《3关系数据库规范化理论》由会员分享，可在线阅读，更多相关《3关系数据库规范化理论（133页珍藏版）》请在金锄头文库上搜索。
1、PrinciplesofDatabase第三章第三章 关系数据库规范化理论关系数据库规范化理论1第三章第三章 关系数据库规范化理论关系数据库规范化理论3.1关系规范化的作用关系规范化的作用3.2函数依赖函数依赖3.3函数依赖的公理系统函数依赖的公理系统3.4关系模式的规范化关系模式的规范化3.5多值依赖与第四范式多值依赖与第四范式3.6关系模式的分解关系模式的分解3.7连接依赖与第五范式连接依赖与第五范式3.8关系模式规范化步骤关系模式规范化步骤3.9小结小结24.1关系规范化的作用关系规范化的作用一、一、问题的提出问题的提出二、二、解决的方法解决的方法三、三、关系模式规范化关系模式规范化的作
2、用的作用3一、一、问题的提出问题的提出例：描述学校教学管理的数据库：例：描述学校教学管理的数据库：学生的学号学生的学号(Sno)、姓名、姓名(Sname)、性别、性别(Ssex)、所在系、所在系名名(Dname)、所学的课程名、所学的课程名(Cname)、任课老师名、任课老师名(Tname)、成绩、成绩(Grade)JiaoXue（Sno，Sname，Ssex，Dname，Cname，Tname，Grade）单一单一的关系模式的关系模式：JiaoXueU Sno，Sname，Ssex，Dname，Cname，Tname，Grade 此关系的主键为：此关系的主键为：（Sno,Cname） 4学校
3、教学管理数据库的语义：学校教学管理数据库的语义：一个系有若干学生，一个系有若干学生，一个学生只属于一个系；一个学生只属于一个系；一个系只有一名主任；一个系只有一名主任；一个学生可以选修多门课程，一个学生可以选修多门课程，每门课程有若干每门课程有若干学生选修；学生选修；每个学生所学的每门课程都有一个成绩。每个学生所学的每门课程都有一个成绩。5.每门课程均由一个教师任教。每门课程均由一个教师任教。5关系模式关系模式JiaoXue中存在的问题中存在的问题1）、数据冗余（）、数据冗余（DataRedundancy）l l每每一一个个系系名名对对该该系系的的学学生生人人数数乘乘以以每每个个学学生生选选修
4、修的课程门数重复存储。的课程门数重复存储。l l每一个课程名均对选修该门课程的学生重复存储。每一个课程名均对选修该门课程的学生重复存储。l l每一个教师都对其所教的学生重复存储。每一个教师都对其所教的学生重复存储。62）、更新异常（）、更新异常（UpdateAnomalies）l l插插入入异异常常（InsertAnomalies）：由由于于主主键键中中元元素素的的属属性性值值不不能能取取空空值值，如如果果新新分分配配来来一一位位教教师师或或新新成成立立一一个个系系，则则这这位位教教师师及及新新系系名名就就无无法法插插入入；如如果果一一位位教教师师所所开开的的课课程程无无人选修或一门课程列入计
5、划但目前不开课，也无法插入。人选修或一门课程列入计划但目前不开课，也无法插入。修修改改异异常常（ModificationAnomalies）：如如果果更更改改一一门门课课程程的的任任课课教教师师，则则需需要要修修改改多多个个元元组组。如如果果仅仅部部分分修修改改，部部分分不不修修改改，就就会会造造成成数数据据的的不不一一致致性性。同同样样的的情情形形，如如果果一一个个学学生生转转系系，则则对对应应此此学学生生的的所所有有元元组组都都必必须须修修改改，否否则则，也也出现数据的不一致性。出现数据的不一致性。l l删除异常（删除异常（DeletionAnomalies）：如果某系的所有学生）：如果某
6、系的所有学生全部毕业，又没有在读及新生，当从表中删除毕业学生的选全部毕业，又没有在读及新生，当从表中删除毕业学生的选课信息时，则连同此系的信息将全部丢失。同样地，如果所课信息时，则连同此系的信息将全部丢失。同样地，如果所有学生都退选一门课程，则该课程的相关信息也同样丢失了。有学生都退选一门课程，则该课程的相关信息也同样丢失了。7二、二、解决的方法解决的方法关系模式关系模式JiaoXue中存在问题的中存在问题的结论：结论：JiaoXue关系模式不是一个好的模式。关系模式不是一个好的模式。“好好”的模式：的模式：不会发生插入异常、删除异常、更新异常，不会发生插入异常、删除异常、更新异常，数据冗余应
7、尽可能少。数据冗余应尽可能少。原因：原因：由存在于模式中的由存在于模式中的某些数据依赖某些数据依赖引起的引起的解决方法：解决方法：通过通过分解分解关系模式来消除其中不合适关系模式来消除其中不合适的数据依赖。的数据依赖。8关系模式关系模式JiaoXue的一种分解方法的一种分解方法 教学关系分解为三个关系模式来表达：学生基本信息教学关系分解为三个关系模式来表达：学生基本信息StudentStudent（Sno，Sname，Ssex，Dname），课程信息），课程信息CourseCourse（Cno，Cname，Tname），及学生成绩），及学生成绩GradeGrade（Sno，Cno，Grade）
8、。）。9分解后的关系模式的优点分解后的关系模式的优点v1）、数据存储量减少。）、数据存储量减少。v2）、更新方便。）、更新方便。插插入入问问题题部部分分解解决决：对对一一位位教教师师所所开开的的无无人人选选修修的的课课程程可可方方便便地地在在课课程程信信息息表表中中插插入入。但但是是，新新分分配配来来的的教教师师、新新成成立立的的系系或或列列入入计计划划但但目目前前不不开开课课的的课课程程，还还是是无无法法插插入入。要要解决无法插入的问题，还可继续将系名与课程作分解来解决。解决无法插入的问题，还可继续将系名与课程作分解来解决。修修改改方方便便：原原关关系系中中对对数数据据修修改改所所造造成成的
9、的数数据据不不一一致致性性，在分解后得到了很好的解决，改进后，只需要修改一处。在分解后得到了很好的解决，改进后，只需要修改一处。删删除除问问题题也也部部分分解解决决：当当所所有有学学生生都都退退选选一一门门课课程程时时，删删除除退退选选的的课课程程不不会会丢丢失失该该门门课课程程的的信信息息。值值得得注注意意的的是是，系系的信息丢失问题依然存在，解决的方法还需继续进行分解。的信息丢失问题依然存在，解决的方法还需继续进行分解。10分解后的关系模式说明分解后的关系模式说明虽虽然然改改进进后后的的模模式式部部分分地地解解决决了了不不合合理理的的关关系系模模式式所所带带来来的的问问题题，但但同同时时，
10、改改进进后后的的关关系系模模式式也也会会带带来来新新的的问问题题，如如当当查查询询某某个个系系的的学学生生成成绩绩时时，就就需需要要将将两两个个关关系系连连接接后后进进行行查查询询，增增加加了了查查询询时时关关系系的的连连接接开开销销，而而关关系系的的连连接接代代价价却又是很大的。却又是很大的。 此外，必须说明的是，不是任何分解都是有效的。若将此外，必须说明的是，不是任何分解都是有效的。若将JiaoXue分解为（分解为（Sno，Sname，Ssex，Dname，），）、（、（Sno，Cno，Cname，Tname）及（）及（Sname，Cno，Grade），不但解决不了实际问题，反面会带来更多
11、的问题。），不但解决不了实际问题，反面会带来更多的问题。11三、三、关系模式规范化的作用关系模式规范化的作用规范化理论规范化理论正是用来改造关系模式，通过分解正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。入异常、删除异常、更新异常和数据冗余问题。124.2函数依赖函数依赖4.2.1、关系模式的简化表示关系模式的简化表示4.2.2、函数依赖的基本概念函数依赖的基本概念4.2.3、码的函数依赖表示、码的函数依赖表示4.2.4、函数依赖和码的唯一性、函数依赖和码的唯一性134.2.1、关
12、系模式的简化表示关系模式的简化表示关系模式由五部分组成，即它是一个五元组：关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)R：关系名关系名U：组成该关系的属性名集合组成该关系的属性名集合D：属性组属性组U中属性所来自的域中属性所来自的域DOM：属性向域的映象集合：属性向域的映象集合F：属性间数据的依赖关系集合属性间数据的依赖关系集合14由由于于D和和Dom对对设设计计关关系系模模式式的的作作用用不不大大，在在讨讨论论关关系系规规范范化化理理论论时时可可以以把把它它们们简简化化掉掉，从从而而关关系系模模式式可可以以用用三三元元组来表示为：组来表示为：R（U，F）154.2.2、函
13、数依赖的基本概念函数依赖的基本概念一、函数依赖的定义一、函数依赖的定义二、平凡函数依赖与非平凡函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖四、传递函数依赖16一、一、函数依赖的定义函数依赖的定义定义定义5.1设设R(U)是一个属性集是一个属性集U上的关系模式，上的关系模式，X和和Y是是U的子集。的子集。若对于若对于R(U)的的任意任意一个可能的关系一个可能的关系r，r中不可能存在两个元中不可能存在两个元组在组在X上的属性值相等，上的属性值相等，而在而在Y上的属性值不等，上的属性值不等，则称则称“X函函数确定数确定Y”或或“
14、Y函数依赖于函数依赖于X”，记作，记作XY。X称为这个函数依赖的称为这个函数依赖的决定属性集决定属性集(Determinant)。Y=f(x)17说明：说明：1.函数依赖不是指关系模式函数依赖不是指关系模式R的某个或某些关系实例满足的的某个或某些关系实例满足的约束条件，而是指约束条件，而是指R的的所有关系实例所有关系实例均要满足的约束条件。均要满足的约束条件。2.函数依赖是函数依赖是语义范畴语义范畴的概念。只能根据数据的语义来确定的概念。只能根据数据的语义来确定函数依赖。函数依赖。例如例如“姓名姓名年龄年龄”这个函数依赖只有在不允许有同名人的这个函数依赖只有在不允许有同名人的条件下成立条件下成
15、立3.数据库设计者可以对现实世界作强制的规定。例如规定不数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖允许同名人出现，函数依赖“姓名姓名年龄年龄”成立。所插入的成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，元组必须满足规定的函数依赖，若发现有同名人存在，则则拒绝装入该元组。拒绝装入该元组。18函数依赖（续）函数依赖（续）例例:Student(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有假设不允许重名，则有:SnoSsex，SnoSage,SnoSdept，SnoSname,SnameSsex，SnameSageSnameS
16、dept但但SsexSage若若XY，并且，并且YX,则记为则记为XY。若若Y不函数依赖于不函数依赖于X,则记为则记为XY。19二、平凡函数依赖与非平凡函数依赖二、平凡函数依赖与非平凡函数依赖在关系模式在关系模式R(U)中，对于中，对于U的子集的子集X和和Y，如果如果XY，但，但Y X，则称，则称XY是是非平凡的函数依赖非平凡的函数依赖若若XY，但，但Y X,则称则称XY是是平凡的函数依赖平凡的函数依赖例：在关系例：在关系SC(Sno,Cno,Grade)中，中，非平凡函数依赖：非平凡函数依赖：(Sno,Cno)Grade平凡函数依赖：平凡函数依赖：(Sno,Cno)Sno(Sno,Cno)C
17、no20对于任一关系模式，平凡函数依赖都对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，是必然成立的，它不反映新的语义，因此若不特别声明，因此若不特别声明，我们总是讨论非我们总是讨论非平凡函数依赖平凡函数依赖。21三、完全函数依赖与部分函数依赖三、完全函数依赖与部分函数依赖定义定义5.2在关系模式在关系模式R(U)中，如果中，如果XY，并且，并且对于对于X的任何一个真子集的任何一个真子集X，都有，都有XY,则称则称Y完全函数依赖于完全函数依赖于X，记作，记作XY。若若XY，但，但Y不完全函数依赖于不完全函数依赖于X，则称，则称Y部分函数部分函数依赖依赖于于X，记作，记作XPY。
18、22例例:在关系在关系SC(Sno,Cno,Grade)中，中，由于：由于：SnoGrade，CnoGrade，因此：因此：(Sno,Cno)Grade23四、传递函数依赖四、传递函数依赖定义定义5.3在关系模式在关系模式R(U)中，如果中，如果XY，YZ，且且Y X，YX，则称，则称Z传递函数依赖传递函数依赖于于X。注注:如果如果YX，即即XY，则，则Z直接依赖直接依赖于于X。例例:在关系在关系Std(Sno,Sdept,Mname)中，有：中，有：SnoSdept，SdeptMnameMname传递函数依赖于传递函数依赖于Sno244.2.3、码的函数依赖表示、码的函数依赖表示定义定义5.
19、4设设K为关系模式为关系模式R中的属中的属性或属性组合。若性或属性组合。若KU，则，则K称为称为R的一个的一个侯选码侯选码（CandidateKey）。若关系模式）。若关系模式R有有多个候选码，则选定其中的一个做为多个候选码，则选定其中的一个做为主码主码（Primarykey）。）。25外部码外部码 定义定义5.55.5 关系模式关系模式 R R 中属性或属中属性或属性组性组X X 并非并非 R R的码，但的码，但 X X 是另一个关系是另一个关系模式的码，则称模式的码，则称 X X 是是R R 的的外部码外部码（Foreign keyForeign key）也称外码也称外码v主码又和外部码一
20、起提供了表示关系间联系的主码又和外部码一起提供了表示关系间联系的手段手段。264.2.4、函数依赖和码的唯一性、函数依赖和码的唯一性v码是由一个或多个属性组成的可唯一标识元组的最码是由一个或多个属性组成的可唯一标识元组的最小属性组。码在关系中总是惟一的，即码函数决定小属性组。码在关系中总是惟一的，即码函数决定关系中的其他属性。因此，一个关系，码值总是唯关系中的其他属性。因此，一个关系，码值总是唯一的（如果码的值重复，则整个元组都会重复）。一的（如果码的值重复，则整个元组都会重复）。否则，违反否则，违反实体完整性规则实体完整性规则。27一、逻辑蕴含一、逻辑蕴含定义定义5.11对于满足一组对于满足
21、一组函数依赖函数依赖F 的关系模的关系模式式R，其任何一个关系，其任何一个关系r，若函数依，若函数依赖赖XY都成立都成立,则称则称F逻辑蕴含逻辑蕴含X Y4.3函数依赖的公理系统函数依赖的公理系统28Armstrong公理系统公理系统v一套推理规则，是模式分解算法的理论基础一套推理规则，是模式分解算法的理论基础v用途用途求给定关系模式的码求给定关系模式的码从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖291.Armstrong公理系统公理系统关系模式关系模式R 来说有以下的推理规则：来说有以下的推理规则：Al.自反律自反律（Reflexivity）：）：若若Y X U，则，则
22、X Y为为F所蕴含。所蕴含。A2.增广律增广律（Augmentation）：若）：若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ为为F所蕴含。所蕴含。A3.传递律传递律（Transitivity）：若）：若XY及及YZ为为F所蕴含，所蕴含，则则XZ为为F所蕴含。所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于并不依赖于F30定理定理4.lArmstrong推理规则是正确的推理规则是正确的（l）自反律）自反律:若若Y X U，则，则X Y为为F所蕴含所蕴含证证:设设Y X U对对R 的任一关系的
23、任一关系r中的任意两个元组中的任意两个元组t，s：若若tX=sX，由于，由于Y X，有，有ty=sy，所以所以XY成立成立.自反律得证自反律得证31(2)增广律增广律:若若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ 为为F所所蕴含。蕴含。证：证：设设XY为为F所蕴含，且所蕴含，且Z U。设设R的任一关系的任一关系r中任意的两个元组中任意的两个元组t，s；若若tXZ=sXZ，则有，则有tX=sX和和tZ=sZ；由由XY，于是有，于是有tY=sY，所以，所以tYZ=sYZ，所以，所以XZYZ为为F所蕴含所蕴含.增广律得证。增广律得证。32(3)传递律：若传递律：若XY及及YZ为为F所蕴含
24、，则所蕴含，则XZ为为F所蕴含。所蕴含。证：证：设设XY及及YZ为为F所蕴含。所蕴含。对对R的任一关系的任一关系r中的任意两个元组中的任意两个元组t，s。若若tX=sX，由于，由于XY，有，有tY=sY；再由再由YZ，有，有tZ=sZ，所以，所以XZ为为F所蕴含所蕴含.传递律得证。传递律得证。332.导出规则导出规则1.根据根据A1，A2，A3这三条推理规则可以得到下面三这三条推理规则可以得到下面三条推理规则：条推理规则：合并规则合并规则：由：由XY，XZ，有，有XYZ。（A2，A3）伪传递规则伪传递规则：由：由XY，WYZ，有，有XWZ。（A2，A3）分解规则分解规则：由：由XY及及Z Y，
25、有，有XZ。（A1，A3）34导出规则导出规则2.根据合并规则和分解规则，可得引理根据合并规则和分解规则，可得引理5.1引理引理5.lXA1 A2Ak成立的充分必要条件成立的充分必要条件是是XAi成立（成立（i=l，2，k）。）。353.函数依赖闭包函数依赖闭包定义定义4.l2在关系模式在关系模式R中为中为F所逻辑蕴所逻辑蕴含的函数依赖的全体叫作含的函数依赖的全体叫作F的闭包的闭包，记为，记为F+。定义定义4.13设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U，XF+=A|XA能由能由F 根据根据Armstrong公公理导出理导出，XF+称为属性集称为属性集X关于函数依赖集
26、关于函数依赖集F 的闭包的闭包36F的闭包的闭包 F=XY,YZ,F+计算是计算是NP完全问题，完全问题，XA1A2.AnF+=X,Y,Z,XY,XZ,YZ,XYZ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZXYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ37关于闭包的引理关于闭包的引理v引理引理4.2设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U，X
27、Y能由能由F 根据根据Armstrong公理导出的充分公理导出的充分必要条件是必要条件是Y XF+v用途用途将判定将判定XY是否能由是否能由F根据根据Armstrong公理导出的问公理导出的问题，就转化为求出题，就转化为求出XF+，判定，判定Y是否为是否为XF+的子集的问的子集的问题题38求闭包的算法求闭包的算法算法算法4.l求属性集求属性集X（X U）关于）关于U上的函数依上的函数依赖集赖集F 的闭包的闭包XF+输入：输入：X，F输出：输出：XF+步骤：步骤：（1）令）令X（0）=X，i=0（2）求）求B，这里，这里B=A|( V)( W)(VW F V X（i） A W)；（3）X（i+1
28、）=B X（i）39算法算法4.l（4）判断）判断X（i+1）=X（i）吗吗?（5）若相等或）若相等或X（i）=U , 则则X（i）就是就是XF+,算法终止。算法终止。（6）若否，则）若否，则i=i+l，返回第（，返回第（2）步。）步。对于算法对于算法4.l，令令ai=|X（i）|，ai 形成一个步长大形成一个步长大于于1的严格递增的序列，序列的上界是的严格递增的序列，序列的上界是|U|，因，因此该算法最多此该算法最多|U|-|X|次循环就会终止。次循环就会终止。40函数依赖闭包函数依赖闭包例例1已知关系模式已知关系模式R，其中，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，AC
29、B。求（求（AB）F+。解解设设X（0）=AB；(1)计算计算X（1）:逐一的扫描逐一的扫描F集合中各个函数依赖，集合中各个函数依赖，找左部为找左部为A，B或或AB的函数依赖。得到两个：的函数依赖。得到两个：ABC，BD。于是于是X（1）=AB CD=ABCD。41函数依赖闭包函数依赖闭包(2)因为因为X（0）X（1），所以再找出左部为，所以再找出左部为ABCD子集子集的那些函数依赖，又得到的那些函数依赖，又得到ABC，BD，CE，ACB，于是于是X（2）=X（1） BCDE=ABCDE。(3)因为因为X（2）=U，算法终止，算法终止所以（所以（AB）F+=ABCDE。424.Armstron
30、g公理系统的有效性与完备性公理系统的有效性与完备性v有效性有效性：由：由F出发根据出发根据Armstrong公理推导出来的公理推导出来的每一个函数依赖一定在每一个函数依赖一定在F+中中/*Armstrong正确正确v完备性完备性：F+中的每一个函数依赖，必定可以由中的每一个函数依赖，必定可以由F出出发根据发根据Armstrong公理推导出来公理推导出来/*Armstrong公理够用，完全公理够用，完全完备性完备性：所有不能用：所有不能用Armstrong公理推导出来公理推导出来f,都不为真都不为真若若f不能用不能用Armstrong公理推导出来，公理推导出来，f F+43有效性与完备性的证明有
31、效性与完备性的证明证明：证明：1.有效性有效性可由定理可由定理4.l得证得证2.完备性完备性只需证明只需证明逆否命题逆否命题:若函数依赖若函数依赖XY不能由不能由F从从Armstrong公理导出，那么它必然不为公理导出，那么它必然不为F所蕴含所蕴含分三步证明：分三步证明：44有效性与完备性的证明有效性与完备性的证明(1)引理引理:若若VW成立，且成立，且V XF+，则，则W XF+证证因为因为V XF+，所以有，所以有XV成立；成立；因为因为X V，VW，于是，于是XW成立成立所以所以W XF+(2)/*若若f不能用不能用Armstrong公理推导出来，公理推导出来，f F+/*若存在若存在r
32、， F+中的全部函数依赖在中的全部函数依赖在r上成立。上成立。/*而不能用而不能用Armstrong公理推导出来的公理推导出来的f,在在r上不成立。上不成立。构造一张二维表构造一张二维表r，它由下列两个元组构成，可以证明，它由下列两个元组构成，可以证明r必是必是R（U，F）的一个关系）的一个关系，即，即F+中的全部函数依赖在中的全部函数依赖在r上成立上成立。45Armstrong公理系统的有效性与完备性公理系统的有效性与完备性(续续) XF+U-XF+11.100.011.111.1若若r不不是是R的的关关系系，则则必必由由于于F中中有有函函数数依依赖赖VW在在r上上不不成成立立所所致致。由由
33、r的的构构成成可可知知，V必必定定是是XF+的的子子集集，而而W不不是是XF+的的子子集集，可可是是由由第第（1）步步，W XF+，矛矛盾盾。所所以以r必必是是R的的一个关系。一个关系。46Armstrong公理系统的有效性与完备性公理系统的有效性与完备性(续续)(3)/*若若f不能用不能用Armstrong公理推导出来，公理推导出来，f F+/*而不能用而不能用Armstrong公理推导出来的公理推导出来的f,在在r上不成立。上不成立。若若XY 不能由不能由F从从Armstrong公理导出，则公理导出，则Y 不是不是XF+的子集。（引理的子集。（引理4.2）因此必有因此必有Y 的子集的子集Y
34、 满足满足Y U-XF+，则则XY在在r 中中不成立，即不成立，即XY必不为必不为R蕴含蕴含/*因为因为 F+中的全部函数依赖在中的全部函数依赖在r上成立。上成立。47Armstrong公理系统的有效性与完备性公理系统的有效性与完备性(续续)Armstrong公理的完备性及有效性说明公理的完备性及有效性说明:“蕴含蕴含”=“导出导出”等价的概念等价的概念 F+=由由F出发借助出发借助Armstrong公理导出的函公理导出的函数依赖的集合数依赖的集合485.函数依赖集等价函数依赖集等价定义定义4.14如果如果G+=F+，就说函数依赖集，就说函数依赖集F覆覆盖盖G（F是是G的覆盖，或的覆盖，或G是
35、是F的覆盖），或的覆盖），或F与与G等价等价。49函数依赖集等价的充要条件函数依赖集等价的充要条件引理引理4.3F+=G+的充分必要条件是的充分必要条件是F G+，和，和G F+证证:必要性显然，只证充分性。必要性显然，只证充分性。（1）若）若F G+，则，则XF+ XG+。（2）任取）任取XY F+则有则有Y XF+ XG+。所以所以XY (G+）+=G+。即。即F+ G+。（3）同理可证）同理可证G+ F+，所以，所以F+=G+。50函数依赖集等价函数依赖集等价v要要判判定定F G+，只只须须逐逐一一对对F中中的的函函数数依依赖赖XY，考考察察Y 是是否否属属于于XG+就就行行了了。因因此
36、此引引理理4.3给给出出了了判判断断两两个个函函数数依依赖赖集集等等价价的的可可行算法。行算法。516.最小依赖集最小依赖集定定义义4.15如如果果函函数数依依赖赖集集F满满足足下下列列条条件件，则则称称F为为一一个个极极小小函函数数依依赖赖集集。亦亦称称为为最最小小依依赖赖集集或或最小覆盖最小覆盖。(1)F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。(2)F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得F与与F-XA等价。等价。(3)F中不存在这样的函数依赖中不存在这样的函数依赖XA，X有真有真子集子集Z使得使得F-XA ZA与与F等价。等价。527
37、.极小化过程极小化过程定理定理4.3每一个函数依赖集每一个函数依赖集F均等价于一个极小均等价于一个极小函数依赖集函数依赖集Fm。此。此Fm称为称为F的最小依赖集的最小依赖集证证:构构造造性性证证明明，依依据据定定义义分分三三步步对对F进进行行“极极小小化处理化处理”，找出，找出F的一个最小依赖集。的一个最小依赖集。(1)逐一检查逐一检查F中各函数依赖中各函数依赖FDi：XY，若若Y=A1A2Ak，k 2，则用则用XAj|j=1，2，k来取代来取代XY。引理引理5.1保证了保证了F变换前后的等价性。变换前后的等价性。53极小化过程极小化过程(2)逐一检查逐一检查F中各函数依赖中各函数依赖FDi：
38、XA，令令G=F-XA，若若A XG+，则从则从F中去掉此函数依赖。中去掉此函数依赖。由于由于F与与G =F-XA等价的充要条件是等价的充要条件是A XG+因此因此F变换前后是等价的。变换前后是等价的。54极小化过程极小化过程(3)逐一取出逐一取出F中各函数依赖中各函数依赖FDi：XA，设设X=B1B2Bm，逐一考查逐一考查Bi（i=l，2，m），），若若A （X-Bi）F+，则以则以X-Bi取代取代X。由由于于F与与F-XA ZA等等价价的的充充要要条条件件是是A ZF+，其中，其中Z=X-Bi因此因此F变换前后是等价的。变换前后是等价的。55极小化过程极小化过程由定义，最后剩下的由定义，最
39、后剩下的F就一定是极小依赖集。就一定是极小依赖集。因为对因为对F的每一次的每一次“改造改造”都保证了改造前后的都保证了改造前后的两个函数依赖集等价，因此剩下的两个函数依赖集等价，因此剩下的F与原来的与原来的F等价。等价。证毕证毕v定理定理4.3的证明过程的证明过程也是求也是求F极小依赖集极小依赖集的过程的过程56极小化过程极小化过程例例3F=AB，BA，BC，AC，CA Fm1、Fm2都是都是F的最小依赖集：的最小依赖集：Fm1=AB，BC，CAFm2=AB，BA，AC，CAvF的最小依赖集的最小依赖集Fm不一定是唯一的，它与对各函数不一定是唯一的，它与对各函数依赖依赖FDi及及XA中中X各属
40、性的处置顺序有关。各属性的处置顺序有关。57极小化过程极小化过程v极极小小化化过过程程(定定理理4.3的的证证明明)也也是是检检验验F是是否否为极小依赖集的一个算法为极小依赖集的一个算法若改造后的若改造后的F与原来的与原来的F相同，说明相同，说明F本身本身就是一个最小依赖集就是一个最小依赖集58极小化过程极小化过程v在在R中可以用与中可以用与F等价的依赖集等价的依赖集G来取代来取代F原因：两个关系模式原因：两个关系模式R1，R2，如果如果F与与G等价，那么等价，那么R1的关系一定是的关系一定是R2的关系。的关系。反过来，反过来，R2的关系也一定是的关系也一定是R1的关系。的关系。594.4关系
41、模式的规范化关系模式的规范化604.4.1范式范式v范式是符合某一种级别的关系模式的集合。范式是符合某一种级别的关系模式的集合。v关系数据库中的关系必须满足一定的要求。满足不关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。同程度要求的为不同范式。v范式的种类：范式的种类：第一范式第一范式(1NF)第二范式第二范式(2NF)第三范式第三范式(3NF)BC范式范式(BCNF)第四范式第四范式(4NF)第五范式第五范式(5NF)61范式范式(续续)v各种范式之间存在联系：各种范式之间存在联系：v某一关系模式某一关系模式R为第为第n范式，可简记为范式，可简记为R nNF。624.4
42、.21NFv1NF的定义的定义如果一个关系模式如果一个关系模式R的所有属性都是的所有属性都是不可分的基本不可分的基本数据项数据项，则，则R 1NF。v第一范式是对关系模式的最起码的要求。不满足第第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。一范式的数据库模式不能称为关系数据库。v但是满足第一范式的关系模式并不一定是一个好的但是满足第一范式的关系模式并不一定是一个好的关系模式。关系模式。634.4.32NF例例:关系模式关系模式SLC(Sno,Sdept,Sloc,Cno,Grade)Sloc为学生住处，假设每个系的学生住在同一个地为学生住处，假设每个系的学生
43、住在同一个地方。方。v函数依赖包括：函数依赖包括：(Sno,Cno)fGradeSnoSdept(Sno,Cno)PSdeptSnoSloc(Sno,Cno)PSlocSdeptSloc642NFvSLC的码为的码为(Sno,Cno)vSLC满足第一范式。满足第一范式。v非主属性非主属性Sdept和和Sloc部分函数依赖于码部分函数依赖于码(Sno,Cno)SnoCnoGradeSdeptSlocSLC65SLC不是一个好的关系模式不是一个好的关系模式(1)插入异常插入异常假设假设Sno95102，SdeptIS，SlocN的学生还未选的学生还未选课，因课程号是主属性，因此该学生的信息无法插入
44、课，因课程号是主属性，因此该学生的信息无法插入SLC。(2)删除异常删除异常假定某个学生本来只选修了假定某个学生本来只选修了3号课程这一门课。现在因身号课程这一门课。现在因身体不适，他连体不适，他连3号课程也不选修了。因课程号是主属性，号课程也不选修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。此操作将导致该学生信息的整个元组都要删除。66SLC不是一个好的关系模式不是一个好的关系模式(3)数据冗余度大数据冗余度大如果一个学生选修了如果一个学生选修了10门课程，那么他的门课程，那么他的Sdept和和Sloc值就要重复存储了值就要重复存储了10次。次。(4)修改复杂修改复杂例如
45、学生转系，在修改此学生元组的例如学生转系，在修改此学生元组的Sdept值的同值的同时，还可能需要修改住处（时，还可能需要修改住处（Sloc）。如果这个学生）。如果这个学生选修了选修了K门课，则必须无遗漏地修改门课，则必须无遗漏地修改K个元组中全部个元组中全部Sdept、Sloc信息。信息。672NFv原因原因Sdept、Sloc部分函数依赖于码。部分函数依赖于码。v解决方法解决方法SLC分解为两个关系模式，以消除这些部分函数依分解为两个关系模式，以消除这些部分函数依赖赖SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）682NFvSLC的码为的码为(Sno,Cno)vSLC
46、满足第一范式。满足第一范式。v非主属性非主属性Sdept和和Sloc部分函数依赖于码部分函数依赖于码(Sno,Cno)SnoCnoGradeSdeptSlocSLC692NF函数依赖图函数依赖图：SnoCnoGradeSCSLSnoSdeptSloc702NFv2NF的定义的定义定义定义4.10若关系模式若关系模式R 1NF，并且每一个，并且每一个非主非主属属性都性都完全完全函数依赖于函数依赖于R的码，则的码，则R 2NF。例：例：SLC(Sno,Sdept,Sloc,Cno,Grade) 1NFSLC(Sno,Sdept,Sloc,Cno,Grade) 2NFSC（Sno，Cno，Grade
47、） 2NFSL（Sno，Sdept，Sloc） 2NF71第二范式（续）第二范式（续）v采用投影分解法将一个采用投影分解法将一个1NF的关系分解为多个的关系分解为多个2NF的关系，可以在一定程度上减轻原的关系，可以在一定程度上减轻原1NF关系中存在关系中存在的插入异常、删除异常、数据冗余度大、修改复杂的插入异常、删除异常、数据冗余度大、修改复杂等问题。等问题。v将一个将一个1NF关系分解为多个关系分解为多个2NF的关系，并不能完的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。全消除关系模式中的各种异常情况和数据冗余。724.4.33NF例：例：2NF关系模式关系模式SL(Sno,Sd
48、ept,Sloc)中中v函数依赖：函数依赖：SnoSdeptSdeptSlocSnoSlocSloc传递函数依赖于传递函数依赖于Sno，即，即SL中存在非主中存在非主属性对码的传递函数依赖。属性对码的传递函数依赖。733NF函数依赖图函数依赖图：SLSnoSdeptSloc743NFv解决方法解决方法采用投影分解法，把采用投影分解法，把SL分解为两个关系模式，以消除传分解为两个关系模式，以消除传递函数依赖：递函数依赖：SD（Sno，Sdept）DL（Sdept，Sloc）SD的码为的码为Sno，DL的码为的码为Sdept。753NFSD的码为的码为Sno，DL的码为的码为Sdept。SnoSd
49、eptSDSdeptSlocDL763NFv3NF的定义的定义定义定义4.11关系模式关系模式R中若不存在这样中若不存在这样的码的码X、属性组、属性组Y及及非主属性非主属性Z（Z Y）, 使得使得XY，YX，YZ，成立，则称，成立，则称R 3NF。例，例，SL(Sno,Sdept,Sloc) 2NFSL(Sno,Sdept,Sloc) 3NFSD（Sno，Sdept） 3NFDL（Sdept，Sloc） 3NF773NFv若若R 3NF，则，则R的每一个的每一个非主属性非主属性既不部分函数依赖于候既不部分函数依赖于候选码也不传递函数依赖于候选码。选码也不传递函数依赖于候选码。v如果如果R 3N
50、F，则，则R也是也是2NF。v采用投影分解法将一个采用投影分解法将一个2NF的关系分解为多个的关系分解为多个3NF的关系，的关系，可以在一定程度上解决原可以在一定程度上解决原2NF关系中存在的插入异常、删关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。除异常、数据冗余度大、修改复杂等问题。v将一个将一个2NF关系分解为多个关系分解为多个3NF的关系后，并不能完全消的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。除关系模式中的各种异常情况和数据冗余。784.4.4BC范式（范式（BCNF）v定义定义4.12设关系模式设关系模式R 1NF，如果对于，如果对于R的的每每个函
51、数依赖个函数依赖XY，若，若Y不属于不属于X，则，则X必含有候选码，那必含有候选码，那么么R BCNF。若若R BCNFv每一个决定属性集（因素）都包含（候选）码每一个决定属性集（因素）都包含（候选）码vR中的所有属性（主，非主属性）都完全函数依赖于码中的所有属性（主，非主属性）都完全函数依赖于码vR 3NF（证明）（证明）v若若R 3NF则则R不一定不一定 BCNF79BCNF例：在关系模式例：在关系模式STJ（S，T，J）中，）中，S表示学生，表示学生，T表示教师，表示教师，J表示课程。表示课程。v每一教师只教一门课。每门课由若干教师教，某一学每一教师只教一门课。每门课由若干教师教，某一学
52、生选定某门课，就确定了一个固定的教师。某个学生生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称选修某个教师的课就确定了所选课的名称：(S，J)T，(S，T)J，TJ80SJTSTJSTJBCNF81BCNFSTJ 3NFv(S，J)和和(S，T)都可以作为候选码都可以作为候选码vS、T、J都是主属性都是主属性STJ BCNFvTJ，T是决定属性集，是决定属性集，T不是候选码不是候选码82BCNF解决方法：将解决方法：将STJ分解为二个关系模式：分解为二个关系模式：SJ(S，J) BCNF，TJ(T，J) BCNF没有没有任何属性任何属性对码的部分函数依赖和传递
53、函数依赖对码的部分函数依赖和传递函数依赖SJSTTJTJ833NF与与BCNF的关系的关系v如果关系模式如果关系模式R BCNF，必定有必定有R 3NFv如果如果R 3NF，且，且R只有一个候选码，只有一个候选码，则则R必属于必属于BCNF。84BCNF的关系模式所具有的性质的关系模式所具有的性质所有所有非主属性非主属性都完全函数依赖于每个候选码都完全函数依赖于每个候选码所有所有主属性主属性都完全函数依赖于每个不包含它的候都完全函数依赖于每个不包含它的候选码选码没有任何属性完全函数依赖于没有任何属性完全函数依赖于非码非码的任何一组属的任何一组属性性855.2.5多值依赖与第四范式（多值依赖与第
54、四范式（4NF）例例:学校中某一门课程由多个教师讲授，他们学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。使用相同的一套参考书。关系模式关系模式Teaching(C,T,B)课程课程C、教师、教师T和和参考书参考书B86课课程程C教教员员T参参考考书书B物理物理数学数学计算数学计算数学李李勇勇王王军军李李勇勇张张平平张张平平周周峰峰普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析表表5.187普通物理学普通物理学光学原理光学原理物理习题集物理习题集普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数
55、学分析微分方程微分方程高等代数高等代数数学分析数学分析微分方程微分方程高等代数高等代数李李勇勇李李勇勇李李勇勇王王军军王王军军王王军军李李勇勇李李勇勇李李勇勇张张平平张张平平张张平平物物理理物物理理物物理理物物理理物物理理物物理理数数学学数数学学数数学学数数学学数数学学数数学学 参考书B教员T课程C用二维表表示用二维表表示Teaching88多值依赖与第四范式（续）多值依赖与第四范式（续）vTeaching BCNF:vTeach具有唯一候选码具有唯一候选码(C，T，B)，即全码即全码vTeaching模式中存在的问题模式中存在的问题(1)数据冗余度大：有多少名任课教师，参考书就要存数据冗余度
56、大：有多少名任课教师，参考书就要存储多少次储多少次89多值依赖与第四范式（续）多值依赖与第四范式（续）(2)插入操作复杂：当某一课程增加一名任课教师时，该课程插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组有多少本参照书，就必须插入多少个元组例如物理课增加一名教师刘关，需要插入三个元组：例如物理课增加一名教师刘关，需要插入三个元组：（物理，刘关，普通物理学）（物理，刘关，普通物理学）（物理，刘关，光学原理）（物理，刘关，光学原理）（物理，刘关，物理习题集）（物理，刘关，物理习题集）90多值依赖与第四范式（续）多值依赖与第四范式（续）(3)删除操作复杂：某一
57、门课要去掉一本参考书，删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组该课程有多少名教师，就必须删除多少个元组(4)修改操作复杂：某一门课要修改一本参考书，修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组该课程有多少名教师，就必须修改多少个元组v产生原因产生原因存在多值依赖存在多值依赖91一、多值依赖一、多值依赖v定义定义5.10设设R(U)是一个属性集是一个属性集U上的一个关系模式，上的一个关系模式，X、Y和和Z是是U的的子集，并且子集，并且ZUXY，多值依赖多值依赖XY成立当且仅当对成立当且仅当对R的的任一关系任一关系r，r在
58、（在（X，Z）上的每个值对应一组）上的每个值对应一组Y的值，的值，这组值仅仅决定于这组值仅仅决定于X值而与值而与Z值无关值无关例例Teaching（C,T,B）对于对于C的每一个值，的每一个值，T有一组值与之对应，而不论有一组值与之对应，而不论B取何值取何值92一、多值依赖一、多值依赖v在在R（U）的任一关系）的任一关系r中，如果存在元组中，如果存在元组t，s 使得使得tX=sX，那么就必然存在元组，那么就必然存在元组w，v r，（，（w，v可以可以与与s，t相同），使得相同），使得wX=vX=tX，而，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交换（即交换s，t元组的元组的Y值所得
59、的两个新元组必在值所得的两个新元组必在r中），则中），则Y多值依赖于多值依赖于X，记，记为为XY。这里，这里，X，Y是是U的子集，的子集，Z=U-X-Y。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z293多值依赖（续）多值依赖（续）v平凡多值依赖和非平凡的多值依赖平凡多值依赖和非平凡的多值依赖若若XY，而，而Z，则称，则称XY为为平凡的多值依赖平凡的多值依赖否则称否则称XY为为非平凡的多值依赖非平凡的多值依赖94多值依赖的性质多值依赖的性质（1）多值依赖具有对称性）多值依赖具有对称性若若XY，则，则XZ，其中，其中ZUXY多值依赖的对称性可以用完全二分图直观地
60、表示多值依赖的对称性可以用完全二分图直观地表示出来。出来。（2）多值依赖具有传递性）多值依赖具有传递性若若XY，YZ，则则XZ-Y95多值依赖的对称性多值依赖的对称性XiZi1Zi2ZimYi1Yi2Yin96多值依赖的对称性多值依赖的对称性物物理理普通物理学普通物理学光学原理光学原理物理习题集物理习题集李勇李勇王军王军97多值依赖（续）多值依赖（续）（3）函数依赖是多值依赖的特殊情况。）函数依赖是多值依赖的特殊情况。若若XY，则，则XY。（4）若）若XY，XZ，则，则XY Z。（5）若）若XY，XZ，则，则XYZ。（6）若）若XY，XZ，则，则XY-Z，XZ-Y。98多值依赖与函数依赖的区别
61、多值依赖与函数依赖的区别v多值依赖的有效性与属性集的范围有关多值依赖的有效性与属性集的范围有关若若XY在在U上成立，则在上成立，则在W（XY W U）上一定成立；）上一定成立；反之则不然，即反之则不然，即XY在在W（W U）上成立，在）上成立，在U上上并不一定成立并不一定成立多值依赖的定义中不仅涉及属性组多值依赖的定义中不仅涉及属性组X和和Y，而且涉及，而且涉及U中中其余属性其余属性Z。一般地，在一般地，在R（U）上若有）上若有XY在在W（W U）上成立，）上成立，则称则称XY为为R（U）的嵌入型多值依赖）的嵌入型多值依赖99多值依赖与函数依赖的区别多值依赖与函数依赖的区别v只要在只要在R（U
62、）的任何一个关系）的任何一个关系r中，元组在中，元组在X和和Y上上的值满足定义的值满足定义5.l（函数依赖），（函数依赖），则函数依赖则函数依赖XY在任何属性集在任何属性集W（XY W U）上成立上成立。100多值依赖（续）多值依赖（续）(2)若函数依赖若函数依赖XY在在R（U）上成立，则对于任何）上成立，则对于任何Y Y均有均有XY成立成立多值依赖多值依赖XY若在若在R(U)上成立，不能断言对上成立，不能断言对于任何于任何Y Y有有XY成立成立101二、第四范式（二、第四范式（4NF）v定义定义5.10关系模式关系模式R 1NF，如果对于，如果对于R的的每个非平凡多值依赖每个非平凡多值依赖X
63、Y（Y X），），X都含有都含有候选码，则候选码，则R 4NF。v如果如果R 4NF，则则R BCNF不允许不允许有非平凡且非函数依赖的有非平凡且非函数依赖的多值依赖多值依赖允许允许的是的是函数依赖函数依赖（是非平凡多值依赖）（是非平凡多值依赖）102第四范式（续）第四范式（续）例：例：Teach(C,T,B) 4NF存在非平凡的多值依赖存在非平凡的多值依赖CT，且，且C不是候选码不是候选码v用投影分解法把用投影分解法把Teach分解为如下两个关系模式：分解为如下两个关系模式：CT(C,T) 4NFCB(C,B) 4NFCT，CB是平凡多值依赖是平凡多值依赖1035.4模式的分解模式的分解v把
64、低一级的关系模式分解为若干个高一级的把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的关系模式的方法并不是唯一的v只有能够保证分解后的关系模式与原关系模只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义式等价，分解方法才有意义104关系模式分解的标准关系模式分解的标准三种模式分解的等价定义三种模式分解的等价定义分解具有无损连接性分解具有无损连接性分解要保持函数依赖分解要保持函数依赖分解既要保持函数依赖，又要具有无损连接性分解既要保持函数依赖，又要具有无损连接性105模式的分解模式的分解定义5.16关系模式关系模式R的一个分解：的一个分解：=R1，R2，RnU=U1 U
65、2 Un，且不存在且不存在Ui Uj，Fi为为F在在Ui上的投影定义5.17 函数依赖集合函数依赖集合XY |XY F+ XY Ui的的一个一个覆盖覆盖Fi 叫作叫作F 在属性在属性Ui 上的投影上的投影106模式的分解（续）模式的分解（续）例例:SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSlocSL 2NF存在插入异常、删除异常、冗余度大和修改复杂等问题存在插入异常、删除异常、冗余度大和修改复杂等问题分解方法可以有多种分解方法可以有多种107模式的分解（续）模式的分解（续）SLSnoSdeptSloc95001CSA95002ISB95003MAC9
66、5004ISB95005PHB108模式的分解（续）模式的分解（续）1.SL分解为下面三个关系模式：分解为下面三个关系模式：SN(Sno)SD(Sdept)SO(Sloc)109分解后的关系为：分解后的关系为：SNSDSOSnoSdeptSloc95001CSA95002ISB95003MAC95004PH95005110模式的分解（续）模式的分解（续）分解后的数据库分解后的数据库丢失了许多信息丢失了许多信息例例如如无无法法查查询询95001学学生生所所在在系系或或所所在在宿宿舍舍。如如果果分分解解后后的的关关系系可可以以通通过过自自然然连连接接恢恢复复为为原原来来的的关关系，那么这种分解就没
67、有系，那么这种分解就没有丢失信息丢失信息111模式的分解（续）模式的分解（续）2.SL分解为下面二个关系模式：分解为下面二个关系模式：NL(Sno,Sloc)DL(Sdept,Sloc)分解后的关系为：分解后的关系为：NLDLSnoSlocSdeptSloc95001ACSA95002B ISB95003CMAC95004B PHB95005B112模式的分解（续）模式的分解（续）NLDLSnoSlocSdept95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH113模式的分解（续）模式的分解（续）NLDL比原来的比
68、原来的SL关系多了关系多了3个元组个元组无法知道无法知道95002、95004、95005究竟是哪个系的学生究竟是哪个系的学生 元组增加了，信息丢失了元组增加了，信息丢失了114第三种分解方法第三种分解方法3.将将SL分解为下面二个关系模式：分解为下面二个关系模式：ND(Sno,Sdept)NL(Sno,Sloc)分解后的关系为：分解后的关系为：115模式的分解（续）模式的分解（续）NDNLSnoSdeptSnoSloc95001CS95001A95002IS95002B95003MA95003C95004IS95004B95005PH95005B116模式的分解（续）模式的分解（续）NDNL
69、SnoSdeptSloc95001CSA95002ISB95003MAC95004CSA95005PHB与与SL关系一样，因此没有丢失信息关系一样，因此没有丢失信息117具有无损连接性的模式分解具有无损连接性的模式分解v关系模式关系模式R的一个分解的一个分解=R1，R2，Rn若若R与与R1、R2、Rn自然连接的结果相等，则称关系自然连接的结果相等，则称关系模式模式R的这个分解的这个分解具有无损连接性（具有无损连接性（Losslessjoin）v具有无损连接性的分解保证不丢失信息具有无损连接性的分解保证不丢失信息v无损连接性不一定能解决插入异常、删除异常、修改复杂、无损连接性不一定能解决插入异常
70、、删除异常、修改复杂、数据冗余等问题数据冗余等问题118模式的分解（续）模式的分解（续）第三种分解方法具有无损连接性第三种分解方法具有无损连接性问题问题:这种分解方法没有保持原关系中的函数依赖这种分解方法没有保持原关系中的函数依赖SL中的函数依赖中的函数依赖SdeptSloc没有投影到关系模式没有投影到关系模式ND、NL上上119保持函数依赖的模式分解保持函数依赖的模式分解设关系模式设关系模式R被分解为若干个关系模式被分解为若干个关系模式R1，R2，Rn（其中（其中U=U1 U2 Un，且不存在，且不存在Ui Uj，Fi为为F在在Ui上的投影），若上的投影），若F所逻辑蕴含的函数依赖一定也由分
71、解所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则所逻辑蕴含，则称关系模式称关系模式R的这个分解是保持函数依赖的的这个分解是保持函数依赖的（Preservedependency）。）。120第四种分解方法第四种分解方法将将SL分解为下面二个关系模式：分解为下面二个关系模式：ND(Sno,Sdept)DL(Sdept,Sloc)这种分解方法就保持了函数依赖。这种分解方法就保持了函数依赖。121模式的分解（续）模式的分解（续）v如果一个分解具有无损连接性，则它能够保证如果一个分解具有无损连接性，则它能够保证不丢失信息。不丢失信息。v如果
72、一个分解保持了函数依赖，则它可以减轻如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。或解决各种异常情况。v分解具有无损连接性和分解保持函数依赖是两分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。的分解也不一定具有无损连接性。122模式的分解（续）模式的分解（续）第一种分解方法既不具有无损连接性，也未保第一种分解方法既不具有无损连接性，也未保持函数依赖，它不是原关系模式的一个等价分解持函数依赖，它不是原关
73、系模式的一个等价分解第二种分解方法保持了函数依赖，但不具有无第二种分解方法保持了函数依赖，但不具有无损连接性损连接性第三种分解方法具有无损连接性，但未持函数第三种分解方法具有无损连接性，但未持函数依赖依赖第四种分解方法既具有无损连接性，又保持了第四种分解方法既具有无损连接性，又保持了函数依赖函数依赖123分解算法分解算法v算法算法5.2判别一个分解的无损连接性判别一个分解的无损连接性v算算法法5.3（合合成成法法）转转换换为为3NF的的保保持持函函数数依依赖赖的的分分解。解。v算法算法5.4转换为转换为3NF既有无损连接性又保持函数依赖的既有无损连接性又保持函数依赖的分解分解v算法算法5.5转
74、换为转换为BCNF的无损连接分解（分解法）的无损连接分解（分解法）v算法算法5.6达到达到4NF的具有无损连接性的分的具有无损连接性的分124分解算法分解算法v若要求分解具有无损连接性，那么模式分解一若要求分解具有无损连接性，那么模式分解一定能够达到定能够达到4NF。v若要求分解保持函数依赖，那么模式分解一定若要求分解保持函数依赖，那么模式分解一定能够达到能够达到3NF，但不一定能够达到，但不一定能够达到BCNF。v若要求分解既具有无损连接性，又保持函数依若要求分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到赖，则模式分解一定能够达到3NF，但不一定，但不一定能够达到能够达到BCN
75、F。125泛关系假设泛关系假设v“假设已知一个模式假设已知一个模式S，它仅由单个关，它仅由单个关系模式组成，问题是要设计一个模式系模式组成，问题是要设计一个模式SD，它与，它与S等价等价，但在某些方面更好一，但在某些方面更好一些些”v从一个关系模式出发，而不是从一从一个关系模式出发，而不是从一组关系模式出发实行分解组关系模式出发实行分解v“等价等价”的定义也是一组关系模式与的定义也是一组关系模式与一个关系模式的一个关系模式的“等价等价”1265.2.6规范化规范化v关系数据库的规范化理论是数据库逻辑设计关系数据库的规范化理论是数据库逻辑设计的工具。的工具。v一个关系只要其分量都是不可分的数据项
76、，一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规它就是规范化的关系，但这只是最基本的规范化。范化。v规范化程度可以有多个不同的级别规范化程度可以有多个不同的级别127规范化（续）规范化（续）v规范化程度过低的关系不一定能够很好地描述规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题修改复杂、数据冗余等问题v一个低一级范式的关系模式，通过模式分解可一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，以转换为若干个高一级范式的关系模式集合，这种过程
77、就叫这种过程就叫关系模式的规范化关系模式的规范化128规范化（续）规范化（续）v关系模式规范化的基本步骤关系模式规范化的基本步骤1NF消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除决定属性消除决定属性2NF集非码的非平集非码的非平消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖凡函数依赖凡函数依赖3NF消除主属性对码的部分和传递函数依消除主属性对码的部分和传递函数依赖赖BCNF消除非平凡且非函数依赖的多值依赖消除非平凡且非函数依赖的多值依赖4NF129规范化的基本思想规范化的基本思想消除不合适的数据依赖消除不合适的数据依赖的各关系模式达到某种程度的的各关系模式达到
78、某种程度的“分离分离”采用采用“一事一地一事一地”的模式设计原则的模式设计原则让一个关系描述一个概念、一个实体或者实让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它体间的一种联系。若多于一个概念就把它“分离分离”出去出去所谓规范化实质上是概念的单一化所谓规范化实质上是概念的单一化130规范化（续）规范化（续）v不能说规范化程度越高的关系模式就越好不能说规范化程度越高的关系模式就越好v在设计数据库模式结构时，必须对现实世界的实际在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式的、能够反映现实世界的模式v上面的规范化步骤可以在其中任何一步终止上面的规范化步骤可以在其中任何一步终止131小结小结(续续)v规规范范化化理理论论为为数数据据库库设设计计提提供供了了理理论论的的指指南南和工具和工具也仅仅是指南和工具也仅仅是指南和工具v并不是规范化程度越高，模式就越好并不是规范化程度越高，模式就越好必必须须结结合合应应用用环环境境和和现现实实世世界界的的具具体体情情况况合合理理地地选择数据库模式选择数据库模式132谢谢观赏！谢谢观赏！
