20231111.md

# HW 4
## 7.1
As is shown in the following table :
| Dependencies | A | B | C | D | E |
| -------------- | ----- | -------- | -------- | -------- | -------- |
| $R_1(A, B, C)$ | $a_1$ | $a_2$ | $a_3$ | $b_{14}$ | $b_{15}$ |
| $R_2(A, D, E)$ | $a_1$ | $b_{22}$ | $b_{23}$ | $a_4$ | $a_5$ |
modify table content according to stated dependencies :
| Dependencies | A | B | C | D | E |
| -------------- | ----- | ----- | ----- | ----- | ----- |
| $R_1(A, B, C)$ | $a_1$ | $a_2$ | $a_3$ | $a_4$ | $a_5$ |
| $R_2(A, D, E)$ | $a_1$ | $a_2$ | $a_3$ | $a_4$ | $a_5$ |
both rows are filled with all-a items which proves the decomposition $(A, B, C), (A, D, E)$ is lossless ($A$ is a candidate key)
## 7.6
Since $A \rarr BC$ , conclude : $A \rarr B$ and $A \rarr C$
Since $A \rarr B$ and $B \rarr D$, $A \rarr D$
Since $A \rarr CD$ and $CD\rarr E, A \rarr E$
Since $A \rarr A$, we have $A \rarr ABCDE$
Since $E \rarr A$, $E \rarr ABCDE$
Since $B \rarr D$ and $BC \rarr CD$ , $BC \rarr ABCDE$
Also, we have $C \rarr C$, $D \rarr D$, $BD \rarr D$, etc.
Therefore, functional dependency with $A, E, BC$ or $CD$ on the left-hand side of the arrow is in $F^+$
Then $F^+$ is $BD \rarr B, BD \rarr D, C \rarr C, D \rarr D, BD \rarr BD, B \rarr D, B \rarr B, B \rarr BD$ and all functional dependencies which contains $A, E, BC$ or $CD$ on the left side (Let $*$ represent any set of attributes in $R$, then dependencies could be formulated as : $A* \rarr \alpha, BC* \rarr \alpha, CD* \rarr \alpha, E* \rarr \alpha$ where $\alpha$ is any subset of $\{A, B, C, D, E\}$).
The candidate keys are $A, BC, CD ,E$
## 7.27
**Decomposition Rule Statement:** If $\alpha \rarr \beta\gamma$ holds , then $\alpha \rarr \beta$ holds and $\alpha \rarr \gamma$ holds.
**Proof:**
Suppose $\alpha \rarr\beta\gamma$ holds.
According to Reflexivity rule, $\beta\gamma \rarr \beta$ and $\beta\gamma \rarr \gamma$ holds
According to Transivity rule, $\alpha \rarr \beta$ holds and $\alpha \rarr \gamma$ holds.
## 7.30
### a.
initialize $X_0 = \{B\}$
Since $B \rarr D$ , $X_1 = \{B, D\}$
Since $D \rarr A, X_2 = \{A, B, D\}$
Since $A \rarr BCD$, $X_3 = \{A, B, C, D\}$
Since $BC \rarr DE, X_4 = \{A, B, C ,D, E\}$
Therefore, $B^+ = \{A, B, C, D, E\}$
### b.
Given $A \rarr BCD$
By Decomposition rule, $A \rarr BC$ holds.
Given $BC \rarr DE$
By Transitivity rule, $A \rarr DE$ holds.
By Union rule $A \rarr BCDE$ holds.
Apparently, $A \rarr A$ holds (self determination rule)
By Union rule, $A \rarr ABCDE$ holds.
By Augmentation rule, $AG \rarr ABCDEG$ holds.
This provces that $AG$ is a superkey.
### c.

1. spilt dependencey so that the right-hand side contains only one element
$G_0 = \{A \rarr B, A \rarr C, A \rarr D,BC \rarr D, BC \rarr E, B \rarr D, D\rarr A\}$
2. for left-hand items which contain more than 1 element:
$(B)^+_{G_0} = \{A, B, C, D\}, (C)^+ = \{C\}$
where $D \in (B)^+$ .
Therefore, $G_0$ could be updated as :
$G_1 = \{ A \rarr B, A \rarr C, A \rarr D, B \rarr D, BC \rarr E, D \rarr A\}$
3. check out remaining depedency for whether they are redundant or not
for $A \rarr B$, $B \not\in(A)^+_{G_1 - (A \rarr B)} = \{A, C, D\}$
for $A \rarr C$, $C \not\in (A)^+_{G_1 - (A \rarr C)} = \{A, B, D\}$
for $A \rarr D$, $D \in (A)^+_{A \rarr D} = \{A, B, C, D, E\}$ so $A \rarr D$ is redundant
Therefore, $G$ could be updated as : $G_2 = \{ A \rarr B, A \rarr C, B \rarr D, BC \rarr E, D \rarr A\}$
for $B \rarr D$ , $D \not\in (B)^+_{G_1 - (B \rarr D)} = \{B\}$
for $BC \rarr E$, $E \not\in (BC)^+_{G_1 - (BC \rarr E)} = \{A, B, C, D\}$
for $D \rarr A$, $A \not\in (D)^+_{G_1 - (D \rarr A)} = \{ D \}$
According to Union rule, $G_2 = \{A \rarr BC, B \rarr D, BC \rarr E, D \rarr A\}$
Thus the canonical cover for $F$ is $G = \{A \rarr BC, B \rarr D, BC \rarr E, D \rarr A\}$
### d.
1. The canonical cover for $F$ is $G = \{A \rarr BC, B \rarr D, BC \rarr E, D \rarr A\}$
2. The candidate keys:
1. no LHSA or NONA
2. candidate keys : $\{AB, AC, AD, BC, BD, CD\}$
3. The 3NF decomposition is $\{\{A,B,C\}, \{B,C,E\}, \{B,D\}, \{D,A\}, \{C, D\}\}$