Database Reference
In-Depth Information
i
z
i
i
i
i
i
i
z
z
z
z
x
x
x
x
i
i
i
i
i
i
i
i
x
x
x
x
R(z,x)
S(x,y)
R(z,x)
S(x,y)
T(z,x)
S(x,y)
T(z,x)
S(x,y)
Q
J
(z)
:−
R(z, x
1
), S(x
1
,y
1
), T (z, x
2
), S(x
2
,y
2
)
Figure 4.4:
A safe plan for a conjunctive query with self-joins.
Figure 4.3
denotes a table with three attributes
S(x,y,P)
, but we omit the probability
P
. All joins
are natural joins; thus,
R(x)
x
S(x,y)
means the natural join on the
x
-attribute, and we follow
standard practice of including the common attributes only once in the output relation.
For any non-Boolean query, its head variables are treated as constants for the purpose of
attribute-constant ranking. For example, consider the query
Q(u)
=
R(x, u), R(u, x)
This query is
identical to
Q
2
in
Example 4.9
except that it uses a head variable
u
instead of a constant. The ranked
query is
Q
r
(u)
=
(R(x, u), x
=
u), (R(u, x), x
=
u)
∨
(R(x, u), x
=
u)
hence a safe plan is:
i
u
[
i
x,u
σ
x
=
u
(R(u, x))
i
u
i
u
[
Q
=
σ
x
=
u
(R(x, u))
]∪
σ
x
=
u
(R(x, u))
]