Consider the following database schema. The attributes are ABCDEF. The FDs are:

ABF -> C
CF -> B
CD -> A
BD -> AE
C -> F
B -> F

(a) Compute the attribute closure of ABD 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? Explain all steps: yes/no answers
do not count.

(a) What is a functional dependency?
(b) Explain why a primary key constraint is an example of a functional dependency.
(c) State the conditions (in terms of functional dependencies) for a relation to be in 3rd
normal form and in BCNF.
(d) Consider a relation in a library system with the following attributes: author (A), title (T),
copy number (C), author's year of birth (B), shelf (Sh), subject (Sub). If the library has
multiple copies of a particular book they are numbered consecutively with (unique) copy
numbers. Shelf is the location of a particular book and all the books on a shelf are in the
same subject category. What are the functional dependencies? Decompose the relation
into two or more relations to eliminate redundant storage of information. In what normal
form are the relations that result from your decomposition?

(a) Compute the attribute closure of ABD with respect to the above set of FDs. Show all
steps.
Solution:
Using the attribute closure algorithm:
ABD
ABDE by BD->E
ABDEF by B->F
ABDEFC by ABF->C

(b) Compute the minimal cover of the above set of FDs. Show all steps.
Solution:
Step 1: Replace BD -> AE with BD -> A and BD -> E.
Step 2: ABF -> C can be replaced with: AB -> C while CF -> B can be replaced with:
C -> B. This is because AB -> C is entailed by ABF -> C and C -> F, and C -> B is
entailed by CF -> B and C -> F.
So, after steps 1 and 2 in the minimal cover algorithm, we have the following FDs:
AB -> C
C -> B
CD -> A
BD -> A
BD -> E
C -> F
B -> F
Step 3: Eliminate redundant FDs:
C -> F is entailed by C -> B and B -> F, while
CD -> A is entailed by C -> B and BD -> A. Therefore, the minimal cover is
AB -> C
C -> B
BD -> A
BD -> E
B -> F

(b) Compute the minimal cover of the above set of FDs. Show all steps.
Solution:
Step 1: Replace BD -> AE with BD -> A and BD -> E.
Step 2: ABF -> C can be replaced with: AB -> C while CF -> B can be replaced with:
C -> B. This is because AB -> C is entailed by ABF -> C and C -> F, and C -> B is
entailed by CF -> B and C -> F.
So, after steps 1 and 2 in the minimal cover algorithm, we have the following FDs:
AB -> C
C -> B
CD -> A
BD -> A
BD -> E
C -> F
B -> F
Step 3: Eliminate redundant FDs:
C -> F is entailed by C -> B and B -> F, while
CD -> A is entailed by C -> B and BD -> A. Therefore, the minimal cover is
AB -> C
C -> B
BD -> A
BD -> E
B -> F

(c) Use the 3NF synthesis algorithm to construct a lossless, dependency preserving decomposition of the above schema. Show all steps.
Solution:
The 3NF decomposition that corresponds to this minimal cover is
R1 = (ABC; fAB -> Cg)
R2 = (CB; fC -> Bg)
R3 = (BDAE; fBD -> A; BD -> Eg)
R4 = (BF; fB -> Fg)
Test for losslessness:
BDAE is a superkey, since BDAE+ = BDAEFC. Therefore, the above decomposition is
lossless.
(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? Explain all steps: yes/no answers
do not count.
Solution:
The schema R1 = (ABC; fAB -> Cg) is not in BCNF because C -> B is entailed by the
original set of FDs. Since C+ = CBF, C is not a superkey of R1, it follows that C -> B
violates the BCNF condition for R1. The BCNF decomposition (which uses C -> B) is
R11 = (CB; fC -> Bg)
R12 = (CA; fg)
This decomposition is not dependency preserving, since the dependency AB -> C no
longer has a home schema and it does not follow from the dependencies associated with
R11, R12, R2, R3, R4.

(a) What is a functional dependency?
(b) Explain why a primary key constraint is an example of a functional dependency.
Solution
The value of the primary key determines the values of all other attributes.
(c) State the conditions (in terms of functional dependencies) for a relation to be in 3rd
normal form and in BCNF.
(d) Consider a relation in a library system with the following attributes: author (A), title (T),
copy number (C), author's year of birth (B), shelf (Sh), subject (Sub). If the library has
multiple copies of a particular book they are numbered consecutively with (unique) copy
numbers. Shelf is the location of a particular book and all the books on a shelf are in the
same subject category. What are the functional dependencies? Decompose the relation
into two or more relations to eliminate redundant storage of information. In what normal
form are the relations that result from your decomposition?
Solution:
The functional dependencies are:
A T C -> B Sh Sub
A -> B
Sh -> Sub
The relation can be decomposed into the following three relations:
(A T C Sh) with FD ATC -> Sh
(A B) with FD A -> B
(Sh Sub) with FD Sh -> Sub