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