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
h031fb572fdbd44ab
Venue
PODS
Year
1996
Pagerank
7.0297786e-05
Overall Rank
3,771 | 74.65%
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,640 Exact and Approximate Aggregation in Constraint Query Languages 1999 PODS 6.4903073e-05
5,429 Querying Spatial Databases via Topological Invariants 1998 PODS 6.1337552e-05
8,220 Complete geometrical query languages (extended abstract) 1997 PODS 5.3761403e-05
13,164 Reachability and Connectivity Queries in Constraint Databases 2000 PODS 4.9793485e-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
914 Constraint Programming and Database Languages: A Tutorial 1995 PODS 0.00013104061
1,512 Towards a Theory of Spatial Database Queries (Extended Abstract) 1994 PODS 0.00010429539
1,950 Relational Expressive Power of Constraint Query Languages 1996 PODS 9.3195393e-05
2,292 Finitely Representable Databases 1994 PODS 8.6854411e-05
5,658 Dense-Order Constraint Databases (Extended Abstract) 1995 PODS 6.0482089e-05
Previous Page 1 / 1 Next

Semantically Similar Papers