“用ΔV准备可删除聚合的候选G'和摘要变化；它失败时仍不发布”
形式陈述
输入变化和输出变化不是同一种数
本页接收整批带符号变化。输入是有限bag
每个当前非空组保存状态
频数表只存
这行的bag重数是1，列里的n不是它自己的重数。金额可以为负或零；组是否存在由n决定，不能由s是否为零决定。
设旧、新摘要行分别为a、a'。输出变化是
一个可准备、可拒绝的状态转换
先按组收集本批已合并的ΔB。只为受影响组复制频数表及n、s；对一个不同金额x的净权d：
- 核
- 令
- 令
- 全组变化处理完后，若
本组是否空和新MIN只能在整批金额变化结清后决定。随后把旧摘要撤回、新摘要插入合并到候选输出。所有组均验证成功，才把候选状态及输出差分交给同一个发布步骤；准备函数不修改旧组，后面某组失败不会留下前面组已生效的半批结果。
输入按金额已合并，所以对每个x只核一次最终频数。这一条件与上页整批净变化合同一致，不约束原SQL事务内部省略掉的语句顺序。下游把本批完整摘要差分合并到相同旧版本，才得到新聚合结果；任意截断输出前缀都不是完整事务答案。
频数如何使删除可判定
distinct只在频数跨越0时改变。对受影响金额，可计算
若旧频数3、净删1，新频数2，该金额仍算一个distinct值。MIN也只有在知道剩余值后才可确定。参考器保留完整的不同值频数表，逐组扫描正频数的键求最小值；它没有假装一个MIN标量能恢复被删最小值之后的次小值。[1，§§4.3、7.2–7.4；2，§5]
直觉
可加状态像账本的累计列：删一笔金额20，就从总和减20、从份数减1。但是报表上“这一组的平均金额25”是一条新的结果行。更改这行需要先收回旧答案，再交付新答案，不能把金额变化当成答案的复制次数。
频数表则回答删除最常见的疑问：“这个值真的已经没有了吗？”同一金额有两份时，删掉一份不会改变最小值或不同值数；最后一份消失时，才需要寻找下一个值。允许任意删除后，一个看上去很小的聚合结果可能需要保留远比结果更多的状态。
例子与边界
同一批差分怎样更新五列摘要
共同任务初始结果有三组。以下顺序固定为(n,sum,avg,distinct,min)：
| 分组 | 旧摘要 | 批1后摘要 |
|---|---|---|
| a/hot | (6,100,50/3,2,10) | (3,60,20,3,10) |
| a/sale | (3,50,50/3,2,10) | (6,120,20,3,10) |
| b/sale | (1,5,5,1,5) | 不变 |
| c/sale | 不存在 | (1,7,7,1,7) |
以a/hot逐金额核算。旧频数为10→4、30→2；连接差分给10→−3、20→+1、30→−1。新频数因此为10、20、30各1。份数变化
输入删掉了若干出现，不同值数反而从2增到3，因为增加了新金额20，而10和30都还存在。不能根据本批总份数为负就断言distinct也减少。
输出对a/hot撤回旧的七列行(a,hot,6,100,50/3,2,10)，插入(a,hot,3,60,20,3,10)，两项权分别−1、+1。a/sale同样两项，c/sale只加一项，b/sale无项。于是批1摘要变化共五个非零元组，不是按输入的净行数+1复制某一旧摘要。
删除最后一份10，再删除整个hot组
批2从Orders删除最后一份(a,p,10)。此时hot标签重数为1，sale标签为2，所以聚合输入撤回(a,hot,10)一份、(a,sale,10)两份。两组中的10都变成0频数，删除该键。
新的a/hot只含20、30各一份，状态为(2,50,25,2,20)；a/sale含20、30各两份，状态为(4,100,25,2,20)。两个MIN都从10变成20，两个distinct都从3变成2。若sale侧只撤回一份10，就会错误留下一个最小值10；上游连接的重数与下游频数必须对齐。
批3删除最后一份(p,hot)标签，上游给a/hot金额20、30各−1。该组n归零，频数表为空，聚合结果只发出旧摘要行的−1撤回，随后不再保存a/hot组。a/sale、b/sale、c/sale三组不受影响。
只存一个数会丢掉什么
只保存MIN的两个组{1,2}与{1,3}有同样状态1；同样删除1后，新MIN分别为2、3。相同旧状态和相同更新要求不同新答案，已经证明单一MIN不够。
即使还保存n、sum、distinct，也未必足够。两组{1,2,5}与{1,3,4}的(n,sum,distinct,min)同为(3,8,3,1)，删除1之后的最小值却为2和3。必须保留更丰富的有序信息或允许重新访问底层数据；本页选择不同值频数表。
两个平均值相同的组也不等价。{10}与{10,10}的AVG都为10，同样新增20后平均分别15和40/3。因而AVG不能单独作可逆累计器；n、sum按带符号贡献更新后再相除，才保留所需信息。
空组、零和与净零变化
组{−5,5}的sum=0，n=2，仍要输出摘要(2,0,0,2,−5)。删去最后一份输入才使普通GROUP BY组消失。不能把“总和变0”当成组不存在。
全局聚合需要另外的输出约定。本页沿用数学版本：空输入仍保留唯一空键，COUNT=0、SUM=0、AVG和MIN未定义、distinct=0；程序用None表示两个未定义值。这个全局辅助入口与普通按键聚合的“没有组就没有行”不同，也不是SQL空SUM返回NULL的逐字实现。含NULL的COUNT(*)、COUNT(列)与SUM请沿用既有相关聚合合同，不能直接套这里无NULL的一份一计。
净零输入变化合并后为空，不需要处理任何组。更一般地，组的内部值可能变化而当前输出摘要碰巧相同；旧行与新行会相消，但内部频数仍须更新，否则下一次删除会使用过时状态。有没有输出变化不能决定要不要更新内部状态。
推论与应用
状态不变量与输出保持
初始化时逐份或按重数累加输入，频数等于每个(g,x)的真实出现数，n和sum分别为频数和、加权和。假设批前成立，一次金额净变化d同时给频数加d、n加d、sum加xd，因此三个等式逐项保持。未受影响组不改；全部变化合并完成时，频数正好对应新输入bag。合法性核查排除负频数，零项删除不改变任何和。
由非负性，n=0当且仅当频数表为空；因此分组存在判断正确。n>0时，s/n、频数键数与最小键分别就是AVG、distinct与MIN的定义。对每个组，旧结果加上“撤旧、加新”恰好等于新结果；不变行相消，创建与消失也分别符合一侧为空的情况。对有限组求和，便得到整张聚合视图的正确差分。
准备失败不触碰已发布字典，所以不需要尝试反向执行一串已经对外可见的摘要事件。与上页的唯一发布点组合，基表、连接结果和聚合结果在每个成功版本都一致；这个归纳只覆盖所规定的串行内存输入，不声称故障后可以从任意截断日志自行恢复。
不同聚合需要多少额外状态
只维护无NULL的COUNT/SUM/AVG，在已可信验证的输入差分下，每组两个数足够。若还要独立验证“某个金额是否删过头”，就需要能回答逐值剩余数的状态或下层证书；仅检查n非负会漏掉“删不存在的99、同时新增1”的错误。
本页为了精确distinct、可删除MIN及逐值验证，保留每组的不同金额频数。大量重复金额能压缩：一百万个10只需一项频数；一百万个互异金额则要一百万项。结果只有一行，不意味着维护空间也是常数。删除所有频数后可以释放该组；如果外部读者仍持有旧快照，旧副本的释放还要服从它自己的所有权合同。
参考实现的扫描成本
公开参考器的prepare_groups接收已正规化差分与合法旧状态。组索引和金额频数用散列表，保留完整键比较。设ΔB有D个非零(g,x)项，当前有g个组，受影响组旧、新不同金额总数为U、U'。它先读D项分组，复制g项组索引，再复制受影响的U项频数；逐金额更新后，对旧、新摘要各求一次MIN。
在固定字长和期望常数散列表访问前提下，时间为
可以把频数放进支持插删和最小值查询的平衡搜索树，以按不同值数计的对数更新替换扫描；还须选择可回滚或持久化候选的方式。本附件没有实现那种树，不引用其成本作为当前程序的性能。若只看一行金额变化就声称所有聚合都O(1)，正好忽略了最小值删除所需的搜索。
同批视图终点把三次真实变化、非法删除、净零内部变化和自连接交叉项放在同一任务中。逐批全量重算可以做有限oracle；一般正确性由频数不变量和行撤回等式给出。
参考资料
- [1] Mihai Budiu、Tej Chajed、Frank McSherry、Leonid Ryzhyk、Val Tannen，DBSP: Automatic Incremental View Maintenance for Rich Query Languages，PVLDB16(7)，2023，§4.3 Proposition4.7（PDF第6页），§§7.2–7.4（PDF第10–11页）：distinct的零界变化、可加标量与singleton结果行的区别、MIN删除及分组。本文使用显式非负频数和普通空组删除，不照搬任意负权嵌套组的显示约定。
- [2] Timothy Griffin、Leonid Libkin，Incremental Maintenance of Views with Duplicates，SIGMOD1995，§5，印刷p.335/PDF第8页：增删后更新计数/总和、AVG需要的状态，以及删去最小值的额外信息。本文的五列摘要、全批候选发布与后续反例是自定有限任务。