数据依赖和关系模式规范化.ppt

第10章 数据依赖和关系模式规范化,10.1 关系模式设计中的数据语义问题10.2 函数依赖(FD)10.3 多值依赖(MVD)10.4 联接依赖(JD)*10.5 关系模式的分解及其问题10.6 关系模式的规范化,10.1 关系模式设计中的数据语义问题,前面我们已经讨论了关系数据库的基本概念、关系模型的三个部分以及关系数据库的标准语言SQL。但是还有一个很基本的问题尚未涉及，针对一个具体问题，应该如何构造一个适合于它的数据库模式，即应该构造几个关系模式，每个关系由哪些属性组成等。这是数据库设计的问题，确切地讲是关系数据库逻辑设计问题。,10.1 关系模式设计中的数据语义问题,下面首先回顾一下关系模型的形式化定义。一个关系模式应当是一个五元组。R(U,D,DOM,F)这里：关系名R，它是符号化的元组语义；一组属性U；属性组U中属性所来自的域D；属性到域的映射DOM；属性组U上的一组数据依赖F由于D和DOM对模式设计关系不大,因此我们在本章中把关系模式看作是一个三元组：R 当且仅当U上的一个关系r满足F时，称r为关系模式R的一个关系。,10.1 关系模式设计中的数据语义问题,关系作为一张二维表,我们对它有一个最起键的要求：每一个分量必须是不可分的数据项。满足了这个条件的关系模式就属于第一范式（1NF）。我们的任务是研究模式设计，研究设计一个“好”的（没有“毛病”的）关系模式的办法。数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系。它是现实世界属性间相互联系的抽象，是数据内在的性质，是语义的体现。现在人们已经提出了许多种类型的数据依赖，其中最重要的是函数依赖(Functional Dependency简记为FD)和多值依赖(Multivalued Dependency简记为MVD)。函数依赖极为普遍地存在于现实生活中。,10.1 关系模式设计中的数据语义问题,比如描述一个学生的关系,可以有学号(SNO),姓名(SNAME),系名(SDEPT)等几个属性。由于一个学号只对应一个学生,一个学生只在一个系学习。因而当“学号”值确定之后,姓名和该生所在系的值也就被唯一地确定了。就象自变量x确定之后,相应的函数值f(x)也就唯一地确定了一样，我们说SNO函数决定SNAME和SDEPT,或者说SNAME，SDEPT函数依赖于SNO,记为 SNOSNAME,SNOSDEPT。,10.1 关系模式设计中的数据语义问题,现在我们要建立一个数据库来描述学生的一些倩况。面临的对象有：学生(用学号SNO描述),系(用系名SDEPT描述),系负责人(用其姓名MN描述),课程(用课程名CNAME描述)和成绩(G)。现实世界的已知事实告诉我们 一个系有若干学生,但一个学生只属于一个系；一个系只有一名(正职)负责人；一个学生可以选修多门课程,每门课程有若干学生选修；每个学生学习每一门课程有一个成绩；如果只考虑函数依赖这一种数据依赖,我们就得到了一个描述学校的数据库模式S，它由一个单一的关系模式构成：U=SNO，SDEPT，MN，CNAME，G F=SNOSDEPT，SDEPTMN，(SNO，CNAME)G,10.1 关系模式设计中的数据语义问题,这个模式有下述三个“毛病”：插入异常：如果一个系刚成立尚无学生,或者虽然有了学生但尚未安排课程。那么我们就无法把这个系及其负责人的信息存入数据库。删除异常：反过来,如果某个系的学生全部毕业了,我们在删除该系学生选修课程的同时,把这个系及其负责人的信息也丢掉了。更新异常：比如，某系负责人更换后,就必须逐一修改有关的每一个元组。数据冗余：比如,每一个系负责人的姓名要与该系每一个学生的每一门功课的成绩出现的次数一样多。这样,一方面浪费存储,另一方面系统耍付出很大的代价来维护数据库的完整性。,10.1 关系模式设计中的数据语义问题,为什么会发生插入异常和删除异常呢?这是因为这个模式中的函数依赖存在某些不好的性质。假如我们把这个单一的模式改造一下,分成三个关系模式：S；SG；DEPT；这三个模式都不会发生插入异常、删除异常的毛病,数据的冗佘也得到了控制。一个模式的函数依赖会有哪些不好的性质,如何改造一个不好的模式,这就是本章要讨论的主要内容。,10.2 函数依赖,定义10.1：设R(U)是属性集U上的关系模式。X,Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作XY。下面介绍一些术语和记号：XY，但YX，则称XY为平凡的函数依赖。否则，称XY为非平凡的函数依赖。今后，若不特别声明，我们总是讨论非平凡的函数依赖。若XY，则称X为决定因素(Determinant)。若XY，YX，则记作XY。若Y不函数依赖于X，则记作X Y。,10.2 函数依赖,定义10.2：在R(U)中,如果XY，并且对于X的任何一个真子集X,都有X Y,则称Y对X完全函数依赖,记作:X Y。若XY,但Y不完全函数依赖于X,则称Y对X部分函数依赖,记作X Y。定义10.3：在R(U)中,如果XY,(Y X)，Y X,YZ,则称Z对X传递函数依赖。加上条件Y X,是因为如果YX,则XY,实际上是,是直接函数依赖而不是传递函数依赖。定义10.4：对于满足一组函数依赖F的关系模式R,其任何一个关系r,若函数依赖XY都成立(即r中任意两元组t,s,若tX=sX,则tY=sY),则称F逻辑蕴含XY，记为F|=XY,10.2 函数依赖,Armstrong公理系统 为了求得给定关系模式的键,为了从一组函数依赖求得蕴含的函数依赖，例如，已知函数依赖集F,要问XY是否为F所蕴含，就需要一套推理规则，这组推理规则是l974年首先由Armstrong提出来的。设U为属性集总体，F是U上的一组函数依赖,于是有关系模式R。对R来说有以下的推理规则：Al.自反律(Reflexivity):若YXU,则XY为F所蕴含。A2.增广律(Augmentation):若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。A3.传递律(Transitivity):若XY及YZ为F所蕴含，则XZ为F所蕴含。注意，由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。,10.2 函数依赖,定理10.l：Armstrong推理规则是正确(sound)的。证：设YX U。对R的任一关系r中的任意两个元组t,s：若tX=sX,由于YX,有ty=sy,所以XY成立，自反律得证。设XY为F所蕴含,且ZU。设R的任一关系r中任意的两个元组t,s；若tXZ=sXZ,则有tX=sX和tZ=sZ；由XY,于是有tY=sY,所以tYZ=sYZ,所以XZYZ为F所蕴含，增广律得证。设XY及YZ为F所蕴含。对R的任一关系r中的任意两个元组t,s。若tX=sX,由于XY,有tY=sY；再由YZ,有tZ=sZ,所以XZ为F所蕴含，传递律得证。,10.2 函数依赖,根据这三条推理规则可以得到下面三条很有用的推理规则:合并规则:由XY,XZ,有XYZ。伪传递规则：由XY,WYZ,有XWZ。分解规则：由XY及Z Y,有XZ。根据合并规则和分解规则,很容易得到这样一个重要事实：引理10.l：XA1 A2.Ak成立的充分必要条件是XAi成立(i=l,2,.,k)。,10.2 函数依赖,定义10.5：在关系模式R中为F所逻辑蕴含的函数依赖的全体叫做F的闭包,记为F+。定义10.6：给定关系模式R，如果能由F根据Armstrong公理导出XY，则称XY是F的逻辑导出，记为F=XY。人们把自反律,传递律和增广律称为Armstrong公理系统。Armstrong公理系统是有效的、完备的。Armsttrong公理的有效性指的是：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中；Armsttrong公理的完备性指的是F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。,10.2 函数依赖,要证明Armsttrong公理的完备性，就首先要解决如何判定一个函数依赖是否属于由F根据Armstrong公理推导出来的函数依赖的集合。当然，如果能求出这个集合，问题就解决了。但不幸的是，这是一个NP完全问题。比如从F=XA1.,XAn 出发，我们至少可以推导出2n个不同的函数依赖。为此引入下面概念：定义10.7：设F为属性集U上的一组函数依赖，XU，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包。,10.2 函数依赖,由引理10.1容易得出：引理10.2：设F为属性集U上的一组函数依赖，X,Y U，XY能由F根据Armstrong公理导出的充分必要条件是YXF+。于是,判定XY是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，并判定Y是否为XF+的子集的问题。这个问题由算法10.l解决了。,10.2 函数依赖,算法10.l：求属性集X(X U)关于U上的函数依赖集F的闭包XF+。输入：X，F 输出：XF+步骤：令X(0)=X，i=0 求B，这里B=A|(存在VW)(VWFVX(i)AW)；X(i+1)=X(i)B判断X(i+1)=x(i)吗?若相等或X(i)=U 则X(i)就是XF+,算法终止。若否，则i=i+l，返回第 2)步。,10.2 函数依赖,例1:已知关系模式R,其中U=A,B,C,D,E；F=ABC，BD，CE，ECB，ACB。求(AB)F+。解：由算法5.1，X(0)=AB；计算X(1)；逐一的扫描F集合中各个函数依赖,找左部为A,B,或 AB的函数依赖。得到两个：ABC，BD。于是X(1)=ABCD=ABCD。因为 X(0)X(1)，所以再找出左部为ABCD子集的那些函数依 赖，又得到CE，ACB，于是X(2)=X(1)BE=ABCDE。因为X(2)已等于全部属性集合,所以(AB)F+=ABCDE。对于算法10.l，令ai=|X(i)|,ai 形成一个步长大于1的严格递增的序列,序列的上界是|U|,因此该算法最多|U|-|X|次循环就会终止。,10.2 函数依赖,定理10.2:Armstrong公理系统是有效的、完备的。Armstrong公理系统的有效性可由定理10.l得到证明。下面我们给出完备性的证明。我们证明完备性的逆否命题，即若函数依赖XY不能由F从Armstrong公理导出，那么它必然不为F所蕴含，其证明分三步：若VW成立，且VXF+，则WXF+。因VXF+,有XV成立；由A3规则有XW成立，所以WXF+。,10.2 函数依赖,由下列两个元组构成的二维表，必是R的一个关系r，即满足F中的全部函数依赖。若r不是R的关系，则必由于F中有函数依赖VW在r上不成立所致。由r的构成可知，V必定是XF+的子集，而W不是XF+的子集，可是由 l)，WXF+，矛盾。所以r必是R的一个关系。,10.2 函数依赖,若XY不能由F从Armstrong公理导出，则Y不是XF+的子集，因此必有Y的子集Y满足Y U-XF+，即XY在r上不成立，故XY必不为R蕴含.Armstrong公理的完备性及有效性说明了“逻辑导出”与“逻辑蕴含”是两个完全等阶的概念。于是F+也可以说成是由F出发借助Armstrong公理导出的函数依赖的集合。从蕴含(或导出)的概念出发，又引出了两个函数依赖集等价和最小依赖集的概念。,10.2 函数依赖,定义10.7：如果G+=F+，则称函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖)，或F与G等价。引理10.3：F+=G+的充分必要条件是FG+并且GF+。证：必要性显然,只证充分性。若F G+,则XF+XG+。任取XYF+则有 Y XF+XG+。所以XY(G+)+=G+。即F+G+。同理可证G+F+，所以F+=G+。而要判定F G+,只须逐一对F中的函数依赖XY，考查Y是否属于XG+就行了。因此引理10.3给出了判断两个函数依赖集等价的可行算法。,10.2 函数依赖,定义10.8：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖(Canonical Cover)。F中任一函数依赖的右部仅含有一个属性。F中不存在这样的函数依赖XA，使得F与F-XA等价。F中不存在这样的函数依赖XA,X有真子集Z使得F-XAZA与F等价。,10.2 函数依赖,例2：考察5关系模式S,其中：U=SNO，SDEPT，MN，CNAME，G,F=SNOSDEPT，SDEPTMN，(SNO,CNAME)G F=SNOSDEPT，SNOMN，SDEPTMN，(SNO，CNAME)G，(SNO，SDEPT)SDEPT 根据定义10.8可以验证F是最小覆盖，而F不是。因为F-SNOMN与F等价,F-(SNO,SDEPT)SDEPT与F等价。,10.2 函数依赖,定理10.3：每一个函数依赖集F均等价于一个极小函数依赖集Fmin。此Fmin称为F的最小依赖集。证：这是一个构造性的证明，我们分三步对F进行“极小化处理”，找出F的一个最小依赖集来。逐一检查F中各函数依赖FDi:XY，若Y=A1A2.Ak,k2，则用XAj|j=1,2,k来取代XY。逐一检查F中各函数依赖FDi:XA，令G=F-XA,若AXG+,则从F中去掉此函数依赖(因为F与G等价的充要条件是AXG+)。逐一取出F中各函数依赖FDi:XA，设X=B1B2.Bm,逐一考查Bi(i=l,2,.,m),若A(X-Bi)F+,则以X-Bi 取代X（因为F与F-XAZA等价的充要条件是AZF+其中Z=X-Bi)。,10.2 函数依赖,最后剩下的F就一定是极小依赖集,并且与原来的F等价。因为我们对F的每一次改造都保证了改造前后的两个函数依赖集等价。这些证明很显然，请读者自行补出。应当指出，F的最小依赖集Fm不一定是唯一的，它和我们对各函数依赖FDi 及XA中X各属性的处置顺序有关。,10.2 函数依赖,例3:F=AB，BA，BC，AC，CA Fmin1=AB，BC，CA Fmin2=AB，BA，AC，CA 这里我们给出了F的两个最小依赖集Fmin1,Fmin2。若改造后的F与原来的F相同，那么就说明F本身就是一个最小依赖集，因此定理10.3的证明给出的极小化过程也可以看成是检验F是否极小依赖集的一个算法。两个关系模式R1,R2,如果F与G等价,那么R1的关系一定是R2的关系。反过来，R2的关系也一定是R1的关系。所以在R中用与F等价的依赖集G来取代F是允许的。,10.2 函数依赖,例4:R(A,B,C,D,E,H,I)F=ABE,AHD,BC,BDE,CD,HI,IH,HBE 试求F的最小依赖集Fmin解：Fmin=AB,BC,BE,CD,HI,IH,HB,10.3 多值依赖,除了函数依赖以外，关系的属性间还存在其他一些数据依赖关系，多值依赖(multivalued dependency,MVD)就是其中之一。下面让我们来看一个例子。例l：学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。我们可以用一个非规范化的关系来表示教员T,课程C和参考书B之间的关系：课程C 教员T 参考书B-物理 李 勇 普通物理学 王 军 光学原理 物理习题集-数学 李 勇 数学分析 张 平 微分方程 高等代数,10.3 多值依赖,把这张表变成一张规范化的二维表,就成为:Teaching课程C 教员T 参考书B-物 理 李 勇 普通物理学 物 理 李 勇 光学原理 物 理 李 勇 物理习题集 物 理 王 军 普通物理学 物 理 王 军 光学原理 物 理 王 军 物理习题集 数 学 李 勇 数学分析 数 学 李 勇 微分方程 数 学 李 勇 高等代数 数 学 张 平 数学分析 数 学 张 平 微分方程 数 学 张 平 高等代数,10.3 多值依赖,仔细考察这类关系模式，发现它具有一种称之为多值依赖(MVD)的数据依赖。定义10.9：设R(U)是属性集U上的一个关系模式。X，Y，Z是的U的子集,并且Z=U-X-Y。关系模式R(U)中多值依赖XY成立，当且仅当对R(U)的任一关系r,给定的一对(x，z)值有一组Y的值，这组值仅仅决定于x值而与z值无关。例如，在关系模式TEACHING中，对于一个(物理，光学原理)有一组T值李勇，王军，这组值仅仅决定于课程C上的值(物理)。也就是说对于另一个(物理,普通物理学)它对应的一组T值仍是李勇,王军，尽管这时参考书B的值已经改变了。因此T多值依赖于C，即CT。,10.3 多值依赖,以上对多值依赖进行了一些直观的讨论，下面我们将对MVD进行形式化的描述。定义10.10：设R(U)是属性集U上的一个关系模式。X，Y，Z是的U的子集,并且Z=U-X-Y，如果对R(U)的任一关系r，都有如下性质：如果r中存在2个元组s、t，使得：sX=tX 则r中必存在元组u，使得：(1)sX=tX=uX(2)uY=tY 且 uZ=sZ(即交换s、t在Y上的值得到的2个元组必在r中)则称关系模式R满足多值依赖XY。,10.3 多值依赖,与函数依赖一样，多值依赖也有一组公理：A4：互补律(complementation)如果XY，则X(U-X-Y)以后如果需要，可用XY|(U-X-Y)表示多值依赖，以强调其互补关系。A5：扩展律(MVD)如果XY且VW，则WXVYA6：传递律(MVD)如果XY且YZ，则X(Z-Y)下面两条为(FD+MVD)公理：A7：如果XY，则XY，即FD是MVD的特例。A8：如果XY、ZY且对某一个与Y不相交的W有：如果 WZ，则XZ。,10.3 多值依赖,若XY，而Z=U-X-Y为空，则称XY 为平凡的多值依赖。多值依赖具有以下性质：多值依赖具有对称性。即若XY，则XZ，其中ZUXY。多值依赖的传递性。即若XY，YZ，则XZY。函数依赖可以看作是多值依赖的特殊情况。即若XY，则XY。这是因为当XY时，对X的每一个值x，Y有一个确定的值y与之对应，所以XY。若XY，XZ，则XYZ。若XY，XZ，则XYZ。若XY，XZ，则XYZ，XZY。,10.3 多值依赖,由上述公理，还可以得出下列四个有关MVD的推导规则：MVD合并规则 如果XY、YZ，则XYZMVD伪传递规则 如果XY、WYZ，则WX(Z-WY）混合伪传递规则 如果XY、XYZ，则X(Z-Y）MVD分解规则 如果XY、XZ，则X(YZ）、X(Y-Z)、X(Z-Y）均成立。以上规则的证明从略。,10.3 多值依赖,多值依赖与函数依赖相比，具有下面两个基本的区别：多值依赖的有效性与属性集的范围有关。若XY在U上成立则在W(XYWU)上一定成立；反之则不然，即XY在W(WU)上成立，在U上并不一定成立。这是因为多值依赖的定义中不仅涉及属性组X和Y，而且涉及U中其余属性Z。一般地,在R(U)上若有XY在W(WU)上成立,则称XY为R(U)的嵌入型多值依赖(eMVD)。但是在关系模式R(U)中函数依赖XY的有效性仅决定于X,Y这两个属性集的值。只要在R(U)的任何一个关系r中,元组在X和Y上的值满足定义10.l，则函数依赖XY在任何属性集W(XY W U)上成立。若函数依赖XY在R(U)上成立，则对于任何Y Y均有XY成立。而多值依赖XY若在R(U)上成立，我们却不能断言对于任何Y Y有XY成立。,10.5 关系模式分解及其性质,定义10.5-1 设R(U)为关系模式，则称=R1(U1),R2(U2),Rk(Uk)(其中U=)为R的一个分解。定义10.5-2 函数依赖集F在属性集Ui(U)上的投影定义为：,定义10.5-3 设=R1,R2,Rk为R的一个分解，r是R上的任意一个具体关系，如果满足条件：,则称为无损连接分解(Lossless-join decomposition)。,Example of Lossy-Join Decomposition,Lossy-join decompositions result in information loss.Example:Decomposition of R=(A,B)R2=(A)R2=(B),A,B,121,A,B,12,r,A(r),B(r),A(r)B(r),A,B,1212,10.5 关系模式分解及其性质,定义10.5-4 设=R1,R2,Rk为R的一个分解，如果,则称为保持函数依赖(Dependency preservation)的分解。定义10.5-5 设=R1,R2,Rk为R的一个分解，r是R上的任意一个具体关系，则r对于的投影连接运算定义为：,10.5 关系模式分解及其性质,引理10.5-1:设=R1,R2,Rk为R的一个分解，r是R上的任意一个具体关系，令ri=Ri(r),s=m(r)则有：(1)r m(r)(2)Ri(m(r)=Ri(s)=ri(3)m(m(r)=m(r)证：(1)任取tr,则tRiri(i=1,2,k)。由于tR1,tRk本来取自t在Ri上的投影，因此在进行 连接时，必然相互匹配，拼接成元组t，故tm(r)，即rm(r)(2)由(1)可知，rs,因此Ri(r)Ri(s),或 ri Ri(s)。现只须证Ri(s)ri。为此任娶uRi(s),则必有tss,使tsRi=u，由s的构造方式可知tsRiri(i=1,k),即 uri,因此有Ri(s)ri。(3)由Ri(s)=ri，可知:m(m(r)=m(s)=m(r)(证毕),10.5 关系模式分解及其性质,由引理10.5-1可得到下面的结论：如果 r m(r)，则不是无损分解。由引理10.5-1(1)可知，r经过分解后再连接，如果不是无损分解，则所得到的结果的元组数总比原来的r多，即所谓“元组增加，信息丢失(有损)！”。由引理10.5-1(2)可知，对r进行m(r)变换后得到的s可满足条件：Ri(s)=ri。但必须注意：如果ri不是r的投影，而是独立的关系，则一般而言，连接后的关系s不再满足条件Ri(s)=ri，而是 Ri(s)ri。这可由下面的例子看出：例10-4：（P384）,10.5 关系模式分解及其性质,下面介绍无损连接分解的检验算法。算法10.5-1:检验一个分解是否无损连接分解。输入：关系模式R(A1,An);R上的函数依赖集F；R的一个分解=R1,R2,Rk；输出：是否无损连接分解。方法：（1）建立一个n列、k行的符号表M(图18-7)：A1 A2 Aj An R1 R2 Ri Mi,j Rk,10.5 关系模式分解及其性质,符号表M各元素的值由下面的规则确定：,用F中的每一函数依赖XY对M反复进行下列检查和处理，直到M不再改变为止。检查X中的属性所对应的列，找出在X上取值相等的行。如果找到两个(或多个)行在X上取值相等，就将对应行中Y中属性所对应的符号改为一致，即如果其中之一为aj，则将其他符号也改为aj；如果全部符号都是“b”符号，则将它们改为同样的“b”符号。如此进行下去，直到发现M中某一行变为：a1,a2,an，则说明是无损连接分解；否则一直进行到M不再改变为止，则说明不是无损连接分解。例10-5：设R(ABCDE)F=AC,BC,CD,DEC,CEA=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)为R的一个分解 试判断是否无损分解。,10.5 关系模式分解及其性质,定理10.5-1:算法10.5-1可以正确判断一个分解是否无损连接分解。证明:(见P388-389)首先证明算法10.5-1的判断条件是必要的；其次再证明算法10.5-1的判断条件是充分的。算法10.5-1是一个普遍算法，即无论一个关系模式被分解为多少个关系模式，都可以用这一算法检验其是否为无损分解。但如果一个关系模式只被分解为2个关系模式，则可以用下面更简单的方法检验其无损连接性。定理10.5-2:设=R1(U1),R2(U2)是R(U)的一个分解，则为无损分解的充分必要条件为(U1U2)(U1U2)或(U1U2)(U2U1)证：(P389),10.5 关系模式分解及其性质,例10-6：R(C#,TN,D)F=C#TN,TN D=R1(C#,TN),R2(TN,D)试判断是否无损分解(P389)下面介绍检验分解是否保持函数依赖的方法。检验分解是否保持函数依赖实质上就是检验 是否覆盖F。算法10.5-2:检验分解是否保持函数依赖。输入：=R1,R2,Rk，函数依赖集F输出：是否保持F。方法：令G=为检验G是否覆盖F，可对F中的每一函数依赖XY进行下列检验：首先计算，然后检查Y是否被包含在 中。,10.5 关系模式分解及其性质,下面是不必求出G而计算 的算法：Z:=X;repeat for i=1 to k do Z:=Z(Z Ui)F Ui)until Z不再变化；如果Y被包含在 中，则XY。如果F中的所有函数依赖经检验都属于，则保持依赖，否则不保持依赖。例10-7：R(ABCD)F=AB,BC,CD,DA 试判别分解=R1(AB,R2(BC),R3(CD)是否保持依赖。（P390）,10.6 关系模式的规范化,为了使数据库设计的方法走向完备，人们研究了关系规范化理论，以指导我们设计规范化的数据库模式。关系数据库中的关系模式要满足一定的规范化要求，满足不同程度规范化要求的关系模式的类称为不同的范式。满足最低要求的关系模式称为第一范式,简称lNF。在第一范式中满足进一步要求的为第二范式，其余以此类推。R为第几范式就可以写成RxNF。按属性间依赖情况来区分，关系规范化的程度为1NF,2NF,3NF,BCNF,4NF和5NF等。对于各种范式之间的关系有 5NF 4NF BCNF 3NF 2NF lNF 成立。一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这一过程称为规范化。,10.6 关系模式的规范化,在介绍各种范式之前，我们首先根据函数依赖的概念，重新给出键(Key)的定义。定义10.6-1:设K为R中的属性或属性组合，若 KU，则称K为R的一个超键。如果一个超键K的任何真子集都不再是超键，则称K为R的一个候选键(Candidate key)。候选键有时也简称为键。若关系模式中有多个候选键，则选定其中的一个为主键(Primary key)。定义10.6-2:包含在任何一个候选键中的属性，称为主属性(Prime attribute)或键属性(Key attribute)。不包含在任何候选键中的属性，则称为非主属性(Nonprime attribute)或非键属性(Non-key attribute)。最简单的情况，单个属性是候选键。最极端的情况下，整个属性组是候选键，并称为全键(All-key)。例：关系模式R(P,W,A),属性P表示演奏者，W表示作品,A表示听众。假设一个演奏者可以演奏多个作品，某一作品可被多个演奏者演奏。听众也可以欣赏不同演奏者的不同作品，这个关系模式的候选键为(P,W,A)，即All-key。,10.6 关系模式的规范化,定义10.6-3：设关系模式R1NF，若对R中任何非平凡的函数依赖XY(Y X)，X必含有键，则称R为BCNF(Boyce-Codd normal form)。上述定义说明，若关系模式R中的每一个决定因素都包含键，则RBCNF。这就是说，在BCNF中，除了键决定其它所有属性这样的函数依赖及其所蕴涵的函数依赖外，不再有其它非平凡的函数依赖，特别是不存在以不含键的属性组作为决定子(即左部)的非平凡的函数依赖。BCNF在概念上已足够单纯。就函数依赖而言，它已进行了所有必须的分解，并消除了增、删、改异常和数据冗余。,10.6 关系模式的规范化,定义10.6-4：设关系模式R1NF，若对R中任何非平凡的函数依赖XA(A X)，都满足下列两个条件之一：(1)X是超键 或(2)A是主属性 则称R为3NF。由上面的定义不难看出，若R3NF，则每一个非主属性既不部分依赖于任何键也不传递依赖于任何键。比起BCNF，3NF放松了一个限制，即如果一个函数依赖的右部为主属性，则允许其左部不含任何键。从3NF的定义可知，XA违反3NF的定义可分为下列两种情况：A是非主属性，而X是某一(候选)键 的真子集；A是非主属性，而X既不是超键，也不是某一(候选)键 的真子集。如果是第一种情况，则说明在R中存在非主属性对于某一键的部分依赖；如果是第二种情况，则说明在R中存在非主属性对于某一键的传递依赖。,10.6 关系模式的规范化,因此，3NF就是通过从1NF消除非主属性对于所有键的部分函数依赖和传递函数依赖得到的关系模式。如果只消除了非主属性对于所有键的部分函数依赖，则所得到的关系模式被称为2NF。若一个关系模式R不是3NF，就会产生插入异常、删除异常、更新异常和数据冗余度等问题。所以一般情况下，关系模式应至少达到3NF。从有关定义，不难看出如果关系模式是BCNF，则也一定是3NF。但反之不然。下面用几个例子说明属于3NF的关系模式有的属于BCNF，但有的不属于BCNF。,10.6 关系模式的规范化,例l：关系模式SJP(S,J,P)中，S表示学生，J表示课程，P表示名次。每一个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生（即没有并列名次）。由语义可得到下面的函数依赖：(S,J)P，(J,P)S 所以(S,J)与(J,P)都可以作为候选键。这两个键各由两个属性组成,而且它们是相交的。这个关系模式中显然没有非主属性对键的传递依赖或部分依赖。所以SJP是3NF；而且除(S,J)与(J,P)以外没有其它决定因素，所以SJP也是BCNF。,10.6 关系模式的规范化,例2：关系模式STJ(S,T,J)中，S表示学生，T表示教师，J表示课程。每一教师只教一门课。每门课有若干教师,某一学生选定某门课,就对应一个固定的教师。由语义可得到如下的函数依赖。(S,J)T；(S,T)J；TJ。这里(S,J),(S,T)都是候选键。由于STJ中没有非典属性，因此也不会任何非主属性对键传递依赖或部分依赖，所以STJ是3NF。但STJ不是BCNF，因为T是决定因素，而T不包含键。3NF的“不彻底”性表现在可能存在主属性对键的部分依赖和传递依赖。任何非BCNF的关系模式还可以通过分解被规范化为BCNF。例如STJ可分解为ST(S,T)与TJ（T,J)，并且它们都是BCNF。但注意这一分解已不保持函数依赖。,10.6 关系模式的规范化,例3：设有关系模式R(S,C,Z)，其中S表示 街道(street)，C表示城市(city)，Z表示邮编(zip)；由语义可以得到以下函数依赖集F=CSZ，ZC(见图18-13(P393)，CS是R的键。在F中，ZC的左部虽不是超键，C是主属性，在3NF中允许这样函数依赖，而BCNF中则不允许。因此，R属于3NF，但不属于BCNF。R在被更新时仍可能发生异常，例如要插入一邮政编码与某个城市的对应关系，则必须知道该邮政编码所对应的一个街道。我们可以将R分解为 R1(Z,C)和R2(S,Z)，其中R1和R2都是BCNF，并且这一分解是无损的，但却不保持函数依赖。一般而言，属于3NF但不属于BCNF的关系并不多见。而且，即使出现这样的关系模式，其引起的更新异常也不是很严重。例如上面例子中的R(S,C,Z)，虽然不属于BCNF，但基本上是“合理”的关系模式。任何关系模式都可以分解为一组3NF，且既无损连接，又保持函数依赖。,10.6 关系模式的规范化,下面分别介绍将关系模式规范化为BCNF和3NF的算法，首先给出两个引理。引理10.6-1:设R(U,F)为关系模式，=R1,R2,Rk是R的一个无损分解，=S1,S2,Sm是Ri的一个无损分解，则R1,Ri-1,S1,Sm,Ri+1,Rk也是R的一个无损分解。证:(P393)引理10.6-2:设R(U,F)为关系模式，=R1,R2,Rk是R的一个无损分解，则=R1,R2,Rk,Rk+1,Rn(nK)也是R的一个无损分解。证:(P394),10.6 关系模式的规范化,算法10.6-1:将一个关系模式分解为一组BCNF且无损连接输入：关系模式R(U,F)输出：R的一个无损分解=R1,R2,Rk，其中Ri属于BCNF方法：初始化=R如果S为中一个非BCNF的关系模式，则S中必有非平凡的函数依赖XA，其中X不是S的超键。因此可将S分解为S1(XA)和 S2(XY)，式中Y=UsXA(其中Us为 S中的所有属性)，由于XAXYA=XA XY，故S可以无损分解为S1和S2，因此在中可用S1，S2取代原来的S。如此反复进行下去，直到中所有关系模式都成为BCNF为止。由于开始时是无损的(仅有R)，且之后每次分解都是无损的，根据引理10.6-1，始终都是无损分解。注意：在上述分解过程中，S1(XA)和S2(XY)中的属性都应是Us的真子集，否则即XA=Us，由XA，必有X是S的超键，与假设矛盾。因此，每经过一次分解得到新的关系模式S1,S2中的属性总必分解前的关系模式(S)中属性少，而当一个关系模式只包含两属性时，必为BCNF。所以，按照上述算法进行分解一定会终止，并将使中的所有关系模式都成为BCNF。,10.6 关系模式的规范化,例：R(S#,C#,G,TN,D),F=(S#,C#)G,S#TN,TND 试将R分解为BCNF。BCNF分解的结果一般并不唯一，这与选择分解的顺序有关。算法10.6-1的缺点是涉及F+的计算，这一计算的复杂性是指数型的。有人已经证明判断一个关系模式是否属性BCNFS是一个NP完全问题。下面介绍将关系模式转化为3NF且即无损又保持依赖的算法。该算法分为两步。算法10.6-2:将一个关系模式转化为一组3NF且保持依赖输入：关系模式R(U,F)输出：R的一个保持依赖的分解=R1,R2,Rk，其中Ri属于3NF方法：首先将F以其最小覆盖替代，仍记为F。找出R中不在F中出现的属性，将她们从R中分离出来组成一个关系模式R0。其余属性组成的关系模式仍记为R。将F中的所有函数依赖按照左部相同的原则进行分组，并将每一组函数依赖XA1,X An(n=1)所涉及的属性XA1An作为中的一个关系模式输出。,10.6 关系模式的规范化,如果中有一个关系模式包含R的全部属性，则以整个R作为输出。算法终止。定理10.6-1:算法10.6-2可以将一个关系模式转化为一组3NF且保持依赖证:(P395)保持依赖显然。只须证明分解后的关系模式属于3NF。设Ri(XA1Am)(m=1)为中的任意一个关系模式，其中XA1,XAm 为Fmin当中以X为左部的所有函数依赖，易知X必为Fi的一个候选键(否则，将与Fmin为最小依赖集相矛盾)。为了证明Ri属于3NF，从Fi(Fmin在Ri上的投影)中任取非平凡的函数依赖YB，若B为非主属性，由X为Fi的一个候选键，可知BA1,Am，不妨设B=Aj(1=j=m)。令G=FminXAj。由B Y，可知X YG+，若YB G+，则有 XB=Aj G+，这与Fmin为最小依赖集相矛盾，故YB G+，而由 YBF+，可知必有YXF+，即Y是Ri的一个超键。定理得证。,10.6 关系模式的规范化,算法10.6-2产生的分解只保持依赖，但不一定是无损分解，所以要得到即保持依赖，又无损连接的分解必须进一步使用算法10.6-3。算法10.6-3：将一个关系模式转化为3NF且即无损又保持依赖输入：关系模式R(U,F)输出：R的一个既无损又保持依赖的分解=R1,R2,Rk，其中Ri属于3NF方法：首先用算法10.6-2得到R的一个保持依赖的3NF分解，设=R1,Rk，如果经检验已是无损分解，则将作为输出，算法终止；否则，求出R的一个键X，并令=R(X)定理10.6-2：算法10.6-3可将一个关系模式转化为一组3NF且既无损又保持依赖。证：(P395)显然保持依赖且将R全部分解为3NF(注意：R(X)必属于3NF)。只须证明 是无损分解。,10.6 关系模式的规范化,用算法10.6-3得到的分解不一定是最小的关系模式集合，即如果有Ui Uj(ij)，则Ri是多余的，可以删除。与算法10.6-1类似，用算法10.6