数学关系数据库.pptx

3.1 问题的提出关系数据库逻辑设计针对具体问题，如何构造一个适合于它的数据模式数据库逻辑设计的工具关系数据库的规范化理论第1页/共44页二、关系模式的形式化定义关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)R(U,D,DOM,F)R R：关系名U U：组成该关系的属性名集合D D：属性组U U中属性所来自的域DOMDOM：属性向域的映象集合F F：属性间数据的依赖关系集合在本章中简化表示为R(U,F)R(U,F)。当且仅当U U上的一个关系r r 满足F F时，r r称为关系模式 R R（U,FU,F）的一个关系第2页/共44页三、什么是数据依赖定义属性值间的相互关连（主要体现于值的相等与否），这就是数据依赖，它是数据库模式设计的关键数据依赖的类型函数依赖（Functional Dependency，简记为FD）多值依赖（Multivalued Dependency，简记为MVD）连接依赖第3页/共44页四、数据依赖对关系模式的影响例：描述学校的数据库：学生的学号（Sno）、所在系（Sdept）系主任姓名（Mname）、课程名（Cname）、成绩（Grade）单一的关系模式：Student U Sno,Sdept,Mname,Cname,Grade 学校数据库的语义：一个系有若干学生，一个学生只属于一个系；M:1M:1 一个系只有一名主任；1 1：1 1 一个学生可以选修多门课程，每门课程有若干学生选修；M:NM:N 每个学生所学的每门课程都有一个成绩。M:1第4页/共44页数据依赖对关系模式的影响（续）属性组U上的一组函数依赖F：F Sno Sdept,Sdept Mname,(Sno,Cname)Grade SnoCnameSdeptMnameGrade第5页/共44页关系模式Student中存在的问题 数据冗余太大浪费大量的存储空间 例：每一个系主任的姓名重复出现 更新异常（Update AnomaliesUpdate Anomalies）数据冗余，更新数据时，维护数据完整性代价大。例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组 插入异常（Insertion AnomaliesInsertion Anomalies）该插的数据插不进去 例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任 的信息存入数据库。删除异常（Deletion AnomaliesDeletion Anomalies）不该删除的数据不得不删例，如果某个系的学生全部毕业了，我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。第6页/共44页数据依赖对关系模式的影响（续）结论：Student关系模式不是一个好的模式。“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。原因：由存在于模式中的某些数据依赖引起的解决方法：通过分解关系模式来消除其中不合适的数据依赖。第7页/共44页3.2 规范化 规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。第8页/共44页函数依赖定义3.1 设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y”或 “Y函数依赖于X”，记作XY。X称为这个函数依赖的决定属性集(Determinant)。第9页/共44页说明：1.函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。2.函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。例如“姓名年龄”这个函数依赖只有在不允许有同名人的条件下成立3.数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，则拒绝装入该元组。第10页/共44页函数依赖（续）例:Student(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有:Sno Ssex，Sno Sage,Sno Sdept，Sno Sname,Sname Ssex，Sname SageSname Sdept但Ssex Sage若XY，并且YX,则记为XY。若Y不函数依赖于X,则记为XY。第11页/共44页二、平凡函数依赖与非平凡函数依赖在关系模式R(U)中，对于U的子集X和Y，如果XY，但Y X，则称XY是非平凡的函数依赖若XY，但Y X,则称XY是平凡的函数依赖例：在关系SC(Sno,Cno,Grade)中，非平凡函数依赖：(Sno,Cno)Grade 平凡函数依赖：(Sno,Cno)Sno (Sno,Cno)Cno第12页/共44页三、完全函数依赖与部分函数依赖定义3.2 在关系模式R(U)中，如果XY，并且对于X的任何一个真子集X，都有 X Y,则称Y完全函数依赖于X，记作X Y。若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作X P Y。例:在关系SC(Sno,Cno,Grade)中，由于：Sno Grade，Cno Grade，因此：(Sno,Cno)Grade第13页/共44页四、传递函数依赖定义3.3 在关系模式R(U)中，如果XY，Y Z，且Y X，Y X，则称Z传递函数依赖于X。注:如果YX，即XY，则Z直接依赖于X。加上条件YX,是因为如果YX,则XY,实际上是XZ,是直接函数依赖而不是传递函数依赖例:在关系Std(Sno,Sdept,Mname)中，有：Sno Sdept，Sdept Mname Mname传递函数依赖于Sno第14页/共44页范式范式是符合某一种级别的关系模式的集合。关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。各种范式之间的关系：某一关系模式R为第n范式，可简记为RnNF第15页/共44页1NF的定义如果一个关系模式R的所有属性都是不可分的基本数据项，则R1NF。第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。但是满足第一范式的关系模式并不一定是一个好的关系模式。第16页/共44页2NF例:关系模式 SLC(Sno,Sdept,Sloc,Cno,Grade)Sloc为学生住处，假设每个系的学生住在同一个地方。函数依赖包括：(Sno,Cno)f Grade Sno Sdept (Sno,Cno)P Sdept Sno Sloc (Sno,Cno)P Sloc Sdept Sloc第17页/共44页 2NFSLC的码为(Sno,Cno)SLC满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno)SnoCnoGradeSdeptSlocSLC第18页/共44页SLC不是一个好的关系模式(1)(1)插入异常假设Sno95102，SdeptIS，SlocN的学生还未选课，因课程号是主属性，因此该学生的信息无法插入SLC。(2)(2)删除异常 假定某个学生本来只选修了3号课程这一门课。现在因身体不适，他连3号课程也不选修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。(3)(3)数据冗余度大 如果一个学生选修了10门课程，那么他的Sdept和Sloc值就要重复存储了10次。(4)(4)修改复杂 例如学生转系，在修改此学生元组的Sdept值的同时，还可能需要修改住处（Sloc）。如果这个学生选修了K门课，则必须无遗漏地修改K个元组中全部Sdept、Sloc信息。第19页/共44页问题及解决原因 Sdept、Sloc部分函数依赖于码。解决方法 SLC分解为两个关系模式，以消除这些部分函数依赖 SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）第20页/共44页模式分解函数依赖图：SnoCnoGradeSCSLSnoSdeptSloc第21页/共44页 2NF2NF的定义定义3.6 若关系模式R1NF，并且每一个非主属性都完全函数依赖于R的码，则R2NF。例：SLC(Sno,Sdept,Sloc,Cno,Grade)1NF SLC(Sno,Sdept,Sloc,Cno,Grade)2NF SC（Sno，Cno，Grade）2NF SL（Sno，Sdept，Sloc）2NF第22页/共44页例：2NF关系模式SL(Sno,Sdept,Sloc)中函数依赖：SnoSdept、SdeptSloc、SnoSlocSloc传递函数依赖于Sno，即SL中存在非主属性对码的传递函数依赖。存在问题：插入异常、删除异常、数据冗余度大、修改复杂等问题解决方法采用投影分解法，把SL分解为两个关系模式，以消除传递函数依赖：SD（Sno，Sdept），码为Sno DL（Sdept，Sloc），码为Sdept第23页/共44页3NF3NF的定义定义3.8 关系模式R 中若不存在这样的码X、属性组Y及非主属性Z（Z Y）,使得XY，Y X，YZ，成立，则称R 3NF。例，SL(Sno,Sdept,Sloc)2NF SL(Sno,Sdept,Sloc)3NF SD（Sno，Sdept）3NF DL（Sdept，Sloc）3NF第24页/共44页 3NF若R3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。如果R3NF，则R也是2NF。采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。第25页/共44页范式（BCNF）定义3.9 设关系模式R1NF，如果对于R的每个函数依赖XY，若Y不属于X，则X必含有候选码，那么RBCNF。若RBCNF 每一个决定属性集（因素）都包含（候选）码R中的所有属性（主，非主属性）都完全函数依赖于码R3NF（证明）若R3NF 则 R不一定BCNF第26页/共44页 BCNF例：在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称：(S，J)T，(S，T)J，TJSTJ3NF(S，J)和(S，T)都可以作为候选码S、T、J都是主属性STJBCNFTJ，T是决定属性集，T不是候选码第27页/共44页BCNF解决方法：将STJ分解为二个关系模式：SJ(S，J)BCNF，TJ(T，J)BCNF 没有任何属性对码的部分函数依赖和传递函数依赖SJSTTJTJ第28页/共44页3NF与BCNF的关系如果关系模式RBCNF，必定有R3NF如果R3NF，且R只有一个候选码，则R必属于BCNF。第29页/共44页BCNF的关系模式所具有的性质 所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非码的任何一组属性第30页/共44页规范化小结关系数据库的规范化理论是数据库逻辑设计的工具。一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。规范化程度可以有多个不同的级别规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化第31页/共44页关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖消除决定属性 2NF集非码的非平 消除非主属性对码的传递函数依赖凡函数依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NF第32页/共44页规范化的基本思想消除不合适的数据依赖中，使各关系模式达到某种程度的“分离”，采用“一事一地”的模式设计原则。并不是规范化程度越高越好，可以根据实际应用需求在其中任何一步终止第33页/共44页3.3 模式的分解关系模式分解的标准三种模式分解的等价定义 分解具有无损连接性 分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性第34页/共44页模式的分解（续）例:SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSloc SL2NF 存在插入异常、删除异常、冗余度大和修改复杂等问题分解方法可以有多种 第35页/共44页模式的分解1 SL SL SL1 SL2SL1 SL2_ _ _ _ _ Sno Sdept Sloc Sno Sdept Sloc Sno Sloc Sdept SlocSno Sloc Sdept Sloc _ _ _ _ _95001 CS A 95001 CS A 95001 A CS A95001 A CS A 95002 IS B 95002 IS B 95002 B IS B95002 B IS B 95003 MA C 95003 MA C 95003 C MA C95003 C MA C 95004 IS B 95004 IS B 95004 B95004 B PH APH A95005 PH A 95005 PH A 95005 A95005 A 结论：丢失信息，不具无损连接性 第36页/共44页模式的分解2 SL SL SL1 SL2SL1 SL2_ _ _ _ _ Sno Sdept Sloc Sno Sdept Sloc Sno Sdept Sno SlocSno Sdept Sno Sloc _ _ _ _ _95001 CS A 95001 CS A 95001 CS 95001 A95001 CS 95001 A 95002 IS B 95002 IS B 95002 IS 95002 B95002 IS 95002 B 95003 MA C 95003 MA C 95003 MA 95003 C95003 MA 95003 C 95004 IS B 95004 IS B 95004 IS95004 IS 95004 B95004 B 95005 PH A 95005 PH A 95005 PH 95005 PH 95005 A95005 A结论：不丢失信息，但不保持函数依赖性，未能消除异常 第37页/共44页模式的分解3 SL SL SL1 SL2SL1 SL2_ _ _ _ _ Sno Sdept Sloc Sno Sdept Sloc Sno Sdept Sdept SlocSno Sdept Sdept Sloc _ _ _ _ _95001 CS A 95001 CS A 95001 CS CS A95001 CS CS A 95002 IS B 95002 IS B 95002 IS IS B95002 IS IS B 95003 MA C 95003 MA C 95003 MA MA C95003 MA MA C 95004 IS B 95004 IS B 95004 IS95004 IS PH APH A 95005 PH A 95005 PH A 95005 PH 95005 PH 结论：不丢失信息，具无损连接性，同时保持函数依赖性 第38页/共44页无损连接性关系模式R的一个分解=R1，R2，Rn若R与R1、R2、Rn自然连接的结果相等，则称关系模式R的这个分解具有无损连接性（Lossless join）具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题第39页/共44页保持函数依赖分解保持函数依赖分解 定义：若F+(F1F2 Fk)+,则RU,F的分解R1U1，F1，R2U2，F2 RkUk，Fk保持函数依赖。意义：确保整个数据库中数据的语义完整性不受破坏。第40页/共44页模式的分解性质如果一个分解具有无损连接性，则它能够保证不丢失信息。如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。第41页/共44页模式分解算法示例已知关系模式Teaching(CTHRSG)，其中C表示课程，T表示教师，H表示时间，R表示教室，S表示学生，G表示成绩。函数依赖集F及其所反映的语义分别为：CT 每门课程仅有一位教师担任。HTR 在任一时间，一个教师只能在一个教室上课。HRC 在任一时间，每个教室只能上一门课。HSR 在任一时间，每个学生只能在一个教室听课。CSG 每个学生学习一门课程只有一个成绩。在保持函数依赖与无损连接的情况下将其分解为符合3NF的范式。第42页/共44页既有无损联接性又保持函数依赖的分解 用依赖保持分解算法得=CT，CSG，CHR，HSR，HRT，而HS是原模式的关键字，所以=CT，CSG，CHR，HSR，HRT，HS。由于HS是模式HSR的一个子集，所以消去HS后的分解CT，CSG，CHR，HSR，HRT就是具有无损联接性和保持函数依赖性的分解，且其中每一个模式均为3NF。第43页/共44页An Introduction to Database System感谢您的观看！第44页/共44页