 |
|
|
Conjunctive-Query Containment and Constraint Satisfaction |
Full Paper (PDF)
Conjunctive-query containment is recognized as a fundamental problem in database query evaluation and optimization. At the same time, constraint satisfaction is recognized as a fundamental problem in artificial intelligence. What do conjunctive-query containment and constraint satisfaction have in common? Our main conceptual contribution in this paper is to point out that, despite their very different formulation, conjunctive-query containment and constraint satisfaction are essentially the same problem. The reason is that they can be recast as the following fundamental algebraic problem: given two finite relational structures A and B, is there a homomorphism from A to B? As formulated above, the homomorphism problem is uniform in the sense that both relational structures A and B are part of the input. By fixing the structure B, one obtains the following non-uniform problem: given a finite relational structure A, is there a homomorphism from A to B? In general, non-uniform tractability results do not uniformize. Thus, it is natural to ask: which tractable cases of non-uniform tractability results for constraint satisfaction and conjunctive-query containment do uniformize?
Our main technical contribution in this paper is to show that several cases of tractable non-uniform constraint satisfaction problems do indeed uniformize. We exhibit three non-uniform tractability results that uniformize and, thus, give rise to polynomial-time solvable cases of constraint satisfaction and conjunctive-query containment. We begin by examining the tractable cases of Boolean constraint satisfaction problems and show that they do uniformize. This can be applied to conjunctive-query containment via binarization; in particular, it yields one of the known tractable cases of conjunctive query containment. After this, we show that tractability results for constraint-satisfaction problems that can be expressed using Datalog programs with bounded number of distinct variables also uniformize. Finally, we establish that tractability results for queries with bounded treewidth uniformize as well. |
References, where available, link to the DBLP on the World Wide Web.
[AHV95]Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents[Bib88]Wolfgang Bibel:
Constraint Satisfaction from a Deductive Viewpoint.
Artificial Intelligence 35(3): 401-413(1988)[Bod93]Hans L. Bodlaender:
A Linear Time Algorithm for Finding Tree-Decompositions of Small Treewidth.
STOC 1993: 226-234[CM77]Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90[CR97]Chandra Chekuri, Anand Rajaraman:
Conjunctive Query Containment Revisited.
ICDT 1997: 56-70[Dec90]Rina Dechter:
Decomposing a Relation into a Tree of Binary Relations.
JCSS 41(1): 2-24(1990)[Dec92]...
[DP92]Rina Dechter, Judea Pearl:
Structure Identification in Relational Data.
Artificial Intelligence 58(1-3): 237-270(1992)[FV93]Tomás Feder, Moshe Y. Vardi:
Monotone Monadic SNP and Constraint Satisfaction.
STOC 1993: 612-622[GJ79]M. R. Garey, David S. Johnson:
Computer and Intractability: A Guide to NP-Completeness.
W. H. Freeman 1979, ISBN 0-7167-1044-7
[GJC94]Marc Gyssens, Peter Jeavons, David A. Cohen:
Decomposing Constraint Satisfaction Problems Using Database Techniques.
Artificial Intelligence 66(1): 57-89(1994)[HN90]...
[JC95]...
[JCG95]Peter Jeavons, David Cohen, Marc Gyssens:
A Unifying Framework for Tractable Constraints.
CP 1995: 276-291[JCG96]Peter Jeavons, David Cohen, Marc Gyssens:
A test for Tractability.
CP 1996: 267-281[Jea97]...
[Kum92]...
[KV]...
[KV92]Phokion G. Kolaitis, Moshe Y. Vardi:
Infinitary Logics and 0-1 Laws.
Information and Computation 98(2): 258-294(1992)[KV95]Phokion G. Kolaitis, Moshe Y. Vardi:
On the Expressive Power of Datalog: Tools and a Case Study.
JCSS 51(1): 110-134(1995)[KV96]Phokion G. Kolaitis, Moshe Y. Vardi:
On the Expressive Power of Variable-Confined Logics.
LICS 1996: 348-359[LMSS95]Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava:
Answering Queries Using Views.
PODS 1995: 95-104[McK43]...
[Mes89]...
[MF93]Alan K. Mackworth, Eugene C. Freuder:
The Complexity of Constraint Satisfaction Revisited.
Artificial Intelligence 59(1-2): 57-62(1993)[PJ97]...
[PT87]Robert Paige, Robert Endre Tarjan:
Three Partition Refinement Algorithms.
SIAM J. Comput. 16(6): 973-989(1987)[Qia96]Xiaolei Qian:
Query Folding.
ICDE 1996: 48-55[Riv74]...
[RSU95]Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman:
Answering Queries Using Templates with Binding Patterns.
PODS 1995: 105-112[Sar91]...
[Sch78]Thomas J. Schaefer:
The Complexity of Satisfiability Problems.
STOC 1978: 216-226[Tsa93]...
[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[Var95]Moshe Y. Vardi:
On the Complexity of Bounded-Variable Queries.
PODS 1995: 266-276[vL90]...
[Yan81]Mihalis Yannakakis:
Node-Deletion Problems on Bipartite Graphs.
SIAM J. Comput. 10(2): 310-327(1981)
|
@inproceedings{DBLP:conf/pods/KolaitisV98,
author = {Phokion G. Kolaitis and
Moshe Y. Vardi},
title = {Conjunctive-Query Containment and Constraint Satisfaction},
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 = {205-213},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
