Database Reference
In-Depth Information
stuck, it is technically in the separator variable step, when we cannot find a separator variable. We
will show later that, for UCQ queries, the rules are complete (once we replace inclusion-exclusion
with Möbius' inversion formula), in the sense that every unsafe query is provably hard; thus, UCQ
admits a dichotomy.
4.1.3 EXAMPLES OF UNSAFE (INTRACTABLE) QUERIES
Before we illustrate how the rules work, we will briefly illustrate how they fail. Recall the list of
intractable queries from
Section 3.2
:
H
0
=
R(x),S(x,y),T(y)
H
1
=
R(x
0
), S(x
0
,y
0
)
∨
S(x
1
,y
1
), T (y
1
)
H
2
=
S
2
(x
2
,y
2
), T (y
2
)
H
3
=
R(x
0
), S
1
(x
0
,y
0
)
∨
S
1
(x
1
,y
1
), S
2
(x
1
,y
1
)
∨
S
2
(x
2
,y
2
), S
3
(x
2
,y
2
)
∨
S
3
(x
3
,y
3
), T (y
3
)
...
R(x
0
), S
1
(x
0
,y
0
)
∨
S
1
(x
1
,y
1
), S
2
(x
1
,y
1
)
∨
We have already seen in
Chapter 3
that these queries are intractable; hence, they cannot be
safe (unless
P
=
#
P
). However, it is useful to understand how the rules fail to apply in each case,
so we briefly discuss why each of them is unsafe.
Consider
H
0
. We cannot apply an independent-project because no variable is a root vari-
able:
x
does not occur in the atom
T(y)
and
y
does not occur in
R(x)
. We cannot apply the
independent join because we cannot write
H
0
=
Q
1
∧
Q
2
where both
Q
1
and
Q
2
are Boolean
queries; for example, if we write it as
R(x)
T(y)
must share the variable
x
; hence, they are not Boolean queries. For the same reason, we cannot
apply the inclusion-exclusion rule. We could rank
S(x,y)
by its two attributes, and split it into
S
1
=
σ
x<y
(S(x, y))
,
S
2
=
x
(σ
x
=
y
(S(x, y)))
,
S
3
=
yx
(σ
x>y
(S(x, y)))
, but this doesn't help; we
obtain
H
0
=
R(x), S
1
(x, y), T (y)
∨
R(x), S
2
(x), T (x)
∨
R(x), S
3
(y, x), T (y)
, and we are stuck
because this query has no separator variable (neither the first nor the last query have a root variable).
Thus, the rules fail on
H
0
.
The rules also fail on
H
1
. While it is the disjunction of two Boolean queries, they are not
independent (both contain
S
). If we tried to apply the independent-project rule by substituting
z
∧
(S(x, y)
∧
T(y))
, then
R(x)
and
S(x,y)
∧
y
1
.S(z, y
1
), T (y
1
))
then
z
occurs in the same position in both atoms
S(z,y
0
)
and
S(z,y
1
)
, but it is not a root variable because
it does not occur in
T(y
1
)
.Ifwetried
z
=
x
0
=
x
1
(as we did in
Eq. (4.3)
),
H
1
≡∃
z.(
∃
y
0
.R(z), S(z, y
0
)
∨∃
∨
T(z)
∧∃
x
1
.S(x
1
,z))
;now
z
is a root variable, but it is not a separator variable because it occurs on
different positions in
S(z,y
0
)
and in
S(x
1
,z)
. The reader can check that none of the rules applies
to any
H
k
, for any
k
≥
=
x
0
=
y
1
instead, then
H
1
≡∃
z.(R(z)
∧∃
y
0
.S(z, y
0
)
0.
