数据库理论第八章部分作业——基于《数据库系统概念》第七版_数据库系统概念第七版课后答案

8.18

令主属性为至少在一个候选码中出现的属性。令$\alpha ,\beta$为属性集，使得$\alpha \to \beta$成立，令A为不属于$\alpha 或\beta$的属性，并且$\beta \to A$，我们称$A$为传递依赖于$\alpha$（$\alpha$传递函数确定$A$）. 我们可以按照如下方式重新定义3NF： 关系模式R是关于函数依赖集F的3NF的条件为：R中没有非主属性A传递依赖于R的一个码，请证明这个新定义等价于原始定义

反证法：(假定题目定义的3NF不成立推出课本定义3NF不成立)
根据题目传递依赖定义,

当$A为$非主码且满足$A传递依赖\alpha$的时(违背了题目的定义)
我们有
$$\exists \beta \subseteq R,使得\beta \to A,\alpha \to \beta ,A\notin \alpha ,A\notin \beta$$

1. $A\notin \beta ⟺\beta \to A不是平凡的$
2. $\beta \to \alpha 不成立\Rightarrow \beta 不是超码$
3. $A非主码\Rightarrow A不包含于任意候选码中(A⊈候选码)$

接下来推
假定课本定义的3NF不成立推出题目定义3NF不成立
我们根据课本有以下三个条件同时满足

1. $\alpha \to \beta 非平凡$
2. $\alpha 不是R的超码$
3. $存在A\in (\beta -\alpha )\wedge A不包含于任意候选码中$

$$\begin{gathered} 上面三个内容\Rightarrow A不是主键\wedge \alpha \to A \\ 因为：A是主键A就一定会包含于候选码中 \\ 因为：由于(1)(3)，A是\beta 的元素且\alpha \to \beta \end{gathered}$$

假设$c$是一个R的候选码，$\alpha$不是主码(不是超码，所以肯定不是主码)，我们有$c\to \alpha$ ,$\alpha \to c$不成立（c是候选码）；因为A非主码，这种情况下有$A\notin \alpha \wedge A\notin c$(根据(1)(3)得到因为A是$\beta$的元素但不是$\alpha$的，且$\alpha \to \beta$非平凡)，因此A传递依赖c(c是候选码，有$c\to \alpha$.还有$\alpha \to \beta ,A\in \beta$)，违反了题目的定义

综上，题目定义等价于课本定义

8.21

Give a lossless-join decomposition into BCNF of schema R of Exercise 8.1

$$\begin{gathered} A\to BC \\ CD\to E \\ B\to D \\ E\to A \end{gathered}$$
根据函数依赖集，我们依次测试单个多个属性集的闭包可以得到以下候选码
$$A,BC,CD,E$$

过程如下
$$(A{)}^{+}=(ABC{)}^{+}=(ABCD{)}^{+}=ABCDE$$
$$(CD{)}^{+}=(CDE{)}^{+}=(CDEA{)}^{+}=ABCDE$$
$$(E{)}^{+}=ABCDE$$
$$(BC{)}^{+}=ABCDE$$
其他组合不满足要求

$B\to D非平凡$
$B非超码$

若以我们可以把它们分解为
$$\begin{gathered} (A,B,C,E) \\ (B,D) \end{gathered}$$

8.27

Use Armstrong’s axioms to prove the soundness of the decomposition rule.

Armstrong’s公式
$$\begin{gathered} b\subset a\Rightarrow a\to b \\ a\to b\Rightarrow ca\to cb \\ a\to b\wedge b\to c\Rightarrow a\to c \end{gathered}$$

要证明
$$a\to bc\Rightarrow a\to c\wedge a\to b$$

$$\begin{gathered} (1)a\to bc \\ (2)bc\to b(自反率) \\ (3)bc\to c(自反率) \\ (4)a\to c((1)(3)传递律) \\ (5)a\to b((1)(2)传递律) \end{gathered}$$
综上，证毕

8.34

F = { A B → C D , D → C , D E → B , D E H → A B , A C → D C } F=\{AB\rightarrow CD, D\rightarrow C, DE\rightarrow B, DEH\rightarrow AB, AC \rightarrow DC \} F={AB→CD,D→C,DE→B,DEH→AB,AC→DC}

1. 把右边变单元素
   F = { A B → C , A B → D , D → C , D E → B , D E H → A , D E H → B , A C → D , A C → C } F=\{AB\rightarrow C, AB\rightarrow D, D\rightarrow C, DE\rightarrow B, DEH\rightarrow A, DEH\rightarrow B, AC \rightarrow D , AC \rightarrow C\} F={AB→C,AB→D,D→C,DE→B,DEH→A,DEH→B,AC→D,AC→C}
2. 去掉冗余属性
   F = { A B → C , A B → D , D → C , D E → B , D E H → A , D E H → B , A C → D } F=\{AB\rightarrow C, AB\rightarrow D, D\rightarrow C, DE\rightarrow B, DEH\rightarrow A, DEH\rightarrow B, AC \rightarrow D \} F={AB→C,AB→D,D→C,DE→B,DEH→A,DEH→B,AC→D}

• 若(AB->C）冗余，则 $(AB{)}^{+}=ABCD$,包含C，冗余可去
• 若(AB->D）冗余，则 $(AB{)}^{+}=AB$, 不冗余
• D->C显然不冗余
• 若(DE->B）冗余，则 $(DE{)}^{+}=DEC$, 不包含B， 不冗余
• 若(DEH->A）冗余，则 $(DEH{)}^{+}=DEHB$, 不冗余
• 若(DEH->B）冗余，则 $(DEH{)}^{+}=DEHABC$, 包含B， 冗余
• 若(AC->D）冗余，则 $(AC{)}^{+}=AC$, 不冗余

得到如下数据
F = { A B → D , D → C , D E → B , D E H → A , A C → D } F=\{ AB\rightarrow D, D\rightarrow C, DE\rightarrow B, DEH\rightarrow A, AC \rightarrow D \} F={AB→D,D→C,DE→B,DEH→A,AC→D}

处理完右边再处理左边

• $AB\to D$中A冗余的话， $(B{)}^{+}=B$，不冗余
• $AB\to D$中B冗余的话， $(A{)}^{+}=A$,不冗余
• $DE\to B$中D冗余的话， $(E{)}^{+}=E$,不冗余
• $DE\to B$中E冗余的话， $(D{)}^{+}=DC$,不冗余
• $DEH\to A$中D冗余的话， $(EH{)}^{+}=EH$,不冗余

剩余部分同理可得不冗余
得到

3. 最小子查询
   F = { A B → D , D → C , D E → B , D E H → A , A C → D } F=\{ AB\rightarrow D, D\rightarrow C, DE\rightarrow B, DEH\rightarrow A, AC \rightarrow D \} F={AB→D,D→C,DE→B,DEH→A,AC→D}

4. 统计各个元素在依赖关系中的出现情况

   • A：左右均出现
   • B：左右均出现
   • C：左右均出现
   • D：左右均出现
   • E: 只出现左侧
   • G：未出现
   • H：只出现左侧

只出现在左侧或未出现的元素一定为候选码，则求他们的闭包
$$(EHG{)}^{+}=EHG\ne R$$

1. 于是加入一个属性计算
   经测试发现$(DEHG{)}^{+}=DEHGABC=R$ 我们得到DEHG是R的一个候选码，剩下的A,B,C均不行
2. 测试加入两个属性，剩余的ABC两两组合，有$(ABEHG{)}^{+}=ABEHGDC$， $(ACEHG{)}^{+}=ACEHGDB$

综上可行的候选码有
$$\begin{gathered} DEHG \\ ABEHG \\ ACEHG \end{gathered}$$
于是我们在F的最小子查询的基础上进行分解，有
$$\begin{gathered} (A,B,D) \\ (D,C) \\ (D,E,B) \\ (D,E,H,A) \\ (A,C,D) \end{gathered}$$
然后再加上前文算出的所有候选码
$$\begin{gathered} (D,E,H,G) \\ (A,B,E,H,G) \\ (A,C,E,H,G) \end{gathered}$$

最后，观察新组成的分解模式中，是否存在包含关系，有则去掉被包含的，这里$(D,C)\subseteq (A,D,C)$，去掉，而达到无损分解，我们还缺一个候选码，我们只需要取其中一个候选码即可，这里我选了第一个DEHG

$$\begin{gathered} (A,B,D) \\ (D,E,B) \\ (D,E,H,A) \\ (A,C,D) \\ (D,E,H,G) \end{gathered}$$