# Problem 1
1. Not satisfied, because of the instances (A,B,C)=(6,2, 3) and (A,B,C)=(6,2, 5)
2. Satisfied
3. Not satisfied, because of the instances (C, A)=(3, 1) and (C, A)=(3, 6)
4. Not satisfied, because of the instances (B,C,A)=(2, 3, 1) and (B,C,A)=(2, 3, 6)
5. Satisfied
6. Not satisfied. because of the instances (6,2,5) and (6,2,3).
# Problem2
1. B->A
B->C
A->C
2. | A | B | C |
| :–: | :–: | :–: |
| 2 | 1 | 3 |
| 5 | 4 | 6 |
| 8 | 7 | 9 |
3.
| A | B | C |
| —- | —- | —- |
| 2 | 1 | 3 |
| 2 | 3 | 3 |
| 5 | 4 | 6 |
4.Not . Because F={B->A, A->C} implies AB->C. We can prove this using the definition of functional dependency. Assuming there are two instances of R(A,B,C), and they share the same A,B, then they share the same A. But according to the functional dependency of A->C, they share the same C. So AB->C also holds.
# Problem 3
Yes, they are equivalent.
First, we prove G is a subset of F: B->AE can be derived from B->CE and B->A.
Second, we prove F is a subset of G:
B->AE, E->CD can derive B->CE.
E->CD implys E->D
B->AE implys B->A
# Problem 4
Not. Because of the FD A->DE. And closeure set of A is {A, D, E}, so A is not super-key.
# Problem 5
1. A+ = B+= C+ = D+ =E+ = {A,B,C,D,E}. So A,B,C,D,E are all super-keys. So according to the definition of BCNF, this relation is in BCNF.
2. Yes, it is lossless. Because A,B,C,D,E are all super-keys, after joining process, no new instances will be generated. Then we can recover R.
3. {C->D, C->E, D->E, D->C, E->C, E->D}
4. {A->B, A->D, B->A, B->D, D->A, D->B}
5. F1 union F2 logically imply F.
# Problem 6
1. AB, ACE, AEF
2. Not, FD AC->F, in which AC is not super key.
3. Apply algorithm for R:
R1={A,C,F}, R2={A,B,C,D,E}
F1={AC->F }. F2 ={B->D, AB->C, AB->E, ACE->B, ACE->D}
R2 is not in BCNF, apply algorithm for R2 again because of FD B->D:
R3={B,D}, F3={B->D}.
R4={A,B,C,E}, F4={AB->C, AB->E, ACE->B}.
In the end, we decompose R into R1={A,C,F},R3={B,D},R4={A,B,C,E}.