  Several query evaluation tasks can be done via knowledge compilation: the
query result is compiled as a lineage circuit from which the answer can be
determined. For such tasks, it is important to leverage some width parameters
of the circuit, such as bounded treewidth or pathwidth, to convert the circuit
to structured classes, e.g., deterministic structured NNFs (d-SDNNFs) or OBDDs.
In this work, we show how to connect the width of circuits to the size of their
structured representation, through upper and lower bounds. For the upper bound,
we show how bounded-treewidth circuits can be converted to a d-SDNNF, in time
linear in the circuit size. Our bound, unlike existing results, is constructive
and only singly exponential in the treewidth. We show a related lower bound on
monotone DNF or CNF formulas, assuming a constant bound on the arity (size of
clauses) and degree (number of occurrences of each variable). Specifically, any
d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size
in its treewidth; and the same holds for pathwidth when compiling to OBDDs. Our
lower bounds, in contrast with most previous work, apply to any formula of this
class, not just a well-chosen family. Hence, for our language of DNF and CNF,
pathwidth and treewidth respectively characterize the efficiency of compiling
to OBDDs and (d-)SDNNFs, that is, compilation is singly exponential in the
width parameter. We conclude by applying our lower bound results to the task of
query evaluation.
