Please use this identifier to cite or link to this item:
Title: On the optimality of strategies for multiple joins
Authors: Tay, Y.C. 
Issue Date: Nov-1993
Citation: Tay, Y.C. (1993-11). On the optimality of strategies for multiple joins. Journal of the ACM 40 (5) : 1067-1086. ScholarBank@NUS Repository.
Abstract: Relational database systems rely on the join operator to assemble data for answering queries. Although the order of (natural) joins - here called the strategy for computing the joins - does not affect the final result, it does determine to a large extent the response time of the query. Query optimizers therefore try to pick an optimal strategy. In practice, optimizers usually restrict their search for an optimal strategy to strategies that are linear or that avoid Cartesian products, or both. The purpose of this paper is to examine the conditions under which an optimizer can find an optimal strategy, despite having restricted the scope of its search. Specifically, sufficient conditions are given under which (1) a linear strategy that is optimum will not use Cartesian products, (2) there is an optimum strategy that does not use Cartesian products, and (3) there is an optimum strategy that is linear and that does not use Cartesian products. (Optimality is with respect to the number of tuples generated by a strategy.) The necessity of these conditions is illustrated through examples. The conditions do not assume uniformity in the distribution of attribute values, nor independence in the attributes. Instead, they are either a formalization of heuristic assumptions, or based on semantic constraints. For example, the conditions are satisfied if all join attributes form superkeys. The analytic framework can be adapted for database acyclicity, lossless joins, unions, and intersections.
Source Title: Journal of the ACM
ISSN: 00045411
DOI: 10.1145/174147.174151
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Mar 4, 2021


checked on Feb 24, 2021

Page view(s)

checked on Feb 28, 2021

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.