第六章 关系数据库理论
6.1 问题的提出例如,Student(Sno,Sdept,Mname,Cname,Grade)
F={Sno?Sdept,Sdept? Mname,(Sno,Cname)? Grade}
存在问题：
⑴数据冗余太大
⑵插入异常
⑶删除异常
⑷更新异常分解成三个关系模式：
S(Sno,Sdept,Sno?Sdept)；
SG(Sno,Cname,Grade,(Sno,Cname)? Grade)；
D(Sdept,Mname,Sdept? Mname)；
6.2 规范化数据依赖,关系中属性值之间的这种相互依赖又相互制约的联系，称为数据依赖。包括：函数依赖、多值依赖。
一,函数依赖定义 1,设 R(U)是属性集 U上的关系模式。 X,Y是 U的子集。若对于 R(U)的任意一个可能的关系 r,r中不可能存在两个元组在 X上的属性值相等，而在 Y上的属性值不等，则称 X函数决定 Y或 Y函数依赖于 X，记作 X→Y 。
说明,1,函数依赖是语义范畴的概念
2、函数依赖关系是反映属性之间的一般规律根据函数依赖的定义，可找出下面规律：
1、在一个关系模式中，如属性 X,Y有 1,1联系，则存在函数依赖 X→Y,
Y→X,可记作 X?Y
2,X,Y是 1,m联系，则存在 Y→X,但 X\→Y
3,X,Y是 n:m联系，则 X,Y之间不存在任何函数依赖
X→Y,但 Y?X则称 X→Y 是 平凡的函数依赖 。否则，称 非平凡的函数依赖 。
定义 2,在 R（ U）中，如果 X→Y,并且对于 X的任何一个真子集 X′,都有
X′→Y,则 称 Y对 X部分函数依赖,记作 X→pY,否则,称 Y完全函数依赖于
X,记作 X→fY 。
定义 3,在 R（ U）中，如果 X→Y,（ Y?X）,Y \→X,Y→Z,则 称 Z对 X传递函数依赖。
定义 4,设 K为 R<U,F>中的属性或属性组合，若 K f→U 则 K为 R的 候选码 。
若候选码多于一个，则选定其中的一个为 主码 （ Primary Key）。
包含在任何一个候选码中的属性，叫做 主属性 。不包含在任何码中的属性称为 非主属性 或非码属性。整个属性组是码，称为 全码 。
定义 5,关系模式 R中属性或属性组 X并非 R的码，但 X是另一个关系模式的码，则称 X是 R的外部码（ Foreign Key），也称 外码 。
二、码三、范式范式：是符合某一种级别的关系模式的集合。
关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。 1NF,2NF,3NF,BCNF,4NF,5NF
定义：关系模式 R（ U）中所有属性都不可再分的，则称 R是第一范式，记作
R?1NF。
例如,SLC（ SNO,SDEPT,SLOC,CNO,GRADE）
四,2NF
定义 6：若 R?1NF，且每一个非主属性完全函数依赖于码，则 R?2NF。
SNO
CNO
G
SDEPT
SLOC
五,3NF
定义 7：若 R?2NF，且 R中任一非主属性都不传递函数依赖于码，则 R?3NF。
SNO
CNO
G
SDEPT
SLOC
SNO
SLSC
上例 SL分解为,SD（ SNO,SDEPT） DL（ SDEPT,SLOC）
由于第三范式有效地消除了非主属性对码的部分和传递依赖，因而消除了一大类操作异常问题。因此,3NF在数据库设计中得到了广泛应用。
六,BCNF
例,关系模式 STJ（ S,T,J）中,S表示学生,T表示教师,J表示教师,J表示课程。每一教师只教一门课。每门课有若干教师，某一学生选定某门课，
就对应一个固定的教师。
由语义可得到如下的函数依赖：
（ S,J） → T； （ S,T） → J； T →J
关系有两个候选键，是（ S,J）和（ S,T）
S,T,J都是主属性，不存在非主属性，更不会有非主属性对键的传递依赖、
部分依赖了，因此,STJ关系满足第三范式。
但仍然存在问题：
定义 8,R?BCNF，当且仅当每个决定因素都是码（候选键）。
上例分解为,ST（ S,T）,TJ（ T,J）
七、多值依赖例：学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。如下表：
课程 C 教员 T 参考书 B
物理 李勇 普通物理学物理 李勇 光学原理物理 李勇 物理习题集物理 王军 普通物理学物理 王军 光学原理物理 王军 物理习题集数学 李勇 数学分析数学 李勇 微分方程数学 李勇 高等代数数学 张平 数学分析数学 张平 微分方程数学 张平 高等代数
┇ ┇ ┇
定义 9,关系模式 R（ U）,X,Y,Z是 U的子集，并且 Z=U-X-Y。关系模式 R(U)
中多值依赖 XY成立，当且仅当对 R（ U）的任一关系 r，给定的一对（ x,z）
值，有一组 Y的值，这组值仅仅决定于 x值而与 z值无关。
若 XY,而 Z=?即 Z为空，则称 XY为 平凡的多值依赖 。
多值依赖性质：
⑴ 对称性。若 XY,则 XZ，其中 Z=U－Ｘ－Ｙ。
⑵ 传递性。若 XY,ＹＺ，则 XＺ－ Y。
⑶ 函数依赖可看作是多值依赖的特殊情况。若 X?Y，则 XY。
⑷ 若 XY,XＺ，则 XYＺ。
⑸ 若 XY,XＺ，则 XY?Ｚ。
⑹ 若 XY,XＺ，则 XY－Ｚ,XＺ－ Y。
八,4NF
定义 10：关系模式 R<U,F>?1NF，如果对于 R的每个非平凡多值依赖 XY（ Y? X ）,X都含有码，则称 R<U,F>?4NF。
九、规范化小结
1NF
↓ 消除非主属性对码的部分函数依赖
2NF
↓ 消除非主属性对码的传递函数依赖
3NF
↓ 消除主属性对码的部分和传递函数依赖
BCNF
↓ 消除非平凡且非函数依赖的多值依赖
4NF
6.3 数据依赖的公理系统定义 11,对于满足一组函数依赖 F的关系模式 R<U,F>，其任何一个关系 r，若函数依赖 X→Y 都成立，则称 F逻辑蕴含 X→Y 。
Armstrong公理系统,设 U为属性集总体,F是 U上的一组函数依赖，于是有关系模式 R<U,F>。对 R<U,F>来说有以下的推理规则：
A1自反律：若 Y?X? U，则 X?Y为 F所蕴含。
A2增广律：若 X?Y为 F所蕴含，且 Z?U，则 XZ?YZ为 F所蕴含。
A3传递律：若 X?Y及 Y?Z为 F所蕴含，则 X?Z为 F所蕴含。
推论：
合并规则：由 X?Y,X?Z，有 X?YZ。
伪传递规则：由 X?Y,WY?Z，有 XW?Z。
分解规则：由 X?Y及 Z?Y，有 X?Z。
根据合并规则和分解规则，得到一重要事实：
引理 1,X?A1A2 ┅ Ak成立的充分必要条件是 X?Ai成立（ i= 1,2,┅,k）。
定义 12,在关系模式 R<U,F>中为 F所逻辑蕴含的函数依赖的全体叫做 F的闭包,
记为 F+。
定义 13,设 F为属性集 U上的一组函数依赖,X? U,XF+={A| X?A能由 F根据
Armstrong公理导出 },XF+称为属性集 X关于函数依赖集 F的闭包。
引理 2,设 F为属性集 U上的一组函数依赖,X,Y? U,X?Y能由 F根据
Armstrong公理导出的充分必要条件是 Y? XF+ 。
算法 6.1,求属性集 X（ X? U ）关于 U上的函数依赖集 F的闭包 XF+。
步骤,⑴令 X(0)=X,i=0
⑵ 求 B，这里 B={A | (?V) (? W) (V? W? F ∧ V?X(i) ∧ A?W)};
⑶ X(i+1) =B?X(i)
⑷ 判断 X(i+1) =X(i) 吗？
⑸若相等或 X(i+1) =U，则 X(i+1) 就是 XF+,算法终止。
⑹若否，则 i=i+1，返回第⑵步。
例 1 已知关系模式 R<U,F>，其中 U={A,B,C,D,E}；
F={AB?C,B?D,C?E,EC?B,AC?B}。求（ AB） F+。
定义 14,如果 G+=F+，就说函数依赖集 F覆盖 G（ F是 G的覆盖，
或 G是 F的覆盖），或 F与 G等价。
引理 3,F+ = G+的充分必要条件是 F?G+,和 G? F+ 。
定义 15,如果函数依赖集 F满足下列条件，则称 F为一个极小函数依赖集。亦称为最小依赖集或 最小覆盖 。
⑴ F中任一函数依赖的右部仅含有一个属性。
⑵ F中不存在这样的函数依赖 X?A，使得 F与 F－ {X?A}等价。
⑶ F中不存在这样的函数依赖 X?A,X有真子集 Z使得
F－ {X?A}?{Z?A}与 F 等价。
例,F={A?B,B?A,B?C,A?C,C?A} 求 Fm 。
Fm1={A?B,B?C,C?A}
Fm2={A?B,B?A,A?C,C?A}
6.4 模式的分解
分解具有“无损连接性”
分解要“保持函数依赖”
分解既要“保持函数依赖”，又要具有“无损连接性”。
定义 16,关系模式 R<U,F>的一个分解是指 ρ＝ {R1<U1,F1>,R2<U2,F2>,…,
Rn<Un,Fn>} 其中 U=?Ui，并且没有 Ui?Uj,1≤ｉ,j ≤ n,Fi是 F在 Ui上的投影。
定义 17,函数依赖集合 {X? Y|X? Y? F+ ∧ XY?Ui}的一个覆盖 Fi叫做 F在属性 Ui上的投影。
一、模式分解的三个定义例：已知关系模式 R<U,F>，其中 U={SNO,SDEPT,MN},F={SNO? SDEPT,
SDEPT?MN}。
分解,ρ1＝ {R1<SNO,?>,R2<SDEPT,? >,R3<MN,?>}
ρ2＝ {R1<{SNO,SDEPT},{SNO?SDEPT}>,R2<{SNO,MN},{SNO? MN} >}
ρ3＝ {R1<{SNO,SDEPT},{SNO?SDEPT}>，
R2<{SDEPT,MN},{SDEPT? MN} >}
二、分解的无损连接性和保持函数依赖性定义 18,ρ ＝ {R1<U1,F1>,…,Rk<Uk,Fk>}是 R<U,F>的一个分解，若 R<U,F>
的任何一个关系 r均有 r=m ρ (r)成立，则称分解 ρ 具有无损连接性。简称 ρ 为无损分解。
算法 6.2,判别一个分解的无损连接性。 ρ ＝ {R1<U1,F1>,…,Rk<Uk,Fk>}是
R<U,F>的一个分解,U={A1,…,An},F＝ {FD1,FD2,…,FDρ },F是一极小依赖集,记 FDi为 Xi?A1i。
⑴ 建立一张 n列 k行的表。每一列对应一个属性，每一行对应分解中的一个关系模式。若属性 Aj属于 Ui，则在 j列 i行交叉处填上 aj，否则填上 bij ；
⑵ 对每一个 FDi做下列操作：找到 Xi所对应的列中具有相同符号的那些行。考察这些行中 li列的元素，若其中有 ali，则全部改为 ali ；否则全部改为 bmli ； m是这些行的行号最小值。
⑶ 比较扫描前后，表有无变化。如有变化，则返回第⑵步，否则算法终止。
例,已知 R<U,F>,U＝ {A,B,C,D,E},F={AB? C,C?D,D?E},R的一个分解为 R1(A,B,C),R2(C,D),R3(D,E)。
⑴ 首先构造初始表，如图
A B C D E
a1 a2 a3 b14 b15
b21 b22 a3 a4 b25
b31 b32 b33 a4 a5
⑵ 对 AB?C，因各元组的第 1,2列没有相同的分量，所以表不改变。由 C?D
可以把 b14改为 a4,再由 D?E可使 b15,b25全改为 a5。
A B C D E
a1 a2 a3 a4 a5
b21 b22 a3 a4 a5
b31 b32 b33 a4 a5
定理,R<U,F>的一个分解 ρ ＝ {R1<U1,F1>,R2<U2,F2>}具有无损连接性的充分必要条件是,U1∩U2? U1－ U2? F+ 或 U1∩U2? U2－ U1? F+ 。
⑴ 若要求分解保持函数依赖，那么模式分离总可以达到 3NF，
但不一定能达到 BCNF;
⑵ 若要求分解既保持函数依赖，又具有无损连接性，可以达
到 3NF，但不一定能达到 BCNF;
⑶ 若要求分解具有无损连接性，那一定可达到 4NF;
当关系模式 R分解为两个关系模式 R1,R2时有下面的判定准则。
定义 19,若 F+ ＝（ ∪ Fi） ＋,则 R<U,F> 的分解 ρ ＝ {R1<U1,F1>,…,
Rk<Uk,Fk>}保持函数依赖。
三、模式分解的算法关于模式分解的几个重要事实是：
算法 6.3 转换为 3NF的保持函数依赖的分解
⑴ 对 R<U,F> 中的函数依赖集 F进行“极小化处理”，
仍记为 F。
⑵ 找出不在 F中出现的属性，把这样的属性构成一个
关系模式。把这些属性从 U中去掉，剩余的属性仍
记为 U。
⑶ 若有 X? A? F，且 XA=U，则 ρ＝ {R}，算法终止。
⑷ 否则，对 F按具有相同左部的原则分组（假定分为
k组）,每一组函数依赖 Fi′所涉及的全部属性形成
一个属性集 Ui 。若 Ui?Uj (i≠j)就去掉 Ui 。
算法 6.4 转换为 3NF既有无损连接性又保持函数依赖的分解
⑴ 设 X 是 R<U,F> 的码。 R<U,F> 已由算法 5.3分解为
ρ ＝ {R1<U1,F1>,R2<U2,F2>,…,Rk<Uk,Fk>}，
令?＝ ρ ∪ { Rx<U,Fx> } 。
⑵ 若有某个 Ui,X? Ui,将 Rx<U,Fx> 从? 中去掉。
把这些属性从 U中去掉，剩余的属性仍记为 U。
⑶? 就是所求的分解。
算法 6.5 转换为 BCNF的无损连接的分解
⑴ 令 ρ ＝ {R<U,F>}
⑵ 检查 ρ 中各关系模式是否均属于 BCNF。若是，则算法终止。
⑶ 设 ρ 中 Ri<Ui,Fi>不属于 BCNF,那么必有 X? A? Fi+ (A?X)，
且 X非 Ri的码。因此,XA是 Ui的真子集。对 Ri进行分解：
＝ {S1,S2},Us1=XA,Us2=Ui-{A}，以?代替 Ri<Ui,Fi>返回第
⑵ 步。
算法 6.6 达到 4NF的具有无损连接性的分解
⑴ 令 ρ ＝ {R}
⑵ 检查 ρ 中所有关系模式，如均为 4NF，则转 ⑷ 。
⑶ ρ 中找非 4NF的关系模式 S,S中必有一个多值依
赖 X Y,其中 X不包含 S的关键字,Y既非
空又不是 X的子集，且 XY≠S。用 S1=XY 和
S2=S－ Y代替 S。返回 ⑵。
⑷ 停止分解，输出 ρ 。
例子,关系模式 CTHRSG，其中 C表示课程,T表示教师,H表示时间,R表示教室,S表示学生,G表示成绩。函数依赖集 F及其所反映的语义分别为：
C?T 每门课程仅有一位教师担任。
HT?R 在任一时间，一个教师只能在一个教室上课。
HR?C 在任一时间，每个教室只能上一门课。
HS?R 在任一时间，每个学生只能在一个教室听课。
CS?G 每个学生学习一门课程只有一个成绩。
解,HS?CTHRSG,HS是关系模式的关键字。
⑴ 面向 3NF且保持函数依赖的分解。
最小函数依赖集为 F={C?T,CS?G,HR?C,HS?R,TH?R}
分解为,?＝ {CT,CSG,HRC,HSR,THR}
⑵ 面向 3NF既有无损连接性又保持函数依赖的分解。
∵ HS是关键字,?＝? ∪ { HS },HS是 HSR的一个子集
∴ 分解仍为,?＝ {CT,CSG,HRC,HSR,THR}
⑶ 面向 BCNF且具有无损连接性的分解。
CTHRSG
Key=HS
CSG
Key=CS
CS?G
CTHRS Key=CS
C?T,TH?R
HR?C,HS?R
CT
Key=C
C?T
CTRS Key=HS
CH?R,HR?C
HS?R
CHR
Key=CH,HR
CH?R,HR?C
CHS
Key=HS
HS?C
分解树
⑷ 面向 4NF且具有无损连接性的分解。
关系模式 R中存在多值依赖 C HR,T HR，显然由于
C或 T都不含该关系模式的码 HS,∴ R?4NF。
选择 C HR将它分解为 CHR和 CTSG;
再将 CTSG分解为 CT和 CSG。
关系模式 CTHRSG最后无损地分解为 CHR,CT和 CSG，其中每一个关系模式都属于 4NF。
6.1 问题的提出例如,Student(Sno,Sdept,Mname,Cname,Grade)
F={Sno?Sdept,Sdept? Mname,(Sno,Cname)? Grade}
存在问题：
⑴数据冗余太大
⑵插入异常
⑶删除异常
⑷更新异常分解成三个关系模式：
S(Sno,Sdept,Sno?Sdept)；
SG(Sno,Cname,Grade,(Sno,Cname)? Grade)；
D(Sdept,Mname,Sdept? Mname)；
6.2 规范化数据依赖,关系中属性值之间的这种相互依赖又相互制约的联系，称为数据依赖。包括：函数依赖、多值依赖。
一,函数依赖定义 1,设 R(U)是属性集 U上的关系模式。 X,Y是 U的子集。若对于 R(U)的任意一个可能的关系 r,r中不可能存在两个元组在 X上的属性值相等，而在 Y上的属性值不等，则称 X函数决定 Y或 Y函数依赖于 X，记作 X→Y 。
说明,1,函数依赖是语义范畴的概念
2、函数依赖关系是反映属性之间的一般规律根据函数依赖的定义，可找出下面规律：
1、在一个关系模式中，如属性 X,Y有 1,1联系，则存在函数依赖 X→Y,
Y→X,可记作 X?Y
2,X,Y是 1,m联系，则存在 Y→X,但 X\→Y
3,X,Y是 n:m联系，则 X,Y之间不存在任何函数依赖
X→Y,但 Y?X则称 X→Y 是 平凡的函数依赖 。否则，称 非平凡的函数依赖 。
定义 2,在 R（ U）中，如果 X→Y,并且对于 X的任何一个真子集 X′,都有
X′→Y,则 称 Y对 X部分函数依赖,记作 X→pY,否则,称 Y完全函数依赖于
X,记作 X→fY 。
定义 3,在 R（ U）中，如果 X→Y,（ Y?X）,Y \→X,Y→Z,则 称 Z对 X传递函数依赖。
定义 4,设 K为 R<U,F>中的属性或属性组合，若 K f→U 则 K为 R的 候选码 。
若候选码多于一个，则选定其中的一个为 主码 （ Primary Key）。
包含在任何一个候选码中的属性，叫做 主属性 。不包含在任何码中的属性称为 非主属性 或非码属性。整个属性组是码，称为 全码 。
定义 5,关系模式 R中属性或属性组 X并非 R的码，但 X是另一个关系模式的码，则称 X是 R的外部码（ Foreign Key），也称 外码 。
二、码三、范式范式：是符合某一种级别的关系模式的集合。
关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。 1NF,2NF,3NF,BCNF,4NF,5NF
定义：关系模式 R（ U）中所有属性都不可再分的，则称 R是第一范式，记作
R?1NF。
例如,SLC（ SNO,SDEPT,SLOC,CNO,GRADE）
四,2NF
定义 6：若 R?1NF，且每一个非主属性完全函数依赖于码，则 R?2NF。
SNO
CNO
G
SDEPT
SLOC
五,3NF
定义 7：若 R?2NF，且 R中任一非主属性都不传递函数依赖于码，则 R?3NF。
SNO
CNO
G
SDEPT
SLOC
SNO
SLSC
上例 SL分解为,SD（ SNO,SDEPT） DL（ SDEPT,SLOC）
由于第三范式有效地消除了非主属性对码的部分和传递依赖，因而消除了一大类操作异常问题。因此,3NF在数据库设计中得到了广泛应用。
六,BCNF
例,关系模式 STJ（ S,T,J）中,S表示学生,T表示教师,J表示教师,J表示课程。每一教师只教一门课。每门课有若干教师，某一学生选定某门课，
就对应一个固定的教师。
由语义可得到如下的函数依赖：
（ S,J） → T； （ S,T） → J； T →J
关系有两个候选键，是（ S,J）和（ S,T）
S,T,J都是主属性，不存在非主属性，更不会有非主属性对键的传递依赖、
部分依赖了，因此,STJ关系满足第三范式。
但仍然存在问题：
定义 8,R?BCNF，当且仅当每个决定因素都是码（候选键）。
上例分解为,ST（ S,T）,TJ（ T,J）
七、多值依赖例：学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。如下表：
课程 C 教员 T 参考书 B
物理 李勇 普通物理学物理 李勇 光学原理物理 李勇 物理习题集物理 王军 普通物理学物理 王军 光学原理物理 王军 物理习题集数学 李勇 数学分析数学 李勇 微分方程数学 李勇 高等代数数学 张平 数学分析数学 张平 微分方程数学 张平 高等代数
┇ ┇ ┇
定义 9,关系模式 R（ U）,X,Y,Z是 U的子集，并且 Z=U-X-Y。关系模式 R(U)
中多值依赖 XY成立，当且仅当对 R（ U）的任一关系 r，给定的一对（ x,z）
值，有一组 Y的值，这组值仅仅决定于 x值而与 z值无关。
若 XY,而 Z=?即 Z为空，则称 XY为 平凡的多值依赖 。
多值依赖性质：
⑴ 对称性。若 XY,则 XZ，其中 Z=U－Ｘ－Ｙ。
⑵ 传递性。若 XY,ＹＺ，则 XＺ－ Y。
⑶ 函数依赖可看作是多值依赖的特殊情况。若 X?Y，则 XY。
⑷ 若 XY,XＺ，则 XYＺ。
⑸ 若 XY,XＺ，则 XY?Ｚ。
⑹ 若 XY,XＺ，则 XY－Ｚ,XＺ－ Y。
八,4NF
定义 10：关系模式 R<U,F>?1NF，如果对于 R的每个非平凡多值依赖 XY（ Y? X ）,X都含有码，则称 R<U,F>?4NF。
九、规范化小结
1NF
↓ 消除非主属性对码的部分函数依赖
2NF
↓ 消除非主属性对码的传递函数依赖
3NF
↓ 消除主属性对码的部分和传递函数依赖
BCNF
↓ 消除非平凡且非函数依赖的多值依赖
4NF
6.3 数据依赖的公理系统定义 11,对于满足一组函数依赖 F的关系模式 R<U,F>，其任何一个关系 r，若函数依赖 X→Y 都成立，则称 F逻辑蕴含 X→Y 。
Armstrong公理系统,设 U为属性集总体,F是 U上的一组函数依赖，于是有关系模式 R<U,F>。对 R<U,F>来说有以下的推理规则：
A1自反律：若 Y?X? U，则 X?Y为 F所蕴含。
A2增广律：若 X?Y为 F所蕴含，且 Z?U，则 XZ?YZ为 F所蕴含。
A3传递律：若 X?Y及 Y?Z为 F所蕴含，则 X?Z为 F所蕴含。
推论：
合并规则：由 X?Y,X?Z，有 X?YZ。
伪传递规则：由 X?Y,WY?Z，有 XW?Z。
分解规则：由 X?Y及 Z?Y，有 X?Z。
根据合并规则和分解规则，得到一重要事实：
引理 1,X?A1A2 ┅ Ak成立的充分必要条件是 X?Ai成立（ i= 1,2,┅,k）。
定义 12,在关系模式 R<U,F>中为 F所逻辑蕴含的函数依赖的全体叫做 F的闭包,
记为 F+。
定义 13,设 F为属性集 U上的一组函数依赖,X? U,XF+={A| X?A能由 F根据
Armstrong公理导出 },XF+称为属性集 X关于函数依赖集 F的闭包。
引理 2,设 F为属性集 U上的一组函数依赖,X,Y? U,X?Y能由 F根据
Armstrong公理导出的充分必要条件是 Y? XF+ 。
算法 6.1,求属性集 X（ X? U ）关于 U上的函数依赖集 F的闭包 XF+。
步骤,⑴令 X(0)=X,i=0
⑵ 求 B，这里 B={A | (?V) (? W) (V? W? F ∧ V?X(i) ∧ A?W)};
⑶ X(i+1) =B?X(i)
⑷ 判断 X(i+1) =X(i) 吗？
⑸若相等或 X(i+1) =U，则 X(i+1) 就是 XF+,算法终止。
⑹若否，则 i=i+1，返回第⑵步。
例 1 已知关系模式 R<U,F>，其中 U={A,B,C,D,E}；
F={AB?C,B?D,C?E,EC?B,AC?B}。求（ AB） F+。
定义 14,如果 G+=F+，就说函数依赖集 F覆盖 G（ F是 G的覆盖，
或 G是 F的覆盖），或 F与 G等价。
引理 3,F+ = G+的充分必要条件是 F?G+,和 G? F+ 。
定义 15,如果函数依赖集 F满足下列条件，则称 F为一个极小函数依赖集。亦称为最小依赖集或 最小覆盖 。
⑴ F中任一函数依赖的右部仅含有一个属性。
⑵ F中不存在这样的函数依赖 X?A，使得 F与 F－ {X?A}等价。
⑶ F中不存在这样的函数依赖 X?A,X有真子集 Z使得
F－ {X?A}?{Z?A}与 F 等价。
例,F={A?B,B?A,B?C,A?C,C?A} 求 Fm 。
Fm1={A?B,B?C,C?A}
Fm2={A?B,B?A,A?C,C?A}
6.4 模式的分解
分解具有“无损连接性”
分解要“保持函数依赖”
分解既要“保持函数依赖”，又要具有“无损连接性”。
定义 16,关系模式 R<U,F>的一个分解是指 ρ＝ {R1<U1,F1>,R2<U2,F2>,…,
Rn<Un,Fn>} 其中 U=?Ui，并且没有 Ui?Uj,1≤ｉ,j ≤ n,Fi是 F在 Ui上的投影。
定义 17,函数依赖集合 {X? Y|X? Y? F+ ∧ XY?Ui}的一个覆盖 Fi叫做 F在属性 Ui上的投影。
一、模式分解的三个定义例：已知关系模式 R<U,F>，其中 U={SNO,SDEPT,MN},F={SNO? SDEPT,
SDEPT?MN}。
分解,ρ1＝ {R1<SNO,?>,R2<SDEPT,? >,R3<MN,?>}
ρ2＝ {R1<{SNO,SDEPT},{SNO?SDEPT}>,R2<{SNO,MN},{SNO? MN} >}
ρ3＝ {R1<{SNO,SDEPT},{SNO?SDEPT}>，
R2<{SDEPT,MN},{SDEPT? MN} >}
二、分解的无损连接性和保持函数依赖性定义 18,ρ ＝ {R1<U1,F1>,…,Rk<Uk,Fk>}是 R<U,F>的一个分解，若 R<U,F>
的任何一个关系 r均有 r=m ρ (r)成立，则称分解 ρ 具有无损连接性。简称 ρ 为无损分解。
算法 6.2,判别一个分解的无损连接性。 ρ ＝ {R1<U1,F1>,…,Rk<Uk,Fk>}是
R<U,F>的一个分解,U={A1,…,An},F＝ {FD1,FD2,…,FDρ },F是一极小依赖集,记 FDi为 Xi?A1i。
⑴ 建立一张 n列 k行的表。每一列对应一个属性，每一行对应分解中的一个关系模式。若属性 Aj属于 Ui，则在 j列 i行交叉处填上 aj，否则填上 bij ；
⑵ 对每一个 FDi做下列操作：找到 Xi所对应的列中具有相同符号的那些行。考察这些行中 li列的元素，若其中有 ali，则全部改为 ali ；否则全部改为 bmli ； m是这些行的行号最小值。
⑶ 比较扫描前后，表有无变化。如有变化，则返回第⑵步，否则算法终止。
例,已知 R<U,F>,U＝ {A,B,C,D,E},F={AB? C,C?D,D?E},R的一个分解为 R1(A,B,C),R2(C,D),R3(D,E)。
⑴ 首先构造初始表，如图
A B C D E
a1 a2 a3 b14 b15
b21 b22 a3 a4 b25
b31 b32 b33 a4 a5
⑵ 对 AB?C，因各元组的第 1,2列没有相同的分量，所以表不改变。由 C?D
可以把 b14改为 a4,再由 D?E可使 b15,b25全改为 a5。
A B C D E
a1 a2 a3 a4 a5
b21 b22 a3 a4 a5
b31 b32 b33 a4 a5
定理,R<U,F>的一个分解 ρ ＝ {R1<U1,F1>,R2<U2,F2>}具有无损连接性的充分必要条件是,U1∩U2? U1－ U2? F+ 或 U1∩U2? U2－ U1? F+ 。
⑴ 若要求分解保持函数依赖，那么模式分离总可以达到 3NF，
但不一定能达到 BCNF;
⑵ 若要求分解既保持函数依赖，又具有无损连接性，可以达
到 3NF，但不一定能达到 BCNF;
⑶ 若要求分解具有无损连接性，那一定可达到 4NF;
当关系模式 R分解为两个关系模式 R1,R2时有下面的判定准则。
定义 19,若 F+ ＝（ ∪ Fi） ＋,则 R<U,F> 的分解 ρ ＝ {R1<U1,F1>,…,
Rk<Uk,Fk>}保持函数依赖。
三、模式分解的算法关于模式分解的几个重要事实是：
算法 6.3 转换为 3NF的保持函数依赖的分解
⑴ 对 R<U,F> 中的函数依赖集 F进行“极小化处理”，
仍记为 F。
⑵ 找出不在 F中出现的属性，把这样的属性构成一个
关系模式。把这些属性从 U中去掉，剩余的属性仍
记为 U。
⑶ 若有 X? A? F，且 XA=U，则 ρ＝ {R}，算法终止。
⑷ 否则，对 F按具有相同左部的原则分组（假定分为
k组）,每一组函数依赖 Fi′所涉及的全部属性形成
一个属性集 Ui 。若 Ui?Uj (i≠j)就去掉 Ui 。
算法 6.4 转换为 3NF既有无损连接性又保持函数依赖的分解
⑴ 设 X 是 R<U,F> 的码。 R<U,F> 已由算法 5.3分解为
ρ ＝ {R1<U1,F1>,R2<U2,F2>,…,Rk<Uk,Fk>}，
令?＝ ρ ∪ { Rx<U,Fx> } 。
⑵ 若有某个 Ui,X? Ui,将 Rx<U,Fx> 从? 中去掉。
把这些属性从 U中去掉，剩余的属性仍记为 U。
⑶? 就是所求的分解。
算法 6.5 转换为 BCNF的无损连接的分解
⑴ 令 ρ ＝ {R<U,F>}
⑵ 检查 ρ 中各关系模式是否均属于 BCNF。若是，则算法终止。
⑶ 设 ρ 中 Ri<Ui,Fi>不属于 BCNF,那么必有 X? A? Fi+ (A?X)，
且 X非 Ri的码。因此,XA是 Ui的真子集。对 Ri进行分解：
＝ {S1,S2},Us1=XA,Us2=Ui-{A}，以?代替 Ri<Ui,Fi>返回第
⑵ 步。
算法 6.6 达到 4NF的具有无损连接性的分解
⑴ 令 ρ ＝ {R}
⑵ 检查 ρ 中所有关系模式，如均为 4NF，则转 ⑷ 。
⑶ ρ 中找非 4NF的关系模式 S,S中必有一个多值依
赖 X Y,其中 X不包含 S的关键字,Y既非
空又不是 X的子集，且 XY≠S。用 S1=XY 和
S2=S－ Y代替 S。返回 ⑵。
⑷ 停止分解，输出 ρ 。
例子,关系模式 CTHRSG，其中 C表示课程,T表示教师,H表示时间,R表示教室,S表示学生,G表示成绩。函数依赖集 F及其所反映的语义分别为：
C?T 每门课程仅有一位教师担任。
HT?R 在任一时间，一个教师只能在一个教室上课。
HR?C 在任一时间，每个教室只能上一门课。
HS?R 在任一时间，每个学生只能在一个教室听课。
CS?G 每个学生学习一门课程只有一个成绩。
解,HS?CTHRSG,HS是关系模式的关键字。
⑴ 面向 3NF且保持函数依赖的分解。
最小函数依赖集为 F={C?T,CS?G,HR?C,HS?R,TH?R}
分解为,?＝ {CT,CSG,HRC,HSR,THR}
⑵ 面向 3NF既有无损连接性又保持函数依赖的分解。
∵ HS是关键字,?＝? ∪ { HS },HS是 HSR的一个子集
∴ 分解仍为,?＝ {CT,CSG,HRC,HSR,THR}
⑶ 面向 BCNF且具有无损连接性的分解。
CTHRSG
Key=HS
CSG
Key=CS
CS?G
CTHRS Key=CS
C?T,TH?R
HR?C,HS?R
CT
Key=C
C?T
CTRS Key=HS
CH?R,HR?C
HS?R
CHR
Key=CH,HR
CH?R,HR?C
CHS
Key=HS
HS?C
分解树
⑷ 面向 4NF且具有无损连接性的分解。
关系模式 R中存在多值依赖 C HR,T HR，显然由于
C或 T都不含该关系模式的码 HS,∴ R?4NF。
选择 C HR将它分解为 CHR和 CTSG;
再将 CTSG分解为 CT和 CSG。
关系模式 CTHRSG最后无损地分解为 CHR,CT和 CSG，其中每一个关系模式都属于 4NF。
