《关系数据理论》PPT课件.ppt

关系数据理论,要点,关系规范化理论研究背景 数据依赖 规范化(Normalization)理论 1NF、2NF、3NF、BCNF、4NF等范式 关系模式规范化的必要性及方法,5.1 问题的提出,问题提出： 针对一个具体问题，如何构造合适的(更好的)数据模式，即如何更好地设计数据的逻辑结构？ 关系数据理论的研究背景 关系模型建立在严格的数据理论基础上，并可向别的数据模型转换，因此常以关系模型为背景来讨论这个问题,背景知识,数据模式(schema) 数据库中全体数据的逻辑结构和特征描述，如数据记录的构成，数据间的联系，安全性、完整性要求等。常以某一种数据模型为基础 关系模型的形式化定义：R(U,D,dom,F)，本章简化为R(U, F) 关系模型R的一个关系r：U上的一个关系r满足F,属性组,一组数据依赖,一个例子：学生-课程-成绩管理,客观存在的事实 一个系有若干学生，但一个学生只属于一个系；一个系只有一名负责人；一个学生可以选修多门课程，每门课程有若干学生选修；每个学生学习每一门课程有一个成绩 设计如下单个模式 属性组U = 学号SNO,系名SDEPT,系负责人MN,课程名CNAME,成绩G 数据依赖,该模式存在的问题？怎么改善这个模式？,问题和改进,该模式存在的问题 插入异常：一个系无学生或未安排课程时，无法存入系与负责人删除异常：删除一个系的所有学生信息时，系与负责人也丢失 冗余太大：负责人姓名重复存入 更新异常：当某系负责人更换时，须更新该系所有学生信息中的信息，更新不完全时，易造成数据不一致 原因：数据依赖存在一些不合适的性质，需寻找更好的模式，如 S(SNO, SDEPT, ) SG(SNO, CNAME, G, ) DEPT(SDEPT, MN, ),5.2 规范化,意图 讨论一个关系属性间不同的依赖情况 讨论如何根据属性间依赖关系来判定关系是否有某些不合适的性质 数据依赖概念 反映客观世界数据间的相互关联 通过一个关系中属性间值的相等与否来体现 两种重要的数据依赖 函数依赖(Functional Dependency, FD) 多值依赖(Multivalued Dependency, MVD),5.2.1 函数依赖,定义1 设R(U)是属性集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不是一个候选码，则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)。 若候选码多于一个，则选定其中的一个为主码(Primary 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 5NF 通常称某一关系模式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？,不是2NF可能出现的问题,插入异常 某学生没有选课时，无法插入其系、住处等信息 删除异常 某学生所有的选课信息都删除后，其系、住处等信息也被删除 修改复杂（更新异常） 学生转系时，除了修改其系名外，还需修改其住处信息；另外，若该学生选修了多门课程，则其对应的重复存储的系、住处等信息需一一修改 冗余 同系的所有学生的住处信息重复存储，同一学生选多门课程时，其系、住处信息重复存储,解决办法,模式分解 依赖关系分析 上例中的模式分解为下列两个模式，该模式是2NF SC(SNO, CNO, G) (SNO, CNO)G S-L(SNO, SDEPT, SLOC) SNO SDEPT, SNO SLOC, SDEPT SLOC,分解说明,一个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为外码 这样，R可以通过R1和R2的自然连接运算得以恢复，即满足分解的无损连接性,5.2.5 3NF,定义：若R2NF, 且它的任何一个非主属性都不传递依赖于任何候选码，则R 3NF 说明：即不存在非主属性部分依赖和传递依赖于码的关系为3NF 推论：不存在非主属性的模式为3NF 上例中得到的关系模式是2NF SC(SNO, CNO, G); S-L(SNO, SDEPT, SLOC);,S-L中存在传递传递依赖，故该模式不是3NF,可能问题？ 如何改造？,不是3NF可能存在的问题,插入异常 只有当知道某学生的系时才能插入其住处信息 删除异常 当删除某系对应的所有学生时，有关该系学生住处的信息也被删除掉了 修改异常 一个系及其住处信息重复出现，只更新一个元组中对应的系及其住处时可能导致数据不一致 冗余 同系学生的住处重复存储,解决方法,继续模式分解 如上例中的模式可分解为3NF SC(SNO, CNO, G); (SNO, CNO) G S-D(SNO, SDEPT); SNO SDEPT D-L(SDEPT, SLOC); SDEPT SLOC,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的进一步说明,在不考虑主属性对码的部分依赖和传递依赖时，可以认为是实现了彻底的分离，已消除了插入异常，删除异常，修改异常，冗余等问题 但是，当关系中存在两个或更多的候选码时，尤其是有几个候选码、且候选码内的属性又有部分复合或交迭时，仅仅满足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)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, 也是BCNF SC(SNO, CNO, G); (SNO, CNO) G S-D(SNO, SDEPT); SNO SDEPT D-L(SDEPT, SLOC); SDEPT SLOC,SNO,SDEPT,SLOC,SDEPT,5.2.7 多值依赖,属于BCNF的关系模式是不是很完美了呢？ 教材P178例子 存在问题？ 如何解决？,5.2.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 规范化理论,规范化 概念：将一个低一级范式的关系模式分解为若干个高一级范式的关系模式的过程 目的：设计正确、良好的关系模式 基本思想：逐步消除关系模式的数据依赖中不合适的部分，使模式达到一定程度的分离，但又不丢失原模式中的信息 模式分解的实质：投影,几个事实,模式分解可以消除冗余，解决更新异常等问题，但也要付出做连接运算等昂贵的代价 需要强调的是：对已知关系模式的范式等级是语义上的，而不仅仅是看某个时刻关系中的数据值，必须考察数据间的依赖 即便是知道了数据依赖，也不能证明一个关系是否3NF。我们只能首先假设这个关系是3NF，而去验证给出的关系中没有违反数据依赖的情形,规范化理论,如何辨别一个关系模式的“好坏”？ 不存在部分和传递函数依赖等“不好”的性质的模式是“好”模式，否则会出现冗余和插入、删除、更新等异常现象 规范化过程是用于设计好的数据库的有力辅助，但并不是唯一的方法 最初的设计中尽量做到“概念单一化”，即做到让一个关系描述一个概念、一个实体或实体间的一种联系，这样所设计的关系模式将会接近或达到第三范式，甚至达到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#)为码 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,练习二,设计订货系统的数据库，包括顾客、货物和订货单信息 初模式： 顾客(顾客号， 收货地址，赊购限额，余额，折扣) 货物(货物号，制造厂商，实际存货量，规定的最低存货量，货物描述) 订货单(订货单号，顾客号，货物号，订货数量，订货细则， 未发数量，订货日期，经办人),问题分析： 顾客模式中，顾客号不能唯一决定收货地址 货物模式中，货物描述部分依赖于码 订货单模式中，未发数量将随发货过程更新，而其他信息相对静态； 订货细则有多条,改进模式,顾客及其地址(顾客号， 收货地址) 顾客及其余额(顾客号，赊购限额，余额，折扣) 货物及其厂商(货物号，制造厂商，实际存货量，规定的最低存货量) 货物及其描述-2(货物号，货物描述) 订货单(订货单号，顾客号，货物号，订货数量，订货日期，经办人) 发货(订货单号，未发货量) 发货(订货单号，订货细则),练习三,欲设计移动公司手机信息管理系统，用于管理： 1、手机销售信息（由营业厅售给用户） 2、手机用户档案信息（用户名，证件号码等） 3、手机通话信息（每一次通话的详细情况） 4、手机话费信息（每月的话费组成） 在此基础上实现常用的查询，如： 1、每月手机的销售情况 2、每种机型的销售情况 3、每个营业厅的手机销售情况 4、根据手机号码查询其用户信息 5、根据手机号码查询某时间段内的通话情况 6、每月手机话费收入 7、欠费用户查询 试设计合适的数据库，并在此基础上用SQL实现所有的查询,设计结果,营业厅(营业厅编号，地址，负责人) 销售记录(营业厅编号，机型，数量，日期，经办人) 手机销售单价(机型，单价) 手机用户信息(手机号码，用户名，住址，证件号码) 手机通话记录(手机号码，被叫号码，日期，起始时刻，通话时长) 手机话费信息(手机号码，话费，漫游费，短信费) 话费缴费信息(手机号码，缴费日期，金额，缴费营业厅),定义回顾：函数依赖,设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 Y Armstrong公理系统是函数依赖的一个有效而完备的公理系统 可用于从一组函数依赖F求得蕴含(导出)的函数依赖 可用于求得关系模式的码,Armstrong公理系统,Armstrong公理系统 A1自反律： A2增广律： A3传递律： Armstrong公理系统的推理规则 合并规则: 伪传递规则: 分解规则: 引理5.1 (由合并规则和分解规则可得),Armstrong公理系统,定义：闭包 在关系模式R中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为F+ Armstrong公理系统是有效的、完备的 Armstrong公理系统的有效性 由F出发根据Armstrong公理导出的每一个函数依赖一定在F+中 Armstrong公理系统的完备性 F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理导出,或导出,怎样计算F+? 怎样判断一个函数依赖一定在闭包中？,定义,设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，求蕴含于给定函数依赖的所有非平凡函数依赖。 求解方法：求所有属性组合的闭包，从中找出新的非平凡依赖。如：,A+=ABCD,B+=BCD,C+=C, D+=D，则有新的非平凡依赖为A C, A D 2) 两个属性的排列组合，8种新的： AB C, AB D, AC B, AC D, AD B, AD C, BC D, BD C 3）三个属性的排列组合，2种新的：ABC D, ABD C 4）ABCD+=ABCD，无,定义,如果G+=F+，就说函数依赖集F覆盖G,或F与G等价 引理3：,用于判定F与G是否等价的算法,定义,如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，或称最小依赖集 性质：函数依赖集F的最小函数依赖集不一定唯一，它与求解的次序有关 定理：每一个函数依赖集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 模式的分解,分解的目的 解决冗余和异常，提高范式等级 分解的概念 用原关系模式的若干个投影构成新的关系模式，即,关系模式分解应满足的特性,无损连接性(Lossless join) 保持函数依赖性(Preserve dependency) 相互独立性 分解后的关系模式中，当修改某一个关系数据时，不会影响其他关系,例子分析,设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 分析两种分解的无损连接性？ 分解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-