Database Reference
In-Depth Information
Algorithm 5.1
The aggressive reordering algorithm
Input:
an uncertain table
T
, a set of generation rules
, and a top-
k
query
Q
k
f
R
Output:
Reordered compressed dominant set
T
(
t
i
)
of each tuple
t
i
∈
T
Method:
1: set
L
complete
0
2: retrieve tuples in
T
in the ranking order one by one
3:
for all
t
i
=
0,
L
open
=
∈
T
do
4:
if
t
i
is independent
then
L
open
6: add
t
i
to the rear of
L
complete
7:
else
8:
T
(
t
i
+
1
)=
L
complete
+(
L
open
−
t
R
left
)
{
*
t
i
is involved in rule
R
}
9:
if
t
i
is the last tuple in a rule
R
then
10: remove
t
R
left
from
L
open
11: form rule-tuple
t
R
and add
t
R
to
L
complete
12:
else
13: update rule-tuple
t
R
left
in
L
open
by compressing
t
i
∈
R
14: sort all rule-tuples in
L
open
in their next tuple indices descending order.
15:
end if
16:
end if
17:
end for
5:
T
(
t
i
+
1
)=
L
complete
+
15.
As a comparison, without reordering, the total number of subset probability values
needed to be calculated is the sum of lengths of all compressed dominant sets, which
is 31.
The total cost by using the aggressive reordering method is
Cost
aggressive
=
The aggressive reordering algorithm is given in Algorithm 5.1. The complexity
of the aggressive reordering algorithm lies in the sorting of
L
open
. When scanning a
tuple, the rule-tuples in
L
open
are already sorted and at most one rule-tuple in
L
open
is updated. Therefore, the complexity is
O
(
log
|
L
open
|
)
for processing one tuple. The
overall complexity is
O
(
n
log
n
)
where
n
is the number of tuples in
T
.
5.2.2.2 Lazy Reordering
On the other hand, a
lazy method
always reuses the longest common prefix in the
compressed dominant set of the last tuple scanned, and reorders only the tuples not
in the common prefix using the two observations discussed in Section 5.2.2.1.
We scan the tuples in
T
in the ranking order. During the scan, we maintain the
compressed dominant set of the last scanned tuple. When processing tuple
t
i
, one of
the following two cases may apply.
Case 1:
If
t
i
is an independent tuple, or
t
i
is the first tuple scanned in a multi-tuple
generation rule
R
, then the compressed dominant set of
t
i
can be computed by
one of the following two subcases.
