练习题3
3.1解释下列名词 1．函数依赖：
设有关系模式R（U），X和Y是属性集U的子集，函数依赖（functional dependency，简记为FD）是形为X→Y的一个命题，只要r是R的当前关系，对r中任意两个元组t和s，都有t[X]=s[X]蕴涵t[Y]=s[Y],那么称FD X→Y在关系模式R（U）中成立。
这里t[X]表示元组t在属性集X上的值，其余类同。X→Y读作“X函数决定Y”，或“Y函数依赖于X”。FD是对关系模式R的一切可能的关系r定义的。对于当前关系r的任意两个元组，如果X值相同，则要求Y值也相同，即有一个X值就有一个Y值与之对应，或者说Y值由X值决定。因而这种依赖称为函数依赖。
2．平凡的函数依赖
对于FD X→Y,如果Y?X，那么称X→Y是一个“平凡的FD”，否则称为“非平凡的FD”。
正如名称所示，平凡的FD并没有实际意义，根据规则A1就可推出。人们感兴趣的是非平凡的FD。只有非平凡的FD才和“真正的”完整性约束条件相关。
从规则A4和A5，立即可得到下面的定理。 定理3.3 如果A1??An是关系模式R的属性集，那么X→A1??An成立的充分必要条件是X→Ai（i=1,?，n）成立。
3．函数依赖集F的闭包F+（Closure）
设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集F的闭包（Closure），记为F+。即
F+={ X→Y | F|=X→Y}。
4．属性集X的闭包X+
设F是属性集U上的FD集，X是U的子集，那么（相对于F）属性集X的闭包用X+
表示，它是一个从F集使用FD推理规则推出的所有满足X→A的属性A的集合：
+
X={属性A | F|=X→A }
5．函数依赖的逻辑蕴含 设F是在关系模式R上成立的函数依赖的集合，X→Y是一个函数依赖。如果对于R的每个满足F的关系r也满足X→Y，那么称F逻辑蕴涵X→Y，记为F|=X→Y。
6．函数依赖集的等价
如果关系模式R（U）上的两个函数依赖集F和G，有F+=G+，则称F和G是等价的函数依赖集。
7．最小依赖集
如果函数依赖集G满足下列三个条件，则称为G是最小依赖集。 （1）G中每个FD的右边都是单属性。
（2）G中没有冗余的F，即G中不存在这样的函数依赖X→Y，使得G—{X→Y}与G等价。
（3）G中每个FD的左边没有冗余的属性，即G中不存在这样的函数依赖X→Y，X
有真子集W使得G—{X→Y}∪{W→Y}与G等价。 显然，每个函数依赖集至少存在一个等价的最小依赖集，但并不一定惟一。
8．无损分解
设R是一个关系模式，F是R上的一个FD集。R分解成数据库模式?={R1，R2?Rk}。
如果对R中满足F的每一个关系r，都有
9．泛关系假设
无损分解定义有一个先决条件，即r是R的一个关系。也就是先存在r（泛关系）的情况下，再去谈论分解，这就是关系数据库理论中著名的“泛关系假设”（Univarsal Relation Assumption）。
有泛关系假设时，r与m?（r）之间的联系，可用图3.3表示。从图中可看出m?（r）有两个性质：
（1）r?m?（r）
（2）设s=m?（r），则?R(r)=ri
i
r=?R(r)??R(r)????R(r)
12k那么称分解?相对于F是“无损连接分解”（Lossless Join Decomposition），简称为“无
损分解”，否则称为“损失分解”（Lossy Decomposition）。
R r s
?={R1，R2?Rk}
? r1，r2，?，rk
?
?
图3.3 泛关系假设下关系模式分解的示意图
10．Chase过程
“追踪”（chase）过程，用于测试一个分解是否是无损分解。
追踪过程的算法（无损分解的测试）
输入：关系模式R=A1?An，F是R上成立的函数依赖集，?={R1，?，Rk}是R的一
个分解。 输出：判断?相对于F是否具有无损分解特征。
方法：
①构造一张k行n列的表格，每列对于一个属性Aj（1≤j≤n），每行对于一个模式Ri
（1≤i≤k）。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上bij。 ②把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改反复如下：
对于F中一个FD X→Y，如果表格中有两行在X值上相对，在Y值上不相等，那么把这
两行在Y值上也改成相等的值。如果Y值中有一个是aj，那么另一个也改成aj；如果没有aj，那么用其一个bij替换另一个值（尽量把下标ij改成较小的数）。一直到表格不能修改为止。（这个过程称为Chase过程）
③若修改的最后一张表格中有一行是全a，即a1a2?an，那么称?相对于F是无损分解，
否则称损失分解。
11．保持函数依赖
分解的另一个特征是在分解的过程中能否函数依赖集，如果不能保持FD，那么数据的
语义就会出现混乱。
设F是属性集U上的FD集，Z是U的子集，F在Z上的投影用?Z(F)表示，定义为
?Z(F)?{X?Y|X?Y?F,且XY?Z}
k?
设?={R1，?，Rk}是R的一个分解，F是R上的FD集，如果有??R（F）|?F，那么
ii?1称分解?保持函数依赖集F。
12．1NF
如果关系模式R的每个关系r的属性值都是不可分的原子值，那么称R是第一范式（First Normal Form，简记为1NF）的模式。
13．2NF
如果关系模式R是1NF，且每个非主属性完全函数依赖于候选键，那么称R是第二范式（2NF）的模式。
14．3NF
如果关系模式R是1NF，且每个非主属性都不传递依赖于R的候选键，那么称R是第三
范式（3NF）的模式。
15．BCNF
如果关系模式R是1NF，且每个属性都不传递依赖于R的候选键，那么称R是BCNF。