A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator

Summary: Dichotomy for NRC(Q,+,·,-,÷,Σ,powerset): on structures like long chains and deep trees, queries are either definable without powerset or require exponential space. Generalizes prior exponential lower bounds to SQL‑capturing calculi and to languages with a normal form and locality. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1593
Venue: PODS
Year: 2013
Pagerank: -
Overall Rank: 13,419 | 6.65%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

1. Limsoon Wong

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,110	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	9.5315487e-05
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
7,248	Positive Higher-Order Queries	2010	PODS	4.7902631e-05
14,281	EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract)	1984	SIGMOD	-
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
1,741	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010714223
5,974	A Query Language for NC	1994	PODS	5.246329e-05
8,704	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4647149e-05
7,782	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	4.6523963e-05
2,800	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	8.1019352e-05