数据库原理与应用CHAP04

第4章关系模式的规范化设计理论第4章关系模式的规范化设计理论4.2关系模式的函数依赖4.3关系模式的规范化4.4关系模式的分解特性4.1问题的提出4.1问题的提出4.1.1关系模式可能存在的异常关系可能存在以下几个异常问题：p116例4.1⑴插入异常。⑵删除异常。⑶冗余过多。4.1.2异常原因分析-p118关系模式出现异常问题的原因：在关系模式的结构中，属性之间存在过多的“数据依赖”。4.1.3异常问题的解决p118例4.2消除关系模式出现的异常问题的方法：对关系模式进行分解。4.2.1再论关系与关系模式关系模型的外延——关系，基本表或当前值。关系是元组的集合，由于用户经常对关系进行插入，删除和修改等操作，所以关系是与时间变化而不断变化的。关系模型内涵——关系模式，是对关系中数据的定义和数据完整性约束的定义等，其中对数据的定义包括对关系的属性、域的定义和说明等，而关键是关系模式的定义和说明，且这些定义和说明是相对稳定的。在以后的讨论中，一个关系模式R(U)对应的具体关系(取值实例)通常用小写字母r来表示。4.2.2函数依赖的一般概念(1)定义4.1设R(U)是属性集U={A1,A2,…,An}上的关系模式，X和Y是U的子集。若对R(U)的任一具体关系r中的任意两个元组t1和t2，只要t1[X]=t2[X]就有t1[Y]=t2[Y]，则称“X函数确定Y”或“Y函数依赖于X”(FounctionalDependence)，记作XY。P120例4.3几个常用的术语和记号：⑴若XY，则称X为这个函数依赖的决定(Determinant)因素，简称X是决定因素。⑵若XY且YX，则称X与Y相互函数依赖，记作XY。⑶若Y不函数依赖于X，则记作XY。⑷若XY，但YX，则称XY是平凡函数依赖。⑸若XY，但YX，则称XY是非平凡函数依赖。定义4.2设R(U)是属性集U={A1,A2,…,An}上的关系模式。X和Y是U的子集。⑴如果XY，且对于X的任何一个真子集X，都有XY，则称Y对X完全函数依赖(FullFounctionalDependence)或者X完全决定Y，记作：⑵如果XY，但Y不是完全函数依赖于X，则称Y对X部分函数依赖(PartialFounctionalDependence)，记作：。定义4.3对于关系模式R(U)，设X、Y和Z都是U的子集。如果XY，YZ，且YX，YX，ZY，则称Z对X传递函数依赖(TransitiveFounctionalDependence)，记作:。例4.4YXf4.2.2函数依赖的一般概念(2)YXpYXt定义4.4对关系模式R(U)，设KU。如果，则称K为R(U)的候选键或候选关键字(CandidateKey)。通常在R(U)的所有候选键中选定一个作为主键(PrimaryKey)。主键也称为主码或主关键字。例4.5定义4.5对关系模式R(U)，包含在任何一个候选键中的属性称为主属性(PrimaryAttribute)，不包含在任何候选键中的属性称为非主属性(NonprimaryAttribute)或非码属性(Non-keyAttribtute)。定义4.6对关系模式R(U)，设XU。若X不是R(U)的主键，但X是另一个关系模式的主键，则称X是R(U)的外键或外部关键字(Foreignkey)。例4.74.2.3候选键与主键UKf1、函数依赖的逻辑蕴涵定义4.7对于满足函数依赖集F的关系模式R(U,F)的任意一个具体关系r，若函数依赖XY都成立(即对于r中的任意两个元组t，s，若t[X]=s[X]，则有t[Y]=s[Y])，则称F逻辑蕴涵XY，记为FXY。定义4.8被函数依赖集F逻辑蕴涵的函数依赖所构成的集合，称为F的闭包(Closure)，记作F+。即：F+={XY|FXY}。通常，FF+。若F=F+，称F是函数依赖完备集。2、Armstrong公理系统Armstrong公理系统设有关系模式R(U,F)，F是只涉及到U中属性的函数依赖集。若X，Y，Z，W均是U的子集，则有以下推理规则：4.2.4函数依赖的推理规则(1)⑴自反律(ReflexivityRule)：如果YXU，则XY成立，即FXY。⑵增广律(AugmentationRule)：如果XY成立,则XZYZ成立(其中XZ是XZ的简单记法，其它类同)，即若FXY，则FXZYZ。⑶传递律(Transitivityrule)：如果XY，YZ成立，则XZ成立，即若FXY，FYZ，则F若FXZ。定理4.1Armstrong公理系统中的推理规则⑴，⑵，⑶是正确的，即若XY由Armstrong公理导出，则XY属于F+。定理4.2函数依赖的如下三个推理规则是正确的。⑴合并律(UnionRule)：如果XY和XZ成立，那么XYZ成立，即若FXY，FXZ，则FXYZ。⑵伪传递律(PseudotransivityRule)：如果XY和WYZ成立，那么WXZ成立，即若FXY，FWYZ，则FWXZ。4.2.4函数依赖的推理规则(2)⑶分解律(DecompositionRule)：如果XY和ZY成立，那么XZ成立，即若FXY，ZY，则FXZ。推论4.1对关系模式R(U)，设XU，{A1,A2,…,Am}U，则X{A1,A2,…,Am}成立的充分必要条件是XAi(i=1,2,…,m)成立。定义4.9设F是属性集合U上的一个函数依赖集，XU，称为属性集X关于F的闭包。例4.8定理4.3设F是属性集U上的函数依赖集，X，Y是U的子集，则XY能由F根据Armstrong公理导出的充分必要条件是。}ArmstrongFAXU,A|A{XF公理导出根据能由4.2.4函数依赖的推理规则(3)XY3、函数依赖推理规则的完备性*定理4.4Armstrong公理系统，即函数依赖推理规则系统(自反律、增广律和传递律)是完备的。从Armstong公理系统的完备性可以得到两个重要结论：⑴对属性集X+中的每个属性A，都有XA被F逻辑蕴涵，即X+是所有由F逻辑蕴含XA的属性A的集合。⑵F+是由F根据Armstrong公理导出的函数依赖的集合。函数依赖集F的闭包的一个计算公式：F+={XY|XY由F根据Armstrong公理导出}4.2.4函数依赖的推理规则(4)4、闭包的计算一个计算X+的算法。算法4.1求属性集XU关于函数依赖集F的闭包X+。输入：有限的属性集合U、它上面的函数依赖集合F和U的一个子集X。输出：X关于F的闭包X+。计算方法和计算步骤：⑴设置初始值：令X(0)＝，X(1)＝X，F=；⑵如果X(0)X(1)，令X(0)＝X(1)，否则转⑷；⑶构造函数依赖集F={YZ|(YZ)F且YX(1)}，令F=FF,对F中的每一个函数依赖YZ，令X(1)=X(1)Z，转⑵⑷输出X(1)，它就是X+。例4.104.2.4函数依赖的推理规则(5)5函数依赖集的等价和覆盖*定义4.10对关系模式R(U)上的两个函数依赖集F和G，如果满足F+＝G+，则称F和G是等价的。如果F和G是等价的，则称F覆盖G(同时G也覆盖F)。定理4.5F+＝G+充分必要条件是FG+,GF+。定理4.6每个函数依赖集F都可以被一个右部只有单属性的函数依赖集G所覆盖。定义4.11如果函数依赖集合F满足：⑴F中每一个函数依赖的右部都是单属性，即全是XA的形式，其中XU，AU；⑵对F中的任一函数依赖XA，有F{XA}与F不等价；⑶对F中的任一函数依赖XA，若ZX，则(F{XA}){ZA}与F不等价。则称F为最小函数依赖集，记为Fmin。如果函数依赖集F和G等价，并且G是最小函数依赖集，那么称G是F的一个最小覆盖。4.2.4函数依赖的推理规则(6)定理4.7每个函数依赖集F都有最小覆盖。4.2.4函数依赖的推理规则(7)4.3.1范式及其类型1、关系模式主要有六个范式级别：第一范式(简称1NF)，第二范式(2NF)，第三范式(3NF)，BC范式(BCNF)，第四范式(4NF)和第五范式(5NF)。各范式之间的关系为1NF2NF3NFBCNF4NF5NF。2、关系模式的规范化：将一个低级别范式的关系模式，通过模式分解转换为若干个高一级范式的关系模式的过程。定义4.12如果一个关系模式R(U)的所有属性都是不可再分的基本数据项，则称R(U)为第一范式，即R(U)1NF。第一范式通常存在数据冗余过多、删除异常和插入异常等问题。例4.124.3.2第一范式(1NF)4.3.3第二范式(2NF)定义4.13若R(U)1NF，且每一个非主属性完全函数依赖于某个候选键，称R(U)为第二范式，即R(U)2NF。例4.134.3.4第三范式(3NF)定义4.14设关系模式R(U)2NF，且每一个非主属性不传递函数依赖于R(U)的候选键，则称R(U)为第三范式，即R(U)3NF。例4.144.3.5BC范式(BCNF)(1)定义4.15若关系模式R(U)1NF，对于R(U)的任意一个函数依赖XY，若YX，则X必含有候选键，那么称R(U)为BC范式，即R(U)BCNF。以下是BC范式的一个等价定义。定义4.15’若关系模式R(U)1NF，且R(U)的每个属性都不传递依赖于R的候选键，则称R(U)为BC范式，即R(U)BCNF。若关系模式R(U)BCNF，则下结论成立。⑴R(U)的所有非主属性都完全函数依赖于每一个候选键，因此R(U)2NF。⑵R(U)的所有主属性都完全函数依赖于不包含它的候选键。⑶R(U)中没有属性完全函数依赖于任何一组非候选键属性。4.3.5BC范式(BCNF)(2)定理4.8若R(U)BCNF，则R(U)3NF。定理4.9如果R(U)3NF且R(U)有唯一候选键X，且不存在使的平凡函数依赖XY，则必有R(U)BCNF。例4.15-16BCNF是在函数依赖条件下对模式分解所能达到的最高分离程度。4.3.5BC范式(BCNF)(3)X’X例4.17定义4.16设R(U)是属性集U上的一个关系模式，X，Y，Z是U的子集，并且Z=UXY。若对于R(U)的任一具体关系r，r在属性(X，Z)上的每一个值，就有属性Y上的一组值与之对应，且这组值仅仅决定于X上的值而与Z上的值无关，则称Y多值依赖于X，记作XY。例4.184.3.6多值依赖(1)2、多值依赖的性质*⑴互补律：若XY，则XZ，其中Z＝UXY。多值依赖的互补性也称为对称性。⑵函数依赖导出多值依赖：若XY，则XY。⑶传递律：若XY且YZ，则X(ZY)。⑷增广律：若XY，且VW，则WXVY。⑸自反律：若YX，则XY。⑹多值依赖导出函数依赖：若XY，ZY，YW=，WZ，则XZ。⑺合并律：若XY，YZ，则XYZ。⑻分解律：若XY，XZ，则X(YZ)，X(ZY)。4.3.6多值依赖(2)定义4.17设关系模式R(U)1NF，若对于R(U)的每一个非平凡的多值依赖XY(YX)，X都含有候选键，则称R(U)为第四范式，即R(U)4NF。定理4.10若R(U)4NF，则R(U)BCNF。4.3.7第四范式(4NF)4.3.8关系模式规范化步骤例4.201、关系模式的分解：设有关系模式R(U)和R1(U1),R2(U2),…,Rk(Uk)，其中U={A1,A2,…,An}，UiU(i=1,2,…,k)且U＝U1U2…Uk。令={R1(U1),R2(U2),…,Rk(Uk)}，则称为关系模式R(U)的一个分解。例4.212、关系模式分解的标准：⑴分解具有无损连接性；{可能不保持函数依赖，丢失候选键，即与分解前不等价}；⑵分解保持函数依赖；{可能不具无损连接性，无法恢复以前的