CS430/630 FDs, Normalization Lab  NAME: ______________
(3 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 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)



b. 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 a.).



2. Suppose a company has an employees relation as follows, showing the department and parking lot number for each employee

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

a. Find the nontrivial FDs consistent with this relation instance.



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




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.