We study topological queries over two-dimensional spatial databases. First, we show that the topological properties of semi- algebraic 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 semi- algebraic 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 two- dimensional spatial databases, starting from the topological rela- tionships 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 proper- ties. 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.
展开▼
