Multivalued dependencies and a new normal form for relational databases

ABSTRACT

A new type of dependency, which includes the well-known functional dependencies as a special case, is defined for relational databases. By using this concept, a new (“fourth”) normal form for relation schemata is defined. This fourth normal form is strictly stronger than Codd's “improved third normal form” (or “Boyce-Codd normal form”). It is shown that every relation schema can be decomposed into a family of relation schemata in fourth normal form without loss of information (that is, the original relation can be obtained from the new relations by taking joins).

REFERENCES

• 1: ARMSTRONG, W.W. Dependency structures of database relationships. Information Processing 74, North-Holland Pub. Co., 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 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]
• 4: P. A. Bernstein , J. R. Swenson , D. C. Tsichritzis, A unified approach to functional dependencies and relations, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500112]
• 5: CADIOV, J.-M. On semantic issues in the relational model of data. Proc. Int. Symp. on Math. Foundations of Comptr. Sci., Gdafisk, Poland, Lecture Notes in Computer Science, Springer-Verlag, Heidelberg, Sept. 1975.
• 6: CODD, E.F. Further normalization of the data base relational model. In Courant Computer Science Symposium 6: Data Base Systems, Prentice-Hall, Englewood Cliffs, N.J., May 1971, pp. 65-98.
• 7: CODD, E.F. Recent investigations in relational data base systems. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 1017-1021.
• 8: 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 (Sept. 1973), 374-386.
• 9: DELOBEL, C., AND L~ONARD, M. The decomposition process in a relational model. Proc. int. Workshop on Data Structure Models for Information Systems, Presses U. de Namur, Namur, Belgium, May 1974, pp. 57-80.
• 10: FAGIN, R. Functional dependencies in a relational database and propositional logic. IBM J. Res. and Develop. 21, 6 (Nov. 1977).
• 11: RISSANEN, J.J. Independent components of relations. Res. Rep. RJ1899, IBM Res. Lab., San Jose, Calif., Jan. 1977.
• 12: 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]
• 13: Carlo Antonio Zaniolo, Analysis and design of relational schemata for database systems., 1976

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Design, Management

Keywords:
3NF, 4NF, Boyce-Codd normal form, database design, decomposition, fourth normal form, functional dependency, multivalued dependency, normalization, relatioanl database, third normal form