Topological queries in spatial databases

We study topological queries over two-dimensional spatial databases. First, we show that the topological properties of semialgebraic spatial regions c an be completely specified using a classical finite structure, essentially the embedded planar graph of the region boundaries. This provides an invari ant characterizing semi-algebraic regions up to homeomorphism. All topologi cal queries on semialgebraic regions can be answered by queries on the inva riant whose complexity is polynomially related to the original. Also, we sh ow that for the purpose of answering topological queries, semi-algebraic re gions can always be represented simply as polygonal regions. We then study query languages for topological properties of two-dimensional spatial datab ases, starting from the topological relationships between pairs of planar r egions introduced by Egenhofer, We show that the closure of these relations hips under appropriate logical operators yields languages which are complet e for topological properties. This provides a theoretical a posteriori just ification for the choice of these particular relationships. Unlike the poin t-based languages studied in previous work on constraint databases, our lan guages are region based-quantifiers range over reg ions in the plane. This yields a family of languages, whose complexity ranges from NC to undecidabl e. Another type of completeness result shows that the region-based language of complexity NC expresses precisely the same topological properties as we ll-known point-based languages. (C) 1999 Academic Press.