Database Reference
In-Depth Information
t'
j
t'
j+x
t'
j
...
O'
O'
t
i
t
i+1
t
i+2
t
i
t
i+1
t
i+2
O
O
L
i+1
U
i+2
U
L
i
U
i+1
L
U
L
i
U
i+1
L
i+1
U
i+2
L
i
i+2
i
i+2
(b) Case 2.
(a) Case 1.
Fig. 6.3
Two cases in the proof of Theorem 6.7.
Lemma 6.3 (Monotonicity).
Let t
i
,t
i
+
1
and t
i
+
2
be three consecutive intervals in
the
Pr
k
Pr
k
φ
-quantile summary of W
(
O
)
. Let
L
(
(
t
i
))
and
U
(
(
t
i
+
2
))
be the lower
bound of Pr
k
and the upper bounds of Pr
k
(
t
i
)
(
t
i
+
2
)
, respectively, derived from
Theorem 6.6. If for any interval t
in the
-quantile summary of O
(
O
=
φ
O
)
,
t
.
MIN, t
.
Pr
k
Pr
k
MAX
>
t
i
.
MIN
>
t
i
+
2
.
MAX, then
L
(
(
t
i
))
≥U
(
(
t
i
+
2
))
.
t
|
t
∈
O
,
t
.
Proof.
For intervals
t
i
and
t
i
+
2
,wehave
LDS
(
t
i
)=
{
MAX
>
t
i
.
MIN
}
,
t
|
t
∈
O
,
t
.
and
UDS
(
t
i
+
2
)=
{
MIN
≥
t
i
+
2
.
MAX
}
. Using the assumption in the
Pr
k
Pr
k
lemma, we have
LDS
(
t
i
)
⊂
UDS
(
t
i
+
2
)
. Thus,
L
(
(
t
i
))
≥U
(
(
t
i
+
2
))
.
We consider the following two cases:
Case 1.
For any interval
t
and
t
∈
O
)(
O
=
,if
t
.
∈
W
(
O
)
W
(
O
)
MAX
>
t
.
MAX
,
then
t
.
MIN
, as illustrated in Figure 6.3(a). Lemma 6.3 holds in this case.
According to the definitions of
MIN
>
t
.
Pr
k
Pr
k
Pr
k
U
(
(
O
))
and
L
(
(
O
))
,
U
(
(
O
)) =
1
i
1
Pr
k
Pr
k
i
Pr
k
U
(
(
t
i
))
and
L
(
(
O
)) =
∑
L
(
(
t
i
))
. Thus,
∑
=
1
=
1
Pr
k
Pr
k
U
(
(
O
))
−L
(
(
O
))
1
φ
−
i
=
1
U
(
Pr
k
2
Pr
k
Pr
k
=
(
))
−L
(
(
))
+
U
(
(
))
(6.2)
t
i
+
2
t
i
t
1
Pr
k
Pr
k
Pr
k
+
U
(
(
))
−L
(
(
))
−L
(
(
φ
))
t
2
t
1
φ
−
t
1
1
Using Lemma 6.3, we have
i
=
1
U
(
t
i
))
<
1
φ
−
2
Pr
k
Pr
k
(
t
i
+
2
))
−L
(
(
0.
∑
Thus, we have
Pr
k
Pr
k
U
(
(
O
))
−L
(
(
O
))
(6.3)
< U
(
Pr
k
Pr
k
Pr
k
Pr
k
(
t
1
))+
U
(
(
t
2
))
−L
(
(
t
1
φ
−
))
−L
(
(
t
1
φ
))
1
1
φ
Also, for 1
≤
i
≤
,
Pr
(
t
i
)=φ
and
Pr
k
Pr
k
≤U
(
(
))
≤
(
)
≤L
(
(
))
≤
(
)
0
t
i
Pr
t
i
and 0
t
i
Pr
t
i
.
Thus, we have
U
(
Pr
k
Pr
k
Pr
k
Pr
k
(
t
1
))+
U
(
(
t
2
))
−L
(
(
t
1
φ
−
1
))
−L
(
(
t
1
φ
))
≤
2
φ
(6.4)
Plugging Inequalities 6.3 and 6.4 into Equation 6.2, we get
