单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6.4 模式的分解,模式分解的定义,无损连接分解,保持函数依赖的分解,模式分解的算法,关系模式R的一个分解是指,=R1,R2,Rn,其中U=U1U2Un，并且没有Ui Uj,ij，,Fi是F在Ui上的投影。,F在Ui上的投影记作Ui F是指,函数依赖集合XY|XYF+XYUi的一个覆盖Fi。,例1:R,UA,B,C,D,F=A-BD,D-C,如果将R分解为R1(U1,F1)和R2(U2,F2),其中U1=A,B,D,U2=A,C,那么F1,F2分别是？,一、关系模式分解的定义,一个模式的分解是多种多样的，但是分解后产生的模式应与原模式等价。,对“等价的三种定义：,分解具有“无损连接性；,分解要“保持函数依赖；,分解既具有“无损连接性，又“保持函数依赖。,例2：关系模式R,其中,USno,Sdept,Sloc,F=Sno-Sdept,Sdept-Sloc.,分析R属于？NF，并分析R的各种模式分解方法。,Sno,Sdept,Sloc,99001,计算机,D1,99002,电信,D2,99003,自控,D3,99004,电信,D2,99005,管理,D2,表1：R的一个关系r,1.分解1：R1、R2、R3,分解后的DB无法恢复到原来的情况。,2.分解2：,R1 R2,Sno,Sdept,Sno,Sloc,99001,计算机,99001,D1,99002,电信,99002,D2,99003,自控,99003,D3,99004,电信,99004,D2,99005,管理,99005,D2,Sno,Sdept,Sloc,99001,计算机,D1,99002,电信,D2,99003,自控,D3,99004,电信,D2,99005,管理,D2,表1：R的一个关系r,分解后可以恢复，,但仍然存在插入和删除异常。,3.分解3：,R1 R2,Sno,Sdept,Sdept,Sloc,99001,计算机,计算机,D1,99002,电信,电信,D2,99003,自控,自控,D3,99004,电信,管理,D2,99005,管理,Sno,Sdept,Sloc,99001,计算机,D1,99002,电信,D2,99003,自控,D3,99004,电信,D2,99005,管理,D2,表1：R的一个关系r,分解可恢复，,并且解决了异常。,二、无损连接的分解,引入一个记号：设=R1,R2,Rk 是R的一个分解，r是R的一个关系。定义m(r)=,即m(r)是r在中各关系模式上投影的自然连接。,定义：=R1,Rk是R的一个分解.假设对R的任一关系r都有r=m(r)，那么称具有无损连接性。简称为无损分解。,k,i=,1,Ri,(r),判断一个分解是否具有无损连接性,方法一：,定理：R的一个分解=R1,R2,具有无损连接性的充要条件是,(U1U2)(U1-U2)F+,或(U1U2)(U2-U1)F+证明从略。,例3:R,U=A,B,C,F=AB,CB。,分解1=AB,BC、分解2=AC,BC是否具备无损连接性？,例4：R,U=ABCDEF,F=AB,CF,EA,CED,=R1(ABE),R2(CDEF)是否具备无损连接性？,=R1,RK是R的一个分解，U=A1,An,F=FD1,FDm，并设F是一极小依赖集，,记FDi为 XiAli,1建立一个n列k行的表。每列对应一个属性Aj，每行对应一个子关系模式的属性集Ui。假设Aj属于Ui，那么在第i行j列交叉处填上aj，否那么填上bij；,2对每个FDi做如下操作：找到Xi所对应的列中具有相同符号的那些行，考察这些行中li列的元素，假设其中有ali那么全部改为ali，否那么全部改为bmli；m是这些行的行号最小值假设某个btli被更动，那么该表的li列中但凡btli的符号均作相应更改。,假设有一行成为a1，an。那么算法终止，分解具备无损连接性。,对F中个FD逐一进行上述处理，称为对F的一次扫描。,3比较扫描前后，假设表有变化，那么返回2；假设表无变化，那么算法终止，分解不具备无损连接性。,判断一个分解是否具有无损连接性,方法二,：,例5：R,U=A,B,C,D,E,F=AB-C,C-D,D-E,R的一个分解为R1(A,B,C),R2(C,D),R3(D,E)。判断此分解是否具备无损连接性。,例6：设有关系模式R,U=E,G,H,I,J,F=E-I,J-I,I-G,GH-I,IH-E,判断=EG,EJ,JH,IGH,EH 是否为无损连接分解。,三、保持函数依赖的分解,定义:设=R1,Rk是R的一,个分解，假设 ,那么保持函数依赖。,其中FiUi F.,例7:R,U=A,B,C,F=AB，CB,判断1=AC,AB是否具有依赖保持性？,例8:R,U=ABCDEF,F=AB,EA,CF,CED，判断2=ABE,CDEF是否具有依赖保持性？,四、模式分解的算法,算法1合成法)：,将R分解为3NF并保持函数依赖的算法,对R中的函数依赖集F进行极小化处理处理后的结果仍记为F；,找出不在F中出现的属性，把它们构成一个关系模式。并把这些属性从U中去掉剩余的属性仍记为U；,假设XAF且XA=U,那么=R，算法终止；,否那么，对F按具有相同左部的原那么分组，每组函数依赖Fi所涉及的全部属性形成一个属性集Ui；假设 Ui包含于Uj就去掉Ui。,停止，是3NF且具有依赖保持性。,例9：R,U=C,T,H,I,S,G，,最小集F=CT,CSG,HTI,HI C,HSI，,将R分解为3NF且具有函数依赖保持性。,设X是R的码。R由算法1分解为=R1,R2,Rn，令 R*,假设有某个Ui,X Ui,将R*从中去掉。,即为所求。,算法2：,分解为3NF，既具有,无损连接性,又,保持函数依赖,四、模式分解的算法,四、模式分解的算法,算法3分解法：分解为BCNF,且具有无损连接性。,步骤：,令=R,检查：假设中所有关系模式均属于BCNF，那么算法终止。,假设中Ri不属于BCNF,那么必有XAFi+,且X不是Ri的码，显然AX是Ui的真子集。对Ri进行分解:Ri1,Ri2,其中Ui1=XA,Ui2=Ui-A,用分解Ri1,Ri2代替Ri,转,例10：R,U=C,T,H,I,S,G，,最小集F=CT,CSG,HTI,HIC,HSI，,将R分解为BCNF且为无损分解。,作业：,1.对给定的关系模式R,U=A,B,C,D,E,P,F=A-B,C-P,E-A,CE-D,有如下分解：=R1(ABE),R2(CDEP),1)求R的候选码，并判断是否无损,2R1,R2分别属于第几范式,2.关系R(ABCDE)满足以下函数依赖：,F=A-C,C-D,B-C,DE-C,CE-A,1)求R的候选码,2)判断=AD,AB,BC,CDE,AE是否无损连接分解,3)分解R为BCNF，并具有无损连接性,3.设有关系模式R。U=E,G,H,I,J,F=E-I,J-I,I-G,GH-I,IH-E,1)求R的候选码,2)判断=EG,EJ,JH,IGH,EH是否为无损连接分解,3)分解R为3NF，要求具有无损连接性并保持函数依赖,小结,关系模式设计最低要求为,1,NF,范式级别并非越高越好：,大多分解到,3,NF,即可满足要求；,依用户效率、空间、访问特征确定；,一、函数依赖,1.FD定义：假设r中任意两个元组t，s，如果tx=sx导致ty=sy,那么xy。,2.FD的逻辑蕴涵，F+=XY|XY是从F用推理系统推出,3.Armstrong推理系统,自反，假设Y X,那么XY,增广，假设XY 那么XZYZ,传递，假设XY,YZ,那么XZ,推论：,合并，假设XY,XZ,那么XYZ,分解，假设XYZ,那么XY,XZ,伪传递，假设XY,WYZ，那么XWZ,4.key,5.属性闭包 X+,6.FD集的等价，假设F+=G+，那么F与G等价,7.最小FD集Fmin,二、R的标准化,1.1NF,2NF,3NF,BCNF,2.R设计原那么,三、模式分解,1.无损联接性，检验算法。,2.依赖保持性，检验方法。,3.模式分解的算法,