Definition 5

Let M be an L-structure. An L-formula φ(x,y) is called an independent formula in M iff the following property holds:

for each natural n there are a1,…,an in M such that for any subset σ of
{ a1,…,an } there is bσ in M such that { ai | φ(ai, bσ)} is σ.

M lucks the independence property iff there is no independent formula in M.


Theorem 8 ([1], Theorem 5.2)

Let M be a model of T and an infinite set I with order type a complete dense linear order be an indiscernible sequence in M. If M has no independent formula then (M,I) is P-reducible.

Corollary 9 ([1])

If U lacks the independence property then for any extended query φ which is locally generic for finite database states over U, there is a restricted query ψ which is equivalent to φ over finite database states over U.

Previous page
Next page