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