《关系数据库设计与范式理论.ppt》由会员分享，可在线阅读，更多相关《关系数据库设计与范式理论.ppt（59页珍藏版）》请在三一办公上搜索。
1、关系数据库设计,主要内容,什么样的关系数据库设计是好的？函数依赖范式判断模式分解及相关算法,问题的提出,问题针对一个具体问题，如何构造合适的（更好的）数据模式？思路讨论一个关系中属性间的依赖情况讨论如何根据属性间依赖关系来判定关系是否有某些不合适的性质掌握基于函数依赖概念的关系数据库设计的规范方法,银行数据库模式,branch=(branch_name,branch_city,assets)customer=(customer_id,customer_name,customer_street,customer_city)loan=(loan_number,amount)loan_branch=
2、(loan_number,branch_name)account=(account_number,balance)account_branch=(account_number,branch_name)employee=(employee_id.employee_name,telephone_number,start_date)dependent_name=(employee_id,dname)borrower=(customer_id,loan_number)depositor=(customer_id,account_number)cust_banker=(customer_id,emplo
3、yee_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),更大的模式实例分析1,方案1：borrower=(customer_id,loan_number)loan=(loan_number,amount)方案2
4、：bor_loan=(customer_id,loan_number,amount)显然，方案2对应的表不必连接运算，但可能出现信息冗余,更大的模式实例分析2,方案1：loan_branch=(loan_number,branch_name)loan=(loan_number,amount)方案2：loan_amt_br=(loan_number,amount,branch_name)显然，方案2对应的表不必连接运算，且没有信息冗余,更大的模式分析,试图将太多的属性放在一个表里，可能会导致异常：数据冗余：同样的信息在多条元组中重复出现插入异常：插入元组时可能由于部分属性的值未知而导致插入失败删
5、除异常：部分元组的删除可能其他信息的丢失更新异常：存在数据冗余时，更新某元组而不是所有可能的元组，可能导致数据不一致,如：Movie-Star数据库模式,更小的模式实例分析1,假设已知模式 bor_loan=(customer_id,loan_number,amount)，如何将模式分解成：borrower=(customer_id,loan_number)loan=(loan_number,amount),更小的模式实例分析2,并不是所有的分解都是有益的如将 employee 表分解该分解是有损的，即无法通过自然连接重建原模式,更小的模式实例分析3,模式S-C-M（S学号，C班级，M班主任）
6、,该模式设计不好，存在数据冗余、插入异常、删除异常和更新异常,以下哪一个分解是好的呢？,第一范式,First Normal Form（1NF）定义：关系R中每个属性域都是原子的，则R 1NF 非1NF的例子employee表中的children属性域是若干名字的集合employeeID由6位字符串组成，其中前两个字母表示所属部门，后面四位数字表示部门内编号（数据库应用程序中，字符串通常被认为是原子的，应尽量避免利用应用程序对数据进行解析）模式中使用非原子属性会导致设计中存储冗余数据如：为每一个客户存储一个 accounts集合，为每一个account存储一个owners集合我们假设所有关系满足
7、1NF,范式理论,目的：通过属性间的依赖关系，分析关系模式设计是否“好”规范化：将一个低一级范式的关系模式分解为若干个高一级范式的关系模式的过程基本思想：通过模式分解，逐步消除关系模式的数据依赖（函数依赖范畴）中不合适的部分（部分函数依赖和传递函数依赖），但又不丢失原模式中的信息（无损连接）模式分解可以消除冗余，解决更新异常等问题，但也要付出做连接运算等昂贵的代价,函数依赖,定义设R(U)是属性集U上的关系模式。X,Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作术语和记号，但，则称 是平
8、凡函数依赖，但，则称 是非平凡函数依赖若，则X叫做决定因素,如：customer_name,loan_number customer_name customer_name customer_name均为平凡函数依赖,函数依赖,在R(U)中，如果，并且对于X的任何一个真子集X,都有，则称Y对X完全函数依赖，记作若，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作在R(U)中，如果，()，则称Z对X传递函数依赖，记作K是关系模式R的超码当且仅当K RK是关系模式R的候选码当且仅当K R,且for no K,R,F,P,传递,第二范式,Second Normal Form(2NF)定义：若R 1
9、NF,且每个非主属性完全依赖于码，则R 2NF说明：不存在非主属性部分依赖于码的关系为2NF,例:学生-课程-成绩管理关系模式属性组U=学号SNO,系名SDEPT,系主任MN,课程号CNO,成绩G数据依赖,该模式存在非主属性部分函数依赖，达不到2NF，属于1NF。,分解方法,一个1NF，但非2NF的关系总是可以被分解成为一组2NF的关系方法：已知关系R(A,B,C,D),(A,B)为主码，即(A,B)-C,(A,B)-D，且A-D,则将R分解成为:R1(A,D),A为主码R2(A,B,C),(A,B)为主码，A为外码,第三范式,Third Normal Form(3NF)定义：若R2NF,且它
10、的任何一个非主属性都不传递依赖于任何候选码，则R 3NF说明：即不存在非主属性部分依赖和传递依赖于码的关系为3NF,S-M中存在传递传递依赖，故该模式不是3NF,上例分解为：SC(SNO,CNO,G);S-M(SNO,SDEPT,MN);,分解方法,一个2NF，但非3NF的关系总是可以被分解成为一组3NF的关系方法：已知关系R(A,B,C),A为主码(A-B,A-C)，且B-C，则可将R分解为:R1(B,C),B为主码 R2(A,B),A为主码，B为外码,函数依赖集的闭包,给定函数依赖集F，有一些函数依赖是在F中被逻辑蕴涵的如：如果 A B 且 B C，推理可得A C函数依赖集F 中逻辑蕴含的
11、所有函数依赖，成为F的闭包，表示为F+F+是F的超集,BCNF,已知函数依赖集合F对应的F+，对任意 R 和 R，若任意函数依赖 都满足：是平凡的(即)，且是R的超码，则关系R满足BCNF。,例1：bor_loan=(customer_id,loan_number,amount)，有 loan_number amount 但 loan_number 不是超码，因此bor_loan不是BCNF,定义：若每一个决定因素都包含(或是)码，则R BCNF,Boyce-Codd Normal Form(BCNF),关系的关键字为（course,teacher,book）由于不存在非平凡的函数依赖，因此模
12、式满足BCNF,course,teacher,book,databasedatabasedatabasedatabasedatabasedatabaseoperating systemsoperating systemsoperating systemsoperating systems,AviAviHankHankSudarshanSudarshanAviAvi PetePete,DB ConceptsUllmanDB ConceptsUllmanDB ConceptsUllmanOS ConceptsStallingsOS ConceptsStallings,classes,例2:,BCN
13、F 模式分解方法,给定关系模式R，假设其中的一个非平凡函数依赖 不符合BCNF约束，则将R分解为：(U)(R-(-)例如：已知 bor_loan=(customer_id,loan_number,amount)，且 loan_number amount，即bor_loan不满足BCNF 设：=loan_number=amount则 bor_loan 可分解为：(U)=(loan_number,amount)(R-(-)=(customer_id,loan_number),BCNF 模式分解算法,result:=R;done:=false;计算 F+;while(not done)doif(re
14、sult 中存在不属于BCNF的模式 Ri)then begin令 是Ri 上的一个非平凡函数依赖，满足 Ri 不 存在 F+中,且=;result:=(result Ri)(Ri)(,);endelse done:=true;注:用这个算法产生的分解不仅是一个 BCNF 分解，而且是无损分解,例3,已知关系模式 R 和函数依赖集 F R=(branch_name,branch_city,assets,customer_name,loan_number,amount)F=branch_name assets,branch_city loan_number amount,branch_name
15、Key=loan_number,customer_name可知，R不是BCNF，因为存在函数依赖，其决定因素不包含(是)码模式分解为：R1=(branch_name,branch_city,assets)R2=(branch_name,customer_name,loan_number,amount)R21=(branch_name,loan_number,amount)R22=(customer_name,loan_number)最终的分解：R1,R21,R22,练习,设计关于供应商供应零件的数据库，要求达到3NF最初的设计：R(S#,Sname,City,Status,P#,Pname,C
16、olor,Weight,QTY)主码：(S#,P#)函数依赖：S#Sname,S#Status,S#City,City Status,P#Pname,P#Color,P#Weight,可见，其中有部分依赖，还有传递依赖。该模式仅为1NF,分解,第一步分解，消除部分依赖，得到：R1(S#,P#,QTY)，(S#,P#)为码R2(S#,Sname,City,Status)，S#为码R3(P#,Pname,Color,Weight)，P#为码R1和R3都已达到3NF，但R2存在传递依赖，仅是2NF第二步分解，消除R2中的传递依赖，得到：R2-1(S#,Sname,City)，S#为码R2-2(Cit
17、y,Status)，City为码R1,R2-1,R2-2和R3就是达到3NF的关系模式。此例中也已达到BCNF,判断是否BCNF,例2:SJP(学生S,课程J,名次P),(S,J)和(J,P)均为候选码函数依赖为(S,J)P,(J,P)S其中，两个决定因素均包含(是)候选码可见SJP BCNF,例3:STJ(学生S,教师T,课程J),(S,T)和(S,J)均为候选码函数依赖为(S,J)T,(S,T)J,T J其中，T为决定因素，但不包含任何一个候选码可见STJ BCNF,规范化过程小结,函数依赖理论,已知函数依赖集，求解所有被逻辑蕴涵的函数依赖保持无损连接特性的BCNF或3NF模式分解算法保持
18、依赖保持特性的BCNF或3NF模式分解算法,模式分解应满足的特性,无损连接性(Lossless join)保持函数依赖性(Preserve dependency)相互独立性分解后的关系模式中，当修改某一个关系数据时，不会影响其他关系,Armstrong公理,Armstrong公理：if,then(reflexivity 自反律)if,then(augmentation 增补律)if,and,then(transitivity 传递律)这些规则是正确有效的完备的用于求解 F+,例子,R=(A,B,C,G,H,I)F=A B，A C，CG H，CG I，B HF+中的部分成员A H 通过传递律 A
19、 B 和 B H 可得AG I 对A C进行增补,得到 AG CG 再通过传递律可得 CG I CG HI 对CG I 进行增补，可得 CG CGI,对CG H 进行增补，可得 CGI HI,再应用传递律可得,算法1：求属性集X关于函数依赖集F的闭包,计算属性闭包可用于检测超码、检测函数依赖、计算F的闭包。,例1,例2,例3,R=(A,B,C,G,H,I)F=A B，A C，CG H，CG I，B H求(AG)+1.result=AG2.result=ABCG(A C and A B)3.result=ABCGH(CG H and CG AGBC)result=ABCGHI(CG I and
20、CG AGBCH)AG 是一个候选码吗？(AG R?)AG 是一个超码吗？(A R?G R?),最小函数依赖集,函数依赖集合中可能存在冗余，如：A C 对于 A B,B C 来说，是冗余的A B,B C,A CD 可以被简化为 A B,B C,A D A B,B C,AC D 可以被简化为 A B,B C,A D 最小函数依赖集是指没有任何冗余的函数依赖集,定义,如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，或称最小依赖集F性质：函数依赖集F的最小函数依赖集不一定唯一，它与求解的次序有关定理：每一个函数依赖集F均等价于一个最小依赖集F,这样，R可以用R来取代,算法2：求函数依赖F的
21、最小依赖集F,例子,1）考查AB，去掉它，计算A+=AC，不包含B，不能去掉2）考查 B A，去掉它，计算BB C A，包含A，可去掉它3）考查 B C，去掉它，计算BB，不包含C，不能去掉4）考查A C，去掉它，计算AA B C，包含C，可去掉它5）考查 C A，去掉它，计算CC，不包含A，不能去掉,函数依赖集F的最小函数依赖集不一定唯一，它与求解的次序有关,R=(A,B,C)F=A BC，B C，A B，AB CF可分解并简化：F=A B，A C，B C，A B，AB CA B重复出现，去掉1个考虑到有A C，B为多余属性，去掉AB C考虑到A C可由A B，B C得到，去掉A C最小函数
22、依赖集F是:A B,B C,例2,算法3：检验一个分解是否具有无损连接性,初始表：,最后结果：,R1,R2,R3,R1,R2,R3,例1,例2,R(A,B,C),F=AB,C B分解1=（A,B）AB,（A,C）分解2=（A,B）AB,（B,C）CB 分析两种分解的无损连接性？分解1只具有无损连接性,分解2不具有无损连接性,AB,AC,a2,AB,BC,例3,设S-C-M（学号，班级，班主任）F=学号班级，班级班主任，学号班主任,存在传递依赖，为2NF,有三种可能的分解，哪些具有无损连接性？,该关系属于几范式？,算法4：检验一个分解是否具有保持函数依赖性,例1,设S-C-M（学号，班级，班主任
23、）F=学号班级，班级班主任，学号班主任,三种分解：,例2,R=(A,B,C)F=A B，B CKey=AR 不满足 BCNF将R分解为 R1=(A,B),R2=(B,C)R1 和 R2 满足 BCNF分解具有无损连接性分解具有依赖保持性,算法5：求解关系模式的候选码,属性分类L类：只出现在函数依赖的左边的属性R类：只出现在函数依赖的右边的属性N类：在函数依赖的两边均未出现的属性LR类：出现在函数依赖的两边的属性函数依赖图FDG用有向图表示的函数依赖，如,快速求解候选码的充分条件,对于给定的关系模式R及其函数依赖集F如果X是L或N类属性，则X必为R的任一候选码的成员如果X是R类属性，则X必不在任
24、何候选码中如果X是L和N类组成的属性组，且X+包含了全部属性，则X是R的唯一候选码,算法：对左边为单属性的函数依赖集求所有候选码,(1)求F的最小依赖集F(2)作出函数依赖图FDG(3)从FDG图中找出无入边的属性集X(4)察看FDG图中有无回路，若无，则输出X并结 束,否则进行下一步(5)从各独立回路中各取一个结点的属性与X组成一个候选码，重复取得所有可能的组合，即R的全部候选码,几个命题,一个无损连接的分解不一定具有依赖保持性，反之亦然若要求模式分解保持函数依赖，则模式分解总能达到3NF，但不一定能达到BCNF若要求分解既保持函数依赖，又具有无损连接性，则模式分离可以达到3NF，但不一定能达到BCNF,算法6：求R的保持函数依赖的3NF分解,算法7：求R的无损连接且保持函数依赖的3NF分解,总结,函数依赖1NF,2NF,3NF,BCNF的定义及判定模式分解及规范化过程模式分解的无损连接和依赖保持特性具有无损连接性的BCNF模式分解求解闭包、最小函数依赖集、候选码具有无损连接和依赖保持特性的3NF模式分解,
