Database Reference
In-Depth Information
Example 2.1 (Uncertain objects).
Table 1.2 is an example of a uncertain object with
6 instances. Each instance takes an equal membership probability
1
6
.
2.1.2 Probabilistic Database Model
In some other studies, the probabilistic database model is used to represent uncertain
data. A probabilistic database [17] is a finite set of probabilistic tables defined as
follows.
Definition 2.3 (Probabilistic table).
A
probabilistic table
contains a set of uncer-
tain tuples
T
and a set of generation rules
R
. Each
uncertain tuple
t
∈
T
is associ-
ated with a
membership probability
Pr
(
t
)
>
0. Each
generation rule
(or
rule
for
short)
R
∈R
specifies a set of exclusive tuples in the form of
R
:
t
r
1
⊕···⊕
t
r
m
where
i
t
r
i
∈
T
(
1
≤
i
≤
m
)
,
Pr
(
t
r
i
∧
t
r
j
)=
0
(
1
≤
i
,
j
≤
m
,
i
=
j
)
and
1
Pr
(
t
r
i
)
≤
1.
∑
=
The probabilistic database model also follows the possible worlds semantics. The
generation rule
R
constrains that, among all tuples
t
r
1
,···,
t
r
m
involved in the rule, at
most one tuple can appear in a possible world.
R
is a
singleton rule
if there is only
one tuple involved in the rule, otherwise,
R
is a
multi-tuple rule
. The
cardinality
of
a generation rule
R
, denoted by
|
R
|
, is the number of tuples involved in
R
.
Definition 2.4 (Possible worlds of a probabilistic table).
Given a probabilistic ta-
ble
T
,a
possible world W
is a subset of
T
such that for each generation rule
R
∈R
T
,
|
R
∩
W
|
=
1if
Pr
(
R
)=
1, and
|
R
∩
W
|≤
1if
Pr
(
R
)
<
1. The existence probability
of
W
is
∏
∏
R
∈R
T
,
R
∩
W
=
Pr
(
W
)=
Pr
(
R
∩
W
)
0
(
1
−
Pr
(
R
))
R
∈R
T
,|
R
∩
W
|
=
1
Corollary 2.2 (Number of possible worlds).
For an uncertain table T with a set of
generation rules
R
T
, the number of all possible worlds is
∏
∏
|W |
=
R
∈R
T
,
Pr
(
R
)=
1
|
|
R
∈R
T
,
Pr
(
R
)
<
1
(
|
|
+
)
R
R
1
Example 2.2 (Probabilistic tables).
Table 1.1(a) is an example of a probabilistic ta-
ble with 6 uncertain tuples and 2 multi-tuple generation rules
R
2
⊕
R
3 and
R
5
⊕
R
6.
The corresponding possible worlds are shown in Table 1.1(b).
