Normal forms and relational database operators

ABSTRACT

We discuss the relationship between normal forms in a relational database and an allowed set of relational operators. We define "projection-join normal form" (PJ/NF), which is the ultimate normal form when only projection and join are allowed. Aho, Beeri and Ullman made the counterintuitive discovery that there is a relation schema with a valid decomposition into three of its projections without the decomposition being equivalent to a cascade of decompositions, each into two projections. Because of this possibility, there exist bizarre relation schemata that are in fourth normal form but not in PJ/NF. We also discuss issues associated with allowing the union operator.

REFERENCES

• 1: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 2: {ABU} A. V. Aho, C. Beeri, and J. D. Ullman, The theory of joins in relational data bases. Proc. 19th IEEE Symp. on Foundations of Computer Science (Oct. 1977), 107--113.
• 3: {ASU} A. V. Aho, Y. Sagiv, and J. D. Ullman, Equivalences among relational expressions. To appear, SIAM J. Computing.
• 4: {Ar} W. W. Armstrong, Dependency structures of database relationships. Proc. IFIP 74, North Holland (1974), 580--583.
• 5: {BBG} C. Beeri, P. A. Bernstein, and N. Goodman, A sophisticate's introduction to database normalization theory. Proc. 1978 VLDB (Berlin), 113--124.
• 6: 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]
• 7: {Ca} J.-M. Cadiou, On semantic issues in the relational model of data. Proc. Int. Symp, on Math. Foundations of Computer Science, Gdansk, Poland, Lecture Notes in Computer Science, Springer-Verlag, Heidelberg, Sept. 1975.
• 8: 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]
• 9: {Co2} E. F. Codd, Relational completeness of data base sublanguages. Courant Computer Science Symposia 7, Data Base Systems, New York City, May 24--25, 1971, Prentice Hall.
• 10: {Co3} E. F. Codd, Recent investigations in relational data base systems. Proc. IFIP Congress 74, North-Holland (1974), 1017--1021.
• 11: {Co4} E. F. Codd, Understanding relations. Installment No. 7, FDT (bulletin of ACM SIGMOD) 7, 3--4, Dec. 1975.
• 12: {DB} U. Dayal and P. A. Bernstein, The fragmentation problem: lossless decomposition of relations into files. Technical report CCA-78-13, Computer Corporation of America, Cambridge Mass. (Nov. 15, 1978).
• 13: 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]
• 14: {Fa2} R. Fagin, Functional dependencies in a relational database and propositional logic. IBM J. Res. and Devel. 21,6 (Nov. 1977), 534--544.
• 15: {He} I. J. Heath, Unacceptable file operations in a relational data base. Proc. 1971 ACM-SIGFIDET workshop on data description, access, and control, San Diego, Calif., Nov. 11--12, 1971.
• 16: {Me} A. Mendelzon, Private communication received transitively through Y. Sagiv.
• 17: {Ni} J. M. Nicolas, Mutual dependencies and some results on undecomposable relations. Proc. 1978 VLDB (Berlin), 360--367.
• 18: 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]
• 19: {Ri2} J. Rissanen, Theory of relations for databases --- a tutorial survey. Proc. 7th Symp. on Math. Found. of Comp. Science, Lecture notes in Comp. Science, 64, Springer-Verlag, 537--551.
• 20: {Sm} J. M. Smith, A normal form for abstract syntax. Proc. 1978 VLDB (Berlin), 156--162.