第七章数据库设计理论基础Chapter--Relat优秀文档.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,12.,*,单击此处编辑母版标题样式,数据库与智能网络研究室,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,第七章：数据库设计理论基础,银行数据库模式,branch,=(,branch_name,branch_city,assets,),customer,=(,customer_id,customer_name,customer_street,customer_city,),loan,=(,loan_number,amount,),account,=(,account_number,balance,),employee,=(,employee_id,.,employee_name,telephone_number,start_date,),dependent_name,=(,employee_id,dname,),account_branch,=(,account_number,branch_name,),loan_branch,=(,loan_number,branch_name,),borrower,=(,customer_id,loan_number,),depositor,=(,customer_id,account_number,),cust_banker,=(,customer_id,employee_id,type,),works_for,=(,worker_employee_id,manager_employee_id,),payment,=(,loan_number,payment_number,payment_date,payment_amount,),savings_account,=(,account_number,interest_rate,),checking_account,=(,account_number,overdraft_amount,),有损分解,函数依赖,函数依赖（,Functional Dependency,，,FD,）是数据依赖的一种，它反映属性或属性组之间互相依存、互相制约的关系。,函数依赖的定义,定义,设,R(U),是属性集,U,上的一个关系模式，,X,和,Y,均为,U,A1,，,A2,，,，,An,的子集，,r,为,R,的任一个关系。如果对于,r,中的任意两个元组,u,、,v,，只要有,uX,vX,，就有,uY,vY,，则称,X,函数决定,Y,或称,Y,函数依赖于,X,，记为,X Y,。其中,X,称为决定因素（,Determinant,）。,bor_loan=(customer_id,loan_number,amount).,函数依赖成立,:,loan_number,amount,函数依赖的定义,在,R,(,U,),中，如果,X,Y,，并且对于,X,的任何真子集,X,都有,X,Y,，则称,Y,完全函数依赖于,X,，记作 （简记为,X,Y,）；如果,X,Y,，且,X,中存在一个真子集,X,，使得,X,Y,成立，则称,Y,部分函数依赖于,X,，记作 。,函数依赖的逻辑蕴涵,设有关系模式,R,(,U,),及其函数依赖集,F,，如果对于,R,的任一个满足,F,的关系,r,函数依赖,X,Y,都成立，则称,F,逻辑蕴涵,X,Y,，或称,X,Y,可由,F,推出。,所有被,F,逻辑蕴涵的函数依赖的集合，称为,F,的闭包（,closure,），记为,F,+,。在一般情况下,F F,+,，如果,F,F,+,，则称,F,为一个函数依赖的完备集。,函数依赖的逻辑蕴涵,设,R,ABC,，,F,AB,，,BC,，则,F,+,由所有这样的函数依赖,XY,组成：,（,1,）,X,含有,A,。如,ABCAB,，,ABBC,，,AA,，,AC,。,（,2,）,X,含有,B,但不含,A,，且,Y,也不含,A,。如,BCB,，,BC,，,B,。,（,3,）,X,Y,是,CC,和,C,。,函数依赖的逻辑蕴涵,设,R,ABC,，,F,AB,，,BC,，则,F,+,由所有这样的函数依赖,XY,组成：,（,1,）,X,含有,A,。如,ABCAB,，,ABBC,，,AA,，,AC,。,（,2,）,X,含有,B,但不含,A,，且,Y,也不含,A,。如,BCB,，,BC,，,B,。,（,3,）,X,Y,是,CC,和,C,。,Armstrong,公理,设,U,为关系模式,R,的属性全集，,F,为,U,上的一组函数依赖，对,R,(,U,，,F),有以下推理规则。,A,1,：自反律（,Reflexivity,）,如果,Y,X,U,，则,X,Y,为,F,所蕴涵。,A,2,：增广律（,Augmentation,）,如果,X,Y,为,F,所蕴涵，且,Z,U,，则,XZ,YZ,为,F,所蕴涵。,A,3,：传递律（,Transitivity,）,如果,X,Y,和,Y,Z,为,F,所蕴涵，则,X,Z,为,F,所蕴涵,。,Armstrong,公理,定理,Armstrong,公理是正确的，即由,F,出发根据,Armstrong,公理推导出来的每一个函数依赖必定为,F,所逻辑蕴涵。,根据,Armstrong,公理可以得到下面三条推论，它们也是很有用的推理规则。,（,1,）合并规则（,Union Rule,）,如果,X,Y,，,X,Z,，则,X,YZ,。,（,2,）伪传递规则（,Pseudotransivity Rule,）,如果,X,Y,、,WY,Z,，则,XW,Z,。,（,3,）分解规则（,Decomposition Rule,）,如果,X,Y,，且,Z,Y,，则,X,Z,。,Armstrong,公理的完备性,定义,设,F,是属性集,U,上的函数依赖集，,X,是,U,的子集，则由,Armstrong,公理可从,F,推导出的所有,X,A,i,所形成的属性集,A,i,i,1,2,称为,X,对于,F,的闭包，记为,X,+,。,例,设,R,ABC,，,F,AB,，,BC,，则,当,X,A,时，,X,+,ABC,；,当,X,B,时，,X,+,BC,；,当,X,C,时，,X,+,C,。,引理,当且仅当,Y,X,+,时，,X,Y,能根据,Armstrong,公理由,F,导出。,例如:如果 A B and B C,则可以推理得出 A C,不是每个BCNF分解都是保持依赖的，同时它也说明我们不是总能满足,定理 如果R1，R2是关系模式R的一个分解，F为R所满足的函数依赖集，则分解具有无损连接性的充分必要条件为：,（3）XY是CC和C。,解：按最小函数依赖集的定义分别考虑3个条件。,（2）X含有B但不含A，且Y也不含A。,分解的无损连接性（Lossless join）。,解：设XBD,在R(U)中，如果XY，并且对于X的任何真子集X 都有X Y，则称Y完全函数依赖于X，记作 （简记为XY）；,loan_number amount,Does A R?=Is(A)+R,R=(J,K,L)F=JK L L K 两个候选键=JK and JL,此外，如果关系模式集中的每个模式都属于BCNF，则这个数据库设计属于BCNF.,dependent_name=(employee_id,dname),Parts of a functional dependency may be redundant,分解为无损的,如果,（2）伪传递规则（Pseudotransivity Rule）,闭包计算,由函数依赖集,F,计算,F,+,是一件相当费时的事。即使,F,很小，,F,+,却可能很大。,但幸运的是计算,F,+,的目的往往是为了判断函数依赖,X,Y,是否为,F,所蕴涵，而根据引理，只要知道,Y,X,+,，就可以断定,X,Y,为,F,所蕴涵。因此，可以用计算,X,+,代替计算,F,+,，通过判断是否满足,Y,X,+,来判定,X,Y,是否为,F,所蕴涵。,算法,求属性集,X,关于函数依赖集,F,的闭包,X,+,。,输入：关系模式,R,的属性全集,U,，在,U,上的函数依赖集,F,，以及,U,的子集,X,。,输出：属性集,X,关于,F,的闭包,X,+,。,闭包计算,方法：,（,1,）令,X,(0),X,，,i,=0,；,（,2,）计算,B,A,(,V,)(,W,)(,V,W,F,V,X,（,i,）,A,W,；,（,3,）,X,(,i,+1),B,X,(,i,),；,（,4,）如果,X,(,i,+1),X,(,i,),，则令,i,i,+1,，返回（,2,）；,（,5,）输出,X,(,i,),，它就是,X,+,。,闭包计算,例,已知关系模式,R,中,U,A,，,B,，,C,，,D,，,E,，,G,，,F,ABC,，,CA,，,BCD,，,ACDB,，,DEG,，,BEC,，,CGBD,，,CEAG,，求,(BD),+,。,解：设,X,BD,（,1,）令,X,(0),BD,。,（,2,）计算,X,(1),：在,F,中找左边为,X,(0),子集即,B,、,D,或,BD,的函数依赖，结果有,DEG,，所以,X,(1),X,(0),EG,BDEG,。,（,3,）计算,X,(2),：在,F,中找尚未使用过的、左边为,X,(1),子集的函数依赖，得,BEC,，所以,X,(2),X,(1),C,BCDEG,。,（,4,）计算,X,(3),：在,F,中找尚未用过且左边为,X,(2),子集的函数依赖，得,CA,、,BCD,、,CGBD,、,CEAG,，所以,X,(3),X,(2),ABDG,ABCDEG,。,由于,X,(3),已包含全部属性，显然,X,(4),X,(3),，算法终止，得,(BD),+,ABCDEG,。,函数依赖集的等价和最小集,定义,设,F,和,G,是两个函数依赖集，如果,F+,G+,，则称,F,和,G,等价，也称,F,覆盖,G,，或,G,覆盖,F,。,定义,如果函数依赖集,F,满足：,（,1,）,F,中每一个函数依赖的右部仅含单个属性；,（,2,）对于,F,中的任一函数依赖,XA,，集,F,XA,不等价于,F,；,（,3,）对于,F,中的任一函数依赖,XA,和,X,的任何真子集,Z,，集,(F,XA)ZA,不等价于,F,，则称,F,为最小函数依赖集或称最小覆盖。,函数依赖集的等价和最小集,定理,每个函数依赖集,F,都等价于一个最小函数依赖集。,证明：定理的证明其实就是给出求最小函数依赖集的方法，如果方法存在，定理也就得证。为此，按三个条件进行最小化处理，找出,F,的一个最小函数依赖集。,（,1,）为了满足条件（,1,），只要根据分解规则把右侧是属性组的函数依赖分解为单属性的多个函数依赖即可。例如,ABC,可分解为,AB,和,AC,，从而满足条件（,1,）。,（,2,）逐一考察,F,中的函数依赖,XY,，令,G,F,XY,，且对,G,求,X+,，因为,F,与,G,等价的充要条件是,Y,X+,，所以如果,Y,X+,，则,XY,冗余，可以删去。,（,3,）逐一考察,F,中留下的函数依赖，消去左侧冗余的属性。为了判断函数依赖,XYA,中,Y,是否冗余，可在,F,中求,X+,，若,A,X+,，则,Y,是冗余属性。,经过上述三步处理之后剩下的,F,一定是最小函数依赖集，并且与原来的,F,等价。,F,的最小函数依赖集不一定是唯一的。,函数依赖集的等价和最小集,例,求给出的,F,的最小函数依赖集。,解：按最小函数依赖集的定义分别考虑,3,个条件。,（,1,）根据分解规则分解右部为属性组的函数依赖，得：,函数依赖集的等价和最小集,（,2,）消去,F1,中多余的函数依赖。因为由,CA,可导出,CEA,，又由,CGD,、,CA,、,ACDB,可导出,CGB,，所以从,F1,中删去冗余函数依赖,CEA,和,CGB,，得：,函数依赖集的等价和最小集,（,3,）消去,F2,中左边多余的属性。因为由,CA,、,CDB,可导出,ACDB,，所以可去掉,ACDB,中左侧,A,属性，从而求得,F,的最小函数依赖集：,关系模式的分解,定义,关系模式,RU,F,的分解是指,R,为它的一组子集,R1U1,F1,R2U2,F2,，,，,RkUk,Fk,所代替的过程。,分解的无损连接性（,Lossless join,）。分解的函数依赖保持性（,Preserve dependency,）。,分解具有“无损连接性”,分解要“保持函数依赖”,分解既要“保持函数依赖”，又要具有“无损连接性”。,分解的无损连接性,分解的无损连接性,例,已知关系模式,R(ABCDE),及其函数依赖集,F,AC,，,BC,，,CD,，,DEC,，,CEA,。试检验分解,R1(AD),，,R2(AB),，,R3(BE),，,R4(CDE),，,R5(AE),的无损连接性。,分解的无损连接性,定理,如果,R1,，,R2,是关系模式,R,的一个分解，,F,为,R,所满足的函数依赖集，则分解,具有无损连接性的充分必要条件为：,R1R2R1,R2F+,或,R1R2R2,R1F+,。,其中,R1R2,表示模式的交，结果为公共属性；,R1,R2,或,R2,R1,表示模式的差集，,R1,R2,的结果由属于,R1,但不属于,R2,的属性组成。,分解的函数依赖保持性,定义,设,F,是关系模式,R,的函数依赖集，,R1,R2,Rk,为,R,的一个分解，如果,(F),的并集（,i=1,2,k,）逻辑蕴涵,F,中的全部函数依赖，则称分解,具有函数依赖保持性。,一个无损连接的分解不一定具有函数依赖保持性；同样，一个保持函数依赖的分解也不一定具有无损连接性。而且有些实用的分解算法也往往顾此失彼，难以兼顾。,分解的函数依赖保持性,例,设关系模式,R,CITY,，,ST,，,ZIP,表示各城市街道的邮政编码，其中属性分别表示城市、街道名和邮政编码，,F,(CITY,，,ST)ZIP,，,ZIPCITY,。如果将,R,分解为,R1,，,R2,，其中,R1,ST,，,ZIP,，,R2,CITY,ZIP,，由于,R1R2,ZIP,，,R2,R1,CITY,，,ZIPCITYF,第一范式（,1NF,）,定义,如果关系模式,R,的所有的域为简单域，其元素不可再分，则称,R,为第一范式的关系，简记为,R1NF,。,1NF,的关系模式要求属性不能再分，即属性项不能是属性组。下列两个关系模式均不是第一范式：,部门,(,部门号，名称，经理,(,正经理，副经理,),雇员,(,雇员号，姓名，工资,(,基本工资，补贴，奖金,),可以转化为如下,1NF,的关系：,部门,(,部门号，名称，正经理，副经理,),。,雇员,(,雇员号，姓名，基本工资，补贴，奖金,),。,BCNF,设,R,是一个关系模式，如果对于每一个函数依赖对,XY,，其中的决定因素,X,都含有键，则称关系模式,R,满足,Boyce-Codd,范式，简称,BC,范式，记为,RBCNF,。,BC,范式的本质意义在于，其中的每一个决定因素都是一个超键。或者说，在,BCNF,中，除了键决定其所有属性和超键决定其所有属性之外，绝不会有其他的非平凡函数依赖。,由以上定义可以得出关于,BCNF,关系模式的以下结论：,（,1,）非主属性对关键字完全函数依赖；,（,2,）主属性对不包含它的关键字完全函数依赖；,（,3,）没有属性完全函数依赖于一组非主属性。,BCNF,例,在关系模式,STJ(S,，,T,，,J),中，,S,、,T,、,J,分别表示学生、教师和课程。假设每位教师只教授一门课程，每门课程可有若干教师担任；此外对每门课程，一个学生只能听一位教师的讲义。由语义可得如下函数依赖集：,TJ,S,TJ,S,JT,分解算法,人们不得不接受这样的事实。,（,1,）若要求分解具有无损连接性，那么分解一定可以达到,BCNF,。,（,2,）若要求分解保持函数依赖，那么分解可以达到,3NF,，但不一定能达到,BCNF,。,（,3,）若要求分解既保持函数依赖，又具有无损连接性，那么分解也可以达到,3NF,，但不一定能达到,BCNF,。,分解算法,例,无损连接地将,CTHRSG,分解为一组,BCNF,的关系模式。其中,C,表示课程，,T,表示教师，,H,表示时间，,R,表示教室，,S,表示学生，,G,表示成绩。函数依赖集,F,及其所反映的语义分别为：,CT,每门课程仅有一位教师担任,HTR,在任一时间，一个教师只能在一个教室上课,HRC,在任一时间，每个教室只能上一门课,HSR,在任一时间，每个学生只能在一个教室听课,CSG,每个学生学习一门课程只有一个成绩,分解算法,对于给定的函数依赖集,F,，如果对,F+,中所有形如,的函数依赖，其中,R,，,R,。下面至少有一个成立,:,is trivial(i.e.,),is a superkey for,R,则具有函数依赖集,F,的关系模式,R,属于,BCN,下。此外，如果关系模式集中的每个模式都属于,BCNF,，则这个数据库设计属于,BCNF.,Example,不属于,BCNF,的关系模式,:,bor_loan,=(,customer_id,loan_number,amount,),由于,loan_number,amount,成立,bor_loan,而,loan_number,不是超键,实例,R=(A,B,C)F=A,B B,CKey=A,R,不满足,BCNF,分解,R1=(A,B),R2=(B,C),R1 and R2,满足,BCNF,无损连接分解,依赖保持,BCNF,分解算法,result,:=,R,;,done,:=false;compute,F,+,;,while(not,done),doif,(there is a schema,R,i,in,result,that is not in BCNF),then begin,let,be a nontrivial functional dependency that holds on,R,i,such that,R,i,is not in,F,+,and,=,;,result,:=(,result R,i,),(,R,i,),(,);,endelse,done,:=,true;,BCNF,分解实例,R=(A,B,C)F=A,B B,CKey=A,R,不满足,BCNF(B,C but B,不是超键,),分解,R1=(B,C),R2=(A,B),BCNF,分解实例,初始关系模式,R,和函数依赖,F,R=(branch_name,branch_city,assets,customer_name,loan_number,amount),F=branch_name,assets branch_city,loan_number,amount branch_name,Key=loan_number,customer_name,分解,R1=(branch_name,branch_city,assets),R2=(branch_name,customer_name,loan_number,amount),R3=(branch_name,loan_number,amount),R4=(customer_name,loan_number),最终分解结果,R1,R3,R4,将关系模式分解为,BCNF,给定关系模式,R,和非平凡函数依赖,违背,BCNF,.,将,R,分解为,:,(,U,),(R-(,-),例如,=loan_number,=amount,and bor_loan,分解为,(,U,)=(loan_number,amount),(R-(,-)=(customer_id,loan_number),BCNF,和依赖保持,不是每个,BCNF,分解都是保持依赖的，同时它也说明我们不是总能满足,所有以下几个设计目标,:,1)BCNF,2),无损连接。,3),保持函数依赖。,第三范式,如果关系模式,R,中的每一个非主属性既不部分依赖也不传递依赖于键，则称这个关系模式属于第三范式，记为,R3NF,。,设,F,是关系模式,R,的,FD,集，如果对于,F,中每一个非平凡的,FD XY,，都有,X,是,R,的超键，或者,Y,的每个属性都是主属性，那么称,R,是,3NF,的模式。,设关系模式,R,，当,R,上每一个,FD X-A,满足下列条件之一时：,即,XA,是一个平凡的,FD,X,是,R,的超键,A,是主属性,关系模式,R,就是,3NF,模式。,函数依赖的闭包,给定函数依赖集,F,，可以证明其他某些函数依赖也成立，我们称这些函数依赖被,F,逻辑蕴涵,.,例如,:,如果,A,B,and,B,C,则可以推理得出,A,C,令,F,为一个函数依赖集。,F,的闭包是指,F,逻辑蕴涵的所有函数依赖的集合。,.,F,的闭包表示为,F,+,.,根据,Armstrong,定理计算,F,+,:,if,then ,(,自反律,),if ,then,(,增补律,),if ,and,then,(,传递律,),函数依赖的闭包,根据以下规则简化,F,+,的计算,.,If ,holds,a,nd,holds,then,holds,(,合并律,),If,holds,then,holds and,holds,(,分解律,),If,holds,a,nd,holds,then,holds,(,伪传递律,),属性集的闭包,令,a,为一属性集。我们称在函数依赖集,F,下被,a,函数确定的所有属性为,F,+,下,a,的闭包，,计算,在函数依赖集,F,下,a,+,的算法,result,:=,a,;,while,(changes to,result,),dofor each,in,F,dobeginif,result,then,result,:=,result,end,设关系模式R，当R上每一个FD X-A满足下列条件之一时：,account_branch=(account_number,branch_name),（3）没有属性完全函数依赖于一组非主属性。,如果将R分解为R1，R2，其中R1ST，ZIP，R2CITY,ZIP，由于,result:=R;done:=false;compute F+;while(not done)doif(there is a schema Ri in result that is not in BCNF)then beginlet be a nontrivial functional dependency that holds on Ri such that Ri is not in F+,and =;result:=(result Ri)(Ri )(,);endelse done:=true;,loan_number amount,计算在函数依赖集F下a+的算法,r=R1(r)R2(r),1NF的关系模式要求属性不能再分，即属性项不能是属性组。,可以用两种方法分解,例如:如果 A B and B C,则可以推理得出 A C,例 设关系模式RCITY，ST，ZIP表示各城市街道的邮政编码，其中属性分别表示城市、街道名和邮政编码，F(CITY，ST)ZIP，ZIPCITY。,loan=(loan_number,amount),属性集的闭包示例,R=(A,B,C,G,H,I),F=,A,B,A,C,CG,H,CG,I,B,H,(,AG),+,1.,result=AG,2.,result=ABCG(A,C,and,A,B),3.,result=ABCG,H(CG,H,and,CG,AGBC),4.,result=ABCG,HI(CG,I,and,CG,AGBCH),Is,AG,a candidate key?,Is AG a super key?,Does,AG,R?=,Is(AG),+,R,Is any subset of AG a,superkey,?,Does,A,R,?,=,Is(A),+,R,Does,G,R,?=Is(G),+,R,正则覆盖,假设在关系模式上有函数依赖集,F,，那么在该关系上做任何更新时，数据库系统都要保证,F,中所有函数依赖在新数据库状态下仍然满足，否则就回滚该更新操作。,For example:,A,C,是冗余的,in:,A,B,B,C,Parts of a functional dependency may be redundant,E.g.:on RHS:,A,B,B,C,A,CD,can be simplified to ,A,B,B,C,A,D,E.g.:on LHS:A,B,B,C,AC,D,can be simplified to A,B,B,C,A,D,F,的正则覆盖,F,C,是一个依赖集,意指,F,逻辑蕴涵,F,C,中的所有依赖，并且,F,C,逻辑蕴涵,F,中的所有依赖。,正则覆盖计算,R,=(,A,B,C)F=A,BC B,C A,B,AB,C,Combine,A,BC,and,A,B,into,A,BC,Set is now,A,BC,B,C,AB,C,A,is extraneous in,AB,C,Check if the result of deleting A from,AB,C,is implied by the other dependencies,Yes:in fact,B,C,is already present!,Set is now,A,BC,B,C,C,is extraneous in,A,BC,Check if,A,C,is logically implied by,A,B,and the other dependencies,Yes,:,using transitivity on,A,B and B,C.,Can use attribute closure of,A,in more complex cases,The canonical cover is:,A,BB,C,当XC时，X+C。,R=(A,B,C,G,H,I),（2）计算BA(V)(W)(VWFV X（i）AW；,分解的函数依赖保持性（Preserve dependency）。,and bor_loan 分解为,（2）X含有B但不含A，且Y也不含A。,HTR 在任一时间，一个教师只能在一个教室上课,loan_number amount,3NF缺点:即如果没有消除所有的传递依赖，必须用空值表示数据项间的某些可能有意义的联系。,savings_account=(account_number,interest_rate),R1 R2=B and B BC,R2R1CITY，,设RABC，FAB，BC，则F+由所有这样的函数依赖XY组成：,R3=(branch_name,loan_number,amount),bor_loan=(customer_id,loan_number,amount),（2）消去F1中多余的函数依赖。,无损连接分解,对于关系模式,R=(R,1,R,2,),在关系模式,R,上建立的任何关系,r,均满足,r=,R1,(r),R2,(r),将,R,无损分解为,R,1,和,R,2,必须至少满足,F,+,函数依赖中的一个,:,R,1,R,2,R,1,R,1,R,2,R,2,实例,R=(A,B,C)F=A,B,B,C),可以用两种方法分解,R,1,=(A,B),R,2,=(B,C),无损分解,:,R,1,R,2,=,B,and,B,BC,依赖保持,R,1,=(A,B),R,2,=(A,C),无损分解,:,R,1,R,2,=,A,and,A,A,B,依赖不保持,(cannot check,B,C,without computing,R,1,R,2,),依赖保持,令,F,i,为,F,+,中仅包含,R,i,中属性的函数依赖集,分解为无损的,如果,(,F,1,F,2,F,n,),+,=,F,+,依赖保持测试,将,R,分解为,R,1,R,2,R,n,测试函数依赖,是否保持。应用以下算法,result,=,while,(changes to,result,)do,for each,R,i,in the decomposition,t,=(,result,R,i,),+,R,i,result =result,t,如果结果包含,中所有属性,则函数依赖,保持,.,BCNF,和依赖保持,R=,(,J,K,L,),F=,JK,L L,K,两个候选键,=,JK,and,JL,R,不满足,BCNF,R,任何分解不保持,JK,L,这意味着对依赖,JK,L,的测试需要连接,。,在,BCNF,分解过程中，,并不总能实现依赖保持,3NF,实例,关系模式,R:,R=,(,J,K,L,),F=,JK,L,L,K,两个候选键,:,JK,and,JL,R,满足,3NF,JK,LJK,是,超键,L,KK,包含在候选键中,3NF,中的冗余,关系模式中存在冗余,3NF,中冗余导致的问题实例,R=,(,J,K,L)F=,JK,L,L,K,J,j,1,j,2,j,3,null,L,l,1,l,1,l,1,l,2,K,k,1,k,1,k,1,k,2,repetition of information(e.g.,the relationship,l,1,k,1,),need to use null values(e.g.,to represent the relationship,l,2,k,2,where there is no corresponding value for,J,).,3NF,分解算法,Let,F,c,be a canonical cover for,F;i,:=0;,for each,functional dependency,in,F,c,doif,none of the schemas,R,j,1,j,i,contains ,then begin,i,:=,i +,1;,R,i,:=,endif,none of the schemas,R,j,1,j,i,contains a candidate key for,R,then begin,i,:=,i,+1;,R,i,:=any candidate key for,R;,end return,(R,1,R,2,.,R,i,),3NF,分解算法,(Cont.),以上算法保证,:,每个关系模式,R,i,满足,3NF,分解是依赖保持的和无损连接的,3NF,分解实例,关系模式,:,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,是冗余的,其他属性不冗余，得到,F,C,=,customer_id,employee_id,type,employee_id,branch_name,customer_id,branch_name,employee_id,BCNF,和,3NF,的比较,3NF,优点,:,即总可以在满足无损连接并保持依赖的前提下得到,3NF,设计。,3NF,缺点,:,即如果没有消除所有的传递依赖，必须用空值表示数据项间的某些可能有意义的联系。此外，,3NF,还存在信息重复的问题。,关系数据库设计的次要三个目标,:,1)3NF,。,2),无损连接。,3),保持依赖。,设计目标,关系数据库的设计目标,:,BCNF.,无损连接,.,依赖保持,.,如果无法实现,退而求其次,缺失依赖保持,3NF,SQL,除了超键以外，不提供其他指定函数依赖的方法,.,