关系模式的规范化理论

《关系模式的规范化理论》由会员分享，可在线阅读，更多相关《关系模式的规范化理论（61页珍藏版）》请在装配图网上搜索。

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

2、F、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）为例来说明该模式存在的问题。下表是其一个实例。S#SNSDSACCNPCG0001张华张华计算机计算机1717C101C101离散数学离散数学C110C1105 50001张华张华计算机计算机1717

3、C102C102数据结构数据结构C101C1015 50001张华张华计算机计算机1717C105C105数据库原理数据库原理C102C1023 30002李明李明信息管理信息管理1919C103C103操作系统操作系统C102C1023 30002李明李明信息管理信息管理1919C105C105数据库原理数据库原理C102C1023 30003刘强刘强计算机计算机1818C107C107汇编语言汇编语言C110C1104 4（1）冗余度大（2）操作异常由于数据的冗余，在对数据操作时会引起各种异常：插入异常删除异常修改异常关系模式的分解我们采用分解的方法，将上述S_C_G分解成以下三个模式：S

4、（S，SN，SD，SA）C（C，CN，PC）S_C（S，C，G）关系关系SS#SNSDSA0001张华张华计算机计算机17170002李明李明信息管理信息管理19190003刘强刘强计算机计算机1818关系关系CCCNPCC101C101离散数学离散数学C110C110C102C102数据结构数据结构C101C101C103C103操作系统操作系统C102C102C105C105数据库原理数据库原理C102C102C107C107汇编语言汇编语言C110C110关系关系S_CS#CG0001C101C1015 50001C102C1025 50001C105C1053 30002C103C10

5、33 30002C105C1053 30003C107C1074 46.2 函数依赖 1）函数依赖(Functional Dependency，简称FD)在上述的关系模式S（S，SN，SD，SA）中，存在以下函数依赖：S#SDSSNSSA（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）几种类型的函数依赖 例如X,XX,XZX等都是平凡函数依赖。定义6.2（非平凡函数依赖、平

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

7、函数依赖中，DT并不直接依赖于S#，是通过中间属性SD间接依赖于S#。这就是传递函数依赖。定义6.4（传递函数依赖）：设X、Y、Z是关系模式R(U)中的不同的属性集，如果XY，YX，YZ，则称Z传递依赖于X，否则，称为非传递函数依赖。3）关系的关健字和超关键字 一个包含了关键字的属性集合也能够函数决定（但不是完全函数决定，而是部分决定）属性全集，我们把这种包含了关键字的属性集合称为超关键字(Super Key)。例如，在上例的S（S，SN，SD，SA）、C（C,CN,PC）、S_C（S，C，G）三个关系模式中，存在以下关键字：)SA,SD,SN,#S(#Sf)#PC,CN,#C(#CfG)#C

8、,#S(f)SA,SD,SN,#S()SN,#S(p)SA,SD,SN,#S()SD,#S(p 所以，S#、C#和（S#，C#）分别是关系模式S、C和S_C的关键字。所以，(S#，SN)和(S#，SD)都不是关键字，而是超关键字。定义6.5（关键字）:在关系模式R(U)中，若K U，且满足 ，则称K为R的关键字。UKf 6.3 函数依赖的公理系统 6.3.1 函数依赖的逻辑蕴涵 6.3.2 Armstrong公理系统 6.3.3 函数依赖集的等价与覆盖6.3.1 函数依赖的逻辑蕴涵 例如在上述的传递函数依赖中，由XY，YZ，推导出XZ，这可以表示为：XY，YZ XZ 其中:表示逻辑蕴涵。一般地

9、讲，函数依赖的逻辑蕴涵定义如下：定义6.6（逻辑蕴涵）：设F是由关系模式R(U)满足的一个函数依赖集，XY是R的一个函数依赖，且不包含在F，如果满足F中所有函数依赖的任一具体关系r，也满足XY，则称函数依赖集F逻辑地蕴涵函数依赖XY，或称XY可从F推出。可表示为：FXY函数依赖集F的闭包F+定义6.7：函数依赖集F所逻辑蕴涵的函数依赖的全体称为为F的闭包（Closure），记为F+，即F+XYFXY例如，有关系R（X，Y，Z），它的函数依赖集FXY，YZ，则其闭包F+为：YZYZXYZXYZXYZXZXYZXYXYZXZYZYZXYZYZXZYZXYYZXYYZXZXYZXZXZXZXYXZX

10、YZXYXYZXYXZXYXYXYXYZYZXYZZXZZXYZXZYYXYZYXZYXYYXZZYYXXYZXXZXXYXXZYXYZXZXYXF6.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）A1：自反律(Reflexivity)如果Y X，则XY成立，这是一个平凡函数依赖。根据A1可以推出X、UX等

11、平凡函数依赖（因为 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 （给定条件）由上可得XZ（A3传递律）推论2：分解规则(The Decomposition Rule)如果XY，Z Y，则XZ成立一个重要定理 例6.2：设有关系模式R(A,

12、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=A1，A2，,An,X是U的子集,F是U上的一个函数依赖集，则属性集X关于函数依赖集F的闭包 定义为：AiAiU，且XAi可用阿氏公理从F推出例：设关系模式R(A,B,C)的函数依赖

13、集为F=AB,BC，分别求A、B、C的闭包。FXFX解：若XA，AB,BC（给定条件）AC （A2传递律）AA （A1自反律）=A，B，C （据定义）FA若X=B BB （A1自反律）BC （给定条件）=B，C （据定义）FB 若X=C，CC （自反律）=C（据定义）FC定理定理6.2:设F是关系模式R(U)上的函数依赖集,U是属性全集，X,Y U,则函数依赖XY是用阿氏公理从F推出的，充分必要条件是Y ；反之，能用阿氏公理从F推出的所有XY的Y都在 中。FXFX这个定理告诉我们，只要Y ，则必有XY。于是，一个函数依赖XY能否用阿氏公理从F推出的问题，就变成判断Y是否为 子集的问题。下面介绍

14、一下计算 的算法。FXFXFX属性集的闭包计算方法：根据下列步骤计算一系列属性集合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(i)，结束。)WAXVFWV)W)(V(|AB)i(FX算法6.1：求属性集X(X U)关于U上的函数依赖集F的闭包。输入：属性全集U,U上的函数依赖集F,以及属性集X U。输出：X关于F的闭包 。FXFX算法

15、6.1的求解过程 例：设FAHC，CA，EHC，CHD，DEG，CGDH，CEAG，ACDH，令XDH，求 。FX最后，(DH)+=ACDEGH。FX解：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=C，则X(2)X(1)B=CDEGH。判断是否X(i+1)=X(i)，显然X(2)X(1)。在F中找所有满足条件V X(2)=CDEGH的函数依赖VW，结果为CA，CHD，CG

16、DH，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)中未出现过的属性。（4）在F中再也找不到满足条件V X(i)的函数依赖VW。6.3.3 函数依赖集的等价和覆盖 定义6.9（函数依赖集的等价、覆盖）：设F和G是关系R（U）上的两个依赖集，若F+=G+，则称F与G等价，记为

17、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+。GXGX引理6.1：设G是一个函数依赖集，且其中所有依赖的右部都只有一个属性，则G覆盖任一左部与G（左部）相同的函数依赖集。一个函数依赖集F可能有若干个与其等价的函数依赖集，我们可以从中选择一个较好以便应用的函数依赖集。标准至少是：所有函数

18、依赖均独立，即该函数依赖集中不存在这样的函数依赖，它可由这个集合中的别的函数依赖推导出来。表示最简单，即每个函数依赖的右部为单个属性，左部最简单。证明：构造GXAXYF且AY由AY，XYF根据分解规则导出，从而等到G F+。反之，如果YA1A2An，而且XA1，XA2，XAn在G中可根据合并律等到F G+。由此可见，F与G等价，即F被G覆盖。最小函数依赖集 定义6.10（最小函数依赖集）:函数依赖集F如果满足下列条件，则称F为最小函数覆盖，记为Fmin：(1)F中每一个函数依赖的右部都是单个属性。(2)对F中任一函数依赖XA，FXA都不与F等价。(3)对于F中的任一函数依赖XA,FXAZA都不

19、与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 时，即以XBi替换X。GXFi)BX(最小覆盖的求解事例例6.5：求下列函数依赖集的最小覆盖：FAHC，CA，CHD，CEG，EHC，CGDH，CEAG，ACDH。解：解：(1)用分解规则将用分解规则将F中的所有依赖的右部变成单个属性，可以得到以下中的所有依赖的右部变成

20、单个属性，可以得到以下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)用所含属性较少的依赖代替所含属性较多的依赖。用所含属性较少的依赖代替所含属性较多的依赖。由于由于CA,ACDH中中A是冗余属性

21、，因此，可用是冗余属性，因此，可用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,DNAMED

22、ADDR）定义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上的投影，即 n1iiUU|iiUXYFYXYXFjiUU（1）连接不失真问题（a a）原关系）原关系R RSNOSNAMEDNAMEDADDR0001张华张华计算机计算机D1D10002李明李明信息管理信息管理D2D20003刘强刘强计算机计算机D1D1（b b）方法）方法1 1：关系：关系R1SNOSNAME0001张华张华0002李明李明0003

23、刘强刘强（c c）方法）方法1 1：关系：关系R2DNAMEDADDR计算机计算机D1D1信息管理信息管理D2D2（d d）方法）方法1 1：关系：关系R1R2SNOSNAMEDNAMEDADDR0001张华张华计算机计算机D1D10001张华张华信息管理信息管理D2D20002李明李明计算机计算机D1D10002李明李明信息管理信息管理D2D20003刘强刘强计算机计算机D1D10003刘强刘强信息管理信息管理D2D2方法2：假设按下列方法对R进行分解=R1(SNO,SNAME,DNAME,SNOSNAME,SNODNAME),R2（DNAME,DADDR），DNAMEDADDR）（a a）

24、原关系）原关系R RSNOSNAMEDNAMEDADDR0001张华张华计算机计算机D1D10002李明李明信息管理信息管理D2D20003刘强刘强计算机计算机D1D1（e e）方法）方法2 2：关系：关系R1（f f）方法）方法2 2：关系：关系R2DNAMEDADDR计算机计算机D1D1信息管理信息管理D2D2SNOSNAMEDNAME0001张华张华计算机计算机0002李明李明信息管理信息管理0003刘强刘强计算机计算机（g g）方法）方法2 2：R1R2 SNOSNAMEDNAMEDADDR0001张华张华计算机计算机D1D10002李明李明信息管理信息管理D2D20003刘强刘强计算

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

26、ADDR F+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR (F1F2)+SNOSNAME,SNODNAME,DNAMEDADDR,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的是连接不失真分解或称无损连接分解。k21RRR)r()r()r(r对于关系模式R关于F的无损连接条件是：任何满足F的关系r有r=m

27、(r)。ik21Rk1iRRR)r()r()r()r()r(mr 和m(r)之间的联系定理6.4：设R是一关系模式，=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)是关系模式R的一个分解，r是R的任一关系，（1ik）,那么有：；如果s=m(r)，则 ，或 mm(r)=m(r)r(mriRr)s(iiiUU)r()s(定理6.4证明 由定理由定理6-5可知可知 ，可得到，可得到 ，即，即 （因为（因为s=m(r)）（也就是两边同时在）（也就是两边同时在Ui上投影，得上投影，得 ）。）。为了证明为了证明 。假设。假设 ，则，则s中必存在满足中必存在满足tRi=ti的元组的元组t。由于由

28、于ts,对每个对每个j,在在rj中必存在元组中必存在元组uj满足满足tRj=uj(1jk),即即 。于是对那个特定的于是对那个特定的i，亦有，亦有tRi=ui，即，即tRiri。但。但tRi=ti，所以，所以tiri，从而，从而得到得到 （即（即 ）。）。由由 和和 可得可得 （即（即 ）。）。iRi)s(t)r(mriiiRRR)s()r(m()r(jRjjrru)(iRi)s(riRr)s(iiRi)s(riRr)s(iiRr)s(iiiUUrs)()(iiUU)r()s(iRr)s(iiiUU)s()r(由定理由定理6-5可知可知 (i=1,2,k)，于是有，于是有 。此式左式此式左式m

29、(s)=mm(r)（由（由得），右式得），右式 m(r)，因此得：因此得：mm(r)=m(r)该定理该定理说明，关系模式只有在第一次分解的连接恢复后有可能丢失信息，此说明，关系模式只有在第一次分解的连接恢复后有可能丢失信息，此后的多次分解恢复均能使分解不失真后的多次分解恢复均能使分解不失真iRk1i)r(iRr)s(iik1iRk1ir)s(i证明：证明：设任意一个元组设任意一个元组tr,ti=tUi(i=1,2,k);则则tiRi。根据自然连接。根据自然连接定义，可知定义，可知t在在 中，即中，即tm(r)，所以，所以 。该定理该定理说明，一个关系模式经分解再连接恢复所得的新关系说明，一个关

30、系模式经分解再连接恢复所得的新关系m(r)的元的元组一般比原关系的元组要多，而且组一般比原关系的元组要多，而且m(r)一定包括原关系的元组。一定包括原关系的元组。只有当只有当r=m(r)时，分解才是连接不失真分解。时，分解才是连接不失真分解。)r(mriRk1i)r(2）无损连接的检验 方法1：采用检验表格构造法算法6.2：连接不失真检验方法 1：(1)构造一个n列k行表，每一行对应于一个模式Ri（1ik），每一列对应于一个属性Aj（1jn），如下表所示。A1A2AnR1 R2 Rk (2)初始表（填表）：若AjRi，则第i行第j列上填入aj，否则填入bij。(3)修改表：反复检查F中的每一个

31、函数依赖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)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)是否无损分解？是否无损分解？根据算法根据算法

32、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所在的第所在的第

33、3列第列第3、4、5行的行的b13、a3、b13均均修改成修改成a3，其结果如表（，其结果如表（d）所示。）所示。(因为因为BC,AC,CD)再考虑再考虑CEA，根据修改原则，将，根据修改原则，将A所在的第所在的第1列第列第3、4、5行的行的b31（由（由BC推出）、推出）、b41（由（由AC推出）、推出）、a1均修改成均修改成a1，其结果如表（，其结果如表（e）所示。）所示。表表(a)初始表格初始表格 ABCDER1:ADa1b12b13a4b15R2:ABa1a2b23b24b25R3:BEb31a2b33b34a5R4:CDEb41b42a3a4a5R5:AEa1b52b53b54a5表

34、表(b)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13b24b25R3:BEb31a2b13b34a5R4:CDEb41b42a3a4a5R5:AEa1b52b13b54a5表表(c)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEb31a2b13a4a5R4:CDEb41b42a3a4a5R5:AEa1b52b13a4a5表表(d)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEb31a2a3a4a5R4:CDEb41b42a3a4a5R5:AEa1b52a3a4a5表表(e)ABCD

35、ER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEa1a2a3a4a5R4:CDEa1b42a3a4a5R5:AEa1b52a3a4a5简单的检验方法方法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，所以该分解具有连接不失真性。定理

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

37、(Fk1iRi判断两个函数依赖集是否等价的方法也可以用来判断一个分解是否保持依赖。下面以一个例子来说明一下。：设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=CR1R2R1R2=ABF但FAB,CB，F1F2AB,AC,即F+(F1F2)+可见具有连接不失真性，但不具有依

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

39、NF）定义6.14（1NF）：如果一个关系模式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存在异常现象，

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

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

42、分必要条件是，它的每个非主属性既不部分依赖也不传递依赖于候选关键字。4）Boyce-Codd范式（BCNF)例如，模式S(NAME,SEX,BIRTH,ADDR,DNAME)的主属性为：NAME,SEX,BIRTH和ADDR，候选关键字为：(NAME,SEX)、(N A M E,B I RT H)以 及(N A M E，A D D R)。定 义 中 的 A 为(ADDR,DNAME)。显然有：定义6.17（BCNF）：设有关系模式R及其函数依赖集F,X和A是R的属性集合，且AX。如果只要R满足XA，X就必包含R的一个候选关键字，则称R满足BCNF，记为RBCNF。该定义主要有三点：(1)所有非

43、主属性A对键都是完全函数依赖的(R2NF)。(2)没有属性完全函数依赖于非键的任何属性组(R3NF)。(3)所有主属性对不包含它的键是完全函数依赖的（新增加条件）。ADDRSEX)(NAME,fADDRBIRTH)(NAME,f事例 解解由语义可得到如下的函数依赖：（SNO，CNO）TNO，（SNO，TNO）CNO，TNOCNO这里（SNO，CNO），（SNO，TNO）都是侯选关键字。因为没有任何非主属性对侯选关键字部分依赖，所以STC2NF。没有任何非主属性对侯选关键字传递依赖，所以STC3NF。但在F中有TNOCNO，而TNO不包含侯选关键字，所以STC不是BCNF关系 例6.13：关系模

44、式STC（SNO，TNO，CNO），SNO表示学号，TNO表示教师编号，CNO表示课程号。每一个教师只教一门课，每门课有若干教师，某一个学生选定某门课，就对应一个固定教师。试判断ST的最高范式。这里我们可以将STC（SNO，TNO，CNO）分解成ST（SNO，TNO）和TC（TNO，CNO），它们都是BCNF。范式之间的关系 1NF3NFBCNF2NF消去非主属性对键的部分函数依赖消去非主属性对键的部分函数依赖消去非主属性对键的传递函数依赖消去非主属性对键的传递函数依赖消去主属性对键的部分函数依赖消去主属性对键的部分函数依赖6.5.2 模式分解的算法 按照上面讨论的模式分解理论，一个模式分解必

45、须满足：连接不失真性；依赖保持性某一级范式。但事实上不能顺利地同时满足上述三个条件。一般而言：(1)若要求连接不失真，分解可达到BCNF；(2)若要求依赖保持，则分解可达到3NF，但不一定能达到BCNF。(3)若同时要求连接不失真和依赖保持，则分解可达到3NF，但不一定能达到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

46、，,Ri1,S1,S2,Sm，Ri+1，Rk则这一分解相对于F的一个连接不失真性分解。(2)设2=R1，R2，,Rk,Rk+1，Rn为R的一个分解，其中包含了的那些关系模式,则2相对于F的一个连接不失真性分解。结果为BCNF的连接不失真分解算法 输入：R(U，F)输出：分解=R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk)，且，满足BCNF。方法：反复应用定理610（分解定理），逐步分解关系模式R，使每次分解具有连接不失真性，并且分解出来的模式是BCNF。置初值=R；如果中所有关系模式都是BCNF，则转；如果中有一个关系模式S不是BCNF，则S中必能找到一个函数依赖XA有X不是S的键

47、，且AX，设S1XA，S2SA，用分解S1，S2代替S，则转；分解结束，输出。事例 例例6.14：设有关系模式：设有关系模式CTHRSG(C,T,H,R,S,G)及其函数依赖集及其函数依赖集F=CSG,CT,HRC,HSR,THR。(1)求所有候选关键字求所有候选关键字如果直接根据候选关键字的定义来求一个关系模式的所有关键字：如果直接根据候选关键字的定义来求一个关系模式的所有关键字：若属性若属性A仅出现在所有函数依赖的右部，则它一定不包含在任何仅出现在所有函数依赖的右部，则它一定不包含在任何候选关键字中；候选关键字中；若属性若属性A仅出现在所有函数依赖的左部，则它一定包含在某个候仅出现在所有函

48、数依赖的左部，则它一定包含在某个候选关键字中；选关键字中；若属性若属性A既出现在函数依赖的右部，又出现在左部，则它可能包既出现在函数依赖的右部，又出现在左部，则它可能包含在候选关键字中；含在候选关键字中；在上述基础上求属性集闭包。在上述基础上求属性集闭包。对本例对本例,G仅出现在函数依赖的右部，则它不包含在候选关键字中；仅出现在函数依赖的右部，则它不包含在候选关键字中；又属性又属性H和和S仅出现在函数依赖的左部，则仅出现在函数依赖的左部，则H和和S必包含在候选关键字中。必包含在候选关键字中。计算计算(HS)+为：为：(HS)(0)=HS (HS)(1)=HSR (HS)(2)=HSRC (HS

49、)(3)=CTHRSG (HS)(4)=CTHRSG即即(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很显然，模式很显

50、然，模式CSG是是BCNF。模式。模式CTHRS不是不是BCNF，还要继续分解。，还要继续分解。(2-1)求得求得CTHRS的候选关键字为的候选关键字为HS。(2-2)再分解再分解CTHRS，选，选CT，将，将CTHRS分解为分解为 CTHRSCT,CHRS。函数依赖集函数依赖集CT上投影的最小覆盖是上投影的最小覆盖是CT，在，在CHRS上的投影的最小覆盖是上的投影的最小覆盖是CHR，HSR，HRC。记作：。记作：CT(F1)=CT；CHRS(F1)=CHR，HSR，HRCF2显然显然,模式模式CT为为BCNF，但模式，但模式CHRS不是不是BCNF，还要继续分解。，还要继续分解。(2-3)求

51、得求得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。分解树 CTHRSGkey=HS CSG CTHRC HSRTHRCTHRSkey=HS CT HRC HSR THRCSGkey=CS CSGCTkey=C CT

52、CHRkey=CH,HRCHRHRCCHRSkey=HS CHR HRC HSRCHSkey=HSHSC 2）结果为3NF的依赖保持分解 算法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：对于

53、上例，F=CT,CSG,HTR,HRC,CHR,HSR,KEYHS 所以 =CT,CSG,HRT,CHR,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，HSR6.6 多值函数依赖与4NF 6.6.1 BCNF

54、关系模式存在的问题(CTB是关键字)CTB高等数学高等数学张华民张华民高等数学高等数学高等数学高等数学张华民张华民高等数学教程高等数学教程高等数学高等数学王天华王天华高等数学高等数学高等数学高等数学王天华王天华高等数学教程高等数学教程高等数学高等数学林静林静高等数学高等数学高等数学高等数学林静林静高等数学教程高等数学教程普通物理普通物理吴刚吴刚物理学物理学普通物理普通物理吴刚吴刚普通物理普通物理普通物理普通物理吴刚吴刚普通物理基础普通物理基础普通物理普通物理李晓芳李晓芳物理学物理学普通物理普通物理李晓芳李晓芳普通物理普通物理普通物理普通物理李晓芳李晓芳普通物理基础普通物理基础6.6.2 多值函

55、数依赖为了形式地定义多值依赖，根据上例，构造一个抽象关系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值无关。R（U）XYUXYssXsYsUXYttXtYtUXYuuX=sXuY=sYuUXY=tUXYvvX=tXvY=tYvUXY=sUXY1）多值依赖的独立推理规则(1)MVD0：多值互补性或对称性(Complementation)XY，则XUXY(2)MVD1:多值依

56、赖自反性(Reflexivity)Y X U，则XY(3)MVD2：多值依赖增广性(Augmentation)XY，且V W，则WXVY(4)MVD3：多值依赖传递性(Transitivity)XY，且YZ，则XZY2）多值依赖的其他推理规则(1)MVD4：伪传递性 XY，且WYZ，则XWZWY(2)MVD5：多值依赖的合并规则 XY，且XZ，则XYZ(3)MVD6：多值依赖的分解或投影规则 XY，且 XZ，则XYZ，XYZ，XZY6.6.3 4NF 从上面的例子可以看到，一个存在多值依赖的关系模式，其数据冗余量特别大，而且还有其他异常现象。如果把上面的关系TEACH分解成两个关系C_T和C_

57、B，如下表。(a)C_T关系关系CT高等数学高等数学张华民张华民高等数学高等数学王天华王天华高等数学高等数学林静林静普通物理普通物理吴刚吴刚普通物理普通物理李晓芳李晓芳(b)C_B关系关系CB高等数学高等数学高等数学高等数学高等数学高等数学高等数学教程高等数学教程普通物理普通物理物理学物理学普通物理普通物理普通物理普通物理普通物理普通物理普通物理基础普通物理基础把关系分解成仅含平凡多值依赖的多个关系,定义一个其条件比BCNF更苛刻的范式，即4NF。一个满足4NF的关系模式的特点是：该关系模式满足BCNF；该关系模式只允许出现平凡多值依赖。定义6.19（4NF）:关系模式R(U)lNF,若XY(

58、YX)是非平凡的多值依赖，且X包含关键字，（或只出现平凡多值依赖，不存在非平凡多值依赖），则称R(U)满足第四范式，记为R4NF。将TEACH分解后产生的C_T(C,T)和C_B(C,B)，显然因为有CT和CB，故不存在非平凡多值依赖，从而有C_T4NF和C_B4NF上例中的关系模式TEACH为例，虽然是BCNF，但不是4NF，因为在TEACH(C,T,B)中有:CT和CB，关键字是CTB。虽然TEACHBCNF，但C不是关键字，即TEACH 4NF。本章小结 本章讨论如何设计关系模式问题。关系模式设计得好与坏，直接影响到数据冗余度、数据一致性等问题。要设计好的数据库模式，必须有一定的理论为基

59、础。这就是模式规范化理论。在数据库中，数据冗余是指同一个数据存储了多次，由数据冗余将会引起各种操作异常。通过把模式分解成若干比较小的关系模式可以消除冗余。函数依赖XY是数据之间最基本的一种联系，在关系中有两个元组，如果X值相等那么要求Y值也相等。FD有一个完备的推理规则集。关系模式在分解时应保持“等价”，有数据等价和语义等价两种，分别用无损分解和保持依赖两个特征来衡量。前者能保持泛关系在投影联接以后仍能恢复回来，而后者能保证数据在投影或联接中其语义不会发生变化，也就是不会违反FD的语义。但无损分解与保持依赖两者之间没有必然的联系。本章小结（续）（续）范式是衡量模式优劣的标准，范式表达了模式中数据依赖之间应满足的联系。如果关系模式R是3NF，那么R上成立的非平凡FD都应该左边是超键或右边是非主属性。如果关系模式R是BCNF，那么R上成立的非平凡的FD都应该左边是超键。范式的级别越高，其数据冗余和操作异常现象就越少。分解成BCNF模式集的算法能保持无损分解，但不一定能保持FD集。而分解成3NF模式集的算法既能保持无损分解，又能保持FD集。关系模式的规范化过程实际上是一个“分解”过程：把逻辑上独立的信息放在独立的关系模式中。分解是解决数据冗余的主要方法，也是规范化的一条原则：“关系模式有冗余问题就分解它”。