Relational Theory

问题提出
关系模式
函数依赖*
键
基于函数依赖的关系模式范式*
- 1 NF
- 2 NF
- 3 NF
- BCNF
多值依赖
- 4 NF
关系模型的分解

问题提出

数据冗余 + 增删改异常

合适 vs 不合适（斜体）

解决方式：形式化地表述数据之间的依赖关系

多值依赖： $x = f(y)$
函数依赖： $y = f(x)$ $y = f (x)$
- 完全依赖 vs 部分依赖
- 传递依赖
- 平凡 vs 非平凡

关系模式

一个五元组 $R(U, D, DOM, F)$

$R$ 关系名
$U$ 一组属性
$D$ 属性组 $U$ 中的属性所来自的域
$DOM$ 为属性到域的映射
$F$ 为属性组 $U$ 上的一组数据依赖

当且仅当 $U$ 上的一个关系 $r$ 满足 $F$ 时，称 $r$ 为关系模式 $R$ 上的一个关系。

函数依赖*

对属性集 $R(U)$ 中任意一个可能的关系 $r$ ，不可能存在两个原组在 $X$ 上的属性相等，而在 $Y$ 上的属性不等（即对给定的 $X$ ，有唯一确定的 $Y$ ），则称“ $X$ 函数确定 $Y$ ” 或“ $Y$ 函数依赖于 $X$ ”，记作 $X \rightarrow Y$ 。

平凡与非平凡

$X \rightarrow Y$ ，但 $Y \subsetneq X$ 是非平凡的函数依赖
$X \rightarrow Y$ ，但 $Y \subseteq X$ 是平凡的函数依赖（显然成立）

完全与部分

若对 $X$ 的任意一个真子集 $X^{'}$ ，都有 $X^{'} \nrightarrow Y$ ，则称 $Y$ 对 $X$ 完全函数依赖，记作 $X \stackrel{F}{\rightarrow} Y$ 。
若 $Y$ 不完全函数依赖于 $X$ ，则称 $Y$ 对 $X$ 部分依赖，记作 $X \stackrel{P}{\rightarrow} Y$ 。

传递函数依赖：满足

$X \rightarrow Y \; (Y \subsetneq X)$
$Y \nrightarrow X$
$Y \rightarrow Z$
$Z \subsetneq Y$

则称 $Z$ 对 $X$ 传递函数依赖（transitive functional dependency），记为 $X \stackrel{传递}{\rightarrow} Z$ 。

函数依赖集闭包

$F^+$ （一个关系的集合）是关系集合 $F$ 在 $R(U, F)$ 上的闭包，当且仅当 $F^+$ 中的所有关系都可由 $F$ 中的关系推出。

例子：

\begin{aligned} given \\ R &= (A, B, C, G, H, I) \\ F &= \{ \\ & \; A \rightarrow B, \\ & \; A \rightarrow C, \\ & \; CG \rightarrow H, \\ & \; CG \rightarrow I, \\ & \; B \rightarrow H, \\ \} \\ then \\ F^+ &\supseteq \{ \\ & \; A \rightarrow H, \\ & \; AG \rightarrow I, \\ & \; CG \rightarrow HI, \\ \} \end{aligned}

属性集闭包

根据函数依赖能够推出的所有属性的集合，例子：

\begin{aligned} given \\ R &= (A, B, C, G, H, I) \\ F &= \{ \\ & \; A \rightarrow B, \\ & \; A \rightarrow C, \\ & \; CG \rightarrow H, \\ & \; CG \rightarrow I, \\ & \; B \rightarrow H, \\ \} \\ then \\ (AG)^+ &= \{A, B, C, G, H, I\} \end{aligned}

最小覆盖 Minimal Cover

也称最小函数依赖，可能不唯一。求解方式：

右侧化为单属性（多属性的拆开写）
去掉左侧冗余属性
去掉冗余函数依赖

正则覆盖 Canonical Cover

$F_c$ 是 $F$ 的正则覆盖，需要满足下列条件：

$F$ 逻辑蕴含所有 $F_c$ 中的依赖
$F_c$ 逻辑蕴含所有 $F$ 中的依赖
$F_c$ 中不包含无关的函数依赖
$F_c$ 中所有函数依赖左侧是不重复的

求解正则覆盖的方式：

先求最小函数依赖
将最小函数依赖合并，如 $A \rightarrow B$ , $A \rightarrow C$ 合并为 $A \rightarrow BC$

键

候选键：可以唯一标志一个原组
主键：从候选键中挑一个
主属性*：包含在任何一个候选键中的属性，称为主属性 primary attribute
非主属性：不包含在任何键中的属性 non-primary / non-key attribute
全键：整个属性组是码，all-key

例子：以下属性中

(A, B, C, D, E)

{A, B}，{B, C} 都可以唯一标志一个原组。则：

{A, B} 和 {B, C} 都是候选键
A, B, C 都是主属性（不管 {A, B} 和 {B, C} 哪个是主键）

基于函数依赖的关系模式范式*

\begin{aligned} 1NF \supset 2NF &\supset 3NF \supset BCNF \\ &\supset 4NF \supset 5NF \end{aligned}

其中 1 NF, 2 NF, 3 NF, BCNF 是函数依赖，4 NF, 5 NF 是多值依赖。

1 NF

作为二维表，关系要符合一个最基本的条件：每个分量是不可分开的数据项。

2 NF

在 1 NF 的基础上，每一个非主属性都完全函数依赖于任何一个候选键。换言之，2 NF 中没有部分函数依赖。如果一个关系模式不符合 2 NF，则会出现增删改异常，因为非主属性存在对候选键的部分依赖。

关系模式不符合 2 NF 的解决方式（1 NF 转 2 NF）：模式分解（拆表）

3 NF

因为存在传递函数依赖，所以只满足 2 NF 仍然存在数据冗余和增删改异常，因此需要更严格的规范化。因此，3 NF 的定义就是在 2 NF 的基础上，没有非主属性对候选键的传递函数依赖。从 2 NF 转 3 NF 的方法也是拆表。如果 $X \rightarrow Y \rightarrow Z$ ，则 $X$ , $Y$ 一个表， $Y$ , $Z$ 一个表。

BCNF

两种判断思路

每一个决定属性集都包含候选键（即所有箭头左边都是候选键）。
主属性内部不存在部分和传递依赖关系。

多值依赖

一个 $X$ 可以导出多个 $Y$ ，每个 $Y$ 之间可能也存在关系。

定义：设 $R(U)$ 是属性集 $U$ 上的一个关系模式。 $X, Y, Z$ 是 $U$ 的子集，并且 $Z = U - X - Y$ 。关系模式 $R(U)$ 中多值依赖 $X \rightarrow \rightarrow Y$ 成立，当且仅当对 $R(U)$ 的任一关系 $r$ ，给定的一对 $(x, z)$ 值，有一组 $Y$ 的值，这组值仅仅决定于 $x$ 值而与 $z$ 值无关。

4 NF

把多值依赖拆解成函数依赖。

关系模型的分解

无损连接分解

若 $R_1 \cap R_2 \rightarrow R_1$ 或 $R_1 \cap R_2 \rightarrow R_2$ ，则 $R_1$ 与 $R_2$ 是 $R$ 的 lossless-join decomposition 成立。

如：

\begin{aligned} R &= (A, B, C, D, E) \\ F &= {AB \rightarrow C, C \rightarrow DE} \\ R_1 &= (A, B, C) \\ R_2 &= (C, D, E) \\ \end{aligned}

$R_1$ 与 $R_2$ 是 $R$ 的无损连接分解。

函数依赖保持

(F_1 \cup F_2 \cup ... \cup F_n)^+ = F^+

如：

\begin{aligned} F &= \{A \rightarrow B, B \rightarrow C\} \\ F_1 &= \{A \rightarrow B\} \\ F_2 &= \{A \rightarrow C\} \end{aligned}

不是函数依赖保持的分解， $B \rightarrow C$ 函数依赖丢失了。

3 NF Decomposition Algorithm

将关系模型分解为第三范式，同时保持无损连接和函数依赖。

求 $F$ 的 canonical cover $F_c$
对 $F_c$ 中的每一个函数依赖 $\alpha \rightarrow \beta$ ，如果不存在包含 $\alpha$ 和 $\beta$ 的表，拆出一张新表 $R_n(\alpha, \beta)$
如果拆出的子表中没有任何一个包含候选键，则将候选键作为一个单独的子表