Skip to Main content Skip to Navigation
Journal articles

On First-Order Topological Queries

Martin Grohe 1 Luc Segoufin 2
2 VERSO - Databases
Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8629
Abstract : One important class of spatial database queries is the class of topological queries, that is, queries invariant under homeomorphisms. We study topological queries expressible in the standard query language on spatial databases, rst-order logic with various amounts of arithmetic. Our main technical result is a combinato-rial characterization of the expressive power of topological rst-order logic on regular spatial databases.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01223388
Contributor : Luc Segoufin <>
Submitted on : Monday, November 2, 2015 - 3:37:19 PM
Last modification on : Friday, May 25, 2018 - 12:02:04 PM
Long-term archiving on: : Wednesday, February 3, 2016 - 10:53:07 AM

File

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

Identifiers

Collections

Citation

Martin Grohe, Luc Segoufin. On First-Order Topological Queries. ACM Transactions on Computational Logic, Association for Computing Machinery, 2002, 3 (3), ⟨10.1145/507382.507384⟩. ⟨hal-01223388⟩

Share

Metrics

Record views

159

Files downloads

192