Constraint Query Languages.

@inproceedings{DBLP:conf/pods/KanellakisKR90,
  author    = {Paris C. Kanellakis and
               Gabriel M. Kuper and
               Peter Z. Revesz},
  title     = {Constraint Query Languages},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {299-313},
  ee        = {http://doi.acm.org/10.1145/298514.298582, db/conf/pods/KanellakisKR90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

Journal Version

Online Edition: ACM Digital Library

References

[AV88]

Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX

[ASU79]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[AGSS86]

...

[B81]

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

[BKR86]

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

[BS87]

Wolfram Büttner, Helmut Simonis: Embedding Boolean Expressions into Logic Programming. J. Symb. Comput. 4(2): 191-205(1987) BibTeX

[C87]

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

[CH80]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX

[CM76]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[ChI89]

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

[Co70]

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

[D88]

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

[FG77]

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

[GJ79]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX

[HHLE89]

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

[HS89]

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

[I86]

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

[JL87]

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

[Ka90]

...

[Ki88]

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

[Kl88]

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

[KP88]

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

[K80]

Dexter Kozen: Complexity of Boolean Algebras. Theor. Comput. Sci. 10: 221-247(1980) BibTeX

[KY86]

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

[Le87]

...

[L84]

John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX

[MN88]

Ursula Martin, Tobias Nipkow: Unification in Boolean Rings. J. Autom. Reasoning 4(4): 381-396(1988) BibTeX

[PS85]

...

[R83]

...

[R88]

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

[S80]

...

[T51]

...

[U82]

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

[UvG88]

Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. Algorithmica 3: 5-42(1988) BibTeX

[V82]

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

Referenced by

1. Stephan Kreutzer: Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls. ICDT 2001: 248-262
2. Chris Olston, Jennifer Widom: Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data. VLDB 2000: 144-155
3. Stéphane Grumbach, Philippe Rigaux, Luc Segoufin: Manipulating Interpolated Data is Easier than You Thought. VLDB 2000: 156-165
4. Stephan Kreutzer: Fixed-Point Query Languages for Linear Constraint Databases. PODS 2000: 116-125
5. Leonid Libkin: Some Remarks on Variable Independence, Closure, and Orthographic Dimension in Constraint Databases. SIGMOD Record 28(4): 24-28(1999)
6. Stéphane Grumbach, Maurizio Rafanelli, Leonardo Tininini: Querying Aggregate Data. PODS 1999: 174-184
7. Stéphane Grumbach, Philippe Rigaux, Luc Segoufin: On the Orthographic Dimension of Constraint Databases. ICDT 1999: 199-216
8. Gösta Grahne, Alberto O. Mendelzon: Tableau Techniques for Querying Information Sources through Global Schemas. ICDT 1999: 332-347
9. Stéphane Grumbach, Philippe Rigaux, Luc Segoufin: The DEDALE System for Complex Spatial Queries. SIGMOD Conference 1998: 213-224
10. Jeffrey Scott Vitter: External Memory Algorithms. PODS 1998: 119-128
11. Luc Segoufin, Victor Vianu: Querying Spatial Databases via Topological Invariants. PODS 1998: 89-98
12. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
13. Xubo Zhang, Z. Meral Özsoyoglu: Implication and Referential Constraints: A New Formal Reasoning. IEEE Trans. Knowl. Data Eng. 9(6): 894-910(1997)
14. Sridhar Ramaswamy: Efficient Indexing for Constraint and Temporal Databases. ICDT 1997: 419-431
15. Serge Abiteboul, Victor Vianu: Queries and Computation on the Web. ICDT 1997: 262-275
16. Stéphane Grumbach, Philippe Rigaux, Michel Scholl, Luc Segoufin: DEDALE, A Spatial Constraint Database. DBPL 1997: 38-59
17. Julie Wilks: Querying and Updating Constraint Databases with Incomplete Information. ADBIS 1997: 80-89
18. Sha Guo, Wei Sun, Mark Allen Weiss: On Satisfiability, Equivalence, and Impication Problems Involving Conjunctive Queries in Database Systems. IEEE Trans. Knowl. Data Eng. 8(4): 604-616(1996)
19. David Toman: Point vs. Interval-based Query Languages for Temporal Databases. PODS 1996: 58-67
20. Alexei P. Stolboushkin, Michael A. Taitslin: Linear vs. Order Contstrained Queries Over Rational Databases. PODS 1996: 17-27
21. Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92
22. Stéphane Grumbach, Jianwen Su: Towards Practical Constraint Databases. PODS 1996: 28-39
23. Hagit Shatkay, Stanley B. Zdonik: Approximate Queries and Representations for Large Data Sequences. ICDE 1996: 536-545
24. Jacques Calmet, Dirk Debertin, Sebastian Jekutsch, Joachim Schü: An Executable Graphical Representation of Mediatory Information Systems. ICDE 1996: 124-131
25. Thodoros Topaloglou, John Mylopoulos: Representing Partial Spatial Information in Databases. ER 1996: 325-340
26. Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534
27. Jan Chomicki: Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding. ACM Trans. Database Syst. 20(2): 149-186(1995)
28. James J. Lu, Guido Moerkotte, Joachim Schü, V. S. Subrahmanian: Efficient Maintenance of Materialized Mediated Views. SIGMOD Conference 1995: 340-351
29. Alexei P. Stolboushkin, Michael A. Taitslin: Finite Queries do not Have Effective Syntax. PODS 1995: 277-285
30. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
31. Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77
32. Jan Chomicki, Gabriel M. Kuper: Measuring Infinite Relations. PODS 1995: 78-85
33. Peter Z. Revesz: Datalog Queries of Set Constraint Databases. ICDT 1995: 425-438
34. Jan Paredaens: Spatial Databases, The Final Frontier. ICDT 1995: 14-32
35. Marianne Baudinet, Jan Chomicki, Pierre Wolper: Constraint-Generating Dependencies. ICDT 1995: 322-337
36. Stéphane Grumbach, Zoé Lacroix: Computing Queries on Linear Constraint Databases. DBPL 1995: 11
37. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
38. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: The CORAL Deductive System. VLDB J. 3(2): 161-210(1994)
39. Jiawei Han: Constraint-Based Query Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 6(1): 96-107(1994)
40. Raghu Ramakrishnan, Divesh Srivastava: Semantics and Optimization of Constraint Queries in Databases. IEEE Data Eng. Bull. 17(2): 14-17(1994)
41. Peter J. Stuckey, S. Sudarshan: Compiling Query Constraints. PODS 1994: 56-67
42. Sridhar Ramaswamy, Sairam Subramanian: Path Caching: A Technique for Optimal External Searching. PODS 1994: 25-35
43. Inderpal Singh Mumick, Oded Shmueli: Universal Finiteness and Satisfiability. PODS 1994: 190-200
44. Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300
45. Jan Chomicki, Tomasz Imielinski: Finite Representation of Infinite Query Answers. ACM Trans. Database Syst. 18(2): 181-223(1993)
46. Divesh Srivastava, Raghu Ramakrishnan, Praveen Seshadri, S. Sudarshan: Coral++: Adding Object-Orientation to a Logic Database Language. VLDB 1993: 158-170
47. Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181
48. Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
49. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122
50. Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243
51. Manolis Koubarakis: Representation and Querying in Temporal Databases: the Power of Temporal Constraints. ICDE 1993: 327-334
52. Divesh Srivastava, Raghu Ramakrishnan: Pushing Constraint Selections. PODS 1992: 301-315
53. Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345
54. Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80
55. Allen Van Gelder: The Well-Founded Semantics of Aggregation. PODS 1992: 127-138
56. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Linear Programming. PODS 1992: 283-292
57. Catriel Beeri: New Data Models and Languages - the Challenge. PODS 1992: 1-15
58. Marianne Baudinet, Marc Niézette, Pierre Wolper: On the Representation of Infinite Temporal Data and Queries. PODS 1991: 280-290
59. Jiawei Han: Constraint-Based Reasoning in Deductive Databases. ICDE 1991: 257-265
60. Jean-Louis Lassez: From LP to LP: Programming with Constraints. DBPL 1991: 257-283
61. Jean-Louis Lassez: Querying Constraints. PODS 1990: 288-298
62. Peter Z. Revesz: A Closed Form for Datalog Queries with Integer Order. ICDT 1990: 187-201
63. Gabriel M. Kuper: On The Expressive Power of the Relational Calculus with Arithmetic Constraints. ICDT 1990: 202-211