DBScholar

Back to papers

Relational Expressive Power of Constraint Query Languages

Summary: Shows recursive queries (parity, transitive closure) are inexpressible in relational calculus with polynomial inequalities over R. Establishes collapse: generic Boolean queries with many constraint classes collapse to the constraint-free relational calculus under both active-domain and natural semantics, using Ramsey-type combinatorics and nonstandard/model-theoretic methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1071
Venue
PODS
Year
1996
Pagerank
9.5330753e-05
Overall Rank
1,890 | 87.04%
DOI
10.1145/237661.237667

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{benedikt_pods96,
        address = {New York, NY, USA},
        series = {{PODS} '96},
        title = {{Relational Expressive Power of Constraint Query Languages}},
        url = {https://dl.acm.org/doi/10.1145/237661.237667},
        doi = {10.1145/237661.237667},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Benedikt, Michael and Dong, Guozhu and Libkin, Leonid and Wong, Limsoon},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
3,544 On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract) 1997 PODS 7.3264444e-05
3,695 Topological Queries in Spatial Databases 1996 PODS 7.1911058e-05
4,013 Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract) 1996 PODS 6.9565842e-05
4,203 An Expressive Language for Linear Spatial Database Queries (extended abstract) 1998 PODS 6.8354052e-05
4,226 Safe Constraint Queries 1998 PODS 6.8211482e-05
4,336 Languages for Relational Databases over Interpreted Structures 1997 PODS 6.7554436e-05
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
5,475 Verifiable Properties of Database Transactions 1996 PODS 6.205309e-05
5,736 On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) 1997 PODS 6.1050534e-05
5,895 The 3W Model and Algebra for Unified Data Mining 2000 VLDB 6.0486927e-05
8,559 Towards Practical Constraint Databases (Extended Abstract) 1996 PODS 5.4119882e-05
11,828 Personal Insights for Altering Decisions of Tree-based Ensembles over Time 2020 VLDB 5.093636e-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
12,879 Uniform Generation in Spatial Constraint Databases and Applications 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.

Previous Page 1 / 1 Next

Semantically Similar Papers