数据库 4：函数依赖与模式分解
函数依赖
定义
设 \(R(U)\) 是属性集合 \(U=\{A_1, A_2, \cdots, A_n\}\) 上的一个关系模式，\(X\) 和 \(Y\) 是 \(U\) 的两个子集，若对 \(R(U)\) 的任何一个关系 \(r\) 都没有两个这样的元组，它们在 \(X\) 中的属性值相等而在 \(Y\) 中的属性值不等，则称 \(X\) 函数决定 \(Y\)，或 \(Y\) 函数依赖 \(X\)。记作 \(X\to Y\)。
例如：\(U=\{学号, 姓名, 年龄, 班号, 班长, 课号, 成绩\}\)，则
\(学号\to\{姓名, 年龄\}\)
\(班号\to 班长\)
\(\{学号, 课号\}\to 成绩\)
如果 \(X\to Y\)，但 \(Y\not\subset X\)，称 \(X\to Y\) 是非平凡的函数依赖。
部分与完全函数依赖
若 \(X\to Y\)，且对 \(X\) 的任何真子集 \(X'\) 都有 \(X'\not\to Y\)，称 \(Y\) 完全函数依赖于 \(X\)，记作 \(X\xrightarrow{f} Y\)；否则称 \(Y\) 部分依赖于 \(X\)，记作 \(X\xrightarrow{p} Y\)。
传递函数依赖
在 \(R(U)\) 中，若 \(X\to Y\)，\(Y\to Z\) 且 \(Y\not\subset X\)，\(Z\not\subset Y\)，\(Z\not\subset X\)，\(Y\not\to X\)，则 \(X\to Z\)，称 \(Z\) 传递依赖于 \(X\)。
候选键
对于 \(R(U)\) 中的属性或属性组合，若 \(K\xrightarrow{f}U\)，称 \(K\) 为 \(R(U)\) 上的候选键。
任一候选键都可以作为 \(R\) 的主键。包含在任一候选键中的属性称为主属性，其他属性称为非主属性。
逻辑蕴涵
设 \(F\) 是 \(R(U)\) 上的一个函数依赖集合，\(X\) 和 \(Y\) 是 \(R\) 的属性子集。如果从 \(F\) 中的函数依赖能推导出 \(X\to Y\)，称 \(F\) 逻辑蕴涵 \(X\to Y\)，记作 \(F\vDash X\to Y\)。
闭包
被 \(F\) 逻辑蕴涵的所有函数依赖集合称为 \(F\) 的闭包，记作 \(F^+\)。如果 \(F=F^+\)，则 \(F\) 是一个全函数依赖族，或称函数依赖完备集。
Armstrong's Axioms
设有关系模式 \(R(U)\)，\(F\) 为 \(R(U)\) 的一组函数依赖，有：
A1 自反律：若 \(Y\subseteq X\subseteq U\)，则 \(X\to Y\) 被 \(F\) 逻辑蕴涵。
A2 增广律：若 \(X\to Y\in F\)，\(Z\subseteq U\)，则 \(XZ\to YZ\) 被 \(F\) 逻辑蕴涵。
A3 传递律：若 \(X\to Y\in F\)，\(Y\to Z\)，则 \(X\to Z\) 被 \(F\) 逻辑蕴涵。
可以由它们推出这些次要结论：
合并律：如果 \(X\to Y\)，且 \(X\to Z\)，则 \(X\to YZ\)。
伪传递律：如果 \(X\to Y\)，且 \(WY\to Z\)，则 \(XW\to Z\)。
分解律：若 \(X\to Y\)，且 \(Z\subseteq Y\)，则 \(X\to Z\)。
最小覆盖
如果函数依赖集合 \(F\) 满足下面的条件，称 \(F\) 为最小覆盖或最小依赖集：
\(F\) 中每个函数依赖，右部都是单个属性。
\(\forall X\to A\in F\)，有 \(F-\{X\to A\}\) 不等价于 \(F\)——即，\(F\) 是最小的，去掉 \(F\) 中的任何一个函数依赖都不行。
\(\forall X\to A\in F\)，\(Z\subset X\)，有 \((F-\{X\to A\})\cup\{Z\to A\}\) 不等价于 \(F\)——即，\(F\) 中的任何一个函数依赖都是最小的，不可以把它们的左部缩小。
构造最小依赖的方法：
分解——将 \(X\to AB\) 分解成 \(X\to A\) 和 \(X\to B\)，即所有依赖的右部都是单一属性。
去除左部多余的属性——逐一检查所有的依赖项的左部。对于左部不是单一属性的依赖项，例如 \(XY\to A\)，判断 \(Y\) 是否多余。计算 \(X^+\)，如果 \(X^+\) 包含 \(Y\)，那么 \(Y\) 就是多余的，可以去掉。
去掉多余的依赖——对于每一个依赖项 \(X\to Y\)，先去掉它，然后在其他项里求 \(X^+\)，如果 \(X^+\) 包含 \(Y\)，那么确实可以去掉它，否则就不能去掉。
关系范式
第一范式（1NF）
若关系模式 \(R(U)\) 中每个关系都不可分，则 \(R(U)\) 满足第一范式，记为 \(R(U)\in \text{1NF}\)。即，不存在复合属性的关系模式满足 1NF。
将含有复合属性的关系中的复合属性拆分，就可以得到满足 1NF 的关系。
第二范式（2NF）
如果满足 1NF 的关系模式 \(R(U)\)，每一个非主属性完全函数依赖于候选键，则 \(R(U)\) 满足 2NF。
例如：
\[R(S\#, SN, SD, CN,G)\]
分别对应学号、姓名、班级、课程、成绩。候选键有 \(S\#\) 和 \(CN\)，但是因为 \(S\#\xrightarrow{f}\{SN, SD\}\)，故 \(\{S\#, CN\}\xrightarrow{p}\{SN, SD\}\)，所以不满足 2NF。
将原关系拆分成两个子关系 \(R_1(S\#, SN, SD)\) 和 \(R_2(S\#, CN, G)\)，这两个子关系都满足 2NF。
第三范式（3NF）
如果满足 2NF 的关系模式 \(R(U)\) 不存在这样的情况：对于候选键 \(X\)，属性组 \(Y\) 和非主属性 \(A\)，\(A\not\in X\)，\(A\not\in Y\)，\(Y\not\subset X\)，\(Y\not\to X\)，但有 \(X\to Y\)，\(Y\to A\) 成立，则 \(R(U)\) 满足 3NF。
即，某些属性依赖一些非主属性，构成传递依赖。例如：学号 \(\to\) 系号 \(\to\) 系主任。这样的关系就不满足 3NF。
同样，通过拆分可以构造满足 3NF 的关系。
Boyce-Codd 范式（BCNF）
满足 1NF 的关系模式 \(R(U)\)，对于任何 \(X\to Y\)，当 \(Y\not\subset X\) 时，\(X\) 必含有候选键，则 \(R(U)\) 满足 BCNF。
即，有不依赖于候选键的函数依赖，就不满足 BCNF。
分解规则：将左侧不含候选键的函数依赖单独组成一个关系，将含有的组成另一关系。
模式分解
关系模式 \(R(U)\) 的分解指用 \(R\) 的一组子集 \(\rho=\{R_1(U_1), R_2(U_2), \cdots, R_k(U_k)\}\) 代替它。其中 \(U=U_1\cup U_2\cup\cdots\cup U_k\)，并且任意两个子关系 \(U_i\) 和 \(U_j\) 不同。
无损连接性：\(R\) 与 \(\rho\) 在数据内容方面是否等价。
保持依赖性：\(R\) 与 \(\rho\) 在数据依赖方面是否等价。