关系模型

一、第四章收尾：范式理论的深化

1.1 多值依赖与无损分解

前文介绍了多值依赖（Multi-Valued Dependency, MVD）及其推理规则。多值依赖与无损分解之间存在密切联系。

若关系模式 $R$ 的属性集 $U$ 被划分为 $X, Y, Z$（即 $Z = U - XY$），则 多值依赖 $X \twoheadrightarrow Y$ 成立的条件是：

\[R = \pi_{XY}(R) \bowtie \pi_{XZ}(R)\]

即 $R$ 在 $XY$ 和 $XZ$ 上的投影的自然连接等于 $R$ 本身。这等价于 $Y$ 和 $Z$ 两组属性在给定 $X$ 下是彼此无关的，因此自然构成一个无损分解。

核心直觉：多值依赖的本质是两组属性在给定 $X$ 的条件下完全独立，因此把它们分开存储再连接回来不会丢失信息。

1.2 第四范式（4NF）

定义：关系模式 $R$ 属于 第四范式（Fourth Normal Form, 4NF），当且仅当对于 $R$ 中每一个非平凡的多值依赖 $X \twoheadrightarrow Y$，$X$ 都是 $R$ 的超键（superkey）。

4NF 与 BCNF 的关系：

函数依赖（FD）是多值依赖的特殊情况（FD 要求 $X$ 确定唯一一个 $Y$ 值，MVD 允许 $X$ 确定多个 $Y$ 值）
因此 $X \rightarrow Y \implies X \twoheadrightarrow Y$，即每个 FD 都是 MVD
4NF 要求 MVD 的决定因素都是超键，BCNF 要求 FD 的决定因素都是超键
所以 $4NF \subseteq BCNF$，即满足 4NF 的模式一定满足 BCNF

示例（课程-学生-先导课程）：

关系 CSP(Course, Student, Prerequisite)，三个属性都是键
存在 MVD：Course $\twoheadrightarrow$ Student 和 Course $\twoheadrightarrow$ Prerequisite
但 Course 不是超键（需要全部三个属性才是超键）
因此不满足 4NF，需分解为 CS(Course, Student) 和 CP(Course, Prerequisite)

1.3 嵌入多值依赖（Embedded MVD）

当 MVD 不是在整个属性集 $U$ 上成立，而仅在 $U$ 的某个真子集 $W$ 上成立时，称为 嵌入多值依赖。

示例：在 CSPY(Course, Student, Prerequisite, Year) 中（加入选课年份）：

在子集 CSP(Course, Student, Prerequisite) 上，Course $\twoheadrightarrow$ Student | Prerequisite 成立
但加上 Year 后，因为同一个学生在不同年份选同一门课可能对应不同先导课程，MVD 不再成立
这就是嵌入多值依赖：只在去掉 Year 之后才成立

处理方式：先将 CSPY 分解为 CSP 和 DY（课程年份关系），再对 CSP 进一步分解。

1.4 连接依赖与第五范式（5NF）

连接依赖（Join Dependency, JD）：将关系 $R$ 分解为 $R_1, R_2, \ldots, R_n$（满足 $\bigcup R_i = U$），如果

\[R = \bowtie_{i=1}^{n} \pi_{R_i}(R)\]

即所有这些投影的自然连接等于原关系，则称 $R$ 满足连接依赖 $\bowtie (R_1, R_2, \ldots, R_n)$。

平凡连接依赖：若其中一个 $R_i$ 恰好等于 $R$ 本身，则该连接依赖是平凡的（因为其余投影都来自 $R$，连接回来自然不会多出元组）。

SPJ 示例（Supplier-Part-Project）：

原始关系 SPJ(S#, P#, J#) 有 4 条元组
分解为 SP(S#, P#)、PJ(P#, J#)、JS(J#, S#) 三个关系
先将 SP 和 PJ 连接，得到 5 条元组（多出 1 条不存在的组合）
再与 JS 连接，多余的被过滤掉，恢复到 4 条元组
只有三个关系全部同时连接才能恢复原关系

连接依赖会带来插入/删除异常——如果在满足连接依赖的关系中插入一条元组，可能必须同时插入另一条（否则连接回去会不一致）；删除一条时也可能必须连带删除另一条。这正是 5NF 要解决的问题。

第五范式（Fifth Normal Form, 5NF），又称 Project-Join Normal Form（PJ/NF）：关系模式 $R$ 属于 5NF，当且仅当 $R$ 中每一个非平凡的连接依赖都由 $R$ 的候选键蕴含。

值得注意的历史联系：5NF 的思想与今天分布式数据库中 key-value 存储的方式非常类似——定义一个公共的 key，所有属性按 key 分布在不同的 value 中，需要时通过 key 连接回来。当年提出 5NF 时还没有 key-value 存储，但却自然地暗合了后来的工程实践。

1.5 范式之间的关系总结

范式严格程度：$5NF \subset 4NF \subset BCNF \subset 3NF \subset 2NF \subset 1NF$

更高的范式消除更多类型的冗余：

2NF/3NF/BCNF：关注函数依赖带来的冗余
4NF：关注多值依赖带来的冗余
5NF：关注连接依赖带来的冗余

二、关系代数：除法与扩展操作

2.1 除法操作（Division）

2.1.1 直觉理解

除法操作的语义与 SQL 中”查询选修了所有课程的学生的学号”这类查询对应。若将学生的选课关系 $R(Sno, Cno)$ 除以所有课程 $S(Cno)$，结果就是选修了全部课程的学生学号。

除法本质上是笛卡尔积的逆运算——正如乘法和除法的关系一样。$R \div S$ 的结果与 $S$ 做笛卡尔积，得到的结果是 $R$ 中包含了所有 $S$ 组合的那部分。

具体例子：

$R$ 包含（学号，课程号）：除以 1 门课 -> 选修了这门课的所有学生
除以 2 门课 -> 同时选修了这两门课的所有学生
除以 3 门课 -> 同时选修了三门课的学生

2.1.2 形式化定义

设 $R$ 和 $S$ 是两个关系，$S$ 的属性集是 $R$ 属性集的子集。则：

\[R \div S = \pi_{R-S}(R) - \pi_{R-S}\left(\pi_{R-S}(R) \times S - R\right)\]

推导步骤：

$\pi_{R-S}(R)$：取 $R$ 中除 $S$ 属性以外的所有属性的投影（得到所有”候选者”）
$\pi_{R-S}(R) \times S$：将候选者与 $S$ 做笛卡尔积（得到”所有候选者选修了所有课程”的假想表）
步骤 2 的结果减去 $R$：找出哪些候选者并没有真正选修全部课程
把步骤 3 从候选者中去掉，剩下的就是真正选修了全部课程的

在 SQL 中没有直接的除法运算符，所以必须用两次否定（NOT EXISTS）来模拟：先找出”不满足条件”的，再从全部中排除。如果 SQL 有除法操作，”选修了全部课程”这类查询一行就能完成。

2.2 SQL 到关系代数表达式的转换

所有 SQL 查询都可以转换为关系代数表达式，这是查询处理的基础。

转换的基本模式：

SELECT A FROM R WHERE condition -> $\pi_A(\sigma_{condition}(R))$
多表查询 -> 笛卡尔积（或自然连接）+ 选择 + 投影
嵌套查询 -> 对应的嵌套关系代数子表达式

关键原则：关系代数的所有操作都可以用程序实现，所以只要将 SQL 转为关系代数表达式，就能编程执行查询。

具体示例（学生 S、选课 SC、课程 C 三张表）：

检索选修 C2 课程的学生学号和成绩：$\pi_{Sno, Grade}(\sigma_{Cno=’C2’}(SC))$
检索选修 C2 课程的学生学号和姓名（需要 S 和 SC 自然连接）：$\pi_{Sno, Sname}(\sigma_{Cno=’C2’}(S \bowtie SC))$
检索选修 Math 课程的学生：$\pi_{Sno, Sname}(\sigma_{Cname=’Math’}(S \bowtie SC \bowtie C))$
检索选修 C2 或 C4 的学生：$\pi_{Sno}(\sigma_{Cno=’C2’ \lor Cno=’C4’}(SC))$
检索同时选修 C2 和 C4 的学生：需要 SC 与自身做笛卡尔积（自连接），条件为学号相同且分别选修 C2 和 C4
未选修 C2 的学生：$\pi_{Sname, Age}(S) - \pi_{Sname, Age}(\sigma_{Cno=’C2’}(S \bowtie SC))$

涉及”否定”（NOT）的查询需要特别注意——不能简单地在选择条件中写 Cno != 'C2'。因为一个学生可能选多门课，他在选其他课的元组上满足 Cno != 'C2'，但他确实选了 C2。正确的做法是用集合差：全部学生减去选了 C2 的学生。

选修了全部课程的学生：$\pi_{Sno, Sname}((\pi_{Sno, Cno}(SC) \div \pi_{Cno}(C)) \bowtie S)$
选修的课程包含 S3 所学全部课程的学生的学号：$SC \div \pi_{Cno}(\sigma_{Sno=’S3’}(SC))$

2.3 外连接（Outer Join）

在普通自然连接中，没有匹配元组的行会被丢弃。外连接保留这些无匹配的行，缺失的属性填 NULL。

左外连接（Left Outer Join）：保留左表全部元组
右外连接（Right Outer Join）：保留右表全部元组
全外连接（Full Outer Join）：保留两表全部元组

2.4 外部并（Outer Union）

当两个关系模式不同（属性不完全重叠）时，普通的并操作无法进行。外部并将两个关系的属性全部纳入，形成一个新的关系模式，缺失的值填 NULL。

2.5 半连接（Semi-Join）

半连接 $R \ltimes S = \pi_R(R \bowtie S)$，即 $R$ 和 $S$ 连接后只在 $R$ 的属性上做投影，保留 $R$ 中能与 $S$ 形成连接的元组。

主要应用场景：分布式数据库的查询优化。

在分布式环境中，关系 $R$ 和 $S$ 可能分布在不同的计算节点上。做连接有两种简单方案：

将 $R$ 传到 $S$ 的节点做连接
将 $S$ 传到 $R$ 的节点做连接

无论哪种，整表传输的网络开销都很大。使用半连接的优化策略：

在 $R$ 的节点上，对 $R$ 在公共属性上做投影（只获取连接键的值）
将此投影（数据量远小于整表）发送到 $S$ 的节点
在 $S$ 的节点上做半连接，筛出能与 $R$ 连接的那部分 $S$ 元组
仅将该部分 $S$ 元组传回 $R$ 节点做最终连接

核心思想：不传整表，只传”可能匹配”的那一小部分，大幅减少网络传输量。

2.6 计算代价的层次

数据库系统的数据传输代价可以从计算机存储体系来理解：

最快：CPU/GPU 内部高速缓存（SRAM）
快：内存（DRAM）
慢：硬盘（机械硬盘 HDD / 固态硬盘 SSD）
最慢：网络传输（在不利网络条件下甚至比读硬盘还慢）

在数据库系统中，网络 I/O 是分布式查询的重要开销来源——这正是半连接等技术有价值的原因。

三、关系演算（Relational Calculus）

3.1 元组关系演算（Tuple Relational Calculus）

关系演算是将数理逻辑中的谓词演算与关系模型结合产生的查询语言。其核心形式为：

\[\{t \mid P(t)\}\]

其中 $t$ 是元组变量，$P(t)$ 是 $t$ 需要满足的谓词公式。

原子公式：

$t \in R$：元组 $t$ 属于关系 $R$
$t[A] \;\theta\; s[B]$：两个元组的属性值满足比较关系 $\theta$（如 $=, >, <$ 等）
$t[A] \;\theta\; c$：元组属性值与常量 $c$ 满足比较关系

逻辑运算符：

$\lnot$（非）、$\land$（与）、$\lor$（或）
$\implies$（推出）：$P_1 \implies P_2$ 等价于 $\lnot P_1 \lor P_2$
$\exists$（存在量词）：存在某个元组使公式为真
$\forall$（全称量词）：所有元组都使公式为真

自由变量与约束变量：受量词约束的变量是约束变量（如 $\exists t$ 中的 $t$），否则为自由变量。只有自由变量出现在结果元组中。

关系代数基本操作到元组演算的转换：

并：${t \mid t \in R \lor t \in S}$
差：${t \mid t \in R \land \lnot(t \in S)}$
笛卡尔积：${t \mid \exists u \in R, \exists v \in S \text{ such that } t \text{ 由 } u, v \text{ 拼接而成}}$
投影：${t \mid \exists u \in R \text{ such that } t \text{ 是 } u \text{ 的部分属性}}$
选择：${t \mid t \in R \land \text{condition}(t)}$

3.2 域关系演算（Domain Relational Calculus）

域关系演算与元组演算的区别：用属性级变量代替元组级变量。

形式：${x_1, x_2, \ldots, x_n \mid P(x_1, x_2, \ldots, x_n)}$

元组变量 $t$ 被拆解为各个属性变量 $x_1, x_2, \ldots$。其他逻辑运算符、量词的使用与元组演算完全一致。

3.3 安全运算问题

无限关系问题：形如 ${t \mid \lnot(t \in R)}$ 的表达式会产生无限大的关系——因为不在 $R$ 中的元组有无穷多个（考虑所有可能的属性值组合）。无法对无穷集合进行验证。

安全表达式（Safe Expression）：限定所有变量的取值只能来自于关系中实际出现的值（定义域 DOM），从而将变量的可能取值限定为有限集合。

核心思路：一个关系本身就是对数据的一种约束——只有出现在关系中的值才是有效值。$DOM(P)$ 定义为出现在公式 $P$ 中的关系的所有属性值。要求表达式中的所有变量值都来自 $DOM(P)$，自然就避免了无限关系的问题。

例如，学生表中年龄字段的值可能只是 16 到 26 这 11 个值，那么就只在这 11 个值上做验证，而不需要考虑所有的整数。

四、关系代数表达式的优化

4.1 为什么需要优化

同一个查询可以对应多个等价的关系代数表达式，但它们的计算代价差异巨大。

具体例子（$R(A, B)$ 和 $S(C, D)$，查询条件为 $B=99$ 且 $B=C$）：

表达式 E1（直接翻译）：先 $R \times S$ 做笛卡尔积（$n_R \times n_S$ 条），再做选择，再做投影
- 代价约 $3 \times n_R \times n_S$
表达式 E2（先做选择）：先在 $S$ 上选择 $D=99$（约 $n_S/100$ 条结果），再与 $R$ 做笛卡尔积，再做选择和投影
- 代价约 $n_S + n_R \times n_S/100 + \text{常数}$，远小于 E1
表达式 E3（用自然连接替代笛卡尔积）：先选择 $D=99$，再做自然连接（基于排序-合并算法）
- 自然连接的复杂度为 $O(n \log n)$ 级别（$n_R \log n_R + n_S \log n_S$），而非 $O(n_R \times n_S)$
- 代价远小于前两种

即使三者结果完全相同，执行效率可以差几个数量级。因此优化器的工作就是从众多等价表达式中选出最高效的那个。

4.2 优化的核心策略

尽早做选择操作（Push selection down）：将选择条件下推到叶子节点附近执行，在笛卡尔积/连接之前就大幅缩减参与运算的元组数量
- 拆分复合选择条件：$\sigma_{F_1 \land F_2}(R) = \sigma_{F_1}(\sigma_{F_2}(R))$
- 利用分配律：$\sigma_{F}(R \times S) = \sigma_{F_R}(R) \times \sigma_{F_S}(S)$（$F_R$ 仅涉及 $R$ 属性，$F_S$ 仅涉及 $S$ 属性）
尽早做投影操作（Push projection down）：无关的属性尽早裁掉，减少元组的宽度
用自然连接替代笛卡尔积：笛卡尔积 + 等值选择 = 自然连接，后者的实现算法比纯笛卡尔积高效得多

4.3 语法树优化

查询可以表示为一棵语法树（syntax tree）：

叶节点：关系表
内部节点：关系代数操作（选择、投影、笛卡尔积/连接等）
操作的执行顺序是从叶到根

优化过程：

从初始语法树出发（笛卡尔积在最下层，选择在上层）
拆分选择条件为原子条件
将每个原子条件下推到叶节点附近
将投影操作也下推
将”选择 + 笛卡尔积”的组合转换为自然连接

优化后的语法树：选择操作紧贴叶节点（关系表），自然连接替代了笛卡尔积。

这仅仅是关系代数层面的优化。后续的查询处理层面还包括各种连接算法的具体实现、不同场景下算法的选择、每种算法的复杂度分析。

五、关系逻辑（Relational Logic / Datalog）

5.1 历史背景

关系逻辑诞生于 AI 的前一轮热潮——谓词逻辑主导的时代。当时人们试图用大量逻辑规则进行推理，从已知事实推导新知识。这种思路后来与关系数据库相结合，成为 Datalog 语言。基于规则的系统至今在很多领域仍有专家系统（expert system）应用，以规则的方式进行推理和决策。

5.2 基本概念

谓词（Predicate）分为两种：

外延谓词（Extensional Predicate）：存储在数据库中的事实/数据（即我们已有的关系表），相当于知识库
内涵谓词（Intensional Predicate）：通过逻辑规则推导出来的结果

两者的统一：通过谓词概念将存储事实和推导结论表示在同一体系下，使得推理有了数据基础。

规则（Rule）的形式：

\[W \leftarrow P_1, P_2, \ldots, P_n\]

即：如果 $P_1, P_2, \ldots, P_n$ 同时成立，则 $W$ 成立（$W$ 就是内涵谓词）。

5.3 关系代数操作在关系逻辑中的表示

交：$W(x,y,z) \leftarrow R(x,y,z), S(x,y,z)$
并：$W(x,y,z) \leftarrow R(x,y,z)$ 和 $W(x,y,z) \leftarrow S(x,y,z)$（两条规则）
选择：在规则体中添加比较条件
投影：通过变量选择实现

5.4 与递归查询的关系

递归查询最早出现在谓词逻辑中，是通过推理规则的反复应用实现的。后来被引入关系数据库的递归查询（如 SQL 中的 WITH RECURSIVE）。在表达递归时，用的正是推理规则的形式——这是关系逻辑的一个重要遗产。

六、数据库存储结构

6.1 数据库存储的特殊性

数据库与数据结构课程的根本不同：

数据结构：数据在内存中，断电即丢失
数据库：数据必须存储在硬盘（非易失存储器）上持久保存，断电不能丢失

这带来了核心问题：数据在内存中计算，在硬盘上存储，必须考虑两者之间的数据交换。

6.2 三级存储体系

级别	存储器类型	特点
一级	CPU缓存 + 内存（DRAM）	速度最快，价格最贵，容量最小
二级	硬盘（HDD）/ 闪存（SSD/Flash）	速度中等，价格适中，容量大
三级	光盘、磁带等	速度最慢，价格最便宜，用于离线备份

目前一台机器有 1TB 内存已属高配，但 1TB 硬盘现在已很普通——两者的价差极大。

第三级存储器真正被重视来自于 9/11 事件。世贸中心里有大量银行和金融机构的服务器，撞击导致大量数据永久丢失。此后业界开始非常重视定期备份并将数据异地存放。今天在线云存储也是一种新的第二级存储形式。

6.3 块（Block）：数据库 I/O 的基本单位

最重要的特性：硬盘和闪存都以块（block）为单位进行读写，而非按字节。

一次读取至少读一个块（通常 4KB），即使只需要其中 100 个字节
一次写入至少写一个块
内存可以按位/按字节读取，但硬盘和闪存做不到

为什么这对数据库影响巨大：

要把经常一起访问的相关数据放在相邻的块中（局部性原理）
顺序读效率高，随机访问效率极低（尤其是机械硬盘，需要移动磁头）
即使对 SSD，顺序访问仍然优于随机访问

6.4 磁盘与闪存的异同

磁盘（HDD）结构：

多个碟片（platter），每个碟片上有多个磁道（track）
磁头在磁道上读写数据
容量 = 碟片数 x 每碟磁道数 x 每磁道块数
顺序读快，随机读慢（需要寻道 + 旋转延迟）

闪存（Flash / SSD）：

同样以块为单位读写
关键区别：Flash 不能直接原地修改。修改数据的步骤是：
1. 读取整个旧块
2. 在空白区域写一个新块（append-only 方式）
3. 标记旧块为无效（后续回收）
大块内部分成多个小页（page），写以 page 为单位，擦除以大块（erase block，通常几十到上百 KB）为单位
擦除前必须先整块清零
擦除代价较高（毫秒级），但读取速度非常快（接近内存），远快于 HDD 随机读

Flash 的这种 append-only + 擦除回收特性，直接影响了数据库中一些关键技术——如 LSM-Tree（Log-Structured Merge Tree）的设计、冷热数据分离等策略。

Flash vs HDD 性能对比：

连续读写：两者速度接近（都受限于接口带宽）
随机读：Flash 远快于 HDD（Flash 无机械寻道延迟）
随机写：Flash 有擦除开销，但与 HDD 差距不大

6.5 非易失存储器的演进

Flash（SSD）作为非易失存储器，因其读速度快、可直接持久化，越来越多地被用作内存和传统硬盘之间的中间层：

日志（WAL）可以被放在 Flash 上
热数据可以放在 Flash 上，冷数据放 HDD
三层存储体系的边界日益模糊

6.6 RAID：冗余磁盘阵列

动机：

单一存储系统包含几百块硬盘，体积小、容量大
但可靠性是问题：单块磁盘可靠性 99.99%，100 块一起就是 $0.9999^{100} \approx 0.99$，显著降低
几百块盘时可靠性完全不可接受

RAID 的解决思路：

冗余（Redundancy）：通过额外的校验盘/镜像提高容错能力
并行（Parallelism）：通过条带化（striping）将数据分散在多块盘上，同时读写，提高吞吐量

条带化（Striping）：将数据分成小块，交替存放在多个磁盘上。例如块 1 放盘 1，块 2 放盘 2，块 3 放盘 1，以此类推。读取时可从多盘并发读取。

关系模型深化：范式理论、查询语言与存储结构基础