数据库系统原理及应用丁忠俊第四章关系数据库理论.ppt

《数据库系统原理及应用丁忠俊第四章关系数据库理论.ppt》由会员分享，可在线阅读，更多相关《数据库系统原理及应用丁忠俊第四章关系数据库理论.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 关系数据库设计理论关系数据库设计理论第一节第一节 概述概述一、关系一、关系DB设计理论的主要内容设计理论的主要内容1、解决的主要问题、解决的主要问题从理论上来讲，如何设计一个比较好的关系模式的集合？从理论上来讲，如何设计一个比较好的关系模式的集合？2 2、本章的主要内容、本章的主要内容 三方面的内容：三方面的内容：数据依赖（函数依赖、关键字、函数依赖的推理规则）数据依赖（函数依赖、关键字、函数依赖的推理规则）关系模式的分解（两种特性：无损联接性和保持依赖性）关系模式的分解（两种特性：无损联接性和保持依赖性）范式理论（范式理论（1 1NF-5NFNF-5NF）其中：数据依赖是基础。

2、其中：数据依赖是基础。即即：范范式式理理论论和和关关系系模模式式的的分分解解都都是是建建立立在在数数据据依依赖赖的的概概念念基基础础之之上。上。二、关系模式使用中的异常问题二、关系模式使用中的异常问题例例:设设有有关关系系模模式式R R（TNAMETNAME，ADDRADDR，C#C#，CNAMECNAME）（分分别别为为：教教师师名名，地址，课程号，课程名）其关系如下：地址，课程号，课程名）其关系如下：TNAMEADDRC#CNAMEt1t1t1t2t2t3a1a1a1a2a2a3c1c2c3c4c5c6n1n2n3n4n2n4R R现实世界的事实可知：现实世界的事实可知：一个教师只有一个地

3、址一个教师只有一个地址一个教师可讲若干课程一个教师可讲若干课程每门课程只有一个教师任教每门课程只有一个教师任教R R的侯选关键字为的侯选关键字为:(TNAME,C#)TNAME,C#)在使用过程中会存在以下问题：在使用过程中会存在以下问题：（1 1）数数据据冗冗余余：当当一一个个教教师师若若讲讲多多门门课课程程，则则其其地地址址值值会会重重复复存存储多次。储多次。数据冗余：同一个数据重复存储。数据冗余：同一个数据重复存储。数据冗余会引起：数据冗余会引起：浪费存储空间；浪费存储空间；造成修改数据不一致性。造成修改数据不一致性。（2 2）更新操作异常）更新操作异常修改异常：由数据冗余引起的。修改异

4、常：由数据冗余引起的。如如上上例例：t1t1教教师师讲讲了了三三门门课课，其其地地址址值值a1a1重重复复存存储储了了三三次次；若若t1t1搬搬家家，则则它它的的地地址址值值必必须须修修改改三三处处值值，若若只只修修改改一一处处，则则会会产产生生修修改改不一致性。不一致性。插入异常：指该插入的数据而不能插入到关系中。插入异常：指该插入的数据而不能插入到关系中。如如：新新增增加加一一个个教教师师，但但尚尚未未分分配配讲讲课课任任务务，则则不不能能将将其其姓姓名名和和地地址值插入到址值插入到R R中。中。原因：原因：R R 的候选关键字（的候选关键字（TNAMETNAME，C C#）中，中，C C

5、#为空值。即：为空值。即：候选关键字中主属性为空或部分为空的元组违反了实体完整性原则。候选关键字中主属性为空或部分为空的元组违反了实体完整性原则。删除异常：指不该从关系中删除的数据被删除了。删除异常：指不该从关系中删除的数据被删除了。如：若要把原来上过课，但目前未上课的教师的所有元组删去，则如：若要把原来上过课，但目前未上课的教师的所有元组删去，则将该教师的姓名和地址信息也从将该教师的姓名和地址信息也从R R中删除了。中删除了。注：注：DBDB的更新操作异常和数据冗余在网状，层次，面向对象的模型的更新操作异常和数据冗余在网状，层次，面向对象的模型也存在。也存在。什么原因使得关系产生操作异常和数

6、据冗余呢？什么原因使得关系产生操作异常和数据冗余呢？原原因因：关关系系模模式式中中的的属属性性之之间间依依赖赖问问题题；这这就就是是引引入入属属性性之之间间函函数数依依赖赖的的原原因因。现现在在采采用用函函数数依依赖赖的的概概念念，利利用用分分解解方方法法，将将R R 分分解两个等价的关系：解两个等价的关系：R1 R1（TNAMETNAME，ADDRADDR）R2 R2（TNAMETNAME，C C#，CNAMECNAME）TNAME ADDRt1t2t3a1a2a3TNAMEC#CNAMEt1t1t1t2t2t3c1c2c3c4c5c6n1n2n3n4n2n4数据冗余大减，上述情况的异常消除

7、。数据冗余大减，上述情况的异常消除。关关系系模模式式如如何何分分解解；分分解解到到一一个个什什么么程程度度为为好好？将将是是本本章章讨讨论论的的问问题。题。R1R1R2R2第二节第二节 函数依赖函数依赖一、函数依赖（一、函数依赖（Functional Dependency Functional Dependency 简称简称FDFD）的定义的定义定定 义义 1 1：设设 有有 关关 系系 模模 式式 R R（U U），U=AU=A1 1，A A2 2，A An n，若若对对R R的的所所有有具具体体关关系系r r都都存存在在：对对于于每每一一个个X X值值，都都有有唯唯一一的的Y Y值与之对应

8、，则称值与之对应，则称 X X 函数决定函数决定 Y Y；或说或说 Y Y 函数依赖于函数依赖于X X，记为：记为：定义定义2 2：设有关系模式：设有关系模式R(A1,A2,An),R(A1,A2,An),和和 均均 A1,A2,AnA1,A2,An的子集，的子集，r r是是R R 的任一具体的关系的任一具体的关系(R-R-型型,r r值值),),t1t1和和t2t2是是r r中任意两中任意两个元组个元组,若由若由 导致导致 ,则称则称 函数决定函数决定 ,或说或说 函数依赖于函数依赖于 ,记为：记为：注：注：(1)FD(1)FD是对是对R R一切可能的当前值一切可能的当前值r r定义的，不是

9、针对某个特定关系。定义的，不是针对某个特定关系。(2)(2)FDFD是是语语义义范范畴畴的的概概念念，只只有有通通过过属属性性之之间间的的语语义义来来确确定定是是否否存存在在函函数数依依赖赖关关系系，不不能能用用数数学学方方法法推推导导或或证证明明。它它是是现现实实世世界界中中属属性之间客观存在或设计者人为强制相结合的产物。性之间客观存在或设计者人为强制相结合的产物。例例:若设计者限定：无同名同姓；则：姓名若设计者限定：无同名同姓；则：姓名年龄（反之：年龄（反之：年龄年龄 姓名），姓名），若有同名同姓：则，姓名若有同名同姓：则，姓名 年龄。年龄。(3)(3)中中，称称为为决决定定的的因因素素，

10、只只要要 取取一一个个值值，则则有有 唯唯一一的的值与之对应。值与之对应。二、函数依赖与属性间联系的关系二、函数依赖与属性间联系的关系设关系模式设关系模式R R，则：则：(1)(1)如如果果 ，之之间间是是1-11-1联联系系，则则存存在在：和和 ，即即 ，相相互互函函数数依赖依赖 记为记为 。(2)(2)如果如果 ,之间是之间是 m-1m-1联系，则存在联系，则存在 ,。(3)(3)如如果果X,YX,Y之之间间是是n-mn-m 联联系系，则则X,Y X,Y 之之间间不不存存在在函函数数依依赖赖，即即 ，.结结论论：根根据据关关系系r r当当前前值值，可可从从属属性性间间的的联联系系入入手手来

11、来决决定定函函数数依依赖赖是否存在。是否存在。例：已知关系例：已知关系r r如下如下ABCDEa1a1a2a2b1b2b1b1c1c2c3c4d1d2d3d3e1e1e1e1r r下列函数依赖中，关系下列函数依赖中，关系r r满足哪些依赖？满足哪些依赖？a a、A ABBb b、(A,B)D(A,B)Dc c、C(B,D,E)C(B,D,E)d d、EAEAe e、A AEE 三、关键字（键、码）三、关键字（键、码）用用FDFD概念精确定义关键字概念精确定义关键字定定义义：设设关关系系模模式式R R（A A1 1，A A2 2，A An n），F F是是R R上上的的函函数数依依赖赖集集，X

12、X是（是（A A1 1，A A2 2，A An n）的一个子集，如果：的一个子集，如果：（1 1）XAXA1 1，A A2 2，A An n且且 （2 2）在在X X中中不不存存在在真真子子集集 Y Y，使使得得YAYA1 1，A A2 2，A An n成成立立，则则称称X X是是R R的候选关键字。的候选关键字。注：条件（注：条件（1 1）表示）表示X X能唯一决定一个元组。能唯一决定一个元组。条件（条件（2 2）表示）表示X X是满足（是满足（1 1）而无多余的属性集。）而无多余的属性集。例：关系模式例：关系模式R R（学号，姓名，性别，年龄）中，按语义：学号，姓名，性别，年龄）中，按语义

13、：学号学号姓名姓名 学号学号性别性别 学号学号年龄年龄 学号学号（学号，姓名，性别，年龄）（学号，姓名，性别，年龄）学号是学号是R R一个候选关键字。一个候选关键字。也可说明：（学号，姓名）也可决定也可说明：（学号，姓名）也可决定R R中的全部属性，中的全部属性，但（学号，姓名）不是候选关键字。但（学号，姓名）不是候选关键字。（学学号号，姓姓名名）存存在在真真子子集集：“学学号号”可可以以决决定定全全部部属属性性；“姓名姓名”属性多余。属性多余。说明：说明：主属性：包含在候选关键字中的属性。主属性：包含在候选关键字中的属性。非主属性：不包含在候选关键字中的属性。非主属性：不包含在候选关键字中的

14、属性。四、函数依赖的分类四、函数依赖的分类 根据不同性质，函数依赖分类：根据不同性质，函数依赖分类：完全函数依赖完全函数依赖部分函数依赖部分函数依赖传递函数依赖传递函数依赖 1 1、完全函数依赖与部分函数依赖、完全函数依赖与部分函数依赖定定义义：在在关关系系模模式式R R（U U）中中，如如果果 ，并并且且对对 的的任任何何一一个个真真子子集集 ，都都有有 则则称称 完完全全函函数数依依赖赖于于 ，记记作作 。如如果果对对 某某个个真真子子集集 ,有有 ，则则称称 对对 的的函函数数依依赖赖是是部部分分的的函函数依赖，记作：数依赖，记作：。例：关系模式例：关系模式SC(SC(学号，课程号，成绩

15、学号，课程号，成绩)中，显然：中，显然：学号学号 成绩，课程号成绩，课程号 成绩，而：成绩，而：(学号，课程号学号，课程号)成绩成绩,可见：可见：(学学号号、课课程程号号)是是候候选选关关键键字字：学学号号，课课程程号号是是主主属属性性；成成绩绩为为非非主属性。主属性。又如：关系模式又如：关系模式R(R(学号，课程名，系名学号，课程名，系名)中：学号中：学号系名系名,课程名课程名 系名系名 ,(,(学号，课程名学号，课程名)系名系名.f fp p 注注：只只有有决决定定因因素素是是组组合合属属性性，才才存存在在部部分分函函数数依依赖赖，当当决决定定因因素是单属性时，只能是完全函数依赖。素是单属

16、性时，只能是完全函数依赖。2 2、传递函数依赖、传递函数依赖定定义义：在在关关系系模模式式R R（U U）中中，如如果果 ，且且 ，则称则称Z Z传递函数依赖于传递函数依赖于 ，记作，记作:。注：当条件注：当条件 不成立时，即不成立时，即 ，则则 ，实际上实际上是直接函数依赖而非传递函数依赖。是直接函数依赖而非传递函数依赖。例：在关系模式例：在关系模式R R（学号，学生姓名，系名，系主任名）中。学号，学生姓名，系名，系主任名）中。学号学号学生姓名学生姓名 学生姓名学生姓名系名（设无同名同姓）系名（设无同名同姓）则：学号则：学号系名是直接函数决定系名是直接函数决定再：学号再：学号系名，系名系名，

17、系名 学号，系名学号，系名系主任名，系主任名，则有：学号则有：学号 系主任名。系主任名。t t五、函数依赖的逻辑蕴涵五、函数依赖的逻辑蕴涵有时需要从一些已知的有时需要从一些已知的FDFD去判断另一些去判断另一些FDFD是否成立。是否成立。如：已知F=AB，BC在模式R中成立，那么AC在R中是否成成立。这个问题称为逻辑蕴涵问题。立。这个问题称为逻辑蕴涵问题。定义：定义：设设F F 在关系在关系R R上成立的函数依赖集上成立的函数依赖集,XYXY是一个其他的是一个其他的FD(XFD(XR,YR,YR)R)。如果从如果从F F中的函数依赖能推出中的函数依赖能推出XYXY，则称则称F F逻辑蕴逻辑蕴涵

18、涵XYXY，记为：记为：F|F|XYXY。定义：被定义：被F F函数蕴涵的函数依赖的全体构成的集合称为函数蕴涵的函数依赖的全体构成的集合称为F F的闭包的闭包(closure),closure),记为：记为：F+=xY|F XY一般，一般，F F+，若若F=F+则称则称F F是函数依赖的完备集。是函数依赖的完备集。值得注意：依据值得注意：依据F F计算计算F F+是很麻烦的，即使是很麻烦的，即使F F不大，不大，F F+也可能很也可能很大。大。如：有关系如：有关系R(X,Y,Z)R(X,Y,Z)其函数依赖集其函数依赖集F=XF=XY,YZY,YZ 则则共有共有4343个依赖个依赖这些函数依赖怎

19、么出来？待学习了函数依赖的推理规则，再回答此这些函数依赖怎么出来？待学习了函数依赖的推理规则，再回答此问题问题 第三节第三节 F D 公理公理目目的的：确确定定函函数数依依赖赖的的逻逻辑辑蕴蕴涵涵。即即从从给给定定的的F F中中的的函函数数依依赖赖，推推出出F F+中中的的函函数数依依赖赖。也也就就是是说说给给定定了了F F和和 ，判判断断是是 否否在在F F+中。中。为此，要有一套推理规则。为此，要有一套推理规则。一、一、Armstrong Armstrong 公理公理 设设有有关关系系R(AR(A1 1,A A2 2,A An n)和和属属性性全全集集U=AU=A1 1 A A2 2A A

20、n n X，Y，Z，W均是均是U U的子集；的子集；F F是是U U上的一个函数依赖集，推导规则是：上的一个函数依赖集，推导规则是：A A1 1 自反性自反性(Reflexivity)Reflexivity)：若若 ，则，则F F逻辑蕴涵逻辑蕴涵（平凡的函数依赖）平凡的函数依赖）A A2 2 增广性增广性(Augmentation)Augmentation)：若若F F逻辑蕴涵逻辑蕴涵 ，则，则F F逻辑蕴涵逻辑蕴涵A3 A3 传递性传递性(Transitivity)Transitivity)：若若F F逻辑蕴涵逻辑蕴涵 ,F F逻辑蕴逻辑蕴涵：涵：例例：设设R(R(C,C,S,S,Z)Z)，

21、其其中中：C C为为城城市市名名，S S为为街街名名，Z Z为为邮邮编编，给给定定F=CSZ,ZC 即函数依赖图如下：即函数依赖图如下：C CS SZ Z由由ArmstrongArmstrong公理，有公理，有(1)(1)Z ZC(C(已知已知)说明：说明：Z ZC C逻辑蕴涵逻辑蕴涵F F+中。中。(2)(2)SZSZCS (CS (由由(1)(1)和和 A A2 2增广性增广性)说明说明:SZSZCS CS 逻辑蕴涵在逻辑蕴涵在F F+中。中。(3)(3)CSCSZ (Z (已知已知)(4)(4)CSCSCSZ CSZ(由由(3)(3)和和A A2 2增增广广性性)说说明明：CSCSCSZ

22、 CSZ 在在F F+，也也说说明明 CSCS是是R R 的一个候选关键字。的一个候选关键字。(5)5)SZSZCSZ(CSZ(由由(2)(2)和和A A2 2增广性，或由增广性，或由(2),(4)(2),(4)和和A A3 3传递性传递性)说明：说明：SZSZCSZ CSZ 在在F F+中，也说明中，也说明 SZ SZ 是是R R 的另一个候选关键字。的另一个候选关键字。注：注：可以证明候关键字：可以证明候关键字：CS CS 和和 SZ SZ 中没有多余的属性存在。中没有多余的属性存在。说明：说明：通通过过公公理理可可以以推推出出F F中中的的隐隐含含的的FDFD，尤尤其其可可推推出出关关系

23、系R R的的候候选选关关键字。键字。能能否否保保证证由由公公理理推推出出的的函函数数依依赖赖都都是是正正确确的的，即即所所推推出出的的函函数数依赖都是否依赖都是否 都属于都属于F F+？公理的正确性。公理的正确性。正正确确性性：只只要要F F的的FDFD为为真真，由由公公理理推推出出的的FDFD也也为为真真，则则推推出出的的FDFD都都由由F F+逻辑蕴涵逻辑蕴涵。若公理正确，求若公理正确，求F F+，则可根据则可根据F F通过公理推出所有的函数依赖。通过公理推出所有的函数依赖。属于属于F F+中函数依赖是否都能够由公理通过中函数依赖是否都能够由公理通过F F中的中的FDFD推出？推出？公公理

24、完备性。理完备性。定定理理：ArmstrongArmstrong公公理理是是正正确确的的，即即若若 是是由由F F通通过过公公理理推推出出的的，那么那么 在在F F+中。中。证明：用证明：用FDFD定义证明定义证明(1)(1)自反性：设自反性：设r r是是R R的任意一个关系，的任意一个关系，t t1 1和和t t2 2是是r任意的两个元组。任意的两个元组。若若 ，则在，则在t t1 1和和t t2 2中的中的 的任何子集也必相等的任何子集也必相等 由条件：由条件：必有必有 由由FDFD定义可知：定义可知：(2)(2)增广性：设增广性：设t t1 1,t,t2 2,r,r的含义同上的含义同上采

25、用反证法：假定结果不成立：采用反证法：假定结果不成立：，即：，即：但但 由由 设：设：或或 若若 则与已知的则与已知的 相矛盾相矛盾(,)(,)若若 则与假设的则与假设的 相矛盾相矛盾 增广性是正确的增广性是正确的(3)(3)传递性：设传递性：设t t1 1,t,t2 2,r,r的含义同上的含义同上采用反证法：假设结果不成立：即采用反证法：假设结果不成立：即 X Z 即即 但但 若若 则与条件则与条件 相矛盾相矛盾 (则则 ，但由上但由上 )，若若 则与条件则与条件 相矛盾相矛盾 (，则，则 )传递性正确传递性正确推论：由阿氐公理可以得出如下推论：推论：由阿氐公理可以得出如下推论：(1)(1)

26、合并规则：若合并规则：若 ，成立，则成立，则 成立成立 (2)(2)分解规则：若分解规则：若 成立，则成立，则 ，成立成立 (3)(3)伪传递规则：若伪传递规则：若 ，成立，则成立，则 成立成立证明：用公理证明证明：用公理证明 (1)(1)(已知已知)(2)(2)(3)(3)(已知已知)(公理公理A A2 2)(公理公理A A1 1)(公理公理A A2 2)又又 (已知已知)同理同理 (公理公理A A1 1)(已知已知)(公理公理A A2 2)(已知已知)(公理公理A A3 3)(公理公理A A3 3)(公理公理A A3 3)同理同理 (公理公理A A3 3)例：判断下列推论是否正确，若正确给

27、出相关证明；若错误，试举例：判断下列推论是否正确，若正确给出相关证明；若错误，试举出一反例说明出一反例说明(1)(1)如果如果ABABC C，则则B BC C(2)(2)如果如果ABABC C，则则A AB,B,或或A AC C(3)(3)如果如果A AB B 并且并且BCBCD,D,则则ABCABCD D解：解：(1)(1)错误错误(2)(2)错误错误 (3)(3)正确正确ABC010001ABC000101R RR R A AB ABCBC又又 BCD ABCD（公理公理A3）R R 满足满足ABC ABC 但但B B C ;R C ;R 满足满足ABC ABC 但但A A C C，A A

28、 B B 说明：说明：通过规则通过规则A A1 1，得出平凡的得出平凡的FDFD概念：概念：对对于于函函数数依依赖赖 ,若若 ,则则称称 是是平平凡凡的的函数依赖；若函数依赖；若 ，则为非平凡的则为非平凡的 FDFD。如如：AA,A是是平平凡凡FD.FD.平平凡凡FDFD总总是是成成立立的的，对对A A的的语语义无影响，对模式设计也没有影响。一般不考虑平凡义无影响，对模式设计也没有影响。一般不考虑平凡FDFD 根据推论中合并和分解规则：得出根据推论中合并和分解规则：得出 推论：若推论：若A i(i=1,2,n)是关系模式是关系模式R 的属性集则的属性集则 XA1 A2An成立的充分必要条件是成

29、立的充分必要条件是XA i(i=1,2,n)均成立。均成立。属性集的闭包概念属性集的闭包概念定义：设有关系模式定义：设有关系模式R(A1,A2,An)，U=A1,A2,An；F是是U上的一个函数依赖集，上的一个函数依赖集，则称所有用公理从则称所有用公理从F推出的函数依赖推出的函数依赖 中的中的Ai的属性集合为的属性集合为X 的属性的属性闭包，记为闭包，记为 。即：。即：=Ai 用阿氐公理从用阿氐公理从F推出推出 XA i。显然：显然：例：设关系模式例：设关系模式R(A,B,C),R R(A,B,C),R 的的FDFD集集 F=AF=AB,BB,BCC 则：则：C C+=C (C=C (CC)C

30、)B B+=BC(=BC(由由B BB,BB,BC)A A+=ABC(=ABC(由由A AA A，A AB B，B BC C；A AABC)A A 是是R R的侯选关键字的侯选关键字 可见：计算属性闭包可见：计算属性闭包 比从比从F F计算计算F F+要简单得多。要简单得多。下下列列定定理理告告诉诉我我们们判判断断：从从 一一眼眼看看出出某某一一函函数数依依赖赖是是否否是是用用阿阿氐氐公理从公理从F F推出推出。定理：设定理：设F F是关系模式是关系模式R(AR(A1 1,A,A2 2,An),An)的的FDFD集，集，U=AU=A1 1,A,A2 2,An,An。若若 ，则则 是是用用阿阿氐

31、氐公公理理从从F F推推出出的的充充要要条条件件是是 。二、二、ArmstrongArmstrong公理是完备的。公理是完备的。证明见书证明见书(证明：不能从证明：不能从F F通过公理推出的通过公理推出的FDFD不在不在F F+中中)ArmstrongArmstrong公理完备性告诉我们两个重要结论：公理完备性告诉我们两个重要结论：(1)所有由所有由F F逻辑蕴涵的逻辑蕴涵的 的右端属性的右端属性A A的集合称为的集合称为 的属的属性闭包性闭包 。(与与 定义等价定义等价)(2)(2)用阿氐公理从用阿氐公理从F F推导出来的所有推导出来的所有FDFD的集合是的集合是F F的闭包的闭包F F+(

32、与与F F+定义等价：定义等价：F F+是由是由F逻辑蕴涵的所有逻辑蕴涵的所有FDFD的集合的集合)可见可见:函数依赖公理和函数依赖的逻辑蕴涵之间有某种等效关系。函数依赖公理和函数依赖的逻辑蕴涵之间有某种等效关系。三、属性集闭包的计算三、属性集闭包的计算计计算算F F+的的目目的的：确确定定某某一一函函数数依依赖赖 是是否否由由F F逻逻辑辑蕴蕴涵涵，即即它它是不是成立。是不是成立。公公理理的的完完备备性性说说明明：通通过过计计算算 ，若若 则则 是是由由阿阿氐氐定定理从理从F F推出，则推出，则 是成立的。是成立的。这就说明这就说明:则则 成立。成立。因此，把计算因此，把计算F F+转化为转

33、化为 计算，可达到同样的目的。计算，可达到同样的目的。算法：求属性集算法：求属性集 在在F F上的属性闭包上的属性闭包 。输入：关系模式输入：关系模式R R的全部属性集的全部属性集U U，F F为为U U上的函数依赖集上的函数依赖集输出：输出：在在F F上的属性闭包上的属性闭包方法：按下列规则计算方法：按下列规则计算 ；(1)(1)置初值置初值(2)(2)其中其中A A是这样的属性：在是这样的属性：在F F中寻找尚未用过的左边是中寻找尚未用过的左边是 的子集的函数依赖：的子集的函数依赖：其中：其中：在在Z Z中寻找中寻找 中未出现过的属性集合中未出现过的属性集合A A；若无这样的若无这样的A

34、A则转则转(4)(4)，否则：，否则：(3)(3)判断是否有判断是否有 ，若是则转，若是则转(4)(4)，否则转，否则转(2)(2)(4)(4)输出输出 ，即为，即为上述方法计算步骤是很有限的，因为上述方法计算步骤是很有限的，因为U,X,FU,X,F是有限集。是有限集。例：设函数依赖集例：设函数依赖集F=ABF=ABC,DC,DEG,CEG,CA,BEA,BEC,BCC,BCD,CGD,CGBD,ACDBD,ACDB,CEB,CEAGAG 试用算法，求试用算法，求(BD)BD)+解：解：设设 =BD (1)(1)=BD (2)(2)在在F F中找左边是中找左边是BDBD子集的子集的FDFD，只

35、有：只有：D DEGEG ，显然显然 (i=0)i=0)接下来在接下来在F F中找左边是中找左边是BDEGBDEG子集的子集的FDFD，(但用过的不再考虑但用过的不再考虑)：BECBEC ，显然显然 (i=1)i=1)又在又在F F中找左边是中找左边是BCDEGBCDEG的子集的的子集的FDFD：CA,BCD,CGBD,CEAGCA,BCD,CGBD,CEAG 于是：于是：BCDEGABDG(BCDEGABDG(不考虑用过的不考虑用过的FD)FD)，在在 中未出现的属性是中未出现的属性是A A 此时，虽然此时，虽然 ，但发现，但发现 已包含了全部属性，所以不再计算下去。已包含了全部属性，所以不

36、再计算下去。若即使计算下去，很快发现若即使计算下去，很快发现 或再也找不到在或再也找不到在 中未出现的属性。中未出现的属性。(BD)BD)+=ABCDEG=ABCDEG说明：判断计算终止的说明：判断计算终止的4 4种方法：种方法：(1)(1)；(2)(2)当当 包含了全部属性；包含了全部属性；(3)(3)在在F F中中FDFD的右边属性中再也找不到的右边属性中再也找不到 中未出现过的属性；中未出现过的属性；(4)(4)在在F F中未用过的中未用过的FDFD的左边属性已经没有的左边属性已经没有 的子集。的子集。算法计算正确性见书。算法计算正确性见书。说明：利用说明：利用 求求R R的候选关键字：

37、的候选关键字：上例：由于上例：由于(BD)BD)+=ABCDEG (B,D)=ABCDEG (B,D)可能是可能是R R的候选关键字；的候选关键字；(B,D)B,D)是否一定是是否一定是R R候选关键字，则还要看候选关键字，则还要看(B,D)B,D)是否存在决定全部属性的是否存在决定全部属性的 真子集：真子集：即即(B)B)+ABCDEG D ABCDEG D+ABCDEGABCDEG 求求B B+求求D D+=B=B D D+=DEG=DEG =B =B D D也不是真子集也不是真子集 B B+=B=B B B不是真子集不是真子集 (B,D)B,D)是是R R的一个候选关键字的一个候选关键字

38、怎么找出怎么找出R R的全部候选关键字呢？的全部候选关键字呢？(下面介绍求候选关键字的理论下面介绍求候选关键字的理论)四四.FD集的等价和覆盖（求集的等价和覆盖（求F 的最小集）的最小集）定义：设定义：设F和和G是两个函数依赖集，若是两个函数依赖集，若F F+G+则称则称F和和G等价；如果等价；如果F和和G等价，等价，则说则说F覆盖覆盖G，同时同时G覆盖覆盖F。引理引理1：设：设F和和G是函数依赖集，则是函数依赖集，则F+G+的充分必要条件是的充分必要条件是F G+且且G F+。证明略。证明略。这说明，检查这说明，检查F和和G是否等价并不困难，只要检查是否等价并不困难，只要检查 F G+且且G

39、 F+是否是否成成立。立。检查检查F G+是否成立是否成立,即即F中的每一个中的每一个FD是否属于是否属于G+。例如：对于例如：对于X Y F，则在则在G上计算上计算X+，看是否满足看是否满足Y X+，若满足，若满足，则则X Y G+。继续检查其他所有依赖，若全部满足，则继续检查其他所有依赖，若全部满足，则F G+。同理，同理，对对G中每个依赖作同样的处理来检查中每个依赖作同样的处理来检查G F+才能确定才能确定F+=G+.引理引理2:每一个函数依赖集每一个函数依赖集F都可以由一个右端只有单个属性的函数依赖集都可以由一个右端只有单个属性的函数依赖集G所所覆盖。覆盖。证明：设证明：设G由行为由行

40、为X A（A为单属性）的函数依赖组成。为单属性）的函数依赖组成。A Y且且X Y在在F中。中。此时，显然能从此时，显然能从X Y按分解规则导出按分解规则导出X A，从而有从而有G F+。.反之，如果反之，如果YA1A2An，而且而且X A1，X A2，X An在在G中，可中，可根据合并规则得：根据合并规则得：X A1An，因而有因而有F G+。由此得：由此得：FG，即即F被被G覆盖。覆盖。在研究在研究FD时，它的最小集是很有用处的。时，它的最小集是很有用处的。定义：对于给定的一个函数依赖集定义：对于给定的一个函数依赖集F,当满足下列条件时，称为当满足下列条件时，称为F的最小集，的最小集，记为记

41、为F（最小集也称为最小覆盖）。最小集也称为最小覆盖）。（1）F 的每个依赖的右部都是单个属性；的每个依赖的右部都是单个属性；（2）对于）对于F 的任一函数依赖的任一函数依赖X A来说，来说，F X A与与F 都不等价；都不等价；（3）对于）对于F 的任一函数依赖的任一函数依赖X A来说，（来说，（F X A）U Z A与与F 都不等价，其中都不等价，其中Z为为X的任一子集。的任一子集。这个定义中：条件这个定义中：条件(1)保证了每个依赖的右边都是单属性保证了每个依赖的右边都是单属性 条件条件(2)保证在保证在F中不存在多余的依赖中不存在多余的依赖 条件条件(3)保证在保证在F中的每一个依赖的左

42、边没有多余的属性中的每一个依赖的左边没有多余的属性 定理：每一个函数依赖集定理：每一个函数依赖集F都与它的最小依赖集都与它的最小依赖集F 等价等价这个定理的证明按最小依赖集的定义考虑其三个条件，证明的这个定理的证明按最小依赖集的定义考虑其三个条件，证明的过程也是计算最小集的过程。证明过程见书。过程也是计算最小集的过程。证明过程见书。例：设例：设FAB C，C A，BC D，ACD B，D EG，BE C，CG BD，CE AG求求F 解：按最小覆盖依赖集的定义，分别考虑三个条件。解：按最小覆盖依赖集的定义，分别考虑三个条件。（1）用分解规则，将）用分解规则，将F中所有的中所有的FD变为右边是单

43、属性的依赖变为右边是单属性的依赖AB C，C A，BC D，ACD B，D E，D G，BE C，CG B，CG D，CE A，CE G（2）去掉）去掉F中函数依赖左边多余的属性中函数依赖左边多余的属性方法：逐个检查方法：逐个检查F中左边非单属性的依赖，如：中左边非单属性的依赖，如：XY A，若判若判Y是否为多余是否为多余属性，只要在属性，只要在F中求中求X+，若若X+包含包含A，则则Y为多余属性，否则为多余属性，否则Y不多于，不多于，依法判依法判F中其它中其它FD。考察：考察：ACD B（CD）+CDAEGB A为多余属性，应去掉，即用为多余属性，应去掉，即用CD B代替代替ACD B再考察

44、：再考察：CE A (C)=CA (C A)E为多余属性，用为多余属性，用C A代替代替CE AAB C，C A，BC D，CD B，D E，D G，BE C，CG B，CG D，C A，CE G（3）去掉去掉F中多余的依赖中多余的依赖方法：从方法：从F中的第一个中的第一个FD开始，将它从开始，将它从F中去掉（设为中去掉（设为X Y），），然后从剩下的依赖求然后从剩下的依赖求X，看看X是否包含是否包含Y，若包含，则若包含，则X Y是多余的，应去掉，这样依次做下去。是多余的，应去掉，这样依次做下去。(1)(1)显然：上面显然：上面F F中有两个中有两个C AC A，应去掉一应去掉一个个.考察考察

45、;CG BCG B先去掉先去掉CG BCG B则：则：CG DCG D保留保留（CGCG）CGD CGD（CG DCG D）（CGCG）CGDB CGDB（CD BCD B）CG BCG B为多余为多余FDFD。得：得：FFAB C，C A，BC D，CD B，D E，D G，BE C，CG D，CE G 注：注：求出的求出的FF不是唯一的。不是唯一的。注：依注：依F中的顺序不同，则中的顺序不同，则F是不同是不同的的若先考察：若先考察：CD B（CD）CDG （D G）（CD）CDGB （CG B）CD B多余多余.再考察：再考察：CG D（CG）CGB （CG B）（CG）CGBD （BC

46、D）CG D 多余多余另一个另一个FAB C，C A，BC D，DC E，D G，BE C，CG B，CE G(1)(1)(1)(1)(2)(2)(2)(2)(2)(2)(1)(1)第四节第四节 关系模式的分解关系模式的分解一、关系模式分解中的问题一、关系模式分解中的问题1模式分解的目的模式分解的目的为为了了消消除除更更新新异异常常（插插、删删、改改）和和减减少少数数据据冗冗余余，设设计计一一个个较较好的关系模式。好的关系模式。2模式分解的定义模式分解的定义定定义义：设设有有关关系系模模式式R（A1，A2，A3，An）,Ri(i=1,2,k)是是R的的一一些些属属性性子子集集，R1R2Rk=U

47、 则则称称用用=R1,R2,Rk代代替替R的过程称为关系模式的过程称为关系模式R 的分解。的分解。注注：关关系系模模式式的的分分解解，不不仅仅仅仅是是属属性性集集合合的的分分解解，它它是是对对模模式式上上的的函数依赖集以及关系模式当前值的分解的具体表现。函数依赖集以及关系模式当前值的分解的具体表现。例，设关系模式例，设关系模式 （其中（其中S#为为学号，学号，SD为系名，为系名，MN为为系主任名）系主任名），R中当前值的关系中当前值的关系r如下：如下：S#SDMNS1S2S3S4D1D1D2D3张五张五张五张五李四李四王一王一关系关系r若不分解若不分解R，存在的问题：存在的问题：删删除除异异常

48、常：若若S4学学生生毕毕业业了了，删删除除S4则则D3系系的的系系主主任任的的王王一一的信息随之丢失。的信息随之丢失。插插入入异异常常：若若一一个个系系D5尚尚无无学学生生，则则这这个个系系的的系系主主任任赵赵某某信信息无法插入息无法插入R中。中。数据冗余：系和数据冗余：系和系主任的系主任的名称会多次重复存储。名称会多次重复存储。F=S SD,SD F=S SD,SD MN#3模式分解中的问题模式分解中的问题（1 1）将）将R R分解为分解为 则对每一个则对每一个r ri i 有：有：将将R按下列按下列3种方式分解：种方式分解：r r r1 r1 r2 r2 r3 r3 R1R1(r)(r)R

49、2R2(r)(r)R3R3(r)(r)r r3 3=张五，李四，五一张五，李四，五一分解的特性分解的特性:既不保持函数依赖性，又不保持无损连接性。既不保持函数依赖性，又不保持无损连接性。R1R2R3的的属属性性之之间间不不能能保保持持F中中的的函函数数依依赖赖：不不能能回回答答“S1在哪在哪 个系学习个系学习”的问题。的问题。分解后分解后r1r2r3难以恢复原来难以恢复原来r值，即值，即一般表示：一般表示：（2）将）将R分解为分解为 则得则得r4和和r5的关系如下：的关系如下：S#SDS1S2S3S4D1D1D2D3S#MNS1S2S3S4张五张五张五张五李四李四王一王一r4r5不保持不保持S

50、DMN，仍存在前面提到的数据冗余插入和删除异常。，仍存在前面提到的数据冗余插入和删除异常。保持无损的连接性：分解后保持无损的连接性：分解后r4r4和和r5r5中没有损失中没有损失r r中的数据中的数据,即用连即用连接运算可以恢复：接运算可以恢复：r=r4 r5=R4(r)R5(r)(与原来与原来r r中的元组一致中的元组一致)分解的特性：分解的特性：不保持不保持FDFD性性,但保持无损的连接性。但保持无损的连接性。总之：总之：模式分解特性的四种情况：模式分解特性的四种情况：1 1）既不具有无损连接性，又不具有函数依赖的保持性。（不）既不具有无损连接性，又不具有函数依赖的保持性。（不可取的分解）