模式分解

2.保持FD（函数依赖）的分解

定义1：设F是属性集U上的FD集，Z是U的子集，F在Z上的投影用πZ(F)表示，定义为

πZ(F)={X→Y|X→Y∈F+，且XYZ}

定义2. 设},...{1KRR 是R的一个分解，F是R上的FD集，如果有)(1FRiki╞ F，那么称分解保持函数依赖集F。

根据定义1，测试一个分解是否保持FD，比较可行的方法是逐步验证F中的每个FD是否被)(1FRiki逻辑蕴涵。如果F的投影不蕴涵F，而我们又用},...{1KRR表达R，很可能会找到一个数据库实例 满足投影后的依赖，但不满足F。对的更新也有可能使r违反FD。

案例1：

R（T#，TITLE，SALARY）。如果规定每个教师只有一个职称，并且每个职称只有 一个工资数目，那么R上的FD有T#→TITLE和TITLE →SALARY。

如果R分解成={R1，R2}，其中R1={T#，TITLE}，R2={T#，SALARY }。则该分解具有无损连接性，但未保持函数依赖，丢失了依赖TITLE →SALARY。

习题1：

设关系模式R（ABC），={AB，AC}是R的一个分解。试分析分别在F1={A→B}；F2={A→C，B→C}，F3={B→A}，F4={C

→B，B→A}情况下，是否具有无损分解和保持FD的分解特性。

算法1：分解成2NF模式集的算法

设关系模式R（U），主码是W，R上还存在FD X→Z，并且Z是非主属性和X⊂W，那么W→Z就是非主属性对码的部分依赖。此时，应把R分解成两个关系模式：

R1（XZ），主码是X；

R2（Y），其中Y=U-Z，主码仍为W，外码是X（参照R1）

利用外码和主码的连接可以从R1和R2重新得到R。

如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中的每个关系模式都是2NF为止。

案例2：设有一个反映球队及球队队员每场比赛进球数的关系模式：

R（队员编号，队员名，比赛场次，进球数，球队名，教练名）

如果规定每个队员只能属于一个球队，每个球队只有一个教练，队员名可能重复。

（1）试写出关系模式R的基本FD和关键码。

（2）说明R不是2NF模式的理由，并把R分解成2NF模式集。

算法2：分解成3NF模式集的算法

设关系模式R（U），主码是W，R上还存在FD X→Z，并且Z是非主属性，Z /⊆X，X不是候选码，那么W→Z就是非主属性对码的传递依赖。此时，应把R分解成两个关系模式：

R1（XZ），主码是X；

R2（Y），其中Y=U-Z，主码仍为W，外码是X（参照R1）

利用外码和主码的连接可以从R1和R2重新得到R。

如果R1和R2还不是3NF，则重复上述过程，一直到数据库模式中的每个关系模式都是3NF为止。

案例3：进而把案例2的R分解成3NF模式集，并说明理由。

算法3. 分解成3NF模式集的合成算法

无损分解，且保持依赖地分解成3NF模式集。

（1） 对于关系模式R和R上成立的FD集F，先求出F 的最小依赖集，然后再把最小依赖集中那些左部相同的FD用合并性合并起来。

（2） 对最小依赖集中，每个FD X→Y去构成一个模式XY。

（3） 在构成的模式集中，如果每个模式都不包含R的侯选码，那么把侯选码作为一个模式放入模式集中。

这样得到的模式集是关系模式R的一个分解，并且这个分解即是无损分解，又保持了FD。

案例4：设关系模式R（ABCDE），R的最小依赖集为{A→B，C→D}。从依赖集可知，R 的侯选码为ACE。

先根据最小依赖集，可知，={ AB，CD}，然后再加入由侯选码组成的模式ACE。因此最后结果={AB，CD，ACE}是一个即保持FD又具有无损分解性。

课后练习题：

简述函数依赖集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| U |W→Y| 与G等价。

关系模式R（ABCDE）上FD集为F，并且F={A→BC，CD→E，B→D，E→A}，求R的候选健及B+。

解：函数依赖中的只在左边出现的属性：无 ；

只在右边出现的属性：无；

左右都没出现的属性：无

左右都出现的属性：A,B,C,D,E

A的闭包：A+为ABCDE=U, 即A是候选码；

E的闭包：E +为ABCDE=U, E是候选码。

CD的闭包： CD+为ABCDE =U,CD是候选码。

B的闭包B+：

令U0=B, 在依赖中，找到B→D,

U1=U0 ∪ D = BD, 依赖中，左边为B,D,或BD的没有了，即B+ =BD

案例：设有一个反应公司职工相关信息的关系模式：

R(职工号，职工名，部门号，工资，部门名，部门主任，社团名，社团角色)

如果规定：

职工号、部门号惟一；每个部门有多名职工，每名职工在固定的部门；每个部门有一个部门主任；每个职工可以参加多个社团，并且在社团中承担一定的角色，每个社团有多名职工。

(1)根据上述规定，写出模式R的基本FD和关键码。

解：R基本FD: 职工号→职工名，职工号→部门号，部门号→部门名，部门号→部门主任，（职工号，社团号）→社团角色

R关键码为：（职工号，社团号）

(2)R最高达到第几范式，并说明理由。

解：最高达到1NF，因为在函数依赖中存在“ 职工号→职工名”，且候选码是（职工号，社团号） ，存在非主属性对码的部分函数依赖。

(3)将R规范到3NF。

解：按照左部相同原则将FD分组:

（1）: 职工号→职工名，职工号→部门号

（2）：部门号→部门名，部门号→部门主任

（3）：（职工号，社团号）→社团角色

将上述每组中涉及的属性组成一个关系模式如下所示：

R1(职工号，职工名，部门名)

R2(部门号，部门名，部门主任)

R3（职工号，社团号，社团角色）

42．设有一个反映球队及球队队员每场比赛进球数的关系模式：

R（队员编号，队员名，比赛场次，进球数，球队名，教练名）

如果规定每个队员只能属于一个球队，每个球队只有一个教练，队员名可能重复。

（1）试写出关系模式R的基本FD和关键码。

解：FD：队员号→球队名，队员号→队员名，球队名→教练名，队员号→教练名，（队员号，比赛场次）→进球数

关键码为：（队员号，比赛场次）

（2）说明R不是2NF模式的理由，并把R分解成2NF模式集。

由依赖（队员号，比赛场次）→队员名；队员号→队员名，可知，存在非主属性对码的部分依赖。

分解成2NF 为：

R1（ 队员号，队员名，球队名，教练名）和R2(队员号，比赛场次，进球数)

（3）进而把R分解成3NF模式集，并说明理由。

按照分解3NF分解算法：

R1（ 队员号，队员名，球队名，教练名）存在队员号→教练名是非主属性对码的传递依赖。把R1进行分解，分为R11，R12。

R11（球队名，教练名），主码是球队名；

R12（队员号，队员名，球队名），主码是队员号。

R11，R12与R2一起是把R分解3NF模式的一个分解。

把R分解3NF ：合成算法：

 最小依赖集F：队员号→球队名，队员号→队员名，球队名→教练名，（队员号，比赛场次）→进球数，再把F中那些左部相同的FD用合并性合并起来。把队员号→球队名，队员号→队员名合并：队员号→球队名队员名；

F变为：队员号→球队名队员名，球队名→教练名，（队员号，比赛场次）→进球数， 由F可知，侯选码为“队员号，比赛场次”

 对F中每个FD，X→Y去构成一个模式 XY。

R1（队员号，队员名，球队名）；

R2（球队名，教练名）；

R3(队员号，比赛场次，进球数)

 R3中包含侯选码“队员号，比赛场次”，就不用单独把侯选码作为一个模式放入模式集中。

39．设有一个反映学生及其所选课程信息的关系模式：

R(学生号，学生名，学生系别，系办公地点，课程号，课程名，授课教师，成绩)

如果规定：

学生号、课程号惟一；每门课程只有一位授课教师；每个系的办公地点固定。学生名和课程名有可能重复。

每个学生可以选修多门课程，每门课程可以有多个学生选修；学生选修课程最终会有选修成绩。

问题(1)根据上述规定，写出模式R的基本FD和关键码。

解：R的基本函数依赖FD 有：学号→学生名，学号→学生系别，学生系别→系办公地点，课程号→课程名，课程号→授课教师，（学号，课程号）→成绩

问题(2)R最高达到第几范式，并说明理由。

解：R最高达到第一范式，因为该关系模式中码是（学号，课程号），其中，学号→学生名，（学号，课程号）→学生名，可知存在非主属性学生名部分依赖于码（学号，课程号）。

问题(3)将R规范到3NF。

解：将关系R的函数依赖集FD进行极小化处理,得到的极小函数依赖集，即本题的基本函数依赖。

将这些函数依赖按具有相同左部的原则分组，可分为如下四组:

Z1: 学号→学生名，学号→学生系别，涉及的属性集为（学号，学生名，学生系别）

Z2: 学生系别→系办公地点， 涉及的属性集为（学生系别，系办公地点）

Z3: 课程号→课程名，课程号→授课教师，涉及的属性集为（课程号，课程名，授课教师）

Z4:（学号，课程号）→成绩，涉及的属性集为（学号，课程号，成绩）

因此，根据算法，以上各个属性集构成的关系模式即满足第3范式。将R分解的关系模式如下所示：

学生（学号，学生名，学生系别）

系（学生系别，系办公地点）

课程（课程号，课程名，授课教师）

选修（学号，课程号，成绩）