(有例子)关系数据模式的规范化理论

《(有例子)关系数据模式的规范化理论》由会员分享，可在线阅读，更多相关《(有例子)关系数据模式的规范化理论（28页珍藏版）》请在金锄头文库上搜索。

1、2018/10/17,数据库系统原理,韶关学院计算机科学与技术系,第7章 关系数据库理论,7.1 关系数据模式的规范化理论 7.1.1 关系模式规范化的必要性7.1.2 函数依赖及其关系的范式7.1.3 多值依赖及关系的第四范式 7.2 关系模式的分解算法7.2.1 关系模式分解的算法基础7.2.3 判定分解服从规范的方法7.2.4 关系模式的分解方法,7.1 关系数据模式的规范化理论,范式（Normal Form）是指规范化的关系模式。由满足最基本规范化的关系模式叫第一范式，第一范式的关系模式再满足另外一些约束条件就产生了第二范式、第三范式、BC范式等等。一个低一级的关系范式通过模式分解可以

2、转换成若干高一级范式的关系模式的集合，这种过程叫关系模式的规范化。,7.1.1 关系模式规范化的必要性,1. 关系模式应满足的基本要求 1) 元组的每个分量必须是不可分的数据项。 2) 数据库中的数据冗余应尽可能少。 3) 关系数据库不能因为数据更新操作而引起数据不一致问题。 4) 当执行数据插入操作时，数据库中的数据不能产生插入异常现象。 5) 数据库中的数据不能在执行删除操作时产生删除异常问题。 6) 数据库设计应考虑查询要求，数据组织应合理。,2. 关系规范化可能出现的问题,数据冗余大。 插入异常。 删除异常。 更新异常。,3. 模式分解是关系规范化的主要方法,上述的关系模式:教学(学号

3、，姓名，年龄，性别，系名，系主任，课程名，成绩).可以按“一事一地”的原则分解成“学生”、“教学系”和“选课”三个关系，其关系模式为： 学生(学号，姓名，年龄，性别，系名称)； 教学系(系名，系主任)； 选课(学号，课程名，成绩).,7.1.2 函数依赖及其关系的范式,1. 关系模式的简化表示法 关系模式的完整表示是一个五元组： RU，D，Dom，F. 其中：R为关系名；U为关系的属性集合；D为属性集U中属性的数据域；Dom为属性到域的映射；F为属性集U的数据依赖集。 关系模式可以用三元组来为： RU，F.,2. 函数依赖的概念,1) 设RU是属性集U上的关系模式，X、Y是U的子集。若对于RU

4、的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而Y上的属性值不等，则称X函数确定Y函数，或Y函数依赖于X函数，记作XY。 例如，对于教学关系模式：教学U，F； U=学号，姓名，年龄，性别，系名，系主任，课程名，成绩； F=学号姓名，学号年龄，学号性别，学号系名，系名系主任，(学号，课程名)成绩. XY，但Y X，则称XY是非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。 XY，但YX，则称XY是平凡的函数依赖。 若XY，则X叫做决定因素（Determinant），Y叫做依赖因素（Dependent）。 若XY，YX，则记作XY。 若Y不函数依赖于X，则记作X Y。

5、,完全函数依赖、传递函数依赖,2) 在RU中，如果XY，并且对于X的任何一个真子集X，都有X Y，则称Y对X完全函数依赖，记作：XY；若XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作： XY。 例如，在教学关系模式：(学号，课程名)成绩，(学号，课程名)姓名 3) 在RU中，如果XY，(YX)，Y X，YZ，则称Z对X传递函数依赖。传递函数依赖记作X Z。 传递例如，在教学模式中，因为：学号系名，系名系主任；所以：学号 系主任。,P,F,F,P,传递,传递,3. 1NF的定义、 2NF的定义,如果关系模式R，其所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，记

6、作R1NF。 若R1NF，且每一个非主属性完全依赖于码，则R2NF。 在教学模式中：属性集=学号，姓名，年龄，系名，系主任，课程名，成绩. 函数依赖集=学号姓名，学号年龄，学号性别，学号系名， 系名系主任，(学号，课程名)成绩. 主码=(学号，课程名). F 非主属性=(姓名，年龄，系名，系主任，成绩)。 非主属性对码的函数依赖：(学号，课程名)姓名，(学号，课程名)年龄，(学号，课程号)性别 ，(学号，课程名)系名，(学号，课程名)系主任；(学号，课程名)成绩. 显然，教学模式不服从2NF，即：教学2NF。,P,P,P,P,P,5. 3NF的定义,关系模式RU，F中若不存在这样的码X、属性组

7、Y及非主属性Z(ZY)使得XY、Y X、YZ成立，则称RU，F3NF。 可以证明，若R3NF，则每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。 考查学生_系关系，由于存在：学号系名，系名系主任。 则： 学号 系主任。所以学生_系3NF。 如果分解为： 学生(学号，姓名，年龄，性别，系名)； 教学系(系名，系主任). 显然分解后的各子模式均属于3NF。,传递,6. BCNF的定义,关系模式RU，F1NF。若XY且YX时X必含有码，则RU，FBCNF。 也就是说，关系模式RU，F中，若每一个决定因素都包含码，则RU，FBCNF。由BCNF的定义可以得到结论，一个满足BCNF的关系模式有

8、： 1) 所有非主属性对每一个码都是完全函数依赖。 2) 所有的主属性对每一个不包含它的码，也是完全依赖。 3) 没有任何属性完全函数依赖于非码的任何一组属性。,7. BCNF和3NF的比较,1) BCNF不仅强调其他属性对码的完全的直接的依赖，而且强调主属性对码的完全的直接的依赖，它包括3NF，即RBCNF，则R一定属于3NF。 2) 3NF只强调非主属性对码的完全直接依赖，这样就可能出现主属性对码的部分依赖和传递依赖。例如，关系模式STJ(S，T，J)中，S表示学生，T表示教师，J表示课程。语义为：每一教师只能讲授一门课程，每门课程由若干教师讲授；每个学生选修某门课程就对应一个固定的教师。

9、由语义可以得到STJ模式的函数依赖为： F=(S，J)T，TJ 显然：(S，J)和(T，S)都是关系的码；关系的主属性集为S，T，J，非主属性为（空集）。 P由于STJ模式中无非主属性，所以它属于3NF；但因为存在TJ，由于T不是码，故STJBCNF。,7.1.3 多值依赖及关系的第四范式,1. 研究多值依赖的必要性 例如，给定一个关系模式JPW(产品，零件，工序)，其中每种产品由多种零件构成，每个零件在装配时需要多道工序。设产品电视机需要的零件和工序如图所示。,2. 多值依赖的定义和性质,设有关系模式RU，U是属性集，X、Y是U的子集。如果R的任一关系，对于X的一个确定值，都存在Y的一组值与

10、之对应，且Y的这组值又与Z=U-X-Y中的属性值不相关，此时称Y多值依赖于X，或X多值决定Y，记为XY。 多值依赖具有以下性质： 1) 多值依赖具有对称性。即若XY，则XZ，其中Z=U-X-Y。 2) 函数依赖可以看作是多值依赖的特殊情况。即若XY，则XY。这是因为当XY时，对X的每一个值x，Y有一个确定的值y与之对应，所以XY。 3) 在多值依赖中，若XY且Z=U-X-Y，则称XY为非平凡的多值依赖，否则称为平凡的多值依赖。,7.2 关系模式的分解算法 7.2.1 关系模式分解的算法基础,1. 函数依赖的逻辑蕴含 设F是模式RU的函数依赖集，X和Y是属性集U的子集。如果从F中的函数依赖能推出

11、XY，则称F逻辑蕴含XY，或称XY是F的逻辑蕴含。 2. Armstrong公理系统 (1) Armstrong公理系统 设U为属性集，F是U上的函数依赖集，于是有关系模式RU，F。对RU，F来说，有以下的推理规则。 1) 自反律：若YXU，则XY为F所蕴含。 2) 增广律：若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。 3) 传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。 (2) Armstrong公理的三个推理 1) 合并规则：由XY，XZ，有XYZ。 2) 伪传递规则：由XY，WYZ，有XWZ。 3) 分解规则：由XY及ZY，有XZ。,3. 函数依赖集闭包F+和属性集闭包XF+,(

12、1) 函数依赖集闭包F+和属性集闭包XF+的定义 定义：在关系模式RU，F中，为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F+。 定义：设有关系模式RU，F，X是U的子集，称所有从F推出的函数依赖集XAi中Ai的属性集为X的属性闭包，记作XF+。即： XF+= Ai | AiU，XAiF+ (2) 属性集闭包XF+的求法 1) 选X作为闭包XF+的初值XF(0)。 2) XF(i+1)是由XF(i)并上集合A所组成，其中A为F中存在的函数依赖YZ，而AZ，YXF(i)。 3) 重复步骤2)。一旦发现XF(i)= XF(i+1)，则XF(i)为所求XF+。,例子,【例7-1】已知关系RU，F

13、，其中U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB，求(AB)F+。 设X=AB XF(0)=AB XF(1)=ABCD XF(2)=ABCDE XF(3)= XF(2)=ABCDE (AB)F+=ABCDE=A，B，C，D，E,4. 函数依赖集的最小化,(1) 最小函数依赖集的定义 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 1) F中任一函数依赖的右部仅含有一个属性。 2) F中不存在这样的函数依赖XA，使得F与F-XA等价。 3) F中不存在这样的函数依赖XA，X有真子集Z使得F-XAZ-A与F等价。 (2) 最小函数依赖集的

14、求法 1) 逐一检查F中各函数依赖XY，若Y=A1A2Ak，k2，则用XAj|j=1，2，k来取代XY。 2) 逐一检查F中各函数依赖XA，令G=F-XA，若AXG+，则从F中去掉此函数依赖。 3) 逐一取出F中各函数依赖XA，设X=B1B2Bm，逐一检查Bi（i=1，2，m），如果A(X-Bi)F+，则以X-Bi取代X。,【例7-2】设F=ABC，BAC，CA，对F进行极小化处理。,解： 1) 根据分解规则把F中的函数依赖转换成右部都是单属性的函数依赖集合，分解后的函数依赖集仍用F表示。 F=AB，AC，BA，BC，CA 2) 去掉F中冗余的函数依赖。 判断AB。设：G1= AC，BA，BC

15、，CA， 得：AG1+=AC BAG1+ AB不冗余 判断AC。设：G2= AB，BA，BC，CA， 得：AG2+=ABC CAG2+ AC冗余 判断BA。设：G3= AB，BC，CA， 得：BG3+=BCA ABG3+ BA冗余 判断BC。设：G4= AB，CA， 得：BG4+=B CBG4+ BC不冗余 判断CA。设：G5= AB，BC ， 得：CG5+=C ACG5+ CA不冗余 Fm= AB，BC，CA,【例7-3】求F=ABC，AB，BA的最小函数依赖集Fm。,解：(1)去掉F中冗余的函数依赖。 判断ABC是否冗余。设：G1= AB，BA， 得：(AB)G1+=AB C (AB)G1

16、+ ABC不冗余 判断AB是否冗余。设：G2= ABC，BA， 得：AG2+=A BABG2+ AB不冗余 判断BA是否冗余。设：G3= ABC，AB ， 得：BG3+=B ABG3+ BA不冗余 经过检验后的函数依赖集仍然为F=ABC，AB，BA。 (2) 去掉各函数依赖左部冗余的属性。 本题只需考虑ABC的情况。 方法1：在决定因素中去掉B，若CAF+，则以AC代替ABC。 求得：AF+=ABC CAF+ 以AC代替ABC 故：Fm=AC，AB，BA 方法2：在决定因素中去掉A，若CBF+，则以BC代替ABC。 求得：BF+=ABC CBF+ 以BC代替ABC 故：Fm=BC，AB，BA,