带符号重数的批量视图维护

形式陈述

快照非负，变化可以为负

多重集关系用非负整数记录每个元组的份数。本页把中间运算扩到整数：一个带符号关系是有限支撑函数 $X:U\to\mathbb Z$ ， $X(t)$ 是元组t的权重；未存储的元组权为0，合并后权为0的项可以删除。两个关系逐元组相加，负号也逐元组作用。它们通常称为Z-set或整数标注关系。

基表快照仍要求 $R(t)\ge0$ 。一批净变化 $\Delta R$ 可以含负权，新的合法快照为 $R'=R+\Delta R\ge0$ 。例如旧重数3加−2得到1；加−4则拒绝。本页的输入是整批净变化，不是按序执行的SQL语句。先删2再加1与净删1在此表示中相同，接口不负责验证被省略的语句中间状态。一个外部事务若要求逐语句约束，必须在形成这批输入之前检查。

固定有限、无NULL的两张表和纯、确定、总定义的连接谓词 $\theta$ 及投影p。允许相同值的多份出现，不承诺输出顺序。把连接后投影记为J：

J(R,S)(z)=\sum_{r,s:\theta(r,s),\ p(r,s)=z}R(r)S(s).

求和只需两表有限支撑上的配对。相同输出z由不同配对产生时，相加其贡献；不要用集合去重。这个定义也适用于带负权的中间关系，但基表和已发布查询结果仍是非负bag。

两侧同时改变时的完整差分

设 $V=J(R,S)$ 。对同一批中的 $\Delta R,\Delta S$ ，有

\Delta V=J(\Delta R,S)+J(R,\Delta S)+J(\Delta R,\Delta S), \qquad V'=V+\Delta V.

三项中的R、S全部取批前快照。第三项修正两边都发生变化的配对：两个新出现会相遇，两个删除也会互相抵消一次重复扣除。它不是可忽略的“高阶小量”，因为本页没有无穷小参数。

同一公式可写成两项的顺序形式：

\Delta V=J(\Delta R,S)+J(R+\Delta R,\Delta S).

这里第二项必须用更新后的左表。若两项都用旧表，会漏第三项；若第二项已用新左表却又额外加一次交叉项，则重复计入。两种正确写法给相同净变化，不要求内部每一步都成为可见数据库快照。[1，Theorem3.4]

选择、重命名和bag投影是线性的。例如投影满足 $\pi(X+Y)=\pi X+\pi Y$ ，因为相同输出下的有限和可逐项分配。因此可以先算完整连接变化再投影，也可以像J一样在产生配对时直接累加投影结果。DISTINCT、外连接补行和一般聚合需要另外的状态规则，不能因同样写成一个查询算子就套用这条线性等式。

一次发布对应一批完整输入

参考器维护一个已发布状态 $(e,R,S,V,G)$ ，e为批次版本，G是后续聚合状态。调用者提交期望旧版本e及两侧净变化；单个管理器串行执行以下步骤：

核期望版本，读取并合并本批所有输入项，检查元组列和整数权重
在候选副本上形成R'、S'；任一最终重数为负便拒绝整批
从同一旧R、S计算三项，合并成一份ΔV，再形成非负候选V'
用ΔV准备可删除聚合的候选G'和摘要变化；它失败时仍不发布
完成所有候选与返回记录后，一次替换状态引用为 $(e+1,R',S',V',G')$

发布前的读者只观察旧状态，发布后观察新状态。这里“原子”来自已声明的串行调用及唯一发布点，是内存教学接口；不包含磁盘持久化、多线程竞争、网络重试或分布式提交。状态内部字典不得被调用者直接修改。期望版本不匹配会拒绝调用，但不能由此推导消息系统已经实现恰好一次交付。

直觉

一张维护中的报表不必每次重新展开全部订单。它可以接收“这一行少三份、那一行多两份”，把这些变化合并到旧报表。但只要两张输入表一起变，旧表与新表的配对方式就要统一；把“新订单找旧标签”和“新标签找旧订单”各做一次，仍可能漏掉新订单与新标签彼此相遇。

负数在这里是一张撤回单，不是数据库里存在“负三个订单”。计算暂存的撤回单可以相加、相消；只有把整批单据结清之后，才能问新快照的每一行是否还有合法份数。

三项差分各用明确的旧表或变化表，投影后合并再发布；双删时正交叉项防止扣两遍 — 同批变化的三项账本

例子与边界

一批订单和标签的共同变化

Orders的列为(customer,product,amount)，Tags为(product,tag)。旧输入的不同元组及重数为：

Orders元组	重数	Tags元组	重数
(a,p,10)	2	(p,hot)	2
(a,p,30)	1	(p,sale)	1
(b,q,5)	1	(q,sale)	1

按product相等连接，投影到(customer,tag,amount)。旧结果有(a,hot,10)×4、(a,hot,30)×2、(a,sale,10)×2、(a,sale,30)×1、(b,sale,5)×1，共10份，金额合计155。

批1对Orders删一份(a,p,10)，插入(a,p,20)和(c,r,7)；对Tags删一份(p,hot)，插入(p,sale)和(r,sale)。把三项逐输出元组列齐：

输出元组	J(ΔR,S)	J(R,ΔS)	J(ΔR,ΔS)	净变化
(a,hot,10)	−2	−2	+1	−3
(a,hot,20)	+2	0	−1	+1
(a,hot,30)	0	−1	0	−1
(a,sale,10)	−1	+2	−1	0
(a,sale,20)	+1	0	+1	+2
(a,sale,30)	0	+1	0	+1
(c,sale,7)	0	0	+1	+1

(a,hot,10)的新重数是 $4-3=1$ ，直接重算也得 $1\cdot1=1$ 。(a,sale,10)重数仍是2：左侧从2降到1，右侧从1升到2，乘积不变。新r键在两边旧快照中都没有，只能由交叉项产生(c,sale,7)。

新结果的a/hot金额10、20、30各一份；a/sale三种金额各两份；b/sale仍一份5；c/sale新增一份7。总份数11、总金额192。净份数只加1，却包含多种插入和撤回，不能只给聚合器传一个总行数差。

双删为何产生一个正项

最小例只有一对能匹配的R、S，旧重数都为1，同批各删1。三项在唯一输出上的值为−1、−1、+1，净变化−1，正好把旧输出1变成0。

若先从旧输出扣第一项、再扣第二项，临时重数会到−1；这不说明合法批次有错，因为三项不是三个独立提交。若把每一步负数截成0，最后再加+1，就会错误留下一个结果。正确做法是保存整数中间量，合并整批后再检查非负性。

程序中的字典累加显式保留负数。某些多重集库的加法运算默认丢掉非正项，用这种“正bag并”替代整数加法，会使撤回在进入连接前就消失。

失败、重放与自连接

在批3完成后请求删除不存在的(a,p,99)，新Orders重数为−1，参考器抛出拒绝异常，旧版本、两基表、连接和摘要全部保持不变。另一种失败是带旧e提交：即使变化为空也拒绝；空变化若携带当前e则是合法批，推进版本但不产生结果差分。

如果一张物理表在自连接中出现两次，仍有两个逻辑输入槽。把两槽都替换为 $R+\Delta R$ 后，必须保留 $J(\Delta R,\Delta R)$ 。例如一个相同值有2份，配对自身得到4份；新增1份后应得到9份，变化为 $2+2+1=5$ 。去掉最后一项只得到8。这里允许同一出现与自身配对；若业务禁止它，须把出现身份与不等条件一起写入查询合同。

推论与应用

三项公式及整批不变量

对任意输出z，把新连接展开：每对输入的贡献为 $(R(r)+\Delta R(r))(S(s)+\Delta S(s))$ 。整数分配律给四项，有限求和后第一项恰为旧V，另外三项恰为上式ΔV，故 $V+\Delta V=J(R',S')$ 。证明不依赖变化的正负，也不要求输入值唯一；相同输出的所有配对都进入同一个有限和。

初始化时V由R、S完整求得。若某次调用前该等式成立，成功候选由上述恒等式保持；失败不改发布引用，等式也保持。逐批归纳就得到每个可见版本上的正确物化结果。这里证明的是所有成功发布的边界，不把任意中间项都当作可见查询答案。

查询来源多项式解释了连接乘贡献、投影加贡献，以及事实删除如何影响答案。本页维护的是每个批次的新旧差，允许负整数中间权；它不要求存储完整的符号来源表达式，也不把整数减法解释为SQL的集合差或截断bag差。

当前执行器的实际成本

标准库参考器用散列表保存“元组→非零整数权”，哈希只定位，完整元组相等仍决定是否合并。固定列数及字长、通常的哈希负载与随机性假设下，单次表访问按期望常数计；碰撞、长字符串和大整数运算另付成本。

设旧R、S的支撑大小为r、s，本批合并后的支撑为d、e，读入的原始变化项共b个。三个直接嵌套扫描恰检查 $ds+re+de$ 个候选对；这数的是不同元组的配对，每个匹配用重数乘法代表全部出现。零右表时仍有左侧循环与接口基础工作。

完整管理器还复制两基表、旧结果与组索引。设旧结果支撑为v，组数为g，受影响组在旧、新状态中的不同金额数合计分别为U、U'。包含下一页所实现的频数副本、MIN扫描和摘要准备，一次成功调用的安全期望时间界为

O(1+b+r+s+v+g+ds+re+de+U+U').

工作内存要同时容纳旧状态、候选副本、三项与净差分；可用同一式中各项的和作为宽松记录数上界。持久保留的当前状态规模为 $O(1+r+s+v+g)$ ，因为本例投影结果的一项恰对应某组的一个金额频数。调用者若保留历次状态或返回的审计记录，还须累计这些历史，不能只算最新一版。JSON排序、显示和自查的全量oracle不在核心调用界内。

本批r=s=d=e=3，直接增量程序检查27个候选对，匹配13次；重算新表的4×4支撑只检查16对。因此这个小例没有证明增量必然省工作。只有结合变化大小、键索引、结果规模、复制策略和状态复用才能作性能选择；正确差分给的是额外执行方式，不是无条件加速定理。[2，§6]

参考资料

[1] Mihai Budiu、Tej Chajed、Frank McSherry、Leonid Ryzhyk、Val Tannen，DBSP: Automatic Incremental View Maintenance for Rich Query Languages，PVLDB16(7)，2023，pp.1601–1614；§3 Theorems3.3–3.4、§4.1、§4.3及§7.1，PDF第4–6、10页：线性/双线性变化与Z-set。本文只证明所列有限bag算子和串行发布模型，不声称实现论文的一般递归编译器。
[2] Timothy Griffin、Leonid Libkin，Incremental Maintenance of Views with Duplicates，SIGMOD1995，pp.328–339，§5及§6开头，印刷p.335/PDF第8页：聚合变化及增量未必更快的成本条件。原文分开插入/删除bag；本页采用整数净差分，数据与发布参考器自定。

形式陈述 ​

快照非负，变化可以为负 ​

两侧同时改变时的完整差分 ​

一次发布对应一批完整输入 ​

一批订单和标签的共同变化 ​

双删为何产生一个正项 ​

失败、重放与自连接 ​

三项公式及整批不变量 ​

当前执行器的实际成本 ​

反向链接