Consider SQL queries Q1, Q8, Q1B, Q4, Q27 in Chapter 5.

Question

(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 1

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
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE SSN = ESSN AND PNO = PNUMBER AND PNAME = 'ProductX'
Q8's tree1:
PROJECT E.FNAME, E.LNAME, S.FNAME, S.LNAME
E.SUPERSSN=S.SSN JOIN
EMPLOYEE E EMPLOYEE S
Q8'S tree2:
PROJECT
CARTESIAN PRODUCT
EMPLOYEE E EMPLOYEE S
E.FNAME, E.LNAME, S.FNAME, S.LNAME
SELECT E.SUPERSSN=S.SSN
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
SSN=ESSN JOIN SELECT PNAME="ProductX"
WORKS_ON
Q27's tree2:
PROJECT FNAME, LNAME, SALARY
PNO=PNUMBER AND SSN=ESSN AND PNAME="ProductX" SELECT
EMPLOYEE
PROJECT
CARTESIAN PRODUCT
WORKS_ON
CARTESIAN PRODUCT
The initial query tree of Q27 is tree2 above, but the result of the heuristic optimization
process will NOT be the same as tree1 in this case. It can be optimized more thoroughly,
as follows:
PROJECT FNAME, LNAME, SALARY
PNO=PNUMBER JOIN EMPLOYEE
PROJECT
SSN=ESSN JOIN
SELECT PNAME="ProductX" WORKS_ON
The reason is that the leaf nodes could be arranged (in Step 3 of the algorithm outlined on
page 613) so that the more restrictive selects are executed first.