第06讲 关系数据理论 v2014

1、学以致用学以致用 用以促学用以促学An Introduction to Database System数据库系统原理数据库系统原理第六讲第六讲 关系数据理论关系数据理论学以致用学以致用 用以促学用以促学An Introduction to Database System第第6 6讲讲 关系数据理论关系数据理论1. 问题问题的提出的提出2. 规范化规范化3. 数据依赖数据依赖的公理系统的公理系统4. 模式的分解模式的分解学以致用学以致用 用以促学用以促学An Introduction to Database System1. 问题问题的提出的提出 针对针对具体问题，如何构造一个适合于它的数据模式

2、具体问题，如何构造一个适合于它的数据模式 1 1）应该应该构造几个关系模式；构造几个关系模式； 2 2）每每一个关系应该由哪一些属性组成。一个关系应该由哪一些属性组成。思考：教务管理数据库的模式？思考：教务管理数据库的模式？ 关系数据库的逻辑设计问题关系数据库的逻辑设计问题 数据库逻辑设计的工具数据库逻辑设计的工具关系数据库的规范化理论关系数据库的规范化理论学以致用学以致用 用以促学用以促学An Introduction to Database System概念回顾概念回顾v 关系关系v 关系关系模式模式v 关系数据库关系数据库v 关系数据库关系数据库的模式的模式学以致用学以致用 用以促学用以

3、促学An Introduction to Database System概念回顾概念回顾关系模式的形式化定义关系模式由五部分组成，即它是一个五元组：关系模式由五部分组成，即它是一个五元组： R(U, D, DOM, F)R： 关系名（关系名（符号化的元组语义）U： 组成该关系的属性名集合组成该关系的属性名集合D： 属性组属性组U中属性所来自的域中属性所来自的域DOM： 属性向域的映象集合属性向域的映象集合F： 属性间数据的依赖关系集合属性间数据的依赖关系集合学以致用学以致用 用以促学用以促学An Introduction to Database System关系关系模式的简化表示模式的简化表示

4、v关系模式关系模式R（U, D, DOM, F）简化为一个三元组：）简化为一个三元组： R（U, F） 当且仅当当且仅当U上的一个关系上的一个关系r满足满足F时，时，r称为关系模式称为关系模式 R（U, F）的一个关系）的一个关系学以致用学以致用 用以促学用以促学An Introduction to Database System问题的问题的提出提出数据依赖数据依赖1） 完整性约束的表现形式完整性约束的表现形式 限定属性取值范围：例如学生成绩必须在限定属性取值范围：例如学生成绩必须在0-100之间之间 定义属性值间的相互关连（主要体现于值的相等与否），这就定义属性值间的相互关连（主要体现于值的

5、相等与否），这就是数据依赖，它是数据库模式设计的关键是数据依赖，它是数据库模式设计的关键学以致用学以致用 用以促学用以促学An Introduction to Database System2）数据依赖数据依赖 一个关系内部属性与属性之间的约束关系一个关系内部属性与属性之间的约束关系 现实世界属性间相互联系的抽象现实世界属性间相互联系的抽象 数据内在的性质数据内在的性质 语义的体现语义的体现3）数据依赖数据依赖的类型的类型函数依赖（函数依赖（Functional Dependency，简记为，简记为FD）多值依赖（多值依赖（Multivalued Dependency，简记为，简记为MVD）问

6、题的问题的提出提出数据依赖数据依赖学以致用学以致用 用以促学用以促学An Introduction to Database System数据依赖数据依赖对关系模式的影响对关系模式的影响【例】【例】 建立一个描述学校教务的数据库：建立一个描述学校教务的数据库： 学生的学号（学生的学号（Sno）、所在系（）、所在系（Sdept） 系主任姓名（系主任姓名（Mname）、）、课程课程号号（Cno）、成绩（、成绩（Grade） 单一的关系模式单一的关系模式 ： Student U Sno, Sdept, Mname, Cno, Grade 数据之间的关系有数据之间的关系有： 1） 一个系有若干个学生，一

7、个学生只属于一个系；一个系有若干个学生，一个学生只属于一个系； 2） 一个系只有一名系主任；一个系只有一名系主任； 3） 一个学生可以选修多门课程；一个学生可以选修多门课程； 4） 每个学生选修的每门课程有一个成绩。每个学生选修的每门课程有一个成绩。学以致用学以致用 用以促学用以促学An Introduction to Database System数据依赖数据依赖对关系模式的影响对关系模式的影响属性组属性组U上的一组函数依赖上的一组函数依赖F： F Sno Sdept, Sdept Mname, (Sno, Cno) Grade 单一的关系模式单一的关系模式 ： Student SnoCno

8、SdeptMnameGrade学以致用学以致用 用以促学用以促学An Introduction to Database System数据依赖数据依赖对关系模式的影响对关系模式的影响关系模式关系模式StudentStudent中存在的中存在的问题问题：1. 1. 数据冗余太大：数据冗余太大：如系主任的姓名，这将浪费大量的存储空间。2. 2. 更新异常（更新异常（Update AnomaliesUpdate Anomalies）：）：由于冗余，更新数据库时系统要付出很大的代价来维护数据库的完整性，否则面临数据的不一致性，比如换了系主任3. 3. 插入异常（插入异常（Insertion Anomal

9、iesInsertion Anomalies）：）：如某个系刚成立没有学生，则系主任的信息无法存入到数据库。4. 4. 删除异常（删除异常（Deletion AnomaliesDeletion Anomalies）：）：如学生毕业了，要删除学生的信息，则系主任的信息业被删除了。SnoSdeptMnameCnoGrade20100001sseChen02159520100002sseChen02158920100003sseChen02157520100004sseChen021580：学以致用学以致用 用以促学用以促学An Introduction to Database System数据依赖

10、数据依赖对关系模式的影响对关系模式的影响结论：结论：nStudent关系模式不是一个好的模式。关系模式不是一个好的模式。n“好好”的模式：的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少 原因：原因：由存在于模式中的某些数据依赖引起的由存在于模式中的某些数据依赖引起的 解决方法：解决方法：通过关系模式通过关系模式的规范化的规范化来来消除其中不合适的数据依赖消除其中不合适的数据依赖学以致用学以致用 用以促学用以促学An Introduction to Database System第第6 6讲讲 关系数据理论关系数据理论1.

11、 问题问题的提出的提出2. 规范化规范化3. 数据依赖数据依赖的公理系统的公理系统4. 模式的分解模式的分解学以致用学以致用 用以促学用以促学An Introduction to Database System2.2.规范化规范化 2.1 函数依赖函数依赖 2.2 码码 2.3 范式范式 2.4 2NF 2.5 3NF 2.6 BCNF 2.7 多值依赖多值依赖 2.8 4NF学以致用学以致用 用以促学用以促学An Introduction to Database Systemn 函数依赖是指一个关系表中属性（列）之间的联系。n 函数依赖关注一个属性或属性集与另外一个属性或属性集之间的依赖，亦

12、即两个属性或属性集之间的约束。n 函数依赖是关系中属性之间在语义上的关联特性。n 数据库设计者根据对关系R中的属性的语义理解确定函数依赖，确定约束R的所有元组r的函数依赖集，并获知属性间的语义关联。符号说明：符号说明： R表示一个关系的模式；表示一个关系的模式； UA1，A2，An 是是R的所有属性的集合；的所有属性的集合； F 是是 R中函数依赖的集合；中函数依赖的集合； r 是是 R所取的值；所取的值； t X 表示元组表示元组t在属性在属性 X 上的取值。例如上的取值。例如 t Dname = HuangKai2.1 函数函数依赖依赖学以致用学以致用 用以促学用以促学An Introdu

13、ction to Database System函数依赖定义函数依赖定义n 设有一个关系模式设有一个关系模式R(U),X,YR(U),X,Y为其属性为其属性 U U 的子集，即的子集，即X X U,Y U,Y U, U, 设设t,st,s是关系是关系R R中的任意两个元组，如果中的任意两个元组，如果 tX = sX, tX = sX,则则tY=sY,tY=sY,那么称那么称Y Y函数依赖于函数依赖于 X X ，或，或 X X 函数决定函数决定 Y, Y,也可称也可称 F F：X XYY在关系在关系模式模式R( U )R( U )上成立。上成立。函数依赖图函数依赖图u左部称为决定因子左部称为决定

14、因子u右部称为依赖因子。右部称为依赖因子。XYY函数依赖于函数依赖于X函数依赖图函数依赖图2.1 函数函数依赖依赖学以致用学以致用 用以促学用以促学An Introduction to Database System说说 明明 1. 所有关系实例均要满足所有关系实例均要满足2. 语义范畴的概念语义范畴的概念3. 数据库设计者可以对现实世界作强制的规定数据库设计者可以对现实世界作强制的规定 例如：例如：规定不允许同名人出现，因而使得 “姓名姓名” “年龄年龄”函数依赖成立。学以致用学以致用 用以促学用以促学An Introduction to Database System在关系模式在关系模式

15、R( U )中，对于中，对于 U 的子集的子集 X 和和 Y： 如果Y X， XY显然成立，此时称XY是平凡的函数依赖是平凡的函数依赖 若XY，但Y X, 则称XY是非平凡的函数依赖非平凡的函数依赖例：在关系例：在关系SC(Sno, Cno, Grade)中，中， 非平凡函数依赖：非平凡函数依赖： (Sno, Cno) Grade 平凡函数依赖：平凡函数依赖： (Sno, Cno) Sno (Sno, Cno) Cno 平凡的平凡的函数依赖必然成立，它不反映任何语义，若不特别声明，函数依赖必然成立，它不反映任何语义，若不特别声明，总是总是讨论非平凡的函数依赖。讨论非平凡的函数依赖。2.1 函数

16、函数依赖依赖学以致用学以致用 用以促学用以促学An Introduction to Database System 若若XY，则则 X 称为称为这个函数依赖的决定属性组，也这个函数依赖的决定属性组，也称为决定因素（称为决定因素（Determinant）。）。 若若XY，YX，则记作，则记作XY。 若若Y不函数依赖于不函数依赖于X，则记作，则记作XY。2.1 函数函数依赖依赖学以致用学以致用 用以促学用以促学An Introduction to Database System2.1 函数依赖函数依赖完全函数依赖完全函数依赖与部分函数依赖与部分函数依赖SnoCnoSdeptMnameGrade学以

17、致用学以致用 用以促学用以促学An Introduction to Database System2.1 函数依赖函数依赖传递函数依赖传递函数依赖定义：定义： 在R ( U ) 中，如果XY，(Y X) ,YX YZ，则 称Z对X传递函数依赖。 记为：X Z 注注: : 如果YX， 即XY，则Z直接依赖于X。 【例】【例】 在关系Std (Sno, Sdept, Mname) 中，有： （学号，院系，系主任）（学号，院系，系主任） Sno Sdept，Sdept Mname Mname传递函数依赖于Sno传递传递学以致用学以致用 用以促学用以促学An Introduction to Datab

18、ase System2.2 码码定义（用函数依赖定义码）定义（用函数依赖定义码）: 设K为R 中的属性或属性组合。若K U，则K称为R的侯选码侯选码（Candidate Key）。 若候选码多于一个，则选定其中的一个做为主码主码（Primary Key）F学以致用学以致用 用以促学用以促学An Introduction to Database Systemv 主属性与非主属性主属性与非主属性 包含在任何一个候选码中的属性包含在任何一个候选码中的属性 ，称为主属性（，称为主属性（Prime attribute） 不包含在任何候选码中的属性称为非主属性（不包含在任何候选码中的属性称为非主属性（No

19、nprime attribute）或非码属性（）或非码属性（Non-key attribute） v 全码全码 整个属性组是码，称为全码（整个属性组是码，称为全码（All-key） 2.2 码码学以致用学以致用 用以促学用以促学An Introduction to Database System2.2 码码【例】关系模式【例】关系模式S(Sno, Sdept, Sage)，单个属性，单个属性Sno是码，是码， SC（Sno，Cno，Grade）中，（）中，（Sno，Cno）是码）是码【例】【例】 关系模式关系模式R（P，W，A） P：演奏者：演奏者 W：作品：作品 A：听众：听众 一个演奏者可

20、以演奏多个作品一个演奏者可以演奏多个作品 某一作品可被多个演奏者演奏某一作品可被多个演奏者演奏 听众可以欣赏不同演奏者的不同作品听众可以欣赏不同演奏者的不同作品 码为码为(P，W，A)，即，即All-Key 学以致用学以致用 用以促学用以促学An Introduction to Database System2.3 2.3 范范 式式v 范式是符合某一种级别的关系模式的集合范式是符合某一种级别的关系模式的集合v 关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式同范式v 范式的种类：范式的种类：第一范式第一范式(1NF

21、)第二范式第二范式(2NF)第三范式第三范式(3NF)BC范式范式(BCNF)第四范式第四范式(4NF)第五范式第五范式(5NF)学以致用学以致用 用以促学用以促学An Introduction to Database System2.3 2.3 范范 式式v各种范式之间存在联系：各种范式之间存在联系：v某一关系模式某一关系模式R为第为第n范式，可简记为范式，可简记为RnNF。v 一个低一级范式的关系模式，通过模式分解可以转换为若干一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫个高一级范式的关系模式的集合，这种过程就叫规范化规范化 。NF5NF4

22、BCNFNF3NF2NF1学以致用学以致用 用以促学用以促学An Introduction to Database Systemv 1NF 的定义的定义如果一个关系模式如果一个关系模式 R 的所有属性都是不可分的基本数据项，则的所有属性都是不可分的基本数据项，则 R1NFn 第一范式是对关系模式的最起码的要求，第一范式是对关系模式的最起码的要求，不满足第一范式的数据库模式不满足第一范式的数据库模式不能称为关系数据库不能称为关系数据库学号姓名选修课程数学英语语文2014001张三908589学号姓名数学英语语文2014001张三908589n 但是满足第一范式的关系模式并不一定是一个好的关系模式

23、。但是满足第一范式的关系模式并不一定是一个好的关系模式。1范式非1范式2.3 2.3 范范 式式 1NF1NF学以致用学以致用 用以促学用以促学An Introduction to Database Systemn 码函数确定非主属性码函数确定非主属性院长院长学号学号课程号课程号学院名学院名n 传递函数依赖传递函数依赖 U 学号，课程号学号，课程号，学院名，院长，成绩，学院名，院长，成绩 学院名学院名学号学号课程号课程号院长院长学号学号课程号课程号n 部分函数依赖部分函数依赖学号学号课程号课程号成绩成绩学号学号课程号课程号学院名学院名学号学号课程号课程号院长院长2.4 2 2NFNF学以致用学

24、以致用 用以促学用以促学An Introduction to Database System课程号课程号成绩成绩学号学号课程号课程号成绩成绩完全函数依赖：完全函数依赖：部 分 函 数 依部 分 函 数 依赖：赖：解决方法：解决方法： 学生学生 关系分解为两个关系模式，以消除这些部分函数依赖关系分解为两个关系模式，以消除这些部分函数依赖 SCSC（学号，课程号学号，课程号， 成绩）成绩） S S（学号学号，学院名，院长），学院名，院长）学院名学院名院长院长学号学号学院名学院名院长院长学号学号2.4 2NF2NF“学生学生” 关系模式关系模式 学学 生生 （学号，课程号学号，课程号，学院名，院长，

25、成绩），学院名，院长，成绩）学以致用学以致用 用以促学用以促学An Introduction to Database System2.4 2NF2NFv2NF的定义的定义 若R1NF，且每一个非主属性完全函数依赖非主属性完全函数依赖于码，则R2NF。例例：Student (Sno, Sdept, Mname, Cno, Grade) 1NF Student(Sno, Sdept, Mname, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF S（Sno， Sdept， Mname） 2NF学以致用学以致用 用以促学用以促学An Introduction to D

26、atabase System2.4 2 2NFNFv 2NF的定义的定义 若R1NF，且每一个非主属性完全函数依赖非主属性完全函数依赖于码，则R2NF。v 采用投影分解法将采用投影分解法将一个一个1NF1NF的关系分解的关系分解为多个为多个2NF2NF的关系，的关系，可以在一定程度上可以在一定程度上减轻原减轻原1NF1NF关系中存关系中存在的异常、冗余度在的异常、冗余度大和修改复杂等问大和修改复杂等问题。题。学号学号课程号课程号学院名学院名院长院长成绩成绩201400010215sseChen95201400020215sseChen89201400030215sseChen752014000

27、40215sseChen80：学号学号课程号课程号成绩成绩20140001021595201400020215892014000302157520140004021580：学号学号学院名学院名院长院长20140001sseChen20140002sseChen20140003sseChen20140004sseChen：1NF学以致用学以致用 用以促学用以促学An Introduction to Database System2.5 2.5 3 3NFNF【例例】2NF关系模式关系模式 S (学号学号, 学院名学院名, 院长院长) 中中 传递函数依赖：传递函数依赖： 学号学号学院学院 学院学院

28、 学号学号 学院学院院长院长S 学号学号 学院名学院名 院长院长传递函数依赖的解决方法：传递函数依赖的解决方法： 采用投影分解法，把采用投影分解法，把S 分解为两个关系模式，以消除传递函数依赖分解为两个关系模式，以消除传递函数依赖 S_D（学号学号， 学院）学院） D_M（学院学院，院长），院长）传递依赖：传递依赖：学以致用学以致用 用以促学用以促学An Introduction to Database System2.5 2.5 3 3NFNF学号学号学院名学院名20140001sse20140002sse20140003sse20140004sse：S 学号学号学院名学院名院长院长学号学号

29、学院名学院名S-D学院名学院名院长院长D-M学院名学院名院长院长sseChen：学号学号学院名学院名院长院长20140001sseChen20140002sseChen20140003sseChen20140004sseChen：学以致用学以致用 用以促学用以促学An Introduction to Database System2.5 3NFv3NF3NF的定义的定义定义：定义：关系模式关系模式R 中若不存在这样的码中若不存在这样的码 X、属性、属性组组Y及非主属性及非主属性 Z（Z Y）, 使得使得 X Y，Y Z 成立，成立，Y X，则称，则称R 3NF。n若若R3NF，则每一个非主属性

30、既不部分依赖于码也不，则每一个非主属性既不部分依赖于码也不传递依赖于码。传递依赖于码。 学以致用学以致用 用以促学用以促学An Introduction to Database System2.5 3NFv 采用投影分解法将一个采用投影分解法将一个2NF的关系分解为多个的关系分解为多个3NF的关系，可以的关系，可以在一定程度上解决原在一定程度上解决原2NF关系中存在的插入异常、删除异常、数关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题据冗余度大、修改复杂等问题。学以致用学以致用 用以促学用以促学An Introduction to Database Systemv 规范化理论是数

31、据库逻辑设计的工具规范化理论是数据库逻辑设计的工具1范式范式2范式范式3范式范式关系数据模型的基本要求消除了部分函数依赖消除传递函数依赖目的：尽量消除插入、删除异常，修改复杂，数据冗余目的：尽量消除插入、删除异常，修改复杂，数据冗余2.5 3NF学以致用学以致用 用以促学用以促学An Introduction to Database System讨论讨论与思考与思考v1、规范化方法是否唯一，不同的规范化方法有何异同？、规范化方法是否唯一，不同的规范化方法有何异同？学号学号学院名学院名S-D1学院名学院名院长院长D-M1学号学号学院名学院名S-D2学学 号号院长院长D-M2S 学号学号学院名学院

32、名院长院长 学号学号学院名学院名院长院长S学以致用学以致用 用以促学用以促学An Introduction to Database System学号学号学院名学院名院长院长20140001sseChen20140002sseChen20140003sseChen20140004sseChen：学号学号学院名学院名20140001sse20140002sse20140003sse20140004sse：学号学号学院名学院名20140001sse20140002sse20140003sse20140004sse：学院名学院名 院长院长sseChen：学号学号学院名学院名院长院长20140001ss

33、eChen20140002sseChen20140003sseChen20140004sseChen：学号学号院长院长20140001Chen20140002Chen20140003Chen20140004Chen：v 不同规范化方法之比较不同规范化方法之比较讨论讨论与思考与思考学以致用学以致用 用以促学用以促学An Introduction to Database System讨论讨论与思考与思考 2、规范化可能会产生什么样的负面作用，请举一例说明？、规范化可能会产生什么样的负面作用，请举一例说明？ 学号学号学院名学院名20140001sse20140002sse20140003sse201

34、40004sse：学院名学院名院长院长sseChen：可能增加查询的复杂度：可能增加查询的复杂度： 比如需要查询20140002号学生的院长是谁？学号学号学院名学院名院长院长20140001sseChen20140002sseChen20140003sseChen20140004sseChen：学以致用学以致用 用以促学用以促学An Introduction to Database System2.6 BCBC范式范式( (BCNF)v定义：定义：关系模式关系模式R1NF，若，若XY且且Y X 时时 X 必必含有码，则含有码，则R BCNF;v等价于：等价于：在一个关系模式中每一个决定属性因素

35、都包含码。在一个关系模式中每一个决定属性因素都包含码。学以致用学以致用 用以促学用以促学An Introduction to Database System2.6 BCBC范式范式v 若若RBCNF 所有非主属性对每一个码都是完全函数依赖 所有的主属性对每一个不包含它的码，也是完全函数所有的主属性对每一个不包含它的码，也是完全函数依赖依赖 没有任何属性完全函数依赖于非码的任何一组属性v R BCNF R 3NF充分不必要学以致用学以致用 用以促学用以促学An Introduction to Database System2.6 BCBC范式范式【例例】 关系模式关系模式SC（Sno，Cno，G

36、rade）n SC3NFn SCBCNF【例例】 关系模式关系模式S（Sno，Sname，Sdept，Sage）n 假定假定S有两个码有两个码Sno，Snamen S3NF。n SBCNF学以致用学以致用 用以促学用以促学An Introduction to Database System2.6 BCBC范式范式【例例】关系模式关系模式SCR（Student，Course，Rank），假设没有），假设没有并列名次。并列名次。n 函数依赖函数依赖: (Student，Course)Rank, (Course，Rank)Studentn （Student，Course）与（）与（Course，Ra

37、nk）为候选码）为候选码, 属性相交属性相交n SCR3NF，n SCRBCNF (除了（除了（Student, Course）和（）和（Course, Rank）再没）再没有其它的有其它的决定因素决定因素)学以致用学以致用 用以促学用以促学An Introduction to Database System2.6 BCBC范式范式【例例】在关系模式在关系模式STC（Student，Teacher，Course）中，）中，Student表示表示学生，学生，Teacher表示教师，表示教师，Course表示课程。表示课程。 每个教师只教一门课，每门课有若干个老师，某学生选定某门课就对应一每个教师

38、只教一门课，每门课有若干个老师，某学生选定某门课就对应一个固定的老师。个固定的老师。 函数依赖：函数依赖： (Student，Course) Teacher，(Student，Teacher) Course， Teacher Course (Student，Course )和 (Student，Teacher)都是候选码学以致用学以致用 用以促学用以促学An Introduction to Database System2.6 BCBC范式范式 CSCTSTSTC中的函数依赖中的函数依赖v STC3NF 没有任何非主属性对码传递依赖或部分依赖没有任何非主属性对码传递依赖或部分依赖 v STCB

39、CNF T是决定因素，是决定因素，T不包含码不包含码学以致用学以致用 用以促学用以促学An Introduction to Database System2.6 BCBC范式范式v 解决方法：解决方法：将STC分解为二个关系模式： ST(S，T) BCNF， TC(T，C) BCNF 没有没有任何属性任何属性对码的部分函数依赖和传递函数依赖对码的部分函数依赖和传递函数依赖STSTTCTC学以致用学以致用 用以促学用以促学An Introduction to Database System2.6 BCBC范式范式vR BCNF R 3NFv如果R3NF，且R只有一个候选码 R BCNF R 3N

40、F充分不必要充分必要学以致用学以致用 用以促学用以促学2.7 多值依赖多值依赖An Introduction to Database System【例例】学校中某一门一门课程由多个多个教师讲授，他们使用相相同同的一套参考书，每个教师可以额讲授多门多门课程，每种参考书可以供多门多门课程使用学以致用学以致用 用以促学用以促学2.7 多值依赖多值依赖An Introduction to Database Systemu 非规范化关系课程课程教师教师参考书参考书物理数学计算数学课程课程C教师教师T参考书参考书B物理李勇普通物理物理李勇光学原理物理李勇物理习题集物理王军普通物理物理王军光学原理物理王军物

41、理习题集数学李勇数学分析数学李勇微分方程数学李勇高等代数数学张平数学分析数学张平微分方程u 规范化关系Teaching学以致用学以致用 用以促学用以促学2.7 多值依赖多值依赖An Introduction to Database System原因：存在多值依赖！学以致用学以致用 用以促学用以促学An Introduction to Database System2.7 多值依赖多值依赖定义：定义：设R(U)是属性集U上的一个关系模式，X, Y和Z是U的子集， 并且Z=U-X-Y。关系模式R(U)中多值依赖XY成立，当且仅当对R(U)的任一关系r，给定的一对(x, z )值，有一组Y的值，这组

42、值仅仅决定于x值，而与z值无关。课程课程C教师教师T参考书参考书B物理数学计算数学C TC B学以致用学以致用 用以促学用以促学An Introduction to Database System2.7 多值依赖多值依赖u 平凡的多值依赖和非平凡的多值依赖平凡的多值依赖和非平凡的多值依赖 若X Y 有，且Z=，则称X Y为平凡的多值依赖 否则，称X Y为非平凡的多值依赖 学以致用学以致用 用以促学用以促学An Introduction to Database System2.7 多值依赖多值依赖【例例】 关系模式关系模式WSC(W, S, C)lW表示仓库，S表示保管员，C表示商品；l假设每个

43、仓库有若干个保管员，有若干种商品；l每个保管员保管所有仓库的所有商品；l每种商品被所有保管员保管。WSCw1s1c1w1s1c2w1s1c3w1s2c1w1s2c2w1s2c3w2s3c4w2s3c5w2s4c4w2s4c5学以致用学以致用 用以促学用以促学An Introduction to Database System2.7 多值依赖多值依赖用下图表示这种对应：用下图表示这种对应：Wi学以致用学以致用 用以促学用以促学An Introduction to Database System2.7 多值依赖多值依赖 性质性质学以致用学以致用 用以促学用以促学An Introduction to

44、 Database System2.7 多值依赖多值依赖 与函数依赖的区别与函数依赖的区别学以致用学以致用 用以促学用以促学An Introduction to Database System2.2.规范化规范化 2.1 函数依赖函数依赖 2.2 码码 2.3 范式范式 2.4 2NF 2.5 3NF 2.6 BCNF 2.7 多值依赖多值依赖 2.8 4NF学以致用学以致用 用以促学用以促学An Introduction to Database System2.8 4NF学以致用学以致用 用以促学用以促学An Introduction to Database System2.8 4NF学以致

45、用学以致用 用以促学用以促学An Introduction to Database System规范化小结规范化小结v 关系数据库的规范化理论是数据库逻辑设计的工具关系数据库的规范化理论是数据库逻辑设计的工具v 目的：目的：尽量消除插入、删除异常，修改复杂，数据冗余v 基本思想：基本思想：逐步消除数据依赖中不合适的部分v实质：实质：概念的单一化学以致用学以致用 用以促学用以促学An Introduction to Database System规范化小结规范化小结v 关系模式规范化的基本关系模式规范化的基本步骤步骤 1NF 消除非主属性对码的部分函数依赖消除决定属性 2NF集非码的非平 消除非

46、主属性对码的传递函数依赖凡函数依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NF学以致用学以致用 用以促学用以促学An Introduction to Database System规范化小结规范化小结v 不能说规范化程度越高的关系模式就越好v 在设计数据库模式结构时，必须对现实世界的实际情况 和用户应用需求作进一步分析，确定一个合适的、能够反 映现实世界的模式v 上面的规范化步骤可以在其中任何一步终止学以致用学以致用 用以促学用以促学An Introduction to Database System第六讲第六讲 关系数据理论关系数据理论 1

47、. 问题问题的提出的提出 2. 规范化规范化 3. 数据依赖数据依赖的公理系统的公理系统 4. 模式模式的分解的分解学以致用学以致用 用以促学用以促学An Introduction to Database Systemn 一个关系模式可能有多个函数依赖形成函数依赖集，现在有一个新的函数依赖不在函数依赖集里，但能从集合里根据一定的规则推导出来，就说那个集合逻辑蕴涵这个新的函数依赖。n 举例举例: : XZ并不是显式地表现出来，而是从XY 和YZ推出的，这可以表示为 XY, YZ蕴含XZn 如果一个函数依赖能够由集合中的其他函数推出，则该函数依赖是多余的。函数依赖中需要解决的问题：从一些已知的函数

48、依赖去判断另外一些函数依赖是否成立。3.1 3.1 逻辑逻辑蕴含蕴含学以致用学以致用 用以促学用以促学An Introduction to Database System3.1 逻辑蕴含v逻辑蕴含逻辑蕴含 定义定义: : 对于满足一组函数依赖 F 的关系模式R ，其任何一个关系 r，若函数依赖 XY 都成立, （即 r 中任意两元组t，s，若tX=sX，则tY=sY），则称 F 逻辑蕴含 XY.学以致用学以致用 用以促学用以促学An Introduction to Database System3.2 3.2 ArmstrongArmstrong公理系统公理系统关系模式关系模式R 来说有以下的

49、推理规则：来说有以下的推理规则： A1. 自反律自反律（Reflexivity）：）：若Y X U，则X Y 为F所蕴含。 A2. 增广律增广律（Augmentation）：）：若XY 为F所蕴含，且Z U，则 X U ZY U Z为F所蕴含。 A3. 传递律传递律（Transitivity）：）：若 XY 及YZ 为F所蕴含，则XZ 为F所 蕴含。学以致用学以致用 用以促学用以促学An Introduction to Database System3.2 3.2 “ArmstrongArmstrong推理规则是正确推理规则是正确的的”（1）自反律自反律: 若Y X U，则X Y为F所蕴含 证

50、证: 设Y X U 对R 的任一关系r中的任意两个元组t，s： 若t X = s X ，由于Y X，有t y =s y ，所以XY成立，自反律得证学以致用学以致用 用以促学用以促学An Introduction to Database System(2) 增广律增广律: 若XY为F所蕴含，且Z U，则X UZY UZ 为F所蕴含。 证：证：设XY为F所蕴含，且Z U。 设R 的任一关系r中任意的两个元组t，s： 若t X U Z =s X U Z，则有t X =s X 和t Z =s Z ； 由XY，于是有t Y =sY ，所以tY U Z=sY U Z，所以 X U ZY U Z为 F 所蕴

51、含，增广律得证。3.2 3.2 “ArmstrongArmstrong推理规则是正确推理规则是正确的的”学以致用学以致用 用以促学用以促学An Introduction to Database System(3) 传递律：传递律：若XY及YZ为F所蕴含，则 XZ 为 F所蕴含。证：证：设 XY 及 YZ 为 F 所蕴含对R 的任一关系 r中的任意两个元组 t，s：若t X =s X ，由于XY，有 t Y =sY ；再由YZ，有t Z =s Z ，所以XZ为F所蕴含，传递律得证。3.2 3.2 “ArmstrongArmstrong推理规则是正确推理规则是正确的的”学以致用学以致用 用以促学用

52、以促学An Introduction to Database System3.3 Armstron公理公理推论推论1. 根据根据A1，A2，A3这三条推理规则可以得到下面这三条推理规则可以得到下面三条推理规则：三条推理规则： 合并规则：合并规则：由XY，XZ，有XY U Z。 （A2， A3） 伪传递规则伪传递规则：由XY，W U YZ，有X U WZ。 （A2， A3） 分解规则：分解规则：由XY及 ZY，有XZ。 （A1， A3）学以致用学以致用 用以促学用以促学An Introduction to Database System2. 根据合并规则和分解规则，可得引理根据合并规则和分解规则

53、，可得引理 引理引理1 : XA1 A2Ak 成立的充分必要条件是 XAi 成立（i=l，2，k）3.3 Armstron公理公理推论推论学以致用学以致用 用以促学用以促学An Introduction to Database System3.3 Armstron公理公理推论推论 【定义定义】在关系模式R中为F所蕴涵的函数依赖的全体叫做F的闭包，记为F+ Armstrong公理系统是有效的、完备的公理系统是有效的、完备的 【有效性有效性】由F出发根据Armstrong公理推导出来的每一个函数依赖一定在 F+中； 【完备性完备性】F+中的每一个函数依赖，必定可以由 F 出发根据Armstrong

54、公理推导出来 学以致用学以致用 用以促学用以促学An Introduction to Database SystemF的闭包的闭包学以致用学以致用 用以促学用以促学An Introduction to Database System函数依赖闭包函数依赖闭包【定义】【定义】 设 F 为属性集 U 上的一组函数依赖，X U， XF+ = A| XA 能由F 根据Armstrong公理导出，XF+ 称为属性集 X 关于函数依赖集 F 的闭包.学以致用学以致用 用以促学用以促学An Introduction to Database System关于闭包的引理关于闭包的引理v 【引理】【引理】 设F为属

55、性集U上的一组函数依赖，X，Y U，XY能 由F 根据Armstrong公理导出的充分必要条件是Y XF+v 用途用途 将判定XY是否能由F根据Armstrong公理导出的问题，转化为求出XF+ 、判定Y是否为XF+的子集的问题。学以致用学以致用 用以促学用以促学An Introduction to Database System求闭包的算法求闭包的算法算法：算法： 求属性集X（X U）关于U上的函数依赖集F 的闭包XF+ 输入输入：X，F输出输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，这里B = A |( V)( W)(VWFV X（i）A W)；（3）X（i+1）=BX（i）

56、 （4）判断X（i+1）= X （i）吗?（5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。（6）若否，则 i=i+l，返回第（2）步。 对于该算法， 令ai =|X（i）|，ai 形成一个步长大于1的严格递增的序列，序列的上界是 | U |，因此该算法最多 |U| - |X| 次循环就会终止。学以致用学以致用 用以促学用以促学An Introduction to Database System函数依赖闭包函数依赖闭包【例例】已知关系模式R，其中 U=A，B，C，D，E； F=ABC，BD，CE，ECB，ACB。 求（AB）F+ 。 解解： 设 X（0）=AB； (1) X（

57、1）=ABCD=ABCD。 (2) X（0） X（1） X（2）=X（1）BE=ABCDE。 (3) X（2）=U，算法终止 （AB）F+ =ABCDE。学以致用学以致用 用以促学用以促学An Introduction to Database System函数依赖集等价函数依赖集等价【定义定义】 如果 G+ = F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。【引理引理】 F+ = G+ 的充分必要条件是F G+ ，和G F+ 证: 必要性显然，只证充分性。（1）若FG+ ，则XF+ XG+ 。（2）任取XYF+ 则有 Y XF+ XG+ 。 所以XY (G+）+=

58、 G+。即F+ G+。（3）同理可证G+ F+ ，所以F+ = G+。学以致用学以致用 用以促学用以促学An Introduction to Database System最小依赖集最小依赖集【定义定义】如果如果函数依赖函数依赖集集 F 满足满足下列条件，则下列条件，则称称 F 为为一个极小函一个极小函数依赖集。亦称为最小依赖集或最小覆盖。数依赖集。亦称为最小依赖集或最小覆盖。 （1） F 中任一函数依赖的右部仅含有一个属性。 （2）F中不存在这样的函数依赖XA，使得F与F- XA等价。 （3）F中不存在这样的函数依赖XA， X 有真子集 Z 使得 F- XA ZA 与F等价。 学以致用学以致

59、用 用以促学用以促学An Introduction to Database System最小依赖集最小依赖集【例例】关系模式关系模式S，其中：，其中： U= Sno，Sdept，Mname，Cno，Grade ， F= SnoSdept，SdeptMname，(Sno，Cno)Grade 设F =SnoSdept，SnoMname，SdeptMname， (Sno，Cno)Grade，(Sno，Sdept)Sdept F 是最小覆盖，而F 不是。 因为：F - SnoMname与F 等价 F - (Sno，Sdept)Sdept也与F 等价 学以致用学以致用 用以促学用以促学An Introd

60、uction to Database System极小化过程极小化过程【定理定理】 每一个函数依赖每一个函数依赖集集 F 均均等价于一个极小函数等价于一个极小函数依依 赖集赖集 Fm ， Fm 称为称为 F 的的最小依赖集。最小依赖集。 证明证明: 构造性证明，找出 F 的一个最小依赖集。 学以致用学以致用 用以促学用以促学An Introduction to Database System极小化过程极小化过程学以致用学以致用 用以促学用以促学An Introduction to Database System极小化过程极小化过程【例】 F = AB，BA，BC，AC，CAFm1、Fm2都是