Querying Spatial Databases via Topological Invariants
Summary: Use topological invariants as compact annotations to answer topological queries by translating spatial FO queries into queries over the invariant. Show that fixpoint logic precisely captures PTIME on these invariants and provide FO/fp translation results. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Luc Segoufin (INRIA)
- 2. Victor Vianu (University of California San Diego)
BibTeX Citation
@inproceedings{segoufin_pods98,
address = {New York, NY, USA},
series = {{PODS} '98},
title = {{Querying Spatial Databases via Topological Invariants}},
url = {https://dl.acm.org/doi/10.1145/275487.275498},
doi = {10.1145/275487.275498},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Segoufin, Luc and Vianu, Victor},
year = {1998}
}
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,543 | Exact and Approximate Aggregation in Constraint Query Languages | 1999 | PODS | 6.6388258e-05 |
| 12,763 | A characterization of first-order topological properties of planar spatial data (Extended abstract) | 2004 | PODS | 5.093636e-05 |
| 12,874 | Reachability and Connectivity Queries in Constraint Databases | 2000 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 650 | The Sequoia 2000 Storage Benchmark | 1993 | SIGMOD | 0.00015319951 |
| 1,473 | Towards a Theory of Spatial Database Queries (Extended Abstract) | 1994 | PODS | 0.0001066845 |
| 1,890 | Relational Expressive Power of Constraint Query Languages | 1996 | PODS | 9.5330753e-05 |
| 3,695 | Topological Queries in Spatial Databases | 1996 | PODS | 7.1911058e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,544 | On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract) | 1997 | PODS |
| 2 | 3,290 | Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees | 1995 | SIGMOD |
| 3 | 3,581 | Time-Parameterized Queries in Spatio-Temporal Databases | 2002 | SIGMOD |
| 4 | 12,763 | A characterization of first-order topological properties of planar spatial data (Extended abstract) | 2004 | PODS |
| 5 | 12,874 | Reachability and Connectivity Queries in Constraint Databases | 2000 | PODS |
| 6 | 8,052 | Complete geometrical query languages (extended abstract) | 1997 | PODS |
| 7 | 12,875 | Fixed-Point Query Languages for Linear Constraint Databases | 2000 | PODS |
| 8 | 1,473 | Towards a Theory of Spatial Database Queries (Extended Abstract) | 1994 | PODS |
| 9 | 12,876 | Linear approximation of planar spatial databases using transitive-closure logic | 2000 | PODS |
| 10 | 3,695 | Topological Queries in Spatial Databases | 1996 | PODS |