Paper Info
Title
Identifying the Extent of Completeness of Query Answers over Partially Complete Databases
Abstract
In many applications including loosely coupled cloud databases, collaborative editing and network monitoring, data from multiple sources is regularly used for query answering. For reasons such as system failures, insufficient author knowledge or network issues, data may be temporarily unavailable or generally nonexistent. Hence, not all data needed for query answering may be available. In this paper, we propose a natural class of completeness patterns, expressed by selections on database tables, to specify complete parts of database tables. We then show how to adapt the operators of relational algebra so that they manipulate these completeness patterns to compute completeness patterns pertaining to query answers. Our proposed algebra is computationally sound and complete with respect to the information that the patterns provide. We show that stronger completeness patterns can be obtained by considering not only the schema but also the database instance and we extend the algebra to take into account this additional information. We develop novel techniques to efficiently implement the computation of completeness patterns on query answers and demonstrate their scalability on real data.
Year
DOI
Venue
2015
10.1145/2723372.2750544
ACM SIGMOD Conference
DocType
Citations 
PageRank 
Conference
14
0.77
References 
Authors
18
4
Name
Order
Citations
PageRank
Simon Razniewski115727.07
Flip Korn22141380.45
Werner Nutt32009395.43
Divesh Srivastava489841191.22