Database Reference
In-Depth Information
cost
(
W
, C A ,
i +1
,
j
)>
cost
(
W
, C O ,
i +1
,
j
)
. (Note that if
C A contains no index
C A C O = C n
C n =
creations or deletions,
0 as well.) Now consider line 5
(case A 2). Algorithm Opt-SI generates a subschedule
n >
C O =
(
,
,... ,
)
1
1
1
from
C A that contains at least
i +1 to j . Suppose there is an alternative schedule
one index deletion. Then:
C A
C 1
b I
C 2
C 3
b I
C 4
...
C n
[
b I
C n + 1
]
C O
b I
C 1
C 2
C 3
C 4
...
C n
[
C n + 1
]
C A -
C O
δ 1
δ 3
b I
...
δ n
[
b I
]
Similar to the analysis for case A 1, we can show that
δ 1
>
0,
δ n
>
0, and
| δ i | <
b I for the remaining cases. If C A contains no index creations or dele-
C A C O = C n
C n =
tions,
n >
0 as well. Putting it all together, we again have
that cost
. We can prove case A 3 with
the same argument as for case A 1, and cases B 1 through B 3 can be proved
analogously to cases A 1 through A 3.
(
W
, C A ,
i +1
,
j
)>
cost
(
W
, C O ,
i +1
,
j
)
10.2.1.1
Online Algorithm
A careful look at algorithm Opt-SI in Figure 10.5 reveals the following prop-
erty. Suppose that at some iteration we add a configuration block of C i =0.
Algorithm Opt-SI will then transition to C =1 if
i , j
>
b I for the smallest
j <
j . Another way of ob-
taining this behavior is to maintain the minimum value of
j
>
i , and
i , j
does not goes below zero for i
<
0 , i since Opt-SI
min ) and to transition to C =1 if
lastly transitioned to C =0 (let us call it
there is j
>
i such that
0 , j
> min + b I and no j <
j satisfies
0 , j < min .
Similarly, if C =1, we maintain the maximum value of
0 , i since Opt-SI lastly
transitioned to C =1 (let us call it max ), and transition to C =0 if there is a
j
b I and no j <
j satisfies 0 , j > max .
This alternative formulation of Opt-SI suggests an online algorithm. We
maintain min and max as explained already, but instead of looking into the
(unknown) future we transition configurations after gathering the information
that proves that the optimal strategy would have done so at a past point in
time. Algorithm Online-SI is shown in Figure 10.7. We note that in line 1
we need to obtain the expected cost of the input query under the “opposite”
configuration. We do that without issuing an additional optimization call by
using the getCost function (introduced at the beginning of this section) over
the request that used (or could have used) index I . Note that we store a
constant amount of information per index (i.e.,
>
i such that 0 , j < max
,
min , and
max ). Also,
every time we execute a query we update only
values, whose cost is negligible
compared with that of executing the actual queries.
Competitive analysis: Conceptually, algorithm Online-SI lags behind
Opt-SI and modifies physical designs only after the evidence that
Search WWH ::

Custom Search