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.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2000, 61 (2), pp.32
Liste complète des métadonnées

Littérature citée [50 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01128308
Contributeur : Luc Segoufin <>
Soumis le : lundi 9 mars 2015 - 14:58:38
Dernière modification le : lundi 23 mars 2015 - 13:32:32
Document(s) archivé(s) le : mercredi 10 juin 2015 - 16:06:11

Fichier

topo-inv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

27

Téléchargements de fichiers

62