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
 
Search WWH ::




Custom Search