模式的分解精选文档.ppt

《模式的分解精选文档.ppt》由会员分享，可在线阅读，更多相关《模式的分解精选文档.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模式的分解2022/10/251本讲稿第一页，共三十三页数据库原理数据库原理第六章第六章第四第四节节模式的分解模式的分解2022/10/252本讲稿第二页，共三十三页定义6.16 模式分解在对函数依赖的基本性质了解之后，可以具体地来讨论模式的分解了。定义6.16：关系模式R（U，F）的一个分解是指：其中定义6.17：Fi是指函数依赖集合XY XYF+XY是Ui的子集的一个覆盖。2022/10/253本讲稿第三页，共三十三页6.4.1 模式分解的三个定义对于每一个分解是多种多样的，但是分解后的模式应该与原模式是等价的。那么怎么衡量分解的等价呢？从不同的角度可以分为三种：分解要具有“无损连接性”分

2、解要“保持函数依赖”分解既要“保持函数依赖”，又要具有“无损连接性”2022/10/254本讲稿第四页，共三十三页本小节要讨论的内容“无损连接性”和“保持函数依赖”的含义；对于这三种角度的分解可以达到的分离程度，即可以达到第几范式；对于这几种分离的分解算法；下面用一个实际分解的例子来引出本小节的内容。2022/10/255本讲稿第五页，共三十三页一个分解实例例4：一个关系模式R，其中U=Sno，Sdept，Mn，F=SnoSdept，Sdept Mn。如果我们把它分解成：我们可以对照课本表6.5和分解的办法，我们可以把表6.5分解成了三个关系：r1=S1，S2，S3，S4r2=D1，D2，D3

3、r3=张五，李四，王一2022/10/256本讲稿第六页，共三十三页一个分解实例（续）我们从r1，r2和r3这三个关系中已经不能回答“某个学生在哪个系学习”了，显然这样的分解是失败的。这是由于失去了关系的“无损连接性”。无损连接性是指：分解后的关系通过自然连接运算还能恢复原来的关系。而我们把r1，r2和r3做自然连接（它们的笛卡尔积）后，我们得到的是一个具有4*4*4=64行的没有实际意义的关系表。不能恢复表5.3所示的含义了。2022/10/257本讲稿第七页，共三十三页一个分解实例（续2）分解2：这种分解通过自然连接后是可以恢复原来的关系的，但是我们发现在原来的关系模式的F中有函数依赖Sd

4、eptMn，而在分解后的关系模式中不存在了。因此，关系模式的分解就要求具有“保持函数依赖”的特性才好。2022/10/258本讲稿第八页，共三十三页一个分解实例（续3）我们来看一个比较好的分解：我们按这种模式分解后的关系通过自然连接是可以恢复到原来的关系的，同时，我们可以显然的发现在原关系模式中的函数依赖在新的关系模式中都存在，因此，这次分解既保证了“无损连接特性”，又“保持了函数依赖”。下面我们用形式化的概念来描述“无损连接性”和“保持函数依赖性”。2022/10/259本讲稿第九页，共三十三页6.4.2.1 分解的“无损连接性”我们先来定义几个符号：分解：其中r是R的一个关系。再定义：=（

5、r）也就是说 是r在各个模式分解上的投影的连接。2022/10/2510本讲稿第十页，共三十三页 与r以及ri的关系其中：r是R的一个关系；ri=（r）是Ri的一个关系；则有：2022/10/2511本讲稿第十一页，共三十三页无损连接的定义定义6.18 是R的一个分解，若对R的任何一个关系r均有r=（r）成立，则称这个分解具有无损连接性。也就是说：把分解后的关系做自然连接后可以恢复成原来的关系就可以了。那么用什么样的数学法子来判断呢？2022/10/2512本讲稿第十二页，共三十三页判断无损连接的算法算法6.2 判断一个分解的无损连接性 是RU，F的一个分解，U=A1，A2，An，F=FD1，

6、FD2，FDm，这里我们设F是一个极小依赖集，记FDi为XiAli。（1）建立一张n列k行的表。一列对应一个属性，一行对应一个分解后的模式；在i行j列中的空白处，若属性Aj属于Ui，则填上aj，否则填上bij。2022/10/2513本讲稿第十三页，共三十三页判断无损连接的算法（续）（2）对于每一个FDi做如下的操作：取F中的函数依赖XY，如果表格中有两行在X分量上相等，在Y分量上不相等，那么修改Y分量上的值，使这两行在Y分量上也相等，修改时分两种情况：如果Y的分量上有一个是aj，那么另外一个也修改正aj。如果Y的分量上没有aj，那么下标i较小的那个bij替换其他的符号。2022/10/251

7、4本讲稿第十四页，共三十三页判断无损连接的算法（续2）对F中的m个FD逐一进行一次这样的处置，称为对F的一次扫描。（3）比较扫描前后表的变化，若有则转到第（2）步，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此循环必然终止。定理6.4：若修改结束后的表格中有一行全是a，即a1，a2，an，那么该模式分解是无损连接分解。下面我们用两个例子来解释一下。2022/10/2515本讲稿第十五页，共三十三页判断无损连接分解实例1例5：R，U=A，B，C，D，E，F=ABC，C D，D E，R的一个分解为R1（A，B，C），R2（C，D），R3（D，E）。解：我们来看

8、算法的动画演示。2022/10/2516本讲稿第十六页，共三十三页例5 第（1）步构造初始表ABCDEA,B,Ca1a2a3b14b15C,Db21b22a3a4b25D,Eb31b32b33a4a5UiAA,B,C因此此处填a1D不属于A,B,C因此此处填b142022/10/2517本讲稿第十七页，共三十三页例5 第（2）步修改表ABCDEA,B,Ca1a2a3b14b15C,Db21b22a3a4b25D,Eb31b32b33a4a5对于ABC来说，在AB属性组上，在这三行中没有任何两行是相同的，因此不用修改C的值对于CD来说，在C属性组上，第1，2行的值相等（a3），因此要修改D的值，

9、又因为在D属性上存在a4，因此把b14修改为a4a4对于DE来说，在D属性组上，第1，2，3行的值相等，因此要修改E的值，又因为在E属性上存在a5，因此把b15，b25修改为a5a5a52022/10/2518本讲稿第十八页，共三十三页一个很有用的判定准则(begin)当关系模式R分解成两个关系模式R1，R2时有下面的判定准则。定理定理6.5 R的一个分解R1,R2具有无损连接性的充分必要条件是：U1U2U1-U2F+或U1U2U2-U1F+。也就是说：分解后的两个关系模式的公共属性能函数确定U1或U2中的其他属性，这样的分解就是无损连接的。2022/10/2519本讲稿第十九页，共三十三页6

10、.4.2.2 保持函数依赖性保持函数依赖的判定相对简单。定义6.19 若 ，则R的分解保持函数依赖。也就是说，各个分解后的模式中的函数依赖合并后可以与原模式的函数依赖等价。2022/10/2520本讲稿第二十页，共三十三页6.4.3 模式分解的算法在模式分解时：1.保持函数依赖时：模式分解一定可以达到3NF，不一定达到BCNF。2.既保持函数依赖，又保证无损连接：模式分解可以达到3NF，不一定达到BCNF。3.只要求保证无损连接性：模式分解一定可以达到4NF。2022/10/2521本讲稿第二十一页，共三十三页保持函数依赖转换为3NF算法输入：关系模式R输出：R的一个分解 ，其中的每一个分解都

11、是3NF的，且保持函数依赖。对R中的函数依赖做“极小化处理”，处理后的函数依赖集仍记为F，令 。找出不在F中的属性，并把这些属性构成一个关系模式。把去掉这些属性的剩余属性仍记为U。若有XAF，并且XA=U，则 算法终止。否则，对F中的每个函数依赖都按具有相同左部的原则分组，即XY1，XY2，XYk，构成关系模式R,且函数依赖集为XY1，XY2，XYk，并令 ，输出 。2022/10/2522本讲稿第二十二页，共三十三页既无损连接性又保持函数依赖的分解算法算法6.4:（1）设X是R的码，R已由算法6.3分解为R1，R2，Rk，并令（2）若有某个Ui，X是Ui的子集，那就将R*从 中去掉。（3）就

12、是所求的分解。下面我们给出一个例子。2022/10/2523本讲稿第二十三页，共三十三页模式分解的实例引例：设关系模式R，其中U=A，B，C，D，E，P，F=AB，AE P，CD A，CE D，BC D，此时F已经是极小函数依赖集，我们先用算法6.3分解该模式：第一步：先作保持函数依赖的模式分解；（1）对F做极小化处理，可以省略。（2）去掉F中未出现的属性，未找到。（3）在F中找X A，且XA=U，未发现。（4）对F中的函数依赖按相同左部分组，并分解成一个模式合并到结果集中。2022/10/2524本讲稿第二十四页，共三十三页模式分解的实例（续）我们在F中找不到相同的左部，因此对每个函数依赖进

13、行模式分解，如下所示。分解后的关系模式有：R1,R2,R3,R4,R5 2022/10/2525本讲稿第二十五页，共三十三页模式分解的实例（续2）第二步：转换为既保持函数依赖又具有无损连接的模式分解。（1）X=C，E是R的一个候选码，此时Fx=CED，并令（2）我们在上一步的模式分解中发现U4=C,E,D,X是其子集，那么我们把 从 去掉。（3）显然上一步的分解也是这一步的解。2022/10/2526本讲稿第二十六页，共三十三页6.4.3.3 转换为4NF的算法我们知道若一个关系模式中存在非平凡的非函数依赖的多值依赖，那么该关系的冗余是很大的，而且存在插入、修改和删除异常。那么我们就需要转换为

14、4NF。我们不希望存在非平凡的非函数依赖的多值依赖，因此我们就要对存在这种多值依赖的属性组进行分解。这是通过定理6.6来实现的。2022/10/2527本讲稿第二十七页，共三十三页定理6.6 多值依赖的分解定理6.6：关系模式R中，D为R中函数依赖FD和多值依赖MVD的集合。则X Y成立的充要条件是R的分解具有无损连接性，其中Z=U-X-Y。2022/10/2528本讲稿第二十八页，共三十三页达到4NF具有无损连接性分解算法分两步：（1）先把原关系模式R按前述算法分解到BCNF。（2）对分解后的各个关系模式Ri（Ui，Di）若他不属于4NF，那么按定理6.6分解。这是由于用定理6.6分解后的子

15、模式只具有平凡的函数依赖了。2022/10/2529本讲稿第二十九页，共三十三页本章小结关系模式的规范化，其基本思想：2022/10/2530本讲稿第三十页，共三十三页小结(续)若要求分解具有无损连接性，那么模式分解一定能够达到4NF若要求分解保持函数依赖，那么模式分解一定能够达到3NF，但不一定能够达到BCNF若要求分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到3NF，但不一定能够达到BCNF2022/10/2531本讲稿第三十一页，共三十三页小结(续)规范化理论为数据库设计提供了理论的指南和工具也仅仅是指南和工具并不是规范化程度越高，模式就越好必须结合应用环境和现实世界的具体情况合理地选择数据库模式2022/10/2532本讲稿第三十二页，共三十三页本章作业1，2，12提交：2，122022/10/2533本讲稿第三十三页，共三十三页