数据库 4：函数依赖与模式分解

2022 年 12 月 8 日

函数依赖 #

定义 #

设 $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$ 在数据依赖方面是否等价。