Skip to Main content Skip to Navigation
Conference papers

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 metadata
Contributor : Khalil Ben Mohamed Connect in order to contact the contributor
Submitted on : Friday, November 19, 2010 - 2:50:53 PM
Last modification on : Friday, August 5, 2022 - 3:03:00 PM

Links full text




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⟩



Record views