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.00012112852
Overall Rank: 1,084 | 92.72%
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.00017471997
809	FAD, a Powerful and Simple Database Language	1987	VLDB	0.00013777631
828	Logic Programming With Sets	1987	PODS	0.00013614671
3,502	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.2525074e-05
4,582	Reasoning about Nested Functional Dependencies	1999	PODS	6.5191203e-05
4,584	A Semantics for Complex Objects and Approximate Queries	1988	PODS	6.5181125e-05
5,681	On The Expressive Power Of The Extended Relational Algebra For The Unnormalized Relational Model	1987	PODS	6.0401867e-05
6,002	Cooperative Object Buffer Management in the Advanced Information Management Prototype	1987	VLDB	5.9177524e-05
6,054	Nested Historical Relations	1989	SIGMOD	5.9024935e-05
6,643	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD	5.7232205e-05
6,910	Efficient Discovery of XML Data Redundancies	2006	VLDB	5.6486607e-05
7,156	Extending the Relational Algebra to Capture Complex Objects	1989	VLDB	5.5973998e-05
9,129	CRIUS: User-Friendly Database Design	2011	VLDB	5.2233677e-05
9,512	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS	5.1701225e-05
11,371	Towards Principled, Practical Document Database Design	2025	VLDB	4.9793485e-05
13,433	Optimization of Relational Schemas Containing Inclusion Dependencies	1989	VLDB	4.9793485e-05
13,460	Logical Design of Relational Database Schemes	1987	PODS	4.9793485e-05
13,482	Some Classes of Multilevel Relational Structures (Extended Abstract)	1986	PODS	4.9793485e-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.00029346895
549	Non First Normal Form Relations To Represent Hierarchically Organized Data	1984	PODS	0.00016563595
2,581	REAL-WORLD MVD's	1981	SIGMOD	8.2708541e-05
3,287	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB	7.4551258e-05
3,575	Elimination of Intersection Anomalies from Database Schemes (Extended Abstract)	1983	PODS	7.194079e-05
6,606	Weak Multivalued Dependencies+	1984	PODS	5.7364017e-05

Semantically Similar Papers

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