关系数据库规范化理论1.ppt

第五章 关系数据库规范化理论,内容特点: 理论性强，从数据依赖出发，得出4级范式 然后按照范式理论，对关系模式进行模式分解，达到某一级别 范式及关系模式的分解是本章的重点和难点，形式化强,关系数据库规范化理论,5.1 问题的提出 5.2 规范化（重点） 5.3 数据依赖的公理系统 *5.4 模式的分解（难点） 5.5 小结,5.1 问题的提出,DB设计理论包括三方面的内容 数据依赖（核心） 范式（Normarform） 模式设计方法,5.1.1 关系概念回顾,1. 关系：描述实体及其属性、实体间的联系。 从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。 2. 关系模式：用来定义关系。 3.关系数据库：基于关系模型的数据库，利用关系来描述现实世界。从形式上看，它由一组关系组成。,4.关系模式的形式化定义 R(U, D, DOM, F) R： 关系名 U： 组成该关系的属性名集合 D： 属性组U中属性所来自的域 DOM：属性向域的映象集合 F： 属性间数据的依赖关系集合。即限定 了组成关系的各个元组必须满足的完整性约束条件。,关系概念回顾,5.关系模式的简化表示 在关系模式R(U, D, DOM, F)中，影响数据库模式设计的主要是U和F，D和DOM对其影响不大，为了方便讨论，我们将关系模式简化为一个三元组： R(U, F) 当且仅当U上的一个关系r满足F时，r称为关系模式R(U, F)的一个关系。,关系概念回顾,5.1.2 什么是数据依赖,1. 完整性约束的表现形式 限定属性取值范围：例如学生成绩必须在0-100之间 定义属性值间的相互关连（主要体现于值的相等与否），这就是数据依赖，它是数据库模式设计的关键。,什么是数据依赖,2. 数据依赖 是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系 是现实世界属性间相互联系的抽象 是数据内在的性质 是语义的体现,什么是数据依赖,3. 数据依赖的主要类型 函数依赖（Functional Dependency，简记为FD） 多值依赖（Multivalued Dependency，简记为MVD） 连接依赖,例1：建立一个描述学校的数据库S_D_C。 涉及的对象包括： 学生的学号（Sno） 所在系（Sdept） 系主任姓名（Dname） 课程号（Cno） 成绩（Grade） 假设学校的数据库模式由一个单一的关系模式S_D_C构成， 则该关系模式的属性集合为： U Sno, Sdept, Dname, Cno, Grade ,5.1.3数据依赖对关系模式的影响,现实世界的已知事实告诉我们： 1. 一个系有若干学生， 但一个学生只属于一个系； 2. 一个系只有一名主任； 3. 一个学生可以选修多门课程， 每门课程有若干学生选修； 4. 每个学生所学的每门课程都有一个成绩。,数据依赖对关系模式的影响,由此可得到属性组U上的一组函数依赖F： F Sno Sdept, Sdept Dname, (Sno, Cno) Grade ,数据依赖对关系模式的影响,关系模式S_D_C 中存在的问题（p 171 ) 数据冗余太大 -浪费大量的存储空间 例：每一个系主任的姓名重复出现，重复次数与该系所有学生的所有课程成绩出现次数相同。,数据依赖对关系模式的影响, 更新异常（Update Anomalies） 数据冗余 ，更新数据时，维护数据完整性代价大。 例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组。,数据依赖对关系模式的影响, 插入异常（Insertion Anomalies） -该插的数据插不进去 例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。,数据依赖对关系模式的影响, 删除异常（Deletion Anomalies） -不该删除的数据不得不删 例，如果某个系的学生全部毕业了， 我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。,数据依赖对关系模式的影响,结论： S_D_C关系模式不是一个好的模式。 一个“好”的模式应当不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。 原因：由存在于模式中的某些数据依赖引起的。 解决方法：通过分解关系模式来消除其中不合适 的数据依赖。,数据依赖对关系模式的影响,例2 教师任课关系模式TDC TDC(教师号，教师名，职称，地址，系，系名，系地址，课程号码，课程名，教学水平，学分) 有数据,数据依赖对关系模式的影响,T TNA TIT ADD D# DNA LOC C# CNA LEVER Credit T1 MA PRF A1 D1 DEPT1 L1 C1 Compu GOOD 3 T1 MA PRF A1 D1 DEPT1 L1 C2 Progr EXCEL 3 T1 MA PRF A1 D1 DEPT1 L1 C3 DB GOOD 4 T2 LI AP A2 D1 DEPT1 L1 C3 DB OK 4 T2 LI AP A2 D1 DEPT1 L1 C4 OS GOOD 4 T3 CHEN PRF A3 D2 DEPT2 L2 C6 MATH GOOD 4,数据依赖对关系模式的影响,在这个关系中，只有根据教师号和课程号才能确定哪位教师上哪门课，也既: 关系TDC的关键字是（教师号，课程号码） 该关系在使用过程中存在下面几个问题：,数据依赖对关系模式的影响,1、 数据冗余 每当教师开设一门课程时，该教师的职称、地址等信息就重复。一个系由好多教师，导致数据冗余非常大。 2、 更新异常 若一位任三门课的教师改变了地址，三个元组都要改变，否则不一致,数据依赖对关系模式的影响,3、 插入异常 若学校新调来一个教师，暂时未讲课，由于缺少部分关键字（不为空），则new teacher就不能插入此关系中。 4 删除异常 若教师不教学了，就要删除相关纪录，那么关于这些教师的其他信息将无法记载。,问题的解决 思考：这两个模式有相同四个“毛病”.? 为什么会发生插入异常和删除异常呢 ? -存在不合适的函数依赖 解决之道：分解! 分解! 再分解!,5.1.4 规范化理论概述,规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。,规范化理论概述,可将S_D_C关系模式分解为： S_D(Sno, Sdept) D-M(Sdept, Dname) S_C(Sno, Cno, Grade ),规范化理论概述,规范化理论概述,若将TDC分解成 T（教师号，教师名，职称，地址，系） D（系，系名，位置） C (课程号，课程名，学分) TC (教师号，课程号，水平),规范化理论概述,T(T#,Tname,TIT,ADD,D#) D(D#,Dname,LOC) C(C#,Cname,Credit) TC(T#,C#,level) 新关系包括4个模式 T和D通过T中的外关键字D#系相联系。 T和C(多对多)通过TC中外关键字（教师号，课程号，T#,C#）相连,规范化理论概述,由前面的讨论知，在关系数据库中，并不是随便一种关系模式设计方案均是可行的，也不是任何一种关系模式都无所谓。,规范化理论概述,要设计一个好的关系模式方案，其根本方法是要弄清属性间的内在语义联系 也即两种依赖联系 （1）函数依赖 (2 ) 多值依赖,5.2 规范化,关系数据库中的每个关系模式的属性间一定要满足某种内在联系，而这种联系又可对关系的不同要求分为若干等级，这就叫做关系的规范化（normalization),规范化概述,规范化的目的主要是为： 克服数据库逻辑结构中的插入异常，删除异常以及冗余度大的缺陷，从而增强数据库库结构的稳定性和灵活性 规范化的过程：模式分解,5.2.1 函数依赖,定义5-1： 设R(U)是属性集U上的关系模式。X,Y是U的子集。若对于X上的每一个具体值，Y有唯一的具体值与之对应，（ X上的属性值确定后， Y上的属性值必确定）则称X函数确定Y或Y函数依赖于X，记作XY 或说: r是R(U) 上的任意一个关系，如果成立 对t , s r，若tX = sX，则tY = sY X称为决定因素， Y称为依赖因素,函数依赖,比如描述一个课程的关系，可以有: 课程号（CNO），课程名（CNAME），学分（CREDIT） 称CNO函数决定CNAME, CREDIT 或者说CNAME, CREDIT函数依赖于CNO， 记为： CNO CNAME , CNO CREDIT,说明： 1. 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。 2. 函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。 例如“姓名年龄”这个函数依赖只有在不允许有同名人的条件下成立,函数依赖,定义52：若有XY，但Y X，则称XY是非平凡的函数依赖。 若 XY，但Y X 则称XY是平凡的函数依赖。,函数依赖,思考：在关系SC(Sno, Cno, Grade)中 非平凡函数依赖？ - (Sno, Cno) Grade 平凡函数依赖： -(Sno, Cno) Sno -(Sno, Cno) Cno,注意： 若不特别声明，总是讨论非平凡的函数依赖,函数依赖,在一个关系模式中 （1）若X和Y有1：1关系，则XY，YX，记作XY。 （2）若X和Y是1:m关系，则有YX， 但X Y,（3）若X和Y是n:m关系，则X,Y之间不存在任何函数依赖,函数依赖,定义53 在R(U)中,如果XY，并且对于X的任何一个真子集X 有X Y,则称Y对X完全函数依赖 记作:X Y 。 由定义知，当X是单个属性时，由于X不存在任何真子集， X Y,函数依赖,若X Y, 但Y不完全函数依赖于X(即存在X的真子集X ，满足X - Y ),则称Y对X部分函数依赖,记作X Y。,函数依赖,例3：设有关系模式选课 SC1(S#,C#,GRADE,CREDIT), 在SC1中，由于一个学生可选多门课，一门课程可由多个学生选修，因此，S#,C#,都不能单独决定GRADE,只能由组合（S#,C#）决定。由此可知 （S#,C#）fGRADE (S#,C#)pCREDIT （因为C#CREDIT),函数依赖,在S_D_C（Sno, Sdept, Dname, Cno，Grade ） 中存在函数依赖： (Sno, Cno) Grade (Sno, Cno) Sdept,F,P,函数依赖,属性组U上的一组函数依赖F： F Sno Sdept, Sdept Dname, (Sno, Cno) Grade ,函数依赖,定义5-4 在R(U)中,如果XY,(Y X),Y X , YZ(Z Y) 则称Z传递函数依赖于X。 记为：X Z,传递,函数依赖,S1(S#,SNAME,D#，DNAME, Location) 存在传递函数依赖 S#location(S#D#location）,函数依赖,F Sno Sdept, Sdept Dname, (Sno, Cno) Grade ,Sno Dname,传递,函数依赖,定义55 设K为RU，F中的属性或属性组合， 若K U, 则K为R的候选关键字（码）（Candidate key）。,5.2.2 码,若候选码多于一个，则选定其中的一个为主关键字（码）（Primary key） 包含在任何一个候选码中的属性,叫做主属性(Prime attribute)。 不包含在任何码中的属性称为非主属性(Nonprime attribute)或非码属性(Non-key attribute)。,码,最简单的情况，单个属性是码；最极端的情况，所有属性都为码 如 S (SNO , SDEPT , SAGE) SC( SNO ,CNO ,GRADE ) R( P,W,A),码,候选码有两个性质： （1）标志的唯一性：对R(U)中的每一个元组，K确定后，元组就相应确定了。 （2）无冗余性：当K是属性组时，K的任一部分不能确定元组 在例2关系SC1(S#,C#,GRADE,CREDIT)中，属性组（S#,C#）是候选码，也是主码， S#,C#是主属性，CRADE,CREDIT是非主属性。,码,定义5-6 关系模式R中属性或属性组X并非R的码,但X是另一个关系模式的码,则称 X是R的外部码(Foreign key)也称外码。 主码与外部码提供了一个表示关系间联系的手段。,码,如：在选课关系DB中 S(S#,SNAME,SEX,ADD) C(C#,CNAME,CREDIT) SC(S#,C#,GRADE) 学生和课程之间存在的多对多联系由SC反映出来，三个关系间的联系是通过SC的外码S#,C#实现的。,码,5.2.3 范式,范式是符合某一种级别的关系模式的集合。 关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。 范式的种类： 第一范式(1NF) 第二范式(2NF) 第三范式(3NF) BC范式(BCNF) 第四范式(4NF) 第五范式(5NF),范式,各种范式之间存在联系： 某一关系模式R为第n范式，可简记为RnNF。,一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合 -规范化。,范式,一范式（1NF）-是关系最基本的性质 定义5-7 在关系模式中R的每一个具体关系r中，若每个属性值都不可再分，则称R为第一范式，记作RlNF。 DB研究的都是1NF的关系，不是1NF的R为非规范化R.,范式,设有关系模式SC1（S#,C#,GRADE,CREDIT）,存在函数依赖（S#,C#）GRADE, C#CREDIT; 码（S#,C#），该关系存在下列问题： 1. 数据冗余 每当1名学生选修一门课时，学分就重复一次，若同一门课被40多名学生选修，则CREDIT要重复40多次。,范式,2更新异常 SC1（S#,C#,GRADE,CREDIT） 若调整了某门课的学分，则每个相应元组的CREDIT都要改 3插入异常 若学校计划开设新课，应把其C#和CREDIT插入到SC1中，但只有当有学生选此课时才能插入。,范式,4. 删除异常 若学生已结业，则删除选修记录，若某些门新生未选修，则其CREDIT将无从记载。 在本例中，原因在于非主属性CREDIT函数依赖于组合码（S#,C#）的一部分。（S#,C#）CREDIT,P,范式,定义58 若RlNF,且每一个非主属性完全函数依赖于码,则R2NF。 将上述非2NF的关系规范化为2NF， 设法消除部分依赖。 SC（S#,C#,GRADE）通过外码C#联系 C(C#,CREDIT)需要时作自然连接则恢复原关系 消除了部分函数依赖的1NF的关系模式必定是2NF,5.2.4 二范式,思考：S-D-C(Sno, Sdept, Dname, Cno, Grade ) 是2NF吗？,二范式(2NF),一个关系模式R若属于2NF,就会有较少异常和较少冗余度。,二范式(2NF),满足2NF的关系仍可能出现问题， 如S1(S#,SNAME, D#,DNAME ,Location)， 码是单个属性S#，不存在部分依赖，属于2NF。 但仍存在大量冗余。有关“系”的重复值随着学生的增加而增加，也存在类似上面的异常。 原因是? 存在传递依赖S#location(S#D#location),二范式(2NF),定义59 若关系模式R(U)的每个非主属性都不部分依赖也不传递依赖于关键字，则称R满足第三范式，记为R 3NF 如 Student (Sno ,Sname, Ssex, Sdept, Sage) SC(S# , C#, GRADE) Course(C#, Cname, Cpno, Ccredit) S1(S#, SNAME, D#， DNAME , Location),5.2.5 三范式(3NF),第三范式将关系模式中的属性分为两类: 非主属性集 主属性集 而非主属性集的每个属性均完全、不传递依赖于主属性集中的关键字，从而做到在关系模式中理顺了复杂的依赖关系，使依赖单一化与标准化，进而力求达到避免异常性的出现。,三范式(3NF),一个关系模式R若不是3NF,就会产生插入异常、删除异常、冗余度大等问题。 可以通过模式分解使其分解成若干个模式，使分解后的模式能满足第三范式,三范式(3NF),三范式(3NF),通过投影分解将 S1(S#,SNAME,D#，DNAME,location) 分解成如下两个关系后，则满足3NF的要求 S(S#,SNAME,D#), D(D#,DNAME,location),必须注意，投影时不能从关系S中遗漏外关键字D#， 否则，这两个关系之间将失去联系， 就不能通过自然连接再恢复原来的关系。,根据上述规范化过程，包括下面4个关系模式 SC(S#,C#,GRADE) C(C#,CNAME,CREDIT) S(S#,SNAME,D#) D(D#,DNAME,location),SC1分解,S1分解,三范式(3NF),达到了3NF的要求，课程学分和系地址的存储减少到了最低限度，学生删除选课也不再影响CREDIT，对学分与系地址的插入与更新简化了。从而有效避免数据不一致性的潜在危险。,三范式(3NF),应用举例 EX1:指出下面关系模式属于几范式，为什么？STJ(S,T,C)中,S表示学生,T表示教师,C表示课程。每一教师只教一门课。每门课有若干教师,某一学生选定某门课,就对应一个固定的教师。 由语义可得到如下的函数依赖。 (S,C)T (S,T)C TC 这里(S,C),(S,T)都是候选码。不存在非主属性，是3NF,三范式(3NF),Ex2 ：对于规范化的模式，经过（1）转变为1NF， 将1NF经过（2）转变为2NF， 将2NF经过（3）转变为3NF， 则 （1）使属性域变为不能再分的简单域 （2）消除非主属性对主关键字的部分依赖 （3）消除非主属性对主关键字的传递依赖,三范式(3NF),Ex3:当关系模式R（A，B）已属于3NF， 下列说法中（）是正确的 A、它一定消除了插入和删除异常 B、仍可能存在插入和删除异常 C、一定属于2NF -B ,C,1972年Boyce, Codd等从另一个角度研究了范式，发现了函数依赖中的决定因素与关键字间的联系与范式有关，从而创立了另一种扩冲的第三范式，称为 Boyce- Codd范式，简称BCNF,5.2.6 BC范式（BCNF）,部分函数依赖和传递函数依赖是产生存储异常的两个重要原因，3NF消除了大部分存储异常，具有较好的性能。但3NF并没有要求消除主属性对候选关键字的传递依赖，如果存在这种情况，3NF仍可能发生存储异常现象,BC范式（BCNF）,假设有关系模式仓库保管WPE WPE(W# , P#, E#, QNT) 其中各属性分别表示仓库号、器件号、职工号、数量,BC范式（BCNF）,W# p# E# QNT W1 P1 E1 20 W1 P2 E3 15 W1 P3 E2 18 W1 P4 E1 10 W1 P5 E3 20 W1 P7 E3 18 W1 P6 E2 15 W2 P4 E4 12 W2 P1 E5 20 W2 P3 E4 18 W2 P6 E5 15 W3 P2 E6 20 W3 P3 E6 15 W3 P4 E7 18,它所反映的语义是： （1）一个仓库有多个职工 （2）一个职工仅在一个仓库工作 （3）每个仓库里一种器件由专人 负责，但一个人可以管理几种器件,存在函数依赖 (W# , P#)-QNT (W#, P#)- E# E#-W# (E#, P#)-QNT,根据语义可以分析出下面函数依赖 （W# , P#)-QNT (W#, P#)- E# E#-W# (E#, P#)-QNT 因此这个关系模式有两个候选关键字（W# , P# ), (E# ,P#) 它们都能函数决定整个元组。只有一个非主属性QNT，它对任何一个候选关键字都是完全依赖的，并且是直接函数依赖。故，该关系模式属于3NF,BC范式（BCNF）,会出现: 如果一个新职工被分配到仓库工作，但暂时处于实习阶段，没有独立承担任务，由于缺少关键字的一部分P#而无法插入到该关系中去。要消除这些异常需要提出更高的要求。 原因是:主属性E#是W#的决定因素，但它本身不是关键字，只是组合关键字的一部分，这就造成主属性W#对另一个不包含它候选关键字（E# , P#)的部分依赖。,BC范式（BCNF）,再如： 关系模式STJ(S,T,C)中,S表示学生,T表示教师,C表示课程。每一教师只教一门课。每门课有若干教师,某一学生选定某门课,就对应一个固定的教师。 由语义可得到如下的函数依赖。 (S,C)T (S,T)C TC 这里(S,C),(S,T)都是候选码。,BC范式（BCNF）,STJ是3NF,因为没有任何非主属性对码传递依赖或部分依赖。 但STJ不是BCNF关系,因为T是决定因素,而T不包含码。 仍有一些不良的影响,BC范式（BCNF）,S T C 95001 T001 C001 95001 T002 C002 95003 T002 C002 95004 T003 C001 95004 T004 C003 95005 T001 C001 95006 T001 C001 95007 T002 C002,BC范式（BCNF）,不良特性 插入异常：如果没有学生选修某位老师的任课，则该老师担任课程的信息就无法插入 删除异常：删除学生选课信息，会删除掉老师的任课信息 更新异常：如果老师所教授的课程有所改动，则所有选修该老师课程的学生元组都要做改动 数据冗余：每位学生都存储了有关老师所教授的课程的信息 症由： 主属性对码的不良依赖,BC范式（BCNF）,3NF的“不彻底”性表现在: 可能存在主属性对码的部分依赖和传递依赖。需要更高一级的范式要求。,BC范式（BCNF）,定义510 如果关系模式RU,F的所有属性都不传递依赖也不部分依赖于R的任何候选关键字，则称RBCNF。 或关系模式RU,F，若XY且Y X时X必是侯选码,则RBCNF。 也就是说,关系模式RU,F中,若每一个决定因素都包含关键字（而不是被关键字所包含）,则RBCNF。 （ E#-W# (E#, P#)-QNT ）,BC范式（BCNF）,由BCNF的定义可以得到以下结论: 一个满足BCNF的关系模式有 1.所有非主属性对每一个码都是完全函数依赖。 2.所有的主属性对每一个不包含它的码,也是完全函数依赖。 3.没有任何属性完全函数依赖于非码的任何一组属性。 4.如果R BCNF，则R 3NF。BCNF排除了任何属性对码的传递与部分依赖。,BC范式（BCNF）,思考 (1) SCM(Sno,Cno,Mc)中,Sno是学号,Cno表示课程号,Mc表示名次。每一个学生选修每门课程的成绩有一定的名次，每一个课程中的每一个名次只有一个学生，它属于3NF吗？是BCNF吗？ (2)全码属于BCNF吗？,BC范式（BCNF）,非BCNF的关系模式也可以通过分解成为BCNF。 例如STJ可分解为： ST(S,T) TJ（T,C),它们都是BCNF。,BC范式（BCNF）,由于R BCNF,按定义排除了任何属性对码的传递依赖与部分依赖,所以R 3NF。但是若R 3NF,则R未必属于BCNF。,BC范式（BCNF）,* 一个模式中的关系模式如果都属于BCNF,那么在函数依赖范畴内,它已实现了彻底的分离,已消除了插入和删除的异常。,BC范式（BCNF）,上面我们的讨论是在函数依赖的范畴内，属于BCNF的关系模式是否就很完美了呢？,5.2.7 多值依赖与第四范式,多值依赖与第四范式,例：学校中某一门课由多个教员讲授，他们使用相同的一套参考书。每个教员可以讲授多门课，每种参考书可以供多门课程使用。 下面用一个非规范化的关系来表示教员T，课程C和参考书B之间的关系,多值依赖与第四范式,课程C 教员T 参考书B 物理 李勇 普通物理学 王军 物理习题集 光学原理 数学 李勇 数学分析 张平 微分方程 高等代数,多值依赖与第四范式,课程C 教员T 参考书B 物理 李 勇 普通物理学 物理 李 勇 光学原理 物理 李 勇 物理习题集 物理 王 军 普通物理学 物理 王 军 光学原理 物理 王 军 物理习题集 数学 李 勇 数学分析 数学 李 勇 微分方程 数学 李 勇 高等代数 数学 林 静 数学分析 数学 林 静 微分方程 数学 林 静 高等代数,关系模式TEACH（C#，T#，B#），一门课程由多个教员担任，一门课程使用相同的一套参考书。 它的码是（C#，T#，B#） 所以属于BCNF,多值依赖与第四范式,但它仍有不良特性: 插入异常：当某门课程增加一名教员时，该门课程有多少本参考书就必须插入多少个元组；同样当某门课程需要增加一本参考书时，它有多少个教员就必须插入多少个元组 删除异常：当删除一门课程的某个教员或者某本参考书时，需要删除多个元组 更新异常：当一门课程的教员或参考书作出改变时，需要修改多个元组 数据冗余：同一门课的教员与参考书信息被反复存储多次,多值依赖与第四范式,定义5.9(多值依赖) (1)描述型：关系模式R(U)，X、Y、Z U，并且Z = U X Y，多值依赖X Y成立 当且仅当对R(U)的任一关系r，给定一对（x，z）值,有一组Y值与之对应，这组值仅仅决定于x值而与z值无关,多值依赖与第四范式,课程C 教员T 参考书B 物理 李 勇 普通物理学 物理 李 勇 光学原理 物理 李 勇 物理习题集 物理 王 军 普通物理学 物理 王 军 光学原理 物理 王 军 物理习题集 数学 李 勇 数学分析 数学 李 勇 微分方程 数学 李 勇 高等代数 数学 林 静 数学分析 数学 林 静 微分方程 数学 林 静 高等代数,在上述具体关系模式中： 对于一个(物理,光学原理)，有一组T值李勇，王军，这组值仅仅决定于课程C上的值物理,与其它的属性光学原理无关。 因为，对于另一个（物理，普通物理学），它对应的一组T值仍是李勇，王军，尽管这时参考书B的值已经改变了，因此T多值依赖于C，即 C-T,多值依赖与第四范式,(2)形式化：关系模式R(U)，X、Y、ZU，Z=UX Y，对于R(U)的任一关系r，若存在元组t1，t2，使得t1X = t2X，那么就必然存在元组t3，t4，使得： t3X = t4X = t1X = t2X t3Y = t1Y， t4Y = t2Y t3Z = t2Z， t4Z = t1Z 则称Y多值依赖于X，记作X Y,多值依赖与第四范式,如(C#, T#, B#)满足C#T#， 含有元组 t1=(C1, T1, B1)， t2=(C1, T2, B2)， 则也一定含有元t3=(C1, T1, B2)，t4=(C1, T2, B1)。,多值依赖与第四范式,t1,t3,t2,t4,练习: 请指出下面关系中的多值依赖 (1) MSC(M,S,C) M表示专业,S表示学生,C表示该专业的必修课. 假设每个专业有多个学生,有一组必修课,同专业课内所有学生所修的必修课相同 按照语义,对于M的每一个值Mi, S有一个完整的集合与之对应,而不问C取何值 所以有: MS 由于C与S的完全对称性,必然也有 MC,多值依赖与第四范式,(2)RDP(R,D,P) .R表示病房,D表示医生,P表示病人.设每个病房住有多个病人,有多个医生负责和护理该病房的所有病人. 则有 : RD RP,多值依赖与第四范式,在多值依赖中，若X Y且Z=U-X-Y 不空 则称X Y为非平凡多值依赖，否则称为平凡多值依赖,多值依赖与第四范式,多值依赖的性质 （1）在R（U）中，若有X Y，则有 X U-X-Y （2）函数依赖可看成是多值依赖的特例,多值依赖与第四范式,由前面的例子知，具有多值依赖的关系，它们的数据冗余特别大，可以将其分解减少冗余。如把关系模式teaching分解为： C1（C，T） C2（C，B） 即可明显减少冗余和异常,多值依赖与第四范式,从多值依赖的观点来看，在C1，C2中各对应着一个多值依赖C-T, C-B, 它们都是平凡多值依赖。 因此，在多值依赖时，减少数据冗余的方法是使关系分解成仅有平凡多值依赖,多值依赖与第四范式,定义512 R（U）中如果X-Y是非平凡多值依赖，则X必含有关键字，此时称R满足第四范式，记作：R 4NF,5.2.8 四范式（4NF),在前面的teaching关系中，虽然有 C-T C-B, 但由于其关键字是 （C，T，B），所以不是4NF 而在C1（C，T）中，有C-T , C为关键字，不存在非平凡多值依赖，因此C14NF,四范式（4NF),规范化小结,（1）规范化的目的 在关系数据库中，对关系模式的基本要求是满足第一范式，但有些关系模式存在插入删除异常，规范化的目的就是解决插入、修改、删除异常以及数据冗余,（2）规范化的方法（思想） 逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的“分离”，即“一事一地”的模式设计原则，尽量作到每个模式表示客观世界中的一个事物,规范化小结,（3）规范化的方法（过程） 规范化的方法（过程）是用模式分解的方法。 通过对关系模式的分解，把低一级的关系分解成若干个高一级的关系,规范化小结,1NF 2NF 3NF BCNF 4NF,消除非主属性对关键字的部分依赖,消除非主属性对关键字的传递依赖,消除主属性对关键字的部分和传递依赖,消除非平凡多值依赖,练习题,一、选择与填空 1、在关系模式中，如果属性A和B存在1对1的联系，则说_。 A、AB B、BA C、AB D、以上都不是 答案：C 2、在关系模式DB中，任何二元关系模式的最高范式必定是_。 A、1NF B、2NF C、3NF D、BCNF 答案：D 3、关系模式R中的属性全部是主属性，则R肯定是_。 A、2NF B、3NF C、BCNF D、4NF 答案：B,练习题,4、关系模式的分解（ ） A、唯一 B、不唯一 答案： B 5、侯选关键字的属性可以有 A、0个 B、1个 C、1个或多个 D、多个 答案：C,6、消除了部分函数依赖的1NF的关系模式是必定是： A、1NF B、2NF C、3NF D、BCNF 答案：B 7、关系模式中，满足2NF的模式是： A、必定是1NF B、必定是2NF C、必定是3NF D、可能是1NF 答案：A,练习题,8、设计性能较好的关系模式称为规范化，规范化的主要理论依据是（） A、关系规范化理论 B、关系运算理论 C、关系代数理论 D、数理逻辑 答案： A,9、关系数据库规范化是为了解决关系数据库中（ ）问题而引如的 A、插入、删除和数据冗余 B、提高查询速度 C、减少数据操作的反复性 D、保证数据完整性和安全性 答案： A,练习题,10、规范化过程主要为克服数据库逻辑结构中的插入异常，删除异常以及 （ ）缺陷 A、数据的不一致性 B、 结构不合理 C、冗余度大 D、数据丢失 答案： C,11.关系规范化中的删除操作异常是指（1）， 插入操作异常是指（2） （1） 不该删除的数据被删除 （2）应该插入的数据未被插入,二、判断对错 1.任何一个二目关系都属于3NF。 （） 2.任何一个二目关系都属于BCNF。 （） 3.任何一个二目关系都属于4NF。 （ ）,4.若R.A-R.B , R.B-R.C 则R.A-R.C （） 5.若R.A-R.B , R.B-R.C 则R.A-R.(B,C) （） 6.若R.B-R.A , R.C-R.A 则R.(B,C) -R.A （） 7. 若R.(B,C) -R.A则R.BR.A , R.C-R.A （,三、将上述的仓库保管WPE分解成BCNF范式WPE(W# , P#, E#, QNT) （W# , P#)-QNT (W#, P#)- E# E#-W# (E#, P#)-QNT 分解： 保管 EP（E# ， P#，QNT） 关键字是 E# ， P# 工作EW（E# ，W#） 关键字是 E#,练习题,四、指出下列关系模式是第几范式，并说明理由 （1） R（X，Y， Z） F=XY Z （2）R（X，Y， Z） F=Y Z, XZ-Y (3) R（X，Y， Z） F=Y-Z, Y-X, X-YZ,练习题,(4) R（X，Y， Z） F=X-Y , X- Z (5) R（W, X，Y， Z） F=X- Z, WX-Y,练习题,解： （1） R（X，Y， Z） F=XY - Z R的侯选关键字XY， F中只有一个函数依赖，而该函数依赖的 左部包含了R的侯选关键字， 所以R为BCNF,(2）R（X，Y， Z） F=Y Z, XZ-Y R的侯选关键字为XY和XZ，R中所有属性都为主属性，不存在非主属性对侯选关键字的传递依赖，但存在主属性Z对关键字XY的部分依赖 或者说决定因素Y被关键字包含 或决定因素不是关键字 所以 仅为3NF,练习题,（3）R（X，Y， Z） F=Y-Z, Y-X, X-YZ R的侯选关键字为X和Y ： 又因为F的每一个函数依赖的左部都包含了任一侯选关键字 所以R为BCNF,练习题,（4）R（X，Y， Z） F=X-Y , X- Z R的侯选关键字为X， 而F的每一个函数依赖的左部都包含有侯选关键字 所以R 为BCNF,（5）R（W, X，Y， Z） F=X- Z, WX-Y R的侯选关键字为 WX，则Y， Z为非主属性，又由于X- Z, 因此F中存在非主属性对侯选关键字的部分依赖 所以R仅为1NF,5.3 数据依赖的公理系统,数据依赖的公理系统是模式分解算法的理论基础 如何判定关系的范式？ 如何判定关系的码？ 问题 给定一组函数依赖，是否能导出另外一些函数依赖，或另外的函数依赖是否成立。 （如练习四中的： （2）R（X，Y， Z） F=Y Z, XZ-Y）是否隐含XY-Z 如FD=A B，B C，A C是否成立？,函数依赖的推理规则,逻辑蕴涵 Armstrong公理系统 闭包的计算(重点) 函数依赖的等价和覆盖(极小覆盖计算）,定义5.11 关系模式R(U,F)，F是其函数依赖，X，Y是其属性子集，如果从F的函数依赖能够推出XY，则称F逻辑蕴涵XY， 记作F XY 如: R(X, Y), F = XY 能推出: XX , XXY,定义5.12 被F所逻辑蕴涵的函数依赖的全体所构成的集合 称作F的 闭包，记作F+ = XY | F XY 如: R(X, Y), F = XY F+ = X， XX， XY， XXY， Y， YY XY ，XYX，XYY，XYXY,Armstrong公理系统,Armstrong公理系统: 设U为属性集总体,F是一组U上的函数依赖, X，Y，Z是属性集，对R(U,F) 有 自反律(reflexivity)：若Y X， 则X Y 增广律(augmentation)：若X Y ，则XZ YZ 传递律(transitivity)：若X Y，Y Z，则X Z,Armstrong公理系统,Armstrong公理正确性的证明,按函数依赖定义r是R上的任一关系， t，s r,Armstrong公理系统,若X Y ，则XZ YZ,Armstrong公理系统,若X Y，Y Z，则X Z,Armstrong公理系统,由Armstrong公理导出的推理规则 (1)合并律(union rule) 若X Y，X Z，则X YZ (2)分解律(decomposition rule) 若X Y Z Y，则X Y，X Z (3)伪传递律(pseudotransitivity rule) 若X Y，WY Z，则WX Z,Armstrong公理系统,若X Y，X Z， 则X YZ,Armstrong公理系统,若X Y，WY Z， 则WX Z,Armstrong公理系统,Armstrong公理的有效性及完备性 有效性：用Armstrong公理从F中导出的函数依赖一定在F+ 完备性：F +中的每一个函数依赖，必定可由F根据Armstrong公理推出来,Armstrong公理系统,Armstrong公理系统,引理5.1 XA1 A2 Ak成立 XAi成立(i=1, 2, ,k) 定义5.13 属性集的闭包,设F为属性集U上的一组函数依赖，X U， = A | XA能由F根据Armstrong公理导出 称 为属性集X关于函数依赖集F的闭包,Armstrong公理系统,例1 属性集U=A，B，C， 函数依赖集F=A B，B C 则 A+ = ABC B+ = BC C+ = C,引理5.2 X,Y是U的属性子集 XY能由Armstrong公理导出 Y 这样： XY能否由Armstrong公理导出转化为求出XF+,判定Y是否为XF+的子集问题,Armstrong公理系统,闭包的计算,算法5.1（求属性集的闭包）,最多|U|-|X|步,闭包的计算,例2 R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH,计算 所用依赖 AB AGB AC AGBC CGH AGBCH CGI AGBCH I = AGBCH I,思考：AG是码吗,注意！ 只要该属性集的闭包包含关系的所有属性,那么该属性就为候选码 检验任何给定函数依赖：A1A2An-B是否蕴含于F的 步骤： 第一步，计算闭包。根据F计算 A1A2An-F+ 第二步，判断。如果B在A1A2AnF+中，则A1A2An- B蕴含于F中，否则不蕴含于F中,闭包的计算,例3： R, U = (A, B, C, D, E，F), F = ABC, BCAD, DE, CFB 判断ABD和D-A是否蕴含于F中 解：（1）先求AB的闭包 ABF+=A,B,C,D,E 因为：D在ABF+中，所以ABD蕴含于F中 （2）再求D的闭包 D F+ =D,E 因为A不在D F+ ，所以D-A不蕴含于F中,闭包的计算,例4 R, U = (A, B, C, D, E), F = ABC, BD, CE, CEB, ACB,计算 所用依赖 ABC ABC BD ABCD CE ABCDE = ABCDE,闭包的计算,闭包的计算,例5 R, U = (A, B, C, D, E, G), F = AE, BEAG, CEA, GD,计算 所用依赖 AE ABE BEAG ABEG GD ABEGD = ABEGD,假设某个关系模式上有F，那么在该关系作任何更新时，数据库系统都要保证F中的所有依赖在新数据库状态下仍然满足，否则就取消这种更新操作。因此数据库系统要对更新进行检测，开销较大。 为了降低检测开销，在不改变闭包的情况下，可以简化给定的函数依赖集。,闭包的计算,函数依赖的等价和覆盖,定义5.14函数依赖集的等价性 (1)函数依赖集F，G，若F+= G+，则称F与G等价。 (2) F+ = G+ F G+，G F+,定义5.1