 |
|
|
On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates |
Full Paper (PDF)
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. |
References, where available, link to the DBLP on the World Wide Web.
[AFS98]...
[CM77]Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90[Cos83]Stavros S. Cosmadakis:
The Complexity of Evaluating Relational Queries.
Information and Control 58(1-3): 101-112(1983)[CR97]Chandra Chekuri, Anand Rajaraman:
Conjunctive Query Containment Revisited.
ICDT 1997: 56-70[GJ79]M. R. Garey, David S. Johnson:
Computer and Intractability: A Guide to NP-Completeness.
W. H. Freeman 1979, ISBN 0-7167-1044-7
[Klu88]Anthony C. Klug:
On Conjunctive Queries Containing Inequalities.
JACM 35(1): 146-160(1988)[LMSS95]Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava:
Answering Queries Using Views.
PODS 1995: 95-104[Pap94]...
[PY82]Christos H. Papadimitriou, Mihalis Yannakakis:
The Complexity of Facets (and Some Facets of Complexity).
STOC 1982: 255-260[Qia96]Xiaolei Qian:
Query Folding.
ICDE 1996: 48-55[RSU95]Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman:
Answering Queries Using Templates with Binding Patterns.
PODS 1995: 105-112[Sar91]...
[Sto77]Larry J. Stockmeyer:
The Polynomial-Time Hierarchy.
TCS 3(1): 1-22(1976)[Ull88]Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
[Ull89]Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
[Ull97]Jeffrey D. Ullman:
Information Integration Using Logical Views.
ICDT 1997: 19-40[vdM97]Ron van der Meyden:
The Complexity of Querying Indefinite Data about Linearly Ordered Domains.
JCSS 54(1): 113-135(1997)[Yan81]Mihalis Yannakakis:
Algorithms for Acyclic Database Schemes.
VLDB 1981: 82-94
|
@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-966-3},
pages = {197-204},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
