Marcelo Arenas
email: marenas@ing.puc.cl

Pablo Barceló
email: pbarcelo@ing.puc.cl

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

Counting Problems over Incomplete Databases

Keywords: Incomplete databases, closed-world assumption, counting complexity, FPRAS 1

come

INTRODUCTION

Context. In the database literature, incomplete databases are often used to represent missing information in the data; see, e.g., [START_REF] Abiteboul | Foundations of databases[END_REF][START_REF] Libkin | Incomplete data: what went wrong, and how to fix it[END_REF][START_REF] Van Der Meyden | Logical approaches to incomplete information: A survey[END_REF]. These are traditional relational databases whose active domain can contain both constants and nulls, the latter representing unknown values [START_REF] Imieliński | Incomplete information in relational databases[END_REF]. There are many ways in which one can define the semantics of such a database, each being equally meaningful depending on the intended application. Under the so called closedworld assumption [START_REF] Abiteboul | Foundations of databases[END_REF][START_REF] Reiter | On closed world data bases[END_REF], a standard, complete database ν (D) is obtained from an incomplete database D by applying a valuation ν which replaces each null ⊥ in D with a constant ν (⊥). The goal is then to reason about the space formed by all valuations ν and completions ν (D) of D.

Decision problems related to querying incomplete databases have been well studied already. Consider for instance the problem Certainty(q( x)) which, for a fixed query q( x), takes as input an incomplete database D and a tuple ā and asks whether ā is an answer to q for every possible completion/valuation of D. By now, we have a deep understanding of the complexity of these kind of decision problems for different choices of query languages, including conjunctive queries (CQs) and FO queries [START_REF] Abiteboul | On the representation and querying of sets of possible worlds[END_REF][START_REF] Imieliński | Incomplete information in relational databases[END_REF]. However, having the answer to this question is sometimes of little help: what if it is not the case that q is certain on D? Can we still infer some useful information? This calls for new notions that could be used to measure the certainty with which q holds, notions which should be finer than those previously considered. This is for instance what the recent work in [START_REF] Libkin | Certain answers meet zero-one laws[END_REF] does by introducing a notion of best answer, which are those tuples ā for which the set of completions of D over which q( ā) holds is maximal with respect to set inclusion.

A fundamental complementary approach to address this issue can be obtained by considering some counting problems related to incomplete databases; more specifically, determining the number of completions/valuations of an incomplete database that satisfy a given Boolean query q. These problems are relevant as they tell us, intuitively, how close is q from being certain over D, i.e., what is the level of support that q has over the set of completions/valuations of D. Surprisingly, such counting problems do not seem to have been studied for incomplete databases. A reason for this omission in the literature might be that, in general, it is assumed that the domain over which nulls can be interpreted is infinite, and thus incomplete databases might have an infinite number of completions/valuations. However, in many scenarios it is natural to assume that the domain over which nulls are interpreted is finite, in particular when dealing with uncertainty in practice [START_REF] Agrawal | Foundations of uncertain-data integration[END_REF][START_REF] Andritsos | Clean answers over dirty databases: A probabilistic approach[END_REF][START_REF] Antova | 10 (10 6 ) worlds and beyond: efficient representation and processing of incomplete information[END_REF][START_REF] Benjelloun | ULDBs: Databases with uncertainty and lineage[END_REF][START_REF] Fan | Conditional functional dependencies for capturing data inconsistencies[END_REF][START_REF] Das Sarma | Representing uncertain data: models, properties, and algorithms[END_REF]. By assuming this we can ensure that the number of completions and valuations are always finite, and thus that they can be counted. This is the setting that we study.

In this paper, we will focus only on Boolean queries. We consider this as a necessary first step in understanding the complexity of some relevant counting problems over incomplete databases. Besides, as shown in the paper, the case of Boolean queries is rich and complex enough to deserve its own investigation, providing very valuable information for the general case where queries can have arbitrary tuples as answers.

Problems studied. We focus on the problems #Comp(q) and #Val(q) for a Boolean query q, which take as input an incomplete database D together with a finite set dom(⊥) of constants for every null ⊥ occurring in D, and ask the following: How many completions, resp., valuations, of D satisfy q? More formally, a valuation ν of D is a mapping that associates to every null ⊥ of D a constant ν(⊥) in dom(⊥). Then, given a valuation ν of D, we denote by ν (D) the database that is obtained from D after replacing each null ⊥ with ν (⊥). Besides, in this paper we consider set semantics, so repeated tuples have to be removed from ν (D). For #Comp(q) we count all databases of the form ν (D) such that q holds in ν (D). Instead, for #Val(q) we count the number of valuations ν such that q holds in ν (D). It is easy to see that these two values can differ, as there might be different valuations ν, ν ′ of D leading to the same completion, i.e., ν (D) = ν ′ (D). We think that both problems are meaningful: while #Comp(q) determines the support for q over the databases represented by D, we have that #Val(q) further refines this by incorporating the support for a particular completion that satisfies q over the set of valuations for D.

The problems we study are analogous to the ones studied in other uncertainty scenarios; in particular, in probabilistic databases [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF][START_REF] Suciu | Probabilistic databases[END_REF] and inconsistent databases [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF][START_REF] Bertossi | Database repairing and consistent query answering[END_REF][START_REF] Bertossi | Database repairs and consistent query answering: Origins and further developments[END_REF]. More specifically, we deal with the problems #Comp(q) and #Val(q) focusing on obtaining dichotomy results for them in terms of counting complexity classes, as well as studying the existence of randomized algorithms that approximate their results under probabilistic guarantees. For the dichotomies, we concentrate on self-join-free Boolean conjunctive queries (sjfBCQs). This assumption simplifies the mathematical analysis, while at the same defines a setting which is rich enough for many of the theoretical concepts behind these problems to appear in full force. Notice that a similar assumption is used in several works that study counting problems over probabilistic and inconsistent databases; see, e.g., [START_REF] Dalvi | Queries and materialized views on probabilistic databases[END_REF][START_REF] Maslowski | A dichotomy in the complexity of counting database repairs[END_REF].

To refine our analysis, we study two restrictions of the problems #Comp(q) and #Val(q) based on natural modifications of the semantics, and analyze to what extent these restrictions simplify our problems. For the first restriction we consider incomplete databases in which each null occurs exactly once, which corresponds to the well-studied setting of Codd tables -as opposed to naïve tables where nulls are allowed to have multiple occurrences. We denote the corresponding problems by #Val Cd (q) and #Comp Cd (q). For the second restriction, we consider uniform incomplete databases in which all the nulls share the same domain -as opposed to the basic non-uniform setting in which all nulls come equipped with their own domain. We denote the corresponding problems by #Val u (q) and #Comp u (q). When both restrictions are in place, we denote the problems by #Val u Cd (q) and #Comp u Cd (q). Our dichotomies for exact counting. We provide almost complete characterizations of the complexity of counting valuations and completions satisfying a given sjfBCQ q, when the input is a Codd table or a naïve table, and is a non-uniform or a uniform incomplete database (hence we have eight cases in total). The only case we have not yet completely solved is that of counting valuations in the uniform setting over Codd tables, i.e., the problem #Val u Cd (q). Our seven dichotomies express that these problems are either tractable or #P-hard, and that the tractable cases can be fully characterized by the absence of certain forbidden patterns in q. A pattern is simply an sjfBCQ which can be obtained from q essentially by deleting atoms, renaming relation symbols, deleting occurrences of variables and reordering the variables in atoms (the exact definition of this notion is given in Section 3). Our characterizations are presented in Table 1. By analyzing this table we can draw some important conclusions as explained next.

#Comp(q) and #Val(q) are computationally difficult: For very few sjfBCQs q the aforementioned problems can be solved in polynomial time. Take as an example the uniform setting over naïve tables. Then #Val u (q) is #P-hard as long as q contains the pattern R(x, x), or R(x) ∧ S(x, y) ∧T (y), or R(x, y) ∧ S(x, y). That is, as long as there is an atom in q that contains a repeated variable x, or a pair (x, y) of variables that appear in an atom and both x and y appear in some other atoms in q. By contrast, for this same setting, #Comp u (q) is #P-hard as long as q contains the pattern R(x, y) or R(x, x), that is, as long as there is an atom in q that is not of arity one. #Val(q) is always easier than #Comp(q): In all of the possible versions of our problem, the tractable cases for #Val(q) are a strict superset of the ones for #Comp(q). For instance, we have that #Comp u Cd (∃x∃y R(x, y)) is hard, while #Val u Cd (∃x∃y R(x, y)) is tractable (because #Val u (∃x∃y R(x, y)) is).

Even counting completions is hard: While counting the total number of valuations for an incomplete database can always be done in polynomial time, observe from Table 1 that #Comp u Cd (∃x∃y R(x, y)) is #P-hard, and thus that simply counting the completions of a uniform Codd table with a single binary relation R is #P-hard. Moreover, we show that in the non-uniform case a single unary relation suffices to obtain #P-hardness.

Codd tables help but not much: We show that counting valuations is easier for Codd tables than for naïve tables. In particular, there is always an sjfBCQ q such that counting the valuations that satisfy q is #P-hard, yet it becomes tractable when restricted to the case of Codd tables. However, for counting completions, both in the uniform and non-uniform setting, the sole restriction to Codd tables presents no benefits: for every sjfBCQ q, we have that #Comp(q) (resp., #Comp u (q)) is #P-hard if and only if #Comp Cd (q) (resp., #Comp u Cd (q)) is #P-hard. Non-uniformity complicates things: All versions of our problems become harder in the non-uniform setting. This means that in all cases there is an sjfBCQ q for which countings valuations is tractable on uniform incomplete databases, but becomes #P-hard assuming non-uniformity, and an analogous result holds for counting completions.

Our dichotomies for approximate counting. Although #Val(q) can be #P-hard, we prove in the paper that good randomized approximate algorithms can be designed for this problem. More precisely, we give a general condition under which #Val(q) admits a fully polynomial-time randomized approximation scheme [START_REF] Mark R Jerrum | Random generation of combinatorial structures from a uniform distribution[END_REF] (FPRAS). This condition applies in particular to all unions of Boolean conjunctive queries. Remarkably, we show that this no longer holds for #Comp(q); more precisely, there exists an sjfBCQ q such that #Comp(q) does not admit an FPRAS under a widely believed complexity theoretical assumption. More surprisingly, even counting the completions of uniform incomplete database containing a single binary relation does not admit an FPRAS under such an assumption (and in the non-uniform case, a single unary relation suffices). Generally, for sjfBCQs, we obtain seven dichotomies for our problems between polynomial-time computability of exact counting and non admissibility of an FPRAS. The only case that we did not solve yet is that of #Comp u Cd (q).

Beyond #P. It is easy to see that the problem of counting valuations is always in #P. This is no longer the case for counting completions, and in fact we show that, under a complexity theoretical assumption, there is an sjfBCQ q for which #Comp u (q) is not in #P. This does not hold if restricted to Codd tables, however, as we prove that #Comp Cd (q) is always in #P.

Table 1: Our dichotomies for counting valuations and completions of sjfBCQs. For each one of the eight cases, if an sjfBCQ q has as a pattern a query mentioned in that case, then the problem is #P-hard (and #P-complete for counting valuations, as well as for counting completions over Codd tables). In turn, for each case except for counting valuations under uniform Codd tables, if an sjfBCQ q does not have as a pattern any of the queries mentioned in that case, then the problem is in FP.

For reasons that we explain in the paper, a suitable complexity class for the problem #Comp(q) is SpanP, which is defined as the class of counting problems that can be expressed as the number of different accepting outputs of a nondeterministic Turing machine running in polynomial time. While we have not managed to prove that there is an sjfBCQ q for which #Comp(q) is SpanP-complete, we show in the paper that this is the case for the problem of counting completions for the negation of an sjfBCQ, even in the uniform setting; that is, we show that #Comp u (¬q) is SpanP-complete for some sjfBCQ q.

Organization of the paper. We start with the main terminology used in the paper in Section 2, and then present in Section 3 our three dichotomies on #Val(q) when q is an sjfBCQ, and the input incomplete database can be Codd or not, and the domain can be uniform or not. We then establish the four dichotomies on #Comp(q) in Section 4. In Section 5, we study the approximability complexity of our problems. We then give in Section 6 some general considerations about the exact complexity of the problem #Comp(q) going beyond #P. In Section 7, we discuss related work and explain the differences with the problems considered in this paper. Last, we provide some conclusions and mention possible directions for future work in Section 8. All missing proofs can be found in the appendix.

PRELIMINARIES

Relational databases and conjunctive queries. A relational schema σ is a finite non-empty set of relation symbols written R, S, T , . . . , each with its associated arity, which is denoted by arity(R).

Let Consts be a countably infinite set of constants. A database D over σ is a set of facts of the form R(a 1 , . . . , a arity(R) ) with R ∈ σ , and where each element a i ∈ Consts. For R ∈ σ , we denote by D(R) the subset of D consisting of facts over R. Such a set is usually called a relation of D.

A Boolean query q is a query that a database D can satisfy (written D |= q) or not (written D ̸ |= q). A Boolean conjunctive query (BCQ) over σ is an FO formula of the form

∃ x R 1 ( x1 ) ∧ . . . ∧ R m ( xm ) , (1)
where all variables are existentially quantified, and where for each i ∈ [1, m], we have that R i is a relation symbol in σ and xi is a tuple of variables with | xi | = arity(R i ). To avoid trivialities, we will always assume that m ⩾ 1, i.e., the query has at least one atom, and also that arity(R i ) ⩾ 1 for all atoms. For simplicity, we typically write a BCQ q of the form (1) as

R 1 ( x1 ) ∧ . . . ∧ R m ( xm ),
and it will be implicitly understood that all variables in q are existentially quantified. As usual, we define the semantics of a BCQ in terms of homomorphisms. A homomorphism from q to a database D is a mapping from the variables in q to the constants used in

D such that {R 1 (h( x1 )), . . . , R m (h( xm ))} ⊆ D.
Then, we have D |= q if there is a homomorphism from q to D. A self-join-free BCQ (sjfBCQ) is a BCQ such that no two atoms use the same relation symbol.

Incomplete databases. Let Nulls be a countably infinite set of nulls (also called labeled nulls in the literature), which is disjoint with Consts. An incomplete database over schema σ is a pair D = (T , dom), where T is a database over σ whose facts contain elements in Consts ∪ Nulls, and where dom is a function that associates to every null ⊥ occurring in D a subset dom(⊥) of Consts. Intuitively, T is a database that can mention both constants and nulls, while dom tells us where nulls are to be interpreted. Following the literature, we call T a naïve table [START_REF] Imieliński | Incomplete information in relational databases[END_REF].

An incomplete database D = (T , dom) can represent potentially many complete databases, via what are called valuations. A valuation of D is simply a function ν that maps each null ⊥ occurring in T to a constant ν (⊥) ∈ dom(⊥). Such a valuation naturally defines a completion of D, denoted by ν(T ), which is the complete database obtained from T by substituting each null ⊥ appearing in T by ν (⊥). It is understood, since a database is a set of facts, that ν (T ) does not contain duplicate facts. By paying attention to completions of incomplete databases that are generated exclusively by applying valuations to them, we are sticking to the so called closed-world semantics of incompleteness [START_REF] Abiteboul | Foundations of databases[END_REF][START_REF] Reiter | On closed world data bases[END_REF]. This means that the databases represented by an incomplete database D = (T , dom) are not open to adding facts that are not "justified" by the facts in T .

Example 2.1. Let D = (T , dom) be the incomplete database consisting of the naïve table T = {S(⊥ 1 , ⊥ 1 ), S(a, ⊥ 2 )}, and where dom(⊥ 1 ) = {a, b} and dom(⊥ 2 ) = {a, c}. Let ν 1 be the valuation mapping ⊥ 1 to b and ⊥ 2 to c. Then ν 1 (T ) is {S(b, b), S(a, c)}. Let ν 2 be the valuation mapping both ⊥ 1 and ⊥ 2 to a. Then ν 2 (T ) is {S(a, a)}. On the other hand, the function ν mapping ⊥ 1 and ⊥ 2 to b is not a valuation of D, because b dom(⊥ 2 ). □

(ν (⊥ 1 ), ν (⊥ 2 )) (a, a) (a, b) (b, a) (b, b) (c, a) (c, b) ν (D)
When every null occurs at most once in T , then D is what is called a Codd table [START_REF] Codd | Understanding relations (installment# 7)[END_REF]; for instance, the incomplete database in Example 2.1 is not a Codd table because ⊥ 1 occurs twice. We also consider uniform incomplete databases in which the domain of every null is the same. Formally, a uniform incomplete database is a pair D = (T , dom), where T is a database over σ and dom is a subset of Consts. The difference now is that a valuation ν of D must simply satisfy ν (⊥) ∈ dom for every null of D.

We will often abuse notation and use D instead of T ; for instance, we write ν

(D) instead of ν (T ), or R(a, a) ∈ D instead of R(a, a) ∈ T , or again D(R) instead of T (R).
Counting problems on incomplete databases. We will study two kinds of counting problems for incomplete databases: problems of the form #Val(q), that count the number of valuations ν that yield a completion ν (D) satisfying a given BCQ q, and problems of the form #Comp(q), that count the number of completions that satisfy q. The query q is assumed to be fixed, so that each query gives rise to different counting problems, and we are considering the data complexity [START_REF] Vardi | The complexity of relational query languages[END_REF] of these problems.

Before formally introducing our problems, let us observe that they are well defined if we assume that the set of constants to which a null can be mapped to is finite. Hence, for the (default) case of an incomplete database D = (T , dom), we assume that dom(⊥) is always a finite subset of Consts. Similarly, for the case of a uniform incomplete database D = (T , dom), we assume that dom is a finite subset of Consts. Finally, given a Boolean query q, we use notation sig(q) for the set of relation symbols occurring in q. With these ingredients, we can define our problems for the (default) case of incomplete naïve tables and a Boolean query q.

PROBLEM : #Val(q) INPUT :

An incomplete database D over sig(q) OUTPUT : Number of valuations ν of D with ν(D) |= q PROBLEM : #Comp(q) INPUT :

An incomplete database D over sig(q) OUTPUT : Number of completions ν (D) of D with ν (D) |= q

We also consider the uniform variants of these problems, in which the input D is a uniform incomplete database over sig(q), and the restriction of these problems where the input is a Codd table instead of a naïve table. We then use the terms #Val u (q), #Comp u (q) when restricted to the uniform case, #Val Cd (q), #Comp Cd (q) when restricted to Codd tables, and #Val u Cd (q), #Comp u Cd (q) when both restrictions are applied.

As we will see, even though the problems #Val(q) and #Comp(q) look similar, they are of a different computational nature; this is because two distinct valuations can produce the same completion of an incomplete database. In the following example, we illustrate this phenomenon.

Example 2.2. Let q be the Boolean conjunctive query ∃x S(x, x), and D be the (non-uniform) incomplete database D = (T , dom), with T = {S(a, b), S(⊥ 1 , a), S(a, ⊥ 2 )}, dom(⊥ 1 ) = {a, b, c} and dom(⊥ 2 ) = {a, b}. We have depicted in Figure 1 the six valuations of D together with the completions that they define. Out of these six valuations ν , only four are such that ν (D) |= q, so that we have #Val(q)(D) = 4. Moreover, there are only 3 distinct completions of D that satisfy q, so #Comp(q)(D) = 3. □ Counting complexity classes. Given two problems A, B, we write A ⩽ p T B when A reduces to B under polynomial-time Turing reductions. When both A and B are counting problems, we write A ⩽ p par B when A can be reduced to B under polynomial-time parsimonious reductions, i.e., there exists a polynomial-time computable function f that transforms an input x of A to an input f (x) of B such that A(x) = B(f (x)). We say that a counting problem is in FP when it can be solved in polynomial time. We will consider the counting complexity class #P [START_REF] Leslie | The complexity of computing the permanent[END_REF] of problems that can be expressed as the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Following [START_REF] Leslie | The complexity of computing the permanent[END_REF][START_REF] Valiant | The complexity of enumeration and reliability problems[END_REF], we define #P-hardness using Turing reductions. It is clear that FP ⊆ #P. This inclusion, on the other hand, is widely believed to be strict. Therefore, proving that a counting problem is #P-hard implies that it cannot be solved in polynomial time under such an assumption.

Graphs. In our reductions, we will often depart from hard problems that are defined over graphs. Unless mentioned otherwise, by graph we mean a pair G = (V , E), where V is a finite set of nodes, and E is a set whose elements are of the form {u, v} for u, v ∈ V and u v. Notice then that such graphs are undirected, cannot contain self-loops, and cannot contain multiple edges between any two nodes.

DICHOTOMIES FOR COUNTING VALUATIONS

In this section, given a fixed sjfBCQ q, we study the complexity of the problem of computing, given an incomplete database D, the number of valuations ν of D such that ν (D) satisfies q. Recall that we have four cases to consider for this problem depending on whether we focus on naïve or on Codd tables, where nulls are restricted to appear at most once, and whether we focus on non-uniform or uniform incomplete databases, where nulls are restricted to have the same domain. Our specific goal then is to understand whether the problem is tractable (in FP) or #P-hard in these scenarios, depending on the shape of q.

To this end, the shape of an sjfBCQ q will be characterized by the presence or absence of certain specific patterns. In the following definition, we introduce the necessary terminology to formally talk about the presence of a pattern in a query. Definition 3.1. Let q, q ′ be sjfBCQs. We say that q ′ is a pattern of q if q ′ can be obtained from q by using an arbitrary number of times and in any order the following operations: deleting an atom, deleting an occurrence of a variable, renaming a relation to a fresh one, renaming a variable to a fresh one and reordering the variables in an atom. 1Example 3.2. Recall that we always omit existential quantifiers in Boolean queries. Then we have that q ′ = R ′ (u, u, y) ∧ S ′ (z) is a pattern of q = R(u, x, u) ∧ S ′ (y, y) ∧ T (x, s, z, s). Indeed, q ′ can be obtained from q by deleting atom T (x, s, z, s), renaming R(u, x, u) as R ′ (u, x, u) to obtain R ′ (u, x, u) ∧ S ′ (y, y), reordering the variables in R ′ (u, x, u) to obtain R ′ (u, u, x) ∧ S ′ (y, y), renaming variable y into z to obtain R ′ (u, u, x) ∧ S ′ (z, z), deleting the second variable occurrence in S ′ (z, z) to obtain R ′ (u, u, x)∧S ′ (z), and finally renaming variable x into y to obtain q ′ . □

In the following general lemma, we show that if q ′ is a pattern of q, then each one of the problems considered in this section is as hard for q as it is for q ′ . Recall in this result that unless stated otherwise, our problems are defined for naïve tables. Lemma 3.3. Let q, q ′ be sjfBCQs such that q ′ is a pattern of q. Then we have #Val(q ′ ) ⩽ p par #Val(q) and #Val u (q ′ ) ⩽ p par #Val u (q). Moreover, the same results hold if we restrict to Codd tables.

The idea is then to show the #P-hardness of our problems for some simple patterns, which then we combine with Lemma 3.3 and with some tractability proofs to obtain the desired dichotomies. Our findings are summarized in the first two columns of Table 1 in the introduction. We first focus on the two dichotomies for the non-uniform setting in Section 3.1, and then we move to the case of uniform incomplete databases in Section 3.2. We explicitly state when a #P-hardness result holds even in the restricted setting in which there is a fixed domain over which nulls are interpreted. In other words, when there is a fixed domain A such that the incomplete databases used in the reductions are of the form D = (T , dom) and dom(⊥) ⊆ A, for each null ⊥ of T .

The complexity on the non-uniform case

In this section, we study the complexity of the problems #Val(q) and #Val Cd (q), providing dichotomy results in both cases. We start by proving the #P-hardness results needed for these dichotomies. We first show that #Val(R(x, x)) is #P-hard by actually proving that hardness holds already in the uniform case. Proposition 3.4. #Val u (R(x, x)) is #P-hard and, hence, #Val(R(x, x)) is also #P-hard. This holds even in the restricted setting in which all nulls are interpreted over the same fixed domain {1, 2, 3}.

Proof. We reduce from the problem of counting the number of 3-colorings of a graph G = (V , E), which is #P-hard [START_REF] Jaeger | On the computational complexity of the Jones and Tutte polynomials[END_REF]. For every node v ∈ V we have a null ⊥ v , and for every edge {u, v} ∈ E we have the facts R(⊥ v , ⊥ u ) and R(⊥ u , ⊥ v ). The domain of the nulls is {1, 2, 3}. It is then clear that the number of valuations of the constructed database that do not satisfy R(x, x) is exactly the number of 3-colorings of G. Since the total number of valuations can be computed in PTIME, this concludes the reduction. □

The next pattern that we consider is R(x) ∧ S(x). This time, we can show #P-hardness of the problem even for Codd databases. Proposition 3.5. #Val Cd (R(x) ∧ S(x)) is #P-hard.

Already with Propositions 3.5 and 3.4, we have all the relevant hard patterns for the non-uniform setting. We start by proving our dichotomy result for naïve tables, which is our default case. Theorem 3.6 (dichotomy). Let q be an sjfBCQ. If R(x, x) or R(x) ∧ S(x) is a pattern of q, then #Val(q) is #P-complete. Otherwise, #Val(q) is in FP.

Proof. The #P-hardness part of the claim follows from the last two propositions and from Lemma 3.3. We explain why the problems are in #P right after this proof. When q does not have any of these two patterns then all variables have exactly one occurrence in q. This implies that every valuation ν of D is such that ν (D) satisfies q (except when one relation is empty, in which case the result is simply zero). We can obviously compute the total number of valuations in FP by simply multiplying the sizes of the domains of every null in D. □

Notice that in this theorem, the membership of #Val(q) in #P can be established by considering a nondeterministic Turing Machine M that, with input a non-uniform incomplete database D, guesses a valuation ν of D and verifies whether ν(D) satisfies q. This machine works in polynomial time as we can verify whether ν (D) satisfies q in polynomial time (since q is a fixed FO query). Then given that #Val(q)(D) is equal to the number of accepting runs of M with input D, we conclude that #Val(q) is in #P. Obviously, the same idea shows that #Val Cd (q) is in #P. But with this restriction we obtain more tratable cases, as shown by the following dichotomy result. Theorem 3.7 (dichotomy). Let q be an sjfBCQ. If R(x) ∧ S(x) is a pattern of q, then #Val Cd (q) is #P-complete. Otherwise, #Val Cd (q) is in FP.

Proof. We only need to prove the tractability claim, since hardness follows from Proposition 3.5 and Lemma 3.3. We will assume without loss of generality that D contains no constants, as we can introduce a fresh null with domain {c} for every constant c appearing in D, and the result is again a Codd table, and this does not change the output of the problem. Let q be R 1 ( x1 ) ∧ . . . ∧ R m ( xm ). Observe that since q does not have R(x) ∧S(x) as a pattern then any two atoms cannot have a variable in common. But then, since D is a Codd table we have

#Val Cd (q)(D) = m i=1 #Val Cd (R i ( xi ))(D(R i )).
Hence it is enough to show how to compute #Val Cd (R i ( xi ))(D(R i )) for every 1 ⩽ i ⩽ m. Let t1 , . . . , tn be the tuples of D(R i ). Let us write ρ( tj ) for the number of valuations of the nulls appearing in tj that do not match xi . Clearly, #Val

Cd (R i ( xi ))(D(R i )) = ⊥ appears in D(R i ) |dom(⊥)| -n j=1 ρ( tj )
, so we only have to show how to compute ρ( tj ) for 1 ⩽ j ⩽ n. Since we can easily compute the total number of valuations of tj , it is enough to show how to compute the number of valuations of tj that match xi . For every variable x that appears in xi , compute the size of the intersection of the corresponding nulls in tj , and denote it s x . Then the number of valuations of tj that match xi is simply x appears in xi s x . This concludes the proof. □ At this stage, we have completed the first column of Table 1, and we also know that R(x, x) is a hard pattern in the uniform setting for naïve tables (but not for Codd tables, by Theorem 3.7). In the next section, we treat the uniform setting.

The complexity on the uniform case

We start our investigation with the case of naïve tables. In Proposition 3.4, we already showed that #Val u (R(x, x)) is #P-hard. In the following proposition, we identify two other simple queries for which this problem is still intractable. Proposition 3.8. #Val u (R(x)∧S(x, y)∧T (y)) and #Val u (R(x, y)∧ S(x, y)) are both #P-hard. This holds even in the restricted setting in which all nulls are interpreted over the same fixed domain {0, 1}.

Proof. We reduce both problems from the problem of counting the number of independent sets in a graph (denoted by #IS), which is #P-complete [START_REF] Scott | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF]. We start with #Val u (R(x) ∧ S(x, y) ∧ T (y)). Let q = R(x) ∧ S(x, y) ∧T (y) and G = (V , E) be a graph. Then we define an incomplete database D as follows. For every node v ∈ V , we have a null ⊥ v , and the uniform domain is {0, 1}. For every edge {u, v} ∈ E, we have facts S(⊥ u , ⊥ v ) and S(⊥ v , ⊥ u ) in D. Finally, we have facts R(1) and T (1) in D. For a valuation ν of the nulls, consider the corresponding subset S ν of nodes of G, given by S ν = {t ∈ V | ν (⊥ t ) = 1}. This is a bijection between the valuations of the database and the node subsets of G. Moreover, we have that ν (D) ̸ |= q if and only if S ν is an independent set of G. Since the total number of valuations of D is 2 |V | , we have that the number of independent sets of G is equal to 2 |V | -#Val u (q)(D). Hence, we conclude that #IS ⩽ p T #Val u (q). The idea is similar for #Val u (R(x, y) ∧ S(x, y)): we encode the graph with the relation S in the same way, and this time we add the fact R(1, 1). □

As shown in the following result, it turns out that the three aforementioned patterns are enough to fully characterize the complexity of counting valuations for naïve tables in the uniform setting. Theorem 3.9 (dichotomy). Let q be an sjfBCQ. If R(x, x) or R(x)∧S(x, y)∧T (y) or R(x, y)∧S(x, y) is a pattern of q, then #Val u (q) is #P-complete. Otherwise, #Val u (q) is in FP.

The #P-completeness part of the claim follows directly from what we have proved already. Here, the most challenging part of the proof is actually the tractability part. We only present a simple example to give an idea of the proof technique, and defer the full proof to Appendix A.3. We will use the following definition. Given n, m ∈ N, let us write surj n→m for the number of surjective functions from {1, . . . , n} to {1, . . . , m}. By an inclusion-exclusion argument, one can show that surj n→m = m-1 i=0 (-1) i m i (m -i) n (for instance, see [START_REF] Adam | Number of surjective functions[END_REF]). It is clear that this can be computed in FP, when n and m are given in unary.

Example 3.10. Let q be the sjfBCQ R(x) ∧ S(x), and D be an incomplete database over relations R, S. Notice that q does not have any of the patterns mentioned in Theorem 3.9. We will show that #Val u (q) is in FP. Since q contains only two unary atoms we can also assume without loss of generality that the input D is a Codd table (otherwise all valuations are satisfying).

Since we can compute in FP the total number of valuations, it is enough to show how to compute the number of valuations of D that do not satisfy q. Let dom be the uniform domain, d be its size, n R (resp., n S ) be the number of nulls in D(R) (resp., in D(S)) and C R (resp., C S ) be the set of constants occurring in D(R) (resp., in D(S)), with c R (resp., c S ) its size. We can assume without loss of generality that C R ∩ C S = ∅, as otherwise all the valuations are satisfying, and this is computable in PTIME. Furthermore, we can also assume that C R ∪ C S ⊆ dom, since we can remove the constants that are not in dom, as these can never match.

Let M := dom \ (C R ∪ C S ), and m its size (i.e., with our assumptions we have m = dc R -c S ). Fix some subsets M ′ ⊆ M and R ′ ⊆ C R . The quantity surj n R →|M ′ |+|R ′ | then counts the number of valuations of the nulls of D(R) that span exactly M ′ ∪ R ′ . Moreover, letting ν R be a valuation of the nulls of D(R) that spans exactly M ′ ∪R ′ , the quantity (d -c R -|M ′ |) n S is the number of ways to extend ν R into a valuation ν of all the nulls of D so that ν (D) ̸ |= q: indeed, every null of D(S) can take any value in dom \ (C R ∪ M ′ ). The number of valuations of D that do not satisfy q is then (keeping in mind that a null in D(R) cannot take a value in C S ):

M ′ ⊆M R ′ ⊆C R surj n R →|M ′ |+ |R ′ | × (d -c R -|M ′ |) n S
and since the summands only depends on the sizes of M ′ and R ′ , this is equal to

0⩽m ′ ⩽m 0⩽r ′ ⩽c R m m ′ c R r ′ surj n R →m ′ +r ′ × (d -c R -m ′ ) n S
This last expression can clearly be computed in PTIME. 2□

We conclude this section by turning our attention to the case of Codd tables. Notice that none of the results proved so far provides a hard pattern in this case. We identify in the following proposition a simple query for which the problem is intractable.

Proposition 3.11. #Val u Cd (R(x) ∧ S(x, y) ∧ T (y)) is #P-hard.
In Proposition 3.8, we proved that #Val u (R(x) ∧ S(x, y) ∧T (y)) is #P-hard in the general case where naïve tables are allowed. Hence, Proposition 3.8 was in fact a consequence of Proposition 3.11, where only Codd tables are allowed. However, we decided to provide a separate proof for Proposition 3.8, because this result includes another intractable case, and both cases in Proposition 3.8 can be established via a simple reduction from counting independent sets. By contrast, Proposition 3.11 requires of a more complicated proof (we reduce from #IS on bipartite graphs and use a Turing reduction with ( n /2 + 1) 2 calls to the oracle, where n is the number of nodes of the input graph, to form a system of linear equations which we then invert to recover the number of independent sets).

Up to this point, we have not been able to prove that when an sjfBCQ q does not contain R(x) ∧S(x, y) ∧T (y) as a pattern, it holds that #Val u Cd (q) is in FP. Thus, the possibility of having a dichotomy in this case is left as a problem for future research. Nevertheless, we can still observe that restricting to Codd tables simplifies the problem of counting valuations in the non-uniform setting. Indeed, considering the query R(x, x), counting valuations is #P-hard for naïve tables, while it is in FP for Codd tables by Theorem 3.7.

DICHOTOMIES FOR COUNTING COMPLETIONS

In this section, we study the complexity of the problems of counting completions satisfying an sjfBCQ q, in the four cases that can be obtained by considering naïve or Codd tables and non-uniform or uniform domains. We will again use the notion of pattern as introduced in Definition 3.1. Our first step is to show that Lemma 3.3, which we used in the last section for the problems or counting valuations, extends to the problems of counting completions.

Lemma 4.1. Let q, q ′ be sjfBCQs such that q ′ is a pattern of q. Then we have that #Comp(q ′ ) ⩽ p par #Comp(q) and #Comp u (q ′ ) ⩽ p par #Comp u (q). Moreover, the same results hold if we restrict to the case of Codd tables.

We will then follow the same general strategy as in the last section, i.e., prove hardness for some simple patterns and combine these with Lemma 4.1 and tractability proofs to obtain dichotomies. Our findings are summarized in the last two columns of Table 1 in the introduction. We start in Section 4.1 with the non-uniform cases and continue in Section 4.2 with the uniform cases. Again, we explicitly state when a #P-hardness result holds even in the restricted setting in which there is a fixed domain over which nulls are interpreted.

The complexity on the non-uniform case

Here, we study the complexity of the problems #Comp(q) and #Comp Cd (q), providing dichotomy results in both cases. In fact, it turns out that these problems are #P-hard for all sjfBCQs. To prove this, it is enough to show that the problem #Comp Cd (R(x)) is hard, that is, even counting the completions of a single unary table is #P-hard in the non-uniform setting.

Proposition 4.2. #Comp Cd (R(x)) is #P-hard.
Proof. We provide a polynomial-time parsimonious reduction from the problem of counting the vertex covers of a graph, which we denote by #VC. Let G = (V , E) be a graph. We construct a Codd table D using a single unary relation R such that the number of completions of D equals the number of vertex covers of G. For every edge e = {u, v} of G, we have one null ⊥ e with dom(⊥ e ) = {u, v} and the fact R(⊥ e ). Let a be a fresh constant. For every node u ∈ V we have a null ⊥ u with dom(⊥ u ) = {u, a} and the fact R(⊥ u ). Last, we add the fact R(a). We now show that the number of completions of D equals the number of vertex covers of G.

Let VC(G) be the set of vertex covers of G. For a valuation ν of D, define the set

S ν := {u ∈ V | R(u) ∈ D}. Since the fact R(a) is in every completion of D, it is clear that the number of com- pletions of D is equal to |{S ν | ν is a valuation of D}|. We claim that VC(G) = {S ν | ν is a valuation of D}, which shows that the reduction works. (⊆) Let C ∈ VC(G)
, and let us show that there exists a valuation ν of D such that S ν = C. For a null of the form ⊥ e with e = {u, v} ∈ E, assuming wlog that u ∈ C, we define ν (⊥ e ) to be u. For a null of the form ⊥ u with u ∈ V , we define ν (⊥ u ) to be u if u ∈ C and a otherwise. It is then clear that S ν = C. (⊇) Let ν be a valuation of D, and let us show that S ν is a vertex cover. Assume by contradiction that there is an edge e = {u, v} such that e ∩ S ν = ∅. By definition of D, we must have ν (⊥ e ) ∈ {u, v}, so that one of u or v must be in S ν , hence a contradiction. Therefore, we conclude that #VC ⩽

p par #Comp Cd (R(x)). □
Recall from Section 2 that, to avoid trivialities, we assume all sjfBCQs to contain at least one atom and that the arity of every atom is ⩾ 1 (that is, all atoms have at least one variable). Using Lemma 3.3, this allows us to obtain the following dichotomy result. Theorem 4.3 (Dichotomy). For every sjfBCQ q, it holds that #Comp(q) and #Comp Cd (q) are #P-hard.

Notice here that we do not claim membership in #P; in fact, we will come back to this issue in Section 6 to show that this is unlikely to be true for naïve tables. However, we can still show that membership in #P holds for Codd tables. We then obtain: Theorem 4.4 (Dichotomy). For every sjfBCQ q, the problem #Comp Cd (q) is #P-complete.

The complexity on the uniform case

We now investigate the complexity of #Comp u (q) and #Comp u Cd (q). Recall that in the non-uniform case, even counting the completions of a single unary table is a #P-hard problem. This no longer holds in the uniform case, as we will show that #Comp u (q) is in FP for every sjfBCQ that is defined over a schema consisting exclusively of unary relation symbols.

Such a positive result, however, cannot be extended much further. In fact, we show next that R(x, x) and R(x, y) are hard patterns (and, thus, we also conclude that the problem of counting the completions of a single binary table is a #P-hard problem). Moreover, #P-hardness holds even if restricted to one of the following settings: Proof. We only present the proof of (a) here. The proof of (b) requires more work and can be found in Appendix B.4. We reduce from #IS, the problem of counting the number of independent sets of a graph.

Let G = (V , E) be a graph. We will construct an incomplete database D containing a single binary predicate R such that each completion of D satisfies R(x, x) and the number of completions of D is 2 |V | + #IS(G), thus establishing hardness for the two queries. For every node u ∈ V , we have a null ⊥ u with dom(⊥ u ) = {0, 1}. We then construct the naïve table D as follows:

• for every node u ∈ V we add to D the fact R(u, ⊥ u );

• then for every edge {u, v} ∈ E, we add the facts R(⊥ u , ⊥ v ) and R(⊥ v , ⊥ u ) to D; and • last, we add the facts R(0, 0), R(0, 1), R(1, 0), and R(⊥, ⊥),

where ⊥ is a fresh null. It is clear that every completion of D satisfies R(x, x).

Let us now count the number of completions of D. First, we observe that, thanks to the facts of the form R(u, ⊥ u ), for u ∈ V , for every two valuations ν, ν ′ that do not assign the same value to the nulls of the form ⊥ u , it is the case that ν (D) ν (D ′ ). We then partition the completions of D into those that contain the fact R(1, 1), and those that do not contain R(1, 1). Because of the facts of the form R(u, ⊥ u ), for u ∈ V , and thanks to the fact R(⊥, ⊥) which becomes R(1, 1) when we assign 1 to ⊥, there are exactly 2 |V | completions of D that contain R(1, 1). Moreover, it is easy to see that there are #IS(G) valuations ν of D that assign 0 to ⊥ and that yield a completion not containing R(1, 1). Indeed, one can check that a valuation of D that assigns 0 to ⊥ yields a completion not containing R(1, 1) if and only if the set {u ∈ V | ν(⊥ u ) = 1} is an independent set of G. Therefore, we conclude that #IS ⩽ p T #Comp u (q), where q can be R(x, x) or R(x, y). □

The patterns in Proposition 4.5 suffice to characterize the complexity of #Comp u (q) and #Comp u Cd (q). Theorem 4.6 (Dichotomy). Let q be an sjfBCQ. If R(x, x) or R(x, y) is a pattern of q, then #Comp u (q) and #Comp u Cd (q) are #Phard. Otherwise, these problems are in FP.

The proof of the tractability part of this theorem is combinatorial and very technical, and we present it in Appendix B.6, where we also give several examples to provide the main intuitions. Note that, as in the last section, we do not claim membership in #P. However, and also as in the last section, we can show that these problems are in #P for Codd tables, which allows us to obtain our last dichotomy for exact counting. Theorem 4.7 (Dichotomy). Let q be an sjfBCQ. If R(x, x) or R(x, y) is a pattern of q, then #Comp u Cd (q) is #P-complete. Otherwise, this problem is in FP.

APPROXIMATING THE NUMBERS OF VALUATIONS AND COMPLETIONS

As we saw in the previous sections, counting valuations and completions of an incomplete database are usually intractable problems.

However, this does not necessarily rule out the existence of efficient approximation algorithms for such counting problems, in particular if some source of randomization is allowed. In this section, we investigate this question by focusing on the well-known notion of Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for counting problems [START_REF] Mark R Jerrum | Random generation of combinatorial structures from a uniform distribution[END_REF]. Formally, let Σ be a finite alphabet and f : Σ * → N be a counting problem. Then f is said to have an FPRAS if there is a randomized algorithm A : Σ * × (0, 1) → N and a polynomial p(u, v) such that, given x ∈ Σ * and ε ∈ (0, 1), algorithm A runs in time p(|x |, 1 /ε) and satisfies the following condition:

Pr | f (x) -A(x, ε)| ⩽ ε f (x) ⩾ 3 4
.

Observe that the property of having an FPRAS is closed under polynomial-time parsimonious reductions, that is, if we have an FPRAS for a counting problem A and for counting problem B we have that B ⩽ p par A, then we also have an FPRAS for B. In the following sections, we investigate the existence of FPRAS for the problems of counting valuations and completions of an incomplete database. We first deal with counting valuations in Section 5.1, where we show a general condition under which this problem has an FPRAS (which will apply, in particular, to all Boolean conjunctive queries). Then, in Section 5.2, we show that the situation is quite different for counting completions, as in most cases this problem does not admit an FPRAS.

Approximating the number of valuations

To prove the main result of this section, we need to consider the counting complexity class SpanL [START_REF] Álvarez | A very hard log-space counting class[END_REF]. Given a finite alphabet Σ, an NL-transducer M over Σ is a nondeterministic Turing Machine with input and output alphabet Σ, a read-only input tape, a write-only output tape (where the head is always moved to the right once a symbol in Σ is written in it, so that the output cannot be read by M), and a work-tape of which, on input x, only the first c • log(|x |) cells can be used for a fixed constant c > 0 (so that the space used by M is logarithmic). Moreover, y ∈ Σ * is said to be an output of M with input x, if there exists an accepting run of M with input x such that y is the string in the output tape when M halts. Then a function f : Σ * → N is said to be in SpanL if there exists an NL-transducer M over Σ such that for every x ∈ Σ * , the value f (x) is equal to the number of distinct outputs of M with input x. In [START_REF] Álvarez | A very hard log-space counting class[END_REF], it was proved that SpanL ⊆ #P, and also that this inclusion is strict unless NL = NP.

Very recently, the authors of [START_REF] Arenas | Efficient logspace classes for enumeration, counting, and uniform generation[END_REF] have shown that every problem in SpanL has an FPRAS. By using this result, we can give a general condition on a Boolean query q under which #Val(q) has an FPRAS, as this condition ensures that #Val(q) is in SpanL. More precisely, a Boolean query q is said to be monotone if for every pair of (complete) databases D, D ′ such that D ⊆ D ′ , if D |= q, then D ′ |= q. Moreover, q is said to have bounded minimal models if there exists a constant C q (that depends only on q) satisfying that for every (complete) database D, if D |= q, then there exists D ′ ⊆ D such that D ′ |= q and the number of facts in D ′ is at most C q . Finally, the model checking problem for q, denoted by MC(q), is the problem of deciding, given a (complete) database D, whether D |= q. Then q is said to have a model checking in a complexity class C if MC(q) ∈ C. With this terminology, we can state the main result of this section. Proposition 5.2. Assume that a Boolean query q is monotone, has model checking in nondeterministic linear space, and has bounded minimal models. Then #Val(q) is in SpanL.

In particular, given that a union of Boolean of conjunctive queries satisfies the three properties of the previous proposition, we conclude from Theorem 5.1 that #Val(q) can be efficiently approximated by using a randomized algorithm if q is a union of BCQs. 3Corollary 5.3. If q is a union of BCQs, then #Val(q) has an FPRAS. Hence, for such a query q, we have that each one of the problems #Val u (q), #Val Cd (q), #Val u Cd (q) admits an FPRAS. We prove in the next section that the good properties stated in Proposition 5.2 do not hold for counting completions.

Approximating the number of completions

In this section, we prove that the problem of counting completions of an incomplete database is much harder in terms of approximation than the problem of counting valuations. In this investigation, two randomized complexity classes play a fundamental role. Recall that RP is the class of decision problems L for which there exists a polynomial-time probabilistic Turing Machine M such that: (a) if x ∈ L, then M accepts with probability at least 3 /4; and (b) if x L, then M does not accept x. Moreover, BPP is defined exactly as RP but with condition (b) replaced by: (b') if x L, then M accepts with probability at most 1 /4. Thus, BPP is defined as RP but allowing errors for both the elements that are and are not in L. It is easy to see that RP ⊆ BPP. Besides, it is known that RP ⊆ NP, and this inclusion is widely believed to be strict. Finally, it is not known whether BPP ⊆ NP or NP ⊆ BPP, but it is widely believed that NP is not included in BPP.

The non-uniform case. Recall that #IS is the problem of counting the number of independent sets of a graph. This problem will play a fundamental role when showing non-approximability of counting completions in the non-uniform case. More precisely, the following is known about the approximability of #IS. In the proof of Proposition 4.2, we considered the problem #VC of counting the number of vertex covers of a graph G = (V , E), and showed that #VC ⩽ p par #Comp Cd (R(x)). By observing that S ⊆ V is an independent set of G if and only if V \ S is a vertex cover of G, we can conclude that #IS(G) = #VC(G) and, thus, the same reduction from the proof of Proposition 4.2 establishes that #IS ⩽ p par #Comp Cd (R(x)). Therefore, from the fact that the reduction in Lemma 4.1 is also parsimonious and preserves the property of being a Codd table, and the fact that the existence of an FPRAS is closed under polynomial-time parsimonious reductions, we obtain the following result from Theorem 5.4. Theorem 5.5 (Dichotomy). For every sjfBCQ q, it holds that #Comp Cd (q) does not admit an FPRAS unless NP = RP (and, hence, the same holds for #Comp(q)).

The uniform case. Recall that from Theorem 4.6, we know that if an sjfBCQ q contains neither R(x, x) nor R(x, y) as a pattern, then #Comp u (q) is in FP. Thus, the question to answer in this section is whether #Comp u (q) and #Comp u Cd (q) can be efficiently approximated if q contains any of these two patterns. For the case of naïve tables, we will give a negative answer to this question. Notice that, this time, our reduction from #IS in Proposition 4.5 is not parsimonious, so we cannot use Theorem 5.4 as we did for the non-uniform case. Instead, we will rely on the following wellknown fact: if there exists a BPP algorithm for a problem that is NP-complete, then NP ⊆ BPP, which implies that NP = RP [START_REF] Ker | Some observations on the probabilistic algorithms and NP-hard problems[END_REF]. Proposition 5.6. Neither #Comp u (R(x, x)) nor #Comp u (R(x, y)) admits an FPRAS unless NP = RP. This holds even in the restricted setting in which all nulls are interpreted over the same fixed domain {1, 2, 3}.

Proof. Let G = (V , E) be a graph. First, we explain how to construct an incomplete database D containing a single binary relation R, with uniform domain {1, 2, 3}, and such that (a) all completions of D satisfy both queries; (b) if G is 3-colorable then D has 8 completions; and (c) if G is not 3-colorable then D has 7 completions. For every node u ∈ V we have a null ⊥ u . The database D consists of the following three disjoint sets of facts:

• For every edge {u, v} ∈ E, we have the two facts R(⊥ u , ⊥ v ) and R(⊥ v , ⊥ u ); we call these the encoding facts. • We have the facts R(1, 2), R(2, 1), R(2, 3), R(3, 2), R(1, 3), and R(3, 1); we call these the triangle facts;

• We have six fresh nulls ⊥ 1 , ⊥ ′ 1 , ⊥ 2 , ⊥ ′ 2 , ⊥ 3 , ⊥ ′ 3 and the facts R(⊥ i , ⊥ ′ i ) and R(⊥ ′ i , ⊥ i ) for 1 ⩽ i ⩽ 3;
we call these the auxiliary facts;

• Last, we have a fact R(c, c), where c is a fresh constant.

It is clear that all the completions of D satisfy both queries, so we only need to prove (b) and (c). Observe that a candidate completion of D can be equivalently seen as an undirected graph, possibly with self-loops, over the nodes {1, 2, 3} (we omit the fact R(c, c) since it is in every completion) and that contains the triangle. Thanks to the auxiliary facts, it is easy to show that all such graphs with at least one self-loop can be obtained as a completion of D. For instance, the completion that is triangle with a self-loop only on 1 can be obtained by assigning 1 to all the nulls in the coding facts, assigning 1 to ⊥ 1 , ⊥ ′ 1 , ⊥ 2 and ⊥ 3 and assigning 2 to ⊥ ′ 2 and ⊥ ′ 3 . There are 7 such completions. Then, the completion whose graph is the triangle with no self-loops is obtainable if and only if G is 3colorable (we assign a 3-coloring to the nulls in the coding facts, and assign 1 to ⊥ i and 2 to ⊥ ′ i for every i ∈ {1, 2, 3}). This indeed proves (b) and (c). Next, we show that any FRPAS with ε = 1 /16 for counting the number of completions of D would yield a BPP algorithm to solve 3-colorability, thus implying NP = RP since 3-colorability is an NP-complete problem.

Let A be an FPRAS for #Comp u (q), with q being R(x, x) or R(x, y), and let us define a BPP algorithm B for 3-colorability using A. On input graph G, algorithm B does the following. First, it computes in polynomial time the naïve □

By observing again that the reduction in Lemma 4.1 is parsimonious, and that the existence of an FPRAS is closed under parsimonious reductions, we obtain that #Comp u (q) cannot be efficiently approximated if q contains R(x, x) or R(x, y) as a pattern. Theorem 5.7 (Dichotomy). Let q be an sjfBCQ. If q has R(x, x) or R(x, y) as a pattern, then #Comp u (q) does not admit an FPRAS unless NP = RP. Otherwise, this problem is in FP (by Theorem 4.6).

Up until now, we do not know if this result still holds for Codd tables, or if it is possible to design an FPRAS in this setting. We leave this question open for future research.

ON THE GENERAL LANDSCAPE:

BEYOND #P Recall that, when studying the complexity of counting completions for sjfBCQs in Section 4, we did not show that these problems are in #P for naïve tables. The goal of this section is then twofold. First, we want to give formal evidence that we indeed could not show membership in #P in Section 4. Second, we want to identify a counting complexity class that is more appropriate to describe the complexity of #Comp(q), but in a more general setting which is not based on some syntactic restrictions imposed on q. More precisely, for the second goal, we consider the complexity of the model checking problem MC(q) for q, which is defined in Section 5.1 as the problem of deciding, given a (complete) database D, whether D |= q.

In this section, all upper bounds will be proved for the most general scenario of non-uniform naïve tables, while all lower bounds will be proved for the most restricted scenario of uniform naïve tables with the fixed domain {0, 1}.

To meet our first goal, we need to define the complexity class SPP introduced in [START_REF] Fenner | Gap-definable counting classes[END_REF][START_REF] Gupta | The power of witness reduction[END_REF][START_REF] Ogiwara | A complexity theory for feasible closure properties[END_REF]. Given a nondeterministic Turing Machine M and a string x, let accept M (x) (resp., reject M (x)) be the number of accepting (resp., rejecting) runs of M with input x, and let gap M (x) = accept M (x)reject M (x). Then a language L is said to be in SPP [START_REF] Fenner | Gap-definable counting classes[END_REF] if there exists a polynomial-time nondeterministic Turing Machine M such that: (a) if x ∈ L, then gap M (x) = 1; and (b) if x L, then gap M (x) = 0. In this way, SPP is the smallest class that can be defined in terms of the gap function gap M . It is conjectured that NP ⊈ SPP as, for example, for every known polynomial-time nondeterministic Turing Machine M accepting an NP-complete problem, the function gap M is not bounded. In the following proposition, we show how this conjecture helps us to reach our first goal. Proposition 6.1. There exists an sjfBCQ q such that #Comp u (q) is not in #P unless NP ⊆ SPP.

To meet our second goal, we need to introduce one last counting complexity class. The class SpanP [START_REF] Köbler | On counting and approximation[END_REF] is defined exactly as the class SpanL introduced in Section 5.1, but considering polynomialtime nondeterministic Turing machines with output, instead of logarithmic-space nondeterministic Turing machines with output. It is straightforward to prove that #P ⊆ SpanP. Besides, it is known that #P = SpanP if and only if NP = UP [START_REF] Köbler | On counting and approximation[END_REF]. 4 Therefore, it is widely believed that #P is properly included in SpanP. The following easy observation can be seen as a first hint that SpanP is a good alternative to describe the complexity of counting completions. Observation 6.2. If q is a Boolean query such that MC(q) is in P, then #Comp(q) is in SpanP.

Notice that this result applies to all sjfBCQs and, more generally, to all FO Boolean queries. In fact, this results applies to even more expressive query languages such as Datalog [START_REF] Abiteboul | Foundations of databases[END_REF]. More surprisingly, in the following theorem we show that #Comp u (q) can be SpanPcomplete for an FO query q and, in fact, already for the negation of an sjfBCQ. Theorem 6.3. There exists an sjfBCQ q such that #Comp u (¬q) is SpanP-complete under polynomial-time parsimonious reductions.

This theorem gives evidence that SpanP is the right class to describe the complexity of counting completions for FO queries (and even for queries with model checking in polynomial time). It is important to notice that SpanP-hardness is proved in Theorem 6.3 by considering parsimonious reductions. This is a delicate issue because from the main result in [START_REF] Toda | Polynomial time 1-Turing reductions from #PH to #P[END_REF], it is possible to conclude that every counting problem that is #P-hard (even under polynomial-time parsimonious reductions) is also SpanP-hard under polynomial-time Turing reductions, so a more restrictive notion of reduction has to be used when proving that a counting problem is SpanP-hard [START_REF] Köbler | On counting and approximation[END_REF].

We conclude this section by considering an even more general scenario where queries have model checking in NP. Interestingly, in this case SpanP is again the right class to describe the complexity not only of counting completions, but also of counting valuations. Theorem 6.4. If q is a Boolean query with MC(q) ∈ NP, then both #Val(q) and #Comp(q) are in SpanP. Moreover, there exists such a Boolean query q for which #Val u (q) is SpanP-complete under polynomial-time parsimonious reductions (and for #Comp u (q), we can even take q to be the negation of an sjfBCQ, hence with model checking in P, as given by Theorem 6.3).

RELATED WORK

There are two main lines of work that must be compared to what we do in this paper. In both cases the goal is to go beyond the traditional notion of certain answers that so far had been used almost exclusively to deal with query answering over uncertain data. We discuss them here, explain how they relate to our problems and what are the fundamental differences.

Best answers and 0-1 laws for incomplete databases. Libkin has recently introduced a framework that can be used to measure the certainty with which a Boolean query holds on an incomplete database, and also to compare query answers (for a non-Boolean query) [START_REF] Libkin | Certain answers meet zero-one laws[END_REF]. For a Boolean query q, incomplete database D, and integer k, he defines the quantity µ k (q, D) as

|Supp k (q, D) | |V k (D) | , where V k (D)
denotes the set of valuations of D with domain {1, . . . , k}, and Supp k (q, D) denotes the set of valuations ν ∈ V k (D) such that ν (D) |= q; hence, µ k (q, D) represents the relative frequency of valuations ν in {1, . . . , k} for which the query is satisfied. He then shows that, for a very large class of queries (namely, generic queries), the value µ k (q, d) always tends to 0 or 1 as k tends to infinity (and the same results holds when considering completions instead of valuations). This means that, intuitively, over an infinite domain the query q is either almost certainly true or almost certainly false.

He also studies the complexity of finding best answers for a non Boolean query q. As mentioned in the introduction, a tuple a is a better answer than another tuple b when for every valuation ν of D, if we have b ∈ q(ν (d)) then we also have b ∈ q(ν (d)). A best answer is then an answer such that there is no other answer strictly better than it (under inclusion of the sets of satisfying valuations). He studies the complexity of comparing answers under this semantics, and that of computing the set of best answers (see also [START_REF] Gheerbrant | Best answers over incomplete data : Complexity and first-order rewritings[END_REF]).

There are several crucial differences between this previous work and ours. First, Libkin does not study the complexity of computing µ k (q, d). We do this under the name #Val u (q); moreover, we also study the setting in which the domains are not uniform. Second, knowing that a tuple is the best answer might not tell us anything about the size of its "support", i.e., the number of valuations that support it. In particular, a best answer is not necessarily an answer which has the biggest support. Finally, under the semantics of better answers it does not matter if we look at the completions or at the valuations (i.e., a tuple is a best answer with respect to inclusion of valuations iff it is the best answer with respect to completions); while we have shown that it does matter for counting problems.

Counting problems for probabilistic databases and consistent query answering. Remarkably, counting problems have received considerable attention in other database scenarios where uncertainty issues appear. As mentioned in the introduction, this includes the settings of probabilistic databases and inconsistent databases. In the former case, uncertainty is represented as a probability distribution on the possible states of the data [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF][START_REF] Suciu | Probabilistic databases[END_REF]. There, query answering amounts to computing a weighted sum of the probabilities of the possible states of the data that satisfy a query q. We call this problem Prob(q). In the case of inconsistent databases, we are given a set Σ of constraints and a database D that does not necessarily satisfy Σ; cf. [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF][START_REF] Bertossi | Database repairing and consistent query answering[END_REF][START_REF] Bertossi | Database repairs and consistent query answering: Origins and further developments[END_REF]. Then the task is to reason about the set of all repairs of D with respect to Σ [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF]. In our context, this means that one wants to count the number of repairs of D with respect to Σ that satisfy a given query q. When q and Σ are fixed, we call this problem #Repairs(q, Σ).

Both Prob(q) and #Repairs(q, Σ) have been intensively studied already. To start with, counting complexity dichotomies have been obtained for the problem #Repairs(q, Σ); e.g., [START_REF] Maslowski | A dichotomy in the complexity of counting database repairs[END_REF] gives a dichotomy for this problem when q is an sjfBCQ and σ consists of primary keys, and [START_REF] Maslowski | Counting database repairs that satisfy conjunctive queries with self-joins[END_REF] extends this result to CQs with self-joins but only for unary keys constraints. We also mention [START_REF] Calautti | Counting database repairs under primary Keys revisited[END_REF], where the problem of counting repairs such that a particular input tuple is in the result of the query on the repair is studied. A seemingly close counting problem for probabilistic databases is the problem Prob(q) over block independent disjoint (BIDs) databases. We do not define it formally here, but counting repairs under primary keys can be seen as a special case of this problem, where the tuples in a "block" all have the same probability, and where the sum of the probabilities sum to 1 (and in BIDs this sum is allowed to be < 1, meaning that a block can be completely erased). Dichotomies for this problem have been obtained in [START_REF] Dalvi | Queries and materialized views on probabilistic databases[END_REF] for sjfBCQs. Counting complexity dichotomies for other models of probabilistic databases also exist; e.g., for tuple-independent probabilistic databases in which each fact is assigned an independent probability of being part of the actual dataset. Interestingly, dichotomies in this case hold for arbitrary unions of BCQs, and thus not just for sjfBCQs [START_REF] Nilesh | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF].

In some cases, one can use a problem of the form #Repairs(q, Σ) (or Prob(q)) to show the hardness of a problem of the form #Val(q ′ ). For instance, we explain in Appendix E.1 how the #P-hardness of #Val Cd (R(x) ∧S(x)) can be deduced from that of #Repairs(R ′ (y, x) ∧ S ′ (z, x)). 5 In general however, the problems #Repairs(q, Σ) and Prob(q) seem to be unrelated to our problems, for the following reasons. First, in our setting the nulls can appear anywhere, so there is no notion of primary keys here; hence it seems unlikely that one can design a generic reduction from the problem of counting valuations/completions to the problem of counting repairs. In fact, it would perfectly make sense to study our counting problems where we add constraints such a functional dependencies. Second, in the BID and counting repairs problems, each "valuation" (repair) gives a different complete database, while in our case we have seen that this is not necessarily the case. In particular, problems of the form #Comp(q) have no analogues in these settings, whereas we have seen that they behave very differently in our setting.

Concerning approximation results, it is known that the problems #Repairs(q, Σ) and Prob(q) admit an FPRAS in some important settings. In particular, when q is a union of BCQs, this holds for #Repairs(q, Σ) when Σ is a set of primary keys [START_REF] Calautti | Counting database repairs under primary Keys revisited[END_REF], and for Prob(q) over BID and tuple-independent probabilistic databases [START_REF] Dalvi | Queries and materialized views on probabilistic databases[END_REF]. We observe here that this is reminescent of our Corollary 5.3, which shows that problems of the form #Val(q) have an FPRAS for every union of BCQs.

FINAL REMARKS

Our work aims to be a first step in the study of counting problems over incomplete databases. The main conclusion behind our results is that the counting problems studied in this paper are particularly hard from a computational point of view, especially when compared to more positive results obtained in other uncertainty scenarios; e.g., over probabilistic and inconsistent databases. As we have shown, a particularly difficult problem in our context is that of counting completions, even in the uniform setting where all nulls have the same domain. In fact, Proposition 4.5 shows that this problem is #P-hard even in very restricted scenarios, and Proposition 5.6 that it cannot be approximated by an FPRAS. It seems then that the only way in which one could try to tackle this problem is by developing suitable tractable heuristics, without provable quantitative guarantees, but that work sufficiently well in practical scenarios. An example of this could be developing algorithms that compute "under-approximations" for the number of completions of a naïve table satisfying a certain sjfBCQ q. Notice that a related approach has been proposed by Console et al. for constructing under-approximations of the set of certain answers by applying methods based on many-valued logics [START_REF] Console | Approximations and refinements of certain answers via many-valued logics[END_REF].

We plan to continue working on several interesting problems that are left open in this paper. First of all, we would like to pinpoint the complexity of #Comp(q) when q is an sjfBCQ; in particular, whether this problem is SpanP-complete for at least one such a query. We also want to study whether the non-existence of FPRAS for #Comp u (q) established in Proposition 5.6 continues to hold over Codd tables. We would also like to develop a more thorough understanding of the role of fixed domains in our dichotomies. In several cases, that we have explicitly stated, our lower bounds hold even if nulls in tables are interpreted over a fixed domain. Still, in some cases we do not know whether this holds. These include, e.g., Proposition 3.11, Proposition 4.2, and Proposition 4.5 for the case of Codd tables. Finally, it would also be interesting to study these counting problems under bag semantics (instead of the set semantics used in this paper), study counting problems for non-Boolean queries as in [START_REF] Gheerbrant | Best answers over incomplete data : Complexity and first-order rewritings[END_REF][START_REF] Libkin | Certain answers meet zero-one laws[END_REF], and consider arbitrary BCQs as opposed to only sjfBCQs.

A PROOFS FOR SECTION 3 (DICHOTOMIES FOR COUNTING VALUATIONS)

A.1 Proof of Lemma 3.3 Lemma 3.3. Let q, q ′ be sjfBCQs such that q ′ is a pattern of q. Then we have #Val(q ′ ) ⩽ p par #Val(q) and #Val u (q ′ ) ⩽ p par #Val u (q). Moreover, the same results hold if we restrict to Codd tables.

Proof. We only present the proof of #Val(q ′ ) ⩽ p par #Val(q), as the uniform case is identical. Let q be R 1 (x 1 ) ∧ . . . ∧ R m (x m ), and q ′ be R ′ j 1 (x ′ j 1 ) ∧ . . . ∧ R ′ j p (x ′ j p ), where 1 ⩽ j 1 < . . . < j p ⩽ m and each R j k has become R ′ j k (i.e., we either have

R j k = R ′ j k , or R j k has been renamed into R ′ j k
) and x ′ j k is obtained from x j k by deleting some variable occurrences but not all, and the other atoms have been deleted (we will assume without loss of generality that we did not reorder the variables in the atoms nor renamed variables by fresh ones, because this obviously does not change the complexity of the problems). Let D ′ be an incomplete database input of #Val(q ′ ). Let A be set of constants that are appearing in D ′ or are in a domain of some null occurring in D ′ . For 1 ⩽ k ⩽ p, we construct the relation

D(R j k ) from the relation D ′ (R ′ j k ).
Let us assume that x j k is the tuple (x 1 , . . . , x r ) (with some variables possibly being equal). We initialize D(R j k ) to be empty, and then for every tuple t

′ in D ′ (R ′ j k
) we add to D(R j k ) all the tuples t that can be obtained from t ′ in the following way for 1 ⩽ i ⩽ r : a) If x i is a variable occurrence that has not been deleted from x j k , then copy the element (constant or null) of t ′ corresponding to that variable occurrence to the i-th position of t; b) Otherwise, if x i is a variable occurrence that has been deleted from x j k , then fill the i-th position of t with every possible constant from A.

Then we construct the relations D(R i ) where R ′ i does not appear in q ′ (this can happen if we have deleted the atom R i (x i )) by filling it with every possible R i -fact over A. We leave the domains of all nulls unchanged. The whole construction can be performed in polynomial time (this uses the fact that q is assumed to be fixed, so that the arities of the relations mentioned in q are fixed). Since D and D ′ contain exactly the same set of nulls, the construction preserves the property of being a Codd table. Hence, it only remains to be checked that #Val(q ′ )(D ′ ) = #Val(q)(D), that is, that the reduction works and is indeed parsimonious. It is clear that the valuations of D ′ are exactly the same as the valuations of D (because they have the same sets of nulls). Hence it is enough to verify that for every valuation ν , we have ν (D ′ ) |= q ′ if and only if ν (D) |= q. Let h ′ be a homomorphism from q ′ to ν (D ′ ) witnessing that ν (D ′ ) |= q ′ (i.e., we have h ′ (q) ⊆ ν (D ′ )). Then h ′ can clearly be extended in the expected way into a homomorphism h from q to ν (D): this is in particular thanks to the fact that we filled the missing columns with every possible constant. Conversely, let h be a homomorphism from q to ν (D) witnessing that ν (D) |= q. Then the restriction h ′ of h to the variables occurring in q ′ is such that h(q ′ ) ⊆ ν (D ′ ), hence we have ν(D ′ ) |= q ′ . This concludes the proof. □

A.2 Proof of Proposition 3.5

In this section we prove the following.

Proposition 3.5. #Val Cd (R(x) ∧ S(x)) is #P-hard.

In the main text of this article, all graphs considered were undirected graphs with no self-loops an did not contain multiple edges between any two nodes. By contrast, the proofs in this section will rely on hardness results that use a more general notion of graph. We introduce here the notation that we will use in these proofs.

Multigraphs. By multigraph, we mean a finite undirected graph without self-loops, where two nodes can have multiple edges between them. Formally, a multigraph G = (V , E, λ) consists of a finite set V of nodes, a finite set E of edges, and a function λ that assigns to every edge e ∈ E a set λ(e) = {u, v} of two distinct nodes u, v ∈ V . We say that e is incident to u, and to v, and that u and v are adjacent (or are neighbors). Two edges e e ′ are parallel when λ(e) = λ(e ′ ). For a node u ∈ V , we write E(u) the set of edges that are incident to u, and the degree of u is |E(u)|. We say that G is d-regular (where d ∈ N ⩾1 ) when every node of G has degree d. A multigraph G is bipartite when its nodes can be partitioned in two sets A, B such that for every edge e of G we have that λ(e) contains one node in A and one node in B. We will often write such a bipartite multigraph as G = (A ⊔ B, E, λ). A bipartite multigraph G is a-b-regular when every node in A has degree a and every node in B has degree b. Observe that with these definitions, we can see a graph, as defined in Section 2, as a multigraph that does not contain parallel edges. We can then indeed write a graph simply as G = (V , E), and an edge e ∈ E as e = {u, v} (with u v).

We now explain how we prove Proposition 3.5. We execute the reduction in two steps, and we start from the problem that we call #Avoidance.

Definition A.1. Let G = (V , E, λ) be a multigraph. An assignment of G is a mapping µ : V → E such that for every node u we have µ(u) ∈ E(u). We say that µ is avoiding when there does not exist two (adjacent) nodes u, v such that µ(u) = µ(v). The problem #Avoidance takes as input a multigraph G and outputs the number of avoiding assignments of G.

Example A.2. Figure 2 represents a multigraph together with an avoiding assignment.

We explain how to obtain the following: Proposition A.3 (Implied by [START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF], see also [START_REF] Monet | A variant of #POSITIVE-2-DNF[END_REF]). The problem #Avoidance is #P-complete, and hardness holds even when restricted to 3-regular multigraphs.

Membership in #P is clear. We will show how hardness derives from the results of [START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF]. First, let us introduce what are called Holant problems: Definition A.4. Let G = (V , E, λ) be a multigraph. For a valuation of the edges ν : E → {0, 1} and a node t ∈ V , we write ν (E(t)) the multiset {{ν(e) | e ∈ E(t)}}. Given a multiset of bits B, the Hamming weight of B is the number of 1 bits in B. For each x 0 , . . . , x n ∈ {0, 1}, let [x 0 , . . . , x n ] denote the function that takes a multiset of n bits as input and outputs x i if the Hamming weight of those n bits is i.

Definition A.5. For every x 0 , x 1 , x 2 , y 0 , y 1 , y 2 , y 3 ∈ {0, 1}, the problem Holant([x 0 , x 1 , x 2 ]|[y 0 , y 1 , y 2 , y 3 ]) is the following: given a 2-3- regular bipartite multigraph G = (U ⊔ V , E, λ), compute the quantity ν :E→{0,1} u ∈U [x 0 , x 1 , x 2 ](ν (E(u)) × v ∈V [y 0 , y 1 , y 2 , y 3 ](ν (E(v))).
Holant problems provide a rich framework to express a lot of natural problems on 2-3-regular graphs (this was actually the motivation for introducing this framework), as the following examples illustrate: Example A.6. On 2-3-regular multigraphs, observe that:

• Counting perfect matchings is exactly the problem Holant([0, 1, 0]|[0, 1, 0, 0]); We will then reduce #Avoidance to the problem Holant([1, 1, 0]|[0, 1, 0, 0]), which is shown to be #P-hard in [START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF] using the tools of holographic reduction and interpolation: Proposition A.7 ( [START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF]). Holant([1, 1, 0]|[0, 1, 0, 0]) is #P-hard, even when restricted to 2-3-regular graphs.

•
Proof. The problem appears as hard for multigraphs in the table on page 10 of [START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF]. A careful inspection of the paper reveals that it is hard for graphs. □ Given a 2-3-regular bipartite graph G, we define the merging of G to be the multigraph obtained from G by merging the incident edges of every node of degree 2. Note that, because G is a graph and not a multigraph, the merging of G is indeed a multigraph, i.e., it does not contain self-loops. Furthermore, it is easy to see that this multigraph is 3-regular. We can now show Proposition A.3:

Proof of Proposition A.3. Let G be a 2-3-regular bipartite graph G input of Holant([1, 1, 0]|[0, 1, 0, 0]). Construct in polynomial time from G its merging G ′ ,
which is a 3-regular multigraph. Observe that the assignments of G ′ are in bijection with the edge subsets S of G such that every node of degree 3 in G is adjacent to exactly one edge in S. One can then easily see that the number of avoiding assignments of G ′ corresponds to the value of Holant([1, 1, 0]|[0, 1, 0, 0]) on G. □ However, in order to show hardness of #Val Cd (R(x) ∧ S(x)), we will actually need the hardness of #Avoidance on bipartite graphs. To the best of our knowledge this does not follow from related work, so we need to prove it here: Proposition A.8. The problem #Avoidance is #P-hard when restricted to 2-3-regular bipartite graphs.

Proof. We reduce from #Avoidance on 3-regular multigraphs, which is hard according to Proposition A.3. Let G = (V , E, λ) be a 3-regular multigraph. Let G ′ be the graph obtained from G by adding a node in the middle of every edge of G. Formally, the vertices of G ′ are V ⊔ {n e | e ∈ E} and its edges are e ∈E, λ(e)={u,v } {{u, n e }, {n e , v}}. It is clear that G ′ is a 2-3-regular bipartite graph. We claim that #Avoidance(G ′ ) = 2 |E |-|V | ×#Avoidance(G), which would complete the reduction. To prove this, we will use the following definition: letting µ be an assignment of G and µ ′ be an assignment of G ′ , we say that µ and µ ′ agree if for every v ∈ V , if µ ′ (v) = {v, n e } then we have ν (v) = e. We then show the following, which directly implies our claim:

(1) For every avoiding assignment µ of G, there are exactly 2 |E |-|V | avoiding assignments µ ′ of G ′ that agree with µ;

R 1 (x 1 , x 1 , y 1 , t 1 ) R 2 (x 1 , y 1 , t 2 ) x 1 , y 1 S 1 (x 2 , t 3 ) S 2 (x 2 , t 4 ) S 3 (x 2 ) x 2 x 2 x 2 T 1 (x 3 ) T 2 (x 3 ) T 3 (x 3 )
T 4 (x 3 , t 5 )

x 3

x 3

x 3

x 3

x 3 x 3

Figure 3: The connectivity graph G q of the sj-free CQ q from Example A.10.

(2) If µ ′ is an avoiding assignment of G ′ , then µ ′ |V is an avoiding assignment of G. We first prove item 1). We say that an edge e of G is chosen if it is in the image of µ. Observe that, because µ is avoiding, there are exactly |V | edges of G that are chosen; for instance, considering the graph of Figure 2, the assignment is avoiding and there are 5 = |V | chosen edges. Let us now look at the number of avoiding assignments µ ′ of G ′ that agree with µ. It is easy to see that for every edge e of G that is chosen, the value of µ ′ (n e ) is forced: we have to set µ ′ (n e ) to be the (unique) edge {n e , v} such that µ(v) e. Moreover when e is not chosen, both values for n e are possible. But then this indeed implies that there are 2 |E |-|V | avoiding assignments µ ′ of G ′ that agree with µ. To show item 2), assume by contradiction that µ ′ |V is not avoiding. This means that there is an edge e ∈ E with λ(e) = {u, v} such that we have µ ′ |V (u) = µ ′ |V (u) = e. But then, looking at the possible value for µ ′ (n e ), we see that µ ′ cannot be avoiding in G ′ , a contradiction. □

We are now ready to treat the problem #Val Cd (R(x) ∧ S(x)):

Proof of Proposition 3.5. We reduce from #Avoidance on bipartite graphs, which we have just shown to be #P-hard. Let G = (U ⊔ V , E) be a bipartite graph. For every node t ∈ U ⊔ V , we have a null ⊥ t with domain dom(⊥ t ) def = E(t). For every node u ∈ U we have a fact R(⊥ u )

and for every node v ∈ V a fact S(⊥ v ). The constructed database is a Codd table. Moreover, it is clear that the value of #Val Cd (R(x) ∧ S(x)) on that database is exactly the number of assignments of G that are not avoiding, thus establishing hardness. □

A.3 Proof of Theorem 3.9

In this section we prove the tractability claim of the following dichotomy theorem.

Theorem 3.9 (dichotomy). Let q be an sjfBCQ. If R(x, x) or R(x) ∧ S(x, y) ∧ T (y) or R(x, y) ∧ S(x, y) is a pattern of q, then #Val u (q) is #P-complete. Otherwise, #Val u (q) is in FP.

First, to characterize the queries that do not have these patterns, we will use the notion of connectivity graph of a sj-free CQ q: Definition A.9. Let q be a sj-free CQ. The connectivity graph of q is the graph G q = (V , E) with labeled edges, where V is the set of atoms of q, and for every two atoms R( xi ), S( ȳi ) of q, if they share a variable then we have an edge between the corresponding nodes of G q , that edge being labeled with the variables in xi ∩ ȳi .

Example A.10. Figure 3 shows the connectivity graph of the query

R 1 (x 1 , x 1 , y 1 , t 1 ), R 2 (x 1 , y 1 , t 2 ), S 1 (x 2 , t 3 ), S 2 (x 2 , t 4 ), S 3 (x 2 ),T 1 (x 3 ),T 2 (x 3 ),T 3 (x 3 ),T 4 (x 3 , t 5 ).
The following is then readily observed: Lemma A.11. Let q be a sj-free CQ that does not contain any of the patterns mentioned in Theorem 3.9. Then for every connected component C of G q , C is a clique and there exists a variable such that all edges of C are labeled by exactly that variable.

Proof. First, observe that every edge of G q must be labeled by exactly one variable, as otherwise the query q would contain the pattern R(x, y) ∧ S(x, y). Let C be a connected component of G q . Then we have:

• C is a clique. Indeed, assume by contradiction that C is not a clique. Then, since C is connected and is not a clique, we can find 3

nodes A 1 (x), A 2 (x ′ ), A 3 (x ′′ ) such that A 1 (x) is adjacent to A 2 (x ′ ), A 2 (x ′
) is adjacent to A 3 (x ′′ ), and A 1 (x) is not adjacent to A 3 (x ′′ ).

Let X be x ∩ x ′ and Y be x ′ ∩ x ′′ , i.e., the labels on the two corresponding edges of C. By definition of G q and since A 1 (x) is not adjacent to A 3 (x ′′ ), we must have X ∩ Y = ∅. But X and Y are not empty (again by definition of G q ), so by picking x in X and y in Y we see that q contains the pattern R(x) ∧ S(x, y) ∧ T (y), a contradiction. • There exists a variable that labels every edge of C. Indeed, since every edge of G q is labeled by exactly one variable, and since C is a clique, if it was not the case then again we could find the pattern R(x) ∧ S(x, y) ∧ T (y) in q.

This concludes the proof. □

For instance, the query from Example A.10 does not satisfy this criterion, since the edge in the first connected component of G q is labeled by two variables. However if we consider the query S 1 (x 2 , t 3 ), S 2 (x 2 , t 4 ), S 3 (x 2 ),T 1 (x 3 ),T 2 (x 3 ),T 3 (x 3 ),T 4 (x 3 , t 5 ) (i.e., we remove the first connected component), then it satisfies the criterion.

We will also use the general fact that for a sj-free CQ q, we can assume wlog that q does not contain variables that occur only once:

Lemma A.12. Let q be a sj-free CQ, and let q ′ be the sj-free CQ obtained from q by deleting all the variables that have only one occurrence in q. Then #Val u (q) ⩽ p T #Val u (q ′ ).

Proof. Let D be an incomplete database input of #Val u (q). Let S be set of nulls ⊥ such that:

• ⊥ occurs in a column corresponding to a variable that has been deleted; and • ⊥ does not occur in a column corresponding to a variable that has not been deleted.

Then, letting D ′ be the database obtained from D by projecting out the columns corresponding to the deleted variables, it is clear that we have #Val u (q

)(D) = #Val u (q ′ )(D ′ ) × ⊥∈S |dom(⊥)|,
where dom is the uniform domain of the nulls. We note here that this lemma is also true in the non-uniform setting. □ By Lemma A.11 and Lemma A.12, it is enough to show the tractability of #Val u (q) when q is of the form

C 1 (x 1 ) ∧ . . . ∧ C m (x m ), where each C i (x i
) is what we call a basic singleton query, i.e., is a conjunction of unary atoms over the same variable x i . We call such a sj-free CQ a conjunction of basic singletons. For instance,

S 1 (x 2 ), S 2 (x 2 ), S 3 (x 2 ),T 1 (x 3 ),T 2 (x 3 ),T 3 (x 3 ),T 4 (x 3 )
is such a query, with m = 2. We will use the following: Lemma A.13. Let q = C 1 (x 1 )∧. . .∧C m (x m ) be a conjunction of basic singletons sj-free query, and let D be an incomplete database. For S ⊆ [m], we define N S (D)

def = |{ν valuation of D | ν (D) ̸ |= i ∈S C i (x i )}|. Then we have #Val u (q)(D) = S ⊆[m] (-1) |S | N S (D).

Proof. Direct, by inclusion-exclusion. □

Hence, and remembering that we consider data complexity, it is enough to show how to compute N S (D) for every S ⊆ [m]. The main difficulties in computing N S (D) is that the relations can have nulls in common (since we consider naïve tables), and that they may also have constants; this makes it technically painful to express a closed-form expression for N S (D). We explain how to do it next, thus finishing the proof of Theorem 3.9.

Proposition A.14. Let q = C 1 (x 1 ) ∧ . . . ∧ C m (x m ) be a conjunction of basic singletons sj-free query and S ⊆ [m]. Then, given an incomplete database D as input, we can compute N S (D) in polynomial time.

Proof. We strongly advise the reader to have well understood Example 3.10 before reading this proof. First, observe that to compute N S (D) we can assume without loss of generality that the input database D only contains facts over relation names that occur in some C i (x i ), for i ∈ S. Indeed, N S (D) counts the valuations ν of D that do not satisfy any of the C i (x i ) for i ∈ S, so that for any j S we do not care if ν satisfies C j (x j ) or not; hence, we could simply multiply the result by the appropriate factor. Therefore, we can assume that S is [m]. We now need to fix some notation. Let us write the conjunction of basic singleton sj-free query q as

R 1 (x 1 ) ∧ . . . ∧ R m 1 (x 1 ) ∧ R m 1 +1 (x 2 ) ∧ . . . ∧ R m 1 +m 2 (x 2 ) ∧ . . . ∧ R m-1 i =1 m i (x m ) ∧ . . . ∧ R m i =1 m i (x m )
and let K be the number of atoms in q, that is,

K def = m i=1 m i .
Let dom be the uniform domain of the nulls occurring in D and d its size. For s ⊆ [K], we write C s the set of constants that occur in each of the relations D(R i ) for i ∈ s but in none of the others, and write c s the size of that set. We call such a set a block of constants. Similarly for the nulls, we write N s the set of nulls that occur in each of the relations D(R i ) for i ∈ s but in none of the others (and we call this a block of nulls), and n s for its size. We can assume wlog that: (a) For every 1 ⩽ i ⩽ m, there is no constant that occurs in every D(R) for R a relation name in C i (x i ). Indeed otherwise any valuation would satisfy C i (x i ), thus N [m] (D) would simply be 0. (b) Every constant c appearing in D is in dom. Indeed otherwise, with the last item, this constant would have no chance to be part of a match, so we could simply remove it (i.e., remove all tuples of the form R(c) from D).

For a subset A ⊆ dom, let us write A ∁ def = dom \ A. Finally, for a set Z = {A 1 , . . . , A l } of subsets of dom, we denote by I(Z ) the set

I(Z ) def = { l i=1 B i | (B 1 , . . . , B l ) ∈ {A 1 , A ∁ 1 } × . . . × {A l , A ∁ l }}
We now explain informally how we can compute N [m] (D). Let L = s 1 , . . . , s 2 K be an arbitrary linear order of the set of subsets of [K]. We will define by induction on i ∈ [2 K ] an expression computing N [m] (D), which will be a nested sum of the form

something s 1 f s 1 × something s 2 f s 2 × . . . ( something s 2 K f s 2 K ) . . . (2)
where each something s i sums over the possible images A s i of the nulls in N s i by a valuation, and f s i will simply be surj n s i →a s i , where a s i def = |A s i |, i.e., the number of valuations ν of N s i with image exactly A s i . But there are two technicalities:

• First, we need to ensure that each basic singleton query C i (x i ) of q will not be satisfied. In order to do that, something s i will actually sum over all the possible partitions (B 1 s i , . . . , B

|I(Z i -1 |) s i
) of A s i , where each of the B j s i is included in one of the sets in I(Z i-1 ), where Z i-1 contains all the blocs of constants and all the other B r s j for j < i. We iteratively build that sum from the outside to the inside, starting with

Z 0 def = {dom} ∪ {C s | s ⊆ [K]}.
This will allow us to avoid summing over the B j s i that would render a basic singleton query true.

• Second, as is, such a sum is obviously not going to be computable in PTIME, as we are summing over subsets of dom. To fix this, observe that the value of the subsum for s i actually only depends on the sizes of the sets in Z i-1 . Hence, iterating from the outside to the inside, whenever something s i contains a sum of the form, say, B k s i ⊆ B k ′ s j for j < i, we can replace this with a sum over 0

⩽ b k s i ⩽ b k ′ s j ,
and add to f s i a factor of

b k ′ s j b k s i
. Now, because of how Z 0 is defined, and because of how I works, all the initial numbers in the first sum are either |dom \ K i=1 C {i } | or one of the numbers c s for s ⊆ [K]. These can all be computed in polynomial time. The resulting expression then indeed evaluates to N [m] (D), and is in a form that allows us to directly compute it in polynomial time (but non-elementary in the query). This concludes the proof of Proposition A.14. □

A.4 Proof of Proposition 3.11

Proposition 3.11. #Val u Cd (R(x) ∧ S(x, y) ∧ T (y)) is #P-hard.
Proof. We reduce from the problem of counting the number of independent sets of a bipartite graph, written #BIS, which is #P-hard [START_REF] Scott | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF]. Let G = (X ⊔ Y , E) be a bipartite graph. Without loss of generality, we can assume that

|X | = |Y | = n; indeed, if |X | < |Y | then we could simply add |Y | -|X | isolated
nodes to complete the graph, which simply multiplies the number of independent sets by 2 |Y |-|X | . Also, observe that counting the number of independent sets of G is the same as counting the number of pairs (S 1 , S 2 ) with S 1 ⊆ X , S 2 ⊆ Y , such that (S 1 × S 2 ) ∩ E = ∅. We will call such a pair an independent pair. For 0 ⩽ i, j ⩽ n, let Z i, j be the number of independent pairs (S 1 , S 2 ) such that |S 1 | = i and |S 2 | = j. It is clear that (⋆) the number of independent sets of G is then #BIS(G) = 0⩽i, j ⩽n Z i, j . The idea of the reduction is to construct in polynomial time (n + 1) 2 incomplete databases D a,b for 0 ⩽ a, b ⩽ n such that, letting C a,b be the number of valuations ν of D a,b with ν (D a,b ) ̸ |= R(x) ∧ S(x, y) ∧ T (y), the values of the variables Z i, j and C i, j form a linear system of equations AZ = C, with A an invertible matrix. This will allow us, using (n + 1) 2 calls to an oracle for #Val u Cd (R(x) ∧ S(x, y) ∧ T (y)), to recover the Z i, j values, and then to compute #BIS(G) using (⋆). We now explain how we construct D a,b from G for 0 ⩽ a, b ⩽ n, and define A. First, we fix an arbitrary linear order x 1 , . . . , x n of X , and similarly y 1 , . . . , y n for Y . The database D a,b has constants a i for 1 ⩽ i ⩽ n, and has a fact S(a i , a j ) whenever (x i , y j ) ∈ E. It has nulls ⊥ 1 , . . . , ⊥ a and facts R(⊥ i ) for 1 ⩽ i ⩽ a (if a = 0 there are no such nulls and facts), and nulls ⊥ ′ 1 , . . . , ⊥ ′ b and facts T (⊥ ′ i ) for 1 ⩽ i ⩽ b; in particular, this is a Codd table. The uniform domain of the nulls is {a i | 1 ⩽ i ⩽ n}. Given a valuation ν of D a,b , let P(ν ) be the pair of subsets of V defined by

P(ν ) def = ({x i | ∃1 ⩽ k ⩽ a s.t. ν (⊥ k ) = a i }, {y i | ∃1 ⩽ k ⩽ b s.t. ν (⊥ ′ k ) = a i })
One can then easily check that the following two claims hold:

• For every valuation ν of D a,b , we have that ν (D a,b ) ̸ |= R(x) ∧ S(x, y) ∧ T (y) iff P(ν ) is an independent pair of G; 6 • For every independent pair (S 1 , S 2 ) of G, there are exactly surj a→|S 1 | × surj b→|S 2 | valuations ν such that P(ν ) = (S 1 , S 2 ).
But then, we have C a,b = 0⩽i, j ⩽n (surj a→i × surj b→j )Z i, j . In other words, we have the linear system of equations AZ = C, where A is the (n + 1) 2 × (n + 1) 2 matrix defined by A (a,b),(i, j) def = surj a→i × surj b→j . This matrix is the Kronecker product A ′ ⊗ A ′ of the (n + 1) × (n + 1) matrix with entries A ′ a,i def = surj a→i . Since A ′ is a triangular matrix with non-zero coefficients on the diagonal, it is invertible, hence so is A, Lemma 4.1. Let q, q ′ be sjfBCQs such that q ′ is a pattern of q. Then we have that #Comp(q ′ ) ⩽ p par #Comp(q) and #Comp u (q ′ ) ⩽ p par #Comp u (q). Moreover, the same results hold if we restrict to the case of Codd tables.

That is, we deal with the problems #Comp u Cd (R(x, x)) and #Comp u Cd (R(x, y)). We will use the problem of counting the number of induced pseudoforests of a graph, as defined next.

Definition B.3.

A graph G is a pseudoforest if every connected component of G contains at most one cycle. Let G = (V , E) be a graph. For S ⊆ E, let us denote by G[S] the graph (V ′ , S), where V ′ is the set of nodes of G that appear in some edge of S. The problem #PF is the problem that takes as input a graph G = (V , E) and outputs the number of edge sets S ⊆ E such that G[S] is a pseudoforest.

Using techniques from matroid theory, the authors of [START_REF] Giménez | On the complexity of computing the Tutte polynomial of bicircular matroids[END_REF] have shown that #PF is #P-hard on graphs. We explain in Appendix B.5 how their proof actually shows hardness of this problem for bipartite graphs.

To prove that the reduction that we will present is correct, we will also need the following folklore lemma about pseudoforests. We recall that an orientation of an undirected graph G = (V , E) is a directed graph that can be obtained from G by orienting every edge of G. Equivalently, one can see such an orientation as a function f : E → V that assigns to every edge in G a node to which it is incident. We then have: Lemma B.4. A graph G is a pseudoforest if and only if there exists an orientation of G such that every node has outdegree at most 1.

Proof. Folklore, see, e.g., [START_REF] Fan | Decomposing a graph into pseudoforests with one having bounded degree[END_REF][START_REF] Grout | On decomposing graphs into forests and pseudoforests[END_REF][START_REF] Kowalik | Approximation scheme for lowest outdegree orientation and graph density measures[END_REF]. □

Using hardness of #PF on bipartite graphs, are able show hardness of #Comp u Cd (R(x, y)) and #Comp u Cd (R(x, y)) for Codd tables, as follows.

Proof of Proposition 4.5, item (b). We reduce both problems from #PF on bipartite graphs. Let G = (U ⊔ V , E) be a bipartite graph. We will construct a uniform Codd table D over binary relation R such that (1) all the completions of D satisfy both queries; and (2) the number of completions of D is equal to #PF(G), thus establishing hardness. For every (t, t ′ ) ∈ (U ∪ V ) 2 \ E, we add to D the fact R(t, t ′ ); we call these the complementary facts. For every u ∈ U we add to D the fact R(u, ⊥ u ) and for every v ∈ V the fact R(⊥ v , v). Finally, we add to D a fact R(f , f ) where f is a fresh constant. The uniform domain of the nulls if dom = U ∪ V . It is clear that D is a Codd table and that every completion of D satisfies both queries (thanks to the fact R(f , f )), so (1) holds. We now prove that (2) holds. First of all, observe that a completion ν (D) of D is uniquely determined by the set of edges {(u, v) ∈ E | R(u, v) ∈ ν(D)}: this is because ν (D) already contains all the complementary facts. For a set S ⊆ E of edges, let us define D S to be the complete database that contains all the complementary facts and all the facts R(u, v) for (u, v) ∈ S (note that D S is not necessarily a completion of D). We now argue that for every set S ⊆ E, we have that D S is a completion of D if and only if G[S] is a pseudoforest, which would conclude the proof. By lemma B.4 we only need to show that D S is a completion of D if and only if G[S] admits an orientation with maximum outdegee 1. We show each direction in turn. (⇒) Assume D S is a completion of D, and let ν be a valuation witnessing this fact, i.e., such that ν (D) = D S . First, observe that we can assume without loss of generality that (⋆) for every e = (u, v) ∈ S, we have either ν (⊥ u ) = v or ν (⊥ v ) = u but not both. Indeed, if we had both then we could modify ν into ν ′ by redefining, say, ν ′ (⊥ u ) to be u, and we would still have that ν ′ (D) = D S (because R(u, u) is already present in D: it is a complementary fact). We now define an orientation f ν : S → U ∪ V of G[S] from ν as follows. Let e = (u, v) ∈ S. Then: if we have ν (⊥ u ) = v we define f ν ((u, v)) to be v, i.e., we orient the (undirected) edge (u, v) from u to v. Else, if we have ν (⊥ v ) = u we define f ν ((u, v)) to be u, i.e., we orient the (undirected) edge (u, v) from v to u. Observe that by (⋆) f ν is well defined. It is then easy to check that the maximal outdegree or the directed graph defined by f ν is 1: this is because for every u ∈ U (resp., v ∈ V ), there is only one fact in D of the form R(u, null) (resp., R(null, v)), namely, the fact R(u, ⊥ u ) (resp., R(⊥ v , v)). (⇐) let f : S → U ∪ V an orientation of G[S] with maximum outdegree 1. Let ν f be the valuation of D defined from f as follows: for every u ∈ U (resp., v ∈ V ), if there is an edge (u, v) ∈ S such that f ((u, v)) = v (resp., such that f ((u, v)) = u), then define ν f (⊥ u ) to be v (resp., define ν f (⊥ v ) to be u). Observe that there can be at most one such edge because f has maximum outdegree 1, so this is well defined. If there is no such edge, define ν f (⊥ u ) to be u (resp., define ν f (⊥ v ) to be v). Since all edges in S are given an orientation by f , it is clear that for every (u, v) ∈ S we have R(u, v) ∈ ν f (D). Moreover, since ν f (D) contains all the complementary facts, we have that ν f (D) = D S , which shows that D S is a completion of D and concludes this proof. □

B.5 Proof for Proposition B.5

In this section we explain how to obtain the following hardness result.

Proposition B.5 (Implied by [START_REF] Giménez | On the complexity of computing the Tutte polynomial of bicircular matroids[END_REF]). The problem #PF restricted to bipartite graphs is #P-hard.

This result is proven for (non-necessarily bipartite) graphs in [START_REF] Giménez | On the complexity of computing the Tutte polynomial of bicircular matroids[END_REF] using techniques from matroid theory, in particular using the notions of bicircular matroid of a graph and of Tutte polynomial of a matroid. We did not find a way to show that the result holds on bipartite graphs without explaining their proof for general graphs, and we did not find a way to explain the proof for general graphs without introducing these concepts. Therefore, we need to define these concepts here. We have tried to keep this exposition as brief as possible, but more detailed introductions to matroid theory and to the Tutte polynomial can be found in [START_REF] Oxley | What is a matroid[END_REF][START_REF] Welsh | The tutte polynomial[END_REF]. First, we define what is a matroid. Definition B.6. A matroid M = (E, I) is a pair where E is a finite set (called the ground set) and I is a set of subsets of E whose elements are called independent sets and that satisfies the following properties: Non emptiness. I ∅; Heritage. For every A ′ ⊆ A ⊆ E, if A ∈ I then A ′ ∈ I; Independent set exchange. For every A, B ∈ I, if |A| > |B| then there exists x ∈ A \ B such that B ∪ {x } ∈ I.

In a matroid M = (E, I), an independent set A ∈ I is called a basis if every strict superset A ⊊ A ′ ⊆ E is not in I. Notice that, thanks to the independent set exchange property, all bases of M have the same number of elements. The rank of M is defined as the number of elements in any basis of M. Given a matroid M = (E, I) and A ⊆ E, we can define the submatroid of M generated by A to be M A = (A, I ′ ), where for A ′ ⊆ A we have A ′ ∈ I ′ iff A ′ ∈ I (one should check that this is indeed a matroid). The rank function rk M : {A | A ⊆ E} → N of M is then defined with rk M (A) being the rank of the matroid M A . We will now ommit the subscript in rk M as this will not cause confusion. We are ready to define the Tutte polynomial of a matroid. Notice then that the problem #PF is exactly the same as the problem of computing, given as input a graph G, the quantity T(B(G); 2, 1). We now explain the steps used in [START_REF] Giménez | On the complexity of computing the Tutte polynomial of bicircular matroids[END_REF] to prove that computing T(B(G); 2, 1) is #P-hard for graphs. The starting point of our explanation is that computing T(B(G); 1, 1) is #P-hard. Notice that this is indeed a polynomial and that its degree is at most |E| (the degree is exactly |E| iff G is itself a pseudoforest). If we could compute efficiently the coefficients of P G , then we could in particular compute the value P G (1) = T(B(G); 1, 1), which is #P-hard by the previous proposition. We recall that to compute the coefficients of a polynomial of degree n, it is enough to know its value on n + 1 distinct points; in fact, given these values in n + 1 distinct points, it is possible to efficiently compute the coefficients of the polynomial by using standard interpolation techniques (for example, by using Lagrange polynomials). We need one last definition.

Definition B.11. Let G be a graph. For k ∈ N, let s k (G) be the graph obtained from G by replacing each edge of G by a path of lenght k; this graph is called the k-stretch of G.

Then, using a result attributed to Brylawski (see [START_REF] Jaeger | On the computational complexity of the Jones and Tutte polynomials[END_REF]), the authors of [START_REF] Giménez | On the complexity of computing the Tutte polynomial of bicircular matroids[END_REF] obtain that, "up to a trivial factor", we have T(B(s k (G)); 2, 1) ≃ T(B(G); 2 k , 1).

A careful inspection of [START_REF] Jaeger | On the computational complexity of the Jones and Tutte polynomials[END_REF] reveals 7 that, in fact, we have

T(B(s k (G)); 2, 1) = (2 k -1) |E |-rk B(G ) (E) × T(B(G); 2 k , 1).
Notice that rk B(G) (E) is the size (number of edges) of a pseudoforest of G that is maximal by inclusion of edges, which we can compute in polynomial time. 8With this, the authors of [START_REF] Giménez | On the complexity of computing the Tutte polynomial of bicircular matroids[END_REF] can conclude the proof that computing T(B(G); 2, 1) is hard for (non-necessarily bipartite) graphs, i.e., that #PF is #P-hard. Indeed, given as input G = (V , E), we can construct in polynomial time the graphs s k (G) for |E| + 1 distinct values of k, then use oracle calls to obtain the numbers T(B(s k (G)); 2, 1), which gives us the value of P G on |E| + 1 distinct points. With that we can recover the coefficients of P G and compute P G (1) = T(B(G); 1, 1) as argued above, thus proving hardness for general graphs. To obtain hardness for bipartite graphs, it is enough to observe that when k is even then the k-stretch of G is bipartite (even if G is not bipartite). Hence, to obtain a proof of Proposition B.5 for bipartite graphs, we can simply change that proof and specify that we make |E| + 1 calls to the oracle T(B(s k (G)); 2, 1) for |E| + 1 disctinct even values of k.

B.6 Proof of Theorem 4.6

Theorem 4.6 (Dichotomy). Let q be an sjfBCQ. If R(x, x) or R(x, y) is a pattern of q, then #Comp u (q) and #Comp u Cd (q) are #P-hard. Otherwise, these problems are in FP.

We only need to prove the tractability part of that claim, and this only for uniform incomplete databases. Remember from Section A.3 that what we call a conjunction of basic singleton sjfBCQ is an sjfBCQ of the form C 1 (x 1 ) ∧ . . . ∧ C m (x m ), where each C i (x i ) is a conjunction of unary atoms over the same variable x i . Since q does not contain the pattern R(x, x) nor the pattern R(x, y), q is in fact a conjunction of basic singleton sjfBCQ. The main difficulty is to decompose the computation in such a way that we do not count the same completion twice. Moreover, the fact that the database is naïve and not Codd, and the fact that constants can appear everywhere, complicate a lot the description of the algorithm. For these reasons, and to give the intuition of the general proof, we first present a few warm-up examples of increasing difficulty. We strongly advise the reader to read these before reading the proof. In what follows we will always denote by dom the uniform domain of the nulls, and d ⩾ 1 its size.

⩽ |I R | ⩽ n R .
But then the answer is simply 1⩽i R ⩽n R d i R , which we can compute in polynomial time. 9 Note that the expression 0⩽i R ⩽n R d i would give the right answer only when n R = 0 because there has to be at least one tuple in the completion if n R > 1 so the sum should start at 1. We can also compute the result using the following expression, which works for all n ∈ N:

0⩽i R ⩽d d i R × check(i R ) (3)
where check

(i R ) ∈ {0, 1} is defined as check(i R ) def =          if i R > n R then 0 if i R = 0
⩽ |I R | ⩽ n R .
But then the answer is simply 0⩽i R ⩽n R d -c R i R . Note that this expression would not give the right answer in case we had c R = 0, n R ⩾ 1 because the nulls cannot be "absorbed" by C R , so in that case the sum should start at 1. We can also compute the result using the following expression, which works for all c R , n R ∈ N:

0⩽i R ⩽d d -c R i R × check(i R ) (4)
where check(i R )

def =          if i R > n R then 0 if i R = 0 and c R = 0 and n R ⩾ 1 then 0 otherwise 1 .
B.6.3 Warm-up example 3: #Comp u (R(x) ∧ S(y)) without constants. Let D be an incomplete naïve table over R, S that do not have constants.

Let n RS be the number of nulls that occur in both R and S, n R the number of nulls that occur only in R and n S the number of nulls that occur only in S. We further assume that n RS ⩾ 1, otherwise we can simply compute independently the number of completions of the R and S tables as in warm-up example 1 and multiply the two numbers. We claim the following: Claim B.12. Let D ′ be a complete database over R, S with constants in dom, and let

I R def = {a ∈ dom | R(a) ∈ D ′ , S (
R | ⩽ n R , |I S | ⩽ n S , and 1 ⩽ |I RS | ⩽ min(n RS + n R -|I R |, n RS + n S -|I S |).
Proof. The only if part is easy to check. Suppose then that these conditions hold on D ′ . We can assign the first |I R | nulls that are only in R so that they span I R , and assign the first |I S | nulls that are only in S so that they span I S . If |I RS | ⩽ n RS then we can assign the nulls that are in both R and S so that they span I RS , and then we can assign the remaining nulls (that appear only in R or only in S) to a value that has already been assigned, and we indeed obtain (4) the following system of equations, whose variables are natural numbers between 0 and d, has a solution:

z {N R } N R + z {N R ,C S } N R + z {N R , N S } N R ⩽ n R z {N S } N S + z {N S ,C R } N S + z {N S , N R } N S ⩽ n R z {C R , N S } C R ⩽ c R z {C S , N R } C S ⩽ c S z {N R } N R ⩾ |I R | z {N S } N S ⩾ |I S | n RS + min(z {N R ,C S } N R , z {C S , N R } C S ) + min(z {N R , N S } N R , z {N S , N R } N S ) + min(z {N S ,C R } N S , z {C R , N S } C R ) ⩾ |I RS |
Proof. We prove the claim informally by explaining the main ideas, because a formal proof would be too long and not that interesting. Conditions (1-3) are easily checked to be necessary. We now explain why condition (4) is also necessary. Suppose that P(I R , I S , I RS ) is a completion of D. Observe that ( †) to obtain the constants in I RS , we had to use some or all of the following:

• the nulls in N RS ; or • the nulls in N R together with those in N S ; or • the nulls in N R together with the constants in C S ; or • the nulls in N S together with the constants in C R .

But then, to obtain P(I R , I S , I RS ) as a completion, we must have used three disjoint (possibly empty) sets

Z {N R } N R , Z {N R ,C S } N R , Z {N R , N S } N R of the nulls in N R of sizes 0 ⩽ z {N R } N R , z {N R ,C S } N R , z {N R , N S } N R
⩽ d, we have done the same for the nulls in N S and we also used a subset of the constants of C R (and C S ) in such a way that, according to ( †):

• the nulls in

Z {N R } N R
have been used to obtain the set I R (which, we recall, is the set of constants that occur only in R and that are not in C R ). Note that only the nulls in N R could have been used to obtain constants in I R . This is what the fifth equation expresses.

• the nulls in

Z {N R ,C S } N R have values in Z {C S , N R } C S
, which gives us constants in I RS . Observe that at maximum we could obtain min(z

{N R ,C S } N R , z {C S , N R } C S
) constants in this manner.

• the nulls in

Z {N R , N S } N R and those in Z {N R , N S } N R
have common values, which gives us constants in I RS . Again, observe that we can get at most min(z

{N R , N S } N R , z {N S , N R } N S
) constants using these.

The first 4 equations express the partitioning process, and the last equation then expresses that by combining all these constants we indeed obtained the whole set I RS .

We now explain why conditions (2-4) are sufficient. If |I R |, |I S | and I RS are all ⩾ 1 then condition ( 4) is sufficient, because we can use the nulls and constants as explained above, and we have enough of them to obtain the sets I R , I S , I RS . We explain what happens when I R = ∅ for instance. In that case, condition [START_REF] Abiteboul | Foundations of databases[END_REF] ensures us that we have either n R = 0 or C R ∪ C RS ∪ I RS ∅. If we have n R = 0 then it is fine, since the only nulls that could be used to fill I R are those in N R . If we have n R ⩾ 1 and C R ∪ C RS ∪ I RS ∅ then we can use these to absorb the values of the nulls in N R , and we are fine (i.e., we will be able to obtain I R = ∅). We leave it to the reader to complete the small gaps in this proof. Proof. The fact that this value only depends on the sizes of these sets is simply by inspection of the conditions in Claim B. [START_REF] Codd | Understanding relations (installment# 7)[END_REF]. Conditions (1-3) can obviously be checked in P. The fact that condition (4) can be checked in P is because we can test all possible assignments between 0 and d for all these variables and see if there is one assignment that satisfies the equations (note that the number of variables is fixed). □ But then, we can express the result as follows

0⩽i R ,i S ,i RS ⩽d d -c i R d -c -i R i S d -c RS -i R -i S i RS × check(i R , i S , i RS )
and we can evaluate this expression as-is in FP because computing check(I R , I S , I RS ) ∈ {0, 1} is in P by the last claim. This concludes this example.

B.6.6 Proof of Theorem 4.6. We now present the general proof. Let σ = {R 1 , . . . , R l } be the set of relation symbols, and D be an incomplete database over these relations. For every s ⊆ σ , s ∅, let:

• C s be the set of constants that occur in all relations of s and in none of the others; c s be its size;

• N s be the set of nulls that occur in all relations of s and in none of the others; n s be its size.

We also define c as ∅ s⊆σ c s . We can assume wlog that C s ⊆ dom for all ∅ s ⊆ σ , otherwise we can simply remove from D the corresponding facts. Let L def = 2 l -1, and let s 1 , . . . , s L be an arbitrary linear order of {s ⊆ σ | s ∅} (for instance, by non-decreasing size).

We will follow the same steps as in the last example. The following lemma is the generalization of Claim B.13, and explains how we can guide the computation so that we do not count the same completion twice: Lemma B.17. For a tuple (I s 1 , . . . , I s L ) of subsets of dom satisfying (⋆)

I s ⊆ (dom \ (C ∪ ∅ s ′ ⊆σ s ′ s I s ′ )) ∪ ∅ s ′ ⊊s C s ′
for every s ∈ (s Proof. Let us write P = P(I s 1 , . . . , I s L ) and P ′ = P(I ′ s 1 , . . . , I ′ s L ). Assume that P = P ′ , and let us show that (I s 1 , . . . , I s L ) = (I ′ s 1 , . . . , I ′ s L ). Assume by way of contradiction that for some ∅ s ⊆ σ we have I s I ′ s . Then (wlog) there exists a ∈ I s \ I ′ s . By the definition of P, we have that P contains all the facts R(a) for R ∈ s. Let us show that P does not contain any fact R(a) for R s. Otherwise, assume that P contains R(a) with R s. Then there exists s ′ ⊆ σ such that R ∈ s ′ and such that a ∈ I s ′ ∪ (C s ′ \ s ′ ⊋s ′′ I s ′′ ). Since s does not contain R while s ′ does, we have s ′ ⊈ s. But then by (⋆) we have that I s and I s ′ ∪ C s ′ are disjoint, which is a contradiction because a is supposed to be in both I s and I s ′ ∪ (C s ′ \ s ′ ⊋s ′′ I s ′′ ). Therefore, it is indeed the case that P does not contain any fact R(a) for R s. Now, if P ′ contains a fact R(a) for some R σ then we are done since this would imply P P ′ , a contradiction. Hence we can assume that P ′ does not contain any fact R(a) for R σ . We will now prove that P ′ does not contain all the facts R(a) for R ∈ σ , thus establishing a contradiction (because P does, so we would have P P ′ ) and concluding this proof. Assume by contradiction that P ′ contains all the facts R(a) for R ∈ s. First of all, observe that we have a C s because by (⋆) we have that I s and C s are disjoint, and we know that a ∈ I s . Hence, the only way in which P ′ could contain all the facts R(a) for R ∈ s is if there exist s ′ 1 , . . . , s ′ k with k ⩾ 1 and s ′ j ⊊ s for 1 ⩽ j ⩽ k such that 1⩽j ⩽k s ′ j = s and such that for every 1 ⩽ j ⩽ k we have that (i) a ∈ I s ′ j ∪ (C s ′ j \ s ′ j ⊋s ′′ I s ′′ ). Observe that there must exist 1 ⩽ j 1 , j 2 ⩽ k such that s ′ j 1 and s ′ j 2 are incomparable by inclusion (otherwise, since all s j are strictly included in s, their union could not be equal to s). Also observe that by (⋆) we have that the sets I s ′ j 1 ∪ C s ′ j 1 and I s ′ j 2 ∪ C s ′ j 2 must be disjoint. But then (i) applied to j 1 and j 2 gives a contradiction (namely, these two sets are not disjoint since they both contain a). This finishes the proof. □

This next Lemma generalizes Claim B.14 and tells us that by summing over all such tuples (I s 1 , . . . , I s L ) we cannot miss a completion of D:

Lemma B.18. Let D ′ be a completion of D. Then there exists a tuple (I s 1 , . . . , I s L ) of subsets of dom satisfying (⋆) such that D ′ = P(I s 1 , . . . , I s L ).

Proof. For ∅ s ⊆ σ , let us define D s to be the set of constants that occur in all relation of s and in none of the others. Define the set I s for ∅ s ⊆ σ as follows:

I s def = D s \ C s .
We give here the necessary and sufficient conditions for P(I s 1 , . . . , I s L ) to be a completion of D that satisfies q.

Lemma B.19. We have check(I s 1 , . . . , I s L ) = 1 if and only if the following conditions hold:

(1) for every basic singleton query C i (x) of q, letting s be its sets of relation symbols, there exists s ⊆ s ′ ⊆ σ such that we have |I s ′ | ⩾ 1 or c s ′ ⩾ 1.

(2) for every ∅ s ⊆ σ , if n s ⩾ 1 and | s ′ ⊇s C s ′ ∪ s ′ ⊋s I s ′ | = 0 then |I s | 0.

(3) consider the following system of equations, with integer variables between 0 and d:

• for every two sets A, A ′ of subsets of {∅ s ⊆ σ }, we have a variable z A,A ′ of the constants in C {U } in order to obtain constants in I {R,S,T ,U } . Let us write V this set of variables. (we note here that we are using sligthly different notation than for the last warm-up example; this is for readability reasons only.) • Now, for every ∅ s ⊆ σ we have the constraint intuitively meaning that we have allocated the groups of nulls and constants in a way that allows us to fill the set I s . Then this system of equations must have a solution.

Proof. The idea is the same as in Claim B.15. The only difference is that we added condition [START_REF] Abiteboul | Foundations of databases[END_REF], which ensures that the guessed completion indeed satisfies the query. □

As in the last warm-up example, this implies that the value of check(I s 1 , . . . , I s L ) only depends on (|I s 1 |, . . . , |I s L |) and can be computed in FP (by testing all assignments of the z * * variables; keep in mind that the schema is fixed so there are only a fixed number of such variables). But then we can compute the result in FP by evaluating the expression 7, which finishes the proof.

B.7 Proof of Theorem 4.7

Theorem 4.7 (Dichotomy). Let q be an sjfBCQ. If R(x, x) or R(x, y) is a pattern of q, then #Comp u Cd (q) is #P-complete. Otherwise, this problem is in FP.

Proof. Hardness follows from Theorem 4.6, while membership in #P follows from the result proven in Appendix B. Proposition 5.2. Assume that a Boolean query q is monotone, has model checking in nondeterministic linear space, and has bounded minimal models. Then #Val(q) is in SpanL.

Proof. Let D be the input incomplete database, with the domains for each null. First, the machine guesses a subset D ′ ⊆ D of size ⩽ C q , such that each fact of D ′ is over a relation symbol that appears in q. Observe that D ′ contains at most |D ′ | × arity(q) ⩽ C q × arity(q) distinct nulls, and that this is a constant. The machine then guesses and remembers a valuation ν of D ′ and computes ν(D ′ ). The encoding size ||ν (D ′ )|| of ν (D ′ ) is O(log |D|), so the machine can check in nondeterministic linear space whether ν (D ′ ) |= Q, and stops and rejects in the branches that fail the test. Then, the machine reads the input tape left to right and for every occurrence of a null ⊥ (appearing in D) that it finds, it does the following:

• It checks whether ⊥ appears before on the input tape and if so it simply continues;

• Else if ⊥ does not appear before on the input tape but appears in D ′ then the machine writes ν (⊥) on its output tape;

• Else if ⊥ does not appear before on the input tape and does not appear in D ′ then it guesses a value for it and writes that value on the output tape (but it does not remember that value). It is easy to see that this procedure can be carried out by a logspace nondeterministic transducer, so we only need to show that the distinct outputs of the machine correspond exactly to the distinct valuations ν of D such that ν(D) |= Q. Since the machine writes values for nulls in order of first appearance on the input tape, it is clear that every valuation is outputted exactly once. Let ν be a valuation that is outputted, and let D ′ be the subdatabase such that ν (D ′ ) |= Q. Since ν (D ′ ) ⊆ ν (D) and q is monotone, we have ν (D) |= Q. Inversely, let ν be a valuation of D such that ν(D) |= Q, and let us show that it must be outputted. Since ν(D) |= Q and q has bounded minimal models, there exists D ν ⊆ ν (D) of size ⩽ C q such that D ν |= Q. But D ν is ν (D ′ ) for some D ′ ⊆ D of size ⩽ C q . Then it is clear that one of the branches of the machine has guessed D ′ and then ν |D ′ and then has written ν on the output tape. □

We note here that the same proof does not work for counting completions. Informally, there are two complications that arise if we try to modify its proof to make the machine write a completion on the output tape:

• First, in order to write a completion on the output tape, the machine could need to remember the values of a nonconstant number of nulls, which it obviously cannot do in logspace; • Second, even if we considered Codd tables in order to avoid the previous complication, there does not seem to be a way to ensure that when we write a completion ν (D) to the output tape, this completion has not been written already in another branch of the computation but with the tuples written in a different order (in which case this completion would be counted more than once).

D PROOFS FOR SECTION 6 (ON THE GENERAL LANDSCAPE: BEYOND #P) D.1 Proof of Proposition 6.1 Proposition 6.1. There exists an sjfBCQ q such that #Comp u (q) is not in #P unless NP ⊆ SPP.

The proof of this result relies on the proof of Theorem 6.3 (we presented the results in this order in the main text for narrative purposes). Let q be the sjfBCQ defined in Equation [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF] in the proof of Theorem 6. Proof. Let D be an incomplete database over schema σ , that is an input of #Comp u (σ ). We construct in polynomial time an incomplete database D ′ over the same schema such that #Comp u (σ )(D) = #Comp u (q)(D ′ ), thus establishing the parsimonious reduction. Let f be a fresh constant that does occurs neither in D nor in the domain of some null. Then the relation D ′ (S) is the same as the relation D(S), plus a fact S(f , f ). Moreover, for every (a, b, c) ∈ {0, 1} 3 , the relation D ′ (C abc ) consits of all the facts in D(C abc ), plus a fact C abc (f , f , f ). It is

Figure 1 :

 1 Figure 1: The six valuations of the (non-uniform) incomplete database D = (T , dom) with T = {S(a, b), S(⊥ 1 , a), S(a, ⊥ 2 )} from Example 2.2, and their corresponding completions. The Boolean conjunctive query q is ∃x S(x, x).

  (a) Naïve tables where nulls are interpreted over a fixed domain, and (b) Codd tables. Proposition 4.5. We have that: (a) #Comp u (R(x, x)) and #Comp u (R(x, y)) are both #P-hard, even when nulls are interpreted over the same fixed domain {0, 1}. (b) #Comp u Cd (R(x, x)) and #Comp u Cd (R(x, y)) are #P-hard.

  Theorem 5.1 ([9, Corollary 3]). Every problem in SpanL has an FPRAS.

  Theorem 5.4 ([19, Theorem 3.1]). The problem #IS does not admit an FPRAS unless NP = RP.

Figure 2 :

 2 Figure2: A multigraph with an assignment µ. The edge µ(v) assigned to each node is indicated in orange next to each node. This assignment is avoiding because no edge is fully orange.

  Counting matchings is exactly the problem Holant([1, 1, 0]|[1, 1, 0, 0]); • Counting edge covers is exactly the problem Holant([0, 1, 1]|[0, 1, 1, 1]).

  which concludes the proof. □ B PROOFS FOR SECTION 4 (DICHOTOMIES FOR COUNTING COMPLETIONS) B.1 Proof of Lemma 4.1

Definition B. 7 .

 7 Let M = (E, I) be a matroid. The Tutte polynomial of M, denoted T(M; x, y), is the two-variables polynomial defined byT(M; x, y) = A ⊆E (x -1) rk(M )-rk(A) (y -1) |A |-rk(A)We will use the following observation: Observation B.8. Let M = (E, I) be a matroid. Then T(M; 2, 1) = |I|, i.e., evaluating the Tutte polynomial of a matroid at point (2, 1) simply counts its number of independent sets.Proof. We have T(M; 2, 1) = A ⊆E 0 |A |-rk(A) . We recall the convention that 0 0 = 1, and the fact that 0 k = 0 for k > 0. Observe then that we always have rk(A) ⩽ |A|, and that we have rk(A) = |A| if and only if A ∈ I, which proves the claim. □ Next, we define what is called the bicircular matroid of a graph G = (V , E). Recall from Section B.4 the definition of the induced subgraph G[S] for S ⊆ E. Definition B.9. Let G = (V , E) be a graph and I = {S ⊆ E | G[S] is a pseudoforest}. Then one can check that (E, I) is a matroid [55]. This matroid is called the bicircular matroid of G, and is denoted by B(G).

Proposition B. 10 (

 10 [START_REF] Giménez | On the complexity of computing the Tutte polynomial of bicircular matroids[END_REF] Corollary 4.3]). The problem of computing, given a graph G, the quantity T(B(G); 1, 1) is #P-hard.Second, let us define the following univariate polynomial: for a graph G, let P G (x) be P G (x) = T(B(G); x, 1).

B. 6 . 1

 61 Warm-up example 1: #Comp u (R(x)) without constants. The database D consists of the facts {R(⊥ 1 ), . . . , R(⊥ n R )}. If n R = 0 then the result is 1 (the empty completion), so let us assume n R ⩾ 1. Notice then that for every subset I R ⊆ dom, the database {R(a) | a ∈ I R } is a completion of D if and only if we have 1

and n R ⩾ 1 then 0 otherwise 1 .B. 6 . 2

 162 Warm-up example 2: #Comp u (R(x)) with constants. Let D be the database {R(a 1 ), . . . , R(a c R ), R(⊥ 1 ), . . . , R(⊥ n R )}, and let C R = {a 1 , . . . , a c R } be the set of constants. First, observe that we can assume wlog that C R ⊆ dom; indeed, letting D ′ be the incomplete database obtained from D by removing all the facts R(a) for which a ∈ C R \ dom, then D and D ′ actually have the same number of completions. Moreover, we can assume that c R ⩾ 1, otherwise we are in the previous example. Then, observe that for every subset I R ⊆ dom \ C R , the database {R(a) | a ∈ I R or a ∈ C R } is a completion of D if and only if we 0

  a) D ′ }, I S def = {a ∈ dom | S(a) ∈ D ′ , R(a) D ′ }, and I RS def = {a ∈ dom | {R(a), S(a)} ⊆ D ′ }. Then D ′ is a completion of D if and only if we have |I

Figure 4 :

 4 Figure 4: How the sets dom, I R , I S , I RS , C RS , C R and C S from Claim B.13 are allowed to intersect when they satisfy (⋆). The sets themselves and the intersections can be empty.

□

  Using this, we have that the value of check(I R , I S , I RS ) only depends on the sizes of I R , I S , I RS , and moreover can be computed in polynomial time Claim B.16. The value of check(I R , I S , I RS ) only depends on |I R |, |I S |, |I RS |, n R , n S , n RS , c R , c S , c RS , and can be computed in P.

  N s for every s ∈ A and a variable z A,A ′ C s for every s ∈ A ′ . For instance if σ = {R, S,T , U } and if A = {{R, S }, {S,T }} and A ′ = {{U }} we have the variables z { {R,S }, {S,T } }, { {U } } N {R, S } and z { {R,S }, {S,T } }, { {U } } N {S,T } and z { {R,S }, {S,T } }, { {U } } C {U } . The intuition is that we will use z { {R,S }, {S,T } }, { {U } } N {R, S } of the nulls in N {R,S } and combine them with z { {R,S }, {S,T } }, { {U } } N {S,T } of the nulls in N {S,T } and with z { {R,S }, {S,T } }, { {U } } C {U }

  we do not use more nulls and constants than there are available.• for every ∅ s ⊆ σ we have a constraintA,A ′ ⊆ { ∅ s⊆σ } A∪A ′ =s min z A, A ′ * ∈V z A,A ′ * ⩾ I s

  3. □ C PROOFS FOR SECTION 5 (APPROXIMATING THE NUMBERS OF VALUATIONS AND COMPLETIONS) C.1 Proof of Proposition 5.2

3 .

 3 Its schema σ = {S } ∪ {C abc | (a, b, c) ∈ {0, 1} 3 } consists of 10 relation symbols, with S being binary and each C abc being ternary. Let us denote by #Comp u (σ ) the problem that takes as input an incomplete database over schema σ and outputs its number of completions. The first part of our proof is to reduce #Comp u (σ ) to #Comp u (q): Lemma D.1. We have that #Comp u (σ ) ⩽ p par #Comp u (q).

  table D as described above. Then B calls A with input (D, 1 /16), and if A(D, 1 /16) ⩾ 7.5, then B accepts, otherwise B rejects. We now prove that B is indeed a BPP algorithm for 3-colorability. Assume first that G is 3-colorable. Then by (b) and by definition of what is an FPRAS, we have that Pr |8-A(D, 1 /16)| ⩽ 8 /16 ⩾ 3 4 . This implies in particular that Pr A(D, 1 /16) ⩾ 8-8 /16 ⩾ 3 4 . Since 8 -8 /16 = 7.5 we conclude that if G is 3-colorable, then B accepts with probability at least 3 /4. Next, assume that G is not 3colorable. Then by (c) we have that Pr |7 -A(D, 1 /16)| ⩽ 7 /16 ⩾ 3 4 . This implies in particular that Pr A(D, 1 /16) ⩽ 7 + 7 /16 ⩾ 3 4 . Since 7 + 7 /16 < 7.5, this implies in particular that Pr A(D, 1 /16) < 7.5 ⩾ 3 4 . From this, we conclude that if G is not 3-colorable, then B rejects with probability at least 3 /4. This concludes the proof of the proposition.

  1 , . . . , s L ) (in other words, all the sets I s are mutually disjoint subsets of dom, and a set I s can only contain a constant b ∈ C if b is in one of the sets C s ′ for which s ′ is striclty included in s), let us define P(I s 1 , . . . , I s L ) to be the complete database consisting of the following facts, for every ∅ s ⊆ σ :• R(a) for every R ∈ s and a ∈ I s and a ∈ C s \ s⊋s ′ I s ′ Then, for every two such tuples (I s 1 , . . . , I s L ) and (I ′ s 1 , . . . , I ′ s L ) satisfying (⋆) and that are distinct, we have that P(I s 1 , . . . , I s L ) P(I ′ s 1 , . . . , I ′ s L ).

  It is then routine to check that (I s 1 , . . . , I s L ) satisfies (⋆) and is such that D ′ = P(I s 1 , . . . , I s L ). □ Lemma B.17 and B.18 allows us to express the result asI s 1 ⊆dom\C . . . I s j ⊆(dom\(C∪ 1⩽k < j I s k ))∪ ∅ s ′ ⊊s C s ′ . . . I s L ⊆dom\(C s L ∪ 1⩽k <L I s k ) check(I s 1 , . . . , I s L )(6)where check(I s 1 , . . . , I s L ) ∈ {0, 1} is defined by check(I s 1 , . . . , I s L ) s 1 , . . . , I s L ) is a completion of D that satisfies q 0 otherwise . As such we cannot evaluate this expression in P. The next step is to show that the value of check(I s 1 , . . . , I s L ) only depends on (|I s 1 |, . . . , |I s L |), which would allow us to rewrite the result as 0⩽i s 1 , ...,i s L ⩽d 1⩽j ⩽L dc -1⩽k <j i s k + ∅ s ′ ⊊s C s ′ i s j × check(i s 1 , . . . , i s L )

def = 1 if P(I

We remind the reader that we assume all sjfBCQs to contain at least one atom and that all atoms must contain at least one variable.

Note that in the sum we do not need to specify that m ′ + r ′ ⩽ n R , as when a < b we have surj a→b = 0.

As a matter of fact, this holds even for the larger class of unions of BCQs with inequalities (that is, atoms of the form x y), as such queries also satisfy the aforementioned three properties.

Recall that UP is the class Unambiguous Polynomial-Time introduced in[START_REF] Valiant | Relative complexity of checking and evaluating[END_REF], and that L ∈ UP if and only if there exists a polynomial-time nondeterministic Turing Machine M such that if x ∈ L, then accept M (x ) = 1, and if x L, then accept M (x ) = 0.

Where we write, for instance, R ′ (y, x ), to mean that the first attribute of R is a primary key.

This observation, and in fact the idea of reducing from #BIS, is due to Antoine Amarilli.

To be precise, we use Equations (7.1) and (7.2) of[START_REF] Jaeger | On the computational complexity of the Jones and Tutte polynomials[END_REF] with x = 1, y = 0, and Equation (2.2) with x = 2, y = 1.

This is because, since B(G) is a matroid, any two such pseudoforests have the same number of edges. We can then simply start from the empty subgraph and iteratively add edges until it is not possible to add an edge such that the resulting graph is a pseudoforest. This also relies on the fact that we can check in polynomial time whether a graph is a pseudoforest.

With the convention that a b = 0 when b > a.

In fact, the class GapSpanP is defined in[START_REF] Mahajan | A note on SpanP functions[END_REF], where it is proved that a function f is in GapSpanP if and only if f = дh, where h, д are functions in SpanP. Then it is shown in[START_REF] Mahajan | A note on SpanP functions[END_REF] Corollary 3.5] that the inclusion GapSpanP ⊆ GapP implies that NP ⊆ SPP. But if we have that SpanP ⊆ GapP, then we also have that GapSpanP ⊆ GapP as GapP is closed under subtraction and, therefore, we conclude that NP ⊆ SPP as desired.

To see that[START_REF] Maslowski | A dichotomy in the complexity of counting database repairs[END_REF] establishes the hardness of q = R ′ (y, x ) ∧ S ′ (z, x ), first apply their rewrite rule R7 (from Fig.6) to obtain q ′ = R ′ (y, x ) ∧ S ′ (x, x ), then apply rewrite rule R10 to obtain q ′′ = R ′ (y, x ) ∧ S ′ (x, a). Then, q ′′ is #P-hard by Lemma 19, and so is q by Lemma 7.

ACKNOWLEDGMENTS

The third author would like to thank Antoine Amarilli for reminding him of the paper [13] in [41] and for suggesting to use #BIS in the proof of Proposition 3.11. This work was partly funded by the Millennium Institute for Foundational Research on Data (IMFD).

Proof. The reduction is exactly the same as the one of Lemma 3.3. To show that this reduction works properly for counting completions, it is enough to observe that for every valuations ν 1 , ν 2 of D ′ , we have that ν 1 (D ′ ) = ν 2 (D ′ ) iff ν 1 (D) = ν 2 (D). □

B.2 Proof of Proposition 4.4

Theorem 4.4 (Dichotomy). For every sjfBCQ q, the problem #Comp Cd (q) is #P-complete.

Proof. Hardness is from Theorem 4.3. To show membership in #P we will actually prove a more general result, which we prove in Appendix B. [START_REF] Adam | Number of surjective functions[END_REF]. There, we show that for every Boolean query q such that q has model checking in P the problem #Comp Cd (q) is in #P. This in particular applies to all sjfBCQs. □ B.3 Proof of membership in #P of #Comp Cd (q)

We recall that the model checking of a Boolean query q is the problem of deciding, given a (complete) database D, whether D |= q. In this section, we call a fact that contains only constants a ground fact. Our goal here is to prove the following.

Proposition B.1. If a Boolean query q has model checking is in P, then we have that #Comp Cd (q) is in #P.

To show this, we first prove that we can check in polynomial time if a given set of ground facts is a possible completion of an incomplete database: Lemma B.2. Given as input an incomplete Codd table D and a set S of ground facts, we can decide in polynomial time whether there exists a valuation ν of D such that ν(D) = S.

Proof. For every fact f of D, let us denote by P(f ) the set of ground facts that can be obtained from f via a valuation (P(f ) can be { f } if f is already a ground fact). The first step is to check that for every fact f of D, it holds that (⋆) P(f ) ∩ S ∅. If this is not the case, then we know for sure that for every valuation ν of D we will have ν (D) ⊈ S, so that we can safely reject. Next, we build the bipartite graph G D,S defined as follows: the nodes in the left partition of G D,S are the facts of D, the nodes in the right partition are the facts in S, and we connect a fact f of D with all the ground facts in the right partition that are in S ∩ P(f ). It is clear that we can construct G D,S in polynomial time. We then compute in polynomial time the size m of a maximum-cardinality matching of G D,S , for instance using [START_REF] Edmonds | Paths, trees, and flowers[END_REF]. It is clear that we have m ⩽ |S |. At this stage, we claim that there exists a valuation ν of D such that ν(D) = S if and only if m = |S |. We prove this by analysing the two possible cases:

• If m < |S |, then let us show that there is no such valuation. Indeed, assume by way of contradiction that such a valuation ν exists. Let B be a subset of D of minimal size such that ν(B) = S. It is clear that such a subset exists, and moreover that its size is exactly |S |.

But then, consider the set M of edges of G D,S defined by

contradicting the fact that m is the size of a maximum-cardinality matching. • If m = |S |, let us show that such a valuation exists. Let M be a matching of G D,S of size |S |. By the pigeonhole principle, it is clear that every node corresponding to a ground fact f ∈ S is incident to (exactly) one edge of M; let us denote that edge by e f . Moreover, since M is a matching, the mapping that associates to a ground fact f ∈ S the fact f ′ f at the other end of e f is injective. Hence, we can define ν(⊥) of every null ⊥ occurring in such a fact f ′ f ∈ D to be the unique constant such that ν (f ′ f ) = f holds, and for every other fact f ′ in D not incident to an edge in M, we chose a value for its nulls so that ν (f ′ ) ∈ S, which we can do thanks to (⋆). It is then clear that we have ν (D) = S.

But then, we can simply accept if m = |S | and reject otherwise. □

We can now prove Proposition B.1:

Proof of Proposition B.1. We define a non-deterministic turing machine M q such that, on input incomplete Codd table D, its number of accepting computation paths is exactly the number of completions of D that satisfy q. First, compute in polynomial time the set A def = f ∈D P(f ), where P(f ) is defined just as in Lemma B.2. Then, the machine M q guesses a subset S of A. It then checks in polynomial time if S, when seen as a database, satisfies q, and rejects if it is not the case. Then, using Lemma B.2, it checks in polynomial time whether there exists a valuation ν of D such that ν (D) = S, and accepts iff this is the case. It is then clear that M q satisfies the conditions, which shows that #Comp Cd (q) is in #P. □

B.4 Proof of Proposition 4.5, item (b)

In this section we prove point (b) of the following claim (we recall that (a) was proved in Section 4.2). But then this implies that the result can be expressed as

We cannot compute this expression as-is because we are summing over subsets of dom. However, since each subsum depends only on the sizes of the sets introduced before it, we can simplify this expression to

which we can compute in polynomial time. The result can also be expressed as the following expression which work for all n R , n S , n RS ∈ N:

where check

) without constants. We use again Equation 5, but to ensure that the query is satisfied we add that check(i R , i S , i RS ) becomes 0 when i RS = 0.

B.6.5 Warm-up example 5: #Comp u (R(x) ∧ S(y)) with constants. This example is much more involved, and we will mimick all the steps of the general proof. Let C RS , C R , C S (resp, N RS , N R , N S ) be the sets of constants (resp., nulls) that occur respectively: in R and in S, only in R, only in S, and denote c RS , c R , c S (resp., n RS , n R , n S ) their sizes. For the same reason as in warm-up example 2, we can assume wlog that Proof. We define:

; where we see D ′ (R) as the set of constants occurring in relation R of D ′ .

Then one can easily check that we have D ′ = P(I R , I S , I RS ). □

By combining these two claims, we have that the result that we wish to compute is equal to

easy to see that D and D ′ have the same number of completions. Moreover, thanks to the facts that use the constant f , we have that every completion of D ′ satisfies q. Therefore, we indeed have that #Comp u (σ )(D) = #Comp u (q)(D ′ ). □

For the second part of the proof, we need to introduce the complexity class GapP. This class consists of function problems that can be expressed as the difference of two functions in #P [START_REF] Fenner | Gap-definable counting classes[END_REF][START_REF] Gupta | Closure properties and witness deduction[END_REF]. It is known that if the inclusion SpanP ⊆ GapP holds, then we have that NP ⊆ SPP [START_REF] Mahajan | A note on SpanP functions[END_REF]. 10 With this, we are able to prove the proposition.

Proof of Proposition 6.1. Assume that #Comp u (q) is in #P. Then, by Lemma D.1 we have that #Comp u (σ ) ∈ #P as well (because #P is closed under polynomial-time parsimonious reductions). Now, observe that for every incomplete database D over σ , the following holds:

But then this means that #Comp u (¬q) is in GapP (since both problems in the right hand side are in #P). Since #Comp u (¬q) is SpanP-complete by Theorem 6.3 under polynomial-time parsimonious reductions, and since GapP is closed under polynomial-time parsimonious reductions, this would indeed imply that SpanP ⊆ GapP and, hence, that NP ⊆ SPP. □ D.2 Proof of Theorem 6.3

Theorem 6.3. There exists an sjfBCQ q such that #Comp u (¬q) is SpanP-complete under polynomial-time parsimonious reductions.

Proof. Notice that we only need to show that #Comp u (¬q) is SpanP-hard under parsimonious reductions, for a fixed sjfBCQ q. In this proof, we reduce from counting the number of satisfying assignments of a 3-CNF formula that are distinct in the first k variables, that we denoted by #k3SAT: Definition D.2. The problem #k3SAT takes as input a 3-CNF formula F on variables {x 1 , . . . , x n } and an integer 1 ⩽ k ⩽ n, and outputs the number of assignments of the first k variables that can be extended to a satisfying assignment of F .

Proposition D.3 ([34, Section 6]). #k3SAT is SpanP complete (under polynomial-time parsimonious reductions).

We reduce from #k3SAT to #Comp u (¬q), for a fixed sjfBCQ q to be defined. Let F be a 3-CNF on variables {x 1 , . . . , x n }, and 1 ⩽ k ⩽ n. We first explain how we build the incomplete database D, and we will define the sjfBCQ q after. For every variable x i , 1 ⩽ i ⩽ n, we have a null ⊥ x i , and the (uniform) domain is {0, 1}. For (a, b, c) ∈ {0, 1} 3 , we have a relation C abc of arity 3, and we fill it with every tuple of the form C abc (a ′ , b ′ , c ′ ) with (a ′ , b ′ , c ′ ) ∈ {0, 1} 3 such that a = a ′ ∨ b = b ′ ∨ c = c ′ holds; hence for every (a, b, c) ∈ {0, 1} 3 there are exactly 7 facts of this form. For every clause K = l 1 ∨ l 2 ∨ l 3 of F with l 1 , l 2 , l 3 being literals over variables y 1 , y 2 , y 3 , letting (a 1 , a 2 , a 3 ) ∈ {0, 1} 3 be the unique tuple such that a i = 1 iff l i is a positive literal, we add to C a 1 a 2 a 3 the fact C a 1 a 2 a 3 (⊥ y 1 , ⊥ y 2 , ⊥ y 3 ). Last, we have a binary relation S that we fill with the tuples S(i, ⊥ x i ) for 1 ⩽ i ⩽ k. The sjfBCQ q then simply says that there exists a tuple that appears in all the relations C abc :

Note that we added the seemingly useless query ∃x∃y S(x, y) to q because the set of relations in D has to be equal to the set of relations occurring in q. We now show that the number of completions of D that do not satisfy q is equal to the number of assignments of the first k variables that can be extended to a satisfying assignment of F , thus establishing that #Comp u (¬q) is SpanP-hard (under polynomial-time parsimonious reductions). First, observe that the assignments of the variables are in bijection with the valuations of the nulls of D. One can then readily observe the following:

• If q is falsified in a completion of D, it can only be because there does not exist a tuple that occurs in all the relations; this is because the query ∃x, y S(x, y) is always satisfied by any completion of D. • For every assignment of the variables, letting ν be the corresponding valuation of the nulls, there exists a tuple that is in all relations C abc of ν (D) if and only if that assignment is not satisfying for F . Indeed, one can check that this happens if and only if there exists a relation C abc such that ν (D)(C abc ) contains exactly 8 facts. • For every two valuations ν, ν ′ such that the corresponding assignments are not satisfying the query, we have that ν (D) ν ′ (D) if and only if ν and ν ′ differ on the first k variables. This is because, by the previous item, each relation C abc contains exactly the 7 ground tuples that we initially put in D.

By putting it all together, we obtain that the reduction works as expected. □ D.3 Proof of Theorem 6.4

Theorem 6.4. If q is a Boolean query with MC(q) ∈ NP, then both #Val(q) and #Comp(q) are in SpanP. Moreover, there exists such a Boolean query q for which #Val u (q) is SpanP-complete under polynomial-time parsimonious reductions (and for #Comp u (q), we can even take q to be the negation of an sjfBCQ, hence with model checking in P, as given by Theorem 6.3).

Proof. It is straightforward to prove that these problems are in SpanP. The part in between parenthesis has been shown in theorem 6.3. Thus, we need to prove that #Val u (q) is SpanP-hard for a fixed Boolean query q such that MC(q) ∈ NP, under polynomial-time parsimonious reductions. To do this, we will reduce from the SpanP-complete problem #HamSubgraphs, defined as follows: Next we show that #HamSubgraphs ⩽ p par #Val u (q), for a fixed Boolean query q (to be defined). Let G = (V , E) be an undirected graph. We first explain how we construct the incomplete database D, and we will then define the query q. The schema contains two binary relation symbols R,T and one unary relation symbol K. Fix a linear order a 1 , . . . , a n of the nodes of G. For every edge {u, v} ∈ E we have the facts R(u, v) and R(v, u). For 1 ⩽ i ⩽ n we have a fact T (a i , ⊥ i ), and the domain of the nulls is {0, 1}. For 1 ⩽ j ⩽ k we have a fact K(j). Observe that D is a Codd table. We now define the Boolean query q, which will be a sentence in existential second-order logic (∃SO) over relational signature R,T , K. Before doing so, we explain the main idea: intuitively, q will check that there are exactly k facts of the form T (a i , 1) in the relation T and that, letting S be the set of nodes v such that T (v, 1) is in relation T , the induced subgraph G[S] is Hamiltonian. This will indeed ensure that we have #Val u (q)(D) = #HamSubgraphs(G, k), thus completing this reduction, which is parsimonious and can be performed in polynomial-time. The query is

where S is a unary second order variable and the formula ψ 1 (S) states that (a) the elements s of S are exactly all the elements such that T (s, 1) holds, and that (b) there are exactly the same number of elements in S as there are elements j for which K(j) holds. It is clear that (a) can be expressed in FO. Moreover, (b) can be expressed in ∃SO by asserting the existence of a binary second-order relation U that represents a bijective function from S to the elements in K. Then ψ 2 (S) is a formula that asserts that G[S] is Hamiltonian. Since this is a property in NP, ψ 2 (S) can be expressed in ∃SO by Fagin's theorem (see, e.g., [START_REF] Immerman | Descriptive complexity[END_REF]). This shows that the reduction is correct. Finally, the fact that MC(q) is in NP again follows from Fagin's theorem. This concludes the proof. □ E PROOFS FOR SECTION 7 (RELATED WORK) E.1 Alternative proof of Proposition 3.5 using #Repairs

In this section we explain how Proposition 3.5, i.e., the #P-hardness of #Val Cd (R(x) ∧ S(x)), can be deduced from the hardness of the problem #Repairs(R ′ (y, x) ∧ S ′ (z, x)), which was established in [START_REF] Maslowski | A dichotomy in the complexity of counting database repairs[END_REF]. 11 Let D ′ be a database with binary relation R ′ , S ′ . We construct an incomplete Codd database D with unary relations R, S as follows. For every constant a that appears in the first attribute of R ′ , we have a tuple R(⊥) in D ′ , where ⊥ is a fresh null, and we set dom(⊥) = {b | R ′ (a, b) ∈ D ′ }. For every constant a that appears in the first attribute of S ′ , we have a tuple S(⊥) in D ′ , where ⊥ is a fresh null, and we set dom(⊥) = {b | S ′ (a, b) ∈ D ′ }. It is then clear that the number of repairs of D ′ that satisfy R ′ (y, x) ∧ S ′ (z, x) is equal to the number of valuations of D that satisfy R(x) ∧ S(y).