Database Reference
In-Depth Information
5. INTENSIONAL QUERY EVALUATION
may be exponential in the size of the formula
. For example, if
X
1
X
2
...X
n
(a conjunction
of
n
independent variables), assuming
P(X
1
)
=
...
=
P(X
n
)
=
1
/
2, then
P ()
=
1
/
2
n
, and we
have to sample about 2
n
random assignments
θ
to have a chance to hit the unique assignment that
makes
true.
Karp and Luby
[
1983
] and
Karp et al.
[
1989
] gave two improved algorithms that are guar-
anteed to run in polynomial time in 1
/ε
and the size of
. We study one such algorithm next. The
algorithm estimates the probability
p
of a DNF
=
φ
1
∨
φ
2
∨···∨
φ
n
, over independent Boolean
random variables. The clauses
φ
i
are assumed to be in some order that will be made use of but is
arbitrary. We use
n
to denote the
number
of clauses in the DNF.
Let
M
=
=
i
P(φ
i
)
. Here,
P(φ
i
)
is, of course, the product of the probabilities of the literals
(i.e., random variables or their negations) occurring in
φ
i
. Recall that
ω(φ
i
)
denotes the set of
assignments
θ
that make
φ
i
true;
θ
denote complete assignments, including assignments to variables
that do not occur in
φ
i
.
Definition 5.11
Karp-Luby Estimator
The Karp-Luby estimator for the probability of DNF
over independent Boolean random variables is:
1. Choose a number
i
∈[
n
]
with probability
P(φ
i
)/M
.
2. Choose a valuation
θ
ω(φ
i
)
, with probability
P (θ)/P (φ
i
)
. This means the following: every
variable
X
occurring in
φ
i
is set deterministically to what is required by
φ
i
, and every variable
Y
of
which does not occur in
φ
i
is set to true with probability
P(Y)
.
∈
3. Consider the indexes of the conjunctions of
that are consistent with
θ
, i.e., the indexes
j
such that
θ
∈
ω(φ
j
)
.If
i
is the smallest among these, return
Z
=
1; otherwise, return
Z
=
0. In other words, return 1 iff
φ
1
[
θ
]=
...φ
i
−
1
[
θ
]=
false
(and note that
φ
i
[
θ
]=
true
by
construction).
The algorithm proceeds by computing the Karp-Luby estimator
N
times and returning their
mean times
M
. If we use 0-1-random variable
Z
k
to represent the outcome of the
k
-th call of the
Karp-Luby estimator, the result of the algorithm can be modeled by the random variable
p
, where:
N
Z
·
M
N
Z
=
Z
k
,
p
ˆ
=
k
=
1
