An improved third normal form for relational databases

ABSTRACT

In this paper, we show that some Codd third normal form relations may contain “superfluous” attributes because the definitions of transitive dependency and prime attribute are inadequate when applied to sets of relations. To correct this, an improved third normal form is defined and an algorithm is given to construct a set of relations from a given set of functional dependencies in such a way that the superfluous attributes are guaranteed to be removed. This new normal form is compared with other existing definitions of third normal form, and the deletion normalization method proposed is shown to subsume the decomposition method of normalization.

REFERENCES

• 1: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 2: ARMSTRONG, W.W., Dependency structures of data base relationships. Information Processing 74. North-Holland, Amsterdam, 1974, pp. 580-583.
• 3: BEERI, C., BERNSTEIN, P.A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. Proc. 4th Int. Conf. Very Large Data Bases, West Berlin, 1978, pp. 113-124.
• 4: Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
• 5: 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]
• 6: Joachim Biskup , Umeshwar Dayal , Philip A. Bernstein, Synthesizing independent database schemas, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582118]
• 7: 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]
• 8: CODD, E.F. Further normalization of the data base relational model. In Data Base Systems, R. Rustin, Ed., Courant Computer Science Symposium, vol. 6, Prentice-Hall, Englewood Cliffs, N.J., 1971, pp. 33-64.
• 9: CODD, E.F. Recent investigations in relational data base systems. Information Processing 74. North-Holland, Amsterdam, 1974, pp. 1017-1021.
• 10: DELOBEL, C., AND CASEY, R.G. Decomposition of a data base and the theory of Boolean switching functions. IBM J. Res. Dev. 17, 5 (Sept. 1973), 374-386.
• 11: Claude Delobel, Normalization and hierarchical dependencies in the relational data model, ACM Transactions on Database Systems (TODS), v.3 n.3, p.201-222, Sept. 1978 [doi>10.1145/320263.320271]
• 12: DEMETROVIC8, J. On the number of candidate keys. Inf. Process. Lett. 7, 6 (I978), 266-269.
• 13: FAGIN, R. Functional dependencies in a relational database and propositional logic. IBM J. Res. Dev. 21, 6 (Nov. 1977), 534-544.
• 14: 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]
• 15: KENT, W. A primer of normal forms (in a relational database). TR02.600, IBM Systems Development Division, San Jose, Calif., Dec. 1973.
• 16: Tok-Wang Ling, Improving data base integrity based on functional dependencies., 1978
• 17: LUCCHESI, C.L., AND OSBORN, S.L. Candidate keys for relations. J. Comput. Syst. Sci. 17, 2 (1978), 270-279.
• 18: David Maier, Minimum covers in the relational database model (Extended Abstract), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.330-337, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804425]
• 19: Sylvia Louise Osborn, Normal forms for relational data bases., 1978
• 20: OSBORN, S,L. Testing for existence of a covering Boyce-Codd normal form. Inf. Process. Lett. 8, 1 (1978), 11-14.
• 21: 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]
• 22: Yu, C.T., AND JOHNSON, D.T. On the complexity of finding the set of candidate keys for a given set of functional dependencies. Inf. Process. Lett. 5, 4 (1976), 100-101.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

General Terms:
Design

Keywords:
covering, database design, functional dependency, normalization, prime attribute, reconstructibility, relational schema, third normal form, transitive dependency