资源简介

(共32张PPT)
关系数据库规范化理论
第4章
目录
01
关系规范化
的引入
02
函数依赖
03
函数依赖的
公理系统
04
关系模式的
规范化
05
多值依赖
与4NF
06
关系模式分解
及规范化步骤
本章主要内容
通过第2、3章的学习，学生可以完成数据库关系模型的设计及实现。每种关系模型对应一种关系模式，关系模式的好坏直接决定数据的完整性、准确性、一致性和操作性。然而，是不是所有满足关系模型的关系模式设计都是“最好”的设计？不同的关系模式设计会出现什么样的问题？有没有什么理论标准来评价或者优化该关系模式，使其成为“更好”的关系模式设计？
本章重点内容是学习如何针对具体的应用项目，从概念模型设计出发，通过不断优化，实现一个“较好”的数据库关系模式设计。其内容包括关系模式设计存在的常见问题，关系模式中属性间依赖关系及函数依赖的公理系统理论，最小函数依赖集及其求解算法，范式及其转换步骤和多属性之间的依赖关系。
关系模式分解
及规范化步骤
第4章
06
4.6 关系模式分解
定义： 假设有关系模式R(U,F)，U是属性全集，F是函数依赖集，其中，{,,…,}是U的子集，且，如果用一个关系模式的集合代替R(U)，就称ρ是关系模式R(U)的一个分解。
为确保模式分解前后保持一致性，在R(U,F)分解为ρ的过程中，需要考虑以下两个问题:
（1）R和ρ是否等价。
（2）{F1,F2,…,Fn}是否与F等价。
对以上两个问题的讨论，主要考虑模式分解后数据依赖的一致性，即分解要能够保持无损连接性和保持函数依赖性，如若破坏这种依赖关系，就失去了分解的意义。
4.6.1 无损分解
1．无损分解的定义
定义: 设R(U,F)是一个关系模式，F是R上的一个函数依赖集，R分解为关系模式集合。如果对于R中满足F的每一个关系r，都有,则称分解相对于F是无损连接分解（Lossingless Join Decomposition），简称为无损分解，否则就称为有损分解（Lossy Decomposition）。
4.6.1 无损分解
【例4.14】已知关系模式R(U,F)，其中属性集U＝{A,B,C}，F={A→B,A→C}，如若将R分解后的关系模式集合为：ρ1＝{R1{A,B},R2{A,C}},ρ2＝{R3{A,B},R4{B,C}}，依据无损分解的定义，判断ρ1、ρ2是否为无损分解。
解：（1）如图4.5（a）所示，r是关系模式R(U,F)上的一个关系，图4.5（b）和图4.5（c）分别是r在R1、R2上的投影r1和r2。r1与r2自然连接后，得到图4.5（d）所示的关系模式。由图4.5（a）与图4.5（d）可知，分解后ρ1能够恢复到r，因此ρ1是一个无损分解。
（2）图4.5（e）和图4.5（f）分别是r在R3、R4上的投影r3和r4。r3与r4自然连接后，得到图4.5（g）所示的关系模式。由图4.5（g）可知，分解后ρ2不能够恢复到r，因此ρ2是一个有损分解。
4.6.1 无损分解
图4.5 有损分解与无损分解示意图
4.6.1 无损分解
2．无损分解测试算法
无损分解测试算法：假设有关系模式R(U,F)，其中，U＝{A1,A2,…,An}，R(U)的一个分解是，判断ρ是否为无损分解的算法如下。
输入：
（1）关系模式R(U)，其中，U＝{A1,A2,…,An}；
（2）R(U)上成立的函数依赖集F；
（3）R(U)的一个分解，而。
输出：
ρ相对于F是否为无损分解。
4.6.1 无损分解
具体步骤如下:
（1）构造一个k行n列的表格，每列对应一个属性，每行对应一个模式的属性集合。如果在中，那么在表格的第i行第j列处填写，否则填写。
（2）根据函数依赖集F中的每个函数依赖，重复地修改表格中的元素，直至表格不能修改为止。
具体操作过程:从F中按照某种顺序取某一函数依赖X→Y，在表格中查询X分量，如若存在表格内有两行在X上分量相等，在Y分量上不相等，则修改Y分量的值，使这两行在Y分量上相等，具体修改过程分以下两种情况。
① 如若其中一个Y分量是aj，则将另一个也修改成aj。
② 如若Y分量均不是aj，则用标号较小的bij替换另一个标号。
（3）重复操作，当按着F中的顺序，根据所有函数依赖对表格修改完毕后，如若表格中有一行全是a，即a1,a2,…,an，则ρ相对于F是无损分解，否则是有损分解。
4.6.1 无损分解
【例4.15】设有关系模式R(U,F)，U={A,B,C,D,E}，。R(U,F)的一个模式分解。下面使用无损分解测试算法“追踪”判断ρ是否为无损分解。
解：（1）根据题意，构建一个5行5列的初始表格，如表4.16所示。
4.6.1 无损分解
（2）根据函数依赖F中的函数依赖，修改表格元素。
① 根据函数依赖A→C，可对表4.16进行处理，因为第1、2和5行在A分量（列）上的值均为a1，而在C分量上的值都不相同，且不为a3，所以属性C列的第1、2和5行上的值b13、b23和b53统一修改为最小的标号b13，其结果如表4.17所示。
A→C
b13
b13
b13
4.6.1 无损分解
② 根据函数依赖B→C，修改表4.17，因为第2、3行在B列上相等，在C列上不相等且不为a3，所以将属性C列的第2、3行中的b13和b33改为最小标号b13，其结果如表4.18所示。
B→C
b13
b13
4.6.1 无损分解
③ 根据函数依赖C→D，修改表4.18，因为第1、2、3和5行在C列上的值均为b13，在D列上的值不相等，所以将D列的第2、3和5行上的元素b24、b34、b54都改为a4，其结果如表4.19所示。
C→D
a4
a4
a4
a4
4.6.1 无损分解
④ 根据函数依赖{D,E}→C，修改表4.19，因为第3、4和5行在D和E列上的值均为a4和a5，在C列上的值不相等，所以将C列的第3、5行上的元素都改为a3，其结果如表4.20所示。
{D,E}→C
a3
a3
a3
4.6.1 无损分解
⑤ 根据函数依赖{C,E}→A，修改表4.20，因为第3、4和5行在D和E列上的值均为a3和a5，在A列上的值不相等，所以将A列的第3、4行的元素都改成a1，其结果如表4.21所示。
{D,E}→C
a1
a1
a1
4.6.1 无损分解
至此，F中的所有函数依赖均已检查完毕，由表4.21可知，第3行全为a，根据算法的定义，关系模式R(U)的分解ρ是无损分解。
4.6.1 无损分解
【例4.16】假设有授课关系SCT(SNo,CNo,Score,TNo,TN)，其中，属性SNo为学生学号，CNo为课程号，Score为课程成绩，TNo为教师号，TN为教师名称。关系SCT的函数依赖集F={(SNo,CNo)→Score,CNo→TNo,TNo→TN}。判断SCT的一个分解ρ={R1(SNo,CNo,Score),R2(CNo,TNo),R3(TNo,TN)}相对于F是否为无损分解。
解：（1）根据算法的定义，关系模式SCT有5个属性，分解为3个模式，则需要构建一个3行5列的表格，并根据算法4.3向表格内填入相应的符号，构建的初始表格如表4.22所示。
4.6.1 无损分解
（2）根据函数依赖(SNo,CNo)→Score修改表4.22，由于在表格中，SNo、CNo所对应的列中没有相同的行，因此不用修改。
（3）根据函数依赖CNo→TNo修改表4.22，由于在表格中，CNo所对应的列中第1、2行都为a2，因此把TNo列所对应的第1行修改为a4，使其与第2行相同，修改后的结果如表4.23所示。
4.6.1 无损分解
（4）根据函数依赖TNo→TN修改表4.23，因为在表格中TNo列对应的第1、2、3行均为a4，TN列中第3行为a5，所以将TN列的第1、2行都修改为a5，修改后的结果如表4.24所示。
对F中的所有函数依赖均已检查完毕，由表4.24可知，第1行全为a，根据无损分解算法的定义可知，关系模式SCT的分解是无损分解。
4.6.1 无损分解
定理：假设={R1,R2}是关系模式R的一个分解，F是R上成立的函数依赖集，那么分解相对于F是无损分解的充分条件是：
或,
其中，表示两个模式的交集和,表示两个模式的差集。当模式R分解成两个模式和时，如果两个模式的交集不为空，且能够决定的其他属性，则该分解为无损分解。
该定理可以用算法4.3证明，此处不再展开证明。
4.6.2 保持函数依赖
1．保持函数依赖的概念
定义: 假设有关系模式R(U,F)，F是属性集U上的函数依赖集，Z是U的一个子集，F在Z上的一个投影用表示：
定义: 假设有关系模式R(U,F)，是R的一个分解，如若，则称分解保持函数依赖集F，简称为保持函数依赖分解。
4.6.2 保持函数依赖
【例4.17】已知有关系模式R(U,F)，其中U＝{CNo,CN,BN}，CNo为课程号，CN为课程名称，BN为教材名称；F＝{CNo→CN,CN→BN}。语义规定，一门课程可以有多个课程号（开设不同的专业），每门课程可以订购不同的教材。
假设将R(U,F)分解为ρ＝{R1(U1,F1),R2(U2,F2)}，其中，U1＝{CNo,CN}，F1＝{CNo→CN}，U2＝{CNo,BN}，F2＝{CNo→BN}，判断ρ是否为无损分解和保持函数依赖分解。
4.6.2 保持函数依赖
解：(1)通过表4.25～表4.28很容易就可以证明该模式分解ρ是无损分解。我们再分析一下ρ是不是保持函数依赖分解。
(2)已知R1上的函数依赖CNo→CN和R2上的函数依赖CNo→BN无法得到在R上成立的函数依赖CN→BN，即分解ρ丢失了CN→BN，ρ不能保持函数依赖F，因此ρ不是保持函数依赖分解。
4.6.2 保持函数依赖
2．保持函数依赖分解的测试算法
保持函数依赖分解的测试算法:假设有关系模式R(U,F)，是R的一个分解，判断ρ是否为保持函数依赖分解的测试算法如下。
输入：
（1）关系模式R(U)；
（2）关系模式集合
输出：
ρ是否为保持函数依赖分解。
4.6.2 保持函数依赖
算法过程：
（1）令；
（2）对于F中的第一个函数依赖，计算，并令；
（3）若，则令，转向（4）；否则，若，转向（2），否则转向（4）；
（4）若，则ρ是保持函数依赖分解；否则，ρ不是保持函数依赖分解。
4.6.2 保持函数依赖
【例4.18】设有关系模式R(U,F)，其中的一个模式分解，其中，判断ρ是否为保持函数依赖分解。
解：保持函数依赖分解算法的分析如下。
（1）G＝{A→B,B→C,C→D}，F＝F－G＝{D→A}，Result＝True。
（2）对于函数依赖D→A，根据算法，有X→Y，令X={D}，Y={A}，计算XG的闭包XG＋＝{A,B,C,D}，根据算法F=F－{X→Y}=F－{D→A}＝。
（3）由于Y＝{A}XG＋＝{A,B,C,D}，且F=，故转向（4）。
（4）由于Result＝True，因此模式分解ρ是保持函数依赖分解。
4.6.2 保持函数依赖
【例4.19】假设有授课关系SCT(SNo,CNo,Score,TNo,TN），其中，属性SNo为学生学号，CNo为课程号，Score为课程成绩，TNo为教师号，TN为教师名称。关系SCT的函数依赖集，SCT的一个分解为
其中，。
（1）判断ρ相对于F是否为无损分解。
（2）判断ρ相对于F是否为保持函数依赖分解。
4.6.2 保持函数依赖
解：（1）由例4.16可知，ρ相对于F为无损分解。
（2）根据保持函数依赖分解算法判断ρ相对于F是否为保持函数依赖分解。
① G＝{(SNo,CNo)→Score,CNo→TNo,TNo→TN}，F=F-G=，Result＝True。
② 因F为空，故不用求XG+。
③ 由于F=F-G=，且Result＝True，则ρ相对于F为保持函数依赖分解。
4.7 关系模式规范化步骤
规范化的基本思想是逐步消除不合适的数据依赖，使模式中的各个关系模式达到某种程度的“分离”。即采用“一事一地”的模式设计原则，让一个关系描述一个概念、一个实体或实体间的一种联系。
关系模式规范化的基本步骤如图4.6所示。
本章小结
关系模式不合理存在的问题：数据冗余、插入异常、删除异常和更新异常；
函数依赖：关系模式中不同属性间存在的函数依赖和数据依赖关系，进而引起数据存储问题，函数依赖定义、分类及符号表示；
函数依赖的公理系统：函数依赖的公理系统一方面可以解决由已知函数推出未知函数依赖的问题，另一方面还可以简化函数依赖集，并为关系模式的候选码提供了求解方法，即求属性集闭包。
范式：关系模式规范化对不同程度的规范化要求设立不同的标准，通过关系模式从低级到高级的规范化过程，逐步消除数据冗余及数据更新存在的问题，优化关系模式的设计；
多值依赖：关系模式中不同属性间存在一对多的关系，理解第四范式。
本章小结
关系模式分解：关系模式规范化的过程就是关系模式不断分解的过程，在分解的过程中一定要保持以上两种分解规则：无损分解和保持函数依赖分解，才能保证关系模式的完整性约束。
关系模式规范化步骤：直观的理解关系模式规范化过程，以及每次由低级到高级范式规范化过程中要解决的问题。

展开更多......

收起↑