Database Reference
In-Depth Information
Algorithm 1 Input:
A query
Q( x)
, with head variables
x
.
Output:
A safe query plan for
Q( x)
,or
fail
if none exists.
Assumption
We assume that the attributes in the query have already been attribute-ranked; thus,
some of the tables
R
occurring in the query are actually selections over base tables.
1:
algorithm
plan
(Q( x))
.
2:
if
Q(
x)
¯
=
Q
1
(
x)
¯
∧
Q
2
(
x)
, where
Q
1
,Q
2
are syntactically independent
then
¯
i
return
plan
(Q
1
)
x
plan
(Q
2
)
3:
4:
end if
5:
if
Q( x)
=
Q
1
( x)
∨
Q
2
( x)
where
Q
1
,Q
2
are syntactically independent
then
6:
i
return
plan
(Q
1
)
∪
x
plan
(Q
2
)
7:
end if
8:
if
Q( x)
has a separator variable
z
:
Q( x)
=∃
z.Q
1
( x,z)
then
9:
return
i
x
(
plan
(Q
1
))
/* the new head variables of
Q
1
are
x
¯
∪{
z
}
*/
10:
end if
11:
if
Q(
x)
¯
=
Q
1
(
x)
¯
∧
...
∧
Q
k
(
x)
,
k
¯
≥
2
then
{
u
|
u
∈
L, u
=
1
, μ(u,
1
)
=
0
}={
u
1
,...,u
m
}
let
L
be the CNF lattice of
Q
, and
12:
return
−
μ(u
1
,
1
),...,
−
μ(u
m
,
1
)
(
plan
(Q
u
1
),...,
plan
(Q
u
m
))
13:
x
14:
end if
15:
if
Q( x)
=¬
Q
1
( x)
then
16:
return
C
x
(
plan
(Q
1
))
17:
end if
18:
if
Q(
x)
¯
=
a base table
R(
x)
(possibly ranked by attributes and/or constants)
then
¯
19:
return
R(x)
.
20:
end if
21:
otherwise FAIL
/* no safe plan exists */
Consider the unsafe plan on the left of
Figure 4.3
. The query is safe, but the plan on the left
is “unsafe”. We claim that the unsafe plan computes an upper bound of the correct probabilities. In
particular, the probability for
c
1
returned by the plan on the right is
≤
that returned by the plan on
the left, in other words 1
−
p
1
q
1
)
·
(
1
−
p
1
q
2
)
·
(
1
−
p
2
q
3
)
. Instead of showing this directly (which is possible but tedious), we give
the general statement, which is much easier to understand. To give the intuition, let
denote the
correct lineage for the output
c
1
, and let
d
−[
1
−
p
1
·
(
1
−
(
1
−
q
1
)
·
(
1
−
q
2
))
]·
(
1
−
p
2
·
q
3
)
≤
1
−
(
1
be the lineage of the same output computed by the
unsafe plan. Then:
=
X
1
Y
1
∨
X
1
Y
2
∨
X
2
Y
3
d
=
X
1
Y
1
∨
X
1
Y
2
∨
X
2
Y
3
