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

关系数据库设计,主要内容,什么样的关系数据库设计是好的？函数依赖范式判断模式分解及相关算法,问题的提出,问题针对一个具体问题，如何构造合适的（更好的）数据模式？思路讨论一个关系中属性间的依赖情况讨论如何根据属性间依赖关系来判定关系是否有某些不合适的性质掌握基于函数依赖概念的关系数据库设计的规范方法,银行数据库模式,branch=(branch_name,branch_city,assets)customer=(customer_id,customer_name,customer_street,customer_city)loan=(loan_number,amount)loan_branch=(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,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),更大的模式实例分析1,方案1：borrower=(customer_id,loan_number)loan=(loan_number,amount)方案2：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对应的表不必连接运算，且没有信息冗余,更大的模式分析,试图将太多的属性放在一个表里，可能会导致异常：数据冗余：同样的信息在多条元组中重复出现插入异常：插入元组时可能由于部分属性的值未知而导致插入失败删除异常：部分元组的删除可能其他信息的丢失更新异常：存在数据冗余时，更新某元组而不是所有可能的元组，可能导致数据不一致,如：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班主任）,该模式设计不好，存在数据冗余、插入异常、删除异常和更新异常,以下哪一个分解是好的呢？,第一范式,FirstNormalForm（1NF）定义：关系R中每个属性域都是原子的，则R1NF非1NF的例子employee表中的children属性域是若干名字的集合employeeID由6位字符串组成，其中前两个字母表示所属部门，后面四位数字表示部门内编号（数据库应用程序中，字符串通常被认为是原子的，应尽量避免利用应用程序对数据进行解析）模式中使用非原子属性会导致设计中存储冗余数据如：为每一个客户存储一个accounts集合，为每一个account存储一个owners集合我们假设所有关系满足1NF,范式理论,目的：通过属性间的依赖关系，分析关系模式设计是否“好”规范化：将一个低一级范式的关系模式分解为若干个高一级范式的关系模式的过程基本思想：通过模式分解，逐步消除关系模式的数据依赖（函数依赖范畴）中不合适的部分（部分函数依赖和传递函数依赖），但又不丢失原模式中的信息（无损连接）模式分解可以消除冗余，解决更新异常等问题，但也要付出做连接运算等昂贵的代价,函数依赖,定义设R(U)是属性集U上的关系模式。X,Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作术语和记号，但，则称是平凡函数依赖，但，则称是非平凡函数依赖若，则X叫做决定因素,如：customer_name,loan_numbercustomer_namecustomer_namecustomer_name均为平凡函数依赖,函数依赖,在R(U)中，如果，并且对于X的任何一个真子集X,都有，则称Y对X完全函数依赖，记作若，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作在R(U)中，如果，()，则称Z对X传递函数依赖，记作K是关系模式R的超码当且仅当KRK是关系模式R的候选码当且仅当KR,且fornoK,R,F,P,传递,第二范式,SecondNormalForm(2NF)定义：若R1NF,且每个非主属性完全依赖于码，则R2NF说明：不存在非主属性部分依赖于码的关系为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为外码,第三范式,ThirdNormalForm(3NF)定义：若R2NF,且它的任何一个非主属性都不传递依赖于任何候选码，则R3NF说明：即不存在非主属性部分依赖和传递依赖于码的关系为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中被逻辑蕴涵的如：如果AB且BC，推理可得AC函数依赖集F中逻辑蕴含的所有函数依赖，成为F的闭包，表示为F+F+是F的超集,BCNF,已知函数依赖集合F对应的F+，对任意R和R，若任意函数依赖都满足：是平凡的(即)，且是R的超码，则关系R满足BCNF。,例1：bor_loan=(customer_id,loan_number,amount)，有loan_numberamount但loan_number不是超码，因此bor_loan不是BCNF,定义：若每一个决定因素都包含(或是)码，则RBCNF,Boyce-CoddNormalForm(BCNF),关系的关键字为（course,teacher,book）由于不存在非平凡的函数依赖，因此模式满足BCNF,course,teacher,book,databasedatabasedatabasedatabasedatabasedatabaseoperatingsystemsoperatingsystemsoperatingsystemsoperatingsystems,AviAviHankHankSudarshanSudarshanAviAviPetePete,DBConceptsUllmanDBConceptsUllmanDBConceptsUllmanOSConceptsStallingsOSConceptsStallings,classes,例2:,BCNF模式分解方法,给定关系模式R，假设其中的一个非平凡函数依赖不符合BCNF约束，则将R分解为：(U)(R-(-)例如：已知bor_loan=(customer_id,loan_number,amount)，且loan_numberamount，即bor_loan不满足BCNF设：=loan_number=amount则bor_loan可分解为：(U)=(loan_number,amount)(R-(-)=(customer_id,loan_number),BCNF模式分解算法,result:=R;done:=false;计算F+;while(notdone)doif(result中存在不属于BCNF的模式Ri)thenbegin令是Ri上的一个非平凡函数依赖，满足Ri不存在F+中,且=;result:=(resultRi)(Ri)(,);endelsedone:=true;注:用这个算法产生的分解不仅是一个BCNF分解，而且是无损分解,例3,已知关系模式R和函数依赖集FR=(branch_name,branch_city,assets,customer_name,loan_number,amount)F=branch_nameassets,branch_cityloan_numberamount,branch_nameKey=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,Color,Weight,QTY)主码：(S#,P#)函数依赖：S#Sname,S#Status,S#City,CityStatus,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(City,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其中，两个决定因素均包含(是)候选码可见SJPBCNF,例3:STJ(学生S,教师T,课程J),(S,T)和(S,J)均为候选码函数依赖为(S,J)T,(S,T)J,TJ其中，T为决定因素，但不包含任何一个候选码可见STJBCNF,规范化过程小结,函数依赖理论,已知函数依赖集，求解所有被逻辑蕴涵的函数依赖保持无损连接特性的BCNF或3NF模式分解算法保持依赖保持特性的BCNF或3NF模式分解算法,模式分解应满足的特性,无损连接性(Losslessjoin)保持函数依赖性(Preservedependency)相互独立性分解后的关系模式中，当修改某一个关系数据时，不会影响其他关系,Armstrong公理,Armstrong公理：if,then(reflexivity自反律)if,then(augmentation增补律)if,and,then(transitivity传递律)这些规则是正确有效的完备的用于求解F+,例子,R=(A,B,C,G,H,I)F=AB，AC，CGH，CGI，BHF+中的部分成员AH通过传递律AB和BH可得AGI对AC进行增补,得到AGCG再通过传递律可得CGICGHI对CGI进行增补，可得CGCGI,对CGH进行增补，可得CGIHI,再应用传递律可得,算法1：求属性集X关于函数依赖集F的闭包,计算属性闭包可用于检测超码、检测函数依赖、计算F的闭包。,例1,例2,例3,R=(A,B,C,G,H,I)F=AB，AC，CGH，CGI，BH求(AG)+1.result=AG2.result=ABCG(ACandAB)3.result=ABCGH(CGHandCGAGBC)result=ABCGHI(CGIandCGAGBCH)AG是一个候选码吗？(AGR?)AG是一个超码吗？(AR?GR?),最小函数依赖集,函数依赖集合中可能存在冗余，如：AC对于AB,BC来说，是冗余的AB,BC,ACD可以被简化为AB,BC,ADAB,BC,ACD可以被简化为AB,BC,AD最小函数依赖集是指没有任何冗余的函数依赖集,定义,如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，或称最小依赖集F性质：函数依赖集F的最小函数依赖集不一定唯一，它与求解的次序有关定理：每一个函数依赖集F均等价于一个最小依赖集F,这样，R可以用R来取代,算法2：求函数依赖F的最小依赖集F,例子,1）考查AB，去掉它，计算A+=AC，不包含B，不能去掉2）考查BA，去掉它，计算BBCA，包含A，可去掉它3）考查BC，去掉它，计算BB，不包含C，不能去掉4）考查AC，去掉它，计算AABC，包含C，可去掉它5）考查CA，去掉它，计算CC，不包含A，不能去掉,函数依赖集F的最小函数依赖集不一定唯一，它与求解的次序有关,R=(A,B,C)F=ABC，BC，AB，ABCF可分解并简化：F=AB，AC，BC，AB，ABCAB重复出现，去掉1个考虑到有AC，B为多余属性，去掉ABC考虑到AC可由AB，BC得到，去掉AC最小函数依赖集F是:AB,BC,例2,算法3：检验一个分解是否具有无损连接性,初始表：,最后结果：,R1,R2,R3,R1,R2,R3,例1,例2,R(A,B,C),F=AB,CB分解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（学号，班级，班主任）F=学号班级，班级班主任，学号班主任,三种分解：,例2,R=(A,B,C