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