关系模式分解PPT课件

《关系模式分解PPT课件》由会员分享，可在线阅读，更多相关《关系模式分解PPT课件（99页珍藏版）》请在装配图网上搜索。

1、 4.3 数据依赖的公理系统数据依赖的公理系统4.4 关系模式的分解关系模式的分解本章小结本章小结一、问题一、问题如何构造一个关系模式如何构造一个关系模式n例：例：假设有学生关系模式假设有学生关系模式 其中，其中，S#S#学号、学号、SNAMESNAME学生姓名、学生姓名、CLASSCLASS班级、班级、C#C#课程号、课程号、TNAMETNAME教师姓名、教师姓名、TAGETAGE教师年龄、教师年龄、ADDRESSADDRESS教师地址、教师地址、GRADEGRADE成绩。成绩。S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE)S(S#,SNAME,C

2、LASS,C#,TNAME,TAGE,ADDRESS,GRADE)关系关系S S存在以下问题：存在以下问题：1 1数据冗余度高。数据冗余度高。SNAMESNAME、CLASSCLASS、TNAMETNAME、TAGETAGE、ADDRESSADDRESS重复存储多次。重复存储多次。2 2数据修改复杂。数据修改复杂。3 3插入异常。插入异常。插入异常插入异常是指应该插入到数据库中的数据不能执是指应该插入到数据库中的数据不能执行插入操作的情形。行插入操作的情形。关系关系S S的主码：的主码：（S#S#，C#C#）从在从在S#、C#、和、和(S#,c#)上出现上出现NULL值去分析。值去分析。注意：

3、注意：当一个元组在主码的属性上部分或全部为空当一个元组在主码的属性上部分或全部为空时，该元组不能插入到关系中。时，该元组不能插入到关系中。4 4删除异常。删除异常。删除异常删除异常是指不应该删去的数据被删去的情形。是指不应该删去的数据被删去的情形。例如：例如：选修某门课的所有学生都退选时，删除相关元组，选修某门课的所有学生都退选时，删除相关元组，会丢失该课程老师的信息。会丢失该课程老师的信息。解决：解决：关系模式分解（关系规范化）关系模式分解（关系规范化）分解为分解为 ST(S#ST(S#，SNAMESNAME，CLASS)CLASS)CT(C#,TNAME)CT(C#,TNAME)TA(TN

4、AME,TAGE,ADDRESS)TA(TNAME,TAGE,ADDRESS)SC(S#,C#,GRADE)SC(S#,C#,GRADE)二、函数依赖二、函数依赖functional dependency,abbr.FDn设：设：R（A1，A2，An)=R(U)nX，Y，Z 为为U的不同子集的不同子集n定义定义4.1：函数依赖函数依赖 是完整性约束的一种，它推广了关键词是完整性约束的一种，它推广了关键词的概念。的概念。If t1.X=t2.X,then t1.Y=t2.Y 函数依赖函数依赖：若：若R的任意关系有：对的任意关系有：对X中的每个属性值，中的每个属性值，在在Y中都有惟一的值与之对应，

5、则称中都有惟一的值与之对应，则称Y函数依赖于函数依赖于X，记作记作 XY。属性全集属性全集n例：指出下列关系例：指出下列关系R中的函数依赖。中的函数依赖。A B C D a1 b1 c1 d1 a1 b1 c1 d2 a1 b2 c2 d1 a2 b1 c3 d1nFD:AB-C、AC、CA、ABD？nInsert into R values(a1,b1,c2,d1)nFD=key constraint?函数依赖与属性间的关系函数依赖与属性间的关系有：有：n若若X，Y是是1 1关系，关系，则存在则存在 XY或或Y X。如学号与借书证号。如学号与借书证号n若若X，Y是是m 1关系，关系，则存在则

6、存在 XY但但 Y+X。如学号与姓名。如学号与姓名n 若若X，Y是是m n关系，关系，则则X，Y间不存在函数依赖关系。如姓名与课程间不存在函数依赖关系。如姓名与课程CF:实体间的联系实体间的联系NOTE:函数依赖的方向性函数依赖的方向性n例例 试指出学生关系试指出学生关系S(S#S(S#，SNAMESNAME，CLASSCLASS，C#C#，TNAMETNAME，TAGETAGE，ADDRESSADDRESS，GRADE)GRADE)中存在的函数依赖关系。中存在的函数依赖关系。S#SNAMES#SNAME（每个学号只能有一个学生姓名）（每个学号只能有一个学生姓名）S#CLASSS#CLASS（

7、每个学号只能有一个班级）（每个学号只能有一个班级）C#TNAMEC#TNAME（设每门课程只有一个教师任教，而一个教师可教多门（设每门课程只有一个教师任教，而一个教师可教多门课程，见课程，见CTCT表）表）TNAMETAGETNAMETAGE（每个教师只能有一个年龄）（每个教师只能有一个年龄）TNAMEADDRESSTNAMEADDRESS（每个教师只能有一个地址）（每个教师只能有一个地址）(S#(S#，C#)GRADEC#)GRADE（每个学生学习一门课只能有一个成绩）（每个学生学习一门课只能有一个成绩）(S#(S#，C#)SNAMEC#)SNAME、(S#(S#，C#)CLASSC#)CL

8、ASS、(S#(S#，C#)C#C#)C#、(S#(S#，C#)TNAMEC#)TNAME、(S#(S#，C#)TAGEC#)TAGE、(S#(S#，C#)ADDRESSC#)ADDRESS 三、函数依赖的分类三、函数依赖的分类 XY，但，但Y 不包含于不包含于 X则称则称X是非平凡的函数依赖。是非平凡的函数依赖。XY，但，但Y X 则称则称X是平凡的函数依赖。是平凡的函数依赖。若若XY，则，则X叫做决定因素。叫做决定因素。若若XY，Y X，则记作则记作:XY。定义定义4.2：在在R(U)中，中，X,Y,Z为为U的不同子集。的不同子集。n完全函数依赖完全函数依赖:是指是指 XY，且对任何且对任

9、何X的真子集的真子集X，都有都有X+Y，记作：记作：X F Y。n部分函数依赖部分函数依赖:是指是指XY，且存在且存在X的真子集的真子集X，有有X-Y，记作：记作：X P Y。定义定义4.3：在在R(U)中中n传递函数依赖：传递函数依赖：是指若是指若XY(Y 不包含于不包含于 X)，Y+X，而而Y Z。记作：。记作：X T Z。n左部为单属性的函数依赖一定是完全函数依赖。左部为单属性的函数依赖一定是完全函数依赖。n左部为多属性的函数依赖，如何判断其是否为完全函数依赖？左部为多属性的函数依赖，如何判断其是否为完全函数依赖？方法：取真子集，看其能否决定右部属性。方法：取真子集，看其能否决定右部属性

10、。例：例：试指出学生关系试指出学生关系S S中存在的完全函数依赖和部分函数依赖。中存在的完全函数依赖和部分函数依赖。nS#SNAMES#SNAME，S#CLASSS#CLASS，TNAMETAGETNAMETAGE，TNAMEADDRESSTNAMEADDRESS，C#TNAMEC#TNAME都是完全函数依赖。都是完全函数依赖。n(S#(S#，C#)GRADE C#)GRADE 是一个完全函数依赖，因为是一个完全函数依赖，因为S#S#+GRADEGRADE，C#C#+GRADEGRADE。例：试指出学生关系例：试指出学生关系S S中存在的传递函数依赖。中存在的传递函数依赖。解：因为解：因为C#

11、TNAMEC#TNAME，TNAMETNAME+C#C#，TNAMETAGETNAMETAGE，所以，所以C#TAGE C#TAGE 是一个传递函数依赖。类似地，是一个传递函数依赖。类似地，C#ADDRESSC#ADDRESS也是一个传递函数也是一个传递函数依赖。依赖。n(S#(S#，C#)SNAMEC#)SNAME，(S#(S#，C#)CLASSC#)CLASS，(S#(S#，C#)TNAMEC#)TNAME，(S#(S#，C#)TAGEC#)TAGE，(S#(S#，C#)ADDRESSC#)ADDRESS都是部分函数依赖，因为都是部分函数依赖，因为S#SNAMES#SNAME，S#CLAS

12、SS#CLASS，C#TNAMEC#TNAME，C#TAGEC#TAGE，C#ADDRESSC#ADDRESS。四、候选码四、候选码 用函数依赖的概念来定义码。用函数依赖的概念来定义码。定义定义4.4:设设X为为R中的属性或属中的属性或属性组合，若性组合，若 X F U 则则X为为R的的候选码。候选码。说明：说明：X F U X-U X能决定整个元组能决定整个元组 X+U X中无多余的属性中无多余的属性 术语：术语：主码主码 主属性主属性:侯选码中的属性侯选码中的属性 非主属性非主属性 全码：全码：整个属性组为码整个属性组为码 例：例：R(顾客，商品，日期顾客，商品，日期)n例：例：试指出下列

13、关系试指出下列关系R R中的侯选码、主属性和非主属性。中的侯选码、主属性和非主属性。A D E a1 d1 e2 a2 d6 e2 a3 d4 e3 a4 d4 e4解：关系解：关系R的的侯选码侯选码为：为：A，(D,E)关系关系R R的的主属性主属性为：为：A，D，E 关系关系R R的的非主属性非主属性：无：无 函数依赖判断：函数依赖判断：A-D?D-A?AD-E?候选码判断候选码判断:A-ADE?AD-ADE?例例1.R(A,B,C,D)，F=A-B,A-C,AB-D解：由解：由 AB-A(自反律自反律)和和 A-C(已知已知)得：得：AB-C(传递律传递律)又因为又因为 AB-A(自反律

14、自反律)，AB-B(自反律自反律)和和 AB-D(已知已知)得：得：AB-ABCD。AB是是R的唯一候选码，同时也是的唯一候选码，同时也是R的主码。的主码。例例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是主码。是主码。一、关系与范式关系与范式n关系的规范化是

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

16、据项，则的每个分量都是不可分的数据项，则R1NF。从型上看：不存在嵌套结构从型上看：不存在嵌套结构 从值上看，不存在重复组从值上看，不存在重复组 1NF是关系模式的最低要求。是关系模式的最低要求。n例：例：学生关系学生关系S(S#S(S#，SNAMESNAME，CLASSCLASS，C#C#，TNAMETNAME，TAGETAGE，ADDRESSADDRESS，GRADE)GRADE)是是1NF1NF关系，但它存在数据冗余，插入关系，但它存在数据冗余，插入异常和删除异常等问题。异常和删除异常等问题。三、第二范式：三、第二范式：2NF 定义定义4.64.6 若若R1NFR1NF，且，且R R中的

17、每一个非主属性都完全函数中的每一个非主属性都完全函数依赖于依赖于R R的任一候选码，则的任一候选码，则R2NFR2NF。n例：例：学生关系学生关系S(S#S(S#，SNAMESNAME，CLASSCLASS，C#C#，TNAMETNAME，TAGETAGE，ADDRESSADDRESS，GRADE),GRADE),判断判断R R是否为是否为2NF?2NF?n侯选码为侯选码为(S#(S#，C#)C#)，非主属性有：，非主属性有：SNAMESNAME，CLASSCLASS，TNAMETNAME，TAGETAGE，ADDRESSADDRESS，GRADEGRADE (S#(S#，C#)C#)SNAM

18、ESNAME，S#S#SNAMESNAME (S#(S#，C#)C#)P SNAMESNAME S S 2NF(2NF(每一个非主属性每一个非主属性!)。n分解为分解为2NF的方法：破坏部分依赖的条件。的方法：破坏部分依赖的条件。将满足部分函数依赖和满足完全函数依赖的属性分解将满足部分函数依赖和满足完全函数依赖的属性分解到不同的关系中。到不同的关系中。n对上例，考察非主属性和侯选码之间的函数依赖关系：对上例，考察非主属性和侯选码之间的函数依赖关系：(S#S#，C#)C#)P SNAMESNAME，(S#S#，C#)C#)P CLASSCLASS，(S#(S#，C#C#)P TNAMETNAME

19、，(S#(S#，C#C#)P TAGETAGE，(S#(S#，C#C#)P ADDRESSADDRESS，(S#(S#，C#)C#)F GRADEGRADE 区分出完全依赖和部分依赖，若是部分依赖，标记出其区分出完全依赖和部分依赖，若是部分依赖，标记出其中的主属性。中的主属性。n关系关系S S分解为三个关系：分解为三个关系：ST(ST(S#S#，SNAMESNAME，CLASS)CLASS)（只依赖（只依赖S#S#的属性分解到一个子模的属性分解到一个子模式中）式中）CTA(CTA(C#C#，TNAMETNAME，TAGETAGE，ADDRESS)ADDRESS)（只依赖（只依赖C#C#的属性分

20、的属性分解到另一个子模式中）解到另一个子模式中）SC(SC(S#S#，C#C#，GRADE)GRADE)（完全函数依赖于候选码的属性分解（完全函数依赖于候选码的属性分解到第三个子模式中）到第三个子模式中）分解后，分解后，关系关系STST、CTACTA和和SCSC都为都为2NF2NF。结论结论1：若关系若关系R的侯选码是单属性的，则的侯选码是单属性的，则R必定是必定是2NF。n达到达到2NF2NF的关系仍然可能存在问题。的关系仍然可能存在问题。例如，在例如，在关系关系CTACTA中还存在以下问题：中还存在以下问题：（1 1）数据冗余。一个教师承担多门课程时，教师的姓名、数据冗余。一个教师承担多门

21、课程时，教师的姓名、年龄、地址要重复存储。年龄、地址要重复存储。（2 2）修改复杂。一个教师更换地址时，必须修改相关的修改复杂。一个教师更换地址时，必须修改相关的多个元组。多个元组。（3 3）插入异常。一个新教师报到，需将其有关数据插入插入异常。一个新教师报到，需将其有关数据插入到到CTACTA关系中，但该教师暂时还未承担任何教学任务，关系中，但该教师暂时还未承担任何教学任务，则因缺码则因缺码C#C#值而不能进行插入操作。值而不能进行插入操作。（4 4）删除异常。删除某门课程时，会丢失该课程任课教删除异常。删除某门课程时，会丢失该课程任课教师的姓名、年龄和地址信息。师的姓名、年龄和地址信息。四

22、、第三范式：四、第三范式：3NF定义定义4.74.7 如果关系如果关系R R的任意一个非主属性都不传递函数依的任意一个非主属性都不传递函数依赖于它的任意一个候选码，则赖于它的任意一个候选码，则R3NFR3NF。n关系关系CTA(CTA(C#C#，TNAMETNAME，TAGETAGE，ADDRESS)ADDRESS)是是2NF2NF，但不是，但不是3NF3NF。n候选码：候选码：C#C#，非主属性：，非主属性：TNAMETNAME、TAGETAGE、ADDRESSADDRESS。由于由于C#TNAMEC#TNAME，TNAMETNAME+C#C#，TNAMETAGETNAMETAGE，所以，所

23、以 C#C#T TAGE TAGE，同样有，同样有C#C#T ADDRESSADDRESS，即存在非，即存在非主属性对候选码的传递函数依赖。主属性对候选码的传递函数依赖。关系模式关系模式R（A，B，C，D），码为），码为AB，给出它的，给出它的一个函数依赖集，使得一个函数依赖集，使得R属于属于2NF而不属于而不属于3NFn分解为分解为3NF3NF的方法：破坏传递依赖的条件。的方法：破坏传递依赖的条件。将涉及传递函数依赖中的两个依赖中的属性分解到不同的关系中。将涉及传递函数依赖中的两个依赖中的属性分解到不同的关系中。n例：例：CTACTA中，两个传递依赖中，两个传递依赖C#C#T TAGE TA

24、GE，C#C#T ADDRESSADDRESS C#TNAME C#TNAME，TNAMETNAME+C#C#，TNAMETAGETNAMETAGE。C#TNAMEC#TNAME，TNAMETNAME+C#C#，TNAMEADDRESSTNAMEADDRESS。n将将CTACTA分解为：分解为：CT(C#CT(C#，TNAME)TNAME)TA(TNAME TA(TNAME，TAGETAGE，ADDRESS)ADDRESS)则关系则关系CTCT和和TATA都是都是3NF3NF，关系，关系CTACTA中存在的问题得到了解决。中存在的问题得到了解决。n 定理定理4.14.1 一个一个3NF3NF的

25、关系必定是的关系必定是 2NF2NF。（3NF3NF传递函数依赖，传递函数依赖，2NF2NF完全函数依赖。）完全函数依赖。）证明：证明：用反证法。设用反证法。设R3NFR3NF，但，但R R 2NF2NF，则，则R R中必有非中必有非主属性主属性A A、侯选码、侯选码X X和和X X的真子集的真子集XX存在，使得存在，使得XAXA。nXX是侯选码是侯选码X X的真子集，有的真子集，有X-XX-X；A A是非主属性，是非主属性，A-XA-X，A-XA-X，这样，这样A A、X X、XX是是U U的不同子集。的不同子集。nXX是侯选码是侯选码X X的真子集，则有的真子集，则有XX XX 且且 XX

26、+X X，联，联合反证假设合反证假设XAXA可知存在传递依赖（可知存在传递依赖（XXXX，XX+X X，XAXA）nR R不是不是3NF3NF，与题设矛盾。，与题设矛盾。n通过转为通过转为2NF2NF消除了部分依赖，通过转为消除了部分依赖，通过转为3NF3NF消除了传递消除了传递依赖，依赖，问题：达到问题：达到3NF3NF的关系是否仍然存在问题？的关系是否仍然存在问题？n例：例：每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称：解：关系解：关系SCTSCT的的侯选码侯选码：(S#(S#，CNAME)CNAME)和和

27、(S#(S#，TNAME)TNAME)非主属性：非主属性：无无 （SCTSCT至少是一个至少是一个3NF3NF关系关系)结论结论2 2：若关系若关系R R的所有属性都是主属性，则的所有属性都是主属性，则R R必定是必定是3NF3NF。S#S#CNAMECNAME TNAME TNAME s1 s1 英语英语 王平王平 s1 s1 数学数学 刘红刘红 s2 s2 物理物理 高志强高志强 s2 s2 英语英语 陈进陈进 s3 s3 英语英语 王平王平候选码判断候选码判断:S#-S#CNAME TNAME.取左部的相同值，判断右部。取左部的相同值，判断右部。在在3NF3NF关系关系SCTSCT中存在

28、：中存在：n插入异常。例如，一个新课程和任课教师的数据，在没插入异常。例如，一个新课程和任课教师的数据，在没有学生选课时不能插入数据库。有学生选课时不能插入数据库。n删除异常。例如，删除某门课的所有选课记录，会丢失删除异常。例如，删除某门课的所有选课记录，会丢失课程与教师的数据。课程与教师的数据。n达到达到3NF3NF的关系仍然可能存在问题。的关系仍然可能存在问题。五、五、BCNF 定义定义4.84.8 关系模式关系模式RUR1NFF1NF。若函数依赖集合。若函数依赖集合F F中的中的所有函数依赖所有函数依赖XYXY（Y Y不包含于不包含于X X）的左部都包含）的左部都包含R R的任一侯选码，

29、的任一侯选码，则则RBCNFRBCNF。换言之，换言之，BCNF中的所有依赖的左部都必须包含候选中的所有依赖的左部都必须包含候选码码。n 例：关系例：关系SCTSCT是否是否BCNF?BCNF?因为因为TNAMECNAMETNAMECNAME，其左部未包含该关系的任一侯选码，其左部未包含该关系的任一侯选码，所以它不是，所以它不是BCNFBCNF。n 解决：解决：BCNFBCNF分解。分解。n分解为分解为BCNF的方法：的方法：消除不包含关系。1.假设R(U)不是BCNF,X是R的属性子集，A是R的单个属性，X-A是导致违反BCNF的函数依赖，则将R分解为R-A 以及 XA。2.若R-A以及 X

30、A 仍然不是BCNF，则在R-A 以及 XA递归地执行上述分解。n例例 SCTSCT：(S#(S#，CNAMECNAME，TNAME)TNAME)，FD:TNAMECNAMEFD:TNAMECNAME。可分解为可分解为SC(S#SC(S#，TNAME)TNAME)和和CT(CNAMECT(CNAME，TNAME)TNAME)，它们都，它们都是是BCNFBCNF。定理定理4.24.2：一个一个BCNFBCNF的关系必定是的关系必定是3NF3NF。（3NF3NF：任意的非主属性都不传递依赖于任意一个候选：任意的非主属性都不传递依赖于任意一个候选码。）码。）证明：用反证法。设证明：用反证法。设R R

31、是一个是一个BCNFBCNF，但不是，但不是3NF3NF，则必存在，则必存在一个非主属性一个非主属性A A和候选码和候选码X X以及属性集以及属性集Y Y，使得，使得A A传递依赖传递依赖于于X X，即，即XY(YXY(Y不包含于不包含于X)X)，Y Y+X X，YAYA。这就是说这就是说Y Y不包含不包含R R的候选码，但的候选码，但YAYA却成立。却成立。根据根据BCNFBCNF定义可知，定义可知，R R不是不是BCNFBCNF，与题设矛盾。，与题设矛盾。结论结论3 3：任何的二元关系必定是任何的二元关系必定是BCNFBCNF。n3NF下仍然存在插入异常和删除异常，下仍然存在插入异常和删除

32、异常，原因在于可能原因在于可能存在主属性对候选码的部分函数依赖和传递函数依赖。存在主属性对候选码的部分函数依赖和传递函数依赖。n一个模式中的关系模式如果都属于一个模式中的关系模式如果都属于BCNF，则在，则在函数依函数依赖的范畴内赖的范畴内实现了彻底的分离，已消除了插入和删除的实现了彻底的分离，已消除了插入和删除的异常。异常。n其它问题？其它问题？六、第四范式：六、第四范式：4NF定义定义4.10 4.10 若若R 1NF，D是是R上的依赖集，如果上的依赖集，如果对于任何一个多值依赖对于任何一个多值依赖XY(Y-X,XY没没有包含有包含R的全部属性的全部属性)，X都包含了都包含了R的一个候选的

33、一个候选关键词，则关键词，则R4NF。n4NF必定是必定是BCNF，但，但BCNF不一定是不一定是4NF。n5种范式的关系：种范式的关系：4.2 4.2 关系模式的规范化关系模式的规范化1NF非规范化的关系非规范化的关系2NF3NF消除组合数据项消除组合数据项消除非主属性对码消除非主属性对码的部分函数依赖的部分函数依赖消除非主属性对码消除非主属性对码的传递函数依赖的传递函数依赖4NF消除非平凡的消除非平凡的多值依赖多值依赖BCNF消除主属性对码的部消除主属性对码的部分和传递函数依赖分和传递函数依赖范式的范式的转换关系：转换关系：1NF2NF3NFBCNF4NFn关系的规范化是将一个低级范式的关

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

35、值依赖。多值依赖。1.阿氏公理阿氏公理定义定义4.134.13 设设F F是关系模式是关系模式R R的函数依赖集，的函数依赖集，X X、Y Y是是R R的属的属性子集，如果从性子集，如果从F F的函数依赖中能够推出的函数依赖中能够推出X XY Y，则称则称F F逻辑蕴逻辑蕴涵涵X XY Y。在在R 中为中为F所逻辑蕴含的函数依赖全体叫所逻辑蕴含的函数依赖全体叫F的闭的闭包，记为：包，记为：F+。F+=F；F中推出的非平凡的函数依赖；中推出的非平凡的函数依赖；平凡的函数依赖：平凡的函数依赖：A-、A-A、AB-A.例：例：有关系模式有关系模式R(AR(A，B B，C)C)，它的函依赖集，它的函依

36、赖集F=ABF=AB，BCBC，计算计算F F的闭包的闭包。nArmstrongArmstrong公理公理(阿氏公理阿氏公理)：对对RUR F 有：有：nA1A1自反律：若自反律：若Y YX X，则，则X XY Y。nA2A2增广律：若增广律：若X XY Y，则，则XZXZYZYZ。nA3A3传递律：若传递律：若X XY Y、Y YZ Z，则，则X XZ Z。nNoteNote：XYXY与与YXYX的次序无关。的次序无关。n证：证：设设s，t是是r的任意两个元组，的任意两个元组，r是是R的任意一个关系。的任意一个关系。nA1自反律：若自反律：若YX，则，则XY。若若sx=tx，则在，则在s和和

37、t中的中的x的任何子集也必相等。的任何子集也必相等。YX，sy=ty XY。nA2增广律：若增广律：若XY，则，则XZYZ。若若sxz=txz，即，即sxsz=txtz 则则 sx=tx 且且 sz=tz XY，sy=ty syz=sysz=tytz=tyz XZYZnA3传递律：若传递律：若XY、YZ，则，则XZ。若若s sx=tx XY sy=ty 又又 YZ sz=tz XZ。n公理的推论公理的推论：合并规则：若合并规则：若XY、XZ，则则XYZ。分解规则：若分解规则：若XYZ，则，则XY,XZ。伪传递规则：若伪传递规则：若XY、WYZ，则则WXZ。证明：证明：n合并规则：合并规则：XY

38、 XXY (A2)又又 XZ XYYZ (A2)XYZ (A3)n分解规则：分解规则：YY Z YZY (A1)又又 XYZ(已知）已知）XY (A3)同理可证同理可证XZ。伪传递规则：伪传递规则：XY WXWY (A2)又又 WYZ (已知已知)WXZ (A3)n定理定理4.54.5:XA1A2AK成立的充分必要条件是成立的充分必要条件是XAi成立。成立。由合并律 由分解律 n定义定义4.144.14:XF+=A|XA能由能由F用用阿氏阿氏公理导出公理导出 XF+称为属性集称为属性集X关于关于F的闭包。的闭包。n定理定理4.64.6：XY能从能从F中用中用阿氏阿氏公理导出的充要条件是：公理导

39、出的充要条件是：YXF+n定理定理4.6的证明的证明n证明：证明：充分性（充分性（YXF+-XY）假设假设YXF+(其中其中Y=A1A2An)由属性闭包定义可知，由属性闭包定义可知，XA1，XA2，XAn能由阿氏公理导出，再由合并规则得能由阿氏公理导出，再由合并规则得X A1A2An，即，即XY。必要性：（必要性：（XY-YXF+）假设假设XY能由阿氏公理导出能由阿氏公理导出(Y=A1A2An)则有则有XA1A2An 由分解规则得：由分解规则得：XA1，XA2，XAn 由由XF+的定义可知，的定义可知，Ai XF+(i=1,2,n)即即YXF+。nArmstrong公理完备性的证明证明：（构造

40、性证明）用反证法假定存在函数依赖XY被F逻辑蕴涵，但XY不能用Armstrong公理从F中导出由引理二，构造R(U)上的关系r如下：下面证明（1）r满足F，（2）r不满足XYFXFXFXY ，Y ，U r（U ）t 1 0s 1 1FXFX2.属性闭包的计算属性闭包的计算算法算法4.14.1:求属性集求属性集X关于关于F的闭包的闭包XF+(X+)。n算法：算法：设设 R，A为为U中属性中属性(集集)。(1)X(0)=X (2)X(i+1)=X(i)A 其中：对其中：对F中任一个中任一个Y-A，且，且YX(i)；求得求得X(i+1)后，对后，对Y-A 做删除标记。做删除标记。(3)若若X(i+1

41、)=X(i)或或 X(i+1)=U则结束，否则转则结束，否则转(2)。算法会终算法会终止吗？止吗？最多最多|U-X|步步n示例1R,U=(A,B,C,G,H,I),F=AB,AC,CGH,CGI,BH,计算 所用依赖 ABAGB ACAGBC CGHAGBCH CGIAGBCH I=AGBCH IFAG)(FAG)(FAG)(n示例2R,U=(A,B,C,D,E),F=ABC,BD,CE,CEB,ACB,计算所用依赖 ABCABC BDABCD CEABCDE=ABCDEFAB)(FAB)(FAB)(n示例3R,U=(A,B,C,D,E,G),F=AE,BEAG,CEA,GD,计算所用依赖 A

42、EABE BEAGABEG GDABEGD=ABEGDFAB)(FAB)(FAB)(3.3.函数依赖集的等价和覆盖函数依赖集的等价和覆盖定义定义4.154.15:如果如果F F+=G=G+，就说函数依赖集，就说函数依赖集F F覆盖覆盖G G或或F F与与G G等价。等价。定理定理4.94.9:F F+=G=G+的充分必要条件是的充分必要条件是F FG G+，和，和G GF F+。（1 1）必要性）必要性FF和和G G等价，等价，FF+=G=G+，又，又FFF F+，FFG G+同理，同理，GGG G+，GGF F+。（2 2）充分性）充分性任取任取XYFXYF+，则有，则有Y YX XF F+

43、(定理定理4.6)4.6)又又FFG G+（已知），（已知），YYX XG G+XY(GXY(G+)+=G=G+，FF+G G+。同理可证同理可证G G+F F+，FF+=G=G+，即，即F F和和G G等价。等价。n如何判断函数依赖集如何判断函数依赖集F F和和G G是否等价？是否等价？n根据根据定理定理4.94.9:只需只需F FG G+和和G GF F+，即证集合的包含关，即证集合的包含关系。系。对每个对每个T F,T F,有有T G+T G+；对每个；对每个S GS G，有，有S F+S F+，T T和和S S是形如是形如X-YX-Y的属性依赖。的属性依赖。n证证 X-Y G+,X-Y

44、 G+,根据根据定理定理4.64.6：只需只需Y Y X XG G+n转为计算转为计算X XG G+例：例：F=ABF=AB，BCBC，G=ABCG=ABC，BCBC，判断，判断F F和和G G是否是否等价。等价。解：（解：（1 1）先检查）先检查F F中的每一个函数依赖是否属于中的每一个函数依赖是否属于G G+。AAG G+=ABC=ABC，BBA AG G+，ABGABG+(定理定理4.6)4.6)又又BBG G+=BC=BC，CCB BG G+，BCGBCG+FFG G+（2 2）然后检查）然后检查G G中的每一个函数依赖是否属于中的每一个函数依赖是否属于F F+。AAF F+=ABC=

45、ABC，BCBCA AF F+，ABCFABCF+又又BBF F+=BC=BC，CCB BF F+，BCFBCF+GGF F+由（由（1 1）和（）和（2 2）可得）可得F F和和G G等价。等价。4.4.最小函数依赖集最小函数依赖集n定义定义4.164.16:若若F F满足下列条件，则称其为一个最小函数依满足下列条件，则称其为一个最小函数依赖集赖集FmFm。(1)(1)F F中每个函数依赖的右部都是单属性；中每个函数依赖的右部都是单属性；(2)(2)对于对于F F的任一函数依赖的任一函数依赖XAXA，F-XAF-XA与与F F都不等价；都不等价；(3)(3)对于对于F F中的任一函数依赖中的

46、任一函数依赖X XA A和和X X的真子集的真子集Z Z，(F-(XA)UZA(F-(XA)UZA与与F F都不等价。都不等价。最小：（最小：（1 1）F F中每个函数依赖的右部没有多余的属性；中每个函数依赖的右部没有多余的属性；（2 2）F F中不存在多余的函数依赖；中不存在多余的函数依赖；（3 3）F F中每个函数依赖的左部没有多余的属性中每个函数依赖的左部没有多余的属性。n定理定理4.104.10:每个每个F与与Fm等价。等价。n如何求最小函数依赖集如何求最小函数依赖集Fm？(1)分解：分解：使使F中任一函数依赖的右部仅含有单属性。中任一函数依赖的右部仅含有单属性。(2)删除冗余的函数依

47、赖删除冗余的函数依赖：方法：对方法：对F中任一中任一XA，在，在F-XA中求中求X+，若若AX+，则，则XA为多余的。为多余的。(3)最小化左边的多余属性：最小化左边的多余属性：方法：对方法：对F中任一中任一XYA，在，在F中求中求X+，若若AX+，则，则Y为多余的。为多余的。(4)检查：用公理或检查：用公理或(2)例：例：设有设有F=BCF=BC，CABCAB，BCABCA，求与，求与F F等价的最小函数依赖集。等价的最小函数依赖集。n分解分解CABCAB，F=BCF=BC，CACA，CBCB，BCABCAn判断判断BCBC是否冗余，是否冗余，F=CAF=CA，CBCB，BCABCA B B

48、+=B,BC=B,BC非冗余。非冗余。F=BCF=BC，CACA，CBCB，BCABCA 判断判断CACA是否冗余，是否冗余，F=BC,CBF=BC,CB，BCABCA C C+=ABC,CA=ABC,CA冗余。冗余。F=BCF=BC，CBCB，BCABCA 判断判断CBCB是否冗余，是否冗余，F=BC,BCAF=BC,BCA C C+=C,CB=C,CB非冗余。非冗余。F=BCF=BC，CBCB，BCABCA 判断判断BCABCA是否冗余，是否冗余，F=BCF=BC，CB CB BC C+=BC,BCA=BC,BCA非冗余。非冗余。F=BCF=BC，CBCB，BCABCAn判断判断BCABC

49、A。B+=ABC,A=ABC,AB+B+，则，则C C在在BCABCA中是多余的。中是多余的。Fmin=BCFmin=BC，CBCB，BABA注意：注意：对当前对当前F求闭包求闭包例：例：设有函数依赖集设有函数依赖集F=AB,ABCDE,EFG,EFH,ACDFEGF=AB,ABCDE,EFG,EFH,ACDFEG 求与求与F F等价的最小函数依赖集。等价的最小函数依赖集。注意：一个函数依赖集的最小集不是惟一的。注意：一个函数依赖集的最小集不是惟一的。例如，例如，F=ABF=AB，BABA，BCBC，ACAC，CACA Fm1=AB Fm1=AB，BCBC，CACA，Fm2=ABFm2=AB，

50、BABA，ACAC，CACA。方法方法1 1：无多余属性；依次判断无多余属性；依次判断B-A,A-CB-A,A-C是否冗余；是否冗余；方法方法2 2：无多余属性；依次判断无多余属性；依次判断B-CB-C是否冗余。是否冗余。Fmin=Fmin=AB,ACDE,EFG,EFHAB,ACDE,EFG,EFH n对于存在数据冗余、插入异常、删除异常的关系对于存在数据冗余、插入异常、删除异常的关系模式，可以通过对关系模式的分解来解决问题。模式，可以通过对关系模式的分解来解决问题。关系模式分解后会带来两个问题：关系模式分解后会带来两个问题：（1）查询时的连接操作是否会丢失某些信息或多）查询时的连接操作是否

51、会丢失某些信息或多出某些信息。这引出了无损连接的概念。出某些信息。这引出了无损连接的概念。（2）分解后的关系模式是否保持了原来的函数依）分解后的关系模式是否保持了原来的函数依赖。这是保持函数依赖性的问题。赖。这是保持函数依赖性的问题。1.等价模式分解的定义等价模式分解的定义 一个关系可以有多种分解方法，如何判断分解的好与坏一个关系可以有多种分解方法，如何判断分解的好与坏呢？呢？例：例：关系模式关系模式R(S#R(S#，SDSD，MN),F=S#SDMN),F=S#SD，SDSDMNMN分解一：分解一：1=R1(S#)1=R1(S#)，R2(SD)R2(SD)，R3(MN)R3(MN)不好！不好

52、！无法恢复无法恢复r.r.分解二：分解二：2=R1(S#2=R1(S#，SD)SD)，R2(S#R2(S#，MN)MN)不好！不好！丢失丢失SDSDMNMN分解三：分解三：3=R1(S#3=R1(S#，SD)SD)，R2(SDR2(SD，MN)MN)好！好！R(A,B,C)ABC112221AB1122BC1221ABC112221AB(R)BC(R)AB(R)BC(R)R(A,B,C)ABC111212AB1121BC1112ABC111112211212AB(R)BC(R)AB(R)BC(R)有损分解有损分解无损分解无损分解2.2.无损连接性与依赖保持性无损连接性与依赖保持性 n对于对于R

53、中任何一个关系中任何一个关系r，R分解分解=R1,R2.RKn无损连接性：无损连接性：r=R1(r)R2(r)RK(r)n保持函数依赖：保持函数依赖：F R1(F)R2(F)RK(F)Ri(F)=X-Y|X-YF+XYRi Ri所蕴含的所蕴含的F+中的函数依赖中的函数依赖例：例：R(A，B，C)，F=A-B，A-C，分解，分解=AB，AC 判断判断1：r=AB(r)|X|AC(r)是无损连接分解。是无损连接分解。判断判断2:FAB(F)AC(F)=A-B，A-C 具有函数依赖保持性。具有函数依赖保持性。ABCa1b1c1a2b2c2a3b1c2r?=AB，BCn算法算法4.3 无损连接性检验。

54、无损连接性检验。输入：输入：关系模式关系模式R(AR(A1 1，A A2 2，A An n)，它的函数依赖集，它的函数依赖集F F，以及分，以及分解解=R=R1 1，R R2 2，R Rk k。输出：输出：确定确定是否具有无损连接性。是否具有无损连接性。方法：方法：(1)(1)构造一个构造一个k k行行n n列的表，第列的表，第i i行对应于关系模式行对应于关系模式R Ri i，第，第j j列列对应于属性对应于属性A Aj j。如果。如果A Aj jRRi i，则在第，则在第i i行第行第j j列上放符号列上放符号a aj j，否则放，否则放符号符号b bijij。（属于用（属于用a a代表，

55、且位置信息用代表，且位置信息用j j表示；不属于用表示；不属于用b b代表代表,且且位置信息用位置信息用ijij表示。）表示。）(2)(2)重复考察重复考察F F中的每一个函数依赖，并修改表中的元素。其方中的每一个函数依赖，并修改表中的元素。其方法如下：取法如下：取F F中一个函数依赖中一个函数依赖XYXY，在，在X X的分量中寻找相同的行，然的分量中寻找相同的行，然后将这些行中后将这些行中Y Y的分量改为相同的符号，如果其中有的分量改为相同的符号，如果其中有a aj j，则将，则将b bijij改改为为a aj j；若其中无；若其中无a aj j，则全部改为，则全部改为b bijij（i i

56、是这些行的行号最小值）。是这些行的行号最小值）。(3)(3)如果发现表中某一行变成了如果发现表中某一行变成了a al l，a a2 2，a an n，则分解，则分解 具有无损连接性；如果具有无损连接性；如果F F中所有函数依赖都不能再修改中所有函数依赖都不能再修改 表中的内容，且没有发现这样的行，则分解表中的内容，且没有发现这样的行，则分解不具有无不具有无 损连接性。损连接性。n示例一：U=A,B,C,D,E,F=ABC,CD,DE=(A,B,C),(C,D),(D,E)ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2

57、a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCABCDEABCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5CDABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b32b33a4a5DEn示例二：U=A,B,C,D,E,F=AC,BC,CD,DEC,CEA=(A,D),(A,B),(B,E),(C,D,E),(A,E)ABCDEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b32b33b54a5ACABCDEADa1b

58、12b13a4b15ABa1a2b13b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b32b13b54a5BCABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b13b34a5CDEb41b42a3a4a5AEa1b32b13b54a5CDABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2b13a4a5CDEb41b42a3a4a5AEa1b32b13a4a5DECABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2a3a4a5CDEb41b42a3a4a5AEa1

59、b32a3a4a5CEAABCDEADa1b12b13a4b15ABa1a2b13a4b25BEa1a2a3a4a5CDEa1b42a3a4a5AEa1b32a3a4a5n定理定理4.124.12 设设=(R1=(R1，R2)R2)是是R R的一个分解，的一个分解，F F是是R R上的函数上的函数 依赖集，分解依赖集，分解具有无损连接性的充分必要条件是：具有无损连接性的充分必要条件是：R1R2(R1-R2)FR1R2(R1-R2)F+或或 R1R2(R2-R1)FR1R2(R2-R1)F+证明：证明：（1 1）充分性：设）充分性：设R1R2(R1-R2)R1R2(R1-R2)，按算法，按算法5

60、.25.2可构造出下表。可构造出下表。表中省略了表中省略了a a和和b b的下标，这无关紧要。的下标，这无关紧要。Ri R1R2 R1R2 R1-R2 R1-R2 R2-R1 R2-R1 R1 aaa aaa bbb R2 aaa bbb aaa只能用于判断分解为只能用于判断分解为2个子模式的情况。个子模式的情况。如果如果R1R2(R1-R2)R1R2(R1-R2)在在F F中，则可将表中第中，则可将表中第2 2行位于行位于(R1-R2)(R1-R2)列列 中的所有符号都改为中的所有符号都改为a a，这样该表中第，这样该表中第2 2行就全是行就全是a a了，则了，则具有无具有无 损连接性。同理

61、可证损连接性。同理可证R1R2(R2-R1)R1R2(R2-R1)的情况。的情况。如果如果R1R2(R1-R2)R1R2(R1-R2)不在不在F F中，但在中，但在F F+中，即它可以用公理从中，即它可以用公理从 F F中推出来，从而也能推出中推出来，从而也能推出R1R2Ax,R1R2Ax,其中其中AxAxR1-R2R1-R2，所以可，所以可 以将以将AxAx列的第列的第2 2行改为全行改为全a a，同样可以将，同样可以将R1-R2R1-R2中的其他属性的第中的其他属性的第2 2 行也改为行也改为a a，这样第，这样第2 2行就变成全行就变成全a a行。所以分解行。所以分解=R1=R1，R2R

62、2具有具有 无损连接性。无损连接性。同样可以证明同样可以证明R1R2(R2-R1)R1R2(R2-R1)的情况。的情况。（2 2）必要性：设构造的表中有一行全为）必要性：设构造的表中有一行全为a a，例如第，例如第1 1行全为行全为a a，则，则 由函数依赖定义可知由函数依赖定义可知R1R2(R2-R1)R1R2(R2-R1)；如果是第；如果是第2 2行全为行全为a a，则，则 R1R2(R1-R2)R1R2(R1-R2)。定理证毕。定理证毕。例例:下列分解是否具有无损连接性和函数依赖保持性。下列分解是否具有无损连接性和函数依赖保持性。已知：已知：R(A,B,C)F=ABR(A,B,C)F=A

63、B，CBCB(1(1）1 1=AB=AB，BCBC（2 2）2 2=AC=AC，BCBC RiABCABa1a2b13BCb21 a2a3（1 1）对）对1 1和和F F构造表：构造表：（2 2）检查）检查F=ABF=AB，CBCB 对对ABAB，A A列中无相同的行；列中无相同的行；对对CB,CCB,C列中无相同的行。列中无相同的行。1 1不具有无损连接性。不具有无损连接性。n1 1=AB=AB，BCBC F=AB F=AB，CBCBn1=AB1=AB，BCBC F=AB F=AB，CBCB 利用定理利用定理4.124.12解。解。R1R2=BR1R2=B (R1-R2)=A (R1-R2)

64、=A R1R2 R1R2+(R1-R2)(R1-R2)1 1不是无损连接分解。不是无损连接分解。RiABCACa1b12 a3BCb21 a2a3n2 2=AC=AC，BCBC F=AB F=AB，CBCBn对对2 2和和F F构造表：构造表：检查检查F=ABF=AB，CBCB 对对CB,CB,C C列列有相同的行，改有相同的行，改写写B B列列的相异符号为的相异符号为a a，下标为，下标为列号列号2 2。第一行变为。第一行变为a1a2a3,a1a2a3,2 2具有无损连接性。具有无损连接性。RiABCACa1a2a3BCb21 a2a3n2=AC2=AC，BCBC F=AB F=AB，CBC

65、Bn利用定理利用定理4.124.12解。解。R1R2=CR1R2=C (R1-R2)=A (R1-R2)=A；(R2-R1)=B(R2-R1)=B；R1R2 R1R2+(R2-R1)(R2-R1)2 2是无损连接分解。是无损连接分解。3.模式分解的方法模式分解的方法n3NF的保持无损连接及函数依赖的分解：的保持无损连接及函数依赖的分解：设：设：R 1)对对Fm中任一中任一X-A，若，若XA=U则不分解，结束。则不分解，结束。2)若若R中中Z属性在属性在Fm中未出现，则所有中未出现，则所有Z为一个子模式，为一个子模式，令令U=U-Z。3)对对Fm中中 X-A1，.X-An，用合成规则合成一个，用

66、合成规则合成一个，再对再对Fm中每个中每个X-A，令，令Ri=XA。4)R的分解为的分解为R1，R2，.RK，码码依赖保持不需要；依赖保持不需要；原包含有不需要。原包含有不需要。nBCNF的保持无损连接的分解：的保持无损连接的分解：（1 1）令）令=R=R；（2 2）如果）如果中所有关系模式都是中所有关系模式都是BCNFBCNF，则转（，则转（4 4）；）；（3 3）如果）如果中有一个关系模式中有一个关系模式R Ri iU 不是不是BCNFBCNF，则，则R Ri i中必有中必有XAFXAFi i+(A(A X)X)，且，且X X不是不是R Ri i的码的码。设。设S1=XAS1=XA，S2=Ui-AS2=Ui-A，用分解，用分解SS1 1，S S2 2 代替代替R Ri iU，转（，转（2 2）；）；（4 4）分解结束，输出）分解结束，输出。例：设例：设R=A,B,C,D,F=ACR=A,B,C,D,F=AC，CACA，BACBAC，DACDAC，BDABDA （1）将）将R 分解为分解为3NF且具有无损连接性和依赖保持性。且具有无损连接性和依赖保持性。（2）将）将R 分解为分解为B