DB2605 - 关系规范化设计

一、有函数依赖集 \(S = \{ DEF \to A,\ DF \to CE,\ A \to BDE,\ E \to B \}\)，请计算它的极小函数依赖集。请简要写出极小函数依赖集计算算法（补充算法1）的计算过程。

1. 令 \(G = \{DEF \rightarrow A, DF \rightarrow C, DF \rightarrow E, A \rightarrow B, A \rightarrow D, A \rightarrow E, E \rightarrow B\}\)
2. 由 \(A \in (DF)_G^+ = \{D, F, C, E, A, B\}\) 故可用 \(DF \rightarrow A\) 替换 \(G\) 中的 \(DEF \rightarrow A\) 此时 \(G = \{DF \rightarrow A, DF \rightarrow C, DF \rightarrow E, A \rightarrow B, A \rightarrow D, A \rightarrow E, E \rightarrow B\}\) 经检验，此时不存在可消除的左部冗余属性
3. ① 令 \(G' = G - \{A \rightarrow B\}\)， 又 \(B \in A_{G'}^+ = \{A, D, E, B\}\) 故可删除 \(G\) 中 \(A \rightarrow B\)，此时 \(G = \{DF \rightarrow A, DF \rightarrow C, DF \rightarrow E, A \rightarrow D, A \rightarrow E, E \rightarrow B\}\) ② 令 \(G'' = G - \{DF \rightarrow E\}\) 又 \(E \in (DF)_{G''}^+ = \{D, F, A, C, E, B\}\) 故可删除 \(G\) 中 \(DF \rightarrow E\)， 此时 \(G = \{DF \rightarrow A, DF \rightarrow C, A \rightarrow D, A \rightarrow E, E \rightarrow B\}\) 经检验，此时不存在冗余的函数依赖
4. 将 \(G\) 中 \(DF \rightarrow A, DF \rightarrow C\) 合并为 \(DF \rightarrow AC\) 将 \(G\) 中 \(A \rightarrow D, A \rightarrow E\) 合并为 \(A \rightarrow DE\) 故 \(G = \{DF \rightarrow AC, A \rightarrow DE, E \rightarrow B\}\)

即 \(S\) 的极小函数依赖集为 \(\{ DF \to AC, A \to DE, E \to B \}\)

二、有关系模式 \(R(A, B, C, D, E, F)\) 及其极小函数依赖集：\(\{ B \to F,\ AD \to BE,\ E \to CD \}\)

1.请计算得到关系 \(R\) 的所有候选码，简要写出候选码计算算法（补充算法2）的计算过程；

只在函数依赖左边出现的属性 \(U_L = \{A\}\)
只在函数依赖右边出现的属性 \(U_R = \{C, F\}\)
在函数依赖两边出现的属性 \(U_A = \{B, D, E\}\)
故 \(A\) 是每一个候选码的组成部分
记 \(F = \{B \to F, AD \to BE, E \to CD\}\)，\(U = \{A, B, C, D, E, F\}\)
令 \(K = U - U_R = \{A, B, D, E\}\)

由 \((K - B)^+_F = \{A, B, C, D, E, F\} = U\)
故 \(K = K - B = \{A, D, E\}\)
由 \((K - D)^+_F = \{A, B, C, D, E, F\} = U\)
故 \(K = K - D = \{A, E\}\)
由 \((K - E)^+_F = \{A\} \neq U\)
故 \(R\) 的一个候选码为 \(\{A, E\}\)

同理，继续按 \(U_A = \{B, D, E\}\) 的不同顺序计算 \(K\) 可得到 \(R\) 的所有候选码为 \(\{A, E\}, \{A, D\}\)

2.关系 \(R\) 最高能够满足到第几范式？请简单说明理由；

关系 \(R\) 的非主属性为 \(\{B, C, F\}\)

对于候选码 \(\{A, E\}\)，由 \(E \rightarrow CD\) 即 \(E \rightarrow C\)

有 \((A, E) \xrightarrow{P} C\)，故 \(R \notin 2NF\)

故关系 \(R\) 最高能够满足到 \(1NF\)

表示候选码时使用花括号，表示函数依赖时使用圆括号

3.关系 \(R\) 是否满足 \(3NF\) ？如不满足，请调用算法 6.3 & 6.4，将关系模式 \(R\) 直接分解到满足 \(3NF\)，且分解具有无损连接性和保持函数依赖性；

由 2 得 \(R \notin 2NF\)，则 \(R \notin 3NF\)

令 \(P = \varnothing\)，

\(Z_1(U_1, F_1) = Z_1(\{B, F\}, \{B \to F\})\)，

\(Z_2(U_2, F_2) = Z_2(\{A, B, D, E\}, \{AD \to BE\})\)，

\(Z_3(U_3, F_3) = Z_3(\{C, D, E\}, \{E \to CD\})\)，

则 \(P = \{Z_1, Z_2, Z_3\}\)

对于关系 \(R\) 的所有候选码 \(\{A, E\}, \{A, D\}\)

\(\{A, E\} \subseteq U_2\), \(\{A, D\} \subseteq U_2\)

故 \(P = \{Z_1, Z_2, Z_3\}\)

故关系 \(R\) 满足 \(3NF\) 且具有无损连接性和保持函数依赖的分解为

\(\{Z_1(\{B, F\}, \{B \to F\}),~ Z_2(\{A, B, D, E\}, \{AD \to BE\}),~ Z_3(\{C, D, E\}, \{E \to CD\})\}\)

4.上述分解结果是否满足 \(BCNF\) ？如不满足，请调用算法 6.5 将其进一步分解到满足 \(BCNF\) 并说明理由。

对于 \(Z_2(\{A, B, D, E\}, \{AD \rightarrow BE\})\)

由极小函数依赖集 \(F\) 中的 \(E \rightarrow CD\)，有 \(E \rightarrow D\) 且 \(D \notin E\)

又 \(E, D \in U_2\)，\(F_2\) 是 \(F\) 在 \(U_2 = \{A,B,D,E\}\) 上的投影

故 \(E \rightarrow D\) 在 \(Z_2\) 上成立

又 \(Z_2\) 的候选码为 \(\{A, E\}, \{A, D\}\)，\(E\) 不是 \(Z_2\) 的候选码

故 \(Z_2 \notin BCNF\)，即 3 的分解结果不满足 BCNF

令 \(U_{S_1} = \{E, D\}, U_{S_2} = U_2 - D = \{A, B, E\}\)

由 \(E \rightarrow CD, AD \rightarrow BE\)，有 \(AE \rightarrow AD \rightarrow B\)

则 \(F_{S_1} = \{E \rightarrow D\}, F_{S_2} = \{AE \rightarrow B\}\)

令 \(\sigma = \{S_1(U_{S_1}, F_{S_1}), S_2(U_{S_2}, F_{S_2})\}\)

以 \(\sigma\) 替换 \(\rho\) 中的 \(Z_2\) ，得

\(\rho = \{ Z_1(\{B, F\}, \{B \rightarrow F\}), S_1(\{E, D\}, \{E \rightarrow D\}),\) \(\quad S_2(\{A, B, E\}, \{AE \rightarrow B\}), Z_3(\{C, D, E\}, \{E \rightarrow CD\}) \}\)

经检验，此时各子模式均满足 \(BCNF\)

令 \(\rho = \{ R(U, F) \}\)

对 \(R\) 中的 \(B \to F\)，\(B\) 不是 \(R\) 的候选码

令 \(U_{S_1} = \{B, F\}\)，\(F_{S_1} = \{B \to F\}\)

\(U_{S_2} = U - F = \{A, B, C, D, E\}\)，\(F_{S_2} = \{AD \to BE, E \to CD\}\)

令 \(\sigma = \{S_1, S_2\}\)，以 \(\sigma\) 代替 \(\rho\) 中的 \(R\) 得

\(\rho = \{ S_1(\{B, F\}, \{B \to F\}), S_2(\{A, B, C, D, E\}, \{AD \to BE, E \to CD\}) \}\)

经计算，\(S_2\) 的候选码为 \(\{A, D\}, \{A, E\}\)

对 \(S_2\) 中的 \(E \to CD\)，\(E\) 不是 \(S_2\) 的候选码

令 \(U_{S_3} = \{C, D, E\}\)，\(F_{S_3} = \{E \to CD\}\)

\(U_{S_4} = S_2 - \{C, D\} = \{A, B, E\}\)

由 \(E \to CD\) 得 \(AE \to ACD \to AD \to BE \to B\)

故 \(F_{S_4} = \{AE \to B\}\)

令 \(\sigma = \{S_3, S_4\}\)，以 \(\sigma\) 代替 \(\rho\) 中的 \(S_2\) 得

\(\rho = \{ S_1(\{B, F\}, \{B \to F\}), S_3(\{C, D, E\}, \{E \to CD\}), S_4(\{A, B, E\}, \{AE \to B\}) \}\)

经检验，此时 \(\rho\) 中各关系模式均属于 \(BCNF\)

故关系 \(R\) 满足 \(BCNF\) 的分解结果为

\(\rho = \{ S_1(\{B, F\}, \{B \to F\}), S_3(\{C, D, E\}, \{E \to CD\}), S_4(\{A, B, E\}, \{AE \to B\}) \}\)

三、有一个学生选课及研究生助教安排关系 R(学号, 课程号, 课程班号, 成绩, 助教学号)，其中：

① 学号、课程号、课程班号、助教学号分别是选课的学生、课程、课程班、研究生助教的码。
② 一门课程可能开设有多个课程班，每一个课程班只能讲授一门课程；一个课程班可以安排多名研究生助教，一名研究生只担任一个课程班的助教。
③ 在一个学生和一门课程之间只能有一条选课记录、一个成绩、以及确定的一名助教；一名助教可以辅助指导多名选课的学生。

1.请写出该关系上的极小函数依赖集。（不需要写过程）

2.该关系最高能够满足到第几范式？请简单说明理由。

经计算，关系 \(R\) 的所有候选码为 {学号, 课程号}，{学号，课程班号}，{学号, 助教学号}

关系 \(R\) 的主属性为 {学号, 课程号, 课程班号, 助教学号}，非主属性为 {成绩}

又 课程班号 \(\rightarrow\) 课程号，课程班号 不是 \(R\) 的候选码，故 \(R\) 中存在对非码的完全函数依赖

故 \(R \notin BCNF\)

检查 \(R\) 中每一个非主属性和每一个候选码之间的函数依赖：

对于候选码 {学号, 课程号}，由 (学号, 课程号) \(\rightarrow\) (成绩, 助教学号) 即 (学号, 课程号) \(\rightarrow\) 成绩

对于候选码 {学号, 课程班号}，由 (学号, 课程班号) \(\rightarrow\) (学号, 课程号)\(\rightarrow\) 成绩

对于候选码 {学号, 助教学号}，由 (学号, 助教学号) \(\rightarrow\) (学号, 课程班号) \(\rightarrow\) 成绩

不存在非主属性对于候选码的传递函数依赖

故关系 \(R\) 最高能够满足到 \(3NF\)

\(3NF\) 的 “传递函数依赖”，是指存在 \(X \rightarrow Y\)，\(Y \rightarrow Z\) 成立，且 \(Y\) 不是 \(R\) 的候选码的函数依赖