关系系统及查询优化与范式定理

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

2、元组在X上的属性值相等，而在Y上的属性值不等，则称X函数决定Y或Y函数依赖于X,记作：XYof(1)完全函数依赖：在R(U)中，如果XY,并且对于X的任何一个真子集X',都有X'不能决定Y,则称Y对X完全函数依赖，记作：XY例给定一个学生选课关系SC(Sno,Cno,G),我们可以得到F=(Sno,Cno)G,又t(Sno,Cno)中的任何一个真子集Sno或Cno都不能决定G,所以，G完全依赖于Sno,Cno。P(2)平凡的函数依赖：如果XY,1Y不完全函数依赖于X,则称Y对X部分函数依赖，记作：XY(3)传递依束在R(U)中，如果XY,(YX),YX,Y则称Z对X传递依赖(4

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

4、范式的关系模式的集合，这种过程叫做规范化。下面将给出各个范式的定义。1. 1NF(第一范式)定义若关系模式R的每一个分量是不可再分的数据项，则关系模式R属于第一范式(1NF)o例供应者和它所提供的零件信息，关系模式如下：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东方红3

5、0北京P1300S3东方红30北京P2280S4泰达20上海P2460从图51中可以看出，每一个分量都是不可再分的数据项，所以是1NF。但是，1NF带来四个问题：(1)冗余度大：例如每个供应者的Sno,Sname,Status,City要与零件的种类一样多；(2)引起修改操作的不一致性：例如供应者S1从“天津”搬到“上海”，若稍不注意，就会使一些数据被修改，另一些数据没有被修改，导致数据修改的不一致性；(3)插入异常：若某个供应者的其它信息未提供时，如“零件号”，则不能进行插入操作；(4)更新异常：若供应商S4的P2零件销售完了，删除后，在基本关系FIRST找不到S4,可S4又是客观存在的。正

6、因为上述原因引入了2NF。2. 2NF(第二范式)定义若关系模式R1NF,且每一个非主属性完全依赖于码，则关系模式R2NF。即当1NF消除了非主属性对码的部分函数依赖，则成为2NF例 FIRST关系中的码是 Sno、Pno,而Sno Status因此非主属性 Status部分函数依赖于码，故非2NF的。若此时，将FIRST关系分解为:FIRSTl(Sno,Sname,Status,City)2NFFIRST2(Sno,Pno,Qty)2NF因为FIRSTl和FIRST2中的码分别为Sno和Sno,Pno每一个非主属性完全依赖于码。3. 3NF(第三范式)定义若关系1K式R(U,F)中不存在这样

7、的码X,属性组Y及非主属性Z(ZY)使得XY,(YX)Y/Z成立，则关系模式R3NF。即当2NF消除了非主属性对码的传递函数依赖，则成为3NF。例FIRSTl3NF,因为在分解后的关系模式FIRSTl中有：SnoStatus,StatusCity,存在着非主属性City传递依束于码Sno。4.BCNF(巴克斯范式)；定义若关系模式R1NF,若XY且YX时，*必含有码，则关系模式RBCNF。即当3NF消除了主属性对码的部分和传递函数依赖，则成为BCNFo结论一个满足BCNF的关系模式，应有如下性质:(1)所有非主属性对每一个码都是完全函数依赖；(2)所有非主属性对每一个不包含它的码，也是完全函数

8、依赖;(3)没有任何属性完全函数依赖于非码的任何一组属性。(三)多值依赖1 .多值依赖定义若关系模式R(U)中，X、Y、Z是U的子集，并且Z=UX丫。当且仅当对R(U)的任何一个关系r,给定一对(x,z)值，有一组Y的值，这组值仅仅决定于x值而与z值无关,则称“Y多值依赖于X”或“X多值决定Y”成立。记为：X丫。2 .多值依赖的性质多值依赖具有如下六条性质：(1)多值依赖具有对称性。即若XY,则XZ,其中Z=UXY(2)多值依赖的传递性。即若XY,YZ,则XZY(3)函数依赖可以看成是多值依赖的特殊情况(4)若XY,XZ,则XYZ(5)若XY,XZ,贝，XYZ；(6)若XY,XZ,则XZY。3

9、 .4NF(第四范式)定义(4NF)若关系模式R1NF,若对于R的每个非平凡多值依赖XY且YX时，X必含有出,则关系模式R(U,F)4NF。(四)函数依赖的公理系统Armstrong公理系统：设关系模式R(U,F),其中U为属性集，F是U上的一组函数依赖，那么有如下推理规则：(1)A1自反律：若丫XU,则X丫为F所蕴涵；(2)A2增广律：若X丫为F所蕴涵，且ZU,则XZYZ为F所蕴涵；(3)A3传递律：若XY,YZ为F所蕴涵，则XZ为F所蕴涵。根据上述三条推理规则又可推出下述三条推理规则:合并规则：若XY,XZ,则XYZ为F所蕴涵(2)伪传递率：若XY, WY Z,则XW Z为F所蕴涵(3)分

10、解规则：若XY, Z Y,则X Z为F所蕴涵。引理：X A: A1A2A1成立的充分必要的条件是XAi成立(I=1,2,3,k)(五) 函数依赖的闭包F+及属性的闭包X +:1 函数依赖的闭包定义 关系模式 R(U ， F) 中为 F 所逻辑蕴含的函数依赖的全体称为F 的闭包，记为： F+属性的闭包X +F定义 设 F 为属性集 U 上的一组函数依赖， X U ，A | X X +FA 能由 F 根据 Armstrong公理导出 ，则称 为属性集 X 关于数依赖集 + F 的闭包。X +F求属性 X 的闭包 X 吉的算法X F算法求属性的闭包 X +F输入X ， F输出 X + F步骤(1)令

11、 X(0)=X, i=0(2)求 B, B = A |(v)( w)(V WF V X (i) A W)(3) X(i+1) = B X(i)(4) 判断X(i+1) = X(i) 吗(5)若相等，或X (i)=U ，则 X(i) 为属性集 X 关于函数依赖集F 的闭包。且算法终止(6)若不相等，则i=i+1,返回第二步例 1 已知关系模式 R(U , F), U = A, B, C, D, E);F = A B, D C, BC E, AC B求 (AE) + F (AD) + F解 求(AE)上述F法，设X(0)=AE计算 X (1) : 逐一扫描 F 中的各个函数依赖，找到左部为A 、

12、E 或 AE 的函数依赖，得到一个：A Bo 故有 X(1)=AE B计算X(2) ：逐一扫描F 中的各个函数依赖，找到左部为为找不到这样的函数依赖，所以， X(1)=X(2)O算法终止，(AE) + = ABE。求(AD);,由上述算法，设 XtO' = AD计算X ”：逐一扫描F 中的各个函数依赖，找到左部为个： A+B ， D-C 函数依赖。故有ABE 或 ABE 子集的函数依赖，因A 、 D 或 AD 的函数依赖，得到两XCl ： ADUBC计算 X n ：逐一扫描F 中的各个函数依赖，找到左部为ADBC 或 ADBC 子集的函数依赖，得到两个： BC E， AC B 函数依赖

13、。故有X2，： ABCDUE 。所以， X(2 ： ABCDE ： 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与FXA等价；扩(3)F中不存在这样一个函数依赖X一A,X有真子集Z使得FX

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

15、系模式R(U,F),U=A,B,C,D,E,G;江F=AB+C,DEG,CA，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(2)去掉F中多余的函数依赖，具体做法如下：从第一个函数依赖开始从F中去掉它(假定它为XY),剩下的函数依赖F'求X'的闭包，看X'是否含Y,若包含Y,则X+Y为冗余

16、函数依赖，则去掉它，否则不去。依次下去，直到能满足定义最小依赖的第二个条件。故有：设ABC为冗余的函数依赖，则去掉AB+C得F1=D+E,DG,C+A,BECBC+D，CGB，CGD，ACD+B，CEA，CE+G因为从Fl中找不到找到左部为AB或AB子集的函数依赖，则依8)击=。所以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

17、“：逐一扫描F2中的各个函数依赖，找到左部为CGA或CGA子集的函数依赖，得到一个：CG+D函数依赖。故有X'9'=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)占；设

18、XCO):CG:计算Xm:逐一扫描F3中的各个函函依赖，找到左部为C、G城CG的函函依赖，得到一个：C+A函函依赖。故有Xu：；ACG。熟计算X”：逐一扫描F3中的各个函函依赖，找到左部为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(O':CE芝计算X-):逐一扫描F4中的各个

19、函函依赖，找到左部为C、E藏CE的函函依赖，得到一个：CA函函依赖。故有：X(1'=5ACE。计算XC2):逐一扫描F4中的各个函数依赖，找到左部为ACE；藏ACE子集的函函依赖，得到一个：CEG函函依赖。故有：骚X'2)=ACEG。计算X”：逐一扫描F4中的各个函函依赖，找到左部为ACEG或ACEG子集的函函依赖，得到一个：CGD函函依赖。故有：X'''=ACDEG。计算X“：逐一扫描F4中的各个函函依赖，找到左部为ACDEG或ACDEG子集的函函依赖，得到一个：ACDB函函依赖。故有：X'''=ABCDEG。因为X=ABCDE

20、G=U,算法终止，（CE）占：ABCDEG。所以CE+A为冗余的函数依赖，从F4中去掉。又因为F4中无多余函数依赖所以转（3）。（3）去掉F4中各函数依赖左边多余的属性。函数依赖ACD+B,属性A是多余的，去掉A得CDB,因为CA，所以可推导出ACDB。故最小函数依赖集为：FMIN=AB+C,DE,D+G,CA,BECBC+D，CGD，CD+B，CEG方法2（利用Armstrong公理系统的推理规则求解）假设CGB为冗余的函数依赖，那么，从F中去掉它后能根据Armstrong公理系统的推理规则导出。因为CG+DCA（已知）所以CGAACD（增广律）因为ACDB（已知）所以CGAB（传递律）因为

21、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+C,CA求最小函数依赖集。分析此题可以有两种不同的答案，下面分别叙述如下。答案1设BA是冗余的，将其从F中去掉，看能否根据，Armstrong公理系统的推理规则导出。因B-C，CA（已知）故BA（传递律）故B-,-A是冗余的，将其从F中去掉，得n为F1：A+B，B-C，A+C，C+A。又设AC为

22、冗余，将其从F1中去掉因AB,B-C(已知)故AC(传递律)故A+C是冗余的，将其从n中去掉，得Fm为：FM,=AB,B+C,G+A。因为在FM，中的其它函数依赖是非冗余的，所以，FMl为最小函数依赖集。答案2设BC是冗余的，将其从F中去掉，看能否根据、Armstrong公理系统的推理规则导出。：因BA，A+C(已知)故BC(传递律)故B+C是冗余的，将其从F中去掉，得FM2为FM2=AB,B+C,AC,CAo：i因为在Fm中的其它函数依赖是非冗余的，所以，FM2为最小函数依赖集。从上分析我们可以得到两个最小函数依赖集Fh4，和Fht。，因此，F的最小函数依赖集不是惟一的。(七)模式分解1分解

23、定义(分解)关系模式R(U，F)的一个分解是指，PRl(Ul,P1),R2(U2,F2),Ro(U。，F。),其中：nU=UU,并且没有U(U,1<i,j<n,E是F在U上的投影。其中Fi=XYXYEF'八XY三Ui对一个给定的模式进行分解，使得分解后的模式是否与原来的模式等价有三种情况：(1)分解具有无损连接性；(2)分解要保持函数依赖；(3)分解既要无损连接性；又要保持函数依赖。2无损连接定义(无损连接)P'R,(U1,F:),R:(U:,F2),Rh(Uk,Fk)是关系模式R(U,F)的一个分解，若又tR(U,F)的任何一个关系r均有r=mP(r)成立，则成分

24、解P具有无损连接性(简称无损分解)其中，mP(r):冈开R:(r)。定理关系模式R(U,F)的一个分解，P'R1(U：,F1),R：(U2，F：)具有无损连接的充分必要的条件是：Ul门U2一UlU2EF或Ul门U2+U2一UlEF3保持函数依赖定义：设关系模式R(U,F)的一个分解，P=民(U:,F1),R:咖2,F2)，Rk(Uk,Pk),如果：F'=(UJTKi(F1-)',则称分解P保持函数依赖。十4.判别一个分解的无损连4i-'1和保持函数依赖的算法；算法1判别一个分解的无损连接性。广p'Rl(U:,F1),Ro(U2,F:),凡(UL,Fb)是

25、关系模式R:(U,F)的一个分解，U:A1,A:,，Ao,F=FDl,FD2,：FDp,并设F是一个最小依赖集，记FDi为戈一Au,其步骤如下：(1)建立一张n列k行的表，每一列对应一个属性，每一行对：应分解中的一个关系模式。若属性八任U,则在j列i行上填上钙，否则填上、b.芝(2)对于每一个FDi做如下操作：找到Xi所对应的列中具有：；相同符号的那些行。考察这些行中1i列的元素，若其中有，则全；都改为，否则全部改为bmli,m是这些行的行号最小值。i,如果在某次更改后，有一行成为：a1,a2,，an,则算法终止。：且分解p具有无损连接性，否则不具有无损连接性。：，对F中p个FD逐一进行一次这

26、样的处理，称为对F的一次；扫描。：；：(3)比较扫描前后，表有无变化，如有变化，则返回第(2)步，：否则算法终止。一斗如果发生循环，那么前次扫描至少应使该表减少一个符号，表：中符号有限，因此，循环必然终止。：算法2转换成3NF的保持函数依赖的分解。工p=R1(U:,F1),R:(U:,F:),，Rk(Uk,Fk)是关系模式R:囊U,F)的一个分解，U:A:,A:,，An,F=FDl,FD2,'：FD,并设F是一个最小依赖集，记FDi为咒一，其步骤如下：；(1)对R(U，F)的函数依赖集F进行极小化处理(处理后的：结果仍记为F)；i(2)找出不在F中出现的属性，将这样的属性构成一个关系模

27、式。把这些属性从U中去掉，剩余的属性仍记为U；(3)若有XA正F,且XA=U,则P'R>,算法终止；(4) 否则，对F按具有相同左部的原则分组(假定分为k组)，每一组函数依赖Fi所涉及的全部属性形成一个属性集U。若U三U(ire就去掉Uo由于经过了步骤(2),故U U9 ，于是P R ， （Ul ， F1） ， R2（U2 ，F2),Rk(Uk,Fk)构成R(U，F)的一个保持函数依赖的分解。并且，每个Ri(Ui,E)均属于3NF且保持函数依赖。例4关系模式R(U,F),其中U=C,T,H,I,S,G),F=CSG，C+T，THI，HIC，HSI>，将其分解成3NF并保持函

28、数依赖。解根据算法2求解如下：(1)F已为最小函数依赖集；(2)R中的所有属性均在F中都出现，所以转(3)；(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),民为3NF,且P具有无损连接又保持函数依赖的分解。操作步骤如下：(1)根据算法2求出保持依赖的分

29、解P=R1,Ro,，Roii(2)判分解P是否具有无损连接性，若有，转(4)；惑；、(3)令ppUX)，其中X是R的候选关键字；牡.知输出P孙。例5对快J4的关系模式R(U,F)将其分解成3NF,使P具有嘎损连接又保持函数依赖的分解。弘，解根据算法3求解如下：扒(1)据例4得3NF保持函数依赖的分解如下：杠。二RI(CSG),R2(CT),R3(THl),R4(HIC),R5(HSR)(2)根据算法1构造一个二维矩阵如图52所示。；：根据F中的CT，对上表进行处理，由于属性列C上第一；行、第二行及第四行相同a,所以将属性列T上b12、b'2改为同一：符号a：。又根据HIC将属性列C上b

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

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

32、,F2=C一黔T,THI,HIC,HSI>oR2的候选关键字为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,TH1,.在F22中，有CH一心。R22的候选关键字为HS。整因R21已是BCNF，R22不是BCNF熙故进一步分解R22即可。默分解R22：考虑CH一1，将其分解成R221(CHl)、R222扭CHS)。计算R221和R

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

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

35、：为无损连接。豁例52对给定的关系模式R(U,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,且属T列D上第一行

36、为a,所以将R'涧性列D上b：,、b,：、b：,改为同一符号a：,修改后的表如图57渤示。苣团O(4)根据DE+C，将属性列C上第三行及第五行改为同一符号a，修改后的表如图58所示。田OO(5)根据CE+A，将属性列A上第三行及第四行改为同一符号al,修改后的表如图59所示。通过上述更改，使第三行成为：a1，a：，a，a4，a。，则算法终止。且分解P具有无损连接性。例53对给定的关系模式R(U,F),U=A,B,C,D,E,尸通过上述更改，使第三行成为：a1，a：，a，a4，a。，则算法终止。且分解P具有无损连接性。例53对给定的关系模式R(U,F),U=A,B,C,D,E,尸轧F;A

37、B,CP,EA，CED，如下的分解：感pR1(ABE)，R2(CDEP)甄。：(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:属于几范式？踩：R1E2N

38、F骚；因EA,A+B良故EB,存在传递依赖野故R1任3NF萨R:任1NF皂因CE+D,C+P瑟故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所示:（2）根据AB,对上表进行处理，由于属性列A上无相同元素，所以不能修改表。又根据C一P将属性列P上b:,改为a,修改后的表如图511所示。（3）根据E

39、A,对上表进行处理，由于属性列E上第二行、第三行相同a5,所以将属性列A上b:,、L改为同一符号b:,修改后的表如图512所示。；（4）根据CED，对上表进行处理，无法修改上表。因此，在辗后的表格，找不到一行全为al,a：,，an,所以P是有损的。：例55试证明由Armstrong公理系统推导出下面三条推理规则是正确的：l（1）合并规则：若XZ，XY，则有XYZ（2）伪传递规则：若XY,WYZ,则有XWZ（3）分解规则：若XY,Z任Y,则有X2+证明一.（1）合并规则：因XY（已知）器故XXY（增广律）因XZ（已知）故XYYZ（增广律）：因XXY，XYYZ（从上面得知）故XYZ（传递律）（2）

40、伪传递规则：，因X+Y（已知）故WXWY（增广律）因WYZ（已知）故XW2'（传递律）（3）分解规则：因Z（Y（已知）故YZ（自反律）因XY（已知）故XZ（传递律）例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，

41、由于它们都没有在函数依赖集的任何一个函数依赖的右边出现，所以它们都不能从超码中去掉。故候选码为：ABCD。所谓超码是指能惟一标识关系中的每一个元组，不含多余属性的才是候选关键字(或候选码)。例37设=131,F1),R2(U2,F2)是R(U,F)上的一个分解，试证明P具有无损连接的充分必要的条件是：U1门U:UlU2任F'或Ul门UzU2一Ul任F'。证明充分性：设U、门Uz-'U:一U:,则可构造表如图513所示。该图省略了a、b的下标。如果U，门U2+U，一U2在F中，则可将表的第二行U，一U：瀚韵所有符号全改为aaaa,使得该表的第二行全为a,则P具有海损连接性

42、。同理可证U、门U:+U:U:的情况。如果Ul门U2知：一U:不在F中，但在F'中，那么，它可以从Armstrong公理纂统的推理规则导出，从而也能推出Ul门U2一九，且Ai三U1一巍中，所以可以将九列的b改为a,同样，可将UlU2的其它属醛对应的第二行也全改为a,这样，第二行就变成全a,所以分解是凛有无损连接性。卧(2)必要性：设构造的表中有一行全为a,例如第一行全为a'湘由函数依赖的定义可知U:门U:U:Ul;如第二行全为a,则油函数依赖的定义可知U,门U2+UlU2o黔例58试证明由关系模式中全部属性组成的集合为候选拱键字的关系是3NF，同时也是BCNF。证明由于关系模式

43、中的全部属性组成的集合为候选关键障，该关系中没有非主属性，满足R属于3NF的条件，即每个非主幽性即不函数依赖候选关键字，也不传递依赖于候选关键字。醛又因为它没有非候选关键字的属性，也满足BCNF的三个降件：F(1)所有非主属性对每个候选关键字都完全函数依赖；苣(2)没有任何属性都完全函数依赖于非候选关键字的任一组61性；因为它只是一个候选关键字，所以又满足BCNF的另一个陋伍(3)所有的主属性对每一个不包含它的候选关键字也是完全函数依赖。例59试证明一个关系模式R是BCNF，那么它一定是3NF。证明采用反证法。设关系模式R是BCNF，不是3NF的，则必存在非主属性A和候选关键字X以及属性组Y，

44、使得：X，Y，Y+A，其中A+X，AY，Y+X不属于F，这就是说Y不可能包含R的候选关键字，但YA却成立。根据BCNF定义，R不是BCNF，与题设矛盾，所以一个BCNF必是3NF的。例510关系R(A,B,C,D,E)满足下列函数依赖：F=AC,CD,BC,DEC,CEA(1)给出关系R的候选关键字；(2)判P=AD,AB,BC,CDE,AE是否无损连接分解；(3)将R分解为BCNF，并具有无损连接性。解(1)从函数依赖集F中看，候选关键字至少包含BE,因为BE不依赖于谁，而(BE)'=ABCDE，所以，BE是R的候选关键字。(2)构造一个二维表，如图514所示。根据A+C，对上表进行

45、处理，由于属性列A上第1，2，5行相同，但属性列C上对应的1,2,5行上无ai元素，所以，只能将b13b:bs,改为行号最小值b130又根据CD将属性列D上b.改为a：,修改后的表如图515所示。臣blb扩根据BC，对上表进行处理，由于属性列B上第2，3行相湘，但属性列C上对应的3行为a：元素，所以，只能将第2行b13改妆口a3。又根据DEC,CEA不能修改此表所以修改后的表如卜,i声516所不。摹“。”：根据AC,对上表进行处理，由于属性列A上第1,2,5府相同，但属T列C上对应的1,2,5行上有a3元素，所以，只能将藻1,5行b13改为a3。又根据C+D将属性列D上b2'bs：改为

46、a4,:修改后的表如图517所示。根据CE+A，对上表进行处理，由于属性列CE上第4，5行相伺，但属性列A上对应的5行为al元素，所以，将第4行b41改为a,。修改后的表如图518所示。继续扫描F不能修改此表，由于找不到一行全为a,所以该分解是有损的。(3)考虑AC，因为AC不包含候选关键字，所以AC不是BCNF，故将ABCDE分解为两个子模式R1(AC)R2(ABDE)。此时，R1正BCNF。，继续分解R2，考虑BD，将ABDE分解为两个子模式R21(BD)R22(ABE)，此时，R21和R22均属于BCNF。所以R分解为BCNF，并具有无损连接性的分解如下：P=AC,BD,ABE三、习题一

47、、选择题L设学生关系模式为：学生(学号，姓名，年龄，性别，成绩，专业)，则该关系模式的主键是()。A姓名B学号，姓名C学号D学号，姓名年龄搬2设关系模式R（U，F），U为R的属性集合，F为U上的一种函数依甑，则对R（U，F）而言，如果XY为F所蕴涵，且Z巨U,则XZYZ为F所酶硒。这是函数依赖的（）。笋A.传递律U.合并规则巴自反律D.增广律瓢3.X一九成立是XA1A2Ah成立的（）。终久充分条件D.必要条件随C充要条件D.既不充分也不必要蓑4.设一关系模式为：运货路径（顾客姓名，顾客地址，商品名，供应商姓辐，供应商地址），则该关系模式的主键是（）。女儿顾客姓名，供应商姓名-幂BB顾客姓名，商

48、品名轧巴顾客姓名，商品名，供应商姓名乏D顾客姓名，顾客地址，商品名醛5设有关系模式R（U，F），U是R的属性集合，X，Y是U的子集，则多灌函数依赖的传递律为（）。萨A.如果X+Y,且YZ,则XZ小h:,萨B.如果X一+Y,Y+Z,则X+（ZY）粒豪C.如果X一+Y,则X一+（U丫一X）铲D.如果X+一Y,VOW,则WX一+VY严6.下列有关范式的叙述中正确的是（）。瓢A.如果关系模式RElNF，且R中主属性完全函数依赖于主键，则R遵2NF蜂B如果关系模式RE3NF，X,YOU，若X+Y,则R是BCNFC如果关系模式REBCNF，若X+Y（Y篡X）是平凡的多值依赖，簿斓R是4NF芝D.一个关系模

49、式如果属于4NF，则一定属于BCNF；反之不成立酾7.关系模式学生（学号，课程号，名次），若每一名学生每门课程有一定辆名次，每门课程每一名次只有一名学生，则以下叙述中错误的是（）。牲A.（学号，课程号）和（课程号，名次）都可以作为候选键驻D.只有（学号，课程号）能作为候选键弹巴关系模式属于第三范式D.关系模式属于BCNF8 .下列叙述中正确的是（）。A.若X+一Y，其中Z二UX+Y：中，则称X一一Y为非平凡的多疽依赖且若X，一Y，其中Z：UXY：中，则称X一一Y为平凡的多值依赖巴对于函数依赖A1,A2,，AnB来说，如果B是A中的某一个，则称为非平凡函数依赖D.对于函数依赖A1,A2,，AnB

50、来说，如果B是A中的某一个，则称为平凡函数依赖9 .能消除多值依赖引起的冗余的是（）。A.2NFa3NFC.4NFaBCNF10.下列叙述中正确的是（）。丸第三范式不能保持多值依赖D第四范式肯定能保持多值依赖CBC范式可能保持函数依赖D第四范式不能保持函数依赖11 下列关于第四范式的叙述中错误的是()。丸第四范式条件实质上是BC范式条件a第四范式应用与多值依赖C如果一个关系属于第四范式，则每个非平凡多值依赖实际上就是一个左边为超键码的函数依赖D属于BC范式的每个关系都属于第四范式12 以下叙述中正确的是()。久函数依赖XY的有效性仅决定于两属性集的值；而多值依赖X一一Y的有效性与属性集的范围有

51、关D函数依赖XY与多值依赖X+Y的有效性都决定于两属性集的值C多值依赖X一一Y若在R(U)上成立，则对任何Y三Y都有X一一Y成立D对于函数依赖XY在R上成立，不能断言对任何y'cY均有X隘r成立醛：13关系数据库设计理论中，起核心作用的是()。蘸A范式D模式设计巳数据依赖D数据完整性醛爵二、填空题跹酽1关系数据库是以为基础的数据库，利用细述现实世界。一个关系既可以描述，也可以描述攥l+扛2在关系数据库中，二维表称为一个表的每一行称为卜：二，表的每一列称为。芝3数据完整性约束分为和两类。黔4关系数据库设计理论，主要包括三个方面内容：、：二和。其中起着核心的作用。隘5X-,-Y是模式R的一

52、个函系依赖，在当前值，的两个不同元组中，如海X值相同，就一定要求。也就是说，对于x的每一个具体涕，都有与之对应。隘；6设F是关系模式R的一个函系依赖集，X，Y是R的属性子集，如果熬，则称F逻辑蕴涵XY，记为。被F逻辑蕴涵g麴函系依赖的全体构成的集合，称为，记作。§；：7设U是关系模式R的属性集，X，Y，Z是U的子集，则：FD的自反律泌；增广律是；传递律是。函系依阳推理规则系统(自反律、增广律和传递律)是一一的。芝8.关系模式R(U)上的两个函数依赖集 F 和予，如果满足酝，则称F和G是等价的。芝9每个函系依赖集F都可以被的函数依赖集G所覆盖。酿lo.将一个关系模式分解成多个关系模式时

53、，为了保持原模式所满足的豪特性要求分解处理具有和811.设R是一关系模式，分解成关系模式P'R1,R2,，Rk,P是R上的一个函数依赖集，如果对R中满足F的每一个关系，都有胆以以以以以以，N，j称该分解P相ZF&“xN969”。臣12 .如果R的分解为P=Rl,R2,F为R所满足的函数依赖集合，分解P具有无损联接性的充分必要条件是或。13 ，多值依赖的合并律是以以；伪传递律是以以；分解律是。14 对于函数依赖X以Y，如果Y巨X，则称X以Y是一个。15 对属性集U上的一个多值依赖X+一Y(X，Y是U的子集)，如果以以，则称以以是一个平凡的多值依赖。16 好的模式设计应符合、三条原

54、则。三、问答题1关系规范化一般应遵循的原则是什么?2多值依赖与函数依赖有哪些主要的区别?3低级范式的关系模式对数据存储和数据操作产生的不利影响是什么?4 3NF与BCNF的区别和联系各是什么?5设一关系为：学生(学号，姓名，年龄，所在系，出生日期)，判断此关系属性组属于第几范式。为什么?6下面的结论哪些是正确的?哪些是错误的?对于错误的请给出一个反例说明之。(1)任何一个二目关系是属于3NF。(2)任何一个二目关系是属于BCNF(3)任何一个二目关系是属于4NF。(4)当且仅当函数依赖A+B在R上成立，关系R(A,B,C)等与其投影Rl(A,B)和凡(A,C)的连接。(5)若R.AR.B,R.B-"R.C,则民A'-*R.C(6)若R.AR.B,R.A+兄C,则R.A民(B,C)(7)若R.BR.A.R.C+R.A,则R.(B,C)R.A(8)若R.(B,C)R.A,则R.B'-R.A,R.CR.A四、综合题1.对给定的关系模式R(U,F),U=A,B,C,D),F:AB,CD,BC卧灿球P、。胆：2.已知学生关系模式S(Sno,Sname,SD,Sdname,Course,Grade),其中：肛学号Sname姓名SD系名Sdname系主任名Course课程Grade成绩。默(1)写出