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: 1072
Venue: PODS
Year: 1996
Pagerank: 0.00010714223
Overall Rank: 1,741 | 87.89%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,357	Topological Queries in Spatial Databases	1996	PODS	8.9617862e-05
2,851	On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)	1997	PODS	8.0155027e-05
3,784	Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract)	1996	PODS	6.7697677e-05
3,890	Querying Spatial Databases via Topological Invariants	1998	PODS	6.6604161e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
4,369	An Expressive Language for Linear Spatial Database Queries (extended abstract)	1998	PODS	6.2487721e-05
4,379	Safe Constraint Queries	1998	PODS	6.2397591e-05
4,709	Verifiable Properties of Database Transactions	1996	PODS	5.9795558e-05
4,723	Exact and Approximate Aggregation in Constraint Query Languages	1999	PODS	5.9714196e-05
5,276	The 3W Model and Algebra for Unified Data Mining	2000	VLDB	5.5905507e-05
5,709	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3602702e-05
8,323	Towards Practical Constraint Databases (Extended Abstract)	1996	PODS	4.5435639e-05
11,634	Personal Insights for Altering Decisions of Tree-based Ensembles over Time	2020	VLDB	4.1945683e-05
12,570	A characterization of first-order topological properties of planar spatial data (Extended abstract)	2004	PODS	4.1945683e-05
12,681	Reachability and Connectivity Queries in Constraint Databases	2000	PODS	4.1945683e-05
12,686	Uniform Generation in Spatial Constraint Databases and Applications	2000	PODS	4.1945683e-05

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
620	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00019005954
1,415	Towards a Theory of Spatial Database Queries (Extended Abstract)	1994	PODS	0.0001211468
1,649	Finitely Representable Databases	1994	PODS	0.00011017687
1,783	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	0.00010568101
3,784	Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract)	1996	PODS	6.7697677e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
7,782	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	4.6523963e-05
1,835	The Expressiveness of a Family of Finite Set Languages	1991	PODS	0.00010375854
12,682	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS	4.1945683e-05
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
13,419	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS	-
4,778	Dense-Order Constraint Databases (Extended Abstract)	1995	PODS	5.9290535e-05
7,248	Positive Higher-Order Queries	2010	PODS	4.7902631e-05
4,379	Safe Constraint Queries	1998	PODS	6.2397591e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05