《关系数据理论.ppt》由会员分享，可在线阅读，更多相关《关系数据理论.ppt（74页珍藏版）》请在三一办公上搜索。
1、关系数据理论,要点,关系规范化理论研究背景数据依赖规范化(Normalization)理论1NF、2NF、3NF、BCNF、4NF等范式关系模式规范化的必要性及方法,5.1 问题的提出,问题提出：针对一个具体问题，如何构造合适的(更好的)数据模式，即如何更好地设计数据的逻辑结构？关系数据理论的研究背景关系模型建立在严格的数据理论基础上，并可向别的数据模型转换，因此常以关系模型为背景来讨论这个问题,背景知识,数据模式(schema)数据库中全体数据的逻辑结构和特征描述，如数据记录的构成，数据间的联系，安全性、完整性要求等。常以某一种数据模型为基础关系模型的形式化定义：R(U,D,dom,F)，本
2、章简化为R(U,F)关系模型R的一个关系r：U上的一个关系r满足F,属性组,一组数据依赖,一个例子：学生-课程-成绩管理,客观存在的事实一个系有若干学生，但一个学生只属于一个系；一个系只有一名负责人；一个学生可以选修多门课程，每门课程有若干学生选修；每个学生学习每一门课程有一个成绩设计如下单个模式属性组U=学号SNO,系名SDEPT,系负责人MN,课程名CNAME,成绩G数据依赖,该模式存在的问题？怎么改善这个模式？,问题和改进,该模式存在的问题插入异常：一个系无学生或未安排课程时，无法存入系与负责人删除异常：删除一个系的所有学生信息时，系与负责人也丢失冗余太大：负责人姓名重复存入更新异常：当
3、某系负责人更换时，须更新该系所有学生信息中的信息，更新不完全时，易造成数据不一致原因：数据依赖存在一些不合适的性质，需寻找更好的模式，如S(SNO,SDEPT,)SG(SNO,CNAME,G,)DEPT(SDEPT,MN,),5.2 规范化,意图讨论一个关系属性间不同的依赖情况讨论如何根据属性间依赖关系来判定关系是否有某些不合适的性质数据依赖概念反映客观世界数据间的相互关联通过一个关系中属性间值的相等与否来体现两种重要的数据依赖函数依赖(Functional Dependency,FD)多值依赖(Multivalued Dependency,MVD),5.2.1 函数依赖,定义1设R(U)是属
4、性集U上的关系模式。X,Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作术语和记号，但，则称 是非平凡的函数依赖，但，则称 是平凡的函数依赖若，则X叫做决定因素若，则记作若Y不函数依赖于X，则记作,对函数依赖的说明,换句话说：任何时候若某一关系中的两个元组中的X属性组的值相等，则元组中对应的属性组Y的值也相等，类似于函数概念，Y=f(X)需要指出的是：关系R中，如果属性组X是一个候选码或码，则属性组Y一定函数依赖于X（这与候选码的定义一致）事实上：如果关系R上有函数依赖XY，而属性X不是一
5、个候选码，则R中可能存在一些数据冗余例如：R(Sno,Sdept,MN,Cname,Grade)中有函数依赖Sdept-MN，而Sdept并不是候选码，表中数据有大量冗余出现,函数依赖,定义2在R(U)中，如果，并且对于X的任何一个真子集X,都有，则称Y对X完全函数依赖，记作若，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作定义3在R(U)中，如果，()，则称Z对X传递函数依赖，记作,F,P,传递,5.2.2 码,用函数依赖的概念来定义码定义4 设K为R(U,F)中的属性或属性组合，若 则K为R的候选码(Candidate Key)。若候选码多于一个，则选定其中的一个为主码(Primar
6、y Key)相关术语包含在任何一个候选码中的属性，叫做主属性不包含在任何码中的属性，叫做非主属性整个属性组是码，称为全码,F,码,定义5关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码(Foreign Key)，也称为外码 主码与外码提供了一个表示关系间联系的手段SC(Sno,Cno,Grade)Studen(Sno,Sname,.)Course(Cno,Cname,.),5.2.3 范式,范式：符合某种级别(条件、要求)的关系模式范式种类1NF,2NF,3NF,BCNF,4NF,5NF按级别(条件、要求)由低到高：1NF 2NF 3NF BCNF 4NF 5
7、NF通常称某一关系模式R为第几范式，记作R xNF,1NF(First Normal Form),定义：关系R中每个分量都是不可分割的数据项，则R 1NF说明：1NF是关系模式的基本要求举例：关系模式S-L-C(学号SNO,系SDEPT,住处SLOC,课程CNO,成绩G)是1NF,5.2.4 2NF,定义：若R 1NF,且每个非主属性完全依赖于码，则R 2NF说明：不存在非主属性部分依赖于码的关系为2NF举例：关系模式 S-L-C(SNO,SDEPT,SLOC,CNO,G)函数依赖图,关系模式S-L-C是不是2NF？,不是，因为SDEPT和SLOC部分依赖于码,前面的实例是不是2NF？,不是2
8、NF可能出现的问题,插入异常某学生没有选课时，无法插入其系、住处等信息删除异常某学生所有的选课信息都删除后，其系、住处等信息也被删除修改复杂（更新异常）学生转系时，除了修改其系名外，还需修改其住处信息；另外，若该学生选修了多门课程，则其对应的重复存储的系、住处等信息需一一修改冗余同系的所有学生的住处信息重复存储，同一学生选多门课程时，其系、住处信息重复存储,解决办法,模式分解依赖关系分析上例中的模式分解为下列两个模式，该模式是2NFSC(SNO,CNO,G)(SNO,CNO)GS-L(SNO,SDEPT,SLOC)SNO SDEPT,SNO SLOC,SDEPT SLOC,分解说明,一个1NF
9、，但非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为外码这样，R可以通过R1和R2的自然连接运算得以恢复，即满足分解的无损连接性,5.2.5 3NF,定义：若R2NF,且它的任何一个非主属性都不传递依赖于任何候选码，则R 3NF说明：即不存在非主属性部分依赖和传递依赖于码的关系为3NF推论：不存在非主属性的模式为3NF上例中得到的关系模式是2NF
10、 SC(SNO,CNO,G);S-L(SNO,SDEPT,SLOC);,S-L中存在传递传递依赖，故该模式不是3NF,可能问题？如何改造？,不是3NF可能存在的问题,插入异常只有当知道某学生的系时才能插入其住处信息删除异常当删除某系对应的所有学生时，有关该系学生住处的信息也被删除掉了修改异常一个系及其住处信息重复出现，只更新一个元组中对应的系及其住处时可能导致数据不一致冗余同系学生的住处重复存储,解决方法,继续模式分解如上例中的模式可分解为3NFSC(SNO,CNO,G);(SNO,CNO)G S-D(SNO,SDEPT);SNO SDEPT D-L(SDEPT,SLOC);SDEPT SLO
11、C,SNO,SDEPT,SLOC,SDEPT,分解说明,一个2NF，但非3NF的关系总是可以被分解成为一组3NF的关系规范化过程中通过一组投影运算消除传递依赖，建议作如下分解(第二步分解)已知关系R(A,B,C),A为主码(A-B,A-C)，且B-C,则将R分解成为两个投影:R1(B,C),B为主码R2(A,B),A为主码，B为外码这样，R可以通过R1和R2的自然连接运算得以恢复，分解满足分解的无损连接性,3NF的进一步说明,在不考虑主属性对码的部分依赖和传递依赖时，可以认为是实现了彻底的分离，已消除了插入异常，删除异常，修改异常，冗余等问题但是，当关系中存在两个或更多的候选码时，尤其是有几个
12、候选码、且候选码内的属性又有部分复合或交迭时，仅仅满足3NF仍有问题，需要进一步分解成BCNF,5.2.6 BCNF,(Boyce/Codd Normal Form)定义：若每一个决定因素都包含(或是)码，则R BCNF说明BCNF中所有的依赖都是包含码的依赖一个BCNF范式必是3NF，但一个3NF范式不一定是BCNF(3NF中可能存在主属性对码的部分和传递依赖)BCNF是在函数依赖范畴内对关系模式的彻底分离，已消除了插入和删除异常通常认为BCNF是扩充的第三范式，一般数据库设计达到BCNF已足够,实例,例1:SJP(学生S,课程J,名次P)(S,J)和(J,P)均为候选码函数依赖为(S,J)
13、P,(J,P)S其中，两个决定因素均包含(是)候选码可见SJP BCNF例2:STJ(学生S,教师T,课程J)(S,T)和(S,J)均为候选码函数依赖为(S,J)T,(S,T)J,T J其中，T为决定因素，但不包含任何一个候选码可见STJ 3NF,但STJ BCNF,例子,前例是3NF,也是BCNFSC(SNO,CNO,G);(SNO,CNO)GS-D(SNO,SDEPT);SNO SDEPTD-L(SDEPT,SLOC);SDEPT SLOC,SNO,SDEPT,SLOC,SDEPT,5.2.7 多值依赖,属于BCNF的关系模式是不是很完美了呢？教材P178例子存在问题？如何解决？,5.2.
14、8 4NF,4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖如果一个关系模式是4NF，必定为BCNF一个关系模式是BCNF，但不是4NF，依然有不好的性质，可以用投影分解的办法解决例：WSC(仓库W,保管员S,商品C)全码(W,S,C)存在多值依赖WS,WC，WSC 4NF可进一步分解使之满足4NF:WS(W,S),WC(W,C)4NF是多值依赖范畴内最高程度的规范化,5.2.9 规范化理论,规范化概念：将一个低一级范式的关系模式分解为若干个高一级范式的关系模式的过程目的：设计正确、良好的关系模式基本思想：逐步消除关系模式的数据依赖中不合适的部分，使模式达到一定程度的分离，
15、但又不丢失原模式中的信息模式分解的实质：投影,几个事实,模式分解可以消除冗余，解决更新异常等问题，但也要付出做连接运算等昂贵的代价需要强调的是：对已知关系模式的范式等级是语义上的，而不仅仅是看某个时刻关系中的数据值，必须考察数据间的依赖即便是知道了数据依赖，也不能证明一个关系是否3NF。我们只能首先假设这个关系是3NF，而去验证给出的关系中没有违反数据依赖的情形,规范化理论,如何辨别一个关系模式的“好坏”？不存在部分和传递函数依赖等“不好”的性质的模式是“好”模式，否则会出现冗余和插入、删除、更新等异常现象规范化过程是用于设计好的数据库的有力辅助，但并不是唯一的方法 最初的设计中尽量做到“概念
16、单一化”，即做到让一个关系描述一个概念、一个实体或实体间的一种联系，这样所设计的关系模式将会接近或达到第三范式，甚至达到BCNF,规范化过程小结,练习一,设计关于供应商供应零件的数据库，要求达到3NF最初的设计：R(S#,Sname,City,Status,P#,Pname,Color,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#)为码
17、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,练习二,设计订货系统的数据库，包括顾客、货物和订货单信息初模式：顾客(顾客号，收货地址，赊购限额，余额，折扣)货物(货物号，制造厂商，实际存货量，规定的最低存货量，货物描述)订货单(订货单号，顾
18、客号，货物号，订货数量，订货细则，未发数量，订货日期，经办人),问题分析：顾客模式中，顾客号不能唯一决定收货地址 货物模式中，货物描述部分依赖于码 订货单模式中，未发数量将随发货过程更新，而其他信息相对静态；订货细则有多条,改进模式,顾客及其地址(顾客号，收货地址)顾客及其余额(顾客号，赊购限额，余额，折扣)货物及其厂商(货物号，制造厂商，实际存货量，规定的最低存货量)货物及其描述-2(货物号，货物描述)订货单(订货单号，顾客号，货物号，订货数量，订货日期，经办人)发货(订货单号，未发货量)发货(订货单号，订货细则),练习三,欲设计移动公司手机信息管理系统，用于管理：1、手机销售信息（由营业厅
19、售给用户）2、手机用户档案信息（用户名，证件号码等）3、手机通话信息（每一次通话的详细情况）4、手机话费信息（每月的话费组成）在此基础上实现常用的查询，如：1、每月手机的销售情况 2、每种机型的销售情况 3、每个营业厅的手机销售情况 4、根据手机号码查询其用户信息 5、根据手机号码查询某时间段内的通话情况 6、每月手机话费收入 7、欠费用户查询试设计合适的数据库，并在此基础上用SQL实现所有的查询,设计结果,营业厅(营业厅编号，地址，负责人)销售记录(营业厅编号，机型，数量，日期，经办人)手机销售单价(机型，单价)手机用户信息(手机号码，用户名，住址，证件号码)手机通话记录(手机号码，被叫号码
20、，日期，起始时刻，通话时长)手机话费信息(手机号码，话费，漫游费，短信费)话费缴费信息(手机号码，缴费日期，金额，缴费营业厅),定义回顾：函数依赖,设R(U)是属性集U上的关系模式，X,Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作XY,5.3 Armstrong公理系统,定义：逻辑蕴涵对于满足一组函数依赖F的关系模式R，其任何一个关系r，若函数依赖XY都成立，则称F逻辑蕴含X YArmstrong公理系统是函数依赖的一个有效而完备的公理系统可用于从一组函数依赖F求得蕴含(导出)的函数依
21、赖可用于求得关系模式的码,Armstrong公理系统,Armstrong公理系统A1自反律：A2增广律：A3传递律：Armstrong公理系统的推理规则合并规则:伪传递规则:分解规则:引理5.1(由合并规则和分解规则可得),Armstrong公理系统,定义：闭包在关系模式R中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为F+Armstrong公理系统是有效的、完备的Armstrong公理系统的有效性由F出发根据Armstrong公理导出的每一个函数依赖一定在F+中Armstrong公理系统的完备性F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理导出,或导出,怎样计算F+?怎
22、样判断一个函数依赖一定在闭包中？,定义,设F为属性集U上的一组函数依赖，XU，X+FAX A能由Armstrong公理导出,X+F称为属性集X关于函数依赖F的闭包引理2：设F为属性集U上的一组函数依赖，X,YU，X Y能根据Armstrong公理导出的充分必要条件是Y X+F,说明：如果X+F中含有Y，则F逻辑蕴含XY,也是用于判定XY能否由F根据Armstrong公理导出的算法,算法：求属性集X关于函数依赖集F的闭包X+F,例2,练习,假设关系模式为R(A,B,C,D),F=AB,B C,B D，求蕴含于给定函数依赖的所有非平凡函数依赖。求解方法：求所有属性组合的闭包，从中找出新的非平凡依赖
23、。如：,A+=ABCD,B+=BCD,C+=C,D+=D，则有新的非平凡依赖为A C,A D2)两个属性的排列组合，8种新的：AB C,AB D,AC B,AC D,AD B,AD C,BC D,BD C3）三个属性的排列组合，2种新的：ABC D,ABD C4）ABCD+=ABCD，无,定义,如果G+=F+，就说函数依赖集F覆盖G,或F与G等价引理3：,用于判定F与G是否等价的算法,定义,如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，或称最小依赖集性质：函数依赖集F的最小函数依赖集不一定唯一，它与求解的次序有关定理：每一个函数依赖集F均等价于一个最小依赖集Fm,这样，R可以用R来
24、取代,算法：求函数依赖F的最小依赖集F,例子,1）考查AB，去掉它，计算A+=AC，不包含B，不能去掉2）考查 B A，去掉它，计算BB C A，包含A，可去掉它3）考查 B C，去掉它，计算BB，不包含C，不能去掉4）考查A C，去掉它，计算BA B C，包含C，可去掉它5）考查 C A，去掉它，计算CC，不包含A，不能去掉,1 2 3 4 5,其它例子,5.4 模式的分解,分解的目的解决冗余和异常，提高范式等级分解的概念用原关系模式的若干个投影构成新的关系模式，即,关系模式分解应满足的特性,无损连接性(Lossless join)保持函数依赖性(Preserve dependency)相互
25、独立性分解后的关系模式中，当修改某一个关系数据时，不会影响其他关系,例子分析,设S-C-M（学号，班级，班主任）F=学号班级，班级班主任，学号班主任,存在传递依赖，为2NF,有三种分解：,该关系属于几范式？,范式？,3NF,三种特性?,例子,教材P188，例4,算法：检验一个分解是否具有无损连接性,初始表：,最后结果：,R1,R2,R3,R1,R2,R3,1,2,2,例子：判断无损连接性,初始表：,最后结果：,R1,R2,R3,R1,R2,R3,1,2,2,简易方法：只画关注数据,例子,R(A,B,C),F=AB,C B分解1=(A,B)AB,(A,C)分解2=(A,B)AB,(B,C)CB分
26、析两种分解的无损连接性？分解1只具有无损连接性,分解2不具有无损连接性,AB,AC,a2,AB,BC,算法：检验一个分解是否具有保持函数依赖性,例子,R(A,B,C),F=AB,C B分解1=(A,B)AB,(A,C)分解2=(A,B)AB),(B,C)C B分析两种分解的依赖保持性？分解1：只有AB，显然，分解1不具有依赖保持性分解2：保留了所有函数依赖，具有依赖保持性,简单练习：判定无损连接性和函数依赖性,设S-C-M（S学号，C班级，M班主任）F=S学号C班级，C班级M班主任，S学号M班主任,几个命题,一个无损连接的分解不一定具有依赖保持性，反之亦然若要求模式分解保持函数依赖，则模式分离
27、总能达到3NF，但不一定能达到BCNF若要求分解既保持函数依赖，又具有无损连接性，则模式分离可以达到3NF，但不一定能达到BCNF若要求分解具有无损连接性，则模式分离一定可以达到4NF,求解关系模式的候选码,属性分类L类：只出现在函数依赖的左边的属性R类：只出现在函数依赖的右边的属性N类：在函数依赖的两边均未出现的属性LR类：出现在函数依赖的两边的属性函数依赖图FDG用有向图表示的函数依赖，如,快速求解候选码的充分条件,对于给定的关系模式R及其函数依赖集F如果X是L或N类属性，则X必为R的任一候选码的成员如果X是R类属性，则X必不在任何候选码中如果X是L和N类组成的属性组，且X+包含了全部属性
28、，则X是R的唯一候选码,算法：对左边为单属性的函数依赖集求所有候选码,(1)求F的最小依赖集F(2)作出函数依赖图FDG(3)从FDG图中找出无入边的属性集X(4)察看FDG图中有无回路，若无，则输出X并结 束,否则进行下一步(5)从各独立回路中各取一个结点的属性与X组成一个候选码，重复取得所有可能的组合，即R的全部候选码,单属性下求解候选码的充要条件,算法：对左边为多属性的函数依赖集求所有候选码,(1)将R所有属性分为L,R,N,LR四类，并令X代表L,N两类，令Y代表LR类(2)求X+，若X+包含R全部属性，则X即为R的唯一候选码，结束，否则转下一步(3)在Y中取一属性A，求(XA)+,若它包含R的全部属性，则转下一步，否则换一个属性重试，直至试完所有Y中的属性(4)若已找出所有候选码，则结束，否则在Y中依次取两个、三个、，求它们的属性闭包，直至其闭包包含R的全部属性,多属性下求解候选码的充分条件,算法：求R的保持函数依赖的3NF分解,算法：求R的无损连接且保持函数依赖的3NF分解,作业,P196 习题1，2，9，12思考：10，11，自由选做,
