Conjunctive-Query Containment and Constraint Satisfaction.

@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-996-3},
  pages     = {205-213},
  ee        = {http://doi.acm.org/10.1145/275487.275511, db/conf/pods/KolaitisV98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

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.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[AHV95]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[Bib88]

Wolfgang Bibel: Constraint Satisfaction from a Deductive Viewpoint. Artif. Intell. 35(3): 401-413(1988) BibTeX

[Bod93]

Hans L. Bodlaender: A linear time algorithm for finding tree-decompositions of small treewidth. STOC 1993: 226-234 BibTeX

[CM77]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[CR97]

Chandra Chekuri, Anand Rajaraman: Conjunctive Query Containment Revisited. ICDT 1997: 56-70 BibTeX

[Dec90]

Rina Dechter: Decomposing a Relation into a Tree of Binary Relations. J. Comput. Syst. Sci. 41(1): 2-24(1990) BibTeX

[Dec92]

...

[DP92]

Rina Dechter, Judea Pearl: Structure Identification in Relational Data. Artif. Intell. 58(1-3): 237-270(1992) BibTeX

[FV93]

Tomás Feder, Moshe Y. Vardi: Monotone monadic SNP and constraint satisfaction. STOC 1993: 612-622 BibTeX

[GJ79]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX

[GJC94]

Marc Gyssens, Peter Jeavons, David A. Cohen: Decomposing Constraint Satisfaction Problems Using Database Techniques. Artif. Intell. 66(1): 57-89(1994) BibTeX

[HN90]

...

[JC95]

...

[JCG95]

Peter Jeavons, David A. Cohen, Marc Gyssens: A Unifying Framework for Tractable Constraints. CP 1995: 276-291 BibTeX

[JCG96]

Peter Jeavons, David A. Cohen, Marc Gyssens: A test for Tractability. CP 1996: 267-281 BibTeX

[Jea97]

...

[Kum92]

...

[KV]

...

[KV92]

Phokion G. Kolaitis, Moshe Y. Vardi: Infinitary Logics and 0-1 Laws. Inf. Comput. 98(2): 258-294(1992) BibTeX

[KV95]

Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. J. Comput. Syst. Sci. 51(1): 110-134(1995) BibTeX

[KV96]

Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Variable-Confined Logics. LICS 1996: 348-359 BibTeX

[LMSS95]

Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX

[McK43]

...

[Mes89]

...

[MF93]

Alan K. Mackworth, Eugene C. Freuder: The Complexity of Constraint Satisfaction Revisited. Artif. Intell. 59(1-2): 57-62(1993) BibTeX

[PJ97]

...

[PT87]

Robert Paige, Robert Endre Tarjan: Three Partition Refinement Algorithms. SIAM J. Comput. 16(6): 973-989(1987) BibTeX

[Qia96]

Xiaolei Qian: Query Folding. ICDE 1996: 48-55 BibTeX

[Riv74]

...

[RSU95]

Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman: Answering Queries Using Templates with Binding Patterns. PODS 1995: 105-112 BibTeX

[Sar91]

...

[Sch78]

Thomas J. Schaefer: The Complexity of Satisfiability Problems. STOC 1978: 216-226 BibTeX

[Tsa93]

...

[Ull88]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[Ull89]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[Ull97]

Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40 BibTeX

[Var95]

Moshe Y. Vardi: On the Complexity of Bounded-Variable Queries. PODS 1995: 266-276 BibTeX

[vL90]

...

[Yan81]

Mihalis Yannakakis: Node-Deletion Problems on Bipartite Graphs. SIAM J. Comput. 10(2): 310-327(1981) BibTeX

Referenced by

1. Jörg Flum, Markus Frick, Martin Grohe: Query Evaluation via Tree-Decompositions. ICDT 2001: 22-38
2. Moshe Y. Vardi: Constraint Satisfaction and Database Theory: a Tutorial. PODS 2000: 76-85
3. Georg Gottlob, Nicola Leone, Francesco Scarcello: Hypertree Decompositions and Tractable Queries. PODS 1999: 21-32