DBScholar

Back to papers

Reachability and Connectivity Queries in Constraint Databases

Summary: Augments standard constraint-query languages (FO+Lin, FO+Poly) with topological predicates to obtain closed languages that can express connectivity and reachability. Introduces Path Logic: closed, PTIME data complexity for linear/polynomial constraints, expresses rich path properties via discrete abstractions of continuous paths. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1199
Venue
PODS
Year
2000
Pagerank
5.093636e-05
Overall Rank
12,874 | 11.68%
DOI
10.1145/335168.335213

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

BibTeX Citation

@inproceedings{benedikt_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Reachability and Connectivity Queries in Constraint Databases}},
        url = {https://dl.acm.org/doi/10.1145/335168.335213},
        doi = {10.1145/335168.335213},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Benedikt, Michael and Grohe, Martin and Libkin, Leonid and Segoufin, Luc},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank Citing Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank Cited Paper Year Venue Pagerank
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
5,303 Querying Spatial Databases via Topological Invariants 1998 PODS 6.2745166e-05
Previous Page 1 / 1 Next

Semantically Similar Papers