On the Pi-2-P Completeness of the Containment Problem of Conjunctive Queries with Negation and Other Problems

Marie-Laure Mugnier 1
1 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 : This research note proves the $\Pi_2^P$-completeness of several equivalent problems: deduction in the first-order logical fragment composed of existential conjunctive formulas, deduction in polarized graphs (which are simple conceptual graphs with negation on relations, built on a simplified vocabulary) and containment of conjunctive queries with negation. The exhibited reduction is essentially due to Guillaume Bagan (November 2004).
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00129534
Contributor : Marie-Laure Mugnier <>
Submitted on : Wednesday, February 7, 2007 - 11:42:02 PM
Last modification on : Wednesday, December 12, 2018 - 2:38:02 PM

Identifiers

  • HAL Id : lirmm-00129534, version 1

Collections

Citation

Marie-Laure Mugnier. On the Pi-2-P Completeness of the Containment Problem of Conjunctive Queries with Negation and Other Problems. RR-07004, 2007, pp.7. ⟨lirmm-00129534⟩

Share

Metrics

Record views

225