第6章(4) 模式的分解

2020/1/211数据库原理计算机系软件教研室2020/1/212数据库原理第六章第四节模式的分解2020/1/213定义6.16模式分解在对函数依赖的基本性质了解之后，可以具体地来讨论模式的分解了。定义6.16：关系模式R（U，F）的一个分解是指：其中111222{,,,,...,,}nnnRUFRUFRUF1,1,,FnijiiUUUUijnFUii并且没有是在上的投影定义6.17：Fi是指函数依赖集合{X→Y∣X→Y∈F+∧XY是Ui的子集}的一个覆盖。2020/1/2146.4.1模式分解的三个定义对于每一个分解是多种多样的，但是分解后的模式应该与原模式是等价的。那么怎么衡量分解的等价呢？从不同的角度可以分为三种：•分解要具有“无损连接性”•分解要“保持函数依赖”•分解既要“保持函数依赖”，又要具有“无损连接性”2020/1/215本小节要讨论的内容•“无损连接性”和“保持函数依赖”的含义；•对于这三种角度的分解可以达到的分离程度，即可以达到第几范式；•对于这几种分离的分解算法；下面用一个实际分解的例子来引出本小节的内容。2020/1/216一个分解实例例4：一个关系模式RU，F，其中U={Sno，Sdept，Mn}，F={Sno→Sdept，Sdept→Mn}。如果我们把它分解成：我们可以对照课本表6.5和分解的办法，我们可以把表6.5分解成了三个关系：r1={S1，S2，S3，S4}r2={D1，D2，D3}r3={张五，李四，王一}1123{,,,,,}RSnoRSdeptRMn2020/1/217一个分解实例（续）我们从r1，r2和r3这三个关系中已经不能回答“某个学生在哪个系学习”了，显然这样的分解是失败的。这是由于失去了关系的“无损连接性”。无损连接性是指：分解后的关系通过自然连接运算还能恢复原来的关系。而我们把r1，r2和r3做自然连接（它们的笛卡尔积）后，我们得到的是一个具有4*4*4=64行的没有实际意义的关系表。不能恢复表5.3所示的含义了。2020/1/218一个分解实例（续2）分解2：这种分解通过自然连接后是可以恢复原来的关系的，但是我们发现在原来的关系模式的F中有函数依赖Sdept→Mn，而在分解后的关系模式中不存在了。因此，关系模式的分解就要求具有“保持函数依赖”的特性才好。212{{,},{},{,},{}}RSnoSdeptSnoSdeptRSnoMnSnoMn2020/1/219一个分解实例（续3）我们来看一个比较好的分解：我们按这种模式分解后的关系通过自然连接是可以恢复到原来的关系的，同时，我们可以显然的发现在原关系模式中的函数依赖在新的关系模式中都存在，因此，这次分解既保证了“无损连接特性”，又“保持了函数依赖”。下面我们用形式化的概念来描述“无损连接性”和“保持函数依赖性”。312{{,},{},{,},{}}RSnoSdeptSnoSdeptRSdeptMnSdeptMn2020/1/21106.4.2.1分解的“无损连接性”我们先来定义几个符号：分解：其中r是RU，F的一个关系。再定义：=（r）也就是说是r在各个模式分解上的投影的连接。111222{,,,,...,,}kkkRUFRUFRUFmiRm2020/1/2111与r以及ri的关系其中：r是R的一个关系；ri=（r）是Ri的一个关系；则有：miR(1)()(2)(),()(3)(())()iRirmrsmrsrmmrmr若则2020/1/2112无损连接的定义定义6.18是RU，F的一个分解，若对RU，F的任何一个关系r均有r=（r）成立，则称这个分解具有无损连接性。也就是说：把分解后的关系做自然连接后可以恢复成原来的关系就可以了。那么用什么样的数学法子来判断呢？111222{,,,,...,,}kkkRUFRUFRUFm2020/1/2113判断无损连接的算法算法6.2判断一个分解的无损连接性是RU，F〉的一个分解，U={A1，A2，…，An}，F={FD1，FD2，…，FDm}，这里我们设F是一个极小依赖集，记FDi为Xi→Ali。（1）建立一张n列k行的表。一列对应一个属性，一行对应一个分解后的模式；在i行j列中的空白处，若属性Aj属于Ui，则填上aj，否则填上bij。111222{,,,,...,,}kkkRUFRUFRUF2020/1/2114判断无损连接的算法（续）（2）对于每一个FDi做如下的操作：取F中的函数依赖X→Y，如果表格中有两行在X分量上相等，在Y分量上不相等，那么修改Y分量上的值，使这两行在Y分量上也相等，修改时分两种情况：①如果Y的分量上有一个是aj，那么另外一个也修改正aj。②如果Y的分量上没有aj，那么下标i较小的那个bij替换其他的符号。2020/1/2115判断无损连接的算法（续2）对F中的m个FD逐一进行一次这样的处置，称为对F的一次扫描。（3）比较扫描前后表的变化，若有则转到第（2）步，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此循环必然终止。定理6.4：若修改结束后的表格中有一行全是a，即a1，a2，…，an，那么该模式分解是无损连接分解。下面我们用两个例子来解释一下。2020/1/2116判断无损连接分解实例1例5：RU,F，U={A，B，C，D，E}，F={AB→C，C→D，D→E}，R的一个分解为R1（A，B，C），R2（C，D），R3（D，E）。解：我们来看算法的动画演示。2020/1/2117例5第（1）步构造初始表ABCDE{A,B,C}a1a2a3b14b15{C,D}b21b22a3a4b25{D,E}b31b32b33a4a5UiA∈{A,B,C}因此此处填a1D不属于{A,B,C}因此此处填b142020/1/2118例5第（2）步修改表ABCDE{A,B,C}a1a2a3b14b15{C,D}b21b22a3a4b25{D,E}b31b32b33a4a5对于AB→C来说，在AB属性组上，在这三行中没有任何两行是相同的，因此不用修改C的值对于C→D来说，在C属性组上，第1，2行的值相等（a3），因此要修改D的值，又因为在D属性上存在a4，因此把b14修改为a4a4对于D→E来说，在D属性组上，第1，2，3行的值相等，因此要修改E的值，又因为在E属性上存在a5，因此把b15，b25修改为a5a5a52020/1/2119一个很有用的判定准则(begin)当关系模式R分解成两个关系模式R1，R2时有下面的判定准则。定理6.5RU,F的一个分解{R1U1,F1,R2U2,F2}具有无损连接性的充分必要条件是：U1∩U2→U1-U2∈F+或U1∩U2→U2-U1∈F+。也就是说：分解后的两个关系模式的公共属性能函数确定U1或U2中的其他属性，这样的分解就是无损连接的。2020/1/21206.4.2.2保持函数依赖性保持函数依赖的判定相对简单。定义6.19若，则RU,F的分解保持函数依赖。也就是说，各个分解后的模式中的函数依赖合并后可以与原模式的函数依赖等价。1()kiiFF111222{,,,,...,,}nnnRUFRUFRUF2020/1/21216.4.3模式分解的算法在模式分解时：1.保持函数依赖时：模式分解一定可以达到3NF，不一定达到BCNF。2.既保持函数依赖，又保证无损连接：模式分解可以达到3NF，不一定达到BCNF。3.只要求保证无损连接性：模式分解一定可以达到4NF。2020/1/2122保持函数依赖转换为3NF算法输入：关系模式RU,F输出：R的一个分解，其中的每一个分解都是3NF的，且保持函数依赖。–对RU,F中的函数依赖做“极小化处理”，处理后的函数依赖集仍记为F，令。–找出不在F中的属性，并把这些属性构成一个关系模式。把去掉这些属性的剩余属性仍记为U。–若有X→A∈F，并且XA=U，则算法终止。–否则，对F中的每个函数依赖都按具有相同左部的原则分组，即X→Y1，X→Y2，…，X→Yk，构成关系模式RXY1Y2…Yk,且函数依赖集为{X→Y1，X→Y2，…，X→Yk}，并令，输出。{}R111222{,,,,...,,}kkkRUFRUFRUF12{(...)}kRXYYY2020/1/2123既无损连接性又保持函数依赖的分解算法算法6.4:（1）设X是RU,F的码，R已由算法6.3分解为{R1，R2，…，Rk}，并令（2）若有某个Ui，X是Ui的子集，那就将R*X,Fx从中去掉。（3）就是所求的分解。下面我们给出一个例子。*{,}xRXF2020/1/2124模式分解的实例引例：设关系模式RU,F，其中U={A，B，C，D，E，P}，F={A→B，AE→P，CD→A，CE→D，BC→D}，此时F已经是极小函数依赖集，我们先用算法6.3分解该模式：第一步：先作保持函数依赖的模式分解；（1）对F做极小化处理，可以省略。（2）去掉F中未出现的属性，未找到。（3）在F中找X→A，且XA=U，未发现。（4）对F中的函数依赖按相同左部分组，并分解成一个模式合并到结果集中。2020/1/2125模式分解的实例（续）我们在F中找不到相同的左部，因此对每个函数依赖进行模式分解，如下所示。分解后的关系模式有：{R1{A,B},A→B,R2{A,E,P},AE→P,R3{C,D,A},CD→A,R4{C,E,D},CE→D,R5{B,C,D},BC→D}2020/1/2126模式分解的实例（续2）第二步：转换为既保持函数依赖又具有无损连接的模式分解。（1）X={C，E}是R的一个候选码，此时Fx={CE→D}，并令（2）我们在上一步的模式分解中发现U4={C,E,D},X是其子集，那么我们把从去掉。（3）显然上一步的分解也是这一步的解。*{,}xRXF*,xRXF2020/1/21276.4.3.3转换为4NF的算法我们知道若一个关系模式中存在非平凡的非函数依赖的多值依赖，那么该关系的冗余是很大的，而且存在插入、修改和删除异常。那么我们就需要转换为4NF。我们不希望存在非平凡的非函数依赖的多值依赖，因此我们就要对存在这种多值依赖的属性组进行分解。这是通过定理6.6来实现的。2020/1/2128定理6.6多值依赖的分解定理6.6：关系模式RU,D中，D为R中函数依赖FD和多值依赖MVD的集合。则X→→Y成立的充要条件是R的分解具有无损连接性，其中Z=U-X-Y。1122{(,),(,)}RXYFRXZF2020/1/2129达到4NF具有无损连接性分解算法分两步：（1）先把原关系模式R按前述算法分解到BCNF。（2）对分解后的各个关系模式Ri（Ui，Di）若他不属于4NF，那么按定理6.6分解。这是由于用定理6.6分解后的子模式只具有平凡的函数依赖了。2020/1/2130本章小结关系模式的规范化，其基本思想：2020/1/2131小结(续)•若要求分解具有无损连接性，那么模式分解一定能够达到4NF•若要求分解保持函数依赖，那么模式分解一定能够达到3NF，但不一定能够达到BCNF•若要求分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到3NF，但不一定能够达到BCNF2020/1/2132小结(续)•规范化理论为数据库设计提供了理论的指南和工具–也仅仅是指南和工具•并不是规范化程度越高，模式就越好–必须结合应用环境和现实世界的具体情况合理地选择数据库模式2020/1/2133本章作业•1，2，12•提交：2，12