函数依赖的公理系统：
设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则如下：
-
自反律：如果YXU,则X→Y在R上成立。
-
增广律：如果X→Y为F所蕴涵，ZU，则XZ→YZ在R上成立。(XZ表示X∪Z，下同)
-
传递律：如果X→Y和Y→Z在R上成立，则X→Z在R上成立。
以上三条为Armstrong公理系统 -
合并律：如果X→Y和X→Z成立，那么X→YZ成立。
-
伪传递律：如果X→Y和WY→Z成立，那么WX→Z成立。
-
分解律：如果X→Y和ZY成立，那么X→Z成立。
这三条为引理
注意：
模式分解的几个重要事实：
- 若只要求分解具有“无损连接性”，一定可以达到4NF；
- 若要求分解要“保持函数依赖”，可以达到3NF，但不一定能达到BCNF；
- 若要求分解既要“保持函数依赖”，又要具有“无损连接性”，可以达到3NF，但不一定能达到BCNF；
试分析下列分解是否具有无损联接和保持函数依赖的特点：
设R(ABC)，F1={A→B} 在R上成立，ρ1={AB,AC}。
首先，检查是否具有无损联接特点：
第1种解法--算法4.2:
|
|
|||||||||||||||||||||
| (1) 构造表 |
(2)根据A→B进行处理 |
结果第二行全是a行，因此分解是无损联接分解。
第2种解法:(定理4.8)
R1(AB)∩R2(AC)=A
R2- R1=B
∵A→B,∴该分解是无损联接分解。
然后，检查分解是否保持函数依赖
πR1（F1）={A→B，以及按自反率推出的一些函数依赖}
πR2（F1）={按自反率推出的一些函数依赖}
F1被πR1（F1）所蕴涵，∴所以该分解保持函数依赖。
5.4.3保持函数依赖的模式分解
一、转换成3NF的保持函数依赖的分解
算法：
ρ={R1<U1,F1>,R2<U2,F2>,...,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解，U={A1,A2,An}，F={FD1,FD2,FDp}，并设F是一个最小依赖集，记FDi为Xi→Alj，其步骤如下：
①对R<U,F>的函数依赖集F进行极小化处理（处理后的结果仍记为F）；
②找出不在F中出现的属性，将这样的属性构成一个关系模式。把这些属性从U中去掉，剩余的属性仍记为U；
③若有X→AF，且XA=U，则ρ={R}，算法终止；
④否则，对F按具有相同左部的原则分组(假定分为k组)，每一组函数依赖Fi所涉及的全部属性形成一个属性集Ui。若UiUj(i≠j)，就去掉Ui。由于经过了步骤②，故
，于是构成的一个保持函数依赖的分解。并且，每个Ri(Ui,Fi)均属于3NF且保持函数依赖。
例1：关系模式R<U,F>，其中U={C,T,H,I,S,G}，F={CS→G,C→T,TH→I,HI→C,HS→I}，将其分解成3NF并保持函数依赖。
解：根据算法进行求解
(一)计算F的最小函数依赖集
①利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖。由于F的所有函数依赖的右边都是单个属性，故不用分解。
②去掉F中多余的函数依赖
A．设CS→G为冗余的函数依赖，则去掉CS→G，得：
F1={C→T,HS→I}
计算(CS)F1+：
设X(0)=CS
计算X(1)：扫描F1中各个函数依赖，找到左部为CS或CS子集的函数依赖，找到一个C→T函数依赖。故有X(1)=X(0)∪T=CST。
计算X(2)：扫描F1中的各个函数依赖，找到左部为CST或CST子集的函数依赖，没有找到任何函数依赖。故有X(2)=X(1)。算法终止。
(CS)F1+= CST不包含G，故CS→G不是冗余的函数依赖，不能从F1中去掉。
B．设C→T为冗余的函数依赖，则去掉C→T，得：
F2={CS→G,HS→I}
计算(C)F2+：
设X(0)=C
计算X(1)：扫描F2中的各个函数依赖，没有找到左部为C的函数依赖。故有X(1)=X(0)。算法终止。故C→T不是冗余的函数依赖，不能从F2中去掉。
C．设TH→I为冗余的函数依赖，则去掉TH→I，得：
F3={CS→G,HS→I}
计算(TH)F3+：
设X(0)=TH
计算X(1)：扫描F3中的各个函数依赖，没有找到左部为TH或TH子集的函数依赖。故有X(1)=X(0)。算法终止。故TH→I不是冗余的函数依赖，不能从F3中去掉。
D．设HI→C为冗余的函数依赖，则去掉HI→C，得：
F4={CS→G,HS→I}
计算(HI)F4+：
设X(0)=HI
计算X(1)：扫描F4中的各个函数依赖，没有找到左部为HI或HI子集的函数依赖。故有X(1)=X(0)。算法终止。故HI→C不是冗余的函数依赖，不能从F4中去掉。
E．设HS→I为冗余的函数依赖，则去掉HS→I，得：
F5={CS→G,HI→C}
计算(HS)F5+：
设X(0)=HS
计算X(1)：扫描F5中的各个函数依赖，没有找到左部为HS或HS子集的函数依赖。故有X(1)=X(0)。算法终止。故HS→I不是冗余的函数依赖，不能从F5中去掉。即：F5={CS→G,HS→I}
③去掉F5中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）
F={CS→G,HS→I}
(二)由于R中的所有属性均在F中都出现，所以转下一步。
(三)对F按具有相同左部的原则分为：R1=CSG，R2=CT，R3=THI，R4=HIC，R5=HSI。所以ρ={R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)}。
二、转换成3NF的保持无损连接和函数依赖的分解
算法：
输入关系模式R和R的最小函数依赖集F。
输出R<U,F>的一个分解ρ={R1<U1,Fk>}，Ri为3NF，且ρ具有无损连接又保持函数依赖的分解。
步骤
①根据算法1求出保持函数依赖的分解ρ={R1,R2,Rk}
②判断分解ρ是否具有无损连接性，若有，转④
③令ρ=ρ∪{X}，其中X是R的候选关键字（候选码）；
④输出ρ
例2：关系模式R<U,F>，其中：U={C,HS→I}，将其分解成3NF并保持无损连接和函数依赖。
解：
①根据例1，得到3NF并保持函数依赖的分解如下：
ρ={R1(CSG),R5(HSI)}。
②判断是否是无损连接
构造一个初始的二维表，若“属性”属于“模式”中的属性，则填aj，否则填bij。
根据C→T，对上表的处理结果如下表。
根据HI→C，对上表的处理结果如下表。
根据CS→G，对上表的处理结果如下表。
根据C→T，对上表的处理结果如下表。
通过上述的修改，使第五行成为a1a2a3a4a5a6，则算法终止。且分解具有无损连接性。
三、转换成BCNF的保持无损连接的分解
算法：
输入关系模式R和R的函数依赖集F。
输出R<U,Fk>}，Ri为BCNF，且ρ具有无损连接的分解。
步骤
①令ρ={R}，根据算法1求出保持函数依赖的分解ρ={R1,Rk}
②若ρ中的所有模式都是BCNF，转④
③若ρ中有一个关系模式Ri不是BCNF，则Ri中必能找到一个函数依赖X→A，且X不是Ri的候选码，且A不属于X，设Ri1(XA)，Ri2(Ri-A)，用分解{Ri1,Ri2}代替Ri，转②；
④输出ρ
例3：关系模式R<U,HS→I}，将其分解成BCNF并保持无损连接。
解：
①令ρ={R(U,F)}。
②ρ中不是所有的模式都是BCNF，转入下一步。
③分解R：R上的候选关键字为HS（因为所有函数依赖的右边没有HS）。考虑CS→G函数依赖不满足BCNF条件（因CS不包含候选键HS），将其分解成R1(CSG)、R2(CTHIS)。计算R1和R2的最小函数依赖集分别为：F1={CS→G}，F2={C→T,HS→I}。
分解R2：R2上的候选关键字为HS。考虑C→T函数依赖不满足BCNF条件，将其分解成R21(CT)、R22(CHIS)。计算R21和R22的最小函数依赖集分别为：F21={C→T}，F22={CH→I,HS→I}。其中CH→I是由于R22中没有属性T且C→T,TH→I。
分解R22：R22上的候选关键字为HS。考虑CH→I函数依赖不满足BCNF条件，将其分解成R221(CHI)、R222(CHS)。计算R221和R222的最小函数依赖集分别为：F221={CH→I,HI→C}，F222={HS→C}。其中HS→C是由于R222中没有属性I且HS→I,HI→C。
由于R221上的候选关键字为H，而F221中的所有函数依赖满足BCNF条件。由于R222上的候选关键字为HS，而F222中的所有函数依赖满足BCNF条件。故R可以分解为无损连接性的BCNF如：ρ={R1(CSG),R21(CT),R221(CHI),R222(CHS)}
例4：关系模式R<U,F>，其中：U={A,B,C,D,E}，F={A→C,C→D,B→C,DE→C,CE→A}，将其分解成BCNF并保持无损连接。
解：
①令ρ={R(U,F)}。
②ρ中不是所有的模式都是BCNF，转入下一步。
③分解R：R上的候选关键字为BE（因为所有函数依赖的右边没有BE）。考虑A→C函数依赖不满足BCNF条件（因A不包含候选键BE），将其分解成R1(AC)、R2(ABDE)。计算R1和R2的最小函数依赖集分别为：F1={A→C}，F2={B→D,DE→D,BE→A}。其中B→D是由于R2中没有属性C且B→C,C→D；DE→D是由于R2中没有属性C且DE→C,C→D；BE→A是由于R2中没有属性C且B→C,CE→A。又由于DE→D是蕴含关系，可以去掉，故F2={B→D,BE→A}。
分解R2：R2上的候选关键字为BE。考虑B→D函数依赖不满足BCNF条件，将其分解成R21(BD)、R22(ABE)。计算R21和R22的最小函数依赖集分别为：F21={B→D}，F22={BE→A}。
由于R22上的候选关键字为BE，而F22中的所有函数依赖满足BCNF条件。故R可以分解为无损连接性的BCNF如：ρ={R1(AC),R21(BD),R22(ABE)}
四、转换成4NF的保持无损连接的分解
算法：
输入关系模式R和R的函数依赖集F。
输出R<U,Fk>}，Ri为4NF，且ρ具有无损连接的分解。
步骤
①令ρ={R}，根据算法1求出保持函数依赖的分解ρ={R1,Rk}
②若ρ中的所有模式都是4NF，转④
③若ρ中有一个关系模式Ri不是4NF，则Ri中必能找到一个函数依赖X→→A，且X不是Ri的候选码，且A-X≠φ，XA≠Ri，令Z=A-X，由分解规则得出X→→Z。令Ri1(XZ)，Ri2(Ri-Z)，用分解{Ri1,Ri2}代替Ri，由于(Ri1∩Ri2)→→(Ri1-Ri2)，所以分解具有无损连接性，转②；
④输出ρ
①②③④⑤⑥⑦⑧
原文链接：https://www.f2er.com/javaschema/287526.html