Topological queries in spatial databases
Christos H. Papadimitriou, Dan Mircea Suciu, Victor Vianu · 1996
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. IntroductionThe manipulation of represented simply as polygonal spatial data is art increasingly important part of database systems.Spatial data is involved in a wide range of applications: geographic information systems, video databases, medical imaging,