Database Paper Browser

Back to papers

Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions

Summary: Nested algebra with the nest operator has no extra expressiveness over ordinary relational algebra for queries with flat inputs and flat outputs. Implications: transitive closure remains inexpressible; powerset (not nest) yields strictly more power; provide rewritings to maximize flat operators. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
813
Venue
PODS
Year
1988
Pagerank
8.541561e-05
Overall Rank
2,560 | 82.21%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
1,781 Normal Forms and Conservative Properties for Query Languages over Collection Types 1993 PODS 0.00010557953
2,520 Untyped Sets, Invention, and Computable Queries 1989 PODS 8.6044305e-05
2,546 Towards Tractable Algebras for Bags (Extended Abstract) 1993 PODS 8.5606179e-05
2,808 On the Expressive Power of Database Queries with Intermediate Types 1988 PODS 8.0939851e-05
3,043 Tractable Query Languages for Complex Object Databases 1991 PODS 7.6632326e-05
3,392 The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra 1988 SIGMOD 7.1418515e-05
4,411 An Implementation for Nested Relational Databases 1988 VLDB 6.2005552e-05
4,612 On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values 2005 PODS 6.0428289e-05
5,980 A Query Language for NC 1994 PODS 5.241279e-05
7,147 Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure 1994 PODS 4.8131534e-05
7,554 Storing and Querying Tree-Structured Records in Dremel 2014 VLDB 4.7079131e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank Cited Paper Year Venue Pagerank
93 Remarks on the Algebra of Non First Normal Form Relations 1982 PODS 0.00051290296
273 A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies 1986 SIGMOD 0.00029399666
443 A Calculus for Complex Objects 1986 PODS 0.00023059917
652 Logic Programming With Sets 1987 PODS 0.00018643929
910 Sets and Negation in a Logic Database Language (LDL1) 1987 PODS 0.00015398775
1,901 On Line Processing Of Compacted Relations 1982 VLDB 0.00010166949
2,299 Designing a Generalized NF2 Model with an SQL-Type Language Interface 1986 VLDB 9.0711063e-05
2,466 Supporting Flat Relations by a Nested Relational Kernel 1987 VLDB 8.734134e-05
2,568 Architecture and Implementation of the Darmstadt Database Kernel System 1987 SIGMOD 8.5205422e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,747 Determining When A Structure Is A Nested Relation 1985 VLDB 8.1818958e-05
93 Remarks on the Algebra of Non First Normal Form Relations 1982 PODS 0.00051290296
8,699 Equivalence of Nested Queries with Mixed Semantics 2009 PODS 4.4604187e-05
12,543 A Nested Relational Approach to Processing SQL Subqueries 2005 SIGMOD 4.1905499e-05
3,392 The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra 1988 SIGMOD 7.1418515e-05
6,672 Optimization of Nested Queries using the NF2 Algebra 2016 SIGMOD 4.9621566e-05
2,466 Supporting Flat Relations by a Nested Relational Kernel 1987 VLDB 8.734134e-05
13,432 A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator 2013 PODS -
2,546 Towards Tractable Algebras for Bags (Extended Abstract) 1993 PODS 8.5606179e-05
2,109 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD 9.5283567e-05