关系数据理论 (2)精.ppt

《关系数据理论 (2)精.ppt》由会员分享，可在线阅读，更多相关《关系数据理论 (2)精.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关系数据理论(2)第1页，本讲稿共92页第五章规范化设计（8学时）第七章数据库设计（4学时）第八章 数据库的管理（8学时）第九章分布式数据库系统（4学时）第十章 对象关系数据库（4学时）习题分析、总复习（2学时）数据库原理二 数据库原理二 课堂教学（课堂教学（30 30学时 学时)内容及安排：内容及安排：第2页，本讲稿共92页实验五:编程实施学分制教务管理信息系统（12学时）(教材P.373)实验六：SQL Server 2000 高级技术使用（6学时）(教材P.303)验收：（2学时）数据库原理二 数据库原理二 实验内容和安排（实验内容和安排（20 20学时）学时）第3页，本讲稿共92页 第

2、五章 规范化设计本章讨论如何设计关系数据库的模式问题。关系数据库规范化设计理论即“模式设计理论”数据依赖研究数据之间的联系范式关系模式的标准模式设计方法规范化的方法第4页，本讲稿共92页 本章重要概念:关系模式的一般形式和关系模式的冗余和异常问题。数据依赖的定义、数据依赖与关键码的联系；平凡的FD。关系模式的范式：1NF，2NF，3NF，BCNF。逻辑蕴涵、闭包、数据依赖的公理系统和推理规则；属性集的闭包；FD集的等价；最小依赖集。无损分解的定义、性质、测试；保持依赖的分解定义。分解算法：分解成3NF、BCNF模式集的算法。MVD、4NF和5NF的定义。第5页，本讲稿共92页1概述一、关系模式

3、的一般形式:R第6页，本讲稿共92页R其中：U：为组成关系R的全部属性的集合，即UA1,A2,An。D：为域的集合，即属性的取值范围的集合。Dom：为U与D之间的映象，即Dom：U D|Dom安全约束集。F：为属性U上的一组约束，即数据依赖集。例如：学习关系SC中存在如下数据依赖：（SNO,CNO）GRADE学生关系S中存在如下数据依赖：SNO SNAME（SNO,SNAME）AGE第7页，本讲稿共92页关系模式一般形式可简化为：R 泛关系模式满足上述制约条件F的关系用符号r 表示r 表示的关系称为：泛关系例如:学习关系模式SC 其中:U=SNO,CNO,GRADE F=(SNO,CNO)GR

4、ADE 第8页，本讲稿共92页设计关系数据库的核心问题是关系模式的设计。对于一个数据库设计，可以有多个关系模式的选择。按照什么原则来选择关系模式？标准是什么？如何实现？第9页，本讲稿共92页二关系模式的存储异常问题在数据管理中,数据冗余一直是影响系统性能的大问题。数据冗余是指同一个数据在系统中多次重复出现。例：SPJ_A(SNO，PNO，JNO，JNAME，JCITY，PRICE，QTY)属性分别表示:供应商号、零件号、工程项目号、工程项目名称、工程项目所在城市、零件单价、供应数量。SPJ_A的一个实例：第10页，本讲稿共92页存在的问题：数据冗余修改异常 插入异常 删除异常关系模式 SPJ_

5、A 的一个实例：SPJ_A1关系SNO PNO JNO JNAME JCITY PRICE QTYS1 P1 J1 东方明珠 上海 22.60 80S1 P1 J4 明珠线 上海 22.60 60S1 P3 J1 东方明珠 上海 22.80 100S1 P3 J4 明珠线 上海 22.80 60S1 P3 J6 南浦大桥 上海 22.80 6S3 P3 J5 炼钢工地 天津 22.10 100S3 P4 J1 东方明珠 上海 11.90 30S3 P4 J4 明珠线 上海 11.90 60S3 P4 J6 南浦大桥 上海 11.90 6S4 P2 J4 明珠线 上海 33.80 60S4 P2

6、 J6 南浦大桥 上海 33.80 8S5 P5 J1 东方明珠 上海 22.80 20S5 P5 J4 明珠线 上海 22.80 60S5 P5 J6 南浦大桥 上海 22.80 8S8 P3 J1 东方明珠 上海 13.00 20第11页，本讲稿共92页关系可定义为笛卡儿积的一个子集，并不是每个子集都是有意义的。对关系的值要作各种限制，这种限制称为数据完整性约束条件。数据完整性约束主要有两种：1.依赖于值域的限制-由DBMS完整性子系统实现；2.只依赖于属性间取值的相等与否的限制-仅取决于两个元组的某些分量是否相等-统称为数据依赖数据依赖描述的是属性与属性之间的对应关系。2 函数依赖第12

7、页，本讲稿共92页一、函数依赖定义定义：设有关系模式 R（A1,A2,An），X和 Y是属性集（A1,A2,An）的子集，如果对于R的任何一个关系r中的任两个元组u和v，对应于X的属性分量的值相等，而对应于Y的属性分量的值也相等，即：只要有uX=vX，就有uY=vY，称“X函数确定Y”或称“Y函数依赖于X”,其符号表示为：X YFD的确切语义：表示了关系模式集X值与Y值的多对一联系。(SNO,PNO,JNO)(JNAME,JCITY).JNO(JNAME,JCITY)更明确地说：对于r中属性或属性组X的每一个值，r中Y只有一个值与之对应。第13页，本讲稿共92页二、完全函数依赖定义：在关系模式

8、R（A1,A2,An）中，已知X Y,对于X中任何真子集X(X X)都不能函数确定Y，称 X Y是完全函数依赖,用符号XY表示。完全依赖也称为“左部不可约依赖”。f三、部分函数依赖定义：在关系模式R（A1,A2,An）中，已知X Y,如果存在一个真子集X(X X)，满足X Y，则称Y对X是部分函数依赖，用符号XY表示。p四、传递函数依赖定义：在关系模式R（A1,A2,An）中，已知X Y，Y Z(Y X，Z Y不存在Y X），则称 X Z 是传递函数依赖。t第14页，本讲稿共92页 定义:如果A是关系模式R的候选键K中属性，那么称A是R的主属性；否则称A是R的非主属性。五、函数依赖和关键码的联

9、系定义:设有关系模式R(A1,A2,An),K是属性集(A1,A2,An)的一个子集。如果KU（U完全函数依赖于K）在R上成立，那么称K是R的一个候选键。f如果X U(K X)在R上成立,那么称X是R的一个超键。p第15页，本讲稿共92页3关系模式的范式用什么标准来衡量关系模式设计的好与坏？-关系模式的范式(NormalForms,简记为NF)。一、第一范式（1NF）定义：如果关系模式R的每个关系r的属性值都是不可分 的原子值,那么称R是第一范式(firstnormalform)的模式。满足1NF的关系称为规范化的关系，否则称为非规范化的关系。关系数据库研究的关系都是规范化的关系。第16页，本

10、讲稿共92页既使关系模式是1NF，但很可能具有不受欢迎的冗余和异常现象。因此需把关系模式作进一步的规范化。如果数据库模式中每个关系模式都是2NF，则称数据库模式为2NF的数据库模式。二、第二范式（2NF）定义:如果关系模式R 1NF,并且R中每个非主属性都完全函数依赖于R的候选键，称R是第二范式（2NF）的模式。第17页，本讲稿共92页三、第三范式（3NF）定义:如果关系模式R 1NF,并且R中每个非主属性都不传递依赖于R的候选键,那么称R是第三范式（3NF）的模式。如果数据库模式中每个关系模式都是3NF，则称其为3NF的数据库模式。在3NF模式中，并未排除主属性对候选键的传递依赖，仍有可能有

11、冗余和异常现象。3NF分解第18页，本讲稿共92页四、BCNF模式定义：如果关系模式R 1NF，并且R中每个属性都不传递依赖于R的候选键,那么称R是BCNF的模式。由BCNF 的定义得出如下结论：1.非主属性对码完全函数依赖；2.主属性对不包含它的码也是完全函数依赖；3.没有属性完全依赖非码的任何属性组。如果数据库模式中每个关系模式都是BCNF，称其为BCNF的数据库模式。第19页，本讲稿共92页例如：关系模式R(C,S,Z)其中C：城市名称S：街道名称Z：邮政编码假定：F=CS Z,Z CCS Z:表示地址(城市和街道)决定邮政编码;Z C:表示邮政编码决定城市名称。R的候选码为：CS和SZ

12、。第20页，本讲稿共92页R(C,S,Z)的候选码为：CS 和SZ。由于F中存在Z C:主属性C对不包含它的码SZ不是完全函数依赖，所以R(C,S,Z)不是BCNF模式，但R(C,S,Z)是3NF，因为没有任何非主属性对码传递函数依赖或部分函数依赖。如果把R(C,S,Z)分解为:R1（S，Z）R2（Z,C）能解决冗余问题，而且R1，R2都是BCNF模式集。但丢失了CS Z，数据语义将会引起新的矛盾。第21页，本讲稿共92页 4 数据依赖的公理系统 一、函数依赖 FD 的逻辑蕴涵 F 逻辑蕴涵 XY，记为：FXY。定义一：设F是关系模式R(A1,A2,An)上成立的函数依赖集，X和Y是属性集（A

13、1,A2,An）的子集，XY是一个其他的函数依赖。如果对于R的每个满足F的关系r也满足XY（或从F推导出XY也在R（U）上成立），那么称第22页，本讲稿共92页定义二：设F是关系模式R（A1,A2,An）上成立的函数依赖集，X和Y是属性集（A1,A2,An）的子集，F的所有逻辑蕴涵组成的集合称为函数依赖集F的闭包,记为F+。F+=XY|FXY 即：从给定的函数依赖集合F推出的所有函数依赖组成 的集合，称为F的闭包。第23页，本讲稿共92页二、FD推理规则（Armstrong公理）设U是关系模式R的属性集，F是R上成立的一组函数依赖集X、Y分别是U上的子集，存在如下规则：1、FD公理（函数依赖公

14、理）：自反性：若Y X U，则XY在R上成立。增广性：若XY在R上成立，且Z U，则XZYZ在R上成立。传递性：若XY和YZ在R上成立，则XZ在R上成立。第24页，本讲稿共92页2、FD推理规则并规则：若XY，XZ，则XYZ。伪传递规则：若XY，YWZ，则XWZ。分解规则：若XY，Z Y，则XZ。复合规则：若XY，WZ，则XWYZ。通用一致性定理：若XY，WZ，则X（WY）YZ。从并规则和分解规则可得到下面的定理。定理:如果A1An是关系模式R的属性集，那么XA1An成立的充分必要条件是XAi（i=1，n）成立。第25页，本讲稿共92页例:已知关系模式R(ABC),F=AB，BC,求F+。答：

15、根据函数依赖公理系统，可推出F的F+有43个FD。其中：据自反性可得出27个FD：A BCAB BC CA ABC AABBCCABABCBCAAABCAABBBCCCACABCBABABBCBCCACAABCCABCABABCBCABCCAABCABC第26页，本讲稿共92页据增广性可得出7个FD：ABBCABC(AB，ABB,BC)AABBBCABABCCABC(CAA,AB,BBC)据传递性可得出9个FD：AC(AB，BC)CAB(CAA,AB)ACAABC(ACA,CABC)ABBC(ABA,ABC）CAAB(CAA,AAB)CAAB(CAA,AAB)ABCA(ABA,ACA)AABC

16、(ACA,CAABC)第27页，本讲稿共92页在实际使用中，经常要判断能否从已知的函数依赖集F推导出函数依赖XY，那么可先求出F的闭包F+，然后再看XY是否在F+中。但是从F求F+是一个复杂且困难的问题（NP完全问题，指数级问题）。下面引入属性集闭包概念，将使判断问题化为多项式问题。定义三：对于函数依赖XY，如果Y X，那么称XY是一个“平凡的FD”；否则称为“非平凡的FD”。平凡的FD并没有实际意义，根据自反性就可推出。我们感兴趣的是非平凡的FD。只有非平凡的FD与完整性约束条件相关。第28页，本讲稿共92页三、属性集的闭包定义：设F是属性集U上的FD集,X是U的子集，那么（相对于F）属性集

17、X的闭包用XF+表示，它是一个从F集使用FD推理规则推出的所有满足XA的属性A的集合：XF+=A|A U，XA F+从属性集闭包的定义可得出下面的定理。定理：XY能用FD推理规则推出的充分必要条件是:Y XF+第29页，本讲稿共92页四、属性集X的闭包的计算方法输入：一个有限的属性集合U；U上满足的函数依赖集合F；U的一个子集X。输出：X关于F的闭包XF+。方法：根据下列规则计算属性集序列X（0），X（1），。、置初值X（0）:=X,i=0；、X(i+1):=X(i)A|YZ F AZ Y X(i)、判断X（i）=X（i+1）否？若不等，置X（i）=X（i+1）,i:=i+1转若相等，计算终止

18、，此时X（i+1）就是所要求的属性集X关于F的闭包XF+。第30页，本讲稿共92页四、属性集X的闭包的计算方法输入：一个有限的属性集合U；U上满足的函数依赖集合F；U的一个子集X。输出：X 关于F 的闭包XF+。第31页，本讲稿共92页方法：根据下列规则计算属性集序列X（0），X（1），。、置初值X（0）:=X,i=0；、X(i+1):=X(i)A|YZ F AZ Y X(i)、判断X（i）=X（i+1）否？若不等，置X（i）=X（i+1）,i:=i+1转若相等，计算终止，此时X（i+1）就是所要求的属性集X关于F的闭包XF+。第32页，本讲稿共92页例：设UA,B,C,D,E,G，F=ABC

19、，CA，BCD,ACDB,DEG,BEC,CGBD,CEAG 求(BD)F+解：设X=BD令：X(0)=BD 计算 X(1):=BD EG=BDEG;(DEG)计算 X(2):=BDEGC=BCDEG;(BEC)计算 X(2):=BCDEGA=ABCDEG;(CA,BCD,CGBD,CEAG)X(3)已包括所有属性，算法终止。(BD)F+=ABCDEG第33页，本讲稿共92页五、函数依赖集的等价和最小依赖集定义一:关系模式R(U)上的两个函数依赖集F和G，如果F+=G+，称F和G是等价的；如果F和G等价，称F覆盖G，或G覆盖F。定理：F+=G+的充分必要条件是：F G+且G F+第34页，本讲

20、稿共92页定义二：如果函数依赖集F满足下列三个条件,称F为最小依赖集：F中每一个函数依赖的右边都是单属性;-右端无冗余属性对于F中任一函数依赖XA，其FXA与F不等价；-F中没有冗余的函数依赖对于F中任一函数依赖XA，其FXA ZA与F不等价，其中Z X。-左端无冗余属性。定理：任何一个函数依赖集F至少存在一个最小函数依赖集Fmin。第35页，本讲稿共92页例：分析下列函数依赖集F1，F2，F3是否为最小函数依赖集。ADBCADACF1=BECF2=BAF3=ADBCHACCDBDDADC解析：F1不是最小集，因为ADBC不满足条件。F2不是最小集,因为F2AC等价于F2，不满足条件。F3不是

21、最小集，因为F3ADB DB等价于F3，不满足条件。(F3中：DA，ADB 由伪传递得DB)第36页，本讲稿共92页函数依赖集最小化处理的一般步骤：1、用分解规则消去函数依赖右端的冗余属性。(使F中每一个函数依赖的右边都是单属性).2、应用传递性消去函数依赖集F中冗余的函数依赖。(对于F中每一个函数依赖XA,分别检验F与FXA不等价)3、应用伪传递规则消去函数依赖左端的冗余属性。（对于F中任一函数依赖XA，其FXA ZA与F不等价，Z X）。第37页，本讲稿共92页例:设函数依赖集F=AC,CA,AB,BA,BC，试求Fmin。解：第一步：F已满足最小函数依赖集的第个条件中。第二步：对于F中每

22、一个函数依赖XA,分别检验F与FXA是否等价;F中的AC（AB，BC，据传递性）是多余的，所以AC可删去。得F=AB，BA，BC，CA同样F中BA也是多余的（BC,CA）,BA可删去。得F=AB，BC，CA第三步：消去函数依赖左端的多余属性：在本例中，F中每一个函数依赖左端的都是单属性，不可再分。Fmin=AB，BC，CA第38页，本讲稿共92页例:已知F=AD，BD，BDCA，CDB，求 Fmin。第二步：消去函数依赖左端的冗余属性(应用伪传递)由BD,BDC,可推出BC,所以BDC的左端的D是多余的;由BD，BDA,可推出BA,所以BDA的左端的D是多余的;F2=AD，BD，BC，BA,C

23、DB 第三步：去除F中冗余的FD(应用传递性);由 BA，AD，可推出 BD，所以 BD 是多余的。Fmin=AD，BC，BA,CDB 解:第一步：应用分解规则得：F1=AD，BD，BDC，BDA,CDB 第39页，本讲稿共92页 解决的办法是：对关系模式进行分解 即：将一个模式分解为多个关系模式。但在分解后又会出现新的问题，原模式所满足的特征（如属性之间的约束）在新模式中是否被保持；即 模式的等价性问题。关系模式存在多余的函数依赖或者说模式不够规范，就有可能出现存储异常现象。5 关系模式的分解第40页，本讲稿共92页 等价性问题包括:数据等价和依赖等价两个方面:数据等价是指两个数据库实例应表

24、示同样的信息内容,用“无损联接”来衡量。如果是无损联接分解，那么反复投影和自然联接都不会丢失信息。依赖等价是指两个数据库模式应有相同的依赖集闭包。在依赖集闭包相同的情况下，数据的语义是不会出差错的。一个违反数据等价或依赖等价的分解很难说是一个好的模式设计。第41页，本讲稿共92页一、模式分解问题定义：设有关系模式R（U），R1、Rk都是R的子集，U=R1Rk,关系模式R1、Rk的集合用表示，=R1，Rk,用代替R的过程称为关系模式R的分解。称为R的一个分解,也称为数据库模式。泛关系模式数据库模式R=R1，Rkr=r1，rk泛关系(元组的集合）数据库实例（数据库）第42页，本讲稿共92页把R分解

25、成的目的:是为了消除数据冗余和操作异常现象。问题是：和r是否表示同一个数据库。如果两者表示不同的内容，那么这个分解就没有什么意义了。第43页，本讲稿共92页可以从两个角度来考虑分解：和r是否等价:即是否表示同样的数据?用“无损分解”特性表示。在模式R上有一个函数依赖集F，在的每一个模式Ri上也有一个FD集Fi，那么F1，Fn与F是否等价?用“保持依赖”特性表示。第44页，本讲稿共92页 二、无损联接分解定义：如果R是一个关系模式,数据库模式=R1，Rk是R的一个分解,F是R上成立的一个函数依赖集。如果在R中满足F的每一个关系r，都有下式成立：r=R1（r）R2（r）Rk（r）称分解相对于F是“

26、无损联接分解”，否则称为“损失分解”。其中：符号 Ri（r）表示：关系r在模式Ri属性上的投影。r的投影联接表达式R1(r)Rk(r)用符号m(r)表示：Km（r）=Ri（r）i=1第45页，本讲稿共92页如果R是一个关系模式，=R1,R2,，Rk是关系模式R上的一个分解，r是R上的任一关系，ri=Ri(r)（1ik）,则有下列性质：r m(r);若s=m(r),则Ri(s)=ri;m(m(r)=m(r);幂等性。第46页，本讲稿共92页三、无损联接的测试算法1：输入：关系模式R（A1,A2,An）,R上成立的函数依赖集F，R的一个分解=R1，R2，Rk。输出：判断相对于F是否具有无损联接特性

27、。具体步骤:构造一张k行n列的表格,每列对应一个属性Aj(1jn)，每行对应一个模式Ri(1ik)：如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上符号bij。第47页，本讲稿共92页反复检查F中的每一个函数依赖,并修改表格中的元素,方法是：取F中的一个函数依赖XY，如果表格中有两行在X分量上相等,在Y分量上不相等，那么修改Y，使这两行在Y分量上也相等。原则：a.如果Y的分量中有一个是aj，那么另一个也修改成aj；b.如果没有aj，那么用其中一个bij替换另一个符号（尽量把下标ij改成较小的数）。一直到表格不能修改为止（这个过程称为Chase过程）。、若修改到最后,一张表格中

28、有一行是全a，即a1a2an,那么相对于F是无损联接分解。第48页，本讲稿共92页例：设有R（ABCDE），F=AC，BC，CD，CEA，DEC，R 的一个分解=AD，AB，BE，CDE，AE，求的分解无损性。答：根据已知条件构造一张5行5列的表格如下：jiA BCDEADa1b12b13a4b15AB a1a2b23b24b25BE b31a2 b33b34a5CDE b41b42a3a4a5AE a1b52b53b54a5第49页，本讲稿共92页根据AC，对表一进行处理，将b23，b53改为b13，jiA BCDEAD a1b12b13a4b15AB a1a2b23 b13b24b25BE

29、 b31a2b33b34a5CDEb41b42a3a4a5AE a1b52b53 b13b54a5 再考虑BC，将b33改为b13;第50页，本讲稿共92页根据AC，对表一进行处理，将b23，b53改为b13，再考虑BC，将b33改为b13;jiA BCDEAD a1b12b13a4b15AB a1a2b23 b13b24 b25BE b31a2b33 b13b34 a5CDEb41b42a3a4a5AE a1b52b53 b13b54 a5第51页，本讲稿共92页根据AC，对表一进行处理，将b23，b53改为b13，再考虑BC，将b33改为b13;然后考虑CD，将b24，b34，b54改为a

30、4。修改后的表格如下：jiA BCDEAD a1b12b13a4b15AB a1a2b23 b13b24 a4b25BE b31a2b33 b13b34 a4a5CDEb41b42a3a4a5AE a1b52b53 b13b54 a4a5第52页，本讲稿共92页 在上表的基础上，考虑DEC，将b13改为 a3;考虑CEA，将b31,b41改为 a1。由于 第三行为全a,所以是无损联接。A BCDEAD a1b12b13 a4b15AB a1a2b13a4b25BE b31 a1a2b13 a3a4a5CDEb41 a1b42a3a4a5AE a1b52b13 a3a4a5第53页，本讲稿共92

31、页2、无损联接的测试算法2：如果R的一个分解为=R1,R2，F为R所满足的函数依赖集合，分解相对于F是无损分解的充要条件是：R1R2 R1-R2 或 R1R2 R2-R1第54页，本讲稿共92页例：试分析下列分解是否具有无损联接性：设R（ABC），F=AB在R上成立，1=AB，AC。52页答：1相对于F具有无损联接性。R1R2=ABAC=A；R1-R2=AB-AC=B；满足AB；模式1=AB，AC具有无损联接性。第55页，本讲稿共92页设R(ABC),F=AB在R上成立，2=AB，BC。答：2相对于F3是有损分解：R1R2=ABBC=B；R1-R2=AB-BC=A；不满足AB；模式2=AB，B

32、C是有损分解。第56页，本讲稿共92页四、保持函数依赖的分解如果关系模式在分解后不能保持函数依赖，那么在数据库中就会出现异常现象。所以，关系模式R到=R1，R2，Rk的分解，应使函数依赖集F被F在这些Ri上的投影所逻辑蕴涵。这就是保持函数依赖问题。第57页，本讲稿共92页定义一:设F是属性集U上的函数依赖集,Z是U上的一个子集,F在Z上的一个投影用Z（F）表示：Z（F）=XY|XY F+X,YZ定义二:设=R1,R2,，Rk是关系模式R的一个分解，F是R上的函数依赖集，如果k Ri（F）Fi=1称分解保持函数集F。第58页，本讲稿共92页 k k从定义一可知F Ri（F），从定义二可知Ri（F

33、）F，i=1 ki=1因此，在分解保持函数依赖情况下有（Ri（F）+=F+。i=1根据定义二，测试一个分解是否保持FD，比较可行的方法是k逐步验证F中每个FD是否被Ri（F）逻辑蕴涵。i=1如果F的投影不蕴涵F，而我们又用=R1，Rk表达R，很可能会找到一个数据库实例满足投影后的依赖，但不满足F。对的更新也有可能使r违反FD。下面的例子说明了这种情况。第59页，本讲稿共92页例：试分析下列分解是否具有无损联接性和保持函数依赖性：设R（ABC），F=AC，BC在 R上成立，=AB，AC。又 已知 F=AC，BC A+=AC B+=BC（AB）+=ABC AB（F）=；AC（F）=AC；而AB（F

34、）AC（F）=AC，BC在该分解中丢失了。模式不具有保持函数依赖性。解：相对于F是无损联接分解但不保持函数依赖性。R1R2=ABAC=A；R2-R1=AC-AB=C；满足 AC；模式=AB，AC具有无损联接性。第60页，本讲稿共92页一、分解成3NF模式集算法1：结果为3NF并保持函数依赖性的分解。输入：关系模式R的属性集合U和R上成立的最小函数依赖集Fmin。输出：R的一个分解=R1，R2，Rk，满足每一个Ri相对Ri（F）是3NF，且保持F。6模式分解的方法第61页，本讲稿共92页方法：如果R中某些属性在F的所有依赖的左端或右端都不出现，那么这些属性可以从R中分解出去，单独构成一个模式。如

35、果F中存在一个依赖XA，而且X，A=U，则:=R，停止。如果不为，则进行如下分解：对F中的每一个依赖XA，构成一个关系模式XA。如果F中有XA1，XA2，An，则可以用模式XA1A2An代替XA1，XA2，XAn。分解结束，输出。第62页，本讲稿共92页例：关系模式W（CTHSRG），最小函数依赖集Fmin=（CT，HRC，HTR，CSG，HSR）根据算法，生成的分解为：=（CT，HRC，HTR，CSG，HSR）这样的分解，显然将原有的函数依赖都保持下来，而且每个分解模式均为3NF模式。第63页，本讲稿共92页算法2：转换为3NF即具有无损连接性又保持函数依赖的分解。输入:关系模式R的属性集合

36、U和R上成立的最小函数依赖集Fmin。输出:即保持函数依赖又具有无损联接地分解，而且中所有关系模式都是3NF。方法：设=R1，R2，Rn是由算法1得到的一个3NF保持函数依赖的分解；构造=X,其中X是R的一个侯选键。例：=（CT，HRC，HTR，CSG，HSR）HS+=CTHSRG=X=(CT，HRC，HTR，CSG，HSR)第64页，本讲稿共92页四、无损联接地分解成BCNF模式集定理：设F是模式R的FD集，=R1，R2，Rk是相对于F的一个无损联接分解，则有下面的结论成立：对某个i，设Fi=Ri（F）,且1=S1，S2，Sm是相对于Fi的Ri一个无损联接分解。那么R分解成：R1，Ri-1，

37、S1，S2，Sm，Ri+1，Rk是相对于F的一个无损联接分解。设2=R1，Rk，Rk+1，Rn是R的一个分解，那么2相对于F也是一个无损联接分解，第65页，本讲稿共92页算法3：无损联接地分解成BCNF模式集输入：关系模式R的属性集合U和R上成立的函数依赖集F。输出：R的一个无损分解=R1，R2，Rk，满足每个Ri相对Ri（F）是BCNF模式集。方法：反复使用上述定理，逐步分解关系模式R，使每次分解具有无损联接特征，并且分解出来的模式满足BCNF。第66页，本讲稿共92页方法：反复使用上述定理，逐步分解关系模式R，使每次分解具有无损联接特征，并且分解出来的模式满足BCNF。置初值：=R；如果中

38、所有模式都是BCNF，则转；如果中有一个关系模式S不是BCNF，则S中必能找到一个函数依赖XA有X不是S的码,且A X，设S1=XA，S2=SA，用分解S1，S2代替S，转;分解结束，输出。第67页，本讲稿共92页举 例1：试分析下列分解是否保持函数依赖性：设 R（ABCD），F=AB，BC,CD，DA,=AB,BC,CD 请运用保持函数依赖集的测试算法验证是否保持函数依赖性。解：算法的第一步是计算F在每一个关系模式Ri上的投影：A+=ABCD，B+=ABCD，C+=ABCD，D+=ABCD AB(F)=AB，BABC(F)=BC，CB CD(F)=CD，DC k 算法的第二步是逐步验证F中每个FD是否被Ri(F)逻辑蕴涵。ki=1Ri(F)=AB,BA,BC,CB,CD,DC只要判断其是否i=1逻辑蕴涵DA?由 DC,CB,BA 可推出 DA，=AB,BC,CD 保持 FD。第68页，本讲稿共92页