Mikaël Monet
email: mikael.monet@imfd.cl

Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases

Keywords: Tuple-independent databases, knowledge compilation, deterministic decomposable Boolean circuits, inclusion-exclusion principle

We consider the problem of exact probabilistic inference for Union of Conjunctive Queries (UCQs) on tuple-independent databases. For this problem, two approaches currently coexist. In the extensional method, query evaluation is performed by exploiting the structure of the query, and relies heavily on the use of the inclusionexclusion principle. In the intensional method, one first builds a representation of the lineage of the query in a tractable formalism of knowledge compilation. The chosen formalism should then ensure that the probability can be efficiently computed using simple disjointness and independence assumptions, without the need of performing inclusion-exclusion. The extensional approach has long been thought to be strictly more powerful than the intensional approach, the reason being that for some queries, the use of inclusion-exclusion seemed unavoidable. In this paper we introduce a new technique to construct lineage representations as deterministic decomposable circuits in polynomial time. We prove that this technique applies to a class of UCQs that had been conjectured to separate the complexity of the two approaches. In essence, we show that relying on the inclusion-exclusion formula can be avoided by using negation. This result brings back hope to prove that the intensional approach can handle all tractable UCQs.

INTRODUCTION

Probabilistic databases [START_REF] Suciu | Probabilistic Databases[END_REF] have been introduced in answer to the need to capture data uncertainty and reason about it. In their simplest and most common form, probabilistic databases consist of a relational database in which each tuple is annotated with an independent probability value. This value is supposed to represent how confident we are about having the tuple in the database. This is known as the tuple-independent database (TID) model [START_REF] Fuhr | A probabilistic relational algebra for the integration of information retrieval and database systems[END_REF][START_REF] Zimányi | Query evaluation in probabilistic relational databases[END_REF]. While a traditional database can only satisfy or violate a Boolean query, a probabilistic database has a certain probability of satisfying it. Given a Boolean query Q, the probabilistic query evaluation problem for Q (PQE(Q)) then asks for the probability that the query holds on an input probabilistic database. Here, the complexity of PQE(Q) is measured as a function of the input database, hence considering that the Boolean query Q is fixed. This is known as data complexity [START_REF] Vardi | The complexity of relational query languages[END_REF], and is motivated by the fact that the queries are usually much smaller than the data.

When Q is a union of conjunctive queries, a dichotomy result is provided by the seminal work of Dalvi and Suciu [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF]: either Q is safe and PQE(Q) is in polynomial time (PTIME), or Q is not safe and PQE(Q) is #P-hard. The algorithm to compute the probability of a safe UCQ exploits the first-order structure of the query to find a so called safe extensional query plan, using extended relational operators that can manipulate probabilities. An unusual feature of this algorithm is the use of the inclusion-exclusion principle (more precisely, of the Möbius inversion formula), which allows for distinct hard sub-queries to cancel each other. This approach is referred to as extensional query evaluation, or lifted inference [START_REF] Gribkoff | Lifted probabilistic inference: a guide for the database researcher[END_REF][START_REF] Poole | First-order probabilistic inference[END_REF].

A second approach to PQE for safe UCQs is intensional query evaluation or grounded inference, and consists of two steps. First, compute a representation of the lineage [START_REF] Todd | Models for incomplete and probabilistic information[END_REF] (also called provenance) of the query Q on the database D, which is a Boolean function intuitively representing which tuples of D suffice to satisfy Q. Second, perform weighted model counting on the lineage to obtain the probability. This is, for instance, the approach taken by the recent probabilistic database management system ProvSQL [START_REF] Senellart | ProvSQL: Provenance and probability management in PostgreSQL[END_REF]. To ensure that model counting is tractable, we use the structure of the query to represent the lineage in tractable formalisms from the field of knowledge compilation. This includes read-once Boolean formulas [START_REF] Alexander | Repetition-free Boolean functions[END_REF], free or ordered binary decision diagrams (FBDDs [START_REF] Sheldon | Binary decision diagrams[END_REF], OBDDs [START_REF] Bryant | Graph-based algorithms for Boolean function manipulation[END_REF][START_REF] Wegener | BDDs-design, analysis, complexity, and applications[END_REF]), deterministic decomposable normal forms (d-DNNFs [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF]), decision decomposable normal forms (dec-DNNFs [START_REF] Huang | DPLL with a trace: From SAT to knowledge compilation[END_REF][START_REF] Huang | The language of search[END_REF]), decomposable logic decision diagrams (DLDDs [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF]), deterministic decomposable circuits (d-Ds [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF][START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF][START_REF] Suciu | Probabilistic Databases[END_REF] 1 ), structured versions thereof [START_REF] Pipatsrisawat | New compilation languages based on structured decomposability[END_REF], etc. These can all be seen as restricted classes of Boolean circuits, that by definition allow for efficient (in fact, linear) probability computation: the ∧-gates are decomposable (their inputs depend on disjoint sets of variables, hence represent independent probabilistic events) and the ∨-gates are deterministic (their inputs represent disjoint probabilistic events). There are many advantages of this approach compared to lifted inference. First, and this is also true for non-probabilistic evaluation, the lineage can help explain the query answer [START_REF] Buneman | Why and where: a characterization of data provenance[END_REF]. Second, having the lineage in a good knowledge compilation formalism can be useful for various other applications: we could for instance update the tuples' probabilities and compute the new result easily, or compute the most probable state of the data that satisfies the query [START_REF] Darwiche | Modeling and reasoning with Bayesian networks[END_REF][START_REF] Sharma | Knowledge compilation meets uniform sampling[END_REF], or enumerate satisfying states with constant delay [START_REF] Amarilli | A circuitbased approach to efficient enumeration[END_REF], or produce random samples of satisfying states [START_REF] Sharma | Knowledge compilation meets uniform sampling[END_REF], etc. This ability to reuse the lineage for multiple tasks is precisely one of the main motivations of the field of knowledge compilation.

A natural question is then to ask if the intensional approach is as powerful as the extensional one. To answer it, a whole line of research started, whose goal is to determine exactly which queries can be handled by which formalisms of knowledge compilation. It is known, for example, that the UCQs whose lineages have polynomial-sized read-once formulas representations are exactly the hierarchical-read-once UCQs [START_REF] Jha | Knowledge compilation meets database theory: compiling queries to decision diagrams[END_REF][START_REF] Olteanu | Using OBDDs for efficient query evaluation on probabilistic databases[END_REF], and that those having polynomial-sized OBDDs are exactly the inversion-free UCQs [START_REF] Jha | Knowledge compilation meets database theory: compiling queries to decision diagrams[END_REF]. (This later result on OBDDs was extended to UCQs with disequalities atoms [START_REF] Jha | On the tractability of query compilation and bounded treewidth[END_REF] and to self-join-free CQs with negations [START_REF] Fink | Dichotomies for queries with negation in probabilistic databases[END_REF].) However, as far as we know, the characterization is open for all the other formalisms of knowledge compilation. What we call the intensional-extensional conjecture, formulated in [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF][START_REF] Jha | Knowledge compilation meets database theory: compiling queries to decision diagrams[END_REF][START_REF] Suciu | Probabilistic Databases[END_REF], states that, for safe queries, extensional query evaluation is strictly more powerful than the knowledge compilation approach. Or, in other words, that there exists a UCQ which is safe (i.e., that can be handled by the extensional approach) whose lineages on arbitrary databases cannot be computed in PTIME in a tractable knowledge compilation formalism (i.e., cannot be handled by the intensional approach). As we have already mentioned, the conjecture depends on which tractable formalism we consider. However, generally speaking, the idea would be that knowledge compilation formalisms cannot simulate efficiently the Möbius inversion formula used in the algorithm for safe queries.

The conjecture has recently been shown in [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF] to hold for the formalism of DLDDs (including OBDDs, FBDDs and dec-DNNFs), which captures the execution of modern model counting algorithms by restricting the power of determinism. Another independent result [START_REF] Bova | Circuit treewidth, sentential decision, and query compilation[END_REF] shows that the conjecture also holds when we consider the class of structured d-DNNFs (d-SDNNFs, also including OBDDs), which are d-DNNFs that follow the structure of a v-tree [START_REF] Pipatsrisawat | New compilation languages based on structured decomposability[END_REF]. However the question is still widely open for the most expressive formalisms, namely, d-DNNFs and d-Ds. Indeed, it could be the case that the conjecture does not hold for such expressive formalisms, which would imply that we could explain the tractability of all safe UCQs via knowledge compilation, and thus enjoy all of its advantages.

In this paper we focus on a class of Boolean queries that have been intensively studied already [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF][START_REF] Bova | Circuit treewidth, sentential decision, and query compilation[END_REF][START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF][START_REF] Jha | Knowledge compilation meets database theory: compiling queries to decision diagrams[END_REF][START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF][START_REF] Suciu | Probabilistic Databases[END_REF], and that we name here the H -queries. An H -query can be defined as a Boolean combination of very simple CQs. To ease notation, we can always denote an H -query as Q φ , where φ is a Boolean function whose variables correspond to simple CQs (see Section 3.1 for the exact definition). Hence, when the Boolean function φ is monotone, Q φ is a UCQ, and we write H + the set of H -queries that are UCQs. The safe H + -queries were conjectured in [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF][START_REF] Jha | Knowledge compilation meets database theory: compiling queries to decision diagrams[END_REF][START_REF] Suciu | Probabilistic Databases[END_REF] to not have tractable lineage representations in any good knowledge compilation formalism. In fact, the H + -queries are precisely the ones that were used to prove the intensional-extensional conjecture for both DLDDs [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF] and d-SDNNFs [START_REF] Bova | Circuit treewidth, sentential decision, and query compilation[END_REF], leaving little hope for the remaining formalisms. In a sense, these queries are the simplest UCQs that illustrate the need of the Möbius inversion formula in Dalvi and Suciu's algorithm. Hence, they are also the first serious obstacle to disproving the conjecture for the most expressive formalisms of knowledge compilation.

Contributions, short version. Building on preliminary investigations [START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF], we develop a new technique to construct d-Ds in polynomial time for some of the H -queries, and we prove that our technique applies to all the safe H + -queries. What is more, we also show that this technique applies to some H -queries that are not UCQs (i.e., in H \ H + ), and we show #P-hardness for a subset of those for which it does not work. A picture of the situation can be found in Figure 1. Not illustrated in Figure 1, we also provide a detailed analysis of when lineages for an H -query Q φ can be transformed into lineages for another H -query Q φ ′ , with only a polynomial increase in size.

Contributions, long version. We now explain these results and our methodology more exhaustively. The dichotomy theorem of Dalvi and Suciu implies that an H + -query Q φ is safe if and only if the Möbius value of the CNF lattice of φ is zero (and for Q φ ∈ H \ H + we do not know, because these are not UCQs).

Our starting point is to reformulate that criterion by showing that this value is equal to the Euler characteristic of φ. This connection seems to have been unnoticed so far in the probabilistic database literature. Hence, we obtain that Q φ ∈ H + is safe if and only if the Euler characteristic of φ is zero. While it is not clear how to define the CNF lattice for the H -queries that are not UCQs, one advantage of our characterization is that the Euler characteristic is defined for any Boolean function φ.

We then use this new characterization to show that all H -queries Q φ for which φ has zero Euler characteristic have d-D representation of their lineages constructible in polynomial time. This can be considered as the main result of this article. Its proof contains three ingredients:

• The first one is a result on constructing OBDDs for restricted fragments of UCQs with negations [START_REF] Fink | Dichotomies for queries with negation in probabilistic databases[END_REF], that we use as a black box (but we explain the relevant parts in Appendix, for completeness).

• The second one is a notion of what we call a fragmentable

Boolean function, intuitively designed to ensure that Q φ has d-Ds constructible in PTIME whenever φ is fragmentable, and that relies on the result of [START_REF] Fink | Dichotomies for queries with negation in probabilistic databases[END_REF].

• The third component is a certain transformation between

Boolean functions, where φ can be transformed into φ ′ by iteratively (1) removing from φ two connected (i.e., that differ in only one variable) satisfying valuations; or (2) adding to φ two connected valuations that did not satisfy φ.

This transformation defines an equivalence relation ≃ between all

Boolean functions, and we can show that if φ ≃ ⊥ (the Boolean function that is always false), then φ is fragmentable. We then show that when φ has zero Euler characteristic it is equivalent to ⊥, thus completing the proof. We also justify the definition of our transformation by showing that using only (1) or only (2) is not enough.

Our next main result is to show that if φ and φ ′ have the same Euler characteristic, then (a) PQE(Q φ ) and PQE(Q φ ′ ) are reducible to each other (under PTIME Turing reductions); (b) we can compute in polynomial time d-D representations of the lineage of Q φ on arbitrary databases iff we can do the same for Q φ ′ ; and (c) the lineages of Q φ can be represented as d-Ds of polynomial size iff those of Q φ ′ can. To show these equivalences, we prove that the equivalences classes of ≃ correspond exactly to the different values of the Euler characteristic. We think that this last combinatorial result can be of independent interest. We then obtain the equivalences (a-b-c) by observing that our transformation always preserves the corresponding properties. As a bonus, the first equivalence (a) also allows us all H -queries. Interior black horizontal rectangle: all H +queries (UCQs). Solid green rectangle: all safe H + -queries according to the dichotomy of [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF], i.e., whose CNF lattice have zero Möbius value. Solid red rectangle: all unsafe H + -queries. Blue vertical rectangle: all the H -queries having OBDDs constructible in PTIME (upper bound [START_REF] Fink | Dichotomies for queries with negation in probabilistic databases[END_REF], lower bound [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF]). These are the inversion-free H -queries and correspond to what we call degenerate Boolean functions. Dashed green rectangle (left): all the H -queries to which our technique can apply, implying that they have d-Ds constructible in PTIME. These correspond to fragmentable Boolean functions, or equivalently, to those having zero Euler characteristic. Dashed red rectangle (right): the H -queries corresponding to Boolean functions having non-zero Euler characteristic and for which we could show #P-hardness. Dotted gray rectangle: all the remaining Hqueries corresponding to Boolean functions having nonzero Euler characteristic. We conjecture these to be #P-hard as well. Note that each individual region contains an infinite number of queries.

to show #P-hardness of some H -queries that are not UCQs, thus slightly extending the dichotomy of [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] for the H -queries.

The difference with [START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF]. In [START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF], we studied with Dan Olteanu the compilation of the H -queries into d-DNNFs. This preliminary work already contains the idea of covering the satisfying valuations of φ by removing two adjacent satisfying valuations, through the notion of what we called a nice Boolean function (of which fragmentability is a generalization). This article contained an experimental study that the proposed approach might work for the safe H + -queries, but had no proof. We still do not know if this approach works for all safe H + -queries, but we do know that it cannot work for all H -queries with zero Euler characteristic (more on that in Section 7). What was missing to get to a proof for the H -queries is the reformulation with the Euler characteristic (which allows one to understand the combinatorial meaning of having a zero Möbius value of the CNF lattice), and the fact that we might also need to add adjacent non-satisfying valuations.

Paper structure. To help the reader, we have depicted the structure of the paper and of the proofs as a DAG in Appendix D. We start in Section 2 with short preliminaries. In Section 3 we define the H -queries, review what is known about them and reformulate the safety criterion for the H + -queries in terms of the Euler characteristic. We continue in Section 4 by introducing our notion of fragmentable Boolean function and we prove that if φ is fragmentable then Q φ has d-Ds. In Section 5 we present our transformation and prove that if φ has zero Euler characteristic then φ is fragmentable, which implies our main result. We analyze in Section 6 what happens in the case of a non-zero Euler characteristic. Last, we expose in Section 7 open questions, justify the definition of our transformation, and discuss the applicability of our technique to a broader class of queries than the H -queries. We conclude in Section 8.

PRELIMINARIES

Boolean functions. A (Boolean) valuation of a set V is a subset of V . We write 2 V the set of all valuations of V . For a Boolean valuation ν and variable l of V , we write l ) is ν except that the membership of l has been flipped. A Boolean function φ on V is a mapping φ : 2 V → {False, True} that associates to each valuation ν a value φ(ν ) in {False, True}.

ν (l ) def = ν ∪ {l } if l ν ν \ {l } if l ∈ ν , i.e., ν (
A valuation ν is satisfying when φ(ν ) = True, also written ν |= φ.

We write SAT(φ) the set of satisfying valuations of φ, and #φ the number of satisfying valuations of φ. We write ⊥ (resp., ⊤) the Boolean function that maps every valuation to False (resp., True).

A Boolean function φ is monotone if φ(ν ) =⇒ φ(ν ′ ) for every valuations ν, ν ′ such that ν ⊆ ν ′ . A monotone Boolean function can always be represented as a DNF of the form C 0 ∨ . . . ∨ C n , where we see each clause simply as the set of variables that it contains. Moreover, there is a unique minimized DNF representing φ, where no clause is a subset of another; we denote it by φ DNF . We will similarly consider the unique minimized CNF representation φ CNF of a monotone Boolean function φ. 2 Two Boolean functions φ, φ ′ are disjoint when φ ∧ φ ′ = ⊥, or in other words, when SAT(φ ∧ φ ′ ) = ∅.

Definition 2.1. Let φ be a Boolean function on V . We say that φ depends on variable l ∈ V when there exists a valuation ν ⊆ V such that φ(ν) φ(ν (l ) ). We write DEP(φ) ⊆ V for the set of variables on which φ depends. We call φ nondegenerate if DEP(φ) = V , and degenerate otherwise. Definition 2.2 (See [START_REF] Hammersholt | Complexity and algorithms for Euler characteristic of simplicial complexes[END_REF]35]). Let φ be a Boolean function. The Euler characteristic of φ, denoted e(φ), is ν |=φ (-1) |ν | .

Tuple-independent databases. A tuple-independent (TID) database is a pair (D, π ) consisting of a relational instance D and a function π mapping each tuple t ∈ D to a rational probability π (t) ∈ [0; 1]. A TID instance (D, π ) defines a probability distribution Pr on D ′ ⊆ D, where Pr(D ′ )

def = t ∈D ′ π (t) × t ∈D\D ′ (1 -π (t)
). Given a Boolean query Q, the probabilistic query evaluation problem for Q (PQE(Q)) asks, given as input a TID instance (D, π ), the probability that Q is satisfied in the distribution Pr. That is, formally, Pr(Q, (D, π ))

def = D ′ ⊆D s.t. D ′ |=Q Pr(D ′ ).
Dalvi and Suciu [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] have shown a dichotomy result on UCQs for PQE: either Q is safe and PQE(Q) is PTIME, or Q is not safe and PQE(Q) is #P-hard. Due to space constraints, we must refer to [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] for a presentation of their algorithm to compute the probability of a safe query, though it is not necessary to understand the current paper: we will reproduce the relevant parts in the next section. We write for the formal definition). This connection was first observed in [START_REF] Todd | Models for incomplete and probabilistic information[END_REF].

PQE(Q) ⩽ T PQE(Q ′ ) when PQE(Q) reduces in PTIME (under Tur- ing reductions) to PQE(Q ′ ). We write PQE(Q) ≡ T PQE(Q ′ ) when we have both PQE(Q) ⩽ T PQE(Q ′ ) and PQE(Q ′ ) ⩽ T PQE(Q).
Knowledge compilation formalisms. The lineage, being a Boolean function, can be represented with any formalism that represents Boolean functions (Boolean formulas, BDDs, Boolean circuits, etc). In the intensional query evaluation context, the crucial idea is to use a formalism that allows tractable probability computation. In this work we will specifically focus on deterministic decomposable circuits (d-Ds) and deterministic decomposable normal forms [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF] (d-DNNFs). Let C be a Boolean circuit (featuring ∧, ∨, ¬, and variable gates). An ∧-gate д of C is decomposable if for every two input gates д 1 д 2 of д we have Vars(д 1 )∩Vars(д 2 ) = ∅, where Vars(д) denotes the set of variable gates that have a directed path to д in C. We call C decomposable if each ∧-gate is. An ∨-gate д of C is deterministic if for every pair д 1 д 2 of input gates of д, the Boolean functions captured by д 1 and д 2 are disjoint. We call C deterministic if each ∨-gate is. A negation normal form (NNF) is a circuit in which the inputs of ¬-gates are always variable gates. Probability computation is in linear time for d-Ds (hence, for d-DNNFs): to compute the probability of a d-D, compute by a bottom-up pass the probability of each gate, where ∧ gates are evaluated using ×, ∨ gates using +, and ¬ gates using 1 -x.

For a formalism C of representation of Boolean functions, we denote by C(PTIME) the class of all Boolean queries Q such that, given as input an arbitrary database D, we can compute in polynomial time (in data complexity) an element of C representing Lin(Q, D). Similarly, we write C(PSIZE) for the class of Boolean queries Q such that, for any database D, there exists an element of C representing Lin(Q, D) whose size is polynomial in that of D (but this element is not necessarily computable in PTIME).

The Möbius function. The characterization of the safe H +queries by [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] uses the Möbius function of a poset, which we define here. Let P = (A, ⩽) be a finite poset. The Möbius function [35]

µ P : A × A → Z of P is defined on pairs (u, v) with u ⩽ v by µ P (u, u) def = 1 and µ P (u, v) def = - u <w ⩽v µ P (w, v) for u < v.
It is used to express the Möbius inversion formula, which is a generalization for posets of the inclusion-exclusion principle (see Proposition A.1 in Appendix A.2).

THE H -QUERIES

In this section we define the H -queries and review what is known about them, before reformulating the safety criterion for H + -queries.

Reviewing what is known

The building blocks of these queries are the conjunctive queries h k,i , which were first defined in the work of Dalvi and Suciu [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] to show the hardness of UCQs that are not safe: Definition 3.1. Let k ∈ N ⩾1 , and let R, S 1 , . . . , S k ,T be pairwise distinct relational predicates, with R and T being unary, and S i for 0 ⩽ i ⩽ k being binary. The queries h k,i for 0 ⩽ i ⩽ k are defined by:

• h k,0 = ∃x∃y R(x) ∧ S 1 (x, y); • h k,i = ∃x∃y S i (x, y) ∧ S i+1 (x, y) for 1 ⩽ i < k; • h k,k = ∃x∃y S k (x, y) ∧ T (y).
As in [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF], we define the H k -queries to be Boolean combinations of the queries h k,i : Definition 3.2. Let k ∈ N ⩾1 and φ be a Boolean function on variables V = {0, . . . , k }. We define the query Q φ to be the query represented by the first order formula φ

[0 → h k,0 , . . . , k → h k,k ],
i.e., φ where we substituted each variable i ∈ V by the formula h k,i .

The query class H k (resp., H + k ) is then the set of queries Q φ when φ ranges over all Boolean functions (resp., monotone Boolean functions) on variables {0, . . . , k}. We finally define H (resp.,

H + ) to be ∞ k =1 H k (resp., ∞ k =1 H + k ).
Observe that the queries in H + are in particular (equivalent to some) UCQs.

Example 3.3. Let k = 3, and φ 9 be the monotone Boolean function

(2 ∨ 3) ∧ (0 ∨ 3) ∧ (1 ∨ 3) ∧ (0 ∨ 1 ∨ 2). Then Q φ 9 represents the query (h 32 ∨h 33 ) ∧ (h 30 ∨h 33 ) ∧ (h 31 ∨h 33 ) ∧ (h 30 ∨h 31 ∨h 32 ) ∈ H +
3 . This query was introduced in [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF], where it is called q 9 . It is the simplest safe H + -query for which Dalvi and Suciu's algorithm requires the Möbius inversion formula.

At this point, it is important to warn the reader not to confuse the function φ, whose purpose is to define Q φ , and the lineage of Q φ on a database. While they are both Boolean functions, the similarity stops here: we use φ simply to alleviate the notations. Also, from now on and until the end, we fix k ∈ N ⩾1 and V = {0, . . . , k}, and we will never use the symbols k and V for anything else.

To study the H k -queries, let us first listen to what the dichotomy of [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] has to say about them. We shall temporarily restrict our attention to monotone functions, i.e., to queries in H + k , because the dichotomy theorem applies only to UCQs. We need to define the CNF lattice of φ: Definition 3.4. Let φ be a monotone Boolean function represented by its (unique) minimized CNF φ CNF = C 0 ∧. . .∧C n (remember that we see each clause simply as the set of variables that it contains).

For s ⊆ {0, . . . , n}, we define

d s def = i ∈s C i . Note that d ∅ is ∅, and that it is possible to have d s = d s ′ for s s ′ . We define the poset L φ CNF = (A, ⩽), where A is {d s | s ⊆ {0, . . . , n}},
and where ⩽ is reversed set inclusion 3 . One can check that L φ CNF is a (finite) lattice, but this fact is not important for this paper. In particular, L φ CNF has a greatest element 1, which is ∅, and has a least element 0, which is DEP(φ).

The dichotomy theorem then tells us the following: Proposition 3.5 ( [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF], see also [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF]Section 3.3]). Let φ be monotone. If φ is degenerate then PQE(Q φ ) is PTIME. If φ is nondegenerate, let L φ CNF be the CNF lattice of φ, and µ CNF be the Möbius function on

L φ CNF . Then, if µ CNF ( 0, 1) = 0 then PQE(Q φ ) is PTIME, otherwise it is #P-hard.
Example 3.6. Consider φ 9 from Example 3.3. Clearly φ 9 is nondegenerate. The Hasse diagram of its CNF lattice is shown in Figure 2, with the value µ CNF (n, 1) for each node n. We have

µ CNF ( 0, 1) = µ CNF ({0, 1, 2, 3}, ∅) = 0, hence PQE(Q φ 9 ) is PTIME.
The solid green and red rectangles in Figure 1 represent the tractable and #P-hard H + -queries.

Having reviewed the tractability of the H + -queries, we now do the same concerning the compilation of H -queries to knowledge compilation formalisms. First, when φ is degenerate, then

Q φ ∈ OBDD(PTIME) (hence Q φ ∈ d-D(PTIME)):
Proposition 3.7 (Implied by Lemma 3.8 of [START_REF] Fink | Dichotomies for queries with negation in probabilistic databases[END_REF]). If φ (not necessarily monotone) is degenerate, then Q φ ∈ OBDD(PTIME).

In this work we will only need the fact that Q φ ∈ d-D(PTIME) when φ is degenerate. Since our results depend on Proposition 3.7 and in order to be self-contained, we reproduce its proof in Appendix A.1, but it can be safely skipped: the reader can see it as a black box.

Proposition 3.7 is in sharp contrast to when φ is nondegenerate. Indeed in that case the authors of [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF] show an exponential lower bound on the size of what they call Decomposable Logic Decision Diagrams (DLDDs) for Q φ . A DLDD is a d-D in which the determinism of ∨-gates is restricted to simply choosing the value of a variable. That is, each ∨-gate is of the form (v ∧ д) ∨ (¬v ∧ д ′ ) for some variable v. An OBDD being in particular a DLDD, we have represented in Figure 1 all the H -queries in OBDD(PTIME) by the vertical blue rectangle (and we even know that those outside this rectangle are not even in OBDD(PSIZE), thanks to this lower bound).

When φ is monotone and nondegenerate, another independent exponential lower bound [START_REF] Bova | Circuit treewidth, sentential decision, and query compilation[END_REF] tells us than we cannot impose structuredness either (i.e., use d-SDNNFs). These two lower bounds mean that to build tractable lineages for the H -queries, one cannot restrict the expressivity of determinism too much, nor restrict the structure in which the variables appear. One question is then: do the safe nondegenerate H + -queries have polynomial sized (and computable in PTIME?) d-DNNFs (or d-Ds)?

Reformulation of safety for the H + -queries

With this section starts the presentation of our technical contributions. Here, we reformulate the safety criterion of [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] in terms of the Euler characteristic (recall Definition 2.2). As a by-product, we also show that for the H + -queries, using the CNF lattice or the DNF lattice 4 is equivalent (that question was left open in [START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF]). We show the following (remember that k ∈ N ⩾1 and V = {0, . . . , k} are fixed):

∅ {0, 1, 2} {0, 3} {0, 1, 3} {1, 3} {0, 2, 3} {2, 3} {1, 2, 3} {0, 1, 2, 3} 1 -1 -1 1 -1 -1 1 1 0 Figure 2: Hasse diagram of L φ 9
CNF . The green value besides each node n is µ CNF (n, ∅), and can be computed top-down following the definition. Proof sketch. The idea is to use Möbius's inversion formula on the CNF and DNF lattices to obtain three different expressions of a variant of the characteristic polynomial of φ [START_REF] Nisan | On the degree of Boolean functions as real polynomials[END_REF], and then to observe that the leading coefficients are equal to the targeted terms. The full proof can be found in Appendix A.2. □

A result that looks very similar to Lemma 3.8 is Philip Hall's theorem (see [35,Proposition 3.8.6] and text above), relating the Möbius value µ P ( 0, 1) of a poset P with the Euler characteristic of a certain abstract simplicial complex5 defined from P. However, we did not see a direct relation between this result and our lemma.

Combining Lemma 3.8 with Proposition 3.5, and with the observation that any degenerate function φ has e(φ) = 0, we obtain the following simple characterization of the safe H + -queries: Corollary 3.9. Let φ be monotone. If e(φ) = 0 then PQE(Q φ ) is PTIME, otherwise it is #P-hard.

Using the Euler characteristic instead of the Möbius function to characterize the safe H + -queries has two advantages. First, e(φ) is conceptually much simpler to grasp than µ CNF ( 0, 1). 6 The second one is that e(φ) is always defined, whereas it is not entirely clear how to define the CNF lattice when φ is not monotone.

While the proof of Lemma 3.8 is not very challenging, the connection does not seem to have been made in the literature so far.

FRAGMENTABLE BOOLEAN FUNCTIONS

We now introduce our notion of fragmentable Boolean function and show that whenever φ is fragmentable, then Q φ ∈ d-D(PTIME). We also show that if e(φ) 0 then φ cannot be fragmentable.

Definition

We first need to define what we call an ¬-∨-template. Definition 4.1. An ¬-∨-template is a Boolean circuit whose internal nodes (i.e., those that are not a leaf) are either ¬or ∨gates. We call holes the variables (i.e., the leaves) of T . Let l 0 , . . . , l n be the holes of T , and let φ 0 , . . . , φ n be Boolean functions. Then T [φ 0 , . . . , φ n ] represents the Boolean function obtained by substituing each hole l i by φ i , and then seeing the result as a "hybrid" Boolean circuit 7 . We say that T [φ 0 , . . . , φ n ] is deterministic when every ∨-gate in the template is deterministic.

Observe that it can be the case that T [φ 0 , . . . , φ n ] is deterministic while T itself is not. For a simple example, take T to be the template with two holes l 0 ∨ l 1 , and take φ 0 def = x and φ 1 def = ¬x. Then T [φ 0 , φ 1 ] is deterministic but T is not. Proposition 3.7 then suggests the following definition: Definition 4.2. We say that a Boolean function φ is fragmentable if there exist a ¬-∨-template T and degenerate Boolean functions φ 0 , . . . , φ n (with n + 1 equals the number of holes of T ) such that T [φ 0 , . . . , φ n ] is deterministic and is equivalent to φ.

Note that in Definition 4.1 we allowed ¬-∨-templates to consist of a single leaf, which is then also the root. In particular, this implies that any degenerate Boolean function is fragmentable.

φ 2 def = ¬0 ∧ 1 ∧ 3; and φ 3 def = 0 ∧ 1 ∧ 2,
which are all degenerate. One can easily see that T [φ 0 , φ 1 , φ 2 , φ 3 ] is deterministic (because any two φ i , φ j with i j are disjoint) and (less easily) that T [φ 0 , φ 1 , φ 2 , φ 3 ], i.e., φ 0 ∨φ 1 ∨φ 2 ∨φ 3 , is equivalent to φ 9 . Therefore, φ 9 is fragmentable. Observe the we did not use ¬-gates in the template.

First properties

The main property of fragmentability is that it implies having d-Ds constructible in polynomial time. This is actually its sole purpose.

Proposition 4.4. If φ is fragmentable then Q φ ∈ d-D(PTIME).
Proof. Let T be a ¬-∨-template and φ 0 , . . . , φ n be degenerate Boolean functions such that T [φ 0 , . . . , φ n ] if deterministic and equivalent to φ, and let D be an arbitrary database. Since φ 0 , . . . φ n are degenerate, by Proposition 3.7 we can construct in PTIME deterministic decomposable Boolean circuits C 0 , . . . , C n capturing the lineages Lin(Q φ i , D) of Q φ i on D, for 0 ⩽ i ⩽ n. Let C φ be the Boolean circuit obtained by plugging the circuits C i at the holes of T . Then one can check that C φ is a d-D and that it captures Lin(Q φ , D).

□

Remember that we are working with data complexity here, so we can assume that we know T and φ 0 , . . . , φ n already. Although we do not know the exact complexity of finding these given φ, the results of the next section will imply (Corollary 5.12) that this task is computable. Another property of fragmentability is that it implies having zero Euler characteristic. Proposition 4.6. If φ is fragmentable then e(φ) = 0.

Proof. Easily proved by bottom-up induction on T [φ 0 , . . . , φ n ] and by using the facts that (1) e(φ) = 0 when φ is degenerate;

(2) e(¬φ) = -e(φ); and (3) e(φ ∨ φ ′ ) = e(φ) + e(φ ′ ) when φ and φ ′ are disjoint. □

At first glance, the definition of fragmentability seems completely ad-hoc. Indeed, it could very well be the case that some H -query, say even H + -query, is in d-D(PTIME) by other means than Proposition 4.4. Yet, we will show in the next section the surprising fact that the converse of Proposition 4.6 is also true, implying that fragmentability is the right notion to consider.

UPPER BOUND

We dedicate this section to showing that having a zero Euler characteristic implies being fragmentable. Formally: Proposition 5.1. If e(φ) = 0 then φ is fragmentable.

Before embarking on its proof, we spell out its consequences. The first one is that all the H -queries Q φ with e(φ) = 0 are in d-D(PTIME), thanks to Proposition 4.4:

Theorem 5.2. If e(φ) = 0 then Q φ ∈ d-D(PTIME).
This is, in a sense, the main result of this article. We have represented in Figure 1 all the H -queries with zero Euler characteristic by the dashed green rectangle. Theorem 5.2 applies in particular to all the safe H + -queries, thanks to Corollary 3.9. So we get: Corollary 5.3. All safe H + -queries are in d-D(PTIME).

Remember that the intensional-extensional conjecture was thought to hold for the safe H + -queries, because the use of inclusionexclusion seemed unavoidable. This surprising result shows that it is avoidable, and that we can get away by using only decomposability and determinism.

Less importantly, by combining Proposition 5.1 and Proposition 4.6, we obtain the following: Corollary 5.4. φ is fragmentable if and only if e(φ) = 0.

In the rest of this section, we prove Proposition 5.1. The idea is the following. In Section 5.1, we define a notion of transformation between Boolean functions. This transformation defines an equivalence relation (denoted ≃) between all Boolean functions, and we show that for a Boolean function φ, if φ ≃ ⊥ then φ is fragmentable. Then, in Section 5.2 we show that φ ≃ ⊥ when e(φ) = 0.

∅ {0} {1} {2} {3} {0, 1} {0, 2} {0, 3} {1, 2} {1, 3} {2, 3} {0, 1, 2} {0, 1, 3} {0, 2, 3} {1, 2, 3} {0, 1, 2, 3} Figure 3: The colored graph G V [φ 9 ]. Note that it is differ- ent from L φ 9
CNF (Figure 2). In particular, the semantics of the nodes is not the same.

The transformation

(We remind once again the reader that the set V = {0, . . . , k} of variables is fixed, and that we only consider Boolean functions with variables V .) We start with the definition of our notion of transformation between Boolean functions: Definition 5.5. Let φ, φ ′ be Boolean functions, ν ⊆ V a valuation and l ∈ V a variable. Then we write φ ∼∼∼∼▷

+(ν , l ) φ ′ whenever ν ̸ |= φ and ν (l ) ̸ |= φ and SAT(φ ′ ) = SAT(φ) ∪ {ν, ν (l ) }. Similarly, we write φ ∼∼∼∼▷ -(ν , l ) φ ′ whenever φ ′ ∼∼∼∼▷ +(ν , l )
φ, i.e., when ν |= φ and ν (l ) |= φ and SAT(φ ′ ) = SAT(φ) \ {ν, ν (l ) }. We will also use the following auxiliary relations:

• we write φ ∼∼∼∼▷ ±(ν , l ) φ ′ when φ ∼∼∼∼▷ +(ν , l ) φ ′ or φ ∼∼∼∼▷ -(ν , l ) φ ′ ; • we write φ ∼∼∼∼▷ + φ ′ when φ ∼∼∼∼▷ +(ν , l )
φ ′ for some ν, l, and similarly for φ ∼∼∼∼▷

V = {0, 1, 2, 3}) The graph G V [φ 9
] is shown in Figure 3 (ignore for now the fact that some edges are dashed and green).

Then, we have φ ∼∼∼∼▷ ± * φ ′ whenever we can go from

G V [φ] to G V [φ ′
] by iteratively (1) coloring two uncolored adjacent nodes; or (2) uncoloring two adjacent colored nodes. In particular, observe that this transformation never changes the Euler characteristic. We illustrate the transformation in Figure 4 (ignore for now the last sentence in the description).

We can now show that if φ ≃ ⊥, then φ is fragmentable: Proposition 5.8. If φ ≃ ⊥ then φ is fragmentable.

Proof. For some n ∈ N, we have ⊥ = φ 0 ∼∼∼∼▷ ±(ν1, l1)

• • • ∼∼∼∼▷ ±(νn, ln ) φ n = φ
for some valuations and variables ν i , l i . We show by induction on 0 ⩽ i ⩽ n that φ i is fragmentable by constructing a ¬-∨-template T i having i + 1 holes l 0 , . . . , l i and degenerate Boolean functions ψ j for 0 ⩽ j ⩽ i such that T i [ψ 0 , . . . ,ψ i ] is deterministic and represents φ i . The base case of i = 0 is trivial since ⊥ is degenerate, hence fragmentable. For the inductive case, supose i > 0 with φ i-1 fragmentable, and letT i-1 andψ 0 , . . . ,ψ i-1 be a template and degenerate functions witnessing that φ i-1 is fragmentable. Define ψ i by SAT(ψ i )

def = {ν i , ν (l i ) i }.
Surely ψ i is degenerate (it does not depend on variable l i ). We then distinguish the two possible cases:

• we have φ i-1 ∼∼∼∼▷ +(νi , li )
φ i . Then we can write φ i as the deterministic disjunction φ i-1 ∨ ψ i . But then we can define T i to be the template T i def = T i-1 ∨ l i , and one can easily check that T i [ψ 0 , . . . ,ψ i ] is deterministic and represents φ i . Therefore, φ i is indeed fragmentable.

• we have φ i-1 ∼∼∼∼▷ -(νi , li ) φ i . Then we can write φ i as ¬(¬φ i-1 ∨ ψ i ), with the disjunction being deterministic. But then we can define T i to be the template T i def = ¬(¬T i-1 ∨ l i ), and once again it is direct that T i [ψ 0 , . . . ,ψ i ] is deterministic and represents φ i . Hence φ i is fragmentable. □

If e(φ) = 0 then φ ≃ ⊥

The missing piece to show Proposition 5.1 is to prove that whenever e(φ) = 0 then φ is equivalent to ⊥. This is what we do in this section. Formally: Proposition 5.9. If e(φ) = 0 then φ ≃ ⊥.

In order to do that, we need two simple lemmas, which we will also reuse in the next section. The first is what we call the chaining lemma: Lemma 5.10 (Chaining lemma). Let φ be a Boolean function, and ν ν ′ be two valuations such that there is a simple path ν = ν 0 -• • • -ν n+1 = ν ′ from ν to ν ′ in G V with n ⩾ 0 and ν i SAT(φ) for 1 ⩽ i ⩽ n. Then we have the following:

Chainkilling. If (-1) |ν | (-1) |ν ′ | (i.e., n is even) and {ν, ν ′ } ⊆ SAT(φ) then, defining φ ′ by SAT(φ ′ ) def = SAT(φ) \ {ν, ν ′ }, we have φ ∼∼∼∼▷ ± * φ ′ .
In other words, we can uncolor both ν and ν ′ .

We say that we have chainkilled ν and ν ′ . Chainswapping. If (-1) |ν | = (-1) |ν ′ | (i.e., n is odd) and ν ∈ SAT(φ) and ν ′ SAT(φ) then, defining φ ′ by SAT(φ ′ ) def = (SAT(φ)\{ν })∪{ν ′ }, we have φ∼∼∼∼▷ ± * φ ′ . In other words, we can uncolor ν and color ν ′ . We say that we have chainswapped ν to ν ′ .

Proof. We only explain the chainkilling part, as chainswapping works similarly. Let n = 2i. For 0 ⩽ j < i, do the following: color the nodes ν 2j+1 and ν 2j+2 and then uncolor the nodes ν 2j and ν 2j+1 . Finally, uncolor the nodes ν 2i and ν 2i+1 . (Or, alternatively, first color all the nodes on the path and then uncolor everything.) □ Figure 4 illustrates a chainswap. In this section we will only need the chainkilling part of the lemma, but we will use chainswapping in the next section. The second lemma that we need is the following

ν 0 ν 1 ν 2 ν 3 ν 4 ν 0 ν 1 ν 2 ν 3 ν 4 ν 0 ν 1 ν 2 ν 3 ν 4 ν 0 ν 1 ν 2 ν 3 ν 4 ν 0 ν 1 ν 2 ν 3 ν 4 ∼∼∼▷ - ∼∼∼▷ + ∼∼∼▷ - ∼∼∼▷ + ν 0 ν 0 ν 1 ν 2 ν 2 ν 2 ν 3 ν 4 ν 4
Figure 4: Imagine that the path at the top is a subgraph of the colored graph G V [φ] for some function φ (for instance, the dashed green path in Figure 3). The consecutive subgraphs are obtained by single steps of our transformation. The total transformation also illustrates what we call a chainswap (Definition 5.10).

(in this section we only need its instantiation when e(φ) = 0), which we call the fetching lemma:

= ν 0 -• • • -ν n+1 = ν ′ from ν to ν ′ in G V (hence with n even) such that ν i SAT(φ) for 1 ⩽ i ⩽ n.
i ′ def = min(i < j ⩽ m + 1 | (-1) |ν ′′ j | = (-1) |ν ′′′ | and ν ′′ j |= φ).
Then we can take ν to be ν ′′ i and ν ′ to be ν ′′ i ′ , which satisfy the desired property.

□

Given the right circumstances (#φ |e(φ)|), this lemma fetches two valuations ν, ν ′ for us to chainkill them. With these tools in place, it is now easy to prove Proposition 5.9: Proof of Proposition 5.9. Let φ be such that e(φ) = 0. We prove the claim by induction on #φ. When #φ = 0 then we have φ = ⊥, hence a fortiori φ ≃ ⊥. Assume now that #φ > 0. Lemma 5.11 fetches two satisfying valuations ν, ν of φ, which we then chainkill. Let φ ′ be the function obtained. We again have e(φ ′ ) = 0, because the transformation ∼∼∼∼▷ ± does not change the Euler characteristic. Moreover, we have #φ ′ = #φ -2, so that φ ′ ≃ ⊥ by induction hypothesis, and therefore φ ≃ ⊥ as well. □

Notice how the same valuation could be colored and uncolored multiple times, in case it appears on the paths of different pairs of valuations that are chainkilled. Also, and although this is of absolutely no use to us, we note here the amusing fact that an analogue of Proposition 5.9 works for any connected bipartite colored graph. Moreover, by inspection of the proofs, we also obtain the following: Corollary 5.12. It is computable, given a fragmentable Boolean function φ, to find a ¬-∨-template T and degenerate Boolean functions φ 0 , . . . , φ n such that T [φ 0 , . . . , φ n ] if deterministic and equivalent to φ. This concludes the upper-bound results of this paper. In the next section, we reuse the tools that we have developed so far to carry a detailed analysis of the remaining cases (e(φ) 0).

EQUIVALENCES AND HARDNESS

The results of the last section imply that, for any two Boolean functions φ, φ ′ with e(φ) = e(φ ′ ) = 0, we have φ ≃ φ ′ . Indeed, by Proposition 5.9 we have φ ≃ ⊥ and φ ′ ≃ ⊥, implying φ ≃ φ ′ . In fact, we can show a more general statement about our transformation. We claim: Proposition 6.1. We have e(φ) = e(φ ′ ) if and only if φ ≃ φ ′ .

The proof is similar to that of Proposition 5.9, but is more involved. We first discuss the consequences of Proposition 6.1 in terms of tractability and compilation of the H -queries in Section 6.1, and then prove the proposition in Section 6.2.

Consequences

Proposition 6.1 allows us to prove: Theorem 6.2. Let φ, φ ′ such that e(φ) = e(φ ′ ). Then the following hold:

(a) we have

PQE(Q φ ) ≡ T PQE(Q φ ′ ); (b) we have Q φ ∈ d-D(PTIME) iff Q φ ′ ∈ d-D(PTIME); (c) we have Q φ ∈ d-D(PSIZE) iff Q φ ′ ∈ d-D(PSIZE).
Proof. The proof is similar to that of Proposition 5.8. We sketch the only-if directions of (b) and (c), but (a) works similarly. By Proposition 6.1, we have φ = φ 0 ∼∼∼∼▷ ±(ν1, l1)

• • • ∼∼∼∼▷ ±(νn, ln )
φ n = φ ′ for some n ∈ N and valuations and variables ν i , l i . We show by induction on 0 ⩽ i ⩽ n that Q φ i ∈ d-D(PTIME). The case i = 0 holds by assumption.

For the inductive case we proceed just as in Proposition 5.8, but this time we use the degeneracy of ψ i to obtain Q ψ i ∈ d-D(PTIME) by Proposition 3.7. The whole construction can clearly be carried out in PTIME data complexity. □

Observe how each item says something different: as far as we can tell, and except when e(φ) = e(φ ′ ) = 0, in which case all three items are equivalent since PQE(Q φ ) ∈ d-D(PTIME) by Section 5, there is no obvious implication between any two of them.

Also observe that Theorem 6.2, together with the observations that e(⊥) = 0 and Q ⊥ ∈ d-D(PTIME), imply our main result of Theorem 5.2. We decided to present them separately to make the proofs more modular, so that someone only interested into the upper bound results of the paper can understand the relevant parts more easily (since, as we said, Proposition 6.1 requires more work; see also Figure 7).

We must now discuss a result of [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF] concerning FBDDs for the H -queries which, on the surface, seems closely related to the last two items of Theorem 6.2. There, the authors show the following (we paraphrase to fit our notation): Theorem 6.3 [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF]Theorem 3.9]. Let φ be nondegenerate, and φ ′ be an arbitrary Boolean function. Then any FBDD F representing the lineage of Q φ on a database D can be transformed into an FBDD F ′ representing the lineage of Q φ ′ on the same database, with only a polynomial increase in size.

First, we note that the proof techniques are seemingly very different: while we did not need to work at the tuple-level, the proof of Theorem 3.9 proceeds by chirugically examining the FBDD F in order to transform it into F ′ . In fact, one could even argue that the two results are inherently incomparable, for the following reasons:

(1) Theorem 6.2, items (b) and (c), do not hold when applied to FBDDs. Indeed, take φ would be in d-D(PSIZE), including those that are #P-hard by [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF]. Indeed, for all k ∈ N ⩾2 , there clearly exists a query Q φ ∈ H k such that φ is nondegenerate and e(φ) = 0. Then by Theorem 5.2 we have Q φ ∈ d-D(PTIME), hence any other H k -query would also be in d-D(PSIZE). This would not be in contradiction with anything, as far as we know, but it would still be quite surprising. Second, by combining Theorem 6.3 with an exponential lower bound on FBDD representations of one particular nondegenerate H -query Q φ big-FBDDs , the authors of [START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF] obtain an exponential lower bound on FBDDs for all nondegenerate H -queries. In our case we observe a similar phenomenon with Theorem 6.2, where an exponential lower bound on d-D representations for a query Q φ big-d-Ds would also apply to all queries with same Euler characteristic. However, the existence of such a query Q φ big-d-Ds would answer a long-standing open problem in knowledge compilation: that of separating d-Ds (or even d-DNNFs) with DNFs [START_REF] Amarilli | Connecting knowledge compilation classes and width parameters[END_REF][START_REF] Bova | Knowledge compilation meets communication complexity[END_REF][START_REF] Darwiche | A knowledge compilation map[END_REF]. This is because the lineage of any UCQ on a database can always be computed in PTIME as a DNF.

Nevertheless, we can still use Theorem 6.2 to show a hardness result extending that of [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] for H + -queries (though this was not the primary goal of this paper). Specifically, we show: Proposition 6.4. Let φ be a Boolean function (not necessarily monotone) with e(φ) 0 and such that min(e(φ) : φ is monotone) ⩽ e(φ) ⩽ max(e(φ) : φ is monotone). Then PQE(Q φ ) is #P-hard.

Proof. Let φ be such a Boolean function. We show in Appendix B that there exists a monotone Boolean function φ mon such that e(φ mon ) = e(φ). But then we have e(φ mon ) 0, hence by Corollary 3.9 we have that PQE(Q φ mon ) is #P-hard, and by Theorem 6.2, item (a), it holds that PQE(Q φ ) is #P-hard as well. □

We represented by the dashed red rectangle in Figure 1 all the H -queries to which this result applies. This unfortunately does not apply to all the H -queries Q φ with e(φ) 0: for instance, consider the function φ max-Euler whose satisfying valuations are exactly all the valuations of even size. Then we have e(φ max-Euler ) = 2 k , and this value is not reachable by a monotone function.

Proof of Proposition 6.1

As we have already observed, the transformation does not change the Euler characteristic, so we only need to show the "only if" part of Proposition 6.1, i.e., that if e(φ) = e(φ ′ ) then φ ≃ φ. Furthermore, since e(φ) = -e(¬φ), it is enough to show it when e(φ) ⩾ 0. We proceed in three steps. The first step is to transform the functions so that they have only satisfying valuations of even size. Formally: Lemma 6.5. Let φ a Boolean function with e(φ) ⩾ 0. Then there exists φ min ≃ φ having only satisfying valuations of even size.

Proof. We proceed as in the proof of Proposition 5.9: until φ has satisfying valuations of odd size, we use Lemma 5.11 to fetch two valuations ν, ν ′ , and then we chainkill them with Lemma 5.10. Indeed, this always decreases the number of valuations of odd size by one. □

By applying Lemma 6.5 to φ and φ ′ , we are left with two functions φ min and φ ′ min , both having only valuations of even size, and with #φ min = #φ ′ min . The second step is then to transform these into what we call a canonical form. Definition 6.6. We say that a Boolean function φ is in canonical form when (1) φ only has satisfying valuations of even size; and (2) there does not exist two valuations ν, ν ′ of even size with |ν ′ | < |ν | and ν ∈ SAT(φ) but ν ′ SAT(φ) (in other words, the satisfying valuations of φ are the smallest possible). Let us call such a pair of valuations a bad pair.

We then show: Lemma 6.7. Let φ be a Boolean function having only satisfying valuations of even size. Then there exists a Boolean function φ in canonical form such that φ ≃ φ.

Proof. We prove the claim by induction on the number B φ of bad pairs. If B φ = 0 then we are done, so assume B φ > 0, and let (ν, ν ′ ) be a bad pair of φ. We distinguish two cases:

• we have ν ′ ⊆ ν . Then there exists a descending path p from ν to ν ′ in G V . By "descending" we mean that the sizes of the valuations along the path are strictly decreasing (by 1, of course). Let ν i be a valuation on that path that satisfies φ and such that no intermediary valuation on p from ν i to ν ′ satisfies φ. Such a ν i clearly exists, since in the worst case we can take ν i def = ν . Observe that (ν i , ν ′ ) is a bad pair. We now chainswap ν i to ν ′ . Let φ ′ be the function obtained. It is clear that φ ′ only has satisfying valuations of even size, and that B φ ′ = B φ -1 (since we have eliminated the bad pair (ν i , ν ′ ) without introducing others), so that the claim holds by induction hypothesis. • we have ν ′ ⊈ ν . Then consider another valuation ν ′′ with |ν ′ | = |ν ′′ | and such that there is a descending path from ν to ν ′′ in G V (i.e., such that ν ′′ ⊆ ν : there clearly exist one such ν ′′ ). If ν ′′ does not satisfy φ, simply use the preceding item with ν ′′ instead of ν ′ , and we are done. If ν ′′ satisfies φ, then consider a path

ν ′′ = ν = 0 -ν + 1 -ν = 1 -• • •-ν + j -ν = j -• • • ν + n - ν = n = ν ′ from ν ′′ to ν ′ that alternates between valuations ν = j of size |ν ′′ | = |ν ′ | and valuations ν + j of size |ν ′′ | + 1.
Again, such a path clearly exists. For instance if ν = {0, 1, 2, 3} and ν ′ = {4, 5} and ν ′′ = {2, 3}, we have the path ν ′′ = {2, 3}-{2, 3, 4}-{3, 4}-{3, 4, 5}-{4, 5} = ν ′ . Now, consider the smallest j such that ν = j SAT(φ) (which is defined since

ν ′ = ν = n SAT(φ))
. We now chainswap ν ′′ to ν = j , which does not introduce any bad pair, and preserves the fact that all satisfying valuations are of even size. Then, we can simply use the preceding item with ν ′′ instead of ν ′ . □

We now apply Lemma 6.7 to φ min and φ ′ min , thus obtaining φmin and φ′ min , both in canonical form, and with # φmin = # φ′ min again. The third step is to show that φmin ≃ φ′ (1) pick a valuation ν ∈ SAT( φmin ) \ SAT( φ′ min ) and a valuation ν ′ ∈ SAT( φ′ min ) \ SAT( φmin ); these exist and are necessarily of size M; We then chainswap ν = j m to ν ′ , and then for 0 ⩽ p < m we chainswap ν = j p to ν = j p+1 . The total transformation then simply amounts to uncoloring ν and coloring ν ′ . Therefore, we indeed have φmin ≃ φ′ min , which implies φ min ≃ φ ′ min and then φ ≃ φ ′ , concluding the proof of Proposition 6.1.

(2) let ν = ν = 0 -ν + 1 -ν = 1 -• • •-ν + j -ν = j -• • • ν + n -ν = n = ν ′ be

OPEN PROBLEMS AND FUTURE WORK

In this section we mention some of the numerous questions that this work must leave behind. Some of them are directly related to other open problems in knowledge compilation, while others seem specific to probabilistic databases. We also justify the definition of our transformation.

Hardness and lower bounds. We start with the question of showing hardness for the queries in the dotted gray rectangle of Figure 1: Open problem 1. Show #P-hardness of all H -queries Q φ with e(φ) 0. This would require adapting the proofs of [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] to UCQs with negations, which appears to be challenging. Note that, thanks to Theorem 6.2 and Lemmas 6.5 and 6.7, it would be enough to show the hardness of the queries in canonical form. In an orthogonal direction, and as we have mentioned already, Theorems 5. Using fewer negations. A brief inspection of our proofs indicates that we have spent a generous number of negations to construct the d-Ds. One can readily wonder if that was really necessary. In this regard, an easy observation is that if φ ∼∼∼∼▷ - * ⊥, then Q φ ∈ d-DNNF(PTIME), and that if φ ∼∼∼∼▷ + * ⊤ then ¬Q φ ∈ d-DNNF(PTIME). This was actually the approach taken in [START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF].

The facts φ ∼∼∼∼▷ - * ⊥ and φ ∼∼∼∼▷ + * ⊤ can be reformulated using more standard notions of graph theory: we have φ∼∼∼∼▷ - * ⊥ iff the subgraph of G V [φ] induced by the colored nodes has a perfect matching, and φ ∼∼∼∼▷ + * ⊤ iff that induced by the non-colored nodes has a perfect matching. We then conjecture the following:

Conjecture 1 (See also [START_REF] Monet | Perfect matching of monotone Boolean function with null Euler characteristic[END_REF][START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF]). If φ is monotone and e(φ) = 0, then the subgraph of G V [φ] induced by the colored nodes, or that induced by the non-colored nodes, has a perfect matching.

First, we note that the claim does not hold if we do not impose φ to be monotone. Indeed, consider the function φ no-PM for k = 4, whose graph G V [φ no-PM ] we have depicted in Figure 5. This function has zero Euler characteristic, yet it is easy to see that the subgraph induced by the colored (resp., non-colored) nodes has no perfect matching: the colored node {3, 4} (resp., non-colored node {0, 3, 4}) is isolated. In a sense, this Boolean function justifies the definition of our transformation, and shows that the approach of [START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF] was doomed to fail for the H -queries that are not UCQs. Second, and much harder to see, the "or" in Conjecture 1 is necessary. Indeed, there exists a monotone function φ one-neg (with k = 5) such that the colored nodes have no perfect matching but the non-colored nodes do (and vice versa, by symmetry). We depicted G V [φ one-neg ] in Appendix C (this is actually the smallest such function). Third, we have checked in [START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF], using the SAT solver Glucose [START_REF] Audemard | Predicting learnt clauses quality in modern SAT solvers[END_REF], that this conjecture holds for all monotone Boolean functions with k ⩽ 5, amounting to about 20 million non-isomorphic (under permutation of the variables) nondegenerate9 functions. This conjecture seems also closely related to the open problem in knowledge compilation of determining whether d-DNNFs are closed under negation 10 .

Generalize our technique to all UCQs. We now discuss the most important question: extending the techniques we have developed to capture a larger class of queries than the H -queries. To do this, recall that the algorithm of [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] for UCQs recursively alternates between two steps. The first step is to find what is called a separator variable, intuitively ensuring that the subqueries obtained are independent. This step can clearly be simulated with d-Ds. The second step is to perform inclusion-exclusion using Möbius's inversion formula. Here the algorithm recurses on the subqueries of the CNF lattice whose Möbius coefficient is not zero, potentially allowing for #P-hard queries to be ignored during the computation. It is this step that seems hard to simulate using a knowledge compilation approach. With this article, we have shown that we can simulate it, in the special case where the bottom term in the CNF lattice is the only hard subquery (and has a zero Möbius coefficient), and where we can recursively construct d-Ds for subqueries that are disjunctions of two connected terms in the poset of the original query (i.e., the poset of Definition 5.6). Although we do not have a concrete example at hand 11 , this already seems to define a larger class of queries than the H -queries. However, it is far from obvious how to extend our technique to avoid other #P-hard queries than the bottom one. We leave this task for future work.

∅ 0 1 2 3
Open problem 3. Generalize our techniques to all UCQs, i.e., show that all safe UCQs are in d-D(PTIME).

CONCLUSION

To the best of our knowledge, we provide the first result formally proving that the inclusion-exclusion principle can be simulated using decomposability and determinism only. We see this as yet another indication that knowledge compilation is an effective way to treat query answering on probabilistic databases [START_REF] Amarilli | Provenance circuits for trees and treelike instances[END_REF][START_REF] Amarilli | Connecting knowledge compilation classes and width parameters[END_REF][START_REF] Jha | Knowledge compilation meets database theory: compiling queries to decision diagrams[END_REF]. Although this new technique applies only to a restricted class of UCQs, the queries considered here seem to already contain the core difficulty of the intensional-extensional conjecture. We think that solving this problem for all UCQs will require solving it for UCQs with negations (more precisely, for Boolean combinations of CQs). This is reminiscent of the algorithm of [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] for UCQs, which, even when applied to a CQ, can introduce UCQs in the computation.

ACKNOWLEDGMENTS

I acknowledge Dan Olteanu for our initial work on the problem [START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF]. In particular, this joint work already contains the idea of covering the satisfying valuations of φ with mutually exclusive terms, which we reuse intensively here (see the paragraph "The difference

A PROOFS FOR SECTION 3 (THE H -QUERIES) A.1 d-Ds for degenerate H -queries

In this section we explain how to build d-Ds in polynomial time for H -queries Q φ such that φ is degenerate. Remember that we have: Proposition 3.7 (Implied by Lemma 3.8 of [START_REF] Fink | Dichotomies for queries with negation in probabilistic databases[END_REF]). If φ (not necessarily monotone) is degenerate, then Q φ ∈ OBDD(PTIME).

We only explain how it works for d-Ds, since this is what we need (but we will still use OBDDs in the proof, and we assume here that the reader is familiar with their definition). For a valuation ν ⊆ V , we write φ ν the Boolean function defined by SAT(φ ν ) def = {ν }. Since φ is degenerate, let l ∈ V be a variable upon which it does not depend. We can then write φ as φ = ν |=φ,l ν (φ ν ∨ φ ν (l ) ). The outermost ∨ being disjoint, we only need to explain how to build d-Ds for the queries Q φ ν ∨φ ν (l ) . The query Q φ ν ∨φ ν (l ) can be written as

Q L ∧ Q R , where Q L is i ∈P L h k,i ∧ i ∈N L ¬h k,i for some subsets P L , N L ⊆ {0, . . . , l -1} with P L ∩ N L = ∅, and similarly Q R is i ∈P R h k,i ∧ i ∈N R ¬h k,i for some subsets P R , N R ⊆ {l + 1, . . . , k } with P R ∩ N R = ∅.
Since the Boolean queries Q L and Q R do not share any relational predicate, by decomposability it is enough to show how to build d-Ds for these two, separately. We only show it for Q L since Q R works similarly. To do this, we will build OBDDs O i for the queries h k,i , i ∈ {0, . . . , l -1}, under the same variable order Π L (recall that the variables of the lineage are the tuples of the database). This will be enough, because we can then use standard techniques [START_REF] Wegener | BDDs-design, analysis, complexity, and applications[END_REF] to combine these OBDDs and obtain an OBDD for Q L . Let {a 1 , . . . , a n } be the domain of the database D. The variable order Π L that we consider is

Π L def = Π L (1) . . . Π L (n),
where Π L (i) def = R(a i ), S 1 (a i , a 1 ), . . . , S l -1 (a i , a 1 ), S 1 (a i , a 2 ), . . . , S l -1 (a i , a 2 ), . . . , S 1 (a i , a n ), . . . , S l -1 (a i , a n ). Under this variable order, it is easy to see that we can build in polynomial time OBDDs O i for the queries h k,i , i ∈ {0, . . . , l -1}, concluding the proof.

A.2 Equivalence Möbius-Euler

In this section we prove Lemma 3.8. We start by recalling its statement (remember that k ∈ N ⩾1 and V = {0, . . . , k} are fixed): • д(x) = u ⩽x f (u) for all x ∈ P;

• f (x) = u ⩽x µ(u, x)д(u) for all x ∈ P.

The second one is the notion of probability of a Boolean function, which we introduce formally here:

Definition A.2. A probability assignment π is a mapping from V to [0; 1]. Given a valuation ν ⊆ V and a probability assignment π , the probability π (ν ) of ν under π is defined as

π (ν ) def = x ∈ν π (x) x ∈V \ν (1 -π (x)) .
Given a Boolean function φ and a probability assignment π , the probability Pr(φ, π ) of φ under π is then naturally defined as the total probability mass under π of the valuations that satisfy φ, that is Pr(φ, π ) def = ν |=φ π (ν ).

We will be using specific probability assignments: Definition A.3. For t ∈ [0; 1], let π t denote the probability assignment that maps every variable to t.

The third ingredient is a univariate variant of a characteristic polynomial of φ [START_REF] Nisan | On the degree of Boolean functions as real polynomials[END_REF], of which we will give three different expressions: µ DNF (x, 1)t α ′ s .

We will show that these polynomials are equal:

Lemma A.5. Let φ be a nondegenerate monotone Boolean function. Then for all t ∈ R, we have that P φ (t) = P φ CNF (t) = P φ DNF (t).

This will imply Lemma 3.8: indeed, observe that the coefficient of t k +1 is ν |=φ (-1) k+1-|ν | = (-1) k +1 ν |=φ (-1) |ν | in P φ (t), and is (-1) k +1 µ CNF ( 0, 1) in P φ CNF (t), and is -µ DNF ( 0, 1) in P φ DNF (t). Since P φ (t) and P This time, we have д(x) = u ⩽x f (u) and f (x) = u ⩽x µ DNF (u, x)д(u) and д(x) = t α s for all x = d ′ s ∈ L φ DNF . Combining with P φ (t) = 1-f ( 1) we obtain that P φ (t) = P φ DNF (t). This finishes the proof. □

B PROOFS FOR SECTION 6 (EQUIVALENCES AND HARDNESS)

In this section we prove the following, which we used in the proof of Proposition 6.4 (remember, once again, that k ∈ N ⩾1 and the set of variables V = {0, . . . , k} are fixed):

Lemma B.1. Let φ be a Boolean function (not necessarily monotone) with e(φ) 0 and such that min(e(φ) : φ is monotone) ⩽ e(φ) ⩽ max(e(φ) : φ is monotone). Then there exists a monotone Boolean function φ mon such that e(φ mon ) = e(φ).

Proof. We will assume wlog that e(φ) > 0, as the case of e(φ) < 0 is symmetric. The idea of the proof is to start from a monotone Boolean function φ M that maximizes e(φ M ), and then to modify φ M (specifically, we will remove satisfying valuations) to show that all the intermediate values between 0 and e(φ M ) for the Euler characteristic (hence, also the value e(φ)) are achievable by a monotone Boolean function. More formally, consider the Boolean functions ψ 0 , . . . ,ψ |SAT(φ M )| , obtained by starting with ψ 0 def = φ M and iteratively removing exactly one satisfying assignment of maximal size. Then each ψ i for 0 ⩽ i ⩽ |SAT(φ M )| is a monotone Boolean function, and we have that ψ |SAT(φ M ) | = ⊥. Moreover, the Euler characteristic of ψ i ,ψ i+1 differ only by one. Since we have e(⊥) = 0, and since we know that 0 < e(φ) ⩽ e(ψ 0 ), there exists a ψ i such that e(ψ i ) = e(φ), and we can then take ψ i to be φ mon . This concludes the proof. □

For completeness (but this is of no use to us), we note here that the monotone Boolean functions φ M such that |e(φ M )| is maximized are characterized precisely in [START_REF] Björner | An extended Euler-Poincaré theorem[END_REF]. Since [START_REF] Björner | An extended Euler-Poincaré theorem[END_REF] is all about simplicial complexes, we will paraphrase their result in terms of Boolean functions here. To do it correctly, we must keep in mind that (1) for our purposes, a "simplicial complex" is the same thing as "the negation of a monotone Boolean function", so we need to reverse the powerset; and (2) in simplicial complexes terminology, the dimension of a face ν ⊆ V is |ν | -1. We then have: , having e(φ) = 0, illustrating that in Conjecture 1, the "or" is necessary: the colored nodes have no perfect matching (because 012345 needs to be matched to both 01234 and 01345), but the non-colored ones do (checked with a SAT solver).

Figure 1 :

 1 Figure1: Picture of the situation. Outmost black rectangle: all H -queries. Interior black horizontal rectangle: all H +queries (UCQs). Solid green rectangle: all safe H + -queries according to the dichotomy of[START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF], i.e., whose CNF lattice have zero Möbius value. Solid red rectangle: all unsafe H + -queries. Blue vertical rectangle: all the H -queries having OBDDs constructible in PTIME (upper bound[START_REF] Fink | Dichotomies for queries with negation in probabilistic databases[END_REF], lower bound[START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF]). These are the inversion-free H -queries and correspond to what we call degenerate Boolean functions. Dashed green rectangle (left): all the H -queries to which our technique can apply, implying that they have d-Ds constructible in PTIME. These correspond to fragmentable Boolean functions, or equivalently, to those having zero Euler characteristic. Dashed red rectangle (right): the H -queries corresponding to Boolean functions having non-zero Euler characteristic and for which we could show #P-hardness. Dotted gray rectangle: all the remaining Hqueries corresponding to Boolean functions having nonzero Euler characteristic. We conjecture these to be #P-hard as well. Note that each individual region contains an infinite number of queries.

Lineages.

  The lineage of a Boolean query Q over D is a Boolean function Lin(Q, D) on the tuples of D mapping each sub-database D ′ ⊆ D of D to True or False depending on whether D ′ satisfies Q or not. It is clear that, by definition, for any probability mapping π : D → [0; 1] we have Pr(Q, (D, π )) = Pr(Lin(Q, D), π ), where the later is defined just as expected (see Definition A.2 in Appendix A.2

Lemma 3 . 8 .

 38 Let φ be a nondegenerate monotone Boolean function on V . Then we have e(φ) = µ CNF ( 0, 1) = (-1) k µ DNF ( 0, 1), where µ CNF (resp., µ DNF ) is the Möbius function of L φ CNF (resp., L φ DNF ).

Example 4 . 3 .

 43 Consider φ 9 from Example 3.3. Let T be the ¬-∨template T def = l 0 ∨l 1 ∨l 2 ∨l 3 , and let φ 0 def = 0∧¬2∧3; φ 1 def = ¬1∧2∧3;

Example 4 . 5 .

 45 Continuing Example 4.3, since φ 9 is fragmentable we obtain that Q φ 9 ∈ d-D(PTIME) 8 .

-Example 5 . 7 .

 57 transitive closures thereof. It is clear from the definitions that ∼∼∼∼▷ ± * is symmetric, so let us write ≃ the induced equivalence relation. Next, we explain how to visually understand this transformation. Definition 5.6. Let G V be the undirected graph with node set 2 V and edge set {{ν, ν (l ) } | ν ⊆ V , l ∈ V }. Let φ be a Boolean function. We define the colored graph G V [φ] to be the graph G V where we have colored every satisfying valuation of φ. Consider again the function φ 9 from Example 3.3 (here

Lemma 5 . 11 (

 511 Fetching lemma). Let φ be such that #φ |e(φ)|. Then there exist satisfying valuations ν, ν ′ of φ with (-1) |ν | (-1) |ν ′ | and a simple path ν

  Proof. Since #φ |e(φ)|, there exist satisfying valuations ν ′′ , ν ′′′ of φ with (-1) |ν ′′ | (-1) |ν ′′′ | . Let ν ′′ = ν ′′ 0 -• • • -ν ′′ m+1 = ν ′′′′ be an arbitrary simple path from ν ′′ to ν ′′′ in G V (such a path clearly exists because G V is a connected graph). Now, let i def = max(0 ⩽ j ⩽ m | (-1) |ν ′′ j | = (-1) |ν ′′ | and ν ′′ j |= φ), and then let

def=

  ⊥ and φ ′ to be φ 9 from Example 3.3. We have e(⊥) = e(φ 9 ) = 0. Yet, Q ⊥ ∈ FBDD(PTIME) (clearly), but Q φ 9 FBDD(PSIZE) by the lower bounds of[START_REF] Beame | Exact model counting of query expressions: limitations of propositional methods[END_REF].(2) Less convincingly, if we could show a version of Theorem 6.3 with d-Ds instead of FBDDs, then all H -queries (for k ⩾ 2)

  min . Letting M def = max(|ν | : ν |= φmin ) and M ′ def = max(|ν | : ν |= φ′ min ), we necessarily have M = M ′ because the functions are in canonical form and have the same number of satisfying valuations. If M = |V | then clearly φmin = φ′ min , because then SAT( φmin ) and SAT( φ′ min ) both contain exactly all the valuations of even size. Otherwise, we can use valuations of size M + 1 to transform, say, φmin into φ′ min , by iteratively doing the following:

  a simple path from ν to ν ′ that alternates between valuations ν = j of size |ν | = |ν ′ | = M and valuations ν + j of size M + 1. Let 0 = j 0 < . . . < j m < n be all the indices such that ν = j l |= φmin .

  2 and 6.2 are begging for a counterpart lower bound: Open problem 2. Show superpolynomial lower bounds for d-D representations of the lineages of all H -queries Q φ with e(φ) 0. However, a lower bound on d-Ds seems far out of reach with current techniques. Instead, a framework to show lower bounds on d-DNNFs has recently been introduced in [8], using tools from communication complexity. Hence, maybe showing a lower bound on d-DNNFs representations could be an easier target (though this would still answer an important open problem in knowledge compilation).

Lemma 3 . 8 .

 38 Let φ be a nondegenerate monotone Boolean function on V . Then we have e(φ) = µ CNF ( 0, 1) = (-1) k µ DNF ( 0, 1), where µ CNF (resp., µ DNF ) is the Möbius function of L φ CNF (resp., L φ DNF ). The proof contains three ingredients. The first one is the Möbius inversion formula: Proposition A.1 (See [35, Proposition 3.7.1]). Let P be a finite poset, and let f , д : P → R. Then the following are equivalent:

Definition A. 4 .x

 4 Let φ be a nondegenerate monotone Boolean function, written as 0⩽i ⩽n C i in CNF and as 0⩽i ⩽m C ′ i in DNF. Consider the CNF and DNF lattices of φ, L φ CNF and L φ DNF . For s ⊆ {0, . . . , n} or s ⊆ {0, . . . , m} we write d s def = i ∈s C i and d ′ s def = i ∈s C ′ i , as well as α s def = |d s | and α ′ s def = |d ′ s |. We define the polynomials P φ , P φ DNF , and P φ CNF of R[t] as follows:• P φ (t) def = Pr(φ, π t ); =d s ∈L φ CNF µ CNF (x, 1)(1 -t) α s ; • P φ DNF (t) def = 1x =d ′ s ∈L φ DNF

φ

  CNF and P φ DNF are the same polynomials, these coefficients are equal. So, let us show Lemma A.5: Proof of Lemma A.5. Clearly, it is enough to show that these polynomials are equal on [0; 1]. We use Proposition A.1 on L φ CNF and on L φ DNF to compute P φ (t). We start with L φ CNF . Define the functions f and д, from L φ CNF to R, as follows: let d s ∈ L φ CNF , then:(1) f (d s ) def = Pr (¬ i ∈s C i ) ∧ i ∈V \s C i , π t ;in other words the total probability mass of the valuations that do not satisfy any of the (disjunctive) clauses C i for i ∈ s but satisfy all other clauses C i .(2) д(d s ) def = Pr (¬ i ∈s C i , π t ); in other words the total probability mass of the valuations that do not satisfy any of the clauses C i for i ∈ s.We clearly haveд(x) = u ⩽x f (u) for all x ∈ L φ CNF , hence by Proposition A.1 we have f (x) = u ⩽x µ CNF (u, x)д(u). Moreover, for x = d s ∈ L φ CNF , we have that д(x) = (1 -t) α s . Now, since P φ (t) = f ( 1), we indeed have that P φ (t) = P φ CNF (t).Let us now have a look at L φ DNF . The reasoning is similar, but we include it for completeness. Forx = d ′ s ∈ L φ DNF define: (1) f (d ′ s ) def = Pr ( i ∈s C ′ i ) ∧ ¬ i ∈V \s C ′ i ,π t ; in other words the total probability mass of the valuations that satisfy all the (conjunctive) clauses C ′ i for i ∈ s but none of the other clauses C ′ i . (2) д(d ′ s ) def = Pr i ∈s C ′ i , π t ; in other words the total probability mass of the valuations that satisfy all the clauses C ′ i for i ∈ s.

Theorem B. 2 (Figure 6 :

 26 Figure 6: The colored graph G V [φ one-neg ], having e(φ) = 0, illustrating that in Conjecture 1, the "or" is necessary: the colored nodes have no perfect matching (because 012345 needs to be matched to both 01234 and 01345), but the non-colored ones do (checked with a SAT solver).

  The colored graph G V [φ no-PM ], illustrating that Conjecture 1 must be restricted to monotone functions. For space reasons we write, e.g., 024 instead of {0, 2, 4}.

					01234
			0123	0124	0134	0234	1234
	012	013	014	023	024	034	123	124	134	234
	01	02	03	04	12	13	14	23	24	34
							4
	Figure 5:

The notation d-D was introduced in[START_REF] Monet | Towards deterministic decomposable circuits for safe queries[END_REF].1

Note that the uniqueness of φ CNF is less obvious than for φ DNF , see for instance[START_REF] Rdbury | Uniqueness of minimal positive CNFs[END_REF].

We could have defined it with ⩽ being set inclusion, this is just a matter of taste. We chose to use reversed set inclusion to fit with related work.

Defined similarly as the CNF lattice but by starting from the DNF minimized expression of φ instead of the CNF expression.

A synonym for the negation of a monotone Boolean function.

For instance, a satisfactory consequence is that we can easily express the number of (not necessarily monotone) functions with e(φ) = 0: this is 2 k j=0 2 k j

"Hybrid" because the leaves of the circuit are Boolean functions, i.e., we do not care how these are represented concretely.

We do not claim credit for this fact, as it has been known for at least 4 years by Guy Van den Broeck and Dan Olteanu (with whom we initially worked on the problem).

Since for degenerate functions the conjecture clearly holds.

Formally: given a d-DNNF D, is there a d-DNNF D ′ of polynomial size representing ¬D?

 [START_REF] Buneman | Why and where: a characterization of data provenance[END_REF]We do not think that such an example would be particularly enlightening.

with [26]" in the introduction for more details). I also acknowledge Guy Van den Broeck, Paul Beame and Vincent Liew, who had already worked on this problem and attempted similar approaches. Guy Van den Broeck and Dan Olteanu were the first to notice that one could use negation to attack the problem. I note here that Paul Beame and his student Vincent Liew independently found the query from Figure 1 (which was also a counterexample to one of their approaches). I am grateful to Pierre Senellart for careful proofreading of the paper. I thank the Millennium Institute for Foundational Research on Data (IMFD) for funding this research.

D OVERALL STRUCTURE

Lemma 3.8

Corollary 3.9

Section 3 Section 4

Section 5

If e(φ) = e(φ ′ ) then