8.18
令主属性为至少在一个候选码中出现的属性。令 α , β \alpha,\beta α,β为属性集，使得 α → β \alpha\rightarrow\beta α→β成立，令A为不属于 α 或 β \alpha或\beta α或β的属性，并且 β → A \beta\rightarrow A β→A，我们称 A A A为传递依赖于 α \alpha α（ α \alpha α传递函数确定 A A A）. 我们可以按照如下方式重新定义3NF： 关系模式R是关于函数依赖集F的3NF的条件为：R中没有非主属性A传递依赖于R的一个码，请证明这个新定义等价于原始定义
反证法：(假定题目定义的3NF不成立推出课本定义3NF不成立)
根据题目传递依赖定义,
当 A 为 A为 A为非主码且满足 A 传递依赖 α A传递依赖\alpha A传递依赖α的时(违背了题目的定义)
我们有
∃ β ⊆ R , 使得 β → A , α → β , A ∉ α , A ∉ β \exists \beta \sube R, 使得 \beta\rightarrow A,\alpha\rightarrow \beta,A\notin\alpha,A\notin\beta ∃β⊆R,使得β→A,α→β,A∈/α,A∈/β
A ∉ β ⟺ β → A 不是平凡的 A\notin \beta \iff \beta\rightarrow A不是平凡的 A∈/β⟺β→A不是平凡的 β → α 不成立 ⇒ β 不是超码 \beta\rightarrow \alpha不成立\Rightarrow \beta不是超码 β→α不成立⇒β不是超码 A 非主码 ⇒ A 不包含于任意候选码中 ( A ⊈ 候选码 ) A非主码\Rightarrow A不包含于任意候选码中(A\not\sube 候选码) A非主码⇒A不包含于任意候选码中(A⊆候选码)
接下来推
假定课本定义的3NF不成立推出题目定义3NF不成立
我们根据课本有以下三个条件同时满足
α → β 非平凡 \alpha\rightarrow \beta 非平凡 α→β非平凡 α 不是 R 的超码 \alpha 不是R的超码 α不是R的超码 存在 A ∈ ( β − α ) ∧ A 不包含于任意候选码中 存在A \in (\beta - \alpha)\land A不包含于任意候选码中 存在A∈(β−α)∧A不包含于任意候选码中
上面三个内容 ⇒ A 不是主键 ∧ α → A 因为： A 是主键 A 就一定会包含于候选码中 因为：由于 ( 1 ) ( 3 ) ， A 是 β 的元素且 α → β 上面三个内容\Rightarrow A不是主键\land\alpha \rightarrow A\\ 因为：A是主键A就一定会包含于候选码中\\ 因为：由于(1)(3)，A是\beta的元素且\alpha \rightarrow\beta 上面三个内容⇒A不是主键∧α→A因为：A是主键A就一定会包含于候选码中因为：由于(1)(3)，A是β的元素且α→β
假设 c c c是一个R的候选码， α \alpha α不是主码(不是超码，所以肯定不是主码)，我们有 c → α c\rightarrow\alpha c→α , α → c \alpha\rightarrow c α→c不成立（c是候选码）；因为A非主码，这种情况下有 A ∉ α ∧ A ∉ c A\notin\alpha\land A\notin c A∈/α∧A∈/c(根据(1)(3)得到因为A是 β \beta β的元素但不是 α \alpha α的，且 α → β \alpha\rightarrow\beta α→β非平凡)，因此A传递依赖c(c是候选码，有 c → α c\rightarrow \alpha c→α.还有 α → β , A ∈ β \alpha\rightarrow \beta, A\in \beta α→β,A∈β)，违反了题目的定义
综上，题目定义等价于课本定义
8.21
Give a lossless-join decomposition into BCNF of schema R of Exercise 8.1
A → B C C D → E B → D E → A A → BC\\ CD → E\\ B → D\\ E → A A→BCCD→EB→DE→A
根据函数依赖集，我们依次测试单个多个属性集的闭包可以得到以下候选码
A , B C , C D , E A, BC, CD, E A,BC,CD,E
过程如下
( A ) + = ( A B C ) + = ( A B C D ) + = A B C D E (A)^+ = (ABC)^+=(ABCD)^+ = ABCDE (A)+=(ABC)+=(ABCD)+=ABCDE
( C D ) + = ( C D E ) + = ( C D E A ) + = A B C D E (CD)^+ = (CDE)^+=(CDEA)^+=ABCDE (CD)+=(CDE)+=(CDEA)+=ABCDE
( E ) + = A B C D E (E)^+ = ABCDE (E)+=ABCDE
( B C ) + = A B C D E (BC)^+ = ABCDE (BC)+=ABCDE
其他组合不满足要求
B → D 非平凡 B\rightarrow D非平凡 B→D非平凡
B 非超码 B非超码 B非超码
若以我们可以把它们分解为
( A , B , C , E ) ( B , D ) (A,B,C,E)\\(B,D) (A,B,C,E)(B,D)
8.27
Use Armstrong’s axioms to prove the soundness of the decomposition rule.
Armstrong’s公式
b ⊂ a ⇒ a → b a → b ⇒ c a → c b a → b ∧ b → c ⇒ a → c b\sub a\Rightarrow a\rightarrow b\\ a\rightarrow b\Rightarrow ca\rightarrow cb\\ a\rightarrow b\land b\rightarrow c\Rightarrow a\rightarrow c b⊂a⇒a→ba→b⇒ca→cba→b∧b→c⇒a→c
要证明
a → b c ⇒ a → c ∧ a → b a\rightarrow bc\Rightarrow a\rightarrow c \land a\rightarrow b a→bc⇒a→c∧a→b
( 1 ) a → b c ( 2 ) b c → b ( 自反率 ) ( 3 ) b c → c ( 自反率 ) ( 4 ) a → c ( ( 1 ) ( 3 ) 传递律 ) ( 5 ) a → b ( ( 1 ) ( 2 ) 传递律 ) (1) a\rightarrow bc\\ (2) bc\rightarrow b (自反率)\\ (3) bc\rightarrow c (自反率)\\ (4) a\rightarrow c ((1)(3)传递律) \\ (5) a\rightarrow b ((1)(2)传递律) (1)a→bc(2)bc→b(自反率)(3)bc→c(自反率)(4)a→c((1)(3)传递律)(5)a→b((1)(2)传递律)
综上，证毕
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}
把右边变单元素
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}去掉冗余属性
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）冗余，则 ( A B ) + = A B C D (AB)^+ = ABCD (AB)+=ABCD,包含C，冗余可去若(AB->D）冗余，则 ( A B ) + = A B (AB)^+ = AB (AB)+=AB, 不冗余D->C显然不冗余若(DE->B）冗余，则 ( D E ) + = D E C (DE)^+ = DEC (DE)+=DEC, 不包含B， 不冗余若(DEH->A）冗余，则 ( D E H ) + = D E H B (DEH)^+ = DEHB (DEH)+=DEHB, 不冗余若(DEH->B）冗余，则 ( D E H ) + = D E H A B C (DEH)^+ = DEHABC (DEH)+=DEHABC, 包含B， 冗余若(AC->D）冗余，则 ( A C ) + = A C (AC)^+ = AC (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}
处理完右边再处理左边
A B → D AB\rightarrow D AB→D中A冗余的话， ( B ) + = B (B)^+=B (B)+=B，不冗余 A B → D AB\rightarrow D AB→D中B冗余的话， ( A ) + = A (A)^+=A (A)+=A,不冗余 D E → B DE\rightarrow B DE→B中D冗余的话， ( E ) + = E (E)^+=E (E)+=E,不冗余 D E → B DE\rightarrow B DE→B中E冗余的话， ( D ) + = D C (D)^+=DC (D)+=DC,不冗余 D E H → A DEH\rightarrow A DEH→A中D冗余的话， ( E H ) + = E H (EH)^+=EH (EH)+=EH,不冗余
剩余部分同理可得不冗余
得到
最小子查询
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}
统计各个元素在依赖关系中的出现情况
A：左右均出现B：左右均出现C：左右均出现D：左右均出现E: 只出现左侧G：未出现H：只出现左侧
只出现在左侧或未出现的元素一定为候选码，则求他们的闭包
( E H G ) + = E H G ≠ R (EHG)^+=EHG\not=R (EHG)+=EHG=R
于是加入一个属性计算
经测试发现 ( D E H G ) + = D E H G A B C = R (DEHG)^+=DEHGABC = R (DEHG)+=DEHGABC=R 我们得到DEHG是R的一个候选码，剩下的A,B,C均不行测试加入两个属性，剩余的ABC两两组合，有 ( A B E H G ) + = A B E H G D C (ABEHG)^+=ABEHGDC (ABEHG)+=ABEHGDC， ( A C E H G ) + = A C E H G D B (ACEHG)^+=ACEHGDB (ACEHG)+=ACEHGDB
综上可行的候选码有
D E H G A B E H G A C E H G DEHG\\ ABEHG\\ACEHG DEHGABEHGACEHG
于是我们在F的最小子查询的基础上进行分解，有
( A , B , D ) ( D , C ) ( D , E , B ) ( D , E , H , A ) ( A , C , D ) (A,B,D)\\ (D,C)\\ (D,E,B)\\ (D,E,H,A)\\(A,C,D) (A,B,D)(D,C)(D,E,B)(D,E,H,A)(A,C,D)
然后再加上前文算出的所有候选码
( D , E , H , G ) ( A , B , E , H , G ) ( A , C , E , H , G ) (D,E,H,G)\\(A,B,E,H,G)\\(A,C,E,H,G) (D,E,H,G)(A,B,E,H,G)(A,C,E,H,G)
最后，观察新组成的分解模式中，是否存在包含关系，有则去掉被包含的，这里 ( D , C ) ⊆ ( A , D , C ) (D,C)\sube(A,D,C) (D,C)⊆(A,D,C)，去掉，而达到无损分解，我们还缺一个候选码，我们只需要取其中一个候选码即可，这里我选了第一个DEHG
( A , B , D ) ( D , E , B ) ( D , E , H , A ) ( A , C , D ) ( D , E , H , G ) (A,B,D)\\ (D,E,B)\\ (D,E,H,A)\\(A,C,D)\\(D,E,H,G) (A,B,D)(D,E,B)(D,E,H,A)(A,C,D)(D,E,H,G)
