Continuous Physical Database Design - Automated Physical Database Design and Tuning - page 182

AND

AND

OR

ρ 3

OR OR

OR

ρ 1 ρ 5

ρ 2 ø

ø ø

AND

OR

ρ 1

ρ 2

ρ 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

return P . request

2

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) // Case 3

6 return AND( buildAOT ( P . leftChild),

OR( P . request,
buildAOT ( P . rightChild)))

7 else // Case 4

return OR( P . request, buildAOT ( P . child))

8

FIGURE 10.3 Building the AND/OR request tree. (Used with permission
from Bruno, N. & Chaudhuri, S. In Proceedings of the International Confer-
ence on Very Large Databases [VLDB] , 2006.)