模式分解补充材料.docVIP

补充阅读材料（例题）属性闭包的计算例1设关系模式R的属性集U=A,B,C,D,E,G,F=ABC,BCAD,DE,CGB是R上的函数依赖集.求A,B关于F的闭包，即A,BF+。解： 从X=A,B 出发，X(0)=AB。(1) 左部为X(0)子集的函数依赖只有ABC，X(1)=ABC=ABC(2) 左部为X(1)子集而未检查的函数依赖只有BCAD，X(2)=ABCAD=ABCD(3) 左部为X(2)子集而未检查的函数依赖只有DE，X(3)=ABCDE=ABCDE已经不存在左部为X(3)的子集而未检查的函数依赖。因此，A,BF+=A,B,C,D,E注意到函数依赖CGB没有用上，因为它的左边没有包含在A,BF+中。函数依赖集的最小化例2 设F=ABC,BAC,CA,对F进行极小化处理解：(1) 根据分解规则，把F中的函数依赖转化成右部都是单属性的函数依赖集合，分解后的函数依赖集仍用F表示F=AB, AC,BA, BC,CA(2) 去掉F中的冗余函数依赖判断AB是否冗余。设G1=AC,BA, BC,CA,得 AG1+=AC因，所以AB不冗余。判断AC是否冗余。设G2=AB,BA, BC,CA,得 AG2+=ABC因，所以AC冗余（以后得检查不再考虑AC）。判断BA是否冗余。设G3=AB, BC,CA,得 BG3+=ABC因，所以BA冗余（以后得检查不再考虑BA）。判断BC是否冗余。设G4=AB, CA,得 BG4+=B因，所以BC不冗余。判断CA是否冗余。设G5=AB, BC,得 CG5+=C因，所以CA不冗余。由于该例中的函数依赖表达式的左部均为单属性，因而不需要进行第三步的检查。上述结果为最小函数依赖集，用Fm表示：FmAB, BC,CA若依次按AB，BC的顺序判定函数依赖是否冗余，则得到最小依赖集：Fm2AB, BA, AC,CA。这说明最小依赖集不唯一，与对各函数依赖FDi及XA中X各属性的处置顺序有关。同时注意到，在此例中A、B、C是一一对应的。例3 求F=ABC,AB,BA的最小函数依赖集Fm解：(1) 将F中函数依赖都分解为右部为单属性的函数依赖。显然，F已满足该条件。(2) 去掉F中冗余的函数依赖。判断ABC是否冗余。设，得 ， ABC不冗余。判断AB是否冗余。设，得 ， AB不冗余。判断BA是否冗余。设，得 ， BA不冗余。经检验后得函数依赖集仍然为F。(3) 去掉各函数依赖左部冗余得属性。本题只需考虑ABC的情况。方法一：在决定因素中去掉B，若，则以AC代替ABC。求得：。 以AC代替ABC。故，FmAC, AB,BA方法二：也可在决定因素中去掉A，若，则以BC代替ABC。求得：。 以BC代替ABC。故，FmBC, AB,BA例4 F=BEG,BDG,CDEAB,CDA,CEG,BCA,BD,CD，求Fmin.解： （1） 先分解右边F=BEG,BDG,CDEA, CDEB,CDA,CEG,BCA,BD,CD(2) 判断每个函数依赖，是否冗余。F= BDG, CDEB,CDA,CEG, BD,CD(3) , 包含G ，用BG代替BDG，未包含G ，不能用DG代替BDG，包含B ，用CEB代替CDEB，包含A ，用CA代替CDAFminBG,CEB,CA,CEG,BD,CD 候选码的确定确定关系模式的候选码是进行规范化分析的出发点，有下述准则可以使用：关系R(U,F)中，F是最小函数依赖集。准则1：如果属性A只在F中各函数依赖的左端出现，则A必是码中的属性；准则2：如果属性A只在F中各函数依赖的右端出现，则A必不是码中的属性；确定候选码的步骤是：(1) 对于关系模式R(U,F)，求F的最小函数依赖集，仍用F表示。(2) 根据准则1，确定码中必须有的属性集(设为M)。(3) 根据准则2，去掉码中没有的属性集。(4) 确定余下的属性集(设为W)。(5) 从M开始，令KM，如果，K就是候选码。否则从W选择属性加入到K中，直到，K就是候选码。(6) 注意可能有多个候选码。例5 设R(U,F),U=ABCDEG,F=BEG,BDG,CDEAB,CDA,CEG,BCA,BD,CD，求R的码。解：(1) 求得 FminBG,CEB,CA,CEG,BD,CD (2) 只在左端出现的属性CE (M=CE)。(3) 只在右端出现的属性ADG。(4) 余下的属性B (W=B)。R的候选码只可能是CE、CEB。经计算，因此R的码是CE。模式分解对模式分解的两个基本要求(1) 避免信息丢失：无损连接性；(2) 避免数据关系丢失。分解具有无损连接性和分解保持函数依赖是两个相互独立的标准。无损分解决定一个关系是否可分解，保持数据依赖决定一个关系分解的好坏。算法6.2 判别一个分解的无损连接性若是R的一个分解，不妨设F是一极小依赖集，记为。(1) 建立一张n列k行的表。每一列队应一个属性，每一行对应分解中的一个关系模式。若属性属于，则在j列i行交叉处填上，否则填上；(2) 对每一个做下列操作：找到所对应的列中具有相同符号的那些行。考察这些行中列的元素，若其中有，则全部改为，否则全改为，m是这些行的行号最小值。如在某次更改后，有一行成为。则算法终止。具有无损连接性，否则不具有无损连接性。对F中m个FD逐一进行一次这样的处置，称为对F的一次扫描。(3) 比较扫描前后，表有无变化。如有变化，则返回第(2)步。否则终止算法。定理6.5 对于R的一个分解，如果或，则具有无损连接性。定义6.19 若，则R的分解保持函数依赖。引理6.3 给出了判定两个函数依赖集等价的可行算法。因此引理6.3 也给出了判别R的分解是否保持函数依赖的方法。例6 关系模式R=CITY,ST,ZIP,其中CITY为城市，ST为街道，ZIP为邮政编码，F=(CITY,ST) ZIP,ZIPCITY。如果将R分解成R1和R2，R1=ST,ZIP,R2=CITY,ZIP，检查分解是否具有无损连接和保持函数依赖。解：(1) 检查无损连接性方法一：求得R1R2=ZIP ; R2-R1=CITY. (ZIPCITY)F+ （即 R1R2 R2-R1F+） 分解具有无损连接性方法二：构造判定矩表T，如下图：CITYSTZIPR1(ST,ZIP)b11a2a3R2(CITY,ZIP)a1b22a3由F中函数依赖ZIPCITY修改表T，结果如下：CITYSTZIPR1(ST,ZIP)a1a2a3R2(CITY,ZIP)a1b22a3表中已有一行全为a，所以具有无损连接性(2) 检查分解是否保持函数依赖求得 ； 。 该分解不保持函数依赖。可求得R的两个候选码为(ZIP,ST),(CITY,ST)。只在左端出现的属性为:ST，候选码必包含ST；其它属性为：CITY、ZIP。因 ，故 R有两个候选码：(ZIP,ST),(CITY,ST)例7 设关系模式R的属性集U=A,B,C,D,E,F=AB,BC,DE是R上的函数依赖集，=R1(A,B,C),R2(A,D,E)是R上的一个模式分解。(1) 求函数依赖集F的闭包F+中非平凡的函数依赖子集F*；(2) 求函数依赖集F*在关系模式R1、R2上的投影；(3) 判断分解是否具有无损分解；(4) 判断分解是否具有函数依赖保持性。解：(1) 求函数依赖集F的闭包F+中非平凡的函数依赖子集F*对F中的函数依赖AB，求属性集A关于F的闭包 从X=A 出发，X(0)=A。左部为X(0)子集的函数依赖只有AB，X(1)=AB=AB 左部为X(1)子集而未检查的函数依赖只有BC，X(2)=ABC=ABC左部为X(2)子集而未检查的函数依赖已不存在，故同理，由，得(2) 求函数依赖集F*在关系模式R1、R2上的投影；因R1(A,B,C),，所以因R2(A,D,E)，所以(3) 判断分解是否具有无损分解方法一：构造判定矩表T，如下图：ABCDER1(A,B,C)a1a2a3b14b15R2(A,D,E)a1b22b23a4a5由F中函数依赖AB修改表T，结果如下：ABCDER1(A,B,C)a1a2a3b14b15R2(A,D,E)a1a2b23a4a5由F中函数依赖BC修改表T，结果如下：ABCDER1(A,B,C)a1a2a3b14b15R2(A,D,E)a1a2a3a4a5表中已有一行全为a，所以具有无损连接性方法二：，由已知可得AB，AC，因而ABC，即，故分解具有无损连接性。(4) 判断分解是否具有函数依赖保持性F*在R1上的投影，F*在R2上的投影，令G=F1F2,可得G=F*,必有G+=F+,可见分解具有函数依赖保持性。1. 达到3NF保持函数依赖分解的方法：设有关系模式R(U,F)(1) 将F化为最小函数依赖集，令FFmin。(2) 把在F中不出现的属性(可看成无关属性)从U中去掉，属性集仍然用U表示.(3) 对照F中函数依赖集，将所有函数依赖左端相同的划分为一组，相应右端以及函数依赖均归入该组。(4) 这些分组就是分解后的模式组成。这种分解方法得到的就是达到3NF且保持函数依赖的分解。2. 达到3NF既符合无损连接并保持函数依赖的分解方法设有关系模式R(U,F)(1) 分解关系模式R到保持函数依赖的3NF：R1,R2,Rn。(2) 选取R的主码，将主码与函数依赖相关的属性组成一个关系Rn+1.(3) 将Rn+1归并到R1,R2,Rn中。这个分解系列就是既符合无损连接并保持函数依赖的分解系列。3. 达到BCNF无损连接的分解方法设有关系模式R(U,F)(1) 若RBCNF，算法终止，=R。(2) 若中有RiBCNF，即有非平凡的函数依赖：XY且XY Ri 而XY( X不含有码)，则分解Ri为Ri1 =X（RiY）和Ri2= XY；用Ri1和Ri2 代替中的Ri 。(3) 若中所有RiBCNF，输出，否则转(2)继续进行分解。 BCNF的分解算法通过不断地选择合适的分解，可以把任何关系模式分解成其属性子集的聚集，而这些子集具有如下重要特性：1. 这些子集都是属于BCNF的关系模式；2. 分解的关系能重构原始关系中的数据（即是无损连接的）。采取的策略是，寻找一个违背BCNF的非平凡依赖A1A2AnB1B2Bm (AB)；也就是说A1，A2，An不是码，作为试探，通常在右边加入尽可能多的由A1，A2，An函数决定的属性，如图所示。一个模式包含了违背BCNF的所有属性，而另一个模式则包含了该依赖的左边以及未包含在该依赖中的所有属性，也就是说，除A以外，再加上B之外的所有属性。A中属性B中属性其它通常，必须根据实际需要多次应用分解规则，直到所有的关系都属于BCNF为止。可以肯定最终必然成功，因为每次对关系R应用分解规则时，得到的两个关系模式的属性都比R小。当分解到只有两个属性的关系时，它必然属于BCNF。为说明分解为什么总是得到更小的模式，假设有一个BCNF的违例A1A2AnB1B2Bm。我们可以假定该依赖已经是扩展后的，B中包含了由A函数决定的所有属性，而且，任何既包含在A中，又包含在B中的属性已经从B中删除。分解后的一个模式是除了B以外的R的所有属性，B中必定至少有一个属性，因此该模式并不会包含所有的属性。另一个模式是A的所有属性和B的属性。这个集合不可能是R的属性全集，因为如果是这样的话，则A1,A2,An就是R的码。左边为码的依赖不是BCNF的违例。因此，可以断言分解后的两个模式都比R的模式小。所以不断分解的过程必然最终导致BCNF关系的聚集。4. 达到4NF无损连接的分解方法定理5.6 达到4NF无损连接的分解方法设有关系模式R(U,F)(1) 若R4NF，算法终止，=R。(2) 若中有Ri4NF，即有XY，X不包含Ri的码，YX，YXU。则分解Ri为Ri1 =X（RiY）和Ri2= XY；用Ri1和Ri2 代替中的Ri 。(3) 若中所有Ri4NF，输出，否则转(2)继续进行分解。例8 设关系模式R的属性集U=A,B,C,D,E,G,F=BEG,BDG,CDEAB,CDA,CEG,BCA,BD,CD，(1)求达到3NF并保持函数依赖的分解；(2) 求达到3NF既符合无损连接并保持函数依赖的分解。解 (1) 例4 中求得，FminBG,CEB,CA,CEG,BD,CD ，码是CE。分解成三个模式：R1,U1=BDG,F1= BG, BDR2,U2=ACD,F2= CA, CDR3,U3=BCEG,F3= CEB, CEG分解后，R1、R2、R3均达到3NF，且分解符合保持函数依赖的规则。R3就是包含码CE的模式，所以分解符合无损连接性。例9：设有关系模式R,U=CTHRSG,F=CT,HRC,HTR,CSG, HSR,试将R分解为3NF，且既具有无损连接性又能保持函数依赖。解： （1）确定R的码只在F左边出现的属性：HS，R的码必定包含HS；只在F右边出现的属性：G；其它属性：T，C。因，故R的码为HS。(2) 它的一个保持函数依赖的3NF为：=CT,HRC,THR,CSG,HSR 因为，主码HS及相关函数依赖HSR对应的模式已在中，所以，CT,CSG,HRC,HSR,THR为满足要求的分解。例10 设R(U,F),U=ABCDE,F=ABC, BD，DE，将R分解具有无损连接的BCNF。解： 只在F的函数依赖左边出现的属性：AB，R的码必定包含AB；只在F的函数依赖右边出现的属性：CE；其它属性：D。因为，故AB是R的码.分解过程如下：(1) 先分出DE，= R1(DE) ，R2(ABCD)(2) 再从R2中分解出BD，= R1(DE) ,R21(ABC),R22(BD)(3) R1,R21,R22都属于BCNF，分解完成。注:这种分解保持函数依赖.F=F1F2F3例11：设有关系模式R,U=CTHBSG,F=CT,HBC,HTB,CSG, HSB,试将R分解成具有无损连接的BCNF。解：只在左端出现的属性有H、S，只在右端出现的属性有G，其它属性C、T、B，R的码包含HS。，R的码是HS。另CTHBSG(1) 由于R的码为HS，选择CSG分解。得出：S1,S2其中：S1=CSG,F1=CSG; S2=CTHBS,F2= CT,HBC,HTB,HSB .S2 不服从BCNF，需继续分解。(2) 对S2分解。S2的码为HS，选择CT分解。得出：S1,S3,S4其中：S3=CT,F3=CT ; S4=CHBS, F4=HCB,HBC,HSB .(由 CT, HTB 推出HCB)S4 不服从BCNF，需继续分解。(3) 对S4分解，S4的码为HS，选择HCB分解得出：S1,S3,S5,S6其中：S5=HCB,F5=HCB ; S6=CHS, F6=.(4) 最后得到的分解为：CSG,CT,HCB,CHS例12：设有关系模式R,U=学号，课程号，成绩，教师名，教师所在系,F(学号,课程号) 成绩,课程号教师名,教师名教师所在系，将其分解为具有无损连接的BCNF。解： R的码为(学号,课程号)(1) 初始化，学号，课程号，成绩，教师名，教师所在系(2) 选择“教师名教师所在系”分解得出：=R1,R2.其中，R1=教师名,教师所在系,F1=教师名教师所在系R2=学号，课程号，成绩，教师名,F2=(