(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.