|
|
|
@inproceedings{DBLP:conf/pods/KolaitisMT98,
author = {Phokion G. Kolaitis and
David L. Martin and
Madhukar N. Thakur},
title = {On the Complexity of the Containment Problem for Conjunctive
Queries with Built-in Predicates},
booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-996-3},
pages = {197-204},
ee = {http://doi.acm.org/10.1145/275487.275510, db/conf/pods/KolaitisMT98.html},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
When the inputs are conjunctive queries with \=, <=, or < as built-in predicates, the query containment problem "is Q1 contained in Q2?" is Pi2P-complete and, thus, highly intractable. In this paper, we investigate the impact of syntactic and structural conditions on the computational complexity of the query containment problem for safe conjunctive queries with disequation (that is, "not equals", notated here as \=) as a built-in predicate. In the case of "pure" conjunctive queries (no built-in predicates), it is known that the boundary between polynomial-time solvability and NP-completeness is crossed, when the number of occurrences of any database predicate in Q1 increases from two to three. We show here that, as regards safe conjunctive queries with disequations, the same syntactic condition delineates the boundary between membership in coNP and Pi2P-completeness. Moreover, it is also known that the "pure" conjunctive query containment problem is solvable in polynomial time, if the hypergraph associated with the database predicates of Q2 is acyclic. In contrast, we show that the very same structural condition does not lower the computational complexity of the containment problem for safe conjunctive queries with disequations, that is, the problem remains Pi2P-complete.
We also analyze the computational complexity of the query equivalence problem for conjunctive queries with disequations, when one of the two queries is fixed. We show that this problem can be DP-complete, where DP is the class of all decision problems that are the conjunction of a problem in NP and a problem in coNP. It follows that, as regards conjunctive queries with disequations, the complexity of the query equivalence problem may be higher than the complexity of the query containment problem, when one of the two queries is fixed.
Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.