DBSP: Automatic Incremental View Maintenance for Rich Query Languages

Abstract.

Incremental view maintenance has been for a long time a central problem in database theory (gupta-idb93, ). Many solutions have been proposed for restricted classes of database languages, such as the relational algebra, or Datalog. These techniques do not naturally generalize to richer languages. In this paper we give a general solution to this problem in 3 steps: (1) we describe a simple but expressive language called DBSP for describing computations over data streams; (2) we give a general algorithm for solving the incremental view maintenance problem for arbitrary DBSP programs, and (3) we show how to model many rich database query languages (including the full relational queries, grouping and aggregation, monotonic and non-monotonic recursion, and streaming aggregation) using DBSP. As a consequence, we obtain efficient incremental view maintenance techniques for all these rich languages.

1. Introduction

In this paper we present a simple mathematical theory for modeling streaming and incremental computations. This model has immediate practical applications in the design and implementation of streaming databases and incremental view maintenance. Our model is based on mathematical formalisms used in discrete digital signal processing (DSP) (rabiner-book75, ), but we apply it to database computations. Thus, we have called it “DBSP”. DBSP is inspired from Differential Dataflow (mcsherry-cidr13, ) (DD), and started as an attempt to provide a simpler formalization of DD than the one of Abadi et al. (abadi-fossacs15, ) (as discussed in §9), but has evolved behind that purpose.

The core concept of DBSP is the stream: a stream $s$ with type ${𝒮}_A$ maps “time” moments $t\in \mathbb{N}$ to values $s[t]$ of type $A$; think of it as an ”infinite vector”. A streaming computation is a function that consumes one or more streams and produces another stream. We depict streaming computations with typical DSP box-and-arrow diagrams (also called “circuits”), where boxes are computations and streams are arrows, as in the following diagram, which shows a stream operator $T$ consuming two input streams $s_0$ and $s_1$ and producing one output stream $s$:

We generally think of streams as sequences of small values, and we will use them in this way. However, we make a leap of imagination and also treat a whole database as a stream value. What is a stream of databases? It is a sequence of database snapshots. We model the time-evolution of a database $DB$ as a stream $DB\in {𝒮}_{SCH}$, where $SCH$ is the database schema. Time is not the wall-clock time, but essentially a counter of the sequence of transactions applied to the database. Since transactions are linearizable, they have a total order, which defines a linear time $t$ dimension: the value of the stream $DB[t]$ is the snapshot of the database contents after $t$ transactions have been applied. We assume that $DB[0]=0$, i.e., the database starts empty.

Database transactions also form a stream $T$, a stream of changes, or deltas that are applied to our database. The database snapshot at time $t$ is the cumulative result of applying all transactions in the sequence up to $t$: $DB[t]={\sum }_{i\le t}T[i]\stackrel{\text{def}}{=}ℐ(T)[t]$ (we make the notion of “addition” precise later.). The operation of adding up all changes is stream integration. The following diagram expresses this relationship using the $ℐ$ operator for stream integration:

Conversely, we can say that transactions are the changes of a database, and write $T=𝒟(DB)$, or $T[t]=DB[t]-DB[t-1]$. This is the definition of stream differentiation, denoted by $𝒟$; this operation computes the changes of a stream, and is the inverse of stream integration. §2 precisely defines streams, integration and differentiation, and analyzes their properties.

Let us apply these concepts to view maintenance. Consider a database $DB$ and a query $Q$ defining a view $V$ as a function of a database snapshot $V=Q(DB)$. Corresponding to the stream of database snapshots $DB$ we have a stream of view snapshots: $V[t]$ is the view’s contents after the $t$-th transaction has been applied. We show this relationship using the following diagram:

The symbol $\uparrow Q$ (the “lifting” of $Q$) shows that the query $Q$ is applied independently to every element of the stream of database snapshots $DB$. $\uparrow Q$ is a “streaming query” since it operates on a stream of values. The incremental view maintenance problem requires an algorithm to compute the stream $\mathrm{\Delta }V$ of changes of the view $V$, i.e., $𝒟(V)$, as a function of the stream $T$. By chaining these definitions together we get the following fundamental equation of the view maintenance problem: $\mathrm{\Delta }V=𝒟(\uparrow Q(DB))=𝒟(\uparrow Q(ℐ(T)))$, graphically shown as:

This definition can be generalized to more general streaming queries $S:{𝒮}_A\to {𝒮}_B$ that are richer than lifted pointwise queries $Q$. The incremental version of streaming query $S$ is denoted by $S^{\mathrm{\Delta }}$ and is defined according to the above equation, which can also be written as: $S^{\mathrm{\Delta }}=𝒟\circ S\circ ℐ$.

It is generally assumed that the changes to a dataset are much smaller than the dataset itself; thus, computing on streams of changes may produce significant performance benefits.

Applying the query incrementalization operator $S\mapsto S^{\mathrm{\Delta }}$ constructs a query that computes directly on changes; however, the resulting query is no more efficient than a query that computes on the entire dataset, because it uses an integration operator to reconstitute the full dataset. §3 shows how algebraic properties of the ${\cdot }^{\mathrm{\Delta }}$ operator are used to optimize the implementation of $S^{\mathrm{\Delta }}$:

1. The first property is that many classes of primitive operations have very efficient incremental versions. In particular, linear queries have the property $Q=Q^{\mathrm{\Delta }}$. Almost all relational and Datalog queries are based on linear operators. Thus, the incremental version of such queries can be computed in time proportional to the size of the changes. Bilinear operators (such as joins) have a more complex implementation, which nevertheless still performs work proportional to the size of the changes, but require storing an amount of data proportional to the size of the relations.

2. The second key property is the chain rule: ${(S_1\circ S_2)}^{\mathrm{\Delta }}=S_1^{}{}_{}{}^{\mathrm{\Delta }}\circ S_2^{}{}_{}{}^{\mathrm{\Delta }}$. This rule gives the incremental version of a complex query as a composition of incremental versions of its components. It follows that we can implement any incremental query as a composition of primitive incremental queries, all of which perform work proportional to the size of the changes.

Armed with this general theory of incremental computation, in §4 we show how to model relational queries in DBSP. This immediately gives us a general algorithm to compute the incremental version of any relational query. These results are well-known, but they are cleanly modeled by DBSP.

Applying DBSP to recursive queries requires extending this computational model. In §5 we introduce two additional operators: ${\delta }_0$ creates a stream from a scalar value, and $\int$ creates a scalar value from a stream. These operators can be used to implement computations with while loops. So, in addition to modelling changing inputs and database, we also use streams as a model for sequences of consecutive values of loop iteration variables. With this addition DBSP becomes rich enough to implement recursive queries. §5.1 shows how stratified recursive Datalog programs with negation can be implemented in DBSP.

In §6 we use DBSP to model computations on nested streams, where each value of a stream is another stream. This allows us to define incremental streaming computations for recursive programs. As a consequence we derive a universal algorithm for incrementalizing arbitrary streaming Datalog programs.

DBSP is a simple language: the basic DBSP streaming model is built essentially from two elementary mathematical operators: lifting $\uparrow$ and delay $z^{-1}$. The nested streams model adds two additional operators, ${\delta }_0$ for stream construction and $\int$ for destruction.

DBSP is also expressive: for example, it is more powerful than stratified Datalog. DBSP can also describe streaming window queries, or queries on nested relations (such as grouping), and non-monotone recursive queries. We discuss briefly the application of DBSP to richer languages in §7.

This paper omits most proofs; the full proofs are available in an expansive companion technical report (tr, ).

This paper makes the following contributions:

1. It defines DBSP, a small language for streaming computation, which nonetheless can express nested non-monotonic recursion;

2. It provides an algorithm incrementalizing all DBSP programs;

3. For fragments of DBSP corresponding to the relational algebra and stratified-monotonic Datalog, the automatic incrementalization algorithm provides results matching state-of-the-art approaches. Moreover, our approach also applies to more powerful languages, such as while-relational and non-monotonic Datalog (Abiteboul-book95, ).

4. It develops a formal, sound foundation for the manipulation of streaming and incremental computations, which allows one to reason formally about program transformations and design new efficient implementations.

5. DBSP can express both streaming and incremental computation models in a single framework. We regard this unification as a significant contribution.

2. Stream computations

In this section we introduce formally the notion of a stream as an infinite sequence of values, and we define computations on streams. Stream operators (§2.1) are the basic building block of stream computations. We employ (§2.2) restricted types of stream operators: causal operators (which cannot “look into the future”), and strict operators (which cannot even “look into the present”). Moreover, all our operators are “synchronous”: they consume and produce data at the same “rate”. Causal operators can be chained into complex acyclic computational circuits; cyclic circuits are restricted to using strict operators on back-edges. Finally, we define (§2.3) two useful stream operators: integration and differentiation.

All the results in this section have been known for decades, but we recapitulate them to clarify our model’s formal assumptions.

2.1. Streams and stream operators

$\mathbb{N}$ is the set of natural numbers, $𝔹$ is the set of Booleans, and $\mathbb{Z}$ is the set of integers.

Definition 2.1 (stream):

Given a set $A$, a stream of values from $A$, or an $A$-stream, is a function $\mathbb{N}\to A$. We denote by ${𝒮}_A\stackrel{\text{def}}{=}\{s|s:\mathbb{N}\to A\}$ the set of all $A$-streams.

When $s\in {𝒮}_A$ and $t\in \mathbb{N}$ we write $s[t]$ for the $t$-th element of the stream $s$ instead of the usual $s(t)$ to distinguish it from other function applications. We think of the index $t\in \mathbb{N}$ as (discrete) time and of $s[t]\in A$ as the value of the the stream $s$ “at time” $t$. For example, the stream of natural numbers $id\in {𝒮}_{\mathbb{N}}$ given by $\mathrm{𝑖𝑑}[t]=t$ is the sequence of values .

Definition 2.2 (stream operator):

A (typed) stream operator with $n$ inputs is a function $T:{𝒮}_{A_0}\times \mathrm{\cdots }\times {𝒮}_{A_{n-1}}\to {𝒮}_B$.

In general we will use “operator” for functions on streams, and “function” for computations on “scalar” values.

We are using an extension of the simply-typed lambda calculus to write DBSP programs; we will introduce its elements gradually. However, we find it more readable to also use signal-processing-like circuit diagrams to depict DBSP programs. In a circuit diagram a rectangle represents an operator application (labeled with the operator name, e.g., $T$), while an arrow is a stream.

Stream operator composition (function composition) is shown as chained circuits. The composition of a binary operator $T:{𝒮}_A\times {𝒮}_B\to {𝒮}_A$ with the unary operator $S:{𝒮}_A\to {𝒮}_B$ into the computation $\lambda s.T(T(s,S(s)),S(s)):{𝒮}_A\to {𝒮}_A$ is:

(Diagrams obscure the order of the inputs of an operator; for non-commutative operators we have to provide more information.)

Definition 2.3:

(lifting) Given a (scalar) function $f:A\to B$, we define a stream operator $\uparrow f:{𝒮}_A\to {𝒮}_B$ by lifting the function $f$ pointwise in time: $(\uparrow f)(s)\stackrel{\text{def}}{=}f\circ s$. Equivalently, $(\uparrow f)(s)[t]\stackrel{\text{def}}{=}f(s[t])$. This extends to functions of multiple arguments.

For example, (↑(λx.(2x)))(id)=arg02468[arg⁡[1]arg⁡[2]arg⁡[3]arg⁡[4]arg⁡[5]⋯].

Proposition 2.4 (distributivity):

Lifting distributes over function composition: $\uparrow (f\circ g)=(\uparrow f)\circ (\uparrow g)$.

We say that two DBSP programs are equivalent if they compute the same input-output function on streams. We use the symbol $\cong$ to indicate that two circuits are equivalent. For example, Proposition 2.4 states the following circuit equivalence:

$\cong$

2.2. Streams over abelian groups

For the rest of the technical development we require the set of values $A$ of a stream ${𝒮}_A$ to form a commutative group $(A,+,0,-)$. Now we introduce the primitive stream operators that DBSP uses.

2.2.1. Delays and time-invariance

Definition 2.5 (Delay):

The delay operator produces an output stream by delaying its input by one step: $z_A^{-1}:{𝒮}_A\to {𝒮}_A$:

We often omit the type parameter $A$, and write just $z^{-1}$. For example, .

Definition 2.6 (Time invariance):

A stream operator $S:{𝒮}_A\to {𝒮}_B$ is time-invariant iff $S(z_A^{-1}(s))=z_B^{-1}(S(s))$ for all $s\in {𝒮}_A$, or, in other words, iff the two following circuits are equivalent:

$\cong$

This definition extends naturally to operators with multiple inputs.

The composition of time-invariant operators of any number of inputs is time invariant. The delay operator $z^{-1}$ is time-invariant. DBSP only uses time-invariant operators.

Definition 2.7:

We say that a function between groups $f:A\to B$ has the zero-preservation property if $f(0_A)=0_B$. We write $\text{zpp}(f)$.

A lifted operator $\uparrow f$ is time-invariant iff $\text{zpp}(f)$.

2.2.2. Causal and strict operators

Definition 2.8 (Causality):

A stream operator $S:{𝒮}_A\to {𝒮}_B$ is causal when for all $s,s^{\prime }\in {𝒮}_A$, and all times $t$ we have: $(\forall i\le ts[i]=s^{\prime }[i])\Rightarrow S(s)[t]=S(s^{\prime })[t].$

In other words, the output value at time $t$ can only depend on input values from times $t^{\prime }\le t$. Operators produced by lifting are causal, and $z^{-1}$ is causal. All DBSP operators are causal. The composition of causal operators of any number of inputs is causal.

Definition 2.9 (Strictness):

A stream operator, $F:{𝒮}_A\to {𝒮}_B$ is strictly causal (abbreviated strict) if $\forall s,s^{\prime }\in {𝒮}_A,\forall t\in \mathbb{N}$ we have:

So the $t$-th output of $F(s)$ can depend only on “past” values of the input $s$, between $0$ and $t-1$. In particular, $F(s)[0]=0_B$ is the same for all $s\in {𝒮}_A$. Strict operators are causal. Lifted operators in general are not strict. $z^{-1}$ is strict.

Proposition 2.10:

For a strict $F:{𝒮}_A\to {𝒮}_A$ the equation $\alpha =F(\alpha )$ has a unique solution $\alpha \in {𝒮}_A$, denoted by $\text{fix}\alpha .F(\alpha )$.

Thus every strict operator from a set to itself has a unique fixed point. The simple proof relies on strong induction, showing that $\alpha [t]$ depends only on the values of $\alpha$ prior to $t$.

We show that the following circuit, having a strict “feedback” edge $F$, is a well-defined function on streams:

Lemma 2.11:

If $F:{𝒮}_B\to {𝒮}_B$ is strict and $T:{𝒮}_A\times {𝒮}_B\to {𝒮}_B$ is causal, then for a fixed $s$ the operator $\lambda \alpha .T(s,F(\alpha )):{𝒮}_A\to {𝒮}_B$ is strict.

Corollary 2.12:

If $F:{𝒮}_B\to {𝒮}_B$ is strict and $T:{𝒮}_A\times {𝒮}_B\to {𝒮}_B$ is causal, the operator $Q(s)=\text{fix}\alpha .T(s,F(\alpha ))$ is well-defined and causal. If, moreover, $F$ and $T$ are time-invariant then so is $Q$.

All stream computations in DBSP are built from the primitive operators we have described: lifted operators and delays (we add two more operators in §6). Circuits composed of such operators can be efficiently implemented using Dataflow machines (lee-ieee95, ).

Circuits with feedback are used for two purposes: defining an integration operator (in the next section), and defining recursive computations (§5). In turn, the integration operator will be instrumental in defining incremental computations (§3).

2.3. Integration and differentiation

Remember that we require the elements of a stream to come from an abelian group $A$. Streams themselves form an abelian group:

Proposition 2.13:

The structure $({𝒮}_A,+,0,-)$, obtained by lifting the $+$ and unary $-$ operations from $A$ to ${𝒮}_A$, is an abelian group.

Stream addition and negation are causal, time-invariant operators.

Definition 2.14:

Given abelian groups $A$ and $B$ we call a stream operator $S:{𝒮}_A\to {𝒮}_B$ linear if it is a group homomorphism, that is, $S(a+b)=S(a)+S(b)$ (and therefore $S(0)=0$ and $S(-a)=-S(a)$).

Lifting a linear function $f:A\to B$ produces a stream operator $\uparrow f$ that is linear, time-invariant (LTI). $z^{-1}$ is LTI.

Definition 2.15:

(bilinear) A function of two arguments $f:A\times B\to C$ with $A,B,C$ groups, is bilinear if it is linear separately in each argument (i.e., it distributes over addition): $\forall a,b,c,d.f(a+b,c)=f(a,c)+f(b,c)$, and $f(a,c+d)=f(a,c)+f(c,d).$

This definition extends to stream operators. Lifting a bilinear function $f:A\times B\to C$ produces a bilinear stream operator $\uparrow f$. An example bilinear operator over ${𝒮}_{\mathbb{Z}}$ is lifted multiplication: $f:{𝒮}_{\mathbb{N}}\times {𝒮}_{\mathbb{N}}\to {𝒮}_{\mathbb{N}},f(a,b)[t]=a[t]\cdot b[t]$.

The composition of (bi)linear operators with linear operators is (bi)linear (since homomorphisms compose).

The feedback loop produced with a linear operator is linear:

Proposition 2.16:

Let $S$ be a unary causal LTI operator. The operator $Q(s)=\text{fix}\alpha .S(s+z^{-1}(\alpha ))$ is well-defined and LTI:

Definition 2.17 (Differentiation):

The differentiation operator ${𝒟}_{{𝒮}_A}:{𝒮}_A\to {𝒮}_A$ is defined by: $𝒟(s)\stackrel{\text{def}}{=}s-z^{-1}(s)$.

We generally omit the type, and write just $𝒟$ when the type can be inferred from the context. The value of $𝒟(s)$ at time $t$ is the difference between the current (time $t$) value of $s$ and the previous (time $t-1$) value of $s$. As an example, .

If $s$ is a stream, then $𝒟(s)$ is the stream of changes of $s$.

Proposition 2.18:

Differentiation $𝒟$ is causal and LTI.

Differentiation	Integration

The integration operator “reconstitutes” a stream from its changes:

Definition 2.19 (Integration):

The integration operator ${ℐ}_{{𝒮}_A}:{𝒮}_A\to {𝒮}_A$ is defined by $$ℐ​(s)=defλ​s.fix​α.(s+z−1​(α)).

We also generally omit the type, and write just $ℐ$. This is the construction from Proposition 2.16 using the identity function for $S$.

Proposition 2.20:

$ℐ(s)$ is the discrete (indefinite) integral applied to the stream $s$: $ℐ(s)[t]={\sum }_{i\le t}s[i]$.

As an example, .

Proposition 2.21:

$ℐ$ is causal and LTI.

Theorem 2.22 (Inversion):

Integration and differentiation are inverses of each other: $\forall s.ℐ(𝒟(s))=𝒟(ℐ(s))=s$.

$\cong$

$\cong$

3. Incremental computation

Definition 3.1:

Given a unary stream operator $Q:{𝒮}_A\to {𝒮}_B$ we define the incremental version of $Q$ as $Q^{\mathrm{\Delta }}\stackrel{\text{def}}{=}𝒟\circ Q\circ ℐ$. $Q^{\mathrm{\Delta }}$ has the same “type” as $Q$: $Q^{\mathrm{\Delta }}:{𝒮}_A\to {𝒮}_B$. For an operator with multiple inputs we define the incremental version by applying $ℐ$ to each input independently: e.g., if $T:{𝒮}_A\times {𝒮}_B\to {𝒮}_C$ then $T^{\mathrm{\Delta }}(a,b)\stackrel{\text{def}}{=}𝒟(T(ℐ(a),ℐ(b)))$.

The following diagram illustrates the intuition behind this definition:

If $Q(s)=o$ is a computation, then $Q^{\mathrm{\Delta }}$ performs the “same” computation as $Q$, but between streams of changes $\mathrm{\Delta }s$ and $\mathrm{\Delta }o$. This is the diagram from the introduction, substituting $\mathrm{\Delta }s$ for the transaction stream $T$, and $o$ for the stream of view versions $V$.

Notice that our definition of incremental computation is meaningful only for streaming computations; this is in contrast to classic definitions, e.g. (gupta-idb95, ) which consider only one change. Generalizing the definition to operate on streams gives us additional power, especially when operating with recursive queries.

The following proposition is one of our central results.

Proposition 3.2:

(Properties of the incremental version): For computations of appropriate types, the following hold:

inversion::

$Q\mapsto Q^{\mathrm{\Delta }}$ is bijective; its inverse is $Q\mapsto ℐ\circ Q\circ 𝒟$.

invariance::

${+}^{\mathrm{\Delta }}=+,{(z^{-1})}^{\mathrm{\Delta }}=z^{-1},{-}^{\mathrm{\Delta }}=-,{ℐ}^{\mathrm{\Delta }}=ℐ,{𝒟}^{\mathrm{\Delta }}=𝒟$

push/pull::

$Q\circ ℐ=ℐ\circ Q^{\mathrm{\Delta }}$; $𝒟\circ Q=Q^{\mathrm{\Delta }}\circ 𝒟$

chain::

${(Q_1\circ Q_2)}^{\mathrm{\Delta }}=Q_1^{}{}_{}{}^{\mathrm{\Delta }}\circ Q_2^{}{}_{}{}^{\mathrm{\Delta }}$ (This generalizes to operators with multiple inputs.)

add::

${(Q_1+Q_2)}^{\mathrm{\Delta }}=Q_1^{}{}_{}{}^{\mathrm{\Delta }}+Q_2^{}{}_{}{}^{\mathrm{\Delta }}$

cycle::

${(\lambda s.\text{fix}\alpha .T(s,z^{-1}(\alpha )))}^{\mathrm{\Delta }}=\lambda s.\text{fix}\alpha .T^{\mathrm{\Delta }}(s,z^{-1}(\alpha ))$

The proof of these properties relies on elementary algebraic manipulations. Despite their simplicity, they are very useful. For example, the chain rule states that the following two circuits are equivalent:

$\cong$

In other words, to incrementalize a composite query you can incrementalize each sub-query independently. This gives us a simple deterministic recipe for computing the incremental version of an arbitrarily complex query.

We illustrate by giving the proof of the chain rule, which is trivial, and is based on function composition associativity:

${(Q_1\circ Q_2)}^{\mathrm{\Delta }}$ $=𝒟\circ Q_1\circ Q_2\circ ℐ$

$=𝒟\circ Q_1\circ (ℐ\circ 𝒟)\circ Q_2\circ ℐ$

$=(𝒟\circ Q_1\circ ℐ)\circ (𝒟\circ Q_2\circ ℐ)$

$={(Q_1)}^{\mathrm{\Delta }}\circ {(Q_2)}^{\mathrm{\Delta }}.$

The cycle rule states that the following circuits are equivalent:

$\cong$

The incremental version of a feedback loop around a query is just the feedback loop with the incremental query. The significance of this result will be apparent when we implement recursive queries.

To execute incremental queries efficiently, we want to compute directly on streams of changes without integrating them. The invariance property above shows that stream operators $+$, $-$, and $z^{-1}$ are identical to their incremental versions, thus $ℐ$ and $𝒟$ can be omitted for them: $Q^{\mathrm{\Delta }}=ℐ\circ Q\circ 𝒟=Q$. The following theorems generalize this to linear and bi-linear operators:

Theorem 3.3 (Linear):

For an LTI operator $Q$ we have $Q^{\mathrm{\Delta }}=Q$.

Theorem 3.4 (Bilinear):

For a bilinear time-invariant operator $\times$ we have ${(a\times b)}^{\mathrm{\Delta }}=a\times b+z^{-1}(ℐ(a))\times b+a\times z^{-1}(ℐ(b))$.

By rewriting this statement using $\mathrm{\Delta }a$ for the stream of changes to $a$ we get the familiar formula for incremental equi-joins: $\mathrm{\Delta }(a\times b)=\mathrm{\Delta }a\times \mathrm{\Delta }b+a\times (\mathrm{\Delta }b)+(\mathrm{\Delta }a)\times b$.

This should not be surprising because equi-joins are bilinear, as we discuss in the next section.

4. Incremental View Maintenance

Results in §2 and §3 apply to streams of arbitrary group values. In this section we turn our attention to using these results in the context of relational view maintenance. As explained in the introduction, we want to efficiently compute the incremental version of any relational query $Q$ that updates a database view.

However, we face a technical problem: the $ℐ$ and $𝒟$ operators were defined on abelian groups, and relational databases in general are not abelian groups, since they operate on sets. Fortunately, there is a well-known tool in the database literature which converts set operations into group operations by using $\mathbb{Z}$-sets (also called z-relations (green-pods07, )) instead of sets.

We start by defining the $\mathbb{Z}$-sets group, and then we review how relational queries are converted into DBSP circuits over $\mathbb{Z}$-sets. What makes this translation efficiently incrementalizable is the fact that many basic relational queries can be expressed using LTI $\mathbb{Z}$-set operators.

4.1. $\mathbb{Z}$-sets as an abelian group

Given a set $A$, we define $\mathbb{Z}$-sets over $A$ as functions with finite support from $A$ to $\mathbb{Z}$. These are functions $f:A\to \mathbb{Z}$ where $f(x)\ne 0$ for at most a finite number of values $x\in A$. We also write $\mathbb{Z}[A]$ for the type of $\mathbb{Z}$-sets with elements from $A$. Values in $\mathbb{Z}[A]$ can be thought of as key-value maps with keys in $A$ and values in $\mathbb{Z}$, justifying the array indexing notation. We write $f[a]$ instead of $f(a)$. Since $\mathbb{Z}$ is an abelian ring, $\mathbb{Z}[A]$ is also an abelian ring (and thus a group). This group $(\mathbb{Z}[A],{+}_{\mathbb{Z}[A]},0_{\mathbb{Z}[A]},{-}_{\mathbb{Z}A})$ has addition and subtraction defined pointwise: $(f{+}_{\mathbb{Z}[A]}g)(x)=f(x)+g(x).\forall x\in A.$ The $0$ element of $\mathbb{Z}[A]$ is the function $0_{\mathbb{Z}[A]}$ defined by $0_{\mathbb{Z}[A]}(x)=0.\forall x\in A$.

A particular $\mathbb{Z}$-set $m\in \mathbb{Z}[A]$ can be denoted by enumerating the inputs that map to non-zero values and their corresponding values: $m=\{x_1\mapsto w_1,\mathrm{\dots },x_n\mapsto w_n\}$. We call $w_i\in Z$ the multiplicity (or weight) of $x_i\in A$. Multiplicities can be negative. We write that $x\in m$ for $x\in A$, iff $m[x]\ne 0$.

For example, let’s consider a concrete $\mathbb{Z}$-set $R\in \mathbb{Z}[\text{string}]$, defined by $R=\{\text{joe}\mapsto 1,\text{anne}\mapsto -1\}$. $R$ has two elements in its domain, joe with a multiplicity of 1 (so $R[\text{joe}]=1$), and anne with a multiplicity of $-1$. We say joe $\in R$ and anne $\in R$.

$\mathbb{Z}$-sets generalize sets and bags. A set with elements from $A$ can be represented as a $\mathbb{Z}$-set by associating a weight of 1 with each set element. When translating queries on sets to DBSP programs we convert the data values back and forth between sets and $\mathbb{Z}$-sets.

Definition 4.1:

We say that a $\mathbb{Z}$-set represents a set if the multiplicity of every element is one. We define a function to check this property $\text{isset}:\mathbb{Z}[A]\to 𝔹$ given by:

For our example $\text{isset}(R)=\text{false}$, since $R[\text{anne}]=-1$.

Definition 4.2:

We say that a $\mathbb{Z}$-set is positive (or a bag) if the multiplicity of every element is positive. We define a function to check this property $\text{ispositive}:\mathbb{Z}[A]\to 𝔹$. given by

$\forall m\in \mathbb{Z}[A].\text{isset}(m)\Rightarrow \text{ispositive}(m)$.

We have $\text{ispositive}(R)=\text{false}$, since $R[\text{anne}]=-1$.

We write $m\ge 0$ when $m$ is positive. For positive $m,n$ we write $m\ge n$ for $m,n\in \mathbb{Z}[A]$ iff $m-n\ge 0$. $\ge$ is a partial order.

We call a function $f:\mathbb{Z}[A]\to \mathbb{Z}[B]$ positive if it maps positive values to positive values: $\forall x\in \mathbb{Z}[A],x\ge 0_{\mathbb{Z}[A]}\Rightarrow f(x)\ge 0_{\mathbb{Z}[B]}$. We apply this notation to functions as well: $\text{ispositive}(f)$.

Definition 4.3 (distinct):

The function $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}:\mathbb{Z}[A]\to \mathbb{Z}[A]$ projects a $\mathbb{Z}$-set into an underlying set (but the result is still a $\mathbb{Z}$-set):

$\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ “removes” elements with negative multiplicities. $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}(R)=\{\text{joe}\mapsto 1\}$.

While very simple, this definition of $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ has been carefully chosen to enable us to define precisely all relational (set) operators from $\mathbb{Z}$-sets operators.

Circuits derived from relational queries only compute on positive $\mathbb{Z}$-sets; negative values will only be used to represent changes to $\mathbb{Z}$-sets. Negative weights “remove” elements from a set.

All the results from §2 extend to streams over $\mathbb{Z}$-sets.

Definition 4.4:

(mononotonicity) A stream $s\in {𝒮}_{\mathbb{Z}[A]}$ is positive if every value of the stream is positive: $s[t]\ge 0.\forall t\in \mathbb{N}$. A stream $s\in {𝒮}_{\mathbb{Z}[A]}$ is monotone if $s[t]\ge s[t-1],\forall t\in \mathbb{N}$.

If $s\in {𝒮}_{\mathbb{Z}[A]}$ is positive, then $ℐ(s)$ is monotone. If $s\in {𝒮}_{\mathbb{Z}[A]}$ is monotone, $𝒟(s)$ is positive.

Generalizing box-and-arrow diagrams

From now on we will use circuits to compute both on scalars and streams. We use the same graphical representation for functions on streams or scalars: boxes with input and output arrows. For scalar functions the “values” of the arrows are scalars instead of streams; otherwise the interpretation of boxes as function application is unchanged.

4.2. Implementing relational operators

The fact that relational algebra can be implemented by computations on $\mathbb{Z}$-sets has been shown before, e.g. (green-pods07, ). The translation of all the core relational operators is shown in Table 4.2. The translation is essentially given by induction on the query structure.

Operation	SQL example	DBSP circuit	Details
Composition	⬇ SELECT DISTINCT ... FROM (SELECT ... FROM ...)		$C_I$ circuit for inner query, $C_O$ circuit for outer query.
Union	⬇ (SELECT * FROM I1) UNION (SELECT * FROM I2)
Projection	⬇ SELECT DISTINCT I.c FROM I		$\pi \left(i\right)\left[y\right]\stackrel{\text{def}}{=}{\sum }_{x\in i,{x|}_c=y}i\left[x\right]$ ${x|}_c$ is projection on column $c$ of the tuple $x$ $\pi$ is linear; $\text{ispositive}\left(\pi \right),\text{zpp}\left(\pi \right)$.
Filtering	⬇ SELECT * FROM I WHERE p(I.c)		$P:A\to 𝔹$ is a predicate. ${\sigma }_P$ is linear; $\text{ispositive}\left({\sigma }_P\right),\text{zpp}\left({\sigma }_P\right)$.
Selection	⬇ SELECT DISTINCT f(I.c, ...) FROM I		For a function $f$ $\text{map}\left(f\right)$ is linear, $\text{ispositive}\left(\text{map}\left(f\right)\right),\text{zpp}\left(\text{map}\left(f\right)\right)$ .
Cartesian product	⬇ SELECT I1.*, I2.* FROM I1, I2		$\left(a\times b\right)\left((x,y)\right)\stackrel{\text{def}}{=}a\left[x\right]\times b\left[y\right]$. $\times$ is bilinear, $\text{ispositive}(\times ),\text{zpp}(\times )$.
Equi-join	⬇ SELECT I1.*, I2.* FROM I1 JOIN I2 ON I1.c1 = I2.c2		$\left(a\bowtie b\right)\left((x,y)\right)\stackrel{\text{def}}{=}{a\left[x\right]\times b\left[y\right]\text{if}x|}_{c1}={y|}_{c2}$. $\bowtie$ is bilinear, $\text{ispositive}(\bowtie ),\text{zpp}(\bowtie )$.
Intersection	⬇ (SELECT * FROM I1) INTERSECT (SELECT * FROM I2)		Special case of equi-join when both relations have the same schema.
Difference	⬇ SELECT * FROM I1 EXCEPT SELECT * FROM I2

Table 1. Implementation of SQL relational set operators in DBSP. Each query assumes that inputs I, I1, I2, are sets and it produces output sets.

The translation is fairly straightforward, but many operators require the application of a $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ to produce sets. The correctness of this implementation is predicated on the global circuit inputs being sets as well. For example, $a\cup b=\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}(a+b)$, $a\setminus b=\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}(a-b)$, $(a\times b)((x,y))=a[x]\times b[y]$.

4.2.1. Correctness of the DBSP implementations

A relational query $Q$ that transforms a set $V$ into a set $U$ will be implemented by a DBSP computation $Q^{\prime }$ on $\mathbb{Z}$-sets. The correctness of the implementation requires that the following diagram commutes:

The toset and tozset functions convert sets to $\mathbb{Z}$-sets and vice-versa:

$\text{toset}:\mathbb{Z}\left[A\right]\to 2^A$ is defined by $\text{toset}\left(m\right)\stackrel{\text{def}}{=}{\cup }_{x\in \mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}\left(m\right)}\left\{x\right\}$.

$\text{tozset}:2^A\to \mathbb{Z}\left[A\right]$ is defined by $\text{tozset}\left(s\right)\stackrel{\text{def}}{=}{\sum }_{x\in s}1\cdot x$.

All standard algebraic properties of the relational operators can be used to optimize circuits (they can even be applied to queries before building the circuits).

Notice that the use of the $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ operator allows DBSP to model the full relational algebra, including difference (and not just the positive fragment). Most of the operators that appear in the circuits in Table 4.2 are linear, and thus have very efficient incremental versions. A notable exception is $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$. While we show below that $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ can be computed efficiently incrementally, it does have an important cost in terms of memory, so we try to minimize its use. For this we can use a pair of optimizations:

Proposition 4.5:

Let Q be one of the following $\mathbb{Z}$-sets operators: filtering $\sigma$, join $\bowtie$, or Cartesian product $\times$. Then we have $\forall i\in \mathbb{Z}\left[I\right],\text{ispositive}\left(i\right)\Rightarrow Q\left(\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}\left(i\right)\right)=\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}\left(Q\left(i\right)\right)$.

This rule allows us to delay the application of $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$.

Proposition 4.6:

Let Q be one of the following $\mathbb{Z}$-sets operators: filtering $\sigma$, projection $\pi$, selection (map($f$)), addition $+$, join $\bowtie$, or Cartesian product $\times$. Then we have $\forall i\in \mathbb{Z}\left[I\right],\text{ispositive}\left(i\right)\Rightarrow \mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}\left(Q\left(\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}\left(i\right)\right)\right)=\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}\left(Q\left(i\right)\right)$.

This is Proposition 6.13 in (green-tcs11, ).

These properties allow us to “consolidate” distinct operators by performing one $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ at the end of a chain of computations.

Finally, the next proposition shows that the incremental of $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ can be computed with work proportional to the size of the input change.

Proposition 4.7:

The following circuit implements ${(\uparrow \mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡})}^{\mathrm{\Delta }}$: $\cong$

where $H:\mathbb{Z}\left[A\right]\times \mathbb{Z}\left[A\right]\to \mathbb{Z}\left[A\right]$ is defined as: H(i, d)[x] =def{-1 if i[x] ¿ 0 and (i + d)[x] ≤01 if i[x] ≤0 and (i + d)[x] ¿ 00 otherwise

The function $H$ detects whether the multiplicity of an element in the input set $i$ when adding change $d$ is changing from negative to positive or vice-versa. Notice that only multiplicities of the elements that appear in the change $d$ can change from input to output, so the work needed to compute both $H$ is bounded by the size of $d$ and not $i$.

4.3. Incremental view maintenance

Let us consider a relational query $Q$ defining a view. To create a circuit that maintains incrementally the view defined by $Q$ we apply the following mechanical steps; this algorithm is deterministic and its running time is proportional to the complexity of the query (number of operators in the query):

Algorithm 4.8 (incremental view maintenance):

1. Translate $Q$ into a circuit using the rules in Table 4.2.

2. Apply $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ consolidation until convergence.

3. Lift the whole circuit, by applying Proposition 2.4, converting it to a circuit operating on streams.

4. Incrementalize the whole circuit “surrounding” it with $ℐ$ and $𝒟$.

5. Apply the chain rule and other properties of the ${\cdot }^{\mathrm{\Delta }}$ operator from Proposition 3.2 recursively on the query structure to optimize the incremental implementation.

Step (3) yields a circuit that consumes a stream of complete database snapshots and outputs a stream of complete view snapshots. Step (4) yields a circuit that consumes a stream of changes to the database and outputs a stream of view changes; however, the internal operation of the circuit is non-incremental, as it computes on the complete state of the database reconstructed by the integration operator. Step (5) incrementalizes the internals of the circuit by rewriting it to compute on changes, avoiding integration when possible (see §3).

4.4. Example

In this section we apply the incremental view maintenance algorithm to a concrete query. Let us consider the following query:

⬇

CREATE VIEW v AS

SELECT DISTINCT t1.x, t2.y FROM (

SELECT t1.x, t1.id

FROM t

WHERE t.a > 2

) t1

JOIN (

SELECT t2.id, t2.y

FROM r

WHERE r.s > 5

) t2 ON t1.id = t2.id

Step 1: First we create a DBSP circuit to represent this query using the translation rules from Table 4.2:

Step 2: we apply the $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ optimization rules; first the rule from 4.6 gives us the following equivalent circuit:

Applying the rule from 4.5 we get:

And applying again 4.6 we get:

Step 3: we lift the circuit using distributivity of composition over lifting; we obtain a circuit that computes over streams, i.e., for each new input pair of relations t1 and t2 it will produce an output view V:

Step 4: incrementalize circuit, obtaining a circuit that computes over changes; this circuit receives changes to relations t1 and t2 and for each such change it produces the corresponding change in the output view V:

Step 5: apply the chain rule to rewrite the circuit as a composition of incremental operators;

Use the linearity of $\sigma$ and $\pi$ to simplify this circuit:

Finally, replace the incremental join using the formula for bilinear operators (Theorem 3.4), and the incremental $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ (Proposition 4.7), obtaining the circuit from Figure 1.

Figure 1. Final version of the incremental query circuit from §4.4.

Notice that the resulting circuit contains three integration operations: two from the join, and one from the $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$. It also contains three join operators. However, the work performed by each operator for each new input is proportional to the size of change, as we argue in the following section.

4.5. Complexity

Incremental circuits are efficient. The work performed (and the memory used) by a circuit is the sum of the work performed (and memory used) by its operators. We argue that each operator in the incremental version of a circuit is efficient.

For incrementalized circuits the input stream of each operator contains changes in its input relations. Denote $C\left[t\right]\stackrel{\text{def}}{=}\Vert s\left[t\right]\Vert$ the size of the value of stream $s$ of changes at time $t$, and $R\left[t\right]\stackrel{\text{def}}{=}\Vert ℐ\left(s\right)\left[t\right]\Vert$ the size of the relation produced by integrating all changes in $s$. An unoptimized incremental operator $Q^{\mathrm{\Delta }}=𝒟\circ Q\circ ℐ$ evaluates query $Q$ on the integration of its input streams; hence its time complexity is the same as that of the non-incremental operator, a function of $R\left[t\right]$. In addition, because of the $ℐ$ and $𝒟$ operators, it uses $O\left(R\left[t\right]\right)$ memory.

The optimizations described in §3 reduce the reduce the time complexity of an operator to be a function of $C\left[t\right]$. Assuming $C\left[t\right]\ll R\left[t\right]$, this translates to major performance improvements in practice. For example, Theorem 3.3, allows evaluating $T^{\mathrm{\Delta }}$, where $T$ is a linear operator, in time $O\left(C\left[t\right]\right)$. Interestingly, while the $ℐ$ operator uses $O\left(R\left[t\right]\right)$ memory, it can be evaluated in $O\left(C\left[t\right]\right)$ time, because all values that appear in the output at time $t$ must be present in current input change for time $t$. Similarly, while the $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ operator is not linear, ${(\uparrow \mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡})}^{\mathrm{\Delta }}$ can also be evaluated in $O\left(C\left[t\right]\right)$ according to Proposition 4.7. Bilinear operators, including join, can be evaluated in time proportional to the product of the sizes of their input changes $O\left(C{\left[t\right]}^2\right)$ (Theorem 3.4).

The space complexity of linear operators is 0 (zero), since they store no data persistently. The space complexity of ${(\uparrow \mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡})}^{\mathrm{\Delta }}$ and join is $O\left(R\left[t\right]\right)$.

5. Recursive queries

Recursive queries are very useful in a many applications. For example, many graph algorithms (such as graph reachability or transitive closure) are naturally expressed using recursive queries.

We introduce two new stream operators that are instrumental in expressing recursive query evaluation. These operators allow us to build circuits implementing looping constructs, which are used to iterate computations until a fixed-point is reached.

Definition 5.1:

We say that a stream $s\in {𝒮}_A$ is zero almost-everywhere if it has a finite number of non-zero values, i.e., there exists a time $t_0\in \mathbb{N}$ s.t. $\forall t\ge t_0.s\left[t\right]=0$. Denote the set of streams that are zero almost everywhere by $\overline{{𝒮}_A}$.

Stream introduction

The delta function (named from the Dirac delta function) ${\delta }_0:A\to {𝒮}_A$ produces a stream from a scalar value: δ_0(v)[t] =def{ vif t = 00_A otherwise For example, ${\delta }_0\left(5\right)$ is the stream .

Stream elimination

We define the function $\int :\overline{{𝒮}_A}\to A$, over streams that are zero almost everywhere, as $\int \left(s\right)\stackrel{\text{def}}{=}{\sum }_{t\ge 0}s\left[t\right]$. $\int$ is closely related to $ℐ$; if $ℐ$ is the indefinite integral, $\int$ is the definite integral on the interval $0-\mathrm{\infty }$.

For many implementation strategies (including relational and Datalog queries given below) the $\int$ operator can be approximated finitely and precisely by integrating until the first 0 value encountered, since it can be proven that its input is always the derivative of a monotone stream.

${\delta }_0$ is the left inverse of $\int$, i.e.: $\int \circ {\delta }_0={\mathrm{𝑖𝑑}}_A$.

Proposition 5.2:

${\delta }_0$ and $\int$ are LTI.

Nested time domains

So far we used a tacit assumption that “time” is common for all streams in a program. For example, when we add two streams, we assume that they use the same “clock” for the time dimension. However, the ${\delta }_0$ operator creates a stream with a “new”, independent time dimension. We require well-formed circuits to “insulate” such nested time domains by nesting them between a ${\delta }_0$ and an $\int$ operator:

Proposition 5.3:

If $Q$ is time-invariant, the circuit above has the zero-preservation property: $\text{zpp}\left(\int \circ Q\circ {\delta }_o\right)$.

5.1. Implementing Recursive Datalog

We illustrate the implementation of recursive queries in DBSP for stratified Datalog. Datalog is strictly more expressive than relational algebra since it can express recursive programs, e.g.:

⬇

O(v) :- I(v). // base case

O(v) :- I(z), O(x), v = ... . // rec case

In general, a recursive Datalog program defines a set of mutually recursive relations $O_1,..,O_n$ as an equation $(O_1,..,O_n)=R(I_1,..,I_m,O_1,..,O_n)$, where $I_1,..,I_m$ are input relations and $R$ is a relational (non-recursive) query.

The following algorithm generates a circuit that computes a solution to this equation. We describe the algorithm informally and for the special case of a single input $I$ and single output $O$; the general case can be found in the companion technical report (tr, ), and is only slightly more involved.

1. Implement the non-recursive relational query $R$ as described in §4 and Table 4.2; this produces an acyclic circuit whose inputs and outputs are a $\mathbb{Z}$-set (i.e., not a stream):

2. Lift this circuit to operate on streams and connect the output to the input in a feedback cycle as follows:

   We construct $\uparrow R$ by lifting each operator of the circuit individually according to Proposition 2.4.

The inner loop of the circuit computes the fixed point of $R$. The differentiation operator $𝒟$ yields the set of new Datalog facts (changes) computed by each iteration of the loop. When the set of new facts becomes empty the iterations have completed. $\int$ computes the value of the fixed point by aggregating these changes.

Theorem 5.4 (Recursion correctness):

If $\text{isset}\left(\text{I}\right)$, the output of the circuit above is the relation O as defined by the Datalog semantics as a function of the input relation I.

Proof.

Let us compute the contents of the $o$ stream, produced at the output of the $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$ operator. We will show that this stream is composed of increasing approximations of the value of O.

We define the following one-argument function: $S\left(x\right)=\lambda x.R(\text{I},x)$. Notice that the left input of the $\uparrow R$ block is a constant stream with the value I. Due to the stratified nature of the language, we must have $\text{ispositive}\left(S\right)$, so $\forall x.S\left(x\right)\ge x$. Also $\uparrow S$ is time-invariant, so $S\left(0\right)=0$. From §4, the definition of set union we know that $x\cup y=\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}\left(x+y\right)$. We get the following system of equations: o[0] =S(0) o[t] =S(o[t-1]) So, by induction on $t$ we have $o\left[t\right]=S^t\left(0\right)$, where by $S^t$ we mean $\underset{t}{\underbrace{S\circ S\circ \mathrm{\dots }\circ S}}$. $S$ is monotone; thus, if there is a time $k$ such that $S^k\left(0\right)=S^{k+1}\left(0\right)$, we have $\forall j\in \mathbb{N}.S^{k+j}\left(0\right)=S^k\left(0\right)$. Applying a derivative to this stream will then produce a stream that is zero almost everywhere, and integrating this derivative will return the last distinct value in the stream $o$.

This is essentially the definition of the semantics of a recursive Datalog relation: $\text{O}=\text{fix}x.R(\text{I},x)$. ∎

Note that the use of unbounded data domains (like integers with arithmetic) does not guarantee convergence for all programs.

In fact, this circuit implements the standard naïve evaluation algorithm (e.g., see Algorithm 1 in (greco-sldm15, )). Notice that the inner part of the circuit is the incremental form of another circuit, since it is sandwiched between $ℐ$ and $𝒟$ operators. Using the cycle rule of Proposition 3.2 we can rewrite this circuit as:

(5.1)

This last circuit effectively implements the semi-naïve evaluation algorithm (Algorithm 2 from (greco-sldm15, )). The correctness of semi-naïve evaluation is an immediate consequence of the cycle rule.

6. Incremental recursive programs

In §2–4 we showed how to incrementalize a relational query by compiling it into a circuit, lifting the circuit to compute on streams, and applying the ${\cdot }^{\mathrm{\Delta }}$ operator to the lifted circuit. In §5.1 we showed how to compile a recursive query into a circuit that employs incremental computation internally to compute the fixed point. Here we combine these results to construct a circuit that evaluates a recursive query incrementally. The circuit receives a stream of updates to input relations, and for every update recomputes the fixed point. To do this incrementally, it preserves the stream of changes to recursive relations produced by the iterative fixed point computation, and adjusts this stream to account for the modified inputs. Thus, every element of the input stream yields a stream of adjustments to the fixed point computation, using nested streams.

Nested streams, or streams of streams, ${𝒮}_{{𝒮}_A}=\mathbb{N}\to \left(\mathbb{N}\to A\right)$, are well defined, since streams form an abelian group. Equivalently, a nested stream is a value in $\mathbb{N}\times \mathbb{N}\to A$, i.e., a matrix with an infinite number of rows, indexed by two-dimensional time $(t_0,t_1)$. where each row is a stream. In §A.1 we show a few example nested stream computations.

Lifting a stream operator $S:{𝒮}_A\to {𝒮}_B$ yields an operator over nested streams $\uparrow S:{𝒮}_{{𝒮}_A}\to {𝒮}_{{𝒮}_B}$, such that $(\uparrow S)\left(s\right)=S\circ s$, or, pointwise: $(\uparrow S\left(s\right))\left[t_0\right]\left[t_1\right]=S\left(s\left[t_0\right]\right)\left[t_1\right],\forall t_0,t_1\in \mathbb{N}$. In particular, a scalar function $f:A\to B$ can be lifted twice to produce an operator between streams of streams: $\uparrow \uparrow f:{𝒮}_{{𝒮}_A}\to {𝒮}_{{𝒮}_B}$.

We define a partial order over timestamps: $(i_0,i_1)\le (t_0,t_1)$ iff $i_0\le t_0$ and $i_1\le t_1$. We extend the definition of strictness for operators over nested streams: a stream operator $F:{𝒮}_{{𝒮}_A}\to {𝒮}_{{𝒮}_B}$ is strict if for any $s,s^{\prime }\in {𝒮}_{{𝒮}_A}$ and all times $t,i\in \mathbb{N}\times \mathbb{N}$ we have implies $F\left(s\right)\left[t\right]=F\left(s^{\prime }\right)\left[t\right]$. Proposition 2.10 holds for this notion of strictness, i.e., the fixed point operator $\text{fix}\alpha .F\left(\alpha \right)$ is well defined for a strict operator $F$.

Proposition 6.1:

The operator $\uparrow z^{-1}:{𝒮}_{{𝒮}_A}\to {𝒮}_{{𝒮}_A}$ is strict.

The operator $z^{-1}$ on nested streams delays “rows” of the matrix, while $\uparrow z^{-1}$ delays “columns”. (See examples in §A.1).

The $ℐ$ operator on ${𝒮}_{{𝒮}_A}$ operates on rows of the matrix, treating each row as a single value. Lifting a stream operator computing on ${𝒮}_A$, such as $ℐ:{𝒮}_A\to {𝒮}_A$, also produces an operator on nested streams, but this time computing on the columns of the matrix $\uparrow ℐ:{𝒮}_{{𝒮}_A}\to {𝒮}_{{𝒮}_A}.$

Proposition 6.2 (Lifting cycles):

For a binary, causal $T$ we have: $\uparrow (\lambda s.\text{fix}\alpha .T(s,z^{-1}\left(\alpha \right)))=\lambda s.\text{fix}\alpha .(\uparrow T)(s,(\uparrow z^{-1})\left(\alpha \right))$ i.e., lifting a circuit containing a “cycle” can be accomplished by lifting all operators independently, including the $z^{-1}$ back-edge.

This means that lifting a DBSP stream function can be expressed within DBSP itself. For example, we have:

$\cong$

This proposition gives the ability to lift entire circuits, including circuits computing on streams and having feedback edges, which are well-defined, due to Proposition 6.1. With this machinery we can now apply Algorithm 4.8 to arbitrary circuits, even circuits built for recursively-defined relations. Consider the “semi-naive” circuit (5.1), and denote $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}\circ R$ with $T$:

Lift the entire circuit using Proposition 6.2 and incrementalize it:

Now apply the chain rule to this circuit:

(6.1)

This is the incremental version of an arbitrary recursive query.

6.1. Example

In this section we derive the incremental version of a circuit containing recursion, by applying Algorithm 4.8. We start with a very simple program, expressed in Datalog, which computes the transitive closure of a directed graph:

⬇

// Edge relation with head and tail

input relation E(h: Node, t: Node)

// Reach relation with source s and sink t

output relation R(s: Node, t: Node)

R(x, x) :- E(x, _).

R(x, x) :- E(_, x).

R(x, y) :- E(x, y).

R(x, y) :- E(x, z), R(z, y).

We haven’t explained how Datalog is translated to circuits, but most Datalog operators are relational in nature. Assuming one could write recursive queries in SQL where a view is defined in terms of itself, the above program would be implemented by the following (illegal) SQL query:

⬇

CREATE VIEW R AS

(SELECT E.h, E.h FROM E)

UNION

(SELECT E.t, E.t FROM E)

UNION

(SELECT * FROM E)

UNION

(SELECT E.h, R.t

FROM E JOIN R

ON E.t = R.s)

We apply the algorithm from §5.1 to create first the non-recursive circuit, by assuming that R is already computed as a view R1, and using R1 in the definition of R instead of itself:

⬇

CREATE VIEW Reach AS

(SELECT E.h, E.h FROM E)

UNION

(SELECT E.t, E.t FROM E)

UNION

(SELECT * FROM E)

UNION

(SELECT E.h, R1.t

FROM E JOIN R ON E.t = R1.s)

Now we implement this query as a DBSP circuit with two inputs E and R1:

Now lift the circuit by lifting each operator pointwise, and connect it in a feedback loop by connecting input R1 from the output R through a $z^{-1}$operator and bracket everything with ${\delta }_0--\int$:

The above circuit is a complete implementation of the non-streaming recursive query; given an input relation E it will produce its transitive closure R at the output.

Now we use the seminaïve property 5.1 to rewrite the circuit:

(To save space in the figures we will omit the indices from $\pi$ and $\sigma$ in the subsequent figures, for example by writing just $\pi$ instead of ${\pi }_h$.)

Using the linearity of $\uparrow \pi$ and $\uparrow \sigma$, this can be rewritten as an equivalent circuit:

To make this circuit into a streaming computation that evaluates a new transitive closure for a stream of inputs E, we lift it entirely, using Proposition 6.2:

We convert this circuit into an incremental circuit, which receives in each transaction the changes to relation E and produces the corresponding changes to relation R:

We can now apply again the chain rule to this circuit:

We now take advantage of the linearity of $\uparrow {\delta }_0$, $\uparrow \int$, $\uparrow z^{-1}$, $\uparrow \uparrow \pi$, and $\uparrow \uparrow \sigma$ to simplify the circuit by removing some ${\cdot }^{\mathrm{\Delta }}$ invocations:

There are two applications of ${\cdot }^{\mathrm{\Delta }}$ left in this circuit: ${(\uparrow {(\uparrow \bowtie )}^{\mathrm{\Delta }})}^{\mathrm{\Delta }}$ and ${(\uparrow {(\uparrow \mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡})}^{\mathrm{\Delta }})}^{\mathrm{\Delta }}$. We expand their implementations separately, and we stitch them into the global circuit at the end. This ability to reason about sub-circuits independently highlights the modularity of DBSP.

The join is expanded twice, using the bilinearity of $\uparrow \bowtie$ and $\uparrow \uparrow \bowtie$. Let’s start with the inner circuit, implementing ${(\uparrow \bowtie )}^{\mathrm{\Delta }}$, given by Theorem 3.4:

$\cong$

Now we lift and incrementalize to get the circuit for ${(\uparrow {(\uparrow \bowtie )}^{\mathrm{\Delta }})}^{\mathrm{\Delta }}$:

Applying the chain rule and the linearity of $\uparrow ℐ$ and $\uparrow z^{-1}$ this becomes:

We now have three applications of ${(\uparrow \uparrow \bowtie )}^{\mathrm{\Delta }}$. Each of these is the incremental form of a bilinear operator, so it looks like in the end we will have $3\times 3$ applications of $\uparrow \uparrow \bowtie$. In fact, the overall expression can be simplified (see (tr, ) for a precise derivation), and the end result only has 4 terms in $\uparrow \uparrow \bowtie$.

Here is the final form of the expanded join circuit:

Returning to ${(\uparrow {(\uparrow \mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡})}^{\mathrm{\Delta }})}^{\mathrm{\Delta }}$, we can compute its circuit by expanding once using Proposition 4.7:

$\cong$

Finally, stitching all these pieces together we get the final circuit shown in Figure 2.

Figure 2. Final form of circuit from §6.1.

6.2. Complexity of incremental recursive queries

Time complexity

The time complexity of an incremental recursive query can be estimated as a product of the number of fixed point iterations and the complexity of each iteration. The incrementalized circuit (6.1) performs the same number of iterations as the non-incremental circuit (5.1) in the worst case: once the non-incremental circuit reaches the fixed point, its output is constant and so is its derivative computed by the incrementalized circuit.

Consider a nested stream of changes $s\in {𝒮}_{{𝒮}_A},s\left[t_1\right]\left[t_2\right]$, where $t_1$ is the input timestamp and $t_2$ is the fixed point iteration number. The unoptimized loop body ${(\uparrow {(\uparrow T)}^{\mathrm{\Delta }})}^{\mathrm{\Delta }}=𝒟\circ \uparrow 𝒟\circ \uparrow \uparrow T\circ \uparrow ℐ\circ ℐ$ has the same time complexity as $T$ applied to the aggregated input of size $R\left(s\right)\left[t_1\right]\left[t_2\right]\stackrel{\text{def}}{=}\parallel (\uparrow ℐ\circ ℐ)\left(s\right)\left[t_1\right]\left[t_2\right]\parallel =\parallel {\sum }_{(i_1,i_2)\le (t_1,t_2)}s\left[i_1\right]\left[i_2\right]\parallel$. As before, an optimized circuit can be significantly more efficient. For instance, by applying Theorem 3.4 twice, to $\bowtie$ and $\uparrow \bowtie$, we obtain a circuit for nested incremental join $s_1{(\uparrow {(\uparrow \bowtie )}^{\mathrm{\Delta }})}^{\mathrm{\Delta }}{s}_2$ that runs in $O(\parallel \uparrow ℐ\left(s1\right)\left[t1\right]\left[t2\right]\parallel \times \parallel ℐ\left(s2\right)\left[t1\right]\left[t2\right]\parallel )\ll O(R\left(s_1\right)\times R\left(s_2\right))$ (because each term is correspondingly smaller).

Space complexity

Integration ($ℐ$) and differentiation ($𝒟$) of a stream $s\in {𝒮}_{{𝒮}_A}$ uses memory proportional to ${\sum }_{t_2}\Vert {\sum }_{t_1}s\left[t_1\right]\left[t_2\right]\Vert$, i.e., the total size of changes aggregated over columns of the matrix. The unoptimized circuit integrates and differentiates respectively inputs and outputs of the recursive program fragment. As we move $ℐ$ and $𝒟$ inside the circuit using the chain rule, we additionally store changes to intermediate streams. Effectively we cache results of fixed point iterations from earlier timestamps to update them efficiently as new input changes arrive. Notice that space is proportional to the number of iterations of the inner while loop.

7. Extensions

The DBSP language can express a richer class of streaming computations (both incremental and non-incremental) than those covered so far. In this section we give several examples.

7.1. Multisets and bags

In §4 we have shown how to implement the relational algebra on sets. Some SQL queries however produce multisets, e.g., UNION ALL. Since $\mathbb{Z}$-sets generalize multisets and bags, it is easy to implement query operators that compute on such structures. For example, while SQL UNION is $\mathbb{Z}$-set addition followed by $\mathrm{𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡}$, UNION ALL is just $\mathbb{Z}$-set addition.

7.2. Aggregation

Aggregation in SQL applies a function $a$ to a whole set producing a “scalar” result with some type $R$: $a:2^A\to R$. We convert such aggregation functions to operate on $\mathbb{Z}$-sets, so in DBSP an aggregation function has a signature $a:\mathbb{Z}\left[A\right]\to R$. Correctness of the implementation is defined as in §4.2.1.

The SQL COUNT aggregation function is implemented on $\mathbb{Z}$-sets by $a_{\text{COUNT}}:\mathbb{Z}\left[A\right]\to \mathbb{Z}$, which computes a sum of all the element weights: $a_{\text{COUNT}}\left(s\right)={\sum }_{x\in s}s\left[x\right]$. The SQL SUM aggregation function is implemented on $\mathbb{Z}$-sets by $a_{\text{SUM}}:\mathbb{Z}\left[ℝ\right]\to ℝ$ which performs a weighted sum of all (real) values: $a_{\text{SUM}}\left(s\right)={\sum }_{x\in s}x\times s\left[x\right]$.

With this definition the aggregation functions $a_{\text{COUNT}}$ and $a_{\text{SUM}}$ are in fact linear transformations between the group $\mathbb{Z}\left[A\right]$ and the result group ($\mathbb{Z}$, and $ℝ$ respectively).

If the output of the DBSP circuit can be such a “scalar” value, then aggregation with a linear function is simply function application, and thus it is automatically incremental. However, in general, for composing multiple queries we require the result of an aggregation to be a singleton $\mathbb{Z}$-set (containing a single value), and not a scalar value. In this case the aggregation function is implemented in DBSP as the composition of the actual aggregation and the $\text{makeset}:A\to \mathbb{Z}\left[A\right]$ function, which converts a scalar value of type $A$ to a singleton $\mathbb{Z}$-set, defined as follows: $\text{makeset}\left(x\right)\stackrel{\text{def}}{=}1\cdot x$.

In conclusion, the following SQL query: SELECT SUM(c) FROM I is implemented as the following circuit:

The lifted incremental version of this circuit is interesting: since $\pi$ and $a_{\text{SUM}}$ are linear, they are equivalent to their own incremental versions. Although ${(\uparrow \text{makeset})}^{\mathrm{\Delta }}=𝒟\circ \uparrow \text{makeset}\circ ℐ$ cannot be simplified, it is nevertheless efficient, doing only O(1) work per invocation, since its input and output are singleton values.

An aggregation function such as AVG can be written as the composition of a more complex linear function that computes a pair of values using SUM and COUNT, followed by a makeset and a selection operation that divides the two columns.

⬇

SELECT AVG(c) FROM I

Finally, some aggregate functions, such as MIN, are not incremental in general, since for handling deletions they may need to know the full set, and not just its changes. The lifted incremental version of such aggregate functions is implemented essentially by “brute force”, using the formula ${(\uparrow a_{\text{MIN}})}^{\mathrm{\Delta }}=𝒟\circ \uparrow a_{\text{MIN}}\circ ℐ$. Such functions perform work proportional to $R\left(s\right)$ at each invocation.

Note that the SQL ORDER BY directive can be modeled as a non-linear aggregate function that emits a list. However, such an implementation it is not efficiently incrementalizable in DBSP. We leave the efficient handling of ORDER BY to future work.

Even when aggregation results do not form a group, they usually form a structure with a zero element. We expect that a well-defined aggregation function maps empty $\mathbb{Z}$-sets to zeros in the target domain.

7.3. Grouping; indexed relations

Pick an arbitrary set $K$ of “key values.” Consider the mathematical structure of finite maps from $K$ to $\mathbb{Z}$-sets over some other domain $A$: $K\to \mathbb{Z}\left[A\right]=\mathbb{Z}\left[A\right]\left[K\right]$. We call values $i$ of this structure indexed $\mathbb{Z}$-sets: for each key $k\in K$, $i\left[k\right]$ is a $\mathbb{Z}$-set. Because the codomain $\mathbb{Z}\left[A\right]$ is an abelian group, this structure is itself an abelian group.

We use this structure to model the SQL GROUP BY operator in DBSP. Consider a partitioning function $p:A\to K$ that assigns a key to any value in $A$. We define the grouping function $G_p:\mathbb{Z}\left[A\right]\to \left(K\to \mathbb{Z}\left[A\right]\right)$ as $G_p\left(a\right)\left[k\right]\stackrel{\text{def}}{=}{\sum }_{x\in a.p\left(x\right)=k}a\left[x\right]\cdot x$. When applied to a $\mathbb{Z}$-set $a$ this function returns a indexed $\mathbb{Z}$-set, where each element is called a grouping: for each key $k$ a grouping is a $\mathbb{Z}$-set containing all elements of $a$ that map to $k$ (as in SQL, groupings are multisets, represented by $\mathbb{Z}$-sets). Consider our example $\mathbb{Z}$-set $R$ from §4, and a key function $p\left(s\right)$ that returns the first letter of the string $s$. Then we have that $G_p\left(R\right)=\left\{\text{j}\mapsto \left\{\text{joe}\mapsto 1\right\},\text{a}\mapsto \left\{\text{anne}\mapsto -1\right\}\right\}$, i.e., grouping with this key function produces an indexed $\mathbb{Z}$-set with two groupings, each of which contains a $\mathbb{Z}$-set with one element.

The grouping function $G_p$ is linear for any $p$. It follows that the group-by implementation in DBSP is automatically incremental: given some changes to the input relation we can apply the partitioning function to each change separately to compute how each grouping changes.

7.4. GROUP BY-AGGREGATE

Grouping in SQL is almost always followed by aggregation. Let us consider an aggregation function $a:\left(K\times \mathbb{Z}\left[A\right]\right)\to B$ that produces values in some group $B$, and an indexed relation of type $\mathbb{Z}\left[A\right]\left[K\right]$, as defined above in §7.3. The nested relation aggregation operator $Ag{g}_a:\mathbb{Z}\left[A\right]\left[K\right]\to B$ applies $a$ to the contents of each grouping independently and adds the results: $Ag{g}_a\left(g\right)\stackrel{\text{def}}{=}{\sum }_{k\in K}a(k,g\left[k\right])$. To apply this to our example, let us compute the equivalent of GROUP-BY count; we use the following aggregation function $count:K\times \mathbb{Z}\left[A\right]$, $count(k,s)=\text{makeset}\left((k,a_{\text{COUNT}}\left(s\right))\right)$, using the $\mathbb{Z}$-set counting function $a_{\text{COUNT}}$ from §7.2; the notation $(a,b)$ is a pair of values $a$ and $b$. Then we have $Ag{g}_{count}\left(G_p\left(R\right)\right)=\left\{(\text{j},1)\mapsto 1,(\text{a},-1)\mapsto 1\right\}$.

Notice that, unlike SQL, DBSP can express naturally computations on indexed $\mathbb{Z}$-sets, they are just an instance of a group structure. One can even implement queries that operate on each grouping in an indexed $\mathbb{Z}$-set. However, our definition of incremental computation is only concerned with incrementality in the outermost structures. We leave it to future work to explore an appropriate definition of incremental computation that operates on the inner relations.

A very useful operation on nested relations is flatmap, which is essentially the inverse of partitioning, converting an indexed $\mathbb{Z}$-set into a $\mathbb{Z}$-set: $\text{flatmap}:\mathbb{Z}\left[A\right]\left[K\right]\to \mathbb{Z}\left[A\times K\right]$. flatmap is in fact a particular instance of aggregation, using the aggregation function $a:K\times \mathbb{Z}\left[A\right]\to \mathbb{Z}\left[A\times K\right]$ defined by $a(k,s)={\sum }_{x\in s\left[k\right]}s\left[k\right]\left[x\right]\cdot (k,x).$ For our previous example, $\text{flatmap}\left(G_p\left(R\right)\right)=\left\{(\text{j},\text{joe})\mapsto 1,(\text{a},\text{anne})\mapsto -1\right\}$.

If we use an aggregation function $a:K\times Z\left[A\right]$ that is linear in its second argument, then the aggregation operator $Ag{g}_a$ is linear, and thus fully incremental. As a consequence, flatmap is linear. However, many practical aggregation functions for nested relations are in fact not linear; an example is the $count$ function above, which is not linear since it uses the makeset non-linear function. Nevertheless, while the incremental evaluation of such functions is not fully incremental, it is at least partly incremental: when applying a change to groupings, the aggregation function only needs to be re-evaluated for groupings that have changed.

7.5. Antijoin

Antijoins arise in the implementation of Datalog programs with stratified negation. Consider the following program:

⬇

O(v, z) :- I1(v, z), not I2(v).

The semantics of such a rule is defined in terms of joins and set difference. This rule is equivalent with the following pair of rules:

⬇

C(v, z) :- I1(v, z), I2(v).

O(v, z) :- I1(v, z), not C(v, z).

This transformation reduces an antijoin to a join followed by a set difference. This produces the following DBSP circuit:

7.6. Streaming joins

Consider a binary query $T(s,t)=ℐ\left(s\right)\uparrow \bowtie t$. This is the relation-to-stream join operator supported by streaming databases like ksqlDB (jafarpour-edbt19, ). Stream $s$ carries changes to a relation, while $t$ carries arbitrary data, e.g., logs or telemetry data points. $T$ discards values from $t$ after matching them against the accumulated contents of the relation.

7.6.1. Streaming Window queries

Streaming databases often organize the contents of streams into windows, which store a subset of data points with a predefined range of timestamps. The circuit below (a convolution filter in DSP) computes a fixed-size sliding-window aggregate over the last four timestamps defined by the $T_i$ functions.

In practice, windowing is usually based on physical timestamps attached to stream values rather than logical time. For instance, the CQL (arasu-tr02, ) query “SELECT * FROM events [RANGE 1 hour]” returns all events received within the last hour. The corresponding circuit (on the left) takes input stream $s\in {𝒮}_{\mathbb{Z}\left[A\right]}$ and an additional input $\theta \in {𝒮}_{ℝ}$ that carries the value of the current time.

$\cong$

where the window operator $W$ prunes input $\mathbb{Z}$-sets, only keeping values with timestamps less than an hour behind $\theta \left[t\right]$. Assuming $ts:A\to ℝ$ returns the physical timestamp of a value, $W$ is defined as $W(v,\theta )\left[t\right]\stackrel{\text{def}}{=}\{x\in v\left[t\right].ts\left(x\right)\ge \theta \left[t\right]-1hr\}$. Assuming $\theta$ increases monotonically, $W$ can be moved inside integration, resulting in the circuit on the right, which uses bounded memory to compute a window of an unbounded stream. This circuit is a building block of a large family of window queries, including window joins and aggregation. We conjecture that DBSP can express any CQL query.

7.7. Relational while queries

(See also non-monotonic semantics for Datalog^¬ and Datalog^¬¬(Abiteboul-book95, ).) To illustrate the power of DBSP we implement the following “while” program, where $Q$ is an arbitrary relational algebra query:

⬇

x := i;

while (x changes)

x := Q(x);

The DBSP implementation of this program is:

This circuit can be converted to a streaming circuit that computes a stream of values $i$ by lifting it; it can be incrementalized using Algorithm 4.8 to compute on changes of $i$:

Note that at runtime the execution of this circuit is not guaranteed to terminate; however, if the circuit does terminate, it will produce the correct output, i.e., the least fixpoint of $Q$ that includes $i$.

8. Implementation

We are prototyping an implementation of DBSP as part of an open-source project with an MIT license: https://github.com/vmware/database-stream-processor. The implementation is written in Rust. The implementation consists of a library and a runtime. The library provides APIs for basic algebraic data types: such as groups, finite maps, $\mathbb{Z}$-set, indexed $\mathbb{Z}$-set. A separate circuit construction API allows users to create DBSP circuits by placing operator nodes (corresponding to boxes in our diagrams) and connecting them with streams, which correspond to the arrows in our diagrams. The library provides pre-built generic operators for integration, differentiation, delay, nested integration and differentiation. The $\mathbb{Z}$-set library provides functions for computing the basic $\mathbb{Z}$-set operations corresponding to plus, negation, grouping, joining, aggregation.

For iterative computations we provide the ${\delta }_0$ operator and an operator that approximates $\int$ by terminating iteration of a loop at a user-specified condition (usually the condition is the requirement for a zero to appear in a specified stream). The low level library allows users to construct incremental circuits manually. Our plan is to add a higher-level library (a compiler) which will automatically incrementalize a circuit.

9. Related work

DBSP using non-nested streams is a simplified instance of a Kahn network (kahn-ifip74, ). Johnson (johnson-phd83, ) studies a very similar computational model without nested streams and its expressiveness. The implementation of such streaming models of computation and their relationship to dataflow machines has been studied by Lee (lee-ieee95, ). Lee (lee-ifip93, ) also introduced streams of streams and the $\uparrow z^{-1}$ operator.

In §7 we have discussed the connections with window and stream database queries (arasu-tr02, ; aurora, ).

Incremental view maintenance (e.g. (gupta-idb93, )) is surveyed in (gupta-idb95, ); a large bibliography is present in (motik-ai19, ). Its most formal aspect is propagating “deltas” through algebraic expressions: $Q\left(R+\mathrm{\Delta }R\right)=Q\left(R\right)+\mathrm{\Delta }Q(R,\mathrm{\Delta }R)$. This work eventually crystallized in (koch-pods16, ). DBSP incrementalization is both more modular and more fine-grain since it deals with streams of updates. Both (koch-pods10, ) and (green-tcs11, ) use $\mathbb{Z}$-sets to uniformly model insertions/deletions.

Picallo et al. (picallo-scop19, ) provide a general solution to IVM for rich languages. DBSP requires a group structure on the values operated on; this assumption has two major practical benefits: it simplifies the mathematics considerably (e.g., Picallo uses monoid actions to model changes), and it provides a general, simple algorithm (4.8) for incrementalizing arbitrary programs. The downside of DBSP is that one has to find a suitable group structure (e.g., $\mathbb{Z}$-sets for sets) to “embed” the computation. Picallo’s notion of “derivative” is not unique: they need creativity to choose the right derivative definition, we need creativity to find the right group structure.

Many heuristic algorithms were published for Datalog-like languages, e.g., counting based approaches (Dewan-iis92, ; motik-aaai15, ) that maintain the number of derivations, DRed (gupta-sigmod93, ) and its variants (Ceri-VLDB91, ; Wolfson-sigmod91, ; Staudt-vldb96, ; Kotowski-rr11, ; Lu-sigmod95, ; Apt-sigmod87, ), the backward-forward algorithm and variants (motik-aaai15, ; Harrison-wdd92, ; motik-ai19, ). DBSP is more general than these approaches. Interestingly, the $\mathbb{Z}$-sets multiplicities in our relational implementation are related to the counting-number-of-derivations approaches.

DBSP is tightly related to Differential Dataflow (DD) (mcsherry-cidr13, ; murray-sosp13, ) and its theoretical foundations (abadi-fossacs15, ) (and recently (mchserry-vldb20, ; chothia-vldb16, )). All DBSP operators are based on DD operators. DD’s computational model is more powerful than DBSP, since it allows past values in a stream to be ”updated”. In contrast, our model assumes that the inputs of a computation arrive in the time order while allowing for nested time domains via the modular lifting transformer. However, DBSP can express both incremental and non-incremental computations; in essence DBSP is “deconstructing” DD into simple component building blocks; the core Proposition 3.2 and the Algorithm based on it 4.8 are new contributions.

10. Conclusions

In this paper we have introduced DBSP, a model of computation based on infinite streams over abelian groups. In this model streams are used to model consecutive snapshots of a database, consecutive changes (or transactions) applied to a database, and consecutive values of loop-carried variables.

We have defined an abstract notion of incremental computation over streams, and defined the incrementalization operator ${\cdot }^{\mathrm{\Delta }}$, which transforms a stream computation $Q$ into its incremental version $Q^{\mathrm{\Delta }}$. The incrementalization operator has some very nice algebraic properties, which can generate very efficient incremental implementations for linear and bilinear computations.

We have then applied these tools to two domains: relational queries and recursive stratified queries. This gave us a general algorithm for incrementalizing an arbitrary query, including recursive queries. However, we believe that both the incrementalization algorithm and DBSP are even more powerful and can apply to even richer classes of query languages, including languages operating on nested relations and streaming query languages.

Appendix A Supporting material

A.1. Operations on nested streams

If a stream can be thought of as an infinite vector, a stream of streams can be thought of as an “matrix” with an infinite number of rows, where each row is a stream. For example, we can depict the nested stream $i\in {𝒮}_{{𝒮}_{\mathbb{N}}}$ defined by $i\left[t_0\right]\left[t_1\right]=t_0+2t_1$ as: i = arg0 1 2 3 2 3 4 5 4 5 6 7 6 7 8 9 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

($t_0$ is the column index, and $t_1$ is the row index). Let us perform some computations on nested streams to get used to them. Lifting twice a scalar function computes on elements of the matrix pointwise:

(↑↑(x ↦x mod2))(i) = arg0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

The $ℐ$ operator on ${𝒮}_{{𝒮}_A}$ is well-defined: it operates on rows of the matrix, treating each row as a single value:

I(i) = arg0 1 2 3 2 4 6 8 6 9 12 15 12 16 20 24 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

Lifting a stream operator computing on ${𝒮}_A$, such as $ℐ:{𝒮}_A\to {𝒮}_A$, also produces an operator on nested streams, but this time computing on the columns of the matrix: $\uparrow ℐ:{𝒮}_{{𝒮}_A}\to {𝒮}_{{𝒮}_A}.$

(↑I)(i) = arg0 1 3 6 2 5 9 14 4 9 15 22 6 13 21 30 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

Similarly, we can apply $𝒟$ to nested streams $𝒟:{𝒮}_{{𝒮}_A}\to {𝒮}_{{𝒮}_A}$, computing on rows of the matrix:

D(i) = arg0 1 2 3 2 2 2 2 2 2 2 2 2 2 2 2 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

while $\uparrow 𝒟:{𝒮}_{{𝒮}_A}\to {𝒮}_{{𝒮}_A}$ computes on the columns:

(↑D)(i) = arg0 1 1 1 2 1 1 1 4 1 1 1 6 1 1 1 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

Similarly, $z^{-1}$ and its lifted variant have different outcomes:

$z^{-1}$(i) = arg0 0 0 0 0 1 2 3 2 3 4 5 4 5 6 7 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

Notice the following commutativity properties for integration and differentiation on nested streams: $ℐ\circ (\uparrow ℐ)=(\uparrow ℐ)\circ ℐ$ and $𝒟\circ (\uparrow 𝒟)=(\uparrow 𝒟)\circ 𝒟$.

(↑$z^{-1}$)(i) = arg0 0 1 2 0 2 3 4 0 4 5 6 0 6 7 8 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

$z^{-1}$ commutes with $\uparrow z^{-1}$:

(↑$z^{-1}$)($z^{-1}$(i)) = $z^{-1}$((↑$z^{-1}$)(i)) = arg0 0 0 0 0 0 1 2 0 2 3 4 0 4 5 6 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

D_${𝒮}_{{𝒮}_{\mathbb{N}}}$(i) = (D(↑D))(i) = arg0 1 1 1 2 0 0 0 2 0 0 0 2 0 0 0 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]

I_${𝒮}_{{𝒮}_{\mathbb{N}}}$(i) = ((↑I)(I))(i)= arg0 1 3 6 2 6 12 20 6 15 27 42 12 28 48 72 [[arg[1]arg[2]arg[3]arg[4]⋯][arg[5]arg[6]arg[7]arg[8]⋯][arg[9]arg[10]arg[11]arg[12]⋯][arg[13]arg[14]arg[15]arg[16]⋯]⋮]