数据库系统概论AnIntroductiontoDatabaseSystems

1、数据库系统概论 An Introduction to Database Systems黔 南 民 族 师 范 学 院 计 算 机 科 学 系 黔南民族师范学院计算机科学系数据库系统概论An Introduction to Database System第六章 关系数据理论第六章 关系数据理论6.1 问题的提出6.2 规范化6.3 数据依赖的公理系统*6.4 模式的分解6.5 小结数据库设计的基本步骤6.1 问题的提出关系数据库逻辑设计针对具体问题，如何构造一个适合于它的数据模式。（应该设计多少个关系模式、每个关系模式由哪些属性构成、关系模式之间的联系）设计目标：避免出现过多数据冗余更新异常插入

2、异常删除异常解决方案：数据库逻辑设计的工具关系数据库规范化理论。关系模式的形式化定义与数据依赖关系模式的五元组组成： R(U, D, DOM, F)R： 关系名U： 组成该关系的属性名集合D： 属性组U中属性所来自的域DOM： 属性向域的映象集合F： 属性间数据依赖的集合 数据依赖：定义关系内部属性值间的相互关连（主要体现于值的相等与否），它是数据库模式设计的关键。简化关系模式R为：R（U, F） 当且仅当U上的一个关系r满足F时，r称为关系模式 R（U, F）的一个关系数据依赖分类数据依赖类型（函数依赖、多值依赖）函数依赖（Functional Dependency，简记为FD） 关系R上的

3、FD指：如果R的两个属性在属性A1，A2，An上一致(这些属性上对应分量相同)，则它们在其它分量B上的值也必定相同。 记做 A1A2AnB 即 A1，A2，An函数决定B 如果属性集A1，A2，An函数决定多个属性，即 A1A2AnB1，A1A2AnB2， ，A1A2AnBm 则这个FD集合可缩写为： A1A2AnB1B2Bm数据依赖对关系模式的影响例建立一个描述学校教务的数据库：学生的学号(Sno)、所在系(Sdept)、系主任姓名(Mname)、课程名(Cname)、成绩(Grade)用单一关系模式描述 ： Student U Sno, Sdept, Mname, Cname, Grade

4、说明：1、一个系有若干学生，而一个学生只属于一个系。 2、一个系只有一名(正职)负责人系主任。 3、一个学生可选多门课程，每门课程有若干学生选修。 4、每个学生选每门课有一个成绩。数据依赖对关系模式的影响（续）则Student属性组U上的一组函数依赖F为： FSnoSdept, SdeptMname, (Sno, Cname)Grade SnoCnameSdeptMnameGrade数据依赖对关系模式的影响Student表示例SnoSdeptMnameCnoGradeS1计科系张明C195S2计科系张明C190S3计科系张明C188S4计科系张明C170问题： 数据冗余：系主任名重复出现 更新

5、异常：系主任更换，则需更换所有学生相应信息 插入异常：如某系刚成立，没有学生，则不能插入系的相关信息 删除异常：删除所有学生信息，则删除一个系的信息数据依赖对关系模式的影响解决方法：通过分解关系模式来消除其中不合适的数据依赖。把这个单一模式分成3个关系模式： S Sno，Sdept，Sno Sdept SC Sno，Cno，Grade，(Sno，Cno) Grade DEPT Sdept，Mname，Sdept Mname思考：什么是不合适的函数依赖，应该怎么消除呢？第六章 关系数据理论6.1 问题的提出6.2 规范化6.3 数据依赖的公理系统*6.4 模式的分解6.5 小结6.2 规范化 规

6、范化理论是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。 规范化理论以数据依赖为基础（函数依赖、多值依赖），利用“范式”表示其能达到的规范级别。6.2 规范化6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结函数依赖 定义6.1 设R(U)是一个属性集U上的关系模式，X和Y是U的子集。 若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等， 而在Y上的属性值不等， 则称 “X函数确定Y”

7、或 “Y函数依赖于X”，记作XY。 若XY，YX，则记作XY。 若Y不函数依赖于X，则记作XY。函数依赖的类型 平凡的： Y X 非平凡的： Y 中至少有一个属性不属于X 完全非平凡的： Y中所有属性均不属于X完全函数依赖与部分函数依赖 定义6.2 在R(U)中，如果XY，并且对于X的任何一个真子集X，都有X Y, 则称Y对X完全函数依赖，记作 X F Y 若XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作X P Y。 例 在学生教务系统中 (Sno,Cno)Grade是完全函数依赖， (Sno,Cno)Sdept是部分函数依赖，因为Sno Sdept成立，且Sno是（Sno，Cno

8、）的真子集。FP传递函数依赖 定义6.3 在R(U)中，如果XY，(Y X) ,YX ，YZ， (Z Y)， 则称Z对X传递函数依赖。 记为：X Z 注: 如果YX， 即XY，则Z直接依赖于X。例: 在关系Std(Sno, Sdept, Mname)中，有： Sno Sdept，Sdept Mname Mname传递函数依赖于Sno传递分解/结合规则如果属性集A1，A2，An函数决定多个属性，即 A1A2AnB1，A1A2AnB2， ，A1A2AnBm则这个FD集合可缩写为： A1A2AnB1B2Bm分解规则(splitting rule) 用A1A2AnBi(i=1,2, ,m)替换A1A2

9、AnB1B2Bm合并规则(combining rule) 用A1A2AnB1B2Bm 替换A1A2AnBi(i=1,2, ,m)闭包属性集闭包的定义： 假设属性集合A1,A2,An，S是一个FD集合。则S集合下属性集合A1,A2,An的闭包(closure)的集合B，使得每一个满足S中的所有FD的关系，也同样满足A1A2AnB。即A1A2AnB是从S的FD中推断出来的。 A1,A2,An的闭包记为A1,A2,An。 为简化讨论，允许存在平凡FD，于是A1,A2,An总是在A1,A2,An中。闭包算法属性集A1,A2,An 关于某已知FD集合S的闭包算法：1.设X是结果属性集合，闭包。首先把X初

10、始化为A1,A2,An 。2.在S中查找B1B2BnC这样的式子，这里B1,B2,Bn在X中，而C不在X中。如找到，则把C加入到X。3.重复第二步，直到不再有其他的属性加入到X。（因X的元素只能增长，而关系模式中属性都是有限的，最后肯定存在不能再加入情况。）当不能添加任何属性时，集合X就是A1,A2,An。例 ：考虑含有属性A,B,C,D,E,F的关系，设关系有FD：ABC, BCAD, DE, CFB，则A,B的闭包A,B+是什么？ A,B+= A,B,C,D,E闭包作用判断任一给定的A1A2AnB是否来自FD集合S的推断：首先可用S计算A1,A2,An。如果B在A1,A2,An中，则说明A

11、1A2AnB可以从S推断出来。如果B不在A1,A2,An中，则A1A2AnB不能从S推断出来。例 ：考虑含有属性A,B,C,D,E,F的关系，设关系有FD：ABC, BCAD, DE, CFB，是否ABD， DA由S推出？ DA不是ABD是闭包和键的关系：当且仅当A1,A2,An是关系的超键时， A1,A2,An才是这个关系所有属性的集合。故如要验证A1,A2,An是关系的键，则可验证A1,A2,An是否包含所有属性。 Armstrong公理系统 若想知道一个FD是否从指定的FD集合中导出，经常使用闭包算法。但也可使用Armstrong公理的一组规则得到一个给定集合能推断出的FD。 关系模式R

12、 来说有以下的推理规则：自反律(Reflexivity)：若Y X U，则X Y为F所蕴含。增广律(Augmentation)：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。传递律(Transitivity)：若XY及YZ为F所蕴含，则XZ为F所蕴含。6.2 规范化6.2.1 函数依赖6.2.2 码（键）6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结6.2.2 码（键） 定义6.4 设K为R中的属性或属性组合。如K满足下列条件，则认为K是关系R的键或侯选码(Candidate Key)： 1、若K U，

13、即K函数决定其他属性。 2、不存在K的任意真子集L， L U。即码必须是最小的。FF全码All-key ：所有U中的属性构成码主键Primary Key ：候选键有多个时，可选择其中之一作为主键超键SuperKey：包含键的属性集码（键）关系键属性的设计原则（E/R关系模式）如关系R来自一个实体集，则其键就是该实体集的键属性 如联系是多对多，则与其相连的实体集的键属性都是R的键属性。如联系是从E1到E2的多对一联系，则只有E1的键属性是R的键属性。如联系是一对一，则与其相连的任意一个实体集的键属性都是R的键属性。即键不唯一。 关于键的最小化和最小值的问题？例教学管理系统概念设计（E-R模型）教

14、师学生选课成绩课程选课考试成绩任课教师任课任课教师例教学管理系统逻辑结构设（ E-R图向关系模式的转换）关系模式表6.2 规范化6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结6.2.3 范式范式是符合某一种级别的关系模式的集合。关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。某一关系模式R为第n范式，可简记为RnNF。一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化模式分解 一般用分解关系的方法来消除异常

15、。分解R不但要分离R的属性，使其组成两个新的关系，还要对R进行投影以转移元组的信息到这两个新关系中。 给定一个模式为A1,A2,An的关系R，分解为关系S和T，它们的模式分别为B1,B2,Bm和C1,C2,Ck，并且满足： 1、 A1,A2,An= B1,B2,Bm C1,C2,Ck。 2、S中的元组是R中所有元组在B1,B2,Bm 上的投影。由于在S上的投影可能存在重复，所以应消除重复项。 3、 同上，T中的元组是R中所有元组在C1,C2,Ck上的投影。范式关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖消除决定属性 2NF集非码的非平 消除非主属性对码的传递函数依赖凡函数依

16、赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NF6.2 规范化6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结6.2.4 1NF1NF定义：如果一个关系模式R的所有属性都是不可分的基本数据项(原子属性)，则R1NF第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库但是满足第一范式的关系模式并不一定是一个好的关系模式1NF例4 关系模式 S-L-C(Sno, Sdept, Sloc, Cno, Gra

17、de) Sloc为学生住处，假设每个系的学生住在同一个地方函数依赖包括： (Sno, Cno) F Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept SlocSnoCnoGradeSdeptSlocS-L-C的码为(Sno, Cno)S-L-C满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno, Cno)S-L-C不是一个好的关系模式S-L-C(Sno, Sdept, Sloc, Cno, Grade)(1) 插入异常：如学生未选课，则不能插入学生信息。(2) 删除异常：如删除学生所有选修课程

18、，其信息就将消失。(3) 修改复杂：转系学生不仅需要修改系别，还要修改住处。(4) 数据冗余度大：学生每一门选修都附带系别和住处信息。 2NF（续）2NF定义：若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。 即允许关系中存在传递FD，但不允许有左边是键真子集的非平凡FD存在(消除非主属性对码的部分依赖)。 将一个1NF关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题，但不能完全消除。由1NF分解到2NF 1NF：S-L-C(Sno, Sdept, Sloc, Cno, Grade) Sloc函数依赖包括： (Sno

19、, Cno) F Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc2NF：分解为两个关系模式，以消除非主属性部分函数依赖 SC(Sno， Cno， Grade) (Sno, Cno) F Grade S-L(Sno， Sdept， Sloc) SnoSdept，SnoSloc，SdeptSloc 传递依赖是否存在异常？6.2 规范化6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结 6

20、.2.5 3NF3NF定义：若R3NF，则每一个非主属性既不部分依赖于码也不传递依赖于码。例：2NF关系模式S-L(Sno, Sdept, Sloc)中 函数依赖： SnoSdept、Sdept Sno、SdeptSloc 可知：SnoSloc，存在非主属性对码的传递函数依赖。S-L分解为两个关系模式，以消除传递函数依赖： S-D（Sno， Sdept） 函数依赖：SnoSdept D-L（Sdept，Sloc） 函数依赖： SdeptSloc3NF1NF：S-L-C(Sno, Sdept, Sloc, Cno, Grade)通过上述分解，得到3个3NF SC(Sno，Cno，Grade)函数

21、依赖： (Sno, Cno) Grade S-D（Sno， Sdept） 函数依赖：SnoSdept D-L（Sdept，Sloc） 函数依赖： SdeptSloc3NF说明 一个关系模式总可以信息无损地分解到3NF，并且原关系中的FD仍存在分解后的多个关系中。3NF可以某种程度上避免异常，但仍然会导致大量冗余。6.2 规范化6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结BC范式（BCNF）关系R满足BCNF当且仅当： 如果R中非平凡FD A1A2An B1B2Bm成立，则A

22、1,A2,An是关系R的超键。即每一个决定属性因素都包含码。说明若RBCNF ：所有非主属性对每一个码都是完全函数依赖所有的主属性对每一个不包含它的码，也是完全函数依赖没有任何属性完全函数依赖于非码的任何一组属性 把低级的关系模式分解为若干个高级的关系模式的方法不是唯一的，目的是将一个关系用多个不会产生异常的关系来替换。保证不产生异常的条件称为Boycc-Codd范式，BCNF。分解为BCNFBCNF分解步骤：首先寻找违反BCNF条件地非平凡FD： A1A2An B1B2Bm。即要找A1,A2,An不是超键的FD。然后尽可能地往FD右边增加足够多的由A1,A2,An决定的属性。最后将上述FD分

23、解为两个模式：一个包含FD的所有属性，另一个包含位于这个FD左边的属性和不属于FD的所有属性(关系中的)。 重复使用适当的分解，可以把任何一个关系模式分解为具有下列重要性质的多个真子集： 1.这些真子集都满足BCNF的关系模式 2.原始关系中的数据都正确地反映在分解后地关系上。(可重构)BCNF考虑下面关系模式Movies(title,year,length,filmtype,studioname,starname)1、有哪些函数依赖？2、主键是谁？3、如何分解到BCNF?BCNFMovies(title,year,length,filmtype,studioname,starname)函数依

24、赖： title yearlength filmtype studioname？ title yearstarname？ title year studioname length?主键选择： title,year? title,year,studioname? title,year,starname? 分析表明：Movies关系模式的主键应为 title,year,starnameBCNFMovies(title,year,length,filmtype,studioname,starname)BCNF分解： title yearlength filmtype studioname 违反了BC

25、NF。应为左边不是超键。应安BCNF分解方法进行分解。 由于该FD右边已经包含了由 title，year函数决定的所有属性。所以可把Movies分解为： 1.包含上述FD所有属性的模式： title,year,length,filmtype,studioname 2.除了上述FD右边三个属性外，包含了其它所有属性的模式： title,year,starname3NF与BCNF的关系R BCNF R 3NF如果R3NF，且R只有一个候选码 R BCNF R 3NF充分不必要充分必要6.2 规范化6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF6.2.5 3NF6.2.6 BC

26、NF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结课 程 C教 员 T参 考 书 B物理数学计算数学李 勇王 军李 勇张 平张 平 周 峰 普通物理学光学原理 物理习题集数学分析微分方程高等代数数学分析.多值依赖 例9 教师授课关系：学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。多值依赖用二维表表示Teaching普通物理学光学原理物理习题集普通物理学光学原理物理习题集数学分析微分方程高等代数数学分析微分方程高等代数李 勇李 勇李 勇王 军王 军王 军李 勇李 勇李 勇张 平张 平张 平 物 理物 理物 理物 理

27、物 理物 理数 学数 学数 学数 学数 学数 学 参考书B教员T课程C多值依赖TeachingC,T,B具有唯一候选码(C,T,B)，即全码：分别考察单属性、双属性情况？TeachingC,T,BBCNF：FD的左边是超键，并决定了所有属性。不存在属性的部分依赖和传递依赖情况。Teaching模式中存在的问题: (1)数据冗余度大 (2)插入操作复杂 (3) 删除操作复杂 (4) 修改操作复杂存在多值依赖多值依赖 某个模式是BCNF，但在相应关系中还有与FD无关的冗余存在。在BCNF模式中最常见的导致冗余的情况，是试图把两个或多个多对多联系置于同一个关系中。多值依赖定义 设R(U)是一个属性集

28、U上的一个关系模式， X、 Y和Z是U的子集，并且ZUXY。关系模式R(U)中多值依赖 XY成立，当且仅当对R(U)的任一关系r，给定的一对（x，z）值，有一组Y的值，这组值仅仅决定于x值而与z值无关。多值依赖更精确的说法是，对于R(U)中属性集X，Y，Z，若MVD XY存在，则对在X上取值相同的元组对t和u，能找到满足下列条件的元组v：在X上的取值与t和u相同在Y上的取值与t相同在Z上的取值与u相同例Teaching（C, T, B）CT普通物理学光学原理物理习题集普通物理学光学原理物理习题集数学分析微分方程高等代数数学分析微分方程高等代数李 勇李 勇李 勇王 军王 军王 军李 勇李 勇李

29、勇张 平张 平张 平 物 理物 理物 理物 理物 理物 理数 学数 学数 学数 学数 学数 学 参考书B教员T课程Ctu多值依赖平凡多值依赖和非平凡的多值依赖若XY，而Z，则称 XY为平凡的多值依赖否则称XY为非平凡的多值依赖多值依赖的性质（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) 多值依赖的有效性与属性集的范围有关若函数依赖XY在R（U）上成立，则对于任何Y Y均有XY 成立多值依赖XY若在R(U)上成立，不能断言对于任何Y Y有XY