
182 Automated Physical Database Design and Tuning
OR
OR
OR
OR
AND
AND
ρ
1
ρ
2
ρ
5
ρ
3
ø
ø
ø
AND
OR
ρ
2
ρ
1
ρ
3
ρ
5
FIGURE 10.2 (Continued)
ρ
5
in Figure 10.2b). However, these requests are orthogonal to the requests in
P’s left subplan, and thus we return the AND/OR tree of case 3. Finally, if the
root P is not a join node, the request ρ conflicts with any request in a subplan
of P (we cannot implement both alternatives), and therefore we return the
AND/OR tree of case 4.
buildAOT (P:Execution Plan)
return AND/OR tree for P
1 if (P.isLeaf) // Case 1
2 return P.request
3 else if (P.request is null) // Case 2
4 return AND(buildAOT(P.child
1
), ..., buildAOT(P.child
n
))
5 else if (P.isJoin) ...