A Theoretical and Experimental Comparison of Algorithms for Containment of Conjunctive Queries with Negation

Khalil Ben Mohamed 1, 2 Michel Leclère 2 Marie-Laure Mugnier 2
1 LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We tackle the containment problem for conjunctive queries with negation, which takes two queries q1 and q2 as input and asks if q1 is contained in q2. A general approach for solving this problem consists of considering all completions of q1 (intuitively these completions represent all canonical databases that satisfy q1) and checking if each completion yields the same answer on q2. Since the total number of completions of q1 is exponential in the size of q1, several proposals have aimed at reducing the number (and the size) of the completions checked. In this paper, we propose a unifying framework for comparing algorithms following this general approach and define two kinds of heuristics for exploring the space of completions. Combining these heuristics with both classical kinds of traversals, i.e., depth-first and breadth-first, we obtain four algorithms that we compare experimentally with respect to running time on difficult instances of the containment problem.
Keywords : Experiments Algorithms Containment Homomorphism Databases Conjunctive Queries with Negation
Type de document :
Communication dans un congrès
DEXA: Database and Expert Systems Applications, Aug 2011, Toulouse, France. 22nd International Conference on Database and Expert Systems Applications, LNCS (6860), pp.466-480, 2011, Database and Expert Systems Applications. 〈www.dexa.org〉. 〈10.1007/978-3-642-23088-2_35〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00618779
Contributeur : Khalil Ben Mohamed <>
Soumis le : vendredi 2 septembre 2011 - 18:21:08
Dernière modification le : mercredi 12 décembre 2018 - 14:38:02

Identifiants

Collections

INRIA | GRAPHIK | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

Khalil Ben Mohamed, Michel Leclère, Marie-Laure Mugnier. A Theoretical and Experimental Comparison of Algorithms for Containment of Conjunctive Queries with Negation. DEXA: Database and Expert Systems Applications, Aug 2011, Toulouse, France. 22nd International Conference on Database and Expert Systems Applications, LNCS (6860), pp.466-480, 2011, Database and Expert Systems Applications. 〈www.dexa.org〉. 〈10.1007/978-3-642-23088-2_35〉. 〈lirmm-00618779〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

493

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD