Hierarchical Schemata for Relational Databases.

@article{DBLP:journals/tods/Lien81,
  author    = {Y. Edmund Lien},
  title     = {Hierarchical Schemata for Relational Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {6},
  number    = {1},
  year      = {1981},
  pages     = {48-69},
  ee        = {http://doi.acm.org/10.1145/319540.319546, db/journals/tods/Lien81.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Most database design methods for the relational model produce a flat database, that is, a family of relations with no explicit interrelational connections. The user of a flat database is likely to be unaware of certain interrelational semantics. In contrast, the entity-relationship model provides schema graphs as a description of the database, as well as for navigating the database. Nevertheless, the user of an entity-relationship database may still commit semantic errors, such as performing a lossy join. This paper proposes a nonflat, or hierarchical, view of relational databases. Relations are grouped together to form relation hierarchies in which lossless joins are explicitly shown whereas lossy joins are excluded. Relation hierarchies resemble the schema graphs in the entity-relationship model.

An approach to the design of relation hierarchies is outlined in the context of data dependencies and relational decomposition. The approach consists of two steps; each is described as an algorithm. Algorithm DEC decomposes a given universal relation according to a given set of data dependencies and produces a set of nondecomposable relation schemes. This algorithm differs from its predecessors in that it produces no redundant relation schemes. Algorithm RH further structures the relation schemes produced by Algorithm DEC into a hierarchical schema. These algorithms can be useful software tools for database designers.

Copyright © 1981 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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX

[2]

Catriel Beeri: On the Membership Problem for Functional and Multivalued Dependencies in Relational Databases. ACM Trans. Database Syst. 5(3): 241-259(1980) BibTeX

[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]

Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX

[6]

Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX

[7]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[8]

E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX

[9]

C. J. Date: An Introduction to Database Systems, 2nd Edition. Addison-Wesley 1977
BibTeX

[10]

Claude Delobel: Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Trans. Database Syst. 3(3): 201-222(1978) BibTeX

[11]

Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX

[12]

Ronald Fagin: The Decomposition Versus Synthetic Approach to Relational Database Design. VLDB 1977: 441-446 BibTeX

[13]

Y. Edmund Lien: Multivalued Dependencies with Null Values in Relational Data Bases. VLDB 1979: 61-66 BibTeX

[14]

Alberto O. Mendelzon: On Axiomatizing Multivalued Dependencies in Relational Databases. J. ACM 26(1): 37-44(1979) BibTeX

[15]

Jorma Rissanen: Theory of Relations for Databases - A Tutorial Survey. MFCS 1978: 536-551 BibTeX

[16]

Yehoshua Sagiv: An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic. J. ACM 27(2): 250-262(1980) BibTeX

[17]

...

[18]

...

Referenced by

1. Jeffrey R. Horowitz, Alfonso F. Cardenas: Decomposing Heterogeneous Inter-Entity Relationship Updates. IEEE Trans. Knowl. Data Eng. 4(4): 360-370(1992)
2. Amit P. Sheth, James A. Larson: Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases. ACM Comput. Surv. 22(3): 183-236(1990)
3. Z. Meral Özsoyoglu, Li-Yan Yuan: Reduced MVDs and Minimal Covers. ACM Trans. Database Syst. 12(3): 377-394(1987)
4. Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987)
5. Mark A. Roth, Henry F. Korth: The Design of ¬1NF Relational Databases into Nested Normal Form. SIGMOD Conference 1987: 143-159
6. Li-Yan Yuan, Z. Meral Özsoyoglu: Logical Design of Relational Database Systems. PODS 1987: 38-47
7. Hans Janssens: A Theory of Reference Graphs in Relational Databases. MFDBS 1987: 159-180
8. Shamkant B. Navathe, A. M. Awong: Abstracting Relational and Hierarchical Data with a Semantic Data Model. ER 1987: 305-333
9. Toby J. Teorey, Dongqing Yang, James P. Fry: A Logical Design Methodology for Relational Databases Using the Extended Entity-Relationship Model. ACM Comput. Surv. 18(2): 197-222(1986)
10. Li-Yan Yuan, Z. Meral Özsoyoglu: Unifying Functional and Multivalued Dependencies for Relational Database Design. PODS 1986: 183-190
11. Dirk Van Gucht, Patrick C. Fischer: Some Classes of Multilevel Relational Structures. PODS 1986: 60-69
12. Z. Meral Özsoyoglu, Li-Yan Yuan: A Normal Form for Nested Relations. PODS 1985: 251-260
13. Kathi Hogshead Davis, Adarsh K. Arora: A Methodology for Translating a Conventional File System into an Entity-Relationship Model. ER 1985: 148-159
14. Alfonso F. Cardenas, George R. Wang: Translation of SQL/DS Data Access/Update into Entity-Relationship Data Access/Update. ER 1985: 256-267
15. Gösta Grahne, Kari-Jouko Räihä: Database Decomposition into Fourth Normal Form. VLDB 1983: 186-196
16. Robert Brown, Douglas Stott Parker Jr.: LAURA: A Formal Data Model and her Logical Design Methodology. VLDB 1983: 206-218
17. Chandra M. R. Kintala: Attributed Grammars for Query Language Translations. PODS 1983: 137-148
18. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
19. Carol Helfgott LeDoux, Douglas Stott Parker Jr.: Reflections on Boyce-Codd Normal Form. VLDB 1982: 131-141
20. Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157
21. Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9