A Recursive Algebra and Query Optimization for Nested Relations

Summary: Introduces a recursive algebra for nested relations enabling access and update of all nesting levels without flattening or navigational operators. Demonstrates improved query succinctness and optimization, with standard relational techniques extended to the recursive algebra. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2510
Venue: SIGMOD
Year: 1989
Pagerank: 8.9680897e-05
Overall Rank: 2,198 | 84.93%
DOI: 10.1145/67544.66952

Incoming Non-self Citations Over Time

Authors

1. Latha S. Colby (Indiana University)

BibTeX Citation

@inproceedings{colby_sigmod89,
        title = {{A Recursive Algebra and Query Optimization for Nested Relations}},
        author = {Colby, Latha S.},
        series = {{SIGMOD} '89},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/67544.66952},
        url = {https://dl.acm.org/doi/10.1145/67544.66952},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
51	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004291425
1,261	Rewriting Procedures for Batched Bindings	2008	VLDB	0.0001143305
7,405	Storing and Querying Tree-Structured Records in Dremel	2014	VLDB	5.624456e-05
8,972	CRIUS: User-Friendly Database Design	2011	VLDB	5.3414676e-05
13,022	Tutorial: Languages for Collection Types	1994	PODS	5.093636e-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
538	Non First Normal Form Relations To Represent Hierarchically Organized Data	1984	PODS	0.00016919845
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
3,564	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD	7.3058238e-05
5,569	On The Expressive Power Of The Extended Relational Algebra For The Unnormalized Relational Model	1987	PODS	6.1702169e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,155	Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets	2014	SIGMOD
2	7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS
3	1,860	Querying Multiple Features of Groups in Relational Databases	1996	VLDB
4	95	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB
5	7,986	Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies	1992	SIGMOD
6	4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD
7	143	Optimization of Nonrecursive Queries	1986	VLDB
8	7,148	Optimization of Nested Queries using the NF2 Algebra	2016	SIGMOD
9	129	Optimization of Nested SQL Queries Revisited	1987	SIGMOD
10	12,727	A Nested Relational Approach to Processing SQL Subqueries	2005	SIGMOD