Efficient optimization of a class of relational expressions

ABSTRACT

The design of several database query languages has been influenced by Codd's relational algebra. This paper discusses the difficulty of optimizing queries based on the relational algebra operations select, project, and join. A matrix, called a tableau, is proposed as a useful device for representing the value of a query, and optimization of queries is couched in terms of finding a minimal tableau equivalent to a given one. Functional dependencies can be used to imply additional equivalences among tableaux. Although the optimization problem is NP-complete, a polynomial time algorithm exists to optimize tableaux that correspond to an important subclass of queries.

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: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: AHo, A.V., SAlty, Y., AND ULLMAN, J.D. Equivalences among relational expressions. SIAM J. Comptg. 8, 2 (May 1979), 218-246.
• 4: AHO, A.V., SAGIV, Y., SZYMANSKI, T.G., ANY ULLMAN, J.D. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. Proc. 16th Ann. Allerton Conf. on Commun., Contr. and Comptg., Oct. 1978, pp. 54-63.
• 5: ARMSTRONG, W.W. Dependency structures of data base relationships. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 580-583.
• 6: 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]
• 7: Joachim Biskup , Umeshwar Dayal , Philip A. Bernstein, Synthesizing independent database schemas, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582118]
• 8: 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]
• 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, R. Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 33-64.
• 11: CODD, E.F. Relational completeness of data base sublanguages. In Data Base Systems, R. Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 65-98.
• 12: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 13: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 14: DELOBEL, C. Contributions theoretiques a la conception d'un systeme d'informations. Ph.D. Th., U. of Grenoble, Grenoble, France, Oct. 1973.
• 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: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 17: HALL, P.A.V. Optimization of a single relational expression in a relational database system. IBM J. Res. Develop. {May 1976}, 244-257.
• 18: KARP, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85-104.
• 19: 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]
• 20: MINKER, J. Performing inferences over relational databases. Tech. Rep. TR363, Dept. of Comptr. Sci., U. of Maryland, College Park, Md., March 1975.
• 21: PALERMO, F.P. A database search problem. In Information Systems COINS IV, J.T. Tou, Ed., Plenum Press, New York, 1974.
• 22: PECHERER, R.M. Efficient evaluation of expressions in a relational algebra. Proc. ACM Pacific Conf., April 1975, pp. 44-49.
• 23: SACXV, Y., AND YANNAKAKm, M. Equivalence among relational expressions with the union and difference operations. Proc. Fourth Int. Conf. on Very Large Data Bases, 1978, pp. 535-548.
• 24: John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
• 25: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 26: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 27: ZANIOLO, C. Analysis and design of relational schemata for database systems. Tech. Rep. UCLA- ENG-7769, Dept. of Comptr. Sci., U. of California, Los Angeles, Calif., July 1976.
• 28: ZLOOF, M.M. Query.by-example: The revocation and definition of tables and forms. Proc. ACM Int. Conf. on Very Large Data Bases, Sept. 1975, pp. 1-24.

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.4 Systems
          Subjects: Query processing

General Terms:
Design

Keywords:
NP-completeness, equivalence of queries, query optimization, relational algebra, relational database, tableaux