New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions

Summary: New techniques show that graph properties definable in nested-collection query languages (set/bag semantics with aggregates) are finite or cofinite, settling that parity, TC and balanced-tree tests are inexpressible in bag/nested-relational languages. Prove a bounded-degree property for the nested-relational language that yields a uniform source of many inexpressibility results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1027
Venue: PODS
Year: 1994
Pagerank: 4.6523963e-05
Overall Rank: 7,782 | 45.87%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Leonid Libkin
2. Limsoon Wong

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
481	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00022167223
1,412	A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques	1996	SIGMOD	0.00012122159
4,709	Verifiable Properties of Database Transactions	1996	PODS	5.9795558e-05
5,709	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3602702e-05
8,704	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4647149e-05
12,799	Normalizing Incomplete Databases	1995	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027036073
1,783	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	0.00010568101
1,835	The Expressiveness of a Family of Finite Set Languages	1991	PODS	0.00010375854
2,546	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.5701687e-05
3,040	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6707607e-05
5,974	A Query Language for NC	1994	PODS	5.246329e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,828	Tutorial: Languages for Collection Types	1994	PODS	4.1945683e-05
11,326	Data Path Queries over Embedded Graph Databases	2022	PODS	4.1945683e-05
2,546	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.5701687e-05
1,835	The Expressiveness of a Family of Finite Set Languages	1991	PODS	0.00010375854
1,741	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010714223
1,783	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	0.00010568101
5,871	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS	5.2943906e-05
8,704	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4647149e-05
13,419	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS	-
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05