山东大学数据库07数据库设计.ppt

DATABASE SYSTEM CONCEPTS,第七章 关系数据库设计,提纲,7.1好的关系设计的特点 7.2原子域和第一范式 7.3使用函数依赖的分解 7.4函数依赖理论 7.5分解的算法 7.6使用多值依赖的分解 7.7更多的范式 7.8数据库设计过程 7.9时态数据建模,2019年4月18日星期四,2,数据库系统概念-关系数据库设计,2019年4月18日星期四,3,数据库系统概念-关系数据库设计,第七章 关系数据库设计,RDB设计工程方法的代表：E-R图方法 绘制E-R E-RRDB模式 模式优化 RDB设计工程方法的问题 E-R质量和分析员能力水平相关 E-R质量难以保证，致使E-R方法设计质量难以保证 其它RDB模式工程设计方法存在类似问题 质量保证 质量保证vs高质量 工程方法质量保证困难，受工程人员能力影响大 质量保证常用方法：机械化、形式化,2019年4月18日星期四,4,数据库系统概念-关系数据库设计,第七章 关系数据库设计,关系模式规范化研究的背景 为提高RDB设计质量保证，国外学者探寻和研究形式化的RDB设计方法 提出和完善了：关系模式规范化理论和方法 希望按照规范化理论和方法， 能够进行有质量保证的RDB设计 关系模式规范化的基本思路 泛关系Universal Relation 数据间的约束 按照机械算法，得到“好”的关系模式,2019年4月18日星期四,5,数据库系统概念-关系数据库设计,第七章 关系模式规范化理论和方法,模式规范化方法的研究状况 提出了模式规范化的标准： 1NF,2NF,3NF,BCNF,4NF,5NF,6NF 给出了泛关系分解到具体范式的算法 算法多为Np算法，无法实际执行 规范化方法学习价值 理解不同范式的优缺点 理解相应的模式改进方法 作为重要指导思想指导模式设计 本章讲述关系模式规范化理论、方法,2019年4月18日星期四,6,数据库系统概念-关系数据库设计,7.1好的关系设计,本节初步探讨好关系模式的特点 分析大模式的优缺点 分析小模式的优缺点,2019年4月18日星期四,7,数据库系统概念-关系数据库设计,7.1.1大关系模式分析,大模式示例： R(sno,sname,dno,dname) 大模式的缺点： 数据冗余大 容易出现数据不一致 插入异常-不能表示某些信息：没有学生的院系 删除异常 问题的本质： 两件事不应使用一个表来表示 应该将这个模式分解为两个模式 分解必须按照一定的策略，无序分解不可接受,2019年4月18日星期四,8,数据库系统概念-关系数据库设计,7.1 小关系模式分析,小模式 小模式不一定是好的模式 SC(sno,cno) TC(tno,cno) TS(tno,sno) 上述表不能表示上课(STC)信息 简单地模式变小不是追求目标,2019年4月18日星期四,9,数据库系统概念-关系数据库设计,7.1好的关系特点,大关系模式、小关系模式都有问题 好的关系模式： 该大则大，该小则小 同数据本质结构相吻合 不必存储不必要的重复信息，同时又可以方便地获取信息 如何得到好的关系模式？ 方法1：工程化方法 方法2：模式规范化 本章重点研究模式规范化方法,2019年4月18日星期四,10,数据库系统概念-关系数据库设计,7.2原子域和第一范式,原子域 域元素被认为是不可分的单元，称域是原子的 域原子性分析示例： 学号域2001CS621, 学号的编码规则决定了学号可以分段解释 (这是数据的客观特点，不能改变) 学号域是原子的吗？ 如果需要DBMS分段解释学号含义，则学号域不是原子域 否则，学号域是原子域,2019年4月18日星期四,11,数据库系统概念-关系数据库设计,7.2原子域和第一范式,1NF 如果关系模式R所有属性都源自原子域，称模式属于1NF 记作：R1NF 违背1NF的模式示例 存在属性不是原子的 R(SNO,SNAME,ADDR(CITY,STREET) 经典RDBMS中，不会出现如上非原子属性 存在某属性来自非原子域 如R(SNO,SNAME)，SNO源于学号域 学号域2001CS621需要DBMS分段解释值的含义 达不到1NF的缺点 不符合关系理论 编程困难 关系的规范化基础：1NF,2019年4月18日星期四,12,数据库系统概念-关系数据库设计,7.3使用函数依赖的分解,本节要点 函数依赖的定义 BCNF定义 BCNF与保持依赖的关系 3NF定义 7.3.5更高的范式(本小节略，我们将在7.7节讨论) 下一步学习 7.4.1-3:函数依赖的性质、理论 7.4.4-5:模式分解的基本性质、要求 7.5:BCNF、3NF的分解算法,2019年4月18日星期四,13,数据库系统概念-关系数据库设计,7.3.1函数依赖,函数依赖 设R(U)是属性集U上的关系模式，X , Y U， r是R(U) 上的任意一个关系，如果成立 对t , s r，若tX = sX，则tY = sY 那么称“X函数决定Y”，或“Y函数依赖于X”，记作XY 称X为决定因素 如S# SN， （S#，C#） G,2019年4月18日星期四,14,数据库系统概念-关系数据库设计,7.3.1函数依赖,函数依赖示例 对关系模式R(sno,sname,dno,dname)，分析下述函数依赖，哪些成立？哪些不成立？ snamesname dnamedname sname,dnamedname snosname,dno,dname snoR sno,snamedno dnodname snamesno sno,dnoR,2019年4月18日星期四,15,数据库系统概念-关系数据库设计,7.3.1平凡的函数依赖,对关系模式R(sno,sname,dno,dname)，下述函数依赖成立： snamesname dnamedname sname,dnamedname 平凡的函数依赖： 对所有关系模式R，如果，必有 当时，称是平凡(trivial)的函数依赖 否则，称为非平凡的函数依赖，称是的实质决定因素 思考：关系模式R上，平凡函数依赖的数量规模？,2019年4月18日星期四,16,数据库系统概念-关系数据库设计,7.3.1函数依赖对模式的约束,对关系模式R(sno,sname,dno,dname)，下述函数依赖成立： snosname,dno,dname sno,snamedno dnodname 函数依赖是对关系模式的约束 对关系实例r=(s1,甲,d1,计), (s2,乙,d1,数) 如果模式R没有指明dnodname，r R 如果模式R指明dnodname之后，r R 函数依赖限制了关系模式可能的实例 关系模式的表示 研究函数依赖后，关系模式描述应为四元组 R(U,D,dom,F) /F是R成立的函数依赖集合 关系模式常简单表示为： R(F),2019年4月18日星期四,17,数据库系统概念-关系数据库设计,7.3.1不成立的函数依赖,对关系模式R(sno,sname,dno,dname)，下述函数依赖不成立： snamesno 函数依赖是对模式的约束 函数依赖必须是现实语义约束的反映 也许在一些具体的关系示例上，snamesno成立 不能通过对实例数据的分析，总结模式上成立的函数依赖,2019年4月18日星期四,18,数据库系统概念-关系数据库设计,7.3.1函数依赖与码,对关系模式R(sno,sname,dno,dname)，下述函数依赖成立： snoR sno,dnoR 使用函数依赖定义码： 超码SuperKey： 对关系模式R， R，如果R,则为超码 候选码CandidateKey： 对关系模式R，为超码，如果任意的真子集 ，R不成立，则称为候选码,2019年4月18日星期四,19,数据库系统概念-关系数据库设计,7.3.1关系实例满足的函数依赖,关系实例满足的函数依赖 实例r满足的函数依赖： snosname snamesno 实例r不满足函数依赖： dnosname 实例满足的依赖 vs 模式上成立的依赖 关系模式R(F),如果rR(F),则： 1、R上成立的所有函数依赖，r必须满足； (否则，称rR(F) 2、r上满足的函数依赖， R上不一定成立；,2019年4月18日星期四,20,数据库系统概念-关系数据库设计,7.3.1关系实例满足的函数依赖,思考，如下关系实例r： r满足的函数依赖有哪些？ r不满足的函数依赖有哪些？,2019年4月18日星期四,21,数据库系统概念-关系数据库设计,7.3.2 BCNF定义,定义一： 对R(F)，如果R上成立的所有函数依赖，均有： 1) 或者 2)是超码 则称关系模式R为BCNF，记作RBCNF 定义二： 关系模式R(F)，如果(不包含于)成立，则必为超码，称RBCNF 。 定义三： 决定因素必含码 每个关系模式都属BCNF，则DB为BCNF。,2019年4月18日星期四,22,数据库系统概念-关系数据库设计,7.3.2 BCNF,判定：下列哪个模式是BCNF? R1(sno,sname,dno,dname) snosname,dno dnodname R2(sno,sname,cno,score) snosname sno,cnoscore R3(sno,pid,sname,sage,dept) sno pid,sname,sage,dept pid sno R4(sno,tno,cno) /F= R5(sno,tno,cno) tnocno sno,cnotno,2019年4月18日星期四,23,数据库系统概念-关系数据库设计,7.3.2 BCNF,BCNF的本质 (在只考虑函数依赖的前提下)只讲一件事 非码决定因素的相关决定关系讲述了另外一件事 R1(sno,sname,dno,dname) F:snosname,dno dnodname R1讲述了“学生”和“院系”两件事，R1(F)BCNF 有多个码是一件事的不同方面,本质仍是一件事 R3(sno,pid,sname,sage,dept) F:snopid,sname,sage,dept pid sno R3有两个码，讲述了”学生”一件事， R3(F)BCNF 思考：所有的二元联系都是BCNF吗？,2019年4月18日星期四,24,数据库系统概念-关系数据库设计,7.3.3BCNF和保持依赖,关系模式可以通过分解达到BCNF 示例： R(sno,sname,dno,dname) F:snosname,dno dnodname R(F)BCNF 分解R为R1,R2 R1(sno,sname,dno) F1=snosname,dno R2(dno,dname) F2=dnodname R1,R2 BCNF 分解效果良好,2019年4月18日星期四,25,数据库系统概念-关系数据库设计,7.3.3BCNF和保持依赖,有些关系模式分解BCNF会有问题 示例： R(sno,tno,cno) tnocno sno,cnotno R(F)BCNF 分解R为R1,R2 R1(sno,tno) F1= R2(tno,cno) F2=tnocno R1,R2 BCNF R1,R2 中不易验证sno,cnotno 保持依赖 通俗地说，不依靠关系连接就能验证依赖关系，称保持依赖 不是所有关系模式都能保持依赖地分解到BCNF,2019年4月18日星期四,26,数据库系统概念-关系数据库设计,7.3.4 3NF定义,定义一： 对R(F),如果对F+，必有 1) 或者 2)是超码 或者 3) (-)的每个属性均包含在某一候选码中 则称关系模式R为3NF，记作R3NF,2019年4月18日星期四,27,数据库系统概念-关系数据库设计,7.3.4 3NF,判定：下列哪个模式是3NF? R1(sno,sname,dno,dname) snosname,dno dnodname R2(sno,sname,cno,score) snosname sno,cnoscore R3(sno,pid,sname,sage,dept) sno pid,sname,sage,dept pid sno R4(sno,tno,cno) /F= R5(sno,tno,cno) tnocno sno,cnotno,2019年4月18日星期四,28,数据库系统概念-关系数据库设计,7.3.4 3NF,示例模式3NF判定结果： R1，R2：不是3NF R3，R4，R5：是3NF R53NF，因为R5中没有属性不属于候选码 R5(sno,tno,cno) tnocno sno,cnotno R5的候选码：(sno,cno)或(sno,tno),2019年4月18日星期四,29,数据库系统概念-关系数据库设计,7.3.4 3NF定义的注意问题,定义一：对R(F),如果对F+，必有 1) 或者 2)是超码 或者 3) (-)的每个属性均包含在某一候选码中 则称R3NF 注意： 定义中第3)点，不是：(-)包含在某一候选码中 例如：R(cno,cname,tno,sno) F: cnocname cnamecno cno,snotno tnocno,cname tnocno,cname中,cno,cname不包含在任何一个候选码, 但“(-)的任一个属性均包含在某一候选码中”,R(F)3NF,2019年4月18日星期四,30,数据库系统概念-关系数据库设计,7.3.4 3NF vs BCNF,BCNF是3NF的真子集 证明： 1、显然： BCNF 3NF 2、存在R(F)3NF, R(F) BCNF 例如： R5(sno,tno,cno) F: tnocno sno,cnotno,2019年4月18日星期四,31,数据库系统概念-关系数据库设计,7.3.4 3NF的其它定义,传递函数依赖定义(习题7.14) 关系模式R(F)， R， 属性AR，A： ，不函数决定，A,称A传递依赖于 否则，称称A直接依赖于 主属性定义 至少出现在一个候选码中的属性，称为主属性 否则，称为非主属性 3NF定义二 关系模式R(F)，没有非主属性传递依赖于码,称R(F)为3NF 3NF定义三 非主属性决定因素必含码 每个关系模式都属3NF，则DB为3NF,2019年4月18日星期四,32,数据库系统概念-关系数据库设计,7.3.5 更高的范式,我们将在7.7节中学习,2019年4月18日星期四,33,数据库系统概念-关系数据库设计,7.4函数依赖,本节要点 函数依赖集的闭包 逻辑蕴含 Armstrong公理系统 属性集的闭包 正则覆盖 无关属性 无损分解 保持依赖,2019年4月18日星期四,34,数据库系统概念-关系数据库设计,7.4.1函数依赖的推理规则,问题 给定一组函数依赖，是否能导出另外一些函数依赖，或另外的函数依赖是否成立。 如FD=A B，B C，A C是否成立？,2019年4月18日星期四,35,数据库系统概念-关系数据库设计,7.4.1逻辑蕴涵,定义 关系模式R，F是其函数依赖集，X，Y是其属性子集，如果从F中的函数依赖能够推出XY，则称F逻辑蕴涵XY，记作F XY,2019年4月18日星期四,36,数据库系统概念-关系数据库设计,7.4.1函数依赖集的闭包,定义 关系模式R(F)中，F逻辑蕴含的所有函数依赖的集合，称为F的闭包，记作F+ 关系模式R(F)成立的所有函数依赖的集合 F+的规模 Np，任何计算F+的算法一定是np 示例 R(X, Y), F = XY F+ = X， XX， XY， XXY，Y， YY，XY ，XYX，XYY，XYXY,2019年4月18日星期四,37,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,推理规则系统 正确的、完备的推理规则集 公理、定理、推论（如欧几里德集合） Armstrong公理 X，Y，Z是属性集， 自反律(reflexivity)：若Y X， 则X Y 增广律(augmentation)：若X Y ，则XZ YZ 传递律(transitivity)：若X Y，Y Z，则X Z,2019年4月18日星期四,38,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,Armstrong公理的正确性及完备性 A = f |可用Armstrong公理从F中导出的函数依赖f B = f |被F所逻辑蕴涵的函数依赖f 正确性：用Armstrong公理从F中导出的函数依赖必为F所蕴涵 A B 完备性：F所蕴涵的函数依赖都能用Armstrong公理从F中导出 B A,2019年4月18日星期四,39,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,关于Armstrong公理正确性,按函数依赖定义r是R上的任一关系，t，s r,2019年4月18日星期四,40,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,2019年4月18日星期四,41,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,2019年4月18日星期四,42,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,由Armstrong公理导出的推理规则 合并律(union rule) 若X Y，X Z，则X YZ 分解律(decomposition rule) 若X YZ ，则X Y，X Z 伪传递律(pseudotransitivity rule) 若X Y，WY Z，则WX Z,2019年4月18日星期四,43,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,2019年4月18日星期四,44,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,2019年4月18日星期四,45,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,2019年4月18日星期四,46,数据库系统概念-关系数据库设计,7.4.1 Armstrong公理系统,示例 R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, A H？ CG HI？ AG I？,2019年4月18日星期四,47,数据库系统概念-关系数据库设计,7.4.1 计算F+,F+=F repeat for each 函数依赖f in F+ 在f上应用自反律和增补律将结果加入到F+ for each 一对函数依赖f1和f2 in F+ if f1和f2可以使用传递律连接起来，将结果加入到F+ until F+不再发生变化,2019年4月18日星期四,48,数据库系统概念-关系数据库设计,7.4.1 计算F+,F=XY,Y Z, F+= X , Y , Z , XY , XZ , YZ , XYZ , X X, Y Y, Z Z, XY X, XZ X, YZ Y, XYZ X, X Y, Y Z , XY Y, XZ Y, YZ Z, XYZ Y, X Z, Y YZ, XY Z, XZ Z, YZ YZ, XYZ Z, X XY, XY XY, XZ XY, XYZ XY, X XZ, XY YZ, XZ XZ, XYZ YZ X YZ, XY XZ, XZ XY, XYZ XZ, X ZYZ, XY XYZ, XZ XYZ, XYZ XYZ,7.4.1 计算F+,算法的时间复杂性：NP 不可能有计算F+的多项式算法 计算闭包算法的特征 集合按照一定规则生长、直到不能再生长,2019年4月18日星期四,49,数据库系统概念-关系数据库设计,2019年4月18日星期四,50,数据库系统概念-关系数据库设计,7.4.2 属性集的闭包,要判断一个属性集X是否为超码，必须设计一个计算由X属性集函数确定的属性集的算法。办法之一是计算F+,2019年4月18日星期四,51,数据库系统概念-关系数据库设计,7.4.2 属性集的闭包,属性集的闭包,设F为属性集U上的一组函数依赖，X U， = A | XA能由F根据Armstrong公理导出 称 为属性集X关于函数依赖集F的闭包,2019年4月18日星期四,52,数据库系统概念-关系数据库设计,7.4.2 属性集的闭包,示例 属性集U=A，B，C， 函数依赖集F=A B，B C 则 A+ = ABC B+ = BC C+ = C,2019年4月18日星期四,53,数据库系统概念-关系数据库设计,判定XY是否能由F根据Armstrong公理导出，可转化为求 ，判定Y 是否成立,7.4.2 闭包的计算,问题：有没有一般性的算法判定XY是否能由F根据Armstrong公理导出？,如果计算出F+，再判断XY是否属于F+，则由于F+的计算非常复杂，实际上是不可行的,2019年4月18日星期四,54,数据库系统概念-关系数据库设计,开始：,Input：X，F，U Output： := X; while ( 发生变化）do for each 函数依赖 AB in F do begin if A then := B end,7.4.2 闭包的计算,算法（求属性集的闭包）,2019年4月18日星期四,55,数据库系统概念-关系数据库设计,7.4.2 计算+ ：算法正确性证明,证明：算法结束时，result= +(即Armstrong 公理完备性) 证明： 0)记算法结束时，result=A1A2Am，R-result=B1B2Bn 1)反证法；假设result+,必有result+，即： 必存在属性(不妨设该属性为B1) ：B1+,B1result； 2)构造如图所示关系r。 3)关系r满足F： 如不然，算法不会结束。 4)关系r不满足B1； 5) B1+,必有B1F+；r不满足F+。 6) r满足F，不满足F+，矛盾； 假设不成立，证毕。,2019年4月18日星期四,56,数据库系统概念-关系数据库设计,7.4.2 闭包的计算,示例1 R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH,计算 所用依赖 AB AGB AC AGBC CGH AGBCH CGI AGBCH I = AGBCH I,2019年4月18日星期四,57,数据库系统概念-关系数据库设计,示例2 R, U = (A, B, C, D, E), F = ABC, BD, CE, CEB, ACB,计算 所用依赖 ABC ABC BD ABCD CE ABCDE = ABCDE,7.4.2 闭包的计算,2019年4月18日星期四,58,数据库系统概念-关系数据库设计,7.4.2 闭包的计算,示例3 R, U = (A, B, C, D, E, G), F = AE, BEAG, CEA, GD,计算 所用依赖 AE ABE BEAG ABEG GD ABEGD = ABEGD,2019年4月18日星期四,59,数据库系统概念-关系数据库设计,7.4.2 闭包的计算,练习 R, U = (C, T, H, R, S), F = CT, HRC, HTR, HSR，HR是码吗？HS呢？,2019年4月18日星期四,60,数据库系统概念-关系数据库设计,7.4.2 属性集的闭包,算法作用： 1、判断属性集是否为超码 2、通过检验 +是否成立，可以验证函数依赖 是否成立 3、是另一种计算F+的方法：对任意的属性集，找出+ ，对于任意的属性集S + ，得到 S,2019年4月18日星期四,61,数据库系统概念-关系数据库设计,7.4.3正则覆盖(Canonical Cover),假设在一个关系模式上有一个函数依赖集F。当用户对于关系进行更新时，数据库系统将保证此操作不会破坏任何一个函数依赖,可以通过测试与给定函数依赖集有相同闭包的简化集的方式，来降低检测的开销,2019年4月18日星期四,62,数据库系统概念-关系数据库设计,7.4.3 函数依赖集的等价和覆盖,函数依赖集的等价性 函数依赖集F，G，若F+= G+，则称F与G等价。 若F与G等价，则称F是G的一个覆盖，G是F的一个覆盖。 F+ = G+ F G+，G F+,2019年4月18日星期四,63,数据库系统概念-关系数据库设计,7.4.3 正则覆盖,满足下列条件的函数依赖集F称为正则覆盖，记作Fc： Fc 与 F 等价 Fc 中任何函数依赖都不含无关属性 Fc 中函数依赖的左半部都是唯一的,2019年4月18日星期四,64,数据库系统概念-关系数据库设计,7.4.3 无关属性,如果去除一个函数依赖中的属性，不会改变该函数依赖集的闭包，则称该属性是无关的(extraneous),2019年4月18日星期四,65,数据库系统概念-关系数据库设计,7.4.3 无关属性,对于函数依赖集F及F中函数依赖 属性A在中是无关的，如果A，并且 F ( F - )(- A) 属性A在中是无关的，如果A ，并且 ( F - )( - A) F,2019年4月18日星期四,66,数据库系统概念-关系数据库设计,7.4.3 无关属性,在AB C，A C中 在AB CD， A C中,B在AB C中是无关属性 C在AB CD中是无关属性,2019年4月18日星期四,67,数据库系统概念-关系数据库设计,7.4.3 检验无关属性的方法,考虑中的属性A 如果A ，F= ( F - ( - A) ,检验A是否能由F推出，即计算F下的+，如果+包含A，则A在是无关的 如果A ，令 = -A，并计算 是否可以由F推出，即计算在F下的+，如果+包含的所有属性，则A在是无关的,2019年4月18日星期四,68,数据库系统概念-关系数据库设计,7.4.3 检验无关属性的方法,F=AB CD, A E, E C,C在AB CD上是否是无关属性？,F=AB D, A E, E C下AB的属性闭包为ABCDE，包含CD，因此C在AB CD上是无关属性,2019年4月18日星期四,69,数据库系统概念-关系数据库设计,7.4.3 正则覆盖,算法求函数依赖集F的正则覆盖FC REPEAT 合并和为 找出在、中含无关属性的函数依赖 删除中的无关属性 UNTIL F 不再改变 注意：检查无关属性是在当前Fc中的函数依赖，而不是F 不能同时讨论F中的两个属性的无关性，一次只能讨论一个属性,2019年4月18日星期四,70,数据库系统概念-关系数据库设计,7.4.3 正则覆盖,如果一个函数依赖的右半部只包含一个属性，例如， A C，并且右边的属性是无关的，那么将得到一个右部为空的函数依赖，这样的函数依赖应该删除 从某种意义上说， FC是最小的，它不含无关属性，并且具有相同左半部的函数都已经被合并，所以验证FC比验证F本身更容易,2019年4月18日星期四,71,数据库系统概念-关系数据库设计,7.4.3 正则覆盖,示例 F = ABC，BC，AB，ABC，求FC 合并ABC， AB为ABC A在ABC中是无关的 C在ABC中是无关的 因此FC = AB，BC,2019年4月18日星期四,72,数据库系统概念-关系数据库设计,7.4.3 正则覆盖,正则覆盖未必唯一 示例 F=ABC, BAC, CAB Fc1=AB, BC, CA Fc2=AB, BAC, CB Fc3=AC, CB , BA Fc4=AC, BC, CAB,2019年4月18日星期四,73,数据库系统概念-关系数据库设计,7.4.4无损连接& 7.4.5保持依赖,模式分解的定义 模式分解中的问题 无损连接分解 保持函数依赖的分解,2019年4月18日星期四,74,数据库系统概念-关系数据库设计,模式分解的定义,模式分解 函数依赖集合Fi = XY | XYF+ XY Ui称为F在Ui上的投影 关系模式R的一个分解是指 = R1 , R2, , Rn 其中U = Ui ，并且没有Ui Uj，1i，j n， Fi是F在Ui上的投影,2019年4月18日星期四,75,数据库系统概念-关系数据库设计,模式分解的定义,分解的基本代数运算 投影 自然连接 分解的目标 无损连接分解 保持函数依赖,2019年4月18日星期四,76,数据库系统概念-关系数据库设计,模式分解中存在的问题,R(A, B, C),AB(R),BC(R),AB(R),BC(R),R(A, B, C),AB(R),BC(R),AB(R),BC(R),有损分解,无损分解,2019年4月18日星期四,77,数据库系统概念-关系数据库设计,模式分解中存在的问题,A B, B C,=,插入,违反 B C,2019年4月18日星期四,78,数据库系统概念-关系数据库设计,模式分解中存在的问题,=,=,2019年4月18日星期四,79,数据库系统概念-关系数据库设计,无损连接分解,保持无损的模式分解 有损分解的例子,R(A, B, C),AB(R),BC(R),AB(R),BC(R),2019年4月18日星期四,80,数据库系统概念-关系数据库设计,无损连接分解,定义 关系模式R ，U = Ui ， = R1 , R2, , Rn是R的一个分解，r是R的一个关系定义m(r) = Ri(r) ,若对于R的任一个关系r，都有r = m(r)，则称是R的一个无损连接分解。,2019年4月18日星期四,81,数据库系统概念-关系数据库设计,无损连接分解,定理 在仅存在函数依赖的前提下，关系模式R(U)的分解=R1，R2，则是一个无损连接分解的充要条件是 R1R2R1R2或R1R2R2R1 成立,2019年4月18日星期四,82,数据库系统概念-关系数据库设计,无损连接分解,R=ABC, F=A B, =R1(AB), R2(AC) R1R2 = A, R1R2 = B 由A B ，得到是无损连接分解,2019年4月18日星期四,83,数据库系统概念-关系数据库设计,定理证明,定理证明： 只需证明当R1R2R1时，分解无损即可。 证明分解无损，即证明： rR, r=r(记r1= R1(r), r2= R1(r),r =r1 r2) 1、证明：r r (略) 2、证明：r r 记=R1R2,=R1-R2, =R2-R1 t r 必有t r1， t r2 由于r1= R1(r),必有t1 r 由于r2= R2(r),必有t2 r 又：在R上成立，得：= 即：t=t2 r ,证毕,2019年4月18日星期四,84,数据库系统概念-关系数据库设计,保持函数依赖的分解,保持函数依赖的模式分解 Z是U的子集，函数依赖集合F在Z上的投影定义为 Z(F) = XY | XYF+ XY Z 设 = R1, R2, , Rn是关系模式R的一个分解，如果F+ = ( Ri(F)+，则称是保持函数依赖的分解,2019年4月18日星期四,85,数据库系统概念-关系数据库设计,保持依赖,保持依赖示例一： R(sno,dno,dname) F=snodno,dnodname 子模式： R1(sno,dno) F1c=snodno R2(sno,dname) F2c=snodname R3(dno,dname) F2c=dnodname R1,R2 是无损连接分解，不保持依赖 R1,R3 是无损连接分解，保持依赖 思考： R还有其它无损、保持依赖的分解吗？,2019年4月18日星期四,86,数据库系统概念-关系数据库设计,保持依赖,保持依赖示例二： R(A,B,C) F=AB,BC, CA 分解R1(A,B),R2(B,C) 判定分解R1,R2是否保持依赖： F1c=AB,BA F2c=BC,CB Fc=AB,BAC,CB F F 分解R1,R2保持依赖 保持依赖 vs F(Ri(Ri) F(Ri(Ri),则一定保持依赖 保持依赖不一定有： F(Ri(Ri),2019年4月18日星期四,87,数据库系统概念-关系数据库设计,保持函数依赖的分解,关系模式R U = CITY, ST, ZIP, F = (CITY, ST) ZIP, ZIP CITY = R1 = ST, ZIP, R2 = CITY, ZIP R1R2 =ZIP, R2R1 =CITY R1R2 R2R1 分解是无损的 R1(F) = ， R2(F) = ZIP CITY R1(F) R2(F) = ZIP CITY 丢失了函数依赖(CITY, ST) ZIP,2019年4月18日星期四,88,数据库系统概念-关系数据库设计,保持函数依赖的分解,违反了函数依赖(CITY, ST) ZIP,2019年4月18日星期四,89,数据库系统概念-关系数据库设计,保持依赖 vs 无损连接,思考： 分解无损，一定保持依赖吗？ 分解保持依赖，一定无损吗？,2019年4月18日星期四,90,数据库系统概念-关系数据库设计,判定保持依赖,输入：D=R1，R2，Rn，F 计算F+ For each D中模式Ri do begin Fi := F+在Ri上的限定 end F:= For each Fi do begin F := F Fi end 计算F+ If F+= F+ then return(true) else return(false),2019年4月18日星期四,91,数据库系统概念-关系数据库设计,判定保持依赖,通过检查F中的每一个函数依赖都在分解后的某一个关系上成立，可以判断这个分解是否是保持依赖的。但是，有时分解是保持依赖的，但是F上的一个依赖不在分解后的任何一个关系上成立，也有可能是保持依赖的分解。只要F+ = (R1 F Rn F)+即可。因此这个验证只能是充分条件，必须寻找其他的判断方法,2019年4月18日星期四,92,数据库系统概念-关系数据库设计,判定保持依赖,为了避免计算F+，给出一种更有效的算法。思想如下：通过使用修改后的属性闭包的形式，判断F上的每一个函数依赖在分解中是否被保持,2019年4月18日星期四,93,数据库系统概念-关系数据库设计,保持函数依赖的分解,如何判断分解保持函数依赖？ 回忆： F+ = ( Fi)+ F ( Fi )+， Fi F+ 如对于ABC，AB , BC的分解， 思考：BCAB， AC+ ? 检验：C ？,2019年4月18日星期四,94,数据库系统概念-关系数据库设计,判定保持依赖,Input：Ri，F() Output：属性集 result= while (result 发生变化）do for each 分解后的Ri t=(result Ri)+ Ri result=result t 如果result包含了的所有属性，则保持函数依赖,2019年4月18日星期四,95,数据库系统概念-关系数据库设计,示例,示例： R(A,B,C) F=AB,BC, CA 判定分解R1(A,B),R2(B,C)是否保持依赖？ 关键是能否保持CA 按照算法三判定CA是否成立： result=C R1：result=C R2：result=C,B R1：result=C,B,A CA成立,2019年4月18日星期四,96,数据库系统概念-关系数据库设计,算法证明,证明：(仅证明是否被保持的判定是正确的) 证明：算法回答是,则一定保持依赖 显然result一直能被保持 证明：算法回答否,则一定不能被保持： 1、算法回答否,算法结束时，-result； 记result=A1A2Am R-result=B1B2Bn 构造如右关系r； 2、关系实例r的分解中所有子模式Ri,分别满足Fi; 3、关系实例r,不满足; 故：分解没有能保持依赖关系,2019年4月18日星期四,97,数据库系统概念-关系数据库设计,7.4.4-5无损分解&保持依赖,评价模式分解的两个重要指标 无损连接分解 & 保持依赖 无损连接分解 可以接受的分解必须是无损连接分解 分解有损，表明分解后的模式不能有效表示泛关系原来含有的全部信息，那么分解没有价值，有损分解是不可实际接受的 保持依赖 分解保持依赖，DBMS容易检查、确保函数依赖成立 分解不保持依赖， DBMS不易检查、确保函数依赖成立；但并不意味着数据一定有问题 保持依赖意味着分解更优，但不是分解必须具备的性质,2019年4月18日星期四,98,数据库系统概念-关系数据库设计,7.5 BCNF、3NF分解算法,本节要点 范式 7.5.1：BCNF BCNF的判定 子模式Ri 是否为BCNF的判定 BCNF分解算法 7.5.2：3NF 3NF的判定 3NF的分解算法 7.5.3：分解的目标 BCNF vs 3NF,2019年4月18日星期四,99,数据库系统概念-关系数据库设计,范式,定义 范式是对关系的不同数据依赖程度的要求 通过模式分解将一个低级范式转换为若干个高级范式的过程称作规范化（概念的纯粹化）,2019年4月18日星期四,100,数据库系统概念-关系数据库设计,1NF,定义 关系中每一分量不可再分。即不能以集合、序列等作为属性值,2019年4月18日星期四,101,数据库系统概念-关系数据库设计,2NF,关系模式S(S# , SN , SD , DEAN , C# , G) 不良特性 插入异常：如果学生没有选课，关于他的个人信息及所在系的信息就无法插入 删除异常：如果删除学生的选课信息，则有关他的个人信息及所在系的信息也随之删除 更新异常：如果学生转系，若他选修了k门课，则需要修改k次 数据冗余：如果一个学生选修了k门课，则有关他的所在系的信息重复,2019年4月18日星期四,102,数据库系统概念-关系数据库设计,2NF,定义 若R1NF，且每个非主属性完全依赖于码，则称R2NF 消除非主属性对码的部分依赖 如S2NF，因为,（S#，C#） SN （S#，C#） SD,2019年4月18日星期四,103,数据库系统概念-关系数据库设计,2NF,改造 非主属性有两种，一种完全依赖于码，一种部分依赖于码。 将S分解为： SC(S# , C# , G) S_SD(S# , SN , SD , DEAN),2019年4月18日星期四,104,数据库系统概念-关系数据库设计,3NF,S_SD(S# , SN , SD , DEAN) 不良特性 插入异常：如果系中没有学生，则有关系的信息就无法插入 删除异常：如果学生全部毕业了，则在删除学生信息的同时有关系的信息也随之删除了 更新异常：如果学生转系，不但要修改SD，还要修改DEAN，如果换系主任，则该系每个学生元组都要做相应修改 数据冗余：每个学生存储了所在系主任的信息,2019年4月18日星期四,105,数据库系统概念-关系数据库设计,3NF,定义 关系模式R中，若不存在这样的码X，属性组Y及非主属性Z(Z Y)，使得下式成立： XY , YZ , YX 则称R3NF 关系模式R中，对于属性组X，Y，若XY且Y X时至少有以下之一成立：X必含有码Y-X的每一个属性A都包含在R的候选码中，则称R3NF,2019年4月18日星期四,106,数据库系统概念-关系数据库设计,3NF,消除非主属性对码的传递依赖 如S_SD 3NF，因为有S#SD，SDDEAN 改造 将S_SD分解为 STUDENT(S# , SN , SD) DEPT(SD , DEAN),2019年4月18日星期四,107,数据库系统概念-关系数据库设计,BCNF,示例 STC(S# , T# , C#)， T# C#，每位老师只教授一门课 （S#，T#） C# （S#，C#） T#，学生选定一门课，就对应一位老师 （S#，T#），（S#，C#）为候选码。 思考 STC 3NF ？,2019年4月18日星期四,108,数据库系统概念-关系数据库设计,BCNF,不良特性 插入异常：如果没有学生选修某