On The Expressive Power Of The Extended Relational Algebra For The Unnormalized Relational Model

Summary: Shows extended relational algebra with NEST/UNNEST is BP-complete (boundedness + expressiveness) over the unnormalized (non-1NF) model. Characterizes BP-boundedness/expressiveness via invariance under database transformations, generalizing classical completeness. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hf4d04e34f0bf9eb0
Venue: PODS
Year: 1987
Pagerank: 6.0176113e-05
Overall Rank: 5,693 | 61.84%
DOI: 10.1145/28659.28692

Incoming Non-self Citations Over Time

Authors

1. Dirk Van Gucht (Indiana University)

BibTeX Citation

@inproceedings{gucht_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{ON THE EXPRESSIVE POWER OF THE EXTENDED RELATIONAL ALGEBRA FOR THE UNNORMALIZED RELATIONAL MODEL}},
        url = {https://dl.acm.org/doi/10.1145/28659.28692},
        doi = {10.1145/28659.28692},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Van Gucht, Dirk},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,161	Theory of Database Queries (Extended Abstract)	1988	PODS	8.9203568e-05
2,163	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	8.9189753e-05
3,641	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD	7.1238143e-05
13,364	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
551	Non First Normal Form Relations To Represent Hierarchically Organized Data	1984	PODS	0.00016502064
561	A New Approach to Database Logic	1984	PODS	0.00016361117
642	Data Structures for an Integrated Data Base Management and Information Retrieval System	1982	VLDB	0.00015230974
692	On An Algebra For Historical Relational Databases. Two Views	1985	SIGMOD	0.00014701559
1,087	A Normal Form for Nested Relations	1985	PODS	0.00012067301
2,024	On Line Processing of Compacted Relations	1982	VLDB	9.1532448e-05
2,835	Determining When a Structure Is a Nested Relation	1985	VLDB	7.9414981e-05
6,620	Weak Multivalued Dependencies+	1984	PODS	5.7147406e-05
7,392	A Model for Integrated Information Systems	1983	VLDB	5.5203248e-05
13,529	Some Classes of Multilevel Relational Structures (Extended Abstract)	1986	PODS	4.9605343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,707	Operations and the Properties on Non-First-Normal-Form Relational Databases	1983	VLDB
2	2,522	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS
3	6,166	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD
4	1,962	Relational Expressive Power of Constraint Query Languages	1996	PODS
5	13,392	Interpreting a Reconstructed Relational Calculus: Extended Abstract	1993	SIGMOD
6	4,448	Languages for Relational Databases over Interpreted Structures	1997	PODS
7	5,253	On the Correctness of Representing Extended Entity-Relationship Structures in the Relational Model	1989	SIGMOD
8	13,467	A Sound and Complete Query Evaluation Algorithm for Relational Databases with Disjunctive Information (Extended Abstract)	1989	PODS
9	13,978	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS
10	140	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS