The complexity of counting problems over incomplete databases]The Complexity of
Counting Problems
over Incomplete Databases

Marcelo Arenas
Universidad Católica & IMFD Chile

Department of Computer Science & Institute for Mathematical and Computational Engineering, School of Engineering,
Pontificia Universidad Católica de Chile

Pablo Barceló
Universidad Católica & IMFD Chile

Institute for Mathematical and Computational Engineering, School of Engineering and Faculty of Mathematics, Pontificia
Universidad Católica de Chile

Mikaël Monet

Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France

We study the complexity of various fundamental counting problems that arise in
the context of incomplete databases, i.e., relational databases that can
contain unknown values in the form of labeled nulls. Specifically, we assume
that the domains of these unknown values are finite and, for a Boolean
query $q$, we consider the following two problems: given as input an incomplete
database $D$, (a) return the number of completions of $D$ that satisfy $q$; or
(b) return the number of valuations of the nulls of $D$ yielding a
completion that satisfies $q$.  We obtain dichotomies between #P-hardness and
polynomial-time computability for these problems when $q$ is a self-join–free
conjunctive query, and study the impact on the complexity of the following two
restrictions: (1) every null occurs at most once in $D$ (what is called
Codd tables); and (2) the domain of each null is the same.  Roughly
speaking, we show that counting completions is much harder than counting
valuations: for instance, while the latter is always in #P, we prove that the
former is not in #P under some widely believed theoretical complexity
assumption. Moreover, we find that both (1) and (2) can reduce the complexity
of our problems. We also study the approximability of these problems and show
that, while counting valuations always has a fully polynomial-time randomized
approximation scheme (FPRAS), in most cases counting completions does not.
Finally, we consider more expressive query languages and situate our problems
with respect to known complexity classes.

2021 1 1 1 1 15.0010.1145/3461642

<concept_desc>Theory of computation Complexity theory and logic</concept_desc>
<concept_desc>Theory of computation Incomplete, inconsistent, and uncertain databases</concept_desc>
<concept_desc>Mathematics of computing Approximation algorithms</concept_desc>

[500]Theory of computation Complexity theory and logic
[500]Theory of computation Incomplete, inconsistent, and uncertain databases
[300]Mathematics of computing Approximation algorithms

§ INTRODUCTION

In the database literature, incomplete databases are often used to
represent missing information in the data; see,
e.g., <cit.>.
These are traditional relational databases whose active domain can contain both
constants and nulls, the latter representing unknown
values <cit.>.  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 closed-world
assumption <cit.>, a standard,
complete database $\nu(D)$ is obtained from an incomplete database $D$ by
applying a valuation $\nu$ which replaces each null $\bot$ in $D$ with a
constant $\nu(\bot)$.  The goal is then to reason about the space formed by all
valuations $\nu$ and completions $\nu(D)$ of $D$.

Decision problems related to querying incomplete databases have been well
studied already.  Consider for instance the problem Certainty$(q(\bar{x}))$ which, for a fixed query $q(\bar{x})$, takes as input
an incomplete database $D$ and a tuple $\bar{a}$ and asks whether $\bar{a}$ is
an answer to $q$ for every possible completion 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 <cit.>.  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
<cit.> does by introducing a notion of best answer,
which are those tuples $\bar a$ for which the set of completions of $D$ over
which $q(\bar a)$ 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 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 <cit.>.  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

Problems studied
We focus on the problems $(q)$ and $(q)$ for a Boolean
query $q$, which take as input an incomplete database $D$ together with a
finite set $\dom(\bot)$ of constants for every null $\bot$ 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 $\nu$ that
associates to every null $\bot$ of $D$ a constant $\nu(\bot)$ in $\dom(\bot)$.
Then, given a valuation $\nu$ of $D$, we denote by $\nu(D)$ the database that
is obtained from $D$ after replacing each null $\bot$ with $\nu(\bot)$, and we
call such a database a completion.  Besides, in this article we consider
set semantics, that is, we remove repeated tuples from $\nu(D)$.
For $(q)$ we count all databases of the form $\nu(D)$ such that $q$
holds in $\nu(D)$. Instead, for $(q)$ we count the number of
valuations $\nu$ such that $q$ holds in $\nu(D)$. It is easy to see that these
two values can differ, as a completion might be obtained from two different
valuations, i.e., there might exist two distinct valuations $\nu,\nu'$ such
that $\nu(D) = \nu'(D)$. We think that both problems are meaningful: while
$(q)$ determines the support for $q$ over the databases represented
by $D$, we have that $(q)$ further refines this by incorporating the
support for a particular completion that satisfies $q$ over the set of
valuations for $D$.

2 c| Counting valuations     2 c| Counting completions

Non-uniform     Uniform     Non-uniform     Uniform

$R(x) \land  S(x)$

$R(x) \land S(x,y) \land T(y)$
$R(x,y) \land S(x,y)$

$R(x) \land S(x)$

$R(x) \land S(x,y) \land T(y)$
$R(x,y) \land S(x,y)$

Our dichotomies for counting valuations and completions of . For each of the eight cases, if an  $q$ contains a pattern mentioned in that case, then the problem is -hard (and -complete for counting valuations, as well as for counting completions over Codd tables). In turn, for each case
if an  $q$ does not have any of the patterns mentioned in that case, then the problem is in .

2 c| FPRAS for counting valuations     2 c| FPRAS for counting completions

Non-uniform     Uniform     Non-uniform     Uniform

Only when $q$ has

only unary atoms

Our results on the existence of FPRAS for solving the problems studied in the article (assuming $\np \neq \rp$).

We deal with the data complexity of the problems $(q)$ and
$(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
(). This assumption simplifies the mathematical analysis, while at the
same time 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., <cit.>. To simplify further the presentation, in the bulk of the article
we mainly consider self-join–free Boolean conjunctive queries that do not contain constants; however, we explain later (in Section <ref>)
how our results can be extended to queries that can contain constants and free variables.

To refine our analysis, we study two restrictions of the problems
$(q)$ and $(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 naive tables where nulls are allowed to have
multiple occurrences. We denote the corresponding problems by $\ccountvals(q)$
and $\ccountcompls(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 $\ucountvals(q)$
and $\ucountcompls(q)$.  When both restrictions are in place, we denote the
problems by $\cucountvals(q)$ and $\cucountcompls(q)$.

Our dichotomies for exact counting We provide
complete characterizations of the complexity of counting valuations and
completions satisfying a given  $q$, when the input is a Codd table or
a naive table, and is a non-uniform or a uniform incomplete database (hence we
have eight cases in total).
Our eight dichotomies express that these problems are  either tractable
or -hard, and that the tractable cases can be fully characterized by the
absence of certain forbidden patterns in $q$. In essence, a pattern is
simply an  which can be obtained from $q$
by deleting atoms
and occurrences of variables (the exact definition of this notion is given in
Section <ref>).  Our characterizations are presented in
Table <ref>.  By analyzing this table we can draw some
important conclusions as explained next.

$(q)$ and $(q)$ are computationally
difficult: For very few  $q$  the aforementioned problems can be
solved in polynomial time. Take as an example the uniform setting over naive
tables.  Then $(q)$ is -hard as long as $q$ contains the
pattern $R(x,x)$, or $R(x)\land S(x,y)\land T(y)$, or $R(x,y) \wedge 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, $(q)$ is -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.

$(q)$ is always easier than $(q)$:
In all of the possible versions of our problem, the tractable cases for
$(q)$ are a strict superset of the ones for $(q)$. For
instance, $\cucountcompls(\exists x \exists y\, R(x,y))$ is hard, while
$\cucountvals(\exists x \exists y\, R(x,y))$ is tractable.

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 <ref> that the
problem $\cucountcompls(\exists x \exists y\, R(x,y))$ is -hard, and thus
that simply counting the completions of a uniform Codd table with a single
binary relation $R$ is -hard.  Moreover, we show that in the non-uniform
case a single unary relation suffices to obtain -hardness.

Codd tables help but not much: We show that counting
valuations is easier for Codd tables than for naive tables. In particular,
there is always an  $q$ such that counting  the valuations that
satisfy $q$ is -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  $q$, we have that $\countcompls(q)$ (resp.,
$\ucountcompls(q)$) is -hard if and only if  $\ccountcompls(q)$ (resp.,
$\cucountcompls(q)$) is -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  $q$ for which counting valuations is tractable on
uniform incomplete databases, but becomes -hard assuming non-uniformity,
and the same holds for counting completions.

Our dichotomies for approximate counting
Although $(q)$ can be -hard, we prove that good
randomized approximation algorithms can be designed for this problem.  More
precisely, we give a general condition under which $\countvals(q)$ admits a
fully polynomial-time randomized approximation
scheme <cit.> (FPRAS).  This condition applies in particular
to all unions of Boolean conjunctive queries.  Remarkably, we show that
this no longer holds for $(q)$; more precisely, there exists an
$q$ such that $(q)$ does not admit an FPRAS under a widely
believed complexity theoretical assumption. More surprisingly, even counting
the completions of a 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 ,
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 completely solve is that of $\cucountcompls(q)$.  Our
dichotomies for approximate counting are illustrated in
Table <ref>.

It is easy to see that the problem of counting valuations is always in ,
provided that the model checking problem for $q$ is in .  This is no
longer the case for counting completions, and in fact we show that, under a
complexity theoretical assumption, there is an  $q$ for which
$(q)$ is not in .  This does not hold if restricted to Codd
tables, however, as we prove that $(q)$ is always in  when
the model checking problem for $q$ is in .

For reasons that we explain in the article, a suitable complexity class for the
problem $(q)$ is , 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  $q$ for which $(q)$
is -complete, we show that this is the case for the problem
of counting completions for the negation of an , even in the uniform
setting; that is, we show that $(\neg q)$ is -complete for
some  $q$. Finally, we also show that  is the right complexity
class for counting valuations of queries for which model checking is in .

Extension to queries with constants and free variables.

As we said already, for pedagogical reasons we mostly present our results by
considering queries that are Boolean and that do not have constants.  In
Section <ref> however, we explain how to extend these results to
the case of queries that have free variables and that can contain constants.
For the case of a query $q(\bar x)$ with free variables $\bar x$, our counting
problems are defined in the expected way; for instance the
problem $\countvals(q(\bar x))$ takes as input an incomplete database $D$, a
tuple of constants $\bar a$ of same arity as $\bar x$, and it outputs the
number of valuations $\nu$ of $D$ such that $\bar a$ in an answer to $q(\bar
x)$ on $\nu(D)$. We then extend our dichotomies and approximation results in
this setting.

The current article extends the conference article <cit.> in the following ways:

* In <cit.> we left open the dichotomy for $\cucountvals(q)$, i.e., for counting valuations of  for Codd tables under the uniform setting.
We close this case here, by finding one more hard pattern (namely, the pattern $\exists x,y \, R(x,y) \land S(x,y)$) and showing that the problem can be solved in polynomial time for all other queries.

* We added Section <ref> which explains how our framework can be extended to handle queries with constants and free variables;

* Proposition <ref>, which establishes the -completeness of checking if a set of facts is a possible completion of an incomplete database, is new;

* Finally, full proofs of most results are included in the body of the article.

Organization of the article

We start with the main terminology used in the article in
Section <ref>, and then present in
Section <ref> our four dichotomies on $(q)$
when $q$ is an , 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 $(q)$ in Section <ref>. In
Section <ref>, we study the approximability complexity of our
problems. We then give in Section <ref> some general considerations
about the exact complexity of the problem $(q)$ going beyond .
We explain in Section <ref> how to extend our results to queries
with constants and free variables. In Section <ref>, we discuss
related work and explain the differences with the problems considered in this
article. Last, we provide some conclusions and mention possible directions for
future work in Section <ref>.

§ PRELIMINARIES

Relational databases and conjunctive queries
A relational schema $\sigma$ 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 $\sigma$ is a set of facts of the
form $R(a_1, \ldots, a_{\arity(R)})$ with $R \in \sigma$, and where each
element $a_i \in \consts$. For $R\in \sigma$, 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 \models q$) or not (written $D \not\models q$).
If $q$ is a Boolean query, then $\lnot q$ is the Boolean query such that $D\models \lnot q$
if and only if $D\not\models q$.
A Boolean
conjunctive query (BCQ) over $\sigma$ is an FO formula of the form

\begin{equation} \label{eq:cq}  \exists \bar x \, \big(R_1(\bar x_1) \land   \,
\dots \, \land R_m(\bar x_m)\big), \end{equation}
where all variables are
existentially quantified, and where for each $i \in [1,m]$, we have that $R_i$
is a relation symbol in $\sigma$ and $\bar x_i$ is a tuple of variables with
$|\bar x_i| = \arity(R_i)$.  To avoid trivialities, we will always assume
that $m \geq 1$, i.e., the query has at least one atom, and also
that $\arity(R_i) \geq 1$ for all atoms.
Observe that we do not allow constants to appear in the query (but we will come back to this issue in Section <ref>).
For simplicity, we typically write a
BCQ $q$ of the form (<ref>) as
$$R_1(\bar x_1)  \land   \, \dots \, \land
R_m(\bar x_m),$$
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(\bar x_1)),\dots,R_m(h(\bar x_m))\} \subseteq D$.  Then, we have $D
\models q$ if there exists a homomorphism from $q$ to $D$.   A
self-join–free BCQ () 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
or marked nulls in the literature), which is disjoint with $\consts$. An
incomplete database over schema $\sigma$ is a pair $D = (T,\dom)$,
where $T$ is a database over $\sigma$ whose facts contain elements in $\consts
\cup \nulls$, and where $\dom$ is a function that associates to every
null $\bot$ occurring in $D$ a subset $\dom(\bot)$ 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 naive table <cit.>.

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 $\nu$ that maps each null $\bot$ occurring in $T$ to a
constant $\nu(\bot) \in \dom(\bot)$.  Such a valuation naturally defines a
completion of $D$, denoted by $\nu(T)$, which is the complete database
obtained from $T$ by substituting each null $\bot$ appearing in $T$
by $\nu(\bot)$.  It is understood, since a database is a set of facts,
that $\nu(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 <cit.>.
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$.

Let $D = (T,\dom)$ be the incomplete database consisting of the
naive table $T = \{S(\bot_1,\bot_1),S(a,\bot_2)\}$, and where $\dom(\bot_1) =
\{a,b\}$ and $\dom(\bot_2) = \{a,c\}$.  Let $\nu_1$ be the valuation
mapping $\bot_1$ to $b$ and $\bot_2$ to $c$.  Then $\nu_1(T)$ is
$\{S(b,b),S(a,c)\}$.  Let $\nu_2$ be the valuation mapping both $\bot_1$
and $\bot_2$ to $a$.  Then $\nu_2(T)$ is $\{S(a,a)\}$. On the other hand, the
function $\nu$ mapping $\bot_1$ and $\bot_2$ to $b$ is not a valuation of $D$,
because $b\notin \dom(\bot_2)$.

When every null occurs at most once in $T$, then $D$ is what is called a
Codd table <cit.>; for instance, the incomplete
database in Example <ref> is not a Codd table because $\bot_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 $\sigma$ and $\dom$ is a
subset of $\consts$. The difference now is  that a valuation $\nu$ of $D$ must
simply satisfy $\nu(\bot) \in \dom$ for every null of $D$.

We will often abuse notation and use $D$ instead of $T$; for instance, we
write $\nu(D)$ instead of $\nu(T)$, or $R(a,a) \in D$ instead of $R(a,a) \in
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 $\countvals(q)$, that count the number of valuations $\nu$
that yield a completion $\nu(D)$ satisfying a given BCQ $q$, and problems of
the form $\countcompls(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 <cit.> 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(\bot)$ 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 naive tables and a Boolean query $q$.

PROBLEM :     $\countvals(q)$

INPUT :     An incomplete database $D$ over $\sig(q)$

OUTPUT :     Number of valuations $\nu$ of $D$ with $\nu(D) \models q$

PROBLEM :     $\countcompls(q)$

INPUT :     An incomplete database $D$ over $\sig(q)$

OUTPUT :     Number of completions $\nu(D)$ of $D$ with $\nu(D) \models 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 naive table.  We then use
the terms $\ucountvals(q)$, $\ucountcompls(q)$ when restricted to the uniform
case, $\ccountvals(q)$, $\ccountcompls(q)$ when restricted to Codd tables, and
$\cucountvals(q)$, $\cucountcompls(q)$ when both restrictions are applied.

As we will see, even though the problems $(q)$ and $(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.
We illustrate this phenomenon in the following example.

Let $q$ be the Boolean conjunctive query $\exists x \, S(x,x)$,
and $D$ be the (non-uniform) incomplete database $D = (T,\dom)$, with $T \, =
\, \{S(a,b)$, $S(\bot_1,a),S(a,\bot_2)\}$,  $\dom(\bot_1)=\{a,b,c\}$ and
$\dom(\bot_2)=\{a,b\}$.  We have depicted in
Figure <ref> the six valuations of $D$ together with
the completions that they define.  Out of these six valuations $\nu$, only four
are such that $\nu(D) \models q$, so we have	$\countvals(q)(D) = 4$.
Moreover, there are only $3$ distinct completions of $D$ that satisfy $q$ –
because the first two are the same – so $\countcompls(q)(D) = 3$.

*Counting complexity classes.

Given two problems $A,B$, we write $A \leq_{\mathrm{T}}^{\mathrm{p}} B$
when $A$ reduces to $B$ under polynomial-time Turing reductions.  When both $A$
and $B$ are counting problems, we write $A \pr B$ when $A$ can be reduced
to $B$ under polynomial-time parsimonious reductions, i.e., when 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  when it can be solved in polynomial time.  We will
consider the counting complexity class  <cit.> of
problems that can be expressed as the number of accepting paths of a
nondeterministic Turing machine running in polynomial time.
Following <cit.>, we define #P-hardness using Turing
reductions.  It is clear that $\fp \subseteq \shp$. Moreover, this inclusion is
widely believed to be strict. Therefore, proving that a counting problem is
-hard implies that it cannot be solved in polynomial time under such an

§ DICHOTOMIES FOR COUNTING VALUATIONS

In this section, for a fixed  q, we study the complexity of the
problem of computing, given as input an incomplete database $D$, the number of
valuations $\nu$ of $D$ such that $\nu(D)$ satisfies $q$.  Recall that we have
four cases to consider for this problem depending on whether we focus on naive
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 ) or -hard in these
scenarios, depending on the shape of $q$.

To this end, the shape of an  $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.

Let $q,q'$ be .  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.[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.]

Recall that we always omit existential quantifiers in Boolean queries.
Then we have that $q' = R'(u,u,y) \land  S'(z)$ is a pattern of $ q = R(u,x,u)
\land  S'(y,y) \land  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) \land S'(y,y)$, reordering the variables in $R'(u,x,u)$ to
obtain $R'(u,u,x) \land S'(y,y)$, renaming variable $y$ into $z$ to
obtain $R'(u,u,x) \land S'(z,z)$, deleting the second variable occurrence
in $S'(z,z)$ to obtain $R'(u,u,x) \land S'(z)$, and finally renaming
variable $x$ into $y$ to obtain $q'$.

We point out that in Definition <ref>, the important parts are
those about deleting atoms and variable occurrences. The parts about reordering
variable occurences inside an atom and about renaming relations and variables
to fresh ones have obviously no effect on the complexity of the
problem[This is in particular because the conjunctive queries we
consider have no self-joins (otherwise, reordering variables inside an atom
could change the complexity).]; these are only here to allow us to formally
say, for instance, that “$R(x)$ is a pattern of $R(y)$”, or that “$S(x,u,x)$ is
a pattern of $T(w,z,z)$” (as these are, in essence, the same queries).

In the following general lemma, we show that if $q'$ is a pattern of $q$, then
each 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 naive tables under the non-uniform setting.

Let $q,q'$ be  such that $q'$ is a pattern of $q$.  Then we
have $\countvals(q') \pr \countvals(q)$.  Moreover, the same results hold if we
restrict to Codd tables, and/or to the uniform setting.

We first present the proof for $\countvals(q') \pr \countvals(q)$, that
is, for naive tables in the non-uniform setting.  First of all, observe that we
can assume without loss of generality that we did not reorder the variables in
the atoms nor renamed relation names or variables by fresh ones, because, as
mentioned above, this does not change the complexity of the
problem.[Formally, one can first check that we can assume without loss
of generality that $q'$ was obtained from $q$ by first deleting some atoms and
variable occurences to obtain a query $q''$, and then performing some renamings
and variable reorderings to obtain $q'$ (that is, we can always push the
renaming and reordering parts at the end of the transformation). But then,
since $\countvals(q'')$ and $\countvals(q')$ are obviously the same problem, we
can assume $q'=q''$.] We can then write $q$ as $R_1(\overline{x_1}) \land
\ldots \land  R_m(\overline{x_m})$ and $q'$ as $R_{j_1}(\overline{x'_{j_1}})
\land  \ldots \land  R_{j_p}(\overline{x'_{j_p}})$, where $1 \leq j_1 < \ldots
< j_p \leq m$ and $\overline{x'_{j_k}}$ is obtained from $\overline{x_{j_k}}$
by deleting some variable occurrences but not all[See
Footnote <ref>.], and the other atoms have been deleted.  Let $D'$
be an incomplete database input of $\countvals(q')$.  Let $A$ be the set of
constants that are appearing in $D'$ or are in a domain of some null occurring
in $D'$.  For $1 \leq k \leq p$, we construct the relation $D(R_{j_k})$ from
the relation $D'(R_{j_k})$.  Let us assume that $\overline{x_{j_k}}$ is the
tuple $(x_1, \ldots, x_r)$ (with some variables possibly being equal).  We
initialize $D(R_{j_k})$ to be empty, and then for every tuple $\overline{t'}$
in $D'(R_{j_k})$ we add to $D(R_{j_k})$ all the tuples $\overline{t}$ that can
be obtained from $\overline{t'}$ in the following way for $1 \leq i \leq r$:

a) If $x_i$ is a variable occurrence that has not been deleted from $\overline{x_{j_k}}$,
then copy the element (constant or null) of $\overline{t'}$ corresponding to that variable occurrence to the $i$-th position of $\overline{t}$;

b) Otherwise, if $x_i$ is a variable occurrence that has been deleted from $\overline{x_{j_k}}$,
then fill the $i$-th position of $\overline{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(\overline{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).
Hence, it only remains to be checked that $\countvals(q')(D') =
\countvals(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 $\nu$, we have $\nu(D') \models q'$
if and only if $\nu(D) \models q$.  Let $h'$ be a homomorphism from $q'$ to
$\nu(D')$ witnessing that $\nu(D') \models q'$ (i.e., we have $h'(q) \subseteq
\nu(D')$).  Then $h'$ can clearly be extended in the expected way into a
homomorphism $h$ from $q$ to $\nu(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 $\nu(D)$ witnessing that $\nu(D) \models
q$.  Then the restriction $h'$ of $h$ to the variables occurring in $q'$ is
such that $h(q') \subseteq \nu(D')$, hence we have $\nu(D') \models q'$.  This
concludes the proof for the case of naive tables in the non-uniform setting.
For the cases of Codd tables and/or for the uniform setting, the reduction is
exactly the same. Indeed, the domains of the nulls are unchanged, and it is
clear that the presented construction preserves the property of being a Codd

The idea is then to show the -hardness of our problems for some
simple patterns, which then we combine with
Lemma <ref> and with some tractability proofs to
obtain the desired dichotomies.  Our findings are summarized in the first two
columns of Table <ref> in the introduction.  We first
focus on the two dichotomies for the non-uniform setting in
Section <ref>, and then we move to the case of
uniform incomplete databases in Section <ref>. We
explicitly state when a -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(\bot)
\subseteq A$, for each null $\bot$ of $T$.

§.§ The complexity on the non-uniform case

In this section, we study the complexity of the problems
$\countvals(q)$ and $\ccountvals(q)$, providing dichotomy results in both
cases. We start by proving the -hardness results needed for these
dichotomies. We first show that $\countvals(R(x,x))$ is -hard by actually
proving that hardness holds already in the uniform case.

$\ucountvals(R(x,x))$ is -hard.
This holds even in the restricted setting in which all nulls are interpreted
over the same fixed domain $\{1,2,3\}$.

We reduce from the problem of counting the number of
$3$-colorings of a graph $G=(V,E)$, which is
-hard <cit.>.  For every node $v\in V$ we have a
null $\bot_v$, and for every edge $\{u,v\} \in E$ we have the
facts $R(\bot_v,\bot_u)$ and $R(\bot_u,\bot_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) \land S(x)$.	This time, we
can show -hardness of the problem even for Codd databases.

$\ccountvals(R(x) \land S(x))$ is -hard.

We start by recalling the setting of consistent query answering under key
constraints.  Intuitively, in this case we are given a set $\Sigma$ of keys
and a database $D$ that does not necessarily satisfy $\Sigma$. Then the task is
to reason about the set of all repairs of $D$ with respect to $\Sigma$
<cit.>.  In our context, this means that one wants to count the number of
repairs of $D$ with respect to $\Sigma$ that satisfy a given CQ $q$.  When $q$
and $\Sigma$ are fixed, we call this problem $\#$Repairs$(q,\Sigma)$;
see, e.g., <cit.>.  We formalize these notions below.

Here we focus on the case when $\Sigma$ is a set of primary keys.  Recall
that this means that each relation name $R \in  \sigma$ of arity $n$ comes
equipped with its own key, i.e., ${\sf key}(R) = A$, where $A = \emptyset$ or
$A = [1,\ldots,p]$ for some $p \in \{1,\dots,n\}$.  Henceforth, $D$ is inconsistent with respect to $\Sigma$ if there is a relation name $R \in
\sigma$ and facts $R(\bar a),R(\bar b) \in D$ with $\bar{a} \neq \bar{b}$ such
$$\text{${\sf key}(R) = A \quad$ and $\quad \pi_A(\bar a) = \pi_A(\bar
In this case we say that the pair $(R(\bar a), R(\bar b))$ is key-violating.   Let us define a block in a database $D$ with respect to
a set $\Sigma$ of primary keys to be any maximal set $B$ of facts from $D$ such
that the facts in $B$ are pairwise key-violating.  A repair of $D$ with
respect to $\Sigma$ is a subset $D'$ of $D$ that is obtained by choosing
exactly one tuple from each block of $D$ with respect to $\Sigma$.

Let us consider a schema $\sigma$ with two binary relations $R'$ and $S'$, such
that ${\sf key}(R') = {\sf key}(S') = \{1\}$.  That is, the first attribute of
both $R'$ and $S'$ defines a key over such relations.  We define this set of
keys over $\sigma$ to be $\Sigma$.  Also, let $q = \exists x,y,z (R'(y,x)
\wedge S'(z,x))$.  For simplicity, we write the pair $(q,\Sigma)$
as $R'(\underbar{y},x) \land S'(\underbar{z},x)$.  The problem $\#$Repairs$(R'(\underbar{y},x) \land S'(\underbar{z},x))$, which given a database
$D'$ over schema $\sigma$ aims at computing the number of repairs of $D'$ under
$\Sigma$ that satisfy $q$, is known to be -complete
<cit.>.[To see
that <cit.> establishes the hardness
of $q=R'(\underbar{y},x) \land S'(\underbar{z},x)$, first apply their rewrite
rule R7 (from Fig. 6) to obtain $q'=R'(\underbar{y},x) \land
S'(\underbar{x},x)$, then apply rewrite rule R10 to
obtain $q''=R'(\underbar{y},x) \land S'(\underbar{x},a)$. Then, $q''$ is
-hard by Lemma 19, and so is $q$ by Lemma 7.]

Now, observe that the -hardness of $\ccountvals(R(x) \land S(x))$ easily
follows from the hardness of the problem $\#$Repairs$(R'(\underbar{y},x)
\land S'(\underbar{z},x))$.  In fact, 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(\bot)$ in $D$, where $\bot$ is a fresh
null, and we set $\dom(\bot) = \{b \mid R'(a,b) \in D'\}$.  For every
constant $a$ that appears in the first attribute of $S'$, we have a
tuple $S(\bot)$ in $D$, where $\bot$ is a fresh null, and we set $\dom(\bot) =
\{b \mid S'(a,b) \in D'\}$. It is then clear that the number of repairs of $D'$
that satisfy $R'(\underbar{y},x) \land S'(\underbar{z},x)$ is equal to the
number of valuations of $D$ that satisfy $R(x) \land S(x)$, thus concluding the
proof.  We point out here that another proof of
Proposition <ref>, that uses different techniques, can be found
in the conference version of the article <cit.> (the proof
that we presented here is shorter).

Already with Propositions <ref> and <ref>,
we have all the relevant hard patterns for the non-uniform setting.  We start
by proving our dichotomy result for naive tables, which is our default case.

Let $q$ be an .  If $R(x,x)$ or $R(x) \land S(x)$ is a
pattern of $q$, then $\countvals(q)$ is -complete. Otherwise,
$\countvals(q)$ is in .

The -hardness part of the claim follows from the last two
propositions and from Lemma <ref>.  We explain why the
problems are in  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 $\nu$ of $D$ is such that $\nu(D)$ satisfies $q$
(except when one relation is empty, in which case the result is simply zero).
We can then 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 $\countvals(q)$ in  can be
established by considering a nondeterministic Turing Machine $M$ that, with
input a non-uniform incomplete database $D$, guesses a valuation $\nu$ of $D$
and verifies whether $\nu(D)$ satisfies $q$. This machine works in polynomial
time as we can verify whether $\nu(D)$ satisfies $q$ in polynomial time
(since $q$ is a fixed FO query). Then given that $\countvals(q)(D)$ is equal to
the number of accepting runs of $M$ with input $D$, we conclude that
$\countvals(q)$ is in . Obviously, the same idea works for codd tables,
that is, $\ccountvals(q)$ is also in . But with this restriction we obtain
more tractable cases, as shown by the following dichotomy result.

Let $q$ be an .  If $R(x) \land S(x)$ is a pattern of $q$, then
$\ccountvals(q)$ is -complete. Otherwise, $\ccountvals(q)$ is in .

We only need to prove the tractability claim, since hardness follows from
Proposition <ref> and Lemma <ref>.  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({\bar x_1}) \land  \ldots \land
R_m({\bar x_m})$.  Observe that since $q$ does not have $R(x) \land  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
$$\ccountvals(q)(D) \, = \, \prod_{i=1}^m
\ccountvals(R_i({\bar x_i}))(D(R_i)).$$
Hence it is enough to show how to
compute $\ccountvals(R_i({\bar x_i}))(D(R_i))$ for every $1\leq i \leq m$.
Let ${\bar t_1},\ldots,{\bar t_n}$ be the tuples of $D(R_i)$.  Let us
write $\rho({\bar t_j})$ for the number of valuations of the nulls appearing
in ${\bar t_j}$ that do not match ${\bar x_i}$.  Clearly,
$\ccountvals(R_i({\bar x_i}))(D(R_i)) = \prod_{\bot \text{ appears in }D(R_i)}
|\dom(\bot)| - \prod_{j=1}^n \rho({\bar t_j})$, so we only have to show how to
compute $\rho({\bar t_j})$ for $1\leq j \leq n$.  Since we can easily compute
the total number of valuations of ${\bar t_j}$, it is enough to show how to
compute the number of valuations of ${\bar t_j}$ that match ${\bar x_i}$.  For
every variable $x$ that appears in ${\bar x_i}$, compute the size of the
intersection of the domains of the corresponding nulls in ${\bar t_j}$, and denote it $s_x$.
Then the number of valuations of ${\bar t_j}$ that match ${\bar x_i}$ is
simply $\prod_{x\text{ appears in }{\bar x_i}} s_x$.  This concludes the proof.

At this stage, we have completed the first column of
Table <ref>, and we also know that $R(x,x)$ is a hard
pattern in the uniform setting for naive tables (but not for Codd tables, by
Theorem <ref>).  In the next section, we treat the
uniform setting.

§.§ The complexity on the uniform case

In this section, we study the complexity of the problems
$\ucountvals(q)$ and $\cucountvals(q)$, again providing dichotomy results in
both cases.

§.§.§ Naïve tables

We start our investigation with the case of naive tables. In
Proposition <ref>, we already showed that $\ucountvals(R(x,x))$ is
-hard. In the following proposition, we identify two other simple queries
for which this problem is still intractable.

$\ucountvals(R(x) \land S(x,y) \land T(y))$ and $\ucountvals(R(x,y)
\land S(x,y))$ are both -hard. This holds even in the restricted setting in
which all nulls are interpreted over the same fixed domain $\{0,1\}$.

We reduce both problems from the problem of counting the number of
independent sets in a graph (denoted by ), which is
-complete <cit.>.  We start
with $\ucountvals(R(x)\land  S(x,y)\land  T(y))$.  Let $q = R(x)\land
S(x,y)\land  T(y)$ and $G=(V,E)$ be a graph.  Then we define an incomplete
database $D$ as follows.  For every node $v \in V$, we have a null $\bot_v$,
and the uniform domain is $\{0,1\}$.  For every edge $\{u,v\} \in E$, we have
facts $S(\bot_u,\bot_v)$ and $S(\bot_v,\bot_u)$ in $D$.  Finally, we have
facts $R(1)$ and $T(1)$ in $D$.  For a valuation $\nu$ of the nulls, consider
the corresponding subset $S_\nu$ of nodes of $G$, given by $S_\nu = \{t \in V
\mid \nu(\bot_t) = 1 \}$.  This is a bijection between the valuations of the
database and the node subsets of $G$.  Moreover, we have that $\nu(D)
\not\models q$ if and only if $S_\nu$ 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|} - \ucountvals(q)(D)$.  Hence, we
conclude that $\sIS \tr \ucountvals(q)$.  The idea is similar
for $\ucountvals(R(x,y)\land  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 naive tables in the uniform setting.

§.§ Proof of Theorem <ref>

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

Let $q$ be an . If $R(x,x)$ or $R(x) \land S(x,y) \land T(y)$
or $R(x,y) \land S(x,y)$ is a pattern of $q$, then $\ucountvals(q)$ is
-complete.  Otherwise, $\ucountvals(q)$ is in .

The -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 <ref>.  We will use the following
definition.  Given $n,m \in \mathbb{N}$, let us write $\surj_{n\rightarrow m}$
for the number of surjective functions from $\{1,\ldots,n\}$
to $\{1,\ldots,m\}$.  By an inclusion–exclusion argument, one can show
that $\surj_{n\rightarrow m} = \sum_{i=0}^{m-1} (-1)^i \binom{m}{i} (m-i)^n$
(for instance, see <cit.>).  It is clear that this can
be computed in FP, when $n$ and $m$ are given in unary.

Let $q$ be the  $R(x)\land  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 <ref>. We will
show that $\ucountvals(q)$ is in .  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 \cap C_S =
\emptyset$, as otherwise all the valuations are satisfying, and this is
computable in PTIME.  Furthermore, we can also assume that $C_R \cup C_S
\subseteq \dom$, since we can remove the constants that are not in $\dom$, as
these can never match.

Let $M := \dom \setminus(C_R \cup C_S)$, and $m$ its size (i.e., with
our assumptions we have $m = d-c_R-c_S$).  Fix some subsets $M' \subseteq M$
and $R' \subseteq C_R$. The quantity $\surj_{n_R \to |M'|+|R'|}$ then counts
the number of valuations of the nulls of $D(R)$ that span exactly $M'\cup R'$.
Moreover, letting $\nu_R$ be a valuation of the nulls of $D(R)$ that spans
exactly $M'\cup R'$, the quantity $(d-c_R-|M'|)^{n_S}$ is the number of ways to
extend $\nu_R$ into a valuation $\nu$ of all the nulls of $D$ so that $\nu(D)
\not\models q$: indeed, every null of $D(S)$ can take any value in $\dom
\setminus(C_R \cup 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$):
\[ \sum_{\substack{M' \subseteq M \\ R' \subseteq C_R}} \surj_{n_R
\to |M'|+|R'|} \times (d-c_R-|M'|)^{n_S}\]
and since the summands only depends
on the sizes of $M'$ and $R'$, this is equal to
\[ \sum_{\substack{0 \leq m'
\leq m \\ 0 \leq r' \leq c_R}} \binom{m}{m'} \binom{c_R}{r'} \surj_{n_R \to
m'+r'} \times (d-c_R-m')^{n_S}\]
This last expression can clearly be computed
in PTIME.[Note that in the sum we do not need to specify that $m'+r'
\leq n_R$, as when $a <b$ we have $\surj_{a \to b} = 0$.]

First, to characterize the queries that do not have these patterns, we will use
the notion of connectivity graph of an  $q$:

Let $q$ be an .  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(\bar{x_i}),S(\bar{y_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 $\bar{x_i} \cap \bar{y_i}$.

Figure <ref> 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 connectivity graph $G_q$ of the  $q$ from Example <ref>.

The following is then readily observed:

Let $q$ be an  that does not contain any of the patterns
mentioned in Theorem <ref>.  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.

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)\land
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(\overline{x}),A_2(\overline{x'}),A_3(\overline{x''})$ such
that $A_1(\overline{x})$ is adjacent to $A_2(\overline{x'})$,
$A_2(\overline{x'})$ is adjacent to $A_3(\overline{x''})$,
and $A_1(\overline{x})$ is not adjacent to $A_3(\overline{x''})$. Let $X$ be
$\overline{x} \cap \overline{x'}$ and $Y$ be $\overline{x'} \cap \overline{x''}$, i.e., the labels
on the two corresponding edges of $C$. By definition of $G_q$ and
since $A_1(\overline{x})$ is not adjacent to $A_3(\overline{x''})$, we must
have $X \cap Y = \emptyset$.  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)\land  S(x,y)\land  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)\land  S(x,y)\land
T(y)$ in $q$.

This concludes the proof.

For instance, the query from Example <ref> 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
(i.e., we remove the first connected component), then it satisfies the

We will also use the general fact that for an  $q$, we can
assume wlog that $q$ does not contain variables that occur only once:

Let $q$ be an , and let $q'$ be the  obtained
from $q$ by deleting all the variables that have only one occurrence in $q$.
Then $\ucountvals(q) \leq_{\mathrm{T}}^{\mathrm{p}} \ucountvals(q')$.

Let $D$ be an incomplete database input of $\ucountvals(q)$.  Let $S$ be set of
nulls $\bot$ such that:

* $\bot$ occurs in a column corresponding to a variable that has been deleted; and

* $\bot$ 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 $\ucountvals(q)(D) = \ucountvals(q')(D') \times \prod_{\bot \in
S}|\dom(\bot)| $, 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 <ref> and
Lemma <ref>, it is enough to show the tractability
of $\ucountvals(q)$ when $q$ is of the form $C_1(x_1) \land  \ldots \land
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 an  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:

Let $q=C_1(x_1) \land  \ldots \land  C_m(x_m)$ be a conjunction of basic
singletons , and let $D$ be an incomplete database.  For $S
\subseteq [m]$, we define $N_S(D) \defeq |\{\nu \text{ valuation of } D \mid
\nu(D) \not\models \bigvee_{i \in S} C_i(x_i)\}|$.  Then we
have $\ucountvals(q)(D) = \sum_{S \subseteq [m]} (-1)^{|S|} N_S(D)$.

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 \subseteq [m]$.  The main difficulties in
computing $N_S(D)$ is that the relations can have nulls in common (since we
consider naive 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 <ref>.

Let $q=C_1(x_1) \land  \ldots \land  C_m(x_m)$ be a conjunction of
basic singletons  and $S \subseteq [m]$.  Then, given an
incomplete database $D$ as input, we can compute $N_S(D)$ in polynomial time.

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\in S$.  Indeed, $N_S(D)$ counts the
valuations $\nu$ of $D$ that do not satisfy any of the $C_i(x_i)$ for $i\in S$,
so that for any $j \notin S$ we do not care if $\nu$ 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  $q$ as
\[R_1(x_1)
\land  \ldots \land  R_{m_1}(x_1) \land  R_{m_1 + 1}(x_2) \land  \ldots \land
R_{m_1 + m_2}(x_2) \land  \ldots \land  R_{\sum_{i=1}^{m-1} m_i}(x_m) \land
\ldots \land  R_{\sum_{i=1}^m m_i}(x_m)\]
and let $K$ be the number of atoms
in $q$, that is, $K \defeq \sum_{i=1}^m m_i$.  Let $\dom$ be the uniform domain
of the nulls occurring in $D$ and $d$ its size.  For $\mathbf{s} \subseteq
[K]$, we write $C_\mathbf{s}$ the set of constants that occur in each of the
relations $D(R_i)$ for $i\in \mathbf{s}$ but in none of the others, and
write $c_\mathbf{s}$ the size of that set. We call such a set a block of
constants.  Similarly for the nulls, we write $N_\mathbf{s}$ the set of nulls
that occur in each of the relations $D(R_i)$ for $i\in \mathbf{s}$ but in none
of the others (and we call this a block of nulls), and $n_\mathbf{s}$ for its
size. We can assume wlog that:

(a) For every $1 \leq i \leq 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 \subseteq \dom$, let us write $A^\complement \defeq \dom
\setminus A$.  Finally, for a set $Z=\{A_1,\ldots,A_l\}$ of subsets of $\dom$,
we denote by $\I(Z)$ the set

\[\I(Z) \defeq \{ \bigcap_{i=1}^l B_i \mid (B_1,\ldots,B_l) \in \{A_1,A_1^\complement\} \times \ldots \times \{A_l,A_l^\complement\} \} \]

We now explain informally how we can compute $N_{[m]}(D)$.
Let $L=\mathbf{s}_1,\ldots,\mathbf{s}_{2^K}$ be an arbitrary linear order of
the set of subsets of $[K]$.  We will define by induction on $i\in [2^K]$ an
expression computing $N_{[m]}(D)$, which will be a nested sum of the form

\begin{equation}
\label{eq:huge-sum}
\sum_{\text{sum}_{\mathbf{s}_1}} f_{\mathbf{s}_1} \times \bigg( \sum_{\text{sum}_{\mathbf{s}_2}} f_{\mathbf{s}_2} \times
\big( \ldots (\sum_{\text{sum}_{\mathbf{s}_{2^K}}} f_{\mathbf{s}_{2^K}}) \ldots \big) \bigg)
\end{equation}

where each $\text{sum}_{\mathbf{s}_i}$ sums over the possible
images $A_{\mathbf{s}_i}$ of the nulls in $N_{\mathbf{s}_i}$ by a valuation,
and $f_{\mathbf{s}_i}$ will simply be $\surj_{n_{\mathbf{s}_i} \to
a_{\mathbf{s}_i}}$, where $a_{\mathbf{s}_i} \defeq |A_{\mathbf{s}_i}|$, i.e.,
the number of valuations $\nu$ of $N_{\mathbf{s}_i}$ with image
exactly $A_{\mathbf{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, $\text{sum}_{\mathbf{s}_i}$ will actually sum over all
the possible partitions $(B_{\mathbf{s_i}}^1,\ldots,B_{\mathbf{s_i}}^{|\I(Z_{i-1}|)})$ of $A_{\mathbf{s}_i}$,
where each of the $B_{\mathbf{s}_i}^j$
is included in one of the sets in $\I(Z_{i-1})$, where $Z_{i-1}$ contains all the blocks of constants and all the other $B_{\mathbf{s_j}}^r$ for $j < i$.
We iteratively build that sum from the outside to the inside, starting with $Z_0 \defeq \{\dom\} \cup \{C_{\mathbf{s}} \mid \mathbf{s} \subseteq [K]\}$.
This will allow us to avoid summing over the $B_{\mathbf{s_i}}^j$ 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 $\mathbf{s}_i$ actually only depends on the sizes of the sets in $Z_{i-1}$.
Hence, iterating from the outside to the inside, whenever $\text{sum}_{\mathbf{s}_i}$ contains a
sum of the form, say, $B_{\mathbf{s_i}}^k \subseteq B_{\mathbf{s_j}}^{k'}$ for $j<i$,
we can replace this with a sum over $0 \leq b_{\mathbf{s_i}}^k \leq b_{\mathbf{s_j}}^{k'}$, and add to $f_{\mathbf{s}_i}$ a factor
of $\binom{b_{\mathbf{s_j}}^{k'}}{b_{\mathbf{s_i}}^k}$.
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 \setminus \bigcup_{i=1}^K C_{\{i\}}|$ or	one of the numbers $c_{\mathbf{s}}$
for $\mathbf{s} \subseteq [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 <ref>.

§.§.§ Codd tables

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.

$\cucountvals(R(x) \land S(x,y) \land T(y))$ is -hard.

We reduce from the problem of counting the number of independent sets of a
bipartite (simple) graph, written #BIS, which is
-hard <cit.>.  Let $G = (X \sqcup 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
\subseteq X, S_2 \subseteq Y$, such that $(S_1 \times S_2) \cap E = \emptyset$.
We will call such a pair an independent pair.  For $0 \leq i,j \leq 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 ($\star$) the number of independent sets
of $G$ is then $\#\mathrm{BIS}(G) = \sum_{0 \leq i,j \leq 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 \leq a,b \leq n$ such that, letting $C_{a,b}$ be the
number of valuations $\nu$ of $D_{a,b}$ with $\nu(D_{a,b}) \not \models
R(x)\land  S(x,y)\land  T(y)$, the values of the variables $Z_{i,j}$
and $C_{i,j}$ form a linear system of equations $\mA \mZ = \mC$, with $\mA$ an
invertible matrix.  This will allow us, using $(n+1)^2$ calls to an oracle for
$\cucountvals(R(x)\land  S(x,y)\land  T(y))$, to recover the $Z_{i,j}$ values,
and then to compute $\#\mathrm{BIS}(G)$ using ($\star$).  We now explain how we
construct $D_{a,b}$ from $G$ for $0 \leq a,b \leq n$, and define $\mA$.  First,
we fix an arbitrary linear order $x_1,\ldots,x_n$ of $X$, and similarly
$y_1,\ldots,y_n$ for $Y$.  The database $D_{a,b}$ has constants $a_i$ for $1
\leq i \leq n$, and has a fact $S(a_i,a_j)$ whenever $(x_i,y_j) \in E$. It has
nulls $\bot_1,\ldots,\bot_a$ and facts $R(\bot_i)$ for $1 \leq i \leq a$
(if $a=0$ there are no such nulls and facts), and
nulls $\bot_1',\ldots,\bot'_b$ and facts $T(\bot'_i)$ for $1 \leq i \leq b$; in
particular, this is a Codd table.  The uniform domain of the nulls is $\{a_i
\mid 1 \leq i \leq n\}$.  Given a valuation $\nu$ of $D_{a,b}$, let $P(\nu)$ be
the pair of subsets of $V$ defined by
\[P(\nu) \defeq (\{x_i \mid \exists 1
\leq k \leq a \text{ s.t. } \nu(\bot_k)=a_i\}, \\ \{y_i \mid \exists 1 \leq k
\leq b \text{ s.t. } \nu(\bot'_k)=a_i \})\]
One can then easily check that the
following two claims hold:

* For every valuation $\nu$ of $D_{a,b}$, we have that $\nu(D_{a,b}) \not\models R(x)\land  S(x,y)\land  T(y)$ iff $P(\nu)$ is an independent
pair of $G$;[This observation, and in fact the idea of reducing from #BIS, is due to Antoine Amarilli.]

* For every independent pair $(S_1,S_2)$ of $G$, there are
exactly $\surj_{a \to |S_1|} \times \surj_{b \to |S_2|}$ valuations $\nu$ such that $P(\nu) = (S_1,S_2)$.

But then, we have $C_{a,b} = \sum_{0 \leq i,j \leq n} (\surj_{a \to i} \times
\surj_{b \to j}) Z_{i,j}$.  In other words, we have the linear system of
equations $\mA \mZ = \mC$, where $\mA$ is the $(n+1)^2 \times (n+1)^2$ matrix
defined by $\mA_{(a,b),(i,j)} \defeq \surj_{a \to i} \times \surj_{b \to j}$.
This matrix is the Kronecker product $\mA' \otimes \mA' $ of the $(n+1) \times
(n+1)$ matrix with entries $\mA'_{a,i} \defeq \surj_{a \to i}$.  Since $\mA'$
is a triangular matrix with non-zero coefficients on the diagonal, it is
invertible, hence so is $\mA$, which concludes the proof.

Note that in Proposition <ref>, we proved that
$\ucountvals(R(x) \land S(x,y) \land T(y))$ is -hard in the general case
where naive tables are allowed. Hence, the hardness of that query for naive
tables was in fact a consequence of Proposition <ref>.
However, we decided to provide a separate proof for
Proposition <ref>, because in this case intractability
holds already when nulls are interpreted over the fixed domain $\{0,1\}$,
whereas we do not know if this is true for Codd tables.

The second pattern that we show is hard for $\ucountvals$ for Codd tables is
$R(x,y) \land S(x,y)$. Again, notice that we already showed this query to be
hard in the case of naive tables (as Proposition <ref>),
even for a fixed domain of $\{0,1\}$. In the case of Codd tables, hardness
still holds, but the proof is more complicated and uses domains of unbounded
size (which is why we provide separate proofs). We show:

$\cucountvals(R(x,y) \land S(x,y))$ is -hard.

Let $q$ be the query $R(x,y) \land S(x,y)$.  We reduce from the
problem of counting the number of matchings of a $2$-$3$–regular bipartite
graph, which is -complete <cit.>.
Let $G=(A\sqcup B,E)$ be a $2$-$3$–regular bipartite graph, with the nodes
in $A$ having degree $3$ and those in $B$ having degree $2$, and let $n_A
\defeq |A|$, and $n_B \defeq |B|$. Notice that since $G$ is $2$-$3$–regular we
have that $n_B = \frac{3n_A}{2}$.  We say that a set $S \subseteq E$ of edges
of $G$ is an $A$-semimatching if every node $a$ of $A$ is adjacent to at
most $1$ edge of $S$; formally, for every $a\in A$ we have $|\{e \in S \mid a
\in e\}| \leq 1$. The type of an $A$-semimatching $S$ is the number $c$
of nodes in $B$ that are adjacent to exactly $2$ edges of $S$; formally, $c
\defeq |\{b \in B \mid |\{ e \in S \mid b \in e\}|=2\}|$. For $0 \leq c \leq
n_B$, we write $T_c$ for the number of $A$-semimatchings of $G$ of type $c$.
Observe then that $T_0$ is simply the number of matchings of $G$. The idea of
the reduction is then as follows. We will construct databases $D_k$ for $0 \leq
k \leq n_B$ such that, letting $C_k$ be the number of valuations $\nu$ of $D_k$
such that $\nu(D_k) \not\models q$, the values of the variables $T_k$ and $C_k$
form a system of linear equations $\mA \mT = \mC$, with $\mA$ and invertible
matrix. This will allow us, using $n_B+1$ calls to and oracle
for $\cucountvals(q)$, to recover the values $T_k$, and thus to obtain $T_0$ in
polynomial time, that is, the number of matchings of $G$. We now explain how to
construct the database $D_k$ for $0 \leq k \leq n_B$. In what follows we use
the convention that $\{1,\ldots,k\} = \emptyset$ when $k=0$. The database $D_k$
contains the following facts:

* One fact $R(a,\bot_a)$ for every $a\in A$;

* One fact $S(\bot_b,b)$ for every $b\in B$;

* One fact $S(\bot_{a'},a')$ for every $a\in A$ where $a'$ is a fresh constant. In particular, observe that there are $n_A$ such facts. In what follows we will write $A' \defeq \{a' \mid a\in A\}$.

* One fact $S(a_1,a_2')$ for every $(a_1,a_2) \in A \times A$ with $a_1 \neq a_2$;

* One fact $S(a,i)$ for every $(a,i)\in A \times \{1,\ldots,k\}$;

* One fact $S(u,v)$ for every $(u,v) \in (A \cup B)^2$ such that $\{u,v\}$ is not in $E$.

* One fact $R(u,v)$ for every $(u,v) \in (A' \cup B)^2$.

And finally, the (uniform) domain for all the nulls is $\dom \defeq A \cup B
\cup A' \cup \{1,\ldots,k\}$. Note that this is indeed a Codd database. Now,
let us compute $C_k$, the number of valuations $\nu$ of $D_k$ such
that $\nu(D_k) \not\models q$.  For such a valuation $\nu$ of $D_k$ such
that $\nu(D_k) \not\models q$, observe that ($\star$) for every $a \in A$ it
holds that $\nu(\bot_a)$ is either $a'$ or is one of the nodes in $B$ that is a
neighbor of $a$; this is because otherwise, the facts from ($4$-$6$) would make
the query be satisfied.  Then, for a valuation $\nu$ of $D_k$ such
that $\nu(D_k) \not\models q$, let us define $\sm(\nu) \defeq \{\{a,b\} \mid
(a,b)\in (A \times B) \cap R(\nu(D_k))\}$. Because of ($\star$), observe
that $\sm(\nu)$ is a subset of $E$, and that it is in fact an $A$-semimatching.
We can then partition the valuations $\nu$ of $D_k$ with $\nu(D_k) \not\models
q$ according to the type of $\sm(\nu)$ as follows:

\begin{equation}
\label{eq:semimatchings}
\{\nu \mid \nu \text{ is a valuation of $D_k$ with } \nu(D_k) \not\models q\} = \bigsqcup_{0\leq c \leq n_B} \,\,\,\bigsqcup_{\substack{S: \text{ $S$ is an $A$-semimatching}\\ \text{of~$G$ of type } c}} \,\, \bigsqcup_{\substack{\nu: \text{ $\nu$ valuation of $D_k$}\\ \nu(D_k)\not\models q\\ \sm(\nu)=S}} \{\nu\}.
\end{equation}

Fix an $A$-semimatching $S$ of $G$ of type $c \in \{0,\ldots,n_B\}$, and let us
count how many valuations $\nu$ of $D_k$ there are such that $\nu(D_k)
\not\models q$ and $\sm(\nu)=S$.  First of all, observe that for such a
valuation $\nu$, the value of $\nu(\bot_a)$ for every $a\in A$ is forced: it
is $a'$ if $a$ is adjacent to no edge of $S$, and otherwise it is $b$ for the
unique $\{a,b\} \in S$. Therefore we have to count how many possibilities there
are for the remaining nulls, those of the form $\bot_{a'}$ and $\bot_b$ from
facts ($2$-$3$).  We have:

* For a null $\bot_b$ such that $b$ is adjacent to two edges of $S$, there
are $n_A+k-2$ possible values in order to not satisfy the query. Note that there
are $c$ such nulls $\bot_b$.

* For a
null $\bot_{a'}$ such that $a$ is not adjacent to an edge in $S$ (so that we
know that $\nu(\bot_a)=a'$), there are $n_A+k-1$ possible values in order to not
satisfy the query. For a null $\bot_b$ such that $b$ is adjacent to exactly one
edge $\{a,b\}$ of $S$ (i.e., we have $\nu(\bot_a)=b$) there are again $n_A+k-1$
possible values to not satisfy the query. Observe that in total there are $n_A
-2c$ such nulls $\bot_{a'}$ or $\bot_b$, because $S$ is an $A$-semimatching.

* For a null $\bot_{a'}$ such that $a$ is adjacent to an edge in
$S$ (so that we know that $\nu(\bot_a)\neq a'$) there are $n_A+k$
possibilities, and similarly for a null $\bot_b$ such that $b$ is not adjacent
to an edge in $S$ there are $n_A+k$ possible values. By the previous two items,
in total there are $n_A+n_B - c - (n_A-2c) = n_B+c$ such nulls $\bot_{a'}$
or $\bot_b$.

Therefore, there are exactly $(n_A+k-2)^c (n_A+k-1)^{n_A-2c} (n_A+k)^{n_B+c}$
valuations $\nu$ of $D_k$ such that $\nu(D_k) \not\models q$ and $\sm(\nu)=S$.
Since this depends only on the type of the $A$-semimatching $S$ (and not on $S$
itself), we obtain from Equation <ref> that

\begin{align*}C_k &= |\{\nu \mid \nu \text{ is a valuation of $D_k$ with } \nu(D_k) \not\models q\}|\\
&= \sum_{0 \leq c \leq n_B} T_c \times (n_A+k-2)^c (n_A+k-1)^{n_A-2c} (n_A+k)^{n_B+c}.
\end{align*}

That is, we have the linear system of equations $\mA \mT = \mC$,
with $\mA_{k,c} = (n_A+k-2)^c (n_A+k-1)^{n_A-2c} (n_A+k)^{n_B+c}$ for $0\leq
c,k \leq n_B$.  But observe that we have $\mA = \mD \mV$, with $\mD$ being the
diagonal $(n_B+1)\times (n_B+1)$ matrix with
entries $(n_A+k-2)^{n_A}(n_A+k)^{n_B}$, and $\mV$ being the $(n_B+1)\times
(n_B+1)$ Vandermonde matrix with coefficients $\frac{(n_A+k-2)
(n_A+k)}{(n_A+k-1)^2}$ for $0\leq k \leq n_B$.  Hence to show that $\mA$ is
invertible, we only need to argue that the coefficients of this Vandermonde
matrix $\mV$ are all distinct. But for the function $f_{n_A}(x) \defeq
\frac{(n_A+x-2) (n_A+x)}{(n_A+x-1)^2}$, one can check that $f'_{n_A}(x) =
\frac{2}{(n_A+x-1)^3}$, so that $f_{n_A}$ is strictly increasing on $[0,n_B]$
(we assume $n_A \geq 2$ without loss of generality), so that all the
coefficients are indeed distinct.  This concludes the proof.

As we show next, the patterns from Propositions <ref>
and <ref> are the only hard patterns for $\cucountvals$.
The following is then the last dichotomy of this section.

Let $q$ be an . If $R(x) \land S(x,y) \land T(y)$ or $R(x,y)
\land S(x,y)$ is a pattern of $q$, then $\cucountvals(q)$ is -complete.
Otherwise, $\cucountvals(q)$ is in .

We only need to show the tractability part of that claim, as hardness follows
from Propositions <ref> and <ref>
and Lemma <ref>.  First of all, observe that we can
assume without loss of generality that the  $q$ is connected. This is
because $q$ has no self-join and the database $D$ is Codd, so,
letting $q_1,\ldots,q_t$ be the connected components of $q$, and letting $D_i$
be the database $D$ restricted to the relations appearing in $q_i$, we have

\[\cucountvals(q)(D) = \prod_{i=1}^t \cucountvals(q_i)(D_i).\]

Second, notice that, for a connected  $q$, not containing any of these
two patterns is equivalent to the following: there exists a variable $x$
such that all atoms of $q$ contain variable $x$, and for any two atoms
of $q$, the only variable that they have in common is $x$. In other words, $x$
is in every atom and every other variable occurs in only one atom. For
instance $R_1(x,y,y)\land R_2(x,x,z,z,z,u,u) \land R_3(x,x,v,t,t)$ is such a
We now provide an example of a connected query with only two atoms.

We consider the query $q=R(x,x,y,y)\land S(x,x)$. Let $D$ be an incomplete Codd
database over relations $R,S$, with uniform domain $\dom$ of size $d$. In this
proof we will use symbols $a,a_1,a_2,\ldots$ to denote a constant or a null,
and symbols $c,c_1,c_2,\ldots$ to denote constants. Moreover, unless stated
otherwise, these symbols can refer to the same constant (but not to the same
null because $D$ is a Codd database). A fact that contains only constants is
called a ground fact. Furthermore, since that database is Codd we will
always represent a null with $\bot$, being understood that they are all distinct.

We start with a few simplifications.  First, we assume wlog that $D$ does not
contain ground facts that already satisfy the query. Second, we assume wlog
that $D$ does not contain facts of the form $R(a,a',c,c')$ or $R(c,c',a,a')$
or $S(c,c')$ where $c$ and $c'$ are distinct constants. Indeed, because $D$ is
Codd and such a fact $f$ can never be part of a match, we could simply
remove $f$ from $D$ and multiply the end result by the appropriate value
(namely, $d^t$ where $t$ is the number of nulls of $f$). Last, we assume wlog
that for any fact of the form $R(a,a',c,\bot)$ or $R(a,a',\bot,c)$
or $R(\bot,c,a,a')$ or $R(c,\bot,a,a')$ or $S(c,\bot)$ or $S(\bot,c)$, we
have $c\in \dom$; indeed otherwise, those facts can never be part of a match
and we could again remove them and multiply the result by the appropriate

Next, we need to introduce some notation.  For a fact $f$ of $D$, the
type of $f$ is the word in $\{0,1\}^{\arity(f)}$ that has a $1$ in
position $i$ iff the $i$-th element of $f$ is a null. For instance the type
of $R(\bot,\bot,c,\bot)$ is $1101$ and that of $S(c,c)$ is $00$.  Observe that
there are a fixed number of possible types, because the query is fixed.   For a
constant $c$ and fact $f$ of $D$, we say that $f$ is $c$-determined
if $f$ contains the constant $c$ at a position for variable $x$. For
instance $R(\bot,c,c',\bot)$ is $c$-determined and so is $S(c,c)$.  A fact $f$
that contains only nulls on the positions for $x$ is called free. With
the simplifications of the last paragraph, a fact of $D$ is either free or it
is $c$-determined for a unique constant $c$.  Let $\mathbf{t}$ be a type of $D$
(for $R$ or for $S$).  We say that $\mathbf{t}$ is free if it has
only $1$s in the positions corresponding to variable $x$; in other words, if it
is the type of a free fact. Otherwise we say that $\mathbf{t}$ is determined.
For a constant $c$ and determined type $\mathbf{t}$, we
write $n_{R,c,\mathbf{t}}$ (resp., $n_{R,c,\mathbf{t}}$) the number
of $R$-facts (resp., of $S$-facts) of $D$ that are $c$-determined of
type $\mathbf{t}$.  For a free type $\mathbf{t}$ of $R$ (resp., of $S$) we
write $F_{R,\mathbf{t}}$ (resp., $F_{S,\mathbf{t}}$) for the set of
free $R$-facts (resp., of free $S$-facts) and $\ff_{R,\mathbf{t}}$
(resp.,$\ff_{\mathbf{t}}$) for its size.  Let $f$ be a fact that
is $c$-determined.  We write $\alpha_{f}$ for the number of valuations $\nu$ of
the nulls in $f$ such that $f$ matches the corresponding atom in $q$.  For
instance if $f$ is $R(\bot,c,c',\bot)$ or again $R(c,c,c',c')$
then $\alpha_{f}=1$, while if $f$ is $R(c,c,\bot,\bot)$
then $\alpha_{f}=d$.[When $f$ is a ground fact – such
as $R(c,c,c',c')$ – we recall the mathematical convention that there exists a
unique function with emtpy domain, hence a unique valuation of the nulls
of $f$.]  Similarly we let $\beta_{f}$ denote the number of valuations $\nu$ of
the nulls in $f$ such that $f$ does not match the corresponding atom in $q$;
which is then equal to $d^t - \alpha_{f}$, for $t$ the number of nulls in $f$.
Observe that $\alpha_{f}$ and $\beta_f$ depend only on the type $\mathbf{t}$
of $f$.  Hence we will write $\alpha_\mathbf{t}$ and $\beta_\mathbf{t}$
instead.  Let $f$ be a free fact. We let $\alpha_f$ be the number of valuations
of the nulls in $f$ that are not on a position for variable $x$ that match the
corresponding part of the atom in $q$. For instance if $f$
is $R(\bot,\bot,c',\bot)$ then $\alpha_f=1$ and if $f$
is $R(\bot,\bot,\bot,\bot)$ then $\alpha_f=d$.  We also define $\beta_f \defeq
d^t - d \alpha_f$ where $t$ is the number of nulls, which correspond to the
number of valuations of the nulls in $f$ such that the ground fact obtained
does not match its corresponding atom.  Again, since $\alpha_{f}$ and $\beta_f$
depend only on the free type $\mathbf{t}$ of $f$, we will
write $\alpha_\mathbf{t}$ and $\beta_\mathbf{t}$ instead.  It is clear that we
can compute all values $\alpha_{f,c}$ and $\beta_{f,c}$, for every determined
fact $f$ and constant $c$ of $D$, and values $\alpha_{f}$ for every free fact
in polynomial time.    Last, we fix a linear order $c_1,\ldots,c_n$ on the
constants $c_i$ such that there exists a fact of $D$ that is $c_i$-determined.

Next, we explain how we can compute in  the number of valuations of $D$
that do not satisfy $q$.  To do so, we will first define some
quantities, and then show that we can compute these quantities in polynomial
time using a dynamic programming approach. One of these quantities will be the
number of valuations of $D$ that do not satisfy $q$, which is what we want to
compute. The quantities that we will define are of the form $V(\params)$,
where $\params$ consist of the following parameters ($\dagger$):

* one parameter $v$ whose range is $0\ldots n$;

* one parameter $q_{R,\mathbf{t}}$ for every free type $\mathbf{t} \in \{0,1\}^4$ of $R$, with range $0\ldots \ff_{R,\mathbf{t}}$;

* one parameter $r_R$ with range $0,\ldots,n$;

* one parameter $r_S$ with range $0,\ldots,r_R$;

We now explain what the quantity $V(\params)$ with these parameters represent. To that end, we define the incomplete database $D(\params)$ to be the database that contains only

* all of the facts that are $c_i$-determined for $1 \leq i \leq v$
(if $v=0$ then $D_v$ contains no determined facts);
* for every free
type $\mathbf{t}$ of $R$, $D(\params)$ contains $q_{R,\mathbf{t}}$ free
$R$-facts of $D$ of type $\mathbf{t}$ (it doesn't matter which ones, say the
first $q_{R,\mathbf{t}}$ ones);

* $D(\params)$ contains all the free $S$-facts of $D$.

(Note that parameters (c) and (d) are not used to define the database but we still write $D(\params)$.)

The quantity $V(\params)$ is then defined to be the number of valuations $\nu$
of database $D(\params)$ such that $\nu(D(\params))\not\models q$ and such that
the following holds: (1) for every $ 1 \leq i \leq r_S$ and free fact $f$
of $R$ or of $S$, the ground fact $\nu(f)$ does not match the corresponding
atom in $q$ with variable $x$ mapped to $c_i$ (this condition is empty if $r_S
= 0$); and (2) for every $r_S + 1 \leq i \leq r_R$ and every free fact $f$
of $R$, the ground fact $\nu(f)$ does not match $R(x,x,y,y)$ with variable $x$
mapped to $c_i$ (this condition is empty if $r_R = r_S$).  By definition we then have that,
when $v=n$, $q_{R,\mathbf{t}}=\ff_{R,\mathbf{t}}$ for every free
type $\mathbf{t}$ of $R$ – so that $D(\params)$ is equal to $D$ –, $r_R=0$
and $r_S=0$ then $V(\params)$ is then equal to $\cucountvals(q)(D)$.  Observe
that there are a fixed number of parameters in $\params$ (because the query is
fixed), and that the possible values of these parameters are polynomial in the
size of the input. We explain how compute the values $V(\params)$ by dynamic

*Base case.
Our base case will be when $v$ is equal to zero (and the other parameters are
arbitrary as in ($\dagger$)); in other words, the database $D(\params)$
does not contain any determined facts, it contains only free facts. We have to
compute the number of valuations of $D(\params)$ that do not satisfy the query
and such that (1) and (2) hold.
We do so as follows.  We guess a subset $S_R$ of $\dom \setminus
\{c_1,\ldots,c_{r_R}\}$; this will be the set of constants $c$ such
that $R(c,c,c',c') \in \nu(D(\params))$ for some $c'$.  We also guess a subset $S_S$
of $\dom \setminus \big( \{c_1,\ldots,c_{r_S}\} \cup S_R\big)$; this will
be the set of constants $c$ such that $S(c,c) \in \nu(D(\params))$ (observe
that $S_R$ and $S_S$ are disjoint; this is in order to avoid satisfying the
query). To “achieve” these subsets, we for each free type $\mathbf{t}$ of $R$
guess a subset $W_{R,\mathbf{t}}$ of the free facts of $R$ of
type $\mathbf{t}$; these will be the $R$-facts $f$ of type $\mathbf{t}$ such
that $\nu(f)$ matches $R(x,x,y,y)$ with a constant in $S_R$ for variable $x$.
Similarly we for each free type $\mathbf{t}$ of $S$ guess a
subset $W_{S,\mathbf{t}}$ of the free facts of $S$ of type $\mathbf{t}$; these
will be the $S$-facts $f$ of type $\mathbf{t}$ such that $\nu(f)$
matches $S(x,x)$ with a constant in $S_S$ for variable $x$. To ensure that
these subsets are indeed enough to cover $S_R$ and $S_S$, we surjectively
assign each of the corresponding facts a constant in $S_R$ (for $R$-facts)
or $S_S$ (for $S$-facts). For such facts $f$, we then choose one of
the $\alpha_\mathbf{t}$ valuations of $f$ that ensure that the ground fact
obtained satisfies the correspoinding atom of the query; crucially, this
quantity depends only on the type of $f$. For the remaining (free) facts $f$, we
choose one of the $\beta_\mathbf{t}$ valuations of $f$ that ensure that the
ground facts obtained do not satisfy the corresponding atom of the query. In
the end we obtain that $V(\params)$ is equal to the following

\begin{equation}
\label{eq:base-intermediate}
\sum_{S_R \subseteq \dom \setminus \{c_1,\ldots,c_{r_R}\}} \sum_{S_S \subseteq\dom \setminus \big( \{c_1,\ldots,c_{r_S}\} \cup S_R\big)}
\sum_{W_{R,\mathbf{t_1}} \subseteq Q_{R,\mathbf{t_1}}} \cdots
\sum_{W_{R,\mathbf{t_J}} \subseteq Q_{R,\mathbf{t_J}}}
\sum_{W_{R,\mathbf{t'_1}} \subseteq F_{S,\mathbf{t'_1}}} \cdots
\sum_{W_{R,\mathbf{t'_K}} \subseteq F_{S,\mathbf{t'_K}}}
\gamma
\end{equation}

where $\mathbf{t_1}\ldots \mathbf{t_J}$ are all the free types of $R$,
$\mathbf{t'_1}\ldots \mathbf{t'_K}$ are all the free types of $S$,
$Q_{R,\mathbf{t_i}}$ is the set of the first $q_{R,\mathbf{t_i}}$ free
$R$-facts of type $\mathbf{t_i}$, and where,
letting $z \defeq \sum_{i=1}^J |W_{R,\mathbf{t_i}}|$ and $z' \defeq
\sum_{i=1}^K |W_{S,\mathbf{t'_i}}|$, we have

\begin{equation*}
\gamma = \surj_{z \to |S_R|} \times \surj_{z' \to |S_S|} \times \big(\prod_{i=1}^J \alpha_{\mathbf{t_i}}^{|W_{R,\mathbf{t_i}}|} \beta_{\mathbf{t_i}}^{|Q_{R,\mathbf{t_i}}| - |W_{R,\mathbf{t_i}}|}  \big)
\times \big(\prod_{i=1}^K \alpha_{\mathbf{t'_i}}^{|W_{S,\mathbf{t'_i}}|} \beta_{\mathbf{t'_i}}^{|F_{S,\mathbf{t'_i}}| - |W_{S,\mathbf{t'_i}}|}  \big).
\end{equation*}

Obviously, we cannot compute the expression in <ref> in polynomial time, since we are summing over subsets of the input facts.
However, because $\gamma$ depends only on the sizes of all these sets, we can express $V(\params)$ as

\begin{equation}
\label{eq:base-final}
\sum_{0 \leq s_R \leq d-r_R} \sum_{0 \leq s_S \leq d-r_S -s_R }
\sum_{0 \leq w_{R,\mathbf{t_1}} \leq q_{R,\mathbf{t_1}}} \cdots
\sum_{0 \leq w_{R,\mathbf{t_J}} \leq q_{R,\mathbf{t_J}}}
\sum_{0 \leq w_{R,\mathbf{t'_1}} \leq \ff_{R,\mathbf{t'_1}}} \cdots
\sum_{0\leq w_{R,\mathbf{t'_K}} \leq \ff_{R,\mathbf{t'_K}}}
\delta,
\end{equation}

where, letting again $z \defeq \sum_{i=1}^J w_{R,\mathbf{t_i}}$ and $z' \defeq \sum_{i=1}^K w_{S,\mathbf{t'_i}}$, we have

\begin{align*}
\delta = & \surj_{z \to s_R} \times \surj_{z' \to s_S} \times \big(\prod_{i=1}^J \alpha_{\mathbf{t_i}}^{w_{R,\mathbf{t_i}}} \beta_{\mathbf{t_i}}^{q_{R,\mathbf{t_i}} - w_{R,\mathbf{t_i}}}  \big)
\times \big(\prod_{i=1}^K \alpha_{\mathbf{t'_i}}^{w_{S,\mathbf{t'_i}}} \beta_{\mathbf{t'_i}}^{\ff_{S,\mathbf{t'_i}} - w_{S,\mathbf{t'_i}}}  \big)\\
&  \times \binom{d-d_R}{s_R}\binom{d-r_S-s_R}{s_S} \times \big(\prod_{i=1}^J \binom{q_{R,\mathbf{t_i}}}{w_{R,\mathbf{t_i}}}\big)
\times \big(\prod_{i=1}^K \binom{\ff_{S,\mathbf{t'_i}}}{w_{S,\mathbf{t'_i}}}\big).
\end{align*}

But then, because the expression <ref> contains a fixed number of
nested sums (this number depends only on the query $q$), and because indices
and summands are polynomial, this quantity can be computed in polynomial time.
This concludes the base case, that was when $v=0$.

*Inductive case.

Next we explain how we can compute the quantities $V(\params)$ (with the
parameters $\params$ as in ($\dagger$)) in polynomial time from
quantities $V(\params')$ with a strictly smaller value for parameter (a). Hence
we assume that parameter $v$ is $\geq 1$. The idea is to get rid of
the $c_v$-determined facts of $D(\params)$, by partitioning the valuations
of $D(\params)$ that do not satisfy $q$ and satisfy (1) and (2) into

(A) those valuations $\nu$ that do not satisfy the query and satisfy (1) and (2) and such that
no $c_v$-determined $R$-fact or free $R$-fact $f$ of $D(\params)$ is such
that $\nu(f)$ matches $R(x,x,y,y)$ with variable $x$ mapped to $c_v$; and

(B) those valuations $\nu$ that do not satisfy the query and satisfy (1) and (2) and such that at
least one $c_v$-determined $R$-fact or free $R$-fact $f$ of $D(\params)$ is
such that $\nu(f)$ matches $R(x,x,y,y)$ with variable $x$ mapped to $c_v$ (and thus,
no $c_v$-determined $S$-fact or free $S$-fact $f$ of $D(\params)$ is such
that $\nu(f)$ matches $S(x,x)$ with variable $x$ mapped to $c_v$).

To compute valuations in $\mathbf{(A)}$, we choose for each $R$-fact $f$ that
is $c_v$-determined one of the $\beta_{f,c_v}$ valuations of its nulls that is
such that $\nu(f)$ does not match $R(x,x,y,y)$, we disallow the free facts
of $R$ to have valuations that would match on $c_v$ by increasing $r^R$ by one,
and we choose any valuation for the $c_v$-determined facts of $S$ (since we
know that they will not be part of a match). Formally, letting $t_f$ be the
number of nulls of a fact $f$, we have the expression

\[A = \big(\prod_{\substack{c_v\text{-determined}\\R\text{-fact }f}} \beta_{f}\big)
\times \big(\prod_{\substack{c_v\text{-determined}\\S\text{-fact }f}} d^{t_f}\big)
\times V(\params')
\]

where $\params'$ is equal to $\params$ except that $v' = v-1$ and $r'_R = r'_R
+1$. This can be computed in polynomial time if we know the
value $V(\params')$.  For valuations in $\mathbf{(B)}$, we do as follows. We
choose exactly which subset of the $c_v$-determined and free facts of $R$ will
match $R(x,x,y,y)$ with $x=c_v$ by partioning according to the types, for the
remaining $c_v$-determined $R$-facts we choose one of the $\beta$ valuations
that do not match on $c_v$, for the remaining free facts of $R$ we disallow to
match on $c_v$ by increasing $r^R$ by one, for each $c_v$-determined fact $f$
of $S$ we choose one of the $\beta_{f,c_v}$ valuations of $f$ that are such
that $\nu(f)$ is not $S(c_v,c_v)$, and for the free facts of $S$ we disallow
matching on $c_v$ by increasing $r_S$ by one. Formally,
letting $\mathbf{t_1},\ldots,\mathbf{t_J}$ be the types of the $c_v$-determined
$R$-facts and $\mathbf{t'_1},\ldots,\mathbf{t'_J}$ be the free types of $R$ we
obtain an expression of the form

\begin{equation}
B = \sum_{0 \leq h_\mathbf{t_1} \leq n_{R,c_v,\mathbf{t_1}}} \cdots \sum_{0 \leq h_\mathbf{t_J} \leq n_{R,c_v,\mathbf{t_J}}}
\sum_{0 \leq h'_\mathbf{t'_1} \leq q_{R,\mathbf{t'_1}}} \cdots \sum_{0 \leq h'_\mathbf{t'_K} \leq q_{R,\mathbf{t'_K}}}
\gamma \times \delta \times V(\params')
\end{equation}

where $\gamma$ is equal to $1$ if $\sum_{i=1}^J h_\mathbf{t_i} + \sum_{i=1}^K h_\mathbf{t'_i} \geq 1$ and to $0$ otherwise (in order to match on $c_v$ in $R$), $\delta$ is

\[ \big(\prod_{i=1}^J \binom{n_{R,c_v,\mathbf{t_i}}}{h_\mathbf{t_i}} \alpha_{\mathbf{t_i}}^{h_\mathbf{t_i}} \beta_{\mathbf{t_i}}^{n_{R,c_v,\mathbf{t_i}} - h_\mathbf{t_i}} \big)
\times \big(\prod_{i=1}^J \binom{q_{R,\mathbf{t'_i}}}{h'_\mathbf{t'_i}} \alpha_{\mathbf{t'_i}}^{h'_\mathbf{t'_i}}\big)
\times \big(\prod_{\substack{c_v\text{-determined}\\S\text{-fact }f}} \beta_f\big),
\]

and where $\params'$ is equal to $\params$ except that:

* we have $v'=v-1$;

* for every free type $\mathbf{t}$ of $R$, we have $q'_{R,\mathbf{t}} = q'_{R,\mathbf{t}} - h'_\mathbf{t}$;

* we have $r'_R = r_R +1$;

* we have $r'_S = r_S +1$.

The crucial point to see that expressions A and B indeed compute what we
want is that we do not need to remember exactly which susbsets of constants are
disallowed to match for the free facts, but we only need to remember their
numbers (this is what allows us to use a dynamic programming approach); and
similarly for the free facts of $R$, we only need to remember how many we have
left at each stage of each type, but not their precise subsets.  Again, if we know the values
of $V(\params')$ where in $\params'$ parameter $v'$ is equal to $v -1$ then we
can compute in polynomial time the value $V(\params) = A + B$.  Thus, we can
compute all values $V(\params)$ in polynomial time, and this concludes this

The proof in this example can be extended as-is to any connected containing only two atoms and having only one variable ($x$) that joins.  We
claim that the same idea works for an arbitrary number of atoms, which
concludes Theorem <ref>.
Since a full proof is technically tedious and does not provide new insights, we omit it here.

§ DICHOTOMIES FOR COUNTING COMPLETIONS

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

Let $q,q'$ be  such that $q'$ is a pattern of $q$.  Then we
have that $\countcompls(q') \pr \countcompls(q)$. Moreover, the same results
hold if we restrict to the case of Codd tables, and/or to the uniform setting.

The reduction is exactly the same as the one of
Lemma <ref>.  To show that this reduction works
properly for counting completions, it is enough to observe that for every
pair of valuations $\nu_1,\nu_2$ of $D'$ (or of $D$, since $D$ and $D'$ have exactly
the same set of nulls), we have that $\nu_1(D')=\nu_2(D')$ iff $\nu_1(D) =
\nu_2(D)$.

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 <ref> and tractability proofs to obtain
dichotomies.  Our findings are summarized in the last two columns of Table
<ref> in the introduction.  We start in
Section <ref> with the non-uniform cases and
continue in Section <ref> with the uniform cases.
Again, we explicitly state when a -hardness result holds even in the
restricted setting in which there is a fixed domain over which nulls are

§.§ The complexity on the non-uniform case

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

$\ccountcompls(R(x))$ is -hard.

We provide a polynomial-time parsimonious reduction from the problem of
counting the vertex covers of a graph, which we denote by .  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 $\bot_e$ with
$\dom(\bot_e) = \{u,v\}$ and the fact $R(\bot_e)$.  Let $a$ be a fresh
constant.  For every node $u\in V$ we have a null $\bot_u$ with $\dom(\bot_u) =
\{u,a\}$ and the fact $R(\bot_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 $\nu$
of $D$, define the set $S_\nu := \{u \in V \mid R(u) \in D\}$.  Since the
fact $R(a)$ is in every completion of $D$, it is clear that the number of
completions of $D$ is equal to $|\{S_\nu \mid \nu \text{ is a valuation of }
D\}|$.  We claim that $\VC(G)=\{S_\nu \mid \nu \text{ is a valuation of } D\}$,
which shows that the reduction works. ($\subseteq$) Let $C \in \VC(G)$, and let
us show that there exists a valuation $\nu$ of $D$ such that $S_\nu = C$.  For
a null of the form $\bot_e$ with $e=\{u,v\}\in E$, assuming wlog that $u \in
C$, we define $\nu(\bot_e)$ to be $u$.  For a null of the form $\bot_u$
with $u\in V$, we define $\nu(\bot_u)$ to be $u$ if $u\in C$ and $a$ otherwise.
It is then clear that $S_\nu = C$. ($\supseteq$) Let $\nu$ be a valuation
of $D$, and let us show that $S_\nu$ is a vertex cover.  Assume by
contradiction that there is an edge $e=\{u,v\}$ such that $e \cap S_\nu =
\emptyset$.  By definition of $D$, we must have $\nu(\bot_e) \in \{u,v\}$, so
that one of $u$ or $v$ must be in $S_\nu$, hence a contradiction. Therefore, we
conclude that $\sVC \pr \ccountcompls(R(x))$.

Recall from Section <ref> that, to avoid trivialities, we
assume all  to contain at least one atom and that all atoms have at
least one variable.  Using Lemma <ref>, this allows us
to obtain the following dichotomy result.

For every  $q$, it holds that $\countcompls(q)$ and $\ccountcompls(q)$
are -hard.

Notice here that we do not claim membership in ; in fact, we will come back
to this issue in Section <ref> to show that this is unlikely to be
true for naive tables.  However, we can still show that membership in holds for Codd tables.  We then obtain:

For every  $q$, the problem $\ccountcompls(q)$ is -complete.

Hardness is from Theorem <ref>. To show
membership in   we will actually prove a more general result in
Section <ref>. There, we show that for every
Boolean query $q$ such that $q$ has model checking in   the
problem $\ccountcompls(q)$ is in . This in particular applies to all

§.§ The complexity on the uniform case

We now investigate the complexity of $\ucountcompls(q)$ and
$\cucountcompls(q)$.  Recall that in the non-uniform case, even counting the
completions of a single unary table is a -hard problem. This no longer
holds in the uniform case, as we will show that $\ucountcompls(q)$ is in for every  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, both for naive and Codd
tables (and, thus, we also conclude that the problem of counting the
completions of a single binary Codd table is a -hard problem).  We start
with the case of naive tables, for which hardness even holds when nulls are
interpreted over the fixed domain $\{0,1\}$.

The problems $\ucountcompls(R(x,x))$ and $\ucountcompls(R(x,y))$ are both -hard, even
when nulls are interpreted over the same fixed domain $\{0,1\}$.

We reduce from $\sIS$, 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
\in V$, we have a null $\bot_u$ with $\dom(\bot_u) = \{0,1\}$. We then
construct the naive table $D$ as follows:
* for every
node $u \in V$ we add to $D$ the fact $R(u,\bot_u)$;
* then for every
edge $\{u,v\} \in E$, we add the facts $R(\bot_u,\bot_v)$
and $R(\bot_v,\bot_u)$ to $D$; and
* last, we add the facts $R(0,0)$,
$R(0,1)$, $R(1,0)$, and $R(\bot,\bot)$, where $\bot$ is a fresh null.
It is clear that every completion of $D$ satisfies $R(x,x)$
(thanks to the fact $R(\bot,\bot)$).  Let us now count the number of
completions of $D$.  First, we observe that, thanks to the facts of the form
$R(u,\bot_u)$, for $u \in V$, for every two valuations $\nu,\nu'$ that do not
assign the same value to the nulls of the form $\bot_u$, it is the case that
$\nu(D) \neq \nu(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,\bot_u)$, for $u \in V$, and thanks to
the fact $R(\bot,\bot)$ which becomes $R(1,1)$ when we assign $1$ to $\bot$,
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 $\nu$ of $D$
that assign $0$ to $\bot$ and that yield a completion not containing $R(1,1)$.
Indeed, one can check that a valuation of $D$ that assigns $0$ to $\bot$ yields
a completion not containing $R(1,1)$ if and only if the set $\{u \in V \mid
\nu(\bot_u)=1 \}$ is an independent set of $G$. Therefore, we conclude that the
number of completions of $D$ is indeed $2^{|V|} + \#\IS(G)$, and therefore
that $\sIS \tr \ucountcompls(q)$, where $q$ can be $R(x,x)$ or $R(x,y)$.

Next, we prove hardness of the same queries for Codd tables (but in this case
we do not know if harness holds when nulls are interpreted over a fixed domain,
as our proof will use domains of unbounded size).
We will reduce from the problem of counting the number of induced pseudoforests of a graph, as defined next.

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 \subseteq
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 $\shpf$ is the problem that
takes as input a graph $G=(V,E)$ and outputs the number of edge sets $S
\subseteq E$ such that $G[S]$ is a pseudoforest.

Using techniques from matroid theory, the authors
of <cit.> have shown that $\shpf$ is -hard on graphs.
We explain in Appendix <ref> how their proof actually
shows hardness of this problem for bipartite graphs (which we need);
formally, we have:

§.§ Proof for Proposition <ref>

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

[Implied by <cit.>]

The problem $\shpf$ restricted to bipartite graphs is -hard.

This result is proven for (non-necessarily bipartite) graphs
in <cit.> 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 <cit.>.  First, we define what is a

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 \neq \emptyset$;

Heritage. For every $A' \subseteq A \subseteq E$, if $A \in \I$ then $A' \in \I$;

Independent set exchange. For every $A,B \in \I$, if $|A| > |B|$ then there exists $x\in A \setminus B$ such that $B\cup \{x\} \in \I$.

In a matroid $M=(E,\I)$, an independent set $A \in \I$ is called a
basis if every strict superset $A \subsetneq A' \subseteq 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 \subseteq E$, we can define the submatroid of $M$ generated
by $A$ to be $M_A = (A,\I')$, where for $A' \subseteq A$ we
have $A' \in \I'$ iff $A' \in \I$ (one should check that this is indeed
a matroid).  The rank function $\rk_M:\{A \mid A \subseteq E\} \to \N$
of $M$ is then defined with $\rk_M(A)$ being the rank of the
matroid $M_A$. We will now omit the subscript in $\rk_M$ as this will not cause confusion.
We are ready to define the Tutte polynomial of a matroid.

Let $M=(E,\I)$ be a matroid. The Tutte polynomial of $M$, denoted $\T(M;x,y)$, is the two-variables polynomial defined by

\begin{eqnarray*}
\label{eq:tutte}
\T(M;x,y) & = & \sum_{A \subseteq E} (x-1)^{\rk(M)-\rk(A)} (y-1)^{|A|-\rk(A)}
\end{eqnarray*}

We will use the following observation:

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.

We have $\T(M;2,1) =\sum_{A \subseteq 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) \leq |A|$, and that we have $\rk(A) = |A|$ if and only if $A\in \I$, which proves the claim.

Next, we define what is called the bicircular matroid of a graph $G=(V,E)$.
Recall from Definition <ref> the definition of the induced subgraph $G[S]$ for $S \subseteq E$.

Let $G=(V,E)$ be a graph and $\I = \{S\subseteq E \mid G[S] \text{ is a pseudoforest}\}$.
Then one can check that $(E,\I)$ is a matroid <cit.>.
This matroid is called the bicircular matroid of $G$, and is denoted by $B(G)$.

Notice then that the problem $\shpf$ 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 <cit.> to prove that computing $\T(B(G);2,1)$ is -hard for graphs.
The starting point of our explanation is that computing $\T(B(G);1,1)$ is -hard.

The problem of computing, given a graph $G$, the quantity $\T(B(G);1,1)$ is -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).\]

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 -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.

Let $G$ be a graph. For $k\in \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 <cit.>), the authors of <cit.> obtain that, “up to a trivial factor”, we have

\[\T(B(\s_k(G));2,1) \ \simeq \ \T(B(G);2^k,1). \]

A careful inspection of <cit.> reveals[To be precise, we use Equations (7.1) and (7.2) of <cit.> with $x=1,y=0$, and Equation (2.2) with $x=2,y=1$.] that, in fact, we have

\[\T(B(\s_k(G));2,1) \ = \ (2^k -1)^{|E|-\rk_{B(G)}(E)} \times \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.[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 this, the authors of <cit.> can conclude the proof that computing $\T(B(G);2,1)$ is hard for (non-necessarily bipartite) graphs, i.e., that $\shpf$ is -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 <ref> 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$.

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 \to V$ that assigns to every edge in $G$ a node to which it is incident.
We then have:

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$.

Folklore, see, e.g., <cit.>.

Using the hardness of $\shpf$ on bipartite graphs, we are able show hardness of $\cucountcompls(R(x,x))$ and $\cucountcompls(R(x,y))$ as follows.

The problems $\cucountcompls(R(x,x))$ and $\cucountcompls(R(x,y))$ are both -hard.

We reduce both problems from $\shpf$ on bipartite graphs. Let $G=(U \sqcup 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 $\shpf(G)$, thus establishing hardness.
For every $(t,t') \in (U \cup V)^2 \setminus E$, we add to $D$ the fact $R(t,t')$; we call these the complementary facts.
For every $u \in U$ we add to $D$ the fact $R(u,\bot_u)$ and for every $v \in V$ the fact $R(\bot_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 \cup 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 $\nu(D)$ of $D$ is uniquely determined by the set of edges $\{(u,v)\in E \mid R(u,v) \in \nu(D)\}$: this is because $\nu(D)$ already contains all the complementary facts. For a set $S\subseteq 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) \in S$ (note that $D_S$ is not necessarily a completion of $D$). We now argue that for every set $S \subseteq 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 <ref> 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. $(\Rightarrow)$ Assume $D_S$ is a completion of $D$, and let $\nu$ be a valuation witnessing this fact, i.e., such that $\nu(D)=D_S$.
First, observe that we can assume without loss of generality that ($\star$) for every $e =(u,v) \in S$, we have either $\nu(\bot_u)=v$ or $\nu(\bot_v)=u$ but not both. Indeed, if we had both then we could modify $\nu$ into $\nu'$ by redefining, say, $\nu'(\bot_u)$ to be $u$, and we would still have that $\nu'(D)=D_S$ (because $R(u,u)$ is already present in $D$: it is a complementary fact).
We now define an orientation $f_{\nu}:S \to U\cup V$ of $G[S]$ from $\nu$ as follows. Let $e=(u,v) \in S$. Then: if we have $\nu(\bot_u)=v$ we define $f_\nu((u,v))$ to be $v$, i.e., we orient the (undirected) edge $(u,v)$ from $u$ to $v$. Else, if we have $\nu(\bot_v)=u$ we define $f_\nu((u,v))$ to be $u$, i.e., we orient the (undirected) edge $(u,v)$ from $v$ to $u$. Observe that by ($\star$) $f_\nu$ is well defined. It is then easy to check that the maximal outdegree of the directed graph defined by $f_\nu$ is $1$: this is because for every $u \in U$ (resp., $v \in V$), there is only one fact in $D$ of the form $R(u,\text{null})$ (resp., $R(\text{null},v)$), namely, the fact $R(u,\bot_u)$ (resp., $R(\bot_v,v)$).
$(\Leftarrow)$ Let $f:S \to U\cup V$ be an orientation of $G[S]$ with maximum outdegree $1$. Let $\nu_f$ be the valuation of $D$ defined from $f$ as follows:
for every $u\in U$ (resp., $v\in V$), if there is an edge $(u,v)\in S$ such that $f((u,v)) = v$ (resp., such that $f((u,v)) = u$), then define $\nu_f(\bot_u)$ to be $v$ (resp., define $\nu_f(\bot_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 $\nu_f(\bot_u)$ to be $u$ (resp., define $\nu_f(\bot_v)$ to be $v$). Since all edges in $S$ are given an orientation by $f$, it is clear that for every $(u,v)\in S$ we have $R(u,v) \in \nu_f(D)$. Moreover, since $\nu_f(D)$ contains all the complementary facts, we have that $\nu_f(D)=D_S$, which shows that $D_S$ is a completion of $D$ and concludes this proof.

As we show next, these two patterns
suffice to characterize the complexity of $\ucountcompls(q)$ and $\cucountcompls(q)$.

§.§ Proof of Theorem <ref>

In this section we prove the tractability part of the following:

Let $q$ be an .
If $R(x,x)$ or $R(x,y)$ is a pattern of $q$,
then $\ucountcompls(q)$ and $\cucountcompls(q)$ are -hard. Otherwise, these problems are in .

From what precedes, we only have to prove the tractability part of that claim, and this for naive tables.
To this end, we define a conjunction of basic singletons  to be an  of the form $C_1(x_1) \land \ldots \land C_m(x_m)$,
where each $C_i(x_i)$ is a conjunction of unary atoms over the same variable $x_i$ (here the $x_i$ are pairwise distinct).
Since $q$ does not contain the pattern $R(x,x)$ nor the pattern $R(x,y)$, observe that $q$ must in fact be a conjunction of basic singletons .
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 naive and not Codd, and the fact that constants can appear everywhere, complicate a lot the description of the algorithm.
For these reasons, we provide in the next section an example that gives the intuition of the general proof, and defer the general proof to Appendix <ref>.

Note that, as in the last section, we do not claim membership in  in the statement of Theorem <ref>. However,
and also as in the last section,
we can show that these problems are in  for Codd tables, which allows us to obtain our last dichotomy for exact counting.

Let $q$ be an .
If $R(x,x)$ or $R(x,y)$ is a pattern of $q$, then
$\cucountcompls(q)$ is -complete. Otherwise, this problem is in .

Hardness follows from Theorem <ref>, while membership in  follows from the result proven in Section <ref>.

§.§ Example of tractability for Theorem <ref>

In this section, we prove that for the query $q\defeq R(x)\land S(y)$, the problem $\cucountcompls(q)$ is in . Observe that $q$ is a conjunction of basic singletons query, and that it is always satisfied (as long as the database is not empty). We will show that $\ucountcompls(q)$ is in .
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. Let $\dom$ be the uniform domain of the nulls, and let $d$ be its size.
First of all, observe that we can assume without loss of generality that $C \defeq C_{RS} \cup C_R \cup C_S \subseteq \dom$, as otherwise we could simply remove the facts of $D$ that are over constants that are not in $\dom$ and this would not change the result.
Let $c = c_{RS} + c_R + c_S$.
The next two claims explain how we can decompose the computation in a way that we do not count a same completion twice (Claim <ref>), and that we count all the possible completions (Claim <ref>).

For a triplet $(I_R,I_S,I_{RS})$ of subsets of $\dom$ satisfying the conditions ($\star$) $I_R \subseteq \dom \setminus C$, $I_S \subseteq \dom \setminus (C \cup I_R)$, and $I_{RS} \subseteq \dom \setminus (C_{RS} \cup I_R \cup I_S)$,
let us define $P(I_R,I_S,I_{RS})$ to be the complete database consisting of the following facts:

* $R(a)$ and $S(a)$ for $a \in C_{RS} \cup I_{RS}$;

* $R(a)$ for $a \in I_R \cup (C_R \setminus I_{RS})$;

* $S(a)$ for $a \in I_S \cup (C_S \setminus I_{RS})$;

Then, for any two such triplets of sets $(I_R,I_S,I_{RS})$ and $(I'_R,I'_S,I'_{RS})$ that are different, the complete databases $P(I_R,I_S,I_{RS})$ and $P(I'_R,I'_S,I'_{RS})$ are distinct.

To help the reader, we have drawn in Figure <ref> how the sets can intersect.
If we have $I_{RS} \neq I'_{RS}$ with $a \in I_{RS}$ and $a
\notin I'_{RS}$, then $P(I_R,I_S,I_{RS})$ contains both
facts $R(a)$ and $S(a)$,
while $P(I'_R,I'_S,I'_{RS})$ does not. So let us
assume now that $I_{RS} = I'_{RS}$. If we have $I_R \neq I'_R$
with $a \in I_R$ and $a\notin I'_R$ then one can check
that $P(I_R,I_S,I_{RS})$ contains the
fact $R(a)$ while $P(I'_R,I'_S,I'_{RS})$ does
not. Hence let us assume that $I_R = I'_R$. Using the same
reasoning we obtain that $I_S = I'_S$, thus completing the

(0,0) – (5,0) – (5,6) – (0,6) – (0,0);
at (.6,5.5) $\dom$;
at (2.5,5) $C_{RS}$;
at (2.5,3.5) $I_{RS}$;
at (1,2.5) $C_R$;
at (4,2.5) $C_S$;
at (1.8,.8) $I_R$;
at (3.2,.8) $I_S$;

How the sets $\dom, I_R,I_S,I_{RS},C_{RS},C_R$ and $C_S$ from Claim <ref> are allowed to intersect when they satisfy ($\star$). The sets themselves and the intersections can be empty.

Our next step is to show that every completion of $D$ is of the form $P(I_R,I_S,I_{RS})$ for some triplet $(I_R,I_S,I_{RS})$ satisfying ($\star$):

For every completion $D'$ of $D$, there exist a triplet $(I_R,I_S,I_{RS})$ satisfying ($\star$) such that $D' = P(I_R,I_S,I_{RS})$.

We define:

* $I_R \defeq D'(R) \setminus (C_R \cup D'(S))$; where we see $D'(R)$ as the set of constants occurring in relation $R$ of $D'$.

* $I_S \defeq D'(S) \setminus (C_S \cup D'(R))$;

* $I_{RS} \defeq (D'(R) \cap D'(S)) \setminus C_{RS}$.

Then one can easily check that $(I_R,I_S,I_{RS})$ satisfies ($\star$) and that $D' = P(I_R,I_S,I_{RS})$.

By combining these two claims, we have that the result that we wish to compute (which, we recall, is simply the total number of completions of $D$, because any valuation satisfies the query) is equal to

\[\sum_{I_R \subseteq \dom \setminus C} \sum_{I_S \subseteq \dom \setminus (C \cup I_R)} \sum_{I_{RS} \subseteq \dom \setminus (C_{RS} \cup I_R \cup I_S)} \checkp(I_R,I_S,I_{RS}) \]

where $\checkp(I_R,I_S,I_{RS}) \defeq \begin{cases}
1 \text{ if } P(I_R,I_S,I_{RS}) \text{ is a possible completion of } D \\
0 \text{ otherwise}
\end{cases}$.

Next, we show that the value of $\checkp(I_R,I_S,I_{RS})$ can be computed in polynomial time and actually only depends on the sizes of these sets.
In order to show this, we will use the following:

We have $\checkp(I_R,I_S,I_{RS}) = 1$ if and only if the following conditions hold:

* if $n_R \geq 1$ and $|C_R \cup C_{RS} \cup I_{RS}| = 0$, then we have $|I_R| \neq 0$. Intuitively, this means that the value of a null in $N_R$ cannot be “absorbed” by $C_R \cup C_{RS} \cup I_{RS}$.

* if $n_S \geq 1$ and $|C_S \cup C_{RS} \cup I_{RS}| = 0$, then we have $|I_S| \neq 0$. (Same reasonning for nulls in $N_S$.)

* if $n_{RS} \geq 1$ and $|C_{RS}| = 0$, then we have $|I_{RS}| \neq 0$. (Same reasonning for nulls in $N_{RS}$.)

* the following system of equations, whose variables are natural numbers between $0$ and $d$, has a solution:

\begin{align*}
z_{N_R}^{\{N_R\}} + z_{N_R}^{\{N_R,C_S\}} +  z_{N_R}^{\{N_R,N_S\}} &\leq n_R  \\
z_{N_S}^{\{N_S\}} + z_{N_S}^{\{N_S,C_R\}} +  z_{N_S}^{\{N_S,N_R\}} &\leq n_R  \\
z_{C_R}^{\{C_R,N_S\}} &\leq c_R  \\
z_{C_S}^{\{C_S,N_R\}} &\leq c_S  \\
z_{N_R}^{\{N_R\}} &\geq |I_R| \\
z_{N_S}^{\{N_S\}} &\geq |I_S| \\
n_{RS} + \min(z_{N_R}^{\{N_R,C_S\}}, z_{C_S}^{\{C_S,N_R\}}) +
\min(z_{N_R}^{\{N_R,N_S\}}, z_{N_S}^{\{N_S,N_R\}}) +
\min(z_{N_S}^{\{N_S,C_R\}}, z_{C_R}^{\{C_R,N_S\}})
&\geq |I_{RS}|
\end{align*}

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 ($\dagger$) 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}^{\{N_R,C_S\}},  Z_{N_R}^{\{N_R,N_S\}}$ of the nulls in $N_R$ of sizes $0\leq z_{N_R}^{\{N_R\}}, z_{N_R}^{\{N_R,C_S\}},  z_{N_R}^{\{N_R,N_S\}} \leq 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 ($\dagger$):

* 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}^{\{N_R,C_S\}}$ have values in $Z_{C_S}^{\{C_S,N_R\}}$, which gives us constants in $I_{RS}$. Observe that at maximum we could obtain $\min(z_{N_R}^{\{N_R,C_S\}}, z_{C_S}^{\{C_S,N_R\}})$ constants in this manner.

* the nulls in $Z_{N_R}^{\{N_R,N_S\}}$ and those in $Z_{N_R}^{\{N_R,N_S\}}$ have common values, which gives us constants in $I_{RS}$.
Again, observe that we can get at most $\min(z_{N_R}^{\{N_R,N_S\}}, z_{N_S}^{\{N_S,N_R\}})$ constants using these.

* the nulls in $Z_{N_S}^{\{N_S,C_R\}}$ have values in $Z_{C_R}^{\{C_R,N_S\}}$, which gives us constants in $I_{RS}$. Observe that at maximum we could obtain $\min(z_{N_S}^{\{N_S,C_R\}}, z_{C_R}^{\{C_R,N_S\}})$ constants in this manner.

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 $\geq 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 = \emptyset$ for instance. In that case, condition (1) ensures us that we have either $n_R=0$ or $C_R \cup C_{RS} \cup I_{RS} \neq \emptyset$. 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 \geq 1$ and $C_R \cup C_{RS} \cup I_{RS} \neq \emptyset$ 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 = \emptyset$). We leave it to the reader to complete the small gaps in this proof.

Using this, we have that the value of $\checkp(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

The value of $\checkp(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 .

The fact that this value only depends on the sizes of these sets is simply by inspection of the conditions in Claim <ref>. Conditions (1-3) can obviously be checked in PTIME. The fact that condition (4) can be checked in PTIME 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; indeed, observe that the number of variables is fixed because the query is fixed.

But then, we can express the result as follows

\[\sum_{0 \leq i_R,i_S,i_{RS} \leq d} \binom{d-c}{i_R} \binom{d-c-i_R}{i_S} \binom{d-c_{RS} - i_R - i_S}{i_{RS}}  \times \checkp(i_R,i_S,i_{RS}) \]

and we can evaluate this expression as-is in FP because computing $\checkp(I_R,I_S,I_{RS}) \in \{0,1\}$ is in PTIME by the last claim. This concludes this (long) example.

Let $q$ be an sjfBCQ not containing any of these two patterns. Then, as observed in Section <ref>, $q$ is a conjunction of basic singletons query.
Let $\sigma = \{R_1,\ldots,R_l\}$ be the set of relation symbols of $q$, and $D$ be an incomplete database over these relations, with $\dom$ the uniform domain of the nulls and $d$ its size.
For every $\mathbf{s} \subseteq \sigma$, $\mathbf{s} \neq \emptyset$, let:

* $C_\mathbf{s}$ be the set of constants that occur in all relations of $\mathbf{s}$ and in none of the others; $c_\mathbf{s}$ be its size;

*  $N_\mathbf{s}$ be the set of nulls that occur in all relations of $\mathbf{s}$ and in none of the others; $n_\mathbf{s}$ be its size.

We also define $c$ as $\sum_{\emptyset \neq \mathbf{s} \subseteq \sigma} c_\mathbf{s}$.
We can assume wlog that $C_\mathbf{s} \subseteq \dom$ for all $\emptyset \neq \mathbf{s} \subseteq \sigma$, otherwise we can simply remove from $D$ the corresponding facts.
Let $L \defeq 2^l-1$, and let $\mathbf{s}_1,\ldots,\mathbf{s}_L$ be an arbitrary linear order of $\{\mathbf{s} \subseteq \sigma \mid \mathbf{s} \neq \emptyset\}$ (for instance, by non-decreasing size).
We will follow the same steps as in the example of Section <ref>.
The following lemma is the generalization of Claim <ref>, and explains how we can guide the computation so that we do not count the same completion twice:

For a tuple $(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})$ of subsets of $\dom$ satisfying ($\star$)

\[I_{\mathbf{s}} \subseteq (\dom \setminus (C \cup \bigcup_{\substack{\emptyset \neq \mathbf{s'}\subseteq \sigma \\ \mathbf{s'} \neq \mathbf{s}}} I_{\mathbf{s'}})) \cup \bigcup_{\emptyset \neq \mathbf{s'}\subsetneq \mathbf{s}} C_\mathbf{s'}\]

for every $\mathbf{s} \in (\mathbf{s}_1,\ldots,\mathbf{s}_L)$ (in other words, all the sets $I_\mathbf{s}$ are mutually disjoint subsets of $\dom$, and a set $I_\mathbf{s}$ can only contain a constant $b\in C$ if $b$ is in one of the sets $C_\mathbf{s'}$ for which $\mathbf{s'}$ is striclty included in $\mathbf{s}$),
let us define $P(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})$ to be the complete database consisting of the following facts, for every $\emptyset \neq \mathbf{s} \subseteq \sigma$:

* $R(a)$ for every $R \in \mathbf{s}$ and $a \in I_\mathbf{s}$ or $a \in C_\mathbf{s} \setminus \bigcup_{\mathbf{s} \supsetneq \mathbf{s'}} I_\mathbf{s'}$

Then, for every two such tuples $(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})$ and $(I'_{\mathbf{s}_1},\ldots,I'_{\mathbf{s}_L})$ satisfying ($\star$) and that are distinct, we have that $P(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L}) \neq P(I'_{\mathbf{s}_1},\ldots,I'_{\mathbf{s}_L})$.

Let us write $P = P(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})$
and $P' = P(I'_{\mathbf{s}_1},\ldots,I'_{\mathbf{s}_L})$.
Assume that $P=P'$, and let us show
that $(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L}) =
(I'_{\mathbf{s}_1},\ldots,I'_{\mathbf{s}_L})$.  Assume by way
of contradiction that for some $\emptyset \neq \mathbf{s}
\subseteq \sigma$ we have $I_\mathbf{s} \neq I'_\mathbf{s}$. Then
(wlog) there exists $a \in I_\mathbf{s} \setminus
I'_\mathbf{s}$. By the definition of $P$, we have that $P$
contains all the facts $R(a)$ for $R \in \mathbf{s}$. Let us
show that $P$ does not contain any fact $R(a)$
for $R\notin\mathbf{s}$. Otherwise, assume that $P$
contains $R(a)$ with $R \notin \mathbf{s}$. Then there
exists $\mathbf{s'} \subseteq \sigma$ such that $R \in
\mathbf{s'}$ and such that $a \in I_{\mathbf{s'}} \cup (
C_\mathbf{s'} \setminus \bigcup_{\mathbf{s'} \supsetneq
\mathbf{s''}} I_\mathbf{s''})$.
Since $\mathbf{s}$ does not contain $R$ while $\mathbf{s'}$
does, we have $\mathbf{s'} \not\subseteq \mathbf{s}$. But then
by ($\star$) we have that $I_\mathbf{s}$ and $I_{\mathbf{s'}}
\cup  C_\mathbf{s'}$ are disjoint, which is a contradiction
because $a$ is supposed to be in both $I_\mathbf{s}$
and $I_{\mathbf{s'}} \cup ( C_\mathbf{s'} \setminus
\bigcup_{\mathbf{s'} \supsetneq \mathbf{s''}}
I_\mathbf{s''})$.  Therefore, it is indeed the case that $P$
does not contain any fact $R(a)$ for $R\notin\mathbf{s}$.  Now,
if $P'$ contains a fact $R(a)$ for some $R \notin \sigma$ then
we are done since this would imply $P \neq P'$, a
contradiction. Hence we can assume that $P'$ does not contain any
fact $R(a)$ for $R \notin \sigma$.  We will now prove
that $P'$ does not contain all the facts $R(a)$ for $R \in
\sigma$, thus establishing a contradiction (because $P$ does, so we would have $P
\neq P'$) and concluding this proof.  Assume by contradiction
that $P'$ contains all the facts $R(a)$ for $R \in \mathbf{s}$.
First of all, observe that we have $a \notin C_\mathbf{s}$
because by ($\star$) we have that $I_\mathbf{s}$
and $C_\mathbf{s}$ are disjoint, and we know that $a \in
I_\mathbf{s}$. Hence, the only way in which $P'$ could contain
all the facts $R(a)$ for $R \in \mathbf{s}$ is if there
exist $\mathbf{s'}_1,\ldots,\mathbf{s'}_k$ with $k \geq 1$
and $\mathbf{s'}_j \subsetneq \mathbf{s}$ for $1 \leq j\leq k$
such that $\bigcup_{1 \leq j \leq k} \mathbf{s'}_j =
\mathbf{s}$ and such that for every $1 \leq j \leq k$ we have
that (i) $a \in I_{\mathbf{s'}_j} \cup ( C_{\mathbf{s'}_j}
\setminus \bigcup_{\mathbf{s'}_j \supsetneq \mathbf{s''}} I_\mathbf{s''})$.  Observe that there must
exist $1 \leq j_1,j_2 \leq k$ such that $\mathbf{s'}_{j_1}$
and $\mathbf{s'}_{j_2}$ are incomparable by inclusion
(otherwise, since all $\mathbf{s}_j$ are strictly included
in $\mathbf{s}$, their union could not be equal
to $\mathbf{s}$). Also observe that by ($\star$) we have that
the sets $I_{\mathbf{s'}_{j_1}} \cup C_{\mathbf{s'}_{j_1}}$ and
$I_{\mathbf{s'}_{j_2}} \cup C_{\mathbf{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 <ref> and tells us that by summing over all such tuples $(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})$ we cannot miss a completion of $D$:

Let $D'$ be a completion of $D$. Then there exists a tuple $(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})$ of subsets of $\dom$ satisfying ($\star$) such that $D' = P(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})$.

For $\emptyset \neq \mathbf{s} \subseteq \sigma$, let us define $D_\mathbf{s}$ to be the set of constants that occur in all relation of $\mathbf{s}$ and in none of the others. Define the set $I_\mathbf{s}$ for $\emptyset \neq \mathbf{s} \subseteq \sigma$ as follows: $I_\mathbf{s} \defeq D_\mathbf{s} \setminus C_\mathbf{s}$.
It is then routine to check that $(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})$ satisfies ($\star$) and is such that $D' = P(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})$.

Lemma <ref> and <ref> allows us to express the result as

\begin{equation}
\sum_{I_{\mathbf{s}_1} \subseteq \dom \setminus C} \ldots
\sum_{I_{\mathbf{s}_j} \subseteq (\dom \setminus (C \cup \bigcup_{1 \leq k < j} I_{\mathbf{s}_k})) \cup \bigcup_{\emptyset \neq \mathbf{s'}\subsetneq \mathbf{s}} C_\mathbf{s'}} \ldots
\sum_{I_{\mathbf{s}_L} \subseteq \dom \setminus (C_{\mathbf{s}_L} \cup \bigcup_{1 \leq k < L} I_{\mathbf{s}_k}) }
\checkp(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})
\end{equation}

where $\checkp(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L}) \in \{0,1\}$ is defined by

$$\checkp(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L})\defeq \begin{cases}
1 \text{ if } P(I_{\mathbf{s}_1},\ldots,I_{\mathbf{s}_L}) \text{ is a completion of } D \text{ that satisfies } q \\
0 \text{ otherwise}
\end{cases}.$$

As such we cannot evaluate this expression in .