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 |
c1 |
d1 |
| a4 |
b2 |
c1 |
d1 |
a. Find the one single-column key:
b. Find the one two-column key:
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.), so AB->C is one answer here. Your answer to b. gives you two more
of these FDs.
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 superkey -> non-key
attribute.