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.5500139e-05
Overall Rank: 2,553 | 82.25%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jan Paredaens
2. Dirk Van Gucht

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,783	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	0.00010568101
2,515	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.6128871e-05
2,546	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.5701687e-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,392	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD	7.1485699e-05
4,411	An Implementation for Nested Relational Databases	1988	VLDB	6.2071929e-05
4,611	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.0488752e-05
5,974	A Query Language for NC	1994	PODS	5.246329e-05
7,146	Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure	1994	PODS	4.8177747e-05
7,554	Storing and Querying Tree-Structured Records in Dremel	2014	VLDB	4.712434e-05

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
97	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.0005080702
272	A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies	1986	SIGMOD	0.00029426313
440	A Calculus for Complex Objects	1986	PODS	0.00023084404
649	Logic Programming With Sets	1987	PODS	0.00018662857
912	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS	0.00015414126
1,898	On Line Processing Of Compacted Relations	1982	VLDB	0.00010175799
2,294	Designing a Generalized NF2 Model with an SQL-Type Language Interface	1986	VLDB	9.0795264e-05
2,468	Supporting Flat Relations by a Nested Relational Kernel	1987	VLDB	8.7416405e-05
2,561	Architecture and Implementation of the Darmstadt Database Kernel System	1987	SIGMOD	8.5400984e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,744	Determining When A Structure Is A Nested Relation	1985	VLDB	8.1896577e-05
97	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.0005080702
8,704	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4647149e-05
12,534	A Nested Relational Approach to Processing SQL Subqueries	2005	SIGMOD	4.1945683e-05
3,392	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD	7.1485699e-05
6,672	Optimization of Nested Queries using the NF2 Algebra	2016	SIGMOD	4.9669223e-05
2,468	Supporting Flat Relations by a Nested Relational Kernel	1987	VLDB	8.7416405e-05
13,419	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.5701687e-05
2,110	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	9.5315487e-05