关系数据理论.ppt

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

1、关系数据理论 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望要点v关系规范化理论研究背景v数据依赖v规范化(Normalization)理论u1NF、2NF、3NF、BCNF、4NF等范式u关系模式规范化的必要性及方法5.1 问题的提出v问题提出：u针对一个具体问题，如何构造合适的合适的(更好更好的的)数据模式，即如何更好地设计数据的逻辑结构？v关系数据理论的研究背景u关系模型建立在严格的数据理论基础上，并可向别的数据模型转换，因此常以关系模型为背景来讨论这个问题

2、背景知识v数据模式(schema)u数据库中全体数据的逻辑结构和特征描述，如数据记录的构成，数据间的联系，安全性、完整性要求等。常以某一种数据模型为基础v关系模型的形式化定义：R(U,D,dom,F)，本章简化为R(U,F)v关系模型R的一个关系r：U上的一个关系r满足F属性组一组数据依赖一个例子：学生-课程-成绩管理v客观存在的事实u一个系有若干学生，但一个学生只属于一个系；一个系只有一名负责人；一个学生可以选修多门课程，每门课程有若干学生选修；每个学生学习每一门课程有一个成绩v设计如下单个模式u属性组U=学号SNO,系名SDEPT,系负责人MN,课程名CNAME,成绩Gu数据依赖v该模式存

3、在的问题？怎么改善这个模式？问题和改进v该模式存在的问题u插入异常：一个系无学生或未安排课程时，无法存入系与负责人删除异常：删除一个系的所有学生信息时，系与负责人也丢失u冗余太大：负责人姓名重复存入u更新异常：当某系负责人更换时，须更新该系所有学生信息中的信息，更新不完全时，易造成数据不一致v原因：数据依赖存在一些不合适的性质，需寻找更好的模式，如S(SNO,SDEPT,)SG(SNO,CNAME,G,)DEPT(SDEPT,MN,)SNO CNAMEGSDEPTMN5.2 规范化v意图u讨论一个关系属性间不同的依赖情况u讨论如何根据属性间依赖关系来判定关系是否有某些不合适的性质v数据依赖概念

4、u反映客观世界数据间的相互关联u通过一个关系中属性间值的相等与否来体现v两种重要的数据依赖u函数依赖(Functional Dependency,FD)u多值依赖(Multivalued Dependency,MVD)5.2.1 函数依赖v定义1u设R(U)是属性集U上的关系模式。X,Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定函数确定Y或或Y函数依赖于函数依赖于X，记作v术语和记号u ，但 ，则称 是非平凡的函数依赖u ，但 ，则称 是平凡的函数依赖u若 ，则X叫做决定因素u若 ，则记作u若Y不函数依赖于X

5、，则记作对函数依赖的说明v换句话说：任何时候若某一关系中的两个元组中的X属性组的值相等，则元组中对应的属性组Y的值也相等，类似于函数概念，Y=f(X)v需要指出的是：关系R中，如果属性组X是一个候选码或码，则属性组Y一定函数依赖于X（这与候选码的定义一致）v事实上：如果关系R上有函数依赖XY，而属性X不是一个候选码，则R中可能存在一些数据冗余u例如：R(Sno,Sdept,MN,Cname,Grade)中有函数依赖Sdept-MN，而Sdept并不是候选码，表中数据有大量冗余出现函数依赖v定义2u在R(U)中，如果 ，并且对于X的任何一个真子集X,都有 ，则称Y对对X完全函完全函数依赖数依赖，

6、记作u若 ，但Y不完全函数依赖于X，则称Y对对X部分函数依赖部分函数依赖，记作v定义3u在R(U)中，如果 ，()，u则称Z对对X传递函数依赖传递函数依赖，记作FP传递5.2.2 码用函数依赖的概念来定义码v定义4 u设K为R(U,F)中的属性或属性组合，若 则K为R的候选码候选码(Candidate Key)。u若候选码多于一个，则选定其中的一个为主码主码(Primary Key)v相关术语u包含在任何一个候选码中的属性，叫做主属性主属性u不包含在任何码中的属性，叫做非主属性非主属性u整个属性组是码，称为全码全码F码v定义5u关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则

7、称X是R的外部码(Foreign Key)，也称为外码外码 主码与外码提供了一个表示关系间联系的手段SC(Sno,Cno,Grade)Studen(Sno,Sname,.)Course(Cno,Cname,.)5.2.3 范式v范式：符合某种级别(条件、要求)的关系模式v范式种类u1NF,2NF,3NF,BCNF,4NF,5NFu按级别(条件、要求)由低到高：1NF 2NF 3NF BCNF 4NF 5NFv通常称某一关系模式R为第几范式，记作R xNF1NF(First Normal Form)v定义：关系R中每个分量都是不可分割的数据项，则R 1NFv说明：1NF是关系模式的基本要求v举例

8、：关系模式S-L-C(学号SNO,系SDEPT,住处SLOC,课程CNO,成绩G)是1NF5.2.4 2NFv定义：若R 1NF,且每个非主属性完全依赖于码，则R 2NFv说明：不存在非主属性部分依赖于码的关系为2NFv举例：关系模式 S-L-C(SNO,SDEPT,SLOC,CNO,G)u函数依赖图GSNOCNOSDEPTSLOC关系模式S-L-C是不是2NF？不是，因为SDEPT和SLOC部分依赖于码前面的实例是不是2NF？不是2NF可能出现的问题v插入异常u某学生没有选课时，无法插入其系、住处等信息v删除异常u某学生所有的选课信息都删除后，其系、住处等信息也被删除v修改复杂（更新异常）u

9、学生转系时，除了修改其系名外，还需修改其住处信息；另外，若该学生选修了多门课程，则其对应的重复存储的系、住处等信息需一一修改v冗余u同系的所有学生的住处信息重复存储，同一学生选多门课程时，其系、住处信息重复存储解决办法v模式分解u依赖关系分析u上例中的模式分解为下列两个模式，该模式是2NFSC(SNO,CNO,G)(SNO,CNO)GS-L(SNO,SDEPT,SLOC)SNO SDEPT,SNO SLOC,SDEPT SLOCGSNOCNOSDEPTSLOC分解说明v一个1NF，但非2NF的关系总是可以被分解成为一组2NF的关系v规范化过程中通过一组投影运算消除部分依赖，建议作如下分解(第一

10、步分解)u已知关系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为外码u这样，R可以通过R1和R2的自然连接运算得以恢复，即满足分解的无损连接性5.2.5 3NFv定义：若R2NF,且它的任何一个非主属性都不传递依赖于任何候选码，则R 3NFv说明：即不存在非主属性部分依赖和传递依赖于码的关系为3NFv推论：不存在非主属性的模式为3NFv上例中得到的关系模式是2NF SC(SNO,CNO,G);S-L(SNO,SDEPT,SLOC);S-L中存在传递传递依赖，故该模式不

11、是3NFSNOSDEPTSLOC可能问题？如何改造？不是3NF可能存在的问题v插入异常u只有当知道某学生的系时才能插入其住处信息v删除异常u当删除某系对应的所有学生时，有关该系学生住处的信息也被删除掉了v修改异常u一个系及其住处信息重复出现，只更新一个元组中对应的系及其住处时可能导致数据不一致v冗余u同系学生的住处重复存储解决方法v继续模式分解u如上例中的模式可分解为3NFSC(SNO,CNO,G);(SNO,CNO)G S-D(SNO,SDEPT);SNO SDEPT D-L(SDEPT,SLOC);SDEPT SLOCSNOSDEPTSLOCSDEPTGSNOCNO分解说明v一个2NF，但

12、非3NF的关系总是可以被分解成为一组3NF的关系v规范化过程中通过一组投影运算消除传递依赖，建议作如下分解(第二步分解)u已知关系R(A,B,C),A为主码(A-B,A-C)，且B-C,则将R分解成为两个投影:R1(B,C),B为主码R2(A,B),A为主码，B为外码u这样，R可以通过R1和R2的自然连接运算得以恢复，分解满足分解的无损连接性3NF的进一步说明v在不考虑主属性对码的部分依赖和传递依赖时，可以认为是实现了彻底的分离，已消除了插入异常，删除异常，修改异常，冗余等问题v但是，当关系中存在两个或更多的候选码时，尤其是有几个候选码、且候选码内的属性又有部分复合或交迭时，仅仅满足3NF仍有

13、问题，需要进一步分解成BCNF5.2.6 BCNF(Boyce/Codd Normal Form)v定义：若每一个决定因素都包含(或是)码，则R BCNFv说明uBCNF中所有的依赖都是包含码的依赖u一个BCNF范式必是3NF，但一个3NF范式不一定是BCNF(3NF中可能存在主属性对码的部分和传递依赖)uBCNF是在函数依赖范畴内对关系模式的彻底分离，已消除了插入和删除异常u通常认为BCNF是扩充的第三范式，一般数据库设计达到BCNF已足够实例v例1:SJP(学生S,课程J,名次P)u(S,J)和(J,P)均为候选码u函数依赖为(S,J)P,(J,P)S其中，两个决定因素均包含(是)候选码可

14、见SJP BCNFv例2:STJ(学生S,教师T,课程J)u(S,T)和(S,J)均为候选码u函数依赖为(S,J)T,(S,T)J,T J其中，T为决定因素，但不包含任何一个候选码可见STJ 3NF,但STJ BCNF 例子v前例是3NF,也是BCNFSC(SNO,CNO,G);(SNO,CNO)GS-D(SNO,SDEPT);SNO SDEPTD-L(SDEPT,SLOC);SDEPT SLOCSNOSDEPTSLOCSDEPTGSNOCNO5.2.7 多值依赖v属于BCNF的关系模式是不是很完美了呢？v教材P178例子v存在问题？v如何解决？5.2.8 4NFv4NF就是限制关系模式的属性

15、之间不允许有非平凡且非函数依赖的多值依赖v如果一个关系模式是4NF，必定为BCNFv一个关系模式是BCNF，但不是4NF，依然有不好的性质，可以用投影分解的办法解决v例：WSC(仓库W,保管员S,商品C)u全码(W,S,C)u存在多值依赖WS,WC，WSC 4NF可进一步分解使之满足4NF:WS(W,S),WC(W,C)v4NF是多值依赖范畴内最高程度的规范化5.2.9 规范化理论v规范化u概念：将一个低一级范式的关系模式分解模式分解为若干个高一级范式的关系模式的过程u目的：设计正确、良好的关系模式u基本思想：逐步消除关系模式的数据依赖中不合适的部分，使模式达到一定程度的分离，但又不丢失原模式

16、中的信息u模式分解的实质：投影几个事实v模式分解可以消除冗余，解决更新异常等问题，但也要付出做连接运算等昂贵的代价v需要强调的是：对已知关系模式的范式等级是语义上的，而不仅仅是看某个时刻关系中的数据值，必须考察数据间的依赖v即便是知道了数据依赖，也不能证明一个关系是否3NF。我们只能首先假设这个关系是3NF，而去验证给出的关系中没有违反数据依赖的情形规范化理论v如何辨别一个关系模式的“好坏”？u不存在部分和传递函数依赖等“不好”的性质的模式是“好”模式，否则会出现冗余和插入、删除、更新等异常现象v规范化过程是用于设计好的数据库的有力辅助，但并不是唯一的方法v 最初的设计中尽量做到“概念单一化”

17、，即做到让一个关系描述一个概念、一个实体或实体间的一种联系，这样所设计的关系模式将会接近或达到第三范式，甚至达到BCNF规范化过程小结1NF2NF3NFBCNF4NF消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和传递函数依赖消除多值依赖练习一v设计关于供应商供应零件的数据库，要求达到3NFv最初的设计：R(S#,Sname,City,Status,P#,Pname,Color,Weight,QTY)u主码：(S#,P#)u函数依赖：S#Sname,S#Status,S#City,City Status,P#Pname,P#Color,P#Weight v可见

18、，其中有部分依赖，还有传递依赖。该模式仅为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 练习二设计订货系统的数据库，包括顾客、货物和订货单信息v初模式：

19、顾客(顾客号，收货地址，赊购限额，余额，折扣)货物(货物号，制造厂商，实际存货量，规定的最低存货量，货物描述)订货单(订货单号，顾客号，货物号，订货数量，订货细则，未发数量，订货日期，经办人)问题分析：v 顾客模式中，顾客号不能唯一决定收货地址v 货物模式中，货物描述部分依赖于码v 订货单模式中，未发数量将随发货过程更新，而其他信息相对静态；v 订货细则有多条 改进模式q顾客及其地址(顾客号，收货地址)q顾客及其余额(顾客号，赊购限额，余额，折扣)q货物及其厂商(货物号，制造厂商，实际存货量，规定的最低存货量)q货物及其描述-2(货物号，货物描述)q订货单(订货单号，顾客号，货物号，订货数量，

20、订货日期，经办人)q发货(订货单号，未发货量)q发货(订货单号，订货细则)练习三欲设计移动公司手机信息管理系统，用于管理：1、手机销售信息（由营业厅售给用户）2、手机用户档案信息（用户名，证件号码等）3、手机通话信息（每一次通话的详细情况）4、手机话费信息（每月的话费组成）在此基础上实现常用的查询，如：1、每月手机的销售情况 2、每种机型的销售情况 3、每个营业厅的手机销售情况 4、根据手机号码查询其用户信息 5、根据手机号码查询某时间段内的通话情况 6、每月手机话费收入 7、欠费用户查询试设计合适的数据库，并在此基础上用SQL实现所有的查询设计结果q营业厅(营业厅编号，地址，负责人)q销售记

21、录(营业厅编号，机型，数量，日期，经办人)q手机销售单价(机型，单价)q手机用户信息(手机号码，用户名，住址，证件号码)q手机通话记录(手机号码，被叫号码，日期，起始时刻，通话时长)q手机话费信息(手机号码，话费，漫游费，短信费)q话费缴费信息(手机号码，缴费日期，金额，缴费营业厅)定义回顾：函数依赖v设R(U)是属性集U上的关系模式，X,Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定函数确定Y或或Y函数依赖于函数依赖于X，记作XY5.3 Armstrong公理系统v定义：逻辑蕴涵u对于满足一组函数依赖F的关系

22、模式R，其任何一个关系r，若函数依赖XY都成立，则称F逻辑蕴含逻辑蕴含X YvArmstrong公理系统是函数依赖的一个有效而完备的公理系统u可用于从一组函数依赖F求得蕴含(导出)的函数依赖u可用于求得关系模式的码Armstrong公理系统vArmstrong公理系统uA1自反律：uA2增广律：uA3传递律：vArmstrong公理系统的推理规则u合并规则:u伪传递规则:u分解规则:v引理5.1(由合并规则和分解规则可得)Armstrong公理系统v定义：闭包u在关系模式R中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为F+vArmstrong公理系统是有效的、完备的uArmstrong公理

23、系统的有效性t由F出发根据Armstrong公理导出的每一个函数依赖一定在F+中uArmstrong公理系统的完备性tF+中的每一个函数依赖，必定可以由F出发根据Armstrong公理导出或导出怎样计算F+?怎样判断一个函数依赖一定在闭包中？定义v设F为属性集U上的一组函数依赖，XU，X+FAX A能由Armstrong公理导出,X+F称为属性集X关于函数依赖F的闭包v引理2：设F为属性集U上的一组函数依赖，X,YU，X Y能根据Armstrong公理导出的充分必要条件是Y X+F说明：如果X+F中含有Y，则F逻辑蕴含XY 也是用于判定XY能否由F根据Armstrong公理导出的算法算法：求属

24、性集X关于函数依赖集F的闭包X+F例2练习v假设关系模式为R(A,B,C,D),F=AB,B C,B D，求蕴含于给定函数依赖的所有非平凡函数依赖。v求解方法：求所有属性组合的闭包，从中找出新的非平凡依赖。如：1)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，无定义v如果G+=F+，就说函数依赖集F覆盖G,或F与G等价v引理3：用于判定F与G是否等价的算法定义v如果

25、函数依赖集F满足下列条件，则称F为一个极小函数依赖集，或称最小依赖集v性质：函数依赖集F的最小函数依赖集不一定唯一，它与求解的次序有关v定理：每一个函数依赖集每一个函数依赖集F均等价于一个最小依赖集均等价于一个最小依赖集Fm这样，R可以用R来取代算法：求函数依赖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

26、模式的分解v分解的目的u解决冗余和异常，提高范式等级v分解的概念u用原关系模式的若干个投影构成新的关系模式，即关系模式分解应满足的特性v无损连接性(Lossless join)v保持函数依赖性(Preserve dependency)v相互独立性u分解后的关系模式中，当修改某一个关系数据时，不会影响其他关系例子分析v设S-C-M（学号，班级，班主任）F=学号班级，班级班主任，学号班主任存在传递依赖，为2NF有三种分解：该关系属于几范式？范式？3NF三种特性?例子v教材P188，例4算法：检验一个分解是否具有无损连接性ABCDEa1a2a3b14b15b21b22a3a4b25b31b32b33

27、a4a5ABCDEa1a2a3a4a5b21b22a3a4a5b31b32b33a4a5初始表：最后结果：R1R2R3R1R2R3122例子：判断无损连接性ABCDEa1a2a3a3a4a4a5ABCDEa1a2a3a4a5a3a4a5a4a5初始表：最后结果：R1R2R3R1R2R3122简易方法：只画关注数据例子vR(A,B,C),F=AB,C Bu分解1=(A,B)AB,(A,C)u分解2=(A,B)AB,(B,C)CBv分析两种分解的无损连接性？u分解1只具有无损连接性,分解2不具有无损连接性ABCa1a2a1a3ABACa2ABCa1a2a2a3ABBC算法：检验一个分解是否具有保持

28、函数依赖性例子vR(A,B,C),F=AB,C Bu分解1=(A,B)AB,(A,C)u分解2=(A,B)AB),(B,C)C Bv分析两种分解的依赖保持性？u分解1：只有AB，显然，分解1不具有依赖保持性u分解2：保留了所有函数依赖，具有依赖保持性简单练习：判定无损连接性和函数依赖性v设S-C-M（S学号，C班级，M班主任）F=S学号C班级，C班级M班主任，S学号M班主任 几个命题v一个无损连接的分解不一定具有依赖保持性，反之亦然v若要求模式分解保持函数依赖，则模式分离总能达到3NF，但不一定能达到BCNFv若要求分解既保持函数依赖，又具有无损连接性，则模式分离可以达到3NF，但不一定能达到

29、BCNFv若要求分解具有无损连接性，则模式分离一定可以达到4NF求解关系模式的候选码v属性分类uL类：只出现在函数依赖的左边的属性uR类：只出现在函数依赖的右边的属性uN类：在函数依赖的两边均未出现的属性uLR类：出现在函数依赖的两边的属性v函数依赖图FDGu用有向图表示的函数依赖，如XY即X Y快速求解候选码的充分条件v对于给定的关系模式R及其函数依赖集Fu如果X是L或N类属性，则X必为R的任一候选码的成员u如果X是R类属性，则X必不在任何候选码中u如果X是L和N类组成的属性组，且X+包含了全部属性，则X是R的唯一候选码算法：对左边为单属性的函数依赖集求所有候选码(1)求F的最小依赖集F(2

30、)作出函数依赖图FDG(3)从FDG图中找出无入边的属性集X(4)察看FDG图中有无回路，若无，则输出X并结 束,否则进行下一步(5)从各独立回路中各取一个结点的属性与X组成一个候选码，重复取得所有可能的组合，即R的全部候选码单属性下求解候选码的充要条件ZWYXSDIBOQIBOQSD算法：对左边为多属性的函数依赖集求所有候选码(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分解作业vP196 习题1，2，9，12v思考：10，11，自由选做