When is Naïve Evaluation Possible?

Amélie Gheerbrant 1, 2 Leonid Libkin 1 Cristina Sirangelo 3, 4
4 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : The term naïve evaluation refers to evaluating queries over incomplete databases as if nulls were usual data values, i.e., 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: i.e., 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 open-world 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 naïve 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, naïve evaluation makes perfect sense under assumptions different from open-world. Our key observations are: (1) naïve evaluation is equivalent to monotonicity of queries with respect to a semantics-induced ordering, and (2) for most reasonable semantics, such monotonicity is captured by preservation under various types of homomorphisms. Using these results we find classes of queries for which naïve evaluation works, e.g., positive first-order formulae for the closed-world semantics. Even more, we introduce a general relation-based 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 first-order queries for which naïve evaluation works under such semantics.
Type de document :
Communication dans un congrès
PODS - 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013, Jun 2013, New York, United States. 2013
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

Contributeur : Cristina Sirangelo <>
Soumis le : vendredi 22 novembre 2013 - 18:04:52
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : dimanche 23 février 2014 - 04:31:49


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00908404, version 1



Amélie Gheerbrant, Leonid Libkin, Cristina Sirangelo. When is Naïve Evaluation Possible?. PODS - 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013, Jun 2013, New York, United States. 2013. 〈hal-00908404〉



Consultations de la notice


Téléchargements de fichiers