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: 741
Venue: PODS
Year: 1985
Pagerank: 0.00012388199
Overall Rank: 1,056 | 92.76%
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
475	A Calculus for Complex Objects	1986	PODS	0.00017864549
782	FAD, a Powerful and Simple Database Language	1987	VLDB	0.00014080876
799	Logic Programming With Sets	1987	PODS	0.00013911498
3,432	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.4182332e-05
4,487	Reasoning about Nested Functional Dependencies	1999	PODS	6.6686357e-05
4,491	A Semantics for Complex Objects and Approximate Queries	1988	PODS	6.6652483e-05
5,569	On The Expressive Power Of The Extended Relational Algebra For The Unnormalized Relational Model	1987	PODS	6.1702169e-05
5,880	Cooperative Object Buffer Management in the Advanced Information Management Prototype	1987	VLDB	6.0533041e-05
5,929	Nested Historical Relations	1989	SIGMOD	6.037567e-05
6,516	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD	5.8545649e-05
6,771	Efficient Discovery of XML Data Redundancies	2006	VLDB	5.7783105e-05
7,014	Extending the Relational Algebra to Capture Complex Objects	1989	VLDB	5.7258694e-05
8,972	CRIUS: User-Friendly Database Design	2011	VLDB	5.3414676e-05
9,332	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS	5.2887881e-05
10,995	Towards Principled, Practical Document Database Design	2025	VLDB	5.093636e-05
13,143	Optimization of Relational Schemas Containing Inclusion Dependencies	1989	VLDB	5.093636e-05
13,170	Logical Design of Relational Database Schemes	1987	PODS	5.093636e-05
13,192	Some Classes of Multilevel Relational Structures (Extended Abstract)	1986	PODS	5.093636e-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.00029686538
538	Non First Normal Form Relations To Represent Hierarchically Organized Data	1984	PODS	0.00016919845
2,529	REAL-WORLD MVD's	1981	SIGMOD	8.4604846e-05
3,222	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB	7.6260706e-05
3,504	Elimination of Intersection Anomalies from Database Schemes (Extended Abstract)	1983	PODS	7.3590322e-05
6,478	Weak Multivalued Dependencies+	1984	PODS	5.8678984e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,192	Some Classes of Multilevel Relational Structures (Extended Abstract)	1986	PODS
2	12,055	SQL Schema Design: Foundations, Normal Forms, and Normalization	2016	SIGMOD
3	6,569	The Partial Normalized Storage Model of Nested Relations	1988	VLDB
4	4,232	A Unified Approach to Functional Dependencies and Relations	1975	SIGMOD
5	6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS
6	13,170	Logical Design of Relational Database Schemes	1987	PODS
7	7,542	Operations and the Properties on Non-First-Normal-Form Relational Databases	1983	VLDB
8	9,332	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
9	4,259	Database Decomposition into Fourth Normal Form	1983	VLDB
10	6,516	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD