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 rst-order 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.