数据库第十章

数据库系统原理1陈岭浙江大学计算机学院关系模型2BCNF3NF多值依赖4NF数据库设计过程BCNF、3NF和4NFBoyce-Codd范式3具有函数依赖集合F的关系模式R属于BCNF的条件是，当且仅当对F+中所有函数依赖(其中，R且R)，下列至少有一项成立是平凡的函数依赖(即)是R的超码(即，R+，R)Boyce-Codd范式4例，R=(A，B，C)F={ABBC}键={A}R不属于BCNF(∵F+={AB，BC，AC，…}，因为BC，B不是超码)分解成R1=(A，B)，R2=(B，C)R1与R2属于BCNF(A是R1的超码，B是R2的超码)无损连接分解(R1R2=B，并且B是R2的超码）保持依赖(F1={AB}在R1上保持依赖，F2={BC}在R2上保持依赖）检查是否为BCNF5为检查非平凡依赖是否违反BCNF的要求计算+检验+是否包含R的所有属性，即，是否为R的超码简化的测试：为检查具有函数依赖集合F的关系模式R是否属于BCNF，只需检查F中的函数依赖是否违反BCNF即可，而不需检查F+中的所有函数依赖可以证明如果F中没有违反BCNF的依赖，则F+中也没有违反BCNF的依赖∵F+是由Armstrong的3个公理从F推出的，而任何公理都不会使FD左边变小(拆分)，故如果F中没有违反BCNF的FD(即左边是superkey)，则F+中也不会检查是否为BCNF6但是，当检查R的分解后的关系时仅用F是错误的例，考虑R(A，B，C，D)，具有F={AB，BC}分解R到R1(A，B)与R2(A，C，D)F中的函数依赖都不是只包含(A，C，D)中的属性，因此我们可能错误地认为R2满足BCNF事实上，F+中的依赖AC显示R2不属于BCNF可在F下判别R是否违反BCNF，但须在F+下判别R的分解式是否违反BCNFBCNF分解算法7result:={R};done:=false;computeF+;while(notdone)doif(result中存在模式Ri不属于BCNF)thenbegin令是Ri上的一个非平凡函数依赖使得Ri不属于F+，且=;result:=(result–Ri)(Ri–)(,);endelsedone:=true;注意：每个Ri都属于BCNF，且分解是无损连接的将Ri分解为二个子模式：Ri1=(,)和Ri2=(Ri–)，是Ri1和Ri2的共同属性Ri1Ri2BCNF分解示例8class(course_id,title,dept_name,credits,sec_id,semester,year,building,room_number,capacity,time_slot_id)函数依赖：course_id→title,dept_name,creditsbuilding,room_number→capacitycourse_id,sec_id,semester,year→building,room_number,time_slot_id候选码：{course_id,sec_id,semester,year}BCNF分解：course_id→title,dept_name,credits，但是course_id不是超码BCNF分解示例9我们将class分解为：―course(course_id,title,dept_name,credits)―class-1(course_id,sec_id,semester,year,building,room_number,capacity,time_slot_id)course是BCNFbuilding,room_number→capacity在class-1上存在依赖，但是{building,room_number}不是class-1的超码我们将class-1分解为：―classroom(building,room_number,capacity)―section(course_id,sec_id,semester,year,building,room_number,time_slot_id)classroom和section是BCNFBCNF与保持依赖10BCNF分解不总是保持依赖的例，R=(J,K,L)F={JKLLK}两个候选码：JK和JLR不属于BCNF(∵LK，L不是超码)R的任何分解都不满足保持依赖：JKL例，R1=(L,K)，R2=(J,L)BCNF，但不保持依赖J---student，K---course，L---teacher(一门课有多个教师，一个教师上一门课，一个学生选多门课，一门课有多个学生选)BCNF与保持依赖11因此，我们并不总能满足这三个设计目标：无损连接BCNF保持依赖3NF：动机12存在这样的情况BCNF不保持依赖但是，有效检查更新是否违反FD是重要的解决方法：定义一种较弱的范式，称为第三范式（3NF）允许出现一些冗余(从而会带来一些问题)但FD可以在单个关系中检查，不必计算连接总是存在到3NF的无损连接分解，且是保持依赖的3NF13关系模式R属于第三范式(3NF)当且仅当对所有F+中的函数依赖下列条件中至少一个成立：是平凡的函数依赖(即，)是R的超码–中的每个属性A都包含于R的一个候选码中(即A–是主属性，若=，则A=是主属性)注：各属性可能包含在不同候选码中3NF14若一个关系属于BCNF则必属于3NF第三范式相对于BCNF来说放宽了约束，允许非平凡函数依赖的左面不是超码。因为候选码是最小的超码，它的任何一个真子集都不是超码第三个条件是对BCNF条件的最小放宽，以确保每一个模式都有保持依赖的3NF分解讨论：国内其他教材关于3NF的定义：不存在非主属性对码的部分依赖和传递依赖。该定义实际是说，当为非主属性时，必须是码；但当为主属性时，则无限制。二种定义本质上是一致的3NF15例，R=(J,K,L)F={JKL,LK}两个候选码：JK和JLR属于3NFJKL，JK是超码LK，K包含在一候选码中但BCNF分解将得到(J,L)和(L,K)，JKL不保持依赖检查JKL，需要连接操作此模式中存在冗余J---student，K---course，L---teacher(一门有多个教师，一个教师上一门课,一个学生选多门课，一门课有多个学生选)BCNF与3NF的比较16因3NF的冗余引起的问题R=(J,K,L)F={JKL,LK}J---student，K---course，L---teacher(一门有多个教师，一个教师上一门课,一个学生选多门课，一门课有多个学生选)Jj1j2j3nullLl1l1l1l2Kk1k1k1k2属于3NF但不属于BCNF的模式存在以下问题：信息重复(如，联系l1和k1)需要使用空值(如，表示联系l2和k2，这里没有对应的J值)检查是否为3NF17优化：只需检查F中的FD，而不必检查F+中的所有FD对每个依赖，利用属性闭包来检查是否为超码如果不是超码，必须检查中的每个属性是否包含在R的某个候选码中这个检查较昂贵,，因为它涉及求候选码检查是否属于3NF是NP-hard的有趣的是，分解到第三范式可以在多项式时间内完成3NF分解算法18令Fc是F的正则覆盖;i:=0;foreachFc中的函数依赖do{if没有模式Rj(1ji)包含thenbegini:=i+1;Ri:=(,)end}if没有模式Rj(1ji)包含R的候选码thenbegini:=i+1;Ri:=R的任意候选码;endreturn(R1,R2,...,Ri)保证至少在一个Ri中存在R的候选码，从而保证lossless-join将Fc中的每个分解为子模式Ri:=（,），从而保证dependency-preserving3NF示例19关系模式：cust_banker_branch=(customer_id,employee_id,branch_name,type)函数依赖：customer_id,employee_idbranch_name,typeemployee_idbranch_namecustomer_id,branch_nameemployee_id计算正则覆盖：branch_name在第一个函数依赖中是多余的没有其他的多余属性，因此，我们得到FC=―customer_id,employee_idtype―employee_idbranch_name―customer_id,branch_nameemployee_id3NF示例20通过for循环，我们得到以下子关系模式：(customer_id,employee_id,type)(employee_id,branch_name)(customer_id,branch_name,employee_id)由于(customer_id,employee_id,type)包含原关系模式的候选码，分解到此为止在循环结束后，检查并删除模式。如，(employee_id,branch_name)是其他模式的子集，应该删除结果与考虑函数依赖的顺序无关3NF示例21最后，得到3NF分解的子关系模式：(customer_id,employee_id,type)(customer_id,branch_name,employee_id)BCNF与3NF的比较22总是可以将一个关系分解到3NF并且满足分解是无损的保持依赖总是可以将一个关系分解到BCNF并且满足分解是无损的但可能不保持依赖练习23例1，F={ABE,BEI,EG,GIH}，使用Armstrong公理证明ABGH证明：ABE，由增补率得：ABBE；BEI，由增补率得：BEEI；∴ABEI----(1)EG，由增补率得：EIGI；GIH，由增补率得：GIGH∴EIGH----(2)∴(1)，(2)通过传递律得：ABGH练习24例2，对于关系模式：R(A,B,C,D)，F={ABC,CD,DA}1)列出R的所有候选码2)将R分解为到BCNF3)上述分解是否为保持依赖的答：1)(AB)+=(ABCD)R,(BC)+=(ABCD)R,DA,BDAB;ABC;∴(BD)+=(ABCD)R,∴AB,BC,BD是候选码，且R不满足BCNF2)R1(C,D);R2(A,B,C),(R1满足BCNF,R2不满足BCNF,∵CD,DA,∴CA,C不是R2的超码);R21(A,C),R22(B,C),R21满足BCNF,R22满足BCNF3)DA,ABC不是保持依赖的ABCD练习25例3，对于关系模式：R(A,B,C,D,E,F)，F={AB,AC,BCA,DEF,FE}1)列出R的所有候选码2)R属于BCNF还是3NF，或都不属于3)如果R不属于BCNF，将其分解到BCNF4)上述分解是否为保持依赖的答：1)候选码为：AD,BCD2)∵FE，F不是超码，E不在超码中，不属于BCNF，也不属于3NF3)R1=(A,B,C)，R2=(A,D,E,F)，(由ABC)R21=(D,E,F)，R22=(A,D)，∵FE，R21不属于BCNF，R211=(F,E)，R212=(D,F)ABCDEF练习26答：3)方法2：R1=(B,C,A),R2=(B,C,D,E,F);R21=(F,E),R22=(B,C,D,F),R221=(D,F),R222=(B,C,D)4)DE是保持依赖吗？练习27例4，对于关系模式：R(A,B,C,D,E)，