DIMACS TR: 96-01

On Order-Generic Queries

Authors: Oleg V. Belegradek, Alexei P. Stolboushkin, and Michael A. Taitslin


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. In fact, we consider two formalizations of this notion: ``generic'', and ``locally generic'', queries. For several domains order-generic queries fail to express more than pure order queries, for example, every order-generic query over rational numbers with $+$ can be rewritten without $+$. Our goal is to find general conditions on the domain that allow for such a simplification of order-generic queries.

An important difference of this paper from a recent series of related papers (see, for example,~\cite{PBG95,BDLW95}) 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 finitely-representable states, and thus all the results in this paper are proved for the general case of {\em constraint databases.}

On the simplification of order-generic queries, we offer two types of results. The results of the first type address {\em equivalence\/} of order-generic queries that use the additional predicates (extended queries) to pure order queries. Here we establish the necessary and sufficient condition for an extended query to be equivalent to a pure order query, in terms of behavior of this extended query over the ultra-product of this domain by a non-principal ultra-filter over $\omega$. This characterization relies upon the Continuum Hypothesis, and is used as instrumental in establishing equivalence of generic, as well as locally generic, extended queries to pure order queries for several classes of domains, including in particular the so-called $o$-minimal domains, integers with $+$, and such. Although, by Shoenfield's Absoluteness Theorem, the Continuum Hypothesis can be eliminated from these latter results, the fact remains, no translation algorithm can be extracted from arguments of this type.

That is why we also offer {\em effective algorithms\/} of translating extended to pure order queries for divisible ordered Abelian groups. Such groups---including real or rational numbers with $+$---are all $o$-minimal.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-01.ps.gz

DIMACS Home Page