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