Database Reference
In-Depth Information
For clique C
3
(Figure 7.4(c)), similarly, the probabilities of v
6
=
1
and v
7
=
1
1
3
and Pr
when v
5
=
0
are Pr
(
v
6
=
1
|
v
5
=
0
)=
(
v
7
=
1
|
v
5
=
0
)=
0
.
5
, respectively.
Suppose we set v
8
=
0
.
The probability of possible world W
1
=
{
1
. Then, v
6
=
l
1
,
l
4
,
l
7
}
is Pr
(
v
1
=
1
,
v
2
=
0
,
v
3
=
0
,
v
4
=
1
,
v
5
=
0
,
v
6
=
0
,
v
7
=
1
)=
Pr
(
v
1
=
1
)
Pr
(
v
4
=
1
|
v
3
=
0
)
Pr
(
v
7
=
1
|
v
5
=
)=
.
×
.
×
.
=
.
0
15
.
Interestingly, the joint probability in this example is factored into a set of con-
ditional probabilities on a subset of vertices that can be directly derived from the
given linkages. Moreover, the other possible worlds can be enumerated recursively
in the same way.
0
6
0
5
0
5
0
7.3 Ranking Queries on Probabilistic Linkages
We formulate the probabilistic ranking queries introduced in Section 2.2.2 on prob-
abilistic linkages as follows.
Given a set of linkages
L
A
,
B
between tables
A
and
B
, let
Q
P
,
f
be a top-
k
selec-
tion query, where
P
is a predicate and
f
is a scoring function which may involve
attributes in
A
,
B
, or both. For a linkage
l
is a real value score.
Definition 7.5 (Top-
k
probability of linkages and tuples).
For a linkage
l
∈L
A
,
B
,
f
(
l
)
∈L
A
,
B
,
the
rank-
k
probability
of
l
, denoted by
Pr
(
l
,
k
)
, is the probability that
l
is ranked
at the
k
-th position in possible worlds. That is
∑
Pr
(
l
,
k
)=
Pr
(
W
)
W
∈W
L ,
A
,
B
,
W
f
(
k
)=
l
where
W
f
(
k
)
is the
k
-th linkage in possible world
W
. Moreover, the
top-
k
probabil-
ity
of
l
is
k
i
=
1
Pr
(
l
,
i
)
Consequently, the
rank-
k
probability
of a tuple
t
Pr
k
(
l
)=
∈
A
∪
B
is
)=
l
∈
t
Pr
(
l
,
k
)
Pr
(
t
,
k
The
top-
k
probability
of
t
is
Pr
k
)=
l
∈
t
Pr
k
(
t
(
l
)
,a
probabilistic
threshold top-
k
query (Definition 2.12) on linkages
finds the probabilistic link-
ages whose top-
k
probabilities are at least
p
. Similarly, a
probabilistic threshold
top-
k
query on tuples
finds the tuples whose top-
k
probabilities are at least
p
.
Given a positive integer
k
and probability threshold
p
∈
(
0
,
1
]
