Database Reference
In-Depth Information
z
i
i
i
i
z
z
z
i
i
z
z
i
i
i
i
z
z
y
x i
i
i
i
z
ii
z
R(z,x)
T(z,y)
i
i
y
x
y
R(z,x)
T(z,y)
S(x,y)
T(z,y)
R(z,x)
S(x,y)
Q V (z) :− R(z, x 1 ), S(x 1 ,y 1 )
Q V (z)
S(x 2 ,y 2 ), T (z, y 2 )
Q V (z) :− R(z, x 3 ), T (z, y 3 )
:−
Figure 4.5: A safe plan for a union of conjunctive queries. The query is shown in datalog notation,
and it is equivalent to (
x 3 .R(z, x 3 )
∨∃
x 2 .
y 2 .S(x 2 ,y 2 ), T (z, y 2 ))
(
x 1 .
y 1 .R(z, x 1 ), S(x 1 ,y 1 )
y 3 .T (z, y 3 )) .
4.2.2 AN ALGORITHM FOR SAFE PLANS
We now give an algorithm that computes a safe plan for a query Q , or indicates that none exists. The
algorithm adapts the six rules in Subsection 4.1.2 to compute operators rather than probabilities,
and it is shown in Algorithm 1 . The algorithms assumes that the ranking rule has already been
applied. That means that some of the relations used in the query Q are actually selections applied
 
Search WWH ::




Custom Search