Abstract
Evaluating a conjunctive database query is known to be equivalent to solving a constraint satisfaction problem. These problems are NP-complete in general but become tractable, and actually highly parallelizable, if restricted to acyclic or nearly acyclic queries.
This paper surveys recent results by the authors on tractable classes of conjunctive queries and constraint satisfaction problems and presents a new decomposition algorithm for such problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases, Addison-Wesley Publishing Company, 1995.
S. Arnborg, J. Lagergren, and D. Seese. Problems easy for tree-decomposable graphs. J. of Algorithms, 12:308–340, 1991.
C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. On the Desiderability of Acyclic Database Schemes. Journal of ACM, 30(3):479–513, 1983.
P.A. Bernstein, and N. Goodman. The power of natural semijoins. SIAM J. Computing, 10(4):751–771, 1981.
W. Bibel. Constraint Satisfaction from a Deductive Viewpoint. Artificial Intelligence, 35,401–413, 1988.
H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305–1317, 1996.
A.K. Chandra and P.M. Merlin. Optimal Implementation of Conjunctive Queries in relational Databases. In In ACM Symp. on Theory of Computing (STOC’77), pp.77–90, 1977.
Ch. Chekuri and A. Rajaraman. Conjunctive Query Containment Revisited. In Proc. International Conference on Database Theory 1997 (ICDT’97), Delphi, Greece, Jan. 1997, Springer LNCS, Vol. 1186, pp.56–70, 1997.
R. Dechter. Constraint Networks. In Encyclopedia of Artificial Intelligence, second edition, Wiley and Sons, pp. 276–285, 1992.
R. Dechter and J. Pearl. Network based heuristics for CSPs. AIJ, 34(1):1–38, 1988.
R. Dechter and J. Pearl. Tree clustering for constraint networks. Artificial Intelligence, pp. 353–366, 1989.
E.C. Freuder. A sufficient condition for backtrack-free search. JACM, 29(1):24–32, 1982.
E.C. Freuder. A sufficient condition for backtrack bounded search. Journal of the ACM, 32(4):755–761, 1985.
E.C. Freuder. Complexity of K-Tree Structured Constraint Satisfaction Problems. Proc. of AAAI’90, 1990.
M.R. Garey and D.S. Johnson. Computers and Intractability. A Guide to the Theory of NP-completeness. Freeman and Comp., NY, USA, 1979.
N. Goodman, and O. Shmueli. Tree queries: a simple class of relational queries. ACM Trans. on Database Systems, 7(4):653–677, 1982.
G. Gottlob, N. Leone, and F. Scarcello. The Complexity of Acyclic Conjunctive Queries. Proc. of the IEEE Symposium on Foundations of Computer Science (FOCS’98), pp.706–715, Palo Alto, CA, 1998.
G. Gottlob, N. Leone, and F. Scarcello. Advanced Parallel Algorithms for Acyclic Conjunctive Queries. Technical Report DBAI-TR-98/18, available on the web as: http://www.dbai.tuwien.ac.at/staff/gottlob/parallel.ps, or by email from the authors.
G. Gottlob, N. Leone, and F. Scarcello. Hypertree Decompositions and Tractable Queries. Technical Report DBAI-TR-98/21, available as Paper cs.DB/9812022 in The Computer Research Repository, http://xxx.lanl.gov/archive/cs
G. Gottlob, N. Leone, and F. Scarcello. Hypertree Decompositions and Tractable Queries. In Proc. of Symp. on Principles of Database Systems (PODS’99), pp. 21–32, Philadelphia, May, 1999.
G. Gottlob, N. Leone, and F. Scarcello. A Comparison of Structural CSP Decomposition Methods. To appear in Proc. of the International Joint Conference on Artificial Intelligence (IJCAI’99), Stockholm, August, 1999.
M. Gyssens, P.G. Jeavons, and D.A. Cohen. Decomposing constraint satisfaction problems using database techniques. Artificial Intelligence, 66:57–89, 1994.
M. Gyssens, and J. Paredaens. A Decomposition Methodology for Cyclic Databases. In Advances in Database Theory, volume 2, pp. 85–122. Plenum Press New York, NY, 1984.
P. Jeavons, D. Cohen, and M. Gyssens. Closure Properties of Constraints. Journal of the ACM, 44(4):527–548.
Ph. G. Kolaitis andf M. Y. Vardi. Conjunctive-Query Containment and Constraint Satisfaction. In Proc. of Symp. on Principles of Database Systems (PODS’98), pp.205–213, Seattle, Washington, 1998.
D. Maier. The Theory of Relational Databases, Rochville, Md, Computer Science Press, 1986.
N. Robertson and P.D. Seymour. Graph Minors II. Algorithmic Aspects of Tree-Width. J. Algorithms, 7:309–322, 1986.
R.E. Tarjan, and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Computing, 13(3):566–579, 1984.
J.D. Ullman. Principles of Database and Knowledge Base Systems, Vol II, Computer Science Press, Rockville, MD, 1989.
M. Vardi. Complexity of Relational Query Languages. In Proc. of 14th ACM STOC, pp. 137–146, 1982.
A.N. Wilschut, J. Flokstra, and P.M.G. Apers. Parallel evaluation of multi-join queries. In Proc. of SIGMOD’95, San Jose, CA USA, pp.115–126, 1995.
M. Yannakakis. Algorithms for Acyclic Database Schemes. In Proc. of Int. Conf. on Very Large Data Bases (VLDB’81), pp. 82–94, C. Zaniolo and C. Delobel Eds., Cannes, France, 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gottlob, G., Leone, N., Scarcello, F. (1999). On Tractable Queries and Constraints. In: Bench-Capon, T.J., Soda, G., Tjoa, A.M. (eds) Database and Expert Systems Applications. DEXA 1999. Lecture Notes in Computer Science, vol 1677. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48309-8_1
Download citation
DOI: https://doi.org/10.1007/3-540-48309-8_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66448-2
Online ISBN: 978-3-540-48309-0
eBook Packages: Springer Book Archive