构造表格法判无损ABCABa1a2ACa1a3.ppt

1、5 关系数据库,1,第五章 RDB (关系数据库）5.1 函数依赖 FD5.2 闭包及其运算5.3 关系模式分解5.4 关系模式规范化 NF,5 关系数据库,2,问题 R ( Sh,Sn,Sex,Ch,Grade )Sh Sn Sex Ch GradeS1 丁一 m c1 90S1 丁一 m c2 89S1 丁一 m c3 88S1 丁一 m c4 87S1 丁一 m c5 95,insert,update,delete 异常,数据冗余,PK: ( Sh,Ch ),5 关系数据库,3,R1 ( Sh,Sn,Sex ) PK:Sh Sh Sn Sex S1 丁一 mR2 ( Sh,Ch,Grad

2、e ) PK: (Sh,Ch) Sh Ch Grade S1 c1 90 S1 c2 89 S1 c3 88 S1 c4 87 S1 c5 95,解决问题 模式分解,5 关系数据库,4,函数依赖D 函数依赖分类 函数依赖特性,问题,5 关系数据库,5,X1X2X3X4Xn,Y1Y2Y3Yn,XY,X决定Y,Y依赖于X,5 关系数据库,6,R(Sh,Sn,Sex,Ch,Grade) PK: (Sh,Ch),(Sh,Ch) Sn / Sex / Grade,Sh Sn / Sex,Sn/Sex对(Sh,Ch) Pfd 部分依赖,5 关系数据库,7,R(Sh,Sn,Sex,Ch,Grade) PK:

3、 (Sh,Ch),(Sh,Ch) Sn / Sex / Grade,Grade对(Sh,Ch) Ffd 完全依赖,(sh,ch) Grade,5 关系数据库,8,Ex. S (Sh , Bj , Bad),ShBj , BjBad,Bad对Sh tfd传递依赖,Sh Bad,Sh Bj Bad,5 关系数据库,9,R (U,F) Relation关系 U Property Set 属性集合 F FD Set 函数依赖集合 Pk: Primary Key 主键 Fk: Foreign Key 外键,5 关系数据库,10,W ( 日期D ，工号G，姓名N，工种A，定额B，超额C，车间E，车间主任F

4、 ),例,求,完全函数依赖fFD部分函数依赖 pFD传递函数依赖 tFD,Pk Primary Key主键,5 关系数据库,11,W( 日期D ，工号G，姓名N， 工种A，定额B，超额C， 车间E，车间主任F ),FD,PK: (D,G),(D,G)N/A/B/C/E/F,pFD,G N/A/ E,5 关系数据库,12,W( 日期D ，工号G，姓名N， 工种A，定额B，超额C， 车间E，车间主任F ),FD,PK: (D,G),(D,G),p,AB,t,G,B,N/A/E,三类函数依赖FD表示方法,G N/A/ E,5 关系数据库,13,1下表是职工职务工资表R1职工（E） 职务（F） 职务工

5、资（G）王 键 车间主任 1200张 扬 车间主任 1200王元元 工程师 800李 民 工程师 800,关系模式R1（E，F，G） 试述：（1）指出 R1的主键（2）指出是否存在部分函数依赖（3）指出是否存在传递函数依赖。（4）R1是否存在数据冗余、更新异常。,5 关系数据库,14,2. 表为一个某工程关系模式R（A，B，C，D，E，F）试述： （1）指出 R的主键（2）指出是否存在部分函数依赖（3）指出是否存在传递函数依赖（4）R是否存在数据冗余、更新异常。,5 关系数据库,15,2a. 表为一个某工程关系模式R（A，B，C，D，E，F）试述： （1）R是否满足1NF，为什么？（2）指出

6、R的主键 （3）指出是否存在部分函数依赖（4）指出是否存在传递函数依赖 （5）R是否存在数据冗余、更新异常。*（6）使用什么方法可以进一步提高范式，可达到第几范式,A D D E A E,YES,AB,ABD AD B F,YES,5 关系数据库,16,3.关系模式R(Sh,Ch,Grade,Tname,Taddr),其属性分别表示学生学号、选修课程的编号、成绩、任课教师姓名、教师地址等意义。如果规定，每个学生每学一门课程只有一个成绩，每门课程只有一个教师任课，每个教师只有一个地址（此处不允许教师同名同姓）。 1)指出 R的主键 3)指出是否存在部分函数依赖 4)指出是否存在传递函数依赖。 5

7、)R是否存在数据冗余、更新异常。,5 关系数据库,17,3a. 设关系模式R(Sh,Ch,Grade,Tname,Taddr),其属性分别表示学生学号、选修课程的编号、成绩、任课教师姓名、教师地址等意义。如果规定，每个学生每学一门课程只有一个成绩，每门课程只有一个教师任课，每个教师只有一个地址（此处不允许教师同名同姓）。 1)R是否满足1NF，为什么？ 2)指出 R的主键 3)指出是否存在部分函数依赖 4)指出是否存在传递函数依赖 5)R是否存在数据冗余、更新异常。 *6)使用什么方法可以进一步提高范式，可达到第几范式,YES,sh,ch,shch Tn ch Tn,ch Tn TnTa,YE

8、S,5 关系数据库,18,4.下表为一个职工关系模式R（A,B,C,D,E） 日期A 工号B 超额C 车间D 车间主任E 1101 01 1500 组装 Li 1102 01 1000 组装 Li 1103 01 2000 组装 Li 1101 02 1800 配件 Wu,5 关系数据库,19,试述：(1) R是否满足1NF，为什么？(2) 指出 R的主键(3) 指出是否存在部分函数依赖(4) 指出是否存在传递函数依赖。(5)R是否存在数据冗余、更新异常。*(6)使用什么方法可以进一步提高范式，可达到第几范式,函数依赖应用举例,5 关系数据库,20,4a.下表为一个职工关系模式R（A，B，C，

9、D，E）。 日期（A）工号（B）超额（C）车间（D）车间主任（E）(1) R是否满足1NF，为什么？(2) 指出 R的主键(3) 指出是否存在部分函数依赖 (4) 指出是否存在传递函数依赖。 (5)R是否存在数据冗余、更新异常。*(6)使用什么方法可以进一步提高范式,可达到第几范式,Yes,PK:AB,ABD BD pFD,ABE DE tFD,Yes,R1(A,B,C) R2(B,D) R3(D,E) 3NF ABE DE tFD,5 关系数据库,21,FD Armstrong,R( U ),xy,xy,xzyz,xyyz,xz,自反律,增广律,传递律,函数依赖特性,5 关系数据库,22,F

10、D Armstrong,R(U),xyz,xyz,xyywz,xwz,xyxz,xyxz,合并律,分解律,伪传递律,函数依赖特性,5 关系数据库,23,5.2 闭包X+及其运算,书86,问题,闭包定义闭包求法闭包运用,定义：X ？,5 关系数据库,24,5.2 闭包X+及其运算,R ( U,F ) U=A,B,C,D,E,I F=AD,ABE,BIE,CDI,EC? (AE)+,(AE)+=ACDEI,书86,AD,EC,AEAE,AEAC E,CDI,AEACDEI,D,5 关系数据库,25,R ( U,F ) U=A,B,C,D,E,I F=AD,ABE,BIE,CDI,EC? (AE)+

11、,AEAE (AD, EC) AEACDE (CDI) AEACDEI,(AE)+=ACDEI,书86,AE决定的属性集就是的闭包记为(AE)+,5 关系数据库,26,AE决定的属性集合就是的闭包. 记为: (AE)+,的闭包 ?,求闭包就是求它所决定的属性集合,5 关系数据库,27,R(U,F) U=A,B,C,D,E,P F=AB,CP,EA,CED? (CE)+ , C+, E+,左部(only),CK书29,(CE)+=U (C+!=U, E+ !=U) (C,E):CK,EE (EA) EAE (AB) EABE,CC (CP) CCP,CECE (CP, EA,CED) CEACD

12、EP (AB) CEABCDEP=U,5 关系数据库,28,侯选关键字 CKCandidate Key指 它的值能决定元组值; 它的子集值不能决定元组值. 即它具备主键的特性,CK书29,主键是在侯选关键字 CK中选择,5 关系数据库,29,?求侯选关键字 CK方法 F Fmin,CK书29,1. FD左部(only)属性一定是CK成员2. FD左,右部属性可能是CK成员3. 与F中FD无关属性也一定是CK成员,5 关系数据库,30,1. R(U,F) U=C,G,N,S,T F=CT,CSG, SN ? Candidate Key,3. R(U,F) U=A,B,C,D,EF=AD,ED,D

13、B,BCD,DCA ? Candidate Key4. R(U,F) U=A,B,C,D,EF=ABC,CDE,BD,EA ? Candidate Key,2. U=A,B,C,D,E,G F=AB,CA,CDE,DG ? Candidate Key,CK书29,5 关系数据库,31,1. R(U,F) U=C,G,N,S,T F=CT,CSG, SN? Candidate Key,左部(only),CK书29,左部(only) 是S是S,5 关系数据库,32,1. R(U,F) U=C,G,N,S,T F=CT,CSG, SN? Candidate Key (CS)+,左部(only),即C

14、SCSGTN,CS+=U; C+=CT; S+=SN,CK: CS,CK书29,CSCS (CSG) (CT) (SN) CSU,5 关系数据库,33,2. R(U,F) U=A,B,C,D,E,G F=AB,CA,CDE,DG ? Candidate Key,左部(only),CK书29,5 关系数据库,34,2. R(U,F) U=A,B,C,D,E,G F=AB,CA,CDE,DG ? Candidate Key C+, (CD)+ , D+,左部(only),AA (AB) AAB,CC (CA) CCA( AB) CCAB,DD (DG) DDG,CDCD (CDE)(CA) (DG

15、) CDCDEAG ( AB) CDABCDEG=U,CD+=U; C+=CAB; D+=DG,CK: CD,CK书29,5 关系数据库,35,3. R(U,F) U=A,B,C,D,E F=AD,ED,DB,BCD,DCA ? Candidate Key,左部(only),CK书29,左部(only) 是且(CE)+=U是,5 关系数据库,36,左,右部属性,4. R(U,F) U=A,B,C,D,E F=ABC,CDE,BD,EA ? Candidate Key,左部(only) 无.是由左,右部属性组成,5 关系数据库,37,AA (ABC) AABC ( BD) AABCD (CDE)

16、 AABCDE=U,左,右部属性,4. R(U,F) U=A,B,C,D,E F=ABC,CDE,BD,EA ? Candidate Key A+,(CD)+ , B+, E+, (BC)+,CK: A, CD, E , BC,EE (EA) EEA (ABC) EEABC (BD) EABCDE=U,BB (BD) BBD,CDCD (CDE) CDCDE (EA) CDCDEA (ABC) CDABCDE=U,BCBC (BD) BCBCD,5 关系数据库,38,?求侯选关键字 CK方法 F Fmin,CK书29,1. FD左部(only)属性一定是CK成员2. FD左,右部属性可能是CK

17、成员3. 与F中FD无关属性也一定是CK成员,5 关系数据库,39,最小函数(FD)集合 Fmin,例1、 R(U,F) U=A,B,C,D,E,G F=ABC,CA,BCD, ACDB,DEG， BE C,CG BD, CE AG? Fmin,函数依赖应用举例之二求Min FD集,5 关系数据库,40,F=ABC,CA,BCD,ACDB,DEG，BE C，CG BD，CE AG,F1= ABC,CA,BCD,ACDB, DEG， BE C， CG BD， CE AG ,DE，D G，,CG B， CG D，,CE A， CE G ,2.去掉F1左部的多余属性得F2,CA,CE A,CE A,

18、ACD少A,A,1.将F中FD右边属性单一化,5 关系数据库,41,3、去掉F2中多余的FD,故去掉CGD或CG-B得F3F3比F2少一项,2.去掉F1左部的多余属性得F2 F2=ABC,CA,BCD, CDB,DE,D G, BE C,CG B, CG D,CE G,CG D,CG B,设去掉CG B （CG)+= CGDABE=U 故CG-B可去掉,设去掉CGD （CG)+= CGBADE = U 故CG D可去掉,5 关系数据库,42,例2、 F=ABC , EP A ， D H ， AB E ，CDE P ，D G ，ABC G GP B ，HB P ，ABC P，A C ? Fmin

19、,ABC P 改为 ABC G 改为,ABC,A C,F2: 去掉 ABC,F1=右部单一化 FD,F3:分别假设去掉AB-P和AB-G计算(AB)+,AB P AB G,AB G,AB P,C,C,5 关系数据库,43,求 Fmin 的方法1、使F 中每一个FD右部属性单一化2、去掉各FD左部多余的属性 若有X A 而XY A ,则Y是多余的 若有 X-Y 而XYZ A ，则Y是多余的3、去掉多余的FD 设去掉X Y，再求X+ 若X+包含Y ，则X Y是多余,5 关系数据库,44,练习 F=E G ， G E， F EG ， H EG ， FH E? Fmin,右部单一得F1有七项去掉左部多

20、余属性得F2有六项去掉多余FD得F3有四项,FH E,Fmin =E G ， G E， F E ，H G,5 关系数据库,45,最小FD集 Fmin 应满足的条件：（1）F中每一个FD的右边都是单属性（2）F中任一FD，X A 其F-X A与F不等价 (即缺任何一个FD都与原F不等价)（3）F中任一个FD，X A，Z是X的子集， （F-X A） Z A与F不等价 即Z X，X A无法用Z A替代,5 关系数据库,46,（1） 分解得F=A B，A C，B A， B C，C A （2）判别每个FD 设 G=F-A B A+G=AC,练习1 F=A BC，B AC，C A ？Fmin,G=F-A

21、C A+G=ABC,A C,G=F-B A B+G =ABC,B A,G=F-B C B+G =BG=F-C A C+G =C,5 关系数据库,47,练习2 F=BE G ， BD G，CDE AB， CD A ， CE G，BC A， B D ， C D ？Fmin,CE A CE,B,5 关系数据库,48,作业一、求CK？ 1,3题U=A,B,C,D,E 2题U=A,B,C,D,E,G1、 F=AD,ED,DB,BCD,DCA2、F=AB C ,D EG,C A，BD C 3、F=E A，CD E，B D，A BC二、求Fmin?1、 F=ABD AC,C BE,AD BF,B E2、F=

22、A BC，B C，A B，AB C,5 关系数据库,49,5.3 关系模式分解,问题,分解方案选择方案选择依据,5 关系数据库,50,例:学生宿舍表SL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B ,5 关系数据库,51,方案1. SL分解为下面三个关系模式： SN(Sno) SD(Sdept) SO(Sloc),SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 PH 95005 ,问题:信息丢失,5 关系数据库,52,方案

23、2、SL分解为下面二个关系模式： NL(Sno, Sloc) DL(Sdept, Sloc) NL DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B ,5 关系数据库,53,NL DL Sno Sloc Sdept 95001 A CS 95002 B IS 95002 B PH 95003 C MA 95004 B IS 95004 B PH 95005 B IS 95005 B PH,元组增加了，信息丢失了,5 关系数据库,54,方案3. 将SL分解为下面二个关系模式： ND

24、(Sno, Sdept) NL(Sno, Sloc),ND NL Sno Sdept Sno Sloc 95001 CS 95001 A 95002 IS 95002 B 95003 MA 95003 C 95004 IS 95004 B 95005 PH 95005 B ,5 关系数据库,55,ND NL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 CS A 95005 PH B 与SL关系一样，因此没有丢失信息,数据无损,5 关系数据库,56,且F=A B，B C,书95,R1(A,B)A,B(R),R2(A,C)A,C(R)

25、,R (A,B,C),分解方案一,5 关系数据库,57,且F1=A B,书95,R1(A,B),R2(A,C),R (A,B,C),R1R2,1,具有无损连接性,1具有依赖保持性 2具有无损连接性 =,5 关系数据库,58,且F=A B，B C,书95,R (A,B,C),R1(A,B)A,B(R),R3(B,C)B,C(R),分解方案二,5 关系数据库,59,且F2=A B，B C,书95,R1(A,B),R3(B,C),R (A,B,C),具有无损连接性,1具有依赖保持性 =2具有无损连接性 =,5 关系数据库,60,且F=A B，B C,书95,R (A,B,C),R2(A,C)A,C(

26、R),R3(B,C)B,C(R),分解方案三,5 关系数据库,61,且F3=B C,书95,R2(A,C),R3(B,C),R (A,B,C),R2R3,1具有依赖保持性 2具有无损连接性,5 关系数据库,62,设关系模式R(U ,F) ,一个分解 =R1,R2,Rk若r =r1r2rk 称分解 满足函数依赖集的无损连接性,即 分解具有无损连接性,5 关系数据库,63,自然连接判断构造表格法3. 判别式,分解具有无损连接性判别方法,5 关系数据库,64,1. 利用构造表格法 A1 A2. R1 a1 当A1属于R1 a列号 R2 b21 当A1不属于R 2 b行列号利用F中的FD修改,若某行全

27、a,则无损,2.若二元 =R1,R2R1 R2R1 R2 或 R2 R1 满足FD 则无损,无损连接性判定方法,5 关系数据库,65,构造表格法判“无损”,A B CAB a1 a2AC a1 a3,1,R1 R2=A 交 差R1 R2=B A B 无损R2 R1=C,F中: AB,第二行全a,是具有“无损连接性”,b22,a2,b13,5 关系数据库,66,A B CAB a1 a2BC a2 a3,2,第一行全a,则无损,R1 R3=B B CR1- R3 =A 交 差R3 R1 =C 则无损,b21,b13,F中: B C,a3,5 关系数据库,67,A B CAC a1 b12 a3B

28、C b21 a2 a3 无全a行 有损R2 R3=CR2 - R3 =A R3 R2 =B,3,有损,5 关系数据库,68,例2 设R(城市C ,街道S ,邮编Z ) 且 F= (C,S) Z, Z C R 分解为 R1(S ,Z) R2 (C,Z),C S ZSZ a2 a3CZ a1 a3,b11,b22,Z C,第一行为全a,具有无损连接性,a1,5 关系数据库,69,F=Sh-Sn ,Sh-Dept ,Dept-Daddr 分解为下面几种是否具有无损连接性1= R1(Sh ,Sn) , R2(Dept ,Daddr) 2= R3(Sh ,Sn ,Dept) , R2(Dept ,Dad

29、dr) ,Sh Sn Dept Daddr S1 AB CS D1S2 CD CS D1S3 EF MA D2S4 EF PHY D3,练习,5 关系数据库,70,Sh Sn Dept DaSh Sn Dept a1 a2 a3Dept Da b21 b22 a3 a4,R2 R3= Dept R2 R3 =Daddr 无损,2,练习3 R(Sh,Sn,Dept,Daddr),b14,F中: Dept Da,第一行全a,是“无损”,a4,5 关系数据库,71,5.4 关系模式规范化,5 关系数据库,72,5.4 关系模式规范化,户名 水电费 丁一 36.00 120.00 马二 45.00 2

30、40.00 水电费非原子项，分割为水费，电费 户名 水费 电费 丁一 36.00 120.00 马二 45.00 240.00,定义：如果关系R的所有属性都是不可再分的数据项，称该关系属于第一范式，记为R 1NF,5 关系数据库,73,R(Sh,Sn,Sex,Ch,Grade) PK: (Sh,Ch),Sh Sn / Sex,(sh,ch) Grade,(Sh,Ch) Sn / Sex / Grade,非主属性,主属性,定义：R为第一范式，且R中每个非主属性完全函数依赖R的某候选键，则R 2NF,R1(Sh,Sn,Sex） R2（Sh,Ch,Grade),5 关系数据库,74,学生表（学号，姓

31、名，性别，所在城市，长途区号，课程号，学期，学分，成绩）,学生（学号，姓名，性别，所在城市，长途区号）,课程（课程号，学期，学分）,成绩（学号，课程号，成绩）,定义：R为第二范式，且R中每个非主属性都不传递依赖R的某候选键，,学生（学号，姓名，性别，所在城市)城市（所在城市，长途区号）,R 2NF,则R 3NF,5 关系数据库,75,R(城市C ,街道S ,邮编Z )且 F= (C,S)-Z, Z-C CK： （C，S）,分解为 ZC（Z，C），SZ（S，Z）,定义：R为第一范式，且每个属性都不传递依赖于R的候选键，,因有 ZC Z是决定因素，但不是键,R,BCNF,5 关系数据库,76,1N

32、F,R,2NF,3NF,BCNF,属性分解,消除非主属性对键的部分函数依赖,消除非主属性对键的传递函数依赖,消除主属性对键的传递函数依赖,5 关系数据库,77,例：W(日期D,工号G,姓名N,工种A,定额B,超额C,车间E,车间主任F) PK: (D,G),W1（D，G，C）W2（G，N，A，E）W3（A，B）W4（E，F）,保持,无损3NF？,5 关系数据库,78,D G C N A E B F DGC a1 a2 a3GNAE a2 a4 a5 a6 AB a5 a7 EF a6 a8,a4,a5,a6,a7,a8,G N,G A,AB,E F,G E,5 关系数据库,79,设R（U，F）F=B G,CE B,CA,CE G,B D ,CD1. 将其保持FD分解,实现3NF的方法, 若FFminF中FD左部相同,(含右部)构成子模式. R1: U1=BDG R2: U2=ACD R3: U3=BCEG,