《关系数据理论》PPT课件.ppt

4.1关系模式的设计问题,4.2关系模式的规范化,4.3数据依赖的公理系统(自学),4.4关系模式的分解,第四章关系数据理论,本章小结,4.1函数依赖,一、问题如何构造一个关系模式例：假设有学生关系模式,其中，S#学号、SNAME学生姓名、CLASS班级、C#课程号、TNAME教师姓名、TAGE教师年龄、ADDRESS教师地址、GRADE成绩。,S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE),关系S存在以下问题：1数据冗余度高。SNAME、CLASS、TNAME、TAGE、ADDRESS重复存储多次。,4.1函数依赖,2数据修改复杂。3插入异常。插入异常是指应该插入到数据库中的数据不能执行插入操作的情形。,关系S的主码：,（S#，C#）,从在S#、C#、和(S#,c#)上出现NULL值去分析。注意：当一个元组在主码的属性上部分或全部为空时，该元组不能插入到关系中。,4.1函数依赖,4删除异常。删除异常是指不应该删去的数据被删去的情形。例如：选修某门课的所有学生都退选时，删除相关元组，会丢失该课程老师的信息。解决：关系模式分解（关系规范化）分解为ST(S#，SNAME，CLASS)CT(C#,TNAME)TA(TNAME,TAGE,ADDRESS)SC(S#,C#,GRADE),4.1函数依赖,二、函数依赖functionaldependency,abbr.FD,设：R（A1，A2，An)=R(U)X，Y，Z为U的不同子集,定义4.1：函数依赖是完整性约束的一种，它推广了关键词的概念。Ift1.X=t2.X,thent1.Y=t2.Y函数依赖：若R的任意关系有：对X中的每个属性值，在Y中都有惟一的值与之对应，则称Y函数依赖于X，记作XY。,属性全集,4.1函数依赖,例：指出下列关系R中的函数依赖。,FD:AB-C、AC、CA、ABD？InsertintoRvalues(a1,b1,c2,d1)FD=keyconstraint?,4.1函数依赖,函数依赖与属性间的关系有：若X，Y是11关系，则存在XY或YX。如学号与借书证号若X，Y是m1关系，则存在XY但Y+X。如学号与姓名若X，Y是mn关系，则X，Y间不存在函数依赖关系。如姓名与课程CF:实体间的联系NOTE:函数依赖的方向性,4.1函数依赖,例试指出学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)中存在的函数依赖关系。S#SNAME（每个学号只能有一个学生姓名）S#CLASS（每个学号只能有一个班级）C#TNAME（设每门课程只有一个教师任教，而一个教师可教多门课程，见CT表）TNAMETAGE（每个教师只能有一个年龄）TNAMEADDRESS（每个教师只能有一个地址）(S#，C#)GRADE（每个学生学习一门课只能有一个成绩）(S#，C#)SNAME、(S#，C#)CLASS、(S#，C#)C#、(S#，C#)TNAME、(S#，C#)TAGE、(S#，C#)ADDRESS,4.1函数依赖,三、函数依赖的分类XY，但Y不包含于X则称X是非平凡的函数依赖。XY，但YX则称X是平凡的函数依赖。若XY，则X叫做决定因素。若XY，YX，则记作:XY。定义4.2：在R(U)中，X,Y,Z为U的不同子集。完全函数依赖:是指XY，且对任何X的真子集X，都有X+Y，记作：XFY。部分函数依赖:是指XY，且存在X的真子集X，有X-Y，记作：XPY。,定义4.3：在R(U)中传递函数依赖：是指若XY(Y不包含于X)，Y+X，而YZ。记作：XTZ。,4.1函数依赖,左部为单属性的函数依赖一定是完全函数依赖。左部为多属性的函数依赖，如何判断其是否为完全函数依赖？方法：取真子集，看其能否决定右部属性。例：试指出学生关系S中存在的完全函数依赖和部分函数依赖。S#SNAME，S#CLASS，TNAMETAGE，TNAMEADDRESS，C#TNAME都是完全函数依赖。(S#，C#)GRADE是一个完全函数依赖，因为S#+GRADE，C#+GRADE。,4.1函数依赖,例：试指出学生关系S中存在的传递函数依赖。解：因为C#TNAME，TNAME+C#，TNAMETAGE，所以C#TAGE是一个传递函数依赖。类似地，C#ADDRESS也是一个传递函数依赖。,(S#，C#)SNAME，(S#，C#)CLASS，(S#，C#)TNAME，(S#，C#)TAGE，(S#，C#)ADDRESS都是部分函数依赖，因为S#SNAME，S#CLASS，C#TNAME，C#TAGE，C#ADDRESS。,4.1函数依赖,四、候选码用函数依赖的概念来定义码。定义4.4:设X为R中的属性或属性组合，若XFU则X为R的候选码。说明：XFUX-UX能决定整个元组X+UX中无多余的属性,术语：主码主属性:侯选码中的属性非主属性全码：整个属性组为码例：R(顾客，商品，日期),4.1函数依赖,例：试指出下列关系R中的侯选码、主属性和非主属性。,解：关系R的侯选码为：A，(D,E)关系R的主属性为：A，D，E关系R的非主属性：无,函数依赖判断：A-D?D-A?AD-E?候选码判断:A-ADE?AD-ADE?,4.1函数依赖,例1.R(A,B,C,D)，F=A-B,A-C,AB-D解：由AB-A(自反律)和A-C(已知)得：AB-C(传递律)又因为AB-A(自反律)，AB-B(自反律)和AB-D(已知)得：AB-ABCD。AB是R的唯一候选码，同时也是R的主码。,4.1函数依赖,例2.R(A,B,C,D)，F=A-B,A-C,A-D,AB-D解：由A-A(自反律)和A-B,A-C,A-D(已知)得：A-ABCD可知A是R的候选码AB-ABCD，但由于存在A-ABCD，则AB对ABCD是部分函数依赖，因此AB不能成为候选码。A是R的唯一候选码，A是主码。,4.2关系模式的规范化,一、关系与范式关系的规范化是将一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。关系模式分解的目的：去冗余、满足约束。关系模式的冗余性问题。例R(A,B,C)，无任何约束可导致冗余，若规定FD:A-B，则冗余可利用FD预测到。约束条件通过函数的多值依赖和连接依赖及范式完成。,4.2关系模式的规范化,二、第一范式：1NF定义4.5:若R的每个分量都是不可分的数据项，则R1NF。从型上看：不存在嵌套结构从值上看，不存在重复组1NF是关系模式的最低要求。例：学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)是1NF关系，但它存在数据冗余，插入异常和删除异常等问题。,4.2关系模式的规范化,三、第二范式：2NF定义4.6若R1NF，且R中的每一个非主属性都完全函数依赖于R的任一候选码，则R2NF。例：学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE),判断R是否为2NF?侯选码为(S#，C#)，非主属性有：SNAME，CLASS，TNAME，TAGE，ADDRESS，GRADE(S#，C#)SNAME，S#SNAME(S#，C#)PSNAMES2NF(每一个非主属性!)。,4.2关系模式的规范化,分解为2NF的方法：破坏部分依赖的条件。将满足部分函数依赖和满足完全函数依赖的属性分解到不同的关系中。对上例，考察非主属性和侯选码之间的函数依赖关系：(S#，C#)PSNAME，(S#，C#)PCLASS，(S#，C#)PTNAME，(S#，C#)PTAGE，(S#，C#)PADDRESS，(S#，C#)FGRADE区分出完全依赖和部分依赖，若是部分依赖，标记出其中的主属性。,4.2关系模式的规范化,关系S分解为三个关系：ST(S#，SNAME，CLASS)（只依赖S#的属性分解到一个子模式中）CTA(C#，TNAME，TAGE，ADDRESS)（只依赖C#的属性分解到另一个子模式中）SC(S#，C#，GRADE)（完全函数依赖于候选码的属性分解到第三个子模式中）分解后，关系ST、CTA和SC都为2NF。结论1：若关系R的侯选码是单属性的，则R必定是2NF。,4.2关系模式的规范化,达到2NF的关系仍然可能存在问题。例如，在关系CTA中还存在以下问题：（1）数据冗余。一个教师承担多门课程时，教师的姓名、年龄、地址要重复存储。（2）修改复杂。一个教师更换地址时，必须修改相关的多个元组。（3）插入异常。一个新教师报到，需将其有关数据插入到CTA关系中，但该教师暂时还未承担任何教学任务，则因缺码C#值而不能进行插入操作。（4）删除异常。删除某门课程时，会丢失该课程任课教师的姓名、年龄和地址信息。,4.2关系模式的规范化,四、第三范式：3NF定义4.7如果关系R的任意一个非主属性都不传递函数依赖于它的任意一个候选码，则R3NF。关系CTA(C#，TNAME，TAGE，ADDRESS)是2NF，但不是3NF。候选码：C#，非主属性：TNAME、TAGE、ADDRESS。由于C#TNAME，TNAME+C#，TNAMETAGE，所以C#TTAGE，同样有C#TADDRESS，即存在非主属性对候选码的传递函数依赖。,关系模式R（A，B，C，D），码为AB，给出它的一个函数依赖集，使得R属于2NF而不属于3NF,4.2关系模式的规范化,分解为3NF的方法：破坏传递依赖的条件。将涉及传递函数依赖中的两个依赖中的属性分解到不同的关系中。例：CTA中，两个传递依赖C#TTAGE，C#TADDRESSC#TNAME，TNAME+C#，TNAMETAGE。C#TNAME，TNAME+C#，TNAMEADDRESS。将CTA分解为：CT(C#，TNAME)TA(TNAME，TAGE，ADDRESS)则关系CT和TA都是3NF，关系CTA中存在的问题得到了解决。,4.2关系模式的规范化,定理4.1一个3NF的关系必定是2NF。（3NF传递函数依赖，2NF完全函数依赖。）证明：用反证法。设R3NF，但R2NF，则R中必有非主属性A、侯选码X和X的真子集X存在，使得XA。X是侯选码X的真子集，有X-X；A是非主属性，A-X，A-X，这样A、X、X是U的不同子集。X是侯选码X的真子集，则有XX且X+X，联合反证假设XA可知存在传递依赖（XX，X+X，XA）R不是3NF，与题设矛盾。,4.2关系模式的规范化,通过转为2NF消除了部分依赖，通过转为3NF消除了传递依赖，问题：达到3NF的关系是否仍然存在问题？例：每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称：,4.2关系模式的规范化,解：关系SCT的侯选码：(S#，CNAME)和(S#，TNAME)非主属性：无（SCT至少是一个3NF关系)结论2：若关系R的所有属性都是主属性，则R必定是3NF。,候选码判断:S#-S#CNAMETNAME.取左部的相同值，判断右部。,4.2关系模式的规范化,在3NF关系SCT中存在：插入异常。例如，一个新课程和任课教师的数据，在没有学生选课时不能插入数据库。删除异常。例如，删除某门课的所有选课记录，会丢失课程与教师的数据。达到3NF的关系仍然可能存在问题。,4.2关系模式的规范化（自学）,五、BCNF定义4.8关系模式R1NF。若函数依赖集合F中的所有函数依赖XY（Y不包含于X）的左部都包含R的任一侯选码，则RBCNF。换言之，BCNF中的所有依赖的左部都必须包含候选码。例：关系SCT是否BCNF?因为TNAMECNAME，其左部未包含该关系的任一侯选码，所以它不是BCNF。解决：BCNF分解。,4.2关系模式的规范化,分解为BCNF的方法：消除不包含关系。1.假设R(U)不是BCNF,X是R的属性子集，A是R的单个属性，X-A是导致违反BCNF的函数依赖，则将R分解为R-A以及XA。2.若R-A以及XA仍然不是BCNF，则在R-A以及XA递归地执行上述分解。例SCT：(S#，CNAME，TNAME)，FD:TNAMECNAME。可分解为SC(S#，TNAME)和CT(CNAME，TNAME)，它们都是BCNF。,4.2关系模式的规范化,定理4.2：一个BCNF的关系必定是3NF。（3NF：任意的非主属性都不传递依赖于任意一个候选码。）证明：用反证法。设R是一个BCNF，但不是3NF，则必存在一个非主属性A和候选码X以及属性集Y，使得A传递依赖于X，即XY(Y不包含于X)，Y+X，YA。这就是说Y不包含R的候选码，但YA却成立。根据BCNF定义可知，R不是BCNF，与题设矛盾。结论3：任何的二元关系必定是BCNF。,4.2关系模式的规范化,3NF下仍然存在插入异常和删除异常，原因在于可能存在主属性对候选码的部分函数依赖和传递函数依赖。一个模式中的关系模式如果都属于BCNF，则在函数依赖的范畴内实现了彻底的分离，已消除了插入和删除的异常。其它问题？,4.2关系模式的规范化（自学）,六、第四范式：4NF定义4.10若R1NF，D是R上的依赖集，如果对于任何一个多值依赖XY(Y-X,XY没有包含R的全部属性)，X都包含了R的一个候选关键词，则R4NF。4NF必定是BCNF，但BCNF不一定是4NF。,5种范式的关系：,4.2关系模式的规范化,1NF,非规范化的关系,2NF,3NF,4NF,BCNF,范式的转换关系：,1NF,2NF,3NF,BCNF,4NF,4.2关系模式的规范化,关系的规范化是将一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。范式的转换过程是通过分析和消除属性间的数据依赖关系来实现的。属性可分为码和非主属性。2NF,3NF考察非主属性和码的关系，BCNF考察主属性和码的关系。属性间的依赖关系包括函数依赖和多值依赖。1NF,2NF,3NF,BCNF考察了函数依赖关系；4NF考察了多值依赖。,4.3数据依赖的公理系统（自学）,1.阿氏公理定义4.13设F是关系模式R的函数依赖集，X、Y是R的属性子集，如果从F的函数依赖中能够推出XY，则称F逻辑蕴涵XY。在R中为F所逻辑蕴含的函数依赖全体叫F的闭包，记为：F+。F+=F；F中推出的非平凡的函数依赖；平凡的函数依赖：A-、A-A、AB-A.例：有关系模式R(A，B，C)，它的函依赖集F=AB，BC，计算F的闭包。,4.3数据依赖的公理系统,Armstrong公理(阿氏公理)：对R有：A1自反律：若YX，则XY。A2增广律：若XY，则XZYZ。A3传递律：若XY、YZ，则XZ。Note：XY与YX的次序无关。,4.3数据依赖的公理系统,证：设s，t是r的任意两个元组，r是R的任意一个关系。A1自反律：若YX，则XY。若sx=tx，则在s和t中的x的任何子集也必相等。YX，sy=tyXY。A2增广律：若XY，则XZYZ。若sxz=txz，即sxsz=txtz则sx=tx且sz=tzXY，sy=tysyz=sysz=tytz=tyzXZYZ,4.3数据依赖的公理系统,A3传递律：若XY、YZ，则XZ。若sx=txXYsy=ty又YZsz=tzXZ。,4.3数据依赖的公理系统,公理的推论：合并规则：若XY、XZ，则XYZ。分解规则：若XYZ，则XY,XZ。伪传递规则：若XY、WYZ，则WXZ。证明：合并规则：XYXXY(A2)又XZXYYZ(A2)XYZ(A3),4.3数据依赖的公理系统,分解规则：YYZYZY(A1)又XYZ(已知）XY(A3)同理可证XZ。伪传递规则：XYWXWY(A2)又WYZ(已知)WXZ(A3)定理4.5:XA1A2AK成立的充分必要条件是XAi成立。,由合并律由分解律,4.3数据依赖的公理系统,定义4.14:XF+=A|XA能由F用阿氏公理导出XF+称为属性集X关于F的闭包。定理4.6：XY能从F中用阿氏公理导出的充要条件是：YXF+,4.3数据依赖的公理系统,定理4.6的证明证明：充分性（YXF+-XY）假设YXF+(其中Y=A1A2An)由属性闭包定义可知，XA1，XA2，XAn能由阿氏公理导出，再由合并规则得XA1A2An，即XY。,4.3数据依赖的公理系统,必要性：（XY-YXF+）假设XY能由阿氏公理导出(Y=A1A2An)则有XA1A2An由分解规则得：XA1，XA2，XAn由XF+的定义可知，AiXF+(i=1,2,n)即YXF+。,Armstrong公理系统,Armstrong公理完备性的证明证明：（构造性证明）用反证法假定存在函数依赖XY被F逻辑蕴涵，但XY不能用Armstrong公理从F中导出由引理二，构造R(U)上的关系r如下：下面证明（1）r满足F，（2）r不满足XY,Y，Y，U,4.3数据依赖的公理系统,2.属性闭包的计算算法4.1:求属性集X关于F的闭包XF+(X+)。算法：设R，A为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)。,最多|U-X|步,闭包的计算,示例1R,U=(A,B,C,G,H,I),F=AB,AC,CGH,CGI,BH,计算所用依赖ABAGBACAGBCCGHAGBCHCGIAGBCHI=AGBCHI,闭包的计算,示例2R,U=(A,B,C,D,E),F=ABC,BD,CE,CEB,ACB,计算所用依赖ABCABCBDABCDCEABCDE=ABCDE,闭包的计算,示例3R,U=(A,B,C,D,E,G),F=AE,BEAG,CEA,GD,计算所用依赖AEABEBEAGABEGGDABEGD=ABEGD,4.3数据依赖的公理系统,3.函数依赖集的等价和覆盖定义4.15:如果F+=G+，就说函数依赖集F覆盖G或F与G等价。定理4.9:F+=G+的充分必要条件是FG+，和GF+。（1）必要性F和G等价，F+=G+，又FF+，FG+同理，GG+，GF+。（2）充分性任取XYF+，则有YXF+(定理4.6)又FG+（已知），YXG+XY(G+)+=G+，F+G+。同理可证G+F+，F+=G+，即F和G等价。,4.3数据依赖的公理系统,如何判断函数依赖集F和G是否等价？根据定理4.9:只需FG+和GF+，即证集合的包含关系。对每个TF,有TG+；对每个SG，有SF+，T和S是形如X-Y的属性依赖。证X-YG+,根据定理4.6：只需YXG+转为计算XG+,4.3数据依赖的公理系统,例：F=AB，BC，G=ABC，BC，判断F和G是否等价。解：（1）先检查F中的每一个函数依赖是否属于G+。AG+=ABC，BAG+，ABG+(定理4.6)又BG+=BC，CBG+，BCG+FG+（2）然后检查G中的每一个函数依赖是否属于F+。AF+=ABC，BCAF+，ABCF+又BF+=BC，CBF+，BCF+GF+由（1）和（2）可得F和G等价。,4.3数据依赖的公理系统,4.最小函数依赖集定义4.16:若F满足下列条件，则称其为一个最小函数依赖集Fm。(1)F中每个函数依赖的右部都是单属性；(2)对于F的任一函数依赖XA，F-XA与F都不等价；(3)对于F中的任一函数依赖XA和X的真子集Z，(F-(XA)UZA与F都不等价。,最小：（1）F中每个函数依赖的右部没有多余的属性；（2）F中不存在多余的函数依赖；（3）F中每个函数依赖的左部没有多余的属性。,4.3数据依赖的公理系统,定理4.10:每个F与Fm等价。如何求最小函数依赖集Fm？(1)分解：使F中任一函数依赖的右部仅含有单属性。(2)删除冗余的函数依赖：方法：对F中任一XA，在F-XA中求X+，若AX+，则XA为多余的。(3)最小化左边的多余属性：方法：对F中任一XYA，在F中求X+，若AX+，则Y为多余的。(4)检查：用公理或(2),4.3数据依赖的公理系统,例：设有F=BC，CAB，BCA，求与F等价的最小函数依赖集。分解CAB，F=BC，CA，CB，BCA判断BC是否冗余，F=CA，CB，BCAB+=B,BC非冗余。F=BC，CA，CB，BCA判断CA是否冗余，F=BC,CB，BCAC+=ABC,CA冗余。F=BC，CB，BCA判断CB是否冗余，F=BC,BCAC+=C,CB非冗余。F=BC，CB，BCA判断BCA是否冗余，F=BC，CBBC+=BC,BCA非冗余。F=BC，CB，BCA判断BCA。B+=ABC,AB+，则C在BCA中是多余的。Fmin=BC，CB，BA,注意：对当前F求闭包,4.3数据依赖的公理系统,例：设有函数依赖集F=AB,ABCDE,EFG,EFH,ACDFEG求与F等价的最小函数依赖集。注意：一个函数依赖集的最小集不是惟一的。例如，F=AB，BA，BC，AC，CAFm1=AB，BC，CA，Fm2=AB，BA，AC，CA。方法1：无多余属性；依次判断B-A,A-C是否冗余；方法2：无多余属性；依次判断B-C是否冗余。,Fmin=AB,ACDE,EFG,EFH,4.4关系模式的分解,对于存在数据冗余、插入异常、删除异常的关系模式，可以通过对关系模式的分解来解决问题。关系模式分解后会带来两个问题：（1）查询时的连接操作是否会丢失某些信息或多出某些信息。这引出了无损连接的概念。（2）分解后的关系模式是否保持了原来的函数依赖。这是保持函数依赖性的问题。,4.4关系模式的分解,1.等价模式分解的定义一个关系可以有多种分解方法，如何判断分解的好与坏呢？例：关系模式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)好！,R(A,B,C),AB(R),BC(R),AB(R),BC(R),R(A,B,C),AB(R),BC(R),AB(R),BC(R),有损分解,无损分解,4.4关系模式的分解,2.无损连接性与依赖保持性对于R中任何一个关系r，R分解=R1,R2.RK无损连接性：r=R1(r)R2(r)RK(r)保持函数依赖：FR1(F)R2(F)RK(F)Ri(F)=X-Y|X-YF+XYRi,Ri所蕴含的F+中的函数依赖,4.4关系模式的分解,例：R(A，B，C)，F=A-B，A-C，分解=AB，AC判断1：r=AB(r)|X|AC(r)是无损连接分解。判断2:FAB(F)AC(F)=A-B，A-C具有函数依赖保持性。,r,?=AB，BC,4.4关系模式的分解（自学）,算法4.3无损连接性检验。输入：关系模式R(A1，A2，An)，它的函数依赖集F，以及分解=R1，R2，Rk。输出：确定是否具有无损连接性。方法：(1)构造一个k行n列的表，第i行对应于关系模式Ri，第j列对应于属性Aj。如果AjRi，则在第i行第j列上放符号aj，否则放符号bij。（属于用a代表，且位置信息用j表示；不属于用b代表,且位置信息用ij表示。）(2)重复考察F中的每一个函数依赖，并修改表中的元素。其方法如下：取F中一个函数依赖XY，在X的分量中寻找相同的行，然后将这些行中Y的分量改为相同的符号，如果其中有aj，则将bij改为aj；若其中无aj，则全部改为bij（i是这些行的行号最小值）。,4.4关系模式的分解,(3)如果发现表中某一行变成了al，a2，an，则分解具有无损连接性；如果F中所有函数依赖都不能再修改表中的内容，且没有发现这样的行，则分解不具有无损连接性。,无损连接分解,示例一：U=A,B,C,D,E,F=ABC,CD,DE=(A,B,C),(C,D),(D,E),ABC,CD,DE,4.4关系模式的分解,示例二：U=A,B,C,D,E,F=AC,BC,CD,DEC,CEA=(A,D),(A,B),(B,E),(C,D,E),(A,E),AC,4.4关系模式的分解,BC,CD,4.4关系模式的分解,DEC,CEA,4.4关系模式的分解,定理4.12设=(R1，R2)是R的一个分解，F是R上的函数依赖集，分解具有无损连接性的充分必要条件是：R1R2(R1-R2)F+或R1R2(R2-R1)F+证明：（1）充分性：设R1R2(R1-R2)，按算法5.2可构造出下表。表中省略了a和b的下标，这无关紧要。,只能用于判断分解为2个子模式的情况。,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)的情况。（2）必要性：设构造的表中有一行全为a，例如第1行全为a，则由函数依赖定义可知R1R2(R2-R1)；如果是第2行全为a，则R1R2(R1-R2)。定理证毕。,4.4关系模式的分解,例:下列分解是否具有无损连接性和函数依赖保持性。已知：R(A,B,C)F=AB，CB(1）1=AB，BC（2）2=AC，BC,4.4关系模式的分解,（1）对1和F构造表：,（2）检查F=AB，CB对AB，A列中无相同的行；对CB,C列中无相同的行。1不具有无损连接性。,1=AB，BCF=AB，CB,4.4关系模式的分解,1=AB，BCF=AB，CB利用定理4.12解。R1R2=B(R1-R2)=AR1R2+(R1-R2)1不是无损连接分解。,4.4关系模式的分解,2=AC，BCF=AB，CB,对2和F构造表：,检查F=AB，CB对CB,C列有相同的行，改写B列的相异符号为a，下标为列号2。第一行变为a1a2a3,2具有无损连接性。,4.4关系模式的分解,2=AC，BCF=AB，CB利用定理4.12解。R1R2=C(R1-R2)=A；(R2-R1)=B；R1R2+(R2-R1)2是无损连接分解。,4.4关系模式的分解,3.模式分解的方法3NF的保持无损连接及函数依赖的分解：设：R1)对Fm中任一X-A，若XA=U则不分解，结束。2)若R中Z属性在Fm中未出现，则所有Z为一个子模式，令U=U-Z。3)对Fm中X-A1，.X-An，用合成规则合成一个，再对Fm中每个X-A，令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且具有无损连接性和依赖保持性。（2）将R分解为BCNF且具有无损连接性。,关系模式的分解算法,示例：U=S#，SD，MN，C#，GF=S#SD，S#MN，SDMN，(S#,C#)GU1=S#，SD,F1=S#SDU2=S#,MN,C#,G,F2=S#MN,(S#,C#)GU1=S#,SD,F1=S#SDU2=S#,MN,F2=S#MNU3=S#,C#,G,F3=(S#,C#)G,4.4关系模式的分解,关系模式CTHRSG，其中C表示课程，T表示教师，H表示时间，R表示教室，S表示学生，G表示成绩。函数依赖集F及其所反映的语义分别为：CT每门课程仅有一位教师担任。HTR在任一时间，一个教师只能在一个教室上课。HRC在任一时间，每个教室只能上一门课。HSR在任一时间，每个学生只能在一个教室听课。CSG每个学生学习一门课程只有一个成绩。,4.4关系模式的分解,解：HSCTHRSG，HS是关系模式的关键字。,面向3NF且保持函数依赖的分解。最小函数依赖集为F=CT,CSG,HRC,HSR,THR分解为：CT，CSG，HRC，HSR，THR,面向3NF既有无损连接性又保持函数依赖的分解。HS是关键字，HS，HS是HSR的一个子集分解仍为：CT，CSG，HRC，HSR，THR,4.4关系模式的分解,面向BCNF且具有无损连接性的分解。,CTHRSGKey=HS,CSGKey=CSCSG,CTHRSKey=HSCT，THRHRC，HSR,CTKey=CCT,CHRSKey=HSCHR，HRCHSR,CHRKey=CH，HRCHR，HRC,CHSKey=HSHSC,4.5.多值依赖与第四范式4NF）,例:学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。关系模式Teaching(C,T,B)课程C、教师T和参考书B,例:学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。关系模式Teaching(C,T,B)课程C、教师T和参考书B,4.5.多值依赖与第四范式4NF）,4.5.多值依赖与第四范式4NF）,TeachingBCNF:Teach具有唯一候选码(C，T，B)，即全码Teaching模式中存在的问题(1)数据冗余度大：有多少名任课教师，参考书就要存储多少次(2)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组例如物理课增加一名教师刘关，需要插入两个元组：（物理，刘关，普通物理学）（物理，刘关，光学原理）,4.5.多值依赖与第四范式4NF）,(3)删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组(4)修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组产生原因存在多值依赖,4.5.多值依赖与第四范式4NF,第四范式：4NF定义4.10若R1NF，D是R上的依赖集，如果对于任何一个多值依赖XY(Y-X,XY没有包含R的全部属性)，X都包含了R的一个候选关键词，则R4NF。4NF必定是BCNF，但BCNF不一定是4NF。,4.5.多值依赖与第四范式4NF,在R（U）的任一关系r中，如果存在元组t，s使得tX=sX，那么就必然存在元组w，vr，（w，v可以与s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为XY。这里，X，Y是U的子集，Z=U-X-Y。txy1z2sxy2z1wxy1z1vxy2z2,4.5.多值依赖与第四范式4NF,平凡多值依赖和非平凡的多值依赖若XY，而Z，则称XY为平凡的多值依赖否则称XY为非平凡的多值依赖,4.5.多值依赖与第四范式4NF多值依赖的性质,（1）多值依赖具有对称性若XY，则XZ，其中ZUXY多值依赖的对称性可以用完全二分图直观地表示出来。（2）多值依赖具有传递性若XY，YZ，则XZ-Y,（3）函数依赖是多值依赖的特殊情况。若XY，则XY。（4）若XY，XZ，则XYZ。（5）若XY，XZ，则XYZ。（6）若XY，XZ，则XY-Z，XZ-Y。,4.5.多值依赖与第四范式4NF多值依赖与函数依赖的区别,(1)有效性多值依赖的有效性与属性集的范围有关若XY在U上成立，则在W（XYWU）上一定成立；反之则不然，即XY在W（WU）上成立，在U上并不一定成立多值依赖的定义中不仅涉及属性组X和Y，而且涉及U中其余属性Z。一般地，在R（U）上若有XY在W（WU）上成立，则称XY为R（U）的嵌入型多值依赖,只要在R（U）的任何一个关系r中，元组在X和Y上的值满足定义5.l（函数依赖），则函数依赖XY在任何属性集W（XYWU）上成立。(2)若函数依赖XY在R（U）上成立，则对于任何YY均有XY成立多值依赖XY若在R(U)上成立，不能断言对于任何YY有XY成立,4.5.多值依赖与第四范式4NF,例：Teach(C,T,B)4NF存在非平凡的多值依赖CT，且C不是候选码用投影分解法把Teach分解为如下两个关系模式：CT(C,T)4NFCB(C,B)4NFCT，CB是平凡多值依赖,4.5.多值依赖与第四范式4NF,定理4.3如果关系模式R4NF，则R必为BCNF。证明：用反证法。设R4NF，但RBCNF，则R中必有某个函数依赖XY(Y不包含于X)，且X不包含R的侯选码。由多值依赖公理可知，若XY，则XY，而此时X不包含R的侯选码，R不是4NF，与假设矛盾，从而定理得证。,4.5.多值依赖与第四范式4NF,分解为4NF的方法：（类似于BCNF，消除不包含关系。）1.假设R(U)不是4NF,X-A是导致违反4NF的多值依赖，则将R分解为R-A以及XA。2.若R-A以及XA仍然不是4NF，则在R-A以及XA递归地执行上述分解。,4.5.多值依赖与第四范式4NF）,面向4NF且具有无损连接性的分解。,关系模式R中存在多值依赖CHR，THR，显然由于C或T都不含该关系模式的码HS，R4NF。选择CHR将它分解为CHR和CTSG;再将CTSG分解为CT和CSG。关系模式CTHRSG最后无损地分解为CHR、CT和CSG，其中每一个关系模式都属于4NF。,4.6规范化的问题,1.规范化的优缺点关系模式的分解会降低查询的效率。所讨论的关系规范化是基于泛关系假设的，即只基于一个关系模式的规范化。但现实并不一定满足。2.反规范化的设计对一些特定的应用不规范化，而是通过使用冗余来改进性能。例：account(帐号，支行名，余额)depositor(客户名，帐号)每次访问帐户时，帐户持有者的名字都与帐户密码和余额一起显示。,4.6规范化的问题,并不是规范化程度越高越好。例：earnings(公司号，年份，数量)若设计成：（1）使用多个关系，每年建一个表。不好！（是BCNF）（2）使用一个关系：company_year(公司号，收入_2000，收入_2001，收入_2002)不好！（是BCNF）,第四章关系数据理论小结,1.函数依赖关系2.关系模式的规范化5种范式及转换3.阿氏公理及其推理规则4.XF+的定义及求XF+5.用函数依赖或XF+求码6.求最小函数依赖集Fm7.模式分解的概念、方法,