David Maier
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.
- 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.Google Scholar
- 2 AHO, A,V,, SAGIV, Y., AND ULLMA~, J.D. Equivalence of relational expressions. SIAM J. Comping. 8, 2 (May 1979), 218-246.Google ScholarCross Ref
- 3 ARMSTRONG, W.W. Dependency structures of data base relationships. Proc. IFIP '74, North- Holland Pub. Co., Amsterdam, 1974, pp. 580-583.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 7 BEERI, C., FAt}IN, R., AND HOWARD, J. A complete axiomatization for functional and multivalued dependencies. Proc. ACM-SIGMOD Conf., Toronto, Canada, 1977, pp. 47-61. Google ScholarDigital Library
- 8 BEERI, C., MENDELZON, A.O., SAGIV, Y., AND ULLMAN, J.D. Equivalence of relational database schemes. Proc. 11th ACM Syrup. on Theory of Computing, Atlanta, Ga., 1979, pp. 319-329. See also Tech. Rep. 252, Dept. Elec. Eng. and Comptr. Sci., Princeton U., Princeton, N.J., 1978. Google ScholarDigital Library
- 9 BERNSTEIN, P.A. Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst. I, 4 (Dec. 1976), 277-298. Google ScholarDigital Library
- 10 CHANDRA, A.K., AND M~RLIN, P.M. Optimal implementation of conjunctive queries in relational databases. Proc. 9th Ann. ACM Syrup. on Theory of Computing, Boulder, Colo., 1976, pp. 77-90. Google ScholarDigital Library
- 11 CODD, E.F. A relational model for large shared data banks. Comm. ACM 13, 6 (June 1970), 377-387. Google ScholarDigital Library
- 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.Google Scholar
- 13 FAGIN. R. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst. 2, 3 (Sept. 1977), 262-278. Google ScholarDigital Library
- 14 FAGIN, R. Normal forms and relational database operators. Proc. ACM-SIGMOD Conf., Boston, Mass., 1979, pp. 153-160. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 16 MAIER, D., MENDELZON, A.O., SADRI, F., AND ULLMAN, J.D. Adequacy of decompositions of relational databases. Unpub. manuscript.Google Scholar
- 17 RISSANEN, J. Independent components of relations.ACM Trans. Database Syst. 2, 4 (Dec. 1977), 317-325. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 20 ZANIOLO, C. Analysis and design of relational schemata for database systems. Tech. Rep. UCLA- ENG-7769, Ph.D. Th., Dept. Comptr. Sci., U. of California, Los Angeles, Calif., 1976. Google ScholarDigital Library
Index Terms
- Testing implications of data dependencies
Recommendations
Data dependencies for query optimization: a survey
AbstractEffective query optimization is a core feature of any database management system. While most query optimization techniques make use of simple metadata, such as cardinalities and other basic statistics, other optimization techniques are based on ...
On the design of relational database schemata
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 ...
Comments