数据库原理与应用CHAP04.pptVIP

第 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，只要t1X=t2X就有t1Y=t2Y，则称“X函数确定Y”或“Y函数依赖于X”(Founctional Dependence)，记作XY。 P120 例4.3 几个常用的术语和记号： 若XY，则称X为这个函数依赖的决定(Determinant)因素，简称X是决定因素。 若XY且YX，则称X与Y相互函数依赖，记作XY。 若Y不函数依赖于X，则记作 XY 。 若XY，但Y X，则称XY是平凡函数依赖。 若XY，但Y X ，则称XY是非平凡函数依赖。,定义4.2 设R(U)是属性集U=A1, A2, , An上的关系模式。X和Y是U的子集。 如果XY，且对于 X的任何一个真子集X，都有XY ，则称Y对X完全函数依赖(Full Founctional Dependence)或者X完全决定Y，记作： 如果XY，但Y不是完全函数依赖于X，则称Y对X部分函数依赖(Partial Founctional Dependence)，记作： 。 定义4.3 对于关系模式R(U)，设X、Y和Z都是U的子集。如果XY，YZ，且Y X，YX，ZY，则称Z对X传递函数依赖(Transitive Founctional Dependence)，记作: 。例4.4,4.2.2函数依赖的一般概念(2),定义4.4 对关系模式R(U)，设KU。如果 ，则称K为R(U)的候选键或候选关键字(Candidate Key)。通常在R(U)的所有候选键中选定一个作为主键(Primary Key)。主键也称为主码或主关键字。例4.5 定义4.5对关系模式R(U)，包含在任何一个候选键中的属性称为主属性(Primary Attribute)，不包含在任何候选键中的属性称为非主属性(Nonprimary Attribute)或非码属性(Non-key Attribtute)。 定义4.6 对关系模式R(U)，设XU。若X不是R(U)的主键，但X是另一个关系模式的主键，则称X是R(U)的外键或外部关键字(Foreign key)。 例4.7,4.2.3 候选键与主键,1、函数依赖的逻辑蕴涵 定义4.7 对于满足函数依赖集F的关系模式R(U,F)的任意一个具体关系r，若函数依赖XY都成立(即对于r中的任意两个元组t，s，若tX=sX，则有tY=sY)，则称F逻辑蕴涵XY，记为FXY。 定义4.8 被函数依赖集F逻辑蕴涵的函数依赖所构成的集合，称为F的闭包(Closure)，记作F+。即： F+=XY | FXY。 通常，FF+。若F=F+，称F是函数依赖完备集。 2、Armstrong公理系统 Armstrong公理系统 设有关系模式R(U, F)，F是只涉及到U中属性的函数依赖集。若X，Y，Z，W均是U的子集，则有以下推理规则：,4.2.4 函数依赖的推理规则(1), 自反律 (Reflexivity Rule)：如果YX U，则XY成立，即FXY。 增广律(Augmentation Rule)：如果XY成立, 则XZYZ 成立(其中XZ是XZ的简单记法，其它类同)，即若FXY，则FXZYZ。 传递律(Transitivity rule)：如果XY，YZ成立，则X Z成立，即若FXY，FYZ，则F若F XZ。 定理4.1 Armstrong公理系统中的推理规则，是正确的，即若XY由Armstrong公理导出，则XY属于F+。 定理4.2 函数依赖的如下三个推理规则是正确的。 合并律(Union Rule)：如果XY和XZ成立，那么XYZ成立，即若FXY，FXZ，则F XYZ。 伪传递律(Pseudotransivity Rule)：如果XY和WYZ成立，那么WXZ成立，即若FXY，FWYZ，则FWXZ。,4.2.4 函数依赖的推理规则(2), 分解律(Decomposition Rule)：如果XY和ZY成立，那么XZ成立，即若FXY，ZY，则F XZ。 推论4.1 对关系模式R(U)，设XU，A1, A2 , AmU，则XA1, A2 , Am成立的充分必要条件是XAi (i=1,2,m)成立。 定义4.9 设F是属性集合U上的一个函数依赖集，XU，称 为属性集X关于F的闭包。例4.8 定理4.3 设F是属性集U上的函数依赖集，X，Y是U的子集，则XY能由F根据Armstrong公理导出的充分必要条件是 。,4.2.4 函数依赖的推理规则(3),3、函数依赖推理规则的完备性* 定理4.4 Armstrong公理系统，即函数依赖推理规则系统(自反律、增广律和传递律)是完备的。 从Armstong公理系统的完备性可以得到两个重要结论： 对属性集X+中的每个属性A，都有XA被F逻辑蕴涵，即X+是所有由F逻辑蕴含XA的属性A的集合。 F+是由F根据Armstrong公理导出的函数依赖的集合。 函数依赖集F的闭包的一个计算公式： F+=XY | XY由F根据Armstrong公理导出,4.2.4 函数依赖的推理规则(4),4、闭包的计算 一个计算X+的算法。 算法4.1 求属性集XU关于函数依赖集F的闭包X+。 输入：有限的属性集合U、它上面的函数依赖集合F和U的一个子集X。 输出：X关于F的闭包X+。 计算方法和计算步骤： 设置初始值：令X(0)，X(1)X，F=； 如果X(0)X(1)，令X(0)X(1)，否则转； 构造函数依赖集F=YZ | (YZ)F且YX(1)， 令F=FF,对F中的每一个函数依赖YZ，令X(1)= X(1)Z，转 输出X(1)，它就是X+。例 4 .10,4.2.4 函数依赖的推理规则(5),5 函数依赖集的等价和覆盖* 定义4.10 对关系模式R(U)上的两个函数依赖集F和G，如果满足F+G+，则称F和G是等价的。 如果F和G是等价的，则称F覆盖G(同时G也覆盖F)。 定理4.5 F+G+充分必要条件是FG+, GF+。 定理4.6 每个函数依赖集F都可以被一个右部只有单属性的函数依赖集G所覆盖。 定义4.11 如果函数依赖集合F满足： F中每一个函数依赖的右部都是单属性，即全是X A的形式，其中XU，AU； 对F中的任一函数依赖X A，有FXA与F不等价； 对F中的任一函数依赖X A，若Z X，则(FXA)ZA与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)。各范式之间的关系为 1NF2NF3NFBCNF 4NF5NF。 2、关系模式的规范化：将一个低级别范式的关系模式，通过模式分解转换为若干个高一级范式的关系模式的过程。,定义4.12 如果一个关系模式R(U)的所有属性都是不可再分的基本数据项，则称R(U)为第一范式，即R(U) 1NF。 第一范式通常存在数据冗余过多、删除异常和插入异常等问题。例4.12,4.3.2 第一范式(1NF),4.3.3 第二范式(2NF),定义4.13 若R(U)1NF，且每一个非主属性完全函数依赖于某个候选键，称R(U)为第二范式，即R(U)2NF。例4.13,4.3.4 第三范式(3NF),定义4.14 设关系模式R(U)2NF，且每一个非主属性不传递函数依赖于R(U)的候选键，则称R(U)为第三范式，即R(U)3NF。例4.14,4.3.5 BC范式(BCNF)(1),定义4.15 若关系模式R(U)1NF，对于R(U)的任意一个函数依赖XY，若YX ，则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.5 BC范式(BCNF)(2),定理4.8 若R(U)BCNF，则R(U)3NF。 定理4.9 如果R(U)3NF且R(U)有唯一候选键X，且不存在使 的平凡函数依赖XY，则必有R(U)BCNF。例4.15-16 BCNF是在函数依赖条件下对模式分解所能达到的最高分离程度。,4.3.5 BC范式(BCNF)(3),例4.17 定义4.16 设R(U)是属性集U上的一个关系模式，X，Y，Z是U的子集，并且Z=UXY。若对于R(U)的任一具体关系r，r在属性(X，Z)上的每一个值，就有属性Y上的一组值与之对应，且这组值仅仅决定于X上的值而与Z上的值无关，则称Y 多值依赖于X，记作XY。例4.18,4.3.6 多值依赖(1),2、多值依赖的性质* 互补律：若X Y，则XZ，其中ZUXY。多值依赖的互补性也称为对称性。 函数依赖导出多值依赖：若XY，则XY。 传递律：若XY且YZ，则X(ZY)。 增广律：若XY，且VW，则WXVY。 自反律：若YX，则 XY。 多值依赖导出函数依赖：若XY，ZY，YW=，WZ，则 XZ。 合并律：若XY，YZ，则XYZ。 分解律：若XY，X Z，则X(YZ)，X(ZY)。,4.3.6 多值依赖(2),定义4.17 设关系模式R(U)1NF，若对于R(U)的每一个非平凡的多值依赖XY(YX)，X都含有候选键，则称R(U)为第四范式，即R(U)4NF。 定理4.10 若R(U) 4NF，则R(U) BCNF。,4.3.7 第四范式(4NF),4.3.8 关系模式规范化步骤,例4.20,1、关系模式的分解：设有关系模式R(U)和R1(U1), R2(U2), , Rk(Uk)，其中U=A1, A2, , An， Ui U(i=1,2, k)且UU1U2Uk。 令=R1(U1), R2(U2), , Rk(Uk)，则称为关系模式R(U)的一个分解。例4.21 2、关系模式分解的标准： 分解具有无损连接性；可能不保持函数依赖，丢失候选键，即与分解前不等价； 分解保持函数依赖；可能不具无损连接性，无法恢复以前的元组，即与分解前不等价； 分解既保持函数依赖，又具有无损连接性。最好的分解，与分解前等价。,4.4.1 模式分解中存在的问题,定义4.18 设R(U)是一关系模式，F是R(U)满足的一个函数依赖集，将R(U)分解成关系模式=R1(U1), R2(U2), , Rk(Uk)，UU1U2Uk。如果对R(U)中满足F的每一个具体关系r都有： 则称这个分解相对于F具有无损连接性(Lossless Join Decomposition)，简称为无损连接分解，即r为它自己在Ui上投影的自然连接。 r的投影连接表达式 用m(r)表示，称它为关系r的投影连接变换式。在一般情况下，r和m(r)不一定相等。对于关系模式R(U)关于F的无损连接条件是：任何满足F的关系r，有rm(r)。,4.4.2 无损连接(1),定理4.11* 设R(U)是一关系模式，=R1(U1), R2(U2), , Rk(Uk)是R(U)的一个分解，r是R(U)的任一具体关系，设 (i1, 2, k)，那么有： r m(r)； 若s= m(r)，则 (i1，2，k)； m(m(r)= m(r)。,4.4.2 无损连接(2),4.4.3 无损连接的测试(1),例4.22 算法4.2 无损连接的测试。 输入：关系模式R(U)，其中U=A1, A2, , An，R(U)上成立的函数依赖集F和R(U)的一个分解=R1(U1), R2(U2), , Rk(Uk)，其中UU1U2Uk。 输出： 相对于F具有或不具有无损连接性的判断。,算法步骤： 构造一张k行n列的表格，每列对应一个属性Aj(j=1, 2, , n)，每行对应一个模式Ri(Ui) 的属性集合(i=1, 2, , k)。如果Aj在Ui中，那么在表格的第i行第j列处填上符号aj，否则填上符号bij， 反复检查F的每一个函数依赖，并修改表格中的元素，直到表格不能修改为止。其方法如下： 取F中的函数依赖XY，如果表格中有两行在X分量上相等，在Y分量上不相等，那么修改Y分量上的值，使这两行在Y分量上也相等，具体修改分两种情况： 如果Y的分量中有一个是aj，那么另一个也修改成aj， 如果Y的分量中没有aj，那么用下标i较小的那个bij替换另一个符号。 若修改结束后的表格中有一行全是a，即al, a2, , an，那么相对于F是无损连接分解，否则，相对于F不是无损连接分解。 例4.23,4.4.3 无损连接的测试(2),定理4.12 关系模式R(U)的一个分解 =R1(U1), R2(U2), , Rk(Uk)是无损连接分解的充分必要条件是算法4.2终止且最终结果表中有一行的元素为a1, a2, , an。 定理4.13 如果R(U)的分解为Rl(U1)，R2(U2)，其中U=U1U2，F为R(U)所满足的函数依赖集合，则分解是无损连接的充分必要条件为(U1U2)(U1U2)或者(U1U2)(U2U1)成立。例4.24,4.4.3 无损连接的测试(2),4.4.4 保持函数依赖的分解(1),设F是属性集U上的函数依赖集，Z是U上的一个子集，F在Z上的一个投影用Z(F)表示，定义为：Z(F)XY | (XY)F+且XYZ 定义4.19 设关系模式R(U)的一个分解=R1(U1), R2(U2), , Rk(Uk)，F是R(U)满足的函数依赖集，如果 ，则称分解保持函数集F，简称保持函数依赖。,算法4.3 函数依赖测试 输入：R(U,F)和=R1(U1), R2(U2), , Rk(Uk) 输出：是否保持F的判断结果。 算法步骤： 令 ，F=FG，Result=True 对于F中的第一个函数依赖XY，计算 并令F=FXY； 若Y ，则令Result=False，转 否则，若F，转，否则，转； 若Result=True则保持函数依赖F，否 则不保持函数依赖F。,4.4.4 保持函数依赖的分解(2),对于关系模式的分解，有以下几个重要事实： 若要求分解保持函数依赖，那么模式分解总可以达到3NF，但不一定能达到BCNF。 若要求分解既保持函数依赖，又具有无损连接性，可以达到3NF，但不一定能达到BCNF。 若要求分解具有无损连接性，那一定可达到4NF。,4.4.4 保持函数依赖的分解(3),4.4.5 分解成3NF的模式集(1),算法4.4 将一个关系模式转