Constraint satisfaction and database theory: a tutorial

ABSTRACT

A large class of problems in AI and other areas of computer science can be viewed as constraint-satisfaction problems. This includes problems in machine vision, belief maintenance, scheduling, temporal reasoning, type reconstruction, graph theory, and satisfiability. In general, the constraint satisfaction-problem is NP-complete, so searching for tractable cases is an active research area. It turns out that constraint satisfaction has an intimate connection with database theory: constraint-satisfaction problems can be recast as database problems and database problems can be recast as constraint-satisfaction problems. In this tutorial, I will cover the fundamentals of constraints satisfaction and describe its intimate relationship with database theory from various perspectives.

References

1. 1.S. Abiteboul and O. Duschka. Complexity of answering queries using materialized views. In Proc. of the 17th A CM Sym. on Principles of Database Systems (PODS'98), pages 254-265, 1998.]]
2. 2.S. Abiteboul, R. Hull, and V. Vianu. Foundations of databases. Addison-Wesley, 1995.]]
3. 3.S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J.L. Wiener. The Lorel query language for semistructured data. Int. J. on Digital Libraries, 1(1):68-88, 1997.]]
4. 4.W. Bibel. Constraint satisfaction from a deductive viewpoint. Artificial Intelligence, 35:401-413, 1988.]]
5. 5.H.L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. In Proc. 25th ACM Symp. on Theory of Computing, pages 226-234, 1993.]]
6. 6.P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization technique for unstructured data. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 505-516, 1996.]]
7. 7.P. Buneman, D. Suciu, and S. Abiteboul. Data on the Web : From Relations to Semistructured Data and XML. Morgan Kaufmann, 1999.]]
8. 8.D. Calvanese, G. De Giacomo, M. Lenzerini, and M.Y. Vardi. Rewriting of regular expressions and regular path queries. In Proc. of the 18th ACM Sym. on Principles of Database Systems (PODS'99), pages 194-204, 1999.]]
9. 9.D. Calvanese, G. De Giacomo, M. Lenzerini, and M.Y. Vardi. Answering regular-path queries using views. In Proc. of the 16th IEEE Int. Conf. on Data Engineering (ICDE 2000), pages 389-398, 2000.]]
10. 10.D. Calvanese, G. De Giacomo, M. Lenzerini, and M.Y. Vardi. View-based query processing and constraint satisfaction. Submitted, 2000.]]
11. 11.D. Calvanese, G. De Giacomo, M. Lenzerini, and M.Y. Vardi. View-based query processing for regular-path queries with inverse. In Proc. of the 19th ACM Sym. on Principles of Database Systems (PODS 2000), 2000. This proceedings.]]
12. 12.A. Chandra and D. Hard. Horn clause queries and generalizations. Journal of Logic Programming, 1:1-15, 1985.]]
13. 13.A.K. Chandra and P.M. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proc. 9th A CM Symp. on Theory of Computing, pages 77-90, 1977.]]
14. 14.C. Chekuri and A. Ramajaran. Conjunctive query containment revisited. Technical report, Stanford University, November 1998.]]
15. 15.M.C. Cooper. An optimal k-consistency algorithm. Artificial Intelligence, 41(1):89-95, 1989.]]
16. 16.R. Dechter. Constraint networks. In S.C. Shapiro, editor, Encyclopedia of Artificial Intelligence, pages 276- 185. Wiley, New York, 1992.]]
17. 17.R. Dechter. From local to global consistency. Artificial Intelligence, 55(1):87-107, May 1992.]]
18. 18.R. Dechter and I. Meiri. Experimental evaluation of preprocessing algorithms for constraint satisfaction problems. Artificial Intelligence, 68:211-241, 1994.]]
19. 19.R. Dechter and J. Pearl. Tree clustering for constraint networks. Artificial Intelligence, pages 353-366, 1989.]]
20. 20.O.M. Duschka and M.R. Genesereth. Answering recursive queries using views. In Proc. of the 16th A CM Sym. on Principles of Database Systems (PODS'97), pages 109-116, 1997.]]
21. 21.T. Feder and M.Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. on Computing, 28:57-104, 1999. Preliminary version in Proc. 25th A CM Syrup. on Theory of Computing, May 1993, pp. 612-622.]]
22. 22.M.F. Fernandez, D. Florescu, J. Kang, A.Y. Levy, and D. Suciu. Catching the boat with strudel: Experiences with a web-site management system. In Proc. of the A CM SIGMOD Int. Conf. on Management of Data, pages 414-425, 1998.]]
23. 23.E.C. Freuder. Synthesizing constraint expressions. Communications of the A CM, 21(11):958-966, November 1978.]]
24. 24.E.C. Freuder. A sufficient condition for backtrack-free search. Journal of the Association for Computing Machinery, 29(1):24-32, 1982.]]
25. 25.E.C Freuder. Complexity of k-tree structured constraint satisfaction problems. In Proc. AAAI-90, pages 4-9, 1990.]]
26. 26.D.H. Frost. Algorithms and Heuristics for Constraint Satisfaction Problems. PhD thesis, Department of Computer Science, University of California, Irvine, 1997.]]
27. 27.M.L. Ginsberg, editor. Readings in Nonmonotonic Reasoning. Morgan Kaufmann, Los Altos, 1987.]]
28. 28.G. Gottlob, N. Leone, and F. Scarcello. The complexity of acyclic conjunctive queries. In Proc. 39th IEEE Syrup. on Foundation of Computer Science, pages 706- 715, 1998.]]
29. 29.G. Gottlob, N. Leone, and F. Scarcello. A comparison of structural CSP decomposition methods. In Proc. 16th Int'l Joint Conf. on Artificial Intelligence (IJCAI'99), pages 394-399, 1999.]]
30. 30.G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. In Proc. 18th ACM Syrup. on Principles of Database Systems, pages 21-32, 1999.]]
31. 31.G. Grahne and A.O. Mendelzon. Tableau techniques for querying information sources through global schemas. In Proc. of the 7th Int. Conf. on Database Theory (ICDT'99), volume 1540 of Lecture Notes in Computer Science, pages 332-347. Springer-Verlag, 1999.]]
32. 32.M. Gyssens, P.G. Jeavons, and D.A. Cohen. Decomposition constraint satisfaction problems using database techniques. Artificial Intelligence, 66:57-89, 1994.]]
33. 33.P. Hell and J. Neget~il. On the complexity of H- coloring. Journal of Combinatorial Theory, Series B, 48:92-110, 1990.]]
34. 34.P. Jeavons, D. Cohen, and M. Gyssens. A unifying framework for tractable constraints. In U. Montanari and F. Rossi, editors, Proceedings of 1st International Conference on Principles and Practice of Constraint Programming, CP95, pages 276-291. Springer-Verlag, 1995.]]
35. 35.P. Jeavons, D. Cohen, and M. Gyssens. A test for tractability. In E.C. Freuder, editor, Proceedings of 2nd International Conference on Principles and Practice of Constraint Programming, CP96, pages 267-281. Springer-Verlag, 1996.]]
36. 36.P. Jeavons, D. Cohen, and M. Gyssens. Closure properties of constraints. Journal of the A CM, 44(4):527-48, 1997.]]
37. 37.Ph. G. Kolaitis and M. Y. Vardi. Infinitary logic and 0-1 laws. Information and Computation, 98:258-294, 1992. Special issue: Selections from the Fifth Annual IEEE Symposium on Logic in Computer Science.]]
38. 38.Ph. G. Kolaitis and M. Y. Vardi. On the expressive power of Datalog: tools and a case study. Journal of Computer and System Sciences, 51(1):110-134, August 1995. Special Issue: Selections from Ninth Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Nashville, TN, USA, 2-4 April 1990.]]
39. 39.Ph.G. Kolaitis and M.Y. Vardi. Conjunctivequery containment and constraint satisfaction. In Proc. 17th ACM Syrup. on Principles of Database Systems, pages 205-13, 1998. Full version at http ://www. cs. rice. edu/~ vardi/papers.]]
40. 40.Ph.G. Kolaitis and M.Y. Vardi. A game-theoretic approach to constraint satisfaction. Submitted, 2000.]]
41. 41.V. Kumar. Algorithms for constraint-satisfaction problems. AI Magazine, 13:32-44, 1992.]]
42. 42.A.Y. Levy. Obtaining complete answers from incomplete databases. In Proc. of the 22nd Int. Conf. on Very Large Data Bases (VLDB'96), pages 402-412, 1996.]]
43. 43.A.Y. Levy, A.O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In Proc. l~th ACM Syrup. on Principles of Database Systems, pages 95-104, 1995.]]
44. 44.A.K. Mackworth and E.C. Freuder. The complexity of constraint satisfaction revisited. Artificial Intelligence, 59(1-2):57-62, 1993.]]
45. 45.D. Maier. The Theory of Relational Databases. Computer Science Press, Rockville, Md., 1983.]]
46. 46.P. Meseguer. Constraint satisfaction problems: an overview. AICOM, 2:3-16, 1989.]]
47. 47.J. Pearson and P. Jeavons. A survey of tractable constraint satisfaction problems. Technical Report CSD- TR-97-15, Royal Holloway University of London, 1997.]]
48. 48.A. Rajaraman, Y. Sagiv, and J.D. Ullman. Answering queries using templates with binding patterns. In Proc. of the l~th A CM Sym. on Principles of Database Systems (PODS'95), 1995.]]
49. 49.R. Reiter. On closed world data bases. In Herv4 Gallaire and Jack Minker, editors, Logic and Databases, pages 119-140. Plenum Publ. Co., New York, 1978. Republished in {27}.]]
50. 50.T.J. Schaefer. The complexity of satisfiability problems. In Proc. l Oth A CM Syrup. on Theory of Computing, pages 216-226, 1978.]]
51. 51.E.P.K. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.]]
52. 52.J. D. Ullman. Database and Knowledge-Base Systems, Volumes I and II. Computer Science Press, 1989.]]
53. 53.J.D. Ullman. Information integration using logical views. In Proc. of the 6th Int. Conf. on Database Theory (ICDT'9V), volume 1186 of Lecture Notes in Computer Science, pages 19-40. Springer-Verlag, 1997.]]
54. 54.P. van Beek. On the inherent tightness of local consistency in constraint networks. In Proc. of National Conference on Artificial Intelligence (AAAI-9~), pages 368-373, 1994.]]
55. 55.P. van Beek and R. Dechter. Constraint tightness and looseness versus local and global consistency. Journal of the A CM, 44(4):549-566, 1997.]]
56. 56.J. van Leeuwen. Graph algorithms. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science A: Algorithms and Complezity, chapter 10, pages 525-631. Elsevier, Amsterdam, 1990.]]
57. 57.M.Y. Vardi. The complexity of relational query languages. In Proc. of the l~th A CM Sym. on Theory of Computing (STOC'82), pages 137-146, 1982.]]
58. 58.M.Y. Vardi. On the complexity of bounded-variable queries. In Proc. l~th A CM Syrup. on Principles of Database Systems, pages 266-76, 1995.]]

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Philosophical/theoretical foundations of artificial intelligence

• Security and privacy

  • Database and storage security

• Theory of computation

  • Logic

  • Models of computation

  • Theory and algorithms for application domains

    • Database theory

      • Theory of database privacy and security