Skip to Main content Skip to Navigation
Journal articles

Querying Spatial Databases via Topological Invariants

Abstract : The paper investigates the use of topological annotations (called topological invariants) to answer topological queries in spatial databases. The focus is on the translation of topological queries against the spatial database into queries against the topological invariant. The languages considered are first-order on the spatial database side, and fixpoint + counting, fixpoint, and first-order on the topological invariant side. In particular, it is shown that fixpoint + counting expresses precisely all the ptime queries on topological invariants; if the regions are connected, fixpoint expresses all ptime queries on topological invariants.
Document type :
Journal articles
Complete list of metadata

Cited literature [50 references]  Display  Hide  Download

https://hal.inria.fr/hal-01128308
Contributor : Luc Segoufin <>
Submitted on : Monday, March 9, 2015 - 2:58:38 PM
Last modification on : Wednesday, August 7, 2019 - 12:18:05 PM
Long-term archiving on: : Wednesday, June 10, 2015 - 4:06:11 PM

File

topo-inv.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01128308, version 1

Citation

Luc Segoufin, Victor Vianu. Querying Spatial Databases via Topological Invariants. Journal of Computer and System Sciences, Elsevier, 2000, 61 (2), pp.32. ⟨hal-01128308⟩

Share

Metrics

Record views

84

Files downloads

294