Database Reference
In-Depth Information
2.1.3 Converting Between the Uncertain Object Model and the
Probabilistic Database Model
Interestingly, the uncertain object model and the probabilistic database model are
equivalent.
•
Converting from the uncertain object model to the probabilistic database
model.
A set of uncertain objects can be represented by a probabilistic table as
follows. For each instance
o
of an uncertain object
O
, we create a tuple
t
o
, whose
membership probability is
f
(
o
)
. For each uncertain object
O
=
{
o
1
,···,
o
m
}
,we
create one generation rule
R
O
=
t
o
1
⊕···⊕
t
o
m
.
•
Converting from the probabilistic database model to the uncertain object
model.
A probabilistic table can be represented by a set of uncertain objects
with discrete instances. For each tuple
t
in a probabilistic table, we create an
instance
o
t
, whose probability mass function is
f
(
)=
(
)
o
t
Pr
t
. For a genera-
tion rule
R
:
t
r
1
⊕···⊕
t
r
m
, we create an uncertain object
O
R
, which includes
instances
o
t
o
1
,···,
o
t
o
m
corresponding to
t
r
1
,···,
t
r
m
, respectively. Moreover, if
m
i
=
1
Pr
(
t
r
i
)
<
1, we create another instance
o
0
whose probability mass function
∑
i
is
f
(
o
0
)=
1
−
∑
1
Pr
(
t
r
i
)
, and add
u
0
to the uncertain object
O
R
.
=
Example 2.3 (Converting between two models). R
1 in Table 1.1(a) can be converted
to an uncertain object
O
1
=
{
R
1
,¬
R
1
}
where
Pr
(
R
1
)=
0
.
3 and
Pr
(
¬
R
1
)=
0
.
7.
Moreover, generation rule
R
2
⊕
R
3 in Table 1.1(a) can be converted to uncertain
object
O
1
,
2
=
{
R
2
,
R
3
,¬
R
23
}
where
Pr
(
R
2
)=
0
.
4,
Pr
(
R
3
)=
0
.
5 and
Pr
(
¬
R
23
)=
0
.
1.
2.2 Basic Ranking Queries on Uncertain Data
In this section, we discuss various types of ranking queries on the uncertain object
model. Since the uncertain object model and the probabilistic database model are
equivalent, the queries discussed in this section can also be applied to the proba-
bilistic database model.
Depending on different application scenarios, probabilistic ranking queries can
be applied at one of the three
granularity levels
.
•
The
instance
probabilistic ranking queries return the instances satisfying query
conditions. We develop two classes of instance probabilistic ranking queries. The
first are
top-k typicality queries
, which rank instances in an uncertain object ac-
cording to how typical each instance is. The second are
probabilistic ranking
queries
, which rank instances in multiple objects according to the probability
that each instance is ranked top-
k
. The two classes of queries will be discussed
in Sections 2.2.1 and 2.2.2, respectively.
•
The
object
probabilistic ranking queries find the object satisfying query condi-
tions, which will be discussed in Section 2.2.3.
