Containment of Conjunctive Queries with Negation: Algorithms and Experiments

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

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.

Mots clés: Databases; Conjunctive Queries with Negation; Containment; Homomorphism; Algorithms; Experiments

Domaines: Intelligence artificielle [cs.AI]; Base de données [cs.DB]

Khalil Ben Mohamed, Michel Leclère, Marie-Laure Mugnier. Containment of Conjunctive Queries with Negation: Algorithms and Experiments. DEXA 2010 - 21st International Conference on Database and Expert Systems Applications, Aug 2010, Bilbao, Spain. pp.330-345, ⟨10.1007/978-3-642-15251-1_27⟩. ⟨lirmm-00537832⟩