《数据库系统概论第五版PPT第6章》由会员分享,可在线阅读,更多相关《数据库系统概论第五版PPT第6章(123页珍藏版)》请在金锄头文库上搜索。
1、中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem数据库系统概论数据库系统概论AnIntroductiontoDatabaseSystem第六章第六章 关系数据理论关系数据理论xx大大中国人民大学数据库系统概论AnIntroductiontoDatabaseSystemv基于某个数据库管理系统设计数据库,如何基于基于某个数据库管理系统设计数据库,如何基于数据库系统编程数据库系统编程n第第6章章关系数据理论关系数据理论n第第7章章数据库设计数据库设计n第第8章章数据库编程数据库编程第二篇第二篇 设计与应用开发篇设计与应用开发篇中国人民大学数据库系统概论AnIn
2、troductiontoDatabaseSystem第六章第六章关系数据理论关系数据理论n6.1问题的提出问题的提出v6.2规范化规范化v6.3数据依赖的公理系统数据依赖的公理系统v*6.4模式的分解模式的分解v6.5小结小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.1问题的提出问题的提出关系数据库逻辑设计关系数据库逻辑设计n针对具体问题,如何构造一个适合于它的数据模式针对具体问题,如何构造一个适合于它的数据模式n数据库逻辑设计的工具数据库逻辑设计的工具关系数据库的规范化理论关系数据库的规范化理论中国人民大学数据库系统概论AnIntroducti
3、ontoDatabaseSystem*问题的提出(续)问题的提出(续)v关系模式由五部分组成,是一个五元组:关系模式由五部分组成,是一个五元组:R(U,D,DOM,F)n关系名关系名R是符号化的元组语义是符号化的元组语义nU为一组属性为一组属性nD为属性组为属性组U中的属性所来自的域中的属性所来自的域nDOM为属性到域的映射为属性到域的映射nF为属性组为属性组U上的一组数据依赖上的一组数据依赖中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem问题的提出(续)问题的提出(续)n由于由于D、DOM与模式设计关系不大,因此在本章中把与模式设计关系不大,因此在本章中
4、把关系模式看作一个三元组:关系模式看作一个三元组:Rn当且仅当当且仅当U上的一个关系上的一个关系r满足满足F时,时,r称为关系模式称为关系模式R的一个关系的一个关系n作为二维表,关系要符合一个最基本的条件:每个分作为二维表,关系要符合一个最基本的条件:每个分量必须是不可分开的数据项。满足了这个条件的关系量必须是不可分开的数据项。满足了这个条件的关系模式就属于第一范式(模式就属于第一范式(1NF)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)v数据依赖数据依赖n是一个关系内部属性与属性之间的一种约束关系是一个关系内部属性与
5、属性之间的一种约束关系l通过属性间值的相等与否体现出来的数据间相互联系通过属性间值的相等与否体现出来的数据间相互联系n是现实世界属性间相互联系的抽象是现实世界属性间相互联系的抽象n是数据内在的性质是数据内在的性质n是语义的体现是语义的体现中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)v数据依赖的主要类型数据依赖的主要类型n函数依赖(函数依赖(FunctionalDependency,简记为,简记为FD)n多值依赖(多值依赖(Multi-ValuedDependency,简记为,简记为MVD)中国人民大学数据库系统概论An
6、IntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)v函数依赖普遍存在于现实生活中函数依赖普遍存在于现实生活中n描述一个学生关系,可以有学号、姓名、系名等属性。描述一个学生关系,可以有学号、姓名、系名等属性。l一个学号只对应一个学生,一个学生只在一个系中学习一个学号只对应一个学生,一个学生只在一个系中学习l“学号学号”值确定后,学生的姓名及所在系的值就被唯一确值确定后,学生的姓名及所在系的值就被唯一确定。定。nSname=f(Sno),Sdept=f(Sno)l即即Sno函数决定函数决定SnamelSno函数决定函数决定Sdeptl记作记作SnoSname
7、,SnoSdept中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)v例例6.1建立一个描述学校教务的数据库。建立一个描述学校教务的数据库。涉及的对象包括:涉及的对象包括:n学生的学号(学生的学号(Sno)n所在系(所在系(Sdept)n系主任姓名(系主任姓名(Mname)n课程号(课程号(Cno)n成绩(成绩(Grade)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)n假设学校教务的数据库模式用一个单一的关系模式假设学校教务的数据库模式用一个单一的关
8、系模式Student来表示,则该关系模式的属性集合为:来表示,则该关系模式的属性集合为:nUSno,Sdept,Mname,Cno,Graden现实世界的已知事实(语义):现实世界的已知事实(语义):l一个系有若干学生,一个系有若干学生, 但一个学生只属于一个系;但一个学生只属于一个系;l一个系只有一名(正职)负责人;一个系只有一名(正职)负责人;l一个学生可以选修多门课程,每门课程有若干学生选修;一个学生可以选修多门课程,每门课程有若干学生选修;l每个学生学习每一门课程有一个成绩。每个学生学习每一门课程有一个成绩。 中国人民大学数据库系统概论AnIntroductiontoDatabaseS
9、ystem*问题的提出(续)问题的提出(续)n由此可得到属性组由此可得到属性组U上的一组函数依赖上的一组函数依赖F:vF=SnoSdept,SdeptMname,(Sno,Cno)GradeSnoCnoSdeptMnameGrade中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)v关系模式关系模式Student中存在的问题:中存在的问题:v(1)数据冗余)数据冗余n浪费大量的存储空间浪费大量的存储空间l每一个系主任的姓名重复出现,重复次数与该系所有学每一个系主任的姓名重复出现,重复次数与该系所有学生的所有课程成绩出现次数相
10、同。生的所有课程成绩出现次数相同。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)(2)更新异常()更新异常(UpdateAnomalies)n数据冗余数据冗余,更新数据时,维护数据完整性代价大。更新数据时,维护数据完整性代价大。l某系更换系主任后,必须修改与该系学生有关的每一个某系更换系主任后,必须修改与该系学生有关的每一个元组。元组。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)v(3)插入异常()插入异常(InsertionAnomalies)
11、n如果一个系刚成立,尚无学生,则无法把这个系及其如果一个系刚成立,尚无学生,则无法把这个系及其系主任的信息存入数据库。系主任的信息存入数据库。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)(4)删除异常()删除异常(DeletionAnomalies)n如果某个系的学生全部毕业了,如果某个系的学生全部毕业了,则在删除该系学生信则在删除该系学生信息的同时,把这个系及其系主任的信息也丢掉了。息的同时,把这个系及其系主任的信息也丢掉了。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题
12、的提出(续)问题的提出(续)v结论结论nStudent关系模式不是一个好的模式。关系模式不是一个好的模式。n一个一个“好好”的模式应当不会发生插入异常、删除异常和更的模式应当不会发生插入异常、删除异常和更新异常,数据冗余应尽可能少。新异常,数据冗余应尽可能少。v原因原因n由存在于模式中的某些数据依赖引起的。由存在于模式中的某些数据依赖引起的。v解决方法解决方法n用规范化理论改造关系模式来消除其中不合适的数据依赖用规范化理论改造关系模式来消除其中不合适的数据依赖中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*问题的提出(续)问题的提出(续)v把这个单一的模
13、式分成三个关系模式:把这个单一的模式分成三个关系模式:nS(Sno,Sdept,SnoSdept);nSC(Sno,Cno,Grade,(Sno,Cno)Grade);nDEPT(Sdept,Mname,SdeptMname);v这三个模式都不会发生插入异常、删除异常的问这三个模式都不会发生插入异常、删除异常的问题,数据的冗余也得到了控制。题,数据的冗余也得到了控制。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem第六章第六章关系数据理论关系数据理论n6.1问题的提出问题的提出n6.2规范化规范化v6.3数据依赖的公理系统数据依赖的公理系统v*6.4模式的
14、分解模式的分解v6.5小结小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.2规范化规范化v6.2.1函数依赖函数依赖v6.2.2码码v6.2.3范式范式v6.2.42NFv6.2.53NFv6.2.6BCNFv6.2.7多值依赖多值依赖v6.2.84NFv6.2.9规范化小结规范化小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.2.1函数依赖函数依赖v1.函数依赖函数依赖v2.平凡函数依赖与非平凡函数依赖平凡函数依赖与非平凡函数依赖v3.完全函数依赖与部分函数依赖完全函数依赖与部分函数依赖v4.传递函数
15、依赖传递函数依赖中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*1.函数依赖函数依赖v定义定义6.1设设R(U)是一个属性集是一个属性集U上的关系模式,上的关系模式,X和和Y是是U的子集。若对于的子集。若对于R(U)的任意一个可能的关的任意一个可能的关系系r,r中不可能存在两个元组在中不可能存在两个元组在X上的属性值相上的属性值相等,等,而在而在Y上的属性值不等,上的属性值不等,则称则称“X函数确定函数确定Y”或或“Y函数依赖于函数依赖于X”,记作,记作XY。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem函数依赖(
16、续)函数依赖(续)v例例Student(Sno,Sname,Ssex,Sage,Sdept),v假设不允许重名,则有假设不允许重名,则有:vSnoSsex,SnoSagevSnoSdept,SnoSnamevSnameSsex,SnameSagevSnameSdeptn但但SsexSage,SsexSdept若若XY,并且,并且YX,则记为则记为XY。若若Y不函数依赖于不函数依赖于X,则记为则记为XY。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem函数依赖(续)函数依赖(续)SnoSnameSsexSageSdeptS1 张三张三男男20计算机系计算机系
17、S1李四李四女女21自动化系自动化系S3王五王五男男20计算机系计算机系S4赵六赵六男男21计算机系计算机系S5田七田七男男20计算机系计算机系.违背了违背了SnoSname中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem函数依赖(续)函数依赖(续)v由下面的关系表由下面的关系表,能否得出能否得出SnoSnameSnoSnameSsexSageSdeptS1张三张三男男20计算机系计算机系S2李四李四女女21自动化系自动化系S3王五王五男男20计算机系计算机系S4赵六赵六男男21计算机系计算机系S5田七田七男男20计算机系计算机系.函数依赖不是指关系模式函
18、数依赖不是指关系模式R的某个或某些关系实例满足的的某个或某些关系实例满足的约束条件,而是指约束条件,而是指R的所有关系实例均要满足的约束条件。的所有关系实例均要满足的约束条件。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*函数依赖(续)函数依赖(续)v函数依赖是语义范畴的概念,只能根据数据的语函数依赖是语义范畴的概念,只能根据数据的语义来确定一个函数依赖。义来确定一个函数依赖。n例如例如“姓名姓名年龄年龄”这个函数依赖只有在不允许有同这个函数依赖只有在不允许有同名人的条件下成立名人的条件下成立中国人民大学数据库系统概论AnIntroductiontoD
19、atabaseSystem*2.平凡函数依赖与非平凡函数依赖平凡函数依赖与非平凡函数依赖vXY,但,但Y X则称则称XY是是非平凡的函数依赖非平凡的函数依赖。vXY,但,但Y X则称则称XY是是平凡的函数依赖平凡的函数依赖。对于任一关系模式,平凡函数依赖都是必然成立的,它对于任一关系模式,平凡函数依赖都是必然成立的,它不反映新的语义。不反映新的语义。若不特别声明,若不特别声明, 我们总是讨论非平凡函数依赖。我们总是讨论非平凡函数依赖。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*平凡函数依赖与非平凡函数依赖(续)平凡函数依赖与非平凡函数依赖(续)v若若
20、XY,则,则X称为这个函数依赖的称为这个函数依赖的决定因素决定因素(Determinant)。)。v若若XY,YX,则记作,则记作XY。v若若Y不函数依赖于不函数依赖于X,则记作,则记作XY。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*3.完全函数依赖与部分函数依赖完全函数依赖与部分函数依赖v定义定义6.2在在R(U)中,如果中,如果XY,并且对于,并且对于X的任的任何一个真子集何一个真子集X,都有都有X Y,则称则称Y对对X完全函数完全函数依赖依赖,记作,记作XY。v若若XY,但,但Y不完全函数依赖于不完全函数依赖于X,则称,则称Y对对X部部分函数
21、依赖分函数依赖,记作,记作XYFP中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*完全函数依赖与部分函数依赖(续)完全函数依赖与部分函数依赖(续)v例例在关系在关系SC(Sno,Cno,Grade)中,有:中,有:n由于:由于:SnoGrade,CnoGrade,v因此:因此:(Sno,Cno)Graden(Sno,Cno)Snon(Sno,Cno)CnoFPP中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*4.传递函数依赖传递函数依赖v定义定义6.3在在R(U)中,如果中,如果XY(Y X),YX,YZ,Z Y,
22、则称则称Z对对X传递函数依赖传递函数依赖(transitivefunctionaldependency)。记为:。记为:XZ。n注注:如果如果YX,即即XY,则,则Z直接依赖于直接依赖于X,而不是,而不是传递函数依赖。传递函数依赖。n例例在关系在关系Std(Sno,Sdept,Mname)中,有:中,有:SnoSdept,SdeptMname,Mname传递函数依赖于传递函数依赖于Sno传递传递中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.2规范化规范化v6.2.1函数依赖函数依赖v6.2.2码码v6.2.3范式范式v6.2.42NFv6.2.53N
23、Fv6.2.6BCNFv6.2.7多值依赖多值依赖v6.2.84NFv6.2.9规范化小结规范化小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*6.2.2码码v定义定义6.4设设K为为R中的属性或属性组合。若中的属性或属性组合。若KU,则,则K称为称为R的一个的一个候选码候选码(CandidateKey)。n如果如果U部分函数依赖于部分函数依赖于K,即,即KU,则则K称为超码称为超码(Surpkey)。候选码是最小的超码,即)。候选码是最小的超码,即K的任意一个的任意一个真子集都不是候选码。真子集都不是候选码。v若关系模式若关系模式R有多个候选码,则
24、选定其中的一个有多个候选码,则选定其中的一个做为做为主码主码(Primarykey)。FP中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*码(续)码(续)v主属性与非主属性主属性与非主属性n包含在任何一个候选码中的属性包含在任何一个候选码中的属性,称为主属性,称为主属性(Primeattribute)n不包含在任何码中的属性称为非主属性(不包含在任何码中的属性称为非主属性(Nonprimeattribute)或非码属性()或非码属性(Non-keyattribute)v全码:整个属性组是码,称为全码(全码:整个属性组是码,称为全码(All-key)中国人
25、民大学数据库系统概论AnIntroductiontoDatabaseSystem*码(续)码(续)v例例6.2S(Sno,Sdept,Sage),单个属性,单个属性Sno是码是码vSC(Sno,Cno,Grade)中,中,(Sno,Cno)是码是码v例例6.3R(P,W,A)P:演奏者:演奏者W:作品:作品A:听众:听众v一个演奏者可以演奏多个作品一个演奏者可以演奏多个作品v某一作品可被多个演奏者演奏某一作品可被多个演奏者演奏v听众可以欣赏不同演奏者的不同作品听众可以欣赏不同演奏者的不同作品 v码为码为(P,W,A),即,即All-Key中国人民大学数据库系统概论AnIntroductiont
26、oDatabaseSystem*码(续)码(续)v定义定义6.5关系模式关系模式R中属性或属性组中属性或属性组X并非并非R的的码,但码,但X是另一个关系模式的码,则称是另一个关系模式的码,则称X是是R的的外部码外部码(Foreignkey)也称)也称外码外码。nSC(Sno,Cno,Grade)中,中,Sno不是码不是码nSno是是S(Sno,Sdept,Sage)的码,则的码,则Sno是是SC的外码的外码v主码与外部码一起提供了表示关系间联系的手段主码与外部码一起提供了表示关系间联系的手段中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.2规范化规范化
27、v6.2.1函数依赖函数依赖v6.2.2码码v6.2.3范式范式v6.2.42NFv6.2.53NFv6.2.6BCNFv6.2.7多值依赖多值依赖v6.2.84NFv6.2.9规范化小结规范化小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*6.2.3范式范式v范式是符合某一种级别的关系模式的集合。范式是符合某一种级别的关系模式的集合。v关系数据库中的关系必须满足一定的要求。满足关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。不同程度要求的为不同范式。v范式的种类:范式的种类:第一范式第一范式(1NF)第二范式第二范式(2NF)第
28、三范式第三范式(3NF)BC范式范式(BCNF)第四范式第四范式(4NF)第五范式第五范式(5NF)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*范式(续)范式(续)v各种范式之间存在联系:各种范式之间存在联系:n某一关系模式某一关系模式R为第为第n范式,可简记为范式,可简记为R nNF。v一个低一级范式的关系模式,通一个低一级范式的关系模式,通过模式分解(过模式分解(schemadecomposition)可以转换为若)可以转换为若干个高一级范式的关系模式的集干个高一级范式的关系模式的集合,这种过程就叫合,这种过程就叫规范化规范化(normaliza
29、tion)。)。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.2规范化规范化v6.2.1函数依赖函数依赖v6.2.2码码v6.2.3范式范式v6.2.42NFv6.2.53NFv6.2.6BCNFv6.2.7多值依赖多值依赖v6.2.84NFv6.2.9规范化小结规范化小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*6.2.42NFv定义定义6.6若关系模式若关系模式R 1NF,并且每一个非主属性,并且每一个非主属性都完全函数依赖于任何一个候选码,则都完全函数依赖于任何一个候选码,则R 2NFv例例6.4S
30、-L-C(Sno,Sdept,Sloc,Cno,Grade),Sloc为学生的住处,并且每个系的学生住在同一个为学生的住处,并且每个系的学生住在同一个地方。地方。S-L-C的码为的码为(Sno,Cno)。v函数依赖有函数依赖有n(Sno,Cno)GradenSnoSdept,(Sno,Cno)SdeptnSnoSloc,(Sno,Cno)SlocnSdeptSlocFPP中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*2NF(续)(续)SnoCnoGradeSdeptSlocn关系模式关系模式S-L-C不属于不属于2NFn非主属性非主属性Sdept、Sl
31、oc并不完全依赖于码并不完全依赖于码中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*2NF(续)(续)v一个关系模式不属于一个关系模式不属于2NF,会产生以下问题:,会产生以下问题:n插入异常插入异常l如果插入一个新学生,但该生未选课,即该生无如果插入一个新学生,但该生未选课,即该生无Cno,由于插入元组时,必须给定码值,因此插入失败。由于插入元组时,必须给定码值,因此插入失败。n删除异常删除异常l如果如果S4只选了一门课只选了一门课C3,现在他不再选这门课,则删除,现在他不再选这门课,则删除C3后,整个元组的其他信息也被删除了。后,整个元组的其他信息也
32、被删除了。n修改复杂修改复杂l如果一个学生选了多门课,则如果一个学生选了多门课,则Sdept,Sloc被存储了多被存储了多次。如果该生转系,则需要修改所有相关的次。如果该生转系,则需要修改所有相关的Sdept和和Sloc,造成修改的复杂化。,造成修改的复杂化。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*2NF(续)(续)v出现这种问题的原因出现这种问题的原因n例子中有两类非主属性:例子中有两类非主属性:l一类如一类如Grade,它对码完全函数依赖,它对码完全函数依赖l另一类如另一类如Sdept、Sloc,它们对码不是完全函数依赖,它们对码不是完全函数
33、依赖v解决方法:解决方法:n用投影分解把关系模式用投影分解把关系模式S-L-C分解成两个关系模式分解成两个关系模式lSC(Sno,Cno,Grade)lS-L(Sno,Sdept,Sloc)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem2NF(续)(续)nSC的码为的码为(Sno,Cno),SL的码为的码为Sno,这样使得非主属,这样使得非主属性对码都是完全函数依赖了性对码都是完全函数依赖了SnoCnoGradeSnoSdeptSloc图图6.4SC中的函数依赖中的函数依赖图图6.5S-L中的函数依赖中的函数依赖中国人民大学数据库系统概论AnIntrod
34、uctiontoDatabaseSystem6.2规范化规范化v6.2.1函数依赖函数依赖v6.2.2码码v6.2.3范式范式v6.2.42NFv6.2.53NFv6.2.6BCNFv6.2.7多值依赖多值依赖v6.2.84NFv6.2.9规范化小结规范化小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*6.2.53NFv定义定义6.7设关系模式设关系模式R 1NF,若若R中不存在中不存在这样的码这样的码X、属性组、属性组Y及非主属性及非主属性Z(Z Y),使使得得XY,YZ成立,成立,YX不成立,则称不成立,则称R 3NF。nSC没有传递依赖,因此没
35、有传递依赖,因此SC 3NFnS-L中中SnoSdept(SdeptSno),SdeptSloc,可得可得SnoSloc。n解决的办法是将解决的办法是将S-L分解成分解成lS-D(Sno,Sdept)3NFlD-L(Sdept,Sloc)3NF传递传递中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.2规范化规范化v6.2.1函数依赖函数依赖v6.2.2码码v6.2.3范式范式v6.2.42NFv6.2.53NFv6.2.6BCNFv6.2.7多值依赖多值依赖v6.2.84NFv6.2.9规范化小结规范化小结中国人民大学数据库系统概论AnIntroduc
36、tiontoDatabaseSystem*6.2.6BCNFvBCNF(BoyceCoddNormalForm)由)由Boyce和和Codd提出,比提出,比3NF更进了一步。通常认为更进了一步。通常认为BCNF是修正的第三范式,有时也称为扩充的第是修正的第三范式,有时也称为扩充的第三范式。三范式。v定义定义6.8设关系模式设关系模式R 1NF,若,若XY且且YX时时X必含有码,则必含有码,则R BCNF。v换言之,在关系模式换言之,在关系模式R中,如果每一个决定中,如果每一个决定属性集都包含候选码,则属性集都包含候选码,则R BCNF。中国人民大学数据库系统概论AnIntroductionto
37、DatabaseSystem*BCNF(续)(续)vBCNF的关系模式所具有的性质的关系模式所具有的性质n所有非主属性都完全函数依赖于每个候选码所有非主属性都完全函数依赖于每个候选码n所有主属性都完全函数依赖于每个不包含它的候选码所有主属性都完全函数依赖于每个不包含它的候选码n没有任何属性完全函数依赖于非码的任何一组属性没有任何属性完全函数依赖于非码的任何一组属性v如如果果一一个个关关系系数数据据库库中中的的所所有有关关系系模模式式都都属属于于BCNF,那那么么在在函函数数依依赖赖范范畴畴内内,它它已已实实现现了了模模式式的的彻彻底底分分解解,达达到到了了最最高高的的规规范范化化程程度度,消消
38、除除了了插插入异常和删除异常。入异常和删除异常。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystemv例例6.5考察关系模式考察关系模式C(Cno,Cname,Pcno)n它它只只有有一一个个码码Cno,没没有有任任何何属属性性对对Cno部部分分依依赖赖或或传递依赖,所以传递依赖,所以C 3NF。n同时同时C中中Cno是唯一的决定因素,所以是唯一的决定因素,所以C BCNF。n对于关系模式对于关系模式SC(Sno,Cno,Grade)可作同样分析。可作同样分析。BCNF(续)(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSys
39、temv例例6.6关系模式关系模式S(Sno,Sname,Sdept,Sage),n假定假定Sname也具有唯一性,那么也具有唯一性,那么S就有两个码,这两个就有两个码,这两个码都由单个属性组成,彼此不相交。码都由单个属性组成,彼此不相交。n其他属性不存在对码的传递依赖与部分依赖,所以其他属性不存在对码的传递依赖与部分依赖,所以S 3NF。n同时同时S中除中除Sno,Sname外没有其他决定因素,所以外没有其他决定因素,所以S也属于也属于BCNF。BCNF(续)(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystemv例例6.7关系模式关系模式SJP(S,J
40、,P)中,中,S是学生,是学生,J表表示示v课程,课程,P表示名次。每一个学生选修每门课程表示名次。每一个学生选修每门课程的的v成绩有一定的名次,每门课程中每一名次只有成绩有一定的名次,每门课程中每一名次只有一一v个学生(即没有并列名次)。个学生(即没有并列名次)。n由语义可得到函数依赖:由语义可得到函数依赖:(S,J)P;(J,P)Sn(S,J)与与(J,P)都可以作为候选码。都可以作为候选码。n关系模式中没有属性对码传递依赖或部分依赖,所以关系模式中没有属性对码传递依赖或部分依赖,所以nSJP 3NF。n除除(S,J)与与(J,P)以外没有其他决定因素,所以以外没有其他决定因素,所以nSJ
41、P BCNF。BCNF(续)(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystemBCNF(续)(续)v例例6.8关系模式关系模式STJ(S,T,J)中,中,S表示学生,表示学生,T表表v示教师,示教师,J表示课程。每一教师只教一门课。每表示课程。每一教师只教一门课。每v门课有若干教师,某一学生选定某门课,就对门课有若干教师,某一学生选定某门课,就对应应v一个固定的教师。一个固定的教师。n由语义可得到函数依赖:由语义可得到函数依赖:(S,J)T;(S,T)J;TJn因为没有任何非主属性对码传递依赖或部分依赖,因为没有任何非主属性对码传递依赖或部分依赖,nS
42、TJ 3NF。n因为因为T是决定因素,而是决定因素,而T不包含码,所以不包含码,所以STJ BCNFn关系。关系。图图6.6STJ中的函数依赖中的函数依赖中国人民大学数据库系统概论AnIntroductiontoDatabaseSystemBCNF(续)(续)v对于不是对于不是BCNF的关系模式,仍然存在不合适的的关系模式,仍然存在不合适的地方。地方。v非非BCNF的关系模式也可以通过分解成为的关系模式也可以通过分解成为BCNF。例如例如STJ可分解为可分解为ST(S,T)与与TJ(T,J),它们都是,它们都是BCNF。中国人民大学数据库系统概论AnIntroductiontoDatabase
43、SystemBCNF(续)(续)v3NF和和BCNF是在函数依赖的条件下对模式分解所是在函数依赖的条件下对模式分解所能达到的分离程度的测度。能达到的分离程度的测度。n一个模式中的关系模式如果都属于一个模式中的关系模式如果都属于BCNF,那么在函数,那么在函数依赖范畴内,它已实现了彻底的分离,已消除了插入依赖范畴内,它已实现了彻底的分离,已消除了插入和删除的异常。和删除的异常。n3NF的的“不彻底不彻底”性表现在可能存在主属性对码的部分性表现在可能存在主属性对码的部分依赖和传递依赖。依赖和传递依赖。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.2规范化
44、规范化v6.2.1函数依赖函数依赖v6.2.2码码v6.2.3范式范式v6.2.42NFv6.2.53NFv6.2.6BCNFv6.2.7多值依赖多值依赖v6.2.84NFv6.2.9规范化小结规范化小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*6.2.7多值依赖多值依赖v例例6.9设学校中某一门课程由多个教师讲授,他设学校中某一门课程由多个教师讲授,他们们v使用相同的一套参考书。使用相同的一套参考书。每个教员可以讲授多门每个教员可以讲授多门课课v程,每种参考书可以供多门课程使用程,每种参考书可以供多门课程使用n用关系模式用关系模式Teaching
45、(C,T,B)来表示课程来表示课程C、教师、教师T和参和参n考书考书B之间的关系。之间的关系。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem多值依赖(续)多值依赖(续)表表6.3非规范化关系示例非规范化关系示例课程课程 C教员教员 T参考书参考书 B物理物理数学数学计算数学计算数学李李勇勇王王军军李李勇勇张张平平张张平平周周峰峰普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(续)多值依赖
46、(续)表表6.4规范化规范化的二维表的二维表Teaching课程课程C教员教员T参考书参考书B物物理理李李勇勇普通物理学普通物理学物物理理李李勇勇光学原理光学原理物物理理李李勇勇物理习题集物理习题集物物理理王王军军普通物理学普通物理学物物理理王王军军光学原理光学原理物物理理王王军军物理习题集物理习题集数数学学李李勇勇普通物理学普通物理学数数学学李李勇勇光学原理光学原理数数学学李李勇勇物理习题集物理习题集数数学学张张平平普通物理学普通物理学数数学学张张平平光学原理光学原理数数学学张张平平物理习题集物理习题集中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多
47、值依赖(续)多值依赖(续)vTeaching具有唯一候选码具有唯一候选码(C,T,B),即全码。即全码。vTeaching BCNF中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(续)多值依赖(续)课程课程C教员教员T参考书参考书B物物理理李李勇勇普通物理学普通物理学物物理理李李勇勇光学原理光学原理物物理理李李勇勇物理习题集物理习题集物物理理王王军军普通物理学普通物理学物物理理王王军军光学原理光学原理物物理理王王军军物理习题集物理习题集数数学学李李勇勇普通物理学普通物理学数数学学李李勇勇光学原理光学原理数数学学李李勇勇物理习题集物理习题集数数学
48、学张张平平普通物理学普通物理学数数学学张张平平光学原理光学原理数数学学张张平平物理习题集物理习题集(1)数据冗余度大:有多数据冗余度大:有多少名任课教师,参考书少名任课教师,参考书就要存储多少次。就要存储多少次。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(续)多值依赖(续)课程课程C教员教员T参考书参考书B物物理理李李勇勇普通物理学普通物理学物物理理李李勇勇光学原理光学原理物物理理李李勇勇物理习题集物理习题集物物理理王王军军普通物理学普通物理学物物理理王王军军光学原理光学原理物物理理王王军军物理习题集物理习题集数数学学李李勇勇普通物理学普通
49、物理学数数学学李李勇勇光学原理光学原理数数学学李李勇勇物理习题集物理习题集数数学学张张平平普通物理学普通物理学数数学学张张平平光学原理光学原理数数学学张张平平物理习题集物理习题集(2)增加操作复杂:当增加操作复杂:当某一课程增加一名任某一课程增加一名任课教师时,该课程有课教师时,该课程有多少本参照书,就必多少本参照书,就必须插入多少个元组。须插入多少个元组。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(续)多值依赖(续)课程课程C教员教员T参考书参考书B物物理理李李勇勇普通物理学普通物理学物物理理李李勇勇光学原理光学原理物物理理李李勇勇物理习
50、题集物理习题集物物理理王王军军普通物理学普通物理学物物理理王王军军光学原理光学原理物物理理王王军军物理习题集物理习题集数数学学李李勇勇普通物理学普通物理学数数学学李李勇勇光学原理光学原理数数学学李李勇勇物理习题集物理习题集数数学学张张平平普通物理学普通物理学数数学学张张平平光学原理光学原理数数学学张张平平物理习题集物理习题集(3)删除操作复杂:某一删除操作复杂:某一门课要去掉一本参考书,门课要去掉一本参考书,该课程有多少名教师,该课程有多少名教师,就必须删除多少个元组。就必须删除多少个元组。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(续)多
51、值依赖(续)课程课程C教员教员T参考书参考书B物物理理李李勇勇普通物理学普通物理学物物理理李李勇勇光学原理光学原理物物理理李李勇勇物理习题集物理习题集物物理理王王军军普通物理学普通物理学物物理理王王军军光学原理光学原理物物理理王王军军物理习题集物理习题集数数学学李李勇勇普通物理学普通物理学数数学学李李勇勇光学原理光学原理数数学学李李勇勇物理习题集物理习题集数数学学张张平平普通物理学普通物理学数数学学张张平平光学原理光学原理数数学学张张平平物理习题集物理习题集(4)修改操作复杂:某一修改操作复杂:某一门课要修改一本参考书,门课要修改一本参考书,该课程有多少名教师,该课程有多少名教师,就必须修改多
52、少个元组。就必须修改多少个元组。产生原因产生原因: 存在多值依赖存在多值依赖中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(续)多值依赖(续)v定义定义6.9设设R(U)是属性集是属性集U上的一个关系模式。上的一个关系模式。X,Y,Z是是U的子集,并且的子集,并且Z=U-X-Y。关系模式。关系模式R(U)中多值依赖中多值依赖XY成立,当且仅当对成立,当且仅当对R(U)的任一的任一关系关系r,给定的一对,给定的一对(x,z)值,有一组值,有一组Y的值,这组的值,这组值仅仅决定于值仅仅决定于x值而与值而与z值无关。值无关。v例例Teaching(C
53、,T,B)v对于对于C的每一个值,的每一个值,T有一组值与之对应,而不有一组值与之对应,而不论论vB取何值。因此取何值。因此T多值依赖于多值依赖于C,即,即CT。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem多值依赖(续)多值依赖(续)v多值依赖的另一个等价的定义多值依赖的另一个等价的定义n在在R(U)的任一关系的任一关系r中,如果存在元组中,如果存在元组t,s使得使得tX=sXn,那么就必然存在元组,那么就必然存在元组w,vr,(,(w,v可以与可以与s,t相相n同)同),使得使得wX=vX=tX,而,而wY=tY,wZ=sZ,nvY=sY,vZ=tZ
54、(即交换(即交换s,t元组的元组的Y值所得的两值所得的两n个新元组必在个新元组必在r中则中则Y多值依赖于多值依赖于X,记为,记为XY。这。这里里nX,Y是是U的子集,的子集,Z=U-X-Y。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(续)多值依赖(续)v平凡多值依赖和非平凡的多值依赖平凡多值依赖和非平凡的多值依赖n若若XY,而,而Z,即,即Z为空,为空,则称则称XY为为平凡平凡的多值依赖的多值依赖。n否则称否则称XY为为非平凡的多值依赖非平凡的多值依赖。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem多
55、值依赖(续)多值依赖(续)WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C5例例6.10关系模式关系模式WSC(W,S,C)中,中,W表示仓库,表示仓库,S表示保管表示保管员,员,C表示商品。假设每个仓库有若干个保管员,有若干种表示商品。假设每个仓库有若干个保管员,有若干种商品。每个保管员保管所在仓库的所有商品,每种商品被所商品。每个保管员保管所在仓库的所有商品,每种商品被所有保管员保管。有保管员保管。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem多值依赖(续)多值依赖(续)v按
56、照语义对于按照语义对于W的每一个值的每一个值Wi,S有一个完整的集有一个完整的集合与之对应而不问合与之对应而不问C取何值。所以取何值。所以WS。v如图如图6.7所示所示n对应对应W的某一个值的某一个值Wi的全部的全部S值记作值记作SWi(表示此仓库(表示此仓库工作的全部保管员)工作的全部保管员)n全部全部C值记作值记作CWi(表示在此仓库中存放的所有商品)(表示在此仓库中存放的所有商品)n应当有应当有SWi中的每一个值和中的每一个值和CWi中的每一个中的每一个C值对应值对应n于是于是SWi与与CWi之间正好形成一个完全二分图,因而之间正好形成一个完全二分图,因而WS。中国人民大学数据库系统概论
57、AnIntroductiontoDatabaseSystem多值依赖(续)多值依赖(续)v由于由于C与与S的完全对称性,必然有的完全对称性,必然有WC成立。成立。图图6.7WS且且WC中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem多值依赖(续)多值依赖(续)v多值依赖的性质多值依赖的性质(1)多值依赖具有对称性。)多值依赖具有对称性。即若即若XY,则,则XZ,其中,其中ZUXYl多值依赖的对称性可以用完全二分图直观地表示出来。多值依赖的对称性可以用完全二分图直观地表示出来。l从从例例6.10容易看出,因为每个保管员保管所有商品,容易看出,因为每个保管员保
58、管所有商品,同时每种商品被所有保管员保管,显然若同时每种商品被所有保管员保管,显然若WS,必然,必然有有WC。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(续)多值依赖(续)n(2)多值依赖具有传递性。即若)多值依赖具有传递性。即若XY,YZ,则则XZ-Y。n(3)函数依赖是多值依赖的特殊情况。即若)函数依赖是多值依赖的特殊情况。即若XY,则,则n XY。n(4)若)若XY,XZ,则,则XYZ。n(5)若)若XY,XZ,则,则XYZ。n(6)若)若XY,XZ,则,则XY-Z,XZ-Y。中国人民大学数据库系统概论AnIntroductionto
59、DatabaseSystem*多值依赖(续)多值依赖(续)v多值依赖与函数依赖的区别多值依赖与函数依赖的区别n(1)多值依赖的有效性与属性集的范围有关)多值依赖的有效性与属性集的范围有关l若若XY在在U上成立,则在上成立,则在W(XY W U)上一定成)上一定成立;反之则不然,即立;反之则不然,即XY在在W(W U)上成立,在)上成立,在U上并不一定成立。上并不一定成立。l原因:多值依赖的定义中不仅涉及属性组原因:多值依赖的定义中不仅涉及属性组X和和Y,而且涉,而且涉及及U中其余属性中其余属性Z。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(
60、续)多值依赖(续)n多值依赖的有效性与属性集的范围有关(续)多值依赖的有效性与属性集的范围有关(续)l一般地,在一般地,在R(U)上若有上若有XY在在W(W U)上成立,则上成立,则称称XY为为R(U)的嵌入型多值依赖。的嵌入型多值依赖。l函数依赖函数依赖XY的有效性仅决定于的有效性仅决定于X、Y这两个属性集的值这两个属性集的值l只要在只要在R(U)的任何一个关系的任何一个关系r中,元组在中,元组在X和和Y上的值满上的值满足定义足定义6.l,则函数依赖,则函数依赖XY在任何属性集在任何属性集W(XY W U)上成立。上成立。中国人民大学数据库系统概论AnIntroductiontoDataba
61、seSystem*多值依赖(续)多值依赖(续)n(2)若函数依赖)若函数依赖XY在在R(U)上成立,则对于任何上成立,则对于任何Y Y均有均有XY 成立。多值依赖成立。多值依赖XY若在若在R(U)上成立,上成立,不能断言对于任何不能断言对于任何Y Y有有XY 成立。成立。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*多值依赖(续)多值依赖(续)n例如,关系例如,关系R(A,B,C,D),ABC成立,当然也有成立,当然也有AD成立。有成立。有R的一个关系实例,在此实例上的一个关系实例,在此实例上AB是不成立的。是不成立的。ABCDa1b1c1d1a1b1
62、c1d2a1b2c2d1a1b2c2d2表表6.6R的一个实例的一个实例中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.2规范化规范化v6.2.1函数依赖函数依赖v6.2.2码码v6.2.3范式范式v6.2.42NFv6.2.53NFv6.2.6BCNFv6.2.7多值依赖多值依赖v6.2.84NFv6.2.9规范化小结规范化小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*6.2.84NFv定义定义6.10关系模式关系模式R 1NF,如果对于,如果对于R的的每个非平凡多值依赖每个非平凡多值依赖XY(Y X),
63、),X都含有都含有码,则码,则R 4NF。v4NF就是限制关系模式的属性之间不允许有非平就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。凡且非函数依赖的多值依赖。4NF所允许的非平所允许的非平凡多值依赖实际上是函数依赖。凡多值依赖实际上是函数依赖。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*4NF(续)(续)v如果一个关系模式是如果一个关系模式是4NF,则必为则必为BCNF。v在在例例6.10的的WSC中,中,WS,WC,他们都他们都是非平凡多值依赖。而是非平凡多值依赖。而W不是码,关系模式不是码,关系模式WSC的码是的码是(W,S,
64、C),即,即All-key,因此,因此WSC4NF。v可以把可以把WSC分解成分解成WS(W,S),WC(W,C),WS4NF,WC4NF。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.2规范化规范化v6.2.1函数依赖函数依赖v6.2.2码码v6.2.3范式范式v6.2.42NFv6.2.53NFv6.2.6BCNFv6.2.7多值依赖多值依赖v6.2.84NFv6.2.9规范化小结规范化小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*6.2.9规范化小结规范化小结v在关系数据库中,对关系模式的基本要求是
65、满足在关系数据库中,对关系模式的基本要求是满足第一范式。第一范式。v规范化程度过低的关系不一定能够很好地描述现规范化程度过低的关系不一定能够很好地描述现实世界实世界n可能存在插入异常、删除异常、修改复杂、数据冗余可能存在插入异常、删除异常、修改复杂、数据冗余等问题等问题n解决方法就是对其进行规范化,转换成高级范式。解决方法就是对其进行规范化,转换成高级范式。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*规范化小结(续)规范化小结(续)v一个低一级范式的关系模式,通过模式分解可以一个低一级范式的关系模式,通过模式分解可以转换为若干个高一级范式的关系模式集
66、合,这种转换为若干个高一级范式的关系模式集合,这种过程就叫关系模式的规范化。过程就叫关系模式的规范化。v关系数据库的规范化理论是数据库逻辑设计的工关系数据库的规范化理论是数据库逻辑设计的工具。具。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*规范化小结(续)规范化小结(续)v规范化的基本思想规范化的基本思想n是逐步消除数据依赖中不合适的部分,使模式中的各关是逐步消除数据依赖中不合适的部分,使模式中的各关系模式达到某种程度的系模式达到某种程度的“分离分离”。n即采用即采用“一事一地一事一地”的模式设计原则的模式设计原则l让一个关系描述一个概念、一个实体或
67、者实体间的一种联让一个关系描述一个概念、一个实体或者实体间的一种联系。系。l若多于一个概念就把它若多于一个概念就把它“分离分离”出去。出去。n因此因此规范化实质上是概念的单一化。规范化实质上是概念的单一化。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*规范化小结(续)规范化小结(续)v关系模式规范化的基本步骤关系模式规范化的基本步骤v1NFv 消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖v消除决定因素消除决定因素2NFv非码的非平凡非码的非平凡消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖v函数依赖函数依赖3NFv 消除主
68、属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖vBCNFv 消除非平凡且非函数依赖的多值依赖消除非平凡且非函数依赖的多值依赖v4NF图图6.8规范化过程规范化过程中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*规范化小结(续)规范化小结(续)v不能说规范化程度越高的关系模式就越好。不能说规范化程度越高的关系模式就越好。n必须对现实世界的实际情况和用户应用需求作进一步必须对现实世界的实际情况和用户应用需求作进一步分析,确定一个合适的、能够反映现实世界的模式。分析,确定一个合适的、能够反映现实世界的模式。n上面的规范化步骤可以在其中任何一步终
69、止。上面的规范化步骤可以在其中任何一步终止。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem第六章第六章关系数据理论关系数据理论n6.1问题的提出问题的提出n6.2规范化规范化n6.3数据依赖的公理系统数据依赖的公理系统v*6.4模式的分解模式的分解v6.5小结小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*6.3数据依赖的公理系统数据依赖的公理系统v定义定义6.11对于满足一组对于满足一组函数依赖函数依赖F的关系模式的关系模式R,其任何一个关系,其任何一个关系r,若函数依赖,若函数依赖XY都成都成立(即立(即r
70、中任意两元组中任意两元组t、s,若,若tX=sX,则,则tY=sY),则称),则称F逻辑蕴涵逻辑蕴涵XY。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)vArmstrong公理系统公理系统n一套推理规则,是模式分解算法的理论基础一套推理规则,是模式分解算法的理论基础n用途用途l求给定关系模式的码求给定关系模式的码l从一组函数依赖求得蕴涵的函数依赖从一组函数依赖求得蕴涵的函数依赖中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统
71、(续)vArmstrong公理系统公理系统设设U为属性集总体,为属性集总体,F是是U上的一组函数依赖,上的一组函数依赖,于是有关系模式于是有关系模式R。对对R来说有以下的推理规则:来说有以下的推理规则:nA1自反律(自反律(reflexivityrule):若):若Y X U,则,则XY 为为F所蕴涵。所蕴涵。nA2增广律(增广律(augmentationrule):若):若XY为为F所蕴所蕴涵,且涵,且Z U,则,则XZYZ 为为F所蕴涵。所蕴涵。nA3传递律(传递律(transitivityrule):若):若XY及及YZ为为F所所蕴涵,则蕴涵,则XZ 为为F所蕴涵。所蕴涵。n注意:由自反
72、律所得到的函数依赖均是平凡的函数依赖,n自反律的使用并不依赖于F。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)v定理定理6.1Armstrong推理规则是正确的。推理规则是正确的。v证明证明nA1自反律自反律n设设Y X U。n对对R的任一关系的任一关系r中的任意两个元组中的任意两个元组t、s:n若若tX=sX,由于,由于Y X,有,有tY=sY,n所以所以XY成立,成立,n自反律得证。自反律得证。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统
73、(续)数据依赖的公理系统(续)nA2增广律增广律v设设XY为为F所蕴涵,且所蕴涵,且Z U。n对对R的任一关系的任一关系r中任意的两个元组中任意的两个元组t、s:n若若tXZ=sXZ,则有,则有tX=sX和和tZ=sZ;n由由XY,于是有,于是有tY=sY,n所以所以tYZ=sYZ,XZYZ为为F所蕴涵,所蕴涵,n增广律得证。增广律得证。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)nA3传递律传递律v设设XY及及YZ为为F所蕴涵。所蕴涵。n对对R的任一关系的任一关系r中的任意两个元组中的任意两个元组t、
74、s:n若若tX=sX,由于,由于XY,有,有tY=sY;n再由再由YZ,有,有tZ=sZ,n所以所以XZ为为F所蕴涵,所蕴涵,n传递律得证。传递律得证。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)v根据根据A1,A2,A3这三条推理规则可以得到下面这三条推理规则可以得到下面三条推理规则:三条推理规则:n合并规则(合并规则(unionrule):):由由XY,XZ,有,有XYZ。n伪传递规则(伪传递规则(pseudotransitivityrule):):n由由XY,WYZ,有,有XWZ。n分解规则(分解
75、规则(decompositionrule):):n由由XY及及Z Y,有,有XZ。n中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)v根据合并规则和分解规则,可得引理根据合并规则和分解规则,可得引理6.1v引理引理6.1XA1 A2Ak成立的充分必要条件是成立的充分必要条件是XAi成立(成立(i=1,2,k)。)。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)v定义定义6.12在关系模式在关系模式R中为中为F所逻辑蕴涵
76、的所逻辑蕴涵的函数依赖的全体叫作函数依赖的全体叫作F的闭包,记为的闭包,记为F+。v定义定义6.13设设F为属性集为属性集U上的一组函数依赖,上的一组函数依赖,X、Y U,XF+=A|XA能由能由F根据根据Armstrong公理导公理导出出,XF+称为属性集称为属性集X关于函数依赖集关于函数依赖集F的闭包。的闭包。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)v引理引理6.2设设F为属性集为属性集U上的一组函数依赖,上的一组函数依赖,X、Y U,XY能由能由F根据根据Armstrong公理导出的充分公理导
77、出的充分必要条件是必要条件是Y XF+。n引理引理6.2的用途的用途判定判定XY是否能由是否能由F根据根据Armstrong公理导出的问题,就公理导出的问题,就转化为求出转化为求出XF+,判定,判定Y是否为是否为XF+的子集的问题。的子集的问题。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)v求闭包的算法求闭包的算法v算法算法6.1求属性集求属性集X(X U)关于)关于U上的函数依赖上的函数依赖集集F的闭包的闭包XF+n输入:输入:X,Fn输出:输出:XF+n步骤:步骤:迭代迭代中国人民大学数据库系统概论
78、AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)令令X(0)=X,i=0求求B,这里,这里B=A|( V)( W)(VW F V X(i)A W)。X(i+1)=B X(i)。判断判断X(i+1)=X(i)。若若X(i+1)与与X(i)相等或相等或X(i)=U,则,则X(i)就是就是XF+,算法终止。算法终止。若否,则若否,则i=i+1,返回第,返回第步。步。对对X(i)中的每个元素,依次检查相应中的每个元素,依次检查相应的函数依赖的函数依赖,将依赖它的属性加入将依赖它的属性加入B中国人民大学数据库系统概论AnIntroductio
79、ntoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)例例6.11已知关系模式已知关系模式R,其中,其中U=A,B,C,D,E;F=ABC,BD,CE,ECB,ACB。求求(AB)F+。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)n解解:由算法:由算法6.1,设,设X(0)=AB。计算计算X(1):逐一的扫描:逐一的扫描F集合中各个函数依赖,找左部为集合中各个函数依赖,找左部为A、B或或AB的函数依赖。得到两个:的函数依赖。得到两个:ABC,BD。于。于是是X(1)=AB
80、CD=ABCD。因为因为X(0)X(1),所以再找出左部为,所以再找出左部为ABCD子集的那些函数子集的那些函数依赖,又得到依赖,又得到CE,ACB,于是,于是X(2)=X(1)BE=ABCDE。因为因为X(2)已等于全部属性集合,所以已等于全部属性集合,所以(AB)F+=ABCDE。n参见爱课程网数据库系统概论参见爱课程网数据库系统概论6.3节节动画动画求闭包求闭包中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)v有效性与完备性的含义有效性与完备性的含义n有效性:由有效性:由F出发根据出发根据Armstr
81、ong公理推导出来的每公理推导出来的每一个函数依赖一定在一个函数依赖一定在F+中中n完备性:完备性:F+中的每一个函数依赖,必定可以由中的每一个函数依赖,必定可以由F出发根出发根据据Armstrong公理推导出来公理推导出来中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*v定理定理6.2Armstrong公理系统是有效的、完备的。公理系统是有效的、完备的。v证明:证明:1.有效性有效性l有效性实际上是有效性实际上是“正确性正确性”l可由定理可由定理6.1得证得证数据依赖的公理系统(续)数据依赖的公理系统(续)中国人民大学数据库系统概论AnIntroduc
82、tiontoDatabaseSystem*2.完备性完备性l只需证明逆否命题:若函数依赖只需证明逆否命题:若函数依赖XY不能由不能由F从从Armstrong公理导出,那么它必然不为公理导出,那么它必然不为F所蕴所蕴涵涵l分三步证明:分三步证明:(1)若若VW成立,且成立,且V XF+,则,则W XF+证:因为证:因为 V XF+,所以有,所以有XV成立;成立;因为因为XV,VW,于是,于是XW成立;成立;所以所以W XF+。数据依赖的公理系统(续)数据依赖的公理系统(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*(2)构造一张二维表)构造一张二维表
83、r,它由下列两个元组构成,可以证明,它由下列两个元组构成,可以证明r 必必是是R的一个关系,即的一个关系,即F中的全部函数依赖在中的全部函数依赖在r上成立。上成立。XF+U-XF+11.100.011.111.1若若r 不是不是R的关系,则必由于的关系,则必由于F中有某一个函数依赖中有某一个函数依赖VW在在r上上不成立所致。由不成立所致。由r 的构成可知,的构成可知,V必定是必定是XF+的子集,而的子集,而W不是不是XF+的子集,可是由第(的子集,可是由第(1)步,)步,WXF+,矛盾。,矛盾。所以所以r必是必是R的一个关系。的一个关系。数据依赖的公理系统(续)数据依赖的公理系统(续)中国人民
84、大学数据库系统概论AnIntroductiontoDatabaseSystem*(3)若)若XY不能由不能由F从从Armstrong公理导出,则公理导出,则Y不是不是XF+的子集。(引理的子集。(引理6.2)因此必有因此必有Y的子集的子集Y满足满足Y U-XF+,则则XY在在r 中不成立,中不成立,即即XY必不为必不为R蕴涵。蕴涵。数据依赖的公理系统(续)数据依赖的公理系统(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*vArmstrong公理的完备性及有效性说明公理的完备性及有效性说明:n“导出导出”与与“蕴涵蕴涵”是两个完全等价的概念是两个完全
85、等价的概念nF+:为:为F所逻辑蕴涵的函数依赖的全体(定义所逻辑蕴涵的函数依赖的全体(定义6.12)nF+:可以说成由:可以说成由F出发借助出发借助Armstrong公理导出的函公理导出的函数依赖的集合数依赖的集合数据依赖的公理系统(续)数据依赖的公理系统(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*v定义定义6.14如果如果G+=F+,就说函数依赖集,就说函数依赖集F覆盖覆盖G(F是是G的覆盖,或的覆盖,或G是是F的覆盖),或的覆盖),或F与与G等价。等价。两个函数依赖集等价是指它们的闭包等价两个函数依赖集等价是指它们的闭包等价数据依赖的公理系
86、统(续)数据依赖的公理系统(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystemv函数依赖集等价的充要条件函数依赖集等价的充要条件v引理引理6.3F+=G+的充分必要条件是的充分必要条件是F G+和和G F+。n证证:必要性显然,只证充分性。必要性显然,只证充分性。(1)若)若F G+,则,则XF+ XG+。(2)任取)任取XY F+则有则有Y XF+ XG+。所以所以XY (G +)+=G+。即。即F+ G+。(3)同理可证)同理可证G+ F+,所以,所以F+=G+。引理引理6.3给出了判断两个函数依赖集等价的给出了判断两个函数依赖集等价的可行算法可行算
87、法如何判定如何判定FG+?只需逐一对只需逐一对F中的函数依赖中的函数依赖XY考察考察 Y是否是否属于属于XG+数据依赖的公理系统(续)数据依赖的公理系统(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*v定义定义6.15如果函数依赖集如果函数依赖集F满足下列条件,则称满足下列条件,则称F为一个极小函数依赖集,亦称为最小依赖集或最为一个极小函数依赖集,亦称为最小依赖集或最小覆盖。小覆盖。(1)F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。(2)F中不存在这样的函数依赖中不存在这样的函数依赖XA, 使得使得F与与 F-XA等价
88、。等价。(3)F中不存在这样的函数依赖中不存在这样的函数依赖XA,X有真有真子集子集Z使得使得F-XA ZA与与F等价。等价。即即F中的函数依赖均中的函数依赖均不能由不能由F中其他函数中其他函数依赖导出依赖导出F中各函数依赖左部均中各函数依赖左部均为最小属性集(不存为最小属性集(不存在冗余属性)在冗余属性)数据依赖的公理系统(续)数据依赖的公理系统(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*v例例6.12考察考察6.1节中的关系模式节中的关系模式S,其中:,其中:U=Sno,Sdept,Mname,Cno,Grade,F=SnoSdept,Sd
89、eptMname,(Sno,Cno)GradeF是最小覆盖是最小覆盖F =SnoSdept,SnoMname,SdeptMname,(Sno,Cno)Grade,(Sno,Sdept)SdeptF 不是最小覆盖不是最小覆盖n因为:因为:F -SnoMname与与F 等价等价nF -(Sno,Sdept)Sdept也与也与F 等价等价v参见爱课程网数据库系统概论参见爱课程网数据库系统概论6.2节节动画动画最小覆盖集难点解最小覆盖集难点解析析数据依赖的公理系统(续)数据依赖的公理系统(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续
90、)数据依赖的公理系统(续)v定理定理6.3每一个函数依赖集每一个函数依赖集F均等价于一个极小函均等价于一个极小函数依赖集数依赖集Fm。此。此Fm称为称为F的最小依赖集。的最小依赖集。n证:构造性证明,分三步对证:构造性证明,分三步对F进行进行“极小化处理极小化处理”,找,找出出F的一个最小依赖集。的一个最小依赖集。(1)逐一检查)逐一检查F中各函数依赖中各函数依赖FDi:XY,若若Y=A1A2 Ak,k2,则用则用XAj|j=1,2,k来取代来取代XY。引理引理6.1保证了保证了F变换前后的等价性。变换前后的等价性。中国人民大学数据库系统概论AnIntroductiontoDatabaseSy
91、stem*数据依赖的公理系统(续)数据依赖的公理系统(续)(2)逐一检查)逐一检查F中各函数依赖中各函数依赖FDi:XA,令令G=F-XA,若若A XG+,则从,则从F中去掉此函数依赖。中去掉此函数依赖。由于由于F与与G等价的充要条件是等价的充要条件是A XG+因此因此F变换前后是等价的。变换前后是等价的。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)(3)逐一取出)逐一取出F中各函数依赖中各函数依赖FDi:XA,设设X=B1B2Bm,m2,逐一考查逐一考查Bi (i=1,2,m),),若若A (X-Bi
92、)F+,则以,则以X-Bi取代取代X。由于由于F与与F-XA ZA等价的充要条件是等价的充要条件是A ZF+,其中,其中Z=X-Bi ,因此因此F变换前后是等价的。变换前后是等价的。最后剩下的最后剩下的F就一定是极小依赖集。就一定是极小依赖集。因为对因为对F的的每一次每一次“改造改造”都都保证了改造前后的两个函数保证了改造前后的两个函数依赖集等价,因此剩下的依赖集等价,因此剩下的F与原来的与原来的F等价。等价。证毕证毕中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)v定理定理6.3的证明过程的证明过程n是求
93、是求F极小依赖集的过程极小依赖集的过程n也是检验也是检验F是否为极小依赖集的一个算法是否为极小依赖集的一个算法若改造后的若改造后的F与原来的与原来的F相同,说明相同,说明F就是一个最小依赖集就是一个最小依赖集中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)v例例6.13F=AB,BA,BC,AC,CAF的最小依赖集:的最小依赖集:Fm1=AB,BC,CA中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)vF的最小依赖集的最
94、小依赖集Fm不一定是唯一的,它与对各函不一定是唯一的,它与对各函数依赖数依赖FDi及及XA中中X各属性的处置顺序有关。各属性的处置顺序有关。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*数据依赖的公理系统(续)数据依赖的公理系统(续)例例6.13(续)(续)F=AB,BA,BC,AC,CAFm1、Fm2都是都是F的最小依赖集:的最小依赖集:Fm1=AB,BC,CAFm2=AB,BA,AC,CA中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem*v在在R中可以用与中可以用与F等价的依赖集等价的依赖集G来取代来取代Fn原
95、因:两个关系模式原因:两个关系模式R1,R2,如果,如果F与与G等价,那么等价,那么R1的关系一定是的关系一定是R2的关系。反过来,的关系。反过来,R2的的关系也一定是关系也一定是R1的关系。的关系。数据依赖的公理系统(续)数据依赖的公理系统(续)中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem第六章第六章关系数据理论关系数据理论n6.1问题的提出问题的提出n6.2规范化规范化v6.3数据依赖的公理系统数据依赖的公理系统n*6.4模式的分解模式的分解n6.5小结小结中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem6.5
96、小结小结v关系模式的规范化,其基本思想:关系模式的规范化,其基本思想:中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem小结(续)小结(续)v若要求分解具有无损连接性,那么模式分解一定若要求分解具有无损连接性,那么模式分解一定能够达到能够达到4NF。v若要求分解保持函数依赖,那么模式分解一定能若要求分解保持函数依赖,那么模式分解一定能够达到够达到3NF,但不一定能够达到,但不一定能够达到BCNF。v若分解既具有无损连接性,又保持函数依赖,则若分解既具有无损连接性,又保持函数依赖,则模式分解一定能够达到模式分解一定能够达到3NF,但不一定能够达到,但不一定能够达到BCNF。中国人民大学数据库系统概论AnIntroductiontoDatabaseSystem小结(续)小结(续)v规范化理论为数据库设计提供理论的指南和工具规范化理论为数据库设计提供理论的指南和工具n仅仅是指南和工具仅仅是指南和工具v并不是规范化程度越高,模式就越好并不是规范化程度越高,模式就越好n必必须须结结合合应应用用环环境境和和现现实实世世界界的的具具体体情情况况合合理理地地选选择择数据库模式数据库模式