Topological queries
In some applications the precise size of the regions is not important, but rather the topological relationships between them are of primary interest. This chapter of the book of \textit{G. Kuper}, \textit{L. Libkin} and \textit{J. Paradaens} (eds.) [Constraint databases (2000; Zbl 0935.00022)] presents a survey of results concerning topological queries in spatial databases -- it focuses on semi-algebraic regions in the two-dimensional plane. Three themas are studied: languages for expressing topological queries, representations of topological information by topological invariants, and using topological invariants to answer topological queries. The first part starts from the eight relationships between pairs of regions, based on the intersections of their interiors and boundaries, and exhibits their extensions by logical operators and quantification over regions. This yields a family of languages -- their completeness, expressiveness and complexity is studied. In the second part several proposals for representing topological information in spatial databases are presented based on one topological invariant that captures complete information for semi-algebraic regions, and can be computed efficiently. The topological invariant for a spatial instance is a finite structure consisting of relations Vertex, Edge, Face, Regions, Endpoints, Face-Edge, Face-Vertex and Between. As this invariant is an annotation summarizing precisely the topological properties of the spatial instance, all relevant queries can be answered by queries posed against the invariant rather then on the raw spatial data. In the last section two related problems are studied -- the identification of languages that can serve as a target for the translation of topological queries into queries against the invariant, and the existence of an effective translation of queries. For the entire collection see [Zbl 0935.00022].
- Topological queries in spatial databases
- A model for representing topological relationships between complex geometric features in spatial databases
- Querying spatial databases via topological invariants
- Towards a topological view of databases
- A characterization of first-order topological properties of planar spatial data
- scientific article; zbMATH DE number 2080410 (Why is no real title available?)
- A general strategy for decomposing topological invariants of spatial databases and an application
- Topological elementary equivalence of regular semi-algebraic sets in three-dimensional space
- On first-order topological queries
- Representation, reasoning and similar matching for detailed topological relations with DTString
This page was built for publication: Topological queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4508943)
