数据依赖和关系模式规范化.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，则WXVY A6：传递律(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，其中Z UXY。 多值依赖的传递性。即若XY，YZ， 则XZ Y。 函数依赖可以看作是多值依赖的特殊情况。即若XY， 则XY。这是因为当XY时，对X的每一个值x，Y有一个 确定的值y与之对应，所以XY。 若XY，XZ，则XYZ。 若XY，XZ，则XYZ。 若XY，XZ，则XYZ，XZY。 10.3 多值依赖 由上述公理，还可以得出下列四个有关MVD的推导规 则： MVD合并规则 如果XY、YZ，则XYZ MVD伪传递规则 如果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) AB 1 2 1 A B 1 2 r A(r) B(r) A (r) B (r) AB 1 2 1 2 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)中属性少，