Querying spatial databases via topological invariants

The paper investigates the use of topological annotations (called topologic al invariants) to answer topological queries in spatial databases. The focu s is on the translation of topological queries against the spatial database into queries against the topological invariant. The languages considered a re first-order on the spatial database side, and fixpoint + counting, fixpo int, and first-order on the topological invariant side. In particular, it i s shown that fixpoint + counting expresses precisely all the PTME queries o n topological invariants; if the regions are connected, fixpoint expresses all PTIME queries on topological invariants. (C) 2000 Academic Press.