ACM SIGMOD Anthology TODS dblp.uni-trier.de

A New Normal Form for Nested Relations.

Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987)
@article{DBLP:journals/tods/OzsoyogluY87,
  author    = {Z. Meral {\"O}zsoyoglu and
               Li-Yan Yuan},
  title     = {A New Normal Form for Nested Relations},
  journal   = {ACM Trans. Database Syst.},
  volume    = {12},
  number    = {1},
  year      = {1987},
  pages     = {111-136},
  ee        = {http://doi.acm.org/10.1145/12047.13676, db/journals/tods/OzsoyogluY87.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We consider nested relations whose schemes are structured as trees, called scheme trees, and introduce a normal form for such relations, called the nested normal form. Given a set of attributes U, and a set of multivalued dependencies (MVDs) M over these attributes, we present an algorithm to obtain a nested normal form decomposition of U with respect to M. Such a decomposition has several desirable properties, such as explicitly representing a set of full and embedded MVDs implied by M, and being a faithful and nonredundant representation of U. Moreover, if the given set of MVDs is conflict-free, then the nested normal form decomposition is also dependency-preserving. Finally, we show that if M is conflict-free, then the set of root-to-leaf paths of scheme trees in nested normal form decomposition is precisely the unique 4NF decomposition [9, 16] of U with respect to M.

Copyright © 1987 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations to Represent Hierarchical Organized Data. PODS 1984: 191-200 BibTeX
[2]
...
[3]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[4]
Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX
[5]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[6]
Catriel Beeri, Michael Kifer: Elimination of Intersection Anomalies from Database Schemes. PODS 1983: 340-351 BibTeX
[7]
Catriel Beeri, Michael Kifer: Comprehensive Approach to the Design of Relational Database Schemes. VLDB 1984: 196-207 BibTeX
[8]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[9]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[10]
Patrick C. Fischer, Dirk Van Gucht: Weak Multivalued Dependencies. PODS 1984: 266-274 BibTeX
[11]
...
[12]
...
[13]
Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX
[14]
...
[15]
Y. Edmund Lien: Hierarchical Schemata for Relational Databases. ACM Trans. Database Syst. 6(1): 48-69(1981) BibTeX
[16]
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX
[17]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[18]
Akifumi Makinouchi: A Consideration on Normal Form of Not-Necessarily-Normalized Relation in the Relational Data Model. VLDB 1977: 447-453 BibTeX
[19]
Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Victor Matos: Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions. ACM Trans. Database Syst. 12(4): 566-592(1987) BibTeX
[20]
...
[21]
...
[22]
...
[23]
Edward Sciore: Real-World MVD's. SIGMOD Conference 1981: 121-132 BibTeX
[24]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[25]
Li-Yan Yuan, Z. Meral Özsoyoglu: Unifying Functional and Multivalued Dependencies for Relational Database Design. PODS 1986: 183-190 BibTeX
[26]
Carlo Zaniolo, Michel A. Melkanoff: On the Design of Relational Database Schemata. ACM Trans. Database Syst. 6(1): 1-47(1981) BibTeX

Referenced by

  1. Carmem S. Hara, Susan B. Davidson: Reasoning about Nested Functional Dependencies. PODS 1999: 91-100
  2. Sin Yeung Lee, Mong-Li Lee, Tok Wang Ling, Leonid A. Kalinichenko: Designing Good Semi-Structured Databases and Conceptual Modeling. ER 1999: 131-145
  3. Zahir Tari, John Stokes, Stefano Spaccapietra: Object Normal Forms and Dependency Constraints for Object-Oriented Schemata. ACM Trans. Database Syst. 22(4): 513-569(1997)
  4. Abdullah Uz Tansel: Temporal Relational Data Model. IEEE Trans. Knowl. Data Eng. 9(3): 464-479(1997)
  5. Wai Yin Mok, Yiu-Kai Ng, David W. Embley: A Normal Form for Precisely Characterizing Redundancy in Nested Relations. ACM Trans. Database Syst. 21(1): 77-106(1996)
  6. Christian S. Jensen, Richard T. Snodgrass, Michael D. Soo: Extending Existing Dependency Theory to Temporal Databases. IEEE Trans. Knowl. Data Eng. 8(4): 563-582(1996)
  7. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  8. Mark Levene, George Loizou: Semantics for Null Extended Nested Relations. ACM Trans. Database Syst. 18(3): 414-459(1993)
  9. Gultekin Özsoyoglu, Aladdin Hafez: Near-Optimum Storage Models for Nested Relations Based on Workload Information. IEEE Trans. Knowl. Data Eng. 5(6): 1018-1038(1993)
  10. János Demetrovics, Lajos Rónyai, Hua nam Son: On the Composition and Decomposition of Attributes and Tuples. ICDT 1992: 71-85
  11. Z. Meral Özsoyoglu, Jian Wang: A Keying Method for a Nested Relational Database Management System. ICDE 1992: 438-446
  12. Georges Gardarin, Patrick Valduriez: ESQL2: An Object-Oriented SQL with F-Logic Semantics. ICDE 1992: 320-327
  13. Mizuho Iwaihara, Tetsuya Furukawa, Yahiko Kambayashi: Navigation and Schema Transformations for Producing Nested Relations form Networks. ICDE 1991: 181-190
  14. Howard M. Dreizen, Shi-Kuo Chang: Imprecise Schema: A Rationale for Relations with Embedded Subrelations. ACM Trans. Database Syst. 14(4): 447-479(1989)
  15. Marco A. Casanova, Luiz Tucherman, Antonio L. Furtado, Anelise P. Braga: Optimization of Relational Schemas Containing Inclusion Dependencies. VLDB 1989: 317-325
  16. Abdullah Uz Tansel, Lucy Garnett: Nested Historical Relations. SIGMOD Conference 1989: 284-294
  17. Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 13(4): 389-417(1988)
  18. Peter Buneman, Susan B. Davidson, Aaron Watters: A Semantics for Complex Objects and Approximate Queries. PODS 1988: 305-314
  19. Mark Levene, George Loizou: A Universal Relation Model for Nested Relations. EDBT 1988: 294-308
  20. Z. Meral Özsoyoglu, Li-Yan Yuan: Reduced MVDs and Minimal Covers. ACM Trans. Database Syst. 12(3): 377-394(1987)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:01 2008