关系数据理论模式分解课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,*6.4模式的分解,复习:例 SL（Sno，Sdept，,Sloc）,F=SnoSdept,Sdept,Sloc,SL2NF,1.存在问题：插入异常、删除异常、冗余度大和修改复杂,2.问题解决：,分,解,ND(,Sno,Sdept,),F1=SnoSdept,DL(,Sdept,Sloc,),F2=Sdept,Sloc,3.把低一级的关系模式分解为若干个高一级的关系模式的方法,并不是唯一的。,为什么要这样分解？,11/6/2024,模式的分解主要内容,目的:,把一个关系模式按要求,正确,分解到一定的级别,概念：,分解；无损分解；投影；无损连接性；,保持函数依赖,算法：,判断保持函数依赖不变方法,判别一个分解的无损连接性（,算法,6.2,；,定理,6.5,）,转换为,2NF,既有无损连接性又保持函数依赖的分解,转换为,3NF,既有无损连接性又保持函数依赖的分解（算法,6.4,）,转换为,BCNF,的无损连接分解（算法,6.5,）,11/6/2024,一、模式分解概念,定义,6.16,关系模式R的,一个分解,：,=R,1,，R,2,，R,n,U=U,1,U,2,U,n,，且不存在 U,i,U,j,，F,i,为 F在 U,i,上的,投影。,定义,6.17,函数依赖集合,X,Y,|,X,Y,F,+,XY,U,i,的一个,覆盖,F,i,叫作,F,在属性,U,i,上的投影。,例,1:R(ABCD),F=A B,B C,C D,=,AB,ACD,F,1,=？，F,2,=？,上例:F,1,=A B,F,2,=A C,C D,11/6/2024,二、几种模式分解方法,例2：,SL（Sno，Sdept，Sloc）,F=SnoSdept,SdeptSloc,Sno Sdept Sloc,95001 CS A,95002 IS B,95003 MA C,95004 IS B,95005 PH B,11/6/2024,第一种分解方法,1.SL分解为三个关系模式：,=SN，SD，SO,SN SD SO,Sno Sdept Sloc,95001 CS A,95002 IS B,95003 MA C,95004 PH ,95005 ,分解后的关系为：,分解后,丢失了许多信息,.,如：无法查询95001学生所在系或所在宿舍。,分解后的关系若可通过,自然连接恢复为原来的关系,，那么这种分解就没有,丢失信息.。,11/6/2024,第二种分解方法,分解后的关系为：,NL DL,Sno Sloc Sdept Sloc,95001 A CS A,95002 B IS B,95003 C MA C,95004 B PH B,95005 B ,2.SL分解为下面二个关系模式：,=NL，,DL,11/6/2024,第二种分解方法（续）,NL DL,Sno Sloc Sdept,95001 A CS,95002 B IS,95002 B PH,95003 C MA,95004 B IS,95004 B PH,95005 B IS,95005 B PH,元组增加了，信息丢失了,11/6/2024,第三种分解方法,3.,将SL分解为下面二个关系模式：,=ND，,NL,分解后的关系为：,ND NL,Sno Sdept Sno Sloc,95001 CS 95001 A,95002 IS 95002 B,95003 MA 95003 C,95004 IS 95004 B,95005 PH 95005 B,11/6/2024,第三种分解方法（续）,ND NL,Sno Sdept Sloc,95001 CS A,95002 IS B,95003 MA C,95004 CS A,95005 PH B,与SL关系一样，因此,没有丢失信息,11/6/2024,具有无损连接性的模式分解,R的一个分解,=R,1,R,n,若R与R1、R2、Rn自然连接的结果相等，则称R的这个,分解,具有,无损连接性,（Lossless join）,具有无损连接性的分解,保证不丢失信息,显然，第三种分解方法具有无损连接性,无损连接性能否解决插入异常、删除异常、修改复杂、数据冗余等问题？,不能,。,原因,:,分解,没有保持原关系中的函数依赖。,SL中的函数依赖,SdeptSloc,，没有投影到关系模式ND、NL上,11/6/2024,保持函数依赖的模式分解,设关系模式R被分解为若干个关系模式,R,1,，R,2,，R,n,若F所逻辑蕴含的函数依赖,一定,也由分解得到的,某个关系模式,中的函数依赖F,i,所逻辑蕴含,，则称,R的这个分解是保持函数依赖的,（Preserve dependency）。,定义6.19 若,F,+,=（,F,i,）,+,，则,R的分解,=R,1,，R,2,，R,k,保持函数依赖不变。,-据此，可,判断分解是否保持函数依赖,。,11/6/2024,例3：设关系模式R（ABCD），R分解为=AB，BC，CD。,(1)如果R上成立的函数依赖集为F=BA,C D，分解是否保持函数依赖?,(2)如果R上成立的函数依赖集为F=AB,C D 呢?,判断分解是否保持函数依赖,11/6/2024,第四种分解方法,将SL分解为下面二个关系模式：,ND(Sno,Sdept)，F,1,=Sno Sdept,DL(Sdept,Sloc)，F,2,=SdeptSloc,可见,：,分解具有无损连接性，能够保证不丢失信息。,分解保持了函数依赖，可以减轻或解决各种异常情况。,是两个互相独立的标准。,11/6/2024,算法,6.2,无损分解的测试（一）,构造一张,k,行,n,列的表格,三、判别一个分解的无损连接性,若修改的最后一张表格中有一行是全,a,，那么称相对于F是无损分解，否则称损失分解。,对于F中一个FD XY，如果表格中有两行在X值上相等，在Y值上不相等，那么把这两行在Y值上也改成相等的值。一直到表格不能修改为止。,11/6/2024,例4：,设关系模式R（ABCD），R分解为=AB，BC，CD。(1)如果R上成立的函数依赖集为F1=BA,C D，是否具有无损分解?(2)如果R上成立的函数依赖集为F2=AB,C D 呢?,怎样判断分解的无损连结性,a,4,a,3,b,32,b,31,CD,b,24,a,3,a,2,b,21,BC,b,14,b,13,a,2,a,1,AB,D,C,B,A,（a）初始表格,（b）修改后的表格,示意图（一）,F1,=BA,C D,a,4,a,3,b,32,b,31,CD,b,24,a,3,a,2,b,21,BC,b,14,b,13,a,2,a,1,AB,D,C,B,A,据BA,a,1,据CD,a,4,第二行全a,故为无损分解,11/6/2024,a,4,a,3,b,32,b,31,CD,b,24,a,3,a,2,b,21,BC,b,14,b,13,a,2,a,1,AB,D,C,B,A,a,4,a,3,b,32,b,31,CD,a,4,a,3,a,2,b,21,BC,b,14,b,13,a,2,a,1,AB,D,C,B,A,（a）初始表格,（b）修改后的表格,示意图（二）,F2,=AB,C D,11/6/2024,无损分解的测试方法(二),定理6.5 R的一个分解,=R,1,，R,2,具有无损分解的,充分必要条件,是：,（U,1,U,2,）（U,1,U,2,）,F,+,或,（U,1,U,2,）（U,2,U,1,）,F,+,仅,适用于分解为两个关系模式,的情况,提问：,例5：R，U为ABC，F=A B，B C,(1),1,=AB，BC,是否为无损分解？是否保持函数依赖不变？,(2),2,=AB，AC,是否为无损分解？是否保持函数依赖不变？,11/6/2024,四、模式分解算法,算法：分解成2NF模式集的算法,设关系模式,R,（U），主码是,W,，R上还存在FD,XZ,，并且Z是非主属性和,X,W,，那么WZ就是一个局部函数依赖。此时应把R分解成两个模式,R1（XZ），,主码是X；,R2（U-Z），,主码仍是W，外码是X,如果R1和R2还不是2NF，则,重复上述过程,，一直到数据库模式中每一个关系模式都是2NF为止。,11/6/2024,分解成2NF模式集的算法示例,例6:关系模式 SLC(Sno,Sdept,Sloc,Cno,Grade),Sloc为学生住处，假设每个系的学生住在同一个地方。,F=(Sno,Cno)Grade,Sno Sdept,Sdept Sloc,SLC码为：,(Sno,Cno),据算法：,SLC分解为两个关系模式，以消除这些部分函数依赖,SL（Sno，Sdept，Sloc）,SC（Sno，Cno，Grade）,11/6/2024,四、模式分解算法,算法6.4：将R无损且保持依赖地分解成3NF模式集,对于,R,先求出,F,min,把,F,min,中,左部相同,的,FD,用合并性合并起来。,对,F,min,中，,每个,FD,XY,去构成一个模式,XY,。,在构成的模式集中，若每个模式,都不包含,R,的候选,码,，把候选,码,作为一个模式放入模式集中。,这样得到的模式集是关系模式,R,的一个分解，并且这个分解,既是无损分解，又能保持,FD,。,11/6/2024,例7：设关系模式R（ABCDE），R的F,min,=,A B,C D,将R分解为3NF。,开始提出的问题：,SL（Sno，Sdept，Sloc），,F=SnoSdept,Sdept Sloc,据,算法6.4，将SL,分解为：,ND(Sno,Sdept)F1=SnoSdept,DL(Sdept,Sloc)F2=Sdept Sloc,无损且保持依赖地分解成3NF模式集示例,11/6/2024,对于关系模式R的分解（初始时=R）,如果中有一个关系模式R,i,不是BCNF。,据定义可知,，R,i,中存在一个非平凡FD XY，有X不包含码。此时把R,i,分解成,XY,和,R,i,Y,两个模式。,重复上述过程，一直到中每一个模式都是BCNF。,算法6.5：,无损分解,成BCNF模式集,例8：在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。,每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称：,码？,(,S，J,)T，(,S，T,)J，TJ,11/6/2024,BCNF,解决方法：将STJ分解为二个关系模式：,ST(,S，T,)BCNF，TJ(,T,，J)BCNF,没有,任何属性,对码的部分函数依赖和传递函数依赖,S,T,ST,T,J,TJ,11/6/2024,分解算法,若要求分解,既具有无损连接性，又保持函数依赖,，则模式分解一定能够达到3NF，但不一定能够达到BCNF。,若要求分解,具有无损连接性,，那么模式分解一定能够达到BCNF。,11/6/2024,模式的分解小结,目的:,把一个关系模式按要求,正确,分解到一定的级别,概念：,分解；投影；无损连接性；保持函数依赖,无损分解；,算法：,判断保持函数依赖方法,判别一个分解的无损连接性（,算法,6.2,；,定理,6.5,）,转换为,2NF,既有无损连接性又保持函数依赖的分解,转换为,3NF,既有无损连接性又保持函数依赖的分解（算法,6.4,）,转换为,BCNF,的无损连接分解（算法,6.5,）,11/6/2024,小结,规范化理论为数据库设计提供了理论的指南和工具,也仅仅是指南和工具,并不是规范化程度越高，模式就越好,必须结合应用环境和现实世界的具体情况合理地选择数据库模式,11/6/2024,下课了。,休息一会儿。,研,11/6/2024,