A Normal Form for Nested Relations

Summary: Introduces Nested Normal Form (NNF) for tree-structured nested relation schemes and an algorithm to decompose a universal scheme U into a normal scheme tree given a set M of MVDs (treating FDs as MVDs). NNF decomposition explicitly captures implied full and embedded MVDs, is faithful and nonredundant, preserves dependencies when M is conflict-free, and yields the unique 4NF decomposition as the set of root-to-leaf paths in that case. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h0f65c7e829a1a646
Venue: PODS
Year: 1985
Pagerank: 0.00012107176
Overall Rank: 1,085 | 92.71%
DOI: 10.1145/325405.325451

Incoming Non-self Citations Over Time

Authors

1. Z. Meral Ozsoyoglu (Case Western Reserve University)
2. Li-Yan Yuan (Case Western Reserve University)

BibTeX Citation

@inproceedings{ozsoyoglu_pods85,
        address = {New York, NY, USA},
        series = {{PODS} '85},
        title = {{A Normal Form for Nested Relations}},
        url = {https://dl.acm.org/doi/10.1145/325405.325451},
        doi = {10.1145/325405.325451},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ozsoyoglu, Z. Meral and Yuan, Li-Yan},
        year = {1985}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
486	A Calculus for Complex Objects	1986	PODS	0.00017463801
809	FAD, a Powerful and Simple Database Language	1987	VLDB	0.00013771533
828	Logic Programming With Sets	1987	PODS	0.00013608891
3,502	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.2490781e-05
4,584	Reasoning about Nested Functional Dependencies	1999	PODS	6.5160342e-05
4,586	A Semantics for Complex Objects and Approximate Queries	1988	PODS	6.5150868e-05
5,682	On The Expressive Power Of The Extended Relational Algebra For The Unnormalized Relational Model	1987	PODS	6.0373361e-05
6,003	Cooperative Object Buffer Management in the Advanced Information Management Prototype	1987	VLDB	5.9149516e-05
6,056	Nested Historical Relations	1989	SIGMOD	5.8997034e-05
6,648	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD	5.7205114e-05
6,912	Efficient Discovery of XML Data Redundancies	2006	VLDB	5.6459867e-05
7,159	Extending the Relational Algebra to Capture Complex Objects	1989	VLDB	5.5947501e-05
9,139	CRIUS: User-Friendly Database Design	2011	VLDB	5.220895e-05
9,523	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS	5.167675e-05
11,377	Towards Principled, Practical Document Database Design	2025	VLDB	4.9769913e-05
13,439	Optimization of Relational Schemas Containing Inclusion Dependencies	1989	VLDB	4.9769913e-05
13,466	Logical Design of Relational Database Schemes	1987	PODS	4.9769913e-05
13,488	Some Classes of Multilevel Relational Structures (Extended Abstract)	1986	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
549	Non First Normal Form Relations To Represent Hierarchically Organized Data	1984	PODS	0.00016555794
2,581	REAL-WORLD MVD's	1981	SIGMOD	8.2669432e-05
3,288	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB	7.4516003e-05
3,578	Elimination of Intersection Anomalies from Database Schemes (Extended Abstract)	1983	PODS	7.1906771e-05
6,610	Weak Multivalued Dependencies+	1984	PODS	5.7336898e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,488	Some Classes of Multilevel Relational Structures (Extended Abstract)	1986	PODS
2	9,976	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD
3	6,699	The Partial Normalized Storage Model of Nested Relations	1988	VLDB
4	4,319	A Unified Approach to Functional Dependencies and Relations	1975	SIGMOD
5	6,839	Properties Of Database Schemata With Functional Dependencies	1984	PODS
6	13,466	Logical Design of Relational Database Schemes	1987	PODS
7	7,694	Operations and the Properties on Non-First-Normal-Form Relational Databases	1983	VLDB
8	9,523	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
9	4,350	Database Decomposition into Fourth Normal Form	1983	VLDB
10	6,648	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD