Towards Practical Constraint Databases.
Stéphane Grumbach, Jianwen Su:
Towards Practical Constraint Databases.
PODS 1996: 28-39@inproceedings{DBLP:conf/pods/GrumbachS96,
author = {St{\'e}phane Grumbach and
Jianwen Su},
editor = {Richard Hull},
title = {Towards Practical Constraint Databases},
booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 3-5, 1996, Montreal,
Canada},
publisher = {ACM Press},
year = {1996},
isbn = {0-89791-781-2},
pages = {28-39},
ee = {http://doi.acm.org/10.1145/237661.237672, db/conf/pods/GrumbachS96.html},
crossref = {DBLP:conf/pods/96},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
We develop a framework for (real) constraint databases based on finite
precision arithmetic which fulfills the main requirements of practical
constraint databases. First, it allows the manipulation of approximate
values, standard in scientific applications. More importantly, it permits
the extension of the relational calculus with aggregate functions, while
preserving the fundamental property of closed evaluation with PTIME data
complexity. This is an important step since the initial model of
[KKR90] cannot be extended to aggregate
functions. Moreover, finite precision computation plays a central role in
efficient query processing. We introduce the finite precision semantics of
queries and prove expressive power results concerning it. We then present
a new constraint query language, CACLF, which includes
aggregate and analytical functions, and show that it admits a closed
form evaluation in PTIME.
Copyright © 1996 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.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
Printed Edition
Richard Hull (Ed.):
Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, 1996, Montreal, Canada.
ACM Press 1996, ISBN 0-89791-781-2
Contents 
[Index Terms]
[Full Text in PDF Format, 1320 KB]
References
- [ACGK94]
- Foto N. Afrati, Stavros S. Cosmadakis, Stéphane Grumbach, Gabriel M. Kuper:
Linear vs Polynomial Constraints in Database Query Languages.
PPCP 1994: 181-192
- [ACM88]
- Dennis S. Arnon, George E. Collins, Scott McCallum:
Cylindrical Algebraic Decomposition I: The Basic Algorithm.
SIAM J. Comput. 13(4): 865-877(1984)
- [Arn88]
- Dennis S. Arnon:
A Bibliography of Quantifier Elimination for Real Closed Fields.
J. Symb. Comput. 5(1/2): 267-274(1988)
- [BDLW95]
- ...
- [BF85]
- ...
- [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)
- [CK73]
- ...
- [CK95]
- Jan Chomicki, Gabriel M. Kuper:
Measuring Infinite Relations.
PODS 1995: 78-85
- [CL82]
- ...
- [Col75]
- ...
- [Dr82]
- ...
- [FK94]
- Christos Faloutsos, Ibrahim Kamel:
Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension.
PODS 1994: 4-13
- [GS94]
- Stéphane Grumbach, Jianwen Su:
Finitely Representable Databases.
PODS 1994: 289-300
- [GS95a]
- Stéphane Grumbach, Jianwen Su:
Dense-Order Constraint Databases.
PODS 1995: 66-77
- [GS95b]
- Stéphane Grumbach, Jianwen Su:
First-order Definability over Constraint Databases.
CP 1995: 121-136
- [GST94]
- Stéphane Grumbach, Jianwen Su, Christophe Tollu:
Linear Constraint Query Languages: Expressive Power and Complexity.
LCC 1994: 426-446
- [GV88]
- Dima Grigoriev, Nicolai Vorobjov:
Solving Systems of Polynomial Inequalities in Subexponential Time.
J. Symb. Comput. 5(1/2): 37-64(1988)
- [KG94]
- ...
- [KKR90]
- Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz:
Constraint Query Languages.
PODS 1990: 299-313
- [Knu69]
- Donald E. Knuth:
The Art of Computer Programming, Volume II: Seminumerical Algorithms.
Addison-Wesley 1969
- [KRVV93]
- Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter:
Indexing for Data Models with Constraints and Classes.
PODS 1993: 233-243
- [Kup93]
- Gabriel M. Kuper:
Aggregation in Constraint Databases.
PPCP 1993: 166-173
- [Moo66]
- ...
- [Nef90]
- C. Andrew Neff:
Specified Precision Polynomial Root Isolation is in NC.
FOCS 1990: 152-162
- [Pan92]
- ...
- [PVV94]
- Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht:
Towards a Theory of Spatial Database Queries.
PODS 1994: 279-288
- [PVV95]
- Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht:
First-order Queries on Finite Structures over the Reals.
LICS 1995: 79-87
- [PTVF92]
- William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery:
Numerical Recipes in C, 2nd Edition.
Cambridge University Press 1992
Contents - [Ren92a-1]
- James Renegar:
On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals.
J. Symb. Comput. 13(3): 255-300(1992)
- [Ren92a-2]
- James Renegar:
On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part II: The General Decision Problem. Preliminaries for Quantifier Elimination.
J. Symb. Comput. 13(3): 301-328(1992)
- [Ren92a-3]
- James Renegar:
On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part III: Quantifier Elimination.
J. Symb. Comput. 13(3): 329-352(1992)
- [Ren92b]
- James Renegar:
On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae.
SIAM J. Comput. 21(6): 1008-1025(1992)
- [SA94]
- ...
- [Tar51]
- ...
- [Wei85]
- ...
- [Yap94]
- ...
Last update Thu May 24 04:40:31 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
