第四章 关系数据理论 4.1 关系模式的设计问题 4.2 关系模式的规范化 4.3 数据依赖的公理系统 4.4 关系模式的分解 本章小结

4.1函数依赖 一、问题——如何构造一个关系模式 例：假设有学生关系模式 S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE) 其中，S#—学号、 SNAME—学生姓名、 CLASS—班级、 C#—课程号、 TNAME—教师姓名、 TAGE—教师年龄、ADDRESS—教师地址、 GRADE—成绩。 关系S存在以下问题： 1．数据冗余度高。 SNAME、CLASS、TNAME、TAGE、ADDRESS重复存储多次。

4.1函数依赖 2．数据修改复杂。 3．插入异常。 插入异常是指应该插入到数据库中的数据不能执行插入操作的情形。 关系S的主码： （S#，C#） 从在S#、C#、和(S#,c#)上出现NULL值去分析。 注意：当一个元组在主码的属性上部分或全部为空时，该元组不能插入到关系中。

4.1函数依赖 4．删除异常。 删除异常是指不应该删去的数据被删去的情形。 例如：选修某门课的所有学生都退选时，删除相关元组，会丢失该课程老师的信息。 解决：关系模式分解（关系规范化） 分解为 ST(S#，SNAME，CLASS) CT(C#,TNAME) TA(TNAME,TAGE,ADDRESS) SC(S#,C#,GRADE)

4.1函数依赖 二、函数依赖functional dependency, abbr. FD 设：R（A1，A2，…An)=R( U ) X，Y，Z 为U的不同子集 属性全集 定义4.1： ① 函数依赖 是完整性约束的一种，它推广了关键词的概念。If t1.X=t2.X, then t1.Y=t2.Y ②函数依赖：若R的任意关系有：对X中的每个属性值，在Y中都有惟一的值与之对应，则称Y函数依赖于X，记作 XY 。

4.1函数依赖 例：指出下列关系R中的函数依赖。 FD: AB->C、 A→C、C→A、AB→D？ Insert into R values(a1, b1, c2, d1) FD = key constraint ?

4.1函数依赖 函数依赖与属性间的关系有： 若X，Y是1 — 1关系， 则存在 XY或Y X 。如学号与借书证号 若X，Y是m — 1关系， 则存在 XY但 Y+> X。如学号与姓名 若X，Y是m — n关系， 则X，Y间不存在函数依赖关系。如姓名与课程 CF: 实体间的联系 NOTE: 函数依赖的方向性

4.1函数依赖 例 试指出学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)中存在的函数依赖关系。 S#→SNAME（每个学号只能有一个学生姓名） S#→CLASS（每个学号只能有一个班级） C#→TNAME（设每门课程只有一个教师任教，而一个教师可教多门课程，见CT表） TNAME→TAGE（每个教师只能有一个年龄） TNAME→ADDRESS（每个教师只能有一个地址） (S#，C#)→GRADE（每个学生学习一门课只能有一个成绩） (S#，C#)→SNAME、 (S#，C#)→CLASS、 (S#，C#)→C#、 (S#，C#)→TNAME、 (S#，C#)→TAGE、 (S#，C#)→ADDRESS

4.1函数依赖 三、函数依赖的分类 XY，但Y 不包含于 X则称X是非平凡的函数依赖。 XY，但Y ⊆ X 则称X是平凡的函数依赖。 若XY ，则X叫做决定因素。 若XY，Y X，则记作: X<— —>Y。 定义4.2：在R( U)中，X, Y, Z为U的不同子集。 完全函数依赖: 是指 XY，且对任何X的真子集X’， 都有X’+>Y，记作：X F > Y。 部分函数依赖: 是指XY，且存在X的真子集X’， 有X’->Y， 记作：X P > Y。 定义4.3：在R( U )中 传递函数依赖：是指若XY (Y 不包含于 X)， Y +> X ， 而Y  Z。记作： X T > Z 。

4.1函数依赖 左部为单属性的函数依赖一定是完全函数依赖。 左部为多属性的函数依赖，如何判断其是否为完全函数依赖？ 方法：取真子集，看其能否决定右部属性。 例：试指出学生关系S中存在的完全函数依赖和部分函数依赖。 S#→SNAME，S#→CLASS，TNAME→TAGE， TNAME→ADDRESS，C#→TNAME都是完全函数依赖。 (S#，C#)→GRADE 是一个完全函数依赖，因为S#+>GRADE，C#+>GRADE。

4.1函数依赖 (S#，C#)→SNAME，(S#，C#)→CLASS， (S#，C#)→TNAME，(S#，C#)→TAGE， (S#，C#)→ADDRESS都是部分函数依赖，因为S#→SNAME，S#→CLASS，C#→TNAME，C#→TAGE，C#→ADDRESS。 例：试指出学生关系S中存在的传递函数依赖。 解：因为C#→TNAME，TNAME+>C#，TNAME→TAGE，所以C#→TAGE 是一个传递函数依赖。类似地，C#→ADDRESS也是一个传递函数依赖。

4.1函数依赖 四、候选码 用函数依赖的概念来定义码。 术语： 定义4.4 : 主码 设X为R<U，F>中的属性或属性组合，若 X F > U 则X为R的候选码。 说明： X F > U X -> U X能决定整个元组 X’+> U X中无多余的属性 术语： 主码 主属性: 侯选码中的属性 非主属性 全码：整个属性组为码 例：R(顾客，商品，日期)

4.1函数依赖 例：试指出下列关系R中的侯选码、主属性和非主属性。 A D E a1 d1 e2 a2 d6 a3 d4 e3 a4 e4 函数依赖判断：A->D? D->A? … AD->E?… 候选码判断: A->ADE?… AD->ADE?… 解：关系R的侯选码为：A，(D,E) 关系R的主属性为：A，D，E 关系R的非主属性：无

4.1函数依赖 例1. R(A, B, C, D)，F={A->B, A->C, AB->D} 解：由 AB->A(自反律) 和 A->C(已知) 得：AB->C(传递律) 又因为 AB->A (自反律) ，AB->B (自反律) 和 AB->D (已知) 得：AB->ABCD。 AB是R的唯一候选码，同时也是R的主码。

4.1函数依赖 例2. R(A, B, C, D)，F={A->B, A->C, A->D, AB->D} 解：由 A->A(自反律) 和 A->B, A->C, A->D(已知) 得：A-> ABCD 可知 A是R的候选码 AB->ABCD，但由于存在A-> ABCD，则AB对ABCD是部分函数依赖，因此AB不能成为候选码。 A是R的唯一候选码，A是主码。

4.2 关系模式的规范化 一、关系与范式 关系的规范化是将一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。 关系模式分解的目的：去冗余、满足约束。 关系模式的冗余性问题。例R(A,B,C)，无任何约束可导致冗余，若规定FD:A->B，则冗余可利用FD预测到。 约束条件通过函数的多值依赖和连接依赖及范式完成。

4.2 关系模式的规范化 二、第一范式：1NF 定义4.5: 若R的每个分量都是不可分的数据项，则R∈1NF。 从型上看：不存在嵌套结构 4.2 关系模式的规范化 二、第一范式：1NF 定义4.5: 若R的每个分量都是不可分的数据项，则R∈1NF。 从型上看：不存在嵌套结构 从值上看，不存在重复组 1NF是关系模式的最低要求。 例：学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)是1NF关系，但它存在数据冗余，插入异常和删除异常等问题。

4.2 关系模式的规范化 三、第二范式： 2NF 定义4.6 若R∈1NF，且R中的每一个非主属性都完全函数依赖于R的任一候选码，则R∈2NF。 例：学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE),判断R是否为2NF? 侯选码为(S#，C#)，非主属性有：SNAME，CLASS，TNAME，TAGE，ADDRESS，GRADE (S#，C#)－>SNAME， S# －> SNAME (S#，C#) P >SNAME S2NF(每一个非主属性!)。

4.2 关系模式的规范化 分解为2NF的方法：破坏部分依赖的条件。 将满足部分函数依赖和满足完全函数依赖的属性分解到不同的关系中。 4.2 关系模式的规范化 分解为2NF的方法：破坏部分依赖的条件。 将满足部分函数依赖和满足完全函数依赖的属性分解到不同的关系中。 对上例，考察非主属性和侯选码之间的函数依赖关系： (S#，C#) P >SNAME， (S#，C#) P >CLASS， (S#，C#) P >TNAME， (S#，C#) P >TAGE， (S#，C#) P >ADDRESS， (S#，C#) F >GRADE 区分出完全依赖和部分依赖，若是部分依赖，标记出其中的主属性。

4.2 关系模式的规范化 关系S分解为三个关系： ST(S#，SNAME，CLASS)（只依赖S#的属性分解到一个子模式中） 4.2 关系模式的规范化 关系S分解为三个关系： ST(S#，SNAME，CLASS)（只依赖S#的属性分解到一个子模式中） CTA(C#，TNAME，TAGE，ADDRESS) （只依赖C#的属性分解到另一个子模式中） SC(S#，C#，GRADE) （完全函数依赖于候选码的属性分解到第三个子模式中） 分解后，关系ST、CTA和SC都为2NF。 结论1：若关系R的侯选码是单属性的，则R必定是2NF。

4.2 关系模式的规范化 达到2NF的关系仍然可能存在问题。 例如，在关系CTA中还存在以下问题： 4.2 关系模式的规范化 达到2NF的关系仍然可能存在问题。 例如，在关系CTA中还存在以下问题： （1） 数据冗余。一个教师承担多门课程时，教师的姓名、年龄、地址要重复存储。 （2） 修改复杂。一个教师更换地址时，必须修改相关的多个元组。 （3） 插入异常。一个新教师报到，需将其有关数据插入到CTA关系中，但该教师暂时还未承担任何教学任务，则因缺码C#值而不能进行插入操作。 （4） 删除异常。删除某门课程时，会丢失该课程任课教师的姓名、年龄和地址信息。

4.2 关系模式的规范化 四、第三范式： 3NF 定义4.7 如果关系R的任意一个非主属性都不传递函数依赖于它的任意一个候选码，则R∈3NF。 关系CTA(C#，TNAME，TAGE，ADDRESS)是2NF，但不是3NF。 候选码：C#，非主属性：TNAME、TAGE、ADDRESS。 由于C#→TNAME，TNAME+>C#，TNAME→TAGE，所以 C# T >TAGE ，同样有C# T >ADDRESS，即存在非主属性对候选码的传递函数依赖。 关系模式R（A，B，C，D），码为AB，给出它的 一个函数依赖集，使得R属于2NF而不属于3NF

4.2 关系模式的规范化 分解为3NF的方法：破坏传递依赖的条件。 将涉及传递函数依赖中的两个依赖中的属性分解到不同的关系中。 4.2 关系模式的规范化 分解为3NF的方法：破坏传递依赖的条件。 将涉及传递函数依赖中的两个依赖中的属性分解到不同的关系中。 例：CTA中，两个传递依赖C# T >TAGE ，C# T >ADDRESS C#→TNAME，TNAME+>C#，TNAME→TAGE。 C#→TNAME，TNAME+>C#，TNAME→ADDRESS。 将CTA分解为： CT(C#，TNAME) TA(TNAME，TAGE，ADDRESS) 则关系CT和TA都是3NF，关系CTA中存在的问题得到了解决。

4.2 关系模式的规范化 定理4.1 一个3NF的关系必定是 2NF。 （3NF传递函数依赖，2NF完全函数依赖。） 4.2 关系模式的规范化 定理4.1 一个3NF的关系必定是 2NF。 （3NF传递函数依赖，2NF完全函数依赖。） 证明：用反证法。设R∈3NF，但R2NF，则R中必有非 主属性A、侯选码X和X的真子集X‘存在，使得X’→A。 X’是侯选码X的真子集，有X-X‘≠ф；A是非主属性，A-X≠ф，A-X‘≠ф，这样A、X、X‘是U的不同子集。 X’是侯选码X的真子集，则有X→X’ 且 X’+>X，联合反证假设X’→A可知存在传递依赖（X→X’，X’+>X，X’→A） R不是3NF，与题设矛盾。

4.2 关系模式的规范化 通过转为2NF消除了部分依赖，通过转为3NF消除了传递依赖，问题：达到3NF的关系是否仍然存在问题？ 4.2 关系模式的规范化 通过转为2NF消除了部分依赖，通过转为3NF消除了传递依赖，问题：达到3NF的关系是否仍然存在问题？ 例：每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称 ：

4.2 关系模式的规范化 CNAME TNAME 解：关系SCT的侯选码：(S#，CNAME)和(S#，TNAME) 4.2 关系模式的规范化 S# CNAME TNAME s1 英语 王平 数学 刘红 s2 物理 高志强 陈进 s3 候选码判断: S#->S# CNAME TNAME.. 取左部的相同值，判断右部。 解：关系SCT的侯选码：(S#，CNAME)和(S#，TNAME) 非主属性：无 （SCT至少是一个3NF关系) 结论2：若关系R的所有属性都是主属性，则R必定是3NF。

4.2 关系模式的规范化 在3NF关系SCT中存在： 插入异常。例如，一个新课程和任课教师的数据，在没有学生选课时不能插入数据库。 4.2 关系模式的规范化 在3NF关系SCT中存在： 插入异常。例如，一个新课程和任课教师的数据，在没有学生选课时不能插入数据库。 删除异常。例如，删除某门课的所有选课记录，会丢失课程与教师的数据。 达到3NF的关系仍然可能存在问题。

4.2 关系模式的规范化 五、BCNF 定义4.8 关系模式R<U，F>∈1NF。若函数依赖集合F中的 4.2 关系模式的规范化 五、BCNF 定义4.8 关系模式R<U，F>∈1NF。若函数依赖集合F中的 所有函数依赖X→Y（Y不包含于X）的左部都包含R的任一侯选码，则R∈BCNF。 换言之，BCNF中的所有依赖的左部都必须包含候选码。 例：关系SCT是否BCNF? 因为TNAME→CNAME，其左部未包含该关系的任一侯选码 ，所以它不是BCNF。 解决：BCNF分解。

4.2 关系模式的规范化 分解为BCNF的方法： 消除不包含关系。 4.2 关系模式的规范化 分解为BCNF的方法： 消除不包含关系。 1. 假设R(U)不是BCNF, X是R的属性子集，A是R的单个属性，X->A是导致违反BCNF的函数依赖，则将R分解为R-A 以及 XA。 2. 若R-A以及 XA 仍然不是BCNF，则在R-A 以及 XA递归地执行上述分解。 例 SCT：(S#，CNAME，TNAME)，FD: TNAME→CNAME。 可分解为SC(S#，TNAME)和CT(CNAME，TNAME)，它们都是BCNF。

4.2 关系模式的规范化 定理4.2：一个BCNF的关系必定是3NF。 （3NF：任意的非主属性都不传递依赖于任意一个候选码。） 4.2 关系模式的规范化 定理4.2：一个BCNF的关系必定是3NF。 （3NF：任意的非主属性都不传递依赖于任意一个候选码。） 证明：用反证法。设R是一个BCNF，但不是3NF，则必存在一个非主属性A和候选码X以及属性集Y，使得A传递依赖于X，即X→Y(Y不包含于X)，Y+>X，Y→A。 这就是说Y不包含R的候选码，但Y→A却成立。 根据BCNF定义可知，R不是BCNF，与题设矛盾。 结论3：任何的二元关系必定是BCNF。

4.2 关系模式的规范化 3NF下仍然存在插入异常和删除异常， 原因在于可能存在主属性对候选码的部分函数依赖和传递函数依赖。 4.2 关系模式的规范化 3NF下仍然存在插入异常和删除异常， 原因在于可能存在主属性对候选码的部分函数依赖和传递函数依赖。 一个模式中的关系模式如果都属于BCNF，则在函数依赖的范畴内实现了彻底的分离，已消除了插入和删除的异常。 其它问题？

4.2 关系模式的规范化 六、第四范式：4NF 定义4.10 若R∈ 1NF，D是R上的依赖集，如果对于任何一个多值依赖XY (Y-X≠ф,XY没有包含R的全部属性)，X都包含了R的一个候选关键词，则R∈4NF。 4NF必定是BCNF，但BCNF不一定是4NF。

4.2 关系模式的规范化 5种范式的关系： 范式的 转换关系： 非规范化的关系 消除组合数据项 1NF 消除非主属性对码的部分函数依赖 4.2 关系模式的规范化 消除组合数据项 5种范式的关系： 1NF 1NF 消除非主属性对码的部分函数依赖 2NF 2NF 3NF 消除非主属性对码的传递函数依赖 BCNF 3NF 4NF 消除主属性对码的部分和传递函数依赖 BCNF 范式的 转换关系： 消除非平凡的 多值依赖 4NF

4.2 关系模式的规范化 关系的规范化是将一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。 4.2 关系模式的规范化 关系的规范化是将一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。 范式的转换过程是通过分析和消除属性间的数据依赖关系来实现的。 属性可分为码和非主属性。 2NF, 3NF考察非主属性和码的关系，BCNF考察主属性和码的关系。 属性间的依赖关系包括函数依赖和多值依赖。 1NF, 2NF, 3NF, BCNF考察了函数依赖关系；4NF考察了多值依赖。

4.3 数据依赖的公理系统 1.阿氏公理 定义4.13 设F是关系模式R的函数依赖集，X、Y是R的属性子集，如果从F的函数依赖中能够推出XY，则称F逻辑蕴涵XY。 在R<U，F> 中为F所逻辑蕴含的函数依赖全体叫F的闭包，记为：F+。 F+={ ① F； ② F中推出的非平凡的函数依赖； ③平凡的函数依赖：A->φ、A->A、AB-> A….. } 例：有关系模式R(A，B，C)，它的函依赖集F={A→B，B→C}，计算F的闭包。

4.3 数据依赖的公理系统 Armstrong公理(阿氏公理)： 对R<U，F> 有： A1自反律：若Y⊆X ，则XY。 A2增广律：若XY，则XZYZ。 A3传递律：若XY、YZ，则XZ。 Note：XY与YX的次序无关。

4.3 数据依赖的公理系统 证：设s，t是r的任意两个元组，r是R的任意一个关系。 A1自反律：若Y⊆X ，则XY。 4.3 数据依赖的公理系统 证：设s，t是r的任意两个元组，r是R的任意一个关系。 A1自反律：若Y⊆X ，则XY。 若s[x]=t[x]，则在s和t中的x的任何子集也必相等。 ∵ Y⊆X，∴ s[y]=t[y] ∴ XY。 A2增广律：若XY，则XZYZ。 若s[xz]=t[xz]，即s[x]s[z]=t[x]t[z] 则 s[x]=t[x] 且 s[z]=t[z] ∵ XY， ∴ s[y]=t[y] ∴ s[yz]=s[y]s[z]=t[y]t[z]=t[yz] ∴ XZYZ

4.3 数据依赖的公理系统 A3传递律：若XY、YZ，则XZ。 若s[x]=t[x] ∵ XY ∴ s[y]=t[y] 又∵ YZ ∴ s[z]=t[z] ∴ XZ。

4.3 数据依赖的公理系统 公理的推论： 合并规则：若XY 、 XZ，则XYZ。 分解规则：若XYZ，则XY,XZ。 4.3 数据依赖的公理系统 公理的推论： 合并规则：若XY 、 XZ，则XYZ。 分解规则：若XYZ，则XY,XZ。 伪传递规则：若XY 、WYZ，则WXZ。 证明： 合并规则：∵ XY ∴ XXY (A2) 又∵ XZ ∴ XYYZ (A2) ∴ XYZ (A3)

4.3 数据依赖的公理系统 分解规则： ∵ Y⊆Y Z ∴ YZY (A1) 又∵ XYZ(已知） ∴ XY (A3) 4.3 数据依赖的公理系统 分解规则： ∵ Y⊆Y Z ∴ YZY (A1) 又∵ XYZ(已知） ∴ XY (A3) 同理可证XZ。 伪传递规则：∵ XY ∴ WXWY (A2) 又∵ WYZ (已知) ∴ WXZ (A3) 定理4.5: XA1A2…AK成立的充分必要条件是XAi成立。 由合并律  由分解律 

4.3 数据依赖的公理系统 定义4.14: XF+={A|XA能由F用阿氏公理导出} XF+称为属性集X关于F的闭包。 定理4.6： 4.3 数据依赖的公理系统 定义4.14: XF+={A|XA能由F用阿氏公理导出} XF+称为属性集X关于F的闭包。 定理4.6： XY能从F中用阿氏公理导出的充要条件是：Y⊆XF+

4.3 数据依赖的公理系统 定理4.6的证明 证明： 充分性（ Y⊆XF+ -> XY） 假设Y⊆XF+ (其中Y=A1A2…An ) 由属性闭包定义可知， XA1， XA2…， XAn能由阿氏公理导出，再由合并规则得X A1A2…An，即XY。

4.3 数据依赖的公理系统 必要性：（ XY -> Y⊆XF+ ） 假设XY能由阿氏公理导出(Y=A1A2…An) 则有XA1A2…An 由分解规则得： XA1， XA2…， XAn 由XF+的定义可知，Ai⊆ XF+ (i=1,2,…,n) 即Y⊆XF+ 。

Armstrong公理系统 Armstrong公理完备性的证明 Y  ，Y ≠ ， U  ≠  r（ U  ） t 1 0 证明：（构造性证明）用反证法 假定存在函数依赖XY被F逻辑蕴涵，但XY不能用Armstrong公理从F中导出 由引理二， 构造R(U)上的关系r如下： 下面证明（1）r满足F，（2）r不满足XY Y  ，Y ≠ ， U  ≠  r（ U  ） t 1 0 s 1 1

4.3 数据依赖的公理系统 2. 属性闭包的计算 算法4.1 : 求属性集X关于F的闭包XF+(X+)。 算法： 4.3 数据依赖的公理系统 2. 属性闭包的计算 算法4.1 : 求属性集X关于F的闭包XF+(X+)。 算法： 设 R<U，F>，A为U中属性(集)。 (1) X(0)=X (2) X(i+1)=X(i)∪A 其中：对F中任一个Y->A ，且Y⊆X(i)； 求得X(i+1) 后，对Y->A 做删除标记。 (3)若X(i+1)=X(i) 或 X(i+1) =U则结束，否则转(2)。 算法会终止吗？ 最多|U-X|步

闭包的计算 示例1 R< U, F >, U = (A, B, C, G, H, I), F = {AB, AC, CGH, CGI, BH},计算 所用依赖 AB AGB AC AGBC CGH AGBCH CGI AGBCH I = AGBCH I

闭包的计算 示例2 R< U, F >, U = (A, B, C, D, E), F = {ABC, BD, CE, CEB, ACB},计算 所用依赖 ABC ABC BD ABCD CE ABCDE = ABCDE

闭包的计算 示例3 R< U, F >, U = (A, B, C, D, E, G), F = {AE, BEAG, CEA, GD},计算 所用依赖 AE ABE BEAG ABEG GD ABEGD = ABEGD

4.3 数据依赖的公理系统 3.函数依赖集的等价和覆盖 定义4.15 : 如果F+=G+ ，就说函数依赖集F覆盖G或F与G等价。 4.3 数据依赖的公理系统 3.函数依赖集的等价和覆盖 定义4.15 : 如果F+=G+ ，就说函数依赖集F覆盖G或F与G等价。 定理4.9: F+=G+ 的充分必要条件是F⊆G+，和G⊆F+。 （1）必要性 ∵F和G等价，∴F+=G+，又∵F⊆F+，∴F⊆G+ 同理，∵G⊆G+，∴G⊆F+。 （2）充分性 任取X→Y∈F+，则有Y⊆XF+ (定理4.6) 又∵F⊆G+（已知），∴Y⊆XG++ ∴X→Y∈(G+)+=G+，∴F+⊆G+。 同理可证G+⊆F+，∴F+=G+，即F和G等价。

4.3 数据依赖的公理系统 如何判断函数依赖集F和G是否等价？ 根据定理4.9: 只需F⊆G+和G⊆F+，即证集合的包含关系。 4.3 数据依赖的公理系统 如何判断函数依赖集F和G是否等价？ 根据定理4.9: 只需F⊆G+和G⊆F+，即证集合的包含关系。 对每个T ∈ F,有T ∈ G+；对每个S ∈G，有S ∈ F+，T和S是形如X->Y的属性依赖。 证 X->Y ∈ G+,根据定理4.6：只需Y ⊆ XG+ 转为计算XG+

4.3 数据依赖的公理系统 例：F={A→B，B→C}，G={A→BC，B→C}，判断F和G是否等价。 4.3 数据依赖的公理系统 例：F={A→B，B→C}，G={A→BC，B→C}，判断F和G是否等价。 解：（1）先检查F中的每一个函数依赖是否属于G+。 ∵AG+=ABC，∴B⊆AG+，∴A→B∈G+ (定理4.6) 又∵BG+=BC，∴C⊆BG+，∴B→C∈G+ ∴F⊆G+ （2）然后检查G中的每一个函数依赖是否属于F+。 ∵AF+=ABC，∴BC⊆AF+，∴A→BC∈F+ 又∵BF+=BC，∴C⊆BF+，∴B→C∈F+ ∴G⊆F+ 由（1）和（2）可得F和G等价。

4.3 数据依赖的公理系统 4.最小函数依赖集 定义4.16:若F满足下列条件，则称其为一个最小函数依赖集Fm。 4.3 数据依赖的公理系统 4.最小函数依赖集 定义4.16:若F满足下列条件，则称其为一个最小函数依赖集Fm。 (1) F中每个函数依赖的右部都是单属性； (2) 对于F的任一函数依赖X→A，F-{X→A}与F都不等价； (3) 对于F中的任一函数依赖X→A和X的真子集Z， (F-(X→A))U{Z→A}与F都不等价。 最小：（1）F中每个函数依赖的右部没有多余的属性； （2）F中不存在多余的函数依赖； （3）F中每个函数依赖的左部没有多余的属性。

4.3 数据依赖的公理系统 定理4.10: 每个F与Fm等价。 如何求最小函数依赖集Fm？ 4.3 数据依赖的公理系统 定理4.10: 每个F与Fm等价。 如何求最小函数依赖集Fm？ (1)分解：使F中任一函数依赖的右部仅含有单属性。 (2)删除冗余的函数依赖： 方法：对F中任一XA，在F-{XA}中求X+， 若A⊆X+，则XA为多余的。 (3)最小化左边的多余属性： 方法：对F中任一XYA，在F中求X+， 若A⊆X+ ，则Y为多余的。 [ (4)检查：用公理或(2) ]

4.3 数据依赖的公理系统 例：设有F={B→C，C→AB，BC→A}，求与F等价的最小函数依赖集。 4.3 数据依赖的公理系统 例：设有F={B→C，C→AB，BC→A}，求与F等价的最小函数依赖集。 分解C→AB，F={B→C，C→A，C→B，BC→A} 判断B→C是否冗余，F’={C→A，C→B，BC→A} B+ = B, B→C非冗余。 F={B→C，C→A，C→B，BC→A} 判断C→A是否冗余，F’={B→C, C→B，BC→A} C+ = ABC, C→A冗余。 F={B→C，C→B，BC→A} 判断C→B是否冗余，F’={B→C, BC→A} C+ = C, C→B非冗余。 F={B→C，C→B，BC→A} 判断BC→A是否冗余，F’={B→C，C→B} BC+ = BC, BC→A非冗余。F={B→C，C→B，BC→A} 判断BC→A。 B+ = ABC, A⊆B+ ，则C在BC→A中是多余的。 Fmin={B→C，C→B，B→A} 注意： 对当前F求闭包

4.3 数据依赖的公理系统 例：设有函数依赖集F={A→B,ABCD→E,EF→G,EF→H,ACDF→EG} 求与F等价的最小函数依赖集。 4.3 数据依赖的公理系统 例：设有函数依赖集F={A→B,ABCD→E,EF→G,EF→H,ACDF→EG} 求与F等价的最小函数依赖集。 注意：一个函数依赖集的最小集不是惟一的。 例如，F={A→B，B→A，B→C，A→C，C→A} Fm1={A→B，B→C，C→A}， Fm2={A→B，B→A，A→C，C→A}。 方法1： 无多余属性；依次判断B->A, A->C是否冗余； 方法2： 无多余属性；依次判断B->C是否冗余。 Fmin = {A→B,ACD→E, EF→G,EF→H}

4.4 关系模式的分解 对于存在数据冗余、插入异常、删除异常的关系模式，可以通过对关系模式的分解来解决问题。关系模式分解后会带来两个问题： （1）查询时的连接操作是否会丢失某些信息或多出某些信息。这引出了无损连接的概念。 （2）分解后的关系模式是否保持了原来的函数依赖。这是保持函数依赖性的问题。

4.4 关系模式的分解 1. 等价模式分解的定义 一个关系可以有多种分解方法，如何判断分解的好与坏呢？ 4.4 关系模式的分解 1. 等价模式分解的定义 一个关系可以有多种分解方法，如何判断分解的好与坏呢？ 例：关系模式R(S#，SD，MN),F={S#→SD，SD<—>MN} 分解一：ρ1={R1(S#)， R2(SD)， R3(MN)} 不好！无法恢复r. 分解二：ρ2={R1(S#，SD)，R2(S#，MN)} 不好！丢失SD<—>MN 分解三：ρ3={R1(S#，SD)，R2(SD，MN)} 好！

R(A, B, C) ∏AB(R) ∏BC(R) ∏AB(R) ∏BC(R) 无损分解 R(A, B, C) ∏AB(R) ∏BC(R) 1 2 B C 1 2 A B C 1 2 A B C 1 2 无损分解 R(A, B, C) ∏AB(R) ∏BC(R) ∏AB(R) ∏BC(R) A B C 1 2 A B 1 2 B C 1 2 A B C 1 2 有损分解

对于R<U，F>中任何一个关系r， R分解ρ={R1, R2….RK} 无损连接性： 4.4 关系模式的分解 2.无损连接性与依赖保持性 对于R<U，F>中任何一个关系r， R分解ρ={R1, R2….RK} 无损连接性： r=ΠR1(r) ⋈ ΠR2(r) ⋈ … ⋈ ΠRK(r) 保持函数依赖： F ≡ ΠR1(F)∪ΠR2(F)∪… ΠRK(F) ΠRi(F)={X->Y| X->Y∈F+∧XY⊆Ri } Ri所蕴含的F+中的函数依赖

4.4 关系模式的分解 是无损连接分解。 = {A->B，A->C} 4.4 关系模式的分解 例：R(A，B，C) ， F={A->B，A->C} ，分解ρ={AB，AC} 判断1： r=ΠAB(r) |X| ΠAC(r) 是无损连接分解。 判断2: F≡ΠAB(F)∪ΠAC(F) = {A->B，A->C} 具有函数依赖保持性。 r A B C a1 b1 c1 a2 b2 c2 a3 ?ρ={AB，BC}

4.4 关系模式的分解 算法4.3 无损连接性检验。 输入：关系模式R(A1，A2，…，An)，它的函数依赖集F，以及分 4.4 关系模式的分解 算法4.3 无损连接性检验。 输入：关系模式R(A1，A2，…，An)，它的函数依赖集F，以及分 解ρ={R1，R2，…，Rk}。 输出：确定ρ是否具有无损连接性。 方法：(1)构造一个k行n列的表，第i行对应于关系模式Ri，第j列 对应于属性Aj。如果Aj∈Ri，则在第i行第j列上放符号aj，否则放 符号bij。（属于用a代表，且位置信息用j表示；不属于用b代表,且位置信息用ij表示。） (2)重复考察F中的每一个函数依赖，并修改表中的元素。其方 法如下：取F中一个函数依赖X→Y，在X的分量中寻找相同的行，然 后将这些行中Y的分量改为相同的符号，如果其中有aj，则将bij改 为aj；若其中无aj，则全部改为bij（i是这些行的行号最小值）。

4.4 关系模式的分解 (3)如果发现表中某一行变成了al，a2，…，an，则分解ρ 具有无损连接性；如果F中所有函数依赖都不能再修改 4.4 关系模式的分解 (3)如果发现表中某一行变成了al，a2，…，an，则分解ρ 具有无损连接性；如果F中所有函数依赖都不能再修改 表中的内容，且没有发现这样的行，则分解ρ不具有无 损连接性。

无损连接分解 ABC CD DE 示例一：U={A,B,C,D,E}, F={ABC, CD,DE}

4.4 关系模式的分解 AC 示例二：U={A,B,C,D,E}, F={AC, BC, CD,DEC ,CEA} 4.4 关系模式的分解 示例二：U={A,B,C,D,E}, F={AC, BC, CD,DEC ,CEA}  ={(A, D), (A, B), (B, E), (C, D, E), (A, E)} AC A B C D E AD a1 b12 b13 a4 b15 AB a2 b23 b24 b25 BE b31 b33 b34 a5 CDE b41 b42 a3 AE b32 b54 A B C D E AD a1 b12 b13 a4 b15 AB a2 b24 b25 BE b31 b33 b34 a5 CDE b41 b42 a3 AE b32 b54

4.4 关系模式的分解 BC CD A B C D E AD a1 b12 b13 a4 b15 AB a2 b24 b25 BE 4.4 关系模式的分解 BC CD A B C D E AD a1 b12 b13 a4 b15 AB a2 b24 b25 BE b31 b34 a5 CDE b41 b42 a3 AE b32 b54 A B C D E AD a1 b12 b13 a4 b15 AB a2 b25 BE b31 a5 CDE b41 b42 a3 AE b32

4.4 关系模式的分解 DEC CEA A B C D E AD a1 b12 b13 a4 b15 AB a2 b25 BE b31 4.4 关系模式的分解 DEC CEA A B C D E AD a1 b12 b13 a4 b15 AB a2 b25 BE b31 a3 a5 CDE b41 b42 AE b32 A B C D E AD a1 b12 b13 a4 b15 AB a2 b25 BE a3 a5 CDE b42 AE b32

4.4 关系模式的分解 定理4.12 设ρ=(R1，R2)是R的一个分解，F是R上的函数 依赖集，分解ρ具有无损连接性的充分必要条件是： 4.4 关系模式的分解 定理4.12 设ρ=(R1，R2)是R的一个分解，F是R上的函数 依赖集，分解ρ具有无损连接性的充分必要条件是： R1∩R2→(R1-R2)∈F+ 或 R1∩R2→(R2-R1)∈F+ 证明： （1）充分性：设R1∩R2→(R1-R2)，按算法5.2可构造出下表。表中省略了a和b的下标，这无关紧要。 只能用于判断分解为2个子模式的情况。 Ri R1∩R2 R1-R2 R2-R1 R1 aa…a bb…b R2

4.4 关系模式的分解 如果R1∩R2→(R1-R2)在F中，则可将表中第2行位于(R1-R2)列 4.4 关系模式的分解 如果R1∩R2→(R1-R2)在F中，则可将表中第2行位于(R1-R2)列 中的所有符号都改为a，这样该表中第2行就全是a了，则ρ具有无 损连接性。同理可证R1∩R2→(R2-R1)的情况。 如果R1∩R2→(R1-R2)不在F中，但在F+中，即它可以用公理从 F中推出来，从而也能推出R1∩R2→Ax, 其中Ax⊆R1-R2，所以可 以将Ax列的第2行改为全a，同样可以将R1-R2中的其他属性的第2 行也改为a，这样第2行就变成全a行。所以分解ρ={R1，R2}具有 无损连接性。 同样可以证明R1∩R2→(R2-R1)的情况。 （2）必要性：设构造的表中有一行全为a，例如第1行全为a，则 由函数依赖定义可知R1∩R2→(R2-R1)；如果是第2行全为a，则 R1∩R2→(R1-R2)。定理证毕。

4.4 关系模式的分解 例:下列分解是否具有无损连接性和函数依赖保持性。 已知：R(A,B,C) F={A→B，C→B} 4.4 关系模式的分解 例:下列分解是否具有无损连接性和函数依赖保持性。 已知：R(A,B,C) F={A→B，C→B} (1）ρ1={AB，BC} （2）ρ2={AC，BC}

4.4 关系模式的分解 ρ1={AB，BC} F={A→B，C→B} Ri A B C AB a1 a2 b13 BC b21 a3 4.4 关系模式的分解 ρ1={AB，BC} F={A→B，C→B} Ri A B C AB a1 a2 b13 BC b21 a3 （1）对ρ1和F构造表： （2）检查F={A→B，C→B} 对A→B，A列中无相同的行； 对C→B, C列中无相同的行。 ρ1不具有无损连接性。

4.4 关系模式的分解 ρ1={AB，BC} F={A→B，C→B} 利用定理4.12解。 R1∩R2 = B (R1-R2) = A 4.4 关系模式的分解 ρ1={AB，BC} F={A→B，C→B} 利用定理4.12解。 R1∩R2 = B (R1-R2) = A R1∩R2 +> (R1-R2) ρ1不是无损连接分解。

4.4 关系模式的分解 ρ2={AC，BC} F={A→B，C→B} Ri A B C AC a1 b12 a3 BC b21 a2 4.4 关系模式的分解 ρ2={AC，BC} F={A→B，C→B} Ri A B C AC a1 b12 a3 BC b21 a2 对ρ2和F构造表： 检查F={A→B，C→B} 对C→B, C列有相同的行，改写B列的相异符号为a，下标为列号2。第一行变为a1a2a3,ρ2具有无损连接性。 Ri A B C AC a1 a2 a3 BC b21

4.4 关系模式的分解 ρ2={AC，BC} F={A→B，C→B} 利用定理4.12解。 R1∩R2 = C 4.4 关系模式的分解 ρ2={AC，BC} F={A→B，C→B} 利用定理4.12解。 R1∩R2 = C (R1-R2) = A；(R2-R1) = B； R1∩R2 +> (R2-R1) ρ2是无损连接分解。

4.4 关系模式的分解 3. 模式分解的方法 3NF的保持无损连接及函数依赖的分解： 设： R<U，Fm> 4.4 关系模式的分解 3. 模式分解的方法 3NF的保持无损连接及函数依赖的分解： 设： R<U，Fm> 1)对Fm中任一X->A，若XA=U则不分解，结束。 2)若R中Z属性在Fm中未出现，则所有Z为一个子模式， 令U=U-Z。 3)对Fm中 X->A1，…. X->An，用合成规则合成一个， 再对Fm中每个X->A，令Ri=XA。 4) R的分解为{R1，R2，….RK，码} 依赖保持不需要； 原包含有不需要。

4.4 关系模式的分解 BCNF的保持无损连接的分解： （1）令ρ={R}； （2）如果ρ中所有关系模式都是BCNF，则转（4）； 4.4 关系模式的分解 BCNF的保持无损连接的分解： （1）令ρ={R}； （2）如果ρ中所有关系模式都是BCNF，则转（4）； （3）如果ρ中有一个关系模式Ri<Ui，Fi>不是BCNF，则Ri中必有X→A∈Fi+(AX)，且X不是Ri的码。设S1=XA，S2=Ui-A，用分解{S1，S2}代替Ri<Ui，Fi>，转（2）； （4）分解结束，输出ρ。 例：设R={A,B,C,D},F={A→C，C→A，B→AC，D→AC，BD→A} （1）将R 分解为3NF且具有无损连接性和依赖保持性。 （2）将R 分解为BCNF且具有无损连接性。

关系模式的分解算法 示例：U={S#，SD，MN，C#，G} F={S#SD，S#MN，SDMN，(S#,C#)G} ⒈U1={S#，SD} , F1={S#SD} U2={S#, MN, C#, G}, F2={S#MN, (S#,C#)G} ⒉U1 = {S#, SD}, F1={S#SD} U2 = {S#, MN}, F2={S#MN} U3 = {S#, C#, G}, F3 = {(S#,C#)G}

4.4 关系模式的分解 关系模式CTHRSG，其中C表示课程，T表示教师，H表示时 间，R表示教室，S表示学生，G表示成绩。函数依赖集F及 4.4 关系模式的分解 关系模式CTHRSG，其中C表示课程，T表示教师，H表示时 间，R表示教室，S表示学生，G表示成绩。函数依赖集F及 其所反映的语义分别为： CT 每门课程仅有一位教师担任。 HTR 在任一时间，一个教师只能在一个教室上课。 HRC 在任一时间，每个教室只能上一门课。 HSR 在任一时间，每个学生只能在一个教室听课。 CSG 每个学生学习一门课程只有一个成绩。

4.4 关系模式的分解 解：HSCTHRSG，HS是关系模式的关键字。 ⑴ 面向3NF且保持函数依赖的分解。 4.4 关系模式的分解 解：HSCTHRSG，HS是关系模式的关键字。 ⑴ 面向3NF且保持函数依赖的分解。 最小函数依赖集为 F={CT,CSG,HRC,HSR,THR} 分解为：＝{CT，CSG，HRC，HSR，THR} ⑵ 面向3NF既有无损连接性又保持函数依赖的分解。 ∵ HS是关键字， ＝  ∪{ HS } ，HS是HSR的一个子集 ∴分解仍为：＝{CT，CSG，HRC，HSR，THR}

4.4 关系模式的分解 ⑶ 面向BCNF且具有无损连接性的分解。 CTHRSG Key=HS CSG Key=CS CSG 4.4 关系模式的分解 ⑶ 面向BCNF且具有无损连接性的分解。 CTHRSG Key=HS CSG Key=CS CSG CTHRS Key=HS CT，THR HRC，HSR CT Key=C CT CHRS Key=HS CHR，HRC HSR CHR Key=CH，HR CHR， HRC CHS Key=HS HSC

4.5. 多值依赖与第四范式4NF） 例: 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。 关系模式Teaching(C, T, B) 课程C、教师T 和 参考书B

例: 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。 关系模式Teaching(C, T, B) 课程C、教师T 和 参考书B

4.5. 多值依赖与第四范式4NF） 参考书B 教员T 课程C 普通物理学 光学原理 物理习题集 数学分析 微分方程 高等代数 … 李 勇 王 军 张 平 物 理 数 学 参考书B 教员T 课程C

4.5. 多值依赖与第四范式4NF） Teaching∈BCNF: Teach具有唯一候选码(C，T，B)， 即全码 (1)数据冗余度大：有多少名任课教师，参考书就要存储多少次 (2)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组 例如物理课增加一名教师刘关，需要插入两个元组： （物理，刘关，普通物理学） （物理，刘关，光学原理）

4.5. 多值依赖与第四范式4NF） (3) 删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组 (4) 修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组 产生原因 存在多值依赖

4.5. 多值依赖与第四范式4NF 第四范式：4NF 定义4.10 若R∈ 1NF，D是R上的依赖集，如果对于任何一个多值依赖XY (Y-X≠ф,XY没有包含R的全部属性)，X都包含了R的一个候选关键词，则R∈4NF。 4NF必定是BCNF，但BCNF不一定是4NF。

4.5. 多值依赖与第四范式4NF 在R（U）的任一关系r中，如果存在元组t，s 使得t[X]=s[X]，那么就必然存在元组 w，v r，（w，v可以与s，t相同），使得w[X]=v[X]=t[X]，而w[Y]=t[Y]，w[Z]=s[Z]，v[Y]=s[Y]，v[Z]=t[Z]（即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为X→→Y。 这里，X，Y是U的子集，Z=U-X-Y。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2

4.5. 多值依赖与第四范式4NF 平凡多值依赖和非平凡的多值依赖 若X→→Y，而Z＝φ，则称 X→→Y为平凡的多值依赖

4.5. 多值依赖与第四范式4NF 多值依赖的性质 （1）多值依赖具有对称性 若X→→Y，则X→→Z，其中Z＝U－X－Y 多值依赖的对称性可以用完全二分图直观地表示出来。 （2）多值依赖具有传递性 若X→→Y，Y→→Z， 则X→→Z -Y

物 理 普通物理学 光学原理 物理习题集 李勇 王军

（3）函数依赖是多值依赖的特殊情况。 若X→Y，则X→→Y。 （4）若X→→Y，X→→Z，则X→→Y Z。 （5）若X→→Y，X→→Z，则X→→Y∩Z。 （6）若X→→Y，X→→Z，则X→→Y-Z，X→→Z -Y。

4.5. 多值依赖与第四范式4NF 多值依赖与函数依赖的区别 (1) 有效性 多值依赖的有效性与属性集的范围有关 若X→→Y在U上成立，则在W（X Y  W  U）上一定成立；反之则不然，即X→→Y在W（W  U）上成立，在U上并不一定成立 多值依赖的定义中不仅涉及属性组 X和 Y，而且涉及U中其余属性Z。 一般地，在R（U）上若有X→→Y在W（W  U）上成立，则称X→→Y为R（U）的嵌入型多值依赖

只要在R（U）的任何一个关系r中，元组在X和Y上的值满足定义5.l（函数依赖）， 则函数依赖X→Y在任何属性集W（X Y  W U）上成立。 (2) 若函数依赖X→Y在R（U）上成立，则对于任何Y'  Y均有X→Y' 成立 多值依赖X→→Y若在R(U)上成立，不能断言对于任何Y'  Y有X→→Y' 成立

4.5. 多值依赖与第四范式4NF C→→T， C→→B是平凡多值依赖 例： Teach(C,T,B) ∈ 4NF CT(C, T) ∈ 4NF CB(C, B) ∈ 4NF C→→T， C→→B是平凡多值依赖

4.5. 多值依赖与第四范式4NF 定理4.3 如果关系模式R∈4NF，则R必为BCNF。 证明：用反证法。设R∈4NF，但RBCNF，则R中必 有某个函数依赖XY(Y不包含于X)，且X不包含R的侯选 码。由多值依赖公理可知，若XY，则XY，而 此时X不包含R的侯选码，R不是4NF，与假设矛盾，从而定理得证。

4.5. 多值依赖与第四范式4NF 分解为4NF的方法： （ 类似于BCNF，消除不包含关系。） 1. 假设R(U)不是4NF, X->->A是导致违反4NF的多值依赖，则将R分解为R-A 以及 XA。 2. 若R-A以及 XA 仍然不是4NF，则在R-A 以及 XA递归地执行上述分解。

4.5. 多值依赖与第四范式4NF） ⑷ 面向4NF且具有无损连接性的分解。 关系模式R中存在多值依赖C  HR，T  HR，显然由于 C或T都不含该关系模式的码HS，∴R4NF。 选择C  HR将它分解为CHR和CTSG; 再将CTSG分解为CT和CSG。 关系模式CTHRSG最后无损地分解为CHR、CT和CSG，其中 每一个关系模式都属于4NF。

4.6 规范化的问题 1. 规范化的优缺点 关系模式的分解会降低查询的效率。 4.6 规范化的问题 1. 规范化的优缺点 关系模式的分解会降低查询的效率。 所讨论的关系规范化是基于泛关系假设的，即只基于一个关系模式的规范化。但现实并不一定满足。 2.反规范化的设计 对一些特定的应用不规范化，而是通过使用冗余来改进性能。 例：account(帐号，支行名，余额) depositor(客户名，帐号) 每次访问帐户时，帐户持有者的名字都与帐户密码和余额一起显示。

4.6 规范化的问题 并不是规范化程度越高越好。 例：earnings(公司号，年份，数量) 若设计成： 4.6 规范化的问题 并不是规范化程度越高越好。 例：earnings(公司号，年份，数量) 若设计成： （1）使用多个关系 ，每年建一个表。 不好！（是BCNF） （2）使用一个关系： company_year(公司号，收入_2000，收入_2001，收入_2002) 不好！ （是BCNF）

第四章 关系数据理论 小结 1. 函数依赖关系 2. 关系模式的规范化 5种范式及转换 3. 阿氏公理及其推理规则 第四章 关系数据理论 小结 1. 函数依赖关系 2. 关系模式的规范化 5种范式及转换 3. 阿氏公理及其推理规则 4. XF+的定义及求XF+ 5. 用函数依赖或XF+求码 6.求最小函数依赖集Fm 7. 模式分解的概念、方法 练习： P196：3、9、12题 讨论题：2题