A normal form for relational databases that is based on domains and keys

ABSTRACT

A new normal form for relational databases, called domain-key normal form (DK/NF), is defined. Also, formal definitions of insertion anomaly and deletion anomaly are presented. It is shown that a schema is in DK/NF if and only if it has no insertion or deletion anomalies. Unlike previously defined normal forms, DK/NF is not defined in terms of traditional dependencies (functional, multivalued, or join). Instead, it is defined in terms of the more primitive concepts of domain and key, along with the general concept of a “constraint.” We also consider how the definitions of traditional normal forms might be modified by taking into consideration, for the first time, the combinatorial consequences of bounded domain sizes. It is shown that after this modification, these traditional normal forms are all implied by DK/NF. In particular, if all domains are infinite, then these traditional normal forms are all implied by DK/NF.

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: AHO, A. V., SAGIV, Y., AND ULLMAN, J.D. Equivalences among relational expressions. SIAM J. Comput. 8, 2 (May 1979), 218-246.
• 3: ARMSTRONG, W.W. Dependency structures of database relationships. In Proc. 1974 IFIP Congr. North-Holland, Amsterdam, 1974, pp. 580-583.
• 4: W. W. Armstrong , C. Deobel, Decompositions and functional dependencies in relations, ACM Transactions on Database Systems (TODS), v.5 n.4, p.404-430, Dec. 1980 [doi>10.1145/320610.320620]
• 5: 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]
• 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: CADIOU, J.-M. On semantic issues in the relational model of data. In Proc. Int. Syrup. Mathematical Foundations of Computer Science, Gdansk, Poland, Lecture Notes in Computer Sciences, Springer-Verlag, Heidelberg, Sept. 1975.
• 8: CHURCH, A. A note on the Entscheidungsproblem. J. Symbolic Logic 1, 40--41. Correction, 101- 102.
• 9: 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]
• 10: CODD, E.F. Further normalization of the database relational model. In Data Base Systems, Courant Computer Science Symposia 6. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 65-98.
• 11: CODD, E.F. Recent investigations in relational database systems. In Proc. 1974 IFIP Congr. North-Holland, Amsterdam, 1974, pp. 1017-1021.
• 12: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 13: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 14: DAYAL, U., AND BERNSTEIN, P. A. The fragmentation problem: Lossless decomposition of relations into files. Tech. Rep. CCA-78-13, Computer Corporation of America, Cambridge, Mass., Nov. 15, 1978.
• 15: DELOBEL, C. Contribution theorique a la conception des systemes d'information. Ph.D. Dissertation, Univ. Grenoble, Grenoble, France, 1973.
• 16: 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]
• 17: Ronald Fagin, Normal forms and relational database operators, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582120]
• 18: Ronald Fagin, Horn clauses and database dependencies (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.123-134, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804660]
• 19: IBM CORPORATION.Generalized information System/Virtual Storage, User's Guide. SH20- 9036.
• 20: IBM CORPORATION. Information Management System~Virtual Storage Utilities Reference Manual. SH20-9029.
• 21: IBM CORPORATION. Query by Example, User's Guide. SH20-2078.
• 22: KANELLAKIS, P.C. On the computational complexity of cardinality constraints in relational databases. Inf. Process. Lett. 11, 2 (Oct. 1980), 98-101.
• 23: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 24: NICOLAS, J.M. Mutual dependencies and some results on undecomposable relations. In Proc. 4th Conf. Very Large Data Bases, West Berlin, 1978, pp. 360-367.
• 25: 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]
• 26: RISSASEN, J. Theory of relations for databases--A tutorial survey. In Proc. 7th Syrup. Mathematical Foundations of Computer Science, 1978, Lecture Notes in Computer Science, vol. 64, Springer-Verlag, pp. 537-551.
• 27: Yehoshua Sagiv , Claude Delobel , D. Scott Parker, Jr. , Ronald Fagin, An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic, Journal of the ACM (JACM), v.28 n.3, p.435-453, July 1981 [doi>10.1145/322261.322263]
• 28: SMITH, J.M. A normal form for abstract syntax. In Proc. 4th Conf. Very Large Data Bases, West Berlin, 1978, pp. 156-162.
• 29: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation, Communications of the ACM, v.20 n.6, p.405-413, June 1977 [doi>10.1145/359605.359620]
• 30: SOFTWARE AG. ADABAS Introductory Manual. Software AG North America Inc., 11800 Sunrise Valley Drive, Reston, Va. 22091.
• 31: SPERNER, E. Ein satz fiber Untermengen einer endlichen Menge. Math. Zeitschrift 27 (1928), 544-548.
• 32: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 33: TYMSHARE INC. MAGNUM Reference Manual, Nov, 1975,
• 34: Carlo Zaniolo, Design of relational views over network schemas, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582126]

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:
Algorithms, Design

Keywords:
DK/NF, anomaly, complexity, database design, domain-key normal form, functional dependency, join dependency, multivalued dependency, normalization, relational database