## DIMACS TR: 95-56

## Relational expressive power of local generic queries

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

**
ABSTRACT
**

Consider a scheme of databases Q and two signatures:
L_0={<}, L={<, Omega},
where Omega is a finite relational signature.
FO is the first-order language.
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