FO in {L_0,Q} is called restricted. FO in {L,Q} is called extended. Consider a countable universe U in L.
Let V be a saturated elementary extension of U in power aleph_1. There is the only such V up to elementary isomorphisms over U.
Th.1. An extended query Phi is equal for all the finite database states over U to a restricted query iff Phi is generic for all the pseudo-finite database states over V.
Th.2. If U is o-minimal, every locally generic for all the finite database states over U extended query is generic for all the pseudo-finite database states over V.
Divisible ordered Abelian groups are o-minimal structures. So, for example, groups of rational and real numbers are o-minimal structures. But the additive group of the integer numbers and the additive semigroup of the natural numbers are not.
Th.3. If U is the additive group of the integer numbers or is the additive semigroup of the natural numbers, every locally generic for all the finite database states over U extended query is generic for all the pseudo-finite database states over V.
We propose a notion of local genericity for extended queries
over finitely representable order database states.
We show that every finitely representable order database state can be
represented by a finite state (of another scheme) such that these two
states are uniformly FO-translatable to one another. Using this
result, we show that, for any divisible ordered Abelian group,
the additive group of the integer numbers,
the additive semigroup of the natural numbers, and
any o-minimal structure, every locally generic
extended query over finitely
representable order database states can be translated into
a restricted query. Over all rational
database states, however, these two query languages differ.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-56.ps.gz
DIMACS Home Page