Database Reference
In-Depth Information
i
i
z
z
x
x
i
i
i
x
R(z,x)
S(x,y)
R(z,x)
S(x,y)
R(z,x) =
S(x,y) =
Q(z)
:−
R(z,x),S(x,y)
Q
[
c
1
/z
]
=
X
1
Y
1
∨
X
1
Y
2
∨
X
2
Y
3
P(c
1
∈
Q)
=
P(
c
1
)
=
1
−[
1
−
p
1
·
(
1
−
(
1
−
q
1
)
·
(
1
−
q
2
))
]·
(
1
−
p
2
·
q
3
)
Figure 4.3:
An extensional plan (left) and a safe plan (right). On the given database the query returns two
tuples,
c
1
,c
2
. The plan on the left computes the probabilities incorrectly; the plan on the right computes
them correctly. We show the lineage of the output
c
1
, and its probability: one can see that it is equal to
the probability returned by the safe plan.
4.2.1.2 Independent Project
The independent projection
i
A
(R)
of a relation
R
on a set of attributes
A
is the regular projection
A
(R)
extended with a probability attribute computed as follows. If
u
1
,u
2
,...,u
k
are all the
tuples in
R
that have a common value
A
attribute, then the probability of
a
of the
a
is set to
