Database Reference
In-Depth Information
PME-graphs are useful in deriving possible worlds of linkages and ranking query
evaluation methods, which will be discussed in Sections 7.2.5, 7.3 and 7.4.
Besides PME-graphs, we create a maximal clique graph to represent the depen-
dencies between maximal cliques. Hereafter, only maximal cliques in the PME-
graphs are of interest. For the sake of simplicity, we refer to maximal cliques as
cliques.
Definition 7.3 (Clique graph).
Given a PME-graph
G
L ,
A
,
B
, the corresponding
clique graph
is a graph
G
clique
(
,
)
∈
V
E
, where a vertex
v
C
V
corresponds to a max-
E
if cliques
C
and
C
in the
imal clique
C
in
G
L ,
A
,
B
and an edge
e
CC
=(
v
C
,
v
C
)
∈
PME-graph share a common vertex.
Let
C
be a maximal clique in
G
L ,
A
,
B
and
V
C
be the set of vertices in
C
. The
probability of the corresponding vertex
v
C
∈
V
in the clique graph is
Pr
(
v
C
)=
∑
x
∈
V
C
Pr
(
x
)
.
Hereafter, in order to distinguish between the vertices in a PME-graph and the
vertices in a clique graph, we refer to a vertex in a clique graph as a clique.
Figures 7.2(a), (b) and (c) show a set of linkages, the PME-graph and the clique
graph, respectively. Each node
v
i
in Figure 7.2(b) corresponds to a linkage
l
i
in
Figure 7.2(a). Each maximal clique in Figure 7.2(b) corresponds to a vertex in Fig-
ure 7.2(c).
7.2.3 Compatibility of Linkages
To check wether a set of linkages
L
are compatible, a straightforward approach is
to check, for each clique
C
C
can lead to a marginal distribution on
C
that is consistent with the given marginal
distribution
f
∈
G
clique
, whether the joint probability on
G
clique
−
(
)
. However, this approach is very costly since we have to compute
the joint probability on cliques
G
clique
−
C
C
for every
C
.
Fortunately, we can derive a sufficient and necessary condition for compatible
linkages as stated in the following theorem.
Theorem 7.2 (Compatibility).
Given a set of linkages
L
and the corresponding
clique graph G
C
, then linkages in
L
are compatible if and only if, for each con-
nected component G
∈
G
C
, one of the following two conditions holds:
1. G
is acyclic;
2. G
is a cycle such that each vertex v
C
in the cycle is connected to two edges
e
1
and e
2
, whose corresponding vertices v
1
and v
2
in the PME-graph satisfy
Pr
(
v
1
)+
Pr
(
v
2
)=
1
.
Proof.
We first prove the sufficiency, that is, if the clique graph of a set of linkages
satisfies one of the two conditions in the theorem, then the linkages are compatible.
Condition 1.
If the clique graph
G
C
is acyclic, then the joint distribution of the
linkages can be derived using the methods discussed in Section 7.2.5.
