§ 7.2.6 BCNF
BCNF 比 3NF 更进一步，其消除 主属性 对 码 的部分与传递依赖。
1.定义 7.8：
关系模式 R<U,F>∈ 1NF，若 X→Y 且 Y?X时 X必含有码，则 R<U,F>
∈ BCNF 。
即,R<U,F> 中，每一个决定因素都包含码，则 R<U,F> ∈ BCNF。
2.结论：
⑴,所有非主属性对每一个码都是完全函数依赖。
显然，这是 3NF的要求所达到的，非主属性不部分、传递函数依赖于
码。
⑵,所有主属性对每一个不包含它的码，是完全函数依赖。
这是 BCNF的特征：让主属性对不包含它的码也无部分、传递 FD。如，
有 X∈ U,Y∈ U，且 X→Y, Y→X,若 Y′是 Y中的码，则有 Y′ →X 。
⑶,无任何属性完全函数依赖于非码的属性。
BCNF中没有任何属性对非码属性完全函数依赖。
3.实例：
例子 1,C〈 C#,CN,PC#,C#→CN, C#→PC# 〉
没有对 C#的部分和传递函数依赖。所以 C∈ 3NF。
又因 C中 C#是唯一的决定因素。所以 C∈ BCNF。
例子 2,S〈 S#,SN,SD,SA,S#→SA, S#→SD, SN →SA, S#→SD 〉
S有两个码,S#,SN。它们都由单个属性组成，互不相交。
没有对 S# 和 SN 的部分和传递函数依赖。所以 S∈ 3NF。
又因 S中 S# 和 SN 是唯一的决定因素。所以 S∈ BCNF。
4.讨论：
⑴,若 R∈ BCNF，则 R∈ 3NF。
证明：假设 R∈ BCNF且 R∈ 3NF，则必存在传递依赖有：
X →Y, Y →Z, Y→X, Y?X
由于 R ∈ BCNF，则 Y →Z 中的 Y必含有码 Y′
∴ Y→ Y′ （ Y中包含有 Y′）
Y′ →X （结论 2）
∴ Y→X
∴ 与假设不符
故 R∈ 3NF。
⑵,若 R ∈ 3NF，则 R未必属于 BCNF。
反例见书上 166页的例 2。
5.3NF与 BCNF的区别：
3NF中可能存在主属性对码的部分、传递函数依赖。
§ 7.2.7 多值依赖
1.引入：
在书 167页上的例子中
在关系模式 TEACH中,C—课程,T—教员,B—参考书，
有一组值 (C,B)，则必有一个 T 值与之对应。
同理，有一组值 (C,T)，则必有一个 B 值与之对应。
所对应的值只由 C 决定。
这就是要给大家介绍的多值依赖,C→→T, C→→B 。
2.定义 7.9：
设 R（ U）是属性集 U上的一个关系模式。 X,Y,Z是 U的子集，并且 Z=U-
X-Y，多值依赖 X→→Y 成立当且仅当对 R（ U）的任一关系 r,给定的一对（ x,z）
值有一组 Y的值，这组值仅仅决定于 x值而与 z值无关。
3.实例：
见书 168页的例 2
4.多值依赖的性质：
⑴,若 X→→Y,则 X→→Z,其中 Z=U-X-Y，即多值依赖的对称性。
证明：假设 X→→Z 不成立，
则根据多值依赖定义有元组在 Z上的取值与 Y有关，
存在两组值：（ x,yi），（ x,yj）,yi≠yj
在 Z上对应的元组不全相同
一般可假设 zk为（ x,yi）所对应的 Z值的集合，但不属于（ x,yj）所
对应的值集合，
则有（ x,yi,zk） ∈ r,
（ x,yj,zk） ∈ r,
又由多值依赖定义有 yi与 yj交换得一新元组（ x,yj,zk） ∈ r,
这与假设结论矛盾，
故 X→→Z 成立。
⑵,若 X→Y,则 X→→Y,即函数依赖是多值依赖的特殊情况。
这是由于当 X→Y 时，对 X的每一个值 x,Y有一个确定的值 y与之对应，
由多值依赖的定义可知,X→→Y
⑶,若 X→→Y,而 Z=○,则称 X→→Y 为平凡的多值依赖。
5.多值依赖与函数依赖的区别：
⑴,函数依赖：其有效性仅决定于 X,Y这两个属性集的值，只要在 R（ U）
的任何一个关系 r 中，元组在 X 和 Y上的值满足定义 7.1，则函数依赖 X→Y 在任
何属性集 W（ XY?W?U）上成立。
多值依赖：其有效性与属性集的范围有关,X→→Y 在 U上成立则在 W
（ XY?W?U）上成立，反之则不然。
⑵,若函数依赖 X→Y 在 R（ U）上成立，则对于任何 Y′ Y均有 X →Y′ 成立。
若多值依赖 X→→Y 若在 R（ U）上成立，则不能断言对于任何 Y′ Y均有
X →→Y′ 成立。
∩
∩
§ 7.2.8 4NF
4NF 是消除了非平凡且非函数依赖的多值依赖。
1.定义 7.10：
关系模式 R<U,F>∈ 1NF，若 X→→Y （ Y?X）是非平凡的多值依赖，且 X
含有码，则称 R<U,F> ∈ 4NF 。
注：一个关系模式若属于 4NF，则必然属于 BCNF。
R中所有平凡的多值依赖实际上是函数依赖。
2.非 4NF的反例：
书 168页上的例 2，虽然 W→→S, W→→C 是非平凡的多值依赖，但是 W
不是码，（ W,S,C）才是码。故 WSC∈ 4NF。
3.非 4NF的关系模式存在的问题：
数据冗余。
4.解决方法：
投影分解。
§ 7.2.9 规范化小结
规范化的目的是：消除关系模式中存在的插入异常、删除异常、修改复杂
和数据冗余等毛病。
基本思想是：逐步消除数据依赖中不合适的部分，使概念单一化。
1NF→2NF,消除非主属性对码的部分函数依赖。
2NF→3NF,消除非主属性对码的传递函数依赖。
3NF→BCNF,消除主属性对码的部分和传递函数依赖。
BCNF→4NF,消除非平凡且非函数依赖的多值依赖。
方法：通过对关系模式的投影分解来实现的。
§ 7.3* 数据依赖的公理系统
定义 7.11：
对于满足一组函数依赖 F 的关系模式 R <U,F>，其任何一个关系 r,若函
数依赖 X→Y 都成立，则称 F 逻辑蕴含 X→Y 。
定义 7.12：
在关系模式 R<U,F>中为 F所逻辑蕴含的函数依赖的全体叫做 F的闭包，
记为 F+
定义 7.13：
设 F为属性集 U上的一组函数依赖,X?U,XF+=﹛ A︱ X →A 能由 F根据
Armstrong公理导出 ﹜, XF+称为属性集 X关于函数依赖集 F的闭包。
因此，要判定 X →Y 是否能由 F根据 Armstrong公理导出，就要求出 XF+，
判定 Y是否为 XF+的子集。 这是由算法 7.1来完成的。
1.合并规则：由 X→Y, X→Z,有 X→YZ
2.伪传递规则：由 X→Y, WY→Z,有 XW→Z
3.分解规则：由 X→Y, Z?Y，有 X→Z
算法 7.1：
求属性集 X（ X?U）关于 U上的函数依赖集 F的闭包 XF+
输入,X,F
输出,XF+
步骤：
①,令 X(0)=X,i=0
②,求 B
③, X(i+1)=B∪ X(i)
④,判断 X(i+1)=X(i) 吗？
⑤,不等，则 i = i+1，返回②
⑥,相等，则 XF+ =X(i),算法终止
实例：
已知关系 R <U,F>,U=﹛ A,B,C,D,E﹜, F=﹛ AB→C, B→D,
C→E, EC→B, AC→B ﹜ 。
求 (AB)F+
由算法 7.1得：
设 X(0) ={AB}，
计算 X(1)，扫描 F中各函数依赖，找左部为 A,B,AB的函数依赖：
AB→C, B→D,
于是 X(1)=AB∪ CD={ABCD}，
因为 X(0) ≠ X(1)
计算 X(2)，扫描 F中各函数依赖，找左部为 X(1)的子集的函数依赖：
AC→B, C→E,
于是 X(2)= X(1) ∪ BE={ABCDE}，
因为 X(3) ＝ X(2)
所以 (AB)F+= X(2) ={ABCDE}。
补充：
已知关系 R <U,F>,U=﹛ A,B,C,D,E﹜, F=﹛ AB→C, B→D,
C→E, EC→B, AC→B ﹜ 。
求 R 的码？
解法：
1.求出所有可能存在的闭包 X(i) =XF+,
2.若 X(i) =U，则选出其中的 X，
3.在 X中选出最简的主属性组 Xi,
4,Xi 就是所求的码。
具体解为：
(AB)F+=﹛ ABCDE﹜
(B)F+=﹛ BD﹜
(C)F+=﹛ CBDE﹜
(EC)F+=﹛ CBDE﹜
(AC)F+=﹛ ABCDE﹜
(ABC)F+=﹛ ABCDE﹜
(ABCE)F+=﹛ ABCDE﹜
(BC)F+=﹛ BCDE﹜
(BEC)F+=﹛ BCDE﹜
(AEC)F+=﹛ ABCDE﹜
包含全部属性的有 (AB)F+,(AC)F+, (ABC)F+, (ABCE)F+, (AEC)F+
挑选出最简的是,(AB)F+, (AC)F+
所以 R 的码为,AB 和 AC
定义 7.14：
如果 F+=G+，就说函数依赖集 F覆盖 G（ F是 G的覆盖，或 G是 F的覆盖），
或 F与 G等价。
定义 7.15：
如果函数依赖集 F满足下列条件，则称 F为一个极小函数依赖集 Fm,亦
称为最小依赖集，最小覆盖。
⑴,F中任一函数依赖的右部仅含有一个属性。
⑵,F中不存在这样的函数依赖 X→A,使得 F与 F-﹛ X→A ﹜ 等价。
⑶, F中不存在这样的函数依赖 X→A, X有真子集 Z使得 F -
﹛ X→A ﹜∪ ﹛ Z→A ﹜ 与 F等价。
例：关系模式 S <U,F>,U=﹛ S#,SD,MN,CN,G﹜,
F=﹛ S#→SD, SD→MN,（ S#, CN） → G﹜ 。
设 F′=﹛ S#→SD, S#→MN, SD→MN,（ S#, CN） → G,（ S#, SD）
→ SD﹜ 。
由上面的定义可知,F为极小函数依赖集，而 F′不是。
定理 7.3：
每一个函数依赖集 F均等价于一个极小函数依赖集 Fm (此 Fm称为 F的最小
依赖集）。
求极小函数依赖集 Fm的步骤：
见书 174页
例 1：
已知,F=﹛ A→B, B→A, B→C, A→C, C→A ﹜
求 F 的极小函数依赖集 Fm
解：
1.化右部为单一属性,F=﹛ A→B, B→A, B→C, A→C, C→A ﹜
2,① 在 F中去掉 A→B, (A)F+={AC},∵ B∈ (A)F+, ∴ 不去掉。
②在 F中去掉 B→A, (B)F+={ABC},∵ A∈ (B)F+, ∴ 应去掉。
③在 F中去掉 B→C, (B)F+={B},∵ C∈ (B)F+, ∴ 不去掉。
④在 F中去掉 A→C, (A)F+={ABC},∵ C∈ (A)F+, ∴ 应去掉。
⑤ 在 F中去掉 C→A, (C)F+={C},∵ A∈ (C)F+, ∴ 不去掉。
3.因主属性是单属性，故不用再取其子集去考察。
故极小函数依赖集 Fm=﹛ A→B, B→C, C→A ﹜
例 2：
已知关系 R <U,F>,U=﹛ A,B,C,D,E,F,G,H,I,J﹜,
F=﹛ A→B, A→C, A→DE, D→E, DE→B, AF→GHI, I→J ﹜ 。
求 F 的极小函数依赖集 Fm
解：
1.化右部为单一属性：
① A→DE ?A→D, A→E
② AF→GHI ?AF→G, AF→H, AF→I
则 F=﹛ A→B, A→C, A→D, A→E, D→E, DE→B, AF→G,
AF→H, AF→I, I→J ﹜ 。
2,① A→B,记 G=F-﹛ A→B ﹜,
∴ (A)G+= ﹛ ACDEB﹜,
∴ B∈ (A)G+,
∴ 去掉 A→B,
F=F-﹛ A→B ﹜ =﹛ A→C, A→D, A→E, D→E, DE→B,
AF→G, AF→H, AF→I, I→J ﹜ 。
② A→C,记 G=F-﹛ A→C ﹜,
∴ (A)G+= ﹛ ADEB﹜,
∴ C∈ (A)G+,
∴ 不去掉 A→C,
F=﹛ A→C, A→D, A→E, D→E, DE→B, AF→G,
AF→H, AF→I, I→J ﹜ 。
③ A→E,记 G=F-﹛ A→E ﹜,
∴ (A)G+= ﹛ ACDEB﹜,
∴ E∈ (A)G+,
∴ 去掉 A→E,
F=F-﹛ A→E ﹜ =﹛ A→C, A→D, D→E, DE→B, AF→G,
AF→H, AF→I, I→J ﹜ 。
④ 同理考察,A→D, D→E, DE→B, AF→G, AF→H, AF→I,
I→J,它们都不能去掉。
故记 F为,F=﹛ A→C, A→D, D→E, DE→B, AF→G, AF→H,
AF→I, I→J ﹜ 。
3,函数依赖左部的分解
①,DE→B, ∴ (D)F+= ﹛ DEB﹜,
∴ B∈ (D)F+,
∴ 用 D→B 代替 DE→B,
记 F=﹛ A→C, A→D, D→E, D→B, AF→G, AF→H,
AF→I, I→J ﹜ 。
②,AF→G,
∴ (A)F+= ﹛ ACDEB﹜,
∴ (F)F+= ﹛ ACDEB﹜,
∵ G∈ (A)F+ ； G∈ (F)F+,
∴ 不能用 A→G 或 F→G 代替 AF→G,
记 F=﹛ A→C, A→D, D→E, D→B, AF→G, AF→H,
AF→I, I→J ﹜ 。
同理，可考察 AF→H, AF→I,它们都应保留。
所以,Fm=﹛ A→C, A→D, D→E, D→B, AF→G, AF→H, AF→I,
I→J ﹜ 。
作业 1：
书 182页练习题第 1题全部。
作业 2：
已知,R <U,F>,U=﹛ A,B,C,D,E,G﹜,
F=﹛ C→D, G→B, CG→E, B→A ﹜ 。
求 ① (C)F+, (G)F+, (B)F+, (CG)F+, (BC)F+, (BG)F+, (BCG)F+
② R 的码？
作业 3：
已知,R <U,F>,U=﹛ A,B,C,D,E,G﹜,
F=﹛ AB→C, D→EG, C→A, BE→C, BC→D, CG→BD,
ACD→B, CE→AG ﹜ 。
求 Fm
§ 7.4 模式的分解
书 175页的定义 7.16只要求 R<U,F>分解后的各关系模式的属性 Ui的并集
等 于 U,F在 Ui上的投影就构成了 Fi。
模式分解后产生的模式应与原模式等价，最起码的要求也要分解后产生
的模式不能丢失原模式的信息。
模式等价有三种不同定义：
①,分解具有“无损连接性”。
②,分解要“保持函数依赖”。
③,分解既要“保持函数依赖”，又要具有“无损连接性”。
这是我们实行分解的三条准则，分解准则不同，能达到的分离程度也不
同。
举例说明：
已知关系 R <U,F>,U=﹛ S#,SD,MN﹜, F=﹛ S#→SD, SD→MN ﹜ 。
在 R中存在传递函数依赖 S#→ MN,若要删除一个学生 S#,则将会把 MN也
一起删除；若 R中无学生 S#，则不能向 R中存入系主任的值 MN。即存在插入
异常和删除异常。一种分解如下：
①, ρ1 ={R1< S#,Ф>,R2< SD,Ф>,R3< MN,Ф >}
这样分解得到的是三个属性的集合（见书 176页），而且是通过自然连
接来实现向 R的恢复，其结果就是产生它们的笛卡尔积，元组增加了，信息
丢失了，这样的分解就不具有“无损连接性”。于是对 R又产生第二种分解：
②, ρ2 ={R1< {S#,SD},{S#→ SD} >,R2< {S#,MN},{S#→ MN} >}
这样分解对 R来说是可恢复的，但由于在 R中存在的函数依赖 SD→MN 在
R1,R2中都不存在了，其结果就是插入和删除异常仍未解决，故此分解不具
有“保持函数依赖性”。于是对 R又产生第三种分解：
③, ρ3 ={R1< {S#,SD},{S#→ SD} >,R2< {SD,MN},{SD→ MN} >}
这样分解既具有“无损连接性”，又,保持函数依赖性”，而且它解决
了更新异常，又没有丢失信息，这是我们希望得到的分解。
下面讨论“分解的无损连接性” 和“保持函数依赖性”。
§ 7.4 分解的无损连接性和保持函数依赖性
算法 7.2：
判别一个分解的无损连接性：
ρ={R1< U1,F1 >,…, Rk< Uk,Fk>}是 R< U,F >的一个分解,U={A1
,…, An},F={FD1,FD2,…, FDp}，不防设 F是一极小依赖集，记 FDi 为
Xi→A 1i
1.建立一张 n 列 k 行的表，每一列对应一个属性，每一行对应分解中的
一个关系模式，若属性 Aj属于 Ui，则在 j 列 i 行交叉处填上 aj，否则填上 bij
2,对每一个 FDi做下列操作：找到 Xi所对应的列中具有相同符号的哪些
行，考察这些行中 li列的元素，若其中有 Ali，则全部改为 Ali ；否则全部改为
Bmli； m 是这些行的行号最小值，应当注意的是，若某个 btli被改动，那么该
表的 li 列中凡是的 btli 的符号（不管它是否是开始找到的那些行）均应作相应
的更改。如在某次更改之后，有一行成为 a1,a2,…, an，则算法终止。对 F
中 P个 FD逐一进行一次这样的处置，称为对 F的一次扫描。
3.比较扫描前后，表有无变化。如有变化，则返回第 2步，否则算法终
止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有
限，因此循环必然终止。
定理 7.4,ρ 为无损连接分解的充分必要条件是算法 7.2终止时，表中有一
行为 a1,a2,…, an 。
例,判断 R的分解 是否具有无损连接性。
已知,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 >。
解：
1.构造初始表：
建立一张 5（ U中属性的个数）（ +1） 列 3（分解的 R个数） 行的表
，每一列对应一个属性，每一行对应分解中的一个关系模式，若属性 Aj属于
Ui，则在 j 列 i 行交叉处填上 aj，否则填上 bij。
Ui Aj A B C D E
R1< A,B,C> a1 a2 a3 b14 b15
R2< C,D > b21 b22 a3 a4 b25
R3< D,E > b31 b32 b33 a4 a5
例,判断 R的分解 是否具有无损连接性。
已知,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 >。
解：
Ui Aj A B C D E
R1< A,B,C> a1 a2 a3 b14 b15
R2< C,D > b21 b22 a3 a4 b25
R3< D,E > b31 b32 b33 a4 a5
2.对每一个 Fdi做下列操作：找到 Xi所对应的列中具有相同符号的哪些行，
考察这些行中 li列的元素，若其中有 Ali，则全部改为 Ali ；否则全部改为 Bmli；
m 是这些行的行号最小值，应当注意的是，若某个 btli被改动，那么该表的 li
列中凡是的 btli 的符号（不管它是否是开始找到的那些行）均应作相应的更
改。如在某次更改之后，有一行成为 a1,a2,…, an，则算法终止。对 F中 P
个 FD逐一进行一次这样的处置，称为对 F的一次扫描。
操作,AB→C,无相同符号的行，故不变
C→D, b14?a4
D→E, b15?a5,b25?a5
Ui Aj A B C D E
R1< A,B,C> a1 a2 a3 a4 a5
R2< C,D > b21 b22 a3 a4 a5
R3< D,E > b31 b32 b33 a4 a5
例,判断 R的分解 是否具有无损连接性。
已知,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 >。
解：
2.对每一个 Fdi做下列操作：找到 Xi所对应的列中具有相同符号的哪些行，
考察这些行中 li列的元素，若其中有 Ali，则全部改为 Ali ；否则全部改为 Bmli；
m 是这些行的行号最小值，应当注意的是，若某个 btli被改动，那么该表的 li
列中凡是的 btli 的符号（不管它是否是开始找到的那些行）均应作相应的更
改。如在某次更改之后，有一行成为 a1,a2,…, an，则算法终止。对 F中 P
个 FD逐一进行一次这样的处置，称为对 F的一次扫描。
操作,AB→C,
C→D, b14?a4
D→E, b15?a5,b25?a5
例,判断 R的分解 是否具有无损连接性。
已知,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 >。
解：
3.判断表中是否有,a1a2 a3a4 a5”行，若有，则 R的分解 ρ就具有无损连接
性。
现第一行就有：, a1a2 a3a4 a5”行。
故 R的分解 ρ就具有无损连接性。U
i Aj A B C D E
R1< A,B,C> a1 a2 a3 a4 a5
R2< C,D > b21 b22 a3 a4 a5
R3< D,E > b31 b32 b33 a4 a5
§ 7.4.3 模式分解的算法
1．算法 7.3：
（合成法）转换为 3NF的保持函数依赖的分解：
1.对 R <U,F>中的函数依赖集 F进行“极小化处理”（处理后得到的依
赖集仍记为 F）。
2,找出不在 F中出现的属性，把这样的属性构成一个关系模式。把这些
属性从 U中去掉，剩余的属性仍记为 U。
3.若有 X→A ∈ F，且 XA=U，则 ρ={R},算法终止。
4.否则，对 F按具有相同左部的原则分组（假定分为 k组），每一组函数
依赖 Fi′所涉及的全部属性形成一个属性集 Ui。若 Ui ?Uj（ i≠j）就去掉 Ui，由
于经过了步骤 2，故 U=∪ Ui （ i=1… k），于是 ρ= {R1< U1,F1 >,…, Rk<
Uk,Fk>}构成 R <U,F>的一个保持函数依赖的分解，并且每个 Ri< Ui,Fi>均
属 3NF。
2．举例说明：
已知,R <U,F>中 Fm=﹛ A→C, A→D, D→E, D→B, AF→G,
AF→H, AF→I, I→J ﹜,按算法 7.3分解 R <U,F>，设结果为 P1。
解,A→C, A→D, D→E, D→B,
AF→G, AF→H, AF→I, I→J
U={ABCDEFGHIJ}
U0=○A→C, A→D, D→E, D→B,AF→G, AF→H, AF→I, I→J
A→C, A→D
U1={ACD}
D→E, D→B, AF→G, AF→H,
AF→I, I→J
D→E, D→B
U2={DEB}
AF→G, AF→H,
AF→I, I→J
AF→G, AF→H, AF→I
U3={AFGIH}
I→J
U4={IJ}
－ A
－ D
－ AF
所以有：
Fu1={A→C, A→D}
Fu2={D→E, D→B}
Fu3={AF→G,
AF→H, AF→I}
Fu4={I→J}
即有：
P1 = {R1< U1,F1 >,R2< U2，
F2 >,R3< U3,F3 >,R4<
U4,F4>}
所以,P1∈ 3NF
1．算法 7.4：
转换为 3NF的即有无损连接性又保持函数依赖的分解：
1.设 X是 R <U,F>的码,R <U,F>已由算法 7.3分解为 ρ= {R1< U1,F1
>,R2< U2,F2 >,…, Rk< Uk,Fk>}，令 τ = ρ∪ {R*<X,FX>}。
2,若有某个 Ui, X? Ui,将 R*<X,FX>从 τ中去掉。
3,τ就是所求的分解。
2．举例说明：
已知,R <U,F>中已由算法 7.3分解为 ρ= {R1< {A,C,D},{A→C,
A→D} >, R2< {D,E,B},{D→E, D→B} >, R3< {A,F,G,H,I}，
{AF→G, AF→H, AF→I} >, R4< {I,J},{I→J} >,按算法 7.4分解 R <U，
F>，设结果为 P2。
解：
⑴．求 R <U,F>的码
AF+={ACDEB}
DF+={DEB}
AFF+={ACDEBFGHIJ}
IF+={IJ}
∵ AFF+=U,AF+ ≠ U,DF+ ≠ U,IF+ ≠ U
∴ AF是 R <U,F>的码
⑵,因为 AF是 R <U,F>的码
由算法 7.3的例子得：
令 τ = P1 ∪ {R*<AF,FAF>}= {R1< U1,F1 >,R2< U2,F2 >,R3<
U3,F3 >,R4< U4,F4>,R*<AF,FAF>} = {R1< {A,C,D},{A→C,
A→D} >, R2< {D,E,B},{D→E, D→B} >, R3< {A,F,G,H,I}，
{AF→G, AF→H, AF→I} >, R4< {I,J},{I→J} >,R*<{A,F},{AF →
AF}>} 。
又因 {AF} ? U3 。
所以将 R*<AF,FAF>从 τ中 去掉。
即,P2 = P1= {R1< {A,C,D},{A→C, A→D} >, R2< {D，
E,B},{D→E, D→B} >, R3< {A,F,G,H,I},{AF→G, AF→H,
AF→I} >, R4< {I,J},{I→J} >} 。
所以,P2∈ 3NF
1．算法 7.5：
转换为 BCNF的无损连接分解（分解法）：
1．令 ρ= {R <U,F>}
2,检查 ρ中各关系模式是否均属于 BCNF，若是，则算法
终止。
3,设 ρ中 Ri<Ui,Fi>不属于 BCNF，那么必有 X→A ∈ Fi+
（ A?X），且 X非 Ri的码 。因此,XA是 Ui的真子集，对 Ri进行
分解,?={S1,S2},Us1=XA,Us2=Ui – {A}，以 ?代替 Ri<Ui，
Fi>返回第二步。
2．举例说明：
已知,R <U,F>中 Fm=﹛ A→C, A→D, D→E, D→B, AF →G,
AF→H, AF→I, I→J ﹜,按算法 7.5分解 R <U,F>，设结果为 P3。
解,A→C, A→D, D→E, D→B,
AF→G, AF→H, AF→I, I→J
U={ABCDEFGHIJ},KEY= 4
A→C, A→D
U1={ACD},KEY=A
D→E, D→B, AF→G, AF→H,
AF→I, I→J
D→E, D→B
U2={DEB},KEY=D
AF→G, AF→H,
AF→I, I→J
AF→G, AF→H, AF→I
U3={AFGIH},KEY=AF
I→J, U4={IJ}
KEY=I
－ A
－ D
－ AF
R1∈ BCNF
R2∈ BCNF
R3∈ BCNFR4∈ BCNF
P3={R1<U1,F1>,R2<U2,F2>,R3<U3,F3>,R4<U4,F4>}
作业 5：
已知关系 R <U,F>,U=﹛ A,B,C,D,E,G﹜,
F=﹛ D→G, CD→E, C→A, A→B, C→B ﹜ 。
①．求 Fm
②,求 F+
③,求 R <U,F>的码
④,按算法 7.3分解 R <U,F>，设结果为 P1
⑤,验证 P1是否具有无损连接性
⑥,按算法 7.4分解 R <U,F>，设结果为 P2
⑦,按算法 7.5分解 R <U,F>，设结果为 P3
E4.2 5.用关系代数完成第二章习题 10中 (1)至 (5)的各项操作。
⑴求供应工程 J1零件的单位号码 SNO
T1= σJNO=‘J1’(SPJ)
T=πSNO (T1)
⑵ 求供应工程 J1零件 P1的供应单位号码
T1= σJNO=‘J1’ ∧ PNO=‘P1’(SPJ)
T=πSNO (T1)
⑶ 求供应工程 J1零件为红色的单位号码
T1= P∞SPJ
T=πSNO (σJNO=‘J1’ ∧ COLOR=‘红’ (T1))
⑷ 求没有使用天津单位供应的红色零件的工程号 JNO
T1=S∞SPJ∞P
T2=πJNO (σCITY=‘天津’ ∧ COLOR=‘红’ (T1))
T= πJNO (J) － T2
E4.3
⑸ 求至少用了单位 S1所供应的全部零件的工程号 JNO
T1= πJNO,PNO(SPJ)
T2=πPNO (σSNO=‘S1’(SPJ))
T= T1÷ T2
6.用关系演算语言 ALPHA完成第二章习题 10中 1至 5各项
操作。
⑴求供应工程 J1零件的单位号码 SNO
RANGE SPJ X
GET W(X.SNO), X,JNO=‘J1’
⑵ 求供应工程 J1零件 P1的供应单位号码
RANGE SPJ X
GET W(X.SNO), X,JNO=‘J1’ ∧ X,PNO=‘P1’
E4.4
⑶ 求供应工程 J1零件为红色的单位号码
RANGE P PX
SPJ X
GET W(S,SNO), ?X ?PX(X,SNO=S,SNO∧ X,JNO=‘J1’
∧ X,PNO=PX,PNO∧ PX,COLOR=‘红色’ )
⑷ 求没有使用天津单位供应的红色零件的工程号 JNO
RANGE S SX
P PX
SPJ SPJX
GET W(J,JNO), ?SPJX ?SX
?PX(SPJX,JNO=J,JNO∧ PX,PNO=SPJX,PNO∧ SX,SNO=SPJX,SNO
∧ PX,COLOR=‘红’ ∧ SX,CITY=‘天津’ )
∟
⑸ 求至少用了单位 S1所供应的全部零件的工程号 JNO
RANGE P PX
SPJ SPJX
SPJ SPJY
GET W(J,JNO),
?PX(?SPJX(SPJX,PNO=PX,PNO∧ SPJX,SNO=‘S1’)
?SPJY(SPJY,PNO=PX,PNO∧ SPJY,JNO=J,JNO))
第五章 练习题及解答
1,用 SQL写出第二章习题 10中的各项操作。（书 59页）
① 求供应工程 J1 零件的单位号码 SNO。
SELECT DISTINCT SNO
FROM SPJ
WHERE JNO=‘J1’
② 求供应工程 J1 零件 P1的供应单位号码 SNO。
SELECT SNO
FROM SPJ
WHERE PNO=‘P1’ AND JNO=‘J1’
③ 求供应工程 J1 零件为红色的单位号码 。
SELECT SNO
FROM S,P,SPJ
WHERE S,SNO=SPJ,SNO AND SPJ,JNO=‘J1’ AND P,
PNO=SPJ,PNO AND P,COLOR=‘红’
E5.2 ④ 求没有使用天津单位供应的红色零件的工程号 JNO。
SELECT JNO
FROM J
WHERE NOT EXISTS
( SELECT *
FROM S,P,SPJ
WHERE SPJ,JNO=J,JNO
AND S,SNO=SPJ,SNO AND P,PNO=SPJ,PNO
AND P,COLOR=‘红’ AND S,CITY=‘天津’ );
⑤ 求至少用了单位 S1所供应的全部零件的工程号 JNO。
SELECT DISTINCT JNO
FROM SPJ SPJX
WHERE NOT EXISTS
( SELECT *
FROM SPJ SPJY
WHERE SPJ,JNO=‘S1’
AND NOT EXISTS
( SELECT *
FROM SPJ SPJZ
WHERE SPJZ,SNO=SPJX,SNO
AND SPJZ,PNO=SPJY,PNO
2,什么是基本表？什么是视图？两者的区别与联系是什么？
基本表 —本身独立存在的表，在 SQL中一个关系对应一个表。
视图 —是从一个表或几个基本表（或视图）导出的表。
视图 基本表
区别 是一个虚表，数据库中只存
储视图的定义，不存储视图
所对应的数据。
是一个独立存在的表。
联系 视图是从一个或几个基本表（或视图）导出的表。
E5.3
3,DB2中允许对哪些视图更新？
只有从单个基本表导出的视图才允许对它执行更新操作。
4,视图的优点是什么？
① 视图对于数据库的重构造提供了一定程度的逻辑独立性；如数据库
扩大（增加了新字段，新关系），用户和用户程序不会受影响。
② 简化了用户观点；若这些数据不是直接来自基本表，则可以定义视
图，从而使用户眼中的数据结构简单而直截了当，并可大大简化用户的数
据查询操作，特别是把若干表连接在一起的视图，把从表到表所需要的连
接操作向用户隐蔽了起来。
③ 视图机制使不同的用户能以不同的方式看待同一数据。
④ 视图机制对机密数据提供了自动的安全保护功能。
5,SQL的特点是什么？
① 一体化的特点； SQL具有集 DDL,DML,DCL为一体的特点，用
SQL可以实现数据库生命期中的全部活动。
② 两种使用方式，统一的语法结构； SQL有 联机交互使用, 嵌入某
种高级程序设计语言程序中 两种使用方式，但其语法结构是基本一致的。
③ 高度非过程化；用户不必了解存取路径，存取路径的选择和 SQL
语句操作的过程由系统自动完成。
④ 语言简洁，易学易用； SQL完成核心功能一共用了 8个动词，其
语法简单，接近英语口语，因此易学易用。
第六章 练习题及解答
1.试给出各类关系系统的定义：
最小关系的系统 —支持关系数据结构和选择、投影、（自然）连接运算
三种关系操作。
关系上完备的系统 —支持关系数据结构和所有的关系代数操作（功能上
与关系代数等价）。
全关系系统 —支持关系模型的所有特征。
3.对学生 -课程数据库有如下的查询：
SELECT CN
FROM S,SC,C
WHERE S.S#=SC.S# AND SC.C#=C.C# AND S.SD=‘IS’
此查询要求信息系学生选修的课程名称。
试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语
法树进行优化处理，画出优化后的标准语法树。
内部表示语法树：
结果
Project(CN)
Select(S.SD=‘IS’)
Join(SC.C#=C.C#)
Join(SC.S#=C.S#) C
S SC
πCN
σ SC.C#=C.C#
×
C
SC
σ SC.S#=S.S#
σ S.SD=‘IS’
S
πCN
σ SC.C#=C.C#
×
C
SC
σ SC.S#=S.S#
σ S.SD=‘IS’
S
π SC.C#,C.C#,CN
×
πCN
σ SC.C#=C.C#
×
C
SC
σ SC.S#=S.S#
σ S.SD=‘IS’
S
π SC.C#,SC.S#,S.S#
×
π C.C#,CNπ SC.C#
πCN
σ SC.C#=C.C#
×
C
SC
σ SC.S#=S.S#
σ S.SD=‘IS’
S
π S.S#
×
π C.C#,CNπ SC.C#
π SC.C#,SC.S#
BCNF 比 3NF 更进一步，其消除 主属性 对 码 的部分与传递依赖。
1.定义 7.8：
关系模式 R<U,F>∈ 1NF，若 X→Y 且 Y?X时 X必含有码，则 R<U,F>
∈ BCNF 。
即,R<U,F> 中，每一个决定因素都包含码，则 R<U,F> ∈ BCNF。
2.结论：
⑴,所有非主属性对每一个码都是完全函数依赖。
显然，这是 3NF的要求所达到的，非主属性不部分、传递函数依赖于
码。
⑵,所有主属性对每一个不包含它的码，是完全函数依赖。
这是 BCNF的特征：让主属性对不包含它的码也无部分、传递 FD。如，
有 X∈ U,Y∈ U，且 X→Y, Y→X,若 Y′是 Y中的码，则有 Y′ →X 。
⑶,无任何属性完全函数依赖于非码的属性。
BCNF中没有任何属性对非码属性完全函数依赖。
3.实例：
例子 1,C〈 C#,CN,PC#,C#→CN, C#→PC# 〉
没有对 C#的部分和传递函数依赖。所以 C∈ 3NF。
又因 C中 C#是唯一的决定因素。所以 C∈ BCNF。
例子 2,S〈 S#,SN,SD,SA,S#→SA, S#→SD, SN →SA, S#→SD 〉
S有两个码,S#,SN。它们都由单个属性组成，互不相交。
没有对 S# 和 SN 的部分和传递函数依赖。所以 S∈ 3NF。
又因 S中 S# 和 SN 是唯一的决定因素。所以 S∈ BCNF。
4.讨论：
⑴,若 R∈ BCNF，则 R∈ 3NF。
证明：假设 R∈ BCNF且 R∈ 3NF，则必存在传递依赖有：
X →Y, Y →Z, Y→X, Y?X
由于 R ∈ BCNF，则 Y →Z 中的 Y必含有码 Y′
∴ Y→ Y′ （ Y中包含有 Y′）
Y′ →X （结论 2）
∴ Y→X
∴ 与假设不符
故 R∈ 3NF。
⑵,若 R ∈ 3NF，则 R未必属于 BCNF。
反例见书上 166页的例 2。
5.3NF与 BCNF的区别：
3NF中可能存在主属性对码的部分、传递函数依赖。
§ 7.2.7 多值依赖
1.引入：
在书 167页上的例子中
在关系模式 TEACH中,C—课程,T—教员,B—参考书，
有一组值 (C,B)，则必有一个 T 值与之对应。
同理，有一组值 (C,T)，则必有一个 B 值与之对应。
所对应的值只由 C 决定。
这就是要给大家介绍的多值依赖,C→→T, C→→B 。
2.定义 7.9：
设 R（ U）是属性集 U上的一个关系模式。 X,Y,Z是 U的子集，并且 Z=U-
X-Y，多值依赖 X→→Y 成立当且仅当对 R（ U）的任一关系 r,给定的一对（ x,z）
值有一组 Y的值，这组值仅仅决定于 x值而与 z值无关。
3.实例：
见书 168页的例 2
4.多值依赖的性质：
⑴,若 X→→Y,则 X→→Z,其中 Z=U-X-Y，即多值依赖的对称性。
证明：假设 X→→Z 不成立，
则根据多值依赖定义有元组在 Z上的取值与 Y有关，
存在两组值：（ x,yi），（ x,yj）,yi≠yj
在 Z上对应的元组不全相同
一般可假设 zk为（ x,yi）所对应的 Z值的集合，但不属于（ x,yj）所
对应的值集合，
则有（ x,yi,zk） ∈ r,
（ x,yj,zk） ∈ r,
又由多值依赖定义有 yi与 yj交换得一新元组（ x,yj,zk） ∈ r,
这与假设结论矛盾，
故 X→→Z 成立。
⑵,若 X→Y,则 X→→Y,即函数依赖是多值依赖的特殊情况。
这是由于当 X→Y 时，对 X的每一个值 x,Y有一个确定的值 y与之对应，
由多值依赖的定义可知,X→→Y
⑶,若 X→→Y,而 Z=○,则称 X→→Y 为平凡的多值依赖。
5.多值依赖与函数依赖的区别：
⑴,函数依赖：其有效性仅决定于 X,Y这两个属性集的值，只要在 R（ U）
的任何一个关系 r 中，元组在 X 和 Y上的值满足定义 7.1，则函数依赖 X→Y 在任
何属性集 W（ XY?W?U）上成立。
多值依赖：其有效性与属性集的范围有关,X→→Y 在 U上成立则在 W
（ XY?W?U）上成立，反之则不然。
⑵,若函数依赖 X→Y 在 R（ U）上成立，则对于任何 Y′ Y均有 X →Y′ 成立。
若多值依赖 X→→Y 若在 R（ U）上成立，则不能断言对于任何 Y′ Y均有
X →→Y′ 成立。
∩
∩
§ 7.2.8 4NF
4NF 是消除了非平凡且非函数依赖的多值依赖。
1.定义 7.10：
关系模式 R<U,F>∈ 1NF，若 X→→Y （ Y?X）是非平凡的多值依赖，且 X
含有码，则称 R<U,F> ∈ 4NF 。
注：一个关系模式若属于 4NF，则必然属于 BCNF。
R中所有平凡的多值依赖实际上是函数依赖。
2.非 4NF的反例：
书 168页上的例 2，虽然 W→→S, W→→C 是非平凡的多值依赖，但是 W
不是码，（ W,S,C）才是码。故 WSC∈ 4NF。
3.非 4NF的关系模式存在的问题：
数据冗余。
4.解决方法：
投影分解。
§ 7.2.9 规范化小结
规范化的目的是：消除关系模式中存在的插入异常、删除异常、修改复杂
和数据冗余等毛病。
基本思想是：逐步消除数据依赖中不合适的部分，使概念单一化。
1NF→2NF,消除非主属性对码的部分函数依赖。
2NF→3NF,消除非主属性对码的传递函数依赖。
3NF→BCNF,消除主属性对码的部分和传递函数依赖。
BCNF→4NF,消除非平凡且非函数依赖的多值依赖。
方法：通过对关系模式的投影分解来实现的。
§ 7.3* 数据依赖的公理系统
定义 7.11：
对于满足一组函数依赖 F 的关系模式 R <U,F>，其任何一个关系 r,若函
数依赖 X→Y 都成立，则称 F 逻辑蕴含 X→Y 。
定义 7.12：
在关系模式 R<U,F>中为 F所逻辑蕴含的函数依赖的全体叫做 F的闭包，
记为 F+
定义 7.13：
设 F为属性集 U上的一组函数依赖,X?U,XF+=﹛ A︱ X →A 能由 F根据
Armstrong公理导出 ﹜, XF+称为属性集 X关于函数依赖集 F的闭包。
因此，要判定 X →Y 是否能由 F根据 Armstrong公理导出，就要求出 XF+，
判定 Y是否为 XF+的子集。 这是由算法 7.1来完成的。
1.合并规则：由 X→Y, X→Z,有 X→YZ
2.伪传递规则：由 X→Y, WY→Z,有 XW→Z
3.分解规则：由 X→Y, Z?Y，有 X→Z
算法 7.1：
求属性集 X（ X?U）关于 U上的函数依赖集 F的闭包 XF+
输入,X,F
输出,XF+
步骤：
①,令 X(0)=X,i=0
②,求 B
③, X(i+1)=B∪ X(i)
④,判断 X(i+1)=X(i) 吗？
⑤,不等，则 i = i+1，返回②
⑥,相等，则 XF+ =X(i),算法终止
实例：
已知关系 R <U,F>,U=﹛ A,B,C,D,E﹜, F=﹛ AB→C, B→D,
C→E, EC→B, AC→B ﹜ 。
求 (AB)F+
由算法 7.1得：
设 X(0) ={AB}，
计算 X(1)，扫描 F中各函数依赖，找左部为 A,B,AB的函数依赖：
AB→C, B→D,
于是 X(1)=AB∪ CD={ABCD}，
因为 X(0) ≠ X(1)
计算 X(2)，扫描 F中各函数依赖，找左部为 X(1)的子集的函数依赖：
AC→B, C→E,
于是 X(2)= X(1) ∪ BE={ABCDE}，
因为 X(3) ＝ X(2)
所以 (AB)F+= X(2) ={ABCDE}。
补充：
已知关系 R <U,F>,U=﹛ A,B,C,D,E﹜, F=﹛ AB→C, B→D,
C→E, EC→B, AC→B ﹜ 。
求 R 的码？
解法：
1.求出所有可能存在的闭包 X(i) =XF+,
2.若 X(i) =U，则选出其中的 X，
3.在 X中选出最简的主属性组 Xi,
4,Xi 就是所求的码。
具体解为：
(AB)F+=﹛ ABCDE﹜
(B)F+=﹛ BD﹜
(C)F+=﹛ CBDE﹜
(EC)F+=﹛ CBDE﹜
(AC)F+=﹛ ABCDE﹜
(ABC)F+=﹛ ABCDE﹜
(ABCE)F+=﹛ ABCDE﹜
(BC)F+=﹛ BCDE﹜
(BEC)F+=﹛ BCDE﹜
(AEC)F+=﹛ ABCDE﹜
包含全部属性的有 (AB)F+,(AC)F+, (ABC)F+, (ABCE)F+, (AEC)F+
挑选出最简的是,(AB)F+, (AC)F+
所以 R 的码为,AB 和 AC
定义 7.14：
如果 F+=G+，就说函数依赖集 F覆盖 G（ F是 G的覆盖，或 G是 F的覆盖），
或 F与 G等价。
定义 7.15：
如果函数依赖集 F满足下列条件，则称 F为一个极小函数依赖集 Fm,亦
称为最小依赖集，最小覆盖。
⑴,F中任一函数依赖的右部仅含有一个属性。
⑵,F中不存在这样的函数依赖 X→A,使得 F与 F-﹛ X→A ﹜ 等价。
⑶, F中不存在这样的函数依赖 X→A, X有真子集 Z使得 F -
﹛ X→A ﹜∪ ﹛ Z→A ﹜ 与 F等价。
例：关系模式 S <U,F>,U=﹛ S#,SD,MN,CN,G﹜,
F=﹛ S#→SD, SD→MN,（ S#, CN） → G﹜ 。
设 F′=﹛ S#→SD, S#→MN, SD→MN,（ S#, CN） → G,（ S#, SD）
→ SD﹜ 。
由上面的定义可知,F为极小函数依赖集，而 F′不是。
定理 7.3：
每一个函数依赖集 F均等价于一个极小函数依赖集 Fm (此 Fm称为 F的最小
依赖集）。
求极小函数依赖集 Fm的步骤：
见书 174页
例 1：
已知,F=﹛ A→B, B→A, B→C, A→C, C→A ﹜
求 F 的极小函数依赖集 Fm
解：
1.化右部为单一属性,F=﹛ A→B, B→A, B→C, A→C, C→A ﹜
2,① 在 F中去掉 A→B, (A)F+={AC},∵ B∈ (A)F+, ∴ 不去掉。
②在 F中去掉 B→A, (B)F+={ABC},∵ A∈ (B)F+, ∴ 应去掉。
③在 F中去掉 B→C, (B)F+={B},∵ C∈ (B)F+, ∴ 不去掉。
④在 F中去掉 A→C, (A)F+={ABC},∵ C∈ (A)F+, ∴ 应去掉。
⑤ 在 F中去掉 C→A, (C)F+={C},∵ A∈ (C)F+, ∴ 不去掉。
3.因主属性是单属性，故不用再取其子集去考察。
故极小函数依赖集 Fm=﹛ A→B, B→C, C→A ﹜
例 2：
已知关系 R <U,F>,U=﹛ A,B,C,D,E,F,G,H,I,J﹜,
F=﹛ A→B, A→C, A→DE, D→E, DE→B, AF→GHI, I→J ﹜ 。
求 F 的极小函数依赖集 Fm
解：
1.化右部为单一属性：
① A→DE ?A→D, A→E
② AF→GHI ?AF→G, AF→H, AF→I
则 F=﹛ A→B, A→C, A→D, A→E, D→E, DE→B, AF→G,
AF→H, AF→I, I→J ﹜ 。
2,① A→B,记 G=F-﹛ A→B ﹜,
∴ (A)G+= ﹛ ACDEB﹜,
∴ B∈ (A)G+,
∴ 去掉 A→B,
F=F-﹛ A→B ﹜ =﹛ A→C, A→D, A→E, D→E, DE→B,
AF→G, AF→H, AF→I, I→J ﹜ 。
② A→C,记 G=F-﹛ A→C ﹜,
∴ (A)G+= ﹛ ADEB﹜,
∴ C∈ (A)G+,
∴ 不去掉 A→C,
F=﹛ A→C, A→D, A→E, D→E, DE→B, AF→G,
AF→H, AF→I, I→J ﹜ 。
③ A→E,记 G=F-﹛ A→E ﹜,
∴ (A)G+= ﹛ ACDEB﹜,
∴ E∈ (A)G+,
∴ 去掉 A→E,
F=F-﹛ A→E ﹜ =﹛ A→C, A→D, D→E, DE→B, AF→G,
AF→H, AF→I, I→J ﹜ 。
④ 同理考察,A→D, D→E, DE→B, AF→G, AF→H, AF→I,
I→J,它们都不能去掉。
故记 F为,F=﹛ A→C, A→D, D→E, DE→B, AF→G, AF→H,
AF→I, I→J ﹜ 。
3,函数依赖左部的分解
①,DE→B, ∴ (D)F+= ﹛ DEB﹜,
∴ B∈ (D)F+,
∴ 用 D→B 代替 DE→B,
记 F=﹛ A→C, A→D, D→E, D→B, AF→G, AF→H,
AF→I, I→J ﹜ 。
②,AF→G,
∴ (A)F+= ﹛ ACDEB﹜,
∴ (F)F+= ﹛ ACDEB﹜,
∵ G∈ (A)F+ ； G∈ (F)F+,
∴ 不能用 A→G 或 F→G 代替 AF→G,
记 F=﹛ A→C, A→D, D→E, D→B, AF→G, AF→H,
AF→I, I→J ﹜ 。
同理，可考察 AF→H, AF→I,它们都应保留。
所以,Fm=﹛ A→C, A→D, D→E, D→B, AF→G, AF→H, AF→I,
I→J ﹜ 。
作业 1：
书 182页练习题第 1题全部。
作业 2：
已知,R <U,F>,U=﹛ A,B,C,D,E,G﹜,
F=﹛ C→D, G→B, CG→E, B→A ﹜ 。
求 ① (C)F+, (G)F+, (B)F+, (CG)F+, (BC)F+, (BG)F+, (BCG)F+
② R 的码？
作业 3：
已知,R <U,F>,U=﹛ A,B,C,D,E,G﹜,
F=﹛ AB→C, D→EG, C→A, BE→C, BC→D, CG→BD,
ACD→B, CE→AG ﹜ 。
求 Fm
§ 7.4 模式的分解
书 175页的定义 7.16只要求 R<U,F>分解后的各关系模式的属性 Ui的并集
等 于 U,F在 Ui上的投影就构成了 Fi。
模式分解后产生的模式应与原模式等价，最起码的要求也要分解后产生
的模式不能丢失原模式的信息。
模式等价有三种不同定义：
①,分解具有“无损连接性”。
②,分解要“保持函数依赖”。
③,分解既要“保持函数依赖”，又要具有“无损连接性”。
这是我们实行分解的三条准则，分解准则不同，能达到的分离程度也不
同。
举例说明：
已知关系 R <U,F>,U=﹛ S#,SD,MN﹜, F=﹛ S#→SD, SD→MN ﹜ 。
在 R中存在传递函数依赖 S#→ MN,若要删除一个学生 S#,则将会把 MN也
一起删除；若 R中无学生 S#，则不能向 R中存入系主任的值 MN。即存在插入
异常和删除异常。一种分解如下：
①, ρ1 ={R1< S#,Ф>,R2< SD,Ф>,R3< MN,Ф >}
这样分解得到的是三个属性的集合（见书 176页），而且是通过自然连
接来实现向 R的恢复，其结果就是产生它们的笛卡尔积，元组增加了，信息
丢失了，这样的分解就不具有“无损连接性”。于是对 R又产生第二种分解：
②, ρ2 ={R1< {S#,SD},{S#→ SD} >,R2< {S#,MN},{S#→ MN} >}
这样分解对 R来说是可恢复的，但由于在 R中存在的函数依赖 SD→MN 在
R1,R2中都不存在了，其结果就是插入和删除异常仍未解决，故此分解不具
有“保持函数依赖性”。于是对 R又产生第三种分解：
③, ρ3 ={R1< {S#,SD},{S#→ SD} >,R2< {SD,MN},{SD→ MN} >}
这样分解既具有“无损连接性”，又,保持函数依赖性”，而且它解决
了更新异常，又没有丢失信息，这是我们希望得到的分解。
下面讨论“分解的无损连接性” 和“保持函数依赖性”。
§ 7.4 分解的无损连接性和保持函数依赖性
算法 7.2：
判别一个分解的无损连接性：
ρ={R1< U1,F1 >,…, Rk< Uk,Fk>}是 R< U,F >的一个分解,U={A1
,…, An},F={FD1,FD2,…, FDp}，不防设 F是一极小依赖集，记 FDi 为
Xi→A 1i
1.建立一张 n 列 k 行的表，每一列对应一个属性，每一行对应分解中的
一个关系模式，若属性 Aj属于 Ui，则在 j 列 i 行交叉处填上 aj，否则填上 bij
2,对每一个 FDi做下列操作：找到 Xi所对应的列中具有相同符号的哪些
行，考察这些行中 li列的元素，若其中有 Ali，则全部改为 Ali ；否则全部改为
Bmli； m 是这些行的行号最小值，应当注意的是，若某个 btli被改动，那么该
表的 li 列中凡是的 btli 的符号（不管它是否是开始找到的那些行）均应作相应
的更改。如在某次更改之后，有一行成为 a1,a2,…, an，则算法终止。对 F
中 P个 FD逐一进行一次这样的处置，称为对 F的一次扫描。
3.比较扫描前后，表有无变化。如有变化，则返回第 2步，否则算法终
止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有
限，因此循环必然终止。
定理 7.4,ρ 为无损连接分解的充分必要条件是算法 7.2终止时，表中有一
行为 a1,a2,…, an 。
例,判断 R的分解 是否具有无损连接性。
已知,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 >。
解：
1.构造初始表：
建立一张 5（ U中属性的个数）（ +1） 列 3（分解的 R个数） 行的表
，每一列对应一个属性，每一行对应分解中的一个关系模式，若属性 Aj属于
Ui，则在 j 列 i 行交叉处填上 aj，否则填上 bij。
Ui Aj A B C D E
R1< A,B,C> a1 a2 a3 b14 b15
R2< C,D > b21 b22 a3 a4 b25
R3< D,E > b31 b32 b33 a4 a5
例,判断 R的分解 是否具有无损连接性。
已知,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 >。
解：
Ui Aj A B C D E
R1< A,B,C> a1 a2 a3 b14 b15
R2< C,D > b21 b22 a3 a4 b25
R3< D,E > b31 b32 b33 a4 a5
2.对每一个 Fdi做下列操作：找到 Xi所对应的列中具有相同符号的哪些行，
考察这些行中 li列的元素，若其中有 Ali，则全部改为 Ali ；否则全部改为 Bmli；
m 是这些行的行号最小值，应当注意的是，若某个 btli被改动，那么该表的 li
列中凡是的 btli 的符号（不管它是否是开始找到的那些行）均应作相应的更
改。如在某次更改之后，有一行成为 a1,a2,…, an，则算法终止。对 F中 P
个 FD逐一进行一次这样的处置，称为对 F的一次扫描。
操作,AB→C,无相同符号的行，故不变
C→D, b14?a4
D→E, b15?a5,b25?a5
Ui Aj A B C D E
R1< A,B,C> a1 a2 a3 a4 a5
R2< C,D > b21 b22 a3 a4 a5
R3< D,E > b31 b32 b33 a4 a5
例,判断 R的分解 是否具有无损连接性。
已知,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 >。
解：
2.对每一个 Fdi做下列操作：找到 Xi所对应的列中具有相同符号的哪些行，
考察这些行中 li列的元素，若其中有 Ali，则全部改为 Ali ；否则全部改为 Bmli；
m 是这些行的行号最小值，应当注意的是，若某个 btli被改动，那么该表的 li
列中凡是的 btli 的符号（不管它是否是开始找到的那些行）均应作相应的更
改。如在某次更改之后，有一行成为 a1,a2,…, an，则算法终止。对 F中 P
个 FD逐一进行一次这样的处置，称为对 F的一次扫描。
操作,AB→C,
C→D, b14?a4
D→E, b15?a5,b25?a5
例,判断 R的分解 是否具有无损连接性。
已知,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 >。
解：
3.判断表中是否有,a1a2 a3a4 a5”行，若有，则 R的分解 ρ就具有无损连接
性。
现第一行就有：, a1a2 a3a4 a5”行。
故 R的分解 ρ就具有无损连接性。U
i Aj A B C D E
R1< A,B,C> a1 a2 a3 a4 a5
R2< C,D > b21 b22 a3 a4 a5
R3< D,E > b31 b32 b33 a4 a5
§ 7.4.3 模式分解的算法
1．算法 7.3：
（合成法）转换为 3NF的保持函数依赖的分解：
1.对 R <U,F>中的函数依赖集 F进行“极小化处理”（处理后得到的依
赖集仍记为 F）。
2,找出不在 F中出现的属性，把这样的属性构成一个关系模式。把这些
属性从 U中去掉，剩余的属性仍记为 U。
3.若有 X→A ∈ F，且 XA=U，则 ρ={R},算法终止。
4.否则，对 F按具有相同左部的原则分组（假定分为 k组），每一组函数
依赖 Fi′所涉及的全部属性形成一个属性集 Ui。若 Ui ?Uj（ i≠j）就去掉 Ui，由
于经过了步骤 2，故 U=∪ Ui （ i=1… k），于是 ρ= {R1< U1,F1 >,…, Rk<
Uk,Fk>}构成 R <U,F>的一个保持函数依赖的分解，并且每个 Ri< Ui,Fi>均
属 3NF。
2．举例说明：
已知,R <U,F>中 Fm=﹛ A→C, A→D, D→E, D→B, AF→G,
AF→H, AF→I, I→J ﹜,按算法 7.3分解 R <U,F>，设结果为 P1。
解,A→C, A→D, D→E, D→B,
AF→G, AF→H, AF→I, I→J
U={ABCDEFGHIJ}
U0=○A→C, A→D, D→E, D→B,AF→G, AF→H, AF→I, I→J
A→C, A→D
U1={ACD}
D→E, D→B, AF→G, AF→H,
AF→I, I→J
D→E, D→B
U2={DEB}
AF→G, AF→H,
AF→I, I→J
AF→G, AF→H, AF→I
U3={AFGIH}
I→J
U4={IJ}
－ A
－ D
－ AF
所以有：
Fu1={A→C, A→D}
Fu2={D→E, D→B}
Fu3={AF→G,
AF→H, AF→I}
Fu4={I→J}
即有：
P1 = {R1< U1,F1 >,R2< U2，
F2 >,R3< U3,F3 >,R4<
U4,F4>}
所以,P1∈ 3NF
1．算法 7.4：
转换为 3NF的即有无损连接性又保持函数依赖的分解：
1.设 X是 R <U,F>的码,R <U,F>已由算法 7.3分解为 ρ= {R1< U1,F1
>,R2< U2,F2 >,…, Rk< Uk,Fk>}，令 τ = ρ∪ {R*<X,FX>}。
2,若有某个 Ui, X? Ui,将 R*<X,FX>从 τ中去掉。
3,τ就是所求的分解。
2．举例说明：
已知,R <U,F>中已由算法 7.3分解为 ρ= {R1< {A,C,D},{A→C,
A→D} >, R2< {D,E,B},{D→E, D→B} >, R3< {A,F,G,H,I}，
{AF→G, AF→H, AF→I} >, R4< {I,J},{I→J} >,按算法 7.4分解 R <U，
F>，设结果为 P2。
解：
⑴．求 R <U,F>的码
AF+={ACDEB}
DF+={DEB}
AFF+={ACDEBFGHIJ}
IF+={IJ}
∵ AFF+=U,AF+ ≠ U,DF+ ≠ U,IF+ ≠ U
∴ AF是 R <U,F>的码
⑵,因为 AF是 R <U,F>的码
由算法 7.3的例子得：
令 τ = P1 ∪ {R*<AF,FAF>}= {R1< U1,F1 >,R2< U2,F2 >,R3<
U3,F3 >,R4< U4,F4>,R*<AF,FAF>} = {R1< {A,C,D},{A→C,
A→D} >, R2< {D,E,B},{D→E, D→B} >, R3< {A,F,G,H,I}，
{AF→G, AF→H, AF→I} >, R4< {I,J},{I→J} >,R*<{A,F},{AF →
AF}>} 。
又因 {AF} ? U3 。
所以将 R*<AF,FAF>从 τ中 去掉。
即,P2 = P1= {R1< {A,C,D},{A→C, A→D} >, R2< {D，
E,B},{D→E, D→B} >, R3< {A,F,G,H,I},{AF→G, AF→H,
AF→I} >, R4< {I,J},{I→J} >} 。
所以,P2∈ 3NF
1．算法 7.5：
转换为 BCNF的无损连接分解（分解法）：
1．令 ρ= {R <U,F>}
2,检查 ρ中各关系模式是否均属于 BCNF，若是，则算法
终止。
3,设 ρ中 Ri<Ui,Fi>不属于 BCNF，那么必有 X→A ∈ Fi+
（ A?X），且 X非 Ri的码 。因此,XA是 Ui的真子集，对 Ri进行
分解,?={S1,S2},Us1=XA,Us2=Ui – {A}，以 ?代替 Ri<Ui，
Fi>返回第二步。
2．举例说明：
已知,R <U,F>中 Fm=﹛ A→C, A→D, D→E, D→B, AF →G,
AF→H, AF→I, I→J ﹜,按算法 7.5分解 R <U,F>，设结果为 P3。
解,A→C, A→D, D→E, D→B,
AF→G, AF→H, AF→I, I→J
U={ABCDEFGHIJ},KEY= 4
A→C, A→D
U1={ACD},KEY=A
D→E, D→B, AF→G, AF→H,
AF→I, I→J
D→E, D→B
U2={DEB},KEY=D
AF→G, AF→H,
AF→I, I→J
AF→G, AF→H, AF→I
U3={AFGIH},KEY=AF
I→J, U4={IJ}
KEY=I
－ A
－ D
－ AF
R1∈ BCNF
R2∈ BCNF
R3∈ BCNFR4∈ BCNF
P3={R1<U1,F1>,R2<U2,F2>,R3<U3,F3>,R4<U4,F4>}
作业 5：
已知关系 R <U,F>,U=﹛ A,B,C,D,E,G﹜,
F=﹛ D→G, CD→E, C→A, A→B, C→B ﹜ 。
①．求 Fm
②,求 F+
③,求 R <U,F>的码
④,按算法 7.3分解 R <U,F>，设结果为 P1
⑤,验证 P1是否具有无损连接性
⑥,按算法 7.4分解 R <U,F>，设结果为 P2
⑦,按算法 7.5分解 R <U,F>，设结果为 P3
E4.2 5.用关系代数完成第二章习题 10中 (1)至 (5)的各项操作。
⑴求供应工程 J1零件的单位号码 SNO
T1= σJNO=‘J1’(SPJ)
T=πSNO (T1)
⑵ 求供应工程 J1零件 P1的供应单位号码
T1= σJNO=‘J1’ ∧ PNO=‘P1’(SPJ)
T=πSNO (T1)
⑶ 求供应工程 J1零件为红色的单位号码
T1= P∞SPJ
T=πSNO (σJNO=‘J1’ ∧ COLOR=‘红’ (T1))
⑷ 求没有使用天津单位供应的红色零件的工程号 JNO
T1=S∞SPJ∞P
T2=πJNO (σCITY=‘天津’ ∧ COLOR=‘红’ (T1))
T= πJNO (J) － T2
E4.3
⑸ 求至少用了单位 S1所供应的全部零件的工程号 JNO
T1= πJNO,PNO(SPJ)
T2=πPNO (σSNO=‘S1’(SPJ))
T= T1÷ T2
6.用关系演算语言 ALPHA完成第二章习题 10中 1至 5各项
操作。
⑴求供应工程 J1零件的单位号码 SNO
RANGE SPJ X
GET W(X.SNO), X,JNO=‘J1’
⑵ 求供应工程 J1零件 P1的供应单位号码
RANGE SPJ X
GET W(X.SNO), X,JNO=‘J1’ ∧ X,PNO=‘P1’
E4.4
⑶ 求供应工程 J1零件为红色的单位号码
RANGE P PX
SPJ X
GET W(S,SNO), ?X ?PX(X,SNO=S,SNO∧ X,JNO=‘J1’
∧ X,PNO=PX,PNO∧ PX,COLOR=‘红色’ )
⑷ 求没有使用天津单位供应的红色零件的工程号 JNO
RANGE S SX
P PX
SPJ SPJX
GET W(J,JNO), ?SPJX ?SX
?PX(SPJX,JNO=J,JNO∧ PX,PNO=SPJX,PNO∧ SX,SNO=SPJX,SNO
∧ PX,COLOR=‘红’ ∧ SX,CITY=‘天津’ )
∟
⑸ 求至少用了单位 S1所供应的全部零件的工程号 JNO
RANGE P PX
SPJ SPJX
SPJ SPJY
GET W(J,JNO),
?PX(?SPJX(SPJX,PNO=PX,PNO∧ SPJX,SNO=‘S1’)
?SPJY(SPJY,PNO=PX,PNO∧ SPJY,JNO=J,JNO))
第五章 练习题及解答
1,用 SQL写出第二章习题 10中的各项操作。（书 59页）
① 求供应工程 J1 零件的单位号码 SNO。
SELECT DISTINCT SNO
FROM SPJ
WHERE JNO=‘J1’
② 求供应工程 J1 零件 P1的供应单位号码 SNO。
SELECT SNO
FROM SPJ
WHERE PNO=‘P1’ AND JNO=‘J1’
③ 求供应工程 J1 零件为红色的单位号码 。
SELECT SNO
FROM S,P,SPJ
WHERE S,SNO=SPJ,SNO AND SPJ,JNO=‘J1’ AND P,
PNO=SPJ,PNO AND P,COLOR=‘红’
E5.2 ④ 求没有使用天津单位供应的红色零件的工程号 JNO。
SELECT JNO
FROM J
WHERE NOT EXISTS
( SELECT *
FROM S,P,SPJ
WHERE SPJ,JNO=J,JNO
AND S,SNO=SPJ,SNO AND P,PNO=SPJ,PNO
AND P,COLOR=‘红’ AND S,CITY=‘天津’ );
⑤ 求至少用了单位 S1所供应的全部零件的工程号 JNO。
SELECT DISTINCT JNO
FROM SPJ SPJX
WHERE NOT EXISTS
( SELECT *
FROM SPJ SPJY
WHERE SPJ,JNO=‘S1’
AND NOT EXISTS
( SELECT *
FROM SPJ SPJZ
WHERE SPJZ,SNO=SPJX,SNO
AND SPJZ,PNO=SPJY,PNO
2,什么是基本表？什么是视图？两者的区别与联系是什么？
基本表 —本身独立存在的表，在 SQL中一个关系对应一个表。
视图 —是从一个表或几个基本表（或视图）导出的表。
视图 基本表
区别 是一个虚表，数据库中只存
储视图的定义，不存储视图
所对应的数据。
是一个独立存在的表。
联系 视图是从一个或几个基本表（或视图）导出的表。
E5.3
3,DB2中允许对哪些视图更新？
只有从单个基本表导出的视图才允许对它执行更新操作。
4,视图的优点是什么？
① 视图对于数据库的重构造提供了一定程度的逻辑独立性；如数据库
扩大（增加了新字段，新关系），用户和用户程序不会受影响。
② 简化了用户观点；若这些数据不是直接来自基本表，则可以定义视
图，从而使用户眼中的数据结构简单而直截了当，并可大大简化用户的数
据查询操作，特别是把若干表连接在一起的视图，把从表到表所需要的连
接操作向用户隐蔽了起来。
③ 视图机制使不同的用户能以不同的方式看待同一数据。
④ 视图机制对机密数据提供了自动的安全保护功能。
5,SQL的特点是什么？
① 一体化的特点； SQL具有集 DDL,DML,DCL为一体的特点，用
SQL可以实现数据库生命期中的全部活动。
② 两种使用方式，统一的语法结构； SQL有 联机交互使用, 嵌入某
种高级程序设计语言程序中 两种使用方式，但其语法结构是基本一致的。
③ 高度非过程化；用户不必了解存取路径，存取路径的选择和 SQL
语句操作的过程由系统自动完成。
④ 语言简洁，易学易用； SQL完成核心功能一共用了 8个动词，其
语法简单，接近英语口语，因此易学易用。
第六章 练习题及解答
1.试给出各类关系系统的定义：
最小关系的系统 —支持关系数据结构和选择、投影、（自然）连接运算
三种关系操作。
关系上完备的系统 —支持关系数据结构和所有的关系代数操作（功能上
与关系代数等价）。
全关系系统 —支持关系模型的所有特征。
3.对学生 -课程数据库有如下的查询：
SELECT CN
FROM S,SC,C
WHERE S.S#=SC.S# AND SC.C#=C.C# AND S.SD=‘IS’
此查询要求信息系学生选修的课程名称。
试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语
法树进行优化处理，画出优化后的标准语法树。
内部表示语法树：
结果
Project(CN)
Select(S.SD=‘IS’)
Join(SC.C#=C.C#)
Join(SC.S#=C.S#) C
S SC
πCN
σ SC.C#=C.C#
×
C
SC
σ SC.S#=S.S#
σ S.SD=‘IS’
S
πCN
σ SC.C#=C.C#
×
C
SC
σ SC.S#=S.S#
σ S.SD=‘IS’
S
π SC.C#,C.C#,CN
×
πCN
σ SC.C#=C.C#
×
C
SC
σ SC.S#=S.S#
σ S.SD=‘IS’
S
π SC.C#,SC.S#,S.S#
×
π C.C#,CNπ SC.C#
πCN
σ SC.C#=C.C#
×
C
SC
σ SC.S#=S.S#
σ S.SD=‘IS’
S
π S.S#
×
π C.C#,CNπ SC.C#
π SC.C#,SC.S#
