《数据库模式的分解无损连接性学习教案》由会员分享，可在线阅读，更多相关《数据库模式的分解无损连接性学习教案（41页珍藏版）》请在金锄头文库上搜索。
1、会计学1数据库模式数据库模式(msh)的分解无损连接性的分解无损连接性第一页，共41页。3.9 3.9 模式模式(msh)(msh)的分解的分解3.9.1 3.9.1 关系模式分解的标准关系模式分解的标准把低一级的关系模式分解为若干个把低一级的关系模式分解为若干个高一级的关系模式的方法并不是高一级的关系模式的方法并不是唯一的唯一的只有能够只有能够(nnggu)(nnggu)保证分解后的保证分解后的关系模式与原关系模式等价，分关系模式与原关系模式等价，分解方法才有意义解方法才有意义 “ “等价等价”概念的三种定义：概念的三种定义：（1 1）分解具有无损连接性。）分解具有无损连接性。（2 2）分解
2、要保持函数依赖性。）分解要保持函数依赖性。（3 3）分解既要保持函数依赖，又）分解既要保持函数依赖，又要具有无损连接性。要具有无损连接性。第1页/共40页第二页，共41页。3.9.2 3.9.2 无损无损(w sn)(w sn)分解分解 无损分解定义：关系模式无损分解定义：关系模式无损分解定义：关系模式无损分解定义：关系模式RRRR的一个分解的一个分解的一个分解的一个分解 = R1 = R1 = R1 = R1，R2R2R2R2， ，RnRnRnRn，对于，对于，对于，对于R R R R的任一关系的任一关系的任一关系的任一关系r r r r，都有，都有，都有，都有r r r r为其在各为其在各
3、为其在各为其在各Ui(1=1,n)Ui(1=1,n)Ui(1=1,n)Ui(1=1,n)上的投影的上的投影的上的投影的上的投影的( ( ( (自然自然自然自然) ) ) )连接连接连接连接, , , ,即即即即r=U1(r) r=U1(r) r=U1(r) r=U1(r) U2(r) U2(r) U2(r) U2(r) Un(r)Un(r)Un(r)Un(r)，则称关系模式，则称关系模式，则称关系模式，则称关系模式R R R R的这个的这个的这个的这个(zh ge)(zh ge)(zh ge)(zh ge)分解分解分解分解具有具有具有具有无损连接性（无损连接性（无损连接性（无损连接性（Loss
4、less joinLossless joinLossless joinLossless join）。）。）。）。具有无损连接性的分解保证不丢失信息。具有无损连接性的分解保证不丢失信息。具有无损连接性的分解保证不丢失信息。具有无损连接性的分解保证不丢失信息。 无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。第2页/共40页第三页，共41页。3.9.2 3.9.2 无损无损(w
5、 sn)(w sn)分解（续）分解（续） 例：例：S-LS-L（SnoSno， Sdept Sdept， SlocSloc） F= F= SnoSdept,SdeptSloc,SnoSnoSdept,SdeptSloc,SnoSloc S-L2NFSloc S-L2NF，分解分解(fnji)(fnji)方法可以有多种：方法可以有多种： 1. S-L 1. S-L分解分解(fnji)(fnji)为三个关为三个关系模式：系模式： SN(Sno) SN(Sno) ，SD(Sdept)SD(Sdept)，SL(Sloc) SL(Sloc) 2. SL 2. SL分解分解(fnji)(fnji)为下面二
6、为下面二个关系模式：个关系模式： NL(Sno, Sloc) NL(Sno, Sloc)，DL(Sdept, Sloc) DL(Sdept, Sloc) 3. 3. 将将SLSL分解分解(fnji)(fnji)为下面为下面二个关系模式：二个关系模式： ND(Sno, Sdept) ND(Sno, Sdept) ，NL(Sno, Sloc)NL(Sno, Sloc)第3页/共40页第四页，共41页。3.9.2 3.9.2 无损无损(w sn)(w sn)分解（续）分解（续）第第第第3 3 3 3种分解方法具有无损连接性。种分解方法具有无损连接性。种分解方法具有无损连接性。种分解方法具有无损连接性
7、。 问题问题问题问题: : : :（1 1 1 1）没有保持）没有保持）没有保持）没有保持(boch)(boch)(boch)(boch)原关系中的函数依赖，即原关系中的函数依赖，即原关系中的函数依赖，即原关系中的函数依赖，即S-LS-LS-LS-L中的函数依赖中的函数依赖中的函数依赖中的函数依赖SdeptSlocSdeptSlocSdeptSlocSdeptSloc没有投影到关系模没有投影到关系模没有投影到关系模没有投影到关系模式式式式NDNDNDND、NLNLNLNL上。上。上。上。（2 2 2 2）存在冗余和操作异常。）存在冗余和操作异常。）存在冗余和操作异常。）存在冗余和操作异常。 第
8、4页/共40页第五页，共41页。3.9.2 3.9.2 无损无损(w (w sn)sn)分解（续）分解（续）4. 将SL分解为下面二个关系模式： ND(Sno, Sdept) ， DL(Sdept, Sloc) 该分解保持了函数依赖(yli)(且具有无损连接性)。第5页/共40页第六页，共41页。3.9.3 3.9.3 保持函数依赖保持函数依赖(yli)(yli)的的模式分解模式分解 定义：设关系模式定义：设关系模式RR被分解被分解为若干个关系模式为若干个关系模式 R1 R1，R2R2，Rn Rn 其其中中U=U1U2UnU=U1U2Un，且不存在，且不存在Ui Ui Uj Uj，FiFi为为
9、F F在在UiUi上的投影），上的投影），若若F F所逻辑蕴含的函数所逻辑蕴含的函数(hnsh)(hnsh)依赖一定也由分解得到的某个关依赖一定也由分解得到的某个关系模式中的函数系模式中的函数(hnsh)(hnsh)依赖依赖FiFi所逻辑蕴含，则称关系模式所逻辑蕴含，则称关系模式R R的的这个分解是保持函数这个分解是保持函数(hnsh)(hnsh)依依赖的（赖的（Preserve dependencyPreserve dependency）。）。 第6页/共40页第七页，共41页。3.9.3 3.9.3 3.9.3 3.9.3 保持函数依赖的模式保持函数依赖的模式保持函数依赖的模式保持函数依赖
10、的模式(msh)(msh)(msh)(msh)分分分分解（续）解（续）解（续）解（续） 例如，将例如，将S SL L（SnoSno， Sdept Sdept， SlocSloc） F= F= SnoSdept,SdeptSloc,SnoSSnoSdept,SdeptSloc,SnoSlocloc 分解为下面二个关系模式分解为下面二个关系模式( (第四第四种分解种分解) )： ND(Sno, Sdept) ND(Sno, Sdept) ， DL(Sdept, Sloc) DL(Sdept, Sloc) 该分解保持了函数该分解保持了函数(hnsh)(hnsh)依依赖赖( (具有无损连接性具有无损连
11、接性) )。第7页/共40页第八页，共41页。3.9.3 3.9.3 3.9.3 3.9.3 保持函数依赖保持函数依赖保持函数依赖保持函数依赖(yli)(yli)(yli)(yli)的模式分的模式分的模式分的模式分解解解解( ( ( (续续续续) ) ) )n n如果一个分解具有无损连接性，如果一个分解具有无损连接性，则它能够则它能够(nnggu)(nnggu)保证不丢失保证不丢失信息。信息。n n如果一个分解保持了函数依赖，如果一个分解保持了函数依赖，则它可以减轻或解决各种异常则它可以减轻或解决各种异常情况。情况。n n分解具有无损连接性和分解保分解具有无损连接性和分解保持函数依赖是两个互相
12、独立的持函数依赖是两个互相独立的标准。具有无损连接性的分解标准。具有无损连接性的分解不一定能够不一定能够(nnggu)(nnggu)保持函数保持函数依赖；同样，保持函数依赖的依赖；同样，保持函数依赖的分解也不一定具有无损连接性。分解也不一定具有无损连接性。第8页/共40页第九页，共41页。3.9.3 3.9.3 3.9.3 3.9.3 保持保持保持保持(boch)(boch)(boch)(boch)函数依赖的模式分解函数依赖的模式分解函数依赖的模式分解函数依赖的模式分解( ( ( (续续续续) ) ) ) 对于对于(duy)(duy)关系模式关系模式S-LS-L：第第1 1种分解方法既不具有无
13、损连接种分解方法既不具有无损连接性，也未保持函数依赖。性，也未保持函数依赖。 第第2 2种分解方法未保持函数依赖，种分解方法未保持函数依赖，也不具有无损连接性。也不具有无损连接性。 第第3 3种分解方法具有无损连接性，种分解方法具有无损连接性，但未保持函数依赖。但未保持函数依赖。第第4 4种分解方法既具有无损连接性，种分解方法既具有无损连接性，又保持了函数依赖。又保持了函数依赖。第9页/共40页第十页，共41页。3.9.4 3.9.4 模式模式(msh)(msh)分解算法分解算法n n算法算法1 1 判别一个二元分解的无损连接性判别一个二元分解的无损连接性 n n算法算法2 2 判别一个分解的
14、无损连接性判别一个分解的无损连接性 n n算法算法3 3（合成法）转换为（合成法）转换为3NF3NF的保持函数的保持函数(hnsh)(hnsh)依赖的分解。依赖的分解。 n n算法算法4 4 转换为转换为3NF3NF既有无损连接性又保持函既有无损连接性又保持函数数(hnsh)(hnsh)依赖的分解依赖的分解 。n n算法算法5 5 （分解法）转换为（分解法）转换为BCNFBCNF的无损连接分的无损连接分解解 n n算法算法6 6 达到达到4NF4NF的具有无损连接性的分解。的具有无损连接性的分解。第10页/共40页第十一页，共41页。n n算法算法(sun f)1 (sun f)1 判别一个二
15、判别一个二元分解的无损连接性。元分解的无损连接性。n n若若F F中至少存在如下函数依赖中至少存在如下函数依赖中的一个：中的一个：n n（1 1）（）（U1U2U1U2）U1U1U2U2n n（2 2）（）（U1U2U1U2）U2U2U1U1n n 则则= R1= R1，R2R2是是R R的无损分解。反之也的无损分解。反之也n n 成立。成立。n n 如：模式如：模式S-LS-L（SnoSno， Sdept Sdept， SlocSloc）n n 分解为分解为2 2个模式：个模式：n n ND(Sno, Sdept) ND(Sno, Sdept) ，NL(Sno, Sloc) NL(Sno,
16、Sloc) n n 则是无损分解。则是无损分解。 3.9.4 3.9.4 模式模式(msh)(msh)分解算法分解算法第11页/共40页第十二页，共41页。算法算法算法算法(sun f)2 (sun f)2 (sun f)2 (sun f)2 判别一个分解的无损连判别一个分解的无损连判别一个分解的无损连判别一个分解的无损连接性接性接性接性 设设R1U1R1F1，R2U2R2F2，RkUkRkFk是是RURF的一个分解，的一个分解，U UA1, A1, AnAn构造一张构造一张k k行行n n列的表格。每列列的表格。每列对应一个属性对应一个属性AjAj，每行对应一，每行对应一个模式个模式RiRi
17、。如果。如果(rgu)Aj(rgu)Aj属于属于UiUi，那么在表格的第，那么在表格的第i i行第行第j j列列处填上符号处填上符号ajaj，否则填上，否则填上bijbij。第12页/共40页第十三页，共41页。算法算法算法算法2 2 2 2 判别判别判别判别(pnbi)(pnbi)(pnbi)(pnbi)一个分解的无损连接性一个分解的无损连接性一个分解的无损连接性一个分解的无损连接性逐一检查逐一检查F F中的每个函数依赖，中的每个函数依赖，并修改元素，方法是：取并修改元素，方法是：取F F中一中一函数依赖函数依赖XYXY，找出，找出X X所对应的所对应的列中具有相同符号的行，考察这列中具有相
18、同符号的行，考察这些行中些行中Y Y列的元素，若其中有列的元素，若其中有ajaj，则全部改为，则全部改为ajaj，否则全部改，否则全部改bmjbmj，其中，其中m m是这些行的行号最小是这些行的行号最小值。值。 若在某次更改后，有一行是若在某次更改后，有一行是a1a2ana1a2an，那么，那么相对于相对于F F是无是无损分解，算法结束损分解，算法结束(jish)(jish)。 对对F F中的每个函数依赖进行一次中的每个函数依赖进行一次上述的处置，称对上述的处置，称对F F的一次扫描。的一次扫描。第13页/共40页第十四页，共41页。算法算法算法算法2 2 2 2 判别一个分解判别一个分解判别
19、一个分解判别一个分解(fnji)(fnji)(fnji)(fnji)的无损连接性的无损连接性的无损连接性的无损连接性比较扫描前后，表有无变化。如有变化，比较扫描前后，表有无变化。如有变化，比较扫描前后，表有无变化。如有变化，比较扫描前后，表有无变化。如有变化，则返回第则返回第则返回第则返回第步处理，否则，算法结束，则步处理，否则，算法结束，则步处理，否则，算法结束，则步处理，否则，算法结束，则相对于相对于相对于相对于F F F F是有损分解。是有损分解。是有损分解。是有损分解。 如果发生循环，那么前次扫描至少如果发生循环，那么前次扫描至少如果发生循环，那么前次扫描至少如果发生循环，那么前次扫描
20、至少(zhsho)(zhsho)(zhsho)(zhsho)应使该表减少一个符号，表中符应使该表减少一个符号，表中符应使该表减少一个符号，表中符应使该表减少一个符号，表中符号有限，因此循环必然会终止。号有限，因此循环必然会终止。号有限，因此循环必然会终止。号有限，因此循环必然会终止。第14页/共40页第十五页，共41页。算法算法算法算法2 2 2 2 判别一个分解判别一个分解判别一个分解判别一个分解(fnji)(fnji)(fnji)(fnji)的无损连接性的无损连接性的无损连接性的无损连接性 例例例例1 1 1 1，设关系模式，设关系模式，设关系模式，设关系模式R(ABCDE)R(ABCDE
21、)R(ABCDE)R(ABCDE)， F=ABC F=ABC F=ABC F=ABC，CDCDCDCD，DEDEDEDE， R R R R分解成分解成分解成分解成 =R1(ABC), R2(CD),R3(DE) =R1(ABC), R2(CD),R3(DE) =R1(ABC), R2(CD),R3(DE) =R1(ABC), R2(CD),R3(DE)。 那么那么那么那么相对于相对于相对于相对于F F F F是否无损是否无损是否无损是否无损(w sn)(w sn)(w sn)(w sn)分解？分解？分解？分解？第15页/共40页第十六页，共41页。算法算法算法算法2 2 2 2 判别一个判别一
22、个判别一个判别一个(y )(y )(y )(y )分解的无损连分解的无损连分解的无损连分解的无损连接性接性接性接性R1(ABC), R2(CD),R3(DE) R1(ABC), R2(CD),R3(DE) R1(ABC), R2(CD),R3(DE) R1(ABC), R2(CD),R3(DE) F=ABCF=ABCF=ABCF=ABC，CDCDCDCD，DEDEDEDEA AB BC CD DE Ea1a1a2a2a3a3b14b14b15b15b21b21b22b22a3a3a4a4b25b25b31b31b32b32b33b33a4a4a5a5A AB BC CD DE Ea1a1a2a
23、2a3a3a4a4a5a5b21b21b22b22a3a3a4a4a5a5b31b31b32b32b33b33a4a4a5a5初始初始(ch sh)(ch sh)表：表：最后最后(zuhu)(zuhu)结果：结果：R R1 1R2R2R3R3R1R1R2R2R3R31 12 22 2相对于相对于F F是无损分解是无损分解第16页/共40页第十七页，共41页。算法算法算法算法2 2 2 2 判别判别判别判别(pnbi)(pnbi)(pnbi)(pnbi)一个分解的无损连一个分解的无损连一个分解的无损连一个分解的无损连接性接性接性接性 例例2 2，R(AR(A，B B，C)C)， F= A F=
24、AB B，C CBB分解分解(fnji)1=R1(A,B)(fnji)1=R1(A,B)，R2(A,C)R2(A,C)分解分解(fnji)2=R1(A,B)(fnji)2=R1(A,B)，R1(B,C)R1(B,C) 分析两种分解分析两种分解(fnji)(fnji)的无损的无损连接性？连接性？分解分解(fnji)1(fnji)1只具有无损连接性只具有无损连接性, , 分解分解(fnji)2(fnji)2不具有无损连接不具有无损连接性。性。A AB BC Ca1a1a2a2a1a1a2a2a3a3ABABACACA AB BC Ca1a1a2a2a2a2a3a3ABABBCBC第17页/共40页
25、第十八页，共41页。算法算法2 2 判别一个判别一个(y (y )分解的无损连接分解的无损连接性性例例例例3 3 3 3，设关系模式，设关系模式，设关系模式，设关系模式(msh)R(ABCD)(msh)R(ABCD)(msh)R(ABCD)(msh)R(ABCD)，R R R R分解成分解成分解成分解成 =R1(AB), R2(BC),R3(CD) =R1(AB), R2(BC),R3(CD) =R1(AB), R2(BC),R3(CD) =R1(AB), R2(BC),R3(CD)。 如果如果如果如果R R R R上成立的函数依赖集上成立的函数依赖集上成立的函数依赖集上成立的函数依赖集 F=
26、AB F=AB F=AB F=AB，CDCDCDCD， 那么那么那么那么相对于相对于相对于相对于F F F F是否无损分解？是否无损分解？是否无损分解？是否无损分解？第18页/共40页第十九页，共41页。算法算法2 2 判别一个分解判别一个分解(fnji)(fnji)的的无损连接性无损连接性 F=AB F=AB，CDCDA AB BC CD DABABa a1 1a a2 2b b1313b b1414 BCBCb b2121a a2 2a a3 3b b2424 CDCDb b3131b b3232a a3 3a a4 4 是是有损分解有损分解A AB BC CD DABABa a1 1a
27、a2 2b b1313b b1414 BCBCb b2121a a2 2a a3 3a a4 4 CDCDb b3131b b3232a a3 3a a4 4 第19页/共40页第二十页，共41页。3.9.4 3.9.4 模式分解模式分解(fnji)(fnji)算法算法算法算法3 3（合成法）转换为（合成法）转换为3NF3NF的保持的保持函数依赖的分解。函数依赖的分解。（1 1）对关系模式）对关系模式R R中的函数依赖集中的函数依赖集F F进行进行(jnxng)“(jnxng)“极小化极小化”处理，处理，处理后的函数依赖集仍记为处理后的函数依赖集仍记为F F；（2 2）若有）若有XAXA F
28、F，且，且XA=UXA=U，则，则=R=R，算法终止；，算法终止；（3 3）找出不在）找出不在F F中出现的属性，将中出现的属性，将它们构成一个关系模式，并把这它们构成一个关系模式，并把这些属性从些属性从R R中去掉，把剩余的属中去掉，把剩余的属性仍记为性仍记为U U。第20页/共40页第二十一页，共41页。算法算法算法算法(sun f)3 (sun f)3 (sun f)3 (sun f)3 转换为转换为转换为转换为3NF3NF3NF3NF的保持函数依的保持函数依的保持函数依的保持函数依赖的分解赖的分解赖的分解赖的分解（4 4）对）对F F按具有相同左部的原则按具有相同左部的原则(yunz)
29、(yunz)分组分组( (假定分为假定分为k k组组) )，每一组函数依赖每一组函数依赖FiFi所涉及的全部所涉及的全部属性形成一个属性集属性形成一个属性集UiUi。若。若Ui Ui Uj(ij) Uj(ij)，就去掉，就去掉UiUi。于是。于是=R1U1=R1F1，R2U2R2F2，RkUkRk Fk 构成构成RURF的一个保持函数依赖的分解，并的一个保持函数依赖的分解，并且每个且每个Ri(Ui,Fi)Ri(Ui,Fi)均属于均属于3NF3NF且保且保持函数依赖。持函数依赖。第21页/共40页第二十二页，共41页。3.9.4 3.9.4 模式模式(msh)(msh)分解算法分解算法例，设例，
30、设R R（A,B,C,D,EA,B,C,D,E），），Fmin= ABFmin= AB，CDCD。则，则， R1R1（A,B)A,B)，R2R2（C,DC,D）,R3,R3（E E） 是保持是保持(boch)(boch)函数依赖的分解。函数依赖的分解。第22页/共40页第二十三页，共41页。算法算法4 4 转换为转换为3NF3NF既有无损既有无损(w (w sn)sn)连接性又保持函数依赖的连接性又保持函数依赖的分解分解 。 （1 1）对关系模式）对关系模式R R中的函数依中的函数依赖集赖集F F进行进行“极小化极小化”处理，然处理，然后把最小依赖集中那些左部相后把最小依赖集中那些左部相同的同
31、的FDFD用合并性合并起来，处用合并性合并起来，处理后的函数依赖集仍记为理后的函数依赖集仍记为F F；（2 2）对）对F F中的每个一函数依赖中的每个一函数依赖XYXY，构成一个关系模式，构成一个关系模式Ri(X,Y)Ri(X,Y)，RiRi为为3NF,3NF,R1,R2,RnR1,R2,Rn（3 3）如果每个）如果每个RiRi不包含不包含R R的候选的候选键，那么把候选键作为一个模键，那么把候选键作为一个模式放入式放入中。中。 即为所求。即为所求。3.9.4 3.9.4 模式分解模式分解(fnji)(fnji)算法算法第23页/共40页第二十四页，共41页。 例，设有关系例，设有关系R(F,
32、G,H,I,J)R(F,G,H,I,J)，FD=FI,JI,IG,GHI,IHFFD=FI,JI,IG,GHI,IHF，将分，将分解为解为3NF,3NF,并具有无损并具有无损(w sn)(w sn)连接性和保持连接性和保持依赖性。依赖性。 解：解：HJHJ是是L L类属性，所以候选键至少包含类属性，所以候选键至少包含HJHJ，另外，另外，(HJ)(HJ) FGHIJFGHIJ，所以，所以HJHJ是唯是唯一的候选键。一的候选键。 （1 1）求出最小依赖集）求出最小依赖集 Fmin=F=FI,JI,IG,GHI,IHFFmin=F=FI,JI,IG,GHI,IHF3.9.4 3.9.4 模式分解模
33、式分解(fnji)(fnji)算法算法第24页/共40页第二十五页，共41页。 (2) (2) 将关系将关系(gun x)(gun x)分解为：分解为： R1(FI),R2(JI),R3(IG),R4(GHI),R1(FI),R2(JI),R3(IG),R4(GHI),R5(IHF)R5(IHF) (3) (3) 并上候选键：并上候选键： R1R1（FIFI）,R2(JI),R3(IG),R4(G,R2(JI),R3(IG),R4(GHI),R5(IHF)HI),R5(IHF)， R6 R6（HJHJ） 3.9.4 3.9.4 模式模式(msh)(msh)分解算法分解算法第25页/共40页第二
34、十六页，共41页。3.9.4 3.9.4 模式分解模式分解(fnji)(fnji)算法算法 课后习题：课后习题：课后习题：课后习题： 已知，关系模式已知，关系模式已知，关系模式已知，关系模式R(A,B,C,D,E)R(A,B,C,D,E)R(A,B,C,D,E)R(A,B,C,D,E)，R R R R的最小依赖集的最小依赖集的最小依赖集的最小依赖集Fmin=ABFmin=ABFmin=ABFmin=AB，CDCDCDCD。 试将试将试将试将R R R R分解为分解为分解为分解为3NF,3NF,3NF,3NF,并具有并具有并具有并具有(jyu)(jyu)(jyu)(jyu)无损连接性和保持函数无
35、损连接性和保持函数无损连接性和保持函数无损连接性和保持函数依赖性。依赖性。依赖性。依赖性。第26页/共40页第二十七页，共41页。3.9.4 3.9.4 模式分解模式分解(fnji)(fnji)算法算法算法算法5 5 转换为转换为BCNFBCNF的无损连接的无损连接(linji)(linji)分解。分解。(1)(1)关系模式关系模式R R的分解的分解，初始时，初始时=R=R。(2)(2)检查检查中各关系模式是否均属中各关系模式是否均属于于BCNFBCNF。若是，则。若是，则 算法终止。算法终止。(3)(3)设设中中RiRi不属于不属于BCNFBCNF，那么必有那么必有XAXA FiFi ( A
36、 ( A X)X)，且，且X X非非RiRi的超码。对的超码。对RiRi进行分解：进行分解： S1,S2S1,S2，US1US1XAXA，US2US2UiUiAA，以，以代替代替 Ri Ri返回第返回第(2)(2)步。步。 由于由于U U中属性有限，因而有限次中属性有限，因而有限次循环后算法循环后算法5 5一定一定 会终止。会终止。 第27页/共40页第二十八页，共41页。算法算法算法算法5 5 5 5 转换转换转换转换(zhunhun)(zhunhun)(zhunhun)(zhunhun)为为为为BCNFBCNFBCNFBCNF的无损连接分解。的无损连接分解。的无损连接分解。的无损连接分解。
37、 这是一个自项向下的算法。它自然地形成这是一个自项向下的算法。它自然地形成一棵对一棵对RR的二又分解树。的二又分解树。RR的分的分解树不一定是唯一解树不一定是唯一(wi y)(wi y)的。这与步骤的。这与步骤(3)(3)中具体选定的中具体选定的XAXA有关。有关。第28页/共40页第二十九页，共41页。算法算法算法算法(sun f)5 (sun f)5 (sun f)5 (sun f)5 转换为转换为转换为转换为BCNFBCNFBCNFBCNF的无损连接分解。的无损连接分解。的无损连接分解。的无损连接分解。 例，例， 设关系模式设关系模式W(CTHRSG)W(CTHRSG)的的属性分别表示课
38、程名、任课教属性分别表示课程名、任课教师名、上课时间、上课教室、师名、上课时间、上课教室、选修的学生学号、成绩选修的学生学号、成绩(chngj)(chngj)等含义。等含义。W W上的函数上的函数依赖集依赖集F F： C T C T，HR CHR C，THRTHR，CS CS G G，HS RHS R 显然，模式显然，模式W W上只有一个键，上只有一个键，是是HSHS。 解：要把解：要把W W分解成分解成BCNFBCNF模式集，模式集，可以首先考虑可以首先考虑CS GCS G，据算法，据算法，应把应把CTHRSGCTHRSG分解成分解成CSGCSG和和CTHRSCTHRS。为进一步分解，计算出
39、为进一步分解，计算出CSG CSG (F)(F)CS G CS G ， CTHRS CTHRS (F) (F) C TC T，HR CHR C，TH TH R R，HS RHS R。模式。模式CTHRSCTHRS的的键是键是HSHS。 第29页/共40页第三十页，共41页。算法算法算法算法(sun f)5 (sun f)5 (sun f)5 (sun f)5 转换为转换为转换为转换为BCNFBCNFBCNFBCNF的无损连接分解。的无损连接分解。的无损连接分解。的无损连接分解。 显然显然显然显然CSGCSGCSGCSG已是已是已是已是BCNFBCNFBCNFBCNF，而，而，而，而CTHRSC
40、THRSCTHRSCTHRS必须进一步分解。如考虑必须进一步分解。如考虑必须进一步分解。如考虑必须进一步分解。如考虑(kol)CT(kol)CT(kol)CT(kol)CT，则把，则把，则把，则把CTHRSCTHRSCTHRSCTHRS分解成分解成分解成分解成CTCTCTCT和和和和CHRSCHRSCHRSCHRS， CT (F) CT (F) CT (F) CT (F) C C C C TTTT， CHRS (F) CHRS (F) CHRS (F) CHRS (F) CH RCH RCH RCH R，HS RHS RHS RHS R，HR CHR CHR CHR C。HSHSHSHS是是是
41、是CHRSCHRSCHRSCHRS的键。的键。的键。的键。 CHRS CHRS CHRS CHRS再分解一次，利用再分解一次，利用再分解一次，利用再分解一次，利用CHRCHRCHRCHR分解成分解成分解成分解成CHRCHRCHRCHR和和和和CHSCHSCHSCHS，2 2 2 2模式均满足模式均满足模式均满足模式均满足BCNFBCNFBCNFBCNF。 分解结束。分解结束。分解结束。分解结束。第30页/共40页第三十一页，共41页。分解分解(fnji)(fnji)树树第31页/共40页第三十二页，共41页。算法算法算法算法5 5 5 5 转换为转换为转换为转换为BCNFBCNFBCNFBCN
42、F的无损的无损的无损的无损(w sn)(w sn)(w sn)(w sn)连接分解。连接分解。连接分解。连接分解。 W分解成CSG，CT，CHR，CHS，其中四个关系模式分别描述： 学生的各门课程成绩(CSG) 每门课程的任课教师(CT) 每门课程的上课时间(shjin)和教室 (CHR) 每个学生的上课时间(shjin)表(CHS) 是转换为BCNF的无损连接分解，但分解中有一个问题，THR在分解时未能保持。在CTHRS分解成CT和CHRS时， THR丢失了。第32页/共40页第三十三页，共41页。3.9.4 3.9.4 模式模式(msh)(msh)分解算法分解算法算法算法算法算法6 6 6
43、 6 达到达到达到达到4NF4NF4NF4NF的具有无损连接性的分解的具有无损连接性的分解的具有无损连接性的分解的具有无损连接性的分解 首先首先首先首先(shuxin)(shuxin)(shuxin)(shuxin)使用算法使用算法使用算法使用算法5 5 5 5得到得到得到得到R R R R的一个达到的一个达到的一个达到的一个达到了了了了BCNFBCNFBCNFBCNF的无损连接分解的无损连接分解的无损连接分解的无损连接分解。然后对某一。然后对某一。然后对某一。然后对某一Ri Ri Ri Ri ， 若不属于若不属于若不属于若不属于4NF4NF4NF4NF，则可按下述定，则可按下述定，则可按下述
44、定，则可按下述定理的作法进行分解。直到每个关系模式均属理的作法进行分解。直到每个关系模式均属理的作法进行分解。直到每个关系模式均属理的作法进行分解。直到每个关系模式均属于于于于4NF4NF4NF4NF为止。为止。为止。为止。定理定理定理定理 若若若若RRRR中中中中XYXYXYXY成立，则成立，则成立，则成立，则R R R R的分解的分解的分解的分解 =R1(X,Y),R2(X,Z) =R1(X,Y),R2(X,Z) =R1(X,Y),R2(X,Z) =R1(X,Y),R2(X,Z) 具有无损连接性。具有无损连接性。具有无损连接性。具有无损连接性。 其中其中其中其中Z Z Z ZU U U U
45、X X X XY Y Y Y。第33页/共40页第三十四页，共41页。算法算法算法算法6 6 6 6 达到达到达到达到4NF4NF4NF4NF的具有无损的具有无损的具有无损的具有无损(w sn)(w sn)(w sn)(w sn)连接性的分解连接性的分解连接性的分解连接性的分解例，例，例，例，TEACHING(C,T,B)TEACHING(C,T,B)TEACHING(C,T,B)TEACHING(C,T,B)的码是的码是的码是的码是A1l_KeyA1l_KeyA1l_KeyA1l_Key。TEACHINGBCNFTEACHINGBCNFTEACHINGBCNFTEACHINGBCNF，但，但
46、，但，但TEACHING4NFTEACHING4NFTEACHING4NFTEACHING4NF 将模式将模式将模式将模式TEACHINGTEACHINGTEACHINGTEACHING分解分解分解分解(fnji)(fnji)(fnji)(fnji)为：为：为：为： CT(C,T) CT(C,T) CT(C,T) CT(C,T)和和和和CB(C,B)CB(C,B)CB(C,B)CB(C,B)，均满足，均满足，均满足，均满足4NF4NF4NF4NF第34页/共40页第三十五页，共41页。数据依赖的一个有效数据依赖的一个有效数据依赖的一个有效数据依赖的一个有效(yuxio)(yuxio)(yuxi
47、o)(yuxio)且完备的且完备的且完备的且完备的公理系统公理系统公理系统公理系统 关系模式关系模式RR，U U是属性总体集，是属性总体集，D D是是U U上上的一组数据依赖的一组数据依赖( (函数函数(hnsh)(hnsh)依赖和多值依赖和多值依赖依赖) )，对于包含函数，对于包含函数(hnsh)(hnsh)依赖和多值依赖和多值依赖的数据依赖有依赖的数据依赖有个有效且完备的公理个有效且完备的公理系统。系统。A1A1：若：若Y Y X X U U，则，则XYXY；A2A2：若：若XYXY为为F F所蕴含，且所蕴含，且Z Z U U，则，则XZYZXZYZ。A3A3：若：若XYXY，YZYZ，则
48、，则XZ XZ A4A4：若：若XY XY ，V V W W U U，则，则XW XW YVYVA5A5：若：若XY XY ，则，则XUXUX XY Y A6A6：若：若XY XY ，YZYZ，则，则XZXZY Y 第35页/共40页第三十六页，共41页。A7A7：若：若XYXY，则，则XY XY A8A8：若：若XYXY，WZWZ，WYWY，Z Z Y Y，则，则 XZ XZ。 公理公理(gngl)(gngl)系统的有效性是系统的有效性是指从指从D D出发根据出发根据8 8条公理条公理(gngl)(gngl)推导出的函数依赖或推导出的函数依赖或多值依赖一定为多值依赖一定为D D蕴含；完备性蕴
49、含；完备性是指凡是指凡D D所蕴含的函数依赖或多所蕴含的函数依赖或多值依赖均可以从值依赖均可以从D D根据根据8 8条公理条公理(gngl)(gngl)推导出来。也就是说，推导出来。也就是说，在函数依赖和多值依赖的条件在函数依赖和多值依赖的条件下，下，“蕴含蕴含”与与“导出导出”仍是仍是等价的。等价的。数据数据数据数据(shj)(shj)(shj)(shj)依赖的一个有效且完备的公依赖的一个有效且完备的公依赖的一个有效且完备的公依赖的一个有效且完备的公理系统理系统理系统理系统第36页/共40页第三十七页，共41页。3.9.5 3.9.5 模式模式(msh)(msh)分解小结分解小结 关于模式关
50、于模式(msh)(msh)分解的几个重要事实：分解的几个重要事实： （1 1）若要求分解保持函数依赖，那么分）若要求分解保持函数依赖，那么分解总可以达到解总可以达到3NF3NF，但不一定能达到，但不一定能达到BCNFBCNF。 （2 2）若要求分解既保持函数依赖，又具）若要求分解既保持函数依赖，又具有无损连接性，可以达到有无损连接性，可以达到3NF3NF，但不一定能，但不一定能达到达到BCNFBCNF。 （3 3）若要求分解具有无损连接性，那一）若要求分解具有无损连接性，那一定可达到定可达到4NF4NF。第37页/共40页第三十八页，共41页。3.9.5 3.9.5 模式分解模式分解(fnji
51、)(fnji)小结小结n n数据库设计者在进行关系数据库设计时，应数据库设计者在进行关系数据库设计时，应作权衡，尽可能使数据库模式保持最好的作权衡，尽可能使数据库模式保持最好的特性。一般尽可能设计成特性。一般尽可能设计成BCNFBCNF模式集。如模式集。如果果(rgu)(rgu)设计成设计成BCNFBCNF模式集时达不到保持模式集时达不到保持FDFD的特点，那么只能降低要求，设计成的特点，那么只能降低要求，设计成3NF3NF模式集，以求达到保持模式集，以求达到保持FDFD和无损分解的特和无损分解的特点。点。第38页/共40页第三十九页，共41页。3.10 3.10 本章本章(bn zhn)(b
52、n zhn)小结小结n n关系模式的规范化过程实际上是一个关系模式的规范化过程实际上是一个关系模式的规范化过程实际上是一个关系模式的规范化过程实际上是一个“分解分解分解分解”过程：把逻辑上独过程：把逻辑上独过程：把逻辑上独过程：把逻辑上独立的信息放在独立的关系模式中。分解是解决数据冗余的主要方立的信息放在独立的关系模式中。分解是解决数据冗余的主要方立的信息放在独立的关系模式中。分解是解决数据冗余的主要方立的信息放在独立的关系模式中。分解是解决数据冗余的主要方法，也是规范化的一条原则：法，也是规范化的一条原则：法，也是规范化的一条原则：法，也是规范化的一条原则：“关系模式有冗余问题就分解它关系模
53、式有冗余问题就分解它关系模式有冗余问题就分解它关系模式有冗余问题就分解它”。n n要设计要设计要设计要设计(shj)(shj)(shj)(shj)好的数据库模式，必须有一定的理论为基础。这就好的数据库模式，必须有一定的理论为基础。这就好的数据库模式，必须有一定的理论为基础。这就好的数据库模式，必须有一定的理论为基础。这就是模式规范化理论。是模式规范化理论。是模式规范化理论。是模式规范化理论。n n 第39页/共40页第四十页，共41页。内容(nirng)总结会计学。（3）分解既要保持函数依赖，又要具有无损连接性。无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。，Rn 其中U=U1U2。若F中至少存在如下函数依赖中的一个(y )：。（3）如果每个Ri不包含R的候选键，那么把候选键作为一个(y )模式放入中。(3)设中Ri不属于BCNF，那么必有XAFi。由于U中属性有限，因而有限次循环后算法5一定。其中ZUXY第四十一页，共41页。
