MySQL版数据库原理与应用-----学习篇4_数据库原理与应用第四范式

4.1 问题的提出

4.1.1 一个泛关系模式的实例

 1. 内容回顾：

• 关系：描述实体、实体间的联系。从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。
• 关系模式：用来定义关系的逻辑结构。
• 关系数据库：基于关系模型的数据库，利用关系来描述现实世界。从形式上看，它由一组关系组成。
• 关系数据库的模式：定义这组关系的关系模式的全体。
• 关系模式由五部分组成，即它是一个五元组： R(U，D，DOM，I，F)。

 2. 数据依赖：

• 就是关系中属性间互相依存、互相制约的关系。
• 完整性约束的表现形式：限定属性取值范围，例如学生成绩必须在0-100之间。
• 定义属性值间的相互关连（主要体现于值的相等与否），这就是数据依赖，它是数据库模式设计的关键。
• 是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系。
• 是现实世界属性间相互联系的抽象。

 3. 泛化模式产生的问题：

• 数据内部的联系表现为同一关系模式中各个属性间的依赖关系，即数据依赖。对数据依赖的不恰当处理是产生数据冗余和操作异常的重要原因。
• 解决方法：将关系模式进一步分解。

4.1.2 规范化理论的提出

 1. 将属性之间的关联分为若干等级，形成“ 规范化 ”理论。
 2. “ 关系规范化 ”理论包含两个核心的问题：

• (1) 如何判断关系模式中存在的问题：通过分析关系模式中的数据依赖关系，判断关系模式的“范式”级别，从而得到这种模式中可能存在的数据冗余和操作异常问题。
• (2) 如何解决关系模式中存在的问题，即对关系模式进行分解。

4.2 函数依赖和范式

4.2.1 函数依赖的概念

 1. 数据依赖包括：函数依赖、多值依赖、连接依赖、分层依赖、相互依赖。函数依赖是最常见、最重要的一种数据依赖。
 2. 函数依赖的概念：

• 定义：设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r，r 中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作X→Y。
• 或者说：关系模式R(U)的任一具体关系，属性集X在任意元组上的值能唯一决定属性集Y在该元组上的值，则称X函数确定Y或Y函数依赖于X，记作X→Y。
• 或者说：设R(U)是一个关系模式，X，Y是U的子集，对于R中X的每一个值都有Y的唯一值与之对应，则称X函数确定Y或Y函数依赖于X，记作X→Y。

 3. 由函数依赖定义可以导出下列概念：

• (1) 决定因素：若X →Y，则X叫做决定因素。
• (2) 平凡的函数依赖：X →Y，Y含与X，则称X→Y是平凡的函数依赖。
• (3) 非平凡的函数依赖:X →Y，且X不包含Y，则称X→Y是非平凡的函数依赖。
• (4) 互相依赖：若X→Y， Y→X，则记作X ←→Y。

 4. 函数依赖类型：

• 完全函数依赖。
• 部分函数依赖。
• 传递函数依赖。

例如：设车间考核职工完成生产定额关系W(日期，工号，姓名，工种，超额，定额，车间，车间主任)。
则存在的函数依赖为F(工号→ 姓名，工号→ 工种，工种→ 定额，工号→ 车间，车间→ 车间主任，日期、工号→ 超额)。
函数依赖图如下所示：

 4. 码的函数依赖定义：

• 候选码：设K为R(U，F)中的属性或属性组，若K→U ，则K为R的候选码。
• 主码：若候选码多于一个，则选定其中的一个为主码。
• 主属性：包含在任何一个侯选码中的属性。
• 非主属性：不包含在任何码中的属性。
• 全码：是整个属性组。
• 外码: 关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外码。
• 超码: 一个包含关键字的属性集合也能用函数决定（不是完全函数依赖，而是部分函数确定）属性全集，这种包含主码的属性集合称为超码。

4.2.2 范式

 1. 范式的种类：

• 第一范式(1NF)。
• 第二范式(2NF)。
• 第三范式(3NF)。
• BC范式(BCNF)。
• 第四范式(4NF)。
• 第五范式(5NF)。

 2. 某一关系模式R为第n范式，可简记为R∈nNF。
 3. 第一范式：满足关系的每一个分量是不可分的数据项这一条件的关系模式就属于第一范式(1NF)。

 4. 第二范式：若R∈1NF，且每一个非主属性完全函数依赖于码，则R∈2NF。


 5. 第三范式：关系模式R（U,F）中若不存在这样的码X，属性组Y及非主属性组Z，使得X→Y，Y→Z成立，则称R（U，F）∈3NF。 即：若R ∈3NF，且每一个非主属性既不部分依赖于码也不传递依赖于码。 若R ∈2NF，且每一个非主属性不传递依赖于码，则R ∈3NF。

 6. BCNF：也叫扩充的3NF。关系模式R(U，F) ∈1NF。若 X→Y且Y⊈ X时X必含有码，则R(U，F) ∈BCNF。即：关系模式R(U，F) 中，若每一个决定因素都包含码，则R(U, F)∈BCNF。

• 所有非主属性对每一个码都是完全函数依赖。
• 所有主属性对每一个不包含它的码也是完全函数依赖。
• 没有任何属性完全函数依赖于非码的任何一组属性。

例如1：关系模式SJP（S，J，P）。其中：S：学生（学生选修课程有一定的名次）；J：课程（每门课程中每一名次只有一个学生）；P：名次（名次没有并列）。
函数依赖：（S，J）→ P，（J，P）→ S。分析得知：SJP ∈ 3NF，SJP ∈ BCNF。

例如2：关系模式STJ（S，T，J）。其中： S：学生（某一学生选定某门课，就对应一个固定教师）；T：教师（每个教师只教一门课）；J：课程（每门课有若干教师）。
函数依赖：（S，J）→ T ，（S，T）→ J，T→ J。分析得知：STJ ∈ 3NF，但是：STJ不属于BCNF。因为： T → J，而T不是码。

4.2.3 关系模式的规范化

 1. 一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。
 2. 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化。
 3. 关系模式规范化的基本步骤如下图所示：

4.3 数据依赖的公理系统

4.3.1 函数依赖集的闭包

 1. 函数依赖集F的逻辑蕴含：对于R(U,F)，如果X→Y不在F中，但是对于其任何一个关系r，X→Y都成立，则称F逻辑蕴含X→Y。或者说： X→Y可以由F导出。

例如：关系模式R(U，F)，其中U(A，B，C，D，E，F，G)，F(A→B，C→D，AB→E，F→G)。
则F逻辑蕴含A→E。

 2. 函数依赖集闭包：所有被一个已知函数依赖集F及F逻辑蕴涵的那些函数依赖的集合为F的闭包（Closure），记为F+ 。

4.3.2 函数依赖的推理规则

 1. Armstrong公理系统：

• 自反律：若Y含于X，则X→Y为F所蕴含。
• 增广律：若X→Y为F所蕴含，且Z含于U，则XZ→YZ为F所蕴含。
• 传递律：若X→Y，Y→Z为F所蕴含，则X→Z为F所蕴含。

 2. 由自反律、增广律、传递律可以导出下面三条推理规则：

• 合并规则：由X→Y，X→Z，有X→YZ。
• 分解规则：由X→Y及Z含于Y，有X→Z。
• 伪传递规则：由X→Y，WY→Z，有XW→Z。

 3. 定理：若Ai(i=1,2,…,n)是关系模式R的属性，所以X→{A1,A2,…,An}成立的充分必要条件是X→Ai均成立。

例如：证明对R（A，B，C，G，H，I），F＝｛A→B，A→C，CG→H，CG→I，B→H｝，存在：A→H，CG→HI，AG→I。
由于A→B，B→H，依传递律，可得A→H。
由于CG→H，CG→I，依合并规则，可得 CG→HI。
由于A→C，CG→I，依伪传递律，可得AG→I。也可由A→C，依增广律，得AG→CG，又CG→I，依传递律，得：AG→I。

4.3.3 属性集闭包与F逻辑蕴涵的充要条件

 1. X关于函数依赖集F的闭包：设F为属性集U上的一组函数依赖，X含于U，XF+={A|X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包。

例如：设关系模式R（A、B、C）的函数依赖集为F={A → B,B → C}，分别求A、B、C的闭包。
求A的闭包：若X=A，A→B，B→C （已知），则A→C（传递律），A→A（自反律），所以XF+={A，B，C}。
求B的闭包：若X=B，因为B→B，B→C，所以XF+={B，C}。
求C的闭包：若X=C，因为C→C，所以XF+={C}。

 2. F逻辑蕴涵的充要条件：设F为属性集U上的一组函数依赖，X,Y含于U， X→Y能由F根据Armstrong公理导出的充分必要条件是Y含于XF+。
 所以判定X→Y是否能由F根据Armstrong公理导出的问题，可以转化为求出XF+，判定Y是否为XF+的问题。
 3. 求属性集闭包XF+的算法，如下图所示：

例如1：

例如2：

 4. 对于属性闭包算法的终止条件，下列四种方法是等价的：

• X(i+1) = X(i)。
• 当发现X(i) 包含了全部属性时。
• 在F中的函数依赖的右部属性中，再也找不到X(i) 中未出现过的属性。
• 在F中未用过的函数依赖的左部属性中已没有X(i) 的子集。

 5. 码值理论：对于给定的关系R（A1，A2，……，An）和函数依赖集F，可将其属性分为4类。

• L类 仅出现在F的函数依赖左部的属性。
• R类 仅出现在F的函数依赖右部的属性。
• N类 在F的函数依赖左右两边均未出现的属性。
• LR类 在F的函数依赖左右两边均出现的属性。

 6. 求候选码的相关定理：

• 对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，则X一定是R的候选码的成员。
• 对于给定的关系模式R及其函数依赖集F，若X（X∈R）是N类属性，则X一定是R的候选码的成员。
• 对于给定的关系模式R及其函数依赖集F，若X（X∈R）是R类属性，则X必不在任何候选码中。
• 对于给定的关系模式R及其函数依赖集F，若X（X∈R）是LR类属性，则X可能是R的候选码的成员。

 7. 多属性依赖集候选关键字求解算法，如下图所示：

例如：设有关系模式R（A，B，C，D，E，P），R的函数依赖集为：F={A→D，E→D，D→B，BC →D，DC →A}，求R的候选码。
因为 C，E是L类属性，P是N类属性，所以CEP包含在所有候选码中；因为 （CEP）＋＝ABCDEP；所以 CEP是R的唯一候选码。

4.3.4 函数依赖集的等价和最小函数依赖集

 1. 等价定义：如果G+=F+，则称F与G等价，记为F=G。
 2. F+=G+的充分必要条件是F含于G+且G含于F+。

例如：R(U) U=ABC，F={A→B，B→C，A→C，AB→C,A → BC}，可以写成：G={A→B，B→C}。F与G等价。
证明：
1：A→B，B→C，传递规则 A→C 。
2： A→B，得AB → B，再由B→C，所以 AB→C。
3： A→B，B→C，扩展 B→BC，所以 A → BC。

 3. 最小依赖集定义：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，也称最小依赖集或最小覆盖。

• F中任一函数依赖的右部仅含有一个属性。
• F中不存在这样的函数依赖X→A，使得F与F—{X →A}等价。
• F中不存在这样的函数依赖X→A，X有真子集Z使得F—{X →A}∪{Z→A}与F等价。

 4. 求Fm （F的最小依赖集）的算法，如下图所示：

4.4 关系模式的分解方法

4.4.1 模式分解的概念

 1. 模式分解的等价性，实施分解三个不同的准则：

• 分解具有“ 无损连接性 ”。
• 分解要“ 保持函数依赖 ”。
• 分解既要“ 保持函数依赖 ”又要具有“ 无损连接性 ”。

例如：设一关系模式R(T#，TD，DH)，其中T#表示教师编号，TD表示教师所属系部，DH表示系主任名。假定每位教师只能在一个系任教，每个系只有一位系主任。
分解1：ρ1={R1(T#)，R2(TD)，R3(DH)}
分解2：ρ2={R1(T#，TD)，R2(T#，DH)}
分解3：ρ3={R1(T#，TD)，R2(TD，DH)}
分析：这三种分解哪一个最好？

 2. （1）分解前的关系模式R和分解后的ρ是否表示同样的数据，即分解是否导致数据的丢失，用分解的无损连接性进行判断。（2）分解前的关系模式R和分解后的ρ是否保持相同的函数依赖，即分解是否导致函数依赖的丢失，用函数依赖保持性进行判定。（3）分解后关系应达到要求的范式级别。

4.4.2 分解的无损连接性判定

 1. 分解的无损连接性：如果一个关系模式分解后，可以通过自然连接恢复原模式的信息，这一特性称为分解的无损连接性。
 2. 判定一个分解的无损连接性的方法：ρ={R1(U1,F1),…,Rk(Uk,Fk)}是R(U,F)的一个分解，U={A1,…,An}，F={FD1,FD2,…,FDp}。

• （1）构造一个n列k行的二维表T。
• （2）根据F中函数依赖修改表T的内容。修改规则：逐个考察F中的每个函数依赖X→Y，在属性X所在的那些列上找出具有相同符号的行，在这些行上使对应于Y的各属性列位置上的符号改为相同，如果其中有一个符号为aj，则把其它符号也改为aj，否则改为bmj，其中m是这些行的最小行号。直至在表中发现一行已变成a1a2…ak，或表不能再进行修改为止。
• （3）如果发现表中有一行已变成a1a2…ak，则表示该分解具有无损连接性，否则分解不是无损连接的。

4.4.3 分解的函数依赖保持判定

 分解的函数依赖保持性：

4.4.4 关系模式的分解算法

 1. 一个模式分解必须满足：

• 连接不失真性。
• 依赖保持性。
• 某一级范式。

 2. 模式分解的几个重要事实：

• 若要求连接不失真，分解可达到BCNF。
• 若要求依赖保持，则分解可达到3NF，但不一定能达到BCNF。
• 若同时要求连接不失真和依赖保持，则分解可达到3NF，但不一定能达到BCNF。

 3. 分解算法1：转换为3NF的保持函数依赖的分解。

• 输入：关系模式R和函数依赖集F。
• 输出：结果为3NF的一个依赖保持分解。
• 步骤①：对R中的函数依赖集F进行极小化处理（处理后的函数依赖集仍记为F）。
• 步骤②：找出不在F中出现的属性，把这样的属性构成一个关系模式，把这些属性从U中去掉，剩余的属性仍记为U。
• 步骤③：若有X→A∈F，且XA=U，则ρ={R}，算法中止。
• 步骤④：否则，对于F中的每一个X→A，构成一个关系模式XA。（如果有X→A1,X→A2,…,X→An(左部相同),则可以用模式XA1A2…An代替n个模式XA1，XA2，…,XAn)。

 4. 分解算法2：结果为3NF，且具有依赖保持和连接不失真的分解。

• ①：设X是R(U,F)的码。R(U,F)已由前面的算法1分解为ρ={R1(U1,F1),R2(U2,F2),…,Rk(Uk,Fk)},令τ= ρ∪X。
• ②：若有某个Ui，X含于Ui，将X从τ中去掉。
• ③：若有某个Ui，使得X含于Ui， τ就是所求的分解。