[理学]第六章 关系数据理论.ppt

第六章 关系数据理论,数据库系统概论 华中科技大学能源与动力工程学院,设计任何一个数据库应用系统，现实世界 E-R模型关系模型,都会遇到如何构造合适的数据模式，即逻辑结构的问题； 对于初步的关系模式，可能存在这样或那样的问题（如插入异常、删除异常等），需要利用关系数据库设计理论进行规范化，以逐步消除存在的问题，从而得到一定规范程度的关系模式，这就是本章要讲的内容； 本章将阐述关系数据库中最深的一些特性函数依赖、多值依赖和连接依赖，以及由此引出的诸多异常，如插入异常、更新异常、删除异常及冗余等，对于出现的问题，通过理论引入，对关系模式的规范化进行系统阐述。,一、概念回顾,关系：描述实体、属性、实体间的联系。从形式上看，它是一张二维表； 关系模式：对关系的描述；关系数据库中，关系模式是型，关系是值； 关系数据库：基于关系模型的数据库； 关系数据库的模式：对关系数据库的描述，关系数据库的型也称为关系数据库模式。,关系模式的形式化定义 关系模式由五部分组成，即它是一个五元组：R(U, D, DOM, F) R： 关系名； U： 组成该关系的属性名集合一组属性U； D： 属性组U中属性所来自的域； DOM：属性向域的映象集合 F： 属性间数据的依赖关系集合,二、关系模式中可能存在的异常,例：建立一个描述学校教务的数据库：学生的学号（Sno）、所在系（Sdept）、系主任姓名（Mname）、课程号（Cno）成绩（Grade）； 假设用单一的关系模式 Student 来表示，则该关系模式的属性集合U Sno, Sdept, Mname, Cname, Grade 现实世界已知事实的语义： 一个系有若干学生， 一个学生只属于一个系； 一个系只有一名系主任； 一个学生可以选修多门课程， 每门课程有多名学生选修； 每个学生所学的每门课程都有一个成绩。,Student表,数据冗余 如果一个系有多名学生或该学生选修了多门课程，则系名称和系主任姓名就要出现多次，浪费了存储设备； 操作异常 由于数据的冗余，在对数据操作时会引起各种异常： 更新异常：如果某系更换系主任或更换系名后，系统必须修改与该系学生有关的每一个元组；若有一个元组中的数据未更改，就会造成这个系主任姓名不一致现象。 数据冗余 ，更新数据时，维护数据完整性代价大,操作异常 插入异常：如果一个系刚成立，无学生，或者虽然有学生但尚未安排课程，那么就无法把这个系及其负责人的信息加入数据库。 应该插入而未被插入 删除异常：如果某个系的学生全部毕业了， 我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。 不该删除的数据不得不删,结论： Student关系模式不是一个好的模式。 “好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。 如果将关系模式Student划分为三个关系模式S(Sno,Sdept ) SC(Sno,Cno,Grade ) Dept(Sdept, Mname ) 可基本解决以上问题，但分解后是否是最佳的模式，也不是绝对的。,三、关系模式中存在异常的原因,事实上，异常现象产生的根源，就是由于关系模式中属性间存在着复杂的依赖关系。如学生学号和学生姓名、学生学号和院系名称、院系名称和院系系领导之间都存在着依赖关系，这种依赖都称为数据依赖； 数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系。 数据冗余的产生和数据依赖有着密切的关系；,数据依赖 是通过一个关系内部属性与属性之间的一种约束关系； 是语义的体现； 是现实世界属性间相互联系的抽象； 是数据内在的性质； 数据依赖的类型 函数依赖（Functional Dependency，简记为FD） 多值依赖（Multivalued Dependency，简记为MVD） 其他,函数依赖 函数依赖极普遍地存在现实生活中，如描述一个学生的关系： 学生（学号、姓名、系名、系领导），如果语义是：一个学号只对应的学生，一个学生只在一个系学习；那么 学号姓名；学号系名；系名系领导 类似于 Y = F(x) 函数，变量x确定后，相应y的值也确定了； 可写为：name=f（sno）,dept=f（sno）,mname=f（sdept） 可称为：name和dept函数依赖于sno，mname函数依赖于dept；,对于关系模式StudentSno, Sdept, Mname, Cno, Grade 由语义可得出一组函数依赖： FSnoSdept, SdeptMname, (Sno, cno)Grade ,如何构造一个好的关系模式呢？ 消除数据冗余，更新异常，插入异常和删除异常的关系模式 如何改造关系模式？ 如何把一个不好的关系模式分解改造为一个好的关系模式，分析一个关系模式有哪些数据依赖，如何消除那些不合适的数据依赖，这就是关系数据库设计过程中要讨论的规范化理论问题。,四、关系模式的规范化,关系规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。 函数依赖 其他相关定义（候选码） 关系模式的范式,1、函数依赖,函数依赖定义 设R(U)是属性集U上的关系模式，X,Y是U的子集。若对于R(U)的任意两个元组t1和t2，如果t1X= t2 X,则t1Y= t2 Y ，那么称X函数确定Y或Y函数依赖X，记作 XY 。 不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等 任意：关系模式R中的所有关系都要满足约束条件 在X上：取值唯一 所谓函数依赖是指一个或一组属性的值可以决定其它属性的值。函数依赖正如一个函数 y = f(x) ，x的值给定后，y的值也就唯一地确定了。,对于关系模式R ，U为属性集合，XY为其属性子集，根据函数依赖定义和实体间联系的定义，可得出如下结论： 若X和Y是1：1的联系，则存在函数依赖XY 和Y X； 若X和Y是1：n的联系，则存在函数依赖Y X； 若X和Y是m：n的联系，则XY之间不存在函数依赖关系。 以关系模式student为例 系与系主任是 1：1，故有sdept Mname和Mnamesdept； 系与学生是 1： n，故有sno sdept 学生与课程是m ：n，sno和cno不存在函数依赖,例: S (Sno, Sname, Ssex, Sage, Sdept) 假设学生姓名不允许重名，则有: Sno Ssex，Sno Sage , Sno Sdept， Sno Sname, Sname Ssex， Sname Sage Sname Sdept 但Ssex Sage 备注： 1）若XY，并且YX, 则记为XY。 2）若Y不函数依赖于X, 则记为XY。,函数依赖说明 函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。 例如“姓名年龄”这个函数依赖只有在不允许有同名人时成立。 例如，如果允许一个职工只有一个电话号码，那么，职工号确定了，则其电话号码也就随之确定了。 设计者可以对现实世界做强制规定； 关系模式的所有关系实例都要满足约束条件。,函数依赖分类及其定义 平凡函数依赖（Trivial FD） 非平凡函数依赖（Nontrivial FD） 完全函数依赖（Full FD） 部分函数依赖（Partial FD） 传递函数依赖（Transitive FD）,1）平凡函数依赖与非平凡函数依赖,在关系模式R(U)中，对于U的子集X和Y： 如果XY，但Y X，则称XY是非平凡的函数依赖； 如果XY，但Y X, 则称XY是平凡的函数依赖； 若XY，则X称为这个函数依赖的决定属性组，也称为决定因素（Determinant）。 备注：对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，若不特别声明， 我们总是讨论非平凡函数依赖。,例：在关系Student(Sno, Cno, Grade)中 (Sno, Cno) Grade，但Grade （Cno，Sno） (Sno, Cno) Sno，但Sno (Sno, Cno) 非平凡函数依赖： (Sno, Cno) Grade 平凡函数依赖： (Sno, Cno) Sno (Sno, Cno) Cno,2）完全函数依赖与部分函数依赖,定义6.2 在R(U)中， 如果XY，并且对于X的任何一个真子集X，都有X Y, 则称Y对X完全函数依赖，记作 X FY; 若XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作X PY。,例: 在关系SC(Sno, Cno, Grade)中 由于： (Sno, Cno) Grade ，Sno Grade，Cno Grade 因此：(Sno, Cno) Grade（完全函数依赖） 由于： (Sno, Cno) Sdept ，Sno Sdept 故： (Sno, Cno) P Sdept （部分函数依赖）,3）传递函数依赖,定义6.3 在R(U)中，如果XY (Y X) ，YX，YZ， 则称Z对X传递函数依赖。记为：X Z； 若上述定义中有YX，则XY ，实际上为XZ，是直接函数依赖而不是传递函数依赖。,传递,例: 在关系Student(Sno, Sdept, Mname , cno , Grade)中，有 Sno Sdept， Sdept Sno ，（非平凡函数依赖） Sdept sno，Sdept Mname 则称：Mname传递函数依赖于Sno，记作Sno Mname,传递,例：模式R（Sno,Sname,Sdept,Mname,Cno, Cname, Grade ),根据其语义，有如下函数依赖关系： 语义1：每个学生只会有一个学号； SnoSname 语义2：系与学生是一对多的关系；SnoSdept 语义3：系与系主任是一对一的关系； SdeptMname 语义4：每门课程只有一个课程号； CnoCname 语义5：每个学生学习每门课程有一个成绩；（Sno，Cno）FGrade 可推出： Sno 传递 Mname 省略部分函数依赖：如（Sno，Cno）PSname等,关系模式相关定义 关系模式规范化 1NF 2NF 3NF BCNF 4NF,一、关系模式相关定义,定义6.4：设K为R（U,F）中的属性或属性组合。若K F U， 则K称为R的侯选码（Candidate Key）；若候选码多于一个，则选定其中的一个做为主码（Primary Key）；主属性与非主属性 包含在任何一个候选码中的属性 ，称为主属性（Prime attribute） 不包含在任何码中的属性称为非主属性（Nonprime attribute）或非码属性（Non-key attribute） 最简单情况：一个属性是码； 最极端情况：整个属性组是码，也称全码（ALL-KEY）；,定义6.5 ：关系模式 R 中属性或属性组X 并非 R的码，但 X 是另一个关系模式的码，则称 X 是R 的外部码（Foreign key）也称外码； 如在SC（Sno，Cno，Grade）中，Sno不是码，但Sno是关系模式S（Sno，Sdept，Sage）的码，则Sno是关系模式SC的外部码； 主码与外部码一起提供了表示关系间联系的手段。,二、关系模式规范化,关系模式的好与坏，用什么标准衡量？这个标准就是模式的范式（Normal Forms，简记为NF）； 范式是符合某一种级别的关系模式的集合； 范式的种类与数据依赖有着直接的联系，基于FD的范式有1NF、2NF、3NF、BCNF等多种。 某一关系模式R为第n范式，可简记为RnNF。,各范式之间的关系,如果一个关系满足某个范式要求,则它也会满足较其级别低的所有范式的要求。 一个低一级范式的关系模式,通过模式分解(投影运算)可以转化为若干个高一级范式的关系模式的集合,这个过程叫做规范化； 用几个简单的关系去取代原来结构复杂的关系的过程叫做关系规范化。规范化理论是围绕着范式建立的。,关系规范化 目的: 使结构合理,使数据冗余尽量小,减少插入,删除和更新异常； 方法: 将关系模式投影分解成多个关系模式，但关系模式的分解不是唯一的； 要求: 分解后的关系模式集合应当与原关系模式“等价”,既具有无损连接性,又保持函数依赖特性”.,1）第一范式1NF,第一范式(1NF) 当且仅当一个关系R中，每一个分量都是不可再分的数据项时， R1NF ； 要求属性是原子的； 第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库； 但是满足第一范式的关系模式并不一定是一个好的关系模式。,2）第二范式2NF,定义6.6 若R1NF，且每一个非主属性完全函数依赖于码，则R2NF ； 例1：判断关系模式S-L-C(Sno, Sdept, Sloc, Cno, Grade)是否满足2NF，其中Sloc为学生住处，假设每个系的学生住在同一个地方； 第一步：判断S-L-C是否为第一范式； 第二步：确定候选码（sno，cno）； 第二步：确定所有函数依赖有： snosdept，sno sloc，（sno，cno）Psdept，（sno，cno）Psloc ，（sno，cno）FGrade； 得出结论：和2NF定义相违背，故S-L-C不是2NF；,例. 判断关系模式 sc(sno,sname,cno,grade)是否满足2NF； 第一步：判断sc是否为第一范式； 第二步：确定候选码（sno，cno）； 第三步：确定所有函数依赖有： snosname ， （sno,cno） P sname ，（sno,cno） Fgrade； 得出结论：和2NF定义相违背，故sc不是2NF；,一个关系模式不是2NF，就会产生以下问题（S-L-C）： (1) 插入异常：假设Sno95102，SdeptIS，SlocN的学生还未选课，因课程号是主属性，因此该学生的信息无法插入SLC。 (2) 删除异常：假定某个学生本来只选修了3号课程这一门课。现在因其他原因，3号课程也不选修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。 (3) 数据冗余度大：如果一个学生选修了10门课程，那么他的Sdept和Sloc值就要重复存储了10次。,(4) 修改复杂：例如学生转系，在修改此学生元组的Sdept值的同时，还可能需要修改住处（Sloc）。如果这个学生选修了K门课，则必须无遗漏地修改K个元组中全部Sdept、Sloc信息。 原因：非主属性Sdept、 Sloc部分函数依赖于码。 解决方法：S-L-C分解为两个关系模式，以消除这些部分函数依赖 ；SC（Sno， Cno， Grade） S-L（Sno， Sdept， Sloc）,分解成2NF模式集的方法：投影分解法 S-L-C函数依赖图为： SC（Sno， Cno， Grade）和S-L（Sno， Sdept， Sloc）,例2. 分解关系模式 sc(sno,sname,cno,grade)为2NF； 函数依赖图为： 可分解为：,模式S（sno，sname） 模式SC（sno，cno，grade）,采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。 将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。如S-L（Sno， Sdept， Sloc） 。,3）第三范式3NF,定义6.7 如果关系模式R是1NF，且每个非主属性都不传递依赖于R的候选码，那么称R是第三范式（3NF）的模式。 如果R3NF，则R也是2NF。 若 R3NF ，则每一个非主属性既不部分依赖于码也不传递依赖于码；,例：判断2NF关系模式SC（Sno，Cno，Grade）及S-L（Sno， Sdept，Sloc）是否满足3NF； 模式sc的函数依赖有：（sno，cno）grade 模式s-l的函数依赖有： sno sdept，Sdept Sno，sdept sloc 故：模式sc为3NF，模式s-l依然为2NF；,例：判断2NF关系模式S（sno，sname）及SC（Sno，Cno，Grade）是否满足3NF； 模式sc的函数依赖有：sno sname 模式sc的函数依赖有：（sno，cno）grade 故：模式s和sc皆为3NF；,解决方法： 采用投影分解法，把S-L分解为两个关系模式，以消除传递函数依赖： S-D（Sno， Sdept），D-L（Sdept，Sloc） 分解后的关系模式S-D与D-L中不再存在传递依赖 S-D(Sno，Sdept) 3NF，D-L(Sdept， Sloc) 3NF,采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。 将一个2NF关系分解为多个3NF的关系后，仍然不能完全消除关系模式中的各种异常情况和数据冗余。可能表现在主属性对码的部分依赖和传递依赖。,违反3NF的传递依赖的三种情况,4）BCNF,定义6.8 设关系模式R（U，F）1NF，如果对于R的每个函数依赖XY，若Y不属于X，则X必含有候选码，那么RBCNF。 若RBCNF 每一个决定属性集（因素）都包含（候选）码； R中的所有属性（主，非主属性）都完全函数依赖于码； R3NF；,例：判断3NF模式S-D（Sno， Sdept），D-L（Sdept，Sloc）及SC（Sno，Cno，Grade）是否满足BCNF； 判断 每一个决定属性集（因素）都包含（候选）码； 主属性对码是否存在部分依赖和传递依赖； 对于s-d模式，满足，故属于BCNF； 对于d-l模式，满足，故属于BCNF； 对于sc模式，满足，故属于BCNF；,例：判断3NF模式S（sno，sname）及SC（Sno，Cno，Grade）是否满足BCNF； 判断 每一个决定属性集（因素）都包含（候选）码； 主属性对码是否存在部分依赖和传递依赖； 对于s模式，满足，故属于BCNF； 对于sc模式，满足，故属于BCNF；,例：判断关系模式C（Cno，Cname，Pcno） C3NF CBCNF 例：判断关系模式S（Sno，Sname，Sdept，Sage） 假定Sname唯一 假定S有两个码Sno，Sname S3NF S BCNF,例：关系模式SPJ(S,P,J)，S:学生，J:课程，P:名次，每一个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生（无并列名次）； 函数依赖：（S，J）P；(J，P）S （S，J）与（J，P）都可以作为候选码,属性相交，属性间无部分依赖或传递依赖 SJP 3NF， SJP BCNF,例：在关系模式STC（S，T，C）中，S表示学生，T表示教师， C 表示课程。每一教师只教一门课，每门课有若干教师，某学生选修某门课就对应一个老师。 函数依赖有：（S，C） T ，（S， T ） C ， TC 候选码： （S，T） ，（S，C） 无非主属性对码的部分依赖和传递依赖，但是存在主属性部分依赖于码的情况； 故不属于BCNF；,解决方法：将STC分解为二个关系模式： ST(S，T) BCNF， TC(T，C) BCNF 没有任何属性对码的部分函数依赖和传递函数依赖,一个关系模式达到BCNF,说明在函数依赖的范畴内,已实现了彻底分离,可消除“异常”,但在实际应用中,并不一定要求全部模式都达到BCNF。 3NF与BCNF的关系 如果关系模式RBCNF，必定有R3NF 如果R3NF，且R只有一个候选码，则R必属于BCNF。,BCNF的关系模式所具有的性质 所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非码的任何一组属性,多值依赖,例 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。,多值依赖（续）,非规范化关系,多值依赖（续）,用二维表表示Teaching,多值依赖（续）,TeachingBCNF Teaching具有唯一候选码(C，T，B)， 即全码,多值依赖（续）,Teaching模式中存在的问题 (1)数据冗余度大 (2)插入操作复杂 (3) 删除操作复杂 (4) 修改操作复杂,存在 多值依赖,多值依赖（续）,定义6.9 设R(U)是一个属性集U上的一个关系模式， X、 Y和Z是U的子集，并且ZUXY。关系模式R(U)中多值依赖 XY成立，当且仅当对R(U)的任一关系r，给定的一对（x，z）值，有一组Y的值，这组值仅仅决定于x值而与z值无关,多值依赖（续）,多值依赖的另一个等价的形式化的定义： 在R（U）的任一关系r中，如果存在元组t，s 使得tX=sX，那么就必然存在元组 w，v r，（w，v可以与s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为XY。 这里，X，Y是U的子集，Z=U-X-Y。,多值依赖（续）,平凡多值依赖和非平凡的多值依赖 若XY，而Z，则称 XY为平凡的多值依赖 否则称XY为非平凡的多值依赖,多值依赖（续）,例关系模式WSC（W，S，C） W表示仓库，S表示保管员，C表示商品 假设每个仓库有若干个保管员，有若干种商品 每个保管员保管所在的仓库的所有商品 每种商品被所有保管员保管,多值依赖（续）,多值依赖（续）,WS且WC,用下图表示这种对应,多值依赖的性质,（1）多值依赖具有对称性 若XY，则XZ，其中ZUXY （2）多值依赖具有传递性 若XY，YZ， 则XZ Y （3）函数依赖是多值依赖的特殊情况。 若XY，则XY。 （4）若XY，XZ，则XY Z。 （5）若XY，XZ，则XYZ。 （6）若XY，XZ，则XY-Z，XZ -Y。,多值依赖与函数依赖的区别,(1) 多值依赖的有效性与属性集的范围有关 (2) 若函数依赖XY在R（U）上成立，则对于任何Y Y均有XY 成立 多值依赖XY若在R(U)上成立，不能断言对于任何Y Y有XY 成立,5) 第四范式（4NF）,定义6.10 关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y X），X都含有候选码，则R4NF。 （XY） 如果R 4NF， 则R BCNF 不允许有非平凡且非函数依赖的多值依赖 允许的是函数依赖（是非平凡多值依赖）,4NF,一个存在多值依赖的关系模式，其数据冗余量特别大，而且还有其他异常现象。如果把上面的关系TEACH分解成两个关系C_T和C_B，如下表。,把关系分解成仅含平凡多值依赖的多个关系,定义一个其条件比BCNF更苛刻的范式，即4NF。一个满足4NF的关系模式的特点是： 该关系模式满足BCNF； 该关系模式只允许出现平凡多值依赖。,将TEACH分解后产生的C_T(C,T)和C_B(C,B)，显然因为有CT和CB，故不存在非平凡多值依赖，从而有C_T4NF和C_B4NF,上例中的关系模式TEACH为例，虽然是BCNF，但不是4NF，因为在TEACH (C,T,B)中有:CT和CB，关键字是CTB。虽然TEACHBCNF，但C不是关键字，即TEACH 4NF。,关系模式规范化的基本步骤,练习题,1、设有关系模式R(学号Sno,课程号Cno,成绩G,任课教师TN,教师专长TS)，基于R的函数依赖集F=(Sno,Cno)G,CnoTN,TNTS,判断R为第几范式？ 判断步骤： 是否为1NF； 候选码有（sno，cno），非主属性为（g，tn和ts） 判断函数依赖集中非主属性是否完全函数依赖于候选码；非主属性G对键是完全依赖：(S#,C#)G。但非主属性TN,TS对键是部分依赖(他们仅依赖于键的真子集C#)。 得出结论：属于1NF；,2、设有关系模式R(Sno,sname,sdept)，函数依赖集F=snosname ，Snosdept,判断R为第几范式？ 判断步骤： 是否为1NF； 候选码为（sno），非主属性为（sname和sdept） 判断函数依赖集中非主属性是否完全函数依赖于候选码；非主属性grade对键是完全依赖；但非主属性sname对码是部分依赖(仅依赖于键的真子集sno。属于2NF； 非主属性为（sname和sdept）是否存在传递依赖候选码属于3NF； 主属性sno 是否存在对码的部分和传递依赖 属于BCNF； 得出结论：属于BCNF,3、设有关系模式R(课程C,教师T,参考书B)，学校中某一门课程由多个教师讲授，使用相同的一套参考书;教师可讲授多门课程，每种参考书也可以供多门课程使用。判断R为第几范式？ 判断步骤： 是否为1NF； 候选码为（C,T,B），为全码； 属于3NF； 主属性是否存在对码的部分和传递依赖 属于BCNF； 得出结论：属于BCNF,以上我们完全是在函数依赖的范畴内讨论问题。属于BCNF的关系模式是否就很完美了呢？ 一个关系模式达到BCNF,说明在函数依赖的范畴内,已实现了彻底分离,可消除“异常”； 但从练习可以看出，在关系r中数据冗余和操作异常都十分明显。究其原因，是关系r中存在着一种称之为多值依赖的数据依赖。（如课程：教师=m：n 等）,证明一个BCNF范式必是3NF,证明：用反证法，设R是一个B