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,432 | 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,176	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	9.0846524e-05
527	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00017133432
7,573	Positive Higher-Order Queries	2010	PODS	5.6509472e-05
14,295	EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract)	1984	SIGMOD	-
4,274	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.8586833e-05
1,865	Relational Expressive Power of Constraint Query Languages	1996	PODS	9.680674e-05
5,765	A Query Language for NC	1994	PODS	6.1598109e-05
8,918	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.4078372e-05
7,725	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	5.6176017e-05
2,835	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	8.1173669e-05