《2015第十一章关系数据理论.ppt》由会员分享，可在线阅读，更多相关《2015第十一章关系数据理论.ppt（88页珍藏版）》请在三一办公上搜索。
1、第十一章:关系数据理论,问题的提出规范化数据依赖的公理系统关系模式的分解,问题的提出,由ER模型翻译为关系模式,得到的关系模式一定是好的吗?一个好的设计不一定导致一个好的关系模式ER的设计过程是主观的和复杂的有些约束用ER无法表示转换后的关系模式可能存在冗余,关系数据库设计中存在的问题,可以用ER模型来表示 enoeno,name,level,salary无法用ER模型来表示 levelsalary该约束引起冗余,例1：考虑为管理职工的工资信息而设计一个关系模式。,冗余导致的问题分类,插入异常如果没有职工具有8级工资，则8级工资的工资数额就难以插入。删除异常如果仅有职工赵明具有4级工资，如果将
2、赵明删除，则有关4级工资的工资数额信息也随之删除了。数据冗余职工很多，工资级别有限，每一级别的工资数额反复存储多次。更新复杂如果将5级工资的工资数额调为620，则需要找到每个具有5级工资的职工，逐一修改。,关系数据库设计中存在的问题,解决之道：模式分解,建立一个描述学生的数据库,一个系有若干学生,但一个学生只属于一个系一个系只有一名(正职)负责人一个学生可以选修多门课程,每门课程有若干学生选修每个学生学习每一门课程有一个成绩同一个系的同学被分配在同一个宿舍楼,面临的对象有学生号(S#)学生名(SN)学生宿舍(Loc)系名(Dept)系负责人(Dean)课程号(C#)成绩(Grade),现实世界
3、的已知事实告诉我们,建立一个描述学生的数据库,S#,C#,Dept,Loc,Grade,Dean,SN,例2：有关学生的关系模式 S(S#,SN,Loc,Dept,Dean,C#,Grade),关系数据库设计中存在的问题,例2：有关学生的关系模式 S(S#,SN,Loc,Dept,Dean,C#,Grade),关系数据库设计中存在的问题,存在的问题冗余太大:如SN,Loc,Dept,Dean删除异常:删除某系学生的选课将删除系信息插入异常:系刚成立,无学生;有学生,但未选课,S#,C#GradeS#SN,Loc,Dept,DeanDept LocDept Dean,例2：有关学生的关系模式 S
4、(S#,SN,Loc,Dept,Dean,C#,Grade)问题：它有哪些数据冗余？它有哪些不良的数据依赖？,关系数据库设计中存在的问题,例2：有关学生的关系模式 S(S#,SN,Loc,Dept,Dean,C#,Grade)结论：S(S#,SN,Loc,Dept,Dean,C#,Grade)不是一个好的关系模式原因：其中存在的数据依赖具有不好的性质一个好的关系模式应该具备以下四个条件 尽可能少的数据冗余 没有插入异常 没有删除异常 没有更新异常,关系数据库设计中存在的问题,S SC,例2：有关学生的关系模式S(S#,SN,Age,Dept,Dean,C#,Grade),讨论关系数据库逻辑设计
5、问题:针对一个具体问题，应该如何构造一个适合于它的数据库模式?针对一个关系模式，如何判断该模式 是否存在问题？应该构造几个关系模式?每个关系由哪些属性组成?规范化理论,规范化:为了控制由于冗余带来的问题而要求关系模式满足一定的范型，可以通过模式分解来达到，这一过程称之为规范化(Normalization),数据依赖,数据依赖实体内部各属性之间的联系,是现实世界属性间相互联系的抽象,体现在关系模式中的各属性之间相互依赖、相互制约的联系数据依赖种类函数依赖：最重要多值依赖连接依赖,函数依赖(Functional Dependency),关系模式中属性之间的一种逻辑依赖关系例如：S#与SN、Loc、
6、Dept之间都有一种函数依赖关系,由于一个S#只对应一个学生，而一个学生只能属于一个系，所以当SNO的值确定之后，SN、Loc，Dept的值也随之被唯一的确定了。这类似于变量之间的单值函数关系。设单值函数Y=F(X)，自变量X的值可以决定一个唯一的函数值Y。称 S#决定函数(SN,Loc,Dept)，或者说(SN,Loc,Dept)函数依赖于S#。,函数依赖的定义,设R是属性集U上的关系模式,X,Y是U的子集,若对于R的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值相等,而在Y上的属性值不等,则称“X函数确定Y”或“Y函数依赖于X”,记作XYX,Y含义:假定关系r,r1和r2是其中
7、两个元组,如果r1X=r2X=S1,从应用要求可知r1Y=r2Y=(赵亦,17,CS),即r1和r2是一个元组,则XYX,Y含义:若 X-SN,Y-Loc假定r1和r2是关系r中的两个元组,如果r1X=r2X=赵亦,从应用要求可知(重名)r1Y=一舍 而 r2Y=八舍,则X Y,X,S(S#,SN,Loc,Dept),函数依赖的定义,注意:函数依赖是指关系模式R的一切关系均要满足的约束条件;函数依赖和别的数据依赖一样是语义范畴的概念(只能从属性含义上加以说明,不能在数据上加以证明),关系中的所有元组应该满足的约束条件，而不是指关系中某个或某些元组所满足的约束条件当关系中的元组增加、删除或更新后
8、都不能破坏这种函数依赖语义确定属性之间的函数依赖，而不能单凭某一时刻关系中的实际数据值来判断例如，对于关系模式S，即使当前关系中没有重名的记录，也只能存在函数依赖S#SN，而不能存在函数依赖SNS#，因为可能有新增加的一个重名的学生,函数依赖的定义,一些记号和术语 若XY,则称X为决定因素若XY,YX,则记作XY若Y不函数依赖于X,则记作X Y非平凡函数依赖:若XY,但Y X,则称XY是非平凡的函数依赖平凡函数依赖:若XY,但Y X,则称XY是平凡的函数依赖,函数依赖的定义,完全函数依赖:在R中,如果XY,并且对于 X 的任何真子集X,都有X Y,则称Y对X完全函数依赖,记作X Y部分函数依赖
9、:如果XY,但Y不完全函数依赖于 X,则称Y对X部分函数依赖,记作X Y函数传递依赖:在R中,如果 XY,(Y X),Y X,YZ,则称Z对X传递函数依赖,关系模式,候选码:设K为R中的属性或属性组,若K U,则称K为候选码主码:若候选码为多个,选其中一个为主码 主属性:包含在任何一个候选码中的属性非主属性:关系模式的表示:一个关系模式可以表示成 R,根据讨论问题需要,以前简化表示为 R,现在简化表示为 R,范式（Normal Form）,规范化的基本思想是消除关系模式中的数据冗余，消除数据依赖中的不合适的部分，解决数据插入、删除时发生异常现象。范式是对关系的不同数据依赖程度的要求我们把关系数
10、据库的规范化过程中为不同程度的规范化要求设立的不同标准称为范式。通过模式分解将一个低级范式转换为若干个高级范式的过程称作规范化（概念的纯粹化）,范式,范式的概念最早由提出从1971年起，Codd相继提出了关系的三级规范化形式，即第一范式（1NF）、第二范式（2NF）、第三范式（3NF）1974年，Codd和Boyce共同提出了一个新的范式的概念，即Boyce-Codd范式，简称BC范式1976年Fagin提出了第四范式后来又有人定义了第五范式至此在关系数据库规范中建立了一个范式系列：1NF,2NF,3NF,BCNF,4NF,5NF，一级比一级有更严格的要求,一范式(1NF)：如果一个关系中的所
11、有属性值均是原子的，则称该关系满足1NF。关系模型中的关系必须满足1NF,规范化：一范式(1NF),Company(cno,cname,addr)Dept(dno,dname,cno)Employee(eno,dno,ename,salary),分量是否需要再分，与具体应用有关！如果用到值的一部分，则需要进一步分割。如果只是查询出生日期，则它满足1NF。如果查询两人生日是否相同，则只比较月、日，需要将生日分解，就不满足1NF。如果比较两人的生肖呢？,规范化：一范式(1NF),规范化：二范式(2NF),二范式(2NF):若R1NF,且每一个非主属性完全函数依赖于码,则称R2NF（即消除非主属性对
12、码的部分依赖）例子:关系模式S(S#,SN,Loc,Dept,Dean,C#,Grade)S2NF，因为(S#,C#)SN，(S#,C#)C#分解非主属性有两种，一种完全依赖于码，一种部分依赖于码将S分解为：SC(S#,C#,Grade)S_SD(S#,SN,Loc,Dept,Dean)练习:关系模式R(A,B,C,D)，码为AB，给出它的一个函数依赖集，使得R属于1NF而不属于2NF。,规范化：二范式(2NF),S_SD(S#,SN,Loc,Dept,Dean)不良特性插入异常：若系中没有学生，则有关该系的信息就无法插入。删除异常：如果学生全部毕业了，则在删除学生信息的同时有关该系的信息也随
13、之删除了。更新复杂：如果学生转系，不但要修改Dept，还要修改Dean，如果换系主任，则该系每个学生元组都要做相应修改。数据冗余：每个学生都存储了所在系的系主任的信息。,规范化：三范式(3NF),如果关系模式R2NF，且每一个非主属性不传递依赖于任一候选关键字，则称R3NF可以证明如果R3NF,则每一个非主属性既不部分依赖于码,也不传递依赖于码S_SD(S#,SN,Loc,Dept,Dean)如S_SD 3NF，因为有S#Dept，Dept Loc,Dean,即S#Loc,Dean,三范式(3NF):关系模式R中若不存在这样的码X,属性组Y以及非主属性组Z(Z Y),使得XY、YZ和Y X 成
14、立，则称R3NF。（即消除非主属性对码的传递依赖）,规范化：三范式(3NF),分解方案(1)将S_SD分解为：STUDENT(S#,SN,Dept)MANAGE(S#,Dean)LIVE(S#,Loc)(2)将S_SD分解为：STUDENT(S#,SN,Dept)DEPT(Dept,Loc,Dean)练习：关系模式R(A,B,C,D)，码为AB，给出它的一个函数依赖集，使得R属于2NF而不属于3NF。,好?,规范化:BCNF,BCNF(Boyce Codd Normal Form):关系模式R 1NF,若XY且Y X时,X必含有码,则R BCNF由定义可得到:所有非主属性对每一个码都是完全函数
15、依赖的所有主属性对每个不包含它的码也是完全函数依赖没有任何属性完全函数依赖于非码的任何一组属性,规范化,讨论:RBCNF,则R 3NF若R 3NF,则R未必属于BCNF 例如:关系模式STJ(S,T,J),其中每位教师T只教授一门课,每门课有若干教师担任,某一学生S选定一门课J,就对应一位固定的教师T,因此对应函数依赖可表示(S,J)T(S,T)J TJ,候选码为(S,J)和(S,T)结论:STJ 3NF,但STJBCNF存在的问题:插入异常,删除异常和冗余等问题规范化:解决办法是投影分解 ST(S,T)TJ(T,J),规范化,结论:一个模式中的关系模式如果都属于BCNF,那么在函数依赖的范畴
16、内,它已实现了彻底的分离,已消除了插入和删除异常3NF的不彻底性表现在可能存在主属性对码的部分依赖和传递依赖例如:(S,J)T,TJ:J对码的传递依赖,S,J,T,规范化：四范式(4NF),多值依赖:问题:属于BCNF的关系模式可能仍然存在一些问题,例如关系模式teaching(C,T,B),其中某一门课程C由多位教师T讲授,他们使用同一套参考书B,每位教师T可以讲授多门课程,每种参考书B可供多门课程使用,该模式的码为全码,分析该模式的一个关系,课程C 教师T 参考书B物理 李勇 普通物理物理 李勇 光学原理物理 李勇 物理习题集物理 王军 普通物理物理 王军 光学原理物理 王军 物理习题集数
17、学 李勇 数学分析数学 李勇 微分方程数学 李勇 高等代数数学 张平 数学分析数学 张平 微分方程数学 张平 高等代数,.,.,.,(物理,李勇),(物理,王军),Y X Z,(数学,李勇),(数学,张平),(物理,普通物理)李勇 王军(物理,光学原理)李勇 王军(数学,数学分析)李勇 张平.,规范化：四范式(4NF),V1,V2,V3,多值依赖样例一个员工（ENO）有多个服务（ORG-CODE）和多个分配（ASSIGN-NO）V1,V2:存在空值，无主码；V3：满足3NF,全码,数据冗余,规范化：四范式(4NF),多值依赖定义定义:设R是属性U上的一个关系模式,X、Y、Z是U的子集,并且Z=
18、U-X-Y,多值依赖X Y成立当且仅当对R的任一关系r,给定的一对(x,z)值有一组Y的值,这组值仅决定于x的值而与z的值无关形式化定义:在R的任一关系r中,如果存在元组t和s使得tX=sX,那么必然存在元组w,v r,(w,v可以与s,t相同)使得wX=vX=tX,而wY=tY,wZ=sZ vY=sY,vZ=tZ,记为:X Y,规范化：四范式(4NF),多值依赖的性质:多值依赖具有对称性:若X Y,则X Z函数依赖可以看作多值依赖的特例:若XY,则X Y若X Y,而Z=,则称X Y为平凡的多值依赖,规范化：四范式(4NF),4NF:关系模式R1NF,则R4NF需要满足：R中所有多值依赖X Y
19、，都是平凡的多值依赖；R中所有的函数依赖XY，X是关系R的码。关系模式teaching中存在非平凡的多值依赖,所以不属于4NF,规范化：四范式(4NF),存在的问题:如果一个模式已达到3NF,但不是4NF,问题是数据冗余太大解决办法:模式分解,消除非平凡的多值依赖 CT(C,T)CB(C,B)只有平凡的多值依赖,所以CT和CB都是4NF规范化小结:规范化目的:消除插入、删除异常，修改复杂和数据冗余等问题规范化实质：概念单一化规范化过程：通过对关系模式分解来实现,数据依赖的公理系统,数据依赖的公理系统是模式分解算法的理论基础Armstrong公理系统:函数依赖的一个有效而完备的公理系统逻辑蕴含:
20、对于满足一组函数依赖F的关系模式R,其中任何一个关系r,若函数依赖XY都成立,则称F逻辑蕴含XY一套推理规则(Armstrong公理系统):可以求得给定关系模式的码,可以从一组函数依赖求得蕴含的函数依赖,数据依赖的公理系统,Armstrong公理系统:设U为属性集总体,F是U上的一组函数依赖,于是有关系模式R,对R来说有以下的推理规则A1 自反律:若YXU,则XY为F所蕴含A2 增广律:若XY为F所蕴含,且ZU,则XZYZ 为F所蕴含A3 传递律:若XY和YZ为F所蕴含,则XZ为F所蕴含定理1:Armstrong推理规则是正确的,即如果F成立,则由F出发,根据Armstrong公理导出的函数依
21、赖总是正确的,数据依赖的公理系统,证明1:设YXU 对R的任一关系r中的任意两个元组t,s 若tX=sX,由YX 可得tY=sY 所以XY成立 证明2:设XY为F所蕴含,且ZU 对R的任一关系r中的任意两个元组t,s 若tXZ=sXZ,则有tX=sX和tZ=sZ 又XY成立,则有tX=sX和 tY=sY 所以tYZ=sYZ,所以XZYZ为F所蕴含,数据依赖的公理系统,证明3:设XY及YZ为F所蕴含 对R的任一关系r中的任意两个元组t,s 若tX=sX,由XY可得tY=sY 又YZ成立,则有tZ=sZ 所以XZ为F所蕴含根据上述推理规则得到另外的推理规则1合并规则:若XY 和XZ,则有XYZ2伪
22、传递规则:若XY和 WYZ,则有XWZ3分解规则:若XY及ZY,则有XZ,数据依赖的公理系统,引理1:XA1 A2.Ak成立的充分必要条件是X Ai成立(由合并规则和分解规则可以证明)定义2:F的闭包 在关系模式R中为F所蕴含的函数依赖的全体,记作F+定理2:Armstrong公理系统是有效的、完备的有效的/保真的:指由F出发,根据Armstrong公理导出的每个函数依赖一定在F+中(由定理1可证明)完备的:指F+中的每个函数依赖必定可由F出发,根据Armstrong公理推导出来,数据依赖的公理系统,由定理2可知,理论上是可以求得F+的,如果有F+,判断XY是否属于F+是非常容易的,但实际上由
23、F求F+有时几乎是不可能做到的,例如从 F=XA1,XA2,XAn 出发可以推导出2n个函数依赖定义3:设F为属性集U上的一组函数依赖,X U,XF+=A|X A能由F根据Armstrong公理导出,XF+称为属性集X关于函数依赖集F的闭包引理2(由引理1得出):设F为属性集U上的一组函数依赖,X,Y U,XY能由F根据Armstrong公理导出的充分必要条件是Y XF+,数据依赖的公理系统,判断XY是否能由F根据Armstrong问题,转化为求XF+,判断Y是否为XF+的子集问题求XF+算法(输入X,F,输出XF+)(1)令X(0)=X,i=0(2)求tmp,tmp=T|(v)(w)(v w
24、Fv X(i)Tw)(3)X(i+1)=tmp X(i)(4)判断X(i+1)=X(i)(5)若不等,i=i+1,返回(2)(6)若X(i+1)=X(i)或X(i)=U,则XF+=X(i),结束,找到左部为X子集的函数依赖,数据依赖的公理系统,例子:已知关系模式R,U=A,B,C,D,E,F=AB C,B D,C E,EC B,AC B 求(AB)F+(1)X(0)=AB,i=0(2)求tmp,tmp=CD(3)X(1)=tmpX(0)=ABCD(4)因为X(1)X(0),所以再找出左部为ABCD子集的那些函数依赖(5)tmp=CDEB(6)X(2)=tmpX(1)=ABCDE(AB)F+=A
25、BCDE,找到左部为X子集的函数依赖,数据依赖的公理系统,定义4:设F,G为两个函数依赖集,如果F+=G+,则称F和G是等价的,也称F覆盖G,或称G覆盖F,也可以说F和G互相覆盖引理3:F+=G+的充分必要条件为FG+和GF+证:必要性 F+=G+F+G+G+F+所以 F G+G F+充分性 F G+则F+(G+)+,但(G+)+=G+故F+G+同理可证 G+F+所以F+=G+,数据依赖的公理系统,引理3给出了测试函数依赖集F和G是否等价的方法:测试FG+和GF+是否成立 例如:测试FG+对每个函数依赖XY F,测试它是否在G+中,通过 计算X关于G的闭包XG+,然后测试Y XG+得到。,数据
26、依赖的公理系统,定义5:如果函数依赖集F满足下列条件,则称F为一个极小的函数依赖集,也称最小覆盖(1)F中的每个函数依赖的右部为单属性(2)F中不存在这样的函数依赖XA,使得F-XA 与F等价(3)F中不存在这样的函数依赖XA,使得F-XA ZA与F等价(Z X),数据依赖的公理系统,定理3:每个函数依赖集F均等价于一个极小的函数依赖集Fm,Fm称为F的最小覆盖 证明:只要能构造一个满足定义5中3个条件的覆盖Fm,定理得证(1)逐一检查F中的函数依赖XY,如Y=A1A2.Ak,则用XAi|i=1,2.,K取代XY(2)逐一检查XAi 令G=F-XAi,若Ai XG+则从F中去掉该函数依赖,对所
27、有的XAi检查并处理后,得覆盖G,G满足定义5中的(1)(2),数据依赖的公理系统,(3)检查G中每个函数依赖XAi,设X=B1B2.Bm,对Bj逐一做下列检查和处理 G与G-XAi(X-Bj)Ai是否等价 如等价,则以X-Bj取代X,如不等价,则X不变 所有的Bj检查完后,令最后的X为Z 并以G-XAiZ Ai 代替G G中每个XAi做如此检查后,设得函数依赖集G 显然G满足定义5中的3项,故令G为Fm,即Fm是可构造的,数据依赖的公理系统,关系模式R1和R2,如果F和G等价,那么R1的关系一定是R2的关系,所以在R中用与F等价的依赖集G来取代F是允许的,数据依赖的公理系统,求候选关键字的经
28、验方法：若属性A仅出现在所有函数依赖的右部，则它一定不包含在任何候选关键字中；若属性A仅出现在所有函数依赖的左部，则它一定包含在某个候选关键字中；若属性A既出现在函数依赖的右部，又出现在左部，则它可能包含在候选关键字中；在上述基础上求属性集闭包。,数据依赖的公理系统,给定关系模式R,求候选码 例子:对于R(ABCDE),F=AB,BC E,EDA求出R的所有候选关键字 如果K是关键字,则有K U,所以只要判断KF+=U 且KF+U(KK)CD一定包含在候选码中(CD)F+=CD(CDA)F+=ABCDE(CDB)F+=CDBEA(CDE)F+=CDEAB,练习,对于R(ABCD),对于下面的函
29、数依赖CD,CA,BC BC,DAABCD,DAAB,BCD,ACABC,ABD,CA,DB问题：上述每种情况的所有候选关键字,(B)F+=ABCD,(BD)F+=ABCD,(ABC)F+=(BCD)F+=ABCD,(A)F+=ABCD,(AB)F+=(AD)F+=(BC)F+=(CD)F+ABCD,模式分解,有时候为了控制由于冗余带来的问题以及插入和删除等问题要求关系模式满足一定的范型，可以通过模式分解来达到，这一过程称之为规范化(Normalization)有时候考虑到查询的效率，需要将满足较高范型的关系模式进行合并，这一过程称之为 Denormalization,模式分解,关系模式R(U
30、,F)的一个分解是指=R1,R2,Rn,其中U=ni=1Ui,并且没有UiUj,1i,j n,Fi是F在Ui上的投影Fi是F在Ui上的投影=XY|XYF+XYUi的最小函数依赖集模式分解的三个定义:朴素想法:一个关系分解成多个关系,相应的原来一个关系中的数据就要分散到多个关系中,要使分解有意义,就要求后者不能丢失前者的信息,模式分解,例子:已知R,其中U=S#,SD,MN F=S#SD,SD MN,由于R中存在传递函数依赖S#MN,会发生更新异常分解 1=R1,R2,R3 分解后Ri的关系ri是R的关系r在Ui上的投影,如果问S1在哪个系学习,此时变得无从知道,丢失了原来的信息结论：有损分解，
31、不保持函数依赖,模式分解,分解 2=R1,R2,通过自然连接,可以恢复r,无损分解(分解具有无损连接性):不丢失信息2不能解决插入、删除异常,由于丢失SDMN结论：无损分解、不保持函数依赖,模式分解,分解 3=R1,R2,通过自然连接,可以恢复r,保持函数依赖:不丢失函数依赖结论：无损分解、保持函数依赖,模式分解,结论:对一个模式的分解是多种多样的,但分解后产生的模式应与原模式等价,等价的三个不同定义:分解具有“无损连接性”分解要保持函数依赖分解既要保持函数依赖又要具有无损连接性定义3:设=R1,R2,Rn是R的一个分解,r是R的任意一个值,如果满足条件r=r1 r2,rn,其中ri=Ui(r
32、),称分解具有无损连接性或简称无损分解,模式分解,定义4:设=R1,R2,Rn是R的一个分解,如果 逻辑蕴含F,称分解保持函数依赖关系模式分解的两种准则 只满足无损分解:最基本的要求,发同样的查询得到查询结果相等即满足无损分解又满足保持函数依赖,模式分解,反例:只保持函数依赖,而不满足无损分解要求的分解.关系模式R(ABCD),设F=AB,CD,它的分解=R1(AB),R2(CD),分解无意义无损分解测试算法:检测一个分解是否无损分解输入:关系模式R(A1,A2,.,An)R上的函数依赖集F R上的分解=R1,R2,.,Rk输出:是否是无损分解步骤:,模式分解,属性,的K个关系模式,A1 A2
33、.Aj.AnR1R2Ri.Mi,j Rk,.,.,.,Mi,j=aj 若AjUi bij 若AjUi,(1)建立n列,k行的矩阵M,无损分解测试算法:检测一个分解是否无损分解输入:关系模式R(A1,A2,.,An),R上的分解=R1,R2,.,Rk R上的函数依赖集F=FD1,FD,FDi=XiAi输出:是否是无损分解步骤:,模式分解,(2)对F中的每个函数依赖XiAi反复进行下面 的检查和处理,直到矩阵M无变化为止 检查Xi中的属性所对应的列,找出Xi的取值相等的那些行,如果找到X相等的两行(或多行),把相应的Ai属性对应的分量取值改为一致,即如果其中之一为aj,则其他也改成aj,如果这两个
34、符号为bij和blj,将它们统一成bij或blj(3)当M无变化时,如果M中有一行变成了 a1,a2.,an,则是无损分解,否则不是,模式分解,例子:关系模式R(ABCDE)=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)是R的一个分解,在R上有下列函数依赖 F=A C,B C,C D,DE C,CE A,判别是否是无损分解 解:(1)建M,模式分解,=R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE)(2)对A C检查 b13,b23,b53 b13 对B C检查 b13,b33 b13,模式分解,对C D检查对DE C检查,模式分解,对CE A检
35、查再进行下去,M无任何变动,由于第三行已是全a,所以是无损分解,模式分解,定理:算法1可以正确判断一个分解是无损分解定理:关系模式R,分解=R1,R2具有无损连接性的充分必要条件为 U1U2U1-U2F+或U1U2U2-U1F+保持函数依赖分解测试算法:检测一个分解是否保持函数依赖输入:,F输出:是否保持函数依赖,R1和R2的公共属性部分必然包含R1或R2的key,模式分解,(1)令G=,检查G是否覆盖F(2)对F中的每个函数依赖XY进行下列检查 1)计算X关于G的闭包XG+,检查Y是否是XG+的子集 为了计算XG+,不必求出G,可以分别地,反复地计算Ui(F)(其中i=1,2,.,k)对XG
36、+所增加的属性 Z=X 判断Z是否与Ui有关 while Z有改变 do for i=1 to k do Z=Z(Z Ui)+Ui),Z中与Ui有关属性,是Ui(F)对XG+增加的属性,模式分解,经反复计算,直至Z不变 Z是XG+.如果YXG+,则XY G+2)如果F中的所有函数依赖都属于G+,则保持函数依赖例子:关系模式R(ABCD),F=AB,BC,CD,DA,判别=R1(AB),R2(BC),R3(CD)是否保持函数依赖解:U1(F)AB U2(F)BC U3(F)CD,F中的前三个函数依赖已明显在G中,只要检验DA是否为F所蕴含,模式分解,令 Z=D 第一遍:i=1 ZU1=D A,B
37、=Z不变 i=2 ZU2=D B,C=Z不变 i=3 ZU3=D C,D=D Z=D(D+C,D)=D(A,B,C,D C,D)=C,D,模式分解,第二遍:i=1 ZU1=C,D A,B=Z不变 i=2 ZU2=C,D B,C=C Z=C,D(C+B,C)=C,D(A,B,C,D B,C)=B,C,D i=3 ZU3=B,C,D C,D=C,D Z=B,C,D(C,D+C,D)=B,C,D(A,B,C,D C,D)=B,C,D,模式分解,第三遍:i=1 ZU1=B,C,D A,B=B Z=B,C,D(B+A,B)=A,B,C,D Z是全部属性集,不可能再改变 所以D+=A,B,C,D 因为A
38、D+所以DA G+所以保持函数依赖,模式分解,对数据库设计者来说两种重要的范式:3NF和BCNF 由于关系规范化要求不同,出现了不同的范式,其规范化条件越来越强,后面的范式可以看成是前面范式的特例。但在规范化时,不必按此步骤顺序去做,对于数据库设计者来说1NF和2NF并不重要一般来说属于3NF而非BCNF的关系模式不是很多,即使出现了这种关系模式,对数据库设计者来说,引起的更新异常往往也不是重要的,模式分解,例子:关系模式R(C,S,Z),其中C-city,S-street,Z-zip,R属于3NF而非BCNF问题:插入异常(如不知道街道)规范化:R1(Z,C)R2(S,Z),都为BCNF因为
39、(ZCSZ)(ZC-SZ)F+无损连接的分解但F中的CS Z将得不到保持R(C,S,Z)还是合理的,因为撇开街道,单纯表示Z与C的关系在应用中不是很必要的,CS,Z,码,非主属性,模式分解算法 BCNF,具有无损连接性的BCNF范式分解：=R检查中的每个关系模式是否为BCNF，若是算法终止设中Ri不属于BCNF,那么必存在XAFi+(AX),X不是Ri的码，对Ri进行分解：=S1,S2,Us1=XA,Us2=Ui-A,以代替Ri,返回第二步,假设R不符合BCNF.设R,A是R的单属性,XA违背了BCNF.将R分解为R1和R2,F是F在U-A上的投影.,模式分解算法BCNF,例如:关系模式STJ
40、(S,T,J),其中每位教师只教授一门课,每门课有若干教师担任,某一学生S选定一门课J,就对应一位固定的教师T F=(S,J)T(S,T)J TJ 候选码为(S,J)和(S,T)结论:STJ 3NF,但STJBCNFTJ违背了BCNF,则STJ分解为ST(S,T)和TJ(T,J),F在ST上的投影为,F在TJ上的投影为TJ,保持了无损连接性,但不保持函数依赖,模式分解算法BCNF,不能要求分解为BCNF的关系一定是保持函数依赖的例如:船员俱乐部中的reserve关系SBD(S,B,D)SBD(要求一名水手租用一条船的时间最多为一天)DB(每天只能外租一条船)SBD不符合BCNF,因为D不是KE
41、Y如果进行分解,则不能保持函数依赖SBD.,模式分解算法 3NF,保持函数依赖的3NF范式分解：算法1对R中的F进行最小化处理,得到Fm不在Fm中出现的属性组成一个关系模式,并从U中去掉这些属性,得Um若存在XAF,且XA=Um,则=R,终止算法否则，对于具有相同左部的函数依赖分成一组，假设有K组：记为F1,F2,Fk.Fi的所有属性构成Ui,若UiUj(ij),则去掉Ui,这样得到的一个分解=R1,R2,Rk 构成了R的一个保持函数依赖的分解,模式分解算法 3NF,具有无损连接性和保持函数依赖的3NF范式分解：算法2设X是关系模式R的关键字通过算法1得到一个分解=U R*若存在一个Uj,有X
42、Uj,则将R*从中去掉 是一个具有无损连接和保持函数依赖的3NF分解,模式分解算法-小结,若要保持函数依赖，模式分解总可以达到3NF，但不一定能达到BCNF若要保持函数依赖和具有无损分解性，模式分解也总可以达到3NF，但不一定能达到BCNF若要求具有无损分解性，模式分解总可以达到4NF,本章小结,概念函数依赖、关键字、1NF、2NF、3NF、BCNF、属性闭包、最小函数依赖集算法属性闭包的求解算法最小函数依赖集的求解算法关键字的判定方法1NF、2NF、3NF、BCNF的判定方法模式分解算法,本章练习,对于R(A,B,C,D),设AB是关键字，给定一个函数依赖集FD，使得R1NF,但R2NF对于
43、R(A,B,C,D),设AB是关键字，给定一个函数依赖集FD，使得R2NF,但R3NF对于R(A,B,C),BCF,设A是一个候选关键字，RBCNF可能吗？若可能需要什么条件？若不可能则为什么？对于R(ABCDE),F=AB,BC E,EDA求出R的所有候选关键字R3NF？RBCNF？,本章练习,对于R(ABCDEFGHI),分解得到下面的关系R1(ABCDE),AB,CD,ACER2(ABF),AB,BFR3(AD),R4(DCGH),DG,GH,CDR5(AICE),AI,IA,问题：上述子关系模式最高范式级别？如果不满足BCNF，进行分解,本章练习,对于R(ABCD),对于下面的函数依赖
44、CD,CA,BC BC,DAABCD,DAAB,BCD,ACABC,ABD,CA,DB问题：上述每种情况的所有候选关键字上述每种情况的最高范式级别？如果不满足BCNF，进行分解,练习,对于R(ABCD),对于下面的函数依赖CD,CA,BC BC,DAABCD,DAAB,BCD,ACABC,ABD,CA,DB问题：上述每种情况的最高范式级别？,Key=(B)非主属性传递FD 2NF,Key=(BD)非主属性部分FD 1NF,Key=(ABC)=(BCD)主属性传递3NF,Key=(A)非主属性传递FD2NF,(5)Key=(CD)=(AB)=(AD)=(BC)主属性传递3NF,练习答案,对于R(ABCD),对于下面的函数依赖CD,CA,BC BC,DAABCD,DAAB,BCD,ACABC,ABD,CA,DB问题：如果不满足BCNF，进行分解,(BC)(ACD),(BC)(AD),(ABC)(BCD),(BCD)(AD),(AC)(BD),
