 |
|
Full Paper (PDF)
We extend some of the classical characterization theorems of the relational theory - particularly 44ose related to query safety - to the context where database elements come with fixed interpreted structure, and where formulae over elements of that structure can be used in queries. We show that the addition of common interpreted functions such as real addition and multiplication to the relational calculus preserves important characterization theorems of the relational calculus, and also preserves certain combinatorial properties of queries. Our main result of the first kind is that there is a syntactic characterization of the collection of safe queries over the relational calculus supplemented by a wide class of interpreted functions - a class that includes addition, multiplication, and exponentiation - and that this characterization gives us an interpreted analog of the concept of range-restricted query from the uninterpreted setting. Furthermore, our range-restricted queries are particularly intuitive for the relational calculus with real arithmetic, and give a natural syntax for safe queries in the presence of polynomial functions. We use these characterizations to show that safety is decidable for Boolean combinations of conjunctive queries for a large class of interpreted structures. We show a dichotomy theorem that sets a polynomial bound on the growth of the output of a query that might refer to addition, multiplication and exponentiation.
We apply the above results for finite databases to get results on finitely representable databases. We obtain syntactic characterizations of the queries on finitely representable databases that preserve certain geometric conditions, such as being convex polytopes, polyhedra, and compact semi-linear sets. The latter corresponds to many spatial applications. We show how to give an effective syntax to safe queries, and prove decidability of preservation properties for conjunctive queries. |
References, where available, link to the DBLP on the World Wide Web.
[1]Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents[2]...
[3]Arnon Avron, Yoram Hirshfeld:
On First Order Database Query Languages.
LICS 1991: 226-231[4]Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong:
Relational Expressive Power of Constraint Query Languages.
PODS 1996: 5-16[5]Michael Benedikt, Leonid Libkin:
Languages for Relational Databases over Interpreted Structures.
PODS 1997: 87-98[6]...
[7]...
[8]...
[9]Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht:
On the Decidability of Semi-Linearity of Semi-Algebraic Sets and Its Implications for Spatial Databases.
PODS 1997: 68-77[10]Martha Escobar-Molano, Richard Hull, Dean Jacobs:
Safety and Translation of Calculus Queries with Scalar Functions.
PODS 1993: 253-264[11]Stéphane Grumbach, Jianwen Su:
Finitely Representable Databases.
JCSS 55(2): 273-298(1997)[12]Stéphane Grumbach, Jianwen Su, Christophe Tollu:
Linear Constraint Query Languages: Expressive Power and Complexity.
LCC 1994: 426-446[13]Richard Hull, Jianwen Su:
Domain Independence and the Relational Calculus.
Acta Informatica 31(6): 513-524(1994)[14]Oscar H. Ibarra, Jianwen Su:
On the Containment and Equivalence of Database Queries with Linear Constraints.
PODS 1997: 32-43[15]Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz:
Constraint Query Languages.
PODS 1990: 299-313[16]Michael Kifer:
On Safety, Domain Independence, and Capturability of Database Queries (Preliminary Report).
JCDKB 1988: 405-415[17]Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz:
An Axiomatic Approach to Deciding Query Safety in Deductive Databases.
PODS 1988: 52-60[18]...
[19]...
[20]Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht:
Towards a Theory of Spatial Database Queries.
PODS 1994: 279-288[21]Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht:
First-order Queries on Finite Structures over the Reals.
LICS 1995: 79-87[22]...
[23]Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz:
Safety of Recursive Horn Clauses With Infinite Relations.
PODS 1987: 328-339[24]...
[25]...
[26]...
[27]Yehoshua Sagiv, Mihalis Yannakakis:
Equivalences Among Relational Expressions with the Union and Difference Operators.
JACM 27(4): 633-655(1980)[28]Alexei P. Stolboushkin, Michael A. Taitslin:
Finite Queries do not Have Effective Syntax.
PODS 1995: 277-285[29]Alexei P. Stolboushkin, Michael A. Taitslin:
Linear vs. Order Contstrained Queries Over Rational Databases.
PODS 1996: 17-27[30]...
[31]...
[32]Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht:
On Query Languages for Linear Queries Definable with Polynomial Constraints.
CP 1996: 468-481[33]Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht:
An Expressive Language for Linear Spatial Database Queries.
PODS 1998: 109-118[34]Moshe Y. Vardi:
The Decision Problem for Database Dependencies.
Information Processing Letters 12(5): 251-254(1981)[35]...
Referenced By:
- Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht:
An Expressive Language for Linear Spatial Database Queries.
PODS 1998: 109-118
|
@inproceedings{DBLP:conf/pods/BenediktL98,
author = {Michael Benedikt and
Leonid Libkin},
title = {Safe Constraint Queries},
booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-966-3},
pages = {99-108},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
