Toward Practical Constraint Databases.
Alexander Brodsky, Joxan Jaffar, Michael J. Maher:
Toward Practical Constraint Databases.
VLDB 1993: 567-580@inproceedings{DBLP:conf/vldb/BrodskyJM93,
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, http://dblp.uni-trier.de}
}
Abstract
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
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
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
References
- [1]
- 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)
![bibliographical record in XML](../../xml.gif)
- [2]
- Philip A. Bernstein, Nathan Goodman:
Power of Natural Semijoins.
SIAM J. Comput. 10(4): 751-771(1981)
![bibliographical record in XML](../../xml.gif)
- [3]
- Alexander Brodsky, Catherine Lassez:
Separability of Polyhedra and a New Approach to Spatial Storage (Extended Abstract).
PPCP 1993: 7-11
![bibliographical record in XML](../../xml.gif)
- [4]
- Alexander Brodsky, Yehoshua Sagiv:
Inference of Monotonicity Constraints in Datalog Programs.
PODS 1989: 190-199
![bibliographical record in XML](../../xml.gif)
- [5]
- Jan Chomicki, Tomasz Imielinski:
Relational Specifications of Infinite Query Answers.
SIGMOD Conference 1989: 174-183
![bibliographical record in XML](../../xml.gif)
- [6]
- Upen S. Chakravarthy, Jack Minker:
Multiple Query Processing in Deductive Databases using Query Graphs.
VLDB 1986: 384-391
![bibliographical record in XML](../../xml.gif)
- [7]
- 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)
![bibliographical record in XML](../../xml.gif)
- [8]
- 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
![bibliographical record in XML](../../xml.gif)
- [9]
- ...
- [10]
- 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
![bibliographical record in XML](../../xml.gif)
- [11]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57
![bibliographical record in XML](../../xml.gif)
- [12]
- 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)
![bibliographical record in XML](../../xml.gif)
- [13]
- 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)
![bibliographical record in XML](../../xml.gif)
- [14]
- 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)
![bibliographical record in XML](../../xml.gif)
- [15]
- Joxan Jaffar, Jean-Louis Lassez:
Constraint Logic Programming.
POPL 1987: 111-119
![bibliographical record in XML](../../xml.gif)
- [16]
- Joxan Jaffar, Michael J. Maher, Peter J. Stuckey, Roland H. C. Yap:
Output in CLP.
FGCS 1992: 987-995
![bibliographical record in XML](../../xml.gif)
- [17]
- Anthony C. Klug:
On conjunctive queries containing inequalities.
J. ACM 35(1): 146-160(1988)
![bibliographical record in XML](../../xml.gif)
- [18]
- Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz:
Constraint Query Languages.
PODS 1990: 299-313
![bibliographical record in XML](../../xml.gif)
- [19]
- ...
- [20]
- David B. Kemp, Kotagiri Ramamohanarao, Isaac Balbin, Krishnamurthy Meenakshi:
Propagating Constraints in Recusive Deduction Databases.
NACLP 1989: 981-998
![bibliographical record in XML](../../xml.gif)
- [21]
- Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter:
Indexing for Data Models with Constraints and Classes.
PODS 1993: 233-243
![bibliographical record in XML](../../xml.gif)
- [22]
- Jean-Louis Lassez:
Querying Constraints.
PODS 1990: 288-298
![bibliographical record in XML](../../xml.gif)
- [23]
- Jean-Louis Lassez, Tien Huynh, Ken McAloon:
Simplification and Elimination of Redundant Linear Arithmetic Constraints.
NACLP 1989: 37-51
![bibliographical record in XML](../../xml.gif)
- [24]
- Jean-Louis Lassez, Ken McAloon:
A Canonical Form for Generalized Linear Constraints.
J. Symb. Comput. 13(1): 1-24(1992)
![bibliographical record in XML](../../xml.gif)
- [25]
- Richard J. Lipton, Jeffrey F. Naughton:
Query Size Estimation by Adaptive Sampling.
PODS 1990: 40-46
![bibliographical record in XML](../../xml.gif)
- [26]
- Alon Y. Levy, Yehoshua Sagiv:
Constraints and Redundancy in Datalog.
PODS 1992: 67-80
![bibliographical record in XML](../../xml.gif)
- [27]
- Michael J. Maher:
A Transformation System for Deductive Database Modules with Perfect Model Semantics.
FSTTCS 1989: 89-98
![bibliographical record in XML](../../xml.gif)
- [28]
- Edward M. McCreight:
Priority Search Trees.
SIAM J. Comput. 14(2): 257-276(1985)
![bibliographical record in XML](../../xml.gif)
- [29]
- Lothar F. Mackert, Guy M. Lohman:
R* Optimizer Validation and Performance Evaluation for Local Queries.
SIGMOD Conference 1986: 84-95
![bibliographical record in XML](../../xml.gif)
- [30]
- Jack Minker:
Search Strategy and Selection Function for an Inferential Relational System.
ACM Trans. Database Syst. 3(1): 1-31(1978)
![bibliographical record in XML](../../xml.gif)
- [31]
- Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan:
Magic Conditions.
PODS 1990: 314-330
![bibliographical record in XML](../../xml.gif)
- [32]
- ...
- [33]
- Robert M. Pecherer:
Efficient Evaluation of Expressions in a Relational Algebra.
ACM Pacific 1975: 44-49
![bibliographical record in XML](../../xml.gif)
- [34]
- Franco P. Preparata, Michael Ian Shamos:
Computational Geometry - An Introduction.
Springer 1985, ISBN 3-540-96131-3
![bibliographical record in XML](../../xml.gif)
- [35]
- Raghu Ramakrishnan:
Magic Templates: A Spellbinding Approach To Logic Programs.
J. Log. Program. 11(3&4): 189-216(1991)
![bibliographical record in XML](../../xml.gif)
- [36]
- Nick Roussopoulos, Daniel Leifker:
Direct Spatial Search on Pictorial Databases Using Packed R-Trees.
SIGMOD Conference 1985: 17-31
![bibliographical record in XML](../../xml.gif)
- [37]
- ...
- [38]
- John Miles Smith, Philip Yen-Tang Chang:
Optimizing the Performance of a Relational Algebra Database Interface.
Commun. ACM 18(10): 568-579(1975)
![bibliographical record in XML](../../xml.gif)
- [39]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518
![bibliographical record in XML](../../xml.gif)
- [40]
- ...
- [41]
- Divesh Srivastava, Raghu Ramakrishnan:
Pushing Constraint Selections.
PODS 1992: 301-315
![bibliographical record in XML](../../xml.gif)
- [42]
- 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)
![bibliographical record in XML](../../xml.gif)
- [43]
- Eugene Wong, Karel Youssefi:
Decomposition - A Strategy for Query Processing.
ACM Trans. Database Syst. 1(3): 223-241(1976)
![bibliographical record in XML](../../xml.gif)
- [44]
- Mihalis Yannakakis:
Algorithms for Acyclic Database Schemes.
VLDB 1981: 82-94
![bibliographical record in XML](../../xml.gif)
Copyright © Tue Mar 16 02:22:03 2010
by Michael Ley (ley@uni-trier.de)