《关系模式的设计方案问题》由会员分享,可在线阅读,更多相关《关系模式的设计方案问题(51页珍藏版)》请在金锄头文库上搜索。
1、武汉大学数据库原理课题组4.1 关系模式的设计问题关系模式的设计问题4.2 关系模式的规范化关系模式的规范化4.3 数据依赖的公理系统数据依赖的公理系统4.4 关系模式的分解关系模式的分解第四章第四章 关系数据理论关系数据理论本章本章小结小结4.5 规范化的问题规范化的问题武汉大学数据库原理课题组4.1 关系模式的设计问题关系模式的设计问题如何对现实世界建模形成数据库模式?层次模型和网状模型:由设计者凭借经验进行建模,没有固定的规则和理论可循。关系模型:可以利用关系数据库的规范化理论来规范数据库的逻辑设计,使之更加合理。例:学生关系模式S(S#,SNAME,CLASS,C#,TNAME,TAG
2、E,ADDRESS,GRADE)其中主码是(S#,C#)武汉大学数据库原理课题组4.1 关系模式的设计问题关系模式的设计问题学生关系学生关系SS#SNAMECLASSC#TNAMETAGEADDRESSGRADES1刘力200101C1周文军38A178S1刘力200101C2曹立新27A164S2李军200101C1周文军38A185S2李军200101C2曹立新27A162S2李军200101C3罗晓52A285S3王林200102C1周文军38A172S3王林200102C3罗晓52A293S4沈国立200102C2曹立新27A172S4沈国立200102C3罗晓52A166S4沈国立2
3、00102C4周文军38A173问题?武汉大学数据库原理课题组4.1 关系模式的设计问题关系模式的设计问题学生关系S存在的问题:数据冗余度高学生与课程之间是多对多的关系,SNAME,CLASS,TNAME,TAGE,ADDRESS在S中需要被多次重复存储。数据修改复杂数据冗余导致数据修改复杂。插入异常没有选课之前学生不能被插入。删除异常如果删除某门课程的选课信息,该课程任课老师的信息也丢失。武汉大学数据库原理课题组4.1 关系模式的设计问题关系模式的设计问题问题产生的原因:S中存在多余的数据依赖(不够规范)解决:分解为四个关系ST, CT, TA和SC。STS#SNAMECLASSS1刘力20
4、0101S2李军200101S3王林200102S4沈国立200102CTC#TNAMEC1周文军C2曹立新C3罗晓C4周文军TATNAMETAGEADDRESS周文军38A1曹立新27A1罗晓52A2SCS#C#GRADES1C178S1C264S2C185S2C262S2C385S3C172S3C393S4C272S4C366S4C473武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化关系规范化的目的:关系规范化的目的:控制数据冗余、避免插入和删除异常控制数据冗余、避免插入和删除异常增增强数据库结构的稳定性和灵活性。强数据库结构的稳定性和灵活性。规范化过程:规范化过程:用结
5、构更单纯、规范的关系逐步取代原有关系。用结构更单纯、规范的关系逐步取代原有关系。一、函数依赖的概念一、函数依赖的概念数据依赖是实体内部各属性间的联系。分为:n函数依赖n多值依赖定义4.1: 属性集U上关系模式R(U),X、Y是U的子集,r是R的任一关系。若对于r中任意两个元组s,t有:由sX=tX可以得到sY=tY,称X函数决定Y或Y函数依赖X,记为XY。武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化注意:(1)函数依赖属于语义范畴,无法通过形式化证明;(2)关系模式所有的具体关系都需要满足关系模式的函数依赖。例例: 指出学生关系指出学生关系S中的函数依赖关系。中的函数依赖关
6、系。存在如下函数依赖:存在如下函数依赖:S#SNAME(每个学号只能有一个学生姓名每个学号只能有一个学生姓名)S#CLASS(每个学号只能有一个班级每个学号只能有一个班级)TNAMETAGE(每个教师只能有一个年龄每个教师只能有一个年龄)TNAMEADDRESS(每个教师只能有一个地址每个教师只能有一个地址)(S#,C#)GRADE(每个学生学习一门课程只能有一个成绩每个学生学习一门课程只能有一个成绩)C#TNAME(每门课程只能有一个老师教授每门课程只能有一个老师教授)武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化一般,函数依赖与属性间的关系有:(1)若X, Y是1:1关系
7、,则存在 XY或YX;(2)若X, Y是m:1关系,则存在 XY但不存在Y X;(3)若X, Y是m:n关系,则X,Y间不存在函数依赖关系。常用术语和记号:(1)XY,但Y X,则称XY是非平凡的函数依赖非平凡的函数依赖;(2)XY,但Y X,则称XY是平凡的函数依赖凡的函数依赖;(3)若XY,称X是决定因素决定因素;(4)若XY, YX,记作:X Y;(5)若Y不函数依赖于X,记作:X Y。 武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化定义4.2: 关系模式R(U),函数依赖的分类如下。n完全函数依赖: 是指 XY,且对任何X的真子集X, 都有X Y,记作:X Y。n部分
8、函数依赖: 是指XY,且存在XY, 记作:X Y。n传递函数依赖:是指若XY (Y X), Y X , 而Y Z。记作: X Z 。 FPT武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化例: 指出学生关系S中存在的完全和部分函数依赖。左部为单属性的函数依赖一定是完全函数依赖,所以S#SNAME, S#CLASS, TNAMETAGE, TNAMEADDRESS, C#TNAME都是完全函数依赖。(S#, C#)GRADE 是一个完全函数依赖,因为S#+GRADE且C#+GRADE。(S#, C#)SNAME,(S#, C#)CLASS,(S#, C#)TNAME,(S#, C
9、#)TAGE,(S#, C#)ADDRESS都是部分函数依赖,因为 : S#SNAME, S#CLASS, C#TNAME, C#TAGE,C#ADDRESS。武汉大学数据库原理课题组例: 试指出学生关系S中存在的传递函数依赖。因 为 C#TNAME, TNAME+C#, TNAMETAGE, 所 以C#TAGE 是一个传递函数依赖。C#ADDRESS也是一个传递函数依赖。二、码的精确定义二、码的精确定义 用函数依赖的概念来定义码。定义4.4: 设X为R中的属性或属性组合,若 X U 则X为R的候选码。说明:XU说明X能决定整个元组,X+U说明X中没有多余属性。4.2 关系模式的规范化关系模式
10、的规范化F武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化术语主码:被选中的候选码主属性:候选码中的属性非主属性:不在任何一个候选码中的属性全码:关系模式的整个属性组为码 例: R(顾客,商品,日期)例: 指出下列关系R中的候选码、主属性和非主属性关系R的候选码为:A,(D,E)关系R的主属性为:A,D,E关系R的非主属性:无 A D E a1 d1 e2 a2 d6 e2 a3 d4 e3 a4 d4 e4武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化三、函数依赖与基础范式关系的规范化是将一个低级范式的关系模式,通过关系模式的分解转换为若干个高级范式的过程。
11、(1)第一范式:1NF定义: 若R的每个分量都是不可分的数据项,则R1NF。 从型上看:不存在嵌套结构 从值上看:不存在重复组 1NF是关系模式的最低要求。例: 学生关系S(S#, SNAME, CLASS, C#, TNAME, TAGE, ADDRESS, GRADE)是1NF关系,但它存在数据冗余,插入异常和删除异常等问题。武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化(2)第二范式: 2NF 定义:若R1NF,且R中的每一个非主属性都完全函数依赖于R的任一候选码,则R2NF。例: 学生关系S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,G
12、RADE),候选码为(S#,C#)。非主属性和候选码之间的函数依赖关系:(S#, C#) SNAME,(S#, C#) CLASS,(S#, C#) TNAME,(S#, C#) TAGE,(S#, C#) ADDRESS, (S#, C#) GRADE由此可见,在这个关系中存在非主属性对候选码的部分函数依赖,所以S2NF。PPPPPF武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化分解为2NF的方法: 将满足部分函数依赖和满足完全函数依赖的属性分解到不同的关系中。例: 关系S分解为三个关系:ST(S#, SNAME, CLASS)(只依赖S#的属性分解到一个子模式中)CTA(
13、C#, TNAME, TAGE, ADDRESS) (只依赖C#的属性分解到另一个子模式中)SC(S#, C#, GRADE) (完全函数依赖于候选码的属性分解到第三个子模式中) 关系ST、CTA和SC都为2NF。若关系R的候选码是单属性的,则R必定是2NF。武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化达到2NF的关系仍然可能存在问题。例: 在关系CTA中还存在以下问题:数据冗余。一个教师承担多门课程时,教师的姓名、年龄、地址要重复存储。修改复杂。一个教师更换地址时,必须修改相关的多个元组。插入异常。一个新教师报到,需将其有关数据插入到CTA关系中,但该教师暂时还未承担任何
14、教学任务,则因缺码C#值而不能进行插入操作。删除异常。删除某门课程时,会丢失该课程任课教师的姓名、年龄和地址信息。武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化(3)第三范式: 3NF定义: 如果关系R的任何一个非主属性都不传递函数依赖于它的任何一个候选码,则R3NF。例: 关系CTA是2NF,但不是3NF。因为C#是候选码,TNAME、TAGE、ADDRESS是非主属性,由于C#TNAME,TNAME+C#,TNAMETAGE,所以C# TAGE ,同样有C# ADDRESS, 即存在非主属性对候选码的传递函数依赖。分解为3NF的方法:将涉及传递函数依赖中的两个依赖中的属性
15、分解到不同的关系中。例: 将CTA分解为:CT(C#, TNAME),TA(TNAME, TAGE, ADDRESS)则关系CT和TA都是3NF,关系CTA中存在的问题得到了解决。FF武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化(4)BCNF 定义: 关系模式R1NF。若函数依赖集合F中的所有函数依赖XY(YX)的左部都包含R的任一候选码,则RBCNF。 例: 如果假定:每一学生可选修多门课程,一门课程可由多个学生选修,每一课程可有多个教师任教,但每个教师只能承担一门课程。判断下列给出的关系SCT(S#, CNAME, TNAME) 最高属于第几范式?并分析该模式存在的问题
16、。武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化关系SCT的候选码:(S#, CNAME)和(S#, TNAME)非主属性:无 (SCT至少是一个3NF关系)因为TNAMECNAME,其左部未包含该关系的任一候选码,所以它不是BCNF。因此,SCT3NF。 若关系R的所有属性都是主属性,则R必定是3NF。 S#CNAME TNAME s1 英语 王平 s1 数学 刘红 s2 物理 高志强 s2 英语 陈进 s3 英语 王平武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化达到3NF的关系仍然可能存在问题。在关系SCT中还存在以下问题:n插入异常。如,一个新课程和
17、任课教师的数据,在没有学生选课时不能插入数据库。n删除异常。如,删除某门课的所有选课记录,会丢失课程与教师的数据。解决:模式分解。SCT可分解为SC(S#,CNMAE)和CT(CNAME,TNAME),都是BCNF。 一个BCNF的关系必定是3NF,但一个3NF不一定属于BCNF。任何的二元关系必定是BCNF。武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化四、多值依赖与第四范式函数依赖有效地表达了属性间的多对一的联系,但不能表示属性间的一对多联系。例: 一门课C可由多个教员T讲授,他们使用相同的一套参考书X;每个教员可讲授多门课,每种参考书可供多门课使用。问:R(C,T,X)
18、 属于第几范式?CTX的候选码是:(C, T, X)BCNFCTX表存在冗余、插、删、改不便武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化 计算数学张平数学分析计算数学张平高等数学计算数学张平计算数学计算数学周峰数学分析计算数学周峰高等数学计算数学周峰计算数学CTX物理李勇普通物理学物理李勇光学原理物理李勇物理习题集物理王军普通物理学物理王军光学原理物理王军物理习题集数学李勇数学分析数学李勇微分方程数学李勇高等代数数学张平数学分析数学张平微分方程数学张平高等代数武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化(1)多值依赖定义: 设R(U)是属性集U上的一个关
19、系模式,X、Y、Z是U的子集,并且Z=U-X-Y,当且仅当对于R(U)的任一关系r,给定的一对(x, z)值,有一组Y的值与之对应,且这组Y值仅仅决定于X值而与Z值无关,则称Y多值依赖于X ,或称X多值决定Y,记为XY 。例: CTX关系中,对于一个(数学, 微分方程)有一组T值李勇,张平,但这组T值仅取决于课程C的值。对于另一个(数学, 高等代数)所对应的T值还是李勇,张平。因此CTX表中:CT,同样的道理可以知道C X。武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化例: 设关系模式R(A,B,C)上有一个多值依赖AB。如果已知R的当前关系中存在三个元组(a,b1,c1)、
20、(a,b2,c2)和(a,b3,c3),那么这个关系中至少还应该存在哪些元组?平凡多值依赖:对于属性集U上的一个多值依赖XY(X,Y是U的子集),如果YX或者XY=U,则称XY是一个平凡多值依赖。 当前关系中还应该存在六个元组:(a, b1, c2)、(a, b1, c3)、(a, b2, c1)、(a, b2, c3)、(a, b3, c1)、(a, b3, c2)。武汉大学数据库原理课题组4.2 关系模式的规范化关系模式的规范化多值依赖与函数依赖的区别:nXY 涉及U中其他属性Z;而 XY 仅由X、Y的属性值所决定。n若XY成立,则对于任何Y Y均有XY成立;而若XY成立,却不能断言对于任
21、何Y Y有XY成立。(2)第四范式:4NF定义: 若R1NF,如果对于R的每个非平凡多值依赖 XY (YX),X都含有码,R4NF。定理: 如果关系模式R4NF,则R必为BCNF。UU武汉大学数据库原理课题组 (3)5种范式的关系:4.2 关系模式的规范化关系模式的规范化1NF非规范化的关系2NF3NF消除组合数据项消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖4NF消除非平凡的多值依赖BCNF消除主属性对码的部分和传递函数依赖1NF2NF3NFBCNF4NF武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统 1.阿氏公理 设F是关系模式R的函数依赖集,X、Y是
22、R的属性子集。 定义:在R 中,从F的函数依赖中能够推出的函数依赖全体叫F的闭包,记为:F+。 F+= F; F中推出的非平凡的函数依赖; F中推出的平凡的函数依赖: A-、A-A、AB- A. 例:有关系模式R(A,B,C),F=AB,BC,计算F的闭包。nArmstrong公理(阿氏公理): 对R 有:nA1自反律:若YX ,则XY。nA2增广律:若XY,则XZYZ。nA3传递律:若XY、YZ,则XZ。武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统n证明:设s,t是r的任意两个元组,r是R的任意一个关系nA1自反律:若YX ,则XY。 若sx=tx,则在s和t中的x的
23、任何子集也必相等。 YX, sy=ty XY。nA2增广律:若XY,则XZYZ。 若sxz=txz,即sxsz=txtz 则 sx=tx 且 sz=tz XY, sy=ty syz=sysz=tytz=tyz XZYZ武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统nA3传递律:若XY、YZ,则XZ。 若sx=tx XY sy=ty 又 YZ sz=tz XZ。n公理的推论则: 合并规则:若XY 、 XZ,则XYZ。 分解规则:若XYZ,则XY,XZ。 伪传递规则:若XY 、WYZ,则WXZ。 证明:n合并规则: XY XXY (A2) 又 XZ XYYZ (A2) XYZ
24、 (A3)武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统n分解规则: YY Z YZY (A1) 又 XYZ(已知) XY (A3) 同理可证XZ。n伪传递规则: XY WXWY (A2) 又 WYZ (已知) WXZ (A3)n定理: XA1A2AK成立的充分必要条件是XAi成立。武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统n定义: XF+=A| XA能由F用阿氏公理导出 XF+称为属性集X关于F的闭包。 例:R(A,B,C) F=AB,BC 则A+=ABC B+=BC C+=Cn定理: XY能从F中用阿氏公理导出的充要条件是:YXF+ 证明:充
25、分性( YXF+ - XY) 设YXF+ ,并设Y=A1A2An 由属性闭包定义可知, XA1, XA2, XAn由阿氏公理导出,再由合并规则得X A1A2An, 即XY。武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统 必要性: ( XY - YXF+ ) 设XY能由阿氏公理导出。Y=A1A2An 由分解规则得: XA1, XA2, XAn 由X+ 的定义可知,AiX+ (i=1,2,n) 即YXF+ 。武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统 2. 属性闭包的计算 算法4.1 : 求属性集X关于F的闭包XF+(X+)。n简化算法: 设 R,A
26、为U中属性(集)。 (1) X(0)=X (2) X(i+1)=X(i)A 其中:对F中任一个Y-A ,且YX(i); 求得X(i+1) 后,对Y-A 做删除标记。 (3)若X(i+1)=X(i) 或 X(i+1) =U则结束,否则转(2)。例:设有关系模式R,其中U=A,B,C,D,E,I, F=AD,ABE,BIE,CDI,EC 计算(AE)+。武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统 3.函数依赖集的等价和覆盖定义: 如果F+=G+ ,就说函数依赖集F覆盖G或F与G等价定理: F+=G+ 的充分必要条件是FG+,和GF+。(1)必要性F和G等价,F+=G+,又
27、FF+,FG+同理,GG+,GF+。(2)充分性任取XYF+,则有YXF+ (定理4.6)又FG+(已知),YXG+XY(G+)+=G+,F+G+。同理可证G+F+,F+=G+,即F和G等价。定理证毕。武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统n如何判断函数依赖集F和G是否等价呢? 只要验证F中的每一个函数依赖XY都在G+中,同时验证 G中的每一个函数依赖VW都在F+中。这不需要计算F+和 G+,只要计算XG+验证YXG+,再计算VF+,验证WVF+即可。 例:F=AB, BC, G=ABC, BC,判断F和G是否等价 解:(1)先检查F中的每一个函数依赖是否属于G+
28、。 AG+=ABC,BAG+,ABG+ 又BG+=BC,CBG+,BCG+ FG+ (2)然后检查G中的每一个函数依赖是否属于F+。 AF+=ABC,BCAF+,ABCF+ 又BF+=BC,CBF+,BCF+ GF+ 由(1)和(2)可得F和G等价。 武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统4.最小函数依赖集n定义:若F满足下列条件,则称其为最小函数依赖集Fm。 (1) F中每个函数依赖的右部都是单属性; (2) 对F中的任一函数依赖XA,F-XA与F都不等价 (3) 对于F中的任一函数依赖XA和X的真子集Z, (F-(XA)UZA与F都不等价。 n(1)保证在函数
29、依赖的右部没有多余的属性;n(2)保证F中不存在多余的函数依赖;n(3)保证F中每个函数依赖的左部没有多余的属性。武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统n定理: 每个F与Fm等价。n如何求最小函数依赖集Fm? (1)分解:使F中任一函数依赖的右部仅含有单属性。 (2)去掉函数依赖左边多余的属性: 方法:对F中任一XYA,在F中求X+, 若AX+ ,则Y为多余的。 (3)去掉多余函数依赖: 方法:对F中任一XA,在F-XA中求X+, 若AX+,则XA为多余的。武汉大学数据库原理课题组4.3 数据依赖的公理系统数据依赖的公理系统 例: 设 函 数 依 赖 集 F=AC
30、, CA, BAC, DAC,BDA 求与F等价的最小函数依赖集。 例:设有函数依赖集F=BC,CAB,ABC,BCA 求与F等价的最小函数依赖集。 注意:一个函数依赖集的最小集不是惟一的。 例如,F=AB,BA,BC,AC,CA Fm1=AB,BC,CA, Fm2=AB,BA,AC,CA。 武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解对于存在数据冗余、插入异常、删除异常的关系模式,可以通过对关系模式的分解来解决问题。关系模式分解后会带来两个问题:(1)查询时的连接操作是否会丢失某些信息或多出某些信息。这引出了无损连接的概念。(2)分解后的关系模式是否保持了原来的函数依赖。这是
31、保持函数依赖性的问题。 一、等价模式分解的定义一个关系有多种分解方法,如何判断分解的好与坏呢?例: 关系模式R(S#,SD,MN),F=S#SD, SDMN分解一:1=R1(S#), R2(SD), R3(MN) 不好!无法恢复R分解二:2=R1(S#, SD), R2(S#, MN) 不好!丢失SDMN分解三:3=R1(S#, SD), R2(SD, MN) 好!武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解二、无损连接性与依赖保持性 对于R中任何一个关系r,R分解=R1, R2, ., RK 无损连接性:r=R1(r) R2(r) RK(r)保持函数依赖:F R1(F)R2(
32、F) RK(F)Ri(F)=XY| XYF+XYRi Ri所含的F+中的函数依赖武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解例: R(A, B, C),F=AB, AC,分解=AB, AC 判断1:r=AB(r) AC(r) 是无损连接分解。 判断2:FAB(F)AC(F) = AB, AC具有函数依赖保持性。 ABCa1b1c1a2b2c2a3b1c2r武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解n算法4.3 无损连接性检验。 输入:关系模式R(A1,A2,An),它的函数依赖集F,以及 分解=R1,R2,Rk。 输出:确定是否具有无损连接性。 方法:(1)构
33、造一个k行n列的表,第i行对应于关系模式Ri, 第j列对应于属性Aj。如果AjRi,则在第i行第j列上放符号ai,否则放符号bij。 (2)重复考察F中的每一个函数依赖,并修改表中的元素。 方法如下:取F中一个XY,在X的分量中寻找相同的行, 然后将这些行中Y的分量改为相同的符号,如果其中有aj, 则将bij改为aj;若其中无aj,则全部改为bij(i是这些行的行号最小值)。武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解 (3)如果发现表中某一行变成了al,a2,an,则分解 具有无损连接性;如果F中所有函数依赖都不能再修改 表中的内容,且没有发现这样的行,则分解不具有无损连接性
34、。 例:设R,其中U=A,B,C,D,E, F=AC,BC,CD,DEC,CEA =R1,R2,R3,R4,R5, 这里R1=AD,R2=AB,R3=BE, R4=CDE,R5=AE。 判断分解是否具有无损连接性。 武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解n定理: 设=(R1,R2)是R的一个分解,F是R上的函数 依赖集,分解具有无损连接性的充分必要条件是: R1R2(R1-R2)F+ 或 R1R2(R2-R1)F+ 证明: (1)充分性:设R1R2(R1-R2),按算法5.2可构造出下表。表中省略了a和b的下标,这无关紧要。 RiR1R2 R1-R2 R2-R1 R1 a
35、aa aaa bbb R2 aaa bbb aaa武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解 如果R1R2(R1-R2)在F中,则可将表中第2行位于(R1-R2)列中的所有符号都改为a,这样该表中第2行就全是a了,则具有无损连接性。同理可证R1R2(R2-R1)的情况。 如果R1R2(R1-R2)不在F中,但在F+中,即它可以用公理从 F中推出来,从而也能推出R1R2Ax, 其中AxR1-R2,所以可以将Ax列的第2行改为全a,同样可以将R1-R2中的其他属性的第2行也改为a,这样第2行就变成全a行。所以分解=R1,R2具有无损连接性。 同样可以证明R1R2(R2-R1)的情
36、况。 (2)必要性:设构造的表中有一行全为a,例如第1行全为a,则由函数依赖定义可知R1R2(R2-R1);如果是第2行全为a,则 R1R2(R1-R2)。定理证毕。武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解 例: 下列分解是否具有无损连接性和函数依赖保持性。 已知:R(A,B,C) F=AB,CB (1)1=AB,AC (2)2=AB,BC武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解三、三、模式分解的方法3NF的保持无损连接及函数依赖的分解: 设:R(1)对Fm中任一XA,若XA=U则不分解,结束;(2)若R中Z属性在Fm中未出现,则所有Z为一个子模式,令U
37、=U-Z;(3)对Fm中 XA1, ., XAn,用合成规则合成一个,再对Fm中每个XA,令Ri=XA;(4) R的分解为R1, R2, ., RK, 码武汉大学数据库原理课题组4.4 关系模式的分解关系模式的分解BCNF的保持无损连接的分解:(1)令=R;(2)如果中所有关系模式都是BCNF,则转(4); (3)如果中有一个关系模式Ri不是BCNF, 则Ri中必有XAFi+(AX),且X不是Ri的码。 设S1=XA,S2=Ui-A,用分解S1,S2代替Ri, 转(2); (4)分解结束,输出。 例:设R=A,B,C,D, F=AC,CA,BAC,DAC,BDA (1)将R分解为3NF且具有无
38、损连接性和依赖保持性。 (2)将R 分解为BCNF且具有无损连接性。武汉大学数据库原理课题组4.5 规范化的问题规范化的问题一、规范化的缺点一、规范化的缺点 n模式分解会降低查询效率;n仅基于一个关系模式的规范化。 二、反规范化的设计二、反规范化的设计n对特定的应用不规范化,而通过使用冗余来改进性能。例: 清单(帐号, 支行名, 密码, 余额),帐户(客户名, 帐号) 每次访问时,客户名都与帐号、密码和余额一起显示。 n并不是规范化程度越高越好;并非越简越好。例: 收益(公司号, 年份, 数量),若设计成:(1)使用多个关系 ,每年建一个表。收益-xx(公司号,数量) BCNF 多年、分组统计
39、不便! (2)使用一个关系:收益(公司号,收入2000,收入2001,收入2002) BCNF 好不好?武汉大学数据库原理课题组4.5 规范化的问题规范化的问题三、模式设计的原则(1)模式R,分解= R1, , Rk,一般应有的特性:是3NF模式集或BCNF模式;无损分解:r=R1(r) R2(r) RK(r) 保持函数依赖:F F1F2 Fk(2)尽可能使模式保持最好的特性:尽量设计成BCNF。若达不到保持函数依赖的特点,则需设计成3NF,以保证两个条件。(3)模式分解和转换的关键是要: “等价”。原则:n表达性:新模式能表达原模式。n分离性:将产生不好性质的属性分离。n少冗余性:选择非最高的范式、“小”的公共属性。少连接属性武汉大学数据库原理课题组第四章第四章 关系数据理论关系数据理论1. 函数依赖关系2. 关系模式的规范化n几种常见范式及其转换3. 阿氏公理及其推理规则4. XF+的定义及求XF+5. 用函数依赖或XF+求码6. 求最小函数依赖集Fm7. 模式分解的概念、方法本章练习:本章练习:本章思考题: 1、关系模式的规范化的意义? 2、XF+与XF+的关系? 3、最小函数依赖集Fm的概念与作用?