|
|
|
@inproceedings{DBLP:conf/pods/StolboushkinT96,
author = {Alexei P. Stolboushkin and
Michael A. Taitslin},
title = {Linear vs. Order Contstrained Queries Over Rational 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 = {17-27},
ee = {http://doi.acm.org/10.1145/237661.237669, db/conf/pods/StolboushkinT96.html},
crossref = {DBLP:conf/pods/96},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
We consider relational databases organized over an ordered domain with some additional relations - a typical example is the ordered domain of rational numbers together with the ternary relation + of addition. In the focus of our study are the first order queries that are invariant under order-preserving "permutations" - such queries are called (order-)generic.
We show that for an arbitrary ordered Abelian group order-generic queries fail to express more than pure order queries, and that, moreover, the generic queries can be effectively translated into pure order queries. For example, every order-generic query over rational numbers with + can be effectively rewritten without +.
An important difference of this paper from a recent series of related papers (see, for example [PVV95, BDLW96]) is that we generalize all notions to the case of finitely representable database states - as opposed to finite states - and develop a general lifting technique that, essentially, allows us to extend any result of the kind we are interested in, from finite to finite-representable states, and thus all the results in this paper are proved for the general case of constraint databases.
This lifting technique relies upon a geometrically clear representation of finitely representable (but possible infinite) relations over an arbitrary ordered domain in the form of finite relations. The translation of one representation into another is shown to be uniform first order. The value of these results is not limited to the specific set of problems considered in this paper, as a matter of fact, they show that order-constraint and finite databases are equally powerful - although the constraint representation does provide a more intuitive user interface.
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.