Database Reference
In-Depth Information
, a vertex
v
is corresponding
to a linkage
l
and a clique
C
is corresponding to a tuple
t
. The top-
k
probability of a
vertex
v
is
Pr
k
In a PME-graph
G
=(
V
,
E
)
representing linkages
L
Pr
k
and the top-
k
probability of clique
C
is
Pr
k
Pr
k
.
There are two categories of vertices in a PME-graph
G
.A
private vertex
belongs
to only one clique, such as
(
v
)=
(
l
)
(
C
)=
(
t
)
in Figure 7.2(b). A
joint vertex
belongs
to two cliques, such as
v
3
and
v
5
in Figure 7.2(b). We use
V
P
and
V
J
to denote the
set of private vertices and joint vertices, respectively.
Let
V
S
denote the set of vertices satisfying the predicate
P
and
V
S
{
v
1
,
v
2
,
v
4
,
v
6
,
v
7
}
=
−
V
V
S
be the
set of vertices not satisfying
P
. Two questions arise.
Question 1: Which vertices in
V
S
can be removed?
We can partition the vertices in
V
S
into two subsets.
•
The first subset contains the joint vertices in
V
S
that lie in at least one path be-
tween two vertices in
V
S
. That is,
V
1
=
{
v
|
v
∈
V
S
∩
V
J
∧∃
P
=
v
1
,···,
v
,···,
v
2
s
.
t
.
v
1
∈
V
S
∧
v
2
∈
V
S
}.
The vertices in
V
1
cannot be removed in preprocessing, since removing them may
not preserve the dependen
cie
s among the vertices satisfying
P
.
•
The second subset is
V
2
=
V
1
. Removing the vertices in
V
2
does not change
the top-
k
probabilities of the vertices satisfying
P
.
V
S
−
Hereafter, let us assume that
V
2
has been removed from
G
as preprocessing.
Therefore, two sets of vertices remain in
G
:
V
S
contains all vertices satisfying pred-
icate
P
;
V
1
contains all vertices not satisfying
P
but connecting to vertices in
V
S
.
Question 2: Should we treat the remaining vertices equally?
Consider two vertices
v
1
∈
V
1
and
v
2
∈
V
S
. Given another vertex
v
∈
V
S
, let
v
1
f
v
and
v
2
f
v
. In a possible world
W
, whether
v
1
appears or not does not affect the
rank of
v
. However, whether
v
2
appears or not does change the rank of
v
.
In order to distinguish between the vertices in
V
S
and
V
1
, we associate a flag
attribute
F
with each vertex
v
∈
G
.If
P
(
v
)=
true
, then
v
.
F
=
1, otherwise
v
.
F
=
0.
7.3.2 Dominant Subgraphs
The dominant set property (Theorem 5.1) indicates that, to compute the top-
k
prob-
ability of a tuple
t
in a probabilistic table, we only need to consider the tuples ranked
higher than
t
.
