函数依赖规范化省公共课一等奖全国赛课获奖课件.pptx

规范化第1页规范化必要性与主要性规范化在整个数据库设计知识结构中位置规划化处理问题第2页规范化在数据库概要设计中位置概念模型设计（E/R图）关系模型关系模型规范化模式定义，建立数据库第3页一个异常模式设计一个异常模式设计例：lending(branch_name,branch_city,asset(分支机构资产额)，customer_name,loan_number,amount)这个设计问题：这个设计问题：冗余：冗余：修改异常：修改修改异常：修改Branch_nameasset 插入异常：新增加一个分支机构插入异常：新增加一个分支机构删除异常：删除删除异常：删除 贷款号贷款号222结论：lending关系模式不是一个好模式。第4页“好好”模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。异常原因：异常原因：处理方法：处理方法：一个异常模式设计一个异常模式设计由存在于模式中一些一些数据依赖数据依赖引发经过分解分解关系模式来消除其中不适当数据依赖。第5页规范化理论规范化理论正是用来改造关系模式，经过分解关系模式来消除其中不适当数据数据依赖依赖，以处理插入异常、删除异常、更新异常和数据冗余问题。函数依赖函数依赖多值依赖多值依赖第6页重点内容函数依赖三种范式、BCNF范式模式分解第7页函数依赖1函数依赖定义2用函数依赖解释候选码、超码3函数依赖等价性4函数依赖推理规则5最小函数依赖集第8页1 函数依赖定义关关系系R上上函函数数依依赖赖：假如R两个元元组组在属属性性A1,A2,.An上一致（也就是说，两个元组在这些属性相对应各个分分量量含有相同值），则它们在另一个属性B上也应该是一致。记作：A1A2.AnBn关系：描述实体、属性、实体间联络。n从形式上看，它是一张二维表，是所包括属性笛卡尔积一个子集。元组：关系中每一行属性：关系中每一列分量：分量：属性在某个元组上取值第9页函数依赖举例Movie(title,year,length,filmType,studioName,starName）Title year-lengthTitle year-filmtypeTitle year-studioName简写：title year-length filmtypestudioName第10页函数依赖说明强调：函数依赖是针对关系模式，而不是特定实例。第11页2 用函数依赖解释候选码、超码假如一个或多个属性集合A1,A2,.An满足以下条件，就称该集合为关系R键码。1这些属性函数决定该关系全部其它属性。2A1,A2,.An任何真子集都不能函数决定R全部其它属性。第12页键码举例MovieStar(title,year,length,filmType,studioName,starName）属 性 组 title,year,starName组 成 了Movie关系键码。1.TitleyearstarName-lengthfilmType2.必须证证实实：title,year,starName任何真子集都不能函数决定全部其它属性。第13页键码举例首先：观察title和year不能决定starName，因为很多电影有多个影星。year,starName也不是键码，因为一个影星在同一年中可能出演多部电影，所以，year,starnametitle不是函数依赖。一样title,starName也不是键码。从而确定了title,year,starName是最小集合第14页关系键码（候选码）说明：有时一个关系有多个键码（候选码），这么话，通常要指定其中一个为主键码。第15页超键码包含键码（候选码）属性集称为“超键码superkey”,即键码超集（supersetofakey）。键码和超键码关系：每个键码都是超键码不过，某个超键码不是（最小）键码超键码满足键码第一个条件，不过不一定满足键码第二个条件。第16页寻找关系键码判断键码第第一一条条规规则则：来自实体集关系键码就是该实体集或类键码属性。例：Movie(title,year,length,filmtype)Stars(name,address)第17页寻找关系键码第第二二条条规规则则：假如关系R来自一个联络，则该联络多样性将会影响R键码。有三种情况：l假如联络是“多对多”，则相连两个实体集键码都是R键码属性。l假如是从实体集E1到实体集E2“多对一”联络，那么实体集E1键码属性是R键码属性，而E2键码属性则不是R键码属性。l假如联络是“一对一”，则联络两端任何一个实体集键码属性都是R键码属性，即R键码属性不是唯一。第18页寻找关系键码例：Movie(title,year,length,filmtype)多Studios(name,address)一Owns(title,year,studioName)Movie与Stars多对多Stars-in(主演)Stars-in(title,year,starName)第19页寻找关系键码多向联络情况：假如多向联络R有一个箭头指向实体集E，则对应关系中，除了E键码以外，最少还存在一个键码。第20页3 函数依赖等价性在不改变关系正当实例集条件下，函数依赖通常能够用几个不一样方式来表示。假如满足这种情况，我们就称这么函函函函数数数数依依依依赖赖赖赖集集集集是是是是等等等等价价价价（equivalent）。对于函数依赖集T，S，假如满足T中全部依赖每个关系实例都满足S中全部依赖，称函数依赖集S“蕴含于蕴含于蕴含于蕴含于followfrom”函数依赖集T.假如S蕴含于T，同时T也蕴含于S，则S和T两个函数依赖是等价等价等价等价。第21页4函数依赖规则分解分解/合并规则：合并规则：平凡依赖规则：平凡依赖规则：计算属性闭包：计算属性闭包：传递规则：传递规则：函数依赖闭包：函数依赖闭包：第22页分解分解/合并规则合并规则假如一组属性A1,A2,.An函数决定了多个属性，比喻说：A1A2.AnB1A1A,.AnB2.A,A,.AnBm能够把这一组依赖关系简记为：A1A2.AnB1,B2,Bm 第23页分解分解/合并规则合并规则反过来：反过来：能够把依赖关系：A1A2.AnB1,B2,Bm 分解为以下多个函数依赖：A1A2.AnB1A1A,.AnB2.A,A,.AnBm两种情况下，新依赖集等价于旧依赖集。两种情况下，新依赖集等价于旧依赖集。这个等价关系用于两个方向：分解这个等价关系用于两个方向：分解/合并合并第24页分解分解/合并规则证实合并规则证实已知各个单个依赖，证实合并后是成立已知合并后依赖，证实分解后是成立既：证实了它们相互蕴含，所以是等价第25页平凡依赖概念平凡依赖概念对于依赖：A1A2.AnB1,B2,Bm：假如B是A 子集，则称依赖为平凡依赖平凡依赖平凡依赖平凡依赖假如B中最少有一个属性不在A 中，则称该依赖为非平凡依赖非平凡依赖非平凡依赖非平凡依赖。假如B中没有一个属性在A中，则称该依赖为完完完完全非平凡依赖全非平凡依赖全非平凡依赖全非平凡依赖。例：平凡依赖平凡依赖 title,year-title 恒真恒真第26页平凡依赖规则平凡依赖规则函数依函数依赖赖A A1 1A A2 2.An.An BB1,1,B B2,2,B Bm m 等价等价于于A A1 1A A2 2.An.An CC1,1,C C2,2,C Ck k ,其中其中C C是是B B子子集，但属性集，但属性C C不在不在A A中出中出现现。第27页传递规则传递规则 传递规则使我们级联两个函数依赖。假 如 A1A2.An-B1B2.Bm和 B1B2.BmC1C2.Ck在关系R中成立，则A1A2.AnC1C2.Ck在R中也成立。第28页例326：已知关系R拥有属性A,B和C，它满足以下函数依赖：A-B和和B-C，则能够推断出则能够推断出R满足满足A-C。分析：分析：考查R任意两个在属性A上取值一致元组，证实它们在属性C上也取得一致。第29页证实传递规则假 设：存 在 在 属 性 A上 取 值 一 致 元 组（a,b1,c1,）和（a,b2,c2）。对应属性是A,B,C。满足：A-B,B-C。1.因为A-B,所以：b1=b22.又因为B-C，所以：c1=c23.结论：A-C第30页传递规则传递规则关系模式：Movie(title,year,length,filmType,studioName,studioAddr)下面两个依赖成立：titleyear-studioNamestudioName-studioAddr依据传递规则，能够得到一个新依赖：titleyear-studioAddr第31页计算属性闭包计算属性闭包定义：定义：假设A1,A2,.,An是属性集，S是函数依赖集。属性集A1,A2,.,An在依赖集S下闭包是这么属性集B，它使得满足依赖集S中全部依赖每个关系也都满足A1A2.An B。也就是说A1A2.AnB蕴含于S中函数依赖。用A1,A2,.,An+来表示属性集A1A2.An闭包。第32页计算属性闭包计算属性闭包求求闭闭包包过过程程：从给定属性集出发，一旦包含了某函数依赖左边属性，就把其右边属性增加进来，这么不停地扩展该集合。最终，当该集合再也无法扩展时，得到结果就是闭包。第33页计算属性闭包计算属性闭包求求解解属属性性集集A1,A2,.,An在某函数依赖集下闭包算法详细描述：1设设属属性性集集X最最终终将将成成为为闭闭包包。首首先先将将X初初始始化化为为A1,A2,.,An。2然然后后，重重复复地地搜搜索索某某个个函函数数依依赖赖B1B2.BmC,使得全部B1B2.Bm都在属性集X中，但C不在其中。于是将C加到属性集X中。3依依据据需需要要屡屡次次重重复复步步骤骤2，直直到到没没有有属属性性能能加加到到X中。中。4 最最 终终 得得 到到 不不 能能 再再 增增 加加 属属 性性 集集 X就就 是是 A1,A2,.,An+正确值。第34页计算属性闭包计算属性闭包例：某个关系，含有属性：A,B,C,D,E,F。假设该关系有以下函数依赖：AB-CBC-ADD-ECF-B问AB闭包是什么，即A,B+？第35页计算属性闭包计算属性闭包求解：初始化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不在X中，不能加入。A,B+=A,B,C,D,E第36页证实闭包算法有效性：证实闭包算法有效性：假设A1,A2,.,An是属性集，S是函数依赖集。初始：X=A1,A2,.,An最终要证实：最终要证实：A1A2.An-XD第37页证实闭包算法有效性证实闭包算法有效性假设已经得到了：X包含B1B2.Bm,准备利用依赖集S上一个依赖B1B2.BmD,将D加入到X中能够必定函数依赖：A1A2.An-X,只需要证实A1A2.An-D，则能够证实A1A2.An-XD因为X包含了B1B2.Bm，依据分解规则：A1A2,.An-B1A1A2.An-B2.A1A2.An-Bm再合并，能够得到：A1A2.An-B1B2.Bm。已知B1B2.BmD依据传递规则：满足A1,A2,.,An-D.第38页检验给定任一函数依赖检验给定任一函数依赖A1A2.AnBB是否蕴含于依赖集是否蕴含于依赖集S S 分分析析：依依据据属属性性集集闭闭包包定定义义，可可知知A1A2.AnA1,A2,.,An+蕴含于S。只要证实B在A1,A2,.,An+中，那么函数依赖A1A2.AnBB必定蕴含于依赖集S中。第39页检验给定任一函数依赖检验给定任一函数依赖A1A2.AnBB是否蕴含于依赖集是否蕴含于依赖集S S求解过程：求解过程：（1）利用依赖集计算闭包（2）假如B在闭包中，则函数依赖A1A2.AnB是否蕴含于依赖集S，不然不蕴含于s.第40页某个关系，含有属性：A,B,C,D,E,F。假设该关系有以下函数依赖：AB-CBC-ADD-ECF-B检验AB-D是否蕴含于这些函数依赖中。因为A,B+=A,B,C,D,E，D在集合中，所以AB-D蕴含于这些函数依赖中。第41页某个关系，含有属性：A,B,C,D,E,F。假设该关系有以下函数依赖：AB-CBC-ADD-ECF-B检验依赖：D-A是否蕴含于这些函数依赖中求闭包：D+=D,E，所以，D-A不蕴含于这些函数依赖中第42页Armstrong公理公理自反律：自反律：假如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第43页伪传递律伪传递律若A-B，BC-D则AC-D第44页基概念基基：任何一个能从中导出关系全部依赖给定依赖集称为该关系一个“基”。最最小小基基：假如一个基任何真子集都不能推导出该关系依赖全集，则称此基为最小基。第45页基概念举例例：关系R(A,B,C),其中每个属性都决定其它两个属性。所以推导依赖全集包含六个左、右各有一个属性依赖：A-BA-CB-AB-CC-AC-B还有三个左边有两个属性非平凡依赖：AB-CAC-BBC-A几个最小基：A-B,B-A,B-C,C-BA-B,B-C,C-A第46页函数依赖闭包给定函数依赖集F,能够证实其它一些函数依赖也成立，称这些函数依赖被F蕴含。令F为一个函数依赖集，F闭闭包包是是指指F逻逻辑辑蕴含全部函数依赖集合蕴含全部函数依赖集合。记为F+第47页求函数依赖闭包方法求函数依赖闭包方法，基于三个公理（Armstrong公理）或称函数依赖推理规则。经过重复使用这些规则，能够找出函数依赖集FF+第48页求函数依赖闭包例：R=(A,B,C,G,H,I)已知FA-B,A-C,CG-H,CG-I,B-H堆导得出：F+部分：A-HCG-HIAG-I第49页求函数依赖闭包问题：推导过程中可能会忽略一些依赖一个求函数依赖毕包思绪：逐一排查全部可能函数依赖，检验是否能够推导得出。第50页求函数依赖闭包例：R=(A,B,C,G,H,I)已知FA-B,A-C,CG-H,CG-I,B-H求F+：解：考查左边是单个属性依赖：A-H考查左边是两个属性依赖：AB-CAB-HAC-BAC-HAD-BAD-CAD-HAG-BAG-CAG-HAG-IAH-BAH-CAI-BAI-CAI-HBC-HBG-HBI-HCG-HCG-I考查左边是多了属性依赖：ABCABGABHABIACGACHACIAGHAGIAHIBCGBCHBCIBGHBGICGHCGIGHI.第51页函数依赖等价假如函数依赖集E中每一个函数依赖也在函数依赖集FF+中，即E中每一个依赖能够从F中推导得出，那么就称E被F覆覆盖盖，或者说F覆盖(cover)E。假如E+=F+话，两个函数依赖集E,F是等价（equivalent）。第52页怎样确定F是否覆盖E.问题问题：怎样确定F是否覆盖E.方法：对E中每个函数依赖X-Y,计算X关于FX+,然后检验这个X+是否包含Y中属性。假如E中每个函数都是X+包含Y中属性这种情况，那么F覆盖E。第53页确定F是否覆盖E已知：R(A,B,C)F=A-B,B-C,C-AE=B-A,A-C,C-A确定F是否覆盖E解：1.对于B-A，在F当中求B+=ABC,包含了A,也就是说B-A能够被F推导得出2.对于A-C，在F当中求A+=ABC,包含了C,也就是说A-C能够被F推导得出3.对于C-A，在F当中求C+=ABC,包含了A,也就是说C-A能够被F推导得出所以F覆盖了E第54页最小函数依赖集（最小基）满足以下条件函数依赖集F是最小：lF中每个依赖右边只含有单个属性。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第55页定理：每一个函数依赖集F均等价于一个极小函数依赖集。第56页例例：模式（A,B,C）,函数依赖集F：A-BCB-CA-BAB-C计算F最小函数依赖集：第57页1A-BCB-CA-BAB-C逐一检验F中各个函数依赖，使用分解规则，将依赖右边转换为单个属性A-BC:A-BA-C2逐一检验F中各个函数依赖X-A,令G=F-X-A,若A属于X关于G闭包，则从F中去掉此函数依赖。检验A-CB-CA-BAB-C3逐一取出F中各个函数依赖X-A,设X=B1B2.Bm,逐一考查Bi，若A属于（X-Bi）在F上闭包，则以X-Bi取代X。最终剩下F就是极小依赖集。B-CA-B第58页例已知：R(A,B,C)F=A-B,B-A,B-C,A-C,C-A计算最小函数依赖集A-B,B-C,C-AA-B,B-A,A-C,C-A第59页两种方式使用函数依赖1）用用于于指指明明正正当当关关系系集集上上约约束束。这么就能够只考虑码满足给定函数依赖集那些关系。假如希望只局限于模式R上满足函数依赖集F关系，我们说R上F成立2）用用于于检检测测关关系系是是否否在在给给定定函函数数依依赖赖集集上上正正当当。假如关系R在函数依赖集F上正当，则称R满足函数依赖集F.第60页举例例：假如现有数据能够反应关系函数依赖，找出全部可能函数依赖第61页函数依赖规则学习怎样推导函数依赖。即，已经知道某关系所满足函数依赖集，在不知道该关系详细元组情况下，通常能够推断出该关系必定满足其它一些函数依赖。第62页习题关系R=(A,B,C,D,E)函数依赖集FA-BCCD-EB-DE-A计算F闭包列出R候选码计算B闭包计算最小覆盖集第63页第64页模式分解第65页一个异常模式设计从E/R到关系数据库转换时问题：数据冗冗余余,不能表示一些信息。例：lending(branch_name,branch_city,asset(分支机构资产额)，customer_name,loan_number,amount)这个设计问题：这个设计问题：冗余：冗余：修改异常：修改修改异常：修改Branch_nameasset 删除异常：删除删除异常：删除 贷款号贷款号222第66页异常设计问题已知函数依赖：Branch_name-branch_city不过没有函数依赖：Branch_name-Loan_number一个分支机构位于一个城市与一个分支机构贷了一笔款是两个独立事实。这个设计另一个问题是不能直接表示相关一个分支机构信息第67页消除异常消除异常一个可行方法：“分解分解”关系。R分解方法：把R属性分开，以组成两个新关系模式。或对R元组进行投影，增加新关系。怎样选择一个能消除异常分解方法选择一个能消除异常分解方法?第68页消除异常将lending模式分解：假如lending被分解成以下两个模式：Branch_customer=(branch_name,branch_city,asset,customer_name)Customer_loan=(Customer_name,Loan_number,ammout)第69页消除异常问题：找出金额大于15元贷款全部分支机构关系代数处理：branch_name(ammount15（branch_customercustomer_loan）)第70页消除异常结果:A,C两家更深入结果：无法确定用户从哪家分支结构贷了多少款，所 以 实 际 上 是 丢 失 了 信 息。称 Lending 到Branch_Customer和Customer_Loan分解为有有损损分分解解，或者有损连接分解有损连接分解第71页消除异常错误分析：为何刚才分解是有损。原因公共属性：公共属性：Customer_name。这么表示信息有问题，因为一个客户可能有多笔贷款，而这些贷款不一定来自同一个分支机构。第72页消除异常重新分解：Branch=(branch_name,branch_city,assets)Loan_Info=(branch_name,Customer_name,Loan_number,ammount)分析：公共属性：Branch_namebranch_name-assetsbranch_city第73页模式分解对于一个模式分解是各种多样，不过分解后产生模式应与原模式等价详细说就是：分解含有分解含有“无损连接性无损连接性”LossLessjoin分解要分解要“保持函数依赖保持函数依赖”Preservedependency第74页模式分解模式分解评判标准：范式范式规范化：一个低一级范式关系模式，经过模式分解能够转换为若干个高一级范式关系模式集合，这种过程就叫做规范化规范化。第75页范式第一范式第二范式第三范式BC范式第四范式第76页第一范式第一范式：firstnormalform(1NF)要求属性域只能是原子（简单、不可分割）值，且元组中任何属性值必须是一个来自于该属性域单个值。第77页第二范式第第二二范范式式：每一个非主属性，完全函数依赖于码。非主属性非主属性：不是候选码组员完完全全函函数数依依赖赖：函数依赖X-Y是完全函数依赖条件是：从X中移去任何属性A就意味着依赖不再成立。第78页第三范式传传递递依依赖赖：关系模式R中函数依赖X-Y是传递函数依赖（transitivefunctionaldependency）条件是属性集Z既不是R候选码也不是R中任何码子集，且X-Z,Z-Y成立。对对于于第第三三范范式式了了解解：R中每一个非主属性，均满足以下两个条件：n完全地函数依赖于R每一个码n非传递依赖于R每一个码第79页BC范式BC范范式式（BoyeeCoddNormalForm）是由Boyce与Codd提出。BCNF定定义义：当当且且仅仅当当：只只要要非非平平凡凡依依赖赖A1A2.An-B1B2.Bm在在关关系系R中中成成立立，则则必必定定A1,A2,.,An是是R超超键码。满足该条件关系键码。满足该条件关系R就属于就属于BCNF。第80页分解为BCNF给定一个模式为A1,A2,.,An关系R，能够把R 分解成为两个关系S和T。模式分别为B1,B2,.,Bm和C1,C2,.,CK，使得：1 A1,A2,.,An=B1,B2,.,Bm C1,C2,.,CK2关系S中元组是R全部元组在B1,B2,.,Bm上投影。1关系T中元组是R全部元组在C1,C2,.,CK上投影。第81页一个存在异常设计一个存在异常设计 假如关系Movie键码是title,year，则该关系不是BCNF，因为titleyear-starName不成立。第82页消除异常例：分解上表中关系Movie。首先进行模式分解。我们选择下面两个关系：1一个关系称为Movie1，其模式是除了starName以外全部属性。2另一个关系称为Movie2，其模式是包含属性title,year和starName.第83页消除异常第84页消除异常分解结果中，Movie1(title,year,length,filmType,studioName)属于BCNF范式titleyear-lengthfilmTypestudioName第85页一个断言断言：任何双属性关系都属于BCNF。可能情形：1.没有非平凡函数依赖2.A-B3.B-A4.A-B和B-A第86页分解成BCNF经过分解，能够把任何关系模式分解成若干个属性子集，而这些子集有以下特征：1这些子集都属于BCNF关系模式2在某种意义上，分解后关系中数据如实地表示原始关系中数据。第87页分解成BCNF我们将要采取分解策略是寻找一个违反BCNF非平凡依赖：A1A2.An-B1B2.Bm也就是说A1,A2,.,An不是超键码。例：Movie(title,year,length,filmType,studioName,starName)键码：title,year,starName一个BCNF违例：title year-length filmTypestudioName第88页分解成BCNF依据这个违例分解Movie:1.包含了该依赖全部属性模式：包含了该依赖全部属性模式：title,year,length，filmType,studioName2.包包含含除除了了该该依依赖赖右右边边三三个个属属性性之之外外全全部部Movie属属性性模模式式。所以，除去length,filmType和studioName,得到第二个模式：title,year,starName第89页分解成为BCNF举例（1）MovieStudiotitle,year,length,filmType,studioName,studioAddr已知依赖集：titleyear-studioNamestudioName-studioAddrtitleyear-lengthfilmType存在问题：数据可能出现冗余传递依赖第90页分解成为BCNF举例（1）(1)找到键码title,year是一个键码(2)一个违反BCNF依赖。依赖studioName-studioAddr 是非平凡依赖。不过，它 studioName 并不是超键码。所以，Moviestudio不属于BCNF第91页分解成为BCNF举例（1）(3)分解：studioName,studioAddrtitle,year,length,filmType,studioName第92页分解成为BCNF举例（2）例：模式：title,year,studioName,president,presAddr三个函数依赖：titleyear-studioNamestudioName-presidentpresident-presAddr该关系唯一键码：title,year有两个非平凡函数依赖违反了BCNF规则所以不属于BCNF第93页分解成为BCNF举例（2）应用依赖传递规则：studioName-presAddr把两个依赖和起来：studioName-president,presAddr分解：title,year,studioName属于属于BCNFstudioName,president,presAddr 不不 属属 于于BCNF第94页分解成为BCNF举例（2）因为，依据因为，依据studioName-president,presAddr,能够得出能够得出studioName是候选码是候选码而函数依赖：而函数依赖：president-presAddr违反违反了了BCNF。所以需要继续分解：所以需要继续分解：studioName,presidentpresident,presAddr第95页分解成为BCNF举例（2）最终分解结果：title,year,studioNamestudioName,presidentpresident,presAddr第96页分解为分解为BCNF关系且含有没有损连接性质算法已知：关系R和R上函数依赖集F1.令D:=R2.While(D中有不属于BCNF关系模式Q时)do 选择D中一个不属于BCNF关系模式Q；在Q 中找出一个违反BCNF范式函数依赖X-Y 把D中Q用两个关系模式（Q-Y）和(XY)第97页关于分解讨论函数依赖投影从分解中恢复信息第98页函数依赖投影找到分解得到关系中成立函数依赖为何要找分解得到模式当中成立函数依赖？目标：依据函数依赖，判断分解得到模式是否符合BCNF第99页函数依赖投影找到分解得到关系中成立函数依赖方法：假设把关系R分解为关系S和另一个关系。设F是已知R中成立依赖集。计算S中成立函数依赖集步骤是：考虑包含于S属性集每个属性集X。计算X+。对于满足以下条件每个属性B,函数依赖X-B在S中成立：1B是S一个属性2B属于X+，而且3B不属于X。第100页函数依赖投影例：设R模式为R（A,B,C,D）。给定函函数数依赖集：依赖集：A-B B-C设S(A,C)是R经过某种分解得到一个关系。我们来计算S中成立函数依赖。第101页函数依赖投影计算S属性集A,C每个子集闭包。首先计算：A+=A,B,C,因为B不在S中，而C在S中。所以断言A-C成立。计算C+：因为C不在已知依赖左边，所以，C+=C,得不到任何依赖。计算A,C+：=A,B,C：AC-CA-CA-AC-C第102页函数依赖投影例：考虑R(A,B,C,D,E)分解为S(A,B,C)和另一个关系。推导S依赖。设R函数依赖为：A-DB-E和DE-C首先，考虑A+=A,DA-D不是新依赖B+=B,EB-E不是新依赖C+=C没有新依赖A,B+=A,B,C,D,E得出新依赖：AB-C第103页从分解中恢复信息从分解中恢复信息讨论：考虑关系R，其模式为A,B,C函数依赖：B-C是BCNF违例。可可能能出出现现情情况况之之一一：存在另一个依赖A-B,形成传递依赖。在这种情况下，A是唯一键码。另另一一个个可可能能出出现现情情形形：B-C是唯一非平凡依赖。在这种情况下，A,B是唯一键码。第104页从分解中恢复信息从分解中恢复信息上述两种情况可能分解结果是：A,B和（B,C）设t是R一个元组:T=(a,b,c)。t在模式为A,B关系上投影是：(a,b)t在模式为B,c关系上投影是：(b,c)将这两个投影连接起来，得到原来t是可能。第105页从分解中恢复信息从分解中恢复信息另一个情况：R两个元组：t=(a,b,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)是原来关系中不存在元组第106页从分解中恢复信息从分解中恢复信息关于x讨论:因为B-C,所以，e=c,所以，结果依然是x=(a,b,c)对上面讨论推广：对于A,B,C是属性集情况，上面讨论依然成立。结论结论：假如我们按照前面介绍方法进行分解，则以全部可能方式对新关系元组进行连接就能够准确地恢复原始关系。第107页从分解中恢复信息从分解中恢复信息假如不是基于一个函数依赖对关系进行分解：则可能无法恢复原始关系。例：假设关系R模式为(A,B,C),这和上面一样，但依赖B-C不成立。R可能包含两个元组：第108页从分解中恢复信息从分解中恢复信息R在模式为A,B和B,C关系上投影分别是：第109页从分解中恢复信息从分解中恢复信息第110页无损分解无损分解讨论无损分解：设R为关系模式，将R分解为关系模式集R1R2.RnR=R1R2.Rn令r为模式R上关系，ri=Ri(r),即r1r2.rn是将R分解为R1R2.Rn对应数据库。总有：rr1r2.rn第111页无损分解无损分解为了得到无损分解，需要在可能关系集上加约束。令C表示数据库上约束集。假如对模式R上满足C全部正当关系r,都有r=R1(r)R2(r).Rn(r)则称关系模式R分解R1R2.Rn是关关于于R无损连接分解无损连接分解第112页无损连接分解判定无损连接分解判定（1）判定分解无损标准：令R为一个关系模式，F为R上函数依赖集。R1和R2为R分解。该分解为R无损连接分解条件是，只要F+中最少有以下函数依赖中一个：R1R2-R1R1R2-R2第113页无损连接分解判定（无损连接分解判定（1 1）例：lending(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-assetsbranch_cityLoan_number-amount,branch_name第114页无损连接分解判定（无损连接分解判定（1 1）证实是无损分解：证实是无损分解：先分解为：先分解为：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_citybranch_name-assets branch_citybranch_name-branch_name branch_name-branch_name 能够得到：能够得到：branch_name-branch_name assets branch_name-branch_name assets branch_citybranch_city第115页无损连接分解判定（无损连接分解判定（1 1）下一步：将Loan_Info分解为：Loan=(branch_name,loan_number,amount)Borrow=(customer_name,loan_number)LoanBorrow=Loan_number由Loan_number-amountbranch_name可得：Loan_number-LoanNumbermountbranch_name所以是无损连接分解第116页无损分解性质无损分解性质 假如R一个分解R1,R2,Rm是关于函数依赖F无损连接分解，并接Ri分解Q1,Q2,Rn含有关于F在Ri上投影无损连接性质，那么R分解R1,R2,Q1,Q2,Qn,.Rm就含有关于F无损连接性质。第117页分解为第三范式不属于BCNF关系模式和依赖例：假设关系Booking属性以下：属性以下：1Title,电影名2Theater,正在上映该电影电影院名3City,电影院所在城市合理函数依赖：theater-citytitlecity-theater（不在同一个城市同一个电影院中重复预定同一部电影票）第118页分解为第三范式确定键码：任何一个单独属性都不是键码显然title,city是键码是键码能够得到：titletheater-city得到另一个键码另一个键码title,theater出现了BCNF违例：theater-city第119页分解为第三范式分解：title,theatertheater,city第120页分解为第三范式连接得到了违反依赖titlecity-theater两个元组：该分解没有保持依赖第121页分解为第三范式处理这一问题方法：将BCNF限制稍微放宽一些，放宽后条件是“第三范式”假如对于任何非平凡依赖：A1A2.An-B，或者A1A2.An是超键码，或者B是某个键码组成部分，则关系R就是属于“第三范式”（3NF）。第122页分解为第三范式前面例子属于3NF。Booking(title,city,theater)依赖：theater-citytitlecity-theater求得超码两个：title,citytitle,theater依赖theater-city，左边即使不是键码，不过右边是键码一部分。第123页模式分解算法关于模式分解几个主要事实：l若要求分解保持函数依赖，那么模式分解总能够到达3NF,但不一定到达BCNF.l若要求分解既保持函数依赖，又含有没有损连接性，能够到达3NF,但不一定到达BCNF.l若要求分解含有没有损连接性，那一定能够到达4NF。第124页模式分解算法关系R,函数依赖集F算法1：（合成法）保持函数依赖F分解：确保3NFl对F进行“极小化处理”l找出不在F中出现属性，把这么属性组成一个关系模式R1,剩下属性依然记为R.l若有X-A