函数依赖规范化

1、整理课件1规范化整理课件2规范化的必要性与重要性规范化在整个数据库设计知识结构中的位置规划化解决的问题整理课件3规范化在数据库概要设计中的位置概念模型的设计（E/R图）关系模型关系模型规范化模式定义，建立数据库整理课件4一个异常模式设计一个异常模式设计 例：lending(branch_name,branch_city,asset(分支机构的资产额)，customer_name,loan_number,amount)这个设计的问题：这个设计的问题：冗余：冗余：修改异常：修改修改异常：修改Branch_name的的asset 插入异常：新增加一个分支机构插入异常：新增加一个分支机构删除异常：删除

2、删除异常：删除 贷款号贷款号222结论：lending关系模式不是一个好的模式。整理课件5“好好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。异常原因：异常原因：解决方法：解决方法：一个异常模式设计一个异常模式设计由存在于模式中的某某些数据依赖些数据依赖引起的通过分解分解关系模式来消除其中不合适的数据依赖。整理课件6 规范化理论规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数数据依赖据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。函数依赖函数依赖多值依赖多值依赖整理课件7重点内容函数依赖三种范式、BCNF范式模式分解整理课件8函数依赖1 函数

3、依赖定义2 用函数依赖解释候选码、超码3 函数依赖的等价性4 函数依赖的推理规则5 最小函数依赖集整理课件91 函数依赖的定义 关系关系R上的函数依赖：上的函数依赖：如果R的两个元组元组在属性属性A1,A2,.An上一致（也就是说，两个元组在这些属性相对应的各个分量分量具有相同的值），则它们在另一个属性B上也应该是一致。记作：A1 A2.An Bn关系：描述实体、属性、实体间的联系。n从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。元组：关系中的每一行属性：关系中的每一列分量：分量：属性在某个元组上的取值整理课件10函数依赖举例Movie(title,year,length,fi

4、lmType,studioName,starName）Title year-lengthTitle year - filmtypeTitle year - studioName简写：title year - length filmtype studioName整理课件11函数依赖说明强调：函数依赖是针对关系模式，而不是特定的实例。整理课件122 用函数依赖解释候选码、超码如果一个或多个属性的集合A1,A2,.An满足如下条件，就称该集合为关系R的键码。1 这些属性函数决定该关系的所有其他属性。2 A1,A2,.An的任何真子集都不能函数决定R的所有其他属性。整理课件13键码举例MovieSta

5、r(title,year,length,filmType,studioName,starName）属性组title,year,starName构成了Movie关系的键码。Title year starName-length filmType必须证明证明：title,year,starName的任何真子集都不能函数决定所有其他的属性。整理课件14键码举例首先：观察title 和year不能决定starName，因为很多电影有多个影星。year,starName也不是键码，因为一个影星在同一年中可能出演多部电影，因此，year,starnametitle不是函数依赖。同样title,starNam

6、e也不是键码。从而确定了title, year,starName是最小的集合整理课件15关系的键码（候选码）说明：有时一个关系有多个键码（候选码），这样的话，通常要指定其中一个为主键码。整理课件16超键码 包含键码（候选码）的属性集称为“超键码 superkey”,即键码的超集（superset of a key）。键码和超键码的关系：每个键码都是超键码但是，某个超键码不是（最小的）键码超键码满足键码的第一个条件，但是不一定满足键码的第二个条件。整理课件17寻找关系的键码 判断键码的第一条规则第一条规则：来自实体集的关系的键码就是该实体集或类的键码属性。例：Movie(title,year,l

7、ength,filmtype)Stars(name,address)整理课件18寻找关系的键码第二条规则第二条规则：如果关系R来自一个联系，则该联系的多样性将会影响R的键码。有三种情况：l如果联系是“多对多”的，则相连的两个实体集的键码都是R 的键码属性。l如果是从实体集E1到实体集E2的“多对一”联系，那么实体集E1的键码属性是R的键码属性，而E2的键码属性则不是R的键码属性。l如果联系是“一对一”的，则联系两端的任何一个实体集的键码属性都是R的键码属性，即R的键码属性不是唯一的。整理课件19寻找关系的键码例：Movie(title,year,length,filmtype) 多Studio

8、s(name,address) 一Owns(title,year,studioName)Movie 与 Stars 多对多 Stars-in(主演)Stars-in(title,year,starName)整理课件20寻找关系的键码多向联系的情况：如果多向联系R有一个箭头指向实体集E，则相应的关系中，除了E的键码以外，至少还存在一个键码。整理课件213 函数依赖的等价性 在不改变关系的合法实例集的条件下，函数依赖通常可以用几种不同的的方式来表示。如果满足这种情况，我们就称这样的的（equivalent）。对于函数依赖集T，S，如果满足T中所有依赖的每个关系实例都满足S中的所有依赖，称函数依赖集

9、S“ follow from”函数依赖集T.如果S蕴含于T，同时T也蕴含于S，则S和T两个函数依赖是的。整理课件224 函数依赖的规则分解分解/合并规则：合并规则：平凡依赖规则：平凡依赖规则：计算属性的闭包：计算属性的闭包：传递规则：传递规则：函数依赖的闭包：函数依赖的闭包：整理课件23分解分解/合并规则合并规则 如果一组属性A1,A2,.An 函数决定了多个属性，比方说：A1A2.An B1A1A,.An B2.A,A,.An Bm可以把这一组依赖关系简记为：A1A2.An B1,B2,Bm 整理课件24分解分解/合并规则合并规则反过来：反过来：可以把依赖关系：A1A2.An B1,B2,B

10、m 分解为下列多个函数依赖：A1A2.An B1A1A,.An B2.A,A,.An Bm两种情况下，新的依赖集等价于旧的依赖集。两种情况下，新的依赖集等价于旧的依赖集。这个等价关系用于两个方向：分解这个等价关系用于两个方向：分解/合并合并整理课件25分解分解/合并规则证明合并规则证明已知各个单个依赖，证明合并后是成立的已知合并后的依赖，证明分解后是成立的既：证明了它们互相蕴含，因此是等价的整理课件26平凡依赖概念平凡依赖概念 对于依赖：A1A2.An B1,B2,Bm：如果B是A 的子集，则称依赖为的如果B中至少有一个属性不在A 中，则称该依赖为的。如果B中没有一个属性在A中，则称该依赖为的

11、。例：平凡依赖平凡依赖 title,year-title 恒真恒真整理课件27平凡依赖规则平凡依赖规则函数依赖函数依赖A A1 1A A2 2.An B.An B1,1,B B2,2,B Bm m 等价等价于于A A1 1A A2 2.An C.An C1,1,C C2,2,C Ck k , ,其中其中C C是是B B的的子集，但属性子集，但属性C C不在不在A A中出现。中出现。 整理课件28传递规则传递规则 传递规则使我们级联两个函数依赖。如果A1A2.An -B1B2.Bm 和 B1B2.Bm C1C2.Ck在关系R中成立，则A1A2.AnC1C2.Ck在R中也成立。整理课件29例326

12、 ：已知关系R拥有属性A,B和C，它满足如下函数依赖：A-B和和B-C，则可以推断出则可以推断出R满足满足A-C。分析：分析：考察R的任意两个在属性A上取值一致的元组，证明它们在属性C上也取得一致。整理课件30证明传递规则假设：存在在属性A上取值一致的元组（a,b1,c1,）和（a,b2,c2）。对应的属性是A,B,C。 满足：A-B,B-C。由于A-B, 所以： b1= b2 又由于B-C， 所以：c1 =c2结论：A-C整理课件31传递规则传递规则关系模式：Movie(title,year,length,filmType,studioName,studioAddr)下面两个依赖成立：tit

13、le year-studioNamestudioName- studioAddr根据传递规则，可以得到一个新的依赖：title year - studioAddr整理课件32计算属性的闭包计算属性的闭包定义：定义：假设 A1,A2,.,An 是属性集， S 是函数依赖集。属性集A1,A2,.,An 在依赖集S下的闭包是这样的属性集B， 它使得满足依赖集S中的所有依赖的每个关系也都满足A1A2.An B。也就是说A1A2.An B蕴含于S中的函数依赖。用 A1,A2,.,An + 来表示属性集A1A2.An的闭包。整理课件33计算属性的闭包计算属性的闭包求闭包的过程：求闭包的过程： 从给定的属性

14、集出发，一旦包含了某函数依赖左边的属性，就把其右边的属性增加进来，这样不断地扩展该集合。最终，当该集合再也无法扩展时，得到的结果就是闭包。整理课件34计算属性的闭包计算属性的闭包求解属性集求解属性集 A1,A2,.,An 在某函数依赖集下的闭包的算法的详细描述：1 设属性集设属性集X最终将成为闭包。首先将最终将成为闭包。首先将X初始化初始化为为 A1,A2,.,An 。2 然后，重复地搜索某个函数依赖然后，重复地搜索某个函数依赖B 1B2.Bm C,使得所有的B 1B2.Bm都在属性集X中，但C不在其中。于是将C加到属性集X中。3 根据需要多次重复步骤根据需要多次重复步骤2，直到没有属性能加，

15、直到没有属性能加到到X中。中。4 最后得到的不能再增加的属性集最后得到的不能再增加的属性集X就是就是 A1,A2,.,An + 的正确值。整理课件35计算属性的闭包计算属性的闭包例：某个关系，具有属性：A,B,C,D,E,F。假设该关系有如下的函数依赖：AB-CBC-ADD-ECF-B问AB的闭包是什么，即A,B + ？整理课件36计算属性的闭包计算属性的闭包求解：初始化X: X=A,B从AB-C, A,B都在X中，将C加入。因此X=A,B,C从BC-AD, B，C都在X中，将A,D加入，因此 X=A,B,C,D从D-E, D都在X中，将E加入，因此 X=A,B,C,D,E从CF-B, 由于F

16、不在X中，不能加入。A,B +=A,B,C,D,E整理课件37证明闭包算法的有效性：证明闭包算法的有效性： 假设 A1,A2,.,An 是属性集， S 是函数依赖集。初始：X=A1,A2,.,An最终要证明：最终要证明：A1A2.An- X D整理课件38证明闭包算法的有效性证明闭包算法的有效性假设已经得到了：X包含 B 1B2.Bm ,准备利用依赖集S 上的一个依赖B 1B2.Bm D,将D加入到X中可以肯定函数依赖：A1A2.An-X, 只需要证明A1A2.An-D ，则可以证明A1A2.An- X D由于X包含了 B 1B2.Bm ，根据分解规则：A1A2,.An-B 1A1A2.An-

17、B2.A1A2.An-Bm再合并，可以得到：A1A2.An-B 1B2.Bm。已知B 1B2.Bm D根据传递规则：满足A1,A2,.,An-D.整理课件39检验给定的任一函数依赖检验给定的任一函数依赖A1A2.An BB是否蕴含于依赖集是否蕴含于依赖集S S 分析：分析： 根据属性集闭包的定义，根据属性集闭包的定义， 可可知知A1A2.An A1,A2,.,An + 蕴含于S。 只要证明B在 A1,A2,.,An + 中，那么函数依赖A1A2.An BB 肯定蕴含于依赖集S中。整理课件40检验给定的任一函数依赖检验给定的任一函数依赖A1A2.An BB是否蕴含于依赖集是否蕴含于依赖集S S求

18、解过程：求解过程： （1） 利用依赖集计算闭包（2） 如果B在闭包中，则函数依赖A1A2.An B是否蕴含于依赖集S，否则不蕴含于s.整理课件41某个关系，具有属性：A,B,C,D,E,F。假设该关系有如下的函数依赖：AB-CBC-ADD-ECF-B检验AB-D是否蕴含于这些函数依赖中。因为A,B +=A,B,C,D,E，D在集合中，所以AB-D蕴含于这些函数依赖中。整理课件42某个关系，具有属性：A,B,C,D,E,F。假设该关系有如下的函数依赖：AB-CBC-ADD-ECF-B检验依赖：D-A 是否蕴含于这些函数依赖中求闭包：D +=D,E ，所以，D-A 不蕴含于这些函数依赖中整理课件4

19、3Armstrong公理公理自反律：自反律：如果 B1,B2,.,Bm包含于 A1,A2,.,An ,则A1A2.An- B1B2.Bm是平凡依赖增长律：增长律：如果A1A2.An- B1B2.Bm，则对于任何属性集C1C2.Ck,A1A2.AnC1CC2.Ck- B1B2.BmC1C2.Ck传递律传递律：如果A1A2.An- B1B2.Bm，且B1B2.Bm-C1C2.Ck，则A1A2.An- C1C2.Ck整理课件44伪传递律伪传递律若A-B， BC-D 则 AC-D整理课件45基的概念 基：基：任何一个能从中导出关系的所有依赖的给定依赖集称为 该 关 系 的 一 个“基”。最小的基最小的

20、基：如果一个基的任何真子集都不能推导出该关系的依赖全集，则称此基为最小基。整理课件46基的概念举例例：关系R(A,B,C),其中每个属性都决定其他两个属性。因此推导的依赖全集包括六个左、右各有一个属性的依赖：A - B A-C B-AB-C C-A C-B还有三个左边有两个属性的非平凡依赖：AB-C AC-B BC-A几个最小的基：A-B,B-A,B-C,C-BA-B,B-C,C-A整理课件47函数依赖的闭包给定函数依赖集F,可以证明其他某些函数依赖也成立，称这些函数依赖被F蕴含。令F为一个函数依赖集，F的闭包是指的闭包是指F逻逻辑蕴含的所有函数依赖的集合辑蕴含的所有函数依赖的集合。记为F+

21、整理课件48求函数依赖闭包的方法求函数依赖闭包的方法，基于三个公理（Armstrong公理）或称函数依赖推理规则。通过反复使用这些规则，可以找出函数依赖集F的 F+ 整理课件49求函数依赖闭包例：R=(A,B,C,G,H,I)已知FA-B,A-C,CG-H,CG-I,B-H堆导得出：F+ 的部分： A-HCG-HIAG-I 整理课件50求函数依赖的闭包问题：推导过程中可能会忽略某些依赖一个求函数依赖的毕包的思路：逐一排查所有的可能的函数依赖，检查是否可以推导得出。整理课件51求函数依赖的闭包例：R=(A,B,C,G,H,I)已知FA-B,A-C,CG-H,CG-I,B-H求F+ ： 解：考察左

22、边是单个属性的依赖：A-H考察左边是两个属性的依赖：AB-C AB -H AC-B AC-H AD-B AD-C AD-H AG-B AG-C AG-H AG-I AH-B AH-C AI-B AI-C AI-HBC-H BG-H BI-H CG-H CG-I 考察左边是多了属性的依赖：ABC ABG ABH ABI ACG ACH ACIAGH AGI AHI BCG BCH BCI BGH BGI CGH CGI GHI. 整理课件52函数依赖的等价如果函数依赖集E中的每一个函数依赖也在函数依赖集F的 F+ 中， 即E中的每一个依赖可以从F中推导得出，那么就称E被F覆盖覆盖，或者说F覆盖(

23、cover)E。如果E+ = F+ 的话，两个函数依赖集E ,F是等价（ equivalent）的。整理课件53如何确定F是否覆盖E.问题问题：如何确定F是否覆盖E. 方法：对E中的每个函数依赖X-Y,计算X关于F的X+,然后检查这个X+是否包含Y中的属性。如果E中的每个函数都是X+ 包含Y中的属性这种情况，那么F覆盖E。整理课件54确定F是否覆盖E已知：R(A,B,C)F=A-B ,B-C,C-AE=B-A,A-C,C-A确定F是否覆盖E解：对于B-A ，在F当中求B+ =ABC,包含了A,也就是说B-A可以被F推导得出对于A-C ，在F当中求A+ =ABC,包含了C,也就是说A-C可以被F

24、推导得出对于C-A ，在F当中求C+ =ABC,包含了A,也就是说C-A可以被F推导得出因此F覆盖了E整理课件55最小函数依赖集（最小基）满足下列条件的函数依赖集F 是最小的：l F中每个依赖的右边只含有单个属性。l不能从F中删除任何依赖。（不存在这样的依赖，X-A, 使得F与F-X-A等价）l不能用依赖Y-A来替换F中的任意一个依赖X-A,其中Y是X的一个真子集。（不存在这样的依赖，X-A，Y是X 的真子集，使得F-X-A (Y-A) 与F等价）最小函数依赖集，也就是F的最小基Fmin 整理课件56定理：每一个函数依赖集F均等价于一个极小函数依赖集。整理课件57例例：模式（A,B,C）,函数

25、依赖集F：A-BC B-C A-BAB-C计算F的最小函数依赖集：整理课件581 A-BC B-C A-B AB-C逐一检查F中的各个函数依赖，使用分解规则，将依赖右边转换为单个属性 A-BC : A-B A-C2 逐一检查F中的各个函数依赖X-A, 令G=F-X-A,若A 属于X关于 G的闭包，则从F中去掉此函数依赖。检查 A-C B-C A-B AB-C3 逐一取出F中各个函数依赖X-A, 设X= B1B2.Bm ,逐一考察Bi ，若A 属于（X-Bi） 在F上的闭包，则以X -Bi 取代X。 最后剩下的F就是极小依赖集。 B-C A-B整理课件59例已知：R(A,B,C)F=A-B ,

26、B-A,B-C,A-C,C-A计算最小函数依赖集A-B, B-C, C-AA-B,B-A,A-C,C-A整理课件60两种方式使用函数依赖1） 用于指明合法关系集上的约束用于指明合法关系集上的约束。这样就可以只考虑码满足给定函数依赖集的那些关系。如果希望只局限于模式R上满足函数依赖集F的关系，我们说R上F成立2） 用于检测关系是否在给定函数依赖用于检测关系是否在给定函数依赖集上合法集上合法。如果关系 R在函数依赖集F上合法，则称R 满足函数依赖集F.整理课件61举例例：假如现有数据能够反映关系的函数依赖，找出所有可能的函数依赖整理课件62函数依赖的规则 学习如何推导函数依赖。即，已经知道某关系所

27、满足的函数依赖集，在不知道该关系具体元组的情况下，通常可以推断出该关系必然满足的其他某些函数依赖。整理课件63习题关系R=(A,B,C,D,E)函数依赖集FA-BCCD-EB-DE-A计算F的闭包 列出R的候选码计算B的闭包计算最小覆盖集整理课件64整理课件65模式分解整理课件66一个异常模式设计 从E/ R到关系数据库转换时的问题：数据冗余冗余,不能表示某些信息。例：lending(branch_name,branch_city,asset(分支机构的资产额)，customer_name,loan_number,amount)这个设计的问题：这个设计的问题：冗余：冗余：修改异常：修改修改异常

28、：修改Branch_name的的asset 删除异常：删除删除异常：删除 贷款号贷款号222整理课件67异常设计的问题已知函数依赖： Branch_name-branch_city但是没有函数依赖： B r a n c h _ n a m e -Loan_number 一个分支机构位于一个城市与一个分支机构贷了一笔款是两个独立的事实。这个设计的另一个问题是不能直接表示有关一个分支机构的信息整理课件68消除异常消除异常的一个可行的办法：“分解分解”关系。R的分解的方法：把R的属性分开，以构成两个新的关系模式。或对R 的元组进行投影，增加新关系。如何选择一个能消除异常的分解方法选择一个能消除异常的

29、分解方法?整理课件69消除异常将lending模式分解：假如lending被分解成下列两个模式：Branch_customer=(branch_name,branch_city,asset,customer_name)Customer_loan=(Customer_name,Loan_number,ammout)整理课件70消除异常问题：找出金额大于15元的贷款所有的分支机构关系代数解决：branch_name(ammount15（branch_customercustomer_loan）)整理课件71消除异常结果: A, C两家更深入的结果：无法确定用户从哪家分支结构贷了多少款，因此实际上是

30、丢失了信息。称Lending 到Branch_Customer和Customer_Loan的分解为有损分解有损分解，或者有损连接分解有损连接分解整理课件72消除异常错误分析：为什么刚才的分解是有损的。原因公共属性：公共属性：Customer_name。这样表示信息有问题，因为一个客户可能有多笔贷款，而这些贷款不一定来自同一个分支机构。整理课件73消除异常重新分解：Branch=(branch_name,branch_city,assets) Loan_Info=(branch_name,Customer_name,Loan_number,ammount)分析：公共属性：Branch_nameb

31、ranch_name-assets branch_city整理课件74模式分解对于一个模式的分解是多种多样的，但是分解后产生的模式应与原模式等价具体的说就是：分解具有分解具有 “无损连接性无损连接性” LossLess join分解要分解要“保持函数依赖保持函数依赖” Preserve dependency整理课件75模式分解模式分解的评判标准：范式范式规范化：一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫做规范化规范化。整理课件76范式第一范式第二范式第三范式BC范式第四范式整理课件77第一范式第一范式：first normal form (1

32、NF) 规定属性域只能是原子的（简单的、不可分割的）值，且元组中任何属性的值必须是一个来自于该属性域的单个值。整理课件78第二范式第二范式：第二范式：每一个非主属性，完全函数依赖于码。非主属性非主属性：不是候选码的成员完全函数依赖完全函数依赖：函数依赖X-Y是完全函数依赖的条件是：从X中移去任何属性A就意味着依赖不再成立。整理课件79第三范式传递依赖传递依赖：关系模式R中的函数依赖X-Y是传递函数依赖（transitive functional dependency）的条件是属性集Z既不是R的候选码也不是R中任何码的子集，且X-Z, Z-Y成立。对于第三范式的理解对于第三范式的理解：R中的每一

33、个非主属性，均满足以下两个条件：n 完全地函数依赖于 R 的每一个码n 非传递依赖于R 的每一个码整理课件80BC范式 BC范式范式 （Boyee Codd Normal Form ）是由Boyce 与Codd提出的。BCNF定义：定义：当且仅当：只要非平凡依赖当且仅当：只要非平凡依赖A1A2.An-B1B2.Bm 在关系在关系R 中中成立，则必然成立，则必然 A1,A2,.,An 是是 R 的的超键码。满足该条件的关系超键码。满足该条件的关系R就属于就属于BCNF。整理课件81分解为BCNF给定一个模式为 A1,A2,.,An 的关系R，可以把R 分解成为两个关系S和T。模式分别为 B1,B

34、2,.,Bm 和 C1,C2,.,CK ，使得：1 A1,A2,.,An = B1,B2,.,Bm C1,C2,.,CK 2 关 系 S 中 元 组 是 R 的 所 有 元 组 在 B1,B2,.,Bm 上的投影。1 关 系 T 中 元 组 是 R 的 所 有 元 组 在 C1,C2,.,CK 上的投影。整理课件82一个存在异常的设计一个存在异常的设计 如果关系Movie的键码是title,year，则该关系不是BCNF，因为 title year -starName不成立。整理课件83消除异常例：分解上表中的关系Movie。首先进行模式分解。我们选择下面两个关系：1 一个关系称为Movie1

35、，其模式是除了starName以外的所有属性。2 另一个关系称为Movie2，其模式是包括属性title,year和starName.整理课件84消除异常整理课件85消除异常分解结果中，Movie1(title, year, length, filmType, studioName) 属于BCNF范式 title year - length filmType studioName整理课件86一个断言断言：任何双属性关系都属于BCNF。可能的情形：1.没有非平凡函数依赖2.A-B3.B-A4.A-B 和B-A整理课件87分解成BCNF通过分解，可以把任何关系模式分解成若干个属性子集，而这些子集有

36、如下特性：1 这些子集都属于BCNF的关系模式2 在某种意义上，分解后关系中的数据如实地表示原始关系中的数据。整理课件88分解成BCNF我们将要采取的分解策略是寻找一个违背BCNF的非平凡依赖：A1A2.An-B1B2.Bm 也就是说A1,A2,.,An 不是超键码。例：Movie(title,year,length,filmType,studioName,starName)键码：title, year, starName一个BCNF违例：title year - length filmType studioName整理课件89分解成BCNF根据这个违例分解Movie:1. 包含了该依赖所有属

37、性的模式：包含了该依赖所有属性的模式：title, year, length，filmType, studioName 2. 包含除了该依赖右边的三个属性之外的所包含除了该依赖右边的三个属性之外的所有有 Movie属性的模式。属性的模式。因此，除去length, filmType和studioName,得到第二个模式：title, year, starName整理课件90分解成为BCNF举例（1）MovieStudiotitle, year, length,filmType, studioName, studioAddr已知依赖集：title year - studioNamestudioNa

38、me - studioAddrtitle year - length filmType存在的问题： 数据可能出现冗余 传递依赖整理课件91分解成为BCNF举例（1）(1)找到键码 title , year 是一个键码(2) 一个违背BCNF的依赖。依赖studioName - studioAddr 是非平凡依赖。但是，它 studioName 并不是超键码。所以，Moviestudio不属于BCNF 整理课件92分解成为BCNF举例（1）(3)分解：studioName,studioAddrtitle, year, length, filmType, studioName整理课件93分解成为B

39、CNF举例（2）例：模式：title, year, studioName,president, presAddr三个函数依赖：title year - studioName studioName - president president - presAddr 该关系的唯一键码：title, year 有两个非平凡函数依赖违背了BCNF规则 所以不属于BCNF整理课件94分解成为BCNF举例（2）应用依赖传递规则：studioName -presAddr把两个依赖和起来：studioName - president, presAddr分解：title, year, studioName 属于属

40、于BCNFstudioName,president, presAddr 不属于不属于BCNF 整理课件95分解成为BCNF举例（2）因为，根据因为，根据 studioName - president, presAddr, 可以得出可以得出 studioName 是候选码是候选码而函数依赖：而函数依赖：president - presAddr 违背违背了了BCNF。所以需要继续分解：所以需要继续分解：studioName, presidentpresident, presAddr整理课件96分解成为BCNF举例（2）最终分解结果：title, year, studioNamestudioName

41、, presidentpresident, presAddr整理课件97分解为分解为BCNF关系且具有无损连接性质的算法已知：关系R和R上的函数依赖集F1.令D:=R2. While (D中有不属于BCNF的关系模式Q时) do 选择D中的一个不属于BCNF的关系模式Q； 在Q 中找出一个违背BCNF范式的函数依赖X-Y 把D中的Q用两个关系模式（Q-Y）和(XY)整理课件98关于分解的讨论函数依赖的投影从分解中恢复信息整理课件99函数依赖的投影找到分解得到的关系中成立的函数依赖为什么要找分解得到的模式当中成立的函数依赖？ 目的：根据函数依赖，判断分解得到的模式是否符合BCNF整理课件100函

42、数依赖的投影找到分解得到的关系中成立的函数依赖的方法：假设把关系R分解为关系S和另一个关系。设F是已知的R中成立的依赖集。计算S中成立的函数依赖集的步骤是：考虑包含于S的属性集的每个属性集X。计算X+ 。对于满足下列条件的每个属性B,函数依赖X-B在S中成立：1 B是S的一个属性2 B属于X+ ，而且3 B不属于X。整理课件101函数依赖的投影例：设R的模式为R（A,B,C,D）。给定的函数依赖集：函数依赖集：A - B B -C设S(A,C)是R经过某种分解得到的一个关系。我们来计算S中成立的函数依赖。整理课件102函数依赖的投影计算S的属性集A,C的每个子集的闭包。首先计算：A+ =A,B

43、,C,由于B不在S中，而C在S中。所以断言A-C成立。计算C+ ：因为C不在已知依赖的左边，所以，C+ =C,得不到任何依赖。计算A,C+ ：=A,B,C ：AC-C A-C A-A C- C整理课件103函数依赖的投影例：考虑R(A,B,C,D,E)分解为S(A,B,C)和另一个关系。推导S的依赖。设R的函数依赖为：A-D B-E 和 DE-C首先，考虑A+ =A,D A-D 不是新的依赖B+ =B,E B - E不是新的依赖C+ =C 没有新的依赖A,B+ =A,B,C,D,E 得出新的依赖：AB - C 整理课件104从分解中恢复信息从分解中恢复信息 讨论：考虑关系R，其模式为A,B,C

44、函数依赖：B-C是BCNF违例。可能出现的情况之一可能出现的情况之一：存在另一个依赖A-B,形成传递依赖。在这种情况下，A是唯一的键码。另一种可能出现的情形另一种可能出现的情形：B-C是唯一的非平凡依赖。在这种情况下，A,B是唯一的键码。整理课件105从分解中恢复信息从分解中恢复信息上述两种情况的可能分解结果是：A,B和（B,C）设 t 是R的一个元组:T=(a,b,c)。t 在模式为 A,B的关系上的投影是：(a,b)t 在模式为 B,c的关系上的投影是：(b,c)将这两个投影连接起来，得到原来的t是可能的。整理课件106从分解中恢复信息从分解中恢复信息另一种情况：R的两个元组：t=(a,b

45、,c) v=(d,b,e)t 在模式为 A,B的关系上的投影是：(a,b)t 在模式为 B,c的关系上的投影是：(b,c)v 在模式为 A,B的关系上的投影是：(d,b)v 在模式为 B,c的关系上的投影是：(b,e)连接得到了一个x=(a,b,e) 是原来的关系中不存在的元组整理课件107从分解中恢复信息从分解中恢复信息关于x的讨论:因为B-C, 所以，e=c,因此，结果仍然是x=(a,b,c)对上面讨论的推广：对于A,B,C是属性集的情况，上面的讨论仍然成立。结论结论：如果我们按照前面介绍的方法进行分解，则以所有可能的方式对新关系的元组进行连接就可以准确地恢复原始关系。整理课件108从分解

46、中恢复信息从分解中恢复信息如果不是基于一个函数依赖对关系进行分解：则可能无法恢复原始关系。例： 假设关系R的模式为(A,B,C),这和上面一样，但依赖B-C不成立。R可能包含两个元组：整理课件109从分解中恢复信息从分解中恢复信息R在模式为A,B和B,C的关系上的投影分别是：整理课件110从分解中恢复信息从分解中恢复信息整理课件111无损分解无损分解讨论无损分解：设R为关系模式，将R分解为关系模式集 R1R2.Rn R= R1R2. .Rn令r为模式R上的关系，ri = Ri (r) ,即 r1r2.rn 是将R分解为 R1R2.Rn 对应的数据库。总有： r r1 r2 . .rn整理课件1

47、12无损分解无损分解为了得到无损分解，需要在可能的关系集上加约束。令C表示数据库上的约束集。如果对模式R上满足C的所有合法关系r,均有r= R1 (r) R2 (r) . . Rn (r)则称关系模式R的分解 R1R2.Rn 是关于关于R的无损连接分解的无损连接分解整理课件113无损连接分解的判定无损连接分解的判定 （1）判定分解无损的标准： 令R为一个关系模式，F 为R上函数依赖集。R1 和R2 为R的分解。该分解为R的无损连接分解的条件是，只要F+ 中至少有如下函数依赖中的一个： R1 R2 - R1R1 R2 - R2整理课件114无损连接分解的判定（无损连接分解的判定（1 1）例：le

48、nding(branch_name,branch_city,asset，customer_name,loan_number,amount)分解结果： Branch=(branch_name,branch_city,assets) Loan=(branch_name,loan_number,amount) Borrow=(customer_name,loan_number)已知函数依赖：branch_name-assets branch_cityLoan_number-amount,branch_name整理课件115无损连接分解的判定（无损连接分解的判定（1 1）证明是无损分解：证明是无损分解

49、：先分解为：先分解为：Branch=(branch_name,branch_city,assets) Branch=(branch_name,branch_city,assets) Loan_Info=(branch_name,Customer_name,LoaLoan_Info=(branch_name,Customer_name,Loan_number,ammount)n_number,ammount) Branch Loan_Info = Branch_nameBranch Loan_Info = Branch_name由由branch_name-assets branch_citybr

50、anch_name-assets branch_citybranch_name-branch_name branch_name-branch_name 可以得到：可以得到： branch_name-branch_name assets branch_name-branch_name assets branch_citybranch_city整理课件116无损连接分解的判定（无损连接分解的判定（1 1）下一步：将 Loan_Info分解为： Loan=(branch_name, loan_number, amount) Borrow=(customer_name,loan_number)Loan

51、 Borrow = Loan_number由 Loan_number-amount branch_name 可得：Loan_number-LoanNumber mount branch_name所以是无损连接分解整理课件117无损分解性质无损分解性质 如果R的一个分解R1,R2,Rm是关于函数依赖F的无损连接分解，并接Ri的分解Q1,Q2,Rn具有关于F在Ri上的投影的无损连接性质，那么R的分解R1,R2,Q1,Q2,Qn,.Rm就具有关于F的无损连接性质。整理课件118分解为第三范式不属于BCNF的关系模式和依赖例： 假设关系Booking的属性如下：的属性如下： 1 Title, 电影名2

52、 Theater,正在上映该电影的电影院名3 City, 电影院所在的城市合理的函数依赖：theater -citytitle city -theater （不在同一个城市的同一个电影院中重复预定同一部电影的票）整理课件119分解为第三范式确定键码：任何一个单独属性都不是键码显然 title , city是键码是键码可以得到： title theater -city得到另一个键码另一个键码 title , theater出现了BCNF违例：theater -city整理课件120分解为第三范式分解：title, theater theater, city整理课件121分解为第三范式连接得到了违

53、背依赖title city - theater 的两个元组：该分解没有保持依赖整理课件122分解为第三范式解决这一问题的办法：将BCNF限制稍微放宽一些，放宽后的条件是“第三范式”如果对于任何非平凡依赖：A1A2.An-B ，或者 A1A2.An是超键码，或者B是某个键码的组成部分，则关系R就是属于“第三范式”（ 3NF）。 整理课件123分解为第三范式前面的例子属于3NF。 Booking(title,city, theater)依赖：theater -city title city -theater 求得的超码两个： title , city title , theater依赖theate

54、r -city ，左边虽然不是键码，但是右边是键码的一部分。整理课件124模式分解算法关于模式分解的几个重要事实：l 若要求分解保持函数依赖，那么模式分解总可以达到3NF,但不一定达到BCNF.l 若要求分解既保持函数依赖，又具有无损连接性，可以达到3NF,但不一定达到BCNF.l 若要求分解具有无损连接性，那一定可以达到4NF。整理课件125模式分解算法关系R ,函数依赖集F算法1：（合成法）保持函数依赖F的分解： 保证3NFl 对F进行“极小化处理”l 找出不在F中出现的属性，把这样的属性构成一个关系模式R1,剩余的属性仍然记为R.l 若有X-AF,且XA=R,则=R,算法终止。否则，对F

55、按照具有相同左部的原则分组，每一组函数依赖集所涉及的全部属性形成一个属性集Ui.若Ui包含于Uj当中，则将Ui去掉。整理课件126算法2：既保持函数依赖，又具有无损连接性的分解 保证3NFl 找出F 的最小覆盖Gl 对于每个出现在G中的函数依赖，为这个依赖的左边X在D中创建一个关系模式,其属性为XA1A2Ak,其中X-A1,X-A2,.X-An是G中仅有的X作为左边的依赖（X是这个关系的码）。l 如果D中没有任何一个关系模式包含R的码，那么就在D中再创建一个关系模式，其中要包含能形成R的码的属性。模式分解算法整理课件127多值依赖 整理课件128属性的独立性及其带来的冗余 某关系模式属于BCN

56、F，但该关系有和函数依赖无关的某种冗余。例：stars(name,street,city,title,year)整理课件129属性的独立性及其带来的冗余把地址和电影两个毫不相关的属性放在一起，出现数据冗余。判断该关系是否违背了BCNF：star的五个属性中，没有一个可以由其他的四个属性函数决定。所以，star中根本不存在非平凡依赖。结论：所有这五个属性组成唯一的键码，这个关系模式却没有BCNF违例。整理课件130多值依赖的定义 多值依赖是关于某个关系R的陈述，其含义是是如果确定了如果确定了R 在一个属性集的取值，则其他某在一个属性集的取值，则其他某些特定的属性的取值与该关系的所有其他属性些特定

57、的属性的取值与该关系的所有其他属性的取值无关。的取值无关。也就是说：如果我们限定了元组R，在属于A上的每个属性上取某特定的值，结果属于B的属性取值的集合与既不属于A, 也不属于B但属于R的属性取值的集合无关。多值依赖的表示： A1A2.An -B1B2.Bm整理课件131多值依赖的定义设关系R中在A的所有属性上的取值一致的每对元组t和u,我们可以在R中找到某个元组 V,满足：1.和t,u在A上的取值一致2.和t在B上的取值一致。3.和u在除了A和B之外R的所有属性上取得一致。整理课件132多值依赖的定义在这个规则中，t和u可以交换。结果是，对于A的任何固定值，B和其他属性的相关值在不同的元组中以所有可能的组合出