# Combined Approximations for Uniform Operational Consistent Query Answering

Marco Calautti  University of Milan<EMAIL_ADDRESS>,  Ester Livshits
University of Edinburgh<EMAIL_ADDRESS>,  Andreas Pieris  University
of Edinburgh & University of Cyprus<EMAIL_ADDRESS>and  Markus Schneider
University of Edinburgh<EMAIL_ADDRESS>
###### Abstract.

Operational consistent query answering (CQA) is a recent framework for CQA
based on revised definitions of repairs, which are built by applying a
sequence of operations (e.g., fact deletions) starting from an inconsistent
database until we reach a database that is consistent w.r.t. the given set of
constraints. It has been recently shown that there are efficient
approximations for computing the percentage of repairs, as well as of
sequences of operations leading to repairs, that entail a given query when we
focus on primary keys, conjunctive queries, and assuming the query is fixed
(i.e., in data complexity). However, it has been left open whether such
approximations exist when the query is part of the input (i.e., in combined
complexity). We show that this is the case when we focus on self-join-free
conjunctive queries of bounded generelized hypertreewidth. We also show that
it is unlikely that efficient approximation schemes exist once we give up one
of the adopted syntactic restrictions, i.e., self-join-freeness or bounding
the generelized hypertreewidth. Towards the desired approximation schemes, we
introduce a novel counting complexity class, called $\mathsf{SpanTL}$, show
that each problem in $\mathsf{SpanTL}$ admits an efficient approximation
scheme by using a recent approximability result in the context of tree
automata, and then place the problems of interest in $\mathsf{SpanTL}$.

inconsistency; consistent query answering; operational semantics; primary
keys; conjunctive queries; approximation schemes

††ccs: Information systems Data management systems

##  1\. Introduction

Operational consistent query answering (CQA) is a recent framework, introduced
in 2018 (Calautti et al., 2018), that allows us to compute conceptually
meaningful answers to queries posed over inconsistent databases, that is,
databases that do not conform to their specifications given in the form of
constraints, and it is based on revised definitions of repairs and consistent
answers. In particular, the main idea underlying this new framework is to
replace the declarative approach to repairs, introduced in the late 1990s by
Arenas, Bertossi, and Chomicki (Arenas et al., 1999), and adopted by numerous
works (see, e.g., (Calautti et al., 2019, 2021; Calautti et al., 2022a; Fuxman
et al., 2005; Fuxman and Miller, 2007; Geerts et al., 2015; Koutris and Suciu,
2014; Koutris and Wijsen, 2015, 2021; Maslowski and Wijsen, 2013)), with an
operational one that explains the process of constructing a repair. In other
words, we can iteratively apply operations (e.g., fact deletions), starting
from an inconsistent database, until we reach a database that is consistent
w.r.t. the given set of integrity constraints. This gives us the flexibility
of choosing the probability with which we apply an operation, which in turn
allows us to calculate the probability of an operational repair, and thus, the
probability with which an answer is entailed. Probabilities can be naturally
assigned to operations in many scenarios leading to inconsistencies. This is
illustrated using the following example from (Calautti et al., 2018).

###### Example 1.1.

Consider a data integration scenario that results in a database containing the
facts ${\rm Emp}(1,{\rm Alice})$ and ${\rm Emp}(1,{\rm Tom})$ that violate the
constraint that the first attribute of the relation name ${\rm Emp}$ (the id)
is a key. Suppose we have a level of trust in each of the sources; say we
believe that each is 50% reliable. With probability $0.5\cdot 0.5=0.25$ we do
not trust either tuple and apply the operation that removes both facts. With
probability $(1-0.25)/2=0.375$ we remove either ${\rm Emp}(1,{\rm Alice})$ or
${\rm Emp}(1,{\rm Tom})$. Therefore, we have three repairs, each with its
probability: the empty repair with probability $0.25$, and the repairs
consisting of ${\rm Emp}(1,{\rm Alice})$ or ${\rm Emp}(1,{\rm Tom})$ with
probability $0.375$. Note that the standard CQA approach from (Arenas et al.,
1999) only allows the removal of one of the two facts (with equal probability
$0.5$). It somehow assumes that we trust at least one of the sources, even
though they are conflicting.

As recently discussed in (Calautti et al., 2022b), a natural way of choosing
the probabilities assigned to operations is to follow the uniform probability
distribution over a reasonable space. The obvious candidates for such a space
are the set of operational repairs and the set of sequences of operations that
lead to a repair (note that multiple such sequences can lead to the same
repair). This led to the so-called uniform operational CQA. Let us note that
in the case of uniform operational repairs (resp., sequences of operations),
the probability with which an answer is entailed is essentially the percentage
of operational repairs (resp., sequences of operations leading to repairs)
that entail the answer in question. We know from (Calautti et al., 2022b)
that, although computing the above percentages is $\sharp$P-hard, they can be
efficiently approximated via a fully polynomial-time randomized approximation
scheme (FPRAS) when we focus on primary keys, conjunctive queries, and the
query is fixed (i.e., in data complexity). However, it has been left open
whether such efficient approximations exist when the query is part of the
input (i.e., in combined complexity). Closing this problem is the main goal of
this work.

###  1.1. Our Contributions

We show that the problem of computing the percentage of operational repairs,
as well as of sequences of operations leading to repairs, that entail an
answer to the given query admits an FPRAS in combined complexity when we focus
on self-join-free conjunctive queries of bounded generalized hypertreewidth.
We further show that it is unlikely to have efficient approximation schemes
once we give up one of the adopted syntactic restrictions, i.e., self-join-
freeness or bounding the generelized hypertreewidth. Note that an analogous
approximability result has been recently established for the problem of
computing the probability of an answer to a conjunctive query over a tuple-
independent probabilistic database (van Bremen and Meel, 2023). Towards our
approximability results, our main technical task is to show that computing the
numerators of the ratios in question admits an FPRAS since we know from
(Calautti et al., 2022b) that the denominators can be computed in polynomial
time. To this end, we introduce a novel counting complexity class, called
$\mathsf{SpanTL}$, establish that each problem in $\mathsf{SpanTL}$ admits an
FPRAS, and then place the problems of interest in $\mathsf{SpanTL}$. The
complexity class $\mathsf{SpanTL}$, apart from being interesting in its own
right, will help us to obtain the desired approximation schemes for the
problems of interest in a more modular and comprehensible way.

The class $\mathsf{SpanTL}$ relies on alternating Turing machines with output.
Although the notion of output is clear for (non-)deterministic Turing
machines, it is rather uncommon to talk about the output of an alternating
Turing machine. To the best of our knowledge, alternating Turing machines with
output have not been considered before. We define an output of an alternating
Turing machine $M$ on input $w$ as a node-labeled rooted tree, where its nodes
are labeled with (finite) strings over the alphabet of the machine, obtained
from a computation of $M$ on $w$. We then define $\mathsf{SpanTL}$ as the
class that collects all the functions that compute the number of distinct
accepted outputs of an alternating Turing machine with output with some
resource usage restrictions. For establishing that each problem in
$\mathsf{SpanTL}$ admits an FPRAS, we exploit a recent approximability result
in the context of automata theory, that is, the problem $\sharp\mathsf{NFTA}$
of counting the number of trees of a certain size accepted by a non-
deterministic finite tree automaton admits an FPRAS (Arenas et al., 2021b). In
fact, we reduce each function in $\mathsf{SpanTL}$ to $\sharp\mathsf{NFTA}$.
Finally, for placing our problems in $\mathsf{SpanTL}$, we build upon an idea
from (van Bremen and Meel, 2023) on how the generalized hypertree
decomposition of the query can be used to encode a database as a node-labeled
rooted tree. Note, however, that transferring the idea from (van Bremen and
Meel, 2023) to our setting requires a non-trivial adaptation since we need to
encode operational repairs and sequences of operations.

At this point, we would like to stress that $\mathsf{SpanTL}$ generalizes the
known complexity class $\mathsf{SpanL}$, which collects all the functions that
compute the number of distinct accepted outputs of a non-deterministic
logspace Turing machine with output (Àlvarez and Jenner, 1993). We know that
each problem in $\mathsf{SpanL}$ admits an FPRAS (Arenas et al., 2021a), but
our problems of interest are unlikely to be in $\mathsf{SpanL}$ (unless
$\mathsf{NL}=\mathsf{LOGCFL}$). This is because their decision version, which
asks whether the number that we want to compute is greater than zero, is
$\mathsf{LOGCFL}$-complete (this is implicit in (Gottlob et al., 2002)),
whereas the decision version of each counting problem in $\mathsf{SpanL}$ is
in $\mathsf{NL}$.

##  2\. Preliminaries

We assume the disjoint countably infinite sets $\mathbf{C}$ and $\mathbf{V}$
of constants and variables, respectively. For $n>0$, let $[n]$ be the set
$\\{1,\ldots,n\\}$.

#### Relational Databases.

A (relational) schema $\mathbf{S}$ is a finite set of relation names with
associated arity; we write $R/n$ to denote that $R$ has arity $n>0$. A fact
over $\mathbf{S}$ is an expression of the form $R(c_{1},\ldots,c_{n})$, where
$R/n\in\mathbf{S}$ and $c_{i}\in\mathbf{C}$ for each $i\in[n]$. A database $D$
over $\mathbf{S}$ is a finite set of facts over $\mathbf{S}$. The active
domain of $D$, denoted $\mathsf{dom}(D)$, is the set of constants occurring in
$D$.

#### Key Constraints.

A key constraint (or simply key) $\kappa$ over a schema $\mathbf{S}$ is an
expression $\mathsf{key}(R)=A$, where $R/n\in\mathbf{S}$ and $A\subseteq[n]$.
Such an expression is called an $R$-key. Given an $n$-tuple of constants
$\bar{t}=(c_{1},\ldots,c_{n})$ and a set
$A=\\{i_{1},\ldots,i_{m}\\}\subseteq[n]$, for some $m\in[n]$, we write
$\bar{t}[A]$ for the tuple $(c_{i_{1}},\ldots,c_{i_{m}})$, i.e., the
projection of $\bar{t}$ over the positions in $A$. A database $D$ satisfies
$\kappa$, denoted $D\models\kappa$, if, for every two facts
$R(\bar{t}),R(\bar{s})\in D$, $\bar{t}[A]=\bar{s}[A]$ implies
$\bar{t}=\bar{s}$. We say that $D$ is consistent w.r.t. a set $\Sigma$ of
keys, written $D\models\Sigma$, if $D\models\kappa$ for each
$\kappa\in\Sigma$; otherwise, it is inconsistent w.r.t. $\Sigma$. In this
work, we focus on sets of primary keys, i.e., sets of keys that, for each
predicate $R$ of the underlying schema, have at most one $R$-key.

#### Conjunctive Queries.

A (relational) atom $\alpha$ over a schema $\mathbf{S}$ is an expression of
the form $R(t_{1},\ldots,t_{n})$, where $R/n\in\mathbf{S}$ and
$t_{i}\in\mathbf{C}\cup\mathbf{V}$ for each $i\in[n]$. A conjunctive query
(CQ) $Q$ over $\mathbf{S}$ is an expression of the form
$\textrm{Ans}(\bar{x})\ \text{:-}\
R_{1}(\bar{y}_{1}),\ldots,R_{n}(\bar{y}_{n})$, where $R_{i}(\bar{y}_{i})$, for
$i\in[n]$, is an atom over $\mathbf{S}$, $\bar{x}$ are the answer variables of
$Q$, and each variable in $\bar{x}$ is mentioned in $\bar{y}_{i}$ for some
$i\in[n]$. We may write $Q(\bar{x})$ to indicate that $\bar{x}$ are the answer
variables of $Q$. When $\bar{x}$ is empty, $Q$ is called Boolean. Moreover,
when $Q$ mentions every relation name of $\mathbf{S}$ at most once it is
called self-join-free and we write $\mathsf{SJF}$ for the class of self-join-
free CQs. The semantics of CQs is given via homomorphisms. Let
$\mathsf{var}(Q)$ and $\mathsf{const}(Q)$ be the set of variables and
constants in $Q$, respectively. A homomorphism from a CQ $Q$ of the form
$\textrm{Ans}(\bar{x})\ \text{:-}\
R_{1}(\bar{y}_{1}),\ldots,R_{n}(\bar{y}_{n})$ to a database $D$ is a function
$h:\mathsf{var}(Q)\cup\mathsf{const}(Q)\rightarrow\mathsf{dom}(D)$, which is
the identity over $\mathbf{C}$, such that $R_{i}(h(\bar{y}_{i}))\in D$ for
each $i\in[n]$. A tuple $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$ is an answer
to $Q$ over $D$ if there is a homomorphism $h$ from $Q$ to $D$ with
$h(\bar{x})=\bar{c}$. Let $Q(D)$ be the answers to $Q$ over $D$. For Boolean
CQs, we write $D\models Q$, and say that $D$ entails $Q$, if $()\in Q(D)$.

A central class of CQs, which is crucial for our work, is that of bounded
generalized hypertreewidth. The definition of generalized hypertreewidth
relies on the notion of tree decomposition. A _tree decomposition_ of a CQ $Q$
of the form $\textrm{Ans}(\bar{x})\ \text{:-}\
R_{1}(\bar{y}_{1}),\ldots,R_{n}(\bar{y}_{n})$ is a pair $(T,\chi)$, where
$T=(V,E)$ is a tree and $\chi$ is a labeling function $V\rightarrow
2^{\mathsf{var}(Q)\setminus\bar{x}}$, i.e., it assigns a subset of
$\mathsf{var}(Q)\setminus\bar{x}$ to each node of $T$, such that (1) for each
$i\in[n]$, there exists $v\in V$ such that $\chi(v)$ contains all the
variables in $\bar{y}_{i}\setminus\bar{x}$, and (2) for each
$t\in\mathsf{var}(Q)\setminus\bar{x}$, the set $\\{v\in V\mid t\in\chi(v)\\}$
induces a connected subtree of $T$; the second condition is generally known as
the connectedness condition. A generalized hypertree decomposition of $Q$ is a
triple $(T,\chi,\lambda)$, where $(T,\chi)$ is a tree decomposition of $Q$
and, assuming $T=(V,E)$, $\lambda$ is a labeling function that assigns a
subset of $\\{R_{1}(\bar{y}_{1}),\ldots,R_{n}(\bar{y}_{n})\\}$ to each node of
$T$ such that, for each $v\in V$, the terms in $\chi(v)$ are “covered” by the
atoms in $\lambda(v)$, i.e.,
$\chi(v)\subseteq\bigcup_{R(t_{1},\ldots,t_{n})\in\lambda(v)}\\{t_{1},\ldots,t_{n}\\}$.
The width of $(T,\chi,\lambda)$ is the number $\max_{v\in
V}\\{|\lambda(v)|\\}$, i.e., the maximal size of a set of the form
$\lambda(v)$ over all nodes $v$ of $T$. The generalized hypertreewidth of $Q$
is the minimum width over all its generalized hypertree decompositions. For
$k>0$, we denote by $\mathsf{GHW}_{k}$ the class of CQs of generalized
hypertreewidth $k$. Recall that $\mathsf{GHW}_{1}$ coincides with the class of
acyclic CQs.

##  3\. Uniform Operational CQA

We recall the basic notions underlying the operational approach to consistent
query answering, focusing on keys, as defined in (Calautti et al., 2018). We
then use those notions to recall the recent uniform operational approach to
consistent query answering considered in (Calautti et al., 2022b).

#### Operations.

The notion of operation is the building block of the operational approach,
which essentially removes some facts from the database in order to resolve a
conflict. As usual, we write $\mathcal{P}(S)$ for the powerset of a set $S$.

###### Definition 3.1 (Operation).

For a database $D$, a $D$-operation is a function
$\mathit{op}:\mathcal{P}(D)\rightarrow\mathcal{P}(D)$ such that, for some non-
empty set $F\subseteq D$, for every $D^{\prime}\in\mathcal{P}(D)$,
$\mathit{op}(D^{\prime})=D^{\prime}\setminus F$. We write $-F$ to refer to
this operation. We say that $-F$ is $(D^{\prime},\Sigma)$-justified, where
$D^{\prime}\subseteq D$ and $\Sigma$ is a set of keys, if
$F\subseteq\\{f,g\\}\subseteq D^{\prime}$ and $\\{f,g\\}\not\models\Sigma$.

The operations $-F$ depend on the database $D$ as they are defined over $D$.
Since $D$ will be clear from the context, we may refer to them simply as
operations, omitting $D$. The main idea of the operational approach to CQA is
to iteratively apply justified operations, starting from an inconsistent
database $D$, until we reach a database $D^{\prime}\subseteq D$ that is
consistent w.r.t. the given set $\Sigma$ of keys. Note that justified
operations do not try to minimize the number of atoms that need to be removed.
As argued in (Calautti et al., 2018), a set of facts that collectively
contributes to a key violation should be considered as a justified operation
during the iterative repairing process since we do not know a priori which
atoms should be deleted.

#### Repairing Sequences and Operational Repairs.

The main idea of the operational approach discussed above is formalized via
the notion of repairing sequence. Consider a database $D$ and a set $\Sigma$
of keys. Given a sequence $s=(\mathit{op}_{i})_{1\leq i\leq n}$ of
$D$-operations, we define $D_{0}^{s}=D$ and
$D_{i}^{s}=\mathit{op}_{i}(D_{i-1}^{s})$ for $i\in[n]$, that is, $D_{i}^{s}$
is obtained by applying to $D$ the first $i$ operations of $s$.

###### Definition 3.2 (Repairing Sequence).

Consider a database $D$ and a set $\Sigma$ of keys. A sequence of
$D$-operations $s=(\mathit{op}_{i})_{1\leq i\leq n}$ is called
$(D,\Sigma)$-repairing if, for every $i\in[n]$, $\mathit{op}_{i}$ is
$(D_{i-1}^{s},\Sigma)$-justified. Let $\mathsf{RS}(D,\Sigma)$ be the set of
all $(D,\Sigma)$-repairing sequences.

It is easy to verify that the length of a $(D,\Sigma)$-repairing sequence is
linear in the size of $D$ and that the set $\mathsf{RS}(D,\Sigma)$ is finite.
For a $(D,\Sigma)$-repairing sequence $s=(\mathit{op}_{i})_{1\leq i\leq n}$,
we define its result as the database $s(D)=D_{n}^{s}$ and call it complete if
$s(D)\models\Sigma$. Let $\mathsf{CRS}(D,\Sigma)$ be the set of all complete
$(D,\Sigma)$-repairing sequences. We can now introduce the central notion of
operational repair.

###### Definition 3.3 (Operational Repair).

Let $D$ be a database over a schema $\mathbf{S}$ and $\Sigma$ a set of keys
over $\mathbf{S}$. An operational repair of $D$ w.r.t. $\Sigma$ is a database
$D^{\prime}$ such that $D^{\prime}=s(D)$ for some
$s\in\mathsf{CRS}(D,\Sigma)$. Let $\mathsf{ORep}(D,\Sigma)$ be the set of all
operational repairs of $D$ w.r.t. $\Sigma$.

#### Uniform Operational CQA.

We can now recall the uniform operational approach to consistent query
answering introduced in (Calautti et al., 2022b) and define the main problems
of interest. The goal is to provide a way to measure how certain we are that a
candidate answer is indeed a consistent answer. A natural idea is to compute
the percentage of operational repairs that entail a candidate answer, which
essentially measures how often a candidate answer is an answer to the query if
we evaluate it over all operational repairs. Here, we consider all the
operational repairs to be equally important; hence the term “uniform”. This
leads to the notion of repair relative frequency. For a database $D$, a set
$\Sigma$ of keys, a CQ $Q(\bar{x})$, and a tuple
$\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$, the repair relative frequency of
$\bar{c}$ w.r.t. $D$, $\Sigma$, and $Q$ is

$\displaystyle\mathsf{RF}^{\mathsf{ur}}(D,\Sigma,Q,\bar{c})$ $\displaystyle=$
$\displaystyle\frac{|\\{D^{\prime}\in\mathsf{ORep}(D,\Sigma)\mid\bar{c}\in
Q(D^{\prime})\\}|}{|\mathsf{ORep}(D,\Sigma)|}.$

Considering all the operational repairs to be equally important is a self-
justified choice. However, as discussed in (Calautti et al., 2022b), this does
not take into account the support in terms of the repairing process. In other
words, an operational repair obtained by very few repairing sequences is
equally important as an operational repair obtained by several repairing
sequences. This is rectified by the notion of sequence relative frequency,
which is the percentage of repairing sequences that lead to an operational
repair that entails a candidate answer. For a database $D$, a set $\Sigma$ of
keys, a CQ $Q(\bar{x})$, and $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$, the
sequence relative frequency of $\bar{c}$ w.r.t. $D$, $\Sigma$, and $Q$ is

$\displaystyle\mathsf{RF}^{\mathsf{us}}(D,\Sigma,Q,\bar{c})$ $\displaystyle=$
$\displaystyle\frac{|\\{s\in\mathsf{CRS}(D,\Sigma)\mid\bar{c}\in
Q(s(D))\\}|}{|\mathsf{CRS}(D,\Sigma)|}.$

###  3.1. Problems of Interest

The problems of interest in the context of uniform operational CQA, focusing
on primary keys, are defined as follows: for
$\star\in\\{\mathsf{ur},\mathsf{us}\\}$ and a class $\mathsf{Q}$ of CQs (e.g.,
$\mathsf{SJF}$ or $\mathsf{GHW}_{k}$ for $k>0$),

PROBLEM : $\mathsf{OCQA}^{\star}[\mathsf{Q}]$ INPUT : A database $D$, a set
$\Sigma$ of primary keys, a query $Q(\bar{x})$ from $\mathsf{Q}$, a tuple
$\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$. OUTPUT :
$\mathsf{RF}^{\star}(D,\Sigma,Q,\bar{c})$.

We can show that the above problems are hard, even for self-join-free CQs of
bounded generalized hypertreewidth. In particular, with
$\mathsf{SJF}\cap\mathsf{GHW}_{k}$ for $k>0$ being the class of self-join-free
CQs of generalized hypertreewidth $k$, we show that:

###### Theorem 3.4.

For every $k>0$, $\mathsf{OCQA}^{\star}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$ is
$\sharp$P-hard, where $\star\in\\{\mathsf{ur},\mathsf{us}\\}$.

With the above intractability result in place, the question is whether the
problems of interest are approximable, i.e., whether the target ratio can be
approximated via a fully polynomial-time randomized approximation scheme
(FPRAS). An FPRAS for $\mathsf{OCQA}^{\star}[\mathsf{Q}]$, where
$\star\in\\{\mathsf{ur},\mathsf{us}\\}$, is a randomized algorithm
$\mathsf{A}$ that takes as input a database $D$, a set $\Sigma$ of primary
keys, a query $Q(\bar{x})$ from $\mathsf{Q}$, a tuple
$\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$, $\epsilon>0$ and $0<\delta<1$, runs
in polynomial time in $||D||$, $||\Sigma||$, $||Q||$, $||\bar{c}||$,111As
usual, $||o||$ denotes the size of the encoding of a syntactic object $o$.
$1/\epsilon$ and $\log(1/\delta)$, and produces a random variable
$\mathsf{A}(D,\Sigma,Q,\bar{c},\epsilon,\delta)$ such that $\text{\rm
Pr}(|\mathsf{A}(D,\Sigma,Q,\bar{c},\epsilon,\delta)-\mathsf{RF}^{\star}(D,\Sigma,Q,\bar{c})|\
\leq\ \epsilon\cdot\mathsf{RF}^{\star}(D,\Sigma,Q,\bar{c}))\ \geq\ 1-\delta.$
It turns out that the answer to the above question is negative, even if we
focus on self-join-free CQs or CQs of bounded generalized hypertreewidth,
under the widely accepted complexity assumption that ${\rm RP}\neq{\rm NP}$;
RP is the complexity class of problems that are efficiently solvable via a
randomized algorithm with a bounded one-sided error (Aror and Barak, 2009).

###### Theorem 3.5.

Unless ${\rm RP}={\rm NP}$, for $\star\in\\{\mathsf{ur},\mathsf{us}\\}$,

  1. (1)

There is no FPRAS for $\mathsf{OCQA}^{\star}[\mathsf{SJF}]$.

  2. (2)

For every $k>0$, there is no FPRAS for
$\mathsf{OCQA}^{\star}[\mathsf{GHW}_{k}]$.

After a quick inspection of the proof of the above result, one can verify that
the CQ used in the proof of item (1) is of unbounded generalized
hypertreewidth, whereas the CQ used in the proof of item (2) is with self-
joins. Hence, the key question that comes up is whether we can provide an
FPRAS if we focus on self-join-free CQs of bounded generalized hypertreewidth.
The main result of this work provides an affirmative answer to this question:

###### Theorem 3.6.

For every $k>0$, $\mathsf{OCQA}^{\star}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$
admits an FPRAS, where $\star\in\\{\mathsf{ur},\mathsf{us}\\}$.

###  3.2. Plan of Attack

For a database $D$ and a set $\Sigma$ of primary keys, both
$|\mathsf{ORep}(D,\Sigma)|$ and $|\mathsf{CRS}(D,\Sigma)|$, that is, the
denominators of the ratios in question, can be computed in polynomial time
(Calautti et al., 2022b). Therefore, to establish Theorem 3.6, it suffices to
show that the numerators of the ratios can be efficiently approximated. In
fact, it suffices to show that the following auxiliary counting problems admit
an FPRAS. For $k>0$,

PROBLEM : $\sharp\mathsf{Repairs}[k]$ INPUT : A database $D$, a set $\Sigma$
of primary keys, a query $Q(\bar{x})$ from $\mathsf{SJF}$, a generalized
hypetree decomposition of $Q$ of width $k$,
$\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$. OUTPUT :
$|\\{D^{\prime}\in\mathsf{ORep}(D,\Sigma)\mid\bar{c}\in Q(D^{\prime})\\}|$.

PROBLEM : $\sharp\mathsf{Sequences}[k]$ INPUT : A database $D$, a set $\Sigma$
of primary keys, a query $Q(\bar{x})$ from $\mathsf{SJF}$, a generalized
hypetree decomposition of $Q$ of width $k$,
$\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$. OUTPUT :
$|\\{s\in\mathsf{CRS}(D,\Sigma)\mid\bar{c}\in Q(s(D))\\}|$.

Note that the above problems take as input, together with the CQ, a
generalized hypertree decomposition of it, whereas the main problems of
interest $\mathsf{OCQA}^{\star}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$, for
$\star\in\\{\mathsf{ur},\mathsf{us}\\}$, take as input only the CQ. Despite
this mismatch, the existence of an FPRAS for $\sharp\mathsf{Repairs}[k]$ and
$\sharp\mathsf{Sequences}[k]$, for every $k>0$, implies Theorem 3.6. This is
due to the well-known fact that, given a CQ $Q$ from $\mathsf{GHW}_{k}$,
although it is hard to compute a generalized hypertree decomposition of $Q$ of
width $k$, we can compute in polynomial time a generalized hypertree
decomposition of $Q$ of width $\ell$, where $k\leq\ell\leq 3k+1$ (Adler et
al., 2007; Gottlob et al., 2002). Hence, our task is to show that
$\sharp\mathsf{Repairs}[k]$ and $\sharp\mathsf{Sequences}[k]$, for $k>0$,
admit an FPRAS. To this end, we are going to introduce the novel counting
complexity class $\mathsf{SpanTL}$, show that each counting problem in
$\mathsf{SpanTL}$ admits an FPRAS, and place $\sharp\mathsf{Repairs}[k]$ and
$\sharp\mathsf{Sequences}[k]$, for every $k>0$, in $\mathsf{SpanTL}$.

##  4\. A Novel Complexity Class

We proceed to introduce the counting complexity class $\mathsf{SpanTL}$
($\mathsf{T}$ stands for tree and $\mathsf{L}$ for logspace). Its definition
relies on alternating Turing machines with output. We define an output of an
alternating Turing machine $M$ on input $w$ as a node-labeled rooted tree,
where its nodes are labeled with (finite) strings over the alphabet of the
machine, obtained from a computation of $M$ on $w$.

###  4.1. Alternating Turing Machines with Output

We consider alternating Turing machines with a read-only input tape, a read-
write working tape, and a write-only one-way labeling tape. Furthermore, some
of the states of the machine are classified as labeling states. The labeling
tape and states, which are rather non-standard in the definition of a Turing
machine, should be understood as auxiliary constructs that allow us to build
the strings that label the nodes of an output. In particular, we use a
standard alternating Turing machine that, whenever it enters a labeling state,
it produces a node of the output with label the content of the labeling tape,
which is then erased. The formal definition follows.

###### Definition 4.1 (Model).

An _alternating Turing machine with output_ (ATO) $M$ is a tuple
$(S,\Lambda,s_{\text{\rm init}},s_{\text{\rm accept}},s_{\text{\rm
reject}},S_{\exists},S_{\forall},S_{L},\delta),$ where

  * -

$S$ is the finite set of states of $M$,

  * -

$\Lambda$ is a finite set of symbols, the alphabet of $M$, including the
symbols $\bot$ (blank symbol) and $\triangleright$ (left marker),

  * -

$s_{\text{\rm init}}\in S$ is the initial state of $M$,

  * -

$s_{\text{accept}},s_{\text{reject}}\in S$ are the accepting and rejecting
states of $M$, respectively,

  * -

$S_{\exists},S_{\forall}$ are the existential and universal states of $M$,
respectively, and they form a partition of $S\setminus\\{s_{\text{\rm
accept}},s_{\text{\rm reject}}\\}$,

  * -

$S_{L}\subseteq S$ are the labeling states of $M$ including $s_{\text{\rm
init}}$,

  * -

$\delta:(S\setminus\\{s_{\text{\rm accept}},s_{\text{\rm
reject}}\\})\times\Lambda\times\Lambda\rightarrow\mathcal{P}(S\times\\{-1,0,+1\\}\times\\{-1,0,+1\\}\times\Lambda\times\Lambda^{*})$
is the transition function of $M$.

Fix an ATO $M=(S,\Lambda,s_{\text{\rm init}},s_{\text{\rm
accept}},s_{\text{\rm reject}},S_{\exists},S_{\forall},S_{L},\delta)$. A
configuration of $M$ is a tuple $C=(s,x,y,z,h_{x},h_{y})$, where $s\in S$,
$x,y,z$ are strings of $\Lambda^{*}$, and $h_{x},h_{y}$ are positive integers.
If $M$ is in configuration $C$, then the input (resp., working, labeling) tape
contains the infinite string $x\bot\bot\cdots$ (resp., $y\bot\bot\cdots$,
$z\bot\bot\cdots$) and the cursor of the input (resp., working) tape points to
the cell $h_{x}$, (resp., $h_{y}$). As usual, we use the left marker, which
means that $x$ and $y$ are always starting with $\triangleright$. Moreover,
$\delta$ is restricted in such a way that $\triangleright$ occurs exactly once
in $x$ and $y$ and always as the first symbol.

Assume now that $M$ is in configuration $C=(s,x,y,z,h_{x},h_{y})$, where
$x[h_{x}]=\alpha$ and $y[h_{y}]=\beta$, and assume that
$\delta(s,\alpha,\beta)=\\{(s_{i},d_{i},d_{i}^{\prime},\beta_{i},z_{i})\\}_{i\in[n]}$
for some $n>0$. Then, in one step, $M$ enters the configurations
$C_{i}=(s_{i},x,y^{\prime}_{i},z_{i}^{\prime},h_{x}^{\prime},h_{y^{\prime}_{i}})$
for $i\in[n]$, where $y^{\prime}_{i}$ is obtained from $y$ by replacing
$y[h_{y}]=\beta$ with $\beta_{i}$, $z_{i}^{\prime}=z_{i}$ (resp.,
$z_{i}^{\prime}=z\cdot z_{i}$) if $s\in S_{L}$ (resp., $s\not\in S_{L}$),
$h_{x}^{\prime}=h_{x}+d_{i}$, and $h_{y^{\prime}_{i}}=h_{y}+d_{i}^{\prime}$.
In this case we write $C\rightarrow_{M}\\{C_{1},\ldots,C_{n}\\}$. Note that
the cursors of the input and the working tapes cannot move left of the symbol
$\triangleright$. This is achieved by restricting the transition function.

The ATO $M$ receives an input $w=w_{1}\cdots
w_{n}\in(\Lambda\setminus\\{\bot,\triangleright\\})^{*}$. The initial
configuration of $M$ on input $w$ is $(s_{\text{\rm init}},\triangleright
w,\triangleright,\epsilon,1,1)$. We call a configuration of $M$ accepting
(resp., rejecting) if its state is $s_{\text{\rm accept}}$ (resp.,
$s_{\text{\rm reject}}$). We further call $C$ existential (resp., universal,
labeling) if its state belongs to $S_{\exists}$ (resp., $S_{\forall}$,
$S_{L}$). We proceed to define the notion of computation of an ATO.

###### Definition 4.2 (Computation).

A computation of $M$ on input
$w\in(\Lambda\setminus\\{\bot,\triangleright\\})^{*}$ is a finite node-labeled
rooted tree $T=(V,E,\lambda)$, where $\lambda$ assigns to the nodes of $T$
configurations of $M$, such that:

  1. -

if $v\in V$ is the root node of $T$, then $\lambda(v)$ is the initial
configuration of $M$ on input $w$,

  2. -

if $v\in V$ is a leaf node of $T$, then $\lambda(v)$ is either an accepting or
a rejecting configuration of $M$, and

  3. -

if $v\in V$ is a non-leaf node of $T$ with
$\lambda(v)\rightarrow_{M}\\{C_{1},\ldots,C_{n}\\}$ for some $n>0$, then:
$\lambda(v)$ is existential implies $v$ has exactly one child $u\in V$ with
$\lambda(u)=C_{i}$ for some $i\in[n]$, and $\lambda(v)$ is universal implies
$v$ has $n$ children $u_{1},\ldots,u_{n}\in V$ with $\lambda(u_{i})=C_{i}$ for
each $i\in[n]$.

We say that $T$ is accepting if all its leaves are labeled with accepting
configurations of $M$; otherwise, it is rejecting.

It remains to define the notion of output of $M$. To this end, we need some
auxiliary notions. A path $v_{1},\ldots,v_{n}$, for some $n\geq 0$, in a
computation $T=(V,E,\lambda)$ of $M$ is called labeled-free if
$\lambda(v_{i})$ is not a labeling configuration for each $i\in[n]$. The
output of a computation $T=(V,E,\lambda)$ of $M$ on input
$w\in(\Lambda\setminus\\{\bot,\triangleright\\})^{*}$ is the node-labeled
rooted tree $O=(V^{\prime},E^{\prime},\lambda^{\prime})$, where
$\lambda^{\prime}:V^{\prime}\rightarrow\Lambda^{*}$, such that:

  * -

$V^{\prime}=\\{v\in V\mid\lambda(v)\text{ is a labeling configuration of
}M\\}$,

  * -

$E^{\prime}=\\{(u,v)\mid u\text{ reaches }v\text{ in }T\text{ via a
}\text{labeled-free path}\\}$,

  * -

for every $v^{\prime}\in V^{\prime}$, $\lambda^{\prime}(v^{\prime})=z$
assuming that $\lambda(v^{\prime})$ is of the form
$(\cdot,\cdot,\cdot,z,\cdot,\cdot)$.

We are now ready to define the output of $M$ on a certain input.

###### Definition 4.3 (Output).

A node-labeled rooted tree $O$ is an output of $M$ on input $w$ if $O$ is the
output of some computation $T$ of $M$ on input $w$. We further call $O$ a
valid output if $T$ is accepting.

###  4.2. The Complexity Class $\mathsf{SpanTL}$

We now proceed to define the complexity class $\mathsf{SpanTL}$ and establish
that each of its problems admits an efficient approximation scheme. To this
end, we need to introduce the notion of well-behaved ATO, that is, an ATO with
some resource usage restrictions. We require (i) each computation to be of
polynomial size, (ii) the working and labeling tapes to use logarithmic space,
and (iii) each labeled-free path to have a bounded number of universal
configurations.

###### Definition 4.4 (Well-behaved ATO).

Consider an ATO $M=(S,\Lambda,s_{\text{\rm init}},s_{\text{\rm
accept}},s_{\text{\rm reject}},S_{\exists},S_{\forall},S_{L},\delta)$. We call
$M$ well-behaved if there is a polynomial function $\text{\rm
pol}:\mathbb{N}\rightarrow\mathbb{N}$ and an integer $k\geq 0$ such that, for
every string $w=w_{1}\cdots
w_{n}\in(\Lambda\setminus\\{\bot,\triangleright\\})^{*}$ and computation
$T=(V,E,\lambda)$ of $M$ on input $w$, the following hold:

  * -

$|V|\in O(\text{\rm pol}(n))$,

  * -

for each $v\in V$ with $\lambda(v)$ being of the form
$(\cdot,\cdot,y,z,\cdot,\cdot)$, $|y|,|z|\in O(\log(n))$, and

  * -

for every labeled-free path $v_{1},\ldots,v_{m}$ of $T$, for $m\geq 0$,
$|\\{v_{i}\mid i\in[m]~{}~{}\text{and}~{}~{}\lambda(v_{i})\text{ is
universal}\\}|\leq k$.

Let
$\mathsf{span}_{M}:(\Lambda\setminus\\{\bot,\triangleright\\})^{*}\rightarrow\mathbb{N}$
be the function that assigns to each
$w\in(\Lambda\setminus\\{\bot,\triangleright\\})^{*}$ the number of distinct
valid outputs of $M$ on input $w$, i.e., $\mathsf{span}_{M}(w)=|\\{T\mid
T\text{ is a valid output of }M\text{ on }w\\}|$. Note that whenever we use
$\mathbb{N}$ as the codomain of such a function, we assume that
$0\in\mathbb{N}$. We finally define the complexity class

$\mathsf{SpanTL}\ =\ \left\\{\mathsf{span}_{M}\mid M\text{ is a well-behaved
ATO}\right\\}.$

A property of $\mathsf{SpanTL}$, which will be useful for our later
development, is the fact that it is closed under logspace reductions. This
means that, given two functions $f:\Lambda_{1}^{*}\rightarrow\mathbb{N}$ and
$g:\Lambda_{2}^{*}\rightarrow\mathbb{N}$, for some alphabets $\Lambda_{1}$ and
$\Lambda_{2}$, if there is a logspace computable function
$h:\Lambda_{1}^{*}\rightarrow\Lambda_{2}^{*}$ with $f(w)=g(h(w))$ for all
$w\in\Lambda_{1}^{*}$, and $g$ belongs to $\mathsf{SpanTL}$, then $f$ also
belongs to $\mathsf{SpanTL}$.

###### Proposition 4.5.

$\mathsf{SpanTL}$ is closed under logspace reductions.

Another key property of $\mathsf{SpanTL}$, which is actually the crucial one
that we need for establishing Theorem 3.6, is that each of its problems admits
an FPRAS. The notion of FPRAS for an arbitrary function
$f:\Lambda^{*}\rightarrow\mathbb{N}$, for some alphabet $\Lambda$, is defined
in the obvious way, i.e., an FPRAS for $f$ is a randomized algorithm
$\mathsf{A}$ that takes as input $w\in\Lambda^{*}$, $\epsilon>0$ and
$0<\delta<1$, runs in polynomial time in $|w|$, $1/\epsilon$ and
$\log(1/\delta)$, and produces a random variable
$\mathsf{A}(w,\epsilon,\delta)$ such that $\text{\rm
Pr}\left(|\mathsf{A}(w,\epsilon,\delta)-f(w)|\ \leq\ \epsilon\cdot
f(w)\right)\ \geq\ 1-\delta.$

###### Theorem 4.6.

Every function $f\in\mathsf{SpanTL}$ admits an FPRAS.

To establish the above result we exploit a recent approximability result in
the context of automata theory, that is, the problem of counting the number of
trees of a certain size accepted by a non-deterministic finite tree automaton
admits an FPRAS (Arenas et al., 2021b). Hence, for establishing Theorem 4.6,
we reduce in polynomial time each function in $\mathsf{SpanTL}$ to the above
counting problem for tree automata.

##  5\. Combined Approximations

As discussed in Section 3, for establishing Theorem 3.6, it suffices to show
that, for every $k>0$, $\sharp\mathsf{Repairs}[k]$ and
$\sharp\mathsf{Sequences}[k]$ admit an FPRAS. To this end, by Theorem 4.6, it
suffices to show that

###### Theorem 5.1.

For every $k>0$, the following hold:

  1. (1)

$\sharp\mathsf{Repairs}[k]$ is in $\mathsf{SpanTL}$.

  2. (2)

$\sharp\mathsf{Sequences}[k]$ is in $\mathsf{SpanTL}$.

To prove the above result, for $k>0$, we need to devise two procedures, which
can be implemented as well-behaved ATOs $M_{R}^{k}$ and $M_{S}^{k}$,
respectively, that take as input a database $D$, a set $\Sigma$ of primary
keys, a CQ $Q(\bar{x})$ from $\mathsf{SJF}$, a generalized hypetree
decomposition $H$ of $Q$ of width $k>0$, and a tuple
$\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$, such that

$\displaystyle\mathsf{span}_{M_{R}^{k}}(D,\Sigma,Q,H,\bar{c})$
$\displaystyle=$
$\displaystyle|\\{D^{\prime}\in\mathsf{ORep}(D,\Sigma)\mid\bar{c}\in
Q(D^{\prime})\\}|$
$\displaystyle\mathsf{span}_{M_{S}^{k}}(D,\Sigma,Q,H,\bar{c})$
$\displaystyle=$ $\displaystyle|\\{s\in\mathsf{CRS}(D,\Sigma)\mid\bar{c}\in
Q(s(D))\\}|.$

For the sake of simplicity, we are going to assume, w.l.o.g., that the input
to those procedures is in a certain normal form. Let us first introduce this
normal form, and then discuss the procedures.

#### Normal Form.

Consider a CQ $Q(\bar{x})$ from $\mathsf{SJF}$ and a generalized hypertree
decomposition $H=(T,\chi,\lambda)$ of $Q$. We say that $H$ is $\ell$-uniform,
for $\ell>0$, if every non-leaf vertex of $T$ has exactly $\ell$ children. For
any two vertices $v_{1},v_{2}$ of $T$, we write $v_{1}\prec_{T}v_{2}$ if
$\mathsf{depth}(v_{1})<\mathsf{depth}(v_{2})$, or
$\mathsf{depth}(v_{1})=\mathsf{depth}(v_{2})$ and $v_{1}$ precedes $v_{2}$
lexicographically. It is easy to verify that $\prec_{T}$ is a total ordering
over the vertices of $T$. Consider an atom $R(\bar{y})$ of $Q$. We say that a
vertex $v$ of $T$ is a _covering vertex for_ $R(\bar{y})$ (in $H$) if
$\bar{y}\subseteq\chi(v)$ and $R(\bar{y})\in\lambda(v)$ (van Bremen and Meel,
2023). We say that $H$ is _complete_ if each atom of $Q$ has at least one
covering vertex in $H$. The _$\prec_{T}$ -minimal covering vertex_ for some
atom $R(\bar{y})$ of $Q$ (in $H$) is the covering vertex $v$ for $R(\bar{y})$
for which there is no other covering vertex $v^{\prime}$ for $R(\bar{y})$ with
$v^{\prime}\prec_{T}v$; if $H$ is complete, every atom of $Q$ has a
$\prec_{T}$-minimal covering vertex. We say that $H$ is _strongly complete_ if
it is complete, and every vertex of $T$ is the $\prec_{T}$-minimal covering
vertex of some atom of $Q$.

Now, given a database $D$, a CQ $Q$ from $\mathsf{SJF}$, and a generalized
hypertree decomposition $H$ of $Q$, we say that the triple $(D,Q,H)$ is in
_normal form_ if _(i)_ every relation name in $D$ also occurs in $Q$, and
_(ii)_ $H$ is strongly complete and 2-uniform. We can show that, given a
database $D$, a set $\Sigma$ of primary keys, a CQ $Q(\bar{x})$ from
$\mathsf{SJF}$, a generalized hypetree decomposition $H$ of $Q$ of width
$k>0$, and a tuple $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$, we can convert in
logarithmic space the triple $(D,Q,H)$ into a triple
$(\hat{D},\hat{Q},\hat{H})$, where $\hat{H}$ is a generalized hypetree
decomposition of $\hat{Q}$ of width $k+1$, that is in normal form while
$|\\{D^{\prime}\in\mathsf{ORep}(D,\Sigma)\mid\bar{c}\in
Q(D^{\prime})\\}|=|\\{D^{\prime}\in\mathsf{ORep}(\hat{D},\Sigma)\mid\bar{c}\in\hat{Q}(D^{\prime})\\}|$
and $|\\{s\in\mathsf{CRS}(D,\Sigma)\mid\bar{c}\in
Q(s(D))\\}|=|\\{s\in\mathsf{CRS}(\hat{D},\Sigma)\mid\bar{c}\in\hat{Q}(s(\hat{D}))\\}|$.
This, together with the fact that $\mathsf{SpanTL}$ is closed under logspace
reductions (Proposition 4.5), allows us to assume, w.l.o.g., that the input
$D,\Sigma,Q,H,\bar{c}$ to the procedures that we are going to devise in the
rest of the section always enjoys the property that the triple $(D,Q,H)$ is in
normal form.

###  5.1. The Case of Uniform Repairs

We proceed to show item (1) of Theorem 5.1. This is done via the procedure
$\mathsf{Rep}[k]$, depicted in Algorithm 1, for which we can show the
following technical lemma:

###### Lemma 5.2.

For every $k>0$, the following hold:

  1. (1)

$\mathsf{Rep}[k]$ can be implemented as a well-behaved ATO $M_{R}^{k}$.

  2. (2)

For a database $D$, a set $\Sigma$ of primary keys, a CQ $Q(\bar{x})$ from
$\mathsf{SJF}$, a generalized hypertree decomposition $H$ of $Q$ of width $k$,
and a tuple $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$, where $(D,Q,H)$ is in
normal form,
$\mathsf{span}_{M_{R}^{k}}(D,\Sigma,Q,H,\bar{c})=|\\{D^{\prime}\in\mathsf{ORep}(D,\Sigma)\mid\bar{c}\in
Q(D^{\prime})\\}|$.

Item (1) of Theorem 5.1 readily follows from Lemma 5.2. The rest of this
section is devoted to discuss the procedure $\mathsf{Rep}[k]$ and why Lemma
5.2 holds. We first start with some auxiliary notions and a discussion on how
the valid outputs of the procedure $\mathsf{Rep}[k]$ (which are labeled trees)
look like, which will greatly help the reader to understand how the procedure
$\mathsf{Rep}[k]$ works.

#### Auxiliary Notions and Valid Outputs.

Consider a database $D$, a set $\Sigma$ of primary keys, and a fact
$\alpha=R(c_{1},\ldots,c_{n})\in D$. The _key value_ of $\alpha$ w.r.t.
$\Sigma$ is defined as

$\displaystyle\mathsf{key}_{\Sigma}(\alpha)\
=\left\\{\begin{array}[]{ll}\langle R,\langle
c_{i_{1}},\ldots,c_{i_{m}}\rangle\rangle&\text{if
}\mathsf{key}(R)=\\{i_{1},\ldots,i_{m}\\}\in\Sigma,\\\ &\\\ \langle R,\langle
c_{1},\ldots,c_{n}\rangle\rangle&\text{otherwise.}\end{array}\right.$

Moreover, we let $\mathsf{block}_{\alpha,D}(\Sigma)=\\{\beta\in
D\mid\mathsf{key}_{\Sigma}(\beta)=\mathsf{key}_{\Sigma}(\alpha)\\}$, and
$\mathsf{block}_{R,D}(\Sigma)=\\{\mathsf{block}_{R(\bar{c}),D}(\Sigma)\mid
R(\bar{c})\in D\\}$, for a relation name $R$.

Consider now the following Boolean CQ $Q$

$\text{Ans}()\text{ :- }P(x,y),S(y,z),T(z,x),U(y,w),$

which has generalized hypertree width $2$. A generalized hypertree
decomposition $H=(T,\chi,\lambda)$ of $Q$ of width $2$ is

where each box denotes a vertex $v$ of $T$, and the content of the box is
$\chi(v)$ while on its side is $\lambda(v)$. Consider now the set of primary
keys $\Sigma=\\{\mathsf{key}(R)=\\{1\\}\mid R\in\\{P,S,T,U\\}\\}$ and the
database

$D\ =\
\\{P(a_{1},b),P(a_{1},c),P(a_{2},b),P(a_{2},c),P(a_{2},d),S(c,d),S(c,e),\\\
T(d,a_{1}),U(c,f),U(c,g),U(h,i),U(h,j),U(h,k)\\}.$

Each operational repair in $\mathsf{ORep}(D,\Sigma)$ is such that, for each
relation $R$ in $D$, and for each block $B\in\mathsf{block}_{R,D}(\Sigma)$,
either $B=\\{\beta\\}$ and $\beta\in D^{\prime}$, or _at most_ one fact of $B$
occurs in $D^{\prime}$; recall that justified operations can remove pairs of
facts, and thus a repairing sequence can leave a block completely empty. For
example, the database

$D^{\prime}=\\{P(a_{1},c),S(c,d),T(d,a_{1}),U(c,f),U(h,i)\\}$

is an operational repair of $\mathsf{ORep}(D,\Sigma)$ where we keep the atoms
occurring in $D^{\prime}$ from their respective block in $D$, while for all
the other blocks we do not keep any atom. Assuming a lexicographical order
among the key values of all facts of $D$, we can unambiguously encode the
database $D^{\prime}$ as the following labeled tree $\mathcal{T}$:

The root of $\mathcal{T}$ is labeled with the empty string $\epsilon$, and the
label of each other node denotes the choice made on a block $B$ of
$\mathsf{block}_{R,D}(\Sigma)$, for some relation name $R$, in order to
construct $D^{\prime}$, i.e., either we keep a certain fact from $B$, or we
keep none ($\bot$). Crucially, the shape of $\mathcal{T}$ is determined by
$H$. In particular, since the root $v$ of $H$ is such that $\lambda(v)$
mentions the relation names $P$ and $S$, then, after its root, $\mathcal{T}$
proceeds with a path where nodes correspond to choices relative to the blocks
of $P$ and $S$, and the choices are ordered according to the order over key
values discussed before. Then, since $v$ has two children $u_{1},u_{2}$ such
that $\lambda(u_{1})$ and $\lambda(u_{2})$ mention $T$ and $U$, respectively,
$\mathcal{T}$ continues in two parallel branches, where in the first branch it
lists the choices for the blocks of $T$, while in the second branch it lists
the choices for the blocks of $U$.

We can now discuss the procedure $\mathsf{Rep}[k]$. In what follows, a _tuple
mapping_ is an expression of the form $\bar{x}\mapsto\bar{c}$, where $\bar{x}$
is a tuple of terms and $\bar{c}$ a tuple of constants with
$|\bar{x}|=|\bar{c}|$, and we say that a set $A$ of tuple mappings is
_coherent_ if, for any $\bar{x}\mapsto\bar{t}\in A$, $\bar{x}[i]\in\mathbf{C}$
implies $\bar{x}[i]=\bar{t}[i]$, for all $i\in[|\bar{x}|]$, and for any
$\bar{x}\mapsto\bar{t},\bar{y}\mapsto\bar{u}\in A$, $\bar{x}[i]=\bar{y}[j]$
implies $\bar{t}[i]=\bar{u}[j]$, for all $i\in[|\bar{x}|]$, $j\in[|\bar{y}|]$.

Input: A database $D$, a set $\Sigma$ of primary keys, a CQ $Q(\bar{x})$ from
$\mathsf{SJF}$, a generalized hypertree decomposition $H=(T,\chi,\lambda)$ of
$Q$ of width $k$, and $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$, where $(D,Q,H)$
is in normal form

1

2$v:=\mathsf{root}(T)$; $A:=\emptyset$;

3

4Assuming
$\lambda(v)=\\{R_{i_{1}}(\bar{y}_{i_{1}}),\ldots,R_{i_{\ell}}(\bar{y}_{i_{\ell}})\\}$,
guess a set $A^{\prime}=$
$\\{\bar{y}_{i_{1}}\mapsto\bar{c}_{1},\ldots,\bar{y}_{i_{\ell}}\mapsto\bar{c}_{\ell}\\}$,
with $R_{i_{j}}(\bar{c}_{j})\in D$ for $j\in[\ell]$, and verify $A\cup
A^{\prime}\cup\\{\bar{x}\mapsto\bar{c}\\}$ is coherent; if not, reject;

5

6 for $j=1,\ldots,\ell$ do

7 if $v$ is the $\prec_{T}$-minimal covering vertex for
$R_{i_{j}}(\bar{y}_{i_{j}})$ then

8 foreach $B\in\mathsf{block}_{R_{i_{j}},D}(\Sigma)$ do

9 if $B=\\{\beta\\}$ then $\alpha:=\beta;$

10 else if $R_{i_{j}}(\bar{c}_{j})\in B$ then
$\alpha:=R_{i_{j}}(\bar{c}_{j})$;

11 else Guess $\alpha\in B\cup\\{\bot\\}$;

12

13 Label with $\alpha$;

14

15

16

17

18if $v$ is not a leaf of $T$ then

19 Universally guess a child $u$ of $v$ in $T$;

20 $v:=u$; $A:=A^{\prime}$;

21 goto line 1;

22

23else accept;

Algorithm 1 The alternating procedure $\mathsf{Rep}[k]$

#### The Procedure $\mathsf{Rep}[k]$.

Roughly speaking, $\mathsf{Rep}[k]$ describes the computation of a well-
behaved ATO $M_{R}^{k}$ that, given $D,\Sigma,Q,H,\bar{c}$, with $(D,Q,H)$
being in normal form, non-deterministically outputs a labeled tree which, if
accepted, encodes in the way discussed above a repair of
$\\{D^{\prime}\in\mathsf{ORep}(D,\Sigma)\mid\bar{c}\in Q(D^{\prime})\\}$.

We assume that when $\mathsf{Rep}[k]$ starts, it immediately moves from the
initial (necessarily labeling) state to a non-labeling state, and then
proceeds with its computation; this automatically creates the root with label
$\epsilon$ of the output tree. Then, starting from the root $v$ of $H$,
$\mathsf{Rep}[k]$ guesses a set $A^{\prime}$ of tuple mappings from the tuples
of terms in $\lambda(v)$ to constants. This set witnesses that the tree being
constructed encodes an operational repair $D^{\prime}$ such that $\bar{c}\in
Q(D^{\prime})$. For this to be the case, $A^{\prime}$ must be coherent with
$\\{\bar{x}\mapsto\bar{c}\\}$ and the set $A$ of tuple mappings guessed at the
previous step. Having $A^{\prime}$ in place, lines 1-1 non-deterministically
construct a path of the output tree that encodes, as discussed above, the
choices needed to obtain the operational repair $D^{\prime}$ being considered.
The statement “Label with $\alpha$” means that $M_{R}^{k}$ writes a _pointer_
to $\alpha$ in the labeling tape, then moves to a labeling state, and finally
moves to a non-labeling state; writing a pointer to $\alpha$ allows to use at
most logarithmic space in the labeling tape. Note that due to the “if”
statement in line 1, $\mathsf{Rep}[k]$ does not consider the same block more
than once when visiting different nodes of $H$. Moreover, since $H$ is
strongly complete, there is a guarantee that, for every visited node $v$ of
$H$, $\mathsf{Rep}[k]$ will always output a node of the tree encoding
$D^{\prime}$ (this guarantees that $M_{R}^{k}$ is well-behaved). The procedure
then proceeds in a parallel branch for each child of $v$. Since $H$ enjoys the
connectedness condition, only the current set $A^{\prime}$ of tuple mappings
needs to be kept in memory when moving to a new node of $H$; such a set can be
stored in logarithmic space using pointers. Moreover, since $H$ is 2-uniform,
only a constant number of universal, non-labeling configurations are needed to
universally move to each child of $v$, and thus $M_{R}^{k}$ is well-behaved.
When all branches accept, the output of $\mathsf{Rep}[k]$ is a tree that
encodes an operational repair $D^{\prime}$ of $D$ w.r.t. $\Sigma$ such that
$\bar{c}\in Q(D^{\prime})$; this is because each relation of $D$ occurs in
$Q$, and thus no blocks of $D$ are left unrepaired.

Let us stress that by guessing $\alpha\in B$ in line 8 of $\mathsf{Rep}[k]$,
without considering the symbol $\bot$, we can show that the problem
$\sharp\mathsf{SRepairs}[k]$, defined as $\sharp\mathsf{Repairs}[k]$ with the
difference that we focus on the classical subset repairs from (Arenas et al.,
1999), is in $\mathsf{SpanTL}$, and thus it admits an FPRAS. To the best of
our knowledge, this is the first result concerning the combined complexity of
the problem of counting classical repairs entailing a query.

###  5.2. The Case of Uniform Sequences

We now proceed to show item (2) of Theorem 5.1. This is done via the procedure
$\mathsf{Seq}[k]$, depicted in Algorithm 2. We show that:

###### Lemma 5.3.

For every $k>0$, the following hold:

  1. (1)

$\mathsf{Seq}[k]$ can be implemented as a well-behaved ATO $M_{S}^{k}$.

  2. (2)

For a database $D$, a set $\Sigma$ of primary keys, a CQ $Q(\bar{x})$ from
$\mathsf{SJF}$, a generalized hypertree decomposition $H$ of $Q$ of width $k$,
and a tuple $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$, where $(D,Q,H)$ is in
normal form,
$\mathsf{span}_{M_{S}^{k}}(D,\Sigma,Q,H,\bar{c})=|\\{s\in\mathsf{CRS}(D,\Sigma)\mid\bar{c}\in
Q(s(D))\\}|$.

Item (2) of Theorem 5.1 readily follows from Lemma 5.3. The rest of this
section is devoted to discussing the procedure $\mathsf{Seq}[k]$ and why Lemma
5.3 holds. But first we need some auxiliary notions.

#### Auxiliary Notions.

Consider a database $D$ and a set $\Sigma$ of primary keys over a schema
$\mathbf{S}$. Moreover, for an integer $n>0$ and $\alpha\in(\\{R(\bar{c})\mid
R/m\in\mathbf{S}\text{ and }\bar{c}\in\mathsf{dom}(D)^{m}\\}\cup\\{\bot\\})$,
we define the set

$\mathsf{shape}(n,\alpha)\ =\ \begin{cases}\\{-1,-2\\}&\text{if }n>1,\\\
\\{-1\\}&\text{if }n=1\text{ and }\alpha\neq\bot,\\\
\emptyset&\text{otherwise.}\end{cases}$

The above set essentially collects the “shapes” of operations (i.e., remove a
fact or a pair of facts) that one can apply on a block of the database,
assuming that only $n$ facts of the block must be removed overall, and either
the block must remain empty (i.e., $\alpha=\bot$), or the block must contain
exactly one fact (i.e., $\alpha\neq\bot$). Finally, for an integer $n>0$ and
$i\in\\{-1,-2\\}$, let $\\#\mathsf{opsFor}(n,i)=n$, if $i=-1$, and
$\\#\mathsf{opsFor}(n,i)=\frac{n(n-1)}{2}$, if $i=-2$. Roughly, assuming that
$n$ facts of a block must be removed, $\\#\mathsf{opsFor}(n,i)$ is the total
number of operations of the shape determined by $i$ that can be applied.

Input: A database $D$, a set $\Sigma$ of primary keys, a CQ $Q(\bar{x})$ from
$\mathsf{SJF}$, a generalized hypertree decomposition $H=(T,\chi,\lambda)$ of
$Q$ of width $k$, and $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$, where $(D,Q,H)$
is in normal form

1 $v:=\mathsf{root}(T)$; $A:=\emptyset$, $b:=0$;

2 Guess $N\in[|D|]$;

3 Assuming
$\lambda(v)=\\{R_{i_{1}}(\bar{y}_{i_{1}}),\ldots,R_{i_{\ell}}(\bar{y}_{i_{\ell}})\\}$,
guess a set $A^{\prime}=$
$\\{\bar{y}_{i_{1}}\mapsto\bar{c}_{1},\ldots,\bar{y}_{i_{\ell}}\mapsto\bar{c}_{\ell}\\}$,
with $R_{i_{j}}(\bar{c}_{j})\in D$ for $j\in[\ell]$, and verify $A\cup
A^{\prime}\cup\\{\bar{x}\mapsto\bar{c}\\}$ is coherent; if not, reject;

4 for $j=1,\ldots,\ell$ do

5 if $v$ is the $\prec_{T}$-minimal covering vertex for
$R_{i_{j}}(\bar{y}_{i_{j}})$ then

6 foreach $B\in\mathsf{block}_{R_{i_{j}},D}(\Sigma)$ do

7

8 if $B=\\{\beta\\}$ then $\alpha:=\beta$;

9 else if $R_{i_{j}}(\bar{c}_{j})\in B$ then $\alpha:=R_{i_{j}}(\bar{c}_{j})$;

10 else Guess $\alpha\in B\cup\\{\bot\\}$;

11

12 if $\alpha=\bot$ then $n:=|B|$ else $n:=|B|-1$;

13

14 $b^{\prime}:=b$;

15

16 while $n>0$ do

17 if $\mathsf{shape}(n,\alpha)=\emptyset$ then reject;

18 else Guess $-g\in\mathsf{shape}(n,\alpha)$;

19 Guess $p\in[\\#\mathsf{opsFor}(n,-g)]$;

20 Label with $(-g,p)$;

21 $b:=b+1$; $N:=N-1$; $n:=n-g$;

22

23 Guess $p\in\left[b\choose b^{\prime}\right]$;

24 Label with $(\alpha,p)$;

25

26

27

28

29if $v$ is not a leaf of $T$ then

30 Guess $p\in\\{0,\ldots,N\\}$;

31 Universally guess a child $u$ of $v$ in $T$;

32 if $u$ is the first child of $v$ then $N:=p$;

33 else $N:=N-p$; $b:=b+p$;

34 $v:=u$; $A:=A^{\prime}$;

35 goto line 2;

36

37else if $N=0$ then accept; else reject;

38

Algorithm 2 The alternating procedure $\mathsf{Seq}[k]$

#### The Procedure $\mathsf{Seq}[k]$.

Let $M_{S}^{k}$ be the ATO underlying $\mathsf{Seq}[k]$. As for
$\mathsf{Rep}[k]$, we assume that $M_{S}^{k}$ immediately moves from the
initial state to a non-labeling state. $\mathsf{Seq}[k]$ proceeds similarly to
$\mathsf{Rep}[k]$, i.e., it traverses the generalized hypertree decomposition
$H$, where for each vertex $v$, it guesses a set of tuple mappings
$A^{\prime}$ coherent with $\\{\bar{x}\mapsto\bar{c}\\}$ and with the set of
tuple mappings of the previous vertex, and non-deterministically chooses which
atom (if any) to keep from each block relative to the relation names in
$\lambda(v)$.

The key difference between $\mathsf{Seq}[k]$ and $\mathsf{Rep}[k]$ is that,
for a certain operational repair $D^{\prime}$ that $\mathsf{Seq}[k]$
internally guesses, $\mathsf{Seq}[k]$ must output a number of trees that
coincides with the number of complete $(D,\Sigma)$-repairing sequences $s$
such that $s(D)=D^{\prime}$. To achieve this, at the beginning of the
computation, $\mathsf{Seq}[k]$ guesses the length $N$ of the repairing
sequence being computed. Then, whenever it chooses some $\alpha\in
B\cup\\{\bot\\}$ for a certain block $B$ (lines 7-9), then, in lines 10-17, it
will non-deterministically output a _path_ of the form
$L_{1}\rightarrow\cdots\rightarrow L_{n}$, where $L_{1},\ldots,L_{n}$ are
special symbols describing the “shape” of operations to be performed in order
to leave in $B$ only the fact $\alpha$, if $\alpha\neq\bot$, or no facts, if
$\alpha=\bot$. Each symbol $L_{i}$ is a pair of the form $(-g,p)$, where
$-g\in\\{-1,-2\\}$ denotes whether the operation removes one or a pair of
facts. For example, a path
$(-1,n_{1})\rightarrow(-2,n_{2})\rightarrow(-2,n_{3})\rightarrow(-1,n_{4})$ is
a template specifying that the first operation on the block should remove a
single fact, then the next two operations should remove pairs of facts, and
the last operation should remove a single fact.

However, a symbol in $\\{-1,-2\\}$ alone only denotes a _family_ of operations
over the block $B$, i.e., there may be multiple ways for translating such a
symbol into an actual operation, depending on the size of $B$ and the value of
$\alpha$. Thus, in a pair $(-g,p)$, the integer $p$ acts as an _identifier_ of
the concrete operation being applied having the shape of $-g$.222Identifiers
are used in place of actual operations as the procedure would not be able to
remember the whole “history” of applied operations in logarithmic space. The
last important observation is that $\mathsf{Seq}[k]$ outputs a template of
_all_ operations of a certain block, before moving to another block, and
further, blocks are considered in a fixed order. However, a complete
$(D,\Sigma)$-repairing sequence might interleave operations coming from
different blocks in an arbitrary way as each block is independent. The
procedure accounts for this in lines 18-19 as follows. Let $k_{1},\dots,k_{m}$
be the number of operations applied over each individual block during a run of
$\mathsf{Seq}[k]$ (where $m$ is the total number of blocks of $D$). Any
arbitrary interleaving of the above operations gives rise to a complete
$(D,\Sigma)$-repairing sequence. Hence, the number of complete
$(D,\Sigma)$-repairing sequences that uses those numbers of operations is the
multinomial coefficient

${k_{1}+\dots+k_{m}\choose k_{1},\dots,k_{m}}={k_{1}\choose
0}\times{k_{1}+k_{2}\choose k_{1}}\times\dots\times{k_{1}+\dots+k_{m}\choose
k_{1}+\dots+k_{m-1}}.$

Hence, when $\mathsf{Seq}[k]$ completely “repairs” the $i$-th block of $D$
(i.e., it reaches line 18), in lines 18-19 it “amplifies” the number of trees
by guessing an integer $p\in\left[{b\choose b^{\prime}}\right]$, with
$b=k_{1}+\cdots+k_{i}$ and $b^{\prime}=k_{1}+\cdots k_{i-1}$, and by running
the statement “Label with $(\alpha,p)$”. We can show that $b\choose
b^{\prime}$, and actually any number $p\in\left[{b\choose b^{\prime}}\right]$,
can be computed in logspace using ideas from (Chiu et al., 2001). However, the
number of bits required to write $p\in\left[{b\choose b^{\prime}}\right]$ in
the labeling tape is polynomial. So, by “Label $(\alpha,p)$” we actually mean
that $M_{S}^{k}$ outputs a _path_ of polynomial length of the form
$(\alpha,b_{1})\rightarrow(\alpha,b_{2})\rightarrow\cdots\rightarrow(\alpha,b_{n})$,
where $b_{i}$ is the $i$-th bit of the binary representation of $p$.

With all blocks relative to a vertex $v$ completely processed, the procedure
moves in parallel to the two children of $v$. To this end, it guesses how many
operations are going to be applied in the sequences produced in the left and
the right branch, respectively. It does this by guessing an integer
$p\in\\{0,\ldots,N\\}$, which essentially partitions $N$ as the sum of two
numbers, i.e., $p$ and $N-p$, and then adapts the values of $N$ (number of
operations left) and $b$ (number of operations applied so far) in each branch,
accordingly. A computation is accepting if in each of its leaves all required
operations have been applied (i.e., $N=0$).

###### Example 5.4.

Consider the database $D$, the set $\Sigma$ of primary keys, the Boolean CQ
$Q$, and the generalized hypertree decomposition $H$ of $Q$ used in the
discussion on valid outputs in Section 5.1. A possible accepting computation
of the ATO $M_{S}^{2}$ described by $\mathsf{Seq}[2]$ on input $D$, $\Sigma$,
$Q$, $H$, and the empty tuple $()$, is the one corresponding to the
operational repair
$D^{\prime}=\\{P(a_{1},c),S(c,d),T(d,a_{1}),U(c,f),U(h,i)\\}$, with
$D^{\prime}\models Q$, that outputs a tree of one of the following forms:

Note that, for simplicity, we omit the root with label $\epsilon$, and each
pair that labels a node is presented by showing each of its elements on a
separate line inside the node. Moreover, the nodes with a gray background
containing a pair $(\alpha,\ell)$ are actually a shorthand for paths of the
form
$(\alpha,b_{1})\rightarrow(\alpha,b_{2})\rightarrow\cdots\rightarrow(\alpha,b_{n})$,
where $b_{i}$ is the $i$-th bit of $\ell$. Different accepting computations of
the procedure that internally guess the same operational repair $D^{\prime}$
will output a tree obtained from one of the above two forms, having each
$\ell$ equal to some value in the corresponding set. Hence, the total number
of such trees is $s_{1}+s_{2}$, where $s_{1}$ (resp., $s_{2}$) is the product
of all “amplifying factors” written in red in each label of the first (resp.,
second) tree in the figure above, i.e.,

$\begin{array}[]{ll}s_{1}=&1\times{1\choose 0}\times 3\times 1\times{3\choose
1}\times 1\times{4\choose 3}\times{4\choose 4}\times 1\times{5\choose 4}\times
2\times 1\times{7\choose 5},\\\ \\\ s_{2}=&1\times{1\choose 0}\times 3\times
1\times{3\choose 1}\times 1\times{4\choose 3}\times{4\choose 4}\times
1\times{5\choose 4}\times 1\times{6\choose 5}.\end{array}$

One can verify that $s_{1}+s_{2}$ is precisely the number of complete
$(D,\Sigma)$-repairing sequences $s$ such that $s(D)=D^{\prime}$, as needed.

##  6\. Future Work

The problems of interest are well-understood in the case of primary keys for
both settings of data and combined complexity. However, it remains open
whether those results can be extended to more general constraints such as
arbitrary keys or even functional dependencies. Settling those open problems
will be our next research goal.

##  Appendix A Proof of Theorem 3.4

We prove the following result:

###### Theorem 3.4.

For every $k>0$, $\mathsf{OCQA}^{\star}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$ is
$\sharp$P-hard, where $\star\in\\{\mathsf{ur},\mathsf{us}\\}$.

For brevity, for a fact $f$, we write $-f$ instead of $-\\{f\\}$ to denote the
operation that removes $f$. We first deal with the uniform repairs case
($\star=\mathsf{ur}$) and then with the uniform sequences case
($\star=\mathsf{us}$).

###  A.1. The Uniform Repairs Case

Fix an arbitrary $k>0$. We are going to show that
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$ is
$\sharp$P-hard. Let us first introduce the $\sharp$P-hard problem that we are
going to reduce to
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$. Consider the
undirected bipartite graph $H=(V_{H},E_{H})$, depicted in Figure 1, where
$V_{H,L}=\\{1_{L},0_{L},?_{L}\\}$ and $V_{H,R}=\\{1_{R},0_{R},?_{R}\\}$, with
$\\{V_{H,L},V_{H,R}\\}$ being a partition of $V_{H}$, and
$E_{H}=\\{\\{u,v\\}\mid(u,v)\in(V_{H,L}\times
V_{H,R})\setminus\\{(1_{L},1_{R})\\}\\}$.

$1_{L}$$0_{L}$$?_{L}$$1_{R}$$0_{R}$$?_{R}$ Figure 1. The graph $H$.

Given an undirected graph $G=(V_{G},E_{G})$, a homomorphism from $G$ to $H$ is
a mapping $h:V_{G}\rightarrow V_{H}$ such that $\\{u,v\\}\in E_{G}$ implies
$\\{h(u),h(v)\\}\in E_{H}$. We write $\mathsf{hom}(G,H)$ for the set of
homomorphisms from $G$ to $H$. The problem $\sharp H\text{-}\mathsf{Coloring}$
is defined as follows:

PROBLEM : $\sharp H\text{-}\mathsf{Coloring}$ INPUT : A connected undirected
graph $G$. OUTPUT : The number $|\mathsf{hom}(G,H)|$.

It is implicit in (Dyer and Greenhill, 2000) that $\sharp
H\text{-}\mathsf{Coloring}$ is $\sharp$P-hard. In fact, (Dyer and Greenhill,
2000) establishes the following dichotomy result:
$\sharp\hat{H}\text{-}\mathsf{Coloring}$ is $\sharp$P-hard if $\hat{H}$ has a
connected component which is neither an isolated node without a loop, nor a
complete graph with all loops present, nor a complete bipartite graph without
loops; otherwise, it is solvable in polynomial time. Since our fixed graph $H$
above consists of a single connected component which is neither a single node,
nor a complete graph with all loops present, nor a complete bipartite graph
without loops (the edge $(1_{L},1_{R})$ is missing), we conclude that $\sharp
H\text{-}\mathsf{Coloring}$ is indeed $\sharp$P-hard. Note that we can assume
the input graph $G$ to be connected since the total number of homomorphisms
from a (non-connected) graph $G^{\prime}$ to $H$ is the product of the number
of homomorphisms from each connected component of $G^{\prime}$ to $H$. We
proceed to show via a polynomial-time Turing reduction from $\sharp
H\text{-}\mathsf{Coloring}$ that
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$ is
$\sharp$P-hard. In other words, we need to show that, given a connected
undirected graph $G$, the number $|\mathsf{hom}(G,H)|$ can be computed in
polynomial time in the size of $G$ assuming that we have access to an oracle
for the problem
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$.

Fix a connected undirected bipartite graph $G$ with vertex partition
$\\{V_{G,L},V_{G,R}\\}$. Let $\mathbf{S}_{k}$ be the schema

$\\{V_{L}/2,V_{R}/2,E/2,T/1,T^{\prime}/1\\}\cup\\{C_{i,j}/2\mid i,j\in[k+1],\
i<j\\},$

with $(A,B)$ being the tuple of attributes of both $V_{L}$ and $V_{R}$. We
define the database $D_{G}^{k}$ over $\mathbf{S}_{k}$ encoding $G$ as follows:

$\displaystyle\\{V_{L}(u,0),V(u,1)\mid u\in V_{G,L}\\}$ $\displaystyle\cup$
$\displaystyle\\{V_{R}(u,0),V(u,1)\mid u\in V_{G,R}\\}$ $\displaystyle\cup$
$\displaystyle\\{E(u,v)\mid(u,v)\in E_{G}\\}\ \cup\ \\{T(1)\\}\ \cup\
\\{T^{\prime}(1)\\}$ $\displaystyle\cup$ $\displaystyle\\{C_{i,j}(i,j)\mid
i,j\in[k+1],\ i<j\\}.$

We also define the set $\Sigma$ of keys consisting of

$\mathsf{key}(V_{L})=\\{1\\}\quad\textrm{and}\quad\mathsf{key}(V_{R})=\\{1\\}$

and the (constant-free) self-join-free Boolean CQ $Q_{k}$

$\textrm{Ans}()\ \text{:-}\
E(x,y),V_{L}(x,z),V_{R}(y,z^{\prime}),T(z),T^{\prime}(z^{\prime}),\bigwedge_{\begin{subarray}{c}i,j\in[k+1]\\\
i<j\end{subarray}}C_{i,j}(w_{i},w_{j}).$

It is easy to verify that $Q_{k}\in\mathsf{GHW}_{k}$ since the big conjunction
over $C_{i,j}$-atoms encodes a clique of size $k+1$. Let us stress that the
role of this conjunction is only to force the CQ $Q_{k}$ to be of generalized
hypertreewidth $k$ as this part of the query will be entailed in every repair
(since there are no inconsistencies involving a $C_{i,j}$-atom).

Consider now the algorithm $\mathsf{HOM}$, which accepts as input a connected
undirected graph $G=(V_{G},E_{G})$ and has access to an oracle for
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$, and performs
as follows:

  1. (1)

If $|V_{G}|=1$ and $E_{G}=\emptyset$, then output the number $6$; otherwise,
continue.

  2. (2)

If $G$ is not bipartite, then output the number $0$; otherwise, continue.

  3. (3)

Let $r=\mathsf{RF}^{\mathsf{ur}}(D_{G}^{k},\Sigma,Q_{k},())$.

  4. (4)

Output the number $2\cdot 3^{|V_{G}|}\cdot(1-r)$.

It is clear that $\mathsf{HOM}(G)$ runs in polynomial time in $||G||$ assuming
access to an oracle for the problem
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$. It remains to
show that $|\mathsf{hom}(G,H)|=\mathsf{HOM}(G)$.

If $G$ consists of only one isolated node, then there are six homomorphism
from $G$ to $H$ (to each of the six vertices of $H$). Further, if $G$ is not
bipartite, then clearly $|\mathsf{hom}(G,H)|=0$. Let us now consider the case
where $G$ is a connected undirected bipartite graph with vertex partition
$\\{V_{G,L},V_{G,R}\\}$. Recall that

$\mathsf{RF}^{\mathsf{ur}}(D_{G}^{k},\Sigma,Q_{k},())=\frac{|\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid
D\models Q_{k}\\}|}{|\mathsf{ORep}(D_{G}^{k},\Sigma)|}.$

Observe that there are $3^{|V_{G}|}$ operational repairs of $D_{G}^{k}$ w.r.t.
$\Sigma$. In particular, in each such a repair $D$, for each node $u\in
V_{G,L}$ of $G$, either $V_{L}(u,0)\in D$ and $V_{L}(u,1)\not\in D$, or
$V_{L}(u,0)\not\in D$ and $V_{L}(u,1)\in D$, or $V_{L}(u,0),V_{L}(u,1)\not\in
D$. Further, for each node $u\in V_{G,R}$ of $G$, either $V_{R}(u,0)\in D$ and
$V_{R}(u,1)\not\in D$, or $V_{R}(u,0)\not\in D$ and $V_{R}(u,1)\in D$, or
$V_{R}(u,0),V_{L}(u,1)\not\in D$. Thus, there are $3^{|V_{G,L}|}\cdot
3^{|V_{G,R}|}=3^{|V_{G}|}$ many operational repairs of $D_{G}^{k}$ w.r.t.
$\Sigma$. Therefore,

$\mathsf{RF}^{\mathsf{ur}}(D_{G}^{k},\Sigma,Q_{k},())\ =\
\dfrac{|\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid D\models
Q_{k}\\}|}{3^{|V_{G}|}}.$

Thus, $\mathsf{HOM}(G)$ coincides with

$\displaystyle 2\cdot
3^{|V_{G}|}\cdot\left(1-\dfrac{|\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid
D\models Q_{k}\\}|}{3^{|V_{G}|}}\right)$ $\displaystyle=\;$ $\displaystyle
2\cdot\left(3^{|V_{G}|}-|\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid D\models
Q_{k}\\}|\right).$

Since $D_{G}^{k}$ has $3^{|V_{G}|}$ operational repairs w.r.t. $\Sigma$, we
can conclude that $3^{|V_{G}|}-|\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid
D\models Q_{k}\\}|$ is precisely the cardinality of the set
$\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid D\not\models Q_{k}\\}$.

Since $G$ and $H$ are both connected and bipartite, we know that any
homomorphism from $G$ to $H$ must preserve the partitions, i.e., every vertex
in one partition of $G$ must be mapped to the same partition in $H$ (and the
other partition of $G$ must be mapped to the other partition of $H$). Let
$\mathsf{hom^{\prime}}(G,H)$ be the set of homomorphisms from $G$ to $H$ such
that $V_{G,L}$ is mapped to $V_{H,L}$ and $V_{G,R}$ is mapped to $V_{H,R}$.
Since $H$ is symmetric, we know that for every homomorphism in
$h\in\mathsf{hom^{\prime}}(G,H)$, there are two homomorphisms in
$\mathsf{hom}(G,H)$. In particular, $h\in\mathsf{hom}(G,H)$ and
$h^{\prime}\in\mathsf{hom}(G,H)$, where $h^{\prime}$ is the homomorphism that
is essentially $h$ but maps the vertices of $V_{G,L}$ to $V_{H,R}$ and the
vertices of $V_{G,R}$ to $V_{H,L}$. Thus,
$|\mathsf{hom}(G,H)|=2\cdot|\mathsf{hom^{\prime}}(G,H)|$. We proceed to show
that $|\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid D\not\models Q_{k}\\}|$
coincides with $|\mathsf{hom^{\prime}}(G,H)|$.

###### Lemma A.1.

$|\mathsf{hom^{\prime}}(G,H)|\ =\ |\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid
D\not\models Q_{k}\\}|$.

###### Proof.

It suffices to show that there exists a bijection from the set
$\mathsf{hom^{\prime}}(G,H)$ to the set
$\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid D\not\models Q_{k}\\}$. To this
end, we define the mapping
$\mu:\mathsf{hom^{\prime}}(G,H)\rightarrow\mathcal{P}(D_{G}^{k})$, where
$\mathcal{P}(D_{G}^{k})$ is the power set of $D_{G}^{k}$, as follows: for each
$h\in\mathsf{hom^{\prime}}(G,H)$,

$\displaystyle\mu(h)\ =\ $ $\displaystyle\\{V_{L}(u,0)\mid u\in V_{G,L}\text{
and }h(u)=0_{L}\\}$ $\displaystyle\cup\ \\{V_{L}(u,1)\mid u\in V_{G,L}\text{
and }h(u)=1_{L}\\}$ $\displaystyle\cup\ \\{V_{R}(u,0)\mid u\in V_{G,R}\text{
and }h(u)=0_{R}\\}$ $\displaystyle\cup\ \\{V_{R}(u,1)\mid u\in V_{G,R}\text{
and }h(u)=1_{R}\\}$ $\displaystyle\cup\ \\{E(u,v)\mid\\{u,v\\}\in E_{G}\\}\
\cup\ \\{T(1)\\}\ \cup\ \\{T^{\prime}(1)\\}$ $\displaystyle\cup\
\\{C_{i,j}(i,j)\mid i,j\in[k+1],\ i<j\\}.$

We proceed to show the following three statements:

  1. (1)

$\mu$ is correct, that is, it is indeed a function from
$\mathsf{hom^{\prime}}(G,H)$ to $\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid
D\not\models Q_{k}\\}$.

  2. (2)

$\mu$ is injective.

  3. (3)

$\mu$ is surjective.

#### The mapping $\mu$ is correct.

Consider an arbitrary homomorphism $h\in\mathsf{hom^{\prime}}(G,H)$. We need
to show that there exists a $(D_{G}^{k},\Sigma)$-repairing sequence $s_{h}$
such that $\mu(h)=s_{h}(D_{G}^{k})$, $s_{h}(D_{G}^{k})\models\Sigma$ (i.e.,
$s_{h}$ is complete), and $Q_{k}(s_{h}(D_{G}^{k}))=\emptyset$. Let
$V_{G}=\\{u_{1},\ldots,u_{n}\\}$. Consider the sequence
$s_{h}=\mathit{op}_{1},\ldots,\mathit{op}_{n}$ such that, for every $i\in[n]$:

$\mathit{op}_{i}\ =\ \begin{cases}-V_{L}(u_{i},1)&\text{if }h(u_{i})=0_{L}\\\
-V_{L}(u_{i},0)&\text{if }h(u_{i})=1_{L}\\\
-\\{V_{L}(u_{i},0),V_{L}(u_{i},1)\\}&\text{if }h(u_{i})=\ ?_{L}\\\
-V_{R}(u_{i},1)&\text{if }h(u_{i})=0_{R}\\\ -V_{R}(u_{i},0)&\text{if
}h(u_{i})=1_{R}\\\ -\\{V_{R}(u_{i},0),V_{R}(u_{i},1)\\}&\text{if }h(u_{i})=\
?_{R}\\\ \end{cases}$

In simple words, the homomorphism $h$ guides the repairing process, i.e.,
$h(u_{i})=0_{L}$ (resp., $h(u_{i})=1_{L}$) implies $V_{L}(u_{i},0)$ (resp.,
$V_{L}(u_{i},1)$) should be kept, while $h(u_{i})=\ ?_{L}$ implies none of the
atoms $V_{L}(u_{i},0),V_{L}(u_{i},1)$ should be kept. The analogous is true
for the vertices that are mapped to one of $\\{0_{R},1_{R},?_{R}\\}$. It is
easy to verify that $s_{h}$ is indeed a $(D_{G}^{k},\Sigma)$-repairing
sequence $s_{h}$ such that $\mu(h)=s_{h}(D_{G}^{k})$ and
$s_{h}(D_{G}^{k})\models\Sigma$. The fact that
$Q_{k}(s_{h}(D_{G}^{k}))=\emptyset$ follows from the fact that, for every edge
$\\{u,v\\}\in E_{G}$, $\\{h(u),h(v)\\}\in E_{H}$ cannot be the edge
$(1_{L},1_{R})$, since it is not in $H$. This implies that for every
$\\{u,v\\}\in E_{G}$, it is not possible that the atoms $V_{L}(u,1)$ and
$V_{R}(v,1)$ (or $V_{R}(u,1)$ and $V_{L}(v,1)$) coexist in $s_{h}(D_{G}^{k})$,
which in turn implies that $Q_{k}(s_{h}(D_{G}^{k}))=\emptyset$, as needed.

#### The mapping $\mu$ is injective.

Assume that there are two distinct homomorphisms
$h,h^{\prime}\in\mathsf{hom^{\prime}}(G,H)$ such that
$\mu(h)=\mu(h^{\prime})$. By the definition of $\mu$, we get that
$h(u)=h^{\prime}(u)$, for every node $u\in V_{G}$. But this contradicts the
fact that $h$ and $h^{\prime}$ are different homomorphisms of
$\mathsf{hom^{\prime}}(G,H)$. Therefore, for every two distinct homomorphisms
$h,h^{\prime}\in\mathsf{hom^{\prime}}(G,H)$, $\mu(h)\neq\mu(h^{\prime})$, as
needed.

#### The mapping $\mu$ is surjective.

Consider an arbitrary operational repair
$D\in\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid D\not\models Q_{k}\\}$. We
need to show that there exists $h\in\mathsf{hom^{\prime}}(G,H)$ such that
$\mu(h)=D$. We define the mapping $h_{D}:V_{G}\rightarrow V_{H}$ as follows:
for every $u\in V_{G}$:

$h_{D}(u)\ =\ \begin{cases}1_{L}&\text{if }u\in V_{G,L}\text{ and
}V_{L}(u,1)\in D\text{ and }V_{L}(u,0)\not\in D\\\ 0_{L}&\text{if }u\in
V_{G,L}\text{ and }V_{L}(u,1)\not\in D\text{ and }V_{L}(u,0)\in D\\\
?_{L}&\text{if }u\in V_{G,L}\text{ and }V_{L}(u,1)\not\in D\text{ and
}V_{L}(u,0)\not\in D\\\ 1_{R}&\text{if }u\in V_{G,R}\text{ and }V_{R}(u,1)\in
D\text{ and }V_{R}(u,0)\not\in D\\\ 0_{R}&\text{if }u\in V_{G,R}\text{ and
}V_{R}(u,1)\not\in D\text{ and }V_{R}(u,0)\in D\\\ ?_{R}&\text{if }u\in
V_{G,R}\text{ and }V_{R}(u,1)\not\in D\text{ and }V_{R}(u,0)\not\in D\\\
\end{cases}$

It is clear that $h_{D}$ is well-defined: for every $u\in V_{G}$, $h_{D}(u)=x$
and $h_{D}(u)=y$ implies $x=y$. It is also clear that $\mu(h_{D})=D$. It
remains to show that $h_{D}\in\mathsf{hom^{\prime}}(G,H)$. Consider an
arbitrary edge $\\{u,v\\}\in E_{G}$. W.l.o.g. let $u\in V_{G,L}$ and $v\in
V_{G,R}$. By contradiction, assume that $\\{h_{D}(u),h_{D}(v)\\}\not\in
E_{H}$. This implies that $h_{D}(u)=1_{L}$ and $h_{D}(v)=1_{R}$, since $u$ is
mapped to $V_{H,L}$ and $v$ is mapped to $V_{H,R}$. Therefore, $D$ contains
both atoms $V_{L}(u,1)$ and $V_{R}(v,1)$, which in turn implies that
$Q_{k}(D)\neq\emptyset$, which contradicts the fact that
$D\in\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid D\not\models Q_{k}\\}$.

Summing up, since
$\mathsf{HOM}(G)=2\cdot|\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid
D\not\models Q_{k}\\}|$, Lemma A.1 implies that

$\mathsf{HOM}(G)\ =\ 2\cdot|\mathsf{hom^{\prime}}(G,H)|\ =\
|\mathsf{hom}(G,H)|.$

This shows that indeed $\mathsf{HOM}$ is a polynomial-time Turing reduction
from $\sharp H\text{-}\mathsf{Coloring}$ to
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$. Thus,
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$ is
$\sharp$P-hard, as needed.

###  A.2. The Uniform Sequences Case

The fact that $\mathsf{OCQA}^{\mathsf{us}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$
is $\sharp$P-hard is proven similarly to the uniform repairs case. In
particular, we use the exact same construction and simply show that the two
relative frequencies, i.e., the repair relative frequency and the sequence
relative frequency coincide. Let us give more details.

Fix an arbitrary $k>0$. We show that
$\mathsf{OCQA}^{\mathsf{us}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$ is
$\sharp$P-hard via a polynomial-time Turing reduction from $\sharp
H\text{-}\mathsf{Coloring}$, where $H$ is the graph employed in the first part
of the proof. For a given graph $G$, let $S_{k}$, $D_{G}^{k}$, $\Sigma$, and
$Q_{k}$ be the schema, database, set of primary keys, and Boolean self-join-
free CQ of generalized hypertreewidth $k$, respectively, from the construction
in the proof for the uniform repairs case. We show that

$\mathsf{RF}^{\mathsf{ur}}(D_{G}^{k},\Sigma,Q_{k},())\ =\
\mathsf{RF}^{\mathsf{us}}(D_{G}^{k},\Sigma,Q_{k},()),$

which implies that the polynomial-time Turing reduction from $\sharp
H\text{-}\mathsf{Coloring}$ to
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$ is a
polynomial-time Turing reduction from $\sharp H\text{-}\mathsf{Coloring}$ to
$\mathsf{OCQA}^{\mathsf{us}}[\mathsf{SJF}\cap\mathsf{GHW}_{k}]$. Recall that

$\mathsf{RF}^{\mathsf{us}}(D_{G}^{k},\Sigma,Q_{k},())\ =\
\frac{|\\{s\in\mathsf{CRS}(D_{G}^{k},\Sigma)\mid s(D)\models
Q_{k}\\}|}{|\mathsf{CRS}(D_{G}^{k},\Sigma)|}.$

By construction of $D_{G}^{k}$, each operational repair
$D\in\mathsf{ORep}(D_{G}^{k},\Sigma)$ can be obtained via $|V_{G}|!$ complete
sequences of $\mathsf{CRS}(D_{G}^{k},\Sigma)$. Thus,

$\displaystyle\mathsf{RF}^{\mathsf{us}}(D_{G}^{k},\Sigma,Q_{k},())$
$\displaystyle=$
$\displaystyle\frac{|\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid D\models
Q_{k}\\}|\cdot|V_{G}|!}{|\mathsf{ORep}(D_{G}^{k},\Sigma)|\cdot|V_{G}|!}$
$\displaystyle=$
$\displaystyle\frac{|\\{D\in\mathsf{ORep}(D_{G}^{k},\Sigma)\mid D\models
Q_{k}\\}|}{|\mathsf{ORep}(D_{G}^{k},\Sigma)|}.$

The latter expression is precisely
$\mathsf{RF}^{\mathsf{ur}}(D_{G}^{k},\Sigma,Q_{k},())$, as needed.

##  Appendix B Proof of Theorem 3.5

We proceed to prove the following result:

###### Theorem 3.5.

Unless ${\rm RP}={\rm NP}$, for $\star\in\\{\mathsf{ur},\mathsf{us}\\}$,

  1. (1)

There is no FPRAS for $\mathsf{OCQA}^{\star}[\mathsf{SJF}]$.

  2. (2)

For every $k>0$, there is no FPRAS for
$\mathsf{OCQA}^{\star}[\mathsf{GHW}_{k}]$.

For brevity, for a fact $f$, we write $-f$ instead of $-\\{f\\}$ to denote the
operation that removes $f$. We prove each item of the theorem separately. For
each item, we first deal with the uniform repairs case ($\star=\mathsf{ur}$)
and then with the uniform sequences case ($\star=\mathsf{us}$).

###  B.1. Item (1)

The Uniform Repairs Case

We proceed to show that, unless ${\rm RP}={\rm NP}$,
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}]$ does not admit an FPRAS. Consider
the decision version of $\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}]$, dubbed
$\mathsf{Pos}\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}]$, defined as follows:

PROBLEM : $\mathsf{Pos}\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}]$ INPUT : A
database $D$, a set $\Sigma$ of primary keys, a query $Q(\bar{x})$ from
$\mathsf{SJF}$, a tuple $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$. QUESTION :
$\mathsf{RF}^{\mathsf{ur}}(D,\Sigma,Q,\bar{c})>0$.

To establish our claim it suffices to show that
$\mathsf{Pos}\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}]$ is NP-hard. Indeed,
assuming that an FPRAS for $\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}]$ exists,
we can place the problem
$\mathsf{Pos}\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}]$ in BPP, which implies
that $\textrm{NP}\subseteq\textrm{BPP}$. This in turn implies that ${\rm
RP}={\rm NP}$ (Jerrum, 2003), which contradicts our assumption that ${\rm RP}$
and ${\rm NP}$ are different.

To show that $\mathsf{Pos}\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{SJF}]$, we
reduce from the problem of deciding whether an undirected graph is
3-colorable, which is a well-known NP-hard problem. Recall that, for an
undirected graph $G=(V,E)$, we say that $G$ is 3-colorable if there is a
mapping $\mu:V\rightarrow\\{1,2,3\\}$ such that, for every edge $\\{u,v\\}\in
E$, we have that $\mu(u)\neq\mu(v)$. The $3{\rm-}\mathsf{Colorability}$
problem is defined as follows:

PROBLEM : $3{\rm-}\mathsf{Colorability}$ INPUT : An undirected graph $G$.
QUESTION : Is $G$ 3-colorable?

Our reduction is actually an adaptation of the standard reduction from
$3{\rm-}\mathsf{Colorability}$ for showing that CQ evaluation NP-hard.
Consider an undirected graph $G=(V,E)$. Let $\mathbf{S}_{G}$ be the schema

$\left\\{C^{u,v}/2,C^{v,u}/2\mid\\{u,v\\}\in E\right\\}.$

We define the database $D_{G}$ over $\mathbf{S}_{G}$ as follows:

$\left\\{C^{u,v}(i,j),C^{v,u}(i,j)\mid\\{u,v\\}\in E;\ i,j\in\\{1,2,3\\};\
i\neq j\right\\}.$

We further consider the set of primary keys $\Sigma$ to be empty and define
the (constant-free) Boolean CQ $Q_{G}$ as

$\textrm{Ans}()\ \text{:-}\ \bigwedge_{\\{u,v\\}\in
E}C^{u,v}(x_{u},x_{v})\wedge C^{v,u}(x_{v},x_{u}).$

Intuitively, the database stores all possible ways to colour the vertices of
an edge in different colours. Note that we store every edge twice since we do
not know in which order $u$ and $v$ occur in the edge. The role of the query
is to check whether there is a coherent mapping from vertices to colours
across all vertices.

Since $\Sigma$ is empty, the only repair of $D_{G}$ is $D_{G}$ itself.
Therefore, $\mathsf{RF}^{\mathsf{ur}}(D_{G},\Sigma,Q_{G},())=1>0$ iff
$D_{G}\models Q_{G}$. Hence, it remains to show that $G$ is 3-colorable iff
there exists a homomorphism
$h:\mathsf{var}(Q_{G})\rightarrow\mathsf{dom}(D_{G})$. We proceed to show the
latter equivalence:

$(\Rightarrow)$ Assume that $G$ is 3-colorable. Thus, there is a mapping
$\mu:V\rightarrow\\{1,2,3\\}$ such that for every edge $\\{u,v\\}\in E$ we
have that $\mu(u)\neq\mu(v)$. Now, consider the mapping
$h:\mathsf{var}(Q_{G})\rightarrow\\{1,2,3\\}$ such that, for every
$x_{v}\in\mathsf{var}(Q_{G})$, $h(x_{v})=\mu(v)$. We need to show that $h$ is
indeed a homomorphism from $Q_{G}$ to $D_{G}$. Consider an arbitrary edge
$\\{u,v\\}\in E$. We need to show that
$\\{C^{u,v}(h(x_{u}),h(x_{v})),C^{v,u}(h(x_{v}),h(x_{u}))\\}\subseteq D_{G}$,
which will imply that $h$ is indeed a homomorphism from $Q_{G}$ to $D_{G}$.
Since $\\{u,v\\}$ is an edge in $G$, we know that $\mu(u)\neq\mu(v)$; thus,
$h(x_{u})\neq h(x_{v})$. Hence,
$\\{C^{u,v}(h(x_{u}),h(x_{v})),C^{v,u}(h(x_{v}),h(x_{u}))\\}\subseteq D_{G}$,
as all possible combinations $h(x_{u}),h(x_{v})\in\\{1,2,3\\}$ with
$h(x_{u})\neq h(x_{v})$ are stored in the relations $C^{u,v}$ and $C^{v,u}$.

$(\Leftarrow)$ Conversely, assume there is a homomorphism
$h:\mathsf{var}(Q_{G})\rightarrow\mathsf{dom}(D_{G})$. Consider the mapping
$\mu:V\rightarrow\\{1,2,3\\}$ such that, for every $v\in V$,
$\mu(v)=h(x_{v})$. We show that $G$ is 3-colorable with $\mu$ being the
witnessing mapping. First, we note that $\mu$ is well-defined since there
exists exactly one variable $x_{v}$ for every vertex $v\in V$ that is reused
across the atoms representing different edges (and thus, making sure the
mapping is consistent across different edges). Consider an edge $\\{u,v\\}\in
E$. Since the variables $x_{u}$ and $x_{v}$ appear together in the query in
the atom $C^{u,v}(x_{u},x_{v})$, we know that $h$ is such that
$C^{u,v}(h(x_{u}),h(x_{v}))\in D_{G}$. By the construction of $D_{G}$, this
implies that $h(x_{u})\neq h(x_{v})$, and thus, $\mu(u)\neq\mu(v)$, as needed.

The Uniform Sequences Case

We use the same proof strategy and construction as in the uniform repairs
case. Consider the decision version of
$\mathsf{OCQA}^{\mathsf{us}}[\mathsf{SJF}]$, dubbed
$\mathsf{Pos}\mathsf{OCQA}^{\mathsf{us}}[\mathsf{SJF}]$, defined as expected:

PROBLEM : $\mathsf{Pos}\mathsf{OCQA}^{\mathsf{us}}[\mathsf{SJF}]$ INPUT : A
database $D$, a set $\Sigma$ of primary keys, a query $Q(\bar{x})$ from
$\mathsf{SJF}$, a tuple $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$. QUESTION :
$\mathsf{RF}^{\mathsf{us}}(D,\Sigma,Q,\bar{c})>0$.

We show that $\mathsf{Pos}\mathsf{OCQA}^{\mathsf{us}}[\mathsf{SJF}]$ is NP-
hard, which in turn implies that $\mathsf{OCQA}^{\mathsf{us}}[\mathsf{SJF}]$
does not admit an FPRAS, under the assumption that ${\rm RP}$ and ${\rm NP}$
are different. For an undirected graph $G$, let $\mathbf{S}_{G}$, $D_{G}$, and
$Q_{G}$ be the schema, database, and Boolean CQ from the construction in the
proof of the uniform repairs case. Again, the set $\Sigma$ of keys is
considered to be empty. Hence, we only have the empty repairing sequence,
denoted $\varepsilon$, with $\varepsilon(D_{G})=D_{G}$. It is easy to see that
$\mathsf{RF}^{\mathsf{ur}}(D_{G},\Sigma,Q_{G},\bar{c})=\mathsf{RF}^{\mathsf{us}}(D_{G},\Sigma,Q_{G},\bar{c})$.
This implies that $\mathsf{RF}^{\mathsf{us}}(D_{G},\Sigma,Q_{G},\bar{c})=1>0$
iff $G$ is 3-colorable, as needed.

###  B.2. Item (2)

The Uniform Repairs Case

A Boolean formula $\varphi$ in Pos2CNF is of the form
$\bigwedge_{i\in[m]}C_{i}$, where $C_{i}=v_{1}^{i}\vee v_{2}^{i}$ with
$v_{1}^{i},v_{2}^{i}$, for each $i\in[m]$, being Boolean variables. We write
$\mathsf{var}(\varphi)$ for the set of variables occurring in $\varphi$ and
$\sharp\varphi$ for the number of satisfying assignments of $\varphi$. We
consider the following decision problem:

PROBLEM : $\sharp\mathsf{MON2SAT}$ INPUT : A formula $\varphi$ in Pos2CNF.
OUTPUT : $\sharp\varphi$.

It is known that $\sharp\mathsf{MON2SAT}$ does not admit an FPRAS, unless
${\rm NP}={\rm RP}$ (Downey and Hirschfeldt, 2001). Fix an arbitrary $k>0$. We
show via an approximation preserving reduction from $\sharp\mathsf{MON2SAT}$
that also $\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{GHW}_{k}]$ does not admit an
FPRAS, unless ${\rm NP}={\rm RP}$. Given a Pos2CNF formula
$\varphi=\bigwedge_{i\in[m]}C_{i}$, let $\mathbf{S}_{\varphi}$ be the schema

$\\{C_{i}/2\mid i\in[m]\\}\cup\\{\mathsf{Var}_{v}/1\mid
v\in\mathsf{var}(\varphi)\\}\cup\\{V/2,E/2\\}$

with $(A,B)$ being the tuple of attributes of relation $V$. We define the
database $D_{\varphi}^{k}$ as

$\displaystyle\\{C_{i}(v_{1}^{i},1),C_{i}(v_{2}^{i},1)\mid i\in[m]\\}$
$\displaystyle\cup$ $\displaystyle\\{\mathsf{Var}_{v}(v)\mid
v\in\mathsf{var}(\varphi)\\}$ $\displaystyle\cup$
$\displaystyle\\{V(v,0),V(v,1)\mid v\in\mathsf{var}(\varphi)\\}$
$\displaystyle\cup$ $\displaystyle\\{E(i,j)\mid i,j\in[k+1],\ i<j\\}.$

Let $\Sigma$ be the singleton set of keys consisting of

$\mathsf{key}(V)=\\{1\\}.$

We finally define the Boolean CQ $Q_{\varphi}^{k}$ as $\textrm{Ans}()\
\text{:-}\ \psi_{1}\wedge\psi_{2}\wedge\psi_{3}$, where

$\displaystyle\psi_{1}\ $ $\displaystyle=\
\bigwedge_{i\in[m]}C_{i}(x_{i},y_{i})\wedge V(x_{i},y_{i}),$
$\displaystyle\psi_{2}\ $ $\displaystyle=\
\bigwedge_{v\in\mathsf{var}(\varphi)}\mathsf{Var}_{v}(z_{v})\wedge
V(z_{v},\\_),$ $\displaystyle\psi_{3}\ $ $\displaystyle=\
\bigwedge_{\begin{subarray}{c}i,j\in[k+1]\\\
i<j\end{subarray}}E(w_{i},w_{j}).$

We use $\\_$ to denote a variable that occurs only once. Note that $\psi_{1}$
and $\psi_{2}$ are acyclic subqueries, whereas $\psi_{3}$ encodes a clique of
size $k+1$ and has generalized hypertreewidth $k$. Since $\psi_{1}$,
$\psi_{2}$, and $\psi_{3}$ do not share variable, we can conclude that
$Q_{\varphi}^{k}$ has generalized hypertreewidth $k$. Note that the sole
purpose of the relation $E$ and the subquery $\psi_{3}$ is to force the
generalized hypertreewidth of $Q_{\varphi}^{k}$ to be $k$. It is clear that
since this part of $Q_{\varphi}^{k}$ will be satisfied in every repair of
$D_{\varphi}^{k}$. Intuitively, $\psi_{1}$ ensures that the repair satisfying
the query entails an assignment to the variables such that $\varphi$ is
satisfied, $\psi_{2}$ ensures that a repair entailing the query encodes some
variable assignment for every variable $v$ occurring in $\varphi$, and
$\psi_{3}$, as said above, ensures that $Q_{\varphi}^{k}$ has generalized
hypertreewidth $k$.

Let $n=|\mathsf{var}(\varphi)|$. It is clear that there are $3^{n}$
operational repairs of $D_{\varphi}^{k}$ since for every
$v\in\mathsf{var}(\varphi)$ we can either keep $V(v,0)$ and remove $V(v,1)$ in
the repair, or we keep $V(v,1)$ and remove $V(v,0)$, or we remove both facts
in the repair. Hence, $|\mathsf{ORep}(D_{\varphi}^{k},\Sigma)|=3^{n}$.

We proceed to show that $|\\{D\in\mathsf{ORep}(D_{\varphi}^{k},\Sigma)\mid
D\models Q_{\varphi}^{k}\\}|=\sharp\varphi$. To this end, let
$\mathsf{sat}(\varphi)$ be the set of satisfying assignments from the
variables of $\varphi$ to $\\{0,1\\}$. We will show that there exists a
bijection from the set $\mathsf{sat}(\varphi)$ to the set
$\\{D\in\mathsf{ORep}(D_{\varphi}^{k},\Sigma)\mid D\models
Q_{\varphi}^{k}\\}$. We define the mapping $\mu$ as follows: for each
$h\in\mathsf{sat}(\varphi)$,

$\displaystyle\mu(h)\ =\ $ $\displaystyle\\{V(v,0)\mid
v\in\mathsf{var}(\varphi)\text{ and }h(v)=0\\}$ $\displaystyle\cup\
\\{V(v,1)\mid v\in\mathsf{var}(\varphi)\text{ and }h(v)=1\\}$
$\displaystyle\cup\ \\{C_{i}(v_{1}^{i},1),C_{i}(v_{2}^{i},1)\mid i\in[m]\\}$
$\displaystyle\cup\ \\{\mathsf{Var}_{v}(v)\mid v\in\mathsf{var}(\varphi)\\}$
$\displaystyle\cup\ \\{E(i,j)\mid i,j\in[k+1],\ i<j\\}.$

We proceed to show the following three statements:

  1. (1)

$\mu$ is correct, that is, it is indeed a function from
$\mathsf{sat}(\varphi)$ to $\\{D\in\mathsf{ORep}(D_{\varphi}^{k},\Sigma)\mid
D\models Q_{\varphi}^{k}\\}$.

  2. (2)

$\mu$ is injective.

  3. (3)

$\mu$ is surjective.

#### The mapping $\mu$ is correct.

Consider an arbitrary satisfying assignment $h\in\mathsf{sat}(\varphi)$. We
need to show that there exists a $(D_{\varphi}^{k},\Sigma)$-repairing sequence
$s_{h}$ such that $\mu(h)=s_{h}(D_{\varphi}^{k})$,
$s_{h}(D_{\varphi}^{k})\models\Sigma$ (i.e., $s_{h}$ is complete), and
$s_{h}(D_{\varphi}^{k})\models Q_{\varphi}^{k}$ (i.e., the resulting repair
entails the query). Let $\mathsf{var}(\varphi)=\\{v_{1},\ldots,v_{n}\\}$.
Consider the sequence $s_{h}=\mathit{op}_{1},\ldots,\mathit{op}_{n}$ such
that, for every $i\in[n]$:

$\mathit{op}_{i}\ =\ \begin{cases}-V(v_{i},1)&\text{if }h(v_{i})=0\\\
-V(v_{i},0)&\text{if }h(v_{i})=1.\end{cases}$

In simple words, the homomorphism $h$ guides the repairing process, i.e.,
$h(v_{i})=0$ (resp., $h(v_{i})=1$) implies $V(v_{i},0)$ (resp., $V(v_{i},1)$)
should be kept in the repair. It is easy to verify that $s_{h}$ is indeed a
$(D_{\varphi}^{k},\Sigma)$-repairing sequence, such that
$\mu(h)=s_{h}(D_{\varphi}^{k})$ and $s_{h}(D_{\varphi}^{k})\models\Sigma$. To
show that $s_{h}(D_{\varphi}^{k})\models Q_{\varphi}^{k}$ it suffices to see
that each of the subqueries $\psi_{1}$, $\psi_{2}$, and $\psi_{3}$ is
satisfied in $s_{h}(D_{\varphi}^{k})$. Since $h$ is a satisfying assignment of
the variables of $\varphi$, we know that for every clause $C_{i}$, where
$i\in[m]$, one of its variables $v_{1}^{i}$ or $v_{2}^{i}$ evaluates to $1$
under $h$, i.e. $h(v_{l}^{i})=1$ for some $l\in\\{1,2\\}$. Hence, for every
$i\in[m]$ and (at least) one $l\in\\{1,2\\}$, we have that
$C_{i}(v_{l}^{i},1)$ and $V(v_{l}^{i},1)$ remains in the repair
$s_{h}(D_{\varphi}^{k})$ and thus $\psi_{1}$ is satisfied. To see that
$\psi_{2}$ is satisfied as well it suffices to see that for every variable
$v\in\mathsf{var}(\varphi)$ either $V(v,0)$ or $V(v,1)$ is kept in the repair
and the relation $\mathsf{Var}_{v}$ remains untouched by the repairing
sequence. Since the relation $E$ remains also unchanged in every repair, it is
clear that $\psi_{3}$ is also satisfied. We can therefore conclude that
$s_{h}(D_{\varphi}^{k})\models Q_{\varphi}^{k}$.

#### The mapping $\mu$ is injective.

Assume that there are two distinct satisfying assignments
$h,h^{\prime}\in\mathsf{sat}(\varphi)$ such that $\mu(h)=\mu(h^{\prime})$. By
the definition of $\mu$, we get that $h(v)=h^{\prime}(v)$, for every
$v\in\mathsf{var}(\varphi)$. But this contradicts the fact that $h$ and
$h^{\prime}$ are different satisfying assignments of the variables in
$\varphi$. Therefore, for every two distinct satisfying assignments
$h,h^{\prime}\in\mathsf{sat}(\varphi)$, $\mu(h)\neq\mu(h^{\prime})$, as
needed.

#### The mapping $\mu$ is surjective.

Consider an arbitrary operational repair
$D\in\mathsf{ORep}(D_{\varphi}^{k},\Sigma)$ such that $D\models
Q_{\varphi}^{k}\\}$. We need to show that there exists some
$h\in\mathsf{sat}(\varphi)$ such that $\mu(h)=D$. Note that, since $D\models
Q_{\varphi}^{k}$, necessarily the subquery $\psi_{2}$ must also be satisfied
in $D$. In other words, for every variable $v\in\mathsf{var}(\varphi)$ either
$V(v,0)\in D$ or $V(v,1)\in D$ (and never both since $D\models\Sigma$). We
define the mapping $h_{D}:\mathsf{var}(\varphi)\rightarrow\\{0,1\\}$ as
follows: for every $v\in\mathsf{var}(\varphi)$:

$h_{D}(v)\ =\ \begin{cases}1&\text{if }V(v,1)\in D\\\ 0&\text{if }V(v,0)\in
D.\end{cases}$

It is clear that $h_{D}$ is well-defined: for every
$v\in\mathsf{var}(\varphi)$, $h_{D}(v)=x$ and $h_{D}(v)=y$ implies $x=y$. It
is also clear that $\mu(h_{D})=D$. The fact that
$h_{D}\in\mathsf{sat}(\varphi)$ follows directly from the fact that $D$
entails the subquery $\psi_{1}$. Since, for every $i\in[m]$ and some
$l\in\\{1,2\\}$, $V(v_{l}^{i},1)\in D$ and thus $h_{D}(v_{l}^{i})=1$, for
every $C_{i}$, where $i\in[m]$, one of its literals evaluates to true under
$h_{D}$ and thus $h_{D}\in\mathsf{sat}(\varphi)$.

Summing up, recall that the repair relative frequency is the ratio

$\mathsf{RF}^{\mathsf{ur}}(D_{\varphi}^{k},\Sigma,Q_{\varphi}^{k},())=\frac{|\\{D\in\mathsf{ORep}(D_{\varphi}^{k},\Sigma)\mid
D\models
Q_{\varphi}^{k}\\}|}{|\mathsf{ORep}(D_{\varphi}^{k},\Sigma)|}=\frac{\sharp\varphi}{3^{n}}.$

Hence, assuming an FPRAS $A$ for the problem
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{GHW}_{k}]$, we can build an FPRAS
$A^{\prime}$ for $\sharp\mathsf{MON2SAT}$ by simply running $A$ on the input
$(D_{\varphi}^{k},\Sigma,Q_{\varphi}^{k},\varepsilon,\delta)$ and returning
its result multiplied by $3^{n}$. We note that $A^{\prime}$ is an FPRAS for
$\sharp\mathsf{MON2SAT}$ with the same probabilistic guarantees $\varepsilon$
and $\delta$, contradicting the assumption ${\rm NP}\neq{\rm RP}$. Thus,
$\mathsf{OCQA}^{\mathsf{ur}}[\mathsf{GHW}_{k}]$ does not admit an FPRAS,
unless ${\rm NP}={\rm RP}$.

The Uniform Sequences Case

Fix $k>0$. For proving the desired claim, it suffices to show that

$\mathsf{RF}^{\mathsf{ur}}(D_{\varphi}^{k},\Sigma,Q_{\varphi}^{k},())\ =\
\mathsf{RF}^{\mathsf{us}}(D_{\varphi}^{k},\Sigma,Q_{\varphi}^{k},()).$

We can then easily use the same construction from the proof for the uniform
repairs case to show that there cannot exist an FPRAS for
$\mathsf{OCQA}^{\mathsf{us}}[\mathsf{GHW}_{k}]$, as this would imply the
existence of an FPRAS for $\sharp\mathsf{MON2SAT}$, which contradicts the
assumption ${\rm NP}\neq{\rm RP}$.

For a Pos2CNF formula $\varphi$, let $\mathbf{S}_{\varphi}$,
$D_{\varphi}^{k}$, $\Sigma$, and $Q_{\varphi}^{k}$ be the schema, database,
set of keys, and CQ, respectively, from the construction in the proof for the
uniform repairs case. Further, let $n=\mathsf{var}(\varphi)$. Since every
complete repairing sequence of $D_{\varphi}^{k}$ consists of $n$ operations,
one to resolve each violation of the form $\\{V(v,0),V(v,1)\\}$ for every
$v\in\mathsf{var}(\varphi)$, and the fact that these operations can be applied
in any order, it is easy to verify that

$|\mathsf{CRS}(D_{\varphi}^{k},\Sigma)|\ =\
|\mathsf{ORep}(D_{\varphi}^{k},\Sigma)|\cdot n!$

and

$\displaystyle|\\{s\in\mathsf{CRS}(D_{\varphi}^{k},\Sigma)\mid
s(D_{\varphi}^{k})\models Q_{\varphi}^{k}\\}|$ $\displaystyle=$
$\displaystyle|\\{D\in\mathsf{ORep}(D_{\varphi}^{k},\Sigma)\mid D\models
Q_{\varphi}^{k}\\}|\cdot n!.$

Hence,

$\displaystyle\mathsf{RF}^{\mathsf{us}}(D_{\varphi}^{k},\Sigma,Q_{\varphi}^{k},())$
$\displaystyle=$
$\displaystyle\frac{|\\{D\in\mathsf{ORep}(D_{\varphi}^{k},\Sigma)\mid D\models
Q_{\varphi}^{k}\\}|\cdot n!}{|\mathsf{ORep}(D_{\varphi}^{k},\Sigma)|\cdot n!}$
$\displaystyle=$
$\displaystyle\frac{|\\{D\in\mathsf{ORep}(D_{\varphi}^{k},\Sigma)\mid D\models
Q_{\varphi}^{k}\\}|}{|\mathsf{ORep}(D_{\varphi}^{k},\Sigma)|}$
$\displaystyle=$ $\displaystyle\frac{\sharp\varphi}{3^{n}}$ $\displaystyle=$
$\displaystyle\mathsf{RF}^{\mathsf{ur}}(D_{\varphi}^{k},\Sigma,Q_{\varphi}^{k},()),$

and the claim follows.

##  Appendix C Proof of Proposition 4.5

We proceed to show that:

###### Proposition 4.5.

$\mathsf{SpanTL}$ is closed under logspace reductions.

Consider two functions $f:\Lambda_{1}^{*}\rightarrow\mathbb{N}$ and
$g:\Lambda_{2}^{*}\rightarrow\mathbb{N}$, for some alphabets $\Lambda_{1}$ and
$\Lambda_{2}$, with $g\in\mathsf{SpanTL}$, and assume there is a logspace
computable function $h:\Lambda_{1}^{*}\rightarrow\Lambda_{2}^{*}$ with
$f(w)=g(h(w))$ for all $w\in\Lambda_{1}^{*}$. We prove that
$f\in\mathsf{SpanTL}$. The proof employees a standard argument used to prove
that logspace computable functions can be composed. It is well known that $h$
can be converted to a logspace computable function
$h^{\prime}:\Lambda_{1}^{*}\times\mathbb{N}\rightarrow\Lambda_{2}$ that, given
a string $w\in\Lambda_{1}^{*}$ and an integer $i\in[|h(w)|]$, where $|h(w)|$
denotes the length of the string $h(w)$, outputs the $i$-th symbol of $h(w)$,
and $h^{\prime}$ is computable in logspace (e.g., see (Arora and Barak,
2009)). This can be achieved by modifying $h$ so that it first initializes a
counter $k$ to $1$, and then, whenever it needs to write a symbol on the
output tape, it first checks whether $k=i$; if not, then it does not write
anything on the output tape, and increases $k$, otherwise, it writes the
required symbol, and then halts. The counter $k$ can be stored in logarithmic
space since $h$ works in logarithmic space, and thus $h(w)$ contains no more
than polynomially many symbols, i.e., $|h(w)|\in O(|w|^{c})$, for some
constant $c$.

With the above in place, proving that $f\in\mathsf{SpanTL}$ is
straightforward. Let $M$ be the well-behaved ATO such that
$g=\mathsf{span}_{M}$. We modify $M$ to another ATO $M^{\prime}$ such that
$f=\mathsf{span}_{M^{\prime}}$; again, this construction is rather standard,
but we give it here for the sake of completeness. In particular, we modify $M$
so that, with input a string $w$, it keeps a counter $k$ initialized to $1$,
and whenever $M$ needs to read the current symbol from the input tape, it
executes $h^{\prime}$ with input $(w,k)$, where its (single) output symbol
$\alpha$ is written on the working tape; then $M^{\prime}$ uses $\alpha$ as
the input symbol. Then, when the input tape head of $M$ moves to the right
(resp., left, stays), $M^{\prime}$ increases (resp., decreases, leaves
untouched) the counter $k$. The fact that $\mathsf{span}_{M^{\prime}}=g(h(w))$
follows by construction of $M^{\prime}$ and the fact that when executing
$h^{\prime}$, no symbols are written on the labeling tape, and no labeling
states of $M^{\prime}$ are visited. Hence, $\mathsf{span}_{M^{\prime}}=f(w)$.
To show that $f\in\mathsf{SpanTL}$, it remains to to prove that $M^{\prime}$
is well-behaved.

Obviously, since $h^{\prime}$ is computable in logspace, $M^{\prime}$ can
execute $h^{\prime}$ using no more than logarithmic space w.r.t. $|w|$ on its
working tape. Moreover, while executing $h^{\prime}$, $M^{\prime}$ does not
need to write anything on the labeling tape, and thus, $M^{\prime}$ uses no
more space than the one that $M$ uses on the labeling tape. Furthermore,
storing $k$ requires logarithmic space since $k\in[|h(w)|]$ can be encoded in
binary. Since $h^{\prime}$ is computable in (deterministic) logspace, an
execution of $h^{\prime}$ corresponds to a sequence of polynomially many (non-
labeling) existential configurations in a computation of $M^{\prime}$ with
input $w$. Hence, each computation $T^{\prime}$ of $M^{\prime}$ corresponds to
a computation $T$ of $M$, where, in the worst case, each node of $T$ becomes a
polynomially long path in $T^{\prime}$; hence, $T^{\prime}$ is of polynomial
size w.r.t. $|w|$. Finally, since, as already discussed, each execution of
$h^{\prime}$ coincides with a sequence of non-labeling _existential_
configurations, the maximum number of non-labeling universal configurations on
a labeled-free path of any computation of $M^{\prime}$ is the same as the one
for $M$, and thus remains a constant. Consequently, $M^{\prime}$ is well-
behaved.

##  Appendix D Proof of Theorem 4.6

We proceed to prove the following result:

###### Theorem 4.6.

Every function $f\in\mathsf{SpanTL}$ admits an FPRAS.

As discussed in the main body, to establish the above result we exploit a
recent result showing that the problem of counting the number of trees of a
certain size accepted by a non-deterministic finite tree automaton admits an
FPRAS (Arenas et al., 2021b). In particular, we reduce in polynomial time each
function in $\mathsf{SpanTL}$ to the above counting problem for tree automata.
In what follows, we recall the basics about non-deterministic finite tree
automata and the associated counting problem, and then give our reduction.

#### Ordered Trees and Tree Automata.

For an integer $k\geq 1$, a finite ordered $k$-tree (or simply $k$-tree) is a
prefix-closed non-empty finite subset $T$ of $[k]^{*}$, that is, if $w\cdot
i\in T$ with $w\in[k]^{*}$ and $i\in[k]$, then $w\cdot j\in T$ for every
$w\in[i]$. The root of $T$ is the empty string, and every maximal element of
$T$ (under prefix ordered) is a leaf. For every $u,v\in T$, we say that $u$ is
a child of $v$, or $v$ is a parent of $u$, if $u=v\cdot i$ for some $i\in[k]$.
The size of $T$ is $|T|$. Given a finite alphabet $\Lambda$, let
$\mathsf{trees}_{k}[\Lambda]$ be the set of all $k$-trees in which each node
is labeled with a symbol from $\Lambda$. By abuse of notation, for
$T\in\mathsf{trees}_{k}[\Lambda]$ and $u\in T$, we write $T(u)$ for the label
of $u$ in $T$.

A (top-down) non-deterministic finite tree automation (NFTA) over
$\mathsf{trees}_{k}[\Lambda]$ is a tuple $A=(S,\Lambda,s_{\text{\rm
init}},\delta)$, where $S$ is the finite set of states of $A$, $\Lambda$ is a
finite set of symbols (the alphabet of $A$), $s_{\text{\rm init}}\in S$ is the
initial state of $A$, and $\delta\subseteq
S\times\Lambda\times\left(\bigcup_{i=0}^{k}S^{k}\right)$ is the transition
relation of $A$. A run of $A$ over a tree $T\in\mathsf{trees}_{k}[\Lambda]$ is
a function $\rho:T\rightarrow S$ such that, for every $u\in T$, if $u\cdot
1,\ldots,u\cdot n$ are the children of $u$ in $T$, then
$(\rho(u),T(u),(\rho(u\cdot 1),\ldots,\rho(u\cdot n)))\in\delta$. In
particular, if $u$ is a leaf, then $(\rho(u),T(u),())\in\delta$. We say that
$A$ accepts $T$ if there is a run $\rho$ of $A$ over $T$ with
$\rho(\epsilon)=s_{\text{\rm init}}$, i.e., $\rho$ assigns to the root the
initial state. We write $L(A)\subseteq\mathsf{trees}_{k}[\Lambda]$ for the set
of all trees accepted by $A$, i.e., the language of $A$. We further write
$L_{n}(A)$ for the set of trees $\\{T\in L(A)\mid|T|=n\\}$, i.e., the set of
trees of size $n$ accepted by $A$. The relevant counting problem for NFTA
follows:

PROBLEM : $\sharp\mathsf{NFTA}$ INPUT : An NFTA $A$ and a string $0^{n}$ for
some $n\geq 0$. OUTPUT : $\left|\bigcup_{i=0}^{n}L_{i}(A)\right|$.

The notion of FPRAS for $\sharp\mathsf{NFTA}$ is defined in the obvious way.
We know from (Arenas et al., 2021b) that $\sharp\mathsf{NFTA}_{=}$, defined as
$\sharp\mathsf{NFTA}$ with the difference that it asks for $|L_{n}(A)|$, i.e.,
the number trees of size $n$ accepted by $A$, admits an FPRAS. By using this
result, we can easily show that:

###### Theorem D.1.

$\sharp\mathsf{NFTA}$ admits an FPRAS.

###### Proof.

The goal is to devise a randomized algorithm $\mathsf{A}$ that takes as input
an NFTA $A$, a string $0^{n}$, with $n\geq 0$, $\epsilon>0$ and $0<\delta<1$,
runs in polynomial time in $||A||$, $n$, $1/\epsilon$ and $\log(1/\delta)$,
and produces a random variable $\mathsf{A}(A,0^{n},\epsilon,\delta)$ such that

$\text{\rm
Pr}\left(\left|\mathsf{A}(A,0^{n},\epsilon,\delta)-L_{0}^{n}\right|\ \leq\
\epsilon\cdot L_{0}^{n}\right)\ \geq\ 1-\delta,$

where $L_{0}^{n}=\left|\bigcup_{i=0}^{n}L_{i}(A)\right|$, or equivalently

$\text{\rm Pr}\left((1-\epsilon)\cdot L_{0}^{n}\
\leq\mathsf{A}(A,0^{n},\epsilon,\delta)\ \leq\ (1+\epsilon)\cdot
L_{0}^{n}\right)\ \geq\ 1-\delta.$

We know from (Arenas et al., 2021b) that the problem $\sharp\mathsf{NFTA}_{=}$
admits an FPRAS. This means that there is a randomized algorithm $B$ that
takes as input an NFTA $A$, a string $0^{n}$, with $n\geq 0$, $\epsilon>0$ and
$0<\delta<1$, runs in polynomial time in $||A||$, $n$, $1/\epsilon$ and
$\log(1/\delta)$, and produces a random variable
$\mathsf{B}(A,0^{n},\epsilon,\delta)$ such that

$\text{\rm Pr}\left((1-\epsilon)\cdot|L_{n}(A)|\
\leq\mathsf{B}(A,0^{n},\epsilon,\delta)\ \leq\
(1+\epsilon)\cdot|L_{n}(A)|\right)\ \geq\ 1-\delta.$

The desired randomized algorithm $\mathsf{A}$ is defined in such a way that,
on input $A$, $0^{n}$, $\epsilon$ and $\delta$, returns the number

$\sum_{i=0}^{n}\mathsf{B}\left(A,0^{i},\epsilon,\frac{\delta}{2(n+1)}\right).$

Note that the $n+1$ runs of $\mathsf{B}$ in the expression above are all
independent, and thus, the random variables
$\mathsf{B}\left(A,0^{i},\epsilon,\frac{\delta}{2(n+1)}\right)$ and
$\mathsf{B}\left(A,0^{j},\epsilon,\frac{\delta}{2(n+1)}\right)$ are
independent, for $i,j\in\\{0,\ldots,n\\}$, with $i\neq j$; it is also clear
that

$\sum_{i=0}^{n}\left|L_{i}(A)\right|\ =\
\left|\bigcup_{i=0}^{n}L_{i}(A)\right|$

since $L_{i}(A)\cap L_{j}(A)=\emptyset$. Therefore, we get that

$\text{\rm Pr}\bigg{(}\left(1-\epsilon\right)\cdot L_{0}^{n}\
\leq\mathsf{A}(A,0^{n},\epsilon,\delta)\ \leq\ \left(1+\epsilon\right)\cdot
L_{0}^{n}\bigg{)}\ \geq\\\ \left(1-\frac{\delta}{2(n+1)}\right)^{n+1}.$

We know that the following inequality hold (see, e.g., (Jerrum et al., 1986))
for $0\leq x\leq 1$ and $m\geq 1$,

$1-x\ \leq\ \left(1-\frac{x}{2m}\right)^{m}.$

Consequently,

$\text{\rm Pr}\left((1-\epsilon)\cdot L_{0}^{n}\
\leq\mathsf{A}(A,0^{n},\epsilon,\delta)\ \leq\ (1+\epsilon)\cdot
L_{0}^{n}\right)\ \geq\ 1-\delta,$

as needed. It is also clear that $\mathsf{A}$ runs in polynomial time in
$||A||$, $n$, $1/\epsilon$ and $\log(1/\delta)$, since $\mathsf{B}$ runs in
polynomial time in $||A||$, $i$, $1/\epsilon$ and $\log(1/\delta)$, for each
$i\in\\{0,\ldots,n\\}$, and the claim follows.

#### The Reduction.

Recall that our goal is reduce in polynomial time every function of
$\mathsf{SpanTL}$ to $\sharp\mathsf{NFTA}$, which, together with Theorem D.1,
will immediately imply Theorem 4.6. In particular, we need to establish the
following technical result:

###### Proposition D.2.

Fix a function $f:\Lambda^{*}\rightarrow\mathbb{N}$ of $\mathsf{SpanTL}$. For
every $w\in\Lambda^{*}$, we can construct in polynomial time in $|w|$ an NFTA
$A$ and a string $0^{n}$, for some $n\geq 0$, such that
$f(w)=\left|\bigcup_{i=0}^{n}L_{i}(A)\right|$.

We proceed to show the above proposition. Since, by hypothesis,
$f:\Lambda^{*}\rightarrow\mathbb{N}$ belongs to $\mathsf{SpanTL}$, there
exists a well-behaved ATO $M=(S,\Lambda^{\prime},s_{\text{\rm
init}},s_{\text{\rm accept}},s_{\text{\rm
reject}},S_{\exists},S_{\forall},S_{L},\delta)$, where
$\Lambda^{\prime}=\Lambda\cup\\{\bot,\triangleright\\}$ and
$\bot,\triangleright\not\in\Lambda$, such that $f$ is the function
$\mathsf{span}_{M}$. The goal is, for an arbitrary string $w\in\Lambda^{*}$,
to construct in polynomial time in $|w|$ an NFTA
$A=(S^{A},\Lambda^{A},s_{\text{\rm init}}^{A}\delta^{A})$ and a string
$0^{n}$, for some $n\geq 0$, such that
$\mathsf{span}_{M}(w)=|\bigcup_{i=0}^{n}L_{i}(A)|$. This is done in two steps:

  1. (1)

We first construct an NFTA $A$ in polynomial time in $|w|$ such that
$\mathsf{span}_{M}(w)=|L(A)|$, i.e., $A$ accepts $\mathsf{span}_{M}(w)$ trees.

  2. (2)

We show that $L(A)=\bigcup_{i=0}^{\mathsf{pol}(|w|)}L_{i}(A)$ for some
polynomial function $\mathsf{pol}:\mathbb{N}\rightarrow\mathbb{N}$.

After completing the above two steps, it is clear that Proposition D.2 follows
with $n=\mathsf{pol}(|w|)$. Let us now discuss the above two steps.

#### Step 1: The NFTA

For the construction of the desired NFTA, we first need to introduce the
auxiliary notion of the computation directed acyclic graph (DAG) of the ATO
$M$ on input $w\in\Lambda^{*}$, which compactly represents all the
computations of $M$ on $w$. Recall that a DAG $G$ is rooted if it has exactly
one node, the root, with no incoming edges. We also say that a node of $G$ is
a leaf if it has no outgoing edges.

###### Definition D.3 (Computation DAG).

The computation DAG of $M$ on input $w\in\Lambda^{*}$ is the DAG
$G=(\mathcal{C},\mathcal{E})$, where $\mathcal{C}$ is the set of
configurations of $M$ on $w$, defined as follows:

  1. -

if $C\in\mathcal{C}$ is the root node of $G$, then $C$ is the initial
configuration of $M$ on input $w$,

  2. -

if $C\in\mathcal{C}$ is a leaf node of $G$, then $C$ is either an accepting or
a rejecting configuration of $M$, and

  3. -

if $C\in\mathcal{C}$ is a non-leaf node of $G$ with
$C\rightarrow_{M}\\{C_{1},\ldots,C_{n}\\}$ for $n>0$, then (i) for each
$i\in[n]$, $(C,C_{i})\in\mathcal{E}$, and (ii) for every configuration
$C^{\prime}\not\in\\{C_{1},\ldots,C_{n}\\}$ of $M$ on $w$,
$(C,C^{\prime})\not\in\mathcal{E}$.

As said above, the computation DAG $G$ of $M$ on input $w$ compactly
represents all the computations of $M$ on $w$. In particular, a computation
$(V,E,\lambda)$ of $M$ on $w$ can be constructed from $G$ by traversing $G$
from the root to the leaves and (i) for every universal configuration $C$ with
outgoing edges $(C,C_{1}),\dots,(C,C_{n})$, add a node $v$ with $\lambda(v)=C$
and children $u_{1},\dots,u_{n}$ with $\lambda(u_{i})=C_{i}$ for all
$i\in[n]$, and (ii) for every existential configuration $C$ with outgoing
edges $(C,C_{1}),\dots,(C,C_{n})$, add a node $v$ with $\lambda(v)=C$ and a
single child $u$ with $\lambda(u)=C_{i}$ for some $i\in[n]$.

The construction of the NFTA $A$ is performed by $\mathsf{BuildNFTA}$,
depicted in Algorithm 3, which takes as input a string $w\in\Lambda^{*}$. It
first constructs the computation DAG $G=(\mathcal{C},\mathcal{E})$ of $M$ on
$w$, which will guide the construction of $A$. It then initializes the sets
$S^{A},\Lambda^{A},\delta^{A}$, as well as the auxiliary set $Q$, which will
collect pairs of the form $(C,U)$, where $C$ is a configuration of
$\mathcal{C}$ and $U$ a set of tuples of states of $A$, to empty. Then, it
calls the recursive procedure $\mathsf{Process}$, depicted in Algorithm 4,
which constructs the set of states $S^{A}$, the alphabet $\Lambda^{A}$, and
the transition relation $\delta^{A}$, while traversing the computation DAG $G$
from the root to the leaves. Here, $S^{A}$, $\Lambda^{A}$, $\delta^{A}$, $G$,
and $Q$ should be seen as global structures that can be used and updated
inside the procedure $\mathsf{Process}$. Eventually,
$\mathsf{Process}(\mathsf{root}(G))$ returns a state $s\in S^{A}$, which acts
as the initial state of $A$, and $\mathsf{BuildNFTA}(w)$ returns the NFTA
$(S^{A},\Lambda^{A},s,\delta^{A})$.

Concerning the procedure $\mathsf{Process}$, when we process a labeling
configuration $C\in\mathcal{C}$, we add to $S^{A}$ a state $s_{C}$
representing $C$. Then, for every computation $T=(V,E,\lambda)$ of $M$ on $w$,
if $V$ has a node $v$ with $u_{1},\dots,u_{n}$ being the nodes reachable from
$v$ via a labeled-free path, and $\lambda(u_{i})$ is a labeling configuration
for every $i\in[n]$, we add the transition
$(s_{C},z,(s_{C_{1}},\dots,s_{C_{n}}))$ to $\delta^{A}$, where $\lambda(v)=C$,
$C$ is of the form $(\cdot,\cdot,\cdot,z,\cdot,\cdot)$, and
$\lambda(u_{i})=C_{i}$ for every $i\in[n]$, for some arbitrary order
$C_{1},\dots,C_{n}$ over those configurations. Since, by definition, the
output of $T$ has a node corresponding to $v$ with children corresponding to
$u_{1},\dots,u_{n}$, using these transitions we ensure that there is a one-to-
one correspondence between the outputs of $M$ on $w$ and the trees accepted by
$A$.

Now, when processing non-labeling configurations, we accumulate all the
information needed to add all these transitions to $\delta^{A}$. In
particular, the procedure $\mathsf{Process}$ always returns a set of tuples of
states of $S^{A}$. For labeling configurations $C$, it returns a single tuple
$(s_{C})$, but for non-labeling configurations $C$, the returned set depends
on the outgoing edges $(C,C_{1}),\dots,(C,C_{n})$ of $C$. In particular, if
$C$ is an existential configuration, it simply takes the union $P$ of the sets
$P_{i}$ returned by $\mathsf{Process}(C_{i})$, for $i\in[n]$, because in every
computation of $M$ on $w$ we choose only one child of each node associated
with an existential configuration; each $P_{i}$ represents one such choice.
If, on the other hand, $C$ is a universal configuration, then $P$ is the set
$\bigotimes_{i\in[n]}P_{i}$ obtained by first computing the cartesian product
$P^{\prime}=\bigtimes_{i\in[n]}P_{i}$ and then merging each tuple of
$P^{\prime}$ into a single tuple of states of $S^{A}$. For example, with
$P_{1}=\\{(),(s_{1},s_{2}),(s_{3})\\}$ and
$P_{2}=\\{(s_{5}),(s_{6},s_{7})\\}$, $P_{1}\otimes P_{2}$ is the set
$\\{(s_{5}),(s_{6},s_{7}),(s_{1},s_{2},s_{5}),(s_{1},s_{2},s_{6},s_{7}),(s_{3},s_{5}),(s_{3},s_{6},s_{7})\\}$.
We define $\bigotimes_{i\in[n]}P_{i}=\emptyset$ if $P_{i}=\emptyset$ for some
$i\in[n]$. We use the $\otimes$ operator since in every computation of $M$ on
$w$ we choose all the children of each node associated with a universal
configuration. When we reach a labeling configuration $C\in\mathcal{C}$, we
add transitions to $\delta^{A}$ based on this accumulated information. In
particular, we add a transition from $s_{C}$ to every tuple
$(s_{1},\dots,s_{\ell})$ of states in $P$.

Concerning the running time of $\mathsf{BuildNFTA}(w)$, we first observe that
the size (number of nodes) of the computation DAG $G$ of $M$ on input $w$ is
polynomial in $|w|$. This holds since for each configuration
$(\cdot,\cdot,y,z,\cdot,\cdot,\cdot)$ of $M$ on $w$, we have that $|y|,|z|\in
O(\log(|w|))$. Moreover, we can construct $G$ in polynomial time in $|w|$ by
first adding a node for the initial configuration of $M$ on $w$, and then
following the transition function to add the remaining configurations of $M$
on $w$ and the outgoing edges from each configuration. Now, in the procedure
$\mathsf{Process}$ we use the auxiliary set $Q$ to ensure that we process each
node of $G$ only once; thus, the number of calls to the $\mathsf{Process}$
procedure is polynomial in the size of $|w|$. Moreover, in
$\mathsf{Process}(C)$, where $C$ is a non-labeling universal configuration
that has $n$ outgoing edges $(C,C_{1}),\dots,(C,C_{n})$, the size of the set
$P$ is $|P_{1}|\times\dots\times|P_{n}|$, where
$P_{i}=\mathsf{Process}(C_{i})$ for $i\in[n]$. When we process a non-labeling
existential configuration $C$ that has $n$ outgoing edges
$(C,C_{1}),\dots,(C,C_{n})$, the size of the set $P$ is
$|P_{1}|+\dots+|P_{n}|$. We also have that $|P|=1$ for every labeling
configuration $C$. Hence, in principle, many universal states along a labeled-
free path could cause an exponential blow-up of the size of $P$. However,
since $M$ is a well-behaved ATO, there exists $k\geq 0$ such that every
labeled-free path of every computation $(V,E,\lambda)$ of $M$ on $w$ has at
most $k$ nodes $v$ for which $\lambda(v)$ is a universal configuration. It is
rather straightforward to see that every labeled-free path of $G$ also enjoys
this property since this path occurs in some computation of $M$ on $w$. Hence,
the size of the set $P$ is bounded by a polynomial in the size of $|w|$. From
the above discussion, we get that $\mathsf{BuildNFTA}(w)$ runs in polynomial
time in $|w|$, and the next lemma can be shown:

###### Lemma D.4.

For a string $w\in\Lambda^{*}$, $\mathsf{BuildNFTA}(w)$ runs in polynomial
time in $|w|$ and returns an NFTA $A$ such that $\text{\rm
span}_{M}(w)=|L(A)|$.

Before we give the full proof of Lemma D.4, let us discuss the rather easy
second step of the reduction.

Input: A string $w\in\Lambda^{*}$

Output: An NFTA $A$

1

2Construct the computation DAG $G=(\mathcal{C},\mathcal{E})$ of $M$ on $w$;

3 $S^{A}:=\emptyset$; $\Lambda^{A}:=\emptyset$; $\delta^{A}:=\emptyset$;
$Q:=\emptyset$;

4 $P:=\mathsf{Process}(\mathsf{root}(G))$;

5 Assuming $P=\\{(s)\\}$, $A:=\left(S^{A},\Lambda^{A},s,\delta^{A}\right)$;

return _$A$ ;_

Algorithm 3 The algorithm $\mathsf{BuildNFTA}$

Input: A configuration $C=(s,x,y,z,h_{x},h_{y})$ of $\mathcal{C}$

1 if  _$(C,U)\in Q$_ then

2 return $U$;

3if  _$C$ is a leaf of $G$_ then

4 if  _$s\in S_{L}$_ then

5 $S^{A}:=S^{A}\cup\\{s_{C}\\}$;

6 $\Lambda^{A}:=\Lambda\cup\\{z\\}$;

7 if  _$s=s_{\text{\rm accept}}$_ then

8 $\delta^{A}:=\delta^{A}\cup\\{(s_{C},z,())\\}$;

9 $Q:=Q\cup\\{(C,\\{(s_{C})\\})\\}$;

10 else if  _$s=s_{\text{\rm accept}}$_ then $Q:=Q\cup\\{(C,\\{()\\})\\}$

11 else $Q:=Q\cup\\{(C,\emptyset)\\}$

12

13else

14 let $C_{1},\dots,C_{n}$ be an arbitrary order over the nodes of $G$ with an
incoming edge from $C$;

15 foreach  _$i\in[n]$_ do $P_{i}:=\mathsf{Process}(C_{i})$

16 if  _$s\in S_{\exists}$_ then $P:=\bigcup_{i\in[n]}P_{i}$

17 else $P:=\bigotimes_{i\in[n]}P_{i}$

18 if  _$s\in S_{L}$_ then

19 $S^{A}:=S^{A}\cup\\{s_{C}\\}$;

20 $\Lambda^{A}:=\Lambda^{A}\cup\\{z\\}$;

21 foreach  _$(s_{1},\dots,s_{\ell})\in P$_ do

22 $\delta^{A}:=\delta^{A}\cup\\{(s_{C},z,(s_{1},\dots,s_{\ell}))\\}$;

23 $Q:=Q\cup\\{(C,\\{(s_{C})\\})\\}$;

24 else $Q:=Q\cup\\{(C,P)\\}$

25

return $U$ with $(C,U)\in Q$;

Algorithm 4 The recursive procedure $\mathsf{Process}$

#### Step 2: The Polynomial Function

Since $M$ is a well-behaved ATO, there exists a polynomial function
$\mathsf{pol}:\mathbb{N}\rightarrow\mathbb{N}$ such that the size of every
computation of $M$ on $w$ is bounded by $\mathsf{pol}(|w|)$. Clearly,
$\mathsf{pol}(|w|)$ is also a bound on the size of the valid outputs of $M$ on
$w$. From the proof of Lemma D.4, which is given below, it will be clear that
every tree accepted by $A$ has the same structure as some valid output of $M$
on $w$. Hence, we have that $\mathsf{pol}(|w|)$ is also a bound on the size of
the trees accepted by $A$, and the next lemma follows:

###### Lemma D.5.

It holds that $L(A)=\bigcup_{i=0}^{\mathsf{pol}(|w|)}L_{i}(A)$.

Proposition D.2 readily follows from Lemmas D.4 and D.5.

###  D.1. Proof of Lemma D.4

We now prove the following lemma.

###### Lemma D.4.

For a string $w\in\Lambda^{*}$, $\mathsf{BuildNFTA}(w)$ runs in polynomial
time in $|w|$ and returns an NFTA $A$ such that $\text{\rm
span}_{M}(w)=|L(A)|$.

We have already discussed the running time of $\mathsf{BuildNFTA(w)}$ and
shown that it runs in polynomial time in $|w|$. We proceed to show that there
is one-to-one correspondence between the valid outputs of $M$ on $w$ and the
$k$-trees accepted by $A$.

#### Valid Output to Accepted Tree.

Let $O=(V^{\prime},E^{\prime},\lambda^{\prime})$ be a valid output of $M$ on
$w$. Then, $O$ is the output of some accepting computation $T=(V,E,\lambda)$
of $M$ on $w$. For every node $v$ of $T$ with $\lambda(v)$ being a labeling
configuration, if $u_{1},\dots,u_{n}$ are the nodes associated with a labeling
configuration that are reachable from $v$ in $T$ via a labeled-free path, we
denote by $\succ_{v}$ the order defined over $u_{1},\dots,u_{n}$ in the
following way. For $i\neq j\in[n]$, let $v^{\prime}$ be the lowest common
ancestor of $u_{i},u_{j}$. Since $v$ is a common ancestor, clearly,
$v^{\prime}$ lies somewhere along the path from $v$ to $u_{i}$ (similarly, to
$u_{j}$). Now, let $w_{1}$ be the child of $v^{\prime}$ that is the ancestor
of $u_{i}$ (or $u_{i}$ itself if $v^{\prime}$ is the parent of $u_{i}$) and
let $w_{2}$ be the child of $v^{\prime}$ that is the ancestor of $u_{j}$ (or
$u_{j}$ itself if $v^{\prime}$ is the parent of $u_{j}$); clearly, $w_{1}\neq
w_{2}$. We define $u_{j}\succ_{v}u_{i}$ iff $\lambda(w_{1})$ occurs before
$\lambda(w_{2})$ in the order defined over the nodes with an incoming edge
from $\lambda(v^{\prime})$ in line 13 of
$\mathsf{Process}(\lambda(v^{\prime}))$ (inside $\mathsf{BuildNFTA}(w)$).
Clearly, this induces a total order $\succ_{v}$ over $u_{1},\dots,u_{n}$. We
will show that the $k$-tree $\tau$ inductively defined as follows is accepted
by $A$:

  1. (1)

The root $\epsilon$ of $\tau$ corresponds to the root $v$ of $T$, with
$\tau(\epsilon)=z$ assuming that $\lambda(v)$ is of the form
$(\cdot,\cdot,\cdot,z,\cdot,\cdot)$.

  2. (2)

For every node $u$ of $\tau$ corresponding to a node $v\in V$, with
$v_{1},\dots,v_{n}\in V$ being the nodes associated with a labeling
configuration that are reachable from $v$ via a labeled-free path, if
$v_{n}\succ_{v},\dots,\succ_{v}v_{1}$, then the children $u\cdot
1,\dots,u\cdot n$ of $u$ are such that $\tau(u\cdot i)=z_{i}$ assuming that
$\lambda(v_{i})$ is of the form $(\cdot,\cdot,\cdot,z_{i},\cdot,\cdot)$ for
all $i\in[n]$.

Note that every node $u$ of $\tau$ corresponds to some node $v\in V$ such that
$\lambda(v)$ is a labeling configuration, that, in turn, corresponds to some
node $v^{\prime}$ of $O$. Clearly, in this way, two different valid outputs of
$M$ on $w$ give rise to two different $k$-trees. We prove the following:

###### Lemma D.6.

The following holds for $\mathsf{BuildNFTA}(w)$.

  1. (1)

For every node $v\in V$ with $\lambda(v)=(s,x,y,z,h_{x},h_{y})$ being a
labeling configuration, $\mathsf{Process}(\lambda(v))$ adds to $\delta^{A}$
the transition
$(s_{\lambda(v)},z,(s_{\lambda(v_{1})},\dots,s_{\lambda(v_{n})}))$, where
$v_{1},\dots,v_{n}$ are the nodes associated with a labeling configuration
that are reachable from $v$ in $T$ via a labeled-free path, and
$v_{n}\succ_{v},\dots,\succ_{v}v_{1}$, and returns the set
$\\{(s_{\lambda(v)})\\}$.

  2. (2)

For every node $v\in V$ with $\lambda(v)$ being a non-labeling configuration,
$\mathsf{Process}(\lambda(v))$ returns a set containing the tuple
$(s_{\lambda(v_{1})},\dots,s_{\lambda(v_{n})})$, where $v_{1},\dots,v_{n}$ are
the nodes associated with a labeling configuration that are reachable from $v$
in $T$ via a labeled-free path, and $v_{n}\succ_{v},\dots,\succ_{v}v_{1}$.

###### Proof.

We prove the claim by induction on $h(v)$, that is, the height of the node $v$
in $T$. The base case, $h(v)=0$, is when $v$ is a leaf of $T$. Clearly, in
this case, there are no nodes associated with a labeling configuration
reachable from $v$ via a labeled-free path. Since $T$ is an accepting
computation, it must be the case that $\lambda(v)$ is of the form
$(s_{\text{\rm accept}},\cdot,\cdot,z,\cdot,\cdot)$. If $\lambda(v)$ is a
labeling configuration, in line 8 of $\mathsf{Process}(\lambda(v))$ the
transition $(s_{\lambda(v)},z,())$ is added to $\delta^{A}$. Then, in line 9
we add $(\lambda(v),\\{(s_{\lambda(v)})\\})$ to $Q$, and in line 24 we return
the set $\\{(s_{\lambda(v)})\\}$. If $\lambda(v)$ is a non-labeling
configuration, in line 10 we add $(\lambda(v),\\{()\\})$ to $Q$, and in line
24 we return the set $\\{()\\}$. This concludes our proof for the base case.

Next, assume that the claim holds for $h(v)\leq\ell$, and we prove that it
holds for $h(v)=\ell+1$. We start with the case where $\lambda(v)$ is a
labeling configuration. Let $w_{1},\dots,w_{m}$ be the children of $v$ in $T$,
and let $v_{1},\dots,v_{n}$ be the nodes associated with a labeling
configuration that are reachable from $v$ via a labeled-free path. Clearly,
every node $v_{i}$ is reachable via a (possibly empty) labeled-free path from
some child $w_{j}$ of $v$. Moreover, for each $w_{j}$ we have that
$h(w_{j})\leq\ell$; hence, the inductive assumption implies that the claim
holds for each node $w_{j}$. Each node $w_{j}$ that is associated with a
labeling configuration is, in fact, one of the nodes $v_{1},\dots,v_{n}$; that
is, $w_{j}=v_{i}$ from some $i\in[n]$. The inductive assumption implies that
$\mathsf{Process}(\lambda(w_{j}))$ returns the set
$\\{(s_{\lambda(v_{i})})\\}$ that contains a single tuple. We denote this
tuple by $p_{j}$. If, on the other hand, $\lambda(w_{j})$ is a non-labeling
configuration, let $v_{i_{1}},\dots,v_{i_{n_{j}}}$ be the nodes of
$v_{1},\dots,v_{n}$ that are reachable from $w_{j}$ via a labeled-free path.
Clearly, these are the only nodes associated with a labeling configuration
that are reachable from $w_{j}$ via a labeled-free path, as each such node is
also reachable from $v$ via a labeled-free path. In this case, the inductive
assumption implies that $\mathsf{Process}(\lambda(w_{j}))$ returns a set
containing the tuple
$(s_{\lambda(v_{i_{1}})},\dots,s_{\lambda(v_{i_{n_{j}}})})$. We again denote
this tuple by $p_{j}$. Note that if $\lambda(w_{j})$ is a non-labeling
configuration, and there are no nodes associated with a labeling configuration
that are reachable from $w_{j}$ via a labeled-free path, we have that
$p_{j}=()$.

If $\lambda(v)$ is a universal configuration, then in line 16 we define
$P:=\bigotimes_{i\in[m]}P_{i}$. In particular, $P$ will contain the tuple
obtained by merging the tuples $p_{1},\dots,p_{m}$, assuming that
$\lambda(w_{1}),\dots,\lambda(w_{m})$ is the order defined over the nodes with
an incoming edge from $\lambda(v)$ in line 13 of
$\mathsf{Process}(\lambda(v))$. Note that for two nodes $v_{i}\neq v_{k}$ that
are reachable from the same child $w_{j}$ of $v$, if
$v_{i}\succ_{w_{j}}v_{k}$, then $v_{i}\succ_{v}v_{k}$, because the lowest
common ancestor of $v_{i},v_{k}$ occurs under $w_{j}$ (or it is $w_{j}$
itself). If $v_{i}$ is reachable from $w_{j_{1}}$ while $v_{k}$ is reachable
from $w_{j_{2}}$ with $j_{1}<j_{2}$, then $v$ is the lowest common ancestor of
$v_{i}$ and $v_{j}$, and since $\lambda(w_{j_{1}})$ occurs before
$\lambda(w_{j_{2}})$ in the order defined over the nodes with an incoming edge
from $\lambda(v)$ in line 13 of $\mathsf{Process}(\lambda(v))$, we have that
$v_{j}\succ_{v}v_{i}$. We conclude that the tuple obtained by merging the
tuples $p_{1},\dots,p_{m}$ is precisely the tuple
$(s_{\lambda(v_{1})},\dots,s_{\lambda(v_{n})})$, assuming that
$v_{n}\succ_{v}\dots\succ_{v}v_{1}$. Then, in line 21 we add the transition
$(s_{\lambda(v)},z,(s_{\lambda(v_{1})},\dots,s_{\lambda(v_{n})}))$ to
$\delta^{A}$ and in line 24 we return the set $\\{(s_{\lambda(v)})\\}$.

Now, if $\lambda(v)$ is an existential configuration, $v$ has a single child
$w_{1}$ in $T$. If $\lambda(w_{1})$ is a labeling configuration, then $w_{1}$
is the only node associated with a labeling configuration that is reachable
from $v$ via a labeled-free path, and the inductive assumption implies that
$\mathsf{Process}(\lambda(w_{1}))$ returns the set
$\\{(s_{\lambda(w_{1})})\\}$ that contains a single tuple, which we denote by
$p$. Otherwise, all the nodes $v_{1},\dots,v_{n}$ are reachable from $w_{1}$
via a labeled-free path, and $\mathsf{Process}(\lambda(w_{1}))$ returns a set
that contains the tuple $(s_{\lambda(v_{1})},\dots,s_{\lambda(v_{n})})$, that
we again denote by $p$. (As aforementioned, it cannot be the case that there
is an additional node associated with a labeling configuration that is
reachable from $w_{1}$ via a labeled-free path, as each such node is also
reachable from $v$ via such a path.) It is rather straightforward that
$\succ_{v}$ is the same as $\succ_{w_{1}}$; hence, since
$v_{n}\succ_{w_{1}}\dots\succ_{w_{1}}v_{1}$ based on the inductive assumption,
it also holds that $v_{n}\succ_{v}\dots\succ_{v}v_{1}$. In line 15 of
$\mathsf{Process}(\lambda(v))$ we simply take the union of the sets returned
by all the nodes of $G$ with an incoming edge from $\lambda(v)$, one of which
is $\lambda(w_{1})$; hence, the tuple $p$ will appear as it is in $P$.
Finally, in line 21 we add the transition $(s_{\lambda(v)},z,p)$ to
$\delta^{A}$ and in line 24 we return the set $\\{(s_{\lambda(v)})\\}$.

Finally, if $\lambda(v)$ is a non-labeling configuration, instead of adding
the transition, we add $(\lambda(v),P)$ to $Q$ in line 23, and return in line
24 the set $P$ that, as aforementioned, contains the tuple
$(s_{\lambda(v_{1})},\dots,s_{\lambda(v_{n})})$, which concludes our proof.

With Lemma D.6 in place, it is not hard to show that there is a run $\rho$ of
$A$ over $\tau$. In particular, for every node $u$ of $\tau$ corresponding to
a node $v\in V$ (with $\lambda(v)$ being a labeling configuration), we define
$\rho(u)=s_{\lambda(v)}$. Lemma D.6 implies that the transition
$(s_{\lambda(v)},z,(s_{\lambda(v_{1})},\dots,s_{\lambda(v_{n})}))$ occurs in
$\delta^{A}$, where $v_{1},\dots,v_{n}$ are the nodes associated with a
labeling configuration that are reachable from $v$ via a labeled-free path and
$v_{n}\succ_{v}\dots\succ_{v}v_{1}$. The children of $u$ in $\tau$ correspond,
by construction, to the nodes $v_{1},\dots,v_{n}$ following the same order