SQLServer教案第03周-关系模式的规范化设计

数据库原理与应用——SQLServer2005教案邹竞授课日期年月日第3周授课形式讲课授课时数4章节名称第03章关系模式的规范化设计教学目的与要求①理解函数依赖、完全函数依赖、部分函数依赖、传递函数依赖的概念②掌握Armstrong公理系统（自反律、增广律、传递律、合并规则、伪传递规则、分解规则）③掌握函数依赖集的闭包和属性闭包的求法④理解最小函数依赖集的定义，掌握最小函数依赖集的求法⑤掌握将E-R图转换成为关系模式的方法⑥掌握根据某个关系的函数依赖找候选键的方法。⑦理解第一范式、第二范式、第三范式、BC范式、第四范式、第五范式的概念⑧掌握将不满足第三范式的关系模式进行分解，令分解后的关系模式满足第三范式的方法教学重点第一范式、第二范式、第三范式教学难点根据某个关系的函数依赖找候选键的方法教学方法和手段讲授法结合课堂实例分析讨论教学过程与组织导入新课关系数据库是以数学理论为基础的。基于这种理论上的优势，关系模型可以设计得较为科学，关系操作可以较好地进行优化，许多技术问题可以得到较好地解决。讲授新课第三章关系模式的对范化设计第01节关系模式的设计问题3.1.1问题的提出设有一个关系模式R(U),其中U为由属性SNO、CNO、TNO、TNAME、TDEPT、和G组成的属性集合，其中SNO为学生学号，CNO为课程号，TNO为任课教师编号，TNAME为任课教师姓名，TDEPT为教师所在系，G为课程成绩。该关系具有如下语义：●1位学生只有1个学号，1位教师只有一个教师号，1门课程只有1个课程号；●每位学生选修的每门课程都有1个成绩；●每门课程只有1位教师任课，每位教师可以担任多门课程；●每个教师只能在1个系，每个系可有多个教师；根据上述语义和常识，可以知道R的候选键：{SNO,CNO}。选定{SNO,CNO}作为主键。通过分析关系模式R(U),我们可以发现下面2类问题。①第1类问题是数据大量冗余，表现在：●每门课程的任课教师的教师编号、姓名必须对选修该门课程的学生重复1次；●每门课程的任课教师所在的系必须对选修该门课程的学生重复1次。②第2类问题是更新出现异常(updateanomalies)，表现在：●修改异常(modificationanomalies)：修改一门课程的任课教师，或者一门课程由另一位教师开设，就需要修改多个元组。如果不分修改，部分不修改，就会出现数据间的不一致。●插入异常(insertanomalies)：由于主键中元素的属性值不能取空值，如果某系的一位教师不开课或一位教师所开的课程无人选修，则这位教师的姓名和所属的系名就不能插入；如果一门课程列入数据库原理与应用——SQLServer2005教案邹竞计划而目前不开,则有关这门课的数据(CNO、TNAME和TDPT)也无法插入。●删除异常(deletionanomalies)：如果所有学生都退选一门课，则有关这门课的其他数据(TNAME和TDPT)也将删除；同样，如果一位教师因故暂时停开，则这位教师的其他信息(TDPT,CNO)也将被删除。3.1.2问题的分析这两类现象的根本原因在于关系的结构。如果在构造关系模式的时候，不从语义上研究和考虑到属性间的这种关联，简单地将属性随意编排在一起，就必然发生某种冲突，即冗余度水平较高，更新产生异常。解决问题的根本方法就是将关系模式进行分解，也就是进行关系的规范化。3.1.3问题的解决方案在关系数据库的设计当中，不是随便一种关系模式设计方案都是可行的。数据库中的每一个关系模式的属性之间需要满足某种内在的必然联系。因此，设计一个好的数据库的根本方法是先要分析和掌握属性间的语义关联，然后再依据这些关联得到相应的设计方案。人们认识到属性之间一般有2种依赖关系，一种是函数依赖关系，一种是多值依赖关系。函数依赖关系与更新异常密切相关，多值依赖与数据冗余密切联系。基于对这两种依赖关系不同层面上的具体要求，人们又将属性之间的联系分为若干等级，这就是所谓的关系的规范化(normalization)。解决问题的基本方案就是分析研究属性之间的联系，按照每个关系中属性间满足某种内在语义条件来构造关系。由此产生的一整套有关理论称之为关系数据库的规范化理论。第02节函数依赖3.2.1函数依赖的概念设有关系模式R(A1,A2,…,An),简记为R(U),其中U={A1,A2,…,An}。设X、Y是U的子集，r是R的任一具体关系,r的任意两个元组r1,r2,若r1[X]=r2[X]（元组r1、r2在X上的属性值相等）则r1[Y]=r2[Y](元组r1、r2在Y上的属性值相等)，则称X函数决定Y(或Y函数依赖于X)，记为X→Y。称X→Y为R的一个函数依赖(简称FD)。可以这样理解：X→Y的意思是：在当前值r的两个不同元组中，如果X值相同，则Y值也相同；或者说,对于X的每一个具体值，都有Y唯一的具体值与之对应,即Y值由X值决定。例3-1设有关系模式R(SNO,SNAME,CNO,SG,CNAME,TNO,TNAME)，其中各属性的含义为：SNO为学生学号,SNAME为学生姓名,CNO为课程号,SG为最终成绩,CNAME为课程名。在R的关系r中,存在着如下函数依赖：SNO→SNAME(每个学号只能有1个学生姓名,SNAME函数依赖于SNO)CNO→CNAME(每个课程号只能对应1门课程名,CNAME函数依赖于CNO)(SNO,CNO)→SG(每个学生学习一门课只能有1个最终成绩,SG函数依赖于SNO和CNO)3.2.2函数依赖的分类（1）完全函数依赖在关系模式R(U)中，如果X→Y，并且对于X的任意一个真子集X1，X1→Y均不成立，则称Y完全依赖于X。例如：(学号,课程号)→最终成绩数据库原理与应用——SQLServer2005教案邹竞（2）部分函数依赖在关系模式R(U)中,如果X→Y,并且至少存在X的一个真子集X1,使得X1→Y成立,则称Y部分依赖于X。例如：(学号,课程号)→姓名（3）传递函数依赖在关系模式R(U)中，如果X→Y并且Y→Z，则称Z传递依赖于X。例如：学号→系主任(学号→系名,系名→系主任)3.2.3函数依赖的逻辑蕴涵与推理规则（1）函数依赖的逻辑蕴涵设U为关系模式R(U,F)的所有属性的集合，F为属性集U上的所有函数依赖的集合，X、Y是U的子集，如果从F能推出函数依赖X→Y，则称F逻辑蕴涵X→Y。（2）函数依赖的推理规则前面我们提到由函数依赖、函数依赖集(F)可以推出另外的函数依赖(X→Y)，那么从一个函数依赖集如何推出另外一个函数依赖？推理依据什么规则呢?函数依赖的推理规则是W.W.Armstrong1974年首先提出来的，称为Armstrong公理系统，由3条公理和3条推理规则构成。设有关系R(U)，U是R属性的集合，F是R上函数依赖的集合。①Armstrong公理系统的3条公理(a)自反律：如果YXU，则F逻辑蕴涵X→Y。(b)增广律：若F逻辑蕴涵X→Y，且ZU，则F逻辑蕴涵XZ→YZ(c)传递律：F逻辑蕴涵X→Y、Y→Z,则F逻辑蕴涵X→Z②Armstrong公理系统的3条推理规则(a)合并规则：F逻辑蕴涵X→Y、X→Z，则X→YZ。证明：利用增广律将函数依赖X→Y、X→Z进行扩充得：X→XYXY→YZ由传递律得：X→YZ。(b)伪传递规则：F逻辑蕴涵X→Y、WY→Z，则XW→Z。证明：利用增广律将函数依赖X→Y进行扩充得：WX→WY,再由WX→WY、WY→Z，根据传递律得：XW→Z。(c)分解规则：F逻辑蕴涵X→Y且ZY,则F逻辑蕴涵X→Z证明：由ZY根据自反律得：Y→Z,再由X→Y、Y→Z根据传递律得：X→Z。定理3-1函数依赖X→Y逻辑蕴涵于F的充要条件是：函数依赖X→Y，可根据F，由Armstrong推理规则推出。3.2.4函数依赖集的闭包与属性闭包设F是函数依赖集，F及由F推出的所有函数依赖（即为F所逻辑蕴含的函数依赖的集合），称为函数依赖集F的闭包，记为F+。一般情况下，F≤F+。如果F=F+，则称F是函数依赖的完备集。数据库原理与应用——SQLServer2005教案邹竞设有关系模式R(U,F)，X是U的子集，称所有利用Armstrong公理系统从F推出的函数依赖集X→Ai中Ai的属性集为X的属性闭包，记作XF+。即：XF+={Ai|Ai∈U,X→Ai∈F+)由公理的自反性可知X→X,因此XXF+。算法3-1求属性集闭包XF+的算法。输入：有限的属性集合U，U上面的函数依赖集合F，U的一个子集X。输出：X关于F的闭包XF+。方法：①置XF+=的初值为X；②依次扫描F中的每个函数依赖Y→Z，若YXF+且ZXF+则置XF+=XF+∪Z；③输出XF+，算法结束。例3-2设有关系模式R(U,F)，其中U={ABCDE}，F={AB→C,B→D,C→E,EC→B,AC→B)，求(AB)F+。(注：“ABCDE”为“A,B,C,D,E”的简写，其它类同)解：①置(AB)F+=AB；(置属性集闭包(AB)F+初值为{AB})②依次扫描F中的每个函数依赖：∵AB→C,AB(AB)F+,C(AB)F+∴(AB)F+=(AB)F+∪C=ABC,扫描下一个函数依赖∵B→D,B(AB)F+,D(AB)F+∴(AB)F+=(AB)F+∪D=ABCD,扫描下一个函数依赖∵C→E,C(AB)F+,E(AB)F+∴(AB)F+=(AB)F+∪E=ABCDE,扫描下一个函数依赖∵EC→B,EC(AB)F+,B(AB)F+∴(AB)F+不变,扫描下一个函数依赖∵AC→B,AC(AB)F+,B(AB)F+∴(AB)F+不变，扫描结束③输出：XF+=ABCDE即XF+={A,B,C,D,E}3.2.5函数依赖集的等价和覆盖（1）函数依赖集的等价概念设F和G是两个函数依赖集，如果F+=G+，则称F和G等价，又称为F覆盖G或G覆盖F。（2）判断两个函数依赖集等价的方法①在G上计算XG+，看是否YXG+。若是，则说明X→Y∈G+,于是继续检查F中的其他依赖，如果全部满足X→Y∈G+,则FG+。数据库原理与应用——SQLServer2005教案邹竞②如果在检查中发现有一个X→Y不属于G+,就可以判定FG+不成立，即F和G不等价。③如果经判断FG+,则类似地重复上述做法,判断是否GF+,如果成立则可断定F和G等价。定理3-2F+=G+的充分必要条件是FG+且GF+。3.2.6函数依赖集的最小化（1）最小函数依赖集的定义如果函数依赖集F同时满足下列3个条件，则称F为一个极小函数依赖集（亦称为最小依赖集或最小覆盖），记为Fmin。①F中任一函数依赖的右部都是单属性。②F中的任一函数依赖X→A，其F-{X→A)与F不等价。③F中的任一函数依赖X→A，其X有真子集Z，F-{X→A}∪{Z→A}与F不等价。条件①说明在最小函数依赖集中的所有函数依赖都应该是“右端没有多余属性”的最简单的形式；条件②保证了最小函数依赖集中无多余的函数依赖；条件③要求最小函数依赖集中的每个函数依赖的左端没有多余属性。（2）最小函数依赖集的求法定理3-3每一个函数依赖集F均等价于一个极小函数依赖集Fm，此Fm称为F的最小依赖集。算法3-2求最小函数依赖集的算法（本算法也是对定理3-3的证明）。可以分三步对F进行“极小化处理”，找出F的一个最小依赖集：①逐一检查F中各函数依赖X→Y，若Y=A1A2…Ak，k≥2，则用{X→Aj|j=1,2,…k}取代X→Y。②逐一检查F中各函数依赖X→A，令G=F-{X→A}，若A∈XG+，则从F中去掉此函数依赖。③逐一取出F中各函数依赖X→A，设X=B1B2…Bm，逐一检查Bi(i=1,2,…,m)，如果A∈(X-Bi)F+，则以X-Bi取代X。因为对F的每一次改造都保证了改造前后的两个函数依赖集等价，所以最后得到的F就是极小依赖集，并且与原来的F等价。注意：F的最小依赖集Fm不一定是唯一的，它与对各函数依赖及X→A中X各属性的处置有关。例3-3设F={A→BC,B→AC,C→A),对F进行极小化处理。解：