Testing implications of data dependencies

ABSTRACT

Presented is a computation method—the chase—for testing implication of data dependencies by a set of data dependencies. The chase operates on tableaux similar to those of Aho, Sagiv, and Ullman. The chase includes previous tableau computation methods as special cases. By interpreting tableaux alternately as mappings or as templates for relations, it is possible to test implication of join dependencies (including multivalued dependencies) and functional dependencies by a set of dependencies.

REFERENCES

• 1: AHO, A.V., BEERI, C., AND ULLMAN, J.D. The theory of joins in relational databases. Proc. 18th Syrup. on Foundations of Computer Science, Providence, R.I., 1977, pp. 107-113.
• 2: AHO, A,V,, SAGIV, Y., AND ULLMA~, J.D. Equivalence of relational expressions. SIAM J. Comping. 8, 2 (May 1979), 218-246.
• 3: ARMSTRONG, W.W. Dependency structures of data base relationships. Proc. IFIP '74, North- Holland Pub. Co., Amsterdam, 1974, pp. 580-583.
• 4: BEERI, C. On the membership problem for multivalued dependencies in relational databases. Tech. Rep. 229, Dept. Elec. Eng. and Comptr. Sci., Princeton U., Princeton, N.J., 1977.
• 5: BEERI, C. On the role of data dependencies in the construction of relational database schemas. Tech. Rep. 43, Dept. Comptr. Sci., The Hebrew University, Jerusalem, Israel, 1979.
• 6: BEERI, C., BERNSTEIN, P., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. Proc. 4th Int. Conf. on Very Large Data Bases, West Berlin, 1978, pp. 113-124.
• 7: 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]
• 8: Catriel Beeri , Alberto O. Mendelzon , Yehoshua Sagiv , Jeffrey D. Ullman, Equivalence of relational database schemes, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.319-329, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804424]
• 9: 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]
• 10: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 11: 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]
• 12: DELOBEL, C. Contributions theoretiques a-la conception et a l'evaluation d'un systeme d'informations applique a la gestion. These d'Etat, U. of Grenoble, Grenoble, France, 1973.
• 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: 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]
• 15: HAGIHARA, K., Iwo, M., TANIGUCHI, K., AND KASAMI, T. Decision problems for multivalued dependencies in relational databases. SIAM J. Comptng. 8, 2 (May 1979), 247-264.
• 16: MAIER, D., MENDELZON, A.O., SADRI, F., AND ULLMAN, J.D. Adequacy of decompositions of relational databases. Unpub. manuscript.
• 17: 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]
• 18: RISSANEN, J. Theory of relations for databases--a tutorial survey. Proc. 7th Syrup. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 64, Springer- Verlag, 1978, pp. 536-551.
• 19: SAGIV, Y. An algorithm for inferring multivalued dependencies that works also for a subclass of propositional logic. Rep. UIUCDCS-R-79-954, Dept. Comptr. Sci., U. of Illinois, Urbana-Champaign, Ill., 1979.
• 20: 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

General Terms:
Design

Keywords:
chase, data dependencies, functional dependencies, join dependencies, multivalued dependencies, relational databases, tableaux