Let us consider ordered domains only and the language of
first-order formulas as the query
language.
Roughly speaking, a query is locally generic if it is preserved by
any order local monomorphism from a finite subset
X
of
U
into
U
for any finite state
s
over
X.
More formally, a
k-ary query
Q
is said to be
locally generic over finite states
if
a
is in
Q(s)
iff
F( a) is in
Q(F(s)),
for any subset
X of
U,
for any partial
<-isomorphism
F from X to
U,
for any finite state
s
over
X, and for any
k-tuple
a in
X.
The problem we are interested in the paper is:
does the general knowledge improve the expressive power of the locally
generic queries over finite states?
Usually the theorem that the answer is negative for a universe is
called
the collapse result
or
the collapse theorem
for the universe.
The collapse result holds for
( N, <, +).
The universe
is called the Presburger's arithmetics. Then, how much higher
than
+ in
( N, <)
can we go? Obviously,
+, *
make locally generic extended queries impossible to express as
pure order ones because, for example, the query "the cardinality
of
P is even" is locally generic and expressible in the first-order
extended language but not in the restricted one. But the
first-order theory of the arithmetics is undecidable, and the
language is bad (is not relevant) for querying.
Previous page
Next page