Database Reference
In-Depth Information
3. THE QUERY EVALUATION PROBLEM
More, they prove that a conjunctive query without self-joins is hard iff it is
non-hierarchical
(a
concept we define in the next chapter), and this happens iff the query contains three atoms of
the form
R(...,x,...),S(...,x,...,y,...),T(...,y,...)
. In other words, we can say, with some
abuse, that the query
H
0
is the
only
conjunctive query without self-joins that is hard. Note that
the query
R(x),S(x,y),R(y)
considered earlier by
Grädel et al.
[
1998
] is a conjunctive query
with
self-join, hence it does not fall under the class discussed by
Dalvi and Suciu
[
2004
].
Dalvi and Suciu
[
2007a
] study the complexity of the evaluation problem for conjunctive
queries (with or without self-joins). They establish the hardness for some queries that are re-
lated to the queries
H
k
. Note that
H
k
is not a conjunctive query, since it uses
∨
: the queries
defined by
Dalvi and Suciu
[
2007a
] are obtained from
H
k
by replacing the
's. For
example, instead of
H
1
, they consider
H
1
=
R(x
0
), S(x
0
,y
0
), S(x
1
,y
1
), T (y
1
)
, which is a con-
junctive query with a self-join. For every
k
, hardness of
H
k
implies hardness of
H
k
, and vice
versa, because the inclusion-exclusion formula reduces the evaluation problem for
H
k
to that
for
H
k
and several tractable queries. The details of the hardness proofs of
H
k
can be found
in [
Dalvi and Suciu
,
2010
], which prove the hardness result of
forbidden
queries: these in-
clude all queries
H
k
, but also many other queries, like
R(x, y
1
), S
1
(x, y
1
), R(x, y
2
), S
2
(x, y
2
)
∨
S
1
(x
,y
), S
2
(x
,y
), S
3
(x
,y
)
∨
S
3
(x
,y
), T (y
)
, whose hardness needs to be proven directly (it
does not seem to follow from the hardness of the queries
H
k
).
Dalvi and Suciu
[
2007a
] also describe an algorithm for evaluating conjunctive queries with
self-joins over tuple-independent databases, but the algorithm is very complex, and is totally super-
seded by a new approach of
Dalvi et al.
[
2010
], which we describe in the next chapter.
Dalvi and Suciu
[
2007c
] discuss the complexity of conjunctive queries without self-joins over
BID tables, and prove a dichotomy into polynomial time and #P-hard. They show that, if one allows
BID tables in the queries in addition to tuple-independent tables, then the class of hard queries is
strictly larger: it includes
H
0
, since every tuple-independent database is, in particular, a BID database,
but also includes two more patterns, which we review briefly in
Subsection 4.3.1
.
The complexity of several other query languages has been considered in the literature:
queries with disequality joins (
∨
's with
∧
)by
Olteanu and Huang
[
2008
], with inequality joins
(<)
by
Olteanu and Huang
[
2009
], with NOT EXISTS predicates by
Wang et al.
[
2008b
], with a
HAVING
clause by
Ré and Suciu
[
2009
], and unrestricted relational algebra queries, and in particular
“quantified queries” such as relational division, by
Fink et al.
[
2011b
].
=
