Containment of Conjunctive Queries with Negation: Algorithms and Experiments

Khalil Ben Mohamed 1, 2 Michel Leclère 2 Marie-Laure Mugnier 2
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 consider the containment problem for conjunctive queries with atomic negation. Firstly, we refine an existing algorithm based on homomorphism checks, which itself improves other known algorithms in databases, and analyze it experimentally. Secondly, we present a new algorithm based on the translation of the containment problem into the problem of checking the unsatisfiability of a propositional logical formula, which allows us to use a SAT solver, and we experimentally compare both algorithms.
Type de document :
Communication dans un congrès
DEXA: Database and Expert Systems Applications, Aug 2010, Bilbao, Spain. Springer, 21st International Conference on Database and Expert Systems Applications, LNCS (6262), pp.330-345, 2010, 〈http://www.dexa.org/previous/dexa2010/index.html〉. 〈10.1007/978-3-642-15251-1_27〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00537832
Contributeur : Khalil Ben Mohamed <>
Soumis le : vendredi 19 novembre 2010 - 14:50:53
Dernière modification le : mercredi 12 décembre 2018 - 14:38:02

Identifiants

Collections

Citation

Khalil Ben Mohamed, Michel Leclère, Marie-Laure Mugnier. Containment of Conjunctive Queries with Negation: Algorithms and Experiments. DEXA: Database and Expert Systems Applications, Aug 2010, Bilbao, Spain. Springer, 21st International Conference on Database and Expert Systems Applications, LNCS (6262), pp.330-345, 2010, 〈http://www.dexa.org/previous/dexa2010/index.html〉. 〈10.1007/978-3-642-15251-1_27〉. 〈lirmm-00537832〉

Partager

Métriques

Consultations de la notice

1058