Database Reference
In-Depth Information
5.1.3 Handling Generation Rules
In general, a probabilistic table may contain some multi-tuple generation rules. For
a tuple
t
T
, two situations due to the presence of multi-tuple generation rules
complicate the computation.
First, there may be a rule
R
such that some tuples involved in
R
are ranked higher
than
t
. Second,
t
itself may be involved in a generation rule
R
. In both cases, some
tuples in
S
t
are dependent and thus Theorem 5.2 cannot be applied directly. Can
dependent tuples in
S
t
be transformed to independent ones so that Theorem 5.2 can
still be used?
Let
T
∈
j
. We compute
Pr
k
=
t
1
···
t
n
be in the ranking order, i.e.,
t
i
f
t
j
for
i
<
(
t
i
)
for a tuple
t
i
∈
T
. A multi-tuple generation rule
R
:
t
r
1
,···,
t
r
m
(
1
≤
r
1
<···<
r
m
≤
n
)
can be handled in one of the following cases.
Case 1:
t
i
f
t
r
1
, i.e.,
t
i
is ranked higher than or equal to all tuples in
R
. According
to Theorem 5.1,
R
can be ignored.
Case 2:
t
r
m
≺
f
t
i
, i.e.,
t
i
is ranked lower than all tuples in
R
. We call
R completed
with respect to
t
i
.
Case 3:
t
r
1
≺
f
t
i
f
t
r
m
, i.e.,
t
i
is ranked in between tuples in
R
.
R
is called
open
with respect to
t
i
. Among the tuples in
R
ranked better than
t
i
, let
t
r
m
0
∈
R
be the
max
l
=
1
{
lowest ranked tuple i.e.,
r
m
0
=
r
l
<
i
}
. The tuples involved in
R
can be
.
Pr
k
divided into two parts:
R
left
=
{
t
i
)
is affected by tuples in
R
left
only and not by those in
R
right
. Two subcases may
arise, according to whether
t
belongs in
R
or not: in subcase 1,
t
i
t
r
1
,...,
t
r
m
0
}
and
R
right
=
{
t
r
m
0
+
1
,...,
t
r
m
}
(
∈
R
; in subcase 2,
t
r
m
0
+
1
.
Since in Case 1, generation rule
R
can be ignored, in the rest of this section, we
mainly discuss how to handle generation rules in Case 2 and Case 3.
We first consider computing
Pr
k
t
i
∈
R
, i.e.,
t
i
=
(
t
i
)
when an generation rule
R
:
t
r
1
⊕···⊕
t
r
m
(
is involved.
In Case 2,
t
i
is ranked lower than all tuples in
R
. At most one tuple in
R
can
appear in a possible world. According to Theorem 5.1, we can combine all tuples in
R
into an
generation rule-tuple t
R
with membership probability
Pr
1
≤
r
1
<···<
r
m
≤
n
)
(
R
)
.
Corollary 5.1 (Generation rule-tuple compression).
For a tuple t
∈
T and a multi-
t
∈
R, t
≺
f
t, then Pr
k
Q
,
T
(
Pr
k
Q
,
T
(
R
)
(
tuple generation rule R, if
∀
t
)=
t
)
where T
(
R
)=
(
T
−{
t
|
t
∈
R
}
)
∪{
t
R
}
, tuple t
R
takes any value such that t
R
≺
f
t, Pr
(
t
R
)=
Pr
(
R
)
,
and other generation rules in T remain the same in T
(
R
)
.
In Case 3,
t
i
is ranked between the tuples in
R
, which can be further divided into
two subcases. First, if
t
i
∈
R
, similar to Case 2, we can compress all tuples in
R
left
into an generation rule-tuple
t
r
1
,...,
r
m
0
where membership probability
Pr
(
t
r
1
,...,
r
m
0
)=
m
0
j
, and compute
Pr
k
1
Pr
(
t
r
j
)
(
t
i
)
using Corollary 5.1.
∑
=
R
, in a possible world where
t
i
appears, any tuples in
R
cannot ap-
pear. Thus, to determine
Pr
k
Second, if
t
i
∈
, according to Theorem 5.1, we only need to consider
the tuples ranked higher than
t
i
and not in
R
, i.e.,
S
t
i
−{
(
t
i
)
t
|
t
∈
R
}
.
