第四章 关系模式的规范化设计理论

基本概念

• 候选码：能唯一决定一个元组的一个最小属性集合（可以有多个属性，一个关系中也可以有多个候选码）。
• 超码：包含候选键的属性集合，候选码是最小的超码。
• 主码：从候选码中任意挑出一个为主码。
• 主属性：包含在任意一个候选码中的属性。
• 非主属性：除主属性外的属性。
• 码：主码、候选码都简称码。
• 全码：所有属性都为主属性。

数据库设计存在的问题

假设有关系模式StudyInfo(Sno, Sname, Dname, Dhead, Cname, Grade)，主键为{Sno, Cname}。这一关系模式存在以下几个异常问题：

• 插入异常：应该插入的无法插入。没有被选修的课程无法存入数据库、没有选课的学生无法存入数据库。
• 删除异常：不该删除的被删除了。某个系的学生毕业时需要删除系主任。
• 数据冗余：许多属性值重复出现，浪费空间。
• 更新异常：更新后造成数据不一致。系主任姓名更新。

为何会出现以上问题？因为属性间存在过多的数据依赖。

数据依赖

1. 函数依赖：相当于数学中的函数，U是属性全集，x和y是U上的子集，x对应唯一确定的y，即x->y（y依赖于x）。（书中的非平凡函数依赖和平凡函数依赖即非子集与子集）
2. 部分函数依赖：如果x->y，且对x的任一真子集x’，存在x’->y。
3. 完全函数依赖：如果x->y，且对x的任一真子集x’，都有x’->y不成立。
4. 传递依赖：如果x->y，且y->z，则x->z。

数据库范式

范式是衡量数据库规范化程度的标准，但数据库规范化程度并非越高越好。规范化程度高，意味着分解的程度高，对分解了的关系进行一些复杂的查询操作时，就必须花费更多时间进行关系的连接运算，而在原来的关系模式中，只需要进行单个关系上的选择和投影即可。
常用的范式有4个，级别越高，规范化程度越高。

第一范式(1NF)

• 所有属性不可再分，即第一范式。

StudyInfo(Sno, Sname, Dname, Dhead, Cname, Grade)就是一个第一范式。
第一范式并不是一个好的关系模式，它存在刚刚所说的四个问题。

第二范式(2NF)

• 第一范式基础上，每个非主属性完全函数依赖于每个主属性。

第二范式在第一范式的基础上，使每个非主属性完全依赖于每个主属性，故StudyInfo中的部分函数依赖为：（此处的->代表部分依赖）
{Sno, Cname} -> Sname
{Sno, Cname} -> Dname
因此，为了消除部分函数依赖，StudyInfo分解为
StudentDept(Sno, Sname, Dname, Dhead)
Report(Sno, Cname, Grade)
第二范式使数据冗余问题得到了解决（主属性非主属性一一对应），但有删除异常、插入异常依然存在。

第三范式(3NF)

• 第二范式基础上，每个非主属性不存在对码的传递依赖。

全码一定是3NF。以上例子在3NF中可以继续分解：
StudentDept中存在：Sno->Dname->Dhead，因此将StudentDept分解为：
Dept(Dname, Dhead)
Student(Sno, Sname, Dname)
Report(Sno, Cname, Grade) （这个没有进行分解）

BC范式(BCNF)

• 第一范式基础上，不存在任何属性对码的传递依赖和部分依赖。
• 重点考察
  ```sql R(A, B, C) F = {AB->C, CB->A, C->B}

1. 找出其中的候选码。 AB / BC
2. 判断关系模式是否为BCNF范式。 思路：是否每一个左边的属性都为候选码。 题解：不是，因为C是决定性元素，但C不包含码。
3. 若一个关系模式是BCNF范式，为什么？ 该关系模式不存在任何属性对码的传递依赖和部分依赖。 ```

候选码

如何确定候选码？若该码闭包为全集U，且不存在冗余属性，我们将其称为候选码。
设关系模式R中U=ABC……等N个属性，U中的属性在F中有四种范围：

1. 左右出现
2. 只在左部出现
3. 只在右部出现
4. 左右都不出现 ```sql
5. 只在F右部出现的属性，不属于候选码
6. 只在F左部出现的属性，一定存在于某候选码中
7. 两边都没有出现的属性，一定在候选键中
8. 其他属性逐个与满足2,3的属性组合，求属性闭包，若闭包等于U，则该属性组合为候选码

— 例题1 R U = {A, B, C, D, E} F = {AB->C, AB->E, CDE->AB} 求R的候选码。 D只在左部出现，因此，求以下闭包： (AD)+ = {AD} (BD)+ = {BD} (CD)+ = {CD} (DE)+ = {DE} 不存在闭包=U，因此，我们求更多属性组合的闭包： (ABD)+ = {ABCDE} (ACD)+ = {ACD} (ADE)+ = {ADE} (CDE)+ = {ABCDE} 闭包(ABD)+ = U, 因此候选键为ABD/CDE。

— 例题2 R U = {A, B, C, D, E, G} F = {AB->C, CD->E, E->A, A->G} 求R的候选码。 B和D只在左部出现，G只在右部出现，一定不是候选码，不用求其闭包。 因此求以下闭包： (ABD)+ = {ABCDEG} (BCD)+ = {ABCDEG} (BDE)+ = {ABCDEG} 因此候选码为ABD/BCD/BDE

<a name="0edb4c85"></a>
### 闭包
- 闭包：通过给定属性能直接/间接推出的属性集的集合。
```sql
-- 例题：给定依赖集，求闭包
U = {A, B, C, D, E}
F = {AB->C, B->D, C->E, CE->B, AC->B}
求{A, B}+（即求AB的闭包）: 
设X+={A, B}
在F中有AB->C,
X+={A, B, C}
在F中有B->D,
X+={A, B, C, D}
在F中有C->E
X+={A, B, C, D, E}

最小函数依赖集

在F中的每个依赖，都不可以被其他依赖推出，且右边一定只有一个属性。如F = {A->B, B->C, A->C}不是最小函数依赖集，因为A->C可以由另外两个推出。（根据求闭包的顺序，最小函数依赖集可能并不唯一）

-- 例题1
已知关系模式R(U, F), U = {A, B, C, D, E, F, G},
F = {BCD->A, BC->E, A->F, F->G, C->D, A->G}
求F的最小函数依赖集。
-- 先将右边的元素都拆分为单个属性，如F={A->BC, B->D}就拆成{A->B, A->C, B->D}
这里右边都是单个属性，不用拆
-- 除去本身的依赖集求闭包
(BCD)的闭包 = BCDE, 推不出A, 满足条件
(BC)+ = ABCDFG, 推不出E, 满足条件
(A)+ = AG
(F)+ = F
(C)+ = C
(A)+ = FG -- 之前的A闭包除去了自身的依赖A->F所以结果不同
最后一个闭包可以推出G, 不满足条件，将A->G去除，
得到F1{BCD->A, BC->E, A->F, F->G, C->D}
-- 左部最小化：去除左部任意属性，看依赖是否依然成立
BCD->A中，有C->D，最小化得到BC->A
其他依赖都无法最小化
因此最小函数依赖集Fmin为{BC->A, BC->E, A->F, F->G, C->D}
-- 例题2: 建议先自己尝试
设F = {C->A, CG->D, CG->B, CE->A, ACD->B}, 求最小函数依赖集：
F = {C->A, CG->D, CG->B, CE->A, ACD->B}
(C)+ = C
(CG)+ = AB
(CG)+ = AD
(CE)+ = A, 不满足条件，去除
(ACD)+ = A
得到F1 = {C->A, CG->D, CG->B, ACD->B}
ACD->B中，有C->A，最小化得到CD->B
因此最小函数依赖集Fmin为{C->A, CG->D, CG->B}

模式分解

• 无损分解：分解之后可以通过自然连接结合起来（分解后每个关系中有相同字段）
• 保持函数依赖：分解之后可以还原

  -- 例题
  U = (A, B, C, D, E), F = {AB->C, C->D, D->E}, 
  R1(A, B, C), R2(C, D), R3(D, E)该分解是否具有无损连接性？
  使用表格法，用a代表有，b代表无，按分解好的关系画初始表格（因为有5个属性3个关系，因此表格为3行5列，且行标为关系，列标为属性）

  | 初始表格 | A | B | C | D | E | | —- | —- | —- | —- | —- | —- | | ABC | a1 | a2 | a3 | b14 | b15 | | CD | b21 | b22 | a3 | a4 | b25 | | DE | b31 | b32 | b33 | a4 | a5 |

按照F中的依赖来对表格进行变换，看相同列不同行是否具有相同分量，有则可以根据依赖对该分列进行推导。
先看第一行AB->C，没有相同分量a1和a2，PASS。
第二行C->D，第1行具有相同分量a3，因此表格变为：

第三行D->E，第1、2行具有相同分量a4，因此表格变为：

表中第1行全为a，因此该分解具有无损连接性。