数据库技术及应用 机械工业出版社 2019/7/24.

Presentation on theme: "数据库技术及应用 机械工业出版社 2019/7/24."— Presentation transcript:

1 数据库技术及应用 机械工业出版社 2019/7/24

2 第7章 关系数据库理论 7.1 关系数据模式的规范化理论 7.1.1 关系模式规范化的必要性 7.2 关系模式的分解算法
第7章 关系数据库理论 7.1 关系数据模式的规范化理论 关系模式规范化的必要性 函数依赖及其关系的范式 多值依赖及关系的第四范式 7.2 关系模式的分解算法 关系模式分解的算法基础 判定分解服从规范的方法 关系模式的分解方法

3 7.1 关系数据模式的规范化理论 范式（Normal Form）是指规范化的关系模式。由满足最基本规范化的关系模式叫第一范式，第一范式的关系模式再满足另外一些约束条件就产生了第二范式、第三范式、BC范式等等。一个低一级的关系范式通过模式分解可以转换成若干高一级范式的关系模式的集合，这种过程叫关系模式的规范化。

4 关系模式规范化的必要性 1. 关系模式应满足的基本要求 1) 元组的每个分量必须是不可分的数据项。 2) 数据库中的数据冗余应尽可能少。 3) 关系数据库不能因为数据更新操作而引起数据不一致问题。 4) 当执行数据插入操作时，数据库中的数据不能产生插入异常现象。 5) 数据库中的数据不能在执行删除操作时产生删除异常问题。 6) 数据库设计应考虑查询要求，数据组织应合理。

5 2. 关系规范化可能出现的问题 数据冗余大。 插入异常。 删除异常。 更新异常。 学号 姓名 年龄 性别 系名 系主任 课程名 成绩
98001 李华 20 男 计算机系 王民 程序设计 88 数据结构 74 数据库 82 电路 65 98002 张平 21 女 92 78 83 98003 陈兵 数学系 赵敏 高等数学 72 94 离散数学 87

6 3. 模式分解是关系规范化的主要方法 上述的关系模式: 教学(学号，姓名，年龄，性别，系名，系主任，课程名， 成绩).
可以按“一事一地”的原则分解成“学生”、“教学系”和“选课”三个关系，其关系模式为： 学生(学号，姓名，年龄，性别，系名称)； 教学系(系名，系主任)； 选课(学号，课程名，成绩).

7 函数依赖及其关系的范式 1. 关系模式的简化表示法 关系模式的完整表示是一个五元组： R〈U，D，Dom，F〉. 其中：R为关系名；U为关系的属性集合；D为属性集U中属性的数据域；Dom为属性到域的映射；F为属性集U的数据依赖集。 关系模式可以用三元组来为： R〈U，F〉.

8 2. 函数依赖的概念 1) 设R〈U〉是属性集U上的关系模式，X、Y是U的子集。若对于R〈U〉的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而Y上的属性值不等，则称X函数确定Y函数，或Y函数依赖于X函数，记作X→Y。 例如，对于教学关系模式：教学〈U，F〉； U={学号，姓名，年龄，性别，系名，系主任，课程名，成绩}； F={学号→姓名，学号→年龄，学号→性别，学号→系名，系名→系主任，(学号，课程名)→成绩}. ① X→Y，但Y X，则称X→Y是非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。 ② X→Y，但YX，则称X→Y是平凡的函数依赖。 ③ 若X→Y，则X叫做决定因素（Determinant），Y叫做依赖因素（Dependent）。 ④ 若X→Y，Y→X，则记作X↔Y。 ⑤ 若Y不函数依赖于X，则记作X Y。

9 完全函数依赖、传递函数依赖 2) 在R〈U〉中，如果X→Y，并且对于X的任何一个真子集X‘，都有X‘ Y，则称Y对X完全函数依赖，记作：X→Y；若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作： X→Y。 例如，在教学关系模式：(学号，课程名)→成绩，(学号，课程名)→姓名 3) 在R〈U〉中，如果X→Y，(YX)，Y X，Y→Z，则称Z对X传递函数依赖。传递函数依赖记作X → Z。 传递例如，在教学模式中，因为：学号→系名，系名→系主任；所以：学号 → 系主任。 F P F P 传递 传递

10 3. 1NF的定义、 2NF的定义 如果关系模式R，其所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，记作R1NF。 若R1NF，且每一个非主属性完全依赖于码，则R2NF。 在教学模式中： 属性集={学号，姓名，年龄，系名，系主任，课程名，成绩}. 函数依赖集={学号→姓名，学号→年龄，学号→性别，学号→系名， 系名→系主任，(学号，课程名)→成绩}. 主码=(学号，课程名). F 非主属性=(姓名，年龄，系名，系主任，成绩)。 非主属性对码的函数依赖： {(学号，课程名)→姓名，(学号，课程名)→年龄，(学号，课程号)→性别 ， (学号，课程名)→系名，(学号，课程名)→系主任；(学号，课程名)→成绩}. 显然，教学模式不服从2NF，即：教学2NF。 P P P P P

11 5. 3NF的定义 关系模式R〈U，F〉中若不存在这样的码X、属性组Y及非主属性Z(ZY)使得X→Y、Y X、Y→Z成立，则称R〈U，F〉3NF。 可以证明，若R3NF，则每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。 考查学生_系关系，由于存在：学号→系名，系名→系主任。 则： 学号 → 系主任。所以学生_系3NF。 如果分解为： 学生(学号，姓名，年龄，性别，系名)； 教学系(系名，系主任). 显然分解后的各子模式均属于3NF。 传递

12 6. BCNF的定义 关系模式R〈U，F〉1NF。若X→Y且YX时X必含有码，则R〈U，F〉BCNF。 也就是说，关系模式R〈U，F〉中，若每一个决定因素都包含码，则R〈U，F〉BCNF。由BCNF的定义可以得到结论，一个满足BCNF的关系模式有： 1) 所有非主属性对每一个码都是完全函数依赖。 2) 所有的主属性对每一个不包含它的码，也是完全依赖。 3) 没有任何属性完全函数依赖于非码的任何一组属性。

13 7. BCNF和3NF的比较 1) BCNF不仅强调其他属性对码的完全的直接的依赖，而且强调主属性对码的完全的直接的依赖，它包括3NF，即RBCNF，则R一定属于3NF。 2) 3NF只强调非主属性对码的完全直接依赖，这样就可能出现主属性对码的部分依赖和传递依赖。 例如，关系模式STJ(S，T，J)中，S表示学生，T表示教师，J表示课程。语义为：每一教师只能讲授一门课程，每门课程由若干教师讲授；每个学生选修某门课程就对应一个固定的教师。由语义可以得到STJ模式的函数依赖为： F={(S，J)→T，T→J} 显然：(S，J)和(T，S)都是关系的码；关系的主属性集为{S，T，J}，非主属性为（空集）。 P由于STJ模式中无非主属性，所以它属于3NF；但因为存在T→J，由于T不是码，故STJBCNF。

14 多值依赖及关系的第四范式 1. 研究多值依赖的必要性 例如，给定一个关系模式JPW(产品，零件，工序)，其中每种产品由多种零件构成，每个零件在装配时需要多道工序。设产品电视机需要的零件和工序如图所示。 显像管 电视机 开关 电源 焊接 调试 测试 装配

15 2. 多值依赖的定义和性质 设有关系模式R〈U〉，U是属性集，X、Y是U的子集。如果R的任一关系，对于X的一个确定值，都存在Y的一组值与之对应，且Y的这组值又与Z=U-X-Y中的属性值不相关，此时称Y多值依赖于X，或X多值决定Y，记为X→→Y。 多值依赖具有以下性质： 1) 多值依赖具有对称性。即若X→→Y，则X→→Z，其中Z=U-X-Y。 2) 函数依赖可以看作是多值依赖的特殊情况。即若X→Y，则X→→Y。这是因为当X→Y时，对X的每一个值x，Y有一个确定的值y与之对应，所以X→→Y。 3) 在多值依赖中，若X→→Y且Z=U-X-Y≠φ，则称X→→Y为非平凡的多值依赖，否则称为平凡的多值依赖。

16 7.2 关系模式的分解算法 7.2.1 关系模式分解的算法基础
7.2 关系模式的分解算法 关系模式分解的算法基础 1. 函数依赖的逻辑蕴含 设F是模式R〈U〉的函数依赖集，X和Y是属性集U的子集。如果从F中的函数依赖能推出X→Y，则称F逻辑蕴含X→Y，或称X→Y是F的逻辑蕴含。 2. Armstrong公理系统 (1) Armstrong公理系统 设U为属性集，F是U上的函数依赖集，于是有关系模式R〈U，F〉。对R〈U，F〉来说，有以下的推理规则。 1) 自反律：若YXU，则X→Y为F所蕴含。 2) 增广律：若X→Y为F所蕴含，且ZU，则XZ→YZ为F所蕴含。 3) 传递律：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。 (2) Armstrong公理的三个推理 1) 合并规则：由X→Y，X→Z，有X→YZ。 2) 伪传递规则：由X→Y，WY→Z，有XW→Z。 3) 分解规则：由X→Y及ZY，有X→Z。

17 3. 函数依赖集闭包F+和属性集闭包XF+ (1) 函数依赖集闭包F+和属性集闭包XF+的定义 定义：在关系模式R〈U，F〉中，为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F+。 定义：设有关系模式R〈U，F〉，X是U的子集，称所有从F推出的函数依赖集X→Ai中Ai的属性集为X的属性闭包，记作XF+。即： XF+={ Ai | Ai∈U，X→Ai∈F+} (2) 属性集闭包XF+的求法 1) 选X作为闭包XF+的初值XF(0)。 2) XF(i+1)是由XF(i)并上集合A所组成，其中A为F中存在的函数依赖Y→Z，而AZ，YXF(i)。 3) 重复步骤2)。一旦发现XF(i)= XF(i+1)，则XF(i)为所求XF+。

18 例子 【例7-1】已知关系R〈U，F〉，其中U={A，B，C，D，E}，F={AB→C，B→D，C→E，EC→B，AC→B}，求(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}

19 4. 函数依赖集的最小化 (1) 最小函数依赖集的定义 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 1) F中任一函数依赖的右部仅含有一个属性。 2) F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。 3) F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z-A}与F等价。 (2) 最小函数依赖集的求法 1) 逐一检查F中各函数依赖X→Y，若Y=A1A2…Ak，k≥2，则用{X→Aj|j=1，2，…k}来取代X→Y。 2) 逐一检查F中各函数依赖X→A，令G=F-{X→A}，若A∈XG+，则从F中去掉此函数依赖。 3) 逐一取出F中各函数依赖X→A，设X=B1B2…Bm，逐一检查Bi（i=1，2，…，m），如果A∈(X-Bi)F+，则以X-Bi取代X。

20 【例7-2】设F={A→BC，B→AC，C→A}，对F进行极小化处理。
解： 1) 根据分解规则把F中的函数依赖转换成右部都是单属性的函数依赖集合，分解后的函数依赖集仍用F表示。 F={A→B，A→C，B→A，B→C，C→A} 2) 去掉F中冗余的函数依赖。 判断A→B。设：G1={ A→C，B→A，B→C，C→A}， 得：AG1+=AC ∵ BAG1+ ∴ A→B不冗余 判断A→C。设：G2={ A→B，B→A，B→C，C→A}， 得：AG2+=ABC ∵ CAG2+ ∴ A→C冗余 判断B→A。设：G3={ A→B，B→C，C→A}， 得：BG3+=BCA ∵ ABG3+ ∴ B→A冗余 判断B→C。设：G4={ A→B，C→A}， 得：BG4+=B ∵ CBG4+ ∴ B→C不冗余 判断C→A。设：G5={ A→B，B→C }， 得：CG5+=C ∵ ACG5+ ∴ C→A不冗余 Fm={ A→B，B→C，C→A}

21 【例7-3】求F={AB→C，A→B，B→A}的最小函数依赖集Fm。
解：(1)去掉F中冗余的函数依赖。 判断AB→C是否冗余。设：G1={ A→B，B→A}， 得：(AB)G1+=AB ∵ C (AB)G1+ ∴ AB→C不冗余 判断A→B是否冗余。设：G2={ AB→C，B→A}， 得：AG2+=A ∵ BABG2+ ∴ A→B不冗余 判断B→A是否冗余。设：G3={ AB→C，A→B }， 得：BG3+=B ∵ ABG3+ ∴B→A不冗余 经过检验后的函数依赖集仍然为F={AB→C，A→B，B→A}。 (2) 去掉各函数依赖左部冗余的属性。 本题只需考虑AB→C的情况。 方法1：在决定因素中去掉B，若CAF+，则以A→C代替AB→C。 求得：AF+=ABC ∵ CAF+ ∴ 以A→C代替AB→C 故：Fm={A→C，A→B，B→A} 方法2：在决定因素中去掉A，若CBF+，则以B→C代替AB→C。 求得：BF+=ABC ∵ CBF+ ∴ 以B→C代替AB→C 故：Fm={B→C，A→B，B→A}

22 7.2.3 判定分解服从规范的方法 1. 关系分解的无损连接性
判定分解服从规范的方法 1. 关系分解的无损连接性 设关系模式R，如果把它分解为两个（或多个）子模式R1和R2，相应一个R关系中的数据就要被分成R1 、R2两个（或多个）子表。假如将这些子表自然连接，即进行R1R2操作，得到的结果与原来关系中的数据一致，信息并没有丢失，则称该分解具有无损连接性，否则如果R≠R1R2，则称该分解不具有无损连接性。 2. 判断分解成两个关系具有无损连接性的方法 定理：R〈U，F〉的一个分解={ R1〈U1，F1〉，R2〈U2，F2〉}具有无损连接性的充分必要条件是： U1∩U2→U1-U2∈F+. 或 U1∩U2→U2-U1∈F+. 3. 判断分解保持函数依赖的方法 设Ｒ〈U，F〉的分解={R1〈U1，F1〉，R1〈U2，F2〉，…Rk〈UK，FK〉}，若F+=(∪Fi)+，则称分解保持函数依赖。

23 例子 【例7-5】关系模式R={CITY，ST，ZIP}，其中CITY为城市，ST为街道，ZIP为邮政编码，F={(CITY，ST)→ZIP，ZIP→CITY}。如果将R分解成R1和R2，R1={ST，ZIP}，R2={CITY，ZIP}，检查分解是否具有无损连接和保持函数依赖。 解：1) 检查无损连接性。 求得：R1∩R2={ZIP}；R2-R1={CITY}. ∵ (ZIP→CITY)∈F+. ∴ 分解具有无损连接性 2) 检查分解是否保持函数依赖 求得：πR1(F)=Ф；πR2(F)={ ZIP→CITY}. ∵ πR1(F)∪πR2(F)={ ZIP→CITY}≠F+. ∴ 该分解不保持函数依赖。

24 关系模式的分解方法 1. 将关系模式转化为3NF的保持函数依赖的分解 1) 对R〈U，F〉中的F进行极小化处理。处理后的函数依赖集仍用F表示。 2) 找出不再在F中出现的属性，把这样的属性构成一个关系模式，并把这些属性从U中去掉。 3) 如果F中有一个函数依赖涉及R的全部属性，则R不能再分解。 4) 如果F中含有X→A，则分解应包含模式XA，如果X→A1，X→A2，…X→An均属于F，则分解应包含模式XA1A2…An。 【例7-6】设关系模式R〈U，F〉，U={C，T，H，R，S，G，X，Y，Z}，F={C→T，CS→G，HR→C，HS→R，TH→R，C→X}，将R分解为3NF，且保持函数依赖。 解：设该函数依赖集已经是最小化的，则分解为： ={YZ，CTX，CSG，HRC，HSR，THR}.

25 2. 将关系转化为3NF、且既具有无损连接性又能保持函数依赖的分解
对于给定的关系模式R〈U，F〉，将其转换为3NF，且既具有无损连接性又能保持函数依赖的分解算法为： 1) 设X是R〈U，F〉的码，R〈U，F〉先进行保持函数依赖的分解，结果为={ R1〈U1，F1〉，R2〈U2，F2〉，…，Rk〈Uk，Fk〉}，令τ=∪{R*〈X，Fx〉}。 2) 若有某个Ui，X Ui，将R*〈X，Fx〉从τ中去掉，τ就是所求的分解。 【例7-7】有关系模式R〈U，F〉，U={C，T，H，R，S，G}，F={C→T，CS→G，HR→C，HS→R，TH→R}，将R分解为3NF，且既具有无损连接性又能保持函数依赖。 解：求得关系模式R的码为HS，它的一个保持函数依赖的3NF为： ={CT，CSG，HRC，HSR，THR}. ∵ HSHSR ∴ τ=={ CT，CSG，HRC，HSR，THR}为满足要求的分解。

26 3. 将关系模式转换为BCNF的无损连接的分解
1) 令= R〈U，F〉。 2) 检查中各关系模式是否均属于BCNF。若是，则算法终止。 3) 假设中Ri〈Ui，Fi〉不属于BCNF，那么必定有X→AFi+，(AX)，且X非Ri的码。对Ri进行分解：σ={S1，S2}，US1=XA，US2= Ui-{A}，以σ代替Ri〈Ui，Fi〉，返回第2)步。

27 例子 【例7-8】关系模式R〈U，F〉，U=CTHRSG，F={ C→T，HR→C， HT→R，CS→G，HS→R}，把R分解成具有无损连接的BCNF。 解：令= CTHRSG 1) 由于R的码为HS，选择CS→G分解。得出：={S1，S2}. 其中：S1=CSG， F1={ CS→G}； S2=CTHRS， F2={ C→T，HR→C，HT→R，HS→R}. S2不服从BCNF，需要继续分解。 2) 对S2分解。S2的码为HS，选择C→T分解。得出：={ S1，S3，S4}. 其中：S3=CT， F3={ C→T}； S4=CHRS， F4={ HR→C，HS→R}. S4不服从BCNF，还需要继续分解。 3) 对S4分解。码为HS，选择HR→C分解：={ S1，S3，S5，S6}. 其中：S5=HRC， F5={ HR→C}； S6=HRS， F6={HS→R}. 4) 最后的分解为：={CSG，CT，HRC，HRS}.

28 本章结束 谢谢