Database Paper Browser

Back to papers

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
987
Venue
PODS
Year
1993
Pagerank
8.5701687e-05
Overall Rank
2,546 | 82.29%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 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
1,421 Algorithms for Deferred View Maintenance 1996 SIGMOD 0.0001205793
4,285 A Query Language for List-Based Complex Objects 1994 PODS 6.2913523e-05
4,611 On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values 2005 PODS 6.0488752e-05
6,539 On the Power of Algebras with Recursion 1993 SIGMOD 5.02287e-05
7,782 New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions 1994 PODS 4.6523963e-05
12,799 Normalizing Incomplete Databases 1995 PODS 4.1945683e-05
12,828 Tutorial: Languages for Collection Types 1994 PODS 4.1945683e-05
Previous Page 1 / 1 Next

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
445 The Magic of Duplicates and Aggregates 1990 VLDB 0.0002294367
603 A Data Model and Query Language for EXODUS 1988 SIGMOD 0.00019351031
837 An Extended Relational Algebra with Control Over Duplicate Elimination 1982 PODS 0.00016097758
2,395 Algebraic Properties of Bag Data Types 1991 VLDB 8.8998019e-05
2,515 Untyped Sets, Invention, and Computable Queries 1989 PODS 8.6128871e-05
2,553 Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions 1988 PODS 8.5500139e-05
2,800 On the Expressive Power of Database Queries with Intermediate Types 1988 PODS 8.1019352e-05
3,040 Tractable Query Languages for Complex Object Databases 1991 PODS 7.6707607e-05
3,364 Multirelations - Semantics and Languages 1985 VLDB 7.1731086e-05
4,381 Functional and Predicative programming in OODB's 1992 PODS 6.2389434e-05
4,894 The Expressive Power of Structured Values in Pure OODB's (extended abstract) 1991 PODS 5.8477088e-05
6,539 On the Power of Algebras with Recursion 1993 SIGMOD 5.02287e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,828 Tutorial: Languages for Collection Types 1994 PODS 4.1945683e-05
8,704 Equivalence of Nested Queries with Mixed Semantics 2009 PODS 4.4647149e-05
2,800 On the Expressive Power of Database Queries with Intermediate Types 1988 PODS 8.1019352e-05
2,110 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD 9.5315487e-05
2,553 Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions 1988 PODS 8.5500139e-05
5,871 Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract) 1998 PODS 5.2943906e-05
13,419 A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator 2013 PODS -
7,782 New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions 1994 PODS 4.6523963e-05
3,392 The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra 1988 SIGMOD 7.1485699e-05
2,395 Algebraic Properties of Bag Data Types 1991 VLDB 8.8998019e-05