关系模式的规范化理论.ppt

《关系模式的规范化理论.ppt》由会员分享，可在线阅读，更多相关《关系模式的规范化理论.ppt（61页珍藏版）》请在三一文库上搜索。

1、第6章 关系模式的规范化理论,本章主要内容,关系数据库的规范化设计是指面对一个现实问题，如何选择一个比较好的关系模式集合。规范化设计理论对关系数据库结构的设计起着重要的作用。,由于关系模型有严格的数学理论基础，因此人们就以关系模型为作为讨论对象，形成了数据库逻辑设计的一个有力工具关系数据库的规范化理论。,本章主要内容,（1）关系模式的冗余和异常问题。 （2）FD的定义、逻辑蕴涵、闭包、推理规则、与关键码的联系；平凡的FD；属性集的闭包；推理规则的正确性和完备性；FD集的等价；最小依赖集。 （3）无损分解的定义、性质、测试；保持依赖集的分解。 （4）关系模式的范式：1NF，2NF，3NF，BCN

2、F。分解成2NF、3NF模式集的算法。 （5）MVD、4NF、5NF的定义。,关系模式的规范化理论,6.1 关系模式设计中的问题 6.2 函数依赖 6.3 函数依赖的公理系统 6.4 关系模式的分解及其问题 6.5 关系模式的规范化 6.6 多值函数依赖与4NF 本章小结,6.1 关系模式设计中的问题,假设需要设计一个学生学习情况数据库StuDB。 下面我们以模式S_C_G（S#，SN，SD，SA，C，CN，G，PC）为例来说明该模式存在的问题。下表是其一个实例。,（1）冗余度大 （2）操作异常 由于数据的冗余，在对数据操作时会引起各种异常： 插入异常 删除异常 修改异常,关系模式的分解,我们

3、采用分解的方法，将上述S_C_G分解成以下三个模式： S（S，SN，SD，SA） C（C，CN，PC） S_C（S，C，G）,6.2 函数依赖,1）函数依赖(Functional Dependency，简称FD),在上述的关系模式S（S，SN，SD，SA）中，存在以下函数依赖： S #SD SSN SSA （S,C）G,定义6.1（函数依赖）：设有关系模式R(U)，其中UA1，A2，An是关系的属性全集，X、Y是U的属性子集，设t和u是关系R上的任意两个元组，如果t和u在X的投影tX=uX推出tY=uY，即：tXuX = tYuY 则称X函数决定Y，或Y函数依赖于X。记为XY。,2）几种类型的

4、函数依赖,例如X, XX , XZX等都是平凡函数依赖。,定义6.2（非平凡函数依赖、平凡函数依赖）：一个函数依赖XY如果满足YX，则称此函数依赖为非平凡函数依赖，否则称之为平凡函数依赖。,定义6.3（完全函数依赖、部分函数依赖）：设X、Y是关系R的不同属性集，若XY （Y函数依赖于X），且不存在XX ，使XY，则称Y完全函数依赖于X，记为 ； 否则则称Y部分函数依赖于X，记为 。,例如，在上例关系S中, 是完全函数依赖; 、 是部分函数依赖。,几种类型的函数依赖,在属性Y与X之间，除了完全函数依赖和部分函数依赖关系等直接函数依赖，还存在间接函数依赖关系。如果在关系S中增加系的电话号码DT，从

5、而有S #SD,SDDT，于是S#DT。在这个函数依赖中，DT并不直接依赖于S#，是通过中间属性SD间接依赖于S#。这就是传递函数依赖。,3）关系的关健字和超关键字,一个包含了关键字的属性集合也能够函数决定（但不是完全函数决定，而是部分决定）属性全集，我们把这种包含了关键字的属性集合称为超关键字(Super Key)。,例如，在上例的S（S，SN，SD，SA）、C（C,CN,PC）、S_C（S，C，G）三个关系模式中，存在以下关键字：,所以，S#、C#和（S#，C#）分别是关系模式S、C和S_C的关键字 。,所以，(S#，SN)和(S#，SD)都不是关键字，而是超关键字。,定义6.5（关键字）

6、:在关系模式R(U)中，若K U，且满足 ， 则称K为R的关键字。,6.3 函数依赖的公理系统,6.3.1 函数依赖的逻辑蕴涵 6.3.2 Armstrong公理系统 6.3.3 函数依赖集的等价与覆盖,6.3.1 函数依赖的逻辑蕴涵,例如在上述的传递函数依赖中，由XY，YZ，推导出XZ，这可以表示为： XY，YZ XZ 其中: 表示逻辑蕴涵。 一般地讲，函数依赖的逻辑蕴涵定义如下：,定义6.6（逻辑蕴涵）：设F是由关系模式R(U)满足的一个函数依赖集，XY是R的一个函数依赖，且不包含在F，如果满足F中所有函数依赖的任一具体关系r，也满足XY，则称函数依赖集F逻辑地蕴涵函数依赖XY，或称XY可

7、从F推出。可表示为： FXY,函数依赖集F的闭包F+,定义6.7：函数依赖集F所逻辑蕴涵的函数依赖的全体称为为F的闭包（Closure），记为F+，即F+XYFXY,例如，有关系R（X，Y，Z），它的函数依赖集FXY，YZ，则其闭包F+为：,6.3.2 Armstrong公理系统,1）独立推理规则 即下面给出的Armstrong公理的三条推理规则是彼此独立的。,（3） A3：传递律(Transitivity) 如果XY且YZ，则XZ成立。,（2） A2：增广律(Augmentation) 如果XY，且Z W，则XWYZ成立。 根据A2可以推出XWY、XZYZ或XWYW、XXY、XYX等。,（1

8、） A1：自反律(Reflexivity) 如果Y X，则XY成立，这是一个平凡函数依赖。 根据A1可以推出X、UX等平凡函数依赖（因为 X U）。,2）其他推理规则,推论1：合并规则(The Union Rule) XY，XZ XYZ,推论3：伪传递规则(The Pseudo Transitivity Rule) XY，WYZ XWZ,证：（1）XY XXY （A2增广律） XZ XYYZ （A2增广律） 由上可得XYZ （A3传递律）,（3）XYWXWY （A2增广律） WYZ （给定条件） 由上可得XWZ （A3传递律）,（2）Z Y YZ （A1自反律） XY （给定条件） 由上可得X

9、Z （A3传递律）,推论2：分解规则(The Decomposition Rule) 如果XY，Z Y，则XZ成立,一个重要定理,例6.2：设有关系模式R(A,B,C,D,E)及其上的函数依赖集F=ABCD,AB,DE，求证F必蕴涵AE。,定理6.1：若Ai(i=1，2，,n)是关系模式R的属性， 则X(A1，A2，,An)成立的充分必要条件是XAi均成立。,证明： AB （给定条件） AAB （A2增广律） ABCD （给定条件） ACD （A3传递律） AC，AD （分解规则） DE （给定条件） AE （A3传递律） 证毕。,属性集闭包,定义6.8（属性集闭包）:设有关系模式R(U),U

10、= A1，A2，,An,X是U的子集,F是U上的一个函数依赖集，则属性集X关于函数依赖集F的闭包 定义为： AiAiU，且XAi可用阿氏公理从F推出,例：设关系模式R(A,B,C)的函数依赖集为F=AB,BC，分别求A、B、C的闭包。,解：若XA， AB,BC （给定条件） AC （A2传递律） AA （A1自反律） =A，B，C （据定义）,若X=B BB （A1自反律） BC （给定条件） =B，C （据定义）,若X=C， CC （自反律） =C （据定义）,定理6.2:设F是关系模式R(U)上的函数依赖集,U是属性全集，X,Y U,则函数依赖XY是用阿氏公理从F推出的，充分必要条件是Y

11、； 反之，能用阿氏公理从F推出的所有XY的Y都在 中。,这个定理告诉我们，只要Y ，则必有XY。于是，一个函数依赖XY能否用阿氏公理从F推出的问题，就变成判断Y是否为 子集的问题。 下面介绍一下计算 的算法。,属性集的闭包计算,方法：根据下列步骤计算一系列属性集合X(0)，X(1)， (1) 令X(0)=X，i0； (2) 求属性集 /*在F中寻找满足条件V X(i)的所有函数依赖VW,并记属性W的并集为B*/ (3) X(i+1)X(i) B (4)判断X(i+1)= X(i)吗？ (4)若X(i+1) X(i)，则用i+1取代i,返回(2)； (5)若X(i+1) = X(i)，则 =X(

12、i)，结束。,算法6.1：求属性集X(X U)关于U上的函数依赖集F的闭包 。 输入：属性全集U,U上的函数依赖集F,以及属性集X U。 输出：X关于F的闭包 。,算法6.1的求解过程,例：设FAHC，CA，EHC，CHD，DEG，CGDH，CEAG，ACDH，令XDH ，求 。,最后， (DH)+=ACDEGH。,解： X(0)=X=DH 在F中找所有满足条件V X(0)=DH的函数依赖VW，结果只有DEG，则B=EG，于是X(1)X(0)B=DEGH 。 判断是否X(i+1)= X(i)，显然X(1)X(0)。 在F中找所有满足条件V X(1)=DEGH的函数依赖VW，结果为EHC，于是B

13、=C，则X(2)X(1)B=CDEGH 。 判断是否X(i+1)= X(i)，显然X(2)X(1)。 在F中找所有满足条件V X(2)=CDEGH的函数依赖VW，结果为CA，CHD，CGDH，CEAG，则B=ADGH，于是X(3)X(2)B=CDEGHB=ACDEGH 。 判断是否X(i+1)= X(i)，这时虽然X(3)X(2)。但X(3)已经包含了全部属性，所以不必再继续计算下去。,属性集闭包计算结束判断方法,在判断计算何时结束时，可用下面四种方法： （1）X(i+1)= X(i)。 （2）X(i+1)已包含了全部属性。 （3）在F中再也找不到函数依赖的右部属性是X(i)中未出现过的属性。

14、 （4）在F中再也找不到满足条件V X(i)的函数依赖VW。,6.3.3 函数依赖集的等价和覆盖,定义6.9（函数依赖集的等价、覆盖）：设F和G是关系R（U）上的两个依赖集，若F+=G+，则称F与G等价，记为F=G。也可以称F覆盖G，或G覆盖F；也可说F与G相互覆盖。,检查两个函数依赖集F和G是否等价的方法是： 第一步：检查F中的每个函数依赖是否属于G+，若全部满足，则F G+。如若有XYF,则计算 ,如果Y , 则XYG+; 第二步：同第一步，检查是否G F+; 第三步：如果F G+，且G F+，则F与G等价。 由此可见,F和G等价的充分必要条件是：F G+，且G F+。,引理6.1：设G是

15、一个函数依赖集，且其中所有依赖的右部都只有一个属性，则G覆盖任一左部与G（左部）相同的函数依赖集。,一个函数依赖集F可能有若干个与其等价的函数依赖集，我们可以从中选择一个较好以便应用的函数依赖集。标准至少是： 所有函数依赖均独立，即该函数依赖集中不存在这样的函数依赖，它可由这个集合中的别的函数依赖推导出来。 表示最简单，即每个函数依赖的右部为单个属性，左部最简单。,证明：构造GXAXYF且AY 由AY，XYF根据分解规则导出，从而等到G F+。 反之，如果YA1A2An，而且XA1，XA2，XAn在G中可根据合并律等到F G +。 由此可见，F与G等价，即F被G覆盖。,最小函数依赖集,定义6.

16、10（最小函数依赖集）:函数依赖集F如果满足下列条件，则称F为最小函数覆盖，记为Fmin： (1) F中每一个函数依赖的右部都是单个属性。 (2) 对F中任一函数依赖XA，FXA都不与F等价。 (3) 对于F中的任一函数依赖XA, FXAZA都不与F等价，其中Z为X的任一子集。,求函数依赖集F的最小覆盖的方法是： (1) 检查F中的每个函数依赖XA,若A= A1,A2,Ak,则根据分解规则，用XAi(i=1，2，k)取代XA。 (2) 检查F中的每个函数依赖XA,令G=FXA， 若有 A ，则从F中去掉此函数依赖。 (3) 检查F中各函数依赖XA，设X= B1,B2,Bm,检查Bi ， 当A

17、时，即以XBi替换X。,最小覆盖的求解事例,例6.5：求下列函数依赖集的最小覆盖： FAHC，CA，CHD，CEG，EHC， CGDH， CEAG，ACDH 。,解：(1)用分解规则将F中的所有依赖的右部变成单个属性，可以得到以下11个函数依赖： AHC，CA，CHD，ACDH （给定） CE，CG （由CEG分解得到） EHC （给定） CGH，CGD （由CGDH分解得到） CEA，CEG （由CEAG分解得到） (2) 根据阿氏公理去掉F中的冗余依赖 由于从CA可推出CEA，从CA、CGD、ACDH推出CGH，因此CEA和CGH是冗余，可从F删除 。 (3) 用所含属性较少的依赖代替所含

18、属性较多的依赖。 由于CA, ACDH中A是冗余属性，因此，可用CDH代替ACDH，故删除ACDH。 最后得到F的最小覆盖为： FAHC，CA，CHD，CDH，CE，CG，EHC，CGD，CEG,6.4 关系模式的分解 及其问题,6.4.1 什么叫模式分解 6.4.2 分解的无损连接性 6.4.3 保持函数依赖性,6.4.1 什么叫模式分解,例6.6：设在模式R(U,F)中 USNO，SNAME，DNAME，DADDR FSNOSNAME，SNODNAME，DNAMEDADDR 如果对R作如下分解（方法1）： =R1（SNO,SNAME,SNOSNAME）， R2（ DNAME，DADDR,

19、DNAMEDADDR）,定义6.11（模式分解）：关系模式R(U，F)的一个分解是若干个关系模式的一个集合：=R1(U1,F1),R2(U2,F2),Rn(Un,Fn) 式中：(1) 。 (2) 对每个i，j（1i,jn）有 。 (3) Fi(i=1，2，,n)是F在Ui上的投影，即,（1）连接不失真问题,方法2：假设按下列方法对R进行分解 =R1 (SNO,SNAME,DNAME,SNOSNAME,SNODNAME ), R2（DNAME,DADDR），DNAMEDADDR）,（2）依赖保持问题,上例方法1： FSNOSNAME，SNODNAME，DNAMEDADDR F1F2SNOSNAM

20、E，DNAMEDADDR F+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR (F1F2)+SNOSNAME，DNAMEDADDR,一个关系模式经分解后，其函数依赖集F也随之被分解，则分解后的依赖集Fi并集是否能保持原有的函数依赖关系？即 ? 若出现 ，说明分解后有些函数依赖被丢失了。,上例方法2： FSNOSNAME，SNODNAME，DNAMEDADDR F1F2SNOSNAME,SNODNAME,DNAMEDADDR F+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR (F1F2)+ SNOSNAME,SNODNAME,DNAMED

21、ADDR,SNODADDR,6.4.2 分解的无损连接性,1）无损连接分解的定义,定义6.12（无损连接分解，即连接不失真分解）：设关系模式R（U，F）上的一个分解为=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)，F是R（U，F）上的一个函数依赖集。如果对R中满足F的任一关系r都有 则称这个分解相对于F的是连接不失真分解或称无损连接分解。,对于关系模式R关于F的无损连接条件是： 任何满足F的关系r有r = m(r)。,r 和m(r)之间的联系,定理6.4：设R是一关系模式，=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)是关系模式R的一个分解，r是R的任一关系，（1i

22、k）,那么有： ； 如果s= m(r)，则 ，或 mm(r)= m(r),定理6.4证明, 由定理6-5可知 ，可得到 ，即 （因为s= m(r)）（也就是两边同时在Ui上投影，得 ）。 为了证明 。假设 ，则s中必存在满足tRi=ti的元组t。由于ts,对每个j,在rj中必存在元组uj满足tRj=uj (1jk),即 。 于是对那个特定的i，亦有tRi=ui，即tRiri。但tRi=ti，所以tiri，从而得到 （即 ）。 由 和 可得 （即 ）。, 由定理6-5可知 (i=1,2,k)，于是有 。 此式左式m(s)= mm(r)（由得），右式 m(r)， 因此得：mm(r) =m(r) 该

23、定理说明，关系模式只有在第一次分解的连接恢复后有可能丢失信息，此后的多次分解恢复均能使分解不失真,证明： 设任意一个元组tr,ti=tUi(i=1,2,k);则tiRi。根据自然连接定义，可知t在 中，即tm(r)，所以 。 该定理说明，一个关系模式经分解再连接恢复所得的新关系m(r)的元组一般比原关系的元组要多，而且m(r)一定包括原关系的元组。 只有当r= m(r)时，分解才是连接不失真分解。,2）无损连接的检验,方法1：采用检验表格构造法 算法6.2：连接不失真检验,方法 1： (1)构造一个n列k行表，每一行对应于一个模式Ri（1ik），每一列对应于一个属性Aj（1jn），如下表所示。

24、,(2) 初始表（填表）：若AjRi，则第i行第j列上填入aj，否则填入bij。 (3) 修改表：反复检查F中的每一个函数依赖XY，按下方法修改表格中的元素：取F中的函数依赖XY，检查Y中的属性所对应的列，找出X相等的那些行，将这些X的符号相同的行中的Y的属性所对应的符号改成一致。即如果其中有aj，则将bij改为aj；若无aj，则将它们全改为bij。一般取i是为其中的最小行号值。 (4) 如发现某一行变成a1，a2，,ak，则此分解具有连接不失真性。,事例说明,例：设有R(U,F)，其中：U =(A,B,C,D,E), F=(AC,BC,CD,DEC,CEA)，R的一个分解为： R1(AD)，

25、R2 (AB)，R3(BE) ，R4(CDE) ，R5(AE)是否无损分解？,根据算法6.2中(1)和(2)构造初始表，如表(a)所示。 根据AC，对表(a)进行处理，将b13、b23、b53改成同一符号b13，即b13b23b53。再根据BC，将b33、b13（R2中）改成同一符号b13。修改后如表(b)所示。 考虑CD，根据上述修改原则，将D所在的第4列的b24、b34、b54均修改成a4，其结果如表（c）所示。(因为AC,BC) 再考虑DEC，根据修改原则，将C所在的第3列第3、4、5行的b13、a3、b13均修改成a3，其结果如表（d）所示。(因为BC, AC, CD) 再考虑CEA，

26、根据修改原则，将A所在的第1列第3、4、5行的b31（由BC推出）、b41（由AC推出）、a1均修改成a1，其结果如表（e）所示。,简单的检验方法,方法2： 定理6.5：设= R1,R2是关系模式R的一个分解，F是R的一个函数依赖集，则对于F, 具有连接不失真性的充分必要条件是R1R2R1R2 F+，或R1R2R2R1F+。,例6.8：设有关系模式R(S,SN,C,G，SSN,(S,C)G)的一个分解为： =R1(S,SN,SSN)，R2(S,C,G,(S,C)G) 因为R1R2=S#，R1R2=SN，故R1R2R1R2，且S#SN属于F，所以该分解具有连接不失真性。,定理6-8和例6-9告诉

27、我们一个事实：如果两个关系模式间的公共属性集至少包含其中一个关系模式的关键字，则此分解必定具有连接不失真性。,6.4.3 函数依赖保持性,定义6.13：设有关系模式R,F是R上的函数依赖集，Z是R上的一个属性集合，则称Z所涉及到的F+中的所有函数依赖为F在Z上的投影，记为z(F)。,该定义实质上是，当XYF+时，若XYZ，则有z(F)， 可以定义为：,定义6-17：设关系模式R的一个分解为=R1,F1，R2,F2，Rk,Fk,F是R上的依赖集，如果对于所有的i=1,2, ,k，z(F)中的全部函数依赖的并集逻辑地蕴涵F中的全部依赖，则称分解具有依赖保持性。,判断两个函数依赖集是否等价的方法也可

28、以用来判断一个分解是否保持依赖。 下面以一个例子来说明一下。 ：设R(A,B,C,D)，FAB,CD，=R1(A,B，AB)，R2（C,D，CD）。 因为 FAB,CD，F1F2AB,CD 所以 F+ = (F1F2)+,该例还说明，一个具有依赖保持性的分解不一定具有连接不失真性。反之，一个连接不失真分解也不一定具有依赖保持性。,例：设R(A,B,C)，FAB，CB，=R1(A,B，AB)，R2（A,C，AC）。 R1R2=A, R1R2=B，R2R1=C R1R2R1R2= ABF 但FAB,CB，F1F2AB,AC,即F+ (F1F2)+ 可见具有连接不失真性，但不具有依赖保持性。,范式的

29、概念是由E. F. Codd在1970年首先提出来的。 满足特定要求的模式称之为范式。 所谓模式规范化，就是对关系模式应当满足的条件的某种处理，其目的是： (1)消除异常现象。 (2)方便用户使用，简化检索操作。 (3)加强数据独立性。 (4)使关系模式更灵活，更容易使用非过程化的高级查询语言。 (5)更容易进行各种查询统计工作。 关系规范化的条件可以分成几级，每一级称为一个范式，记为XNF，其中X表示级别,NF是范式(Normal Form)，即关系模式满足的条件。 范式的级别越高，条件越严格，因此有：,6.5 关系模式的规范化 6.5.1 范式,1）第一范式（1NF）,定义6.14（1NF

30、）：如果一个关系模式R的每个属性的域都只包含单纯值，而不是一些值的集合或元组，则称R是第一范式，记为R1NF, 把一个非规范化关系模式变为1NF有两种方法，一是把不含单纯值的属性分解为多个属性，并使它们仅含单纯值。,例如，设模式： P (PNO，PNAME，QOH,PJ(PJNO,PJNAME，PJMNO，PQC） 将模式P变为： P(PNO,PNAME,QOH,PJNO,PJNAME,PJMNO,PQC） 第二种方法是把关系模式分解，并使每个关系都符合1NF。则： Pl (PNO,PNAME,QOH) PJl (PNO,PJNO,PJNAME,PJMNO,PQC),关系PJl存在异常现象，例

31、如，当一个新工程刚提出，仅有工程名，没有工程号，也没有使用零部件，此时工程数据就不能写入数据库。原因是存在部分函数依赖：,2）第二范式（2NF）,定义6.15（2NF）：如果关系模式R1NF，且它的任一非主属性都完全函数依赖于任一候选关键字，则称R满足第二范式，记为R2NF。 把一个1NF的关系模式变为2NF的方法是，通过模式分解，使任一非主属性都完全函数依赖于它的任一候选关键字。,例如对上例，若把PJ1进一步分解成： PJ2 (PNO,PJNO,PQC) J(PJNO,PJNAME,PJMNO),3）第三范式（3NF）,定义6.16（3NF）：如果关系模式R2NF,且每一个非主属性不传递依赖

32、于任一候选关键字，则称R3NF。,例如把关系模式S分解成： ST (SNO，NAME，DNAME） DEPT(DNAME，DADDR),考察关系模式S (SNO，SNAME，DNAME，DADDR),SNO为候选关键字。但若假定一个系的学生的所在系地址相同，即一个系的学生的DADDR值一样。显然，SNODNAME,DNAMEDADDR，故SNODADDR,该关系模式在DADDR列存在高度数据冗余。 这是由于原关系模式中存在传递函数依赖。因此，要消除数据冗余这种异常现象，必须使关系模式中不出现传递函数依赖。,3NF定义告诉我们，一个关系模式满足3NF的充分必要条件是，它的每个非主属性既不部分依赖

33、也不传递依赖于候选关键字。,4）Boyce-Codd范式（BCNF),例如，模式S (NAME,SEX,BIRTH,ADDR,DNAME)的主属性为：NAME,SEX,BIRTH和ADDR，候选关键字为：(NAME,SEX)、(NAME,BIRTH)以及(NAME，ADDR)。定义中的A为(ADDR,DNAME)。显然有：,定义6.17（BCNF）：设有关系模式R及其函数依赖集F,X和A是R的属性集合，且AX。如果只要R满足XA，X就必包含R的一个候选关键字，则称R满足BCNF，记为RBCNF。 该定义主要有三点： (1)所有非主属性A对键都是完全函数依赖的(R2NF)。 (2)没有属性完全函

34、数依赖于非键的任何属性组(R3NF)。 (3)所有主属性对不包含它的键是完全函数依赖的（新增加条件）。,事例,解 由语义可得到如下的函数依赖： （SNO，CNO）TNO，（SNO，TNO）CNO，TNOCNO 这里（SNO，CNO），（SNO，TNO）都是侯选关键字。 因为没有任何非主属性对侯选关键字部分依赖，所以STC2NF。 没有任何非主属性对侯选关键字传递依赖，所以STC3NF。 但在F中有TNOCNO，而TNO不包含侯选关键字，所以STC不是BCNF关系,例6.13：关系模式STC（SNO，TNO，CNO），SNO表示学号，TNO表示教师编号，CNO表示课程号。每一个教师只教一门课，每

35、门课有若干教师，某一个学生选定某门课，就对应一个固定教师。试判断ST的最高范式。,这里我们可以将STC（SNO，TNO，CNO）分解成ST（SNO，TNO）和TC（TNO，CNO），它们都是BCNF。,范式之间的关系,1NF,3NF,BCNF,2NF,6.5.2 模式分解的算法,按照上面讨论的模式分解理论，一个模式分解必须满足： 连接不失真性； 依赖保持性 某一级范式。 但事实上不能顺利地同时满足上述三个条件。一般而言： (1)若要求连接不失真，分解可达到BCNF； (2)若要求依赖保持，则分解可达到3NF，但不一定能达到BCNF。 (3)若同时要求连接不失真和依赖保持，则分解可达到3NF，但

36、不一定能达到BCNF。,1）结果为BCNF的连接不失真分解,定理6.6：分解定理 (1) 设F是关系模式R的函数依赖集，=R1，R2，,Rk是R的一个分解，且对于F有连接不失真性。设Fi为F在Ri上的投影，即： 如果X和Y均为Ri的子集，则XYF+。又设1=S1,S2,Sm为Ri的一个分解，且对于Fi具有连接不失真性。如果将R分解为 R1，R2，,Ri1,S1,S2,Sm，Ri+1，Rk 则这一分解相对于F的一个连接不失真性分解。 (2) 设2=R1，R2，,Rk,Rk+1，Rn为R的一个分解，其中包含了的那些关系模式,则2相对于F的一个连接不失真性分解。,结果为BCNF的连接不失真分解算法,

37、输入：R(U，F) 输出：分解=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)，且，满足BCNF。 方法：反复应用定理610（分解定理），逐步分解关系模式R，使每次分解具有连接不失真性，并且分解出来的模式是BCNF。 置初值=R； 如果中所有关系模式都是BCNF，则转； 如果中有一个关系模式S不是BCNF，则S中必能找到一个函数依赖XA有X不是S的键，且AX，设S1XA，S2SA，用分解S1，S2代替S，则转； 分解结束，输出。,事例,例6.14：设有关系模式CTHRSG(C,T,H,R,S,G)及其函数依赖集F= CSG, CT,HRC , HSR, THR。 (1) 求所有候选

38、关键字 如果直接根据候选关键字的定义来求一个关系模式的所有关键字： 若属性A仅出现在所有函数依赖的右部，则它一定不包含在任何候选关键字中； 若属性A仅出现在所有函数依赖的左部，则它一定包含在某个候选关键字中； 若属性A既出现在函数依赖的右部，又出现在左部，则它可能包含在候选关键字中； 在上述基础上求属性集闭包。 对本例,G仅出现在函数依赖的右部，则它不包含在候选关键字中；又属性H和S仅出现在函数依赖的左部，则H和S必包含在候选关键字中。计算(HS)+为： (HS)(0) =HS (HS)(1) =HSR (HS)(2) =HSRC (HS)(3) = CTHRSG (HS)(4) = CTHR

39、SG 即(HS)+=CTHRSG，故HS是模式CTHRSG的唯一关键字。,(2) 分解,首先在F中找出这样一个函数依赖XA，其中X不包含R的任何候选关键字，也不包含A。把R分解成R1(X,A)和R2(S-A)。 对本例首先考虑CSG，则CTHRSGCSG,CTHRS。 为进一步分解，需求F+在CSG和CTHRS上的投影： CSG(F)=CSG；CTHRS(F)=CT,THR,HRC,HSRF1 很显然，模式CSG是BCNF。模式CTHRS不是BCNF，还要继续分解。 (2-1)求得CTHRS的候选关键字为HS。 (2-2)再分解CTHRS，选CT，将CTHRS分解为 CTHRSCT,CHRS。

40、 函数依赖集CT上投影的最小覆盖是CT，在CHRS上的投影的最小覆盖是CHR，HSR，HRC。记作： CT(F1)=CT；CHRS(F1)=CHR，HSR，HRCF2 显然,模式CT为BCNF，但模式CHRS不是BCNF，还要继续分解。 (2-3) 求得CHRS的唯一关键字为HS。 (2-4) 再分解CHRS，选CHR，将CHRS分解为 CHRSCHR，CHS。 F2在CHR、CHS上投影的最小覆盖为： CHR(F2)=CHR，HRC；CHS(F2)=HSC 在模式CHR中，HC、HR为键，其所有决定因素都是键，在模式CHS中，HS为键，显然CHR、CHS都为BCNF。,分解树,2）结果为3N

41、F的依赖保持分解,算法6-4：结果为3NF的依赖保持分解算法 输入：关系模式R和函数依赖集F 输出：结果为3NF的一个依赖保持分解 步骤： (1)如果R中有某些属性与F的最小覆盖F 中的每个依赖的左边和右边都无关，原则上可由这些属性构成一个关系模式，并从R中将它们消除； (2)如果F中有一个依赖涉及到R的所有属性，则输出R; (3)否则，输出一个分解,它由模式XA组成，其中XAF。但当XAl，XA2，XAn均属于F时，则用模式XAlA2An代替XAi(i=1,2，,n)。 例6-15：对于上例， F=CT,CSG,HTR,HRC,CHR,HSR,KEYHS 所以 = CT,CSG,HRT,CH

42、R,HSR,定理6-11：设是由结果为3NF的依赖保持分解算法得到的3NF分解，X为R的一个候选关键字，则X是R的一个分解，且中的所有关系模式均满足3NF,同时，既具有连接不失真性，又具有依赖保持性。,3）结果为3NF且具有依赖保持和连接不失真的分解,例：已知R(C,T,H,R,S,G), F=CT,HRC,CSG,HSR,HTR，KEY=HS， 则 = CT,CSG,HRT,CHR,HSR,HS 但HS HSR，故 =CT，CSG，HRT，CHR，HSR,6.6 多值函数依赖与4NF,6.6.1 BCNF关系模式存在的问题(CTB是关键字),6.6.2 多值函数依赖,为了形式地定义多值依赖，

43、根据上例，构造一个抽象关系R(U)（如下表），并设X,Y是U的子集，其余属性为Z=UXY。又设s、t、u、v是该关系中的任意元组。,定义6-23：设有R(U),X,Y是U的子集，Z=UXY。多值依赖XY成立，当且仅当对R的任一具体关系r，给定一对(X,Z)值，有一组Y值与之对应，且这种对应关系与Z值无关。,1）多值依赖的独立推理规则,(1) MVD0：多值互补性或对称性(Complementation) XY，则XUXY,(2) MVD1:多值依赖自反性(Reflexivity) Y X U，则XY,(3) MVD2：多值依赖增广性(Augmentation) XY，且V W，则WXVY,(4

44、) MVD3：多值依赖传递性(Transitivity) XY，且YZ，则XZY,2）多值依赖的其他推理规则,(1) MVD4：伪传递性 XY，且WYZ，则XWZWY,(2) MVD5：多值依赖的合并规则 XY，且XZ，则XYZ,(3) MVD6：多值依赖的分解或投影规则 XY，且 XZ，则XYZ，XYZ，XZY,6.6.3 4NF,从上面的例子可以看到，一个存在多值依赖的关系模式，其数据冗余量特别大，而且还有其他异常现象。 如果把上面的关系TEACH分解成两个关系C_T和C_B，如下表。,把关系分解成仅含平凡多值依赖的多个关系,定义一个其条件比BCNF更苛刻的范式，即4NF。一个满足4NF的关系模式的特点是： 该关系模式满足BCNF； 该关系模式只允许出现平凡多值依赖。,定义6.19（4NF）:关系模式R(U)lNF,若XY(YX)是非平凡的多值