Relational expressive power of local generic queries
Oleg Belegradek, Alexei P. Stolboushkin, Michael A. Taitslin · 1995
Consider a scheme of databases Q and two signatures: L 0 = f!g, L = f!g[ where\\Omega is a finite relational signature. For a database scheme SC = fR 1 ; : : : ; R n g, denote L + 0 = L 0 [SC and L + = L [ SC. FO is the first-order language. FO in L + 0 is called restricted. FO in L + is called extended. Consider a countable universe U in L. Assume CH. It is possible to reconstruct the proofs of corollaries into ones not using CH. Let V be a saturated elementary extension of U in power @ 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 rati...