A. V. Aho
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.
- 1 AHO, A.V., BEERI, C., AND ULLMAN, J.D. The theory of joins in relational databases. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 297-314. Google Scholar
Digital Library
- 2 AHO, A.V., HOPCROFT, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google ScholarDigital Library
- 3 AHo, A.V., SAlty, Y., AND ULLMAN, J.D. Equivalences among relational expressions. SIAM J. Comptg. 8, 2 (May 1979), 218-246.Google Scholar
- 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.Google Scholar
- 5 ARMSTRONG, W.W. Dependency structures of data base relationships. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 580-583.Google Scholar
- 6 BEERI, C., FAGIN, R., AND HOWARD, J.H. A complete axiomatization for functional and multivalued dependencies in database relations. Proc. ACM SIGMOD Int. Conf. on Manage. of Data, Toronto, Canada, 1977, pp. 47-61. Google ScholarDigital Library
- 7 BISKUP, J., DAYAL, U., AND BERNSTEIN, P.A. Synthesizing independent database schemas. Proc. ACM SIGMOD Conf., 1979, pp. 143-151. Google ScholarDigital Library
- 8 CHANDRA, A.K., AND MERLIN, P.M. Optimal implementation of conjunctive queries in relational data bases. Proc. Ninth Ann. ACM Syrup. on Theory of Comptg., May 1976, pp. 77-90. Google ScholarDigital Library
- 9 CODD, E.F. A relational model for large shared data banks. Comm. ACM 13, 6 (June 1970), 377- 387. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 12 COOK, S.A. The complexity of theorem proving procedures. Proc. 3rd Ann. ACM Syrup. on Theory of Comptg., May 1971, pp. 151-158. Google ScholarDigital Library
- 13 DATE, C.J. An Introduction to Database Systems. Addison-Wesley, Reading, Mass., 1975. Google ScholarDigital Library
- 14 DELOBEL, C. Contributions theoretiques a la conception d'un systeme d'informations. Ph.D. Th., U. of Grenoble, Grenoble, France, Oct. 1973.Google Scholar
- 15 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
- 16 GAREY, M.R., AND JOHNSON, D.S. Computers and Intractability: A Guide to the Theory of NP- Completeness. Freeman, San Francisco, 1978. Google ScholarDigital Library
- 17 HALL, P.A.V. Optimization of a single relational expression in a relational database system. IBM J. Res. Develop. {May 1976}, 244-257.Google Scholar
- 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.Google ScholarCross Ref
- 19 MAIER, D., MENDELZON, A., AND SAGIV, V. Testing implications of data dependencies. ACM Trans. Database Syst. 4, 4 (Dec. 1979), 455-469. Google ScholarDigital Library
- 20 MINKER, J. Performing inferences over relational databases. Tech. Rep. TR363, Dept. of Comptr. Sci., U. of Maryland, College Park, Md., March 1975.Google Scholar
- 21 PALERMO, F.P. A database search problem. In Information Systems COINS IV, J.T. Tou, Ed., Plenum Press, New York, 1974.Google Scholar
- 22 PECHERER, R.M. Efficient evaluation of expressions in a relational algebra. Proc. ACM Pacific Conf., April 1975, pp. 44-49.Google Scholar
- 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.Google Scholar
- 24 SMITH, J.M., AND CHANO, P.Y.-T. Optimizing the performance of a relational algebra database interface. Comm. ACM 18, I0 (Oct. 1975), 568-579. Google ScholarDigital Library
- 25 ULLMAN, J. D. Principles of Database Systems. Computer Sciences Press, Potomac, Md., 1979. Google ScholarDigital Library
- 26 WOlqG, E., AND YOUSSEFI, K. Decomposition--a strategy for query processing. A CM Trans. Database Syst. 1, 3 (Sept. 1976), 223-241. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Efficient optimization of a class of relational expressions
Recommendations
Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions
An important step in the optimization of queries in relational databases is minimizing the number of join operations in the evaluation of a query. It is shown that three subclasses of tableaux (including the subclass of simple tableaux) have $O(n^2 )$ ...
Some properties of relational expressions
ACM-SE 17: Proceedings of the 17th annual Southeast regional conferenceWe obtain certain results concerning the power of expressions in relational (calculus and algebra) database sublanguages. Our main results state the undecidability of the equivalence and finite equivalence problems for relational expressions. We also ...
Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries
In this paper, we present a translator from a relevant subset of SQL into relational algebra. The translation is syntax-directed, with translation rules associated with grammar productions; each production corresponds to a particular type of SQL ...
Comments