Constraint Satisfaction and Database Theory: a Tutorial.

@inproceedings{DBLP:conf/pods/Vardi00,
  author    = {Moshe Y. Vardi},
  editor    = {Victor Vianu and
               Georg Gottlob},
  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},
  ee        = {http://doi.acm.org/10.1145/335168.335209, db/conf/pods/Vardi00.html},
  crossref  = {DBLP:conf/pods/00},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 2000 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.

Printed Edition

Online Edition: ACM Digital Library

References

[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. Artif. Intell. 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 Conference 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. J. Log. Program. 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. Artif. Intell. 41(1): 89-95(1989)

[16]

...

[17]

Rina Dechter: From Local to Global Consistency. Artif. Intell. 55(1): 87-108(1992)

[18]

Rina Dechter, Itay Meiri: Experimental Evaluation of Preprocessing Algorithms for Constraint Satisfaction Problems. Artif. Intell. 68(2): 211-241(1994)

[19]

Rina Dechter, Judea Pearl: Tree Clustering for Constraint Networks. Artif. Intell. 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. Fernández, 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. Commun. ACM 21(11): 958-966(1978)

[24]

Eugene C. Freuder: A Sufficient Condition for Backtrack-Free Search. J. ACM 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. Artif. Intell. 66(1): 57-89(1994)

[33]

...

[34]

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

[35]

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

[36]

Peter Jeavons, David A. Cohen, Marc Gyssens: Closure properties of constraints. J. ACM 44(4): 527-548(1997)

[37]

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

[38]

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)

[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. Artif. Intell. 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 Commun. 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 1994: 368-373

[55]

Peter van Beek, Rina Dechter: Constraint tightness and looseness versus local and global consistency. J. ACM 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

Last update Fri Sep 14 17:28:39 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page