《函数依赖理论第二讲》由会员分享，可在线阅读，更多相关《函数依赖理论第二讲（27页珍藏版）》请在金锄头文库上搜索。
1、函数依赖理论与范式郑子仪主要内容无关属性、正则覆盖、无损连接分解、有损连接分解第一范式(1NF)、第二范式(2NF)、Boyce-Codd范式(BCNF)、第三范式(3NF)、无关属性n给定给定函数依赖集函数依赖集F及及 F，如果去除，如果去除 或或 的一个属性不会改变的一个属性不会改变F+，则称，则称该属性是该属性是无关的无关的。n给定给定函数依赖集函数依赖集F及及 F，若，若A ，且且F逻辑蕴涵逻辑蕴涵(F- - ) ( - -A) ，则属性则属性A在在 中是无关的（中是无关的（左无关左无关）。）。n给定给定函数依赖集函数依赖集F及及 F，若，若A ，且，且(F- - ) ( ( - -A
2、)逻辑蕴涵逻辑蕴涵F，则属性则属性A在在 中是无关的（中是无关的（右无关右无关）。）。无关属性检测算法设r(R)为关系模式，F是函数依赖集，则检测上的属性A左无关或右无关的算法分别如图 (a)或(b)所示。if A : - -A; 计算计算F下下 的闭包的闭包 +; if + A在在 中是无关的中是无关的;if A F := (F- - ) ( ( - -A); 计算计算F下下 的闭包的闭包 +; if A + A在在 中是无关的中是无关的;(a)(b)图图5-9 无关属性检测算法无关属性检测算法 无关属性检测举例 设FABCD, AE, EC，证明C在ABCD中为无关属性。证明：由于C是AB
3、CD中的右边属性，依图 (b)的算法： 计算F：F=ABD, AE, EC； 计算F下(AB)+：(AB)+=ABCDE；判断C是否属于(AB)+：CABCDE。 因此，C是ABCD中的无关属性。证毕。正则覆盖定义和计算方法正则覆盖(canonical cover)Fc是一个依赖集，使得F逻辑蕴涵Fc中的所有依赖，Fc逻辑蕴涵F中的所有依赖，而且必须具有下列特性：Fc中的任何函数依赖都不包含无关属性；Fc中函数依赖的左半部都是唯一的，即Fc中不存在两个依赖11和22，且12。根据上述性质，计算F的正则覆盖Fc分为两个步骤：合并函数依赖：将F中所有形如11、12的函数依赖合并为112，得到新函数
4、依赖集F。去除无关属性：对F中的每个函数依赖，依次判断是否包含无关属性。若发现无关属性，则用去除无关属性后的函数依赖代替F中的原函数依赖。计算正则覆盖举例 考虑关系模式r(R)=r(A, B, C)和函数依赖集F=ABC, BC, AB, ABC, 计算F的正则覆盖Fc。第1步，合并函数依赖：将ABC和AB合并为ABC。F =ABC, BC, ABC。第2步，去除无关属性：对于ABC，根据图5-9(a)的算法可检测A是无关的。因此，去除无关属性A后，ABC变为BC，而BC已在F中存在，则F=BC, ABC。对于BC，由于其左右两边都为单属性，故不存在无关属性。对于ABC，根据图5-9(b)的算
5、法可检测C是无关的。因此，去除无关属性C后，ABC变为AB，则F=BC, AB。F中的函数依赖左半部都是唯一的，且都不存在无关属性，因此Fc=BC, AB。无损连接分解 n给定关系模式给定关系模式r(R)及函数依赖集及函数依赖集F，若，若r(R)的任意一个满足的任意一个满足函数依赖集函数依赖集F的关系实例的关系实例r都有都有 =r，其中，其中r1(R1)、r2(R2)分别为分解后的子模式，则称该分解对于分别为分解后的子模式，则称该分解对于F是是无损连接无损连接的。的。n无损连接分解能够根据分解后的关系通过连接来还原原来无损连接分解能够根据分解后的关系通过连接来还原原来的关系实例。的关系实例。n
6、如何判定一分解是否是无损的？如何判定一分解是否是无损的？无损连接分解判断方法给定关系模式r(R)及函数依赖集F，则将r(R)分解成r1(R1)、r2(R2)的分解是无损连接分解，当且仅当F+包含函数依赖R1R2R1或R1R2R2。因此，当一个关系模式分解为两个关系模式时，该分解为无损连接分解的充要条件是两分解关系的公共属性包含r1(R1)的码或r2(R2)的码。无损连接分解判断举例n假设关系模式假设关系模式r(R)=r(A, B, C, D, E), F =ABC, CDE, BD, EA，则，则可将可将r(R)进行两种不同的分解：进行两种不同的分解：l分解分解1：r1(R1)=r1(A, B
7、, C)，r2(R2)=r2(A, D, E)；l分解分解2：r1(R1)=r1(A, B, C)，r2(R2)=r2(C, D, E)。n对于分解对于分解1，R1 R2A，且，且AR1，故此分解，故此分解是无损连接是无损连接分解分解。n而对于分解而对于分解2，R1 R2C，且，且CR1、CR2，故，故此分解此分解不不是无损连接分解是无损连接分解。保持依赖分解 关系数据库模式分解的另一个目标是保持依赖。给定关系模式r(R)及函数依赖集F，r1(R1), r2(R2), ., rn(Rn)为r(R)的分解。F在Ri的投影为闭包F+中所有只包含Ri属性的函数依赖的集合，记为Fi。即如果在Fi中，则
8、和的所有属性均在Ri中。称具有函数依赖集F的关系模式r(R)的分解r1(R1), r2(R2), ., rn(Rn)为保持依赖分解，当且仅当(F1F2Fn)+=F+。保持依赖分解判断举例设关系模式r(R)=r(A, B, C)，F =AB, BC，有两种分解：r1(R1)=r1(A, B)、r2(R2) =r2(B, C)r1(R1)=r1(A, B)、r2(R2) =r2(A, C)。显然，前一种分解是保持依赖分解；而后一种分解不是保持依赖分解，因为分解后，函数依赖BC既不能从F在R1的投影F1中推导出来，也不能从F在R2的投影F2中推导出来。范式概述基于函数依赖理论，关系模式可分成第一范式
9、(1NF)第二范式(2NF)第三范式(3NF)Boyce-Codd范式(BCNF)这几种范式的要求一个比一个严格，它们之间的联系为BCNF3NF2NF1NF。即满足BCNF范式的关系一定满足3NF范式，满足3NF范式的关系一定满足2NF范式，满足2NF范式的关系一定满足1NF范式。第一范式(1NF) 如果一关系模式r(R)的每个属性对应的域值都是不可分的（即原子的），则称r(R)属于第一范式，记为r(R)1NF。第一范式的目标是：将基本数据划分成称为实体集或表的逻辑单元，当设计好每个实体后，需要为其指定主码。第二范式(2NF) 第二范式的目标是：将只部分依赖于主码（即依赖于主码的部分属性）的数
10、据移到其他表中。也就是说，在满足第一范式的实体中，如果有复合主码（即多个属性共同构成主码），那么所有非主属性必须依赖于全部的主码，而不能只是依赖于部分的主码属性。违背了2NF的模式，即存在非主属性对候选码的部分依赖，则可能导致例5.1所述的数据冗余及异常问题。对于非2NF范式的关系模式，可通过分解进行规范化，以消除部分依赖。如将关系模式SCE分解为关系模式S、C和E。这样在每个关系模式中，所有非主属性对候选码都是完全函数依赖，因此都属于2NF范式。2NF范式虽然消除了由于非主属性对主码的部分依赖所引起的冗余及各种异常，但并没有排除传递依赖。因此，还需要对其进一步规范化。Boyce-Codd范式
11、(BCNF) 给定关系模式r(R)及函数依赖集F，若F+中的所有函数依赖 (R，R)至少满足下列条件之一：是平凡函数依赖(即)；是r(R)的一个超码(即+包含R的全部属性)。即起决定作用的属性必须是超码！ 则称r(R)属于Boyce-Codd范式，记为r(R)BCNF。换句话说，在关系模式r(R)中，如果F+中的每一个非平凡函数依赖的决定属性集都包含候选码，则r(R)BCNF。特别说明：为确定r(R)是否满足BCNF范式，必须考虑F+而不是F中的每个依赖。从函数依赖角度可得出，一个满足BCNF的关系模式必然满足下列结论：所有非主属性都完全函数依赖于每个候选码；所有主属性都完全函数依赖于每个不包
12、含它的候选码；没有任何属性完全函数依赖于非候选码的任何一组属性。BCNF范式排除了：任何属性(包括主属性和非主属性)对候选码的部分依赖和传递依赖；主属性之间的传递依赖。Boyce-Codd范式判断举例例1 r(R)=r(A, B, C)，F=AB, BC。r(R)的候选码为A，r(R)BCNF，因为函数依赖BC中的决定属性B不是超码。例2 r(R)=r(A, B, C)，F=ABC, CA。r(R)的候选码为AB或BC，r(R)BCNF，因为CA的决定属性C不是超码。例3 r(R)=r(A, B, C)，F=ABC, BCA。r(R)的候选码为AB或BC，r(R)BCNF，因为两个函数依赖中的
13、决定属性AB或BC都是r(R)的候选码。Boyce-Codd范式存在问题对于非BCNF范式的关系模式，可通过分解进行规范化，以消除部分依赖和传递依赖。将例5.13中的r(R)分解为r1(R1)=r1(A, B)、r2(R2) =r2(B, C) 或r1(R1)=r1(A, B)、r2(R2) =r2(A, C)显然，这两种分解得到的r1(R1)和r2(R2)都属于BCNF范式。但是，后一种分解不是保持依赖分解（例5.12已分析）。因此，满足BCNF范式要求的模式分解，可能不是保持依赖分解。 第三范式(3NF) 给定关系模式r(R)及函数依赖集F，若对F+中的所有函数依赖 (R, R)至少满足下
14、列条件之一：是平凡函数依赖(即)；是r(R)的一个超码(即+包含R的全部属性)；-中的每个属性是r(R)的候选码的一部分。 则称r(R)属于第三范式，记为 r(R)3NF。3NF与BCNF范式的区别在于第3个条件。放松之处：允许存在主属性对候选码的传递依赖和部分依赖。 注意：3NF的第3个条件不要求 -中的每个属性必须包含在r(R)的一个候选码中，即中的每个属性可以包含在r(R)的不同候选码中第三范式的目标是：去掉表中不依赖于主码的数据。也就是说，在满足第二范式的实体中，非主属性不能依赖于另一个非主属性，即所有的非主属性应该直接依赖于全部的主属性（即必须完全依赖，这是2NF的要求），并且彼此之
15、间无相互依赖关系（即不能存在部分依赖，这是3NF的要求）。换一句话说，非主属性不能包括它们自己的属性，如果属性不包括属性，则它们就是真正的实体。3NF范式判断举例例1 r(R)=r(A, B, C)，F=AB, BC。r(R)的候选码为A，r(R)3NF，且r(R)BCNF。例2 r(R)=r(A, B, C)，F=ABC, CA。r(R)的候选码为AB或BC，r(R)3NF，但r(R)BCNF。例3 r(R)=r(A, B, C)，F=ABC, BCA。r(R)的候选码为AB或BC，r(R)3NF，且r(R)BCNF3NF与BCNF比较BCNF比3NF严格。BCNF要求所有的非平凡函数依赖中的是超码，而3NF则放松了该约束，允许不是超码。若关系模式属于BCNF范式就一定属于3NF范式。反之，则不一定成立。3NF存在数据冗余和异常问题，而BCNF是基于函数依赖理论能够达到的最好关系模式。BCNF范式分解是无损分解，但不一定是保持依赖分解；而3NF分解既是无损分解，又是保持依赖分解。 谢谢观看！谢谢观看！27 以上有不当之处，请大家给与批评指正，以上有不当之处，请大家给与批评指正，谢谢大家！谢谢大家！
