On First-Order Topological Queries

Martin Grohe (1) , Luc Segoufin (2)

1 Edin. - University of Edinburgh
2 VERSO - Databases

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.

Domaines: Informatique et langage [cs.CL]

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