Victor Vianu Computer Science Engineering, UC San Diego, La Jolla, CA 92093-0114, USA vianu@cs.ucsd.edu Title: Topological Queries in Spatial Databases Handling spatial information is required by many database applications, and each poses different requirements on query languages. In many cases the precise size of the regions is important, while in other applications we may only be interested in the TOPOLOGICAL properties of regions, which are invariant under homeomorphisms. Such differences in scope and emphasis are crucial, as they affect the data model, the query language, and performance. This talk focuses on logics targeted towards topological properties of two-dimensional regions specified by polynomial inequalities with integer coefficients. We focus on two main aspects: (i) languages for expressing topological queries, and (ii) the representation of topological information. In regard to (i), we study several region-based variations of first-order logic, which use as basic predicates well-known topological relationships between pairs of planar regions. In regard to (ii), we show that the topological information in a spatial database can be precisely summarized by a finite structure which can be viewed as a topological annotation to the raw spatial data. All topological queries can be answered using this annotation, called topological invariant. This yields a potentially more economical evaluation strategy for such queries, since the topological invariant is generally much smaller than the raw data. We examine in detail the problem of translating topological queries against the spatial database into queries against the topological invariant. The languages considered are first-order on the spatial database side, and fixpoint and first-order on the topological invariant side. In particular, fixpoint turns out to express precisely the PTIME queries on topological invariants. This suggests that topological invariants are particularly well-behaved with respect to descriptive complexity. These results parallel recent results in finite-model theory on the expressiveness of fixpoint logic over planar graphs.