《关系数据库理论》PPT课件.ppt

《《关系数据库理论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《关系数据库理论》PPT课件.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第14讲讲 关系数据库理论关系数据库理论 1 1北京林业大学北京林业大学 软件教研室软件教研室4.1 规范化问题的提出规范化问题的提出4.2 函数依赖函数依赖4.3 关系模式的分解关系模式的分解*4.4 关系模式的范式关系模式的范式4.5 关系模式的规范化关系模式的规范化 2 2北京林业大学北京林业大学 软件教研室软件教研室4.1 规范化问题的提出规范化问题的提出 4.1.1 规范化理论的主要内容规范化理论的主要内容关系数据库的规范化理论关系数据库的规范化理论 函数依赖函数依赖范式（范式（Normal Form）模式设计模式设计 核心，是模式分解和设计的基础 模式分解的标准 3 3北京林业大

2、学北京林业大学 软件教研室软件教研室4.1.2 不合理的关系模式存在的存储异常问题不合理的关系模式存在的存储异常问题 教学管理数据库教学管理数据库SCD(SNo，SN，Age，Dept，MN，CNo，Score)在此关系模式中填入一部分具体的数据在此关系模式中填入一部分具体的数据SNo SN Age Dept MN CNo Score S1 赵亦赵亦 17 计算机计算机 刘伟刘伟 C1 90S1 赵亦赵亦 17 计算机计算机 刘伟刘伟 C2 85 S2 钱尔钱尔 18 信息信息 王平王平 C557S2 钱尔钱尔 18 信息信息 王平王平 C680S2钱尔钱尔18信息信息王平王平C7 4 4北京

3、林业大学北京林业大学 软件教研室软件教研室SNo SN Age Dept MN CNo Score S1 赵亦赵亦 17 计算机计算机 刘伟刘伟 C1 90S1 赵亦赵亦 17 计算机计算机 刘伟刘伟 C2 85 S2 钱尔钱尔 18 信息信息 王平王平 C557S2 钱尔钱尔 18 信息信息 王平王平 C680S2钱尔钱尔18信息信息王平王平C7 该表出现的问题该表出现的问题 数据冗余数据冗余 插入异常插入异常 删除异常删除异常 更新异常更新异常 根本原因：属性间存根本原因：属性间存在着在着数据依赖关系数据依赖关系 包罗万象包罗万象 5 5北京林业大学北京林业大学 软件教研室软件教研室一个好

4、的关系模式应该具备以下四个条件：一个好的关系模式应该具备以下四个条件：（1）尽可能少的数据冗余；）尽可能少的数据冗余；（2）没有插入异常；）没有插入异常；（3）没有删除异常；）没有删除异常；（4）没有更新异常。）没有更新异常。SCD(SNo，SN，Age，Dept，MN，CNo，Score)S(SNo，SN，Age，Dept)SC(SNo，CNo，Score)D(Dept，MN)关系模式分解：关系模式分解：6 6北京林业大学北京林业大学 软件教研室软件教研室4.2 函数依赖函数依赖 4.2.1 函数依赖的定义函数依赖的定义定义定义4.1 SNo决定函数（决定函数（SN，Age，Dept）（SN

5、，Age，Dept）函数依赖于）函数依赖于SNo SCD(SNo，SN，Age，Dept，MN，CNo，Score)SNo一个学生一个学生SN，Age，Dept 惟一确定惟一确定 惟一确定惟一确定 7 7北京林业大学北京林业大学 软件教研室软件教研室4.2.2 函数依赖的逻辑蕴涵定义函数依赖的逻辑蕴涵定义 定义定义4.2 设设F是在关系模式是在关系模式R(U)上成立的函数依赖集合，上成立的函数依赖集合，X，Y是属性集是属性集U的子集，的子集，XY是一个函数依赖。如果从是一个函数依赖。如果从F中能够推导出中能够推导出XY，即如果对于，即如果对于R的每个满足的每个满足F的的关系关系r也满足也满足X

6、Y，则称，则称XY为为F的的逻辑蕴涵逻辑蕴涵（或（或F逻辑蕴涵逻辑蕴涵XY），记为），记为F|=XY。定义定义4.3 设设F是函数依赖集，被是函数依赖集，被F逻辑蕴涵的函数依赖的全体逻辑蕴涵的函数依赖的全体构成的集合，称为函数依赖集构成的集合，称为函数依赖集F的闭包（的闭包（Closure），），记为记为F+。即：。即：F+=XY|F|=XY 8 8北京林业大学北京林业大学 软件教研室软件教研室函数依赖的推理规则函数依赖的推理规则 Armstrong公理公理自反律：自反律：如果如果Y X U，则，则XY在在R上成立上成立 增广律增广律：若若XY在在R上成立，且上成立，且Z U，则，则XZYZ在

7、在R上也成立上也成立 传递律传递律：若若XY和和YZ在在R上成立，则上成立，则XZ在在R上也成立上也成立 9 9北京林业大学北京林业大学 软件教研室软件教研室Armstrong公理推论公理推论 合并律（合并律（Union rule）若若XY和和XZ在在R上成立，则上成立，则XYZ在在R上也成立上也成立 伪传递律（伪传递律（Pseudotransitivity rule）若若XY和和YWZ在在R上成立，则上成立，则XWZ在在R上也成立上也成立 分解律（分解律（Decomposition rule）若若XY和和ZY在在R上成立，则上成立，则XZ在在R上也成立上也成立复合律（复合律（Composit

8、ion）若若XY和和WZ在在R上成立，则上成立，则XWYZ在在R上也成立上也成立 1010北京林业大学北京林业大学 软件教研室软件教研室4.2.4 完全函数依赖与部分函数依赖完全函数依赖与部分函数依赖 设有关系模式设有关系模式R(U)，U是属性全集，是属性全集，X和和Y是是U的的子集：子集：如果如果XY，并且对于，并且对于X的任何一个真子集的任何一个真子集X，都有，都有X Y，则称，则称Y对对X完全函数依赖完全函数依赖，记作，记作X Y。如果如果XY，并且对于并且对于X的某个真子集的某个真子集X，有，有XY，则称则称Y对对X部分函数依赖部分函数依赖，记作，记作X Y。在关系模式在关系模式SCD

9、中，因为中，因为SNo Score，且，且CNo Score，所以有：，所以有：(SNo，CNo)Score。而。而SNoAge，所以，所以(SNo，CNo)Age fpffp1111北京林业大学北京林业大学 软件教研室软件教研室4.2.5 传递函数依赖传递函数依赖 设有关系模式设有关系模式R(U)，U是属性全集，是属性全集，X，Y，Z是是U的子集的子集 若若XY，但，但Y X，而，而YZ（Y X，Z Y），则称），则称Z对对X传递函数依赖传递函数依赖，记作：，记作：X Z。如果如果YX，则，则X Y，这时称，这时称Z对对X直接函数依赖，直接函数依赖，而不是传递函数依赖。而不是传递函数依赖。t

10、函数依赖函数依赖 完全函数依赖完全函数依赖 部分函数依赖部分函数依赖 传递函数依赖传递函数依赖 1212北京林业大学北京林业大学 软件教研室软件教研室4.2.6 属性集的闭包及其算法属性集的闭包及其算法 X+=属性属性A|XA在在F+中中 定理定理4.3 XY能用函数依赖推理规则推出的充分必要条件是能用函数依赖推理规则推出的充分必要条件是Y X+中中 算法算法4.1 result=X do if F中有某个函数依赖中有某个函数依赖YZ满足满足Y result then result=result Z while(result有所改变有所改变);1313北京林业大学北京林业大学 软件教研室软件教

11、研室4.2.7 候选键的求解理论和算法候选键的求解理论和算法 关键码的定义关键码的定义 如果如果XU在在R上成立（即上成立（即XU在在F+中），那么称中），那么称X是是R的一个超键。的一个超键。如果如果XU在在R上成立，但对上成立，但对X的任一真子集的任一真子集X都有都有XU不成立（即不成立（即XU不在不在F+中，或者中，或者X U），），那么称那么称X是是R上的一个候选键。上的一个候选键。快速求解候选键的一个充分条件快速求解候选键的一个充分条件 对于给定的关系模式对于给定的关系模式R(A1，An)和函数依赖集和函数依赖集F，可将其属性分为以下四类：可将其属性分为以下四类：fL类类R类类 N类

12、类 LR类类 1414北京林业大学北京林业大学 软件教研室软件教研室定理定理4.4 对于给定的关系模式对于给定的关系模式R及其函数依赖集及其函数依赖集F（1）若）若X（XR）是）是L类属性，则类属性，则X必为必为R的任一候选键的成员。的任一候选键的成员。（2）若）若X（XR）是）是L类属性，且类属性，且X+包含了包含了R的全部属性，则的全部属性，则X必必为为R的惟一候选键。的惟一候选键。（3）若）若X（XR）是）是R类属性，则类属性，则X不在任何候选键中。不在任何候选键中。（4）若）若X（XR）是）是N类属性，则类属性，则X包含在包含在R的任一候选键中。的任一候选键中。（5）若）若X（XR）是

13、）是R的的N类和类和L类属性组成的属性集，且类属性组成的属性集，且X+包含包含了了R的全部属性，则的全部属性，则X是是R的惟一候选键。的惟一候选键。1515北京林业大学北京林业大学 软件教研室软件教研室多属性函数依赖集候选键的求解算法多属性函数依赖集候选键的求解算法（1）属性分类（）属性分类（L、R、N和和LR）（2）若）若X+包含了包含了R的全部属性，转（的全部属性，转（5）；否则，转（）；否则，转（3）。）。（3）在）在Y中取一个属性中取一个属性A，求，求(XA)+，若它包含了，若它包含了R的全部属性，的全部属性，则转（则转（4）；否则，调换一属性反复进行这一过程，直到试完所）；否则，调换

14、一属性反复进行这一过程，直到试完所有有Y中的属性。中的属性。（4）如果已找出所有候选键，则转（）如果已找出所有候选键，则转（5）；否则在）；否则在Y中依次取两中依次取两个、三个、个、三个、，求它们的属性集的闭包，直到其闭包包含，求它们的属性集的闭包，直到其闭包包含R的全的全部属性。部属性。（5）停止，输出结果。）停止，输出结果。令令X代表代表L和和N类，类，Y代表代表LR类类1616北京林业大学北京林业大学 软件教研室软件教研室4.2.8 函数依赖推理规则的完备性函数依赖推理规则的完备性 定理定理4.5 函数依赖推理规则函数依赖推理规则A1，A2，A3是完备的是完备的（1）证明）证明F中每个函

15、数依赖中每个函数依赖VW在在r上成立。上成立。（2）证明）证明XY在关系在关系r上不成立。上不成立。综合（综合（1）和（）和（2）可知，只要）可知，只要XY不能用推理规则推出，那不能用推理规则推出，那么么F就不逻辑蕴涵就不逻辑蕴涵XY，也就是推理规则是完备的。，也就是推理规则是完备的。从函数依赖集从函数依赖集F使用推理规则推出的函数依赖必定在使用推理规则推出的函数依赖必定在F+中中 F+中的函数依赖都能从中的函数依赖都能从F集使用推理规则集推出集使用推理规则集推出 正确性：正确性：完备性：完备性：1717北京林业大学北京林业大学 软件教研室软件教研室4.2.9 函数依赖集的等价、覆盖和最小函数

16、依赖集函数依赖集的等价、覆盖和最小函数依赖集 等价定义等价定义4.8 关系模式关系模式R(U)的两个函数依赖集的两个函数依赖集F和和G，如果满足，如果满足F+=G+，则称，则称F和和G是等价的函数依赖集。记作：是等价的函数依赖集。记作：FG。如果。如果F和和G等价等价，就说，就说F覆盖覆盖G，或，或G覆盖覆盖F。无关定义无关定义4.9 设设F是属性集是属性集U上的函数依赖集，上的函数依赖集，XY是是F中的函数中的函数依赖。函数依赖中无关属性：依赖。函数依赖中无关属性：（1）如果）如果AX，且，且F逻辑蕴涵逻辑蕴涵(F-XY)(X-A)Y，则称属性则称属性A是是XY左部的无关属性。左部的无关属性

17、。（2）如果）如果AX，且，且(F-XY)X(Y-A)逻辑蕴涵逻辑蕴涵F，则称属性则称属性A是是XY右部的无关属性。右部的无关属性。（3）如果）如果XY的左右两边的属性都是无关属性，则函数依的左右两边的属性都是无关属性，则函数依赖赖XY称为无关函数依赖。称为无关函数依赖。1818北京林业大学北京林业大学 软件教研室软件教研室定义定义4.10 设设F是属性集是属性集U上的函数依赖集。如果上的函数依赖集。如果Fmin是是F的一个的一个最小函数依赖集，那么最小函数依赖集，那么Fmin应满足下列四个条件：应满足下列四个条件：（1）Fmin+=F+；（2）每个函数依赖的右边都是单属性；）每个函数依赖的右

18、边都是单属性；（3）Fmin中没有冗余的函数依赖（即在中没有冗余的函数依赖（即在Fmin中不存在这样的中不存在这样的函数依赖函数依赖XY，使得，使得Fmin与与Fmin-XY等价），即减少任等价），即减少任何一个函数依赖都将与原来的何一个函数依赖都将与原来的F不等价；不等价；（4）每个函数依赖的左边没有冗余的属性（即）每个函数依赖的左边没有冗余的属性（即Fmin中不存在这中不存在这样的函数依赖样的函数依赖XY，X有真子集有真子集W使得使得Fmin-XY WY与与Fmin等价），减少任何一个函数依赖左部的属性后，等价），减少任何一个函数依赖左部的属性后，都将与原来的都将与原来的F不等价。不等价。

19、1919北京林业大学北京林业大学 软件教研室软件教研室算法算法4.3 计算函数依赖集计算函数依赖集F的最小函数依赖集的最小函数依赖集G（1）对）对F中的任一函数依赖中的任一函数依赖XY，如果，如果Y=Y1,Y2,，Yk（k2）多于一个属性，就用分解律，分解为）多于一个属性，就用分解律，分解为XY1，XY2，XYk，替换，替换XY，得到一个，得到一个与与F等价的函数依赖集等价的函数依赖集G，G中每个函数依赖的右边中每个函数依赖的右边均为单属性。均为单属性。（2）去掉）去掉G中各函数依赖左部多余的属性。中各函数依赖左部多余的属性。（3）在）在G中消除冗余的函数依赖。中消除冗余的函数依赖。2020北

20、京林业大学北京林业大学 软件教研室软件教研室4.3 关系模式的分解关系模式的分解*4.3.1 模式分解问题模式分解问题 定义定义4.11 设有关系模式设有关系模式R(U)，R=R1R2Rk，=R1，R2，Rk。这里。这里称为称为R的一个分解，也称为的一个分解，也称为数据库模式数据库模式。泛关系模式泛关系模式泛关系泛关系数据库模式数据库模式数据库实例数据库实例 Rr=R1，R2，Rk=模式分解示意图模式分解示意图 衡量关系模式的分解是否可取衡量关系模式的分解是否可取分解是否具有无损连接分解是否具有无损连接分解是否保持了函数依赖分解是否保持了函数依赖2121北京林业大学北京林业大学 软件教研室软件

21、教研室4.3.2 无损连接分解无损连接分解 定义定义4.12设有设有R，F是是R上的函数依赖集，上的函数依赖集，=R1，R2，Rk。如果对如果对R中满足中满足F的每一个关系的每一个关系r，有，有r=R1(r)R2(r)Rk(r),那么就称分解那么就称分解相对于相对于F是是“无损连接分解无损连接分解”；否则称为；否则称为“损失分解损失分解”。定理定理4.6 设设=R1，R2，Rk是关系模式是关系模式R的一个的一个分解，分解，r是是R的任一关系，的任一关系，ri=Ri(r)（1ik）,那么有那么有下列性质：下列性质：（1）r m(r)；（2）若）若s=m(r)，则，则Ri(s)=ri；（3）m(m

22、(r)=m(r)，这个性质称为幂等性。，这个性质称为幂等性。2222北京林业大学北京林业大学 软件教研室软件教研室4.3.3 无损分解的测试算法无损分解的测试算法（1）构造一个）构造一个k行行n列的表格列的表格R，表中每一列对应一个属性，表中每一列对应一个属性Aj（1jn），每一行对应一个模式），每一行对应一个模式Ri（1ik）。如果）。如果Aj在在Ri中，中，则在表中的第则在表中的第i行第行第j列处填上符号列处填上符号aj，否则填上，否则填上bij。（2）把表格看成模式）把表格看成模式R的一个关系，根据的一个关系，根据F中的每个函数依赖，在中的每个函数依赖，在表中寻找表中寻找X分量上相等的行

23、，分别对分量上相等的行，分别对Y分量上的每一列做修改：分量上的每一列做修改：如果列中有一个是如果列中有一个是aj，那么这一列上（，那么这一列上（X相同的行）的元素都改成相同的行）的元素都改成aj；如果列中没有如果列中没有aj，那么这一列上（，那么这一列上（X相同的行）的元素都改成相同的行）的元素都改成bij（下标（下标ij取取i最小的那个）。最小的那个）。对对F中所有的函数依赖，反复地执行上述的修改操作，一直到表格不中所有的函数依赖，反复地执行上述的修改操作，一直到表格不能再修改为止（这个过程称为能再修改为止（这个过程称为“追踪追踪”过程）。过程）。（3）若修改到最后，表中有一行全为）若修改到

24、最后，表中有一行全为a，即，即a1a2an，那么称，那么称相相对于对于F是无损连接分解。是无损连接分解。2323北京林业大学北京林业大学 软件教研室软件教研室例例4-11 设有关系模式设有关系模式R(A，B，C，D)，R分解成分解成=AB，BC，CD，如果，如果R上成立的函数依赖集上成立的函数依赖集F=BA，CD，那么，那么相对于相对于F是否为无损连接分解？是否为无损连接分解？ABCDABa1a2 b13 b14 BCb21 a2 a3 b24 CDb31b32 a3 a4 BA a1CD a4修改后的表格中的第修改后的表格中的第二行为二行为a1a2a3a4，因此，因此，相对于相对于F是无是无

25、损连接分解损连接分解。2424北京林业大学北京林业大学 软件教研室软件教研室 定理定理4.7 设设=R1，R2是关系模式是关系模式R的一个分解，的一个分解，F是是R上成立的函数依赖集，那么分解上成立的函数依赖集，那么分解相对于相对于F是无损是无损分解的分解的充分必要条件充分必要条件是：是：(R1R2)(R1-R2)或或(R1R2)(R2-R1)当模式当模式R分解成两个模式分解成两个模式R1和和R2时，若两个模式的公共属时，若两个模式的公共属性（性（除外）能够函数决定除外）能够函数决定R1（或（或R2）中的其他属性，这）中的其他属性，这样的分解具有无损连接性。样的分解具有无损连接性。2525北京

26、林业大学北京林业大学 软件教研室软件教研室4.3.4 保持函数依赖的分解保持函数依赖的分解 定义定义4.13 设有关系模式设有关系模式R(U)，F是是R(U)上的函数依赖集，上的函数依赖集，Z是属性集是属性集U上的一个子集，上的一个子集，=R1，R2，Rk是是R的一个分解。的一个分解。F在在Z上的一个投影用上的一个投影用Z(F)表示：表示：Z(F)=XY|XYF+XYZ；F在在Ri上的一个投影用上的一个投影用Ri(F)表示：表示：=R1(r)R2(r)Rk(r)；如果有如果有F+=()+，则称，则称是保持函数依赖集是保持函数依赖集F的分解。的分解。一个无损连接分解不一定是保持函数依赖的一个无损

27、连接分解不一定是保持函数依赖的一个保持函数依赖的分解也不一定是无损连接的一个保持函数依赖的分解也不一定是无损连接的2626北京林业大学北京林业大学 软件教研室软件教研室4.4 关系模式的范式关系模式的范式 各种范式之间的关系各种范式之间的关系 2727北京林业大学北京林业大学 软件教研室软件教研室4.4.1 第一范式第一范式 定义定义4.14 如果关系模式如果关系模式R所有的属性均为简单属所有的属性均为简单属性，即每个属性都是不可再分的，则称性，即每个属性都是不可再分的，则称R属于第属于第一范式，简称一范式，简称1NF，记作，记作R1NF。1NF是关系模式应具备的最起码的条件。是关系模式应具备

28、的最起码的条件。第一范式可能具有大量的数据冗余，具有插入异常、第一范式可能具有大量的数据冗余，具有插入异常、删除异常和更新异常等弊端。删除异常和更新异常等弊端。如关系模式如关系模式SCD属于属于1NF，它既存在完全函数依赖，又存，它既存在完全函数依赖，又存在部分函数依赖和传递函数依赖在部分函数依赖和传递函数依赖。克服这些弊端的方法是用投影运算将关系分解，去掉克服这些弊端的方法是用投影运算将关系分解，去掉过于复杂的函数依赖关系，向更高一级的范式进行转过于复杂的函数依赖关系，向更高一级的范式进行转换。换。2828北京林业大学北京林业大学 软件教研室软件教研室4.4.2 第二范式第二范式 第二范式的

29、定义第二范式的定义 如果关系模式如果关系模式R1NF，且每个非主属性都完全函数，且每个非主属性都完全函数依赖于依赖于R的主关系键，则称的主关系键，则称R属于第二范式，简称属于第二范式，简称2NF，记作，记作R2NF。如：关系模式如：关系模式TCS（T，C，S）关系键关系键 （T，C，S）；主属性；主属性 T、C、S 不存在非主属性对主关系键的部分函数依赖，因此属于不存在非主属性对主关系键的部分函数依赖，因此属于2NF。从从1NF关系中消除非主属性对主关系键的部分函数依赖，则可得到关系中消除非主属性对主关系键的部分函数依赖，则可得到2NF如果如果R的关系键为单属性，或的关系键为单属性，或R的全体

30、属性均为主属性，则的全体属性均为主属性，则R2NF 2929北京林业大学北京林业大学 软件教研室软件教研室2NF规范化规范化 2NF规范化是指把规范化是指把1NF关系模式通过投影分解，转换关系模式通过投影分解，转换成成2NF关系模式的集合。关系模式的集合。例例4-15 将将SCD(SNo，SN，Age，Dept，MN，CNo，Score)规范为规范为2NF。学生学生SD(SNo,SN,Age,Dept,MN)学生与课程联系学生与课程联系SC(SNo,CNo,Score)SCD非主属性对主键完全函数依赖。因此，非主属性对主键完全函数依赖。因此，SD2NF，SC2NF。3030北京林业大学北京林业

31、大学 软件教研室软件教研室2NF的缺点的缺点 数据冗余数据冗余 插入异常插入异常 删除异常删除异常 更新异常更新异常 每个系名和系主任的名字存储的次数等于该系的学生人数每个系名和系主任的名字存储的次数等于该系的学生人数 当一个新系没有招生时，有关该系的信息无法插入当一个新系没有招生时，有关该系的信息无法插入 某系学生全部毕业而没有招生时，删除全部学生的记录也某系学生全部毕业而没有招生时，删除全部学生的记录也随之删除了该系的有关信息随之删除了该系的有关信息 更换系主任时，仍需改动较多的学生记录更换系主任时，仍需改动较多的学生记录 3131北京林业大学北京林业大学 软件教研室软件教研室4.4.3

32、第三范式第三范式 第三范式的定义第三范式的定义 如果关系模式如果关系模式R2NF，且每个非主属性都不传递函，且每个非主属性都不传递函数依赖于数依赖于R的主关系键，则称的主关系键，则称R属于第三范式，简称属于第三范式，简称3NF，记作，记作R3NF。如：如：SC(SNo，CNo，Score)函数依赖为函数依赖为(SNo，CNo)Score，非主属性，非主属性Score不传递不传递函数依赖于主关系键（函数依赖于主关系键（SNo，CNo），因此，），因此，SC3NF。又如：又如：SD(SNo，SN，Age，Dept，MN)SNoDep和和DeptMN SNo MN 非主属性非主属性MN与主关系键与主

33、关系键SNo间存在着传递函数依赖，所以间存在着传递函数依赖，所以SD 3NF。主关系键主关系键 非主属性非主属性 t非主属性非主属性 主关系键主关系键 3232北京林业大学北京林业大学 软件教研室软件教研室3NF规范化规范化算法算法4.6 把一个关系模式分解为把一个关系模式分解为3NF，使它具有保持函数，使它具有保持函数依赖性。依赖性。（1）如果）如果Fmin中有一函数依赖中有一函数依赖XA，且，且XA=R，则输出，则输出=R，转（转（4）。）。（2）如果）如果R中某些属性与中某些属性与Fmin中所有依赖的左部和右部都无关，中所有依赖的左部和右部都无关，则将它们构成关系模式，从则将它们构成关系

34、模式，从R中将它们分出去，单独构成一个模中将它们分出去，单独构成一个模式。式。（3）对于）对于Fmin中的每一个函数依赖中的每一个函数依赖XA，都单独构成一个关系，都单独构成一个关系子模式子模式XA。若。若Fmin中有中有XA1，XA2，XAn，则可以，则可以用模式用模式XA1A2An取代取代n个模式个模式XA1，XA2，XAn。（4）停止分解，输出）停止分解，输出。3333北京林业大学北京林业大学 软件教研室软件教研室算法算法4.7 把一个关系模式分解为把一个关系模式分解为3NF，使它既具有无损连接，使它既具有无损连接性又具有保持函数依赖性。性又具有保持函数依赖性。（1）根据算法）根据算法4

35、.6求出保持函数依赖的分解：求出保持函数依赖的分解：=R1，R2，Rk。（2）判定）判定是否具有无损连接性，若是，转（是否具有无损连接性，若是，转（4）。）。（3）令）令=X=R1，R2，Rk，X，其中，其中X是是R的候选键。的候选键。（4）输出）输出。例例4-17 将将SD(SNo，SN，Age，Dept，MN)规范到规范到3NF。（1）根据算法）根据算法4.6求出保持函数依赖的分解：求出保持函数依赖的分解：=S(SNo，SN，Age，Dept)，D(Dept，MN)。3434北京林业大学北京林业大学 软件教研室软件教研室（2）判定）判定是否具有无损连接性是否具有无损连接性SD分解为分解为=

36、S(SNo，SN，Age，Dept)，D(Dept，MN)时，时，S、D都属于都属于3NF，且既具有无损连接性又具有保持函数依赖性。，且既具有无损连接性又具有保持函数依赖性。3NF解决了解决了2NF中存在的四个问题：中存在的四个问题：SNo SN Age DeptMN S(SNo，SN，Age，Dept)a1 a2 a3 a4 b15 D(Dept，MN)b21 b22 b23 a4 a5 DeptMN a5a1a2a3a4a5，相对于相对于F是无损连接分解是无损连接分解数据冗余降低了数据冗余降低了 不存在删除异常不存在删除异常 不存在更新异常不存在更新异常 不存在插入异常不存在插入异常 35

37、35北京林业大学北京林业大学 软件教研室软件教研室4.4.4 BC范式范式 BC范式的定义范式的定义 如果关系模式如果关系模式R1NF，且所有的函数依赖，且所有的函数依赖XY（YX），），决定因素决定因素X都包含了都包含了R的一个候选键，则称的一个候选键，则称R属于属于BC范范式，记作式，记作RBCNF。BCNF具有如下性质具有如下性质：如果如果RBCNF，则，则R也是也是3NF。如果如果R3NF，则，则R不一定是不一定是BCNF。例例4-18 设有关系模式设有关系模式SNC（SNo，SN，CNo，Score）SNo SN。存在着主属性对键的部分函数依赖：（存在着主属性对键的部分函数依赖：（S

38、No，CNo）SN，（，（SN，CNo）SNo，所以，所以SNC不是不是BCNF。无部分函数依赖和传递函数依赖，无部分函数依赖和传递函数依赖，SNC3NF 3636北京林业大学北京林业大学 软件教研室软件教研室BCNF规范化规范化 算法算法4.8 把一个关系模式分解为把一个关系模式分解为BCNF（1）令）令=R。（2）如果）如果中所有模式都是中所有模式都是BCNF，则转（，则转（4）。）。（3）如果）如果中有一个关系模式中有一个关系模式S不是不是BCNF，则，则S中必能找到中必能找到一个函数依赖一个函数依赖XA且且X不是不是S的候选键，且的候选键，且A不属于不属于X，设，设S1=XA，S2=S

39、-A，用分解，用分解S1，S2代替代替S，转（，转（2）。）。（4）分解结束，输出）分解结束，输出。例例4-19 将将SNC(SNo，SN，CNo，Score)规范到规范到BCNF。候选键：（候选键：（SNo，CNo）和（）和（SN，CNo）函数依赖：函数依赖：F=SNoSN，SNSNo，(SNo，CNo)Score，(SN，CNo)Score3737北京林业大学北京林业大学 软件教研室软件教研室（1）令）令=SNC(SNo，SN，CNo，Score)。（2）经过前面分析可知，）经过前面分析可知，中关系模式不属于中关系模式不属于BCNF。（3）用分解）用分解S1(SNo，SN)，S2(SNo，

40、CNo，Score)代替代替SNC。（4）分解结果为：）分解结果为：S1(SNo，SN)描述学生实体；描述学生实体；S2(SNo，CNo，Score)描述学生与课程的联系。描述学生与课程的联系。例例4-20 设有关系模式设有关系模式TCS(T，C，S)候选键候选键：（：（S，C）和（）和（S，T）函数依赖是函数依赖是：F=(S，C)T，(S，T)C，TC 分解分解TC(T，C)，ST(S，T)代替代替TCS 消除了函数依赖消除了函数依赖(S，T)C，STBCNF，TCBCNF 3838北京林业大学北京林业大学 软件教研室软件教研室4.4.5 多值依赖与第四范式多值依赖与第四范式 多值依赖的定义

41、多值依赖的定义 假设学校中一门课程可由多名教师讲授，教学中他们使用相假设学校中一门课程可由多名教师讲授，教学中他们使用相同的一套参考书。同的一套参考书。课程课程C 教师教师T 参考书参考书B 数据库原理数据库原理数据结构数据结构 吴胜利吴胜利陈晨陈晨王平王平张京生张京生 数据库原理与应用数据库原理与应用数据库系统数据库系统SQL Server 2000算法与数据结构算法与数据结构数据结构教程数据结构教程 关系关系CTB 3939北京林业大学北京林业大学 软件教研室软件教研室CTB转化成规范化的关系如下图所示：转化成规范化的关系如下图所示：C与与T间的联系被称为多值依赖间的联系被称为多值依赖 多

42、个多个T对应一个对应一个C 一个确定的一个确定的C值，与其所对应的一组值，与其所对应的一组T值与值与B值无关值无关 课程课程C教师教师T参考书参考书B数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据结构数据结构数据结构数据结构数据结构数据结构数据结构数据结构 吴胜利吴胜利吴胜利吴胜利吴胜利吴胜利陈晨陈晨陈晨陈晨陈晨陈晨王平王平王平王平张京生张京生张京生张京生 数据库原理与应用数据库原理与应用数据库系统数据库系统SQL Server2000数据库原理与应用数据库原理与应用数据库系统数据库系统SQL Server2000算

43、法与数据结构算法与数据结构数据结构教程数据结构教程算法与数据结构算法与数据结构数据结构教程数据结构教程 数据冗余大数据冗余大 插入异常插入异常 删除异常删除异常 4040北京林业大学北京林业大学 软件教研室软件教研室定义定义4.18 设有关系模式设有关系模式R（U），），U是属性全集，是属性全集，X、Y、Z是属性集是属性集U的子集，且的子集，且Z=UXY如果对于如果对于R的任一关系，对于的任一关系，对于X的一个确定值，存在的一个确定值，存在Y的一组值与之对应，且的一组值与之对应，且Y的这组值仅仅决定于的这组值仅仅决定于X的值的值而与而与Z值无关，此时称值无关，此时称Y多值依赖于多值依赖于X，或

44、，或X多值决定多值决定Y，记作，记作XY。若若XY且且Z=UXY，则称，则称XY是非平凡是非平凡的多值依赖，否则称为平凡的多值依赖的多值依赖，否则称为平凡的多值依赖。4141北京林业大学北京林业大学 软件教研室软件教研室多值依赖公理及其推论多值依赖公理及其推论 多值依赖公理多值依赖公理 增广律：如果增广律：如果XY，VWU，则，则WXVY。传递律：如果传递律：如果XY，YZ，则，则XZ-Y。补余律：如果补余律：如果XY，则，则XU-X-Y。函数依赖公理与多值依赖混合公理函数依赖公理与多值依赖混合公理 复制规则：从复制规则：从FD导出导出MVD，如果，如果XY，则，则XY。接合规则：从接合规则：

45、从MVD导出导出FD：如果：如果XY，ZY，且存在，且存在WU有有WY=，WZ，则，则XZ。多值依赖推论多值依赖推论 合并律：如果合并律：如果XY，XZ，则，则XYZ。伪传递律：如果伪传递律：如果XY，WYZ，则，则XW(Z-W-Y)。分解律：如果分解律：如果XY，XZ，则，则X（YZ），），X(Y-Z)，X(Z-Y)。混合伪传递律：如果混合伪传递律：如果XY，XYZ，则，则X(Z-Y)。4242北京林业大学北京林业大学 软件教研室软件教研室第四范式（第四范式（4NF）定义）定义 定义定义4.19 设有一关系模式设有一关系模式R（U），），U是其属性全集，是其属性全集，X、Y是是U的子集，的子

46、集，D是是R上的数据依赖集。如果对于上的数据依赖集。如果对于任一多值依赖任一多值依赖XY，此多值依赖是平凡的，或者，此多值依赖是平凡的，或者X包含了包含了R的一个候选关键字，则称的一个候选关键字，则称R是第四范式的关是第四范式的关系模式，记为系模式，记为R4NF。一个一个BCNF的关系模式不一定是的关系模式不一定是4NF4NF的关系模式必定是的关系模式必定是BCNF的关系模式的关系模式 4NF是是BCNF的推广的推广 4343北京林业大学北京林业大学 软件教研室软件教研室第四范式（第四范式（4NF）的分解）的分解（1）令）令=R。（2）如果）如果中所有模式中所有模式Ri都是都是4NF，则转（，

47、则转（4）。）。（3）如果）如果中有一个关系模式中有一个关系模式S不是不是4NF，则，则S中必能找到一中必能找到一个多值依赖个多值依赖XY且且X不包含不包含S的候选键，的候选键，Y-X，XYS，令，令Z=Y-X，设，设S1=XZ，S2=S-Z，用分解，用分解S1，S2代替代替S，由于，由于S1S2=X，S1-S2=Z，所以有，所以有(S1S2)(S1-S2)，分解具有无损连接性，转（，分解具有无损连接性，转（2）。）。（4）分解结束，输出）分解结束，输出。4444北京林业大学北京林业大学 软件教研室软件教研室4.5 关系模式的规范化关系模式的规范化 一个低一级范式的关系模式，通过模式分解转化为

48、若一个低一级范式的关系模式，通过模式分解转化为若干个高一级范式的关系模式的集合，这种分解过程叫干个高一级范式的关系模式的集合，这种分解过程叫作关系模式的作关系模式的规范化。规范化。关系模式规范化的目的和原则关系模式规范化的目的和原则规范化的目的就是使结构合理，消除存储异常，使数规范化的目的就是使结构合理，消除存储异常，使数据冗余尽量小，便于插入、删除和更新。据冗余尽量小，便于插入、删除和更新。规范化的基本原则就是遵循规范化的基本原则就是遵循“一事一地一事一地”的原则。的原则。4545北京林业大学北京林业大学 软件教研室软件教研室4.5.2 关系模式规范化的步骤关系模式规范化的步骤规范化过程规范

49、化过程 4646北京林业大学北京林业大学 软件教研室软件教研室4.5.3 关系模式规范化的要求关系模式规范化的要求 保证分解后的关系模式与原关系模式是等价的保证分解后的关系模式与原关系模式是等价的等价的三种标准：等价的三种标准：分解要具有无损连接性；分解要具有无损连接性；分解要具有函数依赖保持性；分解要具有函数依赖保持性；分解既要具有无损连接性，又要具有函数依赖保持性。分解既要具有无损连接性，又要具有函数依赖保持性。保证不丢失信息保证不丢失信息 减轻或解决各减轻或解决各种异常情况种异常情况 4747北京林业大学北京林业大学 软件教研室软件教研室4848北京林业大学北京林业大学 软件教研室软件教研室