模式分解

---

模式S-C-M （S 学号，C 班级，M 班主任）

该模式设计不好，存在数据冗余、插入异常、删除异常和更新异常

p1 = {S-C(学号，班级)，C-M(班级，班主任)}
p2 = {S-C(学号，班级)，C-M(学号，班主任)}
p3 = {S-C(学号，班主任)，C-M(班级，班主任)}

---

---

规范化理论：

1. 检测是否在一个表中聚集了过多的属性的过程
2. 模式分解来消除违反范式规则而带来的影响（插入、更新、删除异常，冗余大），构造合适的(更好的)数据模式
3. 概念建模过程中规范化用于检验却总是很有帮助

---

---

数据依赖

1. 一个关系内部属性与属性之间的一种约束关系（属性值时候相同）
2. 现实世界属性间相互联系的抽象
3. 数据内在性质
4. 语义的体现

函数依赖FD

Sno	Sname	Ssex	Sage
a value	b1 value	c value	d value
a2 value	b2 value	c2 value	d2 value
…	…	…	…
an value	bn value	cn value	dn value

定义： 设 R(U) 是一个属性集 U 上的关系模式， X 和 Y 是 U 的子集。若对于 R(U) 的任意一个可能的关系 r ， r 中不可能存在两个元组在 X 上的属性值相等， 而在 Y 上的属性值不等， 则称“ X 函数确定 Y ”或“ Y 函数依赖于 X ”，记作 X → Y
若 Y 不函数依赖于 X ，则记作 X ↛ Y

For example：
Sno → Ssex， Sno → Sage
假设不允许重名 Sno ←→ Sname

---

1. 非平凡函数依赖

   X → Y ，但 Y ⊈ X 则称 X → Y 为非平凡函数依赖
   Y ⊈ X 换为 Y ⊆ X ，则 X → Y 为平凡函数依赖 （对于任一关系模式，必然成立）

2. 完全函数依赖

   如果 X → Y ，并且对于 X 的任何一个真子集 X’ , 都有 X’ ↛ Y , 则称 Y 对 X 完全函数依赖，

3. 部分函数依赖
4. 传递函数依赖

多值依赖MVD

---

关系模式

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

• R：符号化的元组语义
• U：一组属性
• F：属性组U中属性所来自的域
• DOM：属性到域的映射
• F：属性组U上的一组数据依赖

把关系模式看作一个三元组：$R<U,F>$

U ＝{Sno, Sdept, Mname, Cno, Grade}// 数据冗余、更新异常、插入异常、删除异常
// 分解
S(Sno,Sdept,Sno → Sdept);
SC(Sno,Cno,Grade,(Sno,Cno) → Grade);
DEPT(Sdept,Mname,Sdept → Mname)

范式

范式： 是符合某种基本的关系模式的集合

• 1NF：每个分量必须是不可分开的数据项
• 2NF：符合1NF，每一个非主属性都完全函数依赖于任何一个候选码
• 3NF：符合2NF，消除非主属性对于码传递函数依赖
• BCNF：符合3NF，消除主属性对于码的部分与传递函数依赖

4NF：设R是一个关系模型，D是R上的多值依赖集合。如果D中存在凡多值依赖 X->Y时，X必是R的超码，那么称R是第四范式的模式

满足BCNF:

• 实现了模式的彻底分解
• 最高的规范化程度
• 消除了插入异常和删除异常。

规范化： 低级范式的关系模式通过模式分解，可以转换为若干个高一级范式的关系模式集合的过程。

3NF 和 BCNF的区别
BCNF：如果关系模式R（U，F）的所有属性（包括主属性和非主属性）都不传递依赖于R的任何候选关键字，那么称关系R是属于BCNF的。或是关系模式R，如果每个决定因素都包含关键字（而不是被关键字所包含），则BCNF的关系模式。
例：配件管理关系模式 WPE（WNO，PNO，ENO，QNT）分别表仓库号，配件号，职工号，数量。有以下条件
a.一个仓库有多个职工。
b.一个职工仅在一个仓库工作。
c.每个仓库里一种型号的配件由专人负责，但一个人可以管理几种配件。
d.同一种型号的配件可以分放在几个仓库中。

分析：由以上得 PNO 不能确定QNT，由组合属性（WNO，PNO）来决定，存在函数依赖（WNO，PNO） -> ENO。由于每个仓库里的一种配件由专人负责，而一个人可以管理几种配件，所以有组合属性（WNO，PNO）才能确定负责人，有（WNO，PNO）-> ENO。因为 一个职工仅在一个仓库工作，有ENO -> WNO。由于每个仓库里的一种配件由专人负责，而一个职工仅在一个仓库工作，有 （ENO，PNO）-> QNT。
找一下候选关键字，因为（WNO，PNO） -> QNT，（WNO，PNO）-> ENO ，因此 （WNO，PNO）可以决定整个元组，是一个候选关键字。根据ENO->WNO，（ENO，PNO）->QNT，故（ENO，PNO）也能决定整个元组，为另一个候选关键字。属性ENO，WNO，PNO 均为主属性，只有一个非主属性QNT。它对任何一个候选关键字都是完全函数依赖的，并且是直接依赖，所以该关系模式是3NF。

分析一下主属性。因为ENO->WNO，主属性ENO是WNO的决定因素，但是它本身不是关键字，只是组合关键字的一部分。这就造成主属性WNO对另外一个候选关键字（ENO，PNO）的部 分依赖，因为（ENO，PNO）-> ENO但反过来不成立，而P->WNO，故（ENO，PNO）-> WNO 也是传递依赖。
虽然没有非主属性对候选关键辽的传递依赖，但存在主属性对候选关键字的传递依赖，同样也会带来麻烦。如一个新职工分配到仓库工作，但暂时处于实习阶段，没有独立负责对某些配件的管理任务。由于缺少关键字的一部分PNO而无法插入到该关系中去。又如某个人改成不管配件了去负责安全，则在删除配件的同时该职工也会被删除。

解决办法：分成管理EP（ENO，PNO，QNT），关键字是（ENO，PNO）工作EW（ENO，WNO）其关键字是ENO。
缺点： 分解后函数依赖的保持性较差。如此例中，由于分解,函数依赖（WNO，PNO）-> ENO 丢失了, 因而对原来的语义有所破坏。没有体现出每个仓库里一种部件由专人负责。有可能出现 一部件由两个人或两个以上的人来同时管理。因此，分解之后的关系模式降低了部分完整性约束。

---

模式分解实例

函数依赖理论

• 函数依赖集的闭包
  • 用于发现所有蕴含的函数依赖
• 属性集的闭包
  • 用于判断某属性集能够函数确定的其他因素
• 最小函数依赖集
  • 用于寻找等价( 闭包相同) 的最小集，便于降低检测开销
• 无损分解
  • 能够通过自然连接恢复原关系的分解策略
• 保持依赖
  • 分解后的各子关系函数依赖集并集的闭包与分解前某关系函数依赖集的闭包相同
    

相关计算

实例：求解函数依赖集的闭包

算法：求属性集X 关于函数依赖集F 的闭包

实例：

关系模式

第一范式（1NF）：关系模式 R 的每一个分量是不可再分的数据项，则关系模式 R 属于第一范式。

第二范式（2NF）：若关系范式 $R\in 1NF$ ，并且每一个非主属性完全依赖于码，则关系模式 $R\in 2NF$。
换而言之，只要通过分解 1NF 将其中的非主属性对码的部分函数依赖消除，那么分解后得到的关系模式称为 2NF 。

第三范式（3NF）：若关系范式 R（U，F）中不存在这样的码 X ，属性组 Y 和非主属性 Z（$Z⊈Y$）使得 $X\to Y(Y\nrightarrow X)$ ，$Y\to Z$ 成立，则关系模式 $R\in 3NF$。换言之，当消除了 2NF 中非主属性对码的传递函数依赖，得到的关系模式则称为 3NF 。

普通的关系模式通常因为存在部分依赖和传递依赖，而产生数据冗余和异常，所以需要将关系模式分解为性能较好的 3NF ，该模式不存在非主属性对码的部分函数依赖和传递函数依赖，所以性能较好。这种将普通的关系模式变换为 3NF 或更高级别范式的过程，称为 “关系模式的规范化处理”

---

例如，存在关系模式学生信息 StudentInfo 和函数依赖集合 F

StudentInfo(学号，姓名，地址，生源地，号码，所修课程编号，所修课程名称，所修课程学分)

F = {学号->姓名，学号->地址，地址->生源地，学号->号码，所修课程编号->所修课程名称，(学号,所修课程编号)->所修课程学分}

上面所示的关系模式是一个常见的 1NF ，每一个分量都无法再次分割。但是，如果直接使用该范式存储数据，那么将会有大量数据冗余，如果对学生号码进行修改，那么将需要对所有记录进行修改。

可以将 1NF 分解为 2NF ，即消除非主属性对码的部分函数依赖，这里的示例中，码为（学号，所修课程编号），那么将 StudentInfo 关系模式分解如下：

StudentInfo_1(学号，姓名，地址，生源地，号码)

StudentInfo_2(所修课程编号，所修课程名称)

StudentInfo_3(学号，所修课程编号，所修课程学分)

分解后的三个范式中的非主属性对其码都是完全函数依赖，但是，在 StudentInfo_1 中，仍然存在数据的冗余，因为非主属性生源地传递函数依赖于码学号，继续分解，消除该传递函数依赖。

StudentInfo_11(学号，姓名，地址，号码)

StudentInfo_12(地址，生源地)

由此，得到如下几个范式：

StudentInfo_11(学号，姓名，地址，号码)

StudentInfo_12(地址，生源地)

StudentInfo_2(所修课程编号，所修课程名称)

StudentInfo_3(学号，所修课程编号，所修课程学分)

这些范式都不存在部分函数依赖和传递函数依赖，所以都是第三范式。根据该范式进行数据的存储，能够使更好的避免数据的冗余及出错。

目录

1. 什么是关系模式的范式
2. 第一范式(1NF)
3. 第二范式(2NF)
4. 第三范式(3NF)
5. BC范式(BCNF)
6. 第四范式(4NF)
7. 第五范式(5NF)

---

什么是关系模式的范式

        关系模式的范式是衡量关系模式好坏的标准。范式的种类与数据依赖有着直接联系，满足不同程度要求的关系称为不同的范式等级。其中,满足最低要求的关系称为第一范式,简称1NF,以此类推,还有第二范式(2NF)、第三范式(3NF)、BC范式(BCNF)、第四范式(4NF)和第五范式(SNF)等多种。不同的范式表示关系模式遵守的不同规则。

各种范式之间是一种包含关系:    1NF⊃2NF⊃3NF⊃BCNF⊃4NF⊃5NF¹

---

1.第一范式(1NF)

定义：若关系模式R的每个关系r的属性值都是不可分的原子值,则称R是第一范式1NF (First Normal Form)的模式。

如，关系模式R存放的是学生信息：

姓名	性别	出生日期
		年	月	日
张三	男	1999	4	10
...	...	...	...	...

        虽然看上去将出生日期分成年月日更准确，但这种情况下出生日期不再是基本属性而是由年、月、日三个分属性组成的复合属性，因此 该模式不满足1NF的范式要求。

        应改成：

姓名	性别	出生日期
张三	男	1999/04/10
…	…	…

---

2.第二范式(2NF)

定义：1.对于FD W→A,若存在X⊆W有X→A成立,则称W→A是局部依赖(A局部依赖于W);否则称W→A是完全依赖。完全依赖也称为“左部不可约依赖”。
        2.若A是关系模式R中候选键属性,则称A是R的主属性:否则称A是R的非主属性。
        3.若关系模式R是1NF,且每个非主属性完全函数依赖于候选键,则称R是第二范式(2NF)的模式。若数据库模式中每个关系模式都是2NF,则称数据库模式为2NF的数据库模式。

        简单来说在满足第一范式的情况下，候选键与其他键都是完全依赖函数，那么此关系模式就是第二范式。

举个例子：关系模式如图所示，sno为学号，cno为课程号

sno	cno	grade
95001	1	92
95004	1	58
95002	2	90
95003	2	85

该关系模式中存在函数依赖：sno→grade,但该关系模式的主键是sno、cno，因此有(sno,cno)→grade，即存在非主属性对主键的部分依赖关系，所以此关系模式不满足第二范式要求。

应改成：

sno	cno
95001	1
95004	1
95002	2
95003	2

sno	grade
95001	92
95004	58
95002	90
95003	85

即通过模式分解，使任一非主属性都完全函数依赖与它的任一候选键，也就是消除非主属性对键的部分函数依赖。

---

3.第三范式(3NF)

定义：1.若x→Y, Y→A, 且Y-/->x和A⫋Y,则称X→A是传递依赖(A传递依赖于X)。
           2. 若关系模式R是1NF,且每个非主属性都不传递依赖于R的候选键,则称 R是第三范式(3NF)的模式。若数据库模式中的每个关系模式都是3NF,则称其为3NF的数据库模式。

3NF的目的是消除非主属性对键的传递函数依赖。

举个例子：
关系模式如图所示，Mname为系主任，sno为主属性

sno	sname	ssex	sage	sdept	Mname
95001	李勇	男	20	CS	张三
95002	刘晨	女	19	IS	李四
95003	王敏	女	18	MA	王五
95004	张立	男	19	IS	李四
95005	刘云	女	18	CS	张三

可知 sno→sname，sno→ssex，sno→sage，sno→sdept，sdept→Mname

因为sno→sdept，sdept→Mname
所以sno与Mname是传递依赖，因此该关系模式不满足第三范式要求

应改为：

sno	sname	ssex	sage	sdept
95001	李勇	男	20	CS
95002	刘晨	女	19	IS
95003	王敏	女	18	MA
95004	张立	男	19	IS
95005	刘云	女	18	CS

sdept	Mname
CS	张三
IS	李四
MA	王五

---

4.BC范式(BCNF)

定义: 若关系模式R是1NF,且每个属性都不传递依赖于R的候选键,则称R是 BCNF的模式。若数据库模式中的每个关系模式都是BCNF,则称为BCNF的数据库模式。

举个例子：
关系模式如图所示:其中候选键(sno,cno)，(sname,cno) ，假设不重名

sno	sname	cno	grade
95001	李勇	1	20
95001	李勇	2	30
95002	刘晨	2	19
95003	王敏	1	18
95004	张立	2	19
95005	刘云	1	18

该关系模式存在依赖：sno→sname，sname→sno，(sno,cno)→grade，(sname,cno)→grade

应该为：

sno	sname
95001	李勇
95002	刘晨
95003	王敏
95004	张立
95005	刘云

sno	cno	grade
95001	1	20
95002	2	19
95003	1	18
95004	2	19
95005	1	18

---

5.第四范式

定义：设关系R（X，Y，Z），其中X，Y，Z是成对的、不相交属性的集合。若存在非平凡多值依赖，则意味着对R中的每个属性 Ai(i=1,2,…,n)存在有函数依赖 X→Ai（X必包含键）。那么 称R是第四范式的模式 。

        也就是说，当一个表中的非主属性互相独立时（3NF），这些非主属性不应该有多值。若有多值就违反了第四范式。

举个例子：
        当我们统计一个人电话号码时，他可能有多个手机号码或固定电话。name为主键
这时关系模式为：

name	cellphone	telephone
李勇	131xxxxxxxx	0551-xxxxxxxx
李勇	139xxxxxxxx	0539-xxxxxxxx

这样在日后维护中可能产生不必要的麻烦，比如当用户弃用第一行的手机号码和第二行的固定电话号码时，两行会合并吗？
此时违反了第四范式要求

应改为：

name	type	phone
李勇	telephone	0551-xxxxxxxx
李勇	cellphone	139xxxxxxxx
…	…	…

---

6.第五范式

定义：如果关系模式R中的每一个连接依赖均由R的候选码所隐含²，则称此关系模式符合第五范式。

例如：有一个销售信息表。

name	company	item
李勇	xxxx	xxxx
…	…	…

此时违反了每一个连接依赖均由R的候选码所隐含的要求。
应改为：

name	company
李勇	xxxxx
…	…

company	item
xxxxx	xxx
…	.

name	item
李勇	xxx
…	…

---

总结：

        规范化的过程就是在数据库表设计时移除数据冗余的过程。随着规范化的进行，数据冗余越来越少，但数据库的效率也越来越低. 这就要求在数据库设计中，能结合实际应用的性能要求，规范到合适的范式。

        规范化的过程可概括如下：
（1）取原始的1NF关系投影，消去非主属性对键的部分函数依赖，从而产生一组2NF关系。
（2）取2NF关系的投影，消去非主属性对键的传递函数依赖，产生一组3NF关系。
（3）取这些3NF的投影，消去决定因素不是键的函数依赖。产生一组BCNF关系。
（4）取这些BCNF关系的投影，消去其中不是函数依赖的非平多值依赖，产生一组4NF关系。
（5）取4NF关系的投影，消除不是由候选码所蕴含的连接依赖，产生一组5NF关系。

---

1. 即：第三范式一定是第二范式也一定是第一范式······· ↩︎

2. 指在连接时，所连接的属性均为候选码 ↩︎