Database Reference
In-Depth Information
C
1
b
v
1
1
C
1
l
2
(0.2)
a
1
b
v
v
v
3
2
3
2
l
4
(0.4)
v
4
C
2
a
2
b
3
C
2
v
5
v
l
6
(0.2)
6
a
3
b
4
v
5
v
7
C
3
b
5
C
3
(b) PME-graph.
(a) A set of linkages
L
.
(c) Clique graph.
Fig. 7.2
A set of linkages and the corresponding PME-graph and clique graph .
2. v
i
and v
j
are mutually exclusive if there is an edge e
E.
3. v
i
and v
j
are conditionally independent given another vertex v if there is a path
between v
i
and v
j
passing v.
=(
v
i
,
v
j
)
∈
Theorem 7.1.
A PME-graph G
L ,
A
,
B
is a Markov random field.
Proof.
We need to show that
G
L ,
A
,
B
satisfies the Markov property, which states that,
in a set of random variables, the probability of any given random variable
X
being
in a state
x
only depends on a subset of random variables in the system [134]. In a
PME-graph
G
L ,
A
,
B
, a vertex
v
is mutually exclusive with its adjacent vertices
N
v
.
For any other vertex
v
∈
N
v
,
v
and
v
are independent conditional on
N
v
.
V
−{
v
}−
The Markov property is satisfied.
A PME-graph has two interesting and useful properties.
Lemma 7.1 (Property of PME-graphs).
For a PME-graph G corresponding to
linkages
between tuple sets A and B:
1. For a tuple t
L
B, the edges corresponding to the linkages in the mutual
exclusion rule R
t
form a maximal clique in G.
2. Any two cliques in G can share at most one common vertex.
∈
Aort
∈
Proof.
Since a maximal clique in a PME-graph
G
captures a mutual exclusion rule
in the linkages
L
A
,
B
, the first item holds.
To prove the second item, since a vertex
v
in
G
L ,
A
,
B
is a linkage and can involve
only one tuple in
A
and another tuple in
B
,
v
can participate in at most 2 maximal
cliques in the PME-graph.
For example, two maximal cliques
C
1
=
{
v
1
,
v
2
,
v
3
}
and
C
2
=
{
v
3
,
v
4
,
v
5
}
in Fig-
ure 7.2(b) only share one common vertex
v
3
.
A PME-graph captures two types of dependencies among linkages: first, two
linkages associated with the same tuple are mutually exclusive; second, two link-
ages are conditionally independent given the linkages connecting the two linkages.
