数据库引论：5、关系数据库设计理论

5.1 好的关系设计的特点

没有冗余，例如 $in\_dep$ 模式:
$in\_dep(ID,name,salary,dept\_name,building,budget)$
表示 $in s t r u c t or$ 和 $d e p a r t m e n t$ 的关系上进行自然连接的结果，但实际上存在许多冗余，对于同一个院系的老师(例如 $C o m p . S c i .$ )，每一个元组都在 $b u i l d in g$ 属性上冗余了。

此外，如果想要创建一个新的院系，是一件比较麻烦的事情，或许可以通过插入空值来实现，但这样可能会导致不可预料的错误。

那么这个模式就不是一个好的关系

5.1.1 分解

避免模式中信息重复的唯一方式是将其分解为两个模式，单并非所有的模式分解都是有益的，例如：
$e m pl oyee (I D, nam e, s t ree t, c i t y, s a l a ry)$
分解为以下两个模式：
$KaTeX parse error: Expected 'EOF', got '&' at position 2: &̲employee1(ID,na\dots$
存在如下缺陷：如果存在同名的两个员工，我们将其自然连接后，无法分辨到底是谁，反而多了很多无意义的元组。实际上，分解后得到了更多的元组，但却获得了更少的信息，这是因为我们丢失了正确连接的信息。

我们将这样的分解称为有损分解，而将那些没有信息丢失的称为无损分解。

图1 不好的分解导致信息丢失

5.1.2 无损分解

令 $R$ 为关系模式，并令 $R_1$ 和 $R_2$ 构成 $R$ 的分解，即 $R=R_1\cup R_2$ ,如果对于所有合法的数据库实例，关系 $r$ 都包含与下述SQL查询的结果相同的元组集，我们称该分解是无损的：

	select *
	from (select R1 from r)
		natural join
		(select R2 from r)

或用关系代数表示为: $\Pi_{R_1}(r)\Join \Pi_{R_2}(r)=r$

类似的，如果 $r$ 是真子集，即$r\sub\Pi_{R_1}®\Join \Pi_{R_2} $,那么分解是有损的

5.2 使用函数依赖进行分解

在真实世界中的数据上通常存在各种约束(规则)。例如，在一个大学数据库中期望满足的一些约束有:

学生和教师通过他们的ID来唯一识别
每位学生和教师只有一个名字
每位教师和学生只(主要)关联一个系
每个系只有一个预算值，并且只有一栋关联的办公楼

一个关系的满足所有这种真实世界约束的实例被称为该关系的合法实例(legal instance)

5.2.2 码和函数依赖

在之前，我们将超码定义为：能够一起来唯一标识出关系中一个元组的一个或多个属性的集合。在这里，重新定义如下：

给定 $r (R)$ ， $R$ 的一个子集 $K$ 是 $r (R)$ 的超码的条件是：

在 $r (R)$ 的任意合法实例中，对于 $r$ 的实例中的所有元组对 $t_1$ 和 $t_2$ 总满足：若 $t_1\ne t_2$ 则 $t_1[K]\neq t_2[K]$ ,也就是在关系 $r (R)$ 的任意合法实例中，不存在两个元组在属性值 $K$ 上具有相同的值。

考虑一个关系模式 $r (R)$ ，并且令 $\alpha \subseteq R$ 且 $\beta \subseteq R$ 。

给定 $r (R)$ 的一个实例，如果对于该实例中的所有元组对 $t_1$ 和 $t_2$ ，使得若 $t_1[\alpha]=t_2[\alpha]$ ，则 $t_1[\beta]=t_2[\beta]$ 也成立，那么我们称该实例满足函数依赖 $\alpha \rightarrow \beta$
如果 $r (R)$ 的每个合法实例都满足函数依赖 $\alpha\rightarrow \beta$ ，则我们称该函数依赖在模式 $r (R)$ 上成立(hold)

利用函数依赖的表达方式，我们可以对超码和候选码进行重新定义

$K$ 是关系表 $R$ 的一个超码，如果 $K\rightarrow R$

$K$ 是关系表 $R$ 的一个候选码，如果 $K\rightarrow R \ and\ no \ a\subset K,a\rightarrow R$

考虑之前提过的模式：
$in\_dep(ID,name,salary,dept\_name,building,budget)$
对于一个系，他的预算是唯一的，那么函数依赖 $dept\_name\rightarrow budget$ 成立，此外，属性对 $ID,dept\_name)$ 构成 $in\_dep$ 的一个超码，可写作：
$ID，dept\_name \rightarrow name,salary,building,budget$
我们可以发现，函数依赖是否成立，取决于现实世界的一些约束，比如一个学生只能有一个院系，那么 $student\_ID\rightarrow dept\_name$ 是成立的，而相反，尽管表中的每一个实例都满足某一个依赖，也不能断定函数依赖成立。

有些函数依赖被称为是平凡的(trival)，因为它们被所有关系满足，例如 $A\rightarrow A,AB\rightarrow A$ ,一般地，如果 $\beta \subseteq \alpha$ ，则形如 $\alpha\rightarrow \beta$ 地函数依赖是平凡的。

一个关系的实例可能满足的某些函数依赖并不需要在关系的模式上成立。

闭包:包含集合 $F$ 中的所有函数依赖。使用符号 $F^+$ 来表示，即为能够从给定的集合 $F$ 推导出的所有函数依赖的集合。

Armstrong’s Axiom

自反律：如果 $\beta \subseteq \alpha$ ，则 $\alpha \rightarrow \beta$
增广律：如果 $\alpha\rightarrow \beta$ ，则 $\gamma\alpha\rightarrow \gamma\beta$
传递律：如果 $\alpha\rightarrow\beta,\beta\rightarrow\gamma$ ，则 $\alpha\rightarrow\gamma$

这个公理是正确且完备的

通过公理可推导出：

合并规则：如果 $\alpha\rightarrow\beta,\alpha\rightarrow\gamma$ ,则 $\alpha\rightarrow\beta\gamma$
分解规则：如果 $\alpha\rightarrow\beta\gamma$ ，则 $\alpha\rightarrow\beta,\alpha\rightarrow\gamma$
伪传递规则：如果 $\alpha\rightarrow\beta,\gamma\beta\rightarrow\delta$ ,则 $\alpha\gamma\rightarrow\delta$

例子:
$R=(A,B,C,G,H,I)\ F=\{A\rightarrow B,A\rightarrow C,CG\rightarrow H,CG\rightarrow I,B\rightarrow H\}$

则 $A\rightarrow H,AG\rightarrow I,CG\rightarrow HI,\cdots \in F^+$

属性集闭包(Closure of attributes sets)

给定一组属性 $\alpha$ ，定义属性 $\alpha$ 在 $F$ 下的闭包为： $\alpha\rightarrow\beta \in F^+ \Longleftrightarrow \beta \subseteq \alpha^+$

计算 $\alpha^+$ 的算法：
$KaTeX parse error: Expected 'EOF', got '&' at position 2: &̲result:=\alpha;…$
例子：

$R=(A,B,C,G,H,I),F=\{A\rightarrow B,A\rightarrow C,CG\rightarrow H,CG\rightarrow I,B\rightarrow H\}$

计算 $AG)^+$

result = AG

result = ABCG( $A\rightarrow C ,A\rightarrow B$ )

resullt = ABCGH ( $CG\rightarrow H$ )

result = ABCGHI=R ( $CG\rightarrow I$ )

$A G$ 是超键吗？

是否有 $AG\rightarrow R$ ? 显然 $R\subseteq (AG)^+$

$A G$ 是候选码吗？

是否有 $A\rightarrow R$ ？计算可得 $A)^+=ABCH$ ,

是否有 $G\rightarrow R$ ？计算可得 $G)^+=G$

最小覆盖(Canonical cover)

例如：

在右边： $\{A\rightarrow B,B\rightarrow C,A\rightarrow CD\}$ 可被简化为 $\{A\rightarrow B,B\rightarrow C,A\rightarrow D\}$ (缩小的过程)
在左边： $\{A\rightarrow B,B\rightarrow C,AC\rightarrow D\}$ 可被简化为 $\{A\rightarrow B,B\rightarrow C,A \rightarrow D\}$ (放大的过程)

最小覆盖：最简形式的 $F$

无关属性：考虑 $F$ 中的一个依赖 $\alpha\rightarrow \beta$

属性A在左侧是无关的：如果 $A\in \alpha$ 并且 $F$ 满足， $(F-\{\alpha\rightarrow \beta\})\cup\{(\alpha-A)\rightarrow\beta\}$
属性A在右侧是无关的：如果 $A\in\beta$ 并且 $F$ 满足， $(F-\{\alpha\rightarrow\beta\})\cup\{(\alpha\rightarrow(\beta-A))\}$

检测某一属性是否多余

考虑 $\alpha\in\beta$

为了检测左侧的属性 $A$ 是否多余：
- 利用 $F$ 中的依赖，计算 $(\{\alpha\}-A)^+$
- 检查这个闭包，如果包含 $\beta$ ，那么A是多余的
为了检测右侧的属性 $B$ 是否多余：
- 利用 $F'=(F-\{\alpha\rightarrow\beta\}\cup\{\alpha\rightarrow(\beta-A)\})$ 中的依赖关系，计算闭包 $\alpha ^+$
- 如果闭包包含A，那么确实多余。

最小覆盖的严格定义

$F$ 的最小覆盖是依赖的一个集合 $F_c$ ，满足：

$F$ 可以推导出 $F_c$ 中的所有关系，反之亦然
$F_c$ 中的所有依赖没有多余的属性
$F_c$ 中的所有依赖，他们的左边都是唯一的，例如，没有这样两个依赖： $\alpha_1\rightarrow\beta_1,\alpha_2\rightarrow\beta_2$ ,有 $\alpha_1=\alpha_2$

计算最小覆盖的算法

伪代码：

repeat

用集合的并来替换 $F$ 中形如 $\alpha_1\rightarrow\beta_1\ and\ \alpha_2\rightarrow\beta_2$ 为 $\alpha_1\rightarrow\beta_1\beta_2$

找多余的属性，并删除

until F不再变化

找候选码

对于 $R(A_1,A_2,\cdots,A_n)$ 以及 $F$ 中的依赖关系，所有属性都可以被分类为4类：

$L$ :属性只出现在左侧
$R$ :属性只出现在右侧
$N$ :属性在两侧均未出现
$L R$ :属性出现在两侧

算法伪代码：

对所有属性分类： $x$ 代表 $L$ 和 $N$ 类， $y$ 代表 $L R$ 类
计算 $x^+$ ，如果 $x$ 包含 $R$ 中的所有属性，那么 $x$ 就是唯一的候选码，结束算法
在 $y$ 中取属性 $A$ ,计算 $xA)^+$ ，如果 $xA)^+$ 包含 $R$ 中的所有属性，那么 $x A$ 是 $R$ 的一个候选码。继续选取，知道 $y$ 中属性的所有组合都被选过
结束，输出结果

无损链接分解

即无损分解，对于 $R$ 表中的所有属性，必须出现在分解 $R_1,R_2)$ 中,即 $R=R_1\cup R_2$ ，对于 $R$ 上所有可能的关系 $r$ ，有 $r=\Pi_{R_1}(r)\Join \Pi_{R_2}(r)$ 。

无损分解的判断

对于 $R)=(R_1,R_2)$ ，它是一个无损分解，当且仅当

$R_1 \cap R_2 \rightarrow R_1$
$R_1\cap R_2 \rightarrow R_2$

至少满足一个。

例如：给定 $R < U, F >$ , $U=\{A,B,C,D,E\},F=\{AB\rightarrow C,C\rightarrow D,D\rightarrow E\}$ ， $R$ 上的一个分解为： $R 1 (A, B, C), R 2 (C, D), R 3 (D, E)$ ，判断是否为无损分解

$P roo f :$
$R1\cap R2=C\\ C\rightarrow ABC \ ? 没有这个依赖关系\\ C\rightarrow CD \ √ \\ R2 \cap R3= D \\ D\rightarrow CD \ ? 没有这个依赖关系\\ D\rightarrow DE \ √$
所以是无损分解。