Database Reference
In-Depth Information
Chapter 7
Ranking Queries on Probabilistic Linkages
In Chapters 4, 5 and 6, we adopt an independent uncertain object model. That is,
we assume that any two uncertain objects in a data set are independent. In many
applications, various types of dependencies may exist among real world uncertain
objects, such as the case shown in Example 2.12. In this chapter, we study how to
answer probabilistic ranking queries on the probabilistic linkage model.
7.1 Review: the Probabilistic Linkage Model
A probabilistic linkage model contains two sets of tuples
A
and
B
and a set of link-
ages
L
. Each linkage
l
in
L
matches one tuple in
A
and one tuple in
B
. For a
linkage
l
=(
t
A
,
t
B
)
, we say
l
is associated with
t
A
and
t
B
. We write
l
∈
t
A
and
l
∈
t
B
.
We can consider each tuple
t
A
∈
A
as an uncertain object. An tuple
t
B
∈
B
can be
considered as an instance of
t
A
if there is a linkage
l
=(
t
A
,
t
B
)
∈L
. The membership
(
)
probability of instance
t
B
with respect to object
t
A
is
Pr
l
. Object
t
A
may contain
multiple instances
{
t
B
1
,···,
t
B
k
}
(
,
t
B
i
)
∈L
≤
≤
where
t
A
(1
i
k
). At the same time,
an instance
t
B
may belong to multiple objects
{
t
A
1
,···,
t
A
d
}
where
(
t
A
j
,
t
B
)
∈ L
(1
≤
j
≤
d
). A mutual exclusion rule
R
t
B
=(
t
A
1
,
t
B
)
⊕···⊕
(
t
A
d
,
t
B
)
specifies that
t
B
can only belong to one object in a possible world.
Since different objects may share the same instance in the probabilistic linkage
model, we develop a probabilistic mutual exclusion graph (PME-graph for short)
to describe such dependencies. Moreover, the evaluation methods for probabilistic
ranking queries developed for independent uncertain objects cannot be directly ap-
plied on the probabilistic linkage model. We develop efficient evaluation algorithms
in this chapter.
151
