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 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. 1 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. Different applications pose different 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 ..