数据库-模式的分解-无损连接性-教案ppt课件

.,1,3.9（关系）模式的分解,分解的定义：关系模式R的一个分解是指R1，R2，Rn其中UU1U2Un，并且不存在UiUj,1i,jn，Fi是F在Ui上的投影。函数依赖集合XY|XYFXYUi的一个覆盖(等价)Fi叫做F在属性Ui上的投影。,.,2,3.9模式的分解,3.9.1关系模式分解的标准把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义“等价”概念的三种定义：（1）分解具有无损连接性。（2）分解要保持函数依赖性。（3）分解既要保持函数依赖，又要具有无损连接性。,.,3,3.9.2无损分解,无损分解定义：关系模式R的一个分解=R1，R2，Rn，对于R的任一关系r，都有r为其在各Ui(1=1,n)上的投影的(自然)连接,即r=U1(r)U2(r)Un(r)，则称关系模式R的这个分解具有无损连接性（Losslessjoin）。具有无损连接性的分解保证不丢失信息。无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。,.,4,3.9.2无损分解（续）,例：S-L（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSlocS-L2NF，分解方法可以有多种：1.S-L分解为三个关系模式：SN(Sno)，SD(Sdept)，SL(Sloc)2.SL分解为下面二个关系模式：NL(Sno,Sloc)，DL(Sdept,Sloc)3.将SL分解为下面二个关系模式：ND(Sno,Sdept)，NL(Sno,Sloc),.,5,3.9.2无损分解（续）,第3种分解方法具有无损连接性。问题:（1）没有保持原关系中的函数依赖，即S-L中的函数依赖SdeptSloc没有投影到关系模式ND、NL上。（2）存在冗余和操作异常。,.,6,3.9.2无损分解（续）,4.将SL分解为下面二个关系模式：ND(Sno,Sdept)，DL(Sdept,Sloc)该分解保持了函数依赖(且具有无损连接性)。,.,7,3.9.3保持函数依赖的模式分解,定义：设关系模式R被分解为若干个关系模式R1，R2，Rn其中U=U1U2Un，且不存在UiUj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的（Preservedependency）。,.,8,3.9.3保持函数依赖的模式分解（续）,例如，将SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSloc分解为下面二个关系模式(第四种分解)：ND(Sno,Sdept)，DL(Sdept,Sloc)该分解保持了函数依赖(具有无损连接性)。,.,9,3.9.3保持函数依赖的模式分解(续),如果一个分解具有无损连接性，则它能够保证不丢失信息。如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖；同样，保持函数依赖的分解也不一定具有无损连接性。,.,10,3.9.3保持函数依赖的模式分解(续),对于关系模式S-L：第1种分解方法既不具有无损连接性，也未保持函数依赖。第2种分解方法未保持函数依赖，也不具有无损连接性。第3种分解方法具有无损连接性，但未保持函数依赖。第4种分解方法既具有无损连接性，又保持了函数依赖。,.,11,3.9.4模式分解算法,算法1判别一个二元分解的无损连接性算法2判别一个分解的无损连接性算法3（合成法）转换为3NF的保持函数依赖的分解。算法4转换为3NF既有无损连接性又保持函数依赖的分解。算法5（分解法）转换为BCNF的无损连接分解算法6达到4NF的具有无损连接性的分解。,.,12,算法1判别一个二元分解的无损连接性。若F中至少存在如下函数依赖中的一个：（1）（U1U2）U1U2（2）（U1U2）U2U1则=R1，R2是R的无损分解。反之也成立。如：模式S-L（Sno，Sdept，Sloc）分解为2个模式：ND(Sno,Sdept)，NL(Sno,Sloc)则是无损分解。,3.9.4模式分解算法,.,13,算法2判别一个分解的无损连接性,设R1，R2，Rk是R的一个分解，UA1,An构造一张k行n列的表格。每列对应一个属性Aj，每行对应一个模式Ri。如果Aj属于Ui，那么在表格的第i行第j列处填上符号aj，否则填上bij。,.,14,算法2判别一个分解的无损连接性,逐一检查F中的每个函数依赖，并修改元素，方法是：1、取F中一函数依赖XY(从第一个开始，到最后一个取完结束)，2、找出X所对应的列中具有相同符号的行。（如X列中有某两个值均为a3的行,则算是相同的两行，如果是有两个下标的则不是相同符号，如a31）3、考察这些行中Y列的元素，若其中有aj，则全部改为aj，否则全部改bmj，其中m是这些行的行号最小值。4、若在某次更改后，有一行是a1a2an，那么相对于F是无损分解，算法结束。对F中的每个函数依赖进行一次上述的处置，称对F的一次扫描。,.,15,算法2判别一个分解的无损连接性,比较扫描前后，表有无变化。如有变化，则返回第步处理，否则，算法结束，则相对于F是有损分解。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此循环必然会终止。,.,16,算法2判别一个分解的无损连接性,例1，设关系模式R(ABCDE)，F=ABC，CD，DE，R分解成=R1(ABC),R2(CD),R3(DE)。那么相对于F是否无损分解？,.,17,算法2判别一个分解的无损连接性R1(ABC),R2(CD),R3(DE)F=ABC，CD，DE,初始表：,最后结果：,R1,R2,R3,R1,R2,R3,1,2,2,相对于F是无损分解,.,18,算法2判别一个分解的无损连接性,例2，R(A，B，C)，F=AB，CB分解1=R1(A,B)，R2(A,C)分解2=R1(A,B)，R1(B,C)分析两种分解的无损连接性？分解1只具有无损连接性,分解2不具有无损连接性。,AB,AC,AB,BC,.,19,算法2判别一个分解的无损连接性,例3，设关系模式R(ABCD)，R分解成=R1(AB),R2(BC),R3(CD)。如果R上成立的函数依赖集F=AB，CD，那么相对于F是否无损分解？,.,20,算法2判别一个分解的无损连接性F=AB，CD,.,21,3.9.4模式分解算法,算法3（合成法）转换为3NF的保持函数依赖的分解。（1）对关系模式R中的函数依赖集F进行“极小化”处理，处理后的函数依赖集仍记为F；（2）若有XAF，且XA=U，则=R，算法终止；（3）找出不在F中出现的属性，将它们构成一个关系模式，并把这些属性从R中去掉，把剩余的属性仍记为U。,.,22,算法3转换为3NF的保持函数依赖的分解,（4）对F按具有相同左部的原则分组(假定分为k组)，每一组函数依赖Fi所涉及的全部属性形成一个属性集Ui。若UiUj(ij)，就去掉Ui。于是=R1，R2，Rk构成R的一个保持函数依赖的分解，并且每个Ri(Ui,Fi)均属于3NF且保持函数依赖。,.,23,3.9.4模式分解算法,例，设R（A,B,C,D,E），Fmin=AB，CD。则，R1（A,B)，R2（C,D）,R3（E）是保持函数依赖的分解。,.,24,算法4转换为3NF既有无损连接性又保持函数依赖的分解。（1）对关系模式R中的函数依赖集F进行“极小化”处理，然后把最小依赖集中那些左部相同的FD用合并性合并起来，处理后的函数依赖集仍记为F；（2）对F中的每个一函数依赖XY，构成一个关系模式Ri(X,Y)，Ri为3NF,R1,R2,Rn（3）如果每个Ri不包含R的候选键，那么把候选键作为一个模式放入中。即为所求。,3.9.4模式分解算法,.,25,例，设有关系R(F,G,H,I,J)，FD=FI,JI,IG,GHI,IHF，将分解为3NF,并具有无损连接性和保持依赖性。解：HJ是L类属性，所以候选键至少包含HJ，另外，(HJ)FGHIJ，所以HJ是唯一的候选键。（1）求出最小依赖集Fmin=F=FI,JI,IG,GHI,IHF,3.9.4模式分解算法,.,26,(2)将关系分解为：R1(FI),R2(JI),R3(IG),R4(GHI),R5(IHF)(3)并上候选键：R1（FI）,R2(JI),R3(IG),R4(GHI),R5(IHF)，R6（HJ）,3.9.4模式分解算法,.,27,3.9.4模式分解算法,课后习题：已知，关系模式R(A,B,C,D,E)，R的最小依赖集Fmin=AB，CD。试将R分解为3NF,并具有无损连接性和保持函数依赖性。,.,28,3.9.4模式分解算法,算法5转换为BCNF的无损连接分解。(1)关系模式R的分解，初始时=R。(2)检查中各关系模式是否均属于BCNF。若是，则算法终止。(3)设中Ri不属于BCNF，那么必有XAFi(AX)，且X非Ri的超码。对Ri进行分解：S1,S2，US1XA，US2UiA，以代替Ri返回第(2)步。由于U中属性有限，因而有限次循环后算法5一定会终止。,.,29,算法5转换为BCNF的无损连接分解。,这是一个自项向下的算法。它自然地形成一棵对R的二又分解树。R的分解树不一定是唯一的。这与步骤(3)中具体选定的XA有关。,.,30,算法5转换为BCNF的无损连接分解。,例，设关系模式W(CTHRSG)的属性分别表示课程名、任课教师名、上课时间、上课教室、选修的学生学号、成绩等含义。W上的函数依赖集F：CT，HRC，THR，CSG，HSR显然，模式W上只有一个键，是HS。解：要把W分解成BCNF模式集，可以首先考虑CSG，据算法，应把CTHRSG分解成CSG和CTHRS。为进一步分解，计算出CSG(F)CSG，CTHRS(F)CT，HRC，THR，HSR。模式CTHRS的键是HS。,.,31,算法5转换为BCNF的无损连接分解。,显然CSG已是BCNF，而CTHRS必须进一步分解。如考虑CT，则把CTHRS分解成CT和CHRS，CT(F)CT，CHRS(F)CHR，HSR，HRC。HS是CHRS的键。CHRS再分解一次，利用CHR分解成CHR和CHS，2模式均满足BCNF。分解结束。,.,32,分解树,.,33,算法5转换为BCNF的无损连接分解。,W分解成CSG，CT，CHR，CHS，其中四个关系模式分别描述：学生的各门课程成绩(CSG)每门课程的任课教师(CT)每门课程的上课时间和教室(CHR)每个学生的上课时间表(CHS)是转换为BCNF的无损连接分解，但分解中有一个问题，THR在分解时未能保持。在CTHRS分解成CT和CHRS时，THR丢失了。,.,34,3.9.4模式分解算法,算法6达到4NF的具有无损连接性的分解首先使用算法5得到R的一个达到了BCNF的无损连接分解。然后对某一Ri，若不属于4NF，则可按下述定理的作法进行分解。直到每个关系模式均属于4NF为止。定理若R中XY成立，则R的分解=R1(X,Y),R2(X,Z)具有无损连接性。其中ZUXY。,.,35,算法6达到4NF的具有无损连接性的分解,例，TEACHING(C,T,B)的码是A1l_Key。TEACHINGBCNF，但TEACHING4NF将模式TEACHING分解为：CT(C,T)和CB(C,B)，均满足4NF,.,36,数据依赖的一个有效且完备的公理系统,关系模式R，U是属性总体集，D是U上的一组数据依赖(函数依赖和多值依赖)，对于包含函数依赖和多值依赖的数据依赖有个有效且完备的公理系统。A1：若YXU，则XY；A2：若XY为F所蕴含，且ZU，则XZYZ。A3：若XY，YZ，则XZA4：若XY，VWU，则XWYVA5：若XY，则XUXYA6：若XY，YZ，则XZY,.,37,A7：若XY，则XYA8：若XY，WZ，WY，ZY，则XZ。公理系统的有效性是指从D出发根据8条公理推导出的函数依赖或多值依赖一定为D蕴含；完备性是指凡D所蕴含的函数依赖或多值依赖均可以从D根据8条公理推导出来。也就是说，在函数依赖和多值依赖的条件下，“蕴含”与“导出”仍是等价的。,数据依赖的一个有效且完备的公理系统,.,38,3.9.5模式分解小结,关于模式分解的几个重要事实：（1）若要求分解保持函数依赖，那么分解总可以达到3NF，但不一定能达到BCNF。（2）若要求分解既保持函数依赖，又具有无损连接性，可以达到3NF，但不一定能达到BCNF。（3）若要求分解具有无损连接性，那一定