3数据依赖的公理系统
# 0x0.总览
总图:
# 0x1.模式分解算法的理论基础
- 分解的根据:要保证分解后的一组关系能够继续携带完整的实际需求信息
- 很多时候你都期望你的函数依赖集合能够以尽可能少的依赖数量描述出你的实际需求
- 因为分解的时候你期望关注一个最少数量的函数依赖的集合,但是它必须能够反映所有需求
# 0x2.各个概念
# 1.Armstrong公理系统
# (1)定义:
对于满足一组函数依赖 F 的关系模式R <U,F>,其任何一个关系r,若函数依赖X→Y都成立, (即r中任意两元组t,s,若t[X]=s[X],则t[Y]=s[Y]),则称F逻辑蕴含X →Y
# (2)推理规则:
关系模式R <U,F >来说有以下的推理规则:
==自反律(Reflexivity)==:若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成立,自反律得证
==增广律(Augmentation)==:若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所蕴含,增广律得证。
==传递律(Transitivity)==:若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所蕴含,传递 律得证。
根据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)
根据合并规则和分解规则,可得==引理6.1==:
$X→A_1 A_2…A_k$成立的充分必要条件是X→A~i~成立(i=1,2,…,k)
# 2.闭包
# (1)F的闭包
在关系模式R<U,F>中为F所逻辑蕴含的函数依赖的全体叫作==F的闭包==,记为F^+^。
例子:
NP完全问题复杂度太高,因此又定义了X关于函数依赖集F的闭包。
# (2)X关于函数依赖集F的闭包
设F为属性集U上的一组函数依赖,X 属于U, $X_F^+$ ={ A|X→A能由F 根据Armstrong公理导出}, $X_F^+$称为属性集==X关于函数依赖集F的闭包==(即X所能决定的那些属性)
# 用途:
将判定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| 次循环就 会终止。
# 例子:
[例6.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。
# 3.闭包相关概念
# (1)覆盖
定义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+。
# (2)最小覆盖(不唯一)
# 定义和限制:
定义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等价。 (决定因素里没有多余的属性)
目的:用最少的描述反应实际中事物间的关系从而便于分解
# 定理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。(检查左多项,是否可以减少左多项数目)
# 例子:
[例6.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.13] 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是否为极小依赖集的一个算法