Database Reference
In-Depth Information
v
3
v
C
2
v
i
C
3
v
3
C
k−3
v
k−2
i+5
C
3
v
2
v
4
C
2
C
k−2
C
C
i+4
i
v
2
v
v
k−1
C
4
v
i+1
C
C
1
C
C
i+3
C
1
C
k
k−1
i+4
i+1
v
i+2
C
i+2
v
1
v
i+3
v
k
v
1
(a) A set of linkages
L
.
(b) Case 1.
(c) Case 2.
Fig. 7.3
A cycle of
k
cliques.
Condition 2.
If the second condition holds, then the joint distribution of the
linkages involved in
G
can be uniquely determined. Suppose
G
contains ver-
tices
{
v
C
1
,···,
v
C
k
}
as shown in Figure 7.3(a), whose corresponding cliques are
{
in the PME-graph (
k
must be an even number since the linkages be-
tween tuple sets
A
and
B
form a bipartite graph). In the clique graph, since each
vertex
v
C
i
has degree 2, which means, the corresponding clique in the PME-graph
shares 2 vertices with 2 other cliques. There are
k
edges
e
v
1
,···,
C
1
,···,
C
k
}
e
v
k
involved in the
cycle, whose corresponding vertices in the PME-graph are
v
1
,···,
v
k
. Each vertex
v
i
belongs to two cliques
C
i
−
1
and
C
i
(2
k
).
v
1
belongs to cliques
C
1
and
C
k
. Since
the probability sum of each two connected edges is 1, we have
Pr
≤
i
≤
(
v
1
)=
Pr
(
v
2
i
+
1
)
k
2
k
2
). Thus, the joint distribution of
(1
≤
i
≤
−
1) and 1
−
Pr
(
v
1
)=
Pr
(
v
2
j
)
(1
≤
j
≤
all vertices in the PME-graph is given by
((
0
≤
i
≤
1
v
2
i
+
1
)
(
1
≤
j
≤
Pr
2
¬
v
2
j
)) =
Pr
(
v
1
)
k
2
−
k
((
0
≤
i
≤
)
(
1
≤
j
≤
Pr
2
−
1
¬
v
2
i
+
1
2
v
2
j
)) =
1
−
Pr
(
v
1
)
.
The joint distribution is consistent with the marginal distribution specified by each
linkage. Thus, the linkages are compatible.
Then, we prove the necessity. That is, if a set of linkages are compatible, then the
corresponding clique graph must satisfy one of the two conditions in the theorem.
Consider a set of compatible linkages whose clique graph is
G
C
.
Suppose
G
contains a cycle, then we need to show that
G
can only form a cycle
satisfying condition 2 in the theorem. We prove this in two cases: the cycle contains
4 vertices and the cycle contains more than 4 cases.
Case 1:
The cycle in
G
contains 4 vertices
v
C
1
,
v
C
2
,
v
C
3
,
v
C
4
, whose corresponding
cliques in the PME-graph are
{
C
1
,
C
2
,
C
3
,
C
4
}
, as illustrated in Figure 7.3(b). Let
v
i
4) and
v
1
be contained by
C
1
and
C
4
. The joint probability of
v
1
and
v
4
can be expressed as
be the vertex contained by
C
i
−
1
and
C
i
(2
≤
i
≤
Pr
(
v
1
v
4
)=
Pr
(
¬
v
2
¬
v
3
)
Pr
(
v
1
|¬
v
2
)
Pr
(
v
4
|¬
v
3
)
.
Since
v
1
and
v
4
are contained in clique
C
4
,
Pr
(
v
1
v
4
)=
0 holds. Moreover,
Pr
(
v
1
|¬
v
2
)
>
0 and
Pr
(
v
4
|¬
v
3
)
>
0. Thus,
Pr
(
¬
v
2
¬
v
3
)=
0. Since
v
2
and
v
3
are
contained in the same clique
C
2
,wehave
Pr
(
¬
v
2
¬
v
3
)=
1
−
Pr
(
v
2
)
−
Pr
(
v
3
)
. There-
fore,
Pr
(
v
2
)+
Pr
(
v
3
)=
1, which means that
C
2
only contains two vertices
{
v
2
,
v
3
}
