关系模式分解

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，记作XY。属性全集4.1函数依赖例：指出下列关系R中的函数依赖。ABCDa1b1c1d1a1b1c1d2a1b2c2d1a2b1c3d1FD:AB-C、A→C、C→A、AB→D？InsertintoRvalues(a1,b1,c2,d1)FD=keyconstraint?4.1函数依赖函数依赖与属性间的关系有：若X，Y是1—1关系，则存在XY或YX。如学号与借书证号若X，Y是m—1关系，则存在XY但Y+X。如学号与姓名若X，Y是m—n关系，则X，Y间不存在函数依赖关系。如姓名与课程CF:实体间的联系NOTE:函数依赖的方向性4.1函数依赖例试指出学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)中存在的函数依赖关系。S#→SNAME（每个学号只能有一个学生姓名）S#→CLASS（每个学号只能有一个班级）C#→TNAME（设每门课程只有一个教师任教，而一个教师可教多门课程，见CT表）TNAME→TAGE（每个教师只能有一个年龄）TNAME→ADDRESS（每个教师只能有一个地址）(S#，C#)→GRADE（每个学生学习一门课只能有一个成绩）(S#，C#)→SNAME、(S#，C#)→CLASS、(S#，C#)→C#、(S#，C#)→TNAME、(S#，C#)→TAGE、(S#，C#)→ADDRESS4.1函数依赖三、函数依赖的分类XY，但Y不包含于X则称X是非平凡的函数依赖。XY，但Y⊆X则称X是平凡的函数依赖。若XY，则X叫做决定因素。若XY，YX，则记作:X——Y。定义4.2：在R(U)中，X,Y,Z为U的不同子集。完全函数依赖:是指XY，且对任何X的真子集X’，都有X’+Y，记作：XFY。部分函数依赖:是指XY，且存在X的真子集X’，有X’-Y，记作：XPY。定义4.3：在R(U)中传递函数依赖：是指若XY(Y不包含于X)，Y+X，而YZ。记作：XTZ。4.1函数依赖左部为单属性的函数依赖一定是完全函数依赖。左部为多属性的函数依赖，如何判断其是否为完全函数依赖？方法：取真子集，看其能否决定右部属性。例：试指出学生关系S中存在的完全函数依赖和部分函数依赖。S#→SNAME，S#→CLASS，TNAME→TAGE，TNAME→ADDRESS，C#→TNAME都是完全函数依赖。(S#，C#)→GRADE是一个完全函数依赖，因为S#+GRADE，C#+GRADE。4.1函数依赖例：试指出学生关系S中存在的传递函数依赖。解：因为C#→TNAME，TNAME+C#，TNAME→TAGE，所以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为RU，F中的属性或属性组合，若XFU则X为R的候选码。说明：XFUX-UX能决定整个元组X’+UX中无多余的属性术语：主码主属性:侯选码中的属性非主属性全码：整个属性组为码例：R(顾客，商品，日期)4.1函数依赖例：试指出下列关系R中的侯选码、主属性和非主属性。ADEa1d1e2a2d6e2a3d4e3a4d4e4解：关系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的每个分量都是不可分的数据项，则R∈1NF。从型上看：不存在嵌套结构从值上看，不存在重复组1NF是关系模式的最低要求。例：学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)是1NF关系，但它存在数据冗余，插入异常和删除异常等问题。4.2关系模式的规范化三、第二范式：2NF定义4.6若R∈1NF，且R中的每一个非主属性都完全函数依赖于R的任一候选码，则R∈2NF。例：学生关系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#)PSNAMES2NF(每一个非主属性!)。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的任意一个非主属性都不传递函数依赖于它的任意一个候选码，则R∈3NF。关系CTA(C#，TNAME，TAGE，ADDRESS)是2NF，但不是3NF。候选码：C#，非主属性：TNAME、TAGE、ADDRESS。由于C#→TNAME，TNAME+C#，TNAME→TAGE，所以C#TTAGE，同样有C#TADDRESS，即存在非主属性对候选码的传递函数依赖。关系模式R（A，B，C，D），码为AB，给出它的一个函数依赖集，使得R属于2NF而不属于3NF4.2关系模式的规范化分解为3NF的方法：破坏传递依赖的条件。将涉及传递函数依赖中的两个依赖中的属性分解到不同的关系中。例：CTA中，两个传递依赖C#TTAGE，C#TADDRESSC#→TNAME，TNAME+C#，TNAME→TAGE。C#→TNAME，TNAME+C#，TNAME→ADDRESS。将CTA分解为：CT(C#，TNAME)TA(TNAME，TAGE，ADDRESS)则关系CT和TA都是3NF，关系CTA中存在的问题得到了解决。4.2关系模式的规范化定理4.1一个3NF的关系必定是2NF。（3NF传递函数依赖，2NF完全函数依赖。）证明：用反证法。设R∈3NF，但R2NF，则R中必有非主属性A、侯选码X和X的真子集X‘存在，使得X’→A。X’是侯选码X的真子集，有X-X‘≠ф；A是非主属性，A-X≠ф，A-X‘≠ф，这样A、X、X‘是U的不同子集。X’是侯选码X的真子集，则有X→X’且X’+X，联合反证假设X’→A可知存在传递依赖（X→X’，X’+X，X’→A）R不是3NF，与题设矛盾。4.2关系模式的规范化通过转为2NF消除了部分依赖，通过转为3NF消除了传递依赖，问题：达到3NF的关系是否仍然存在问题？例：每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称：4.2关系模式的规范化解：关系SCT的侯选码：(S#，CNAME)和(S#，TNAME)非主属性：无（SCT至少是一个3NF关系)结论2：若关系R的所有属性都是主属性，则R必定是3NF。S#CNAMETNAMEs1英语王平s1数学刘红s2物理高志强s2英语陈进s3英语王平候选码判断:S#-S#CNAMETNAME..取左部的相同值，判断右部。4.2关系模式的规范化在3NF关系SCT中存在：插入异常。例如，一个新课程和任课教师的数据，在没有学生选课时不能插入数据库。删除异常。例如，删除某门课的所有选课记录，会丢失课程与教师的数据。达到3NF的关系仍然可能存在问题。4.2关系模式的规范化五、