1滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精目录范式5.4问题提出5.1函数依赖定义5.2函数依赖理论5.3数据库模式求精模式分解算法5.65.52滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精范式概述基于函数依赖理论,关系模式可分成第一范式(1NF)第二范式(2NF)第三范式(3NF)Boyce-Codd范式(BCNF)这几种范式的要求一个比一个严格,它们之间的联系为BCNF3NF2NF1NF。即满足BCNF范式的关系一定满足3NF范式,满足3NF范式的关系一定满足2NF范式,满足2NF范式的关系一定满足1NF范式。3滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精第一范式(1NF)——码定义5.16如果一关系模式r(R)的每个属性对应的域值都是不可分的(即原子的),则称r(R)属于第一范式,记为r(R)1NF。第一范式的目标是:将基本数据划分成称为实体集或表的逻辑单元,当设计好每个实体后,需要为其指定主码。studentNostudentNamesexbirthdayageaddressclassNoprovincecitystreet图5-10非规范化的关系模式studentNostudentNamesexbirthdayageprovincecitystreetclassNo图5-111NF规范化后的关系模式4滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精第二范式(2NF)——全部码定义5.17设有一关系模式r(R),R。若包含在r(R)的某个候选码中(某个候选码中),则称为主属性,否则为非主属性。在SCE关系中,属性集{studentNo,courseNo}是SCE的唯一候选码。因此,属性studentNo和courseNo为主属性,其余属性为非主属性。定义5.18如果一个关系模式r(R)1NF,且所有非主属性都完全函数依赖于r(R)的候选码,则称r(R)属于第二范式,记为r(R)2NF。由于SCE中存在依赖关系studentNostudentName和courseNocourseName,即非主属性studentName和courseName(子集studentNostudentName)部分依赖于SCE的候选码,故SCE2NF。5滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精第二范式(2NF)——全部码第二范式的目标是:将只部分依赖于主码(即依赖于主码的部分属性)的数据移到其他表中。也就是说,在满足第一范式的实体中,如果有复合主码(即多个属性共同构成主码),那么所有非主属性必须依赖于全部的主码,而不能只是依赖于部分的主码属性。违背了2NF的模式,即存在非主属性对候选码的部分依赖,则可能导致例5.1所述的数据冗余及异常问题。6滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精第二范式(2NF)——全部码对于非2NF范式的关系模式,可通过分解进行规范化,以消除部分依赖。如将关系模式SCE分解为关系模式S、C和E(三个表)。这样在每个关系模式中,所有非主属性对候选码都是完全函数依赖,因此都属于2NF范式。2NF范式虽然消除了由于非主属性对主码的部分依赖所引起的冗余及各种异常,但并没有排除传递依赖。因此,还需要对其进一步规范化。7滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精Boyce-Codd范式(BCNF)RayBoyce(SQL的创建者之一)以及EdgarCodd定义5.19给定关系模式r(R)及函数依赖集F,若F+中的所有函数依赖(R,R)至少满足下列条件之一:是平凡函数依赖(即);是r(R)的一个超码(即+包含R的全部属性)。即起决定作用的属性必须是超码!则称r(R)属于Boyce-Codd范式,记为r(R)BCNF。换句话说,在关系模式r(R)中,如果F+中的每一个非平凡函数依赖的决定属性集都包含候选码,则r(R)BCNF。特别说明:为确定r(R)是否满足BCNF范式,必须考虑F+而不是F中的每个依赖。8滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精Boyce-Codd范式(BCNF)从函数依赖角度可得出,一个满足BCNF的关系模式必然满足下列结论:所有非主属性都完全函数依赖于每个候选码;所有主属性都完全函数依赖于每个不包含它的候选码;没有任何属性完全函数依赖于非候选码的任何一组属性。BCNF范式排除了:任何属性(包括主属性和非主属性)对候选码的部分依赖和传递依赖;主属性之间的传递依赖。9滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精Boyce-Codd范式判断举例[例5.13]r(R)=r(A,B,C),F={A→B,B→C}。r(R)的候选码为A,r(R)BCNF,因为函数依赖B→C中的决定属性B不是超码。[例5.14]r(R)=r(A,B,C),F={AB→C,C→A}。r(R)的候选码为AB或BC,r(R)BCNF,因为C→A的决定属性C不是超码。[例5.15]r(R)=r(A,B,C),F={AB→C,BC→A}。r(R)的候选码为AB或BC,r(R)BCNF,因为两个函数依赖中的决定属性AB或BC都是r(R)的候选码。10滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精Boyce-Codd范式存在问题对于非BCNF范式的关系模式,可通过分解进行规范化,以消除部分依赖和传递依赖。将例5.13中的r(R)分解为r1(R1)=r1(A,B)、r2(R2)=r2(B,C)或r1(R1)=r1(A,B)、r2(R2)=r2(A,C)显然,这两种分解得到的r1(R1)和r2(R2)都属于BCNF范式。但是,后一种分解不是保持依赖分解(例5.12已分析)。因此,满足BCNF范式要求的模式分解,可能不是保持依赖分解。11滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精第三范式(3NF)——仅仅是码定义5.20给定关系模式r(R)及函数依赖集F,若对F+中的所有函数依赖→(R,R)至少满足下列条件之一:→是平凡函数依赖(即);是r(R)的一个超码(即+包含R的全部属性);-中的每个属性是r(R)的候选码的一部分。则称r(R)属于第三范式,记为r(R)3NF。3NF与BCNF范式的区别在于第3个条件。放松之处:允许存在主属性对候选码的传递依赖和部分依赖。注意:3NF的第3个条件不要求-中的每个属性必须包含在r(R)的一个候选码中,即中的每个属性可以包含在r(R)的不同候选码中。12滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精第三范式(3NF)——仅仅是码第三范式的目标是:去掉表中不依赖于主码的数据。也就是说,在满足第二范式的实体中,非主属性不能依赖于另一个非主属性,即所有的非主属性应该直接依赖于全部的主属性(即必须完全依赖,这是2NF的要求),并且彼此之间无相互依赖关系(即不能存在部分依赖,这是3NF的要求)。换一句话说,非主属性不能包括它们自己的属性,如果属性不包括属性,则它们就是真正的实体。13滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精3NF范式判断举例[例5.16]r(R)=r(A,B,C),F={A→B,B→C}。r(R)的候选码为A,r(R)3NF,且r(R)BCNF。[例5.17]r(R)=r(A,B,C),F={AB→C,C→A}。r(R)的候选码为AB或BC,r(R)3NF,但r(R)BCNF。[例5.18]r(R)=r(A,B,C),F={AB→C,BC→A}。r(R)的候选码为AB或BC,r(R)3NF,且r(R)BCNF属于BCNF的关系模式必定属于3NF,但属于3NF不一定属于BCNF!14滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精3NF与BCNF比较BCNF比3NF严格。BCNF要求所有的非平凡函数依赖中的是超码,而3NF则放松了该约束,允许不是超码。若关系模式属于BCNF范式就一定属于3NF范式。反之,则不一定成立。3NF存在数据冗余和异常问题,而BCNF是基于函数依赖理论能够达到的最好关系模式。BCNF范式分解是无损分解,但不一定是保持依赖分解;而3NF分解既是无损分解,又是保持依赖分解。15滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精目录范式5.4问题提出5.1函数依赖定义5.2函数依赖理论5.3数据库模式求精模式分解算法5.65.516滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精模式分解算法数据库设计目标为(基于函数依赖):BCNF无损连接保持依赖但有时不能同时达到这3个目标,就需根据实际应用需求在BCNF和3NF中做出选择。主要模式分解算法BCNF分解3NF分解17滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精BCNF分解方法设即r(R)为关系模式,r(R)BCNF,若非平凡函数依赖(即)违反了BCNF的函数依赖,则将r(R)分解为r1(R1)和r2(R2),其中:R1=F1={}——如果=,则是候选码R2=R-(-)——如果=,则R2=R-若r2(R2)不属于BCNF,则继续分解下去,直到所有结果模式都为BCNF。R-R2R1图5-14不满足BCNF的关系分解18滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精BCNF分解举例[例5.19]r(R)=r(A,B,C),F={AB→C,C→A},判断r(R)是否属于BCNF范式?如果不是,则进行BCNF分解。例5.14已经证明r(R)BCNF(因为候选码为AB或BC,所以C→A的决定属性C不是超码)。按上述算法,r(R)可分解为r1(R1)=r1(A,C),F1={C→A}——该关系r1(R1)中,C是候选码r2(R2)=r2(B,C),F2={}——该关系r2(R2)中,BC是候选码分解后的r1(R1)和r2(R2)都属于BCNF,不需再做分解。注意:F中的函数依赖关系AB→C,在分解后丢失了!19滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精BCNF分解算法BCNF分解算法的形式化描述如下:result:={R};done:=false;计算F+;while(notdone)doifri(Ri)BCNFifF+((Ri)(RiF+=))result:=(result-Ri)(Ri-)(,)elsedone:=true图5-15BCNF分解算法是Ri上的一个非平凡函数依赖不是Ri的超码第一次循环时,ri(Ri)就是r(R)如果≠,则该属性集为Ri-(-)20滁州学院计算机科学与技术系数据库系统原理与设计第5章关系数据理论与模式求精BCNF分解举例例1:r(R)=r(A,B,C,D,G,H),F={A→BC,DG→H,D→A},r(R)是否属于BCNF范式?如果不是,则进行BCNF分解。r(R)BCNF(因为候选码为DG,所以A→BC的决定属性A不是超码)。按上述算法,r(R)可分解为r1(R1)=r1(A,B,C),F1={A→BC}——A是候选码r2(R2)=r2(A,D,G,H),F2={DG→H,D→A}—DG是候选码r2(R