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: 812
Venue: PODS
Year: 1988
Pagerank: 8.240179e-05
Overall Rank: 2,701 | 81.48%
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,130	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	9.1244275e-05
2,400	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.6299917e-05
2,461	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.550394e-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,564	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD	7.3058238e-05
4,702	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.5549225e-05
5,259	An Implementation for Nested Relational Databases	1988	VLDB	6.2965521e-05
7,086	A Query Language for NC	1994	PODS	5.7073076e-05
7,339	Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure	1994	PODS	5.6393827e-05
7,405	Storing and Querying Tree-Structured Records in Dremel	2014	VLDB	5.624456e-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.00029686538
346	A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies	1986	SIGMOD	0.00020654241
475	A Calculus for Complex Objects	1986	PODS	0.00017864549
799	Logic Programming With Sets	1987	PODS	0.00013911498
1,026	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS	0.00012578477
1,976	On Line Processing of Compacted Relations	1982	VLDB	9.3644331e-05
2,051	Designing a Generalized NF2 Model with an SQL-Type Language Interface	1986	VLDB	9.2538701e-05
2,494	Supporting Flat Relations by a Nested Relational Kernel	1987	VLDB	8.5053229e-05
2,518	Architecture and Implementation of the Darmstadt Database Kernel System	1987	SIGMOD	8.4755514e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,764	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	8,971	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
4	12,727	A Nested Relational Approach to Processing SQL Subqueries	2005	SIGMOD
5	3,564	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD
6	7,148	Optimization of Nested Queries using the NF2 Algebra	2016	SIGMOD
7	2,494	Supporting Flat Relations by a Nested Relational Kernel	1987	VLDB
8	13,620	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS
9	2,461	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS
10	2,198	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD