$\omega^{f}=(T_{\omega^{f}},\textit{dep}_{\omega^{f}})=\mathsf{free}\text{-}\mathsf{top}(\omega)$
as defined in Section B.1. By Lemma 33, $\omega^{f}$ is a free-top variable
order for $Q$. We show that the static width of $\omega^{f}$ is $1$, which
implies that the static width of $Q$ is at most $1$. Due to our general
assumption that queries contain at least one atom with non-empty schema, it
follows that $Q$ has static width $1$.

To prove that the static width of $\omega^{f}$ is $1$, it suffices to show
that $\rho^{\ast}(X\cup\textit{dep}_{\omega^{f}}(X))=1$ for each variable $X$
in $\omega^{f}$. Let
$\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)=\\{X_{1},\ldots,X_{k}\\}$.
Recall that the variables in $\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)$
are the root variables of the subtrees in $\omega$ that are transformed during
the construction of $\omega^{f}$. We distinguish the following cases:

  * •

$X$ is not included in any $\omega_{X_{j}}$ with $j\in[k]$: By Remark 32.(1),
we have $\mathsf{anc}_{\omega^{f}}(X)=\mathsf{anc}_{\omega}(X)$ and
$\mathit{vars}(\omega^{f}_{X})=\mathit{vars}(\omega_{X})$. Hence,
$(\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))=(\\{X\\}\cup\mathsf{anc}_{\omega}(X))$.
Since $\omega$ is canonical, the schema of any atom in
$\mathit{atoms}(\omega_{X})$ contains all variables in
$\\{X\\}\cup\mathsf{anc}_{\omega}(X)$, which means that
$\rho^{\ast}(\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))=1$.

  * •

$X$ is bound and included in some $\omega_{X_{j}}$ with $j\in[k]$: By Remark
32.(2),
$\mathsf{anc}_{\omega^{f}}(X)=\mathsf{anc}_{\omega}(X)\cup\mathit{free}(\omega_{X_{j}})$.
Observe that
$\textit{dep}_{\omega^{f}}(X)=\mathsf{anc}_{\omega}(X)\cup\mathit{free}(\omega_{X_{j}})$.
Since $Q$ is free-connex, there is an atom
$R(\mathcal{Y})\in\mathit{atoms}(\omega_{X})$ such that $\mathcal{Y}$ contains
all variables in $\mathit{free}(\omega_{X})$ (Lemma 35). Since $\omega$ is
canonical, $\mathcal{Y}$ contains also all variables in
$\\{X\\}\cup\mathsf{anc}_{\omega}(X)$. This means that
$(\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))=(\\{X\\}\cup\mathsf{anc}_{\omega}(X)\cup\mathit{free}(\omega_{X}))\subseteq\mathcal{Y}$.
It follows $\rho^{\ast}(\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))=1$.

  * •

$X$ is free and included in some $\omega_{X_{j}}$ with $j\in[k]$: Recall that
the variable $X_{j}$ is bound. By the same reasoning as above, we have
$R(\mathcal{Y})\in\mathit{atoms}(\omega_{X_{j}})$ such that
$(\\{X_{j}\\}\cup\mathsf{anc}_{\omega^{f}}(X_{j}))\subseteq\mathcal{Y}$. The
variable $X$ is above $X_{j}$ in $\omega^{f}$. Hence,
$(\\{X\\}\cup\mathsf{anc}_{\omega^{f}}(X))\subseteq(\\{X_{j}\\}\cup\mathsf{anc}_{\omega^{f}}(X_{j}))$.
From this and
$(\\{X_{j}\\}\cup\mathsf{anc}_{\omega^{f}}(X_{j}))\subseteq\mathcal{Y}$
follows $\rho^{\ast}((\\{X\\}\cup\textit{dep}_{\omega^{f}}(X)))=1$.

The above analysis implies that $\omega^{f}$ is a free-top variable order for
$Q$ with static width $1$. Hence, the static width of $Q$ is $1$.

###  B.4 Proof of Theorem 4

######  Theorem 4.

Given a hierarchical query with static width $\mathsf{w}$ and dynamic width
$\delta$, a database of size $N$, and $\epsilon\in[0,1]$, the query result can
be enumerated with $\mathcal{O}(N^{1-\epsilon})$ delay after
$\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon})$ preprocessing time and
$\mathcal{O}(N^{\delta\epsilon})$ amortized update time for single-tuple
updates.

The theorem follows from Propositions 20, 21, 22, 23, and 27. Let
$Q(\mathcal{F})$ be a hierarchical query and $\omega$ an arbitrary canonical
variable order for $Q$. Without loss of generality, assume that $\omega$
consists of a single tree. The preprocessing stage materializes the views in
the set of view trees returned by $\tau(\omega,\mathcal{F})$ from Figure 11 in
the dynamic mode. The preprocessing time
$\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon})$ follows from Proposition 21, which
captures both the static and dynamic modes (see the proof). The equivalence
between the constructed view trees and the query follows from Proposition 20.
The delay $\mathcal{O}(N^{1-\epsilon})$ needed when enumerating the query
result from these materialized views follows from Proposition 22. The time
$\mathcal{O}(N^{\delta\epsilon})$ to maintain these materialized views under a
single-tuple update follows from Proposition 23. By Proposition 27, the
amortized maintenance time under a sequence of single-tuple updates is
$\mathcal{O}(N^{\delta\epsilon})$.

If the canonical variable order consists of several view trees, the reasoning
is analogous to the proof of Theorem 2.

###  B.5 Proof of Proposition 6

######  Proposition 6.

A query is q-hierarchical if and only if it is $\delta_{0}$-hierarchical.

“Only if"-direction: Assume that a query $Q$ is $q$-hierarchical. Per
definition, this means that for any two variables $X$ and $Y$, it holds:

$\text{if }\mathit{atoms}(Y)\subset\mathit{atoms}(X)\text{ and
}Y\in\mathit{free}(Q),\text{ then }X\in\mathit{free}(Q).$

For the sake of contradiction, assume that the query $Q$ is not
$\delta_{0}$-hierarchical. This means that there is a bound variable $X$ and
an atom $R(\mathcal{Y})\in\mathit{atoms}(X)$ such that
$\mathit{free}(\mathit{atoms}(X))\not\subseteq\mathcal{Y}$. This implies that
there is an atom $S(\mathcal{Z})\in\mathit{atoms}(X)$ and a free variable
$Y\in\mathcal{Z}$ such that $Y\not\in\mathcal{Y}$. We show:

$\displaystyle\mathit{atoms}(Y)\subset\mathit{atoms}(X).$ (1)

Since $X$ is bound and $Y$ is free, it follows from (1) that $Q$ cannot be
q-hierarchical, which contradicts our initial assumption.

We prove subsumption (1). We first note that due to $Y\in\mathcal{Z}$ and
$Y\not\in\mathcal{Y}$, we have

$\displaystyle S(\mathcal{Z})\in\mathit{atoms}(Y)$ (2)

and

$\displaystyle R(\mathcal{Y})\not\in\mathit{atoms}(Y).$ (3)

It follows from 2 and $S(\mathcal{Z})\in\mathit{atoms}(X)$ that
$\mathit{atoms}(X)\cap\mathit{atoms}(Y)\neq\emptyset$. It follows from
$R(\mathcal{Y})\in\mathit{atoms}(X)$ and 3 that
$\mathit{atoms}(X)\not\subseteq\mathit{atoms}(Y)$. Hence, it must hold
$\mathit{atoms}(Y)\subseteq\mathit{atoms}(X)$, since $Q$ is hierarchical. From
$\mathit{atoms}(Y)\subseteq\mathit{atoms}(X)$,
$R(\mathcal{Y})\in\mathit{atoms}(X)$ and 3 follows (1).

“If"-direction: Assume that $Q$ is $\delta_{0}$-hierarchical. By definition,
for all $X\in\mathit{bound}(Q)$ and $R(\mathcal{Y})\in\mathit{atoms}(X)$, it
holds:

$\displaystyle\mathit{free}(\mathit{atoms}(X))\subseteq\mathcal{Y}.$ (4)

For the sake of contradiction, assume that $Q$ is not q-hierarchical, which
means that there are two variables $X\in\mathit{bound}(Q)$ and
$Y\in\mathit{free}(Q)$ such that:

$\displaystyle\mathit{atoms}(Y)\subset\mathit{atoms}(X).$ (5)

It follows from 5 that there must be an atom
$R(\mathcal{Y})\in\mathit{atoms}(X)$ with
$R(\mathcal{Y})\not\in\mathit{atoms}(Y)$. This means that

$\displaystyle R(\mathcal{Y})\in\mathit{atoms}(X)\text{ and
}Y\not\in\mathcal{Y}.$ (6)

Let $S(\mathcal{Z})$ be an arbitrary atom from $\mathit{atoms}(Y)$. Due to 5,
$S(\mathcal{Z})\in\mathit{atoms}(X)$. Since $Y\in\mathcal{Z}$ and $Y$ is free:

$\displaystyle Y\in\mathit{free}(\mathit{atoms}(X)).$ (7)

Statements 5-7 imply that there is a bound variable $X$ and an atom
$R(\mathcal{Y})\in\mathit{atoms}(X)$ such that
$\mathit{free}(\mathit{atoms}(X))\not\subseteq\mathcal{Y}$, which contradicts
4.

###  B.6 Proof of Proposition 7

######  Proposition 7.

Any free-connex hierarchical query is $\delta_{0}$\- or
$\delta_{1}$-hierarchical.

Let $Q$ be a free-connex hierarchical query. By Proposition 3, $Q$ has static
width $1$. By Proposition 17, $Q$ has dynamic width $0$ or $1$. By Proposition
8, $Q$ is $\delta_{0}$\- or $\delta_{1}$-hierarchical.

###  B.7 Proof of Proposition 8

######  Proposition 8.

A hierarchical query is $\delta_{i}$-hierarchical for $i\in\mathbb{N}_{0}$ if
and only if it has dynamic width $i$.

Proposition 8 follows from the following Lemmas 36 and 37.

######  Lemma 36.

Any $\delta_{i}$-hierarchical query with $i\in\mathbb{N}_{0}$ has dynamic
width at least $i$.

######  Lemma 37.

Any $\delta_{i}$-hierarchical query with $i\in\mathbb{N}_{0}$ has dynamic
width at most $i$.

Proposition 8 can be easily derived from the above lemmas as follows. Assume
that a hierarchical query $Q$ is $\delta_{i}$-hierarchical for some
$i\in\mathbb{N}_{0}$. Lemmas 36 and 37 imply that $Q$ must have dynamic width
$i$.

For the other direction, assume that $Q$ has dynamic width $i$. For the sake
of contradiction, assume that $Q$ is not $\delta_{i}$-hierarchical. There must
be some $j\neq i$ such that $Q$ is $\delta_{j}$-hierarchical. If $j<i$, $Q$
cannot have dynamic width greater than $j$, as per Lemma 37. Hence, the
dynamic width of $Q$ cannot be $i$, which contradicts our initial assumption.
In case $j>i$, Lemma 36 implies that $Q$ cannot have dynamic width less than
$j$. This means that the dynamic width of $Q$ cannot be $i$, which again leads
to a contradiction.

It remains to prove Lemmas 36 and 37.

###### Proof of Lemma 36.

Let $Q$ be a $\delta_{i}$-hierarchical query for some $i\in\mathbb{N}_{0}$.
Since the dynamic width of $Q$ must be at least $0$, the case $i=0$ is
trivial. Assume now that $i\geq 1$. This means that $Q$ contains a bound
variable $X$ and an atom $R(\mathcal{Y})\in\mathit{atoms}(X)$ such that:

$\displaystyle\text{for all atoms
}R_{1}(\mathcal{Y}_{1}),\ldots,R_{i-1}(\mathcal{Y}_{i-1})\in\mathit{atoms}(X),\text{
it holds
}\mathit{free}(\mathit{atoms}(X))-\mathcal{Y}\not\subseteq\bigcup_{j\in[i-1]}\mathcal{Y}_{j}.$
(8)

Let $\omega=(T_{\omega},\textit{dep}_{\omega})$ be an arbitrary free-top
variable order for $Q$. Since the schema of each atom in $\mathit{atoms}(X)$
contains $X$, all variables in $\mathit{free}(\mathit{atoms}(X))$ depend on
$X$. Hence, each variable in $\mathit{free}(\mathit{atoms}(X))$ must be on a
root-to-leaf path with $X$. Since $X$ is bound, the variables in
$\mathit{free}(\mathit{atoms}(X))$ cannot be included in $\omega_{X}$. Hence,
they must be included in $\mathsf{anc}_{\omega}(X)$. This implies that
$\mathit{free}(\mathit{atoms}(X))\subseteq(\\{X\\}\cup\textit{dep}_{\omega}(X))$.
Since $R(\mathcal{Y})$ includes $X$ in its schema, it is contained in
$\mathit{atoms}(\omega_{X})$. By Lemma 34, all atoms covering variables from
$\mathit{free}(\mathit{atoms}(X))-\mathcal{Y}$ must be from
$\mathit{atoms}(X)$. Thus, by Assumption (8),
$\rho((\\{X\\}\cup\textit{dep}_{\omega}(X))-\mathcal{Y})$ must be at least
$i$. This implies that
$\rho^{\ast}((\\{X\\}\cup\textit{dep}_{\omega}(X))-\mathcal{Y})$ must be at
least $i$ (Lemma 30). It follows $\delta(\omega)\geq i$. Since $\omega$ is an
arbitrary free-top variable order for $Q$, we derive that the dynamic width of
$Q$ is at least $i$. ∎

###### Proof of Lemma 37.

Let $\omega=(T_{\omega},\textit{dep}_{\omega})$ be a canonical variable order
of a $\delta_{i}$-hierarchical query $Q$ for some $i\in\mathbb{N}_{0}$. Let
$\omega^{f}=(T_{\omega^{f}},\textit{dep}_{\omega^{f}})=\mathsf{free}\text{-}\mathsf{top}(\omega)$
as defined in Section B.1. By Lemma 33, $\omega^{f}$ is a free-top variable
order for $Q$. We show that for any $X\in\mathit{vars}(\omega^{f})$ and
$R(\mathcal{Y})\in\mathit{atoms}(\omega^{f}_{X})$, we have
$\rho^{*}((\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))-\mathcal{Y})\leq i$. This
implies that $\delta(\omega^{f})\leq i$, hence, the dynamic width of $Q$ is at
most $i$.

Let $\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)=\\{X_{1},\ldots,X_{k}\\}$.
Recall that the variables in $\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)$
are the root variables of the subtrees in $\omega$ that are transformed during
the construction of $\omega^{f}$. We formulate two useful properties about the
relationship between $\omega$ and $\omega^{f}$. Since the construction of
$\omega^{f}$ from $\omega$ does not touch the variables that do not occur in
any $\omega_{X_{j}}$ with $j\in[k]$, we observe:

  * •

$P_{1}$: For each variable $X\in\mathit{vars}(\omega)$ that is not included in
any $\omega_{X_{j}}$ with $j\in[k]$, the set of atoms in the subtree
$\omega_{X}$ of $\omega$ is the same as the set of atoms in the subtree
$\omega^{f}_{X}$ of $\omega^{f}$:
$\mathit{atoms}(\omega^{f}_{X})=\mathit{atoms}(\omega_{X})$, for each
$X\not\in\bigcup_{j\in[k]}\mathit{vars}(\omega_{X_{j}})$.

During the construction of $\omega^{f}$, we move free variables above bound
ones. This does not change the set of atoms in subtrees rooted at bound
variables.

  * •

$P_{2}$: For each variable $X$ in $\mathit{bound}(\omega_{X_{j}})$ with
$j\in[k]$, the set of atoms in the subtree $\omega_{X}$ of $\omega$ is the
same as the set of atoms in the subtree $\omega^{f}_{X}$ of $\omega^{f}$:
$\mathit{atoms}(\omega^{f}_{X})=\mathit{atoms}(\omega_{X})$, for each
$X\in\bigcup_{j\in[k]}\mathit{bound}(\omega_{X_{j}})$.

Let $X\in\mathit{vars}(\omega^{f})$ and
$R(\mathcal{Y})\in\mathit{atoms}(\omega^{f}_{X})$. We show that
$\rho^{*}((\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))-\mathcal{Y})\leq i$. We
distinguish the following cases:

  * •

$X$ is not included in any $\omega_{X_{j}}$ with $j\in[k]$: By Property
$P_{1}$, $R(\mathcal{Y})\in\mathit{atoms}(\omega_{X})$. Since $\omega$ is
canonical, $(\\{X\\}\cup\mathsf{anc}_{\omega}(X))-\mathcal{Y}=\emptyset$. By
Remark 32.(1), we have $\mathsf{anc}_{\omega^{f}}(X)=\mathsf{anc}_{\omega}(X)$
and $\mathit{vars}(\omega^{f}_{X})=\mathit{vars}(\omega_{X})$. Hence,
$(\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))-\mathcal{Y}=(\\{X\\}\cup\mathsf{anc}_{\omega}(X))-\mathcal{Y}=\emptyset$.
This implies
$\rho^{\ast}((\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))-\mathcal{Y})=0$.

  * •

$X$ is bound and included in some $\omega_{X_{j}}$ with $j\in[k]$: By Remark
32.(2),
$\mathsf{anc}_{\omega^{f}}(X)=\mathsf{anc}_{\omega}(X)\cup\mathit{free}(\omega_{X_{j}})$.
Observe that among the variables in $\mathsf{anc}_{\omega^{f}}(X)$, only the
variables in $\mathsf{anc}_{\omega}(X)\cup\mathit{free}(\omega_{X})$ depend on
the variables in the subtree $\omega^{f}_{X}$. By Property $P_{2}$, the atom
$R(\mathcal{Y})$ is included in $\mathit{atoms}(\omega_{X})$. Since $\omega$
is canonical, $R(\mathcal{Y})$ contains $X$ and, therefore, included in
$\mathit{atoms}(X)$. Since $Q$ is $\delta_{i}$-hierarchical, there are atoms
$R_{1}(\mathcal{Y}_{1}),\ldots,R_{i}(\mathcal{Y}_{i})$ such that
$(\\{X\\}\cup\mathsf{anc}_{\omega}(X)\cup\mathit{free}(\omega_{X}))-\mathcal{Y}\subseteq\bigcup_{\ell\in[i]}\mathcal{Y}_{\ell}$.
This means that
$(\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))-\mathcal{Y}=(\\{X\\}\cup\mathsf{anc}_{\omega}(X)\cup\mathit{free}(\omega_{X}))-\mathcal{Y}\subseteq\bigcup_{\ell\in[i]}\mathcal{Y}_{\ell}$.
This implies that
$\rho^{\ast}((\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))-\mathcal{Y})\leq i$.

  * •

$X$ is free and included in some $\omega_{X_{j}}$ with $j\in[k]$: Recall that
the variable $X_{j}$ is bound. By the same reasoning as above, we have
$R(\mathcal{Y})\in\mathit{atoms}(X_{j})$,

$\displaystyle\textit{dep}_{\omega^{f}}(X_{j})=\mathsf{anc}_{\omega}(X_{j})\cup\mathit{free}(\omega_{X_{j}}),$
(9)

and

$\displaystyle\rho^{\ast}((\\{X_{j}\\}\cup\textit{dep}_{\omega^{f}}(X_{j}))-\mathcal{Y})\leq
i.$ (10)

By the construction of $\omega^{f}$, it holds

$\displaystyle\\{X\\}\cup\mathsf{anc}_{\omega^{f}}(X)\subseteq\\{X_{j}\\}\cup\mathsf{anc}_{\omega}(X_{j})\cup\mathit{free}(\omega_{X_{j}}).$
(11)

From Equality (9) and Subsumption (11) follows
$\\{X\\}\cup\mathsf{anc}_{\omega^{f}}(X)\subseteq\\{X_{j}\\}\cup\textit{dep}_{\omega^{f}}(X_{j})$.
The latter and Inequality 10 imply
$\rho^{\ast}((\\{X\\}\cup\mathsf{anc}_{\omega^{f}}(X))-\mathcal{Y})\leq i$.
Thus, $\rho^{\ast}((\\{X\\}\cup\textit{dep}_{\omega^{f}}(X))-\mathcal{Y})\leq
i$.

The above analysis implies that $\omega^{f}$ is a free-top variable order for
$Q$ with dynamic width at most $i$. Hence, the dynamic width of $Q$ is at most
$i$. ∎

###  B.8 Proof of Proposition 10

######  Proposition 10.

Given a $\delta_{1}$-hierarchical query without repeating relation symbols,
$\gamma>0$, and a database of size $N$, there is no algorithm that maintains
the query with arbitrary preprocessing time,
$\mathcal{O}(N^{\frac{1}{2}-\gamma})$ amortized update time, and
$\mathcal{O}(N^{\frac{1}{2}-\gamma})$ enumeration delay, unless the OMv
conjecture fails.

The proof of Proposition 10 is an adaptation of the proof of Theorem 3.3. in
[10]. We reduce the following Online Matrix-Vector Multiplication (OMv)
problem [23] to the maintenance of $\delta_{1}$-hierarchical queries without
repeating relation symbols.

######  Definition 38 (Online Matrix-Vector Multiplication [23]).

We are given an $n\times n$ Boolean matrix $\mathbf{M}$ and receive $n$ column
vectors of size $n$, denoted by $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$, one by
one; after seeing each vector $\mathbf{v}_{i}$, we output the product
$\mathbf{M}\mathbf{v}_{i}$ before we see the next vector.

It is strongly believed that the OMv problem cannot be solved in subcubic
time.

######  Conjecture 39 (OMv Conjecture, Theorem 2.4 in [23]).

For any $\gamma>0$, there is no algorithm that solves the OMv problem in time
$\mathcal{O}(n^{3-\gamma})$.

The OMv conjecture has been used to exhibit conditional lower bounds for many
dynamic problems including those previously based on other popular problems
like 3SUM [23].

We detail the reduction of the OMv problem to the maintenance of
$\delta_{1}$-hierarchical queries without repeating relation symbols. Let
$\mathcal{A}$ be an algorithm that maintains such queries with arbitrary
preprocessing time, $\mathcal{O}(N^{\frac{1}{2}-\gamma})$ amortized update
time, and $\mathcal{O}(N^{\frac{1}{2}-\gamma})$ delay for some $\gamma>0$. We
show that $\mathcal{A}$ can be used to design an algorithm $\mathcal{B}$ that
solves the OMv problem in subcubic time. This contradicts the OMv Conjecture.

We first show the reduction for the case that the query is the simple
$\delta_{1}$-hierarchical query $Q(A)=R(A,B),S(B)$. Then, we explain how the
reduction extendeds to arbitrary $\delta_{1}$-hierarchical queries without
repeating relation symbols.

#### Reduction to the Maintenance of $Q(A)=R(A,B),S(B)$

Given $n\geq 1$, let $\mathbf{M}$, $\mathbf{v}_{1},$ $\ldots,$
$\mathbf{v}_{n}$ be an input to the OMv problem, where $\mathbf{M}$ is an
$n\times n$ Boolean Matrix and $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ are
Boolean column vectors of size $n$. Algorithm $\mathcal{B}$ uses relation $R$
to encode matrix $\mathbf{M}$ and relation $S$ to encode the vectors
$\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$. The database domain is $[n]$. First,
algorithm $\mathcal{B}$ executes the preprocessing stage on an empty database.
Since the database is empty, the preprocessing stage must end after constant
time. Then, it executes at most $n^{2}$ updates to relation $R$ such that
$R(i,j)=1$ if and only if $\mathbf{M}(i,j)=1$. Afterwards, it performs a round
$r$ of operations for each incoming vector $\mathbf{v}_{r}$ with $r\in[n]$. In
the first part of each round $r$, it executes at most $n$ updates to relation
$S$ such that $S(j)=1$ if and only if $\mathbf{v}_{r}(j)=1$. Then, it uses the
enumeration procedure of $\mathcal{A}$ to enumerate the result of $Q$. Observe
that $i\in[n]$ is in the result of $Q$ if and only if
$(\mathbf{M}\mathbf{v}_{r})(i)=1$. Hence, the result of
$\mathbf{M}\mathbf{v}_{r}$ can easily be computed from the result of $Q$.

Time Analysis. The size of the database remains $\mathcal{O}(n^{2})$ during
the whole procedure. Algorithm $\mathcal{B}$ needs at most $n^{2}$ updates to
encode $\mathbf{M}$ by relation $R$. Hence, the time to execute these updates
is
$\mathcal{O}(n^{2}(n^{2})^{\frac{1}{2}-\gamma})=\mathcal{O}(n^{3-2\gamma})$.
In each round $r$ with $1\leq r\leq n$, algorithm $\mathcal{B}$ executes $n$
updates to encode vector $\mathbf{v}_{r}$ into relation $S$ and enumerates the
current query result. Both the updates and the enumeration need
$\mathcal{O}(n(n^{2})^{\frac{1}{2}-\gamma})=\mathcal{O}(n^{2-2\gamma})$ time.
The time to compute the result of $\mathbf{M}\mathbf{v}_{r}$ from the result
of $Q$ is $\mathcal{O}(n)$. Hence, the overall time for a single round is
$\mathcal{O}(n^{2-2\gamma})$. Consequently, the time for $n$ rounds is
$\mathcal{O}(nn^{2-2\gamma})=\mathcal{O}(n^{3-2\gamma})$. This means that the
overall time of the reduction is $\mathcal{O}(n^{3-2\gamma})$ in worst-case,
which is subcubic.

#### Generalization of the Reduction

We now explain algorithm $\mathcal{B}$ in case the query $Q$ is an arbitrary
$\delta_{1}$-hierarchical query without repeating relation symbols. The query
must contain a bound variable $B$ and an atom
$S(\mathcal{Y})\in\mathit{atoms}(B)$ such that
$\mathit{free}(\mathit{atoms}(B))-\mathcal{Y}\neq\emptyset$. Otherwise, it
would not be $\delta_{1}$-hierarchical. Hence, query $Q$ has (at least) a
bound variable $B$, a free variable $A$, and two atoms $S(\mathcal{Y})$ and
$R(\mathcal{X})$ with $\mathcal{Y}\cap\\{A,B\\}=\\{B\\}$ and
$A,B\in\mathcal{X}$. Similar to the above reduction, for each atom
$R^{\prime}(\mathcal{X})$ with $A,B\in\mathcal{X}$, the relation $R^{\prime}$
is used to encode matrix $\mathbf{M}$ and for each atom
$S^{\prime}(\mathcal{Y})$ with $B\in\mathcal{Y}$, the relation $S^{\prime}$ is
used to encode the vectors $\mathbf{v}_{r}$ with $r\in[n]$. Since the query is
does not have repeating relation symbols, it is guaranteed that the relations
encoding matrix $\mathbf{M}$ and those encoding the vectors $\mathbf{v}_{r}$
with $r\in[n]$ are distinct.

We explain the reduction in more detail. The database domain is
$[n]\cup\\{a\\}$. While the variables $A$ and $B$ take values from $[n]$, the
other variables in the query can only be assigned to the data value $a$. We
write $(A=i,B=j,\mathbf{a})$ to denote a tuple that assigns variables $A$ and
$B$ to $i$ and $j$, respectively, and all other variables to $a$. Likewise,
$(B=j,\mathbf{a})$ denotes a tuple that assigns variable $B$ to $j$ and all
other variables to $a$. After the preprocessing stage on the empty database,
algorithm $\mathcal{B}$ executes $\mathcal{O}(n^{2})$ updates such that for
each atom $R(\mathcal{X})$ with $A,B\in\mathcal{X}$, we have
$R(A=i,B=j,\mathbf{a})=1$ if $\mathbf{M}(i,j)=1$ and $R(\mathbf{x})=0$ for all
other tuples $\mathbf{x}$. In each round $r$ with $1\leq r\leq n$, the
algorithm $\mathbf{B}$ executes $\mathcal{O}(n)$ updates such that for each
atom $S(\mathcal{Y})$ with $\mathcal{Y}\cap\\{A,B\\}=\\{B\\}$, it holds
$S(B=j,\mathbf{a})=1$ if $\mathbf{v}_{r}(j)=1$ and $S(\mathbf{x})$ for all
other tuples $\mathbf{x}$. At the end of each round, algorithm $\mathcal{B}$
starts the enumeration procedure for the query. By construction, it holds
$Q(A=i,\mathbf{a})\geq 1$ if and only if $(\mathbf{M}\mathbf{v}_{r})(i)=1$ for
$i\in[n]$.

Time Analysis. The time analysis is analogous to the above analysis in case
$Q(A)=R(A,B),S(B)$. The number of updates differs only by a factor that
depends on the number of atoms in the query. Note that even though the qury
can have additional free variables besides $A$, its result cannot have more
than $n$ tuples, since the domain of all free variables besides $A$ is $a$.

##  Appendix C Missing Details in Section 3

###  C.1 Proof of Proposition 17

######  Proposition 17.

Given a hierarchical query with static width $\mathsf{w}$ and dynamic width
$\delta$, it holds that $\delta=\mathsf{w}$ or $\delta=\mathsf{w}-1$.

Let $Q$ be a hierarchical query with static width $\mathsf{w}$ and dynamic
width $\delta$. The definitions of static and dynamic width and Lemma 30 imply
that $\mathsf{w},\delta\in\mathbb{N}_{0}$ and $\delta\leq\mathsf{w}$. It
remains to show that $\mathsf{w}-1\leq\delta$. For the sake of contradiction
assume that $\mathsf{w}-1>\delta$. Let $\omega$ be a free-top variable order
for $Q$ with dynamic width $\delta(\omega)=\delta$. Our assumption
$\mathsf{w}-1>\delta$ implies:

$\displaystyle\forall X\in\mathit{vars}(Q),\forall
R(\mathcal{Y})\in\mathit{atoms}(\omega_{X}):\
\rho^{*}((\\{X\\}\cup\textit{dep}_{\omega}(X))-\mathcal{Y})<\mathsf{w}-1.$
(12)

Since the static width of $Q$ is $\mathsf{w}$, it holds:

$\displaystyle\exists Y\in\mathit{vars}(Q):\
\rho^{*}(\\{Y\\}\cup\textit{dep}_{\omega}(Y))\geq\mathsf{w}.$ (13)

We show that Statements (12) and (13) are contradicting, which completes the
proof. Let $X$ be an arbitrary variable in $\mathit{vars}(Q)$ and
$R(\mathcal{Y})$ any atom in $\mathit{atoms}(\omega_{X})$. Let
$\boldsymbol{\lambda}=(\lambda_{K(\mathcal{X})})_{K(\mathcal{X})\in\mathit{atoms}(Q)}$
be a fractional edge cover of
$(\\{X\\}\cup\textit{dep}_{\omega}(X))-\mathcal{Y}$ such that

$\displaystyle\sum_{K(\mathcal{X})\in\mathit{atoms}(Q)}\lambda_{K(\mathcal{X})}=\rho^{*}((\\{X\\}\cup\textit{dep}_{\omega}(X))-\mathcal{Y}).$

Due to Statement (12), it holds

$\displaystyle\sum_{K(\mathcal{X})\in\mathit{atoms}(Q)}\lambda_{K(\mathcal{X})}<\mathsf{w}-1.$
(14)

Let
$\boldsymbol{\lambda^{\prime}}=(\lambda^{\prime}_{K(\mathcal{X})})_{K(\mathcal{X})\in\mathit{atoms}(Q)}$
be defined as

$\displaystyle\lambda^{\prime}_{K(\mathcal{X})}=\begin{cases}1,&\text{if
$K(\mathcal{X})=R(\mathcal{Y})$}\\\
\lambda_{K(\mathcal{X})},&\text{otherwise}\end{cases}$

Clearly, $\boldsymbol{\lambda^{\prime}}$ is a fractional edge cover of
$\\{X\\}\cup\textit{dep}_{\omega}(X)$. Moreover, due to Inequality (14), it
holds
$\sum_{K(\mathcal{X})\in\mathit{atoms}(Q)}\lambda^{\prime}_{K(\mathcal{X})}<\mathsf{w}$.
Since $X$ was chosen arbitrarily from $\mathit{vars}(Q)$, this means that for
any $X\in\mathit{vars}(Q)$, we have
$\rho^{*}(\\{X\\}\cup\textit{dep}_{\omega}(X))<\mathsf{w}$. However, this
contradicts Statement (13).

##  Appendix D Missing Details in Section 4

###  D.1 Proof of Proposition 20

######  Proposition 20.

Let $\\{T_{1},\ldots,T_{k}\\}=\tau(\omega,\mathcal{F})$ be the set of view
trees constructed by the algorithm in Figure 11 for a given hierarchical query
$Q(\mathcal{F})$ and a canonical variable order $\omega$ for $Q$. Let
$Q^{(i)}(\mathcal{F})$ be the query defined by the conjunction of the leaf
atoms in $T_{i}$, $\forall i\in[k]$. Then,
$Q(\mathcal{F})\equiv\bigcup_{i\in[k]}Q^{(i)}(\mathcal{F})$.

We use two observations. (1) The procedure BuildVT constructs a view tree
whose leaf atoms are exactly the same as the leaf atoms of the input variable
order. (2) Each of the procedures NewVT and AuxView constructs a view tree
whose set of leaf atoms is the union of the sets of leaf atoms of the input
trees. For a variable order or view tree $T$ and schema a set $\mathcal{S}$ of
variables occurring in $T$, we define
$Q_{T}(\mathcal{S})=\text{$\Join$}_{R(\mathcal{X})\in\mathit{atoms}(T)}R(\mathcal{X})$.

The proof is by induction over the structure of $\omega$. We show that for any
subtree $\omega^{\prime}$ of $\omega$, it holds:

$\displaystyle
Q_{\omega^{\prime}}(\mathcal{F}\cap\mathit{vars}(\omega^{\prime}))\equiv\bigcup_{T\in\tau(\omega^{\prime},\mathcal{F})}Q_{T}(\mathcal{F}\cap\mathit{vars}(\omega^{\prime})).$
(15)

This completes the proof.

  * Base case: If $\omega^{\prime}$ is an atom, the procedure $\tau$ returns that atom and the base case holds trivially.

  * Inductive step: Assume that $\omega^{\prime}$ has root variable $X$ and subtrees $\omega^{\prime}_{1},\ldots,\omega^{\prime}_{k}$. Let $keys=\mathsf{anc}(X)\cup\\{X\\}$, $\mathcal{F}_{X}=\mathsf{anc}(X)\cup(\mathcal{F}\cap\mathit{vars}(\omega^{\prime}))$, and $Q_{X}(\mathcal{F}_{X})=\text{$\Join$}_{R(\mathcal{X})\mathit{atoms}(\omega^{\prime})}R(\mathcal{X})$. The procedure $\tau$ distinguishes the following cases:

  * Case 1: $(mode=\text{`static'}\land Q_{X}(\mathcal{F}_{X})\text{ is free-connex})\,\lor(mode=\text{`dynamic'}\land Q_{X}(\mathcal{F}_{X})\text{ is $\delta_{0}$-hierarchical})$. The procedure $\tau$ returns a view tree $T$ constructed by $\textsc{BuildVT}(V,\omega^{\prime},\mathcal{F}_{X})$. The leaves of $T$ are exactly the atoms of $\omega^{\prime}$. This implies Equivalence 15.

  * Case 1 does not hold and $X\in\mathcal{F}$:  The set of view trees $\tau(\omega^{\prime},\mathcal{F})$ is defined as follows: for each set $\\{T_{i}\\}_{i\in[k]}$ with $T_{i}\in\tau(\omega^{\prime}_{i},\mathcal{F})$, $\tau(\omega^{\prime},\mathcal{F})$ contains the view tree $\textsc{NewVT}(V_{X},keys,\\{\hat{T}_{i}\\}_{i\in[k]})$ where $\hat{T}_{i}=\textsc{AuxView}(\text{root of }\omega_{i}^{\prime},T_{i})$ for $i\in[k]$.

Using the induction hypothesis, we rewrite as follows:

$\displaystyle
Q_{\omega^{\prime}}(\mathcal{F}\cap\mathit{vars}(\omega^{\prime}))=$
$\displaystyle\text{$\Join$}_{i\in[k]}Q_{\omega_{i}^{\prime}}(\mathcal{F}\cap\mathit{vars}(\omega_{i}^{\prime}))$
$\displaystyle\overset{\text{IH}}{\equiv}$
$\displaystyle\text{$\Join$}_{i\in[k]}\Big{(}\bigcup_{T\in\tau(\omega^{\prime}_{i},\mathcal{F})}Q_{T}(\mathcal{F}\cap\mathit{vars}(\omega^{\prime}_{i}))\Big{)}$
$\displaystyle\equiv$ $\displaystyle\,\bigcup_{\forall
i\in[k]:T_{i}\in\tau(\omega^{\prime}_{i},\mathcal{F})}\text{$\Join$}_{i\in[k]}Q_{T_{i}}(\mathcal{F}\cap\mathit{vars}(\omega^{\prime}_{i}))$
$\displaystyle\equiv$ $\displaystyle\,\bigcup_{\forall
i\in[k]:T_{i}\in\tau(\omega^{\prime}_{i},\mathcal{F})}Q_{\textsc{NewVT}(V_{X},keys,\\{\hat{T}_{i}\\}_{i\in[k]})}(\mathcal{F}\cap\mathit{vars}(\omega^{\prime}))$
$\displaystyle=$
$\displaystyle\,\bigcup_{T\in\tau(\omega^{\prime},\mathcal{F})}Q_{T}(\mathcal{F}\cap\mathit{vars}(\omega^{\prime})).$

  * Case 1 does not hold and $X\not\in\mathcal{F}$:  The procedure $\tau$ creates the views $All_{X}(keys)=\text{$\Join$}_{R(\mathcal{X})\in\mathit{atoms}(\omega^{\prime})}R(\mathcal{X})$, $L_{X}(keys)=\text{$\Join$}_{R(\mathcal{X})\in\mathit{atoms}(\omega^{\prime})}R^{keys}(\mathcal{X})$, and $H_{X}(keys)$ = $All_{X}(keys)$ $\Join$ $\nexists L_{X}(keys)$. It then returns the view trees $\\{ltree\\}\cup htrees$ defined as follows:

    * –

$ltree=\textsc{BuildVT}(V,\omega^{keys},\mathcal{F})$, where $\omega^{keys}$
has the same structure as $\omega^{\prime}$ but each atom is replaced by its
light part;

    * –

for each set $\\{T_{i}\\}_{i\in[k]}$ with
$T_{i}\in\tau(\omega^{\prime}_{i},\mathcal{F})$, $htrees$ contains the view
tree $\textsc{NewVT}(V_{X},keys,\\{\exists
H_{X}\\}\cup\\{\hat{T}_{i}\\}_{i\in[k]})$ where
$\hat{T}_{i}=\textsc{AuxView}(\text{root of }\omega_{i}^{\prime},T_{i})$ for
$i\in[k]$.

From $ALL_{X}(keys)=L_{X}(keys)\cup H_{X}(keys)$, we derive the following
equivalence. For simplicity, we skip the schemas of queries:

$\displaystyle\bigcup_{\forall
i\in[k]:T_{i}\in\tau(\omega^{\prime}_{i},\mathcal{F})}\text{$\Join$}_{i\in[k]}\
Q_{T_{i}}\equiv Q_{ltree}\cup\bigcup_{\forall
i\in[k]:T_{i}\in\tau(\omega^{\prime}_{i},\mathcal{F})}Q_{\textsc{NewVT}(V_{X},keys,\\{\exists
H_{X}\\}\cup\\{\hat{T}_{i}\\}_{i\in[k]})}$ (16)

Using Equivalence (16) and the induction hypothesis, we obtain:

$\displaystyle
Q_{\omega^{\prime}}=\text{$\Join$}_{i\in[k]}Q_{\omega_{i}^{\prime}}\overset{\text{IH}}{\equiv}$
$\displaystyle\text{$\Join$}_{i\in[k]}\Big{(}\bigcup_{T\in\tau(\omega^{\prime}_{i},\mathcal{F})}Q_{T}\Big{)}$
$\displaystyle\equiv$ $\displaystyle\,\bigcup_{\forall
i\in[k]:T_{i}\in\tau(\omega^{\prime}_{i},\mathcal{F})}\text{$\Join$}_{i\in[k]}Q_{T_{i}}$
$\displaystyle\overset{\eqref{eq:heavy_light}}{\equiv}$ $\displaystyle
Q_{ltree}\cup\bigcup_{\forall
i\in[k]:T_{i}\in\tau(\omega^{\prime}_{i},\mathcal{F})}Q_{\textsc{NewVT}(V_{X},keys,\\{\exists
H_{X}\\}\cup\\{\hat{T}_{i}\\}_{i\in[k]})}$ $\displaystyle=$ $\displaystyle\
Q_{ltree}\cup\bigcup_{T\in
htrees}Q_{T}=\bigcup_{T\in\tau(\omega^{\prime},\mathcal{F})}Q_{T}$

###  D.2 Proof of Proposition 21

######  Proposition 21.

Given a hierarchical query $Q(\mathcal{F})$ with static width $\mathsf{w}$, a
canonical variable order $\omega$ for $Q$, a database of size $N$, and
$\epsilon\in[0,1]$, the views in the set of view trees
$\tau(\omega,\mathcal{F})$ can be materialized in
$\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon})$ time.

We analyze the procedure $\tau$ from Figure 11 for both of the cases mode =
‘static’ and mode = ‘dynamic’. We show that in both cases the time to
materialize the set of view trees $\tau(\omega,\mathcal{F})$ is
$\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon})$.

We explain the intuition behind the complexity analysis. If the procedure
$\tau$ runs in ‘static’ mode and $Q$ is free-connex, or it runs in ‘dynamic’
mode and $Q$ is $\delta_{0}$-hierarchical, the procedure constructs a view
tree that can be materialized in $\mathcal{O}(N)$ time. Otherwise, there must
be at least one bound variable $X$ in $\omega$ such that the subtree
$\omega_{X}$ rooted at $X$ contains free variables. In this case, the
algorithm partitions the relations at the leaves of $\omega_{X}$ into heavy
and light parts and creates view trees for computing parts of the query. The
time to materialize the views of the view trees where at least one leaf
relation is heavy is $\mathcal{O}(N)$. The overall time to materialize the
view trees $\tau(\omega,\mathcal{F})$ is dominated by the time to materialize
the views of the view trees where all leaf relations are light. In the worst
case, the root variable of $\omega$ is bound and we need to materialize a view
that joins the light parts of all leaf relations in $\omega$ and has the
entire set $\mathcal{F}$ as free variables. We can compute such a view
$V(\mathcal{F})$ as follows. We first aggregate away all bound variables that
are not ancestors of free variables in $\omega$. By using the algorithm
InsideOut [1], this can be done in $\mathcal{O}(N)$ time. Then, we choose one
atom to iterate over the tuples of its relation (outer loop of the
evaluation). For each such tuple, we iterate over the matching tuples in the
relations of the other atoms (inner loops of the evaluation). To decide which
atom to take for the outer loop and which ones for the inner loops of our
evaluation strategy, we use an optimal integral edge cover
$\boldsymbol{\lambda}$ of $\mathcal{F}$. The schema of each atom that is
mapped to $0$ by $\boldsymbol{\lambda}$ must be subsumed by the schema of an
atom mapped to $1$. Hence, we can take one of the atoms mapped to 1 to do the
outer loop. The other atoms that are mapped to 1 are used for the inner loops.
For the atoms that are mapped to 0, it suffices to do constant-time lookups
during the iteration over the tuples of the other atoms. By exploiting the
degree constraints on light relation parts, the view $V(\mathcal{F})$ can be
materialized in $\mathcal{O}(N^{1+(\rho(\mathcal{F})-1)\epsilon})$ time. By
Lemma 30, $\rho(\mathcal{F})=\rho^{\ast}(\mathcal{F})$. Considering the time
needed to aggregate away bound variables before computing $V(\mathcal{F})$, we
get $\mathcal{O}(N^{\max\\{1,1+(\rho^{\ast}(\mathcal{F})-1)\epsilon\\}})$
overall time complexity. We show that
$\max\\{1,1+(\rho^{\ast}(\mathcal{F})-1)\epsilon\\}$ is upper-bounded by
$1+(\mathsf{w}(Q)-1)\epsilon$.

The proof is structured following the basic building blocks of the procedure
$\tau$. Lemmas 41-45 give upper bounds on the times to materialize the views
in the view trees returned by the procedures NewVT (Figure 7), AuxView (Figure
8) BuildVT (Figure 6), and IndicatorVTs (Figure 10). Lemma 46 states the
complexity of the procedure $\tau$ based on a measure $\xi$ defined over
canonical variable orders. The section closes with the proof of Proposition 21
that bridges the measure $\xi$ and the static width of hierarchical queries.

We introduce the measure $\xi$. Let $\omega$ be a canonical variable order,
$\mathcal{F}\subseteq\mathit{vars}(\omega)$, and $X$ a variable or atom in
$\omega$. We denote by $\omega_{X}$ the subtree of $\omega$ rooted at $X$ and
by $Q_{X}$ a query that joins the atoms at the leaves of $\omega_{X}$. We
define

$\xi(\omega,X,\mathcal{F})=\max_{\begin{subarray}{c}Y\in\mathit{vars}(\omega_{X})\\\
(\mathsf{anc}(Y)\cup\\{Y\\})\not\subseteq\mathcal{F}\end{subarray}}\\{\rho_{Q_{X}}^{\ast}(\mathit{vars}(\omega_{Y})\cap\mathcal{F})\\}.$

If $\omega_{X}$ does not contain a variable $Y$ with
$(\mathsf{anc}(Y)\cup\\{Y\\})\not\subseteq\mathcal{F}$, then
$\xi(\omega,X,\mathcal{F})=0$. If $X$ has children $X_{1},\ldots,X_{k}$, then

$\displaystyle\xi(\omega,X,\mathcal{F})\geq\max_{i\in[k]}\\{\xi(\omega,X_{i},\mathcal{F})\\}.$
(17)

We start with an observation that each view $V$ constructed by the procedures
BuildVT (Figure 6), NewVT (Figure 7), AuxView (Figure 8), IndicatorVTs (Figure
10), and $\tau$ (Figure 11) at some node $X$ of a variable order $\omega$
contains in its schema all variables in the root path of $X$ and no variables
which are not in $\omega_{X}$. Moreover, $V$ results from the join of its
child views. This can be shown by a straightforward induction over the
structure of $\omega$.

######  Remark 40.

Let $\omega$ be a canonical variable order and $V(\mathcal{F})$ a view
constructed at some node $X$ of $\omega$ by one of the procedures BuildVT,
NewVT, AuxView, IndicatorVTs, and $\tau$. It holds

  1. 1.

$\mathsf{anc}(X)\subseteq\mathcal{F}\subseteq\mathsf{anc}(X)\cup\mathit{vars}(\omega)$.

  2. 2.

If $V_{1}(\mathcal{F}_{1}),\ldots,V_{k}(\mathcal{F}_{k})$ are the child views
of $V(\mathcal{F})$, then
$V(\mathcal{F})=V_{1}(\mathcal{F}_{1}),\ldots,V_{k}(\mathcal{F}_{k})$.

The next lemma gives a bound on the time to materialize the views in a view
tree returned by the procedure NewVT in Figure 7.

######  Lemma 41.

Given a set $\\{T_{i}\\}_{i\in[k]}$ of view trees with root views
$\\{V_{i}(\mathcal{S}_{i})\\}_{i\in[k]}$, let $M_{i}$ be the time to
materialize the views in $T_{i}$, for $i\in[k]$. If the query
$V(\mathcal{S})=V_{1}(\mathcal{S}_{1}),\ldots,V_{k}(\mathcal{S}_{k})$ with
$\mathcal{S}\subseteq\bigcap_{i\in[k]}\mathcal{S}_{i}$ is
$\delta_{0}$-hierarchical, the views in the view tree
$\textsc{NewVT}(\cdot,\mathcal{S},\\{T_{i}\\}_{i\in[k]})$ can be materialized
in $\mathcal{O}(\max_{i\in[k]}\\{M_{i}\\})$ time.

###### Proof.

The procedure NewVT defines the view
$V(\mathcal{S})\allowbreak=V_{1}(\mathcal{S}_{1}),\allowbreak\ldots,\allowbreak
V_{k}(\mathcal{S}_{k})$ (Line 2). The view tree $T$ returned by NewVT is
defined as follows (Line 3): If $k=1$ and $\mathcal{S}=\mathcal{S}_{1}$, then
$T=T_{1}$; otherwise, $T$ is the view tree that has root $V(\mathcal{S})$ and
subtrees $T_{1},\ldots,T_{k}$. By assumption, the time to meaterialize the
views in the trees $T_{1},\ldots,T_{k}$ is
$\mathcal{O}(\max_{i\in[k]}\\{M_{i}\\})$. Hence, the sizes of the materialized
root views $V_{1}(\mathcal{S}_{1}),\ldots,V_{k}(\mathcal{S}_{k})$ must be
$\mathcal{O}(\max_{i\in[k]}\\{M_{i}\\})$. Assume that the query defining
$V(\mathcal{S})$ is $\delta_{0}$-hierarchical. Hence, we can construct a free-
top canonical variable order for the query. We materialize $V(\mathcal{S})$ as
follows. Traversing the variable order bottom-up, we aggregate away all bound
variables using the InsideOut algorithm [1]. Since the query defining
$V(\mathcal{S})$ is $\alpha$-acyclic, this aggregation phase can be done in
time linear in the size of the views
$V_{1}(\mathcal{S}_{1}),\ldots,V_{k}(\mathcal{S}_{k})$. Thus, the aggregation
phase requires $\mathcal{O}(\max_{i\in[k]}\\{M_{i}\\})$ time. It follows that
the time to materialize the views in the tree returned by NewVT is
$\mathcal{O}(\max_{i\in[k]}\\{M_{i}\\})$. ∎

We proceed with a lemma that gives a bound on the time to materialize the
views in the view tree returned by the procedure AuxView in Figure 8.

######  Lemma 42.

Let $T$ be a view tree and $M$ the time to materialize the views in $T$. The
views in the view tree $\textsc{AuxView}(\cdot,T)$ can be materialized in time
$\mathcal{O}(M)$.

###### Proof.

Assume that the parameters of the procedure AuxView are $\mathcal{Z}$ and $T$.
Let $V(\mathcal{S})$ be the root of $T$. If the condition in Line 2 of the
procedure AuxView does not hold, the procedure returns $T$ (Line 4).
Otherwise, it returns a view tree $T^{\prime}$ that results from $T$ by adding
a view $V^{\prime}(\mathsf{anc}(Z))$ on top of $V(\mathcal{S})$ (Lines 2 and
3). Since $\mathsf{anc}(Z)\subset\mathcal{S}$, $V^{\prime}(\mathsf{anc}(Z))$
results from $V(\mathcal{S})$ by aggregating away the variables in
$\mathcal{S}-\mathsf{anc}(Z)$. Since the size of $V(\mathcal{S})$ must be
$\mathcal{O}(M)$ and the variables can be aggregated away in time linear in
the size of $V(\mathcal{S})$, the overall time to materialize the views in the
output tree $T^{\prime}$ is $\mathcal{O}(M)$. ∎

The following lemma says that if the input to the procedure BuildVT in Figure
6 represents a free-connex query, the procedure outputs a view tree whose
views can be materialized in time linear in the database size.

######  Lemma 43.

Let $\omega$ be a canonical variable order, $X$ a node in $\omega$, $N$ the
size of the leaf relations of $\omega$, and $\mathcal{F}$ a set of variables.
If the query $Q_{X}(\mathcal{F}^{\prime})=\text{ join of
}\mathit{atoms}(\omega_{X})$ with
$\mathcal{F}^{\prime}=\mathcal{F}\cap(\mathsf{anc}(X)\cup\mathit{vars}(\omega_{X}))$
is free-connex, the views in the view tree
$\textsc{BuildVT}(\cdot,\omega_{X},\mathcal{F})$ can be materialized in
$\mathcal{O}(N)$ time.

###### Proof.

The proof is by induction over the structure of the variable order
$\omega_{X}$.

Base case: Assume that $X$ is a single atom $R(\mathcal{X})$. In this case,
the procedure BuildVT returns this atom, which can obviously be materialized
in $\mathcal{O}(N)$ time.

Inductive step: Assume that $X$ is a variable with child nodes
$X_{1},\ldots,X_{k}$ and $Q_{X}(\mathcal{F}^{\prime})=\text{ join of
}\mathit{atoms}(\omega_{X})$ a free-connex query. Let
$\mathcal{F}_{i}=\mathcal{F}\cap(\mathsf{anc}(X_{i})\cup\mathit{vars}(\omega_{X_{i}}))$,
for $i\in[k]$.

We first show that for each $i\in[k]$:

$\displaystyle Q_{X_{i}}(\mathcal{F}_{i})=\text{join of
}\mathit{atoms}(\omega_{X_{i}})\text{ is free-connex.}$ (18)

An $\alpha$-acyclic query is free-connex if and only if after adding an atom
$R(\mathcal{X})$, where $\mathcal{X}$ is the set of free variables, the query
remains $\alpha$-acyclic [14]. A query is $\alpha$-acyclic if it has a (not
necessarily free-top) variable order with static width $1$ [45, 9]. Let
$Q_{X}^{\prime}$ be the query that results from $Q_{X}$ by adding a new atom
$R(\mathcal{F}^{\prime})$. Likewise, let $Q_{X_{i}}^{\prime}$ be the query
that we obtain from $Q_{X_{i}}$ by adding a new atom $R_{i}(\mathcal{F}_{i})$,
for $i\in[k]$. Since $Q_{X}$ is free-connex, there must be a variable order
$\omega^{\prime}=(T_{\omega^{\prime}},\textit{dep}_{\omega^{\prime}})$ for
$Q_{X}^{\prime}$, such that $\mathsf{w}(\omega^{\prime})=1$. In the following,
we turn $\omega^{\prime}$ into a variable order
$\omega_{i}^{\prime}=(T_{\omega_{i}^{\prime}},\textit{dep}_{\omega_{i}^{\prime}})$
for $Q_{X_{i}}^{\prime}$ with $\mathsf{w}(\omega_{i}^{\prime})=1$, for
$i\in[k]$. From this, it follows that $Q_{X_{i}}$ is free-connex, for each
$i\in[k]$. To obtain $\omega_{i}^{\prime}$, we traverse $\omega^{\prime}$
bottom-up and eliminate all variables and atoms (including
$R(\mathcal{F}^{\prime})$) that do not occur in $Q_{X_{i}}^{\prime}$. When
eliminating a node $Y$ with a parent node $Z$, we append the childrens of $Y$
to $Z$. If $Y$ does not have any parent node, the subtrees rooted at its
children nodes become independent. Finally, we append $R_{i}(\mathcal{F}_{i})$
under the lowest variable $Y$ in the obtained variable order such that $Y$ is
included in $\mathcal{F}_{i}$. In the following we show that for $i\in[k]$:

  1. 1.

$\omega_{i}^{\prime}$ is a valid variable order for $Q_{X_{i}}^{\prime}$.

  2. 2.

$\mathsf{w}(\omega_{i}^{\prime})=1$.

(1) $\omega_{i}^{\prime}$ is a valid variable order for $Q_{X_{i}}^{\prime}$,
for $i\in[k]$: The following property follows from the construction of the
variable order $\omega_{i}^{\prime}$:

  * $(*)$

: Any two variables in $\mathit{vars}(Q_{X_{i}}^{\prime})$ that are on the
same root-to-leaf path in $\omega^{\prime}$ remain on the same root-to-leaf
path in $\omega_{i}^{\prime}$.

Each atom $K(\mathcal{X})$ in
$\mathit{atoms}(Q_{X_{i}}^{\prime})-\\{R_{i}(\mathcal{F}_{i})\\}$ is also an
atom in $\mathit{atoms}(Q_{X}^{\prime})$. Hence, the variables in
$\mathcal{X}$ must be on the same root-to-leaf path in $\omega^{\prime}$. Due
to $(*)$, they also must be on the same root-to-leaf path in
$\omega_{i}^{\prime}$. It remains to show that all variables in
$\mathcal{F}_{i}$ are on the same root-to-leaf path in $\omega_{i}^{\prime}$.
In the canonical variable order $\omega$, each variable in
$\mathcal{F}^{\prime}-\\{X\\}$ is either above or below $X$. Hence, $X$
depends on all variables in $\mathcal{F}^{\prime}-\\{X\\}$, which means that
all variables in $\mathcal{F}^{\prime}$ must be on the same root-to-leaf path
in $\omega^{\prime}$. Due to
$\mathcal{F}_{i}\subseteq\\{X\\}\cup\mathcal{F}^{\prime}$ and Property ($*$),
all variables in $\mathcal{F}_{i}$ must be on the same root-to-leaf path in
$\omega_{i}^{\prime}$.

(2) $\mathsf{w}(\omega_{i}^{\prime})=1$, for $i\in[k]$: Let
$Y\in\mathit{vars}(\omega_{i}^{\prime})$ for some $i\in[k]$. We need to show
that
$\rho^{*}_{Q_{X_{i}}^{\prime}}(\\{Y\\}\cup\textit{dep}_{\omega_{i}^{\prime}}(Y))=1$.
By Lemma 30, it suffices to show that $Q_{X_{i}}^{\prime}$ contains an atom
that covers $\\{Y\\}\cup\textit{dep}_{\omega_{i}^{\prime}}(Y)$, i.e., whose
schema includes the latter set. By construction, $Y$ must be included in
$\omega^{\prime}$. First, observe that any two variables that are not
dependent in $Q_{X}^{\prime}$ cannot be dependent in $Q_{X_{i}}^{\prime}$.
Moreover, each variable $Z$ included in the root path of $Y$ in
$\omega_{i}^{\prime}$, is included in the root path of $Y$ in
$\omega^{\prime}$. Hence:

  * ($**$)

$\\{Y\\}\cup\textit{dep}_{\omega_{i}^{\prime}}(Y)\subseteq(\\{Y\\}\cup\textit{dep}_{\omega^{\prime}}(Y))\cap\mathit{vars}(Q_{X_{i}}^{\prime})$.

Due to $\mathsf{w}(\omega^{\prime})=1$ and Lemma 30, there must be an atom
$K(\mathcal{X})\in\mathit{atoms}(Q_{X}^{\prime})$ such that
$\\{Y\\}\cup\textit{dep}_{\omega^{\prime}}(Y)\subseteq\mathcal{X}$. First,
assume that $K(\mathcal{X})\neq R(\mathcal{F}^{\prime})$. Since $\mathcal{X}$
includes $Y$, the atom $K(\mathcal{X})$ must be under the variable $Y$ in
$\omega_{X_{i}}$, which means that $\mathit{atoms}(Q_{X_{i}}^{\prime})$
includes $K(\mathcal{X})$. Due to Property ($**$), $K(\mathcal{X})$ covers
$\\{Y\\}\cup\textit{dep}_{\omega_{i}^{\prime}}(Y)$. Now assume that
$K(\mathcal{X})=R(\mathcal{F}^{\prime})$. This means that
$\\{Y\\}\cup\textit{dep}_{\omega^{\prime}}(Y)\subseteq\mathcal{F}^{\prime}$.
By Property ($**$),
$\\{Y\\}\cup\textit{dep}_{\omega_{i}^{\prime}}(Y)\subseteq(\\{Y\\}\cup\textit{dep}_{\omega^{\prime}}(Y))\cap\mathit{vars}(Q_{X_{i}}^{\prime})\subseteq\mathcal{F}^{\prime}\cap\mathit{vars}(Q_{X_{i}}^{\prime})$.
Since
$\mathcal{F}_{i}=\mathcal{F}^{\prime}\cap\mathit{vars}(Q_{X_{i}}^{\prime})$,
$R_{i}(\mathcal{F}_{i})$ covers
$\\{Y\\}\cup\textit{dep}_{\omega_{i}^{\prime}}(Y)$.

This completes the proof of (18).

Let $T=\textsc{BuildVT}(\cdot,\omega_{X},\mathcal{F})$. To construct the view
tree $T$, the procedure BuildVT first constructs the view trees
$\\{T_{i}\\}_{i\in[k]}$ with
$T_{i}=\textsc{BuildVT}(\cdot,\omega_{X_{i}},\mathcal{F})$ for each $i\in[k]$
(Line 2). By Property (18) and the induction hypothesis, the views in each
view tree $T_{i}$ can be materialized in $\mathcal{O}(N)$ time. In the
following we show that all views in $T$ can be materialized in
$\mathcal{O}(N)$ time. We distinguish whether $\mathsf{anc}(X)\cup\\{X\\}$ is
included in $\mathcal{F}$ (Lines 3-6) or not (Lines 7-9):

Case $\mathsf{anc}(X)\cup\\{X\\}\subseteq\mathcal{F}$: In this case, it holds
$T=\textsc{NewVT}(V_{X},\mathcal{F}_{X},subtrees)$, where
$subtrees=\\{\,\textsc{AuxView}(X_{i},T_{i})\,\\}_{i\in[k]}$ and
$\mathcal{F}_{X}=\mathsf{anc}(X)\cup\\{X\\}$. The procedures NewVT and AuxView
are given in Figures 7 and 8, respectively. By the induction hypothesis and
Lemma 42, the views in $subtrees$ can be materialized in $\mathcal{O}(N)$
time. Let
$V_{1}^{\prime}(\mathcal{F}_{1}^{\prime}),\ldots,V_{k}(\mathcal{F}_{k}^{\prime})$
be the roots of the trees in $subtrees$. The overall size of these root views
must be $\mathcal{O}(N)$. Remark 40.(1) implies that for any $i,j\in[k]$ with
$i\neq j$, it holds
$\mathcal{F}_{i}^{\prime}\cap\mathcal{F}_{i}^{\prime}=\mathcal{F}_{X}$. Hence,
the query
$V_{X}(\mathcal{F}_{X})=V_{1}(\mathcal{F}_{1}^{\prime}),\ldots,V_{k}(\mathcal{F}_{k}^{\prime})$
is $\delta_{0}$-hierarchical. Since
$\mathcal{F}_{X}=\mathsf{anc}(X)\cup\\{X\\}\subseteq\bigcap_{i\in[k]}\mathcal{F}_{i}^{\prime}$,
it follows from Lemma 41 that the views in $T$ can be materialized in
$\mathcal{O}(N)$ time.

Case $\mathsf{anc}(X)\cup\\{X\\}\not\subseteq\mathcal{F}$: n this case, we
have $T=\textsc{NewVT}(V_{X},\mathcal{F}_{X},subtrees)$, where
$\mathcal{F}_{X}=\mathsf{anc}(X)\cup(\mathcal{F}\cap\mathit{vars}(\omega_{X}))$
and $subtrees=\\{T_{i}\\}_{i\in[k]}$. Let
$V_{i}^{\prime}(\mathcal{F}_{i}^{\prime})$ be the root of $T_{i}$, for
$i\in[k]$. By the definition of the procedure NewVT, the tree $T$ results from
the trees $\\{T_{i}\\}_{i\in[k]}$ by adding a new root view defined by
$V_{X}(\mathcal{F}_{X})=V_{1}^{\prime}(\mathcal{F}_{1}^{\prime}),\ldots,V_{k}^{\prime}(\mathcal{F}_{k}^{\prime})$.
It follows from Remark 40.(2), that $V_{X}(\mathcal{F}_{X})$ can be rewritten
as $V_{X}(\mathcal{F}_{X})=\text{ join of }\mathit{atoms}(\omega_{X})$. We
show that the view $V_{X}(\mathcal{F}_{X})$ can be materialized in
$\mathcal{O}(N)$ time. By Lemma 35, $\mathit{atoms}(\omega_{X})$ must contain
an atom $R(\mathcal{Y})$ with $\mathcal{F}_{X}\subseteq\mathcal{Y}$. Hence, we
can easily materialize the view $V_{X}(\mathcal{F}_{X})$ by using the
InsideOut algorithm [1] to aggregate away all variables that are not included
in $\mathcal{F}_{X}$. Since the query defining the view
$V_{X}(\mathcal{F}_{X})$ is ($\alpha$-)acyclic, the whole computation takes
$\mathcal{O}(N)$ time. ∎

The next lemma upper bounds the time to materialize the views constructed by
the procedure BuildVT in Figure 6 for a variable order $\omega^{keys}_{X}$.
This variable order has the same structure as $\omega_{X}$ yet each atom
$R(\mathcal{Y})$ is replaced by the light part $R^{keys}(\mathcal{Y})$ of
relation $R$ partitioned on the variable set $keys$ (cf. Section 4.2).

######  Lemma 44.

Given a canonical variable order $\omega$, a node $X$ in $\omega$, the size
$N$ of the leaf relations in $\omega$, $keys=\mathsf{anc}(X)\cup\\{X\\}$,
$\mathcal{F}\subseteq\mathit{vars}(\omega)$, and $\epsilon\in[0,1]$. The view
tree $\textsc{BuildVT}(\cdot,\omega^{keys}_{X},\mathcal{F})$ can be
materialized in
$\mathcal{O}(N^{\max\\{1,1+(\xi(\omega^{keys},X,\mathcal{F})-1)\epsilon\\}})$
time.

###### Proof.

For a node $X$ in $\omega^{keys}$, we set

$m_{X}=\max\\{1,1+(\xi(\omega^{keys},X,\mathcal{F})-1)\epsilon\\}.$

The proof is by induction on the structure of $\omega^{keys}_{X}$.

  * Base case: If $\omega^{keys}_{X}$ is a single atom $R(\mathcal{X})$, the procedure BuildVT returns this atom, which can be materialized in $\mathcal{O}(N)$ time. Since $m_{X}\geq 1$, this completes the base case.

  * Inductive step: Assume $X\in\mathit{vars}(\omega^{keys})$ and has child nodes $X_{1},\ldots,X_{k}$. The procedure first calls $\textsc{BuildVT}(\cdot,\omega^{keys}_{X_{i}},\mathcal{F})$ for each $i\in[k]$ and produces the view trees $\\{T_{i}\\}_{i\in[k]}$ (Line 2). By induction hypothesis, we need $\mathcal{O}(N^{m_{X_{i}}})$ time to materialize the views in each view tree $T_{i}$ with $i\in[k]$. The procedure BuildVT distinguishes whether $(\mathsf{anc}(X)\cup\\{X\\})\subseteq\mathcal{F}$ (Lines 3-6) or not (Lines 7-9).

  * Case $(\mathsf{anc}(X)\cup\\{X\\})\subseteq\mathcal{F}$: The view tree $T$ returned by BuildVT is $\textsc{NewVT}(V_{X},\mathcal{F}_{X},subtrees)$, where $subtrees$ is defined as $\\{\,\textsc{AuxView}(X_{i},T_{i})\,\\}_{i\in[k]}$ and $\mathcal{F}_{X}=\mathsf{anc}(X)\cup\\{X\\}$. By induction hypothesis and Inequality (17), the overall time to materialize the views in $\\{T_{i}\\}_{i\in[k]}$ is $\mathcal{O}(N^{m_{X}})$. For each view tree $T_{i}$, $\textsc{AuxView}(X_{i},T_{i})$ adds at most one view with schema $\mathsf{anc}(X_{i})$ on top of the root view of $T_{i}$. Then, $\mathsf{anc}(X_{i})$ is a subset of the schema of the root view of $T_{i}$. Since the size of the root view of $T_{i}$ must be bounded by $\mathcal{O}(N^{m_{X}})$, the view added by AuxView can be materialized in $\mathcal{O}(N^{m_{X}})$ time. Assume that $V_{1}(\mathcal{F}_{1}),\ldots,V_{k}(\mathcal{F}_{k})$ are the roots of the view trees in $subtrees$. In case $k=1$ and $\mathcal{F}=\mathcal{F}_{i}$, $\textsc{NewVT}(V_{X},\mathcal{F}_{X},subtrees)$ returns $V_{1}(\mathcal{F}_{1})$; otherwise, it returns a view tree that has $V_{X}(\mathcal{F}_{X})=V_{1}(\mathcal{F}_{1}),\ldots,V_{k}(\mathcal{F}_{k})$ as root view and $subtrees$ as subtrees. By the definition of AuxView, it holds $\mathcal{F}_{i}\cap\mathcal{F}_{j}=(\mathsf{anc}(X)\cup\\{X\\})=\mathcal{F}_{X}$ for any $i,j\in[k]$. Hence, the view $V_{X}(\mathcal{F}_{X})$ can be computed by iterating over the tuples in a view $V_{i}(\mathcal{F}_{i})$ with $i\in[k]$ and filtering out those tuples that do not have matching tuples in all views $V_{j}(\mathcal{F}_{j})$ with $j\in[k]-\\{i\\}$. Since the size of $V_{i}(\mathcal{F}_{i})$ is $\mathcal{O}(N^{m_{X}})$ and materialized views allow constant time lookups, the view $V_{X}(\mathcal{F}_{X})$ can be computed in $\mathcal{O}(N^{m_{X}})$ time. It follows that the view tree $T$ returned by BuildVT can be materialized in $\mathcal{O}(N^{m_{X}})$ time. This completes the inductive step for this case.

  * Case $(\mathsf{anc}(X)\cup\\{X\\})\not\subseteq\mathcal{F}$: The procedure BuildVT sets $\mathcal{F}_{X}=\mathsf{anc}(X)\cup(\mathcal{F}\cap\mathit{vars}(\omega_{X}^{keys}))$ and $subtrees$ $=\\{T_{i}\\}_{i\in[k]}$. The view tree $T$ returned by the procedure BuildVT is $\textsc{NewVT}(V_{X},\mathcal{F}_{X},subtrees)$. We show that all views in the view tree $T$ can be materialized in $\mathcal{O}(N^{m_{X}})$ time. We analyze the steps in NewVT. In case $subtrees$ consists of a single tree $T^{\prime}$ such that the schema of the root view of $T^{\prime}$ is $\mathcal{F}_{X}$, the procedure NewVT returns the view tree $T^{\prime}$. By induction hypothesis and Inequality (17), the views in $T=T^{\prime}$ can be materialized in $\mathcal{O}(N^{m_{X}})$ time. Otherwise, let $V(\mathcal{F}_{i})$ be the root view of $T_{i}$, for $i\in[k]$. The tree $T$ returned by NewVT consists of the root view

$V_{X}(\mathcal{F}_{X})=V_{1}(\mathcal{F}_{1}),\ldots,V_{k}(\mathcal{F}_{k})$

with subtrees $\\{T_{i}\\}_{i\in[k]}$. By induction hypothesis and Inequality
(17), the views in the trees $\\{T_{i}\\}_{i\in[k]}$ can be materialized in
$\mathcal{O}(N^{m_{X}})$ time. It suffices to show that
$V_{X}(\mathcal{F}_{X})$ can be materialized in $\mathcal{O}(N^{m_{X}})$ time.
Using Remark 40.(2), we rewrite the view $V_{X}(\mathcal{F}_{X})$ using the
leaf atoms of $\omega^{keys}_{X}$:

$V_{X}(\mathcal{F}_{X})=\text{ join of }\mathit{atoms}(\omega^{keys}_{X}).$

We materialize the view $V_{X}(\mathcal{F}_{X})$ as follows. Using the
InsideOut algorithm [1], we first aggregate away all variables in
$\mathit{vars}(\omega^{keys}_{X})-\mathcal{F}_{X}$ that are not above a
variable from $\mathcal{F}_{X}$. Since the view $V_{X}$ is defined by an
$\alpha$-acyclic query, the time required by this step is $\mathcal{O}(N)$.
Let
$V_{X}^{\prime}(\mathcal{F}_{X})=R_{1}(\mathcal{F}_{1}),\ldots,R_{k}(\mathcal{F}_{k})$
be the resulting query. We distinguish between two subcases.

  * Subcase 1: For all $R_{i}(\mathcal{F}_{i})$, it holds $\mathcal{F}_{i}\cap\mathit{vars}(\omega^{keys}_{X})=\emptyset$

This means that $\mathcal{F}_{X}$ and each $\mathcal{F}_{i}$ are contained in
$\mathsf{anc}(X)\cup\\{X\\}$. Since $\omega^{keys}$ is canonical, the inner
nodes of each root-to-leaf path are the variables of an atom. Hence, there is
an $R_{i}(\mathcal{F}_{i})$ with $i\in[k]$ such that $\mathcal{F}_{i}$
subsumes $\mathcal{F}_{X}$ and each $\mathcal{F}_{j}$ with $j\in[k]$. Thus, we
can materialize the result of $V_{X}^{\prime}(\mathcal{F}_{X})$ in
$\mathcal{O}(N)$ time by iterating over the tuples in $R_{i}$ and doing
constant-time lookups in the other relations.

  * Subcase 2: There is an $R_{i}(\mathcal{F}_{i})$ with $\mathcal{F}_{i}\cap\mathit{vars}(\omega^{keys}_{X})\neq\emptyset$

Let $\boldsymbol{\lambda}=(\lambda_{R_{i}(\mathcal{F}_{i})})_{i\in[k]}$ be an
edge cover of $\mathcal{F}_{X}\cap\mathit{vars}(\omega^{keys}_{X})$ with
$\sum_{i\in[k]}\lambda_{R_{i}(\mathcal{F}_{i})}=\rho_{V_{X}^{\prime}}^{\ast}(\mathcal{F}_{X}\cap\mathit{vars}(\omega^{keys}_{X}))$.
Since $V_{X}^{\prime}$ is hierarchical, we can assume that each
$\lambda_{R_{i}(\mathcal{F}_{i})}$ is either $0$ or $1$ (Lemma 30). There must
be at least one $R_{i}(\mathcal{F}_{i})$ with
$\lambda_{R_{i}(\mathcal{F}_{i})}=1$, otherwise there cannot be any variable
from $\mathcal{F}_{X}$ in $\omega^{keys}_{X}$ and we fall back to Subcase 1.
Since $\omega_{X}^{keys}$ is canonical, for each atom $R_{i}(\mathcal{F}_{i})$
with $\lambda_{R_{i}(\mathcal{F}_{i})}=0$, there must be a witness atom
$R_{j}(\mathcal{F}_{j})$ such that $\lambda_{R_{j}(\mathcal{F}_{j})}=1$ and
$\mathcal{F}_{i}\subseteq\mathcal{F}_{j}$. The atoms
$R_{1}(\mathcal{F}_{1}),\ldots,R_{k}(\mathcal{F}_{k})$ can still contain
variables not included in $\mathcal{F}_{X}$. Each such variable appears above
at least one variable from $\mathcal{F}_{X}$ in $\omega^{keys}_{X}$. We first
compute the result of the view
$V_{X}^{\prime\prime}(\bigcup_{i\in[k]}\mathcal{F}_{k})=R_{1}(\mathcal{F}_{1}),\ldots,R_{k}(\mathcal{F}_{k})$
as follows. We choose an arbitrary atom $R_{i}(\mathcal{F}_{i})$ with
$\lambda_{R_{i}(\mathcal{F}_{i})}=1$ and iterate over the tuples in $R_{i}$.
For each such tuple, we iterate over the matching tuples in the other atoms
mapped to $1$ by $\boldsymbol{\lambda}$. For atoms that are not mapped to $1$,
it suffices to do constant-time lookups while iterating over one of their
witnesses. To obtain the result of $V_{X}^{\prime}$ from
$V_{X}^{\prime\prime}$, we aggregate away all variables not included in
$\mathcal{F}_{X}$. Recall that for each atom $R_{i}(\mathcal{F}_{i})$, there
is an atom in $\mathit{atoms}(\omega^{keys}_{X})$ that is the light part of a
relation partitioned on $keys=\mathsf{anc}(X)\cup\\{X\\}$. Hence, each tuple
in the relation of an atom mapped to $1$ by $\boldsymbol{\lambda}$ can be
paired with $\mathcal{O}(N^{\epsilon})$ tuples in the relation of any other
atom mapped to $1$. This means that the time to materialize
$V_{X}^{\prime\prime}$ and hence $V_{X}^{\prime}$ is
$\mathcal{O}(N^{m^{\prime}})$ where
$m^{\prime}=1+(\rho_{V_{X}^{\prime}}^{\ast}(\mathcal{F}_{X}\cap\mathit{vars}(\omega^{keys}_{X}))-1)\epsilon$.
Since $V_{X}^{\prime}$ results from $V_{X}$ by aggregating away variables in
$\mathit{vars}(\omega^{keys}_{X})-\mathcal{F}_{X}$, we have
$\rho_{V_{X}^{\prime}}^{\ast}(\mathcal{F}_{X}\cap\mathit{vars}(\omega^{keys}_{X}))=\rho_{V_{X}}^{\ast}(\mathcal{F}_{X}\cap\mathit{vars}(\omega^{keys}_{X}))$.
It follows from $\mathsf{anc}(X)\cup\\{X\\}\not\subseteq\mathcal{F}$ that
$\rho_{V_{X}}^{\ast}(\mathcal{F}_{X}\cap\mathit{vars}(\omega^{keys}_{X}))$ $=$
$\xi(\omega^{keys},X,\mathcal{F})$. Hence, the view $V_{X}^{\prime}$ can be
materialized in
$\mathcal{O}(N^{1+(\xi(\omega^{keys},X,\mathcal{F})-1)\epsilon})$ time.

We sum up the analysis for the case
$(\mathsf{anc}(X)\cup\\{X\\})\not\subseteq\mathcal{F}$: the initial
aggregation step and the computation in Subcase 1 take $\mathcal{O}(N)$ time;
the computation in Subcase 2 takes
$\mathcal{O}(N^{1+(\xi(\omega^{keys},X,\mathcal{F})-1)\epsilon})$ time. Thus,
given $m_{X}=\max\\{1,1+(\xi(\omega^{keys},X,\mathcal{F})-1)\epsilon\\}$, the
time to materialize the result of $V_{X}$ is $\mathcal{O}(N^{m_{X}})$. This
completes the inductive step in case
$(\mathsf{anc}(X)\cup\\{X\\})\not\subseteq\mathcal{F}$. ∎

The next lemma states that the view trees returned by the procedure
IndicatorVTs from Figure 10 can be materialized in time linear in the database
size.

######  Lemma 45.

Let $\omega$ be a canonical variable order, $X$ a variable in $\omega$, and
$N$ the size of the leaf relations in the variable order $\omega$. The views
in the view trees returned by $\textsc{IndicatorVTs}(\omega_{X})$ can be
materialized in $\mathcal{O}(N)$ time.

###### Proof.

In Lines 3 and 4, the procedure constructs the view tree
$alltree=\textsc{BuildVT}(All,\omega_{X},keys)$ and the view tree
$ltree=\textsc{BuildVT}(L,\omega^{keys}_{X},keys)$, where $keys$ consists of
the set $\mathsf{anc}(X)\cup\\{X\\}$. The variable order $\omega^{keys}_{X}$
results from $\omega_{X}$ by replacing each atom $R(\mathcal{X})$ by the atom
$R^{keys}(\mathcal{X})$, which denotes the light part of relation $R$
partitioned on $keys$. These light parts can be computed in $\mathcal{O}(N)$
time. The queries $Q_{X}(keys)=\text{ join of }\mathit{atoms}(\omega_{X})$ and
$Q_{X}^{keys}(keys)=\text{ join of }\mathit{atoms}(\omega_{X})$ are free-
connex. By using Lemma 43, we derive that the views in $alltree$ and $ltree$
can be materialized in $\mathcal{O}(N)$ time. Hence, the roots $allroot$ and
$lroot$ of $alltree$ and $ltree$, respectively, can be materialized in
$\mathcal{O}(N)$ time as well. It remains to analyze the time to materialize
the views in the view tree
$htree=\textsc{NewVT}(H_{X},\mathcal{F},\\{allroot,\neg lroot\\})$ (Line 7).
It follows from Remark 40.(1) that $V(\mathcal{F})=allroot,\nexists lroot$ is
$\delta_{0}$-hierarchical. By using Lemma 41, we derive that the views in
$htree$ can be materialized in $\mathcal{O}(N)$ time. Overall, all views in
the view trees $(alltree,ltree,htree)$ can be materialized in $\mathcal{O}(N)$
time. ∎

We use Lemmas 41-45 to show an upper bound on the time to materialize the
views in any tree produced by the procedure $\tau$ in Figure 11.

######  Lemma 46.

Let $\omega$ be a canonical variable order, $X$ a node in $\omega$,
$\mathcal{F}\subseteq\mathit{vars}(\omega)$, $N$ the size of the leaf
relations in $\omega$, and $\epsilon\in[0,1]$. The views in the trees returned
by $\tau(\omega_{X},\mathcal{F})$ can be materialized in
$\mathcal{O}(N^{\max\\{1,1+(\xi(\omega,X,\mathcal{F})-1)\epsilon\\}})$ time.

###### Proof.

For simplicity, we set

$m=\max\\{1,1+(\xi(\omega,X,\mathcal{F})-1)\epsilon\\}.$

The proof is by induction on the structure of $\omega_{X}$.

Base case: Assume that $\omega_{X}$ is a single atom $R(\mathcal{X})$. In this
case, the procedure $\tau$ returns this atom (Line 1). The atom can obviously
be materialized in $\mathcal{O}(N)$ time. It holds
$\xi(\omega,X,\mathcal{F})=0$, since $\omega_{X}$ does not contain any node
which is a variable. This means that $m=1$. Then, the statement in the lemma
holds for the base case.

Inductive step: Assume that $X$ is a variable with children nodes
$X_{1},\ldots,X_{k}$. Let $keys=\mathsf{anc}(X)\cup\\{X\\}$,
$\mathcal{F}_{X}=\mathsf{anc}(X)\cup(\mathcal{F}\cap\mathit{vars}(\omega_{X}))$,
and $Q_{X}(\mathcal{F}_{X})=\text{join of }\mathit{atoms}(\omega)$. Following
the control flow in $\tau(\omega_{X},\mathcal{F})$, we make a case
distinction.

Case 1: mode = ‘static’ $\wedge$ $Q_{X}(\mathcal{F}_{X})$ is a free-connex
query or mode = ‘dynamic’ $\wedge$ $Q_{X}(\mathcal{F}_{X})$ is a
$\delta_{0}$-hierarchical query (Lines 5-7):
The procedure $\tau$ returns the view tree
$\textsc{BuildVT}(V,\omega_{X},\mathcal{F}_{X})$ (Line 7). Since
$\delta_{0}$-hierarchical queries are in particular free-connex, it follows
from Lemma 43 that the views in
$\textsc{BuildVT}(V,\omega_{X},\mathcal{F}_{X})$ can be materialized in time
$\mathcal{O}(N)$. This completes the inductive step for Case 1.

Case 2: Case 1 does not hold and $X\in\mathcal{F}$ (Lines 8-11):
The set of view trees $\tau(\omega_{X},\mathcal{F})$ is defined as follows:
for each set $\\{T_{i}\\}_{i\in[k]}$ with
$T_{i}\in\tau(\omega_{X_{i}},\mathcal{F})$, the set
$\tau(\omega_{X},\mathcal{F})$ contains the view tree
$\textsc{NewVT}(V_{X},keys,\\{\hat{T}_{i}\\}_{i\in[k]})$, where
$\hat{T}_{i}=\textsc{AuxView}(X_{i},T_{i})$ for each $i\in[k]$. We consider
one such set $\\{T_{i}\\}_{i\in[k]}$ of view trees. By induction hypothesis,
the views in each $T_{i}$ can be materialized in
$\mathcal{O}(N^{\max\\{1,1+(\xi(\omega,X_{i},\mathcal{F})-1)\epsilon\\}})$
time. It follows from Inequality (17), that the overall time to materialize
the views in these view trees is $\mathcal{O}(N^{m})$. By Lemma 42, the views
in each view tree $\hat{T}_{i}$ with $i\in[k]$ can be materialized in
$\mathcal{O}(N^{m})$ time. Let $V_{i}(\mathcal{F}_{i})$ be the root view of
$\hat{T}_{i}$, for $i\in[k]$. It follows from Remark 40.(1) that $keys$ is
included in each $\mathcal{F}_{i}$ and the query
$V_{X}(keys)=V_{1}(\mathcal{F}_{1}),\ldots,V_{k}(\mathcal{F}_{k})$ is
$\delta_{0}$-hierarchical. Hence, it follows from Lemma 41 that the views in
the view tree $\textsc{NewVT}(V_{X},keys,\\{\hat{T}_{i}\\}_{i\in[k]})$ can be
materialized in time $\mathcal{O}(N^{m})$. This completes the inductive step
in this case.

Case 3: Case 1 does not hold and $X\not\in\mathcal{F}$ (Lines 12-17):
The procedure $\tau$ first calls $\textsc{IndicatorVTs}(\omega_{X})$ (Line 12)
given in Figure 10, which constructs the indicator view trees $alltree$,
$ltree$, and $htree$. By Lemma 45, the views in these view trees can be
materiaized in $\mathcal{O}(N)$ time. Let $H_{X}$ be the root of $htree$. The
only difference between the construction of the view trees returned in Case 2
above and the view trees in the set $htrees$ defined in Lines 13-15 is that
the roots of the view trees in the latter set have $\exists H_{X}$ as
additional child view. By the same argumentation as in Case 2, it follows that
the views in $htrees$ can be materialized in $\mathcal{O}(N^{m})$ time. Let
$ltree=\textsc{BuildVT}(V,\omega_{X}^{keys},\mathcal{F}_{X})$ as defined in
Line 16, where $\omega_{X}^{keys}$ shares the same structure as $\omega_{X}$,
but each atom $R(\mathcal{X})$ is replaced with $R^{keys}(\mathcal{X})$
denoting the light part of relation $R$ partitioned on $keys$. It follows from
Lemma 44 that the views in the view tree $ltree$ can be materialized in
$\mathcal{O}(N^{m})$ time. Thus, all views of the views trees in the set
$htrees\cup\\{ltree\\}$ can be materialized in $\mathcal{O}(N^{m})$ time. This
completes the inductive step for Case 3. ∎

Using Lemma 46, we prove the main result of this section:

###### Proof of Proposition 21.

Without loss of generality, assume that $\omega$ consists of a single
connected component. Otherwise, we apply the same reasoning for each connected
component. We also assume that $Q$ contains at least one atom with non-empty
schema. Otherwise, $\tau(\omega,\emptyset)$ returns a single atom with empty
shema, which can obviously be materialized in constant time.

By Lemma 46, the views of the view trees in $\tau(\omega,\mathcal{F})$ can be
materialized in
$\mathcal{O}(N^{\max\\{1,1+(\xi(\omega,X,\mathcal{F})-1)\epsilon\\}})$ time,
where $X$ is the root variable of $\omega$. It remains to show:

$\displaystyle\max\\{1,1+(\xi(\omega,X,\mathcal{F})-1)\epsilon\\}\leq
1+(\mathsf{w}-1)\epsilon.$ (19)

First, assume that $\xi(\omega,X,\mathcal{F})=0$. This means that
$\max\\{1,1+(\xi(\omega,X,\mathcal{F})-1)\epsilon\\}=1$. Since $Q$ contains at
least one atom with non-empty schema, we have $\mathsf{w}\geq 1$. Thus,
Inequality (19) holds. Now, let $\xi(\omega,X,\mathcal{F})=\ell\geq 1$. We
show that $\mathsf{w}\geq\ell$. It follows from
$\xi(\omega,X,\mathcal{F})=\ell$ that $\omega$ contains a bound variable $Y$
such that $\rho^{\ast}_{Q}(B)=\ell$, where
$B=\mathit{vars}(\omega_{Y})\cap\mathcal{F}$. The inner nodes of each root-to-
leaf path of a canonical variable order are the variables of an atom. Hence,
for each variable $Z\in B$, there must be an atom in $Q$ that contains both
$Y$ and $Z$. This means that $Y$ and $Z$ depend on each other. Let
$\omega^{\prime}=(T,\textit{dep}_{\omega^{\prime}})$ be an arbitrary free-top
variable order for $Q$. Since all variables in $B$ depend on $Y$, each of them
must be on a root-to-leaf path with $Y$. Since $Y$ is bound and the variables
in $B$ are free, the set $B$ must be included in $\mathsf{anc}(Y)$. Hence,
$B\subseteq\textit{dep}_{\omega^{\prime}}(Y)$. This means
$\rho^{\ast}_{Q}(\\{Y\\}\cup\textit{dep}_{\omega^{\prime}}(Y))\geq\ell$, which
implies $\mathsf{w}(\omega^{\prime})\geq\ell$. It follows
$\mathsf{w}\geq\ell$. ∎

##  Appendix E Missing Details in Section 5

###  E.1 Proof of Proposition 22

######  Proposition 22.

The tuples in the result of a hierarchical query $Q(\mathcal{F})$ over a
database of size $N$ can be enumerated with $\mathcal{O}(N^{1-\epsilon})$
delay using the view trees constructed by $\tau(\omega,\mathcal{F})$ for a
canonical variable order $\omega$ for $Q$.

Following Proposition 20, the union of queries defined by the set of view
trees constructed by $\tau(\omega,\mathcal{F})$ is equivalent
$Q(\mathcal{F})$. We enumerate the tuples over $\mathcal{F}$ from this set of
view trees using the $\mathit{next}$ calls of these trees in the set.

We first discuss the case of one view tree. In case there are no indicator
views, then the view tree consisting of a hierarchy of views admits constant
delay [45]. In the static case, this holds for free-connex hierarchical
queries; in the dynamic case, this holds for $\delta_{0}$-hierarchical queries
(Section 4.1).

The view subtrees constructed over the light parts of input relations only do
not bring additional difficulty. By construction (Section 4), the root view
$V$ of such a subtree $T$ contains all the free variables that are present in
$T$. In this case, the $\mathit{open}$ and $\mathit{next}$ calls stop at $V$
and do not explore the children of $V$. This means that for enumeration
purposes, we can discard the descendants of $V$.

By grounding the heavy indicators in $T$, we obtain instances of $T$ that may
represent overlapping relations. We next analyze the enumeration delay in the
presence of heavy indicators as a function of the view tree instances of a
view tree created for $Q$.

Consider one heavy indicator. Since its size is $\mathcal{O}(N^{1-\epsilon})$,
it may lead to that many view tree instances. From each instance, we can
enumerate with constant delay, and we can also look up a tuple with schema
$\mathcal{S}$ in constant time. Given there are $\mathcal{O}(N^{1-\epsilon})$
such tuples, we can enumerate from $T$ with $\mathcal{O}(N^{1-\epsilon})$
delay.

Consider $p$ heavy indicators $\exists H_{1}(\mathcal{X}_{1}),\ldots,$
$\exists H_{p}(\mathcal{X}_{p})$ whose parents
$V_{1}(\mathcal{X}_{1}),\ldots,V_{p}(\mathcal{X}_{p})$ are along the same path
in the view tree. Let us assume $V_{i}$ is an ancestor of $V_{j}$ for $i<j$.
By construction, there is a total strict inclusion order on their sets of
variables, with the indicator above having less variables than at a lower
depth: $\mathcal{X}_{1}\subset\cdots\subset\mathcal{X}_{p}$. Each indicator
draws its tuples from the input relations whose schemas include that of the
indicator. There is also an inclusion between the parent views:
$V_{i}\subseteq\pi_{\mathcal{X}_{i}}V_{i+1},\forall i\in[p-1]$. This holds
since $V_{i}$ is defined by the join of the leaves underneath, so the view
$V_{j}$ that is a descendant of $V_{i}$ is used to define $V_{i}$ in joins
with other views or relations. The size of $V_{i}$ is at most that of $\exists
H_{i}$ since they both have the same schema and the former is defined by the
join of the latter with other views. Since the size of $\exists H_{i}$ is
$\mathcal{O}(N^{1-\epsilon})$, it follows that the size of $V_{i}$ is also
$\mathcal{O}(N^{1-\epsilon})$. When grounding $\exists H_{i}$, we create an
instance for each tuple $t$ that is in both $\exists H_{i}$ and $V_{i}$: If
$t$ were not in $V_{i}$, then there would be at least one sibling of $\exists
H_{i}$ that does not have it. When opening the descendants of $V_{i}$ before
enumeration, only these tuples in $V_{i}$ that also occur in $\exists H_{i}$
and in all its siblings can be extended at the descendant views, including all
views $V_{j}$ for $j>i$. The overall number of groundings for the $h$ heavy
indicators is therefore $\mathcal{O}(N^{1-\epsilon})$. Let $n_{i}$ be the
number of instances of $\exists H_{i}$. Then, the delay for enumerating from
the union of $\exists H_{i}$ instances is $\sum_{i\leq j\leq p}n_{j}$ using
the Union algorithm, which also accounts for the delay incurred for
enumeration from unions at instances of all $\exists H_{j}$ that are
descendants of $\exists H_{i}$. The overall delay is that for the union of
instances for $\exists H_{1}$: $\sum_{1\leq j\leq p}n_{j}=\mathcal{O}(p\times
N^{1-\epsilon})=\mathcal{O}(N^{1-\epsilon})$.

Consider again the $p$ heavy indicators, but this time their parents
$V_{1},\ldots,V_{p}$ are not all along the same path in the view tree. Each
path is treated as in the previous case. We distinguish two cases. In the
first case, there is no parent $V_{i}$ that is an ancestor of several other
parents in our list. Let $W$ be a common ancestor of several parents. Then,
the enumeration algorithm uses each tuple of $W$ (possibly extended by
descendant views) as context for the instances of these parents. A next tuple
is produced in sequence at each of these parents over their corresponding
schemas. These tuples are then composed into a larger tuple over a larger
schema at their common ancestor using the Product algorithm. The number of
branches is bounded by the number of atoms in the query, which means that the
overall delay remains $\mathcal{O}(N^{1-\epsilon})$. In the second case, a
parent $V_{i}$ is a common ancestor of several other parents in our list. We
reason similarly to the one-path case and obtain that the overall delay is
$\mathcal{O}(p\times N^{1-\epsilon})=\mathcal{O}(N^{1-\epsilon})$.

So far we discussed the case of enumerating from one view tree. In case of a
set of view trees we use the Union algorithm to enumerate the distinct tuples.
In case the query has several connected components, i.e., it is a Cartesian
product of hierarchical queries, we use the Product algorithm.

##  Appendix F Missing Details in Section 6

###  F.1 Proof of Proposition 23

######  Proposition 23.

Given a hierarchical query $Q(\mathcal{F})$ with dynamic width $\delta$, a
canonical variable order $\omega$ for $Q$, a database of size $N$, and
$\epsilon\in[0,1]$, maintaining the views in the set of view trees
$\tau(\omega,\mathcal{F})$ under a single-tuple update to any input relation
takes $\mathcal{O}(N^{\delta\epsilon})$ time.

We first give the maintenance time for the views constructed by BuildVT given
a $\delta_{0}$-hierarchical query (Lemma 47). We then show the maintenance
time for the views constructed by $\tau$ given a hierarchical query (Lemma
48). The maintenance time uses a new measure, which we relate to dynamic width
(Lemma 49). We finally show the running times of UpdateIndTree and
UpdateTrees.

######  Lemma 47.

Given a $\delta_{0}$-hierarchical query $Q(\mathcal{F})$, a canonical variable
order $\omega$ for $Q$, and a database of size $N$, the views constructed by
$\textsc{BuildVT}(\cdot,\omega,\mathcal{F})$ from Figure 6 in the dynamic mode
can be maintained under a single-tuple update to any input relation in
$\mathcal{O}(1)$ time.

###### Proof.

At each node $X$ of a canonical variable order $\omega$ for a
$\delta_{0}$-hierarchical query, the set $\mathcal{F}_{X}$ of free variables
is either $\mathsf{anc}(X)\cup\\{X\\}$ if $X$ is free, or $\mathsf{anc}(X)$ if
$X$ is bound because the set $\mathcal{F}\cap\mathit{vars}(\omega_{X})$ of
free variables in $\omega_{X}$ is empty for $\delta_{0}$-hierarchical queries.
The functions AuxView and NewVT maintain the following invariant for
$\delta_{0}$-hierarchical queries in the dynamic mode: If $X$ has a sibling
node in $\omega$, then the view created at node $X$ has $\mathsf{anc}(X)$ as
free variables. If $X$ is bound, then already $\mathcal{F}=\mathsf{anc}(X)$;
otherwise, AuxView constructs an extra view with $\mathsf{anc}(X)$ as free
variables.

Now consider an update $\delta{R}$ to a relation $R$. Due to the hierarchical
property of the input query, the update $\delta{R}$ fixes the values of all
variables on the path from the leaf $R$ to the root to constants. While
propagating an update through the view tree, the delta at each node $X$
requires joining with the views constructed for the siblings of $X$. Each of
the sibling views has $\mathsf{anc}(X)$ as free variables, as discussed above.
Thus, computing the delta at each node makes only constant-time lookups in the
sibling views. Overall, propagating the update through the view tree
constructed for a $\delta_{0}$-hierarchical query using BuildVT takes constant
time. ∎

Consider now a canonical variable order $\omega$ for a hierarchical query and
a set $\mathcal{F}$ of free variables. Given a node $X$ in $\omega$, let
$Q_{X}$ denote the join of $\mathit{atoms}(\omega_{X})$. We define
$\kappa(\omega,\mathcal{F})$ as:

$\max_{X\in\mathit{vars}(\omega)-\mathcal{F}}\
\max_{R(\mathcal{Y})\in\mathit{atoms}(\omega_{X})}\\{\rho_{Q_{X}}^{\ast}((\mathit{vars}(\omega_{X})\cap\mathcal{F})-\mathcal{Y})\\},$

The measure $\kappa(\omega,\mathcal{F})$ is the maximal fractional edge cover
number of $Q_{X}$ over the free variables occurring in the subtree
$\omega_{X}$ of $\omega$ rooted at a bound variable $X$, when the variables of
one atom $R(\mathcal{Y})$ in $\omega_{X}$ are excluded.

######  Lemma 48.

Given a hierarchical query $Q(\mathcal{F})$, a canonical variable order
$\omega$ for $Q$, a database of size $N$, and $\epsilon\in[0,1]$, the views
constructed by $\tau(\omega,\mathcal{F})$ from Figure 11 in the dynamic mode
can be maintained under a single-tuple update in
$\mathcal{O}(N^{\kappa(\omega,\mathcal{F})\epsilon})$ time.

###### Proof.

If $Q$ is $\delta_{0}$-hierarchical, the function $\tau$ returns a view tree
for $Q$ that admits $\mathcal{O}(1)$ update time, per Lemma 47.

Consider now a view tree created by $\tau$ for a non-$\delta_{0}$-hierarchical
query. Let us restrict this view tree such that the views created in the light
case are treated as leaf views. This restricted view tree encodes the result
of a $\delta_{0}$-hierarchical query! As the procedure $\tau$ traverses the
variable order in a top-down manner, every bound variable $X$ with a free
variable below is replaced by a set of view trees where $X$ is free (heavy
case) and by a view tree whose root view aggregates away $X$ and includes only
free variables (light case). Thus, single-tuple updates to the leaves of this
restricted view tree take constant time. That is, updates to the relations
that are not part of the views materialized in the light case are constant.

However, updates to the relations that are part of the views materialized in
the light case might not be constant. The view tree $ltree$ constructed by
BuildVT at a bound variable $X$ is defined over the light parts of relations
partitioned on $keys=\mathsf{anc}(X)\cup\\{X\\}$ (Line 16 in Figure 11). Each
view $V_{Z}$ in $ltree$ constructed at a variable $Z$ includes all the free
variables in $\omega_{Z}$. A single-tuple update $\delta{R}$ to any relation
$R$ in $ltree$ fixes the values of the variables $keys$, thus reducing the
size of other relations in $ltree$ to $\mathcal{O}(N^{\epsilon})$. The
maintenance cost for $V_{Z}$ under the update $\delta{R}$ with schema
$\mathcal{Y}$ is $\mathcal{O}(N^{m_{Z}\epsilon})$, where
$m_{Z}=\rho^{*}_{Q_{Z}}{((\mathit{vars}(\omega_{Z})\cap\mathcal{F})-\mathcal{Y})}$.
The maintenance cost for $ltree$ is dominated by the maintenance cost for its
root $V_{X}$.

The change computed at $V_{X}$ for the single-tuple update consist of
$\mathcal{O}(N^{m_{X}\epsilon})$ tuples and needs to be propagated further up
in the tree. Because there are no further light cases on the path from $X$ to
the root, the propagation cost is constant per tuple. The overall time needed
to maintain $V_{X}$ and propagate the change at $V_{X}$ up to the root is
$\mathcal{O}(N^{m^{\prime}_{X}\epsilon})$, where
$m^{\prime}_{X}=\max_{R(\mathcal{Y})\in\mathit{atoms}(\omega_{X})}\\{\rho_{Q_{X}}^{\ast}((\mathit{vars}(\omega_{X})\cap\mathcal{F})-\mathcal{Y})\\}$.
In the worst case, the root variable of $\omega$ is bound; then, maintaining
the root view and its descendants takes
$\mathcal{O}(N^{\kappa(\omega,\mathcal{F})\epsilon})$ time.

The views constructed by $\tau$ in the light cases thus determine the overall
maintenance $\mathcal{O}(N^{\kappa(\omega,\mathcal{F})\epsilon})$ time. ∎

We next relate the measure $\kappa(\omega,\mathcal{F})$ to dynamic width.

######  Lemma 49.

Given a canonical variable order $\omega$ for a hierarchical query
$Q(\mathcal{F})$ with dynamic width $\delta$, it holds that
$\kappa(\omega,\mathcal{F})\leq\delta$.

###### Proof.

Given any variable order $\omega^{\prime}$ for $Q$ and a variable $X$ in
$\omega^{\prime}$, we denote by $Q_{X}^{\omega^{\prime}}$ the query that joins
the atoms in $\mathit{atoms}(\omega_{X}^{\prime})$. To prove
$\kappa(\omega,\mathcal{F})\leq\delta$, we need to show that

$\displaystyle\kappa(\omega,\mathcal{F})\leq\delta(\omega^{f})$ (20)

for any free-top variable order $\omega^{f}$ for $Q$. It follows from the
definition of $\kappa(\omega,\mathcal{F})$ that $\omega$ has a bound variable
$X$ and an atom $R(\mathcal{Y})\in\mathit{atoms}(Q_{X}^{\omega})$ such that

$\displaystyle\kappa(\omega,\mathcal{F})=\rho_{Q_{X}^{\omega}}^{*}(\mathcal{B})$

where $\mathcal{B}=(\mathit{vars}(\omega_{X})\cap\mathcal{F})-\mathcal{Y}$.
Since $\omega$ is canonical, it holds:

  * $(*)$ Each atom in $Q$ containing a variable from $\mathcal{B}$ must contain $X$.

Let $\omega^{f}=(T,\textit{dep}_{\omega^{f}})$ be a free-top variable order
for $Q$. Property $(*)$ implies that the variables in $\mathcal{B}$ depend on
$X$. Since $X$ is bound and all variables in $\mathcal{B}$ are free, the
latter variables cannot be below $X$ in $\omega^{f}$. Hence,
$\mathcal{B}\subseteq\textit{dep}_{\omega^{f}}(X)$. Since $R(\mathcal{Y})$
contains $X$, it must be included in $\mathit{atoms}(\omega^{f}_{X})$. To
prove Inequality (20), it thus suffices to show:

$\displaystyle\rho_{Q}^{\ast}(\mathcal{B})\geq\rho_{Q_{X}^{\omega}}^{*}(\mathcal{B}).$
(21)

By Property $(*)$, each atom in $Q$ covering a variable from $\mathcal{B}$
contains $X$. Hence, all such atoms are contained in
$\mathit{atoms}(Q_{X}^{\omega})$. This implies that any fractional edge cover
$\boldsymbol{\lambda}^{\prime}$ of $\mathcal{B}$ using atoms in $Q$ can be
turned into a fractional edge cover $\boldsymbol{\lambda}$ of $B$ using atoms
in $Q_{X}^{\omega}$ such that
$\sum_{\lambda\in\boldsymbol{\lambda}}\lambda\leq\sum_{\lambda^{\prime}\in\boldsymbol{\lambda}^{\prime}}\lambda^{\prime}$.
This implies Inequality (21) and hence Inequality (20). ∎

######  Lemma 50.

Given an indicator tree $T_{Ind}$ constructed by IndicatorVTs from Figure 10
and a single-tuple update $\delta{R}$, UpdateIndTree from Figure 18 runs in
$\mathcal{O}(1)$ time.

###### Proof.

The tree $T_{Ind}$ encodes the result of a $\delta_{0}$-hierarchical query and
admits constant-time updates per Lemma 47. The remaining operations in
UpdateIndTree also take constant time. ∎

We next analyze the procedure UpdateTrees from Figure 19 under a single-tuple
update. Applying the update to each view tree from $\mathcal{T}$ (Line 1)
takes $\mathcal{O}(N^{\delta\epsilon})$ time, per Lemmas 48 and 49. We then
apply the update to each triple $(T_{All},T_{L},T_{H})$ of indicator view
trees. The tree $T_{All}$ is a view tree of a $\delta_{0}$-hierarchical query,
thus updating it takes constant time (Line 6). The tree $T_{L}$ is updated
using UpdateIndTree in constant time (Line 12), per Lemma 50. Both of these
changes may trigger a change in $\exists T_{H}$, and propagating
$\delta({\exists H})$ through each view tree from $\mathcal{T}$ (Lines 9 and
14) takes constant time since this change does not affect any view
materialized in the light case. Updating each light part of relation $R$ and
the affected view trees (Line 11) takes $\mathcal{O}(N^{\delta\epsilon})$
time, per Lemmas 48 and 49.

Overall, the procedure UpdateTrees maintains the views constructed by $\tau$
under a single-tuple update in $\mathcal{O}(N^{\delta\epsilon})$ time.

###  F.2 Proof of Proposition 25

######  Proposition 25.

Given a hierarchical query $Q(\mathcal{F})$ with static width $\mathsf{w}$, a
canonical variable order $\omega$ for $Q$, a database of size $N$, and
$\epsilon\in[0,1]$, major rebalancing of the views in the set of view trees
$\tau(\omega,\mathcal{F})$ takes $\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon})$
time.

###### Proof.

Consider the major rebalancing procedure from Figure 20. The light relation
parts can be computed in $\mathcal{O}(N)$ time. Proposition 21 implies that
the affected views can be recomputed in time
$\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon})$. ∎

###  F.3 Proof of Proposition 26

######  Proposition 26.

Given a hierarchical query $Q(\mathcal{F})$ with dynamic width $\delta$, a
canonical variable order $\omega$ for $Q$, a database of size $N$, and
$\epsilon\in[0,1]$, minor rebalancing of the views in the set of view trees
$\tau(\omega,\mathcal{F})$ takes $\mathcal{O}(N^{(\delta+1)\epsilon})$ time.

###### Proof.

Figure 21 shows the procedure for minor rebalancing of the tuples with the
partitioning value $key$ in the light part $R^{\mathcal{S}}$ of relation $R$.
Minor rebalancing either inserts fewer than $\frac{1}{2}M^{\epsilon}$ tuples
into $R^{\mathcal{S}}$ (heavy to light) or deletes at most
$\frac{3}{2}M^{\epsilon}$ tuples from $R^{\mathcal{S}}$ (light to heavy). Each
action updates the indicator trees $T_{L}$ and $T_{H}$ in constant time (lines
5 and 6), per Lemma 50. Propagating the update to the light part of relation
$R$ through each view tree from $\mathcal{T}$ (line 4) takes
$\mathcal{O}(N^{\delta\epsilon})$ time, per Lemmas 48 and 49. Propagating the
change $\delta(\exists{H})$ through each view tree from $\mathcal{T}$ takes
constant time (line 7), as discussed in the proof of Proposition 23. Since
there are $\mathcal{O}(M^{\epsilon})$ such operations and the size invariant
$\left\lfloor\frac{1}{4}M\right\rfloor\leq N<M$ holds, the total time is
$\mathcal{O}(N^{(\delta+1)\epsilon})$. ∎

###  F.4 Proof of Proposition 27

######  Proposition 27.

Given a hierarchical query $Q(\mathcal{F})$ with dynamic width $\delta$, a
canonical variable order $\omega$ for $Q$, a database of size $N$, and
$\epsilon\in[0,1]$, maintaining the views in the set of view trees
$\tau(\omega,\mathcal{F})$ under a sequence of single-tuple updates takes
$\mathcal{O}(N^{\delta\epsilon})$ amortized time per single-tuple update.

The proof of Proposition 27 is based on the proof from prior work (Section 4.1
in [27]). We start by defining the state that our approach initially creates
and maintains on updates.

######  Definition 51.

Given a database of size $N$ and $\epsilon\in[0,1]$, a state of the database
is a tuple $\mathcal{Z}=(\epsilon,M,\mathcal{T},\mathcal{T}^{Ind})$, where:

  * •

$M$ is a natural number such that the size invariant
$\left\lfloor\frac{1}{4}M\right\rfloor\leq N<M$ holds. $M$ is called the
threshold base.

  * •

$\mathcal{T}$ is a set of view trees produced by the procedure $\tau$ from
Figure 11.

  * •

$\mathcal{T}^{Ind}$ is a set of triplets $(T_{All},T_{L},T_{H})$ of indicator
view trees produced by the procedure $\tau$ from Figure 11.

The initial state $\mathcal{Z}$ of the database has $M=2\cdot N+1$ and the
view trees $\mathcal{T}$ and the indicator view trees $\mathcal{T}_{Ind}$
constructed in the preprocessing stage.

###### Proof of Proposition 27.

Let $\mathcal{Z}_{0}=(\epsilon,M_{0},\mathcal{T}_{0},\mathcal{T}^{Ind}_{0})$
be the initial state of a database of size $N_{0}$ and
$\mathit{u}_{0},\mathit{u}_{1},\ldots,\mathit{u}_{n-1}$ a sequence of
arbitrary single-tuple updates.

The application of this update sequence to $\mathcal{Z}_{0}$ yields a sequence
$\mathcal{Z}_{0}\overset{\mathit{u}_{0}}{\longrightarrow}\mathcal{Z}_{1}\overset{\mathit{u}_{1}}{\longrightarrow}\ldots\overset{\mathit{u}_{n-1}}{\longrightarrow}\mathcal{Z}_{n}$
of states, where $\mathcal{Z}_{i+1}$ is the result of executing the procedure
$\textsc{OnUpdate}(\mathcal{T}_{i},\mathcal{T}^{Ind}_{i},\mathit{u}_{i})$ from
Figure 22, for $0\leq i<n$. Let $c_{i}$ denote the actual execution cost of
$\textsc{OnUpdate}(\mathcal{T}_{i},\mathcal{T}^{Ind}_{i},\mathit{u}_{i})$. For
some $\Gamma>0$, we can decompose each cost $c_{i}$ as:

$\displaystyle
c_{i}=c_{i}^{\mathit{apply}}+c_{i}^{\mathit{major}}+c_{i}^{\mathit{minor}}+\Gamma,\text{\qquad
for }0\leq i<n,$

where $c_{i}^{\mathit{apply}}$, $c_{i}^{\mathit{major}}$, and
$c_{i}^{\mathit{minor}}$ are the actual costs of the subprocedures
UpdateTrees, MajorRebalancing, and MinorRebalancing, respectively, in
OnUpdate. If update $\mathit{u}_{i}$ causes no major rebalancing, then
$c_{i}^{\mathit{major}}=0$; similarly, if $\mathit{u}_{i}$ causes no minor
rebalancing, then $c_{i}^{\mathit{minor}}=0$. These actual costs admit the
following worst-case upper bounds:

$c^{\mathit{apply}}_{i}$ | $\leq\gamma M_{i}^{\delta\epsilon}$ | (by Proposition 23),
---|---|---
$c^{\mathit{major}}_{i}$ | $\leq\gamma M_{i}^{1+(\mathsf{w}-1)\epsilon}$ | (by Proposition 25), and
$c^{\mathit{minor}}_{i}$ | $\leq\gamma M_{i}^{(\delta+1)\epsilon}$ | (by Proposition 26),

where $\gamma$ is a constant derived from their asymptotic bounds, and $M_{i}$
is the threshold base of $\mathcal{Z}_{i}$. The rebalancing steps have higher
asymptotic costs than processing one update.

The crux of this proof is to show that assigning an amortized cost
$\hat{c}_{i}$ to each update $\mathit{u}_{i}$ accumulates enough budget to pay
for such expensive but less frequent rebalancing procedures. For any sequence
of $n$ updates, we show that the accumulated amortized cost is no smaller than
the accumulated actual cost:

$\displaystyle\sum_{i=0}^{n-1}\hat{c}_{i}\geq\sum_{i=0}^{n-1}c_{i}.$ (22)

The amortized cost assigned to an update $\mathit{u}_{i}$ is
$\hat{c}_{i}=\hat{c}^{\mathit{apply}}_{i}+\hat{c}^{\mathit{major}}_{i}+\hat{c}^{\mathit{minor}}_{i}+\Gamma$,
where

$\displaystyle\hat{c}^{\mathit{apply}}_{i}=\gamma
M_{i}^{\delta\epsilon},\hat{c}^{\mathit{major}}_{i}=4\gamma
M_{i}^{(\mathsf{w}-1)\epsilon},\hat{c}^{\mathit{minor}}_{i}=\gamma
M_{i}^{\delta\epsilon},\text{ and }$

$\Gamma$ and $\gamma$ are the constants used to upper bound the actual cost of
OnUpdate. In contrast to the actual costs $c^{\mathit{major}}_{i}$ and
$c^{\mathit{minor}}_{i}$, the amortized costs $\hat{c}^{\mathit{major}}_{i}$
and $\hat{c}^{\mathit{minor}}_{i}$ are always nonzero.

We prove that such amortized costs satisfy Inequality (22). Since
$\hat{c}^{\mathit{apply}}_{i}\geq c^{\mathit{apply}}_{i}$ for $0\leq i<n$, it
suffices to show that the following inequalities hold:

$\displaystyle\sum_{i=0}^{n-1}\hat{c}_{i}^{\mathit{major}}\geq\sum_{i=0}^{n-1}c_{i}^{\mathit{major}}\quad\text{and}$
(23)
$\displaystyle\sum_{i=0}^{n-1}\hat{c}_{i}^{\mathit{minor}}\geq\sum_{i=0}^{n-1}c_{i}^{\mathit{minor}}.$
(24)

We prove Inequalities (23) and (24) by induction on the length $n$ of the
update sequence.

##### Major rebalancing.

  * •

Base case: We show that Inequality (23) holds for $n=1$. The preprocessing
stage sets $M_{0}=2\cdot N_{0}+1$. If the initial database is empty, i.e.,
$N_{0}=0$, then $M_{0}=1$ and $\mathit{u}_{0}$ triggers major rebalancing (and
no minor rebalancing). The amortized cost
$\hat{c}_{0}^{\mathit{major}}=4\gamma M_{0}^{(\mathsf{w}-1)\epsilon}=4\gamma$
suffices to cover the actual cost $c_{0}^{\mathit{major}}\leq\gamma
M_{0}^{1+(\mathsf{w}-1)\epsilon}=\gamma$. If the initial database is nonempty,
$\mathit{u}_{0}$ cannot trigger major rebalancing (i.e., violate the size
invariant) because
$\left\lfloor\frac{1}{4}M_{0}\right\rfloor=\left\lfloor\frac{1}{2}N_{0}\right\rfloor\leq
N_{0}-1$ (lower threshold) and $N_{0}+1<M_{0}=2\cdot N_{0}+1$ (upper
threshold); then, $\hat{c}_{0}^{\mathit{major}}\geq c_{0}^{\mathit{major}}=0$.
Thus, Inequality (23) holds for $n=1$.

  * •

Inductive step: Assumed that Inequality (23) holds for all update sequences of
length up to $n-1$, we show it holds for update sequences of length $n$. If
update $\mathit{u}_{n-1}$ causes no major rebalancing, then
$\hat{c}_{n-1}^{\mathit{major}}=4\gamma M_{n-1}^{(\mathsf{w}-1)\epsilon}\geq
0$ and $c_{n-1}^{\mathit{major}}=0$, thus Inequality (23) holds for $n$.
Otherwise, if applying $\mathit{u}_{n-1}$ violates the size invariant, the
database size $N_{n}$ is either
$\left\lfloor\frac{1}{4}M_{n-1}\right\rfloor-1$ or $M_{n-1}$. Let
$\mathcal{Z}_{j}$ be the state created after the previous major rebalancing
or, if there is no such step, the initial state. For the former ($j>0$), the
major rebalancing step ensures $N_{j}=\frac{1}{2}M_{j}$ after doubling and
$N_{j}=\frac{1}{2}M_{j}-\frac{1}{2}$ or $N_{j}=\frac{1}{2}M_{j}-1$ after
halving the threshold base $M_{j}$; for the latter ($j=0$), the preprocessing
stage ensures $N_{j}=\frac{1}{2}M_{j}-\frac{1}{2}$. The threshold base $M_{j}$
changes only with major rebalancing, thus $M_{j}=M_{j+1}=\ldots=M_{n-1}$. The
number of updates needed to change the database size from $N_{j}$ to $N_{n}$
(i.e., between two major rebalancing) is at least $\frac{1}{4}M_{n-1}$ since
$\min\\{\frac{1}{2}M_{j}-1-(\left\lfloor\frac{1}{4}M_{n-1}\right\rfloor-1),M_{n-1}-\frac{1}{2}M_{j}\\}\geq\frac{1}{4}M_{n-1}$.
Then,

$\displaystyle\sum_{i=0}^{n-1}\hat{c}_{i}^{\mathit{major}}$
$\displaystyle\geq\sum_{i=0}^{j-1}c_{i}^{\mathit{major}}+\sum_{i=j}^{n-1}\hat{c}_{i}^{\mathit{major}}\qquad\qquad\qquad\textit{(induction
hypothesis)}$
$\displaystyle=\sum_{i=0}^{j-1}c_{i}^{\mathit{major}}+\sum_{i=j}^{n-1}4\gamma
M_{n-1}^{(\mathsf{w}-1)\epsilon}\qquad\qquad\textit{($M_{j}=\ldots=M_{n-1}$)}$
$\displaystyle\geq\sum_{i=0}^{j-1}c_{i}^{\mathit{major}}+\frac{1}{4}M_{n-1}\,4\gamma
M_{n-1}^{(\mathsf{w}-1)\epsilon}\qquad\textit{(at least $\frac{1}{4}M_{n-1}$
updates)}$ $\displaystyle=\sum_{i=0}^{j-1}c_{i}^{\mathit{major}}+\gamma
M_{n-1}^{1+(\mathsf{w}-1)\epsilon}$
$\displaystyle\geq\sum_{i=0}^{j-1}c_{i}^{\mathit{major}}+c_{n-1}^{\mathit{major}}=\sum_{i=0}^{n-1}c_{i}^{\mathit{major}}\qquad\textit{($c_{j}^{\mathit{major}}=\ldots=c_{n-2}^{\mathit{major}}=0$)}.$

Thus, Inequality (23) holds for update sequences of length $n$.

##### Minor rebalancing.

When the degree of a tuple of values in a partition changes such that the
heavy or light part condition no longer holds, minor rebalancing deletes heavy
tuples from or inserts light tuples into the light part of the relation. To
prove Inequality (24), we decompose the cost of minor rebalancing per triples
of indicator trees, relation partitions, and data values of its partitioning
key.

$\displaystyle c_{i}^{\mathit{minor}}$
$\displaystyle=\sum_{(T_{All},T_{L},T_{H})\in\mathcal{T}_{Ind}}\;\sum_{R^{\mathcal{S}}\in
T_{L}}\;\sum_{key\in\mathsf{Dom}(\mathcal{S})}c_{i}^{R^{\mathcal{S}},key}\quad\text{
and }$ $\displaystyle\hat{c}_{i}^{\mathit{minor}}$
$\displaystyle=\sum_{(T_{All},T_{L},T_{H})\in\mathcal{T}_{Ind}}\;\sum_{R^{\mathcal{S}}\in
T_{L}}\;\sum_{key\in\mathsf{Dom}(\mathcal{S})}\hat{c}_{i}^{R^{\mathcal{S}},key}$

We write $c_{i}^{R^{\mathcal{S}},key}$ and $\hat{c}_{i}^{R^{\mathcal{S}},key}$
to denote the actual and respectively amortized costs of minor rebalancing
caused by update $\mathit{u}_{i}$, for a light part $R^{\mathcal{S}}$
partitioned on $\mathcal{S}$ and a tuple $key$ with the schema $\mathcal{S}$
whose value comes from $\mathit{u}_{i}$. We denote the set of the light parts
of a relation $R$ by

$\displaystyle\mathcal{R}=\\{R^{\mathcal{S}}\mid(T_{All},T_{L},T_{H})\in\mathcal{T}_{Ind},R^{\mathcal{S}}\in
T_{L}\\}$

Consider the update $\mathit{u}_{i}$ of the form $\delta
R=\\{\textbf{t}\rightarrow m\\}$. If update $\mathit{u}_{i}$ triggers minor
rebalancing, then
$\sum_{R^{\mathcal{S}}\in\mathcal{R}}c_{i}^{R^{\mathcal{S}},\pi_{\mathcal{S}}\textbf{t}}=c_{i}^{\mathit{minor}}$;
otherwise,
$\sum_{R^{\mathcal{S}}\in\mathcal{R}}c_{i}^{R^{\mathcal{S}},\pi_{\mathcal{S}}\textbf{t}}=0$.
The amortized cost is
$\sum_{R^{\mathcal{S}}\in\mathcal{R}}\hat{c}_{i}^{R^{\mathcal{S}},\pi_{\mathcal{S}}\textbf{t}}=\hat{c}_{i}^{\mathit{minor}}$
regardless of whether $\mathit{u}_{i}$ causes minor rebalancing or not;
otherwise,
$\sum_{R^{\mathcal{S}}\in\mathcal{R}}\hat{c}_{i}^{R^{\mathcal{S}},\pi_{\mathcal{S}}\textbf{t}}=0$.
We prove that for a light part $R^{\mathcal{S}}$ of the partition of a
relation $R$, and any $key\in\mathsf{Dom}(\mathcal{S})$ the following
inequality holds:

$\displaystyle\sum_{i=0}^{n-1}\hat{c}_{i}^{R^{\mathcal{S}},key}\geq\sum_{i=0}^{n-1}c_{i}^{R^{\mathcal{S}},key}.$
(25)

Since the number of relation partitions of a relation is constant, Inequality
(24) follows directly from Inequality (25). We prove Inequality (25) by
induction on the length $n$ of the update sequence.

  * •

Base case: We show that Inequality (25) holds for $n=1$. Assume that update
$\mathit{u}_{0}$ is of the form $\delta R=\\{\textbf{t}\rightarrow m\\}$;
otherwise, $\hat{c}_{0}^{R^{\mathcal{S}},key}=c_{0}^{R^{\mathcal{S}},key}=0$,
and Inequality (25) follows trivially for $n=1$. If the initial database is
empty, $\mathit{u}_{0}$ triggers major rebalancing but no minor rebalancing,
thus $\hat{c}_{0}^{R^{\mathcal{S}},key}=\gamma M_{0}^{\delta\epsilon}\geq
c_{0}^{R^{\mathcal{S}},key}=0$. If the initial database is nonempty, each
relation is partitioned using the threshold $M_{0}^{\epsilon}$. For update
$\mathit{u}_{0}$ to trigger the minor rebalancing of $R^{\mathcal{S}}$, the
degree of the $\mathcal{S}$ tuple $key$ in $R^{\mathcal{S}}$ has to either
decrease from $\left\lceil M_{0}^{\epsilon}\right\rceil$ to
$\left\lceil\frac{1}{2}M_{0}^{\epsilon}\right\rceil-1$ (heavy to light) or
increase from $\left\lceil M_{0}^{\epsilon}\right\rceil-1$ to
$\left\lceil\frac{3}{2}M_{0}^{\epsilon}\right\rceil$ (light to heavy). The
former happens only if $\left\lceil M_{0}^{\epsilon}\right\rceil=1$ and update
$\mathit{u}_{0}$ removes the last tuple with the $\mathcal{S}$-tuple $key$
from $R^{\mathcal{S}}$, thus no minor rebalancing is needed; the latter cannot
happen since update $\mathit{u}_{0}$ can increase
$|\sigma_{\mathcal{S}=key}R^{\mathcal{S}}|$ to at most $\left\lceil
M_{0}^{\epsilon}\right\rceil$, and $\left\lceil
M_{0}^{\epsilon}\right\rceil<\left\lceil\frac{3}{2}M_{0}^{\epsilon}\right\rceil$.
In any case, $\hat{c}_{0}^{R^{\mathcal{S}},key}\geq
c_{0}^{R^{\mathcal{S}},key}$, implying that Inequality (25) holds for $n=1$.

  * •

Inductive step: Assuming that Inequality (25) holds for all update sequences
of length up to $n-1$, we show it holds for update sequences of length $n$.
Consider that update $u_{n-1}$ is of the form $\delta
R=\\{\textbf{t}\rightarrow m\\}$ and causes minor rebalancing for the light
part $R^{\mathcal{S}}$; otherwise, $\hat{c}_{n-1}^{R^{\mathcal{S}},key}\geq 0$
and $c_{n-1}^{R^{\mathcal{S}},key}=0$, and Inequality (25) follows trivially
for $n$. Let $\mathcal{Z}_{j}$ be the state created after the previous major
rebalancing or, if there is no such step, the initial state. The threshold
changes only with major rebalancing, thus $M_{j}=M_{j+1}=\ldots=M_{n-1}$.
Depending on the existence of minor rebalancing steps since state
$\mathcal{Z}_{j}$, we have two cases:

    * –

Case 1: There is no minor rebalancing for $R^{\mathcal{S}}$ caused by an
update of the form since state $\mathcal{Z}_{j}$; thus,
$c_{j}^{R^{\mathcal{S}},key}=\ldots=c_{n-2}^{R^{\mathcal{S}},key}=0$. From
state $\mathcal{Z}_{j}$ to state $\mathcal{Z}_{n}$, the number of tuples with
the $\mathcal{S}$-tuple $key$ either decreases from at least $\left\lceil
M_{j}^{\epsilon}\right\rceil$ to
$\left\lceil\frac{1}{2}M_{n-1}^{\epsilon}\right\rceil-1$ (heavy to light) or
increases from at most $\left\lceil M_{j}^{\epsilon}\right\rceil-1$ to
$\left\lceil\frac{3}{2}M_{n-1}^{\epsilon}\right\rceil$ (light to heavy). For
this change to happen, the number of updates needs to be greater than
$\frac{1}{2}M_{n-1}^{\epsilon}$ since $M_{j}=M_{n-1}$ and $\min\\{\left\lceil
M_{j}^{\epsilon}\right\rceil-(\left\lceil\frac{1}{2}M_{n-1}^{\epsilon}\right\rceil-1),\left\lceil\frac{3}{2}M_{n-1}^{\epsilon}\right\rceil-(\left\lceil
M_{j}^{\epsilon}\right\rceil-1)\\}>\frac{1}{2}M_{n-1}^{\epsilon}$. Then,

$\displaystyle\sum_{i=0}^{n-1}\hat{c}_{i}^{R^{\mathcal{S}},key}$
$\displaystyle\geq\sum_{i=0}^{j-1}c_{i}^{R^{\mathcal{S}},key}+\sum_{i=j}^{n-1}\hat{c}_{i}^{R^{\mathcal{S}},key}\qquad\qquad\textit{(induction
hypothesis)}$
$\displaystyle=\sum_{i=0}^{j-1}c_{i}^{R^{\mathcal{S}},key}+\sum_{i=j}^{n-1}\gamma
M_{n-1}^{\delta\epsilon}\qquad\qquad\textit{($M_{j}=\ldots=M_{n-1}$)}$
$\displaystyle>\sum_{i=0}^{j-1}c_{i}^{R^{\mathcal{S}},key}+M_{n-1}^{\epsilon}\gamma
M_{n-1}^{\delta\epsilon}\qquad\quad\textit{(more than $M_{n-1}^{\epsilon}$
updates)}$
$\displaystyle\geq\sum_{i=0}^{j-1}c_{i}^{R^{\mathcal{S}},key}+c_{n-1}^{R^{\mathcal{S}},key}$
$\displaystyle=\sum_{i=0}^{n-1}c_{i}^{R^{\mathcal{S}},key}\qquad\qquad\qquad\qquad\qquad\\!\textit{($c_{j}^{R^{\mathcal{S}},key}={...}=c_{n-2}^{R^{\mathcal{S}},key}=0$)}.$

    * –

Case 2: There is at least one minor rebalancing step for $R^{\mathcal{S}}$
caused by an update of the form $\delta R=\\{\textbf{t}^{\prime}\rightarrow
m^{\prime}\\}$ where $\pi_{\mathcal{S}}\hskip
1.00006pt\textbf{t}^{\prime}=key$ since state $\mathcal{Z}_{j}$. Let
$\mathcal{Z}_{\ell}$ denote the state created after the previous minor
rebalancing caused by an update of this form; thus,
$c_{\ell}^{R^{\mathcal{S}},key}=\ldots=c_{n-2}^{R^{\mathcal{S}},key}=0$. The
minor rebalancing steps creating $\mathcal{Z}_{\ell}$ and $\mathcal{Z}_{n}$
inserts or deletes tuples with the $\mathcal{S}$ tuples $key$. From state
$\mathcal{Z}_{\ell}$ to state $\mathcal{Z}_{n}$, the number of such tuples
either decreases from $\left\lceil\frac{3}{2}M_{l}^{\epsilon}\right\rceil$ to
$\left\lceil\frac{1}{2}M_{n-1}^{\epsilon}\right\rceil-1$ (heavy to light) or
increases from $\left\lceil\frac{1}{2}M_{l}^{\epsilon}\right\rceil-1$ to
$\left\lceil\frac{3}{2}M_{n-1}^{\epsilon}\right\rceil$ (light to heavy). For
this change to happen, the number of updates needs to be greater than
$M_{n-1}^{\epsilon}$ since $M_{l}=M_{n-1}$ and
$\min\\{\left\lceil\frac{3}{2}M_{l}^{\epsilon}\right\rceil-(\left\lceil\frac{1}{2}M_{n-1}^{\epsilon}\right\rceil-1),\left\lceil\frac{3}{2}M_{n-1}^{\epsilon}\right\rceil-(\left\lceil\frac{1}{2}M_{l}^{\epsilon}\right\rceil-1)\\}>M_{n-1}^{\epsilon}$.
Then,

$\displaystyle\hskip
19.91684pt\sum_{i=0}^{n-1}\hat{c}_{i}^{R^{\mathcal{S}},key}$
$\displaystyle\geq\sum_{i=0}^{\ell-1}c_{i}^{R^{\mathcal{S}},key}+\sum_{i=\ell}^{n-1}\hat{c}_{i}^{R^{\mathcal{S}},key}\qquad\qquad\textit{(induction
hypothesis)}$
$\displaystyle=\sum_{i=0}^{\ell-1}c_{i}^{R^{\mathcal{S}},key}+\sum_{i=\ell}^{n-1}\gamma
M_{n-1}^{\delta\epsilon}\qquad\qquad\textit{($M_{j}=\ldots=M_{n-1}$)}$
$\displaystyle>\sum_{i=0}^{\ell-1}c_{i}^{R^{\mathcal{S}},key}+M_{n-1}^{\epsilon}\gamma
M_{n-1}^{\delta\epsilon}\qquad\quad\textit{(more than $M_{n-1}^{\epsilon}$
updates)}$
$\displaystyle>\sum_{i=0}^{\ell-1}c_{i}^{R^{\mathcal{S}},key}+c_{n-1}^{R^{\mathcal{S}},key}$
$\displaystyle=\sum_{i=0}^{n-1}c_{i}^{R^{\mathcal{S}},key}\qquad\qquad\qquad\qquad\qquad\\!\textit{($c_{\ell}^{R^{\mathcal{S}},key}={...}=c_{n-2}^{R^{\mathcal{S}},key}=0$)}.$

Cases 1 and 2 imply that Inequality (25) holds for update sequences of length
$n$.

This shows that Inequality (22) holds when the amortized cost of
$\textsc{OnUpdate}(\mathcal{T}_{i},\mathcal{T}^{Ind}_{i},\mathit{u}_{i})$ is

$\hat{c}_{i}=\gamma M_{i}^{\delta\epsilon}+4\gamma
M_{i}^{(\mathsf{w}-1)\epsilon}+\gamma
M_{i}^{\delta\epsilon}+\Gamma,\text{\quad for }0\leq i<n,$

where $\Gamma$ and $\gamma$ are constants. The amortized cost
$\hat{c}^{\mathit{major}}_{i}$ of major rebalancing is $4\gamma
M_{i}^{(\mathsf{w}-1)\epsilon}$, and the amortized cost
$\hat{c}^{\mathit{minor}}_{i}$ of minor rebalancing is $\gamma
M_{i}^{\delta\epsilon}$. From the size invariant
$\left\lfloor\frac{1}{4}M_{i}\right\rfloor\leq N_{i}<M_{i}$ follows that
$N_{i}<M_{i}<4(N_{i}+1)$ for $0\leq i<n$, where $N_{i}$ is the database size
before update $\mathit{u}_{i}$. This implies that for any database of size
$N$, the amortized major rebalancing time is
$\mathcal{O}(N^{(\mathsf{w}-1)\epsilon})$ and the amortized minor rebalancing
time is $\mathcal{O}(N^{\delta\epsilon})$. From $\mathsf{w}-1\leq\delta$ in
Proposition 17, it follows that the overall amortized update time is
$\mathcal{O}(N^{\delta\epsilon})$. ∎