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