We reduce $\texttt{Eval}(Q_{\text{rel}},\mathsf{}_{\text{rel}},\mathbb{B})$ to
$\texttt{Eval}(Q,\mathsf{},\mathbb{B})$. Denote the free variables of $Q$,
$Q_{\text{rel}}$ and $Q_{\text{ineq}}$ by $\overline{x}$, $\overline{x}_{1}$
and $\overline{x}_{2}$, respectively. Note that $\overline{x}_{1}$ and
$\overline{x}_{2}$ are disjoint and
$\mathsf{}(\overline{x})=\mathsf{}(\overline{x}_{1})\cup\mathsf{}(\overline{x}_{2})$.
Consider an arbitrary database $\textit{db}_{\text{rel}}$ over $\mathsf{}$,
input to $\texttt{Eval}(Q_{\text{rel}},\mathsf{},\mathbb{B})$. Construct the
database db, input to $\texttt{Eval}(Q,\mathsf{},\mathbb{B})$ as follows.

Recall that all data values occurring in tuples in $\textit{db}_{\text{rel}}$
are non-zero natural numbers. Scan $\textit{db}_{\text{rel}}$ and compute the
largest natural number $M$ occurring in $\textit{db}_{\text{rel}}$. Then
construct the database db by setting

  * •

$R^{\textit{db}}=R^{\textit{db}_{\text{rel}}}$ for each relation symbol
$R\in\mathsf{}$;

  * •

$db(c):=M$ for all constant symbols $c\in\mathsf{}$ that occur in a covered
inequality in $Q$. Note that $c\not=1$ because $Q$ is constant-disjoint;

  * •

$db(c):=1$ for all other constant symbols $c\in\mathsf{}$.

This is well-defined because $Q$ is constant-disjoint. The computation of db
is clearly in $\mathsf{}(\parallel\\!\textit{db}_{\text{rel}}\\!\parallel)$
and
$\parallel\\!\textit{db}\\!\parallel=\parallel\\!\textit{db}_{\text{rel}}\\!\parallel$.

Note that, because $Q_{\text{rel}}$ consists of relational atoms only, its
evaluation is hence independent of the values assigned to the constant symbols
by $\textit{db}_{\text{rel}}$. Therefore,
$\texttt{Answer}(Q_{\text{rel}},\textit{db}_{\text{rel}})=\texttt{Answer}(Q_{\text{rel}},\textit{db})$.
To obtain the proposition, it hence suffices to show that
$\texttt{Answer}(Q_{\text{rel}},\textit{db})$ may be enumerated with constant
delay after further linear time preprocessing. We do so by showing that
$\texttt{Vals}(Q_{\text{rel}},\textit{db},$) may be enumerated with constant
delay after linear time preprocessing as follows. Observe that db is
atomically consistent with $Q$. This is by construction since for every
covered inequality $x\leq c$ we have $\textit{db}(c)$ equal to $M$, with $M$
larger than any value in db. Hence, by Claim 2 we have

$\texttt{Vals}(Q,\textit{db})=\\{(\nu_{1}\cup\nu_{2},\texttt{t})\mid(\nu_{1},\texttt{t})\in\texttt{Vals}(Q_{\text{rel}},\textit{db}),(\nu_{2},\texttt{t})\in\texttt{Vals}(Q_{\text{ineq}},\textit{db})\\}.$

As such,
$\texttt{Vals}(Q_{\text{rel}},\textit{db})=\\{({\nu}|_{\overline{x}_{1}},\texttt{t})\mid(\nu,\texttt{t})\in\texttt{Vals}(Q,\textit{db})\\}$
and we may hence enumerate $\texttt{Vals}(Q_{\text{rel}},\textit{db})$ by
enumerating the elements of $\texttt{Vals}(Q,\textit{db})$ and for each such
element output $({\nu}|_{\overline{x}_{1}},\texttt{t})$. Note that the
resulting enumeration is necessarily duplicate-free as required: by definition
of db the set $\texttt{Vals}(Q_{\text{ineq}},\textit{db})$ consists of a
single element: the pair $(\overline{x}_{2}\mapsto 1,\texttt{t})$. To see why
this is neccisarily the case observe that, by definition, all free variables
$y\in\overline{x}_{2}$ of $Q_{\text{ineq}}$ must occur in an uncovered
inequality $y\leq c$. Because $Q$ is constant-disjoint this constant $c$ is
such that there is no covered inequality $z\leq d$ in $Q$ with $c=d$. (If
there were, $y$ would be non-free.) This means that we have set
$c^{\textit{db}}=1$. Therefore, for every free variable $y$ of
$Q_{\text{rel}}$, we neccesarily have that $\nu(y)=1$ in a resulting
valuation. As such, all valuations in $\texttt{Vals}(Q,\textit{db})$ are
constant on the variables in $\overline{x}_{2}$ and duplicates can hence not
occur when projecting on $\overline{x}_{1}$. The proposition then follows
because we may enumerate $\texttt{Vals}(Q,\textit{db})$ with $\mathsf{}(1)$
delay after linear time preprocessing by assumption.

######  Proposition 9.17.

Let $Q$ be a CQ over $\mathsf{}$ and $\mathcal{K}$ a semiring such that the
subsemiring generated by $\mymathbb{0}_{\mathcal{K}}$ and
$\mymathbb{1}_{\mathcal{K}}$ is non-trivial and zero-sum free. If
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$
then
$\texttt{Enum}(Q,\mathsf{},\mathbb{B})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$.

######  Proof 9.18.

Let
$\mathcal{K}=(K,\oplus,\odot,\mymathbb{0}_{\mathcal{K}},\mymathbb{1}_{\mathcal{K}})$
be a a semiring such that the subsemiring generated by
$\mymathbb{0}_{\mathcal{K}}$ and $\mymathbb{1}_{\mathcal{K}}$ is non-trivial
and zero-sum free. We reduce $\texttt{Eval}(Q,\mathsf{},\mathbb{B})$ to
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})$ as follows. Let
$\textit{db}_{\mathbb{B}}$ be a $\mathbb{B}$-database over $\mathsf{}$, input
to $\texttt{Eval}(Q,\mathsf{},\mathbb{B})$. Construct the
$\mathcal{K}$-database $\textit{db}_{\mathcal{K}}$, input to
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})$ by setting

  * •

for every relation symbol $R\in\mathsf{}$

$\llceil{R}\rrfloor_{\textit{db}_{\mathcal{K}}}\colon\overline{d}\mapsto\begin{cases}\mymathbb{1}_{\mathcal{K}}\text{
if }R^{\textit{db}_{\mathbb{B}}}(\overline{d})=\texttt{t}\\\
\mymathbb{0}_{\mathcal{K}}\text{ otherwise. }\end{cases}$

  * •

$\textit{db}_{\mathcal{K}}(c):=\textit{db}_{\mathbb{B}}(c)$ for every constant
symbol $c$.

Note that this takes time
$\mathsf{}(\parallel\\!\textit{db}_{\mathbb{B}}\\!\parallel)$.

By assumption,
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$
thus the set $\texttt{Vals}(Q,\textit{db}_{\mathcal{K}})$ can be enumerated
with constant delay after a linear time preprocessing. Now, it suffices to do
the following: for every outputed tuple
$(\nu,\llceil{Q}\rrfloor_{\textit{db}_{\mathcal{K}}}(\nu))$ we output
$(\nu,\texttt{t})$. The former describes a constant delay enumeration for the
set $\texttt{Vals}(Q,\textit{db}_{\mathbb{B}})$, since we claim that for every
valuation $\nu$ we have
$(\nu,\texttt{t})\in\texttt{Vals}(Q,\textit{db}_{\mathbb{B}})$ if and only if
$(\nu,k)\in\texttt{Vals}(Q,\textit{db}_{\mathcal{K}})$ for some
$\mymathbb{0}_{\mathcal{K}}\neq k\in K$. We next argue why this claim holds.

Let $\varphi=\exists\overline{y}.R_{1}(\overline{z}_{1})\wedge\cdots\wedge
R_{n}(\overline{z}_{m})\wedge w_{1}\leq
c_{1}\wedge\cdots\wedge\overline{w}_{m}\leq c_{m}$ be the body of
$Q(\overline{x})$ and assume $\nu\colon\overline{x}$.

First, if
$(\nu,\llceil{Q}\rrfloor_{\textit{db}_{\mathcal{K}}}(\nu))\in\texttt{Vals}(Q,\textit{db}_{\mathcal{K}})$
then in particular
$\llceil{Q}\rrfloor_{\textit{db}_{\mathcal{K}}}(\nu)\neq\mymathbb{0}_{\mathcal{K}}$.
Because

$\displaystyle\llceil{Q}\rrfloor_{\textit{db}_{\mathcal{K}}}(\nu)$
$\displaystyle=\bigoplus_{\mu\colon\mathsf{}(\varphi)\text{
s.t.}{\mu}|_{\overline{x}}=\nu}\llceil{\varphi}\rrfloor_{\textit{db}_{\mathcal{K}}}(\mu)$
$\displaystyle=\bigoplus_{\mu\colon\mathsf{}(\varphi)\text{
s.t.}{\mu}|_{\overline{x}}=\nu}R_{1}^{\textit{db}_{\mathcal{K}}}({\mu}|_{\overline{z}_{1}})\odot\cdots\odot
R_{n}^{\textit{db}_{\mathcal{K}}}({\mu}|_{\overline{z}_{n}})\odot$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\llceil{w_{1}\leq
c_{1}}\rrfloor_{\textit{db}_{\mathcal{K}}}({\mu}|_{w_{1}})\odot\cdots\odot\llceil{w_{m}\leq
c_{m}}\rrfloor_{\textit{db}_{\mathcal{K}}}({\mu}|_{w_{m}})$

we know in particular that there exists some $\mu$ such that

$R_{1}^{\textit{db}_{\mathcal{K}}}({\mu}|_{\overline{z}_{1}})\odot\cdots\odot
R_{n}^{\textit{db}_{\mathcal{K}}}({\mu}|_{\overline{z}_{n}})\odot\llceil{w_{1}\leq
c_{1}}\rrfloor_{\textit{db}_{\mathcal{K}}}({\mu}|_{w_{1}})\odot\cdots\odot\llceil{w_{m}\leq
c_{m}}\rrfloor_{\textit{db}_{\mathcal{K}}}({\mu}|_{w_{m}})\neq\mymathbb{0}_{\mathcal{K}}.$

This is because in any semiring, a sum of terms can be non-$\mymathbb{0}$ only
if one term is non-$\mymathbb{0}$. Moreover, a product is non-$\mymathbb{0}$
only if all of its factors are non-$\mymathbb{0}$. By construction,
$R_{i}^{\textit{db}_{\mathcal{K}}}({\mu}|_{\overline{z}_{i}})\not=\mymathbb{0}$
for all $i=1,\ldots,n$ and $\llceil{w_{j}\leq
c_{j}}\rrfloor_{\textit{db}_{\mathcal{K}}}({\mu}|_{w})\not==\mymathbb{0}_{\mathcal{K}}$
for all $j=1,\ldots,m$ only if
$R_{i}^{\textit{db}_{\mathbb{B}}}({\mu}|_{\overline{z}_{i}})=\texttt{t}$ and
$\llceil{w_{j}\leq
c_{j}}\rrfloor_{\textit{db}_{\mathbb{B}}}({\mu}|_{w})=\texttt{t}$ for all $i$
and $j$. Thus $(\nu,\texttt{t})\in\texttt{Vals}(Q,\textit{db}_{\mathbb{B}})$.

Second, if $(\nu,\texttt{t})\in\texttt{Vals}(Q,\textit{db}_{\mathbb{B}})$ then
in particular $\llceil{Q}\rrfloor_{\textit{db}_{\mathbb{B}}}(\nu)=\texttt{t}$.
Because

$\displaystyle\llceil{Q}\rrfloor_{\textit{db}_{\mathbb{B}}}(\nu)$
$\displaystyle=\bigvee_{\mu\colon\mathsf{}(\varphi)\text{
s.t.}{\mu}|_{\overline{x}}=\nu}R_{1}^{\textit{db}_{\mathbb{B}}}({\mu}|_{\overline{z}_{1}})\wedge\cdots\wedge
R_{n}^{\textit{db}_{\mathbb{B}}}({\mu}|_{\overline{z}_{n}})$
$\displaystyle\qquad\qquad\qquad\qquad\wedge\llceil{w_{1}\leq
c_{1}}\rrfloor_{\textit{db}_{\mathbb{B}}}({\mu}|_{w_{1}})\wedge\cdots\wedge\llceil{w_{m}\leq
c_{m}}\rrfloor_{\textit{db}_{\mathbb{B}}}({\mu}|_{w_{m}})$

this implies there is some valuation $\mu$ such that

$R_{1}^{\textit{db}_{\mathbb{B}}}({\mu}|_{\overline{z}_{1}})\wedge\cdots\wedge
R_{n}^{\textit{db}_{\mathbb{B}}}({\mu}|_{\overline{z}_{n}})\wedge\llceil{w_{1}\leq
c_{1}}\rrfloor_{\textit{db}_{\mathbb{B}}}({\mu}|_{w_{1}})\wedge\cdots\wedge\llceil{w_{m}\leq
c_{m}}\rrfloor_{\textit{db}_{\mathbb{B}}}({\mu}|_{w_{m}})=\texttt{t}.$

In particular,
$R_{i}^{\textit{db}_{\mathbb{B}}}({\mu}|_{\overline{z}_{i}})=\texttt{t}$ for
all $i=1,\ldots,n$ and $\llceil{w_{j}\leq
c_{j}}\rrfloor_{\textit{db}_{\mathbb{B}}}({\mu}|_{w_{j}})=\texttt{t}$ for
$j=1,\ldots,m$. Then, by construction of $\textit{db}_{\mathcal{K}}$ we have
$R_{i}^{\textit{db}_{\mathcal{K}}}({\mu}|_{\overline{z}_{i}})=\mymathbb{1}_{\mathcal{K}}$
for all $i=1,\ldots,n$ and $\llceil{w_{j}\leq
c_{j}}\rrfloor_{\textit{db}_{\mathcal{K}}}({\mu}|_{w_{j}})=\mymathbb{1}_{\mathcal{K}}$
for $j=1,\ldots,m$. Hence,

$R_{1}^{\textit{db}_{\mathcal{K}}}({\mu}|_{\overline{z}_{1}})\odot\cdots\odot
R_{n}^{\textit{db}_{\mathcal{K}}}({\mu}|_{\overline{z}_{n}})\odot\llceil{w_{1}\leq
c_{1}}\rrfloor_{\textit{db}_{\mathcal{K}}}({\mu}|_{w_{1}})\odot\cdots\odot\llceil{w_{m}\leq
c_{m}}\rrfloor_{\textit{db}_{\mathcal{K}}}({\mu}|_{w_{m}})=\mymathbb{1}_{\mathcal{K}}.$

Thus, since the subsemiring generated by $\mymathbb{0}_{\mathcal{K}}$ and
$\mymathbb{1}_{\mathcal{K}}$ is non-trivial and zero-sum free,

$\displaystyle\llceil{Q}\rrfloor_{\textit{db}_{\mathcal{K}}}(\nu)$
$\displaystyle=\bigoplus_{\mu\colon\mathsf{}(\varphi)\text{
s.t.}{\mu}|_{\overline{x}}=\nu}\llceil{\varphi}\rrfloor_{\textit{db}_{\mathcal{K}}}(\mu)\not=\mymathbb{0}_{\mathcal{K}}$

Recall that by convention we only consider commutative and non-trivial
semirings throughout the paper. As such when we consider an arbitrary semiring
$\mathcal{K}$, then we assume that this semiring is commutative and non-
trivial. For such semirings, it is straightforward to check that the sub-
semiring generated by $\mymathbb{0}$ and $\mymathbb{1}$ is also commutative
and non-trivial. (We note that we have only explicitly add the “non-trivial”
requirement in the previous proposition because the proof uses this property.)
Given this discussion, the following Theorem therefore implies Theorem 7 in
Section 7.

######  Theorem 9.19.

Let $Q$ be a CQ over $\mathsf{}$ without self-joins and constant-disjoint. Let
$\mathcal{K}$ a semiring such that the subsemiring generated by
$\mymathbb{0}_{\mathcal{K}}$ and $\mymathbb{1}_{\mathcal{K}}$ is zero-sum
free. If
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$,
then $Q$ is free-connex, unless either the Sparse Boolean Matrix
Multiplication, the Triangle Detection, or the $(k,k+1)$-Hyperclique
conjecture is false.

######  Proof 9.20.

Let $\texttt{split}(Q)=(Q_{\text{rel}},Q_{\text{ineq}})$ and assume
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$.
Because the subsemiring of $\mathcal{K}$ generated by
$\mymathbb{0}_{\mathcal{K}}$ and $\mymathbb{1}_{\mathcal{K}}$ is non-trivial
and zero-sum free,
$\texttt{Eval}(Q,\mathsf{},\mathbb{B})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$
holds by Proposition 9.17. This implies
$\texttt{Eval}(Q_{\text{rel}},\mathsf{},\mathbb{B})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$,
due to Proposition 9.15. Theorem 9.1 yields that $Q_{\text{rel}}$ is free-
connex, unless either the Sparse Boolean Matrix Multiplication, the Triangle
Detection, or the $(k,k+1)$-Hyperclique conjecture is false. Finally, since
$Q_{\text{rel}}$ is free-connex if and only if $Q$ is free-connex (Proposition
9.5), this immediately implies that $Q$ is free-connex, unless either the
Sparse Boolean Matrix Multiplication, the Triangle Detection, or the
$(k,k+1)$-Hyperclique conjecture is false.

We now proceed to prove Corollary 7. In order to achieve this, it is crucial
to identify when a $\mathsf{conj}\text{-}\mathsf{MATLANG}$ query $\mathbf{Q}$
yields a translated CQ $Q$ which

  1. 1.

does not have covered inequalities of the form $x\leq 1$, and

  2. 2.

for every uncovered inequality $y\leq c$ with $c\neq 1$ it holds that $y$ is
not free in $Q$.

Intuitively, $Q$ will possess the first property because it is well-typed, and
the second property if the dimensions of the output matrix of $\mathbf{Q}$ are
_fixed_ by some input matrix.

######  Definition 9.21.

Let $e$ be a $\mathsf{conj}\text{-}\mathsf{MATLANG}$ expression.
$\texttt{FixDim}(e)$ is the set of fixed dimensions of $e$ and it is
inductively defined as follows:

$\begin{array}[]{rl}\texttt{FixDim}(\mathbf{A})\coloneqq\\!\\!\\!\\!\\!&\\{0,1\\}\\\
\texttt{FixDim}(\mathbf{v})\coloneqq\\!\\!\\!\\!\\!&\\{1\\}\\\
\texttt{FixDim}(e^{T})\coloneqq\\!\\!\\!\\!\\!&\\{\left(i+1\right)\mod 2\mid
i\in\texttt{FixDim}(e)\\}\\\ \texttt{FixDim}(e_{1}\cdot
e_{2})\coloneqq\\!\\!\\!\\!\\!&\left(\texttt{FixDim}(e_{1})\setminus\\{1\\}\right)\cup\left(\texttt{FixDim}(e_{2})\setminus\\{0\\}\right)\\\
\texttt{FixDim}(e_{1}\times
e_{2})\coloneqq\\!\\!\\!\\!\\!&\texttt{FixDim}(e_{2})\\\
\texttt{FixDim}(e_{1}\odot
e_{2})\coloneqq\\!\\!\\!\\!\\!&\texttt{FixDim}(e_{1})\cup\texttt{FixDim}(e_{2})\\\
\texttt{FixDim}(\Sigma\mathbf{v}.e)\coloneqq\\!\\!\\!\\!\\!&\texttt{FixDim}(e).\end{array}$

An expression $e$ has _guarded dimensions_ if $\texttt{FixDim}(e)=\\{0,1\\}$,
is _row fixed_ if $\texttt{FixDim}(e)=\\{0\\}$ and _column fixed_ if
$\texttt{FixDim}(e)=\\{1\\}$.

The former definition is straightforwardly extended to a
$\mathsf{conj}\text{-}\mathsf{MATLANG}$ query $\mathbf{Q}$, where
$\texttt{FixDim}(\mathbf{Q})$ stands for $\texttt{FixDim}(e)$. Let
$\mathsf{FO}^{\wedge}_{=}$ denote the conjunctive first order formulas with
equality atoms. We say that free variable $x$ of
$\varphi\in\mathsf{FO}^{\wedge}_{=}$ is _bounded_ in $\varphi$ if $x$ appears
in a relation symbol. Here, we assume without loss of generality that
quantified variables in $\varphi$ are distinct from its free variables. For
example $x$ is bounded in $x\leq\alpha\wedge R(x)$ and is not bounded in
$x\leq 1\wedge\exists z.R(z,y)$.

######  Lemma 9.22.

Let $\mathsf{}$ be a matrix-to-relational schema encoding on $\mathsf{}$ such
that $\mathsf{}(\mathbf{A})$ is a nullary relation if $\mathbf{A}$ is of
scalar type and a unary relation if $\mathbf{A}$ is of vector type (but not
scalar), for every $\mathbf{A}\in\mathsf{}$. Let
$\mathbf{v}_{1}\colon(\alpha_{1},1),\allowbreak\dots,\mathbf{v}_{k}\colon(\alpha_{k},1)$
be iterator variables.

Then for every $\mathsf{conj}\text{-}\mathsf{MATLANG}$ expression
$e(\mathbf{v}_{1},\ldots,\mathbf{v}_{k})$ the simulating
$\mathsf{FO}^{\wedge}_{=}$ formula $\overline{e}[x,y,w_{1},\ldots,w_{k}]$
obtained by Proposition 4.5 is such that:

  * •

If $0\in\texttt{FixDim}(e)$ then $x$ is bounded in $\overline{e}$ or it
appears as $x\leq 1$ in $\overline{e}$.

  * •

If $1\in\texttt{FixDim}(e)$ then $y$ is bounded in $\overline{e}$ or it
appears as $y\leq 1$ in $\overline{e}$.

######  Proof 9.23.

We follow the proof of Proposition 4.5 but retricted to
$\mathsf{FO}^{\wedge}_{=}$. The proof is by induction on the structure of $e$.
In each case, we illustrate why if $0\in\texttt{FixDim}(e)$ then $x$ is
bounded in $\overline{e}$ or it appears as $x\leq 1$ in $\overline{e}$. The
case when $1\in\texttt{FixDim}(e)$ is analogous.

Denote $\mathsf{}(\mathbf{A})$ by $A$, for every matrix symbol
$\mathbf{A}\in\mathsf{}$, and denote the constant symbol $\mathsf{}(\alpha)$
simply by $\alpha$, for every size symbol $\alpha$. (Recall that
$\mathsf{}(1)=1$ by definition.)

Let $e\in\mathsf{conj}\text{-}\mathsf{MATLANG}$ such that
$0\in\texttt{FixDim}(e)$. We show by induction that $x$ is bounded in
$\overline{e}$ or it appears as $x\leq 1$ in $\overline{e}$.

  * •

If $e=\mathbf{A}$ we have two subcases.

    * –

When $A$ is binary then $\overline{e}[x,y]\coloneqq A(x,y)$, where $x$ appears
in $A$ and is hence bounded.

    * –

When $A$ is unary, if $\mathbf{A}\colon(\alpha,1)$ then
$\overline{e}[x,y]\coloneqq A(x)\wedge y\leq 1$, where $x$ appears in $A$ and
is hence bounded. Otherwise, if $\mathbf{A}\colon(1,\alpha)$ then
$\overline{e}[x,y]\coloneqq x\leq 1\wedge A(y)$, and $x$ appears as $x\leq 1$.

    * –

When $A$ is nullary, then $\overline{e}[x,y]\coloneqq A()\wedge x\leq 1\wedge
y\leq 1$, and $x$ appears as $x\leq 1$.

  * •

If $e=\mathbf{v}_{p}\colon(\alpha_{p},1)$ then $\overline{e}[x,y,z]\coloneqq
x\leq\alpha_{p}\wedge y\leq 1\wedge x=z$. Since
$0\notin\texttt{FixDim}(v_{p})$ the claim follows. Here it is importat to
mention that since $1\in\texttt{FixDim}(e)$ we indeed have that $y$ appears as
$y\leq 1$.

  * •

If $e=e_{1}(\mathbf{v}_{1},\ldots,\mathbf{v}_{k})^{T}$ then since
$0\in\texttt{FixDim}(e)$ it is the case that $1\in\texttt{FixDim}(e_{1})$. By
induction there exists a $\mathsf{FO}^{+}_{=}$ formula
$\overline{e}_{1}[y,x,w_{1},\ldots,w_{k}]$ that simulates
$e_{1}(\mathbf{v}_{1},\ldots,\mathbf{v}_{k})$ such that $x$ is bounded in
$\overline{e}$ or it appears as $x\leq 1$ in $\overline{e}$. Then
$\overline{e}[x,y,w_{1},\ldots,w_{k}]\coloneqq\overline{e}_{1}[y,x,w_{1},\ldots,w_{k}]$,
where trivially $x$ is bounded or it appears as $x\leq 1$.

  * •

If $e=e_{1}\odot e_{2}$ then since $0\in\texttt{FixDim}(e)$ we have that
$0\in\texttt{FixDim}(e_{1})$ or $0\in\texttt{FixDim}(e_{2})$. We show the case
when $0\in\texttt{FixDim}(e_{1})$ because the other case is analogous. Assume
that $\mathbf{v}_{1},\ldots,\mathbf{v}_{\ell}$ are the vector variables shared
between $e_{1}$ and $e_{2}$; $\mathbf{v}_{i_{1}},\dots,\mathbf{v}_{i_{p}}$ are
the vector variables occurring only in $e_{1}$ and
$\mathbf{v}_{j_{1}},\dots,\mathbf{v}_{j_{q}}$ occur only in $e_{2}$. By
inductive hypothesis there exists an $\mathsf{FO}^{+}_{=}$ formula
$\overline{e}_{1}[x,y,w_{1},\ldots,w_{\ell},w_{i_{1}},\dots,w_{i_{p}}]$ that
simulates
$e_{1}(\mathbf{v}_{1},\ldots,\mathbf{v}_{\ell},\mathbf{v}_{i_{1}},\dots,\mathbf{v}_{i_{p}})$
and $x$ is bounded in $\overline{e}_{1}$ or it appears as $x\leq 1$ in
$\overline{e}_{1}$. Also, there exists an $\mathsf{FO}^{+}_{=}$ formula
$\overline{e}_{2}[x,y,w_{1},\ldots,w_{\ell},w_{j_{1}},\dots,w_{j_{q}}]$ that
simulates
$e_{2}(\mathbf{v}_{1},\ldots,\mathbf{v}_{\ell},\mathbf{v}_{j_{1}},\dots,\mathbf{v}_{j_{q}})$.
Then the simulating $\mathsf{FO}^{+}_{=}$ formula is

$\overline{e}[x,y,w_{1},\ldots,w_{k}]\coloneqq\overline{e}_{1}[x,y,w_{1},\ldots,w_{\ell},w_{i_{1}},\dots,w_{i_{p}}]\\\
\wedge\overline{e}_{2}[x,y,w_{1},\ldots,w_{\ell},w_{j_{1}},\dots,w_{j_{q}}]$

where $x$ is bounded or it appears as $x\leq 1$.

  * •

If $e=e_{1}\times e_{2}$ then since $0\in\texttt{FixDim}(e)$ we have that
$0\in\texttt{FixDim}(e_{2})$. Assume that
$\mathbf{v}_{1},\ldots,\mathbf{v}_{\ell}$ are the vector variables shared
between $e_{1}$ and $e_{2}$; $\mathbf{v}_{i_{1}},\dots,\mathbf{v}_{i_{p}}$ are
the vector variables occurring only in $e_{1}$ and
$\mathbf{v}_{j_{1}},\dots,\mathbf{v}_{j_{q}}$ occur only in $e_{2}$. By
inductive hypothesis there exists an $\mathsf{FO}^{+}_{=}$ formula
$\overline{e}_{1}[x,y,w_{1},\ldots,w_{\ell},w_{i_{1}},\dots,w_{i_{p}}]$ that
simulates
$e_{1}(\mathbf{v}_{1},\ldots,\mathbf{v}_{\ell},\mathbf{v}_{i_{1}},\dots,\mathbf{v}_{i_{p}})$.
Also, there exists an $\mathsf{FO}^{+}_{=}$ formula
$\overline{e}_{2}[x,y,w_{1},\ldots,w_{\ell},w_{j_{1}},\dots,w_{j_{q}}]$ that
simulates
$e_{2}(\mathbf{v}_{1},\ldots,\mathbf{v}_{\ell},\mathbf{v}_{j_{1}},\dots,\mathbf{v}_{j_{q}})$
such that $x$ is bounded in $\overline{e}_{2}$ or it appears as $x\leq 1$ in
$\overline{e}_{2}$. Then the simulating $\mathsf{FO}^{+}_{=}$ formula is

$\overline{e}[x,y,w_{1},\ldots,w_{k}]\coloneqq\overline{e}_{1}[x,y,w_{1},\ldots,w_{\ell},w_{i_{1}},\dots,w_{i_{p}}]\\\
\wedge\overline{e}_{2}[x,y,w_{1},\ldots,w_{\ell},w_{j_{1}},\dots,w_{j_{q}}].$

where trivially $x$ is bounded or it appears as $x\leq 1$.

  * •

If $e=e_{1}(\mathbf{v}_{1},\ldots,\mathbf{v}_{p})\cdot
e_{2}(\mathbf{u}_{1},\ldots,\mathbf{u}_{q})$ then since
$0\in\texttt{FixDim}(e)$ we have that $0\in\texttt{FixDim}(e_{1})$. Assume
that $\mathbf{v}_{1},\ldots,\mathbf{v}_{\ell}$ are the vector variables shared
between $e_{1}$ and $e_{2}$; $\mathbf{v}_{i_{1}},\dots,\mathbf{v}_{i_{p}}$ are
the vector variables occurring only in $e_{1}$ and
$\mathbf{v}_{j_{1}},\dots,\mathbf{v}_{j_{q}}$ occur only in $e_{2}$. By
inductive hypothesis there exists an $\mathsf{FO}^{+}_{=}$ formula
$\overline{e}_{1}[x,y,w_{1},\ldots,w_{\ell},w_{i_{1}},\dots,w_{i_{p}}]$ that
simulates
$e_{1}(\mathbf{v}_{1},\ldots,\mathbf{v}_{\ell},\mathbf{v}_{i_{1}},\dots,\mathbf{v}_{i_{p}})$
that $x$ is bounded in $\overline{e}_{1}$ or it appears as $x\leq 1$ in
$\overline{e}_{1}$. Also, there exists an $\mathsf{FO}^{+}_{=}$ formula
$\overline{e}_{2}[x,y,w_{1},\ldots,w_{\ell},w_{j_{1}},\dots,w_{j_{q}}]$ that
simulates
$e_{2}(\mathbf{v}_{1},\ldots,\mathbf{v}_{\ell},\mathbf{v}_{j_{1}},\dots,\mathbf{v}_{j_{q}})$.
Then the simulating $\mathsf{FO}^{+}_{=}$ formula is

$\overline{e}[x,y,w_{1},\ldots,w_{k}]\coloneqq\exists
z.\overline{e}_{1}[x,z,w_{1},\ldots,w_{\ell},w_{i_{1}},\dots,w_{i_{p}}]\\\
\wedge\overline{e}_{2}[z,y,w_{1},\ldots,w_{\ell},w_{j_{1}},\dots,w_{j_{q}}].$

where trivially $x$ is bounded or it appears as $x\leq 1$.

  * •

If
$e=\Sigma\mathbf{v}_{p}.e_{1}(\mathbf{v}_{1},\ldots,\mathbf{v}_{p},\ldots,\mathbf{v}_{k})$
then since $0\in\texttt{FixDim}(e)$ we have that $0\in\texttt{FixDim}(e_{1})$.
By inductive hypothesis we have that there exists an $\mathsf{FO}^{+}_{=}$
formula $\overline{e}_{1}[x,y,w_{1},\ldots,w_{k}]$ that simulates
$e_{1}(\mathbf{v}_{1},\ldots,\mathbf{v}_{k})$ such that $x$ is bounded in
$\overline{e}_{1}$ or it appears as $x\leq 1$ in $\overline{e}_{1}$. Then the
simulating $\mathsf{FO}^{+}_{=}$ formula is

$\displaystyle\overline{e}[x,y,w_{1},\ldots,w_{p-1},w_{p+1},\ldots,w_{k}]$
$\displaystyle\coloneqq\exists
w_{p}.\overline{e}_{1}[x,y,w_{1},\ldots,w_{k}].$

where trivially $x$ is bounded or it appears as $x\leq 1$.

A necessary ingredient to prove the lower bound is to have _enumeration-
suited_ matrix-to-relational encodings.

######  Definition 9.24.

A matrix-to-relational encoding $\mathsf{}$ is _enumeration-suited_ for a
$\mathsf{conj}\text{-}\mathsf{MATLANG}$ query
$\mathbf{Q}\coloneqq\mathbf{H}=e$ if

  1. 1.

$\mathsf{}(\mathbf{A})$ is a nullary relation if $\mathbf{A}$ is of scalar
type and a unary relation if $\mathbf{A}$ is of vector type (but not scalar),
for every
$\mathbf{A}\in\mathsf{}\\!\left(\mathbf{Q}\right)\setminus\mathbf{H}$.

  2. 2.

$\mathsf{}(\mathbf{H})$ is a binary relation.

The following result is now at hand.

######  Proposition 9.25.

Let $\mathbf{Q}\coloneqq\mathbf{H}=e$ be a
$\mathsf{conj}\text{-}\mathsf{MATLANG}$ query such that $e$ has guarded
dimensions and does not repeat matrix symbols. Let $\mathsf{}$ be a matrix-to-
relational schema encoding enumeration-suited for $\mathbf{Q}$.

Then there exists an self-join free CQ $Q$ that simulates $\mathbf{Q}$ w.r.t.
$\mathsf{}$ where $Q$ is such that for every uncovered inequality $y\leq c$
with $c\neq 1$ it holds that $y$ is not free in $Q$.

######  Proof 9.26.

By definition $e$ does not have free variables. Since
$\texttt{FixDim}(e)=\\{0,1\\}$ by Lemma 9.22 there exists
$\overline{e}[x,y]\in\mathsf{FO}^{\wedge}_{=}$ that simulates $e$ such that:

  * •

$x$ is bounded in $\overline{e}$ or it appears as $x\leq 1$ in $\overline{e}$.

  * •

$y$ is bounded in $\overline{e}$ or it appears as $y\leq 1$ in $\overline{e}$.

It is readily verified by looking at the construction of $\overline{e}$ that,
because $e$ does not repeat matrix symbols, no relation symbol occurs twice in
$\overline{e}$ (and hence $Q^{\prime}$).

It suffices to define $Q^{\prime}\colon H(x,y)\leftarrow\overline{e}[x,y]$
because hypothesis $H$ is binary. In any case, in $Q^{\prime}$

  * •

$x$ is bounded in $\overline{e}$ or it appears as $x\leq 1$, and

  * •

$y$ is bounded in $\overline{e}$ or it appears as $y\leq 1$.

It is easy to see that this implies that for every uncovered inequality $y\leq
c$ with $c\neq 1$ it holds that $y$ is not free in $Q^{\prime}$.

An $\mathsf{FO}^{\wedge}$ query $Q$ equivalent to $Q^{\prime}$ exists by
Proposition 4.2. This query hence necessarily simulates $\mathbf{Q}$ w.r.t
$\mathsf{}$ and either free variable $x,y$ still remains bounded or appears as
$x\leq 1$ or $y\leq 1$, respectively. The only problem may arise if $x$ is
replaced by $y$ or viceversa. This can only happen if the identity is involved
and therefore either both $x,y$ are bounded or both appear as $x\leq 1$ and
$y\leq 1$ originally, due to well-typedness.

Hence for every uncovered inequality $y\leq c$ with $c\neq 1$ it holds that
$y$ is not free in $Q$. Additionally, since $Q^{\prime}$ is self-join free, so
is $Q$.

To prove the lower bound for $\mathsf{conj}\text{-}\mathsf{MATLANG}$, we
require the following Lemma.

######  Proposition 9.27.

Let $\mathbf{Q}$ be a $\mathsf{conj}\text{-}\mathsf{MATLANG}$ query over
$\mathsf{}$ and let $\mathsf{}$ be a matrix-to-relational encoding scheme
$\mathsf{}$ over $\mathsf{}$ such that it is enumeration-suited for
$\mathbf{Q}$. If $\mathbf{Q}$ has guarded dimension and does not repeat matrix
symbols then there exists a self-join free binary CQ $Q$ over
$\mathsf{}=\mathsf{}(\mathsf{})$ that simulates $\mathbf{Q}$ w.r.t.
$\mathsf{}$. Moreover, $Q$ does not have covered inequalities of the form
$x\leq 1$ and for every uncovered inequality $y\leq c$ with $c\neq 1$ it holds
that $y$ is not free in $Q$.

######  Proof 9.28.

Let $\mathbf{Q}$ and $\mathsf{}$ be as claimed. Let
$\mathsf{}=\mathsf{}(\mathsf{})$ and let $\mathsf{}=\mathsf{}^{-1}$ be the
corresponding inverse relational-to-matrix encoding scheme.

By Proposition 9.25 there exists a self-join free binary conjunctive query $Q$
over $\mathsf{}$ that simulates $\mathbf{Q}$ under $\mathsf{}$ such that for
every uncovered inequality $y\leq c$ with $c\neq 1$ that appears in $Q$ it
holds that $y$ is not free in $Q$. Moreover, $Q$ is well-typed w.r.t.
$\mathsf{}$ (see Proposition 4.5 and Proposition 4.1).

We proceed to prove that $Q$ does not have covered inequalities of the form
$x\leq 1$ by noting that for all covered inequalities $x\leq c$ in $Q$ we have
$c\not=1$. Let $\varphi=\exists\overline{z}.\psi$ be the body of $Q$ with
$\psi$ quantifier free. Because $Q$ is well-typed under $\mathsf{}$, so is
$\psi$. Let $\tau$ be the unique type assignment such that
$\mathsf{}\vdash\psi\colon\tau$.

Indeed, if $R(\overline{y})$ covers $x\leq 1$ then $x$ occurs in
$\overline{y}$. Moreover, because $\psi$ is well-typed and $x\leq 1$ is an
inequality in $\psi$ we have $\tau(x)=\mathsf{}(1)=1$ by the typing rule for
inequalities and the definition of relational-to-matrix encoding schemes. Let
$\mathbf{A}$ be the matrix symbol such that $\mathsf{}(\mathbf{A})=R$; in
particular, $\mathsf{}(R)=\mathbf{A}$. Because $R(\overline{y})$ occurs in
$\psi$ and $\psi$ is well-typed we know that $\mathsf{}\vdash
R(\overline{y})\colon\tau$. This means that the type of
$\mathsf{}(R)=\mathbf{A}$ in the position of $x$ in $R$ must be $\tau(x)=1$.
But then $\mathbf{A}$ is either a scalar or a vector. But note that in this
case we chose $\mathsf{}$ such that $R=\mathsf{}(\mathbf{A})$ has no column to
specify $x$ in, which yields a contradiction.

The following theorem implies Corollary 7 in Section 7.

######  Theorem 9.29.

Let $\mathbf{Q}$ be a $\mathsf{conj}\text{-}\mathsf{MATLANG}$ query over
$\mathsf{}$ such that $\mathbf{Q}$ has guarded dimensions and does not repeat
matrix symbols. Let $\mathcal{K}$ be a semiring such that the subsemiring
generated by $\mymathbb{0}$ and $\mymathbb{1}$ is non-trivial and zero-sum
free. If
$\texttt{Eval}(\mathbf{Q},\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\mathcal{I}\\!\parallel,1)$,
then $\mathbf{Q}$ is equivalent to a $\mathsf{fc}\text{-}\mathsf{MATLANG}$
query, unless either the Sparse Boolean Matrix Multiplication, the Triangle
Detection, or the $(k,k+1)$-Hyperclique conjecture is false.

######  Proof 9.30.

Let $\mathsf{}$ be a matrix-to-relational encoding scheme over $\mathsf{}$
such that is enumeration-suited for $\mathbf{Q}$. Let
$\mathsf{}=\mathsf{}^{-1}$ be its inverse relational-to-matrix encoding.

We apply Proposition 9.27 on $\mathbf{Q}$ to obtain binary CQ $Q$ over
$\mathsf{}=\mathsf{}(\mathsf{})$ that simulates $\mathbf{Q}$ w.r.t.
$\mathsf{}$. We know that $Q$ is binary and self-join free; does not have
covered inequalities of the form $x\leq 1$; and for every uncovered inequality
$y\leq c$ with $c\neq 1$ it holds that $y$ is not free in $Q$. We next modify
$Q$ into a query $Q^{\prime}$ over $\mathsf{}$ such that the following
properties hold:

  1. (P1)

$Q^{\prime}$ continues to simulate $\mathbf{Q}$ w.r.t. $\mathsf{}$;

  2. (P2)

$Q^{\prime}$ is constant-disjoint;

  3. (P3)

$\texttt{Eval}(Q^{\prime},\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$.

This suffices to proof the proposition. Indeed, by Theorem 9.19 $Q^{\prime}$
is necessarily free-connex unless unless either the Sparse Boolean Matrix
Multiplication, the Triangle Detection, or the $(k,k+1)$-Hyperclique
conjecture is false. If $Q^{\prime}$ is free-connex, then by Corollary 5.39
there exists a $\mathsf{fc}\text{-}\mathsf{MATLANG}$ query
$\mathbf{Q}^{\prime}$ that simulates $Q^{\prime}$ w.r.t
$\mathsf{}=\mathsf{}^{-1}$. Consequently, $\mathbf{Q}$ and
$\mathbf{Q}^{\prime}$ are then equivalent.

Intuitively, the modification of $Q$ into $Q^{\prime}$ is necessary to obtain
property (P3): the fact that
$\texttt{Eval}(\mathbf{Q},\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\mathcal{I}\\!\parallel,1)$
only implies that we may evaluate $Q$ with linear time preprocessing and
constant delay _on databases that encode some matrix instance_. To apply
Theorem 9.19, by contrast we need to show that we can evaluate $Q$ on
_arbitrary databases_. The crux will be that we obtain $Q^{\prime}$ by adding
extra inequalities to $Q$, such that evaluating $Q^{\prime}$ on an arbitrary
database yields the same result as evaluating it (and $Q$, $\mathbf{Q}$) on
some matrix instance.

The definition of $Q^{\prime}$ is as follows. Assume $Q$ is of the form
$Q:H(\overline{y})\leftarrow\exists\overline{z}.\psi$ with $\psi$ quantifier
free. For every relational atom $\alpha=R(\overline{x})$ of $\psi$ we define a
formula $\varphi_{\alpha}$ as follows. This formula is a conjunction of
inequalities:

  * •

If $\alpha=R(x_{1},x_{2})$ with $R$ binary and
$\mathsf{}(R)\colon(\beta,\gamma)$ then
$\varphi_{\alpha}:=x_{1}\leq\mathsf{}(\beta)\wedge
x_{2}\leq\mathsf{}(\gamma)$. Note that, by definition of $\mathsf{}$,
$\mathsf{}(\alpha)\not=1\not=\mathsf{}(\beta)$.

  * •

If $\alpha=R(x_{1})$ with $R$ unary then by definition of $\mathsf{}$ we have
$\mathsf{}(R)\colon(\beta,1)$ or $\mathsf{}(R)\colon(1,\beta)$ for some size
symbol $\beta\not=1$. Then take $\varphi_{\alpha}:=x_{1}\leq\mathsf{}(\beta)$.
Note that by definition of matrix-to-relational encoding schemes,
$\mathsf{}(\beta)\not=1$ since $\beta\not=1$.

  * •

If $\alpha=R()$ with $R$ nullary then by definition of $\mathsf{}$ we have
$\mathsf{}(R)\colon(1,1)$ and we take $\varphi_{\alpha}$ the empty formula
(which is equivalent to true).

Then we define $Q^{\prime}$ to be the CQ

$Q^{\prime}\colon H(\overline{y})\leftarrow\exists
z.(\psi\wedge\bigwedge_{\alpha\text{ rel. atom in }\psi}\varphi_{\alpha}).$

Note that $Q^{\prime}$ continues to simulate $\mathbf{Q}$ over $\mathsf{}$
(property P1). Indeed, for any matrix instance $\mathcal{I}$ over $\mathsf{}$
we know that
$\texttt{Answer}(\mathbf{Q},\mathcal{I})=\texttt{Answer}(Q,\mathsf{}(\mathcal{I}))$.
By definition, $\mathsf{}(\mathcal{I})$ is consistent with
$\mathsf{}^{-1}=\mathsf{}$, and therefore the tuples in
$\mathsf{}(\mathcal{I})$ vacuously satisfy all the extra inequalities that we
have dded to $Q$ to obtain $Q^{\prime}$. As such,
$\texttt{Answer}(Q,\mathsf{}(\mathcal{I}))=\texttt{Answer}(Q^{\prime},\mathsf{}(\mathcal{I}))$.
Thus, $Q^{\prime}$ continues to simulate $\mathbf{Q}$.

Also note that $Q^{\prime}$ is constant-disjoint (property P2). Indeed:

  * •

We have only added covered inequalities to $Q$ to obtain $Q^{\prime}$. Any
such covered inequality that we have added was of the form $x\leq c$ with
$c\not=1$. Therefore, since $Q$ does not have covered inequalities of the form
$x\leq 1$, neither does $Q^{\prime}$.

  * •

We did not add any uncovered inequalities to $Q$ to obtain $Q^{\prime}$.
Moreover, $Q^{\prime}$ has the same free variables as $Q$. Therefore, all
uncovered inequalities $y\leq c$ in $Q^{\prime}$ continue to be such that $y$
is not free in $Q^{\prime}$, unless $c=1$. Hence for all pairs $(x\leq c,y\leq
d)$ of covered inequality $x\leq c$ and non-covered inequality $y\leq d$ with
$d\neq 1$ in $Q^{\prime}$ we have that $y$ is not free in $Q^{\prime}$ as
required for constant-disjointness.

Finally, we show that
$\texttt{Eval}(Q^{\prime},\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$
(property P3), as claimed. We do this by reducing
$\texttt{Eval}(Q^{\prime},\mathsf{},\mathcal{K})$ to
$\texttt{Eval}(\mathbf{Q},\mathsf{},\mathcal{K})$ as follows. Let db be a
$\mathcal{K}$-database over $\mathsf{}$, input to
$\texttt{Eval}(Q^{\prime},\mathsf{},\mathcal{K})$. First, create the database
$\textit{db}^{\prime}$ that is equal to db except that for every relation
symbol $R\in\mathsf{}$ that is not mentioned in $Q$ we set
$R^{\textit{db}^{\prime}}$ to empty. This can clearly be done in linear time.
Note that, if $R$ is not mentioned in $Q$, then the answer of $Q$ on db is
independent of the contents of $R^{\textit{db}}$. Therefore,
$\texttt{Answer}(Q^{\prime},\textit{db})=\texttt{Answer}(Q^{\prime},\textit{db}^{\prime})$.
Subsequently, compute $\textit{db}^{\prime\prime}$, the atomic reduction of
$\textit{db}^{\prime}$ w.r.t. $Q$. Computing $\textit{db}^{\prime\prime}$ can
be done in time
$\mathsf{}(\parallel\\!\textit{db}^{\prime}\\!\parallel)=\mathsf{}(\parallel\\!\textit{db}\\!\parallel)$.
(See Definition 9.7 and the discussion following.) By Claim 1 we have
$\texttt{Answer}(Q^{\prime},\textit{db})=\texttt{Answer}(Q^{\prime},\textit{db}^{\prime})=\texttt{Answer}(Q^{\prime},\textit{db}^{\prime\prime})$.
Now verify the following claim: $\textit{db}^{\prime\prime}$ is consistent
w.r.t. $\mathsf{}=\mathsf{}^{-1}$. This is because we have added, for each
matrix symbol $\mathbf{A}$ with $\mathsf{}(\mathbf{A})$ occurring in $Q$, the
inequalities that are required by consistency as atomic inequalities to
$Q^{\prime}$. (The matrix symbols $\mathbf{A}$ with $\mathsf{}(\mathbf{A})$
not occurring in $Q$ are empty in $\textit{db}^{\prime}$ and hence vacuously
consistent w.r.t. $\mathsf{}$.) Since $\textit{db}^{\prime\prime}$ is
consistent with $\mathsf{}$ we have that
$\mathsf{}(\textit{db}^{\prime\prime})$ is a matrix instance over $\mathsf{}$
and hence a valid input to $\mathbf{Q}$. Then, because $Q^{\prime}$ simulates
$\mathbf{Q}$, we have
$\texttt{Answer}(Q^{\prime},\textit{db})=\texttt{Answer}(Q^{\prime},\textit{db}^{\prime\prime})=\texttt{Answer}(\mathbf{Q},\mathsf{}(\textit{db}^{\prime\prime}))$.
The last equality holds because the head of $Q^{\prime}$ is a binary relation
since $\mathsf{}$ is enumeration-suited for $\mathbf{Q}$ (see Definition
9.24).

Because $\texttt{Eval}(\mathbf{Q},\mathsf{},\mathcal{K})$ is in
$\texttt{Enum}(\parallel\\!\mathcal{I}\\!\parallel,1)$ it hence follows that
with additional preprocessing of time
$\mathsf{}(\parallel\\!\mathsf{}(\textit{db}^{\prime\prime})\\!\parallel)=\mathsf{}(\parallel\\!\textit{db}\\!\parallel)$
we may enumerate
$\texttt{Answer}(Q^{\prime},\textit{db}^{\prime\prime})=\texttt{Answer}(Q^{\prime},\textit{db})$
with constant delay, as desired.

##  10 Upper bound and lower bound for q-hierachical CQ on general semirings
and with inequality predicates

###  10.1 Background and extra preliminaries.

In this section we provide extra background and definitions regarding query
processing under updates.

#### Dynamic enumeration problems

A _dynamic enumeration problem_ is an enumeration problem $P$ together with a
set $U$ of _updates_ on $P$’s inputs: a set of operations such that applying
an update $u\in U$ to an input $I$ of $P$ yields a new input to $P$, denoted
$I+u$. An algorithm $A$ _solves_ a dynamic enumeration problem $D=(P,U)$ if it
solves the enumeration problem $P$ (computing, for each input $I$ a data
structure in a preprocessing phase from which $P(I)$ may be enumerated) and,
moreover, it is possible, for every input $I$ and update $u$ to update the
data structure that $A$ computed on $I$ during the update phase to a data
structure for $I+u$. By definition, the latter updated data structure hence
allows to enumerate $P(I+u)$. The preprocessing time and enumeration delay of
$A$ are defined as for normal (static) enumeration problems. The _update time_
of $A$ is an upper bound on the time needed to update the data structure for
$I$ into one for $I+u$.

#### Dynamic Query Evaluation

In our setting, we consider dynamic query evaluation as a dynamic enumeration
problem. Specifically, we consider the following set $U$ of updates. Let
$\mathcal{K}=(K,\oplus,\odot,\mymathbb{0},\mymathbb{1})$ be a semiring and
$\mathsf{}$ be a vocabulary.

  * •

A single-tuple _insertion_ (over $K$ and $\mathsf{}$) is an expression
$u=\texttt{insert}(R,\overline{d},k)$ with $R\in\mathsf{}$ a relation symbol,
$\overline{d}$ a tuple of arity $\mathsf{}(R)$, and $k\in K$. When applied to
a $\mathcal{K}$ database db over vocabulary $\mathsf{}$ it induces the
$\mathcal{K}$ database $\textit{db}+u$ that is identical to db, but
$R^{\textit{db}+u}(\overline{d})=R^{\textit{db}}(\overline{d})\oplus k$.

  * •

A single-tuple _deletion_ (over $K$ and $\mathsf{}$) is an expression
$u=\texttt{delete}(R,\overline{d})$ with $R\in\mathsf{}$ a relation symbol and
$\overline{d}$ a tuple of arity $\mathsf{}(R)$. When applied to a
$\mathcal{K}$ database db over vocabulary $\mathsf{}$ it induces the
$\mathcal{K}$ database $\textit{db}+u$ that is identical to db, but
$R^{\textit{db}+u}(\overline{d})=\mymathbb{0}$.

In this appendix we will consider two versions of the dynamic query evaluation
problem for conjunctive query $Q$ over $\mathsf{}$ under semiring
$\mathcal{K}$:

  * •

The _unbounded_ version, $\texttt{DynEval}(Q,\mathsf{},\mathcal{K})$ which is
the dynamic enumeration problem $(\texttt{Eval}(Q,\mathsf{},\mathcal{K}),U)$
with $U$ the set of all single-tuple insertions and deletions over
$\mathcal{K}$ and $\mathsf{}$.

  * •

The _bounded_ version, denoted $\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$,
where $M\in\mathbb{N}_{\geq 0}$ is a constant positive natural number, and
which is defined as follows.

Define $\texttt{Eval}(Q,\mathsf{},\mathcal{K},M)$ to be the bounded version of
the _static_ query evaluation problem: this is the collection of all pairs
$(I,O)$ with $I=\textit{db}$ with db a $\mathcal{K}$-database over $\mathsf{}$
_such that any data value $d$ occurring in db is at most $M$, i.e., $d\leq
M$_777Recall that the set of data values that may appear in database tuples
equals $\mathbb{N}_{\geq 0}$., and $O=\texttt{Answer}(Q,\textit{db})$. Hence,
$\texttt{Eval}(Q,\mathsf{},\mathcal{K},M)$ is the evaluation problem of $Q$ on
$\mathcal{K}$-databases whose values in the active domain are bounded by $M$.

Then the bounded dynamic evaluation problem
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$ is the dynamic enumeration
problem $(\texttt{Eval}(Q,\mathsf{},\mathcal{K},M),U)$ with $U$ the set of all
single-tuple updates $\texttt{insert}(R,\overline{d},k)$ or
$\texttt{delete}(R,\overline{d})$ where every value $d\in\overline{d}$
satisfies $d\leq M$.

Clearly,
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})=\bigcup_{M=1}^{\infty}\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$.

#### Complexity classes

For functions $f,g$, and $h$ from the natural numbers to the positive reals we
define $\texttt{DynEnum}(f,g,h)$ to be the class of dynamic enumeration
problems $(P,U)$ for which there exists an enumeration algorithm $A$ such that
for every input $I$ it holds that the preprocessing time is
$\mathsf{}\left(f(\parallel\\!I\\!\parallel)\right)$, the delay is
$\mathsf{}\left(g(\parallel\\!I\\!\parallel)\right)$, where
$\parallel\\!I\\!\parallel$ denotes the size of $I$. Moreover, processing
update $u$ on current input $I$ takes time
$\mathsf{}(\left(h(\parallel\\!I\\!\parallel,\parallel\\!u\\!\parallel)\right)$.
Note that, since the inputs in a dynamic evaluation problem
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})$ or
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$ consists only of the database
and not the query, we hence measure complexity in _data complexity_ as is
standard in the literature [BaganDG07, Vansummeren2020, berkholz2020constant,
BerkholzKS17].

In what follows we set the size $\parallel\\!u\\!\parallel$ of a single-tuple
update $u$ to $1$: each update is of constant size, given the fixed vocabulary
$\mathsf{}$.

We note that, because
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})=\bigcup_{M=1}^{\infty}\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$
if
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
then also
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$,
for every $M$. Conversely, if
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)\not\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
for some $M$, then also
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})\not\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$.
Specifically, we will use the bounded evaluation problem
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$ to obtain our lower bounds.

#### Discussion

As the reader may have noticed, updates allow to modify the contents of
relations, but not of constant symbols. This is because an update to a
constant translates as an update to the dimension value of a matrix within the
equivalent linear algebra setting. And updates in the linear algebra setting
affect only entry values, not dimensions. An interesting line of future work
is to consider dimension updates.

#### Complexity Hypothesis and known results.

Like the authors of [henzinger2015unifying, BerkholzKS17] we use the following
hypothesis concerning the hardness of dynamic problems as hypothesis for
obtaining conditional lower bounds:

  * •

The Online Boolean Matrix-Vector Multiplication problem
[henzinger2015unifying, berkholz2020constant]: given an $n\times n$ boolean
matrix $A$, compute $A\cdot v_{1},\ldots,A\cdot v_{n}$ sequentally for
$n\times 1$ vectors $v_{1},\ldots,v_{n}$. It is required that the result of
$A\cdot v_{i-1}$ must already be computed in order to access $v_{i}$. The _OMv
conjecture_ states that this problem cannot be solved in time
$\mathsf{}(n^{3-\varepsilon})$ for any $\varepsilon>0$.

######  Theorem 10.1 ([BerkholzKS17]).

Let $Q$ be a $\text{CQ}^{\not\leq}$ over $\mathsf{}$.

  * •

If $Q$ is q-hierarchical, then
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B})\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$.

  * •

If $Q$ is a query without self joins and
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
for every $M\in\mathbb{N}_{>0}$, then $Q$ is q-hierarchical (unless the $OMv$
conjecture is false).

Analogous to the free-connex case, we aim to extend Theorem 10.1 to general CQ
(which use inequality atoms) and to a more general kind of semirings.

On one hand, for the upper bound it suffices to (1) extend the current result
to sum-maintainable semi-integral domains, and (2) show that the former also
holds for general CQs. On the other hand, for the lower bound it is necessary
to (1) reduce the dynamic evaluation problem of a CQ without inequalities over
the Boolean semiring to that of a general CQ over the boolean semiring, and
(2) reduce the maintenance problem of a general CQ over the boolean semiring
to the maintenance problem of a general CQ over a semiring for which the
subsemiring generated by its $\mymathbb{0}$ and its $\mymathbb{1}$ is non-
trivial and zero-sum free.

#### Q-hierarchicality

For later use we observe the following property. Recall the definition of a
q-hierarchical CQ. Let $Q\colon
H(\overline{x})\leftarrow\exists\overline{y}.a_{1}\wedge\ldots\wedge a_{n}$ be
a CQ and let, for every variable $x$, $\mathsf{}(x)$ be the set $\\{a_{i}\mid
x\in\mathsf{}(a_{i})\\}$ of _relational_ atoms that mention $x$. Then $Q$ is
q-hierarchical if for any two variables $x,y$ the following is satisfied

  1. 1.

$\mathsf{}(x)\subseteq\mathsf{}(y)$ or $\mathsf{}(x)\supseteq\mathsf{}(y)$ or
$\mathsf{}(x)\cap\mathsf{}(y)=\emptyset$,

  2. 2.

if $x\in\overline{x}$ and $\mathsf{}(x)\subsetneq\mathsf{}(y)$ then
$y\in\overline{x}$.

Because the former conditions are imposed over relational atoms, the following
result is straightforward. Recall the definition of $\texttt{split}(Q)$ given
in Definition 9.4.

######  Corollary 10.2.

Let $Q$ be a CQ and $\texttt{split}(Q)=(Q_{\text{rel}},Q_{\text{ineq}})$. Then
$Q$ is q-hierarchical if and only if $Q_{\text{rel}}$ is q-hierarchical.

###  10.2 Upper bound

######  Proposition 10.3.

Let $Q$ be a q-hierarchical $\text{CQ}^{\not\leq}$ over $\mathsf{}$ and
$\mathcal{K}$ a sum-maintainable semi-integral domain. Then
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$.

######  Proof 10.4.

Note that since $Q$ is q-hierarchical it has a guarded query plan $(T,N)$ by
Proposition 6.1. This implies in particular that $Q$ is also free-connex. By
Proposition 9.2 we hence know that
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$.
As such, there is an algorithm $A$ that, given db builds a data structure in
linear time from which $\texttt{Answer}(Q,\textit{db})$ can be enumerated with
constant delay. We will show that for any update $u$ to db this data structure
can also be updated in $\mathsf{}(1)$ into a data structure for
$\texttt{Answer}(Q,\textit{db}+u)$. Because, in the proof of Proposition 9.2
the algorithm (and data structure) depends on the shape of $Q$ and $(T,N)$ we
make a corresponding case analysis here.

  1. 1.

If $Q$ is a full-join, i.e., no variable is quantified, we reduce to the
Boolean case as follows. Assume that $Q=H(\overline{z})\leftarrow
R_{1}(\overline{z}_{1})\wedge\cdots\wedge R_{n}(\overline{z}_{n})$. In
$\mathsf{}(\parallel\\!\textit{db}\\!\parallel)$ time construct
$\texttt{Bool}(\textit{db})$, the $\mathbb{B}$-database obtained from db
defined as:

$R^{\texttt{Bool}(\textit{db})}\colon\overline{d}\mapsto\begin{cases}\texttt{t}\text{
if }R^{\textit{db}}(\overline{d})\neq\mymathbb{0}\\\ \texttt{f}\text{
otherwise, }\end{cases}$

for every $R\in\mathsf{}$. Furthermore, preprocess db by creating lookup
tables such that for every relation $R$ and tuple $\overline{a}$ of the
correct arity we can retrieve the annotation $R^{\textit{db}}(\overline{a})$
in time $\mathsf{}(|\overline{a}|)$ time. Note that since $\mathsf{}$ is
fixed, $|\overline{a}|$ is constant. This retrieval is hence $\mathsf{}(1)$ in
data complexity. It is well-known that such lookup tables can be created in
$\mathsf{}(\parallel\\!\textit{db}\\!\parallel)$ time in the RAM model.

Finally, invoke the algorithm for $\texttt{DynEval}(Q,\mathsf{},\mathbb{B})$
on $\texttt{Bool}(\textit{db})$. By Theorem 10.1, this algorithm has
$\mathsf{}(\parallel\\!\texttt{Bool}(\textit{db})\\!\parallel)=\mathsf{}(\parallel\\!\textit{db}\\!\parallel)$
preprocessing time, after which we may enumerate
$\texttt{Answer}(Q,\texttt{Bool}(\textit{db}))$ with $\mathsf{}(1)$ delay and
maintain this property under updates to $\texttt{Bool}(\textit{db})$ in
$\mathsf{}(1)$ time. We have shown in Proposition 9.2 that using the
enumeration procedure for $\texttt{Answer}(Q,\texttt{Bool}(\textit{db}))$ and
the lookup tables, we may also enumerate $\texttt{Answer}(Q,\textit{db})$ with
constant delay. We do not repeat this argument here.

Given a single-tuple update $u$ we update the lookup tables and the data
structure maintained by $\texttt{DynEval}(Q,\mathsf{},\mathbb{B})$ as follows.

     * •

If $u=\texttt{insert}(R,\overline{d},k)$ then lookup $\overline{d}$ in the
lookup table for $R$ and retrieve its old annotation $\ell$. (If the lookup
table does not contain $\ell$, set $\ell=\mymathbb{0}$). There are two cases
to consider:

       * –

If $k+\ell=\mymathbb{0}$ then the tuple $\overline{d}$ is now deleted from
$R^{\textit{db}+u}$ and we similarly remove it from
$\texttt{Bool}(\textit{db}+u)$ by issuing the update
$u^{\prime}=\texttt{delete}(R,\overline{d})$ to $\texttt{Bool}(\textit{db})$
(and $\texttt{DynEval}(Q,\mathsf{},\mathbb{B})$).

       * –

If $k+\ell\not=\mymathbb{0}$ then the tuple is certainly present in
$R^{\textit{db}+u}$ inserted and similarly make sure it is in
$\texttt{Bool}(\textit{db}+u)$ by issuing
$u^{\prime}=\texttt{insert}(R,\overline{d},\texttt{t})$ to
$\texttt{Bool}(\textit{db})$ (and $\texttt{DynEval}(Q,\mathsf{},\mathbb{B})$).
Note that if the tuple was already in $\texttt{Bool}(\textit{db})$ then
$u^{\prime}$ has no-effect since we are working in the boolean semiring there.

     * •

If $u=\texttt{delete}(R,\overline{d})$ then delete $\overline{d}$ from the
lookup table and issue the update $u^{\prime}=\texttt{delete}(R,\overline{d})$
to $\texttt{Bool}(\textit{db})$ and
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B})$.

Note that in all cases, after issuing $u^{\prime}$ we obtain
$\texttt{Bool}(\textit{db}+u)$ as desired, so that after this update using the
enumeration procedure for $\texttt{Answer}(Q,\texttt{Bool}(\textit{db}+u))$
and the lookup tables, we will enumerate $\texttt{Answer}(Q,\textit{db}+u)$
with constant delay.

  2. 2.

If the guarded query plan $(T,N)$ is such that $N$ consists of a single node
$N=\\{r\\}$, then by Lemma 6.2 we may assume without loss of generality that
for every node $n$ with two children $c_{1},c_{2}$ in $T$ we have
$\mathsf{}(n)=\mathsf{}(c_{1})=\mathsf{}(c_{2})$. Intuitively, the algorithm
will work as follows. We show that for any database db we may compute
$\texttt{Answer}(Q,\textit{db})$ in
$\mathsf{}(\parallel\\!\textit{db}\\!\parallel)$ time. Because we can simply
store this result, we may certainly enumerate it with constant delay. Then, by
also storing the subresults computed during the computation of
$\texttt{Answer}(Q,\textit{db})$ we show that we can also maintain
$\texttt{Answer}(Q,\textit{db})$ and all subresults in $\mathsf{}(1)$ time
under updates.

Formally the data structure used by
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})$ will be the query result itself,
plus some extra lookup tables. In particular, given input database db we:

     * •

compute, for every node $n\in T$ the
$\texttt{Answer}(\varphi[T,n]{\textit{db}},$). We have shown in Proposition
9.2 that we may compute $\texttt{Answer}(\varphi[T,n]{\textit{db}},$) in
linear time, for every node $n$. We do not repeat the argument here. Since $Q$
(and hence $T$) is fixed there are a constant number of nodes in $T$. So this
step takes linear time overall.

     * •

convene that we store $\texttt{Answer}(\varphi[T,n],\textit{db})$ for every
node $n$ by creating a lookup table such that for any tuple
$(\overline{a},k)\in\texttt{Answer}(\varphi[T,n],\textit{db})$ we can retrieve
$k$ in $\mathsf{}(1)$ time given $\overline{a}$. It is well-known that the
lookup tables can be made such that may we enumerate the entries
$(\overline{a},k)$ of this lookup table with constant delay. It is well-known
that such lookup tables can be created in time linear in
$\parallel\\!\texttt{Answer}(\varphi[T,n],\textit{db})\\!\parallel=\mathsf{}(\parallel\\!\textit{db}\\!\parallel)$.
So also this step takes linear time.

Note that by definition $Q\equiv\varphi[T,r]$; therefore the root represents
$\texttt{Answer}(Q,\textit{db})$ as desired, and can be used to enumerate the
result with constant delay.

It remains to show that given an update $u$ to db we can update
$\texttt{Answer}(\varphi[T,n]{\textit{db}},$) into
$\texttt{Answer}(\varphi[T,n]{\textit{db}+u},$) in $\mathsf{}(1)$ time, for
every node $n$. In order to be able to show this, we store one auxiliary
lookup table $L_{n}$ for all nodes $n$ that have a single child $c$. This
auxiliary table is defined as follows. By Lemma 5.9 if $n$ has a single child
$c$ then $\varphi[T,n]\equiv\exists\overline{y}.\varphi[T,c]$ with
$\overline{y}=\mathsf{}(c)\setminus\mathsf{}(n)$. The lookup table $L_{n}$
stores, for each $(\overline{d},k)$ in
$\texttt{Answer}(\varphi[T,n],\textit{db})$ a pointer to a data structure
$\mathcal{D}_{\overline{d}}$ that represents the multiset

$\\{\\{k\mid(\overline{a},k)\in\texttt{Answer}(\varphi[T_{c},c],\textit{db}),{\overline{a}}|_{\mathsf{}(r)}=\overline{d}\\}\\}.$

Because $\mathcal{K}$ is sum-maintainable, and because
$\texttt{Answer}(\varphi[T_{c},c],\textit{db})$ is linear in db, this extra
lookup table can be computed in linear time.888Initially, the lookup table is
empty. Loop over the entries $(\overline{a},k)$ of
$\texttt{Answer}(\varphi[T_{c},c],\textit{db})$ one by one. For each such
tuple, compute $\overline{d}={\overline{a}}|_{\mathsf{}(r)}$ and lookup
$\overline{d}$ in $L$. If it is present with data structure
$\mathcal{D}_{\overline{d}}$ then apply
$\texttt{ins}(k,\mathcal{D}_{\overline{d}})$, hence updating
$\mathcal{D}_{\overline{d}}$. If it is not present, initialize
$\mathcal{D}_{\overline{d}}$ to empty; add $k$ to it, and insert
$(\overline{d},\mathcal{D}_{\overline{d}})$ to the lookup table.

We now verify that for every single-tuple update $u$ to db and every node $n$
we can update $\texttt{Answer}(\varphi[T,n]{\textit{db}},$) into
$\texttt{Answer}(\varphi[T,n]{\textit{db}+u},$) in $\mathsf{}(1)$ time. The
proof is by induction on the height of $n$ in $T$. (I.e., the length of
longest path from $n$ to a leaf.)

     * •

When $n$ is a leaf, it is an atom, say $R(\overline{x})$. Upon update $u$, if
$u$ is of the form $\texttt{insert}(R,\overline{a},k)$ or
$\texttt{delete}(R,\overline{a})$ then we update the lookup table that
represents $\texttt{Answer}(\varphi[T,n]{\textit{db}},$) in the obvious way.
Such updates take $\mathsf{}(1)$ in the RAM model. If $u$ pertains to a
relation other then $R$, we simply ignore it.

     * •

When $n$ is an interior node with a single child $c$ then by Lemma 5.9 we have
$\varphi[T,n]\equiv\exists\overline{y}.\varphi[T,c]$ with
$\overline{y}=\mathsf{}(c)\setminus\mathsf{}(r)$. When we receive update $u$
to db, by inductive hypothesis this yields a bounded number of single-tuple
updates $u_{c}$ to $A=\texttt{Answer}(\varphi[T,c],\textit{db})$ which we may
compute in $\mathsf{}(1)$ time. We translate these updates $u_{c}$ into
updates $u^{\prime}$ to apply to $\texttt{Answer}(\varphi[T,n],\textit{db})$:

       * –

If $u_{c}=\texttt{insert}(\overline{a},k)$. Then apply $u_{c}$ to $A$ and
update the auxiliary lookup table $L_{n}$ by applying
$\texttt{ins}(k,\mathcal{D}_{\overline{d}})$ with
$\overline{d}={\overline{a}}|_{\mathsf{}(r)}$. Furthermore, update
$\texttt{Answer}(\varphi[T,n],\textit{db})$ by applying
$u^{\prime}=\texttt{insert}(\overline{d},k)$ to the lookup table representing
it.

       * –

If $u_{c}=\texttt{delete}(\overline{a})$. Before applying $u_{c}$ to
$A=\texttt{Answer}(\varphi[T,c],\textit{db})$, look up the old annotation $k$
of $\overline{a}$ in $A$. Then apply $u_{c}$ to $A$ and update $L_{n}$ by
applying $\texttt{del}(k,\mathcal{D}_{\overline{d}})$ with
$\overline{d}={\overline{a}}|_{\mathsf{}(r)}$. If
$\texttt{query}(\mathcal{D}_{\overline{d}})=\mymathbb{0}$, then $u$
effectively causes $\overline{d}$ to be removed from
$\texttt{Answer}(\varphi[T,n],\textit{db})$. Hence, the update $u^{\prime}$ to
apply to (the lookup table representing)
$\texttt{Answer}(\varphi[T,n],\textit{db})$ is
$u^{\prime}=\texttt{delete}(\overline{d})$. Otherwise,
$\texttt{query}(\mathcal{D}_{\overline{d}})\not=\mymathbb{0}$ and the update
$u^{\prime}$ to apply is $u^{\prime}=\texttt{insert}(\overline{d},k)$.

     * •

Node $n$ has two children $c_{1}$ and $c_{2}$. By Lemma 5.11 we have
$\varphi[T,n]\equiv\varphi[T,c_{1}]\wedge\varphi[T,c_{2}]$. Note that this
denotes an intersection since
$\mathsf{}(n)=\mathsf{}(c_{1})=\mathsf{}(c_{2})$. When we receive update $u$
to db, by inductive hypothesis this yields a bounded number of single-tuple
updates to $A_{1}=\texttt{Answer}(\varphi[T,c_{1}],\textit{db})$ and
$A_{2}=\texttt{Answer}(\varphi[T,c_{1}],\textit{db})$ which we may compute in
$\mathsf{}(1)$ time. We translate these updates to $A_{1}$ and $A_{2}$ into
updates to $\texttt{Answer}(\varphi[T,n]{\textit{db}},$) as follows. We only
show the reasoning for updates to $A_{1}$. The reasoning for updates to
$A_{2}$ is similar. Let $u_{1}$ be update to $A_{1}$. We translate this into
update $u^{\prime}$ to apply to $\texttt{Answer}(\varphi[T,n],\textit{db})$ as
follows:

       * –

if $u_{1}=\texttt{insert}(\overline{d},k_{1})$ then use the lookup table on
$A_{2}$ to find the annotation $\ell$ of $\overline{d}$ in $A_{2}$. (If
$\overline{d}$ does not appear in $A_{2}$ then take $\ell=\mymathbb{0}$). If
$k_{1}\odot\ell\not=\mymathbb{0}$ then apply
$u^{\prime}=\texttt{insert}(d,k_{1}\odot\ell)$ to
$\texttt{Answer}(\varphi[T,n],\textit{db})$; otherwise there is no update
$u^{\prime}$ to apply.

       * –

if $u_{1}=\texttt{delete}(\overline{d})$ then apply
$u^{\prime}=\texttt{delete}(d)$ to
$\texttt{Answer}(\varphi[T,n],\textit{db})$.

  3. 3.

When $Q$ is not full and $N$ has more than one node we reduce to the previous
two cases because
$\varphi[T,N]\equiv\varphi[T_{1},n_{1}]\wedge\dots\wedge\varphi[T_{l},n_{l}]$
where $F=\\{n_{1},\ldots,n_{l}\\}$ is the frontier of $N$, i.e, the nodes
without children in $N$, and $T_{1},\dots,T_{l}$ are the subtrees of $T$
rooted at $n_{1},\dots,n_{l}$ respectively. Hence, we may enumerate
$\texttt{Answer}(\varphi[T,N],\textit{db})$ with constant delay by first fully
computing $\texttt{Answer}(\varphi[T_{i},n_{i}],\textit{db})$ for $1\leq i\leq
n$ and performing the full join
$\varphi[T_{1},n_{1}]\wedge\dots\wedge\varphi[T_{l},n_{l}]$ on these
subresults. By item (2) above, each
$A_{i}:=\texttt{Answer}(\varphi[T_{i},n_{i}],\textit{db})$ can be computed in
linear time from db. Furthermore, each
$\texttt{Answer}(\varphi[T_{i},n_{i}],\textit{db})$ can be maintained under
updates in $\mathsf{}(1)$ time by item (2) above. By item (1) the result of
the final full join can be enumerated with constant delay after linear time
processing on $A_{i}$. In addition, we can maintain this property under
updates in $\mathsf{}(1)$ time by item (1) above, since this is a full join
and $\varphi[T,N]$ is q-hierarchical. Therefore, the entire result
$\texttt{Answer}(\varphi[T,N],\textit{db})$ can be enumerated with constant
delay after linear time processing, and be maintained under updates in
$\mathsf{}(1)$ time.

######  Proposition 10.5.

Let $Q$ be a CQ over $\mathsf{}$ and
$\texttt{split}(Q)=(Q_{\text{rel}},Q_{\text{ineq}})$ and $\mathcal{K}$ a semi-
integral domain. If
$\texttt{DynEval}(Q_{\text{rel}},\mathsf{},\mathcal{K})\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
then
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$.

######  Proof 10.6.

Let $\mathsf{}$ be the vocabulary of $Q$ and db be an arbitrary
$\mathcal{K}$-database over $\mathsf{}$.

Since
$\texttt{DynEval}(Q_{\text{rel}},\mathsf{},\mathcal{K})\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
we have
$\texttt{Eval}(Q_{\text{rel}},\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$
and consequently
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$,
by Proposition 9.10.

Note that Proposition 9.10 shows that
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$
by first making input database db atomically consistent with $Q$ and then
invoking $\texttt{Eval}(Q_{\text{rel}},\mathsf{},\mathcal{K})$ on the
atomically reduced database $\textit{db}^{\prime}$. It is then possible to
enumerate $\texttt{Vals}(Q,\textit{db}^{\prime})=\texttt{Vals}(Q,\textit{db})$
with constant delay, by enumerating
$\texttt{Vals}(Q_{\text{rel}},\textit{db}^{\prime})=\texttt{Vals}(Q_{\text{rel}},\textit{db})$
with constant delay. In other words, the data structure of
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})$ is simply that of
$\texttt{Eval}(Q_{\text{rel}},\mathsf{},\mathcal{K})$.

Hence, to obtain the proposition, it suffices to translate a given update $u$
to db into an update $u^{\prime}$ to $\textit{db}^{\prime}$ such that
$\textit{db}^{\prime}+u^{\prime}$ is the atomic reduction of $\textit{db}+u$.
This allows us to update the data structure
$\texttt{Eval}(Q_{\text{rel}},\mathsf{},\mathcal{K})$ in $\mathsf{}(1)$ time
by assumption, and still be able to enumerate
$\texttt{Vals}(Q_{\text{rel}},\textit{db}^{\prime}+u^{\prime})=\texttt{Vals}(Q_{\text{rel}},\textit{db}+u)$.
We translate the update as follows

  * •

If $u=\texttt{insert}(R,\overline{d},k)$ then for each atom $R(\overline{x})$
in $Q$ with $\overline{d}\models\overline{x}$ check that the inequality
constraints imposed by $Q[R(\overline{x})]$ are satisfied. If this is the
case, apply $u^{\prime}=u$ to $\textit{db}^{\prime}$. Otherwise, no update
needs to be done to $\textit{db}^{\prime}$.

  * •

If $u=\texttt{delete}(R,\overline{d})$ then apply $u^{\prime}=u$ to
$\textit{db}^{\prime}$.

######  Theorem 10.7.

If $Q$ is a q-hierarchical CQ over $\mathsf{}$ and $\mathcal{K}$ a sum-
maintainable semi-integral domain, then
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$.

######  Proof 10.8.

Let $\texttt{split}(Q)=(Q_{\text{rel}},Q_{\text{ineq}})$. Since $Q$ is
q-hierarchical, we have that $Q_{\text{rel}}$ is q-hierarchical by Corollary
10.2. Then, by Proposition 10.3,
$\texttt{DynEval}(Q_{\text{rel}},\mathsf{},\mathcal{K})\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
since $\mathcal{K}$ is a sum-maintainable semi-integral domain. Hence
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K})\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
because of Proposition 10.5.

###  10.3 Lower bound

######  Proposition 10.9.

Let $M\in\mathbb{N}_{>0}$ and let $Q$ be a CQ over $\mathsf{}$ and
$\texttt{split}(Q)=(Q_{\text{rel}},Q_{\text{ineq}})$. If $Q$ is constant-
disjoint and
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
then
$\texttt{DynEval}(Q_{\text{rel}},\mathsf{}\allowbreak,\mathbb{B},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$.

######  Proof 10.10.

The proof uses the same ideas as the proof Proposition 9.15, but specialized
to the dynamic setting, and utilizing that $M$ is a bound on the active domain
of the databases that we will evaluate $Q_{\text{rel}}$ on.

Specifically, we reduce
$\texttt{DynEval}(Q_{\text{rel}},\mathsf{}_{\text{rel}},\mathbb{B},M)$ to
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)$. Denote the free variables of
$Q$, $Q_{\text{rel}}$ and $Q_{\text{ineq}}$ by $\overline{x}$,
$\overline{x}_{1}$ and $\overline{x}_{2}$, respectively. Note that
$\overline{x}_{1}$ and $\overline{x}_{2}$ are disjoint and
$\mathsf{}(\overline{x})=\mathsf{}(\overline{x}_{1})\cup\mathsf{}(\overline{x}_{2})$.
Consider an arbitrary database $\textit{db}_{\text{rel}}$ over $\mathsf{}$,
input to $\texttt{DynEval}(Q_{\text{rel}},\mathsf{},\mathbb{B},M)$. In
particular, all values in the active domain of db are bounded by $M$.
Construct the database db, input to
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)$ as follows.

  * •

$R^{\textit{db}}=R^{\textit{db}_{\text{rel}}}$ for each relation symbol
$R\in\mathsf{}$;

  * •

$db(c):=M$ for all constant symbols $c\in\mathsf{}$ that occur in a covered
inequality in $Q$. Note that $c\not=1$ because $Q$ is constant-disjoint;

  * •

$db(c):=1$ for all other constant symbols $c\in\mathsf{}$.

This is well-defined because $Q$ is constant-disjoint. The computation of db
is clearly in $\mathsf{}(\parallel\\!\textit{db}_{\text{rel}}\\!\parallel)$
and
$\parallel\\!\textit{db}\\!\parallel=\parallel\\!\textit{db}_{\text{rel}}\\!\parallel$.
We call db the _extension_ of $\textit{db}_{\text{rel}}$.

Because $M$ is an upper bound on the domain values occurring in
$\textit{db}_{\text{rel}}$ we have shown in Proposition 9.15 that
$\texttt{Answer}(Q_{\text{rel}},\textit{db}_{\text{rel}})=\texttt{Answer}(Q_{\text{rel}},\textit{db})$
and, that moreover, we may enumerate
$\texttt{Answer}(Q_{\text{rel}},\textit{db})$ with constant delay using the
constant-delay enumeration for $\texttt{Answer}(Q,\textit{db})$, which exists
because
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$.

Hence, to obtain the proposition, it suffices to show that we can translate
any given update $u$ to $\textit{db}_{\text{rel}}$ into an update $u^{\prime}$
to db such that $\textit{db}+u^{\prime}$ is the extension of
$\textit{db}_{\text{rel}}+u$. Because
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
this allows us to update the data structure of
$\texttt{Eval}(Q_{\text{rel}},\mathsf{},\mathbb{B},M)$ in $\mathsf{}(1)$, and
still be able to enumerate $\texttt{Answer}(Q,\textit{db}+u^{\prime})$, which
yields the enumeration of $\texttt{Answer}(Q,\textit{db}_{\text{rel}}+u)$ with
constant delay. We reason as follows. Let $u$ be a single-tuple update to
$\textit{db}_{\text{rel}}$ such that all data values occurring in $u$ are
bounded by $M$. Then simply apply $u$ to db. Clearly, $\textit{db}+u$ is the
extension of $\textit{db}_{\text{rel}}+u$.

######  Proposition 10.11.

Let $Q$ be a CQ over $\mathsf{}$ and $\mathcal{K}$ a semiring such that the
subsemiring generated by $\mymathbb{0}_{\mathcal{K}}$ and
$\mymathbb{1}_{\mathcal{K}}$ is non-trivial and zero-sum free. Let
$M\in\mathbb{N}_{>0}$. If
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
then
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$

######  Proof 10.12.

Let
$\mathcal{K}=(K,\oplus,\odot,\mymathbb{0}_{\mathcal{K}},\mymathbb{1}_{\mathcal{K}})$
be a a semiring such that the subsemiring generated by
$\mymathbb{0}_{\mathcal{K}}$ and $\mymathbb{1}_{\mathcal{K}}$ is non-trivial
and zero-sum free. The proof uses the same ideas as the proof Proposition
9.17, but specialized to the dynamic setting, with bounded evaluation.

Specifically, we reduce $\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)$ to
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$ as follows. Let
$\textit{db}_{\mathbb{B}}$ be a $\mathbb{B}$-database over $\mathsf{}$, input
to $\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)$. Construct the
$\mathcal{K}$-database $\textit{db}_{\mathcal{K}}$, input to
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$ by setting

  * •

for every relation symbol $R\in\mathsf{}$

$\llceil{R}\rrfloor_{\textit{db}_{\mathcal{K}}}\colon\overline{d}\mapsto\begin{cases}\mymathbb{1}_{\mathcal{K}}\text{
if }R^{\textit{db}_{\mathbb{B}}}(\overline{d})=\texttt{t}\\\
\mymathbb{0}_{\mathcal{K}}\text{ otherwise. }\end{cases}$

  * •

$\textit{db}_{\mathcal{K}}(c):=\textit{db}_{\mathbb{B}}(c)$ for every constant
symbol $c$.

We call $\textit{db}_{\mathcal{K}}$ the $\mathcal{K}$ version of
$\textit{db}_{\mathbb{B}}$ Note that this takes time
$\mathsf{}(\parallel\\!\textit{db}_{\mathbb{B}}\\!\parallel)$. Then run
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$ on $\textit{db}_{\mathcal{K}}$,
which takes linear time. We have shown in the proof of Proposition 9.17 that
we may then enumerate $\texttt{Answer}(Q,\textit{db}_{\mathbb{B}})$ with
constant delay using the constant-delay enumeration procedure for
$\texttt{Answer}(Q,\textit{db}_{\mathcal{K}})$ provided by
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)$.

By assumption,
$\texttt{Eval}(Q,\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\textit{db}\\!\parallel,1)$
thus the set $\texttt{Vals}(Q,\textit{db}_{\mathcal{K}})$ can be enumerated
with constant delay after a linear time preprocessing.

Hence, to obtain the proposition, it suffices to show that we can translate
any given update $u$ to $\textit{db}_{\mathbb{B}}$ into an update $u^{\prime}$
to $\textit{db}_{\mathcal{K}}$ such that
$\textit{db}_{\mathcal{K}}+u^{\prime}$ yields the $\mathcal{K}$-version of
$\textit{db}_{\mathbb{B}}+u$. Because
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
this allows us to update the data structure of
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)$ in $\mathsf{}(1)$, and still be
able to enumerate $\texttt{Answer}(Q,\textit{db}_{\mathcal{K}}+u^{\prime})$,
which yields the enumeration of
$\texttt{Answer}(Q,\textit{db}_{\text{rel}}+u)$ with constant delay.

We reason as follows. Let $u$ be a single-tuple update to
$\textit{db}_{\mathbb{B}}$ such that all data values occurring in $u$ are
bounded by $M$.

  * •

If $u=\texttt{insert}(R,\overline{d},\texttt{t})$ and $\overline{d}$ does not
occur in $R^{\textit{db}_{\mathcal{K}}}$ (meaning that $\overline{d}$ did not
occur in $\textit{db}_{\mathbb{B}}$ before), then set
$u^{\prime}=\texttt{insert}(R,\overline{d},\mymathbb{1}_{\mathcal{K}})$.

  * •

If $u=\texttt{insert}(R,\overline{d},\texttt{f})$ then $\textit{db}+u$ is the
same as db, and we hence issue no update $u^{\prime}$ to
$\textit{db}_{\mathcal{K}}$.

  * •

If $u=\texttt{delete}(R,\overline{d})$ then the update
$u^{\prime}=\texttt{delete}(R,\overline{d})$.

######  Theorem 10.13.

Let $Q$ be a CQ over $\mathsf{}$ without self-joins and constant-disjoint and
$\mathcal{K}$ a semiring such that the subsemiring generated by
$\mymathbb{0}_{\mathcal{K}}$ and $\mymathbb{1}_{\mathcal{K}}$ is non-trivial
and zero-sum free.
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
for every $M\in\mathbb{N}_{>0}$, then $Q$ is q-hierarchical, unless the $OMv$
conjecture is false.

######  Proof 10.14.

Let $\texttt{split}(Q)=(Q_{\text{rel}},Q_{\text{ineq}})$. Since
$\texttt{DynEval}(Q,\mathsf{},\mathcal{K},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
for every $M$, by Proposition 10.11 we have that
$\texttt{DynEval}(Q,\mathsf{},\mathbb{B},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
for every $M$, because the subsemiring generated by
$\mymathbb{0}_{\mathcal{K}}$ and $\mymathbb{1}_{\mathcal{K}}$ is non-trivial
zero-sum free. Proposition 10.9 states then that
$\texttt{DynEval}(Q_{\text{rel}},\mathsf{},\mathbb{B},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
for every $M$, since $Q$ is constant disjoint. Because
$Q_{\text{rel}}\in\text{CQ}^{\not\leq}$, by Theorem 10.1, $Q_{\text{rel}}$ is
q-hierarchical unless the $OMv$ conjecture is false. Given that
$Q_{\text{rel}}$ is q-hierarchical if and only if $Q$ is q-hierarchical, the
former directly implies that $Q$ is q-hierarchical unless the $OMv$ conjecture
is false.

The following Theorem implies Corollary 7.5 in Section 7 because, if
$\texttt{DynEval}(\mathbf{Q},\mathsf{},\mathcal{K})\in\texttt{Enum}(\parallel\\!\mathcal{I}\\!\parallel,1)$
then trivially
$\texttt{DynEval}(\mathbf{Q},\mathsf{},\mathcal{K},M)\in\texttt{Enum}(\parallel\\!\mathcal{I}\\!\parallel,1)$
for every $M$, in which case the following proposition yields the claim of
Corollary 7.5.

######  Theorem 10.15.

Let $\mathbf{Q}$ be a $\mathsf{conj}\text{-}\mathsf{MATLANG}$ query over
$\mathsf{}$ such that $\texttt{FixDim}(\mathbf{Q})=\\{0,1\\}$ and let
$\mathcal{K}$ be a semiring such that the subsemiring generated by
$\mymathbb{0}$ and $\mymathbb{1}$ is non-trivial and zero-sum free. If
$\texttt{DynEval}(\mathbf{Q},\mathsf{},\mathcal{K},M)\in\texttt{Enum}(\parallel\\!\mathcal{I}\\!\parallel,1)$
for every $M\in\mathbb{N}_{>0}$, then $\mathbf{Q}$ is equivalent to a
$\mathsf{qh}\text{-}\mathsf{MATLANG}$ query, unless the OMv conjecture is
false.

######  Proof 10.16.

Let $\mathsf{}$ be a matrix-to-relational encoding scheme over $\mathsf{}$
such that it is enumeration-suited for $\mathbf{Q}$ (see Definition 9.24). Let
$\mathsf{}=\mathsf{}^{-1}$ be its inverse relational-to-matrix encoding.

We apply Proposition 9.27 on $\mathbf{Q}$ to obtain binary CQ $Q$ over
$\mathsf{}=\mathsf{}(\mathsf{})$ that simulates $\mathbf{Q}$ w.r.t.
$\mathsf{}$. We know that $Q$ is binary and self-join free; does not have
covered inequalities of the form $x\leq 1$; and for every uncovered inequality
$y\leq c$ it holds that $y$ is not free in $Q$. We next modify $Q$ into a
query $Q^{\prime}$ over $\mathsf{}$ such that the following properties hold:

  1. (P1)

$Q^{\prime}$ continues to simulate $\mathbf{Q}$ w.r.t. $\mathsf{}$;

  2. (P2)

$Q^{\prime}$ is constant-disjoint;

  3. (P3)

$\texttt{DynEval}(Q^{\prime},\mathsf{},\mathcal{K},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$,
for every $M\in\mathbb{N}_{>0}$.

This suffices to prove the proposition. Indeed, by Theorem 10.13 $Q^{\prime}$
is necessarily q-hierarchical unless the OMv conjecture fails. If $Q^{\prime}$
is q-hierarhical, then by Corollary 5.39 there exists a
$\mathsf{fc}\text{-}\mathsf{MATLANG}$ query $\mathbf{Q}^{\prime}$ that
simulates $Q^{\prime}$ w.r.t $\mathsf{}=\mathsf{}^{-1}$. Consequently,
$\mathbf{Q}$ and $\mathbf{Q}^{\prime}$ are then equivalent.

Intuitively, the modification of $Q$ into $Q^{\prime}$ is necessary to obtain
property (P3): the fact that
$\texttt{DynEval}(\mathbf{Q},\mathsf{},\mathcal{K},M)\in\texttt{Enum}(\parallel\\!\mathcal{I}\\!\parallel,1)$
only implies that we may dynamically evaluate $Q$ in
$\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$ _on databases that
encode some matrix instance_. To apply Theorem 10.13, by contrast we need to
show that we can dynamically evaluate $Q$ on _arbitrary databases_. The crux
will be that we obtain $Q^{\prime}$ by adding extra inequalities to $Q$, such
that evaluating $Q^{\prime}$ on an arbitrary database yields the same result
as evaluating it (and $Q$, $\mathbf{Q}$) on some matrix instance.

The definition of $Q^{\prime}$ is as follows. Assume $Q$ is of the form
$Q:H(\overline{y})\leftarrow\exists\overline{z}.\psi$ with $\psi$ quantifier
free. For every relational atom $\alpha=R(\overline{x})$ of $\psi$ we define a
formula $\varphi_{\alpha}$ as follows. This formula is a conjunction of
inequalities:

  * •

If $\alpha=R(x_{1},x_{2})$ with $R$ binary and
$\mathsf{}(R)\colon(\beta,\gamma)$ then
$\varphi_{\alpha}:=x_{1}\leq\mathsf{}(\beta)\wedge
x_{2}\leq\mathsf{}(\gamma)$. Note that, by definition of $\mathsf{}$,
$\mathsf{}(\alpha)\not=1\not=\mathsf{}(\beta)$.

  * •

If $\alpha=R(x_{1})$ with $R$ unary then by definition of $\mathsf{}$ we have
$\mathsf{}(R)\colon(\beta,1)$ or $\mathsf{}(R)\colon(1,\beta)$ for some size
symbol $\beta\not=1$. Then take $\varphi_{\alpha}:=x_{1}\leq\mathsf{}(\beta)$.
Note that by definition of matrix-to-relational encoding schemes,
$\mathsf{}(\beta)\not=1$ since $\beta\not=1$.

  * •

If $\alpha=R()$ with $R$ nullary then by definition of $\mathsf{}$ we have
$\mathsf{}(R)\colon(1,1)$ and we take $\varphi_{\alpha}$ the empty formula
(which is equivalent to t).

Then we define $Q^{\prime}$ to be the CQ

$Q^{\prime}\colon H(\overline{y})\leftarrow\exists
z.(\psi\wedge\bigwedge_{\alpha\text{ rel. atom in }\psi}\varphi_{\alpha}).$

Note that $Q^{\prime}$ continues to simulate $\mathbf{Q}$ over $\mathsf{}$
(property P1). Indeed, for any matrix instance $\mathcal{I}$ over $\mathsf{}$
we know that
$\texttt{Answer}(\mathbf{Q},\mathcal{I})=\texttt{Answer}(Q,\mathsf{}(\mathcal{I}))$.
By definition, $\mathsf{}(\mathcal{I})$ is consistent with
$\mathsf{}^{-1}=\mathsf{}$, and therefore the tuples in
$\mathsf{}(\mathcal{I})$ vacuously satisfy all the extra inequalities that we
have dded to $Q$ to obtain $Q^{\prime}$. As such,
$\texttt{Answer}(Q,\mathsf{}(\mathcal{I}))=\texttt{Answer}(Q^{\prime},\mathsf{}(\mathcal{I}))$.
Thus, $Q^{\prime}$ continues to simulate $\mathbf{Q}$.

Also note that $Q^{\prime}$ is constant-disjoint (property P2). Indeed:

  * •

We have only added covered inequalities to $Q$ to obtain $Q^{\prime}$. Any
such covered inequality that we have added was of the form $x\leq c$ with
$c\not=1$. Therefore, since $Q$ does not have covered inequalities of the form
$x\leq 1$, neither does $Q^{\prime}$.

  * •

We did not add any uncovered inequalities to $Q$ to obtain $Q^{\prime}$.
Moreover, $Q^{\prime}$ has the same free variables as $Q$. Therefore, all
uncovered inequalities $y\leq c$ in $Q^{\prime}$ continue to be such that $y$
is not free in $Q^{\prime}$, unless $c=1$. Hence for all pairs $(x\leq c,y\leq
d)$ of covered inequality $x\leq c$ and non-covered inequality $y\leq d$ with
$d\neq 1$ in $Q^{\prime}$ we have that $y$ is not free in $Q^{\prime}$ as
required for constant-disjointness.

Finally, we show that
$\texttt{DynEval}(Q^{\prime},\mathsf{},\mathcal{K},M)\in\texttt{DynEnum}(\parallel\\!\textit{db}\\!\parallel,1,1)$
for every $M\in\mathbb{N}_{>0}$ (property P3), as claimed. Fix
$M\in\mathbb{N}_{>0}$ arbitrarily. We reduce
$\texttt{DynEval}(Q^{\prime},\mathsf{},\mathcal{K},M)$ to
$\texttt{DynEval}(\mathbf{Q},\mathsf{},\mathcal{K})$ (which is an _unbounded_
evaluation problem) as follows. Let db be a $\mathcal{K}$-database over
$\mathsf{}$, input to $\texttt{DynEval}(Q^{\prime},\mathsf{},\mathcal{K},M)$.
First, create the database $\textit{db}^{\prime}$ that is equal to db except
that for every relation symbol $R\in\mathsf{}$ that is not mentioned in $Q$ we
set $R^{\textit{db}^{\prime}}$ to empty. This can clearly be done in linear
time. Note that, if $R$ is not mentioned in $Q$, then it is also not mentioned
in $Q^{\prime}$, and hence of $Q^{\prime}$ on db is independent of the
contents of $R^{\textit{db}}$. Therefore,
$\texttt{Answer}(Q^{\prime},\textit{db})=\texttt{Answer}(Q^{\prime},\textit{db}^{\prime})$.
Subsequently, compute $\textit{db}^{\prime\prime}$, the atomic reduction of
$\textit{db}^{\prime}$ w.r.t. $Q$. Computing $\textit{db}^{\prime\prime}$ can
be done in time
$\mathsf{}(\parallel\\!\textit{db}^{\prime}\\!\parallel)=\mathsf{}(\parallel\\!\textit{db}\\!\parallel)$.
(See Definition 9.7 and the discussion following.) By Claim 1 we have
$\texttt{Answer}(Q^{\prime},\textit{db})=\texttt{Answer}(Q^{\prime},\textit{db}^{\prime})=\texttt{Answer}(Q^{\prime},\textit{db}^{\prime\prime})$.
Now verify the following claim: $\textit{db}^{\prime\prime}$ is consistent
w.r.t. $\mathsf{}=\mathsf{}^{-1}$. This is because we have added, for each
matrix symbol $\mathbf{A}$ with $\mathsf{}(\mathbf{A})$ occurring in $Q$, the
inequalities that are required by consistency as atomic inequalities to
$Q^{\prime}$. (The matrix symbols $\mathbf{A}$ with $\mathsf{}(\mathbf{A})$
not occurring in $Q$ are empty in $\textit{db}^{\prime}$ and hence vacuously
consistent w.r.t. $\mathsf{}$.) Since $\textit{db}^{\prime\prime}$ is
consistent with $\mathsf{}$ we have that
$\mathsf{}(\textit{db}^{\prime\prime})$ is a matrix instance over $\mathsf{}$
and hence a valid input to $\mathbf{Q}$. Then, because $Q^{\prime}$ simulates
$\mathbf{Q}$, we have
$\texttt{Answer}(Q^{\prime},\textit{db})=\texttt{Answer}(Q^{\prime},\textit{db}^{\prime\prime})=\texttt{Answer}(\mathbf{Q},\mathsf{}(\textit{db}^{\prime\prime}))$.
Because $\texttt{DynEval}(\mathbf{Q},\mathsf{},\mathcal{K})$ is in
$\texttt{Enum}(\parallel\\!\mathcal{I}\\!\parallel,1)$ it hence follows that
with additional preprocessing of time
$\mathsf{}(\parallel\\!\mathsf{}(\textit{db}^{\prime\prime})\\!\parallel)=\mathsf{}(\parallel\\!\textit{db}\\!\parallel)$
we may enumerate
$\texttt{Answer}(Q^{\prime},\textit{db}^{\prime\prime})=\texttt{Answer}(Q^{\prime},\textit{db})$
with constant delay, as desired.

In essence, therefore, the data structure needed to enumerate
$\texttt{Answer}(Q^{\prime},\textit{db})$ with constant delay is the data
structure computed by $\texttt{DynEval}(\mathbf{Q},\mathsf{},\mathcal{K})$
when run on $\mathsf{}(\textit{db}^{\prime\prime})$. We next show how to
maintain this data structure under updates $u$ to db.

Specifically, we next show how we may translate in $\mathsf{}(1)$ time an
update $u$ to db into an update $u^{\prime\prime}$ to
$\textit{db}^{\prime\prime}$ and an update $u_{M}$ to
$\mathsf{}(\textit{db}^{\prime\prime})$ so that (1)
$\textit{db}^{\prime\prime}+u^{\prime\prime}$ yields the same database as when
we would do the above procedure starting from $\textit{db}+u$ instead of db:
$(\textit{db}+u)^{\prime\prime}=\textit{db}^{\prime\prime}+u^{\prime\prime}$
and (2) applying $u_{M}$ to $\mathsf{}(\textit{db}^{\prime\prime})$ yields
$\mathsf{}(\textit{db}^{\prime\prime}+u^{\prime\prime})$. Therefore, applying
$u_{M}$ to $\texttt{DynEval}(\mathbf{Q},\mathsf{},\mathcal{K})$ will give us
the same data structure as when it was run on
$\mathsf{}(\textit{db}^{\prime\prime}+u^{\prime\prime})$. From this we can
again enumerate
$\texttt{Answer}(Q^{\prime},\textit{db}^{\prime\prime}+u^{\prime\prime})=\texttt{Answer}(Q^{\prime},\textit{db}+u)$
with constant delay. This is because the output relation is binary since
$\mathsf{}$ is enumeration-suited for $\mathbf{Q}$. We reason as follows.

  * •

If $u=\texttt{insert}(R,\overline{d},k)$ with $R$ not occurring in
$Q^{\prime}$ then we ignore $u$, there are no updates $u^{\prime\prime}$ and
$u_{M}$ to be done.

  * •

If $u=\texttt{insert}(R,\overline{d},k)$ with $R$ occurring in $Q^{\prime}$
then we check whether $\overline{d}$ is atomically consistent with
$Q^{\prime}[R(\overline{x})]$ for every atom $R(\overline{x})$ in
$Q^{\prime}$. This can be done in constant time, because $Q^{\prime}$ (and
hence the number of inequalities to check) is fixed. If it is atomically
consistent then $u^{\prime}=u$ and $u_{M}$ inserts $k$ in $\mathsf{}(R)$ at
the coordinates specified by $\overline{d}$.

  * •

If $u=\texttt{delete}(R,\overline{d},k)$ with $R$ not occurring in
$Q^{\prime}$ then we ignore $u$, there are no updates $u^{\prime\prime}$ and
$u_{M}$ to be done.

  * •

If $u=\texttt{delete}(R,\overline{d},k)$ with $R$ occurring in $Q^{\prime}$
then we check whether $\overline{d}$ is atomically consistent with
$Q^{\prime}[R(\overline{x})]$ for every atom $R(\overline{x})$ in
$Q^{\prime}$. This can be done in constant time, because $Q^{\prime}$ is
fixed. If it is atomically consistent then $u^{\prime}=u$ and $u_{M}$ sets the
entry in $\mathsf{}(R)$ at the coordinates specified by $\overline{d}$ to
$\mymathbb{0}$.

## References

  * [1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al.  Tensorflow: a system for large-scale machine learning.  In Osdi, volume 16, pages 265–283. Savannah, GA, USA, 2016.
  * [2] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of databases, volume 8.  Addison-Wesley Reading, 1995.
  * [3] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman.  The Design and Analysis of Computer Algorithms.  Addison-Wesley, 1974.
  * [4] Michael Anderson, Shaden Smith, Narayanan Sundaram, Mihai Capotă, Zheguang Zhao, Subramanya Dulloor, Nadathur Satish, and Theodore L Willke.  Bridging the gap between hpc and big data frameworks.  Proceedings of the VLDB Endowment, 10(8):901–912, 2017.
  * [5] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In CSL, pages 208–222, 2007.
  * [6] Pablo Barceló, Nelson Higuera, Jorge Pérez, and Bernardo Subercaseaux.  On the expressiveness of LARA: A unified language for linear and relational algebra.  In Proceedings of the 23rd International Conference on Database Theory, ICDT, pages 6:1–6:20, 2020.  URL: https://doi.org/10.4230/LIPIcs.ICDT.2020.6.
  * [7] Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis.  On the desirability of acyclic database schemes.  J. ACM, 30(3):479–513, jul 1983.  doi:10.1145/2402.322389.
  * [8] Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt.  Constant delay enumeration for conjunctive queries: a tutorial.  ACM SIGLOG News, 7(1):4–33, 2020.
  * [9] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering conjunctive queries under updates.  In PODS, pages 303–318. ACM, 2017.
  * [10] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering conjunctive queries under updates.  In proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems, pages 303–318, 2017.
  * [11] Philip A. Bernstein and Nathan Goodman.  Power of natural semijoins.  SIAM Journal on Computing, 10(4):751–771, 1981.  arXiv:https://doi.org/10.1137/0210059, doi:10.1137/0210059.
  * [12] Johann Brault-Baron.  De la pertinence de l’énumération: complexité en logiques propositionnelle et du premier ordre.  PhD thesis, Université de Caen, 2013.
  * [13] Johann Brault-Baron.  De la pertinence de l’énumération : complexité en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order). PhD thesis, University of Caen, Normandy, France., 2013.  https://tel.archives-ouvertes.fr/tel-01081392.
  * [14] Robert Brijder, Floris Geerts, Jan Van den Bussche, and Timmy Weerwag.  On the expressive power of query languages for matrices.  ACM Trans. Database Syst., 44(4):15:1–15:31, 2019.
  * [15] Robert Brijder, Marc Gyssens, and Jan Van den Bussche.  On matrices and k-relations.  Ann. Math. Artif. Intell., 90(2-3):181–210, 2022.
  * [16] Nofar Carmeli and Markus Kröll.  On the enumeration complexity of unions of conjunctive queries.  ACM Transactions on Database Systems (TODS), 46(2):1–41, 2021.
  * [17] Nofar Carmeli and Luc Segoufin.  Conjunctive queries with self-joins, towards a fine-grained enumeration complexity analysis.  In PODS, pages 277–289, 2023.
  * [18] Arnaud Durand and Etienne Grandjean.  First-order queries on structures of bounded degree are computable with constant delay.  ACM Trans. Comput. Log., 8(4):21, 2007.
  * [19] Arnaud Durand, Nicole Schweikardt, and Luc Segoufin.  Enumerating answers to first-order queries over databases of low degree.  In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 121–131, 2014.
  * [20] Tarek Elgamal, Shangyu Luo, Matthias Boehm, Alexandre V Evfimievski, Shirish Tatikonda, Berthold Reinwald, and Prithviraj Sen.  Spoof: Sum-product optimization and operator fusion for large-scale machine learning.  In CIDR, 2017.
  * [21] Ahmed Elgohary, Matthias Boehm, Peter J Haas, Frederick R Reiss, and Berthold Reinwald.  Scaling machine learning via compressed linear algebra.  ACM SIGMOD Record, 46(1):42–49, 2017.
  * [22] Floris Geerts.  On the expressive power of linear algebra on graphs.  In Pablo Barceló and Marco Calautti, editors, 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, volume 127 of LIPIcs, pages 7:1–7:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICDT.2019.7.
  * [23] Floris Geerts, Thomas Muñoz, Cristian Riveros, and Domagoj Vrgoč.  Expressive power of linear algebra query languages.  In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 342–354, 2021.
  * [24] Floris Geerts and Juan L. Reutter.  Expressiveness and approximation properties of graph neural networks.  In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.  URL: https://openreview.net/forum?id=wIzUeM3TAU.
  * [25] Jonathan S Golan.  Semirings and their Applications.  Springer Science & Business Media, 2013.
  * [26] Todd J Green, Grigoris Karvounarakis, and Val Tannen.  Provenance semirings.  In PODS, pages 31–40, 2007.
  * [27] Udo Hebisch and Hanns Joachim Weinert.  Semirings: algebraic theory and applications in computer science, volume 5.  World Scientific, 1998.
  * [28] Udo Hebisch and Hans Joachim Weinert.  Semirings and semifields.  Handbook of Algebra, 1:425–462, 1996.
  * [29] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 21–30, 2015.
  * [30] Botong Huang, Shivnath Babu, and Jun Yang.  Cumulon: Optimizing statistical data analysis in the cloud.  In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pages 1–12, 2013.
  * [31] Muhammad Idris, Martín Ugarte, and Stijn Vansummeren.  The dynamic yannakakis algorithm: Compact and efficient query processing under updates.  In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1259–1274, 2017.
  * [32] Muhammad Idris, Martín Ugarte, Stijn Vansummeren, Hannes Voigt, and Wolfgang Lehner.  Efficient query processing for dynamically changing datasets.  ACM SIGMOD Record, 48(1):33–40, 2019.
  * [33] Muhammad Idris, Martín Ugarte, Stijn Vansummeren, Hannes Voigt, and Wolfgang Lehner.  General dynamic yannakakis: conjunctive queries with theta joins under updates.  The VLDB Journal, 29(2-3):619–653, 2020.
  * [34] Dimitrije Jankov, Shangyu Luo, Binhang Yuan, Zhuhua Cai, Jia Zou, Chris Jermaine, and Zekai J. Gao.  Declarative recursive computation on an RDBMS.  VLDB, 12(7):822–835, 2019.  URL: http://www.vldb.org/pvldb/vol12/p822-jankov.pdf, doi:10.14778/3317315.3317323.
  * [35] Konstantinos Kanellopoulos, Nandita Vijaykumar, Christina Giannoula, Roknoddin Azizi, Skanda Koppula, Nika Mansouri Ghiasi, Taha Shahroodi, Juan Gomez Luna, and Onur Mutlu.  Smash: Co-designing software compression and hardware-accelerated indexing for efficient sparse matrix operations.  In Proceedings of the 52nd annual IEEE/ACM international symposium on microarchitecture, pages 600–614, 2019.
  * [36] Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang.  Trade-offs in static and dynamic evaluation of hierarchical queries.  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 375–392, 2020.
  * [37] Wojciech Kazana and Luc Segoufin.  Enumeration of first-order queries on classes of structures with bounded expansion.  In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems, pages 297–308, 2013.
  * [38] Shangyu Luo, Zekai J. Gao, Michael Gubanov, Luis L. Perez, and Christopher Jermaine.  Scalable linear algebra on a relational database system.  SIGMOD Rec., 47(1):24–31, 2018.  http://doi.acm.org/10.1145/3277006.3277013.
  * [39] Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny.  Enumeration for fo queries over nowhere dense graphs.  In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 151–163, 2018.
  * [40] Amir Shaikhha, Mohammed Elseidy, Stephan Mihaila, Daniel Espino, and Christoph Koch.  Synthesis of incremental linear algebra programs.  ACM Transactions on Database Systems (TODS), 45(3):1–44, 2020.
  * [41] Yisu Remy Wang, Shana Hutchison, Jonathan Leang, Bill Howe, and Dan Suciu.  SPORES: Sum-product optimization via relational equality saturation for large scale linear algebra.  Proceedings of the VLDB Endowment, 13(12):1919–1932, August 2020\.  doi:10.14778/3407790.3407799.
  * [42] Fan Yang, Yuzhen Huang, Yunjian Zhao, Jinfeng Li, Guanxian Jiang, and James Cheng.  The best of both worlds: Big data programming with both productivity and performance.  In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1619–1622, 2017.
  * [43] Mihalis Yannakakis.  Algorithms for acyclic database schemes.  In Proceedings of the Seventh International Conference on Very Large Data Bases - Volume 7, VLDB ’81, page 82–94. VLDB Endowment, 1981.