# DBSP：面向丰富查询语言的自动增量视图维护 **DBSP: Automatic Incremental View Maintenance for Rich Query Languages** Mihai Budiu, Tej Chajed, Frank McSherry, Leonid Ryzhyk, Val Tannen *Proceedings of the VLDB Endowment (PVLDB), 16(7): 1601–1614, 2023*（VLDB 2023 最佳论文 / Best Paper Award） 原文 DOI： 原文 PDF： 参考实现： --- ## 译者说明 - 本文是上述论文正文（§1–§10）的中文全译，按原文段落逐段对应翻译，章节编号与原文一致；参考文献列表未翻译。 - 版权归原作者所有。原文以 CC BY-NC-ND 4.0 许可发布，本译文仅供学习研究使用，不得用于商业用途。 - 原文中的方框-箭头电路图**直接从 PDF 中裁剪导出**，按原文位置嵌入正文（600 dpi，见 `figures/vldb/`）；无损缩放的矢量版见 `figures/DBSP-VLDB2023-矢量电路图.pdf`，全部图的对照页见 `DBSP-VLDB2023-图版.html`。只有 4 处无法与 PDF 图形一一对应（其中 3 处是 PDF 把两个面板合成了一张图），保留了文字示意图并注明。 - 表格重画为 Markdown 表格。 - 公式使用 LaTeX 记号。配套的 `.html` 文件可直接用浏览器打开，公式自动渲染（首次打开需联网加载 MathJax）。 - 定义、定理、引理、命题、例、算法的编号沿用原文；文献引用编号 `[n]` 与原文一致。 - 专业术语首次出现附英文原文，全篇统一（术语表见 `TRANSLATION-BRIEF.md`）。 ### 原文疑似笔误的保留情况（译者注） 以下几处我们判断为原文笔误或排印问题，为保持与原文一致**按原样翻译、未擅自改动**，特此标注以便读者核对： 1. §2 定义 2.13（双线性）第二式原文作 $f(a, c+d) = f(a,c) + f(c,d)$，按双线性定义应为 $f(a,d)$。 2. §2 定义 2.17（积分）原文写作 $\mathcal{I}(s) \overset{\mathrm{def}}{=} \lambda s.\,\mathrm{fix}\ \alpha.\,(s + z^{-1}(\alpha))$，等号右侧多写了一个 $\lambda s$（积分本身已是 $s$ 的函数）。 3. §9 相关工作中 DBToaster 一句原文出现重复词 “recursive recursive IVM”，按语义译为“递归式 IVM”。 4. §5.1 算法 5.3 的电路示意图未画出 ${\uparrow}\mathit{distinct}$，与正文 “Step 2: nothing to do (for distinct)” 的说明一致，故照原文处理。 5. §7.4 flatmap 的聚合函数写作 $a(k,s)=\sum_{x\in s[k]} s[k][x]\cdot(k,x)$；按本节 $Agg_a(g)=\sum_k a(k, g[k])$ 的约定，$a$ 的第二个参数已经是分组本身，应为 $\sum_{x \in s} s[x]\cdot(k,x)$。原文如此，照录。 --- ## 目录 - [摘要](#摘要) - [PVLDB 引用格式](#pvldb-引用格式) - [PVLDB 制品可用性](#pvldb-制品可用性) - [1 引言](#1-引言) - [2 流计算](#2-流计算) - [2.1 流与流算子](#2-1-流与流算子) - [2.2 阿贝尔群上的流](#2-2-阿贝尔群上的流) - [2.3 积分与微分](#2-3-积分与微分) - [3 增量视图维护](#3-增量视图维护) - [4 关系代数的 IVM](#4-关系代数的-ivm) - [4.1 ℤ-集合作为阿贝尔群](#4-1-ℤ-集合作为阿贝尔群) - [4.2 实现关系算子](#4-2-实现关系算子) - [4.3 增量视图维护](#4-3-增量视图维护) - [4.4 增量电路的复杂度](#4-4-增量电路的复杂度) - [4.5 关系查询示例](#4-5-关系查询示例) - [5 递归查询](#5-递归查询) - [5.1 递归查询的实现](#5-1-递归查询的实现) - [6 增量递归程序](#6-增量递归程序) - [6.1 增量递归查询的代价](#6-1-增量递归查询的代价) - [8 实现](#8-实现) - [9 相关工作](#9-相关工作) - [10 结论](#10-结论) --- **DBSP：面向富查询语言的自动增量视图维护**（DBSP: Automatic Incremental View Maintenance for Rich Query Languages） - Mihai Budiu，VMware Research，mbudiu@vmware.com - Tej Chajed，VMware Research，tchajed@vmware.com - Frank McSherry，Materialize Inc.，mcsherry@materialize.com - Leonid Ryzhyk，VMware Research，lryzhyk@vmware.com - Val Tannen，University of Pennsylvania，val@seas.upenn.edu ## 摘要 增量视图维护（incremental view maintenance, IVM）长期以来一直是数据库理论中的一个核心问题。针对受限的数据库语言类，例如关系代数或 Datalog，人们已经提出了许多解决方案。这些技术不能自然地推广到更丰富的语言。本文分 3 步给出该问题的一个通用的、不依赖启发式的解决方案：(1) 我们描述一种称为 DBSP 的简单而富有表达力的语言，用于描述数据流上的计算；(2) 我们给出 IVM 的一个新的数学定义，以及一个求解任意 DBSP 程序的 IVM 的通用算法；(3) 我们说明如何用 DBSP 为许多丰富的数据库查询语言建模（包括完整的关系代数、集合与多重集上的查询、任意嵌套的关系、聚合、展平映射（flatmap，即 unnest）、单调与非单调递归、流式聚合，以及上述这些的任意组合）。SQL 与 Datalog 都可以在 DBSP 中实现。因此，我们得到了针对用所有这些语言编写的查询的高效增量视图维护算法。 ## PVLDB 引用格式 Mihai Budiu, Tej Chajed, Frank McSherry, Leonid Ryzhyk, and Val Tannen. DBSP: Automatic Incremental View Maintenance for Rich Query Languages. PVLDB, 16(7): 1601-1614, 2023. doi:10.14778/3587136.3587137 ## PVLDB 制品可用性 源代码、数据和/或其它制品已在 https://github.com/vmware/database-stream-processor 提供。 > 版权声明：本作品依据 Creative Commons BY-NC-ND 4.0 国际许可协议授权。访问 https://creativecommons.org/licenses/by-nc-nd/4.0/ 可查看该许可协议的副本。超出该许可协议范围的任何使用，需发邮件至 info@vldb.org 获得许可。版权由作者所有。出版权授予 VLDB Endowment。 > > Proceedings of the VLDB Endowment, Vol. 16, No. 7 ISSN 2150-8097. > doi:10.14778/3587136.3587137 ## 1 引言 增量视图维护（incremental view maintenance, IVM）是数据库中一个重要且已被深入研究的问题 [25]。IVM 问题可以表述如下：给定数据库 $DB$ 和一个由查询 $Q$ 描述的视图 $V$，其中 $Q$ 是数据库的函数，即 $V = Q(DB)$，要求在数据库发生变化时维护 $V$ 的内容，并且最好比直接从头重新求值 $Q(DB)$ 更高效。我们希望有一个算法能在施加于数据库的变化 $\Delta DB$ 上求值 $Q$，因为变化通常很小，即 $|\Delta DB| \ll |DB|$。 本文提出一种新的视角：基于流式计算模型给出 IVM 的一个新定义。我们的模型受数字信号处理（Digital Signal Processing, DSP）[44] 的启发并应用于数据库，DBSP 由此得名。以往的 IVM 方案都建立在“定义 $Q$ 关于其输入的（偏）导数”这一概念之上，而我们的定义只要求计算流作为时间函数的导数。只要所计算的数据具有满足若干简单数学性质的“差”的概念——具体来说，构成一个阿贝尔群——流的导数就总是良定义的。（幸运的是，关系数据库可以用这种方式建模 [23, 33]。） DBSP 具有若干吸引人的性质： 1. **表达力强。**（a）它可以精确地定义多个概念：传统查询、流式计算与增量计算。（b）我们已能在 DBSP 中表达完整的关系代数、集合与多重集上的计算、嵌套关系、聚合、展平映射（flatmap，即 unnest）、单调与非单调递归、分层否定、while 关系程序、窗口查询、流式查询、流式聚合，以及上述所有计算的增量版本。事实上，我们已经构建了完整的 SQL 语言的 DBSP 实现（§8）。 2. **简单。**DBSP 只有 4 个算子，并且完全建立在函数与代数群等初等概念之上。 3. **数学上精确。**本文所有结果都已使用 Lean 证明助手 [18] 形式化并检查过。 4. **模块化**，表现在以下两个方面：（a）复杂查询的增量版本可以递归地归约为对其各子查询的增量化。由此得到一个简单的、基于语法的、无需启发式的算法（算法 4.6），它能把任意 DBSP 查询计划转换为增量形式。（b）将 DBSP 扩展到支持新的原语算子很容易，而且这些算子会立即受益于增量化的其余理论。模块化的一个重要推论是：该理论可以被高效实现，我们在 §8 中简要讨论这一点。 DBSP 的核心概念是流（stream），它用于对随时间发生的变化建模。我们用 $\mathcal{S}_A$ 表示取值为类型 $A$ 的无穷流的类型。若 $s \in \mathcal{S}_A$ 是一个流，则 $s[t] \in A$（$t \in \mathbb{N}$）是 $s$ 的第 $t$ 个元素，也称为流在时刻 $t$ 的值。流算子（stream operator）是消费一个或多个流并产生另一个流的函数。我们用图——也称为“电路”（circuit）——来表示流式计算，其中方框是计算，箭头是流。下图给出一个流算子 $T : \mathcal{S}_A \times \mathcal{S}_B \to \mathcal{S}_C$，它消费两条输入流 $s_0$ 和 $s_1$，产生一条输出流 $s$： 原文第 2 页的电路图 ▲ 原文（第 2 页）此处的电路图 我们通常把流看作“小”值的序列，例如数据库中的插入或删除。不过，我们也把整个数据库看作一条由数据库快照构成的流。我们把数据库建模为流 $DB \in \mathcal{S}_{SCH}$，其中 $SCH$ 是数据库模式。这里的“时间”不是墙钟时间，而是对施加于数据库的事务的计数。由于事务是可线性化的，它们具有全序。$DB[t]$ 是已施加 $t$ 个事务之后数据库内容的快照。 数据库事务也构成一条流 $\Delta DB$，这一次是施加于数据库的变化（change）或增量（delta）的流。该流的值定义为 $(\Delta DB)[t] = DB[t] - DB[t-1]$，其中“$-$”表示两个数据库之间的差，我们很快就会更精确地刻画这一概念。$\Delta DB$ 流由 $DB$ 流经流微分算子（stream differentiation operator）$\mathcal{D}$ 产生；该算子将其输入流的变化流作为输出；因此有 $\mathcal{D}(DB) = \Delta DB$。 反过来，时刻 $t$ 的数据库快照是施加截至 $t$ 的全部事务的累积结果：$DB[t] = \sum_{i \le t} \Delta DB[i]$。把所有变化累加起来的操作 $\mathcal{I}$ 是另一个基本流算子，即流积分（stream integration），它是流微分的逆。下图给出流 $\Delta DB$ 与 $DB$ 之间的关系： 原文第 2 页的电路图 ▲ 原文（第 2 页）此处的电路图 假设给定一个查询 $Q : SCH \to SCH$，它定义一个视图 $V$。在流模型中视图是什么？它也是一条流！数据库流的每个快照都对应视图的一个快照：$V[t] = Q(DB[t])$。一般地，给定任意函数 $f : A \to B$，我们定义 $f$ 的流式“版本”，记作 ${\uparrow}f$（读作“$f$ 的提升”），它把 $f$ 独立地作用于输入流的每个元素。于是可以写成 $V = ({\uparrow}Q)(DB)$。 有了这些基本定义，我们就可以精确地定义 IVM。增量地维护一个视图意味着什么？一个高效的维护算法需要在给定数据库变化的情况下计算视图的变化。给定查询 $Q$，本文的一个关键贡献是利用流积分与流微分定义它的增量版本 $Q^\Delta$： $$Q^\Delta \overset{\mathrm{def}}{=} \mathcal{D} \circ {\uparrow}Q \circ \mathcal{I}.$$ 查询的增量版本维护视图的变化 $$\Delta V \overset{\mathrm{def}}{=} \mathcal{D}(V) = \mathcal{D}({\uparrow}Q(\mathcal{I}(\Delta DB))),$$ 其图形表示如下： ``` ΔDB ──▶ [ I ] ──▶ [ ↑Q ] ──▶ [ D ] ──▶ ΔV DB V ``` 上图中，$\mathcal{I}$ 为流积分、${\uparrow}Q$ 为提升后的查询、$\mathcal{D}$ 为流微分；方框之间的中间流依次是数据库快照流 $DB$ 与视图快照流 $V$。 查询的增量版本是一个有状态的流算子，它直接在变化上计算并产生变化。因此，查询的增量版本总是良定义的。 上述定义给出了增量地计算查询的一种方式，但朴素地应用它会产生低效的执行计划，因为它会在每一步重建数据库。在 §3 中我们将说明如何利用 $\cdot^\Delta$ 变换的代数性质来优化 $Q^\Delta$ 的实现。第一个关键性质是：子查询的增量组合等于各子查询增量版本的组合，即 $(Q_1 \circ Q_2)^\Delta = Q_1^\Delta \circ Q_2^\Delta$。第二个关键性质是：本质上所有基本数据库操作都有高效的增量版本。更准确地说，它们比非增量版本快 $O(|DB|/|\Delta DB|)$ 倍。 借助这套一般性的增量计算理论，我们在 §4 中说明如何在 DBSP 中建模关系查询。这立即给出一个计算任意关系查询增量版本的通用算法。这些结果此前已为人所知，但 DBSP 为它们提供了简洁的建模。§5.1 说明分层单调递归 Datalog 程序如何能在 DBSP 中实现，§6 给出递归程序的增量流式计算。例如，给定以自然递归方式实现的传递闭包，我们的算法能生成一个程序，在图通过添加和删除边而发生变化时高效地维护该图的传递闭包。 本文省略证明，它们可在内容详尽的配套技术报告 [12] 中找到。我们已在 Lean 证明助手 [14] 中形式化了该理论；我们的形式化包含本文所有定理的机器检查证明。 本文作出如下贡献： 1. DBSP，一种简单而富有表达力的流式计算语言。DBSP 给出了一个优雅的形式基础，统一了对流式计算与增量计算的处理。 2. 一个算法，用于将 DBSP 中表达的任何流式计算增量化。 3. 说明 DBSP 如何建模各类查询，例如关系代数、嵌套关系、聚合，以及分层单调 Datalog。 4. 第一个通用的、经过机器检查的 IVM 理论。 5. DBSP 的一个高性能开源实现，用 Rust 编写，可作为通用流式查询引擎。 ## 2 流计算 增量视图维护（incremental view maintenance, IVM）理论的核心概念是流。本节我们形式地引入作为无限取值序列的流，并定义流上的计算。流算子（stream operator，§2.1）是流计算的基本构件。算子可以借助简单规则（§2.2）组合成复杂的计算电路。在 §2.3 中我们引入流上两个本质性的运算：积分与微分。 ### 2.1 流与流算子 $\mathbb{N}$ 是自然数集（从 0 开始），$\mathbb{B}$ 是布尔值集合，$\mathbb{Z}$ 是整数集，$\mathbb{R}$ 是实数集。 **定义 2.1**（流）：给定集合 $A$，一个来自 $A$ 的值的流，或一个 $A$-流，是一个函数 $\mathbb{N} \to A$。我们记 $\mathcal{S}_A \overset{\mathrm{def}}{=} \{s \mid s : \mathbb{N} \to A\}$ 为所有 $A$-流的集合。 当 $s \in \mathcal{S}_A$ 且 $t \in \mathbb{N}$ 时，我们把流 $s$ 的第 $t$ 个元素写成 $s[t]$，而不是通常的 $s(t)$。我们把下标 $t \in \mathbb{N}$ 视为（离散的）时间，把 $s[t] \in A$ 视为流 $s$ “在时刻” $t$ 的值。例如，由 $id[t] = t$ 给出的自然数流 $id \in \mathcal{S}_{\mathbb{N}}$ 就是取值序列 $[0\ 1\ 2\ 3\ 4\ \cdots]$。 **定义 2.2**（流算子）：一个具有 $n$ 个输入的流算子是一个函数 $T : \mathcal{S}_{A_0} \times \cdots \times \mathcal{S}_{A_{n-1}} \to \mathcal{S}_B$。 一般地，我们用“算子”指流上的函数，用“函数”指“标量”值上的计算。 DBSP 是简单类型 lambda 演算的一个扩展——我们将逐步引入它的各个要素。然而，在很多情况下我们发现用电路图来描绘 DBSP 程序更易读。（电路确实隐藏了算子输入的顺序；对于非交换的算子，我们必须额外区分算子的输入。）在电路中，矩形表示一次算子应用（用算子名标注，例如 $T$），而箭头表示一个流。 流算子的复合（函数复合）画成串联的电路。将二元算子 $T : \mathcal{S}_A \times \mathcal{S}_B \to \mathcal{S}_A$ 与一元算子 $S : \mathcal{S}_A \to \mathcal{S}_B$ 复合成计算 $\lambda s.T(T(s, S(s)), S(s)) : \mathcal{S}_A \to \mathcal{S}_A$，其电路为： 原文第 3 页的电路图 ▲ 原文（第 3 页）此处的电路图 输入 $s$ 分两路：一路直接进入第一个 $T$（作为它的第一个输入），另一路先经 $S$ 得到 $S(s)$，再同时送入两个 $T$ 的第二个输入；第一个 $T$ 的输出作为第二个 $T$ 的第一个输入，第二个 $T$ 的输出即 $o$。 **定义 2.3**（提升）：给定一个（标量）函数 $f : A \to B$，我们通过按时间逐点提升（lifting）函数 $f$ 来定义一个流算子 ${\uparrow}f : \mathcal{S}_A \to \mathcal{S}_B$：$({\uparrow}f)(s) \overset{\mathrm{def}}{=} f \circ s$。等价地，$(({\uparrow}f)(s))[t] \overset{\mathrm{def}}{=} f(s[t])$。这可以推广到具有多个参数的函数。 例如，$({\uparrow}(\lambda x.(2x)))(id) = [0\ 2\ 4\ 6\ 8\ \cdots]$。 **命题 2.4**（分配律）：提升对函数复合满足分配律：${\uparrow}(f \circ g) = ({\uparrow}f) \circ ({\uparrow}g)$。 我们说两个 DBSP 程序是等价的，如果它们在流上计算相同的输入-输出函数。我们用符号 $\cong$ 表示两个电路等价。例如，命题 2.4 陈述了如下电路等价： 原文第 3 页的电路图 ▲ 原文（第 3 页）此处的电路图 ### 2.2 阿贝尔群上的流 在本节余下的技术展开中，我们要求流 $\mathcal{S}_A$ 的取值集合 $A$ 构成一个阿贝尔群（交换群）$(A, +, 0_A, -)$。加法定义了“加入新数据”的含义，而减法使我们能够计算差（增量）；群结构将允许我们重排插入与删除。我们稍后会说明，这一限制对于把 DBSP 用于关系数据并不构成问题。现在我们引入一些有用的算子并研究它们的性质。 #### 2.2.1 延迟与时不变性 **定义 2.5**（延迟）：延迟算子（delay operator）[^1]通过把输入延迟一步来产生输出流：$z^{-1}_A : \mathcal{S}_A \to \mathcal{S}_A$： $$z^{-1}_A(s)[t] \overset{\mathrm{def}}{=} \begin{cases} 0_A & \text{当 } t = 0 \\ s[t-1] & \text{当 } t \geq 1 \end{cases}$$ 我们常常省略类型参数 $A$，只写 $z^{-1}$。例如，$z^{-1}(id) = [0\ 0\ 1\ 2\ 3\ \cdots]$。 **定义 2.6**（时不变性）：流算子 $S : \mathcal{S}_A \to \mathcal{S}_B$ 是时不变（time-invariant, TI）的，如果对所有 $s \in \mathcal{S}_A$ 都有 $S(z^{-1}_A(s)) = z^{-1}_B(S(s))$；换言之，如果下面两个电路等价： 原文第 3 页的电路图 ▲ 原文（第 3 页）此处的电路图 该定义自然地推广到具有多个输入的算子。任意输入个数的 TI 算子的复合仍是 TI 的。延迟算子 $z^{-1}$ 是 TI 的。DBSP 只使用时不变算子。 #### 2.2.2 因果与严格算子 **定义 2.7**（因果性）：流算子 $S : \mathcal{S}_A \to \mathcal{S}_B$ 是因果的（causal），当对所有 $s, s' \in \mathcal{S}_A$ 和所有时刻 $t$ 都有： $$(\forall i \leq t.\, s[i] = s'[i]) \Rightarrow S(s)[t] = S(s')[t].$$ 换言之，时刻 $t$ 的输出值只能依赖于时刻 $t' \leq t$ 的输入值。由提升产生的算子是因果的，$z^{-1}$ 也是因果的。所有 DBSP 算子都是因果的。任意输入个数的因果算子的复合仍是因果的。 **定义 2.8**（严格性）：流算子 $F : \mathcal{S}_A \to \mathcal{S}_B$ 是严格的（strict），如果 $\forall s, s' \in \mathcal{S}_A$、$\forall t \in \mathbb{N}$ 都有： $$(\forall i < t.\, s[i] = s'[i]) \Rightarrow F(s)[t] = F(s')[t].$$ 换言之，$F(s)$ 的第 $t$ 个输出只能依赖于输入 $s$ 在 0 与 $t-1$ 之间的“过去”值。特别地，$F(s)[0] = 0_B$ 对所有 $s \in \mathcal{S}_A$ 都相同。严格算子是因果的。提升算子一般而言不是严格的。$z^{-1}$ 是严格的。 **命题 2.9**：对严格的 $F : \mathcal{S}_A \to \mathcal{S}_A$，方程 $\alpha = F(\alpha)$ 有唯一解 $\alpha \in \mathcal{S}_A$，记作 $\mathrm{fix}\,\alpha.F(\alpha)$。 因此，每个从集合到自身的严格算子都有唯一的不动点。这个简单的证明依赖强归纳法，说明解 $\alpha[t]$ 只依赖于 $\alpha$ 在 $t$ 之前的值。 考虑一个带有严格反馈边的电路： 原文第 3 页的电路图 ▲ 原文（第 3 页）此处的电路图 （反馈边上的 $F$ 从输出 $\alpha$ 取输入，其输出作为 $T$ 的第二个输入。）该电路是流上一个良定义的函数： **引理 2.10**：若 $F : \mathcal{S}_B \to \mathcal{S}_B$ 是严格的，且 $T : \mathcal{S}_A \times \mathcal{S}_B \to \mathcal{S}_B$ 是因果的，则算子 $Q(s) = \mathrm{fix}\,\alpha.T(s, F(\alpha))$ 是良定义且因果的。此外，若 $F$ 与 $T$ 都是 TI 的，则 $Q$ 也是 TI 的。 所有 DBSP 计算都只用提升函数和延迟来构造。我们在 §6 中再加入两个算子。 ### 2.3 积分与微分 记住我们要求流的元素来自阿贝尔群 $A$。流本身也构成一个阿贝尔群： **命题 2.11**：通过提升 $A$ 的 $+$ 与一元 $-$ 运算得到的结构 $(\mathcal{S}_A, +, 0, -)$ 是一个阿贝尔群。$0$ 是所有取值均为 $0_A$ 的流。 流的加法与取负是因果的 TI 算子。 **定义 2.12**：给定阿贝尔群 $A$ 与 $B$，我们称流算子 $S : \mathcal{S}_A \to \mathcal{S}_B$ 是线性的（linear），如果它是一个群同态，即 $S(a+b) = S(a) + S(b)$（从而 $S(0) = 0$ 且 $S(-a) = -S(a)$）。 给定线性函数 $f : A \to B$，流算子 ${\uparrow}f$ 是线性且时不变的（linear and time-invariant, LTI）。$z^{-1}$ 也是 LTI 的。 **定义 2.13**（双线性）：两个参数的函数 $f : A \times B \to C$（其中 $A, B, C$ 是群）是双线性的（bilinear），如果它对每个参数分别线性（即对加法满足分配律）：$\forall a, b, c, d.\,f(a+b, c) = f(a, c) + f(b, c)$，且 $f(a, c+d) = f(a, c) + f(c, d)$。 该定义推广到流算子。双线性函数 $f$ 的提升是一个双线性流算子 ${\uparrow}f$。一个例子是提升乘法：$f : \mathcal{S}_{\mathbb{N}} \times \mathcal{S}_{\mathbb{N}} \to \mathcal{S}_{\mathbb{N}}$，$f(a,b)[t] = a[t] \cdot b[t]$。 线性算子的“反馈回路”是线性的： **命题 2.14**：设 $S$ 是一个一元、因果的 LTI 算子。则算子 $Q(s) = \mathrm{fix}\,\alpha.S(s + z^{-1}(\alpha))$ 是良定义且 LTI 的： 原文第 3 页的电路图 ▲ 原文（第 3 页）此处的电路图 **定义 2.15**（微分）：微分算子（differentiation operator） $\mathcal{D}_{\mathcal{S}_A} : \mathcal{S}_A \to \mathcal{S}_A$ 定义为：$\mathcal{D}(s) \overset{\mathrm{def}}{=} s - z^{-1}(s)$。 原文第 4 页的电路图 ▲ 原文（第 4 页）此处的电路图 我们一般省略类型，只写 $\mathcal{D}$。若 $t > 0$，则 $\mathcal{D}(s)[t] = s[t] - s[t-1]$。例如，$\mathcal{D}(id) = [0\ 1\ 1\ 1\ 1\ \cdots]$。 若 $s$ 是一个流，则 $\mathcal{D}(s)$ 是 $s$ 的变化流。 **命题 2.16**：$\mathcal{D}$ 是因果且 LTI 的。 积分算子从其变化“重构”出一个流： **定义 2.17**（积分）：积分算子（integration operator） $\mathcal{I}_{\mathcal{S}_A} : \mathcal{S}_A \to \mathcal{S}_A$ 定义为 $\mathcal{I}(s) \overset{\mathrm{def}}{=} \lambda s.\,\mathrm{fix}\,\alpha.(s + z^{-1}(\alpha))$： 原文第 4 页的电路图 ▲ 原文（第 4 页）此处的电路图 我们一般也省略类型，只写 $\mathcal{I}$。这就是命题 2.14 中取 $S$ 为恒等函数的构造。 **命题 2.18**：$\mathcal{I}(s)$ 是施加于流 $s$ 的离散（不定）积分：$\mathcal{I}(s)[t] = \sum_{i \leq t} s[i]$。 例如，$\mathcal{I}(id) = [0\ 1\ 3\ 6\ 10\ \cdots]$。 **命题 2.19**：$\mathcal{I}$ 是因果且 LTI 的。 **定理 2.20**（互逆）：积分与微分互为逆运算：$\forall s.\,\mathcal{I}(\mathcal{D}(s)) = \mathcal{D}(\mathcal{I}(s)) = s$。 原文第 4 页的电路图 ▲ 原文（第 4 页）此处的电路图 [^1]: 名称 $z^{-1}$ 来自数字信号处理（digital signal processing, DSP）文献，与 z 变换（z-transform）[44] 有关。 ## 3 增量视图维护 本节我们定义增量视图维护（incremental view maintenance, IVM）并分析其性质。 **定义 3.1**：给定一元流算子 $Q : \mathcal{S}_A \to \mathcal{S}_B$，我们定义 $Q$ 的**增量版本**为： $$Q^{\Delta} \overset{\text{def}}{=} \mathcal{D} \circ Q \circ \mathcal{I}. \qquad (3.1)$$ $Q^{\Delta}$ 与 $Q$ 具有相同的“类型”：$Q^{\Delta} : \mathcal{S}_A \to \mathcal{S}_B$。对于有多个输入的算子，我们通过对每个输入独立地施加 $\mathcal{I}$ 来定义其增量版本：例如，若 $T : \mathcal{S}_A \times \mathcal{S}_B \to \mathcal{S}_C$，则 $T^{\Delta}(a, b) \overset{\text{def}}{=} \mathcal{D}(T(\mathcal{I}(a), \mathcal{I}(b)))$。 原文第 4 页的电路图 ▲ 原文（第 4 页）此处的电路图 图中 $I$ 表示积分算子 $\mathcal{I}$，$D$ 表示微分算子 $\mathcal{D}$；$s$ 与 $o$ 是流，$\Delta s$ 与 $\Delta o$ 是变化流。 若 $Q(s) = o$ 是一次计算，则 $Q^{\Delta}$ 执行与 $Q$“相同”的计算，只不过是在变化流 $\Delta s$ 与 $\Delta o$ 之间进行。 请注意，我们对增量计算的定义只对*流式*计算才有意义；这与经典定义（例如 [25]）不同，后者只考虑单个变化。把该定义推广到流上操作会给我们额外的能力，尤其是在处理递归查询时。 下面的命题是我们的核心结果之一： **命题 3.2**（增量版本的性质）： - **求逆（inversion）**：$Q \mapsto Q^{\Delta}$ 是双射；其逆为 $Q \mapsto \mathcal{I} \circ Q \circ \mathcal{D}$。 - **不变性（invariance）**：$+^{\Delta} = +$，$(z^{-1})^{\Delta} = z^{-1}$，$(-)^{\Delta} = -$，$\mathcal{I}^{\Delta} = \mathcal{I}$，$\mathcal{D}^{\Delta} = \mathcal{D}$。 - **推/拉（push/pull）**：$Q \circ \mathcal{I} = \mathcal{I} \circ Q^{\Delta}$；$\mathcal{D} \circ Q = Q^{\Delta} \circ \mathcal{D}$。 - **链式（chain）**：$(Q_1 \circ Q_2)^{\Delta} = Q_1^{\Delta} \circ Q_2^{\Delta}$（该性质可推广到有多个输入的算子）。 - **加法（add）**：$(Q_1 + Q_2)^{\Delta} = Q_1^{\Delta} + Q_2^{\Delta}$。 - **循环（cycle）**：$(\lambda s.\ \mathrm{fix}\ \alpha.\ T(s, z^{-1}(\alpha)))^{\Delta} = \lambda s.\ \mathrm{fix}\ \alpha.\ T^{\Delta}(s, z^{-1}(\alpha))$。 **链式法则（chain rule）**指出如下两个电路是等价的： 原文第 4 页的电路图 ▲ 原文（第 4 页）此处的电路图 换言之，要对一个复合查询做增量化，你可以分别对每个子查询做增量化。这给了我们一个简单、由语法驱动、确定性的配方（recipe），用来计算任意复杂查询的增量版本。 **循环法则（cycle rule）**指出如下电路是等价的： 原文第 4 页的电路图 ▲ 原文（第 4 页）此处的电路图 图中反馈边从 $T$（或 $T^{\Delta}$）的输出引出，经延迟算子 $z^{-1}$ 后送回该算子的输入。 换言之，一个查询周围反馈环的增量版本，就是把环体换成该查询的增量查询之后的同一个反馈环。当我们实现递归查询时，这个结果的重要性就会显现出来。 为了高效地执行增量查询，我们希望直接在变化流上计算，而不对它们做积分。上面的不变性性质表明，流算子 $+$、$-$ 与 $z^{-1}$ 和它们的增量版本完全相同。下面的定理把这一点推广到线性算子与双线性算子： **定理 3.3**（线性）：对于 LTI（线性时不变，linear time-invariant）算子 $Q$，有 $Q^{\Delta} = Q$。 **定理 3.4**（双线性）：对于双线性的 TI（时不变，time-invariant）算子 $\times$，有 $$(a \times b)^{\Delta} = a \times b + z^{-1}(\mathcal{I}(a)) \times b + a \times z^{-1}(\mathcal{I}(b)) = \mathcal{I}(a) \times b + a \times z^{-1}(\mathcal{I}(b)).$$ 用图形表示如下（同一输入的多路分支表示扇出）： 原文第 4 页的电路图 ▲ 原文（第 4 页）此处的电路图 把定理 3.4 用 $\Delta a$ 表示 $a$ 的变化流改写，我们就得到熟悉的增量等值连接公式：$\Delta(a \times b) = \Delta a \times \Delta b + a \times (\Delta b) + (\Delta a) \times b$；等值连接确实是双线性的。 ## 4 关系代数的 IVM §2 与 §3 的结果适用于任意群值上的流。本节我们把它们用于关系数据库的 IVM。正如引言所述，我们的目标是高效地计算定义数据库视图的任意关系查询 $Q$ 的增量版本。 然而，我们面临一个技术问题：$\mathcal{I}$ 与 $\mathcal{D}$ 算子是在阿贝尔群上定义的，而关系数据库一般并不是阿贝尔群，因为它们操作的是集合。幸运的是，数据库文献中有一个著名的工具，它通过用 ℤ-集合（ℤ-set，也称为 z-关系 [22]）表示集合，把集合运算转换为群运算。 我们先定义 ℤ-集合群，然后回顾关系查询如何被转换为 ℤ-集合上的 DBSP 电路。这种翻译之所以能被高效地增量化，是因为许多基本关系查询都可以用 LTI 的 ℤ-集合算子来表示（见 §4.2）。 ### 4.1 ℤ-集合作为阿贝尔群 ℤ-集合推广了数据库表：可以把 ℤ-集合想成一张表，其中每一行都关联一个权重，该权重可能为负。 给定一个集合 $A$，我们定义 $A$ 上的 ℤ-集合为从 $A$ 到 $\mathbb{Z}$ 的**有限支撑**函数。也就是函数 $f : A \to \mathbb{Z}$，其中至多对有限个 $x \in A$ 有 $f(x) \neq 0$。我们也用 $\mathbb{Z}[A]$ 表示元素取自 $A$ 的 ℤ-集合的类型。$\mathbb{Z}[A]$ 中的值可以被看作键取自 $A$、值取自 $\mathbb{Z}$ 的键值映射，这也正是使用数组下标记号的理由。若 $m \in \mathbb{Z}[A]$，我们写 $m[a]$ 而不写 $m(a)$，同样是为了沿用下标记号。 一个具体的 ℤ-集合 $m \in \mathbb{Z}[A]$ 可以通过枚举其权重非零的元素及相应的权重来表示：$m = \{x_1 \mapsto w_1, \ldots, x_n \mapsto w_n\}$。我们称 $w_i \in \mathbb{Z}$ 为 $x_i \in A$ 的**权重**。权重可以为负。当且仅当 $m[x] \neq 0$ 时，我们写 $x \in m$。我们还写 $w \cdot x$ 来表示 $\{x \mapsto w\}$。 考虑一个具体的 ℤ-集合 $R \in \mathbb{Z}[\text{string}]$，它定义为 $R = \{\text{joe} \mapsto 1, \text{anne} \mapsto -1\}$。$R$ 的定义域中有两个元素：权重为 1 的 joe（因此 $R[\text{joe}] = 1$）和权重为 $-1$ 的 anne。我们说 $\text{joe} \in R$ 且 $\text{anne} \in R$。 由于 $\mathbb{Z}$ 是阿贝尔环，$\mathbb{Z}[A]$ 也是阿贝尔环（从而是群）。这个群 $(\mathbb{Z}[A], +_{\mathbb{Z}[A]}, 0_{\mathbb{Z}[A]}, -_{\mathbb{Z}[A]})$ 的加法与减法都是逐点定义的：$(f +_{\mathbb{Z}[A]} g)(x) = f(x) + g(x), \forall x \in A$。$\mathbb{Z}[A]$ 的 $0$ 元素是函数 $0_{\mathbb{Z}[A]}$，其定义为 $0_{\mathbb{Z}[A]}(x) = 0, \forall x \in A$。例如，$R + R = \{\text{joe} \mapsto 2, \text{anne} \mapsto -2\}$。由于 ℤ-集合构成群，§2 的所有结果都适用于 ℤ-集合上的流。 ℤ-集合推广了集合与多重集。元素取自 $A$ 的集合可以这样表示为 ℤ-集合：给每个元素关联权重 1。多重集是所有权重都为正的 ℤ-集合。关键在于，ℤ-集合还能表示对集合与多重集的任意变化。变化中的负权重表示被“删除”的元素。 **定义 4.1**：若一个 ℤ-集合中每个元素的权重都为 1，则称该 ℤ-集合**表示一个集合**。我们定义一个函数来检查这一性质，$\mathrm{isset} : \mathbb{Z}[A] \to \mathbb{B}$，它由下式给出： $$\mathrm{isset}(m) \overset{\text{def}}{=} \begin{cases} \text{true} & \text{若 } m[x] = 1, \forall x \in m \\ \text{false} & \text{其他情况} \end{cases}$$ 对我们的例子 $\mathrm{isset}(R) = \text{false}$，因为 $R[\text{anne}] = -1$。 **定义 4.2**：若一个 ℤ-集合中每个元素的权重都为正，则称该 ℤ-集合是**正的**（或一个**多重集**）。我们定义一个函数来检查这一性质，$\mathrm{ispositive} : \mathbb{Z}[A] \to \mathbb{B}$，它由下式给出： $$\mathrm{ispositive}(m) \overset{\text{def}}{=} \begin{cases} \text{true} & \text{若 } m[x] \geq 0, \forall x \in A \\ \text{false} & \text{其他情况} \end{cases}$$ 我们有 $\forall m \in \mathbb{Z}[A].\ \mathrm{isset}(m) \Rightarrow \mathrm{ispositive}(m)$。$\mathrm{ispositive}(R) = \text{false}$，因为 $R[\text{anne}] = -1$。 当 $m$ 为正时我们写 $m \geq 0$。对于正的 $m, n \in \mathbb{Z}[A]$，当且仅当 $m - n \geq 0$ 时我们写 $m \geq n$。$\geq$ 是一个偏序。 我们称函数 $f : \mathbb{Z}[A] \to \mathbb{Z}[B]$ 是**正的**，如果它把正的值映射为正的值：$\forall x \in \mathbb{Z}[A],\ x \geq 0_{\mathbb{Z}[A]} \Rightarrow f(x) \geq 0_{\mathbb{Z}[B]}$。我们对函数沿用同样的记号：$\mathrm{ispositive}(f)$。 **定义 4.3**（distinct）：函数 $\mathrm{distinct} : \mathbb{Z}[A] \to \mathbb{Z}[A]$ 把一个 ℤ-集合“转换”为集合： $$\mathrm{distinct}(m)[x] \overset{\text{def}}{=} \begin{cases} 1 & \text{若 } m[x] > 0 \\ 0 & \text{其他情况} \end{cases}$$ 注意 $\mathrm{distinct}$ 从多重集中“删除”重复项，它也会消去权重为负的元素。$\mathrm{distinct}(R) = \{\text{joe} \mapsto 1\}$。这个 $\mathrm{distinct}$ 的定义虽然非常简单，却是经过仔细选择的，为的是使我们能够用 ℤ-集合算子来实现关系（集合）算子。 **推广电路图。** 从现在起，我们将用电路来对纯量（在我们的情形中是 ℤ-集合）以及 ℤ-集合的流进行计算。对于流上的函数或纯量上的函数，我们使用相同的图形表示：带输入箭头与输出箭头的方框。对于纯量函数，箭头上的“值”是纯量而不是流；除此之外，把方框解释为函数应用这一点不变。因此，我们将用电路来刻画关系查询计划。 ### 4.2 实现关系算子 关系代数可以由 ℤ-集合上的计算来实现，这一点此前已有工作表明，例如 [23]。关系算子到 DBSP 的翻译如表 1 所示。表的第一行表明，复合查询是递归地翻译的。这给了我们一个把任意关系查询计划翻译成 DBSP 电路的配方。 这一翻译相当直截了当，但许多算子都需要施加一个 $\mathrm{distinct}$ 才能产生集合。例如，$a \cup b = \mathrm{distinct}(a + b)$，$a \setminus b = \mathrm{distinct}(a - b)$，$(a \times b)((x, y)) = a[x] \times b[y]$。注意，正是 $\mathrm{distinct}$ 算子的使用使 DBSP 能够建模完整的关系代数，包括集合差（而不只是正片段）。 已有工作（例如 [22] 中的命题 6.13）表明，在不改变查询语义的前提下，可以消去查询计划中某些 $\mathrm{distinct}$ 的调用；我们将会看到，$\mathrm{distinct}$ 算子的增量版本会带来显著的空间开销。 **命题 4.4**：设 $Q$ 是下列 ℤ-集合算子之一：过滤 $\sigma$、连接 $\bowtie$ 或笛卡尔积 $\times$。则我们有 $\forall i \in \mathbb{Z}[I],\ \mathrm{ispositive}(i) \Rightarrow Q(\mathrm{distinct}(i)) = \mathrm{distinct}(Q(i))$。 **命题 4.5**：设 $Q$ 是下列 ℤ-集合算子之一：过滤 $\sigma$、投影 $\pi$、$\mathrm{map}(f)$[^2]、加法 $+$、连接 $\bowtie$ 或笛卡尔积 $\times$。则我们有 $\mathrm{ispositive}(i) \Rightarrow \mathrm{distinct}(Q(\mathrm{distinct}(i))) = \mathrm{distinct}(Q(i))$。 这些性质使我们能够通过在一串计算的末端只执行一次 $\mathrm{distinct}$ 来“归并（consolidate）”$\mathrm{distinct}$ 算子。 [^2]: 严格来说，$\mathrm{map}$（把用户定义的函数施加到每一行）并不是关系算子。 ### 4.3 增量视图维护 让我们考虑定义视图 $V$ 的关系查询 $Q$。为了构造一个电路来增量地维护 $V$，我们执行以下机械步骤： **算法 4.6**（增量视图维护）： 1. 使用表 1 中的规则把 $Q$ 翻译成一个电路。 2. 应用 $\mathit{distinct}$ 消除规则（4.4、4.5），直到收敛[^3]。 3. 提升整个电路，即应用命题 2.4，把它转换为一个作用于流的电路。 4. 对整个电路做增量化，即用 $\mathcal{I}$ 和 $\mathcal{D}$ 把它“包围”起来。 5. 在查询结构上递归地应用命题 3.2 中的链式法则，得到一个增量实现。 **表 1**：SQL 关系集合算子在 DBSP 中的实现。每个查询都假定输入 `I`、`I1`、`I2` 是集合，并且产生输出集合。 | 操作 | SQL 示例 | DBSP 电路 | 说明 | |---|---|---|---| | 复合
（composition） | `SELECT DISTINCT ... FROM`
`( SELECT ... FROM ...)` | `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 ──▶ [π] ──▶ [distinct] ──▶ O` | $\pi(i)[y] \overset{\text{def}}{=} \sum_{x \in i,\; x\vert_c = y} i[x]$；
$x\vert_c$ 是元组 $x$ 在列 $c$ 上的投影；
$\pi$ 是线性的；$\mathit{ispositive}(\pi)$。 | | 过滤
（filtering） | `SELECT * FROM I`
`WHERE p(I.c)` | `I ──▶ [σ_P] ──▶ O` | $\sigma_P(m)[x] \overset{\text{def}}{=} \begin{cases} m[x] & \text{若 } P(x) \\ 0 & \text{否则} \end{cases}$；
$P : A \to \mathbb{B}$ 是谓词；
$\sigma_P$ 是线性的；$\mathit{ispositive}(\sigma_P)$。 | | 笛卡尔积
（Cartesian product） | `SELECT I1.*, I2.*`
`FROM I1, I2` | `I1 ──┐`
` ├──▶ [×] ──▶ O`
`I2 ──┘` | $(a \times b)((x,y)) \overset{\text{def}}{=} a[x] \times b[y]$；
$\times$ 是双线性的，$\mathit{ispositive}(\times)$。 | | 等值连接
（equi-join） | `SELECT I1.*, I2.*`
`FROM I1 JOIN I2`
`ON I1.c1 = I2.c2` | `I1 ──┐`
` ├──▶ [⋈_{c1=c2}] ──▶ O`
`I2 ──┘` | $(a \bowtie b)((x,y)) \overset{\text{def}}{=} a[x] \times b[y]$
当 $x\vert_{c_1} = y\vert_{c_2}$ 时；
$\bowtie$ 是双线性的，$\mathit{ispositive}(\bowtie)$。 | | 交
（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}$ 从结果中移除权重为负的元素。 | 该算法是确定性的，其运行时间与查询中算子的数量成正比。第 (2) 步生成一个等价电路，其中的 $\mathit{distinct}$ 算子可能更少。第 (3) 步得到一个电路，它消费由完整数据库快照组成的流，并输出由完整视图快照组成的流。第 (4) 步得到一个电路，它消费数据库变化流并输出视图变化流；然而该电路的内部运算是非增量的，因为它使用积分算子重建完整的数据库。第 (5) 步通过把每个基本算子替换为其增量版本，使该电路增量化。 表 1 的电路中出现的大多数算子都是线性的，因此具有非常高效的增量版本（我们在 §4.4 讨论复杂度）。一个值得注意的例外是 $\mathit{distinct}$。下一个命题表明，$\mathit{distinct}$ 的增量版本也是高效的，并且计算它所需的工作量与输入变化的大小成正比： **命题 4.7**：以下电路实现 $({\uparrow}\mathit{distinct})^\Delta$： 原文第 6 页的电路图 ▲ 原文（第 6 页）此处的电路图 其中 $H : \mathbb{Z}[A] \times \mathbb{Z}[A] \to \mathbb{Z}[A]$ 定义为： $$ H(i, d)[x] \overset{\text{def}}{=} \begin{cases} -1 & \text{若 } i[x] > 0 \text{ 且 } (i + d)[x] \le 0 \\ 1 & \text{若 } i[x] \le 0 \text{ 且 } (i + d)[x] > 0 \\ 0 & \text{否则} \end{cases} $$ “$\cong$”右侧的电路把当前的变化 $\Delta d$ 与 $i$（此前所有变化积分后的旧值，经 $z^{-1}$ 延迟一个时间步得到）一起送入提升后的函数 ${\uparrow}H$，由它直接产生输出变化 $\Delta o$。 下面是 $\mathit{distinct}$ 可以被高效增量化的直觉：$({\uparrow}\mathit{distinct})^\Delta$ 的输出中能够出现的元素，必定在输入中已经发生了变化。因此输出变化的大小不会大于输入变化的大小。在上面的电路中，$i$ 是所有变化的积分的前一版本，即正在计算其 $\mathit{distinct}$ 值的那个完整的 $\mathbb{Z}$-集合。函数 $H$ 检测在加上新的增量 $d$ 时，$i$ 中某个元素的权重是否在改变符号（从正变负或反之）。 ### 4.4 增量电路的复杂度 增量电路是高效的。我们在处理第 $t$ 个输入变化时评估一个电路的开销。即使 $Q$ 是纯函数，$Q^\Delta$ 实际上仍是一个带有内部状态的流式系统。这些状态完全存储在延迟算子 $z^{-1}$ 中，其中一部分延迟算子出现在 $\mathcal{I}$ 和 $\mathcal{D}$ 算子内部。$Q^\Delta$ 对第 $t$ 个输入产生的结果，一般不仅取决于新的第 $t$ 个输入，还取决于它此前收到的所有输入。 我们论证增量版电路中的每个算子在计算量和空间上都是高效的。我们采用标准的 IVM 假设：每个算子的输入变化都很小： $$ |\Delta DB[t]| \ll |DB[t]| = |(\mathcal{I}(\Delta DB))[t]| $$ 未经优化的增量算子 $Q^\Delta = \mathcal{D} \circ Q \circ \mathcal{I}$ 在整个数据库 $DB$（输入流的积分）上求值查询 $Q$：$DB = \mathcal{I}(\Delta DB)$；因此它的时间复杂度与非增量地求值 $Q$ 相同。此外，$\mathcal{I}$ 和 $\mathcal{D}$ 算子各自使用 $O(|DB[t]|)$ 的内存。 增量算法中的第 (5) 步应用了 §3 中描述的优化；这些优化把每个算子的时间复杂度降低为 $O(|\Delta DB[t]|)$ 的函数。例如，定理 3.3 允许在时间 $O(|\Delta DB[t]|)$ 内求值 $S^\Delta$，其中 $S$ 是线性算子。$\mathcal{I}$ 算子也可以在 $O(|\Delta DB[t]|)$ 时间内求值，因为 $\mathcal{I}(\Delta DB)[t]$ 输出中出现的所有值必定存在于当前的输入变化 $\Delta DB[t]$ 中。类似地，虽然 $\mathit{distinct}$ 算子不是线性的，但根据命题 4.7，$({\uparrow}\mathit{distinct})^\Delta$ 也可以在 $O(|\Delta DB[t]|)$ 时间内求值。双线性算子（包括连接）可以在时间 $O(|DB[t]| \times |\Delta DB[t]|)$ 内求值，这比完全重新求值要好一个因子 $|DB[t]|/|\Delta DB[t]|$。 线性算子的空间复杂度是 0（零），因为它们不持久存储任何数据。$({\uparrow}\mathit{distinct})^\Delta$、$({\uparrow}\bowtie)^\Delta$、$\mathcal{I}$ 和 $\mathcal{D}$ 这类算子的空间复杂度是 $O(|DB[t]|)$。它们需要完整地存储其输入关系或输出关系。 #### 4.4.1 IVM 查询计划与最优性 让我们再次审视用算法 4.6 得到了什么。一个关系代数查询可以由多个计划实现，每个计划都有不同的、依赖于数据的代价[^4]。算法 4.6 的输入是一个（关系代数的）非增量查询计划，由查询规划器产生。该算法产生一个与输入计划“相似”的增量计划。 标准的查询规划器使用基于代价的启发式方法和数据统计信息来优化计划。通用的 IVM 规划器没有这种便利，因为计划必须在任何数据被送入数据库之前生成。尽管如此，仍然可以使用所有标准的查询优化技术（也许基于历史统计信息）来生成提供给算法 4.6 的查询计划。在 IVM 计划的语境下，最优性问题比即席查询的优化要困难得多，因为选定的 IVM 计划将在未来的所有数据库更新中执行。 此外，由于增量计算维护内部状态，因此增量计划不能像我们可以根据当前数据统计信息更换即席查询那样，在运行途中被简单地更换：部署一个新计划通常需要构造它的内部状态，而该状态是由此前全部更新历史产生的。幸运的是，安装一个新的增量计划有一个简单但多少有些昂贵的办法：把数据库当前的全部状态作为一个大的变化输入进去。 ### 4.5 关系查询示例 我们把 IVM 算法 4.6 应用到一个具体的关系 SQL 查询上： ```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 ``` **第 1 步**：使用表 1 中的翻译规则，创建一个 DBSP 电路来表示这个查询；注意，这个电路本质上是该查询的一个数据流实现。（注意该查询要求 `SELECT DISTINCT`，因此在 $\sigma$ 之后有一个 $\mathit{distinct}$ 算子）： 原文第 7 页的电路图 ▲ 原文（第 7 页）此处的电路图 **第 2 步**：应用规则消除 $\mathit{distinct}$ 算子。首先使用命题 4.5： 原文第 7 页的电路图 ▲ 原文（第 7 页）此处的电路图 命题 4.4 中的规则给出（从现在起我们省略下标以节省空间）： 原文第 7 页的电路图 ▲ 原文（第 7 页）此处的电路图 然后再次使用 4.5： 原文第 7 页的电路图 ▲ 原文（第 7 页）此处的电路图 此时已经没有更多的 $\mathit{distinct}$ 消除规则可以应用。 **第 3 步**：我们利用“复合在提升下满足分配律”（命题 2.4）提升该电路；由此得到一个在流上计算的电路，即：对于每一对新的输入关系 `t1` 和 `t2`，它都会产生一个输出视图 `V`： 原文第 7 页的电路图 ▲ 原文（第 7 页）此处的电路图 **第 4 步**：对电路做增量化，得到一个在变化上计算的电路；该电路接收对关系 `t1` 和 `t2` 的变化，并对每个这样的变化产生输出视图 `V` 中相应的变化： 原文第 7 页的电路图 ▲ 原文（第 7 页）此处的电路图 **第 5 步**：应用链式法则，把电路重写为增量算子的复合： 原文第 7 页的电路图 ▲ 原文（第 7 页）此处的电路图 利用 $\sigma$ 和 $\pi$ 的线性来化简该电路（注意所有线性算子不再带有 ${\cdot}^\Delta$）： 原文第 8 页的电路图 ▲ 原文（第 8 页）此处的电路图 最后，用双线性算子的公式（定理 3.4）替换增量连接，并用命题 4.7 替换增量 $\mathit{distinct}$，得到以下电路。先看各输入分支及其命名的中间值： ``` Δt1 ──▶ [↑σ] ──▶ [↑π] ──┬──────────────▶ Δa └──▶ [I] ──▶ a Δt2 ──▶ [↑σ] ──▶ [↑π] ──┬──────────────▶ Δb └──▶ [I] ──▶ [z⁻¹] ──▶ b⁻¹ ``` 再由两个连接实例求和得到连接的变化，最后经 $\mathit{distinct}$ 的增量电路产生 $\Delta V$： 原文第 8 页的电路图 ▲ 原文（第 8 页）此处的电路图 其中 $a = \mathcal{I}(\Delta a)$ 与 $b = \mathcal{I}(\Delta b)$ 是两个子查询输出的当前（积分后）值，$b^{-1} = z^{-1}(\mathcal{I}(\Delta b))$ 是 $b$ 延迟一个时间步的旧值，$z^{-1}$ 是延迟算子；两个连接实例之和恰好是定理 3.4 中双线性算子增量公式 $\mathcal{I}(\Delta a) \bowtie \Delta b + \Delta a \bowtie z^{-1}(\mathcal{I}(\Delta b))$ 的两项。$H$ 是命题 4.7 中的符号变化检测函数（$i$ 是求和结果经 $\mathcal{I}$、$z^{-1}$ 得到的旧积分值，$d$ 是同一个求和结果本身）。 注意，所得电路包含三个积分运算：两个来自连接，一个来自 $\mathit{distinct}$。它还包含两个连接算子。然而，每个算子对每个新输入所做的工作量与变化的大小成正比。 [^3]: 规则的施加顺序无关紧要，因为该算法是合流的（confluent）：它总是产生相同的最终结果。 [^4]: 最优计划不仅取决于查询，也取决于数据。 ## 5 递归查询 递归查询在许多应用中非常有用。例如，图可达性或传递闭包这类图算法，天然就可以用递归查询来表达。 我们引入两个简单的 DBSP 流算子，用于表达递归查询的求值。这些算子使我们能够构造实现循环结构的电路，而循环结构用于反复迭代计算，直到到达一个不动点。 **定义 5.1**（几乎处处为零）：称流 $s \in \mathcal{S}_A$ 是**几乎处处为零**的（zero almost-everywhere），如果它只有有限个非零值，即存在一个时间 $t_0 \in \mathbb{N}$，使得 $\forall t \ge t_0.\ s[t] = 0$。我们把几乎处处为零的流所构成的集合记为 $\overline{\mathcal{S}_A} \subset \mathcal{S}_A$。 **流引入（$\delta_0$）**：delta 函数（得名于狄拉克 delta 函数）$\delta_0 : A \to \mathcal{S}_A$ 由一个标量值产生一个流： $$\delta_0(v)[t] \stackrel{\mathrm{def}}{=} \begin{cases} v & \text{若 } t = 0 \\ 0_A & \text{否则} \end{cases}$$ 例如，$\delta_0(5)$ 是流 $[\,5\ 0\ 0\ 0\ 0\ \cdots\,]$。 **流消去（$\int$）**：我们在几乎处处为零的流上定义函数 $\int : \mathcal{S}_A \to A$ 为 $\int(s) \stackrel{\mathrm{def}}{=} \sum_{t \ge 0} s[t]$。$\int$ 与 $\mathcal{I}$ 密切相关；如果 $\mathcal{I}$ 是不定（离散）积分，那么 $\int$ 就是区间 $0 - \infty$ 上的定（离散）积分。例如，$\int([\,1\ 2\ 3\ 0\ 0\ \cdots\,]) = 6$。 对于许多类查询（包括下面给出的关系查询与 Datalog 查询），$\int$ 算子都可以“近似”而不损失精度：一直积分到遇到的第一个 0 值为止。 **命题 5.2**：$\delta_0$ 与 $\int$ 都是 LTI 的。 **嵌套时间域**：到目前为止，我们默认程序中的所有流共享同一个“时间”。例如，当我们把两个流相加时，我们假设它们在时间维上使用同一个“时钟”。然而，$\delta_0$ 算子会创建一个带有“新的”、独立时间维的流。我们要求良构电路（well-formed circuit）把这类嵌套时间域“隔离”开，办法是用 $\delta_0$ 与 $\int$ 算子把它们“括”起来： 原文第 8 页的电路图 ▲ 原文（第 8 页）此处的电路图 在该电路中，双箭头表示流值，单箭头表示标量值[^5]。$Q$ 是一个流式算子，但整个电路是一个标量函数。 下面的算法 5.3 把递归查询翻译为 DBSP 电路，它总是产生良构电路。 ### 5.1 递归查询的实现 我们描述 DBSP 中针对分层 Datalog 的递归查询实现。一般而言，一个递归 Datalog 程序把一组相互递归的关系 $O_1,..,O_n$ 定义为一个方程 $(O_1,..,O_n) = R(I_1,..,I_m, O_1,..,O_n)$，其中 $I_1,..,I_m$ 是输入关系，$R$ 是一个关系（非递归）查询。 我们针对单输入、单输出查询这个更简单的情形描述该算法[^6]。算法的输入是形如 $O = R(I, O)$ 的 Datalog 查询，其中 $R$ 是一个关系型、非递归的查询，它产生一个集合作为结果，但它的输出 $O$ 同时也是一个输入。算法的输出是一个 DBSP 电路，该电路在给定输入 $I$ 时求值这个递归查询并产生输出 $O$。这里我们构造的是一个非增量电路，它求值该 Datalog 查询；在 §6 中我们将推导该电路的增量版本。 **算法 5.3**（递归查询）： 1. 按 §4 与表 1 所述，把非递归的关系查询 $R$ 实现出来；这会产生一个无环电路，其输入与输出都是 ℤ-集合： 原文第 8 页的电路图 ▲ 原文（第 8 页）此处的电路图 其中 $R$ 的两个输入分别是输入关系 I 与递归关系 O，输出仍是 O。 2. 把该电路提升为在流上运算： 原文第 8 页的电路图 ▲ 原文（第 8 页）此处的电路图 我们按照命题 2.4 逐个提升电路中的每个算子来构造 $\uparrow R$。 3. 构造一个环，通过一个延迟把输出连接到相应的递归输入： 原文第 8 页的电路图 ▲ 原文（第 8 页）此处的电路图 4. 先用 $\mathcal{I}$ 与 $\mathcal{D}$ 节点、再用 $\delta_0$ 与 $\int$ 把该电路“括”起来： 原文第 8 页的电路图 ▲ 原文（第 8 页）此处的电路图 图中 [I] 与 [D] 两个方框分别是积分算子 $\mathcal{I}$ 与微分算子 $\mathcal{D}$，左端不带方框的 I 则是输入关系。 我们论证：该电路内部的环迭代地计算 $R$ 的不动点。$\mathcal{D}$ 算子给出循环每一轮迭代所计算出的新 Datalog 事实（即变化）的集合。当新事实的集合变为空时，不动点就已经到达： **定理 5.4**（递归正确性）：若 $\mathit{isset}(I)$，则上述电路的输出是关系 O，它由给定程序 $R$ 的 Datalog 语义定义为输入关系 I 的函数。 注意，如果查询 $R$ 在无界数据域上计算（例如使用带算术的整数），则该构造并不保证运行时一定能到达一个不动点。但如果程序确实收敛，上述构造将找到最小不动点。事实上，该电路实现了标准的**朴素求值**（naïve evaluation）算法（例如见 [21] 中的算法 1）。注意该电路的内层部分是另一个电路的增量形式，因为它被夹在 $\mathcal{I}$ 与 $\mathcal{D}$ 算子之间。利用命题 3.2 的循环规则，我们可以把该电路重写为： 原文第 9 页的电路图 ▲ 原文（第 9 页）此处的电路图 该电路实现了半朴素求值（semi-naïve evaluation，[21] 中的算法 2）。我们刚刚证明了半朴素求值的正确性，它正是循环规则的一个直接推论！ ## 6 增量递归程序 在 §2–4 中，我们展示了如何通过把一个关系查询编译成电路、把该电路提升为在流上计算，再施加 $(\cdot)^\Delta$ 算子，来对它做增量化。在 §5 中，我们展示了如何把一个递归查询编译成一个电路，该电路在内部使用增量计算（半朴素求值）来计算不动点。这里我们把这两个结果结合起来，构造一个增量地求值递归查询的电路。该电路接收输入关系上的更新流，并对每一次更新重新计算不动点。为了增量地做到这一点，它保留迭代式不动点计算所产生的、递归关系的变化流，并根据被修改的输入调整这个流。于是，借助嵌套流，输入流的每一个元素都产生一个对不动点计算的调整流。 嵌套流，即流的流，$\mathcal{S}_{\mathcal{S}_A} = \mathbb{N} \to (\mathbb{N} \to A)$，是良定义的，因为流构成一个阿贝尔群。等价地，嵌套流是 $\mathbb{N} \times \mathbb{N} \to A$ 中的一个值，即一个行数为无限的矩阵，以二维时间 $(t_0,t_1)$ 为索引，其中每一行是一个流。关于嵌套流上的示例计算，请参阅我们的配套报告 [12]。 提升一个流算子 $S : \mathcal{S}_A \to \mathcal{S}_B$ 会得到一个嵌套流上的算子 $\uparrow S : \mathcal{S}_{\mathcal{S}_A} \to \mathcal{S}_{\mathcal{S}_B}$，使得 $(\uparrow S)(s) = S \circ s$；或者按点给出：$(\uparrow S(s))[t_0][t_1] = S(s[t_0])[t_1], \forall t_0,t_1 \in \mathbb{N}$。特别地，一个标量函数 $f : A \to B$ 可以被提升两次，产生一个流之流之间的算子：$\uparrow\uparrow f : \mathcal{S}_{\mathcal{S}_A} \to \mathcal{S}_{\mathcal{S}_B}$。 为了定义递归的嵌套查询，我们需要一个略有不同的严格性定义。如果我们把嵌套流 $F : \mathcal{S}_{\mathcal{S}_A} \to \mathcal{S}_{\mathcal{S}_B}$ 看作时间戳 $(i,j)$ 的函数，那么先前的严格性定义对应于在第一个维度 $i$ 上的严格性；我们在此把它扩展为允许 $F$ 在其第二个维度 $j$ 上是严格的：对任意 $s, s' \in \mathcal{S}_{\mathcal{S}_A}$ 和所有时间 $t \in \mathbb{N}$，$\forall i,j < t.\ s[i][j] = s'[i][j]$ 蕴含 $F(s)[i][t] = F(s')[i][t]$。命题 2.9 在这个扩展的严格性概念下成立，即对严格算子 $F$，不动点算子 $\mathrm{fix}\,\alpha.F(\alpha)$ 是良定义的。 **命题 6.1**：算子 $\uparrow z^{-1} : \mathcal{S}_{\mathcal{S}_A} \to \mathcal{S}_{\mathcal{S}_A}$ 是严格的（在其第二维上）。 嵌套流上的算子 $z^{-1}$ 延迟矩阵的“行”，而 $\uparrow z^{-1}$ 延迟“列”。$\mathcal{S}_{\mathcal{S}_A}$ 上的 $\mathcal{I}$ 算子作用于矩阵的行，把每一行当作一个值。提升一个在 $\mathcal{S}_A$ 上计算的流算子（例如 $\mathcal{I} : \mathcal{S}_A \to \mathcal{S}_A$）也会产生一个嵌套流上的算子，但这次作用于矩阵的列：$\uparrow\mathcal{I} : \mathcal{S}_{\mathcal{S}_A} \to \mathcal{S}_{\mathcal{S}_A}$。 **命题 6.2**（提升环）：对二元、因果的 $T$，有： $$\uparrow(\lambda s.\,\mathrm{fix}\,\alpha.T(s, z^{-1}(\alpha))) = \lambda s.\,\mathrm{fix}\,\alpha.(\uparrow T)(s, (\uparrow z^{-1})(\alpha))$$ 即：提升一个含有“环”的电路，可以通过独立地提升所有算子（包括 $z^{-1}$ 反馈边）来完成。 这意味着提升一个 DBSP 流算子本身可以在 DBSP 内部表达。例如，我们有： ``` i ══▶ [ ↑I ] ══▶ o ``` 与 原文第 9 页的电路图 ▲ 原文（第 9 页）此处的电路图 两者等价（$\cong$）：右图把 $\uparrow\mathcal{I}$ 表示成一个带反馈的累加器，反馈边上是一个 $\uparrow z^{-1}$ 的延迟。 该命题使我们能够提升整个电路，包括在流上计算并且带反馈边的电路——由于命题 6.1，这些电路是良定义的。有了这套机制，我们现在可以把算法 4.6 应用于任意电路，甚至是为递归定义的关系而构造的电路。 **步骤 1**：从“半朴素”电路 (5.1) 出发： 原文第 9 页的电路图 ▲ 原文（第 9 页）此处的电路图 **步骤 2**：无需做任何事（就 distinct 而言）。 **步骤 3 与步骤 4**：提升该电路（利用 6.2）并增量化： 原文第 9 页的电路图 ▲ 原文（第 9 页）此处的电路图 **步骤 5**：应用链式法则以及 $\uparrow\delta_0$ 与 $\uparrow\int$ 的线性性： 原文第 9 页的电路图 ▲ 原文（第 9 页）此处的电路图 这就是任意递归查询的增量版本。传递闭包查询的一个例子见我们的报告 [12]。 ### 6.1 增量递归查询的代价 **时间复杂度**。一个增量递归查询的时间复杂度可以估计为不动点迭代次数与每一轮迭代复杂度的乘积。增量化的电路 (6.1) 执行的迭代次数从不多于非增量电路 (5.1)：一旦非增量电路到达不动点，它的输出就是常量，而增量化的电路中对应值的导数就变为 0。 此外，增量电路中每个算子所做的工作都渐近地少于非增量电路。详细的分析见我们的配套报告 [12]。 **空间复杂度**。对流 $\Delta s \in \mathcal{S}_{\mathcal{S}_A}$ 做积分（$\mathcal{I}$）与微分（$\mathcal{D}$）所使用的内存正比于 $\sum_{t_2}\sum_{t_1}|s[t_1][t_2]|$，即在矩阵的各列上聚合起来的变化总量。未优化的电路分别对递归程序片段的输入和输出做积分与微分。当我们用链式法则把 $\mathcal{I}$ 与 $\mathcal{D}$ 移到电路内部时，我们还会额外存储对中间流的变化。实际上，我们缓存了较早时间戳上不动点迭代的结果，以便在新的输入变化到来时高效地更新它们。注意，空间占用正比于计算不动点的内层循环的迭代次数。幸运的是，许多递归算法在相当少的步数内就收敛（例如，传递闭包所需的步数是 $\log(\text{图直径})$）。 [^5]: 我们只在本图中使用这一约定；一般而言，箭头的类型可以从其源节点的类型推断出来。 [^6]: 一般情形在我们的配套技术报告 [12] 中，只稍微复杂一些。 ## 7 DBSP 与更丰富的查询语言 DBSP 语言能够表达比前文所涵盖的更为丰富的一类流计算（既包括增量式的，也包括非增量式的）。本节我们列举若干重要的查询类别，它们都可以在 DBSP 中实现，因而都能用算法 4.6 增量化。 ### 7.1 多重集（bag） 在 §4 中我们展示了如何在集合上实现关系代数。然而有些 SQL 查询产生的是多重集，例如 `UNION ALL`。由于 ℤ-集合推广了多重集与 bag，在多重集上实现查询算子是很平凡的：只需省略对去重（distinct）算子的调用即可。例如，SQL 的 `UNION` 是先做 ℤ-集合加法再做去重，而 `UNION ALL` 只是 ℤ-集合加法。事实上，§8 中提到的 SQL 到 DBSP 编译器处理完整的标准 SQL，包括所有多重集查询。 ### 7.2 聚合 SQL 中的聚合把一个函数 $a$ 作用于一个类型为 $A$ 的值集合，产生一个具有某个结果类型 $B$ 的“标量”结果：$a : 2^A \to B$。在 DBSP 中，聚合函数具有签名 $a : \mathbb{Z}[A] \to B$。 SQL 的 COUNT 聚合函数在 ℤ-集合上由 $a_{\mathrm{COUNT}} : \mathbb{Z}[A] \to \mathbb{Z}$ 实现，它计算所有元素权重之和：$a_{\mathrm{COUNT}}(s) = \sum_{x \in s} s[x]$。SQL 的 SUM 聚合函数在 ℤ-集合上由 $a_{\mathrm{SUM}} : \mathbb{Z}[\mathbb{R}] \to \mathbb{R}$ 实现，它对所有（实数值）计算加权和：$a_{\mathrm{SUM}}(s) = \sum_{x \in s} x \times s[x]$。这两种实现对于集合与多重集都能正确工作。 按照这一定义，聚合函数 $a_{\mathrm{COUNT}}$ 与 $a_{\mathrm{SUM}}$ 实际上是群 $\mathbb{Z}[A]$ 与结果群（分别为 $\mathbb{Z}$ 与 $\mathbb{R}$）之间的线性变换。 如果允许 DBSP 电路的输出就是这样的“标量”值，那么用线性函数做聚合就只是函数应用，因而是线性的。然而一般来说，组合多个查询要求聚合的结果是一个单元素 ℤ-集合（只含一个值），而不是一个标量值。在这种情况下，DBSP 把聚合函数实现为真正的聚合函数与 $\mathrm{makeset} : A \to \mathbb{Z}[A]$ 函数的复合，后者把类型 $A$ 的标量值转换为单元素 ℤ-集合，定义如下：$\mathrm{makeset}(x) \stackrel{\text{def}}{=} \{x \mapsto 1\}$。 综上所述，以下 SQL 查询：`SELECT SUM(c) FROM I` 被实现为如下电路：[^7] 原文第 10 页的电路图 ▲ 原文（第 10 页）此处的电路图 图中 $\pi_{\texttt{C}}$ 是投影算子，$a_{\mathrm{SUM}}$ 是求和聚合函数，$\mathrm{makeset}$ 把标量结果转换为单元素 ℤ-集合。 这个电路的提升增量版本很有意思：由于 $\pi$ 与 $a_{\mathrm{SUM}}$ 都是线性的，它们等价于各自的增量版本。尽管 $({\uparrow}\mathrm{makeset})^{\Delta} = \mathcal{D} \circ {\uparrow}\mathrm{makeset} \circ \mathcal{I}$ 无法化简，但它仍然是高效的：由于它的输入与输出都是单元素值，每次调用只做 $O(1)$ 的工作。 最后，有些聚合函数（例如 MIN）不是线性的：为了处理删除，它们需要跟踪完整的集合。在 DBSP 中实现这类聚合函数的提升增量版本的一种办法是“暴力”地使用公式 $({\uparrow}a_{\mathrm{MIN}})^{\Delta} = \mathcal{D} \circ {\uparrow}a_{\mathrm{MIN}} \circ \mathcal{I}$。这种实现在每次调用时完成 $O(|DB|)$ 的工作。不过，诸如 Reactive Aggregator [47] 这样的方案可以作为自定义 DBSP 算子来实现，从而把每次更新的摊还代价降到 $O(\log |DB|)$。这种做法类似于去重（distinct）算子的定制实现，它也是 DBSP 模块化的又一个侧面：模块化允许把经过优化的算子实现混合搭配使用。 ### 7.3 分组；带索引的关系 设 $K$ 是一个“键值”的集合。考虑从 $K$ 到 ℤ-集合的有限映射这一数学结构：$K \to \mathbb{Z}[A] = \mathbb{Z}[A][K]$。我们把该结构的取值 $i$ 称为带索引的 ℤ-集合（indexed ℤ-set）：对每个键 $k \in K$，$i[k]$ 是一个 ℤ-集合。由于陪域 $\mathbb{Z}[A]$ 是阿贝尔群，这个结构本身也是阿贝尔群。 我们用这个结构在 DBSP 中实现 SQL 的 GROUP BY 算子。考虑一个分区函数（partitioning function）$p : A \to K$，它把 $A$ 中的任意值赋予一个键。我们定义分组函数 $G_p : \mathbb{Z}[A] \to \mathbb{Z}[A][K]$ 为 $G_p(a)[k] \stackrel{\text{def}}{=} \sum_{x \in a.\,p(x)=k} a[x] \cdot x$（即把输入 $a$ 的每个元素映射到其键所对应的 ℤ-集合分组）。当作用于一个 ℤ-集合 $a$ 时，该函数返回一个带索引的 ℤ-集合，其中每个元素是一个分组：[^8] 对每个键 $k$，分组是一个 ℤ-集合，包含 $a$ 中所有映射到 $k$ 的元素（与 SQL 中一样，分组是多重集）。考虑 §4 中我们的示例 ℤ-集合 $R$，以及返回字符串 $s$ 首字母的键函数 $p(s)$。于是有 $G_p(R) = \{\text{j} \mapsto \{\text{joe} \mapsto 1\}, \text{a} \mapsto \{\text{anne} \mapsto -1\}\}$，也就是说，用这个键函数分组产生一个带索引的 ℤ-集合，它有两个分组，其中每个分组都包含一个只有一个元素的 ℤ-集合。 对任意键函数 $p$，分组函数 $G_p$ 都是线性的！由此可知，DBSP 中的 group-by 实现自动就是增量的：给定对输入关系的一些变化，我们可以对输入中发生变化的每一行分别应用分区函数，从而计算出每个分组如何变化。 注意，与 SQL 不同，DBSP 可以自然地表达在带索引的 ℤ-集合上的计算，它们不过是群结构的一个实例。在 DBSP 中不必让分组后面跟着聚合，而且 DBSP 可以表示任意深度的嵌套分组。我们对增量计算的定义只关心最外层结构上的增量性。至于如何在内部关系上定义恰当的增量计算，我们留待未来工作探索。 ### 7.4 GROUP BY-AGGREGATE 与展平映射（flatmap） SQL 中的分组几乎总是后面跟着聚合。考虑一个聚合函数 $a : (K \times \mathbb{Z}[A]) \to B$，它在某个群 $B$ 中产生值；并考虑如上文 §7.3 所定义的类型为 $\mathbb{Z}[A][K]$ 的带索引的关系。嵌套关系聚合算子（nested relation aggregation operator）$Agg_a : \mathbb{Z}[A][K] \to B$ 把 $a$ 独立地作用于每个分组的内容，再把结果相加：$Agg_a(g) \stackrel{\text{def}}{=} \sum_{k \in K} a(k, g[k])$。 为了把这个算子应用到我们的示例上，我们来计算 GROUP BY-COUNT 的等价物；我们使用如下聚合函数 $count : K \times \mathbb{Z}[A]$，$count(k, s) = \mathrm{makeset}((k, a_{\mathrm{COUNT}}(s)))$，其中用到 §7.2 的 ℤ-集合计数函数 $a_{\mathrm{COUNT}}$；记号 $(a, b)$ 表示值 $a$ 与 $b$ 构成的二元组。于是有 $Agg_{count}(G_p(R)) = \{(\text{j}, 1) \mapsto 1, (\text{a}, -1) \mapsto 1\}$。 嵌套关系上一个非常有用的操作是展平映射（flatmap），也就是 SQL 中的展开（UNNEST），它本质上是分组的逆操作，把一个带索引的 ℤ-集合转换为一个 ℤ-集合：$\mathrm{flatmap} : \mathbb{Z}[A][K] \to \mathbb{Z}[A \times K]$。flatmap 实际上是聚合的一个特例，它使用的聚合函数 $a : K \times \mathbb{Z}[A] \to \mathbb{Z}[A \times K]$ 定义为 $a(k, s) = \sum_{x \in s[k]} s[k][x] \cdot (k, x)$。对于前面的示例，$\mathrm{flatmap}(G_p(R)) = \{(\text{j}, \text{joe}) \mapsto 1, (\text{a}, \text{anne}) \mapsto -1\}$。 ### 7.5 流连接 考虑一个二元查询 $T(s, t) = \mathcal{I}(s)\;{\uparrow}\!\bowtie\;t$。这是 ksqlDB [31] 这类流式数据库所支持的关系-流连接（relation-to-stream join）算子。流 $s$ 携带对一个关系的变化，而 $t$ 携带任意数据，例如日志或遥测数据点。$T$ 把 $t$ 中的值与关系 $I(s)$ 的累积内容进行匹配，匹配之后就把这些值丢弃。 **流式窗口查询（Streaming Window queries）。** 流式数据库常常把流的内容组织成窗口，窗口存储具有预定义时间戳范围的一个数据点子集。在实践中，窗口划分通常基于附加在流值上的物理时间戳，而不是像前一个电路那样基于逻辑（事务）时间。例如，CQL [9] 查询 `SELECT * FROM events [RANGE 1 hour]` 返回过去一小时内收到的所有事件。相应的电路（左图）以流 $s \in \mathcal{S}_{\mathbb{Z}[A]}$ 为输入，并另有一个输入 $\theta \in \mathcal{S}_{\mathbb{R}}$ 携带当前时间的值。 左图： ``` s ──▶ [ I ] ──▶ [ W ] ──▶ o ▲ θ ────────────────┘ ``` 右图（与之等价）： 原文第 11 页的电路图 ▲ 原文（第 11 页）此处的电路图 左图中关系变化流 $s$ 先经积分算子 $\mathcal{I}$ 累积，再经窗口算子 $W$ 修剪；右图把 $W$ 移入积分环路内部：$s$ 与延迟反馈 $z^{-1}$ 相加后进入 $W$，$\theta$ 直接作为 $W$ 的第二个输入，因而只需有界内存。 其中窗口算子 $W$ 修剪输入的 ℤ-集合，只保留时间戳比 $\theta[t]$ 落后不到一小时的取值。假设 $ts : A \to \mathbb{R}$ 返回一个值的物理时间戳，则 $W$ 定义为 $W(v, \theta)[t] \stackrel{\text{def}}{=} \{x \in v[t].\ ts(x) \geq \theta[t] - 1\mathrm{hr}\}$。假设 $\theta$ 单调增长，$W$ 就可以被移到积分内部，从而得到右图电路，它用有界内存计算一个无界流的窗口。这个电路是包括窗口连接与窗口聚合（例如 SQL 的 OVER 查询）在内的一大类窗口查询的构件。 ### 7.6 关系 while 查询 DBSP 能够表达超出 Datalog 的程序：参见 Datalog$^{\neg}$ 与 Datalog$^{\neg\neg}$ 的非单调语义 [5]。我们实现如下“while”程序，其中 $Q$ 是任意查询： ``` x := i; while (x changes) x := Q(x); ``` 该程序的 DBSP 实现为： 原文第 11 页的电路图 ▲ 原文（第 11 页）此处的电路图 其中 $\delta_0$ 是流引入算子，${\uparrow}Q$ 是提升后的查询 $Q$，$\mathcal{D}$ 与 $\int$ 分别是微分与积分算子，$z^{-1}$ 是延迟算子；反馈边把 ${\uparrow}Q$ 的输出送回加法节点。 这个电路可以通过提升转换为计算值 $i$ 的流的流式电路；并且可以用算法 4.6 增量化，以在 $i$ 的变化上进行计算： 原文第 11 页的电路图 ▲ 原文（第 11 页）此处的电路图 其中每个算子都是前一个电路中对应算子的（提升后的）增量版本，$(\uparrow\uparrow Q)^{\Delta}$ 是对提升两次的查询再取增量。 在运行时，该电路的执行不保证终止；不过，如果该电路确实终止，它就会产生正确的输出，即 $Q$ 包含 $i$ 的最小不动点。 [^7]: 实际的 SQL SUM 聚合甚至更复杂，因为它需要跳过 NULL，并且对空输入集返回 NULL；这一点可以在 DBSP 中实现。 [^8]: 我们用“群”表示代数结构，用“分组”表示 GROUP BY 的结果。 ## 8 实现 本文的范围是 DBSP 的 IVM 理论，因此我们只简要涉及实现方面。我们将系统的完整描述与评估留待后续论文。 **DBSP Rust 库。** 我们已作为采用 MIT 许可的开源项目构建了 DBSP 的一个实现：https://github.com/vmware/database-stream-processor。该实现由一个 Rust 库和一个运行时组成。该库为基本代数数据类型提供 API：例如群、有限映射、ℤ-集合（Z-set）、带索引的 ℤ-集合。一个单独的电路构造 API 允许用户通过放置算子节点（对应我们图中的方框）并用流将它们连接起来创建 DBSP 电路，其中流对应我们图中的箭头。该库提供预置的通用算子，用于积分、微分、延迟、嵌套积分与微分，以及一个丰富的 ℤ-集合基本增量算子库：分别对应加、取负、分组、连接、聚合、去重、展平映射（flatmap）、窗口聚合等。对于迭代计算，该库提供 $\delta_0$ 算子，以及一个通过在用户指定条件下终止循环迭代来近似 $\int$ 的算子（通常该条件是要求某个指定流中出现零）。底层库允许用户通过把各基本算子的增量版本拼接起来，手工构造增量电路。该库支持采用一种自然的分片策略对电路进行数据并行的多核求值，并提供多种面向外部数据源（例如 Kafka、CSV 文件等）的适配器。该库还能把算子的内部状态溢写到持久化存储。基准测试结果（非常有前景）可在代码仓库中获得，并将在后续工作中讨论。 **SQL 编译器。** 我们还构建了一个 SQL 到 DBSP 的编译器，它把标准 SQL 查询翻译成 DBSP 电路。该编译器实现了算法 4.6，为任意 SQL 查询生成流式版本。该编译器是开源的，采用 MIT 许可：https://github.com/vmware/sql-to-dbsp-compiler。编译器的前端解析器与优化器基于 Apache Calcite [10] 基础设施。该项目足够成熟，能够通过全部 700 万条 SQL Logic Tests [2]。该编译器处理 SQL 的各个方面，包括 NULL、三值逻辑、分组、聚合、多重集查询等。目前，相关子查询与外连接实质上是使用多个连接转换为等价的关系计划。 **形式化验证。** 我们使用 Lean 定理证明器对本论文中的所有定义、引理、命题、定理与例子进行了形式化并加以验证；我们把这些证明公开在 [14]。该形式化工作构建在 mathlib [37] 之上，后者提供对群以及具有有限支撑的函数（用于建模 ℤ-集合）的支持。我们相信，正是 DBSP 的简洁性使得这些证明能够以相对较少的 Lean 代码行数（5K）完成，并在 [12] 中的论文证明与 Lean 形式化之间保持密切的对应关系。 ## 9 相关工作 增量视图维护 [15, 16, 24–26] 是数据库领域一个被大量研究的问题。针对 Datalog 查询的结果综述见 [40]。标准方法如下：给定一个查询 $Q$，找出一个“增量查询”（delta query）、即满足方程 $Q(d + \Delta d) = Q(d) + \Delta Q(d, \Delta d)$ 的“微分”版本 $\Delta Q$，它可用于在复用先前输出的同时计算新输入所带来的变化。DBToaster 提出了递归式 IVM（recursive IVM）[6, 33]，其中增量化过程会针对增量查询反复执行。 针对各类查询，人们发表了许多定制算法：例如 [34] 处理正嵌套关系演算。DYN [28] 与 IDYN [29, 30] 关注无环合取查询。它们并不把输出视图保持为物化状态，而是构建能够高效查询输出视图的数据结构。PAI maps [4] 专门为带相关聚合的查询设计。AJU [48] 关注外键连接。定制的 DBSP 算子能否达到为窄类查询专门设计的系统的效率，尚待未来工作评估。 DBSP 是一个自底向上的系统，它总是急切地（eagerly）产生输出视图的变化。DBSP 不是完整地维护输出视图，而是提出把增量作为计算的输出产生（类似于 kSQL [31] 的 `EMIT CHANGES` 查询）。IVM 系统的输入与输出都是变化流，这一想法看起来平凡，但它对我们解决方案的对称性至关重要：它既体现在我们对 IVM 的定义（3.1）中，也是链式法则存在的根本原因——正是链式法则使我们的结构归纳 IVM 算法成为可能。 若干针对类 Datalog 语言的 IVM 算法采用基于计数的做法 [19, 41]，维护每个输出事实的推导（derivation）次数：DRed [26] 及其变体 [8, 13, 35, 36, 46, 49]，以及后向-前向算法及其变体 [27, 40, 41]。DBSP 更为一般，我们的增量化算法能处理任意递归查询，并且在存在任意更新（尤其是删除，竞争方法可能会过度删除）的情况下为递归查询生成更高效的执行计划。有趣的是，DBSP 中的 ℤ-集合权重与按推导次数计数的方法相关，但我们使用去重（distinct）算子表明精确计数并非必要。 Picallo 等人 [7] 为富语言中的 IVM 提供了一种通用解决方案。DBSP 要求所操作的值上具有群结构；这一假设有两个主要的实际好处：它极大地简化了数学（例如 Picallo 用幺半群作用（monoid actions）来建模变化），并提供了一个通用而简单的算法（4.6）来增量化任意程序。DBSP 的缺点在于，必须找到一个合适的群结构（例如对集合使用 ℤ-集合）来“嵌入”计算。Picallo 的“导数”（derivative）概念并不唯一：他们需要创造力来选出正确的导数定义，我们需要创造力来找到正确的群结构。 事实证明，为关系找到合适的群结构很容易（[33] 与 [22] 都用 ℤ-集合来统一地建模数据与插入/删除），但对于其他数据类型，例如有序集合或树状集合（如 XML 或 JSON 文档）[20]，如何做到这一点并不显然。一个耐人寻味的问题是：“除 ℤ-集合之外，这一方法还能应用到哪些其他有趣的群结构？”诸如 [43] 的论文探索了其他可能性，例如矩阵代数、线性机器学习模型或合取查询。 DBSP 对三角形查询（triangle queries）[32] 没有做任何特殊处理。这一情形是否存在更好的算法？ 在 §7 中我们简要提到，DBSP 可以很容易地建模窗口与流数据库查询 [1, 9]；是否存在无法用 DBSP 表达的 CQL 查询，是一个有趣的问题（我们猜想不存在这类查询）。 Bonifati 等人 [11] 为称为 Regular Datalog 的一类特定图查询实现了一种经过验证的 IVM 算法，其实现用 Coq 证明助手进行了机器检验。他们关注的是某个特定算法，其方法没有考虑其他 SQL 算子、一般递归或定制算子（尽管它是模块化的，即通过对任意查询递归地进行增量化来工作）。此外，对所有查询而言，输入变化流中的一次删除都需要运行非增量查询才能恢复。我们对本文中的定理进行了形式化验证，这些定理的范围要广得多，但我们没有验证自己的实现。 DBSP 也与差分数据流（Differential Dataflow, DD）[39, 42] 及其理论基础 [3]（以及近期的 [17, 38]）相关。DD 的计算模型比 DBSP 更强大，因为它允许时间值是任意格（lattice）的一部分。事实上，在我们所知的其他框架中，DD 是唯一能像 DBSP 这样高效地增量化递归查询的框架。相比之下，我们的模型要么使用“线性”时间，要么通过模块化提升变换器（${\uparrow}$）使用嵌套时间维度。DBSP 既能表达增量计算，也能表达非增量计算。最重要的是，DBSP 附带算法 4.6——一种语法导向的翻译，能把任何可表达的查询转换为增量版本；而在 DD 中，用户必须使用增量算子手工组装增量查询。（materialize.com 提供了一个基于 DD、为 SQL 查询自动完成增量化的产品。Differential Datalog [45] 则针对一种 Datalog 方言做到这一点。）与 DD 不同，DBSP 是一种模块化的理论，能够轻松容纳新算子的加入：只要能把一个新算子表达为 DBSP 电路，我们就可以 (1) 定义其增量版本，(2) 应用增量化算法得到高效的增量实现，并且 (3) 确信它能与任何其他算子组合。 ## 10 结论 我们提出了 DBSP，一种基于阿贝尔群上无限流的计算模型。在该模型中，流用于 3 个目的：(1) 为数据库的连续快照建模；(2) 为施加到数据库上的连续变化（增量或事务）以及被维护视图的变化建模；(3) 为递归计算中循环携带变量的连续取值建模。 我们定义了流上增量计算的抽象概念，并定义了增量化算子 ${\cdot}^{\Delta}$，它把任意流计算 $Q$ 变换为其增量版本 $Q^{\Delta}$。增量化算子具有一些非常好的代数性质，这些性质为我们提供了一个通用算法，可对许多类复杂查询（包括任意递归查询）进行增量化。 我们相信，DBSP 能够为流式增量计算的理论与实践奠定坚实的基础。