第13讲模式分解-课件

第13讲模式分解关系模式的规范化设计关系模式的规范化设计所要解决的问题什么是什么是“好好”的关系数据模式的关系数据模式如何评价一个好的关系数据模式如何评价一个好的关系数据模式如何设计一个如何设计一个“好好”的关系数据模式的关系数据模式关系模式的规范化设计关系模式的规范化设计主要内容关系模式的设计问题关系模式的设计问题关系模式规范化的基本概念和理论关系模式规范化的基本概念和理论关系模式分解的理论基础和算法关系模式分解的理论基础和算法回顾回顾1NF2NF3NFBCNF去除非主属性对于候选键的部分函数依赖去除非主属性对于候选键的部分函数依赖去除非主属性对于去除非主属性对于候选候选键的传递函数依赖键的传递函数依赖去除主属性对于去除主属性对于候选候选键的部分和传递函数依赖键的部分和传递函数依赖去除不被候选键所蕴涵的非平凡的多值依赖去除不被候选键所蕴涵的非平凡的多值依赖4NF消除消除决定决定因素因素非码非码的非的非平凡平凡函数函数依赖依赖Armstrong公理系统逻辑蕴涵逻辑蕴涵 Armstrong公理系统推理规则公理系统推理规则 FD的逻辑蕴涵的逻辑蕴涵 函数依赖集函数依赖集F 的闭包的闭包F+属性集闭包属性集闭包 函数依赖集等价和最小函数依赖集函数依赖集等价和最小函数依赖集 候选码及其求解方法候选码及其求解方法 回顾回顾 主要内容模式分解的概念模式分解的概念分解的无损连接性和保持函数依赖性分解的无损连接性和保持函数依赖性 模式分解算法模式分解算法 模式分解模式分解分解的概念 设有一关系模式设有一关系模式R（U,F），若用一关系模），若用一关系模式的集合式的集合=R1（U1,F1），），R2（U2,F2），），Rn（Un,Fn）来取代，其中来取代，其中U=Ui，并，并且没有且没有Ui Uj，1i,jn，Fi是是F在在Ui上的投影。上的投影。则关系模式的集合则关系模式的集合为为R的一个分解的一个分解 =R1，R2，Rn模式分解的概念模式分解的概念分解的概念F在在Ui上的投影上的投影 Fi=XY|XY F+XY Ui 模式分解的概念模式分解的概念思考：思考：设有关系模式设有关系模式R（A，B，C，D），），F是是R上成立上成立的的FD集集F=ABC，DB，则，则 F在模式在模式ACD上的投上的投影为影为_；F在模式在模式AC上的投影为上的投影为_。ADC 空空大家学习辛苦了，还是要坚持继续保持安静继续保持安静分解的概念 模式分解的概念模式分解的概念【例】R(编号，连队，连长，科目，成绩),F=编号连队，连队连长，(编号，科目)成绩 【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩，F=学生学号学生姓名，学生学号所在系，所在系系主任，（学生学号，课程名称）成绩分解的概念 模式分解的概念模式分解的概念1NF2NF3NF去除非主属性对于键的部分函数依赖去除非主属性对于键的部分函数依赖去除非主属性对于键的传递函数依赖去除非主属性对于键的传递函数依赖R R（学生学号，学生姓名，所在系，系主任，课程名称，成绩学生学号，学生姓名，所在系，系主任，课程名称，成绩）R1（学生学号学生学号,课程名称课程名称,成绩）R2（学生学号，学生姓名，学生学号，学生姓名，所在系，系主任所在系，系主任）R1（学生学号学生学号,课程名称课程名称,成绩）R3（学生学号学生学号，学生姓名，学生姓名，所在系所在系）R4（所在系，系主任所在系，系主任）分解的概念 模式分解的概念模式分解的概念R（学生学号，学生姓名，所在系，系主任，课程学生学号，学生姓名，所在系，系主任，课程名称，成绩名称，成绩 学生学号学生学号学生姓名，学生学号学生姓名，学生学号所所在系，所在系在系，所在系系主任，（学生学号，课程名称）系主任，（学生学号，课程名称）成绩成绩 1=R1(学生学号，课程名称，成绩学生学号，课程名称，成绩,（学生学号，课程（学生学号，课程名称）名称）成绩成绩),R3(学生学号，学生姓名，所在系学生学号，学生姓名，所在系,学生学号学生学号学生学生姓名，学生学号姓名，学生学号所在系所在系),R4(所在系，系主任所在系，系主任,所在系所在系系主任系主任)分解的概念 模式分解的概念模式分解的概念R（学生学号，学生姓名，所在系，系主任，课程名学生学号，学生姓名，所在系，系主任，课程名称，成绩称，成绩 学生学号学生学号学生姓名，学生学号学生姓名，学生学号所在系，所在系，所在系所在系系主任，（学生学号，课程名称）系主任，（学生学号，课程名称）成绩成绩 2=R1（学生学号）（学生学号）,R2（学生姓名）（学生姓名）,R3（所在系）（所在系）,R4（系主任）（系主任）,R5（课程名称）（课程名称）,R6（成绩）（成绩）U=Ui，并且没有，并且没有Ui Uj，1i，jn Fi是是F在在Ui上的投影不存在非平凡的函数依赖。上的投影不存在非平凡的函数依赖。不具有无损连接性不具有无损连接性分解的概念 模式分解的概念模式分解的概念R（学生学号，学生姓名，所在系，系主任，课程名称，学生学号，学生姓名，所在系，系主任，课程名称，成绩成绩 学生学号学生学号学生姓名，学生学号学生姓名，学生学号所在系，所在所在系，所在系系系主任，（学生学号，课程名称）系主任，（学生学号，课程名称）成绩成绩 3=R1(学生学号，课程名称，成绩学生学号，课程名称，成绩,（学生学号，课程）（学生学号，课程）成绩成绩),R2(学生学号，学生姓名，所在系学生学号，学生姓名，所在系,学生学号学生学号学生姓学生姓名，学生学号名，学生学号所在系所在系),R3(学生学号，系主任学生学号，系主任,学生学号学生学号系主任系主任)U=Ui，并且没有，并且没有Ui Uj，1i,jn Fi是是F在在Ui上的投影。上的投影。没有保持函数依赖没有保持函数依赖分解的概念一个关系模式的分解并不是唯一的。一个关系模式的分解并不是唯一的。理想的分解应该是既具有无损连接性又保持函理想的分解应该是既具有无损连接性又保持函数依赖，这样的分解是等价分解。数依赖，这样的分解是等价分解。等价分解等价分解分解具有无损连接性，即数据等价分解具有无损连接性，即数据等价分解保持函数依赖，即语义等价分解保持函数依赖，即语义等价分解既具有无损连接性又保持函数依赖，即数据等分解既具有无损连接性又保持函数依赖，即数据等价并且语义等价价并且语义等价模式分解的概念模式分解的概念无损连接分解无损连接分解无损连接分解设设=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(r)Rn(r)是是r在在中各关系模式上投影的连接。中各关系模式上投影的连接。若对若对R的任何一个关系的任何一个关系r均有均有r=m(r)成成立，则称分解立，则称分解具有无损连接性。具有无损连接性。分解是无损分解算法：检验一个分解是否是无损分解输入：输入：关系模式关系模式R（U，F），），U=A1,A2,An；R上的分解上的分解=R1（U1,F1）,R2（U2,F2）,Rk（Uk,Fk）。设设F是最小函数依赖集。是最小函数依赖集。输出：输出：判断判断相对于相对于F是否具有无损分解特性。是否具有无损分解特性。无损连接分解无损连接分解无损连接分解无损连接分解检验一个分解是否无损的算法步骤步骤1 1）建立一张建立一张k行行n列的表，列的表，每行对应分解中的一个关每行对应分解中的一个关系模式系模式Ri，每列对应一个，每列对应一个属性属性Aj，若属性，若属性Aj Ui，则在则在i行行j列处填列处填aj，否则，否则填填bij。A1 U1An Uk无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。初始状态1 1）建立一张建立一张k行行n列的表，列的表，每行对应分解中的一个关每行对应分解中的一个关系模式系模式Ri，每列对应一个，每列对应一个属性属性Aj，若属性，若属性Aj Ui，则在则在i行行j列处填列处填aj，否则，否则填填bij。无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。初始状态2 2）把表格看成模式）把表格看成模式R R的的一个关系，反复检查一个关系，反复检查F F中的每个函数依赖在表中的每个函数依赖在表格中是成立，若不成立，格中是成立，若不成立，则修改表格中的值。则修改表格中的值。无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。初始状态2 2）对每一形如对每一形如XY 的的FD做如下做如下操作：操作：检查检查X中的属性所对应的列，找中的属性所对应的列，找出出X相等的行，将这些行中对应的相等的行，将这些行中对应的Y中的属性列所对应的符号改为一中的属性列所对应的符号改为一致。即若其中之一为致。即若其中之一为aj，则都改成，则都改成aj；否则，将其都改成这些列中行；否则，将其都改成这些列中行号最小的符号号最小的符号bij。对F的一次扫描无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。AC无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。AC无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ACBC无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ACBC无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ACBCCD无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ACBCCD无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ACBCCDDEC无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ACBCCDDEC无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ACBCCDDECCEA无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ACBCCDDECCEA无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。ACBCCDDECCEA无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。3 3）若表有变化，则返）若表有变化，则返回步骤回步骤2)2)，否则算法终，否则算法终止。止。若某次修改后，有一若某次修改后，有一行全为行全为a a1 1,a,a2 2,a,an n，则，则算法结束。算法结束。无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是R的一个分解。试判断是否为无损分解。定理：定理：为无损连接分解的充为无损连接分解的充分必要条件是算法终止分必要条件是算法终止时，表中有一行为时，表中有一行为a1,a2,an。判断一个关系模式分解成两个关系模式是否为无损分解的方法定理：定理：设设=R1(U1)，R2(U2)是是R(U)的一个分解，则的一个分解，则为无损分解的充分必要条件为为无损分解的充分必要条件为 （U1U2）（U1-U2）F+或或（U1U2）（U2-U1）F+无损连接分解无损连接分解无损连接分解无损连接分解证明：用检验分解无损算法构造的如下初始表。表中a和b的下标都已省略充分性充分性 因为（因为（U1U2）（U1-U2），则算法），则算法8-2终止时，终止时，对应于对应于(U1-U2)的的bbb全为全为a，因此，因此，=R1(U1)，R2(U2)是是R（U）的一个无损连接分解。）的一个无损连接分解。必要性必要性 若若=R1(U1)，R2(U2)是是R（U）的一个无损连接）的一个无损连接分解，则算法终止时，表中必有一行全为分解，则算法终止时，表中必有一行全为a，假设，假设R2行全行全为为a，则（，则（U1-U2）所对应的元素都应变为）所对应的元素都应变为a。由于在表。由于在表中，只有（中，只有（U1U2）所对应的列的元素相同。设）所对应的列的元素相同。设U1-U2中有一个属性中有一个属性Ai，则根据算法将，则根据算法将Ai所对应的元素都改为所对应的元素都改为a，则必有，则必有SAi F+，且，且S（U1U2）。根据自反律有）。根据自反律有（U1U2）S；根据传递律有（；根据传递律有（U1U2）Ai，即，即Ai(U1U2)+。所以（。所以（U1-U2）(U1U2)+即即（U1U2）(U1U2)是是(U1U2)所对应的元素都变为所对应的元素都变为a的必要条件。的必要条件。【例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 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为有损分解。为有损分解。保持函数依赖分解保持函数依赖分解保持函数依赖 对于关系模式对于关系模式R（U,F），设），设=R1（U1,F1），），R2（U2,F2）,Rn（Un,Fn）是是R的一个分解，的一个分解，若若F+=(Fi)+，则称分解，则称分解保持函数依赖。保持函数依赖。引理5.3 F+=G+的充分必要条件是FG+且G F+判断分解是否保持函数依赖的方法：令G=Fi，即只需判断FG+且GF+是否成立。而要判定FG+或GF+，只需逐一对F或G中的函数依赖XY考察Y是否属于XG 或X就行了。分解的保持函数依赖性分解的保持函数依赖性【例】设关系模式R(ABCD)，F=AB，BC，CD，DA，试判断分解=R1(AB)，R2(BC)，R3(CD)是否保持函数依赖。解答：解答：1）要先根据分解的定义，确定分解后的函数依赖，然后）要先根据分解的定义，确定分解后的函数依赖，然后再加以判断。利用再加以判断。利用Armstrong公理的传递律，可将公理的传递律，可将分解分解为为=R1(A,B，AB，BA),R2(B,C，BC，CB),R3(C,D，CD，DC)分解的保持函数依赖性分解的保持函数依赖性【例】设关系模式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+，故，故保持函数依赖。保持函数依赖。模式分解算法模式分解算法关系模式的规范化就是将低一级的关系模式分解为若干高一级的范式。对数据库应用设计而言，违反数据等价或依赖等价的分解很难说是一个好的模式设计。在函数依赖范畴内，希望分解的结果能达到BCNF，并且能保持无损连接性和函数依赖性。模式分解算法模式分解算法这三个目标有时不能同时满足，一般只能做到如下几点：若分解保持函数依赖，那么模式总可以分解到若分解保持函数依赖，那么模式总可以分解到3NF，但不一定能达到，但不一定能达到BCNF；若分解具有无损连接性，那么模式一定能分解若分解具有无损连接性，那么模式一定能分解到到BCNF；若分解既保持函数依赖，又具有无损连接性，若分解既保持函数依赖，又具有无损连接性，那么模式可以分解到那么模式可以分解到3NF，但不一定能达到，但不一定能达到BCNF。模式分解算法模式分解算法低一级范式高一级范式分解保持函数依赖无损连接保持函数依赖无损连接3NF不一定BCNFBCNF关于模式分解的几个重要事实：模式分解算法模式分解算法数据库设计者在设计关系数据库时，应权衡利弊，尽可能使数据库模式保持最好的特性。一般尽可能设计成一般尽可能设计成BCNF模式集；模式集；如果设计成如果设计成BCNF模式集达不到保持函数依赖模式集达不到保持函数依赖的特性，那么只能降低要求，设计成的特性，那么只能降低要求，设计成3NF模式模式集，以求达到保持依赖和无损分解的特性。集，以求达到保持依赖和无损分解的特性。模式分解算法模式分解算法分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法输入：关系模式输入：关系模式R（U，F）输出：输出：R的一个具有无损连接性且保持函的一个具有无损连接性且保持函数依赖的满足数依赖的满足3NF的分解的分解模式分解算法模式分解算法分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法1）求）求F的最小覆盖的最小覆盖Fm，令，令F=Fm。2）若有）若有XA F，且，且XA=U，输出，输出=R，算法结束。，算法结束。3）对）对F按具有相同左部的原则分组，即按具有相同左部的原则分组，即F中所有形如中所有形如XA1,XA2,，XAn的函数依赖为一组。每一分组中包的函数依赖为一组。每一分组中包含的函数依赖子集含的函数依赖子集Fi所涉及的全部属性组成一个属性集所涉及的全部属性组成一个属性集Ui。若。若Ui Uj（ij）就去掉）就去掉Ui。4）将）将R中不在中不在F中出现的属性，单独构成一属性集中出现的属性，单独构成一属性集Ui。模式分解算法模式分解算法分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法5）将）将Ui及及F在在Ui上的投影上的投影Fi构成一个关系模式构成一个关系模式Ri(Ui,Fi)，由于，由于F是最小函数依赖集，是最小函数依赖集，Ri(Ui,Fi)一定是属于以一定是属于以X为候选键的为候选键的3NF。并且。并且Fi一定被一定被Fi所包含，因此各关系模式所包含，因此各关系模式Ri(Ui,Fi)组成的分解组成的分解是保持函数依赖的。是保持函数依赖的。6）若某个）若某个Ui中已包含中已包含R中的候选键，则该分解也就具有无损中的候选键，则该分解也就具有无损连接性。若连接性。若Ui中均不包含中均不包含R中的候选键，则在分解中的候选键，则在分解的结果的结果上再并入一个关系模式上再并入一个关系模式Rk(K,FK)，其中，其中K为为R的某一候选键，的某一候选键，FK为为F在在K上的投影。上的投影。模式分解算法模式分解算法【例】关系模式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。因为。因为U1 U5、U3 U4，所以去掉，所以去掉U1、U3。（4）R中的所有属性均在中的所有属性均在F中出现。中出现。模式分解算法模式分解算法【例】关系模式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）保持函数依赖，且分解后的每个关系模式均为保持函数依赖，且分解后的每个关系模式均为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）。分解具有无损连接性，。分解具有无损连接性，即为所求。即为所求。模式分解算法模式分解算法算法：分解关系模式为满足BCNF的一个无损分解输入：关系模式输入：关系模式R（U，F）输出：输出：R的一个为的一个为BCNF的无损连接分解的无损连接分解。模式分解算法模式分解算法算法：分解关系模式为满足BCNF的一个无损分解方法：方法：1）令）令=R。2）检查）检查中每个关系模式是否均属于中每个关系模式是否均属于BCNF。若是，则算。若是，则算法终止。法终止。3）对）对中每一个不满足中每一个不满足BCNF的关系模式的关系模式S，做如下操作，做如下操作S中必有不满足中必有不满足BCNF的非平凡的函数依赖的非平凡的函数依赖XA，其中，其中X不是不是S的候选键。的候选键。对对S进行分解，分解为进行分解，分解为S1（XA）和）和S2（US-A），其中），其中US为为S的的属性集，用属性集，用S1和和S2取代取代中的中的S。返回步骤。返回步骤(2)。由于由于U中属性有限，因而有限次循环后算法一定终止。中属性有限，因而有限次循环后算法一定终止。模式分解算法模式分解算法【例】有 关 系 模 式 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。模式分解算法模式分解算法【例】有 关 系 模 式 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进一步进一步分解。分解。模式分解算法模式分解算法【例】有 关 系 模 式 R，U=C,T,H,I,S,G，F=CSG,CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。解答：解答：3）对于）对于 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进一步分解。进一步分解。模式分解算法模式分解算法【例】有 关 系 模 式 R，U=C,T,H,I,S,G，F=CSG,CT,TH I,HIC,HSI，将R分解成具有无损连接的BCNF。解答：解答：对于对于R22（CHIS，CH I,HIC,HSI）考虑考虑CH I，CH不是不是R22的候选键，将的候选键，将 分解为分解为 =R221（CHI，CH I，HIC），），R222（CHS，HSC）；R221 和和R222均是均是BCNF，不需进一步分解。，不需进一步分解。模式分解算法模式分解算法【例】有 关 系 模 式 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），），R222（CHS，HSC），即为所求。，即为所求。在关系模式在关系模式R222（CHS，HSC）中，）中，包含包含R的的一个候选键一个候选键HS，利用算法，利用算法5.3可验证分解可验证分解具有无损连接性。具有无损连接性。模式分解算法模式分解算法 【例】关系模式R(U,F)中U=ABCDEG,F=BGC,BDE,DGC,ADGBC,AGB,BD，完成下列问题：（1）求）求F的最小函数依赖集；的最小函数依赖集；（2）求解）求解R的候选键；的候选键；（3）判断）判断R最高满足第几范式；最高满足第几范式；（4）若若R不不满满足足3NF，将将R分分解解为为无无损损且且保保持持函函数数依依赖赖的的3NF。模式分解算法模式分解算法【例】关系模式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。模式分解算法模式分解算法【例】关系模式R(U,F)中U=ABCDEG,F=BGC,BDE,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不变。不变。模式分解算法模式分解算法【例】关系模式R(U,F)中U=ABCDEG,F=BGC,BDE,DGC,ADGBC,AGB,BD。（1）求）求F的最小函数依赖集；的最小函数依赖集；解答：解答：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 模式分解算法模式分解算法【例】关系模式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。模式分解算法模式分解算法【例】关系模式R(U,F)中U=ABCDEG,F=BGC,BDE,DGC,ADGBC,AGB,BD。（4）若若R不不满满足足3NF，将将R分分解解为为无无损损且且保保持持函函数数依依赖赖的的3NF。解答：解答：Fm BE,DGC,AGB,BD 按算法，对按算法，对Fm按具有相同左部的原则分组，按具有相同左部的原则分组，U1=BDE、U2=DGC、U3=AGB，因此将，因此将R分解为分解为 =R1（B,D,E，BE,BD），），R2（C，D，G，DGC），），R3（A，B，G，AGB）因为候选键因为候选键AG U3，则所求分解，则所求分解具有无损连接性并具有无损连接性并保持函数依赖，且每个子模式为保持函数依赖，且每个子模式为3NF。小结小结在函数依赖和多值依赖的范畴内讨论了关系模式的规范化，给出了范式的概念。讨论了将低一级的范式分解为若干高一级的范式的理论基础Armstrong公理以及判断模式的候选键的方法。小结小结给出了一组模式与一个关系模式等价的含义，介绍了几种在不同含义下模式分解的算法，以及最终所能达到的“等价”效果，即达到第几范式，是否具有无损连接性，是否保持函数依赖。总是从一个关系模式出发实行分解。总是从一个关系模式出发实行分解。采用了两种关系运算采用了两种关系运算投影和自然连接。投影和自然连接。小结小结规范化理论为数据库设计提供了理论的指南和工具对关系模式进行规范化的主要目的是消对关系模式进行规范化的主要目的是消除数据冗余和更新异常；除数据冗余和更新异常；规范化是通过模式分解来实现的，分解规范化是通过模式分解来实现的，分解后的关系模式具有较少的列，能描述的后的关系模式具有较少的列，能描述的信息也相应的减少了，或者说语义更纯信息也相应的减少了，或者说语义更纯了。了。小结小结并不是规范化程度越高，模式就越好，而必须结合应用环境和现实世界的具体情况合理地选择数据库模式。有时出于对数据库性能的考虑而允许数据库中有时出于对数据库性能的考虑而允许数据库中存在数据冗余，来获得比较好的性能。存在数据冗余，来获得比较好的性能。比如比如：1）复制某些数据列到一些表中以便更容易地访问而）复制某些数据列到一些表中以便更容易地访问而不必进行多表的连接。不必进行多表的连接。2）存储派生数据以加快数据处理过程。）存储派生数据以加快数据处理过程。3）撤消某些已分解的关系模式以减少多个表连接的）撤消某些已分解的关系模式以减少多个表连接的开销。开销。