关系数据库设计理论.ppt

《关系数据库设计理论.ppt》由会员分享，可在线阅读，更多相关《关系数据库设计理论.ppt（87页珍藏版）》请在三一文库上搜索。

1、第五章 关系数据库设计理论,关系数据库设计理论是关系数据库的指南，也是关系 数据库的理论基础。它是数据库领域的专家和学者们总结 数据库设计中的经验教训的基础上，借助近代数学工具而 提出来的。它把抽象的数学理论和具体的实际问题结合起 来，为数据库领域的发展起到了推动作用。,意义： 提供分析和判断数据库模式好坏的准则； 指导设计好的数据库模式。 地位： 本章是本书最难的部分之一，但对于应用设计十分有用,5.1 问题的提出什么是不好的数据库设计,实际问题，假定在设计数据库时出现如下的关系模式： Student(Sno, Sname, Dept，Cno, Grade) 学生（学号，姓名，院系，课程号，

2、成绩）,上述的关系模式在实际应用中会出现什么样的问题呢？ 1、数据存在冗余 该关系模式中，学生每选一门课，他的名字和院系就 要重复存放一次。而且，如果他的院系改变的话，那么对 于其的每一个元组的院系都要改变。这样不仅增添了更新 代价，而且还有可能出现一个人在不同院系的情况。,2、插入（删除）异常 该关系模式的主键应该是由学生学号和课程号共同构 成。按照常理，新学生登记注册，应该在学生信息库里存 在他的资料，但如果此时他还未选课，那么关于这个学生 的信息就不能创建，这是违背现实的情况的。,3、更新复杂 如果某个学生转换所在系，那么和他所有的相关的记录 都必须进行修改。而且，容易造成潜在的数据不一

3、致的问题。 比如李平的记录，可能会只修改了其中一部分元组。,结论： Student关系模式不是一个好的模式。 “好”的模式： 不会发生插入异常、删除异常、更新异常， 数据冗余应尽可能少。 原因：由存在于模式中的某些数据依赖引起的 解决方法：通过分解关系模式来消除其中不合适 的数据依赖。,由此可见，一个关系模式如果设计的不合理，将会造成很多 问题。如果我们将上述的关系模式进行分解： Student(Sno, Sname，Dept) SC(Sno, Cno, Grade) 分解以后可以解决上述的问题。但是上述关系模式在有些情 况下也不是最优的。具体的关系模式的设计不仅要结合数据 库设计理论，也还要

4、根据实际的应用来决策。,关系模式的形式化定义,关系模式由五部分组成，即它是一个五元组： R(U, D, DOM, F) R： 关系名 U： 组成该关系的属性名集合 D： 属性组U中属性所来自的域 DOM： 属性向域的映象集合 F： 属性间数据的依赖关系集合,什么是数据依赖,1.完整性约束的表现形式 限定属性取值范围：例如学生成绩必须在0-100之间 定义属性值间的相互关连（主要体现于值的相等与否），这就是数据依赖，它是数据库模式设计的关键 2. 数据依赖 是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系 是现实世界属性间相互联系的抽象 是数据内在的性质 是语义的体现,3. 数据依赖

5、的类型 函数依赖（Functional Dependency，简记为FD） 多值依赖（Multivalued Dependency，简记为MVD） 其他,5.2 规范化理论,规范化理论正是用来改造关系模式，通过分解关系模式来消 除其中不合适的数据依赖，以解决插入异常、删除异常、更新异 常和数据冗余问题。,函数依赖,一、属性间的联系 客观世界中的事物是彼此联系，相互制约的。这种联 系分为两类：一类是实体与实体之间的联系；另一类是实 体内部各属性之间的联系。,属性之间的联系分为三类： 1、11：例如果学生关系模式中没有同名现象，则学号和 姓名两个属性之间的关系是一对一的关系。 2、1M：例一个院系

6、有多个人，但是单个人只能属于一个 院系，那么院系和人的学号之间的关系是一对多的。 3、MN：一个课程号对应于多个学号，一个学号对应于多 个课程号，这两个属性之间是多对多的联系。,二、函数依赖的定义 定义：设有关系模式R(U)，X和Y是属性集U的子集，r是R 上的任一具体关系，u和v是r中的任意两个元组。如果由 uX=vX能推导出uY=vY，则称X函数决定Y，或Y函 数依赖于X，记为,例：有一个学习模式 R(S#,SNAME,C#,GRADE,TNAME,TAGE) 现在规定，每个学号只对应一个具体学生，每个课程号只 由一个教师来教，写出函数依赖。,三、属性间的联系和函数依赖 属性间的联系有三种

7、，但并不是每一种关系中都存在函数 依赖，设有属性集X、Y属于关系模式R， 如果X和Y之间是11关系，则存在函数依赖：,如果X和Y之间是1M关系，则存在函数依赖：,如果X和Y之间是NM关系，则：,X和Y之间不存在函数依赖,例：如果人名唯一的话，那么一个人名对应一个学号，则有,例：院系和学号之间的联系是一对多的，那么存在的FD为,四、FD的逻辑蕴涵,定义：设F是在关系模式R上成立的函数依赖集， 是一个FD。如果对于R的每个满足F的关系也满足 , 则称F逻辑蕴涵 ，记为 定义：被F逻辑蕴涵的函数依赖的全体构成的集合，称为 函数依赖集的闭包，记为F+。,五、FD的推理规则,从已知的FD集推导未知的FD

8、，可以使用的推导规则 （Armstrong） 设有关系模式R（U），X、Y、Z是U的子集： A1(自反性)：如果 ，则有 在R上成立。 A2(增广性)：如果 在R上成立，那么有 A3(传递性)：如果 在R上成立，则有,证明Armstrong公理，用FD定义：,A1：设u,v是r中的任意两个元组，如果uX=vX，则u,v 中的X的任意子集也必然相等，由条件中uY=vY，根据 函数依赖的定义，可以得到,A2：设u,v是r中的任意两个元组，设uXZ=vXZ，即 uXuZ=vXvZ，则uX=vX,uZ=vZ，由条件 根据函数依赖定义有uY=vY,则uYZ=uYuZ= vYvZ=vYZ这样在uXZ=vX

9、Z的基础上推出了 uYZ=vYZ，得证。,A3：设u,v是r中的任意两个元组，对于uX=vX， 因为 ，则有uY=vY，又因为 则根据定 义可以得出uZ=vZ，因此得到,例题：已知关系R(X,Y,Z)以及其上的函数依赖集F，求F+。,FD的分类：,1、对于FD： ，如果 ，则称为“平凡的FD” 2、对于FD： ，如果 ，则称为“非平凡的FD” 3、对于FD： ，如果 则为“完全非平凡的FD”,Armstrong的推论：,1、合并规则： 2、分解规则： 3、伪传递规则：,合并规则：,分解规则：,伪传递规则：,* 用函数依赖定义键,超键：能唯一标识元组的属性集称为关系模式的超键。 候选键：如果一个

10、属性集能唯一标识元组，且不含有多 余的属性，那么这个属性集成为候选键。 定义：如果关系模式R的属性集为A1,A2,An，F是R上成立 的一个FD集，X是A1,A2,An的一个子集，如果XA1,A2, An在F+中，那么称X是R的一个超键。如果XA1,A2,An 在F+中，且对于X的任何一个真子集X1， X1A1,A2,An 在都不在F+中，则称X是R的一个候选键。,属性集的闭包,定义：设F是属性集U上的FD集，X是U的子集，那么属性集 X的闭包X+，它是一个从F集使用FD推导规则推出的所有满 足XA的属性集A的集合：,定理：XY能用FD推理规则推出的充分必要条件是 证明：(充分性)根据 ，设Y

11、=A1,A2,An。由属性集 闭包定义可知：XAi在F+中。再根据合并规则，XA1, A2,An 即XY。 (必要性)由XY，根据分解规则，XAi，根据属性集闭 包定义可得 ，所以 ，即,*用属性集的闭包来定义候选键,定义：如果关系模式R的属性集为U，F是R上成立的一个 FD集，X是U的一个子集，如果X的属性集的闭包X+ =U,则 称X为R的一个超键，如果对于X的任何一个真子集Y， 有Y+U。则X为R的一个候选键。,算法：求属性集X关于FD集F的闭包X+ 输入：属性集U，U上的FD集F，X是U的子集 输出：X关于F的闭包X 方法： Result:=X; repeat for F 中的每个FD

12、YZ do if then Result:=Result U Z; until (result 没有改变)； Result 即为所求的X+,例：属性集U为ABCD，FD集为 , 求A+,AD+ A+ (1) Result=A (2) Result=A U B =AB (3) Result=AB U C =ABC,AD+ = ABCD,例题：,求BD+,1) result=BD, AB不含于result，result=BD 2) result=BD，D包含于result,result =BD U EG=BDEG 3) result=BDEG，C不含于result,result=BDEG 4) r

13、esult=BDEG，BE包含于result,result =BDEG U C=BCDEG 5) result=BCDEG,BC包含于result,result=BCDEG U D=BCDEG 6) result=BCDEG,CG包含于result,result=BCDEG U BD=BCDEG 7) result=BCDEG,ACD不含于result,result=BCDEG 8) result=BCDEG,CE 含于result,result=BCDEGUAG=ABCDEG,* 快速求解候选键的充分条件,对于给定的关系模式R=(A1,A2,An)和函数依赖集F， 可将其属性分为四类： 1、

14、仅仅出现在F的函数依赖左部的属性L类； 2、仅仅出现在F的函数依赖右部的属性R类； 3、在F的函数依赖的左右两边都没有出现的属性N类； 4、在F的函数依赖的左右两边都出现的属性LR类；,定理：对于给定关系模式R及其函数依赖集F(不包含平凡FD) 1) X是L类属性，则X必为R的任何一个候选键的成员。 2) X是R类属性，则X不包含在任何候选键中。 3) X是R的N类属性，则X也必为R的任何一个候选键的成员。 4) X是R的LR类属性，则X可能是也可能不是候选键的成员。,1) 反证法：设W为R的任一候选键，X不是W的成员。由于 X仅仅出现在F的函数依赖左部，所以R中没有其它属性能 够函数决定X，

15、这样W+中就不可能包含X，这样就与W是R的 候选键相矛盾。所以X必然是候选键W的成员。 （X为L类的情况）,2) 反证法：设W是R的任一候选键，X不是W的成员。由于X 没有出现在F中，那么R中没有其它属性能够函数决定X。 这样W+中就不可能包含X，这与W是R的候选键相矛盾。所以 X必然是候选键W的成员。 （X是N类的情况）,例：设有关系模式R(A,B,C,D)，其函数依赖集F如下， 求R的候选键。,传统步骤：1、分别求A/B/C/D/AB/AC/AD/BC/BD/CD ABC/ABD/ACD/BCD/ABCD的属性集的 闭包。 2、根据候选键定义找出候选键。,快速步骤： 1、L类L类:A,C

16、LR类: B,D (AC)+=ABCD 所以AC是关系模式R的唯一候选键。,求解候选键的步骤 1、根据关系模式上成立的FD集确定属性的类型。 2、根据属性类型求属性集的闭包。 3、满足候选键定义条件的即为所求的候选键。注意有些 情况下候选键不是唯一的。,例：设有关系模式R(A,B,C,D)，F是R上成立的FD集，试写 出R的所有候选键。,解答：分析R的属性类型： 求解属性集闭包：,*练习,1、给定关系模式R (ABCDEG)，R上成立的FD集,求D+,C+,A+,CD+,AD+,AC+,ACD+ 求出R的所有候选键,解： D(DG) C+=(ABC) A+ =(AB) (AD)+=(ABDG)

17、 (AC)+=(ABC) (ACD)+=(ABCDEG) 首先确定关系R的属性类型 L类：C,D ；LR类：A ；R类：B,E,G (CD)+=(ABCDEG)，所以R的候选键是CD。,2、设关系模式R(ABCD)上的函数依赖集为F，并且, 求R的所有候选键。 求R的所有不是候选键的超键。, L类：B ；LR类：A,C,D (B)+=(B)，(AB)+=(ABCD)； (BC)+=(ABCD)；(BD)+=(ABCD),所有不是候选键的超键 ABC, ABD, BCD, ABCD,规范化,关系必须是规范化的。通常按属性间依赖情况，来区 分关系规范化的程度为第一范式，第二范式，第三范式等。,术语

18、和记号：,定义：在关系R(U)中，如果 ，并且对于X的任何一个 真子集X都有 ，则称Y对X完全函数依赖。 定义：如果 ，但Y不完全函数依赖于X，则称Y对X部 分函数依赖。 定义：在R(U)中，如果 , ，则 称Z对X传递函数依赖。 定义：包含在任何一个候选键中的属性，叫做主属性。不包 含在任何候选键中的属性称为非主属性。,范式,关系数据库中的关系是要满足一定的要求的。满足不 同的要求称为不同的范式。满足最低要求的称为第一范式， 简称1NF。在第一范式中满足进一步的要求的称为第二范 式，其余以此类推。 对于各种范式之间的联系有：,对某一关系模式R，它属于第几范式，记为,1NF定义：如果一个关系模

19、式R的每个具体关系r的每个 属性值都是不可再分的最小数据单位，称R满足1NF，r为 1NF关系。,1NF,2NF,定义：若 ，且R的每一个非主属性完全函数依 赖于任一候选键，称R是满足第二范式的关系模式。 例：设有关系模式SLC(Sno, Dept, Dom, Cno, Grade) 其中Dom为宿舍楼，并规定一个系的同学住在同一栋楼。 写出关系模式中存在的函数依赖，求候选键。判定该关 系模式是否是2NF。,解：存在的函数依赖有：,L类：Sno,Cno ；LR类：Dept ；R类：Dom,Grade 而且(Sno,Cno)+=(Sno,Cno,Dept,Dom,Grade)， 所以Sno,Cn

20、o为候选键。,主属性：Sno, Cno 非主属性：Dept, Dom, Grade 因为 所以Dom和Dept都不完全函 数依赖于候选键(Sno,Cno)，所以R不满足2NF定义，最高 只达到1NF。,*那么不满足2NF的关系模式可能产生的问题： 1、插入异常：如果某学生未选课，该学生的信息记录就不 能被创建，因为缺少主键的Cno这一部分值。 2、删除异常：如果某个要删除某个学生的选课信息，必然 会将其固有信息即院系和宿舍楼信息删除，造成删除异常。 3、修改复杂。假如某个学生需要转系，本只需要修改Dept 分量的值，但由于Dom值依赖于Dept，所以Dom的值也要修 改，而且该学生选多少们课就

21、要修改多少条记录。 4、存储冗余，对每一次的选课都要存储学生其他信息。,将上述模式分解为：SC(Sno, Cno, Grade) SD(Sno, Dept, Dom),SC中的FD,SD中的FD,分解为满足2NF的多个关系模式后，得到的新的关系模式 如果不满足3NF，仍然可能存在问题，： 这里分解得到的SD中存在下列问题 1、数据有冗余：每个系的学生都住在同一个地方，但是 系的信息将会重复出现，重复次数相当于学生的人数。 2、插入异常：如果某个系刚刚成立，还未有学生注册， 那么该系的信息无法插入该系的信息入库。,3、删除异常：如果某个系的学生都毕业了，在删除该系的 学生信息的时候，会将该系的信

22、息删除掉。 4、修改复杂：当学校调整学生宿舍时，把外语系的学生全 部迁到另外一栋楼，那么需要修改的记录是该系的所有学生 因此满足2NF的关系模式在某些情况下仍然不是最好的。,3NF,定义：关系模式R(U)满足2NF，且它的任何一个非主属性都 不传递依赖于任何候选键，则称R为满足3NF的关系模式。,上述的SC中没有第三方属性，所以不存在传递函数依赖， 但是在SD中，Dom通过Dept传递函数依赖于Sno，所以SC满 足3NF，而SD不满足3NF。,Dom Sno,解决方法：分解SD为以下两个 SD(Sno, Dept) DD(Dept, Dom) 分解以后的两个关系模式都满足3NF。,一个满足3

23、NF的关系模式也不一定是最好的，例如在关系 模式STJ( S,T,J )中，S表示学生，T表示教师，J表示课 程。假设每一个教师只教一门课。但是每门课由若干教师 教，某一学生选定某门课，就确定了一个固定的教师，于 是存在的函数依赖如下:,根据函数依赖可以求出该STJ的候选键为(S,J)或者(S,T)， 此时的关系模式中的所有属性是主属性，则关系模式满足 3NF。但是该关系模式在有时仍然存在一些问题： 1、插入异常：如果某个老师开设了某门课，但是没人选， 则有关信息无法存入数据库。 2、删除异常：选了某门课程的学生全部毕业，该信息丢失 3、数据冗余大：老师信息根据选课的学生人数要存储多次 4、修

24、改复杂：教师所授课程改名后，所有选该课的记录都 要改。,BCNF,定义：关系模式 ，F是关系模式R的函数依赖 集，如果F中所有函数依赖的左部都包含了R的任何一个候 选键，称R是满足Boyce-Codd范式，记为BCNF。即每一个 决定因素都包含候选键。,定理：一个BCNF范式必是3NF。 证明：反证法。设R是一个BCNF但不是3NF。则必存在非主 属性A候选键X以及属性集Y，使得XY,YA,且 , 那么Y不可能包含R的候选键X 。因为如果X包含于Y中，根 据自反性，可得YX。但是由于Y在这里是决定因素，根 据定义这里的条件R就不是BCNF。这和假设相矛盾，从而 定理得证。但是满足3NF不一定满

25、足BCNF。,练习,1、设有关系模式R(X,Y,Z)，其上的函数依赖集如下，判定 R最高满足第几范式。,解：首先根据函数依赖求候选键： L类：X；LR类：Y,Z； 且(XY)+=(XYZ) ,(XZ)+=(XYZ)， 所以R的候选键为XY和XZ。没有非主属性，所以R满足3NF， 但R不是BCNF，因为决定因素Y中不包含候选键。,2、判断下列说法是否正确： （1）任何一个包含两个属性的关系模式一定满足3NF。 （2）任何一个包含两个属性的关系模式一定满足BCNF。 （3）任何一个包含三个属性的关系模式一定满足3NF。 （4）任何一个关系模式一定有键。,解答： 设有二元关系R(X,Y)，则X和Y之

26、间的函数依赖可能如下： 1) , ,则关系模式的候选键为X。没有第三方 属性传递函数依赖，所以R满足3NF，而且决定因素包含候 选键，R满足BCNF。 2) ,则关系模式的候选键为X和Y。没有第三 方属性传递函数依赖，而且决定因素包含候选键，R满足 BCNF。,3)X和Y之间不存在函数依赖，则关系模式的候选键是XY。 这个时候R也是满足BCNF，因为此时不存在推翻R不是BCNF 的条件。包含三个属性的关系模式不一定是3NF，如上面提 到的SD关系模式中Dom传递函数依赖于Sno。 关系模式一定有键，这是关系模式的固有属性。 所以只有第三种说法不正确。,假设某商业集团数据库有一关系模式R如下：

27、R（商店编号，商品编号，数量，部门编号，负责人） 现规定：1、每个商店的每种商品只在一个部门销售。 2、每个商店的每个部门只有一个负责人。 3、每个商店的每种商品只有一个库存数量。 回答下列问题：1、写出R的基本函数依赖 2、找出关系模式R的候选键 3、关系模式R最高达到第几范式？为什么,分析关系模式,分析：关系R存在的函数依赖有：,利用函数依赖求候选键： L类属性：商店编号，商品编号； LR类： 部门编号； R类： 负责人 数量。而且（商店编号，商品编号）U，所以关系模式 R的候选键为（商店编号，商品编号）。,判断R属于第几范式： 非主属性为：部门编号，负责人，数量。它们对候选键都 是完全函

28、数依赖关系，所以R是满足第二范式的。但是，,所以非主属性负责人对候选键传递依赖，那么R不满足第 三范式，因此R最高满足第二范式。,证明：,（1）,（2）,函数依赖集的规范覆盖,定义：关系模式R(U)上的两个FD集F和G，如果满足F+=G+， 则称F和G是等价的。 定理：F+=G+的充分必要条件是 即F和G等价的条件是,函数依赖集的最小集,如何求出给定函数依赖集F的最小集： 1、逐一检查F中的函数依赖，如果函数依赖的右部不是单 个属性，利用分解规则将其分解为多个函数依赖，得到新 的函数依赖集F 2、对于F中的每个FD:XA，令G=F-XA，若 则从F中去掉此函数依赖，得到F”。 3、对于F”中的

29、每个FD:XA，设X=B1B2Bm，对于Bi，如果 ，用XBi代替X。,证明：经过以上步骤后所得的函数依赖集和F等价。 1、分解规则是Armstrong公理的推论，所以F与F等价。 2、现要证明的是当 ，G与F等价。,3、去掉F中各函数依赖左部的多余属性。检查F中左部非 单属性的函数依赖。例如XYA，现要判断Y是否为多余属 性，即能否用XA代替XYA（能代替的条件是 ） 现要证明的是当代替条件成立时，代替后所得的G和F”等价。,例3：求F的最小依赖集,1、分解函数依赖右部，这里不需要 2、消除多余的函数依赖,3、消除函数依赖左部多余属性，这里不需要,练习：求最小依赖集,1、分解各函数的右部为单个属性，得到：,2、去掉多余的函数依赖,2、去掉函数依赖左部的多余属性,