数据库,模式的分解,无损连接性,教案

3.9（关系）模式的分解分解的定义：关系模式RU，F的一个分解是指ρ＝{R1U1，F1，R2U2，F2，…，RnUn，Fn}其中U＝U1∪U2∪…∪Un，并且不存在UiUj,1≤i,j≤n，Fi是F在Ui上的投影。函数依赖集合{X→Y|X→Y∈F＋∧XYUi}的一个覆盖(等价)Fi叫做F在属性Ui上的投影。3.9模式的分解3.9.1关系模式分解的标准•把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的•只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义“等价”概念的三种定义：（1）分解具有无损连接性。（2）分解要保持函数依赖性。（3）分解既要保持函数依赖，又要具有无损连接性。3.9.2无损分解无损分解定义：关系模式RU,F的一个分解ρ={R1U1,F1，R2U2,F2，…，RnUn,Fn}，对于R的任一关系r，都有r为其在各Ui(1=1,…,n)上的投影的(自然)连接,即r=πU1(r)⋈πU2(r)⋈…⋈πUn(r)，则称关系模式R的这个分解ρ具有无损连接性（Losslessjoin）。•具有无损连接性的分解保证不丢失信息。•无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。3.9.2无损分解（续）例：S-L（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}S-L∈2NF，分解方法可以有多种：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)3.9.2无损分解（续）第3种分解方法具有无损连接性。问题:（1）没有保持原关系中的函数依赖，即S-L中的函数依赖Sdept→Sloc没有投影到关系模式ND、NL上。（2）存在冗余和操作异常。3.9.2无损分解（续）4.将SL分解为下面二个关系模式：ND(Sno,Sdept)，DL(Sdept,Sloc)该分解保持了函数依赖(且具有无损连接性)。3.9.3保持函数依赖的模式分解定义：设关系模式RU,F被分解为若干个关系模式R1U1,F1，R2U2,F2，…，RnUn,Fn其中U=U1∪U2∪…∪Un，且不存在UiUj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的（Preservedependency）。3.9.3保持函数依赖的模式分解（续）例如，将S－L（Sno，Sdept，Sloc）F={Sno→Sdept,Sdept→Sloc,Sno→Sloc}分解为下面二个关系模式(第四种分解)：ND(Sno,Sdept)，DL(Sdept,Sloc)该分解保持了函数依赖(具有无损连接性)。3.9.3保持函数依赖的模式分解(续)•如果一个分解具有无损连接性，则它能够保证不丢失信息。•如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。•分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖；同样，保持函数依赖的分解也不一定具有无损连接性。3.9.3保持函数依赖的模式分解(续)对于关系模式S-L：•第1种分解方法既不具有无损连接性，也未保持函数依赖。•第2种分解方法未保持函数依赖，也不具有无损连接性。•第3种分解方法具有无损连接性，但未保持函数依赖。•第4种分解方法既具有无损连接性，又保持了函数依赖。3.9.4模式分解算法•算法1判别一个二元分解的无损连接性•算法2判别一个分解的无损连接性•算法3（合成法）转换为3NF的保持函数依赖的分解。•算法4转换为3NF既有无损连接性又保持函数依赖的分解。•算法5（分解法）转换为BCNF的无损连接分解•算法6达到4NF的具有无损连接性的分解。•算法1判别一个二元分解的无损连接性。若F＋中至少存在如下函数依赖中的一个：（1）（U1∩U2）→U1－U2（2）（U1∩U2）→U2－U1则ρ={R1U1，R2U2}是R的无损分解。反之也成立。如：模式S-L（Sno，Sdept，Sloc）分解为2个模式：ND(Sno,Sdept)，NL(Sno,Sloc)则是无损分解。3.9.4模式分解算法算法2判别一个分解的无损连接性设ρ＝{R1U1，F1，R2U2，F2，…，RkUk，Fk}是RU，F的一个分解，U＝{A1,…,An}①构造一张k行n列的表格。每列对应一个属性Aj，每行对应一个模式Ri。如果Aj属于Ui，那么在表格的第i行第j列处填上符号aj，否则填上bij。算法2判别一个分解的无损连接性②逐一检查F中的每个函数依赖，并修改元素，方法是：1、取F中一函数依赖X→Y(从第一个开始，到最后一个取完结束)，2、找出X所对应的列中具有相同符号的行。（如X列中有某两个值均为a3的行,则算是相同的两行，如果是有两个下标的则不是相同符号，如a31）3、考察这些行中Y列的元素，若其中有aj，则全部改为aj，否则全部改bmj，其中m是这些行的行号最小值。4、若在某次更改后，有一行是a1a2…an，那么ρ相对于F是无损分解，算法结束。对F中的每个函数依赖进行一次上述的处置，称对F的一次扫描。算法2判别一个分解的无损连接性③比较扫描前后，表有无变化。如有变化，则返回第②步处理，否则，算法结束，则ρ相对于F是有损分解。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此循环必然会终止。算法2判别一个分解的无损连接性例1，设关系模式R(ABCDE)，F={AB→C，C→D，D→E}，R分解成ρ={R1(ABC),R2(CD),R3(DE)}。那么ρ相对于F是否无损分解？算法2判别一个分解的无损连接性R1(ABC),R2(CD),R3(DE)F={AB→C，C→D，D→E}ABCDEa1a2a3b14b15b21b22a3a4b25b31b32b33a4a5ABCDEa1a2a3a4a5b21b22a3a4a5b31b32b33a4a5初始表：最后结果：R1R2R3R1R2R3122ρ相对于F是无损分解算法2判别一个分解的无损连接性例2，R(A，B，C)，F={AB，CB}–分解ρ1={R1(A,B)，R2(A,C)}–分解ρ2={R1(A,B)，R1(B,C)}分析两种分解的无损连接性？–分解1只具有无损连接性,分解2不具有无损连接性。ABCa1a2a1a2a3ABACABCa1a2a2a3ABBC算法2判别一个分解的无损连接性例3，设关系模式R(ABCD)，R分解成ρ={R1(AB),R2(BC),R3(CD)}。如果R上成立的函数依赖集F={A→B，C→D}，那么ρ相对于F是否无损分解？算法2判别一个分解的无损连接性F={A→B，C→D}ABCDABa1a2b13b14BCb21a2a3b24CDb31b32a3a4ρ是有损分解ABCDABa1a2b13b14BCb21a2a3a4CDb31b32a3a43.9.4模式分解算法算法3（合成法）转换为3NF的保持函数依赖的分解。（1）对关系模式R中的函数依赖集F进行“极小化”处理，处理后的函数依赖集仍记为F；（2）若有X→AF，且XA=U，则ρ={R}，算法终止；（3）找出不在F中出现的属性，将它们构成一个关系模式，并把这些属性从R中去掉，把剩余的属性仍记为U。算法3转换为3NF的保持函数依赖的分解（4）对F按具有相同左部的原则分组(假定分为k组)，每一组函数依赖Fi所涉及的全部属性形成一个属性集Ui。若UiUj(i≠j)，就去掉Ui。于是ρ={R1U1，F1，R2U2，F2，…，RkUk，Fk}构成RU，F的一个保持函数依赖的分解，并且每个Ri(Ui,Fi)均属于3NF且保持函数依赖。3.9.4模式分解算法例，设R（A,B,C,D,E），Fmin={A→B，C→D}。则，ρ＝{R1（A,B)，R2（C,D）,R3（E）}是保持函数依赖的分解。算法4转换为3NF既有无损连接性又保持函数依赖的分解。（1）对关系模式R中的函数依赖集F进行“极小化”处理，然后把最小依赖集中那些左部相同的FD用合并性合并起来，处理后的函数依赖集仍记为F；（2）对F中的每个一函数依赖X→Y，构成一个关系模式Ri(X,Y)，Ri为3NF,ρ＝{R1,R2,…,Rn}（3）如果每个Ri不包含R的候选键，那么把候选键作为一个模式放入ρ中。ρ即为所求。3.9.4模式分解算法例，设有关系R(F,G,H,I,J)，FD={F→I,J→I,I→G,GH→I,IH→F}，将分解为3NF,并具有无损连接性和保持依赖性。解：HJ是L类属性，所以候选键至少包含HJ，另外，(HJ)＋＝{FGHIJ}，所以HJ是唯一的候选键。（1）求出最小依赖集Fmin=F={F→I,J→I,I→G,GH→I,IH→F}3.9.4模式分解算法(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模式分解算法3.9.4模式分解算法课后习题：已知，关系模式R(A,B,C,D,E)，R的最小依赖集Fmin={A→B，C→D}。试将R分解为3NF,并具有无损连接性和保持函数依赖性。3.9.4模式分解算法算法5转换为BCNF的无损连接分解。(1)关系模式R的分解ρ，初始时ρ={RU,F}。(2)检查ρ中各关系模式是否均属于BCNF。若是，则算法终止。(3)设ρ中RiUi,Fi不属于BCNF，那么必有X→AFi＋(AX)，且X非Ri的超码。对Ri进行分解：σ＝{S1,S2}，US1＝XA，US2＝Ui－{A}，以σ代替RiUi,Fi返回第(2)步。由于U中属性有限，因而有限次循环后算法5一定会终止。算法5转换为BCNF的无损连接分解。这是一个自项向下的算法。它自然地形成一棵对RU,F的二又分解树。RU,F的分解树不一定是唯一的。这与步骤(3)中具体选定的X→A有关。算法5转换为BCNF的无损连接分解。例，设关系模式W(CTHRSG)的属性分别表示课程名、任课教师名、上课时间、上课教室、选修的学生学号、成绩等含义。W上的函数依赖集F：{C→T，HR→C，TH→R，CS→G，HS→R}显然，模式W上只有一个键，是HS。解：要把W分解成BCNF模式集，可以首先考虑CS→G，据算法，应把CTHRSG分解成CSG和CTHRS。为进一步分解，计算出πCSG(F)＝{CS→G}，πCTHRS(F)＝{C→T，HR→C，TH→R，HS→R}。模式CTHRS的键是HS。算法5转换为BCNF的无损连接分解。显然CSG已是BCNF，而CTHRS必须进一步分解。如考虑C→T，则把CTHRS分解成CT和CHRS，πCT(F)＝{C→T}，πCHRS(F)＝{CH→R，HS→R，HR→C}。HS是CHRS的键。CHRS再分解一次，利用CH→R分解成CHR和CHS，2模式均满足BCNF。分解结束。分解树算法5转换为BCNF的无损连接分解。W分解成ρ＝{CSG，CT，CHR，CHS}，其中四个关系模式分别描述：①学生的各门课程成绩(CSG)②每门课程的任课教师(CT)③每门课程的上课时间和教室(CHR)④每个学生的上课时间表(CHS)ρ是转换为BCNF的无损连接分解，但分解中有一个问题，TH→R在分解时未能保持。在CTHRS分解成CT和CHRS时，TH→R丢失了。3.9.4模式分解算法算法6达到4NF的具有无损连接性的分解首先使用算法5得到R的一个达到了BCNF的无损连接分解ρ。然后对某一RiUi,Di，若不属于4NF，则可按下述定理的作法进行分解。直到每个关系模式均属于4N