数据库复习11——关系模式与范式

=> R1(Tname(CK), Addr) R2(C#(PK), Cname, Tname(FK))

模式分解有一套规范化的分解标准，称为范式（本章重点，见后续小节）

11.2 函数依赖

函数依赖（Functional Dependency，FD）是指一个关系模式中一个属性集和另一个属性集间的多对一关系，如选课关系SC(S#, C#, Score)，给定(S#,C#)只有一个Score对应，不同(S#,C#)对应的Score值允许相等

（1）形式化定义

X、Y是关系模式R(U)属性集U的子集，R(U)的实例r中的两个元组t1、t2，若t1[X]==t2[X]可以导出t1[Y]==t2[Y]，则称Y函数依赖于X，记作X→Y

同一个关系模式可以有不同的FD，FD和应用相关；FD是对现实世界的断言，检测FD正确性只能通过考察属性的含义

形式化定义关系模式为R(U, D, dom, F)：

• R为关系模式名
• U是一个属性集
• D是U中属性的值所来自的域
• Dom是属性向域的映射集合
• F是属性间的依赖关系

关系模式设计就是寻求一个最小FD集T，一旦实现T则可以实现所有FD

（2）函数依赖的平凡性

若X→Y且Y是X的子集，则X→Y是平凡FD（子集必然依赖），否则是称FD不平凡；平凡FD无实际意义，可以通过消除平凡FD来缩小FD集

（3）函数依赖闭包

函数依赖有以下推理规则，称为Armstrong公理:

• 自反律：若B是A的子集，则A→B
• 增广律：若A→B，则AC→BC
• 传递律：若A→B且B→C，则A→C
• 自含律：A→A
• 分解律：若A→BC，则A→B且A→C
• 合并律：若A→B且A→C，则A→BC
• 复合律：若A→B且C→D，则AC→BD

函数依赖集F逻辑蕴含的函数依赖的全体构成的集合称为函数依赖F的闭包，记做F+，通过一系列推理规则可以求得F的闭包并判断某一函数依赖X→Y是否能够由F推出（即判断X→Y是否属于F+）

（4）属性闭包

判断X→Y是否能够由F推出就去构造F+计算量比较大，其实只需构造**属性X的闭包**X+即可，X+是所有能够用A推出的属性集合（即函数依赖于A的属性集合）

（5）最小函数依赖集

最小函数依赖集F必须满足以下性质：

• F的每个FD的右边只有一个属性
• F不可约，即F中的每个X→Y,F-{X→Y}与F不等价
• F的每个FD的左部不可约，即删除任意FD左边的任何一个属性后的F’不等价于F

求某个函数依赖集的最小函数依赖集的步骤如下：

1. 分解律让右边无多属性，消除冗余属性
2. 用推理规则消去左边多属性冗余
3. 消除剩余冗余FD

11.3 关系模式的分解

关系模式R(U)的一个分解p={Ri(Ui)}满足U=∪{Ui}，模式分解必须是无损连接并且需要保持函数依赖

（1）无损连接

无损连接是指：某关系模式的事例r按照关系模式分解成多个关系r1,…,rk，若r1,…,rk的自然连接（Join操作）等于r，则称该模式分解是无损的

（2）测试无损连接

Chase方法能够检测完全的无损连接，设有n个属性的模式R分解为k个模式Ri，有如下Chase过程：

1. 构造一个k行n列的表格，每行对应一个模式Ri，每列对应一个属性Aj，若Aj在模式Ri中则表格[i][j]中填入aj，否则填入bij
2. 扫描F中的每个FD X→Y
3. 若表格中有两行在X分量上相等，在Y分量上不相等则修改Y：若Y的分量中是个是aj，则另一个也修改为aj
4. 如果没有aj，则用其中一个bij替换另一个符号（i是所有b中最小的行数）
5. 重复2、3、4一直到表格不能修改为止
6. 若此时表格中有一行全是a，则该分解是无损连接的分解

当模式分解是简单的二元分解时（即p={R1,R2}），p是无损连接的分解当且仅当下面FD之一成立：

• R1和R2两模式属性的交集 → R1与R2两模式属性的差集
• R1和R2两模式属性的交集 → R2与R1两模式属性的差集

（3）保持函数依赖

保持函数依赖是指关系模式R的FD集F在分解后仍在数据库模式中保持不变，这是模式分解的第二个条件

形式化的定义分解后F在模式Ri上的投影为：

$$\pi_{R_i}(F)=\{ X→Y | X→Y \in F^+ \bigcap X、Y\subset R_i \}$$

若分解p满足如下条件则称p**保持函数依赖**：

$$\left(\bigcup_{i=1}^{k} \pi_{R_i}(F)\right)^+=F^+$$

11.4 关系模式的范式

范式$xNF$即是满足特定要求的模式，将低一级范式的关系模式通过模式分解转换为高一级范式的关系模式集合的过程叫做规范化

范式从低级到高级依次为：1NF、2NF、3NF、BCNF、4NF、5NF，高一级的范式总是低一级范式的真子集

根据关系模式R的不可约FD集F，可以画出节点是属性或属性集，边是由被依赖节点指向依赖节点的有向图来辅助分析关系模式，叫做函数依赖图

注：复习时间关系ppt中范式的例子来不及整理了

（1）1NF

1NF要求关系模式R的每一个实例r均满足：r中的每一个元组t的每一个属性中只有一个值，这是关系模式的基本要求

不满足1NF的关系模式有二义性！

（2）2NF

假定：R只有一个候选码，且该候选码为主码

$R \in 1NF$且R的每一个非主属性（非候选码的其他属性）都完全函数依赖于主码时，$R \in 2NF$

A完全依赖于W是指：W→A且A不依赖于任何一个W的真子集X，W是主键也可能包括多个属性{X、Y}，非主属性A不能局部函数依赖于X或Y

不满足2NF的关系模式可能存在［插入异常、删除异常、更新异常和数据冗余］，通过画出函数依赖图无损分解非2NF得到2NF，但2NF也不能完全消除上述问题

（3）3NF

假定：R只有一个候选码，且该候选码为主码

$R \in 2NF$且R的每一个非主属性都不传递依赖于主码时，$R \in 3NF$

称A传递依赖于Y则有：Y→X，X→A，并且Y不依赖于X（即Y不等于X）、A不是X的子集

不满足3NF的关系模式也可能存在［插入异常、删除异常、更新异常和数据冗余］，通过打破传递依赖链条，把关系模式分解成多个子关系模式

（4）BCNF

BCNF是3NF处理R有多个候选码的扩展，当R有多个候选码时即使$R \in 3NF$，也可能出现［插入异常、删除异常、更新异常和数据冗余］，这时需要分解为BCNF范式

如果关系模式R的所有不平凡的、完全的函数依赖的决定因素（左边的属性集）都是候选码，则$R \in BCNF$

若要求保持函数依赖和无损联接，则总可以达到3NF，但不一定满足BCNF；因为BCNF可以达到无损连接，但不一定保持函数依赖

11.5 关系模式分解为范式的分解算法

（1）保持函数依赖地分解R到3NF

算法步骤：

1. 求出R的最小函数依赖集F
2. 把所有不在F中出现的属性组成一个关系模式R’，并在U中去掉这些属性
3. 若F中存在X→A且XA=U，则算法结束输出{R’,R(U)}，否则继续下一步
4. 对F中的FD按相同的左部分组构成一个关系模式Ri(Ui)，Ui包括了该组FD涉及的所有属性
5. 去掉{Ri(Ui)}中属性集Ui是其他某个关系模式属性集Uj子集的关系模式Ri，得到最终的分解p={R1,R2,…,Rk,R’}，p能够保持函数依赖地把R分解到3NF

（2）无损连接且保持函数依赖地分解R到3NF

算法步骤：

1. 按算法(1)中步骤求出保持函数依赖的3NF分解，设q={R1,R2,…,Rk}
2. 设X是R的主码，p={R1,R2,…,Rk,R(X)}
3. 若X是q中某个Ri(Ui)属性集Ui的子集，则删除p中的R(X)
4. 输出p，p能够无损连接且保持函数依赖地把R分解到3NF

（3）无损联接地分解R到BCNF

算法步骤：

1. p={R}
2. 检查p中各关系模式是否满足BCNF，是则终止输出p
3. 设p中S(Us)非BCNF，则必存在X→A且X不是S的候选码：S分解为S1(XA)和S2(Us-A)，把p中的S替换为S1、S2，跳转至第二步

版权声明：本文为博主原创文章，未经博主允许不得转载。

数据库复习11——关系模式与范式

标签：数据库   关系模式   范式   无损连接   函数依赖