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