DBScholar

Back to papers

Topological Queries in Spatial Databases

Summary: Region-based languages from Egenhofer–Franzosa relations are expressively complete for 2D topological properties and range in complexity from NC to undecidable. The NC fragment matches point-based expressiveness, and semi-algebraic regions admit NC-computable finite invariants (and polygonal reps), so topological queries reduce to finite-structure queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1078
Venue
PODS
Year
1996
Pagerank
7.1911058e-05
Overall Rank
3,695 | 74.66%
DOI
10.1145/237661.237683

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{papadimitriou_pods96,
        address = {New York, NY, USA},
        series = {{PODS} '96},
        title = {{Topological Queries in Spatial Databases}},
        url = {https://dl.acm.org/doi/10.1145/237661.237683},
        doi = {10.1145/237661.237683},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Papadimitriou, Christos H. and Suciu, Dan and Vianu, Victor},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank Citing Paper Year Venue Pagerank
4,543 Exact and Approximate Aggregation in Constraint Query Languages 1999 PODS 6.6388258e-05
5,303 Querying Spatial Databases via Topological Invariants 1998 PODS 6.2745166e-05
8,052 Complete geometrical query languages (extended abstract) 1997 PODS 5.4995351e-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 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
889 Constraint Programming and Database Languages: A Tutorial 1995 PODS 0.00013398105
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
2,241 Finitely Representable Databases 1994 PODS 8.8845324e-05
5,523 Dense-Order Constraint Databases (Extended Abstract) 1995 PODS 6.1870017e-05
Previous Page 1 / 1 Next

Semantically Similar Papers