# Counting Answers to Unions of Conjunctive Queries: Natural Tractability
Criteria and Meta-Complexity††thanks: For the purpose of Open Access, the
authors have applied a CC BY public copyright licence to any Author Accepted
Manuscript version arising from this submission. All data is provided in full
in the results section of this paper. Stanislav Živný was supported by UKRI
EP/X024431/1.

Jacob Focke
CISPA Helmholtz Center for Information Security
Saarbrücken
Germany  Leslie Ann Goldberg
Department of Computer Science
University of Oxford
United Kingdom  Marc Roth
Department of Computer Science
University of Oxford
United Kingdom  Stanislav Živný
Department of Computer Science
University of Oxford
United Kingdom

(17 November 2023)

###### Abstract

We study the problem of counting answers to unions of conjunctive queries
(UCQs) under structural restrictions on the input query. Concretely, given a
class $C$ of UCQs, the problem $\\#\textsc{UCQ}(C)$ provides as input a UCQ
$\Psi\in C$ and a database $\mathcal{D}$ and the problem is to compute the
number of answers of $\Psi$ in $\mathcal{D}$.

Chen and Mengel [PODS’16] have shown that for any recursively enumerable class
$C$, the problem $\\#\textsc{UCQ}(C)$ is either fixed-parameter tractable or
hard for one of the parameterised complexity classes $\mathrm{W}[1]$ or
$\\#\mathrm{W}[1]$. However, their tractability criterion is unwieldy in the
sense that, given any concrete class $C$ of UCQs, it is not easy to determine
how hard it is to count answers to queries in $C$. Moreover, given a single
specific UCQ $\Psi$, it is not easy to determine how hard it is to count
answers to $\Psi$.

In this work, we address the question of finding a _natural_ tractability
criterion: The combined conjunctive query of a UCQ
$\Psi=\varphi_{1}\vee\dots\vee\varphi_{\ell}$ is the conjunctive query
$\boldsymbol{\wedge}\left(\Psi\right)=\varphi_{1}\wedge\dots\wedge\varphi_{\ell}$.
We show that under natural closure properties of $C$, the problem
$\\#\textsc{UCQ}(C)$ is fixed-parameter tractable if and only if the combined
conjunctive queries of UCQs in $C$, and their contracts, have bounded
treewidth. A contract of a conjunctive query is an augmented structure, taking
into account how the quantified variables are connected to the free variables
— if all variables are free, then a conjunctive query is equal to its
contract; in this special case the criterion for fixed-parameter tractability
of $\\#\textsc{UCQ}(C)$ thus simplifies to the combined queries having bounded
treewidth.

Finally, we give evidence that a closure property on $C$ is necessary for
obtaining a natural tractability criterion: We show that even for a single UCQ
$\Psi$, the meta problem of deciding whether $\\#\textsc{UCQ}(\\{\Psi\\})$ can
be solved in time $O(|\mathcal{D}|^{d})$ is $\mathrm{NP}$-hard for any fixed
$d\geq 1$. Moreover, we prove that a known exponential-time algorithm for
solving the meta problem is optimal under assumptions from fine-grained
complexity theory. As a corollary of our reduction, we also establish that
approximating the Weisfeiler-Leman-Dimension of a UCQ is $\mathrm{NP}$-hard.

##  1 Introduction

Conjunctive queries are among the most fundamental and well-studied objects in
database theory [18, 60, 2, 45, 46, 59]. A conjunctive query (CQ) $\varphi$
with free variables $X=\\{x_{1},\ldots,x_{k}\\}$ and quantified variables
$Y=\\{y_{1},\ldots,y_{d}\\}$ is of the form

$\varphi(X)=\exists Y\,R_{1}(\mathbf{t}_{1})\wedge\ldots\wedge
R_{n}(\mathbf{t}_{n}),$

where $R_{1},\ldots,R_{n}$ are relational symbols and each $\mathbf{t}_{i}$ is
a tuple of variables from $X\cup Y$. A database $\mathcal{D}$ consists of a
set of elements $U(\mathcal{D})$, denoted the _universe_ of $\mathcal{D}$, and
a set of relations over this universe. The corresponding relation symbols are
the _signature_ of $\mathcal{D}$. If $R_{1},\dots,R_{n}$ are in the signature
of $\mathcal{D}$ then an _answer_ of $\varphi$ in $\mathcal{D}$ is an
assignment $a\colon X\to U(\mathcal{D})$ that has an extension to the
existentially quantified variables $Y$ that agrees with all the relations
$R_{1},\ldots,R_{n}$. Even more expressive is a union of conjunctive queries
(UCQ). Such a union is of the form

$\Psi(X)=\varphi_{1}(X)\vee\ldots\vee\varphi_{\ell}(X),$

where each $\varphi_{i}(X)$ is a CQ with free variables $X$. An answer to
$\Psi$ is then any assignment that is answer to at least one of the CQs in the
union.

Since evaluating a given CQ on a given database is NP-complete [18] a lot of
research focused on finding tractable classes of CQs. A fundamental result by
Grohe, Schwentick, and Segoufin [40] established that the tractability of
evaluating all CQs of bounded arity whose Gaifman graph is in some class of
graphs $C$ depends on whether or not the treewidth in $C$ is bounded.

More generally, finding an answer to a conjunctive query can be cast as
finding a (partial) homomorphism between relational structures, and therefore
is closely related to the framework of constraint satisfaction problems. In
this setting, Grohe [38] showed that treewidth modulo homomorphic equivalence
is the right criterion for tractability. There is also an important line of
work [36, 39, 48] culminating in the fundamental work by Marx [49] that
investigates the parameterised complexity for classes of queries with
unbounded arity. In general, tractability of conjunctive queries is closely
related to how “tree-like” or close to acyclic they are.

Counting answers to CQs has also received significant attention in the past
[26, 54, 29, 37, 20, 28, 3]. Chen and Mengel [19] gave a complete
classification for the counting problem on classes of CQs (with bounded arity)
in terms of a natural criterion loosely based on treewidth. They present a
trichotomy into fixed-parameter tractable, $\mathrm{W[1]}$-complete, and
$\\#\mathrm{W[1]}$-complete cases. In subsequent work [20], this
classification was extended to unions of conjunctive queries (and to even more
general queries in [28]). However, for UCQs, the established criteria for
tractability and intractability are implicit (see [20, Theorems 3.1 and 3.2])
in the sense that, given a specific UCQ $\Psi$, it is not at all clear how
hard it is to count answers to $\Psi$ based on the criteria in [20]. To make
this more precise: It is not even clear whether we can, in polynomial time in
the size of $\Psi$, determine whether answers to $\Psi$ can be counted in
linear time in the input database.

###  1.1 Our contributions

With the goal of establishing a more practical tractability criterion for
counting answers to UCQs, we explore the following two main questions in this
work:

> Q1) Is there a natural criterion that captures the fixed-parameter
> tractability of counting answers to a class of UCQs, parameterised by the
> size of the query?

> Q2) Is there a natural criterion that captures whether counting answers to a
> single fixed UCQ is linear-time solvable (in the size of a given database)?

##### Question Q1): Fixed-Parameter Tractability.

For a class $C$ of UCQs, we consider the problem $\\#\textsc{UCQ}(C)$ that
takes as input a UCQ $\Psi$ from $C$ and a database $\mathcal{D}$, and asks
for the number $\mathsf{ans}(\Psi\to\mathcal{D})$ of answers of $\Psi$ in
$\mathcal{D}$. We assume that the arity of the UCQs in $C$ is bounded, that
is, there is constant $c$ such that each relation that appears in some query
in $C$ has arity at most $c$. As explained earlier, due to a result of Chen
and Mengel [20], there is a known but rather unwieldy tractability criterion
for $\\#\textsc{UCQ}(C)$, when the problem is parameterised by the size of the
query. On a high level, the number of answers of a UCQ $\Psi$ in a given
database can be expressed as a finite linear combination of CQ answer counts,
using the principle of inclusion-exclusion. This means that

$\mathsf{ans}(\Psi\to\mathcal{D})=\sum_{i}c_{i}\cdot\mathsf{ans}(\varphi_{i}\to\mathcal{D}),$

where each $\varphi_{i}$ is simply a conjunctive query (and not a union
thereof). We refer to this linear combination as the _CQ expansion_ of $\Psi$.
Chen and Mengel showed that the parameterised complexity of computing
$\mathsf{ans}(\Psi\to\mathcal{D})$ is guided by the hardest term in the
respective CQ expansion. The complexity of computing these terms is simply the
complexity of counting the answers of a conjunctive query, and this is well
understood [19]. Hence, the main challenge for this approach is to understand
the linear combination, i.e., to understand for which CQs the corresponding
coefficients are non-zero. The problem is that the coefficients $c_{i}$ of
these linear combinations are alternating sums, which in similar settings have
been observed to encode algebraic and even topological invariants [56]. This
makes it highly non-trivial to determine which CQs actually contribute to the
linear combination. We introduce the concepts required to state this
classification informally, the corresponding definitions are given in Section
2.

We first give more details about the result of [19]. Let $\Gamma(C)$ be the
class of those conjunctive queries that contribute to the CQ expansion of at
least one UCQ in $C$, and that additionally are what we call
$\\#\text{minimal}$. Intuitively, a conjunctive query $\varphi$ is
$\\#\text{minimal}$ if there is no proper subquery $\varphi^{\prime}$ of
$\varphi$ that has the same number of answers as $\varphi$ in every given
database. Then the tractability criterion depends on the treewidth of the CQs
in $\Gamma(C)$. It also depends on the treewidth of the corresponding class
$\mathsf{contract}(\Gamma(C))$ of contracts (formally defined in Definition
20), which is an upper bound of what is called the “star size” in [29] and the
“dominating star size” in [28]. Here is the formal statement of the known
dichotomy for $\\#\textsc{UCQ}(C)$.

######  Theorem 1 ([20]).

Let $C$ be a recursively enumerable class of UCQs of bounded arity. If the
treewidth of $\Gamma(C)$ and of $\mathsf{contract}(\Gamma(C))$ is bounded,
then $\\#\textsc{UCQ}(C)$ is fixed-parameter tractable. Otherwise,
$\\#\textsc{UCQ}(C)$ is $\mathrm{W[1]}$-hard.

We investigate under which conditions this dichotomy can be simplified. We
show that for large classes of UCQs there is actually a much more natural
tractability criterion that does not rely on $\Gamma(C)$, i.e., here the
computation of the coefficients of the linear combinations as well as the
concept of #minimality do not play a role. We first show a simpler
classification for UCQs without existential quantifiers. To state the results
we require some additional definitions: The _combined query_
$\boldsymbol{\wedge}\left(\Psi\right)$ of a UCQ
$\Psi(X)=\varphi_{1}(X)\vee\dots\vee\varphi_{\ell}(X)$ is the conjunctive
query obtained from $\Psi$ by replacing each disjunction by a conjunction,
that is

$\boldsymbol{\wedge}\left(\Psi\right)=\varphi_{1}(X)\wedge\dots\wedge\varphi_{\ell}(X)\,.$

Given a class of UCQs $C$, we set
$\boldsymbol{\wedge}\left(C\right)=\\{\boldsymbol{\wedge}\left(\Psi\right)\mid\Psi\in
C\\}$.

It will turn out that the structure of the class of combined queries
$\boldsymbol{\wedge}\left(C\right)$ determines the complexity of counting
answers to UCQs in $C$, given that $C$ has the following natural closure
property: We say that $C$ is _closed under deletions_ if, for all
$\Psi(X)=\varphi_{1}(X)\vee\dots\vee\varphi_{\ell}(X)$ and for every
$J\subseteq[\ell]$, the subquery $\bigvee_{j\in J}\varphi_{j}(X)$ is also
contained in $C$. For example, any class of UCQs defined solely by the
conjunctive queries admissible in the unions (such as unions of acyclic
conjunctive queries) is closed under deletions. The following classification
resolves the complexity of counting answers to UCQs in classes that are closed
under deletions; we will see later that the closedness condition is necessary.
Moreover, the tractability criterion depends solely on the structure of the
combined query, and not on the terms in the CQ expansion, thus yielding, as
desired, a much more concise and natural characterisation. As mentioned
earlier, we first state the classification for quantifier-free UCQs.

######  Theorem 2.

Let $C$ be recursively enumerable class of quantifier-free UCQs of bounded
arity. If $\boldsymbol{\wedge}\left(C\right)$ has bounded treewidth then
$\\#\textsc{UCQ}(C)$ is fixed-parameter tractable. If
$\boldsymbol{\wedge}\left(C\right)$ has unbounded treewidth and $C$ is closed
under deletions then $\\#\textsc{UCQ}(C)$ is $\mathrm{W[1]}$-hard.

We emphasise here that Theorem 2 is in terms of the simpler object
$\boldsymbol{\wedge}\left(C\right)$ instead of the complicated object
$\Gamma(C)$.

If we allow UCQs with quantified variables in the class $C$ then the situation
becomes more intricate. Looking for a simple tractability criterion that
describes the complexity of $\\#\textsc{UCQ}(C)$ solely in terms of
$\boldsymbol{\wedge}\left(C\right)$ requires some additional effort. First,
for a UCQ $\Psi$ that has quantified variables, $\mathsf{contract}(\Psi)$ is
not necessarily the same as $\Psi$, and therefore the treewidth of the
contracts also plays a role. Moreover, the matching lower bound requires some
conditions in addition to being closed under deletions. Nevertheless, our
result is in terms of the simpler objects $\boldsymbol{\wedge}\left(C\right)$
and $\mathsf{contract}(\boldsymbol{\wedge}\left(C\right))$ rather than the
more complicated $\Gamma(C)$ and $\mathsf{contract}(\Gamma(C))$. For Theorem
3, recall that a conjunctive query is _self-join-free_ if each relation symbol
occurs in at most one atom of the query.

######  Theorem 3.

Let $C$ be a recursively enumerable class of UCQs of bounded arity. If
$\boldsymbol{\wedge}\left(C\right)$ and
$\mathsf{contract}(\boldsymbol{\wedge}\left(C\right))$ have bounded treewidth
then $\\#\textsc{UCQ}(C)$ is fixed-parameter tractable. Otherwise, if
(I)–(III) are satisfed, then $\\#\textsc{UCQ}(C)$ is $\mathrm{W[1]}$-hard.

  1. (I)

$C$ is closed under deletions.

  2. (II)

The number of existentially quantified variables of queries in $C$ is bounded.

  3. (III)

The UCQs in $C$ are unions of self-join-free conjunctive queries.

In Appendix A we show that Theorem 3 is tight in the sense that, if any of
these conditions is dropped, there are counterexamples to the claim that
tractability is guided solely by $\boldsymbol{\wedge}\left(C\right)$ and
$\mathsf{contract}(\boldsymbol{\wedge}\left(C\right))$.

##### Question Q2): Linear-Time Solvability.

Now we turn to the question of linear-time solvability for a single fixed UCQ.
The huge size of databases in modern applications motivates the question of
which query problems are actually linear-time solvable. Along these lines,
there is a lot of research for enumeration problems [60, 6, 17, 9, 10, 13].

The question whether counting answers to a conjunctive query $\varphi$ can be
achieved in time linear in the given database has been studied previously
[50]. The corresponding dichotomy is well known and was discovered multiple
times by different authors in different contexts.111We remark that [9, Theorem
7] focuses on the special case of graphs and _near_ linear time algorithms.
However, in the word RAM model with $O(\log n)$ bits, a linear time algorithm
is possible [17]. In these results, the tractability criterion is whether
$\varphi$ is _acyclic_ , i.e., whether it has a join tree (see [35]). The
corresponding lower bounds are conditioned on some widely used complexity
assumptions from fine-grained complexity, namely the SETH or the Triangle
Conjecture. We define all of the complexity assumptions that we use in this
work in Section 2. There we also formally define the size of a database (as
the sum of the size of its signature, its universe, and its relations).

It is well-known that, for acyclic and quantifier-free conjunctive queries,
the linear-time decision algorithm based on join-trees is also able to count
solutions (see e.g. Theorem 7 in [9] for the special case of graph
homomorphisms or Corollary 2 in [50] for the general case222Note that [50]
states the result for self-join-free _free-connex_ conjunctive queries; we
point out that, in the quantifier-free case, being free-connex is equivalent
to being acyclic. Moreover, the condition for being self-join-free is only
needed in the presence of existentially quantified variables.) Moreover, both
results show that acyclicity is also necessary for linear-time tractability
unless either the Triangle Conjecture or the SETH fail.

######  Theorem 4 (Folklore, see e.g. [50, 9]).

Let $\varphi$ be a quantifier-free conjunctive query and suppose that at least
one of the Triangle Conjecture and SETH is true. Then the number of answers of
$\varphi$ in a given database $\mathcal{D}$ can be computed in time linear in
the size of $\mathcal{D}$ if and only if $\varphi$ is acyclic.

We note that the previous theorem is false if quantified variables were
allowed as this would require the consideration of semantic acyclicity333A
conjunctive query is semantically acyclic if and only if its #core (Definition
19) is acyclic. (see [8]).

Theorem 4 yields an efficient way to check whether counting answers to a
quantifier-free conjunctive query $\varphi$ can be done in linear time: Just
check whether $\varphi$ is acyclic (in polynomial time, see for instance
[35]). We investigate the corresponding question for _unions_ of conjunctive
queries. In stark contrast to Theorem 4, we show that there is no efficiently
computable criterion that determines the linear-time tractability of counting
answers to _unions_ of conjunctive queries, unless some conjectures of fine-
grained complexity theory fail.

We first observe that, as in the investigation of question Q1), one can obtain
a criterion for linear-time solvability by expressing UCQ answer counts as
linear combinations of CQ answer counts. Concretely, by a straightforward
extension of previous results, we show that, assuming SETH or the Triangle
Conjecture, a linear combination of CQ answer counts can be computed in linear
time if and only if the answers to each $\\#\text{minimal}$ CQ in the linear
combination can be computed in linear time, that is, if each such CQ is
acyclic. However, this criterion is again unwieldy in the sense that, for all
we know, it may take time exponential in the size of the respective UCQ to
determine whether this criterion holds.

In view of our results for question Q1) about fixed-parameter tractability,
one might suspect that a more natural and simpler tractability criterion
exists. However, it turns out that even under strong restrictions on the UCQs
that we consider, an efficiently computable criterion is unlikely. We make
this formal by studying the following meta problem.444For the question Q1),
considering a similar meta problem is not feasible as, in this case, the meta
problem takes as input a class of graphs. If such a class were encoded as a
Turing machine, the meta problem would be undecidable by Rice’s theorem.

Name:

Meta

Input:

A union $\Psi$ of quantifier-free conjunctive queries.

Output:

Is it possible to count answers to $\Psi$ in time linear in the size of
$\mathcal{D}$.

Restricting the input of Meta to quantifier-free queries is sensible as,
without this restriction, the meta problem is known to be $\mathrm{NP}$-hard
even for conjunctive queries: If all variables are existentially quantified,
then evaluating a conjunctive query can be done in linear time if and only if
the query is semantically acyclic [60] (the “only if” relies on standard
hardness assumptions). However, verifying whether a conjunctive query is
semantically acyclic is already $\mathrm{NP}$-hard [8]. In contrast, when
restricted to quantifier-free conjunctive queries, the problem Meta is
polynomially-time solvable according to Theorem 4.

We can now state our main result about the complexity of Meta. The hardness
results hold under substantial additional input restrictions, which make these
results stronger.

######  Theorem 5.

The problem Meta can be solved in time $|\Psi|^{O(1)}\cdot O(2^{\ell})$, where
$\ell$ is the number of conjunctive queries in the union, if at least one of
the SETH and the Triangle Conjecture is true. Moreover,

  * •

If the Triangle Conjecture is true then Meta is $\mathrm{NP}$-hard. If,
additionally, ETH is true, then Meta cannot be solved in time $2^{o(\ell)}$.

  * •

If SETH is true then Meta is $\mathrm{NP}$-hard and cannot be solved in time
$2^{o(\ell)}$.

  * •

If the non-uniform ETH is true then Meta is $\mathrm{NP}$-hard and

$\textsc{Meta}\notin\bigcap_{\varepsilon>0}\mathrm{DTime}(2^{\varepsilon\cdot\ell})\,.$

The lower bounds remain true even if $\Psi$ is a union of self-join-free and
acyclic conjunctive queries over a binary signature (that is, of arity $2$).

We make some remarks about Theorem 5. First, it may seem counterintuitive that
the algorithmic part of this result relies on some lower bound conjectures.
This is explained by the fact that an algorithmic result for Meta is actually
a classification result for the underlying counting problem. The lower bound
conjectures are the reason that the algorithm for Meta can answer that a
linear-time algorithm is _not_ possible for certain UCQs.

Second, while for counting the answers to a CQ in linear time the property of
being acyclic is the right criterion, note that for unions of CQs, acyclicity
is not even sufficient for tractability. Even when restricted to unions of
acyclic conjunctive queries, the meta problem is $\mathrm{NP}$-hard.

Third, we elaborate on the idea that we use to prove Theorem 5. As mentioned
before, the algorithmic part of Theorem 5 comes from the well-known technique
of expressing UCQ answer counts in terms of linear combinations of CQ answer
counts, and establishing a corresponding complexity monotonicity property, see
Section 2.4. The more interesting result is the hardness part. Here we
discover a connection between the meta question stated in Meta, and a
topological invariant, namely, the question whether the reduced Euler
characteristic of a simplicial complex is non-zero. It is known that
simplicial complexes with non-vanishing reduced Euler characteristic are
evasive, and as such this property is also related to Karp’s Evasiveness
Conjecture (see e.g. the excellent survey of Miller [51]). We use the known
fact that deciding whether the reduced Euler characteristic is vanishing is
$\mathrm{NP}$-hard [57]. Roughly, the reduction works as follows. Given some
simplicial complex $\Delta$, we carefully define a UCQ $\Psi_{\Delta}$ in such
a way that only one particular term in the CQ expansion of $\Psi_{\Delta}$
determines the linear-time tractability of counting answers to
$\Psi_{\Delta}$. However, the coefficient of this term is zero precisely if
the reduced Euler characteristic of $\Delta$ is vanishing.

It turns out that, as additional consequences of our reduction in the proof of
Theorem 5, we also obtain lower bounds for (approximately) computing the so-
called Weisfeiler-Leman-dimension of a UCQ.

##### Consequences for the Weisfeiler-Leman-dimension of quantifier-free UCQs

During the last decade we have witnessed a resurge in the study of the
_Weisfeiler-Leman-dimension_ of graph classes and graph parameters [4, 34, 27,
44, 52, 7]. The Weisfeiler-Leman algorithm (WL-algorithm) and its higher-
dimensional generalisations are important heuristics for graph isomorphism;
for example, the $1$-dimensional WL-algorithm is equivalent to the method of
colour-refinement. We refer the reader to e.g. the EATCS Bulletin article of
Arvind [4] for a concise and self-contained introduction; however, in this
work we will use the WL-algorithm only in a black-box manner.

For each positive integer $k$, we say that two graphs $G_{1}$ and $G_{2}$ are
$k$-_WL equivalent_ , denoted by $G_{1}\cong_{k}G_{2}$, if they cannot be
distinguished by the $k$-dimensional WL-algorithm. A graph parameter $\pi$ is
called $k$_-WL invariant_ if $G_{1}\cong_{k}G_{2}$ implies
$\pi(G_{1})=\pi(G_{2})$. Moreover, the _WL-dimension_ of $\pi$ is the minimum
$k$ for which $\pi$ is $k$-WL invariant, if such a $k$ exists, and $\infty$
otherwise (see e.g.[5]). The WL-dimension of a graph parameter $\pi$ provides
important information about the descriptive complexity of $\pi$ [15].
Moreover, recent work of Morris et al. [52] shows that the WL-dimension of a
graph parameter lower bounds the minimum dimension of a higher-order Graph
Neural Network that computes the parameter.

The definitions of the WL-algorithm and the WL-dimension extend from graphs to
labelled graphs, that is, directed multi-graphs with edge- and vertex-labels
(see e.g. [47]). Formally, we say that a database is a _labelled graph_ if its
signature has arity at most $2$, and if it contains no self-loops, that is,
tuples of the form $(v,v)$. Similarly, _(U)CQs on labelled graphs_ have
signatures of arity at most $2$ and contain no atom of the form $R(v,v)$.

######  Definition 6 (WL-dimension).

Let $\Psi$ be a UCQ on labelled graphs. The _WL-dimension_ of $\Psi$, denoted
by $\mathsf{dim}_{\mathrm{WL}}(\Psi)$, is the minimum $k$ such that, for any
pair of labelled graphs $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ with
$\mathcal{D}_{1}\cong_{k}\mathcal{D}_{2}$, it holds that the number of answers
to $\Psi$ in $\mathcal{D}_{1}$ is the same as in $\mathcal{D}_{2}$. If no such
$k$ exists, then the WL-dimension is $\infty$.

Note that a CQ is a special case of a UCQ, so Definition 6 also applies when
$\Psi$ is a CQ $\varphi$.

It was shown very recently that the WL-dimension of a _quantifier-free
conjunctive query_ $\varphi$ on labelled graphs is equal to the treewidth of
the Gaifman graph of $\varphi$ [53, 47]. Using known algorithms for computing
the treewidth [14, 30] it follows that, for every fixed positive integer $d$,
the problem of deciding whether the WL-dimension of $\varphi$ is at most $d$
can be solved in polynomial time (in the size of $\varphi$). Moreover, the WL-
dimension of $\varphi$ can be efficiently approximated in polynomial time.

In stark contrast, we show that the computation of the WL-dimension of a _UCQ_
is much harder; in what follows, we say that $S$ is an $f$-_approximation_ of
$k$ if $k\leq S\leq f(k)\cdot k$.

######  Theorem 7.

There is an algorithm that computes a $O(\sqrt{\log k})$-approximation of the
WL-dimension $k$ of a quantifier-free UCQ on labelled graphs
$\Psi=\varphi_{1}\vee\dots\vee\varphi_{\ell}$ in time $|\Psi|^{O(1)}\cdot
O(2^{\ell})$.

Moreover, let $f:\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ be any computable
function. The problem of computing an $f$-approximation of
$\mathsf{dim}_{\mathrm{WL}}(\Psi)$ given an input UCQ
$\Psi=\varphi_{1}\vee\dots\vee\varphi_{\ell}$ is NP-hard, and, assuming ETH,
an $f$-approximation of $\mathsf{dim}_{\mathrm{WL}}(\Psi)$ cannot be computed
in time $2^{o(\ell)}$.

Finally, the computation of the WL-dimension of UCQs stays intractable even if
we fix $k$.

######  Theorem 8.

Let $k$ be any _fixed_ positive integer. The problem of deciding whether the
WL-dimension of a quantifier-free UCQ on labelled graphs
$\Psi=\varphi_{1}\vee\dots\vee\varphi_{\ell}$ is at most $k$ can be solved in
time $|\Psi|^{O(1)}\cdot O(2^{\ell})$.

Moreover, the problem is $\mathrm{NP}$-hard and, assuming ETH, cannot be
solved in time $2^{o(\ell)}$.

###  1.2 Further Related Work

For exact counting it makes a substantial difference whether one wants to
count answers to a conjunctive query or a union of conjunctive queries [20,
28]. However, for approximate counting, unions can generally be handled using
a standard trick of Karp and Luby [43], and therefore fixed-parameter
tractability results for approximately counting the answers to a conjunctive
query also extend to unions of conjunctive queries [3, 32].

Counting and enumerating the answers to a union of conjunctive queries has
also been studied in the context of dynamic databases [11, 12]. This line of
research investigates the question whether linear-time dynamic algorithms are
possible. Concretely, the question is whether, after a preprocessing step that
builds a data structure in time linear in the size of the initial database,
the number of answers to a fixed union of conjunctive queries can be returned
in constant time with a constant-time update to the data structure, whenever
there is a change to the database. Berkholz et al. show that for a conjunctive
query such a linear-time algorithm is possible if and only if the CQ is _$q$
-hierarchical_ [11, Theorem 1.3]. There are acyclic CQs that are not
$q$-hierarchical, for instance the query $\varphi(\\{a,b,c,d\\})=E(a,b)\wedge
E(b,c)\wedge E(c,d)$ is clearly acyclic — however, the sets of atoms that
contain $b$ and $c$, respectively, are neither comparable nor disjoint, and
therefore $\varphi$ is not $q$-hierarchical. So, there are queries for which
counting in the static setting is easy, whereas it is hard in the dynamic
setting. Berkholz et al. extend their result from CQs to UCQs [12, Theorem
4.5], where the criterion is whether the UCQ is _exhaustively
$q$-hierarchical_. This property essentially means that, for every subset of
the CQs in the union, if instead of taking the disjunction of these CQs we
take the conjunction, then the resulting CQ should be $q$-hierarchical.
Moreover, checking whether a CQ $\phi$ is $q$-hierarchical can be done in time
polynomial in the size of $\phi$. However, the straightforward approach of
checking whether a UCQ is exhaustively $q$-hierarchical takes exponential
time, and it is stated as an open problem in [12] whether this can be
improved. In the dynamic setting this question remains open — however, in the
static setting we show that, while for counting answers to CQs the criterion
for linear-time tractability can be verified in polynomial time, this is not
true for unions of conjunctive queries, subject to some complexity
assumptions, as we have seen in Theorem 5.

##  2 Preliminaries

Due to the fine-grained nature of the questions we ask in this work (e.g.
linear time counting vs non-linear time counting), it is important to specify
the machine model. We use the standard word RAM model with $O(\log n)$ bits.
The exact model makes a difference. For example, it is possible to count
answers to quantifier-free acyclic conjunctive queries in linear time in the
word RAM model [17], while Turing machines only achieve near linear time (or
expected linear time) [9].

###  2.1 Parameterised and Fine-grained Complexity Theory

A _parameterised counting problem_ is a pair consisting of a function
$P:\\{0,1\\}^{\ast}\to\mathbb{N}$ and a computable555Some authors require the
parameterisation to be polynomial-time computable; see the discussion in the
standard textbook of Flum and Grohe [31]. In this work, the parameter will
always be the size of the input query, which can clearly be computed in
polynomial time. parameterisation $\kappa:\\{0,1\\}^{\ast}\to\mathbb{N}$. For
example, in the problem $\\#\textsc{Clique}$ the function maps an input (a
graph $G$ and a positive integer $k$, encoded as a string in
$\\{0,1\\}^{\ast}$ to the number of $k$-cliques in $G$. The parameter is $K$
so $\kappa(G,k)=k$.

A parameterised counting problem $(P,\kappa)$ is called _fixed-parameter
tractable_ (FPT) if there is a computable function $f$ and an algorithm
$\mathbb{A}$ that, given input $x$, computes $P(x)$ in time
$f(\kappa(x))\cdot|x|^{O(1)}$. We call $\mathbb{A}$ an _FPT-algorithm_ for
$(P,\kappa)$.

A _parameterised Turing-reduction_ from $(P,\kappa)$ to
$(P^{\prime},\kappa^{\prime})$ is an algorithm $\mathbb{A}$ equipped with
oracle access to $P^{\prime}$ that satisfies the following two constraints:
(I) $\mathbb{A}$ is an FPT-algorithm for $(P,\kappa)$, and (II) there is a
computable function $g$ such that, when the algorithm $\mathbb{A}$ is run with
input $x$, every oracle query $y$ to $(P^{\prime},\kappa^{\prime})$ has the
property that the parameter $\kappa^{\prime}(y)$ is bounded by $g(\kappa(x))$.
We write $(P,\kappa)\leq^{\mathsf{FPT}}(P^{\prime}\kappa^{\prime})$ if a
parameterised Turing-reduction exists.

Evidence for the non-existence of FPT algorithms is usually given by hardness
for the parameterised classes $\\#\mathrm{W[1]}$ and $\mathrm{W[1]}$, which
can be considered to be the parameterised versions of $\\#\mathrm{P}$ and
$\mathrm{NP}$. The definition of those classes uses bounded-weft circuits, and
we refer the interested reader e.g. to the standard textbook of Flum and Grohe
[31] for a comprehensive introduction. For this work, it suffices to rely on
the clique problem to establish hardness for those classes: A parameterised
counting problem $(P,\kappa)$ is _$\\#\mathrm{W[1]}$ -hard_ if
$\\#\textsc{Clique}\leq^{\mathsf{FPT}}(P,\kappa)$, and it is _$\mathrm{W[1]}$
-hard_ if $\textsc{Clique}\leq^{\mathsf{FPT}}(P,\kappa)$, where Clique is the
decision version of $\\#\textsc{Clique}$, that is, given $G$ and $k$, the task
is to decide whether there is at least one $k$-clique in $G$. As observed in
previous works [19], if all variables are existentially quantified, the
problem of counting answers to a conjunctive query actually encodes a decision
problem. So it comes to no surprise that both complexity classes
$\mathrm{W[1]}$ and $\\#\mathrm{W[1]}$ are relevant for its classification. It
is well known (see e.g. [21, 22, 25] that $\mathrm{W[1]}$-hard and
$\\#\mathrm{W[1]}$-hard problems are not fixed-parameter tractable, unless the
Exponential Time Hypothesis fails. This hypothesis is stated as follows.

######  Conjecture 9 (ETH [41]).

$3$-SAT cannot be solved in time $\exp(o(n))$, where $n$ denotes the number of
variables of the input formula.

We also rely on the Strong Exponential Time Hypothesis (SETH) and on a non-
uniform version of the Exponential Time Hypothesis, both of which are defined
below.

######  Conjecture 10 (SETH [41, 16]).

For each $\varepsilon>0$ there exists a positive integer $k$ such that $k$-SAT
cannot be solved in time $O(2^{(1-\varepsilon)n})$, where $n$ denotes the
number of variables of the input formula.

######  Conjecture 11 (Non-uniform ETH [23]).

$3$-$\textsc{SAT}\notin\bigcap_{\varepsilon>0}\mathrm{DTime}(\exp(\varepsilon
n))$, where $n$ denotes the number of variables of the input formula.

Clearly, non-uniform ETH implies ETH. Moreover, it is well known that SETH
implies ETH via the Sparsification Lemma [42]. This proof also shows that SETH
implies non-uniform ETH, so we have the following lemma.

######  Lemma 12 ([42]).

SETH $\Rightarrow$ non-uniform ETH $\Rightarrow$ ETH.

Finally, for ruling out linear-time algorithms, we will rely on the Triangle
Conjecture:

######  Conjecture 13 (Triangle Conjecture [1]).

There exists $\gamma>0$ such that any (randomised) algorithm that decides
whether a graph with $n$ vertices and $m$ edges contains a triangle takes time
at least $\Omega(m^{1+\gamma})$ in expectation.

###  2.2 Structures, Homomorphisms, and Conjunctive Queries

A _signature_ is a finite tuple $\tau=(R_{1},\dots,R_{s})$ where each $R_{i}$
is a relation symbol and comes with an arity $a_{i}$. The arity of a signature
is the maximum arity of its relation symbols. A _structure_ $\mathcal{A}$ over
$\tau$ consists of a finite universe $U(\mathcal{A})$ and a relation
$R^{\mathcal{A}}_{i}$ of arity $a_{i}$ for each relation symbol $R_{i}$ of
$\tau$. As usual in relational algebra, we view _databases_ as relational
structures. We encode a structure by listing its signature, its universe and
its relations. Therefore, given a structure $\mathcal{A}$ over $\tau$, we set
$|\mathcal{A}|=|\tau|+|U(\mathcal{A})|+\sum_{R\in\tau}|R^{\mathcal{A}}|\cdot
a_{R}$, where $a_{R}$ is the arity of $R$.

For example, a _graph_ $G$ is a structure over the signature $(E)$ where $E$
has arity $2$. The _Gaifman graph_ of a structure $\mathcal{A}$ has as
vertices the universe $U(\mathcal{A})$ of $\mathcal{A}$, and for each pair of
vertices $u,v$, there is an edge $\\{u,v\\}$ in $E$ if and only if at least
one of the relations of $\mathcal{A}$ contains a tuple containing both $u$ and
$v$. Note that the edge set $E$ of a Gaifman graph is symmetric and
irreflexive.

Let $\mathcal{A}$ and $\mathcal{B}$ be structures over the same signature
$\tau$. Then $\mathcal{A}$ is a _substructure_ of $\mathcal{B}$ if
$U(\mathcal{A})\subseteq U(\mathcal{B})$ and, for each relation symbol $R$ in
$\tau$, it holds that $R^{\mathcal{A}}\subseteq R^{\mathcal{B}}\cap
U(\mathcal{A})^{a}$, where $a$ is the arity of $R$. A substructure is
_induced_ if, for each relation symbol $R$ in $\tau$, we have
$R^{\mathcal{A}}=R^{\mathcal{B}}\cap U(\mathcal{A})^{a}$. A substructure
$\mathcal{A}$ of $\mathcal{B}$ with $\mathcal{A}\neq\mathcal{B}$ is a _proper
substructure_ of $\mathcal{B}$. We also define the _union_
$\mathcal{A}\cup\mathcal{B}$ of two structures $\mathcal{A}$ and $\mathcal{B}$
as the structure over $\tau$ with universe $U(\mathcal{A})\cup U(\mathcal{B})$
and $R^{\mathcal{A}\cup\mathcal{B}}=R^{\mathcal{A}}\cup R^{\mathcal{B}}$. Note
that the union is well-defined even if the universes are not disjoint.

##### Homomorphisms as Answers to CQs

Let $\mathcal{A}$ and $\mathcal{B}$ be structures over signatures
$\tau_{\mathcal{A}}\subseteq\tau_{\mathcal{B}}$. A _homomorphism_ from
$\mathcal{A}$ to $\mathcal{B}$ is a mapping $h:U(\mathcal{A})\to
U(\mathcal{B})$ such that for each relation symbol $R\in\tau_{\mathcal{A}}$
with arity $a$ and each tuple $\vec{t}=(t_{1},\dots,t_{a})\in R^{\mathcal{A}}$
we have that $h(\vec{t})=(h(t_{1}),\dots,h(t_{a}))\in R^{\mathcal{B}}$. We use
$\mathsf{Hom}(\mathcal{A}\to\mathcal{B})$ to denote the set of homomorphisms
from $\mathcal{A}$ to $\mathcal{B}$, and we use the lower case version
$\mathsf{hom}(\mathcal{A}\to\mathcal{B})$ to deonote the _number_ of
homomorphisms from $\mathcal{A}$ to $\mathcal{B}$.

Let $\varphi$ be a conjunctive query with free variables
$X=\\{x_{1},\dots,x_{k}\\}$ and quantified variables
$Y=\\{y_{1},\dots,y_{d}\\}$. We can associate $\varphi$ with a structure
$\mathcal{A}_{\varphi}$ defined as follows: The universe of
$\mathcal{A}_{\varphi}$ are the variables $X\cup Y$ and for each atom
$R(\vec{t})$ of $\varphi$ we add the tuple $\vec{t}$ to $R^{\mathcal{A}}$. It
is well-known that, for each database $\mathcal{D}$, the set of answers of
$\varphi$ in $\mathcal{D}$ is precisely the set of assignments $a:X\to
U(\mathcal{D})$ such that there is a homomorphism
$h\in\mathsf{Hom}(\mathcal{A}_{\varphi}\to\mathcal{D})$ with $h|_{X}=a$. Since
working with (partial) homomorphisms will be very convenient in this work, we
will use the notation from [28] and (re)define a conjunctive query as a pair
consisting of a relational structure $\mathcal{A}$ together with a set
$X\subseteq U(\mathcal{A})$. The size of $(\mathcal{A},X)$ is denoted by
$|(\mathcal{A},X)|$ and defined to be $|\mathcal{A}|+|X|$. Furthermore, we
define

$\mathsf{Ans}((\mathcal{A},X)\to\mathcal{D}):=\\{a:X\to
U(\mathcal{D})\leavevmode\nobreak\ |\leavevmode\nobreak\ \exists
h\in\mathsf{Hom}(\mathcal{A}\to\mathcal{D}):h|_{X}=a\\}$

as the set of answers of $(\mathcal{A},X)$ in $\mathcal{D}$. We then use
$\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})$ to denote the number of answers,
i.e.,
$\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})\coloneqq|\mathsf{Ans}((\mathcal{A},X)\to\mathcal{D})|$.

We can now formally define the (parameterised) problem of counting answers to
conjunctive queries. As is usual, we restrict the problem by a class $C$ of
allowed queries.

Name:

$\\#\textsc{CQ}(C)$

Input:

A conjunctive query $(\mathcal{A},X)\in C$ together with a database
$\mathcal{D}$.

Parameter:

$|(\mathcal{A},X)|$.

Output:

The number of answers $\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})$.

##### Acyclicity and (Hyper-)Treewidth

A structure of arity $2$ is _acyclic_ if its Gaifman graph is acyclic. For
higher arities, a structure is acyclic if it has a join-tree or, equivalently,
if it has (generalised) hyper-treewidth at most $1$ (see [36]). We will not
need the concept of hyper-treewidth, but we refer the reader to [35] for a
comprehensive treatment.

The treewidth of graphs and structures is defined as follows

######  Definition 14 (Tree decompositions, treewidth).

Let $G$ be a graph. A _tree decomposition_ of $G$ is a pair $(T,B)$, where $T$
is a (rooted) tree, and $B$ assigns each vertex $t\in V(T)$ a _bag_ $B_{t}$
such that the following constraints are satisfied:

  * (C1)

$V(G)=\bigcup_{t\in V(T)}B_{t}$,

  * (C2)

For each edge $e\in E(G)$ there exists $t\in V(T)$ such that $e\subseteq
B_{t}$, and

  * (C3)

For each $v\in V(G)$, the subgraph of $T$ containing all vertices $t$ with
$v\in B_{t}$ is connected.

The _width_ of a tree decomposition is $\max_{t\in V(T)}|B_{t}|-1$, and the
_treewidth_ of $G$ is the minimum width of any tree decomposition of $G$.
Finally, the treewidth of a structure is the treewidth of its Gaifman graph.

##### #Equivalence, #Minimality, and #Cores

In the realm of decision problems, it is well known that evaluating a
conjunctive query is equivalent to evaluating the (homomorphic) core of the
query, i.e., evaluating the minimal homomorphic-equivalent query. A similar,
albeit slightly different notion of equivalence and minimality is required for
counting answers to conjunctive queries. In what follows, we will provide the
necessary definitions and properties of equivalence, minimality and cores for
counting answers to conjunctive queries, and we refer the reader to [20] and
to the full version of [28] for a more comprehensive discussion. To avoid
confusion between the notions in the realms of decision and counting, we will
from now on use the # symbol for the counting versions (see Definition 16).

######  Definition 15.

Two conjunctive queries $(\mathcal{A},X)$ and
$(\mathcal{A}^{\prime},X^{\prime})$ are _isomorphic_ , denoted by
$(\mathcal{A},X)\cong(\mathcal{A}^{\prime},X^{\prime})$, if there is an
isomorphism $b$ from $\mathcal{A}$ to $\mathcal{A}^{\prime}$ with
$b(X)=X^{\prime}$.

######  Definition 16 (#Equivalence and #minimality (see [20, 28])).

Two conjunctive queries $(\mathcal{A},X)$ and
$(\mathcal{A}^{\prime},X^{\prime})$ are _$\\#\text{equivalent}$_ , denoted by
$(\mathcal{A},X)\sim(\mathcal{A}^{\prime},X^{\prime})$, if for every database
$\mathcal{D}$ we have
$\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})=\mathsf{ans}((\mathcal{A}^{\prime},X^{\prime})\to\mathcal{D})$.
A conjunctive query $(\mathcal{A},X)$ is _$\\#\text{minimal}$_ if there is no
proper substructure $\mathcal{A}^{\prime}$ of $\mathcal{A}$ such that
$(\mathcal{A},X)\sim(\mathcal{A}^{\prime},X)$.

######  Observation 17.

The following are equivalent:

  1. 1.

A conjunctive query $(\mathcal{A},X)$ is _$\\#\text{minimal}$_.

  2. 2.

$(\mathcal{A},X)$ has no $\\#\text{equivalent}$ substructure that is induced
by a set $U$ with $X\subseteq U\subset U(\mathcal{A})$.

  3. 3.

Every homomorphism from $\mathcal{A}$ to itself that is the identity on $X$ is
surjective.

It turns out that #equivalence is the same as isomorphism if all variables are
free, and it is the same as homomorphic equivalence if all variables are
existentially quantified (see e.g. the discussion in Section 5 in the full
version of [28]). Moreover, each quantifier-free conjunctive query is
$\\#\text{minimal}$.

######  Lemma 18 (Corollary 54 in full version of [28]).

If $(\mathcal{A},X)$ and $(\mathcal{A}^{\prime},X^{\prime})$ are
$\\#\text{minimal}$ and $(\mathcal{A},X)\sim(\mathcal{A}^{\prime},X^{\prime})$
then $(\mathcal{A},X)\cong(\mathcal{A}^{\prime},X^{\prime})$.

As isomorphism trivially implies #equivalence, Lemma 18 shows that, for
$\\#\text{minimal}$ queries, #equivalence and isomorphism coincide.

######  Definition 19 ($\\#\text{core}$).

A _$\\#\text{core}$_ of a conjunctive query $(\mathcal{A},X)$ is a
$\\#\text{minimal}$ conjunctive query $(\mathcal{A}^{\prime},X^{\prime})$ with
$(\mathcal{A},X)\sim(\mathcal{A}^{\prime},X^{\prime})$.

By Lemma 18, the $\\#\text{core}$ is unique up to isomorphisms; in fact, this
allows us to speak of “the” $\\#\text{core}$ of a conjunctive query.

##### Classification of $\\#\textsc{CQ}(C)$ via Treewidth and Contracts

It is well known that the complexity of counting answers to a conjunctive
query is governed by its treewidth, and by the treewidth of its contract [19,
28], which we define as follows.

######  Definition 20 (Contract).

Let $(\mathcal{A},X)$ be a conjunctive query, let $Y=U(\mathcal{A})\setminus
X$, and let $G$ be the Gaifmann graph of $\mathcal{A}$. The _contract_ of
$(\mathcal{A},X)$, denoted by $\mathsf{contract}(\mathcal{A},X)$ is obtained
from $G[X]$ by adding an edge between each pair of vertices $u$ and $v$ for
which there is a connected component $S$ in $G[Y]$ that is adjacent to both
$u$ and $v$, that is, there are vertices $x,y\in S$ such that $\\{x,u\\}\in
E(G)$ and $\\{y,v\\}\in E(G)$. Given a class of conjunctive queries $C$, we
write $\mathsf{contract}(C)$ for the class of all contracts of queries in $C$.

We note that there are multiple equivalent ways to define the contract of a
query. For our purposes, the definition in [28] is most suitable. Also, the
treewidth of the contract of a conjunctive query is an upper bound of what is
called the query’s “star size” in [29] and its “dominating star size” in [28].

Chen and Mengel established the following classification for counting answers
to conjunctive queries of bounded arity.

######  Theorem 21 ([19]).

Let $C$ be a recursively enumerable class of conjunctive queries of bounded
arity, and let $C^{\prime}$ be the class of $\\#\text{cores}$ of queries in
$C$. If the treewidth of $C^{\prime}$ and of $\mathsf{contract}(C^{\prime})$
is bounded, then $\\#\textsc{CQ}(C)$ is solvable in polynomial time.
Otherwise, $\\#\textsc{CQ}(C)$ is $\mathrm{W[1]}$-hard.

We point out that the $\mathrm{W[1]}$-hard cases can further be partitioned
into $\mathrm{W[1]}$-complete, $\\#\mathrm{W[1]}$-complete and even harder
cases [19, 28].666Those cases are: $\\#\mathrm{W[2]}$-hard and
$\\#\mathrm{A}[2]$-complete. However, for the purpose of this work, we are
only interested in tractable and intractable cases (recall that
$\mathrm{W[1]}$-hard problems are not fixed-parameter tractable under standard
assumptions from fine-grained and parameterised complexity theory, such as
ETH).

##### Self-join-free Conjunctive Queries and Isolated Variables

A conjunctive query $(\mathcal{A},X)$ is _self-join-free_ if each relation of
$\mathcal{A}$ contains at most one tuple. We say that a variable of a
conjunctive query is _isolated_ if it is not part of any relation.

Note that that adding/removing isolated variables to/from a conjunctive query
does not change its treewidth or the treewidth of its $\\#\text{core}$.
Further, it does not change the complexity of counting answers: Just
multiply/divide by $n^{v}$, where $n$ is the number of elements of the
database and $v$ it the number of added/removed isolated free variables. For
this reason, we will allow ourselves in this work to freely add and remove
isolated variables from the queries that we encounter. For the existence of
homomorphisms we also observe the following.

######  Observation 22.

Let $(\mathcal{A},X)$ be a conjunctive query, let $X^{\prime}$ be a superset
of $X$ and let $\mathcal{A}^{\prime}$ be the structure obtained from
$\mathcal{A}$ by adding an isolated variable for each $x\in
X^{\prime}\setminus X$. Then for all $a:X^{\prime}\to U(\mathcal{D})$ we have
that $a|_{X}\in\mathsf{Ans}((\mathcal{A},X)\to\mathcal{D})$ iff
$a\in\mathsf{Ans}((\mathcal{A}^{\prime},X^{\prime})\to\mathcal{D})$.

###  2.3 Unions of CQs and the Homomorphism Basis

A _union of conjunctive queries_ (UCQ) $\Psi$ is a tuple of structures
$(\mathcal{A}_{1},\ldots,\mathcal{A}_{\ell(\Psi)})$ over the same signature
together with a set of designated elements $X$ (the free variables) that are
in the universe of each of the structures. For each $J\subseteq[\ell(\Psi)]$,
we define $\Psi|_{J}=((A_{j})_{j\in J},X)$. If we restrict to a single term of
the union then we usually just write $\Psi_{i}$ instead of $\Psi|_{\\{i\\}}$.
Note that $\Psi_{i}=(\mathcal{A}_{i},X)$ is simply a conjunctive query (rather
than a union of CQs).

We will assume (without loss of generality) that, for any distinct $i$ and
$i^{\prime}$ in $[\ell(\Psi)]$, $U(\mathcal{A}_{i})\cap
U(\mathcal{A}_{i^{\prime}})=X$, i.e., that each CQ in the union has its own
set of existentially quantified variables.

If each such conjunctive query is acyclic we say that $\Psi$ is a union of
acyclic conjunctive queries. Moreover, the arity of $\Psi$ is the maximum
arity of any of the $\mathcal{A}_{i}$. The size of $\Psi$ is
$|\Psi|=\sum_{i=1}^{\ell(\Psi)}|\Psi_{i}|$. The elements of $X$ are the _free
variables_ of $\Psi$ and $\ell(\Psi)$ is the number of CQs in the union.

The set of _answers_ of $\Psi$ in a database $\mathcal{D}$, denoted by
$\mathsf{Ans}(\Psi\to\mathcal{D})$ is defined as follows:

$\mathsf{Ans}(\Psi\to\mathcal{D})=\left\\{a:X\to U(\mathcal{D})\mid\exists
i\in[\ell]:a\in\mathsf{Ans}(\Psi_{i}\to\mathcal{D})\right\\}.$

Again, we use the lower case version $\mathsf{ans}(\Psi\to\mathcal{D})$ to
denote the _number_ of answers of $\Psi$ in $\mathcal{D}$.

In the definition of UCQs we assume that every CQ in the union has the same
set of free variables, namely $X$. This assumption is without loss of
generality. To see this, suppose that we have a union of CQs
$(\mathcal{A}_{1},X_{1}),\dots,(\mathcal{A}_{\ell},X_{\ell})$ with individual
sets of free variables. Let $X=\bigcup_{i=1}^{\ell}X_{i}$ and, for each
$i\in[\ell]$, let $\mathcal{A}^{\prime}_{i}$ be the structure obtained from
$\mathcal{A}_{i}$ by adding an isolated variable for each $x\in X\setminus
X_{i}$. Then consider the UCQ
$\Psi:=((\mathcal{A}^{\prime}_{1},\ldots,\mathcal{A}^{\prime}_{\ell}),X)$. If
for some assignment $a:X\to U(\mathcal{D})$ it holds that there is an
$i\in[\ell]$ such that
$a|_{X_{i}}\in\mathsf{Ans}((\mathcal{A}_{i},X_{i})\to\mathcal{D})$. Then,
according to Observation 22, this is equivalent to
$a\in\mathsf{Ans}((\mathcal{A}^{\prime}_{i},X)\to\mathcal{D})$, which means
that $a$ is an answer of $\Psi$. So, without loss of generality we can work
with $\Psi$, which uses the same set of free variables for each CQ in the
union.

Now we define the parameterised problem of counting answers to UCQs. As usual,
the problem is restricted by a class $C$ of allowed queries with respect to
which we classify the complexity.

Name:

$\\#\textsc{UCQ}(C)$

Input:

A UCQ $\Psi\in C$ together with a database $\mathcal{D}$.

Parameter:

$|\Psi|$.

Output:

The number of answers $\mathsf{ans}(\Psi\to\mathcal{D})$.

The next definition will be crucial for the analysis of the complexity of
$\\#\textsc{UCQ}(C)$.

######  Definition 23 (combined query $\boldsymbol{\wedge}\left(\Psi\right)$).

Let $\Psi=((\mathcal{A}_{1},,\dots,\mathcal{A}_{\ell}),X)$ be a UCQ. Then we
define the _combined query_
$\boldsymbol{\wedge}\left(\Psi\right)=(\bigcup_{j\in[\ell]}A_{j},X)$.

What follows is an easy, but crucial observation about
$\boldsymbol{\wedge}\left(\Psi|_{J}\right)$.

######  Observation 24.

Let $((\mathcal{A}_{1},,\dots,\mathcal{A}_{\ell}),X)$ be a UCQ, and let
$\emptyset\neq J\subseteq[\ell]$. For each database $\mathcal{D}$ and
assignment $a:X\to U(\mathcal{D})$ we have

$a\in\mathsf{Ans}(\boldsymbol{\wedge}\left(\Psi|_{J}\right)\to\mathcal{D})\Leftrightarrow\forall
j\in J:a\in\mathsf{Ans}(\Psi_{j}\to\mathcal{D}).$

######  Definition 25 (Coefficient function $c_{\Psi}$).

Let $\Psi=((\mathcal{A}_{1},,\dots,\mathcal{A}_{\ell}),X)$ be a UCQ. For each
conjunctive query $(\mathcal{A},X)$, we set
$\mathcal{I}(\mathcal{A},X)=\\{J\subseteq[\ell]\mid(\mathcal{A},X)\sim\boldsymbol{\wedge}\left(\Psi|_{J}\right)\\}$,
and we define the _coefficient function_ of $\Psi$ as follows:

$c_{\Psi}(\mathcal{A},X)=\sum_{J\in\mathcal{I}(\mathcal{A},X)}(-1)^{|J|+1}\,.$

Using inclusion-exclusion, we can transform the problem of counting answers to
$\Psi$ into the problem of evaluating a linear combination of CQ answer
counts. We include a proof only for reasons of self-containment and note that
the complexity-theoretic applications of this transformation, especially
regarding lower bounds, have first been discovered by Chen and Mengel [20].

######  Lemma 26 ([20]).

Let $\Psi=((\mathcal{A}_{1},,\dots,\mathcal{A}_{\ell}),X)$ be a UCQ. For every
database $\mathcal{D}$,

$\mathsf{ans}(\Psi\to\mathcal{D})=\sum_{(\mathcal{A},X)}c_{\Psi}(\mathcal{A},X)\cdot\mathsf{ans}((\mathcal{A},X)\to\mathcal{D}),$

where the sum is over all equivalence classes of $\sim$.

###### Proof.

By inclusion-exclusion and Observation 24,

$\displaystyle\mathsf{ans}(\Psi\to\mathcal{D})$
$\displaystyle=\sum_{\emptyset\neq
J\subseteq[\ell]}(-1)^{|J|+1}\cdot\left|\\{a:X\to U(\mathcal{D})\mid\forall
j\in J:a\in\mathsf{Ans}((A_{j},X)\to\mathcal{D})\\}\right|$
$\displaystyle=\sum_{\emptyset\neq
J\subseteq[\ell]}(-1)^{|J|+1}\cdot\mathsf{ans}(\boldsymbol{\wedge}\left(\Psi|_{J}\right)\to\mathcal{D}).$

The claim then follows by collecting $\\#\text{equivalent}$ terms. ∎

We conclude this subsection with the following two operations on classes of
UCQs.

######  Definition 27 ($\Gamma(C)$ and $\boldsymbol{\wedge}\left(C\right)$).

Let $C$ be a class of UCQs. We define the following classes of conjunctive
queries:

  1. 1.

$\Gamma(C)=\\{(\mathcal{A},X)\mid(\mathcal{A},X)\text{ is $\\#\text{minimal}$
and there is }\Psi\in C\text{ with }c_{\Psi}(\mathcal{A},X)\neq 0\\}$

  2. 2.

$\boldsymbol{\wedge}\left(C\right)=\\{\boldsymbol{\wedge}\left(\Psi\right)\leavevmode\nobreak\
|\leavevmode\nobreak\ \Psi\in C\\}$

In other words, $\Gamma(C)$ contains all $\\#\text{minimal}$ classes that
appear with a non-zero coefficient in the CQ expansion of $\Psi$, and
$\boldsymbol{\wedge}\left(C\right)$ contains all conjunctive queries that can
be obtained by substituting each $\vee$ by an $\wedge$ in some UCQ in $C$.

###  2.4 Complexity Monotonicity

The principle of Complexity Monotonicity states that the computation of a
linear combination of homomorphism counts is precisely as hard as computing
its hardest term. It was independently discovered by Curticapean, Dell and
Marx [24] and by Chen and Mengel [20]. Moreover, Chen and Mengel established
the principle in the more general context of linear combinations of
conjunctive queries. Formally, their result is stated below for the special
case of linear combinations derived via counting answers to UCQs (see Lemma
26). We include a proof since we need to pay some special attention to running
times, as we will also be interested in the question of linear time
tractability.

######  Theorem 28 (Implicitly by [20]).

There is an algorithm $\mathbb{A}$ with the following properties:

  1. 1.

The input of $\mathbb{A}$ is a UCQ $\Psi$ and a database $\mathcal{D}$.

  2. 2.

$\mathbb{A}$ has oracle access to the function
$\mathcal{D}^{\prime}\mapsto\mathsf{ans}(\Psi\to\mathcal{D}^{\prime})$.

  3. 3.

The output of $\mathbb{A}$ is a list with entries
$((\mathcal{A},X),\mathsf{ans}((\mathcal{A},X)\to\mathcal{D}))$ for each
$(\mathcal{A},X)$ in the support of $c_{\Psi}$.

  4. 4.

$\mathbb{A}$ runs in time $f(|\Psi|)\cdot O(|\mathcal{D}|)$ for some
computable function $f$.

###### Proof.

A crucial operation in the construction is the Tensor product of relational
structures. Let $\mathcal{A}$ and $\mathcal{B}$ be structures over the
signatures $\tau_{A}$ and $\tau_{B}$. The structure
$\mathcal{A}\otimes\mathcal{B}$ is defined as follows: The signature is
$\tau_{A}\cap\tau_{B}$, and the universe is $U(\mathcal{A})\times
U(\mathcal{B})$. Moreover, for every relation symbol
$R\in\tau_{A}\cap\tau_{B}$ with arity $r$, a tuple
$((u_{1},v_{1}),\dots,(u_{r},v_{r}))$ is contained in
$R^{\mathcal{A}\otimes\mathcal{B}}$ if and only if $(u_{1},\dots,u_{r})\in
R^{\mathcal{A}}$ and $(v_{1},\dots,v_{r})\in R^{\mathcal{B}}$.

Observe that $\mathcal{A}\otimes\mathcal{B}$ is of size bounded by and can be
computed in time $O(|\mathcal{A}||\mathcal{B}|)$.777Compute the Cartesian
product of $U(\mathcal{A})$ and $U(\mathcal{B})$ and then, for every relation
$R\in\tau_{A}\cap\tau_{B}$ iterate over all pairs of tuples in
$R^{\mathcal{A}}$ and $R^{\mathcal{B}}$ and add their point-wise product to
$R^{\mathcal{A}\otimes\mathcal{B}}$. The algorithm $\mathbb{A}$ proceeds as
follows. Let $\Psi=((\mathcal{A}_{1},\dots,\mathcal{A}_{\ell}),X)$ be the
input. For a selected set of structures
$\mathcal{B}_{1}\dots,\mathcal{B}_{k}$, specified momentarily, the algorithm
queries the oracle on the Tensor products $\mathcal{D}\otimes\mathcal{B}_{i}$.
Using Lemma 26, this yields the following equations:

$\mathsf{ans}(\Psi\to\mathcal{D}\otimes\mathcal{B}_{i})=\sum_{(\mathcal{A},X)}c_{\Psi}(\mathcal{A},X)\cdot\mathsf{ans}((\mathcal{A},X)\to\mathcal{D}\otimes\mathcal{B}_{i}).$

Next, we use the fact (see e.g. [20]) that the Tensor product is
multiplicative with respect to counting answers to conjunctive queries:

$\mathsf{ans}((\mathcal{A},X)\to\mathcal{D}\otimes\mathcal{B}_{i})=\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})\cdot\mathsf{ans}((\mathcal{A},X)\to\mathcal{B}_{i}).$

In combination, the previous equations yield a system of linear equations:

$\mathsf{ans}(\Psi\to\mathcal{D}\otimes\mathcal{B}_{i})=\sum_{(\mathcal{A},X)}c_{\Psi}(\mathcal{A},X)\cdot\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})\cdot\mathsf{ans}((\mathcal{A},X)\to\mathcal{B}_{i}),$

the unknowns of which are
$c_{\Psi}(\mathcal{A},X)\cdot\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})$.
Finally, it was shown in [20] and [28] that it is always possible to find
$\mathcal{B}_{i}$ for which the system is non-singular. Moreover, the time it
takes to find the $\mathcal{B}_{i}$ only depends on $\Psi$. Finally, solving
the system yields the terms
$c_{\Psi}(\mathcal{A},X)\cdot\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})$ from
which we can recover $\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})$ by dividing
by $c_{\Psi}(\mathcal{A},X)$. It can easily be observed that the overall
running time is bounded by $f(|\Psi|)\cdot O(|\mathcal{D}|)$ for some
computable function $f$, as required, which concludes the proof. ∎

######  Corollary 29.

Let $\Psi$ be a UCQ. For each $d\geq 1$, computing the function
$\mathcal{D}\mapsto\mathsf{ans}(\Psi\to\mathcal{D})$ can be done in time
$O(\left|\mathcal{D}\right|^{d})$ if and only if for each $\\#\text{minimal}$
$(\mathcal{A},X)$ with $c_{\Psi}(\mathcal{A},X)\neq 0$ the function
$\mathcal{D}\mapsto\mathsf{ans}((\mathcal{A},X)\to\mathcal{D})$ can be
computed in time $O(\left|\mathcal{D}\right|^{d})$.

######  Corollary 30 (Implicitly also in [20]).

Let $C$ be a recursively enumerable class of UCQs. The problems
$\\#\textsc{UCQ}(C)$ and $\\#\textsc{CQ}(\Gamma(C))$ are interreducible with
respect to parameterised Turing-reductions.

As a consequence, in combination with Theorem 21, Chen and Mengel [20]
established the following dichotomy, which we can state in a convenient way
using our notation: See 1

In other words, as a summary of the above results, we know that counting
answers to a UCQ is hard if and only if a conjunctive query survives in the CQ
expansion, whose $\\#\text{core}$ has either high treewidth or its contract
has high treewidth. Unfortunately, given a concrete UCQ, or a concrete class
of UCQs, it is not clear how to determine whether such high treewidth terms
survive.

The central question that we ask in this work is whether this implicit
tractability criterion for counting answers to UCQs can be rephrased as a more
natural one. Equivalently, this means that we aim to find out whether there is
a natural criterion for the existence of high treewidth terms in the CQ
expansion. Such natural criteria have been found for subgraph and induced
subgraph counting888(Induced) Subgraph counting is a special case of counting
answers to quantifier-free conjunctive queries with inequalities (and
negations). [24, 33], and for conjunctive queries with inequalities and
negations [28, 55].

##  3 Classifications for Deletion-Closed UCQs

Let $C$ be a class of UCQs. Recall that $\boldsymbol{\wedge}\left(C\right)$ is
the class of all conjunctive queries that are obtained just by substituting
all $\vee$ by $\wedge$ in UCQs in $C$, whereas $\Gamma(C)$ in Theorem 1 is the
much less natural class of $\\#\text{minimal}$ queries that survive with a
non-zero coefficient in the CQ expansion of a UCQ in $C$. The work of Chen and
Mengel [20] implicitly also shows an upper bound for counting answers to UCQs
from the class $C$ in terms of the simpler objects
$\boldsymbol{\wedge}\left(C\right)$ and
$\mathsf{contract}(\boldsymbol{\wedge}\left(C\right))$, rather than in terms
of the more complicated objects $\Gamma(C)$ and
$\mathsf{contract}(\Gamma(C))$. We include a proof for completeness.

######  Lemma 31.

Let $C$ be recursively enumerable class of UCQs. Suppose that both
$\boldsymbol{\wedge}\left(C\right)$ and
$\mathsf{contract}(\boldsymbol{\wedge}\left(C\right))$ have bounded treewidth.
Then $\\#\textsc{UCQ}(C)$ is fixed-parameter tractable.

###### Proof.

Let $\Psi\in C$. Recall from the proof of Lemma 26 that, for every databse
$\mathcal{D}$,

$\displaystyle\mathsf{ans}(\Psi\to\mathcal{D})=\sum_{\emptyset\neq
J\subseteq[\ell]}(-1)^{|J|+1}\cdot\mathsf{hom}(\boldsymbol{\wedge}\left(\Psi|_{J}\right)\to\mathcal{D})\,.$

Hence $\\#\textsc{UCQ}(C)\leq^{\mathsf{FPT}}\\#\textsc{CQ}(\hat{C})$ where

$\hat{C}:=\\{\boldsymbol{\wedge}\left(\Psi|_{J}\right)\leavevmode\nobreak\
|\leavevmode\nobreak\ \Psi\in C\leavevmode\nobreak\ \wedge\leavevmode\nobreak\
\emptyset\neq J\subseteq[\ell(\Psi)]\\}\,.$

Finally, since $\boldsymbol{\wedge}\left(\Psi|_{J}\right)$ is a subquery of
$\boldsymbol{\wedge}\left(\Psi\right)$ for each $J$, the treewidths of
$\boldsymbol{\wedge}\left(\Psi|_{J}\right)$ and
$\mathsf{contract}(\boldsymbol{\wedge}\left(\Psi|_{J}\right))$ are bounded
from above by the treewidths of $\boldsymbol{\wedge}\left(\Psi\right)$ and
$\mathsf{contract}(\boldsymbol{\wedge}\left(\Psi\right))$, respectively.
Consequently, the treewidths of $\hat{C}$ and $\mathsf{contract}(\hat{C})$ are
bounded, and thus $\\#\textsc{CQ}(\hat{C})$ is polynomial-time solvable by the
classification of Chen and Mengel [19, Theorem 22] Since
$\\#\textsc{UCQ}(C)\leq^{\mathsf{FPT}}\\#\textsc{CQ}(\hat{C})$, the lemma
follows. ∎

Our goal is to relate the complexity of $\\#\textsc{UCQ}(C)$ to the structure
of $\boldsymbol{\wedge}\left(C\right)$ with the hope of obtaining a more
natural tractability criterion than the one given by Theorem 1. While we will
see later that this seems not always possible (Appendix A), we identify
conditions under which a natural criterion based on
$\boldsymbol{\wedge}\left(C\right)$ is possible, both in the quantifier-free
case (Section 3.1), and in the general case that allows quantified variables
(Section 3.2).

A class of UCQs $C$ is _closed under deletions_ if, for every
$\Psi=((\mathcal{A}_{1},\ldots,\mathcal{A}_{\ell}),X)\in C$ and for every
$\emptyset\neq J\subseteq[\ell]$, the UCQ $\Psi|_{J}$ is also contained in
$C$. For example, any class of UCQs defined by prescribing the allowed
conjunctive queries is closed under deletions. This includes, e.g., unions of
acyclic conjunctive queries.

###  3.1 The Quantifier-free Case

As a warm-up, we start with the much simpler case of quantifier-free queries.
Here, we only allow (unions of) conjunctive queries $(\mathcal{A},X)$
satisfying $U(\mathcal{A})=X$.

######  Lemma 32.

Let $C$ be a recursively enumerable class of quantifier-free UCQs of bounded
arity. Suppose that $C$ is closed under deletions. If
$\boldsymbol{\wedge}\left(C\right)$ has unbounded treewidth then
$\\#\textsc{UCQ}(C)$ is $\mathrm{W[1]}$-hard.

###### Proof.

We show that $\boldsymbol{\wedge}\left(C\right)\subseteq\Gamma(C)$, which then
proves the claim by Theorem 1. Recall from Definition 27 that
$\Gamma(C)=\\{(\mathcal{A},X)\mid(\mathcal{A},X)\text{ is $\\#\text{minimal}$
and there is }\Psi\in C\text{ with }c_{\Psi}(\mathcal{A},X)\neq 0\\}$. Let
$\Psi=((\mathcal{A}_{1},\ldots,\mathcal{A}_{\ell}),X)\in C$. Note that,
according to Observation 17, $\boldsymbol{\wedge}\left(\Psi\right)$ is its own
$\\#\text{core}$ since it does not have existentially quantified variables.
For the same reason, for each nonempty subset $J$ of $[\ell]$, the query
$\boldsymbol{\wedge}\left(\Psi|_{J}\right)$ is its own $\\#\text{core}$. Now
let $J\subseteq[\ell]$ be inclusion-minimal with the property that
$\boldsymbol{\wedge}\left(\Psi|_{J}\right)$ is isomorphic to
$\boldsymbol{\wedge}\left(\Psi\right)$. Since $C$ is closed under deletions,
the UCQ $\Psi|_{J}$ is contained in $C$. By the inclusion-minimality of $J$,
Definition 25 ensures that
$c_{\Psi|_{J}}(\boldsymbol{\wedge}\left(\Psi\right))=(-1)^{|J|+1}\neq 0$. As a
consequence, $\boldsymbol{\wedge}\left(\Psi\right)\in\Gamma(C)$, concluding
the proof. ∎

From Lemmas 32 and 31 together with the fact that the contract of a
quantifier-free query is the query itself, we obtain the classification for
quantifier-free UCQs, which we restate for convenience. See 2

###  3.2 The General Case

Now we consider UCQs with existentially quantified variables. Here, a
corresponding hardness result (Lemma 35) can be achieved under some additional
assumptions. Note that the number of existentially quantified variables in a
UCQ $\Psi=((\mathcal{A}_{1},\ldots,\mathcal{A}_{\ell}),X)$ is equal to
$\sum_{i=1}^{\ell}|U(\mathcal{A}_{i})\setminus X|$. We first need the
following two auxiliary results:

######  Lemma 33.

Let $(\mathcal{A},X)$ and $(\mathcal{A}^{\prime},X^{\prime})$ be
$\\#\text{equivalent}$ conjunctive queries. Further, let $G$ and $G^{\prime}$
be the Gaifman graphs of $\mathcal{A}$ and $\mathcal{A}^{\prime}$,
respectively. Then $G[X]$ and $G^{\prime}[X^{\prime}]$ are isomorphic.

###### Proof.

By [20] (see Lemma 48 in the full version of [28] for an explicit statement),
there are surjective functions $s:X\to X^{\prime}$ and
$s^{\prime}:X^{\prime}\to X$ and homomorphisms
$h\in\mathsf{Hom}(\mathcal{A}\to\mathcal{A}^{\prime})$ and
$h^{\prime}\in\mathsf{Hom}(\mathcal{A}^{\prime}\to\mathcal{A})$ such that
$h|_{X}=s$ and $h^{\prime}|_{X^{\prime}}=s^{\prime}$.

Clearly, $s$ and $s^{\prime}$ are bijective. Let $e=\\{u,v\\}$ be an edge of
$G[X]$. Then there exists a tuple $\vec{t}$ of elements of $U(\mathcal{A})$
such that

  * (i)

$\vec{t}\in R^{\mathcal{A}}$ for some relation (symbol) $R$ of the signature
of $\mathcal{A}$, and

  * (ii)

$u$ and $v$ are elements of $\vec{t}$.

Since $h$ is a homomorphism, $h(\vec{t})\in R^{\mathcal{B}}$. Thus
$\\{h(u),h(v)\\}=\\{s(u),s(v)\\}$ is an edge of $G^{\prime}[X^{\prime}]$. The
backward direction is analogous. ∎

######  Lemma 34.

Let $(\mathcal{A},X)$ be a self-join-free conjunctive query. Let
$\mathcal{A}^{\prime}$ be the structure obtained from $\mathcal{A}$ by
deleting all isolated variables in $U(\mathcal{A})\setminus X$. Then
$(\mathcal{A}^{\prime},X)$ is the $\\#\text{core}$ of $(\mathcal{A},X)$.

###### Proof.

Clearly, $(\mathcal{A},X)$ and $(\mathcal{A}^{\prime},X)$ are
$\\#\text{equivalent}$. Thus it remains to show that
$(\mathcal{A}^{\prime},X)$ is $\\#\text{minimal}$. Assume for contradiction by
Observation 17 that $(\mathcal{A}^{\prime},X)$ has an #equivalent substructure
$\hat{\mathcal{A}}$ that is induced by a set $U$ with $X\subseteq U\subset
U(\mathcal{A}^{\prime})$.

Since $\mathcal{A}^{\prime}$ is self-join-free and it does not have isolated
variables, there is a relation (symbol) $R$ such that
$R^{\mathcal{A}^{\prime}}$ contains precisely one tuple, and
$R^{\hat{\mathcal{A}}}$ is empty. Thus, there is no homomorphism from
$\mathcal{A}^{\prime}$ to $\hat{\mathcal{A}}$ and, consequently,
$(\hat{\mathcal{A}},X)$ and $(\mathcal{A}^{\prime},X)$ cannot be
$\\#\text{equivalent}$, yielding a contradiction and concluding the proof. ∎

######  Lemma 35.

Let $C$ be a recursively enumerable class of unions of self-join-free
conjunctive queries with bounded arity. Suppose that $C$ is closed under
deletions and that there is a finite upper bound on the number of
existentially quantified variables in queries in $C$. If either of
$\boldsymbol{\wedge}\left(C\right)$ or
$\mathsf{contract}(\boldsymbol{\wedge}\left(C\right))$ have unbounded
treewidth then $\\#\textsc{UCQ}(C)$ is $\mathrm{W[1]}$-hard.

###### Proof.

Let $d$ be the maximum number of existentially quantified variables in a query
in $C$. Assume first that $\boldsymbol{\wedge}\left(C\right)$ has unbounded
treewidth. We show that $\Gamma(C)$ has unbounded treewidth, which proves the
claim by Theorem 1. To this end, let $B$ be any positive integer. The goal is
to find a conjunctive query in $\Gamma(C)$ with treewidth at least $B$. Since
$\boldsymbol{\wedge}\left(C\right)$ has unbounded treewidth, there is a UCQ
$\Psi=((\mathcal{A}_{1},\ldots,\mathcal{A}_{\ell}),X)$ in $C$ such that
$\boldsymbol{\wedge}\left(\Psi\right)$ has treewidth larger than $d+B$. Note
that, although all $\Psi_{i}$ are self-join-free,
$\boldsymbol{\wedge}\left(\Psi\right)$ is not necessarily self-join-free. Let
$J$ be inclusion-minimal among the subsets of $[\ell]$ with the property that
the $\\#\text{core}$ of $\boldsymbol{\wedge}\left(\Psi|_{J}\right)$ is
isomorphic to the $\\#\text{core}$ of $\boldsymbol{\wedge}\left(\Psi\right)$.
Since $C$ is closed under deletions, the UCQ $\Psi|_{J}$ is contained in $C$.
Let $(\mathcal{A}^{\prime},X^{\prime})$ be the $\\#\text{core}$ of
$\boldsymbol{\wedge}\left(\Psi\right)$.

By inclusion-minimality of $J$,
$c_{\Psi|_{J}}((\mathcal{A}^{\prime},X^{\prime}))=(-1)^{|J|+1}\neq 0$. As a
consequence, $(\mathcal{A}^{\prime},X^{\prime})\in\Gamma(C)$. It remains to
show that the treewidth of $(\mathcal{A}^{\prime},X^{\prime})$ is at least
$B$. To this end, let $G$ be the Gaifmann graph of
$\boldsymbol{\wedge}\left(\Psi\right)$ and let $G^{\prime}$ be the Gaifmann
graph of the $\\#\text{core}$ of $\boldsymbol{\wedge}\left(\Psi\right)$ (the
Gaifman graph of $\mathcal{A}^{\prime}$). First, deletion of a vertex can
decrease the treewidth by at most $1$. Thus, $G[X]$ has treewidth at least
$d+B-d=B$. Finally, by Lemma 33, $G[X]$ and $G^{\prime}[X^{\prime}]$ are
isomorphic.

Therefore the treewidth of $G^{\prime}[X^{\prime}]$, i.e., the treewidth of
$(\mathcal{A}^{\prime},X^{\prime})$, is at least $B$. So we have shown that if
the treewidth of $\boldsymbol{\wedge}\left(C\right)$ is unbounded then so is
the treewidth of $\Gamma(C)$.

In the second case, we assume that the contracts of queries in
$\boldsymbol{\wedge}\left(C\right)$ (see Definition 20) have unbounded
treewidth. We introduce the following terminology: Let $(\mathcal{A},X)$ be a
conjunctive query and let $y\in U(\mathcal{A})$. The _degree of freedom_ of
$y$ is the number of vertices in $X$ that are adjacent to $y$ in the Gaifman
graph of $\mathcal{A}$. Let $\hat{C}$ be the class of all conjunctive queries
$(\mathcal{A},X)$ such that there exists
$\Psi=((\mathcal{A}_{1},\ldots,\mathcal{A}_{\ell(\Psi)}),X)$ in $C$ with
$(\mathcal{A},X)=(\mathcal{A}_{i},X)$ for some $i\in[\ell(\Psi)]$. Since $C$
is closed under deletions, $\hat{C}\subseteq C$. By the assumptions of the
lemma, $\hat{C}$ consists only of self-join-free queries. Thus, by Lemma 34,
each query in $\hat{C}$ is its own $\\#\text{core}$ (up to deleting isolated
variables). We will now consider the following cases:

  1. (i)

Suppose that $\hat{C}$ has unbounded degree of freedom. With Definition 20 it
is straightforward to check that a quantified variable $y$ with degree of
freedom $B$ induces a clique of size $B$ in the contract of the corresponding
query. Therefore, the contracts of the queries in $\hat{C}$ have unbounded
treewidth. Consequently, $\\#\textsc{CQ}(\hat{C})$ is $\mathrm{W[1]}$-hard by
the classification of Chen and Mengel [19, Theorem 22]. Since
$\hat{C}\subseteq C$ the problem $\\#\textsc{CQ}(\hat{C})$ is merely a
restriction of $\\#\textsc{UCQ}(C)$, the latter of which is thus
$\mathrm{W[1]}$-hard as well.

  2. (ii)

Suppose that the degree of freedom of queries in $\hat{C}$ is bounded by a
constant $d^{\prime}$. We show that $\Gamma(C)$ has unbounded treewidth, which
proves the claim by Theorem 1. To this end, let $B$ be any positive integer.
The goal is to find a conjunctive query in $\Gamma(C)$ with treewidth at least
$B$. Since $\mathsf{contract}(\boldsymbol{\wedge}\left(C\right))$ has
unbounded treewidth, there is a UCQ
$\Psi=(\mathcal{A}_{1},\ldots,\mathcal{A}_{\ell}),X)$ in $C$ such that
$\mathsf{contract}(\boldsymbol{\wedge}\left(\Psi\right))$ has treewidth larger
than $d+\binom{dd^{\prime}}{2}+B$. We will show that
$\boldsymbol{\wedge}\left(\Psi\right)$ has treewidth larger than $d+B$, which,
as we have argued previously, implies that $\Gamma(C)$ contains a query with
treewidth at least $B$. To prove that $\boldsymbol{\wedge}\left(\Psi\right)$
indeed has treewidth larger than $d+B$, let
$\boldsymbol{\wedge}\left(\Psi\right)=(\mathcal{A},X)$ and let $G$ be the
Gaifman graph of $\mathcal{A}$. Let $Y=U(\mathcal{A})\setminus X$ and recall
from Definition 20 that $\mathsf{contract}(\mathcal{A},X)$ is obtained from
$G[X]$ by adding an edge between any pair of vertices $u$ and $v$ that are
adjacent to a common connected component in $G[Y]$. Let $N\subseteq X$ be the
set of all vertices in $X$ that are adjacent to a vertex in $Y$ and observe
that $|N|\leq dd^{\prime}$ since the number of existentially quantified
variables and the degree of freedom are bounded by $d$ and $d^{\prime}$,
respectively. Thus, $\mathsf{contract}(\mathcal{A},X)$ is obtained by adding
at most $\binom{dd^{\prime}}{2}$ edges to $G[X]$. The deletion of an edge can
decrease the treewidth by at most $1$, so

$\mathsf{tw}(\boldsymbol{\wedge}\left(\Psi\right))=\mathsf{tw}(G)\geq\mathsf{tw}(G[X])\geq\mathsf{tw}(\mathsf{contract}(\mathcal{A},X))-\binom{dd^{\prime}}{2}>d+B\,,$

which concludes Case (ii).

With all cases concluded, the proof is completed. ∎

From Lemmas 31 and 35 we directly obtain the main result of this section,
which we restate for convenience. See 3

######  Remark 36.

It turns out that all side conditions of Theorem 3 are necessary if we aim to
classify $\\#\textsc{UCQ}(C)$ solely via $\boldsymbol{\wedge}\left(C\right)$.
To this end, we provide counter examples for each missing condition in
Appendix A.

##  4 The Meta Complexity of Counting Answers to UCQs

We consider the meta-complexity question of deciding whether it is possible to
count the answers of a given UCQ in linear time. As pointed out in the
introduction, this problem is immediately $\mathrm{NP}$-hard even when
restricted to conjunctive queries if we were to allow quantified variables.
Therefore, we consider quantifier-free UCQs in this section. Recall the
definition of Meta from Section 1.

Name:

Meta

Input:

A union $\Psi$ of quantifier-free conjunctive queries.

Output:

Is it possible to count answers to $\Psi$ in time linear in the size of
$\mathcal{D}$, i.e., can the function
$\mathcal{D}\mapsto\mathsf{ans}(\Psi\to\mathcal{D})$ be computed in time
$O(|\mathcal{D}|)$.

Since we focus in this section solely on quantifier-free queries, it will be
convenient to simplify our notation as follows. As all variables are free, we
will identify a conjunctive query $\varphi$ just by its associated structure,
that is, we will write $\varphi=\mathcal{A}$, rather than
$\varphi=(\mathcal{A},U(\mathcal{A}))$. Similarly, we represent a union of
quantifier-free conjunctive queries $\Psi$ as a tuple of structures
$\Psi=(\mathcal{A}_{1},\dots,\mathcal{A}_{\ell})$.

For studying the complexity of Meta, it will be crucial to revisit the
classification of linear-time counting of answers to quantifier-free
conjunctive queries: The following theorem is well known and was discovered
multiple times by different authors in different contexts.999We remark that
[9, Theorem 7] focuses on the special case of graphs and _near_ linear time
algorithms. However, in the word RAM model with $O(\log n)$ bits, a linear
time algorithm is possible [17]. This is Theorem 4 from the introduction,
which we now restate in a version that expresses CQs as structures.

######  Theorem 37 ([17, 50, 9]).

Let $\mathcal{A}$ be a quantifier-free conjunctive query and suppose that at
least one of the Triangle Conjecture and SETH is true. Then the function
$\mathcal{D}\mapsto\mathsf{hom}(\mathcal{A}\to\mathcal{D})$ is computable in
linear time if and only if $\mathcal{A}$ is acyclic.

Theorem 37 yields an efficient way to check whether counting answers to a
quantifier-free conjunctive query $\varphi$ can be done in linear time: Just
check whether $\varphi$ is acyclic. In stark contrast, we show that no easy
criterion for linear time tractability of counting answers to _unions_ of
conjunctive queries is possible, unless some conjectures of fine-grained
complexity theory fail. In fact, our Theorem 5, which we restate here for
convenience, precisely determines the complexity of Meta.

See 5

The lower bounds in Theorem 5 imply that no significant improvement over our
single-exponential $|\Psi|^{O(1)}\cdot O(2^{\ell})$ time algorithm for Meta is
possible, unless standard assumptions fail.

The remainder of this section is devoted to the proof of Theorem 5. It is
split into two parts: In the first and easier part (Section 4.1), we construct
the algorithm for Meta. For this, all we need to do is to translate the
problem into the homomorphism basis (see Section 2.3), i.e., we transform the
problem of counting answers to $\Psi$ into the problem of evaluating a linear
combination of terms, each of which can be determined by counting the answers
to a conjunctive query. This is done in Lemma 38. The second part (Section
4.2) concerns the lower bounds and is more challenging. The overall strategy
is as follows: In the first step, we use a parsimonious reduction from $3$-SAT
to computing the reduced Euler Characteristic of a complex. The parsimonious
reduction is due to Roune and Sáenz-de-Cabezón [57]. In combination with the
Sparsification Lemma [42], this reduction becomes tight enough for our
purposes. In the second step, we show how to encode a complex $\Delta$ into a
union of acyclic conjunctive queries $\Psi$ such that the following is true:
The reduced Euler Characteristic of $\Delta$ is zero if and only if all terms
in the homomorphism basis are acyclic. The lower bound results of Theorem 5
are established in Lemmas 51, 52, and 53.

###  4.1 Solving Meta via Inclusion-Exclusion

######  Lemma 38.

The problem Meta can be solved in time $|\Psi|^{O(1)}\cdot O(2^{\ell})$, where
$\ell$ is the number of conjunctive queries in the union, if at least one of
the SETH and the Triangle Conjecture is true.

###### Proof.

If the SETH or the Triangle Conjecture is true, then Theorem 37 implies that
counting answers to a quantifier-free conjunctive query is solvable in linear
time if and only if the query is acyclic. In combination with Corollary 29 we
obtain that counting answers to a UCQ
$\Psi=(\mathcal{A}_{1},\dots,\mathcal{A}_{\ell})$ can be done in linear time
if and only if each $\mathcal{A}$ with $c_{\Psi}(\mathcal{A})\neq 0$ is
acyclic.

Recall that #equivalence is the same as isomorphism for quantifier-free
queries (Definition 16). By Definition 25,

$c_{\Psi}(\mathcal{A})=\sum_{\begin{subarray}{c}J\subseteq[\ell]\\\
\boldsymbol{\wedge}\left(\Psi|_{J}\right)\cong\mathcal{A}\end{subarray}}(-1)^{|J|+1}.$

This suggests the following algorithm for Meta with input $\Psi$. For each
subset $J\subseteq[\ell]$, compute
$\boldsymbol{\wedge}\left(\Psi|_{J}\right)$. Afterwards, collect the
isomorphic terms and compute
$c_{\Psi}(\boldsymbol{\wedge}\left(\Psi|_{J}\right))$ for each
$J\subseteq[\ell]$. Clearly, $c_{\Psi}(\mathcal{A})=0$ for every $\mathcal{A}$
that is not isomorphic to any $\boldsymbol{\wedge}\left(\Psi|_{J}\right)$.

Finally, output $1$ if each $\mathcal{A}$ with $c_{\Psi}(\mathcal{A})\neq 0$
is acyclic (each of these checks can be done in linear time [58]), and output
$0$ otherwise. The total running time of this algorithm is bounded from above
by $|\Psi|^{O(1)}\cdot O(2^{\ell})$. ∎

###  4.2 Fine-grained Lower bounds for Meta

For our hardness proof for Meta, we will construct a reduction from the
computation of the reduced Euler characteristic of an abstract simplicial
complex. We begin by introducing some central notions about (abstract)
simplicial complexes.

####  4.2.1 Simplicial Complexes

A simplicial complex captures the geometric notion of an independence system.
We will use the corresponding combinatorial description, which is also known
as _abstract simplicial complex_ , and defined as follows.

######  Definition 39.

A _complex_ (short for abstract simplicial complex) $\Delta$ is a pair
consisting of a nonempty finite ground set $\Omega$ and a set of _faces_
$\mathcal{I}\subseteq 2^{\Omega}$ that includes all singletons and is a
downset. That is, the set of faces $\mathcal{I}$ satisfies the following
criteria.

  * •

$\forall S\subseteq\Omega:S\in\mathcal{I}\Rightarrow\forall
S^{\prime}\subseteq S:S^{\prime}\in\mathcal{I}$, and

  * •

$\forall x\in\Omega:\\{x\\}\in\mathcal{I}$.

The inclusion-maximal faces in $\mathcal{I}$ are called _facets_. Unless
stated otherwise, we encode complexes by the ground set $\Omega$ and the set
of facets. Then $|\Delta|$ is its encoding length.

######  Definition 40.

The _reduced Euler characteristic_ of a complex $\Delta=(\Omega,\mathcal{I})$
is defined as

$\hat{\chi}(\Delta):=-\sum_{S\in\mathcal{I}}(-1)^{|S|}\,.$

Consider for example the complexes $\Delta_{1}$ and $\Delta_{2}$ in Figure 1,
given with a computation of their reduced Euler characteristic.

Figure 1: Two complexes over the groundset $\Omega=\\{1,2,3,4\\}$. Let
$\Delta_{1}$ be the complex shown on the left. It has facets $\\{2,3,4\\}$,
$\\{1,2\\}$, $\\{1,3\\}$, and $\\{1,4\\}$. Let $\Delta_{2}$ be the complex
shown on the right, with facets $\\{1,2\\}$, $\\{2,3\\}$, $\\{1,3\\}$, and
$\\{4\\}$. The reduced Euler characteristic of these complexes is computed as
follows: Since $\Delta_{1}$ has one face of size $3$ ($\\{2,3,4\\}$), $6$
faces of size $2$, $4$ faces of size $1$, and the empty set as face of size
$0$ it holds that $\hat{\chi}(\Delta_{1})=-(-1+6-4+1)=-2$. Similarly, we have
$\hat{\chi}(\Delta_{2})=-(3-4+1)=0$.

Let $\Delta=(\Omega,\mathcal{I})$ be a complex. Consider distinct elements $x$
and $y$ in $\Omega$. We say that $x$ _dominates_ $y$ if, for every
$S\in\mathcal{I}$, $y\in S$ implies $S\cup\\{x\\}\in\mathcal{I}$. For example,
$x$ and $y$ dominate each other if they are contained in the same facets. We
start with a simple observation:

######  Lemma 41.

Let $\Delta=(\Omega,\mathcal{I})$ be a complex and let $x,y\in\Omega$. Then
$x$ dominates $y$ if and only if each facet that contains $y$ must also
contain $x$.

###### Proof.

For the forward direction suppose $x$ dominates $y$. Let $F$ be a facet that
contains $y$. Then $F\cup\\{x\\}\in\mathcal{I}$. Since facets are inclusion
maximal in $\mathcal{I}$ it follows that $F=F\cup\\{x\\}$, that is, $x\in F$.

For the backward direction suppose that each facet containing $y$ must also
contain $x$. Let $S\in\mathcal{I}$ with $y\in S$. Then there is a facet $F$
with $S\subseteq F$. Since $x\in F$ we have $S\cup\\{x\\}\subseteq F$ and
hence $S\cup\\{x\\}\in\mathcal{I}$. Therefore $x$ dominates $y$. ∎

We say that a complex $\Delta=(\Omega,\mathcal{I})$ is _irreducible_ if, for
every $y\in\Omega$, there is no $x\in\Omega\setminus\\{y\\}$ that dominates
$y$.

Given $\Delta=(\Omega,\mathcal{I})$ and $y\in\Omega$, we define
$\Delta\setminus y$ to be the complex obtained from $\Delta$ by deleting all
faces that contain $y$ and by deleting $y$ from $\Omega$. The following lemma
seems to be folklore. We include a proof only for reasons of self-containment.

######  Lemma 42.

Let $\Delta=(\Omega,\mathcal{I})$ be a complex. If $y\in\Omega$ is dominated
by some $x\in\Omega\setminus\\{y\\}$ then
$\hat{\chi}(\Delta)=\hat{\chi}(\Delta\setminus y)$.

###### Proof.

Let $\Delta=(\Omega,\mathcal{I})$. Write $\mathcal{I}_{y}$ for the set of all
faces containing $y$. Consider the mapping
$b:\mathcal{I}_{y}\to\mathcal{I}_{y}$

$b(S):=\begin{cases}S\cup\\{x\\}&x\notin S\\\ S\setminus\\{x\\}&x\in
S\,.\end{cases}$

Note that $b$ is well-defined since $S\cup\\{x\\}\in\mathcal{I}_{y}$ because
$y\in S$ and $x$ dominates $y$. Observe that $b$ induces a partition of
$\mathcal{I}_{y}$ in pairs $\\{S,S\cup\\{x\\}\\}$ for $x\notin S$. For those
pairs, we clearly have $|S|+1=|S\cup\\{x\\}|$. Thus

$\sum_{S\in\mathcal{I}_{y}}(-1)^{|S|}=0\,,$

and therefore

$\hat{\chi}(\Delta)=-\sum_{S\in\mathcal{I}}(-1)^{|S|}=-\sum_{S\in\mathcal{I}\setminus\mathcal{I}_{y}}(-1)^{|S|}=\hat{\chi}(\Delta\setminus
y)\,.$

∎

######  Definition 43.

Two complexes $\Delta_{1}=(\Omega_{1},\mathcal{I}_{1})$ and
$\Delta_{2}=(\Omega_{2},\mathcal{I}_{2})$ are _isomorphic_ if there is a
bijection $b:\Omega_{1}\to\Omega_{2}$ such that $S\in\mathcal{I}_{1}$ if and
only if $b(S)\in\mathcal{I}_{2}$ for each $S\subseteq\Omega$, where
$b(S)=\\{b(x)\mid x\in S\\}$.

Finally, a complex $(\Omega,\mathcal{I})$ is called _trivial_ if it is
isomorphic to $(\\{x\\},\\{\emptyset,\\{x\\}\\})$.

####  4.2.2 The Main Reduction

To begin with, we require a conjunctive query whose answers cannot be counted
in linear time under standard assumptions. To this end, we define, for
positive integers $k$ and $t$, a binary relational structure
$\mathcal{K}_{t}^{k}$ as follows. Start with a $t$-clique $K_{t}$ and
$k$-stretch every edge, that is, each edge of $K_{t}$ is replaced by a path
consisting of $k$ edges. We denote the resulting graph by $K_{t}^{k}$. For
each edge $e$ of $K_{t}^{k}$, we introduce a relation $R_{e}=\\{e\\}$ of arity
$2$. The structure $\mathcal{K}_{t}^{k}$ has universe $V(K_{t}^{k})$ and
relations $(R_{e})_{e\in E(K_{t}^{k})}$.

######  Observation 44.

Let $k$ and $t$ be positive integers. The structure $\mathcal{K}_{t}^{k}$ is
self-join-free and has arity $2$.

######  Lemma 45.

Suppose that the non-uniform ETH holds. For all positive integers $d$, there
is a $t$ such that for each $k$, the function
$\mathcal{D}\mapsto\mathsf{hom}(\mathcal{K}_{t}^{k}\to\mathcal{D})$ cannot be
computed in time $O(\left|\mathcal{D}\right|^{d})$.

###### Proof.

We again write $K_{t}$ for the $t$-clique and $K_{t}^{k}$ for the $k$-stretch
of $K_{t}$. Chen, Eickmeyer and Flum [23] proved that, under non-uniform ETH,
for each positive integer $d$, there is a $t$ such that determining whether a
graph $G$ contains $K_{t}$ as a subgraph cannot be done in time $O(|G|^{d})$.

We construct a simple linear-time reduction to computing
$\mathcal{D}\mapsto\mathsf{hom}(\mathcal{K}_{t}^{k}\to\mathcal{D})$. Since for
each edge $e$ of the underlying graph $K_{t}^{k}$, the structure
$\mathcal{K}_{t}^{k}$ has a separate binary single-element relation $R_{e}$,
the input database $\mathcal{D}$ (of the same signature as
$\mathcal{K}_{t}^{k}$) also has a relation $R^{\prime}_{e}$ whose elements can
be interpreted as $e$-coloured edges. This means that the problem of computing
$\mathcal{D}\mapsto\mathsf{hom}(\mathcal{K}_{t}^{k}\to\mathcal{D})$ can
equivalently be expressed as the following problem: Given a graph
$G^{\prime}$, that comes with an edge-colouring
$\mathsf{col}:E(G^{\prime})\mapsto E(K_{t}^{k})$, count the homomorphisms $h$
from $K_{t}^{k}$ to $G^{\prime}$ such that for each edge $e$ of $K_{t}^{k}$ we
have $\mathsf{col}(h(e))=e$.

We now reduce the problem of determining whether a graph $G$ contains $K_{t}$
to this problem. Given input $G$, we construct an edge-coloured graph
$G^{\prime}$ as follows. Each edge of $G$ is replaced by $\binom{t}{2}$ paths
of length $k$, and we colour the edges of the $i$-th of those paths with the
$k$ edges of the $k$-stretch of the $i$-th edge $e_{i}$ of $K_{t}$. It is easy
to see that $G$ contains a $t$-clique if and only if there is at least one
homomorphism from $K_{t}^{k}$ to $G^{\prime}$ that preserves the edge-colours.
Moreover, the construction of $G^{\prime}$ can clearly be done in linear time.
∎

Before proving Theorem 5, we need to take a detour to examine the complexity
of computing the reduced Euler Characteristic of a complex associated with a
UCQ. To begin with, we introduce the notion of a “power complex”.

######  Definition 46.

Let $\mathcal{U}$ be a finite set, and let $\Omega\subseteq 2^{\mathcal{U}}$
be a set system that does not contain $\mathcal{U}$. The _power complex_
$\Delta_{\Omega,\mathcal{U}}$ is a complex with ground set $\Omega$ and faces

$\mathcal{I}=\left\\{S\subseteq\Omega\leavevmode\nobreak\
:\leavevmode\nobreak\ \bigcup_{A\in S}A\neq\mathcal{U}\right\\}\,.$

It is easy to check that $\Delta_{\Omega,\mathcal{U}}$ is a complex — for each
$x\in\Omega$, the set $\\{x\\}$ is in $\mathcal{I}$ since $\Omega$ does not
contain $\mathcal{U}$. Although we typically encode complexes by the ground
set $\Omega$ and the set of facets, in the case of a power complex we list the
elements of $\mathcal{U}$ and $\Omega$.

In the first step, we show that each complex is isomorphic to a power complex.

######  Lemma 47.

Let $\Delta=(\Omega,\mathcal{I})$ be a non-trivial irreducible complex. It is
possible to compute, in polynomial time in $|\Delta|$, a set $\mathcal{U}$ and
a set $\hat{\Omega}\subseteq 2^{\mathcal{U}}$ with
$\mathcal{U}\notin\hat{\Omega}$ such that $\Delta$ is isomorphic to the power
complex $\Delta_{\hat{\Omega},\mathcal{U}}$.

###### Proof.

Let $F_{1},\dots,F_{k}$ be the facets of $\Delta$ so that the encoding of
$\Delta$ consists of $\Omega$ and $F_{1},\ldots,F_{k}$, and $|\Delta|$ is the
length of this encoding. For each $i\in[k]$, we introduce an element $E_{i}$
corresponding to $F_{i}$. Let $\mathcal{U}=\\{E_{1},\dots,E_{k}\\}$. Next, we
define a mapping $b:\Omega\to 2^{\mathcal{U}}$ as follows:

$b(x)\coloneqq\\{E_{i}\mid x\notin F_{i}\\}\,.$

Observe that $b$ is injective since otherwise two elements of $\Omega$ are
contained in the same facets of $\Delta$, which means that they dominate each
other. Also, note that $b(x)=\mathcal{U}$ implies that $x$ is contained in
every facet of $\Delta$ and therefore dominates all other elements in
$\Omega$. This gives a contradiction as $\Delta$ is non-trivial and therefore
$\Omega$ contains at least two elements (none of which dominate each other).

We choose $\hat{\Omega}$ as the range of $b$. Then, clearly, $b$ is a
bijection from $\Omega$ to $\hat{\Omega}$. Furthermore, $\mathcal{U}$ and
$\hat{\Omega}$ can be constructed in time polynomial in $|\Delta|$.

It remains to prove that $b$ is also an isomorphism from $\Delta$ to
$\Delta_{\hat{\Omega},\mathcal{U}}$. To this end, we need to show that

$S\in\mathcal{I}\Leftrightarrow\bigcup_{A\in b(S)}A\neq\mathcal{U}\,,$

where $b(S)=\\{b(x)\leavevmode\nobreak\ |\leavevmode\nobreak\ x\in S\\}$.

For the first direction, let $S\in\mathcal{I}$. W.l.o.g. we have $S\subseteq
F_{1}$. Then, for all $x\in S$, $E_{1}\notin b(x)$. Hence
$E_{1}\notin\bigcup_{A\in b(S)}A$. For the other direction, suppose that
$S\notin\mathcal{I}$. Then $S$ is not a subset of any facet. Consequently, for
every $i\in[k]$, there exists $x_{i}\in S$ such that $x_{i}\notin F_{i}$. By
definition of $b$, we thus have that, for every $i\in[k]$, there exists
$x_{i}\in S$ such that $E_{i}\in b(x_{i})$. Thus $\bigcup_{A\in
b(S)}A=\mathcal{U}$. ∎

Recall, for example, the complex $\Delta_{1}$ in Figure 1. $\Delta_{1}$ has
facets $F_{1}=\\{2,3,4\\}$, $F_{2}=\\{1,2\\}$, $F_{3}=\\{1,3\\}$, and
$F_{4}=\\{1,4\\}$. Since $\Delta_{1}$ is irreducible and non-trivial, we can
apply the construction in the previous lemma to construct an isomorphic power
complex: We set $\mathcal{U}=\\{E_{1},E_{2},E_{3},E_{4}\\}$, since
$\Delta_{1}$ has $4$ facets. Moreover, the ground set $\hat{\Omega}$ of the
power complex is the range of the function $b:\Omega\to 2^{\mathcal{U}}$ with
$b(x)\coloneqq\\{E_{i}\mid x\notin F_{i}\\}$, that is, $b(1)=\\{E_{1}\\}$
since $1\notin F_{1}$, and similarly, $b(2)=\\{E_{3},E_{4}\\}$,
$b(3)=\\{E_{2},E_{4}\\}$, and $b(4)=\\{E_{2},E_{3}\\}$. Then the facets
$\hat{\mathcal{I}}$ of the power complex are $\\{E_{1},E_{3},E_{4}\\}$,
$\\{E_{1},E_{2},E_{4}\\}$, $\\{E_{1},E_{2},E_{3}\\}$, and
$\\{E_{2},E_{3},E_{4}\\}$. Then $\Delta_{1}$ and the power complex
$\Delta_{\hat{\Omega},\mathcal{U}}$ are isomorphic, where for instance
$F_{2}=\\{1,2\\}$ corresponds to $b(1)\cup b(2)=\\{E_{1},E_{3},E_{4}\\}$. When
applied to $\Delta_{2}$, the same construction yields a power complex with
$\mathcal{U}=\\{E_{1},E_{2},E_{3},E_{4}\\}$ and ground set
$\\{\\{E_{3},E_{4}\\},\\{E_{1},E_{4}\\},\\{E_{2},E_{4}\\},\\{E_{1},E_{2},E_{3}\\}\\}$.

We now introduce the main technical result that we use to establish lower
bounds for Meta; note that computability result in the last part of Lemma 48
will just be required for the construction of exemplary classes of UCQs in the
appendix.

######  Lemma 48.

For each positive integer $t$, there is a polynomial-time algorithm
$\hat{\mathbb{A}}_{t}$ that, when given as input a non-trivial irreducible
complex $\Delta=(\Omega,\mathcal{I})$ with $\Omega\notin\mathcal{I}$, computes
a union of quantifier-free conjunctive queries
$\Psi=(\mathcal{B}_{1},\dots,\mathcal{B}_{\ell})$ satisfying the following
constraints:

  1. 1.

$\boldsymbol{\wedge}\left(\Psi\right)\cong\mathcal{K}_{t}^{k}$ for some $k\geq
1$.

  2. 2.

$c_{\Psi}(\boldsymbol{\wedge}\left(\Psi\right))=-\hat{\chi}(\Delta)$.

  3. 3.

For all relational structures
$\mathcal{B}\ncong\boldsymbol{\wedge}\left(\Psi\right)$,
$c_{\Psi}(\mathcal{B})\neq 0$ implies that $\mathcal{B}$ is acyclic.

  4. 4.

$\ell\leq|\Omega|$.

  5. 5.

For all $i\in[\ell]$ the conjunctive query $\mathcal{B}_{i}$ is acyclic and
self-join-free, and has arity $2$.

Moreover, the algorithm $\hat{\mathbb{A}}_{t}$ can be explicitly constructed
from $t$.

###### Proof.

The algorithm $\hat{\mathbb{A}}_{t}$ applies Lemma 47 to obtain $\mathcal{U}$
and $\hat{\Omega}$ such that the power-complex
$\Delta_{\hat{\Omega},\mathcal{U}}$ is isomorphic to $\Delta$. Let
$k=|\mathcal{U}|$ and assume w.l.o.g. that $\mathcal{U}=[k]$. Let
$\hat{\Omega}=\\{A_{1},\dots,A_{\ell}\\}$. Let $e^{j}$ be the $j$-th edge of
the $k$-stretch of $e$ in $K_{t}^{k}$ and recall that $\mathcal{K}_{t}^{k}$
contains the relations $R_{e^{i}}=\\{e^{i}\\}$ for each $e\in E(K_{t})$ and
$i\in[k]$. For each $i\in[k]$ we define $\mathcal{E}_{i}$ to be the
substructure of $\mathcal{K}_{t}^{k}$ containing the universe $V(K_{t}^{k})$
and the relations $R_{e^{i}}$ (one relation for each $e\in E(K_{t})$). The
algorithm constructs $\Psi=(\mathcal{B}_{1},\dots,\mathcal{B}_{\ell})$ as
follows: For each $j\in[\ell]$, set $\mathcal{B}_{j}=\cup_{i\in
A_{j}}\mathcal{E}_{i}$, that is, $\mathcal{B}_{j}$ is the substructure of
$\mathcal{K}_{t}^{k}$ obtained by taking all relations in $\mathcal{E}_{i}$
for all $i\in A_{j}$. The pseudocode for $\hat{\mathbb{A}}_{t}$ is as follows.

Algorithm 1 Pseudocode for $\hat{\mathbb{A}}_{t}$

1:Input: $\Delta=(\Omega,\mathcal{I})$

2:$(F_{1},\dots,F_{k})\leftarrow$ facets of $\Delta$

3:for $x\in\Omega$ do

4: $A_{x}\leftarrow\\{i\mid x\notin F_{i}\\}$ $\triangleright$
$\mathcal{U}=[k]$ and $\hat{\Omega}=\\{A_{x}\mid
x\in\Omega\\}=\\{A_{1},\ldots,A_{\ell}\\}$ yield the power complex

5:end for

6:$K_{t}\leftarrow$ $t$-clique, $m\leftarrow\binom{t}{2}$ $\triangleright$
$e_{i}$ denotes the $i$-th edge of $K_{t}$

7:$K^{k}_{t}\leftarrow$ $k$-stretch of $K_{t}$ $\triangleright$ $e_{i}^{j}$
denotes the $j$-th edge of the $k$-stretch of $e_{i}\in E(K_{t})$

8:for $i\in[m]$, $j\in[k]$ do

9: $R_{e_{i}^{j}}\leftarrow\\{e_{i}^{j}\\}$

10:end for

11:for $i\in[k]$ do

12:
$\mathcal{E}_{i}\leftarrow(V(K_{k}^{t}),R_{e_{1}^{i}},\dots,R_{e_{m}^{i}})$

13:end for

14:for $j\in[\ell]$ do

15: $\mathcal{B}_{j}\leftarrow\bigcup_{i\in A_{j}}\mathcal{E}_{i}$

16:end for

17:Output: $\Psi=(\mathcal{B}_{1},\dots,\mathcal{B}_{\ell})$

We now prove the required properties of $\Psi$.

  1. 1.

Recall that $\Omega$ is not a facet. Since $\Delta$ and
$\Delta_{\hat{\Omega},\mathcal{U}}$ are isomorphic, $\hat{\Omega}$ is not a
facet. Thus $\bigcup_{i\in[\ell]}A_{i}=\mathcal{U}$ by the definition of power
complexes. Since $\mathcal{B}_{j}$ contains all relations in $\mathcal{E}_{i}$
with $i\in A_{j}$, we have that
$\boldsymbol{\wedge}\left(\Psi\right)=\mathcal{K}_{t}^{k}$ as desired.

  2. 2.

Recall from Definition 25 that
$\mathcal{I}(\mathcal{B},X)=\\{J\subseteq[\ell]\leavevmode\nobreak\
|\leavevmode\nobreak\
(\mathcal{B},X)\sim\boldsymbol{\wedge}\left(\Psi|_{J}\right)\\}$. Since we are
in the setting of quantifier-free queries ($X=U(\mathcal{B})$; we will drop
the $X$ as before), equivalence $(\sim)$ is equivalent to isomorphism. Thus,
we have that $c_{\Psi}(\boldsymbol{\wedge}\left(\Psi\right))$ is equal to

$\sum_{\begin{subarray}{c}J\subseteq[\ell]\\\
\boldsymbol{\wedge}\left(\Psi\right)\cong\boldsymbol{\wedge}\left(\Psi|_{J}\right)\end{subarray}}(-1)^{|J|+1}=\sum_{\begin{subarray}{c}J\subseteq[\ell]\\\
\boldsymbol{\wedge}\left(\Psi\right)\not\cong\boldsymbol{\wedge}\left(\Psi|_{J}\right)\end{subarray}}(-1)^{|J|}=\sum_{\begin{subarray}{c}J\subseteq[\ell]\\\
\cup_{j\in
J}A_{j}\neq\mathcal{U}\end{subarray}}(-1)^{|J|}=-\hat{\chi}(\Delta_{\hat{\Omega},\mathcal{U}})=-\hat{\chi}(\Delta)\,.$

  3. 3.

If $\mathcal{B}\ncong\boldsymbol{\wedge}\left(\Psi\right)$ and
$c_{\Psi}(\mathcal{B})\neq 0$, then $\mathcal{B}$ is a substructure of
$\mathcal{K}_{t}^{k}$ that is missing at least one of the $\mathcal{E}_{i}$.
The claim holds since each $\mathcal{E}_{i}$ is a feedback edge set (i.e., the
deletion of all tuples in $\mathcal{E}_{i}$ breaks every cycle), because
deleting $\mathcal{E}_{i}$ corresponds to deleting one edge from each stretch.

  4. 4.

Follows immediately by construction.

  5. 5.

The $\mathcal{B}_{i}$ are self-join-free and of arity $2$ since they are
substructures of $\mathcal{K}_{t}^{k}$ (see Observation 44). For acyclicity,
we use the fact that for each $j$ we have $A_{j}\neq\mathcal{U}$ by definition
of the power complex, which implies the claim by the same argument as 3.

With all cases completed, the proof is concluded. ∎

To provide a concrete example, we apply the construction in Lemma 48 to the
complexes $\Delta_{1}$ and $\Delta_{2}$ in Figure 1. For this example, we will
choose $t=3$. Since both $\Delta_{1}$ and $\Delta_{2}$ have four facets, we
will choose $k=4$. The structure $\mathcal{K}_{t}^{k}$ is depicted in Figure
2, together with six selected substructures corresponding to the
$\mathcal{B}_{j}$ in the proof of the Lemma 48.

Figure 2: _(Top:)_ The structure $\mathcal{K}_{3}^{4}$. _(Bottom:)_
Substructures $\mathcal{S}_{A}$ for some selected $A\subseteq[4]$. Observe
that all of the $\mathcal{S}_{A}$ are _acyclic_.

Let us start by applying $\hat{\mathbb{A}}_{3}$ to $\Delta_{1}$. Recall from
the previous example, that the power complex of $\Delta_{1}$ has ground set
$\\{A_{1},A_{2},A_{3},A_{4}\\}$ with $A_{1}=\\{E_{1}\\}$,
$A_{2}=\\{E_{3},E_{4}\\}$, $A_{3}=\\{E_{2},E_{4}\\}$, and
$A_{4}=\\{E_{2},E_{3}\\}$. Thus $\hat{\mathbb{A}}_{3}$ returns the UCQ
$\Psi_{1}=(\mathcal{S}_{1},\mathcal{S}_{34},\mathcal{S}_{24},\mathcal{S}_{23})$.
Similarly, applying $\hat{\mathbb{A}}_{3}$ to $\Delta_{2}$ yields the UCQ
$\Psi_{2}=(\mathcal{S}_{24},\mathcal{S}_{34},\mathcal{S}_{14},\mathcal{S}_{123})$.

For the purpose of illustration, let us write $\Psi_{1}$ and $\Psi_{2}$ as
formulas. To this end, given a non-empty subset $A$ of $\\{1,2,3,4\\}$, define
the conjunctive query $\varphi_{A}$ as follows:

$\varphi_{A}=\bigwedge_{a\in A}R_{e_{1}^{a}}(x_{a-1},x_{a})\wedge
R_{e_{2}^{a}}(x_{4+a-1},x_{4+a})\wedge R_{e_{3}^{a}}(x_{8+a-1},x_{8+a})\,,$

where indices are taken modulo $12$. Observe that the $\mathcal{S}_{A}$
depicted in Figure 2 are the structures associated to $\varphi_{A}$ for
$A\in\\{\\{1\\},\\{2,4\\},\\{1,4\\},\\{3,4\\},\\{2,3\\},\\{1,2,3\\}\\}$. Then

$\displaystyle\Psi_{1}(x_{0},\dots,x_{11})$
$\displaystyle=\varphi_{1}\vee\varphi_{34}\vee\varphi_{24}\vee\varphi_{23}\,,\text{
and}$ $\displaystyle\Psi_{2}(x_{0},\dots,x_{11})$
$\displaystyle=\varphi_{24}\vee\varphi_{34}\vee\varphi_{14}\vee\varphi_{123}$

Note that
$\boldsymbol{\wedge}\left(\Psi_{1}\right)=\boldsymbol{\wedge}\left(\Psi_{2}\right)=\mathcal{K}^{4}_{3}$.
Now recall that $\hat{\chi}(\Delta_{1})\neq 0$ and $\hat{\chi(\Delta_{2})}=0$.
Thus, by Item 2. of Lemma 48, it holds that
$c_{\Psi_{1}}(\mathcal{K}^{4}_{3})\neq 0$, which means that there is an
acyclic CQ in the CQ expansion of $\Psi_{1}$. On the contrary, by Item 3. of
Lemma 48, for all $(\mathcal{A},X)$, we have that
$c_{\Psi_{2}}(\mathcal{A},X)\neq 0$ implies that $(\mathcal{A},X)$ is acyclic.
So, as a conclusion of our example, using complexity monotonicity (Corollary
29) and Theorem 37, we obtain as an immediate consequence:

######  Corollary 49.

While it is not possible to count answers to $\Psi_{1}$ in linear time (in the
input database), unless the SETH fails, for $\Psi_{2}$ such a linear-time
algorithm exists (even though
$\boldsymbol{\wedge}\left(\Psi_{1}\right)=\boldsymbol{\wedge}\left(\Psi_{2}\right)$).

###### Proof.

By Corollary 29, it is possible to count answers to a UCQ $\Psi$ in linear
time if and only if for each #minimal conjunctive query $(\mathcal{A},X)$ with
$c_{\Psi}(\mathcal{A},X)\neq 0$, it is possible to count answers to
$(\mathcal{A},X)$ in linear time. Since $\Psi_{1}$ and $\Psi_{2}$ are
quantifier-free, all conjunctive queries
$\boldsymbol{\wedge}\left(\Psi_{1}|_{J}\right)$ and
$\boldsymbol{\wedge}\left(\Psi_{2}|_{J}\right)$ are also quantifier-free and
thus $\\#\text{minimal}$. For all $(\mathcal{A},X)$,
$c_{\Psi_{2}}(\mathcal{A},X)\neq 0$ implies that $(\mathcal{A},X)$ is acyclic,
so it follows from Theorem 37 that it is possible to count answers to
$\Psi_{2}$ in linear time. Moreover, given that $\mathcal{K}^{4}_{3}$ is not
acyclic, Theorem 37 also implies that counting answers to
$\mathcal{K}^{4}_{3}$ cannot be done in linear time, unless SETH fails. Since
$c_{\Psi_{1}}(\mathcal{K}^{4}_{3})\neq 0$, counting answers to $\Psi_{1}$
cannot be done in linear time, unless SETH fails.∎

We will now conclude the hardness proof for Meta.

######  Lemma 50.

For each positive integer $t$, there is a polynomial-time algorithm
$\mathbb{A}_{t}$ that, when given as input a complex
$\Delta=(\Omega,\mathcal{I})$, either computes $\hat{\chi}(\Delta)$, or
computes a union of quantifier-free conjunctive queries
$\Psi=(\mathcal{B}_{1},\dots,\mathcal{B}_{\ell})$ satisfying the following
constraints:

  1. 1.

$\boldsymbol{\wedge}\left(\Psi\right)\cong\mathcal{K}_{t}^{k}$ for some $k\geq
1$.

  2. 2.

$c_{\Psi}(\boldsymbol{\wedge}\left(\Psi\right))=-\hat{\chi}(\Delta)$.

  3. 3.

For all relational structures
$\mathcal{B}\ncong\boldsymbol{\wedge}\left(\Psi\right)$,
$c_{\Psi}(\mathcal{B})\neq 0$ implies that $\mathcal{B}$ is acyclic.

  4. 4.

$\ell\leq|\Omega|$.

  5. 5.

For all $i\in[\ell]$ the conjunctive query $\mathcal{B}_{i}$ is acyclic and
self-join-free, and has arity $2$.

###### Proof.

Given $\Delta=(\Omega,\mathcal{I})$, we can successively apply Lemma 42
without changing the reduced Euler characteristic, until the resulting
simplicial complex is irreducible. This can be done in polynomial time: By
Lemma 41 it suffices to check whether there are $y\neq x\in\Omega$ such that
each facet containing $y$ also contains $x$. If no such pair exists, we are
done. Otherwise we delete $y$ from $\Omega$ and from all facets and continue
recursively. Clearly, the number of recursive steps is bounded by $|\Omega|$
so the run time is at most a polynomial in $|\Delta|$.

If this process makes the complex trivial, we output $0$ (i.e., the reduced
Euler Characteristic of the trivial complex). We can furthermore assume that
$\Omega$ is not a facet, i.e., that $\Omega\notin\mathcal{I}$, since in this
case every subset of $\Omega$ is a face and the reduced Euler Characteristic
is $0$. We can thus assume that $\Delta$ is non-trivial and irreducible, and
that $\Omega$ is not a facet. Therefore, we can use the algorithm
$\hat{\mathbb{A}}_{t}$ from Lemma 48. This concludes the proof. ∎

We are now able to prove our lower bounds for Meta.

######  Lemma 51.

If the Triangle Conjecture is true then Meta is $\mathrm{NP}$-hard. If the
Triangle Conjecture and ETH are both true then Meta cannot be solved in time
$2^{o(\ell)}$ where $\ell$ is the number of conjunctive queries in its input.
Both results remain true even if the input to Meta is restricted to be over a
binary signature.

###### Proof.

For the first result, we assume the triangle conjecture and show that Meta is
NP-hard. The input to Meta is a formula $\Psi^{\prime}$ which is a union of
quantifier-free, self-join-free, and acyclic conjunctive queries. The goal is
to decide whether counting answers of $\Psi^{\prime}$ (in an input database)
can be done in linear time.

We reduce from $3$-SAT. Let $F$ be a $3$-SAT formula. The first step of our
reduction is to apply a reduction from [57]. Concretely, [57] gives a
reduction that, given a $3$-SAT formula $F$ with $n$ variables and $m$
clauses, outputs in polynomial time a complex $\Delta$ such that $F$ is
satisfiable if and only if $\hat{\chi}(\Delta)\neq 0$. Moreover, the ground
set of $\Delta$ has size $O(n+m)$.

Let $t=3$ and let $\mathbb{A}_{t}$ be the algorithm from Lemma 50. Consider
running $\mathbb{A}_{t}$ with input $\Delta$. If $\mathbb{A}_{t}$ outputs
$\hat{\chi}(\Delta)$ then we can check immediately whether
$\hat{\chi}(\Delta)=0$, which determines whether or not $F$ is satisfiable.
Otherwise, $\mathbb{A}_{t}$ outputs a formula $\Psi$ which is a union of self-
join-free, quantifier-free, and acylic conjunctive queries of arity $2$, and
further has the property that
$c_{\Psi}(\boldsymbol{\wedge}\left(\Psi\right))=-\hat{\chi}(\Delta)$. Since
$\mathbb{A}_{t}$ is a polynomial-time algorithm, the number of conjunctive
queries $\ell$ in $\Psi$ is at most a polynomial in $n+m$.

We wish to show that determining whether counting answers of $\Psi$ can be
done in linear time would reveal whether or not
$c_{\Psi}(\boldsymbol{\wedge}\left(\Psi\right))=0$ (which would in turn reveal
whether $F$ is satisfiable).

By Corollary 29, it is possible to compute
$\mathcal{D}\mapsto\mathsf{ans}(\Psi\to\mathcal{D})$ in linear time if and
only if, for each relational structure $\mathcal{A}$ with
$c_{\Psi}(\mathcal{A})\neq 0$, the function
$\mathcal{D}\mapsto\mathsf{hom}(\mathcal{A}\to\mathcal{D})$ can be computed in
linear time.

So the intermediate problem is to check whether, for each relational structure
$\mathcal{A}$ with $c_{\Psi}(\mathcal{A})\neq 0$, the function
$\mathcal{D}\mapsto\mathsf{hom}(\mathcal{A}\to\mathcal{D})$ can be computed in
linear time. We wish to show that solving the intermediate problem (in
polynomial time) would enable us to determine whether or not
$c_{\Psi}(\boldsymbol{\wedge}\left(\Psi\right))=0$ (also in polynomial time).

Item 1 of Lemma 50 implies that there is a positive integer $k$ such that
$\boldsymbol{\wedge}\left(\Psi\right)\cong\mathcal{K}_{3}^{k}$. Thus,
$\boldsymbol{\wedge}\left(\Psi\right)$ is not acyclic. However, Item 3 of
Lemma 50 implies that every relational structure
$\mathcal{A}\ncong\boldsymbol{\wedge}\left(\Psi\right)$ in the intermediate
problem, the structure $\mathcal{A}$ is acyclic. Theorem 37 shows (assuming
the triangle inequality) that, for each acyclic $\mathcal{A}$,
$\mathcal{D}\mapsto\mathsf{hom}(\mathcal{A}\to\mathcal{D})$ can be computed in
linear time. We conclude that the answer to the intermediate problem is yes
iff $c_{\Psi}(\boldsymbol{\wedge}\left(\Psi\right))=0$, completing the proof
that Meta is NP-hard.

To obtain the second result, we assume both the triangle conjecture and ETH.
In this case, we apply the Sparsification Lemma [42] to the initial $3$-SAT
formula $F$ before invoking the reduction. By the Sparsification Lemma, it is
possible in time $2^{o(n)}$ to construct $2^{o(n)}$ formulas
$F_{1},F_{2},\dots$ such that $F$ is satisfiable if and only if at least one
of the $F_{i}$ is satisfiable. Additionally, each $F_{i}$ has $O(n)$ clauses.
As before, for each such $F_{i}$ we obtain in polynomial time a corresponding
complex $\Delta_{i}$, whose ground set has size $O(n)$. For each $\Delta_{i}$,
the algorithm from Lemma 50 either outputs its reduced Euler characteristic
$\hat{\chi}(\Delta_{i})$ or or outputs a UCQ $\Psi_{i}$ which has the property
that that
$c_{\Psi}(\boldsymbol{\wedge}\left(\Psi_{i}\right))=-\hat{\chi}(\Delta_{i})$.

If, for any $i$, the algorithm outputs a value $\hat{\chi}(\Delta_{i})\neq 0$
then $F_{i}$ is satisfiable, so $F$ is satisfiable. Let $I$ be the set of
indices $i$ such that the algorithm outputs a UCQ $\Psi_{i}$. The argument
from the first result shows that $F$ is satisfiable if and only if there is an
$i\in I$ such that counting answers to $\Psi_{i}$ can be done in linear time.

We will argue that a $2^{o(\ell)}$ algorithm for Meta (where $\ell$ is the
number of CQs in its input) would make it possible to determine in $2^{o(n)}$
time whether there is an $i\in I$ such that counting answers to $\Psi_{i}$ can
be done in linear time. This means that a $2^{o(\ell)}$ algorithm for Meta
would make it possible to determine in $2^{o(n)}$ time whether $F$ is
satisfiable, contrary to ETH.

To do this, we just need to show that the number of CQs in $\Psi_{i}$, which
we denote $\ell(\Psi_{i})$, is $O(n)$. This follows since the ground set of
$\Delta_{i}$ has size $O(n)$ and by Item 4 of Lemma 50, $\ell(\Psi_{i})$ is at
most the size of the ground set. Since the size of $I$ is $2^{o(n)}$ the
running time for determining whether $F$ is satisfiable is $2^{o(n)}$ (for the
sparsification) plus $|I|\,\mathrm{poly}(n)=2^{o(n)}$ time (for computing the
complexes $\Delta_{i}$) plus $\sum_{i\in I}2^{o(\ell(\Psi_{i}))}=2^{o(n)}$ for
the calls to Meta, contradicting ETH, as desired. ∎

The proofs of the following two lemmas are analogous, with the only exception
that, for Lemma 53, we do not invoke Theorem 37 but apply Lemma 45 with $d=1$
to obtain a $t$ such that for each $k$ the function
$\mathcal{D}\mapsto\mathsf{hom}(\mathcal{K}_{t}^{k}\to\mathcal{D})$ cannot be
evaluated in linear time.

######  Lemma 52.

If SETH is true then Meta is $\mathrm{NP}$-hard and cannot be solved in time
$2^{o(\ell)}$. This remains true even if the input to Meta is restricted to be
over a binary signature.

######  Lemma 53.

If non-uniform ETH is true then Meta is $\mathrm{NP}$-hard and, furthermore,

$\textsc{Meta}\notin\bigcap_{\varepsilon>0}\mathrm{DTime}(2^{\varepsilon\cdot\ell})\,.$

This remains true even if the input to Meta is restricted to be over a binary
signature.

Theorem 5 now follows immediately from Lemmas 38, 51, 52, and 53.

Finally, we point out that our construction shows, in fact, something much
stronger than just the intractability of deciding whether we can count answers
to a UCQ in linear time: For any pair $(c,d)$ of positive integers satisfying
$c\leq d$, it is hard to distinguish whether counting answers to a given UCQ
can be done in time $O(n^{c})$, or whether it takes time at least
$\omega(n^{d})$. Formally, we introduce the following gap problem:

######  Definition 54.

Let $c$ and $d$ be positive integers with $c\leq d$. The problem
$\textsc{Meta}[c,d]$ has as input a union of quantifier-free, self-join-free,
and acyclic conjunctive queries $\Psi$. The goal is to decide whether the
function $\mathcal{D}\mapsto\mathsf{ans}(\Psi\to\mathcal{D})$ can be computed
in time $O(|\mathcal{D}|^{c})$, or whether it cannot be solved in time
$O(|\mathcal{D}|^{d})$; the behaviour may be undefined for inputs $\Psi$ for
which the best exponent in the running time is in the interval $(c,d]$.

######  Theorem 55.

Assume that non-uniform ETH holds. Then for each positive integer $d$, the
problem $\textsc{Meta}[1,d]$ is $\mathrm{NP}$-hard and, furthermore,

$\textsc{Meta}[1,d]\notin\bigcap_{\varepsilon>0}\mathrm{DTime}(2^{\varepsilon\cdot\ell})\,.$

This remains true even if the input to Meta is restricted to be over a binary
signature.

###### Proof.

By Lemma 45 there is a positive integer $t$ such that for all positive
integers $k$, the function
$\mathcal{D}\mapsto\mathsf{hom}(\mathcal{K}_{t}^{k}\to\mathcal{D})$ cannot be
computed in time $O(|\mathcal{D}|^{d})$. Fix this $t$ and proceed similarly to
the proof of Lemma 53. ∎

Corollary 56 is an immediate consequence, since any algorithm that solves
$\textsc{Meta}[c,d]$ for $1\leq c\leq d$ solves, without modification,
$\textsc{Meta}[1,d]$.

######  Corollary 56.

Assume that non-uniform ETH holds. Then for every pair $(c,d)$ of positive
integers satisfying $c\leq d$, the problem $\textsc{Meta}[c,d]$ is
$\mathrm{NP}$-hard and, furthermore,

$\textsc{Meta}[c,d]\notin\bigcap_{\varepsilon>0}\mathrm{DTime}(2^{\varepsilon\cdot\ell})\,.$

This remains true even if the input to Meta is restricted to be over a binary
signature.

##  5 Connection to the Weisfeiler-Leman-Dimension

Recall that we call a database a _labelled graph_ if its signature has arity
at most $2$, and if it does not contain a self-loop, that is, a tuple of the
form $(v,v)$. Moreover, (U)CQs on labelled graphs must also have signatures of
arity at most $2$ and must not contain atoms of the form $R(v,v)$, where $R$
is any relation symbol of the signature.

Neuen [53] and Lanzinger and Barceló [47] determined the WL-dimension of
computing finite linear combinations of homomorphism counts to be the
_hereditary treewidth_ , defined momentarily. Since counting homomorphisms is
equivalent to counting answers to quantifier-free conjunctive queries, and
since the number of answers of a union of conjunctive queries can be expressed
as a linear combination of conjunctive query answer counts (Lemma 26), we can
state their results as follows.

######  Definition 57 (Hereditary Treewidth of UCQs).

Let $\Psi$ be a UCQ. The _hereditary treewidth_ of $\Psi$, denoted by
$\mathsf{hdtw}(\Psi)$, is defined as follows:

$\mathsf{hdtw}(\Psi)=\max\\{\mathsf{tw}(A,X)\mid c_{\Psi}(A,X)\neq 0\\},$

that is, $\mathsf{hdtw}(\Psi)$ is the maximum treewidth of any conjunctive
query that survives with a non-zero coefficient when $\Psi$ is expressed as a
linear combination of conjunctive queries.

Then, applying the main result of Neuen, Lanzinger and Barceló to UCQs, we
obtain:

######  Theorem 58 ([53, 47]).

Let $\Psi$ be a quantifier-free UCQ on labelled graphs. Then
$\mathsf{dim}_{\mathrm{WL}}(\Psi)=\mathsf{hdtw}(\Psi)$.

This enables us to prove Theorem 7, which we restate for convenience. See 7

###### Proof.

For the upper bound, we compute the coefficients

$c_{\Psi}(\mathcal{A},X)=\sum_{\begin{subarray}{c}J\subseteq[\ell]\\\
\boldsymbol{\wedge}\left(\Psi|_{J}\right)\cong(\mathcal{A},X)\end{subarray}}(-1)^{|J|+1},$

that is, for each subset $J\subseteq[\ell]$, compute
$\boldsymbol{\wedge}\left(\Psi|_{J}\right)$. Afterwards, collect the
isomorphic terms and compute
$c_{\Psi}(\boldsymbol{\wedge}\left(\Psi|_{J}\right))$ for each
$J\subseteq[\ell]$. Clearly, $c_{\Psi}(\mathcal{A},X)=0$ for every
$(\mathcal{A},X)$ that is not isomorphic to any
$\boldsymbol{\wedge}\left(\Psi|_{J}\right)$. Clearly, this can be done in time
$|\Psi|^{O(1)}\cdot O(2^{\ell})$.

Next, for each $(\mathcal{A},X)$ with $c_{\Psi}(\mathcal{A},X)\neq 0$, we use
the algorithm of Feige, Hajiaghayi, and Lee [30] to compute in polynomial time
a $g$-approximation $S(\mathcal{A},X)$ of the treewidth of $(\mathcal{A},X)$,
where $g(k)\in O(\sqrt{\log k})$. Finally, we output the maximum of
$S(\mathcal{A},X)$ over all $(\mathcal{A},X)$ with
$c_{\Psi}(\mathcal{A},X)\neq 0$

For the lower bound, assume that there is a function
$f:\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ and an algorithm $\mathbb{A}$ that
computes an $f$-approximation of $\mathsf{dim}_{\mathrm{WL}}(\Psi)$ in
subexponential time in the number of conjunctive queries in the union. We will
use $\mathbb{A}$ to construct a subexponential time algorithm for $3$-SAT,
which refutes ETH. Our construction is similar to the proof of Lemma 51. Fix
any positive integer $t>f(1)+1$.

Let $F$ be a $3$-CNF with $n$ variables, which we can again assume to be
sparse by using the Sparsification Lemma [16] (the details are identical to
its application in the proof of Lemma 51). Next, using [57], we obtain a
complex $\Delta$, the reduced Euler characteristic of which is zero if and
only if $F$ is not satisfiable. Finally, we apply Lemma 50 with our choice of
$t$. The corresponding algorithm computes in polynomial time either the
reduced Euler characteristic of $\Delta$, or otherwise outputs a UCQ $\Psi$
such that the number $\ell$ of CQs in the union is bounded by $O(n)$.
Moreover, the hereditary treewidth of $\Psi$ is $1$ if $\hat{\chi}(\Delta)=0$,
i.e., if $F$ is not satisfiable; and its hereditary treewidth is at least
$\mathsf{tw}(\mathcal{K}^{k}_{t})=t-1>f(1)$, otherwise.

Thus, we run $\mathbb{A}$ on $\Psi$ and report that $F$ is satisfiable if and
only if it outputs $S>f(1)$. Since $\mathbb{A}$ runs in time $2^{o(\ell)}$,
the total running time is bounded by $2^{o(n)}$, which refutes ETH.
$\mathrm{NP}$-hardness follows likewise. ∎

Finally, the proof of Theorem 8 is identical with the only exception being
that, since $k$ is fixed, we can substitute the approximation algorithm for
treewidth of Feige, Hajiaghayi, and Lee [30] by the exact algorithm of
Bodlaender [14], which runs in polynomial time if $k$ is fixed.

## References

  * [1] Amir Abboud and Virginia Vassilevska Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443. IEEE Computer Society, 2014.
  * [2] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison-Wesley, 1995.
  * [3] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros.  When is approximate counting for conjunctive queries tractable?  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1015–1027. ACM, 2021.
  * [4] Vikraman Arvind.  The Weisfeiler-Lehman procedure.  Bull. EATCS, 120, 2016.
  * [5] Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky.  On the Weisfeiler-Leman dimension of fractional packing.  Inf. Comput., 288:104803, 2022.
  * [6] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, volume 4646 of Lecture Notes in Computer Science, pages 208–222. Springer, 2007.
  * [7] Pablo Barceló, Mikhail Galkin, Christopher Morris, and Miguel A. Romero Orth.  Weisfeiler and Leman go relational.  In Bastian Rieck and Razvan Pascanu, editors, Learning on Graphs Conference, LoG 2022, 9-12 December 2022, Virtual Event, volume 198 of Proceedings of Machine Learning Research, page 46. PMLR, 2022.
  * [8] Pablo Barceló, Miguel Romero, and Moshe Y. Vardi.  Semantic Acyclicity on Graph Databases.  SIAM J. Comput., 45(4):1339–1376, 2016.
  * [9] Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, and Asaf Shapira.  Counting subgraphs in degenerate graphs.  J. ACM, 69(3):23:1–23:21, 2022.
  * [10] Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt.  Constant delay enumeration for conjunctive queries: a tutorial.  ACM SIGLOG News, 7(1):4–33, 2020.
  * [11] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering conjunctive queries under updates.  In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 303–318. ACM, 2017.
  * [12] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering UCQs under updates and in the presence of integrity constraints.  In Benny Kimelfeld and Yael Amsterdamer, editors, 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, volume 98 of LIPIcs, pages 8:1–8:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [13] Christoph Berkholz and Nicole Schweikardt.  Constant delay enumeration with fpt-preprocessing for conjunctive queries of bounded submodular width.  In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 58:1–58:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [14] Hans L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.
  * [15] Jin-yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identification.  Comb., 12(4):389–410, 1992.
  * [16] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi.  The complexity of satisfiability of small depth circuits.  In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 75–85. Springer, 2009.
  * [17] Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Alessio Conte, Benny Kimelfeld, and Nicole Schweikardt.  Answering (unions of) conjunctive queries using random access and random-order enumeration.  ACM Trans. Database Syst., 47(3):9:1–9:49, 2022.
  * [18] Ashok K. Chandra and Philip M. Merlin.  Optimal Implementation of Conjunctive Queries in Relational Data Bases.  In John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison, editors, Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 77–90. ACM, 1977\.
  * [19] Hubie Chen and Stefan Mengel.  A trichotomy in the complexity of counting answers to conjunctive queries.  In Marcelo Arenas and Martín Ugarte, editors, 18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium, volume 31 of LIPIcs, pages 110–126. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.
  * [20] Hubie Chen and Stefan Mengel.  Counting answers to existential positive queries: A complexity classification.  In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 315–326. ACM, 2016.
  * [21] Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia.  Tight lower bounds for certain parameterized NP-hard problems.  Inf. Comput., 201(2):216–231, 2005.
  * [22] Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia.  Strong computational lower bounds via parameterized complexity.  J. Comput. Syst. Sci., 72(8):1346–1367, 2006.
  * [23] Yijia Chen, Kord Eickmeyer, and Jörg Flum.  The exponential time hypothesis and the parameterized clique problem.  In Dimitrios M. Thilikos and Gerhard J. Woeginger, editors, Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings, volume 7535 of Lecture Notes in Computer Science, pages 13–24. Springer, 2012.
  * [24] Radu Curticapean, Holger Dell, and Dániel Marx.  Homomorphisms are a good basis for counting small subgraphs.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210–223. ACM, 2017.
  * [25] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [26] Víctor Dalmau and Peter Jonsson.  The complexity of counting homomorphisms seen from the other side.  Theor. Comput. Sci., 329(1-3):315–323, 2004.
  * [27] Holger Dell, Martin Grohe, and Gaurav Rattan.  Lovász meets Weisfeiler and Leman.  In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 40:1–40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [28] Holger Dell, Marc Roth, and Philip Wellnitz.  Counting answers to existential questions.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 113:1–113:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [29] Arnaud Durand and Stefan Mengel.  Structural tractability of counting of solutions to conjunctive queries.  In Wang-Chiew Tan, Giovanna Guerrini, Barbara Catania, and Anastasios Gounaris, editors, Joint 2013 EDBT/ICDT Conferences, ICDT ’13 Proceedings, Genoa, Italy, March 18-22, 2013, pages 81–92. ACM, 2013.
  * [30] Uriel Feige, Mohammad Taghi Hajiaghayi, and James R. Lee.  Improved approximation algorithms for minimum weight vertex separators.  SIAM J. Comput., 38(2):629–657, 2008.
  * [31] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.
  * [32] Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Zivný.  Approximately counting answers to conjunctive queries with disequalities and negations.  In Leonid Libkin and Pablo Barceló, editors, PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 315–324. ACM, 2022.
  * [33] Jacob Focke and Marc Roth.  Counting small induced subgraphs with hereditary properties.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 1543–1551. ACM, 2022.
  * [34] Martin Fürer.  On the combinatorial power of the weisfeiler-lehman algorithm.  In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, volume 10236 of Lecture Notes in Computer Science, pages 260–271, 2017.
  * [35] Georg Gottlob, Gianluigi Greco, and Francesco Scarcello.  Treewidth and hypertree width.  In Lucas Bordeaux, Youssef Hamadi, and Pushmeet Kohli, editors, Tractability: Practical Approaches to Hard Problems, pages 3–38. Cambridge University Press, 2014.
  * [36] Georg Gottlob, Nicola Leone, and Francesco Scarcello.  Hypertree decomposition and tractable queries.  Journal of Computer and System Sciences, 64(3):579–627, 2002.
  * [37] Gianluigi Greco and Francesco Scarcello.  Counting solutions to conjunctive queries: structural and hybrid tractability.  In Richard Hull and Martin Grohe, editors, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’14, Snowbird, UT, USA, June 22-27, 2014, pages 132–143. ACM, 2014.