Database Reference
In-Depth Information
form
W
⊆
T
(because
S
is deterministic). We associate
the assignment
θ
with the possible world
W
such that
θ(X
i
)
=
=
R
W
,S,T
W
, where
R
W
⊆
R
and
T
W
true
iff
X
i
∈
R
W
true
iff
Y
j
∈
T
W
. This establishes a 1-1 correspondence between possible worlds
W
and assignments
θ
. Now we note that
W
and
θ(Y
j
)
=
true
: indeed,
W
|=
H
0
iff there exists
X
i
,Y
j
such that
R
W
(X
i
), S(X
i
,Y
j
), T
W
(Y
j
)
is true, and this happens iff
θ(X
i
)
=
θ(Y
j
)
=
|=
H
0
iff
[
θ
]=
true
and
X
i
Y
j
isacon-
2
n
P(H
0
)
, where
n
is the total number of Boolean variables.
Thus, an oracle for computing
P(H
0
)
can be used to compute #
, proving that
P(H
0
)
is hard for
#
P
.
junct in
(
Eq. (3.1)
). Therefore, #
=
The proof for
H
1
is by reduction from #PP2CNF (
Theorem 3.1
). Consider any formula
=
(X
i
∨
Y
j
)
(i,j)
∈
E
We show how to use an Oracle for
P(H
1
)
to compute #
, which proves hardness for
H
1
.Let
n
be the
total number of variables (both
X
i
and
Y
j
) and
m
=|
E
|
. Given
, we construct the same probabilistic
database instance as before:
R
={
X
1
,X
2
,...
}
.We
still set
P(R(X
i
))
=
P(T(Y
j
))
=
1
/
2, but now we set
P(S(X
i
,Y
j
))
=
1
−
z
for some
z
∈
(
0
,
1
)
to
be specified below. We will compute
P(
,
T
={
Y
1
,Y
2
,...
}
,
S
={
(X
i
,Y
j
)
|
(i, j)
∈
E
}
R
W
,S
W
,T
W
¬
H
1
)
. Denote
W
=
a possible world, i.e.,
R
W
⊆
R, S
W
⊆
S,T
W
⊆
T
. The probability of each world
W
depends only on
S
W
|
S
W
(if
|=
c
1
z)
c
z
m
−
c
). By definition,
P(
then
P(W)
=
2
n
(
1
−
¬
H
1
)
is:
P(
¬
H
1
)
=
P(W)
(3.2)
W
:¬
(W
|=
H
1
)
Now consider a valuation
θ
for
. Define
E
θ
the following predicate on a world
W
=
R
W
,S
W
,T
W
:
≡
(X
i
∈
R
W
∈
T
W
iff
θ(X
i
)
=
∧
iff
θ(Y
j
)
=
E
θ
true)
(Y
j
true)
In other words, the event
E
θ
fixes the relations
R
W
and
T
W
according to
θ
, and leaves
S
W
totally
unspecified. Therefore its probability is:
1
2
n
Since the events
E
θ
are disjoint, we can expand
Eq. (3.2)
to:
P(E
θ
)
=
P(θ)
=
2
n
θ
1
P(
¬
H
1
)
=
P(
¬
H
1
|
E
θ
)
·
P(E
θ
)
=
P(
¬
H
1
|
E
θ
)
(3.3)
θ
Next, we compute
P(
¬
H
1
|
E
θ
)
. Define:
C(θ)
={
(i, j)
∈
E
|
θ(X
i
∨
Y
j
)
=
true
}
