Database Reference
In-Depth Information
In order to update
L
complete
and
L
open
, the following two subcases arise. First,
if
t
i
is not the last tuple in
R
(i.e.,
t
i
=
t
r
m
0
m
), then we update
rule-tuple
t
R
left
by compressing
t
i
into
t
R
left
, using the methods discussed in Sec-
tion 5.1.3. If
t
R
left
is not in
L
open
, then we add
t
R
left
into
L
open
. Moreover, we sort
the rule-tuples in
L
open
in their next tuple indices descending order. Second, if
t
i
is the last tuple in
R
, which means that the rule-tuple
t
R
will never be updated
later. Therefore, we remove
t
R
left
from
L
open
, and add
t
R
into
L
complete
.
The subset probabilities of the tuples in
L
complete
only need to be calculated once
and can be reused by all tuples ranked lower than them. In contrast, the rule-tuples
in
L
open
may be updated when other tuples in the same rule are scanned. Therefore,
only part of the subset probabilities can be reused.
For two consecutive tuples
t
i
and
t
i
+
1
in the sorted list
L
of all tuples in
T
, let
where 1
≤
m
0
<
L
(
t
i
)
and
L
(
t
i
+
1
)
be the sorted lists of the tuples in
T
(
t
i
)
and
T
(
t
i
+
1
)
, respectively,
given by the aggressive reordering method. Let
Pre f ix
(
L
(
t
i
)
,
L
(
t
i
+
1
))
be the longest
common prefix between
L
(
t
i
)
and
L
(
t
i
+
1
)
. The total number of subset probability
n
−
1
i
=
1
(
|
values needed to be calculated is
Cost
=
∑
L
(
t
i
+
1
)
|−|
Pre f ix
(
L
(
t
i
)
,
L
(
t
i
+
1
))
|
)
.
tuple Aggressive reordering
Lazy reordering
Prefix
Cost
Prefix
Cost
t
1
0
0
0
0
t
2
0
0
0
0
t
3
t
1
,
2
1
t
1
,
2
1
t
4
t
3
t
1
,
2
2
t
1
,
2
t
3
1
t
5
t
3
t
1
,
2
0
t
1
,
2
t
3
0
t
6
t
3
t
4
,
5
t
1
,
2
2
t
1
,
2
t
3
t
4
,
5
1
t
7
t
3
t
6
t
4
,
5
t
1
,
2
3
t
1
,
2
t
3
t
4
,
5
t
6
1
t
8
t
3
t
6
t
7
t
4
,
5
2
t
3
t
6
t
7
t
4
,
5
4
t
9
t
3
t
6
t
7
t
1
,
2
,
8
t
4
,
5
2
t
3
t
6
t
7
t
4
,
5
t
1
,
2
,
8
1
t
10
t
3
t
6
t
7
t
9
t
1
,
2
,
8
2
t
3
t
6
t
7
t
9
t
1
,
2
,
8
2
t
11
t
3
t
6
t
7
t
9
t
4
,
5
,
10
1
t
3
t
6
t
7
t
9
t
4
,
5
,
10
1
Total cost: 15
Total cost: 12
Table 5.1
Results of reordering techniques.
Example 5.2 (Aggressive reordering).
Consider a list of ranked tuples
t
1
,···,
t
11
with
two multi-tuple rules
R
1
:
t
1
⊕
t
10
. The compressed
dominant sets of tuples in the orders made by the aggressive reordering method is
listed in Table 5.1.
For example, before scanning
t
6
,
L
complete
contains independent tuple
t
3
and
L
open
contains rule-tuples
t
4
,
5
and
t
1
,
2
.
t
4
,
5
is ranked before
t
1
,
2
, since the next tuple in
R
2
,
t
10
, is ranked lower than
R
1
's next tuple
t
8
. Since
t
6
is independent, the compressed
dominant set of
t
6
includes all 3 tuples in
L
complete
and
L
open
.
T
t
2
⊕
t
8
⊕
t
11
and
R
2
:
t
4
⊕
t
5
⊕
only
share the common prefix
t
3
, therefore, the cost of calculating the subset probabilities
for
T
(
t
6
)
and
T
(
t
5
)
(
t
6
)
is 3
−
1
=
2. After scanning
t
6
,
t
6
is added into
L
complete
.
