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

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

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

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

4、系模式分解成了若干个高一级范式的关系模式的集合, 这种过程叫做 规范化。下面将给岀各个范式的定义。1. 1NF(第一范式)定义若关系模式R的每一个分量是不可再分的数据项，则关系模式R属于第一范式(1NF)。例 供应者和它所提供的零件信息，关系模式如下:FIRST (Sno，Sname，Status, City，Pno, Qty)并且有 F= SnoSname， SnoStatus，Status City，(Sno， Pno) Qty。具体的关系如图 5 l所示。SnoSnameStatusCityPnoQtyS1精益20天津P1200S1精益20天津P2300S1精益20天津P3480S2盛锡

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

6、除后，在基本关系FIRST找不到S4,可S4又是客观存在的。正因为上述原因引入了2NF。2. 2NF(第二范式)定义若关系模式R1NF，且每一个非主属性完全依赖于码，则关系模式 R 2NF。即当1NF消除了非主属性对码的部分函数依赖,则成为2NF。例 FIRST关系中的码是 Sno、Pno,而SnoStatus，因此非主属性 Status部分函数依赖于码，故非2NF的。2NF若此时，将FIRST关系分解为:FIRSTI(Sno ，Sname，Status，City)FIRST2(Sno , Pno, Qty) 2NF因为FIRSTl和FIRST2中的码分别为Sno 和 Sno,Pno每一个非主

7、属性完全依赖于码。3. 3NF(第三范式)定义 若关系模式R(U , F)中不存在这样的码 X ,属性组 Y及非主属性Z(ZY)使得X Y , (Y X)Y/ Z成立，则关系模式即当2NF消除了非主属性对码的传递函数依赖R 3NF。，则成为3NF。例FIRSTl3NF，因为在分解后的关系模式FIRSTl 中有:Sno Status, Status City，存在着非主属性City传递依赖于码 Sno。4.BCNF(巴克斯范式);BCNF。定义 若关系模式 R 1NF，若X Y且Y X时，X必含有码，则关系模式BCNF。即当3NF消除了主属性对码的部分和传递函数依赖，则成为结论 一个满足BCNF

8、的关系模式，应有如下性质:(1) 所有非主属性对每一个码都是完全函数依赖;所有非主属性对每一个不包含它的码，也是完全函数依赖;(3) 没有任何属性完全函数依赖于非码的任何一组属性。(三)多值依赖1.多值依赖定义 若关系模式 R(U)中，X、Y、Z是U的子集，并且 Z = U X Y。当且仅当对 R(U)的任何一个关系r，给定一对(X，z)值，有一组 Y的值，这组值仅仅决定于X值而与z值无关,则称“ Y多值依赖于X”或“多值决定Y ”成立。记为：XY。2.多值依赖的性质多值依赖具有如下六条性质:(1)多值依赖具有对称性。即若Y，则Z，其中多值依赖的传递性。即若(3)函数依赖可以看成是多值依赖的特

9、殊情况(4)若 XZ，YZ若XZ，贝，XZ;若XZ，3. 4NF(第四范式定义(4NF)若关系模式必含有码，则关系模式R(U，F) 4NF。R 1NF，若对于R的每个非平凡多值依赖 XY且Y X时，X(四)函数依赖的公理系统Armstrong公理系统：设关系模式 R(U，F)，其中U为属性集，F是U上的一组函数依赖,那么有如下推理规则:(1)A1自反律：若YU，贝y X Y为F所蕴涵;(2)A2增广律：若 X为F所蕴涵，且 Z U，则XZ YZ为F所蕴涵;(3)A3传递律：若Y，Y Z为F所蕴涵，则X Z为F所蕴涵。(1)合并规则：若XY，XZ,则XYZ为F所蕴涵伪传递率：若XY，WYZ，则X

10、WZ为F所蕴涵(3)分解规则：若XY，ZY，则XZ为F所蕴涵。根据上述三条推理规则又可推岀下述三条推理规则:引理：X A: A1A2A1成立的充分必要的条件是X Ai成立(1=1 , 2, 3 ，k)(五) 函数依赖的闭包F+及属性的闭包 X +:1函数依赖的闭包定义 关系模式R(U , F)中为F所逻辑蕴含的函数依赖的全体称为F的闭包，记为：F+。2属性的闭包X +F定义 设 F 为属性集U 上的一组函数依赖， XU，= A | X X +p 能由 F 根据 Armstrong3公理导出 ，则称求属性 X 的闭包 X算法求属性的闭包输入输出X +F步骤(1)(2)(3)(4)为属性集 X 关

11、于数依赖集+X + FF 的闭包。吉的算法+X +FX(0)=X , i= 0B, B = A 1(X(i+1)=B X(i)v)(w)(V(i)V X A W)判断 X(i+1)= X(i) 吗(5)若相等，或 X(i)=U ，则X(i)为属性集X关于函数依赖集F的闭包。且算法终止若不相等，则i= i+1，返回第二步输出 F 的一个等价的最小函数依赖集G。F = A B，D C，BCE， ACB+X(0)=AE求 (AE) + F (AD)+ F解 求(，由上述算法，设A、 E 或 AE 的函数依赖，得到一个：计算 X(1): 逐一扫描 F 中的各个函数依赖，找到左部为A B。故有 X(1)

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

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

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

15、则 Y 是多余属性， 可以去掉。例 2 已知关系模式 R(U，F)，U = A，B，C，D，E，G;江 F = AB+C，D EG，C A，BE+C扩 BC D, CG BD , ACD-B，CE AG;请将F化为最小函数依赖集。; 解 此题可以有两种求解方法， 求解过程如下： 辈 方法 1 (利用算法求解， 使得其满足三个条件 );(1)利用分解规则，将所有的函数依赖变成右边都是单个属： 性的函数依赖，得 F 为：F = AB C，D+E，D+G，C A，BE CBCD， CGB， CGD， ACDB，CE+A ， CEGF 中去掉它 (假定它(2) 去掉 F 中多余的函数依赖，具体做法如下

16、：从第一个函数依赖开始从 为X Y)，剩下的函数依赖 F'求X '的闭包，看 X '是否含Y，若包含 Y，贝y X+Y为冗余函数依赖，则去掉它，否则不去。依次下去，直到能满足定义最小依赖的第二个条件。故有：设 AB C 为冗余的函数依赖，则去掉 AB+C 得F1 = D+E，D G，C+A，BE CBC+D， CGB， CGD， ACD+B，CE A， CE+G因为从 Fl 中找不到找到左部为AB或AB子集的函数依赖，则(AB)击=。所以 AB+C 非冗余的函数依赖，不能去掉。设CG B为冗余的函数依赖，则去掉 CG B得F2 = AB+C，D E，D+G，C+A，BE

17、 CBC+D ， CG+D ， ACD+B ，CE A， CE+G求 (CG) 左设 X*) ：CG计算 X ”'：逐一扫描 F2 中的各个函数依赖，找到左部为C 、 (；或 CG的函数依赖，得到一个：C A函数依赖。故有 XCGA O计算 X “：逐一扫描 F2 中的各个函数依赖，找到左部为CGA 或 CGA子集的函数依赖，得到一个：CG+D函数依赖。故有 X 9' = ACDG。计算 X “：逐一扫描 F2 中的各个函数依赖，找到左部为AC 拓或ACDG子集的函数依赖，得到两个：ACD B，D，E 函数依瓤故有 XCa)2ABCDEG 。；：扭 因为ABCDEG ； U ，

18、算法终止，(CG)占=ABCDE O 所以CG B为冗余的函数依赖,从 F2 中去掉。：设CG+D为冗余的函数依赖，则去掉CG D得；捍 F3 = AB+C，D-*E，D+G ， C-,-A ，BECBC+D，ACD-B，CE A，CE+G:求(CG)占； 设 XCO) : CG :计算Xm ：逐一扫描 F3 中的各个函数依赖，找到左部为 C、G 城 CG 的函数依赖，得到一个:C+A函数依赖。故有Xu ' :; ACG。熟 计算X '”：逐一扫描 F3中的各个函数依赖，找到左部为ACG 诚ACG子集的函数依赖，周为找不到这样的函数依赖。故有谨 =X ”，算法终止。(CG)占=

19、ACG O :因为ACG芒D，所以CG+D非冗余的函数依赖，不能从F3冲去掉。；- 设CE+A为冗余的函数依赖，则去掉 CE A得瞰 F4 = AB-*'C，D-E，D-*G，C+A，BEC ； BC-*-D，CG D，ACD-B，CE+G):求(CZ)击； 设 X(0 ' : CE芝 计算 X-) ：逐一扫描 F4 中的各个函数依赖，找到左部为C、 E 藏 CE 的函数依赖，得到一个：C A 函数依赖。故有：X(1 '= 5ACE O 计算XC2) ：逐一扫描 F4 中的各个函数依赖，找到左部为ACE ；藏 ACE 子集的函数依赖，得到一个：CE G 函数依赖。故有：

20、骚X 2) = ACEG。计算 X ”'：逐一扫描 F4 中的各个函数依赖，找到左部为ACEG 或 ACEG 子集的函数依赖，得到一个：CGD 函数依赖。故有：=ACDEG O计算 X “：逐一扫描 F4 中的各个函数依赖，找到左部为 AC DEG 或 ACDEG 子集的函数依赖，得到一个：ACDB 函数依赖。故有：=ABCDEG O因为 XABCDEG = U,算法终止，（CE）占：ABCDEG。所以 CE+A 为冗余的函数依赖，从F4 中去掉。又因为 F4 中无多余函数依赖所以转（3）。（3）去掉 F4 中各函数依赖左边多余的属性。函数依赖 ACD+B，属性A是多余的，去掉 A得C

21、D B,因为 CA 所以可推导出 ACDB。故最小函数依赖集为：FMIN = AB+C , D E , D+G , C A, BE CBC+D ， CGD， CD+B， CEG方法 2 （利用 Armstrong 公理系统的推理规则求解 ）假设CG B为冗余的函数依赖，那么，从F中去掉它后能根据 Armstrong 公理系统的推理规则导出。因为CG+DCA （已知）所以CGA ACD （增广律 ）因为ACD B（已知 ）所以CGA B （传递律 ）因为CA（已知 ）所以CG B （蕴涵 ）同理可证：CE A 是冗余的。又因C A , CD B 可知，需要注意的是F 的最小依赖集ACD-B L

22、故 去掉左边多余的属性得 CD-B 。FMIN 不一定是惟一的 它与对各函数依赖 FDi 及 XA 中X 各属性的处理顺序有关。例3已知关系模式 R（U , F）, U = A , B, C;F = A+B , B A , B+C , A+C , C A求最小函数依赖集。分析此题可以有两种不同的答案 下面分别叙述如下。答案1设B A是冗余的，将其从 F中去掉，看能否根据,Armstrong公理系统的推理规则导出。B-C CA（已知 ）BA（传递律 ）故 A+C是冗余的，将其从 n 中去掉，得 Fm为： FM , = A B, B+C , G+A。 因为在 FM ，中的其它函数依赖是非冗余的，所

23、以，FMl 为最小函数依赖集。答案 2设 B C 是冗余的，将其从 F 中去掉，看能否根据、 Armstrong 公理系统的推理规则导出。：因B A， A+C(已知 )故B-,-A是冗余的，将其从 F中去掉，得n为F1：A+B ， B-C ， A+C ， C+A 。又设 A C 为冗余，将其从 F1 中去掉(传递律 )因 A B, B-C(已知) 故 A C故 B C (传递律 )故 B+C 是冗余的，将其从中去掉，得FM2 为FM2 = A B, B+C , A C,CA。：i 因为在 Fm 中的其它函数依赖是非冗余的， 所以，FM2 为最小函数依赖集。从上分析我们可以得到两个最小函数依赖集

24、Fh4，和Fht。，因此，F的最小函数依赖集不是惟一的。(七)模式分解1分解定义(分解)关系模式R(U , F)的一个分解是指，P Rl(UI , P1), R2(U2 , F2)，R。(U。，F。)，其中:U = UU，并且没有U(U ,K i, j< n, E是F在U上的投影。其中 Fi = X YX YEF'八 XY 三 Ui对一个给定的模式进行分解，使得分解后的模式是否与原来的模式等价有三种情况:(1) 分解具有无损连接性；(2) 分解要保持函数依赖；(3) 分解既要无损连接性；又要保持函数依赖。2无损连接定义 (无损连接)P' R , (U1 , F: ), R

25、 : (U : , F2)，Rh(Uk , Fk)是关系模式 R(U , F)的一个分解，若对R(U ,F)的任何一个关系r均有r = mP(r)成立，则成分解P具有无损连接性(简称无损分解 )。其中， mP(r) ：冈丌 R：(r) 。定理 关系模式R(U , F)的一个分解，P' R1(U :,(U2 , F : )具有无损连接的充分必要的条件是:UI 门 U2 一 Ul U2EF '或Ul 门 U2+U2 一 UlEF3保持函数依赖F1)，R：， F1)， R:咖 2, F2)，Rk(Uk , Pk),如果：F' = (U 丌 Ki(F1-)'，则称分解P

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

27、察这些行中1i 列的元素，若其中有，则全；都改为，否则全部改为bmli, m是这些行的行号最小值。果在某次更改后 有一行成为:a1 a2 an 则算法终止。:且分解 p 具有无损连接性否则不具有无损连接性。:，对F中P个FD逐一进行一次这样的处理，称为对 F的一次；扫描。:；(3)比较扫描前后，表有无变化，如有变化，则返回第(2)步，：否则算法终止。-定义：设关系模式 R(U , F)的一个分解，P = 民(U :斗 如果发生循环，那么前次扫描至少应使该表减少一个符号，表:中符号有限，因此，循环必P = R1(U : , F1) , R : (U :,然终止。:算法 2 转换成 3NF 的保持

28、函数依赖的分解。孓,A :，An , F =F : ), Rk(Uk , Fk)是关系模式 R:囊 U, F)的一个分解，U: A :FDI , FD2，：FD , ，并设F是一个最小依赖集，记FDi为咒一,其步骤如下：；(1)对R(U , F)的函数依赖集F进行极小化处理(处理后的：结果仍记为F)；(2 )找出不在 F 中出现的属性,将这样的属性构成一个关系模式。把这些属性从 U 中去掉 剩余的属性仍记为 U；若有X A正F,且XA = U，贝y P' R，算法终止;(4) 否则,对 F 按具有相同左部的原则分组(假定分为 k 组),每一组函数依赖Fi所涉及的全部属性形成一个属性集U

29、。若U三U(ire就去掉U。由于经过了步骤(2),故U U9，于是 P' R , (Ul, F1), R2(U2 , F2)，Rk(Uk ,Fk)构成R(U , F)的一个保持函数依赖的分解。并且，每个(Ui , E)均属于3NF且保持函数依赖。RiG)，CSG, C+T, THI, HIC, HSI> ,将其分解成3NF并保持例4关系模式 R(U，F)，其中U = C , T, H , I, S,函数依赖。解 根据算法 2 求解如下：(1)F 已为最小函数依赖集；(2)R 中的所有属性均在 F 中都出现,所以转 (3)；对F按具有相同左部的原则分为：R1 = CSG , R2

30、;CT,R3'： THI , R4： HIC ,R5：HSR 。所以P R1(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求岀保持依赖的分解 P = R1 , R。，R。ii (2)判分解P是否具有无损连接性，

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

32、l 改为同一符号 a1 '；修改后如图 5 3 所示。根据F中的CS G,对上表进行处理，由于属性列CS上第一行、第五行相同al、a5，所以将属性列G上b,。改为同一符号a6。又根据C T将属性列T上b。：改为同一符号 a2,修改后如图5 4所示。从上可见，找到一行(第5行)为全a,所以分解是无损的。若P中有一个关系模式民不是4NF，则Ri中必能找到一个函数依赖X 一一 A，且X不包算法4将关系模式转换成 BCNF，使它具有无损连接的分解。输入 关系模式 R 和函数依赖集 F 。输岀 R(U , F)的一个分解 P' R, (U , , F1) , Ro (U2 , F :),

33、Rk(Uk , Fk),民为 BCNF ,且P具有无损连接的分解。操作步骤如下:令P = R若P中的所有模式都是 BCNF，则转(4)；若P中有一个关系模式民不是 BCNF，则民中必能找到一个函数依赖X A，且X 不是民的候选键，且 A不属于X，设Rn(XA) , Ri2(民一 A)，用分解 民, Rn代替民，转(2)；(4)输岀 F；例 6 关系模式 R(U，F)其中：U： C，T，H，I，S，G，F 二 CS C，C T，TH I ，HI+C ， HSI> ，将其无损连接地分解成BCNF o解 R 上只有一个候选关键字 HS(1)令PR(U , F) l:(2)p中不是所有的模式都是

34、BCNF，转(3); R扭；(3)考虑CS G ,这个函数依赖不满足BCNF条件(CS不包蒙禽候选键HS)，所以将其分解成Ri(CSG)、R2(CTHIS) o计算法1和R2的最小函数依赖集分别为：Fl = CS G , F2 = C 一黔T , TH I,HI C, HS 1> o R2的候选关键字为 HS。默 因 R1已是BCNF，而R2的F2中存在不为码的决定因睽素 HI C驻 故 R2不属于BCNF，进一步分解 R2即可。爱：. 分解R2 : 考虑C T,将其分解成 R21(CT)、R22(CHIS)。计6薯R21和R22的最小函数依赖集分别为:F21 = C T，F22 =&#

35、167;: CH+I，HI+C，HS+I>C T，TH 一 1，.在 F22 中, 有CH 一心。R22的候选关键字为 HS。整 因 R21已是BCNF , R22不是BCNF熙故 进步分解 R22即可。默 分解R22 :考虑CH 一 1,将其分解成 R221(CHl)、R222扭CHS)。计算 R221 和 R222 的最小函数依赖集分别为：盼酝F221 = CH I, HI C鞯 R : F222 :HS+C o ir戴 因 R221 , R222已是BCNF磬 故将R分解后为：芝p= R1(CSG),R21(CT)，R221(CHl)，R222(CHS)醛算法5将关系模式分解成 4

36、NF，使它具有无损连接性。酝 输入 关系模式R和函数依赖集 F。黔 输岀 R(U ,F)的一个分解P= RI(U ,F1) ,R2(U :,F2), F? ” , Rk(U , , Fk),民为4NF ,且P具有无损连接的分解。 卧操作步骤如下： 芝 令 P = R含民的候选键，且 A X乒中，XA ; i民令Z = A X，由分解规则得岀 X 一一 Z。令R。(XZ),Ri2(民一 Z)，用分解<Ril , Ri2代替民，由于(R，门Ri2)一一 (R, 一 Ri。)，所以分解具有无损连接性。转 (2)；(4) 停止分解，输出 p二、典型题解析例5 1对给定的关系模式 R(U , F)

37、, U = A , B, C> , F= <A B)，如下的两个分解:F1 = AB , BCp := AB , AC判这两个分解是否无损。解 ( 1 )根据定理判断本题因 AB门BC = BAB BC = ABC AB = CB+C 争 F '故P,为有损连接。(2) 根据定理判断本题因 AB 门 AC 二 AAB AC = BAC AB = CB+C F'E,F 山A C, B C , C D, DE C, CE A，如下的分解：；p = R : (AD) , R2(AB), R:(BE) , R: (CDE) , Rs(AE) 捌分解 P 是否无损。豪 解 (

38、1)构造一个初始的二维表如图5 5所示。拦臻 (2)根据A+C，对上表进行处理，由于属性列A上第一行、汝二行及第三行相同a,所以将属性列 C上b,、b:,、b53改为同一瓢细号 b13，取行号最小值。又根据B C 将属性列C上b"、b北改为粗阑一符号 b13，修改后的表如图 5 6所示。牡芝 故p：为无损连接。豁 例5 2对给定的关系模式R(U , F), U = A , B, C , D,(3)根据C+D ,对上表进行处理，由于属性列C上第一行第野仁行、第三行及第五行相同b,-且属性列 D 上第一行为 a，所以将 R '洄性列D上b:,、b :、 b: 改为同一符号 a:解

39、 (1)构造一个初始的二维表如图5 10 所示。修改后的表如图 5 7 渤示。团 O (4) 根据 DE+C ,将属性列C 上第三行及第五行改为同一符号a,修改后的表如图5 8 所示。(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 对给定的关

40、系模式R(U , F), U = A, B, C , D , E，尸轧 F ; A B,CP，EA, CE D，如下的分解：感p'R1(ABE) ，R2(CDEP) 甄。: (1)求 R 的候选关键字，并判分解P是否无损；扫； (2)R1、R :属于几范式。瓢解(1)候选关键字为 CE筻因 (CE)'=U 6 ;十故 有CE+U ,并且在CE中不存在一个真子集能决定R抽全体属性 U,故CE为R的候选关键字。萨:根据定理判断本题分解P是否无损举因 ABE门CDEP = E 2 :(已知 )E+ABEF '卧:故 故P为无损连接。甄.R1、R :属于几范式？踩：R1E2NF

41、骚；EA ， A+B良 故 E B ,存在传递依赖野故 R1任3NF萨 R :仨1NF皂CE+D，C+P 瑟故 CE能惟一地确定 R :中的每一个元组，故为候选关漠字。醛CE是候选关键字，而CP，所以P部分函数依赖良蔑“ ABE CDEP = AB 醛 磬 CDEP ABE : CDP 良 因 E+A , A+B莨故有E+B (传递律)寥“因 E+A , E B豪 故 有E+AB(合并律)封: 因与 CE故 R2 手 2NF例 5 4 对给定的关系模式R(U , F), U = A, B, C , D , E , P , F = A B , C P , E A , CE+D,如下的分解：p=

42、R1(CP) , R : (BE) , R3(ECD) , R: (AB),判分解 P 是否无损。（2）根据A B,对上表进行处理，由于属性列A上无相同元素，所以不能修改表。又根据 CP将属性列P上b :，改为a,修改后的表如图5 11 所示。（3）根据E A,对上表进行处理，由于属性列E上第二行、第三行相同a5,所以将属性列 A上b:,、L改为同一符号b:,，修改后的表如图5 12 所示。因此,在辗后的表格,找不到一行全为（4）根据CE D，对上表进行处理，无法修改上表。al, a:，an，所以P是有损的。：例5 5试证明由Armstrong公理系统推导岀下面三条推理规则是正确的：I （1）

43、合并规则：若 X Z, X Y，则有X YZ（2）伪传递规则：若 X Y，WY 乙则有 XW Z分解规则：若 X Y, Z任Y，则有X 一 2- 证明一.（1）合并规则:XY （已知）器 故 XXY （增广律 ）XZ（已知 ）XYYZ （增广律 ）:因 XXY， XYYZ（从上面得知 ）XYZ（传递律 ） （2）伪传递规则:，因 X+Y（已知 ）WX WY （增广律 ）WY Z （已知 ）XW 一（传递律）（3）分解规则:Z（Y（已知）YZ（自反律 ）XY（已知）XZ（传递律 ）3-6 关系R（A，B，C，D，E，F，G，H，I，J）满足下列函数依赖:ABD+E ， AB G， BF， C 一

44、工， CJI， G+H该函数依赖集是最小函数依赖集吗 ?给出该关系的候选码。解 该函数依赖集不是最小函数依赖集。CJ， CJI （已知 ）故 CJ （逻辑蕴涵 ）显然， ABCDGJ 是一个超码，即所有出现在函数依赖左边的属性的集合是超码。但是因 CJ （已知 ）故 可将 J 从超码中去掉。因 AB G （已知 ）故 可将 G 从超码中去掉。此时，超码中只剩下 ABCD ，由于它们都没有在函数依赖集的任何一个函数依赖的右边出现，所以它们都不能从超码中去掉。故候选码为：ABCD 。所谓超码是指能惟一标识关系中的每一个元组，不含多余属性的才是候选关键字（或候选码 ）。例3 7设P = R1（U1，

45、F1），R2（U2，F2）是R（U，F）上的一个分解，试证明P具有无损连接的充分必要的条件是： U1门U : 一 UI U2仨F'或UI门Uz U2 一 UI仨F'。证明 充分性：设 U、门Uz-'U : 一 U :，则可构造表如图5 13所示。该图省略了a、b 的下标。如果U，门U2+U，一 U2在F中，则可将表的第二行U，一 U :瀚韵所有符号全改为aaaa，使得该表的第二行全为a，则P具有海损连接性。同理可证U、门U : +U : 一 U :的情况。如果 UI门U2知：一 U :不在F中，但在F'中，那么，它可以从Armstrong 公理纂统的推理规则导出

46、，从而也能推出Ul 门 U2 一九，且 Ai 三 U1 一巍中，所以可以将九列的b改为a,同样，可将 UI U2的其它属醛对应的第二行也全改为a,这样,第二行就变成全a,所以分解是凛有无损连接性。卧 必要性：设构造的表中有一行全为a，例如第一行全为 a湘由函数依赖的定义可知U：门U :一 U :一 UI;如第二行全为a，则油函数依赖的定义可知U，门 U2+UI U2。黔例 5 8 试证明由关系模式中全部属性组成的集合为候选拱键字的关系是3NF ， 同 时 也 是BCNF 。 证明 由于关系模式中的全部属性组成的集合为候选关键障，该关系中没有非主属性，满足 R 属于 3NF 的条件，即每个非主幽

47、性即不函数依赖候选关键字，也不传递依赖于候选关键字。醛 又因为它没有非候选关键字的属性，也满足BCNF 的三个降件:F （1）所有非主属性对每个候选关键字都完全函数依赖；苣（2）没有任何属性都完全函数依赖于非候选关键字BCNF 的另一个陋伍 （3）所有的的任一组 61 性；因为它只是一个候选关键字，所以又满足主属性对每一个不包含它的候选关键字也是完全函数依赖。例5 9试证明一个关系模式 R是BCNF，那么它一定是3NF。证明 采用反证法。设关系模式 R 是 BCNF ，不是 3NF 的，则必存在非主属性 A和候选关键字 X以及属性组 Y，使得:X ， Y ， Y+A ，其中 A+X ， A Y

48、 ， Y+X 不属于 F '，这就是说 Y 不可能包含 R 的候选关键字，但 Y A 却成立。 根据 BCNF 定义， R 不是 BCNF ，与题设矛盾， 所以一个 BCNF 必是 3NF的。例5 10关系R(A , B, C, D, E)满足下列函数依赖:F = A C, C D, B C , DE C , CE A(1)给出关系 R 的候选关键字；(2)判P = AD , AB , BC, CDE , AE是否无损连接分解;将R分解为BCNF，并具有无损连接性。解(1)从函数依赖集 F中看，候选关键字至少包含BE，因为BE不依赖于谁，而(BE)'=ABCDE ，所以， BE

49、 是 R 的候选关键字。(2)构造一个二维表，如图514 所示。根据 A+C ,对上表进行处理,由于属性列 A 上第 1, 2, 5 行相同,但属性列 C 上对应的1, 2, 5行上无ai元素，所以，只能将b13b: bs,改为行号最小值b130 又根据 CD 将属性列D上b 改为a :，修改后的表如图5 15所示。臣 b lb扩 根据B C,对上表进行处理，由于属性列B上第2， 3 行相湘，但属性列C上对应的3行为a :元素，所以，只能将第2行b13改洳a3。又根据DE C , CE A不能修改此表所以修改后的表如卜 i声516所示。根据A C,对上表进行处理，由于属性列A上第1, 2, 5

50、府相同,但属性列C上对应的1, 2, 5行上有a3元素，所以，只能将藻1, 5行b13改为a3。又根据C+D将属性列D上b2 bs：改为a4,:修改后的表如图5 17 所示。根据CE+A，对上表进行处理，由于属性列CE上第4, 5行相伺，但属性列 A上对应的5行为al元素，所以，将第 4行b41改为a,。修改后的表如图518 所示。继续扫描 F 不能修改此表,由于找不到一行全为 a,所以该分解是有损的。考虑A C,因为AC不包含候选关键字，所以AC不是 BCNF ，故将 ABCDE 分解为两个子模式 R1(AC)R2(ABDE) 。此时， R1 正 BCNF 。继续分解R2，考虑B D，将AB

51、DE分解为两个子模式R21 (BD)R22(ABE) ，此时， R21 和R22 均属于 BCNF 。所以 R 分解为 BCNF ，并具有无损连接性的分解如下：P = AC , BD , ABE三、习 题一、选择题L 设学生关系模式为:学生 (学号,姓名,年龄,性别,成绩,专业),则该关系模式的主键是)。A .姓名B .学号，姓名C 学号 D .学号，姓名.年龄 搬 2.设关系模式 R（U ， F）， U 为 R 的属性集合， F 为 U 上的一种函数依甑，则对 R（U ， F）而言，如果X Y为F所蕴涵，且Z巨U，则XZ YZ为F所酶硒。这是函数依赖的（）。笋 A .传递律U .合并规则巴自反律D .增广律瓢 3 . X 一九成立是 X A1A2Ah成立