Victor Vianu

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 relationships between regions intuitively, those that pertain to adjacency and connectivity properties of the regions, and are therefore 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 queries targeted towards topological information for two-dimensional spatial databases, where regions are 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 languages geared towards topological queries, building upon well-known topological relationships between pairs of planar regions proposed by Egenhofer.

In regard to (ii), we show that the topological information in a spatial database can be precisely summarized by a finite relational database 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, it is shown that fixpoint expresses precisely the PTIME queries on topological invariants. This suggests that topological invariants are particularly well- behaved with respect to descriptive complexity.

This talk is based on joint work with C.H. Papadimitriou, D. Suciu and L. Segoufin.