On first-order topological queries.
One important class of spatial database queries is the class of topological queries, that is, queries invariant under homeomorphisms. We study topological queries expressible in the standard query language on spatial databases, first-order logic with various amounts of arithmetic. Our main technical result is a combinatorial characterization of the expressive power of topological first-order logic on regular spatial databases.
Introduction
The expressive power of first-order logic over finite relational
databases is now well understood [AHV95, EF95].
Much less is known in spatial databases (also called constraint
databases), where the relations are no longer finite
but finitely represented [KLP99].
The notion of genericity (invariance of queries under
isomorphisms), fundamental for the relational database
model, can be generalized to spatial databases in various
ways [PVV94]. Given a group G of transformations (trans-
lations, affinities, isometries, similarities, homeomorphism-
s, etc.), a query Q is G-generic if for all database instances
I and each transformation
FOG we denote the set of G-generic first-order queries. The
genericity of a first-order query is undecidable [PVV94],
but the expressive power of FO G can be understood via
sound and complete (decidable) languages. A language is
said to be sound for G if it contains only FO G queries. It is
complete for G if it expresses all FO G queries. The choice of
the group G depends on which information one is interested
in. [GVV97] gives sound and complete languages for several
natural groups of transformations (translations, affinities,
isometries, similarities). The case of the group of homeomorphisms
was left open.
To appear in Proceedings of the 15th IEEE Symposium on Logic in
Computer Science. c
IEEE 2000.
Queries invariant under homeomorphisms, which are also
called topological queries, are of fundamental importance
in various applications of spatial databases. For ex-
ample, in geographical databases, queries like "Is region A
adjacent to region B?", "Is there a road from A to B?", or "Is
A an island?" come up very naturally. Therefore, topological
queries have received a lot of attention in the literature
(e.g. [KPV97, PSV99, SV98, KV99]). A basic result known
about topological queries is that connectivity of a region is
not expressible in first-order logic [GS99, GS97, BDLW96].
Thinking of geographical databases again, planar (or 2-
dimensional) database instances, where all relations are embedded
in the plane R 2 , are of particular importance. In
[PSV99] it has been proven that all topological properties
of a planar spatial database can be represented in a finite
structure called the topological invariant of the instance.
In [SV98] it has been shown how this topological invariant
can be used to answer topological queries. In particular,
[SV98] have proven that first-order topological queries on
a spatial database can be automatically translated into fixpoint
queries on the topological invariant. The translation
of first-order topological queries on the spatial database into
first-order queries on the topological invariant was proven
possible only in the special case of a single relation representing
a closed region. It was left open in [SV98] whether
this translation could be extended to the case of several re-
gions. We answer this question negatively.
The idea of representing the topological information of
a spatial database instance by the topological invariant has
two important drawbacks: In a sense, the topological invariant
contains too much information; ideally we would
just want to store the information that is actually accessible
by the query language (which is usually FO). Furthermore,
the topological invariant has no straightforward generalization
to higher dimensions. The issue of finding an invariant
more suitable for FO (and computable in any dimension)
was raised in [KPV97].
In the special case of one single relation representing a
closed planar region, a cone structure was given in [KPV97]
capturing precisely the first-order topological information.
Intuitively, the cone structure is a finite set containing all
the possible small neighborhoods of a point. The results of
[KPV97] show that, in this context, first-order topological
queries could express only local properties, which is a situation
known to be true in the finite case. [KPV97] asked
whether their results generalize to database instances with
a region that is not necessarily closed; we give a negative
answer to this question. For instances with one closed region
that satisfy the additional technical condition of being
fully two dimensional, [KV99] introduced a cone logic CL
and proved that it is sound and complete for topological FO.
They asked if their results generalize to instances with not
necessarily closed regions or several regions, again we give
a negative answer.
[KPV97] introduced two local operations on spatial
database instances that preserve the equivalence under first-order
topological queries (called topological elementary e-
quivalence). We call two
instances
-equivalent if they can
be transformed into instances homeomorphic to each other
by applying the operations of [KPV97] finitely often. Our
main technical result, from which all the rest easily follows,
is that on especially simple instances that we call regular,
-equivalence and topological first-order equivalence coincide

The paper is organized as follows: After recalling a few
basic definitions on spatial databases in Section 2, in Section
3 we discuss the topology of planar spatial databases
and the topological invariant in detail. In Section 4 we introduce
topological first-order queries and review some results
of [KPV97]. In Section 5, we prove
that
-equivalence is
decidable in PSPACE. Our main result on regular instances
is proved in Section 6. In Section 7, we derive that not
all first-order topological queries can be translated to first-order
queries on the topological invariant, and in Section 8
we briefly discuss the problem of finding a language that is
sound and complete for topological FO.
2. Preliminaries
Spatial databases. We fix an underlying structure R over
the reals; either we let
(R; <; +; 0; 1) or R = R poly
be the vocabulary of R (i.e. either
For a point  an
jja  bjj < rg be the open ball with radius r around  a.
1 As a matter of fact, we could let R be any o-minimal structure over
the reals, and the main results would remain true.
poly we may also let
a 2
n , and we will
assume we have done so in our figures - it just looks better. Since we are
only interested in topological queries, this makes no difference.
A subset S  R n , for some n  1, is R-definable, if
there is a first-order formula '(x) of vocabulary R such
that
A schema is a finite collection  of region names. Let
n  1. An n-dimensional spatial database instance I over
associates an R-definable set R I  R n with every R 2
. The sets R I are called the regions of I . Formally, we
may interpret the region names as n-ary relation symbols
and view an instance I over  as a first-order structure of
vocabulary R [  obtained by expanding the underlying
structure R by the relations R I , for I 2 .
In this paper, we only consider 2-dimensional (or pla-
spatial database instances. For convenience, we also
assume that all regions are bounded, i.e. that for every instance
I over a schema  and for every R 2  there exists a
R such that jjajj  b for all  a 2 R I . The boundedness
assumption is inessential and can easily be removed, but it
occasionally simplifies matters.
Queries. An n-ary query (for an n  0) of schema  is
a mapping Q that associates an R-definable subset Q(I)
R n with every instance I over . Here we consider R 0 as
a one point space and let R
query is usually called Boolean query.
As our basic query language we take first-order logic FO.
of vocabulary R [
defines the n-ary query
I 7! '(I) := f(a an an )g
of schema .
3. The topology of planar instances
R 2 is equipped with the usual topology.
The interior of a set S  R 2 is denoted by int(S), the
closure by cl(S), and the boundary by bd(S). We say that
a set S  R 2 touches a point  a 2 R 2 if
a 2 cl(S). Two
sets touch if S 2 touches a point  a 2 S 1 or vice
versa.
Stratifications. Stratification is the fundamental fact that
makes the topology of our instances easy to handle.
A stratification of an instance I over  is a finite partition
S of R 2 such that
(1) For all S 2 S, either S is a one point set, or S is homeomorphic
to the open interval (0; 1), or S is homeomorphic
to the open disk
(2) For all
cl(S) \ cl(S 0 ) is the union of elements of S.
(3) For all R 2  and S 2 S we either have S  R I or
The following lemma follows from the fact that all regions
of an instance are R-definable. A proof can be found
in [vdD98].
Lemma 3.1. For every instance I there exists a stratification
of I .
Colors and cones. Let I be an instance over . The pre-
color of a point  a 2 R 2 is the mapping (a)
fint; bdi; bde; extg defined by
int if  a 2 int(R I );
bde if  a 2 bd(R I ) n R I ;
ext if  a 2 R 2 n cl(R I
A pre-cell is a maximal connected set of points of the same
pre-color. The cone of a point  a 2 R 2 , denoted by cone(a),
is the circular list of the pre-colors of all pre-cells touching
a. Lemma 3.1 implies that cones are well-defined and finite.
A point  a 2 R 2 is regular if for every neighborhood U of
a there is a point  a 0 2 U such that
Otherwise  a is singular. It follows from Lemma 3.1 that
an instance has only finitely many singular points. We call
an instance regular if it has no singular points. The cones

Figure

1. Two singular and two regular cones
of regular (singular) points are also called regular (singular,
resp.) (cf. Figure 1).
The cone-type of I , denoted by ct(I), is a list of all cones
appearing in I . Furthermore, for every singular cone this list
also records how often it occurs.
The color
of a point  a 2 R 2 is the pair
.
Cells. A cell of color
of I is a maximal connected set
of points of color
. The color of a cell C is denoted by
(C). Lemma 3.1 implies that there are only finitely many
cells. Our assumption that all regions are bounded implies
that there is precisely one unbounded cell, which we call
the exterior of I . Lemma 3.1 implies that every cell has a
well defined dimension, which is either 0, 1, or 2. The 0-
dimensional cells are precisely the sets fag, where
a is a
singular point.
Let C I be the set of all cells of an instance I . We define
a binary adjacency relation E I on C I by letting two cells
be adjacent if, and only if, they touch. We call the graph
the cell graph of I . We can partition C I into
three subsets C I
1 , and C I
2 consisting of the 0, 1, and 2-
dimensional cells, respectively. Observe that the graph G I is
tri-partite with partition (C I
I is planar.
Lemma 3.2. Let I be an instance and C 2 C I .
(1) If C 2 C I
either C is homeomorphic to the open
disk (0), or there exists an m  1 such that C
is homeomorphic to the open disk Dm with m holes.
To be definite, we let
Dm := D n
cl
then C is homeomorphic to the sphere
or to the open interval (0; 1).
Proof: This follows easily from Lemma 3.1. 2
The skeleton S I of an instance I is the set of all 0-
dimensional cells and all 1-dimensional cells homeomorphic
to (0; 1). Note that the skeleton of a regular instance is
empty.
Lemma 3.3. Let I be an instance. Then every connected
component of the graph G I n S I is a tree.
In particular, if I is regular then G I is a tree.
Proof: Follows from the Jordan Curve Theorem and Lemma
3.2. 2

Figure

2 illustrates a typical connected component of an
instance I after removing the skeleton. Note that every con-
Figure

2.
nected component of the graph G I n S I has a unique "ex-
terior" cell which we may consider as the root of the tree.
Having the tree directed by fixing this root, we may speak
of the parent and the children of a node.
The following observation will be useful later.
Lemma 3.4. Let I ; I 0 be instances and C 2 C I
I 0such that
2 that is
adjacent to C there exists a
2 that is adjacent to C 0
such that
The topological invariant. Two instances I ; J over a
schema  are homeomorphic if there is a homeomorphism
such that for all  a 2 R 2 and R 2  we
have  a 2 R I () h(a) 2 R J .
The topological invariant of an instance I over  is an
expansion Y I of the cell graph that carries enough information
to characterize an instance up to homeomorphism. The
vocabulary of Y I is ^
R O is 8-ary, and
R for R 2  are unary. The
restriction of Y I to fEg is the cell graph G I of I . dim i
consists of the i-dimensional cells, for 2. X only
contains the exterior of I (the unique unbounded cell). For
every R 2 , the unary relation ^
R consists of all cells that
are subsets of R I .
O gives the orientation. It is an equivalence relation on
the quadruples (C;
are adjacent to C. Two such quadruples
are equivalent if either
i in the clockwise order of
the cells adjacent to C i for both i 2 f1; 2g or B 0
appears
i in the anti-clockwise order of the cells
adjacent to C i for both i 2 f1; 2g . 3 Note that O is empty
in regular instances.
It is proven in [PSV99] that I and J are homeomorphic
iff Y I and Y J are isomorphic and that Y I is computable
from I in time polynomial in the size of I . Since G I is
a planar graph and canonization of planar graphs is in P-
TIME, we can actually assume that Y I is canonical in the
sense that for homeomorphic instances I and J we have
In [SV98] it is proven that FO-queries over I can be
translated in linear time into fixpoint+counting queries over
Y I . Furthermore, if FO-queries over I can
be translated to FO-queries over Y I on instances with just
one closed region. (More precisely, this means that there is
a recursive mapping that associates with every ' 2 FO of
vocabulary f<; Rg a ' 0 2 FO of vocabulary d
fRg such that
for all instances I over fRg, where R I is a closed set, we
have I
The question was left open whether this result extends to
instances with one arbitrary region or with several regions.
In Section 6, we give a negative answer to this question.
3 There are various ways to define the orientation, ours is equivalent to
[SV98].
4 More precisely, there is a PTIME algorithm that, given an instance
I, computes Y I and a one-to-one mapping  I : C I
(a canonical numbering) such that for homoemorphic instances I; J the
mapping is an isomorphism from Y I to Y J .
4. Topological queries and topological elementary
equivalence
Topological queries. A query is topological if for every
homeomorphism h of R 2 and for all instances I we have
denotes the set of all first-oder
formulas defining a topological query.
It is well-known (and easy to see) that the set FO top is not
decidable.
The following lemma collects a few basic FO-queries.
Its proof is an easy exercise.
Lemma 4.1. (1) For every color
there is a first-order
(x) such that for every instance I and for
every  a 2 R 2 we have I
(a) ()
(2) For every (y) 2 FO there is a formula ' bd(
FO such that for every instance I we have ' bd(
(3) There is a formula '1 (x) 2 FO such that for every
instance I we have

Note that for every color
the formula '
is in FO top .
Moreover, for 2 FO top the formula ' bd( ) is in FO top . In
particular, this is the case for for an R 2 .
On the other hand, the formula '1 is not in FO top .
Topological elementary equivalence. Two instances I ; J
are (topologically) elementary equivalent (denoted I  t J)
if they satisfy the same topological first-order sentences.
It is proven in [KPV97] that if  = fRg then for all
instances I ; J in which R I , R J are closed sets we have:
I  t J
We will see in the next section that this equivalence cannot
be extended to instances with one arbitrary region or with
several regions.
To prove this result, [KPV97] introduced two simple local
operations transforming an instance into an elementary
equivalent one. Their straightforward extension to several
regions is depicted in Figure 3, which is to be read as fol-
lows: Suppose we have an instance I that contains an open
subset O  R 2 homeomorphic to one of the left hand sides
of

Figure

3. The different shades of grey display different
colors. Then it can be replaced by the corresponding subset
on the right hand side (cf. [KPV97] for details). Note that
both operations are symmetric, we can go from the right to
the left by applying the same operation again.
the first and ! 2 the second of the two
operations in Figure 3. For instances I and J we write
I !! i J if I can be transformed into an instance homeomorphic
to J by an application of ! i (for i 2 f1; 2g). We

Figure

3. Operations preserving  t .
I
J if I and J can be transformed into each other
by a finite sequence of operations !!1 and !!2 .
Then the proof of [KPV97] easily yields:
Lemma 4.2. For all instances I , J we have: I
I  t J .
It is an open question whether the converse of Lemma
4.2 holds. In particular, this is interesting because is not
known whether  t is decidable or not, whereas
is decidable
in PSPACE (this is Proposition 5.5 of the next sec-
tion). [KPV97] have shown that that  t and
coincide
on instances with only one closed region. We can extend
their result to several regions, but only on instances with
only regular cones.
5. Minimal instances
Definition 5.1. An instance I is minimal if it satisfies the
following two conditions:
1 is homeomorphic to S 1 and Iare adjacent to C and homeomorphic to Dm , for some
are adjacent to B and
homeomorphic to S 1 , then
Lemma 5.2. There is a PTIME algorithm that associates
with every instance I a minimal instance M(I) such that
I
M(I).
This can be done in such a way that for homeomorphic
instances I ; J we have
Proof: Suppose first that I does not satisfy (M1). We show
that I can be transformed to instance J with fewer cells
violating (M1), by two applications of ! 1 .
Let C be a 1-dimensional cell homeomorphic to S 1 such
that both neighbors of C have the same color, but
neither is homeomorphic to D. Then instance I locally
looks like Figure 4(1). We apply ! 1 twice (to the dashed
boxes) and obtain an instance that locally looks like Figure
4(3). We have obviously reduced the number of cells
violating (M1).
(1) (2) (3)

Figure

4.
Suppose now that I does not satisfy (M2), then it can
be transformed to an instance J with fewer cells violating
(M2) by an application of ! 1 without violating (M1).
To see this, let B be a 2-dimensional cell in I that is adjacent
to the cells C homeomorphic to S 1 of the same
color. A cell homeomorphic to S 1 is adjacent to two 2-
dimensional cells. Let be the other neighbors of
the same color. We have to distinguish between two cases:
Case 1: Both C 1 and C 2 are children of B. Then we can
reduce the number of cells violating (M2) by an application
of

Figure

5).
(1) (2)

Figure

5.
Case 2: C 1 is the parent of B and C 2 its child. Figure 6
shows how to proceed.
(1) (2)

Figure

6.
A PTIME algorithm transforming a given instance I to a
minimal instance M(I) may proceed as follows: Given I ,
the algorithm first computes the invariant Y I ; this is possible
in PTIME [PSV99]. The operations ! 1 and ! 2 translate
to simple local operations on Y I . Our algorithm first applies
pairs of ! 1 until (M1) holds (as in figure 4), and then
holds. This can be done by a simple greedy
strategy. The result is a structure Y that is the toplogical invariant
of a minimal instance M(I). It is shown in [PSV99]
that, given an invariant Y , an instance J such that Y
can be computed in polynomial time.
Because Y I is canonical (cf. Page 4), this algorithm also
guarantees that for homeomorphic instances I ; J we have
The language of an instance. A fundamental curve
in an instance I is an R-definable continuous mapping
lim a!1 jjf (a)jj = 1. If f is a fundamental curve in I ,
then for every 2-dimensional cell the set f 1 (C) is a finite
union of open intervals (one of which is of the form
a) and one of the form (b; 1)), and for every 0- and
1-dimensional cell C the set f 1 (C) is a finite union of
closed intervals (some of which may just be single points).
This follows from the fact that f is R-definable.
We are interested in the finite sequence of colors appearing
on a fundamental curve, i.e. in a finite word W (f; I)
over the alphabet  I consisting of all colors appearing in I .
We say that a word W 2
I is realized in I if there is a fundamental
curve f such that W (f; . The language
L(I) is the set of all words realized by I .
Example 5.3. Let I be the instance with
R I := fa 2 R 2 j (1=2) < jjajj  1g.
I has five cells C 1 := fa
- be the colors of C
respectively, and note that C 5 has the same color  as C 1 .

Figure

7.
a
b a
a
d
d

Figure

8.
Then for example the words
and
are realized in I (cf. Figure 7). It is not hard
to see that L(I) can be described by the finite automaton
displayed in Figure 8.
-From this example it is easy to see that for every I the
language L(I) is regular; it is accepted by an automaton
that is essentially the cell graph.
More formally, let I be an instance. We define a finite
automaton A I
(where 1 is a new symbol that does
not denote a cell).
:= f(C;
denotes the
exterior.
Note that the graph underlying A I is the cell graph G I extended
by one additional vertex 1 that is only adjacent to
the exterior. The proof of the following lemma is straight-forward

Lemma 5.4. For every instance I , the automaton A I accepts
L(I). Thus L(I) is a regular language.
A walk in a graph E) is a sequence
for 1  i < n. For a mapping
. Then it is almost immediate
that for every instance I we have
wn walk in G I
with
where as usual EXT denotes the exterior.
Proposition 5.5.
is decidable in PSPACE.
Proof:
Given two instances I and J , we want to check in
PSPACE whether it is possible to go from I to J using
only homeomorphisms and operations
in
. Given an instance
I it is possible to compute its invariant Y I in PTIME
[PSV99]. Thus the problem reduces to checking in PSPACE
whether Y J can be derived from Y I using operations from
. There are at most polynomially many different ways to
apply operators
from
to Y I (one just has to consider tuples
of at most 5 cells and check if an ! i can be applied
to this tuple).
Let
I) be the set of invariants that can be
obtained from Y I by applying one operation
from
. The
previous remarks show
that
I) contains at most polynomially
many elements and can be computed in PTIME. It
is therefore possible to enumerate all topological invariants
that can be derived from Y I by applying operations
in
and check at each step whether it corresponds to Y J or not.
The latter can be done in PTIME, because this is deciding
whether two planar graphs are isomorphic.
We now give a strategy that ensures that this process will
stop. Because M(I) and M(J) are computable in PTIME
(Lemma 5.2), we can assume I and J minimal.
It is easy to see that operations
in
do not change the
cones of the instances involved. Therefore I
J implies
that I and J have the same cone-type (cf. Page 3) and the
same orientation relation O. This can be checked in PTIME.
As the cones determine the number of 1-dimensional cells
homeomorphic to (0; 1), this implies that all instances J
such that I
J are such that their respective skeletons
verify jS I
We may view the skeletons S I and S J as embedded planar
graphs with the 0-dimensional cells as vertices and the
1-dimensional cells homeomorphic to (0; 1) as edges. Let
F I and F J , resepectively, denote the faces of these embedded
graphs. Note that these faces correspond precisely
to the connected components of G I n S I and G J n S J , re-
spectively. The number of connected components of S J is
bounded by c I < jI j, the number of cones of I . Therefore
the number of faces of S J is given by the Euler formula,
we have jF J is the number of
connected components of S J , and e; v its number of edges
and vertices. As  is bounded by jI j, so is jF J j. This gives
a linear (in jI j) bound on the number of connected components
of G J n S J . We would also like to bound the size of
each connected component of G J n S J (or equivalently the
number of 1-dimensional cells homeomorphic to S 1 ). Un-
fortunately, repeated application of the
operations
1 and
may produce arbitrary large such components.
Nevertheless, it is possible to decide in PSPACE whether
I ! K for an instance K such that there is an isomorphism
from S K to S J that preserves the coloring
and
orientation O. Furthermore, if there is such a K, it can
be computed in PSPACE. The complexity is PSPACE because
there is no need to produce extra 1-dimensional cells
homeomorphic to S 1 during this process. This would only
restrict the number of possible connections between the
connected components of the skeleton.
So without loss of generality we can now assume that I
and J are minimal and have isomorphic skeletons. Recall
that every face f 2 F I (f 2 F J ) corresponds to a connected
component T f of G I n S I (G J n S J , respectively).
By Lemma 3.3, T f is a tree with a canonical root
exterior cell.
To find out whether I
J , for each isomorphism
that preserves the coloring and orientation we
check whether there are instances I 0
I and J 0
such that S I 0
for every face f 2 F I 0
we have T f
denotes the face
corresponding to f under the isomorphism i).
It suffices to prove the following for every f 2 F I :
Claim 1. Either I
6
J , or I and J can be transformed to
instances I 0 and J 0 , respectively, with S I 0
such that in I 0 the component T f is isomorphic to T i(f) in
ffg, the component T g in I 0 has
remained the same as in I , and for all h 2 F J n fi(f)g, the
component T h in J 0 has remained the same as in J .
It can be decided in PSPACE which of the two alternatives
holds, for the latter I 0 ; J 0 can also be computed in
PSPACE.
We can go through all isomorphism i in PSPACE, so we
fix one. We also fix a face f 2 F I .
Before going on we need the following definitions. A
branch of a tree T is a minimal walk in T going from the
root of T to one of its leaves. A walk in G I is said to be
regular if it never goes through a singular cell. Let  be the
set of colors of I and J . For a word W 2   , we define
M(W ) as the word of   computed using rules in the same
spirit as in Lemma 5.2. More precisely this means rewriting
the word W using the rules  !  for all colors ; .
Fact 1. Let
x be a regular walk in G I which starts in
. Then it is possible to transform I in such a way that T f
contains a branch t
x , such that
(x).
This can be proved by a single loop on the length of
starting from the end. Without loss of generality
we can assume that xn is a 2-dimensional cell. We
start by constructing in xn 2 a new ball vn 1 vn of colo

This is easily done by applying ! 1 or ! 2
once. Assume next that we have constructed a subinstance
whose cell graph is a path attached to x i . Again
we apply ! 1 or ! 2 once in order to get v
surrounding v i+1    vn .
The same kind of induction (but starting from the beginning
of the word this time) shows that the converse also
holds:
Fact 2. If it is possible to construct using operations
in
a
new branch t in T f then there exists a walk
x t in G I starting
from E f such that M(
(t)).
We say that a walk  x realizes a word W in I if
It can be checked in PSPACE whether
a given word is realized by a walk in G I starting in E f ; one
way to see this is to reduce the problem to the question of
whether two regular languages have a non-empty intersection

Now we can prove Claim 1. We first transform I to I 0 .
For each branch
x of T i(f) starting from E i(f) , let W
(x) and check whether there is a walk  x 0 that realizes W
x .
If this is not the case, Fact 2 shows that I
6
J . If it is the
case, use Fact 1 to construct the corresponding branch in I .
To construct J 0 , do the same after reversing the role of I
and J . It is clear that if the algorithm does not find out that
J on its way, after minimizing the resulting instances
they satisfy the claim.In the next section, it will be convenient to work with
a slight simplification of the cell graph. We call a 2-
dimensional cell B 6= EXT of an instance I inessential if
B is homeomorphic to a disk D (and thus has precisely one
neighbor in G I ), and the neighbor C of B in G I has another
neighbor
(B). Let H I be the graph
obtained from G I by deleting all vertices that are inessential
cells. We call H I the reduced cell graph of I . Then (5.1)
actually holds with H I instead of G I :
wn walk in H I
with
6. Regular instances
Recall that an instance I is regular if all points  a 2 R 2
are regular. The main result of this section is that
and
t coincide on regular instances. As a corollary, we will see
that the equivalence (4.1) does not extend beyond instances
with one closed region.
To illustrate where the problems are, let us start with a
simple example:
Example 6.1. Let consider the two instances
I ; J with R I := fa
3  jjajj  1g, R J := S I , and S J := R I
(cf.

Figure

9). Obviously, I and J have the same cone-type.

Figure

9.
Let us try to find a sentence ' 2 FO top such that I
and J 6j= '. At first glance this looks easy, just take the
sentence saying "every horizontal line that intersects region
R intersects region S before". Then every instance homeomorphic
to I satisfies ', and every instance homeomorphic
to J does not satisfy '.
Unfortunately, ' 62 FO top . Figure 10 shows why: All
three instances displayed are homeomorphic, but only the
last one satisfies '.
We will see later that there is a sentence ' 2 FO top that
distinguishes I from J , but such a ' is quite complicated.
For now, let us just note that I
6
J .

Figure

10.
Recall that by Lemma 3.3, the cell graph and thus the
reduced cell graph of a regular instance is a tree. We think
of this tree as being directed with the exterior as its root.
The leaves are the 2-dimensional cells homeomorphic to the
disk D.
For instances I ; J we write H I
H J if there is an
embedding h of H I into H J that preserves
. We define
accordingly.
Lemma 6.2. For all regular instances I ; J we have H I
H J if, and only if, I and J are homeomorphic.
Proof: The backward direction is trivial. For the forward
direction, let I and J be regular instances with H I
H J .
Then it follows from Lemma 3.4 that G I
G J . Since for
regular instances the orientation O is empty, this implies
Y I Thus I and J are homeomorphic by [PSV99].2
Recall the definition of the minimal instance M(I) associated
with an instance I . An inspection the proof of Lemma
5.2 shows that for a regular instance I we have
If M is a minimal regular instance, then the reduced cell
graph H M has the following nice property:
If C is a vertex of H M , then all neighbors
of C in H M have different colors. (6.2)
Lemma 6.3. Let M;N be minimal regular instances. Then
Proof: This is an easy consequence of (5.2) and (6.2). 2
Recall that a regular language L    is aperiodic
if there exists an n 2 N such that for all u; v; w 2
such that uv n w 2 L we also have uv n+1 w 2 L. By a
well-known theorem of McNaughton, Papert [MP71] and
Sch-utzenberger [Sch65], the aperiodic languages are precisely
the languages that are definable in first-order logic. 5
The following lemmas will be useful later. They are all
based on (6.2) and the fact that the reduced cell graphs of
regular instances are trees.
5 Furthermore, these are precisely the star-free regular languages.
Lemma 6.4. Let M be a minimal regular instance. Then
L(M) is aperiodic.
Proof:
Let M be a minimal regular instance.
The crucial step is to prove the following claim:
Let
a walk in H M such that y
Suppose for contradiction that (6.3) is wrong. Choose
l minimal such that there is a v 2  l , an n  2,
and a walk y
Since adjacent vertices in a cell graph (and thus in a
reduced cell graph) have different colors and
(y l+1 ), we have l  2.
For notational convenience, we let y 0 := y nl , y
We choose an
such that there is no nlg such that y j is in the
subtree below y i . Then y is the parent of y i .
Let  :=
Then for 0  k  n we have
(y
By (6.2), this implies y
y kl+j+1 . If l = 2, this implies y
tion. If l  3 we can define a walk  y 0 from
y by deleting
y kl+j and y kl+j+1 , for 0  k  n 1. Then (6.3) holds
with in contradiction to the minimality
of l.
This proves (6.3).
Now let n > jH M j and u; v; w 2   such that
We shall prove that uv n+1 w 2 L(M).
Let k; l; m be the length of u; v; w, respectively, and  x :=
a walk in H M with
there exist
such that x Applying (6.3) to the walk
But then
is a walk with
be a minimal regular instance and
instances such that J
Proof: Recall the definitions of the operations ! 1 and ! 2
from

Figure

3. It suffices to prove the statement for instances
L(M). Note that there is a word
obtained from W by replacing some letters
by subwords  (if J !!1 J 0 ) or
(if
Suppose for contradiction that W 0 2 L(M). Then
there is a walk
x 0 in H M such that
. By (6.2), whenever
Hence
n is a walk in H M with
Similarly, if
, we have x
that
a contradiction.
This shows that W 0
Lemma 6.6. Let M be a minimal regular instance and J
a regular instance with L(J) 6 L(M). Then there is a
R such that for the curve f b : x 7! (x; b) we have
Proof: We assume that J and M are instances over the
same schema. Then, denoting by EXT and EXT 0 the exterior
of J , M , respectively, we have
For every walk
define a sequence
n as follows: We let x 0
i be the (by (6.2) unique)
neighbor of x 0
1 that has the same color as x i , if x 0
and such a neighbor exists, and x 0
H J is a tree and H M satisfies (6.2), x
j or x 0
m). It follows
that for any walk
or y 0
.
Note that actually the sequence  x 0 only depends on the
word
(x). This if
then
only if, x 0
Now suppose that
with x 0
that xm+1 must
be a child of xm in the tree H J .
Choose b 2 R such that the curve f b intersects the cell
xm+1 . Let
l be a walk in H J that corresponds
to the curve f b and let j < l be minimal such that y
xm+1 . Then y because xm+1 is a child of xm .
Then either y 0
m . In both case we have
Theorem 6.7. Let I be a regular instance of schema .
Then there is a sentence ' I 2 FO top of vocabulary f<g[
such that an instance J of the same schema  satisfies ' I
if, and only if, J
I .
Proof: Let  be the set of colors appearing in I . For every
aperiodic language L    there is a formula L (y) 2
FO of vocabulary f<g [  such that a regular instance I
satisfies L (b) for a b 2 R if, any only if, W (f b ; I) 2 L.
This is an easy consequence of the theorem of McNaughton,
Papert and Sch-utzenberger that the aperiodic languages are
precisely the first-order definable languages.
Let M := M(I) and L := L(M). By Lemma 6.4, L is
aperiodic. Let
Clearly, M satisfies M .
We claim that for all instances J we have:
To prove this claim, note first that every instance satisfying
M realizes the same cones as I and thus is regular.
Let J be a regular instance. Assume first that J
Then by Lemma 6.6, L(J)  L(M). Because J
M(J), by Lemma 6.5 we have L(M(J))  L(M). Thus
Conversely, if M(J)
and thus J
This proves (6.4).
It follows easily that M 2 FO top . Indeed, assume that
. For every J 0 homeomorphic to J we have
We let
N minimal regular instance
with H N
We shall prove that for any instance J of schema  we
have
Suppose that J I . Then in M(J) I by (6.4).
By Lemma 6.6, this implies L(M(J))  L(M) and
minimal regular N with H N
H M . By Lemma 6.3, this implies M(J)
M . By Lemma
6.2, it follows that M and M(J) are homeomorphic.
Thus J
I .
Conversely, suppose that J
I . Then by Lemma 4.2,
I . Thus J I , because ' I 2 FO top and I
(the later follows easily from the previous paragraph and
Corollary 6.8. For all regular instances I ; J we have I
Finally, we are ready to prove that the equivalence (4.1)
does not extend beyond instances with one closed region.
Corollary 6.9. The two instances of Example 6.1 are not
elementary equivalent. Neither are the instances I ; J over
fRg defined by:
R I := fa
7. Translating sentences to the topological in-
variant
Recall that it is proven in [SV98] that there is a recursive
mapping that associates with every ' 2 FO of vocabulary
f<; Rg a ' 0 2 FO of vocabulary d
fRg such that for
all instances I over fRg, where R I is a closed set, we have
I
The purpose of this section is to prove that this does not
extend to arbitrary instances.
Proposition 7.1. There is a sentence ' 2 FO top of vocabulary
f<; Rg such that for every sentence ' 0 2 FO of vocabulary
d
fRg there is an instance I such that I
G I 6j= ' 0 .
Proof: Let I 0 ; J 0 be the instances defined by
For n  1, let I n ; Jn be defined by
R In := R I0 [
R In := R I0 [
a
(cf.

Figure

11).

Figure

11. The instances I 3 and J 3 .
Note that for all n; m  1 we have I n
I m and Jn
Jm , but I n
6
Jn . Corollary 6.8 implies that there is a
sentence ' 2 FO top such that for all n  1 we have I n
and Jn 6j= '.
Let n  1. The graph G In is just a path with 5
tices, say, C . Denoting the colors by
the colors on this path form the following sequence:
| {z }
times
| {z }
times
G Jn is the same, except that
. The other relations of the topological invariant
are identical in Y In and Y Jn . dim 0 is empty, dim 1
consists of all C i with even i, and dim 2 consists of the C i
with odd i. The orientation O is empty. Finally, g.
Standard Ehrenfeucht-Fra-ss-e techniques show that for
every sentence ' 0 2 FO there is an n  1 such that Y In
' if, and only if, Y Jn
The statement of the proposition follows. 2
8. On completeness of languages
An open problem that we have not considered so far is
to find a (recursive) language that expresses precisely the
first-order topological queries. Although this is certainly
an interesting question, we doubt that, even if theoretically
such a language exists, it would be a natural language that
may serve as a practical query language. Our results show
that first-order topological queries are not local; on the other
hand, it is known that first-order logic fails to express the
most natural non-local topological queries such as connectivity
of a region.
[KV99] have introduced a topological query language,
the cone-logic CL, only expressing local properties. This
language is a two tier language that allows to build first-order
expressions whose atoms are again first-order expressions
talking about the cones and colors of points. [KV99]
have proven that CL captures precisely the first-order topological
properties of instances with only one closed region
that is "fully 2-dimensional". If the underlying structure is
R< , it follows from [SV98] that the condition of being full
2-dimensional is not needed. Corollary 6.9 shows that this
result does not extend to instances with several closed regions
or one arbitrary region.
We propose to extend CL by a path operator, as it has
been introduced in [BGLS99]. Let us call the resulting
topological query language PCL. The results of [BGLS99]
show that this language has the basic properties expected
from a reasonable spatial database query language. In addi-
tion, it admits efficient query evaluation (the cost of evaluating
a PCL-query is not substantially higher than the cost
of evaluating a first-order query).
An example of a PCL-query not expressible in FO is
connectivity of regions. We conjecture that conversely every
FO top -query is expressible in PCL. The idea behind this
conjecture is that local properties (expressible in CL) together
with the language of an instance, which can be described
by the path-operator, seem to capture the first-order
topological properties of an instance. As a first step towards
proving this conjecture, let us remark that Corollary 6.8
implies that on regular instances every FO top -sentence is equivalent
to a set of PCL-sentences.
9. Conclusions
The results of this paper give a good understanding of
first-order topological queries on regular instances. Of
course one may argue that regular instances are completely
irrelevant - look at any map and you will find singular
points. However, we could use our results to answer several
open questions concerning topological queries on arbitrary
instances.
As a matter of fact, we have shown that the previous understanding
of first-order topological queries, viewing them
as "local" in the sense that they can only speak about the
colors of points, is insufficient; this may be our main contribution

The problem of a characterization of topological elementary
equivalence on arbitrary planar instances remains open.
We conjecture that Corollary 6.8 generalizes, i.e. that  t is
the same as
on arbitrary instances. If this was true, by
Proposition 5.5 topological elementary equivalence would
be decidable in PSPACE. Let us remark that we do not believe
that the PSPACE-bound of Proposition 5.5 is optimal,
we see no reason why
should not be decidable in NP or
even PTIME.



--R

Foundations of Databases.
Relational expressive power of constraint query lan- guages
Reachability and Connectivity Queries in Constraint Databases.
Languages for relational databases over interpreted structures.
Safe constraint queries.
Finite Model Theory.
Queries with arithmetical constraints.
Finitely representable databases.


Constraint Databases.

Bart Kuijpers and Jan Van den Bussche.

Topological queries in spatial databases.

On finite monoids having only trivial subgroups.
Querying spatial databases via topological invariants.

--TR
Towards a theory of spatial database queries (extended abstract)
Queries with arithmetical constraints
Finitely representable databases
Relational expressive power of constraint query languages
Topological queries in spatial databases
Complete geometric query languages
Reachability and connectivity queries in constraint databases
Querying spatial databases via topological invariants
Foundations of Databases
Constraint Databases
On Capturing First-Order Topological Properties of Planar Spatial Databases
Fixed-Point Logics on Planar Graphs

--CTR
Michael Benedikt , Jan Van den Bussche , Christof Lding , Thomas Wilke, A characterization of first-order topological properties of planar spatial data, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Michael Benedikt , Bart Kuijpers , Christof Lding , Jan Van den Bussche , Thomas Wilke, A characterization of first-order topological properties of planar spatial data, Journal of the ACM (JACM), v.53 n.2, p.273-305, March 2006
constraint databases;first-order logic;topological queries