查询来源与半环标注

形式陈述

有限关系上的标注运算

固定一个交换含幺半环 $K=(K,+,\cdot,0_K,1_K)$ 。对有限列集合 $U$ ，一个 $K$ -关系是从所有 $U$ -元组到 $K$ 的函数 $R$ ，且其支撑

\operatorname{supp}(R)=\{t:R(t)\ne0_K\}

有限。标注为 $0_K$ 表示该元组不在关系中；非零标注则随查询一起计算。一个数据库实例 $I$ 为每个输入关系名指定这样一个函数。元组的列值仍是普通数据，标注不会成为可供查询比较的数据列。

本页使用关系代数的有限正表达式：由输入关系、并、自然连接、投影、选择与重命名组成，不使用差或关系否定。选择谓词 $\theta$ 是固定的元组值条件，不读取标注；记 $[\theta(t)]_K$ 在条件成立时为 $1_K$ ，否则为 $0_K$ 。若 $R,S$ 的列集合分别为 $U,V$ ，运算定义为：

运算	输出元组的标注
同列关系的并	$(R\cup S)(t)=R(t)+S(t)$
自然连接	$(R\bowtie S)(t)=R(t\restriction_U)\cdot S(t\restriction_V)$ ，其中 $t$ 的列为 $U\cup V$
投影至 $W\subseteq U$	$(\pi_W R)(u)=\sum_{t\in\operatorname{supp}(R),\ t\restriction_W=u}R(t)$
选择	$(\sigma_\theta R)(t)=[\theta(t)]_K\cdot R(t)$
一一重命名 $\rho$	$(\rho R)(u)=R(\rho^{-1}u)$

这里的 $t\restriction_U$ 表示元组在列 $U$ 上的限制；连接用同一个输出元组的两份限制，自动保证公共列相等。空和规定为 $0_K$ 。零列单位关系把唯一的空元组 $()$ 标为 $1_K$ ，其他固定有限常量关系也可把列出的元组标为 $1_K$ ；空关系处处为零。

这些运算保持有限支撑。并的候选支撑包含于两份支撑的并；连接的候选来自有限多对输入元组；投影、选择与重命名只变换或筛选有限多行。因此有限表达式中的所有求和都是有限和，即使数据值来自无限论域，也不需要无限加法。

来源多项式与通用求值

为每条输入事实分配一个互异的符号，组成有限集合 $X$ 。同一事实在查询中被多次读取时始终使用同一个符号。把这些符号作为标注，得到 $\mathbb N[X]$ -实例 $I_X$ ；未出现的输入事实标为零。这里 $\mathbb N[X]$ 是自然数系数的交换多项式半环，采用普通的多项式加法与乘法。查询结果 $Q(I_X)(u)$ 称为答案 $u$ 的来源多项式。

给定任意变量赋值 $v:X\to K$ ，存在唯一保持 $0,1,+,\cdot$ 的半环同态

\operatorname{ev}_v:\mathbb N[X]\longrightarrow K, \qquad \operatorname{ev}_v(x)=v(x).

对任何上述正表达式 $Q$ ，逐元组应用同态，有

\operatorname{ev}_v\bigl(Q(I_X)\bigr) =Q\bigl(\operatorname{ev}_v(I_X)\bigr).

所以可以先保存符号化的查询结果，之后再选半环和输入标注求值；结果等于一开始就采用这些标注执行查询。更一般地，任意交换含幺半环间保持 $0,1,+,\cdot$ 的同态 $h:K\to L$ 都满足 $h(Q(I))=Q(h(I))$ 。两条结论分别由多项式的通用性质和查询结构归纳得到，证明放在“推论与应用”。它们对应 Green、Karvounarakis 与 Tannen 原文 §3 Proposition 3.5 和 §4 Theorem 4.3。

直觉

合取查询的集合语义回答“有没有成功见证”。来源标注进一步保留见证如何组成：两条事实必须同时使用，就把它们的符号相乘；不同见证能产生同一个答案，就把它们相加。投影虽然丢掉了见证列，其标注仍留下这条见证的贡献。

例如 $p_1t_1+p_2t_2$ 表示两种途径：使用 $p_1$ 与 $t_1$ ，或者使用 $p_2$ 与 $t_2$ 。它没有说四条事实都必须存在。一次乘法记录一个见证内部的共同需要，一次加法记录见证之间的替代关系。

选择解释时，布尔半环把加法读成“或”、乘法读成“且”；自然数半环则把它们读成见证数的相加与独立选择数的相乘。多项式暂时保留这两种解释都需要的组合信息。它的“通用”指能够经唯一同态送往任意交换含幺半环，而不是声称一份标注能直接回答所有数据库问题。

例子与边界

六条输入、五个见证、四个答案

沿用学生—课程—教师查询，把六条输入事实分别命名：

输入表	第一列	第二列	标注
Enroll(Student, Course)	甲	算法	$p_1$
Enroll(Student, Course)	甲	数据库	$p_2$
Enroll(Student, Course)	乙	数据库	$p_3$
Teach(Course, Teacher)	算法	林	$t_1$
Teach(Course, Teacher)	数据库	林	$t_2$
Teach(Course, Teacher)	数据库	周	$t_3$

查询为

Q=\pi_{\mathsf{Student},\mathsf{Teacher}} (\mathsf{Enroll}\bowtie\mathsf{Teach}).

按 Course 连接时，每个成功配对将两条输入标注相乘，得到全部五个见证：

Student	Course	Teacher	连接标注
甲	算法	林	$p_1t_1$
甲	数据库	林	$p_2t_2$
甲	数据库	周	$p_2t_3$
乙	数据库	林	$p_3t_2$
乙	数据库	周	$p_3t_3$

投影把产生同一学生—教师对的标注相加。下表同时给出三种解释；加权列使用自然数赋值

(p_1,p_2,p_3,t_1,t_2,t_3)=(2,1,3,4,5,2).

输出	来源多项式	全置 $1$ ，在 $\mathbb N$ 求值	全置 $1$ ，在布尔半环求值	自然数加权求值
甲—林	$p_1t_1+p_2t_2$	$2$	$1$	$2\cdot4+1\cdot5=13$
甲—周	$p_2t_3$	$1$	$1$	$1\cdot2=2$
乙—林	$p_3t_2$	$1$	$1$	$3\cdot5=15$
乙—周	$p_3t_3$	$1$	$1$	$3\cdot2=6$

自然数标注可理解为输入事实的重数：甲的算法选课有两份、林的算法授课有四份，连接产生八份该课程见证，再加数据库贡献的五份，故甲—林共有十三份。布尔解释则只留下四个答案的存在性。两种执行共享同一运算形式，但“加法”不同，输出含义也不同。

删除事实就是把对应变量置零

删除数据库—林这条授课事实，即令 $t_2=0$ ，保留其余符号。四个多项式依次化为

p_1t_1,\qquad p_2t_3,\qquad0,\qquad p_3t_3.

继续沿用上面的自然数权重，结果为 $(8,2,0,6)$ ；在布尔半环中把其余输入全置 $1$ ，结果为 $(1,1,0,1)$ 。乙—林消失，甲—林仍由算法课程支持。随后再删除 $p_1$ ，甲—林也变成零。这个过程直接操作已保存的多项式，通用求值定理保证它与删除输入后重新查询一致。

对甲—林，若只收集出现过的输入符号，得到 lineage 集合 $\{p_1,t_1,p_2,t_2\}$ ；若保留每个成功见证用了哪些事实，得到 why 来源的集合族

\bigl\{\{p_1,t_1\},\{p_2,t_2\}\bigr\}.

how 来源进一步用 $p_1t_1+p_2t_2$ 保存组合运算。在本例里每个事实最多用一次，每个见证单项式只出现一次，因此 why 集合族已经保留了单项式的全部分组信息；后面的重复使用例子才会显示它丢失的幂次与系数。

要让甲—林在集合答案中消失，删除集合必须与每个见证相交。其按包含关系极小的删除集合恰为

\{p_1,p_2\},\quad\{p_1,t_2\},\quad \{t_1,p_2\},\quad\{t_1,t_2\}.

证明可直接穷尽：必须从 $\{p_1,t_1\}$ 中删掉至少一个，也必须从 $\{p_2,t_2\}$ 中删掉至少一个，两组互不相交。各取一个得到上述四组；删得更多就包含其中一组，因而不极小。在这个例子里，四组也都是基数最小的删除方案，大小均为二。lineage 的单一合并集合无法表达这种“每个见证都要被击中”的条件。

系数和幂次记录不同事情

设同一元组在 $R$ 中的标注为 $P$ 。表达式 $R\cup R$ 给它标注 $2P$ ；同列关系的自然连接 $R\bowtie R$ 给它标注 $P^2$ 。前者记录两个查询分支都贡献了相同来源，后者记录同一来源在一个组合中使用两次。例如一条事实标为 $x$ ，这两个结果分别为 $2x$ 与 $x^2$ 。把 $x$ 赋为自然数 $3$ 后，它们为 $6$ 与 $9$ ，不能互换。

多项式的系数表示产生同一个单项式的推导重数，变量的幂次表示单个见证中该事实的使用次数。由于乘法交换，标注不记录使用顺序或完整语法树，但保留重数与幂次。将每个单项式压成事实集合会把 $x^2$ 与 $x$ 合并，将同一集合的多次出现去重又会丢掉系数。

在布尔半环中，加法与乘法都幂等，所以上面两个表达式都与 $R$ 相同。普通集合合取查询可以把重复原子当作一个原子；要计算多项式或 bag 标注，则必须保留查询中的原子出现次数。集合语义下的双向包含或等价改写，只保证布尔答案相同，不能自动保证来源多项式相同。

目标半环决定能观察什么

从来源多项式恢复普通存在性，应把输入的在场与缺席映到布尔半环的 $1$ 与 $0$ ，再按布尔运算求值。不能先随意选一个半环，再把它的所有非零值统一读成“真”：该操作未必是同态。例如模六整数是一个交换半环，两个非零标注 $2,3$ 相乘为零；模二整数中的 $1+1=0$ ，两个非零贡献相加也会消失。一般 $K$ 的支撑因此可能小于相同输入支撑在集合查询下的答案。

概率也需要按事件解释。假设甲—林的四条相关输入事实彼此独立，且各以概率 $1/2$ 存在。两个见证事件的概率各为 $1/4$ ，同时发生的概率为 $1/16$ ，故答案存在概率为 $1/4+1/4-1/16=7/16$ 。直接在实数中把 $p_1,t_1,p_2,t_2$ 都代为 $1/2$ ，多项式却得到 $1/2$ 。这个数可以解释为成功见证数量的期望，不能解释为至少一个见证成功的概率；“替代见证相加”不等于“重叠事件的概率相加”。

推论与应用

多项式求值为何唯一

把多项式写成有限和

P=\sum_\alpha n_\alpha\prod_{x\in X}x^{\alpha_x}, \qquad n_\alpha\in\mathbb N.

其中每个指数向量 $\alpha$ 的分量是非负整数。给定 $v:X\to K$ ，定义

\operatorname{ev}_v(P) =\sum_\alpha (n_\alpha\cdot1_K) \prod_{x\in X}v(x)^{\alpha_x},

这里 $n\cdot1_K$ 是 $n$ 个 $1_K$ 相加，零份为 $0_K$ ；零次幂为 $1_K$ 。交换律保证乘积不依赖变量排列。把两个多项式的系数逐项相加，立即得到求值保持加法；把乘积分配展开，利用 $K$ 的分配律，再合并相同指数，就得到求值保持乘法。常数零、一和单个变量的求值也分别符合要求，因此这确实是半环同态。

反过来，任何保持这些运算并把 $x$ 送到 $v(x)$ 的同态，都必须把自然数常数 $n$ 送到 $n\cdot1_K$ ，再把每个单项式及其有限和送到上述公式。因此延拓唯一。映射 $\mathbb N\to K$ 并不总是单射，例如在布尔半环中所有正整数都变成 $1$ ；唯一性不要求保留不同自然数之间的区别。

同态为何能穿过查询

设 $h:K\to L$ 保持 $0,1,+,\cdot$ ，对表达式结构归纳。输入关系情形就是逐元组定义 $h(I)$ ；常量关系的标注只有零、一，也保持不变。假设结论已对直接子表达式成立，只需逐个检查外层运算。

并的每个输出标注满足 $h(a+b)=h(a)+h(b)$ ，连接满足 $h(ab)=h(a)h(b)$ 。投影对一个输出元组的计算是有限和，所以

h\left(\sum_{t:t\restriction_W=u}R(t)\right) =\sum_{t:t\restriction_W=u}h(R(t)).

等式两侧可共同取原来的有限支撑为求和范围；若某个非零标注被 $h$ 送成零，右侧多写的零项不影响结果。因此支撑缩小不破坏归纳。选择条件只看元组值，且 $h([\theta(t)]_K)=[\theta(t)]_L$ ，于是选择也交换；重命名只改变索引，逐元组应用 $h$ 前后完全相同。所有构造都已覆盖，故 $h(Q(I))=Q(h(I))$ 。最后令 $h=\operatorname{ev}_v$ ，就得到来源多项式的通用求值公式。

这份证明把复用来源的前提落实到了每个运算：换输入重数、把事实置零、改用布尔存在性，都可以通过合适的赋值完成。若改写本身可由交换半环公理证明，则它也保存这些标注；只依据集合的幂等律做的去重改写，需要重新检查目标半环。

有限查询与递归证明的分界

差集要求判断一条候选事实是否缺席，不能在 $\mathbb N[X]$ 中简单写成 $1-x$ ，因为负系数不属于这个半环。上面的归纳只覆盖列出的正运算；扩展到否定需要另行给出标注结构和语义。

递归的困难则来自证明数量。考虑一个由事实 $p$ 启动的可达性答案，以及一条标为 $e$ 的自环。集合求值只需保留一个可达事实，但按走过自环的次数区分见证，会出现

p,\quad pe,\quad pe^2,\quad pe^3,\quad\ldots

这样的无限家族。有限事实上的集合不动点会停止增长，并不说明来源能由有限多项式容纳。处理这种递归来源需要定义无限求和及相应不动点，例如原文 §§5–6 使用的连续半环与形式幂级数。本页的终点是有限正查询：完整记录其有限见证，并证明这些记录在半环求值下如何转换。

参考资料

Todd J. Green、Grigoris Karvounarakis、Val Tannen，Provenance Semirings，PODS 2007，pp. 31–40。§3 Definitions 3.1–3.2 定义有限支撑的 $K$ -关系与正关系代数，Proposition 3.5 给出同态与查询求值交换；§4 Definition 4.1、Proposition 4.2、Theorem 4.3 给出多项式来源和通用性质（印刷 pp. 33–34）。§§5–6 讨论递归及无限来源。
Dan Suciu，CS294-248 Unit 7: Provenance and Semirings，Fall 2023 课程讲义，逻辑幻灯片 16–17、27–30、34–35（含动画的 PDF pp. 44–51、72–78、82–83）：自然数与布尔语义、来源多项式及不同幂等律保留的信息。

形式陈述 ​

有限关系上的标注运算 ​

来源多项式与通用求值 ​

六条输入、五个见证、四个答案 ​

删除事实就是把对应变量置零 ​

系数和幂次记录不同事情 ​

目标半环决定能观察什么 ​

多项式求值为何唯一 ​

同态为何能穿过查询 ​

有限查询与递归证明的分界 ​

反向链接