[1] 是另一篇关于物化视图维护的维护计划的研究工作。但和之前的工作 [2] 不同的是，[1] 没有考虑对不同的输入采取不同的维护计划，而是对一个视图中的不同算子使用不同的维护计划。[1] 分析了不同算子的增量计算能力，使用动态规划给出了一个视图维护的维护计划。

之前的物化视图维护中，我们一般不会区别对待不同表的更新。但 [1] 注意到，不同表的更新会导致不同的物化视图维护开销，因此应该对这些更新使用不同的调度策略来使得整体的维护开销最低。对于维护开销和输入数据量成线性关系的更新，我们可以尽可能地实时维护来降低在查询时的延迟；而对在维护时需要扫描全表的这类更新，我们则在保障查询延迟的前提下尽可能地推迟视图的维护。[1] 对视图维护中不同输入更新的调度策略进行研究，提出了两个有效的算法。

Kraken [1] 是Meta用于取代Scuba的下一代监控分析平台，用于解决Scuba在一致性和可靠性等方面的问题。Kraken一个独特的设计在于使用消息中间件来存储所有的元数据变更，避免分布式环境下进行并发控制的困难。

Napa [1] 是Google内部由于取代Mesa的下一代数据分析系统。相比于Mesa，Napa提供了更加便捷的配置方式来满足用户在数据时效性、查询延迟和资源开销这三方面不同的选择，通过查询时间戳提供了更好的数据一致性；并且支持SQL定义的视图和索引。

Procella是Youtube新一代的SQL处理引擎 [1]，其能够支持批式和实时的数据导入，并为不同的分析场景提供统一和高效的数据查询服务。

Misra-Gries算法最早由J. Misra和D. Gries在1982年提出 [1]。Misra-Gries算法可以看成是对Majority算法的一个扩展，可以对数据流中的频数提供相对误差为$\epsilon$的估计，使用的空间复杂度为$\mathrm{O}(1/\epsilon)$。

为了保证与数据源的一致性，当数据源发生变化时，物化视图需要进行及时的更新。很多时候，数据源的变化相比于整体而言是较小的。此时使用增量更新的方式来对物化视图进行维护会更加高效。本文主要介绍维护物化视图的代数方法。这些方法可能在某些算子上无法提供最高效的维护方法，但在语义上比较直观。

LossyCounting是R. Motwani和G. S. Manku在[1]中提出的另一个频数估计算法（该论文中的另一个算法为 Sticky Sampling算法）。虽然LossyCounting算法在Misra-Gries算法提出之后20年提出，但LossyCounting算法在估计误差上和Misra-Gries算法是一样的，在空间复杂度和计算复杂度上还不如Misra-Gries算法。

StickySampling是R. Motwani和G. S. Manku在2002年提出的一种基于采样的频繁项估计算法 [1]。在原始论文中，作者号称它能够对数据项的频数以超过$1-\delta$的概率提供相对误差为$\epsilon$的估计，并返回数据流中所有频率超过给阈值的所有数据项，其所需的空间复杂度为$\mathrm{O} \left( \log \frac{1}{\epsilon \delta} \right)$。但这个结论的证明可能存在问题。

MorrisCounter算法是R. Morris于1978年提出的一种用于估计频数的算法 [1]. 当时Morris需要编写一段代码来对大量事件进行计数，但是他能使用的只有一个8位的计数器。为了能在有限的存储空间内完成任务，他发明了MorrisCounter算法，能够使用 $ O(\log \log N + \log 1/ \epsilon + \log 1 / \delta ) $个比特，对频数进行估计，并且保证估计频数$\hat{f}$和真实频数$f$之间满足：