A constructive definition of third normal form

ABSTRACT

The concept of normalisation and the definition of third normal form occupy a central place in the relational model of database. Normalisation has been described as an analytic process in which an initially unconstrained collection of relations is successively decomposed into a collection of smaller relations satisfying the constraints of the three normal forms. Normalised relations constitute the basis on which data manipulation languages - relational algebra, relational calculus and others - have been defined. As yet, however, there is no generally recognised data definition language for the relational model. A pre-requisite for this would be a constructive definition of third normal form, that is, a definition in terms of rules for building normalised relations from simple domains. This paper considers how such a definition may be achieved by applying two ideas derived from the study of programming languages; the notion of data type, and the notion of a selector as used in formal language definition. The result is an abstract syntax of relations. This is compared with the standard definition of normalisation and its completeness is critically examined.

REFERENCES

• 1: 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]
• 2: E F CODD, 'Further Normalisation of the Data Base Relational Model', Courant Computer Science Symposia 6 (1971)
• 3: I J HEATH, 'Unacceptable File Operations in a Relational Data Base', Proc. ACM SIGFIDET Workshop (1971)
• 4: W KENT, 'A Primer of Normal Forms', IBM Technical Report TR.02.600 (1973)
• 5: R F BOYCE, 'Fourth Normal Form and its Associated Decomposition Algorithm', IBM TDB 16 p 30 (1973)
• 6: E F CODD, 'Recent Investigations in Relational Data Base Systems', Proc. IFIP Congress, Stockholm (1974)
• 7: P A V HALL, P HITCHCOCK, S J P TODD, 'An Algebra of Relations for Machine Computation', IBM Report UKSC-0066 (1975)
• 8: G C H SHARMAN, 'A New Model of Relational Data Base and High Level Languages', IBM Technical Report TR.12.136 (1975)
• 9: P LUCAS and K WALK, 'On the Formal Definition of PL/I', Ann. Rev. Automatic Programming 6 (1969)
• 10: P LUCAS, P LAUER, H STIGLEITNER, 'Method and Notation for the Formal Definition of Programming Languages', IBM Technical Report TR.25.087 (1970)
• 11: H BEKIC, D BJORNER, W HENHAPL, C B JONES, P LUCAS, 'A Formal Definition of a PL/I Subset, Part I', IBM Technical Report TR.25.139 (1974)
• 12: C. J. Date, An Introduction to Database Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 13: ibid, p 64
• 14: C DELOBEL and R G CASEY, 'Decomposition of a Data Base and the Theory of Boolean Switching Functions', IBM J. Res. Develop 17 p 374 (1973)
• 15: C P WANG and H H WEDEKIND, 'Segment Synthesis in Logical Data Base Design', IBM J. Res. Develop. 19 p 71 (1975)