关系模式规范化设计理论.ppt

《关系模式规范化设计理论.ppt》由会员分享，可在线阅读，更多相关《关系模式规范化设计理论.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 4 4 章 关系模式的规范化设计理论4.4 关系模式的分解特性 4.4.2 无损连接4.4.3 无损连接的测试4.4.4 保持函数依赖的分解4.4.5 分解成3NF的模式集4.4.6 关系模式设计原则4.4.1 模式分解中存在的问题4.4.1 模式分解中存在的问题(1)设有关系模式R(U)和R1(U1),R2(U2),Rk(Uk)，其中U=A1,A2,An，Ui U(i=1,2,k)且UU1U2Uk。令=R1(U1),R2(U2),Rk(Uk)，则称为R(U)的一个分解，也称为数据库模式，有时也称为模式集。用代替R(U)的过程称为关系模式的分解。数据库模式的一个具体取值记作=(r1,r2,

2、rk)，称为数据库实例。其中ri是中关系模式Ri(Ui)对应的一个具体关系。实际上，关系模式的分解，不仅仅是属性集合的分解，它是对关系模式上的函数依赖集，以及关系模式对应的具体关系进行分解的体现。4.4.1 模式分解中存在的问题(2)例例4.21 设关系模式R(A,B,C)，FAB，BC，r是R(U)满足F的一个具体关系，如表4.12所示。下面，我们将R作出几个不同的分解，看看会出现什么样的问题 ABCa1a2a3 a4 b1b1b2 b3 c1c1c2 c1 表4.12 关系模式R的一个关系r表4.13关系r分解为三个关系 Aa1a2a3 a4Bb1b2 b3Cc1c2关系r1 关系r2 关

3、系r3 4.4.1 模式分解中存在的问题(4)表4.14 关系r的三种分解 关系r4 关系r5 关系r6 ABa1a2a3a4b1b1b2b3ACa1a2a3a4c1c1c2c1BCb1b2b3c1c2c1 将R分解为1=R1(A),R2(B),R3(C)，则相应关系r被分解为三个关系(表4.13)，虽然从范式的角度看，关系r1，r2，r3都是4NF，但这样的分解显然是不可取的。因为它不仅不能保持F，即从分解后的1无法得出AB，或BC这种函数依赖，也不能使r得到“恢复”，这里所说的“恢复”意指无法通过对关系r1，r2，r3的连接运算操作得到与r一致的元组，甚至无法回答最简单的查询要求。将R分解

4、为2=R4(A,B),R5(A,C)，对应关系r分解为r4，r5。这样分解后问题虽然少了一些，但由于不保持BC。由表4.14可知，r通过 得到恢复，即r 。这样的分解称为无损连接分解。4.4.1 模式分解中存在的问题(3)r4 r5r4 r54.4.1 模式分解中存在的问题(5)将R分解为3=R5(A,C)，R6(B,C)，对应关系r分解为r5，r6。则函数依赖AB不被保持，而且r 。将R分解为4=R4(A,B)，R6(B,C)，对应关系r分解为r4，r6。这是最好的一种分解，既保持了函数依赖F=AB,BC(这样的分解称为保持函数依赖的分解)，又可得到r 。且不存在插入和删除异常等问题。从上述

5、实例分析中我们可以看到，一个关系模式的分解可以有几种不同的评判标准：分解具有无损连接性；丢失一些完整性信息分解保持函数依赖；丢失无损连接性；分解既保持函数依赖，又具有无损连接性。最好的。分解前于分解后的等价性。r4 r6r5 r64.4.2 无损连接(1)定定义义4.18 设R(U)是一关系模式，F是R(U)满足的一个函数依赖集，将R(U)分解成关系模式=R1(U1),R2(U2),Rk(Uk)，UU1U2Uk。如果对R(U)中满足F的每一个具体关系r都有：则称这个分解相对于F具有无损连接性(Lossless Join Decomposition)，简称为无损连接分解，即r为它自己在Ui上投影

6、的自然连接。在一般情况下，r和m(r)不一定相等。对于关系模式R(U)关于F的无损连接条件是：任何满足F的关系r，有rm(r)。r=.4.4.3 无损连接的测试(1)由于分解不一定具有无损连接性，因此，如何测试一个模式的分解具有无损连接性是一个很重要的问题。例例4.22 设关系模式R(A,B,C)的一个关系为r(表4.15)，将R(A,B,C)分解成两个模式R1(A,B)和R2(B,C)后，关系r相应分解为关系r1，r2(表4.15)，它们是r在相应的模式属性上投影得到。4.4.3 无损连接的测试(2)表4.15 关系r及其投影 关系r 关系r1 关系r2 A B Ca1a2a7a8a9b1b

7、1b3b4b5c1c2c3c4c5ABa1a2a7a8a9b1b1b3b4b5BCb1b1b3b4b5c1c2c3c4c54.4.3 无损连接的测试(3)现在利用r1和r2的自然连接运算计算m(r)，其结果如表4.16所示，并与表4.15中关系r比较可以发现r m(r)，所以R(A,B,C)分解成R1(A,B)，R2(B,C)不是具有无损连接性的分解。表4.16 关系r1与关系r2的自然连接 ABCa1a1a2a2a7a8a9b1b1b1b1b3b4b5c1c2c1c2c3c4c54.4.3 无损连接的测试(4)如果一个关系模式的分解不是无损连接分解，那么分解后的关系通过自然连接运算无法恢复到

8、分解前的关系。关系模式分解具有无损连接性求在对模式进行分解时,必须利用该模式属性间函数依赖的性质，并通过适当的方法判别其分解是否为无损连接分解，以保证最终使用的分解具有无损连接性。算法算法4.2 无损连接的测试。输入：关系模式R(U)，其中U=A1,A2,An，R(U)上成 立 的 函 数 依 赖 集 F和 R(U)的 一 个 分 解=R1(U1),R2(U2),Rk(Uk)，其中UU1U2Uk。输出：相对于F具有或不具有无损连接性的判断。4.4.3 无损连接的测试(5)计算方法和步骤：构造一张k行n列的表格，每列对应一个属性Aj(j=1,2,n)，每行对应一个模式Ri(Ui)的属性集合(i=

9、1,2,k)。如果Aj在Ui中，那么在表格的第i行第j列处境上符号aj，否则填上符号bij，反复检查F的每一个函数依赖，并修改表格中的元素，直到表格不能修改为止。其方法如下：4.4.3 无损连接的测试(6)取F中的函数依赖XY，如果表格中有两行在X分量上相等，在Y分量上不相等，那么修改Y分量上的值，使这两行在Y分量上也相等，具体修改分两种情况：如果Y的分量中有一个是aj，那么另一个也修改成aj，如果Y的分量中没有aj，那么用下标i较小的那个bij替换另一个符号。若修改结束后的表格中有一行是全a，即al,a2,an，那么相对于F是无损连接分解，否则，相对于F不是无损连接分解。4.4.3 无损连接

10、的测试(7)定定理理4.12 关系模式R(U)的一个分解=R1(U1),R2(U2),Rk(Uk)是无损连接分解的充分必要条件是算法4.2终止且最终结果表中有一行的元素为a1,a2,an。例例4.23 设关系模式R(A,B,C,D,E)分解为=R1(A,D),R2(A,B),R3(B,E),B4(C,D,E),R5(A,E)，其函数依赖集是F=AC,BC,CD,DEC,CEA，判断R的分解是否为无损连接分解。4.4.3 无损连接的测试(8)解：构造初始表，如表4.17(a)所示。(a)初始表 ABCDEA,DA,BB,EC,D,EA,Ea1a1b31b41a1b12a2a2b42b52b13b

11、23b33a3b53a4b24b34a4b54b15b25a5a5a54.4.3 无损连接的测试(9)反复检查F中的函数依赖，修改表格元素：根据AC，对以上表4.17(a)进行处理，由于第1,2,5行在A分量(列)上的值为a1(相等)，在C分量(列)上的值不相等，所以将属性C列的第1,2,5行上b13,b23,b53改为同一个符号b13，结果见表4.17(b)4.4.3 无损连接的测试(10)(b)第次修改结果 ABCDEA,DA,BB,EC,D,EA,Ea1a1b31b41a1b12a2a2b42b52b13b13b33a3b13a4b24b34a4b54b15b25a5a5a5 根据BC，

12、考察表4.17(b)，由于第2,3行在B列上相等，在C列上不相等，所以将属性C列的第2,3行b13,b33改为同一个符号b13，结果见表4.18(a)。第次修改结果4.4.3 无损连接的测试(10)分解ABCDEA,DA,BB,EC,D,EA,Ea1a1b31b41a1b12a2a2b42b52b13b13b13a3b13a4b24b34a4a54b15b25a5a5a54.4.3 无损连接的测试(11)根据CD，考察表4.18(a)，由于第1,2,3,5行在C列上的值为b13(相等)，在D列上的值不相等，根据算法修改原则，将D列的第1,2,3,5行上的a4,b24,b34,b54均改成a4，

13、结果见表4.18(b)第次修改结果 分解ABCDEA,DA,BB,EC,D,EA,Ea1a1b31b41a1b12a2a2b42b52b13b13b13a3b13a4a4a4a4a4b15b25a5a5a54.4.3 无损连接的测试(12)根据DEC，考察表4.18(b)，由于3,4,5行在D,E列上的值为(a4,a5)，即相等，而在C列上不相等，根据算法修改原则将C所在列的第3,4,5行上的元素改为a3，结果见表4.19(a)。(b)第次修改结果 分解ABCDEA,DA,BB,EC,D,EA,Ea1a1b31b41a1b12a2a2b42b52b13b13a3a3a3a4a4a4a4a4b1

14、5b25a5a5a54.4.3 无损连接的测试(13)根据CEA，考察表4.19(a)，根据算法修改原则，将A列的第3,4,5行的元素都改成al，结果见见表4.19(b)。第次修改结果 由于F中的所有函数依赖已经检查完毕，所以第次表为最后结果。因为第3行已是全a行，因此关系模式R(U)的分解是无损连接分解。分解ABCDEA,DA,BB,EC,D,EA,Ea1a1a1a1a1b12a2a2b42b52b13b13a3a3a3a4a4a4a4a4b15b25a5a5a54.4.3 无损连接的测试(14)定定理理4.13 如果R(U)的分解为Rl(U1)，R2(U2)，其中U=U1U2，F为R(U)

15、所满足的函数依赖集合，则分解是无损连接的充分必要条件为(U1U2)(U1U2)或者(U1U2)(U2U1)成立。此定理表明，当模式R分解成两个关系模式Rl(U1)和R2(U2)时，如果其公共属性能函数决定U1或U2中的其它属性，这样的分解就是无损连接的。4.4.3 无损连接的测试(15)例例 4.24 设 关 系 模 式 R(A,B,C)，F AB，则 1Rl(A,B)，R2(A,C)是 无 损 连 接 的，而 1 Rl(A,B)，R3(B,C)不是无损连接。解：对于分解1，这里U=A,B,C，U1=A,B，U2=A,C。根据上述定理可证明1是无损连接的。因 为 U1U2=A；U1U2=B，因

16、 为 ABF，所 以U1U2(U1U2)在F中成立，故由定理4.13知，关系模式R(U)的分解1Rl(A,B)，R2(A,C)具有无损连接性。用同样的办法可证明2不是无损连接的。这里U=A,B,C，U1=A,B，U2=B,C 因为U1U2=B；U1U2=A，U2U1=C，所以U1U2(U1U2)和U1U2(U2U1)都不能由F导出，故由定理4.13知，关系模式R(U)的分解2Rl(A,B)，R2(B,C)不具有无损连接性。4.4.4 保持函数依赖的分解(1)对关系模式分解的无损连接性要求是必要的，因为它保证了关系模式的任何一个具体关系能由它自己的那些投影进行自然连接得到恢复。例4.21说明，仅

17、要求关系模式分解具有无损连接性是不够的。如果关系模式在分解后不能保持函数依赖，丢失完整性信息。因此，保持关系模式分解前后的函数依赖集不变，即从关系模式R(U)到=R1(U1),R2(U2),Rk(Uk)的分解，应使函数依赖集F被所有的所蕴涵，这就是保持函数依赖问题。设F是属性集U上的函数依赖集，Z是U上的一个子集，F在Z上的一个投影用Z(F)表示，定义为：Z(F)XY|(XY)F+且XYZ定义定义4.19 设关系模式R(U)的一个分解=R1(U1),R2(U2),Rk(Uk)，F是R(U)满足的函数依赖集，如果，则称分解保持函数集F，简称保持函数依赖。4.4.4 保持函数依赖的分解(2)4.4

18、.4 保持函数依赖的分解(3)由定义可知，检验一个分解是否保持函数依赖，就是检验函数依赖集 是否覆盖函数依赖集F，即对于任意一个函数依赖XYF是否由G根据Armstong公理导出，而由定理4.3可知，即是要检验是否有 。由以上分析可得检验一个分解是否保持函数依赖的算法。4.4.4 保持函数依赖的分解(4)算法算法4.3 函数依赖测试输入：R(U,F)和=R1(U1),R2(U2),Rk(Uk)输出：是否保持F的判断结果。算法步骤：令G=，F=FG，Result=True 对于F中的第一个函数依赖XY，计算 并令F=FXY；若 ，则令Result=False，转 否则，若F，转，否则，转；若Re

19、sult=True则保持函数依赖F，否则不保持函数依赖F。Y4.4.4 保持函数依赖的分解(5)例例4.25 设有关系模式R(A,B,C,D)，F=AB,BC,CD,DA，模 式 R的 一 个 分 解 =R1(A,B),R2(B,C),R3(C,D)。判断是否保持F。解：由函数依赖集F和分解可知：F1=A,B(F)=AB,BA，F2=B,C(F)=BC,CB，F3=C,D(F)=CD,DC，根据算法：G=AB,BA,BC,CB,CD,DC，F=FG=DA,Result=True4.4.4 保持函数依赖的分解(6)对于函数依赖DA，即令X=D,Y=A有XY，F=FDA=由算法4.2计算得 =A,

20、B,C,D 因为 Y=A =A,B,C,D，转 由于Result=True，所以关系模式R的分解保持函数依赖F。4.4.4 保持函数依赖的分解(7)关于关系模式的分解有以下几个重要事实：若要求分解保持函数依赖，那么模式分解总可以达到3NF，但不一定能达到BCNF。若要求分解既保持函数依赖，又具有无损连接性，可以达到3NF，但不一定能达到BCNF。若要求分解具有无损连接性，那一定可达到4NF。4.4.5 分解成3NF的模式集(1)以下算法保证将一个关系模式R分解成3NF模式集，且既保持函数依赖又具有无损连接性。算算法法4.4 将一个关系模式转换为3NF的保持函数依赖的分解。输入：关系模式R，属性

21、集合U和R上成立的函数依赖集F。输出：R的一个分解R1(U1),R2(U2),Rk(Uk)，其中每个Ri(Ui)都是3NF的且 保持函数依赖F。4.4.5 分解成3NF的模式集(2)算法步骤：求出函数依赖集F的最小覆盖并仍记为F,令=。如果U中某些属性U1在F的所有函数依赖的左部和右部都不出现，则把这些属性构成一个关系模式R(U1)，然后把这些属性从U中去掉，剩余的属性仍记为U，令=R(U1)。若F中有函数依赖XY，满足XY=U，则R(U)，则转。否则，对F中所有以X为左部的函数依赖XY1,XY2,XYk，构成关系模式R(XY1Y2Yk)，其函数依赖集为XY1,XY2,XYk，令=R(XY1Y

22、2Y1)，转(4)。输出。4.4.5 分解成3NF的模式集(3)定定理理4.14 算法4.4把一个关系模式分解为保持函数依赖F的3NF模式集。定定理理4.15 设R1(U1),R2(U2),Rk(Uk)是由算法4.3得到的一个分解。设X是R(U)的一个候选键，若 存 在 某 个 Ui 使 XUi，则 令=，否 则 令=Rx(X)。则是R的一个分解，中所有模式都是3NF，且这个分解具有无损连接和保持函数依赖两个特性。4.4.5 分解成3NF的模式集(2)例例4.26 设关系模式R(A,B,C,D,E,P),它满足的函数依赖集F=AB,AEP,CDA,CED,BCD已是最小函数依赖集，则由算法4.

23、4可得R(A,B,C,D,E,P)的一个分解=R1(A,B),R2(A,E,P),R3(C,D,A),R4(C,E,D),R5(B,C,D)这个分解显然将原有的函数依赖F保持下来，且每个分解模式都是3NF。由于R的一个候选键属性集是C,EU4=C,E,D，根据定理4.15可知 =R1(A,B),R2(A,E,P),R3(C,D,A),R4(C,E,D),R5(B,C,D)是R的一个分解，其中的所有模式都是3NF，且这个分解具有无损连接和保持函数依赖两个特性。此外，还有将R分解成BCNF的算法,这里不介绍。4.4.6 关系模式设计原则(1)关系模式R(U,F)分解成数据库模式R1(U1),R2(

24、U2),Rk(Uk)，一般应满足以下四个要求中每个关系模式Ri应有某种范式性质(3NF或BCNF)；应具有无损联接连接性；(3)仍然保持函数依赖集F；最小性:指中的模式个数应最少和模式中属性总数应最少。4.4.6 关系模式设计原则(2)模式分解的关键问题是要“等价”地分解。一个好的模式设计方法应符合下列三条原则：表达性；分离性；最小冗余性。表达性表达性涉及到分解前后两个数据库模式的等价性问题，即数据等价和依赖等价，分别用无损联接性和保持函数依赖来衡量。4.4.6 关系模式设计原则(3)分分离离性性是指属性间的“独立联系”应该用不同的关系模式表达，即分解以后的各个模式尽可能做到概念单一。独立联系

25、是我们所考虑的“基本信息单位”。例如模式R中有XY成立，它就是一个“独立联系”，我们就把XY作为一个基本的信息单位从R(U)中分离出去。实际上分离就是清除存储异常和数据冗余现象，如果能达到这个目的，就实行分离。分离的基准就是一系列范式，但分离与依赖等价有时是不可兼容的。4.4.6 关系模式设计原则(4)最最小小冗冗余余性性要求在保证分解前后两个数据库模式等价的前提下，使数据库模式R1(U1),R2(U2),Rk(Uk)中的模式个数最少和模式中属性总数最少，以节省存储空间，提高操作效率，清除不必要冗余。但要注意，在实际使用并不需要达到最小冗余。因为有时带点冗余对于提高查询处理效率是有好处的。The endThank you for your attention!