Database Reference
In-Depth Information
First, if
t
i
−
1
is independent, then
T
(
t
i
)
can be obtained by adding
t
i
−
1
to the
rear of
T
.
Second, if
t
i
−
1
is involved in a multi-tuple generation rule
R
, then
T
(
t
i
−
1
)
(
t
i
)
is
.
Case 2:
If
t
i
is involved in a multi-tuple generation rule
R
but not the first tuple
scanned in
R
, then there are three subcases.
First, if
t
i
−
1
is involved in the same rule with
t
i
, then
T
computed by adding
t
R
left
to the rear of
T
(
t
i
−
1
)
(
t
i
)=
T
(
t
i
−
1
)
.
Second, if
t
i
−
1
is an independent tuple, then
T
(
t
i
−
1
)
must contain a rule-tuple
t
R
left
corresponding to rule
R
, which should not be included in
T
(
t
i
)
. Moreover,
t
i
−
1
should be added at the rear of
T
(
t
i
−
1
)
. In that case, the longest common prefix
of
T
. The subset
probabilities for the tuples in the longest common prefix can be reused. For those
tuples or rule-tuples not in the longest common prefix, we reorder them so that
the independent tuples are always sorted before the rule-tuples and the rule-tuples
are sorted in their next tuple indices descending order.
Third, if
t
i
−
1
is involved in another rule
R
=
(
t
i
−
1
)
and
T
(
t
i
)
includes the tuples ranked before
t
R
left
in
T
(
t
i
−
1
)
R
, then there are two differences
between
T
(
t
i
−
1
)
and
T
(
t
i
)
:1)
T
(
t
i
−
1
)
contains
t
R
left
but
T
(
t
i
)
does not; 2)
T
(
t
i
)
does not. Therefore, we first add
t
R
left
to the rear of
t
R
left
. Then, as discussed in the second subcase, we can reuse the longest common
prefix of
T
includes
t
R
left
but
T
(
t
i
−
1
)
(
t
i
−
1
)
and
T
(
t
i
)
, and reorder the tuples not in the longest common
prefix.
Example 5.3 (Lazy reordering).
Consider a list of ranked tuples
t
1
,···,
t
11
with
multi-tuple rules
R
1
:
t
1
⊕
t
10
again. The compressed
dominant sets of tuples in the orders made by the lazy reordering method is listed in
Table 5.1.
The lazy reordering method orders the compressed dominant sets in the same
way as the aggressive reordering method for
t
1
,
t
2
and
t
3
.
For
t
4
, the aggressive method orders
t
3
, an independent tuple, before
t
1
,
2
, the
rule-tuple for rule
R
1
which is open with respect to
t
4
. The subset probability values
computed in
T
t
2
⊕
t
8
⊕
t
11
and
R
2
:
t
4
⊕
t
5
⊕
(
t
3
)
cannot be reused. The lazy method reuses the prefix
t
1
,
2
from
T
(
t
3
)
, and appends
t
3
after
t
1
,
2
. All subset probability values computed in
T
(
t
3
)
can
be reused. The total cost of the lazy reordering method is 12.
The algorithm of the lazy reordering method is given in Algorithm 5.2. The com-
plexity is
O
, as analyzed in the aggressive reordering method.
We can show that the lazy method is never worse than the aggressive method.
(
n
log
n
)
Theorem 5.3 (Effectiveness of lazy reordering).
Given a ranked list of tuples in
T , let Cost
(
)
(
)
be the total number of subset probability values
needed to be calculated by the aggressive reordering method and the lazy reordering
method, respectively. Then, Cost
agg
and Cost
lazy
(
agg
)
≥
Cost
(
lazy
)
.
Proof.
For two consecutive tuples
t
i
and
t
i
+
1
in
T
(1
≤
i
≤|
T
|−
1), we consider the
following three cases.
