邏輯蘊含
定義6.11 對於滿足一組函數依賴 F 的關系模式R <U，F>，其任何一個關系r，若函數依賴X→Y都成立, （即r中任意兩元組t，s，若tX］=sX］，則tY］=sY］），則稱F邏輯蘊含X →Y
關系模式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。
定理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
規范化理論為數據庫設計提供了理論的指南和工具
也僅僅是指南和工具
並不是規范化程度越高，模式就越好
必須結合應用環境和現實世界的具體情況合理地選擇數據庫模式
