Topological queries in spatial databases

We study query language for topological properties of twodimensional spatial databases, starting from the topological relationships between pairs of planar regions introduced by Egenhofer and Franzosa. We show that the closure of theserelationships under appropriate logical operators yields languages which are complete for topological properties. This provides a theoretical a posterior justification for the choice of these particular relationships. Unlike the pointbased 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 rangee 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. Finally we show that each set of semi-algebraic regions is characterized up to homeomorphism by an invariant representable as a finite structure, computable in NC'. This allows to answer all topological queries on semi-algebraic regions 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 regions.