Luc Segou
email: luc.segoun@inria.fr

Victor Vianu
email: vianu@cs.ucsd.edu

Querying Spatial Databases via Topological Invariants

The paper investigates the use of topological annotations (called topological invariants) to answer topological queries in spatial databases. The focus is on the translation of topological queries against the spatial database into queries against the topological invariant. The languages considered are rstorder on the spatial database side, and xpoint + counting, xpoint, and rst-order on the topological invariant side. In particular, it is shown that xpoint + counting expresses precisely all the ptime queries on topological invariants; if the regions are connected, xpoint expresses all ptime queries on topological invariants.

Introduction

Spatial data is an increasingly important part of database systems. It is present in a wide range of applications: geographic information systems, video databases, medical imaging, CAD-CAM, VLSI, robotics, etc. Di erent applications pose di erent requirements on query languages and therefore on the kind of spatial information that is needed. For example, in some cases the precise distance between points is important, while in other applications only topological relationships are of interest. Such di erences in scope and emphasis are crucial, as they a ect the data model, the query language, and performance. In this paper we focus on the representation and querying of topological properties of spatial databases.

Motivated primarily by geographic information systems, we use a spatial model that speaks about regions in the two-dimensional plane. Regions are speci ed by inequalities involving polynomials with rational coe cients, as done in constraint databases (such regions are called semi-algebraic). Topological properties of regions are those that are invariant under homeomorphisms of the plane. This means, intuitively, that continuous deformations and re ections of the spatial instance do not a ect satisfaction of the property. For example, the property \the intersection of regions P and Q is connected" is a topological property. On the other hand, the property \the point p is North of the point q" is not topological. In previous work PSV99] it was shown that topological properties of semi-algebraic regions in a spatial database can be completely summarized by an annotation presented in classical relational database form, called the topological invariant of the database 1 . Moreover, the topological invariant of a semi-algebraic database can be constructed very e ciently { in nc.

Suppose that a topological query is posed against the spatial database. In principle, the query can be answered by another query posed against the topological invariant. Since the topological invariant is in most cases smaller in size than the original database, this strategy is likely to be more e cient. In order for this to work, topological queries in the spatial query language need to be e ectively translated into queries in some query language for topological invariants. There are two components to this question:

This work was partly performed while the rst author was visiting U.C. San Diego and partly while the second author was visiting I.N.R.I.A. V.Vianu was supported in part by the NSF under grant number IRI-9221268. 1 A similar invariant for isotopy-invariant properties is presented in KPV95], see related work.

1

What language L inv on topological invariants is needed in order to answer the topological queries formulated in a given query language L spatial on spatial databases? Is there an e ective, uniform translation of topological queries in L spatial into queries in L inv ? What is the complexity of the translation? To answer the rst question, it is useful to understand the expressiveness of various query languages on topological invariants. Topological invariants have special structure, so with some luck they might be better behaved than arbitrary relational databases. This is fully con rmed by our rst result: we show that xpoint + counting expresses precisely the ptime queries over topological invariants ( xpoint alone is su cient if the regions are connected). This should be contrasted with the situation on arbitrary structures, where xpoint + counting falls short of capturing ptime (indeed, it is conjectured that there is no language capturing ptime). This result is very helpful in answering the rst question above, since it makes xpoint + counting (or xpoint in the case of connected regions) a natural target for the translation of topological queries on spatial databases. In the broader context of the theory of query languages, the result is signi cant because it identi es topological invariants as a class of nite structures of practical interest which is very well-behaved with respect to descriptive complexity.

With respect to the second question, we focus on the translation problem for rst-order queries. A common language for constraint spatial databases is FO(R; <). We consider primarily this language on the spatial database side. On the topological invariant side, xpoint + counting is a possible translation target, as suggested by the earlier expressiveness result. Indeed, we show that topological FO(R; <) queries can be uniformly translated in linear time into xpoint + counting queries on the invariant. However, another natural candidate target for the translation is FO. The translation problem now becomes much harder, and we solve it in the special case of single-region databases. However, the region can be highly complex, so the result is fairly general and provides considerable insight into the technical issues involved in the translation.

Unfortunately, the translation cannot be extended to the multi-region case GroSeg99].

Interestingly, even when both FO and xpoint + counting can be used as targets of the translation of topological FO(R; <) queries, there is a signi cant di erence in the complexity of the translation: the complexity is hyperexponential in the quanti er depth of the input query when the target is FO, but it goes down to linear time in the size of the query when the target is xpoint + counting. This suggests an interesting trade-o between the expressive power of the target query language over the topological invariant and the complexity of the translation. Related work. Work in spatial databases has focused on developing models and query languages targeted to various application domains, as well as appropriate data structures and e cient evaluation techniques. We refer to Par95] for a survey of the eld emphasizing geographic information systems.

Various topological invariants have been used in geographic information systems in order to speed up the evaluation of queries that make reference to topological properties of regions (e.g. in the ARC/INFO system Mor85, Mor89]). Among them, the 4-intersection model of topological relationships FK86, Her91, Wor92] has been widely adopted in geographic information systems and has been used in several spatial query languages Ege94, OV91, SZ91]. The satis ability problem for 4-intersection relationships is investigated in GPP95]. The expressiveness of these relationships has been investigated by Egenhofer and Franzosa EF91], who make the argument that they are natural and cognitively plausible, and observe that they cover all possibilities that are expressible in the language that includes disjointness of two sets, interior, exterior, boundary, and Boolean connectives. The 4-intersection invariant was further re ned by Egenhofer and Franzosa, by taking into account additional information, such as the number and dimension of components of the boundary intersection of two regions FE92, Ege93, EF95a]. In particular, the invariant exhibited in EF95a] is claimed (without proof) to completely characterize two regions (discs) up to homeomorphism.

Unlike the above topological invariants, the topological invariants we use are lossless, i.e. they completely characterize the topology of a set of regions. The invariants contain information similar to the PLA model proposed by the U.S. Census Bureau, which provides topological properties on points, lines, and areas [START_REF] Cai | An optimal lower bound onb the number of variables for graph identi cation[END_REF][START_REF] Paredaens | Towards a theory of spatial database queries[END_REF]. The invariants we use can be viewed as an augmentation of the PLA model. Models using decompositions of the space into cell complexes have been used in the geographic information systems community for some time (e.g., see [START_REF] Egenhofer | Spatial SQL: A Query and Presentation Language[END_REF][START_REF] Gurevich | Logic and the challenge of computer science[END_REF][START_REF] Vardi | The complexity of relational query languages[END_REF]). The complexity of computing topological information based on cell complexes, similar to the PLA model and to our invariants, has been studied in computational geometry BKR86, KY85]. While a aw has been discovered in the complexity analysis of BKR86], later modi cations recovered, and even improved upon their upper bounds, see Renegar Ren92].

The topological invariant we use is essentially the one introduced in PSV99]. The invariants proposed in KPV95] are also close to the topological invariants we consider, but capture isotopy-generic information.

Various notions of G-invariance (or G-genericity) for di erent groups G of permutations are discussed in Par+94]. They propose a spatial database model that includes spatial and thematic information, and propose a calculus and an equivalent algebra.

Much of the formal work related to spatial databases focuses on constraint databases, consisting of relations whose tuples represent semi-algebraic regions, speci ed by polynomial inequalities. Such databases and corresponding query languages were rst considered in KKR95]. In particular, they investigate the question of when the answer of a query on a constraint database is representable as a constraint database. Their results are based on quanti er elimination in the rst-order theory of the reals Tar51].

Our result that xpoint + counting expresses ptime on topological invariants is closely related to an elegant result in nite-model theory independently obtained by Grohe Gro98]. It is shown there that xpoint + counting expresses ptime on planar graphs, and xpoint alone captures ptime on 3-connected planar graphs.

The paper is organized as follows. The spatial model used in the paper, as well as topological invariants, several relational and spatial query languages, and Ehrenfeucht-Fraiss e games, are reviewed in the Preliminaries. Section 3 contains the result on the capture of ptime by xpoint + counting on topological invariants, and related results. Section 4 presents the results on the translation of spatial topological FO(R; <) queries into xpoint + counting and FO queries on topological invariants.

Preliminaries

Practical spatial databases (such as geographic information systems) mix thematic and spatial information. Answers to queries can also be multi-sorted. Since our focus is on the spatial aspect, we adopt a simpli ed model where the only thematic information consists of region names. Also, for the sake of simplicity and uniformity, we only consider Boolean queries, de ning properties of sets of regions. We consider only regions in the two-dimensional space.

We use the following model for spatial databases. We assume given an in nite set names (consisting of names of regions). A spatial database schema is a nite subset Reg of names. An instance I over a schema Reg is a mapping from Reg to subsets of R 2 . For each r 2 Reg, I(r) provides a set of points called the extent of r. We generally refer to a set of points in the plane as a region. In practice, each I(r) is nitely speci ed, although this may be transparent to the user. In this paper, all regions considered are compact (bounded and closed), and speci ed by a disjunction of conjunctions of polynomial inequalities with rational coe cients (this later property is usually referred to as semi-algebraic). In this paper, we will call connected a region which boundary is connected. In the following, the term region will be used in the restricted manner just described, unless otherwise speci ed.

As discussed earlier, we are interested here in topological properties of spatial instances. Two instances I; J over a spatial schema Reg are topologically equivalent i there exists a bijection : R 2 ! R 2 such that both and 1 are continuous and for each r 2 Reg, (I(r)) = J(r). A property of spatial instances is topological if it is invariant under homeomorphisms, that is for all topologically equivalent instances I; J over a given schema, I satis es i J satis es .

Topological invariants [START_REF] Van Oosterom | Building a GIS on Top of the Open DBMS Postgres[END_REF] it was shown that one can e ciently compute from a given semialgebraic spatial instance I a nite relational structure top(I) called the topological invariant of I, that describes completely the topological properties of I. The spatial model used in PSV99] is slightly di erent from the one we use: regions are assumed to be homeomorphic to the unit disk, so are open and have dimension two. In contrast, our regions are closed and may have dimension zero, one, or two (the change is motivated by geographic information systems, where such regions are common). However, the construction and results of PSV99] pertaining to the topological invariant are easily adapted to the model used here. We brie y describe the construction of the invariant and the results.

The invariant is constructed from a maximum topological cell decomposition of the spatial instance. A topological cell decomposition of I is a partition of R2 into nitely many subsets called cells, such that for every homeomorphism of R 2 , if I is globally invariant by ( (I) = I) then, for every cell c, (c) is a cell. It can be veri ed that for each spatial instance I there exists a unique maximal (in terms of number of cells) topological cell decomposition. The maximum topological cell decomposition can be constructed from a semi-algebraic spatial instance in nc, using results 2 on cell complexes obtained in BKR86, KY85].

We summarize their approach, slightly adapted to our context. Given a semi-algebraic spatial instance I over a schema Reg, a sign assignment is a mapping : Reg ! fo; ; @g, and the sign class of is the set I def = T r2Reg r (r) , where r o is the interior of r, r @ is the boundary, and r is the exterior. A cell complex for I is a partition of R 2 into nitely many, non-empty, pairwise disjoint regions, called cells, such that:

1. each cell is homeomorphic to R 0 ; R 1 or R 2 fa nite set of pointsg. The dimension of a cell is de ned in the obvious manner. 2. the closure of each cell is a union of other cells; 3. each cell is included in some sign class I .

It is shown in KY85]3 that a cell complex can be constructed from a given semi-algebraic spatial instance in nc. One can further show that the maximum (see de nition above) topological cell decomposition can be constructed from the cell complex obtained in KY85], and the overall complexity remains nc.

The topological invariant for a spatial instance I is built up from the maximum topological cell decomposition for I. Cells of dimension 0,1 and 2 are called vertices, edges, and faces, respectively. The topological invariant associated to spatial instances over a schema Reg is a nite structure consisting of the following relations (their meaning is explained intuitively):

1. unary relations Vertex, Edge, Face, and Exterior -face providing the cells of dimension 0, 1, 2, and a distinguished face of dimension 2 called the exterior face. 2. Edge-Vertex is a binary relation providing endpoint(s) for edges. 3. Face-Edge is a binary relation providing, for each face (including the exterior cell), the edges on its boundary. 4. Face-Vertex is a binary relation providing, for each face (including the exterior cell), the vertices adjacent to it.

5. for each region name p 2 Reg, a unary relation p providing the set of cells contained in region p.

6. Orientation is a 5-ary relation providing the clockwise and counterclockwise orientation of edges incident to each vertex. More precisely, ( -; v; e 1 ; e 2 ; e 3 ) 2 Orientation i v is a vertex, e 1 ; e 2 ; e 3 are edges of faces incident to v, and e 2 lies between e 1 and e 3 in the clockwise order on the incidents cells of v, and (, !; v; e 1 ; e 2 ; e 3 ) 2 Orientation i v is a vertex, e 1 ; e 2 ; e 3 are cells incident to v, and e 2 lies between e 1 and e 3 in the counterclockwise order on the incident cells of v.

Let inv(Reg) denote the above schema and let top denote the mapping associating to each spatial instance I over Reg its topological invariant over inv(Reg).

Remark: The topological invariant of PSV99] had a slightly di erent schema and de nition. The Orientation relation was 4-ary instead of 5-ary, and corresponded to the successor relation of the incident cells of a given vertex v. For technical reasons, in our setting Orientation provides the full cyclic order of the cells incident to v (without this modi cation, Theorem 4.9 does not hold). This change does not a ect the results on the invariant from PSV99].

The main result on the topological invariant is the following.

Theorem 2.1 PSV99] Let Reg be a spatial database schema.

(i) The mapping top associating to each spatial database instance over Reg its topological invariant is computable in polynomial time (and nc) with respect to the size of the representation of I.

(ii) For all spatial instances I; J over Reg, I and J are topologically equivalent i top(I) and top(J) are isomorphic.

Also useful is the following result, which says that the invariant can be e ciently inverted. A linear spatial instance is a semi-algebraic instance de ned by linear inequalities. Theorem 2.2 PSV99] For each spatial instance I there exists a topologically equivalent linear spatial instance J computable in polynomial time from top(I). Some query languages We assume familiarity with classical relational query languages such as FO (relational calculus), Datalog, Datalog : , and the xpoint and while queries (see AHV95]). Recall that the xpoint queries are expressed by various languages such as in ationary Datalog : and in ationary xpoint logic FO+ + AHV95]. It is well known that xpoint expresses precisely ptime [START_REF]La Base de Donn ees Topographiques de l'I.G.N. (The Cartographical Database of the National Geographic Institute[END_REF][START_REF] Wilke | [END_REF] and while expresses exactly pspace Var82] on ordered databases. Without order, this is not the case: for example, neither xpoint nor while can express the parity query on unary relations (this asks if the number of elements in the relation is even or odd). Queries such as parity can be expressed if a counting mechanism is added to FO+ + , yielding the xpoint + counting queries. The counting is provided by counting quanti ers of the form 9 i x '(x) where integer variables i range over an ordered domain of the same size as the input nite domain and disjoint from it (see CFI92, GO93] for details). Unfortunately, xpoint + counting still fails to express ptime CFI92].

Most of the languages previously proposed for spatial databases, including constraint query languages KKR95, GS99, GST94, Par+95, BDLW98], have rst-order syntax and use variables ranging over numbers (reals or rationals), or over points. We adapt the classical de nitions of these languages to our framework. Let Reg be a spatial database schema. By slight abuse of notation we denote also by Reg the rst-order signature consisting of a binary relation for each region name in Reg. The language FO(R; <) is rst-order logic using region names (viewed as binary relations), variables ranging over R, and the binary relation < interpreted as the usual order on R. It was shown in KKR95] that every FO(R; <) query can be evaluated in nc (relative to the size of the representation of a given semi-algebraic spatial instance). A useful variation is rst-order logic where variables range over points in R 2 , and where the order < is replaced by two order relations < x and < y with the following meaning: p < x q i the x-coordinate of p < the x-coordinate of q, and similarly for < y . Note also that the schema consists of region names viewed as unary relations rather than binary. The point-based language just described is denoted by FO(P; < x ; < y ). Its complexity is also nc.

What is the connection between FO(R; <) and FO(P; < x ; < y )? Clearly, FO(R; <) subsumes FO(P; < x ; < y ), and can express queries that FO(P; < x ; < y ) cannot, such as: \does region P intersect the diagonal ?" as 9x P(x; x)4 However, it is shown in PSV99] (and the result easily carries over to our spatial model) that the two languages express precisely the same topological properties of spatial instances. The fragments of the two languages expressing topological properties are denoted by FO top (R; <) and FO top (P; < x ; < y ), respectively. It is easy to see that these fragments are not e ective: it is undecidable whether a sentence in FO(R; <) or in FO(P; < x ; < y ) is topological 5 . In this paper we assume that queries arising in certain applications are topological, and we do not deal with the issue of verifying or enforcing this property. To our knowledge, it is open whether there exist e ective syntactic subsets of FO(R; <) and FO(P; < x ; < y ) that express precisely their topological fragments.

Ehrenfeucht-Fra ss e games Consider rst-order logic FO over a given vocabulary. Let FO r denote the FO sentences of quanti er depth r. Recall that the quanti er depth qd(') is de ned inductively by qd(') = 0 if ' is quanti er-free, qd(' _ ) = qd(' ^ ) = maxfqd('); qd( )g, qd(:') = qd(') and qd(9x') = qd(8x') = qd(') + 1: Two structures are FO r -equivalent if they satisfy precisely the same FO r sentences. There is a very useful characterization of FO r -equivalence in terms of the Ehrenfeucht-Fraiss e game on structures. The game of length r is played by two players, Spoiler and Duplicator. A round in the game has r moves. In each move, Spoiler picks an element in one of the structures and Duplicator responds by picking an element in the opposite structure. Duplicator wins the round if structures restricted to the chosen elements are isomorphic. We say that Duplicator has a winning strategy for the game of length r if he can win every round of the game no matter how Spoiler plays. The main result on the Ehrenfeucht-Fraiss e game of length r (henceforth called FO r -game) is that two structures I; J are FO r -equivalent i Duplicator has a winning strategy for the FO r -game on I and J. See EF95b] for more details.

As an example, consider the language FO(P; < x ; < y ) over spatial database schema Reg. Suppose I; J are spatial instances over Reg and consider a round of the FO r (P; < x ; < y )-game where points p 1 ; : : : ; p r are picked in I and q 1 ; : : : ; q r are picked in J. Duplicator wins this round i p i 2 P , q i 2 P for every P 2 Reg and p i ; p j are in the same order relative to < x and < y as q i ; q j , for 1 i; j r. By the above characterization, Duplicator has a winning strategy for the FO r (P; < x ; < y )-game on I; J i I and J are equivalent with respect to FO r (P; < x ; < y ).

Fixpoint queries on topological invariants

As discussed earlier, the topological invariant of a spatial instance can be viewed as an annotation summarizing precisely the topological properties of the spatial instance. Thus, all topological queries can be answered by queries posed against the invariant rather than on the raw spatial data. This can be much more e cient, since the invariant is in most cases much smaller than the original spatial instance. The invariant is a classical relational database, so it can be queried by classical relational queries. However, invariants are not arbitrary databases { they have a special structure, which may engender special properties. In this section we show that topological invariants are especially well behaved with respect to descriptive complexity: the xpoint + counting queries capture precisely ptime over this class of structures. If we restrict our attention to instances were the regions are connected (i.e. have a connected boundary) then it can be shown that xpoint queries capture precisely ptime. This positive result should be contrasted with the situation on arbitrary structures, where there is a large gap between xpoint (+ counting) and ptime (in the absence of order). Moreover, it is conjectured that there is no language capturing ptime on arbitrary structures Gur88].

Fixpoint on connected regions

We rst consider the case when all regions are connected and show that xpoint expresses ptime on topological invariants of such instances. Then we consider the general case (where regions are not necessarily connected) and show that xpoint + counting expresses ptime on topological invariants.

In the remainder of this section we assume all regions are connected, unless otherwise stated. The proof that xpoint captures ptime on topological invariants in the connected case is conceptually easy, but requires some careful development. We use the classical result that xpoint captures ptime on ordered structures Imm86, Var82]. Thus, for each ptime query over topological invariants there exists a xpoint query '( ) which expresses the ptime query given a total order on the universe of the invariant. The problem of course is that topological invariants are not ordered structures { in fact they are not even rigid { so an order is not directly available. The key to the proof is to observe that there is a standard way to traverse each connected component of the topological invariant, once a constant number of vertices and/or edges have been xed, together with an orientation (or , !). This allows to construct by a xpoint query a polynomial number of orderings, each of which is identi ed by a tuple of constant arity. Since the number of connected components is bounded by the number of regions in the schema, we can put together the orders for each connected component and obtain a polynomial number of orders of the entire invariant. Lastly, '( ) is \run simultaneously" on all of the orderings. Since '( ) is order independent by de nition, all of the \runs" produce the answer to the query.

We now describe the construction in more detail. We break down the construction in several sequential stages, and for each we outline the construction of a xpoint query. Since xpoint is closed under composition, we can then put together the queries for each stage and obtain a nal xpoint query that computes the given ptime query on the invariant. Consider a ptime query over the invariant and let '( ) be a xpoint query that computes it using a total order on the universe (vertices, edges, faces,and , !) of the invariant.

The skeleton of a topological invariant is the graph whose vertices are the elements of the relation Vertice and Edge of the invariant, and whose edges correspond to the relation Edge-Vertex in the invariant. A connected component of the topological invariant is a connected component of the skeleton of the invariant.

To illustrate this de nition, the connected components in Figure 1 are c 1 ; ; c 7 . Since all regions are connected, each connected component of the invariant consists of the boundaries of a set of regions. Thus, there is a partition of the set of region names into equivalence classes de ned by membership of the boundaries into the same connected component. Clearly, for each partition there exists an FO query which veri es that is the partition of region names corresponding to the given topological invariant. We will also need a formula de ning the set of vertices, edges, and faces of each connected component.

For vertices and edges this can be easily done by an FO formula. More care is needed for faces, since the boundary of a face may intersect several connected components (this happens when a connected component is embedded in a face of another connected component). To associate unambiguously a face to a connected component, one can rst de ne a partial order on connected components based on their distance from the external face (i.e. the shortest sequence f 0 ; e 0 ; f 1 ; e 1 ; : : : f k ; e k such that f 0 is the exterior face, e k is in the given connected component, and e i is adjacent to f i ; 0 i k). For instance, in Figure 1, the connected components c 1 and c 2 are at distance 0 from f O , c 3 ; c7 at distance 1, and c 4 ; c 5 and c 6 at distance 2. It is easily seen that for each face other than the exterior face f 0 there exists a unique connected component at minimal distance from f 0 intersecting the boundary of the face. We then say that the face belongs to that connected component. In Figure 1 the boundary of region f 2 touch three connected components, c 1 ; c 3 ; c 7 , and is therefore associated to c 1 because c 1 is at distance 0 from f 0 while the other two are at distance 1.

It is a straightforward exercise to see that the previous construction can be stated by a xpoint formula. In summary, one can construct a xpoint query comp i (x) saying that x is a vertex, edge, or face in connected component i.

Consider a connected component of the topological invariant. An edge is called a proper edge if it connects distinct vertices. We will show that one can construct by a xpoint query a total order on the vertices, edges, and faces of the connected component, once a vertex, an adjacent proper edge, and an orientation ! 2 f -; , !g have been xed. This applies to connected components which have at least one proper edge (and therefore each vertex is connected by some proper edge to another vertex). The special case where there is no proper edge requires special treatment, but presents no di culty. We can show the following.

Lemma 3.1 There exists an FO + + formula (!; v; e; x; y) such that for each orientation !, vertex v and proper edge e adjacent to v, the set !;v;e (x; y) = fhx; yi j (!; v; e; x; y)g is a total order on the vertices, edges, and associated faces of the connected component of v.

Proof For the moment, suppose that all connected components have at least one proper edge. We describe the construction of the FO + + query (!; v; e; x; y) computing the orders !;v;e for each connected component C containing vertex v with an adjacent proper edge e, and xed orientation !. The query rst constructs the set of tuples < !; v; e > where ! 2 f -; , !g, v is a vertex in C and e is a proper edge adjacent to v (this is an FO query, given C). For each such tuple < !; v; e >, the following is done. First, an order on the vertices of C is de ned; simultaneously, to each vertex is associated a particular proper edge adjacent to it. Then the order is extended to the edges and faces of C. The order on vertices is de ned as follows. The rst vertex is v. Suppose e 1 ; : : : ; e k are the proper edges adjacent to v in order of the !-orientation, starting from e, and let v 1 ; : : : ; v k be their respective endpoints other than v. The rst iteration computes the partial order v; v 1 ; : : : ; v k . At the same time, the proper edge associated to v i is de ned to be e i , 1 i k. This is iterated starting from the tuples !; v i ; e i , eliminating repetitions of vertices. The partial order obtained for the pair v i ; e i is then inserted between v i and v i+1 , for 1 i < k and that for v k ; e k is inserted following v k . Clearly, this can be achieved by a xpoint query which produces a total order on all vertices of C, and associates along the way a proper adjacent edge to each vertex. Now the ordering is extended to edges as follows. Edges (proper or not) are rst ordered in lexicographic order of the ranks of their endpoints (the edges are allready ordered). Edges with the same endpoints u v are ordered in the !-orientation relative to the proper edge associated with u. Consider two faces f; f 0 in C (recall the earlier de nition of a face being in a connected component). It is easily seen that no two faces in C have the same set of edges in the intersection of their boundary with C. Since edges are already ordered, the faces of C can be ordered using their associated set of edges in C. Thus, vertices, edges and faces of C are ordered. A total order on the universe of C is obtained by having all vertices be smaller than all edges which in turn are smaller than all faces in C.

Lastly, we brie y discuss the special case of connected components with no proper edges. There are three cases:

1. The connected component consists of a single isolated vertex.

2. The connected component consists of a single edge e (a loop with no endpoints).

3. The connected component consists of a vertex and a set of loops around the vertex.

Case (1) is trivial: the order consists of the pair f< v; v >g, where v is the vertex constituting the connected component. Although the order is uniquely determined without xing any elements, for the sake of uniformity we make the order dependent on the pair < !; v; v > (this keeps the result of 5-ary). Case (2) is similar.

For case (3), we consider pairs v; e where v is the unique vertex and e is a loop adjacent to the exterior cell. The order on vertices is simply < v; v >. The order on edges is determined by the !-orientation of edges starting from e. There is one di culty: loops occur twice in !-orientation order. Therefore, the successor of e is ambiguous: however, there is a single loop which follows e in the !-orientation and is also adjacent to the exterior face. This is taken to be the successor of e. Subsequent successors are uniquely determined (each edge is inserted in the ordering only when rst encountered in the !-orientation). If e is the only loop around v then the order is simply < e; e >. The faces of the connected component are ordered as described earlier.

2

Once the query is constructed, we can use it to generate a set of total orders on the entire invariant as follows. Basically, we need to put together the orders for the connected components of the invariant in some arbitrary way determined by some xed order of the region names in the schema, which induces an order on the connected components. Suppose is the partition of region names determined by the connected components of the invariant. The set of total orders on the invariant corresponding to partition is then obtained by placing in increasing order: (i) the elements denoting the orientations, (ii) the external face, and (iii) the ordered vertices, edges, and faces of each connected component, in increasing order of the components. This is accomplished by the FO+ + formula:

(y) (!; v 1 ; e 1 ; : : : ; v k ; e k ; x; y) = Is-Orientation(!) ^V1 i k vertex-edge(v i ; e i ) ^ (x = !) _(Is-Orientation(x) ^y 6 = !) _(Exterior-face(x) ^:Is-Orientation(y) W 1 i k (!; v i ; e i ; x; y) _ W 1 i<j k (comp i (x) ^comp j (y))]

where Is-Orientation(x) = 9v9e 1 9e 2 9e 3 Orientation(x; v; e 1 ; e 2 ; e 3 ):

Thus, has arity 2k + 3 where k is the size of partition . The last two columns in the result provide a total order on the invariant, for each xed tuple over the rst 2k + 1 columns. Note that k is bounded by the size of Reg so is a constant.

Once is constructed, the xpoint query '( ) can be \run" in parallel on the orders provided by . Because the query '( ) is order invariant by de nition, the answer is the same for all orderings. This yields the main result: Theorem 3.2 Fixpoint expresses exactly the ptime queries on topological invariants of instances with connected regions.

Proof We have seen that the parameterized orderings can be de ned by a xpoint query. Let us denote by the parametric variables of (all free variables except x and y in the fromula de ning ) . With available the resulting xpoint query is obtained by a case analysis over the set of partitions of Reg: _ 9

^' ( )]: 2

The above result can be extended to languages subsuming xpoint, such as while. A technique similar to the above allows to show: Corollary 3.3 While expresses exactly the pspace queries on topological invariants of spatial instances with connected regions.

At this point, it may be tempting to believe that descriptive complexity results on ordered structures transfer uniformly to topological invariants. However, this is far from obvious. For example, it is known that semi-positive Datalog, Datalog : with strati ed semantics, and in ationary Datalog : are equivalent on ordered structures and express ptime (see AHV95]). However, it remains open if this holds on topological invariants. Indeed, the xpoint query constructing the orderings on topological invariants involves careful bookkeeping which, on the face of it, requires the full power of in ationary Datalog : or equivalently FO+ + . In particular, negation is applied recursively in our construction of the orderings. It remains open whether the construction can be achieved in a more restrictive language such as strati able or semi-positive Datalog : . Fixpoint + counting on arbitrary invariants Theorem 3.2 relies crucially on the assumption that regions are connected. In the case where this is not required, each region may have an unbounded number of connected components, and xpoint cannot express ptime queries such as: Is there an even number of connected components? However, this di culty can be overcome by adding counting to xpoint. Indeed, we can show that in this case xpoint + counting expresses precisely the ptime queries on topological invariants. The idea of the proof is to construct using xpoint + counting an isomorphic copy of the invariant over the auxiliary ordered domain provided by xpoint + counting, then use the fact that xpoint expresses ptime on ordered databases Imm86, Var82].

Theorem 3.4 Fixpoint + counting expresses exactly the ptime queries on topological invariants. Proof As stated above, we will exhibit a xpoint + counting query which, given as input a topological invariant I, produces an isomorphic copy of I on the auxiliary ordered domain. Clearly this is su cient to establish the theorem, since xpoint expresses ptime on ordered structures.

The proof involves several stages. First recall that, using Lemma 3.1, we can deal with single connected components: by the lemma, a xpoint query can de ne polynomially many orderings of the invariant. Each ordering < is parameterized by a tuple of xed arity. For each xed ordering <, the invariant can be viewed as an ordered structure c < . Note however that di erent orderings produce di erent ordered structures. To produce a single isomorphic copy on the auxiliary ordered domain, it is su cient to de ne some standard lexicographic ordering among ordered structures c < and pick the minimum ordered structure c min with respect to the lexicographic order. It is now easy to construct an instance isomorphic to c min over the auxiliary ordered domain.

The idea just described can be extended to multiple connected components. First, we de ne a labeled tree that captures the way connected components are embedded into faces. The nodes of the tree are (conceptually) the connected components of the invariant (except for the root, denoted 1). Each connected component c is in fact represented in the tree by its set of vertices6 V c . The edges of the tree are labeled by faces (into which the children connected components are embedded). The tree is de ned inductively as follows. The outgoing edges from the root 1 are all labeled f 0 (the external face). The children of the root are all connected components which share boundaries with f 0 . Now suppose c is a node of the tree. The outgoing edges from c are labeled by all faces f that share a boundary with c and do not yet occur as labels in the tree. There is an edge labeled f from c to each connected component c 0 other than c that shares boundaries with f. It is easy to see that the tree just described can be de ned by a xpoint query. We refer to this tree as the connected component tree of the invariant, denoted T 1 . For example, the connected component tree corresponding to the instance in Figure 1 is represented in Figure 2. For each node c in T 1 , let T c be the subtree of T 1 with root c. Note that each T c corresponds to an invariant comprising c and the connected components embedded in c, denoted inv(T c ). We show the following:

(y) There exists a xpoint + counting query that de nes, for each subtree T c of T 1 , a structure V c inv N (T c ) where inv N (T c ) is an isomorphic copy of inv(T c ) on the auxiliary ordered domain.

In particular, (y) shows that one can de ne in xpoint + counting a structure f1g inv N (T 1 ), and therefore inv N (T 1 ). This is an isomorphic copy of the original invariant over the auxiliary ordered domain.

To prove (y) we proceed inductively by the depth of the subtree. For the basis, consider a subtree of depth zero consisting of a single node c (one connected component). As discussed earlier, this case can be dealt with using the parameterized orders de nable in xpoint by Lemma 3.1. Now consider a subtree T c of depth > 0. By induction, suppose that for each child d of c, a structure V d inv N (T d ) has been de ned, where V d is the set of vertices of d and inv N (T d ) is an isomorphic copy of inv(T d ) over the auxiliary ordered domain. To extend the construction to T c , we rst de ne parameterized orders over inv(c) using the xpoint query provided by Lemma 3.1. Consider one such order <. The cells of inv(c) are totally ordered by < and so inv(c) can easily be mapped to an isomorphic structure inv N (c) over the auxiliary ordered domain. Now we wish to extend this mapping to inv(T c ). Note that children of c embedded in distinct faces of c can be ordered according to the order on faces induced by <. For children d; d 0 of c embedded in the same face of c there are two cases. First, if inv N (T d ) 6 = inv N (T d 0 ), then d and d 0 can be ordered in the lexicographic order of inv N (T d ) and inv N (T d 0 ). If inv N (T d ) = inv N (T d 0 ) then T d and T 0 d are isomorphic and cannot be ordered. However, this di culty can be overcome using counting. Indeed, it is easy to see that one can de ne in xpoint + counting , for each child d of c, the number n of children of c that are embedded in the same face as d and are isomorphic to it. Then one can simply produce n disjoint isomorphic copies of d on the auxiliary ordered domain. In summary, one can de ne in xpoint + counting one isomorphic copy inv N (T c ) over the auxiliary ordered domain for each ordering < previously de ned on inv(c). To produce a single copy inv N (T c ) is is enough to pick among the copies corresponding to the di erent orderings the lexicographically minimum one. Lastly, this structure is associated with c by taking the product of V c with inv N (T c ). This completes the induction and proves (y) and the theorem. 2

The above result can also be extended to language subsuming xpoint, such as while. We denote the natural extension of the partial xpoint queries with counting by while + counting.

Corollary 3.5 While + counting expresses exactly the pspace queries on topological invariants. Remark Theorems 3.4 and 3.2 crucially rely on the fact that regions are part of the database schema and so are xed. Now suppose that this is relaxed so that region names are part of the instance rather than the schema. Then xpoint + counting fails to capture ptime. This is shown by representing arbitrary graphs as spatial instances where each edge is identi ed by a region name, and using the fact that xpoint + counting fails to capture ptime on arbitrary graphs CFI92].

PTIME topological queries on spatial instances

The capture of ptime by xpoint + counting on topological invariants has consequences for the capture of the ptime topological queries on spatial instances (recall that such queries are assumed to be Boolean). Indeed, Theorem 3.2 together with Theorem 2.2 imply that there exists a language expressing precisely the ptime topological queries on spatial instances. Queries in the language consist simply of a xpoint + counting query applied to the topological invariant of the given spatial instance. Clearly, all such queries are topological and are computable in ptime in the size of the representation of the spatial instance. To see that the converse is true, let ' be a topological ptime query on spatial instances. Let inv(') be the query on topological invariants which does the following:

1. on input T, compute from T a semi-linear spatial instance J such that top(J) = T. This can be done in ptime by Theorem 2.2.

2. compute '(J). Clearly, the query inv(') is in ptime on topological invariants, so it is expressed by some xpoint + counting query . Since ' is topological and I and J are topologically equivalent, we have that '(I) = '(J) = (top(I)) for every spatial instance I. Thus, ' is expressed by a query in the language. Note that xpoint + counting can be replaced by xpoint if regions are connected.

It is worth noting that the capture of topological ptime on spatial instances is not simply a direct consequence of Theorems 2.1 and 3.2, as one might rst be tempted to believe. Indeed, this relies crucially on the fact that topological invariants can be e ciently inverted (Theorem 2.2). To understand the importance of this fact, it is useful to make a parallel with invariants for nite structures undistinguishable by rst-order logic sentences with k variables, called k-invariants. Like topological invariants, k-invariants can be computed e ciently (by a xpoint query, see AV95, DLW95]). Furthermore, the k-invariants are ordered structures so xpoint captures ptime on k-invariants. Thus, the analogs of Theorems 2.1 and 3.2 hold. However, this 1. for each ' 2 FO top (R; <) and each spatial instance I over Reg with connected regions, '(I) = inv(')(top(I)). 2. inv(') is computable in linear time in the size of '.

Remark 4.3 In the above, it is assumed that the queries in FO(R; <) to be translated are known to be topological. As discussed in Preliminaries, we do not deal here with the issue of verifying or enforcing that the input ' to the translation is indeed topological (which is undecidable). Instead, we assume that this property is guaranteed by the nature of the application, by the query interface, or other extraneous reasons.

If the input ' is not topological, the result of the translation is no longer equivalent to '. Instead, it is equivalent to the \topological closure" of ', denoted ' top , de ned as follows:

' top = fI j 9J I H J; J j = 'g:

In the remainder of the section we consider the connection between FO top (R; <) and FO inv . We begin with an example that provides some intuition into the di culties involved in translating FO top (R; <) sentences into FO inv sentences. Consider the query on schema Reg = fP; Qg: \Regions P and Q intersect only on their boundaries." Clearly, this is a topological property. It can be expressed in FO top (R; <) by the sentence: (y) 8x8y (P (x; y) ^Q(x; y)) ! (boundary P (x; y) ^boundary Q (x; y))] where boundary P (x; y) (and similarly boundary Q (x; y)) is the formula 7 : P(x; y) ^8x 1 8y 1 8x 2 8y 2 (x 1 < x < x 2 ^y1 < y < y 2 ) ! 9x 0 9y 0 (x 1 < x 0 < x 2 ^y1 < y 0 < y 2 ^:P(x 0 ; y 0 )]:

Clearly, the same property can be expressed by the FO inv sentence over inv(Reg):

(z) 8u (P (u) ^Q(u)) ! (V ertex(u) _ Edge(u))]:

However, how to get from (y) to (z) is mysterious. The di culty is to algorithmically extract the topological meaning of an FO top (R; <) sentence like (y) that uses non-topological statements involving reals and <. We solve the translation problem for the case when Reg contains a single region name; it has been recently shown that the translation is not possible with several region names GroSeg99]. Recall however that single regions can be arbitrarily complicated (as long as they are semi-algebraic and compact), so the result is fairly general and provides considerable insight into the technical issues involved in the translation. In the remainder of the section, spatial database schemas have a single region name unless otherwise speci ed.

We next develop the technical machinery needed for the translation of FO top (R; <) queries into FO inv queries. For technical reasons, it will be useful to rst translate FO top (R; <) queries into the point-based language FO top (P; < x ; < y ). By PSV99], this translation can be done in linear time. Thus, it is su cient to show how to translate FO top (P; < x ; < y ) queries into FO inv queries. We make use of results in KPV97] concerning the equivalence of spatial instances (with a single region name) with respect to FO top (R; <). It is shown there that equivalence of spatial instances with respect to FO top (R; <) (and therefore FO top (P; < x ; < y ), see Preliminaries) is completely characterized by the cone type of the instances, that is the multiset consisting of all vertices (cells of dimension zero) and the cyclic list of their adjacent edges and faces (labeled by whether or not they belong to the region). Furthermore, KPV97] provides a normal form constructing from each instance I an instance cones(I) consisting essentially of the cones of I. For example, given the instance I in Figure 3, the instance cones(I) is represented in Figure 4.

Remark 4.4 The normal form of KPV97] is introduced as a technical tool in the proof of their Proposition 10. It is referred to as an instance with owers and stems. The normal form is not unique: di erent instances in normal form have the same owers but these can be conected in di erent ways by the stems. Since the di erences are irrelevant for our purpose, we denote with cones(I), by abuse of notation, one of the possible instances in normal form constructed from I. Thus, I and cones(I) satisfy the same FO top (P; < x ; < y ) sentences and cones(I) is generally much simpler than I. In terms of the invariant, the relevant information about cones(I) can be represented as a set of colored cycles: to each cone corresponds two cycles representing the list of edges and faces adjacent to the vertex of the cone in clockwise, resp. counterclockwise order. More precisely, consider the structure cycles(I) consisting of the following relations: the 4-ary relation Between such that Between(!,x,y,z) holds if x, y and z are cells adjacent to some vertex, and y lies between x and z in the orientation !. the restriction of relations Edge and Face of top(I) to elements occurring in relation Between.

Clearly, the structure cycles(I) is essentially a set of 2-colored cycles (the nodes are colored according to whether they are a face or an edge). For example, cycles(I) for the instance I in Figure 3 Lemma 4.5 The structure cycles(I) can be de ned by rst-order means from top(I). Let cycles be an FO inv formula de ning cycles(I) from top(I).

The proof of this lemma is rather straightforward. Each element of Vertex in top(I) de nes a cycle in cycle(I) which element are its neighborhoods de ned by the relation Edge-Vertex and Face-Edge, ordered using the Orientation predicate.

The key observation in the translation provides a condition on cycles(I) and cycles(J) that ensures FO r top (P; < x ; < y )-equivalence of cones(I) and cones(J). We rst consider the case when cycles(I) and cycles(J) consist of single cycles (in the two orientations), then consider the case of multiple cycles. We rst prove the following. Lemma 4.6 Let cones(I); cones(J) be spatial instances consisting of a single cone. If cycles(I) and cycles(J) are equivalent with respect to FO r+2 then cones(I) and cones(J) are equivalent with respect to FO r top (P; < x ; < y ).

Proof Suppose cones(I); cones(J) consist of single cones and cycles(I) and cycles(J) are equivalent with respect to FO r+2 . Note that each of cycles(I) and cycles(J) consists of a single cycle (in the two orientations). We wish to prove that cones(I) and cones(J) are equivalent with respect to FO r top (P; < x ; < y ). The di culty is that cones(I) and cones(J) are generally not equivalent with respect to FO r (P; < x ; < y ). To show their equivalence with respect to FO r top (P; < x ; < y ), we construct instances nice(cones(I)) and nice(cones(J)) such that:

nice(cones(I)) is equivalent to cones(I) with respect to FO r top (P; < x ; < y ); nice(cones(J)) is equivalent to cones(J) with respect to FO r top (P; < x ; < y ); and, nice(cones(I)) and nice(cones(J)) are equivalent with respect to FO r (P; < x ; < y ). To construct nice(cones(I)) from cones(I) (and similarly for J) we modify cones(I) in two stages. First, we apply a homeomorphism to cones(I). In the second stage we replace the resulting instance with an instance equivalent to it with respect to FO top (P; < x ; < y ). Since both transformations preserve equivalence with respect to FO r top (P; < x ; < y ), nice(cones(I)) is equivalent to cones(I) with respect to FO r top (P; < x ; < y ). Lastly, we show that nice(cones(I)) and nice(cones(J)) are equivalent with respect to FO r (P; < x ; < y ) (and therefore with respect to FO r top (P; < x ; < y )). The above sequence of equivalences shows that cones(I) and cones(J) are equivalent with respect to FO r top (P; < x ; < y ). We now describe the two stages in the construction of nice(cones(I)) and nice(cones(J)). One subtlety is that the constructions for I and J are not independent, as will become clear shortly. The purpose of the rst stage in the construction of nice(cones(I)) and nice(cones(J)) is to lie out the lines and petals (faces) of the two cones in a very regular manner, which will eventually facilitate playing an FO r (P; < x ; < y )-game on the modi ed instances. In the rst stage, the vertex of each cone is placed at the origin, and all petals are placed in the second quadrant so that their minimum points relative to < y are lined up parallel to the x-axis (see Zone A in Figure 6). Consider a bounding box that includes all the petals of the cone. The lines are pushed away to a region that lies to the lower right of the bounding box, and the connections between the lines are drawn there (Zone B in Figure 6).

Let us focus on Zone B of the instances constructed so far. Note that the pattern of connections in Zone B can be quite complex. However, the connections can be drastically simpli ed as illustrated in Figure 7: lines are simply connected in consecutive pairs (there is always a even number of lines because each line enters and leaves the zone exactly once). Consider the subinstance consisting of a bounding box around Zone B, where the connections occur. Each line intersects the left edge of the box at a point, and connections between the lines can be viewed as connections between the corresponding points. Since the cones around these points remain unchanged by the above simpli cation, the instance with simpli ed Zone B is equivalent to the original with respect to FO top (P; < x ; < y ) by KPV97].

The constructions of nice(cones(I)) and nice(cones(J)) outlined so far have been independent of each other. However, we glossed over two technical subtleties: (ii) The construction of the instances in the rst stage must make a choice of a rst line or petal (the closest to the positive x-axis).

The information needed to deal with (i) and (ii) is provided by the winning strategy of the Duplicator in the FO r+2 -game on cycles(I) and cycles(J). Consider (i). To see if a re ection must be applied to one of the instances, consider the winning strategy of the Duplicator for the game where the Spoiler rst picks an orientation in the structure cycles(I). Duplicator responds by picking an orientation in cycles(J). If the orientations are the same, no re ection is needed. Otherwise, a re ection is applied to one of the instances. Now consider (ii). Continuing with the game, suppose Spoiler picks a node n I in cycles(I) and Duplicator responds by picking a node n J in cycles(J). Then in the construction of nice(cones(I)) the rst line or petal is chosen to be the one represented in the invariant by n I , and the rst line or petal in nice(cones(J)) is chosen to be the one corresponding to n J . The construction of nice(cones(I)) and nice(cones(J)) is now complete.

We next show that nice(cones(I)) and nice(cones(J)) are equivalent with respect to FO r (P; < x ; < y ), i.e. the Duplicator has a winning strategy for the FO r (P; < x ; < y )-game on the two instances. This is done by combining winning strategies from two games. The rst is used to guide the game within Zone A, and the second provides a strategy for Zone B. It is easy to see that the game in the two zones are independent of each other.

We begin by describing Duplicator's winning strategy for Zone A. The strategy mimics Duplicator's winning strategy for the r remaining moves of the (r + 2)-game on cycles(I) and cycles(J) (recall that the rst two moves are used in the construction of nice(cones(I)) and nice(cones(J))). Suppose Spoiler picks a pebble p in Zone A in, say, instance nice(cones(I)). If p is in the region, it belongs to an edge or face represented by a node c in cycles(I). Suppose Duplicator's response in the game on cycles(I) and cycles(J) is to pick a node c 0 in cycles(J). In the FO r (P; < x ; < y )-game on nice(cones(I)) and nice(cones(J)) Duplicator picks a point p 0 on the edge or face corresponding to c 0 . Furthermore, due to the similar shapes of the two cones, p 0 can be picked so that it sits in the desired order relative to previously picked points. If the point languages is hyperexponential in r and the regular expressions de ning the languages of dot-depth r can be e ectively computed Wil]. Let L denote the regular language consisting of words of r-type . Also, let R consist of the set of r-types such that L \ L( ) 6 = ; and R consist of the remaining r-types. Note that R (and so R) is e ectively computable from EF95b]. Furthermore, it turns out that L( ) can be computed from R. To see this, let us denote by L the closure of a language L under conjugate, i.e. L = fvu j uv 2 Lg.

(It is easily seen that if L is regular then L is also regular.) We claim that (y) L( ) = \ 2R L 2 R L Let L R denote the right hand side of (y), and observe that L R is a regular language whose regular expression is e ectively computable from R. To prove (y), consider rst the inclusion L( ) L R . Suppose c is of (r + 1)-type . Clearly, L(c) \ L 6 = ; for each 2 R. Since L(c) is generated by the conjugates of any word it contains, it follows that L(c) L for every 2 R. For similar reasons L(c) \ L = ; for every 2 R. It follows that L( ) L R . Conversely, consider L R L( ). Let w 2 L R and c w be the cycle corresponding to w. We wish to show that c w has (r + 1)-type . Let c be a cycle of (r + 1)-type . It is su cient to show that there is a winning strategy for the (r + 1)-game on c w and c. Suppose Spoiler begins by picking a node in c, yielding a corresponding word u of r-type . Clearly, 2 R and since w 2 T 2R L , some conjugate w 0 of w has r-type . Duplicator then picks the node in c w yielding w 0 . In the remainder r moves, Duplicator mimics the winning strategy of the r-game on w 0 and u. Now suppose Spoiler's rst move is to pick a node in c w , yielding a conjugate w 00 of w. Since w 6 2 S 2 R L it follows that w 00 has r-type for some 2 R. Since c has type , there must exist a node yielding a word u of type , which Duplicator picks. Again, the remainder of the game mimics the winning strategy in the r-game on w 00 and u. Thus, c has (r + 1)-type and so w 2 L( ), which completes the proof of (y). In summary, using (y), one can compute as follows a cycle of type , if such exists: compute a regular expression for L R ; if L R = ; then there is no cycle of type ; if L R 6 = ; nd a word w 2 L R and build the corresponding cycle.

Finally, it is straightforward to construct from the cycle a corresponding cone instance I .

Note that the complexity of the above procedure is hyperexponential in r because there are hyperexponentially many r-types of words, and therefore the size of the regular expression for L R is hyperexponential in r.

The above development leads to the main result on the translation. Theorem 4.9 There exists a mapping inv from FO top (R; <) sentences over Reg to FO inv sentences over inv(Reg) such that:

1. for each instance I over Reg, and ' 2 FO top (R; <),

'(I) = inv(')(top(I)): 2. inv(') is computable from '.
Proof The FO inv sentence inv(') is the sentence described in (?) above. This is rst-order by Lemma 4.7. The computability follows from Lemma 4.8. Remarks (i) Recall that the topological invariant, as de ned in the present paper, contains the relation Between providing the full cyclic order on the elements adjacent to a given vertex. Other presentations of the invariant (including the one in PSV99]) only provides the successor on the element adjacent to each vertex. The distinction is relevant to the results in this section. (They do not a ect the results of Section 3, since xpoint can compute the cyclic order from the successor.) Indeed, the availability of the cyclic order is used in a crucial way in the proof of Theorem 4.9. Speci cally, it allows to de ne cycles(I) from top(I) by rst-order means. It turns out that Theorem 4.9 is no longer true if only the successor is provided. To see this, consider instances having only a single cone. Consider the two sets of such instances illustrated in Figure 9 : on the left side the cone consists of a face followed by several lines then two faces followed by a large number of lines, then again a face followed by lines, and nally two faces followed by lines; on the right side the single faces are consecutive, as are the two pairs of faces, again with a large number of lines in between. It is possible to nd a FO top (R; <) sentence distinguishing the two sets. However, their topological invariants (where successor rather than cyclic order is provided) are indistinguishable by FO inv sentences. This follows from the fact that for each d > 0 if there are su ciently many lines the two instances have the same neighborhood types of size d. Then it follows from FSV95] that the two sets cannot be distinguished by an FO inv sentence. Thus, not all FO top (R; <) sentences can be translated into FO inv sentences on the invariant if the cyclic order is not provided.

Figure 9: Instances that are distinguishable by FO top (R; <), but not by FO inv (ii) Theorems 4.2 and 4.9 suggest an interesting trade-o between the expressive power of the target query language over the topological invariant and the complexity of the translation of FO top (R; <) queries into the target language. Although all FO top (R; <) queries can be uniformly translated into FO inv queries, the complexity of the translation goes down from hyperexponential to linear time if the target language is the more powerful FO + + instead of FO inv .

(iii) We have shown that all FO top (R; <) sentences can be translated into FO inv queries. One might naturally wonder if FO inv and FO top (R; <) express precisely the same topological properties. It is easily seen that this is not the case. For example, consider the instances in Figure 10. Clearly, FO inv can distinguish between the two instances; it follows from KPV97] that FO top (R; <) cannot. (iv) In considering the translation issue, we focused on the topological fragment of FO(R; <) on the spatial database side. It is natural to wonder whether the results can be extended to more powerful languages, such as FO(R; <; +; ). However, there seem to be some di culties involved. For the language FO(R; <; +; ), the use of Ehrenfeucht-Fraiss e games becomes extremely complicated, and it is not clear how to nd the nice instances topologically equivalent to the input that we used in our proof to facilitate Duplicator's strategy.

Incidentally, note that it is open whether the topological fragments of FO(R; <; +; ) and FO(R; <) coincide.

This question is similar to the collapse of order-generic queries for nite database (see BDLW98]).

Conclusions

We examined the use of topological annotations to evaluate topological queries against a spatial database. The rst main result, showing that xpoint expresses exactly the ptime queries on topological invariants, shows that topological invariants are especially well-behaved with respect to descriptive complexity, and provides an appealing target language for the translation of spatial queries into queries against the invariant.

If recursion is not supported, FO top (R; <) queries can be translated into FO inv queries in the case of oneregion schemas. Unfortunately, this cannot be extended to the general case of multiple regions GroSeg99].

The complexity of the translation into FO inv is prohibitively high, even for one-region schemas. However, it becomes more reasonable in several special cases of practical interest, such as the existence of a small bound on number of lines intersecting at one point. In all cases, the cost of the translation has to be balanced against the potential savings due to the di erence in size between spatial databases and their topological invariants. Finally, another appealing option is to use as annotation a linear embedding of the topological invariant, which circumvents the need for query translation.

It is natural to wonder if these techniques can be extended beyond dimension two. This question is examined in Seg], and the picture is largely negative. The existence of a topological invariant for 3-dimensional semi-algebraic databases implies a positive answer to an open problem in Knot Theory: the existence of an invariant for topologically equivalent knots Cro63]. In dimension four (and higher), it is shown in Seg] that there is no nite topological invariant, because topological equivalence itself is undecidable. This is shown by adapting the proof of an undecidability result on topological equivalence of manifolds Mar58]. The latter proof is by reduction of the word problem for nitely generated groups to isomorphism of the fundamental groups of two topological spaces, which in turn is equivalent to their being homeomorphic.

Figure 1 :

 1 Figure 1: A spatial instance.

Figure 2 :

 2 Figure 2: Connected component tree for instance in Figure 1.

Figure 4 :

 4 Figure 3: An instance I

  Figure 5. In the gure, a dark node represents a face in the region, an empty node represents an edge.

Figure 5 :

 5 Figure 5: cycles(I), clockwise orientation

FigureFigure 7 :

 7 Figure 6: nice(cones(I))

Figure 10 :

 10 Figure 10: Instances I and J are distinguishable by FO inv but not by FO top (R; <)

As discussed earlier, while a aw has been discovered in the complexity analysis of BKR86], later modi cations recovered, and even improved upon their upper bounds, seeRenegar Ren92].

Actually KY85] need to do a linear change of the coordinate system in order to be able to compute a cell complex. As this doesn't a ect the topological properties this doesn't a ect the results here. See BCR98, Cos89] for a discussion on cell complex.

It is shown in PSV99] that all queries of FO(P;<x; <y) are invariant with respect to the group of monotone isomorphisms M = f j ((x; y)) = ( 1 (x); 2 (y))g with 1 ; 2 : R ! R bijective and increasing. Since the query 9x P (x; x) is not invariant with respect to M, it cannot be expressed in FO(P;<x; <y).

The undecidability is shown by a straighforward reduction of satis ability for FO(R; <), known to be undecidable GS99]

For simplicity of exposition, we omit the degenerate case of connected components without vertices.

does not imply the existence of a logic for ptime on arbitrary structures. What is missing is the ability to e ciently invert k-invariants Gro97] { the analog of Theorem 2.2.

Of course, the language just described for topological ptime is quite arti cial, but serves the purpose of showing that there exists a logic for topological ptime on spatial instances, in the broad sense of Gurevich's de nition Gur84]. It remains open to nd a more natural language that captures topological ptime on spatial instances { perhaps a recursive extension of FO(R; <). We note that a recursive extension of FO(R; <) expressing all ptime queries on spatial instances is presented in GK97]. However, the language also expresses non-topological queries.

Translating spatial queries into queries on the invariant

In this section we study the problem of translating topological queries against spatial databases into queries against the topological invariant. On the spatial database side, we focus on the language FO(R; <), which is a commonly used language in constraint databases. On the topological invariant side, a natural candidate target for the translation is FO. Most of the results of the section concern the connection between the two languages. Before addressing this problem, we note however that the capture of ptime by xpoint + counting on topological invariants provides for free an e ective translation of topological FO(R; <) queries into xpoint + counting queries on the invariant ( xpoint su ces if the regions are connected). Also, this works in principle for other spatial languages whose topological fragments are in ptime. Perhaps more interesting is the fact that the translation into xpoint + counting ( xpoint) is quite e cient (which turns out not to be the case when the target is FO). We state this result next.

Theorem 4.1 Let Reg be a spatial database schema. There exists a mapping inv from FO top (R; <) sentences over Reg into xpoint + counting sentences over inv(Reg), such that:

1. for each ' 2 FO top (R; <) and each spatial instance I over Reg, '(I) = inv(')(top(I)).

2. inv(') is computable in linear time in the size of '.

Proof Suppose ' is a sentence in FO top (R; <) over schema Reg. The following procedure computes '(I) on input T = top(I):

1. Using a xpoint + counting query, de ne an isomorphic copy T N of T on the auxiliary ordered domain (as in the proof of Theorem 3.4).

2. Construct from T N a semi-linear instance J over Reg such that top(J) = T.

3. Evaluate ' on J and output the result (which recall is Boolean). We claim that (1)-(3) can be simulated by a xpoint + counting query inv(') constructible from ' in linear time. First, note that the xpoint + counting query in (1) is xed and can be constructed in constant time with respect to '. Consider (2)-(3). By Theorem 2.2, (2) can be done in ptime, and (3) can be done in ptime by KKR95]. Thus, steps (2) and (3) combined take ptime with respect to T N . Thus, there is a ptime Turing machine M ' that implements (2) and (3). Essentially, this is a Turing machine that performs step (2) (this is xed and independent of '), composed with a universal Turing machine for evaluating FO(R; <) formulas, to which ' is provided as parameter. Since the universal component is xed it is clear that M ' can be constructed in time linear with respect to '. Next, since T N is ordered and xpoint can simulate all ptime Turing machines on ordered domains, there exists a xpoint query (M ' ) that simulates M ' on input T N . The standard construction used in the simulation of ptime Turing machines by xpoint produces a xpoint formula whose size is linear in the size of the Turing machine (e.g., see AHV95]). Thus, (M ' ) can be constructed in linear time with respect to M ' and therefore with respect to '. Altogether, the composition of the xpoint + counting query in (1) with the xpoint query (M ' ) can be constructed in time linear in '.

If the regions are connected we can similarly show: Theorem 4.2 Let Reg be a spatial database schema. There exists a mapping inv from FO top (R; <) sentences over Reg into FO+ + sentences over inv(Reg), such that: The FO r (P; < x ; < y ) game on nice(cones(I)) and nice(cones(J)) is now played as in Lemma 4.6, with the additional complication of having to choose a cone at each move. However, this is easy: if Spoiler plays in the k-th cone of type of which there are fewer than 2 r cones, Duplicator responds in the k-th cone of the same type (recall that by the de nition of ' r , cycles(I) and cycles(J) have in this case the same number of cycles of type ). If there are more than 2 r cones of type , then Duplicator picks a cone according to the winning strategy for the FO r game on orders of length 2 r (the order of cones of type with respect to < x ). With the cone properly selected, the winning strategy is the same as in the single cone case described in Lemma 4.6. Lemma 4.7 suggests a way to translate FO r top (P; < x ; < y ) sentences into FO inv sentences. Indeed, it follows from the lemma that the set of invariants of instances satisfying an FO r top (P; < x ; < y ) sentence ' is a union of equivalence classes of ' r on their cycles. Note that there are nitely many such equivalence classes and each can be de ned by an FO inv formula. For each equivalence class of ' r let be the FO inv formula de ning , i.e. cycles(I) j = i cycles(I) belongs to . If I j = ' for each I such that cycles(I) 2 , we say that satis es '. Let T be the set of equivalence classes of ' r satisfying '. The translation of ' into FO inv is the sentence

( cycles ):

(Recall from Lemma 4.5 that cycles is the FO inv formula de ning cycles(I) from top(I)). From the earlier remarks it follows that '(I) = inv(')(top(I)) for every spatial instance I.

The above shows that each FO r top (P; < x ; < y ) sentence ' has a corresponding sentence inv(') in FO inv .

In order to e ectively compute inv(') one needs to compute the set T of equivalence classes of ' r satisfying '. To this end, it su ces to do the following for each equivalence class :

(i) construct a cone instance I such that cycles(I ) is in ;

(ii) check whether I j = '. If the answer to (ii) is positive, then 2 T . Clearly, verifying (ii) presents no problem once I is constructed.

The following lemma addresses (i), which is less simple. Lemma 4.8 Given a class of ' r one can e ectively construct a cone instance I such that cycles(I ) is in .

Proof Recall that each equivalence class of ' r is characterized by the multiset of (r + 2)-types of the individual cycles, with the multiplicity truncated to 2 r . Since a cone instance I such that cycles(I ) is in is essentially a union of cone instances of single cycles of appropriate (r+2)-types, it is su cient to show how to construct I when is an (r + 2)-type of a single cycle. Furthermore, because an (r + 2)-type describes a cycle and its image obtained by reversing the orientation, we can assume that the orientation is xed and construct an instance for the corresponding (r + 1)-type.

Thus, let be an (r + 1)-type of a single colored cycle. To construct a cycle of type (if such exists), it is useful to notice a strong connection between (r + 1)-types of colored cycles and r-types of words over the alphabet consisting of the two colors. Indeed, following the choice of the rst nodes in an (r+1)-game on two colored cycles, the remainder r-game is essentially played on the words obtained by going around the cycles starting from the nodes picked in the rst move. Given a colored cycle with an orientation, let us say that a word on the alphabet of colors is compatible with the cycle if it is obtained by walking around the cycle in the given orientation, starting from some node. For a cycle c, let L(c) be the set of words compatible with c, and for a class of cycles , let L( ) = S c2 L(c). Clearly, there exists a cycle of type i L( ) 6 = ;. We will show that L( ) is regular and provide a way to compute a regular expression for it. Then it is possible to test non-emptiness of L( ), and if L( ) 6 = ; produce a word in L( ) (which yields a cycle of type ).

Note that an (r + 1)-type of colored cycles determines the set of r-types of words compatible with such cycles. It well known that there are nitely many r-types of words over a xed alphabet, and the r-equivalence classes are precisely the regular star-free languages of dot-depth r RS97]. Furthermore, the number of such Practical considerations In what circumstances is translation a viable option? Suppose we have to evaluate an FO top (R; <) query ' on a spatial instance I (over a single region name). We have to compare the following evaluation strategies:

(i) evaluate ' on I using classical quanti er elimination techniques; the complexity is ptime in I and 2-exptime in the quanti er depth of '.

(ii) translate ' into inv(') 2 FO inv and evaluate inv(') on top(I). The complexity is ptime in top(I)

and hyperexponential in the quanti er depth of '.

(iii) translate ' into inv(') 2 FO + + and evaluate inv(') on top(I). The complexity is ptime in top(I)

and pspace in '. Clearly, the above information is not conclusive. How direct evaluation compares to translation into FO inv or FO + + followed by evaluation on the invariant depends critically on how much smaller top(I) is compared to I. The gap can be arbitrarily large, so in principle translation can win, although (ii) is likely to be prohibitively expensive due to the hyperexponential complexity in the quanti er depth. At this point it becomes useful to examine real data, in order to gauge how top(I) compares to I in realistic settings.

To this end, we examined cartographic data from the Sequoia 2000 project Seq] and the French National Geographical Institute IGN]. A rst set from Sequoia 2000 contains cartographic data on ground occupancy in California (agricultural land, range land, forests, lakes, bays, estuaries, wetlands, beaches and tundra). The original data is represented by 31,778 polygons stored as a list of 2,557,071 points taking 20 bytes each. The corresponding topological invariant has 190,045 cells taking 3 bytes each, which is 1/90 of the original data. A second set from Sequoia 2000 contains data on rivers, lakes and estuaries and contains 3410 polygons with 135,527 points at 20 bytes each. The invariant has 4,570 cells at 2 bytes each, which is 1/300 of the raw data. Data from the French National Geographical Institute contains cartographic data on the city of Orange (France) and surroundings. It consists of 145 polygons with 11,916 points at 18 bytes each. The topological invariant has 1,487 cells at 2 bytes each (1/72 of the original data).

As it turns out, other characteristics of data may also make translation viable. In cartographic data, it is reasonable to assume that there is a constant bound on the number of lines intersecting at the same point. In the data sets mentioned above, the average number of lines intersecting at a point is 4.5 for both, with maxima of 12 for Sequoia 2000 and 8 for the French National Geographical Institute data. If a constant bound is assumed, then the overall complexity of option (ii) (evaluation via translation to FO inv ) goes down to polynomial in top(I) and 2-exptime in the quanti er depth of '. This wins over direct evaluation, which is polynomial in I rather than top(I). The same complexity is obtained in the case of fully two-dimensional 8 regions. These are regions equal to the closure of their interior; in other words, the only edges and vertices occur on boundaries of faces.

We examined two possibilities for the targets of the translation of FO top (R; <) queries: (ii) FO inv and (iii) FO + + . On the face of it, the complexity of the translation and overall query evaluation seems to favor (iii). However, there is a caveat: the stated complexities of the translation and evaluation hide large constants. Nonetheless, (iii) seems likely to win over (ii), assuming that a recursive query evaluation engine evaluating the xpoint queries on the invariant is available.

Lastly, another option of practical interest is to avoid query translation altogether by using the following strategy for evaluating ' on input I: (iv) construct a standard linear instance I 0 such that top(I 0 ) = top(I) and evaluate ' on I 0 . The instance I 0 can be evaluated from top(I) in ptime, by Theorem 2.2. Altogether, I 0 can be constructed from I in ptime. Note that the size of I 0 is roughly the same as the size of top(I). Thus, maintaining the simpli ed linear instance I 0 as an annotation instead of top(I) combines the advantage of avoiding query translation with evaluation on a smaller input. Note however that the only algorithm known at this point for constructing I 0 is via the topological invariant. We plan to evaluate option (iv) experimentally in future work.

8 Term introduced by B. Kuijpers and J. Van Den Bussche.