Chapter 18: Algorithms for Query Processing and Optimization
1
CHAPTER 18: ALGORITHMS FOR QUERY PROCESSING AND OPTIMIZATION
Answers to Selected Exercises
18.13 – Consider SQL queries Q1, Q8, Q1B, Q4, Q27 in Chapter 5.
(a) Draw at least two query trees that can represented each of these queries.
Under what circumstances would you use each of your query trees?
(b) Draw the initial query tree for each of these queries; then show how the
query tree is optimized by the algorithm outlined in section 19.7.
(c) For each query, compare your on query trees of part (a) and the initial and
final query trees of part (b).
Answer:
Below are possible answers for Q8 and Q27.
Q8: SELECT E.FNAME, E.LNAME, S.FNAME, S.LNAME
FROM EMPLOYEE E, EMPLOYEE S
WHERE E.SUPERSSN = S.SSN
Q27: SELECT FNAME, LNAME, 1.1*SALARY
The initial query tree for Q8 is the same as tree2 above; the only change made by the
optimization algorithm is to replace the selection and Cartesian product by the join in
tree1. Thus, tree 1 is the result after optimization.
Q27’s tree1:
PROJECT FNAME, LNAME, SALARY
PNO=PNUMBER JOIN
EMPLOYEE PROJECT
Copyright © 2016 Pearson Education, Inc., Hoboken NJ
page 613) so that the more restrictive selects are executed first.
18.14 – A file of 4096 blocks is to be sorted with an available buffer space of 64 blocks. How
many passes will be needed in the merge phase of the external sort-merge algorithm?
Answer:
We first need to compute the number of runs, n , in the merge phase.
R
Using the formula in the text, we have
