关系代数

选择问“这一行合格吗”，连接问“两条事实能否接上”，投影问“答案需要保留哪些信息”。投影丢掉课程列，并不表示课程从未参与计算；它把“这位学生和这位教师之间存在课程见证”压缩成一个答案。

这种代数首先规定结果，不指定扫描、散列连接或索引连接的执行方式。优化器可以换执行方案，但每次改写都必须保持所有合法实例上的结果，而不是只在一张示例表上碰巧相同。

三行加三行，连接得到五行 ​

取关系数据模型中的两张三行表。按公共列 Course 连接，得到：

数据库这门课有两个学生、两个教师，贡献 $2\times 2=4$ 行；算法贡献一行，所以连接结果恰为五行。查询

得到 $\{(\text{甲},\text{林}),(\text{甲},\text{周}),(\text{乙},\text{林}),(\text{乙},\text{周})\}$。其中 $(\text{甲},\text{林})$ 有两条课程见证，却只贡献一个集合成员。再选择 Teacher 为周并投影 Student，得到 $\{\text{甲},\text{乙}\}$。

投影不能过早丢掉连接列 ​

令 $R(A,B)=\{(a,1)\}$，$S(B,C)=\{(2,c)\}$。因为 $1\ne 2$，有

先丢掉 $B$，就丢掉了验证两表能否接上的证据，产生伪答案。合法的投影下推必须保留后续连接和选择仍需要的列。

投影后重建需要约束保证 ​

对覆盖原列集合的 $U_1,\dots ,U_m$，任何原行都能由自己的投影片段拼回，因此总有 $r\subseteq {\bowtie }_i{\pi }_{U_i}(r)$。反向包含却未必成立：来自不同原行的片段可能在公共列上一致，因而拼出额外组合。无损连接分解公理库无损连接分解Lossless join decomposition · Dependency preservation证明二元分解的公共属性闭包判据，并在同一四属性模式上比较无损、依赖保持、第三范式与 BCNF。要求原表与重建结果相等，并且这一保证对所有满足指定函数依赖的原表成立。二元分解中，公共列能否决定一侧就是判定关键。它与提前丢掉连接列的查询改写问题相关，但判定对象是一整套存储分解及其允许实例。

集合答案与 SQL 重复行 ​

在不含 NULL 的本例中，连接后用 SELECT DISTINCT Student, Teacher 可以表达上述集合投影；不带 DISTINCT 的普通 SQL 查询通常保留重复项，会把甲—林输出两次。两者甚至对答案基数都给出不同值，因此不能跨越集合与多重集语义直接套用改写。ORDER BY 所规定的顺序也不属于这里的关系值。

每个代数表达式都只处理输入值和显式常量，扩大未使用的外部论域不会改变结果。这提供了域独立性的结构归纳证明，也解释为什么差集必须有左侧候选关系，不能解释为“整个无限宇宙中的补集”。

在关系演算公理库关系演算Relational calculus · Domain relational calculus用一阶公式的满足条件定义关系查询，并以域独立性区分仅依赖数据库事实的查询与依赖外部论域的公式。中，积对应合取、投影对应存在量词、并对应析取、差对应有候选范围的否定。反向翻译要构造包含查询常量的活跃域，并单独处理空活跃域与零列真假值；这些边界是等价定理的一部分。

合取查询公理库合取查询Conjunctive query · CQ · Select-project-join query用关系事实的匹配定义集合答案，并以规范数据库与反向同态判定所有有限实例上的查询包含。只需其中选择、投影与连接的核心片段，就能完成本页的学生—教师查询。它的包含定理把“所有有限实例上的答案包含”转化为反向同态检查；两个方向都成立时，得到保持集合答案的等价改写。检查之前必须确定是否去重、是否另有依赖约束：同一集合答案可以具有不同的见证重数，而约束又会改变需要比较的实例范围。完整代数还允许并和差，不能把这个纯合取片段的判据直接套到所有代数表达式上。

Datalog 与有限最小不动点公理库Datalog 与有限最小不动点Datalog · Positive Datalog · Datalog least model在固定有限活跃域上反复应用正规则，证明所得关系是最小模型，并用有环可达性逐轮推导半朴素求值。把正的连接、投影与并反复执行，直到不再出现新事实，由此计算无预设长度上界的可达性。单轮仍可用关系代数实现；半朴素求值再用差集排除已知答案，减少旧事实的重复匹配。