CS430/630 FDs, Normalization Lab  NAME: ______________
(4 points) 

1. Given the relation T1:

A B C D
a1 b1 c1 d2
a2 b2 c1 d2
a3 b1 c2 d1
a4 b2 c2 d1

a. Find the one single-column key:

b. Find two two-column keys:

c. Find all the FDs consistent with this relation instance that have one attribute on the left hand side and one on the right hand side and are not trivial (A->A is trivial, for example). Your answer to a. gives you 3 such FDs (key -> other-column).



d. Find all FDs that have two attributes on the left hand side and one on the right and are not trivial. For example, AB -> A is trivial, but AB->C is not trivial even though it is implied by A->C (from part c.). Your answer to b. gives you several of these.



2. Suppose a company has an employees relation as follows, showing the department and parking lot number for each employee. You can use E N D L for attribute names to save writing.

eid name department lot
123 Attishoo 3 10
201 Smiley 4 12
202 Smiley 3 10
222 Guldu 5 10
333 Madayan 4 12

a. Find the nontrivial FDs with a single attribute on each side consistent with this relation instance.




b. Find the single-attribute key for this relation instance. Can you also find a two-attribute key?



eid name department lot
123 Attishoo 3 10
201 Smiley 4 12
202 Smiley 3 10
222 Guldu 5 10
333 Madayan 4 12

c. Explain the redundancy found in this table (what data is repeated).



d. Propose a decomposition that removes the redundancy.



e. Prove that your decomposition is lossless. Use the Lossless Decomposition Theorem that says for losslessness, the attributes common to the two tables (the join attributes) must be a superkey of one or other of the tables.





3.  Given the FDs for a relation R:
(1) A -> B,  (2) C-> A, (3) D -> AC

Here is an example attribute closure computation as a model
Compute A+:
A+ = A    (look for A in LHS's, add RHS: find A->B, add B)
A+ = AB by (1)
(No more FDs have A or B or both on left hand side, so done. --not necessary to write this)

a. Compute C+


b. Find a single-attribute key for R (compute K+ to prove your key K)




c. Is R in BCNF?  If not, determine the FDs (in the numbered list) that violate BCNF, that is, FDs that are not of the form key -> non-key attribute.