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: 1026
Venue: PODS
Year: 1994
Pagerank: 5.5324391e-05
Overall Rank: 7,849 | 46.15%
DOI: 10.1145/182591.182609

Incoming Non-self Citations Over Time

Authors

1. Leonid Libkin (University of Pennsylvania)
2. Limsoon Wong (University of Pennsylvania)

BibTeX Citation

@inproceedings{libkin_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions}},
        url = {https://dl.acm.org/doi/10.1145/182591.182609},
        doi = {10.1145/182591.182609},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Libkin, Leonid and Wong, Limsoon},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
375	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00019681204
1,434	A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques	1996	SIGMOD	0.00010800479
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
8,971	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.3420194e-05
12,993	Normalizing Incomplete Databases	1995	PODS	5.093636e-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
309	Optimization of Real Conjunctive Queries	1993	PODS	0.00021768596
1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.5928463e-05
2,130	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	9.1244275e-05
2,461	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.550394e-05
2,986	Tractable Query Languages for Complex Object Databases	1991	PODS	7.8912631e-05
7,086	A Query Language for NC	1994	PODS	5.7073076e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,022	Tutorial: Languages for Collection Types	1994	PODS
2	11,525	Data Path Queries over Embedded Graph Databases	2022	PODS
3	2,461	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS
4	1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS
5	1,890	Relational Expressive Power of Constraint Query Languages	1996	PODS
6	2,130	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS
7	6,319	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS
8	8,971	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
9	13,620	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS
10	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS