数据库-数据依赖的公理系统
数据依赖的公理系统
逻辑蕴含
定义6.11 对于满足一组函数依赖 F 的关系模式R <U，F>，其任何一个关系r，若函数依赖X→Y都成立, （即r中任意两元组t，s，若tX］=sX］，则tY］=sY］），则称F逻辑蕴含X →Y
Armstrong公理系统
关系模式R <U，F >来说有以下的推理规则：
A1.自反律（Reflexivity）：若Y ? X ? U，则X →Y为F所蕴含。
A2.增广律（Augmentation）：若X→Y为F所蕴含，且Z ? U，则XZ→YZ为F所蕴含。
A3.传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。
（l）自反律: 若Y ? X ? U，则X →Y为F所蕴含
证: 设Y ? X ? U
对R <U，F> 的任一关系r中的任意两个元组t，s：
若t[X]=s[X]，由于Y ? X，有t[y]=s[y]，
所以X→Y成立，自反律得证
(2)增广律: 若X→Y为F所蕴含，且Z ? U，则XZ→YZ 为F所蕴含。
证：设X→Y为F所蕴含，且Z ? U。
设R<U，F> 的任一关系r中任意的两个元组t，s：
若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z]；
由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以
XZ→YZ为F所蕴含，增广律得证。
(3) 传递律：若X→Y及Y→Z为F所蕴含，则 X→Z为 F所蕴含。
证：设X→Y及Y→Z为F所蕴含。
对R<U，F> 的任一关系 r中的任意两个元组 t，s：
若t[X]=s[X]，由于X→Y，有 t[Y]=s[Y]；
再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含，传递
律得证。
1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：
合并规则：由X→Y，X→Z，有X→YZ。
（A2， A3）
伪传递规则：由X→Y，WY→Z，有XW→Z。
（A2， A3）
分解规则：由X→Y及 Z?Y，有X→Z。
（A1， A3）
2.根据合并规则和分解规则，可得引理6.1
引理6.l X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）
Armstrong公理系统是有效的、完备的
有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中；
完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来
函数依赖闭包
定义6.l2 在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。
定义6.13 设F为属性集U上的一组函数依赖，X ?U， XF+ ={ A|X→A能由F 根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F 的闭包
引理6.2
设F为属性集U上的一组函数依赖，X，Y ? U，X→Y能
由F 根据Armstrong公理导出的充分必要条件是Y ?XF+
用途
将判定X→Y是否能由F根据Armstrong公理导出的问题，转化为求出XF+ 、判定Y是否为XF+的子集的问题
算法6.1 求属性集X（X ? U）关于U上的函数依赖集F 的闭包XF+
输入：X，F 输出：XF+
步骤：
（1）令X（0）=X，i=0
（2）求B，这里B = { A |(? V)( ? W)(V→W?F∧V ? X（i）∧A? W)}；
（3）X（i+1）=B∪X（i）
（4）判断X（i+1）= X （i）吗?
（5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。
（6）若否，则 i=i+l，返回第（2）步。
对于算法6.1， 令ai =|X（i）|，{ai }形成一个步长大于1的严格递增的序列，序列的上界是 | U |，因此该算法最多 |U| - |X| 次循环就
会终止。
[例1] 已知关系模式R<U，F>，其中
U={A，B，C，D，E}；
F={AB→C，B→D，C→E，EC→B，AC→B}。
求（AB）F+ 。
解 设X（0）=AB；
(1) X（1）=AB∪CD=ABCD。
(2) X（0）≠ X（1）
X（2）=X（1）∪BE=ABCDE。
(3) X（2）=U，算法终止
?（AB）F+ =ABCDE。
Armstrong公理系统的有效性与完备性
定理6.2 Armstrong公理系统是有效的、完备的
证明：
1. 有效性
可由定理6.1得证
2. 完备性
只需证明逆否命题: 若函数依赖X→Y不能由F从Armstrong公理导出，那么它必然不为F所蕴含
函数依赖集等价
定义6.14 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。
引理6.3 F+ = G+ 的充分必要条件是F ? G+ ，和G ? F+
证: 必要性显然，只证充分性。
（1）若F?G+ ，则XF+ ? XG++ 。
（2）任取X→Y?F+ 则有 Y ? XF+ ? XG++ 。
所以X→Y ? (G+）+= G+。即F+ ? G+。
（3）同理可证G+ ? F+ ，所以F+ = G+。
最小依赖集
定义6.15 如果函数依赖集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] 关系模式S<U，F>，其中：
U={ Sno，Sdept，Mname，Cno，Grade }，
F={ Sno→Sdept，Sdept→Mname，(Sno，Cno)→Grade }
设F’={Sno→Sdept，Sno→Mname，Sdept→Mname，
(Sno，Cno)→Grade，(Sno，Sdept)→Sdept}
F是最小覆盖，而F’不是。
因为：F ’ - {Sno→Mname}与F ’等价
F ’ - {(Sno，Sdept)→Sdept}也与F ’等价
定理6.3 每一个函数依赖集F均等价于一个极小函数依赖
集Fm。此Fm称为F的最小依赖集。
证明: 构造性证明，找出F的一个最小依赖集。
(1)逐一检查F中各函数依赖FDi：X→Y，若Y=A1A2 …Ak，k > 2，
则用 { X→Aj |j=1，2，…， k} 来取代X→Y。
(2)逐一检查F中各函数依赖FDi：X→A，令G=F-{X→A}，
若A?XG+， 则从F中去掉此函数依赖。
(3)逐一取出F中各函数依赖FDi：X→A，设X=B1B2…Bm，
逐一考查Bi （i=l，2，…，m），若A ?（X-Bi ）F+ ，
则以X-Bi 取代X。
[例3] F = {A→B，B→A，B→C，A→C，C→A}
Fm1、Fm2都是F的最小依赖集：
Fm1= {A→B，B→C，C→A}
Fm2= {A→B，B→A，A→C，C→A}
F的最小依赖集Fm不唯一
极小化过程( 定理6.3的证明 )也是检验F是否为极小依赖集的一个算法
模式的分解
把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的
只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义
三种模式分解等价的定义：
⒈ 分解具有无损连接性 ⒉ 分解要保持函数依赖 ⒊ 分解既要保持函数依赖，又要具有无损连接性
定义6.16 关系模式R<U,F>的一个分解：
ρ={ R1<U1,F1>，R2<U2,F2>，…，Rn<Un,Fn>}
U= ∪Ui，且不存在 Ui ? Uj，Fi 为 F在 Ui 上的投影
定义6.17 函数依赖集合{X→Y | X→Y ? F+∧XY ?Ui} 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影
例：S-L（Sno， Sdept， Sloc）
F={ Sno→Sdept,Sdept→Sloc,Sno→Sloc}
S-L∈2NF
分解方法可以有多种：
1. S-L分解为三个关系模式：SN(Sno)
SD(Sdept)
SO(Sloc)
2. SL分解为下面二个关系模式： NL(Sno, Sloc)
DL(Sdept, Sloc)
3. 将SL分解为下面二个关系模式： ND(Sno, Sdept)
NL(Sno, Sloc)
关系模式R
分解算法
算法6.2 判别一个分解的无损连接性
算法6.3（合成法）转换为3NF的保持函数依赖的分解。
算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解
算法6.5 （分解法）转换为BCNF的无损连接分解
算法6.6 达到4NF的具有无损连接性的分解
若要求分解具有无损连接性，那么模式分解一定能够达到4NF
若要求分解保持函数依赖，那么模式分解一定能够达到3NF，但不一定能够达到BCNF
若要求分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到3NF，但不一定能够达到BCNF
规范化理论为数据库设计提供了理论的指南和工具
也仅仅是指南和工具
并不是规范化程度越高，模式就越好
必须结合应用环境和现实世界的具体情况合理地选择数据库模式