数据库系统原理(4)--数据依赖与关系模式规范化

关系模式设计中的问题

关系数据库设计要解决的主要问题

• 什么样的数据库模式才合理？
• 怎么分解才能满足要求？
• 衡量的标准是什么？
• 理论基础是什么？
• 如何进行实现？

关于好的数据库模式

好的数据库模式是不会发生插入异常、删除异常、更新异常，同时数据冗余尽可能少的模式。

产生不好模式的根本原因是数据之间存在着某些数据依赖。

解决方法是通过分解关系来消除其中不合适的数据依赖。

数据依赖

数据依赖的定义

数据依赖是数据之间的相互制约关系，是一种语义体现。

数据依赖的类型

• 函数依赖(FD)
• 多值依赖(MVD)
• 连接依赖(JD)

函数依赖的定义

两个实例化的属性集X,Y，如果属性集X中的两个元组取值相同，必有对应的另外一个属性集Y中元组取值相同，则称Y函数依赖于X函数。

特别值得注意的是，如果属性集X中不存在两个取值相同的元组集合，则Y必定依赖于函数X，且函数X的属性集为超键。

平凡函数依赖和非平凡函数依赖

平凡函数依赖

如果Y依赖于X，同时Y是X的子集，那么称X -> Y 为平凡函数依赖

非平凡函数依赖

Y不是X的子集

对于任意关系模式而言，平凡函数依赖是必然成立的，其并不反映新的语义特征，因此我们一般不讨论平凡函数依赖。

完全函数依赖和部分函数依赖、

完全函数依赖表示的就是函数X的属性集构成了候选键。其中形式化的表示就是如果对于X的任何一个子集Z，都有Y不依赖于X，则称Y完全函数依赖于X。
如果Y不完全函数依赖于X，则称Y部分函数依赖于X。

完全函数依赖的左部构成主键，不包含冗余的属性。

传递函数依赖和直接函数依赖

如果Y函数依赖于X，Z函数依赖于Y，其Y不是X的子集，X不依赖于Y，则称Z**传递依赖于X，否则称Z直接函数依赖**于X。

函数依赖的逻辑蕴涵

{X→Y，Y→Z} ⊨ X→Z

即对于关系模式上的函数依赖集合F，只要X→Y是一个函数依赖，那么必然可以推导认为F逻辑蕴涵X→Y。、

函数依赖集合的闭包

由函数依赖集合F所逻辑蕴涵的全部函数依赖所构成的集合称之为F的闭包。
F+＝{ X→Y|F|=X→Y}

闭包的性质

• F 属于 F+，这是因为根据闭包的定义F中的每个函数依赖必定也在中F+；
• (F+)+＝F+，该性质说明闭包运算是幂等的，即F经过任意多次的闭包运算后其结果仍然等于F+
• 如果F＝F+，则称F是完备的

实际上函数依赖集合的闭包是NP问题，因此我们需要使用其他闭包。

函数依赖的推理规则(Armstrong公理)

设U是关系模式R的属性集，F是R上的函数依赖集，则有：
A1（自反律）：如果Y X U，则X→Y成立；
A2（增广律）：如果X→Y成立，且Z U，则XZ→YZ成立
A3（传递律）：如果X→Y，Y→Z成立，则X→Z成立

以上三条合起来成为Armstrong公理。

由A1～A3易推出下面的三条推理规则也是正确的：
- 合并规则：若X→Y，X→Z成立，则X→YZ成立；
- 伪传递规则：若X→Y，WY→Z成立，则WX→Z成立；
- 分解规则：若X→Y，且Z 属于 Y，则有X→Z；

函数依赖的逻辑导出

如果给定的关系模式中，函数依赖集合F由Armstrong公理能够推导出X→Y，则称X→Y是F的逻辑导出。记为F=>X→Y。

值得注意的是，逻辑蕴涵是显式存在的关系，而逻辑导出是隐含存在的关系。

属性集合的闭包

X+F ＝{A|A∈U，F=> X→A}

值得注意的是，求解属性集合的闭包的计算量远远小于求解函数依赖集合的闭包，因为属性集合的闭包是可数的，最多就是属性全集本身。

X→Y可由Armstrong公理推出的充分必要条件是Y 属于 X属性结合的闭包

算法：求解属性集X关于U上的函数依赖集F的闭包

关于数据库系统原理的数据依赖部分的所有算法，只需要能够将其应用于解决实际问题即可。

如：
属性集U为ABCD，FD集为｛ A→B，B→C，D→B ｝， 则A+=ABC； AD+=ABCD； BD+=BCD

Armstrong公理的正确性和完备性

• Armstrong公理的正确性是指“使用推理规则从FD集F推出的FD必定在F+中”即，如果F=>X→Y 则 F|=X→Y
• Armstrong公理的完备性是指“F+中的FD都能从F集使用推理规则集导出”
  即，如果F|=X→Y 则 F=>X→Y
  Armstrong公理的正确性和完备性保证了FD推导过程的有效性和可靠性

Armstrong公理的正确性和完备性说明逻辑导出和逻辑蕴涵是两个等价的概念。

函数依赖集的等价覆盖

设F，G是两个函数依赖集合，如果F+＝G+ ，则称F等价于G，或者F与G互相覆盖
F与G等价的充分必要条件是F属于G+ 并且G属于F+。

要判定F 属于 G+,只须逐一对F中的函数依赖X→Y，考查Y是否属于XG+ +
关于等价覆盖的掌握需要到哪一个程度？

最小函数依赖集

1. 右部均为单属性
2. 左部没有对于属性
3. F中没有对于的函数依赖

一个函数依赖集F均等价于一个最小函数依赖集Fmin

例：

R(A,B,C,D,E,H,I)，F = {A→BE, AH→D, B→C, BD→E, C→D, H→I, I→H, H→BE}，试求F的最小依赖集Fmin。

解：⑴右部拆成单属性
F={A→B, A→E ,AH→D, B→C, BD→E, C→D, H→I,I→H, H→B, H→E}
⑵考察左部不是单属性的函数依赖，消除多余属性
AH→D ∵((AH)-H)F+＝ABECD,D∈((AH)-H)F+
∴以A→D取代AH→D
BD→E ∵((BD)-D)F+＝BCDE,E∈((BD)-D)F+
∴以B→E取代BD→E
则 F={A→B, A→E ,A→D, B→C, B→E, C→D, H→I,I→H, H→B, H→E}

⑶消除多余的函数依赖
A→B ∵AG+＝AED,B∉ AG+(G=F-{A→B}) ∴保留该函数依赖
A→E ∵AG+＝ABCDE,E∈ AG+(G=F-{A→E}) ∴不保留该函数依赖
A→D ∵(A)G+＝ABCDE,D∈ (A)G+(G=F-{A→D}) ∴不保留该函数依赖
B→C ∵BG+＝B,C ∉ BG+(G=F-{B→C}) ∴保留该函数依赖
B→E ∵(B)G+＝BCD,E ∉ (B)G+(G=F-{B→E}) ∴保留该函数依赖
C→D ∵CG+＝AE,D∉CG+(G=F-{C→D})∴保留该函数依赖
H→I ∵HG+＝HBECD,I ∉HG+(G=F-{H→I}) ∴保留该函数依赖
I→H ∵IG+＝I,H ∉ IG+(G=F-{I→H}) ∴保留该函数依赖
H→B ∵HG+＝HIE,B∉ HG+(G=F-{H→B})∴保留该函数依赖
H→E ∵HG+＝HBCDE,E∈HG+(G=F-{H→E}) ∴不保留该函数依赖
最后剩下的F是最小函数依赖集:
Fmin= {A→B, B→C, B→E,C→D, H→I, I→H, H→B}

F的最小依赖集Fmin不一定唯一，它和我们对各函数依赖FDi 及X→A中X各属性的处置顺序有关

多值依赖

多值依赖的定义

对于某个关系上的三个属性A, B, C。如果属性B，C的取值都不单一，同时B的取值与C无关，也就是B依赖于A，随着A取值的变化可以取不同的值。

形式化描述

设R(U)是属性集U上的一个关系模式。X，Y，Z是的U的子集,并且Z=U-X-Y，如果对R(U)的任一关系r，都有如下性质：如果r中存在2个元组s、t，使得：
s[X]=t[X]
则r中必存在元组u，使得：
(1) s[X]=t[X]=u[X]
(2) u[Y]=t[Y] 且 u[Z]=s[Z]
(即交换s、t在Y上的值得到的2个元组必在r中)
则称关系模式R满足多值依赖X→→Y

多值依赖的注意事项

值得注意的是，多值依赖会导致数据冗余和更新异常，因此我们在进行数据模式设计的时候，要消除多值依赖。一般使用的方法是建立两个关系，让每个关系只存储一个多值属性的数据。

多值依赖的推导规则

与函数依赖一样，多值依赖也有一组推导规则：
A4：互补律(MVD)
如果X→→Y，则X→→(U-XY)
以后如果需要，可用X→→Y|(U-XY)表示多值依赖，以强调其互补关系
A5：扩展律(MVD)
如果X→→Y且VW，则WX→→VY
A6：传递律(MVD)
如果X→→Y且Y→→Z，则X→→(Z-Y)
下面两条为(FD+MVD)公理：
A7：如果X→Y，则X→→Y，即FD是MVD的特例
A8：如果X→→Y、ZY且对某个与Y不相交的W有：W→Z，则X→Z

由上述公理，还可以得出下列四个有关MVD的推导规则：
MVD合并规则
如果X→→Y、X→→Z，则X→→YZ
MVD伪传递规则
如果X→→Y、WY→→Z，则WX→→(Z-WY）
混合伪传递规则
如果X→→Y、XY→→Z，则X→(Z-Y）
MVD分解规则
如果X→→Y、X→→Z，则X→→(Y∩Z）、X→→(Y-Z) X→→(Z-Y）均成立。

关于多值依赖的具体内容，在学习深化的过程中去进行深入理解与记忆。

多值依赖与函数依赖

函数依赖规定某些元组不能够出现在关系中，也被称之为相等产生依赖；
多值依赖要求某种形式的其他元组必须在关系中，称为元组产生依赖。

有效性范围

对于函数依赖
X→Y的有效性仅决定于X、Y属性集上的值，它在任何属性集W（XY 属于 W 属于 U）上都成立。
若X→Y在R(U)上成立，则对于任何Y′ 属于 Y，均有X→Y ′成立。

对于多值依赖
X→→Y在属性集W（XY 属于 W 属于 U）上成立，但在U上不一定成立
若X→→Y在R(U)上成立，则不能断言对于Y′ 属于 Y，是否有X→→Y ′成立

嵌入式多值依赖

嵌入式多值依赖是指函数依赖X→→Y在模式R上不成立，但是在R的子模式W上成立，则称X→→Y为R上的嵌入型多值依赖。

关系模式分解

关系模式的分解以及关系模式的规范化相关的内容，关于公式等的记忆学习，最好参照课件。

范式

范式就是关系数据库中满足不同规范化程度的关系模式的类。
第一范式是规范化约束范式，而其他范式根据下图进行依次类推。

值得注意的是，3NF可以在保证无损连接的同时保持函数依赖，而BCNF和4NF则可能不会保持函数依赖了。因此，一般而言进行关系模式设计时，满足3NF的标准即可。

关系模式规范化

规范化

关系模式的规范化过程实际上就是按照不同级别范式的要求条件对模式进行逐渐分解的过程。