Database Reference
In-Depth Information
Δ(W,C,0,t)
Δ 0 +b I 0
Case A2
Case A3
Case A1
Δ 0
Case B1
Case B3
Case B2
Δ 0 -b I 0
t
i
n
0 and j <
Case A1:
j > i such that i , j
j ,0 < i , j < b I
b I and j <
Case A2:
j > i such that i , j
j ,0 < i , j < b I
Case A3:
i <
j n , 0 < i , j
< b I
0 and j <
Case B1:
j > i such that i , j
j , b I
< i , j < 0
≤− b I and j <
Case B2:
j > i such that i , j
j , b I
< i , j < 0
Case B3:
i <
j n , b I
< i , j
< 0
FIGURE 10.6 Possible behavior of i , n . (Used with permission
from Bruno, N. & Chaudhuri, S. In Proceedings of the International Con-
ference on Data Engineering [ICDE] , 2007.)
with no index ( C =0), continues with a strict alternation between blocks of
configurations with the index ( C =1) and without it ( C =0), and optionally
ends with a block of configurations with the index ( C =1). Let us obtain the
difference in cost between subschedules C A and C O :
C A
C 1
b I
C 2
C 3
b I
C 4
...
C n
[
b I
C n + 1
]
C 1
C 2
C 3
C 4
C n
C n + 1
C O
b I
...
[
]
C A -
C O
δ 1
δ 3
b I
...
δ n
[
b I
]
where C i and C i denote the partial cost of the blocks with configuration
C =0 and C =1, respectively. Before switching from C =0 to C =1 in
C A ,we
add b I , the cost of creating I . Also, the final costs between brackets represent
the optional block with C =1. Consider now
δ 1 . According to its definition,
i
δ 1 =
i , i
for some i
<
j . By definition of case A 2 , we know that
δ 1
>
0. Similarly, it can be shown that
δ n =
j , j
>
0, and for each 1
<
k
<
n ,
| δ k |≤
b I (see Figure 10.6 for additional intuition). Putting it all together,
Search WWH ::




Custom Search