Constraint Programming and Database Languages: A Tutorial.

@inproceedings{DBLP:conf/pods/Kanellakis95,
  author    = {Paris C. Kanellakis},
  title     = {Constraint Programming and Database Languages: A Tutorial},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {46-53},
  ee        = {http://doi.acm.org/10.1145/212433.212447, db/conf/pods/Kanellakis95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Programming with constraints as primitives can lead to powerful extensions of both deductive and object-oriented data models. The property that makes this new database programming paradigm (called Constraint Query Languages or CQLs) applicable to areas such as spatial databases, where previous data models have weaknesses, is that its basic data type is spatial point set, i.e., a generalization of the relational tuple data type that is close to the natural language specification of the application area. Most importantly, I/O-efficient access to sets of such generalized tuples can be supported through existing multi-dimensional searching data structures. This facilitates the design and implementation of languages for applications such as: solid modeling in design databases, map overlays in geographic databases, and subsequence matching in scientific databases.

This tutorial is an overview of the development of constraint programming for database applications. We examine: (1) the expressive power for various classes of constraints both linear and nonlinear, (2) calculus/algebra language designs combining constraints and complex objects, (3) optimization in the context of constraints, and (4) new data structures for indexing very large sets of constraints. We survey the features of constraint logic programming, deductive databases, and object-oriented databases that are preserved in CQLs and we highlight the challenging new technical problems.

Copyright © 1995 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

[1]

Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX

[2]

Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX

[3]

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

[4]

Dennis S. Arnon: Geometric Reasoning with Logic and Algebra. Artif. Intell. 37(1-3): 37-60(1988) BibTeX

[5]

...

[6]

David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306(1990) BibTeX

[7]

Marianne Baudinet, Marc Niézette, Pierre Wolper: On the Representation of Infinite Temporal Data and Queries. PODS 1991: 280-290 BibTeX

[8]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[9]

Michael Ben-Or, Dexter Kozen, John H. Reif: The Complexity of Elementary Algebra and Geometry. J. Comput. Syst. Sci. 32(2): 251-264(1986) BibTeX

[10]

Leonard Berman: Precise Bounds for Presburger Arithmetic and the Reals with Addition: Preliminary Report. FOCS 1977: 95-99 BibTeX

[11]

Alan Borning: The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory. ACM Trans. Program. Lang. Syst. 3(4): 353-387(1981) BibTeX

[12]

...

[13]

Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580 BibTeX

[14]

Alexander Brodsky, Yoram Kornatzky: The LyriC Language: Querying Constraint Objects. SIGMOD Conference 1995: 35-46 BibTeX

[15]

Alexander Brodsky, Catherine Lassez, Jean-Louis Lassez, Michael J. Maher: Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data. PODS 1995: 54-65 BibTeX

[16]

Alexander Brodsky, Yehoshua Sagiv: Inference of Monotonicity Constraints in Datalog Programs. PODS 1989: 190-199 BibTeX

[17]

Alexander Brodsky, Yehoshua Sagiv: Inference of Inequality Constraints in Logic Programs. PODS 1991: 227-240 BibTeX

[18]

Anni R. Bruss, Albert R. Meyer: On Time-Space Classes and Their Relation to the Theory of Real Addition. STOC 1978: 233-239 BibTeX

[19]

Samuel R. Buss: The Boolean Formula Value Problem Is in ALOGTIME. STOC 1987: 123-131 BibTeX

[20]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[21]

Jan Chomicki: Polynomial Time Query Processing in Temporal Deductive Databases. PODS 1990: 379-391 BibTeX

[22]

Jan Chomicki, Tomasz Imielinski: Relational Specifications of Infinite Query Answers. SIGMOD Conference 1989: 174-183 BibTeX

[23]

Jan Chomicki, Gabriel M. Kuper: Measuring Infinite Relations. PODS 1995: 78-85 BibTeX

[24]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[25]

Jacques Cohen: Constraint Logic Programming Languages. Commun. ACM 33(7): 52-68(1990) BibTeX

[26]

Alain Colmerauer: An Introduction to Prolog III. Commun. ACM 33(7): 69-90(1990) BibTeX

[27]

...

[28]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[29]

Foto N. Afrati, Stavros S. Cosmadakis, Stéphane Grumbach, Gabriel M. Kuper: Linear vs Polynomial Constraints in Database Query Languages. PPCP 1994: 181-192 BibTeX

[30]

...

[31]

Mehmet Dincbas, Pascal Van Hentenryck, Helmut Simonis, Abderrahmane Aggoun, Thomas Graf, Françoise Berthier: The Constraint Logic Programming Language CHIP. FGCS 1988: 693-702 BibTeX

[32]

Jeanne Ferrante, James R. Geiser: An Efficient Decision Procedure for the Theory of Rational Order. Theor. Comput. Sci. 4(2): 227-233(1977) BibTeX

[33]

...

[34]

...

[35]

Eugene C. Freuder: Synthesizing Constraint Expressions. Commun. ACM 21(11): 958-966(1978) BibTeX

[36]

Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300 BibTeX

[37]

...

[38]

Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55 BibTeX

[39]

...

[40]

Michael R. Hansen, Bo S. Hansen, Peter Lucas, Peter van Emde Boas: Integrating Relational Databases and Constraint Languages. Comput. Lang. 14(2): 63-82(1989) BibTeX

[41]

Tirza Hirst, David Harel: Completeness Results for Recursive Data Bases. PODS 1993: 244-252 BibTeX

[42]

Richard Helm, Kim Marriott, Martin Odersky: Constraint-Based Query Optimization for Spatial Databases. PODS 1991: 181-191 BibTeX

[43]

...

[44]

Richard Hull, Jianwen Su: Domain Independence and the Relational Calculus. Acta Inf. 31(6): 513-524(1994) BibTeX

[45]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[46]

Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX

[47]

...

[48]

Froduald Kabanza, Jean-Marc Stévenne, Pierre Wolper: Handling Infinite Temporal Data. PODS 1990: 392-403 BibTeX

[49]

...

[50]

...

[51]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX

[52]

...

[53]

Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243 BibTeX

[54]

...

[55]

Michael Kifer: On Safety, Domain Independence, and Capturability of Database Queries (Preliminary Report). JCDKB 1988: 405-415 BibTeX

[56]

Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) BibTeX

[57]

Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX

[58]

Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 BibTeX

[59]

Dexter Kozen, Chee-Keng Yap: Algebraic Cell Decomposition in NC (Preliminary Version). FOCS 1985: 515-521 BibTeX

[60]

...

[61]

Gabriel M. Kuper: Aggregation in Constraint Databases. PPCP 1993: 166-173 BibTeX

[62]

...

[63]

Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80 BibTeX

[64]

Edward M. McCreight: Priority Search Trees. SIAM J. Comput. 14(2): 257-276(1985) BibTeX

[65]

...

[66]

...

[67]

Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. PODS 1990: 314-330 BibTeX

[68]

Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288 BibTeX

[69]

Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: First-order Queries on Finite Structures over the Reals. LICS 1995: 79-87 BibTeX

[70]

...

[71]

Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159 BibTeX

[72]

Sridhar Ramaswamy, Sairam Subramanian: Path Caching: A Technique for Optimal External Searching. PODS 1994: 25-35 BibTeX

[73]

...

[74]

Peter Z. Revesz: A Closed-Form Evaluation for Datalog Queries with Integer (Gap)-Order Constraints. Theor. Comput. Sci. 116(1&2): 117-149(1993) BibTeX

[75]

...

[76]

Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX

[77]

...

[78]

Divesh Srivastava, Raghu Ramakrishnan: Pushing Constraint Selections. PODS 1992: 301-315 BibTeX

[79]

...

[80]

Peter J. Stuckey, S. Sudarshan: Compiling Query Constraints. PODS 1994: 56-67 BibTeX

[81]

...

[82]

...

[83]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[84]

Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345 BibTeX

[85]

Allen Van Gelder: Deriving Constraints Among Argument Sizes in Logic Programs. PODS 1990: 47-60 BibTeX

[86]

...

[87]

...

[88]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

1. Ouri Wolfson, Liqin Jiang, A. Prasad Sistla, Sam Chamberlain, Naphtali Rishe, Minglin Deng: Databases for Tracking Mobile Units in Real Time. ICDT 1999: 169-186
2. Gösta Grahne, Alberto O. Mendelzon: Tableau Techniques for Querying Information Sources through Global Schemas. ICDT 1999: 332-347
3. Peter Z. Revesz: Safe Query Languages for Constraint Databases. ACM Trans. Database Syst. 23(1): 58-99(1998)
4. Ouri Wolfson, Bo Xu, Sam Chamberlain, Liqin Jiang: Moving Objects Databases: Issues and Solutions. SSDBM 1998: 111-122
5. Ouri Wolfson, Sam Chamberlain, Son Dao, Liqin Jiang, Gisela Mendez: Cost and Imprecision in Modeling the Position of Moving Objects. ICDE 1998: 588-596
6. Christos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. PODS 1997: 12-19
7. A. Prasad Sistla, Ouri Wolfson, Sam Chamberlain, Son Dao: Modeling and Querying Moving Objects. ICDE 1997: 422-432
8. Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48
9. Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16