《关系模式分解》PPT课件.ppt

2020/6/4,南晓数信学院,1,第3讲关系模式的分解,授课人：李朔Email:chn.nj.ls,2020/6/4,南晓数信学院,2,主要内容,模式分解无损联接分解保持函数依赖集,2020/6/4,南晓数信学院,3,设有关系模式R(U,F)，F是R的函数依赖集，Z是U的子集，则把F中所有满足XYZ的函数依赖XY组成的集合，称为依赖集F在属性集Z上的投影，记为Z(F)：Z(F)XY|XYF且XYZ,1、F在Ui上的投影,2020/6/4,南晓数信学院,4,R(U,F),U=U1U2Uk,对于任意的i,j(1i,jk)，不成立UiUj,Fi是F在Ui上的投影,=R1(U1,F1),R2(U2,F2),Rk(Uk,Fk),一、模式分解,2、分解定义P109,2020/6/4,南晓数信学院,5,经过不适当的分解后再连接，将恢复不了原来信息,2020/6/4,南晓数信学院,6,关系模式分解例：,关系模式：学生（学号，系别，系主任）函数依赖集：F=学号系别，系别-系主任分解1：1=R1(学号)，R2(系别)，R3(系主任)不能连接为原关系实例F1=F2=F3=，函数依赖不保持,2020/6/4,南晓数信学院,7,分解22=P(学号，系别)，R(学号，系主任)F1=学号系别，F2=学号系主任能连接为原关系实例，但依赖约束不能恢复（系别系主任）分解33=P(学号，系属)，R(系属，主任)F1=学号系属，F2=系属主任既能连接为原关系，又能保持函数依赖约束,2020/6/4,南晓数信学院,8,两个问题：,思考：,？,R(U),R1(U1),R2(U2),Rk(Uk),？,数据等价,依赖（语义）等价,无损联接,保持依赖,2020/6/4,南晓数信学院,9,二、无损联接分解,2020/6/4,南晓数信学院,10,二、无损联接分解,1、定义设有关系模式R(U,F)，=（R1,R2,Rk）是R的一个分解。如果对于R的任一满足F的关系r，把r在上的投影的联接表达式记为：m(r)R1(r)R2(r)Rk(r)如果rm(r)成立，则称这个分解是满足依赖集F的无损联接分解。(通过自然连接可还原关系r,一个不少,一个不多),2020/6/4,南晓数信学院,11,输入：关系模式R(A1,An)，函数依赖集F，R的一个分解(R1,Rk)。输出：是否为无损联接的判断。方法:,2、算法5.2判断一个分解的无损联接性,2020/6/4,南晓数信学院,12,si,j,Aj在Ri中,aj,Aj不在Ri中,bij,（1）构造一个k行n列表S，其中：,2、算法5.2判断一个分解的无损联接性（续1）,2020/6/4,南晓数信学院,13,（2）依据函数依赖集F进行修正：XY,若Y值中有aj，其它也改为aj若Y值中无aj，其它改为bij（下标小）,FD的选择顺序可随意,2、算法5.2判断一个分解的无损联接性（续2）,2020/6/4,南晓数信学院,14,分解具有无损联接性,（3）判断条件：,2、算法5.2判断一个分解的无损联接性（续3）,2020/6/4,南晓数信学院,15,第一步：构造表S,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,16,第二步：修正AC,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,17,第二步：修正AC(注意:此时表式,R1,R2,R5自然联接,刚A属性值相同,若有C属性，则值一定相同,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,18,第二步：修正BC,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,19,第二步：修正BC,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,20,第二步：修正CD,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,21,第二步：修正CD,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,22,第二步：修正DEC,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,23,第二步：修正DEC,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,24,第二步：修正CEA,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,25,第二步：修正CEA,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,26,第三步：判断,分解具有无损联接性,例5.7设R(ABCDE)，F=AC，BC，CD，DEC，CEA，=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,27,*补充：关系分解无损连接性判别算法的正确性证明,引理1算法5.2的初始矩阵有性质:任取j,第j行对Rj的投影元素全是a.（事实上，这是由算法的初始化步骤所决定的。）引理2执行算法5.2过程中,矩阵的每个符号a不可能变为其它符号.（因算法规则是若列含a则全列改为a,否则全列取为最小行标）,2020/6/4,南晓数信学院,28,引理3算法5.2终止矩阵有性质:任意j,第j行对Rj的投映元素全是a.(事实上，这由引理1和引理2所决定)引理4算法5.2的终止矩阵作为关系实例必然满足函数依赖集F.（事实上,算法的实质是检查初始矩阵作为关系实例是否满足F的每个函数依赖.若不满足某个函数依赖,则修改相关元素,使矩阵满足这个函数依赖,故终止矩阵必满足F.）,2020/6/4,南晓数信学院,29,定理1关系R的分解具无损连接性的充要条件是算法5.2的终止矩阵r有一行的符号全是a.证明必要性:若终止矩阵无全a的行,断言不具无损连接性.一方面,由引理4,终止矩阵r必满足函数依赖集F,且无全a的行.另一方面,由引理3,终止矩阵r的第j行对Rj的投映元素全是a(任取j),故M(r)=R1(r).Rk(r)必含全a行.故rM(r).故断言真证明充分性:若终止矩阵有一行全a,往证具无损连接性.（),2020/6/4,南晓数信学院,30,设有关系模式R(U,F)，F是R的属性集U上的函数依赖集，=（R1,R2）是R的一个分解，当且仅当（R1R2）（R1-R2）或（R1R2）（R2-R1）属于F+时，具有无损联接性。,3、判断定理,2020/6/4,南晓数信学院,31,证：充分性(R1R2)(R1-R2)或(R1R2)(R2-R1)成立,aaa,aaa,aaa,aaa,bbb,bbb,F,3、判断定理（续1）,2020/6/4,南晓数信学院,32,证：充分性(R1R2)(R1-R2)或(R1R2)(R2-R1)成立,aaa,aaa,aaa,aaa,bbb,F,aaa,3、判断定理（续2）,2020/6/4,南晓数信学院,33,证：充分性(R1R2)(R1-R2)或(R1R2)(R2-R1)成立,aaa,aaa,aaa,aaa,bbb,bbb,F+,3、判断定理（续3）,2020/6/4,南晓数信学院,34,证：充分性(R1R2)(R1-R2)或(R1R2)(R2-R1)成立,aaa,aaa,aaa,aaa,bbb,F+,aaa,具有无损联接性,3、判断定理（续4）,2020/6/4,南晓数信学院,35,（R1R2）（R1-R2）,证：必要性,3、判断定理（续5）,2020/6/4,南晓数信学院,36,（R1R2）（R2-R1）,证：必要性,3、判断定理（续6）,2020/6/4,南晓数信学院,37,分解不具有无损联接性,举例：,例5.8设有关系模式R(A,B,C)，函数依赖集F=AB，CB，分解=R1,R2，其中R1=AB，R2=BC。检验分解是否具有无损联接性。,2020/6/4,南晓数信学院,38,三、保持函数依赖集,2020/6/4,南晓数信学院,39,1、定义,设有关系模式R(U,F)，F是R的函数依赖集，R1,R2,Rk是R上的一个分解。如果所有函数依赖集Ri(F)（i=1，2，,k）的并集逻辑蕴含F中的每一个函数依赖，则称分解具有依赖保持性，也即分解保持依赖集F。即,2020/6/4,南晓数信学院,40,令G=，验证G=F?,2、保持依赖的判断方法,实质是看：Y在G中是否仍被X约束着？,2020/6/4,南晓数信学院,41,例：设有关系模式R(A,B,C,D,E,P)，R的函数依赖集F=CP,ECD,EA,AB。当将R分解成R1(CP),R2(AE),R3(CDE),R4(BCE)时，判断该分解是否保持依赖性？R1(F)=CPR2(F)=EAR3(F)=ECDR4(F)=EB,无法导出AB,该分解不保持依赖性,举例：,2020/6/4,南晓数信学院,42,小结,两个数据库模式的等价性问题,R(U,F),=R1(U1,F1),R2(U2,F2),Rk(Uk,Fk),注意,