Extensional Query Evaluation - Probabilistic Databases - page 81

i i

u,v

i

i

u

v

z

i

x y

i

i

i

u,v,z

R(x) S(u,x) R(z) S(u,z) T(v,z) R(y) T(v,y)

Q(u, v) :− R(x), S(u, x), R(y), T (v, y)

i

∪

Figure 4.6: A safe plan illustrating the need for outer joins. The expression S(u, z)

u,v,z T(v,z) is

domain-dependent and computes A(u, v, z) = S(u, z) ∨ T(v,z) ; it can be replaced with the outerjoin

S(u, z) d—><—d T(v,z) .

to base relations, as in the last query in Example 4.30 ; if we do not apply all required ranking rules
before invoking the algorithm, then it may fail to find a safe plan.

4.2.3 EXTENSIONAL PLANS FOR UNSAFE QUERIES
If Q is unsafe, then it does not have a safe plan. But we can still use an extensional to compute it,
with the understanding that the output probabilities are incorrect. In some cases, these probabilities
are approximations of the correct probabilities in a precise sense, allowing us to use the extensional
plan to approximate the output probabilities.