Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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
Contributor : Luc Segoufin Connect in order to contact the contributor
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


Files produced by the author(s)


  • HAL Id : hal-01128308, version 1


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



Record views


Files downloads