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.
Search WWH ::




Custom Search