ch关系数据库的规范化设计(包括作业)

1、1第第4章章 关系数据库的规范化设计关系数据库的规范化设计n关系数据库的规范化设计是指面对一个现实问题，如何选择一个比较好的关系模式集合。n规范化设计理论涉及的内容包括：函数依赖、范式、模式的分解特性。n函数依赖研究不同属性之间的依赖联系；范式是一个好的关系模式应该遵循的标准；模式的分解特性是指对关系模式进行分解以符合某种范式时，在分解过程中应保持的特性。（不是定义）n规范化设计理论对关系数据库结构的设计起到重要的作用。2第第4章章 关系数据库的规范化设计关系数据库的规范化设计 4.1 关系模式的问题 4.2 函数依赖 4.3 关系模式的分解特性 4.4 关系模式的范式 小结34.1 关系模式

2、的问题关系模式的问题n关系模式：对关系（表）的描述，由关系名关系名+属性集属性集（表名表名+表头表头）组成。n关系模式的问题：数据冗余 数据冗余数据冗余是指一个数据在多个元组中重复出现（重复存储）。 数据冗余导致的问题是操作异常操作异常，即修改异常、插入异常、删除异常。【例】设一个关系模式R(S#, C#, Grade, TName, TAddr)，其中的属性分别表示学生学号，选修课程的课程号，成绩，任课教师姓名，教师办公地址。 并规定： 每个学生每学一门课只有一个成绩， 每门课程只有一个任课教师， 每个教师只有一个办公地址。 则该关系模式的主键为(S#, C#)。44.1 关系模式的问题（续

3、关系模式的问题（续1）【例】关系模式R(S#, C#, Grade, TName, TAddr)的实例：存在的问题：n数据冗余(data redundancy)：每个教师的地址重复存储。由于数据冗余带来的操作异常问题：n修改异常(update anomalies)：更改某教师地址时，必须修改与该教师有关的每一个元组；否则，将造成该教师地址的异常。C-178陈 刚85C2S3D-346吕 宋70C3S2C-529金 谦90C1S2D-346吕 宋82C3S1C-178陈 刚70C2S1C-529金 谦80C1S1TAddrTNameGradeC#S#54.1 关系模式的问题（续关系模式的问题（续

4、2）由于数据冗余带来的操作异常问题：n插入异常(insertion anomalies)：若一个教师刚调来，尚未分配教学任务，则无法将该教师姓名与办公地址存入该关系模式中（因为主键为S#和C#，不能为空），导致该插的数据插不进去。n删除异常(deletion anomalies)：若一个学生已毕业，则在删除该学生选课信息的同时，将把任课教师的地址也删掉，导致不该删除的数据被删掉。n关系模式数据冗余问题的根源n表面原因：把太多的信息放在同一个关系模式中。n实质根源（以前例进行分析）64.1 关系模式的问题（续关系模式的问题（续3）n关系模式数据冗余问题的根源n实质根源分析实质根源分析 【例】设一

5、个关系模式R(S#, C#, Grade, TName, TAddr)；并规定： 每个学生每学一门课只有一个成绩； 每门课程只有一个任课教师； 每个教师只有一个办公地址；则该关系模式的主键为(S#, C#)。 实质根源与这三个规定有关；但不是说这三个规定不对；而是在这三个规定之下，该关系模式R(S#, C#, Grade, TName, TAddr)是一个不好的关系模式（表现为数据异常、操作异常）。 用形式化方法（不用该模式的一个具体表）分析为什么“在这三个规定之下，该关系模式是一个不好的关系模式”？ 给出这3个规定的数学表示（函数依赖）：74.1 关系模式的问题（续关系模式的问题（续4）n关

6、系模式数据冗余问题的根源n实质根源分析实质根源分析 每个学生每学一门课只有一个成绩：(S#, C#) Grade 每门课程只有一个任课教师：C# TName 每个教师只有一个办公地址：TName TAddr 主键与其他属性（称为非主属性）之间的函数依赖形式：(S#, C#) (Grade, TName, TAddr) 该函数依赖即说明为什么关系模式R(S#, C#, Grade, TName, TAddr)的主键为(S#, C#)。 实质根源与这四个函数依赖有关，采用图示方法表示主键与非主属性之间的函数依赖。84.1 关系模式的问题（续关系模式的问题（续5）n关系模式数据冗余问题的根源(S#,

7、 C#) (Grade, TName, TAddr)S#C#GradeTNameTAddrS#C#GradeTNameTAddr (S#, C#) Grade C# TName TName TAddrS#C#GradeTNameTAddr94.1 关系模式的问题（续关系模式的问题（续6）n关系模式数据冗余问题的根源n实质根源实质根源 (1) 在一个关系模式中，当存在非主属性对主键的部分依赖时，就会产生数据冗余和操作异常。 (2) 在一个关系模式中，当存在非主属性对主键的传递依赖时，就会产生数据冗余和操作异常。n关系模式数据冗余问题的解决途径 分解是解决数据冗余的主要途径。如前例的关系模式可分解

8、为三个关系模式R1(S#, C#, Grade)，R2(C#, TName)，R3(TName, TAddr)。 (S#, C#) Grade C# TName TName TAddrS#C#GradeTNameTAddr104.1 关系模式的问题（续关系模式的问题（续7）n关系模式数据冗余问题的解决途径 规范化设计理论规范化设计理论就是通过分解不好的关系模式来消除某些函数依赖的影响，从而得到好的关系模式，以解决数据冗余和修改异常、插入异常、删除异常问题。 衡量关系模式好坏的标准就是范式。n本章的符号规定n用英文字母表首部的大写字母A, B, C, 表示单个属性。n用英文字母表尾部的大写字母

9、, U, V, W, X, Y, Z表示属性集。n大写字母 R 表示关系模式，小写字母 r 表示其关系。n另外，关系模式R(A, B, C)简记为R(ABC)；属性集X和Y的并集XY简记为XY。114.2 函数依赖函数依赖 4.2.1 函数依赖的定义 4.2.2 FD的逻辑蕴涵 4.2.3 FD的推理规则 4.2.4 FD和关键码的联系 4.2.5 属性集的闭包 4.2.6 FD集的最小依赖集（教材4.2.7）124.2.1 函数依赖的定义函数依赖的定义n定义4.1 设有关系模式R(U)，X和Y是属性集U的子集，函数函数依赖依赖（Functional Dependency，简记为FD）是形为X

10、Y的一个命题，只要 r 是 R 的关系，对 r 中任意两个元组 t 和s，都有tX=sX蕴涵tY=sY，那么称FD XY在关系模式R(U)中成立。（“蕴涵”可理解为“必定有”）n定义的理解：定义的理解：若在关系模式R(U)上FD XY成立，则表明在关系模式R的任意一个关系 r 中，任意找两个元组，若在属性集X上的值相同，则在属性集Y的值必相同。 或者说：若在关系模式R(U)上FD XY成立，则表明在关系模式R的任意一个关系 r 中，不可能存在两个元组在属性集X上的值相同，而在属性集Y上的值不相同。nFD XY可读作“X函数决定Y”或“Y函数依赖于X”。4.2 函数依赖134.2.1 函数依赖的

11、定义（续函数依赖的定义（续1）【例4.2】设有关系模式R(A, B, C, D)，并有如下所示的两个关系： 则在关系模式R上，FD AB不成立。【例4.4】设关系模式R(ABCD)，属性之间有这样的联系：A与B是一对多联系（即每个A值有多个B值与之联系，而每个B值只有一个A值与之联系），C与D是一对一联系（即每个C值只有一个D值与之联系，每个D值也只有一个C值与之联系）。试根据这些规则写出相应的函数依赖。4.2 函数依赖r1d4c4b1a3d3c3b2a2d2c2b1a1d1c1b1a1DCBAr2d4c4b1a3d3c3b2a2d2c2b2a1d1c1b1a1DCBA144.2.1 函数依赖

12、的定义（续函数依赖的定义（续2）解：解：A与B是一对多联系（如宿舍与学生），其函数依赖为BA。 C与D是一对一联系（如座位与乘客），其函数依赖为CD和DC。4.2 函数依赖154.2.2 FD的逻辑蕴涵的逻辑蕴涵n定义4.2 设F是在关系模式R上成立的函数依赖的集合（即R的每个关系 r 均满足F中的函数依赖），XY是一个函数依赖。若R的每个关系 r 也满足XY，那么称F逻辑蕴涵XY，记为F XY。 表示：表示：由关系模式R的函数依赖集F可以逻辑推导出函数依赖XY。【例】前例的关系模式R(S#, C#, Grade, TName, TAddr)，设其满足三个函数依赖：(S#, C#)Grade，

13、C#TName，TNameTAddr，则R的函数依赖集F为 (S#, C#)Grade，C#TName，TNameTAddr 。 由F可以逻辑推导出C#TAddr，则称F逻辑蕴涵C#TAddr，记为F C#TAddr或 (S#, C#)Grade，C#TName，TNameTAddr C#TAddr。4.2 函数依赖164.2.2 FD的逻辑蕴涵（续的逻辑蕴涵（续1）n定义4.3 设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集F的闭包（Closure），记为F+。即 F+= XY | F XY 。 表示：表示：F+集合中包括所有由函数依赖集F逻辑推导出来的函数依赖。【例

14、】关系模式R(S#, C#, Grade, TName, TAddr)的函数依赖集F为 (S#, C#)Grade，C#TName，TNameTAddr ，由F可以推导出来的全部函数依赖组成的集合为F+。 F+= C#TAddr，(S#, C#)Grade，C#TName，TNameTAddr， 4.2 函数依赖174.2.3 FD的推理规则的推理规则nFD的基本推理规则有以下三条：nA1(自反性，Reflexivity)：若YXU，则XY在R上成立。即属性集X必函数决定其子集Y。 【例】(S#, C#)S#，(S#, C#)C#nA2(增广性，Augmentation)：若XY在R上成立，且

15、ZU，则XZYZ在R上成立。 【例】若C#TName成立，则(C#, Grade)(TName, Grade)成立。nA3(传递性，Transitivity)：若XY和YZ在R上成立，则XZ在R上成立。 【例】若C#TName，TNameTAddr成立，则C#TAddr成立。4.2 函数依赖184.2.3 FD的推理规则（续的推理规则（续1）nFD的其他五条推理规则：nA4(合并性，Union)： XY, XZ XYZnA5(分解性，Decomposition)： XY, ZY XZnA6(伪传递性)： XY, WYZ WXZnA7(复合性，Composition)： XY, WZ XWYZn

16、A8(通用一致性定理，General Unification Theorem)： XY, WZ X(W-Y)YZn这五条推理规则可以由A1、A2、A3三条基本规则推导出来。4.2 函数依赖194.2.3 FD的推理规则（续的推理规则（续2）nA4(合并性，Union)： XY, XZ XYZ证：证：已知XY，根据A2增广性，两边分别添加X，得到XXY； 已知XZ，根据A2增广性，两边分别添加Y，得到XYYZ； 根据A3传递性，由XXY和XYYZ可得到XYZ。nA5(分解性，Decomposition)： XY, ZY XZ证：证：已知ZY可得到YZ；由XY和YZ可得到XZ。nA6(伪传递性)：

17、 XY, WYZ WXZ证：证：已知XY可得到WXWY；由WXWY和WYZ可得到WXZ。4.2 函数依赖204.2.3 FD的推理规则（续的推理规则（续3）nA7(复合性，Composition)： XY, WZ XWYZ证：证：已知XY可得到XWYW；已知WZ可得到YWYZ；由XWYW和YWYZ可得到XWYZ。 nA8(通用一致性定理，General Unification Theorem)： XY, WZ X(W-Y)YZ证：证：已知XY，根据A2增广性，两边分别添加W-Y，得到X(W-Y)Y(W-Y)； 而Y(W-Y)=YW，因此有X(W-Y)YW； 已知WZ可得到YWYZ； 由X(W-

18、Y)YW和YWYZ可得到X(W-Y)YZ。 4.2 函数依赖214.2.3 FD的推理规则（续的推理规则（续4）nA8(通用一致性定理，General Unification Theorem)： XY, WZ X(W-Y)YZ4.2 函数依赖IDAgeSNameS#S#C#GradeXYWZ注：注：ID表示身份证号码。IDC#AgeSNameS#GradeX(W-Y)YZ224.2.3 FD的推理规则（续的推理规则（续5）4.2 函数依赖n定理4.1 如果一个函数依赖XY可以从一个关系模式的函数依赖集 F 用推理规则导出，那么XY必在该函数依赖集的闭包F+中。【例4.5】已知关系模式R(ABC

19、)，F= AB, BC ，求F+。 据规则A1自反性可推出A(表示空属性集)，B，C，AA，BB，CC，。据已知的AB及规则A2增广性可推出AAB，ABB，ACBC，。另外，根据传递性还可推出AC等等。 F+中共有43个FD。234.2.3 FD的推理规则（续的推理规则（续6）4.2 函数依赖【例4.5】已知关系模式R(ABC)，F= AB, BC ，求F+。 F+中共有43个FD：A AB AC ABC B C AA ABA ACA ABCA BB CCAB ABB ACB ABCB BC AC ABC ACC ABCC BBCAAB ABAB ACAB ABCAB BCAAC ABAC A

20、CAC ABCAC BCBABC ABBC ACBC ABCBC BCCAABC ABABC ACABC ABCABC BCBCn定义4.4 对于一个FD XY，如果YX，那么称XY是一个“平凡的FD”，否则称为“非平凡的FD”。 我们主要关注非平凡的FD。 24【习题4.4】设关系模式R有n个属性，在模式R上可能成立的函数依赖有多少个？其中平凡的FD有多少个？非平凡的FD有多少个？ 设函数依赖形式为XY：4.2.3 FD的推理规则（续的推理规则（续7）4.2 函数依赖 从n个属性中选择属性组成X共有种方法；同理组成Y也有2n种方法；则组成XY应该有2n2n=4n种方法。即可能成立的FD有4n

21、个。nnnnnnCCCC2210 平凡的FD要求YX，则有： 即平凡的FD有3n个，非平凡的FD有4n-3n个。nnnnnnnnnnCCCCCCCCCCCCC3)()()(10221202211011000254.2.4 FD和关键码的联系和关键码的联系n关键码包括4种：超键、候选键、主键、外键。n超键、候选键的概念可用FD进行数学定义。n定义4.5 设关系模式R的属性集是U，X是U的一个子集。如果XU在R上成立，那么称X是R的一个超键。如果XU在R上成立，但对于X的任一真子集X1都有X1U不成立，那么称X是R上的一个候选键。【例】设一个关系模式R(S#, C#, Grade, TName,

22、TAddr)，并规定： 每个学生每学一门课只有一个成绩， 每门课程只有一个任课教师， 每个教师只有一个办公地址；则该关系模式的候选键是什么？ 已知(S#, C#)Grade，C#TName，TNameTAddr，求满足X(S#, C#, Grade, TName, TAddr)的最小X。4.2 函数依赖264.2.4 FD和关键码的联系（续和关键码的联系（续1） (S#, C#)C#，C#TName (S#, C#)TName C#TName，TNameTAddr C#TAddr (S#, C#)C#，C#TAddr (S#, C#)TAddr (S#, C#)Grade，(S#, C#)TN

23、ame， (S#, C#)TAddr (S#, C#)(Grade, TName, TAddr) (S#, C#)(S#, C#)， (S#, C#)(Grade, TName, TAddr) (S#, C#)(S#, C#, Grade, TName, TAddr) 故该关系模式的候选键为(S#, C#)；则其他属性集，如(S#, C#, TName)，虽然也能函数决定该关系模式的全部属性，但是超键，不是候选键。4.2 函数依赖274.2.4 FD和关键码的联系（续和关键码的联系（续2）【习题4.6】设R(ABCD)，F是R上成立的FD集，F= AB, CB ，则相对于F，试写出该关系模式的

24、候选键。 找候选键时，进行逻辑推理的基本方向：推理出来的函数依赖右边的属性要不断增加，以达到FD的右边包括该关系模式的全部属性（XU）。 AB, AA AAB CB, CC CBC AAB, CBC ACABC ACABC, DD ACDABCD 另外，还需要判断能否由AC或AD或CD逻辑推理出ABCD。 故该关系模式的候选键为ACD。4.2 函数依赖284.2.4 FD和关键码的联系（续和关键码的联系（续3）【习题4.7】设关系模式R(ABCD)上FD集为F，F= ABC, CD, DA ，试求R的所有候选键。 (1) ABC, ABAB ABABC ABC, CD ABD ABABC, A

25、BD ABABCD AB是一个候选键。(2) CD, CC CCD CD, DA CA CCD, CA CACD CACD, BB BCABCD BC是一个候选键。4.2 函数依赖294.2.4 FD和关键码的联系（续和关键码的联系（续4）【习题4.7】设关系模式R(ABCD)上FD集为F，F= ABC, CD, DA ，试求R的所有候选键。 (3) DA, DD DAD DAD, BB BDABD BDABD, ABC BDCD BDABD, BDCD BDABCD BD是一个候选键。因此R的候选键有3个：AB、BC、BD。4.2 函数依赖304.2.5 属性集的闭包属性集的闭包n在实际使用

26、中，经常需要判断能否从一个关系模式R已知的函数依赖集 F 推导出一个函数依赖XY，那么可先求出 F 的闭包F+，然后再看函数依赖XY是否在F+中。如果在F+中，则表明可以从函数依赖集 F 推导出。n但是，求一个函数依赖集的闭包F+属于NP问题（Non-Polynomial，即一个问题不能在多项式时间内得到解）。n因此，引入属性集闭包的概念，将“从一个关系模式R已知的函数依赖集 F 推导出一个函数依赖XY”的问题，转变为求该关系模式属性集闭包的问题。4.2 函数依赖314.2.5 属性集的闭包（续属性集的闭包（续1）n定义4.6 设F是属性集U上的FD集，X是U的子集，那么（相对于F）属性集X的

27、闭包用X+表示，它是一个从F集使用FD推理规则推出的所有满足XA的属性A的集合：X+= 属性A | XA可从F集使用推理规则推出 【例4.7】属性集U为ABCD，FD集为 AB, BC, DB ，试求A+，(AD)+，(BD)+。 解：解：A+= A, B, C =ABC，(AD)+= A, B, C, D =ABCD，(BD)+= B, C, D =BCD。 n定理4.4 一个函数依赖XY能从函数依赖集 F 用推理规则推出的充分必要条件是YX+。【练习练习】教材p162习题4.9。 (BD)+=BCD 左边是B的FD有4个：B、BB、BC、BBC324.2.6 FD集的最小依赖集集的最小依赖

28、集n一个函数依赖集F的最小依赖集是指与该函数依赖集等价的，且不含有多余的FD的集合。多余的FD包括平凡的FD，利用其他FD能够推导出来的FD等。n定义4.7 如果关系模式R(U)上的两个函数依赖集F和G，有F+=G+，则称F和G是等价的函数依赖集。n定义4.8 设F是属性集U上的FD集。如果Fmin是F的一个最小依赖集，那么Fmin应满足下列四个条件：(1) F+min =F+；(2) 每个FD的右边都是单属性；(3) Fmin中没有冗余的FD（即Fmin中不存在这样的函数依赖XY，使得Fmin与Fmin XY 等价）；(4) 每个FD的左边没有冗余的属性。n一个函数依赖集 F 的最小依赖集

29、Fmin 不一定是唯一的。4.2 函数依赖334.2.6 FD集的最小依赖集（续集的最小依赖集（续1）【例4.8】设F是关系模式R(ABC)的FD集，F= ABC, BC, AB, ABC ，试求Fmin。 先把F中的FD写成右边是单属性形式： F= AB, AC, BC, AB, ABC 显然多了一个AB，可删去，得F= AB, AC, BC, ABC 。 F中AC可以从AB和BC推出，因此AC是冗余的，可删去，得F= AB, BC, ABC 。 F中ABC可以从AB和BC推出，因此ABC也可删去，最后得F= AB, BC ，即所求的Fmin。 n算法4.2 计算函数依赖集 F 的最小依赖集

30、 Fmin 算法。（教材p141）4.2 函数依赖344.3 关系模式的分解特性关系模式的分解特性 4.3.1 模式分解定义 4.3.2 无损分解 4.3.3 无损分解的测试方法 4.3.4 保持函数依赖的分解 4.3.5 模式分解与模式等价问题354.3.1 模式分解定义模式分解定义n定义4.9 设有关系模式R(U)，属性集为U，R1、R2 、 、Rk都是U的子集，并且有R1R2RkU。关系模式R1、 R2、Rk的集合用表示，= R1, R2, , Rk 。用代替R的过程称为关系模式的分解。称为R的一个分解，也称为数据库模式。n一般把上述的R称为泛关系模式，R对应的表称为泛关系 r。数据库模

31、式对应的表称为数据库实例，用=表示。4.3 关系模式的分解特性图图4.5 模式分解示意图模式分解示意图 364.3.1 模式分解定义（续模式分解定义（续1）n因此，在计算机中数据并不是存储在泛关系 r 中，而是存储在数据库实例中。那么，存在两个问题： (1)和 r 是否等价，即是否表示同样的数据。这个问题用“无损分解”特性表示。 (2) 在泛关系模式R上有一个FD集F，在数据库模式中的每一个模式R i上有一个FD集F i，则 F1, F2, , Fk 与F是否等价。这个问题用“保持函数依赖”特性表示。4.3 关系模式的分解特性图图4.5 模式分解示意图模式分解示意图 374.3.2 无损分解无

32、损分解【例4.9】设泛关系模式R(ABC)，分解为数据库模式= AB, AC 。 (1) 设泛关系模式R对应的泛关系 r 如下所示： 则相应的数据库实例 r1 和 r2 可由泛关系 r 分别在属性集AB和AC上投影得到。4.3 关系模式的分解特性 显然有 ，即由 r 分解得到的 r1 和 r2 仍然能够恢复成 r，并未丢失或增加信息。这种分解称为无损分解。r1r2= r121111CBA泛关系泛关系r2111BA数据库实例数据库实例r111CA数据库实例数据库实例r2121111CBAr1r2384.3.2 无损分解（续无损分解（续1）【例4.9】设泛关系模式R(ABC)，分解为数据库模式=

33、AB, AC 。 (2) 设泛关系模式R对应的泛关系 r 如下所示： 同样，相应的数据库实例 r1 和 r2 可由泛关系 r 投影得到。4.3 关系模式的分解特性 显然有 ，即由 r 分解得到的 r1 和 r2 不能够恢复成 r，元组比以前多（增加了噪声）。这种分解称为有损分解或损失分解。r1r2 r321411CBA泛关系泛关系r2111BA数据库实例数据库实例r14131CA数据库实例数据库实例r2311411321421CBAr1r2394.3.2 无损分解（续无损分解（续2）n定义4.10 设R是一个关系模式，F是R上的一个FD集。R分解成数据库模式= R1, R2, , Rk 。如果

34、对R中满足F的每一个关系 r，都有 那么称分解相对于F是“无损连接分解”（Lossless Join Decomposition），简称为“无损分解”；否则称为“损失分解”（Lossy Decomposition）。其中符号R i(r)表示关系 r 在模式R i属性集上的投影。n设 r i=R i(r)，其中 1ik，并用m(r)表示上面公式等号右边的部分，则上式可改写为：4.3 关系模式的分解特性r=R1(r) R2(r) Rk(r)r =R1(r) R2(r) Rk(r)=r1 r2 r k= r i= m(r)i=1k404.3.2 无损分解（续无损分解（续3）n无损分解和损失分解有如下

35、的定理： 定理4.6 设= R1, R2, , Rk 是关系模式R的一个分解， r 是R的任一关系， r i=R i(r)（1ik），那么有下列性质： (1) r m(r)； (2) 若s=m(r)，则R i(s)=r i； (3) m(m(r)=m(r)，称为幂等性（Idempotent）。n该定理成立的先决条件： 在明确知道数据库实例 r i 是由泛关系 r 投影得到（即 r i=R i(r)成立）的前提下，该定理才成立，称为泛关系假设（Universal Relation Assumption）。 若不存在该前提，称为无泛关系假设。4.3 关系模式的分解特性414.3.2 无损分解（续无

36、损分解（续4）【例4.10】（无泛关系假设的例子）设关系模式R(ABC)分解的数据库模式= AB, BC ，AB和BC对应的数据库实例 r1 和 r2 如下所示： 则 s2=BC(s)r2。我们把r2中使s2r2的元组(b2, c2)称为悬挂元组（Dangling Tuple）。4.3 关系模式的分解特性b1a1BAr1C1b1C2b2CBr2b1Bc1a1CAs=r1 r2424.3.2 无损分解（续无损分解（续5）n模式分解（包括无损分解和损失分解）都能消除数据冗余和操作异常现象（无损分解是目标）。n但是分解之后，检索操作需要做笛卡尔积或连接操作，这将付出时间代价。n一般认为，为了消除冗余

37、和异常现象，对模式进行分解是值得的。4.3 关系模式的分解特性434.3.3 无损分解的测试方法无损分解的测试方法n在把泛关系模式R分解成数据库模式以后，如何测试分解是否是无损分解？可采用如下的测试算法： 算法4.3 无损分解的测试（以教材p145例4.11为例说明） 已知：已知：关系模式R(A1A2An)，F是R上成立的函数依赖集， = R1, , Rk是R的一个分解。 目的：目的：判断相对于F是否具有无损分解特性。 方法：方法： 构造一张k行n列的表格，每列对应一个属性A j（1jn），每行对应一个模式R i（1ik）。如果A j在R i中出现，那么在表格的第i行第j列处填上符号a j；否

38、则填上b ij。 把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改方法如下：4.3 关系模式的分解特性444.3.3 无损分解的测试方法（续无损分解的测试方法（续1） 把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改方法如下： 对于F中一个FD XY，如果表格中有两行在X值上相等，在Y值上不相等，那么把这两行在Y值上也改成相等的值。如果Y值中有一个是a j，那么另一个也改成a j；如果没有a j，那么用其中一个b ij替换另一个值（尽量把下标ij改成较小的数）。一直到表格不能修改为止。（这个过程

39、称为chase过程） 若修改的最后一张表格中有一行是全a，即a1a2an，那么相对于F是无损分解，否则是损失分解。 4.3 关系模式的分解特性454.3.3 无损分解的测试方法（续无损分解的测试方法（续2）【习题4.17】设关系模式R(ABCDEG)上FD集为F，并且F= DG, CA, CDE, AB ，分解2= DG, AC, CDE, AB ，问该分解是无损分解吗？ 解：解： 故2= DG, AC, CDE, AB 相对于 F 是无损分解。4.3 关系模式的分解特性b46b45b44b43a2a1ABb36a5a4a3b32b31CDEb26b25b24a3b22a1ACa6b15a4b

40、13b12b11DGGEDCBAa6a1a2a2464.3.3 无损分解的测试方法（续无损分解的测试方法（续3）【习题4.18】设关系模式R(ABCD)，F是R上成立的FD集，F= AB, BC, AD, DC ，= AB, AC, BD 是R的一个分解，问相对于F，是无损分解吗？ 解：解： 故= AB, AC, BD 相对于 F 是损失分解。【练习练习】教材p163习题4.19。4.3 关系模式的分解特性a4b33a2b31BDb24a3b22a1ACb14b13a2a1ABDCBAb14a2a3a3474.3.4 保持函数依赖的分解保持函数依赖的分解n保持函数依赖的分解 设泛关系模式R(U

41、)的FD集为F，在将R分解为数据库模式 = R1, R2, , Rk （其中每个R i均是U的子集）时，R的FD集 F 中的函数依赖也将被分配到每个R i上，构成R i自己的FD集F i；保持函数依赖的分解是指分解后的 F i 集合 F1, F2, , Fk 与 F 等价。n由泛关系模式R(U)的FD集 F 如何得到分解后的每个子集 R i 上的FD集 F i ？有如下定义： 定义4.11 设F是属性集U上的FD集，Z是U的子集，F在Z上的FD集 Fz 用Z(F)表示，定义为Fz=Z(F)= XY | XYF+，且XYZ 4.3 关系模式的分解特性484.3.4 保持函数依赖的分解（续保持函数

42、依赖的分解（续1）n定义4.12 设R的FD集为F，= R1, R2, , Rk 是R的一个分解，R i 上的FD集为 F i =Ri(F) （1ik），若有 F1, F2, , Fk F，那么称分解保持函数依赖集 F 的特性。 表明：表明：判断一个分解是否保持FD特性，方法是判断能否由分解后的FD集的集合 F1, F2, , Fk 逻辑推出分解前的FD集 F 中的每个函数依赖。若能推出，表明该分解保持了分解前FD集 F 的特性；否则，则不能保持。【例4.12】教材p147。4.3 关系模式的分解特性494.3.4 保持函数依赖的分解（续保持函数依赖的分解（续2）【习题4.17】设关系模式R(

43、ABCDEG)上FD集为F，并且F= DG, CA, CDE, AB ，分解2= DG, AC, CDE, AB ，问该无损分解是否保持FD特性？ 解：解：FDG=DG(F)= DG FAC=AC(F)= CA FCDE=CDE(F)= CDE FAB=AB(F)= AB 则 FDG, FAC, FCDE, FAB = DG, CA, CDE, AB = DG, CA, CDE, AB F 故该无损分解2= DG, AC, CDE, AB 保持了FD特性（保持了分解前FD集 F 的特性）。4.3 关系模式的分解特性504.3.4 保持函数依赖的分解（续保持函数依赖的分解（续3）【习题4.18】

44、设关系模式R(ABCD)，F是R上成立的FD集，F= AB, BC, AD, DC ，= AB, AC, BD 是R的一个分解，问损失分解是否保持FD特性？ 解：解：FAB=AB(F) = AB FAC=AC(F) = AC FBD=BD(F) = 则由 FAB, FAC, FBD = AB, AC, = AB, AC 不能逻辑推出 F。 故该损失分解= AB, AC, BD 不能保持FD特性。 说明：说明：这两个例子不能说明“无损分解一定保持FD特性”，“损失分解一定不保持FD特性”。无损分解特性和保持FD特性两者之间没有必然的联系。4.3 关系模式的分解特性514.3.5 模式分解与模式等

45、价问题模式分解与模式等价问题n模式分解是指将泛关系模式R分解为数据库模式，从而消除数据冗余和操作异常现象。n模式分解的两个特性实际上涉及到泛关系模式R和数据库模式这两个模式等价的问题，模式等价包括数数据等价据等价和函数依赖等价函数依赖等价两个方面。n数据等价数据等价是指泛关系模式R对应的泛关系r与数据库模式对应的数据库实例应表示同样的信息内容，用“无损分解”特性衡量。n函数依赖等价函数依赖等价是指泛关系模式R和数据库模式应具有相同的函数依赖集，用“保持函数依赖”特性衡量。4.3 关系模式的分解特性524.3.5 模式分解与模式等价问题模式分解与模式等价问题 （续续1）n“无损分解”特性和“保持

46、FD”特性两者之间没有必然的联系；故将泛关系模式R分解为数据库模式时，在两个特性方面存在以下4种可能性： (1) 分解既是无损分解，又保持FD； (2) 分解是无损分解，但不保持FD； (3) 分解是损失分解，但保持FD； (4) 分解既是损失分解，也不保持FD。 相应的实例请参见教材p148例4.13。n由于上述4种可能性的存在，在评价一个关系模式的优劣时，存在着不同级别的标准（范式）：有的范式仅要求满足其中一个特性，有的范式要求同时满足这两个特性。4.3 关系模式的分解特性534.4 关系模式的范式关系模式的范式n衡量关系模式好坏的标准就是范式（Normal Forms，简记为NF）。n范

47、式的种类： 1NF、2NF、3NF、BCNF、4NF、5NFn左左右：右：表示范式的级别越高、规定越严，高一级的范式总是在低一级范式的基础上做进一步的规定；n左左右：右：表示范式的级别越低，符合高一级范式的关系模式肯定也符合低一级的范式。n在数据库设计中最常用的是3NF和BCNF。544.4 关系模式的范式关系模式的范式 4.4.1 第一范式(1NF) 4.4.2 第二范式(2NF) 4.4.3 第三范式(3NF) 4.4.4 BC范式(BCNF) 4.4.5 模式分解方法的原则554.4.1 第一范式第一范式(1NF)n定义4.13 在关系模式 R 的每个关系 r 中，如果每个属性值都是不可

48、再分的原子值，那么称R是第一范式（First Normal Form，简记为1NF）的关系模式。n满足1NF的关系称为规范化的关系；否则，称为非规范化的关系。关系数据库研究的关系都是规范化的关系。n1NF是关系模式应具备的最起码的条件。 4.4 关系模式的范式564.4.2 第二范式第二范式(2NF)n如果关系模式中存在局部依赖，就需要将关系模式分解，以排除局部依赖，使模式达到2NF的标准，相关定义如下： 定义4.14 对于FD WA，如果对于W的真子集X有XA成立，那么称WA是局部依赖（A局部依赖于W）；否则，称WA是完全依赖。 定义4.15 如果一个属性是关系模式R候选键中的属性，那么称该

49、属性是R的主属性；否则，称该属性是R的非主属性。 定义4.16 如果关系模式R是1NF，且每个非主属性完全函数依赖于候选键，那么称R是第二范式（2NF）的关系模式。 如果数据库模式 = R1, R2, , Rk 中的每个关系模式都是2NF，则称数据库模式 为2NF的数据库模式。4.4 关系模式的范式574.4.2 第二范式第二范式(2NF)（续（续1）n2NF就是要消除非主属性对候选键的的局部依赖。n算法4.4 将关系模式R分解成2NF模式集。 设关系模式R(U)，候选键为W，对于W的真子集X存在FD XA（其中A为非主属性集），则WA就是一个局部依赖。此时应把R分解成两个模式： R1(XA)

50、，候选键是X； R2(U-A)，候选键仍是W，外键是X。 如果R1和R2还不是2NF，则重复上述过程，直到数据库模式 中每一个关系模式都是2NF为止。 4.4 关系模式的范式候选键候选键W 属性集属性集X属性集属性集A584.4.2 第二范式第二范式(2NF)（续（续2）【例】设关系模式R(S#, C#, Grade, TName, TAddr)，其函数依赖集F为 (S#, C#)Grade，C#TName， TNameTAddr ，候选键为(S#, C#) 。 问：问：R是否为2NF？如不是，将其分解为2NF。 答：答：由 C#TName，TNameTAddr C#(TName, TAddr

51、)知该关系模式 R 存在非主属性对候选键的局部依赖。 分解为R1(C#, TName, TAddr)、R2(S#, C#, Grade)。 则R1是2NF，R2是2NF。【练习练习】教材p163习题4.22。 R的候选键为AB，由AD可知R不是2NF。 分解为 =AD, ABC。4.4 关系模式的范式594.4.3 第三范式第三范式(3NF)n定义4.17 如果XY，YA，且A不是Y的子集（即 YA不是平凡的FD），那么称XA是传递依赖（A传递依赖于X）。n定义4.18 如果关系模式R的每个非主属性都不传递依赖于R的候选键，那么称R是第三范式（3NF）的关系模式。 如果数据库模式 = R1,

52、R2, , Rk 中的每个关系模式都是3NF，则称其为3NF的数据库模式 。n3NF就是要消除非主属性对候选键的的传递依赖。4.4 关系模式的范式候选键候选键W属性集属性集X属性集属性集A候选键候选键W属性集属性集A属性集属性集X604.4.3 第三范式第三范式(3NF)（续（续1）【例】接前例，学生选课关系模式 R 已分解为两个2NF模式 R1(C#, TName, TAddr)、R2(S#, C#, Grade)。 则R1的FD集F= C#TName， TNameTAddr ，候选键为C#；R2的FD集F= (S#, C#)Grade ，候选键为(S#, C#)。 问：问：R1、R2是否为

53、3NF？如不是，如何分解？ 答：答：R2是3NF。 对于R1，由 C#TName， TNameTAddr C# TAddr，知C#TAddr是一个传递依赖，故R1不是3NF。 有如下的分解算法：n算法4.7 将关系模式R无损分解且保持函数依赖地分解成3NF模式集。（教材p154）4.4 关系模式的范式614.4.3 第三范式第三范式(3NF)（续（续2）4.4 关系模式的范式 对于关系模式R和R上成立的FD集F，先求出F的最小依赖集，然后再把最小依赖集中那些左部相同的FD用合并性合并起来。 对最小依赖集中每个FD XY去构成一个关系模式XY。 在构成的模式集中，如果每个模式都不包含R的候选键，

54、那么把候选键单独作为一个模式放入模式集中。 这样得到的模式集是关系模式R的一个符合3NF的分解，并且这个分解既是无损分解，又能保持FD。 【前例】 对于其中的R1(C#, TName, TAddr)， FD集F= C#TName，TNameTAddr 。 则R1可分解为R11(C#, TName)和R12(TName, TAddr)。624.4.3 第三范式第三范式(3NF)（续（续3）4.4 关系模式的范式 故关系模式R(S#, C#, Grade, TName, TAddr)若分解为3NF，应分解为R1(C#, TName)、R2(TName, TAddr)、 R3(S#, C#, Gra

55、de)。【例4.17】设关系模式R(ABCDE)，R的最小依赖集为 AB，C D ，试将其分解为3NF。 根据最小FD集，可得到两个关系模式AB，CD； R的候选键为ACE，这两个模式中都不包含候选键，则将候选键作为一个单独的关系模式； 故，分解结果为 = AB, CD, ACE ，且该分解是无损分解且保持函数依赖。63【练习练习】教材p163习题4.23。 R的候选键为C，由 CB，BA CA，知CA是一个传递依赖，故R不是3NF。 应分解为 = CB, BA 。n定理4.9 如果R是3NF模式，那么R也是2NF模式。4.4.3 第三范式第三范式(3NF)（续（续4）4.4 关系模式的范式6

56、44.4.4 BC范式范式(BCNF)4.4 关系模式的范式n2NF是要消除非主属性对候选键的的局部依赖；3NF是要消除非主属性对候选键的的传递依赖。nBCNF是要消除主属性对候选键的传递依赖。n定义4.19 如果关系模式R是3NF，且每个主属性都不传递依赖于R的候选键，那么称R是BCNF的关系模式。如果数据库模式 = R1, R2, , Rk 中的每个关系模式都是BCNF，则称其为BCNF的数据库模式 。候选键候选键W属性集属性集X属性集属性集A候选键候选键W属性集属性集X属性集属性集A654.4.4 BC范式范式(BCNF)（续（续1）4.4 关系模式的范式【例】设关系模式R(B#, BN

57、ame, Author)，候选键为(Author, BName)，FD集F= (Author, BName)B#，B#BName。 问：问：R是否为BCNF？如不是，将其分解为BCNF。 答：答：由 (Author, BName)B#，B#BName (Author, BName)BName，知关系模式R中存在主属性BName对候选键的传递依赖，故不是BCNF。 有如下的分解算法：n算法4.6 将关系模式R无损分解成BCNF模式集。 设关系模式R(U)的候选键为W，且存在FD XA（其中X为非主属性，A为主属性），则必然存在主属性A对候选键W的传递依赖。此时应把R分解成XA和U-A两个关系模式

58、。 重复上述过程，直到数据库模式 中每一个关系模式都是BCNF为止。 664.4.4 BC范式范式(BCNF)（续（续2）4.4 关系模式的范式 故关系模式R(B#, BName, Author)可分解为两个BCNF模式：R1(B#, BName)，R2(B#, Author)。n注意：上述分解为BCNF模式的算法是无损分解，但不一定能保持函数依赖。【前例】关系模式R(B#, BName, Author)FD集F= (Author, BName)B#，B#BName ；将R分解为两个BCNF模式：R1(B#, BName)，R2(B#, Author)，是否能保持FD特性？ FR1=B#, B

59、Name(F)= B#BName ； FR2=B#, Author(F)= ； 由 FR1, FR2 = B#BName, 不能逻辑推出 F，则该分解不能保持FD特性。674.4.4 BC范式范式(BCNF)（续（续3）4.4 关系模式的范式【习题4.20】设关系模式R(ABCD)上FD集为F，并且F= AB, BC, DB 。 (1) R分解成 =ACD, BD，试求F在ACD和BD上的投影。 (2) ACD和BD是BCNF吗？如不是，试分解成BCNF。解：解：(1) ACD= AC, DC ，候选键为AD； BD= DB ，候选键为D。 (2) 对于模式ACD，候选键为AD，由AC或DC知ACD不是2NF，则肯定不是BCNF。可有两种分解方式： 若采用AC进行分解，ACD可分解为AC和AD，均是BCNF； 若采用DC进行分解，ACD可分解为CD和AD，均是BCNF； 对于模式BD，则是BCNF。684.4.5 模式分解方法的原则模式分解方法的原则n设泛关系模式R的FD集为F，将R分解为数据库模式 = R1, R2, , Rk ，一般应做到以