第13讲模式分解.ppt

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

1、第5章 关系模式的规范化设计模式分解模式分解1第第13讲讲 模式分解模式分解关系模式的规范化设计关系模式的规范化设计所要解决的问题什么是什么是“好好”的关系数据模式的关系数据模式如何评价一个好的关系数据模式如何评价一个好的关系数据模式如何设计一个如何设计一个“好好”的关系数据模式的关系数据模式2第第13讲讲 模式分解模式分解关系模式的规范化设计关系模式的规范化设计主要内容关系模式的设计问题关系模式的设计问题关系模式规范化的基本概念和理论关系模式规范化的基本概念和理论关系模式分解的理论基础和算法关系模式分解的理论基础和算法3第第13讲讲 模式分解模式分解回顾回顾1NF2NF3NFBCNF去除非主

2、属性对于候选键的部分函数依赖去除非主属性对于候选键的部分函数依赖去除非主属性对于去除非主属性对于候选候选键的传递函数依赖键的传递函数依赖去除主属性对于去除主属性对于候选候选键的部分和传递函数依赖键的部分和传递函数依赖去除不被候选键所蕴涵的非平凡的多值依赖去除不被候选键所蕴涵的非平凡的多值依赖4NF消除消除决定决定因素因素非码非码的非的非平凡平凡函数函数依赖依赖4第第13讲讲 模式分解模式分解Armstrong公理系统逻辑蕴涵逻辑蕴涵 Armstrong公理系统推理规则公理系统推理规则 FD的逻辑蕴涵的逻辑蕴涵 函数依赖集函数依赖集F 的闭包的闭包F+属性集闭包属性集闭包 函数依赖集等价和最小函

3、数依赖集函数依赖集等价和最小函数依赖集 候选码及其求解方法候选码及其求解方法 回顾回顾 5第第13讲讲 模式分解模式分解主要内容模式分解的概念模式分解的概念分解的无损连接性和保持函数依赖性分解的无损连接性和保持函数依赖性 模式分解算法模式分解算法 模式分解模式分解6第第13讲讲 模式分解模式分解分解的概念 设有一关系模式设有一关系模式R（U,F），若用一关系模），若用一关系模式的集合式的集合=R1（U1,F1），），R2（U2,F2），），Rn（Un,Fn）来取代，其中来取代，其中U=Ui，并，并且没有且没有Ui Uj，1i,jn，Fi是是F在在Ui上的上的投影投影。则关系模式的集合则关系模式

4、的集合为为R的一个分解的一个分解 =R1，R2，Rn模式分解的概念模式分解的概念7第第13讲讲 模式分解模式分解分解的概念F在在Ui上的投影上的投影 Fi=XY|XY F+XY Ui 模式分解的概念模式分解的概念思考：思考：设有关系模式设有关系模式R（A，B，C，D），），F是是R上成立上成立的的FD集集F=ABC，DB，则，则 F在模式在模式ACD上的投上的投影为影为_；F在模式在模式AC上的投影为上的投影为_。ADC 空空8第第13讲讲 模式分解模式分解分解的概念 模式分解的概念模式分解的概念【例】R(编号，连队，连长，科目，成绩),F=编号连队，连队连长，(编号，科目)成绩 【例】R(学

5、生学号，学生姓名，所在系，系主任，课程名称，成绩，F=学生学号学生姓名，学生学号所在系，所在系系主任，（学生学号，课程名称）成绩9第第13讲讲 模式分解模式分解分解的概念 模式分解的概念模式分解的概念1NF2NF3NF去除非主属性对于键的部分函数依赖去除非主属性对于键的部分函数依赖去除非主属性对于键的传递函数依赖去除非主属性对于键的传递函数依赖R R（学生学号学生学号，学生姓名，所在系，系主任，学生姓名，所在系，系主任，课程名称课程名称，成绩，成绩）R1（学生学号学生学号,课程名称课程名称,成绩）R2（学生学号学生学号，学生姓名，学生姓名，所在系，系主任所在系，系主任）R1（学生学号学生学号,

6、课程名称课程名称,成绩）R3（学生学号学生学号，学生姓名，学生姓名，所在系所在系）R4（所在系所在系，系主任，系主任）10第第13讲讲 模式分解模式分解分解的概念 模式分解的概念模式分解的概念R（学生学号学生学号，学生姓名，所在系，系主任，学生姓名，所在系，系主任，课程课程名称名称，成绩，成绩 学生学号学生学号学生姓名，学生学号学生姓名，学生学号所所在系，所在系在系，所在系系主任，（学生学号，课程名称）系主任，（学生学号，课程名称）成绩成绩 1=R1(学生学号，课程名称学生学号，课程名称，成绩，成绩,（学生学号，课程（学生学号，课程名称）名称）成绩成绩),R3(学生学号学生学号，学生姓名，所在

7、系，学生姓名，所在系,学生学号学生学号学生学生姓名，学生学号姓名，学生学号所在系所在系),R4(所在系所在系，系主任，系主任,所在系所在系系主任系主任)11第第13讲讲 模式分解模式分解分解的概念 模式分解的概念模式分解的概念R（学生学号学生学号，学生姓名，所在系，系主任，学生姓名，所在系，系主任，课程名课程名称称，成绩，成绩 学生学号学生学号学生姓名，学生学号学生姓名，学生学号所在系，所在系，所在系所在系系主任，（学生学号，课程名称）系主任，（学生学号，课程名称）成绩成绩 2=R1（学生学号）（学生学号）,R2（学生姓名）（学生姓名）,R3（所在系）（所在系）,R4（系主任）（系主任）,R5

8、（课程名称）（课程名称）,R6（成绩）（成绩）U=Ui，并且没有，并且没有Ui Uj，1i，jn Fi是是F在在Ui上的投影不存在非平凡的函数依赖。上的投影不存在非平凡的函数依赖。不具有无损连接性不具有无损连接性12第第13讲讲 模式分解模式分解分解的概念 模式分解的概念模式分解的概念R（学生学号学生学号，学生姓名，所在系，系主任，学生姓名，所在系，系主任，课程名称课程名称，成绩成绩 学生学号学生学号学生姓名，学生学号学生姓名，学生学号所在系，所在所在系，所在系系系主任，（学生学号，课程名称）系主任，（学生学号，课程名称）成绩成绩 3=R1(学生学号，课程名称学生学号，课程名称，成绩，成绩,（

9、学生学号，课程）（学生学号，课程）成绩成绩),R2(学生学号学生学号，学生姓名，所在系，学生姓名，所在系,学生学号学生学号学生姓学生姓名，学生学号名，学生学号所在系所在系),R3(学生学号学生学号，系主任，系主任,学生学号学生学号系主任系主任)U=Ui，并且没有，并且没有Ui Uj，1i,jn Fi是是F在在Ui上的投影。上的投影。没有保持函数依赖没有保持函数依赖13第第13讲讲 模式分解模式分解分解的概念一个关系模式的分解并不是唯一的。一个关系模式的分解并不是唯一的。理想的分解应该是既具有无损连接性又保持函理想的分解应该是既具有无损连接性又保持函数依赖，这样的分解是等价分解。数依赖，这样的分

10、解是等价分解。等价分解等价分解分解具有无损连接性，即数据等价分解具有无损连接性，即数据等价分解保持函数依赖，即语义等价分解保持函数依赖，即语义等价分解既具有无损连接性又保持函数依赖，即数据等分解既具有无损连接性又保持函数依赖，即数据等价并且语义等价价并且语义等价模式分解的概念模式分解的概念14第第13讲讲 模式分解模式分解无损连接分解无损连接分解无损连接分解设设=R1（U1,F1），），Rk（Uk,Fk）是是R（U,F）的一个分解，）的一个分解，r是是R（U,F）的一个关）的一个关系，则系，则 Ri(r)=t.Ui|t r为为r在子模式在子模式Ri上的投影，上的投影，m(r)=R1(r)R2(

11、r)Rk(r)是是r在在中各关系模式上投影的连接。中各关系模式上投影的连接。若对若对R的任何一个关系的任何一个关系r均有均有r=m(r)成成立，则称立，则称分解分解具有无损连接性具有无损连接性。分解是无损分解15第第13讲讲 模式分解模式分解算法：检验一个分解是否是无损分解输入：输入：关系模式关系模式R（U，F），），U=A1,A2,An；R上的分解上的分解=R1（U1,F1）,R2（U2,F2）,Rk（Uk,Fk）。设设F是最小函数依赖集。是最小函数依赖集。输出：输出：判断判断相对于相对于F是否具有无损分解特性。是否具有无损分解特性。无损连接分解无损连接分解16第第13讲讲 模式分解模式分解

12、无损连接分解无损连接分解检验一个分解是否无损的算法步骤步骤A1AnR1（U1,F1）a1 ：Rk（Uk,Fk）bkn1 1）建立一张建立一张k行行n列的表，列的表，每行对应分解中的一个关每行对应分解中的一个关系模式系模式Ri，每列对应一个，每列对应一个属性属性Aj，若属性，若属性Aj Ui，则在则在i行行j列处填列处填aj，否则，否则填填bij。A1 U1An Uk17第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。

13、试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b53b54a5初始状态1 1）建立一张建立一张k行行n列的表，列的表，每行对应分解中的一个关每行对应分解中的一个关系模式系模式Ri，每列对应一个，每列对应一个属性属性Aj，若属性，若属性Aj Ui，则在则在i行行j列处填列处填aj，否则，否则填填bij。18第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，C

14、EA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b53b54a5初始状态2 2）把表格看成模式）把表格看成模式R R的的一个关系，反复检查一个关系，反复检查F F中的每个函数依赖在表中的每个函数依赖在表格中是成立，若不成立，格中是成立，若不成立，则修改表格中的值。则修改表格中的值。19第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设

15、有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12 b13 a4b15R2(AB)a1a2b23 b24 b25R3(BE)b31a2b33 b34 a5R4(CDE)b41b42 a3a4a5R5(AE)a1b52 b53 b54 a5初始状态2 2）对每一形如对每一形如XY 的的FD做如下做如下操作：操作：检查检查X中的属性所对应的列，找中的属性所对应的列，找出出X相等的行，将这些行中对应的相等的行，将这些行中对应的Y中的

16、属性列所对应的符号改为一中的属性列所对应的符号改为一致。致。即若其中之一为即若其中之一为aj，则都改成，则都改成aj；否则，否则，将其都改成这些列中行将其都改成这些列中行号最小的符号号最小的符号bij。对F的一次扫描20第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(

17、CDE)b41b42a3a4a5R5(AE)a1b52b53b54a5AC21第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13b54a5AC22第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有

18、关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13b54a5ACBC23第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R

19、5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b13b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13b54a5ACBC24第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3

20、(BE)b31a2b13b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13b54a5ACBCCD25第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)b31a2b13a4a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13a4a5ACBCCD26第第13讲讲

21、模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)b31a2b13a4a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13a4a5ACBCCDDEC27第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(

22、AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12a3a4b15R2(AB)a1a2a3a4b25R3(BE)b31a2a3a4a5R4(CDE)b41b42a3a4a5R5(AE)a1b52a3a4a5ACBCCDDEC28第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12a3a4

23、b15R2(AB)a1a2a3a4b25R3(BE)b31a2a3a4a5R4(CDE)b41b42a3a4a5R5(AE)a1b52a3a4a5ACBCCDDECCEA29第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12a3a4b15R2(AB)a1a2a3a4b25R3(BE)a1a2a3a4a5R4(CDE)a1b42a3a4a5R5(AE)a1b52a3a

24、4a5ACBCCDDECCEA30第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1（AD）a1b12a3a4b15R2（AB）a1a2a3a4b25R3（BE）a1a2 a3 a4 a5R4（CDE）a1b42a3a4a5R5（AE）a1b52a3a4a5ACBCCDDECCEA31第第13讲讲 模式分解模式分解无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE

25、，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)a1a2 a3 a4 a5R4(CDE)a1b42a3a4a5R5(AE)a1b52a3a4a53 3）若表有变化，则返）若表有变化，则返回步骤回步骤2)2)，否则算法终，否则算法终止。止。若某次修改后，有一若某次修改后，有一行全为行全为a a1 1,a,a2 2,a,an n，则，则算法结束。算法结束。32第第13讲讲 模式分解模式分解无损连接分解无

26、损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)a1a2 a3 a4 a5R4(CDE)a1b42a3a4a5R5(AE)a1b52a3a4a5定理：定理：为无损连接分解的充为无损连接分解的充分必要条件是算法终止分必要条件是算法终止时，表中有一行为时，表中有一行为a1,a2,an。33第第13讲讲 模式分解模式分解判断一个关系模式分解成两个关系

27、模式是否为无损分解的方法定理：定理：设设=R1(U1)，R2(U2)是是R(U)的一个分解，则的一个分解，则为无损分解的充分必要条件为为无损分解的充分必要条件为 （U1U2）（U1-U2）F+或或（U1U2）（U2-U1）F+无损连接分解无损连接分解34第第13讲讲 模式分解模式分解无损连接分解无损连接分解证明：用检验分解无损算法构造的如下初始表。表中a和b的下标都已省略充分性充分性 因为（因为（U1U2）（U1-U2），则算法），则算法8-2终止时，终止时，对应于对应于(U1-U2)的的bbb全为全为a，因此，因此，=R1(U1)，R2(U2)是是R（U）的一个无损连接分解。）的一个无损连接

28、分解。必要性必要性 若若=R1(U1)，R2(U2)是是R（U）的一个无损连接）的一个无损连接分解，则算法终止时，表中必有一行全为分解，则算法终止时，表中必有一行全为a，假设，假设R1行全行全为为a，则（，则（U1-U2）所对应的元素都应变为）所对应的元素都应变为a。由于在表。由于在表中，只有（中，只有（U1U2）所对应的列的元素相同。设）所对应的列的元素相同。设U1-U2中有一个属性中有一个属性Ai，则根据算法将，则根据算法将Ai所对应的元素都改为所对应的元素都改为a，则必有，则必有SAi F+，且，且S（U1U2）。根据自反律有）。根据自反律有（U1U2）S；根据传递律有（；根据传递律有（

29、U1U2）Ai，即，即Ai(U1U2)+。所以（。所以（U1-U2）(U1U2)+即即（U1U2）(U1U2)是是(U1U2)所对应的元素都变为所对应的元素都变为a的必要条件。的必要条件。35第第13讲讲 模式分解模式分解【例5-13】设有关系模式R（U，F），U=A,B,C,D,E，F=A BC，CDE，B D，E A。R的两个分解为1=R1(A,B,C)，R2(A,D,E)，2=R1(A,B,C)，R2(C,D,E)。试判断1、2是否为无损分解。无损连接分解无损连接分解解：对于分解对于分解1=R1（A,B,C），），R2（A,D,E）因为因为U1U2=A，U1-U2=BC，且，且A BC

30、F 所以所以U1U2U1-U2，1为无损分解。为无损分解。对于分解对于分解2=R1（A,B,C），），R2（C,D,E）因为因为U1U2=C，U1-U2=AB，U2-U1=DE，且且C AB F+，C DE F+（如何来判断？）（如何来判断？）即即U1U2U1-U2 F+或或U1U2U2-U1 F+，所以所以2为有损分解。为有损分解。36第第13讲讲 模式分解模式分解保持函数依赖分解保持函数依赖分解保持函数依赖 对于关系模式对于关系模式R（U,F），设），设=R1（U1,F1），），R2（U2,F2）,Rn（Un,Fn）是是R的一个分解，若的一个分解，若F+=(Fi)+，则称分解，则称分解保持

31、函数依赖。保持函数依赖。引理5.3 F+=G+的充分必要条件是FG+且G F+判断分解是否保持函数依赖的方法：令G=Fi，即只需判断FG+且GF+是否成立。而要判定FG+或GF+，只需逐一对F或G中的函数依赖XY考察Y是否属于XG 或X就行了。37第第13讲讲 模式分解模式分解分解的保持函数依赖性分解的保持函数依赖性【例】设关系模式R(ABCD)，F=AB，BC，CD，DA，试判断分解=R1(AB)，R2(BC)，R3(CD)是否保持函数依赖。解答：解答：1）要先根据分解的定义，确定分解后的函数依赖，然后）要先根据分解的定义，确定分解后的函数依赖，然后再加以判断。利用再加以判断。利用Armst

32、rong公理的传递律，可将公理的传递律，可将分解分解为为=R1(A,B，AB，BA),R2(B,C，BC，CB),R3(C,D，CD，DC)38第第13讲讲 模式分解模式分解分解的保持函数依赖性分解的保持函数依赖性【例】设关系模式R(ABCD)，F=AB，BC，CD，DA，试判断分解=R1(AB)，R2(BC)，R3(CD)是否保持函数依赖。解答：解答：2）判断）判断DA是否为是否为G所覆盖即可所覆盖即可 G=AB，BA，BC，CB，CD，DC 求得求得D=A，B，C，D 因为因为A D，所以，所以DA G+，故，故保持函数依赖。保持函数依赖。39第第13讲讲 模式分解模式分解模式分解算法模式

33、分解算法关系模式的规范化就是将低一级的关系模式分解为若干高一级的范式。对数据库应用设计而言，违反数据等价或依赖等价的分解很难说是一个好的模式设计。在函数依赖范畴内，希望分解的结果能达到BCNF，并且能保持无损连接性和函数依赖性。40第第13讲讲 模式分解模式分解模式分解算法模式分解算法这三个目标有时不能同时满足，一般只能做到如下几点：若分解保持函数依赖，那么模式总可以分解到若分解保持函数依赖，那么模式总可以分解到3NF，但不一定能达到，但不一定能达到BCNF；若分解具有无损连接性，那么模式一定能分解若分解具有无损连接性，那么模式一定能分解到到BCNF；若分解既保持函数依赖，又具有无损连接性，若

34、分解既保持函数依赖，又具有无损连接性，那么模式可以分解到那么模式可以分解到3NF，但不一定能达到，但不一定能达到BCNF。41第第13讲讲 模式分解模式分解模式分解算法模式分解算法低一级范式高一级范式分解保持函数依赖无损连接保持函数依赖无损连接3NF不一定BCNFBCNF关于模式分解的几个重要事实：42第第13讲讲 模式分解模式分解模式分解算法模式分解算法数据库设计者在设计关系数据库时，应权衡利弊，尽可能使数据库模式保持最好的特性。一般尽可能设计成一般尽可能设计成BCNF模式集；模式集；如果设计成如果设计成BCNF模式集达不到保持函数依赖模式集达不到保持函数依赖的特性，那么只能降低要求，设计成

35、的特性，那么只能降低要求，设计成3NF模式模式集，以求达到保持依赖和无损分解的特性。集，以求达到保持依赖和无损分解的特性。43第第13讲讲 模式分解模式分解模式分解算法模式分解算法分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法输入：关系模式输入：关系模式R（U，F）输出：输出：R的一个具有无损连接性且保持函的一个具有无损连接性且保持函数依赖的满足数依赖的满足3NF的分解的分解44第第13讲讲 模式分解模式分解模式分解算法模式分解算法分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法1）求）求F的最小覆盖的最小覆盖Fm，令，令F=Fm。2）若有）若有XA F，且，且XA=U，

36、输出，输出=R，算法结束。，算法结束。3）对）对F按具有相同左部的原则分组，即按具有相同左部的原则分组，即F中所有形如中所有形如XA1,XA2,，XAn的函数依赖为一组。每一分组的函数依赖为一组。每一分组中包含的函数依赖子集中包含的函数依赖子集Fi所涉及的全部属性组成一个属所涉及的全部属性组成一个属性集性集Ui。若。若Ui Uj（ij）就去掉）就去掉Ui。4）将）将R中不在中不在F中出现的属性，单独构成一属性集中出现的属性，单独构成一属性集Ui。45第第13讲讲 模式分解模式分解模式分解算法模式分解算法分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法5）将）将Ui及及F在在Ui上的投

37、影上的投影Fi构成一个关系模式构成一个关系模式Ri(Ui,Fi)，由，由于于F是最小函数依赖集，是最小函数依赖集，Ri(Ui,Fi)一定是属于以一定是属于以X为候选为候选键的键的3NF。并且。并且Fi一定被一定被Fi所包含，因此各关系模式所包含，因此各关系模式Ri(Ui,Fi)组成的分解组成的分解是保持函数依赖的。是保持函数依赖的。6）若某个若某个Ui中已包含中已包含R中的候选键，则该分解也就具有无中的候选键，则该分解也就具有无损连接性。损连接性。若若Ui中均不包含中均不包含R中的候选键，则在分解中的候选键，则在分解的的结果上再并入一个关系模式结果上再并入一个关系模式Rk(K,FK)，其中，其

38、中K为为R的某一的某一候选键，候选键，FK为为F在在K上的投影。上的投影。46第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例】关系模式R（U，F），其中U=E，G，H，I，J，F=EI，JI，IG，GHI，IHE，将R分解为3NF，并使之具有无损连接性和保持函数依赖特性。解答：解答：（1）F已为最小函数依赖集。已为最小函数依赖集。（2）没有类似）没有类似XA F，且，且XA=U的函数依赖。的函数依赖。（3）对）对F按具有相同左部的原则分组，得到每组所对应的属按具有相同左部的原则分组，得到每组所对应的属性集性集U1=EI、U2=IJ、U3=GI、U4=GHI、U5=EHI。因为。因为

39、U1 U5、U3 U4，所以去掉，所以去掉U1、U3。（4）R中的所有属性均在中的所有属性均在F中出现。中出现。47第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例(续)】关系模式R（U，F），其中U=E，G，H，I，J，F=EI，JI，IG，GHI，IHE，将R分解为3NF，并使之具有无损连接性和保持函数依赖特性。解答：解答：（5）将）将Ui及及F在在Ui上的投影上的投影Fi构成一个关系模式构成一个关系模式Ri（Ui,Fi），则分解），则分解=R1（I,J,JI），），R2（G,H,I，IG,GHI），），R3（E,H,I，EI,IHE）保持函数依赖，且分解后的每个关系模式均为保持

40、函数依赖，且分解后的每个关系模式均为3NF。（6）可确定）可确定R的一个候选键的一个候选键HJ，由于，由于Ui 均不包含均不包含HJ，则，则=R4（H,J），因此将，因此将R分解为分解为=R1（I,J,JI），），R2（G,H,I，IG,GHI），），R3（E,H,I，EI,IHE），），R4（H,J）。分解具有无损连接性，分解具有无损连接性，即为所求。即为所求。48第第13讲讲 模式分解模式分解模式分解算法模式分解算法算法：分解关系模式为满足BCNF的一个无损分解输入：关系模式输入：关系模式R（U，F）输出：输出：R的一个为的一个为BCNF的无损连接分解的无损连接分解。49第第13讲讲 模式

41、分解模式分解模式分解算法模式分解算法算法：分解关系模式为满足BCNF的一个无损分解方法：方法：1）令）令=R。2）检查）检查中每个关系模式是否均属于中每个关系模式是否均属于BCNF。若是，则算。若是，则算法终止。法终止。3）对）对中每一个不满足中每一个不满足BCNF的关系模式的关系模式S，做如下操作，做如下操作S中必有不满足中必有不满足BCNF的非平凡的函数依赖的非平凡的函数依赖XA，其中，其中X不是不是S的候选键。的候选键。对对S进行分解，分解为进行分解，分解为S1（XA）和）和S2（US-A），其中），其中US为为S的的属性集，用属性集，用S1和和S2取代取代中的中的S。返回步骤。返回步骤

42、(2)。由于由于U中属性有限，因而有限次循环后算法一定终止。中属性有限，因而有限次循环后算法一定终止。50第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例】有 关 系 模 式 R，U=C,T,H,I,S,G，F=CSG,CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。解答：解答：1）令）令=R2）检查）检查中每个关系模式是否均属于中每个关系模式是否均属于BCNF；H、S是是L类属性，且类属性，且HS F+=U，所以，所以HS为为 R的一个候的一个候 选键。选键。由此可判断由此可判断中关系模式中关系模式R不属于不属于BCNF。51第第13讲讲 模式分解模式分解模式分解

43、算法模式分解算法【例】有 关 系 模 式 R，U=C,T,H,I,S,G，F=CSG,CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。解答：解答：3）考虑）考虑CSG，CS不是不是R的候选键，将的候选键，将R分解为分解为=R1（CSG，CSG），），R2（CTHIS，CT,TH I,HIC,HSI）；R1是是BCNF，R2不是不是(R2的候选键仍为的候选键仍为HS)，需对，需对R2进一步进一步分解。分解。52第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例】有 关 系 模 式 R，U=C,T,H,I,S,G，F=CSG,CT,TH I,HIC,HSI，将R分解成具有

44、无损连接的BCNF。解答：解答：4）对于）对于 R2（CTHIS，CT,TH I,HIC,HSI）考虑考虑CT，C不是不是R2的候选键，将的候选键，将R2分解为分解为 =R21（CT，CT），），R22（CHIS，CH I,HIC,HSI）；(CT，TH I CH I)R21是是BCNF，R22不是不是(R22的候选键仍为的候选键仍为HS)，需对，需对R22进一步分解。进一步分解。53第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例】有 关 系 模 式 R，U=C,T,H,I,S,G，F=CSG,CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。解答：解答：对于对于R

45、22（CHIS，CH I,HIC,HSI）考虑考虑CH I，CH不是不是R22的候选键，将的候选键，将 分解为分解为 =R221（CHI，CH I，HIC），），R222（CHS，HSC）；R221 和和R222均是均是BCNF，不需进一步分解。，不需进一步分解。54第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例】有 关 系 模 式 R，U=C,T,H,I,S,G，F=CSG,CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。解答：解答：因此，将因此，将R分解为分解为=R1（CSG，CSG），），R21（CT，CT），），R221（CHI，CH I，HIC），），R

46、222（CHS，HSC），即为所求。，即为所求。在关系模式在关系模式R222（CHS，HSC）中，中，包含包含R的的一个候选键一个候选键HS，利用算法，利用算法5.3可验证分解可验证分解具有无损连接性。具有无损连接性。55第第13讲讲 模式分解模式分解模式分解算法模式分解算法 【例】关系模式R(U,F)中U=ABCDEG,F=BGC,BDE,DGC,ADGBC,AGB,BD，完成下列问题：（1）求）求F的最小函数依赖集；的最小函数依赖集；（2）求解）求解R的候选键；的候选键；（3）判断）判断R最高满足第几范式；最高满足第几范式；（4）若若R不不满满足足3NF，将将R分分解解为为无无损损且且保保

47、持持函函数数依依赖赖的的3NF。56第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例(续 1)】关 系 模 式 R(U,F)中 U=ABCDEG,F=BGC,BDE,DGC,ADGBC,AGB,BD。（1）求）求F的最小函数依赖集；的最小函数依赖集；解答：解答：函数依赖右边属性单一化函数依赖右边属性单一化 将将ADGBC分解为分解为ADGB、ADGC，AGB，DGC，ADGB、ADGC为冗余依赖为冗余依赖 F=BGC,BDE,DGC,AGB,BD。57第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例(续 2)】关 系 模 式 R(U,F)中 U=ABCDEG,F=BGC,B

48、DE,DGC,ADGBC,AGB,BD。（1）求）求F的最小函数依赖集；的最小函数依赖集；解答：解答：F=BGC,BDE,DGC,AGB,BD去掉冗余的函数依赖去掉冗余的函数依赖 判断判断BGC是否冗余：是否冗余：令令G=BDE,DGC,AGB,BD BG=BGDEC;C BG，BGC冗余；冗余；F=BDE,DGC,AGB,BD 同理，同理，判断其他函数依赖不冗余，判断其他函数依赖不冗余，F不变。不变。58第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例(续 3)】关 系 模 式 R(U,F)中 U=ABCDEG,F=BGC,BDE,DGC,ADGBC,AGB,BD。（1）求）求F的

49、最小函数依赖集；的最小函数依赖集；解答：解答：F=BDE,DGC,AGB,BD 去掉各函数依赖左部冗余的属性。去掉各函数依赖左部冗余的属性。本题需考虑本题需考虑BDE,DGC,AGB。对于对于BDE，在决定因素中去掉，在决定因素中去掉B,DE，DF+D,不包含不包含E，B不冗余，不冗余，F不变。不变。在决定因素中去掉在决定因素中去掉D,BE，BF+BDE,包含包含E，D多余。多余。所以用所以用BE代替代替BDE。同理，对同理，对DGC,AGB进行判断，没有冗余属性。进行判断，没有冗余属性。Fm BE,DGC,AGB,BD 59第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例(续 4)

50、】关 系 模 式 R(U,F)中 U=ABCDEG,F=BGC,BDE,DGC,ADGBC,AGB,BD。（2）求解）求解R的候选键；的候选键；（3）判断）判断R最高满足第几范式；最高满足第几范式；解答：解答：在在 Fm BE,DGC,AGB,BD 中中 AG为为L类属性，且类属性，且AG F =U，所以，所以AG为为R的候选键。的候选键。R最高属于最高属于2NF。因因为为FmBE,DGC,AGB,BD 中中存存在在对对AG的传递依赖的传递依赖BD。60第第13讲讲 模式分解模式分解模式分解算法模式分解算法【例(续 5)】关 系 模 式 R(U,F)中 U=ABCDEG,F=BGC,BDE,D