# Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries

Ahmet Kara1, Milos Nikolic2, Dan Olteanu1, Haozhe Zhang1

1University of Oxford 2University of Edinburgh

###### Abstract

We investigate trade-offs in static and dynamic evaluation of hierarchical
queries with arbitrary free variables. In the static setting, the trade-off is
between the time to partially compute the query result and the delay needed to
enumerate its tuples. In the dynamic setting, we additionally consider the
time needed to update the query result under single-tuple inserts or deletes
to the database.

Our approach observes the degree of values in the database and uses different
computation and maintenance strategies for high-degree (heavy) and low-degree
(light) values. For the latter it partially computes the result, while for the
former it computes enough information to allow for on-the-fly enumeration.

The main result of this work defines the preprocessing time, the update time,
and the enumeration delay as functions of the light/heavy threshold. By
conveniently choosing this threshold, our approach recovers a number of prior
results when restricted to hierarchical queries.

For a restricted class of hierarchical queries, our approach can achieve
worst-case optimal update time and enumeration delay conditioned on the Online
Matrix-Vector Multiplication Conjecture.

##### Acknowledgements.

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under grant agreement No 682588.

##  1 Introduction

The problems of static evaluation, i.e., computing the result of a query [50,
45, 33, 39], and dynamic evaluation, i.e., maintaining the query result under
data updates [34, 16, 35, 10, 25, 27], are fundamental to relational
databases.

We consider a refinement of these problems that decomposes the overall
computation time into the preprocessing time, which is used to compute a data
structure that represents the query result, the update time, which is the time
to update the data structure under inserts and deletes to the input data, and
the enumeration delay, which is the time to list one distinct tuple after
another one has been listed from the data structure [18]. In this paper we
investigate the relationship between preprocessing, update, and delay. For
instance, how much preprocessing time would be needed to achieve sublinear
enumeration delay?

This paper characterizes the static and dynamic spaces for a subclass of
$\alpha$-acyclic queries called hierarchical queries:

######  Definition 1 ([49, 10]).

A conjunctive query is hierarchical if for any two variables, their sets of
atoms in the query are either disjoint or one is contained in the other.

For instance, the query $Q(\mathcal{F})=R(A,B),S(B,C)$ is hierarchical, while
$Q(\mathcal{F})=R(A,B),S(B,C),T(C)$ is not, for any
$\mathcal{F}\subseteq\\{A,B,C\\}$. In our study, we do not set any restriction
on the set of free variables of a hierarchical query. Hierarchical queries
play a key role in studies of query evaluation in the probabilistic [49, 21],
provenance [44], streaming [22, 10], and parallel [36, 24] settings.

We next state our main result in the static setting.

Complexities forHierarchical QueriesTrade-offs inStatic Query EvaluationTrade-
offs inDynamic Query
Evaluation$0$$1$$1$$\mathsf{w}-1$$\mathsf{w}$$\epsilon$$\log_{N}$
timepreprocessing time ${1+(\mathsf{w}-1)\epsilon}$update time
$\delta\epsilon$delay  $1-\epsilon$$0$$1$$\mathsf{w}$$1$$\log_{N}$
delay$\log_{N}$ preprocessing timeconjunctive$\alpha$-acyclicfree-
connexhierarchical$\log_{N}$delayABC$\log_{N}$preprocessing
time$\log_{N}$update time$0$$(1,0,1)$$1$$1$$\mathsf{w}$$\delta$free-
connex1conjunctiveq-hierarchicalhierarchical Figure 1:  Left: Preprocessing
time, enumeration delay, and amortized update time for a hierarchical query
with static width $\mathsf{w}$ and dynamic width $\delta$ ($\delta$ can be
$\mathsf{w}$ or $\mathsf{w}-1$, hence the two red lines for the update time).
Middle and right: Trade-offs in static and dynamic evaluation. Our approach
achieves each blue point and each point on the blue lines. Prior approaches
are represented by one point in the trade-off space.

######  Theorem 2.

Given a hierarchical query with static width $\mathsf{w}$, 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.

The measure $\mathsf{w}$, previously introduced as $s^{\uparrow}$ [45],
generalizes the fractional hypertree width [38] from Boolean to arbitrary
conjunctive queries. For Functional Aggregate Queries, this measure becomes
the FAQ-width [1]. In this paper, we refer to it as the static width of the
query.

######  Proposition 3.

Any free-connex hierarchical query has static width 1.

Theorem 2 expresses the runtime components as functions of a parameter
$\epsilon$ (Figure 1). By appropriately setting $\epsilon$, it recovers prior
results restricted to hierarchical queries. For $\epsilon=0$, both the
preprocessing time and the delay become $O(N)$, as for $\alpha$-acyclic
queries [8]. For $\epsilon=1$, we obtain $\mathcal{O}(N^{\mathsf{w}})$
preprocessing time and $O(1)$ delay as for conjunctive queries [45]. For free-
connex queries, $\mathsf{w}=1$ and the preprocessing time remains $O(N)$
regardless of $\epsilon$; we then choose $\epsilon=1$ to obtain $O(1)$ delay
[8]. For bounded-degree databases, i.e., where each value appears at most $c$
times for some constant $c=N^{\beta}$, first-order queries admit $O(N)$
preprocessing time and $O(1)$ delay [18, 30]. We recover the $O(1)$ delay
using $\epsilon=1$. The preprocessing time becomes
$\mathcal{O}(N\cdot(N^{\beta})^{\mathsf{w}-1})=\mathcal{O}(N)$ if our approach
uses the constant upper bound $c$ instead of the upper bound $N^{\epsilon}$ on
the degrees.

The dynamic case generalizes the static case.

######  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.

Our approach can achieve sublinear amortized update time and delay for
hierarchical queries with arbitrary free variables. For any
$\epsilon=\frac{1}{\delta+\alpha}>0$ with $\alpha>0$, our algorithm has update
time $\mathcal{O}(N^{1-\alpha\cdot\frac{1}{\delta+\alpha}})$ and delay
$\mathcal{O}(N^{1-\frac{1}{\delta+\alpha}})$.

The dynamic width $\delta$ can be $\mathsf{w}-1$ or $\mathsf{w}$. The update
time for a single tuple is at most the preprocessing time:
$\delta\epsilon\leq\epsilon+(\mathsf{w}-1)\epsilon\leq
1+(\mathsf{w}-1)\epsilon$. If $\delta=\mathsf{w}-1$, then
$\delta\epsilon=(\mathsf{w}-1)\epsilon$, i.e., the update time is an
$\mathcal{O}(N)$ factor less than the preprocessing time. The complexity of
preprocessing thus amounts to inserting $N$ tuples in an initially empty
database using our update mechanism. If $\delta=\mathsf{w}$, then inserting
$N$ tuples would need $\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon+\epsilon})$
time, which is an $\mathcal{O}(N^{\epsilon})$ factor more than the complexity
of one bulk update using our preprocessing algorithm. This suggests a gap
between single-tuple updates and bulk updates. A similar gap highlighting a
fundamental limitation of single-tuple updates has been shown for the Loomis-
Whitney query that generalizes the triangle query from a join of three binary
relations to a join of $n$ $(n-1)$-ary relations: The amortized update time
for single-tuple updates is $\mathcal{O}(N^{1/2})$, which is worst-case
optimal unless the OMv conjecture fails [28]. Inserting $N$ tuples in the
empty database would cost $\mathcal{O}(N^{3/2})$, yet the query can be
computed in the static setting in time $\mathcal{O}(N^{\frac{n}{n-1}})$ [39].

Static Query Evaluationpreprocessing time / enumeration
delayconjunctive$\mathcal{O}(N^{\mathsf{w}})$ /
$\mathcal{O}(1)$[45]$\alpha$-acyclic$\mathcal{O}(N)$ /
$\mathcal{O}(N)$[8]hierarchical$\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon})$ /
$\mathcal{O}(N^{1-\epsilon})$$\epsilon\in[0,1]$free-connex$\mathcal{O}(N)$ /
$\mathcal{O}(1)$[8]Dynamic Query Evaluationpreprocessing time / enumeration
delay / update timeconjunctive$\mathcal{O}(N^{\mathsf{w}})$ / $\mathcal{O}(1)$
/ $\mathcal{O}(N^{\delta})$ [42]triangle query $\mathcal{O}(N^{\frac{3}{2}})$
/ $\mathcal{O}(1)$ / $\mathcal{O}(N^{\frac{1}{2}})^{\ast}$
[27]$\alpha$-acyclicfree-connex$\mathcal{O}(N)$ / $\mathcal{O}(1)$ /
$\mathcal{O}(N)$[25]q-hierarchical$=$$\delta_{0}$-hierarchical$\mathsf{w}=1$,
$\delta=0$[10]hierarchical$\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon})$ /
$\mathcal{O}(N^{1-\epsilon})$ /
$\mathcal{O}(N^{\delta\epsilon})^{\ast}$$\epsilon\in[0,1]$$\delta_{1}$-hierarchical$\mathsf{w}\in\\{1,2\\}$,
$\delta=1$ Figure 2: Landscapes of static and dynamic query evaluation.
$\mathsf{w}$: static width; $\delta$: dynamic width; *: amortized time.

Theorem 4 recovers prior work on conjunctive [42], free-connex [25], and
q-hierarchical [10] queries by setting $\epsilon=1$ (Figure 1). For general
hierarchical queries, our approach then achieves the same complexities as
prior work on conjunctive queries. For free-connex queries, we obtain linear-
time preprocessing and update and constant-time delay since $\mathsf{w}=1$ and
$\delta\in\\{0,1\\}$. For q-hierarchical queries, we obtain linear-time
preprocessing and constant-time update and delay since $\mathsf{w}=1$ and
$\delta=0$. Existing maintenance approaches, e.g, classical first-order IVM
[16] and higher-order recursive IVM [35], DynYannakakis [25], and F-IVM [42],
can achieve constant delay for general hierarchical queries yet after at least
linear-time updates. Figure 2 depicts the relationship of our results in
Theorems 2 and 4 with prior results.

We next introduce a syntactic characterization of hierarchical queries based
on their dynamic width.

######  Definition 5.

A hierarchical query is $\delta_{i}$-hierarchical for $i\in\mathbb{N}_{0}$ if
$i$ is the smallest number such that for each bound variable $X$ and atom
$R(\mathcal{Y})$ of $X$, there are $i$ atoms
$R_{1}(\mathcal{Y}_{1}),\ldots,R_{i}(\mathcal{Y}_{i})$ such that all free
variables in the atoms of $X$ are included in
$\mathcal{Y}\cup\bigcup_{j\in[i]}\mathcal{Y}_{j}$.

For instance, the query
$Q(Y_{0},\ldots,Y_{i})=R_{0}(X,Y_{0}),\ldots,R_{i}(X,Y_{i})$ is a
$\delta_{i}$-hierarchical query for $i\in\mathbb{N}_{0}$.

The class of hierarchical queries can be partitioned into subclasses of
$\delta_{i}$-hierarchical queries for $i\in\mathbb{N}_{0}$. Then, the
$\delta_{0}$-hierarchical queries are precisely the q-hierarchical queries
from prior work [10].

######  Proposition 6.

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

As depicted in Figure 2, all free-connex hierarchical queries are either
$\delta_{0}$\- or $\delta_{1}$-hierarchical.

######  Proposition 7.

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

The following proposition relates $\delta_{i}$-hierarchical queries to their
dynamic width.

######  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 and Theorem 4 imply the following corollary.

######  Corollary 9.

Given a $\delta_{i}$-hierarchical query with $i\in\mathbb{N}_{0}$ and static
width $\mathsf{w}$, 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^{i\epsilon})$ amortized time for single-tuple updates.

For $\delta_{1}$-hierarchical queries, the upper bound from Corollary 9 is
matched by a lower bound conditioned on the Online Matrix-Vector
Multiplication (OMv) Conjecture [23].

######  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 blue line in Figure 3 visualizes the trade-offs of our approach for
$\delta_{1}$-hierarchical queries. The gray cuboid is infinite in the
dimension of preprocessing time. Each point strictly included in the gray
cuboid corresponds to a combination of some preprocessing time and
$\mathcal{O}(N^{\frac{1}{2}-\gamma})$ amortized update time and delay for
$\gamma>0$. Following Proposition 10, this is not attainable. Each point on
the surface of the cuboid corresponds to Pareto worst-case optimality in the
update-delay trade-off space. For $\epsilon=\frac{1}{2}$, our approach needs
$\mathcal{O}(N^{\frac{1}{2}})$ amortized update time and delay, which is
weakly Pareto worst-case optimal: there can be no tighter upper bounds for
both the update time and delay. Since $\mathsf{w}\in\\{1,2\\}$ for
$\delta_{1}$-hierarchical queries, the preprocessing time is
$O(N^{\frac{3}{2}})$.

Appendix A exemplifies our approach for the $\delta_{1}$-hierarchical queries
$Q(A)=R(A,B),S(B)$ and $Q(A,C)=R(A,B),S(B,C)$. All proofs are given in the
appendix.

$\log_{N}$delay$\log_{N}$preprocessing time$\log_{N}$update
time$0$$(1,0,1)$$1$$(2,1,0)$$1$$2$$\delta=1$$\frac{1}{2}$$\frac{1}{2}$$(\frac{3}{2},\frac{1}{2},\frac{1}{2})$weakly
Pareto optimal Figure 3: The trade-off of our approach (blue line) for
$\delta_{1}$-hierarchical queries. No point in the gray cuboid is attainable
unless the OMv conjecture fails. The cuboid surface corresponds to Pareto
worst-case optimal update-delay times.

##  2 Related Work

We complement our discussion in the introduction with further prior work on
static and dynamic query evaluation. Figures 4 and 5 give taxonomies of works
on static and dynamic query evaluation.

Class of Databases | Class of Queries | Preprocessing | Delay | Extra Space | Source
---|---|---|---|---|---
All |  f.c. $\alpha$-acyclic CQ≠ | $\mathcal{O}(N)$ | $\mathcal{O}(1)$ | $\mathcal{O}(N)$ | [8]
All |  f.c. $\beta$-acyclic negative CQ | $\mathcal{O}(N)$ | $\mathcal{O}(1)$ | – | [14, 13]
All | f.c. signed-acyclic CQ | $\mathcal{O}(N\,(\log N)^{|Q|})$ | $\mathcal{O}(1)$ | – | [14]
All |  Acyclic CQ≠ | $\mathcal{O}(N)$ | $\mathcal{O}(N)$ | $\mathcal{O}(N)$ | [8]
All |  CQ≠ of f.c. treewidth $k$ | $\mathcal{O}(|\text{Dom}|^{k+1}+N)$ | $\mathcal{O}(1)$ | – | [8]
All | CQ | $\mathcal{O}(N^{\mathsf{w}(Q)})$ | $\mathcal{O}(1)$ | $\mathcal{O}(N^{\mathsf{w}(Q)})$ | [45, 1]
All | Full CQ with access patterns | $\mathcal{O}(N^{\rho^{*}(Q)})$ | $\mathcal{O}(\tau)$ | $\mathcal{O}(N+N^{\rho^{*}(Q)}/\tau)$ | [17]
X-structures (trees, grids) | CQ | $\mathcal{O}(N)$ | $\mathcal{O}(N)$ | – | [7]
Bounded degree | FO | $\mathcal{O}(N)$ | $\mathcal{O}(1)$ | – | [18, 30]
Bounded expansion | FO | $\mathcal{O}(N)$ | $\mathcal{O}(1)$ | – | [31]
Local bounded expansion | FO | $\mathcal{O}(N^{1+\gamma})$ | $\mathcal{O}(1)$ | – | [48]
Low degree | FO | $\mathcal{O}(N^{1+\gamma})$ | $\mathcal{O}(1)$ | $\mathcal{O}(N^{2+\gamma})$ | [19]
Nowhere dense | FO | $\mathcal{O}(N^{1+\gamma})$ | $\mathcal{O}(1)$ | $\mathcal{O}(N^{1+\gamma})$ | [46]
Bounded treewidth | MSO | $\mathcal{O}(N)$ | $\mathcal{O}(1)$ | – | [6, 32]
Figure 4: Prior work on the trade-off between preprocessing time, enumeration delay, and extra space for different classes of queries (Conjunctive Queries, First-Order, Monadic Second-Order) and static databases under data complexity; f.c. stands for free-connex. Parameters: Query $Q$ with factorization width $\mathsf{w}$ [45] and fractional edge cover number $\rho^{*}$ [5]; database of size $N$; slack $\tau$ is a function of $N$ and $\rho^{*}$; $\gamma>0$. Most works do not discuss the extra space utilization (marked by –). Class of Databases | Class of Queries | Preprocessing | Update | Delay | Extra Space | Source
---|---|---|---|---|---|---
All |  $q$-hierarchical CQ | $\mathcal{O}(N)$ | $\mathcal{O}(1)$ | $\mathcal{O}(1)$ | – | [10, 25]
All | Triangle count | $\mathcal{O}(N^{\frac{3}{2}})$ | $\mathcal{O}(N^{\max\\{\epsilon,1-\epsilon\\}})^{\text{\Cross}}$ | $\mathcal{O}(1)$ | $\mathcal{O}(N^{1+\min\\{\epsilon,1-\epsilon\\}})$ | [27]
All | Full triangle query | $\mathcal{O}(N^{\frac{3}{2}})$ | $\mathcal{O}(N^{\frac{3}{2}})^{\text{\Cross}}$ | $\mathcal{O}(1)$ | $\mathcal{O}(N^{\frac{3}{2}})$ | [29]
All |  $q$-hierarchical UCQ | $\mathcal{O}(N)$ | $\mathcal{O}(1)$ | $\mathcal{O}(1)$ | – | [12]
Bounded degree | FO+MOD | $\mathcal{O}(N)$ | $\mathcal{O}(1)$ | $\mathcal{O}(1)$ | – | [11]
Strings | MSO | $\mathcal{O}(N)$ | $\mathcal{O}(\log N)$ | $\mathcal{O}(1)$ | – | [41]
Figure 5: Prior work on the trade-off between preprocessing time, update time,
enumeration delay, and extra space for different classes of queries
(Conjunctive Queries, Count Queries, First-Order Queries with modulo-counting
quantifiers, Monadic Second Order Logic) and databases under updates in data
complexity. Parameters: Query $Q$; database of size $N$; $\epsilon\in[0,1]$.
Most works do not discuss the extra space utilization (marked by –). †:
amortized update time.

##### Static Evaluation.

Prior work exhibits a dependency between the space and enumeration delay for
conjunctive queries with access patterns [17]. It constructs a succinct
representation of the query result that allows for enumeration of tuples over
some variables under value bindings for all other variables. It does not
support enumeration for queries with free variables, as addressed in our work.
It also states Example 28 as an open problem.

The result of any $\alpha$-acyclic conjunctive query can be enumerated with
constant delay after linear-time preprocessing if and only if it is free-
connex. This is under the conjecture that Boolean multiplication of $n\times
n$ matrices cannot be done in $O(n^{2})$ time [8]. More recently, this was
shown to hold also under the hypothesis that the existence of a triangle in a
hypergraph of $n$ vertices cannot be tested in time $\mathcal{O}(n^{2})$ and
that for any $k$, testing the presence of a $k$-dimensional tetrahedron cannot
be decided in linear time [14]. The free-connex characterization generalizes
in the presence of functional dependencies [15]. An in-depth pre-2015 overview
on constant-delay enumeration is provided by Segoufin [47].

There are also enumeration algorithms for document spanners [4] and satisfying
valuations of circuits [2].

##### Dynamic evaluation.

The q-hierarchical queries are the conjunctive queries that admit linear-time
preprocessing and constant-time update and delay [10, 25]. If a conjunctive
query without repeating relation symbols is not q-hierarchical, there is no
$\gamma>0$ such that the query result can be enumerated with
$\mathcal{O}(N^{\frac{1}{2}-\gamma})$ delay and update time, unless the Online
Matrix Vector Multiplication conjecture fails. The constant delay and update
time carry over to first-order queries with modulo-counting quantifiers on
bounded degree databases, unions of q-hierarchical queries [12], and
q-hierarchical queries with small domain constraints [11].

Prior work characterizes the preprocessing-space-update trade-off for counting
triangles under updates [27]. A follow-up work generalizes this approach to
the triangle queries with arbitrary free variables, adding the enumeration
delay to the trade-off space [29]. In this work, we consider arbitrary
hierarchical queries instead of the triangle queries, and we use a less
trivial adaptive maintenance technique, where the same relation may be subject
to partition on different tuples of variables and where the overall number of
cases for each partition is reduced to only two: the all-light case and the
at-least-one-heavy case.

MSO queries on strings admit linear-time preprocessing, constant delay, and
logarithmic update time. Here, updates can relabel, insert, or remove
positions in the string. Further work considers MSO queries on trees under
updates [40, 37, 3].

DBToaster [35], F-IVM [42], and DynYannakakis [25, 26] are recent systems
implementing incremental view maintenance approaches.

##### Hierarchical queries.

The notion of hierarchical queries used in this paper (Definition 1) has been
initially introduced in the context of probabilistic databases [49].

The Boolean conjunctive queries without repeating relation symbols that can be
computed in polynomial time on tuple-independent probabilistic databases are
hierarchical; non-hierarchical queries are hard for #P [49]. This was extended
to non-Boolean queries with negation [21].

Hierarchical queries are the conjunctive queries whose provenance admits a
factorized representation where each input tuple occurs a constant number of
times; any factorization of the provenance of a non-hierarchical query would
require a number of occurrences of the provenance of some input tuple
dependent on the input database size [44].

In the MPC model, the hierarchical queries admit parallel evaluation with one
communication step [36]. The $r$-hierarchical queries, which are conjunctive
queries that become hierarchical by repeatedly removing the atoms whose
complete set of variables occurs in another atom, can be evaluated in the MPC
model using a constant number of steps and optimal load on every single
database instance [24].

Hierarchical queries also admit one-step streaming evaluation in the finite
cursor model [22]. Under updates, the $q$-hierarchical queries are the
conjunctive queries that admit constant-time update and delay [10]. The
$q$-hierarchical queries are a proper subclass of both the free-connex
$\alpha$-acyclic and hierarchical queries. In addition to being hierarchical,
a second condition holds for a $q$-hierarchical query: if the set of atoms of
a free variable is strictly contained in the set of another variable, then the
latter must also be free.

##  3 Preliminaries

##### Data Model.

A schema $\mathcal{X}=(X_{1},\ldots,X_{n})$ is a non-empty tuple of distinct
variables. Each variable $X_{i}$ has a discrete domain $\mathsf{Dom}(X_{i})$.
We treat schemas and sets of variables interchangeably, assuming a fixed
ordering of variables. A tuple $\mathbf{x}$ of data values over schema
$\mathcal{X}$ is an element from
$\mathsf{Dom}(\mathcal{X})=\mathsf{Dom}(X_{1})\times\dots\times\mathsf{Dom}(X_{n})$.

A relation $R$ over schema $\mathcal{X}$ is a function
$R:\mathsf{Dom}(\mathcal{X})\to\mathbb{Z}$ such that the multiplicity
$R(\mathbf{x}$ is non-zero for finitely many tuples $\mathbf{x}$. A tuple
$\mathbf{x}$ is in $R$, denoted by $\mathbf{x}\in R$, if $R(\mathbf{x})\neq
0$. The notation $\exists{R}$ denotes the use of $R$ with set semantics:
$\exists{R}(\mathbf{x})$ equals $1$ if $\mathbf{x}\in R$ and $0$ otherwise;
also, $\nexists{R}(\mathbf{x})=1-\exists{R}(\mathbf{x})$. The size $|R|$ of
$R$ is the size of the set $\\{\mathbf{x}\mid\mathbf{x}\in R\\}$. A database
is a set of relations and has size given by the sum of the sizes of its
relations.

Given a tuple $\mathbf{x}$ over schema $\mathcal{X}$ and
$\mathcal{S}\subseteq\mathcal{X}$, $\mathbf{x}[\mathcal{S}]$ denotes the
restriction of $\mathbf{x}$ to $\mathcal{S}$ such that the values in
$\mathbf{x}[\mathcal{S}]$ follow the ordering in $\mathcal{S}$. For instance,
$(a,b,c)[(C,A)]=(c,a)$ for the tuple $(a,b,c)$ over the schema $(A,B,C)$. For
a relation $R$ over $\mathcal{X}$, schema $\mathcal{S}\subseteq\mathcal{X}$,
and tuple $\mathbf{t}\in\mathsf{Dom}(\mathcal{S})$,
$\sigma_{\mathcal{S}=\mathbf{t}}R=\\{\,\mathbf{x}\,\mid\,\mathbf{x}\in
R\land\mathbf{x}[\mathcal{S}]=\mathbf{t}\,\\}$ denotes the set of tuples in
$R$ that agree with $\mathbf{t}$ on the variables in $\mathcal{S}$, while
$\pi_{\mathcal{S}}R=\\{\,\mathbf{x}[\mathcal{S}]\,\mid\,\mathbf{x}\in R\,\\}$
denotes the set of restrictions of the tuples in $R$ to the variables in
$\mathcal{S}$.

##### Computational Model.

We consider the RAM model of computation. Each relation (or materialized view)
$R$ over schema $\mathcal{X}$ is implemented by a data structure that stores
key-value entries $(\mathbf{x},R(\mathbf{x}))$ for each tuple $\mathbf{x}$
with $R(\mathbf{x})\neq 0$ and needs $O(|R|)$ space. This data structure can:
(1) look up, insert, and delete entries in constant time, (2) enumerate all
stored entries in $R$ with constant delay, and (3) report $|R|$ in constant
time. For a schema $\mathcal{S}\subset\mathcal{X}$, we use an index data
structure that for any $\mathbf{t}\in\mathsf{Dom}(\mathcal{S})$ can: (4)
enumerate all tuples in $\sigma_{\mathcal{S}=\mathbf{t}}R$ with constant
delay, (5) check $\mathbf{t}\in\pi_{\mathcal{S}}R$ in constant time; (6)
return $|\sigma_{\mathcal{S}=\mathbf{t}}R|$ in constant time; and (7) insert
and delete index entries in constant time.

We give an example data structure that implements a relation. Consider a
relation $R$ over schema $\mathcal{X}$. A hash table with chaining stores key-
value entries $(\mathbf{x},R(\mathbf{x}))$ for each tuple $\mathbf{x}$ over
$\mathcal{X}$ with $R(\mathbf{x})\neq 0$. The entries are doubly linked to
support enumeration with constant delay. The hash table can report the number
of its entries in constant time and supports lookups, inserts, and deletes in
constant time on average, under the assumption of simple uniform hashing.

To support index operations on a schema $\mathcal{F}\subset\mathcal{X}$, we
create another hash table with chaining where each table entry stores an
$\mathcal{F}$-value $\mathbf{t}$ as key and a doubly-linked list of pointers
to the entries in $R$ having $\mathbf{t}$ as $\mathcal{F}$-value. Looking up
an index entry given $\mathbf{t}$ takes constant time on average under simple
uniform hashing, and its doubly-linked list enables enumeration of the
matching entries in $R$ with constant delay. Inserting an index entry into the
hash table additionally prepends a new pointer to the doubly-linked list for a
given $\mathbf{t}$; overall, this operation takes constant time on average.
For efficient deletion of index entries, each entry in $R$ also stores back-
pointers to its index entries (one back-pointer per index for $R$). When an
entry is deleted from $R$, locating and deleting its index entries in doubly-
linked lists takes constant time per index.

##### Modeling Updates Using Multiplicities.

We restrict multiplicities of tuples in the input relations and views to be
strictly positive. Multiplicity 0 means the tuple is not present. A single-
tuple update to a relation $R$ is expressed as $\delta
R=\\{\mathbf{x}\rightarrow m\\}$. It is an insert of the tuple $\mathbf{x}$ in
$R$ if the multiplicity $m$ is strictly positive. It is a delete of the tuple
$\mathbf{x}$ from $R$ if its multiplicity $m$ is negative. Such a delete is
rejected if the existing multiplicity of $\mathbf{x}$ in $R$ is less than
$|m|$.

##### Partitioning.

We partition relations based on value degree.

######  Definition 11.

Given a relation $R$ over schema $\mathcal{X}$, a schema
$\mathcal{S}\subset\mathcal{X}$, and a threshold $\theta$, the pair $(H,L)$ of
relations is a partition of $R$ on $\mathcal{S}$ with threshold $\theta$ if it
satisfies the following conditions:
(union) $R(\mathbf{x})=H(\mathbf{x})+L(\mathbf{x})$ for
$\mathbf{x}\in\mathsf{Dom}(\mathcal{X})$ (domain partition)
$\pi_{\mathcal{S}}H\cap\pi_{\mathcal{S}}L=\emptyset$ (heavy part) for all
$\mathbf{t}\in\pi_{\mathcal{S}}H$:
$|\sigma_{\mathcal{S}=\mathbf{t}}H|\geq\frac{1}{2}\theta$ (light part) for all
$\mathbf{t}\in\pi_{\mathcal{S}}L$:
$|\sigma_{\mathcal{S}=\mathbf{t}}L|<\frac{3}{2}\theta$
The pair $(H,L)$ is a strict partition of $R$ on $\mathcal{S}$ with threshold
$\theta$ if it satisfies the union and domain partition conditions and strict
versions of the heavy and light part conditions:
(strict heavy part) for all
$\mathbf{t}\in\pi_{\mathcal{S}}H:\;|\sigma_{\mathcal{S}=\mathbf{t}}H|\geq\theta$
(strict light part) for all
$\mathbf{t}\in\pi_{\mathcal{S}}L:\;|\sigma_{\mathcal{S}=\mathbf{t}}L|<\theta$
The relations $H$ and $L$ are the heavy and light parts of $R$.

Assuming $|R|=N$ and the strict partition $(H,L)$ of $R$ on $\mathcal{S}$ with
threshold $\theta=N^{\epsilon}$ for $\epsilon\in[0,1]$, we have:
$\forall\mathbf{t}\in\pi_{\mathcal{S}}L:|\sigma_{\mathcal{S}=\mathbf{t}}L|<\theta=N^{\epsilon}$;
and $|\pi_{\mathcal{S}}H|\leq\frac{|R|}{\theta}=N^{1-\epsilon}$. We
subsequently denote the light part of $R$ on $\mathcal{S}$ by
$R^{\mathcal{S}}$.

##### Queries.

A conjunctive query (CQ) has the form

$Q(\mathcal{F})=R_{1}(\mathcal{X}_{1}),\ldots,R_{n}(\mathcal{X}_{n}).$

We denote by: $(R_{i})_{i\in[n]}$ the relation symbols;
$(R_{i}(\mathcal{X}_{i}))_{i\in[n]}$ the atoms;
$\mathit{vars}(Q)=\bigcup_{i\in[n]}\mathcal{X}_{i}$ the set of variables;
$\mathit{free}(Q)=\mathcal{F}$ the set of free variables;
$\mathit{bound}(Q)=\mathit{vars}(Q)-\mathit{free}(Q)$ the set of bound
variables; $\mathit{atoms}(Q)=\\{R_{i}(\mathcal{X}_{i})\mid i\in[n]\\}$ the
set of the atoms; and $\mathit{atoms}(X)$ the set of the atoms containing $X$.
The query $Q$ is full if $\mathit{free}(Q)=\mathit{vars}(Q)$.

The hypergraph $G=(\mathit{vars}(Q),\mathit{atoms}(Q))$ of a query $Q$ has one
node per variable and one hyperedge per atom that covers all nodes
representing its variables. The query is $\alpha$-acyclic if for every cycle
in $G$, the nodes in the cycle are covered by a hyperedge. In this case, it
admits a join tree where each node is an atom and if any two nodes have
variables in common, then all nodes along the path between them also have
these variables. A query is free-connex if it is $\alpha$-acyclic and there is
a join tree over its atoms of including its head atom [14]. It is hierarchical
if for any two of its variables, either their sets of atoms are disjoint or
one is contained in the other. It is q-hierarchical if it is hierarchical and
for every variable $A\in\mathit{free}(Q)$, if there is a variable $B$ such
that $\mathit{atoms}(A)\subset\mathit{atoms}(B)$ then $B\in\mathit{free}(Q)$
[10].

######  Example 12.

The following query is $\alpha$-acyclic:

$Q(A,C,F)=R(A,B,C),S(A,B,D),T(A,E,F),U(A,E,G)$

A join tree is the path $U(AEG)-T(AEF)-R(ABC)-S(ABD)$. It is free-connex since
we can extend this join tree as follows: $U(AEG)-T(AEF)-Q(ACF)-R(ABC)-S(ABD)$.
It is also hierarchical but not q-hierarchical: The bound variables $B$ and
$E$ dominate the free variables $C$ and respectively $F$. ∎

##### Variable Orders.

A variable depends on another variable if they occur in the same atom of the
query.

######  Definition 13 (adapted from [45]).

A variable order $\omega$ for a conjunctive query $Q$ is a pair
$(T,\textit{dep}_{\omega})$ such that the following holds:

  * •

$T$ is a forest with one node per variable or atom in $Q$. The variables of
each atom in $Q$ lie along the same root-to-leaf path in $T$. Each atom is a
child of its lowest variable.

  * •

The function $\textit{dep}_{\omega}$ maps each variable $X$ to the subset of
its ancestor variables in $T$ on which the variables in the subtree rooted at
$X$ depend, i.e., for every variable $Y$ that is a child of variable $X$,
$\textit{dep}_{\omega}(Y)\subseteq\textit{dep}_{\omega}(X)\cup\\{X\\}$.

Given a variable order $\omega$, the subtree of $\omega$ rooted at $X$ is
denoted by $\omega_{X}$. The sets $\mathit{vars}(\omega)$,
$\mathit{atoms}(\omega)$, and $\mathsf{anc}(X)$ consist of all variables of
$\omega$, the atoms at the leaves of $\omega$, and the variables on the path
from $X$ to the root excluding $X$, respectively. The flag
$\textsf{has\\_sibling}(X)$ is true if $X$ has siblings. The variable order
$\omega$ is free-top if no bound variable is an ancestor of a free variable
(called d-tree extension [45]). It is canonical if the variables of the leaf
atom of each root-to-leaf path are the inner nodes of the path. The sets
$\mathsf{freeTopVO}(Q)$, $\mathsf{canonVO}(Q)$, and $\mathsf{VO}(Q)$ consist
of free-top, canonical, and all variable orders of $Q$.

######  Example 14.

The query from Example 12 admits the canonical variable order
$A-\\{B-\\{C-R(ABC);D-S(ABD)\\};E$ $-\\{F-T(AEF);G-U(AEG)\\}\\}$. This
variable order is not free-top since the bound variables $B$ and $E$ sit on
top of the free variables $C$ and respectively $F$. A free-top order is:
$A-\\{C-\\{B-\\{R(ABC);D-S(ABD)\\}\\};F-\\{E-\\{T(AEF);G-U(AEG)\\}\\}\\}$.
This variable order is not canonical: the atom at the leaf of the path $A-C-B-
D-S(ABD)$ does not have the variable $C$.∎

Hierarchical queries admit canonical variable orders, while q-hierarchical
queries admit canonical free-top variable orders. The canonical variable order
of a hierarchical query is unique up to orderings of variables sharing the
same set of atoms.

##### Width Measures.

Given a conjunctive query $Q$ and $\mathcal{F}\subseteq\mathit{vars}(Q)$, a
fractional edge cover of $\mathcal{F}$ is a solution
$\boldsymbol{\lambda}=(\lambda_{R(\mathcal{X})})_{R(\mathcal{X})\in\mathit{atoms}(Q)}$
to the following linear program [5]:

minimize
$\displaystyle\makebox[10.76385pt][r]{}\sum_{R(\mathcal{X})\in\,\mathit{atoms}(Q)}\lambda_{R(\mathcal{X})}$
subject to
$\displaystyle\makebox[10.76385pt][r]{}\sum_{R(\mathcal{X}):\,X\in\mathcal{X}}\lambda_{R(\mathcal{X})}\geq
1$ $\displaystyle\text{ for all }X\in\mathcal{F}\text{ and }$
$\displaystyle\makebox[10.76385pt][r]{}\lambda_{R(\mathcal{X})}\in[0,1]$
$\displaystyle\text{ for all }R(\mathcal{X})\in\mathit{atoms}(Q)$

The optimal objective value of the above program is called the fractional edge
cover number of the variable set $\mathcal{F}$ and is denoted as
$\rho_{Q}^{\ast}(\mathcal{F})$. An integral edge cover of $\mathcal{F}$ is a
feasible solution to the variant of the above program with
$\lambda_{R(\mathcal{X})}\in\\{0,1\\}$ for each
$R(\mathcal{X})\in\mathit{atoms}(Q)$. The optimal objective value of this
program is called the integral edge cover number of $\mathcal{F}$ and is
denoted as $\rho_{Q}(\mathcal{F})$. If $Q$ is clear from the context, we omit
the index $Q$ in the expressions $\rho_{Q}^{\ast}(\mathcal{F})$ and
$\rho_{Q}(\mathcal{F})$. For a database of size $N$, the result of the query
$Q$ can be computed in time $\mathcal{O}(N^{\rho^{*}})$ [39].

######  Definition 15.

The static width of a conjunctive query $Q$ is

$\displaystyle\mathsf{w}(Q)$
$\displaystyle=\min_{\omega\in\mathsf{freeTopVO}(Q)}\mathsf{w}(\omega)$
$\displaystyle\mathsf{w}(\omega)$
$\displaystyle=\max_{X\in\mathit{vars}(Q)}\rho^{*}(\\{X\\}\cup\textit{dep}_{\omega}(X))$

If $Q$ is Boolean, then $\mathsf{w}$ is the fractional hypertree width [38].
FAQ-width generalizes $\mathsf{w}$ to queries over several semirings [1] 111To
simplify presentation, we focus on queries that contain at least one atom with
non-empty schema. This implies that the static width of queries is at least
$1$. Queries where all atoms have empty schemas obviously admit constant
preprocessing time, update time, and enumeration delay..

######  Definition 16.

The dynamic width of a conjunctive query $Q$ is

$\displaystyle\delta(Q)$
$\displaystyle=\min_{\omega\in\mathsf{freeTopVO}(Q)}\delta(\omega)$
$\displaystyle\delta(\omega)$ $\displaystyle=\max_{X\in\mathit{vars}(Q)}\
\max_{R(\mathcal{Y})\in\mathit{atoms}(\omega_{X})}\rho^{*}((\\{X\\}\cup\textit{dep}_{\omega}(X))-\mathcal{Y})$

While the static width of a free-top variable order $\omega$ is defined over
the variable sets $\\{X\\}\cup\textit{dep}_{\omega}(X)$ with
$X\in\mathit{vars}(Q)$, the dynamic width of $\omega$ is defined over
restrictions of these sets obtained by dropping the variables in the schema of
one atom. For any canonical variable order $\omega$, variable $X$ in $\omega$,
and atom $R(\mathcal{Y})$ in $\mathit{atoms}(\omega_{X})$, the set
$(\\{X\\}\cup\textit{dep}_{\omega}(X))-\mathcal{Y}$ is empty. Hence, queries
that admit canonical free-top variable orders have dynamic width $0$.

######  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$.

##  4 Preprocessing

In the preprocessing stage, we construct a data structure that represents the
result of a given hierarchical query. The data structure consists of a set of
materialized view trees, with each view tree computing a part of the query
result. This construction exploits the structure of the query and the degree
of data values in base relations. We construct different sets of view trees
for the static and dynamic evaluation of a given hierarchical query.

We next assume that the canonical variable order of the given hierarchical
query consists of a single connected component. For several connected
components, the preprocessing procedure is executed on each connected
component separately.

###  4.1 View Trees Encoding the Query Result

Given a hierarchical query $Q(\mathcal{F})$ and a canonical variable order
$\omega$ for $Q$, the function BuildVT in Figure 6 constructs a view tree that
encodes the query result. The function proceeds recursively on the structure
of $\omega$ and constructs a view $V_{X}(\mathcal{F}_{X})$ at each inner node
$X$; the leaves correspond to the atoms in the query. The view is defined over
the join of its child views (Figure 7). Its schema $\mathcal{F}_{X}$ includes
the ancestors of $X$ in $\omega$ since they are needed for joins at nodes
above $X$.

If $X$ is free, then it is included in the schema of the view constructed at
$X$ (and not included if bound). It is also kept in the schemas of the views
on the path to the root until it reaches a view whose schema does not have
bound variables.

In the dynamic case, at each variable $Z$ child of $X$ we construct a view
with schema $\mathsf{anc}(Z)$ on top of the view created at $Z$ (Figure 8).
This auxiliary view aggregates away $Z$ from the latter view. The children of
the view created at $X$ then share the same schema $\mathcal{F}_{X}$. This
property enables the efficient maintenance of the view at $X$ since processing
a change coming from any child view requires only constant-time lookups into
that child’s sibling views.

Our preprocessing is particularly efficient for free-connex hierarchical
queries in the static case and for their strict subclass of
$\delta_{0}$-hierarchical queries in the dynamic case.

BuildVT(symbol $V$, variable order $\omega$, free variables $\mathcal{F}$) :
view tree
---
switch $\omega$:
| $R(\mathcal{Y})$ |  1return $R(\mathcal{Y})$
|  $X$$\omega_{1}$$\ldots$$\omega_{k}$ |  2let $T_{i}=\textsc{BuildVT}(V,\omega_{i},\mathcal{F}),\forall i\in[k]$ 3if $(\mathsf{anc}(X)\cup\\{X\\})\subseteq\mathcal{F}$ 4let $\mathcal{F}_{X}=\mathsf{anc}(X)\cup\\{X\\}$ 5let $subtrees=\\{\,\textsc{AuxView}(\text{root of }\omega_{i},T_{i})\,\\}_{i\in[k]}$ 6return $\textsc{NewVT}(V_{X},\mathcal{F}_{X},subtrees)$ 7let $\mathcal{F}_{X}=\mathsf{anc}(X)\cup(\mathcal{F}\cap\mathit{vars}(\omega))$ 8let $subtrees=\\{T_{i}\\}_{i\in[k]}$ 9return $\textsc{NewVT}(V_{X},\mathcal{F}_{X},subtrees)$
Figure 6: Construction of a view tree for a canonical variable order $\omega$
of a hierarchical query with free variables $\mathcal{F}$. $V$ is used to
prefix view names. NewVT(symbol $V$, schema $\mathcal{S}$, view trees
$T_{1},\ldots,T_{k}$) : view tree
---
1let $V_{i}(\mathcal{S}_{i})$ = root of $T_{i},\forall i\in[k]$
2let $V(\mathcal{S})=V_{1}(\mathcal{S}_{1}),\ldots,V_{k}(\mathcal{S}_{k})$
3return $\left\\{\begin{array}[]{@{~~}c@{~~}l@{~~}}{}~{}\lx@intercol\hfil
T_{1}\hfil~{}~{}&\text{,\;
$k=1\land\mathcal{S}=\mathcal{S}_{1}$}\hfil~{}~{}\\\
<EMAIL_ADDRESS>\leavevmode\hbox to45.3pt{\vbox
to37.51pt{\pgfpicture\makeatletter\hbox{\hskip
22.57571pt\lower-57.62534pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-10.69446pt}{-30.95276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$V(\mathcal{S})$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-19.2427pt}{-52.30676pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$T_{1}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{ {}{}{}}{}{
{}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-8.99211pt}{-41.94044pt}\pgfsys@lineto{-5.68845pt}{-36.98576pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.75pt}{-52.29233pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ldots$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{9.06422pt}{-52.23677pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$T_{k}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{ {}{}{}}{}{
{}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}\pgfsys@moveto{8.94547pt}{-41.87045pt}\pgfsys@lineto{5.68845pt}{-36.98576pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\hfil~{}~{}&\text{,\;
otherwise}\hfil~{}~{}\end{array}\right.$
Figure 7: Construction of a view tree with root symbol $V$, root schema
$\mathcal{S}$, and children $T_{1},\ldots,T_{k}$. AuxView(node $Z$, view tree
$T$) : view tree
---
1let $V(\mathcal{S})=\text{ root of }T$
2if
$mode=\text{`dynamic'}\land\textsf{has\\_sibling}(Z)\land\mathsf{anc}(Z)\subset\mathcal{S}$
3return $\textsc{NewVT}(V^{\prime},\mathsf{anc}(Z),\\{T\\})$
4return $T$
Figure 8: A tree $T$ constructed at variable $Z$ is extended with a new root
view that aggregates away $Z$.

For a canonical variable order of a hierarchical query, the free-connex
property fails if there are free variables such that they are below a bound
join variable and are not covered by one atom. Indeed, assume two branches out
of a bound join variable $X$ and with free variables $Y$ and respectively $Z$.
Then, there are two atoms in $Q$ whose sets of variables include $\\{X,Y\\}$
and respectively $\\{X,Z\\}$, while $\\{Y,Z\\}$ are included in the head atom
of $Q$. This creates a cycle in the hypergraph of $Q$, which means that $Q$ is
not free-connex.

For $\delta_{0}$-hierarchical queries, there is no bound variable whose set of
atoms strictly contains the atoms of a free variable. Such queries thus admit
canonical free-top variable orders where all free variables occur above the
bound ones.

For any free-connex hierarchical query, each view created by BuildVT is
defined over variables from one atom of the query and can be materialized in
linear time. We can thus recover the linear-time preprocessing for such
queries used for static [8] and dynamic [10, 25] evaluation.

######  Example 18.

Consider the free-connex query

$Q(A,D,E)=R(A,B,C),S(A,B,D),T(A,E)$

and its canonical variable order in Figure 9. We construct the view tree
bottom-up as follows. At $C$, we create the view $V_{C}(A,B)$ that aggregates
away the bound variable $C$ but keeps its ancestors $A$ and $B$ to define
views up in the tree. At $D$, we do not aggregate it away since it is free.
The view at $D$ would be the same as $S(A,B,D)$, so we do not create it;
similarly, no view is created at $E$. At $B$, we create the view
$V_{B}(A,D)=V_{C}(A,B),S(A,B,D)$, which keeps $D$ as it is free and $A$ as the
ancestor of $B$. At $A$, we create the views $V_{A}(A)=V_{B}(A,D),T(A,E)$ in
the static case and $V_{A}(A)=V^{\prime}_{B}(A),T^{\prime}(A)$ in the dynamic
case, where $V^{\prime}_{B}(A)=V_{B}(A,D)$ and $T^{\prime}(A)=T(A,E)$. Each
view can be computed in linear time by aggregating away variables and semi-
join reduction. The result of $Q$ can be enumerated using $V_{A}(A)$,
$V_{B}(A,D)$, and $T(A,E)$ with constant delay.∎

$\underline{A}$$B$$\underline{E}$$T(\underline{A},\underline{E})$$C$$\underline{D}$$S(\underline{A},B,\underline{D})$$R(\underline{A},B,C)$

$V_{A}(\underline{A})$$V^{\prime}_{B}(\underline{A})$$V_{B}(\underline{A},\underline{D})$$T^{\prime}(\underline{A})$$T(\underline{A},\underline{E})$$V_{C}(\underline{A},B)$$S(\underline{A},B,\underline{D})$$R(\underline{A},B,C)$

Figure 9: Canonical variable order and view tree for
$Q(A,D,E)=R(A,B,C),S(A,B,D),T(A,E)$ in Example 18. The views $V^{\prime}_{B}$
and $T^{\prime}$ are created in the dynamic case.

###  4.2 Skew-Aware View Trees

For free-connex queries, the procedure BuildVT constructs in linear time a
data structure (Lemma 43) that allows for constant-time enumeration delay
(Proposition 22). For $\delta_{0}$-hierarchical queries, it also allows for
constant-time updates (Lemma 47).

We now focus on the bound join variables that violate the free-connex property
in the static case or the $\delta_{0}$-hierarchical property in the dynamic
case. For each such violating bound variable $X$, we use two evaluation
strategies.

The first strategy materializes a subset of the query result obtained for the
light values over the set of variables $\mathsf{anc}(X)\cup\\{X\\}$ in the
variable order. It also aggregates away the bound variables in the subtree
rooted at $X$. Since the light values have a bounded degree, this
materialization is inexpensive.

The second strategy computes a compact representation of the rest of the query
result obtained for those values over $\mathsf{anc}(X)\cup\\{X\\}$ that are
heavy (i.e., have high degree) in at least one relation. This second strategy
treats $X$ as a free variable and proceeds recursively to resolve further
bound variables located below $X$ in the variable order and to potentially
fork into more strategies.

The union of these strategies precisely cover the entire query result, yet not
necessarily disjointly. To enumerate the distinct tuples in the query result,
we then use an adaptation of the union algorithm where the delay is given by
the number of heavy values of the variables we partitioned on and by the
number of strategies. Example 28 showcases this approach for a non-free-connex
query.

##### Heavy and Light Indicators.

We compute heavy and light indicator views consisting of disjoint sets of
values for each violating variable $X$. The heavy indicator has the values
that exist in all relations and are heavy in at least one relation. The light
indicator has the values that exist in all relations and are light in all
relations. Indicator views have set semantics. They allow us to rewrite the
query into an equivalent union of two queries.

Partitioning the query result only based on the degree of $X$-values may blow
up the enumeration delay: the path from $X$ to the root may contain several
bound join variables, each creating buckets of values per bucket of their
ancestors, thus leading to an explosion of the number of buckets that need to
be unioned together during enumeration. However, one remarkable property holds
for hierarchical queries: each base relation located in the subtree rooted at
$X$ contains $X$ but also all the ancestors of $X$. Thus, by partitioning each
relation jointly on $X$ and its ancestors, we can ensure the enumeration delay
remains linear in the number of distinct heavy values over
$\mathsf{anc}(X)\cup\\{X\\}$.

IndicatorVTs(variable order $\omega$) : triple of view trees
---
1let $X=\text{root of }\omega$
2let $keys=\mathsf{anc}(X)\cup\\{X\\}$
3let $alltree=\textsc{BuildVT}(All,\omega,keys)$
4let $ltree=\textsc{BuildVT}(L,\omega^{keys},keys)$
5let $allroot=\text{root of }alltree$
6let $lroot=\text{root of }ltree$
7let $htree=\textsc{NewVT}(H_{X},keys,\\{allroot,\nexists{lroot}\\})$
8return $(alltree,ltree,htree)$
Figure 10: Construction of the heavy and light indicator view trees for a
canonical variable order $\omega$ of a hierarchical query. The variable order
$\omega^{keys}$ has the structure of $\omega$ but each atom $R(\mathcal{Y})$
is replaced with the light part $R^{keys}(\mathcal{Y})$ of relation $R$
partitioned on $keys$.

Figure 10 shows how to construct a triple of view trees for computing the
indicators for $\mathsf{anc}(X)\cup\\{X\\}$, where $X$ is the root of a
variable order $\omega$ that is a subtree in the variable order of a
hierarchical query (thus $\mathsf{anc}(X)$ may be non-empty). We first
construct a view tree that computes the tuples of values for variables
$keys=\mathsf{anc}(X)\cup\\{X\\}$ over the join of the relations from
$\omega$. We then build a similar view tree for the light indicator for $keys$
using a modified variable order $\omega^{keys}$ of the same structure as
$\omega$ but with each relation $R$ replaced by the light part of $R$
partitioned on $keys$. Finally, the view tree for the heavy indicator computes
the difference of all $keys$-values and those from the light indicator.

Appendix A shows the indicators for the queries $Q(A,C)$ $=R(A,B),S(B,C)$ and
$Q(A)=R(A,B),S(B)$.

$\tau(\text{variable order }\omega,\text{free variables }\mathcal{F})$ : set
of view trees
---
switch $\omega$:
| $R(\mathcal{Y})$ |  1 return $\\{R(\mathcal{Y})\\}$
|  $X$$\omega_{1}$$\ldots$$\omega_{k}$ |  2 let $keys=\mathsf{anc}(X)\cup\\{X\\}$ 3 let $\mathcal{F}_{X}=\mathsf{anc}(X)\cup(\mathcal{F}\cap\mathit{vars}(\omega))$ 4 let $Q_{X}(\mathcal{F}_{X})=\text{join of }\mathit{atoms}(\omega)$ 5 if $(mode=\text{`static'}\land Q_{X}(\mathcal{F}_{X})\text{ is free-connex})\,\lor$ 6 $(mode=\text{`dynamic'}\land Q_{X}(\mathcal{F}_{X})\text{ is $\delta_{0}$-hierarchical})$ 7 return $\\{\,\textsc{BuildVT}(V,\omega,\mathcal{F}_{X})\,\\}$ 8 if $X\in\mathcal{F}$ 9 return $\\{\,\textsc{NewVT}(V_{X},keys,\\{\hat{T}_{1},{.}{.}{.},\hat{T}_{k}\\})$ 10 $\mid T_{i}\in\tau(\omega_{i},\mathcal{F})_{i\in[k]},$ 11 $\hat{T}_{i}=\textsc{AuxView}(\text{root of }\omega_{i},T_{i})_{i\in[k]}\\}$ 12 let $(\\_,\\_,H_{X})=\text{roots of }\textsc{IndicatorVTs}(\omega)$ 13 let $htrees=\\{\,\textsc{NewVT}(V_{X},keys,\\{\exists H_{X},\hat{T}_{1},{.}{.}{.},\hat{T}_{k}\\})$ 14 $\mid T_{i}\in\tau(\omega_{i},\mathcal{F})_{i\in[k]},$ 15 $\hat{T}_{i}=\textsc{AuxView}(\text{root of }\omega_{i},T_{i})_{i\in[k]}\\}$ 16 let $ltree=\textsc{BuildVT}(V,\omega^{keys},\mathcal{F}_{X})$ 17 return $htrees\cup\\{\,ltree\,\\}$
Figure 11: Construction of skew-aware view trees for a canonical variable
order $\omega$ of a hierarchical query with free variables $\mathcal{F}$. The
global parameter $mode\in\\{\text{`static'},\text{`dynamic'}\\}$ specifies the
evaluation mode. The variable order $\omega^{keys}$ has the structure of
$\omega$ but each atom $R(\mathcal{Y})$ is replaced by the light part
$R^{\hskip 0.56905ptkeys}(\mathcal{Y})$ of relation $R$ partitioned on $keys$.

$A$$B$$\underline{C}$$\underline{D}$$\underline{E}$$\underline{F}$$G$$R(A,B,\underline{D})$$S(A,B,\underline{E})$$T(A,\underline{C},\underline{F})$$U(A,\underline{C},G)$

$V_{A}({\underline{C},\underline{D},\underline{E},\underline{F}})$$V_{B}(A,\underline{D},\underline{E})$$V_{C}(A,\underline{C},\underline{F})$$V_{G}(A,\underline{C})$$R^{A}(A,B,\underline{D})$$S^{A}(A,B,\underline{E})$$T^{A}(A,\underline{C},\underline{F})$$U^{A}(A,\underline{C},G)$

$V_{A}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}A})$$\exists
H_{A}({A})$$V^{\prime}_{B}({A})$$V_{B}({A,\underline{D},\underline{E}})$$R^{AB}(A,B,\underline{D})$$S^{AB}(A,B,\underline{E})$$V^{\prime}_{C}({A})$$V_{C}({A,\underline{C}})$$T^{\prime}(A,\underline{C})$$V_{G}(A,\underline{C})$$T(A,\underline{C},\underline{F})$$U(A,\underline{C},G)$

$V_{A}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}A})$$\exists
H_{A}({A})$$V^{\prime}_{B}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}A})$$V_{B}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}A,B})$$\exists
H_{B}({A,B})$$R^{\prime}({A,B})$$R(A,B,\underline{D})$$S^{\prime}({A,B})$$S(A,B,\underline{E})$$V^{\prime}_{C}({A})$$V_{C}({A,\underline{C}})$$T^{\prime}(A,\underline{C})$$V_{G}(A,\underline{C})$$T(A,\underline{C},\underline{F})$$U(A,\underline{C},G)$

$All_{A}({A})$$All_{B}({A})$$All_{C}({A})$$All_{D}({A,B})$$All_{E}({A,B})$$All_{F}({A,\underline{C}})$$All_{G}({A,\underline{C}})$$R(A,B,\underline{D})$$S(A,B,\underline{E})$$T(A,\underline{C},\underline{F})$$U(A,\underline{C},G)$

$L_{A}({A})$$L_{B}({A})$$L_{C}({A})$$L_{D}({A,B})$$L_{E}({A,B})$$L_{F}({A,\underline{C}})$$L_{G}({A,\underline{C}})$$R^{A}(A,B,\underline{D})$$S^{A}(A,B,\underline{E})$$T^{A}(A,\underline{C},\underline{F})$$U^{A}(A,\underline{C},G)$

$H_{A}({A})$$All_{A}({A})$$\nexists L_{A}({A})$

$All_{B}({A,B})$$All_{D}({A,B})$$All_{E}({A,B})$$R(A,B,\underline{D})$$S(A,B,\underline{E})$

$L_{B}({A,B})$$L_{D}({A,B})$$L_{E}({A,B})$$R^{{AB}}(A,B,\underline{D})$$S^{{AB}}(A,B,\underline{E})$

$H_{B}({A,B})$$All_{B}({A,B})$$\nexists L_{B}({A,B})$

Figure 12:  Canonical variable order for the query
$Q(C,D,E,F)\allowbreak=\allowbreak R(A,B,D),\allowbreak S(A,B,E),\allowbreak
T(A,C,F),\allowbreak U(A,C,G)$ (top left). The three view trees constructed
for the query (top right and second row). The indicator view trees for
computing $H_{A}$ and $H_{B}$ (third and fourth row). The views with a dashed
box are only needed for dynamic query evaluation.

##### View Trees with Indicators.

Figure 11 gives the algorithm for constructing the view trees for a variable
order $\omega$ of a hierarchical query $Q(\mathcal{F})$. The algorithm
traverses the variable order $\omega$ top-down, maintaining the invariant that
all ancestors of a node are free variables (or treated as such in case of
bound join variables whose values are heavy).

The free variables at node $X$ are the ancestors of $X$ and the free variables
in the subtree rooted at $X$ (Line 3). If the residual query $Q_{X}$ at node
$X$ (Line 4) is free-connex in the static case or $\delta_{0}$-hierarchical in
the dynamic case, we return a view tree for $Q_{X}$ (Lines 5-7). If $X$ is
free, we recursively compute a set of view trees for each child of $X$. We may
extend the root of each child tree with an auxiliary view in the dynamic mode
to support constant-time propagation of updates coming via the siblings of
$X$. For each combination of the child view trees, we form a new view joining
the roots of the child view trees and using $X$ and its ancestors as free
variables (Lines 8-11). If $X$ is bound, we create two evaluation strategies
for the residual query $Q_{X}$ based on the degree of values of $X$ and its
ancestors in the relations of $Q_{X}$. We construct the indicator view trees
for $X$ and its ancestors (Line 12). The heavy indicator restricts the joins
of the child views to only heavy values for the tuple of $X$ and its ancestors
(Lines 13-15). We also construct a view tree over the light parts of the
relations in $\omega$ (Line 16).

######  Example 19.

Figure 12 shows the view trees for the query

$Q(C,D,E,F)=R(A,B,D),\,S(A,B,E),\,T(A,C,F),\,U(A,C,G).$

We start from the root $A$ in the variable order. Since $Q$ is not free-connex
(and also not $\delta_{0}$-hierarchical) and $A$ is bound, we create the view
trees for the indicators $H_{A}(A)$ and $L_{A}(A)$. Materializing the views in
these view trees takes linear time.

In the light case for $A$, we create a view tree with the root
$V_{A}(C,D,E,F)$ and the leaves being the light parts of the input relations
partitioned on $A$ (bottom-left). Computing $V_{G}(A,C)$ and $V_{C}(A,C,F)$
takes linear time. We compute the view $V_{B}(A,D,E)$ in time
$\mathcal{O}(N^{1+\epsilon})$: For each $(a,b,d)$ tuple in $R^{A}$, we iterate
over at most $N^{\epsilon}$ $(a,b,e)$ values in $S^{A}$. The view
$V_{B}(A,D,E)$ contains at most $N^{1+\epsilon}$ tuples. Similarly, we compute
$V_{A}(C,D,E,F)$ in time $\mathcal{O}(N^{1+2\epsilon})$: For each $(a,d,e)$
tuple in $V_{B}$, we iterate over at most $N^{\epsilon}$ $(a,c,f)$ values in
$V_{C}$. The view $V_{A}(C,D,E,F)$ allows constant delay enumeration of its
result.

In the heavy case for $A$, we recursively process the subtrees of $A$ in
$\omega$ and treat $A$ as free. The right subquery,
$Q_{C}(A,C,F)=T(A,C,F),U(A,C,G)$ is free-connex and $\delta_{0}$-hierarchical,
thus we compute its view tree with the root $V_{C}(A,C)$ in the static case
and the root $V^{\prime}_{C}(A)$ in the dynamic case (view trees in the second
row) in linear time. The left subquery $Q_{B}(A,D,E)=R(A,B,D),S(A,B,E)$,
however, is neither free-connex nor $\delta_{0}$-hierarchical. Since $B$ is
bound, we create the indicator relations $H_{B}(A,B)$ and $L_{B}(A,B)$ in
linear time. We distinguish two new cases: In the light case for $(A,B)$, we
construct a view tree with the root $V_{B}(A,D,E)$
$=R^{AB}(A,B,D),S^{AB}(A,B,E)$ (second row left) and compute $V_{B}(A,D,E)$ in
time $\mathcal{O}(N^{1+\epsilon})$ by iterating over $R^{AB}$ and, for each
$(a,b,d)$, iterating over at most $N^{\epsilon}$ $E$-values in $S^{AB}$. In
the heavy case for $(A,B)$, we process the subtrees of $B$ considering $B$ as
free variable. The two subqueries, $Q_{D}(A,B,D)=R(A,B,D)$ and
$Q_{E}(A,B,E)=S(A,B,E)$, are $\delta_{0}$-hierarchical.

Overall, we create three view trees for $Q$ and two sets of view trees for the
indicator relations at $A$ and $B$. The time needed to compute these view
trees is $\mathcal{O}(N^{1+2\epsilon})$. ∎

Given a hierarchical query, our algorithm effectively rewrites it into an
equivalent union of queries, with one query defined by the join of the leaves
of a view tree.

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

The preprocessing time of our approach is given by the time to materialize the
views in the view trees.

######  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.

##  5 Enumeration

For any hierarchical query, Section 4 constructs a set of view trees that
together represent the query result. We now show how to enumerate the distinct
tuples in the query result with their multiplicity using the $open/next/close$
iterator model for such view trees.

Given a subtree $T$ of a view tree and the current tuple $ctx$ in its parent
view, the call $\mathit{T.open(ctx})$ described in Figure 13 sets the range of
the iterator of $T$ to those tuples in its root view that agree with
$\mathit{ctx}$ and positions the iterator at the first tuple in this range.
The $open$ call is recursively propagated down the view tree with an
increasingly more specific context tuple.

There are two cases that need special attention. If the schema of a view $V$
includes all free variables in the subtree rooted at $V$, then there is no
need to open the views in this subtree since $V$ already has the tuples over
these free variables; e.g., this is the case of the view $V_{A}(C,D,E,F)$ in
Figure 12. The views with heavy indicators, e.g., the views $V_{A}(A)$ and
$V_{B}(A,B)$ in Figure 12, also require special treatment. If $V$ has as child
a heavy indicator $\exists H$, the tree $T$ rooted at $V$ represents possibly
overlapping relations in the contexts given by the different tuples
$h\in\exists H$. We ground the heavy indicator by creating an iterator for
each heavy tuple agreeing with the current tuple $\mathit{ctx}$ at the parent
view of $V$ and keep this iterator in a shallow copy of $T$ (i.e., the content
of views under $T$ is not copied).

The time for the $open$ calls is dominated by grounding. Since the overall
size of a heavy indicator is $\mathcal{O}(N^{1-\epsilon})$, it takes
$\mathcal{O}(N^{1-\epsilon})$ time to execute all $open$ calls. Seeking a
context tuple in a view is a constant-time lookup. A $T.close()$ call resets
the iterators of tree $T$.

$T.\mathit{open}(\text{tuple }\mathit{ctx})$
---
1let $V(\mathcal{S})=$ root of $T$
2$V.\mathit{open}(\mathit{ctx})$
3$T.\mathit{tuple}:=V.\mathit{next}()$
4if $(T\mbox{ has no children})\lor(\mathcal{S}=\mbox{free variables in }T)$
return
5let $\\{T_{1},\ldots,T_{k}\\}=$ children of $T$
6if $\exists i\in[k]\text{ such that }T_{i}=\exists H$
7$\exists H.\mathit{open}(\mathit{ctx})$
8foreach $\mathit{h}\in\exists H$ do
9$T^{(\mathit{h})}:=$ shallow copy of $T$ without $\exists H$
10$T^{(\mathit{h})}.open(\mathit{h})$
11$T.\mathit{buckets}:=\\{T^{(\mathit{h})}\\}_{\,\mathit{h}\in\exists H}$
12else
13foreach $i\in[k]$ do $T_{i}.\mathit{open}(T.\mathit{tuple})$
Figure 13: Open the view iterators in a view tree.

After the first $open$ call for a view tree $T$, we can enumerate the distinct
tuples from $T$ with their multiplicity by calling $T.next()$, see Figure 14.
The $next$ call propagates recursively down $T$ and observes the same cases as
the $open$ call. If a view $V$ in $T$ already covers all free variables in
$T$, then it suffices to enumerate from $V$. If $T$ has as child a heavy
indicator, we return the next tuple and its multiplicity from the union of all
its groundings using the Union algorithm from Figure 15. Otherwise, we
synthesize the returning tuple out of the tuples at the iterators of $T$’s
children. In the context given by the current tuple at $T$’s view, we return
the next tuple and its multiplicity from the Cartesian product of the tuples
produced by $T$’s children using the Product algorithm from Figure 16.

The time to produce the next tuple from a view tree is dominated by the Union
algorithm, whose delay is given by the sum of the delays of its input view
trees. View iterators need constant delay, same for trees of such views in the
absence of the grounding of heavy indicators. Since the total size of the
heavy indicators in a view tree is $\mathcal{O}(N^{1-\epsilon})$, the total
time taken by a next call is $\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 again use the Union algorithm. In case the query has
several connected components, i.e., it is a Cartesian product of hierarchical
queries, we use the Product algorithm with an empty context.

The multiplicity for a tuple returned by the Union algorithm is the sum of the
multiplicities of its occurrences across the buckets, while for a tuple
returned by the Product algorithm it is the multiplication of the
multiplicities of the constituent tuples. Since all tuples in the database
have positive multiplicities, the derived multiplicities are always strictly
positive and therefore the returned tuple is part of the result.

$T.\mathit{next}(\,):\text{tuple}$
---
1let $V(\mathcal{S})=$ root of $T$
2if $(T\mbox{ has no children})\lor(\mathcal{S}=\mbox{free variables in }T)$
3$t:=T.\mathit{tuple};\;T.\mathit{tuple}:=V.\mathit{next}()$; return $t$
4let $\\{T_{1},\ldots,T_{k}\\}=$ children of $T$
5if $T.\mathit{buckets}\neq\emptyset$
6if $(t:=\textsc{Union}(T.\mathit{buckets}))\neq$ EOF
7$T.\mathit{tuple}:=t$; return $t$
8else
9while ($T.\mathit{tuple}\neq$ EOF) do
10if $(t:=\textsc{Product}(T_{1},\ldots,T_{k},T.\mathit{tuple}))\neq$ EOF
11return $t$
12$T.\mathit{tuple}:=V.\mathit{next}()$
13foreach $i\in[k]$ do
$T_{i}.\mathit{close}();\;T_{i}.\mathit{open}(T.\mathit{tuple})$
14return EOF
Figure 14: Find the next tuple in a view tree.

We next state the complexity of enumeration in our approach.

######  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$.

###  5.1 The Union and Product Algorithms

We show the Union and Product algorithms used by the $T.next()$ function in
Figure 14.

Union$(\text{view trees }T_{1},\ldots,T_{n}):$ tuple
---
1if ($n=1$) return $T_{n}.next(\,)$
2if ($(t_{\hskip 0.41998pt[n-1]},m_{\hskip 0.41998pt[n-1]}):=$
Union($T_{1},\ldots,T_{n-1}$)) $\neq$ EOF
3if ($T_{n}.\mathit{lookup}\hskip 0.59998pt(t_{\hskip 0.41998pt[n-1]})\neq 0$)
4$(t_{n},m_{n}):=T_{n}.next(\,)$
5$m_{[n]}=m_{n}+\sum_{i\in[n-1]}T_{i}.\mathit{lookup}\hskip
0.59998pt(\mathbf{x}_{n})$
6return $(t_{n},\mathit{m}_{[n]})$
7return $(t_{\hskip 0.41998pt[n-1]},m_{\hskip 0.41998pt[n-1]})$
8if $((t_{n},m_{n}):=T_{n}.next(\,))\neq$ EOF
9$m_{[n]}=m_{n}+\sum_{i\in[n-1]}T_{i}.\mathit{lookup}\hskip 0.59998pt(t_{n})$
10return $(t_{n},m_{[n]})$
11return EOF
Figure 15: Find the next tuple in a union of view trees.

The Union algorithm is given in Figure 15. It is an adaptation of prior work
[20]. It takes as input $n$ view trees that represent possibly overlapping
sets of tuples over the same relation and returns a tuple and its multiplicity
in the union of these sets, where the tuple is distinct from all tuples
returned before.

We first explain the algorithm on two views $T_{1}$ and $T_{2}$ that have been
already open and with their iterators positioned at the first respective
tuples. On each call, we return one tuple together with its multiplicity or
$\mathbf{EOF}$. We check whether the next tuple $t_{1}$ in $T_{1}$ is also
present in $T_{2}$. If so, we return the next tuple in $T_{2}$ and its total
multiplicity from $T_{1}$ and $T_{2}$; otherwise, we return $t_{1}$ and its
multiplicity in $T_{1}$. In case $T_{1}$ is exhausted, we return the next
tuple in $T_{2}$ and its total multiplicity from $T_{1}$ and $T_{2}$, or
$\mathbf{EOF}$ in case $T_{2}$ is also exhausted.

In case of $n>2$ views, we consider one view defined by the union of the first
$n-1$ views and a second view defined by $T_{n}$, and we then reduce the
general case to the previous case of two views.

The delay of this algorithm is given by the delay of iterating over each view,
the cost of lookups into the views, and the cost of computing output
multiplicities. The lookup costs are constant when using a hierarchy of
materialized views for representing the query result [45]. Given $n$ views,
computing an output multiplicity takes $\mathcal{O}(n)$ time. The overall
delay is the sum of the delays of the $n$ views, which is $\mathcal{O}(n)$.

In our paper, we employ the Union algorithm in two cases: (1) on the set of
view trees obtained after grounding the heavy indicators; and (2) on the set
of view trees obtained by using skew-aware indicators in the preprocessing
stage. In the first case, the number of the view trees is in
$\mathcal{O}(N^{1-\epsilon})$, since the number of heavy tuples in any heavy
indicator view is at most $N^{1-\epsilon}$. In the second case, the number of
view trees does not depend on the database size $N$, but it may depend
exponentially on the number of bound join variables in the input hierarchical
query.

The Product algorithm is given in Figure 16. It takes as input a set of view
trees $T_{1},\ldots,T_{k}$ and a context, which is the current tuple in the
parent view, and outputs the next tuple and its multiplicity in the Cartesian
product of the $k$ views given the context.

In case $k=1$, we execute the innermost loop for $T_{k}$: On a call, we take
the current tuple in $T_{k}$ and project away the variables that are in common
with the context tuple, retaining only the free variables in $T_{k}$. We
concatenate this projection with the context tuple. The concatenation operator
is $\circ$. Before we return this concatenated tuple and its multiplicity, we
advance the iterator to the next tuple-multiplicity pair in $T_{k}$.
Eventually, we reach the end of the iterator for $T_{k}$, in which case we
return $\mathbf{EOF}$.

In case $k>1$, we hold the current tuple-multiplicity pairs for
$T_{1},\ldots,T_{k-1}$ and iterate over $T_{k}$. Whenever $T_{k}$ reaches
$\mathbf{EOF}$, we reset it and advance the iterator for $T_{k-1}$. We
concatenate the context tuple and the current tuples of all iterators,
projected onto the variables that are not in the schema of the context tuple
(since those fields are already in the context). We multiply the current
multiplicities of all iterators and advance the iterator for $T_{k}$ before
returning the concatenated tuple and its multiplicity.

The delay for a Product call is given by the sum of the delays of the $k$
input view trees. We use this algorithm in two cases: (1) enumerating from a
view with several children in a tree (in which case the context is given as
the current tuple in the view); (2) a collection of view trees, one per
connected component of the input query (in which case the context is the empty
tuple). In both cases, the number of parameters to the Product call is
independent of the size of the database and only dependent on the number of
atoms and respectively of connected components in the input query. This means
that the delay (in data complexity) is the maximum delay of any of its
parameter view trees, which is $\mathcal{O}(N^{1-\epsilon})$.

Product$(\text{view trees }T_{1},\ldots,T_{k},\text{tuple }\mathit{ctx}):$
tuple
---
1while ($T_{1}.\mathit{tuple}\neq$ EOF) do
$\ldots$
2while ($T_{k-1}.\mathit{tuple}\neq$ EOF) do
3while ($T_{k}.\mathit{tuple}\neq$ EOF) do
4let $(t_{i},m_{i}):=T_{i}.\mathit{tuple},\forall i\in[k]$
5let $(t_{\mathit{ctx}},\\_):=\mathit{ctx},\text{ where
}t_{\mathit{ctx}}\text{ is over schema }\mathcal{S}$
6$t:=t_{\mathit{ctx}}\circ\bigcirc_{i\in[k]}\pi_{\text{free variables in
}T_{i}-\mathcal{S}\,}t_{i}$
7$m:=\prod_{i\in[k]}m_{i}$
8$T_{k}.next()$
9return $(t,m)$
10$T_{k}.\mathit{close}()$; $T_{k}.\mathit{open}(\mathit{ctx})$;
$T_{k-1}.\mathit{next}()$
$\ldots$
11$T_{2}.\mathit{close}()$; $T_{2}.\mathit{open}(\mathit{ctx})$;
$T_{1}.\mathit{next}()$
12return EOF
Figure 16: Find the next tuple in a product of view trees. In case $k=1$, the
innermost loop is executed.

##  6 Updates

We present our strategy for maintaining the views in the set of view trees
$\tau(\omega,\mathcal{F})$ constructed for a canonical variable order $\omega$
of a hierarchical query $Q(\mathcal{F})$ under updates to input relations. We
specify here the procedure for processing a single-tuple update to any input
relation. Processing a sequence of such updates builds upon this procedure and
occasional rebalancing steps (Section 6.2).

We write $\delta{R}=\\{\mathbf{x}\rightarrow m\\}$ to denote a single-tuple
update $\delta{R}$ mapping the tuple $\mathbf{x}$ to the non-zero multiplicity
$m\in\mathbb{Z}$ and any other tuple to 0; i.e., $|\delta{R}|=1$. Inserts and
deletes are updates represented as relations in which tuples have positive and
negative multiplicities. We assume that after applying an update to the
database, all relations and views contain no tuples with negative
multiplicities.

Compared to static evaluation, our strategy for dynamic evaluation may
construct additional views to support efficient updates to all input
relations. In Figure 12, the view tree created for the case of heavy
$(A,B)$-values (second row right) has five such additional views, marked with
dashed boxes. These views enable an update to any leaf view to be propagated
to the root view in constant time. For instance, the views $R^{\prime}$ and
$S^{\prime}$ eliminate the need to iterate over the $D$-values in relation $R$
for updates to relation $S$ and $\exists{H}_{B}$ and respectively over the
$E$-values in $S$ for updates to $R$ and $\exists{H}_{B}$. Figure 8 gives the
rule for creating such views: If node $Z$ has a sibling in the variable order,
then we create an auxiliary view that aggregates away $Z$ to avoid iterating
over the $Z$-values for updates coming via the (auxiliary) views constructed
for the siblings of $Z$.

Apply(view tree $T$, update $\delta R$) : delta view
---
switch $T$:
| $K(\mathcal{X})$ |  1if $K=R$
|  |  2$R(\mathcal{X})=R(\mathcal{X})+\delta R(\mathcal{X})$
|  |  3return $\delta R$
|  |  4return $\emptyset$
|  $V(\mathcal{X})$$T_{1}$$\ldots$$T_{k}$ |  5let $V_{i}(\mathcal{X}_{i})=\text{root of }T_{i},\text{ for }i\in[k]$ 6if $\exists\,j\in[k]$ such that $R\in T_{j}$ 7$\delta V_{j}=\textsc{Apply}(T_{j},\delta R)$ 8$\delta V(\mathcal{X})=V_{1}(\mathcal{X}_{1}),\,\ldots\,,\delta V_{j}(\mathcal{X}_{j}),\,\ldots\,,V_{k}(\mathcal{X}_{k})$ 9$V(\mathcal{X})=V(\mathcal{X})+\delta V(\mathcal{X})$ 10return $\delta V$ 11return $\emptyset$
Figure 17:  Updating views in a view tree $T$ for a single-tuple update
$\delta R$ to relation $R$.

###  6.1 Processing a Single-Tuple Update

An update $\delta{R}$ to a relation $R$ may affect multiple view trees in the
set of view trees constructed by our algorithm from Figure 11.222We focus here
on updates to hierarchical queries without repeating relation symbols. In case
a relation $R$ occurs several times in a query, we represent an update to $R$
as a sequence of updates to each occurrence of $R$. We apply $\delta{R}$ to
each such view tree in sequence, by propagating changes along the path from
the leaf $R$ to the root of the view tree. For each view on this path, we
update the view result with the change computed using the standard delta rules
[16] (see Example 28). To simplify the reasoning about the maintenance task,
we assume that each view tree has a copy of its base relations. We use
$\textsc{Apply}(T,\delta{R})$ from Figure 17 to propagate an update
$\delta{R}$ in a view tree $T$; if $T$ does not refer to $R$, the procedure
has no effect.

Updates to indicator views, however, may trigger further changes in the views
constructed over them. Consider, for instance, the heavy indicator
$H_{B}(A,B)$ constructed over the view $All_{B}(A,B)$ and the light indicator
$\nexists L_{B}(A,B)$ in Figure 12. An insert $\delta{R}=\\{(a,b,d)\rightarrow
1\\}$ into $R$ may change the multiplicity $H_{B}(a,b)$ from 0 to non-zero,
thus changing $\exists H_{B}(A,B)$ and its dependent views: $V_{B}(A,B)$,
$V^{\prime}_{B}(A)$, and $V_{A}(A)$. But if the multiplicity $H_{B}(a,b)$
stays 0 or non-zero after applying $\delta{R}$, then $\exists H_{B}$ also
stays unchanged.

UpdateIndTree(indicator tree $T_{Ind}$, update $\delta{R}):$ indicator change
---
1let $I(\mathcal{S})=\textsf{root}(T_{Ind})$
2let $\textit{key}=\mathbf{x}[\mathcal{S}],\text{ where
}\delta{R}=\\{\mathbf{x}\rightarrow m\\}$
3let $\textit{\\#before}=I(key)$
4$\textsc{Apply}(T_{Ind},\delta{R})$
5if $(\hskip 0.56905pt\textit{\\#before}=0\hskip 0.56905pt)\hskip
0.56905pt\land\hskip 0.56905pt(\hskip 0.56905ptI(key)>0\hskip 0.56905pt)$
return $\\{key\rightarrow 1\\}$
6if $(\hskip 0.56905pt\textit{\\#before}>0\hskip 0.56905pt)\hskip
0.56905pt\land\hskip 0.56905pt(\hskip 0.56905ptI(key)=0\hskip 0.56905pt)$
return $\\{key\rightarrow-1\\}$
7return $\emptyset$
Figure 18: Updating an indicator view tree $T_{Ind}$ for a single-tuple update
$\delta{R}$ to relation $R$. UpdateTrees(view trees $\mathcal{T}$, indicator
triples $\mathcal{T}_{Ind}$, update $\delta{R}$)
---
1foreach $T\in\mathcal{T}$ do $\textsc{Apply}(T,\delta{R})$
2foreach $(T_{All},T_{L},T_{H})\in\mathcal{T}_{Ind}$ such that $R\in T_{All}$
do
3let
$All(\mathcal{S})=\textsf{root}(T_{All}),\;L(\mathcal{S})=\textsf{root}(T_{L}),\;H(\mathcal{S})=\textsf{root}(T_{H})$
4let $\textit{key}=\mathbf{x}[\mathcal{S}],\text{ where
}\delta{R}=\\{\mathbf{x}\rightarrow m\\}$
5let $\textit{\\#before}=All(key)$
6$\textsc{Apply}(T_{All},\delta{R})$
7let $\textit{\\#change}=All(key)-\textit{\\#before}$
8let
$\delta(\exists{H})=\textsc{UpdateIndTree}(T_{H},\delta{All}=\\{key\rightarrow\textit{\\#change}\,\\})$
9foreach $T\in\mathcal{T}$ do $\textsc{Apply}(T,\delta(\exists{H}))$
10if
$(\textit{key}\notin\pi_{\mathcal{S}}R)\,\lor\,(\textit{key}\in\pi_{\mathcal{S}}R^{\mathcal{S}})$
11foreach $T\in\mathcal{T}$ do
$\textsc{Apply}(T,\delta{R}^{\mathcal{S}}=\delta{R})$
12let $\delta(\exists
L)=\textsc{UpdateIndTree}(T_{L},\delta{R}^{\mathcal{S}}=\delta{R})$
13let
$\delta(\exists{H})=\textsc{UpdateIndTree}(T_{H},\delta(\nexists{L})=-\delta(\exists{L}))$
14foreach $T\in\mathcal{T}$ do $\textsc{Apply}(T,\delta(\exists{H}))$
Figure 19: Updating a set $\mathcal{T}$ of view trees and a set
$\mathcal{T}_{Ind}$ of triples of indicator trees for a single-tuple update
$\delta{R}$ to relation $R$.

Figure 18 shows the function UpdateIndTree that applies an update $\delta{R}$
to an indicator tree $T_{Ind}$ with a root view $I(\mathcal{S})$. The function
returns the change $\delta(\exists{I})$ in the support of the indicator view
$I$, to be further propagated to other views. The free variables $\mathcal{S}$
of $I$ appear in each input relation from $T_{Ind}$, and $\delta{R}$ fixes
their values to constants; thus, $|\delta(\exists{I})|\leq 1$.

Figure 19 gives our algorithm for maintaining a set of view trees
$\mathcal{T}$ and a set of indicator tress $T_{Ind}$ under an update
$\delta{R}$. We first apply $\delta{R}$ to the view trees from $\mathcal{T}$
(Line 1). Then, we consider the triples $(T_{All},T_{L},T_{H})$ of indicator
trees from $\mathcal{T}_{Ind}$ that are affected by $\delta{R}$. We maintain
the heavy indicator tree $T_{H}$ with the root
$H(\mathcal{S})=All(\mathcal{S}),\nexists{L(\mathcal{S})}$ for changes in both
$All$ and $\nexists{L}$. We apply $\delta{R}$ to $T_{All}$ (Line 6) and
subsequently $\delta{All}$ to $T_{H}$ (Line 8). The latter may trigger a
change $\delta(\exists H)$ in the support of $H$, which we apply to the view
trees from $\mathcal{T}$ (Line 9). If the update $\delta{R}$ belongs to the
light part $R^{\mathcal{S}}$ (Line 10), we apply $\delta{R}^{\mathcal{S}}$ to
the view trees from $\mathcal{T}$ and to the light indicator tree $T_{L}$
(Lines 11-12). We then propagate the opposite change $\delta(\nexists{L})$ in
the support of the root $L$ of $T_{L}$, if any, to $T_{H}$ and further to the
view trees from $\mathcal{T}$ (Lines 13-14).

We next state the complexity of a single-tuple update in our approach.

######  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.

######  Example 24.

We analyze the time needed to maintain the views from Figure 12 under a
single-tuple update to any input relation. For the view tree constructed for
the case of heavy $(A,B)$-values (second row right), propagating an update
from any relation to the root view takes constant time. For instance, an
update $\delta{R}$ to $R$ changes the view $R^{\prime}(A,B)$ with
$\delta{R^{\prime}}(a,b)=\delta{R}(a,b,d)$; the view $V_{B}(A,B)$ with
$\delta{V_{B}}(a,b)=\exists{H_{B}}(a,b),\delta{R^{\prime}}(a,b),S^{\prime}(a,b)$;
changes to the views $V^{\prime}_{B}(A)$ and $V_{A}(A)$ are similar. The
auxiliary views $S^{\prime}(A,B)$ and $V^{\prime}_{C}(A)$ enable the constant-
time updates in this case by aggregating away the $E$-values in $S(A,B,E)$ and
the $C$-values in $V_{C}(A,B)$.

Consider now the view tree defined over the light parts of input relations
(bottom-left). The update $\delta{R}=\\{(a,b,d)\rightarrow m\\}$ affects the
light part $R^{A}$ of $R$ when $(a,b,d)\notin R$ or $a\in\pi_{A}R^{A}$. If so,
computing $\delta V_{B}(a,d,E)=\delta{R}^{A}(a,b,d),S^{A}(a,b,E)$ takes
$\mathcal{O}(N^{\epsilon})$ time since $a$ is light in $S^{A}$. The size of
$\delta V_{B}$ is also $\mathcal{O}(N^{\epsilon})$. Computing $\delta V_{A}$
at the root requires pairing each $E$-value from $\delta V_{B}$ with the
$(C,F)$-values in $V_{C}$ for the given $a$. Since $a$ is light in $T^{A}$,
the number of such $(C,F)$-values in $T^{A}$ is $\mathcal{O}(N^{\epsilon})$.
Thus, computing $\delta V_{A}$ takes $\mathcal{O}(N^{2\epsilon})$ time. A
similar analysis shows that updates to $S^{A}$ and $T^{A}$ also take
$\mathcal{O}(N^{2\epsilon})$ time, while updates to $U^{A}$ take
$\mathcal{O}(N^{3\epsilon})$ time.

For the view tree constructed for the case of heavy $A$-values (bottom-
middle), updates to $R^{AB}$ and $S^{AB}$ take $\mathcal{O}(N^{\epsilon})$
time, while updates to $T$ and $U$ take constant time. The indicator view
trees (top and middle row) encode the results of $\delta_{0}$-hierarchical
queries, thus maintaining their views takes constant time per update.

The indicator views $\exists H_{A}(A)$ and $\exists H_{B}(A,B)$ may change
under updates to any relation and respectively under updates to $R$ and $S$.
For instance, the update $\delta R$ can trigger a new single-tuple change in
$\exists H_{A}$ when the multiplicity $H_{A}(a)$ increases from 0 to non-zero
or vice versa. Applying this change $\delta(\exists H_{A})$ to the view trees
containing $\exists H_{A}$ takes constant time; the same holds for propagating
a change $\delta(\exists H_{B})$ to the view trees containing $\exists H_{B}$.

In conclusion, maintaining the views from Figure 12 under a single-tuple
update to any relation takes $\mathcal{O}(N^{3\epsilon})$ overall time. ∎

###  6.2 Rebalancing Partitions

As the database evolves under updates, we periodically rebalance the relation
partitions and views to account for a new database size and updated degrees of
data values. The cost of rebalancing is amortized over a sequence of updates.

##### Major Rebalancing.

We loosen the partition threshold to amortize the cost of rebalancing over
multiple updates. Instead of the actual database size $N$, the threshold now
depends on a number $M$ for which the invariant
$\left\lfloor\frac{1}{4}M\right\rfloor\leq N<M$ always holds. If the database
size falls below $\lfloor\frac{1}{4}M\rfloor$ or reaches $M$, we perform major
rebalancing, where we halve or respectively double $M$, followed by strictly
repartitioning the light parts of input relations with the new threshold
$M^{\epsilon}$ and recomputing the views. Figure 20 shows the major
rebalancing procedure.

MajorRebalancing(view trees $\mathcal{T}$, indicator triples
$\mathcal{T}_{Ind}$, threshold $\theta$)
---
1foreach $(T_{All},T_{L},T_{H})\in\mathcal{T}_{Ind}$ do
2foreach $R^{\mathcal{F}}\in T_{L},R\in T_{All}$ do
3$R^{\mathcal{F}}=\\{\mathbf{x}\rightarrow R(\mathbf{x})\mid\mathbf{x}\in
R,\,key=\mathbf{x}[\mathcal{F}],\,|\sigma_{\mathcal{F}=key}R|<\theta\\}$
4$\textsc{Recompute}(T_{L}),\;\textsc{Recompute}(T_{H})$
5foreach $T\in\mathcal{T}$ do $\textsc{Recompute}(T)$
Figure 20: Recomputing the light parts of base relations and affected views.

######  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.

The cost of major rebalancing is amortized over $\Omega{(M)}$ updates. After a
major rebalancing step, it holds that $N=\frac{1}{2}M$ (after doubling), or
$N=\frac{1}{2}M-\frac{1}{2}$ or $N=\frac{1}{2}M-1$ (after halving). To violate
the size invariant $\left\lfloor\frac{1}{4}M\right\rfloor\leq N<M$ and trigger
another major rebalancing, the number of required updates is at least
$\frac{1}{4}M$. Appendix F.4 proves the amortized
$\mathcal{O}(N^{(\mathsf{w}-1)\epsilon})$ time of major rebalancing. By
Proposition 17, we have $\delta=\mathsf{w}$ or $\delta=\mathsf{w}-1$; hence,
the amortized major rebalancing time is $\mathcal{O}(M^{\delta\epsilon})$.

##### Minor Rebalancing.

After an update $\delta{R}=\\{\mathbf{x}\rightarrow m\\}$ to relation $R$, we
check the light part and heavy part conditions of each partition of $R$.
Consider the light part $R^{\mathcal{S}}$ of $R$ partitioned on a schema
$\mathcal{S}$. If the number of tuples in $R^{\mathcal{S}}$ that agree with
$\mathbf{x}$ on $\mathcal{S}$ exceeds $\frac{3}{2}M^{\epsilon}$, then we
delete those tuples from $R^{\mathcal{S}}$. If the number of tuples that agree
with $\mathbf{x}$ on $\mathcal{S}$ in $R^{\mathcal{S}}$ is zero and in $R$ is
below $\frac{1}{2}M^{\epsilon}$, then we insert those tuples into
$R^{\mathcal{S}}$. Figure 21 shows this minor rebalancing procedure.

MinorRebalancing(trees $\mathcal{T}$, tree $T_{L}$, tree $T_{H}$, source $R$,
$key$, insert)
---
1let
$L(\mathcal{F})=\textsf{root}(T_{L}),\;H(\mathcal{F})=\textsf{root}(T_{H})$
2foreach $\mathbf{x}\in\sigma_{\mathcal{F}=key}R$ do
3let $cnt=$ if $(\textit{insert\,})\ R(\mathbf{x})$ else $-R(\mathbf{x})$
4foreach $T\in\mathcal{T}$ do
$\textsc{Apply}(T,\delta{R^{\mathcal{F}}}=\\{\mathbf{x}\rightarrow cnt\\})$
5let
$\delta(\exists{L})=\textsc{UpdateIndTree}(T_{L},\delta{R^{\mathcal{F}}}=\\{\mathbf{x}\rightarrow
cnt\\})$
6let
$\delta(\exists{H})=\textsc{UpdateIndTree}(T_{H},\delta(\nexists{L})=-\delta(\exists{L}))$
7foreach $T\in\mathcal{T}$ do $\textsc{Apply}(T,\delta(\exists{H}))$
Figure 21: Deleting heavy tuples from or inserting light tuples into the light
part of relation $R$.

######  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.

The cost of minor rebalancing is amortized over $\Omega(M^{\epsilon})$
updates. This lower bound on the number of updates is due to the gap between
the two thresholds in the heavy and light part conditions. Appendix F.4 proves
the amortized $\mathcal{O}(N^{\delta\epsilon})$ time of minor rebalancing.

OnUpdate(view trees $\mathcal{T}$, indicator triples $\mathcal{T}_{Ind}$,
update $\delta{R}$)
---
1$\textsc{UpdateTrees}(\mathcal{T},\mathcal{T}_{Ind},\delta{R})$
2if $(N=M)$
3$M=2M$
4$\textsc{MajorRebalancing}(\mathcal{T},\mathcal{T}_{Ind},M^{\epsilon})$
5else if $(N<\left\lfloor\frac{1}{4}M\right\rfloor)$
6$M=\left\lfloor\frac{1}{2}M\right\rfloor-1$
7$\textsc{MajorRebalancing}(\mathcal{T},\mathcal{T}_{Ind},M^{\epsilon})$
8else
9foreach $(T_{All},T_{L},T_{H})\in\mathcal{T}_{Ind}$ such that $R\in T_{All}$
do
10let $R^{\mathcal{F}}\in T_{L}\text{ be light part of $R$ partitioned on
$\mathcal{F}$ }$
11let $\textit{key}=\mathbf{x}[\mathcal{F}],\text{ where
}\delta{R}=\\{\mathbf{x}\rightarrow m\\}$
12if
$(\,|\sigma_{\mathcal{F}=key}R^{\mathcal{F}}|=0\,\land\,\,|\sigma_{\mathcal{F}=key}R|<\frac{1}{2}M^{\epsilon})$
13$\textsc{MinorRebalancing}(\mathcal{T},T_{L},T_{H},R,key,\textsf{true})$
14else if
$(\,|\sigma_{\mathcal{F}=key}R^{\mathcal{F}}|\geq\frac{3}{2}M^{\epsilon}\,)$
15$\textsc{MinorRebalancing}(\mathcal{T},T_{L},T_{H},R,key,\textsf{false})$
Figure 22:  Updating a set of view trees $\mathcal{T}$ and a set of triplets
of indicator view trees $\mathcal{T}_{Ind}$ under a sequence of single-tuple
updates to base relations.

Figure 22 gives the trigger procedure OnUpdate that maintains a set of view
trees $\mathcal{T}$ and a set of indicator trees $\mathcal{T}_{Ind}$ under a
sequence of single-tuple updates to input relations. We first apply an update
$\delta{R}$ to the view trees from $\mathcal{T}$ and indicator trees from
$\mathcal{T}_{Ind}$ using UpdateTrees from Figure 19. If this update leads to
a violation of the size invariant $\left\lfloor\frac{1}{4}M\right\rfloor\leq
N<M$, we invoke MajorRebalancing to recompute the light parts of the input
relations and affected views. Otherwise, for each triple of indicator trees
from $\mathcal{T}_{Ind}$ with the light part $R^{\mathcal{F}}$ partitioned on
$\mathcal{F}$, we check if the heavy or light condition is violated; if so, we
invoke MinorRebalancing to move the $R$-tuples having the $\mathcal{F}$-values
of the update $\delta{R}$ either into or from the light part $R^{\mathcal{F}}$
of relation $R$.

We state the amortized maintenance time of our approach under a sequence of
single-tuple updates.

######  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.

##  7 Conclusion and Future Work

In this paper we investigated the preprocessing-update-delay trade-off for
hierarchical queries and introduced an approach that recovers a number of
prior results when restricted to hierarchical queries. There are several lines
of future work. Of paramount importance is the generalization of our trade-off
from hierarchical to conjunctive queries and even to functional aggregate
queries. The results of this paper can be easily extended to hierarchical
queries with group-by aggregates and order-by clauses. In particular, this
extension would capture the prior result on constant-delay enumeration for
such queries in the context of factorized databases [43]. An open problem is
to find lower bounds for $\delta_{i}$-hierarchical queries for $i>1$. We
conjecture our update-delay upper bounds
$\mathcal{O}(N^{i\epsilon})/\mathcal{O}(N^{1-\epsilon})$ are worst-case
optimal, as it is the case for $i=0$ with $\epsilon=1$ [10] and $i=1$ with
$\epsilon=\frac{1}{2}$ (Proposition 10).

## References

  * [1] M. Abo Khamis, H. Q. Ngo, and A. Rudra.  FAQ: Questions Asked Frequently.  In PODS, pages 13–28, 2016.
  * [2] A. Amarilli, P. Bourhis, L. Jachiet, and S. Mengel.  A circuit-based approach to efficient enumeration.  In ICALP, pages 111:1–111:15, 2017.
  * [3] A. Amarilli, P. Bourhis, and S. Mengel.  Enumeration on trees under relabelings.  In ICDT, pages 5:1–5:18, 2018.
  * [4] A. Amarilli, P. Bourhis, S. Mengel, and M. Niewerth.  Constant-delay enumeration for nondeterministic document spanners.  In ICDT, pages 22:1–22:19, 2019.
  * [5] A. Atserias, M. Grohe, and D. Marx.  Size bounds and query plans for relational joins.  SIAM J. Comput., 42(4):1737–1767, 2013.
  * [6] G. Bagan.  MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay.  In CSL, pages 167–181, 2006.
  * [7] G. Bagan, A. Durand, E. Filiot, and O. Gauwin.  Efficient Enumeration for Conjunctive Queries over X-underbar Structures.  In CSL, pages 80–94, 2010.
  * [8] G. Bagan, A. Durand, and E. Grandjean.  On Acyclic Conjunctive Queries and Constant Delay Enumeration.  In CSL, pages 208–222, 2007.
  * [9] C. Beeri, R. Fagin, D. Maier, and M. Yannakakis.  On the Desirability of Acyclic Database Schemes.  J. ACM, 30(3):479–513, 1983.
  * [10] C. Berkholz, J. Keppeler, and N. Schweikardt.  Answering Conjunctive Queries Under Updates.  In PODS, pages 303–318, 2017.
  * [11] C. Berkholz, J. Keppeler, and N. Schweikardt.  Answering FO+MOD queries under updates on bounded degree databases.  In ICDT, pages 8:1–8:18, 2017.
  * [12] C. Berkholz, J. Keppeler, and N. Schweikardt.  Answering ucqs under updates and in the presence of integrity constraints.  In ICDT, pages 8:1–8:19, 2018.
  * [13] J. Brault-Baron.  A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic.  In CSL, pages 137–151, 2012.
  * [14] J. Brault-Baron.  De la pertinence de l’énumération: complexité en logiques propositionnelle et du premier ordre.  PhD thesis, Université de Caen, 2013.
  * [15] N. Carmeli and M. Kröll.  Enumeration complexity of conjunctive queries with functional dependencies.  In ICDT, pages 11:1–11:17, 2018.
  * [16] R. Chirkova and J. Yang.  Materialized Views.  Found. & Trends DB, 4(4):295–405, 2012.
  * [17] S. Deep and P. Koutris.  Compressed Representations of Conjunctive Query Results.  In PODS, pages 307–322, 2018.
  * [18] A. Durand and E. Grandjean.  First-order Queries on Structures of Bounded Degree are Computable with Constant Delay.  ACM Trans. Comput. Logic, 8(4):21, 2007.
  * [19] A. Durand, N. Schweikardt, and L. Segoufin.  Enumerating Answers to First-order Queries over Databases of Low Degree.  In PODS, pages 121–131, 2014.
  * [20] A. Durand and Y. Strozecki.  Enumeration complexity of logical query problems with second-order variables.  In CSL, pages 189–202, 2011.
  * [21] R. Fink and D. Olteanu.  Dichotomies for queries with negation in probabilistic databases.  ACM Trans. Datab. Syst., 41(1):4:1–4:47, 2016.
  * [22] M. Grohe, Y. Gurevich, D. Leinders, N. Schweikardt, J. Tyszkiewicz, and J. V. den Bussche.  Database query processing using finite cursor machines.  Theory Comput. Syst., 44(4):533–560, 2009.
  * [23] M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak.  Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.  In STOC, pages 21–30, 2015.
  * [24] X. Hu and K. Yi.  Instance and output optimal parallel algorithms for acyclic joins.  In PODS, pages 450–463, 2019.
  * [25] M. Idris, M. Ugarte, and S. Vansummeren.  The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates.  In SIGMOD, pages 1259–1274, 2017.
  * [26] M. Idris, M. Ugarte, S. Vansummeren, H. Voigt, and W. Lehner.  Conjunctive queries with inequalities under updates.  PVLDB, pages 733–745, 2018.
  * [27] A. Kara, H. Q. Ngo, M. Nikolic, D. Olteanu, and H. Zhang.  Counting triangles under updates in worst-case optimal time.  In ICDT, pages 4:1–4:18, 2019.
  * [28] A. Kara, H. Q. Ngo, M. Nikolic, D. Olteanu, and H. Zhang.  Counting triangles under updates in worst-case optimal time.  CoRR, abs/1804.02780, 2019.
  * [29] A. Kara, H. Q. Ngo, M. Nikolic, D. Olteanu, and H. Zhang.  Maintaining Triangle Queries under Updates.  ACM Trans. Database Syst., To appear, 2020.
  * [30] W. Kazana and L. Segoufin.  First-order Query Evaluation on Structures of Bounded Degree.  LMCS, 7(2), 2011.
  * [31] W. Kazana and L. Segoufin.  Enumeration of First-order Queries on Classes of Structures with Bounded Expansion.  In PODS, pages 297–308, 2013.
  * [32] W. Kazana and L. Segoufin.  Enumeration of Monadic Second-order Queries on Trees.  ACM Trans. Comput. Logic, 14(4):25:1–25:12, 2013.
  * [33] M. A. Khamis, H. Q. Ngo, and D. Suciu.  What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another?  In PODS, pages 429–444, 2017.
  * [34] C. Koch.  Incremental Query Evaluation in a Ring of Databases.  In PODS, pages 87–98, 2010.
  * [35] C. Koch et al.  DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views.  VLDB J., 23(2):253–278, 2014.
  * [36] P. Koutris and D. Suciu.  Parallel evaluation of conjunctive queries.  In PODS, pages 223–234, 2011.
  * [37] K. Losemann and W. Martens.  MSO queries on trees: enumerating answers under updates.  In CSL-LICS, pages 67:1–67:10, 2014.
  * [38] D. Marx.  Approximating fractional hypertree width.  ACM Trans. Alg., 6(2):29:1–29:17, 2010.
  * [39] H. Q. Ngo, E. Porat, C. Ré, and A. Rudra.  Worst-case optimal join algorithms.  J. ACM, 65(3):16:1–16:40, 2018.
  * [40] M. Niewerth.  MSO queries on trees: Enumerating answers under updates using forest algebras.  In LICS, pages 769–778, 2018.
  * [41] M. Niewerth and L. Segoufin.  Enumeration of MSO queries on strings with constant delay and logarithmic updates.  In PODS, pages 179–191, 2018.
  * [42] M. Nikolic and D. Olteanu.  Incremental View Maintenance with Triple Lock Factorization Benefits.  In SIGMOD, pages 365–380, 2018.
  * [43] D. Olteanu and M. Schleich.  Factorized databases.  SIGMOD Rec., 45(2):5–16, 2016.
  * [44] D. Olteanu and Závodný.  Factorised representations of query results: size bounds and readability.  In ICDT, pages 285–298, 2012.
  * [45] D. Olteanu and J. Závodný.  Size Bounds for Factorised Representations of Query Results.  ACM TODS, 40(1):2:1–2:44, 2015.
  * [46] N. Schweikardt, L. Segoufin, and A. Vigny.  Enumeration for FO Queries over Nowhere Dense Graphs.  In PODS, pages 151–163, 2018.
  * [47] L. Segoufin.  Constant delay enumeration for conjunctive queries.  SIGMOD Rec., 44(1):10–17, 2015.
  * [48] L. Segoufin and A. Vigny.  Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion.  In ICDT, pages 20:1–20:16, 2017.
  * [49] D. Suciu, D. Olteanu, C. Ré, and C. Koch.  Probabilistic Databases.  Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.
  * [50] M. Yannakakis.  Algorithms for acyclic database schemes.  In VLDB, pages 82–94, 1981.

##  Appendix A Further Examples

######  Example 28.

Let the $\delta_{1}$-hierarchical non-free-connex query

$Q(A,C)=R(A,B),S(B,C)$

whose relations have size at most $N$. We can compute $Q$ in time
$\mathcal{O}(N^{2})$ and then enumerate its tuples with $\mathcal{O}(1)$
delay. We can alternatively enumerate its tuples with $\mathcal{O}(N)$ delay
after $\mathcal{O}(N)$ preprocessing time [8]. It is conjectured that its
delay cannot be lowered to constant after linear-time preprocessing, since it
is not free-connex [8].

Our approach achieves $\mathcal{O}(N^{1-\epsilon})$ delay and
$\mathcal{O}(N^{1+\epsilon})$ preprocessing for any $\epsilon\in[0,1]$. It
recovers the two aforementioned cases by conveniently choosing $\epsilon$. If
$\epsilon=1$, we obtain $\mathcal{O}(1)$ delay after $\mathcal{O}(N^{2})$
preprocessing. If $\epsilon=0$, we obtain $\mathcal{O}(N)$ delay and
preprocessing. A special case of $Q$ is matrix multiplication for $n\times n$
matrices $R$ and $S$. With $\epsilon=1/2$, we obtain $\mathcal{O}(N^{3/2})$
preprocessing time and $\mathcal{O}(N^{1/2})$ delay for each of the $N=n^{2}$
elements in the matrix $Q$.

We partition $R$ and $S$ on $B$: A $B$-value $b$ is light in $R$ if
$|\\{a\mid(a,b)\in R\\}|\leq N^{\epsilon}$ and heavy otherwise (similar for
$S$). Since each heavy $B$-value is paired with at least $N^{\epsilon}$
$A$-values in $R$, there are at most $N^{1-\epsilon}$ heavy $B$-values. There
are four cases to consider: $B$ is either light or heavy in each of $R$ and
$S$. We can reduce them to two cases: either $B$ is light in both relations,
or $B$ is heavy in at least one of them. We keep the light/heavy information
in two indicator views: $L_{B}(B)=R^{B}(A,B),S^{B}(B,C)$, where $R^{B}$ and
$S^{B}$ are the light parts of $R$ and respectively $S$; and
$H_{B}(B)=All_{B}(B),\nexists L_{B}(B)$, where $All_{B}(B)=R(A,B),S(B,C)$. The
$\exists$ operator before indicators denotes their use with set semantics,
i.e., the tuple multiplicities are $0$ or $1$. The $\nexists$ operator flips
the multiplicity.

$All_{B}({B})$$All_{A}({B})$$All_{C}({B})$$R(\underline{A},B)$$S(B,\underline{C})$

$L_{B}({B})$$L_{A}({B})$$L_{C}({B})$$R^{B}(\underline{A},B)$$S^{B}(B,\underline{C})$

$H_{B}({B})$$All_{B}({B})$$\nexists L_{B}({B})$

$V_{B}({\underline{A},\underline{C}})$$\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}R^{B}(\underline{A},B)$$\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}S^{B}(B,\underline{C})$

$V_{B}({{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}B}})$$\exists
H_{B}({B})$$R^{\prime}({B})$$R(\underline{A},B)$$S^{\prime}({B})$$S(B,\underline{C})$

Figure 23: The view trees for $Q(A,C)=R(A,B),S(B,C)$ in Example 28. The dashed
boxes enclose views that are only needed in the dynamic case.

Figure 23 gives the evaluation and maintenance strategies for our query. A
strategy is depicted by a view tree, with one view per node such that the head
of the view is depicted at the node and its body is the join of its children.

To support light/heavy partitions, we need to keep the degree information of
the $B$-values in the two relations. The light/heavy indicators can be
computed in linear time, e.g., for $L_{B}$ we start with the light parts of
$R$ and $S$, aggregate away $A$ and respectively $C$ and then join them on
$B$.

If $B$ is light, we compute the view $V_{B}(A,C)$ in time
$\mathcal{O}(N^{1+\epsilon})$: We iterate over $S^{B}$ and for each of its
tuples $(b,c)$, we fetch the $A$-values in $R^{B}$ paired with $b$ in $R$. The
iteration over $S^{B}$ takes linear time and for each $b$ there are at most
$N^{\epsilon}$ $A$-values in $R$. The view $V_{B}(A,C)$ is a subset of $Q$’s
result.

If $B$ is heavy, we construct the view $V_{B}(B)$ with up to $N^{1-\epsilon}$
heavy $B$-values. For each such value $b$, we can enumerate the distinct
tuples $(a,c)$ such that $R(a,b)$ and $S(b,c)$ hold. Distinct $B$-values may,
however, have the same tuple $(a,c)$. Therefore, if we were to enumerate such
tuples for one $B$-value after those for another $B$-value, the same tuple
$(a,c)$ may be output several times, which violates the enumeration
constraint. To address this challenge, we use the union algorithm [20]. We use
the $N^{1-\epsilon}$ buckets of $(a,c)$ tuples, one for each heavy $B$-value,
and an extra bucket $V_{B}(A,C)$ constructed in the light case. From each
bucket of a $B$-value, we can enumerate the distinct $(a,c)$ tuples with
constant delay by looking up into $R$ and $S$. The tuples in the materialized
view $V_{B}(A,C)$ can be enumerated with constant delay. We then use the union
algorithm to enumerate the distinct $(a,c)$ tuples with delay given by the sum
of the delays of the buckets. For each such tuple, we sum up the positive
multiplicities of its occurrences in the buckets. This yields an overall
$\mathcal{O}(N^{1-\epsilon})$ delay for the enumeration of the distinct tuples
in the result of $Q$.

We now turn to the dynamic case. The preprocessing time and delay remain the
same as in the static case, while each single-tuple update can be processed in
$\mathcal{O}(N^{\epsilon})$ amortized time. To support updates, we need to
maintain tuple multiplicities in addition to the degree information of the
$B$-values in the two relations. The multiplicity of a result tuple is the sum
of the multiplicities of its duplicates across the
$\mathcal{O}(N^{1-\epsilon})$ buckets. We also need two views to support
efficient updates to $R$ and $S$; these are marked with the dashed boxes in
Figure 23. For simplicity, we assume that each view tree maintains copies of
its base relations.

Consider a single-tuple update $\delta R=\\{(a,b)\rightarrow m\\}$ to relation
$R$. We maintain each view affected by $\delta R$ using the hierarchy of
materialized views from Figure 23. The changes in those views are expressed
using the classical delta rules [16]. We update the views $R^{\prime}(B)$ and
$V_{B}(B)$ in the bottom-right tree with $\delta R^{\prime}(b)=\delta R(a,b)$
and $\delta V_{B}(b)=\exists H_{B}(b),\delta R^{\prime}(b),S^{\prime}(b)$ in
constant time; the same holds for updating the views $All_{A}(B)$,
$All_{B}(B)$, and $H_{B}(B)$.

The update $\delta R$ affects the light part $R^{B}$ of $R$ if the $B$-value
$b$ already exists among the $B$-values in $R^{B}$ or does not exist in $R$.
For such change $\delta R^{B}$, we update $V_{B}(A,C)$ with $\delta
V_{B}(a,C)$ $=\delta R^{B}(a,b),S^{B}(b,C)$ in time
$\mathcal{O}(N^{\epsilon})$ since $b$ is light in $S^{B}$; updating $L_{B}(B)$
and $H_{B}(B)$ takes constant time.

The update $\delta R$ may trigger a new single-tuple change in $\exists
H_{B}$, affecting $V_{B}(B)$. The change $\delta(\exists H_{B})$ is non-empty
only when the multiplicity $H_{B}(b)$ changes from 0 to non-zero or vice
versa. For such change $\delta(\exists H_{B})$, we update $V_{B}(B)$ via
constant-time lookups in $R^{\prime}(b)$ and $S^{\prime}(b)$.

The update $\delta R$ may change the degree of $b$ in $R$ from light to heavy
or vice versa. In such cases, we need to rebalance the partitioning of $R$ and
possibly recompute some of the views. Although such rebalancing steps may take
time more than $\mathcal{O}(N^{\epsilon})$, they happen periodically and their
amortized cost remains the same as for a single-tuple update (Section 6).∎

$All_{B}({B})$$All_{A}({B})$$R(\underline{A},B)$$S(B)$

$L_{B}({B})$$L_{A}({B})$$R^{{B}}(\underline{A},B)$$S^{{B}}(B)$

$H_{B}({B})$$All_{B}({B})$$\nexists L_{B}({B})$

$V_{B}({A})$$R(\underline{A},B)$$S(B)$

$V_{B}({\underline{A}})$$R^{B}(\underline{A},B)$$S^{B}(B)$

$V_{B}({{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}B}})$$\exists
H_{B}({B})$$R^{\prime}({B})$$R(\underline{A},B)$$S(B)$

Figure 24: The view trees for $Q(A)=R(A,B),S(B)$ in Example 29. The bottom-
left view tree is the only one needed in the static case, all others are
needed in the dynamic case.

######  Example 29.

Let the $\delta_{1}$-hierarchical and free-connex query

$Q(A)=R(A,B),S(B)$

whose relations have size at most $N$. Figure 24 shows the single view tree
(bottom-left) that our approach constructs in the static case, and the other
five view trees needed in the dynamic case. In the static case, since $Q$ is
free-connex, its result can be computed in $\mathcal{O}(N)$ time and then its
tuples can be enumerated with $\mathcal{O}(1)$ delay. Our approach does not
partition the relations in the static case. We compute the view $V_{B}(A)$ in
time $\mathcal{O}(N)$ by iterating over the tuples in $R$ and looking up for
each tuple $(a,b)$ in $R$ the multiplicity of $b$ in $S$ in $\mathcal{O}(1)$
time. The result can be enumerated from the view $V_{B}(A)$ with
$\mathcal{O}(1)$ delay.

In the dynamic case, we partition relations $R$ and $S$ on the bound join
variable $B$ and create the indicators $L_{B}(B)$ and $H_{B}(B)$ as in Figure
24. In the light case, we compute the view $V_{B}(A)$ in $\mathcal{O}(N)$
time: For each $(a,b)$ in the light part $R^{B}$ of $R$, we check the
multiplicity of $b$ in the light part $S^{B}$ of $S$ using a constant-time
lookup. In the heavy case, we compute the view $V_{B}(B)$ in $\mathcal{O}(N)$
time using the heavy indicator $\exists H_{B}$, the input relation $S$, and
the projection $R^{\prime}(B)$ of $R$ on $B$.

We can enumerate the tuples in the query result with
$\mathcal{O}(N^{1-\epsilon})$ delay: Since there are at most $N^{1-\epsilon}$
heavy $B$-values in $V_{B}(B)$, each with its own list of $A$-values in $R$,
we need $\mathcal{O}(N^{1-\epsilon})$ delay to enumerate the distinct
$A$-values paired with the heavy $B$-values. In addition, we can enumerate
from the view $V_{B}(A)$ created for the light $B$-values with constant delay.
To obtain the multiplicity of each output tuple, we sum up the positive
multiplicities of the duplicates of the tuple across the
$\mathcal{O}(N^{1-\epsilon})$ buckets.

A single-tuple update to $R$ triggers constant-time updates to all views. A
single-tuple update to $S$ triggers constant-time updates to the indicators
and $V_{B}(B)$. In the light case, the update to $V_{B}(A)$ is given by
$\delta V_{B}(A)=R^{B}(A,b),\delta S^{B}(b)$, which requires
$\mathcal{O}(N^{\epsilon})$ time since $b$ is light in $R^{B}$. We may need to
rebalance the partitions, which gives an amortized update time of
$\mathcal{O}(N^{\epsilon})$. ∎

Since both queries in Examples 28 and 29 are $\delta_{1}$-hierarchical and do
not have repeating relation symbols, there is no algorithm that can maintain
them under single-tuple updates with $\mathcal{O}(N^{\frac{1}{2}-\gamma})$
amortized update time and $\mathcal{O}(N^{\frac{1}{2}-\gamma})$ delay for
$\gamma>0$ unless the OMv conjecture fails (Proposition 10). Our approach
meets this lower bound for $\epsilon=\frac{1}{2}$.

##  Appendix B Missing Details in Section 1

We introduce some useful notation for the following sections. Given a query
$Q$ and a variable $X$ in $Q$, we denote by $\mathit{vars}(\mathit{atoms}(X))$
and $\mathit{free}(\mathit{atoms}(X))$ the set of all and respectively free
variables in the schemas of the atoms in $\mathit{atoms}(X)$. For a variable
order $\omega$ of $Q$ and a variable or atom $X$ in $\omega$,
$\mathsf{anc}_{\omega}(X)$ denotes the set of ancestor variables of $X$ in
$\omega$. By $\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)$, we denote the set
of the highest bound variables in $\omega$ that are ancestors of free
variables, that is, $\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)$ consists of
all bound variables $Y$ such that $Y$ is ancestor of at least one free
variable and has no bound variables as ancestors.

The following helping lemma states that for hierarchical queries, integral and
fractional edge cover numbers are equal.

######  Lemma 30.

For any hierarchical query $Q$ and $\mathcal{F}\subseteq\mathit{vars}(Q)$, it
holds $\rho^{\ast}(\mathcal{F})=\rho(\mathcal{F})$.

###### Proof.

By definition, each integral edge cover of $\mathcal{F}$ is a fractional edge
cover of $\mathcal{F}$. This means
$\rho^{*}(\mathcal{F})\leq\rho(\mathcal{F})$. It remains to show
$\rho(\mathcal{F})\leq\rho^{*}(\mathcal{F})$. We define an integral edge cover
$\boldsymbol{\lambda}=(\lambda_{R(\mathcal{X})})_{R(\mathcal{X})\in\mathit{atoms}(Q)}$
of $\mathcal{F}$ and show that
$\sum_{R(\mathcal{X})\in\mathit{atoms}(Q)}\lambda_{R(\mathcal{X})}\leq\rho^{\ast}(\mathcal{F})$.
Let $\omega$ be an arbitrary canonical variable order for $Q$. A maximal
variable path $p$ in $\omega$ is a path that starts at the root of $\omega$
and ends at a variable $X$ such that all children of $X$ are atoms. We call
$X$ the end variable in $p$. All child atoms of an end variable must have the
same schema. Assume that $\omega$ has $k$ maximal variable paths and let
$\mathcal{P}$ be the set consisting of these paths. For each maximal variable
path $p\in\mathcal{P}$ with end variable $X$, we fix an arbitrary child atom
$R_{p}(\mathcal{X}_{p})$ of $X$. For each atom $R(\mathcal{X})$ in $Q$, we
define:

$\displaystyle\lambda_{R(\mathcal{X})}=\begin{cases}1,&\text{if
$R(\mathcal{X})=R_{p}(\mathcal{X}_{p})$ for some $p\in\mathcal{P}$}\\\
0,&\text{otherwise}\end{cases}$

Since $\mathcal{P}$ contains $k$ paths, we have
$\sum_{R(\mathcal{X})\in\mathit{atoms}(Q)}\lambda_{R(\mathcal{X})}=k$.

Let
$\boldsymbol{\lambda^{\prime}}=(\lambda^{\prime}_{R(\mathcal{X})})_{R(\mathcal{X})\in\mathit{atoms}(Q)}$
be an arbitrary fractional edge cover of $\mathcal{F}$. We complete the proof
by showing:

  1. 1.

$\boldsymbol{\lambda}=(\lambda_{R(\mathcal{X})})_{R(\mathcal{X})\in\mathit{atoms}(Q)}$
is an integral edge cover of $\mathcal{F}$.

  2. 2.

$k\leq\sum_{R(\mathcal{X})\in\mathit{atoms}(Q)}\lambda_{R(\mathcal{X})}^{\prime}$.

(1)
$\boldsymbol{\lambda}=(\lambda_{R(\mathcal{X})})_{R(\mathcal{X})\in\mathit{atoms}(Q)}$
is an integral edge cover of $\mathcal{F}$: Let $X$ be an arbitrary variable
in $Q$. The variable $X$ must be included in at least one maximal variable
path $p\in\mathcal{P}$. Since $\omega$ is canonical, the atom
$R_{p}(\mathcal{X}_{p})$ has $X$ in its schema. Due to
$\lambda_{R_{p}(\mathcal{X}_{p})}=1$, the variable $X$ is covered by the edge
cover $\boldsymbol{\lambda}$. Since $X$ was chosen arbitrarily, it follows
that $\boldsymbol{\lambda}$ is an integral edge cover of $\mathcal{F}$.

(2)
$k\leq\sum_{R(\mathcal{X})\in\mathit{atoms}(Q)}\lambda_{R(\mathcal{X})}^{\prime}$:
Given any maximal variable path $p\in\mathcal{P}$ where the end variable has
the child atoms $R_{1}(\mathcal{X}_{1}),\ldots,R_{m}(\mathcal{X}_{m})$, we
define $s_{p}=\sum_{i\in[m]}\lambda^{\prime}_{R_{i}(\mathcal{X}_{i})}$. Let
$p$ be a maximal variable path in $\mathcal{P}$ with end variable $X$. Let
$R_{1}(\mathcal{X}_{1}),\ldots,R_{m}(\mathcal{X}_{m})$ be the child atoms of
$X$. Besides these atoms, no other atom has $X$ in its schema. Hence,
$s_{p}\geq 1$. Since there are $k$ maximal variable paths, this implies
$k\leq\sum_{p\in\mathcal{P}}s_{p}\leq\sum_{R(\mathcal{X})\in\mathit{atoms}(Q)}\lambda_{R(\mathcal{X})}^{\prime}$.
∎

###  B.1 Transforming Canonical into Free-Top Variable Orders

To decide the static or dynamic width of a hierarchical query, it is useful to
transform a canonical variable order of the query into a free-top one. In the
following we describe such a transformation.

##### Restrictions of Variable Orders.

Given a variable order $\omega$ and a set
$\mathcal{X}\subseteq\mathit{vars}(\omega)$, we obtain the restriction
$\omega|_{\mathcal{X}}$ of $\omega$ induced by $\mathcal{X}$ by executing the
following procedure for each $X\in\mathit{vars}(\omega)-\mathcal{X}$. We
eliminate the variable $X$. If $X$ has no children, we are done. Otherwise,
let $\omega_{1},\ldots,\omega_{k}$ be the subtrees of $X$. If $X$ has a parent
$Y$, then $\omega_{1},\ldots,\omega_{k}$ become the subtrees of $Y$. If $X$
has no parent, then $\omega_{1},\ldots,\omega_{k}$ become independent trees.

##### From Canonical to Free-Top Variable Orders.

Let $\omega=(T_{\omega},\textit{dep}_{\omega})$ be a canonical variable order
of a hierarchical query. We obtain the free-top variable order
$\omega^{f}=\text{free-top}(\omega)$ from $\omega$ as follows. Recall that
$\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)$ is the set of all bound
variables in $\omega$ that are ancestors of free variables and have no bound
variables as ancestors. If
$\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)=\emptyset$, then the variable
order $\omega$ is already free-top and we set $\omega^{f}=\omega$. Otherwise,
let $\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)=\\{X_{1},\ldots,X_{k}\\}$.
The variable order $\omega^{f}$ results from $\omega$ by restructuring the
subtrees in $\omega$ rooted at the variables $X_{1},\ldots,X_{k}$.
Intuitively, we move the free variables within each subtree rooted at $X_{j}$
above the bound ones. Consider a subtree $\omega_{X_{j}}$ rooted at $X_{j}$
for some $j\in[k]$. Let $F_{j}^{1},\ldots,F_{j}^{n_{j}}$ be the ordering of
the free variables in $\omega_{X_{j}}$ that respects the partial order given
by $\omega_{X_{j}}$ and breakes ties using the lexicographic ordering of the
variables. The new subtree $\omega^{f}_{F_{j}^{1}}$ in $\omega^{f}$ that
replaces the subtree $\omega_{X_{j}}$ starts with the path
$F_{j}^{1},\ldots,F_{j}^{n_{j}}$ followed by the restriction of
$\omega_{X_{j}}$ induced by
$\mathit{vars}(\omega_{X_{j}})-\\{F_{j}^{1},\ldots,F_{j}^{n_{j}}\\}$. That is,
the root of $\omega^{f}_{F_{j}^{1}}$ is the variable $F_{j}^{1}$, the only
child of $F_{j}^{\ell}$ is $F_{j}^{\ell+1}$ for each $\ell\in[n_{j}-1]$, and
the only child of $F_{j}^{n_{j}}$ is the root of the tree
$\omega_{X_{j}}|_{\mathit{vars}(\omega_{X_{j}})-\\{F_{j}^{1},\ldots,F_{j}^{n_{j}}\\}}$.

$\underline{A}$$\underline{B}$$C$$\underline{D}$$E$$F$$\underline{G}$$H$$I$$\underline{J}$$\underline{K}$$\underline{L}$$\underline{M}$$N$$O$$R_{1}$$R_{2}$$R_{3}$$R_{4}$$R_{5}$$R_{6}$$R_{7}$$R_{8}$

$\underline{A}$$\underline{B}$$\underline{G}$$\underline{D}$$H$$I$$\underline{J}$$\underline{K}$$E$$\underline{L}$$\underline{M}$$C$$F$$N$$O$$R_{1}$$R_{2}$$R_{3}$$R_{4}$$R_{5}$$R_{6}$$R_{7}$$R_{8}$

Figure 25:  Left: canonical variable order $\omega^{\mathsf{c}}$ for a
hierarchical query with free variables $\\{A,B,D,G,J,K,L,M\\}$. Schemas of
leaf atoms are skipped.
$\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega^{\mathsf{c}})=\\{E,C\\}$. Right:
$\mathsf{free}\text{-}\mathsf{top}(\omega^{\mathsf{c}})$.

######  Example 31.

Figure 25 shows a variable order $\omega$ (left) of a hierarchical query with
free variables $\\{A,\allowbreak B,\allowbreak D,\allowbreak G,\allowbreak
J,\allowbreak K,\allowbreak L,\allowbreak M\\}$ and the free-top variable
order $\mathsf{free}\text{-}\mathsf{top}(\omega^{\mathsf{c}})$ (right). For
simplicity, the schemas of the leaf atoms are skipped. The only bound
variables in $\omega$ that are ancestors of free variables but do not have
bound variables as ancestors are $E$ and $C$, hence,
$\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega^{\mathsf{c}})=\\{E,C\\}$.

The following remark formulates two simple properties on the relationship
between $\omega$ and $\mathsf{free}\text{-}\mathsf{top}(\omega)=\omega^{f}$.
Informally: For each variable $X\in\mathit{vars}(\omega)$ that is not included
in any $\omega_{X_{j}}$ with $j\in[k]$, the root path of $X$ as well as the
set of variables in the subtree rooted at $X$ are the same in $\omega$ and
$\omega^{f}$; for each variable $X$ in $\mathit{bound}(\omega_{X_{j}})$ with
$j\in[k]$, all free variables in $\omega_{X_{j}}$ move to the root path of $X$
when constructing $\omega^{f}$.

######  Remark 32.

Let $\omega$ be a canonical variable order of a hierarchical query,
$\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)=\\{X_{i}\\}_{i\in[k]}$, and
$\omega^{f}=\mathsf{free}\text{-}\mathsf{top}(\omega)$. It holds:

  1. 1.

For each
$X\in\mathit{vars}(\omega)-\bigcup_{j\in[k]}\mathit{vars}(\omega_{X_{j}})$:
$\mathsf{anc}_{\omega^{f}}(X)=\mathsf{anc}_{\omega}(X)$ and
$\mathit{vars}(\omega^{f}_{X})=\mathit{vars}(\omega_{X})$.

  2. 2.

For each $j\in[k]$ and $X\in\mathit{bound}(\omega_{X_{j}})$:
$\mathsf{anc}_{\omega^{f}}(X)=\mathsf{anc}_{\omega}(X)\cup\mathit{free}(\omega_{X_{j}})$
and
$\mathit{vars}(\omega^{f}_{X})=\mathit{vars}(\omega_{X})-\mathit{free}(\omega_{X})$.

######  Lemma 33.

If $\omega$ is a canonical variable order for a hierarchical query $Q$, then
$\mathsf{free}\text{-}\mathsf{top}(\omega)$ is a free-top variable order for
$Q$.

###### Proof.

Let $\mathit{h}^{\mathit{B}}_{\mathit{F}}(\omega)=\\{X_{1},\ldots,X_{k}\\}$
and $\omega^{f}=\mathsf{free}\text{-}\mathsf{top}(\omega)$. We show:

  1. 1.

$\omega^{f}$ is a valid variable order for $Q$.

  2. 2.

$\omega^{f}$ is free-top.

Proof of (1): $\omega^{f}$ is a valid variable order for $Q$.
Let $R(\mathcal{Y})$ be an atom in $Q$ and $X$ the parent node of
$R(\mathcal{Y})$ in $\omega$. Since $\omega$ is canonical,
$\mathsf{anc}_{\omega}(R(\mathcal{Y}))=\mathcal{Y}$. We show that
$\mathcal{Y}\subseteq\mathsf{anc}_{\omega^{f}}(R(\mathcal{Y}))$ and the parent
variable of $R(\mathcal{Y})$ in $\omega^{f}$ is the lowest variable in
$\mathsf{anc}_{\omega^{f}}(R(\mathcal{Y}))$ that is included in $\mathcal{Y}$.
We make a case distinction on the position of the parent variable $X$ of
$R(\mathcal{Y})$ in $\omega$.

  * •

$X\notin\bigcup_{j\in[k]}\omega_{X_{j}}$: By Remark 32.(1),
$(\\{X\\}\cup\mathsf{anc}_{\omega^{f}}(X))=(\\{X\\}\cup\mathsf{anc}_{\omega}(X))$.
From $(\\{X\\}\cup\mathsf{anc}_{\omega}(X))=\mathcal{Y}$ follows that
$(\\{X\\}\cup\mathsf{anc}_{\omega^{f}}(X))=\mathcal{Y}$. By construction,
$R(\mathcal{Y})$ is a child node of $X$ in $\omega^{f}$. Thus,
$R(\mathcal{Y})$ is a child of the lowest variable in
$\mathsf{anc}_{\omega^{f}}(R(\mathcal{Y}))$ that is included in $\mathcal{Y}$.

  * •

$X\in\mathit{bound}(\omega_{X_{j}})$ for some $j\in[k]$: By Remark 32.(2),
$(\\{X\\}\cup\mathsf{anc}_{\omega}(X))\subseteq(\\{X\\}\cup\mathsf{anc}_{\omega^{f}}(X))$.
From $(\\{X\\}\cup\mathsf{anc}_{\omega}(X))=\mathcal{Y}$ follows
$\mathcal{Y}\subseteq(\\{X\\}\cup\mathsf{anc}_{\omega^{f}}(X))$. By
construction, $R(\mathcal{Y})$ is a child node of $X$ in $\omega^{f}$. Hence,
$R(\mathcal{Y})$ is a child of the lowest variable in
$\mathsf{anc}_{\omega^{f}}(R(\mathcal{Y}))$ that is included in $\mathcal{Y}$.

  * •

$X\in\mathit{free}(\omega_{X_{j}})$ for some $j\in[k]$: Let $Y$ be the lowest
bound variable in $\mathsf{anc}_{\omega}(X)$. It holds $Y\in\mathcal{Y}$. By
construction, $R(\mathcal{Y})$ is a child of $Y$ in $\omega^{f}$. By Remark
32.(2), all free variables in $\omega_{X_{j}}$ move to the root path of $Y$,
i.e.,
$(\\{X\\}\cup\mathsf{anc}_{\omega}(X))\subseteq(\\{Y\\}\cup\mathsf{anc}_{\omega^{f}}(Y))$.
From $(\\{X\\}\cup\mathsf{anc}_{\omega}(X))=\mathcal{Y}$ follows
$\mathcal{Y}\subseteq(\\{Y\\}\cup\mathsf{anc}_{\omega^{f}}(Y))$. Since
$Y\in\mathcal{Y}$ and the only variable from $\mathcal{Y}$ in $\omega^{f}_{Y}$
is $Y$, $R(\mathcal{Y})$ is a child of the lowest variable in
$\mathsf{anc}_{\omega^{f}}(R(\mathcal{Y}))$ that is included in $\mathcal{Y}$.

Proof of (2): $\omega^{f}$ is free-top.
The variables $X_{1},\ldots,X_{k}$ are the highest bound variables in $\omega$
that contain free variables in their subtrees. Hence, for each $j\in[k]$, all
ancestors of $X_{j}$ in $\omega$ are free. When constructing $\omega^{f}$ from
$\omega$, each subtree $\omega_{X_{j}}$ is replaced by the free-top subtree
$\omega^{f}_{F_{j}^{1}}$. Thus, $\omega^{f}$ is free-top. ∎

###  B.2 Proof of Theorem 2

######  Theorem 2.

Given a hierarchical query with static width $\mathsf{w}$, 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.

The theorem follows from Propositions 20, 21, and 22. 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 view trees
$\\{T_{1},\ldots,T_{k}\\}$ returned by $\tau(\omega,\mathcal{F})$ from Figure
11 in the static mode. By Proposition 21, these views can be materialized in
$\mathcal{O}(N^{1+(\mathsf{w}-1)\epsilon})$. By Proposition 20,
$Q(\mathcal{F})$ is equivalent to $\bigcup_{i\in[k]}Q_{i}(\mathcal{F})$, where
$Q_{i}(\mathcal{F})$ is the query defined by the join of the leaves in
$T_{i}$. By Proposition 22, the result of $Q(\mathcal{F})$ can be enumerated
from these materialized views with delay $\mathcal{O}(N^{1-\epsilon})$.

If the canonical variable order for $Q$ consists of several trees
$\omega_{1},\dots,\omega_{m}$, we construct a set $\mathcal{T}_{i}$ of view
trees for each $\omega_{i}$, where $i\in[m]$. The result of the query is the
Cartesian product of the tuple sets obtained from each $\mathcal{T}_{i}$.
Given that each set $\mathcal{T}_{i}$ of view trees admits
$\mathcal{O}(N^{1-\epsilon})$ enumeration delay, the tuples in the Cartesian
product can be enumerated with the same delay using the Product algorithm
(Figure 16), since $m$ is independent of the database size $N$.

###  B.3 Proof of Proposition 3

######  Proposition 3.

Any free-connex hierarchical query has static width 1.

We first state two helping lemmas. The first lemma states that an atom that
does not contain a variable $X$ cannot cover more variables in
$\mathit{vars}(\mathit{atoms}(X))$ than an atom that contains $X$.

######  Lemma 34.

Let $X$ be a variable in a hierarchical query and
$R(\mathcal{Y})\in\mathit{atoms}(X)$. For all
$S(\mathcal{Z})\not\in\mathit{atoms}(X)$, it holds
$\mathcal{Z}\cap(\mathit{vars}(\mathit{atoms}(X))-\mathcal{Y})=\emptyset$.

###### Proof.

Let $Q$ be a hierarchical query, $X$ a variable in $Q$,
$R(\mathcal{Y})\in\mathit{atoms}(X)$, and $\omega$ a canonical variable order
for $Q$. Each variable $Y$ in $\mathit{vars}(\mathit{atoms}(X))$ that is not
included in $\mathcal{Y}$ must be below $X$ in $\omega$. Since $\omega$ is
canonical, such variables $Y$ can only be covered by atoms in
$\mathit{atoms}(X)$. This means that for all
$S(\mathcal{Z})\not\in\mathit{atoms}(X)$, it holds
$\mathcal{Z}\cap(\mathit{vars}(\mathit{atoms}(X))-\mathcal{Y})=\emptyset$. ∎

The next lemma states that all free variables under a bound variable in a
free-connex hierarchical query are covered by a single atom.

######  Lemma 35.

For any bound variable $X$ in a free-connex hierarchical query, there is an
atom $R(\mathcal{Y})\in\mathit{atoms}(X)$ with
$\mathit{free}(\mathit{atoms}(X))\subseteq\mathcal{Y}$.

###### Proof.

Let $Q(\mathcal{F})$ be a free-connex hierarchical query. For the sake of
contradiction, assume that $Q$ has a bound variable $X$ such that for any atom
$R(\mathcal{Y})\in\mathit{atoms}(X)$, it holds
$\mathit{free}(\mathit{atoms}(X))\not\subseteq\mathcal{Y}$. This means that
there are two atoms
$R_{1}(\mathcal{X}_{1}),R_{2}(\mathcal{X}_{2})\in\mathit{atoms}(X)$ and two
free variables $X_{1}\in\mathcal{X}_{1}$ and $X_{2}\in\mathcal{X}_{2}$ such
that both $X_{1}$ and $X_{2}$ are not covered by any atom in
$\mathit{atoms}(X)$. By Lemma 34, $Q$ cannot have any atom covering both
$X_{1}$ and $X_{2}$. We show that $Q$ cannot be free-connex, which contradicts
our initial assumption. Let $Q^{\prime}$ be the query that is obtained by
extending $Q$ with the atom $R_{3}(\mathcal{F})$, where $R_{3}$ is a relation
symbol that does not appear in $Q$. The query $Q$ is free-connex if and only
if $Q^{\prime}$ is $\alpha$-acyclic [14]. The query $Q^{\prime}$ is
$\alpha$-acyclic if and only if it has a (not necessarily free-top) variable
order with static width $1$ [45, 9]. Hence, it suffices to show that any
variable order for $Q^{\prime}$ has static width at least $2$.

Let $\omega$ be an arbitrary variable order for $Q^{\prime}$. The variables
$X$, $X_{1}$, and $X_{2}$ are mutually dependent in $Q^{\prime}$ and there is
no atom in $Q^{\prime}$ that covers all three variables. Due to their mutual
dependency, the three variables must be on the same root-to-leaf path in
$\omega$. Without loss of generality, assume that $X$ is the lowest of these
variables in $\omega$. It must hold
$\\{X_{1},X_{2}\\}\subseteq\textit{dep}_{\omega}(X)$. Since the three
variables $X$, $X_{1}$, and $X_{2}$ are not covered by a single atom,
$\rho_{Q^{\prime}}(\\{X,X_{1},X_{2}\\})$ is at least $2$. By Lemma 30,
$\rho_{Q^{\prime}}^{\ast}(\\{X_{1},X_{2},X_{3}\\})$ is at least $2$. Hence,
the static width of $\omega$ must be at least $2$. ∎

We are ready to prove Proposition 3. Let $Q$ be a free-connex query,
$\omega=(T_{\omega},\textit{dep}_{\omega})$ a canonical variable order for
$Q$, and