Database Reference
In-Depth Information
Pr
(
v
p
)=∑
m
Pr
(
v
c
i
)
. Moreover, for all other vertices
v
∈
V
C
−{
v
c
1
,···,
v
c
m
}
,an
1
≤
i
≤
edge
is added to
E
. This technique is called
vertex compression
.
Vertex compression does not change the top-
k
probability of
v
. The reason
is that
(
v
,
v
p
)
{
v
c
1
,···,
v
c
m
}
only belongs to
C
and assigning 1 to different vertices in
{
does not affect the value assignment of other vertices not in
C
. After
vertex compression, each clique in
G
v
c
1
,···,
v
c
m
}
(
)
contains at most one private vertex.
For example, for a dominant graph
G
v
(
)
shown in Figure 7.5(a), let the grey
vertices be the ones ranked higher than
v
. After the vertex compression,
G
v
(
)
v
is
changed to the graph in Figure 7.5(b).
7.3.4 Subgraph Probabilities
Given a dominant subgraph
G
(
v
)
,
v
is ranked at the
j
-th position if and only if
v
appears and there are
j
−
1 vertices in
G
(
v
)
appear.
We define
subgraph probability Pr
(
G
(
v
)
,
j
)
as the probability that
j
vertices in
G
(
v
)
appear in possible worlds. Since
v
and the vertices in
G
(
v
)
may not be inde-
pendent, the probability that
j
vertices in
G
appear may depend on
v
. Therefore,
we further define the
conditional subgraph probability
of
G
(
v
)
(
v
)
given
v
.
Definition 7.7 (Conditional subgraph probability).
Given a top-
k
selection query
Q
k
Q
,
f
, a dominant graph
G
(
v
)
of a vertex
v
, the
subgraph probability
Pr
(
G
(
v
)
,
i
)
is
the probability that
i
vertices satisfying predicate
P
appear in
G
(
v
)
, that is,
∑
Pr
(
G
(
v
)
,
i
)=
Pr
(
W
)
.
v
|
v
∈
v
.
W
∈W ,|{
W
∩
G
(
v
)
,
F
=
1
}|
=
i
Moreover, the
conditional subgraph probability
Pr
(
G
(
v
)
,
i
|
v
)
is the probabil-
ity that
i
vertices satisfying predicate
P
appear in
G
(
v
)
given the condition that
v
appears, that is,
)=
∑
W
∈W ,|{
v
|
v
∈
W
∩
G
,
v
.
F
=
1
}|
=
i
,
v
∈
W
Pr
(
W
)
Pr
(
G
,
i
|
v
∑
W
∈W ,
v
∈
W
Pr
(
W
)
The top-
k
probability of
v
can be computed as
k
−
1
i
=
0
Pr
(
G
(
v
)
,
i
|
v
)
.
Pr
k
(
v
)=
Pr
(
v
)
·
(7.6)
, the Poisson binomial recurrence (Theorem 5.2)
cannot be used to compute the subgraph probabilities, since it only works for inde-
pendent uncertain objects. In Section 7.4, we will discuss how to compute subgraph
probabilities of
G
Given a dominant graph
G
(
v
)
(
v
)
.
