(front)
DBSP：流上的增量计算及其在数据库中的应用（DBSP: Incremental Computation on Streams and Its Applications to Databases）[^1]
摘要ABSTRACT
We describe DBSP, a framework for incremental computation. Incremental computations repeatedly evaluate a function on some input values that are “changing”. The goal of an e▯cient implementation is to “reuse” previously computed results.
我们介绍 DBSP，一个用于增量计算的框架。增量计算会反复地对某些“不断变化”的输入值求值一个函数。高效实现的目标是“复用”此前已经计算出的结果。理想情况下，当输入出现新的变化时，增量计算只应花费与输入变化的大小成正比的工作量，而不是与整个数据集的大小成正比。
In databases “incremental computation” is known as Incremental View Maintenance (IVM); IVM has long been a central problem of database theory and practice. Many solutions have been proposed for restricted classes of computation or of changes, but we are seeking a general solution.
在数据库领域，“增量计算”被称为增量视图维护（incremental view maintenance, IVM）；IVM 长期以来一直是数据库理论与实践中的核心问题。针对受限的计算类别或变化类别，人们已经提出了许多解决方案，但我们寻求的是一种通用的解决方案。
We start by defining incremental computations as computations on data streams, i.e., sequences of data values, by borrowing ideas from Digital Signal Processing.
我们首先借鉴数字信号处理（Digital Signal Processing, DSP）的思想，把增量计算定义为数据流上的计算——数据流即数据值构成的序列。
Using these tools, we give a general solution to the incremental computation problem in 4 steps: (1) we describe a simple but expressive language called DBSP for describing computations over data streams; (2) we give a new mathematical definition of incremental computation for DBSP programs; (3) we give a general algorithm for converting any DBSP program into an incremental program. The algorithm reduces the problem of incrementalizing a complex query to the problem of incrementalizing the primitive operations that compose the query. Finally, (4) we show that practical database query languages, such as SQL and Datalog, can be directly implemented on top of DBSP, using primitives with e▯cient incremental implementations. As a consequence, we obtain a general recipe for e▯cient IVM for essentially arbitrary queries written in all these languages.
借助这些工具，我们分 4 步给出增量计算问题的一个通用解决方案：(1) 我们描述一种称为 DBSP 的简单而富有表达力的语言，用于描述数据流上的计算；(2) 我们给出 DBSP 程序上增量计算的一个新的数学定义；(3) 我们给出一个通用算法，把任意 DBSP 程序转换为增量程序。该算法把“对复杂查询增量化”的问题，归约为“对组成该查询的各基本操作分别增量化”的问题。最后，(4) 我们说明，实用的数据库查询语言（例如 SQL 与 Datalog）可以直接构建在 DBSP 之上，所用原语都具有高效的增量实现。因此，我们得到了一个通用配方，可为用所有这些语言编写的、本质上任意的查询给出高效的 IVM。
1 引言1. INTRODUCTION
1.1 增量计算1.1 Incremental computation
Incremental view maintenance (IVM) is an important and well-studied problem in databases [14]. The IVM problem the VLDB Endowment. This is a simplified version of the paper entitled DBSP: Automatic Incremental View Maintenance for Rich Query Languages, published in PVLDB, Vol. 16, Issue 7, ISSN 2150-8097 [5].
增量视图维护（incremental view maintenance, IVM）是数据库中一个重要且已被深入研究的问题 [14]。IVM 问题可以表述如下：给定一个大型数据库 $DB$（比如说 10 亿条记录）和一个视图 $V$，$V$ 由查询 $Q$ 描述。IVM 的目标是在数据库发生变化时保持 $V$ 的内容最新。
The goal of IVM is to keep the contents of V up-to-date in response to changes of the database. As a concrete example, consider the following view definition statement in SQL: CREATE VIEW V AS SELECT * FROM T WHERE Age >= 10. In this example the query Q defining the view V is SELECT * FROM T WHERE Age >= 10. The view V always contains all the rows of table T whose value for the column Age is greater than or equal to 10.
作为一个具体例子，考虑下面这条定义视图的 SQL 语句：CREATE VIEW V AS SELECT * FROM T WHERE Age >= 10。在这个例子中，定义视图 $V$ 的查询 $Q$ 就是 SELECT * FROM T WHERE Age >= 10。视图 $V$ 始终包含表 $T$ 中 Age 列的取值大于或等于 10 的所有行。
In general a query is a function applied to the database state: V = Q(DB). A na¨ıve solution re-executes query Q every time the database changes, illustrated in the following diagram. Time is the horizontal axis; the horizontal arrows labeled with ▯ depict changes to the database, which we assume are much smaller than the database itself (e.g., a change could touch perhaps 100 records).
一般地，查询是施加于数据库状态的函数：$V = Q(DB)$。一种朴素的解法是：每当数据库发生变化，就重新执行一次查询 $Q$，如下图所示。图中水平轴是时间；标有 $\Delta$ 的水平箭头表示对数据库的变化，我们假定这些变化远小于数据库本身（例如，一次变化可能只触及约 100 条记录）。竖直的“向上”箭头表示对每个数据库快照重新求值 $Q$。
V[1] V[2] V[3] V[4]
▲ ▲ ▲ ▲
│Q │Q │Q │Q ← 竖直箭头：对每个快照重新求值 Q
│ │ │ │
DB[1] ───▶ DB[2] ───▶ DB[3] ───▶ DB[4] ← 数据库快照（约 1B 行）
ΔDB[1] ΔDB[2] ΔDB[3] ← 水平箭头：变化（约 100 行）
时间 ────────────────────────────────────────────▶
The “up” arrows show the re-evaluation of Q for each database snapshot. Time ΔDB[1] ΔDB[2] ΔDB[3] 𝑄 𝑄 𝑄 𝑄 Changes (Δ) 1B rows 100 rows V[1] V[2] V[3] V[4] DB[1] DB[2] DB[3] DB[4] The naive solution is expensive. After the first version of the view has been constructed, an ideal algorithm would compute only changes to the view ▯V doing work O(|▯DB|).
这种朴素解法的开销很大。在视图的第一个版本构造出来之后，理想的算法应当只计算视图的变化 $\Delta V$，所做的工作量为 $O(|\Delta DB|)$。理想情况下，我们希望构造一个新的查询 $Q^\Delta$，它具有性质 $\Delta V = Q^\Delta(\Delta DB)$，即 $Q^\Delta$ 能够由数据库的变化算出视图的变化：
ΔDB[0] ΔDB[1] ΔDB[2] ΔDB[3]
│ │ │ │
▼ ▼ ▼ ▼
[ Q ] [ Q^Δ ] [ Q^Δ ] [ Q^Δ ]
│ │ │ │
▼ ▼ ▼ ▼
V[1] ΔV[1] ΔV[2] ΔV[3]
If one thinks of Q▯ as a function of ▯DB, one can show that the ideal solution as described above is impossible to reach. In this paper we propose a new way to define Q▯, as a form of computation on streams. Our model is inspired by Digital Signal Processing DSP [16], applied to databases, hence the name DBSP.
图中第一个输入（初始的整个数据库）需要完整求值 $Q$ 才能得到 $V[1]$；此后每一步只需用 $Q^{\Delta}$ 由该步的变化 $\Delta DB[t]$ 算出视图的变化 $\Delta V[t]$，再把它累加到前一个视图快照上，即得 $V[t+1]$。
Q▯ can be very e▯cient. As for traditional database queries, the performance of Q▯ depends both on the query Q but also on the actual data that the query is applied to.
我们把 $Q^\Delta$ 称为 $Q$ 的增量版本。如果把 $Q^\Delta$ 看作 $\Delta DB$ 的函数，则可以证明：上面所描述的那种理想方案是无法达到的。
Informally, Q▯ built by our algorithm, is faster SIGMOD Record, March 2024 (Vol. 53, No. 1) 87 than Q by a factor of O(|DB|/|▯DB|). In practice this may be an improvement of several orders of magnitude. For our example above |DB| ⇡ 109 and |▯DB| ⇡ 102, this can make Q▯ 10 million times faster! Instead of treating the database as a large changing object, we model it as a sequence or stream of database snapshots.
本文提出一种定义 $Q^\Delta$ 的新方式，即把它视为流上的一种计算。我们的模型受数字信号处理（Digital Signal Processing, DSP）[16] 的启发并应用于数据库，DBSP 由此得名。$Q^\Delta$ 可以非常高效。与传统数据库查询一样，$Q^\Delta$ 的性能既取决于查询 $Q$，也取决于该查询实际作用的数据。粗略地说，由我们的算法构造的 $Q^\Delta$ 比 $Q$ 快 $O(|DB|/|\Delta DB|)$ 倍。在实践中，这可能是若干个数量级的改进。就上面的例子而言，$|DB| \approx 10^9$、$|\Delta DB| \approx 10^2$，这可以使 $Q^\Delta$ 快一千万倍！
DBSP is a simple programming language computing on streams; inputs and outputs are streams of arbitrary values. The DBSP language has only 4 operators. However, it can express a rich set of computations on streams, including repeated computations (similar to the repeated queries Q above), recursive computations that compute fixed points (like Datalog programs), streaming computations, and incremental computations (which we define shortly). The full paper [5] gives a precise mathematical description of DBSP, this presentation is simplified to convey the main intuitions.
我们不把数据库看作一个不断变化的大对象，而是把它建模为数据库快照构成的序列（即流）。类似地，相继的视图快照也构成一个流。DBSP 是一种在流上计算的简单编程语言；其输入与输出都是取任意值的流。DBSP 语言只有 4 个算子。然而，它可以表达丰富的流计算，包括重复计算（类似于上面重复出现的查询 $Q$）、计算不动点的递归计算（如 Datalog 程序）、流式计算，以及增量计算（我们稍后定义）。完整论文 [5] 给出了 DBSP 的精确数学描述，本文的呈现为传达主要直觉做了简化。本文省略了相关工作一节。
We omit the related work section from this presentation. The central result of this paper is Algorithm 4.1 which, given a DBSP program that computes on a stream of values, mechanically transforms it into an incremental DBSP program that computes on a stream of changes.
本文的核心结果是算法 4.1：给定一个在值流上计算的 DBSP 程序，它能机械地把该程序转换为一个在变化流上计算的增量 DBSP 程序。
DBSP is not tied to databases in any way; it is in fact a Turing-complete language that can be used for many other purposes.
DBSP 与数据库没有任何绑定；事实上它是一种图灵完备的语言，可用于许多其他目的。但它在数据库领域表现得特别好，原因有两个：
But it works particularly well in the area of databases, for two reasons: • DBSP operates on values from a commutative group.
- DBSP 作用于来自交换群（阿贝尔群）的值。数据库可以建模为一个交换群。
Databases can be modeled as a commutative group. • DBSP reduces the problem of incrementalizing a complex program to the problem of incrementalizing each primitive operation that appears in the program. For databases there are known e▯cient incremental implementations for all primitive operations.
- DBSP 把“对复杂程序增量化”的问题，归约为“对程序中出现的每个基本操作分别增量化”的问题。对于数据库，所有基本操作都有已知的高效增量实现。
1.2 电路与流1.2 Circuits and Streams
In this paper we use circuit diagrams to depict programs. In a circuit a rectangle represents a function, and an arrow represents an input or output value.
本文用电路图来描绘程序。在电路中，矩形表示一个函数，箭头表示一个输入或输出值。下图给出一个函数 $f$，它消费两个输入 $i$（第 0 个输入）与 $j$（第 1 个输入），产生一个输出 $o = f(i, j)$：
i ──▶ 0 ┐
├──▶ [f] ──▶ o
j ──▶ 1 ┘
The following diagram shows a function f consuming two inputs i (input 0) and j (input 1) and producing one output o = f (i, j): f i j o Most of the functions we deal with are commutative, so we can skip inputs label, displaying the circuit above as: i j f s Functions, and their circuits, can be composed, as in the following example for the function o = g(s) + (f (s) ⇥ s): s f ⇥ + g o We say that two circuits are equivalent if they compute the same function.
我们处理的大多数函数都是可交换的（即与参数的顺序无关），因此可以省略输入标号，把上面的电路画成：
i ──┐
├──▶ [f] ──▶ o
j ──┘
We use the symbol ≅ to indicate circuit equivalence.
函数及其电路可以复合，例如下面这个函数 $o = g(s) + (f(s) \times s)$：
s ──▶ [f] ──▶ f(s) ──┐
├──▶ [×] ──▶ f(s)×s ──┐
s ───────────────────┘ ├──▶ (+) ──▶ o
s ──▶ [g] ──▶ g(s) ────────────────────────┘
For example, we have the following circuit equivalence (where ▯ is function composition): s g f o ≅ s f ▯ g o (*)
如果两个电路计算相同的函数，我们就说它们是等价的。我们用符号 $\cong$ 表示电路等价。例如，我们有如下电路等价（其中 $\circ$ 表示函数复合）：
s ──▶ [g] ──▶ [f] ──▶ o ≅ s ──▶ [f ∘ g] ──▶ o (*)
1.3 流1.3 Streams
The core notion of DBSP is the stream. Given a set A, a stream of values from A is an infinite sequence of values from A. SA denotes the set of all streams with values from A. We write s[t] for the t-th element of the stream s.
DBSP 的核心概念是流。给定一个集合 $A$，一个取值为 $A$ 中值的流是 $A$ 中值构成的无限序列。$\mathcal{S}_A$ 表示所有取值为 $A$ 中值的流构成的集合。我们把流 $s$ 的第 $t$ 个元素写成 $s[t]$。把 $t$ 看作“时间”，把 $s[t] \in A$ 看作流 $s$ “在时刻” $t$ 的值。我们把流画成一串方框，时间自右向左递增：例如，流 $s[t] = t$ 是：
…… ┌───┬───┬───┬───┐
│ 3 │ 2 │ 1 │ 0 │
└───┴───┴───┴───┘
时间 ◀──────────────（越靠左越晚）
Think of t as the “time” and of s[t] 2 A as the value of the stream s “at time” t. We show streams as a sequence of boxes, with time from right to left: e.g., the stream s[t] = t is: · · · 3 2 1 0 ▯▯▯▯▯▯▯▯▯▯▯▯▯▯ time A stream operator is a function that computes on streams and produces streams.
流算子是作用在流上、并产生流的函数。一般地，我们用“算子”指流上的函数，用“函数”指“标量”值上的计算。我们用双箭头表示流。下图给出一个流算子 $T$，它消费两条输入流 $s_0$ 与 $s_1$，产生一条输出流 $s$：
s0 ══▶ 0 ┐
├──▶ [T] ══▶ s
s1 ══▶ 1 ┘
In general we use “operator” for streams, and “function” for computations on “scalar” values. We use arrows with a double head to depict streams. The following diagram shows a stream operator T consuming two input streams s0 and s1, producing one output stream s: T s0 s1 s We write s = T (s0, s1).
我们写 $s = T(s_0, s_1)$。给定函数 $f : A \to B$，我们通过把函数 $f$ 独立地作用于每个输入值，定义一个流算子 ${\uparrow}f : \mathcal{S}_A \to \mathcal{S}_B$（读作“$f$ 的提升”）：
· · · d c b a ══▶ [↑f] ══▶ · · · f(d) f(c) f(b) f(a)
Given a function f : A → B, we define a stream operator ↑f : SA → SB (read as “f lifted”) by applying function f to each input value independently: · · · d c b a ↑f · · · f(d) f(c) f(b) f(a) To simplify the notation, we write a + b for streams a, b instead of a("+)b; we also write ▯a instead of ("▯)a.
为简化记号，对两个流 $a$、$b$，我们写 $a + b$，而不写 $a\,(+)\,b$；同样，我们把 $(-)a$ 写成 $-a$。
1.4 数据库即流1.4 Databases as streams
We generally think of streams as sequences of “small” values, such as insertions or deletions in a database. However, we also treat the whole database as a stream of database snapshots. We model a database as a stream DB. Time is not wall-clock time, but counts the transactions applied to the database.
我们通常把流看作“小”值的序列，例如数据库中的插入或删除。不过，我们也把整个数据库看作数据库快照构成的流。我们把数据库建模为一条流 $DB$。时间不是墙钟时间，而是对施加于数据库的事务的计数。由于事务是可线性化的，它们具有全序。$DB[t]$ 是已施加 $t$ 个事务之后数据库内容的快照。这一记号在 §1.1 的图中可以看出来。
DB[t] is the snapshot of the database contents after t transactions have been applied. This notation is apparent in the diagrams in Section 1.1. Database transactions also form a stream ▯DB, this time a stream of changes, or deltas, that are applied to the database. The values of this stream are defined by (▯DB)[t] = DB[t]▯ DB[t ▯ 1], where “▯” stands for the difference between two databases, a notion that we will soon make more precise.
数据库事务也构成一条流 $\Delta DB$，这一次是施加于数据库的变化（delta）的流。该流的值定义为 $(\Delta DB)[t] = DB[t] - DB[t-1]$，其中“$-$”表示两个数据库之间的差，我们很快就会更精确地刻画这一概念。$\Delta DB$ 流可以由 $DB$ 流经流微分算子（stream differentiation operator）$\mathcal{D}$ 产生；该算子把其输入流的变化流作为输出；因此有 $\mathcal{D}(DB) = \Delta DB$。
The ▯DB stream can be produced from the DB stream by the stream differentiation operator D; this operator produces as its output the stream of changes from its input stream; we have thus D(DB) = ▯DB. Conversely, the database snapshot at time t is the cumulative result of applying all transactions up to t: DB[t] = ▯DB[0] + ▯DB[1] + . . . + ▯DB[t].
反过来，时刻 $t$ 的数据库快照是施加截至 $t$ 的全部事务的累积结果：$DB[t] = \Delta DB[0] + \Delta DB[1] + \cdots + \Delta DB[t]$。流算子 $\mathcal{I}$ 定义为把此前所有输入累加起来产生每个输出。我们称 $\mathcal{I}$ 为流积分，它是流微分的逆。下图给出流 $\Delta DB$ 与 $DB$ 之间的关系：
ΔDB ──▶ [ I ] ──▶ DB ──▶ [ D ] ──▶ ΔDB
The stream operator I is defined to produce each output by adding up all previous inputs.
在这个模型中，视图也是一条流。设查询 $Q$ 定义一个视图 $V$。数据库流的每个快照都对应视图的一个快照：$V[t] = Q(DB[t])$。因此，视图只是一个提升后的查询：$V = ({\uparrow}Q)(DB)$。
We call I stream integration, the inverse of differentiation. The following diagram shows the relationship between the streams ▯DB and DB: ▯DB I DB D ▯DB A view in this model is also a stream.
有了这些基本定义，我们就可以精确地定义 IVM。增量地维护一个视图意味着什么？一个维护算法需要在给定数据库变化的情况下，计算视图的变化。给定查询 $Q$，本文的一个关键贡献是利用流积分与流微分定义它的增量版本 $Q^\Delta$，其图形表示如下：
ΔDB ──▶ [ I ] ──▶ [ ↑Q ] ──▶ [ D ] ──▶ ΔV
DB V
Suppose query Q defining a view V . For each snapshot of the database stream we have a snapshot of the view: V [t] = Q(DB[t]). A view is thus just a lifted query: V = ("Q)(DB).
图中 $[I]$ 与 $[D]$ 分别是积分算子 $\mathcal{I}$ 与微分算子 $\mathcal{D}$；导线上标注的 $DB$ 与 $V$ 是中间流；整个电路即 $Q^{\Delta}$。
Armed with these basic definitions, we can precisely define IVM.
用数学写出来：$Q^\Delta = \mathcal{D} \circ ({\uparrow}Q) \circ \mathcal{I}$。查询 $Q$ 的增量版本是一个流式算子 $Q^\Delta$，它直接在变化上计算并产生变化。因此，查询的增量版本总是良定义的。上述定义给出了增量地计算一个查询的一种方式，但朴素地应用它会产生低效的执行（因为它会在每一步重建数据库）。事实上，它和朴素解法一样糟糕。在 §3 中我们说明如何优化 $Q^\Delta$ 的实现。关键性质是：我们可以把 $\cdot^\Delta$ 算子“下推”到查询计划中：$(Q_1 \circ Q_2)^\Delta = Q_1^\Delta \circ Q_2^\Delta$。
What does it mean to maintain a view incrementally? A maintenance algorithm needs to compute the changes to the view given the changes to the database. Given a query Q, a key contribution of this paper is the definition of its incremental version Q▯, using stream integration and differentiation, depicted graphically as:
借助这套一般性的增量计算理论，我们在 §4 中说明如何在 DBSP 中建模关系查询。这立即给出一个计算任意关系查询增量版本的通用算法。这些结果此前已为人所知，但 DBSP 为它们提供了简洁的建模。§5 说明包含递归的程序如何能在 DBSP 中实现并增量化。例如，给定以自然递归方式实现的传递闭包，我们的算法能生成一个程序，在节点与边被添加和删除时高效地维护该图的传递闭包。
1.5 贡献1.5 Contributions
This work makes the following contributions: (1) We introduce DBSP, a simple but expressive language for streaming computation.
DBSP gives an elegant formal foundation unifying the manipulation of streaming and incremental computations.
- 我们引入 DBSP，一种简单而富有表达力的流式计算语言。DBSP 给出了一个优雅的形式基础，统一了对流式计算与增量计算的处理。
(2) An algorithm for incrementalizing any streaming computation expressed in DBSP that handles arbitrary insertions and deletions from any of the data sources.
- 一个算法，用于将 DBSP 中表达的任何流式计算增量化，并且能处理来自任意数据源的任意插入与删除。
(3) An illustration of how DBSP can model various classes of practical queries, such as relational algebra, nested relations, aggregations, and Datalog.
- 说明 DBSP 如何建模各类实用查询，例如关系代数、嵌套关系、聚合，以及 Datalog。
(4) The first general and machine-checked theory of IVM. All the theoretical results in the original version of this paper [5] have been checked [7] using the Lean proof assistant [8].
- 第一个通用的、经过机器检查的 IVM 理论。本文原始版本 [5] 中的所有理论结果，都已使用 Lean 证明助手 [8] 在 [7] 中检查过。
(5) A practical open-source implementation of this theory as a runtime and a SQL compiler.
- 把该理论实现为一个运行时与一个 SQL 编译器，构成一个实用的开源实现。
[^1]: 版权归作者所有。出版权授予 VLDB Endowment。本文是论文《DBSP: Automatic Incremental View Maintenance for Rich Query Languages》的简化版，该文发表于 PVLDB 第 16 卷第 7 期，ISSN 2150-8097 [5]。DOI: https://doi.org/10.14778/3587136.3587137
2 流算子2. STREAM OPERATORS
For the rest of this paper we require the set of values A of a stream SA to form a commutative group, with operations +, ▯, and a 0 (zero) value. The plus defines what it means to add new data, while the minus allows us to compute differences (deltas). We show later that this requirement is not a problem for using DBSP in the context of databases.
在本文余下的部分，我们要求流 $\mathcal{S}_A$ 的取值集合 $A$ 构成一个交换群（阿贝尔群），其运算为 $+$、$-$，以及一个 $0$（零）值。加法定义了“加入新数据”的含义，而减法使我们能够计算差（增量）。我们稍后会说明，这一要求对于在数据库语境中使用 DBSP 并不构成问题。
Stream operators are very powerful mathematically, but in DBSP we restrict ourselves to a very small subset. All DBSP computations are causal [4]: the output at time t is produced immediately after all inputs up at time t have been received; the output at time t cannot depend on inputs arriving after t.
流算子在数学上非常强大，但在 DBSP 中我们把自己限制在一个很小的子集上。所有 DBSP 计算都是因果的（causal）[4]：时刻 $t$ 的输出在时刻 $t$ 的所有输入都被接收之后立即产生；时刻 $t$ 的输出不能依赖于在 $t$ 之后到达的输入。
下面的电路等价告诉我们，可以通过分别提升电路中的每个函数来提升整个电路：
s ──▶ [↑g] ──▶ [↑f] ──▶ o ≅ s ──▶ [↑(f ∘ g)] ──▶ o (**)
The following circuit equivalence tells us that we can lift a circuit by lifting each of its functions separately: s ↑g ↑f o ≅ s "(f ▯ g) o (**) The delay operator z▯1 produces an output stream by delaying its input by one step (and starting with a zero)1: · · · d c b a z▯1 · · · c b a 0 A very important property of the delay operator is that it produces the first output before having received the first input, and it produces the second output before having received the second input, etc. We define the differentiation operator as a composition of several other operators: D(s) def = s ▯ z▯1(s), shown as: s + D(s) z▯1 ▯ If s is a stream, then D(s) is the stream of changes of s; a value in the output is the difference between two consecutive values in the input.
延迟算子 $z^{-1}$ 通过把输入延迟一步来产生输出流（并以 0 起始）[^1]：
· · · d c b a ──▶ [z⁻¹] ──▶ · · · c b a 0
As an example: D( · · · 1 2 1 0 ) = · · · 1 2 1 0 ▯ z▯1( · · · 1 2 1 0 ) = · · · 1 2 1 0 ▯ · · · 2 1 0 0 = · · · -1 1 1 0 The integration operator is given by the following circuit: s + I(s) = o z▯1 While this definition may seem strange, because the output stream is used to compute itself, the use of the delay in the “feedback” loop ensures that only previous values of the output are used in computing the current one.
延迟算子有一个非常重要的性质：它在收到第一个输入之前就产生第一个输出，在收到第二个输入之前就产生第二个输出，依此类推。
Using the notation o = I(s) to make formulas more readable, we can see the contents of stream o is produced step by step: o[0] = s[0] + (z▯1(o))[0] = s[0] + 0 = s[0] o[1] = s[1] + (z▯1(o))[1] = s[1] + o[0] = s[1] + s[0] o[2] = s[2] + (z▯1(o))[2] = s[2] + o[1] = s[2] + (s[1] + s[0]) In general, I(s)[t] = o[t] = P it s[i].
我们把微分算子定义为若干其他算子的复合：$\mathcal{D}(s) \overset{\mathrm{def}}{=} s - z^{-1}(s)$，图示如下：
s ──┬──────────▶ ( + ) ──▶ D(s)
│ ▲
└─▶ [z⁻¹] (−) ─┘
Examples: I( · · · 3 2 1 0 ) = · · · 6 3 1 0 I( · · · -1 1 1 0 ) = · · · 1 2 1 0 .
若 $s$ 是一个流，则 $\mathcal{D}(s)$ 是 $s$ 的变化流；输出中的每个值是输入中两个相邻值之差。例如：
D( · · · 1 2 1 0 ) =
· · · 1 2 1 0 − z⁻¹( · · · 1 2 1 0 ) =
· · · 1 2 1 0 − · · · 2 1 0 0 =
· · · −1 1 1 0
s ──▶ ( + ) ──▶ I(s) = o
▲ │
└──[z⁻¹]◀────────┘
Integration and differentiation are inverses of each other: while D computes the changes of a stream, I reconstitutes the original stream given the stream of changes.
虽然这个定义看起来有些奇怪，因为输出流被用来计算它自己，但“反馈”环中延迟算子的使用保证了：在计算当前值时只用到输出的先前值。为便于阅读公式，我们使用记号 $o = \mathcal{I}(s)$，于是可以看到流 $o$ 的内容是逐步产生的：
$$o[0] = s[0] + (z^{-1}(o))[0] = s[0] + 0 = s[0]$$
$$o[1] = s[1] + (z^{-1}(o))[1] = s[1] + o[0] = s[1] + s[0]$$
$$o[2] = s[2] + (z^{-1}(o))[2] = s[2] + o[1] = s[2] + (s[1] + s[0])$$
一般地，$\mathcal{I}(s)[t] = o[t] = \sum_{i \leq t} s[i]$。例如：
I( · · · 3 2 1 0 ) = · · · 6 3 1 0
I( · · · −1 1 1 0 ) = · · · 1 2 1 0 .
I and D “cancel out” when applied in sequence: s I D o ≅ s o ≅ s D I o
积分与微分互为逆运算：$\mathcal{D}$ 计算一个流的变化，而 $\mathcal{I}$ 在给定变化流的情况下重构出原来的流。把 $\mathcal{I}$ 与 $\mathcal{D}$ 依次施加时，二者会“相互抵消”：
s ──▶ [I] ──▶ [D] ──▶ o ≅ s ──▶ o ≅ s ──▶ [D] ──▶ [I] ──▶ o
3 增量视图维护3. INCREMENTAL VIEW MAINTENANCE
The results in this section are not specific to databases, they hold for any stream computations, but we hint about their applicability for databases.
本节的结果并不专属于数据库：它们对任何流计算都成立，但我们仍会提示它们在数据库中的适用性。
Given a stream operator S : SA → SB we define the incremental version of S as: ▯s I S D ▯o s o S▯ 1This bizarre name comes from digital signal processing.
给定流算子 $S : \mathcal{S}_A \to \mathcal{S}_B$，我们如下定义 $S$ 的增量版本：
Δs ──▶ [I] ──s──▶ [S] ──o──▶ [D] ──▶ Δo
SIGMOD Record, March 2024 (Vol. 53, No. 1) 89 If S computes on a stream s, then S▯ computes on a stream of changes to s. If S produces a stream o, then S▯ produces the stream of changes to o.
图中 $[I]$ 与 $[D]$ 分别是积分算子 $\mathcal{I}$ 与微分算子 $\mathcal{D}$；导线上标注的 $s$ 与 $o$ 是中间流。整个电路即 $S^{\Delta}$。
Note that this definition does not require S to be a lifted function. For an operator with multiple inputs and outputs we define the incremental version by applying I to each input, and D to each output, e.g.: T ▯(a, b) def = D(T (I(a), I(b))).
若 $S$ 在一个流 $s$ 上计算，则 $S^{\Delta}$ 在 $s$ 的变化流上计算。若 $S$ 产生一个流 $o$，则 $S^{\Delta}$ 产生 $o$ 的变化流。注意，这个定义并不要求 $S$ 是提升函数。
S▯ has many nice properties: The chain rule states that (Q1 ▯ Q2)▯ = Q1▯ ▯ Q2▯, i.e., these circuits are equivalent: ▯i I Q1 Q2 D ▯o ≅ ▯i I Q1 D I Q2 D ▯o ≅ ▯i Q1▯ Q2▯ ▯o In the database world, we can read this as: to incrementalize a composite query you can incrementalize each sub-query independently.
对于有多个输入与输出的算子，我们通过对每个输入施加 $\mathcal{I}$、对每个输出施加 $\mathcal{D}$ 来定义增量版本，例如：$T^{\Delta}(a, b) \overset{\mathrm{def}}{=} \mathcal{D}(T(\mathcal{I}(a), \mathcal{I}(b)))$。
This gives us a simple deterministic recipe reducing the incremental version of an arbitrary query to the incremental version of its primitive operators.
链式法则（chain rule）指出 $(Q_1 \circ Q_2)^{\Delta} = Q_1^{\Delta} \circ Q_2^{\Delta}$，即下面这些电路等价：
Δi ──▶ [I] ──▶ [Q₁] ──▶ [Q₂] ──▶ [D] ──▶ Δo
≅
Δi ──▶ [I] ──▶ [Q₁] ──▶ [D] ──▶ [I] ──▶ [Q₂] ──▶ [D] ──▶ Δo
≅
Δi ──▶ [Q₁^Δ] ──▶ [Q₂^Δ] ──▶ Δo
The cycle rule states that these circuits are equivalent: ▯s I T D ▯o z▯1 ≅ ▯s T ▯ ▯o z▯1 (We have omitted the labels on the inputs of T .) In other words, the incremental version of a feedback loop around a query is just the feedback loop with the incremental query for its body.
在数据库领域，这句话可以这样理解：要对一个复合查询做增量化，你可以分别对每个子查询做增量化。这给了我们一个简单的、确定性的配方，把任意查询的增量版本归约为其基本算子的增量版本。
This result will be useful for recursive queries.
循环法则（cycle rule）指出下面这些电路等价：
Δs ──▶ [I] ──▶ [T] ──┬──▶ [D] ──▶ Δo
└──[z⁻¹]──▶（回送到 [T] 的输入）
≅
Δs ──▶ [T^Δ] ──┬──▶ Δo
└──[z⁻¹]──▶（回送到 [T^Δ] 的输入）
We call an operator S linear if it has the property that S(a + b) = S(a) + S(b) (where + is the addition of streams). For a linear operator S we have S▯ = S.
（我们省略了 $T$ 各输入上的标号。）换言之，一个查询周围反馈环的增量版本，就是把环体换成该查询的增量查询之后的同一个反馈环。这个结果对于递归查询会很有用。
This is very useful because many primitive database operations can be implemented as linear operators: selection, projection, filtering, grouping, parts of aggregation are all linear. Moreover, the following operators are linear: ▯, z▯1, I, D, ↑f if f is a linear function. We call an operator T with two inputs bilinear if it distributes over stream addition: T (a + b, c) = T (a, c) + T (b, c), and T (a, c + d) = T (a, c) + T (a, d).
我们称算子 $S$ 是线性的（linear），如果它具有性质 $S(a + b) = S(a) + S(b)$（其中 $+$ 是流的加法）。对线性算子 $S$，有 $S^{\Delta} = S$。这非常有用，因为许多基本的数据库操作都可以实现为线性算子：选择、投影、过滤、分组，以及聚合的一部分，都是线性的。此外，下列算子也是线性的：$+$、$z^{-1}$、$\mathcal{I}$、$\mathcal{D}$，以及 ${\uparrow}f$（若 $f$ 是线性函数）。
(Similar to multiplication’s distributivity over addition.) In databases intersection, joins, and Cartesian products are bilinear. Using infix notation, for a bilinear operator ⇥ we have: (▯a ⇥ ▯b)▯ = (▯a ⇥ ▯b + z▯1(I(▯a)) ⇥ ▯b + ▯a ⇥ z▯1(I(▯b)) = ▯a ⇥ ▯b + z▯1(a) ⇥ ▯b + ▯a ⇥ z▯1(b) If we ignore the delay operators in this equation we recover the well-known formula for join delta queries, e.g.,[15]. ▯a I ▯b I ⇥ D ▯o ≅ ▯a ▯b I ⇥ I z▯1 z▯1 ⇥ ⇥ + ▯o What is the intuition behind this diagram?
我们称有两个输入的算子 $T$ 是双线性的（bilinear），如果它对流的加法满足分配律：$T(a + b, c) = T(a, c) + T(b, c)$，且 $T(a, c + d) = T(a, c) + T(a, d)$。（这类似于乘法对加法的分配律。）在数据库中，交、连接与笛卡尔积都是双线性的。
Let us consider the case of Cartesian product a ⇥ b.
采用中缀记号，对双线性算子 $\times$ 我们有：
$$(\Delta a \times \Delta b)^{\Delta} = \Delta a \times \Delta b + z^{-1}(\mathcal{I}(\Delta a)) \times \Delta b + \Delta a \times z^{-1}(\mathcal{I}(\Delta b)) = \Delta a \times \Delta b + z^{-1}(a) \times \Delta b + \Delta a \times z^{-1}(b)$$
The incremental product has inputs ▯a = D(a) and ▯b = D(b). What happens when we add a row x to relation a (i.e., ▯a = x)?
如果忽略该等式中的延迟算子，我们就得到众所周知的连接增量查询（join delta query）公式，例如见 [15]。
电路 1（定义）：
Δa ──▶ [I] ───┐
├──▶ [×] ──▶ [D] ──▶ Δo
Δb ──▶ [I] ───┘
≅
电路 2（展开）：
第 1 项 Δa ──▶ [×] ◀── Δb ⇒ Δa × Δb
第 2 项 Δa ──▶ [I] ──▶ [z⁻¹] ──▶ [×] ◀── Δb ⇒ z⁻¹(I(Δa)) × Δb
第 3 项 Δb ──▶ [I] ──▶ [z⁻¹] ──▶ [×] ◀── Δa ⇒ Δa × z⁻¹(I(Δb))
三项在 ( + ) 处相加 ──▶ Δo
The new row x will appear in the output change combined with every row in the previous version of the full relation b.
图中 $[\times]$ 表示双线性算子（笛卡尔积或连接），$(+)$ 把三个乘积相加；输入 $\Delta a$ 与 $\Delta b$ 均有多路扇出。
The operator I(▯b) in fact computes relation b from the stream ▯b of changes, and z▯1 applied to this value gives us its previous version. So the bottom ⇥ operator computes x ⇥ z▯1(b) = ▯a ⇥ z▯1(I(▯b)), the change produced by the new row x. The top ⇥ operator performs the symmetric operation for the changes of the b relation. The middle ⇥ operator produces the results of changes to both inputs.
这个图背后的直觉是什么？让我们考虑笛卡尔积 $a \times b$ 的情形。增量乘积的输入是 $\Delta a = \mathcal{D}(a)$ 与 $\Delta b = \mathcal{D}(b)$。当我们向关系 $a$ 加入一行 $x$ 时（即 $\Delta a = x$）会发生什么？新行 $x$ 会与完整关系 $b$ 的先前版本中的每一行组合，出现在输出的变化中。算子 $\mathcal{I}(b)$ 实际上从变化流 $\Delta b$ 计算出关系 $b$，而对它施加 $z^{-1}$ 就得到它的先前版本。因此底部的 $\times$ 算子计算 $x \times z^{-1}(b) = \Delta a \times z^{-1}(\mathcal{I}(b))$，即新行 $x$ 所产生的变化。顶部的 $\times$ 算子对 $b$ 关系的变化执行对称的操作。中间的 $\times$ 算子产生两个输入的变化所共同导致的结果。
4 关系代数的 IVM4. IVM FOR THE RELATIONAL ALGEBRA
In this section we apply the results on incremental computation to relational databases.
本节我们把关于增量计算的结果应用到关系数据库上。正如引言所述，我们的目标是高效地计算任意关系查询 $Q$ 的增量版本。
As explained in the introduction, our goal is to e▯ciently compute the incremental version of any relational query Q. However, we face a technical problem: we said that streams require their values to belong to a commutative group, and relational databases in general are not commutative groups, since they operate on sets. Fortunately, there is a wellknown tool in the database literature which converts set operations into group operations by using Z-sets (also called z-relations [12]) to represent sets.
然而，我们面临一个技术问题：我们说过流要求其取值属于交换群，而关系数据库一般并不是交换群，因为它们操作的是集合。幸运的是，数据库文献中有一个著名的工具，它通过用 ℤ-集合（Z-set，也称为 z-关系 [12]）表示集合，把集合运算转换为群运算。
4.1 ℤ-集合4.1 Z-sets
Z-sets generalize database tables: think of a Z-set as a table where each row has an associated integer weight, possibly negative.
ℤ-集合推广了数据库表：可以把 ℤ-集合想成一张表，其中每一行都关联一个整数权重，该权重可能为负。这个权重表明该行属于该表多少次。
This weight indicates how many times the row belongs to the table. The following table shows an example Z-set with three rows. The first row has value joe and weight 1. We do not show rows with weight 0.
下面的表给出了一个有三行的 ℤ-集合的例子。第一行的值为 joe，权重为 1。我们不显示权重为 0 的行。
| 行 |
权重 |
| joe |
1 |
| mary |
2 |
| anne |
−1 |
Row Weight joe 1 mary 2 anne -1 Z-sets generalize sets and multisets: a set can be represented as a Z-set by associating a weight of 1 with each element. Multisets (also called “bags” in the database literature) are Z-sets where all weights are positive.
ℤ-集合推广了集合与多重集：一个集合可以这样表示为 ℤ-集合——给每个元素关联权重 1。多重集（数据库文献中也称为“包”）是所有权重都为正的 ℤ-集合。关键在于，ℤ-集合还能表示对集合与包的变化。负权重表示正在被删除的行。
Crucially, Z-sets can also represent changes to sets and bags. Negative weights represent rows that are being removed. We can define three operations on Z-sets with values of a given type: (1) zero (a Z-set with all weights 0) (2) negation: just negate all weights; (3) plus: add up the weights of the rows that have the same value.
我们可以对取给定类型的值的 ℤ-集合定义三个运算：(1) 零（所有权重都为 0 的 ℤ-集合）；(2) 取负：把所有权重取负；(3) 加：把具有相同值的行的权重相加。借助这些运算，ℤ-集合构成一个交换群。
Using these operations Z-sets are a commutative group. We define the function distinct on Z-sets. This function’s output is a Z-set where all rows of the input with negative weights are removed, and all positive weights are changed to 1.
我们在 ℤ-集合上定义函数 $\mathit{distinct}$。该函数的输出是一个 ℤ-集合，其中输入中所有权重为负的行都被去掉，而所有正的权重都变为 1。例如，上述 ℤ-集合的 $\mathit{distinct}$ 为：
注意，$\mathit{distinct}$ 从多重集中“去掉”重复项，它同时也消去了权重为负的行。
For example, the distinct of the above Z-set is: Row Weight joe 1 mary 1 Notice that distinct “removes” duplicates from multisets, and it also eliminates rows with negative weights.
[^1]: 这个古怪的名称来自数字信号处理（digital signal processing）。
4.2 关系算子的实现4.2 Implementing relational operators
The fact that relational algebra can be implemented by computations on Z-sets has been shown before, e.g. [13].
关系代数可以用 ℤ-集合（Z-set）上的计算来实现，这一点此前已有工作表明，例如 [13]。关系算子到 ℤ-集合上函数的翻译见表 1。函数（$\pi$、$\sigma$、$\bowtie$、$\times$）即标准关系算子：投影、选择、连接、笛卡尔积。表 1 的第一行表明，复合查询是递归地翻译的：先实现各个子查询，再用箭头把它们连接起来。这就给出了把任意关系查询计划翻译成电路的配方。
The translation of the relational operators to functions computing on Z-sets is shown in Table 1.
表 1：把 SQL 关系集合算子实现为在 ℤ-集合上计算的电路。
| 操作 |
SQL 示例 |
DBSP 电路 |
说明 |
复合
（composition） |
SELECT ... FROM
( SELECT ... FROM I ) |
I ──▶ [C_I] ──▶ [C_O] ──▶ O |
$C_I$ 是内层查询的电路，
$C_O$ 是外层查询的电路。 |
并
（union） |
( SELECT * FROM I1 )
UNION
( SELECT * FROM I2 ) |
I1 ──┐
├──▶ [+] ──▶ [distinct] ──▶ O
I2 ──┘ |
$\mathit{distinct}$ 消除重复。
UNION ALL 的实现不需要 $\mathit{distinct}$。 |
投影
（projection） |
SELECT DISTINCT I.c
FROM I |
I ──▶ [π_c] ──▶ [distinct] ──▶ O |
每一行连同其权重原样投影，
再把相同行的权重相加。 |
过滤
（filtering） |
SELECT * FROM I
WHERE P(...) |
I ──▶ [σ_P] ──▶ O |
$P$ 是作用于每一行的谓词。
逐行单独选择：若该行被选中则保留其权重，
否则令权重为 0。 |
笛卡尔积
（Cartesian product） |
SELECT I1.*, I2.*
FROM I1, I2 |
I1 ──┐
├──▶ [×] ──▶ O
I2 ──┘ |
二元组 $(a,b)$ 的权重是 $a$ 的权重与 $b$ 的权重之积。 |
等值连接
（equi-join） |
SELECT I1.*, I2.*
FROM I1 JOIN I2
ON I1.c1 = I2.c2 |
I1 ──┐
├──▶ [⋈_{c1=c2}] ──▶ O
I2 ──┘ |
把出现在输出中的行的权重相乘。 |
交
（intersection） |
( SELECT * FROM I1 )
INTERSECT
( SELECT * FROM I2 ) |
I1 ──┐
├──▶ [⋈] ──▶ O
I2 ──┘ |
两个关系具有相同模式时等值连接的特例。 |
差
（difference） |
SELECT * FROM I1
EXCEPT
SELECT * FROM I2 |
I1 ──┐
├──▶ [+] ──▶ [distinct] ──▶ O
I2 ──▶ [−] ──┘ |
$\mathit{distinct}$ 把权重为负的行从结果中移除。 |
这一翻译相当直接，但许多算子都需要施加一次 $\mathit{distinct}$ 才能产生集合。例如，$a \cup b = \mathit{distinct}(a + b)$，$a \setminus b = \mathit{distinct}(a - b)$。在 ℤ-集合上做过滤与在集合上做过滤完全一样，只是保留了每个值的权重。在 ℤ-集合上做选择与在集合上做选择类似，但也保留权重。
The functions (⇡, ▯, ./, ⇥) are the standard relational operators projection, selection, join, Cartesian product. The first row of the table
这是用 ℤ-集合对关系代数——现代数据库所依赖的基础数学理论——的一个忠实实现。这种实现会产生大量的 $\mathit{distinct}$ 算子，但已有一些已知的优化可以去掉其中一部分。
表 1 中的以下函数是线性的：$\sigma$、$\pi$、$-$、$+$。以下函数是双线性的：$\times$、$\bowtie$。事实上，唯一的非线性函数是 $\mathit{distinct}$。因此，这些函数（提升后）都有非常高效的增量版本。
为了解释这些函数为什么是线性的，考虑引言中的过滤查询（WHERE）。当我们向输入中加入一行时，输出的变化是什么？只需检查新行的谓词即可。如果谓词返回真，新行就被加入输出。因此输出的变化只依赖于输入的变化，而不依赖于输入的实际内容。这正是该运算线性的原因。
4.3 增量视图维护4.3 Incremental view maintenance
Let us consider a relational query Q defining a view V .
让我们考虑定义视图 $V$ 的关系查询 $Q$。下面的算法为 $Q^{\Delta}$ 构造一个 DBSP 电路：
To the following algorithm builds a DBSP circuit for Q▯: Algorithm 4.1 (incremental view maintenance).
(1) Translate Q into a circuit using the rules in Table 1.
(2) [Optional] Remove some distinct operations.
- [可选] 去掉一些 $\mathit{distinct}$ 运算。
(3) Lift the whole circuit, converting it to a circuit operating on streams, using formula (**) in Section 2.
- 提升整个电路，把它转换为一个作用于流的电路，使用 §2 中的公式 (**)。
(4) Incrementalize the circuit “surrounding” it with I and D.
- 对整个电路做增量化，即用 $\mathcal{I}$ 和 $\mathcal{D}$ 把它“包围”起来。
(5) Apply the chain rule recursively, producing a circuit using only primitive incremental operations. This algorithm is deterministic; the running time is proportional to the number of operators in the query.
- 递归地应用链式法则，产生一个只使用基本增量算子的电路。
Step (2) generates an equivalent circuit, with fewer distinct operators. Step (3) yields a circuit that consumes a stream of complete database snapshots and outputs a stream of view snapshots. Step (4) yields a circuit that consumes a stream of database changes and outputs a stream of view changes; however, the internal operation of the circuit is non-incremental, as it rebuilds the complete database using integrations. Step (5) optimizes the circuit by replacing each primitive operator with its incremental version.
该算法是确定性的；运行时间与查询中算子的数量成正比。第 (2) 步产生一个等价电路，其中的 $\mathit{distinct}$ 算子更少。第 (3) 步得到一个电路，它消费完整数据库快照流并输出视图快照流。第 (4) 步得到一个电路，它消费数据库变化流并输出视图变化流；然而该电路的内部运算是非增量的，因为它使用积分重建完整的数据库。第 (5) 步通过把每个基本算子替换为其增量版本，对电路进行优化。它本质上在电路的每条边上加一对 $\mathcal{I} \to \mathcal{D}$，然后用链式法则把每个 $\mathcal{I} \to Q \to \mathcal{D}$ 替换为 $Q^{\Delta}$。
It essentially adds a I ▯ D pair on every edge in the circuit, and then uses the chain rule to replace each I ▯ Q ▯ D with Q▯. After running this algorithm, all primitives operations are replaced by their incremental versions. The only non-linear operation from Table 1 is distinct.
运行该算法之后，所有基本运算都被替换为其增量版本。表 1 中唯一的非线性运算是 $\mathit{distinct}$。然而，$\mathit{distinct}$ 有一个高效的增量实现（这个构造此前也已为人所知，但我们用流算子的形式给出），如下图所示：
Δd ──▶ [(↑distinct)^Δ] ──▶ Δo
≅
Δd ──┬──▶ [I] ──▶ [z⁻¹] ──┐
│ ├──▶ [↑H] ──▶ Δo
└────────────────────┘
H detects whether the weight of a row in the full set is changing sign (from negative to positive on a row insertion, and from positive to negative on a deletion) when the row appears in a new change. Here is the intuition why distinct is e▯ciently incrementalizable: only tuples that appear in the input change ▯d can appear in the output change ▯o, so the work performed is O(|▯d)|. The implementation needs to maintain the entire input set (similar to joins) in order to discover whether an item is new or not. That is the purpose of the I operator.
函数 $H$ 有两个输入：左侧输入是变化 $\Delta d$，上方输入是由变化积分得到的完整集合。当某一行出现在新的变化中时，$H$ 检测该行在完整集合中的权重是否改变符号（插入行时从负变正，删除行时从正变负）。下面是 $\mathit{distinct}$ 可以被高效增量化的直觉：只有出现在输入变化 $\Delta d$ 中的元组才可能出现在输出变化 $\Delta o$ 中，因此所做的工作量为 $O(|\Delta d|)$。该实现需要维护整个输入集合（与连接类似），以判断某个元素是否是新的。这正是 $\mathcal{I}$ 算子的用途。
The algorithm reduces the problem of incremental execution of a query plan to the incremental execution of subplans/primitive operators. However, this algorithm works even if we use a primitive P for which no e▯cient incremental version is known: we can always use the ine▯cient “brute-force” implementation given by P ▯ = D ▯ ↑P ▯ I.
该算法把查询计划的增量执行问题归约为子计划/基本算子的增量执行。然而，即使我们使用的基本算子 $P$ 没有已知的高效增量版本，这个算法仍然有效：我们总可以使用低效的“暴力”实现 $P^{\Delta} = \mathcal{D} \circ ({\uparrow}P) \circ \mathcal{I}$。
4.4 关系查询示例4.4 Relational Query Example
Let’s apply the IVM algorithm to the following SQL query: CREATE VIEW v AS SELECT DISTINCT a .x , b . y FROM ( SELECT t1 .x , t1 . id FROM t1 WHERE t1 . a > 2 ) a JOIN ( SELECT t2 . id , t2 . y FROM t2 WHERE t2 . s > 5 ) b ON a . id = b . id Step 1: Create a DBSP circuit to represent this query using the rules in Table 1; this circuit is essentially a dataflow implementation of the query: t1 ▯a>2 distinct ⇡x,id distinct t2 ▯s>5 distinct ⇡y,id distinct ./id=id ⇡x,y distinct V Step 2: eliminate distinct operators, producing an equivalent circuit: (we omit the subscripts to save space): t1 ▯ ⇡ t2 ▯ ⇡ ./ ⇡ distinct V This step is used in some traditional database optimizers.
让我们把增量视图维护（incremental view maintenance, IVM）算法应用到这个 SQL 查询上：
CREATE VIEW v AS
SELECT DISTINCT a.x, b.y FROM (
SELECT t1.x, t1.id FROM t1 WHERE t1.a > 2
) a JOIN (
SELECT t2.id, t2.y FROM t2 WHERE t2.s > 5
) b ON a.id = b.id
Note that some arrows that represented sets in the original circuit may represent multisets in the optimized circuit.
第 1 步：使用表 1 中的规则创建一个 DBSP 电路来表示这个查询；该电路本质上是该查询的一个数据流实现：
t1 ──▶ [σ_a>2] ──▶ [distinct] ──▶ [π_x,id] ──▶ [distinct] ──┐
├──▶ [⋈_id=id] ──▶ [π_x,y] ──▶ [distinct] ──▶ V
t2 ──▶ [σ_s>5] ──▶ [distinct] ──▶ [π_y,id] ──▶ [distinct] ──┘
第 2 步：消除 $\mathit{distinct}$ 算子，产生一个等价电路（为节省空间我们省略下标）：
t1 ──▶ [σ] ──▶ [π] ──┐
├──▶ [⋈] ──▶ [π] ──▶ [distinct] ──▶ V
t2 ──▶ [σ] ──▶ [π] ──┘
这一步被一些传统数据库优化器所使用。注意，在原电路中表示集合的一些箭头，在优化后的电路中可能表示多重集。
第 3 步：提升电路使之在流上计算；所有箭头都被加倍，所有函数都被提升：
t1 ──▶ [↑σ] ──▶ [↑π] ──┐
├──▶ [↑⋈] ──▶ [↑π] ──▶ [↑distinct] ──▶ V
t2 ──▶ [↑σ] ──▶ [↑π] ──┘
Step 3: lift the circuit to compute over streams; all arrows are doubled and all functions are lifted: t1 "▯ "⇡ t2 "▯ "⇡ " ./ "⇡ ↑distinct 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: ▯t1 I "▯ "⇡ ▯t2 I "▯ "⇡ " ./ "⇡ ↑distinct D ▯V Step 5: apply the chain rule to rewrite the circuit as a composition of incremental operators; notice the use of .▯ for all operators: ▯t1 ("▯)▯ ("⇡)▯ ▯t2 ("▯)▯ ("⇡)▯ (" ./)▯ ("⇡)▯ ("distinct)▯ ▯V Use the linearity of ▯ and ⇡ to simplify this circuit (notice that all linear operators no longer have a ·▯): ▯t1 "▯ "⇡ ▯t2 "▯ "⇡ (" ./)▯ "⇡ ("distinct)▯ ▯V Finally, replace the incremental join and the incremental distinct, with their incremental implementations, obtaining the following circuit (we have used a slightly different expansion for the join than the one shown previously; this one only contains two integrators): ▯t1 "▯ "⇡ ▯t2 "▯ "⇡ I I z▯1 " ./ " ./ + "⇡ I z▯1 "H ▯V Notice that the resulting circuit contains three integration operations: two from the join, and one from the distinct.
第 4 步：对电路做增量化，得到一个在变化上计算的电路；该电路接收对关系 t1 和 t2 的变化，并对每个这样的变化产生输出视图 V 中相应的变化：
Δt1 ──▶ [I] ──▶ [↑σ] ──▶ [↑π] ──┐
├──▶ [↑⋈] ──▶ [↑π] ──▶ [↑distinct] ──▶ [D] ──▶ ΔV
Δt2 ──▶ [I] ──▶ [↑σ] ──▶ [↑π] ──┘
It also contains two join operators.
第 5 步：应用链式法则，把电路重写为增量算子的复合；注意所有算子都使用了 ${\cdot}^{\Delta}$ 记号：
Δt1 ──▶ [(↑σ)^Δ] ──▶ [(↑π)^Δ] ──┐
├──▶ [(↑⋈)^Δ] ──▶ [(↑π)^Δ] ──▶ [(↑distinct)^Δ] ──▶ ΔV
Δt2 ──▶ [(↑σ)^Δ] ──▶ [(↑π)^Δ] ──┘
However, the work performed by each operator for each new input is proportional to the size of its input change.
利用 $\sigma$ 和 $\pi$ 的线性来化简该电路（注意所有线性算子不再带有 ${\cdot}^{\Delta}$）：
Δt1 ──▶ [↑σ] ──▶ [↑π] ──┐
├──▶ [(↑⋈)^Δ] ──▶ [↑π] ──▶ [(↑distinct)^Δ] ──▶ ΔV
Δt2 ──▶ [↑σ] ──▶ [↑π] ──┘
最后，用它们的增量实现替换增量连接与增量 $\mathit{distinct}$，得到以下电路（对连接我们采用了与前面稍有不同的展开方式；这种展开只包含两个积分器）：
Δt1 ──▶ [↑σ] ──▶ [↑π] ──┬──────────────▶ Δa
└──▶ [I] ──▶ a
Δt2 ──▶ [↑σ] ──▶ [↑π] ──┬──────────────▶ Δb
└──▶ [I] ──▶ [z⁻¹] ──▶ b⁻¹
[↑⋈]₁: a ⋈ Δb ──┐
[↑⋈]₂: Δa ⋈ b⁻¹ ──┘
├──▶ [+] ──▶ [↑π] ──┬──▶ [I] ──▶ [z⁻¹] ──▶ i ──┐
└───── d ──────────────────┴──▶ [↑H] ──▶ ΔV
其中 $a = \mathcal{I}(\Delta a)$ 与 $b = \mathcal{I}(\Delta b)$ 是两个子查询输出的当前值，$b^{-1} = z^{-1}(\mathcal{I}(\Delta b))$ 是 $b$ 延迟一步的旧值；两个连接实例之和即双线性算子的增量展开，$z^{-1}$ 是延迟算子，${\uparrow}H$ 是 $\mathit{distinct}$ 增量电路中的符号变化检测函数。
注意，所得电路包含三个积分运算：两个来自连接，一个来自 $\mathit{distinct}$。它还包含两个连接算子。然而，每个算子对每个新输入所做的工作量与其输入变化的大小成正比。
4.5 SQL4.5 SQL
SQL is richer than the relational algebra. It can perform operations on multisets, and it offers operations such as GROUP BY and aggregations. All of these can be modeled as operations on Z-set-like structures. Moreover, GROUP BY is a linear operation.
SQL 比关系代数更丰富。它可以对多重集执行运算，并提供 GROUP BY 和聚合等运算。所有这些都可以建模为对类 ℤ-集合结构的运算。此外，GROUP BY 是一个线性运算。有些聚合“几乎”是线性的，但另一些聚合（例如 MIN）需要维护完整的输入集合（类似于 $\mathit{distinct}$），才能正确处理删除。更多细节见完整论文与技术报告 [6]。
5 递归查询5. RECURSIVE QUERIES
Recursive queries are very useful in many applications. For example, graph algorithms such as graph reachability or transitive closure are naturally expressed using recursive queries. We introduce two simple DBSP stream operators that are used for expressing recursive query evaluation.
递归查询在许多应用中非常有用。例如，图可达性或传递闭包这类图算法，天然就可以用递归查询来表达。我们引入两个简单的 DBSP 流算子，用于表达递归查询的求值。这些算子使我们能够构造实现循环结构的电路，而循环结构用于反复迭代计算，直到到达一个不动点（即某个算子的输出不再发生变化）。
5.1 创建与销毁流5.1 Creating and destroying streams
The delta function ▯ : A → SA produces a stream from a scalar value. Given an input value x, the output stream is x followed by an infinite number of zeros.
delta 函数 $\delta_0 : A \to \mathcal{S}_A$ 由一个标量值产生一个流。给定一个输入值 $x$，输出流是 $x$ 后面跟着无穷多个 0。$\delta_0$ 的输入是单箭头，而输出是双箭头。
x ──▶ [δ₀] ══▶ · · · 0 0 0 x
我们定义函数 $\int : \mathcal{S}_A \to A$。它要求输入流最终到达值 0，并且此后不再变化。该函数只是把输入流中的所有值求和，并在遇到输入流中第一个 0 时返回一个单一结果。注意输入是双箭头，而输出是单箭头。例如：
· · · 0 3 2 1 ══▶ [∫] ──▶ 6
The input of ▯ has a single arrow, while the output has a double arrow. x ▯ · · · 0 0 0 x We define the function R : SA → A.
（该函数也是一个积分器；它与 $\mathcal{I}$ 算子的关系，等同于数学中定积分 [1] 与不定积分 [2] 之间的关系。）
Its input stream is required to eventually reach the value 0 and never change afterwards.
$\delta_0$ 与 $\int$ 都是线性的。
This function just sums up all the values in the input stream and returns a single result when it encounters the first 0 in the input stream.
到目前为止，我们默认程序中的所有流共享同一个“时间”。例如，当我们把两个流相加时，我们假设它们使用同一个“时钟”。然而，$\delta_0$ 算子会创建一个带有“新的”、独立时间维的流。我们要求良构电路把嵌套时间域“隔离”开，办法是用 $\delta_0$ 与 $\int$ 算子把它们“括”起来：
i ──▶ [δ₀] ══▶ [S] ══▶ [∫] ──▶ o
Notice that the input is a double arrow, while the output is a single arrow. E.g.,:
$S$ 是一个流式算子，但整个电路实现的是一个标量函数，正如单箭头所示。
5.2 递归查询的实现5.2 Implementing recursive queries
We describe the implementation of recursive queries in DBSP. SQL can only express very limited recursive queries, so here we model Datalog queries. In general, a Datalog program defines a set of mutually recursive relations.
我们描述 DBSP 中递归查询的实现。SQL 只能表达非常有限的递归查询，因此我们在这里以 Datalog 查询为模型。一般而言，一个 Datalog 程序定义一组相互递归的关系。
We describe the algorithm to build DBSP circuits for the simple case of a single-input, single-output recursive query. The input of our algorithm is a Datalog query of the form O = R(x, O), where R is a relational, non-recursive query, producing a set as a result, but whose output O is also an input. The output of the algorithm is a DBSP circuit which evaluates this recursive query producing output O when given the input x. In this section we build a nonincremental circuit, which evaluates the Datalog query; in Section 5.3 we derive the incremental version of this circuit.
我们针对单输入、单输出递归查询这一简单情形，描述构造 DBSP 电路的算法。算法的输入是形如 $O = R(x, O)$ 的 Datalog 查询，其中 $R$ 是一个关系型、非递归的查询，它产生一个集合作为结果，但它的输出 $O$ 同时也是一个输入。算法的输出是一个 DBSP 电路，该电路在给定输入 $x$ 时求值这个递归查询并产生输出 $O$。本节我们构造的是非增量电路，它求值该 Datalog 查询；在 5.3 节中我们推导该电路的增量版本。
Algorithm 5.1 (recursive queries).
(1) Implement the non-recursive relational query R as described in Section 4 and Table 1; this produces an acyclic circuit whose inputs and outputs are Z-sets: x O R O In all these diagrams we show input 0 of operator R on the left, and input 1 on the bottom. (2) Lift this circuit to operate on streams: x O "R O Construct ↑R by lifting each operator individually, using equation (**) in Section 2.
- 按第 4 节与表 1 所述，把非递归的关系查询 $R$ 实现出来；这会产生一个无环电路，其输入与输出都是 ℤ-集合：
x ──┐
├──▶ [ R ] ──▶ O
O ──┘
(3) Build a cycle, connecting the output to the corresponding recursive input via a delay: x ↑R O z▯1 (4) “Bracket” the circuit as follows: x ▯ I ↑R D R O z▯1 The left input of ↑R is an infinite stream of identical values · · · x x x x .
在所有这些图中，我们把算子 $R$ 的输入 0 画在左侧，把输入 1 画在底部。
The feedback cycle in this circuit is a while loop that iterates until no changes are observed (i.e., a fixed-point of R is reached); the outputs produced by ↑R will be: in sequence R(x, 0), R(x, R(x, 0)), R(x, R(x, R(x, 0))), etc..
x ──┐
├──▶ [ ↑R ] ──▶ O
O ──┘
The D operator yields the set of new changes computed by each iteration of the loop.
我们利用第 2 节中的式 (**) 逐个提升每个算子来构造 $\uparrow R$。
When the set of new changes becomes zero, the fixed point has been reached.
- 构造一个环，通过一个延迟把输出连接到相应的递归输入：
x ──────────▶ [ ↑R ] ──┬──▶ O
└──[z⁻¹]──▶（回送到 [↑R] 的输入 1）
Please note that this is not a streaming circuit: the input and output arrows are both simple.
x ──▶ [δ₀] ──▶ [I] ──▶ [↑R] ──┬──▶ [D] ──▶ [∫] ──▶ O
└──[z⁻¹]──▶（回送到 [↑R] 的输入 1）
This is a circuit which receives a single input value and produces a single corresponding output.
图中 [I] 与 [D] 两个方框分别是积分算子 $\mathcal{I}$ 与微分算子 $\mathcal{D}$。
$\uparrow R$ 的左侧输入是一个由相同值构成的无限流 $\cdots x\ x\ x\ x$。该电路中的反馈环是一个 while 循环，它反复迭代直到观察不到任何变化（即到达 $R$ 的一个不动点）；$\uparrow R$ 产生的输出依次将是：$R(x, 0)$、$R(x, R(x, 0))$、$R(x, R(x, R(x, 0)))$，等等。$\mathcal{D}$ 算子给出循环每一轮迭代所计算出的新变化集合。当新变化的集合变为零时，不动点就已经到达。
The circuit uses streams internally to implement the fixed point iteration.
请注意，这不是一个流式电路：输入与输出箭头都是单箭头。这是一个接收单个输入值并产生单个对应输出的电路。该电路在内部使用流来实现不动点迭代。
A concrete example for a transitive closure query is Section 8.2 of our technical report [6].
关于传递闭包查询的一个具体例子见我们技术报告 [6] 的第 8.2 节。
When R, the body of the loop, implements a Datalog programs computing on a finite data domain, this program can be proven to always terminate and compute the least fixed point that contains x.
当 $R$（即循环体）实现的是一个在有限数据域上计算的 Datalog 程序时，可以证明该程序总是终止，并计算出包含 $x$ 的最小不动点。对于一个任意的函数 $R$，所得到的电路对某些输入可能会永远循环。
For an arbirary function R, the resulting circuit may loop forever for some inputs. In fact, this circuit implements the standard Datalog na¨ıve evaluation algorithm (e.g., see Algorithm 1 in [11]). Notice that the inner part of the circuit is the incremental form of another circuit, since it is sandwiched between I and D operators.
事实上，该电路实现了标准的 Datalog 朴素求值算法（例如见 [11] 中的算法 1）。注意该电路的内层部分是另一个电路的增量形式，因为它被夹在 $\mathcal{I}$ 与 $\mathcal{D}$ 算子之间。利用循环规则，我们可以把该电路重写为：
x ──▶ [δ₀] ──▶ [(↑R)^Δ] ──┬──▶ [∫] ──▶ O
└──[z⁻¹]──▶（回送到 [(↑R)^Δ] 的输入 1）
Using the cycle rule we can rewrite this circuit: x ▯ ("R)▯ R O z▯1 This circuit implements semi-na¨ıve evaluation (Algorithm 2 in [11]). We have just proven the correctness of semi-na¨ıve evaluation as an immediate consequence of the cycle rule!
该电路实现了半朴素求值（[11] 中的算法 2）。我们刚刚证明了半朴素求值的正确性，它正是循环规则的一个直接推论！
5.3 增量递归程序5.3 Incremental recursive programs
In Section 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 ·▯ operator. In Section 5 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.
在第 2–4 节中，我们展示了如何通过把一个关系查询编译成电路、把该电路提升为在流上计算，再施加 $(\cdot)^\Delta$ 算子，来对它做增量化。在第 5 节中，我们展示了如何把一个递归查询编译成一个电路，该电路在内部使用增量计算来计算不动点。这里我们把这两个结果结合起来，构造一个增量地求值递归查询的电路。该电路接收输入关系上的更新流，并对每一次更新重新计算不动点。为了增量地做到这一点，它保留迭代式不动点计算所产生的、递归关系的变化流，并根据被修改的输入调整这个流。于是，借助嵌套流，输入流的每一个元素都产生一个对不动点计算的调整流。
Thus, every element of the input stream yields a stream of adjustments to the fixed point computation, using nested streams.
正如流是无限向量，流之流是无限矩阵。在图中我们用三箭头表示流之流。
In the same way streams are infinite vectors, streams of streams are infinite matrices. We denote streams of streams with triple arrows in our diagrams. The same way we lift functions to produce stream operators, we can lift stream operators to produce operators on streams of streams.
正如我们把函数提升为流算子，我们也可以把流算子提升为流之流上的算子。一个标量函数 $f$ 可以提升两次，产生一个流之流之间的算子 $\uparrow\uparrow f : \mathcal{S}_{\mathcal{S}_A} \to \mathcal{S}_{\mathcal{S}_B}$：
i ═══▶ [ ↑↑f ] ═══▶ o
A scalar function f can be lifted twice to produce an operator between streams of streams: i ""f o The operator z▯1 on nested streams delays “rows” of the matrix, while ↑z▯1 delays “columns”.
嵌套流上的算子 $z^{-1}$ 延迟矩阵的“行”，而 $\uparrow z^{-1}$ 延迟“列”。
We have seen in equation (**) that lifting a graph entails lifting all operators.
我们在式 (**) 中已经看到，提升一个图意味着提升其中所有算子。这一点可以推广到带环的图，例如：
i ═══▶ [ ↑I ] ═══▶ o
i ═══▶ ( + ) ═══┬══▶ o
└──[↑z⁻¹]──▶（回到 ( + ) 的另一个输入）
This extends to graphs with cycles, e.g: SIGMOD Record, March 2024 (Vol. 53, No. 1) 93 i ↑I o ≅ i + o "z▯1 This gives us the ability to lift entire circuits, including circuits computing on streams and having feedback edges.
左图是用 $\uparrow\mathcal{I}$ 表示的电路，右图是它的等价展开：用一个加法器和一条经过 $\uparrow z^{-1}$ 的反馈边实现同一个累加器。
With this machinery we can now apply Algorithm 4.1 to arbitrary circuits, even circuits for recursive relations.
这使我们能够提升整个电路，包括在流上计算并且带反馈边的电路。有了这套机制，我们现在可以把算法 4.1 应用于任意电路，甚至是为递归关系而构造的电路。
x ──▶ [δ₀] ──▶ [(↑R)^Δ] ──┬──▶ [∫] ──▶ O
└──[z⁻¹]──▶（回送到 [(↑R)^Δ] 的输入 1）
Step 1: Start with the “semi-naive” circuit: x ▯0 ("R)▯ R O z▯1 Step 2: nothing to do for distinct.
步骤 2：就 distinct 而言无需做任何事。
Δx ──▶ [I] ──▶ [↑δ₀] ──▶ [↑((↑R)^Δ)] ──┬──▶ [↑∫] ──▶ [D] ──▶ ΔO
└──[↑z⁻¹]──▶（回送到 [↑((↑R)^Δ)] 的输入 1）
Steps 3 and 4: Lift the circuit and incrementalize: ▯x I "▯0 "("R)▯ " R D ▯O "z▯1 Step 5: apply the chain rule and the linearity of "▯0 and " R : ▯x "▯0 ("("R)▯)▯ " R ▯O "z▯1 This is the incremental version of a recursive query.
步骤 5：应用链式法则以及 $\uparrow\delta_0$ 与 $\uparrow\int$ 的线性性：
Δx ──▶ [↑δ₀] ──▶ [(↑((↑R)^Δ))^Δ] ──┬──▶ [↑∫] ──▶ ΔO
└──[↑z⁻¹]──▶（回送到 [(↑((↑R)^Δ))^Δ] 的输入 1）
A concrete example for a transitive closure query is Section 9.1 of our technical report [6].
这就是递归查询的增量版本。关于传递闭包查询的一个具体例子见我们技术报告 [6] 的第 9.1 节。
6 实现6. IMPLEMENTATION
DBSP does not make any simplifying assumptions that would make it impractical. In fact, Feldera Inc. has built an open-source implementation of DBSP as a query engine in Rust [9]; and also a compiler from SQL to DBSP [10]. This compiler handles essentially the entire SQL language. The compiler generates execution plans for incrementally maintaining any number of views defined in SQL.
DBSP 不做任何会使其不实用的简化假设。事实上，Feldera 公司（Feldera Inc.）已用 Rust 构建了 DBSP 的一个开源实现，作为查询引擎 [9]；此外还构建了一个从 SQL 到 DBSP 的编译器 [10]。该编译器基本上处理整个 SQL 语言。该编译器生成执行计划，用于增量地维护任意数量的、用 SQL 定义的视图。
The input of Algorithm 4.1 is a non-incremental query plan, produced by a query planner. The algorithm produces an incremental plan that is “similar” to the input plan. Standard query planners use cost-based heuristics and data statistics to optimize plans. A generic IVM planner does not have this luxury, since the plan must be generated before any data has been fed to the query.
计划质量。 一个关系代数查询可以由多个计划实现，每个计划具有不同的、依赖于数据的代价。算法 4.1 的输入是一个非增量查询计划，由查询规划器生成。该算法产生一个与输入计划“相似”的增量计划。标准查询规划器使用基于代价的启发式方法和数据统计信息来优化计划。通用的 IVM 规划器没有这种便利，因为计划必须在任何数据被馈送到查询之前生成。尽管如此，所有标准的查询优化技术——也许基于历史统计信息——都可以用来生成提供给我们的算法的查询计划。在 IVM 计划的语境下，最优性问题比即席（ad-hoc）查询的优化困难得多，因为选定的 IVM 计划将针对未来所有的数据库更新持续执行。
In the cost analysis we have to consider both the time and the space used by each operator. While many incremental database operations can be implemented using work proportional to the size of the changes, and no storage overhead, several classes of database operations, such as joins, “distinct”, and aggregates can be implemented e▯ciently only using additional storage in the form of indexes. The size of these indexes is proportional to the size of the total data in the database (and not just to the size of the changes) — and since some indexes are over intermediate relations, they can even exceed the size of the original database. In DBSP the indexes are represented by delay operators z▯1.
权衡。 增量计算并非没有代价。它实际上是时间与空间之间的权衡。在代价分析中，我们必须同时考虑每个算子所用的时间和空间。虽然许多增量数据库操作可以用与变化大小成正比的工作量、且没有存储开销来实现，但有几类数据库操作——例如连接、“去重”与聚合——只有借助以索引形式存在的额外存储才能高效实现。这些索引的大小与数据库中全部数据的大小成正比（而不只是与变化的大小成正比）——并且由于有些索引是建立在中间关系之上的，它们甚至可能超过原始数据库的大小。在 DBSP 中，索引由延迟算子 $z^{-1}$ 表示。事实上，延迟算子（及其提升变体 ${\uparrow}z^{-1}$）是唯一维护状态的算子。这也是为使 DBSP 计算具备容错性而需要持久化、建立检查点或迁移的唯一状态。
This is also the only state that needs to be persisted, checkpointed, or migrated to make DBSP computations fault-tolerant. DBSP is an “eager” or “top-down” execution model: it constantly maintains the entire contents of any number of views, even if no one really wants to inspect the views. In contrast, “lazy” or “bottom-up” models only build part of the views when the views are inspected. Such models have the potential to be more e▯cient.
DBSP 是一种“急切”（eager）或“自顶向下”（top-down）的执行模型：它持续维护任意数量视图的全部内容，即使并没有人真的想查看这些视图。相比之下，“惰性”（lazy）或“自底向上”（bottom-up）模型只在视图被查看时才构建视图的一部分。这类模型有可能更为高效。如果对将要针对视图执行的操作类别有所了解，就可以把急切模型转换为惰性模型。
Start-up costs. When a new view is installed, the IVM system must compute the first change, which is the same as the initial contents of the view. This computation is in proportional to the size of the whole database.
启动成本。 当安装一个新视图时，IVM 系统必须计算第一个变化，它等同于该视图的初始内容。这一计算与整个数据库的大小成正比。这被称为“回填”（backfill）问题。同样，对视图定义或数据模式的更改需要从头重新计算受影响的查询。
This is known as the “backfill” problem. Likewise, changes to the definition of a view or the data schema require recomputing the affected queries from scratch. Adopting DBSP. Traditional databases do not offer e▯cient IVM implementations for arbitrary queries.
采用 DBSP。 传统数据库并不为任意查询提供高效的 IVM 实现。原则上可以对数据库进行改造以使用本文的算法，但现有查询引擎并不是围绕能够表示负向变化（如 ℤ-集合）的结构构建的，因此这一工作将需要一次重大的重新设计。
Then, for any transaction committed, each user receives a notification containing the list of changes for the all the views they registered. Databases today do not have convenient mechanism for reporting changes to the outside world. In fact, entire industries have sprung up around the concept of Change Data Capture [3], which is building adhoc solutions for extracting changes from databases, usually by inspecting the write-ahead transaction log.
此外，我们认为数据库不仅应当增量地计算视图，还应当把“变化”作为与其环境通信的基本数据结构：数据库服务应当提供如下 API：用户注册以接收一个或多个视图变化的通知。然后，对于每个已提交的事务，每个用户都会收到一条通知，其中包含他们所注册的所有视图的变化列表。当今的数据库没有向外报告变化的便利机制。事实上，围绕变更数据捕获（Change Data Capture）[3] 的概念已经发展出成规模的产业，它们构建从数据库中提取变化的专用方案，通常是通过检查预写事务日志。
7 结论7. CONCLUSIONS
We have introduced DBSP, a model of computation based on infinite streams over commutative groups. In this model streams are used for 3 purposes: (1) to model consecutive snapshots of a database, (2) to model consecutive changes (deltas, or transactions) applied to a database and changes of a maintained view, (3) to model consecutive values of loop-carried variables in recursive computations.
我们提出了 DBSP，一种基于交换群（commutative groups）上无限流的计算模型。在该模型中，流用于 3 个目的：(1) 为数据库的连续快照建模；(2) 为施加到数据库上的连续变化（增量或事务）以及被维护视图的变化建模；(3) 为递归计算中循环携带变量的连续取值建模。
We have defined an abstract notion of incremental computation over streams, and defined the incrementalization operator ·▯, which transforms an arbitrary stream computation Q into its incremental version Q▯.
我们定义了流上增量计算的抽象概念，并定义了增量化算子 ${\cdot}^{\Delta}$，它把任意流计算 $Q$ 变换为其增量版本 $Q^{\Delta}$。增量化算子具有一些非常好的代数性质，这些性质为我们提供了一个通用算法，可对许多类复杂查询（包括任意递归查询）进行增量化。
The incrementalization operator has some very nice algebraic properties, which gave us a general algorithm for incrementalizing many classes of complex queries, including arbitrary recursive queries. We believe that DBSP can form a solid foundation for a theory and practice of streaming incremental computation.
我们相信，DBSP 能够为流式增量计算的理论与实践奠定坚实的基础。