First-Order Queries on Finite Structures Over the Reals.
We investigate properties of finite relational structures over the reals expressed by first-order sentences whose predicates are the relations of the structure plus arbitrary polynomial inequalities, and whose quantifiers can range over the whole set of reals.  In constraint programming terminology, this corresponds to Boolean real polynomial constraint queries on finite structures.  The fact that quantifiers range over all reals seems crucial; however, we observe that each sentence in the first-order theory of the reals can be evaluated by letting each quantifier range over only a finite set of real numbers without changing its truth value. Inspired by this observation, we then show that when all polynomials used are linear, each query can be expressed uniformly on all finite structures by a sentence of which the quantifiers range only over the finite domain of the structure. In other words, linear constraint programming on finite structures can be reduced to ordinary query evaluation as usual in finite model theory and databases. Moreover, if only "generic" queries are taken into consideration, we show that this can be reduced even further by proving that such queries can be expressed by sentences using as polynomial inequalities only those of the simple form x < y.
Introduction
In this paper we are motivated by two fields of
computer science which heavily rely on logic: relational
databases and constraint programming.
We will look at the latter from the perspective of
the former.
In classical relational database theory [1], a database
is modeled as a relational structure. The
domain of this structure is some fixed universe U
of possible data elements (such as all strings, or
all natural numbers), and is typically infinite. The
relations of the structure, in contrast, are always
finite as they model finite tables holding data. As
a consequence, the active domain of the database,
consisting of all data elements actually occurring
in one or more of the relations, is finite as well.
A (Boolean) query is a mapping from databases
(over some fixed relational signature) to true
or false. A basic way of expressing a query is
by a first-order sentence over the relational sig-
nature. For example, on a database containing
information on children and hobbies, the
query "does each parent have at least all hobbies
his children have?" is expressed by the sentence
(8p)(8c)(8h)(Child (p; c) - Hobby(c;
Since the domain of each database is U, the
quantifiers in a sentence expressing a query will
naturally range over the whole infinite U. It is
thus not entirely obvious that under this natural
interpretation the query will always be effectively
computable. That first-order queries are indeed
computable follows immediately from a result by
Aylamazyan, Gilula, Stolboushkin, and Schwartz
[4] (for simplicity hereafter referred to as "the four
Russians"). They showed that in order to obtain
the result of the query it suffices to let the quantifiers
range over the active domain augmented with
a finite set of q additional data elements, where
q is the number of quantified variables in the formula
expressing the query. The intuition behind
this result is that all data elements outside the
active domain of a given database are alike with
respect to that database.
Alternatively, we can choose to let the quantifiers
range over the active domain only, thus obtaining
a semantics which is quite different from
the natural interpretation. For example, consider
databases over the single unary relation symbol
. Then the sentence (8x)P (x) will always be
false under the natural interpretation, while under
the active-domain interpretation it will always be
true. In fact, it is not obvious that each query expressible
under the natural interpretation is also
expressible under the active-domain interpreta-
tion. Hull and Su [11] established that the implication
indeed holds. (The converse implication
holds as well, since the active-domain interpretation
can easily be simulated under the natural
interpretation using bounded quantification.)
In recent years, much attention has been paid
to "constraint programming languages" (e.g., [5]).
In particular, in 1990, Kanellakis, Kuper and
Revesz demonstrated that the idea of constraint
programming also applies to database query languages
by introducing the framework of "con-
straint query languages" [12]. An important instance
of this framework is that of real polynomial
constraints. Here, the universe U of data
elements is the field R of real numbers. Data-bases
then are relational structures over R, but
the database relations need no longer be finite; it
suffices that they are definable as finite Boolean
combinations of polynomial inequalities. In other
words, each k-ary relation of the structure must
be a semi-algebraic subset of R k [6].
A basic way of querying real polynomial constraint
databases is again by first-order sentences,
which can now contain polynomial inequalities in
addition to the predicate symbols of the relational
signature. For example, if the database holds a
set S of points in R 2 , the query "do all points
in S lie on a common circle?" is expressed by
that quantifiers are naturally interpreted
as ranging over the whole of R. In order
to evaluate such a sentence on a database, we replace
each predicate symbol in the formula by the
polynomial definition of the corresponding data-base
relation, and obtain a sentence in the pure
first-order theory of the reals. As is well-known,
this theory is decidable [15]; the truth value of the
obtained sentence yields the result of the query.
So, real polynomial constraint queries are effectively
computable.
Finite relations are semi-algebraic, so that finite
relational databases over the reals form an important
special case of real polynomial constraint
databases. For example, if we want to model a database
holding a finite number of rectangles, we
can either choose to store the full extents of the
rectangles, resulting in the infinite set of all points
on the rectangles (represented in terms of linear
inequalities in the obvious way), or we can choose
to store only the corner points of each rectangle,
resulting in a finite relation.
In the present paper, we investigate whether
the results by the four Russians and by Hull and
Su, mentioned in the beginning of this Introduc-
tion, carry over from classical first-order queries
on relational databases to polynomial constraint
queries on finite databases over the reals. In-
deed, as in the classical case, one can give an
alternative active-domain semantics to constraint
sentences and again ask whether this is without
loss of expressive power. Note, however, that
active-domain quantification defies the very nature
of constraint programming as a means to
reason about intentionally defined, potentially in-
finite, ranges of values. Hence, it is not obvious
that the results just mentioned might carry over
at all.
Nonetheless, we have found a natural analog of
the four Russians theorem, and we have been able
to establish the verbatim analog of the Hull-Su
theorem in the case when only linear polynomials
are used. This is often the case in practice.
Our result might be paraphrased by saying that
on finite structures, first-order linear constraint
programming can be reduced to ordinary query
evaluation as usual in finite model theory and databases

Our development is based upon the following
observation. Consider a prenex normal form sentence
in the first-order
theory of the reals. For any finite set D 0 of
real numbers, there exists a sequence D 0 ' D 1 '
of finite sets of reals such that the sentence
can be evaluated by letting each quantifier
range over D i only (rather than over the whole
of R) without changing the sentence's truth value.
By taking D 0 to be the active domain of a given
finite database over the reals, we get the analog
in the real case of the four Russians theorem.
The reader familiar with Collins's method for
quantifier elimination in real-closed fields through
cylindrical algebraic decomposition (cad) [3, 8]
will not be surprised by the above observation. In-
deed, it follows more or less directly from an obvious
adaptation of the cad construction. However,
we give an alternative self-contained proof from
first principles which abstracts away the purely
algorithmical aspects of the cad construction and
focuses on the logic behind it. Importantly, this
proof provides us with a basis to show how in the
case of linear polynomials, the construction of the
sequence departing from the active
domain D 0 can be simulated using a linear
constraint formula. As a result, we obtain the
analog in the real case of the Hull-Su theorem.
In a final section of this paper, we look at
queries that are "generic," i.e., that do not distinguish
between isomorphic databases. Genericity
is a natural criterion in the context of classical
relational databases [2, 7]. Perhaps this is a little
less so for databases over the reals; in other
work [14] we have proposed alternative, "spatial"
genericity criterions based on geometrical intu-
itions. Nevertheless, it remains interesting to investigate
which classically generic queries can be
expressed using linear constraint sentences.
Sentences that do not contain any polynomial
inequalities always express generic queries, but
from the moment a sentence even contains only
simple inequalities of the form x ! y it can
already be non-generic. Furthermore, there is
an example due to Gurevich [1, Exercise 17.27],
showing a generic query expressible with such
simple inequalities but not without. In other
words, simple inequalities, though inherently non-generic
when viewed in isolation, help to express
more generic queries. The natural question now is
to ask whether general linear polynomial inequalities
help even more. We will answer this question
negatively, thus providing a partial rectification
of Kuper's original intuitions [13] (which are incorrect
as stated, by the Gurevich example just
mentioned).
Real formulas
Let R be the field of real numbers. A real formula
is a first-order formula built from atomic formulas
of the form p ? 0, with p a multivariate polynomial
with real coefficients, using logical connectives
and quantifiers in the obvious manner. If
are among x
is a tuple of real numbers, then the satisfaction
of \Phi on R with a i substituted for x i , denoted
R defined in the standard way. As
usual, a formula without free variables is called a
sentence.
Example 2.1 The formula \Phi(a; b; c) j (9x)
a, b and c. [A condition like easily
expressed in terms of conditions of the form p ? 0
by :(p ? 0)-:(\Gammap ? 0).] We have R
but R 6j= \Phi[5; 3; 1].
be a real formula in prenex
normal
with each Q i either 9 or 8 and M quantifier-free.
If D k+1 , . , D n are subsets of R, then we say
that \Phi[-a] is satisfied on (D
(D evaluates to true
when we let each quantifier Q i range over D i only
rather than over the whole of R.
Example 2.2 Let \Phi be the sentence
Our main result of this section can now be
stated as follows:
Theorem 2.3 Let \Phi(-x) be a prenex normal form
real formula as in ( be a finite
subset of R. Then there exists a sequence D k '
of finite subsets of R such that
for all tuples - a on D k , R only if
(D
Example 2.4 As a trivial illustration let
be the formula (9x 2 )x
We have R
we have (D 2 )
In the remainder of this section we give a simple
proof of Theorem 2.3. We will introduce various
auxiliary notions on which we will rely heavily in
later sections.
We first define the following natural equivalence
relation on R
Definition 2.5 Two points - a and - b in R n are
called equivalent (with respect to \Phi), denoted - a j
each polynomial occurring in \Phi has the same
sign (positive, zero, or negative) on - a and - b.
We now extend this equivalence relation inductively
to lower dimensions such that the equivalence
classes at each dimension are "cylindrical"
over the equivalence classes at the next lower dimension

Definition 2.6 Let i ! n and assume j is already
defined on R i+1 . Then for
have -
a for each ff there is a fi such that
conversely, for each fi there is
an ff such that ( - b; fi) j (-a; ff) (with ff and fi real
We note:
Lemma 2.7 For each i, j is of finite index on
R i .
Proof. By downward induction on i. The case
-a) the set of equivalence classes in R i+1 lying
"above" - a, i.e., intersecting the line f(-a; ff) j ff 2
Rg. Clearly, so that we
have an injection mapping each equivalence class
c on R i to the set f-a) j -
a 2 cg. Since j is
of finite index on R i+1 , - can have only a finite
number of possible values and hence j is of finite
index on R i as well.
The relevance of the equivalence relations just
defined is demonstrated by the following lemma.
We use the following
stands for the formula (Q i+1 x
M .
Lemma 2.8 Let k - i - n, and let - a and - b be
equivalent points in R i . Then R
only if R
This lemma can be proven by a straightforward
induction (omitted).
The notion of domain sequence, defined next, is
crucial. The technical lemma following the definition
will directly imply Theorem 2.3.
Definition 2.9 Let D k be a finite subset of R. A
sequence of finite subsets
of R is called a domain sequence with respect to \Phi
if for each k -
Since j is of finite index, we know that a domain
sequence always exists.
Lemma 2.10 Let (D k ; D
sequence w.r.t. \Phi, and let a
only if
(D
Proof. By downward induction on i. The case
n. Note that
We concentrate on the
case the case Q
lar. Denote (a a. For the implication
from left to right, assume R
Then there exists a i+1 2 R such that R
According to Definition 2.9, there
exists a 0
By Lemma 2.8, since R
also have R
(D
We can thus
conclude that (D [-a]. The implication
from right to left is straightforward.
Theorem 2.3 immediately follows from the case
of the above lemma. The reader may have
noticed that we have never relied on the fact that
in the polynomial inequalities p ? 0 occurring
in a real formula, p is really a polynomial. So,
the theorem holds for any first-order language of
real functions. This observation substantiates our
claim made in the Introduction that our proof
"abstracts away the purely algorithmical aspects
of Collins's cad construction and focuses on the
logic behind it". Of course, by departing from
the cad construction one gets an effectively computable
version of Theorem 2.3. We will give an
alternative construction for the linear case in Section
4.
3 Queries on real databases
Fix a relational signature oe consisting of a finite
number of relation symbols S with associated arity
ff(S). A real database B is a structure of type
oe with R as domain, assigning to each relation
in oe a finite relation S B of rank ff(S) on
R. The active domain of B, denoted by adom(B),
is the (finite) set of all real numbers appearing in
one or more relations in B.
A query is a mapping from databases of type oe
to true or false. A basic way of expressing queries
is by first-order formulas which look like real for-
mulas, with the important additional feature that
they can use predicates of the form S(p
where S is a relation symbol in oe of arity a, and
each p i is a polynomial. If \Phi(-x) is a query formula
and B is a database, then the satisfaction
defined in the standard way. In par-
ticular, if \Phi is a sentence, it expresses the query
yielding true on an input database B iff B
Example 3.1 Assume 2.
The query "do all points in S lie on a common
circle?" can be expressed as (9x 0 )(9y 0 )(9r)(8x)
query "is there a point in S whose coordinates are
greater than or equal to 1?" can be expressed as
1). Note that the quantifiers
in query formulas are naturally interpreted
as ranging over the whole of R.
If \Phi is a query sentence and B is a database,
then we can produce a real sentence \Phi B in a
very natural way as follows. Let
be an atomic subformula of \Phi, with S a relation
symbol in oe. We know that S B is a finite
relation consisting of, say, the m tuples
)g. Then replace
a ) in \Phi by
It is obvious that B only if R
Now assume the query sentence \Phi is in prenex
normal
If B is a database and D are subsets of R,
then we say that \Phi is satisfied on (B; D
evaluates to
true on B when we let each quantifier Q i range
over D i only, rather than over the whole of R.
Given the preceding discussion, the following
theorem follows readily from the material in the
previous section:
Theorem 3.2 Let \Phi be a query sentence as in
(y) and let B be a database. If adom(B) ' D 1 '
is a domain sequence with respect to \Phi B ,
This theorem is the analog in the real case of the
four Russians theorem [4] mentioned in the Introduction

4 The linear case
In this section, we focus on linear queries, expressed
by query sentences in which all occurring
polynomials are linear. We prove that each linear
query is expressible by a linear query sentence of
which the quantifiers range over the active domain
of the input database only. Thereto, we introduce
a particular way to construct domain sequences
on the active domain of a database, based
on Gaussian elimination. We then show that this
construction can be simulated in a uniform (i.e.,
database-independent) way by a linear query formula

Before embarking, we point out that the notion
of equivalence of points with respect to some given
real formula \Phi (Definitions 2.5 and 2.6) depends
only on the set of polynomials occurring in \Phi. So
we can also talk of equivalence with respect to
some given set of polynomials.
Now let \Pi be a set of linear polynomials on the
Such a polynomial p is of
the form c p
We define a sequence
linear polynomials inductively as
follows:
c q
In words, each \Pi i is a set of linear polynomials
obtained from \Pi i+1 by Gaussian
elimination.
Equivalence of points in R i with respect to \Pi
can be characterized in terms of the polynomials
in \Pi i as follows:
Proposition 4.1 Let 1 - i - n and let -
Then - a j - b with respect to \Pi if and only if each
polynomial in \Pi i has the same sign (positive, zero,
or negative) on -
a and - b.
Proof. (Sketch) By downward induction on i.
The case According
to Definition 2.6, - a j - b if for each ff there
is a fi such that (-a; ff) j ( - b; fi) (and conversely; for
simplicity we will ignore this part in the present
sketch). Equivalently, by induction, for each ff
there is a fi such that each polynomial in \Pi i+1
has the same sign on (-a; ff) and ( - b; fi). For sim-
plicity, we ignore in this sketch the polynomials
equivalently,
for each ff there is a fi such that for each p 2 \Pi i+1 ,
or ?. Now it can be seen that this is equivalent
to p(-a)=c p
for all By definition of \Pi i this is the
same as saying that each p 2 \Pi i has the same sign
on - a and - b.
Now let \Phi be a linear query sentence (Q 1
prenex normal form, and let B
be a database. Recall the definition of the real
described in the previous section; note
that since \Phi is linear, \Phi B is linear as well. Fix
\Pi to be the set of polynomials occurring in \Phi B ,
and consider the sequence \Pi defined just
above. We observe:
Lemma 4.2 Let 1 - i - n. Then \Pi i is a finite
union of sets of the form
Both the number of these sets and the coefficients
c i and d i for each set do not depend on the particular
database B.
Proof. Consider the case
consists of the polynomials occurring in \Phi B . The
elements of \Pi can be classified into two different
kinds: those that already occur in \Phi, and those
that are of the form e, with p a polynomial
occurring in \Phi and e 2 adom(B). In the latter
case, p\Gammae may be assumed to occur for all possible
we omit the argument that this
assumption is without loss of generality. Hence,
the lemma holds for n. The case i ! n now
follows easily by induction.
We are now in a position to define a particular
domain sequence with respect to \Phi B , based on the
sequence
Definition 4.3 The linear sequence on B with
respect to \Phi is the sequence D 0 '
inductively defined as follows: D 0 equals
adom(B), and for 1
where D 0
i is D
Proposition 4.4 The linear sequence on B with
respect to \Phi is a domain sequence with respect to
Proof. According to Definition 2.9, we must
show for each
Consider the definition of D i in terms of D 0
4.3 above. We distinguish
the following possibilities for ff:
1.
2. ff ?
3.
is the maximal element
in E i such that e 1 ! ff, and e 2 is the minimal
element such that ff ! e 2 .
It is obvious that ff 0 2 moreover, from the way
defined, it is clear that all polynomials in \Pi i
have the same sign on (-a; ff) and (-a; ff 0 ). Hence,
by Proposition 4.1, the proposition follows.
After one final lemma we will be able to state
and prove the main result of this section:
Lemma 4.5 For each 0 - i - n there exists
a finite set P of linear polynomials such that
for each database B, the i-th member D i of the
linear sequence on B with respect to \Phi equals
with z independent of B.
Proof. By induction on i. The case
is trivial since D
The definition of D i in
terms of D 0
i in Definition 4.3 is clearly of the
consists of the four polynomials
We have
clearly of the form
some P 00 , and by induction, D i\Gamma1 is of the form
for some P 000 . By combining these expressions
using a tedious but straightforward substitution
process, we obtain the desired form for D i .
Theorem 4.6 For each linear query sentence \Phi
there is a linear query sentence \Psi such that for
each database B, B
\Psi, where adom denotes that the quantifiers in \Psi
range over the active domain of the database only.
Proof. Let be the
linear sequence on B with respect to \Phi. By Theorem
3.2 and Proposition 4.4, we know that B
We can write the latter
explicitly as B
case
8 is similar). From Lemma 4.5 we know that
D 1 can be written as fp(y
Pg. So, equivalently, we have
where each (9y i ) ranges only over adom(B). By
replacing in a similar manner, we
obtain the desired sentence \Psi.
5 Generic queries
Two databases B and B 0 over the same relational
signature oe are called isomorphic if there is a
for each relation symbol S in oe. A
query which yields the same result on isomorphic
databases is called generic.
For example, assume that oe consists of a single
binary relation symbol S. Databases of type
oe can be viewed as finite directed graphs whose
nodes are real numbers. Of course, any query expressed
in the language L of pure first-order sentences
over oe (i.e., not containing any polynomial
inequalities) is generic. Other examples of generic
queries are "is the graph connected?" or "is the
number of edges even?".
In the language L ! consisting of those query
sentences where all inequalities are of the simple
queries can be easily expressed, such as
y. As pointed out in the
Introduction, however, there are generic queries
expressible in L ! but not in L. We have been
able to prove that there is no similar gain in expressiveness
when moving from L ! to full linear
query sentences:
Theorem 5.1 For each linear query sentence \Phi
expressing a generic query there is a query sentence
\Psi in L ! such that for each database B,
As in Theorem 4.6, adom denotes that quantifiers
range over the active domain only; we know
by Theorem 4.6 that this active-domain interpretation
is without loss of generality.
Proof. (Sketch) We first observe:
Lemma 5.2 Let p be a linear polynomial on the
There exists a real formula
involving only simple inequalities
of the form x disjunction, conjunction, and
negation, such that for each natural number s - 1,
1 As an aside, we would like the reader to note that it
is possible to specialize Theorem 4.6 to query sentences in
using a different construction of domain sequence.
each sufficiently large real number a ? 0, and
each tuple y on the set fa; a
true.
This lemma is proven by noting that the application
of the (multivariate) polynomial p to
can be viewed as the
application of another, univariate polynomial to
a. In particular, for a sufficiently large, the sign of
the latter application is determined by the sign of
the leading coefficient. The difficulty to be overcome
is that this univariate polynomial depends
on the particular y However, it can be
seen that it depends essentially only on the way
how the y are ordered. We omit the details

Using the genericity of \Phi, we can now exploit
the above lemma to prove the theorem as follows.
Define \Psi to be the query sentence obtained by
replacing each polynomial inequality p ? 0 occurring
in \Phi by the corresponding formula / p as provided
by the lemma. Now let B a database, and
let s be the size of adom(B). Let a ? 0 be sufficiently
large and let ae be an order-preserving bijection
from adom(B) to fa; a g. Then we
have
\Psi. The first equivalence holds because
\Phi is generic, the second equivalence is obvious
from the lemma and the definition of \Psi, and
the third equivalence holds because ae is order-preserving
and \Psi 2 L ! (query sentences in L !
cannot distinguish between databases that are isomorphic
via an order-preserving bijection).
We can conclude that all generic queries that
are not expressible in L ! , like even cardinality
of a relation or connectivity of a graph, are
not expressible as a linear query either. Non-
expressibility in L ! has been addressed at length
by Grumbach and Su [9]. Grumbach, Su, and
Tollu [10] have also obtained inexpressibility results
for linear queries, using complexity argu-
ments. In particular, they showed that in the
context of the rationals Q rather than the reals
R, linear queries are the complexity class AC 0 ,
while even cardinality and connectivity are not.

Acknowledgment

We are grateful to Bart
Kuijpers for his careful reading of earlier drafts
of the material presented in this paper.



--R

Foundations of Databases.
Universality of data retrieval languages.
Geometric reasoning with logic and algebra.

Constraint Logic Programming: Selected Re- search
G'eometrie Alg'ebrique R'eelle.
Computable queries for relational data bases.
Quantifier elimination for real closed fields by cylindrical algebraic decom- position
Finitely representable databases.
Linear constraint databases.
Domain independence and the relational calculus.
Constraint query languages.
On the expressive power of the relational calculus with arithmetic con- straints


--TR

--CTR
Leonid Libkin, A collapse result for constraint queries over structures of small degree, Information Processing Letters, v.86 n.5, p.277-281, 15 June
Gabriel M. Kuper , Jianwen Su, A representation independent language for planar spatial databases with Euclidean distance, Journal of Computer and System Sciences, v.73 n.6, p.845-874, September, 2007
Michael Benedikt , Martin Grohe , Leonid Libkin , Luc Segoufin, Reachability and connectivity queries in constraint databases, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.104-115, May 15-18, 2000, Dallas, Texas, United States
Michael Benedikt , Martin Grohe , Leonid Libkin , Luc Segoufin, Reachability and connectivity queries in constraint databases, Journal of Computer and System Sciences, v.66 n.1, p.169-206, 01 February
Michael Benedikt , Leonid Libkin, Relational queries over interpreted structures, Journal of the ACM (JACM), v.47 n.4, p.644-680, July 2000
Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001
linear arithmetic;first-order logic;relational databases;constraint programming