Normalization and hierarchical dependencies in the relational data model

ABSTRACT

The purpose of this paper is to present a new approach to the conceptual design of logical schemata for relational databases. One-to-one, one-to-many, and many-to-many relationships between the attributes of database relations are modeled by means of functional dependencies and multivalued dependencies. A new type of dependency is introduced: first-order hierarchical decomposition. The properties of this new type of dependency are studied and related to the normalization process of relations. The relationship between the concept of first-order hierarchical decomposition and the notion of hierarchical organization of data is discussed through the normalization process.

REFERENCES

• 1: ARMSTRONG, W.W. Dependency structures of database relationships. Information Processing 74, North-Holland, Amsterdam, 1974, pp. 580-583.
• 2: Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
• 3: Philip Alan Bernstein, Normalization and functional dependencies in the relational data base model., 1975
• 4: Philip A. Bernstein, Synthesizing third normal form relations from functional dependencies, ACM Transactions on Database Systems (TODS), v.1 n.4, p.277-298, Dec. 1976 [doi>10.1145/320493.320489]
• 5: BOITIEAUX, J. Etude math4matique d'un ensemble de notions. Contrat DGRST 67.01.015, D~l~gation G~n~rale/~ la Recherche Scientifique et Technique, Paris, 1969.
• 6: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 7: CODD, E.F. Further normalization of the database relational model. Courant Computer Science Symposium 6, Database Systems, Prentice-Haft, Englewood Cliffs, N.J., 1971, pp. 65-98.
• 8: DELOBEL, C. Aspects th~oriques sur la structure de {'information dans une base de donn~es. Revue Informatique et Recherche Operationnelle B.3 ( 1971 ), 37-64.
• 9: DELOBEL, C., AND CASEY, R.G. Decomposition of a data base and the theory of Boolean switching functions. IBM J. Res. and Develop. 17, 5 (1973), 374-386.
• 10: DELOBEL, C., AND LEONARD, M. The decomposition process in a relational model. Proc. Int. Workshop on Data Structures, IRIA, Namur, Belgium, May 1974, pp. 57-80.
• 11: Ronald Fagin, Multivalued dependencies and a new normal form for relational databases, ACM Transactions on Database Systems (TODS), v.2 n.3, p.262-278, Sept. 1977 [doi>10.1145/320557.320571]
• 12: LEONARD, M., AND REYNAUD, F. Existence du consensus et caxact~risation des couvertures et bases irredondantes d'une fonction Y~ #,A/. Rapport de recherche, Comptng. Lab., U. of Grenoble, Grenoble, France, Sept. 1976. Submitted to Discrete Math.
• 13: REYNAUD, F., LEONARD, M., AND PICHAT, E. Calculation of the prime implications and their irredundant covers in data bases. Res. Rep. #3, Conservatoire National des Arts et M~tiers, Institut d'Informatique d'Entreprise, Paris, June 1977.
• 14: Jorma Rissanen, Independent components of relations, ACM Transactions on Database Systems (TODS), v.2 n.4, p.317-325, Dec. 1977 [doi>10.1145/320576.320580]
• 15: Hans Albrecht Schmid , J. Richard Swenson, On the semantics of the relational data model, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500110]
• 16: WANG, C.P., AND WEDEKIND, H.H. Segment synthesis in logical data base design. IBM J. Res. and Develop. 19, 1 (Jan. 1975), 71-77.
• 17: Carlo Antonio Zaniolo, Analysis and design of relational schemata for database systems., 1976

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models; Schema and subschema
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Design

Keywords:
data model, first-order hierarchical dependency, functional dependency, hierarchical schema, multivalued dependency, normalization process, relational database, relational model