1
第 9章 关系数据理论
9.1 基本概念
9.2 函数依赖的公理系统
9.3 规范化
9.4 模式分解
2
9.1 基本概念
函数依赖
术语和符号
为什么要讨论函数依赖？
模式分解
3
函数依赖
Y=f(X)
函数
Y=sin(X)
Y=X+1 Y=X2+2X+1
省 =f(城市 ) 姓名 =f(学号 )
4
函数依赖的直观定义：
如果有一个关系模式 R(A1,A2,…,A n),X和 Y
为 {A1,A2,…,A n}的子集，那么对于关系 R中的任意
一个 X值，都只有一个 Y值与之对应，则称 X函数
决定 Y,或 Y函数依赖于 X,并用 X→Y 表示。
5
例：对仓库关系
仓库 (仓库号,城市,面积 )
有函数依赖：
仓库号 → 城市 （ 城市 函数依赖于 仓库号 ）
仓库号 → 面积 （ 面积 函数依赖于 仓库号 ）
6
函数依赖的严格形式化定义
定义 9.1,设有关系模式 R(A1,A2,…,An),X和 Y均
为 {A1,A2,…,An}的子集,r是 R的任一具体关系，
t1,t2是 r中的任意两个元组；如果由 t1[X]=t2[X]
可以推导出 t1[Y]=t2[Y],则称 X函数决定 Y,或 Y
函数依赖于 X,记为 X→ Y。
7
注意定义 9.1中：
t1[X]=t2[X] t1[Y]=t2[Y]
8
术语和符号 (1)
如果 X→Y, 但 Y不包含于 X,则称 X→Y
是非平凡的函数依赖。如不特别说明，我们
总是讨论非平凡函数依赖。
如,(学号,课程号 )→ 成绩
如,(学号,所在系 )→ 所在系
非平凡依赖
平凡依赖
9
术语和符号 (2)
如果 Y不函数依赖于 X,则记作 X Y。
如 学号 不函数依赖于 性别,
则记作 性别 学号 。
10
术语和符号 (3)
如果 X→Y, 则 X称作决定因素。
如 学号 → 所在系,则 学号 称作决定因素
11
用 U表示关系模式 R的属性全集，
即 U={A1,A2,…,An},用 F表示关系模
式 R上的函数依赖集，则关系模式 R
可表示为 R(U,F)。
术语和符号 (4)
如 U={仓库号,城市,面积 }
F={仓库号 → 城市,仓库号 → 面积 }
则 R(U,F)表示仓库关系
12
术语和符号 (5)
如果 K是关系模式 R(U,F)的任一候选关键
字,X是任一属性或属性集，如果 X?K,则 X
称为主属性；否则称为非主属性。
如 (仓库号,器件号 )是 库存 关系的关键
字，那么 仓库号 和 器件号 均是主属性，而
数量 为非主属性。
13
术语和符号 (6)
如果 X→ Y,并且 Y→ X,则可记作 X←→ Y。
14
术语和符号 (7)
如果 X→ Y,并且对于 X的一个任意真子集 X/
都有 X/ Y,则称 Y完全函数依赖于 X,并记
作 ；如果 X/ → Y成立，则称 Y部分函数
依赖于 X,并记作 。
YX f? ??
YX p? ??
如,(学号,课程号 )→ 成绩 是完全函数依赖
而,(学号,所在系 )→ 系主任 是部分函数依赖
15
术语和符号 (8)
如果 X→ Y（ 非平凡函数依赖，并
且 Y X）,Y→ Z,则称 Z传递函数
依赖于 X。
如 学号 → 专业, 专业 → 所在系,则 所
在系 传递函数依赖于 学号 。
16
17
设有库存关系：
数据冗余问题
数据更新问题
数据插入问题
数据删除问题
18
为什么会出现以上种种操作异常现象呢？
因为这个关系模式没有设计好，在它的
某些属性之间存在着, 不良, 的函数依赖。
如何改造这个关系模式？克服以上种种问题，
就是我们这一章要解决的根本问题，也是我
们要讨论函数依赖的根本原因。
19
模式分解
解决各种操作异常现象的方法就是
进行模式分解，即把一个关系模式分解
成两个或多个关系模式，在分解的过程
中消除那些, 不良, 的函数依赖，从而
获得好的关系模式。
20
分解举例
仓库 （ 仓库号, 地点 ）
设备 （ 设备号, 设备名 ）
库存 （ 仓库号, 设备号, 库存数量 ）
刚才提到的 库存 关系模式，我们可以把其分解为：
21
注意：
模式分解不能破坏原来的语义；
模式分解必须遵守：
? 无损连接分解；
? 保持函数依赖分解。
无损连接是指
分解后的关系经过
自然连接可以恢复
成原来的关系。
保持函数依赖是指
分解后的关系不能破坏
原来的函数依赖（不能
破坏原来的语义）。
22
函数依赖的公理系统
Amstrong公理的内容及正确性
Amstrong公理的推论
逻辑蕴涵和闭包
公理的完备性
闭包的计算
函数依赖集的等价和最小化
23
Amstrong公理：
设有关系模式 R(U,F),X,Y,Z均为 U
的子集, 推理规则如下：
① 自反律, 如果 Y?X,则 X→ Y；
② 增广律, 如果 X→ Y,则 XZ→ YZ；
③ 传递律, 如果 X→ Y,Y→ Z,则 X→ Z 。
24
定理 9.1,Amstrong公理是正确的。
25
证明自反律,
设 Y?X ? U
对关系模式 R的任一关系 r 中的
任意两个元组 t和 s,如果 t[X]=s[X]，
由于 Y ? X,所以 t[Y]=s[Y],由定义
9.1有 X→ Y成立, 自反律得证 。
26
证明增广律,
设 X→ Y,且 Z?U,r,t,s的含义同上
如果 t[XZ]=s[XZ],则一定有
t[X]=s[X]和 t[Z]=s[Z]
又根据 X→ Y可有 t[Y]=s[Y]
由 t[Y]=s[Y]和 t[Z]=s[Z]可得 t[YZ]=s[YZ]
即由 t[XZ]=s[XZ]推导出了 t[YZ]=s[YZ]
由定义 9.1有 XZ→ YZ成立, 增广律得证 。
27
证明传递律,
设 X→ Y,Y→ Z,r,t,s的含义同上
如果 t[X]=s[X],由于 X→ Y,根据定义 9.1可得 t[Y]=s[Y]
同理由于 Y→ Z,可得 t[Z]=s[Z]
即由 t[X]=s[X]推导出了 t[Z]=s[Z]
根据定义 9.1 X→ Z成立, 传递律得证 。
28
Amstrong公理的推论：
推论 ① - 合并规则：如果 X→ Y,X→ Z,则
X→ YZ；
推论 ② -分解规则：如果 X→ YZ,则 X→ Y、
X→ Z；
推论 ③ -伪传递规则：如果 X→ Y,YW→ Z,则
XW→ Z。
29
定理 9.2,Amstrong公理
的三个推论是正确的。
30
证明合并规则：
设 X→ Y,X→ Z
根据增广律分别有 X→ XY,XY→ YZ
又根据传递律有 X→ YZ,合并规则得证 。
31
证明分解规则,
设 X→ YZ
根据自反律有 YZ→ Y和 YZ→ Z
又根据传递律分别有 X→ Y和 X→ Z，
分解规则得证 。
32
证明伪传递规则：
设 X→ Y,YW→ Z
根据增广律有 XW→ YW
又根据传递律有 XW→ Z,伪传递规则得证 。
33
引理 9.1
引理 9.1,X→ A1A2… An的充分必要条件
是 X→ Ak成立 (k=1,2,…,n)。
根据合并规则和分解规则可以得出
如下重要结论：
34
逻辑蕴涵和闭包
有时需要根据给定的一组函数依赖来
判断另外一些函数依赖是否成立，这就是
函数依赖逻辑蕴涵所要研究的内容。
比如有关系模式 R(U,F),U={A,B,C}，
F={A→B,B → C}, 问 A → C 是否也成立？
35
逻辑蕴涵
定义 9.2：设有关系模式 R(U,F)，
X?U,Y ? U,如果从 F中的函数依赖能
够推导出 X→ Y,则称 F逻辑蕴涵 X→ Y，
或称 X→ Y是 F的逻辑蕴涵。
36
闭包
定义 9.3 在关系模式 R(U,F)中，被 F 所逻
辑蕴涵的函数依赖的全体称作 F 的闭包，
记为 F + 。
37
闭包计算举例
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
,,,,
,,,,
,,,,
,,,,
,,,,,,
,,,,,,
,,,,,,
,,,,,,
X Y ZX Y ZX Y ZXZX Y ZXYX Y ZX
YZX Y ZYZXZYZXYYZX
XZX Y ZXZXZXZXYXZX
XYX Y ZXYXZXYXYXYX
YZYZYZYZX Y ZZXZZXYZX
ZYZZYYX Y ZYXZYXYYX
ZZYYZYYXX Y ZXXZXXYXX
ZYZYX Y ZXZXYX
→→→→
→→→→
→→→→
→→→→
→→→→→→
→→→→→→
→→→→→→→
Φ→Φ→Φ→Φ→Φ→Φ→Φ→
假设有关系模式 R(U,F),U={X,Y,Z}，
F={X→ Y,Y→ Z},则 F+ 为：
38
属性集闭包
39
计算属性集闭包举例
?FX
?FX
?FX
如果 X={A},则：
＝｛ A,B,C｝
如果 X={B},则
＝｛ B,C｝
如果 X={C},则
＝｛ C｝
设有关系模式 R(U,F),U={A,B,C},F={A→ B,B→ C}
40
公理的完备性
建立一套公理系统必须明确两个问题：
一是能否保证按公理推导出的函数依赖都是正确的, 即
这些函数依赖是否都属于 F+； 也就是说对于关系模式
R(U,F),只要 F中的函数依赖为真, 则用公理根据 F推导
出的函数依赖也一定为真, 这就是公理的正确性；
另外一个问题是：用公理能否推导出所有的函数依赖？
也就是说 F+中所有的函数依赖是否都能用公理推导出来？
这是一个很重要的问题, 因为如果 F+中有函数依赖不能
用公理推导出来, 那么就说明这些公理不够用, 不完全,
就必须补充新的公理, 这就是公理的完备性问题 。
41
引理 9.2
42
引理 9.2充分性证明,YXXY F ??? ?
43
引理 9.2必要性证明,????
FXYYX
44
公理的完备性还可以理解为：
所有不能用公理推导出的函数依赖
都不为真，即如果 X→ Y不能根据 F用公理
导出，则 X→ Y? F+ 。 或者说存在一个具
体的关系 r,F+ 中的所有函数依赖都满足
r,而不能用公理推导出的 X→ Y不满足 r。
也就是说，不能根据 F用公理导出的函数
依赖不属于 F+ 。 如果我们能够找到这样
的 r,则公理的完备性证明问题就解决了。
45
定理 9.3,Amstrong公理是完备的。
为了证明公理的完备性，找到了如下具体的关系 r：
如果能够证明以下两点，则公理的完备性问题就
证明了：
⑴在关系 r中,F + 中的所有函数依赖都成立；
⑵在关系 r中，不能根据 F用 Amstrong公理推导出的
函数依赖 X→ Y不成立。
46
证：在关系 r中,F+ 中的所
有函数依赖都成立
47
证,在关系 r中，不能根据 F用 Amstrong公理推
导出的函数依赖 X→ Y不成立
48
由公理的完备性和引理 9.2有结论：
?? ???? FXYFYX
49
属性集闭包的计算
50
算法 9.1：
51
例：设有 R（ U,F）,U={A,B,C,D,E}，
F={AB→ C,B → D,C → E,EC → B,AC → B}
求 ?
FAB)(
?FAB)( {A,B,C,D,E}=
52
函数依赖集的等价和最小化
53
覆盖和等价的定义
定义 9.5 设 F和 G是两个函数依赖集：
① 如果 F +?G +,则称 G是 F的一个覆盖,
或称 G覆盖 F；
② 如果 F +?G +和 G +?F +同时成立,
即 F +=G +,则称 F和 G等价 。
54
引理 4.3
F+=G+的充分必要条件是 F?G+并且 G ? F+。
必要性证明：
充分性证明：
55
F+=G+ ? F?G+并且 G ? F+ 为判定两个函
数依赖集是否等价提供了简便方法：
可以首先检查 F中的每个函数依赖 X→ Y是否属
于 G+（ 即计算 Y是否属于 XG+）？ 如果对 F中的每
个函数依赖都有 X→ Y?G+,则有 F?G+ ；然后用
同样的方法再检查 G?F+是否成立？ 如果它们都成
立则 F和 G等价 。
56
研究函数依赖集等价的目的
研究函数依赖集等价的目的是为了对指
定函数依赖集找出它的最小函数依赖等
价集，即找出包含函数依赖尽可能少、
甚至最少的函数依赖等价集，从而使模
式分解简化，分解出最简单的关系模式。
57
最小函数依赖集的定义
定义 9.6 如果函数依赖集 F满足如下条件, 则称
F 为一个最小函数依赖集, 也称为极小函数依
赖集或最小覆盖：
① F 中任一函数依赖的右部都仅含有一个属
性；
② F中不存在这样的函数依赖 X→ A,X有真子
集 Z,使得 F与 F-{X→ A} ∪ {Z→ A}等价；
③ F中不存在这样的函数依赖 X→ A,使得 F与
F-{X→ A}等价 。
58
例,假设有属性集 U={A,B,C,D,E},函数依
赖集 F={A→ B,B→ C,AD→ E}和函数依赖集
G={A→ B,A→ C,B→ C,AD→ E},问 F和 G是
否是最小函数依赖集？
答案,F是最小依赖集,G不是最小依赖集。
59
引理 9.4
60
引理 9.4必要性证明
61
引理 9.4充分 性证明
62
引理 9.5
设 X→ A是 F中任意函数依赖,G=F-{X→ A}，
F与 G等 价的充分必要条件是 。??
GXA
必要性证明
充分性证明
63
计算最小覆盖的算法
算法 9.2 给定函数依赖集 F,求其最小覆盖的过
程如下：
? 逐一检查 F 中各函数依赖 X→ Y,若 Y=A1… Ak,k>=2，
则用 {X→ Aj | j=1,…,k}来取代它（分解规则）；
? 逐一取出 F中各函数依赖 X→ A,若 X=B1B2… Bm,m>=2，
则逐一考查 Bj（ j=1,…,m）,如果,则 F
与 F-{X→ A} ∪ {(X-Bj)→ A}等价（引理 9.4），故以 X-
Bj取代 X；
? 逐一检查 F中各函数依赖 X→ A,令 G=F-{X→ A},根据
引理 9.5，如果,则 F与 G等价，故从 F中去掉
X→ A。
??? FjBXA )(
?? GXA
64
例,已知 F={A→ B,B→ A,B→ C,A→ C,C→ A}，
求 F的最小覆盖。
逐一检查 F中的函数依赖是否多余，如
果多余则可以去除之，最后的结果为：
{A → B,B → C,C→ A}
65
注意：算法 9.2的第 2,3两
步是不可以颠倒的。
66
设 F={C?A,A ? D,CD ? B,B ? A}
依照算法 9.2先既约化后无冗余化
既约化
令 G=F-{CD ? B}?{C ? B}
结果 G与 F等价
G= {C?A,A ? D,C ? B,B ? A}
无冗余化
结果所求最小覆盖为
F’={A ? D,C ? B,B ? A}
67
设 F={C?A,A ? D,CD ? B,B ? A}
先无冗余化后既约化
无冗余化
结果没有多余的函数依赖
既约化
结果 G= {C?A,A ? D,C ? B,B ? A}
它不是最小覆盖，因为 C?A这时是多余的函数依赖。
68
规范化
规范化的目的就是要设计“好”的
关系，使关系尽量减少操作异常甚至拒
绝操作异常现象。
69
第一范式
每个关系模式都应满足最低要求：
所有分量都必须是不可分的最小数据项，
并把其称为第一范式（ 1NF） 关系。
70
非规范化表格和规范化表格
71
第二范式
定义 9.7 如果 R(U,F) ∈ 1NF,并且 R中
的每个非主属性都完全函数依赖于关键字,
则 R(U,F) ∈ 2NF。
72
库存 A关系实例：
仓库号 设备号 数量 地点
WH 1 D4 675 北京
WH 1 D7 250 北京
WH 2 D2 280 上海
WH 2 D4 200 上海
WH 2 D9 270 上海
WH 3 D2 550 广州
WH 3 D4 230 广州
WH 4 D5 550 北京
数据冗余
插入异常
更新异常
删除异常
73
为了解决操作异常分解后的关系：
库存 B(仓库号,设备号,数量 )
仓库 B(仓库号,地点 )
74
第三范式
定义 9.8 如果 R(U,F) ∈ 2NF,并且所
有非主属性都不传递依赖于关键字，则
R(U,F) ∈ 3NF。
75
仓库 A关系实例 仓库号 所在省 仓库面积 所在城市
WH2 1 湖北 675 武汉
WH2 2 河北 250 邯郸
WH2 3 湖北 280 武汉
WH2 4 广东 200 广州
WH2 5 湖北 270 武汉
WH2 6 广东 550 广州
数据冗余
插入异常
更新异常
删除异常
76
为了解决操作异常分解后的关系：
仓库 B(仓库号,仓库面积,所在城市 )
城市 (省,城市 )
77
BC范式
78
关系模式实例：
管理 (仓库号，设备号，职工号 )
它所包含的语义是：
① 一个仓库可以有多个职工；
② 一名职工仅在一个仓库工作；
③ 在每个仓库一种设备仅由一名职工保管 （ 但
每名职工可以保管多种设备 ） 。
根据以上语义有函数依赖：
职工号 → 仓库号
(仓库号, 设备号 )→ 职工号
79
进一步理解前述语义：
80
为了解决操作异常现象如何进行分解？
任何分解都会破坏函数依赖：
（仓库号，设备号） ?职工号
结论：不将 3NF分解成 BCNF！
81
如何解决非 BCNF带来的操作异常现象？
不可能靠模式分解来解决问题，只
有靠应用程序或设计数据库时建立一些
必要的约束来预防操作异常现象的发生。
如第 6章介绍的触发器。
82
多值依赖与第四范式
在关系模式上不仅存在函数依赖，还存在着
其他的“依赖”影响着关系模式的质量，如多值
依赖。
83
讨论：三个实体之间的联系
? 每个仓库可以存放多种设备, 每名职工管理一个仓库中
的所有设备；
? 每名职工可以管理多个仓库的设备；
? 每种设备可以存放在多个仓库 。
示意数据
84
关键字是 (仓库号,职工号,设备号 )，即 All-Key
BCNF
是否还存在操作异常现象？为什么？
例如, 职工 E4新分配到 WH1仓库工作, 这时必须插
入如下 3个元组：
WH1 E4 P1
WH1 E4 P2
WH1 E4 P3
同样, 如果 P3不再存放在 WH1仓库, 这时则要删除
多个元组：
WH1 E1 P3
WH1 E2 P3
WH1 E4 P3
排列成关系
85
多值依赖的定义
定义 9.10 设有关系模式 R(U),X,Y,Z
是 U的子集, Z=U-X-Y,如果对于 X的一个给
定值, 存在一组 Y值与其对应, 而 Y的这组值
又不以任何方式与 Z的值相关, 则说 Y多值依
赖于 X,记为 X→→ Y。
若 Z=Φ（ 即 Z为空），则将多值依赖
X→→ Y称为平凡的多值依赖。
86
在下表所示的关系上：
给定一个仓库号值, 有一组职工号与其对应，而
这组职工号值与设备号值没有任何依赖关系，所
以 仓库号 →→ 职工号 ；
同样 仓库号 →→ 设备号 ；
多值依赖具有对称的性质，即如果 X→→ Y,并且
Z=U-X-Y,则 X→→ Z也成立。
87
函数依赖可以看作是
多值依赖的特例。
88
第四范式
定义 9.11 设关系模式 R(U,D)∈ 1NF,若
对每个非平凡的多值依赖 X→→ Y,X都含有侯
选关键字, 则 R(U,D)∈ 4NF。
?从定义可以看出,4NF限定了在关系模式的属性
间不允许有非平凡、且非函数依赖的多值依赖。
?这是因为，若 X→→ Y是非平凡的多值依赖，且 X
含有侯选关键字，则有 X→ Y,所以 4NF所允许的非
平凡的多值依赖实际上就是函数依赖。
?4NF自然是 BCNF
89
非 4NF关系到 4NF关系的转换仍然是通过分解，
上表所示的关系显然不是 4NF,可以分解为：
?职工 (仓库号,职工号 )
?存放 (仓库号,设备号 )
分解结果都是 4NF关系。
90
规范化小结
91
模式分解
模式分解的准则
3NF无损连接和保持函数依赖算法
使分解后的关系模式数最少
92
模式分解的准则
?模式分解具有无损连接性；
?模式分解能够保持函数依赖。
93
无损连接的形式定义：
94
保持函数依赖的形式定义：
定义 9.13 若,则 R(U,F)的分解
ρ ={R1(U1,F1),…,Rk(Uk,Fk)}保持函数依赖
。
?
k
i
iFF
1
)(
?
?? ?
95
设有关系模式 R（ U,F）,U={emp,wh,city}，
F={emp→ wh,wh→ city},其中 emp是职工号,wh是
仓库号,city是仓库所在城市；从 F中可以看出，一名职
工只能在一个仓库工作，一个仓库只能位于一个城市。
看如下的三个分解是否满足无损连接和保持函数依
赖的特性：
ρ 1={R1(emp,Φ),R2(wh,Φ ),R3(city,Φ)}
ρ 2={R1({emp,wh},{emp→wh }),
R2({emp,city},{ emp→city })}
ρ 3= {R1({emp,wh},{emp→wh }),
R2({wh,city},{ wh→city })}
96
为了得到更高范式的关系进行的模
式分解，是否总能既保证无损连接、又
保持函数依赖？
如果要求分解保持函数依赖, 那么模式分解总可
以达到 3NF,但是不一定能达到 BCNF；
如果要求分解具有无损连接的特性, 那么一定可
以达到 BCNF；
如果要求分解既保持函数依赖, 又具有无损连接
的特性, 那么分解可以达到 3NF,但是不一定能
达到 BCNF。
97
例：设有关系模式 R（ U,F）,U={A,B,C}，
F={AB→ C,C→ B},该关系模式是 3NF的，因为存
在一个主属性对非主属性的函数依赖 C→ B,所以
该模式不是 BCNF。
为了达到 BCNF就必须进行分解，但是任何
分解都会破坏函数依赖 AB→ C。 所以为了保持
函数依赖，就必须放弃 BCNF。
98
在实践中 BCNF的意义并不大, 因为我们对模
式分解的要求总是既要保证无损连接, 又要保持
函数依赖 。 那么, 当一个关系是 3NF时：
? 关键字是单属性时, 该模式自然是 BCNF；
? 关键字是复合属性, 并且不存在主属性对非主
属性的函数依赖, 则该模式自然是 BCNF；
? 关键字是复合属性, 并且至少存在一个主属性
对非主属性的函数依赖, 则为了保持函数依赖,
模式分解无法达到 BCNF。
99
判断一个分解是否保持函数依
赖, 可以根据函数依赖的最小覆
盖和等价来判断 。
100
判断一个分解是否具有无损连接特性
可以用如下法则：关系模式 R分解为 R1和
R2是无损连接分解的充分必要条件是：
R1 ∩ R2 → R1 - R2
或
R1 ∩ R2 → R2 – R1
101
3NF无损连接和保持函数依赖算法
102
对 R（ U,F） 中的 F进行最小化处理, 即计算 F的最小覆盖,
并将最小等价依赖集仍然记为 F；
若有 X→ A,并且 X∪ A=U,则 ρ ={R},算法终止 ；
找出不在 F中出现的属性 （ 即与 F中任意函数依赖的左部和
右部都无关的属性 ）, 把这样的属性构成一个关系模式
R0（ U0,Φ ）, 并把 U0从 U中去掉, 剩余的属性仍然记为 U；
对 F按具有相同左部的原则进行分组 （ 假定分为 k组 ）, 每
一组函数依赖 Fi所涉及的全部属性形成属性集 Ui,若 Ui?Uj
（ i<>j）, 就去掉 Ui ；
经过以上步骤得到的分解 ρ ={R0,R1,…, Rk}（ R0可能为
空, 1… k可能不连续 ） 构成 R的一个保持函数依赖的分解,
并且每个 Ri均为 3NF；
设 X是 R（ U,F） 的关键字, 并令 τ =ρ ∪R X（ X,FX） ；
若对某个 Ui, 如果 X?Ui, 则将 RX 从 τ 中去掉, 或 Ui?X，
则将 Ri从 τ 中去掉；
最后 τ 就是所求分解 。
3NF
保
持
函
数
依
赖
和
无
损
连
接
的
分
解
算
法
103
3NF无损连接和保持函数依赖算法举例
104
使分解后的关系模式数最少
105
算法 9.3已经保证了：
?3NF分解；
?保持函数依赖分解；
?无损连接分解；
一般为了操作方便，我们还希望：
分解的关系模式数最少
106
设有函数依赖集合,F={A→ B,A→ C,B→ A，
B→ C,AE→ D,BD→ G,D→ E}
利用算法 9.2求得的最小覆盖集是：
F’={A→ B,B→ A,B→ C,AE→ D,BD→ G，
D→ E}
按照算法 9.3得到的模式分解是：
τ={R1({A,B,C},{B→ AC,A→ B})，
R2({A,E,D},{AE→ D,D→ E})，
R3({B,D,G},{BD→ G})}
107
还是刚才那个依赖集,F={A→ B,A→ C，
B→ A,B→ C,AE→ D,BD→ G,D→ E}
利用算法 9.2求得的最小覆盖集是：
F’={A→ B,B→ A,B→ C,AE→ D,BD→ G,D→ E}
注意,(AE)F’+={A,B,C,D,E,G}
所以 AE → BD和 AE → G?F’+
设 F”=F’∪ {AE→BD, AE→G}
显然有 F’与 F”等价 。 根据 F”再计算最小覆盖, 结果是：
Fm={A→ B,B→ A,B→ C,AE→ D,AE→ G,D→ E}
分解结果是,R1(A,B,C),R2(A,D,E,G)
108
定义 9.14：若 G是 F所有等价集
中函数依赖个数最少的，则称
G是 F的最小等价集。
109
定义 9.15 设 Γ(X→ Y,F)={V→ W|V→ W∈ F,V→ W
参与推导 X→ Y },Δ(X,F)={V→ W| V→ W∈ F,V→ X
∈ F+,X→ V ∈ F+},则当 Γ(X→ Y,F)∩Δ(X,F)=Φ，
Y∈ XF+ 时，称 X直接决定 Y,记为 。
YX ?
定义中 Γ(X→ Y,F)表示包含在 F中推导 X→ Y时
用到的全部函数依赖； Δ(X,F)表示依赖集 F中函数
依赖的左部与 X能相互决定的函数依赖集，或称
左部与 X等价的函数依赖集。
X直接决定 Y也可以叙述为 Γ(X→ Y,F)中所有函
数依赖的左部都不能决定 X 。
110
算法 9.4 设 F是无冗余和既约化的函数依赖集，求
F的最小等价集的算法如下：
1.把 F中的函数依赖按左部等价进行分组；
2.任一组中，若存在 X→ V,Y→ W并且 X直接决
定 Y,则把它们合并为 Y→ VW，直到任一组中都
不存在如此依赖对为止。
111
【本章小节】
本章的内容是关系数据理论，它是关系
数据模型的重要理论基础，该理论可以
指导关系数据库或关系模式的设计。关
系的范式是对关系规范化程度的一个衡
量标准，原则上规范化程度越高，关系
的质量越好。关系的规范化过程是模式
分解的过程，模式分解需要遵守保持函
数依赖和无损连接的原则。
第 9章 关系数据理论
9.1 基本概念
9.2 函数依赖的公理系统
9.3 规范化
9.4 模式分解
2
9.1 基本概念
函数依赖
术语和符号
为什么要讨论函数依赖？
模式分解
3
函数依赖
Y=f(X)
函数
Y=sin(X)
Y=X+1 Y=X2+2X+1
省 =f(城市 ) 姓名 =f(学号 )
4
函数依赖的直观定义：
如果有一个关系模式 R(A1,A2,…,A n),X和 Y
为 {A1,A2,…,A n}的子集，那么对于关系 R中的任意
一个 X值，都只有一个 Y值与之对应，则称 X函数
决定 Y,或 Y函数依赖于 X,并用 X→Y 表示。
5
例：对仓库关系
仓库 (仓库号,城市,面积 )
有函数依赖：
仓库号 → 城市 （ 城市 函数依赖于 仓库号 ）
仓库号 → 面积 （ 面积 函数依赖于 仓库号 ）
6
函数依赖的严格形式化定义
定义 9.1,设有关系模式 R(A1,A2,…,An),X和 Y均
为 {A1,A2,…,An}的子集,r是 R的任一具体关系，
t1,t2是 r中的任意两个元组；如果由 t1[X]=t2[X]
可以推导出 t1[Y]=t2[Y],则称 X函数决定 Y,或 Y
函数依赖于 X,记为 X→ Y。
7
注意定义 9.1中：
t1[X]=t2[X] t1[Y]=t2[Y]
8
术语和符号 (1)
如果 X→Y, 但 Y不包含于 X,则称 X→Y
是非平凡的函数依赖。如不特别说明，我们
总是讨论非平凡函数依赖。
如,(学号,课程号 )→ 成绩
如,(学号,所在系 )→ 所在系
非平凡依赖
平凡依赖
9
术语和符号 (2)
如果 Y不函数依赖于 X,则记作 X Y。
如 学号 不函数依赖于 性别,
则记作 性别 学号 。
10
术语和符号 (3)
如果 X→Y, 则 X称作决定因素。
如 学号 → 所在系,则 学号 称作决定因素
11
用 U表示关系模式 R的属性全集，
即 U={A1,A2,…,An},用 F表示关系模
式 R上的函数依赖集，则关系模式 R
可表示为 R(U,F)。
术语和符号 (4)
如 U={仓库号,城市,面积 }
F={仓库号 → 城市,仓库号 → 面积 }
则 R(U,F)表示仓库关系
12
术语和符号 (5)
如果 K是关系模式 R(U,F)的任一候选关键
字,X是任一属性或属性集，如果 X?K,则 X
称为主属性；否则称为非主属性。
如 (仓库号,器件号 )是 库存 关系的关键
字，那么 仓库号 和 器件号 均是主属性，而
数量 为非主属性。
13
术语和符号 (6)
如果 X→ Y,并且 Y→ X,则可记作 X←→ Y。
14
术语和符号 (7)
如果 X→ Y,并且对于 X的一个任意真子集 X/
都有 X/ Y,则称 Y完全函数依赖于 X,并记
作 ；如果 X/ → Y成立，则称 Y部分函数
依赖于 X,并记作 。
YX f? ??
YX p? ??
如,(学号,课程号 )→ 成绩 是完全函数依赖
而,(学号,所在系 )→ 系主任 是部分函数依赖
15
术语和符号 (8)
如果 X→ Y（ 非平凡函数依赖，并
且 Y X）,Y→ Z,则称 Z传递函数
依赖于 X。
如 学号 → 专业, 专业 → 所在系,则 所
在系 传递函数依赖于 学号 。
16
17
设有库存关系：
数据冗余问题
数据更新问题
数据插入问题
数据删除问题
18
为什么会出现以上种种操作异常现象呢？
因为这个关系模式没有设计好，在它的
某些属性之间存在着, 不良, 的函数依赖。
如何改造这个关系模式？克服以上种种问题，
就是我们这一章要解决的根本问题，也是我
们要讨论函数依赖的根本原因。
19
模式分解
解决各种操作异常现象的方法就是
进行模式分解，即把一个关系模式分解
成两个或多个关系模式，在分解的过程
中消除那些, 不良, 的函数依赖，从而
获得好的关系模式。
20
分解举例
仓库 （ 仓库号, 地点 ）
设备 （ 设备号, 设备名 ）
库存 （ 仓库号, 设备号, 库存数量 ）
刚才提到的 库存 关系模式，我们可以把其分解为：
21
注意：
模式分解不能破坏原来的语义；
模式分解必须遵守：
? 无损连接分解；
? 保持函数依赖分解。
无损连接是指
分解后的关系经过
自然连接可以恢复
成原来的关系。
保持函数依赖是指
分解后的关系不能破坏
原来的函数依赖（不能
破坏原来的语义）。
22
函数依赖的公理系统
Amstrong公理的内容及正确性
Amstrong公理的推论
逻辑蕴涵和闭包
公理的完备性
闭包的计算
函数依赖集的等价和最小化
23
Amstrong公理：
设有关系模式 R(U,F),X,Y,Z均为 U
的子集, 推理规则如下：
① 自反律, 如果 Y?X,则 X→ Y；
② 增广律, 如果 X→ Y,则 XZ→ YZ；
③ 传递律, 如果 X→ Y,Y→ Z,则 X→ Z 。
24
定理 9.1,Amstrong公理是正确的。
25
证明自反律,
设 Y?X ? U
对关系模式 R的任一关系 r 中的
任意两个元组 t和 s,如果 t[X]=s[X]，
由于 Y ? X,所以 t[Y]=s[Y],由定义
9.1有 X→ Y成立, 自反律得证 。
26
证明增广律,
设 X→ Y,且 Z?U,r,t,s的含义同上
如果 t[XZ]=s[XZ],则一定有
t[X]=s[X]和 t[Z]=s[Z]
又根据 X→ Y可有 t[Y]=s[Y]
由 t[Y]=s[Y]和 t[Z]=s[Z]可得 t[YZ]=s[YZ]
即由 t[XZ]=s[XZ]推导出了 t[YZ]=s[YZ]
由定义 9.1有 XZ→ YZ成立, 增广律得证 。
27
证明传递律,
设 X→ Y,Y→ Z,r,t,s的含义同上
如果 t[X]=s[X],由于 X→ Y,根据定义 9.1可得 t[Y]=s[Y]
同理由于 Y→ Z,可得 t[Z]=s[Z]
即由 t[X]=s[X]推导出了 t[Z]=s[Z]
根据定义 9.1 X→ Z成立, 传递律得证 。
28
Amstrong公理的推论：
推论 ① - 合并规则：如果 X→ Y,X→ Z,则
X→ YZ；
推论 ② -分解规则：如果 X→ YZ,则 X→ Y、
X→ Z；
推论 ③ -伪传递规则：如果 X→ Y,YW→ Z,则
XW→ Z。
29
定理 9.2,Amstrong公理
的三个推论是正确的。
30
证明合并规则：
设 X→ Y,X→ Z
根据增广律分别有 X→ XY,XY→ YZ
又根据传递律有 X→ YZ,合并规则得证 。
31
证明分解规则,
设 X→ YZ
根据自反律有 YZ→ Y和 YZ→ Z
又根据传递律分别有 X→ Y和 X→ Z，
分解规则得证 。
32
证明伪传递规则：
设 X→ Y,YW→ Z
根据增广律有 XW→ YW
又根据传递律有 XW→ Z,伪传递规则得证 。
33
引理 9.1
引理 9.1,X→ A1A2… An的充分必要条件
是 X→ Ak成立 (k=1,2,…,n)。
根据合并规则和分解规则可以得出
如下重要结论：
34
逻辑蕴涵和闭包
有时需要根据给定的一组函数依赖来
判断另外一些函数依赖是否成立，这就是
函数依赖逻辑蕴涵所要研究的内容。
比如有关系模式 R(U,F),U={A,B,C}，
F={A→B,B → C}, 问 A → C 是否也成立？
35
逻辑蕴涵
定义 9.2：设有关系模式 R(U,F)，
X?U,Y ? U,如果从 F中的函数依赖能
够推导出 X→ Y,则称 F逻辑蕴涵 X→ Y，
或称 X→ Y是 F的逻辑蕴涵。
36
闭包
定义 9.3 在关系模式 R(U,F)中，被 F 所逻
辑蕴涵的函数依赖的全体称作 F 的闭包，
记为 F + 。
37
闭包计算举例
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
,,,,
,,,,
,,,,
,,,,
,,,,,,
,,,,,,
,,,,,,
,,,,,,
X Y ZX Y ZX Y ZXZX Y ZXYX Y ZX
YZX Y ZYZXZYZXYYZX
XZX Y ZXZXZXZXYXZX
XYX Y ZXYXZXYXYXYX
YZYZYZYZX Y ZZXZZXYZX
ZYZZYYX Y ZYXZYXYYX
ZZYYZYYXX Y ZXXZXXYXX
ZYZYX Y ZXZXYX
→→→→
→→→→
→→→→
→→→→
→→→→→→
→→→→→→
→→→→→→→
Φ→Φ→Φ→Φ→Φ→Φ→Φ→
假设有关系模式 R(U,F),U={X,Y,Z}，
F={X→ Y,Y→ Z},则 F+ 为：
38
属性集闭包
39
计算属性集闭包举例
?FX
?FX
?FX
如果 X={A},则：
＝｛ A,B,C｝
如果 X={B},则
＝｛ B,C｝
如果 X={C},则
＝｛ C｝
设有关系模式 R(U,F),U={A,B,C},F={A→ B,B→ C}
40
公理的完备性
建立一套公理系统必须明确两个问题：
一是能否保证按公理推导出的函数依赖都是正确的, 即
这些函数依赖是否都属于 F+； 也就是说对于关系模式
R(U,F),只要 F中的函数依赖为真, 则用公理根据 F推导
出的函数依赖也一定为真, 这就是公理的正确性；
另外一个问题是：用公理能否推导出所有的函数依赖？
也就是说 F+中所有的函数依赖是否都能用公理推导出来？
这是一个很重要的问题, 因为如果 F+中有函数依赖不能
用公理推导出来, 那么就说明这些公理不够用, 不完全,
就必须补充新的公理, 这就是公理的完备性问题 。
41
引理 9.2
42
引理 9.2充分性证明,YXXY F ??? ?
43
引理 9.2必要性证明,????
FXYYX
44
公理的完备性还可以理解为：
所有不能用公理推导出的函数依赖
都不为真，即如果 X→ Y不能根据 F用公理
导出，则 X→ Y? F+ 。 或者说存在一个具
体的关系 r,F+ 中的所有函数依赖都满足
r,而不能用公理推导出的 X→ Y不满足 r。
也就是说，不能根据 F用公理导出的函数
依赖不属于 F+ 。 如果我们能够找到这样
的 r,则公理的完备性证明问题就解决了。
45
定理 9.3,Amstrong公理是完备的。
为了证明公理的完备性，找到了如下具体的关系 r：
如果能够证明以下两点，则公理的完备性问题就
证明了：
⑴在关系 r中,F + 中的所有函数依赖都成立；
⑵在关系 r中，不能根据 F用 Amstrong公理推导出的
函数依赖 X→ Y不成立。
46
证：在关系 r中,F+ 中的所
有函数依赖都成立
47
证,在关系 r中，不能根据 F用 Amstrong公理推
导出的函数依赖 X→ Y不成立
48
由公理的完备性和引理 9.2有结论：
?? ???? FXYFYX
49
属性集闭包的计算
50
算法 9.1：
51
例：设有 R（ U,F）,U={A,B,C,D,E}，
F={AB→ C,B → D,C → E,EC → B,AC → B}
求 ?
FAB)(
?FAB)( {A,B,C,D,E}=
52
函数依赖集的等价和最小化
53
覆盖和等价的定义
定义 9.5 设 F和 G是两个函数依赖集：
① 如果 F +?G +,则称 G是 F的一个覆盖,
或称 G覆盖 F；
② 如果 F +?G +和 G +?F +同时成立,
即 F +=G +,则称 F和 G等价 。
54
引理 4.3
F+=G+的充分必要条件是 F?G+并且 G ? F+。
必要性证明：
充分性证明：
55
F+=G+ ? F?G+并且 G ? F+ 为判定两个函
数依赖集是否等价提供了简便方法：
可以首先检查 F中的每个函数依赖 X→ Y是否属
于 G+（ 即计算 Y是否属于 XG+）？ 如果对 F中的每
个函数依赖都有 X→ Y?G+,则有 F?G+ ；然后用
同样的方法再检查 G?F+是否成立？ 如果它们都成
立则 F和 G等价 。
56
研究函数依赖集等价的目的
研究函数依赖集等价的目的是为了对指
定函数依赖集找出它的最小函数依赖等
价集，即找出包含函数依赖尽可能少、
甚至最少的函数依赖等价集，从而使模
式分解简化，分解出最简单的关系模式。
57
最小函数依赖集的定义
定义 9.6 如果函数依赖集 F满足如下条件, 则称
F 为一个最小函数依赖集, 也称为极小函数依
赖集或最小覆盖：
① F 中任一函数依赖的右部都仅含有一个属
性；
② F中不存在这样的函数依赖 X→ A,X有真子
集 Z,使得 F与 F-{X→ A} ∪ {Z→ A}等价；
③ F中不存在这样的函数依赖 X→ A,使得 F与
F-{X→ A}等价 。
58
例,假设有属性集 U={A,B,C,D,E},函数依
赖集 F={A→ B,B→ C,AD→ E}和函数依赖集
G={A→ B,A→ C,B→ C,AD→ E},问 F和 G是
否是最小函数依赖集？
答案,F是最小依赖集,G不是最小依赖集。
59
引理 9.4
60
引理 9.4必要性证明
61
引理 9.4充分 性证明
62
引理 9.5
设 X→ A是 F中任意函数依赖,G=F-{X→ A}，
F与 G等 价的充分必要条件是 。??
GXA
必要性证明
充分性证明
63
计算最小覆盖的算法
算法 9.2 给定函数依赖集 F,求其最小覆盖的过
程如下：
? 逐一检查 F 中各函数依赖 X→ Y,若 Y=A1… Ak,k>=2，
则用 {X→ Aj | j=1,…,k}来取代它（分解规则）；
? 逐一取出 F中各函数依赖 X→ A,若 X=B1B2… Bm,m>=2，
则逐一考查 Bj（ j=1,…,m）,如果,则 F
与 F-{X→ A} ∪ {(X-Bj)→ A}等价（引理 9.4），故以 X-
Bj取代 X；
? 逐一检查 F中各函数依赖 X→ A,令 G=F-{X→ A},根据
引理 9.5，如果,则 F与 G等价，故从 F中去掉
X→ A。
??? FjBXA )(
?? GXA
64
例,已知 F={A→ B,B→ A,B→ C,A→ C,C→ A}，
求 F的最小覆盖。
逐一检查 F中的函数依赖是否多余，如
果多余则可以去除之，最后的结果为：
{A → B,B → C,C→ A}
65
注意：算法 9.2的第 2,3两
步是不可以颠倒的。
66
设 F={C?A,A ? D,CD ? B,B ? A}
依照算法 9.2先既约化后无冗余化
既约化
令 G=F-{CD ? B}?{C ? B}
结果 G与 F等价
G= {C?A,A ? D,C ? B,B ? A}
无冗余化
结果所求最小覆盖为
F’={A ? D,C ? B,B ? A}
67
设 F={C?A,A ? D,CD ? B,B ? A}
先无冗余化后既约化
无冗余化
结果没有多余的函数依赖
既约化
结果 G= {C?A,A ? D,C ? B,B ? A}
它不是最小覆盖，因为 C?A这时是多余的函数依赖。
68
规范化
规范化的目的就是要设计“好”的
关系，使关系尽量减少操作异常甚至拒
绝操作异常现象。
69
第一范式
每个关系模式都应满足最低要求：
所有分量都必须是不可分的最小数据项，
并把其称为第一范式（ 1NF） 关系。
70
非规范化表格和规范化表格
71
第二范式
定义 9.7 如果 R(U,F) ∈ 1NF,并且 R中
的每个非主属性都完全函数依赖于关键字,
则 R(U,F) ∈ 2NF。
72
库存 A关系实例：
仓库号 设备号 数量 地点
WH 1 D4 675 北京
WH 1 D7 250 北京
WH 2 D2 280 上海
WH 2 D4 200 上海
WH 2 D9 270 上海
WH 3 D2 550 广州
WH 3 D4 230 广州
WH 4 D5 550 北京
数据冗余
插入异常
更新异常
删除异常
73
为了解决操作异常分解后的关系：
库存 B(仓库号,设备号,数量 )
仓库 B(仓库号,地点 )
74
第三范式
定义 9.8 如果 R(U,F) ∈ 2NF,并且所
有非主属性都不传递依赖于关键字，则
R(U,F) ∈ 3NF。
75
仓库 A关系实例 仓库号 所在省 仓库面积 所在城市
WH2 1 湖北 675 武汉
WH2 2 河北 250 邯郸
WH2 3 湖北 280 武汉
WH2 4 广东 200 广州
WH2 5 湖北 270 武汉
WH2 6 广东 550 广州
数据冗余
插入异常
更新异常
删除异常
76
为了解决操作异常分解后的关系：
仓库 B(仓库号,仓库面积,所在城市 )
城市 (省,城市 )
77
BC范式
78
关系模式实例：
管理 (仓库号，设备号，职工号 )
它所包含的语义是：
① 一个仓库可以有多个职工；
② 一名职工仅在一个仓库工作；
③ 在每个仓库一种设备仅由一名职工保管 （ 但
每名职工可以保管多种设备 ） 。
根据以上语义有函数依赖：
职工号 → 仓库号
(仓库号, 设备号 )→ 职工号
79
进一步理解前述语义：
80
为了解决操作异常现象如何进行分解？
任何分解都会破坏函数依赖：
（仓库号，设备号） ?职工号
结论：不将 3NF分解成 BCNF！
81
如何解决非 BCNF带来的操作异常现象？
不可能靠模式分解来解决问题，只
有靠应用程序或设计数据库时建立一些
必要的约束来预防操作异常现象的发生。
如第 6章介绍的触发器。
82
多值依赖与第四范式
在关系模式上不仅存在函数依赖，还存在着
其他的“依赖”影响着关系模式的质量，如多值
依赖。
83
讨论：三个实体之间的联系
? 每个仓库可以存放多种设备, 每名职工管理一个仓库中
的所有设备；
? 每名职工可以管理多个仓库的设备；
? 每种设备可以存放在多个仓库 。
示意数据
84
关键字是 (仓库号,职工号,设备号 )，即 All-Key
BCNF
是否还存在操作异常现象？为什么？
例如, 职工 E4新分配到 WH1仓库工作, 这时必须插
入如下 3个元组：
WH1 E4 P1
WH1 E4 P2
WH1 E4 P3
同样, 如果 P3不再存放在 WH1仓库, 这时则要删除
多个元组：
WH1 E1 P3
WH1 E2 P3
WH1 E4 P3
排列成关系
85
多值依赖的定义
定义 9.10 设有关系模式 R(U),X,Y,Z
是 U的子集, Z=U-X-Y,如果对于 X的一个给
定值, 存在一组 Y值与其对应, 而 Y的这组值
又不以任何方式与 Z的值相关, 则说 Y多值依
赖于 X,记为 X→→ Y。
若 Z=Φ（ 即 Z为空），则将多值依赖
X→→ Y称为平凡的多值依赖。
86
在下表所示的关系上：
给定一个仓库号值, 有一组职工号与其对应，而
这组职工号值与设备号值没有任何依赖关系，所
以 仓库号 →→ 职工号 ；
同样 仓库号 →→ 设备号 ；
多值依赖具有对称的性质，即如果 X→→ Y,并且
Z=U-X-Y,则 X→→ Z也成立。
87
函数依赖可以看作是
多值依赖的特例。
88
第四范式
定义 9.11 设关系模式 R(U,D)∈ 1NF,若
对每个非平凡的多值依赖 X→→ Y,X都含有侯
选关键字, 则 R(U,D)∈ 4NF。
?从定义可以看出,4NF限定了在关系模式的属性
间不允许有非平凡、且非函数依赖的多值依赖。
?这是因为，若 X→→ Y是非平凡的多值依赖，且 X
含有侯选关键字，则有 X→ Y,所以 4NF所允许的非
平凡的多值依赖实际上就是函数依赖。
?4NF自然是 BCNF
89
非 4NF关系到 4NF关系的转换仍然是通过分解，
上表所示的关系显然不是 4NF,可以分解为：
?职工 (仓库号,职工号 )
?存放 (仓库号,设备号 )
分解结果都是 4NF关系。
90
规范化小结
91
模式分解
模式分解的准则
3NF无损连接和保持函数依赖算法
使分解后的关系模式数最少
92
模式分解的准则
?模式分解具有无损连接性；
?模式分解能够保持函数依赖。
93
无损连接的形式定义：
94
保持函数依赖的形式定义：
定义 9.13 若,则 R(U,F)的分解
ρ ={R1(U1,F1),…,Rk(Uk,Fk)}保持函数依赖
。
?
k
i
iFF
1
)(
?
?? ?
95
设有关系模式 R（ U,F）,U={emp,wh,city}，
F={emp→ wh,wh→ city},其中 emp是职工号,wh是
仓库号,city是仓库所在城市；从 F中可以看出，一名职
工只能在一个仓库工作，一个仓库只能位于一个城市。
看如下的三个分解是否满足无损连接和保持函数依
赖的特性：
ρ 1={R1(emp,Φ),R2(wh,Φ ),R3(city,Φ)}
ρ 2={R1({emp,wh},{emp→wh }),
R2({emp,city},{ emp→city })}
ρ 3= {R1({emp,wh},{emp→wh }),
R2({wh,city},{ wh→city })}
96
为了得到更高范式的关系进行的模
式分解，是否总能既保证无损连接、又
保持函数依赖？
如果要求分解保持函数依赖, 那么模式分解总可
以达到 3NF,但是不一定能达到 BCNF；
如果要求分解具有无损连接的特性, 那么一定可
以达到 BCNF；
如果要求分解既保持函数依赖, 又具有无损连接
的特性, 那么分解可以达到 3NF,但是不一定能
达到 BCNF。
97
例：设有关系模式 R（ U,F）,U={A,B,C}，
F={AB→ C,C→ B},该关系模式是 3NF的，因为存
在一个主属性对非主属性的函数依赖 C→ B,所以
该模式不是 BCNF。
为了达到 BCNF就必须进行分解，但是任何
分解都会破坏函数依赖 AB→ C。 所以为了保持
函数依赖，就必须放弃 BCNF。
98
在实践中 BCNF的意义并不大, 因为我们对模
式分解的要求总是既要保证无损连接, 又要保持
函数依赖 。 那么, 当一个关系是 3NF时：
? 关键字是单属性时, 该模式自然是 BCNF；
? 关键字是复合属性, 并且不存在主属性对非主
属性的函数依赖, 则该模式自然是 BCNF；
? 关键字是复合属性, 并且至少存在一个主属性
对非主属性的函数依赖, 则为了保持函数依赖,
模式分解无法达到 BCNF。
99
判断一个分解是否保持函数依
赖, 可以根据函数依赖的最小覆
盖和等价来判断 。
100
判断一个分解是否具有无损连接特性
可以用如下法则：关系模式 R分解为 R1和
R2是无损连接分解的充分必要条件是：
R1 ∩ R2 → R1 - R2
或
R1 ∩ R2 → R2 – R1
101
3NF无损连接和保持函数依赖算法
102
对 R（ U,F） 中的 F进行最小化处理, 即计算 F的最小覆盖,
并将最小等价依赖集仍然记为 F；
若有 X→ A,并且 X∪ A=U,则 ρ ={R},算法终止 ；
找出不在 F中出现的属性 （ 即与 F中任意函数依赖的左部和
右部都无关的属性 ）, 把这样的属性构成一个关系模式
R0（ U0,Φ ）, 并把 U0从 U中去掉, 剩余的属性仍然记为 U；
对 F按具有相同左部的原则进行分组 （ 假定分为 k组 ）, 每
一组函数依赖 Fi所涉及的全部属性形成属性集 Ui,若 Ui?Uj
（ i<>j）, 就去掉 Ui ；
经过以上步骤得到的分解 ρ ={R0,R1,…, Rk}（ R0可能为
空, 1… k可能不连续 ） 构成 R的一个保持函数依赖的分解,
并且每个 Ri均为 3NF；
设 X是 R（ U,F） 的关键字, 并令 τ =ρ ∪R X（ X,FX） ；
若对某个 Ui, 如果 X?Ui, 则将 RX 从 τ 中去掉, 或 Ui?X，
则将 Ri从 τ 中去掉；
最后 τ 就是所求分解 。
3NF
保
持
函
数
依
赖
和
无
损
连
接
的
分
解
算
法
103
3NF无损连接和保持函数依赖算法举例
104
使分解后的关系模式数最少
105
算法 9.3已经保证了：
?3NF分解；
?保持函数依赖分解；
?无损连接分解；
一般为了操作方便，我们还希望：
分解的关系模式数最少
106
设有函数依赖集合,F={A→ B,A→ C,B→ A，
B→ C,AE→ D,BD→ G,D→ E}
利用算法 9.2求得的最小覆盖集是：
F’={A→ B,B→ A,B→ C,AE→ D,BD→ G，
D→ E}
按照算法 9.3得到的模式分解是：
τ={R1({A,B,C},{B→ AC,A→ B})，
R2({A,E,D},{AE→ D,D→ E})，
R3({B,D,G},{BD→ G})}
107
还是刚才那个依赖集,F={A→ B,A→ C，
B→ A,B→ C,AE→ D,BD→ G,D→ E}
利用算法 9.2求得的最小覆盖集是：
F’={A→ B,B→ A,B→ C,AE→ D,BD→ G,D→ E}
注意,(AE)F’+={A,B,C,D,E,G}
所以 AE → BD和 AE → G?F’+
设 F”=F’∪ {AE→BD, AE→G}
显然有 F’与 F”等价 。 根据 F”再计算最小覆盖, 结果是：
Fm={A→ B,B→ A,B→ C,AE→ D,AE→ G,D→ E}
分解结果是,R1(A,B,C),R2(A,D,E,G)
108
定义 9.14：若 G是 F所有等价集
中函数依赖个数最少的，则称
G是 F的最小等价集。
109
定义 9.15 设 Γ(X→ Y,F)={V→ W|V→ W∈ F,V→ W
参与推导 X→ Y },Δ(X,F)={V→ W| V→ W∈ F,V→ X
∈ F+,X→ V ∈ F+},则当 Γ(X→ Y,F)∩Δ(X,F)=Φ，
Y∈ XF+ 时，称 X直接决定 Y,记为 。
YX ?
定义中 Γ(X→ Y,F)表示包含在 F中推导 X→ Y时
用到的全部函数依赖； Δ(X,F)表示依赖集 F中函数
依赖的左部与 X能相互决定的函数依赖集，或称
左部与 X等价的函数依赖集。
X直接决定 Y也可以叙述为 Γ(X→ Y,F)中所有函
数依赖的左部都不能决定 X 。
110
算法 9.4 设 F是无冗余和既约化的函数依赖集，求
F的最小等价集的算法如下：
1.把 F中的函数依赖按左部等价进行分组；
2.任一组中，若存在 X→ V,Y→ W并且 X直接决
定 Y,则把它们合并为 Y→ VW，直到任一组中都
不存在如此依赖对为止。
111
【本章小节】
本章的内容是关系数据理论，它是关系
数据模型的重要理论基础，该理论可以
指导关系数据库或关系模式的设计。关
系的范式是对关系规范化程度的一个衡
量标准，原则上规范化程度越高，关系
的质量越好。关系的规范化过程是模式
分解的过程，模式分解需要遵守保持函
数依赖和无损连接的原则。
