Loading... # Ex. 常见大题解题步骤 ## Ex.0 闭包 ### Ex.0.1 概念 设 $X$ 和 $Y$ 均为关系 $R$ 的属性集的子集, $F$ 是 $R$ 上的函数依赖集，若对 $R$ 的任一属性集 $B$, 一旦 $X \to B$，必有 $B \subseteq Y$，且对 $R$ 的任一满足以上条件的属性集 $Y_1$ ，必有 $Y \subseteq Y_1$，此时称 $Y$ 为属性集 $X$ 在函数依赖集 $F$ 下的闭包，记作 $X^+$ ### Ex.0.2 计算步骤 > 设有关系 $R<U,F>$, 计算关系 $R$ 的属性集 $X$ 的闭包. 1. 设最终将成为闭包的属性集是 $Y$，把 $Y$ 初始化为 $X$ 2. 检查F中的每一个函数依赖 $A \to B$, 如果属性集 $A$ 中所有属性均在 $Y$ 中, 而 $B$ 中有的属性不在 $Y$ 中，则将其加入到 $Y$ 中 3. 重复第二步，直到没有属性可以添加到属性集 $Y$ 中为止。 最后得到的 $Y$ 就是 $X^+$ ### Ex.0.3 例题 > 设有关系 $R<U,F>$ > 其中 $U = \{A, B, C, D, E, I\}$ > $F=\{A \to D, AB \to E, BI \to E, CD \to I, E→C\}$, 计算 $(AE)^+$ 1. 令 $X=\{AE\}$, $X_0=AE$ 2. 在 $F$ 中寻找尚未使用过且左边是 $AE$ 的子集的函数依赖: $A \to D$, $E \to C$. 则 $X_1=X_0 \cap CD = ACDE$. 此时 $X_1 \neq X_2$ 3. 在 $F$ 中寻找尚未使用过且左边是 $ACDE$ 的子集的函数依赖: $CD \to I$. 则 $X_2=X_1 \cap I= ACDEI$. 此时 $X_2 \neq X_1$. 4. $F$ 中所有依赖都被使用过. 算法结束, $(AE)^+_F=ACDEI$ ## Ex.1 最小依赖集 ### Ex.1.1 计算步骤 1. 用分解的法则, 使F中的任何一个函数依赖的右部仅含有一个属性 2. 去掉多余的函数依赖: 依次检查函数依赖 $X \to Y$, 开始将其从 $F$ 中去掉. 然后在剩下的函数依赖中求 $X$ 的闭包 $X^+_F$, 看 $X^+_F$ 是否包含 $Y$, 若是则去掉$X \to Y$, 否则不能去掉, 直到找不到冗余的函数依赖. 3. 去掉各依赖左部多余的属性, 一个个地检查函数依赖左部非单个属性的依赖. 例如 $XY \to A$，若要判 $Y$ 为多余的，则以 $X \to A$ 代替 $XY \to A$ 是否等价: 若$A \in X^+_F$，则 $Y$ 是多余属性，可以去掉。 ### Ex.1.2 例题 > 设有关系 $R<U,F>$ > 其中 $U = \{A, B, C, D, E, G\}$ > $F=\{AB \to C, D \to EG, C \to A, BE \to C, BC \to D, CG \to BD, ACD \to B, CE \to AG\}$, 计算 $F$ 的最小函数依赖集。 1. 利用分解规则, 将所有的函数依赖变成右边都是单个属性的函数依赖, $$ F=\{AB \to C,D \to E,D \to G,C \to A,BE \to C,BC \to D,CG \to B,CG \to D,ACD \to B,CE \to A,CE \to G\} $$ 2. 去掉 $F$ 中多余的函数依赖 - 设 $AB \to C$ 为冗余的函数依赖，则去掉 $AB \to C$, 得 $$ F_1=\{D \to E,D \to G,C \to A,BE \to C,BC \to D,CG \to B,CG \to D,ACD \to B,CE \to A,CE \to G\} $$ $$ (AB)_{F_1}^+ = AB, C \not\in (AB)_{F_1}^+ $$ , 故 $AB \to C$ 不是冗余的函数依赖, 不能从 $F_1$ 中去掉 - 设 $CG \to B$ 为冗余的函数依赖，则去掉 $CG \to B$, 得 $$ F_2=\{D \to E,D \to G,C \to A,BE \to C,BC \to D,AB \to C,CG \to D,ACD \to B,CE \to A,CE \to G\} $$ $$ (CG)_{F_2}^+ = ABCDEG, B \in (CG)_{F_2}^+ $$ , 故 $CG \to B$ 是冗余的函数依赖, 从 $F_2$ 中去掉 - 设 $CG \to D$ 为冗余的函数依赖，则去掉 $CG \to D$, 得 $$ F_3=\{AB \to C,D \to E,D \to G,C \to A,BE \to C,BC \to D,ACD \to B,CE \to A,CE \to G\} $$ $$ (CG)_{F_3}^+ = ACG, D \not\in (CG)_{F_3}^+ $$ , 故 $CG \to D$ 不是冗余的函数依赖, 不能从 $F_2$ 中去掉 - $\cdots$ - 设 $CE \to A$ 为冗余的函数依赖，则去掉 $CE \to A$, 得 $$ F_4=\{AB \to C, D \to E, D \to G, C \to A, BE \to C, BC \to D, CG \to D, ACD \to B, CE \to G\} $$ $$ (CE)_{F_4}^+ = ABCDEG, A \in (CE)_{F_4}^+ $$ , 故 $CE \to A$ 是冗余的函数依赖, 从 $F_4$ 中去掉 3. 去掉 $F_4$ 中各函数依赖左边多余的属性(只检查左部不是单个属性的函数依赖), 由于 $C \to A$, $ACD \to B$ 中, 属性 $A$ 是多余的, 去掉 $A$ 得 $CD \to B$ 4. $F=\{AB \to C,D \to E,D \to G,C \to A,BE \to C,BC \to D,CG \to D,CD \to B,CE \to G\}$ ## Ex.2 候选码 ### Ex.2.1 计算步骤 > 设有关系 $R<U,F>$ 1. 求 $F$ 的最小函数依赖集, 并令其为 $F$ 2. 判断 $U$ 中所有属性属于哪一类 - L类: 所有依赖关系中仅出现在函数依赖左部的属性 - R类: 所有依赖关系中仅出现在函数依赖右部的属性 - LR类: 所有依赖关系中即出现在函数依赖左部又出现在函数依赖右部的属性 - N类: 所有依赖关系中没有出现的属性 3. 设$P = L \cup N$, $Q = LR$ 4. 计算 $P$ 的闭包, 若 $P^+_F = U$, 则 $P$ 为 $R$ 的唯一的候选码. 算法结束. 5. 将 $P$ 依次与 $Q$ 中的属性组合, 求闭包判断该组合属性是否是候选码(不止一个); 找出所有的候选码后,算法结束. ### Ex.2.2 例题 > 设有关系 $R<U,F>$ > $U = \{A, B, C, D, E\}$ > $F=\{A \to C, C \to A, B \to AC, D \to AC\}$, 求候选码 1. $F$ 已经为最小依赖集 2. $L = \{B, D\}$, $N = \{E\}$, $LR = \{A, C\}$ 3. $P = \{B, D, E\}$, $Q = \{E\}$ 4. $(BDE)_F^+=ABCDE=U$, 所以 $BDE$ 为 **唯一候选码** > 设有关系 $R<U,F>$ > $U = \{A, B, C, D, E, G\}$ > $F=\{AB \to C, CD \to E, E \to A, A \to G\}$, 求候选码 1. $F$ 已经为最小依赖集 2. $L = \{B, D\}$, $N = \varnothing$, $LR = \{A, C, E\}$ 3. $P = \{B, D\}$, $Q = \{A, C, E\}$ 4. $(BD)_F^+ = BD \neq U$ 5. 将 $BD$, 依次与 $A, C, E$ 进行组合并计算闭包 - $(ABD)_F^+ = ABDCEG = U$ - $(BCD)_F^+ = ABDCEG = U$ - $(BDE)_F^+ = ABDCEG = U$ 6. 所以 $ABD$, $BCD$, $BDE$ 为 **候选码** ## Ex.3 3NF分解 ### Ex.3.1 计算步骤 > 设有关系 $R<U,F>$ 1. 先求出 $F$ 的最小依赖集 2. 没有不出现在两侧的元素单独分出一个子集, 再将各依赖分别划分为子集 3. 求解候选码, 并作为子集 ### Ex.3.2 例题 > 设有关系 $R<U,F>$ > $U = \{A, B, C, D, E, G\}$ > $F=\{B \to G,CE \to B,C \to A,CE \to G,B \to D,C \to D\}$, 求候选码 1. 求得 $FF$ 最小依赖集 $F_m=\{B \to G, CE \to B, C \to A, B \to D, C \to D\}F_m=\{B \to G, CE \to B, C \to A, B \to D, C \to D\}$ 2. 将各依赖分别划分为子集得 $\{BG\}\{BG\}$, $\{CEB\}\{CEB\}$, $\{CA\}\{CA\}$, $\{BD\}\{BD\}$, $\{CD\}\{CD\}$ 3. 解得候选码为 $\{ACE\}\{ACE\}$. 4. 3NF分解为$\{BG\}\{BG\}$, $\{CEB\}\{CEB\}$, $\{CA\}\{CA\}$, $\{BD\}\{BD\}$, $\{CD\}\{CD\}$, $\{ACE\}\{ACE\}$. 最后修改：2020 年 11 月 01 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏