Database Reference
In-Depth Information
L
L
with the
following property: for every database instance
D
with
n
tuples, the lineage
Q
has an OBDD
of size
(OBDD)
=
k
≥
1
L
(OBDD,k)
, where
L
(OBDD,k)
is the set of queries
Q
∈
≤
O(n
k
)
. In other words,
L
(OBDD)
is the class of queries that have a polynomial-size
OBDD.
L
(FBDD)
is the class of queries
Q
∈
L
that have a polynomial-size FBDD (defined similarly
to
L
(OBDD)
).
(d-DNNF
¬
)
is the class of queries that have a polynomial-size d-DNNF
¬
.
L
L
(P )
is the class of tractable queries.
L
The compilation target RO differs from the others, in that
(RO)
is the set of queries that
have
some
read-once circuit. In other words, queries that are not
L
(RO)
do not have a read-once
C
C
circuit at all. In contrast, for any other target
, every query can be compiled into the target
, and
L
(
C
)
denotes the class of queries for which the compilation is
efficient
. In all cases however,
L
(
C
)
C
denotes the class of queries that have an efficient compilation into
because, even in the case of
read-once formulas, the read-once circuit is linear in the size of the input database.
We have immediately:
(d-DNNF
¬
)
L
(RO)
⊆
L
(OBDD)
⊆
L
(FBDD)
⊆
L
⊆
L
(P )
(5.10)
5.4.1 CONJUNCTIVE QUERIES WITHOUT SELF-JOINS
For conjunctive queries without self-join, these classes collapse:
CQ
NR
be the language of non-repeating
conjunctive queries (a.k.a. conjunctive queries without self-joins). Then,
[
Olteanu and Huang
,
2008
]
Let
L
=
Theorem 5.13
L
(RO)
=
L
(P )
. In par-
ticular, all inclusions in
Eq. (5.10)
become equalities.
In other words, a conjunctive query with self-joins is either very easy (read-once), or it is very
hard (hard for #P): there is no middle ground. The proof follows immediately from
Theorem 4.29
.
Indeed, let
Q
∈
CQ
NR
(P )
be a tractable conjunctive query without self-joins. By
Theorem 4.29
,
the query is hierarchical and non-repeating. Therefore, by
Proposition 4.27
(see comment after the
proof ) the query's lineage is read-once.