This article describes ,  a unified approach for maintaining analytics over changing relational data. We exemplify its versatility in four disciplines: processing queries with group-by aggregates and joins; learning linear regression models using the covariance matrix of the input features; building Chow-Liu trees using pairwise mutual information of the input features; and matrix chain multiplication.

has three main ingredients: higher-order incremental view maintenance; factorized computation; and ring abstraction. reduces the maintenance of a task to that of a hierarchy of simple views. Such views are functions mapping keys, which are tuples of input values, to payloads, which are elements from a ring. supports efficient factorized computation over keys, payloads, and updates. It treats uniformly seemingly disparate tasks: While in the key space, all tasks require general joins and variable marginalization, in the payload space, tasks differ in the definition of the sum and product ring operations.

We implemented on top of DBToaster and show that it can outperform classical first-order and fully recursive higher-order incremental view maintenance by orders of magnitude while using less memory.

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

§ INTRODUCTION

Supporting modern applications that rely on accurate and real-time analytics  computed over large and continuously evolving databases is a challenging data management problem [7]. Special cases are the classical problems of incremental view maintenance (IVM) [18, 33] and stream query processing [4, 37].

Recent efforts studied the problem of computing machine learning (ML) tasks over static databases. The predominant approach loosely integrates the database systems with the statistical packages [27, 57, 40, 56, 35]: First, the database system computes the input to the statistical package by joining the database relations. It then exports the join result to the statistical package for training ML models. This approach precludes real-time analytics due to the expensive export/import steps.
Systems like Morpheus [36] and LMFAO [61] push the ML task inside the database and learn ML models over static normalized data.
In particular, LMFAO, and its precursors F [60] and AC/DC [31], decompose the task of learning classification and regression models over arbitrary joins into factorized computation of aggregates over joins and fixpoint computation of model parameters. This factorization may significantly lower the complexity by avoiding the computation of Cartesian products lurking within joins [8, 54]. Both the tight integration of the database computation step and of the statistical computation step as well as the factorized computation are pre-requisites for real-time analytics.

This article describes [<https://github.com/fdbresearch/FIVM>.], a unified approach for maintaining analytics over changing relational data.  We exemplify its versatility in four disciplines: processing queries with group-by aggregates and joins; learning linear regression models using the covariance matrix of the input features; building Chow-Liu trees using pairwise mutual information matrix of the input features; and matrix chain multiplication.

was introduced in prior work [47]. This article revisits and extends this prior work with: a more refined analysis of for the $q$-hierarchical and free-connex acyclic  queries in the presence of functional dependencies; the covariance ring over continuous and categorical features; an overview of the design of ; further experiments on: the covariance matrix; end-to-end linear regression models; Chow-Liu trees; $q$-hierarchical queries with eager and lazy approaches and payloads carrying the listing or the factorized representation of the query result; and path queries of increasing length on graph data to stress-test the scalability of the IVM engines.

has three main ingredients: higher-order incremental view maintenance (IVM); factorized computation and data representation; and ring abstraction.

The first ingredient reduces the maintenance task to that of a hierarchy of simple views. Such views are functions mapping keys, which are tuples of input values, to payloads, which are elements from a ring. In contrast to classical (first-order) IVM, which computes changes to the query result on the fly and does not use extra views, can significantly speed up the maintenance task and lower its complexity by using carefully chosen views. Yet can use substantially fewer views than the fully-recursive IVM, which is used by the state-of-the-art IVM system DBToaster [33]. In our experiments, outperforms first-order and higher-order IVM by up to two orders of magnitude in both runtime and memory requirements.

The second ingredient supports efficient computation and representation for keys, payloads, and updates. exploits insights from query evaluation algorithms with best known complexity and optimizations that push aggregates past joins [8, 54, 6]. It can process bulk updates expressed as low-rank decompositions [34, 63] and maintain a factorized representation of query results, which is essential to achieve low complexity for free-connex acyclic and $q$-hierarchical queries.

The third ingredient allows to treat uniformly seemingly disparate tasks. In the key space, all tasks require joins and variable marginalization. In the payload space, tasks differ in the ring operations. To maintain linear regression models and Chow-Liu trees under updates, uses a new ring that captures the maintenance of a covariance matrix over continuous and categorical features from the input database. Furthermore, it composes rings to capture the data-dependent computation for complex analytics. Thanks to the ring abstraction, is highly extensible: efficient maintenance for new analytics over relational databases is readily available as long as they come with appropriate sum and product ring operations.

§.§ by Example

Consider the following SQL query over a database $\db$ with relations $R(A,B)$, $S(A,C,E)$, and $T(C,D)$:
[language=SQL, mathescape, columns=fullflexible]
Q := SELECT A,$\;$C,$\;$SUM(B$\,$*$\,$D$\,$*$\,$E)
$\,$FROM   R NATURAL$\;$JOIN S NATURAL$\;$JOIN T
$\,$GROUP$\;$BY A,$\;$C;

A naïve query evaluation approach first computes the join and then the aggregate. This takes $\bigO{N^3}$ time, where $N$ is the size of $\db$.
An alternative approach exploits the distributivity of SUM over multiplication to partially push the aggregate past joins and then combine the partial aggregates. For instance, one such partial sum over $S$ can be expressed as the view V$_\texttt{S}$:
[language=SQL, mathescape, columns=fullflexible]
V$_\texttt{S}$ := SELECT A,$\;$C,$\;$SUM(E)$\;$AS$\;$S$_\texttt{E}$
$\,$FROM S GROUP$\;$BY A,$\;$C;

In the view V$_\texttt{S}$, we identify keys, which are tuples over $(A,C)$, and payloads, which are aggregate values S$_\texttt{E}$.
Similarly, we compute partial sums over  and  as views V$_\texttt{R}$ and V$_\texttt{T}$. These views are joined as depicted by the view tree in Figure <ref>, which is akin to a query plan with aggregates pushed past joins. This view tree computes the result of $Q$ in $\bigO{N}$ time.

View tree for the query in Example <ref>. The propagation paths for updates to $S$ (right red) and to $T$ (left blue).

Consider now the problem of learning, for each pair $(a,c)$ of $(A,C)$-values in the natural join of $R$, $S$, and $T$, a linear function $f_{a,c}$ with parameters $\theta_{0}$, $\theta_{D}$ and $\theta_{E}$ that predicts the label $B$ given features $D$ and $E$:

\begin{align*}
f(D, E) = \theta_{0} + \theta_{D} \cdot D + \theta_{E} \cdot E
\end{align*}

Our insight is that the same view tree in Figure <ref> can compute the gradient vector used for learning $f_{a,c}$, where we replace the SQL  and  operators.

As shown in Section <ref>, the gradient of the square loss objective function needs the computation of three types of aggregates: the scalar $\LRringC$ that is the count aggregate ; the vector $\LRringS$ of linear aggregates , for $i\in\{\texttt{B},\texttt{D},\texttt{E}\}$; and the matrix $\LRringQ$ of quadratic aggregates , where $i,j\in\{\texttt{B},\texttt{D},\texttt{E}\}$. These aggregates capture the correlation between the features and the label.

We treat these aggregates as one compound aggregate $(\LRringC,\LRringS,\LRringQ)$ so we can share computation across them. This compound aggregate can be partially pushed past joins similarly to the  aggregate discussed before. Its values are carried in the key payloads of views in the view tree from Figure <ref>. For instance, the partial compound aggregate $(\LRringC_\texttt{T},\LRringS_\texttt{T},\LRringQ_\texttt{T})$ at the view V$_\texttt{T}$ computes, for each $C$-value, the count, sum, and sum of squares of the $D$-values in $T$. Similarly, the partial aggregate $(\LRringC_\texttt{S},\LRringS_\texttt{S},\LRringQ_\texttt{S})$ at the view V$_\texttt{S}$ computes, for each pair $(A,C)$, the count, sum, and sum of squares of $E$-values in $S$. In the view V$_\texttt{ST}$, which is the join of V$_\texttt{T}$ and V$_\texttt{S}$, each key $(a,c)$ is associated with the multiplication of the payloads for the keys $c$ in V$_\texttt{T}$ and $(a,c)$ in V$_\texttt{S}$. This multiplication works on compound aggregates: The scalar $\LRringC_\texttt{ST}$ is the arithmetic multiplication of $\LRringC_\texttt{T}$ and $\LRringC_\texttt{S}$; the vector of linear aggregates $\LRringS_\texttt{ST}$ is the sum of the scalar-vector products $\LRringC_\texttt{T}\LRringS_\texttt{S}$ and $\LRringC_\texttt{S}\LRringS_\texttt{T}$; finally, the matrix
$\LRringQ_\texttt{ST}$ of quadratic aggregates is the sum of the scalar-matrix products $\LRringC_\texttt{T}\LRringQ_\texttt{S}$ and $\LRringC_\texttt{S}\LRringQ_\texttt{T}$, and of the outer products of the vectors $\LRringS_\texttt{T}$ and the transpose of $\LRringS_\texttt{S}$ and also of $\LRringS_\texttt{S}$ and the transpose of $\LRringS_\texttt{T}$. Our approach shares the computation across the aggregates: The scalar aggregates are used to scale up the linear and quadratic aggregates, while the linear aggregates are used to compute the quadratic aggregates.

We now turn to incremental view maintenance. operates over view trees. Whereas for non-incremental computation we only materialize the top view in the tree and the input relations, for incremental computation we may materialize additional views to speed up the maintenance task. Our approach is an instance of higher-order IVM, where an update to one relation may trigger the maintenance of several views.

Figure <ref> shows the leaf-to-root maintenance paths under changes to $\texttt{S}$ and $\texttt{T}$. For updates $\delta{\texttt{S}}$ to $\texttt{S}$, each delta view $\delta{V_\texttt{S}}$, $\delta{V_\texttt{ST}}$, and $\delta{\texttt{Q}}$, is computed using delta rules:

[language=SQL, mathescape, columns=flexible]
$\delta$V$_\texttt{S}$ := $\,$SELECT A,$\;$C,$\;$SUM(E)$\;$AS$\;$S$_\texttt{E}$
$\,\,$FROM $\delta$S GROUP$\;$BY A,$\;$C;
$\;\;\delta$V$_\texttt{ST}\,$:= SELECT A,$\;$C,$\;$SUM(S$_\texttt{D}$$\,$*$\,$S$_\texttt{E}$)$\;$AS$\;$S$_\texttt{C}$
$\,\,$FROM V$_\texttt{T}$ NATURAL JOIN $\delta$V$_\texttt{S}$ GROUP$\;$BY A,$\;$C;
$\delta$Q := SELECT A,$\;$C,$\;$SUM(S$_\texttt{B}$$\,$*$\,$S$_\texttt{C}$)
$\,\,$FROM V$_\texttt{R}$ NATURAL JOIN $\delta$V$_\texttt{ST}$ GROUP$\;$BY A,$\;$C;

An update may consist of both inserts and deletes, which are encoded as keys with positive and respectively negative payloads. For the count aggregate, the payload is $1$ for an insert and
$-1$ for a delete. For the compound aggregate, the payload is $(1, {\bf 0}_{5 \times 1}, {\bf 0}_{5 \times 5})$ for an insert and $(-1, {\bf 0}_{5 \times 1}, {\bf 0}_{5 \times 5})$ for a delete, where ${\bf 0}_{n \times m}$ is the $n$-by-$m$ matrix with all zero values.

materializes and maintains views depending on the update workload. For updates to all input relations, it materializes each view in the view tree. For updates to  only, it materializes V$_\texttt{ST}$; for updates to  only, it materializes V$_\texttt{R}$ and V$_\texttt{T}$; for updates to  only, it materializes  V$_\texttt{R}$ and V$_\texttt{S}$. takes constant time for updates to  and linear time for updates to  and ; these complexities are in the number of distinct keys in the views.
In contrast, the first-order IVM computes one delta query per each updated relation and without the use of extra views. It takes linear time for updates to any of the three relations for our example query. The fully-recursive higher-order IVM constructs a view tree for each delta query, so overall more views, including the view materializing the join of V$_\texttt{R}$, V$_\texttt{S}$, and $\delta{\texttt{T}}$.

thus needs the same view tree and views for our query with one SUM aggregate and even for the learning task with the ten SUM aggregates. In contrast, the first-order IVM needs to compute a distinct delta query for each of these aggregates for updates to any of the three relations. DBToaster, which is the state-of-the-art fully recursive IVM, computes 31 views, ten top views and 21 auxiliary ones. Whereas shares the computation across these aggregates, the other IVM approaches do not. This significantly widens the performance gap between and its competitors.

§ OVERVIEW OF THE SYSTEM

Overview of the system.

Figure <ref> overviews the main components of , annotated with the numbers of sections where they are discussed. Applications, e.g., database analytics,  training linear regression model and Chow-Liu trees, and linear algebra computation, rely on queries with natural joins and group-by aggregates, where each aggregate is expressed using the sum and product operations in a ring. In particular, Section <ref> introduces the covariance ring over continuous and categorical features. Queries and rings serve as input to , together with a stream of updates (tuple inserts and deletes) to the underlying database. Section <ref> details the data model, the query language supported by , and the ring algebraic structure.

The logical optimizer creates a variable order for the input query (Section <ref>). This is akin to a query plan, albeit expressed as a partial order on the query variables as opposed to a partial order on the relations to join. Classical query evaluation uses query plans that dictate the order in which the relations are joined. uses variable orders that dictate the  order in which the variables are marginalized.
For each join variable, all relations with that variable are joined. This choice is motivated by the observation that relation-at-a-time query plans is suboptimal in general, whereas the evaluation by variable orders is worst-case optimal [43].

Finding a good variable order for a given query is a computationally hard problem. For q-hierarchical queries [12], we can efficiently find variable orders  that allow for maintenance with best guarantees in terms of update time and time to present the updated query result to the user (Section <ref>).
This also applies to queries, which become  q-hierarchical on databases that satisfy functional dependencies.

Given a variable order for a query, the physical optimizer creates a view tree (Section <ref>), which is a tree of views to support the maintenance and output enumeration of the query. Updates to base relations are propagated bottom-up in the tree, while output enumeration requires top-down access in the view tree. Depending on which base relations are updatable (dynamic) or non-updatable (static), decides to materialize and maintain views in the view tree to support efficient propagation of the updates and avoid recomputation. Section <ref> discusses the view materialization problem, whereas Section <ref> discusses efficient update propagation.

Each view is accessed via indices with key-payload entries. Its primary index is a hash map over all its keys (Section <ref>). may also need secondary and even tertiary indices, which are hash maps over different subsets of its keys.

Such indices are updated lazily: the index updates are buffered and only executed when index access is required.
The views for q-hierarchical queries require the primary indices to support updates that are propagated bottom-up in the view tree, and secondary indices to support output enumeration that proceeds top-down in the view tree (Section <ref>).
implements equality-based joins using in-memory hash-based join operators.
Aggregation is performed using variable marginalization. To marginalize a variable,
enumerates the entries with the same key, except for the marginalized variable, and applies the aggregation on these entries on the fly.

For a view tree and ring specification for each variable to be marginalized, the compiler outputs code in  DBToaster's intermediate representation language M3. DBToaster has its own optimizer and compiler that turns M3 code into highly optimized C++ code. This code takes the stream of input data updates, maintains the views, and enumerates the query output, relying on DBToaster's runtime library for data ingestion.

§ DATA MODEL AND QUERY LANGUAGE

The data model of is based on relations over rings and its query language allows for natural joins and group-by aggregates over such relations.

A ring $(\RING, \RINGPLUS, \RINGPROD, \RINGZERO, \RINGONE)$ is a set $\RING$ with two closed binary operations $\RINGPLUS$ and $\RINGPROD$, the additive identity $\RINGZERO$, and the multiplicative identity $\RINGONE$ such that for all $a,b,c\in\RING$, the following
axioms are satisfied:

* $a \RINGPLUS b = b\RINGPLUS a$.

* $(a \RINGPLUS b)\RINGPLUS c = a \RINGPLUS (b \RINGPLUS c)$.

* $\RINGZERO \RINGPLUS a = a \RINGPLUS \RINGZERO = a$.

* $\exists -a \in \RING: a \RINGPLUS (-a) = (-a) \RINGPLUS a = \RINGZERO$.

* $(a \RINGPROD b) \RINGPROD c = a \RINGPROD (b \RINGPROD c)$.

* $a \RINGPROD \RINGONE = \RINGONE * a = a$.

* $a \RINGPROD (b \RINGPLUS c) = a \RINGPROD b \RINGPLUS a \RINGPROD c$ and $(a \RINGPLUS b) \RINGPROD c = a \RINGPROD c \RINGPLUS b \RINGPROD c$.

A semiring $(\RING, \RINGPLUS, \RINGPROD, \RINGZERO, \RINGONE)$ satisfies all of the above properties
except the additive inverse property (Property 4) and adds the axiom
$\RINGZERO \RINGPROD a = a \RINGPROD \RINGZERO = \RINGZERO$.
A (semi)ring for which $a \RINGPROD b = b \RINGPROD a$ is commutative.

The number sets $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ with arithmetic operations $+$ and $\cdot$ and numbers $0$ and $1$ form commutative rings. The set $\mathcal{M}$ of $(n \times n)$ matrices  forms a non-commutative ring $(\mathcal{M}, \cdot, +, 0_{n,n}, I_{n})$, where $0_{n,n}$ and $I_{n}$ are the zero matrix and the identity matrix of size $(n \times n)$. The set $\mathbb{N}$ of natural numbers  is a commutative semiring but not a ring because it has no additive inverse. Further examples are the max-product semiring $(\mathbb{R}_{+}, \max, \times, 0, 1)$, the Boolean semiring $(\{ \text{true}, \text{false} \}, \lor, \land, \text{false}, \text{true})$,  and the set semiring $(2^{U}, \cup, \cap, \emptyset, U)$ of all possible subsets of a given set $U$.

A schema $\mathcal{S}$ is a set of variables. Let $\Dom(X)$ denote the domain of a variable $X$. A tuple $\vecnormal{t}$ over schema $\mathcal{S}$ has the domain $\Dom(\mathcal{S}) = \prod_{X \in \mathcal{S}}{\Dom(X)}$. The empty tuple $\tuple{}$ is the tuple over the empty schema.

Let $(\RING,\hspace{-0.05em} \RINGPLUS,\hspace{-0.05em} \RINGPROD,\hspace{-0.05em} \RINGZERO,\hspace{-0.05em} \RINGONE)$ be a ring. A relation $\VIEW{R}$ over schema $\mathcal{S}$ and the ring $\RING$ is a function $\VIEW{R}: \Dom(\mathcal{S}) \to \Codom$ mapping tuples over schema $\mathcal{S}$ to values in $\Codom$ such that $\VIEW{R}[\vecnormal{t}] \neq \RINGZERO$ for finitely many tuples $\vecnormal{t}$. The tuple $\vecnormal{t}$ is called a key, while its mapping $\VIEW{R}[\vecnormal{t}]$ is the payload of $\vecnormal{t}$ in $\VIEW{R}$. We use $\sch(\VIEW{R})$ to denote the schema of $\VIEW{R}$.
The statement $\vecnormal{t} \in \VIEW{R}$ tests if $\VIEW{R}[\vecnormal{t}] \neq \RINGZERO$. The size $|\VIEW{R}|$ of $\VIEW{R}$ is the size of the set $\{ \vecnormal{t} \mid \vecnormal{t} \in \VIEW{R} \}$, which consists of all keys with non-$\RINGZERO$ payloads.
A database $\db$ is a collection of relations over the same ring. Its size $|\db|$ is the sum of the sizes of its relations.
This data model is in line with prior work on $K$-relations over provenance semirings [25], generalized multiset relations [32], and factors over semirings [6].

Each relation  or materialized view $\VIEW{R}$  over schema $\mathcal{S}$ is implemented
as a hash map or a multidimensional array that stores
key-payload entries $(\vecnormal{t},\VIEW{R}[\vecnormal{t}])$ for each tuple
$\vecnormal{t}$ with $\VIEW{R}[\vecnormal{t}] \neq \RINGZERO$.

The data structure can:
(1) look up, insert, and delete entries in amortized constant time, and
(2) enumerate all stored entries in $\VIEW{R}$
with constant delay, i.e., the following times are constant:
(i) the time between the start of the enumeration and outputting the first tuple, (ii) the time between outputting any two consecutive tuples, and (iii) the time between outputting the last tuple and the end of the enumeration [21].
For a schema $\mathcal{X} \subset \mathcal{S}$,
we use an index data structure that for any $\vecnormal{t} \in \Dom(\mathcal{X})$ can:
(4) enumerate all tuples in $\sigma_{\mathcal{X}=\vecnormal{t}} \VIEW{R}$ with constant delay,
(5) check $\vecnormal{t} \in \pi_{\mathcal{X}}\VIEW{R}$ in amortized constant time; and
(7) insert and delete index entries in amortized constant time.

We give a hash-based example data structure that supports the above operations with the stated complexities.
Consider a relation $R$ over schema $\mathcal{S}$.
A hash table with chaining stores key-value entries of the form $(\vecnormal{t},R(\vecnormal{t}))$ for each tuple $\vecnormal{t}$ over $\mathcal{S}$ with
$R(\vecnormal{t}) \neq \RINGZERO$.
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 amortized constant time.

To support index operations on a schema $\mathcal{X} \subset \mathcal{S}$,
we create another hash table with chaining where each table entry stores an $\calX$-value
$\vecnormal{t}$ as key and a doubly-linked list of pointers to the entries in $R$ having
$\vecnormal{t}$ as $\mathcal{X}$-value.
Looking up an index entry given $\vecnormal{t}$ takes amortized constant time,

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 $\vecnormal{t}$; overall, this operation takes amortized constant time.
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.

Query Language.
We consider queries with natural joins and group-by aggregates:
SELECT$\;X_1,\ldots,X_f$,$\;$SUM$(g_{f+1}(X_{f+1}) * ... * g_{m}(X_{m}))$
FROM $R_1$ NATURAL$\;$JOIN $\ldots$ NATURAL$\;$JOIN $R_n$
GROUP$\;$BY $X_1,\ldots,X_f$

The group-by variables $X_1,\ldots,X_f$ are free, while the other variables $X_{f+1},\ldots,X_m$ are bound. The SUM aggregate values are from a ring $(\RING, \RINGPLUS, \RINGPROD, \RINGZERO, \RINGONE)$. The  operator uses the addition
$\RINGPLUS$ from $\RING$. Further aggregates can be expressed using the sum and product operations from the ring.
A lifting function $g_{k}: \Dom(X_k) \to \RING$, for $f < k \leq m$, maps $X_k$-values to elements in $\RING$:
when marginalizing $X_k$,  we aggregate the values $g_{k}(x)$ from $\RING$ and not the values $x$ from $\Dom(X_k)$.

Instead of the verbose SQL notation, we use the following more compact encoding:

\begin{align*}
\qquad  \VIEW[X_1,\ldots,X_f]{Q} = \VSUM_{X_{f+1}} \cdots \VSUM_{X_{m}} \VPRODBIG_{i \in [n]} \VIEW[\mathcal{S}_i]{R_i}
\end{align*}

where $\VPRODBIG$ is the join operator, $\VSUM_{X_{f+1}}$ is the aggregation operator that  marginalizes over the variable $X_{f+1}$, and each relation $\VIEW{R_i}$ is a function mapping keys over schema $\mathcal{S}_i$ to payloads in $\RING$. We also need a union operator $\VPLUS$ to express updates (insert/delete) to relations.

The SQL query
SELECT SUM(1) FROM R NATURAL JOIN S NATURAL JOIN T

over tables $R(A,B)$, $S(A,C,E)$, and $T(C,D)$ can be encoded as follows in our formalism.
The table $R$ is encoded as a relation $\VIEW{R}: \Dom(A) \times \Dom(B) \to \mathbb{Z}$ that maps tuples $(a,b)$ to their multiplicity in $R$; similarly, we encode the tables $S$ and $T$ as relations $\VIEW{S}$ and $\VIEW{T}$. We translate the SQL query into:

\VIEW[~]{Q} = \underset{A,B,C,D,E}{\VSUM} \VIEW[A,B]{R}  \VPROD \VIEW[A,C,E]{S} \VPROD \VIEW[C,D]{T}
%  \VIEW[~]{Q} = \VSUM_{A}\VSUM_{B}\VSUM_{C}\VSUM_{D}\VSUM_{E} \VIEW[A,B]{R} \VPROD \VIEW[A,C,E]{S} \VPROD \VIEW[C,D]{T}

where $\underset{A,B,C,D,E}{\VSUM}$ abbreviates $\VSUM_A \cdots \VSUM_E$. The lifting functions used for marginalization map all values to $1$.
Recall that by definition $\VIEW{R}$, $\VIEW{S}$, and $\VIEW{T}$ are finite.
The relation $\VIEW{Q}$ maps the empty tuple $()$ to the count.

Given a ring $(\RING, \RINGPLUS, \RINGPROD, \RINGZERO, \RINGONE)$, relations $\VIEW{R}$ and $\VIEW{S}$ over schema $\mathcal{S}_1$ and relation $\VIEW{T}$ over schema $\mathcal{S}_2$, a variable $X \in \mathcal{S}_1$, and a lifting function $g_{X}:\Dom(X) \to \RING$, we define the three operators as follows:

4@ lunion:

$\forall\vecnormal{t} \in \mathsf{D}_1{:}$
$(\VIEW{R} \VPLUS \VIEW{S})[\vecnormal{t}]$
$= \VIEW{R}[\vecnormal{t}] + \VIEW{S}[\vecnormal{t}]$

4@ ljoin:

$\forall\vecnormal{t} \in \mathsf{D}_2{:}$
$(\VIEW{S} \VPROD \VIEW{T})[\vecnormal{t}]$
$= \VIEW{S}[\pi_{\mathcal{S}_1}(\vecnormal{t})] * \VIEW{T}[\pi_{\mathcal{S}_2}(\vecnormal{t})]$

4@ laggregation by marginalization:

$\forall\vecnormal{t} \in \mathsf{D}_3{:}$
$(\VSUM_{X} \VIEW{R})[\vecnormal{t}]$
$= \textstyle\sum \,\{\, \VIEW{R}[\vecnormal{t}_1] \,\RINGPROD\, g_{X}(\pi_{\{X\}}(\vecnormal{t}_1)) \mid$
$\vecnormal{t}_1 \,{\in}\, \mathsf{D}_1, \vecnormal{t} = \pi_{\mathcal{S}_1 \setminus \{X\}}(\vecnormal{t}_1) \}$

where $\mathsf{D}_1 = \Dom(\mathcal{S}_1)$, $\mathsf{D}_2 = \Dom(\mathcal{S}_1 \cup \mathcal{S}_2)$, and $\mathsf{D}_3 = \Dom(\mathcal{S}_1 \setminus \{X\})$, and $\pi_{\mathcal{S}}(\vecnormal{t})$ is a tuple representing the projection of tuple $\vecnormal{t}$ on the schema $\mathcal{S}$.

Consider relations over a ring $(\RING,\hspace{-0.05em} \RINGPLUS,\hspace{-0.05em} \RINGPROD,\hspace{-0.05em} \RINGZERO,\hspace{-0.05em} \RINGONE)$:

t]@ l@ l@ $\to$ l@
$A$     $B$     $\VIEW{R}[A,B]$
$a_1$     $b_1$     $r_1$

$a_2$     $b_1$     $r_2$

t]@ l@ l@ l@ l@
A     B     $\to$     $\VIEW[A,B]{S}$
$a_2$     $b_1$     $\to$     $s_1$

$a_3$     $b_2$     $\to$     $s_2$

t]@ l@ l@ l@ l@
B     C     $\to$     $\VIEW[B,C]{T}$
$b_1$     $c_1$     $\to$     $t_1$

$b_2$     $c_2$     $\to$     $t_2$

The values $r_1$, $r_2$, $s_1$, $s_2$, $t_1$, $t_2$ are non-$\RINGZERO$ values from $\RING$.
The operators $\VPLUS$, $\VPROD$, and $\oplus$ are akin to union, join, and aggregation ($g_A:\hspace{-0.1em} \Dom(A) \hspace{-0.1em}\to\hspace{-0.1em} \RING$ is the lifting for $A$):

t]@ l@ l@ l@ l@
$A$     $B$     $\to$     $(\VIEW{R} \VPLUS \VIEW{S})[A,B]$
$a_1$     $b_1$     $\to$     $r_1$

$a_2$     $b_1$     $\to$     $r_2+s_1$

$a_3$     $b_2$     $\to$     $s_2$

t]@ l@ l@ l@ l@ l@
$A$     $B$     $C$     $\to$     $\big((\VIEW{R} \VPLUS \VIEW{S}) \VPROD \VIEW{T}\big)[A,B,C]$
$a_1$     $b_1$     $c_1$     $\to$     $r_1*t_1$

$a_2$     $b_1$     $c_1$     $\to$     $(r_2 + s_1)*t_1$

$a_3$     $b_2$     $c_2$     $\to$     $s_2*t_2$

t]@ l@ l@ l@ l@
$B$     $C$     $\to$     $\big(\VSUM_{A}(\VIEW{R} \VPLUS \VIEW{S}) \VPROD \VIEW{T} \big)[B,C]$
$b_1$     $c_1$     $\to$     $r_1 * t_1  \,*\, g_{A}(a_1) + (r_2 + s_1) * t_1  \,*\, g_{A}(a_2)$

$b_2$     $c_2$     $\to$     $s_2 * t_2 \,*\, g_{A}(a_3)$

Let us consider the SQL query from Section <ref>, which computes  grouped by $A$, $C$. Assume that $B$, $D$, and $E$ take values from $\mathbb{Z}$.
We model the tables $R$, $S$, and $T$ as relations mapping tuples to their multiplicity, as in
Example <ref>.
The variables $A$ and $C$ are free, while  $B$, $D$, and $E$ are bound.

When marginalizing over the bound variables, we apply the same lifting function to these variables: $\forall x \in \mathbb{Z}: g_{B}(x) = g_{D}(x) = g_{E}(x) = x$. The SQL query can be expressed in our formalism as follows:

\VIEW[A,C]{Q} = \underset{B,D,E}{\VSUM}\VIEW[A,B]{R} \VPROD \VIEW[A,C,E]{S} \VPROD \VIEW[C,D]{T}

The computation of the aggregate  now happens over payloads.

By using relations over rings, we avoid the intricacies of incremental computation under multiset semantics caused by the non-commutativity of inserts and deletes. We simplify delta processing by representing both inserts and deletes as tuples, with the distinction that they map to positive and respectively negative ring values. This uniform treatment allows for simple delta rules for the three operators of our query language.

§ FACTORIZED RING COMPUTATION

This section introduces a framework for query evaluation  based on factorized computation and data rings. The next section extends it to incremental maintenance.

[xscale=0.96, yscale=0.8]
at (0, 0.0) (A) $A$;
at (-0.4, -1.0) (B) $B$ edge[-] (A);
at (0.4, -1.0) (C) $C$ edge[-] (A);
at (0.8, -2.0) (E) $E$ edge[-] (C);
at (0, -2.0) (D) $D$ edge[-] (C);
at (0.8, -2.6) (S) $S$;
at (-0.6, -1.55) (R) $R$;
at (-0.1, -2.6) (T) $T$;
at (2.55, -1.6)

$dep(A) = \emptyset$

[opacity=.4,fill opacity=.4,line cap=round, line join=round, line width=15pt,color=teal] (0,0.0) – (-0.4,-1);
[opacity=.5,fill opacity=.5,line cap=round, line join=round, line width=18pt,color=orange] (0,0.0) – (0.8,-2.0);
[opacity=.4,fill opacity=.4,line cap=round, line join=round, line width=15pt,color=purple]  (0.4,-1) – (0, -2.0);

[xscale=0.7, yscale=0.8]
at (0, 0) (A) $\VIEW[~]{V^{@A}_{RST}}$;
at (-1.6, -1) (B) $\VIEW[A]{V^{@B}_{R}}$ edge[-] (A);
at (1.6, -1) (C) $\VIEW[A]{V^{@C}_{ST}}$ edge[-] (A);
at (0.6, -2) (D) $\VIEW[C]{V^{@D}_{T}}$ edge[-] (C);
at (2.9, -2) (E) $\VIEW[A,C]{V^{@E}_{S}}$ edge[-] (C);

at (-1.6, -2) $\VIEW[A,B]{R}$ edge[-] (B);
at (2.9, -3) $\VIEW[A,C,E]{S}$ edge[-] (E);
at (0.6, -3) $\VIEW[C,D]{T}$ edge[-] (D);

at (0.5, -4.5) ;

\begin{align*}
&\VIEW[A,C]{V^{@E}_{S}} = \VSUM_{E} \VIEW[A,C,E]{S} \\[2pt]
&\VIEW[C]{V^{@D}_{T}} = \VSUM_{D} \VIEW[C,D]{T} \\[2pt]
&\VIEW[~]{V^{@A}_{RST}} = \VSUM_{A} \big(\VIEW[A]{V^{@B}_{R}} \VPROD \VIEW[A]{V^{@C}_{ST}}\big) \\[2pt]
&\VIEW[A]{V^{@B}_{R}} = \VSUM_{B} \VIEW[A,B]{R} \\[2pt]
&\VIEW[A]{V^{@C}_{ST}} = \VSUM_{C} \big(\VIEW[C]{V^{@D}_{T}} \VPROD \VIEW[A,C]{V^{@E}_{S}}\big)
\\[0.5cm]
\end{align*}

(left) Variable order $\omega$ of the natural join of the relations $\VIEW[A,B]{R}$, $\VIEW[A,C,E]{S}$, and $\VIEW[C,D]{T}$; (middle) View tree over $\omega$ and $\mathcal{F} = \emptyset$;
(right)  View definitions.

Variable Orders.
Classical query evaluation makes use of  query plans that dictate the order in which the relations are joined. We use a different evaluation approach based on variable orders that dictate the  order in which we marginalize each join variable. This approach may require to join several relations at a time if they have the same variable. Our choice is motivated by the complexity of the evaluation problem for join queries: standard (relation-at-a-time) query plans are provably suboptimal, whereas the evaluation by variable orders can be worst-case optimal [43].

Given a join query $Q$, a variable $X$ depends on a variable $Y$ if both are in the schema of a relation in $Q$.

A variable order $\omega$ for a join query $Q$ is a pair $(F,dep)$, where $F$ is a rooted forest with one node per variable in $Q$, and dep is a function mapping each variable $X$ to a set of variables in $F$. It satisfies the following constraints:

* For each relation in $Q$, all of its variables lie along a root-to-leaf path in $F$.

* For each variable $X$, $dep(X)$ is the subset of its ancestors in $F$ on which the variables in the subtree rooted at $X$ depend.

Consider the query

from Example <ref> that joins the relations $\VIEW{R}[A,B]$, $\VIEW[A,C,E]{S}$, and
Figure <ref>  gives a variable order (top left) for
the query.
Variable $D$ has ancestors $A$ and $C$, yet it only depends on $C$ since $C$ and $D$ appear in the same relation $\VIEW[]{T}$ and $D$ does not occur in any relation together with $A$. Thus, $dep(D)=\{C\}$. Given $C$, the variables $D$ and $E$ are independent of each other.

For a query $Q$ with free variables, a variable order is free-top if no bound variable is an ancestor of a free variable [29]. Variable orders are a different syntax [54] for hypertree decompositions [24]. They are more natural for algorithms that proceed one variable at a time.

View Trees. Our framework relies on a variable order $\omega$ for the input query $Q$ to describe the structure of the computation and indicate which variable marginalizations are pushed past joins. Based on $\omega$, we construct a tree of views that represent 's data structure to support query maintenance and enumeration.

3c$\tau$(variable order $\omega$, free variables $\mathcal{F}$) : view tree

a     $\VIEW{R}$     $\VIEW[\mathit{\sch(\VIEW{R})}]{R}$

[xscale=0.4, yscale=1]
at (0,-2)  (n4) $X$;
at (-1,-3)  (n1) $\omega_1$ edge[-] (n4);
at (0,-3)  (n2) $\ldots$;
at (1,-3)  (n3) $\omega_k$ edge[-] (n4);
at (0,-4.5)  ;

$T_i = \tau(\omega_i, \mathcal{F}), \ \forall i\in[k] $

$\VIEW[\mathit{keys_i}]{V^{@\omega_i}_{rels_i}} = \text{ root of } T_i, \ \forall i\in[k] $

$\mathit{keys}=\mathit{dep}(X) \cup (\mathcal{F} \cap \vars(\omega))$

$X \notin \mathcal{F}$

$\VIEW[\mathit{keys}]{V^{@X}_{rels}}= \VSUM_{X} \VPRODBIG_{i \in [k]} \VIEW[\mathit{keys_i}]{V^{@\omega_i}_{rels_i}}$

$\VIEW[\mathit{keys}]{V^{@X}_{rels}}=\VPRODBIG_{i \in [k]} \VIEW[\mathit{keys_i}]{V^{@\omega_i}_{rels_i}}$

\left\{
\begin{array}{@{~~}c@{~~}}
\tikz {
\node at (1.2,-1)  (n4) {$\VIEW[\mathit{keys}]{V^{@X}_{rels}}$};
\node at (0.8,-1.75)  (n1) {$T_1$} edge[-] (n4);
\node at (1.25,-1.75)  (n2) {$\ldots$};
\node at (1.8,-1.75)  (n3) {$T_k$} edge[-] (n4);
\end{array}  \right.$

Creating a view tree $\tau(\omega, \mathcal{F})$ for a variable order $\omega$ and a set of free variables $\mathcal{F}$.

Figure <ref> gives a function $\tau$ that constructs a view tree $\tau$ for a variable order $\omega$ and the set $\mathcal{F}$ of free variables of the query $Q$. Without loss of generality, we assume that $\omega$ is a single rooted tree. Otherwise, we apply $\tau$  to each tree in $\omega$ to obtain a set of view trees.
For simplicity, we assume that $\omega$ was first extended with relations as children under their lowest variable.

The function  $\tau$ maps the variable order to a view tree of the same tree structure, yet with each variable $X$ replaced by a view $\VIEW[keys]{V^{@X}_{rels}}$. This notation states that the view $\VIEW{V}$ is (recursively) defined over the input relations rels, has free variables $keys$, and it corresponds to the variable $X$ in $\omega$; in case of a view for an input relation $\VIEW{R}$, we use the simplified notation $\VIEW[\sch(\VIEW{R})]{R}$.

The base case (leaf in the extended variable order) is that of an input relation: We construct a view that is the relation itself. At a variable $X$ (inner node), we distinguish two cases: If $X$ is a bound variable, then we construct a view that marginalizes out $X$ in the natural join of the views that are children of the current view; we thus first join on $X$, then apply the lifting function for $X$ on its values, and aggregate $X$ away. If $X$ is a free variable, however, then we retain it in the view schema without applying the lifting function to its values. The schema of the view consists of $dep(X)$ and the free variables in the subtree of $\omega$ rooted at $X$.

at (0, 0.5) (x)

[xscale=0.8, yscale=0.24]
at (0, -1.5) (A) $\VIEW[A,C]{V^{@A}_{RST}}$;
at (-1.5, -5) (B) $\VIEW[A]{V^{@B}_{R}}$ edge[-] (A);
at (1.5, -5) (C) $\VIEW[A,C]{V^{@C}_{ST}}$ edge[-] (A);
at (0.5, -9) (D) $\VIEW[C]{V^{@D}_{T}}$ edge[-] (C);
at (2.5, -9) (E) $\VIEW[A,C]{V^{@E}_{S}}$ edge[-] (C);

at (-1.5, -8) $\VIEW[A,B]{R}$ edge[-] (B);
at (2.5, -12) $\VIEW[A,C,E]{S}$ edge[-] (E);
at (0.5, -12) $\VIEW[C,D]{T}$ edge[-] (D);

at (8.2, 0.5) (x)

\begin{align*}
&\VIEW[A,C]{V^{@A}_{RST}} = \VIEW[A]{V^{@B}_{R}} \VPROD \VIEW[A,C]{V^{@C}_{ST}} \\[2pt]
&\VIEW[A,C]{V^{@C}_{ST}} = \VIEW[C]{V^{@D}_{T}} \VPROD \VIEW[A,C]{V^{@E}_{S}} \\[2pt]
&\VIEW[A,C]{V^{@E}_{S}} = \VSUM_{E} \VIEW[A,C,E]{S} \\[2pt]
&\VIEW[A]{V^{@B}_{R}} =  \VSUM_{B}\VIEW[A,B]{R} \\[2pt]
&\VIEW[C]{V^{@D}_{T}} =  \VSUM_{D}\VIEW[C,D]{T}
\end{align*}

(left) View tree over the variable order $\omega$ in Figure <ref> and
$\mathcal{F} = \{A,C\}$; (right) View definitions.

[xscale=0.75, yscale=0.35]

at (2, 0)

$()$     $\rightarrow$      $\VIEW[\;]{V^{@A}_{RST}}$
$()$     $\rightarrow$
$\VIEW{V^{@C}_{ST}}[a_1] \RINGPROD \VIEW{V^{@B}_{R}}[a_1] \RINGPROD g_A(a_1) \RINGPLUS \VIEW{V^{@C}_{ST}}[a_2] \RINGPROD \VIEW{V^{@B}_{R}}[a_2] \RINGPROD g_A(a_2) $

[anchor=north west] at (-7, -2.5)

$A$     $\to$     $\VIEW[A]{V^{@B}_{R}}$
$a_1$     $\rightarrow$     $p_{1} \RINGPROD  g_B(b_1)  + p_{2} \RINGPROD  g_B(b_2)$

$a_2$     $\rightarrow$     $p_{3} \RINGPROD  g_B(b_3)$

$a_3$     $\rightarrow$     $p_{4} \RINGPROD  g_B(b_4)$

[anchor=north west] at (-7, -9)

$A$     $B$     $\VIEW{R}[A,B]$
$a_1$     $b_1$     $p_1$

$a_1$     $b_2$     $p_2$

$a_2$     $b_3$     $p_3$

$a_3$     $b_4$     $p_4$

[anchor=north west] at (1, -2.5)

$A$     $\rightarrow$     $\VIEW[A]{V^{@C}_{ST}}$
$a_1$     $\rightarrow$
$\VIEW{V^{@E}_{S}}[a_1,c_1] \RINGPROD \VIEW{V^{@D}_{T}}[c_1] \RINGPROD g_C(c_1) +
\VIEW{V^{@E}_{S}}[a_1,c_2] \RINGPROD \VIEW{V^{@D}_{T}}[c_2] \RINGPROD g_C(c_2)$

$a_2$     $\rightarrow$     $\VIEW{V^{@E}_{S}}[a_2,c_2] \RINGPROD \VIEW{V^{@D}_{T}}[c_2] \RINGPROD g_C(c_2)$

[anchor=north west] at (1, -8)

$C$     $\to$     $\VIEW[C]{V^{@D}_{T}}$
$c_1$     $\rightarrow$     $ p_9 \RINGPROD g_D(d_1)$

$c_2$     $\rightarrow$     $p_{10} \RINGPROD  g_D(d_2)  + p_{11} \RINGPROD  g_D(d_3)$

$c_3$     $\rightarrow$     $p_{12} \RINGPROD  g_D(d_4)$

[anchor=north west] at (8, -8)

$A$     $C$     $\to$     $\VIEW[A,C]{V^{@E}_{S}}$
$a_1$     $c_1$     $\rightarrow$     $p_{5} \RINGPROD  g_E(e_1)  + p_{6} \RINGPROD  g_E(e_2)$

$a_1$     $c_2$     $\rightarrow$     $p_{7} \RINGPROD  g_E(e_3)$

$a_2$     $c_2$     $\rightarrow$     $p_{8} \RINGPROD  g_E(e_4) $

[anchor=north west] at (1, -14.5)

$C$     $D$     $\VIEW{T}[C,D]$
$c_1$     $d_1$     $p_9$

$c_2$     $d_2$     $p_{10}$

$c_2$     $d_3$     $p_{11}$

$c_3$     $d_4$     $p_{12}$

[anchor=north west] at (8, -14.5)

$A$     $C$     $E$     $\VIEW{S}[A,C,E]$
$a_1$     $c_1$     $e_1$     $p_5$

$a_1$     $c_1$     $e_2$     $p_6$

$a_1$     $c_2$     $e_3$     $p_7$

$a_2$     $c_2$     $e_4$     $p_8$

Contents of the views in the view tree from Figure <ref> in case the relations
$\VIEW{S}$, and $\VIEW{T}$ are over a ring
$(\RING, \RINGPLUS, \RINGPROD, \RINGZERO, \RINGONE)$ with $p_i \in \RING$ for
$i \in [12]$.

Figure <ref> shows the view tree constructed by the function $\tau$ from
Figure <ref> over the variable order $\omega$ and the empty set of free variables.
Figure <ref> depicts
the view tree constructed over the
same variable order but for
the set  $\mathcal{F} = \{A,C\}$ of free variables.

Figure <ref> gives the
contents of the views in the view tree from Figure <ref>, where
$\VIEW{S}$, and $\VIEW{T}$ are relations over a ring $\RING$ with payloads $p_i \in \RING$ for
$i \in [12]$.
Assume that $\RING$ is the $\mathbb{Z}$ ring,
each tuple in these relations
is mapped to $1$,
i.e.,  $p_i = 1$ for $i \in [12]$, and
the lifting functions map all
values to $1$.
Then, the view tree
computes the COUNT query
from Example <ref>
and the root view $\VIEW{V_{RST}^{@A}}$ maps the empty tuple to
the overall count $10$,
which is the number
of tuples in the natural join of $\VIEW{R}$, $\VIEW{S}$, and

By default, the function $\tau$ in Figure <ref> constructs one view per variable in the variable order $\omega$. A wide relation (with many variables) leads to long branches in $\omega$ with variables that are only local to this relation. This is, for instance, the case of our retailer dataset used in
Section <ref>. Such long branches create long chains of views, where each view marginalizes one bound variable over its child view in the chain. For practical reasons, we compose such long chains into a single view that marginalizes several variables at a time.

§ FACTORIZABLE UPDATES

Our focus so far has been on supporting updates represented by delta relations. We next consider an alternative approach that decomposes a delta relation into a union of factorizable relations. The cumulative size of the decomposed relations can be much less than the size of the original delta relation. Also, the complexity of propagating a factorized update can be much lower than that of its unfactorized (listing) representation, since the factorization makes explicit the independence between query variables and enables optimizations of delta propagation such as pushing marginalization past joins. Besides the factorized view computation, this is the second instance where exploits factorization.

Factorizable updates arise in many domains such as linear algebra and machine learning. Section <ref> demonstrates how our framework can be used for the incremental evaluation of matrix chain multiplication, recovering prior work on this [45].  Matrix chain computation can be phrased in our language of joins and aggregates, where matrices are binary relations. Changes to one row/column in an input matrix may be expressed as a product of two vectors. In general, an arbitrary update matrix can be decomposed into a sum of rank-$1$ matrices, each of them  expressible as products of vectors, using low-rank tensor decomposition methods [34, 63].

Arbitrary relations can be decomposed into a union of factorizable relations. The relation $\VIEW[A,B]{R}$ $= \{(a_i,b_j) \to 1\mid i\in[n],j\in[m]\}$ can be decomposed as $\VIEW[A]{R_1}\VPROD\VIEW[B]{R_2}$, where $\VIEW[A]{R_1}=\{(a_i) \to 1\mid i\in[n]\}$ and $\VIEW[B]{R_2}=\{(b_j) \to 1\mid j\in[m]\}$. We thus reduced a relation of size $nm$ to two relations of cumulative size $n+m$. If $\VIEW{R}$ were a delta relation, the delta views on top of it would now be expressed over $\VIEW[A]{R_1}\VPROD\VIEW[B]{R_2}$ and their computation can be factorized as done for queries in Section <ref>. Product decomposition of relations can be done in linearithmic time in both the number of variables and the size of the relation [50].

Consider now $\VIEW[A,B]{R'}$ $=$ $\VIEW[A,B]{R}$ $\VPLUS$ $\{(a_{n+1},b_j) \to 1\mid j\in[m-1]\}$ with $\VIEW{R}$ as above. We can decompose each of the two terms in $\VIEW{R'}$ similarly to $\VIEW{R}$, yielding overall $n+2m$ values instead of $nm+m-1$. A different decomposition with $n+m+3$ values is given by a factorizable over-approximation of $\VIEW{R'}$ compensated by a small product with negative payload: $\{(a_i)\to 1\mid i\in[n+1]\}\VPROD\{(b_j)\to 1\mid j\in[m]\}\VPLUS\{(a_{n+1})\to 1\}\VPROD\{(b_m)\to -1\}$.

The Optimize method used in the delta view tree algorithm in Figure <ref> exploits the distributivity of join $\VPROD$ over marginalization $\VSUM_{X}$ to push the latter past the former and down to the views with variable $X$. This optimization is reminiscent of pushing aggregates past joins in databases and variable elimination in probabilistic graphical models [6]. In case the delta views express Cartesian products, then they are not materialized but instead kept factorized.

Consider the query $\VIEW{Q}$ from Example <ref>
and its view tree in Figure <ref>.
In the delta view tree derived for updates to $\VIEW{S}$, the top-level delta is computed as:

\begin{align*}
\VIEW[~]{\delta{V^{@A}_{RST}}} = \VSUM_{A} \VIEW[A]{V^{@B}_{R}} \VPROD
\big(&  \VSUM_{C} \VIEW[C]{V^{@D}_{T}} \VPROD \\
& \underbrace{\hspace{3em}\underbrace{\VSUM_{E} \VIEW[A,C,E]{\delta{S}}}_{\VIEW[A,C]{\delta{V^{@E}_{S}}}}\big)}_{\VIEW[A]{\delta{V^{@C}_{ST}}}}
\end{align*}

A single-tuple update $\VIEW{\delta{S}}$ binds variables $A$, $C$, and $E$, and computing $\VIEW{\delta{V^{@A}_{RST}}}$ requires $\bigO{1}$ lookups in $\VIEW{V^{@D}_{T}}$ and $\VIEW{V^{@B}_{R}}$. An arbitrary-sized update $\VIEW{\delta{S}}$ can then be processed in $\bigO{|\VIEW{\delta{S}}|}$ time.

Assume now that $\VIEW{\delta{S}}$ is factorizable as $\VIEW[A,C,E]{\delta{S}} = \VIEW[A]{\delta{S_{A}}} \VPROD \VIEW[C]{\delta{S_{C}}} \VPROD \VIEW[E]{\delta{S_{E}}}$. In the construction of the delta view tree, the Optimize method exploits this factorization to push the marginalization past joins at each variable; for example, the delta at $E$ becomes:

\begin{align*}
\VIEW[A,C]{\delta{V^{@E}_{S}}} &= \VSUM_{E} \VIEW[A]{\delta{S_{A}}} \VPROD \VIEW[C]{\delta{S_{C}}} \VPROD \VIEW[E]{\delta{S_{E}}} \\
&= \VIEW[A]{\delta{S_{A}}} \VPROD \VIEW[C]{\delta{S_{C}}} \VPROD \VSUM_{E} \VIEW[E]{\delta{S_{E}}}
\end{align*}

We also transform the top-level delta into a product of three views:

\begin{align*}
\VIEW[~]{\delta{V^{@A}_{RST}}} =
&\big( \VSUM_{A} \VIEW[A]{V^{@B}_{R}} \VPROD \VIEW[A]{\delta{S_{A}}} \big) \VPROD
\big( \VSUM_{C} \VIEW[C]{V^{@D}_{T}} \VPROD \VIEW[C]{\delta{S_{C}}} \big) \VPROD
\big( \VSUM_{E} \VIEW[E]{\delta{S_{E}}} \big)
\end{align*}

The computation time for this delta is proportional to the sizes of the three views representing the update:
$\bigO{\min(|\VIEW{V^{@B}_{R}}|, {|\VIEW{\delta{S_{A}}}|}) + \min(|\VIEW{V^{@D}_{T}}|, |\VIEW{\delta{S_{C}}}|) + |\VIEW{\delta{S_{E}}}|}$.

§ FOR SPECIAL QUERY CLASSES

This section shows how maintains free-connex ($\alpha$-)acyclic queries [28] and $q$-hierarchical queries [12]. The analysis for these queries is refined into: (i) the preprocessing phase, where the view tree is constructed; (ii) the enumeration phase, where we present the query result one tuple at a time; and (iii) the update phase, where we update the view tree. The following data complexity[The data complexity is a function of the database size.] claims assume that the ring operations require constant time, otherwise the complexity results stated in this section have an extra multiplying factor to account for the complexity of the ring operations.

Let a query $\VIEW[]{Q}$ and a database of size $N$.

can maintain $\VIEW[]{Q}$ with $O(N)$ preprocessing, $O(1)$ enumeration delay, and $O(N)$ single-tuple update in case $\VIEW[]{Q}$ is free-connex acyclic.

can maintain $\VIEW[]{Q}$ with $O(N)$ preprocessing, $O(1)$ enumeration delay, and $O(1)$ single-tuple update in case $\VIEW[]{Q}$ is $q$-hierarchical.

Section <ref> discusses an important extension of our view tree construction to better support cyclic queries.

§.§ Free-Connex Acyclic Queries

We first introduce the class of free-connex acyclic queries and then explain how maintains them.

A join tree for a query is a tree, where each node is a relation and if any two nodes have variables in common, then all nodes along the path between them also have these variables.

A query is ($\alpha$-)acyclic if it admits a join tree.

A query is free-connex acyclic if it is acyclic and remains acyclic after adding a new relation whose schema consists of the free variables of the query.

Consider the query
$\VIEW[A,B,C]{Q} = \VSUM_{D}\VSUM_{E}$ $\VIEW[A,B]{R} \VPROD \VIEW[A,C,E]{S} \VPROD \VIEW[C,D]{T}$.
A possible join tree for $\VIEW[]{Q}$ is
$\VIEW[A,B]{R} - \VIEW[A,C,E]{S} - \VIEW[C,D]{T}$, where
“$-$" denotes the parent-child relationship.
Hence, $\VIEW[]{Q}$ is acyclic.

Consider the triangle query
$\VIEW[~]{Q_{\vartriangle}} = \VSUM_{A}\VSUM_{B}\VSUM_{C}$ $\VIEW[A,B]{R} \VPROD \VIEW[B,C]{S} \VPROD \VIEW[A,C]{T}$. A possible tree built from the relations
of $\VIEW[]{Q_{\vartriangle}}$ is
$\VIEW[A,B]{R} - \VIEW[B,C]{S} - \VIEW[A,C]{T}$.
The variable $A$ occurs in the first and last relations but not in the middle relation; thus, this tree is not a join
tree for $\VIEW[]{Q_{\vartriangle}}$. One can show that any
tree built from the relations of $\VIEW[]{Q_{\vartriangle}}$ is not a join tree.
Hence, $\VIEW[]{Q_{\vartriangle}}$ is not acyclic.

The tree $\VIEW[A,B]{R} - \VIEW[A,B,C]{U} - \VIEW[A,C,E]{S} - \VIEW[C,D]{T}$
is a join tree of $\VIEW[]{Q}$ extended with the relation
$U$ whose schema consists of the free variables of $\VIEW[]{Q}$.
Hence, $\VIEW[]{Q}$ is free-connex acyclic.
Consider now the variant $\VIEW[]{Q'}$
of $\VIEW[]{Q}$ where only the variables $B$ and $C$ are free.
Adding a fresh relation $U'$ with schema $(B,C)$ to
$\VIEW[]{Q'}$ turns it into a cyclic query $\VIEW[]{Q''}$
that does not admit a join tree.

3c$\nu$ (free-top variable order $\omega$) : view tree

a     $\VIEW{R}$     $\VIEW[\mathit{\sch(\VIEW{R})}]{R}$

[xscale=0.4, yscale=1]
at (0,-2)  (n4) $X$;
at (-1,-3)  (n1) $\omega_1$ edge[-] (n4);
at (0,-3)  (n2) $\ldots$;
at (1,-3)  (n3) $\omega_k$ edge[-] (n4);
at (0,-4.5)  ;

$T_i  = \tau(\omega_i), \ \forall i\in[k] $

$\VIEW[\mathit{keys_i}]{V^{@\omega_i}_{rels_i}} = \text{ root of } T_i, \ \forall i\in[k] $

$\mathit{keys}=\{X\} \cup \mathit{dep}(X)$

$\VIEW[\mathit{keys}]{H^{@X}_{rels}}= \VPRODBIG_{i \in [k]} \VIEW[\mathit{keys_i}]

$\VIEW[\mathit{keys}\setminus \{X\}]{V^{@X}_{rels}}= \VSUM_{X} \VIEW[\mathit{keys}]{H^{@X}_{rels}}$

$X$ has more than one child ($k\geq 2$)

$X$ has no sibling

\left\{
\begin{array}{@{~~}c@{~~}}
\tikz {
\node at (1.4,-1)  (n4) {$\VIEW[\mathit{keys}]{H^{@X}_{rels}}$};
\node at (0.8,-1.75)  (n1) {$T_1$} edge[-] (n4);
\node at (1.25,-1.75)  (n2) {$\ldots$};
\node at (1.8,-1.75)  (n3) {$T_k$} edge[-] (n4);
\end{array}  \right.$

\left\{
\begin{array}{@{~~}c@{~~}}
\tikz {
\node at (1.2,-0.25)  (n) {$\VIEW[\mathit{keys}\setminus \{X\}]{V^{@X}_{rels}}$};
\node at (1.2,-1)  (n4) {$\VIEW[\mathit{keys}]{H^{@X}_{rels}}$} edge[-] (n);
\node at (0.8,-1.75)  (n1) {$T_1$} edge[-] (n4);
\node at (1.25,-1.75)  (n2) {$\ldots$};
\node at (1.8,-1.75)  (n3) {$T_k$} edge[-] (n4);
\end{array}  \right.$

$X$ has no sibling

\left\{
\begin{array}{@{~~}c@{~~}}
\tikz {
\node at (1.2,-0.25)  (n) {$\VIEW[\mathit{keys}\setminus \{X\}]{V^{@X}_{rels}}$};
\node at (1.2,-1)  (n1) {$T_1$} edge[-] (n);
\end{array}  \right.$

Creating a view tree for a free-top variable order.

We next detail how achieves the complexity from Theorem <ref> for a free-connex acyclic query $\VIEW[]{Q}$.

In the preprocessing phase, we create a view tree
that compactly represent the result of $\VIEW[]{Q}$.
Given a variable order, the function $\tau$ in
Figure <ref> constructs a view tree where
the root view consists of all tuples over the free variables.
While this view allows for constant enumeration delay, it may
require superlinear computation and maintenance time as the free variables may originate from different input relations. We would like to avoid this super-linearity.

To keep the preprocessing and update times linear, we proceed as follows.
We construct view trees such that the query result is kept and maintained factorized over several views at the top of the view tree.
This approach still allows for constant enumeration delay, using a known enumeration approach for factorized representations [54].
We construct the view tree following a free-top variable order of the query $\VIEW[]{Q}$
and materialize a view over the schema $\{X\} \cup \mathit{dep}(X)$ for each variable $X$ in the variable order.
A key insight is that every free-connex acyclic query admits a free-top variable order
where for each variable $X$, the set $\{X\} \cup \mathit{dep}(X)$
is covered by the variables of a single relation [11].
This ensures linear preprocessing and maintenance time for all views in view trees
following such variable orders.

The function  $\nu$ in Figure <ref>
constructs a view tree for a given free-top variable
order of a free-connex query.
If a variable $X$ has at least two children, it proceeds as follows.
It creates at $X$
a view $\VIEW[]{H^{@X}_{rels}}$
with schema $\{X\} \cup \mathit{dep}(X)$
that joins the child views of $X$.
If $X$ has at least one sibling, it additionally
creates a view $\VIEW[]{V^{@X}_{rels}}$ on top of $\VIEW[]{H^{@X}_{rels}}$
obtained from $\VIEW[]{H^{@X}_{rels}}$ by marginalizing  $X$.
The first view
enables efficient enumeration of $X$-values in the query result given a value tuple
over $\mathit{dep}(X)$; the second view enables efficient updates
coming from the subtrees rooted at siblings of $X$.
If $X$ has only one child, the creation of the view $\VIEW[]{H^{@X}_{rels}}$ is not needed for efficient enumeration.
In this case, the function creates  a view $\VIEW[]{V^{@X}_{rels}}$ marginalizing $X$ in the child view if
$X$ has siblings.

Consider the free-connex acyclic query
$\VIEW[]{Q}$ from Example <ref>.
Figure <ref> gives a free-top variable order $\omega$ for $\VIEW[]{Q}$.
Figure <ref> (left) depicts
the view tree $\nu(\omega)$.
The view $\VIEW[]{H_{ST}^{@C}}$ can be computed by iterating
over the $(A,C)$-tuples in $\VIEW[]{V_{S}^{@E}}$ and multiplying
the payload of each such tuple with the payload of the matching
$C$-value in $\VIEW[]{V_{T}^{@D}}$.
Since each such $(A,C)$-tuple  must be in $\VIEW[]{S}$, we need to iterate
over only linearly many such tuples.
Similarly, the view $\VIEW[]{H_{RST}^{@A}}$ can be computed by iterating
over the $A$-values in one of the child views and doing lookups in the other child view to retrieve the payloads. For the computation of both views $\VIEW[]{H_{ST}^{@C}}$ and  $\VIEW[]{H_{RST}^{@A}}$,
we iterate over linearly  many
tuples and do a constant-time lookup for each such tuple.
All other views are obtained by marginalizing one variable from their child views.
Hence, all views can be computed in linear time.

[xscale=0.7, yscale=0.24]

at (-0.4, 3) (A) $\VIEW[A]{H^{@A}_{RST}}$;
at (1.5, 0) (C) $\VIEW[A]{V^{@C}_{ST}}$ edge[-] (A);
at (1.5, -3) (C') $\VIEW[A,C]{H^{@C}_{ST}}$ edge[-] (C);
at (2.5, -6) (E) $\VIEW[A,C]{V^{@E}_{S}}$ edge[-] (C');
at (2.5, -9) $\VIEW[A,C,E]{S}$ edge[-] (E);

at (0, -6) (D) $\VIEW[C]{V^{@D}_{T}}$ edge[-] (C');
at (0, -9) $\VIEW[C,D]{T}$ edge[-] (D);

at (-2.3, -0) (B) $\VIEW[A]{V^{@B}_{R}}$ edge[-] (A);
at (-2.3, -3) $\VIEW[A,B]{R}$ edge[-] (B);

[xscale=0.7, yscale=0.24]

at (-0.4, 3) (A)  $\delta\VIEW[A]{H^{@A}_{RST}}$;
at (1.5, 0) (C)  $\delta\VIEW[A]{V^{@C}_{ST}}$ edge[-] (A);
at (1.5, -3) (C')  $\delta\VIEW[A,c]{H^{@C}_{ST}}$ edge[-] (C);
at (2.5, -6) (E) $\VIEW[A, C]{V^{@E}_{S}}$ edge[-] (C');
at (2.5, -9) $\VIEW[A, C ,E]{S}$ edge[-] (E);

at (0, -6) (D) $\color{blue} \delta\VIEW[c]{V^{@D}_{T}}$ edge[-] (C');
at (0, -9) $\color{blue} \delta\VIEW[c,d]{T}$ edge[-] (D);

at (-2.3, -0) (B) $\VIEW[A]{V^{@B}_{R}}$ edge[-] (A);
at (-2.3, -3) $\VIEW[A,B]{R}$ edge[-] (B);

(left) View tree constructed by the function $\nu$ in
Figure <ref> for the variable
order $\omega$ in Figure <ref>;
(right) Delta view tree for a single-tuple update to $\VIEW{T}$.

The construction of delta view trees under single-tuple updates
is exactly as described
by the function $\Delta$ in Figure <ref> (Section <ref>).
Since the view trees can be constructed in linear time,

the delta view trees can also be constructed in linear time.

Continuing Example <ref>, we consider a single-tuple update $\delta\VIEW{T}[c,d]$ to relation $\VIEW{T}$.
Figure <ref> depicts the original view tree (left) and the delta view tree for updates to $\VIEW{T}$ (right). The difference is that along the path from $\VIEW{T}$ to the root, we now have delta views.
The delta view $\delta\VIEW[]{V^{@D}_{T}}$
results from  $\delta\VIEW[c,d]{T}$ by marginalizing $D$, which takes
constant time since $D$ is fixed to the constant $d$.
To compute $\delta\VIEW[]{H^{@C}_{ST}}$, we iterate over all $A$-values
paired with $c$ in $\VIEW[]{V^{@E}_{S}}$. This operation takes linear time with the support of an index on variable $C$ built for this view.

We obtain $\delta\VIEW[]{V^{@C}_{ST}}$ from $\delta\VIEW[]{H^{@C}_{ST}}$
by marginalizing the variable $C$. This requires constant time because $C$ is fixed to
the constant $c$.
The top delta view $\delta\VIEW[]{H^{@A}_{RST}}$ is obtained by intersecting the two child views, e.g., by iterating over $\delta\VIEW[]{V^{@C}_{ST}}$ and doing lookups in $\VIEW[]{V^{@B}_R}$. This requires linear time. We conclude that the delta views can be computed in linear time.

Consider a view tree $\tau$ constructed using the function $\nu$ from
Figure <ref> for a free-top variable order of a
query $\VIEW[]{Q}$.
We first describe how to enumerate with constant delay the distinct tuples in the result of $\VIEW{Q}$ using $\tau$. Then, we explain how to compute the payload of each result tuple in constant time.

Let $X_1, \ldots, X_n$ be an ordering of the free variables of the query
that is compatible with a top-down traversal of the free-top variable order.
We use the views $\VIEW[]{V_1}, \ldots , \VIEW[]{V_n}$

to enumerate the distinct tuples
in the result of $\VIEW[]{Q}$, where
$\VIEW[]{V_j}$ is $\VIEW[]{H^{@X_j}_{rels}}$ if $X_j$ has at least two children
and it is the child view of $X_j$ otherwise.
We retrieve from $\VIEW[]{V_1}$ the first $X_1$-value in the
When we arrive at a view  $\VIEW[]{V_j}$ with $j > 1$, we have already fixed
the values of the variables above $X_j$ in the variable order.
We retrieve from $\VIEW[]{V_j}$ the first $X_j$-value paired with these values.
Once the values over all free variables
are fixed, we have a complete result tuple that we output.
Then, we iterate over the remaining distinct $X_n$-values in $\VIEW[]{V_n}$
paired with the fixed values over the ancestor variables of $X_n$
and output a new tuple for each such value.
After all $X_n$-values are exhausted, we backtrack, i.e., we move to the next $X_{n-1}$-value
and restart the iteration of the matching $X_n$-values.

3c$payload$(view tree $\tau$, tuple t): payload

a     $\VIEW{R}$     $\VIEW{R}(\textvec{t})$

[xscale=0.4, yscale=1]
at (0,-2)  (n4) $\VIEW[\mathcal{X}]{V}$;
at (-1,-3)  (n1) $\tau_1$ edge[-] (n4);
at (0,-3)  (n2) $\ldots$;
at (1,-3)  (n3) $\tau_k$ edge[-] (n4);
at (0,-4.5)  ;

$\mathcal{X} = \sch(\textvec{t})$

// $\mathcal{X} \subset \sch(\textvec{t})$

$\mathcal{V}_i =$ variables in $\tau_i$,  $\forall i \in [k]$

$\prod_{i \in [k]} payload(\tau_i, \pi_{\mathcal{V}_i}\textvec{t})$

Computing the payload of a tuple from a view tree.

Given a complete tuple $\textvec{t}$ constructed from the view tree $\tau$, we use the
function $payload$ from Figure <ref> to compute its payload.
The function first checks whether the schema of the root view is exactly the schema
$\sch(\textvec{t})$ of $\textvec{t}$. If so, it returns the payload of $\textvec{t}$ in this view. Otherwise, the root view covers only a subset of the schema of the tuple.
In this case, the function recursively computes the payload for each subtree $\tau_i$ of the root view
and the projection of $\textvec{t}$ onto the variables in $\tau_i$.
The final payload is the product of the payloads returned for the subtrees.
The returned payloads are from the lowest views in the view tree whose schemas consist of free variables only. If all variables are free, then these lowest views are the input relations themselves.

The enumeration procedure needs the payloads of the lowest views whose schemas consist of free variables. The payloads from the views above these views thus need not be maintained, beyond keeping track of the multiplicities of each of their tuples. The maintenance of multiplicities is important for correctness, as it tells whether a tuple is to be removed from a view or still has at least one possible derivation from the input.
For expensive payloads, such as those introduced in Section <ref>, it is therefore more efficient to only maintain them for the views from the input relations up to the views used to compute the payloads. Their ancestor views only need maintenance of tuple multiplicities.

We enumerate the distinct result tuples of the query
from Example <ref> using the view tree in Figure <ref> (left). We iterate with constant delay
over the $A$-values in $\VIEW[A]{H^{@A}_{RST}}$. For each such $A$-value
$a$, we iterate with constant delay over the $B$-values in
$\VIEW[a,B]{R}$ and over the $C$-values in
$\VIEW[a,C]{H^{@C}_{ST}}$. Each triple $(a,b,c)$
obtained in this way is a result tuple of $\VIEW[]{Q}$.
Its payload is $\VIEW[a,b]{R} \cdot \VIEW[a,c]{H^{@C}_{ST}}$.

To efficiently support enumeration and updates, we may need several indices for the views in a view tree for a free-connex acyclic query. Each view  (and input relation) in the view tree in Figure <ref> (left) needs an index that can retrieve the payload for a given tuple of values over its variables. This is a primary index. For (top-down) enumeration, we may also need a secondary index per view to lookup for tuples that have as prefix a tuple of values over the variables shared with its parent view. Yet in case of some views, we may also need a tertiary index to support updates, which are propagated bottom-up.

For instance, the view $\VIEW[A,C]{V^{@E}_{S}}$ requires: a primary index to retrieve the payload for each $(A,C)$-tuple; a secondary index to enumerate the $C$-values paired with a given $A$-value fixed by the parent view; and a tertiary index to obtain all $A$-values paired with a given $C$-value $c$ fixed by the delta of its left sibling $\delta\VIEW[c]{V^{@D}_{T}}$. All other views only require primary and secondary indices and no tertiary index.

§.§ $Q$-Hierarchical Queries

$Q$-hierarchical queries form a strict subclass of the free-connex acyclic queries.
They admit linear preprocessing time, constant update time, and constant enumeration delay [12]. Under widely-held complexity theoretic assumptions, there is no algorithm that achieves constant update time and enumeration delay for queries that are not $q$-hierarchical and have no repeating relation symbols [12].
recovers the aforementioned complexities using exactly the same approach as for free-connex acyclic queries detailed in Section <ref>. This directly implies linear preprocessing time and  constant enumeration delay. Constant update time follows from the following observation. Every $q$-hierarchical query admits a free-top variables order, where each root-to-leaf path consists of variables that represent precisely the schema of a relation in the query. A single-tuple update to that relation then sets all these variables to constants, effectively making each delta view along that path of constant size. Our view tree construction also ensures that the computation of each delta view only requires one constant-time lookup per child view.

We first define $q$-hierarchical queries and then show how achieves constant-time update for them.
For a variable $X$ in a query, we denote by $\textsf{rels}(X)$ the set of relations that contain $X$ in their schema.

A query is hierarchical if for any two variables $X$ and $Y$, it holds $\textsf{rels}(X) \subseteq \textsf{rels}(Y)$, $\textsf{rels}(Y) \subseteq \textsf{rels}(X)$, or $\textsf{rels}(X) \cap \textsf{rels}(Y) = \emptyset$.

A query is $q$-hierarchical if it is hierarchical and for any  two variables $X$ and $Y$,
it holds: if $\textsf{rels}(X) \supset \textsf{rels}(Y)$ and $Y$ is free, then $X$ is free.

Every $q$-hierarchical query admits a canonical free-top variable order, where (i) each root-to-leaf path consists of variables that form the schema of a relation and (2) no bound variable is above a free variable [29].
We can construct such a variable order in polynomial time in the query size as follows.
We start with the empty variable order.
For each relation $R$, we add to the variable order a root-to-leaf path made up of $R$'s variables ordered  as follows:
a variable $X$ is before a variable $Y$ if (1) $\textsf{rels}(X) \supset \textsf{rels}(Y)$
or (2) $\textsf{rels}(X) \not\supset \textsf{rels}(Y)$, $\textsf{rels}(X) \not\subset \textsf{rels}(Y)$, $X$ is free, and $Y$ is bound.

[xscale=0.96, yscale=0.8]
at (0, 0.0) (A) $A$;
at (-0.4, -1.0) (B) $B$  edge[-] (A);
at (0.4, -1.0) (C) $C$ edge[-] (A);
at (0.8, -2.0) (E) $E$ edge[-] (C);
at (0, -2.0) (D) $D$ edge[-] (C);
at (0.8, -2.6) (S) $S$;
at (-0.6, -1.55) (R) $R$;
at (-0.1, -2.6) (T) $T$;
at (2.3, -1.5) 0.9

$dep(A) = \emptyset$

[opacity=.5,fill opacity=.5,line cap=round, line join=round, line width=15pt,color=teal] (0,0.0) – (-0.4,-1);
[opacity=.5,fill opacity=.5,line cap=round, line join=round, line width=18pt,color=orange] (0,0.0) – (0.8,-2.0);
[opacity=.5,fill opacity=.5,line cap=round, line join=round, line width=15pt,color=yellow] (0,0.0) – (0.4,-1) – (0, -2.0);

[xscale=0.7, yscale=0.24]

at (-0.4, 3) (A) $\VIEW[A]{H^{@A}_{RST}}$;
at (1.5, 0) (C) $\VIEW[A]{V^{@C}_{ST}}$ edge[-] (A);
at (1.5, -3) (C') $\VIEW[A,C]{H^{@C}_{ST}}$ edge[-] (C);
at (2.7, -6) (E) $\VIEW[A,C]{V^{@E}_{S}}$ edge[-] (C');
at (2.7, -9) $\VIEW[A,C,E]{S}$ edge[-] (E);

at (-0.1, -6) (D) $\VIEW[A,C]{V^{@D}_{T}}$ edge[-] (C');
at (-0.1, -9) $\VIEW[A,C,D]{T}$ edge[-] (D);

at (-2.3, -0) (B) $\VIEW[A]{V^{@B}_{R}}$ edge[-] (A);
at (-2.3, -3) $\VIEW[A,B]{R}$ edge[-] (B);

(left) Canonical free-top variable order of the query $\VIEW[]{Q_h}$ from Example
(right) Corresponding view tree.

The free-connex acyclic query
$\VIEW[A,B,C]{Q}$ $=$
$\VSUM_{D}\VSUM_{E}$ $\VIEW[A,B]{R} \VPROD \VIEW[A,C,E]{S} \VPROD \VIEW[C,D]{T}$
from Example <ref> is not hierarchical: the sets $\textsf{rels}(A)= \{\VIEW[]{R} , \VIEW[]{S}\}$
$\textsf{rels}(C)= \{\VIEW[]{S} , \VIEW[]{T}\}$ are not disjoint, nor one is included in the other.
By extending the schema of $\VIEW[]{T}$ with $A$, we obtain the $q$-hierarchical query
$\VIEW[A,B,C]{Q_h}$ $=$
$\VSUM_{D}\VSUM_{E}$ $\VIEW[A,B]{R} \VPROD \VIEW[A,C,E]{S} \VPROD \VIEW[A,C,D]{T}$
whose canonical free-top variable order is given in Figure <ref> (left).
The variant of the query,
where variable $A$ is bound is hierarchical but not $q$-hierarchical because
the set $\mathsf{rels}(A)= \{\VIEW[]{R}, \VIEW[]{S}, \VIEW[]{T}\}$
for the  bound variable  $A$ is a strict superset of the set
$\mathsf{rels}(B)= \{\VIEW[]{R}\}$ for the free variable $B$.

We next exemplify  how achieves constant-time update for a $q$-hierarchical query.

Figure <ref> shows the view tree (right)
modeled on the canonical free-top variable order (left) of the
$q$-hierarchical query $\VIEW[]{Q_h}$ in Example <ref>.
Figure <ref> shows the
delta view trees under single-tuple updates to $\VIEW[]{R}$  and $\VIEW[]{T}$.

In the delta view tree for $\VIEW[]{R}$, the delta view
$\delta \VIEW[]{H^{@A}_{RST}}$ can be computed by  a constant-time lookup in
In the delta view tree for $\VIEW[]{T}$, the delta views
$\delta \VIEW[]{H^{@C}_{ST}}$ and $\delta \VIEW[]{H^{@A}_{RST}}$
can be computed by constant-time lookups in
$\VIEW[]{V^{@E}_{S}}$ and $\VIEW[]{V^{@B}_{R}}$, respectively.
All other delta views are computed by marginalizing a variable with a single value.

[xscale=0.7, yscale=0.24]

at (-0.4, 3) (A) $\color{blue} \delta \VIEW[a]{H^{@A}_{RST}}$;
at (1.5, 0) (C) $\VIEW[A]{V^{@C}_{ST}}$ edge[-] (A);
at (1.5, -3) (C') $\VIEW[A,C]{H^{@C}_{ST}}$ edge[-] (C);
at (2.7, -6) (E) $\VIEW[A,C]{V^{@E}_{S}}$ edge[-] (C');
at (2.7, -9) $\VIEW[A,C,E]{S}$ edge[-] (E);

at (-0.1, -6) (D) $\VIEW[A,C]{V^{@D}_{T}}$ edge[-] (C');
at (-0.1, -9) $\VIEW[A,C,D]{T}$ edge[-] (D);

at (-2.3, -0) (B) $\color{blue}\delta \VIEW[a]{V^{@B}_{R}}$ edge[-] (A);
at (-2.3, -3) $\color{blue}\delta \VIEW[a,b]{R}$ edge[-] (B);

[xscale=0.7, yscale=0.24]

at (-0.4, 3) (A) $\color{blue} \delta \VIEW[a]{H^{@A}_{RST}}$;
at (1.5, 0) (C) $\color{blue}\delta \VIEW[a]{V^{@C}_{ST}}$ edge[-] (A);
at (1.5, -3) (C') $\delta \VIEW[a,c]{H^{@C}_{ST}}$ edge[-] (C);
at (2.7, -6) (E) $\VIEW[A,C]{V^{@E}_{S}}$ edge[-] (C');
at (2.7, -9) $\VIEW[A,C,E]{S}$ edge[-] (E);

at (-0.1, -6) (D) $\color{blue}\delta \VIEW[a,c]{V^{@D}_{T}}$ edge[-] (C');
at (-0.1, -9) $\color{blue}\delta \VIEW[a,c,d]{T}$ edge[-] (D);

at (-2.3, -0) (B) $\VIEW[A]{V^{@B}_{R}}$ edge[-] (A);
at (-2.3, -3) $\VIEW[A,B]{R}$ edge[-] (B);

Delta view trees derived from the view tree in Figure <ref>
for single-tuple updates to relations $\VIEW[]{R}$ (left) and $\VIEW[]{T}$ (right).

$Q$-hierarchical queries admit view trees whose views only need primary indices to support payload lookup and updates and possibly secondary indices to support enumeration.
Consider the view tree in Figure <ref>. Enumeration proceeds top-down: We iterate over the $A$-values in the top view and for each such value $a$,

we look up in $\VIEW[a,B]{R}$ to enumerate over all the $B$-values paired with $a$, and also look up into $\VIEW[a,C]{H^{@C}_{ST}}$ to enumerate over all $C$-values paired with $a$.
All these look-ups require primary or secondary indices.

Figure <ref> shows the delta view trees for single-tuple updates to $\VIEW[]{R}$ and $\VIEW[]{T}$. To compute a delta view along the path from the delta relation to the root of the delta view tree, we either perform a projection on a delta view or a lookup in the primary index of a sibling view (so with all keys of the index set to constants).

§.§ Queries under Functional Dependencies

Non-hierarchical queries may become hierarchical under functional dependencies (fds) [49].

Given a set $\Sigma$ of fds, we denote by $\textsf{CLOSURE}_\Sigma(\calS)$ the closure of the set $\calS$ of variables under $\Sigma$ [5]. For instance, given the fds $\Sigma=\{A\rightarrow D;BD \rightarrow E\}$, we have $\textsf{CLOSURE}_\Sigma(\{A,B,C\})=\{A,B,C,D,E\}$.

Given a set $\Sigma$ of fds and a query $\VIEW[\calS]{Q} = \VSUM_{\calB} \VIEW[\calS_1]{R_1}\VPROD\cdots\VPROD\VIEW[\calS_n]{R_n}$, the $\Sigma$-reduct of $\VIEW[]{Q}$ under $\Sigma$ is:

\begin{align*}
\;
\VIEW[\textsf{CLOSURE}_\Sigma(\calS)]{Q} = \VSUM_{\calB} &\VIEW[\textsf{CLOSURE}_\Sigma(\calS_1)]{R_1}\VPROD\cdots\VPROD \VIEW[\textsf{CLOSURE}_\Sigma(\calS_n)]{R_n}
\end{align*}

The $\Sigma$-reduct of a query is thus another query, where the schema of each relation is extended to include all variables in the closure of this schema under $\Sigma$. Since the added variables are functionally determined by the original schema, they do not add more information. So, we could extend these schemas and the underlying database without increasing the number of tuples in the relations. For any database $D$ with fds $\Sigma$ and a query $\VIEW[]{Q}$, the query result $\VIEW[]{Q}(D)$ is the same as the result of its $\Sigma$-reduct over the extended database.
The benefit of this rewriting is that queries may admit free-connex acyclic or even $q$-hierarchical $\Sigma$-reducts. We need not physically extend the database to reap this benefit. Instead, we use the $\Sigma$-reduct of $\VIEW[]{Q}$ to infer a free-top variable order or even a canonical free-top variable order for $\VIEW[]{Q}$ in case the $\Sigma$-reduct is free-connex acyclic or $q$-hierarchical, respectively.
Using this variable order, we construct a view tree for $\VIEW[]{Q}$ that enjoys the preprocessing, update, and enumerate times as for its $\Sigma$-reduct.

Theorem <ref> can be generalized to account for fds.

Let a query $\VIEW[]{Q}$ and a database of size $N$ and with a set $\Sigma$ of functional dependencies.

can maintain $\VIEW[]{Q}$ with $O(N)$ preprocessing, $O(1)$ enumeration delay, and $O(N)$ single-tuple updates in case the $\Sigma$-reduct of $\VIEW[]{Q}$ is free-connex acyclic.

can maintain $\VIEW[]{Q}$ with $O(N)$ preprocessing, $O(1)$ enumeration delay, and $O(1)$ single-tuple updates in case the $\Sigma$-reduct of $\VIEW[]{Q}$ is $q$-hierarchical.

[xscale=0.96, yscale=0.8]
at (0, 0) (D) $D$;
at (0, -1) (C) $C$;
at (0, -2) (B) $B$;
at (0, -3) (A) $A$;

at (-0.5, -0.5) (T) $\VIEW{T}$;
at (-0.5, -1.5) (S) $\VIEW{S}$;
at (-0.5, -2.5) (R) $\VIEW{R}$;
[opacity=.5,fill opacity=.5,line cap=round, line join=round, line width=13pt,color=purple] (0,0) – (0,-1);[opacity=0.7,fill opacity=0.7,line cap=round, line join=round, line width=13pt,color=orange] (0,-1) – (0,-2.0);
[opacity=.5,fill opacity=.5,line cap=round, line join=round, line width=13pt,color=teal] (0,-2) – (0,-3);

[xscale=0.96, yscale=0.8]
at (0, 0) (D) $D$;
at (0, -1) (C) $C$;
at (0, -2) (B) $B$;
at (0, -3) (A) $A$;

at (-0.6, -0.5) (T) $\VIEW{T}$;
at (-0.6, -1.6) (S) $\VIEW{S}$;
at (-0.6, -2.9) (R) $\VIEW{R}$;
[opacity=.5,fill opacity=1,line cap=round, line join=round, line width=23pt,color=teal] (0,0) – (0,-3);
[opacity=1,fill opacity=1,line cap=round, line join=round, line width=18pt,color=orange] (0,0) – (0,-2);
[opacity=0.8,fill opacity=0.8,line cap=round, line join=round, line width=13pt,color=purple] (0,0) – (0,-1);

[xscale=0.96, yscale=0.8]
at (0, 0) (D) $D$;
at (0, -1) (C) $C$edge[-] (D);
at (0, -2) (B) $B$edge[-] (C);
at (0, -3) (A) $A$edge[-] (B);
at (1.5, -1.9)

[xscale=0.7, yscale=0.24]
at (-2.3, 6) (C) $\VIEW[C,D]{H^{@C}_{RST}}$;
at (-2.3, 3) (B) $\VIEW[C]{V^{@B}_{RS}}$edge[-] (C);
at (-2.3, 0) (B') $\VIEW[B,C]{H^{@B}_{RS}}$ edge[-] (B);
at (-2.3, -3) (A) $\VIEW[B]{V^{@A}_{R}}$edge[-] (B');
at (-2.3, -6) $\VIEW[A,B]{R}$ edge[-] (A);

at (-0.2, -3) (S) $\VIEW[B,C]{S}$edge[-] (B');
at (-0.2, 3) (T) $\VIEW[C,D]{T}$edge[-] (C);

From left to right: Hypergraph of the query
$\VIEW{Q}$ and its $\Sigma$-reduct for $\Sigma = \{B \rightarrow C, C \rightarrow D\}$
from Example <ref>;
canonical variable order $\omega$ for  $\VIEW{Q}$; view tree modeled on $\omega$.

[xscale=0.7, yscale=0.24]
at (-2.3, 6) (C) $\delta\VIEW[c,d]{H^{@C}_{RST}}$;
at (-2.3, 3) (B) $\delta\VIEW[c]{V^{@B}_{RS}}$edge[-] (C);
at (-2.3, 0) (B') $\color{blue}\delta\VIEW[b,c]{H^{@B}_{RS}}$ edge[-] (B);
at (-2.3, -3) (A) $\color{blue}\delta\VIEW[b]{V^{@A}_{R}}$edge[-] (B');
at (-2.3, -6) $\color{blue}\delta\VIEW[a,b]{R}$ edge[-] (A);

at (-0.2, -3) (S) $\VIEW[B,C]{S}$edge[-] (B');
at (-0.2, 3) (T) $\VIEW[C,D]{T}$edge[-] (C);

[xscale=0.7, yscale=0.24]
at (-2.3, 6) (C)  $\delta\VIEW[c,d]{H^{@C}_{RST}}$;
at (-2.3, 3) (B) $\delta\VIEW[c]{V^{@B}_{RS}}$edge[-] (C);
at (-2.3, 0) (B') $\delta\VIEW[b,c]{H^{@B}_{RS}}$ edge[-] (B);
at (-2.3, -3) (A) $\VIEW[B]{V^{@A}_{R}}$edge[-] (B');
at (-2.3, -6) $\VIEW[A,B]{R}$ edge[-] (A);

at (-0.2, -3) (S) $\delta\VIEW[b,c]{S}$edge[-] (B');
at (-0.2, 3) (T) $\VIEW[C,D]{T}$edge[-] (C);

[xscale=0.7, yscale=0.24]
at (-2.3, 6) (C) $\delta\VIEW[c,d]{H^{@C}_{RST}}$;
at (-2.3, 3) (B) $\VIEW[C]{V^{@B}_{RS}}$edge[-] (C);
at (-2.3, 0) (B') $\VIEW[B,C]{H^{@B}_{RS}}$ edge[-] (B);
at (-2.3, -3) (A) $\VIEW[B]{V^{@A}_{R}}$edge[-] (B');
at (-2.3, -6) $\VIEW[A,B]{R}$ edge[-] (A);

at (-0.2, -3) (S) $\VIEW[B,C]{S}$edge[-] (B');
at (-0.2, 3) (T) $\delta\VIEW[c,d]{T}$edge[-] (C);

Delta view trees derived from the view tree in Figure <ref> for single-tuple updates to

$\VIEW{R}$, $\VIEW{S}$, and $\VIEW{T}$ (left to right).
The values $b$ and $c$ functionally determine $c$ and $d$, respectively.

Consider $\Sigma = \{B \rightarrow C, C \rightarrow D\}$ and the free-connex acyclic but not hierarchical query

\begin{align*}
\quad  \VIEW[A,B,C,D]{Q} =\VIEW[A,B]{R} \VPROD \VIEW[B,C]{S} \VPROD \VIEW[C,D]{T}.
\end{align*}

The $\Sigma$-reduct of $\VIEW[]{Q}$ is

\begin{align*}
\VIEW[A,B,C,D]{Q'} \hspace{-0.1em} =\VIEW[A,B,C,D]{R} \VPROD \VIEW[B,C,D]{S} \VPROD \VIEW[C,D]{T}.
\end{align*}

Figure <ref> depicts the hypergraphs
of $\VIEW[]{Q}$ and $\VIEW[]{Q'}$ (left), a free-top variable order for
$\VIEW[]{Q}$ that is also canonical for $\VIEW[]{Q'}$ (middle), and
the view tree for $\VIEW[]{Q}$ modeled on this variable order (right).
Since $\VIEW{Q}$ is free-connex acylic, we can compute the view tree in linear time and enumerate the result tuples of $\VIEW{Q}$ with constant delay, as explained in Section <ref>.
We next describe how to achieve constant-time update by exploiting
the fds. Figure <ref> shows the delta view trees obtained from the view tree for $\VIEW{Q}$ for single-tuple updates to $\VIEW{R}$, $\VIEW{S}$, and $\VIEW{T}$.

Consider first the update $\delta\VIEW[a,b]{R}$ to relation $\VIEW[]{R}$. The delta view $\delta\VIEW[b]{V^{@A}_{R}}$ is just a projection of the update tuple. The delta view $\delta\VIEW[b,c]{H^{@B}_{RS}}$ requires a lookup in $\VIEW[B,C]{S}$ for $B=b$. In general, there may be many $C$-values paired with $b$. However, under the fd $B\rightarrow C$, there is at most one $C$-value $c$ paired with $b$. Hence, the construction of this delta view takes constant time. Similarly, the delta view $\delta\VIEW[c,d]{H^{@C}_{RST}}$ requires a lookup in $\VIEW[C,D]{T}$ for $C=c$. Again, there may be many $D$-values paired with $c$, yet under the fd $C\rightarrow D$, there is at most one $D$-value $d$ paired with $c$. Hence, the construction of this delta view takes constant time, too.

Similar reasoning applies to the update $\delta\VIEW[b,c]{S}$. To compute the delta view $\delta\VIEW[c,b]{H^{@B}_{RS}}$, we need a constant-time lookup in the view $\VIEW[B]{V^{@A}_R}$ with $B=b$. Computing $\delta\VIEW[c,d]{H^{@C}_{RST}}$ takes constant time due to the fd $C\rightarrow D$, as with updates to  $\VIEW{R}$.
Processing the update $\delta\VIEW[c,d]{T}$ takes constant time without exploiting the fds: it only requires a lookup in the view $\VIEW[C]{V^{@B}_{RS}}$ with $C=c$.

§.§ Cyclic Queries

Our framework supports arbitrary conjunctive queries. Whereas for an acyclic join query the size of each view is asymptotically upper-bounded by the size of the query result, for a cyclic query views may be larger in size than the
query result.

In prior work [47], we show how to reduce the size of intermediate views
for cyclic queries  by extending view trees with indicator projections [6].  Such projections have no effect on the query result but can constrain view definitions (e.g., create cycles) and bring asymptotic savings in space and time.

We consider the triangle query:

\VIEW[~]{Q_{\vartriangle}} = \VSUM_{A}\VSUM_{B}\VSUM_{C} \VIEW[A,B]{R} \VPROD \VIEW[B,C]{S} \VPROD \VIEW[C,A]{T}

Figure <ref> shows the hypergraph of $Q_{\vartriangle}$ and the view tree constructed for the variable order $A-B-C$ by placing each relation directly under its lowest variable. We assume all relations are of size $\bigO{N}$. Computing the triangle query from scratch using a worst-case optimal join algorithm takes $\bigO{N^{3/2}}$ time [43].

In the given view tree (without the view in red), we first join $\VIEW{S}$ and $\VIEW{T}$ and then marginalize out $C$.
This view at node $C$ may contain $\bigO{N^2}$ pairs of $(A,B)$ values, which is larger than the worst-case size $\bigO{N^{3/2}}$.
However, by materializing the view at $C$, we enable single-tuple updates to $R$ in constant time; single-tuple updates to other relations take $\bigO{N}$ time.

To avoid the large intermediate result at variable $C$, we can change the view tree by placing the relation $R$ under variable $C$. Then, joining all three relations at node $C$ takes $\bigO{N^{3/2}}$ time. Updates to any relation now cause recomputation of a $3$-way join, like in first-order IVM. For single-tuple updates, recomputing deltas takes $\bigO{N}$ as only two of the three variables are bound to constants. In contrast, the first approach trades off space for time: We need $\bigO{N^2}$ space but then support $\bigO{1}$ updates to one of the three relations.

c]l@   l

at (-2.4, -2) (r) $R$;
at (2.4, -2) (r) $T$;
at (0, -5.75) (r) $S$;
[rotate=60,line width=0.1mm,fill opacity=0.8,fill=magenta!40] (-2.75,-0.4) ellipse (2.45cm and 0.8cm);
[rotate=-60,line width=0.1mm,fill opacity=0.8,fill=green!60] (2.75,-0.4) ellipse (2.45cm and 0.8cm);
[rotate=0,line width=0.1mm,fill opacity=0.8,fill=blue!40] (0,-4.4) ellipse (2.45cm and 0.8cm);
at (0, -1) (A) A;
at (-2, -4.35) (B) B;
at (2, -4.35) (C) C;

at (0, 0) (A) $\VIEW[~]{V^{@A}_{RST}}$;
at (0, -1) (B) $\VIEW[A]{V^{@B}_{RST}}$ edge[-] (A);
at (0, -2) (C) $\VIEW[A,B]{V^{@C}_{ST}}$ edge[-] (B);

at (2, -2) (R) $\VIEW[A,B]{R} \makebox[0pt][l]{$\phantom{\VIEW[A,B]{V^{@C}}}$} $ edge[-] (B);
at (-1.5, -3) (S) $\VIEW[B,C]{S}$ edge[-] (C);
[color=red] at (-0, -3.15) (S) $\VIEW[A,B]{\displaystyle\VEXISTS{A,B}{R}}$ edge[red,dashed] (C);
at (1.5, -3) (T) $\VIEW[C,A]{T}$ edge[-] (C);

(left) Hypergraph of the triangle query $Q_{\vartriangle}$; (right) View tree for the variable order $A - B - C$ with an indicator projection $\exists_{A,B}\VIEW{R}$.

c]@l@ l@

[thick,darkgray!80,line width=0.3mm] (0,0) – (-1,-2);
[thick,blue!80,line width=0.3mm] (0,0) – (1,-2);
[thick,orange!80,line width=0.3mm] (-1,-2) – (0,-4);
[thick,magenta!80,line width=0.3mm] (1,-2) – (0,-4);
[thick,olive!80,line width=0.3mm] (0,0) – (0,-4);

[fill=black] (0,0) circle (0.7mm);
[fill=black] (-1,-2) circle (0.7mm);
[fill=black] (1,-2) circle (0.7mm);
[fill=black] (0,-4) circle (0.7mm);

at (0,0.3) A;
at (-1.3,-2) B;
at (1.3,-2) D;
at (0.0,-4.3) C;

at (-0.85, -0.8) (r) R;
at (0.75, -0.8) (r) U;
at (-0.85, -3.2) (r) S;
at (0.75, -3.2) (r) T;
at (0.3, -2) (r) Y;

at (0, 0) (A) $\VIEW[~]{V^{@A}_{RSTUY}}$;
at (0, -1) (C) $\VIEW[A]{V^{@C}_{RSTUY}}$ edge[-] (A);
at (-1.8, -2) (B) $\VIEW[A,\!C]{V^{@B}_{RS}}$ edge[-] (C);
at (0, -2) (Y) $\VIEW[A,\!C]{Y}$ edge[-] (C);
at (1.8, -2) (D) $\VIEW[A,\!C]{V^{@D}_{TU}}$ edge[-] (C);
at (-2.6, -3) (R) $\VIEW[A,\!B]{R}$ edge[-] (B);
at (-1.0, -3) (S) $\VIEW[B,\!C]{S}$ edge[-] (B);
at (1.0, -3) (T) $\VIEW[C,\!D]{T}$ edge[-] (D);
at (2.6, -3) (U) $\VIEW[D,\!A]{U}$ edge[-] (D);

[color=red] at (-1.8, -3.8) (P1) $\VIEW[A,C]{\VEXISTS{A,C}Y}$ edge[red,dashed] (B);
[color=red] at (1.8, -3.8) (P2) $\VIEW[A,C]{\VEXISTS{A,C}Y}$ edge[red,dashed] (D);

(left) Hypergraph of the cyclic query $Q_{\boxslash}$; (right) View tree for the variable order $A - C - \{ B, D \}$ with indicator projections (in red).

The above example demonstrates how placing a relation under a different node in a view tree can create a cycle of relations and constrain the size of a view. This strategy, however, might not be always feasible or efficient: One relation might form multiple cycles of relations in different parts of a view tree – for example, in the cyclic $4$-loop
query $\VIEW[~]{Q_{\boxslash}}$ $=$
$\VSUM_{A}\VSUM_{B}\VSUM_{C} \VSUM_{D}$ $\VIEW[A,B]{R}\VPROD \VIEW[B,C]{S} \VPROD \VIEW[C,D]{T}
\VPROD \VIEW[D,A]{U} \VPROD \VIEW[A,C]{W}$ the chord relation $\VIEW{W}$ is part of two triangle subqueries. Since this relation cannot be duplicated in multiple subtrees (for correctness reasons so as to avoid multiplying the same payload several times instead of using it once), one would have to evaluate these subqueries in sequence, which yields a view tree that is higher and more expensive to maintain.

Indicator Projections.
Instead of moving relations in a view tree, we extend the tree with indicator projections that identify the active domains of these relations [6]. Such projections have no effect on the query result but can constrain view definitions (e.g., create cycles) and bring asymptotic savings in space and time.

We define a new unary operation $\VEXISTS{\mathcal{A}}{\VIEW{R}}$ that, given a relation $\VIEW{R}$ over schema
$\mathcal{S}$ with payloads from a ring $(\RING, \RINGPLUS, \RINGPROD, \RINGZERO, \RINGONE)$, and a set of attributes $\mathcal{A} \subseteq \mathcal{S}$, projects tuples from $\VIEW{R}$ with non-$\RINGZERO$ payload on $\mathcal{A}$ and assigns to these tuples the payload $\RINGONE$.

For a relation R over schema $\calS$ and $\calA \subseteq \calS$,
the indicator projection $\VEXISTS{\mathcal{A}}{\VIEW{R}}$ is a relation over $\calA$ such that
$\forall \vecnormal{t} \in \Dom(\calA)$:

\begin{align*}
\left( \textstyle\VEXISTS{\mathcal{A}}{\VIEW{R}} \right)[\vecnormal{t}] =
\begin{cases}
\RINGONE & \exists\vecnormal{s} \in\Dom(\mathcal{S}), \vecnormal{s}\in \VIEW{R}, \vecnormal{t} = \pi_{\mathcal{A}}(\vecnormal{s})\\
\RINGZERO & \text{otherwise}
\end{cases}
\end{align*}

The delta rule for $\VEXISTS{\mathcal{A}}$ is $\delta(\VEXISTS{\mathcal{A}}{\VIEW{R}}) = \VEXISTS{\mathcal{A}}(\VIEW{R} + \delta{\VIEW{R}}) - \VEXISTS{\mathcal{A}}{\VIEW{R}}$. This rule recomputes the query twice, once to insert new contents and once to delete the old contents, which clearly defeats the purpose of incremental computation. Note that some tuples might be unaffected by a given update $\delta{\VIEW{R}}$, so inserting those tuples and deleting them again is wasted work.

We observe that $\delta(\VEXISTS{\mathcal{A}}{\VIEW{R}})$ might change in the output only those tuples from $\VEXISTS{\mathcal{A}}{\delta{\VIEW{R}}}$. We exploit this restriction to refine the delta rule as: $\delta(\VEXISTS{\mathcal{A}}{\VIEW{R}}) = \VEXISTS{\mathcal{A}}{\delta{\VIEW{R}}} \VPROD (\VEXISTS{\mathcal{A}}(\VIEW{R} + \delta{\VIEW{R}}) - \VEXISTS{\mathcal{A}}{\VIEW{R}})$.

Indicator projections may change with updates to input relations. For instance, adding a tuple with a
new $\mathcal{A}$-value to $\VIEW{R}$ enlarges the result of $\VEXISTS{\mathcal{A}}\VIEW{R}$; similarly, deleting the last tuple with the given $\mathcal{A}$-value reduces the result. One change in the input may cause at most one change in the output: $|\delta{(\VEXISTS{\mathcal{A}}\VIEW{R})}| \le |\delta{\VIEW{R}}|$.

To facilitate the computation of $\delta{(\VEXISTS{\mathcal{A}}\VIEW{R})}$, we keep track of how many tuples with non-$\RINGZERO$ payloads project on each $\mathcal{A}$-value. For updating the payload of a tuple in $\VIEW{R}$ from $\RINGZERO$ to non-$\RINGZERO$ (or vice versa), we increase (decrease) the count corresponding to the given $\mathcal{A}$-value. If this count changes from $0$ to $1$ (meaning the $\mathcal{A}$-value is unique) or from $1$ to $0$ (meaning there are no more tuples with the $\mathcal{A}$-value), then $\delta{(\VEXISTS{\mathcal{A}}\VIEW{R})}$ contains a tuple of $\mathcal{A}$-values with the payload of $\RINGONE$ or $-\RINGONE$, respectively; otherwise, the delta is empty.

Consider a relation $\VIEW{R}$ over schema $\{A,B\}$ and
with payloads from a ring $(\RING, \RINGPLUS, \RINGPROD, \RINGZERO, \RINGONE)$. We want to maintain the result of the query $\VIEW[A]{Q} = \VEXISTS{A}\VIEW[A,B]{R}$. To compute $\VIEW[A]{\delta{Q}}$ for updates to $\VIEW{R}$ efficiently, we count the tuples from $\VIEW{R}$ with non-$\RINGZERO$ payloads for each $A$-value, denoted by $\VIEW[A]{CNT_{Q}}$. For example:

\begin{align*}
\begin{tabular}[t]{@{}l|@{~}c@{~}c@{~}c@{~}c@{}}
$\VIEW{R}$ & A & B \\
\midrule
& $a_1$ & $b_1$ & $\to$ & $r_1$ \\
& $a_1$ & $b_2$ & $\to$ & $r_2$ \\
& $a_2$ & $b_3$ & $\to$ & $r_3$ \\
\end{tabular}
\qquad
\begin{tabular}[t]{@{}l|@{~}c@{~}c@{~}c@{}}
$\VIEW{CNT_{Q}}$ & A \\
\midrule
& $a_1$ & $\to$ & $2$ \\
& $a_2$ & $\to$ & $1$ \\
\end{tabular}
\qquad
\begin{tabular}[t]{@{}l|@{~}c@{~}c@{~}c@{}}
$\VIEW{Q}$ & A \\
\midrule
& $a_1$ & $\to$ & $\RINGONE$ \\
& $a_2$ & $\to$ & $\RINGONE$ \\
\end{tabular}
\end{align*}

where $r_1$, $r_2$, and $r_3$ are non-$\RINGZERO$ payloads from $\RING$.

An update $\VIEW{\delta{R}} = \{ \tuple{a_1, b_2} \to -r_2 \}$ removes the tuple $\tuple{a_1,b_2}$ from $\VIEW{R}$, which in turn decreases $\VIEW[\text{$a_1$}]{CNT_{Q}}$ by $1$. Since there is still a tuple in $\VIEW{R}$ that projects on $a_1$, the result of $\VIEW{Q}$ remains unchanged.
A subsequent update $\{ \tuple{a_1, b_1} \to -r_1 \}$ to $\VIEW{R}$ drops the count for $a_1$ to $0$, which triggers a change in the output, $\VIEW{\delta{Q}} = \{ \tuple{a_1} \to -\RINGONE \}$.

3c$indicators(\text{view tree } \tau)$ : view tree

ab     $\VIEW{R}(\calS))$

[xscale=0.5, yscale=1]
at (0,-2)  (n4) $\VIEW{V_{rels}^{@X}}[keys]$;
at (-1,-3)  (n1) $\tau_1$ edge[-] (n4);
at (0,-3)  (n2) $\ldots$;
at (1,-3)  (n3) $\tau_k$ edge[-] (n4);

$\hat{\tau}_i = indicators(\tau_i)$  $\forall i\in[k]$

$\calR $ be the set of all relation symbols

$\calI = \{\VEXISTS{pk}\VIEW{R}\mid \VIEW{R} \in \calR \setminus \textsf{rels} \text{ and } \\[0.5ex]
\TAB\TAB\TAB\STAB pk = \sch(\VIEW{R}) \cap keys \neq \emptyset \}$

$\{I_1, \ldots , I_{\ell}\} = \textsf{GYO}^*(\calI,\textsf{rels})$

\begin{array}{@{~~}c@{~~}}
\tikz {
\node at (3.6,-1)  (n4) {$X$};
\node at (2.2,-1.75)  (n1) {$\hat{\tau}_1$} edge[-] (n4);
\node at (2.65,-1.75)  (n2) {$\ldots$};
\node at (3.2,-1.75)  (n3) {$\hat{\tau}_k$} edge[-] (n4);
\node at (4.0,-1.75)  (n3) {$I_1$} edge[-] (n4);
\node at (4.4,-1.75)  (n2) {$\ldots$};
\node at (4.9,-1.75)  (n3) {$I_\ell$} edge[-] (n4);
\end{array}  \right.$

Adding indicator projections to a view tree $\tau$.
Each view in $\tau$ gets as new children the indicator projections of relations that do not occur in the subtree rooted at the view  but form a cycle with those that occur.
$\textsf{GYO}^*$ is based on the GYO reduction [10].

View Trees with Indicator Projections.
Figure <ref> gives an algorithm that traverses a given view tree
recursively and extends it with indicator projections. At each view $\VIEW{V^{@X}_{rels}}$, the algorithm first computes a set
$\calI$ of indicator projections for those relations that share common variables with $\VIEW{V^{@X}_{rels}}$ and
do not appear in , hence do not take part
in the view definition.
Then, it chooses from this set those indicator projections
that form a cycle with the relations
in the subtree rooted at $\VIEW{V^{@X}_{rels}}$. To achieve this,
it uses a variant of the  reduction [10].
Given the hypergraph formed by
the hyperedges representing the indicator projections $\calI$ and the relations ,
repeatedly applies two rules until it
reaches a fixpoint: (1) Remove a node that only appears in one hyperedge; (2) Remove a
hyperedge that is included in another hyperedge. If the result of  is a hypergraph with
no nodes and one empty hyperedge, then the input hypergraph is acyclic. Otherwise,
the input hypergraph is cyclic and the output of  is a hypergraph with cycles. The
variant, dubbed $\textsf{GYO}^*$ in the procedure in Figure <ref>, returns the
hyperedges that originated from the indicator
projections in $\calI$ and contribute to this non-empty output hypergraph. The chosen indicator
projections become children of $\VIEW{V^{@X}_{rels}}$.

In a view tree with indicator projections, changes in one relation may propagate along multiple leaf-to-root paths. We propagate them in sequence, that is, updates to one relation are followed by a sequence of updates to its indicator projections.

The algorithm from Figure <ref> extends the view tree of the triangle query with an indicator projection $\VEXISTS{A,B}\VIEW[A,B]{R}$ placed below the view $\VIEW{V^{@C}_{ST}}$. This view at $C$ is now a cyclic join of the three relations, which can be computed in $\bigO{N^{3/2}}$ time. The indicator projection also reduces the size of this view to $\bigO{N}$.

Single-tuple updates to $S$ and $T$ still take linear time; however, bulk updates of size $\bigO{N}$ can now be processed in $\bigO{N^{3/2}}$ time, same as reevaluation. Updates to $R$ might affect the indicator projection: If a single-tuple update $\VIEW{\delta{R}}$ causes no change in the projection, then incremental maintenance takes constant time; otherwise, joining a tuple $\delta({\VEXISTS{A,B}\VIEW{R}})$ with $\VIEW{S}$ and $\VIEW{T}$ at node $C$ takes linear time. Bulk updates $\VIEW{\delta{R}}$ of size $\bigO{N}$ can also be processed in $\bigO{N^{3/2}}$ time. We conclude that using indicator projections in this query takes the best of both approaches from Example <ref>, namely faster incremental maintenance and more succinct view representation.

§ APPLICATIONS

This section highlights four applications of , including learning regression models, building Chow-Liu trees,
computing listing or factorized representations of the results of conjunctive queries,
and multiplying a sequence of matrices.
They behave the same in the key space, yet differ in the rings used to define the payloads.

§.§ Covariance Matrix and Linear Regression

We next introduce the covariance matrix ring used for training linear regression models.

Linear Regression.
Consider a training dataset that consists of $k$ samples with $(X_i)_{i\in[m-1]}$ features and a label $X_m$ arranged into a design matrix ${\bf M}$ of size $k \times m$; in our setting, this design matrix is the result of a join query. The goal of linear regression is to learn the parameters $\Th = \TR{[\theta_1 \ldots \theta_m]}$ of a linear function[We consider wlog: $\theta_1$ is the bias parameter and then $X_1=1$ for all tuples in the input data; $\theta_m$ remains fixed to $-1$ and corresponds to the label/response $X_m$ in the data.] $f(X_1,...,X_{m-1}) = \sum_{i\in[m-1]}\theta_iX_i$ best satisfying ${\bf M} \Th \approx {\bf 0}_{k\times 1}$, where ${\bf 0}_{k\times 1}$ is the zero matrix of size $k \times 1$.

We can solve this optimization problem using batch gradient descent. This method iteratively updates the model parameters in the direction of the gradient to decrease the squared error loss and eventually converge to the optimal value. Each convergence step iterates over the entire training dataset to update the parameters, $\Th := \Th - \alpha\TR{\bf M}{\bf M}\Th$, where $\alpha$ is an adjustable step size. The complexity of each step is $\bigO{mk}$. The covariance matrix  $\TR{\bf M}{\bf M}$ quantifies the degree of correlation for each pair of features (or feature and label) in the data. Its computation can be done once for all convergence steps [60]. This is crucial for performance in case $m \ll k$ as each iteration step now avoids processing the entire training dataset and takes time $\bigO{m^2}$.

We next show how to compute the covariance matrix assuming all features have continuous domains; we consider the case with categorical features later on.

The covariance matrix $\TR{\bf M}{\bf M}$ accounts for the interactions SUM(X*Y) of variables $X$ and $Y$ with continuous domains.
We can factorize their computation over training datasets defined by arbitrary join queries [60]. We can further share their computation by casting the covariance matrix computation as the computation of one compound aggregate.
This compound aggregate is a triple
$(\LRringC,\LRringS,\LRringQ)$, where $\LRringC$ is the number of tuples in the training dataset (size $k$ of the design matrix), $\LRringS$ is an $m\times 1$ matrix (or vector) with one sum of values per variable, and $\LRringQ$ is an $m\times m$ matrix of sums of products of values for any two variables. The covariance matrix computation can be captured by a ring.

Fix a ring $(\RING, +, *, \RINGZERO, \RINGONE)$ and $m \in \mathbb{N}$.
Let $\mathsf{C}$ denote the set of triples $({\bf D}, {\bf D}^{m}, {\bf D}^{m \times m})$,
$\RINGZERO^{\mathsf{C}} = (\RINGZERO, \RINGZERO_{m \times 1}, \RINGZERO_{m \times m})$, and
$\RINGONE^{\mathsf{C}} = (\RINGONE, \RINGZERO_{m \times 1}, \RINGZERO_{m \times m})$,
where $\RINGZERO_{m \times n}$ is an $m \times n$ matrix with all zeros from $\RING$.
For $a = (\LRringC_a, \LRringS_a, \LRringQ_a) \in {\mathsf{C}}$ and $b = (\LRringC_b, \LRringS_b, \LRringQ_b) \in {\mathsf{C}}$, define the operations $+^{\mathsf{C}}$ and $*^{\mathsf{C}}$ over ${\mathsf{C}}$ as:

\begin{align*}
& a +^{\mathsf{C}} b = (\LRringC_a {\,\scriptstyle+\,} \LRringC_b,\; \LRringS_a {\,\scriptstyle+\,} \LRringS_b,\; \LRringQ_a {\,\scriptstyle+\,} \LRringQ_b) \\
&a *^{\mathsf{C}} b \hspace{-0.05em}=\hspace{-0.05em} (\LRringC_a \LRringC_b,\; \LRringC_b \LRringS_a {\,\scriptstyle+\,} \LRringC_a \LRringS_b,\; \LRringC_b \LRringQ_a {\,\scriptstyle+\,} \LRringC_a \LRringQ_b {\,\scriptstyle+\,} \LRringS_a \TR{\LRringS_b} {\,\scriptstyle+\,} \LRringS_b \TR{\LRringS_a})
\end{align*}

using matrix addition, scalar multiplication, and matrix multiplication over $\RING$.
We refer to $(\mathsf{C}, +^{\mathsf{C}}, *^{\mathsf{C}}, \RINGZERO^\mathsf{C}, \RINGONE^\mathsf{C})$ as the covariance structure of degree $m$ over $\RING$.

For $m\in\mathbb{N}$ and a ring $\RING$, the covariance structure of degree $m$ over $\RING$ forms a commutative ring.

The continuous covariance ring of degree $m$ is the covariance structure of degree $m$ over $\mathbb{R}$.

We next show how to use this ring to compute the covariance matrix over a training dataset defined by a join with relations $(\VIEW{R_i})_{i\in[n]}$ over variables $(X_j)_{j\in[m]}$. The payload of each tuple in a relation is the identity $\RINGONE^{\mathsf{C}}$ from the continuous covariance ring of degree $m$. The query computing the covariance matrix is:

\begin{align*}
\quad \VIEW{Q} = \textstyle\VSUM_{X_1}{} \cdots \VSUM_{X_m}{\VPRODBIG_{i \in [n]} \VIEW[\mathit{\sch(R_i)}]{R_i}}
\end{align*}

For each $X_j$-value $x$, the lifting function is $g_{X_j}(x) = (1, \LRringS, \LRringQ)$, where $\LRringS$ is an $m \times 1$ vector with all zeros except the value of $x$ at position $j$, i.e., $\LRringS_j=x$, and $\LRringQ$ is an $m \times m$ matrix with all zeros except the value $x^2$ at position $(j,j)$: $\LRringQ_{(j,j)}=x^2$.

We show how to compute the covariance matrix using the join and view tree from
Figure <ref> and the database from Figure <ref>.
We assume alphabetical order of the five variables in the covariance matrix. The leaf relations $\VIEW{R}$, $\VIEW{S}$, and $\VIEW{T}$ map tuples to $\RINGONE^{\mathsf{C}}$ from the continuous covariance ring of degree 5.

In the view $\VIEW{V^{@D}_{T}}$, each $D$-value $d$ is lifted to a triple $(1, \LRringS, \LRringQ)$, where $\LRringS$ is a $5\times 1$ vector with one non-zero element $\LRringS_4=d$, and $\LRringQ$ is a $(5 \times 5)$ matrix with one non-zero element $\LRringQ_{(4,4)} = d^2$. Those covariance triples with the same key $c$ are summed up, yielding:

\begin{align*}
\quad \VIEW{V^{@D}_{T}}[c_1] &= (1,\LRringS_4=d_1, \LRringQ_{(4,4)}=d_1^2) \\
\quad \VIEW{V^{@D}_{T}}[c_2] &= (2,\LRringS_4=d_2+d_3, \LRringQ_{(4,4)}=d_2^2+d_3^2) \\
\quad \VIEW{V^{@D}_{T}}[c_3] &= (1,\LRringS_4=d_4, \LRringQ_{(4,4)}=d_4^2)
\end{align*}

The views $\VIEW{V^{@B}_{R}}$ and $\VIEW{V^{@E}_{S}}$ are computed similarly.
The view $\VIEW{V^{@C}_{ST}}$ joins $\VIEW{V^{@D}_{T}}$ and $\VIEW{V^{@E}_{S}}$ and marginalizes $C$. For instance, the payload for the key $a_2$ is:

\begin{align*}
\VIEW{V^{@C}_{ST}}[a_2] &= \VIEW[\mathit{c_2}]{V^{@D}_{T}} *^{\mathsf{C}} \VIEW[\mathit{a_2, c_2}]{V^{@E}_{S}} *^{\mathsf{C}} g_{C}(c_2) \\[0.5ex]
\VIEW[\mathit{c_2}]{V^{@D}_{T}}
\left(\!
\begin{vmatrix}
0 \\ 0 \\ 0 \\ 0 \\ e_4
\end{vmatrix},
\begin{vmatrix}
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & e_4^2
\end{vmatrix}
\right)
\hspace{-0.2em} *^{\mathsf{C}} \hspace{-0.2em}
\left(\!
\begin{vmatrix}
0 \\ 0 \\ c_2 \\ 0 \\ 0
\end{vmatrix},
\begin{vmatrix}
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
c_2^2 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0
\end{vmatrix}
\right)\\[0.5ex]
\left(
\begin{vmatrix}
0 \\ 0 \\ 2 c_2 \\ d_2 + d_3 \\ 2 e_4
\end{vmatrix},
\begin{vmatrix}
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 2c_2^2 & c_2(d_2 + d_3) & 2 c_2 e_4 \\
0 & 0 & c_2(d_2 + d_3) & d_2^2 + d_3^2 & (d_2 + d_3)e_4 \\
0 & 0 & 2 c_2 e_4 & (d_2 + d_3)e_4 & 2 e_4^2
\end{vmatrix}
\right)
\end{align*}

The root view $\VIEW{V^{@A}_{RST}}$ maps the empty tuple to the ring element $\sum_{i\in[2]}\VIEW[a_i]{V^{@B}_{R}} *^{\mathsf{C}} \VIEW[a_i]{V^{@C}_{ST}} *^{\mathsf{C}} g_{A}(a_i)$.
This payload has aggregates for the entire join result: the count of tuples in the result, the vector with one sum of values per variable, and the covariance matrix.

Linear Regression with Categorical Variables.
Real-world datasets consists of both continuous and categorical variables. The latter take on values from predefined sets of possible values (categories). It is common practice to one-hot encode categorical variables as indicator vectors. This encoding can blow up the size of the covariance matrix and increase its sparsity.

Instead of blowing up the covariance matrix with one-hot encoding, we can capture the interactions between continuous and categorical variables as group-by queries:
SUM(X) group by $Y$, when $X$ is continuous and $Y$ is categorical, and
SUM(1) group by $X$ and $Y$, when $X$ and $Y$ are categorical.
Using the group-by queries ensures a compact representation of such interactions by considering only those categories and interactions that exist in the join result.
We can encode those interactions as values from the relational data ring, introduced next.

Let $\mathbb{F}[\mathbb{R}]$ denote the set of relations over the $\mathbb{R}$ ring,
the zero $\RINGZERO$ in $\mathbb{F}[\mathbb{R}]$ is the empty relation $\{\}$, which maps every tuple to  $0\in\mathbb{R}$, and the identity ${\bf 1}$ is the relation $\{ () \rightarrow 1 \}$, which maps the empty tuple to $1 \in\mathbb{R}$ and all other tuples to $0 \in\mathbb{R}$. The structure $(\mathbb{F}[\mathbb{R}], \VPLUS, \VPROD, \RINGZERO, \RINGONE)$ forms the relational data ring.[
To form a proper ring, we need a generalization [32] of relations and join and union operators, where:
tuples have their own schemas; union applies to tuples with possibly different schemas; join accounts for multiple derivations of output tuples. For our needs this generalization is not necessary.]

We generalize the continuous covariance ring from Definition <ref> to uniformly treat continuous and categorical variables as follows:
we use relations from the relational data ring as values in $c$, $\LRringS$, and $\LRringQ$ instead of scalars;
we use union and join instead of scalar addition and multiplication;
we use the empty relation $\RINGZERO$ instead of the zero scalar.
The operations $+^\mathsf{C}$ and $*^\mathsf{C}$ over triples $(c, \LRringS, \LRringQ)$ remain unchanged.

The generalized covariance ring of degree $m$ is the covariance structure of degree $m$ over $\mathbb{F}[\mathbb{R}]$.

For clarity, we show the operations $+^\mathsf{C}$ and $*^\mathsf{C}$ of the generalized covariance ring $\mathsf{C}$ of degree $m$.

$$(\LRringC', \LRringS', \LRringQ') +^\mathsf{C} (\LRringC'', \LRringS'', \LRringQ'') = (\LRringC, \LRringS, \LRringQ)$$

$\LRringC = c' \VPLUS c''$,
$\LRringS_j = \LRringS'_{j} \uplus \LRringS''_j$,
$\LRringQ_{(i,j)} = \LRringQ''_{(i,j)} \uplus \LRringQ''_{(i,j)}$;

$$(\LRringC', \LRringS', \LRringQ') *^\mathsf{C} (\LRringC'', \LRringS'', \LRringQ'') = (\LRringC, \LRringS, \LRringQ)$$

$\LRringC = c' \VPROD c''$,
$\LRringS_j = (\LRringC'' \VPROD \LRringS'_{j}) \uplus (\LRringC' \VPROD \LRringS''_j)$, and
$\LRringQ_{(i,j)} = (\LRringC'' \VPROD \LRringQ'_{(i,j)}) \uplus (\LRringC' \VPROD \LRringQ''_{(i,j)}) \uplus (\LRringS'_{i} \VPROD \LRringS''_{j}) \uplus (\LRringS''_{i} \VPROD \LRringS'_{j})$.

The lifting function $g_{X_j}$ now depends on whether $X_j$ is continuous or categorical.
For each $X_j$-value $x$,
$g_{X_j}(x) = (\bm{1}, \LRringS, \LRringQ)$,
where $\bm{1} = \{() \to 1\}$,
$\bm{s}$ is an $m\times1$ vector with all $\RINGZERO$s
except $\LRringS_j = \{ () \to x \}$ if $X_j$ is continuous and $\LRringS_j =\{ x \to 1 \}$ otherwise,
and $\LRringQ$ is an $m \times m$ matrix with all $\RINGZERO$s
except $\LRringQ_{(j,j)} = \{ () \to x^2 \}$ if $X_j$ is continuous and $\bm{Q}_{(j,j)} = \{ x \to 1 \}$ otherwise.

We compute the covariance matrix using the view tree and database from
Example <ref> assuming that $C$ is categorical.

Since $B$, $D$, and $E$ are continuous,
the contents of $\VIEW{V^{@B}_{R}}$, $\VIEW{V^{@D}_{T}}$, and $\VIEW{V^{@E}_{S}}$ are similar to those of Example <ref>
except that every scalar value $x$ in their payloads is replaced by the relation $\{ () \to x \}$.
The view $\VIEW{V^{@C}_{ST}}$ marginalizes $C$, lifting every $C$-value $c$ to $(\RINGONE, \LRringS_3 = \{c \to 1\},  \LRringQ_{(3,3)} = \{ c \to 1\})$, and the other entries in $\LRringS$ and $\LRringQ$ are $\RINGZERO$s.
The payload $\VIEW{V^{@C}_{ST}}[a_2]$ encodes
the result of SUM(1) group by $C$ as $\LRringS_3 = \LRringQ_{(3,3)} = \{ c_2 \to 2 \}$,
the result of SUM(D) group by $C$ as $\LRringQ_{(3,4)} = \{ c_2 \to d_2 + d_3 \}$, and
the result of SUM(E) group by $C$ as $\LRringQ_{(3,5)} = \{ c_2 \to 2e_4 \}$. The remaining entries in the payload $\VIEW{V^{@C}_{ST}}[a_2]$ are relations mapping the empty tuple to the same scalar value from $\VIEW{V^{@C}_{ST}}[a_2]$ in
Example <ref>.
The root view $\VIEW{V^{@A}_{RST}}$ computes the payload associated with the empty tuple in the same manner as in the continuous-only case but under the generalized covariance ring.

For performance reasons, we only store as payloads blocks of matrices with non-zero values and assemble larger matrices as the computation progresses towards the root of the view tree. We further exploit the symmetry of the covariance matrix to compute only the entries above and including the diagonal.
For the generalized covariance ring, we store relations, which have the empty tuple as key, as scalar values.

§.§ Mutual Information and Chow-Liu Tree

The mutual information (MI) of two random variables $X$ and $Y$ quantifies their degree of correlation [42]:

\[
I(X,Y) = \hspace{-0.3cm} \sum_{x \in \Dom{(X)}} \sum_{y \in \Dom{(Y)}} p_{XY}(x,y) \log \frac{p_{XY}(x,y)}{p_X(x)p_Y(y)}
\]

where $p_{XY}(x,y)$ is the joint probability of $X=x$ and $Y=y$, and $p_X(x)$ and $p_Y(y)$ are the marginal probabilities of $X = x$ and $Y = y$, respectively.
A value close to $0$ means the variables are almost independent, while a large value means they are highly correlated.
It can be used to identify variables that predict a given label variable and can thus be used for model selection [42].

In our case, we are given the joint probability of several categorical variables as a relation, or the join of several relations. The probabilities defining the MI of any pair of variables can be computed as group-by aggregates over this relation. Let
$C_{\emptyset} = {\tt SUM(1)}$, $C_{X} = {\tt SUM(1)}$ group by $X$, $C_{Y} = {\tt SUM(1)}$ group by $Y$, and $C_{XY} = {\tt SUM(1)}$ group by $X,Y$. Then,
$p_{XY}(x,y) = \frac{C_{XY}(x,y)}{C_{\emptyset}}$,
$p_{X}(x) = \frac{C_{X}(x)}{C_{\emptyset}}$,
$p_{Y}(y) = \frac{C_{Y}(y)}{C_{\emptyset}}$, and

\[
I(X,Y) = \hspace{-0.4cm} \sum_{x \in \Dom{(X)}} \sum_{y \in \Dom{(Y)}} \frac{C_{XY}(x,y)}{C_{\emptyset}} \log \frac{C_\emptyset C_{XY}(x,y)}{C_{X}(x)C_{Y}(y)}
\]

The aggregates $C_\emptyset$, $C_X$, and $C_{XY}$ define the covariance matrix over categorical variables, so we can use the generalized covariance ring to compute and maintain them
(Section <ref>). To compute the MI for continuous variables, we first discretize their domains into finitely many bins, so we turn them into categorical variables.

Mutual information is used for learning the structure of Bayesian networks.
Let a graph with one node per variable and one edge per pair of variables weighted by their MI,
a Chow-Liu tree is a maximum weight spanning tree.
The Chow-Liu algorithm [19] constructs such a tree  in several rounds:
it starts with a single node in the tree and in each round it connects a new node to a node already in the tree such that their pairwise MI is maximal among all pairs of variables not chosen yet.

§.§ Factorized Representation of Query Results

Our framework can also support scenarios where the view payloads are themselves relations representing results of conjunctive queries, or even their factorized representations. Factorized representations can be much smaller than the listing representation of a query result [54], with orders of magnitude size gaps reported in practice [60]. They nevertheless remain lossless and support constant-delay enumeration of the tuples in the query result as well as subsequent aggregate processing in one pass. Besides the factorized view computation and the factorizable updates, this is the third instance where our framework exploits factorization.

We store entire relations as payloads using a variant of the relational data ring (c.f. Definition <ref>) where values are relations over the $\mathbb{Z}$ ring. We denote this ring as $\mathbb{F}[\mathbb{Z}]$.
When marginalizing a variable, we move its values from the key space to the payload space. The tuple payloads in a view are now relations over the same schema. These relations have themselves payloads in the $\mathbb{Z}$ ring used to maintain the multiplicities of their tuples.

We model conjunctive queries as count queries that marginalize every variable but use different lifting functions for the free and bound variables.
For a free variable $X$ and any of its values $x$, we define $g_{X}(x) = \{ x \to 1 \}$, i.e., the lifting function
maps $x$ to the unary relation that consists of the single value $x$ whose payload is $1$.
In case $X$ is bound, we define $g_{X}(x) = \RINGONE = \{ () \to 1 \}$, i.e.,
the lifting function maps $x$ to the identity element $\RINGONE$ of the relational data ring.
This element is the unique relation that consist of the empty tuple whose payload is $1$.
We have relational operations occurring at two levels: for keys, we join views and marginalize variables as before; for payloads, we interpret multiplication and addition of payloads as join and union of relations.

Consider the conjunctive query

\begin{align*}
Q(A,B,C,D) = R(A,B), S(A,C,E), T(C,D)
\end{align*}

over the three relations from Figure <ref>, where each tuple gets the identity payload $\{ \tuple{} \to 1 \} \in \mathbb{F}[\mathbb{Z}]$. The corresponding view marginalizes all the variables:

\begin{align*}
\VIEW[~]Q = \textstyle\VSUM_{A}\ldots\VSUM_{E} \VIEW[A,B]{R} \VPROD \VIEW[A,C,E]{S} \VPROD \VIEW[C,D]{T}
\end{align*}

The lifting function for $E$ maps each value to $\{() \to 1 \}$, while the lifting functions for all other variables map value $x$ to $\{x \to 1 \}$.

Figure <ref> shows the contents of the views with relational data payloads (in black and red) for the view tree from Figure <ref> and the database from Figure <ref>. The view keys gradually move to payloads as the computation progresses towards the root. The view definitions are identical to those of the COUNT query (but under a different ring!). The view $\VIEW{V^{@D}_{T}}$ lifts each $D$-value $d$ from $\VIEW{T}$ to the relation $\{ d \to 1 \}$ over schema $\{D\}$, multiplies (joins) it with the payload $\RINGONE$ of each tuple, and sums up (union) all payloads with the same $c$-value. The views at $\VIEW{V_R^{@B}}$ and $\VIEW{V_S^{@E}}$ are computed similarly, except the latter lifts $e$-values to $\RINGONE$ since $E$ is a bound variable.
The view $\VIEW{V^{@C}_{ST}}$ assigns to each $A$-value a payload that is a union of Cartesian products of the payloads of its children and the lifted $C$-value. The root view $\VIEW{V^{@A}_{RST}}$ similarly computes the payload of the empty tuple, which represents the query result (both views are at the right).

[xscale=1.8, yscale=1.01]

[text=blue, anchor=north west] at (3, 1)

$()$     $\to$     $\VIEW[\;]{V^{@A}_{RST}}$
$\tuple{}$     $\rightarrow$

$a_1$     $\rightarrow$     $8$

$a_2$     $\rightarrow$     $2$

[text=red, anchor=north east] at (6.7, 1)

$()$     $\rightarrow$      $\VIEW[\;]{V^{@A}_{RST}}$
$\tuple{}$     $\rightarrow$

$\mathsf{A}$     $\mathsf{B}$     $\mathsf{C}$     $\mathsf{D}$

$a_1$     $b_1$     $c_1$     $d_1$     $\rightarrow$     $2$

$a_1$     $b_1$     $c_2$     $d_2$     $\rightarrow$     $1$

$a_1$     $b_1$     $c_2$     $d_3$     $\rightarrow$     $1$

$a_1$     $b_2$     $c_1$     $d_1$     $\rightarrow$     $2$

$a_1$     $b_2$     $c_2$     $d_2$     $\rightarrow$     $1$

$a_1$     $b_2$     $c_2$     $d_3$     $\rightarrow$     $1$

$a_2$     $b_3$     $c_2$     $d_2$     $\rightarrow$     $1$

$a_2$     $b_3$     $c_2$     $d_3$     $\rightarrow$     $1$

[text=blue, anchor=north west] at (3, -1.4)

$\mathsf{A}$     $\rightarrow$     $\VIEW[A]{V^{@C}_{ST}}$
$a_1$     $\rightarrow$

$c_1$     $\rightarrow$     $2$

$c_2$     $\rightarrow$     $2$

0mm4mm     $a_2$     $\rightarrow$

$c_2$     $\rightarrow$     $2$

[text=red, anchor=south east] at (6.7, -7.2)

$\mathsf{A}$     $\to$      $\VIEW[A]{V^{@C}_{ST}}$
$a_1$     $\rightarrow$

$\mathsf{C}$     $\mathsf{D}$

$c_1$     $d_1$     $\rightarrow$     $2$

$c_2$     $d_2$     $\rightarrow$     $1$

$c_2$     $d_3$     $\rightarrow$     $1$

0mm6mm     $a_2$     $\rightarrow$

$\mathsf{C}$     $\mathsf{D}$

$c_2$     $d_2$     $\rightarrow$     $1$

$c_2$     $d_3$     $\rightarrow$     $1$

[anchor=south west] at (3, -7.2)

$\mathsf{A}$     $\mathsf{C}$     $\to$     $\VIEW[A,C]{V^{@E}_{S}}$
$a_1$     $c_1$     $\rightarrow$

$\tuple{}$     $\rightarrow$     $2$

0mm3mm     $a_1$     $c_2$     $\rightarrow$

$\tuple{}$     $\rightarrow$     $1$

0mm3mm     $a_2$     $c_2$     $\rightarrow$

$\tuple{}$     $\rightarrow$     $1$

[anchor=north west] at (1, 1)

$\mathsf{A}$     $\to$     $\VIEW[A]{V^{@B}_{R}}$
$a_1$     $\rightarrow$

$b_1$     $\rightarrow$     $1$

$b_2$     $\rightarrow$     $1$

0mm4mm     $a_2$     $\rightarrow$

$b_3$     $\rightarrow$     $1$

0mm4mm     $a_3$     $\rightarrow$

$b_4$     $\rightarrow$     $1$

[anchor=south west] at (1, -7.2)

$\mathsf{C}$     $\to$     $\VIEW[C]{V^{@D}_{T}}$
$c_1$     $\rightarrow$

$d_1$     $\rightarrow$     $1$

0mm6mm     $c_2$     $\rightarrow$

$d_2$     $\rightarrow$     $1$

$d_3$     $\rightarrow$     $1$

0mm4.5mm     $c_3$     $\rightarrow$

$d_4$     $\rightarrow$     $1$

Computing the query from Example <ref>
over the database
in Figure <ref>
and the relational ring, where $\forall i\in[12]: p_i=\{ () \to 1 \}$.
The computation uses
the view tree $\tau$
in Figure <ref>.
The red views (rightmost column) have payloads storing the listing representation of the intermediate and final query results. The blue views (top two views in the middle column) encode a factorized representation of these results distributed over their payloads. The remaining (black) views remain the same for both representations.

We next show how to construct a factorized representation of the query result. In contrast to the scenarios discussed above, this representation is not available as one payload at the root view, but distributed over the payloads of all views. This hierarchy of payloads, linked via the keys of the views, becomes the factorized representation. A further difference lies with the multiplication operation. For the listing representation, the multiplication is the Cartesian product. For a given view, it is used to concatenate payloads from its child views. For the factorized representation, we further project away values for all but the marginalized variable. More precisely, for each view $\VIEW[\mathcal{S}]{V^{@X}_{rels}}$ and each of its keys $a_{\mathcal{S}}$, let $\VIEW[\mathcal{T}]{P} = \VIEW[a_\mathcal{S}]{V^{@X}_{rels}}$ be the corresponding payload relation. Then, instead of computing this payload, we compute $\VSUM_{Y\in \mathcal{T}-\{X\}}\VIEW[\mathcal{T}]{P}$ by marginalizing the variables in $\mathcal{T}-\{X\}$ and summing up the multiplicities of the tuples in $\VIEW[\mathcal{T}]{P}$ with the same $X$-value.

We continue Example <ref>.
Figure <ref> shows the contents of the views with factorized payloads (first two columns in black and blue).
Each view stores relational payloads that have the schema of the marginalized variable.
Together, these payloads form a factorized representation over the variable order $\omega$ used to define the view tree in Figure <ref>. At the top of the factorization, we have a union of two $A$-values: $a_1$ and $a_2$. This is stored in the payloads of (middle) $\VIEW[\;]{V^{A}_{RST}}$. The payloads of (middle) $\VIEW[A]{V^{@C}_{ST}}$ store a union of $C$-values $c_1$ and $c_2$ under $a_1$, and a singleton union of $c_2$ under $a_2$. The payloads of $\VIEW[A]{V^{@B}_R}$ store a union of $B$-values $b_1$ and $b_2$ under $a_1$ and a singleton union of $b_3$ under $a_2$. Note the (conditional) independence of the variables $B$ and $C$ given a value for $A$. This is key to succinctness of factorization. In contrast, the listing representation explicitly materializes all pairings of $B$ and $C$-values for each $A$-value, as shown in the payload of (right) $\VIEW[\;]{V^{A}_{RST}}$. Furthermore, the variable $D$ is independent of the other variables given $C$. This is a further source of succinctness in the factorization: Even though $c_2$ occurs under both $a_1$ and $a_2$, the relations under $c_2$, in this case the union of $d_2$ and $d_3$, is only stored once in $\VIEW[C]{V^{@D}_T}$. Each value in the factorization keeps a multiplicity, that is, the number of its derivations from the input data. This is necessary for maintenance.

This factorization is over a variable order that can be used for all queries with same body and different free variables: As long as their free variables sit on top of the bound variables, the variable order is valid and so is the factorization over it. For instance, if the variable $D$ were not free, then the factorization for the new query would be the same except that we would discard the $D$-values from the payload of the view $\VIEW{V^{@D}_{T}}$.

§.§ Matrix Chain Multiplication

Consider the problem of computing a product of a sequence of matrices $\bm{A}_1, \ldots, \bm{A}_n$ over some ring $\RING$, where matrix $\bm{A}_i[x_i, x_{i+1}]$ has the size $p_{i} \times p_{i+1}$, $i \in [n]$. The product $\bm{A} = \bm{A}_1 \cdots \bm{A}_n$ is a matrix of size $p_1 \times p_{n+1}$ and can be formulated as follows:

\begin{align*}
\bm{A}[x_1, x_{n+1}] = \sum_{x_2 \in[p_2]} \cdots \sum_{x_n\in [p_n]} \prod_{i\in[n]} \bm{A}_i[x_i, x_{i+1}]
\end{align*}

We model a matrix $\bm{A}_i$ as a relation $\VIEW[X_i, X_{i+1}]{A_i}$ with the payload carrying matrix values. The query that computes the matrix $\bm{A}$ is:

\begin{align*}
\VIEW[X_1, X_{n+1}]{A} = \VSUM_{X_2} \cdots \VSUM_{X_n} \VPRODBIG_{i \in [n]} \VIEW[X_i, X_{i+1}]{A_i}
\end{align*}

where each of the lifting functions $\{g_{X_j}\}_{j \in [2,n]}$ maps any key value to payload $\RINGONE\in\RING$.
Different variable orders lead to different evaluation plans for matrix chain multiplication. The optimal variable order corresponds to the optimal sequence of matrix multiplications that minimizes the overall multiplication cost, which is the textbook Matrix Chain Multiplication problem [20].

Consider a multiplication chain of $4$ matrices of equal size $p \times p$ encoded as relations $\VIEW[X_i, X_{i+1}]{A_i}$. Let $\mathcal{F} = \{ X_1, X_5 \}$ be the set of free variables and $\omega$ be the variable order $X_1 - X_5 - X_3 - \{ X_2, X_4 \}$, i.e., $X_2$ and $X_4$ are children of $X_3$, with the matrix relations placed below the leaf variables in $\omega$. The view tree $\tau(\omega, \mathcal{F})$ has the following views (from bottom to top; the views at $X_5$ and $X_1$ are equivalent to the view at $X_3$):

\begin{align*}
\VIEW[X_1,X_3]{V^{@X_2}_{A_1A_2}} &= \textstyle\VSUM_{X_2} \VIEW[X_1,X_2]{A_1} \VPROD \VIEW[X_2,X_3]{A_2} \\
\VIEW[X_3,X_5]{V^{@X_4}_{A_3A_4}} &= \textstyle\VSUM_{X_4} \VIEW[X_3,X_4]{A_3} \VPROD \VIEW[X_4,X_5]{A_4} \\
\VIEW[X_1,X_5]{V^{@X_3}_{A_1A_2A_3A_4}} &=\hspace{-0.05em} \textstyle\VSUM_{X_3}\hspace{-0.05em} \VIEW[X_1,X_3]{V^{@X_2}_{A_1A_2}} \hspace{-0.05em}\VPROD\hspace{-0.05em} \VIEW[X_3,X_5]{V^{@X_4}_{A_3A_4}}
\end{align*}

Recomputing these views from scratch for each update to an input matrix takes $\bigO{p^3}$ time. A single-value change in any input matrix causes changes in one row or column of the parent view, and propagating them to compute the final delta view takes $\bigO{p^2}$ time.

Updates to $\VIEW{A_2}$ and $\VIEW{A_3}$ change every value in $\VIEW{A}$.
In case of a longer matrix chain, propagating $\VIEW{\delta{A}}$ further requires $\bigO{p^3}$ matrix multiplications, same as recomputation.

We exploit factorization to contain the effect of such changes. For instance, if $\VIEW{\delta{A_2}}$ is a factorizable update  expressible as
$\VIEW[X_2,X_3]{\delta{A_2}} = \VIEW[X_2]{u} \VPROD \VIEW[X_3]{v}$ (see Section <ref>), then we can propagate deltas more efficiently, as products of

\begin{align*}
\quad&\VIEW[X_1,X_3]{\delta{V}^{@X_2}_{A_1A_2}} = \underbrace{\left( \textstyle\VSUM_{X_2} \VIEW[X_1,X_2]{A_1} \VPROD \VIEW[X_2]{u} \right)}_{\VIEW[X_1]{u_2}} \VPROD \VIEW[X_3]{v} \\
&\VIEW[X_1,X_5]{\delta{V}^{@X_3}_{A_1A_2A_3A_4}} = \VIEW[X_1]{u_2} \VPROD \left( \textstyle\VSUM_{X_3} \VIEW[X_3]{v} \VPROD \VIEW[X_3,X_5]{V^{@X_4}_{A_3A_4}} \right)
\end{align*}

Using such factorizable updates enables the incremental computation in $\bigO{p^2}$ time. The final delta is also in factorized form, suitable for further propagation.

In general, for a chain of $k$ matrices of size $p \times p$, using a binary view tree of the lowest depth, incremental maintenance with factorizable updates takes $\bigO{p^2\log{k}}$ time, while reevaluation takes $\bigO{p^3 k}$ time. The space needed in both cases is $\bigO{p^2 k}$.

The above example recovers the main idea of LINVIEW [45]: use factorization in the incremental computation of linear algebra programs where matrix changes are encoded as vector outer products, $\delta{A} = u \TR{v}$. Such rank-$1$ updates can capture many practical update patterns such as perturbations of one complete row or column, or even changes of the whole matrix when the same vector is added to every row or column. generalizes this idea to arbitrary join-aggregate queries.

§ COMPLEXITY ANALYSIS

Consider a query $Q$ over a database $\db$, a set of updatable relations $\mathcal{U}$, and a view tree $\tau$ that corresponds to the query $Q$.
We analyze the time complexity of processing single-tuple updates to each relation in $\mathcal{U}$ and the space complexity of the materialized views in $\tau$.

§ EXPERIMENTS

This section reports our experimental findings with our system and three competitors: first-order IVM (), DBToaster's higher-order IVM (), and Apache Flink. We first summarize our findings.

* For maintaining covariance matrices over continuous variables, outperforms and by up to three orders of magnitude. This is primarily due to the use of the covariance ring in , which can capture the maintenance for an entire covariance matrix of 100-800 entries with under ten views. In contrast, requires 600-3,000 views, while needs as many delta queries as matrix entries (136 - 820).
A similar conclusion holds for maintaining covariance matrices over continuous and categorical variables and also only over categorical variables, albeit the performance gap becomes smaller.  Thanks to the covariance ring, also has a low memory footprint, on par with and 4-16x less than .

* Maintaining linear regression models over the covariance matrices takes insignificant time if the batch gradient descent resumes with the values for the model parameters computed after the previous update batch.

* Maintaining mutual information and Chow-Liu trees over the covariance matrices requires recomputation after every update batch and this can decrease the throughput of by up to one order of magnitude.

* For $q$-hierarchical queries,  is the fastest approach in case the updates are followed occasionally by a request to enumerate the query result. pushes the updates from the leaves to the root view in the view tree, yet keeps the result factorized. This ensures update time and enumeration delay per tuple proportional to the payload size. We confirmed experimentally that and cannot achieve constant time for both update and enumeration.

* For path queries of up to 20 joins over the Twitter and TikTok graph datasets, 's throughput remains at least an order of magnitude larger than of competitors. and Apache Flink do not manage to process one 1K-batch within four hours for paths of more than 10 joins.

Our conference paper [46] reports further experiments with showing that:
(1) outperforms competitors in maintaining one sum aggregate over joins;
(2) Using batches with $1,000-10,000$ tuples performs best in maintaining the covariance matrix;
(3) Factorized updates lead to two orders of magnitude speedup for over competitors for matrix chain multiplication; and
(4) For conjunctive query evaluation, factorized payloads can speed up view maintenance and reduce memory by up to two orders of magnitude compared to the listing representation of payloads.
For convenience, we include these experiments in Sections <ref> (last two paragraphs), <ref>, <ref>, and <ref>.

§.§ Experimental Settings

The three maintenance strategies use DBToaster v2.3 [33], a system that compiles SQL queries into code that maintains the query result under updates to input relations. The generated code represents an in-memory stream processor that is standalone and independent of any database system. DBToaster's performance on decision support and financial workloads can be several orders of magnitude better than state-of-the-art commercial databases and stream processing systems [33].
DBToaster natively supports and .
We use the intermediate language of DBToaster to encode that maintains a set of materialized views for a given variable order and a set of updatable relations. We feed this encoding into the code generator of DBToaster.
Unless stated otherwise, all approaches use the same runtime and store views as multi-indexed maps with memory-pooled records. The algorithms and record types used in these approaches can differ greatly. We also report on the performance of Apache Flink v1.17.1 [15] (via Table API), configured to utilize all  cores and main memory of our machine.

Dataset     #Tuples     #Relations     #JoinVars     # Non-JoinVars

Housing     1.4M     6     1     26

Retailer     85M     5     4     39

Favorita     125M     6     3     15

Twitter     1.7M     1     2     0

TikTok     0.6M     1     2     0

Characteristics of the input datasets.

Figure <ref> summarizes our datasets:

* Housing is a synthetic dataset modeling a house price market [60].
It consists of six relations: House, Shop, Institution, Restaurant, Demographics, and Transport, arranged into a star schema. The natural join of all relations is on the common variable (postcode) and has $26$ non-join variables, 14 continuous and 12 categorical. We consider a variable order where each root-to-leaf path consists of variables of one relation.

* Retailer is a real-world dataset used by a retailer to inform decision-making and forecast user demands [60].
It has a snowflake schema with one large fact relation Inventory storing information about the inventory units for products in a location, at a given date.
This relation joins along three dimension hierarchies: Item (on product id), Weather (on location and date), and Location (on location) with its lookup relation Census (on zip).
The natural join of these relations is acyclic and has 33 continuous and 6 categorical non-join variables. We use a variable order, where the variables of each relation form a distinct root-to-leaf path, and the partial order on join variables is: location - $\{$ date - $\{$ product id $\}$, zip $\}$.

* Favorita is a real-world dataset comprising sales data of items sold in grocery stores in Ecuador [2].
It has a star schema with one large fact relation Sales  storing information on sales transactions, including the date, store, item, and item quantity. This relation joins with five dimension tables: Stores (on store id), Item (on item id), Transaction (on date and store id), Holiday (on date), and Oil (on date).
The natural join has 3 continuous and 12 categorical non-join variables.
We consider a variable order where the order on join variables is: date - store id - item id.