Antoine Amarilli

Mikaël Monet

Pierre Senellart

Connecting Width and Structure in Knowledge Compilation

Keywords: 1998 ACM Subject Classification H.2 DATABASE knowledge compilation, probabilistic databases, treewidth, circuits Digital Object Identifier 10.4230/LIPIcs.ICDT.2018

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Uncertainty and errors in data can be modeled using probabilistic databases [START_REF] Suciu | Probabilistic Databases[END_REF], annotating every tuple with a probability of existence. Query evaluation on probabilistic databases must then handle the uncertainty by computing the probability that each query result holds. A common technique to evaluate queries on probabilistic databases is the intensional approach: first compute a representation of the lineage of the query on the database, which intuitively describes how the query depends on the possible database facts; then use this lineage to compute probabilities efficiently. Specifically, the lineage can be computed as a circuit [START_REF] Kumar | On the tractability of query compilation and bounded treewidth[END_REF], and efficient probability computation can be achieved by restricting to tractable circuit classes via knowledge compilation. Thus, to evaluate queries on probabilistic databases, we can use knowledge compilation algorithms to translate circuits to tractable classes; conversely, lower bounds in knowledge compilation can identify the limits of the intensional approach.

In this paper, we study the relationship between two kinds of tractable circuit classes in knowledge compilation: width-based classes, specifically, bounded-treewidth and boundedpathwidth circuits; and structure-based classes, specifically, OBDDs (ordered binary decision Result 3 (Theorem 25). Let ϕ be a monotone DNF (resp., monotone CNF), let a := arity(ϕ) and d := degree(ϕ). Then any d-SDNNF (resp., SDNNF) for ϕ has size 2 Ω tw(ϕ) a 3 ×d 2 . Our two lower bounds contribute to a vast landscape of knowledge compilation results giving lower bounds on compiling specific Boolean functions to restricted circuits classes, e.g., [START_REF] Bova | On compiling structured CNFs to OBDDs[END_REF][START_REF] Devadas | Comparing two-level and ordered binary decision diagram representations of logic functions[END_REF][START_REF] Razgon | On OBDDs for CNFs of bounded treewidth[END_REF] to OBDDs, [START_REF] Calì | Non-FPT lower bounds for structural restrictions of decision DNNF[END_REF] to decision structured DNNF, [START_REF] Beame | New limits for knowledge compilation and applications to exact model counting[END_REF] to sentential decision diagrams (SDDs), [START_REF] Bova | Knowledge compilation meets communication complexity[END_REF][START_REF] Pipatsrisawat | A lower bound on the size of decomposable negation normal form[END_REF] to d-SDNNF, [START_REF] Bova | Knowledge compilation meets communication complexity[END_REF][START_REF] Capelli | Structural restrictions of CNF-formulas: applications to model counting and knowledge compilation[END_REF][START_REF] Capelli | Understanding the complexity of #SAT using knowledge compilation[END_REF] to d-DNNFs and DNNFs. However, all those lower bounds (with the exception of some results in [START_REF] Capelli | Structural restrictions of CNF-formulas: applications to model counting and knowledge compilation[END_REF][START_REF] Capelli | Understanding the complexity of #SAT using knowledge compilation[END_REF] discussed in Section 6) apply to well-chosen families of Boolean functions (usually CNF), whereas Result 2 and 3 apply to any monotone CNF and DNF. Together with Result 1, these generic lower bounds point to a strong relationship between width parameters and structure representations, on monotone CNFs and DNFs of constant arity and degree. Specifically, the smallest width of OBDD representations of any such formula ϕ is in 2 Θ(pw(ϕ)) , i.e., precisely singly exponential in the pathwidth; and an analogous bound applies to d-SDNNF size and treewidth of DNFs.

To prove our lower bounds, we rephrase pathwidth and treewidth to new notions of pathsplitwidth and treesplitwidth, which intuitively measure the performance of a variable ordering or v-tree. We also use the disjoint non-covering prime implicant sets (dncpi-sets), a tool introduced in [START_REF] Amarilli | Leveraging the Structure of Uncertain Data[END_REF][START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF] by some of the present authors, and generalizing subfunction width [START_REF] Bova | On compiling structured CNFs to OBDDs[END_REF]. These dncpi-sets allow us to derive lower bounds on OBDD width directly using [START_REF] Amarilli | Leveraging the Structure of Uncertain Data[END_REF]. We show how they can also imply lower bounds on d-SDNNF size, using the recent communication complexity approach of Bova, Capelli, Mengel and Slivovsky [START_REF] Bova | Knowledge compilation meets communication complexity[END_REF].

Our fourth contribution (Section 7) applies our lower bounds to intensional query evaluation on relational databases. We reuse the notion of intricate queries of [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF], and show that d-SDNNF representations of the lineage of these queries have size exponential in the treewidth of any input instance. This extends the result of [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF] from OBDDs to d-SDNNFs:

Result 4 (Theorem 33). There is a constant d ∈ N such that the following is true. Let σ be an arity-2 signature, and Q be a connected UCQ = which is intricate on σ. For any instance I on σ, any d-SDNNF representing the lineage of Q on I has size 2 Ω(tw(I) 1/d ) .

As in [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF], this result shows that, on arity-2 signatures and under constructibility assumptions, treewidth is the right parameter on instance families to ensure that all queries (in monadic second-order) have tractable d-SDNNF lineage representations.

We start in Section 2 with preliminaries. Full proofs of all results are provided in the extended version [START_REF] Amarilli | Connecting width and structure in knowledge compilation (extended version)[END_REF].

Preliminaries

Hypergraphs, treewidth, pathwidth. A hypergraph H = (V, E) consists of a finite set of nodes (or vertices) V and of a set E of hyperedges (or simply edges) which are non-empty subsets of V . We always assume that hypergraphs have at least one edge. For a node v of H, we write E(v) for the set of edges of H that contain v. The arity of H, written arity(H), is the maximal size of an edge of H. The degree of H, written degree(H), is the maximal number of edges to which a vertex belongs, i.e., max v∈V |E(v)|.

A tree decomposition of a hypergraph H = (V, E) is a finite, rooted tree T , whose nodes b (called bags) are labeled by a subset λ(b) of V , and which satisfies:

1. for every fact e ∈ E, there is a bag b ∈ T with e ⊆ λ(b); 2. for all v ∈ V , the set of bags {b ∈ T | v ∈ λ(b)} is a connected subtree of T .
For brevity, we identify a bag b with its domain λ(b). The width of T is max b∈T |λ(b)| -1. The treewidth of H is the minimal width of a tree decomposition of H. Pathwidth is defined similarly but with path decompositions, where T is a path rather than a tree.

It is NP-hard to determine the treewidth of a hypergraph, but we can compute a tree decomposition in linear time when parametrizing by the treewidth: Theorem 1 ([10]). Given a hypergraph H and an integer k ∈ N we can check in time O(|H| × g(k)) whether H has treewidth k, and if yes output a tree decomposition of H of width k, where g is a fixed function in O(2 (32+ε)k 3 ) for any ε > 0.

I C D T 2 0 1 8

6:4 Connecting Width and Structure in Knowledge Compilation

For simplicity, we will often assume that a tree decomposition is nice, meaning that:

1. it is a full binary tree, i.e., each node has exactly zero or two children; Boolean circuits and functions. A (Boolean) valuation of a set V is a function ν : V → {0, 1}. A Boolean function ϕ on variables V is a mapping that associates to each valuation ν of V a Boolean value in {0, 1} called the evaluation of ϕ according to ν.

A (Boolean) circuit C = (G, W, g output , µ
) is a directed acyclic graph (G, W ) whose vertices G are called gates, whose edges W are called wires, where g output ∈ G is the output gate, and where each gate g ∈ G has a type µ(g) among var (a variable gate), not, or, and. The inputs of a gate g ∈ G are the gates g ∈ G such that (g , g) ∈ W ; the fan-in of g is its number of inputs. We require not-gates to have fan-in 1 and var-gates to have fan-in 0. The treewidth of C, and its size, are those of the graph (G, W ). The set C var of variable gates of C are those of type var. Given a valuation ν of C var , we extend it to an evaluation of C by mapping each variable g ∈ C var to ν(g), and evaluating the other gates according to their type. The Boolean function on C var captured by the circuit is the one that maps ν to the evaluation of g output under ν. Two circuits are equivalent if they capture the same function.

We recall restricted circuit classes from knowledge compilation. We say that C is in negation normal form (NNF) if the inputs of not-gates are always variable gates. For a gate g in a Boolean circuit C, we write Vars(g) for the set of variable gates of C var that have a directed path to g in C. An and-gate g of C is decomposable if for every two input gates g 1 = g 2 of g we have Vars(g 1 ) ∩ Vars(g 2 ) = ∅. We call C decomposable if each and-gate is.

A stronger requirement than decomposability is structuredness. A v-tree [START_REF] Pipatsrisawat | New compilation languages based on structured decomposability[END_REF] over a set V is a rooted ordered binary tree T whose leaves are in bijection with V ; we identify each leaf with the associated element of V . For n ∈ T , we denote by T n the subtree of T rooted at n, and for a subset U ⊆ T of nodes of T , we denote by Leaves(U ) the leaves that are in U , i.e., U ∩ V . We say that T structures a Boolean circuit C (and call it a v-tree for C) if T is over the set C var and if, for every and-gate g of C with inputs g 1 , . . . , g m and m > 0, there is a node n ∈ T that structures g, i.e., n has m children n 1 , . . . , n m and we have Vars(g i ) ⊆ Leaves(T ni ) for all 1 i m. We call C structured if some v-tree structures it. Note that structured Boolean circuits are always decomposable, and their and-gates have at most two inputs because T is binary.

A last requirement on circuits is determinism. An or-gate g of C is deterministic if there is no pair g 1 = g 2 of input gates of g and valuation ν of C var such that g 1 and g 2 both evaluate to 1 under ν. A Boolean circuit is deterministic if each or-gate is.

The main structured class of circuits that we study in this work are deterministic structured decomposable NNFs, which we denote d-SDNNF for brevity as in [START_REF] Pipatsrisawat | New compilation languages based on structured decomposability[END_REF].

DNFs and CNFs.

We also study other representations of Boolean functions, namely, Boolean formulas in conjunctive normal form (CNFs) and in disjunctive normal form (DNFs). A DNF (resp., CNF) ϕ on a set of variables V is a disjunction (resp., conjunction) of clauses, each of which is a conjunction (resp., disjunction) of literals on V , i.e., variables of V (a positive literal) or their negation (a negative literal). A monotone DNF (resp., monotone CNF) is one where all literals are positive, in which case we often identify a clause to the set of variables that it contains. We always assume that monotone DNFs and monotone CNFs are minimized, i.e., no clause is a subset of another. This ensures that every monotone Boolean function has a unique representation as a monotone DNF (the disjunction of its prime implicants), and likewise for CNF. We assume that CNFs and DNFs always contain at least one non-empty clause (in particular, they cannot represent constant functions). Monotone DNFs and CNFs ϕ are isomorphic to hypergraphs: the vertices are the variables of ϕ, and the hyperedges are the clauses of ϕ. We often identify ϕ to its hypergraph. In particular, the pathwidth and treewidth of ϕ, and its arity and degree, are defined as that of its hypergraph.

Upper Bounds

Our upper bound result studies how to compile a Boolean circuit to a d-SDNNF, parametrized by the treewidth of the input circuit. To present it, we first review the independent result that was recently shown by Bova and Szeider [START_REF] Bova | Circuit treewidth, sentential decision, and query compilation[END_REF] about these circuit classes:

Theorem 3 ([16, Theorem 3 and Equation ( 22)]). Given a Boolean circuit C with n variables and of treewidth k, there exists an equivalent d-SDNNF of size O(f (k) × n), where f is doubly exponential.

An advantage of their result is that it depends only on the number of variables of the circuit (and on the width parameter), not on the size of the circuit. None of our results will have this advantage, and we will always measure complexity as a function of the size of the input circuit. In exchange for this advantage, their result has two drawbacks: (i) the doubly exponential dependency on the width; and (ii) its nonconstructive aspect, because [START_REF] Bova | Circuit treewidth, sentential decision, and query compilation[END_REF] gives no time bound on the computation, leaving open the question of effectively compiling bounded-treewidth circuits to d-SDNNFs.

Naive constructive bound. We first address the second drawback by showing an easy constructive result. The argument is very simple and appeals to techniques from our earlier works on provenance circuits [START_REF] Amarilli | Provenance circuits for trees and treelike instances[END_REF][START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF]; it is independent from the techniques of [START_REF] Bova | Circuit treewidth, sentential decision, and query compilation[END_REF].

Theorem 4. Given any circuit C of treewidth k, we can compute an equivalent d-SDNNF in linear time parametrized by k, i.e., in time O(|C| × f (k))

for some computable function f . Proof sketch. We encode in linear time the input circuit C to a relational instance I with same treewidth. We use [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF]Theorem 6.11] to construct in linear time a provenance representation C on I of a fixed MSO formula that describes Boolean circuit evaluation. This allows us to obtain in linear time from C the desired equivalent d-SDNNF representation.

This result shows that we can effectively compile in linear time parametrized by the treewidth k, but does not address the first drawback, namely, the dependency in k.

Improved bound. Our main upper bound result subsumes the naive bound above, with a more elaborate proof, again independent of the techniques of [START_REF] Bova | Circuit treewidth, sentential decision, and query compilation[END_REF]. It addresses both drawbacks and shows that we can effectively compile in time singly exponential in k; formally:

Theorem 5. Given as input a Boolean circuit C and tree decomposition T of width k, we can compute a d-SDNNF equivalent to C with its v-tree, in

O |T | × 2 (4+ε)k for any ε > 0.
We prove Theorem 5 in the next section. Observe how we assume the tree decomposition to be given as part of the input. If it is not, we can compute one with Theorem 1, but this becomes the bottleneck: the complexity becomes O |C| × 2 (32+ε)k 3 for any ε > 0.

I C D T 2 0 1 8

6:6 Connecting Width and Structure in Knowledge Compilation

Applications. Theorem 5 implies several consequences for bounded-treewidth circuits. The first one deals with probability computation: we are given a probability valuation π mapping each variable g ∈ C var to a probability that g is true (independently from other variables), and we wish to compute the probability π(C) that C evaluates to true under π, assuming that arithmetic operations (sum and product) take unit time. This problem is #P-hard for arbitrary circuits, but it is tractable for d-SDNNF [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF]. Hence, our result implies the following, where |π| denotes the size of writing the probability valuation π: Corollary 6. Given a Boolean circuit C, a tree decomposition T of width k of C, and a probability valuation

π of C, we can compute π(C) in O |π| + |T | × 2 (4+ε)k for any ε > 0.
This improves the bound obtained when applying message passing techniques [START_REF] Lauritzen | Local computations with probabilities on graphical structures and their application to expert systems[END_REF] directly on the bounded-treewidth input circuit (as presented, e.g., in [5, Theorem D.2]). Indeed, message passing applies to moralized representations of the input: for each gate, the tree decomposition must contain a bag containing all inputs of this gate simultaneously, which is problematic for circuits of large fan-in. Indeed, if the original circuit has a tree decomposition of width k, rewriting it to make it moralized results in a tree decomposition of width 3k 2 (see [4, Lemmas 53 and 55]), and the bound of [5, Theorem D.2] then yields an overall complexity of O |π| + |T | × 2 3k 2 for message passing. Our Corollary 6 achieves a more favorable bound because Theorem 5 uses directly the associativity of and and or. We note that the connection between message-passing techniques and structured circuits has also been investigated by Darwiche, but his result [START_REF] Darwiche | A differential approach to inference in Bayesian networks[END_REF]Theorem 6] produces arithmetic circuits rather than d-DNNFs, and it also needs the input to be moralized.

A second consequence concerns the task of enumerating the accepting valuations of circuits, i.e., producing them one after the other, with small delay between each accepting valuation. The valuations are concisely represented as assignments, i.e., as a set of variables that are set to true, omitting those that are set to false. This task is of course NP-hard on arbitrary circuits (as it implies that we can check whether an accepting valuation exists), but was recently shown in [START_REF] Amarilli | A circuit-based approach to efficient enumeration[END_REF] to be feasible on d-SDNNFs with linear-time preprocessing and delay linear in the Hamming weight of each produced assignment. Hence, we have: Other applications of Theorem 5 include counting the number of satisfying valuations of the circuit (a special case of probability computation), MAP inference [START_REF] Fierens | Inference and learning in probabilistic logic programs using weighted Boolean formulas[END_REF] or random sampling of possible worlds (which can be done on the d-SDNNF in an easy manner).

Proof of the Main Upper Bound Result

In this section, we present the construction used to prove Theorem 5. We start with prerequisites, and then describe how to build the d-SDNNF equivalent to the input boundedtreewidth circuit. Last, we sketch the correctness proof.

Prerequisites. Let C be the input circuit, and T the input tree decomposition. By Lemma 2, we assume that T is nice. Further, up to adding a constant number of bags and re-rooting T , we can assume that the root bag of T contains only the output gate g output . To abstract away the type of gates and their values in the construction, we will talk of strong and weak values. Intuitively, a value is strong for a gate g if any input g of g which carries this value determines the value of g; and weak otherwise. Formally: Definition 8. Let g be a gate and c ∈ {0, 1}: If g is an and-gate, we say that c = 0 is strong for g and c = 1 is weak for g; If g is an or-gate, we say that c = 1 is strong for g and c = 0 is weak for g; If g is a not-gate, c = 0 and c = 1 are both strong for g; For technical convenience, if g is a var-gate, c = 0 and c = 1 are both weak for g. If we take any valuation ν : C var → {0, 1} of the circuit C = (G, W, g output , µ), and extend it to an evaluation ν : G → {0, 1}, then ν will respect the semantics of gates. In particular, it will respect strong values: for any gate g of C, if g has an input g for which ν(g ) is a strong value, then ν(g) is determined by ν(g ), specifically, it is ν(g ) if g is an oror an and-gate, and 1 -ν(g ) if g is a not-gate. In our construction, we will need to guess how gates of the circuit are evaluated, focusing on a subset of the gates (as given by a bag of T ); we will then call almost-evaluation an assignment of these gates that respects strong values. Formally: Definition 9. Let U be a set of gates of C. We call ν : U → {0, 1} a (C, U )-almostevaluation if it respects strong values, i.e., for every gate g ∈ U , if there is an input g of g in U and ν(g ) is a strong value for g, then ν(g) is determined from ν(g ) in the sense above.

Respecting strong values is a necessary condition for such an assignment to be extensible to a valuation of the entire circuit. However, it is not sufficient: an almost-evaluation ν may map a gate g to a strong value even though g has no input that can justify this value. This is hard to avoid: when we focus on the set U , we do not know about other inputs of g. For now, let us call unjustified the gates of U that carry a strong value that is not justified by ν: Definition 10. Let U be a set of gates of a circuit C and ν a (C, U )-almost-evaluation. We call g ∈ U unjustified if ν(g) is a strong value for g, but, for every input g of g in U , the value ν(g ) is weak for g; otherwise, g is justified. The set of unjustified gates is written Unj(ν).

Let us start to explain how to construct the d-SDNNF circuit D equivalent to the input circuit C. We do so by traversing T bottom-up, and for each bag b of T we create gates G ν,S b in D, where ν is a (C, b)-almost-evaluation and S is a subset of Unj(ν) which we call the suspicious gates of G ν,s b . We will connect the gates of D created for each internal bag b with the gates created for its children in T , in a way that we will explain later. Intuitively, for a gate G ν,S b of D, the suspicious gates g in the set S are gates of b whose strong value is not justified by ν (i.e., g ∈ Unj(ν)), and is not justified either by any of the almost-evaluations at descendant bags of b to which G ν,S b is connected. We call innocent the other gates of b; they are the gates that are justified in ν (in particular, those who carry weak values), and the gates that are unjustified in ν but have been justified by an almost-evaluation at a descendant bag b of b. Crucially, in the latter case, the gate g justifying the strong value in b may no longer appear in b, making g unjustified for ν; this is why we remember the set S.

We is such that (ν, S) is not connectible to the parent bag b , then this gate will not be used as input to any other gate (but we do not try to preemptively remove these useless gates in the construction). We are now ready to give the formal definition that will be used to explain how gates are connected: Definition 12. Let b be an internal bag with children b l and b r , let ν l and ν r be respectively (C, b l ) and (C, b r )-almost-evaluations that mutually agree, and S l ⊆ Unj(ν l ) and S r ⊆ Unj(ν r ) be sets of suspicious gates such that both (ν l , S l ) and (ν r , S r ) are connectible to b. The result of (ν l , S l ) and (ν r , S r ) is then defined as the pair (ν, S) where:

ν is a (C, b)-almost-evaluation defined as the restriction of ν l ∪ ν r to b. S ⊆ Unj(ν) is the new set of suspicious gates, defined as follows. A gate

g ∈ b is innocent (i.e., g ∈ b \ S) if it is justified for ν or if it is innocent for some child. Formally, b \ S := (b \ Unj(ν)) ∪ b ∩ [(b l \ S l ) ∪ (b r \ S r )] .
Construction. We now use these definitions to present the construction formally. For every variable gate g of C, we create a corresponding variable gate G g,1 of D, and we create G g,0 := not(G g,1 ). For every broot where b root is the root of T and ν maps g output to 1 (remember that b root contains only g output ).

Correctness. We have formally described the construction of our d-SDNNF D. The construction clearly works in linear time, and we can prove that the dependency on k of the running time is as stated. Further, we easily see that D is structured by a v-tree constructed from the tree decomposition T . To show that D is equivalent to C, one direction is easier: any valuation χ that satisfies C also satisfies D, because we can construct an accepting trace in D using the gates G ν,S b for ν the restriction of the evaluation χ to b, and for S := Unj(χ |T b ) where T b denotes the gates of C occurring in the bags of the subtree of T rooted at b. The converse is trickier: we show that any accepting trace of D describes an evaluation of C that respects strong values by definition of almost-evaluations, and eventually justifies every gate which is given a strong value thanks to our bookkeeping of suspicious gates. Last, we show that D is deterministic: this is unexpected because we freely guess the values of gates of C at leaf bags, but it holds because, when we know the valuation of the variable gates, knowing the valuation of all gates of a bag b uniquely fixes the valuation at the subtree rooted at b. This concludes the proof sketch of Theorem 5; see the extended version [START_REF] Amarilli | Connecting width and structure in knowledge compilation (extended version)[END_REF] for the full proof.

Lower Bounds on OBDDs

We now move to lower bounds on the size of structured representations of Boolean functions, in terms of the width of a circuit for that function. Our end goal is to obtain a lower bound for (d-)SDNNFs, that will form a counterpart to the upper bound of Theorem 5. We will do so in Section 6. For now, in this section, we consider a weaker class of lineage representations than (d-)SDNNFs, namely, OBDDs.

Definition 13. An ordered binary decision diagram (or OBDD) on a set of variables V = {v 1 , . . . , v n } is a rooted DAG O whose leaves are labeled by 0 or 1, and whose internal nodes are labeled with a variable of V and have two outgoing edges labeled 0 and 1. We require that there exists a total order v = v i1 , . . . , v in on the variables such that, for every path from the root to a leaf, the sequence of variables which labels the internal nodes of the path is a subsequence of v and does not contain duplicate variables. The OBDD O captures a Boolean function on V defined by mapping each valuation ν to the value of the leaf reached from the root by following the path given by ν. The size |O| of O is its number of nodes, and the width w of O is the maximum number of nodes at every level, where a level is defined for a prefix of v as the set of nodes reached by enumerating all possible valuations of this prefix.

Note that we clearly have |O| |V | × w.

Our upper bound in the previous section applied to arbitrary Boolean circuits; however, our lower bounds in this section and the next one will already apply to much weaker formalisms for Boolean functions, namely, monotone DNFs and monotone CNFs (recall their definition from Section 2). Some lower bounds are already known for the compilation of monotone CNFs into OBDDs: Bova and Slivovsky have constructed a family of CNFs of bounded degree whose OBDD width is exponential in their number of variable occurrences [START_REF] Bova | On compiling structured CNFs to OBDDs[END_REF]Theorem 19], following an earlier result of this type by Razgon [START_REF] Razgon | On OBDDs for CNFs of bounded treewidth[END_REF]Corollary 1]. The result is as follows:

Theorem 14 ([15, Theorem 19]). There is a class of monotone CNF formulas of bounded degree and arity such that every formula ϕ in this class has OBDD size at least 2 Ω(|ϕ|) .

We adapt some of these techniques to show a more general result: our lower bound applies to any monotone DNF or monotone CNF, not to one specific family. Specifically, we show: From our Theorem 15, we can easily derive Theorem 14 using the fact (also used in the proof of [START_REF] Bova | On compiling structured CNFs to OBDDs[END_REF]Theorem 19]) that there exists a family of monotone CNFs of bounded degree and arity whose treewidth (hence pathwidth) is linear in their size, namely, the CNFs built from expander graphs (see [START_REF] Grohe | On tree width, bramble size, and expansion[END_REF]Theorem 5 and Proposition 1]). Note that expander graphs can also be used to show lower bounds for (non-deterministic and non-structured) DNNFs for a CNF formula [START_REF] Bova | A strongly exponential separation of DNNFs from CNF formulas[END_REF]; our lower bound on SDNNFs of Section 6 does not capture this result (because we need structuredness).

We observe that, for a family of formulas with bounded arity and degree, the bound of Theorem 15 is optimal, up to constant factors in the exponent. Indeed, following earlier work [START_REF] Ferrara | Treewidth in verification: Local vs. global[END_REF][START_REF] Razgon | On OBDDs for CNFs of bounded treewidth[END_REF], Bova and Slivovsky have shown that any CNF ϕ can be compiled to OBDDs of width 2 pw(ϕ)+2 [15, Theorem 4 and Lemma 9]. (Their upper bound result also applies to DNFs, and does not assume monotonicity nor a bound on the arity or degree.) In other words, for any monotone DNF or monotone CNF of bounded arity and degree, pathwidth characterizes the width of an OBDD for the formula, in the following sense: Corollary 16. For any constant c, for any monotone DNF (or monotone CNF) ϕ with arity and degree bounded by c, the smallest width of an OBDD for ϕ is 2 Θ(pw(ϕ)) .

This corollary talks about the pathwidth of ϕ measured as that of its hypergraph, but note that the same result would hold when measuring the pathwidth of the incidence graph or dual hypergraph of ϕ. Indeed, all these pathwidths are within a constant factor of one another when the degree and arity are bounded by a constant. I C D T 2 0 1 8 6:10

Connecting Width and Structure in Knowledge Compilation

We prove Theorem 15 in the rest of this section. We present the proof in the case of monotone DNFs to reuse existing lower bound techniques from [START_REF] Amarilli | Leveraging the Structure of Uncertain Data[END_REF][START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF], but explain at the end of this section how the proof adapts to monotone CNFs. We first present pathsplitwidth, a new notion which intuitively measures the performance of a variable ordering for an OBDD on the monotone DNF ϕ, and connect it to the pathwidth of ϕ. Second, we recall the definition of dncpi-sets introduced in [START_REF] Amarilli | Leveraging the Structure of Uncertain Data[END_REF][START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF] to show lower bounds from the structure of Boolean functions. Last, we conclude the proof by connecting pathsplitwidth to the size of dncpi-sets.

Pathsplitwidth. The first step of the proof is to rephrase the bound on pathwidth, arity, and degree, in terms of a bound on the performance of variable orderings. Intuitively, a good variable ordering is one which does not split too many clauses. Formally: Definition 17. Let H = (V, E) be a hypergraph, and v = v 1 , . . . , v |V | be an ordering on the variables of V . For 1 i |V |, we define Split i (v, H) as the set of hyperedges e of H that contain both a variable at or before v i , and a variable strictly after v i , formally:

Split i (v, H) := {e ∈ E | ∃l ∈ {1, . . . , i} and ∃r ∈ {i + 1, . . . , |V |} such that {v l , v r } ⊆ e}. Note that Split |V | (v, H) is always empty. The pathsplitwidth of v relative to H is the maximum size of the split, formally, psw(v, H) := max 1 i |V | |Split i (v, H)|. The pathsplitwidth psw(H) of H is then the minimum of psw(v, H) over all variable orderings v of V .
In other words, psw(H) is the smallest integer n ∈ N such that, for any variable ordering v of the nodes of H, there is a moment at which n hyperedges of H are split, i.e., for n hyperedges e, we have begun enumerating the nodes of e but we have not enumerated all of them yet. We note that the pathsplitwidth of H is exactly the linear branch-width [START_REF] Alme | Exploring graph parameters similar to tree-width and pathwidth[END_REF] of the dual hypergraph of H, but we introduced pathsplitwidth because it fits our proofs better.

For a monotone DNF ϕ with hypergraph H, the quantity psw(H) is intuitively connected to the quantity of information that an OBDD will have to remember when evaluating ϕ following any variable ordering, which we will formalize via dncpi-sets. This being said, the definition of pathsplitwidth is also reminiscent of that of pathwidth, and we can indeed connect the two (up to a factor of the arity):

Lemma 18. For any hypergraph H = (V, E), we have pw(H) arity(H) × psw(H). Proof sketch. From a variable ordering v, we construct a path decomposition of H by creating |V | bags in sequence, each of which containing v i plus Split i (v, H). The width is arity(H) × psw(H), and we check the two conditions of path decompositions. First, each hyperedge of H is contained in a bag where it is split. Second, each vertex v i occurs in the corresponding bag b i and at all positions where the edges containing v are split, which forms a segment of v: thus, the connectedness condition of tree decompositions is respected.

Thanks to Lemma 18, it suffices to show that an OBDD for ϕ has width 2 psw(ϕ) (a×d) 2 , which we will do in the rest of this section. dncpi-sets. To show this lower bound, we use the technical tool of dncpi-sets [START_REF] Amarilli | Leveraging the Structure of Uncertain Data[END_REF][START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF]. We recall the definitions here, adapting the notation slightly. Remember that our monotone DNFs are assumed to be minimized. Note that dncpi-sets are reminiscent of subfunction width in [START_REF] Bova | On compiling structured CNFs to OBDDs[END_REF] (see Theorem 17 in [START_REF] Bova | On compiling structured CNFs to OBDDs[END_REF]), but the latter notion is only defined for graph CNFs. Given a variable ordering v of V , we say that v shatters a dncpi-set S if there exists 1 i |V | such that S ⊆ Split i (v, H), where H is the hypergraph of ϕ.

Observe the analogy between shattering and splitting, which we will substantiate below. We recall the main result on dncpi-sets:

Lemma 20 ([1, Lemma 6.4.7]). Let ϕ be a monotone DNF on variables V and n ∈ N. Assume that, for every variable ordering v of V , there is some dncpi-set S of ϕ with |S| n, such that v shatters S. Then any OBDD for ϕ has width 2 n . Proof sketch. Considering the point at which the dncpi-set is shattered, the OBDD must remember exactly the status of each clause of the set: any valuation that satisfies a subset of these clauses gives rise to a different continuation function. This is where we use the fact that the DNF is monotone: it ensures that we can freely choose a valuation of the variables that do not occur in the dncpi-set without making the formula true.

Concluding the proof. We conclude the proof of Theorem 15 by showing that any variable ordering of the variables of a monotone DNF ϕ shatters a dncpi-set of the right size. The formal statement is as follows, and it is the last result to prove: Lemma 21. Let ϕ be a monotone DNF, H its hypergraph, and v an enumeration of its variables. Then there is a dncpi-set S of ϕ shattered by v such that |S| psw(H) (arity(H)×degree(H)) 2 . We prove this result in the rest of the section. Our goal is to construct a dncpi-set, which intuitively consists of clauses that are disjoint and which do not cover another clause. We can do so by picking clauses sufficiently "far apart". Let the exclusion graph of H = (V, E) be the graph on E where two edges e = e are adjacent if there is an edge e of E with which they both share a node: this is in particular the case when e and e intersect as we can take e := e. Formally, the exclusion graph is G H = (E, {{e, e } ∈ E 2 | e = e ∧ ∃e ∈ E, (e ∩ e ) = ∅ ∧ (e ∩ e ) = ∅}). In other words, two hyperedges are adjacent in G H iff they are different and are at distance at most 4 in the incidence graph of H.

Remember that an independent set in the graph G H is a subset S of E such that no two elements of S are adjacent in G H . The definition of G H then ensures: Lemma 22. For any monotone DNF ϕ, letting H be its hypergraph, any independent set of the exclusion graph G H is a dncpi-set of ϕ.

In other words, our goal is to compute a large independent set of the exclusion graph. To do this, we will use the following straightforward lemma about independent sets: Lemma 23. Let G = (V, E) be a graph and let V ⊆ V . Then G has an independent set

S ⊆ V of size at least |V | degree(G)+1 .
Moreover, we can bound the degree of G H using the degree and arity of H: Lemma 24. Let H be a hypergraph. Then degree(G H ) (arity(H) × degree(H)) 2 -1. Proof sketch. The bound on the arity and degree of H implies a bound on the number of edges that can be at distance 4 of another edge in the incidence graph of H, hence bounding the degree of the exclusion graph.

We are now ready to conclude the proof of Lemma 21:

Proof of Lemma 21. Let ϕ be a monotone DNF, H = (V, E) its hypergraph, and v an enumeration of its variables. By definition of pathsplitwidth, there is v i ∈ V such that, for

E := Split i (v,

6

Lower Bounds on d-SDNNFs

In the previous section, we have shown that pathwidth measures how concisely an OBDD can represent a monotone DNF or CNF formula with bounded degree and arity. In this section, we move from OBDDs to (d-)SDNNFs, and show that treewidth plays a similar role to pathwidth in this setting. Formally, we show the following analogue of Theorem 15: Combined with Theorem 5 (or with existing results specific to CNF formulas such as [14, Corollary 1]), this yields an analogue of Corollary 16. However, its statement is less neat: unlike OBDDs, (d-)SDNNFs have no obvious notion of width, so the lower bound above refers to size rather than width, and it does not exactly match our upper bound. We obtain: Corollary 26. For any constant c, for any monotone DNF (resp., monotone CNF) ϕ with arity and degree bounded by c, there is a d-SDNNF for ϕ having size |ϕ| × 2 O(tw(ϕ)) , and any d-SDNNF (resp., SDNNF) for ϕ has size 2 Ω(tw(ϕ)) .

Our proof of Theorem 25 will follow the same overall structure as in the previous section. We present the proof for monotone DNFs and d-DNNFs: see the extended version [START_REF] Amarilli | Connecting width and structure in knowledge compilation (extended version)[END_REF] for the extension to monotone CNFs and SDNNFs. Recall that d-SDNNFs are structured by v-trees, which generalize variable orders. We first introduce treesplitwidth, a width notion that measures the performance of a v-tree by counting how many clauses it splits; and we connect treesplitwidth to treewidth. We use again dncpi-sets, and argue that a d-SDNNF structured by a v-tree must shatter a dncpi-set whose size follows the treesplitwidth of the v-tree. We then show that shattering a dncpi-set forces d-SDNNFs to be large: instead of the easy OBDD result of the previous section (Lemma 20), we will need a much deeper result of Pipatsrisawat and Darwiche [START_REF] Pipatsrisawat | A lower bound on the size of decomposable negation normal form[END_REF]Theorem 3], rephrased in the setting of communication complexity by Bova, Capelli, Mengel, and Slivovsky [START_REF] Bova | Knowledge compilation meets communication complexity[END_REF].

Note that [START_REF] Bova | Knowledge compilation meets communication complexity[END_REF], by a similar approach, shows an exponential lower bound on the size of d-SDNNF which is reminiscent of ours. However, their bound again applies to one well-chosen family of Boolean functions; our contribution is to show a general lower bound. In essence, our result is shown by observing that the family of functions used in their lower bound occurs "within" any bounded-degree, bounded-arity monotone DNF. Also note that a result similar to the lower bound of Corollary 26 is proven by Capelli [START_REF] Capelli | Structural restrictions of CNF-formulas: applications to model counting and knowledge compilation[END_REF]Corollary 6.35] as an auxiliary statement to separate structured DNNFs and FBDDs. The result uses MIM-width, but Theorem 4.2.5 of [START_REF] Vatshelle | New width parameters of graphs[END_REF], as degree and arity are bounded, implies that we could rephrase it to treewidth; further, the result assumes arity-2 formulas, but it could be extended to arbitrary arity as in [START_REF] Capelli | Understanding the complexity of #SAT using knowledge compilation[END_REF]Theorem 12]. More importantly, the result applies only to monotone CNFs and not to DNFs .

6:15

Result. Our bound in the previous section allows us to extend Theorem 8.7 of [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF] from OBDDs to d-SDNNFs, yielding the following: Theorem 33. There is a constant d ∈ N such that the following is true. Let σ be an arity-2 signature, and Q a connected UCQ = which is intricate on σ. For any instance I on σ, any d-SDNNF representing the lineage of Q on I has size 2 Ω(tw(I) 1/d ) .

Proof sketch. As in [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF], we use a result of Chekuri and Chuzhoy [START_REF] Chekuri | Polynomial bounds for the grid-minor theorem[END_REF] to show that the Gaifman graph of I has a degree-3 topological minor S of treewidth Ω(tw(I) 1/d ) for some constant d ∈ N; we also ensure that S has sufficiently high girth relative to Q. We focus on a subinstance I of I that corresponds to S: this suffices to show our lower bound, because we can always compute a tractable representation of ϕ(Q, I ) from one of ϕ(Q, I). Now, we can represent ϕ(Q, I ) as a minimized DNF ψ by enumerating its minimal matches: ψ has constant arity because the number of atoms of Q is fixed, and it has constant degree because S has constant degree and Q is connected. Further, as Q is intricate and I has high girth relative to Q, we can ensure that this DNF has treewidth Ω(tw(I )). We conclude by Theorem 25: d-SDNNFs representing ϕ(Q, I ), hence ϕ(Q, I), have size 2 Ω(tw(I) 1/d ) .

To summarize, given an instance family I satisfying the constructibility requirement of Theorem 8.1 of [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF], there are two regimes: (i.) I has bounded treewidth and then all MSO queries have d-SDNNF lineages on instances of I that are computable in linear time; or (ii.) the treewidth is unbounded and then there are UCQ = queries (the intricate ones) whose lineages on instances of I have no d-SDNNF representations polynomial in the instance size.

Conclusion

We have shown tight connections between structured circuit classes and width measures on circuits. We constructively rewrite bounded-treewidth circuits to d-SDNNFs in time linear in the circuit and singly exponential in the treewidth, and show matching lower bounds for arbitrary monotone CNFs or DNFs under degree and arity assumptions; we also show a lower bound for pathwidth and OBDDs. Our results have applications to rich query evaluation: probabilistic query evaluation, computation of lineages, enumeration, etc. Our work also raises a number of open questions. First, the d-SDNNF obtained in the proof of Theorem 5 does not respect the definition of a sentential decision diagram (SDD) [START_REF] Darwiche | SDD: A new canonical representation of propositional knowledge bases[END_REF]. Can this be fixed, and Theorem 5 extended to SDDs? Or is it impossible, which could solve the open question [START_REF] Bova | SDDs are exponentially more succinct than OBDDs[END_REF] of separating SDDs and d-SDNNFs? Second, can we weaken the hypotheses of bounded degree and arity in Corollaries 16 and 26, and can we rephrase the latter to a notion of (d-)SDNNF width to match more closely the statement of the former? Last, Section 7 shows that d-SDNNF representations of the lineages of intricate queries are exponential in the treewidth; we conjecture a similar result for pathwidth and OBDDs, but this would require a pathwidth analogue of the minor extraction results of [START_REF] Chekuri | Polynomial bounds for the grid-minor theorem[END_REF].

2 . 2 .

 22 for every internal bag b with children b l , b r we have b ⊆ b l ∪ b r ; 3. for every leaf bag b we have |b| 1; 4. for every non-root bag b with parent b , we have |b \ b | 1; 5. for the root bag b we have |b| 1. Lemma Given a tree decomposition T of width k having n nodes, we can compute in time O(k × n) a nice tree decomposition T of width k having O(k × n) nodes.

Corollary 7 .

 7 Given a Boolean circuit C and a tree decomposition T of width k of C, we can enumerate the accepting assignments of C with preprocessing in O |T | × 2 (4+ε)k and delay linear in the size of each produced assignment.

  For any bag b of T , we define VarT(b) to be the set of variable gates such that b is the topmost bag in which they appear; as T is nice, VarT(b) is either empty or is a singleton {g}, in which case we call b responsible for the variable gate g. We can explicitly compute the function VarT in O(|T |), i.e., compute VarT(b) for each b ∈ T ; see for instance [28, Lemma 3.1].

  still have to explain how we connect the gates G ν,S b of D to the gates G ν l ,S l b l and G νr,Sr br created for the children b l and b r of b in T . The first condition is that ν l and ν r must mutually agree, i.e., ν l (g) = ν r (g) for all g ∈ b l ∩ b r , and ν must then be the union of ν l and ν r , restricted to b. Remember that T is nice, so b is a subset of b l ∪ b r , and it is easy to verify that ν is then a (C, b)-almost-evaluation. We impose a second condition to prohibit suspicious gates from escaping before they have been justified, which we formalize as connectibility of a pair (ν, S) at bag b to the parent bag of b. Definition 11. Let b be a non-root bag, b its parent bag, and ν a (C, b)-almost-evaluation. For any set S ⊆ Unj(ν), we say that (ν, S) is connectible to b if S ⊆ b , i.e., the suspicious gates of ν must still appear in b . If a gate G ν,S b

  internal bag b of T , for each (C, b)-almost-evaluation ν and set S ⊆ Unj(ν) of suspicious gates of ν, we create one and-gate G ν,S b and one or-gate G ν,S b,children which is an input of G ν,S b . For every leaf bag b of T , we create one gate G ν,S b for every (C, b)-almost-evaluation ν, where we set S := Unj(ν); intuitively, in a leaf bag, an unjustified gate is always suspicious (it cannot have been justified at a descendant bag). Now, for each internal bag b of T with children b l , b r , for each pair of gates G ν l ,S l b l and G νr,Sr br that are both connectible to b and where ν l and ν r mutually agree, letting (ν, S) be the result of (ν l , S l ) and (ν r , S r ), we create a gate G ν l ,S l ,νr,Sr b = and(G ν l ,S l b l , G νr,Sr br ) and make it an input of G ν,S b,children . Last, for each bag b which is responsible for a variable gate g (i.e., VarT(b) = {g}), for each (C, b)-almost-evaluation ν and set of suspicious gates S ⊆ Unj(ν), we set the gate G g,ν(g) to be the second input of G ν,S b . The output gate of D is the gate G ν,∅

Theorem 15 .

 15 Let ϕ be a monotone DNF or monotone CNF, let a := arity(ϕ) and d := degree(ϕ). Then any OBDD for ϕ has width 2 pw(ϕ) a 3 ×d 2 .

Definition 19 ([ 1 ,

 191 Definition 6.4.6]). Given a monotone DNF ϕ on variables V , a disjoint non-covering prime implicant set (dncpi-set) of ϕ is a set S of clauses of ϕ which: are pairwise disjoint: for anyD 1 = D 2 in S, we have D 1 ∩ D 2 = ∅.are non-covering in the following sense: for any clause D of ϕ, if D ⊆ S, then D ∈ S. The size of S is the number of clauses that it contains.

by Lemma 24 .From

 24 Hence, S is a dncpi-set byLemma 22, has the desired size, and is shattered since S ⊆ E .Combining this result with Lemma 18 and Lemma 20 concludes the proof of Theorem 15. DNFs to CNFs. We now argue that Theorem 15 also holds for monotone CNFs. Let ϕ be a monotone CNF, a := arity(ϕ) and d := degree(ϕ), and suppose for a contradiction that there is an OBDD O for ϕ of width < 2 pw(ϕ) a 3 ×d 2 . Consider the monotone DNF ϕ built from ϕ by replacing each ∧ by a ∨ and each ∨ by a ∧. Now, let O be the OBDD built from O by replacing the label b ∈ {0, 1} of each edge by 1 -b, and replacing the label b of each leaf by 1 -b. It is clear, by De Morgan's laws, that O is an OBDD for ϕ of size < 2 pw(ϕ) a 3 ×d 2 , which contradicts Theorem 15 applied to monotone DNFs.

Theorem 25 .

 25 Let ϕ be a monotone DNF (resp., monotone CNF), let a := arity(ϕ) and d := degree(ϕ). Then any d-SDNNF (resp., SDNNF) for ϕ has size 2 tw(ϕ) 3×a 3 ×d 2 -1.

  H), we have |E | psw(H). Now, by Lemma 23, G H has an independent

	set S ⊆ E of size at least	|E | degree(G H )+1	which is	psw(H) (arity(H)×degree(H)) 2

Acknowledgments. We acknowledge Chandra Chekuri for his helpful comments at https: //cstheory.stackexchange.com/a/38943/, as well as Florent Capelli for pointing out the connection to [19, Corollary 6.35] and [40].

C D T 2 0 1 8 6:16 Connecting Width and Structure in Knowledge Compilation

Treesplitwidth. Informally, treesplitwidth is to v-trees what pathsplitwidth is to variable orders: it bounds the "best performance" of any v-tree. Definition 27. Let H = (V, E) be a hypergraph, and T be a v-tree over V . For any node n of T , we define Split n (T, H) as the set of hyperedges e of H that contain both a variable in T n and one outside T n (recall that T n denotes the subtree of T rooted at n). Formally: Split n (T, H) := {e ∈ E | ∃v i ∈ Leaves(T n ) and ∃v o ∈ Leaves(T \ T n ) such that {v i , v o } ⊆ e}.

The treesplitwidth of T relative to H is tsw(T, H) := max n∈T |Split n (T, H)|. The treesplitwidth tsw(H) of H is then the minimum of tsw(T, H) over all v-trees T of V .

Again, the treesplitwidth of H is exactly the branch-width [START_REF] Robertson | Graph minors. x. obstructions to tree-decomposition[END_REF] of the dual hypergraph of H, but treesplitwidth is more convenient for our proofs. As with pathsplitwidth and pathwidth (Lemma 18), we can bound the treewidth of a hypergraph by its treesplitwidth: Lemma 28. For any hypergraph H = (V, E), we have tw(H) 3 × arity(H) × tsw(H).

Proof sketch. We construct a tree decomposition from a v-tree T : it has same skeleton as T , its leaf bags contain the corresponding variable in the v-tree, and its internal bags contain the split at this v-tree node unioned with the split at the child nodes. This is indeed a tree decomposition because each non-singleton edge is split, and the nodes of the v-tree where a vertex of H occurs always form a connected subtree.

Moreover, using the same techniques that we used in the last section, we can show the analogue of Lemma 21. Specifically, given a monotone DNF ϕ on variables V , a v-tree T over V , and a dncpi-set S of ϕ, we say that T shatters S if there is a node n in T such that S ⊆ Split n (T, ϕ). We now show that any v-tree over V must shatter a large dncpi-set (depending on the treewidth, degree, and arity): Lemma 29. Let ϕ be a monotone DNF, H its hypergraph, and T be a v-tree over its variables. Then there is a dncpi-set S of ϕ shattered by T such that |S| Hence, to prove Theorem 25, the only missing ingredient is a lower bound on the size of d-SDNNFs that shatter large dncpi-sets. Specifically, we need an analogue of Lemma 20: Lemma 30. Let ϕ be a monotone DNF on variables V and n ∈ N. Assume that, for every v-tree T over V , there is some dncpi-set S of ϕ with |S| n, such that T shatters S. Then any d-SDNNF for ϕ has size 2 n -1.

We will prove Lemma 30 in the rest of this section using a recent lower bound by Bova, Capelli, Mengel, and Slivovsky [START_REF] Bova | Knowledge compilation meets communication complexity[END_REF]. They bound the size of any d-SDNNF for the set intersection function, defined as SINT n := (x 1 ∧ y 1 ) ∨ . . . ∨ (x n ∧ y n ). This bound is useful for us: a dncpi-set intuitively isolates some variables on which ϕ computes exactly SINT n : Lemma 31. Let ϕ be a DNF with variables V , and let S = {D 1 , . . . , D n } be a dncpi-set of ϕ where every clause has size 2. Pick two variables

Proof sketch. The valuation ν sets to 1 the variables V which are in S but not in V , and sets to 0 all remaining variables. This amounts to discarding the clauses not in the dncpi-set, and discarding the variables of V in the dncpi-set: what remains of the DNF is then precisely SINT n . Note that this result relies on monotonicity, and on the fact that ϕ is a DNF. (However, in the full version [START_REF] Amarilli | Connecting width and structure in knowledge compilation (extended version)[END_REF], we show a dual result for monotone CNF.)

This observation allows us to leverage the bound of [START_REF] Bova | Knowledge compilation meets communication complexity[END_REF] on the size of d-SDNNFs that compute SINT n , assuming that they are structured by an "inconvenient" v-tree:

6:14

Connecting Width and Structure in Knowledge Compilation Proposition 32 [START_REF] Bova | Knowledge compilation meets communication complexity[END_REF]Proposition 14]). Let X n = {x 1 , . . . , x n } and Y n = {y 1 , . . . , y n } for n ∈ N, and let T be a v-tree over X n Y n such that there exists a node n ∈ T with X n ⊆ Leaves(T n ) and Y n ⊆ Leaves(T \ T n ). Then any d-SDNNF structured by T computing SINT n has size 2 n -1.

In our setting, an "inconvenient" v-tree for a dncpi-set is one that shatters it: each clause of the dncpi-set is then partitioned in two non-empty subsets where we can pick x i and y i for Lemma 31. Hence, when every v-tree shatters a large dncpi-set of ϕ, Proposition 32 allows us to deduce the lower bound on the size of every d-SDNNF for ϕ. We have thus shown Lemma 30, and this concludes the proof of Theorem 25 (in the DNF case).

Application to Query Lineages

In this section, we adapt the lower bound of the previous section to the computation of query lineages on relational instances. Like in [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF], for technical reasons, we must assume a graph signature. We first recall some preliminaries and then state our result.

Preliminaries. We fix a graph signature σ of relation names and arities in {1, 2}, with at least one relation of arity 2. An instance I on σ is a finite set of facts of the form R(a 1 , . . . , a n ) for n the arity of R; we call a 1 , . . . , a n elements of I. An instance I is a subinstance of I if the facts of I are a subset of those of I. The Gaifman graph of I has the elements of I as vertices and has one edge between each pair of elements that co-occur in some fact of I. The treewidth tw(I) of I is that of its Gaifman graph.

A Boolean conjunctive query (CQ) is an existentially quantified conjunction of atoms of the form R(x 1 , . . . , x n ) where the x i are variables. A UCQ is a disjunction of CQs, and a UCQ = also allows atoms of the form x = y. A UCQ = is connected if the Gaifman graph of each disjunct (seen as an instance, and ignoring =-atoms) is connected. For instance, letting σ R consist of one arity-2 relation R, the following connected UCQ = tests if there are two facts that share one element: Q p : ∃xyz (R(x, y) ∨ R(y, x))) ∧ (R(y, z) ∨ R(z, y)) ∧ x = z. (While Q p is not given as a disjunction of CQs, it can be rewritten to one using distributivity.)

The lineage of a UCQ = Q over I is a Boolean formula ϕ(Q, I) on the facts of I that maps each Boolean valuation ν : I → {0, 1} to 1 or 0 depending on whether I ν satisfies Q or not, where I ν := {F ∈ I | ν(F ) = 1}. The lineage intuitively represents which facts of I suffice to satisfy Q. Lineages are useful to evaluate queries on probabilistic databases [START_REF] Suciu | Probabilistic Databases[END_REF]: we can obtain the probability of the query from an OBDD or d-DNNF representing its lineage.

Problem statement. We study when query lineages can be computed efficiently in data complexity, i.e., as a function of the input instance, with the query being fixed. A first question asks which queries have tractable lineages on all instances: Jha and Suciu [START_REF] Kumar | On the tractability of query compilation and bounded treewidth[END_REF]Theorem 3.9] showed that inversion-free UCQ = queries admit OBDD representations in this sense, and Bova and Szeider [16, Theorem 5] have recently shown that UCQ = queries with inversions do not even have tractable d-SDNNF lineages. A second question asks which instance classes ensure that all queries have tractable lineages on them. This was studied for OBDD representations in [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF]: bounded-treewidth instances have tractable OBDD lineage representations for any MSO query ([7, Theorem 6.5], using [START_REF] Kumar | On the tractability of query compilation and bounded treewidth[END_REF]); conversely there are intricate queries (a class of connected UCQ = queries) whose lineages never have tractable OBDD representations in the instance treewidth [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF]Theorem 8.7]. The query Q p above is an example of an intricate query on the signature σ R (refer to [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF]Definition 8.5] for the formal definition of intricate queries). This result shows that we must bound instance treewidth for all queries to have tractable OBDDs, but leaves the question open for more expressive lineage representations.