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: hdc0e187e51dab97c
Venue: PODS
Year: 1988
Pagerank: 8.0523904e-05
Overall Rank: 2,751 | 81.52%
DOI: 10.1145/308386.308402

Incoming Non-self Citations Over Time

Authors

1. Jan Paredaens (University of Antwerp)
2. Dirk Van Gucht (Indiana University)

BibTeX Citation

@inproceedings{paredaens_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions}},
        url = {https://dl.acm.org/doi/10.1145/308386.308402},
        doi = {10.1145/308386.308402},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Paredaens, Jan and Van Gucht, Dirk},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,171	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	8.9205772e-05
2,457	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.4335382e-05
2,515	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.3605462e-05
2,970	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.7976956e-05
3,047	Tractable Query Languages for Complex Object Databases	1991	PODS	7.7108309e-05
3,630	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD	7.1471847e-05
4,810	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.4049669e-05
5,384	An Implementation for Nested Relational Databases	1988	VLDB	6.153286e-05
7,234	A Query Language for NC	1994	PODS	5.576635e-05
7,487	Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure	1994	PODS	5.5102404e-05
7,547	Storing and Querying Tree-Structured Records in Dremel	2014	VLDB	5.4962678e-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
140	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.00029333191
354	A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies	1986	SIGMOD	0.00020212701
486	A Calculus for Complex Objects	1986	PODS	0.00017463801
828	Logic Programming With Sets	1987	PODS	0.00013608891
1,049	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS	0.00012293092
2,015	On Line Processing of Compacted Relations	1982	VLDB	9.1824447e-05
2,096	Designing a Generalized NF2 Model with an SQL-Type Language Interface	1986	VLDB	9.0529033e-05
2,531	Supporting Flat Relations by a Nested Relational Kernel	1987	VLDB	8.3313296e-05
2,556	Architecture and Implementation of the Darmstadt Database Kernel System	1987	SIGMOD	8.2988885e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,820	Determining When a Structure Is a Nested Relation	1985	VLDB
2	140	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS
3	9,145	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
4	13,023	A Nested Relational Approach to Processing SQL Subqueries	2005	SIGMOD
5	3,630	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD
6	7,300	Optimization of Nested Queries using the NF2 Algebra	2016	SIGMOD
7	2,531	Supporting Flat Relations by a Nested Relational Kernel	1987	VLDB
8	2,515	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS
9	13,938	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS
10	2,156	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD