Database Reference
In-Depth Information
The probability
P(R(a)
∨
T(a))
is simply 1
−
(
1
−
P (R(a)))
·
(
1
−
P (T (a)))
while the probability
P(
∃
y.S(a,y))
is 1
−
b
∈
ADom(D)
(
1
−
P (S(a, b)))
.
What is remarkable about
Q
J
is the following fact.
Q
J
is a conjunctive query (with self-joins),
but in order to evaluate it, we needed to use
Q
U
, which is a union of conjunctive queries. In other
words, CQ is not a natural class to consider in isolation for studying query evaluation on probabilistic
databases: UCQ is a natural class.
Example 4.8
A Tractable Query With An Intractable Subquery
Our next example is interesting
because it contains
H
1
as a subquery, yet the query is tractable:
Q
V
=
R(x
1
), S(x
1
,y
1
)
∨
S(x
2
,y
2
), T (y
2
)
∨
R(x
3
), T (y
3
)
The first two union terms represents
H
1
, which is hard. On the other hand, the third union term
is the conjunction of
R(x
3
)
and
T(y
3
)
that do not share any variables. Therefore, we can apply
distributivity and rewrite
Q
V
from DNF to CNF:
Q
V
=
[
R(x
1
), S(x
1
,y
1
)
∨
S(x
2
,y
2
), T (y
2
)
∨
R(x
3
)
]
∧
[
R(x
1
), S(x
1
,y
1
)
T(y
3
)
]
=
[
S(x
2
,y
2
), T (y
2
)
∨
R(x
3
)
]
∧
[
R(x
1
), S(x
1
,y
1
)
∨
T(y
3
)
]
∨
S(x
2
,y
2
), T (y
2
)
∨
We applied the logical equivalence
R(x
1
), S(x
1
,y
1
)
∨
R(x
3
)
≡
R(x
3
)
. Now we use the inclusion-
exclusion formula and obtain:
P(Q
V
)
=
P(S(x
2
,y
2
), T (y
2
)
T(y
3
))
−
P(S(x
2
,y
2
), T (y
2
)
∨
R(x
3
)
∨
R(x
1
), S(x
1
,y
1
)
∨
T(y
3
))
∨
R(x
3
))
+
P(R(x
1
), S(x
1
,y
1
)
∨
=
P(S(x
2
,y
2
), T (y
2
)
∨
R(x
3
))
+
P(R(x
1
), S(x
1
,y
1
)
∨
T(y
3
))
−
P(R(x
3
)
∨
T(y
3
))
Each of the three probabilities on the last line can be computed easily, by first applying the
independent-union rule. For example, the first probability becomes:
P(S(x
2
,y
2
), T (y
2
)
∨
R(x
3
))
=
1
−
(
1
−
P(S(x
2
,y
2
), T (y
2
)))
·
(
1
−
P(R(x
3
)))
Ranking
We give here three examples of ranking. First, lets revisit the Boolean
Example 4.9
conjunctive query
Q
1
=
R(x,y),R(y,x)
which we already illustrated in the context of ranking in
Subsection 4.1.2
. There is no separator
variable:
x
is a root variable, but no separator variable because it occurs in different positions in
