Database Reference
In-Depth Information
set of mutual exclusion rules for tuples in
A
.
R
t
B
for
t
B
∈
B
and
R
B
are defined
symmetrically.
(
L ,
specifies a bipartite graph, where the tuples in
A
and those in
B
are two
independent sets of nodes, respectively, and the edges are the linkages between the
tuples in the two tables.
A
,
B
)
2.3.2.1 Connections with the Uncertain Object Model
Given a set of probabilistic linkage
L
between tuple sets
A
and
B
, we can consider
each tuple
t
A
∈
A
as an uncertain object. For any tuple
t
B
∈
B
, if there is a linkage
l
0, then
t
B
can be considered as an instance of
object
t
A
whose membership probability is
Pr
=(
t
A
,
t
B
)
∈ L
such that
Pr
(
l
)
>
. In contrast to the basic uncertain
object model where each instance only belongs to one object, in the probabilistic
linkage model, a tuple
t
B
∈
(
l
)
B
may be the instance of multiple objects
{
t
A
1
,···,
t
A
d
}
,
where
t
A
i
is a tuple in
A
with linkage
(
t
A
i
,
t
B
)
∈L
(1
≤
i
≤
d
). A mutual exclusion
rule
R
t
B
=(
specifies that
t
B
should only belong to one object
in a possible world. Alternatively, we can consider each tuple
t
B
∈
t
A
i
,
t
B
)
⊕···⊕
(
t
A
d
,
t
B
)
B
as an uncertain
object and a tuple
t
A
∈
.
A linkage function can be regarded as the summarization of a set of possible
worlds.
A
is an instance of
t
B
if there is a linkage
(
t
A
,
t
B
)
∈L
Definition 2.20 (Possible worlds).
For a linkage function
and tables
A
and
B
, let
L
A
,
B
be the set of linkages between tuples in
A
and
B
.A
possible world
of
L
L
A
,
B
,
denoted by
W
⊆L
A
,
B
, is a set of pairs
l
=(
t
A
,
t
B
)
such that (1) for any mutual exclu-
sive rule
R
t
A
,if
Pr
(
t
A
)=
1, then there exists one pair
(
t
A
,
t
B
)
∈
W
, symmetrically, for
any mutual exclusive rule
R
t
B
,if
Pr
(
t
B
)=
1, then there exists one pair
(
t
A
,
t
B
)
∈
W
;
and (2) each tuple
t
A
∈
A
participates in at most one pair in
W
, so does each tuple
t
B
∈
B
.
W
L ,
A
,
B
denotes the set of all possible worlds of
L
A
,
B
.
We study the ranking query answering on probabilistic linkage model in Chap-
ter 7.
2.3.3 Uncertain Road Network
As illustrated in Scenario 3 of Example 1.1, the weight of each edge in a graph may
be an uncertain object. An uncertain road network is a probabilistic graph defined
as follows.
Definition 2.21 (Probabilistic graph).
A
probabilistic graph
G
(
V
,
E
,
W
)
is a sim-
ple graph containing a set of vertices
V
, a set of edges
E
⊆
V
×
V
, and a set of
weights
W
defined on edges in
E
. For each edge
e
∈
E
,
w
e
∈
W
is a real-valued
random variable in
(
0
,
+∞)
, denoting the travel time along edge
e
.
