Optimization of nested SQL queries revisited

RA Ganski, HKT Wong - ACM SIGMOD Record, 1987 - dl.acm.org
RA Ganski, HKT Wong
ACM SIGMOD Record, 1987dl.acm.org
Current methods of evaluating nested queries in the SQL language can be inefficient in a
variety of query and data base contexts. Previous research in the area of nested query
optimization which sought methods of reducing evaluation costs is summarized, including a
classification scheme for nested queries, algorithms designed to transform each type of
query to a logically equivalent form which may then be evaluated more efficiently, and a
description of a major bug in one of these algorithms. Further examination reveals another …
Current methods of evaluating nested queries in the SQL language can be inefficient in a variety of query and data base contexts. Previous research in the area of nested query optimization which sought methods of reducing evaluation costs is summarized, including a classification scheme for nested queries, algorithms designed to transform each type of query to a logically equivalent form which may then be evaluated more efficiently, and a description of a major bug in one of these algorithms. Further examination reveals another bug in the same algorithm. Solutions to these bugs are proposed and incorporated into a new transformation algorithm, and extensions are proposed which will allow the transformation algorithms to handle a larger class of predicates. A recursive algorithm for processing a general nested query is presented and the action of this algorithm is demonstrated. This algorithm can be used to transform any nested query.
ACM Digital Library