Consider the following database schema. The attributes are ABCDEGHKLM (10 in total). The FDs are:

Question

1. ABE -> CK
2. AB -> D
3. C -> BE
4. EG -> DHK
5. D -> L
6. DL -> EK
7. KL -> DM

(a) Compute the attribute closure of EGL with respect to the above set of FDs. Show all
steps.

(b) Compute the minimal cover of the above set of FDs. Show all steps.

(c) Use the 3NF synthesis algorithm to construct a lossless, dependency preserving decomposition of the above schema. Show all steps.

(d) Are all the schemas in the resulting decomposition in BCNF? If yes, then you are done.
If there are schemas that are not in BCNF, decompose them further to achieve BCNF.
Is the resulting decomposition dependency-preserving? Yes/no answers do not count.
Explain everything.

Answer 1

(a) Compute the attribute closure of EGL with respect to the above set of FDs. Show all
steps.
Solution:
EGL
EGLDHK by 4
EGLDHKL by 5
EGLDHKLM by 7

(b) Compute the minimal cover of the above set of FDs. Show all steps.
Solution:
Step 1: Reduce the right-hand sides
1. ABE -> C
2. ABE -> K
3. AB -> D
4. C -> B
5. C -> E
6. EG -> D
7. EG -> H
8. EG -> K
9. D -> L
10. DL -> E
11. DL -> K
12. KL -> D
13. KL -> M
Step 2: Reduce the left-hand sides
Since AB+ includes E, E can be eliminated from 1 and 2.
Similarly, L can be eliminated from 10 and 11. Thus, we obtain
1. AB -> C
2. AB -> K
3. AB -> D
4. C -> B
5. C -> E
6. EG -> D
7. EG -> H
8. EG -> K
9. D -> L
10. D -> E
11. D -> K
12. KL -> D
13. KL -> M
Step 3: Eliminate redundant FDs
FD 2 follows from 3 and 11. Nothing else can be eliminated, so the minimal cover is
FD8 follows from 6 and 11.
1. AB -> C
3. AB -> D
4. C -> B
5. C -> E
6. EG -> D
7. EG -> H
9. D -> L
10. D -> E
11. D -> K
12. KL -> D
13. KL -> M

(c) Use the 3NF synthesis algorithm to construct a lossless, dependency preserving decomposition of the above schema. Show all steps.
Solution:
R1 = (ABCD; fAB -> CDg)
R2 = (CBE; fC -> BEg)
R3 = (EGDH; fEG -> DHg)
R4 = (DLEK; fD -> LEKg)
R5 = (KLDM; fKL -> DMg

(d) Are all the schemas in the resulting decomposition in BCNF? If yes, then you are done.
If there are schemas that are not in BCNF, decompose them further to achieve BCNF.
Is the resulting decomposition dependency-preserving? Yes/no answers do not count.
Explain everything.
Solution:
R1 is not in BCNF due to C -> B: Split into CB and CDA.
R3 is not in BCNF due to D -> E: Split into DE and DHG.
Note: R5 is in BCNF spite D -> KL, because D is a key of R5 along with KL.
The resulting decomposition is not dependency-preserving: The split of R1 looses AB -> CD and the split of R3 looses EG -> DH.