Efficient optimization of simple chase join expressions

ABSTRACT

Simple chase join expressions are relational algebra expressions, involving only projection and join operators, defined on the basis of the functional dependencies associated with the database scheme. They are meaningful in the weak instance model, because for certain classes of schemes, including independent schemes, the total projections of the representative instance can be computed by means of unions of simple chase join expressions. We show how unions of simple chase join expressions can be optimized efficiently, without constructing and chasing the corresponding tableaux. We also present efficient algorithms for testing containment and equivalence, and for optimizing individual simple chase join expressions.

REFERENCES

• 1: AHO, A. V., SAGW, Y., AND ULLMAN, J. D. Equivalence of relational expressions. SIAM J. Comput. 8, 2 (May 1979), 218-246
• 2: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 3: Paolo Atzeni , Edward P. F. Chan, Efficient query answering in the representative instance approach, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.181-188, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325429]
• 4: Paolo Atzeni , D. Stott Parker, Jr., Assumptions in relational database theory, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588113]
• 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: Edward Ping Fung Chan, Query answering and schema analysis under the weak instance model, 1984
• 7: E P F Chan , Paolo Atzeni, On the properties and characterization of connection-trap-free schemes, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.140-147, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15411]
• 8: Edward P. F. Chan , Alberto O. Mendelzon, Answering queries on embedded-complete database schemes, Journal of the ACM (JACM), v.34 n.2, p.349-375, April 1987 [doi>10.1145/23005.23007]
• 9: Edward P. F. Chan , Alberto O. Mendelzon, Independent and separable database schemes, SIAM Journal on Computing, v.16 n.5, p.841-851, Oct. 1987 [doi>10.1137/0216055]
• 10: Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
• 11: GRAHAM, M. H., AND MENDELZON, A.O. Strong equivalence of relationaI expressions under dependencies. Inf. Process. Lett. 14, 2 (Apr. 1982), 57-62.
• 12: GRAHAM, M. H., AND YANNAKAKIS, M. Independent database schemas. J. Comput. Syst. Sci. 28, 1 (1984), 121-141.
• 13: HONEYMAN, P. Extension joins. In Sixth International Conference on Very Large Data Bases (Montreal, Oct. 1-3, 1980). IEEE, New York, 1980, pp. 239-244.
• 14: Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982 [doi>10.1145/322326.322330]
• 15: ITO, M., IWASAKI, M., AND KASAMI, T. Some results on the representative instance in relational databases. SIAM d. Comput. 14, 2 (May 1985), 334-354.
• 16: W. Kent, Consequences of assuming a universal relation, ACM Transactions on Database Systems (TODS), v.6 n.4, p.539-556, Dec. 1981 [doi>10.1145/319628.319630]
• 17: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 18: 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]
• 19: MAIER, D., ROZENSHTEIN, O., AND WARREN, D.S. Windows functions. In Advances in Computing Research, Vol. 3. P. C. Kanellakis and F. Preparata, Eds. JAI Press, Greenwich, Conn., 1986, pp. 213-246.
• 20: David Maier , Jeffrey D. Ullman , Moshe Y. Vardi, On the foundations of the universal relation model, ACM Transactions on Database Systems (TODS), v.9 n.2, p.283-308, June 1984 [doi>10.1145/329.318580]
• 21: Alberto O. Mendelzon, Database states and their tableaux, ACM Transactions on Database Systems (TODS), v.9 n.2, p.264-282, June 1984 [doi>10.1145/329.318579]
• 22: Yehoshua Sagiv, Can we use the universal instance assumption without using nulls?, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582336]
• 23: Yehoshua Sagiv, A characterization of globally consistent databases and their correct access paths, ACM Transactions on Database Systems (TODS), v.8 n.2, p.266-286, June 1983 [doi>10.1145/319983.319988]
• 24: SAGIV, Y. Evaluation of queries in independent database schemes. 1984. Unpublished manuscript.
• 25: SAGIV, Y. Quadratic algorithms for minimizing joins in restricted relational expressing. SIAM J. Comput. 12, 2 (May 1983), 316-328.
• 26: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 27: Jeffrey D. Ullman, The U. R. strikes back, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588114]
• 28: ULLMAN, J.D. Universal relation interfaces for database systems. In IFIP Congress (Paris, Sept. 19-23, 1983). North-Holland, Amsterdam, 1983, pp. 243-252.
• 29: YANNAKAKIS, M. Algorithms for acyclic database schemes. In Seventh International Conference on Very Large Data Bases (Cannes, Sept. 9-11, 1981). IEEE, New York, 1981, pp. 82-94.
• 30: YANNAKAKIS, M. Querying weak instances, in Advances in Computing Research, Voi. J. v'. L;. Kanellakis and F. Preparata, Eds. JAI Press, Greenwich, Conn., 1986, pp. 185-211.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

General Terms:
Algorithms, Languages, Performance, Theory