On the design of relational database schemata

ABSTRACT

The purpose of this paper is to present a new approach to the conceptual design of relational databases based on the complete relatability conditions (CRCs). It is shown that current database design methodology based upon the elimination of anomalies is not adequate. In contradistinction, the CRCs are shown to provide a powerful criticism for decomposition. A decomposition algorithm is presented which (1) permits decomposition of complex relations into simple, well-defined primitives, (2) preserves all the original information, and (3) minimizes redundancy. The paper gives a complete derivation of the CRCs, beginning with a unified treatment of functional and multivalued dependencies, and introduces the concept of elementary functional dependencies and multiple elementary multivalued dependencies. Admissibility of covers and validation of results are also discussed, and it is shown how these concepts may be used to improve the design of 3NF schemata. Finally, a convenient graphical representation is proposed, and several examples are described in detail to illustrate the method.

REFERENCES

• 1: ARMSTRONG, V~.W. Dependency structures of data base relationships. Information Processing, vol. 74. North-Holland, Amsterdam, I974, pp. 580-583.
• 2: Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
• 3: BEERI, C. On the membership problem for multivalued dependencies in relational databases. TR-229, Princeton Univ., Princeton, N.J., Sept. 1977.
• 4: BEERI, C., BERNSTEIN, P.A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. Proc. Int. Conf. Very Large Data Bases, West Berlin, Germany, 1978, pp. 113-124.
• 5: 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]
• 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: BISKUP, J. On the complementation rule for multivalued dependencies on database relations. Acta Inf. 10, 3 (1978), 297-305.
• 8: Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
• 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 data base relational model. In Data Base Systems, Courant Computer Science Series, vol. 6, R. Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 33-64.
• 11: CODD, E.F. Recent investigations in relational database systems. Information Processing, voh 74. North-Holland, Amsterdam, 1974, pp. 1017-1021.
• 12: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 13: 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. 1972), 374-386.
• 14: DELOBEL, C., AND L~:ONARD, M. The decomposition process in a relational model. Proc. Int. Workshop on Data Structure Models for Information Systems, Namur, Belgium, May 1974, pp. 57-80.
• 15: 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]
• 16: FAGIN, R. The decomposition versus synthetic approach to relational database design. Proc. Third Int. Conf. Very Large Data Bases, Tokyo, Japan, Oct. 1977, pp. 441-446.
• 17: GAUL, Z. An almost linear time algorithm for computing a dependency basis in a relational database. IBM Res. Rep. RJ2656, IBM Research Labs., San Jose, Calif., Oct. 1979.
• 18: JOINT GUIDE AND SHARE DATABASE REQUIREMENT GROUP. Requirements for a Database Management System, November 1970. (Available from SHARE, Suite 750, 25 Broadway, New York, NY 10004.)
• 19: HAGIHARA, K., ITO, M., TANIGUCHI, K., AND KASAMI, T. Decision problems for multivalued dependencies in relational databases. SIAM J. Comput. 8, 2, 247-264.
• 20: Alberto O. Mendelzon, On Axiomatizing Multivalued Dependencies in Relational Databases, Journal of the ACM (JACM), v.26 n.1, p.37-44, Jan. 1979 [doi>10.1145/322108.322112]
• 21: MONAHAN, J., AND MELKANOFF, M.A. To be published.
• 22: 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]
• 23: SAGIV, Y. An algorithm for inferring multivalued dependencies that works also for a subclass of proportional logic. VIVCDCS-R-79-954, Dep. Computer Science, Univ. Illinois, Urbana, Jan. 1979.
• 24: SILVA, A.M. Derivation of relational dependencies through case-study analyses. M.S. Thesis, Computer Science Dep., Univ. California, Los Angeles, 1978.
• 25: TANAKA, K., KAMBAYSHI, Y., AND YAJIMA, S. On the representability of decompositional schema design with multivalued dependencies. Rep. ER79-01, Dep. Information Science, Kyoto Univ., Japan, Jan. 1979.
• 26: WANG, C.P., AND WEDEKIND, H.H. Segment synthesis in logical data base design. IBM J. Res. Dev. 19, 1 (Jan. 1975), 71-77.
• 27: ZANIOLO, C. Analysis and design of relational schemata for database systems. Rep. UCLA-ENG- 7669, Computer Science Dep., Univ. California, Los Angeles, July 1976.
• 28: Carlo Zaniolo , Michel A. Melkaoff, A formal approach to the definition and the design of conceptual schemata for databased systems, ACM Transactions on Database Systems (TODS), v.7 n.1, p.24-59, March 1982 [doi>10.1145/319682.319695]

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

Keywords:
decompositon, functional dependencies, minimal covers, multivalued dependencies, relational databases, schema design