关系规范化基础

1、第三章关系规范化基础一、内容提要关系数据库的设计中，一个非常重要的被视为理论问题的内容是如何构造合理的关系，使之能准确地反应现实世界，有利于应用和具体的操作。这一问题就是关系规范化要研究的问题。通过本章的学习，应重点掌握：函数依赖及Armstrong公理系统为什么要对模式进行分解，如何分解如何判断关系模式达到几范式如何求属性的闭包及如何求最小函数依赖集判断分解后的关系模式是不是无损连接或保持函数依赖判断分解后的关系模式既无损连接又保持函数依赖(一)函数依赖及相关概念定义设R(U)是属性集U上的关系模式，X,Y是U的子集。若对R(U)的任何一个可能的关系r，r中不可能存在两个元组在X上的属性值相

2、等，而在Y上的属性值不等，则称X函数决定Y或Y函数依赖于X,记作：XY。完全函数依赖：在R(U)中，如果XY，并且对于X的任何一个真子集X、，都有X、不能决定Y，则称Y对X完全函数依赖，记作：XY例给定一个学生选课关系SC(Sno，Cno，G)，我们可以得到F=(Sno，Cno)G，对(Sno,Cno)中的任何一个真子集Sno或Cno都不能决定G，所以，G完全依赖于Sno，Cno。平凡的函数依赖：如果XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：XY传递依赖：在R(U)中，如果XY，(YX)，YX，YZ则称Z对X传递依赖。码：设K为R(U，F)中的属性的组合，若KU，则K为R的候

3、选码，若有多个候选码，选一个作为主码。注:候选码也称候选关键字。(5)主属性和非主属性：包含在任何一个候选码中的属性叫做主属性，否则叫做非主属性。外码：若R(U)中的属性或属性组X非R的码，但是另一关系的码，则称X为外码。范式在关系数据库中的一个非常重要的问题就是如何评价分解后的各个关系模式的好坏。通常可以通过判断分解后的模式达到几范式来评价模式的好坏。范式有1NF、2NF、3NF、BCNF、4NF和5NF。这几种范式之间的关系如下：1NF2NF3NFBCNF4NF5NF通过模式分解，将低一级范式的关系模式分解成了若干个高一级范式的关系模式的集合，这种过程叫做规范化。下面将给出各个范式的定义。

4、1.1NF(第一范式)定义若关系模式R的每一个分量是不可再分的数据项，则关系模式R属于第一范式(1NF)。例供应者和它所提供的零件信息，关系模式如下：FIRST(Sno,Sname,Status,City,Pno,Qty)并且有F=SnoSname,SnoStatus,StatusCity,(Sno,Pno)Qty。具体的关系如图5l所示。SnoSnameStatusCityPnoQtyS1精益20天津P1200S1精益20天津P2300S1精益20天津P3480S2盛锡10北京P2168S2盛锡10北京P3500S3东方红30北京P1300S3东方红30北京P2280S4泰达20上海P246

5、0从图51中可以看出，每一个分量都是不可再分的数据项，所以是1NF。但是，1NF带来四个问题：冗余度大：例如每个供应者的Sno，Sname，Status，City要与零件的种类一样多；引起修改操作的不一致性：例如供应者S1从“天津”搬到“上海”，若稍不注意，就会使一些数据被修改，另一些数据没有被修改，导致数据修改的不一致性；插入异常：若某个供应者的其它信息未提供时，如“零件号”，则不能进行插入操作；更新异常：若供应商S4的P2零件销售完了，删除后，在基本关系FIRST找不到S4，可S4又是客观存在的。正因为上述原因引入了2NF。2NF(第二范式)定义若关系模式RINF，且每一个非主属性完全依赖

6、于码，则关系模式R2NF。即当1NF消除了非主属性对码的部分函数依赖，则成为2NF。例FIRST关系中的码是Sno、Pno,而SnoStatus，因此非主属性Status部分函数依赖于码，故非2NF的。若此时，将FIRST关系分解为：FIRSTl(Sno,Sname,Status，City)2NFFIRST2(Sno，Pno，Qty)2NF因为FIRSTl和FIRST2中的码分别为Sno和Sno,Pno每一个非主属性完全依赖于码。3NF(第三范式)定义若关系模式R(U，F)中不存在这样的码X，属性组Y及非主属性Z(ZY)使得XY，(YX)YZ成立，则关系模式R3NF。即当2NF消除了非主属性对

7、码的传递函数依赖，贝U成为3NF。例FIRSTl3NF，因为在分解后的关系模式FIRSTl中有：SnoStatus，StatusCity，存在着非主属性City传递依赖于码Sno。BCNF(巴克斯范式)；定义若关系模式R1NF，若XY且YX时，X必含有码，则关系模式RBCNF。即当3NF消除了主属性对码的部分和传递函数依赖，则成为BCNF。结论一个满足BCNF的关系模式，应有如下性质：所有非主属性对每一个码都是完全函数依赖；所有非主属性对每一个不包含它的码，也是完全函数依赖；没有任何属性完全函数依赖于非码的任何一组属性。(三)多值依赖1多值依赖定义若关系模式R(U)中，X、Y、Z是U的子集，并

8、且Z=UXY。当且仅当对R(U)的任何一个关系r,给定一对(x,z)值，有一组Y的值，这组值仅仅决定于x值而与z值无关，则称“Y多值依赖于X”或“X多值决定Y”成立。记为：XY。2多值依赖的性质多值依赖具有如下六条性质：多值依赖具有对称性。即若XY，则XZ，其中Z=UXY多值依赖的传递性。即若XY，YZ，则XZY函数依赖可以看成是多值依赖的特殊情况若XY，XZ，则XYZ若XY，XZ，贝，XYZ；若XY，XZ，则XZY。34NF(第四范式)定义(4NF)若关系模式R1NF，若对于R的每个非平凡多值依赖XY且Yx时，X必含有码，则关系模式R(U，F)4NF。(四)函数依赖的公理系统Armstron

9、g公理系统：设关系模式R(U，F)，其中U为属性集，F是U上的一组函数依赖，那么有如下推理规则：A1自反律：若YXU，则XY为F所蕴涵；A2增广律：若XY为F所蕴涵，且ZU，则XZYZ为F所蕴涵；A3传递律：若XY，YZ为F所蕴涵，则XZ为F所蕴涵。根据上述三条推理规则又可推出下述三条推理规则：合并规则：若XY,XZ,则XYZ为F所蕴涵伪传递率：若XY,WYZ，则XWZ为F所蕴涵分解规则：若XY，ZY，则XZ为F所蕴涵。引理：XA：A1A2A1成立的充分必要的条件是XAi成立(I=1,2,3,k)(五)函数依赖的闭包F+及属性的闭包X+：1函数依赖的闭包定义关系模式R(U,F)中为F所逻辑蕴含

10、的函数依赖的全体称为F的闭包,记为：F+。2属性的闭包X+定义设F为属性集U上的一组函数依赖，XU,X+=AIXA能由F根据Armstrong公理导出,则称X+为属性集X关于数依赖集F的闭包。3.求属性X的闭包X吉的算法X+算法求属性的闭包X+输入X,F输出X+F步骤令X(0)=X,i=0求B,B=A1(啟)(w)(VWFVX(DAW)X(i+D=BX(i)判断X(i+1)=X(i)吗若相等，或X(D=U,则X(D为属性集X关于函数依赖集F的闭包。且算法终止若不相等，则i=i+1,返回第二步例1已知关系模式R(U,F),U=A,B,C,D,E)；F=AB,DC,BCE,ACB求(AE)F+(A

11、D)F+解求(AE)+，由上述算法，设X(o)=AE计算X(1):逐一扫描F中的各个函数依赖,找到左部为A、E或AE的函数依赖，得到一个：AB。故有X=AEB。计算X：逐一扫描F中的各个函数依赖，找到左部为ABE或ABE子集的函数依赖，因为找不到这样的函数依赖，所以，X=XQ。算法终止，(AE)+=ABE。求(AD)；,由上述算法，设XtO=AD计算X”：逐一扫描F中的各个函数依赖，找到左部为A、D或AD的函数依赖，得到两个：A+B,D-C函数依赖。故有XCl：ADUBC。计算Xn：逐一扫描F中的各个函数依赖，找到左部为ADBC或ADBC子集的函数依赖，得到两个：BCE,ACB函数依赖。故有X

12、2：ABCDUE。所以，X(2ABCDE：U,算法终止，(AD)吉：ABCDE。(六)最小函数依赖集1等价和覆盖定义一个关系模式R(U,F)上的两个依赖集F和G,如果F=G,则称F和G是等价的，记做F三G。若F三G,则称G是F的一个覆盖，反之亦然。两个等价的函数依赖集在表达能力上是完全相同的。2最小函数依赖集定义如果函数依赖集F满足下列条件，则称F为最小函数依赖集或最小覆盖。；(1)F中的任何一个函数依赖的右部仅含有一个属性；”(2)F中不存在这样一个函数依赖XA,使得F与F一XA等价；扩(3)F中不存在这样一个函数依赖XA,X有真子集Z使得F一XAUZ+A与F等价。；3计算最小函数依赖集的算

13、法。算法计算最小函数依赖集。输入一个函数依赖集输出F的一个等价的最小函数依赖集G。步骤用分解的规则，使F中的任何一个函数依赖的右部仅含有一个属性；，：(2)去掉多余的函数依赖：从第一个函数依赖X+Y开始将其从F中去掉，然在剩下的函数依赖中求X的闭包X看X是否包含Y,若是，则去掉XY；否则不能去掉，依次做下去。直到拽不到冗余的函数依赖；(3)去掉各依赖左部多余的属性。一个一个地检查函数依赖宏部非单个属性的依赖。例如XY+A，若要判Y为多余的，则以醑+A代替XY+A是否等价?若AE(X),则Y是多余属性，可以去掉。例2已知关系模式R(U，F)，U=A,B，C，D，E，G；江F=AB+C,DEG，C

14、A，BE+C扩BCD，CGBD，ACD-B，CEAG；请将F化为最小函数依赖集。解此题可以有两种求解方法，求解过程如下：辈方法1(利用算法求解，使得其满足三个条件)；(1)利用分解规则，将所有的函数依赖变成右边都是单个属：性的函数依赖，得F为：F=ABC,D+E，D+G，CA，BECBCD，CGB，CGD，ACDB，CE+A，CEG去掉F中多余的函数依赖，具体做法如下：从第一个函数依赖开始从F中去掉它(假定它为XY)，剩下的函数依赖F求X的闭包，看X是否含Y，若包含Y，则X+Y为冗余函数依赖，则去掉它，否则不去。依次下去，直到能满足定义最小依赖的第二个条件。故有：设ABC为冗余的函数依赖，则去

15、掉AB+C得F1=D+E，DG，C+A，BECBC+D，CGB，CGD，ACD+B，CEA，CE+G因为从Fl中找不到找到左部为AB或AB子集的函数依赖，则(AB)击=。所以AB+C非冗余的函数依赖，不能去掉。设CGB为冗余的函数依赖，则去掉CGB得F2=AB+C，DE，D+G，C+A，BECBC+D，CG+D，ACD+B，CEA，CE+G求（CG）左设X*）：CG计算X”逐一扫描F2中的各个函数依赖，找到左部为C、（；或CG的函数依赖，得到一个：CA函数依赖。故有X“=CGA。计算X“：逐一扫描F2中的各个函数依赖，找到左部为CGA或CGA子集的函数依赖，得到一个：CG+D函数依赖。故有X9

16、=ACDG。:计算X“：逐一扫描F2中的各个函数依赖，找到左部为AC拓或ACDG子集的函数依赖，得到两个：ACDB，D，E函数依瓤故有XCa）2ABCDEG。；：扭因为X=ABCDEG：U,算法终止，（CG）占=ABCDE。所以CGB为冗余的函数依赖，从F2中去掉。：设CG+D为冗余的函数依赖，则去掉CGD得：捍F3=AB+C,D-*E,D+G，C-,-A,BECBC+D，ACD-B，CEA，CE+G：求（CG）占；：设XCO）：CG：计算Xm：逐一扫描F3中的各个函数依赖，找到左部为C、G城CG的函数依赖，得到一个：C+A函数依赖。故有Xu：ACG；熟计算X”：逐一扫描F3中的各个函数依赖，

17、找到左部为ACG诚ACG子集的函数依赖，周为找不到这样的函数依赖。故有谨=X”，算法终止。（CG）占=ACG。：因为ACG芒D，所以CG+D非冗余的函数依赖，不能从F3冲去掉。；设CE+A为冗余的函数依赖，则去掉CEA得瞰F4=AB-*C,D-E，D-*G，C+A，BEC：BC-*-D，CGD,ACD-B,CE+G）：求（CZ）击；设X（OCE芝计算X-）：逐一扫描F4中的各个函数依赖，找到左部为C、E藏CE的函数依赖，得到一个：CA函数依赖。故有：X（1，=5ACE；计算XC2）：逐一扫描F4中的各个函数依赖，找到左部为ACE:藏ACE子集的函数依赖，得到一个：CEG函数依赖；故有：骚X2）

18、=ACEG。计算X”逐一扫描F4中的各个函数依赖，找到左部为ACEG或ACEG子集的函数依赖，得到一个：CGD函数依赖。故有：X，=ACDEG。计算X“：逐一扫描F4中的各个函数依赖，找到左部为ACDEG或ACDEG子集的函数依赖，得到一个：ACDB函数依赖。故有：X=ABCDEG。因为X“=ABCDEG=U，算法终止，（CE）占：ABCDEG。所以CE+A为冗余的函数依赖，从F4中去掉。又因为F4中无多余函数依赖所以转（3）。去掉F4中各函数依赖左边多余的属性。函数依赖ACD+B，属性A是多余的，去掉A得CDB，因为CA,所以可推导出ACDB。故最小函数依赖集为：FMIN=AB+C,DE，D

19、+G，CA，BECBC+D，CGD，CD+B，CEG方法2（利用Armstrong公理系统的推理规则求解）假设CGB为冗余的函数依赖，那么，从F中去掉它后能根据Armstrong公理系统的推理规则导出。因为CG+DCA（已知）所以CGAACD（增广律）因为ACDB（已知）所以CGAB（传递律）因为CA（已知）所以CGB（蕴涵）同理可证：CEA是冗余的。又因CA，CDB可知，ACD-BL故去掉左边多余的属性得CD-B。需要注意的是，F的最小依赖集FMIN不一定是惟一的，它与对各函数依赖FDi及XA中X各属性的处理顺序有关。例3已知关系模式R（U，F），U=A，B，C；F=A+B，BA，B+C，A

20、+C，CA求最小函数依赖集。分析此题可以有两种不同的答案，下面分别叙述如下。答案1设B一A是冗余的，将其从F中去掉，看能否根据，Armstrong公理系统的推理规则导出。因B-C,CA（已知）故BA（传递律）故B-,-A是冗余的，将其从F中去掉，得n为F1：A+B，B-C，A+C，C+A。又设AC为冗余，将其从F1中去掉因AB，B-C（已知）故AC（传递律）故A+C是冗余的，将其从n中去掉，得Fm为：FM,=AB,B+C，G+A。因为在FM,中的其它函数依赖是非冗余的，所以，FMl为最小函数依赖集。答案2设B一C是冗余的，将其从F中去掉，看能否根据Armstrong公理系统的推理规则导出。：因

21、BA，A+C（已知）故BC（传递律）故B+C是冗余的，将其从F中去掉，得FM2为FM2=AB，B+C，AC，CA。i因为在Fm中的其它函数依赖是非冗余的，所以，FM2为最小函数依赖集。从上分析我们可以得到两个最小函数依赖集Fh4,和Fht。因此，F的最小函数依赖集不是惟一的。（七）模式分解1分解定义（分解）关系模式R（U,F）的一个分解是指，PR1（Ul,P1）,R2（U2,F2）,R。（U。F。）,其中：nU=UU，并且没有U（U,1Wi,jWn,E是F在U上的投影。其中Fi=XYXYEF八XY三Ui对一个给定的模式进行分解，使得分解后的模式是否与原来的模式等价有三种情况：分解具有无损连接性

22、；分解要保持函数依赖；分解既要无损连接性；又要保持函数依赖。2无损连接定义(无损连接)PR,(U1,F：),R：(U：,F2),Rh(Uk,Fk)是关系模式R(U,F)的一个分解，若对R(U,F)的任何一个关系r均有r=mP(r)成立，则成分解P具有无损连接性(简称无损分解)。k其中，mP(r)：冈丌R：(r)。定理关系模式R(U,F)的一个分解，PR1(U：,F1),R：(U2，F：)具有无损连接的充分必要的条件是：U1门U2一UlU2EF或Ul门U2+U2一UlEF3保持函数依赖定义：设关系模式R(U,F)的一个分解，P=民(U：,F1),R：咖2,F2)，Rk(Uk,Pk)，如果：F=(

23、U丌Ki(F1-),则称分解P保持函数依赖。十4.判别一个分解的无损连4匸1和保持函数依赖的算法；算法1判别一个分解的无损连接性。广pRl(U：,F1),R。(U2,F：)，凡(UL,Fb)是关系模式R：(U,F)的一个分解,U：A1,A：,A。,F=FD1,FD2,:FDp,并设F是一个最小依赖集，记FDi为戈一Au,其步骤如下：(1)建立一张n列k行的表，每一列对应一个属性，每一行对：应分解中的一个关系模式。若属性八仨U,则在j列i行上填上钙，否则填上、b_芝(2)对于每一个FDi做如下操作：找到Xi所对应的列中具有：；相同符号的那些行。考察这些行中1i列的元素，若其中有，则全；都改为，否

24、则全部改为bmli,m是这些行的行号最小值。i,如果在某次更改后，有一行成为：a1,a2,，an,则算法终止。：且分解p具有无损连接性，否则不具有无损连接性。:，对F中p个FD逐一进行一次这样的处理，称为对F的一次；扫描。：；：(3)比较扫描前后，表有无变化，如有变化，则返回第(2)步，：否则算法终止。三斗如果发生循环，那么前次扫描至少应使该表减少一个符号,表：中符号有限,因此,循环必然终止。算法2转换成3NF的保持函数依赖的分解。孓p=R1(U：,F1),R,(U：,F：),，Rk(Uk,Fk)是关系模式R：囊U,F)的一个分解，U：A：,A：,，An,F=FD1,FD2,FD,，并设F是一

25、个最小依赖集，记FDi为咒一，其步骤如下：；(1)对R(U,F)的函数依赖集F进行极小化处理(处理后的：结果仍记为F)；i(2)找出不在F中出现的属性，将这样的属性构成一个关系模式。把这些属性从U中去掉，剩余的属性仍记为U；若有XA正F,且XA=U,则PR，算法终止；否则，对F按具有相同左部的原则分组(假定分为k组)，每一组函数依赖Fi所涉及的全部属性形成一个属性集U。若U三U(ire就去掉U。由于经过了步骤(2),故UU9,于是PR,(Ul,F1),R2(U2,F2),Rk(Uk,Fk)构成R(U,F)的一个保持函数依赖的分解。并且，每个Ri(Ui,E)均属于3NF且保持函数依赖。例4关系模

26、式R(U,F),其中U=C,T,H,I,S,G),F=CSG,C+T,THI,HIC,HS1,将其分解成3NF并保持函数依赖。解根据算法2求解如下：F已为最小函数依赖集；R中的所有属性均在F中都出现，所以转(3)；对F按具有相同左部的原则分为：R1=CSG,R2；CT,R3：THI,R4：HIC,R5：HSR。所以PR1(CSG),R2(CT),R3(THl),R4(HIC),R5(HSR)算法3将一个关系模式转换成3NF,使它既具有无损连接又保持函数依赖的分解。输入关系模式R和R的最小函数依赖集F。输出R(U,F)的一个分解P=R1(U,F1),R：(U：,F：),，Rk(Uk,Fk),民为

27、3NF,且P具有无损连接又保持函数依赖的分解。操作步骤如下：(1)根据算法2求出保持依赖的分解P=R1,R。，R。ii(2)判分解P是否具有无损连接性，若有，转(4)；惑;、(3)令ppUX),其中X是R的候选关键字；牡.矢口(4)输出P孙。例5对例4的关系模式R(U,F)将其分解成3NF,使P具有嘎损连接又保持函数依赖的分解。弘，解根据算法3求解如下：扒(1)据例4得3NF保持函数依赖的分解如下：杠。二RI(CSG),R2(CT),R3(TH1),R4(HIC),R5(HSR)(2)根据算法1构造一个二维矩阵如图52所示。;:根据F中的C一T,对上表进行处理，由于属性列C上第一；行、第二行及

28、第四行相同a,所以将属性列T上b12、b2改为同一：符号a：又根据HIC将属性列C上b“、bsl改为同一符号a1修改后如图53所示。根据F中的CSG，对上表进行处理，由于属性列CS上第一行、第五行相同al、a5,所以将属性列G上b,。改为同一符号a6。又根据CT将属性列T上b。：改为同一符号a2,修改后如图54所示。从上可见，找到一行(第5行)为全a,所以分解是无损的。算法4将关系模式转换成BCNF，使它具有无损连接的分解。输入关系模式R和函数依赖集F。输出R(U,F)的一个分解PR,(U,F1),R。(U2,F：),Rk(Uk,Fk),民为BCNF,且P具有无损连接的分解。操作步骤如下：令P

29、=R若P中的所有模式都是BCNF,则转(4)；若P中有一个关系模式民不是BCNF，则民中必能找到一个函数依赖XA,且X不是民的候选键，且A不属于X,设Rn(XA),Ri2(民一A),用分解民，Rn代替民，转(2)；输出F；例6关系模式R(U,F)其中：U：C,T,H,I,S,G,F二CSC,CT,THI,HI+C,HS1,将其无损连接地分解成BCNF。解R上只有一个候选关键字HS(1)令PR(U,F)l：(2)p中不是所有的模式都是BCNF,转(3)；R扭；(3)考虑CSG,这个函数依赖不满足BCNF条件(CS不包蒙禽候选键HS)，所以将其分解成Ri(CSG)、R2(CTHIS)。计算法1和R

30、2的最小函数依赖集分别为：Fl=CSG,F2=C黔T,THI,HIC,HS1。R2的候选关键字为HS。默因R1已是BCNF,而R2的F2中存在不为码的决定因睽素HIC驻故R2不属于BCNF，进一步分解R2即可。爱:.分解R2：考虑CT,将其分解成R21(CT)、R22(CHIS)。计6薯R21和R22的最小函数依赖集分别为：F21=CT,F22=：CH+I,HI+C,HS+I,.CT,TH一1,.在F22中，有CH一心。R22的候选关键字为HS。整因R21已是BCNF,R22不是BCNF熙故进一步分解R22即可。默分解R22：考虑CH一1,将其分解成R221(CH1)、R222扭CHS)。计算

31、R221和R222的最小函数依赖集分别为：盼酝F221=CHI,HIC鞯R：F222：HS+C。ir戴因R221,R222已是BCNF磬故将R分解后为：芝p=R1(CSG),R21(CT),R221(CHl),R222(CHS)醛算法5将关系模式分解成4NF,使它具有无损连接性。酝输入关系模式R和函数依赖集F。黔输出R(U,F)的一个分解P=Rl(U,F1),R2(U：,F2),F?”，Rk(U,Fk)，民为4NF,且P具有无损连接的分解。卧操作步骤如下：芝(1)令P=R若P中的所有模式都是4NF,贝峙专(4)；若P中有一个关系模式民不是4NF,则Ri中必能找到一个函数依赖X一一A,且X不包含

32、民的候选键，且AX乒中，XA；i民令Z=AX,由分解规则得出XZ。令R。(XZ),Ri2(民一Z),用分解vRil,Ri2代替民，由于(R,门Ri2)一一(R,一Ri。)，所以分解具有无损连接性。转；停止分解，输出p二、典型题解析例51对给定的关系模式R(U,F),U=A,B,C,F=vAB),如下的两个分解：(1)F1=AB,BCp：=AB,AC判这两个分解是否无损。解(1)根据定理判断本题因AB门BC=BABBC=ABCAB=C故BA茫FB+C争F故P,为有损连接。根据定理判断本题因AB门AC二AABAC=BACAB=C故AB正FB+CF芝故p：为无损连接。豁例52对给定的关系模式R(U,

33、F),U=A,B,C,D,E,F山AC,BC,CD,DEC,CEA,如下的分解：:p=R：(AD),R2(AB),R：(BE),R：(CDE),Rs(AE)捌分解P是否无损。豪解(1)构造一个初始的二维表如图55所示。拦臻(2)根据A+C,对上表进行处理，由于属性列A上第一行、汝二行及第三行相同a,所以将属性列C上b,、b：,、b53改为同一瓢细号b13,取行号最小值。又根据BC将属性列C上b_、b北改为粗阑一符号b13，修改后的表如图56所示。牡(3)根据C+D,对上表进行处理，由于属性列C上第一行第野仁行、第三行及第五行相同b,且属性列D上第一行为a,所以将R洄性列D上b：,、b,：、b：

34、,改为同一符号a：,修改后的表如图57渤示。苣团O根据DE+C,将属性列C上第三行及第五行改为同一符号a,，修改后的表如图58所示。田OO根据CE+A，将属性列A上第三行及第四行改为同一符号al,修改后的表如图59所示。通过上述更改，使第三行成为：a1,a：:a,:a4,a。，则算法终止。且分解P具有无损连接性。例53对给定的关系模式R(U:F):U=A:B:C:D:E:尸通过上述更改使第三行成为：a1a：aa4a。则算法终止。且分解P具有无损连接性。例53对给定的关系模式R(U:F):U=A:B:C:D:E:尸轧F；AB,CP,EA,CED,如下的分解：感pR1(ABE),R2(CDEP)甄

35、。(1)求R的候选关键字，并判分解p是否无损；扫；(2)R1、R：属于几范式。瓤解(1)候选关键字为CE筻因(CE)=U6；十故有CE+U，并且在CE中不存在一个真子集能决定R抽全体属性U,故CE为R的候选关键字。萨：根据定理判断本题分解P是否无损举因ABE门CDEP=E2：；蔑“ABECDEP=AB醛磬CDEPABE：CDP良因E+A,A+B(已知)莨故有E+B(传递律)寥“因E+A,EB豪故有E+AB(合并律)封：因E+ABEF卧：故故P为无损连接。甄.(2)R1、R：属于几范式?踩：R1E2NF骚；因EA,A+B良故EB,存在传递依赖野故R1任3NF萨R：仨1NF皂因CE+D,C+P瑟故

36、CE能惟一地确定R：中的每一个元组，故为候选关漠字。醛因CE是候选关键字，而CP,所以P部分函数依赖良与CE故R2手2NF例54对给定的关系模式R(U,F),U=A,B,C,D,E,P,F=AB,CP,EA,CE+D，如下的分解：p=R1(CP),R：(BE),R3(ECD),R：(AB)，判分解P是否无损。解(1)构造一个初始的二维表如图510所示。根据AB,对上表进行处理，由于属性列A上无相同元素，所以不能修改表。又根据CP将属性列P上b：,改为a,修改后的表如图511所示。根据E一A,对上表进行处理，由于属性列E上第二行、第三行相同a5,所以将属性列A上b：,、L改为同一符号b：,修改后

37、的表如图512所示。；(4)根据CED，对上表进行处理，无法修改上表。因此，在辗后的表格，找不到一行全为al,a：,，an,所以P是有损的。：例5一5试证明由Armstrong公理系统推导出下面三条推理规则是正确的：l(1)合并规则：若XZXY则有XYZ伪传递规则：若XY,WYZ,则有XWZ分解规则：若XY,Z任Y,则有X一2三证明一.(1)合并规则:因XY(已知)器故XXY(增广律)因XZ(已知)故XYYZ（增广律）：因XXY，XYYZ（从上面得故XYZ（传递律）（2）伪传递规则：，因X+Y（已知）故WXWY（增广律）因WYZ（已知）故XW一2（传递律）因Z(Y（已知）故YZ（自反律）因XY

38、（已知）故XZ（传递律）（3）分解规则：例3-6关系R(A,B,C,D,E,F,G,H,I,J)满足下列函数依赖:ABD+E，ABG，BF，C一工，CJI，G+H该函数依赖集是最小函数依赖集吗?给出该关系的候选码。解该函数依赖集不是最小函数依赖集。因CJ,CJI（已知）故CJ（逻辑蕴涵）显然，ABCDGJ是一个超码，即所有出现在函数依赖左边的属性的集合是超码。但是因CJ（已知）故可将J从超码中去掉。因ABG（已知）故可将G从超码中去掉。此时，超码中只剩下ABCD,由于它们都没有在函数依赖集的任何一个函数依赖的右边出现，所以它们都不能从超码中去掉。故候选码为：ABCD。所谓超码是指能惟一标识关系

39、中的每一个元组,不含多余属性的才是候选关键字（或候选码）。例37设P=R1（U1,F1）,R2（U2,F2）是R（U,F）上的一个分解，试证明P具有无损连接的充分必要的条件是：U1门U：UlU2仨F或U1门UzU2一Ul仨F。证明充分性：设U、门Uz-U：一U：,则可构造表如图513所示。该图省略了a、b的下标。如果U,门U2+U,U2在F中，则可将表的第二行U，一U：瀚韵所有符号全改为aaaa，使得该表的第二行全为a，则P具有海损连接性。同理可证U、门U：+U:一U：的情况。如果U1门U2知：一U：不在F中，但在F中，那么，它可以从Armstrong公理纂统的推理规则导出，从而也能推出U1门U2一九，且Ai三U1一巍中，所以可以将九列的b改为a，同样，可将UlU2的其它属醛对应的第二行也全改为a，这样，第二行就变成全a，所以分解是凛有无损连接性。卧(2)