Toward Practical Constraint Databases.

Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
  author    = {Alexander Brodsky and
               Joxan Jaffar and
               Michael J. Maher},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {Toward Practical Constraint Databases},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {567-580},
  ee        = {db/conf/vldb/BrodskyJM93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP,}


Linear constraint databases (LCDBs) extend relational databases to include linear arithmetic constraints in both relations and queries. A LCDB can alsobe viewed as a powerful extension of linear programming (LP) where the system of constraints is generalized to a database containing constraints and the objective function is generalized to a relational query containing constraints. Our major concern is query optimization in LCDBs. Traditional database approaches are not adequate for combination with LP technology. Instead, we propose a new query optimization approach, based on statistical estimations and iterated trials of potentially better evaluation plans. The resulting algorithms are not onlyeffective on LCDBs, but also on existing query languages.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Rakesh Agrawal, Seán Baker, David A. Bell (Eds.): 19th International Conference on Very Large Data Bases, August 24-27, 1993, Dublin, Ireland, Proceedings. Morgan Kaufmann 1993, ISBN 1-55860-152-X
Contents BibTeX


Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
Alexander Brodsky, Catherine Lassez: Separability of Polyhedra and a New Approach to Spatial Storage (Extended Abstract). PPCP 1993: 7-11 BibTeX
Alexander Brodsky, Yehoshua Sagiv: Inference of Monotonicity Constraints in Datalog Programs. PODS 1989: 190-199 BibTeX
Jan Chomicki, Tomasz Imielinski: Relational Specifications of Infinite Query Answers. SIGMOD Conference 1989: 174-183 BibTeX
Upen S. Chakravarthy, Jack Minker: Multiple Query Processing in Deductive Databases using Query Graphs. VLDB 1986: 384-391 BibTeX
Donald D. Chamberlin, Morton M. Astrahan, W. Frank King III, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Mario Schkolnick, Patricia G. Selinger, Donald R. Slutz, Bradford W. Wade, Robert A. Yost: Support for Repetitive Transactions and Ad Hoc Queries in System R. ACM Trans. Database Syst. 6(1): 70-94(1981) BibTeX
Dean Daniels, Patricia G. Selinger, Laura M. Haas, Bruce G. Lindsay, C. Mohan, Adrian Walker, Paul F. Wilms: An Introduction to Distributed Query Compilation in R*. DDB 1982: 291-309 BibTeX
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Patrick A. V. Hall: Optimization of a Single Relation Expression in a Relational Data Base System. IBM J. Res. Dev. 20(3): 244-257(1976) BibTeX
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
Joxan Jaffar, Spiro Michaylov, Peter J. Stuckey, Roland H. C. Yap: The CLP(R) Language and System. ACM Trans. Program. Lang. Syst. 14(3): 339-395(1992) BibTeX
Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX
Joxan Jaffar, Michael J. Maher, Peter J. Stuckey, Roland H. C. Yap: Output in CLP. FGCS 1992: 987-995 BibTeX
Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX
David B. Kemp, Kotagiri Ramamohanarao, Isaac Balbin, Krishnamurthy Meenakshi: Propagating Constraints in Recusive Deduction Databases. NACLP 1989: 981-998 BibTeX
Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243 BibTeX
Jean-Louis Lassez: Querying Constraints. PODS 1990: 288-298 BibTeX
Jean-Louis Lassez, Tien Huynh, Ken McAloon: Simplification and Elimination of Redundant Linear Arithmetic Constraints. NACLP 1989: 37-51 BibTeX
Jean-Louis Lassez, Ken McAloon: A Canonical Form for Generalized Linear Constraints. J. Symb. Comput. 13(1): 1-24(1992) BibTeX
Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46 BibTeX
Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80 BibTeX
Michael J. Maher: A Transformation System for Deductive Database Modules with Perfect Model Semantics. FSTTCS 1989: 89-98 BibTeX
Edward M. McCreight: Priority Search Trees. SIAM J. Comput. 14(2): 257-276(1985) BibTeX
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95 BibTeX
Jack Minker: Search Strategy and Selection Function for an Inferential Relational System. ACM Trans. Database Syst. 3(1): 1-31(1978) BibTeX
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. PODS 1990: 314-330 BibTeX
Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49 BibTeX
Franco P. Preparata, Michael Ian Shamos: Computational Geometry - An Introduction. Springer 1985, ISBN 3-540-96131-3
Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach To Logic Programs. J. Log. Program. 11(3&4): 189-216(1991) BibTeX
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
Divesh Srivastava, Raghu Ramakrishnan: Pushing Constraint Selections. PODS 1992: 301-315 BibTeX
Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990) BibTeX
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX

Referenced by

  1. Hongjun Zhu, Jianwen Su, Oscar H. Ibarra: An Index Structure for Spatial Joins in Linear Constraint Databases. ICDE 1999: 636-643
  2. Elisa Bertino, Barbara Catania, Boris Chidlovskii: Indexing Constraint Databases by Using a Dual Representation. ICDE 1999: 618-627
  3. Peter Z. Revesz: Safe Query Languages for Constraint Databases. ACM Trans. Database Syst. 23(1): 58-99(1998)
  4. Alberto Belussi, Elisa Bertino, Barbara Catania: An Extended Algebra for Constraint Databases. IEEE Trans. Knowl. Data Eng. 10(5): 686-705(1998)
  5. Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48
  6. Hagit Shatkay, Stanley B. Zdonik: Approximate Queries and Representations for Large Data Sequences. ICDE 1996: 536-545
  7. Alexander Brodsky, Yoram Kornatzky: The LyriC Language: Querying Constraint Objects. SIGMOD Conference 1995: 35-46
  8. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  9. Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77
  10. Jan Chomicki, Gabriel M. Kuper: Measuring Infinite Relations. PODS 1995: 78-85
  11. 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
  12. Peter Z. Revesz: Datalog Queries of Set Constraint Databases. ICDT 1995: 425-438
  13. Marianne Baudinet, Jan Chomicki, Pierre Wolper: Constraint-Generating Dependencies. ICDT 1995: 322-337
  14. Stéphane Grumbach, Zoé Lacroix: Computing Queries on Linear Constraint Databases. DBPL 1995: 11
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:57 2009