$i$-relations in $D$ independent of each other for different $i$. It should be
clear that $D$ can be constructed in time linear in $|E|$.

We remark that $D$ has two important properties. First, every
$c\in\mathsf{adom}(D)$ has both an incoming $R$-edge and an outgoing $R$-edge
for every binary relation $R\in\mathbf{S}$. And second, every triangle in $D$
that only uses the relations $R_{1},R_{2},R_{3}$ is in $D|_{V}$; more
precisely: if $D^{\prime}\subseteq D$ is an $\\{R_{1},R_{2},R_{3}\\}$-database
such that $|\mathsf{adom}(D^{\prime})|=3$ and the Gaifman graph of
$D^{\prime}$ is a triangle, then $\mathsf{adom}(D^{\prime})\subseteq V$. We
refer to this as the _completeness property_ and the _triangle property_ ,
respectively. To complete the reduction, it suffices to show the following.

###### Lemma C.5.

$G$ contains a triangle iff $D\models Q$.

###### Proof.

“if”. Assume that $D\models Q$. Then there is a homomorphism $h$ from $q$ to
$\mathsf{ch}_{\mathcal{O}}(D)$. Due to the interpretation of the $i$-relations
in $D$ with $3<i\leq n$, we must have $h(x_{4})=\cdots=h(x_{n})=h(x_{1})$.
Consequently, the Gaifman graph of $\mathsf{ch}_{\mathcal{O}}(D)$ must contain
the edge $\\{h(x_{i}),h(x_{j})\\}$ for $1\leq i,j\leq 3$. By construction and
since $G$ has no self loops, $D$ contains no reflexive $R_{i}$-edges for
$1\leq i\leq 3$. Since $\mathcal{O}\in\mathbb{ELI}$, the same is then true for
$\mathsf{ch}_{\mathcal{O}}(D)$. It follows that $h(x_{1}),h(x_{2}),h(x_{3})$
are all distinct and thus the restriction of $\mathsf{ch}_{\mathcal{O}}(D)$ to
$h(x_{1}),h(x_{2}),h(x_{3})$ is a triangle. Due to the triangle property and
since the chase with an ${\mathcal{}ELI}$-ontology only adds to $D$ trees
without self loops and multi-edges, this implies that $h(x_{i})\in V$ for
$1\leq i\leq 3$. Since the chase adds no binary facts $R(c_{1},c_{2})$ with
$c_{1},c_{2}\in\mathsf{adom}(D)$, the restriction of $D$ to
$h(x_{1}),h(x_{2}),h(x_{3})$ is also a triangle. It now follows from the
interpretation of the $i$-relations in $D$ with $1\leq i\leq 3$,
$h(x_{1}),h(x_{2}),h(x_{3})$ is a triangle in $G$.

“only if”. Assume that $G$ contains a triangle that consists of the vertices
$v_{1},v_{2},v_{3}$. Let $q^{-}$ be $q$ with all unary atoms dropped. We first
construct a homomorphism $h$ from $q^{-}$ to $\mathsf{ch}_{\mathcal{O}}(D)$
and then argue that it can be extended to a homomorphism from $q$ to
$\mathsf{ch}_{\mathcal{O}}(D)$.

We construct $h$ by first mapping only some variables from $q$ and then
extending in several rounds. After each round, the constructed $h$ will be a
homomorphism from $q^{-}|_{h}$ to $\mathsf{ch}_{\mathcal{O}}(D)$ where
$q^{-}|_{h}$ is the restriction of $q^{-}$ to the domain of $h$.

Start with setting $h(x_{1})=v_{1}$, $h(x_{2})=v_{2}$, and
$h(x_{3})=\cdots=h(x_{n})=v_{3}$ and $h(c)=c$ for all $c\in\mathsf{con}(q)$.
It can be verified that $h$ is a homomorphism from $q^{-}|_{h}$ to $D$, thus
also to $\mathsf{ch}_{\mathcal{O}}(D)$. To see this, it helps to observe that
$q$ contains no atoms $R(x_{i},x_{j})$ with
$x_{j}\notin\\{x_{i-1},x_{i},x_{i+1}\\}$ and that all binary atoms in
$q^{-}|_{h}$ use a relation from $\mathbf{S}$. In fact, the former is a
consequence of $x_{1},\dots,x_{n}$ being a chordless cycle in
$G^{\mathsf{var}}_{q}$. For the latter, recall that $h_{0}$ is a homomorphism
from $q$ to $\mathsf{ch}_{\mathcal{O}}(D_{0})$ that maps all variables
$x_{1},\dots,x_{n}$ to $\mathsf{adom}(D_{0})$, established in the proof of
Claim 1. But all binary facts in the restriction of
$\mathsf{ch}_{\mathcal{O}}(D_{0})$ to $\mathsf{adom}(D_{0})$ use relations
from $\mathbf{S}$.

To extend $h$, set $h(x)=c_{0}$ for all $x\in\mathsf{var}(q)$ with $h(x)$ not
yet defined and $h_{0}(x)\in\mathsf{adom}(D_{0})$ (any other constant would
also work). It can be verified that $h$ is still a homomorphism from
$q^{-}|_{h}$ to $D$. In particular, we can argue as above that all binary
atoms in $q^{-}|_{h}$ use a relation from $\mathbf{S}$.

For the next extension of $h$, let $q^{\prime}$ be obtained from $q$ by first
dropping all atoms $R(\bar{x})$ such that $h_{0}(x)\in\mathsf{adom}(D_{0})$
for all $x\in\bar{x}$ and then identifying any variables $x_{1},x_{2}$ such
that $h_{0}(x_{1})=h_{0}(x_{2})$. Consider all maximal connected components
$p$ of $q^{\prime}$. We distinguish two cases.

First assume that $p$ contains a variable $x$ with $h(x)$ already defined. It
then only contains a single such variable, that is,
$h_{0}(x)\in\mathsf{adom}(D_{0})$ and all $y\neq x$ in $p$ are mapped to the
tree that the chase has generated below $h_{0}(x)$. Since the restriction of
$\mathsf{ch}_{\mathcal{O}}(D_{0})$ to the nulls is a disjoint union of trees
without reflexive loops and multi-edges, it follows that $p(x)$ is an ELIQ.
Moreover, $D_{0}\models(\mathcal{O},\mathbf{S},p(x))(h_{0}(x))$. The
completeness property of $D$ implies that $(D_{0},h_{0}(x))\preceq(D,h(x))$,
no matter what $h(x)$ is. It thus follows from Lemma A.3 that
$D\models(\mathcal{O},\mathbf{S},p(x))(h(x))$, and consequently there is a
homomorphism $g$ from $p(x)$ to $\mathsf{ch}_{\mathcal{O}}(D)$ with
$g(x)=h(x)$. We can extend $h$ to $p$ by setting $h:=h\cup g$.

Now assume that $p$ contains no variable $x$ with $h(x)$ already defined.
Since $p$ is connected, there is a $c\in\mathsf{adom}(D_{0})$ such that
$h_{0}(x)$ is in the tree that the chase has generated below $c$ for all
$x\in\mathsf{var}(p)$. Let $\widehat{p}(x)$ be the minimal prefix of that tree
that contains $h_{0}(x)$ for all $x\in\mathsf{var}(p)$, viewed as an ELIQ with
$c$ being the answer variable. There is a homomorphism $g$ from $p(x)$ to
$\widehat{p}(x))$ with $g(x)=x$. We have
$D_{0}\models(\mathcal{O},\mathbf{S},\widehat{p}(x))(c)$. Take any constant
$c^{\prime}\in\mathsf{adom}(D)$. The completeness property of $D$ implies that
$(D_{0},c)\preceq(D,c^{\prime})$. It thus follows from Lemma A.3 that
$D\models(\mathcal{O},\mathbf{S},\widehat{p}(x))(c^{\prime})$, and
consequently there is a homomorphism $g^{\prime}$ from $\widehat{p}(x)$ to
$\mathsf{ch}_{\mathcal{O}}(D)$ with $g^{\prime}(x)=c^{\prime}$. We can extend
$h$ to $p$ by setting $h:=h\cup(g\circ g^{\prime})$.

At this point, $h$ is defined for all terms in $\mathsf{var}(q)$ and thus it
is a homomorphism from $q^{-}$ to $\mathsf{ch}_{\mathcal{O}}(D)$. Further
extend $h$ by setting $h(x)$ to any constant in $\mathsf{adom}(D)$ if $x$ does
not occur in any binary atoms. It remains to argue that $h$ satisfies all
unary atoms $A(x)$ in $a$. If $A\in\mathbf{S}$, then this is clear by the
interepretation of such symbols in $D$. Otherwise, we observe that
$A(h_{0}(x))\in\mathsf{ch}_{\mathcal{O}}(D_{0})$. We can argue as above, using
the ELIQ $A(x)$ and Lemma A.3, that $A(h(x))\in\mathsf{ch}_{\mathcal{O}}(D))$.
∎

The next example illustrates another reason for why we cannot easily replace
$\mathbb{ELI}$ with $\mathbb{G}$ in Theorem 3.4, unrelated to self-join
freeness.

###### Example C.6.

Let $Q(x)=(\mathcal{O},\mathbf{S},q)\in(\mathbb{G},\mathbb{CQ})$ where

$\begin{array}[]{rcl}\mathcal{O}&=&\\{A(x)\rightarrow\exists y\exists
z\,R(x,y)\wedge S(y,z)\wedge T(z,x)\\}\\\ \mathbf{S}&=&\\{A\\}\\\
q(x)&=&R(x,y)\wedge S(y,z)\wedge T(z,x).\end{array}$

Then $Q$ is not acyclic and self-join free, yet single-testing $Q$ is in
linear time as $Q\equiv(\emptyset,\mathbf{S},A(x))$.

For CQs without ontologies, we are not aware of any examples which show that
Theorem 3.4 fails when ‘self-join free’ is replaced with ‘a homomorphism
core’.333A CQ is a _homomorphism core_ if every homomorphism from $D_{q}$ to
$D_{q}$ is surjective. For every CQ, there is an equivalent CQ that is a
homomorphism core. For $(\mathbb{ELI},\mathbb{CQ})$, however, such examples
are not hard to find.

###### Example C.7.

Let $Q=(\mathcal{O},\mathbf{S},q)\in(\mathbb{ELI},\mathbb{CQ})$ where

$\begin{array}[]{rcl}\mathcal{O}&=&\\{A(x)\rightarrow\exists y\exists
z\,R(x,y)\wedge B_{1}(y)\wedge B_{2}(y)\wedge R(y,z)\\}\\\
\mathbf{S}&=&\\{A\\}\\\ q(x)&=&R(x,y_{1})\wedge R(x,y_{2})\wedge
B_{1}(y_{1})\wedge B_{2}(y_{2})\,\wedge\\\ &&R(y_{1},z)\wedge
R(y_{2},z).\end{array}$

Then $Q$ is not acyclic and $q$ is a homomorphism core, yet single-testing $Q$
is in linear time as $Q\equiv(\emptyset,\mathbf{S},A(x))$.

###  C.3. Proof of Theorem 3.6

See 3.6

###### Proof.

First for weakly acyclic OMQs and minimal partial answers with a single
wildcard. We start with showing the result for $(\mathbb{G},\mathbb{CQ})$ in
place of $(\mathbb{ELI},\mathbb{CQ})$. Let $R$ be a binary relation symbol and
$\mathbf{S}=\\{R\\}$. We may view an undirected graph $G=(V,E)$ as the
$\mathbf{S}$-database

$D_{G}=\\{R(v,v^{\prime}),R(v^{\prime},v)\mid\\{v,v^{\prime}\\}\in E\\}.$

Consider the OMQ $Q(x)=(\mathcal{O},\mathbf{S},q)\in(\mathbb{G},\mathbb{CQ})$
where $\mathcal{O}$ contains the TGD

$\begin{array}[]{r@{\;}c@{\;}l}R(x_{1},x_{2})&\rightarrow&\exists y_{1}\exists
y_{2}\exists y_{3}\,R\\{y_{1},y_{2}\\}\wedge R\\{y_{2},y_{3}\\}\wedge
R\\{y_{3},y_{1}\\}\end{array}$

with $R\\{x,y\\}$ an abbreviation for $R(x,y)\wedge R(y,x)$ and with

$q(x,y,z)=R\\{x,y\\}\wedge R\\{y,z\\}\wedge R\\{z,x\\}.$

Note that $q$ is weakly acyclic. Let $G=(V,E)$ be an undirected graph. Then
$(\ast,\ast,\ast)$ is a partial answer to $Q$ on $D_{G}$, but not necessarily
a minimal partial answer. In fact, it is a minimal partial answer if and only
if $G$ contains no triangle. It clearly follows that single-testing minimal
partial answers for $Q$ is not in $\mathsf{DelayC}_{\mathsf{lin}}$ unless the
triangle hypothesis fails.

The challenge in improving the construction to $\mathbb{ELI}$ is that
${\mathcal{}ELI}$ TGDs cannot introduce a triangle that consists of nulls. The
solution is to construct $q$, $\mathcal{O}$, and $D$ in a more careful way.
Let us start with $q$, which is now

$\begin{array}[]{r@{\;}c@{\;}l}q(x_{1},x_{2},x_{3},x_{4})&=&R(x_{1},x_{2})\wedge
R(x_{2},x_{3})\wedge R(x_{4},x_{3})\wedge R(x_{1},x_{4})\\\\[2.84526pt]
&&\wedge\,A(x_{1})\wedge B(x_{2})\wedge B(x_{3})\wedge A(x_{4})\end{array}$

where $A$, $B$, $C$ are additional unary relation symbols and the direction of
the edges is chosen carefully. We choose $\mathcal{O}$ to contain the
${\mathcal{}ELI}$ TGD

$\begin{array}[]{r@{\;}c@{\;}l}R(x_{1},x_{2})&\rightarrow&\exists y_{1}\exists
y_{2}\exists y_{3}\,R(x_{1},y_{2})\wedge R(y_{2},y_{3})\\\\[2.84526pt]
&&\qquad\qquad\ \ \ \wedge\,A(y_{1})\wedge A(y_{2})\wedge B(y_{2})\wedge
B(y_{3}).\end{array}$

Similarly to before, $(\ast,\ast,\ast,\ast)$ is a partial answer to $Q$ on any
non-empty $\mathbf{S}$-database, such as the databases $D_{G}$. It remains to
modify $D_{G}$ so that $q(D_{G})$ is non-empty if and only if $G=(V,E)$
contains a triangle, as $q(D_{G})$ is empty if and only if
$(\ast,\ast,\ast,\ast)$ is a _minimal_ partial answer. This is achieved by
constructing $D_{G}$ so that $\mathsf{adom}(D_{G})=V\times[2]$ and $D_{G}$
contains the following facts:

  * •

$R((v,1),(v^{\prime},2)),R((v,2),(v^{\prime},2))$ for all
$\\{v,v^{\prime}\\}\in E$;

  * •

$R((v,1),(v,1)),A(v,1),B(v,2)$ for all $v\in V$.

It thus remains to argue that $q(D_{G})$ is non-empty if and only if $G=(V,E)$
contains a triangle. For the “if” direction, it suffices to observe that any
triangle $v_{1},v_{2},v_{3}$ in $G$ gives rise to the answer
$((v_{1},1),(v_{2},2),(v_{3},2),(v_{1},1))$ in $q(G)$. For the “only if”
direction, let $(c_{1},c_{2},c_{3},c_{4})\in q(G)$. Due to the atoms
$A(x_{1}),R(x_{1},x_{4}),A(x_{4})$ in $q$, we must have
$c_{1}=c_{4}=(v_{1},1)$ for some $v_{1}\in V$. Due to the atoms
$A(x_{1}),R(x_{1},x_{2}),B(x_{2})$ and $A(x_{4}),R(x_{4},x_{3}),B(x_{3})$,
respectively, we must have $c_{2}=(v_{2},2)$ and $c_{3}=(v_{3},2)$ for some
$v_{2},v_{3}\in V$ such that $v_{1}\neq v_{2}$, $v_{1}\neq v_{3}$, and
$\\{v_{1},v_{2}\\},\\{v_{2},v_{3}\\}\in G$. Finally, the atoms
$B(x_{2}),R(x_{2},x_{3}),B(x_{3})$ ensure that $v_{2}\neq v_{3}$ and
$\\{v_{1},v_{2}\\}\in G$. Thus, $v_{1},v_{2},v_{3}$ form a triangle in $G$.

We now turn towards acyclic OMQs and minimal partial answers with multi-
wildcards. The general idea is similar to what was done above. In particular,
with every undirected graph $G=(V,E)$ we associate an $\mathbf{S}$-database
$D_{G}=\\{R(v,v^{\prime}),R(v^{\prime},v)\mid\\{v,v^{\prime}\\}\in E\\}.$
Consider the OMQ $Q(x)=(\mathcal{O},\mathbf{S},q)\in(\mathbb{G},\mathbb{CQ})$
where $\mathcal{O}$ contains the TGD

$\begin{array}[]{r@{\;}c@{\;}l}R(x_{1},x_{2})&\rightarrow&\exists y_{1}\exists
y_{2}\exists y_{3}\,R\\{y_{1},y_{2}\\}\wedge R\\{y_{2},y_{3}\\}\wedge
R\\{y_{3},y_{1}\\}\end{array}$

with $R\\{x,y\\}$ an abbreviation for $R(x,y)\wedge R(y,x)$ and with

$q(x_{1},x^{\prime}_{1},x_{2},x^{\prime}_{2},x_{3},x^{\prime}_{3})=R(x_{1},x^{\prime}_{1})\wedge
R(x_{2},x^{\prime}_{2})\wedge R(x_{3},x^{\prime}_{3}).$

Note that $q$ is acyclic and in fact of a very restricted shape. Let $G=(V,E)$
be an undirected graph. Then
$(\ast_{1},\ast_{2},\ast_{2},\ast_{3},\ast_{3},\ast_{1})$ is a partial answer
with multi-wildcards to $Q$ on $D_{G}$. Moreover, it is a minimal partial
answer if and only if $D_{G}$ contains no triangle. It clearly follows that
single-testing minimal partial answers with multi-wildcards for $Q$ is not in
$\mathsf{DelayC}_{\mathsf{lin}}$ unless the triangle hypothesis fails. ∎

##  Appendix D Proofs for Section 4

See 4.2

###### Proof.

Let $q(\bar{x})$ be a CQ that is free-connex acyclic, over some schema
$\mathbf{S}$. Since $q$ is free-connex acyclic, its extension $q^{+}(\bar{x})$
with atom $R_{0}(\bar{x})$ is acyclic, where $R_{0}$ is a fresh relation
symbol of arity $|\bar{x}|$. Thus $q^{+}$ has a join tree $T=(V,E)$. When
removing from $T$ the node $R_{0}(\bar{x})$, we obtain a forest that consists
of trees $(V_{1},E_{1}),\dots,(V_{k},E_{k})$. Let
$q_{1}(\bar{x}_{1}),\dots,q_{k}(\bar{x}_{k})$ be the corresponding CQs, that
is, $q_{i}$ contains exactly the atoms in $V_{i}$. It is clear that every
$q_{i}$ is acyclic since $(V_{i},E_{i})$ is a join tree for $q_{i}$. It is
also free-connex acyclic. In fact, let $q_{i}^{+}(\bar{x}_{i})$ be $q_{i}$
extended with atom $R_{i}(\bar{x}_{i})$. We obtain a join tree for $q_{i}^{+}$
by starting with $(V_{i},E_{i})$, adding node $R_{i}(\bar{x}_{i})$, and an
edge between $R_{i}(\bar{x}_{i})$ and the node in $V_{i}$ that is adjacent in
$T$ to $R_{0}(\bar{x})$ (there must be a unique such node).

It is known that all-testing is in $\mathsf{CD}$$\circ$$\mathsf{Lin}$ for all
CQs that are acyclic and free-connex acyclic (berkholz-enum-tutorial, ). There
are thus $\mathsf{CD}$$\circ$$\mathsf{Lin}$ all-testing algorithms
$A_{1},\dots,A_{k}$ for $q_{1},\dots,q_{k}$. We devise a
$\mathsf{CD}$$\circ$$\mathsf{Lin}$ all-testing algorithm for $q$ by combining
these. Let the $\mathbf{S}$-database $D$ be given as input. In the
preprocessing phase, we run the preprocessing phases of algorithms
$A_{1},\dots,A_{k}$ on $D$. In the testing phase, we are given a tuple
$\bar{c}\in\mathsf{adom}(D)^{|\bar{x}|}$. Let $\bar{x}=x_{1}\cdots x_{n}$ and
$\bar{c}=c_{1}\cdots c_{n}$. We first check whether $x_{i}=x_{j}$ implies
$c_{i}=c_{j}$ and reject if this is not the case. We then use algorithms
$A_{1},\dots,A_{k}$ to test in constant time whether for $1\leq i\leq k$, it
holds that $\bar{c}_{i}\in q_{i}(D)$ where $\bar{c}_{i}$ is the ‘projection’
of tuple $\bar{c}$ to the answer variables in $q_{i}$, that is, if
$x_{i_{1}},\dots,x_{i_{\ell}}$ are the answer variables in $q_{i}$, then
$c_{i}=c_{i_{1}},\dots,c_{i_{\ell}}$. We answer ‘yes’ if all checks succeed
and ‘no’ otherwise. Since $q_{1},\dots,q_{k}$ is a partitioning of (the atoms
of) $q$ and distinct $q_{i}$ do not share any quantified variables, the answer
is clearly correct. ∎

See 4.1

###### Proof.

Point (1) of Theorem 4.1 is easy to prove using the query-directed chase
established in Section C.1 and the existing result stating that enumeration is
in $\mathsf{CD}$$\circ$$\mathsf{Lin}$ for CQs that are acyclic and
free/̄connex acyclic when no ontologies are present (bagan-enum-cdlin, ). In
fact, assume that an OMQ
$Q(\bar{x})=(\mathcal{O},\mathbf{S},q)\in(\mathbb{G},\mathbb{CQ})$ that is
acyclic and free/̄connex acyclic is given, as well as an $\mathbf{S}$-database
$D$. As a part of the preprocessing phase, we compute in linear time the
query-directed chase $\mathsf{ch}^{q}(\mathcal{O})$. As in the proof of
Theorem 3.1, we introduce a fresh unary relation symbol $P_{\mathsf{db}}$,
extend $\mathsf{ch}^{q}_{\mathcal{O}}(D)$ to a database $D^{\prime}$ by adding
the fact $P_{\mathsf{db}}(c)$ for every $c\in\mathsf{adom}(D)$, and obtain the
CQ $q^{\prime}(\bar{x})$ from $q$ by adding the atom $P_{\mathsf{db}}(x)$ for
every answer variable $x$. Note that since $q$ is acyclic and free/̄connex
acyclic, so is $q^{\prime}$. By Lemma C.1 $Q(D)=q^{\prime}(D^{\prime})$ and
thus we can use an existing procedure as a black box for enumerating
$q^{\prime}(D^{\prime})$ in $\mathsf{CD}$$\circ$$\mathsf{Lin}$ (bagan-enum-
cdlin, ).

The argument for Point (2) is identical, based on Proposition 4.2. ∎

See 4.3

###### Proof.

Let $Q\in(\mathbb{ELI},\mathbb{CQ})$ satisfy the conditions from Theorem 4.3.
Assume that enumerating complete answers to $Q$ is in
$\mathsf{DelayC}_{\mathsf{lin}}$. Let the Boolean OMQ $Q^{\prime}$ be obtained
from $Q$ by quantifying all answer variables. Then $Q^{\prime}$ satisfies the
same conditions, that is, it is not acyclic, non-empty and self/̄join free. It
is even weakly acyclic since acyclicity and weak acyclicity coincide for
Boolean CQs. Moreover, single-testing for $Q^{\prime}$ is in linear time
because given an $\mathbf{S}$-database $D$, we can check whether $()\in
Q^{\prime}(D)$ by enumerating $Q$ on $D$, but accepting after the first ouput
and rejecting if there was no output. It thus follows from Theorem 3.4 that
the triangle conjecture fails. The same argument works for minimal partial
answers and for minimal partial answers with multiple wildcards. ∎

###  D.1. Lower Bound for Proposition 4.2

We prove the following counterpart of Proposition 4.2. Note that it is not
subsumed by Theorem 4.6 because, there, the arity of relation symbols is at
most 2. As we are working without ontologies here, our proof follows closely
the lines of corresponding lower bounds for enumeration given in (bagan-enum-
cdlin, ; BraultBaron, ; berkholz-enum-tutorial, ). For the same reason, we
rely on the additional assumption stating that $(k+1,k)$/̄hyperclique problem
cannot be solved in time $O(n^{k})$.

The $(k+1,k)$/̄ _hyperclique problem_ is as follows. Given a $k$/̄uniform
hypergraph with $n$ vertices, i.e. every hyperedge consists of exactly $k$
vertices, decide whether it contains a hyperclique of size $k{+}1$, i.e. a set
of $k+1$ vertices where every subset of size $k$ is a hyperedge. The
hyperclique conjecture states that for all $k\geq 3$ solving the
$(k+1,k)$/̄hyperclique problem requires $n^{k+1-o(1)}$ time (lincoln-soda-
grain-complexity, ).

###### Lemma D.1.

Let $q(\bar{x})$ be a self/̄join free CQ that is not free-connex acyclic. Then
all-testing for $q$ is not in $\mathsf{DelayC}_{\mathsf{lin}}$ unless one of
the following holds:

  1. (1)

the triangle conjecture fails;

  2. (2)

Boolean $n\times n$ matrices can be multiplied in time $O(n^{2})$;

  3. (3)

$(k+1,k)$/̄hyperclique problem can be solved in time $O(n^{k})$.

To prove Lemma D.1, we make use of the following well-known characterization
of acyclicity.

###### Theorem D.2 ((beeri-acyclic, )).

A CQ $q$ is acyclic iff it satisfies the following properties:

  1. (1)

$q$ is conformal, i. e. for every clique of the Gaifman graph $G_{q}$ of $q$
there exists an atom that contains all variables in the clique;

  2. (2)

$q$ is chordal, i. e. every cycle of length at least $4$ in $G_{q}$ has a
chord. That is, $G_{q}$ contains an edge that is not part of the cycle but
connects two vertices of the cycle.

We now prove Lemma D.1. Let $q$ be as in the lemma and let us assume that all-
testing for $q$ is in $\mathsf{DelayC}_{\mathsf{lin}}$. We show that one of
Points (1)-(3) applies.

Recall that $\hat{q}(\bar{x})$ is the CQ $q(\bar{x})$ with the additional atom
$\hat{R}(\bar{x})$ where $\hat{R}$ is a fresh relation symbol. Since $q$ is
not free/̄connex acyclic, $\hat{q}$ is not acyclic. Hence, $\hat{q}$ is not
conformal or not chordal.

#### Not chordal

If $\hat{q}$ is not chordal, then there is a cordless cycle
$z_{1},z_{2},\dots,z_{m}$ of length $m\geq 4$ in the Gaifman graph of
$\hat{q}$. Moreover, since there is an atom $\hat{R}(\bar{x})$ in $\hat{q}$,
there are no more than two answer variables in this cycle.

#### At most one answer variable in the cycle.

If there is no more than one answer variable in the cycle, then also CQ $q$ is
not chordal, as the new edges in the Gaifman graph of $\hat{q}$ are only those
between answer variables. Hence, we can use the construction for the “not
chordal” case form Section 6.2. in (berkholz-enum-tutorial, ). Given an
undirected graph $G$, it constructs in time $O(n)$ a database $D$ such that
$q(D)\neq\emptyset$ if and only if $G$ has a triangle.

Moreover, a careful analysis of the construction reveals that, in fact, we
only need to test $O(n)$ different tuples
$\bar{a}\in\mathsf{adom}(D)^{|\bar{x}|}$ to decide whether
$q(D)\neq\emptyset$, and we can compute the set of those tuples in time
$O(n)$. Thus, assuming that all-testing is in
$\mathsf{DelayC}_{\mathsf{lin}}$, we can decide whether $q(D)\neq\emptyset$ in
time $O(n)$. Indeed, the database $D$ can be constructed in time $O(n)$. Thus,
the preprocessing phase can be done in $O(n)$ time and testing can be carried
out in time $O(n)$. This gives overall running time $O(n)$, and disproves the
triangle conjecture.

#### Two answer variables in the cycle.

If there are two answer variables in the cycle, then without loss of
generality we can assume that they are $x_{1}=z_{1}$ and $x_{2}=z_{m}$.
Indeed, since there is an atom $\hat{R}(\bar{x})$ in $\hat{q}$ and the cycle
is chordless, the answer variables have to be two consecutive vertices in the
cycle. Thus, to obtain $x_{1}=z_{1}$ and $x_{2}=z_{m}$ we can simply rename
some variables in $q$. Now we have two possibilities. Either there is an atom
in $q$ that contains both $x_{1}$ and $x_{2}$ or there is no such atom in $q$.

If there is no such atom, then we can use the construction for the “acyclic
but not free/̄connex acyclic query” case form Section 6.1. in (berkholz-enum-
tutorial, ). In the terminology of (berkholz-enum-tutorial, ), applying the
construction requires that there is a ‘bad path’ in $q$. This is the case when
$x_{1},x_{2}$ do not co-occur in an atom in $q$. Given two $n{\times}n$
Boolean matrices $M_{1},M_{2}$, the construction creates in time $O(n^{2})$ a
database $D$ such that the set $q(D)$ projected to the first two coordinates
is the set $M_{1}M_{2}$.

Notice that the construction in (berkholz-enum-tutorial, ) is used for queries
that are not only free-connex acyclic, but also acyclic. However, acyclicity
is only used to guarantee the existence of a bad path and not in the
construction of the database $D$. It is easy to verify that the following
claim is valid also in our setting.

###### Claim D.1.

For every pair $(i,j)\in[n]^{2}$ we have $(i,j)\in M_{1}M_{2}$ if and only if
there is a corresponding answer $\bar{a}_{i,j}$ in $q(D)$ where the tuple
$\bar{a}_{i,j}$ can be computed from $(i,j)$ in constant time.

Hence, to compute $M_{1}M_{2}$ we only need to test $\bar{a}_{i,j}\in q(D)$
for all $(i,j)\in[n]^{2}$. If all-testing is in
$\mathsf{DelayC}_{\mathsf{lin}}$, we can thus compute $M_{1}M_{2}$ in time
$O(n^{2})$. Indeed, the database $D$ can be constructed in time $O(n^{2})$.
Thus, the preprocessing phase can be done in $O(n^{2})$ time and testing can
be carried out in time $O(n^{2})$. This gives overall running time $O(n^{2})$.

In the case that $x_{1}$ and $x_{2}$ are in an atom $R^{\prime}(\bar{w})$ in
$q$, we slightly modify the construction by adding to the database $D$ also
the $R^{\prime}$/̄facts that are total on $x_{1},x_{2}$ and use the unique
constants for the remaining variables. Since the cycle is chordless, no other
variables from the cycle appear in $R^{\prime}(\bar{w})$. Thus, every such set
of facts is of size $n^{2}$ and the database can be constructed in time
$O(n^{2})$.

#### Not conformal

Now assume that $\hat{q}$ is not conformal. Then there are $k$ and a clique
$z_{1},\dots,z_{k+1}$ such that the clique is not covered by and atom and
every proper subset of $\\{z_{1},\dots,z_{k+1}\\}$ is. Indeed, it is enough to
take a minimal clique that is not covered by an atom. Let
$Z=\\{z_{1},\dots,z_{k+1}\\}$.

Again, we have two cases. Either every proper subset of $Z$ can be covered by
an atom that is not $\hat{R}(\bar{x})$ or there is a proper subset of $Z$ such
that the only atom that covers it is $\hat{R}(\bar{x})$.

In the former case, $q$ is not conformal and we can apply the construction for
the “not conformal” case form Section 6.2. in (berkholz-enum-tutorial, ).
Given a $k$/̄uniform hypergraph $G$, it creates in time $O(n^{k})$ a database
$D$ such that $q(D)\neq\emptyset$ if and only if $G$ contains a hyperclique of
size $k{+}1$. A careful analysis of the construction reveals that, in fact, we
only need to test $O(n^{k})$ different tuples
$\bar{a}\in\mathsf{adom}(D)^{|\bar{x}|}$ to decide whether $q(D)\neq\emptyset$
and that we can compute the set $W$ of those tuples in time $O(n^{k})$.

If there is an algorithm for all-testing in $\mathsf{DelayC}_{\mathsf{lin}}$,
we can thus solve the hyperclique problem $O(n^{k})$. Indeed, database $D$ can
be constructed in time $O(n^{k})$, the preprocessing phase can be done in
$O(n^{k})$ time, and testing all tuples from $W$ can be carried out in time
$O(n^{k})$. This gives the overall running time $O(n^{k})$.

Finally, for the case where there is a proper subset of $Z$ such that the only
atom that covers it is $\hat{R}(\bar{x})$ we follow the same construction but
using $\hat{q}$ instead of $q$. Then we remove all $\hat{R}$/̄facts from the
database $D$ and adjust the set of tuples $W$ so that it is consistent with
the removed facts. It is easy to see that this adaptation can be done in time
$O(n^{k})$ and does not change the results of the test. This ends the proof.

###  D.2. Proof of Theorem 4.4

There are several characterizations of when an acyclic CQ is free/̄connex
(berkholz-enum-tutorial, ). A characterization that we use in what follows is
via bad paths. A _bad path_ in a CQ $q$ is a sequence of variables
$y_{1},\dots,y_{n}$, $n\geq 3$, such that $y_{1}$ and $y_{n}$ are distinct
answer variables, $y_{2},\dots,y_{n-1}$ are quantified variables, and
$\\{y_{i},y_{i+1}\\}$ is an edge in the Gaifman graph of $q$ while
$\\{y_{1},y_{n}\\}$ is not. It was shown in (bagan-enum-cdlin, ) that an
acyclic CQ is free/̄connex if and only if it has no bad path, see also
(berkholz-enum-tutorial, ).

See 4.4 Before we prove the theorem, let us recall some basic relations
between the sets of complete answers, minimal partial answers, and minimal
partial answers with multiple wildcards.

###### Claim D.2.

For every OMQ $Q\in(\mathbb{G},\mathbb{CQ})$ there is a constant $K$ such that
for every database $D$ holds

$|Q(D)|\leq|Q(D)^{\ast}|\leq|Q(D)^{\mathcal{W}}|\leq K|Q(D)^{\ast}|.$

Every complete answer is also a minimal partial answer (with multiple
wildcards), thus $Q(D)\subseteq Q(D)^{\ast}$ and $Q(D)\subseteq
Q(D)^{\mathcal{W}}$. Hence, the first inequality. The remaining inequalities
are a consequence of Lemma F.5. By Point (1) of Lemma F.5, we have that
$|Q(D)^{\mathcal{W}}|\leq K|Q(D)^{\ast}|$, where $K$ is some constant that
depends only on $Q$. Indeed, every minimal partial answer with multiple
wildcards is in a cone of some minimal partial answer. Since every cone has no
more than $k^{2^{k}}$ elements, where $k$ is the number of answer variables,
the last inequality holds. Finally, by Point (2) and Point (3) of Lemma F.5
there is an injective function from $Q(D)^{\ast}$ to $Q(D)^{\mathcal{W}}$ and,
thus, the middle inequality holds.

Let $Q=(\mathcal{O},\mathbf{S},q)\in(\mathbb{ELI},\mathbb{CQ})$ be an OMQ as
in the theorem. To prove Theorem 4.4 we show that if given a database $D$ we
can enumerate any of the sets $Q(D)$, $Q(D)^{\ast}$, or $Q(D)^{\mathcal{W}}$
in $\mathsf{DelayC}_{\mathsf{lin}}$, then spBMM is possible in time
$\mathcal{O}(|M_{1}|+|M_{2}|+|M_{1}M_{2}|)$.

Assume that we are given Boolean matrices $M_{1}$ and $M_{2}$ of size $n\times
n$. Recall that in sparse Boolean matrix multiplication (spBMM), $M_{1}$ and
$M_{2}$ are given as lists of pairs $(a,b)$ with $M_{i}(a,b)=1$ and also
$M_{1}M_{2}$ is output as such a list. For a pair $(a,b)$ by
$\Pi_{\textit{col}}((a,b))$ we denote the column and by
$\Pi_{\textit{row}}((a,b))$ the row.

We use $M_{1}$ and $M_{2}$ to construct an $\mathbf{S}$-database $D$ such that
enumerating $Q(D)$ or $Q(D)^{\ast}$ in $\mathsf{DelayC}_{\mathsf{lin}}$ allows
us to construct $M_{1}M_{2}$ within the desired time bound.

As a preliminary, we argue that we can w.l.o.g. assume $M_{1}$ and $M_{2}$ to
satisfy a certain condition that shall prove to be useful in what follows. Let
$P_{M}$ denote the set of _productive indices_ in $n\times n$ matrix $M$, i.e.
$P_{M}=\\{c\in[n]\mid\exists a\,M(a,c)=1\text{ or }M(c,a)=1\\}$. Now the
condition is:

  * ($*$)

for all $c\in P_{M}$, there are $a_{1},a_{2}\in[n]$ with $M(c,a_{1})=1$ and
$M(a_{2},c)=1$.

In fact, we can construct from $M_{1},M_{2}$ in time
$\mathcal{O}(|M_{1}|+|M_{2}|)$ two $(n+2)\times(n+2)$ matrices
$\hat{M}_{1},\hat{M}_{2}$ that satisfy ($*$) and such that $M_{k}(a,b)=1$ if
and only if $\hat{M}_{k}(a+2,b+2)=1$ for $1<a,b\leq n$ and $k={1,2,3}$ where
$\hat{M}_{3}=\hat{M}_{1}\cdot\hat{M}_{2}$. To construct $\hat{M}_{k}$, set

$\begin{array}[]{r@{\;}c@{\;}ll}\hat{M}_{k}(a+2,b+2)&=&{M}_{k}(a,b)&\text{ for
}0<a,b\leq n\\\ \hat{M}_{k}(1,1)&=&\hat{M}_{k}(2,2)=1&\\\
\hat{M}_{1}(i+2,2)&=&0&\text{ for }1\leq i\leq n\\\
\hat{M}_{2}(1,i+2)&=&0&\text{ for }1\leq i\leq n\end{array}$

Note that quite a few entries in the first and second column and row are yet
undefined. Independently of how we define them, $\begin{array}[]{r c
l}\hat{M}_{3}(a+2,b+2)&=&\hat{M}_{1}(a+2,1)\hat{M}_{2}(1,b+2)\\\
&+&\hat{M}_{1}(a+2,2)\hat{M}_{2}(2,b+2)\\\
&+&\sum_{c=0}^{n}\hat{M}_{1}(a+2,c+2)\hat{M}_{2}(c+2,b+2)\\\
&=&\sum_{c=0}^{n}{M}_{1}(a,c){M}_{2}(c,b)\\\ &=&M_{1}M_{2}(a,b)=M_{3}(a,b).\\\
\end{array}$

Hence, we can use the remaining undefined positions to satisfy ($*$). It
clearly suffices to add at most $2*|P_{M_{1}}\cup P_{M_{2}}|$ ones to each
matrix and thus $|\hat{M}_{1}|+|\hat{M}_{2}|\in O(|M_{1}|+|M_{2}|)$. We can
thus use $\hat{M}_{1}$ and $\hat{M}_{2}$ in place of $M_{1}$ and $M_{2}$.

Recall that $q$ is acyclic, but not free-connex acyclic and that, as discussed
in the preliminaries, this implies that $q$ contains a bad path, i.e. a
sequence of variables a sequence of variables
$x_{1},y_{1},\dots,y_{\ell},x_{2}$, $\ell\geq 1$, with $x_{1},x_{2}$ answer
variables and $y_{1},\dots,y_{\ell}$ quantified variables such that any two
consecutive variables form an edge in the Gaifman graph of $q$, but not two
non-consecutive variables do. Since $q$ is acyclic and connected, the
undirected graph $G^{\mathsf{var}}_{q}$ is a disjoint union of trees (as the
connectedness can be ‘via’ a constant). We can impose a direction on these
trees. For the tree that contains $x_{1}$, we do this by choosing $x_{1}$ as
the root and call a variable in the tree a successor of another variable if it
is further away from $x_{1}$, and likewise for descendants and ancestors. For
the other trees we do the same, choosing a root as follows. If $q$ contains an
atom that contains a variable $x$ from the tree and a constant, then choose
such an $x$ as the root. Otherwise choose the root arbitrarily.

To present the reduction in a more transparent way, we make the following
simplifying assumptions:

  * (Dir)

if $y$ is a successor of $x$ in $G^{\mathsf{var}}_{q}$, then any binary atom
in $q$ that involves $x$ and $y$ is directed towards $y$, that is, it takes
the form $R(x,y)$; moreover, any binary atom in $q$ that involves a variable
$x$ and a constant $c$ is directed towards $c$ if $x$ is reachable from
$x_{1}$ in $G^{\mathsf{var}}_{q}$ and away from $c$ otherwise;

  * (Mult)

$q$ contain no non-reflexive multi-edges, that is, no two distinct non-
reflexive binary atom that mention the same terms.

It is not difficult to get rid of these assumptions. In fact, this can be done
as follows. Given $q$, first re-orient the edges and drop all edges but one
from non-reflexive multi-edges, obtaining a CQ $q^{\prime}$ that satisfies
(Dir) and (Mult). Then construct the $\mathbf{S}$-database $D$ as described
below and obtain from it another $\mathbf{S}$-database $\hat{D}$ by re-
orienting edges back to their original direction and adding back multi-edges.
Finally, show that every homomorphism from $q$ to
$\mathsf{ch}_{\mathcal{O}}(\hat{D})$ is also a homomorphism from $q^{\prime}$
to $\mathsf{ch}_{\mathcal{O}}(D)$ and vice versa. We omit details.

We now turn towards the announced construction of the $\mathbf{S}$-database
$D$. Let
$R_{0}(x_{1},y_{1}),R_{1}(y_{1},y_{2}),\dots,R_{\ell-1}(y_{\ell-1},y_{\ell}),R_{\ell}(y_{\ell},x_{2})$
be the (unique) atoms in $q$ that give rise to the bad path from $x_{1}$ to
$x_{2}$.

###### Lemma D.3.

$R_{0},\dots,R_{\ell}\in\mathbf{S}$.

###### Proof.

Assume to the contrary of what is to be shown that $R_{i}\not\in\mathbf{S}$
for some $R_{i}$. Since $Q$ is non-empty, there is an $\mathbf{S}$-database
$D_{0}$ such that $Q(D_{0})\neq\emptyset$ and thus there is a homomorphism
$h_{0}$ from $q$ to $\mathsf{ch}_{\mathcal{O}}(D_{0})$. Since $\mathcal{O}$ is
an ${\mathcal{}ELI}$ ontology, the restriction of
$\mathsf{ch}_{\mathcal{O}}(D_{0})$ to $\mathsf{adom}(D_{0})$ does not contain
any binary facts that use a relation symbol $R\notin\mathbf{S}$. Since
$R_{i}\notin\mathbf{S}$, $h_{0}$ must thus map at least one of the variables
on the bad path to a null. Since $\mathcal{O}$ is an ${\mathcal{}ELI}$
ontology, $\mathsf{ch}_{\mathcal{O}}(D_{0})$ takes the shape of $D_{0}$ with
trees without multi-edges and self loops attached to every constant. Since
$h_{0}$ maps some variable on the bad path to a null and both $x_{1}$ and
$x_{2}$ to $\mathsf{adom}(D_{0})$, there must be two distinct atoms in the bad
path that are mapped to a fact that crosses from the database part of
$\mathsf{adom}(D_{0})$, into the null part. This is impossible since $q$ is
self-join free. ∎

Let $C=\mathsf{con}(q)$ if $\mathsf{con}(q)$ is non-empty and $C=\\{\bot\\}$
otherwise, $\bot$ a fresh constant. Moreover, let
$C_{\mathbf{S}}=\\{\bot_{R}\mid R\in\mathbf{S}\text{ binary}\\}$ where each
$\bot_{R}$ is a fresh constant. The active domain of the database $D$ that we
aim to construct is

$\mathsf{adom}(D)=P_{{M}_{1}}\cup P_{{M}_{2}}\cup C\cup C_{\mathbf{S}}$

and $D$ contains the following facts:

  * •

$A(c)$ for every unary $A\in\mathbf{S}$ and every $c\in\mathsf{adom}(D)$;

  * •

For relation symbol $R_{0}$:

    * –

$R_{0}(a,b)$ for all $a,b\in[n]$ such that ${M}_{1}(a,b)=1$;

    * –

$R_{0}(c,c)$ for all $c\in C\cup C_{\mathbf{S}}$;

  * •

For relation symbol $R_{\ell}$:

    * –

$R_{\ell}(a,b)$ for all $a,b\in[n]$ such that ${M}_{2}(a,b)=1$;

    * –

$R_{\ell}(c,c)$ for all $c\in C\cup C_{\mathbf{S}}$;

  * •

For each relation symbol $R_{i}$, $0<i<\ell$:
$R_{i}(a,a)$ for all $a\in[n]$;

  * •

For each relation symbol $R\in\mathbf{S}\setminus\\{R_{0},\dots,R_{\ell}\\}$:

    * –

$R(\bot_{R},a)$ for all $a\in[n]$;

    * –

$R(a,c)$, and $R(c,c^{\prime})$ for all $a\in[n]$, and $c,c^{\prime}\in C$.

    * –

$R(a,a)$ for all $a\in[n]$ if $q$ contains reflexive atom $R(z,z)$.

It should be clear that $D$ can be constructed in time linear in
$|{M}_{1}|+|{M}_{2}|$. Moreover, $D$ satisfies the _completeness property_
that every $c\in\mathsf{adom}(D)$ has an incoming and an outgoing edge for
every $R\in\mathbf{S}$ since $M_{1}$ and $M_{2}$ satisfy Condition ($*$)
above. We next show how answers to $Q$ on $D$ are related to one entries in
the matrix product $M_{1}M_{2}$.

###### Lemma D.4.

Let $(a,b)\in[n]^{2}$. Then ${M}_{1}{M}_{2}(a,b)=1$ if and only if there is a
complete answer $(a_{1},a_{2},\dots,a_{k})\in Q(D)$ such that $a_{1}=a$ and
$a_{2}=b$.

###### Proof.

“if”. Let $(a_{1},a_{2},\dots,a_{k})\in Q(D)$ so that $a_{1}=a$ and $a_{2}=b$.
Then there is a homomorphism $h$ from $q$ to $\mathsf{ch}_{\mathcal{O}}(D)$
such that $h(x_{1})=a$ and $h(x_{2})=b$. Consider the image of the path
$R_{0}(x_{1},y_{1}),\dots,R_{\ell}(y_{\ell},x_{2})$ under $h$ in
$\mathsf{ch}_{\mathcal{O}}(D)$. We first argue that this image is actually
contained in $D$.

Recall the $\mathcal{O}$ is an ${\mathcal{}ELI}$ ontology and
$\mathsf{ch}_{\mathcal{O}}(D)$ takes the shape of $D$ with trees without
multi-edges and self loops attached to each constant. It follows that none of
$h(y_{1}),\dots,h(y_{\ell})$ is a null as then the image of the path would
start at $a$ (in the database part), then cross to the null part and
eventually cross back to end at $b$. But this is not possible because of the
described form of $\mathsf{ch}_{\mathcal{O}}(D)$ and since the relation
symbols $R_{0},\dots,R_{\ell}$ are all distinct (as $q$ is self join free).
Since the chase with an ${\mathcal{}ELI}$ ontology does not add any facts
$R(c_{1},c_{2})$ with $c_{1},c_{2}\in\mathsf{adom}(D)$, the image of the path
must indeed by in $D$.

Considering the construction of $D$, it is now easy to see that
$h(y_{1})=\cdots=h(y_{\ell})=u$ for some $u\in\\{1,\dots,n\\}$. In particular,
note that the only $R_{0}$\- and $R_{\ell}$-edges that originate at a constant
from $[n]$ also end at a constant from $n$, and that the relation symbols
$R_{i}$, $1\leq i<\ell$, only occur in reflexive facts. Thus, $D$ contains
atoms $R_{0}(a,u),R_{\ell}(u,b)$, which by the definition of $D$ implies that
${M}_{1}(a,u)=1$ and ${M}_{2}(u,b)=1$. Consequently, $M_{1}M_{2}(a,b)=1$.

“only if”. Let ${M}_{1}{M}_{2}(a,b)=1$. Then we have ${M}_{1}(a,u)=1$ and
${M}_{2}(u,b)=1$ for some $u$ with $1\leq u\leq n$. Moreover, since $Q$ is not
empty, there is a database $D_{0}$ and a homomorphism $h_{0}$ from $q$ to
$\mathsf{ch}_{\mathcal{O}}(D_{0})$ such that
$h_{0}(x_{1}),h_{0}(x_{2})\in\mathsf{adom}(D_{0})$.

We construct a homomorphism $h$ from $q$ to $\mathsf{ch}_{\mathcal{O}}(D)$.
Start with setting $h(c)=c$ for every constant $c$ in $q$, $h(x_{1})=a$,
$h(x_{2})=b,$ and $h(y_{v})=u$ for $1\leq v\leq\ell$. We also choose a
$c_{\bot}\in C$ and set $h(x)=c_{\bot}$ for all $x$ such that $h(x)$ was not
previously defined and $h_{0}(x)\in\mathsf{adom}(D_{0})$.

It can be verified that $h$ is a homomorphism from $q|_{h}$ to
$\mathsf{ch}_{\mathcal{O}}(D)$ where $q|_{h}$ is the restriction of $q$ to the
domain of $h$. We first argue that $h$ respects all binary atoms in $q|_{h}$
and the consider the unary atoms.

First note that $h$ respects all binary atoms that involve any pair of
variables $(x_{1},y_{1})$, $(y_{i},y_{i+1})$ for $1\leq i<\ell$, and
$(y_{\ell},x_{2})$ by construction of $D$ and due to ($\mathsf{Mult}$).
Reflexive binary atoms on a variable from the bad path are also defined by
definition of $D$. There are no atoms that involve other combinations of
variables on the bad path such as $(x,y_{2})$ since $G^{\mathsf{var}}_{q}$ is
a disjoint union of trees. By definition of $D$, it is also clear that all
binary atoms are respected that involve only constants and non-path variables
for which $h$ is defined. Finally, atoms that involve a path variable and a
constant or a non-path variable are respected by ($\mathsf{Dir}$) and
construction of $D$.

Now for the unary atoms $A(x)$. If $A\in\mathbf{S}$, then $A(x)$ is satisfied
since $A(c)\in D$ for every $c\in\mathsf{adom}(D)$. Thus let
$A\notin\mathbf{S}$. The completeness property of $D$ implies that
$(D_{0},h_{0}(x))\preceq(D,h(x))$, no matter what $h(x)$ is. It thus follows
from Lemma A.3 that $D\models(\mathcal{O},\mathbf{S},A(x))(h(x))$.

We next extend $h$ to all remaining variables in $q$. Assume that $h(t)$ is
defined, $q$ contains an atom that uses term $t$ and variable $y$, and $h(y)$
is not yet defined. First assume that $t$ is a constant $c$. Since $h(y)$ is
undefined, $h_{0}(y)$ is a null. Due to ($\mathsf{Dir}$) and
($\mathsf{Mult}$), $q$ contains a single atom $R(y,c)$ that mentions $y$ and
$c$. Due to the self-join freeness of $q$, $h_{0}$ maps all variables in the
subtree of $G^{\mathsf{var}}_{q}$ rooted at $y$ to a null, the exact argument
for this is similar to the one used in the “if” direction. It follows that the
CQ $p(z)$, which is the restriction of $q$ to the variables in the subtree of
$G^{\mathsf{var}}_{q}$ rooted at $y$, extended with atom $R(y,z)$, contains no
multi-edges and reflexive loops, thus is an ELIQ. The completeness property of
$D$ implies that $(D_{0},h_{0}(z))\preceq(D,h(z))$, no matter what $h(z)$ is.
It thus follows from Lemma A.3 that
$D\models(\mathcal{O},\mathbf{S},p(x))(h(x))$, and consequently there is a
homomorphism $g$ from $p(x)$ to $\mathsf{ch}_{\mathcal{O}}(D)$ with
$g(x)=h(x)$. We can extend $h$ to the variables in $p$ by setting $h:=h\cup
g$.

Now assume that $t$ is a variable $z$. Then $h_{0}(z)$ is not a null and
$h_{0}(y)$ is a null. Moreover, $y$ is a successor of $z$ in the direction
that we have imposed on $G^{\mathsf{var}}_{q}$ because $h_{0}(x_{1})$ is non-
null (as $h_{0}$ witnesses non-emptiness w.r.t.  _complete_ answers). Due to
the self-join freeness of $q$, $h_{0}$ maps all variables in the subtree of
$G^{\mathsf{var}}_{q}$ rooted at $y$ to a null. It follows that the
restriction $p(z)$ of $q$ to $z$ and the variables in the subtree of
$G^{\mathsf{var}}_{q}$ rooted at $y$ contains no multi-edges and reflexive
loops, thus is an ELIQ. We can proceed as in the case where $t$ is a constant.
∎

To finish the proof of Theorem 4.4 we use the following lemma and Claim D.5.

###### Lemma D.5.

The number of minimal partial answers $Q(D)^{\ast}$ is bounded by
$\mathcal{O}(|M_{1}|+|M_{2}|+|M_{1}M_{2}|)$.

We can now prove Theorem 4.4 as follows. Assume that there is an algorithm
that enumerates set $Q(D)$ (or $Q(D)^{\ast}$ or $Q(D)^{\mathcal{W}}$) in
$\mathsf{DelayC}_{\mathsf{lin}}$. Given matrices $M_{1},M_{2}$, we can
construct the database $D$ in time $\mathcal{O}(|{M}_{1}|+|{M}_{2}|)$ and use
and enumerate the answers in time $\mathcal{O}(|M_{1}|+|M_{2}|+|M_{1}M_{2}|)$,
cf. Lemma D.5. Finally, by Lemma D.4, the projection to the first two
positions of the enumerated complete answers gives us a list representation of
$M_{1}M_{2}$ in total time $\mathcal{O}(|{M}_{1}|+|{M}_{2}|+|M_{1}M_{2}|)$.

A central ingredient to the proof of Lemma D.5 is the following.

###### Lemma D.6.

Let $h$ be a homomorphism from $q$ to $\mathsf{ch}_{\mathcal{O}}(D)$. If there
are two distinct answer variables $x_{i}$, $x_{j}$ such that
$h(x_{i}),h(x_{j})\in[n]$, then $\\{x_{i},x_{j}\\}=\\{x_{1},x_{2}\\}$.

###### Proof.

Assume that $x_{i},x_{j}$ are distinct answer variables such that
$h(x_{i}),h(x_{j})\in[n]$. Due to the way in which we have oriented the edges
in $G^{\mathsf{var}}_{q}$, it must be the case that

  1. (1)

$x_{i}$ and $x_{j}$ are in the same tree in $G^{\mathsf{var}}_{q}$ as $x_{1}$
and $x_{2}$.

In fact, assume to the contrary that $x_{i}$ (or $x_{j}$) is in a different
tree in $G^{\mathsf{var}}_{q}$ than $x_{1}$ and $x_{2}$. Then since $q$ is
connected, $q$ must contain a binary atom that contains a constant $c$ and a
variable $x$ from the tree. By the way we have imposed a direction on the
trees in $G^{\mathsf{var}}_{q}$ and by ($\mathsf{Dir}$), we even find such a
$c$ and an $x$ such that all edges in the tree are oriented away from $x$.
Also by ($\mathsf{Dir}$), the edge between $c$ and $x$ is oriented towards
$x$. Thus, there is a directed path in $q$ from $c$ to $x_{i}$. But there is
no such (directed!) path from $c$ to a constant in $[n]$ in $D$. Since
$\mathcal{O}$ is an ${\mathcal{}ELI}$ ontology, the same holds for
$\mathsf{ch}_{\mathcal{O}}(D)$. We have thus shown ($*$).

We next observe that since $q$ is connected and since all edges in
$G^{\mathsf{var}}_{q}$ are oriented away from the roots of the trees, one of
the following must hold:

  1. (2)

there is a variable $y$ such that $x_{i}$ and $x_{j}$ are both reachable in
$G^{\mathsf{var}}_{q}$ from $y$ on a directed path;

  2. (3)

$x_{i}$ and $x_{j}$ are in different trees in $G^{\mathsf{var}}_{q}$, but
there is a constant $c$ such that $x_{i}$ and $x_{j}$ are reachable in $q$
from $c$ on a (not necessarily directed) path.

Point (3), however, is ruled out by Point (1). We are thus left with Point
(2). Consider the combined path from $x_{i}$ to $y$ to $x_{j}$. Since $q$ is
self-join free, all relation symbols on this path are distinct. Now take the
image under $h$ of the path in $\mathsf{ch}_{\mathcal{O}}(D)$. It starts and
ends at a constant in $[n]$. Moreover, (i) the edge from $x_{i}$ to the next
variable $y$ on the path must be directed towards $x_{i}$ or (ii) the edge
from the variable $z$ before $x_{j}$ on the path to $x_{j}$ must be directed
towards $x_{j}$. We only consider Case (i) as Case (ii) is completely
symmetric.

In Case (i), the construction of $D$ implies that $h(y)$ can only be a null or
of the form $\bot_{R}$. First assume the former. Then the $h$-image of the
path crosses from the database part of $\mathsf{ch}_{\mathcal{O}}(D)$ to the
null part and eventually back to reach $h(x_{j})\in[n]$. But since
$\mathcal{O}$ is an ${\mathcal{}ELI}$ ontology, the shape of
$\mathsf{ch}_{\mathcal{O}}(D)$ is that of $D$ with trees without multi-edges
and reflexive loops attached to each constant from $\mathsf{adom}(D)$. Thus,
there is no path in $\mathsf{ch}_{\mathcal{O}}(D)$ of the described form in
which no relation symbol occurs twice.

Now assume that $h(y)$ is of the form $\bot_{R}$. Then the $h$-image of the
path starts at a constant of $[n]$, then reaches a constant of the form
$\bot_{R}$, and eventually again a constant of the form $[n]$. But by
construction $D$ contains no path of this form on which no relation symbol
occurs twice. Since $\mathcal{O}$ is an ${\mathcal{}ELI}$ ontology, the same
is true for $\mathsf{ch}_{\mathcal{O}}(D)$. ∎

###### Proof of Lemma D.5..

Let $\bar{a}=(a_{1},a_{2},\dots,a_{k})\in Q(D)^{\ast}$ be a partial answer. By
Lemma D.6, either $\bar{a}\cap[n]=\\{a_{1},a_{2}\\}$ or there is at most one
value from $[n]$ in $\bar{a}$, i.e. $\\{a\\}=\bar{a}\cap[n]$ for some $a$.

In the former case, we observe that for every variable $x_{i}$, $1\leq i\leq
k$, such that $a_{i}\neq a$, the value $a_{i}$ can be chosen from at most
$|C|+|C_{\mathbf{S}}|+1$ possibilities. Since $k$ is a fixed constant
depending only on the query, we have $O(|M_{1}|+|M_{2}|)$ answers of the
former kind. Similarly, by Lemma D.4 we can conclude that the number of
answers satisfying the latter case is bounded by $O(|M_{1}M_{2}|)$. Indeed,
the number of possible pairs $(a_{1},a_{2})$ is $|M_{1}M_{2}|$ and the
remaining undefined values in $\bar{a}$ are chosen from a set of size
$O(|q|)$. This ends the proof the lemma.

We analyse separately the minimal partial answers
$(a_{1},a_{2},\dots,a_{k})\in Q(D)^{\ast}$ such that $a_{i}\in[n]$ for some
$i>2$ and those for which $a_{i}\in[n]$ only if $i\in\\{1,2\\}$.

For answers of the former kind, Lemma D.6 implies that $a_{j}\notin[n]$ for
all $j\in\\{1,\dots,i-1,i+1,k\\}$. Consequently, the number of answers of this
kind is bounded by $O(|M_{1}|+|M_{2}|)$.

Now for answers of the latter kind. In this case, there are only constantly
many choices for $a_{3},\dots,a_{k}$ as we have at most $|C|+|C_{\mathbf{S}}|$
different possibilities for indices in $i\in\\{3,\dots,k\\}$, and $k$ is a
constant. We may further distinguish between answers where at most one of
$a_{1},a_{2}$ is from $[n]$ and where both are. Due to the limited number of
possible choices for $a_{3},\dots,a_{k}$, the number of answers of the former
kind is bounded by $O(|M_{1}|+|M_{2}|)$ and Lemma D.4 implies that the number
of answers of the latter kind is bounded by $O(|M_{1}M_{2}|)$. This ends the
proof of the conditional lower bound.

∎

We give some remarks on (im)possible generalizations of Theorem 4.4. Replacing
$\mathbb{ELI}$ with $\mathbb{G}$ in Theorem 4.4 would allow us to also remove
‘self-join free’ from Theorem 4.4, as in Example 3.5. But there are CQs (with
self-joins) that are acyclic and not free-connex acyclic, yet their answers
can be enumerated in $\mathsf{CD}$$\circ$$\mathsf{Lin}$ (without ontologies)
(berkholz-enum-tutorial, ).

See 4.5

###### Proof.

Let

$\begin{array}[]{rcl}\mathcal{O}&=&\\{A_{1}(x)\rightarrow
A_{2}(x),B_{1}(x)\rightarrow B_{2}(x),\\\ &&C_{1}(x)\rightarrow C_{2}(x)\\}\\\
\mathbf{S}&=&\\{A_{1},B_{1},C_{1},L,R\\}\\\
q(x_{1},z_{1},x_{2},y_{2},z_{2})&=&L(x_{1},y_{1})\land
R(y_{1},z_{1})\,\land\\\ &&A_{1}(x_{1})\land B_{1}(y_{1})\land
C_{1}(z_{1})\,\land\\\ &&A_{2}(x_{2})\land B_{2}(y_{2})\land
C_{2}(z_{2}).\end{array}$

Note that $Q=(\mathcal{O},\mathbf{S},q)$ satisfies all properties listed in
Proposition 4.5. We argue that complete answers to $Q$ can be enumerated in
$\mathsf{DelayC}_{\mathsf{lin}}$. The idea is that the additional answer
variables $x_{2},y_{2},z_{2}$ enlarge the answer set, which gives additional
computational power in the enumeration phase of the algorithm.

To make this precise, let $D$ be an $\mathbf{S}$/̄database and, by slight
abuse of notation, $A=\\{c\in\mathsf{adom}(D)\mid A(c)\in D\\}$ for every
unary relation symbol $A$, and $|A|$ the size of set $A$. It is clear that
$Q(D)=p(D)\times A_{1}\times B_{1}\times C_{1}$ where

$p(x_{1},z_{1})=L(x_{1},y_{1})\land R(y_{1},z_{1})\land A_{1}(x_{1})\land
B_{1}(y_{1})\land C_{1}(z_{1}).$

Since $q$ is acyclic, we can find an answer
$(a_{1},c_{1},a_{2},b_{2},c_{2})\in Q(D)$ in linear time during the
preprocessing phase. In fact, we can compute $\mathsf{ch}_{\mathcal{O}}(D)$ in
linear time since the chase only needs to add unary relation symbols to
existing constants, and then use the standard Yannakakis algorithm to find an
answer to $q$ on $\mathsf{ch}_{\mathcal{O}}(D)$. This actually reveals the
$|A_{1}|\cdot|B_{1}|\cdot|C_{1}|$ distinct answers in the set
$U=\\{a_{1}\\}\times\\{c_{1}\\}\times A_{1}\times B_{1}\times C_{1}$. Now,
while the algorithm enumerates the answers in $U$ with constant delay, it can
in parallel compute the set $p(D)$ by simply checking all possible triples
$(a_{1},b_{1},b_{2})\in A_{1}\times B_{1}\times C_{1}$. After finishing the
enumeration of $U$, it is then easy to enumerate the remaining answers with
constant delay. ∎

###  D.3. Proof of Theorem 4.6

See 4.6

Let $Q(\bar{x})=(\mathcal{O},\mathbf{S},q)$, and let $\hat{q}(\bar{x})$ be the
CQ obtained from $q$ by adding an atom $R(\bar{x})$ with $R$ a fresh relation
symbol. Since $Q$ is not acyclic free/̄connex $\hat{q}$ is not acyclic.

We observe the following consequence of Theorem D.2.

###### Claim D.3.

There is a chordless cycle $y_{1},y_{2},\dots,y_{\ell}$ in $G_{\hat{q}}$ that
has no repeated vertices and no more than two answer variables.

Since $\hat{q}$ is not acyclic, it is not conformal or not chordal. If it is
not conformal, then there is a clique not contained in an atom. This clique
has to have at least 3 vertices, since every clique of size 2 is an edge, and
at least one quantified variable, as the clique of all answer variables is
induced by the atom $R(\bar{x})$. To obtain the cycle, choose a triangle that
contains this quantified variable.

If $\hat{q}$ is not chordal, then there is a chordless cycle of length at
least $4$. Every such cycle has no more than two answer variables, as there is
an edge between every two answer variables.

We distinguish three cases according to the number of answer variables in the
cycle.

#### No answer variables in the cycle

If no variable in $y_{1},\dots,y_{\ell}$ is an answer variable, then there is
a cycle in $q$ and, thus, $q$ is not weakly acyclic.

Clearly, an algorithm for all-testing for $Q$ in
$\mathsf{DelayC}_{\mathsf{lin}}$ can be used to implement single-testing for
$Q$ in linear time. Thus, Theorem3.4 implies that the triangle conjecture
fails.

#### One answer variable in the cycle

Without loss of generality, we can assume that $x_{1}=y_{1}$ is the single
answer variable in the cycle $y_{1},\dots,y_{\ell}$. Hence the query $q_{0}$
obtained from $q$ by making $x_{1}$ a quantified variable is not weakly
acyclic.

If all-testing for $Q$ is possible in $\mathsf{DelayC}_{\mathsf{lin}}$, then
single-testing for $Q_{0}:=(\mathcal{O},\mathbf{S},q_{0})$ is possible in
linear time: given a candidate answer $\bar{a}$ to $Q_{0}$ on an
$\mathbf{S}$-database $D$, we use the all-testing algorithm to decide whether
$b\bar{a}\in Q(D)$ for any $b\in\mathsf{adom}(D)$, in overall linear time. By
Theorem 3.4, this implies that the triangle conjecture fails.

#### Two answer variables in the cycle

We assume that $x_{1}=y_{1}$ and $x_{2}=y_{\ell}$ are the two answer variables
in the cycle $y_{1},\dots,y_{\ell}$, it shall be clear how the proof can be
adapted if the answer variables are located elsewhere on the cycle. We show
that if all-testing for $Q$ is in $\mathsf{DelayC}_{\mathsf{lin}}$, then given
the two $n\times n$ Boolean matrices $M_{1},M_{2}$ we can compute $M_{1}M_{2}$
in time $\mathcal{O}(n^{2})$.

We use a construction similar to that in the proof of Theorem 4.3. However,
since $Q$ may not be acyclic the construction needs to be suitably adapted.

As shown in proof of Theorem 4.4 we can assume that both $M_{1}$ and $M_{2}$
have $1$ in every row and in every column. Also, we make the following
observation.

###### Claim D.4.

If $R(x,y)$ is an atom in $q$ where $x$ and $y$ are variables in the cycle
$y_{1},\dots,y_{\ell}$ then $R\in\mathbf{S}$.

The proof follows the same pattern as the proof of Lemma D.3.

The active domain of the database $D$ that we aim to construct is
$\mathsf{adom}(D)=[n]\cup\mathsf{con}(q)$ and $D$ contains the following
facts:

  * •

$A(c)$ for every unary $A\in\mathbf{S}$ and every $c\in\mathsf{adom}(D)$;

  * •

for every relation symbol $R\in\mathbf{S}$ we add facts:

    * –

$R(a,b)$ for all $a,b\in[n]$ such that ${M}_{1}(a,b)=1$,

    * if $R(x_{1},y_{2})$ is an atom in $q$;

    * –

$R(b,a)$ for all $a,b\in[n]$ such that ${M}_{1}(a,b)=1$,

    * if $R(y_{2},x_{1})$ is an atom in $q$;

    * –

$R(a,b)$ for all $a,b\in[n]$ such that ${M}_{2}(a,b)=1$,

    * if $R(y_{\ell-1},x_{2})$ is an atom in $q$;

    * –

$R(b,a)$ for all $a,b\in[n]$ such that ${M}_{1}(a,b)=1$,

    * if $R(x_{2},y_{\ell-1})$ is an atom in $q$;

    * –

$R(a,a)$ for all $a\in[n]$,

    * if $R(y_{i},y_{i+1})$ is an atom in $q$ with $2\leq i\leq\ell-2$;

    * –

$R(a,b)$ for all $a,b\in\mathsf{adom}(D)$,

    * if $R(x,y)$ is an atom in $q$ and $x$ and $y$ are not both in the cycle;

    * –

$R(c,c)$ for every $c\in\mathsf{con}(q)$.

The database $D$ can be constructed in time $\mathcal{O}(n^{2})$. Moreover,
for every relation symbol $R\in\mathbf{S}$ and every element
$c\in\mathsf{adom}(D)$ there are $a,b$ such that $R(a,c),R(c,b)\in D$. Thus,
as before, we will be able to extend a partial homomorphism from $q$ to $D$ to
the atoms whose relation symbols are not present in the schema.

To end the reduction it is enough to show the following.

###### Claim D.5.

Let $(a,b)\in[n]^{2}$. Then $(a,b,1,\dots,1)\in Q(D)$ iff
${M}_{1}M_{2}(a,b)=1$.

Indeed, assume that all-testing complete answers for $Q$ is in
$\mathsf{DelayC}_{\mathsf{lin}}$. Then given two matrices $M_{1},M_{2}$, we
can compute $M_{1}M_{2}$ in time $\mathcal{O}(n^{2})$ by first computing the
database $D$ in time $\mathcal{O}(n^{2})$, then executing the preprocessing
phase of the all-testing algorithm in time linear in $||D||$, which is
$\mathcal{O}(n^{2})$, and finally testing the tuple $(a,b,1,\dots,1)$ for
every pair $(a,b)\in[n]^{2}$. $M_{1}M_{2}$ is the set of all pairs $(a,b)$ for
which the test succeeded.

All that is left is to prove the claim. The “$\Rightarrow$” is proven the same
way as in Lemma D.4. For the other direction we cannot use the proof of Lemma
D.4 as the CQ may not be acyclic. We thus do the following. First, we define
$h$ only on $\bar{x}$ so that $h(\bar{x})=(a,b,1,\dots,1)$. Then we argue as
in the proof of Theorem 3.4 that it can be extended to a homomorphism $h$ from
$q$ to $\mathsf{ch}_{\mathcal{O}}(D)$. Details are left to the reader.

For the cases of minimal partial answers and minimal partial answers with
multiple wildcards, recall that $Q(D)\subseteq Q(D)^{\ast}$ and $Q(D)\subseteq
Q(D)^{\mathcal{W}}$. Thus, both the construction and the algorithm work with
no modifications.

##  Appendix E Proofs for Section 5

See 5.1

###### Proof.

We start with showing the result for $(\mathbb{G},\mathbb{CQ})$ in place of
$(\mathbb{ELI},\mathbb{CQ})$. Let $R$ be a binary relation symbol and
$\mathbf{S}=\\{R\\}$. We may view an undirected graph $G=(V,E)$ as the
$\mathbf{S}$-database

$D_{G}=\\{R(v,v^{\prime}),R(v^{\prime},v)\mid\\{v,v^{\prime}\\}\in E\\}.$

Consider the OMQ $Q(x)=(\mathcal{O},\mathbf{S},q)\in(\mathbb{G},\mathbb{CQ})$
where $\mathcal{O}$ contains the TGD

$\begin{array}[]{r@{\;}c@{\;}l}R(x_{1},x_{2})&\rightarrow&\exists y_{1}\exists
y_{2}\,R\\{x_{1},y_{1}\\}\wedge R\\{y_{1},y_{2}\\}\wedge
R\\{y_{2},x_{1}\\}\end{array}$

with $R\\{x,y\\}$ an abbreviation for $R(x,y)\wedge R(y,x)$ and with

$q(x,y,z,u)=R\\{x,y\\}\wedge R\\{y,z\\}\wedge R\\{z,u\\}.$

Let $G=(V,E)$ be an undirected graph. Then $(v,\ast,\ast,v)$ is a partial
answer to $Q$ on $D_{G}$ for every $v\in V$, but not necessarily a minimal
partial answer. In fact, it is a minimal partial answer if and only if $v$ is
not part of a triangle in $G$. It follows that all-testing for $Q$ is not in
$\mathsf{DelayC}_{\mathsf{lin}}$ unless the triangle hypothesis fails: to
decide whether a given graph $G=(V,E)$ contains a triangle, we can construct
$D_{G}$ in time linear in $||E||$, then execute the preprocessing phase of
all-testing for $Q$, and then iterate over all $v\in V$ and test in constant
time whether $(v,\ast,\ast,v)\in Q(D)^{\ast}$. We answer ‘no’ if this is the
case for all $v$ and ‘yes’ otherwise. The same arguments work in the multi-
wildcard case, with $(v,\ast,\ast,v)$ replaced by $(v,\ast_{1},\ast_{1},v)$.

The challenge in improving the construction to $\mathbb{ELI}$ is that
${\mathcal{}ELI}$ TGDs cannot introduce a triangle that consists of nulls. The
solution is to construct $q$, $\mathcal{O}$, and $D$ in a more careful way.
Let us start with $q$, which is now

$q(x_{1},x_{2},x_{3},x_{4},x_{5})=R(x_{1},x_{2})\wedge R(x_{2},x_{3})\wedge
R(x_{4},x_{3})\wedge R(x_{5},x_{4}),$

that is, it is a path of length 4 rather than of length 3 and the direction of
the edges is chosen carefully. We choose $\mathcal{O}$ to contain the
${\mathcal{}ELI}$ TGD

$\begin{array}[]{r@{\;}c@{\;}l}R(x_{1},x_{2})&\rightarrow&\exists y_{2}\exists
y_{3}\,R(x_{1},y_{2})\wedge R(y_{2},y_{3}).\end{array}$

Similarly to before, $(v,\ast,\ast,\ast,v)$ is a partial answer to $Q$ on any
$\mathbf{S}$-database $D$ such that every constant in $D$ has an outgoing
$R$-edge (in the multi-wildcard case, we use
$(v,\ast_{1},\ast_{2},\ast_{1},v)$. It remains to modify $D_{G}$ so that
$q(D_{G})$ contains a tuple $(c_{1},c_{2},c_{3},c_{4},c_{5})$ with
$c_{1}=c_{5}$ if and only if $G=(V,E)$ contains a triangle (as this makes at
least one of the partial answers be not a minimal partial answer). This is
achieved by constructing $D_{G}$ so that $\mathsf{adom}(D_{G})=V\times[4]$ and
it contains the following facts, for each $\\{v,v^{\prime}\\}\in E$:

$R((v,1),(v^{\prime},2)),R((v,2),(v,3)),R((v^{\prime},4),(v,3)),R((v^{\prime},1),(v,4)).$

To finish the proof, it suffices to observe the following.
Claim. $q(D_{G})$ contains a tuple $(c_{1},c_{2},c_{3},c_{4},c_{5})$ with
$c_{1}=c_{5}$ iff $G$ contains a triangle.
For the “if” direction, assume that $v_{1},v_{2},v_{3}$ is a triangle in $G$.
Then the tuple

$((v_{1},1),(v_{2},2),(v_{2},3),(v_{3},4),(v_{1},1))$

is in $q(D_{G})$.

“only if”. Assume that $q(D_{G})$ contains a tuple
$(c_{1},c_{2},c_{3},c_{4},c_{5})$ with $c_{1}=c_{5}$. Consider $c_{3}$. Only
constants of the form $(v_{1},2)$ and $(v_{1},4)$ have both incoming and
outgoing $R$-edges in $D_{G}$, so $c_{2}$ must be of one of these forms.
Assume that $c_{2}=(v_{1},2)$, the case $c_{2}=(v_{1},4)$ is symmetric. The
construction of $D_{G}$ yields the following. We must have $c_{3}=(v_{1},3)$.
The fact $R(c_{4},(v_{1},3))\in D_{G}$ was introduced due to some edge
$\\{v_{2},v_{1}\\}\in E$ and $c_{4}$ must be of the form $(v_{2},4)$. The fact
$R(c_{1},(v_{1},2))\in D_{G}$ was introduced due to some edge
$\\{v_{3},v_{1}\\}\in E$ and $c_{1}$ must take the form $(v_{3},1)$; likewise,
the fact $R(c_{5},(v_{2},4))$ was introduced due to some edge
$\\{v_{4},v_{1}\\}\in E$ and $c_{5}$ must take the form $(v_{4},1)$. Since
$c_{1}=c_{5}$, it follows that $v_{3}=v_{4}$. Thus, the nodes
$v_{1},v_{2},v_{3}$ constitute a triangle in $G$. ∎

###  E.1. Missing Details for Proof of Theorem 5.2

In the main part of the paper, we have declared the goal to be the enumeration
of $q_{0}(\mathsf{ch}^{q_{0}}_{\mathcal{O}}(D))^{\ast}_{\mathbf{N}}$. Here, we
actually prove something slightly more general (based on exactly the algorithm
presented in the main part), as follows.

###### Proposition E.1.

For every CQ $q(\bar{x})$ that is acyclic and free/̄connex ayclic, enumerating
the answers $q(D)^{\ast}_{\mathbf{N}}$ is in $\mathsf{DelayC}_{\mathsf{lin}}$
for databases $D$ and sets of nulls $N\subseteq\mathsf{adom}(D)$ such that $D$
is chase-like with witness $D^{\prime}_{1},\dots,D^{\prime}_{n}$ where
$|\mathsf{adom}(D^{\prime}_{i})|$ does not depend on $D$ for $1\leq i\leq n$.

To prove Proposition E.1, let $q_{0}(\bar{x})$ be a CQ that is acyclic and
free/̄connex acyclic, $D_{0}$ a database over the same schema as $q_{0}$ that
is chase-like with witness $D^{\prime}_{1},\dots,D^{\prime}_{n}$ where
$|\mathsf{adom}(D^{\prime}_{i})|$ does not depend on $D$ for $1\leq i\leq n$.
Note that this notation is completely compatible with the one used in the main
part of the paper, only that there $D_{0}$ is the concrete chase-like database
$\mathsf{ch}^{q_{0}}_{\mathcal{O}}(D)$.

We first note that we can assume w.l.o.g. that the tuple $\bar{x}$ has no
repeated variables and that $q_{0}$ contains no constants. In fact, answer
enumeration in the general case can be reduced in time linear in $||D_{0}||$
to answer enumeration in this restricted case. We give the reduction for
removing constants. For every atom $R(\bar{t})$ in $q_{0}$ where $\bar{t}$
contains at least one constant, introduce a fresh relation symbol
$R_{\bar{t}}$ whose arity is the number of positions in $\bar{t}$ that have a
variable. Then replace $R(\bar{t})$ in $q_{0}$ with $R_{\bar{t}}(\bar{y})$
where $\bar{y}$ is obtained from $\bar{t}$ by removing all constants.
Furthermore, for each fact $R(\bar{c})$ in $D_{0}$ such that each constant $c$
that occurs in some position $i$ of $\bar{t}$ also occurs in position $i$ of
$\bar{c}$, add to $D_{0}$ the fact $R_{\bar{t}}(\bar{c}^{\prime})$ where
$\bar{c}^{\prime}$ is obtained from $\bar{c}$ by removing the constants in the
positions where $\bar{t}$ has a constant.

We can also assume $q_{0}$ to be connected. For assume that we have found an
enumeration algorithm for connected CQs that runs in
$\mathsf{DelayC}_{\mathsf{lin}}$. We can then enumerate
$q_{0}(D_{0})^{\ast}_{\mathbf{N}}$ in $\mathsf{DelayC}_{\mathsf{lin}}$ when
$q_{0}$ has maximal connected components $p_{0},\dots,p_{k}$, $k>0$, in the
following way. We first do preprocessing for all $p_{0},\dots,p_{k}$. We then
start an algorithm that enumerates the answers to $p_{0}$. After the first
answer was found, it calls the enumeration algorithm for $p_{1}$, which upon
finding an answer calls the enumeration algorithm for $p_{2}$, and so on. Only
when the innermost algorithm found an answer to $p_{k}$, the answers are
combined and output as an answer to $Q$. Note the algorithms for
$p_{1},\dots,p_{k}$ have to start from scratch multiple times which is
problematic since the data structures computed in the preprocessing phase are
modified in the enumeration phase and we cannot repeat preprocessing because
that would introduce a linear time delay into the enumeration phase. An easy
solution is as follows. When first enumerating the answers to $p_{k}$, we
store all of them in the form of a linked list. When we need to enumerate the
answers to $p_{k}$ again, we can just use that list without any preprocessing.
We do the same for the subqueries $p_{k-1}\cup p_{k}$, $p_{k-2}\cup
p_{k-1}\cup p_{k}$, and so on, which fixes the problem. The above argument
requires a polynomial amount of memory during the enumeration phase. There is,
however, an alternative approach that avoids this. Our algorithm is such that
the data structure $S$ computed in the preprocessing phase is modified in the
enumeration phase, resulting in a data structure $S^{\prime}$. However,
$S^{\prime}$ is such that it could have been used in place of $S$ after the
preprocessing phase without affecting the output of enumeration. This means
that the preprocessing can simply be skipped before restarting the enumeration
algorithm for a connected subquery.

Recall that from CQ $q_{0}(\bar{x})$ and database $D_{0}$, we have to
construct a CQ $q_{1}(\bar{x})$ and a database $D_{1}$ that satisfy Conditions
(i) to (iv) from the main part of the paper. Note that Condition (ii) implies
that $D_{1}$ is chase-like with a witness
$D^{\prime}_{1},\dots,D^{\prime}_{n}$ (not necessarily the same as for
$D_{0}$) such that $|\mathsf{adom}(D^{\prime}_{i})|$ does not depend on $D$
for $1\leq i\leq n$. he construction of $q_{1}$ and $D_{1}$ has been used many
times in the context of enumerating answers to conjunctive queries (without
ontologies) with constant delay. We give a rouch sketch and refer the
interested reader to (berkholz-enum-tutorial, ) for a very clear exposition of
the details. Exploiting that $q_{0}$ is acyclic and free/̄connex acyclic, it
is possible to first construct a generalized hypertree decomposition (GHD) of
$q_{0}$ of width 1 in which the answer variables constitute a connected
(‘connex’) prefix. Then a bottom-up pass over the GHD is made, manipulating
both $q_{0}$ and $D_{0}$ in a synchronized way. In particular, one introduces
a fresh relation symbol for each node of the GHD and duplicates facts in the
database accordingly, thus achieving self-join freeness. Moreover, one
achieves the progress condition by dropping facts from the database that
violate it. This also turns the GHD into a join tree. Finally, the quantified
variables can simply be dropped because the progress condition has already
been achieved. If $q_{0}(D_{0})$ is empty, then we find this out during the
construction of $q_{1}$ and $D_{1}$ as then all facts from the database that
use the relation symbol from the root of the GHD have been dropped. We then
return ‘end of enumeration’. The construction only needs time linear in
$||D_{0}||$.

See 5.3

###### Proof.

Recall that $D_{1}$ is chase-like with witness
$D^{\prime}_{1},\dots,D^{\prime}_{n}$. We iterate over $i=1,\dots,n$. For each
$i$, set $S=\mathsf{adom}(D^{\prime}_{i})\setminus N$ and iterate over all
pairs $(q,g)$ with $q$ a subtree of $q_{1}$ and $g:\mathsf{var}(q)\rightarrow
S\cup\\{\ast\\}$. Note that there are only constantly many such pairs: since
the OMQ is fixed, there are only constantly many subtrees $q$ of $q_{1}$, and
the arity of relations in schema $\mathbf{S}$ is bounded by a constant; since
$S$ is a guarded set in $D^{\prime}_{i}$ (by definition of chase-likeness), it
follows that the cardinality of $S$ is bounded by a constant as well, implying
that the same is true for the number of maps $g$.

We disregard pairs such that Conditions (1) or (2) of progress trees is
violated. Note that this can clearly be checked in constant time, and that
Condition (4) is in fact satisfied by choice of $g$. We then check whether
there is a homomorphism $\widehat{g}$ from $q$ to $D^{\prime}_{i}$ such that
for all $x,y\in\mathsf{var}(q)$,

  * •

$\widehat{g}(x)\in N$ if $g(x)=\ast$ and $\widehat{g}(x)=g(x)$ otherwise;

  * •

$\widehat{g}(x)=h(y)$ iff $g(x)=g(y)$.

If this is not the case, we disregard $(q,g)$. Otherwise, Condition (3) of
progress trees is satisfied. Note that we can check the existence of $h$ brute
force as there are only constantly many potential targets because
$|\mathsf{adom}(D^{\prime}_{i})|$ does not depend on $D$. We then add $(q,g)$
to $\mathsf{trees}(v,h)$ where $v$ is the root of $q$ and $h$ is the
restriction of $g$ to the predecessor variables in $v$.

Regarding the correctness of this construction, there are two important
observations. The first is that we really generate all progress trees despite
considering only homomorphisms $\widehat{g}$ into the databases
$D^{\prime}_{i}$ instead of into $D_{1}$ as a whole, as required by Condition
(3) of progress trees. This is guaranteed by the following claim.

Claim. Let $(q,g)$ be a progress tree and let $h$ be a homomorphism from $q$
to $D_{1}$ such that for all $x\in\mathsf{var}(q)$, $h(x)\in N$ if $g(x)=\ast$
and $h(x)=g(x)$ otherwise. Then $h$ is a homomorphism from $q$ to
$D^{\prime}_{i}$ for some $i\in\\{1,\dots,n\\}$.

_Proof of claim._ Let $v_{0}=R_{0}(\bar{y}_{0})$ be the root of $T_{q}$. Then
clearly there is an $i$ such that $R_{0}(h(\bar{y}_{0}))\in D^{\prime}_{i}$.
We show that $h$ is a homomorphism from $q$ to $D^{\prime}_{i}$.

More precisely we prove by induction on the depth of $v$ in $T_{q}$ that that
for all $v=R(\bar{y})\in V_{q}$, $R(h(\bar{y}))\in D^{\prime}_{i}$. The
induction start is trivial by choice of $D^{\prime}_{i}$. So let $v\in V_{q}$
be a non-root node. By Condition (2) of progress trees, $v$ contains a
predecessor variable $x$ with $g(x)=\ast$. Thus $h(x)\in N$. Let
$v^{\prime}=R^{\prime}(\bar{y}^{\prime})$ be the predecessor of $v$ in
$T_{q}$. By induction hypothesis, $R^{\prime}(h(\bar{y}^{\prime}))\in
D^{\prime}_{i}$. Since by definition of ‘chase-like’
$\mathsf{adom}(D^{\prime}_{i})\cap\mathsf{adom}(D^{\prime}_{j})\cap
N=\emptyset$, this and $h(x)\in N$ yields $R(h(\bar{y}))\in D^{\prime}_{i}$,
as required. This finishes the proof of the claim.

The second observation is that we must be careful to avoid duplicates as the
same $(q,g)$ can be constructed for $D_{i}$, $D^{\prime}_{j}$ with $i\neq j$,
when $\mathsf{adom}(D^{\prime}_{i})\setminus N$ and
$\mathsf{adom}(D^{\prime}_{j})\setminus N$ overlap. To identify duplicates, we
use a lookup table that stores a Boolean value for every progress tree
$(q,g)$, indicating whether we have already seen this tree or not. Note that a
progress tree $(q,g)$ can essentially be represented by a list of constants
from $\mathsf{adom}(D_{1})$ of constant length, and by the remarks on RAMs
under the uniform cost model in Section 2 we can access and modify such a
table in constant time.

It remains to sort the lists $\mathsf{trees}(v,h)$, each of which is of length
$O(|\mathsf{adom}(\mathcal{D}_{1})|)$, into the desired order in overall
linear time. Recall from Section 2 that sorting a list of short lists equipped
with a strict weak order is possible on a RAM in linear time. Now, a progress
tree $(q,g)$ is essentially a short list. We can use $q$ as the first element
of the list (only constantly many choices), fix a total order
$z_{1},\dots,z_{\ell}$ on the variables in $q$, and use
$g(z_{1}),\dots,g(z_{\ell})$ as the remaining list. A strict weak order on
progress trees is then defined by ‘$\prec_{\mathsf{db}}$’. If we now sort the
progress trees in $\mathsf{trees}(v,h)$ viewed as short lists, then we attain
the required order, that is, $(q,g)\prec_{\mathsf{db}}(q^{\prime},g^{\prime})$
implies that $(q,g)$ occurs before $(q^{\prime},g^{\prime})$ in the list.
There are linearly many lists $\mathsf{trees}(v,h)$ to be sorted, each in
linear time, but we still attain overall linear time since each progress tree
occurs in only one list and thus the total number of items to be sorted
(across all lists) is bounded by $O(||D_{1}||)$.

It remains to prove the ‘moreover’ part. Let $v$ and $h$ be relevant. We have
to show that there is a progress tree $(q,g)$ with root $v$ such that
$g(\bar{z})=h(\bar{z})$. We build this tree together with a homomorphism
$h^{\prime}$ that witnesses Point (3) of the definition of progress trees. We
start with $q$ consisting only of the single node $v$. Since $v$ and $h$ are
relevant, $h$ extends to a homomorphism from $v$ to $D_{1}$. We use this
homomorphism both for (the initial) $g$ and $h^{\prime}$. We then exhaustively
extend $q$, $g$, and $h^{\prime}$ as follows. If $v^{\prime}$ is an atom in
$q$ such that $g$ maps at least one variable in $v^{\prime}$ to ‘$\ast$’ and
$v^{\prime\prime}$ is a successor of $v$ in $T_{1}$, then include $v^{\prime}$
in $q$. By the progress condition, we can extend the homomorphism $h^{\prime}$
to the extended $q$. Extend $g$ accordingly, using ‘$\ast$’ in place of null
constants. It can be verified that Conditions (1) to (4) of progress trees are
satisfied. In particular, Condition (4) is: due to the shape of chase-like
databases and since $q_{1}$ is connected, all constants in the range of $g$
are from the guarded set $h(\bar{x})$, with $\bar{x}$ the variables in $v$. ∎

See 5.4

###### Proof.

Assume to the contrary that some list $\mathsf{trees}(v,h)$, with $v,h$
relevant, becomes empty when $\mathsf{prune}(h^{\prime})$ is called. Assume
that among the progress trees removed during this call, $(q,g)$ is a minimal
progress tree regarding ‘$\prec_{\mathsf{db}}$’. Since $(q,g)$ was still on
$\mathsf{trees}(v,h)$ before the call $\mathsf{prune}(h^{\prime})$, no
progress tree $(q^{\prime},g^{\prime})$ with
$(q^{\prime},g^{\prime})\prec_{\mathsf{db}}(q,g)$ was removed in any previous
pruning step. To obtain a contradiction, it thus suffices to argue that the
initial list $\mathsf{trees}(v,h)$ contains a progress tree
$(q^{\prime},g^{\prime})$ with
$(q^{\prime},g^{\prime})\prec_{\mathsf{db}}(q,g)$.

We extract the tree $(q^{\prime},g^{\prime})$ from $h^{\prime}$. Let
$q^{\prime}\subseteq q_{1}$ be smallest so that $v\in q^{\prime}$ and if $u\in
q^{\prime}$ and $u^{\prime}$ is a successor of $u$ in $T_{1}$ such that
$h(x)\in N$ for at least one predecessor variable in $u^{\prime}$, then
$u^{\prime}\in q^{\prime}$. We define $g^{\prime}$ to be $h^{\prime}$
restricted to the variables in $q^{\prime}$.

Note that we must have $q^{\prime}\subseteq q$. If this is not the case, in
fact, then by definition of $q^{\prime}$ and since $q$ is a progress tree,
there is an atom $u$ in $q$ such that $g$ maps all predecessor variables in
$u$ to $\mathsf{adom}(D_{1})$ while $g^{\prime}$ maps at least one predecessor
variable in $u$ to ‘$\ast$’. But this implies that the test
‘$(q,g)\succ_{\mathsf{db}}(q,h^{\prime}|_{\mathsf{var}(q)})$’ made in
$\mathsf{enum}(h^{\prime})$ fails, in contradiction to $(q,g)$ being removed
during that call.

If $q^{\prime}\subsetneq q$, then
$(q^{\prime},g^{\prime})\prec_{\mathsf{db}}(q,g)$ and we are done. Otherwise,
however, the test
‘$(q,g)\succ_{\mathsf{db}}(q,h^{\prime}|_{\mathsf{var}(q)})$’ made in
$\mathsf{enum}(h^{\prime})$ guarantees that Conditions (a)-(d) from the
definition of ‘$\prec_{\mathsf{db}}$’ are satisfied for
$(q^{\prime},g^{\prime})$ and $(q,g)$, thus again
$(q^{\prime},g^{\prime})\prec_{\mathsf{db}}(q,g)$. ∎

We now work towards a proof of Proposition 5.5. Every partial answer
$\bar{a}^{\ast}$ to $q_{1}$ on $D_{1}$ can be seen as a map
$h_{\bar{a}^{\ast}}:\mathsf{var}(q_{1})\rightarrow(\mathsf{adom}(D_{1})\setminus
N)\cup\\{\ast\\}$ in an obvious way and vice versa. Let $\bar{a}^{\ast}$ be a
partial answer. We say that a progress tree $(q,g)$ is _realized_ in
$\bar{a}^{\ast}$ if $h_{\bar{a}^{\ast}}(x)=g(x)$ for all
$x\in\mathsf{var}(q)$.

###### Lemma E.2.

Without pruning, the algorithm outputs the (not necessarily minimal) partial
answers to $q_{1}$ on $D_{1}$, without repetition. Moreover, the enumeration
order respects ‘$\prec$’, that is, if partial answer $\bar{a}^{\ast}$ is
output before partial answer $\bar{b}^{\ast}$, then
$\bar{b}^{\ast}\not\prec\bar{a}^{\ast}$.

###### Proof.

Let $\bar{a}^{\ast}$ be a partial answer to $q_{1}$ on $D_{1}$. We argue that
there is a path in the recursion tree generated by the initial call
$\mathsf{enum}(\mathsf{nextat}_{h_{0}}(v_{0}))$ that leads to $\bar{a}^{\ast}$
being output. This path can be identified by choosing, for each call
$\mathsf{enum}(v,h)$, a recursive call made during it that identifies the
successor on the path. Let $\mathsf{enum}(v,h)$ be such a call, and let
$h_{\bar{a}^{\ast}}(v)=R(\bar{c})$. Using Condition (2) of progress trees, it
can be shown in a straightforward way that the algorithm satisfies the
following invariant:

  1. ($*$)

In each call $\mathsf{enum}(v^{\prime},h^{\prime})$, all predecessor variables
in $v^{\prime}$ are mapped to database constants.

Hence, the same is true for all predecessor variables $\bar{z}$ in $v$. We
identify a candidate tree $(q,g)\in\mathsf{trees}(v,h|_{\bar{z}})$ as outlined
after the definition of candidate trees. More precisely, choose
$V_{q}\subseteq V_{1}$ to be the smallest set that contains $v$ and such that
if $u\in V_{q}$ and $u^{\prime}$ is a successor of $u$ in $T_{1}$ such that
$h_{\bar{a}^{\ast}}(x)=\ast$ for at least one predecessor variable in
$u^{\prime}$, then $u^{\prime}\in V_{q}$. This defines a subtree $q$ of
$q_{1}$, and for $g$ the restriction of $h_{\bar{a}^{\ast}}$ to the variables
in $q$, it can be verified that $(q,g)\in\mathsf{trees}(v,h|_{\bar{z}})$. This
identifies the recursive call made during $\mathsf{enum}(v,h)$ that we follow
on the path towards the output of $\bar{a}^{\ast}$. It can be verified that
the map $h$ built up on this path is exactly $h_{\bar{a}^{\ast}}$, and thus
$\bar{a}^{\ast}$ is indeed output at the end of the path.

Now assume that the algorithm outputs a tuple $\bar{a}^{\ast}$ and let
$h_{\bar{a}^{\ast}}:\mathsf{var}(q_{1})\rightarrow(\mathsf{adom}(D_{1})\setminus
N)\cup\\{\ast\\}$ be the associated map. We argue that we can obtain from
$h_{\bar{a}^{\ast}}$ a homomorphism $h$ from $q_{1}$ to $D_{1}$ such that for
all $x\in\bar{x}$, (i) $h_{\bar{a}^{\ast}}(x)\in\mathsf{adom}(D_{1})$ implies
$h(x)=h_{\bar{a}^{\ast}}(x)$ and (ii) $h_{\bar{a}^{\ast}}(x)=\ast$ implies
$h(x)\in N$. Consequently, $\bar{a}^{\ast}$ is a partial answer to $q_{1}$ on
$D_{1}$. Let
$\mathsf{enum}(v_{0},h_{0}),\dots,\mathsf{enum}(v_{\ell-1},h_{\ell-1})$ be the
sequence of recursive calls that led to the output of $\bar{a}^{\ast}$ (during
the last call). Note that $v_{0},\dots,v_{\ell-1}$ are not necessarily all
nodes of $V_{1}$ due to the use of progress trees and $\mathsf{nextat}$. We
define a sequence of partial mappings $h^{\prime}_{0}\subseteq\cdots\subseteq
h^{\prime}_{\ell}$ from $\mathsf{var}(q_{1})$ to $\mathsf{adom}(D_{1})$ that
for all $x\in\mathsf{var}(q_{1})$ on which they are defined satisfy Conditions
(i) and (ii). Then $h^{\prime}_{\ell}$ will be a total function and thus the
desired homomorphism $h$ from $q_{1}$ to $D_{1}$. Start with setting
$h^{\prime}_{0}=\emptyset$. Now assume that $h^{\prime}_{i}$ is already
defined and consider the recursive call $\mathsf{enum}(v_{i},h_{i})$. By
definition of the algorithm, there is a progress tree
$(q,g)\in\mathsf{trees}(v_{i},h_{i}|_{\bar{z}})$, with $\bar{z}$ the
predecessor variables of $v_{i}$, such that $h_{\bar{a}^{\ast}}(z)=g(z)$ for
all $z\in\mathsf{var}(q)$. By Property (3) of progress trees, there is a
homomorphism $g^{\prime}$ from $q$ to $D_{1}$ such that for all
$x\in\mathsf{var}(q)$, $g^{\prime}(x)\in N$ if $g(x)=\ast$ and
$g^{\prime}(x)=g(x)$ otherwise. We define $h^{\prime}_{i+1}=h^{\prime}_{i}\cup
g^{\prime}$. It can be verified that the map $h=h^{\prime}_{\ell}$ is indeed
the desired homomorphism from $q_{1}$ to $D_{1}$.

We next argue that there are no repetitions. Consider again the recursion tree
generated by the initial call $\mathsf{enum}(\mathsf{nextat}_{h_{0}}(v_{0})$,
and consider two paths in the tree that lead to the output of partial answers
$\bar{a}_{1}^{\ast}$ and $\bar{a}_{2}^{\ast}$. Let $\mathsf{enum}(v,h)$ be the
call in which the two paths diverge, that is, $h_{\bar{a}_{1}^{*}}$ and
$h_{\bar{a}_{2}^{*}}$ both agree with $h$ on the variables on which $h$ is
defined, but during the call $\mathsf{enum}(v,h)$ the two paths follow
recursive calls made for different
$(p_{1},g_{1}),(p_{2},g_{2})\in\mathsf{trees}(v,h|_{\bar{z}})$. We argue that
then, $h_{\bar{a}_{1}^{*}}$ and $h_{\bar{a}_{2}^{*}}$ must also be different,
and thus so are $\bar{a}_{1}^{\ast}$ and $\bar{a}_{2}^{\ast}$. This is clear
if $p_{1}=p_{2}$ as this implies $g_{1}\neq g_{2}$ and $h$ is extended by
setting $h=h\cup g_{1}$ and $h=h\cup g_{2}$, respectively. Now assume that
$p_{1}\neq p_{2}$. Then there must be nodes $u,u^{\prime}$ in $T_{q_{1}}$ with
$u^{\prime}$ a successor of $u$ and such that $u$ is part of $T_{p_{1}}$ and
$T_{p_{2}}$, but $u^{\prime}$ is part of $T_{p_{1}}$, but not part of
$T_{p_{2}}$ (or vice versa). By Condition (2) of progress trees, $g_{1}$ maps
some predecessor variable of $u^{\prime}$ to $\ast$, but $g_{2}$ does not.
Consequently, the extensions $h=h\cup g_{1}$ and $h=h\cup g_{2}$ differ on
some variable on which they are both defined.

For the ‘moreover’ part, let $\bar{a}^{\ast},\bar{b}^{\ast}$ be partial
answers with $\bar{b}^{\ast}\prec\bar{a}^{\ast}$. Since $\bar{a}^{\ast}$ is a
partial answer, there must be a homomorphism $h_{\bar{a}}$ from $q_{1}$ to
$D_{1}$ such that for all $x\in\mathsf{var}(q_{1})$,
$h_{\bar{a}}(x)=h_{\bar{a}^{\ast}}(x)$ if $h_{\bar{a}^{\ast}}(x)\notin N$ and
$h_{\bar{a}}(x)\in N$ if $h_{\bar{a}^{\ast}}(x)=\ast$, and analogously for
$\bar{b}^{\ast}$ and a homomorphism $h_{\bar{b}}$. Since
$\bar{b}^{\ast}\prec\bar{a}^{\ast}$, there must further be a variable $x_{0}$
with $h_{\bar{b}^{\ast}}(x_{0})$ a database constant and
$h_{\bar{a}^{\ast}}(x_{0})=\ast$. Let $v\in V_{1}$ be the first atom that
contains such an $x_{0}$ in a pre-order tree walk over $T_{1}$. Let
$(q_{a},g_{a})$ be the progress tree realized in $\bar{a}^{\ast}$ with $v\in
q_{a}$, and let $u$ be the root of $q_{a}$. Then
$h_{\bar{a}^{\ast}}(z)\neq\ast$ for all predecessor variables $z$ in $u$.
Since $\bar{b}^{\ast}\prec\bar{a}^{\ast}$, the same is true for
$h_{\bar{b}^{\ast}}$. Due to Condition (2) of progress trees, it follows that
there is a progress tree $(q_{b},g_{b})$ realized in $\bar{b}^{\ast}$ such
that the root of $q^{\prime}$ is $u$. From
$\bar{b}^{\ast}\prec\bar{a}^{\ast}$, it follows that $V_{q_{a}}\subsetneq
V_{q_{b}}$ or $V_{q_{a}}=V_{q_{b}}$ and $g_{b}(x)=\ast$ implies
$g_{a}(x)=\ast$ for all $x\in\mathsf{var}(q_{a})$. From
$h_{\bar{b}^{\ast}}(x_{0})\neq\ast$ and $h_{\bar{a}^{\ast}}(x_{0})=\ast$, it
further follows that $g_{b}(x_{0})\neq\ast$ and $g_{a}(x_{0})=\ast$.
Consequently, $(q_{a},g_{a})$ is before $(q_{b},g_{b})$ in the list
$\mathsf{trees}(u,h_{\bar{z}})$ where
$h_{\bar{z}}=h_{\bar{b}^{\ast}}|_{\bar{z}}=h_{\bar{a}^{\ast}}|_{\bar{z}}$ and
thus the recursive call that leads to the output of $h_{\bar{b}^{\ast}}$ takes
place before the recursive call that leads to the output of
$h_{\bar{a}^{\ast}}$. ∎

Let $\bar{a}^{\ast},\bar{b}^{\ast}$ be partial answers to $q_{1}$ on $D_{1}$.
We say that $\bar{a}^{\ast}$ _prunes_ $\bar{b}^{\ast}$ if there is a node
$v=R(\bar{y})\in V_{1}$ with predecessor variables $\bar{z}$ and a progress
tree $(q,g)\in\mathsf{trees}(v,h_{\bar{b}^{\ast}}|_{\bar{z}})$ that is
realized in $\bar{b}^{\ast}$ and removed from
$\mathsf{trees}(v,h_{\bar{b}^{\ast}}|_{\bar{z}})$ when $\bar{a}^{\ast}$ is
output.

See 5.5

###### Proof.

We first argue that whenever a partial answer is pruned, then it is not a
minimal partial answer. Assume that partial answer $\bar{a}^{\ast}$ prunes
partial answer $\bar{b}^{\ast}$. Then there is a $v\in V_{1}$ with predecessor
variables $\bar{z}$ and a progress tree
$(q,g)\in\mathsf{trees}(v,h_{\bar{b}^{\ast}}|_{\bar{z}})$ such that $(q,g)$ is
realized in $\bar{b}^{\ast}$ and removed from
$\mathsf{trees}(v,h_{\bar{b}^{\ast}}|_{\bar{z}})$ when $\bar{a}^{\ast}$ is
output. Thus $(q,h_{\bar{a}^{\ast}}|_{\bar{z}})\prec_{\mathsf{db}}(q,g)$. We
call the variables in $\bar{z}$ _root variables_ of $q$. A _fringe variable_
of $q$ of is a variable $x$ that occurs in a leaf $u$ of $T_{q}$ that has a
successor $u^{\prime}$ in $T_{1}$ in which $x$ also occurs. We observe that

  * ($*$)

for all variables $x$ that are root variables or fringe variables of $q$,
$h_{\bar{a}^{\ast}}(x)=g(x)$.

In fact, this follows from
$(q,h_{\bar{a}^{\ast}}|_{\bar{z}})\prec_{\mathsf{db}}(q,g)$ and the fact that,
by Conditions 1 and 2 of progress trees, $g(x)\neq\ast$ for all variables $x$
mentioned in ($*$).

Let ${\bar{c}}^{\ast}$ be obtained from $\bar{b}^{\ast}$ by setting
$h_{{\bar{c}}^{\ast}}(x)=h_{\bar{a}^{\ast}}(x)$ for all $x\in\mathsf{var}(q)$.
It can be verified that ${\bar{c}}^{\ast}$ is a partial answer to $q_{1}$ on
$D_{1}$. In particular, there must be a homomorphism $h_{\bar{b}}$ from
$q_{1}$ to $D_{1}$ such that $h_{\bar{b}^{\ast}}(x)=\ast$ iff
$h_{\bar{b}}(x)\in N$ for all $x\in\mathsf{var}(q_{1})$. By Condition 3 of
progress trees, there is a homomorphism $h$ from $q$ to $D_{1}$ such that
$h(x)\in N$ if $h_{\bar{b}^{\ast}}=\ast$ and $h(x)=h_{\bar{b}^{\ast}}(x)$
otherwise. Let $h_{\bar{c}}$ be obtained from $h_{\bar{b}}$ by setting
$h_{\bar{c}}(x)=h(x)$ for all $x\in\mathsf{var}(q)$. Due to ($*$),
$h_{\bar{c}}$ is a homomorphism, and thus ${\bar{c}}^{\ast}$ is a partial
answer to $q_{1}$ on $D_{1}$. Moreover, the construction of $\bar{c}^{*}$
yields ${\bar{c}}^{\ast}\prec_{\mathsf{db}}\bar{b}^{\ast}$, and thus we have
shown that $\bar{b}^{\ast}$ is not a minimal partial answer.

We next show that if a partial answer is not a minimal partial answer, then it
is pruned. Assume that $\bar{b}^{\ast}$ is not a minimal partial answer. Then
there is a minimal partial answer $\bar{a}^{\ast}$ with
$\bar{a}^{\ast}\prec\bar{b}^{\ast}$. We argue that $\bar{a}^{\ast}$ prunes
$\bar{b}^{\ast}$. By Lemma E.2, $\bar{a}^{\ast}$ is output before
$\bar{b}^{\ast}$ when no pruning takes place. Since
$\bar{a}^{\ast}\prec\bar{b}^{\ast}$ , there is an
$x_{0}\in\mathsf{var}(q_{1})$ with $h_{\bar{a}^{\ast}}(x_{0})$ a database
constant and $h_{\bar{b}^{\ast}}(x_{0})=\ast$. Let $v\in V_{1}$ be the first
node encountered in a pre-order tree walk over $T_{1}$ that contains $x_{0}$,
and let $(q,g)$ be the progress tree realized in $\bar{b}^{\ast}$ with $v\in
q$. Further let $u$ be the root of $q$ and $\bar{z}$ be the predecessor
variables of $u$. It follows from $\bar{a}^{\ast}\prec\bar{b}^{\ast}$ and the
fact that $x_{0}$ occurs in $v$ occurs in $q$ that
$(q,g)\succ_{\mathsf{db}}(q,h_{\bar{a}^{\ast}}|_{\mathsf{var}(q)})$. Thus
$(g,q)$ is removed from $(q,g)\in\mathsf{trees}(u,h)$, with
$h=h_{\bar{a}^{\ast}}|_{\bar{z}}=h_{\bar{b}^{\ast}}|_{\bar{z}}$, when
$\bar{a}^{\ast}$ is output (which is the case since $\bar{a}^{\ast}$ is a
minimal partial answer and thus not pruned), and therefore $\bar{a}^{\ast}$
prunes $\bar{b}^{\ast}$. ∎

##  Appendix F Proofs for Section 6

In the main part of the paper, we have declared the goal to be the enumeration
of $q_{0}(\mathsf{ch}^{q_{0}}_{\mathcal{O}}(D))^{\mathcal{W}}_{\mathbf{N}}$.
Here, we actually prove something slightly more general, as follows (this
parallels what is done in Appendix E.1).

###### Proposition F.1.

For every CQ $q(\bar{x})$ that is acyclic and free/̄connex acyclic,
enumerating the answers $q(D)^{\mathcal{W}}_{\mathbf{N}}$ is in
$\mathsf{DelayC}_{\mathsf{lin}}$ for databases $D$ and sets of nulls
$N\subseteq\mathsf{adom}(D)$ such that $D$ is chase-like with witness
$D_{1},\dots,D_{n}$ where $|\mathsf{adom}(D_{i})|$ does not depend on $D$ for
$1\leq i\leq n$.

To prove Proposition F.1, we use as a blackbox the
$\mathsf{DelayC}_{\mathsf{lin}}$ algorithm for the enumeration of minimal
partial answers with a single wildcard presented in the previous section. In
addition, we use a $\mathsf{DelayC}_{\mathsf{lin}}$ algorithm for all-testing
of (not necessarily minimal) partial answers with multi-wildcards.

###  F.1. All-Testing Partial Answers with Multi-Wildcards

We show that all-testing of (not necessarily minimal) partial answers with
multi-wildcards is in $\mathsf{DelayC}_{\mathsf{lin}}$. The following
proposition makes this precise.

###### Proposition F.2.

For every CQ $q(\bar{x})$ that is acyclic and free/̄connex acyclic, all-
testing of the answers $q(D)^{\mathcal{W},\not\prec}_{\mathbf{N}}$ is in
$\mathsf{DelayC}_{\mathsf{lin}}$ for databases $D$ and sets of nulls
$N\subseteq\mathsf{adom}(D)$ such that $D$ is chase-like with witness
$D_{1},\dots,D_{n}$ where $|\mathsf{adom}(D_{i})|$ does not depend on $D$ for
$1\leq i\leq n$.

We remind the reader that when
$Q(\bar{x})=(\mathcal{O},\mathbf{S},q)\in(\mathbb{G},\text{CQ})$,
$D=\mathsf{ch}^{q}_{\mathcal{O}}(D_{0})$, and
$N=\mathsf{adom}(D)\setminus\mathsf{adom}(D_{0})$, then the set of partial
answers with multi-wildcards to $Q$ on $D_{0}$ is not necessarily identical to
$q(D)^{\mathcal{W},\not\prec}_{\mathbf{N}}$. In fact, one can show that for
the former all-testing in $\mathsf{DelayC}_{\mathsf{lin}}$ is not possible
unless BMM can be done in quadratic time, and thus it is vital that we work
with $q(D)^{\mathcal{W},\not\prec}_{\mathbf{N}}$.

To prove Proposition F.2, fix a CQ $q(\bar{x})$ over schema $\mathbf{S}$ that
is acyclic and free/̄connex acyclic, and let $D$ be an $\mathbf{S}$-database
and $N$ a set of nulls satisfying the conditions from Proposition F.2. In time
linear in $||D||$ we can convert $q$ and $D$ into a CQ $q^{\prime}(\bar{x})$
without quantified variables and a database $D^{\prime}$ such that $D$ and
$D^{\prime}$ have the same Gaifman graph and $q(D)=q^{\prime}(D^{\prime})$,
and thus also
$q(D)^{\mathcal{W},\not\prec}_{\mathbf{N}}=q^{\prime}(D^{\prime})^{\mathcal{W},\not\prec}_{\mathbf{N}}$.
Note that we achieve this as part of the preprocessing carried out in Section
5, an outline of how to do this is given in Appendix 5.2 and details are in
(berkholz-enum-tutorial, ). Since $D$ and $D^{\prime}$ have the same Gaifman
graph, $D^{\prime}$ and $N$ also satisfy the conditions from Proposition F.2
and we may in fact simply assume that $q$ contains no quantified variables.

Let $T_{q}=(V_{q},E_{q})$ be a join tree for $q$. A _multi-progress tree_ is a
pair $(q^{\prime},g)$ with $q^{\prime}$ a subtree of $q$ (as defined in
Section 5) and $g:\mathsf{var}(q)\rightarrow(\mathsf{adom}(D)\setminus
N)\cup\mathcal{W}$ a map such that the following conditions are satisfied:

  1. (1)

$g(x)\notin\mathcal{W}$ for every predecessor variable $x$ in the root of
$T_{q^{\prime}}$;

  2. (2)

if $v\in V_{q^{\prime}}$ and $v^{\prime}$ is a successor of $v$ in $T_{q}$,
then $v^{\prime}\in V_{q^{\prime}}$ if and only if $g(x)\in\mathcal{W}$ for
some predecessor variable $x$ in $v^{\prime}$;

  3. (3)

the constants in the range of $g$ form a guarded set in $D$.

Recall that $D$ is chase-like with witness $D_{1},\dots,D_{n}$. A set
$S=\\{(q_{1},g_{1}),\dots,(q_{\ell},g_{\ell})\\}$ of multi-progress trees is
_valid_ if there is a homomorphism $h$ from $q_{1}\cup\cdots\cup q_{\ell}$ to
some database $D_{i}$, with $1\leq i\leq n$, that is _compatible_ with $g$,
that is, for all
$x,y\in\mathsf{var}(q_{1})\cup\cdots\cup\mathsf{var}(q_{\ell})$,

  1. (a)

$h(x)\in N$ if $g(x)\in\mathcal{W}$ and $h(x)=g(x)$ otherwise;

  2. (b)

$g(x)=g(y)$ implies $h(x)=h(y)$.

Our $\mathsf{DelayC}_{\mathsf{lin}}$ algorithm for all-testing
$q(D)^{\mathcal{W},\not\prec}_{\mathbf{N}}$ uses as a black box a
$\mathsf{DelayC}_{\mathsf{lin}}$ algorithm $A_{q^{\prime}}$ for all-testing of
$q^{\prime}(D)$, for every subquery $q^{\prime}(\bar{x}^{\prime})$ of
$q(\bar{x})$, that is, for every CQ $q^{\prime}(\bar{x}^{\prime})$ that can be
obtained from $q$ by dropping atoms. Note that all of these $q^{\prime}$
contain no quantified variables and are thus free-connex acyclic, implying
that all-testing $q^{\prime}(D)$ is possible in
$\mathsf{DelayC}_{\mathsf{lin}}$ by Proposition 4.2. There are clearly only
constantly many such subqueries.

In the preprocessing phase, we run the preprocessing phases of all the
algorithms $A_{q^{\prime}}$, $q^{\prime}$ a subquery of $q$. In addition, we
precompute a lookup table $\mathsf{nullhom}$ that stores a Boolean value for
all sets $S$ of multi-progress trees that contain at most $|\mathsf{var}(q)|$
such trees. Let $S=\\{(q_{1},g_{1}),\dots,(q_{\ell},g_{\ell})\\}$. The stored
value is 1 if $S$ is valid and 0 otherwise. Such a lookup table can be
accessed and updated in $O(1)$ time on a RAM. The proof of the following is
similar to that of Lemma 5.3.

###### Lemma F.3.

The lookup table $\mathsf{nullhom}$ can be computed in time linear in $||D||$.

###### Proof.

To compute the table, we iterate over the databases $D_{1},\dots,D_{n}$. For
each $D_{i}$, set $G=\mathsf{adom}(D_{i})\setminus N$ and iterate over all
sets $S$ of pairs $(q^{\prime},g)$ with $q^{\prime}$ a subtree of $q$ and
$g:\mathsf{var}(q^{\prime})\rightarrow G\cup\mathcal{W}$, such that there are
at most $|q|$ pairs in $S$ and Conditions (1) and (2) of multi-progress trees
is satisfied for all pairs in $S$. Condition (3) is satisfied since $G$ is a
guarded set in $D_{i}$. This also implies that its cardinality is bounded by a
constant and thus there are only constantly many pairs $(q^{\prime},g)$ of the
described form and consequently also only constantly many sets $S$. Let
$S=\\{(q_{1},g_{1}),\dots,(q_{\ell},g_{\ell})\\}$. We then check whether there
is a homomorphism $h$ from $q_{1}\cup\cdots\cup q_{\ell}$ to $D_{i}$ that is
compatible with $g_{1},\dots,g_{\ell}$. If this is the case, we set
$\mathsf{nullhom}(S)=1$. Otherwise, $\mathsf{nullhom}(S)=1$ as all memory is
initialized with value 0 in our machine model. Note that we can check the
existence of $h$ brute force: there are only constantly many potential targets
because $|\mathsf{adom}(D_{i})|$ does not depend on $D$. ∎

e now describe the testing phase of our algorithm. Assume that a multi-
wildcard tuple $\bar{a}^{\mathcal{W}}$ of length $|\bar{x}|$ is to be tested.
We may first check whether wildcards are used in the required way and answer
‘no’ if this is not the case. More precisely, we check that the wildcards in
$\bar{a}^{\mathcal{W}}$ are a prefix of the ordered set
$\mathcal{W}=\\{\ast_{1},\ast_{2},\dots\\}$ and that multiple occurrences of
the same variable in $\bar{x}$ are matched by multiple occurrences of the same
wildcard in $\bar{a}^{\mathcal{W}}$. If this is the case, we may view
$\bar{a}^{\mathcal{W}}$ as a map
$h_{\bar{a}^{\mathcal{W}}}:\mathsf{var}(q)\rightarrow(\mathsf{adom}(D)\setminus
N)\cup\mathcal{W}$ in the obvious way. We may then check that the wildcards in
$\bar{a}^{\mathcal{W}}$ respect the order of the answer variables in
$\bar{x}$, that is, if the first occurrence of $x$ is before the first
occurrence of $x^{\prime}$ in $\bar{x}$,
$h_{\bar{a}^{\mathcal{W}}}(x)=\ast_{i}$, and
$h_{\bar{a}^{\mathcal{W}}}(x^{\prime})=\ast_{j}$, then $i<j$.

We say that a multi-progress tree $(q^{\prime},g)$ is _realized_ in
$\bar{a}^{\mathcal{W}}$ if $h_{\bar{a}^{\mathcal{W}}}(x)=g(x)$ for all
$x\in\mathsf{var}(q^{\prime})$. Let $T$ be the set of all multi-progress trees
realized in $\bar{a}^{\mathcal{W}}$ and let $\sim$ be the smallest equivalence
relation on $T$ such that $(q_{1},g_{1})\sim(q_{2},g_{2})$ if there are
variables $x_{1}\in\mathsf{var}(q_{1})$ and $x_{2}\in\mathsf{var}(q_{2})$ such
that $g_{1}(x_{1})=g_{2}(x_{2})\in\mathcal{W}$. We consider each equivalence
class $S\subseteq T$ of ‘$\sim$’ and check whether $S$ is valid by testing if
$\mathsf{nullhom}(S)=1$. If any of the checks fails, we answer ‘no’. Since at
most $|\mathsf{var}(q)|$ (and thus only constantly many) multi-progress trees
may be realized in $\bar{a}^{\mathcal{W}}$, the required checks can be done in
constant time.

We then do one last check. Let $q^{\prime}$ be the subquery of $q$ that
consists of all atoms $\alpha$ such that for all variables $x$ in $\alpha$,
$h_{\bar{a}^{\mathcal{W}}}(x)\notin\mathcal{W}$. Further let $\bar{a}$ be the
tuple over $\mathsf{adom}(D)\setminus N$ obtained from
$\bar{a}^{\mathcal{W}}=(a^{\mathcal{W}}_{1},\dots,a^{\mathcal{W}}_{|\bar{x}|})$
by dropping $a^{\mathcal{W}}_{i}$ whenever the $i$-th position in $\bar{x}$ is
an answer variable that is not in $\mathsf{var}(q^{\prime})$. We then use
algorithm $A_{q^{\prime}}$ to test whether $\bar{a}\in q^{\prime}(D)$ and
return the result. The following lemma asserts that the returned answer is
correct, which finishes the proof of Proposition 4.2.

###### Lemma F.4.

$\bar{a}^{\mathcal{W}}\in q(D)_{\mathbf{N}}^{\mathcal{W}}$ iff the testing
phase returns ‘yes’.

###### Proof.

‘if’. Assume that the testing phase returns ‘yes’. Then $\bar{a}\in
q^{\prime}(D)$ and thus we may view $\bar{a}$ as a homomorphism $h_{\bar{a}}$
from $q^{\prime}$ to $D$ in the obvious way. Note that the range of
$h_{\bar{a}}$ falls within $\mathsf{adom}(D)\setminus N$ since all constants
in $\bar{a}$ are from this set. We next extend $h$ by considering one
equivalence class $S\subseteq T$ of ‘$\sim$’ at the time. Let
$S=\\{(q_{1},g_{1}),\dots,(q_{\ell},g_{\ell})\\}$. Since the testing phase has
returned ‘yes’, $S$ is valid and thus there is a homomorphism $h_{S}$ from
$q_{1}\cup\cdots\cup q_{\ell}$ to some $D_{i}$, with $1\leq i\leq n$, that is
compatible with $g=g_{1}\cup\cdots\cup g_{n}$. Taking the union of
$h_{\bar{a}}$ and all the homomorphisms $h_{S}$ yields a homomorphism $h$ from
$q$ to $D$ that yields an answer $\bar{b}\in q(D)$ such that
$\bar{a}^{\mathcal{W}}$ is obtained from $\bar{b}$ by replacing nulls with
wildcards from $\mathcal{W}$. Consequently, $\bar{a}^{\mathcal{W}}\in
q(D)_{\mathbf{N}}^{\mathcal{W}}$.

‘only if’. Assume that $\bar{a}^{\mathcal{W}}\in
q(D)_{\mathbf{N}}^{\mathcal{W}}$. Then there is a homomorphism $h$ from $q$ to
$D$ that yields an answer $\bar{b}\in q(D)$ such that $\bar{a}^{\mathcal{W}}$
is obtained from $\bar{b}$ by replacing nulls with wildcards from
$\mathcal{W}$. Clearly, $h$ is also a homomorphism from the subquery
$q^{\prime}$ of $q$ constructed during the testing phase to $D$. Consequently,
$\bar{a}\in q(D)$ where $\bar{a}$ is the tuple over $\mathsf{adom}(D)\setminus
N$ constructed along with $q^{\prime}$, and thus the test for $\bar{a}\in
q(D)$ made in the testing phase succeeds. It remains to argue that every
equivalence class $S\subseteq T$ w.r.t. ‘$\sim$’ is valid, and thus also the
checks associated with that succeed. Let
$S=\\{(q_{1},g_{1}),\dots,(q_{\ell},g_{\ell})\\}$. We first observe the
following. The proof is identical to the proof of the analogous claim for
single-wildcard progress trees in the proof of Lemma 5.3. Details are omitted.
Claim. Let $(q^{\prime},g)$ be a multiple-progress tree and let $h$ be a
homomorphism from $q^{\prime}$ to $D$ such that for all
$x\in\mathsf{var}(q^{\prime})$, $h(x)\in N$ if $g(x)\in\mathcal{W}$ and
$h(x)=g(x)$ otherwise. Then $h$ is a homomorphism from $q$ to $D_{i}$ for some
$i\in\\{1,\dots,n\\}$.
Recall the definition of ‘$\sim$’ via shared wildcards and the fact that
$\mathsf{adom}(D_{i})\cap\mathsf{adom}(D_{j})\cap N=\emptyset$ for $1\leq
i<j\leq n$, by definition of chase-like instances. From this and the claim it
follows that there is a single $D_{i}$, with $1\leq i\leq n$, such that $h$ is
a homomorphism from $q_{1}\cup\cdots\cup q_{\ell}$ to $D_{i}$. Moreover, $h$
is clearly be compatible with $g=g_{1}\cup\cdots\cup g_{\ell}$ and thus $S$ is
valid. ∎

###  F.2. Enumeration with Multi-Wildcards

We prove Proposition F.1 using exactly the algorithm described in the main
part of the paper. Balls and cones play a crucial role in the algorithm. The
following lemma explains how they link the set
$q(D)_{\mathbf{N}}^{\mathcal{W}}$ that we aim to enumerate to the set
$q(D)_{\mathbf{N}}^{\ast}$ that we enumerate in the outer forall loop. Note
that, by Point (2), we can indeed choose an $\bar{a}^{\mathcal{W}}$ with the
required properties in the algorithm.

###### Lemma F.5.

  1. (1)

$\displaystyle
q(D)_{\mathbf{N}}^{\mathcal{W}}\subseteq\bigcup_{\bar{a}^{\ast}\in
q(D)_{\mathbf{N}}^{\ast}}\mathsf{cone}^{\mathcal{W}}(\bar{a}^{\ast})$;

  2. (2)

for all $\bar{a}^{\ast}\in q(D)^{\ast}_{\mathbf{N}}$,
$\emptyset\neq\mathsf{min}^{\\!\prec}(B^{\mathcal{W}}(\bar{a}^{\ast})\cap
q(D)_{\mathbf{N}}^{\mathcal{W},\not\prec})\subseteq
q(D)_{\mathbf{N}}^{\mathcal{W}}$;

  3. (3)

for all distinct $\bar{a}^{\ast},\bar{b}^{\ast}\in q(D)_{\mathbf{N}}^{\ast}$,
$B^{\mathcal{W}}(\bar{a}^{\ast})\cap\mathsf{cone}^{\mathcal{W}}(\bar{b}^{\ast})=\emptyset$.

###### Proof.

For Point (1), let $\bar{b}^{\mathcal{W}}\in q(D)_{\mathbf{N}}^{\mathcal{W}}$
and let $\bar{b}^{\ast}$ be obtained from $\bar{b}^{\mathcal{W}}$ by replacing
every wildcard from $\mathcal{W}$ by ‘$\ast$’. Then $\bar{b}^{\ast}$ is a
partial answer to $q$ on $D$, and thus there is an $\bar{a}^{\ast}\in
q(D)_{\mathbf{N}}^{\ast}$ such that $\bar{a}^{\ast}\preceq\bar{b}^{\ast}$. It
is easy to verify that
$\bar{b}^{\mathcal{W}}\in\mathsf{cone}^{\mathcal{W}}(\bar{a}^{\ast})$.

For Point (2), let $\bar{a}^{\ast}\in q(D)_{\mathbf{N}}^{\ast}$. To prove that
the set $\mathsf{min}^{\\!\prec}(B^{\mathcal{W}}(\bar{a}^{\ast})\cap
q(D)_{\mathbf{N}}^{\mathcal{W},\not\prec})$ is non-empty, consider the multi-
wildcard tuple $\bar{a}^{\mathcal{W}}$ obtained from $\bar{a}^{\ast}$ by
replacing every occurrence of ‘$\ast$’ with a different wildcard from
$\mathcal{W}$. It is clear that $\bar{a}^{\mathcal{W}}\in
B^{\mathcal{W}}(\bar{a}^{\ast})\cap q(D)_{\mathbf{N}}^{\mathcal{W},\not\prec}$
and thus this set is non-empty. Since it is finite (and in fact of constant
size), $\mathsf{min}^{\\!\prec}(B^{\mathcal{W}}(\bar{a}^{\ast})\cap
q(D)_{\mathbf{N}}^{\mathcal{W},\not\prec})$ is also non-empty. To show that
this set is a subset of $q(D)_{\mathbf{N}}^{\mathcal{W}}$, first observe that
any tuple $\bar{a}^{\mathcal{W}}$ in it is from
$q(D)_{\mathbf{N}}^{\mathcal{W},\not\prec}$. Now assume to the contrary of
what is to be shown that there is a $\bar{b}^{\mathcal{W}}\in
q(D)_{\mathbf{N}}^{\mathcal{W},\not\prec}$ with
$\bar{b}^{\mathcal{W}}\prec\bar{a}^{\mathcal{W}}$. Then
$\bar{b}^{\mathcal{W}}$ cannot be in $B^{\mathcal{W}}(\bar{a}^{\ast})$ as
otherwise $\bar{a}^{\mathcal{W}}$ would not be minimal. This and
$\bar{b}^{\mathcal{W}}\prec\bar{a}^{\mathcal{W}}$ means that for
$\bar{a}^{\mathcal{W}}=(a_{1},\dots,a_{|\bar{x}|})$ and
$\bar{b}^{\mathcal{W}}=(b_{1},\dots,b_{|\bar{x}|})$,

  * ($\dagger$)

there is an $i\in\\{1,\dots,{|\bar{x}|}\\}$ with $b_{i}\in\mathsf{adom}(D)$
and $a_{i}\in\mathcal{W}$.

Let $\bar{b}^{\ast}$ be $\bar{b}^{\mathcal{W}}$ with every wildcard from
$\mathcal{W}$ replaced by ‘$\ast$’. It is not hard to verify that
$\bar{b}^{\ast}$ is a partial answer to $q$ on $D$ and, using
$\bar{b}^{\mathcal{W}}\prec\bar{a}^{\mathcal{W}}$ and ($\dagger$), that
$\bar{b}^{\ast}\prec\bar{a}^{\ast}$, in contradiction to $\bar{a}^{\ast}\in
q(D)_{\mathbf{N}}^{\ast}$.

We prove Point (3) by contradiction. Assume that
$\bar{a}^{\ast},\bar{b}^{\ast}\in q^{\ast}_{\mathbf{N}}(D)$ are distinct and
that there is a multi-wildcard tuple $\bar{a}^{\mathcal{W}}\in
B^{\mathcal{W}}(\bar{a}^{\ast})\cap\mathsf{cone}^{\mathcal{W}}(\bar{b}^{\ast})$.
Then by definition of cones, there is a wildcard tuple $\bar{c}^{\ast}$ such
that $\bar{a}^{\mathcal{W}}\in B^{\ast}(\bar{c}^{\ast})$ and
$\bar{b}^{\ast}\prec\bar{c}^{\ast}$. But, by definition of $B^{\mathcal{W}}$,
we have that $B^{\ast}(\bar{a}^{\mathcal{W}})=\bar{a}^{\ast}$ and
$B^{\ast}(\bar{a}^{\mathcal{W}})=\bar{c}^{\ast}$. Thus,
$\bar{a}^{\ast}=\bar{c}^{\ast}$.

Therefore $\bar{b}^{\ast}\prec\bar{a}^{\ast}$ which is impossible as
$\bar{a}^{\mathcal{W}}$ and $\bar{b}^{\ast}$ are both minimal partial answers
and, thus, incomparable. ∎

See 6.3

###### Proof.

We first argue that all tuples output by the algorithm are from
$q(D)_{\mathbf{N}}^{\mathcal{W}}$. Indeed, tuples output during the forall
loop are from $q(D)_{\mathbf{N}}^{\mathcal{W}}$ by Point (2) of Lemma F.5. It
thus remains to consider tuples that were output because they remained on the
list $L$ after the execution of the forall loop. We first observe the
following invariant, which follows from an easy analysis of the algorithm.
Claim. Throughout the run of the algorithm, $F(\bar{a}^{\mathcal{W}})=1$
implies that $\bar{a}^{\mathcal{W}}$ was already added to $L$ or is not in
$q(D)_{\mathbf{N}}^{\mathcal{W}}$.
Now consider a tuple $\bar{a}^{\mathcal{W}}$ that was output after the
execution of the forall loop and assume to the contrary of what is to be shown
that there is a $\bar{b}^{\mathcal{W}}\in q(D)_{\mathbf{N}}^{\mathcal{W}}$
such that $\bar{b}^{\mathcal{W}}\prec\bar{a}^{\mathcal{W}}$. Let
$\bar{b}^{\ast}$ be obtained from $\bar{b}^{\mathcal{W}}$ by replacing every
wildcard from $\mathcal{W}$ with ‘$\ast$’. Then $\bar{b}^{\ast}$ is a (not
necessarily minimal) partial answer to $q$ on $D$ and thus there is a
$\bar{c}^{\ast}\in q(D)_{\mathbf{N}}^{\ast}$ with
$\bar{c}^{\ast}\preceq\bar{b}^{\ast}$. Then
$\bar{b}^{\mathcal{W}}\in\mathsf{cone}^{\mathcal{W}}(\bar{c}^{\ast})$. We next
argue that at some point $\bar{b}^{\mathcal{W}}$ is appended to the list $L$.
In fact, consider the iteration of the outer forall loop that processes
$\bar{c}^{\ast}$. If $F(\bar{b}^{\mathcal{W}})=0$ at that point, then
$\bar{b}^{\mathcal{W}}$ is appended to $L$. If $F(\bar{b}^{\mathcal{W}})=1$,
then by the claim $\bar{b}^{\mathcal{W}}$ was appended to $L$ in a previous
iteration. In both cases, when $\bar{b}^{\mathcal{W}}$ was added to $L$,
$\mathsf{prune}(\bar{b}^{\mathcal{W}})$ was called and $\bar{a}^{\mathcal{W}}$
was removed from $L$ and $F(\bar{a}^{\mathcal{W}})$ set to $1$, ensuring that
$\bar{a}^{\mathcal{W}}$ is never added back to $L$. This is a contradiction to
$\bar{a}^{\mathcal{W}}$ being output because it remained on $L$.

We next argue that all tuples from $q(D)^{\mathcal{W}}_{\mathbf{N}}$ are
output. Let $\bar{a}^{\mathcal{W}}\in q(D)_{\mathbf{N}}^{\mathcal{W}}$. By
Point (1) of Lemma F.5, there is a $\bar{b}^{\ast}\in
q(D)_{\mathbf{N}}^{\ast}$ with
$\bar{a}^{\mathcal{W}}\in\mathsf{cone}^{\mathcal{W}}(\bar{b}^{\ast})$.
Consider the iteration of the outer forall loop that processes
$\bar{b}^{\ast}$. If $F(\bar{a}^{\mathcal{W}})=0$ at that point, then
$\bar{a}^{\mathcal{W}}$ is appended to $L$. If $F(\bar{a}^{\mathcal{W}})=1$,
then by the claim $\bar{a}^{\mathcal{W}}$ was appended to $L$ in a previous
iteration. Since $\mathsf{prune}(\bar{c}^{\mathcal{W}})$ is only ever called
for tuples $\bar{c}^{\mathcal{W}}\in
q(D)_{\mathbf{N}}^{\mathcal{W},\not\prec}$, the only way
$\bar{a}^{\mathcal{W}}$ can be removed from $L$ is when it is chosen to be
output in the outer forall loop. If that never happens, it is still on $L$
after that loop has terminated and thus also output.

Finally, we argue that there are no repetitions. This, however, is an
immediate consequence of the use of the lookup table $F$ to make sure that
every multi-wildcard is appended to list $L$ at most once and of the fact that
when a tuple is output in the outer forall loop, then it is removed from $L$.
∎

##  Appendix G Illustrating the Algorithm

We give examples that showcase important aspects of the enumeration algorithm
for minimal partial answers with a single wildcard presented in Section 5.

Assume that the enumeration algorithm is started on the OMQ
$Q(\bar{x})=(\mathcal{O},\mathbf{S},q)\in(\mathbb{G},\mathbb{CQ})$ where
$\mathcal{O}$ consists of the TGDs

$\begin{array}[]{rcl}A(x)&\rightarrow&\exists y_{1}\exists y_{2}\
R(y_{1},y_{2})\land R(y_{2},x)\land C(y_{2})\\\\[2.84526pt]
B(x)&\rightarrow&\exists y_{1}\exists y_{2}\ R(y_{1},x)\land R(y_{2},x)\land
C(y_{1})\\\\[2.84526pt] E(x)&\rightarrow&\exists y_{1}\
R(x,y_{1})\\\\[2.84526pt] R(x,y)&\rightarrow&L(x,x)\land L(y,y),\end{array}$

the schema $\mathbf{S}$ is $\\{A,B,C,E,R\\}$, and where $q$ is the CQ

$\begin{array}[]{rcl}q(\bar{x})&{\leftarrow}&\exists y_{1}\exists y_{5}\
L(y_{1},x_{1}),R(x_{1},x_{2}),R(x_{2},x_{3}),\\\\[2.84526pt] &&\ \
R(x_{4},x_{3}),R(x_{5},x_{4}),L(y_{5},x_{5}),C(x_{1}).\end{array}$

with $\bar{x}=(x_{1},x_{2},x_{3},x_{4},x_{5})$. The CQ $q$ is displayed in
Figure 2.

C$R$$L$$R$$R$$R$$L$$x_{1}$$y_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$y_{5}$a) CQ $q$
$C_{1}(x_{1})$$L(y_{1},x_{1})$$R(x_{1},x_{2})$$R(x_{2},x_{3})$$R(x_{4},x_{3})$$R(x_{5},x_{4})$$L(y_{5},x_{5})$b)
join tree of $q$ Figure 2. CQ $q$ and its join tree.

It is acyclic and free/̄connex acyclic, as witnessed by the join trees for $q$
and its extension $\hat{q}$ with the atom $\hat{R}(x_{1},\dots,x_{5})$. The
join tree for $q$ is given in Figure 2. Note that the atoms that contain only
answer variables constitute a connected prefix of the join tree of $q$. This
can (almost444It can always be achieved when using a generalized hypertree
decomposition of width 1 in place of a join tree, see (berkholz-enum-tutorial,
).) always be achieved for CQs that are acyclic and free-connex acyclic and is
exploited in the preprocessing phase.

Assume that the input database $D$ is as depicted on the left-hand side of
Figure 3, where all edges represent the relation symbol $R$.

$a$$b$$c$$d$$e$$A$, $E$$E$$B,C$$B$database $D$
$a$$b$$c$$d$$e$$n_{1}$$n_{2}$$n_{3}$$n_{4}$$n_{5}$$n_{6}$$n_{7}$$n_{8}$$A$,
$E$$E$$B,C$$B$$C$$C$$C$database $D_{0}$ Figure 3. Database $D$ and query-
directed chase $D_{0}$. All edges represent relation $R$ and every constant
has an $L$-self/̄loop that is not shown.

#### Preprocessing

In the preprocessing phase, we modify the query $q$ and database $D$ to obtain
the CQ $q_{2}$ and database $D_{2}$ that are used in the enumeration phase.
This is done in several steps. In the very first step, we set $q_{0}=q$ and
replace $D$ with the query-directed chase
$D_{0}=\mathsf{ch}_{\mathcal{O}}^{q}(D)$, displayed on the right-hand side of
Figure 3.

The next step is to construct from $q_{0}$ and $D_{0}$ a self-join free CQ
$q_{1}$ without quantified and a database $D_{1}$ that has been adjusted
accordingly. It is this step that exploits the special shape of the join tree
of $q_{0}$ mentioned above. In our case, $q_{1}$ is

$q_{1}(\bar{x})\leftarrow R_{1}(x_{1},x_{2}),\allowbreak
R_{2}(x_{2},x_{3}),\allowbreak
R_{4}(x_{4},x_{3}),R_{5}(x_{5},x_{4}),C_{1}(x_{1}).$

Informally, $q_{1}$ was obtained from $q$ by renaming relation symbols to
achieve self-join freeness and dropping atoms that involve a quantified
variable. The join tree of $q_{1}$ is the join tree of $q$ except that
relation symbols in atoms change and nodes/atoms that contain any of the
variables $y_{1},y_{5}$ are removed.

The database $D_{1}$ is shown in Figure 3 where, for better readability, we
only show the index $i$ of edge labels $R_{i}$. Observe that the constant
$n_{8}$ was removed and that edges are now multi/̄edges. To get an intuition
of the construction of $D_{1}$, consider the fact $R(n_{2},n_{1})$ in $D_{0}$.
In principle, any of the four $R$-atoms in $q_{0}$ can map to it, and in
$q_{1}$ the relation symbol $R$ in those atoms has been renamed to $R_{1}$,
$R_{2}$, $R_{4}$, and $R_{5}$, respectively. Thus, we should be prepared to
include in $D_{1}$ the fact $R_{i}(n_{2},n_{1})$ for all $i\in\\{1,2,4,5\\}$.
However, a closer inspection shows that the atom $R(x_{2},x_{3})$ in $q_{0}$
cannot map to the fact $R(n_{2},n_{1})$ in $D_{0}$ since then $x_{1}$ would
have to be mapped to an $R$-predecessor of $n_{2}$, which does not exist. A
similar observation holds for the atom $R(x_{4},x_{3})$ in $q_{0}$ and thus we
only include in $D_{1}$ the facts $R_{1}(n_{2},n_{1})$ and
$R_{5}(n_{2},n_{1})$. The ‘right’ facts to include are identified during a
bottom-up walk over the join-tree of $q_{0}$. Note that the relation symbols
$A$, $B$, have been dropped since they do not occur in $q_{0}$.

$a$$b$1,2,4,5$c$5$d$1,2,4,5$e$5$n_{1}$2,4$n_{2}$1,5$n_{3}$1,5$n_{4}$5$n_{5}$1,5$n_{6}$5$n_{7}$2,4$C_{1}$$C_{1}$$C_{1}$$C_{1}$
Figure 4. Database $D_{1}$. Edges are labeled with indices of the relation
symbols $R_{1},R_{2},R_{4},R_{5}$ that constitute the edge.
$R_{1}(x_{1},x_{2})$$R_{2}(x_{2},x_{3})$$R_{4}(x_{4},x_{3})$$R_{5}(x_{5},x_{4})$$C_{1}(x_{1})$$x_{3}$$x_{3}$$x_{4}$$x_{1}$
Figure 5. Join tree of $q_{2}$. The predecessor variables of each atom are
shown on the incoming edge of the atom.

#### Lists of progress trees.

The last step of the preprocessing phase is to create the lists
$\mathsf{trees}(v,h)$ of progress trees for each atom $v$ in $q_{2}$ and each
predecessor map $h$ for $v$. Recall that by the latter we mean a function
$h:\bar{z}\rightarrow\mathsf{adom}(D_{2})\setminus N$ whose range is a guarded
set in $D_{2}$, and where $\bar{z}$ are the predecessor variables in $v$. For
brevity, we represent $h$ in the form $z_{1}\cdots z_{n}\mapsto c_{1}\cdots
c_{n}$ when $z_{1},\dots,z_{n}$ are the variables in $\bar{z}$ and
$h(z_{i})=c_{i}$ for $1\leq i\leq n$; this becomes
$\varepsilon\mapsto\varepsilon$ when $\bar{z}$ is the empty tuple. For the
join tree of $q_{1}$ with marked predecessor variables, see Figure 5.

Also recall that a progress tree is a pair $(q,g)$ with CQ $q$ a subtree of
$q_{2}$ and $g$ a function from $\mathsf{var}(q)$ to
$(\mathsf{adom}(D_{2})\setminus N)\cup\\{\ast\\}$ that must satisfy Conditions
(1)-(4) given in Section 5. We represent the function $g$ in the same way as
predecessor maps. Examples of progress trees include

$(R_{1}(x_{1},x_{2}),x_{1}x_{1}x_{2}\mapsto ba)$

and

$(R_{2}(x_{2},x_{3})\wedge R_{1}(x_{1},x_{2})\wedge
C_{1}(x_{1}),x_{1}x_{2}x_{3}\mapsto{\ast}{\ast}a).$

The reader is invited to verify that the relevant Conditions (1)-(4) are all
satisfied for these progress trees. Intuitively, the second progress tree
$(q,g)$ above describes an ‘excursion’ of the part $q$ of $q_{2}$ into the
‘null part’ of $D_{2}$. This excursion consists of mapping $x_{1}$ to $n_{2}$,
$x_{2}$ to $n_{1}$, and $x_{3}$ to $a$.

Let us review two non-examples progress trees, starting with

$(R_{4}(x_{4},x_{3})\wedge R_{5}(x_{5},x_{4}),x_{3}x_{4}x_{5}\mapsto abc)$

which is not a progress tree as the predecessor variable $x_{4}$ of atom
$R_{5}(x_{5},x_{4})$ is mapped to ‘$\ast$’ and thus Condition (2) is violated.
Next consider

$(R_{4}(x_{4},x_{3})\wedge R_{5}(x_{5},x_{4}),x_{3}x_{4}x_{5}\mapsto
a{\ast}c)$

which is not a progress tree because there is no guarded set in $D_{2}$ that
contains $a$ and $c$, and thus Condition (4) is violated.

We now give all the lists $\mathsf{trees}(v,h)$ that are computed in the
preprocessing phase. For brevity, we represent progress trees $(q,g)$ as the
CQ $q$ in which every variable $x$ was replaced with $g(x)$. List items are
separated by ‘;’. The lists are:

  * •

atom $v=R_{1}(x_{1},x_{2})$ with a predecessor variable $x_{2}$

    * –

$\mathsf{trees}(v,x_{2}\mapsto a)=[R_{1}(b,a);R_{1}(d,a)]$

    * –

$\mathsf{trees}(v,x_{2}\mapsto b)=[R_{1}(\ast,b)\wedge C_{1}(\ast)]$

    * –

$\mathsf{trees}(v,x_{2}\mapsto c)=[]$

    * –

$\mathsf{trees}(v,x_{2}\mapsto d)=[R_{1}(\ast,d)\wedge C_{1}(\ast)]$

    * –

$\mathsf{trees}(v,x_{2}\mapsto e)=[]$

  * •

atom $v=R_{2}(x_{2},x_{3})$ no predecessor variables

    * –

$\mathsf{trees}(v,\emptyset\mapsto\emptyset)=[R_{2}(b,a);R_{2}(d,a);$
$R_{2}(\ast,a)\wedge R_{1}(\ast,\ast)\wedge C_{1}(\ast);R_{2}(a,\ast)\wedge
R_{4}(a,\ast)]$

  * •

atom $v=R_{4}(x_{4},x_{3})$ with a predecessor variable $x_{3}$

    * –

$\mathsf{trees}(v,x_{3}\mapsto\beta)=[]$ for $\beta\in\\{b,c,d,e\\}$

    * –

$\mathsf{trees}(v,x_{3}\mapsto c_{0}a)=[R_{4}(b,a);R_{4}(d,a);$
$R_{4}(\ast,a)\wedge R_{5}(\ast,\ast)]$

  * •

atom $v=R_{5}(x_{5},x_{4})$ with a predecessor variable $x_{4}$

    * –

$\mathsf{trees}(v,x_{2}\mapsto c)=[]$

    * –

$\mathsf{trees}(v,x_{2}\mapsto a)=[R_{5}(b,a);R_{5}(d,a);R_{5}(e,a)]$

    * –

$\mathsf{trees}(v,x_{2}\mapsto b)=[R_{5}(c,b);R_{5}(\ast,b)]$

    * –

$\mathsf{trees}(v,x_{2}\mapsto d)=[R_{5}(\ast,d)]$

    * –

$\mathsf{trees}(v,x_{2}\mapsto e)=[]$

  * •

atom $v=C_{1}(x_{1})$ with a predecessor variable $x_{1}$

    * –

$\mathsf{trees}(v,x_{1}\mapsto\beta)=[]$ for $\beta\in\\{a,c,d,e\\}$

    * –

$\mathsf{trees}(v,x_{1}\mapsto b)=[C_{1}(b)]$

All the remaining lists are empty. The lists above are sorted in database
preferring order, as required, and thus we are ready for the enumeration
phase.

#### Enumeration and pruning

In the enumeration phase, we traverse the join tree of $q_{1}$ in a depth-
first fashion, assembling a minimal partial answer to $q_{1}$ on $D_{1}$. Once
such an answer is found, we output it and execute pruning, then backtrack in a
systematic way and re-start answer assemblage to produce the next answer, and
so on.

In our example, there are no complete answers. The first partial answer
generated is $\bar{c}^{\ast}={\ast}babc$. The answer $\bar{c}^{\ast}$ is
displayed on the left-hand side of Figure 6, inside the join tree for $q_{1}$.
The blue boxes indicate the progress trees that have been used in assembling
the answer $\bar{c}^{\ast}$.

Answer ${\ast}babc$Answer
${\ast}{\ast}abc$${\ast}b$$ba$$ba$$cb$${\ast}$$b$$a$$b$${\ast}$${\ast}{\ast}$${\ast}a$$ba$$cb$${\ast}$${\ast}$$a$$b$${\ast}$

Figure 6. Three least partial answers, inside join tree of $q_{2}$.

Let us now consider pruning with $\bar{c}^{\ast}$. Informally, we consider all
progress trees $(q,g)$ such that $q$ is some subtree of $q_{2}$ and $g$ can be
obtained by starting with $\bar{x}\mapsto\bar{c}^{\ast}$, then restricting to
the variables in $\mathsf{var}(q)$, and then switching at least one variable
from a non-wildcard to a wildcard. One example of such a progress tree is

$R_{2}(\ast,a)\wedge R_{1}(\ast,\ast)\wedge C_{1}(\ast).$

Pruning removes this tree from
$\mathsf{trees}(R_{2}(x_{2},x_{3}),\emptyset\mapsto\emptyset)$. One
consequence of this pruning that the partial answer ${\ast}{\ast}abc$
displayed on the right of Figure 6, which is not a minimal partial answer, is
not output in the enumeration phase.

#### Minimal partial answers with multi-wildcards.

We also briefly consider the enumeration algorithm for minimal partial answers
with multi-wildcards from Section 6, illustrating in particular the necessity
of using _cones_. Recall that a cone of a wildcard tuple $\bar{a}^{\ast}$ is
the set of all multi/̄wildcard tuples $\bar{b}^{\mathcal{W}}$ such that the
wildcard tuple $\bar{b}^{\ast}$ obtained from $\bar{b}^{\mathcal{W}}$ by
replacing all named wildcards by $\ast$ satisfies
$\bar{a}^{\ast}\preceq\bar{b}^{\ast}$.

Intuitively, the enumeration algorithm for multiple wildcards starts the
enumeration algorithm for a single wildcard as a black box procedure and
whenever the black box generates a minimal partial answer $\bar{a}^{\ast}$
then it outputs the multi/̄wildcard minimal partial answers from
$\text{cone}(\bar{a}^{\ast})$, with some bookkeeping to prevent repetition.

Consider again the CQ $q_{1}$ and database $D_{1}$. As mentioned before, the
first generated answer is ${\ast}babc$ and pruning removes from
$\mathsf{trees}(R_{2}(x_{2},x_{3}),\emptyset\mapsto\emptyset)$ the progress
tree $R_{2}(\ast,a)\wedge R_{1}(\ast,\ast)\wedge C_{1}(\ast)$. Apart from
preventing the partial answer ${\ast}{\ast}abc$ to be output as noted above,
this also suppresses the partial answer ${\ast}bab{\ast}$ (which is correct,
as it is not a minimal partial answer). In contrast, it is not hard to check
that ${\ast_{1}}bab{\ast_{1}}$ is a minimal partial answer and thus must be
output by the enumeration procedure for multi-wildcards.

A naive version of the procedure without cones would simply look at each
minimal partial answer with a single wildcard $\bar{c}^{\ast}$ output by the
black box and then output all multi-wildcard answers $\bar{c}^{\mathcal{W}}$
obtained from $\bar{c}^{\ast}$ by replacing each occurrence of the wildcard
with some wildcard from $\mathcal{W}$. Clearly, such a naive version would
miss the minimal partial answer ${\ast_{1}}bab{\ast_{1}}$. However,
${\ast}babc\prec{\ast}bab{\ast}$ and thus
${\ast_{1}}bab{\ast_{1}}\in\mathsf{cone}({\ast}babc)$. Our more refined
algorithm therefore adds ${\ast_{1}}bab{\ast_{1}}$ to the list $L$ when
processing the tuple ${\ast}babc$ and outputs it at the end of its run along
with the other tuples in $L$.