Projects per year
Abstract
The term naive evaluation refers to evaluating queries over incomplete databases as if nulls were usual data values, that is, to using the standard database query evaluation engine. Since the semantics of query answering over incomplete databases is that of certain answers, we would like to know when naïve evaluation computes them, that is, when certain answers can be found without inventing new specialized algorithms. For relational databases it is well known that unions of conjunctive queries possess this desirable property, and results on preservation of formulae under homomorphisms tell us that, within relational calculus, this class cannot be extended under the openworld assumption.
Our goal here is twofold. First, we develop a general framework that allows us to determine, for a given semantics of incompleteness, classes of queries for which naive evaluation computes certain answers. Second, we apply this approach to a variety of semantics, showing that for many classes of queries beyond unions of conjunctive queries, naive evaluation makes perfect sense under assumptions different from open world. Our key observations are: (1) naive evaluation is equivalent to monotonicity of queries with respect to a semanticsinduced ordering, and (2) for most reasonable semantics of incompleteness, such monotonicity is captured by preservation under various types of homomorphisms. Using these results we find classes of queries for which naive evaluation works, for example, positive firstorder formulae for the closedworld semantics. Even more, we introduce a general relationbased framework for defining semantics of incompleteness, show how it can be used to capture many known semantics and to introduce new ones, and describe classes of firstorder queries for which naive evaluation works under such semantics.
Our goal here is twofold. First, we develop a general framework that allows us to determine, for a given semantics of incompleteness, classes of queries for which naive evaluation computes certain answers. Second, we apply this approach to a variety of semantics, showing that for many classes of queries beyond unions of conjunctive queries, naive evaluation makes perfect sense under assumptions different from open world. Our key observations are: (1) naive evaluation is equivalent to monotonicity of queries with respect to a semanticsinduced ordering, and (2) for most reasonable semantics of incompleteness, such monotonicity is captured by preservation under various types of homomorphisms. Using these results we find classes of queries for which naive evaluation works, for example, positive firstorder formulae for the closedworld semantics. Even more, we introduce a general relationbased framework for defining semantics of incompleteness, show how it can be used to capture many known semantics and to introduce new ones, and describe classes of firstorder queries for which naive evaluation works under such semantics.
Original language  English 

Article number  31 
Pages (fromto)  31:131:42 
Number of pages  42 
Journal  ACM Transactions on Database Systems 
Volume  39 
Issue number  4 
DOIs  
Publication status  Published  1 Dec 2014 
Keywords
 Incompleteness, certain answers, homomorphisms, naive tables/evaluation, orderings
Fingerprint
Dive into the research topics of 'Naive Evaluation of Queries over Incomplete Databases'. Together they form a unique fingerprint.Projects
 2 Finished


XML with Incomplete Information: Representation, Querying and Applications
1/09/09 → 30/11/13
Project: Research