Constraint Satisfaction and Database Theory: a Tutorial Moshe Y. Vardi   View Paper (PDF)   Return to Invited Tutorials 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 Note: References link to DBLP on the Web. [1] Serge Abiteboul , Oliver M. Duschka : Complexity of Answering Queries Using Materialized Views. PODS 1998 : 254-263 [2] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [3] Serge Abiteboul , Dallan Quass , Jason McHugh , Jennifer Widom , Janet L. Wiener : The Lorel Query Language for Semistructured Data. Int. J. on Digital Libraries 1(1) : 68-88(1997) [4] Wolfgang Bibel : Constraint Satisfaction from a Deductive Viewpoint. Artificial Intelligence 35(3) : 401-413(1988) [5] Hans L. Bodlaender : A Linear Time Algorithm for Finding Tree-Decompositions of Small Treewidth. STOC 1993 : 226-234 [6] Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516 [7] Serge Abiteboul , Peter Buneman , Dan Suciu : Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann 1999, ISBN 1-55860-622-X [8] Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi : Rewriting of Regular Expressions and Regular Path Queries. PODS 1999 : 194-204 [9] Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi : Answering Regular Path Queries Using Views. ICDE 2000 : 389-398 [10] ... [11] Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi : View-Based Query Processing for Regular Path Queries with Inverse. PODS 2000 : 58-66 [12] Ashok K. Chandra , David Harel : Horn Clauses Queries and Generalizations. JLP 2(1) : 1-15(1985) [13] Ashok K. Chandra , Philip M. Merlin : Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977 : 77-90 [14] Chandra Chekuri , Anand Rajaraman : Conjunctive Query Containment Revisited. ICDT 1997 : 56-70 [15] Martin C. Cooper : An Optimal k-Consistency Algorithm. Artificial Intelligence 41(1) : 89-95(1989) [16] ... [17] Rina Dechter : From Local to Global Consistency. Artificial Intelligence 55(1) : 87-108(1992) [18] Rina Dechter , Itay Meiri : Experimental Evaluation of Preprocessing Algorithms for Constraint Satisfaction Problems. Artificial Intelligence 68(2) : 211-241(1994) [19] Rina Dechter , Judea Pearl : Tree Clustering for Constraint Networks. Artificial Intelligence 38(3) : 353-366(1989) [20] Oliver M. Duschka , Michael R. Genesereth : Answering Recursive Queries Using Views. PODS 1997 : 109-116 [21] Tomás Feder , Moshe Y. Vardi : Monotone Monadic SNP and Constraint Satisfaction. STOC 1993 : 612-622 [22] Mary F. Fernandez , Daniela Florescu , Jaewoo Kang , Alon Y. Levy , Dan Suciu : Catching the Boat with Strudel: Experiences with a Web-Site Management System. SIGMOD Conference 1998 : 414-425 [23] Eugene C. Freuder : Synthesizing Constraint Expressions. CACM 21(11) : 958-966(1978) [24] Eugene C. Freuder : A Sufficient Condition for Backtrack-Free Search. JACM 29(1) : 24-32(1982) [25] Eugene C. Freuder : Complexity of K-Tree Structured Constraint Satisfaction Problems. AAAI 1990 : 4-9 [26] ... [27] ... [28] Georg Gottlob , Nicola Leone , Francesco Scarcello : The Complexity of Acyclic Conjunctive Queries. FOCS 1998 : 706-715 [29] Georg Gottlob , Nicola Leone , Francesco Scarcello : A Comparison of Structural CSP Decomposition Methods. IJCAI 1999 : 394-399 [30] Georg Gottlob , Nicola Leone , Francesco Scarcello : Hypertree Decompositions and Tractable Queries. PODS 1999 : 21-32 [31] Gösta Grahne , Alberto O. Mendelzon : Tableau Techniques for Querying Information Sources through Global Schemas. ICDT 1999 : 332-347 [32] Marc Gyssens , Peter Jeavons , David A. Cohen : Decomposing Constraint Satisfaction Problems Using Database Techniques. Artificial Intelligence 66(1) : 57-89(1994) [33] ... [34] Peter Jeavons , David Cohen , Marc Gyssens : A Unifying Framework for Tractable Constraints. CP 1995 : 276-291 [35] Peter Jeavons , David Cohen , Marc Gyssens : A test for Tractability. CP 1996 : 267-281 [36] Peter Jeavons , David Cohen , Marc Gyssens : Closure Properties of Constraints. JACM 44(4) : 527-548(1997) [37] Phokion G. Kolaitis , Moshe Y. Vardi : Infinitary Logics and 0-1 Laws. Information and Computation 98(2) : 258-294(1992) [38] Phokion G. Kolaitis , Moshe Y. Vardi : On the Expressive Power of Datalog: Tools and a Case Study. JCSS 51(1) : 110-134(1995) [39] Phokion G. Kolaitis , Moshe Y. Vardi : Conjunctive-Query Containment and Constraint Satisfaction. PODS 1998 : 205-213 [40] ... [41] Vipin Kumar : Algorithms for Constraint-Satisfaction Problems: A Survey. AI Magazine 13(1) : 32-44(1992) [42] Alon Y. Levy : Obtaining Complete Answers from Incomplete Databases. VLDB 1996 : 402-412 [43] Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104 [44] Alan K. Mackworth , Eugene C. Freuder : The Complexity of Constraint Satisfaction Revisited. Artificial Intelligence 59(1-2) : 57-62(1993) [45] David Maier : The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0 Contents [46] Pedro Meseguer : Constraint Satisfaction Problems: An Overview. AI Communications 2(1) : 3-17(1989) [47] ... [48] Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman : Answering Queries Using Templates with Binding Patterns. PODS 1995 : 105-112 [49] Raymond Reiter : On Closed World Data Bases. Logic and Data Bases 1977 : 55-76 [50] Thomas J. Schaefer : The Complexity of Satisfiability Problems. STOC 1978 : 216-226 [51] ... [52-1] Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1 Contents [52-2] Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X Contents [53] Jeffrey D. Ullman : Information Integration Using Logical Views. ICDT 1997 : 19-40 [54] Peter van Beek : On the Inherent Level of Local Consistency in Constraint Networks. AAAI, Vol. 1 1994 : 368-373 [55] Peter van Beek , Rina Dechter : Constraint Tightness and Looseness versus Local and Global Consistency. JACM 44(4) : 549-566(1997) [56] Jan van Leeuwen : Graph Algorithms. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990 : 525-631 [57] Moshe Y. Vardi : The Complexity of Relational Query Languages (Extended Abstract). STOC 1982 : 137-146 [58] Moshe Y. Vardi : On the Complexity of Bounded-Variable Queries. PODS 1995 : 266-276 BIBTEX @inproceedings{DBLP:conf/pods/Vardi00,   author    = {Moshe Y. Vardi},    title     = {Constraint Satisfaction and Database Theory: a Tutorial},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {76-85},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.