Efficient optimization of a class of relational expressions
- 1 December 1979
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 4 (4) , 435-454
- https://doi.org/10.1145/320107.320112
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.Keywords
This publication has 11 references indexed in Scilit:
- Testing implications of data dependenciesACM Transactions on Database Systems, 1979
- The theory of joins in relational databasesACM Transactions on Database Systems, 1979
- Synthesizing independent database schemasPublished by Association for Computing Machinery (ACM) ,1979
- Multivalued dependencies and a new normal form for relational databasesACM Transactions on Database Systems, 1977
- Optimal implementation of conjunctive queries in relational data basesPublished by Association for Computing Machinery (ACM) ,1977
- A complete axiomatization for functional and multivalued dependencies in database relationsPublished by Association for Computing Machinery (ACM) ,1977
- Decomposition—a strategy for query processingACM Transactions on Database Systems, 1976
- Optimizing the performance of a relational algebra database interfaceCommunications of the ACM, 1975
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- A relational model of data for large shared data banksCommunications of the ACM, 1970