A complete axiomatization for a large class of dependencies in relational datatbases

ABSTRACT

Relational database theory has discovered complete axiomatizations for functional and multivalued dependencies. However, a database design system that makes use of dependencies declared by the user must deal with some more general kinds of dependencies than these— at least with embedded multivalued dependencies. Yet no axiomatization for embedded multivalued dependencies is known. In this paper, we define a more general class of dependencies, called “template dependencies” and give a complete axiomatization for these. We then discuss the interaction between functional dependencies and template dependencies.

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: Armstrong, W. W. {1974}. “Dependency structures of data base relationships,” Proc. 1974 IFIP Congress, pp. 580–583, North Holland, Amsterdam.
• 3: Beeri, C. {1977}. “On the membership problem for multivalued dependencies in relational databases,” TR229, Dept. of EECS, Princeton Univ., Princeton, N.J.
• 4: Beeri, C. {1979}. Private communication to J. D. Ullman, Dec., 1979.
• 5: 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]
• 6: 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]
• 7: Claude Delobel, Normalization and hierarchical dependencies in the relational data model, ACM Transactions on Database Systems (TODS), v.3 n.3, p.201-222, Sept. 1978 [doi>10.1145/320263.320271]
• 8: 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]
• 9: 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]
• 10: 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]
• 11: Mendelzon, A. O. and D. Maier {1979}. “Generalized mutual dependencies and the decomposition of database relations,” Dept. of EECS, Princeton Univ., Princeton, N. J.
• 12: Nicolas, J. M. {1978}. “Mutual dependencies and some results on undecomposable relations, ” Proc. International Conference on Very Large Data Bases, pp. 360–367.
• 13: Papadimitriou, C.H. and M. Yannakakis {1980}. “Algebraic dependencies,” unpublished memorandum, Laboratory for Computer Science, M. I. T., Cambridge, Mass.
• 14: Paredaens, J. {1979}. “Transitive dependencies in a database scheme,” R387, MBLE, Brussels, Belguim.
• 15: Rissanen, J. {1978}. “Relations with functional and join dependencies and their representation by independent components,” IBM, San Jose, Calif.
• 16: Fereidoon Sadri , Jeffrey D. Ullman, The interaction between functional dependencies and template dependencies, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582258]
• 17: Sagiv, Y. and S. Walecka {1979}. “Subset dependencies as an alternative to embedded multivalued dependencies,” UIUCDCS-R-79-980, Dept. of C. S., Univ. of Illinois, Urbana, Ill.
• 18: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 19: Carlo Antonio Zaniolo, Analysis and design of relational schemata for database systems., 1976

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages

General Terms:
Management, Theory