Database Reference
InDepth 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
OptSI
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
OptSI
in Figure 10.5 reveals the following prop
erty. Suppose that at some iteration we add a configuration block of
C
i
=0.
Algorithm
OptSI
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
OptSI
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
OptSI
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
OptSI
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
OnlineSI
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
OnlineSI
lags behind
OptSI
and modifies physical designs only after the evidence that
Search WWH ::
Custom Search