关系数据库设计与范式理论.ppt

《关系数据库设计与范式理论.ppt》由会员分享，可在线阅读，更多相关《关系数据库设计与范式理论.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关系数据库设计关系数据库设计主要内容主要内容n什么样的关系数据库设计是好的？什么样的关系数据库设计是好的？n函数依赖函数依赖n范式判断范式判断n模式分解及相关算法模式分解及相关算法问题的提出问题的提出n问题问题l针对一个具体问题，如何构造针对一个具体问题，如何构造合适的（更好的）合适的（更好的）数数据模式？据模式？n思路思路l讨论一个关系中属性间的依赖情况讨论一个关系中属性间的依赖情况l讨论如何根据属性间依赖关系来判定关系是否有某讨论如何根据属性间依赖关系来判定关系是否有某些不合适的性质些不合适的性质n掌握掌握l基于函数依赖概念的关系数据库设计的规范方法基于函数依赖概念的关系数据库设计的规范方

2、法银行数据库模式银行数据库模式nbranch=(branch_name,branch_city,assets)ncustomer=(customer_id,customer_name,customer_street,customer_city)nloan=(loan_number,amount)nloan_branch=(loan_number,branch_name)naccount=(account_number,balance)naccount_branch=(account_number,branch_name)nemployee=(employee_id.employee_name,

3、telephone_number,start_date)ndependent_name=(employee_id,dname)nborrower=(customer_id,loan_number)ndepositor=(customer_id,account_number)ncust_banker=(customer_id,employee_id,type)nworks_for=(worker_employee_id,manager_employee_id)npayment=(loan_number,payment_number,payment_date,payment_amount)nsav

4、ings_account=(account_number,interest_rate)nchecking_account=(account_number,overdraft_amount)更大的模式更大的模式实例分析实例分析1n方案方案1：borrower=(customer_id,loan_number)loan=(loan_number,amount)n方案方案2：bor_loan=(customer_id,loan_number,amount)n显然，方案显然，方案2对应的表不必连接运算，但可能出现信息冗余对应的表不必连接运算，但可能出现信息冗余更大的模式更大的模式实例分析实例分析2n方

5、案方案1：loan_branch=(loan_number,branch_name)loan=(loan_number,amount)n方案方案2：loan_amt_br=(loan_number,amount,branch_name)n显然，方案显然，方案2对应的表不必连接运算，且没有信息冗余对应的表不必连接运算，且没有信息冗余更大的模式更大的模式分析分析n试图将太多的属性放在一个表里，可能会导致异常试图将太多的属性放在一个表里，可能会导致异常：l数据冗余数据冗余：同样的信息在多条元组中重复出现：同样的信息在多条元组中重复出现l插入异常插入异常：插入元组时可能由于部分属性的值未知而导致插入失

6、败：插入元组时可能由于部分属性的值未知而导致插入失败l删除异常删除异常：部分元组的删除可能其他信息的丢失：部分元组的删除可能其他信息的丢失l更新异常更新异常：存在数据冗余时，更新某元组而不是所有可能的元组，可：存在数据冗余时，更新某元组而不是所有可能的元组，可能导致数据不一致能导致数据不一致n 如：如：Movie-Star数据库模式数据库模式更小的模式更小的模式实例分析实例分析1n假设已知模式假设已知模式 bor_loan=(customer_id,loan_number,amount)，如何将如何将模式分解模式分解成：成：borrower=(customer_id,loan_number)l

7、oan=(loan_number,amount)更小的模式更小的模式实例分析实例分析2n并不是所有的分解都是并不是所有的分解都是有益的有益的n如将如将 employee 表分解表分解l该分解是有损的，即该分解是有损的，即无法通过自然连接重无法通过自然连接重建原模式建原模式更小的模式更小的模式实例分析实例分析3n模式模式S-C-M（S学号，学号，C班级，班级，M班主任）班主任）l该模式设计不好，存在数据冗余、插入异常、删除异常和更新异常该模式设计不好，存在数据冗余、插入异常、删除异常和更新异常l以下哪一个分解是好的呢？以下哪一个分解是好的呢？第一范式第一范式nFirst Normal Form（

8、1NF）n定义：关系定义：关系R中每个属性域都是原子的，则中每个属性域都是原子的，则R 1NF n非非1NF的例子的例子lemployee表中的表中的children属性域是若干名字的集合属性域是若干名字的集合lemployeeID由由6位字符串组成，其中前两个字母表示所属部门，后位字符串组成，其中前两个字母表示所属部门，后面四位数字表示部门内编号（数据库应用程序中，字符串通常被面四位数字表示部门内编号（数据库应用程序中，字符串通常被认为是原子的，应尽量避免利用应用程序对数据进行解析）认为是原子的，应尽量避免利用应用程序对数据进行解析）n模式中使用非原子属性会导致设计中存储冗余数据模式中使用非

9、原子属性会导致设计中存储冗余数据l如：为每一个客户存储一个如：为每一个客户存储一个 accounts集合，为每一个集合，为每一个account存储一个存储一个owners集合集合n我们假设我们假设所有关系满足所有关系满足1NF范式理论n目的：通过属性间的依赖关系，分析关系模式设计是否目的：通过属性间的依赖关系，分析关系模式设计是否“好好”n规范化：将一个低一级范式的关系规范化：将一个低一级范式的关系模式分解模式分解为若干个高一级为若干个高一级范式的关系模式的过程范式的关系模式的过程n基本思想：通过模式分解，逐步消除关系模式的数据依赖基本思想：通过模式分解，逐步消除关系模式的数据依赖（函数依赖范

10、畴函数依赖范畴）中不合适的部分（部分函数依赖和传递函）中不合适的部分（部分函数依赖和传递函数依赖），但又不丢失原模式中的信息（数依赖），但又不丢失原模式中的信息（无损连接无损连接）n模式分解可以消除冗余，解决更新异常等问题，但也要付出模式分解可以消除冗余，解决更新异常等问题，但也要付出做连接运算等昂贵的代价做连接运算等昂贵的代价函数依赖n定义定义l设设R(U)是属性集是属性集U上的关系模式。上的关系模式。X,Y是是U的子集。若的子集。若对于对于R(U)的任意一个可能的关系的任意一个可能的关系r，r中不可能存在两个中不可能存在两个元组在元组在X上的属性值相等，而在上的属性值相等，而在Y上的属性值

11、不等，则上的属性值不等，则称称X函数确定函数确定Y或或Y函数依赖于函数依赖于X，记作，记作n术语和记号术语和记号l ，但，但 ，则称，则称 是平凡函数依赖是平凡函数依赖l ，但，但 ，则称，则称 是非平凡函数依赖是非平凡函数依赖l若若 ，则，则X叫做决定因素叫做决定因素如：如：customer_name,loan_number customer_name customer_name customer_name均为平凡函数依赖均为平凡函数依赖函数依赖n在在R(U)中，如果中，如果 ，并且对于，并且对于X的任何一个真子集的任何一个真子集X,都有都有 ，则称，则称Y对对X完全函数依赖完全函数依赖，记

12、作，记作n若若 ，但，但Y不完全函数依赖于不完全函数依赖于X，则称，则称Y对对X部分函数依赖部分函数依赖，记作记作n在在R(U)中，如果中，如果 ，()，则称，则称Z对对X传递函数依赖传递函数依赖，记作，记作nK是关系模式是关系模式R的的超码超码当且仅当当且仅当K RnK是关系模式是关系模式R的的候选码候选码当且仅当当且仅当K R,且且for no K,RFP传递传递第二范式第二范式nSecond Normal Form(2NF)n定义：定义：若若R 1NF,且每个非主属性完全依赖于码，则且每个非主属性完全依赖于码，则R 2NFn说明：不存在非主属性部分依赖于码的关系为说明：不存在非主属性部分

13、依赖于码的关系为2NFn例例:学生学生-课程课程-成绩管理关系模式成绩管理关系模式属性组属性组U=学号学号SNO,系名系名SDEPT,系主任系主任MN,课程号课程号CNO,成绩成绩G数据依赖数据依赖v该模式存在非主属性部分函数依赖，达不到该模式存在非主属性部分函数依赖，达不到2NF，属于，属于1NF。分解方法n一个一个1NF，但非，但非2NF的关系总是可以被分解成为一组的关系总是可以被分解成为一组2NF的关系的关系n方法：方法：已知关系已知关系R(A,B,C,D),(A,B)为主码，即为主码，即(A,B)-C,(A,B)-D，且，且A-D,则将则将R分解成为分解成为:R1(A,D),A为主码为

14、主码R2(A,B,C),(A,B)为主码，为主码，A为外码为外码R(SNO,SDEPT,MN,CNO,G)1NFSC(SNO,CNO,G);S-M(SNO,SDEPT,MN);2NF模式分解模式分解第三范式第三范式nThird Normal Form(3NF)n定义：定义：若若R 2NF,且它的任何一个非主属性都不传递且它的任何一个非主属性都不传递依赖于任何候选码，则依赖于任何候选码，则R 3NFn说明：即不存在非主属性部分依赖和传递依赖于码的说明：即不存在非主属性部分依赖和传递依赖于码的关系为关系为3NFS-M中存在传递传递依赖，故该模式不是中存在传递传递依赖，故该模式不是3NF上例分解为：

15、上例分解为：SC(SNO,CNO,G);S-M(SNO,SDEPT,MN);分解方法n一个一个2NF，但非，但非3NF的关系总是可以被分解成为一组的关系总是可以被分解成为一组3NF的关系的关系n方法：方法：已知关系已知关系R(A,B,C),A为主码为主码(A-B,A-C)，且，且B-C，则可将，则可将R分解为分解为:R1(B,C),B为主码为主码 R2(A,B),A为主码，为主码，B为外码为外码R(SNO,SDEPT,MN,CNO,G)1NFSC(SNO,CNO,G);S-M(SNO,SDEPT,MN);2NF模式分解模式分解模式分解模式分解SC(SNO,CNO,G);S-D(SNO,SDEP

16、T)D-L(SDEPT,MN)3NF函数依赖集的闭包函数依赖集的闭包n给定函数依赖集给定函数依赖集F，有一些函数依赖是在，有一些函数依赖是在F中被中被逻辑蕴涵逻辑蕴涵的的l如：如果如：如果 A B 且且 B C，推理可得推理可得A Cn函数依赖集函数依赖集F 中逻辑蕴含的所有函数依赖，成为中逻辑蕴含的所有函数依赖，成为F的闭包，表示为的闭包，表示为F+nF+是是F的超集的超集BCNF 已知函数依赖集合已知函数依赖集合F对应的对应的F+，对任意，对任意 R 和和 R，若任若任意函数依赖意函数依赖 都满足：都满足：是平凡的是平凡的(即即 )，且，且 是是R的超码的超码，则关系则关系R满足满足BCN

17、F。例1：bor_loan=(customer_id,loan_number,amount)，有 loan_number amount 但 loan_number 不是超码，因此bor_loan不是BCNFv定义：若每一个决定因素都包含定义：若每一个决定因素都包含(或是或是)码，则码，则R BCNF Boyce-Codd Normal Form(BCNF)n关系的关键字为（关系的关键字为（course,teacher,book）n由于不存在非平凡的函数依赖，因此模式满足由于不存在非平凡的函数依赖，因此模式满足BCNF courseteacherbookdatabasedatabasedatab

18、asedatabasedatabasedatabaseoperating systemsoperating systemsoperating systemsoperating systemsAviAviHankHankSudarshanSudarshanAviAvi PetePeteDB ConceptsUllmanDB ConceptsUllmanDB ConceptsUllmanOS ConceptsStallingsOS ConceptsStallingsclasses例例2:BCNF 模式分解方法模式分解方法n给定关系模式给定关系模式R，假设其中的一个非平凡函数依赖，假设其中的一个非平

19、凡函数依赖 不符合不符合BCNF约束，则将约束，则将R分解为：分解为：(U )(R-(-)n例如：已知 bor_loan=(customer_id,loan_number,amount)，且 loan_number amount，即bor_loan不满足BCNF 设：l=loan_numberl=amount则 bor_loan 可分解为：l(U )=(loan_number,amount)l(R-(-)=(customer_id,loan_number)BCNF 模式分解算法模式分解算法result:=R;done:=false;计算 F+;while(not done)doif(resul

20、t 中存在不属于BCNF的模式 Ri)then begin令令 是Ri 上的一个非平凡函数依赖，满足 Ri 不 存在 F+中,且 =;result:=(result Ri)(Ri )(,);endelse done:=true;注:用这个算法产生的分解不仅是一个 BCNF 分解，而且是无损分解例例3n已知关系模式已知关系模式 R 和函数依赖集和函数依赖集 F R=(branch_name,branch_city,assets,customer_name,loan_number,amount)F=branch_name assets,branch_city loan_number amount,

21、branch_name Key=loan_number,customer_namen可知，可知，R不是不是BCNF，因为存在函数依赖，其决定因素不包含，因为存在函数依赖，其决定因素不包含(是是)码码n模式分解为：模式分解为：lR1=(branch_name,branch_city,assets)lR2=(branch_name,customer_name,loan_number,amount)l R21=(branch_name,loan_number,amount)l R22=(customer_name,loan_number)n最终的分解：最终的分解：R1,R21,R22练习n设计关于供

22、应商供应零件的数据库，要求达到设计关于供应商供应零件的数据库，要求达到3NFn最初的设计：最初的设计：R(S#,Sname,City,Status,P#,Pname,Color,Weight,QTY)l主码：主码：(S#,P#)l函数依赖：函数依赖：S#Sname,S#Status,S#City,City Status,P#Pname,P#Color,P#Weight n可见，其中有部分依赖，还有传递依赖。该模式仅为可见，其中有部分依赖，还有传递依赖。该模式仅为1NF分解第一步分解第一步分解，消除部分依赖，得到：，消除部分依赖，得到：R1(S#,P#,QTY)，(S#,P#)为码为码R2(S#

23、,Sname,City,Status)，S#为码为码R3(P#,Pname,Color,Weight)，P#为码为码R1和和R3都已达到都已达到3NF，但，但R2存在传递依赖，仅是存在传递依赖，仅是2NF第二步分解第二步分解，消除，消除R2中的传递依赖，得到：中的传递依赖，得到：R2-1(S#,Sname,City)，S#为码为码R2-2(City,Status)，City为码为码R1,R2-1,R2-2和和R3就是达到就是达到3NF的关系模式。的关系模式。此例中也已达到此例中也已达到BCNF判断是否BCNFn例例2:SJP(学生学生S,课程课程J,名次名次P)l(S,J)和和(J,P)均为候

24、选码均为候选码l函数依赖为函数依赖为(S,J)P,(J,P)S其中，两个决定因素均包含其中，两个决定因素均包含(是是)候选码候选码可见可见SJP BCNFn例例3:STJ(学生学生S,教师教师T,课程课程J)l(S,T)和和(S,J)均为候选码均为候选码l函数依赖为函数依赖为(S,J)T,(S,T)J,T J其中，其中，T为决定因素，但不包含任何一个候选码为决定因素，但不包含任何一个候选码可见可见STJ BCNF 规范化过程小结1NF2NF3NFBCNF消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和

25、传递函数依赖消除主属性对码的部分和传递函数依赖函数依赖理论函数依赖理论n已知函数依赖集，求解所有被逻辑蕴涵的函数依赖已知函数依赖集，求解所有被逻辑蕴涵的函数依赖n保持无损连接特性的保持无损连接特性的BCNF或或3NF模式分解算法模式分解算法n保持依赖保持特性的保持依赖保持特性的BCNF或或3NF模式分解算法模式分解算法模式分解应满足的特性n无损连接性无损连接性(Lossless join)n保持函数依赖性保持函数依赖性(Preserve dependency)n相互独立性相互独立性l分解后的关系模式中，当修改某一个关系数据时，不会影分解后的关系模式中，当修改某一个关系数据时，不会影响其他关系响

26、其他关系Armstrong公理公理nArmstrong公理：公理：lif ,then (reflexivity 自反律自反律)lif ,then (augmentation 增补律增补律)lif ,and ,then (transitivity 传递律传递律)n这些规则是这些规则是l正确有效的正确有效的l完备的完备的n用于求解用于求解 F+例子例子nR=(A,B,C,G,H,I)F=A B，A C，CG H，CG I，B HnF+中的部分成员中的部分成员lA H 4通过传递律通过传递律 A B 和和 B H 可得可得lAG I 4对对A C进行增补进行增补,得到得到 AG CG 再通过传递律可

27、得再通过传递律可得 CG I lCG HI 4对对CG I 进行增补，可得进行增补，可得 CG CGI,对对CG H 进行增补，可得进行增补，可得 CGI HI,再应用传递律可得再应用传递律可得算法算法算法算法1 1：求属性集：求属性集：求属性集：求属性集X X关于函数依赖集关于函数依赖集关于函数依赖集关于函数依赖集F F的闭包的闭包的闭包的闭包计算属性闭包可用于检测超码、检测函数依赖、计算计算属性闭包可用于检测超码、检测函数依赖、计算F的闭包。的闭包。例1例2例例3nR=(A,B,C,G,H,I)nF=A B，A C，CG H，CG I，B Hn求(AG)+1.result=AG2.resu

28、lt=ABCG (A C and A B)3.result=ABCGH (CG H and CG AGBC)4.result=ABCGHI (CG I and CG AGBCH)nAG 是一个候选码吗？(AG R?)nAG 是一个超码吗？(A R?G R?)最小函数依赖集最小函数依赖集n函数依赖集合中可能存在冗余，如：函数依赖集合中可能存在冗余，如：lA C 对于对于 A B,B C 来说，是冗余的来说，是冗余的lA B,B C,A CD 可以被简化为可以被简化为 A B,B C,A D lA B,B C,AC D 可以被简化为可以被简化为 A B,B C,A D n最小函数依赖集最小函数依赖

29、集是指没有任何冗余的函数依赖集是指没有任何冗余的函数依赖集 定义n如果函数依赖集如果函数依赖集F满足下列条件，则称满足下列条件，则称F为一个极小函数依赖集，为一个极小函数依赖集，或称或称最小依赖集最小依赖集Fn性质：函数依赖集性质：函数依赖集F的最小函数依赖集不一定唯一，它与求解的最小函数依赖集不一定唯一，它与求解的次序有关的次序有关n定理：每一个函数依赖集定理：每一个函数依赖集F均等价于一个最小依赖集均等价于一个最小依赖集F这样，这样，R可以用可以用R来取代来取代算法算法2：求函数依赖：求函数依赖F的最小依赖集的最小依赖集F例子1）考查）考查AB，去掉它，计算，去掉它，计算A+=A C，不包

30、含，不包含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的最小函数依赖集不一定唯一，它与求解的次序有关的最小函数依赖集不一定唯一，它与求解的次序有关nR=(A,B,C)F=A BC，B C，A B，AB CnF可分解并简化：lF

31、=A B，A C，B C，A B，AB ClA B重复出现，去掉1个l考虑到有A C，B为多余属性，去掉AB Cl考虑到A C可由A B，B C得到，去掉A Cn最小函数依赖集F是:A B,B C例2算法算法3 3：检验一个分解是否具有无损连接性：检验一个分解是否具有无损连接性ABCDEa1a2a3a3a4a4a5ABCDEa1a2a3a4a5a3a4a5a4a5初始表：初始表：最后结果：最后结果：R1R2R3R1R2R3例例1例2nR(A,B,C),F=AB,C Bl分解分解1=（A,B）AB,（A,C）l分解分解2=（A,B）AB,（B,C）CB n分析两种分解的无损连接性？分析两种分解的

32、无损连接性？l分解分解1只具有无损连接性只具有无损连接性,分解分解2不具有无损连接性不具有无损连接性ABCa1a2a1a3ABACa2ABCa1a2a2a3ABBC例例3n设设S-C-M（学号，班级，班主任）（学号，班级，班主任）F=学号学号班级，班级班级，班级班主任，学号班主任，学号班主任班主任存在传递依赖，为存在传递依赖，为2NF有三种可能的分解，哪些具有无损连接性？有三种可能的分解，哪些具有无损连接性？该关系属于几范式？该关系属于几范式？算法算法4 4：检验一个分解是否具有保持函数依赖性：检验一个分解是否具有保持函数依赖性例例1n设设S-C-M（学号，班级，班主任）（学号，班级，班主任）

33、F=学号学号班级，班级班级，班级班主任，学号班主任，学号班主任班主任三种分解：三种分解：例例2nR=(A,B,C)F=A B，B CKey=AnR 不满足 BCNFn将R分解为 R1=(A,B),R2=(B,C)lR1 和 R2 满足 BCNFl分解具有无损连接性l分解具有依赖保持性算法5：求解关系模式的候选码n属性分类属性分类lL类：只出现在函数依赖的左边的属性类：只出现在函数依赖的左边的属性lR类：只出现在函数依赖的右边的属性类：只出现在函数依赖的右边的属性lN类：在函数依赖的两边均未出现的属性类：在函数依赖的两边均未出现的属性lLR类：出现在函数依赖的两边的属性类：出现在函数依赖的两边的

34、属性n函数依赖图函数依赖图FDGl用有向图表示的函数依赖，如用有向图表示的函数依赖，如XY即即X Y快速求解候选码的充分条件n对于给定的关系模式对于给定的关系模式R及其函数依赖集及其函数依赖集Fl如果如果X是是L或或N类属性，则类属性，则X必为必为R的任一候选码的成员的任一候选码的成员l如果如果X是是R类属性，则类属性，则X必不在任何候选码中必不在任何候选码中l如果如果X是是L和和N类组成的属性组，且类组成的属性组，且X+包含了全部属性，则包含了全部属性，则X是是R的唯一候选码的唯一候选码算法：对左边为单属性的函数依赖集求所有候选码算法：对左边为单属性的函数依赖集求所有候选码 (1)求求F的最

35、小依赖集的最小依赖集F(2)作出函数依赖图作出函数依赖图FDG(3)从从FDG图中找出无入边的属性集图中找出无入边的属性集X(4)察看察看FDG图中有无回路，若无，则输出图中有无回路，若无，则输出X并结并结 束束,否则进行下一步否则进行下一步(5)从各从各独立回路独立回路中各取一个结点的属性与中各取一个结点的属性与X组成一个候选码，重复组成一个候选码，重复取得所有可能的组合，即取得所有可能的组合，即R的全部候选码的全部候选码ZWYXSDIBOQIBOQSD 几个命题n一个无损连接的分解不一定具有依赖保持性，反之亦然一个无损连接的分解不一定具有依赖保持性，反之亦然n若要求模式分解保持函数依赖，则

36、模式分解总能达到若要求模式分解保持函数依赖，则模式分解总能达到3NF，但不一定能达到，但不一定能达到BCNFn若要求分解既保持函数依赖，又具有无损连接性，则模若要求分解既保持函数依赖，又具有无损连接性，则模式分离可以达到式分离可以达到3NF，但不一定能达到，但不一定能达到BCNF算法算法算法算法6 6：求：求：求：求R R的保持函数依赖的的保持函数依赖的的保持函数依赖的的保持函数依赖的3NF3NF分解分解分解分解算法算法算法算法7 7：求：求：求：求R R的无损连接且保持函数依赖的的无损连接且保持函数依赖的的无损连接且保持函数依赖的的无损连接且保持函数依赖的3NF3NF分解分解分解分解总结n函数依赖函数依赖n1NF,2NF,3NF,BCNF的定义及判定的定义及判定n模式分解及规范化过程模式分解及规范化过程n模式分解的无损连接和依赖保持特性模式分解的无损连接和依赖保持特性n具有无损连接性的具有无损连接性的BCNF模式分解模式分解n求解闭包、最小函数依赖集、候选码求解闭包、最小函数依赖集、候选码n具有无损连接和依赖保持特性的具有无损连接和依赖保持特性的3NF模式分解模式分解