Database Reference
In-Depth Information
Algorithm 5.2
The lazy 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: retrieve tuples in
T
in the ranking order one by one
2: set
T
(
t
1
)=
0
3:
for all
t
i
∈
T
(
i
≥
2)
do
4:
if
t
i
is independent or
t
i
is the first tuple in
R
then
5:
if
t
i
−
1
is independent
then
6:
T
(
t
i
)=
T
(
t
i
−
1
)+
t
i
−
1
7:
else
8:
T
(
t
i
)=
T
(
t
i
−
1
)+
t
R
left
{
*
t
i
−
1
∈
R
}
9:
end if
10:
else
11:
if
t
i
−
1
is involved in
R
then
12:
T
(
i
)=
T
(
i
−
1
)
13:
else
14:
if
t
i
−
1
is involved in rule
R
then
15:
T
(
t
i
)=
T
(
t
i
−
1
)
−
t
R
left
+
t
R
left
else
16:
T
(
t
i
)=
T
(
t
i
−
1
)
−
t
R
left
+
t
i
−
1
17:
18:
end if
19:
reorder all tuples in
T
(
t
i
)
that are ranked lower than
t
R
left
in their next tuple indices
descending order.
20:
end if
21:
end if
22:
end for
First, if
t
i
and
t
i
+
1
are involved in the same generation rule, then the cost of
computing
T
(
t
i
+
1
)
is 0 using either aggressive reordering or lazy reordering, since
T
.
Second, if
t
i
+
1
is an independent tuple or the first tuple in a generation rule
R
,
then the cost of computing
T
(
t
i
+
1
)
contains the same set of tuples in
T
(
t
i
)
(
t
i
+
1
)
using lazy reordering is 1, since a tuple
t
i
(if
t
i
is
(if
t
i
is involved in
R
) should be added into
T
independent) or rule-tuple
t
R
left
(
t
i
)
to
form
T
(
t
i
+
1
)
. The cost of computing
T
(
t
i
+
1
)
using aggressive reordering is at least
1.
Third, if
t
i
+
1
is involved in rule
R
but is not the first tuple in
R
, then
t
R
left
must be
removed from
T
(
t
i
)
(
)
, as discussed
in the second case. Let
L
reorder
be the set of tuples or rule-tuples in
T
. Moreover,
t
i
or
t
R
left
should be added into
T
t
i
(
t
i
)
that are
ranked lower than
t
R
left
, then the cost of computing
T
1. Now let
us show that, using aggressive reordering, the same amount of cost is also needed
before scanning
t
i
+
1
. For each tuple
t
(
t
i
+
1
)
is
|
L
reorder
|
+
L
reorder
, one of the following two subcases
may arise: 1)
t
is an independent tuple or a completed rule-tuple, then
t
must be
put into
L
complete
using aggressive reordering. The subset probability of
t
R
need to
be recomputed once
L
complete
is updated. Thus, 1 cost is required. 2)
t
is an open-
rule tuple, then it must be put into
L
open
using aggressive reordering. The subset
∈