$\succ_{v}$. Note that if no nodes associated with a labeling configuration
are reachable from $v$ via a labeled-free path, we have the transition
$(s_{\lambda(v)},z,())$ in $\delta^{A}$, and $u$ is a leaf of $\tau$. It is
now easy to verify that the mapping $\rho$ defines a run of $A$ over $\tau$.

#### Accepted Tree to Valid Output.

Let $\tau$ be a $k$-tree accepted by $A$. We will show that the labeled tree
$O=(V^{\prime},E^{\prime},\lambda^{\prime})$ inductively defined as follows is
a valid output of $M$ on $w$:

  1. (1)

The root $v^{\prime}$ of $O$ corresponds to the root $\epsilon$ of $\tau$,
with $\lambda(v^{\prime})=\tau(\epsilon)$.

  2. (2)

For every node $v^{\prime}$ of $O$ corresponding to a non-leaf node $u$ of
$\tau$, if $u\cdot 1,\dots,u\cdot n$ are the children of $u$ in $\tau$, then
$v_{1}^{\prime},\dots,v_{n}^{\prime}$ are the children of $v^{\prime}$ in $O$,
with $\lambda^{\prime}(v_{i}^{\prime})=\tau(u\cdot i)$ for all $i\in[n]$.

Clearly, with this definition, two different $k$-trees give rise to two
different valid outputs of $M$ on $w$. We will show that there is an accepting
computation $T$ of $M$ on $w$ such that $O$ is output of $T$.

Our proof is based on the following simple observation regarding
$\mathsf{BuildNFTA}(w)$ and the labeling configurations of $M$ on $w$. Recall
that $G$ is the computation DAG of $M$ on $w$.

###### Observation 1.

Let $C$ be a labeling configuration of $M$ on $w$. Let $C_{1},\dots,C_{n}$ be
the nodes of $G$ with an incoming edge from $C$, and let
$(s_{C},z,(s_{1},\dots,s_{\ell}))$ be one of the transitions added to
$\delta^{A}$ in line 21 of $\mathsf{Process}(C)$. The following hold:

  * •

If $C$ is a universal configuration, then there are $p_{1},\dots,p_{n}$ such
that $p_{i}$ is one of the tuples returned by $\mathsf{Process}(C_{i})$ for
all $i\in[n]$, and $(s_{1},\dots,s_{\ell})$ is the tuple obtained by merging
$p_{1},\dots,p_{n}$ in line 16, and

  * •

if $C$ is an existential configuration, then $(s_{1},\dots,s_{\ell})$ is one
of the tuples returned by $\mathsf{Process}(C_{i})$ for some $i\in[n]$.

We also need the following observation regarding $\mathsf{BuildNFTA}(w)$ and
non-labeling configurations of $M$ on $w$.

###### Observation 2.

Let $C$ be a non-labeling configuration of $M$ on $w$. Let $C_{1},\dots,C_{n}$
be the nodes of $G$ with an incoming edge from $C$, and let
$(s_{1},\dots,s_{\ell})$ be one of the tuples returned by
$\mathsf{Process}(C)$. Then:

  * •

If $C$ is a universal configuration, then there are $p_{1},\dots,p_{n}$ such
that $p_{i}$ is one of the tuples returned by $\mathsf{Process}(C_{i})$ for
all $i\in[n]$, and $(s_{1},\dots,s_{\ell})$ is obtained by merging the tuples
$p_{1},\dots,p_{n}$ in line 16, and

  * •

if $C$ is an existential configuration, then $(s_{1},\dots,s_{\ell})$ is one
of the tuples returned by $\mathsf{Process}(C_{i})$ for some $i\in[n]$.

Since $\tau$ is accepted by $A$, there is a run $\rho$ of $A$ over $\tau$.
Based on this and the two observations above, we can now define an inductive
procedure to construct $T=(V,E,\lambda)$. Intuitively, we construct $T$ while
traversing the $k$-tree $\tau$ from the root to the leaves. We start by adding
the root of $T$ associated with the initial configuration of $M$ on $w$. For
each node $v$ that we add to $V$, we store two pieces of information: _(1)_
the current node $\text{\rm node}(v)$ of $\tau$ that we handle (starting from
the root of $\tau$), and _(2)_ a tuple $\mathsf{states}(v)$ of states of
$S^{A}$ that this node is responsible for. Intuitively, if
$\mathsf{states}(v)=(s_{1},\dots,s_{\ell})$, then there should be labeled-free
paths from the node $v$ to nodes $v_{1},\dots,v_{\ell}$ such that
$\lambda(v_{j})$ is the configuration of $s_{j}$, for every $j\in[\ell]$. Note
that every state in $S^{A}$ corresponds to a _labeling_ configuration of $M$
on $w$, because in $\mathsf{BuildNFTA}(w)$ we add a state $s_{C}$ to $S^{A}$
if only if $C$ is a labeling configuration; hence, $\lambda(v_{j})$ is a
labeling configuration, for every $j\in[\ell]$.

In addition, for every node $v$ with $\lambda(v)$ being a labeling
configuration, we store an additional tuple $\text{\rm assignment}(v)$ that is
determined by a node of $\tau$. In particular, when we reach a labeling
configuration, we continue our traversal of $\tau$, and consider one of the
children $u$ of $\text{\rm node}(v)$. Then, if the children of $u$ in $\tau$
are $u\cdot 1,\dots,u\cdot\ell$ with $\rho(u)=s_{\lambda(v)}$ and
$\rho(u_{i})=s_{i}$ for $i\in[\ell]$, and we have the transition
$(s_{\lambda(v)},\tau(u),(s_{1},\dots,s_{\ell}))$ in $\delta^{A}$ (such a
transition must exist because $\rho$ is a run of $A$ over $\tau$), the tuple
of states that we should assign responsibility for is $\text{\rm
assignment}(v)=(s_{1},\dots,s_{\ell})$. If $\lambda(v)$ is a universal
configuration, this set is split between the children of $v$ (determined by
the transition
$\lambda(v)\rightarrow_{M}\\{C^{\prime}_{1},\ldots,C^{\prime}_{n}\\}$ of $M$),
so each one of them is responsible for a (possibly empty) subtuple of
$\text{\rm assignment}(v)$. If, on the other hand, $\lambda(v)$ is an
existential configuration, we add one child under $v$ and pass to him the
responsibility for the entire tuple. Formally, we define the following
procedure.

  1. (1)

We add a root node $v$ to $V$ with $\lambda(v)$ being the initial
configuration of $M$ on $w$. We define

$\mathsf{states}(v)=(s_{\lambda(v)}).$

  2. (2)

For every node $v\in V$ with $\lambda(v)$ being a labeling configuration,
assuming $\lambda(v)\rightarrow_{M}\\{C^{\prime}_{1},\ldots,C^{\prime}_{n}\\}$
for some $n>0$, let $u$ be a child of $\text{\rm node}(v)$ (or the root of
$\tau$ if $\text{\rm node}(v)$ is undefined), such that:

_(1)_ $\rho(u)=s_{\lambda(v)}$,

_(2)_ $u\cdot 1,\dots,u\cdot\ell$ are the children of $u$ in $\tau$,

_(3)_ $\rho(u\cdot j)=s_{j}$ for all $j\in[\ell]$. Consider the transition
$(s_{\lambda(v)},\tau(u),(s_{1},\dots,s_{\ell}))$ in $\delta^{A}$. We define

$\text{\rm assignment}(v)=(s_{1},\dots,s_{\ell}).$

Then, if $\lambda(v)$ is an existential configuration, we add a single child
$v_{i}$ under $v$ with $\lambda(v_{i})=C_{i}^{\prime}$ for some $i\in[n]$,
such that $\mathsf{Process}(C^{\prime}_{i})$ returns the tuple
$(s_{1},\dots,s_{\ell})$ based on Observation 1, and define

$\text{\rm
node}(v_{i})=u\quad\text{and}\quad\mathsf{states}(v_{i})=(s_{1},\dots,s_{\ell}).$

If $\lambda(v)$ is a universal configuration, we add the children
$v_{1},\dots,v_{n}$ under $v$ with $\lambda(v_{i})=C_{i}^{\prime}$ for all
$i\in[n]$, and for each child $v_{i}$ we define

$\text{\rm node}(v_{i})=u\quad\text{and}\quad\text{\rm
configurations}(v_{i})=p_{i}$

where $p_{i}$ is the tuple returned by $\mathsf{Process}(C_{i}^{\prime})$, for
every $i\in[n]$, such that $(s_{1},\dots,s_{\ell})$ is obtained by merging the
tuples $p_{1},\dots,p_{n}$ based on Observation 1.

  3. (3)

For a node $v\in V$ with $\lambda(v)$ being a non-labeling configuration,
assuming $\lambda(v)\rightarrow_{M}\\{C_{1}^{\prime},\ldots,C_{n}^{\prime}\\}$
for some $n>0$ and $\mathsf{states}(v)=(s_{1},\dots,s_{\ell})$, if
$\lambda(v)$ is an existential configuration, we add a single child $v_{i}$
under $v$ with $\lambda(c_{i})=C_{i}^{\prime}$ for some $i\in[n]$, such that
the tuple $(s_{1},\dots,s_{\ell})$ is returned by
$\mathsf{Process}(C_{i}^{\prime})$ based on Observation 2, and define

$\text{\rm node}(v_{i})=\text{\rm
node}(v)\quad\text{and}\quad\mathsf{states}(v_{i})=(s_{1},\dots,s_{\ell}).$

If $\lambda(v)$ is a universal configuration, we add the children
$v_{1},\dots,v_{n}$ under $v$ with $\lambda(v_{i})=C_{i}^{\prime}$ for all
$i\in[n]$, and for each child $v_{i}$ we define

$\text{\rm node}(v_{i})=\text{\rm
node}(v)\quad\text{and}\quad\mathsf{states}(v_{i})=p_{i}$

where $p_{i}$ is the tuple returned by $\mathsf{Process}(C_{i}^{\prime})$, for
every $i\in[n]$, such that $(s_{1},\dots,s_{\ell})$ is obtained by merging the
tuples $p_{1},\dots,p_{n}$ based on Observation 2.

  4. (4)

For a leaf node $v\in V$ with $\lambda(v)$ being a labeling configuration, we
define

$\text{\rm assignment}(v)=().$

We now show that the above procedure is well-defined. In particular, we show
that we can always find a node of $\tau$ that satisfies the desired properties
when considering labeling configurations, and that we can indeed apply
Observations 1 and 2.

###### Lemma D.7.

The following hold:

  * •

For every added non-root node $v$, it holds that $\mathsf{states}(v)$ is a
subtuple of $\text{\rm assignment}(r)$, where $r$ is the lowest ancestor of
$v$ with $\lambda(r)$ being a labeling configuration.

  * •

For every added node $v$, $\mathsf{states}(v)$ is a tuple returned by
$\mathsf{Process}(\lambda(v))$.

  * •

For every added node $v$ with $\lambda(v)$ being a labeling configuration,
$\mathsf{states}(v)=(s_{\lambda(v)})$.

  * •

For every added node $v$ with $\lambda(v)$ being a labeling configuration,
there exists a child $u$ of $\text{\rm node}(v)$ (or the root of $\tau$ if
$\text{\rm node}(v)$ is undefined) with $\rho(u)=s_{\lambda(v)}$ such that, if
$u\cdot 1,\dots,u\cdot\ell$ are the children of $u$ in $\tau$ with
$\rho(u\cdot j)=s_{j}$ for every $j\in[\ell]$, then the transition
$(s_{\lambda(v)},\tau(u),(s_{1},\dots,s_{\ell}))$ occurs in $\delta^{A}$ and
$\text{\rm assignment}(v)=(s_{1},\dots,s_{\ell})$.

  * •

For every added leaf $v$, $\lambda(v)$ is an accepting configuration.

###### Proof.

We prove the claim by induction on $d(v)$, that is, the depth of the node $v$
in the constructed tree. If $d(v)=0$, then $v$ is the root of the tree. By
construction, $\lambda(v)$ is the initial configuration of $M$ on $w$ and it
is a labeling configuration by definition. Moreover, in the procedure we
define $\mathsf{states}(v)=(s_{\lambda(v)})$, and $\mathsf{Process}(C)$
returns the tuple $(s_{C})$ for every labeling configuration $C$; in
particular, $\mathsf{Process}(\lambda(v))$ returns $(s_{\lambda(v)})$. Since
$\text{\rm node}(v)$ is undefined, we consider the root $u$ of $\tau$. It must
be the case that $\rho(u)=s_{\lambda(v)}$, since the state $s_{\lambda(v)}$
that corresponds to the initial configuration of $M$ on $w$, and so to the
root of $G$, is the state $s^{A}_{\text{\rm init}}$ (as defined in line 4 of
$\mathsf{BuildNFTA}(w)$). If $u\cdot 1,\dots,u\cdot\ell$ are the children of
$u$ in $\tau$, and $\rho(u\cdot j)=s_{j}$ for every $j\in[\ell]$, since $\rho$
is a run of $A$ over $\tau$, there must be a transition
$(s_{\lambda(v)},\tau(u),(s_{1},\dots,s_{\ell}))$ in $\delta^{A}$. In the
procedure, assuming
$\lambda(v)\rightarrow_{M}\\{C^{\prime}_{1},\ldots,C^{\prime}_{n}\\}$ for some
$n>0$ (i.e. $v$ is a non-leaf node), we define $\text{\rm
assignment}(v)=(s_{1},\dots,s_{\ell})$.

As for the first point of the lemma, the non-root nodes $v_{1},\dots,v_{n}$ of
depth $1$ are the direct children of the root, and, in the procedure, we
define $\mathsf{states}(v_{i})=\text{\rm assignment}(v)$ if $\lambda(v)$ is an
existential configuration and $v_{i}$ is the only child of $v$ in the
constructed tree (in this case, there is only one node of depth $1$), or
$\mathsf{states}(v_{i})\subseteq\text{\rm assignment}(v)$ for every $i\in[n]$
if $\lambda(v)$ is a universal configuration. In both cases, $v$ is the lowest
ancestor of $v_{1},\dots,v_{n}$ with $\lambda(v)$ being a labeling
configuration, and we have that $\mathsf{states}(v_{i})\subseteq\text{\rm
assignment}(v)$. This concludes the base case.

Next, assume that the claim holds for all added nodes $v$ with $d(v)\leq m$.
We prove that it also holds for all added nodes $v$ with $d(v)=m+1$. Let $v$
be such a node, and let $p$ be its parent in the constructed tree. Since
$d(p)\leq m$, the inductive assumption holds for $p$. If $\lambda(p)$ is a
non-labeling configuration, the inductive assumption implies that
$\mathsf{states}(v)=(s_{1},\dots,s_{\ell})$ is a tuple returned by
$\mathsf{Process}(\lambda(p))$. If, on the other hand, $\lambda(p)$ is a
labeling configuration, the inductive assumption implies that there exists a
child $u$ of $\text{\rm node}(p)$ (or the root of $\tau$ if $\text{\rm
node}(p)$ is undefined) with $\rho(u)=s_{\lambda(p)}$, such that if $u\cdot
1,\dots,u\cdot\ell$ are the children of $u$ in $\tau$ with $\rho(u\cdot
j)=s_{j}$ for every $j\in[\ell]$, the transition
$(s_{\lambda(p)},\tau(u),(s_{1},\dots,s_{\ell}))$ occurs in $\delta^{A}$ and,
since $p$ is a non-leaf node, $\text{\rm
assignment}(v)=(s_{1},\dots,s_{\ell})$. Hence, if $\lambda(p)$ is a non-
labeling configuration, we now consider the tuple
$\mathsf{states}(p)=(s_{1},\dots,s_{\ell})$, and if $\lambda(p)$ is a labeling
configuration, we consider the tuple $\text{\rm
assignment}(p)=(s_{1},\dots,s_{\ell})$.

Then, if $\lambda(p)$ is an existential configuration, Observation 1 or 2
(depending on whether $\lambda(p)$ is a labeling or non-labeling
configuration) implies that, assuming
$\lambda(p)\rightarrow_{M}\\{C_{1}^{\prime},\ldots,C_{n}^{\prime}\\}$ for
$n>0$, $(s_{1},\dots,s_{\ell})$ is one of the tuples returned by
$\mathsf{Process}(C_{i}^{\prime})$ for $i\in[n]$. In this case, in the
procedure, we add a single child $v$ under $p$ with
$\lambda(v)=C_{i}^{\prime}$, and define
$\mathsf{states}(v)=(s_{1},\dots,s_{\ell})$. Clearly, this child is the node
$v$; hence, $\mathsf{Process}(\lambda(v))$ returns the tuple
$(s_{1},\dots,s_{\ell})$.

If $\lambda(p)$ is a universal configuration, Observation 1 or Observation 2
(depending on whether $\lambda(p)$ is a labeling or non-labeling
configuration) implies that, again assuming
$\lambda(p)\rightarrow_{M}\\{C_{1}^{\prime},\ldots,C_{n}^{\prime}\\}$ for some
$n>0$, there are $p_{1},\dots,p_{n}$, such that for every $i\in[n]$, $p_{i}$
is one of the tuples returned by $\mathsf{Process}(C_{i}^{\prime})$, and
$(s_{1},\dots,s_{\ell})$ is the tuple obtained by merging $p_{1},\dots,p_{n}$.
In the procedure, we add $n$ children $v_{1},\dots,v_{n}$ under $p$, with
$\lambda(v_{i})=C_{i}^{\prime}$ for $i\in[n]$, and, clearly, $v=v_{i}$ for
some $i\in[n]$; hence, we define $\mathsf{states}(v)=p_{i}$.

Note that in both cases ($\lambda(p)$ being universal or existential), we have
shown that $\mathsf{Process}(\lambda(v))$ returns the tuple
$\mathsf{states}(v)$. Moreover, if $\lambda(p)$ is a labeling configuration,
$p$ is the lowest ancestor of $v$ with $\lambda(p)$ being a labeling
configuration, and we have shown that $\mathsf{states}(v)$ is a subtuple of
$\text{\rm assignment}(p)$. If $\lambda(p)$ is a non-labeling configuration,
the inductive assumption implies that $\mathsf{states}(p)$ is a subtuple of
$\text{\rm assignment}(r)$, where $r$ is the lowest ancestor of $p$ with
$\lambda(r)$ being a labeling configuration. Clearly, $r$ is also the lowest
ancestor of $v$ with $\lambda(r)$ being a labeling configuration, and we
conclude that $\mathsf{states}(v)$ is a subtuple of $\text{\rm
assignment}(r)$.

Now, if $\lambda(v)$ is a non-labeling configuration, then we are done, as we
have proved that the first and second points of the lemma hold. However, if
$\lambda(v)$ is a labeling configuration, we need to prove that the third and
fourth points hold. In particular, we need to establish that there exists a
child $u$ of $\text{\rm node}(v)$ with $\rho(u)=s_{\lambda(v)}$, such that if
$u\cdot 1,\dots,u\cdot\ell$ are the children of $u$ in $\tau$ with
$\rho(u\cdot j)=s_{j}$ for every $j\in[\ell]$, the transition
$(s_{\lambda(v)},\tau(u),(s_{1},\dots,s_{\ell}))$ occurs in $\delta^{A}$.
Consider the lowest ancestor $r$ of $v$ with $\lambda(r)$ being a labeling
configuration. Since $d(r)\leq m$, the inductive assumption implies that there
exists a child $u^{\prime}$ of $\text{\rm node}(r)$ with
$\rho(u^{\prime})=s_{\lambda(r)}$, such that if $u^{\prime}\cdot
1,\dots,u^{\prime}\cdot m$ are the children of $u^{\prime}$ in $\tau$ with
$\rho(u^{\prime}\cdot j)=S_{j}^{\prime}$ for every $j\in[m]$, the transition
$(s_{\lambda(r)},\tau(u^{\prime}),(s_{1}^{\prime},\dots,s_{m}^{\prime}))$
occurs in $\delta^{A}$. Note that $\text{\rm
assignment}(r)=(s^{\prime}_{1},\dots,s_{m}^{\prime})$. Clearly, we have that
$\text{\rm node}(v)=u^{\prime}$, as only labeling configurations modify this
information, and all the nodes along the path from $r$ to $v$ are associated
with non-labeling configurations.

As we have already shown, it holds that $\mathsf{states}(v)$ is a subtuple of
$\text{\rm assignment}(r)$, that is, a subtuple of
$(s^{\prime}_{1},\dots,s_{m}^{\prime})$. Since $\lambda(v)$ is a labeling
configuration, the only tuple returned by $\mathsf{Process}(\lambda(v))$ is
$(s_{\lambda(v)})$. We have also shown that $\mathsf{Process}(\lambda(v))$
returns the tuple $\mathsf{states}(v)$; thus, we conclude that
$\mathsf{states}(v)=(s_{\lambda(v)})$ (which prove the fourth point of the
lemma) and so $s_{\lambda(v)}=s_{j}^{\prime}$ for some $j\in[m]$. Therefore,
there is indeed a child $u^{\prime}\cdot j$ of $\text{\rm node}(v)=u^{\prime}$
with $\rho(u^{\prime}\cdot j)=s_{j}^{\prime}=s_{\lambda(v)}$. If the children
of $u^{\prime}\cdot j$ in $\tau$ are $u^{\prime}\cdot j\cdot
1,\dots,u^{\prime}\cdot j\cdot t$ with $\rho(u^{\prime}\cdot j\cdot
i)=s^{\prime\prime}_{i}$ for all $i\in[t]$, since $\rho$ is a run of $A$ over
$\tau$, clearly there is a transition $(s_{\lambda(v)},\tau(u^{\prime}\cdot
j),(s_{1}^{\prime\prime},\dots,s_{t}^{\prime\prime}))$ in $\delta^{A}$, and in
the procedure we define $\text{\rm
assignment}(v)=(s_{1}^{\prime\prime},\dots,s_{t}^{\prime\prime})$. Note that
if $u^{\prime}\cdot j$ is a leaf of $\tau$, since $\rho$ is a run of $A$ over
$\tau$, we must have a transition $(s_{\lambda(v)},\tau(u^{\prime}\cdot
j),())$ in $\delta^{A}$.

Finally, if $v$ is a leaf and $\lambda(v)$ is a non-labeling configuration, we
have already established that $\mathsf{states}(v)$ is a tuple returned by
$\mathsf{Process}(\lambda(v))$, and it is a subtuple of $\text{\rm
assignment}(r)$, where $r$ is the lowest ancestor of $v$ with $\lambda(r)$
being a labeling configuration. Since $v$ is a leaf of $T$, there is no
transition of the form
$\lambda(v)\rightarrow_{M}\\{C_{1}^{\prime},\ldots,C_{n}^{\prime}\\}$, and so
$\lambda(v)$ is a leaf of $G$. Therefore, in $\mathsf{Process}(\lambda(v))$ we
return the set $\\{()\\}$ in line 24 if $\lambda(v)$ is an accepting
configuration or the empty set if $\lambda(v)$ is a rejecting configuration
(this set is added to $Q$ in line 10 or 11). Hence, the only possible case is
that $\mathsf{states}(v)=()$ and $\lambda(v)$ is an accepting configuration.

If $v$ is a leaf and $\lambda(v)$ is a labeling configuration, we have already
shown that the transition $(s_{\lambda(v)},\tau(u),(s_{1}\dots,s_{\ell}))$ is
in $\delta^{A}$, where $u$ is the child of $\text{\rm node}(v)$ in $\tau$ that
we consider when adding $v$, $u\cdot 1,\dots,u\cdot\ell$ are the children of
$u$ in $\tau$, $\rho(u\cdot j)=s_{j}$ for all $j\in\ell$. Since $v$ is a leaf,
in $\mathsf{Process}(\lambda(v))$ we return a set containing the single tuple
$(s_{\lambda}(v))$ in line 24 (after adding this set to $Q$ in line 9), and
the only transition added to $\delta^{A}$ with $s_{\lambda}(v)$ on its left-
hand side is $(s_{\lambda(v)},\tau(u),())$ if $\lambda(v)$ is an accepting
configuration. If $\lambda(v)$ is a rejecting configuration, we do not add any
transition with $\lambda(v)$ on its left-hand side to $\delta^{A}$. Thus, the
only possible case is that $\lambda(v)$ is an accepting configuration, and $u$
is a leaf of $\tau$.

In the described procedure, we start with a node associated with the initial
configuration of $M$ on $W$, and we systematically add a single child for each
node $v$ with $\lambda(v)$ being an existential configuration and all children
for each node $v$ with $\lambda(v)$ being a universal configuration, while
following the transitions
$\lambda(v)\rightarrow_{M}\\{C^{\prime}_{1},\ldots,C^{\prime}_{n}\\}$ of $M$.
Therefore, in combination with Lemma D.7, it is easy to verify that the
constructed $T$ is indeed a computation of $M$ on $w$. Moreover, since for
every leaf $v$ of $T$ we have shown that $\lambda(v)$ is an accepting
configuration, $T$ is an accepting computation. It is only left to show that
$O=(V^{\prime},E^{\prime},\lambda^{\prime})$ is the output of $T$. The proof
consists of three steps. We start by showing the following.

###### Lemma D.8.

Let $v$ be a node of $T$. Assume that $\text{\rm
assignment}(v)=(s_{C_{1}},\dots,s_{C_{\ell}})$ if $v$ is a node of $T$ with
$\lambda(v)$ being a labeling configuration, or
$\mathsf{states}(v)=(s_{C_{1}},\dots,s_{C_{\ell}})$ otherwise. Then, there is
a labeled-free path from $v$ to a node $v^{\prime}$ with $\lambda(v^{\prime})$
being a labeling configuration if and only if $\lambda(v^{\prime})=C_{i}$ for
some $i\in[\ell]$.

###### Proof.

We prove the claim by induction on $h(v)$, the height of the node $v$ in $T$.
If $h(v)=0$, then $v$ is a leaf of $T$. Lemma D.7 implies that $\lambda(v)$ is
an accepting configuration. If $\lambda(v)$ is a non-labeling configuration,
$\mathsf{Process}(\lambda(v))$ returns the set $\\{()\\}$. Then, Lemma D.7
implies that $\mathsf{states}(v)=()$, and the claim follows. If, on the other
hand, $\lambda(v)$ is a labeling configuration, in the procedure we define
$\text{\rm assignment}(v)=()$, and the claim again follows.

Next, assume that the claim holds for all nodes $v$ with $h(v)\leq m$. We
prove that it holds for all nodes $v$ with $h(v)=m$. If $\lambda(v)$ is a
labeling configuration, assuming
$\lambda(v)\rightarrow_{M}\\{C^{\prime}_{1},\ldots,C^{\prime}_{n}\\}$ for some
$n>0$, in the procedure we either add one node $w_{1}$ under $v$ with
$\mathsf{states}(w_{1})=\text{\rm assignment}(v)$ (if $\lambda(v)$ is
existential), or we add $n$ nodes $w_{1},\dots,w_{n}$ under $v$ with
$\mathsf{states}(w_{i})$ being a (possibly empty) subtuple of $\text{\rm
assignment}(v)$ for every $i\in[n]$, and such that $\text{\rm assignment}(v)$
is obtained by merging the tuples
$\mathsf{states}(w_{1}),\dots,\mathsf{states}(w_{n})$. Similarly, if
$\lambda(v)$ is a non-labeling configuration, assuming
$\lambda(v)\rightarrow_{M}\\{C^{\prime}_{1},\ldots,C^{\prime}_{n}\\}$ for some
$n>0$, in the procedure we either add one node $w_{1}$ under $v$ with
$\mathsf{states}(w_{1})=\mathsf{states}(v)$ (if $\lambda(v)$ is existential),
or we add $n$ nodes $w_{1},\dots,w_{n}$ under $v$ with
$\mathsf{states}(w_{i})$ being a (possibly empty) subtuple of
$\mathsf{states}(v)$ for every $i\in[n]$, and such that $\mathsf{states}(v)$
is obtained by merging the tuples
$\mathsf{states}(w_{1}),\dots,\mathsf{states}(w_{n})$.

If $\lambda(w_{i})$ is a labeling configuration for some $i\in[n]$, Lemma D.7
implies that $\mathsf{states}(w_{i})=(s_{\lambda(w_{i})})$; hence,
$s_{\lambda(w_{i})}$ is one of the states in $(s_{C_{1}},\dots,s_{C_{\ell}})$,
and clearly there is an (empty) labeled-free path from $v$ to $w_{i}$. If
$\lambda(w_{i})$ is a non-labeling configuration for some $i\in[n]$, since
$h(w_{i})\leq m$, the inductive assumption implies that there is a labeled-
free path from $w_{i}$ to nodes $v_{i_{1}},\dots,v_{i_{t}}$ such that
$\mathsf{states}(w_{i})=(s_{C_{i_{1}}},\dots,s_{C_{i_{t}}})$ and
$\lambda(v_{i_{j}})=C_{i_{j}}$ for all $j\in[t]$. Clearly, this means that
there is a labeled-free path from $v$ to $v_{i_{j}}$ for all $j\in[t]$. Since,
as aforementioned, $(s_{C_{1}},\dots,s_{C_{\ell}})$ is obtained by merging the
tuples $\mathsf{states}(w_{1}),\dots,\mathsf{states}(w_{n})$ (or it is the
single tuple $\mathsf{states}(w_{1})$ if $\lambda(v)$ is existential), and
every path from $v$ passes through one of its children, we conclude that there
is a labeled-free path from $v$ to a node $v^{\prime}$ with
$\lambda(v^{\prime})$ being a labeling configuration if and only if
$\lambda(v^{\prime})=C_{i}$ for some $i\in\ell$.

Next, we show that every node of $\tau$ is associated with some node $v$ of
$T$ with $\lambda(v)$ being a labeling configuration.

###### Lemma D.9.

For every node $u$ of $\tau$, there is a node $v$ of $T$ with $\lambda(v)$
being a labeling configuration, such that $u$ is a child of $\text{\rm
node}(v)$ (or the root of $\tau$ is $\text{\rm node}(v)$ is undefined) with
$\rho(u)=s_{\lambda(v)}$.

###### Proof.

We prove the claim by induction on $d(u)$, the depth of the node $u$ in
$\tau$. If $d(u)=0$, then $u$ is the root of $\tau$. By construction, the root
$v$ of $T$ is such that $\lambda(v)$ is the initial configuration of $M$ on
$w$, which is a labeling configuration. Moreover, in the procedure, we
consider the node $u$ when adding $v$ to $T$, and we have that
$\rho(u)=s_{\lambda(v)}$ because $s_{\lambda(v)}$ is the initial state
$s^{A}_{\text{\rm init}}$ of the NFTA.

Next, assume that the claim holds for all nodes $u$ of $\tau$ with $d(u)\leq
m$, and we prove that it holds for nodes $u$ with $d(u)=m+1$. Let $u^{\prime}$
be the parent of $u$ in $\tau$ (hence, $u$ is of the form $u^{\prime}\cdot j$
for some $j$). The inductive assumption implies that there is a node
$v^{\prime}$ of $T$ with $\lambda(v^{\prime})$ being a labeling configuration,
such that $u^{\prime}$ is a child of $\text{\rm node}(v^{\prime})$ with
$\rho(u^{\prime})=s_{\lambda(v^{\prime})}$. Since $\rho$ is a run of $A$ over
$\tau$, there is a transition
$(s_{\lambda(v^{\prime})},\tau(u^{\prime}),(s_{C_{1}},\dots,s_{C_{\ell}}))$ in
$\delta^{A}$ such that $\rho(u)=s_{C_{i}}$ for some $i\in[\ell]$. In the
procedure, we define $\text{\rm
assignment}(v^{\prime})=(s_{C_{1}},\dots,s_{C_{\ell}}))$. Lemma D.8 implies
that there is a labeled-free path from $v^{\prime}$ to some node $v$ with
$\lambda(v)=C_{i}$. Note that $\text{\rm node}(v)=u^{\prime}$, as this is the
case for every node with a labeled-free path from $v^{\prime}$ (only labeling
configurations alter this information). When we consider the node $v$ in the
procedure, we choose a child of $\text{\rm node}(v)$ (hence, a child of
$u^{\prime}$) such that $\rho(u)=s_{\lambda(v)}$, and this is precisely the
node $u$. Hence, $u$ is a child of $\text{\rm node}(v)$ with
$\rho(u)=s_{\lambda(v)}$, and this concludes our proof.

Finally, we show that $O$ is indeed the output of $T$.

###### Lemma D.10.

The following hold.

  1. (1)

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

  2. (2)

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

  3. (3)

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

###### Proof.

The first point is rather straightforward. Every node $v$ of $T$ with
$\lambda(v)$ being a labeling configuration is associated with a (unique) node
$u$ of $\tau$; this is the child of $\text{\rm node}(v)$ that we choose when
adding the node $v$ to $T$. Moreover, Lemma D.9 implies that every node $u$ of
$\tau$ is associated with a node $v$ of $T$ with $\lambda(v)$ being a labeling
configuration. Hence, there is one-to-one correspondence between the nodes $v$
of $T$ with $\lambda(v)$ being a labeling configuration, and the nodes $u$ of
$\tau$. Since $O$ contains a node for every node of $\tau$ by construction,
and no other nodes, item (1) follows.

The second item follows from Lemma D.8 showing that there is a labeled-free
path from a node $v$ to a node $v^{\prime}$ with both $\lambda(v)$ and
$\lambda(v^{\prime})$ being labeling configurations, if and only if $\text{\rm
assignment}(v)=(s_{C_{1}},\dots,s_{C_{\ell}})$ and $\lambda(v^{\prime})=C_{i}$
for some $i\in[\ell]$. In the procedure, we define $\text{\rm
assignment}(v)=(s_{C_{1}},\dots,s_{C_{\ell}})$ if there is a node $u$ of
$\text{\rm node}(v)$ such that $\rho(u)=s_{\lambda(v)}$, with children $u\cdot
1,\dots,u\cdot\ell$ such that $\rho(u\cdot i)=s_{C_{i}}$ for all $i\in[\ell]$.
Clearly, we have that $\text{\rm node}(v^{\prime})=u$, as only nodes
associated with labeling configurations alter this information. When we
consider the node $v^{\prime}$ in the procedure, we select a child
$u^{\prime}$ of $u$ such that $\rho(u^{\prime})=s_{\lambda(v^{\prime})}$; thus
$s_{\lambda(v^{\prime})}=s_{C_{i}}$ for some $i\in[\ell]$. Hence, the node
$u^{\prime}$ associated with $v^{\prime}$ is a child of the node $u$
associated with $v$, and there is an edge $(u,u^{\prime})$ in $\tau$, and so
there is an edge between the corresponding nodes in $O$.

Finally, for every node $v\in V$ with $\lambda(v)$ being a labeling
configuration, the node $u$ of $\tau$ that we consider when adding $v$ to $T$
is such that $\rho(u)=s_{\lambda(v)}$, where $\rho$ is a run of $A$ over
$\tau$, and if $u\cdot 1,\dots,u\cdot\ell$ are the children of $u$ in $\tau$
with $\rho(u\cdot j)=s_{C_{j}}$ for every $j\in[\ell]$, the transition
$(s_{\lambda(v)},\tau(u),(s_{C_{1}},\dots,s_{C_{\ell}}))$ occurs in
$\delta^{A}$. When we add a transition to $\delta^{A}$ in
$\mathsf{BuildNFTA(w)}$, we always add transitions of the form
$(s_{C},z,\cdots)$, where $C$ is a configuration of the form
$(\cdot,\cdot,\cdot,z,\cdot,\cdot)$. Hence, if $\lambda(v)$ is a configuration
of the form $(\cdot,\cdot,\cdot,z,\cdot,\cdot)$, we have that $\tau(u)=z$ and
$\lambda^{\prime}(v^{\prime})=z$ for the corresponding node $v^{\prime}$ of
$O$. This concludes our proof.

This concludes our proof of Lemma D.4.

##  Appendix E The Normal Form

We prove the following result; note that there is no corresponding statement
in the main body of the paper since the discussion on the normal form was kept
informal.

###### Proposition E.1.

Consider a database $D$, a set $\Sigma$ of primary keys $\Sigma$, a CQ
$Q(\bar{x})$ from $\mathsf{SJF}$, a generalized hypertree decomposition $H$ of
$Q$ of width $k$, and $\bar{c}\in\mathsf{dom}(D)^{|\bar{x}|}$. There exists a
database $\hat{D}$, a CQ $\hat{Q}(\bar{x})$ from $\mathsf{SJF}$, and a
generalized hypertree decomposition $\hat{H}$ of $\hat{Q}$ of width $k+1$ such
that:

  * •

$(\hat{D},\hat{Q},\hat{H})$ is in normal form,

  * •

$|\\{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})\\}|$,

  * •

$|\\{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}))\\}|$,
and

  * •

$(\hat{D},\hat{Q},\hat{H})$ is logspace computable in the combined size of
$D,\Sigma,Q,H,\bar{c}$.

With the above proposition in place, together with the fact that
$\mathsf{SpanTL}$ is closed under logspace reductions, to prove that
$\sharp\mathsf{Repairs}[k]$ and $\sharp\mathsf{Sequences}[k]$ are in
$\mathsf{SpanTL}$, for each $k>0$, it is enough to focus on databases $D$,
queries $Q$, and generalized hypertree decompositions $H$ such that $(D,Q,H)$
is in normal form.

We first prove Proposition E.1 in the special case that $H$ is already
complete. Then, the more general result will follow from the fact that
logspace reductions can be composed (see, e.g., (Arora and Barak, 2009)), and
from the following well-known result:

###### Lemma E.2 ((Got, 2002)).

Given a CQ $Q(\bar{x})$ and a generalized hypertree decomposition $H$ for $Q$
of width $k$, a complete generalized hypertree decomposition $H^{\prime}$ of
$Q$ of width $k$ always exists, and can be computed in logarithmic space in
the combined size of $Q$ and $H$.

In the rest of this section, we focus on proving Proposition E.1, assuming
that $H$ is complete. We start by discussing how $\hat{D}$, $\hat{Q}(\bar{x})$
and $\hat{H}$ are constructed. In what follows, fix a database $D$, a set
$\Sigma$ of primary keys, a CQ $Q(\bar{x})$ from $\mathsf{SJF}$, a _complete_
generalized hypertree decomposition $H$ of $Q$ of width $k$, and a tuple
$\bar{c}\in\mathsf{dom}(D)^{\bar{x}}$.

#### Construction of $(\hat{D},\hat{Q},\hat{H})$

Assume $H=(T,\chi,\lambda)$, with $T=(V,E)$, and assume $Q(\bar{x})$ is a CQ
of the form $\text{Ans}(\bar{x})\text{ :-
}R_{1}(\bar{y}_{1}),\ldots,R_{n}(\bar{y}_{n})$.

The Query $\hat{Q}$. The query $\hat{Q}$ is obtained by modifying $Q$ as
follows. If $P_{1}/n_{1},\ldots,P_{m}/n_{m}$ are all the relations occurring
in $D$ but not in $Q$, add two atoms of the form $P_{i}(\bar{z}_{i})$ and
$P^{\prime}_{i}(z_{i}^{\prime})$ to $Q$, for each $i\in[m]$, where
$P_{i}^{\prime}/1$ is a fresh unary relation, $\bar{z}_{i}$ is a tuple of
$n_{i}$ distinct variables not occurring in $Q$, and
$z_{i}^{\prime}\not\in\bar{z}_{i}$ is a variable not occuring in $Q$.
Moreover, if $v_{1},\ldots,v_{\ell}$ are all the vertices in $V$, with $v_{i}$
having $h_{i}\geq 0$ children in $T$, create $h_{i}+1$ fresh unary relations
$S^{(1)}_{v_{i}}/1,\ldots,S^{(h_{i}+1)}_{v_{i}}/1$, for each $i\in[\ell]$, not
occurring anywhere in $Q$, and add to $Q$ the atom
$S^{(j)}_{v_{i}}(w^{(j)}_{v_{i}})$, for each $i\in[\ell]$, and
$j\in[h_{i}+1]$, where $w^{(j)}_{v_{i}}$ is a variable. Hence, $\hat{Q}$ is of
the form:

$\text{Ans}(\bar{x})\text{ :-
}R_{1}(\bar{y}_{1}),\ldots,R_{n}(\bar{y}_{n}),P_{1}(\bar{z}_{1}),P^{\prime}_{1}(z_{1}^{\prime})\ldots,P_{m}(\bar{z}_{m}),P^{\prime}_{m}(z_{m}^{\prime}),\\\
S^{(1)}_{v_{1}}(w^{(1)}_{v_{1}}),\ldots,S^{(h_{1}+1)}_{v_{1}}(w^{(h_{1}+1)}_{v_{1}}),\ldots,S^{(1)}_{v_{\ell}}(w^{(1)}_{v_{\ell}}),\ldots,S^{(h_{\ell}+1)}_{v_{\ell}}(w^{(h_{\ell}+1)}_{v_{\ell}}).$

The query $\hat{Q}$ is clearly self-join free.

The Database $\hat{D}$. The database $\hat{D}$ is obtained from $D$ by adding
an atom of the form $P^{\prime}_{i}(c)$, for each $i\in[m]$, and an atom of
the form $S^{(j)}_{v}(c)$, for each $v\in V$, and $j\in[h+1]$, where $h\geq 0$
is the number of children of $v$ in $T$, and $c$ is some constant.

The Decomposition $\hat{H}$. We now discuss how
$\hat{H}=(\hat{T},\hat{\chi},\hat{\lambda})$, with
$\hat{T}=(\hat{V},\hat{E})$, is constructed:

  * •

Concerning the vertex set $\hat{V}$, for each vertex $v\in V$ in $T$, having
$h\geq 0$ children $u_{1},\ldots,u_{h}$, $\hat{V}$ contains $h+1$ vertices
$v^{(1)},\ldots,v^{(h+1)}$, and for each $i\in[m]$, $\hat{V}$ contains the
vertices $v_{P_{i}}$ and $v_{P^{\prime}_{i}}$.

  * •

The edge set $\hat{E}$ contains the edges $v_{P_{i}}\rightarrow
v_{P^{\prime}_{i}}$, $v_{P_{i}}\rightarrow v_{P_{i+1}}$, for each $i\in[m-1]$,
and the edges $v_{P_{m}}\rightarrow v_{P^{\prime}_{m}}$, $v_{P_{m}}\rightarrow
v^{(1)}$, where $v\in V$ is the root of $T$. Moreover, for each _non-leaf_
vertex $v\in V$ with $h>0$ children $u_{1},\ldots,u_{h}$, $\hat{E}$ contains
the edges $v^{(i)}\rightarrow u^{(1)}_{i}$ and $v^{(i)}\rightarrow v^{(i+1)}$,
for each $i\in[h]$.

  * •

Concerning $\hat{\chi}$ and $\hat{\lambda}$, for each $i\in[m]$,
$\hat{\chi}(v_{P_{i}})=\bar{z}_{i}$,
$\hat{\chi}(v_{P^{\prime}_{i}})=\\{z_{i}^{\prime}\\}$, and
$\hat{\lambda}(v_{P_{i}})=\\{P_{i}(\bar{z}_{i})\\}$,
$\hat{\lambda}(v_{P^{\prime}_{i}})=\\{P_{i}^{\prime}(z_{i}^{\prime})\\}$, and
for each vertex $v\in V$ with $h\geq 0$ children,
$\hat{\chi}(v^{(i)})=\chi(v)\cup\\{w^{(i)}_{v}\\}$, and
$\hat{\lambda}(v^{(i)})=\lambda(v)\cup\\{S^{(i)}_{v}(w^{(i)}_{v})\\}$, for
each $i\in[h+1]$.

#### Proving Proposition E.1 when $H$ is complete

We now proceed to show that $(\hat{D},\hat{Q},\hat{H})$ enjoys all the
properties stated in Proposition E.1, assuming that $H$ is complete.

Complexity of construction. We start by discussing the complexity of
constructing $(\hat{D},\hat{Q},\hat{H})$. Constructing the query $\hat{Q}$
requires producing, in the worst case, two atoms for each relation in $D$, and
$|V|$ atoms, for each vertex $v\in V$, and so the number of atoms in $\hat{Q}$
is $O(|Q|+|D|+|V|^{2})$, where $|Q|$ is the number of atoms in $Q$. Each atom
can be constructed individually using logarithmic space, and by reusing the
space for each atom. We can show the database $\hat{D}$ is constructible in
logspace with a similar argument. Regarding $\hat{H}$, the set $\hat{V}$
contains at most $|V|$ vertices for each node of $V$, plus two nodes for each
relation in $D$. Hence, $|\hat{V}|\in O(|V|^{2}+|D|)$, and each vertex of
$\hat{V}$ can be constructed by a simple scan of $E$, $D$ and $Q$. Moreover,
$\hat{E}$ contains $2\times m\leq 2\times|D|$ edges, i.e. the edges of the
binary tree involving the vertices of the form $v_{P_{i}},v_{P^{\prime}_{i}}$,
and the vertex $v^{(1)}$, where $v\in V$ is the root of $T$, plus at most
$2\times|V|$ edges for each vertex of $V$, so overal $|\hat{E}|\in
O(|V|^{2}+|D|)$. Again, each edge is easy to construct. Finally, constructing
$\hat{\chi}$ and $\hat{\lambda}$ requires a simple iteration over $D$ and
$\hat{V}$, and copying the contents of $\chi$, and $\lambda$.

$\hat{H}$ is a proper decomposition of width $k+1$. We now argue that
$\hat{H}$ is a generalized hypertree decomposition of $\hat{Q}$ of width
$k+1$. We need to prove that _(1)_ for each atom $R(\bar{y})$ in $\hat{Q}$,
there is a vertex $v\in\hat{V}$ with
$\bar{y}\setminus\bar{x}\subseteq\hat{\chi}(v)$, _(2)_ for each
$x\in\mathsf{var}(\hat{Q})\setminus\bar{x}$, the set $\\{v\in\hat{V}\mid
x\in\hat{\chi}(v)\\}$ induces a connected subtree of $\hat{T}$, _(3)_ for each
$v\in\hat{V}$, $\hat{\chi}(v)\subseteq\mathsf{var}(\hat{\lambda}(v))$, and
_4)_ $\max_{v\in\hat{V}}|\lambda(v)|=k+1$.

We start with _(1)_. For each atom $R_{i}(\bar{y}_{i})$, for $i\in[n]$ in
$\hat{Q}$, since there is a vertex $v\in V$ with
$\bar{y}_{i}\setminus\bar{x}\subseteq\chi(v)$, then, e.g., the vertex
$v^{(1)}\in\hat{V}$ is such that
$\bar{y}_{i}\setminus\bar{x}\subseteq\hat{\chi}(v^{(1)})$, by construction of
$\hat{\chi}$. Furthermore, for each atom $P_{i}(\bar{z}_{i})$ (resp.,
$P_{i}^{\prime}(z_{i}^{\prime})$) in $\hat{Q}$, with $i\in[m]$, by
construction of $\hat{\chi}$,
$\bar{z}_{i}\setminus\bar{x}=\bar{z}_{i}\subseteq\hat{\chi}(v_{P_{i}})$
(resp., $z_{i}^{\prime}\not\in\bar{x}$, and
$z_{i}^{\prime}\in\hat{\chi}(v_{P^{\prime}_{i}})$), and for each atom
$S^{(i)}_{v}(w^{(i)}_{v})$ in $\hat{Q}$, with $v\in V$, we have that
$w^{(i)}_{v}\not\in\bar{x}$, and $w^{(i)}_{v}\in\hat{\chi}(v^{(i)})$, again by
construction of $\hat{\chi}$.

We now show item _(2)_. Consider a variable
$x\in\mathsf{var}(\hat{Q})\setminus\bar{x}$. We distinguish two cases:

  * •

Assume $x\not\in\mathsf{var}(Q)\setminus\bar{x}$, i.e.,
$x\in\mathsf{var}(\hat{Q})\setminus\mathsf{var}(Q)$. Hence, either $x$ occurs
in some atom of the form $P_{i}(\bar{z}_{i})$ (resp.,
$P_{i}^{\prime}(z_{i}^{\prime})$) in $\hat{Q}$, which means $x$ occurs only in
$\hat{\chi}(v_{P_{i}})$ (resp., $\hat{\chi}(v_{P_{i}^{\prime}})$), and thus
$v_{P_{i}}$ (resp., $v_{P_{i}^{\prime}}$) trivially forms a connected subtree,
or $x=w^{(i)}_{v}$, for some atom of the form $S^{(i)}_{v}(w^{(i)}_{v})$ in
$\hat{Q}$, with $v\in V$, which means $x$ occurs only in
$\hat{\chi}(v^{(i)})$, and thus $v^{(i)}$ trivially forms a connected subtree.

  * •

Assume now that $x\in\mathsf{var}(Q)\setminus\bar{x}$. By contruction of
$\hat{H}$, for each $v\in V$ having $x\in\chi(v)$, $x$ occurs in
$\hat{\chi}(v^{(i)})$, for each $i\in[h+1]$, where $h\geq 0$ is the number of
children of $v$ in $T$, and $x$ does not occur anywhere else in $\hat{T}$.
Since the set of vertices $\\{v\mid x\in\chi(v)\\}$ forms a subtree of $T$, by
assumption, and since for each $v\in V$, with $h\geq 0$ children
$u_{1},\ldots,u_{h}$ in $T$, the vertices $v^{(1)},\ldots,v^{(h+1)}$ form a
path in $\hat{T}$, and since when $h>0$, each $v^{(i)}$, with $i\in[h]$, is
connected to $u_{i}^{(1)}$ in $\hat{T}$, the set $\\{v\in\hat{V}\mid
x\in\hat{\chi}(v)\\}$ forms a subtree of $\hat{T}$, as needed.

We finally show item _(3)_. Consider a vertex $u\in\hat{V}$. If $v=v_{P_{i}}$
(resp., $v=v_{P_{i}^{\prime}}$), for some $i\in[m]$, then
$\hat{\chi}(v)=\bar{z}_{i}$ (resp., $z_{i}^{\prime}$), and
$\hat{\lambda}(v)=\\{P_{i}(\bar{z}_{i})\\}$ (resp.,
$\\{P_{i}^{\prime}(z_{i}^{\prime})\\}$), and the claim follows trivially. If
$u=v^{(i)}$, for some $v\in V$, and $i\in[h+1]$, where $h\geq 0$ is the number
of children of $v$ in $T$, then
$\hat{\chi}(v^{(i)})=\chi(v)\cup\\{w^{(i)}_{c}\\}$ and
$\hat{\lambda(v)}=\lambda(v)\cup\\{S^{(i)}_{v}(w^{(i)}_{v})\\}$. Since
$\chi(v)\subseteq\mathsf{var}(\lambda(v))$, the claim follows. Finally, to
prove _4)_ it is enough to observe that for any vertex $u\in\hat{V}$,
$\hat{\lambda}(u)$ contains either one atom, or one atom more than
$\lambda(v)$, where $v\in V$ is the node of $T$ from which $u$ has been
contructed. Hence, $\hat{H}$ is a generalized hypertree decomposition of
$\hat{Q}$ of width $k+1$.

$(\hat{D},\hat{Q},\hat{H})$ is in normal form. We now prove that
$(\hat{D},\hat{Q},\hat{H})$ is in normal form, i.e., _(1)_ every relation in
$\hat{D}$ also occurs in $\hat{Q}$, _(2)_ $\hat{H}$ is 2-uniform, and _(3)_
strongly complete. The fact that _(1)_ holds follows by construction of
$\hat{D}$ and $\hat{Q}$. To see why _(2)_ holds, note that every non-leaf node
in $\hat{T}$ has always exactly two children. Finally, we show item _(3)_.
Consider an atom $\alpha$ in $\hat{Q}$. By construction of $\hat{\chi}$ and
$\hat{\lambda}$, if $\alpha$ is of the form $P_{i}(\bar{z}_{i})$ (resp.,
$P_{i}^{\prime}(z_{i})$), then $v_{P_{i}}$ (resp., $v_{P_{i}^{\prime}}$) is a
covering vertex for $\alpha$. Moreover, if $\alpha$ is of the form
$S^{(i)}_{v}(w^{(i)}_{v})$, for some $v\in V$, then $v^{(i)}$ is a covering
vertex for $S^{(i)}_{v}(w^{(i)}_{v})$. Finally, if $\alpha$ is of the form
$R_{i}(\bar{y}_{i})$, with $i\in[n]$, then if $v\in V$ is the covering vertex
of $\alpha$ in $T$ (it always exists, since $H$ is complete, by assumption),
then any vertex of the form $v^{(j)}$ in $\hat{V}$ is a covering vertex for
$R_{i}(\bar{y}_{i})$ in $\hat{T}$. Hence, $\hat{H}$ is complete. To see that
$\hat{H}$ is _strongly_ complete it is enough to observe that every vertex $v$
of $\hat{T}$ is such that $\hat{\lambda}(v)$ contains an atom $\alpha$, whose
variables all occur in $\hat{\chi}(v)$, such that that
$\alpha\not\in\hat{\lambda}(u)$, for any other $u\in\hat{V}$, different from
$v$. So, $(\hat{D},\hat{Q},\hat{H})$ is in normal form.

$(\hat{D},\hat{Q},\hat{H})$ preserves the counts. In this last part we need to
show

$|\\{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}))\\}|.$

To prove both claims, we rely on the following auxiliary notion:

###### Definition E.3 (Key Violation).

Consider a schema $\mathbf{S}$, a database $D^{\prime}$ over $\mathbf{S}$, and
a key $\kappa=\mathsf{key}(R)=A$, with $R\in\mathbf{S}$. A
$D^{\prime}$-violation of $\kappa$ is a set $\\{f,g\\}\subseteq D^{\prime}$ of
facts such that $\\{f,g\\}\not\models\kappa$. We denote the set of
$D^{\prime}$-violations of $\kappa$ by $\mathsf{V}(D^{\prime},\kappa)$.
Furthermore, for a set $\Sigma^{\prime}$ of keys, we denote by
$\mathsf{V}(D^{\prime},\Sigma^{\prime})$ the set
$\\{(\kappa,v)\mid\kappa\in\Sigma^{\prime}\textrm{~{}~{}and~{}~{}}v\in\mathsf{V}(D^{\prime},\kappa)\\}$.

Note that any $(D^{\prime},\Sigma^{\prime})$-justified operation of the form
$-F$, for some database $D^{\prime}$ and set $\Sigma^{\prime}$ of keys, is
such that $F\subseteq\\{f,g\\}$, where $\\{f,g\\}$ is some
$D^{\prime}$-violation in $\mathsf{V}(D^{\prime},\Sigma^{\prime})$. We now
reason about the sets $\mathsf{V}(D,\Sigma)$ and $\mathsf{V}(\hat{D},\Sigma)$
of $D$-violations and $\hat{D}$-violations, respectively, of all keys in
$\Sigma$. In particular, note that $\hat{D}=D\cup C$, where $D\cap
C=\emptyset$, and each fact $\alpha\in C$ is over a relation that no other
fact mentions in $\hat{D}$. Hence, we conclude that
$\mathsf{V}(D,\Sigma)=\mathsf{V}(\hat{D},\Sigma)$. Moreover, we observe that
$\hat{Q}$ contains all atoms of $Q$, and in addition, for each fact
$R(\bar{t})\in C$, a single atom $R(\bar{y})$, where each variable in
$\bar{y}$ occurs exactly ones in $\hat{Q}$. The above observations imply that:

  1. (1)

$\mathsf{CRS}(D,\Sigma)=\mathsf{CRS}(\hat{D},\Sigma)$;

  2. (2)

for every database $D^{\prime}$, $D^{\prime}\in\mathsf{ORep}(D,\Sigma)$ iff
$D^{\prime}\cup C\in\mathsf{ORep}(\hat{D},\Sigma)$;

  3. (3)

for each $D^{\prime}\in\mathsf{ORep}(D,\Sigma)$, $\bar{c}\in Q(D)$ iff
$\bar{c}\in\hat{Q}(D^{\prime}\cup C)$, where $D^{\prime}\cup
C\in\mathsf{ORep}(\hat{D},\Sigma)$.

Hence, item (2) and item (3) together imply
$|\\{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})\\}|$,
while all three items imply $|\\{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 concludes our proof.

##  Appendix F Proof of Lemma 5.2

We proceed to show that:

###### 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})\\}|$.

We start by proving that the algorithm can be implemented as a well-behaved
ATO $M^{k}_{R}$, and then we show that the number of valid outputs of
$M^{k}_{R}$ on input $D$, $\Sigma$, $Q(\bar{x})$, $H=(T,\chi,\lambda)$, and
$\bar{c}\in\mathsf{dom}(D)^{\bar{x}}$, with $(D,Q,H)$ in normal form, is
precisely the number of operational repairs
$D^{\prime}\in\mathsf{ORep}(D,\Sigma)$ such that $\bar{c}\in Q(D^{\prime})$.

###  F.1. Item (1) of Lemma 5.2

We are going to give a high level description of the ATO $M^{k}_{R}$
underlying the procedure $\sharp\mathsf{Rep}[k]$ in Algorithm 1. We start by
discussing the space used in the working tape. Every object that
$\sharp\mathsf{Rep}[k]$ uses from its input and stores in memory, such as
vertices of $T$, atoms/tuples from $D$ and $Q$, etc., can be encoded using
logarithmically many symbols via a pointer encoded in binary to the part of
the input where the object occurs, and thus can be stored in the working tape
of $M^{k}_{R}$ using logarithmic space. Hence, the node $v$ of $T$, the sets
$A$ and $A^{\prime}$, and the fact $\alpha$, all require logarithmic space in
the working tape (recall that $A$ and $A^{\prime}$ contain a fixed number,
i.e., $k$, of tuple mappings). It remains to discuss how $M^{k}_{R}$ can check
that _1)_ $A\cup A^{\prime}\cup\\{\bar{x}\mapsto\bar{c}\\}$ is coherent, _2)_
a vertex $v$ of $T$ is the $\prec_{T}$-minimal covering vertex of some atom,
and _3)_ iterate over each element of $\mathsf{block}_{R_{i_{j}},D}(\Sigma)$,
for some relation $R_{i_{j}}$; checking whether $v$ is a leaf, or guessing a
child of $u$ are all trivial tasks. To perform _1)_ , it is enough to try
every variable $x$ in $A^{\prime}\cup\\{\bar{x}\mapsto\bar{c}\\}$, and for
each such $x$, try every pair of tuple mappings, and check if they map $x$
differently; $x$ and the two tuple mappings can be stored as pointers. To
perform _2)_ , $M^{k}_{R}$ must be able to compute the depth of $v$ in $T$,
and iterate over all vertices at the same depth of $v$, in lexicographical
order, using logarithmic space. The depth can be easily computed by
iteratively following the (unique) path from the root of $T$ to $v$, in
reverse, and increasing a counter at each step. By encoding the counter in
binary, the depth of $v$ requires logarithmically many bits and can be stored
in the working tape. Iterating all vertices with the same depth of $v$ in
lexicographical order can be done iteratively, by running one pass over each
node of $T$, computing its depth $d$, and in case $d$ is different from the
depth of $v$, the node is skipped. During this scan, we keep in memory a
pointer to a node that at the end of the scan will point to the
lexicographically smaller node, e.g., $u$, among the ones with the same depth
of $v$. Then, when the subsequent node must be found, a new scan, as the
above, is performed again, by looking for the lexicographically smallest
vertex that is still larger than the previous one, i.e., $u$. This is the next
smallest node, and $u$ is updated accordingly. The process continues, until
the last node is considered. Storing a pointer to $u$ is feasible in logspace,
and thus, together with the computation of the depth $v$ in logspace, it is
possible to search for all nodes $u$ of $T$ such that $u\prec_{T}v$ in
logspace. Then, checking for each of these nodes whether $\lambda(u)$ contains
$R_{i_{j}}(\bar{c}_{j})$, i.e., $v$ is not the $\prec_{T}$-minimal covering
vertex for $R_{i_{j}}(\bar{c}_{j})$ is trivial. Regarding _3)_ , one can
follow a similar approach to the one for iterating the nodes of the same depth
of $v$ lexicographically, where all the key values of the form
$\mathsf{key}_{\Sigma}(R_{i_{j}}(\bar{t}))$ are instead traversed
lexicographically.

We now consider the space used in the labeling tape of $M^{k}_{R}$. For this,
according to Algorithm 1, $M^{k}_{R}$ needs to write in the labeling tape
facts $\alpha$ of the database $D$, which, as already discussed, can be
uniquely encoded as a pointer to the input tape where $\alpha$ occurs.

Regarding the size of a computation of $M^{k}_{R}$, note that each vertex $v$
of $T$ makes the machine $M^{k}_{R}$ execute all the lines from line 1 to line
1 in Algorithm 1, before it universally branches to one configuration for each
child of $v$. Since all such steps can be performed in logspace, they induce
at most a polynomial number of existential configurations, all connected in a
path of the underlying computation of $M^{k}_{R}$. Since the number of
vertices of $T$ is linear w.r.t. the size of the input, and $M^{k}_{R}$ never
processes the same node of $T$ twice, the total size of any computation of
$M^{k}_{R}$ be polynomial.

It remains to show that for any computation $T^{\prime}$ of $M^{k}_{R}$, all
labeled-free paths in $T^{\prime}$ contain a bounded number of universal
computations. This follows from the fact that before line 1, $M^{k}_{R}$ has
necessarily moved to a labeling state (recall that $H$ is strongly complete,
and thus every vertex of $T$ is the $\prec_{T}$-minimal covering vertex of
some atom). Hence, when reaching line 1, either $v$ is a leaf, and thus
$M^{k}_{R}$ halts, and no universal configuration have been visited from the
last labeling configuration, or $M^{k}_{R}$ universally branches to the (only
two) children of $v$, for each of which, a labeling configuration will
necessarily be visited (again, because $H$ is strongly complete). Branching to
two children requires visiting only one non-labeling configuration on each
path. Hence, $M^{k}_{R}$ is a well-behaved ATO.

###  F.2. Item (2) of Lemma 5.2

Fix a database $D$, a set $\Sigma$ of primary keys, a CQ $Q(\bar{x})$, a
generalized hypertree decomposition $H=(T,\chi,\lambda)$ of $Q$ of width $k$,
and a tuple $\bar{c}\in\mathsf{dom}(D)^{\bar{x}}$, where $(D,Q,H)$ is in
normal form. We show that there is a bijection from the valid outputs of
$M^{k}_{R}$ on input $(D,\Sigma,Q,H,\bar{c})$ to the set of operational
repairs $\\{D^{\prime}\in\mathsf{ORep}(D,\Sigma)\mid\bar{c}\in
Q(D^{\prime})\\}$. We define a mapping $\mu$ in the following way. Each valid
output $O=(V,E,\lambda^{\prime})$ is mapped to the set
$\\{\lambda^{\prime}(v)\mid v\in V\\}\setminus\\{\bot\\}$. Intuitively, we
collect all the labels of the nodes of the valid output which are not labeled
with $\bot$. To see that $\mu$ is indeed a bijection as needed, we now show
the following three statements:

  1. (1)

$\mu$ is correct, that is, it is indeed a function from the set $\\{O\mid
O\text{ is a valid output of }M\text{ on }(D,\Sigma,Q,H,\bar{c})\\}$ to
$\\{D^{\prime}\in\mathsf{ORep}(D,\Sigma)\mid\bar{c}\in Q(D^{\prime})\\}$.

  2. (2)

$\mu$ is injective.

  3. (3)

$\mu$ is surjective.

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

Consider an arbitrary valid output $O=(V,E,\lambda^{\prime})$ of $M^{k}_{R}$
on $(D,\Sigma,Q,H,\bar{c})$. Let $D^{\prime}=\mu(O)$. First note that all
labels assigned in Algorithm 1 are database atoms or the symbol $\bot$. Thus,
$D^{\prime}$ is indeed a database. Further, we observe in Algorithm 1 that for
every relation $R$ and every block $B\in\mathsf{block}_{R,D}(\Sigma)$ exactly
one vertex is labeled in the output $O$ (with either one of the atoms of the
block or $\bot$) and, hence, we have that $D^{\prime}\models\Sigma$, i.e.,
$D^{\prime}\in\mathsf{ORep}(D,\Sigma)$ since every consistent subset of $D$ is
an operational repair of $D$ w.r.t. $\Sigma$. What remains to be argued is
that $\bar{c}\in Q(D^{\prime})$.

Since we consider a complete hypertree decomposition, every atom
$R_{i}(\bar{y}_{i})$ of $Q$ has a $\prec_{T}$-minimal covering vertex $v$. By
definition of covering vertex, we have that $\bar{y}_{i}\subseteq\chi(v)$ and
$R_{i}(y_{i})\in\lambda(v)$. In the computation, for each vertex $v$ of $T$,
we guess a set
$A^{\prime}=\\{\bar{y}_{i_{1}}\mapsto\bar{c}_{1},\ldots,\bar{y}_{i_{\ell}}\mapsto\bar{c}_{\ell}\\}$
assuming
$\lambda(v)=\\{R_{i_{1}}(\bar{y}_{i_{1}}),\ldots,R_{i_{\ell}}(\bar{y}_{i_{\ell}})\\}$,
such that $R_{i_{j}}(\bar{c}_{j})\in D$ for $j\in[\ell]$ and all the mappings
are coherent with $\bar{x}\mapsto\bar{c}$. In particular, when we consider the
$\prec_{T}$-minimal covering vertex of the atom $R_{i}(y_{i})$ of $Q$, we
choose some mapping $\bar{y}_{i}\mapsto\bar{c}_{i}$ such that
$R_{i}(\bar{c}_{i})\in D$. When we consider the block $B$ of
$R_{i}(\bar{c}_{i})$ in line 5, we choose $\alpha=R_{i}(\bar{c}_{i})$ in line
7, which ensures that $D^{\prime}\cap B=R_{i}(\bar{c})$; that is, this fact
will be in the repair. Since $Q$ is self-join-free, the choice of which fact
to keep from the other blocks of $\mathsf{block}_{R_{i},D}(\Sigma)$ can be
arbitrary (we can also remove all the facts of these blocks). When we
transition from a node $v$ of $T$ to its children, we let $A:=A^{\prime}$, and
then, for each child, we choose a new set $A^{\prime}$ in line 2 that is
consistent with $A$ and with $\bar{x}\mapsto\bar{c}$.

This ensures that two atoms $R_{i}(\bar{y}_{i})$ and $R_{j}(\bar{y}_{j})$ of
$Q$ that share at least one variable are mapped to facts $R_{i}(\bar{c}_{i})$
and $R_{j}(\bar{c}_{j})$ of $D$ in a consistent way; that is, a variable that
occurs in both $\bar{y}_{i}$ and $\bar{y}_{j}$ is mapped to the same constant
in $\bar{c}_{i}$ and $\bar{c}_{j}$. Let $v$ and $u$ be the $\prec_{T}$-minimal
covering vertices of $R_{i}(\bar{y}_{i})$ and $R_{j}(\bar{y}_{j})$,
respectively. Let $z$ be a variable that occurs in both $\bar{y}_{i}$ and
$\bar{y}_{j}$. By definition of covering vertex, we have that
$\bar{y}_{i}\subseteq\chi(v)$ and $\bar{y}_{j}\subseteq\chi(u)$. By definition
of hypertree decomposition, the set of vertices $s\in T$ for which
$z\in\chi(s)$ induces a (connected) subtree of $T$. Therefore, there exists a
subtree of $T$ that contains both vertices $v$ and $u$, and such that
$z\in\chi(s)$ for every vertex $s$ of this subtree. When we process the root
$r$ of this subtree, we map the variable $z$ in the set $A^{\prime}$ to some
constant (since there must exist an atom $R_{k}(\bar{y}_{k})$ in $\lambda(r)$
such that $z$ occurs in $\bar{y}_{k}$ by definition of a hypertree
decomposition). Then, when we transition to the children of $r$ in $T$, we
ensure that the variable $z$ is mapped to the same constant, by choosing a new
set $A^{\prime}$ of mappings that is consistent with the set of mappings
chosen for $r$, and so forth. Hence, the variable $z$ will be consistently
mapped to the same constant in this entire subtree, and for every atom
$R_{i}(\bar{y}_{i})$ of $Q$ that mentions the variable $z$ it must be the case
that the $\prec_{T}$-minimal covering vertex $v$ of $R_{i}(\bar{y}_{i})$
occurs in this subtree because $z\in\chi(v)$. Hence, the sets $A$ of mappings
that we choose in an accepting computation map the atoms of the query to facts
of the database in a consistent way, and this induces a homomorphism $h$ from
$Q$ to $D$. since we choose mappings that are coherent with the mapping
$\bar{x}\mapsto\bar{c}$ of the answer variables of $Q$, we get that
$\bar{c}\in Q(D^{\prime})$.

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

Assume that there are two valid outputs $O=(V,E,\lambda^{\prime})$ and
$O^{\prime}=(V^{\prime},E^{\prime},\lambda^{\prime\prime})$ of $M^{k}_{R}$ on
$(D,\Sigma,Q,H,\bar{c})$ such that $\mu(O)=\mu(O^{\prime})$. Note that the
order in which the algorithm goes through relations $R_{i_{j}}$ in
$\lambda(v)$, for some vertex $v$ in $T$, and blocks $B$ of $R_{i_{j}}$ is
arbitrary, but fixed. Further, we only produce one label per block, since the
choices for each block of some atom $R_{i_{j}}(\bar{y}_{i})$ are only made in
the $\prec_{T}$-minimal covering vertex of $R_{i}(\bar{y}_{i})$. Now, since
$Q$ is self-join-free, no conflicting choices can be made on two different
nodes for the same relation. Since every block corresponds to exactly one
vertex in the output, and the order in which the blocks are dealt with in the
algorithm is fixed, all outputs are the same up to the labeling function,
i.e., $V=V^{\prime}$ and $E=E^{\prime}$ (up to variable renaming) and we only
need to argue that $\lambda^{\prime}=\lambda^{\prime\prime}$ to produce a
contradiction to the assumption that $O\neq O^{\prime}$. To this end, see
again that every block of $D$ corresponds to one vertex of $V$, which is
labeled with either an atom of that block or the symbol $\bot$ (to represent
that no atom should be kept in the repair). Fix some arbitrary vertex $v\in
V$. Let $B_{v}$ be the block that corresponds to the vertex $v$. If
$\lambda^{\prime}(v)=\bot$, we know that $\mu(O)\cap B_{v}=\emptyset$. Since
$\mu(O)=\mu(O^{\prime})$, we know that also $\mu(O^{\prime})\cap
B_{v}=\emptyset$ and thus $\lambda^{\prime\prime}(v)=\bot$ (if
$\lambda^{\prime\prime}(v)=\alpha$ for some $\alpha\in B_{v}$, then
$\mu(O^{\prime})\cap B_{v}=\alpha$). On the other hand, if
$\lambda^{\prime}(v)=\alpha$ for some $\alpha\in B_{v}$, with an analogous
argument, we have that also $\lambda^{\prime\prime}(v)=\alpha$ as needed.

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

Consider an arbitrary operational repair
$D^{\prime}\in\\{D^{\prime}\in\mathsf{ORep}(D,\Sigma)\mid\bar{c}\in
Q(D^{\prime})\\}$. We need to show that there exists a valid output
$O=(V,E,\lambda^{\prime})$ of $M^{k}_{R}$ on $(D,\Sigma,Q,H,\bar{c})$ such
that $\mu(O)=D^{\prime}$. Since $D^{\prime}\in\mathsf{ORep}(D,\Sigma)$ such
that $\bar{c}\in Q(D^{\prime})$, we know that there exists a homomorphism $h$
from $Q(\bar{x})$ to $D^{\prime}$ such that $h(\bar{x})=\bar{c}$. This means
that in line 2 of the algorithm, we can always guess the set $A^{\prime}$
according to $h$, since this will guarantee that $A^{\prime}\cup
A\cup\\{\bar{x}\mapsto\bar{c}\\}$ is coherent. Then, when traversing the
hypertree decomposition (and the relations in each node and the blocks in each
relation), we can always choose the labels according to $D^{\prime}$. Note
also that since every relation of $D$ occurs in $Q$, every block of $D$ is
considered in the algorithm. Fix some arbitrary block $B$ in $D$. If $|B|=1$,
then $B$ does not participate in a violation and it will always be present in
every operational repair $D^{\prime}$. Then, when $B$ is considered in
Algorithm 1, we set $\alpha$ to the only fact in $B$ in line 6 and label the
corresponding node in the output with $\alpha$. If $|B|\geq 2$ and some fact
$R_{i_{j}}(\bar{c_{j}})$ of $B$ is in the image of the homomorphism $h$, since
we chose $A^{\prime}$ in such a way that it is coherent with $h$, we guess
$\alpha$ as the fact $R_{i_{j}}(\bar{c_{j}})$ in line 7 of the algorithm.
Otherwise, we guess $\alpha$ as the fact that is left in $B$ in $D^{\prime}$
(if it exists), i.e., $\alpha:=B\cap D^{\prime}$, if $B\cap
D^{\prime}\neq\emptyset$, and $\alpha:=\bot$ otherwise. It should now be clear
that for an output $O$ generated in such a way, we have that
$\mu(O)=D^{\prime}$.

##  Appendix G Proof of Lemma 5.3

We prove the following lemma:

###### 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))\\}|$.

We start by proving that the algorithm can be implemented as a well-behaved
ATO $M^{k}_{S}$, and then we proceed to show that the number of valid outputs
of $M^{k}_{S}$ is precisely the number of complete repairing sequences $s$
such that $\bar{c}\in Q(s(D))$.

###  G.1. Item (1) of Lemma 5.3

The proof of this item proceeds similarly to the one for the first item of
Lemma 5.2. The additional part we need to argue about is how the ATO
$M^{k}_{S}$ underlying Algorithm 2 implements lines 2-2, and lines 2-2 using
logarithmic space in the working and labeling tape. Regarding lines 2-2, the
first two lines require storing a number no larger than $|D|$, which can be
easily stored in logarithmic space. Then, computing $\mathsf{shape}(n,\alpha)$
and $\sharp\mathsf{opsFor}(n,-g)$ is trivially doable in logarithmic space.
Similarly, guessing the number $p\in[\sharp\mathsf{opsFor}(n,-g)]$ requires
logarithmic space. The operation ”Label with $(-g,p)$” requires only
logarithmic space in the labeling tape, since both $-g$ and $p$ can be encoded
in logarithmic space. Similarly, additions and subtractions between two
logspace-encoded numbers can be carried out in logarithmic space.

The challenging part is guessing $p\in\left[{b\choose b^{\prime}}\right]$ and
writing $(\alpha,p)$ in the labeling tape, without explicitly storing $p$ and
${b\choose b^{\prime}}$ in the working tape, and not going beyond the space
bounds of the labeling tape. This is because ${b\choose b^{\prime}}$ and $p$
require, in principle, a polynomial number of bits, since they encode
exponentially large numbers w.r.t. the size of the input. To avoid the above,
$M^{k}_{S}$ does the following: it guesses one bit $d$ of $p$ at the time,
starting from the most significant one. Then, $M^{k}_{S}$ writes $(\alpha,d)$
in the labeling tape, moves to a labeling state, and then moves to a non-
labeling state, and continues with the next bit of $p$. We now need to show
how each bit of $p$ can be guessed in logarithmic space, by also guaranteeing
that the bits chosen so far place $p$ in the interval $\left[{b\choose
b^{\prime}}\right]$. Note that

${b\choose
b^{\prime}}=\dfrac{b!}{b^{\prime}!\times(b-b^{\prime})!}=\dfrac{b\times(b-1)\times\cdot\times(b-b^{\prime}+1)}{b^{\prime}!},$

and thus ${b\choose b^{\prime}}$ can be computed by performing two iterated
multiplications: $B_{1}=b\times(b-1)\times\cdot\times(b-b^{\prime}+1)$, and
$B_{2}=b^{\prime}!=b^{\prime}\times(b^{\prime}-1)\times\cdots\times 1$, of
polynomially many terms, and then by dividing $B_{1}/B_{2}$. Iterated
multiplication and integer division are all doable in deterministic logspace
(Chiu et al., 2001), and thus, by composition of logspace-computable functions
(Arora and Barak, 2009), $M^{k}_{S}$ can compute one bit of ${b\choose
b^{\prime}}$ at the time, using at most logspace, and use such a bit to guide
the guess of the corresponding bit of $p$.

We conclude by discussing lines 2-2. Guessing $p\in\\{0,\ldots,N\\}$ is
clearly feasible in logspace, since $N\leq|D|$. The remaining lines can be
implemented in logarithmic space because of arguments similar to the ones used
for the proof of item (1) of Lemma 5.2.

###  G.2. Item (2) of Lemma 5.3

We prove that there is a one-to-one correspondence between the valid outputs
of $M^{k}_{S}$ on $D,\Sigma,Q,H,\bar{c}$ and the complete repairing sequences
$s$ such that $\bar{c}\in Q(s(D))$. Assume that
$H=(T^{H},\chi^{H},\lambda^{H})$ with $T^{H}=(V^{H},E^{H})$. In what follows,
for each set $P$ of $D$-operations, we assume an arbitrary fixed order over
the operations in $P$ that we denote by $\prec_{P}$. In addition, let
$B_{1},\dots,B_{m}$ be the order defined over all the blocks of $D$ by first
considering the order $\prec_{T^{H}}$ over the nodes of $T^{H}$, then for each
node $v$ of $T^{H}$ considering the fixed order used in Algorithm 2 over the
relation names $R_{i}$ such that $v$ is the $\prec_{T^{H}}$-minimal covering
vertex of the atom $R_{i}(\bar{y}_{i})$ of $Q$, and finally, for each relation
name $R_{i}$, considering the fixed order used in Algorithm 2 over the blocks
of $\mathsf{block}_{R_{i},D}(\Sigma)$. For each $i\in[m]$, consider the first
$i$ blocks $B_{1},\dots,B_{i}$, and let $s_{\leq i-1}$ be a sequence of
operations over the blocks $B_{1},\dots,B_{i-1}$ and $s_{i}$ be a sequence of
operations over $B_{i}$. We assume an arbitrary fixed order over all the
permutations of the operations in $s_{\leq i-1},s_{i}$ that are coherent with
the order of the operations in $s_{\leq i-1}$ and with the order of operations
in $s_{i}$ (i.e., all the possible ways to interleave the sequences $s_{\leq
i-1},s_{i}$), and denote it by $\prec_{s_{\leq i-1},s_{i}}$. For simplicity,
we assume in the proof that in line 19 of Algorithm 2 we produce a single
label $(\alpha,p)$ rather than a sequence of labels representing the binary
representation of $p$. This has no impact on the correctness of the algorithm.

#### Sequences to Valid Outputs.

Consider a complete repairing sequence $s$ such that $\bar{c}\in Q(s(D))$. We
construct a valid output $O=(V^{\prime},E^{\prime},\lambda^{\prime})$ as
follows. First, for each vertex $v\in V^{H}$, we add to $V^{\prime}$ a
corresponding vertex $v^{\prime}$. If there exists and edge $(v,u)\in E^{H}$,
then we add the corresponding edge $(v^{\prime},u^{\prime})$ to $E^{\prime}$.

Next, for every vertex $v^{\prime}\in V^{\prime}$ corresponding to a vertex
$v\in V^{H}$, we replace $v^{\prime}$ by a path
$v^{\prime}_{1}\rightarrow\dots\rightarrow v^{\prime}_{m}$ of vertices. We add
the edges $(u^{\prime},v^{\prime}_{1})$ and
$(v^{\prime}_{m},u^{\prime}_{\ell})$ for $\ell\in[2]$, assuming that
$u^{\prime}$ is the parent of $v^{\prime}$ and $u^{\prime}_{1},u^{\prime}_{2}$
are the children of $v^{\prime}$ in $V^{\prime}$. Note that initially each
node of $V^{\prime}$ has precisely two children since we assume that $(D,Q,H)$
is in normal form; hence, every node of $V^{H}$ has two children. The path
$v^{\prime}_{1}\rightarrow\dots\rightarrow v^{\prime}_{m}$ is such that for
every relation name $R_{i}$ with $v$ being the $\prec_{T^{H}}$-minimal
covering vertex of the atom $R_{i}(\bar{y}_{i})$ of $Q$ (note that for every
$v$ there is at least one such relation name since $(D,Q,H)$ is in normal
form), and for every block $B\in\mathsf{block}_{R_{i},D}(\Sigma)$, there is
subsequence $v^{\prime}_{i_{1}}\rightarrow\dots\rightarrow v^{\prime}_{i_{t}}$
where:

  * •

$t-1$ is the number of operations in $s$ over the block $B$,

  * •

$\lambda^{\prime}(v^{\prime}_{i_{r}})=(-1,p)$ if the $r$-th operation of $s$
over $B$ is the $p$-th operation according to $\prec_{P}$, where $P$ is the
set of operations removing a single fact $f\not\in s(D)$ of $B^{\prime}$, and
$B^{\prime}\subseteq B$ is obtained by applying the first $r-1$ operations of
$s$ over $B$, and excluding the fact of $s(D)\cap B$ (if such a fact exists),

  * •

$\lambda^{\prime}(v^{\prime}_{i_{r}})=(-2,p)$ if the $r$-th operation of $s$
over $B$ is the $p$-th operation according to $\prec_{P}$, where $P$ is the
set of operations removing a pair of facts $f,g\not\in s(D)$ of $B^{\prime}$,
and $B^{\prime}\subseteq B$ is obtained by applying the first $r-1$ operations
of $s$ over $B$, and excluding the fact of $s(D)\cap B$ (if such a fact
exists),

  * •

$\lambda^{\prime}(v^{\prime}_{i_{t}})=(\alpha,p)$ if $B\cap
s(D)=\\{\alpha\\}$, $B$ is the $i$-th block of $D$, and the permutation of the
operations of $s$ over the blocks $B_{1},\dots,B_{i}$ is the $p$-th in
$\prec_{s_{\leq i-1},s_{i}}$, where $s_{\leq i-1}$ is the sequence of
operations in $s$ over the blocks $B_{1},\dots,B_{i-1}$ and $s_{i}$ is the
sequence of operations in $s$ over the block $B_{i}$,

  * •

$\lambda^{\prime}(v^{\prime}_{i_{t}})=(\bot,p)$ if $B\cap s(D)=\emptyset$, $B$
is the $i$-th block of $D$, and then the permutation of the operations of $s$
over the blocks $B_{1},\dots,B_{i}$ is the $p$-th in $\prec_{s_{\leq
i-1},s_{i}}$, where $s_{\leq i-1}$ is the sequence of operations in $s$ over
the blocks $B_{1},\dots,B_{i-1}$ and $s_{i}$ is the sequence of operations in
$s$ over the block $B_{i}$.

The order of such subsequences in $v^{\prime}_{1}\rightarrow\dots\rightarrow
v^{\prime}_{m}$ must be coherent with the order $B_{1},\dots,B_{n}$: the first
subsequence corresponds to the first block of the first relation name $R_{i}$
with $v^{\prime}$ being the $\prec_{T^{H}}$-minimal covering vertex of the
atom $R_{i}(\bar{y}_{i})$ of $Q$, etc.

Since $H$ is complete, every atom $R_{i}(\bar{y}_{i})$ of $Q$ has a
$\prec_{T^{H}}$-minimal covering vertex, and since $(D,Q,H)$ is in normal
form, every relation of $D$ occurs in $Q$. Hence, every block of $D$ has a
representative path of nodes in $O$. Since $\bar{c}\in Q(s(D))$, there exists
a homomorphism $h$ from $Q$ to $D$ with $h(\bar{x})=\bar{c}$. Hence, there is
an accepting computation of $M^{k}_{S}$ with $O$ being its output, that is
obtained in the following way via Algorithm 2:

  1. (1)

We guess $N=|s|$ (i.e., the length of the sequence $s$) in line 2,

  2. (2)

for every node $v$, assuming
$\lambda(v)=\\{R_{i_{1}}(\bar{y}_{i_{1}}),\ldots,R_{i_{\ell}}(\bar{y}_{i_{\ell}})\\}$,
we guess $A^{\prime}=$ $\\{\bar{y}_{i_{1}}\mapsto
h(\bar{y}_{i_{1}}),\ldots,\bar{y}_{i_{\ell}}\mapsto h(\bar{y}_{i_{\ell}})\\}$
in line 3,

  3. (3)

for every block $B$, we guess $\alpha=s(D)\cap B$ if $s(D)\cap B\neq\emptyset$
or $\alpha=\bot$ otherwise in lines 7—9,

  4. (4)

for every block $B$ with $v^{\prime}_{i_{1}}\rightarrow\dots\rightarrow
v^{\prime}_{i_{t}}$ being its representative path in $O$, in the $r$-th
iteration of the while loop of line 12 over this block, for all $1\leq r\leq
t-1$, we guess $-g$ in line 14 and $p$ in line 15 assuming that
$\lambda^{\prime}(v^{\prime}_{i_{r}})=(-g,p)$,

  5. (5)

for every block $B$ with $v^{\prime}_{i_{1}}\rightarrow\dots\rightarrow
v^{\prime}_{i_{t}}$ being its representative path in $O$, we guess $p$ in line
18 assuming $\lambda^{\prime}(v^{\prime}_{i_{t}})=(\alpha,p)$,

  6. (6)

we guess the total number $p$ of operations of $s$ over the blocks $B$ such
that $B\in\mathsf{block}_{R_{i},D}(\Sigma)$ and the $\prec_{T^{H}}$-minimal
covering vertex of the atom $R_{i}(\bar{y}_{i})$ of $Q$ occurs in the subtree
rooted at $u$ (the first child of $v$) in line 21.

The number $N$ that we guess in line 2 clearly belongs to $[|D|]$ because
$|s|\leq|D|$ for every complete repairing sequence $s$. Moreover, since $h$ is
a homomorphism from $Q$ to $D$ with $h(\bar{x})=\bar{c}$, for every atom
$R_{i}(\bar{y}_{i})$ of $Q$ it holds that $R_{i}(h(\bar{y}_{i}))\in D$; hence,
it is always possible to choose a set $A^{\prime}$ in line 3 that is coherent
with the homomorphism as well as with the previous choice and with the mapping
$\bar{x}\mapsto\bar{c}$—for every atom $R_{i}(\bar{y}_{i})$ that we consider,
we include the mapping $\bar{y}_{i}\mapsto h(\bar{y}_{i})$ in the set. In
addition, for every block $B$, since $s$ is a complete repairing sequence,
$s(D)\cap B$ either contains a single fact or no facts at all. Since
$\bar{c}\in Q(s(D))$, as witnessed by $h$, if $R_{i}(h(\bar{y}_{i}))\in B$,
then $s(D)$ contains the fact $R_{i}(h(\bar{y}_{i}))$ and this is the only
fact of $s(D)\cap B$. In this case, we will define
$\alpha=R_{i}(h(\bar{y}_{i}))$ in line 7 or line 8, when considering the block
$B$ in line 6.

Next, if $v^{\prime}_{i_{1}},\dots,v^{\prime}_{i_{t}}$ is the path of nodes in
$O$ representing the block $B$, and
$\lambda^{\prime}(v^{\prime}_{i_{r}})=(-g,p)$ for some $r\in[t-1]$, then
$p\in[\\#\mathsf{opsFor}(n,-g)]$. This holds since we start with $n=|B|$ if
$\alpha=\bot$ or $n=|B|-1$ otherwise, and decrease, in line 17, the value of
$n$ by $1$ when guessing $-1$ in line 14 (i.e, when applying an operation that
removes a single fact) or by $2$ when guessing $-2$ in line 14 (i.e., when
applying an operation that removes a pair of facts); hence, at the $r$-th
iteration of the while loop of line 12 over $B$, it holds that $n$ is
precisely the size of the subset $B^{\prime}$ that is obtained by applying the
first $r-1$ operations of $s$ over $B$, and excluding the fact of $s(D)\cap B$
if such a fact exists. This implies that $\\#\mathsf{opsFor}(n,-g)$ is
precisely the number of operations over $B^{\prime}$ that remove a single fact
if $-g=-1$ (there are $n$ such operations, one for each fact of $B^{\prime}$)
or the number of operations over $B^{\prime}$ that remove a pair of facts if
$-g=-2$ (there are $\frac{n(n-1)}{2}$ such operations, one for every pair of
facts of $B^{\prime}$). Note that the number of possible operations only
depends on the size of a block and not its specific set of facts, as all the
facts of a block are in conflict with each other. Since $\prec_{P}$ is a total
order over precisely these operations, we conclude that
$p\in[\\#\mathsf{opsFor}(n,-g)]$.

Next, we argue that if $\lambda^{\prime}(v^{\prime}_{i_{t}})=(\alpha,p)$ (or
$\lambda^{\prime}(v^{\prime}_{i_{t}})=(\bot,p)$), then $p$ is a value in
$[{b\choose b^{\prime}}]$. An important observation here is that whenever we
reach line 18, and assuming that $B$ is the block that is currently being
handled and it is the $i$-th block of $D$ (w.r.t. the order
$B_{1},\dots,B_{m}$ over the blocks), we have that $b^{\prime}$ is the number
of operations in $s$ over the blocks $B_{1},\dots,B_{i-1}$ and $b$ is the
number of operations in $s$ over the blocks $B_{1},\dots,B_{i}$. This holds
since we start with $b=b^{\prime}=0$, and increase the value of $b$ by one in
every iteration of the while loop of line 12 (hence, with every operation that
we apply over a certain block). When we are done handling a block, we define
$b^{\prime}=b$ in line 11, before handling the next block. Moreover, for each
relation name $R_{j}$, we handle the blocks of
$\mathsf{block}_{R_{j},D}(\Sigma)$ in the fixed order defined over these
blocks, and for each node $v$, we handle the relation names $R_{j}$ with $v$
being the $\prec_{T^{H}}$-minimal covering vertex of the atom
$R_{j}(\bar{y}_{j})$ of $Q$ in the fixed order defined over these relation
names.

In lines 20—25, when we consider the children of the current node $v$, we
guess the number $p$ of operations for the first child of $v$ (hence, for all
the blocks $B^{\prime}\in\mathsf{block}_{R_{j},D}(\Sigma)$ such that the
$\prec_{T^{H}}$-minimal covering vertex of the atom $R_{j}(\bar{y}_{j})$ of
$Q$ is in the subtree rooted at $v$, as each block is handled under its
$\prec_{T^{H}}$-minimal covering vertex), and we define $b=b+p$ for the second
child. By doing so, we take into account all the operations over the blocks
that occur before the blocks handled under the second child of $v$ in the
order, even before they are actually handled. Note that all the blocks handled
under the first child appear before the blocks handled under the second child,
as the first child appears before the second child in the order
$\prec_{T^{H}}$ by definition. Hence, whenever we consider a certain block in
line 6, $b$ always holds the total number of operations applied over the
previous blocks in the order, in line 11 we define $b^{\prime}=b$, and when we
finish handling this block in the last iteration of the while loop of line 12,
$b$ holds the total number of operations applied over the previous blocks in
the order and the current block.

Now, in our procedure for constructing $O$, the value $p$ that we choose for
$\lambda^{\prime}(v_{i_{t}}^{\prime})$ is determined by the number of
permutations of the sequences $s_{\leq i-1}$ and $s_{i}$, where $s_{\leq i-1}$
is the sequence of operations in $s$ over the blocks $B_{1},\dots,B_{i-i}$ and
$s_{i}$ is the sequence of operations over $B_{i}$. As said, the number of
operations in $s_{\leq i-1}$ is the value of $b^{\prime}$ defined in line 11
when considering the block $B$ in line 6, and the number of operations in
$s_{\leq i}$ is precisely the value of $b$ after the last iteration of the
while loop of line 12. The number of ways to interleave these sequences, which
is the number of permutations of these operations that are coherent with the
order of the operations in both $s_{\leq i-1}$ and $s_{i}$ is precisely
${b\choose b^{\prime}}$, and so $p\in[{b\choose b^{\prime}}]$.

Finally, the number $p$ that we guess in line 21 is clearly in the range
$0,\dots,N$, as the number of operations of $s$ over the blocks $B$ that are
handled under some subtree of $T^{H}$ is bounded by the total number of
operations in $s$. Note that for every leaf of the described computation we
have that $N=0$ in line 27, as for each node $v$, the number $N$ of operations
that we assign to it is precisely the number of operations over the blocks
handled under its subtree. We conclude that the described computation is
indeed an accepting computation, and since _(1)_ the described computation and
$O$ consider the blocks of $D$ in the same order $B_{1},\dots,B_{n}$, each
block under its $\prec_{T^{H}}$-minimal covering vertex, and _(2)_ the only
labeling configurations are those that produce the labels in line 16 and line
19, and we use the labels of $O$ to define the computation, it is now easy to
verify that $O$ is the output of this computation.

It remains to show that two different sequences $s$ and $s^{\prime}$ give rise
to two different outputs $O$ and $O^{\prime}$. Assume that
$s=(o_{1},\dots,o_{m})$ and
$s^{\prime}=(o_{1}^{\prime},\dots,o_{\ell}^{\prime})$. If $m\neq\ell$, then
$O\neq O^{\prime}$ since the number of nodes in $O$ is $m+n$, where $n$ is the
total number of blocks of $D$ (one node for each operation and an additional
node for each block), and the number of nodes in $O^{\prime}$ is $\ell+n$. If
$m=\ell$, there are three possible cases. There first is when there is a block
$B$ such that the operations of $s$ over $B$ and the operations of
$s^{\prime}$ over $B$ conform to different templates or $s(D)\cap B\neq
s^{\prime}(D)\cap B$. In this case, the path of nodes in $O$ representing the
block $B$ and the path of nodes in $O^{\prime}$ representing this block will
have different labels, as at some point they will use a different $-g$, or a
different $\alpha$ for the last node.

The second case is when $s$ and $s^{\prime}$ conform to the same templates
over all the blocks and $s(D)\cap B=s^{\prime}(D)\cap B$ for every block $B$,
but they differ on the operations over some block $B$. Assume that they differ
on the $r$-th operation over $B$, and this is the first operation over this
block they differ on. In this case, the $r$-th node in the representative path
of $B$ in $O$ and the $r$-th node in the representative path of $B$ in
$O^{\prime}$ will have different labels, as they will use a different $p$.
This is the case since when determining the value of $p$ we consider the same
subset $B^{\prime}$ of $B$ in both cases (as the first $r-1$ operations over
$B$ are the same for both sequences and $s(D)\cap B=s^{\prime}(D)\cap B$), and
the same $-g$ (as they conform to the same template), and so the same set $P$
of operations. The value of $p$ then depends on the $r$-th operation of $s$
over $B$ (respectively, the $r$-th operation of $s^{\prime}$ over $B$) and the
order $\prec_{P}$ over the operations of $P$, and since these are two
different operations, the values will be different.

The last case is when $s$ and $s^{\prime}$ use the exact same operations in
the same order for every block. In this case, the only difference between $s$
and $s^{\prime}$ is that they interleave the operations over the different
blocks differently. For each $i\in[m]$, let $s_{\leq i-1}$ be the sequence of
operations in $s$ over the blocks $B_{1},\dots,B_{i-1}$, and let
$s^{\prime}_{\leq i-1}$ be the sequence of operations in $s^{\prime}$ over
these blocks. Let $B_{j}$ be the first block such that $s_{\leq
j-1}=s^{\prime}_{\leq j-1}$, but $s_{\leq j}\neq s^{\prime}_{\leq j}$. Note
that $s_{j}$ (the sequence of operations of $s$ over $B_{j}$) and
$s^{\prime}_{j}$ (the sequence of operations of $s^{\prime}$ over $B_{j}$ are
the same). In this case, the last node in the representative path of $B_{j}$
in $O$ and the last node in the representative path of $B_{j}$ in $O^{\prime}$
will have a different label. They will share the same $\alpha$ since they
apply the same operations; hence keep the same fact of this block (or remove
all its facts). However, the value of $p$ will be different as it is
determined by the sequence $s_{\leq j}$ (which is the same as
$s^{\prime}_{\leq j}$, the sequence $s_{j}$ (which is the same as
$s^{\prime}_{j}$), and the order $\prec_{s_{\leq j-1},s_{j}}$ over all the
ways to interleave these sequences. Since $s_{\leq j}\neq s^{\prime}_{\leq
j}$, these sequences are interleaved in different ways, and the values will be
different.

#### Valid Outputs to Sequences.

Next, let $O=(V^{\prime},E^{\prime},\lambda^{\prime})$ be a valid output of
$M^{k}_{S}$ on $D,\Sigma,Q,H,\bar{c}$. In each computation, we traverse the
nodes of $T^{H}$ in the order defined by $\prec_{T^{H}}$, for each node $v$ we
go over the relation names $R_{i}$ such that $v$ is the
$\prec_{T^{H}}$-minimal covering vertex of the atom $R_{i}(\bar{y}_{i})$ of
$Q$ in some fixed order (there is at least one such relation name for every
$v$ since $(D,Q,H)$ is in normal form), and for each relation name $R_{i}$ we
go over the blocks of $\mathsf{block}_{R_{i},D}(\Sigma)$ in some fixed order.
For every block, we produce a set of labels that must all occur along a single
path of the output of the computation, as all the guesses we make along the
way are existential. Since $O$ is the output of some computation of
$M^{k}_{S}$ on $D,\Sigma,Q,H,\bar{c}$, it must be of the structure described
in the proof of the previous direction. That is, for every node $v$ of
$T^{H}$, we have a path of nodes in $O$ representing the blocks handled under
$v$, and under the last node representing the last block of $v$, we have two
children, each representing the first block handled by a child of $v$ in
$T^{H}$. Note that since $H$ is complete, every relation name $R_{i}$ is such
that the atom $R_{i}(\bar{y}_{i})$ of $Q$ has a $\prec_{T^{H}}$-minimal
covering vertex, and so every block of $D$ has a representative path in $O$.

It is now not hard to convert an output
$O=(V^{\prime},E^{\prime},\lambda^{\prime})$ of an accepting computation into
a complete repairing sequence $s$ with $\bar{c}\in Q(s(D))$. In particular,
for every node $v$ of $T^{H}$, every relation name $R_{i}$ such that $v$ is
the $\prec_{T^{H}}$-minimal covering vertex of the atom $R_{i}(\bar{y}_{i})$
of $Q$, and every block $B\in\mathsf{block}_{R_{i},D}(\Sigma)$, we consider
the path $v^{\prime}_{1}\rightarrow\dots\rightarrow v^{\prime}_{m}$ of
vertices in $V^{\prime}$ representing this block. Clearly, the first $m-1$
vertices are such that $\lambda^{\prime}(v_{i}^{\prime})$ is of the form
$(-g,p)$ (these labels are produced in the while loop of line 12), and the
last vertex is such that $\lambda^{\prime}(v_{m}^{\prime})$ is of the form
$(\alpha,p)$ (this label is produced in line 19). Hence, the sequence $s$ will
have $m-1$ operations over the block $B$, such that the $r$-th operation is a
removal of a single fact if $\lambda^{\prime}(v_{r}^{\prime})=(-1,p)$ for some
$p$, or it is the removal of a pair of facts if
$\lambda^{\prime}(v_{r}^{\prime})=(-2,p)$ for some $p$. The specific operation
is determined by the value $p$ in the following way.

If after applying the first $r-1$ operations over $B$, and removing the fact
$\alpha$ of $\lambda^{\prime}(v_{m}^{\prime})$ (if $\alpha\neq\bot$) from the
result, we obtain the subset $B^{\prime}$, then the operation that we choose
is the $p$-th operation in $\prec_{P}$, where $P$ is the set of all operations
removing a single fact of $B^{\prime}$ if
$\lambda^{\prime}(v_{r}^{\prime})=(-1,p)$ or it is the set of all operations
removing a pair of facts of $B^{\prime}$ if
$\lambda^{\prime}(v_{r}^{\prime})=(-2,p)$. Note that such an operation exists
since when we start handling the block $B$ in line 6, we define $n=|B|$ if
$\alpha=\bot$ or $n=|B|-1$ otherwise, and we decrease the value of $n$ by one
when we guess $-1$ in line 14 and by $2$ when we guess $-2$. Thus, in the
$r$-th iteration of the while loop of line 12 over this block, $n$ is
precisely the size of the subset $B^{\prime}$ of $B$ as described above. Then,
the $-g$ that we guess in this operation depends on the size of $B^{\prime}$
and the chosen $\alpha$. If $n>1$, then the removal of any single fact of
$B^{\prime}$ and the removal of any pair of facts of $B^{\prime}$ are all
$D$-justified operations, as all the facts of $B^{\prime}$ are in conflict
with each other; in this case, $-g\in\\{-1,-2\\}$. If $n=1$, the only
$D$-justified operation is the removal of the only fact of $B^{\prime}$ in the
case where $\alpha\neq\bot$, as these two facts are in conflict with each
other; in this case, $-g=-1$. If $n=1$ and $\alpha=\bot$ or $n=0$, there are
no $D$-justified operations over $B^{\prime}$. Hence, we only choose $-1$
(respectively, $-2$) if there is at least one $D$-justified operation that
removes a single fact (respectively, a pair of facts), as determined by
$\mathsf{shape}(n,\alpha)$. The value $p$ is from the range
$[\\#\mathsf{opsFor}(n,-g)]$, where $\\#\mathsf{opsFor}(n,-g)$ is precisely
the number of such operations available. If $-g=-1$, then the number of
available operations is $n$—one for each fact of $B^{\prime}$. If $-g=-2$,
then the number of available operations is $\frac{n(n-1)}{2}$—one for each
pair of facts of $B^{\prime}$. Note that the number of operations only depends
on $n$ and not on the specific block, as all the facts of a block are in
conflict with each other.

As for the last node $v_{m}^{\prime}$,
$\lambda^{\prime}(v_{m}^{\prime})=(\alpha,p)$ determines the final state of
the block $B$, as well as the positions of the operations over $B$ in the
sequence established up to that point (as we will explain later). Since we
always disregard the fact of $\alpha$ when choosing the next operation,
clearly none of the operations of $s$ over $B$ removes this fact. Hence, we
eventually have that $s(D)\cap B=\alpha$ if $\alpha\neq\bot$, or $s(D)\cap
B=\emptyset$ if $\alpha=\bot$ (in this case, we allow removing any fact of
$B^{\prime}$ in the sequence). Note that if $\alpha=\bot$, $|B^{\prime}|=2$,
and we choose an operation that removes a single fact, this computation will
be rejecting, as in the next iteration of the while loop we will have that
$n=1$ and $\alpha=\bot$, and, in this case,
$\mathsf{shape}(n,\alpha)=\emptyset$. Hence, if $\alpha=\bot$, the last
operation of $s$ over $D$ will always be the removal of a pair of facts when
precisely two facts of the block are left, and we will have that $s(D)\cap
B=\emptyset$.

We have explained how we choose, for every block of $D$, the sequence of
operations in $s$ over this block, and it is only left to show how to
interleave these operations in the sequence. We do so by following the order
$B_{1},\dots,B_{m}$ over the blocks. We start with the block $B_{1}$ and
denote by $s_{\leq 1}$ the sequence of operations of $s$ over $B_{1}$. This
sequence of operations has already been determined. Next, when we consider the
node $B_{i}$ for some $i>1$, we denote by $s_{i}$ the sequence of operations
over this block, and by $s_{\leq i-1}$ the sequence of operations over the
blocks $B_{1},\dots,B_{i-1}$. If $s_{\leq i}$ is of length $b$ and $s_{\leq
i-1}$ is of length $b^{\prime}$, we have $b$ positions in the sequence
$s_{\leq i}$, and all we have to do is to choose, among them, the $b^{\prime}$
positions for the sequence $s_{\leq i-1}$, and the rest of the positions will
be filled by the sequence $s_{i}$; the number of choices is ${b\choose
b^{\prime}}$. As argued in the proof of the previous direction, when we handle
the block $B_{i}$, in line 18 the value of $b$ is the number of operations in
$s_{\leq i}$ and the value of $b^{\prime}$ is the number of operations in
$s_{\leq i-1}$; hence, if the path of nodes representing the block $B_{i}$ is
$v_{1}^{\prime}\rightarrow\dots\rightarrow v_{m}^{\prime}$ and
$\lambda^{\prime}(v_{m}^{\prime})=(\alpha,p)$, $p$ is a number in $[{b\choose
b^{\prime}}]$, and it uniquely determines the sequence $s_{\leq i}$; this is
the $p$-th permutation in $\prec_{s_{\leq i-1},s_{i}}$. Finally, we define
$s=s_{\leq n}$.

It is left to show that $s$ is a complete repairing sequence, and that
$\bar{c}\in Q(s(D))$. Since for every block $B$ with a representative path
$v_{1}^{\prime}\rightarrow\dots\rightarrow v_{m}^{\prime}$ we have that
$\lambda^{\prime}(v_{m}^{\prime})=(\alpha,p)$, where $\alpha$ is either a
single fact of $B$ or $\bot$, $s(D)$ contains, for every block of $D$, either
a single fact or no facts. Since there are no conflicts among different
blocks, we conclude that $s$ is indeed a complete repairing sequence.
Moreover, since we consider a complete hypertree decomposition, every atom
$R_{i}(\bar{y}_{i})$ of $Q$ has a $\prec_{T^{H}}$-minimal covering vertex $v$.
By definition of covering vertex, we have that
$\bar{y}_{i}\subseteq\chi^{H}(v)$ and $R_{i}(y_{i})\in\lambda^{H}(v)$. In the
computation, for each vertex $v$ of $T^{H}$, we guess a set $A^{\prime}=$
$\\{\bar{y}_{i_{1}}\mapsto\bar{c}_{1},\ldots,\bar{y}_{i_{\ell}}\mapsto\bar{c}_{\ell}\\}$
assuming
$\lambda(v)=\\{R_{i_{1}}(\bar{y}_{i_{1}}),\ldots,R_{i_{\ell}}(\bar{y}_{i_{\ell}})\\}$,
such that $R_{i_{j}}(\bar{c}_{j})\in D$ for $j\in[\ell]$ and all the mappings
are coherent with $\bar{x}\mapsto\bar{c}$. In particular, when we consider the
$\prec_{T^{H}}$-minimal covering vertex of the atom $R_{i}(y_{i})$ of $Q$, we
choose some mapping $\bar{y}_{i}\mapsto\bar{c}_{i}$ such that
$R_{i}(\bar{c}_{i})\in D$. When we consider the block $B$ of
$R_{i}(\bar{c}_{i})$ in line 6, we choose $\alpha=R_{i}(\bar{c}_{i})$ in line
8, which ensures that eventually $s(D)\cap B=R_{i}(\bar{c})$; that is, we keep
this fact in the repair. Since $Q$ is self-join-free, the choice of which fact
to keep from the other blocks of $\mathsf{block}_{R_{i},D}(\Sigma)$ can be
arbitrary (we can also remove all the facts of these blocks). When we
transition from a node $v$ of $T^{H}$ to its children, we define
$A=A^{\prime}$, and then, for each child, we choose a set $A$ in line 3 that
is consistent with $A^{\prime}$ and with $\bar{x}\mapsto\bar{c}$.

This ensures that two atoms $R_{i}(\bar{y}_{i})$ and $R_{j}(\bar{y}_{j})$ of
$Q$ that share at least one variable are mapped to facts $R_{i}(\bar{c}_{i})$
and $R_{j}(\bar{c}_{j})$ of $D$ in a consistent way; that is, a variable that
occurs in both $\bar{y}_{i}$ and $\bar{y}_{j}$ is mapped to the same constant
in $\bar{c}_{i}$ and $\bar{c}_{j}$. Let $v$ and $u$ be the
$\prec_{T^{H}}$-minimal covering vertices of $R_{i}(\bar{y}_{i})$ and
$R_{j}(\bar{y}_{j})$, respectively. Let $z$ be a variable that occurs in both
$\bar{y}_{i}$ and $\bar{y}_{j}$. By definition of covering vertex, we have
that $\bar{y}_{i}\subseteq\chi^{H}(v)$ and $\bar{y}_{j}\subseteq\chi^{H}(u)$.
By definition of hypertree decomposition, the set of vertices $s\in T^{H}$ for
which $z\in\chi^{H}(s)$ induces a (connected) subtree of $T^{H}$. Therefore,
there exists a subtree of $T^{H}$ that contains both vertices $v$ and $u$, and
such that $z\in\chi^{H}(s)$ for every vertex $s$ of this substree. When we
process the root $r$ of this subtree, we map the variable $z$ in the set
$A^{\prime}$ to some constant (since there must exist an atom
$R_{k}(\bar{y}_{k})$ in $\lambda(r)$ such that $z$ occurs in $\bar{y}_{k}$ by
definition of a hypertree decomposition). Then, when we transition to the
children of $r$ in $T^{H}$, we ensure that the variable $z$ is mapped to the
same constant, by choosing a new set $A^{\prime}$ of mappings that is
consistent with the set of mappings chosen for $r$, and so fourth. Hence, the
variable $z$ will be consistently mapped to the same constant in this entire
subtree, and for every atom $R_{i}(\bar{y}_{i})$ of $Q$ that mentions the
variable $z$ it must be the case that the $\prec_{T^{H}}$-minimal covering
vertex $v$ of $R_{i}(\bar{y}_{i})$ occurs in this subtree because
$z\in\chi^{H}(v)$. Hence, the sets $A$ of mappings that we choose in an
accepting computations map the atoms of the query to facts of the database in
a consistent way, and this induces a homomorphism $h$ from $Q$ to $D$. And
since we choose mappings that are coherent with the mapping
$\bar{x}\mapsto\bar{c}$ of the answer variables of $Q$, we conclude that
$\bar{c}\in Q(s(D))$.

Finally, we show that two different valid outputs
$O=(V^{O},E^{O},\lambda^{O})$ and
$O^{\prime}=(V^{O^{\prime}},E^{O^{\prime}},\lambda^{O^{\prime}})$ give rise to
two different complete repairing sequences $s$ and $s^{\prime}$, respectively.
If the values of $N$ guessed in line 2 in the computations of $O$ and
$O^{\prime}$ are different, then clearly $s\neq s^{\prime}$, as the length of
the sequence is determined by $N$. This holds since we decrease this value by
one with every operation that we apply, and only accept if $N=0$ for every
leaf of $T^{H}$; that is, if all our guesses for the number of operations in
the computation are coherent with the sequence. Similarly, if the length of
the representative path of some block $B$ in $O$ is different from the length
of the representative path of $B$ in $O^{\prime}$, then $s\neq s^{\prime}$, as
they differ on the number of operations over $B$. If both sequences have the
same length and the same number of operations for each block, then there are
three possible cases. The first is when there exists a block $B$ such that the
representative path $v_{1}\rightarrow\dots\rightarrow v_{m}$ of $B$ in $O$ and
the representative path $u_{1}\rightarrow\dots\rightarrow u_{m}$ of $B$ in
$O^{\prime}$ are such that for some $i\in[m-1]$, if
$\lambda^{O}(v_{i})=(-g,p)$ and
$\lambda^{O^{\prime}}(u_{i})=(-g^{\prime},p^{\prime})$ then
$-g\neq-g^{\prime}$, or $\lambda^{O}(v_{m})=(\alpha,p)$ and
$\lambda^{O^{\prime}}(u_{m})=(\alpha^{\prime},p^{\prime})$ with
$\alpha\neq\alpha^{\prime}$. In this case, the operations of $s$ over $B$ and
the operations of $s^{\prime}$ over $B$ conform to different templates or keep
a different fact of $B$ in the repair; hence, we again conclude that $s\neq
s^{\prime}$.

The second case is when for every block $B$, if
$v_{1}\rightarrow\dots\rightarrow v_{m}$ is the path in $O$ representing the
block $B$ and $u_{1}\rightarrow\dots\rightarrow u_{m}$ is the path in
$O^{\prime}$ representing the block $B$, then for every $i\in[m-1]$, if
$\lambda^{O}(v_{i})=(-g,p)$ and
$\lambda^{O^{\prime}}(u_{i})=(-g^{\prime},p^{\prime})$, then $-g=-g^{\prime}$,
but for some $i\in[m-1]$, $p\neq p^{\prime}$. Assume that this holds for the
$r$-th node in the path, and this is the first node they differ on; that is,
$\lambda^{O}(v_{i})=\lambda^{O^{\prime}}(u_{i})$ for all $i\in[r-1]$, but
$\lambda^{O}(v_{r})\neq\lambda^{O^{\prime}}(u_{r})$. In this case, the $r$-th
operation of $s$ over $B$ and the $r$-th operation of $s^{\prime}$ over $B$
will be different. This is the case since when determining the $r$-th
operation of the sequence over $B$, we consider the same subset $B^{\prime}$
of $B$ in both cases (as the first $r-1$ operations over $B$ are the same for
both sequences) and the same $\alpha$, and so the same set $P$ of operations.
The $r$-th operation in $s$ (respectively, $s^{\prime}$) over $B$ is the
$p$-th (respectively, $p^{\prime}$-th) operation in the order $\prec_{P}$ over
such operations, and since $p\neq p^{\prime}$, these are different operations.

The last case is when for some block $B$, with
$v_{1}\rightarrow\dots\rightarrow v_{m}$ being its representative path in $O$
and $u_{1}\rightarrow\dots\rightarrow u_{m}$ being its representative path in
$O^{\prime}$, we have that $\lambda^{\prime O}(u_{i})=\lambda^{O}(v_{i})$ for
all $i\in[m-1]$, $\lambda^{O}(v_{m})=(\alpha,p)$,
$\lambda^{O^{\prime}}(v_{m})=(\alpha^{\prime},p^{\prime})$,
$\alpha=\alpha^{\prime}$, and $p\neq p^{\prime}$. In this case, we consider
the first block $B$ in the order $B_{1},\dots,B_{m}$ for which this is the
case. For each $i\in[m]$, let $s_{\leq i-1}$ be the sequence of operations in
$s$ over the blocks $B_{1},\dots,B_{i-1}$, and let $s^{\prime}_{\leq i-1}$ be
the sequence of operations in $s^{\prime}$ over these blocks. Clearly,
$s_{\leq i-1}=s^{\prime}_{\leq i-1}$, as for all the previous blocks, $O$ and
$O^{\prime}$ agree on all the labels along the representative path of the
block. However, the sequences $s_{\leq i}$ and $s^{\prime}_{\leq i}$ will be
different, and since they are subsequences of $s$ and $s^{\prime}$,
respectively, we will conclude that $s\neq s^{\prime}$. This is the case since
the way we choose to interleave the sequences $s_{\leq i-1}$ (resp.,
$s^{\prime}_{\leq i-1}$) and $s_{i}$ (resp., $s^{\prime}_{i}$) depends on the
values $p$ and $p^{\prime}$; that is, we choose the $p$-th (resp.,
$p^{\prime}$-th) permutation in the order $\prec_{s_{\leq i-1},s_{i}}$ (note
that $s_{i}=s^{\prime}_{i}$). Since $p\neq p^{\prime}$, these will be two
different permutation, and $s_{i}\neq s^{\prime}_{i}$. This concludes our
proof.

## References

  * (1)
  * Got (2002) 2002\.  Hypertree Decompositions and Tractable Queries.  _J. Comput. System Sci._ 64, 3 (2002), 579–627.
  * Adler et al. (2007) Isolde Adler, Georg Gottlob, and Martin Grohe. 2007\.  Hypertree width and related hypergraph invariants.  _Eur. J. Comb._ 28, 8 (2007), 2167–2181.
  * Àlvarez and Jenner (1993) Carme Àlvarez and Birgit Jenner. 1993.  A Very Hard log-Space Counting Class.  _Theor. Comput. Sci._ 107, 1 (1993), 3–30.
  * Arenas et al. (1999) Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. 1999.  Consistent Query Answers in Inconsistent Databases. In _PODS_. 68–79.
  * Arenas et al. (2021a) Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. 2021a.  #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes.  _J. ACM_ 68, 6 (2021), 48:1–48:40.
  * Arenas et al. (2021b) Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. 2021b.  When is approximate counting for conjunctive queries tractable?. In _STOC_. 1015–1027.
  * Aror and Barak (2009) Sanjeev Aror and Boaz Barak. 2009.  _Computational Complexity: A Modern Approach_.  Cambridge University Press.
  * Arora and Barak (2009) Sanjeev Arora and Boaz Barak. 2009.  _Computational Complexity - A Modern Approach_.  Cambridge University Press.
  * Calautti et al. (2019) Marco Calautti, Marco Console, and Andreas Pieris. 2019\.  Counting Database Repairs under Primary Keys Revisited. In _PODS_. 104–118.
  * Calautti et al. (2021) Marco Calautti, Marco Console, and Andreas Pieris. 2021\.  Benchmarking Approximate Consistent Query Answering. In _PODS_. 233–246.
  * Calautti et al. (2018) Marco Calautti, Leonid Libkin, and Andreas Pieris. 2018\.  An Operational Approach to Consistent Query Answering. In _PODS_. 239–251.
  * Calautti et al. (2022a) Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider. 2022a.  Counting Database Repairs Entailing a Query: The Case of Functional Dependencies. In _PODS_.  To appear.
  * Calautti et al. (2022b) Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider. 2022b.  Uniform Operational Consistent Query Answering. In _PODS_. 393–402.
  * Chiu et al. (2001) Andrew Chiu, George Davida, and Bruce Litow. 2001\.  Division in logspace-uniform NC1.  _RAIRO - Theoretical Informatics and Applications_ 35, 3 (2001), 259–275.
  * Downey and Hirschfeldt (2001) Rod Downey and Denis R. Hirschfeldt (Eds.). 2001.  _Aspects of Complexity_.  De Gruyter, Berlin, New York.
  * Dyer and Greenhill (2000) Martin E. Dyer and Catherine S. Greenhill. 2000.  The complexity of counting graph homomorphisms.  _Random Struct. Algorithms_ 17, 3-4 (2000), 260–289.
  * Fuxman et al. (2005) Ariel Fuxman, Elham Fazli, and Renée J. Miller. 2005\.  ConQuer: Efficient Management of Inconsistent Databases. In _SIGMOD_. 155–166.
  * Fuxman and Miller (2007) Ariel Fuxman and Renée J. Miller. 2007.  First-order query rewriting for inconsistent databases.  _J. Comput. Syst. Sci._ 73, 4 (2007), 610–635.
  * Geerts et al. (2015) Floris Geerts, Fabian Pijcke, and Jef Wijsen. 2015\.  First-Order Under-Approximations of Consistent Query Answers. In _SUM_. 354–367.
  * Gottlob et al. (2002) Georg Gottlob, Nicola Leone, and Francesco Scarcello. 2002\.  Hypertree Decompositions and Tractable Queries.  _J. Comput. Syst. Sci._ 64, 3 (2002), 579–627.
  * Jerrum (2003) Mark Jerrum. 2003\.  _Counting, sampling and integrating: algorithms and complexity_.  Springer Science & Business Media.
  * Jerrum et al. (1986) Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. 1986\.  Random Generation of Combinatorial Structures from a Uniform Distribution.  _Theor. Comput. Sci._ 43 (1986), 169–188.
  * Koutris and Suciu (2014) Paraschos Koutris and Dan Suciu. 2014.  A Dichotomy on the Complexity of Consistent Query Answering for Atoms with Simple Keys. In _ICDT_. 165–176.
  * Koutris and Wijsen (2015) Paraschos Koutris and Jef Wijsen. 2015.  The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints. In _PODS_. 17–29.
  * Koutris and Wijsen (2021) Paraschos Koutris and Jef Wijsen. 2021.  Consistent Query Answering for Primary Keys in Datalog.  _Theory Comput. Syst._ 65, 1 (2021), 122–178.
  * Maslowski and Wijsen (2013) Dany Maslowski and Jef Wijsen. 2013.  A dichotomy in the complexity of counting database repairs.  _J. Comput. Syst. Sci._ 79, 6 (2013), 958–983.
  * van Bremen and Meel (2023) Timothy van Bremen and Kuldeep S. Meel. 2023.  Probabilistic Query Evaluation: The Combined FPRAS Landscape. In _PODS_. 339–347.