We study topological queries over two-dimensional spatial databases. First, we show that the topological properties of semialgebraic spatial regions can be completely specified using a classical finite structure, essentially the embedded planar graph of the region boundaries. This provides an invariant characterizing semi-algebraic regions up to homeomorphism. All topological queries on semialgebraic regions can be answered by queries on the invariant whose complexity is polynomially related to the original. Also, we show that for the purpose of answering topological queries, semi-algebraic regions can always be represented simply as polygonal regions.
We then study query languages for topological properties of twodimensional spatial databases, starting from the topological relationships between pairs of planar regions introduced by Egenhofer. We show that the closure of these relationships under appropriate logical operators yields languages which are complete for topological properties. This provides a theoretical a posteriori justification for the choice of these particular relationships. Unlike the point-based languages studied in previous work on constraint databases, our languages are region based quantifiers range over regions in the plane. This yields a family of languages, whose complexity ranges from NC to undecidable. Another type of completeness result shows that the region-based language of complexity NC expresses precisely the same topological properties as well-known point-based languages.