Constraint query languages (preliminary report)

ABSTRACT

We discuss the relationship between constraint programming and database query languages. We show that bottom-up, efficient, declarative database programming can be combined with efficient constraint solving. The key intuition is that the generalization of a ground fact, or tuple, is a conjunction of constraints. We describe the basic Constraint Query Language design principles, and illustrate them with four different classes of constraints: Polynomial, rational order, equality, and Boolean constraints.

REFERENCES

• AV88: Serge Abiteboul , Victor Vianu, Procedural and declarative database update languages, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.240-250, March 1988, Austin, Texas, United States [doi>10.1145/308386.308448]
• ASU79: A.V. Aho, Y. Sagiv, J.D. Ullman. Equivalences among Relational Expressions. SIAM J. of Computing, 8:2:218-246, 1979.
• AGSS86: A.K. Aylamazyan, M.M. Gilula, A.P. Stolboushkin, G.F. Schwartz. Reduction of the Relational Model with Infinite Domain to the Case of Finite Domains. Proc. USSR Acad. of Science (Doklady), 286(2):308- 311, 1986.
• B81: Alan Borning, The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.353-387, Oct. 1981 [doi>10.1145/357146.357147]
• BKR86: Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, v.32 n.2, p.251-264, April 1986 [doi>10.1016/0022-0000(86)90029-2]
• BS87: Wolfram Büttner , Helmut Simonis, Embedding Boolean expressions into logic programming, Journal of Symbolic Computation, v.4 n.2, p.191-205, Oct. 1987 [doi>10.1016/S0747-7171(87)80065-2]
• C87: A. Colmerauer. An Introduction to Prolog III. Draft, 1987.
• CH80: A.K. Chandra, D. Harel. Computable Queries for Relational Data Bases. JCSS, 21:156-178, 1980.
• CM76: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• ChI89: Jan Chomicki , Tomasz Imieliński, Relational specifications of infinite query answers, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.174-183, June 1989, Portland, Oregon, United States
• CO70: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• D88: M. Dincbas, etal. The Constraint Logic Programming Language CHIP. Proc. Fifth Generation Computer Systems, Tokyo Japan, 1988.
• FG77: J. Ferrante, J.R. Geiser. An Efficient Decision Procedure for the Theory of Rational Order. Theoretical Computer Science, 4:227-233, 1977.
• GJ79: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• HHLE89: M. R. Hansen , B. S. Hansen , P. Lucas , P. van Emde Boas, Integrating relational databases and constraint languages, Computer Languages, v.14 n.2, p.63-82, Aug. 1989 [doi>10.1016/0096-0551(89)90014-3]
• HS89: R. Hull, J. Su. Domain Independence and the RelationM Calculus. Technical Report 88-64, University of Southern California, submitted to IP L, 1989.
• I86: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• JL87: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• Ka90: P.C. Kanellakis. Elements of RelationM Database Theory. Handbook of Theoretical Computer Science, North-Holland, to appear.
• Ki88: M. Kifer. On Safety, Domain Independence, and Capturability of Database Queries. Proc. International Conference on Databases and Knowledge Bases, Jerusalem Israel, 1988.
• Kl88: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• KP88: Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.231-239, March 1988, Austin, Texas, United States [doi>10.1145/308386.308446]
• K80: D. Kozen. Complexity of Boolean Algebras. Theo. Comp. Sci., 10, 221- 247, 1980.
• KY86: D. Kozen, C. Yap. Algebraic Cell Decomposition in N C. Proc. 26th IEEE FOCS, 515-521, 1985.
• Le87: William Leler, Constraint programming languages: their specification and generation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• L84: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• MN88: Ursul Martin , Tobias Nipkow, Unification in Boolean rings, Journal of Automated Reasoning, v.4 n.4, p.381-396, Dec. 1988 [doi>10.1007/BF00297246]
• PS85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• R83: H.L. Royden. Real Analysis. 2nd Ed., 1983.
• R88: R. Ramakrishnan. Magic Templates: A Spellbinding Approach to Logic Programs. Proc. 5th International Conference on Logic Programming, 141-159, 1988.
• S80: Guy L. Steele, Jr., The Definition and Implementation of a Computer Programming Language Based on Constraints, Massachusetts Institute of Technology, Cambridge, MA, 1980
• T51: A. Tarski. A Decision Method /or Elementary Algebra and Geometry. University of California Press, Berkeley, California, 1951.
• U82: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• UvG88: J.D. Ullman, A. Van Gelder. Parallel Complexity of Logical Query Programs. Algorithmica, 3:5-42, 1988.
• V82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Design, Languages, Management, Performance, Theory