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.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00537832
Contributor : Khalil Ben Mohamed <>
Submitted on : Friday, November 19, 2010 - 2:50:53 PM
Last modification on : Wednesday, June 5, 2019 - 11:58:13 AM

Links full text

Identifiers

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. pp.330-345, ⟨10.1007/978-3-642-15251-1_27⟩. ⟨lirmm-00537832⟩

Share

Metrics

Record views

1408