Towards Tractable Algebras for Bags (Extended Abstract)

Summary: Extends the nested-relation algebra to bags and analyzes how duplicates and nesting depth change expressive power and complexity. Proves bag algebra strictly more expressive than nested relations at all nesting depths and establishes an expression-structure hierarchy linked to powerset properties. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 986
Venue: PODS
Year: 1993
Pagerank: 8.550394e-05
Overall Rank: 2,461 | 83.12%
DOI: 10.1145/153850.153855

Incoming Non-self Citations Over Time

Authors

1. Stéphane Grumbach (INRIA)
2. Tova Milo (University of Toronto)

BibTeX Citation

@inproceedings{grumbach_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Towards Tractable Algebras for Bags (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/153850.153855},
        doi = {10.1145/153850.153855},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Grumbach, Stéphane and Milo, Tova},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
375	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00019681204
1,133	Algorithms for Deferred View Maintenance	1996	SIGMOD	0.00012039326
1,434	A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques	1996	SIGMOD	0.00010800479
4,467	A Query Language for List-Based Complex Objects	1994	PODS	6.6843364e-05
4,702	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.5549225e-05
7,260	On the Power of Algebras with Recursion	1993	SIGMOD	5.6612789e-05
7,849	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	5.5324391e-05
12,993	Normalizing Incomplete Databases	1995	PODS	5.093636e-05
13,022	Tutorial: Languages for Collection Types	1994	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
527	The Magic of Duplicates and Aggregates	1990	VLDB	0.00017108864
684	A Data Model and Query Language for EXODUS	1988	SIGMOD	0.00014990873
1,095	An Extended Relational Algebra with Control Over Duplicate Elimination	1982	PODS	0.00012207515
2,400	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.6299917e-05
2,423	Algebraic Properties of Bag Data Types	1991	VLDB	8.6016807e-05
2,701	Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions	1988	PODS	8.240179e-05
2,897	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.9790527e-05
2,986	Tractable Query Languages for Complex Object Databases	1991	PODS	7.8912631e-05
3,420	Multirelations -- Semantics and Languages	1985	VLDB	7.4283042e-05
4,422	Functional and Predicative programming in OODB's	1992	PODS	6.7128479e-05
4,934	The Expressive Power of Structured Values in Pure OODB's (extended abstract)	1991	PODS	6.4357823e-05
7,260	On the Power of Algebras with Recursion	1993	SIGMOD	5.6612789e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,569	On The Expressive Power Of The Extended Relational Algebra For The Unnormalized Relational Model	1987	PODS
2	8,971	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
3	2,897	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS
4	2,198	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD
5	2,701	Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions	1988	PODS
6	6,319	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS
7	13,620	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS
8	7,849	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS
9	3,564	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD
10	2,423	Algebraic Properties of Bag Data Types	1991	VLDB