Synthesizing third normal form relations from functional dependencies

ABSTRACT

It has been proposed that the description of a relational database can be formulated as a set of functional relationships among database attributes. These functional relationships can then be used to synthesize algorithmically a relational scheme. It is the purpose of this paper to present an effective procedure for performing such a synthesis. The schema that results from this procedure is proved to be in Codd's third normal form and to contain the fewest possible number of relations. Problems with earlier attempts to construct such a procedure are also discussed.

REFERENCES

• 1: ARMSTRONG, W.W. Dependency structures of data base relationships. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 580-583.
• 2: Philip Alan Bernstein, Normalization and functional dependencies in the relational data base model., 1975
• 3: 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]
• 4: BERNSTEIN, P.A. A comment on "Segment synthesis in logical data base design." IBM J. Res. Develop. 20, 4 (July 1976), 412.
• 5: BERNSTEIN, P.A., AND BEERI, C. An algorithmic approach to normalization of relational data base schemas. Tech. Rep. CSRG-73, Comptr. Systems Res. Group, Dep. Comptr. Sci., U. of Toronto, Toronto, Canada, Sept. 1976.
• 6: CASEY, R.G., DELOBEb, C., AND BERNSTEIN, P.A. A correction to "Decomposition of a data base and the theory of Boolean switching functions." (to appear in IBM J. Res. Develop.).
• 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: CO~D, E.F. Further normalization of the data base relational model, inData Base Systems, Courant Inst. Comptr. Sci. Syrup. 6, R. Rustin, Ed., Prentice-Hall, t~nglewood Cliffs, 1972, pp. 33-64.
• 9: DxT~, C.J. An Introd~xction to Database Systems. Addison-Wesley, Reading, Mass., 1975.
• 10: DELOBEb, C.~ AND CASEY, R.G. Decomposition of a data base and the theory of Boolean switching functions. IBM J. Res. Develop. 17, 5 (Sept. 1972), 374-386.
• 11: RISSANEN, J., AND DELOBEL, C. Decomposition of files, a basis for data storage 'and retrieval. Res. Rep. RJ 1220, IBM Res. Lab., San Jose, Calif., May 1973.
• 12: WANG, C.P.,/kND WEDEKIND, H.H. Segment synthesis in logical data base design. IBM J. Res. Develop. 19, 1 (Jan. 1975), 71-77.

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.1 Logical Design
          Subjects: Data models; Schema and subschema

General Terms:
Design

Keywords:
database schema, functional dependency, relational model, semantics of data, third normal form