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

《第6章 关系模式的规范化理论.ppt》由会员分享，可在线阅读，更多相关《第6章 关系模式的规范化理论.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章 关系模式的规范化理论 本章主要内容关系数据库的规范化设计是指面对一个现实问题，如何选择一个比较好的关系模式集合。规范化设计理论对关系数据库结构的设计起着重要的作用。本章主要内容(1)关系模式的冗余及相关的异常问题。(插入、删除、更新异常)(2)函数依赖(FD)的定义、(非)平凡函数依赖、完全(部分)函数依赖、（非）传递函数依赖。(3)关系模式的范式的概念：1NF，2NF，3NF，BCNF。（理解概念并能够判断一个关系模式的范式级别）关系模式的规范化理论 6.1关系模式设计中的问题6.2函数依赖6.3函数依赖的公理系统6.4关系模式的分解及其问题6.5关系模式的规范化6.6多值函数依赖与

2、4NF本章小结6.1关系模式设计中的问题假设需要设计一个学生学习情况数据库StuDB。下面我们以模式S_C_G（S#，SN，SD，SA，C，CN，G，PC）为例来说明该模式存在的问题。下表是其一个实例。S#SNSDSACCNPCG0001张华张华计算机计算机1717C101C101离散数学离散数学C110C1105 50001张华张华计算机计算机1717C102C102数据结构数据结构C101C1015 50001张华张华计算机计算机1717C105C105数据库原理数据库原理C102C1023 30002李明李明信息管理信息管理1919C103C103操作系统操作系统C102C1023 30

3、002李明李明信息管理信息管理1919C105C105数据库原理数据库原理C102C1023 30003刘强刘强计算机计算机1818C107C107汇编语言汇编语言C110C1104 4（1）冗余度大：同样的数据被多次重复存储。（2）操作异常由于数据的冗余，在对数据操作时会引起多种异常：插入异常:应该能插入的数据，但无法插入删除异常：不该被删除的数据，却被删掉修改异常：修改数据，很困难，容易造成遗漏或出错。关系模式的分解我们采用分解的方法，将上述S_C_G分解成以下三个模式：S（S，SN，SD，SA）C（C，CN，PC）S_C（S，C，G）(让每个模式表达单一的概念信息)关系关系SS#SNSD

4、SA0001张华张华计算机计算机17170002李明李明信息管理信息管理19190003刘强刘强计算机计算机1818关系关系CCCNPCC101C101离散数学离散数学C110C110C102C102数据结构数据结构C101C101C103C103操作系统操作系统C102C102C105C105数据库原理数据库原理C102C102C107C107汇编语言汇编语言C110C110关系关系S_CS#CG0001C101C1015 50001C102C1025 50001C105C1053 30002C103C1033 30002C105C1053 30003C107C1074 4 这三个模式，冗余

5、度小，也消除了各类异常6.2函数依赖1）函数依赖(FunctionalDependency，简称FD)在上述的关系模式S和SC，存在以下函数依赖：S#SDSSNSSA（S,C）G定义6.1（函数依赖）：设有关系模式R(U)，其中U=A1，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（非平凡函数依赖、平凡函数依赖）：一个函数依赖XY如果满足Y X，则称此函数依赖为非平凡

6、函数依赖，否则称为平凡函数依赖。定义6.3（完全函数依赖、部分函数依赖）：设X、Y是关系R的不不同同属性集，若XY（Y函数依赖于X），且且不不存存在在X X，使使XY，则称Y完全函数依赖于X，记为 ；否则称Y部分函数依赖于X，记为 。例如，在上例关系S中,是完全函数依赖;、是部分函数依赖。几种类型的函数依赖在属性Y与X之间，除了完全函数依赖和部分函数依赖关系等直接函数依赖，还存在间接函数依赖关系。如果在关系S中增加系的电话号码DT，从而有S#SD,SDDT，于是S#DT。在这个函数依赖中，DT并不直接依赖于S#，是通过中间属性SD间接依赖于S#。这就是传递函数依赖。定义6.4（传递函数依赖）：

7、设X、Y、Z是关系模式R(U)中的不同的属性集，如果XY，YX，YZ，则称Z传递依赖于X，否则，称为非传递函数依赖。3）关系的关健字和超关键字一个包含了关键字的属性集合也能够函数决定（但不是完全函数决定，而是部分决定）属性全集，我们把这种包含了关键字的属性集合称为超关键字(SuperKey)。例如，在上例的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（关键字）:在关系模式R(U)中，若KU，且满

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

9、辑蕴涵的函数依赖的全体称为为F的闭包（Closure），记为F+，即F+XYFXY例如，有关系R（X，Y，Z），它的函数依赖集FXY，YZ，则其闭包F+为：6.3.2Armstrong公理系统1）独立推理规则即下面给出的Armstrong公理的三条推理规则是彼此独立的。（3）A3：传递律(Transitivity)如果XY且YZ，则XZ成立。（2）A2：增广律(Augmentation)如果XY，且ZW，则XWYZ成立。根据A2可以推出XWY、XZYZ或XWYW、XXY、XYX等。（1）A1：自反律(Reflexivity)如果Y X，则XY成立，这是一个平凡函数依赖。根据A1可以推出X、UX

10、等平凡函数依赖（因为XU）。2）其他推理规则推论1：合并规则(TheUnionRule)XY，XZXYZ推论3：伪传递规则(ThePseudoTransitivityRule)XY，WYZXWZ证：（1）XYXXY（A2增广律）XZXYYZ（A2增广律）由上可得XYZ（A3传递律）（3）XYWXWY（A2增广律）WYZ（给定条件）由上可得XWZ（A3传递律）（2）Z YYZ（A1自反律）XY（给定条件）由上可得XZ（A3传递律）推论2：分解规则(TheDecompositionRule)如果XY，ZY，则XZ成立一个重要定理例 6.2：设 有 关 系 模 式 R(A,B,C,D,E)及 其 上

11、 的 函 数 依 赖 集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)的函数依赖集为F=AB,BC，分别求A

12、、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 ；反之，能用阿氏公理从F推出的所有XY的Y都在中。这个定理告诉我们，只要Y ，则必有XY。于是，一个函数依赖XY能否用阿氏公理从F推出的问题，就变成判断Y是否为子集的问题。下面介绍一下计算的算法。属性集的闭包计算方法：根据下列步骤计算一系列属性集合X(0)

13、，X(1)，(1)令X(0)=X，i0；(2)求属性集/*在F中寻找满足条件VX(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)，结束。算法6.1：求属性集X(XU)关于U上的函数依赖集F的闭包。输入：属性全集U,U上的函数依赖集F,以及属性集XU。输出：X关于F的闭包。算法6.1的求解过程例：设 F AHC，CA，EHC，CHD，DEG，CGDH，CEAG，ACDH，令XDH，求。最后，(DH)+=ACDEGH。解：X(0)

14、=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，CGDH，CEAG，则B=ADGH，于是X(3)X(2)B=CDEGHB=ACDEGH。判断是否X(i+1)=X(i)，这时虽然X(3)X(2)。但X(3)已经包含了全

15、部属性，所以不必再继续计算下去。属性集闭包计算结束判断方法在判断计算何时结束时，可用下面四种方法：（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等价，记为F=G。也可以称F覆盖G，或G覆盖F；也可说F与G相互覆盖。检查两个函数依赖集F和G是否等价的方法是：第一步：检查F中的每个函数依赖是否属于G+，若全部满足，则F G+

16、。如若有XYF,则计算,如果Y ,则XYG+;第二步：同第一步，检查是否G F+;第三步：如果F G+，且G F+，则F与G等价。由此可见,F和G等价的充分必要条件是：F G+，且G F+。引理6.1：设G是一个函数依赖集，且其中所有依赖的右部都只有一个属性，则G覆盖任一左部与G（左部）相同的函数依赖集。一个函数依赖集F可能有若干个与其等价的函数依赖集，我们可以从中选择一个较好以便应用的函数依赖集。标准至少是：所有函数依赖均独立，即该函数依赖集中不存在这样的函数依赖，它可由这个集合中的别的函数依赖推导出来。表示最简单，即每个函数依赖的右部为单个属性，左部最简单。证明：构造GXAXYF且AY由A

17、Y，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都不与F等价，其中Z为X的任一子集。求函数依赖集F的最小覆盖的方法是：(1)检查F中的每个函数依赖XA,若A=A1,A2,Ak,则根据分解规则，用XAi(i=1，

18、2，k)取代XA。(2)检查F中的每个函数依赖XA,令G=FXA，若有A，则从F中去掉此函数依赖。(3)检查F中各函数依赖XA，设X=B1,B2,Bm,检查Bi，当A时，即以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（由（由

19、CGDH分解得到）分解得到）CEA，CEG（由（由CEAG分解得到）分解得到）(2)根据阿氏公理去掉根据阿氏公理去掉F中的冗余依赖中的冗余依赖由由于于从从CA可可推推出出CEA，从从CA、CGD、ACDH推推出出CGH，因因此此CEA和和CGH是冗余，可从是冗余，可从F删除删除。(3)用所含属性较少的依赖代替所含属性较多的依赖。用所含属性较少的依赖代替所含属性较多的依赖。由由于于CA,ACDH中中A是是冗冗余余属属性性，因因此此，可可用用CDH代代替替ACDH，故故删除删除ACDH。最后得到最后得到F的最小覆盖为：的最小覆盖为：F AHC，CA，CHD，CDH，CE，CG，EHC，CGD，CE

20、G 6.4关系模式的分解及其问题6.4.1什么叫模式分解6.4.2分解的无损连接性6.4.3保持函数依赖性6.4.1什么叫模式分解例6.6：设在模式R(U,F)中USNO，SNAME，DNAME，DADDRFSNOSNAME，SNODNAME，DNAMEDADDR如果对R作如下分解（方法1）：=R1（SNO,SNAME,SNOSNAME），R2（DNAME，DADDR,DNAMEDADDR）定义6.11（模式分解）：关系模式R(U，F)的一个分解是若干个关系模式的一个集合：=R1(U1,F1),R2(U2,F2),Rn(Un,Fn)式中：(1)。(2)对每个i，j（1i,jn）有。(3)Fi(

21、i=1，2，,n)是F在Ui上的投影，即（1）连接不失真问题（a a）原关系）原关系R RSNOSNAMEDNAMEDADDR0001张华张华计算机计算机D1D10002李明李明信息管理信息管理D2D20003刘强刘强计算机计算机D1D1（b b）方法）方法1 1：关系：关系R1SNOSNAME0001张华张华0002李明李明0003刘强刘强（c c）方法）方法1 1：关系：关系R2DNAMEDADDR计算机计算机D1D1信息管理信息管理D2D2（d d）方法）方法1 1：关系：关系R1R2SNOSNAMEDNAMEDADDR0001张华张华计算机计算机D1D10001张华张华信息管理信息管理

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

23、ADDR计算机计算机D1D1信息管理信息管理D2D2SNOSNAMEDNAME0001张华张华计算机计算机0002李明李明信息管理信息管理0003刘强刘强计算机计算机（g g）方法）方法2 2：R1R2SNOSNAMEDNAMEDADDR0001张华张华计算机计算机D1D10002李明李明信息管理信息管理D2D20003刘强刘强计算机计算机D1D1（2）依赖保持问题上例方法1：FSNOSNAME，SNODNAME，DNAMEDADDRF1F2SNOSNAME，DNAMEDADDR F+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR(F1F2)+SNOSNAME，DN

24、AMEDADDR一个关系模式经分解后，其函数依赖集F也随之被分解，则分解后的依赖集Fi并集是否能保持原有的函数依赖关系？即?若出现，说明分解后有些函数依赖被丢失了。上例方法2：FSNOSNAME，SNODNAME，DNAMEDADDRF1F2SNOSNAME,SNODNAME,DNAMEDADDR F+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR(F1F2)+SNOSNAME,SNODNAME,DNAMEDADDR,SNODADDR 6.4.2分解的无损连接性1）无损连接分解的定义定义6.12（无损连接分解，即连接不失真分解）：设关系模式R（U，F）上 的 一 个

25、 分 解 为=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的任一关系，（1ik）,那么有：；如果s=m(r)，则，或mm(r)=m(r)定理6.4证明 由定理由定理6-5可知可知 ，可得到，可得到 ，即，即 （因为（因为s=m(r)）（也就是两边

26、同时在）（也就是两边同时在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)，

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

28、定包括原关系的元组。一定包括原关系的元组。只有当只有当r=m(r)时，分解才是连接不失真分解。时，分解才是连接不失真分解。2）无损连接的检验方法1：采用检验表格构造法算法6.2：连接不失真检验方法 1：(1)构造一个n列k行表，每一行对应于一个模式Ri（1ik），每一列对应于一个属性Aj（1jn），如下表所示。A1A2AnR1R2Rk(2)初始表（填表）：若AjRi，则第i行第j列上填入aj，否则填入bij。(3)修改表：反复检查F中的每一个函数依赖XY，按下方法修改表格中的元素：取F中的函数依赖XY，检查Y中的属性所对应的列，找出X相等的那些行，将这些X的符号相同的行中的Y的属性所对应的符号

29、改成一致。即如果其中有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)是否无损分解？是否无损分解？根据算法根据算法6.2中中(1)和和(2)构造初始表，如表构造初始表，如表(a)所示。所示。根根据据AC，对对表表(a)进进行行处处理理，将将b13、b23、b53改改成成

30、同同一一符符号号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，根根据据

31、修修改改原原则则，将将A所所在在的的第第1列列第第3、4、5行行的的b31（由由BC推出）、推出）、b41（由（由AC推出）、推出）、a1均修改成均修改成a1，其结果如表（，其结果如表（e）所示。）所示。表表(a)初始表格初始表格 ABCDER1:ADa1b12b13a4b15R2:ABa1a2b23b24b25R3:BEb31a2b33b34a5R4:CDEb41b42a3a4a5R5:AEa1b52b53b54a5表表(b)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13b24b25R3:BEb31a2b13b34a5R4:CDEb41b42a3a4a5R5:AEa1

32、b52b13b54a5表表(c)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEb31a2b13a4a5R4:CDEb41b42a3a4a5R5:AEa1b52b13a4a5表表(d)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEb31a2a3a4a5R4:CDEb41b42a3a4a5R5:AEa1b52a3a4a5表表(e)ABCDER1:ADa1b12b13a4b15R2:ABa1a2b13a4b25R3:BEa1a2a3a4a5R4:CDEa1b42a3a4a5R5:AEa1b52a3a4a5简单的检

33、验方法方法2：定理6.5：设=R1,R2是关系模式R的一个分解，F是R的一个函数依赖集，则对于F,具有连接不失真性的充分必要条件是R1R2R1R2F+，或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告诉我们一个事实：如果两个关系模式间的公共属性集至少包含其中一个关系模式的关键字，则此分解必定具有连接不失真性。6.4.3函数依赖保持性定义6.13：设有关系模式

34、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中的全部依赖，则称分解具有依赖保持性。判断两个函数依赖集是否等价的方法也可以用来判断一个分解是否保持依赖。下面以一个例子来说明一下。：设R(A,B,C,D)，FAB,CD，=R1(A,B，AB)，R2（C,D，CD）。因为FAB,CD，F1F2AB,

35、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)+可见具有连接不失真性，但不具有依赖保持性。范式的概念是由E.F.Codd在1970年首先提出来的。满足特定要求的模式称之为范式。所谓模式规范化，就是把关系模式规范到某一级范式,目的是：(1)消除异常现象。(2)方便用户使用，简化操作。(3)加强数据独立性。关系

36、规范化的条件可以分成几级，每一级称为一个范式，记为xNF，其中x表示级别,NF是范式(NormalForm)，即关系模式满足的条件。范式的级别越高，条件越严格，因此有：6.5关系模式的规范化6.5.1范式1）第一范式（1NF）定义6.14（1NF）：如果一个关系模式R的每个属性的域都只包含单纯值，而不是一些值的集合或元组，则称R是第一范式，记为R1NF,把一个非规范化关系模式变为1NF有两种方法，一是把不含单纯值的属性分解为多个属性，并使它们仅含单纯值。例如，设模式：P(PNO，PNAME，QOH,PJ(PJNO,PJNAME，PJMNO，PQC）将模式P变为：P(PNO,PNAME,QOH,

37、PJNO,PJNAME,PJMNO,PQC）第二种方法是把关系模式分解，并使每个关系都符合1NF。则：Pl(PNO,PNAME,QOH)PJl(PNO,PJNO,PJNAME,PJMNO,PQC)思考：PJNAME,PJMNO对(PNO,PJNO)函数依赖的类型？2）第二范式（2NF）定义6.15（2NF）：如果关系模式R1NF，且它的任一非主属性都完全函数依赖于任一候选关键字，则称R满足第二范式，记为R2NF。把一个1NF的关系模式变为2NF的方法是，通过模式分解，使任一非主属性都完全函数依赖于它的任一候选关键字。例如对上例，若把PJ1进一步分解成：PJ2(PNO,PJNO,PQC)J(PJ

38、NO,PJNAME,PJMNO)PJ2和J均达到2NF。（不存在非主属性对候选关键字的部分函数依赖。）3）第三范式（3NF）定义6.16（3NF）：如果关系模式R2NF,且每一个非主属性不传递依赖于任一候选关键字，则称R3NF。例如把关系模式S分解成：ST(SNO，SNAME，DNAME）DEPT(DNAME，DADDR)(都达到了3NF。)考察关系模式S(SNO，SNAME，DNAME，DADDR),SNO为候选关键字。但若假定一个系的学生的所在系地址相同，即一个系的学生的DADDR值一样。显然，SNODNAME,DNAMEDADDR，故SNODADDR,该关系模式在DADDR列存在高度数据

39、冗余。这是由于原关系模式中存在传递函数依赖。因此，要消除数据冗余这种异常现象，必须使关系模式中不出现传递函数依赖。3NF定义告诉我们，一个关系模式满足3NF的充分必要条件是，它的每个非主属性既不部分依赖也不传递依赖于候选关键字。4）Boyce-Codd范式（BCNF)定义6.17（BCNF）：设有关系模式R及其函数依赖集F,X和A是R的属性集合，且AX。如果有XA，X就必包含R的一个候选关键字，则称R满足BCNF，记为RBCNF。请同学分析：上述的S、C、SC达到了BCNF的要求了吗？关系模式R满足BCNF，则必满足3NF.但反之不成立。事例解解由语义可得到如下的函数依赖：（SNO，CNO）T

40、NO，（SNO，TNO）CNO，TNOCNO这里（SNO，CNO），（SNO，TNO）都是侯选关键字。因为没有任何非主属性对侯选关键字部分依赖，所以STC2NF。没有任何非主属性对侯选关键字传递依赖，所以STC3NF。(但存在主属性对键的部分函数依赖！)但在F中有TNOCNO，而TNO不包含侯选关键字，所以STC不是BCNF关系例6.13：关系模式STC（SNO，TNO，CNO），SNO表示学号，TNO表示教师编号，CNO表示课程号。假设:每一个教师只教一门课，每门课有若干教师。某一个学生选定某门课，就对应一个固定教师。试判断ST的最高范式。这里我们可以将STC（SNO，TNO，CNO）分解成

41、ST（SNO，TNO）和TC（TNO，CNO），它们都是BCNF。范式之间的关系1NF3NFBCNF2NF消去非主属性对键的部分函数依赖消去非主属性对键的部分函数依赖消去非主属性对键的传递函数依赖消去非主属性对键的传递函数依赖消去主属性对键的部分函数依赖消去主属性对键的部分函数依赖6.5.2模式分解的算法按照上面讨论的模式分解理论，一个模式分解必须满足：连接不失真性；依赖保持性某一级范式。但事实上不能顺利地同时满足上述三个条件。一般而言：(1)若要求连接不失真，分解可达到BCNF；(2)若要求依赖保持，则分解可达到3NF，但不一定能达到BCNF。(3)若同时要求连接不失真和依赖保持，则分解可达

42、到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，,Ri1,S1,S2,Sm，Ri+1，Rk则这一分解相对于F的一个连接不失真性分解。(2)设2=R1，R2，,Rk,Rk+1，Rn为R的一个分解，其中包含了的那些关系模式,则2相对于F的一个连接不失真性分解。结果为BCNF的连接不失真分解算法输入：R(

43、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)求所有候选关键字求所有

44、候选关键字如果直接根据候选关键字的定义来求一个关系模式的所有关键字：如果直接根据候选关键字的定义来求一个关系模式的所有关键字：若若属属性性A仅仅出出现现在在所所有有函函数数依依赖赖的的右右部部，则则它它一一定定不不包包含含在在任任何何候选关键字中；候选关键字中；若若属属性性A仅仅出出现现在在所所有有函函数数依依赖赖的的左左部部，则则它它一一定定包包含含在在某某个个候候选关键字中；选关键字中；若若属属性性A既既出出现现在在函函数数依依赖赖的的右右部部，又又出出现现在在左左部部，则则它它可可能能包包含在候选关键字中；含在候选关键字中；在上述基础上求属性集闭包。在上述基础上求属性集闭包。对对本本例例

45、,G仅仅出出现现在在函函数数依依赖赖的的右右部部，则则它它不不包包含含在在候候选选关关键键字字中中；又又属属性性H和和S仅仅出出现现在在函函数数依依赖赖的的左左部部，则则H和和S必必包包含含在在候候选选关关键键字字中中。计算计算(HS)+为：为：(HS)(0)=HS (HS)(1)=HSR (HS)(2)=HSRC (HS)(3)=CTHRSG (HS)(4)=CTHRSG即即(HS)+=CTHRSG，故，故HS是模式是模式CTHRSG的唯一关键字。的唯一关键字。(2)分解首首先先在在F中中找找出出这这样样一一个个函函数数依依赖赖XA，其其中中X不不包包含含R的的任任何何候候选选关关键键字字，

46、也不包含也不包含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。函函数数依依赖赖集集

47、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中

48、中，HC、HR为为键键，其其所所有有决决定定因因素素都都是是键键，在在模模式式CHS中中，HS为键，显然为键，显然CHR、CHS都为都为BCNF。分解树CTHRSGkey=HS CSG CTHRC HSRTHRCTHRSkey=HS CT HRC HSR THRCSGkey=CS CSGCTkey=C CTCHRkey=CH,HRCHRHRCCHRSkey=HS CHR HRC HSRCHSkey=HSHSC2）结果为3NF的依赖保持分解算法6-4：结果为3NF的依赖保持分解算法输入：关系模式R和函数依赖集F输出：结果为3NF的一个依赖保持分解步骤：(1)如果R中有某些属性与F的最小覆盖F中的

49、每个依赖的左边和右边都无关，原则上可由这些属性构成一个关系模式，并从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,CHR,HSR定理6-11：设是由结果为3NF的依赖保持分解算法得到的3NF分解，X为R的一个候选关键字，则X是R的一个分解，且中的所有关系模式均满足3NF,同时，既具有连接不失真性，又具有依赖保持性。3

50、）结果为3NF且具有依赖保持和连接不失真的分解例：已知R(C,T,H,R,S,G),F=CT,HRC,CSG,HSR,HTR，KEY=HS，则=CT,CSG,HRT,CHR,HSR,HS但HSHSR，故=CT，CSG，HRT，CHR，HSR6.6多值函数依赖与4NF6.6.1BCNF关系模式存在的问题(CTB是关键字)CTB高等数学高等数学张华民张华民高等数学高等数学高等数学高等数学张华民张华民高等数学教程高等数学教程高等数学高等数学王天华王天华高等数学高等数学高等数学高等数学王天华王天华高等数学教程高等数学教程高等数学高等数学林静林静高等数学高等数学高等数学高等数学林静林静高等数学教程高等数