Containment for Conjunctive Queries with Negation

A query Q is contained in a query Q’ if, for every database D, the result Q(D) is contained in Q'(D). Deciding containment is an interesting and often used sub-problem for minimisation of queries, verification of dependencies and other tasks. It was shown that the containment of conjunctive queries is intimately related to the existence of a homomorphism between the queries and that deciding containment in this case is NP-complete [1]. We have shown that deciding containment for conjunctive queries _with negation_ is coNEXPTIME-complete in general [2]. Previously the problem seems only to have been studied for queries over schemas of bounded arity, where it was known to be Pi^p_2-complete [3]. PUBLICATION: This result has been published in [2] for the 19th International Conference on Database Theory, ICDT 2016, Bordeaux, France, March 15-18, 2016. REFERENCES [1] Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 [2] Gaetano Geck, Bas Ketsman, Frank Neven, Thomas Schwentick: Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation. ICDT 2016: 9: 1-9: 17 [3] Marie-Laure Mugnier, Geneviève Simonet, Michaël Thomazo: On the complexity of entailment in existential conjunctive first-order logic with atomic negation. Inf. Comput. 215: 8-31 (2012)

Authors

• With Bas Ketsman
• Frank Neven
• Thomas Schwentick

Keywords

No keywords are indexed for this paper.