CSE 444 Homework 2

Objectives:

To be able to translate from E/R diagrams to a relational database, to understand functional dependencies, Boyce-Codd Normal Form, and Third Normal Form.

Reading Assignments:

3.1,(3.2 recommended), 3.3-3.7.7

Number of points:

100

Due date:

October 20

Assignment Tools

1. [10 points]
   1. Create a relational schema that captures this E/R diagram.
   2. Which relation in your relational schema represents the relationship "History," in the E/R diagram and why is that your representation?
   3. What is your representation of the entity "Ship_Movement", and why?
   4. What are the keys for each relation in your relational schema?
2. [10 points] Consider a relation with the schema V(A,B,C,D) and functional dependencies AB -> C, BC -> D, A-> D, B-> A.
   1. What are all the nontrivial functional dependencies that follow from the given dependencies?
   2. What are all of the keys of V?
3. [5 points] Consider the relation W(A,B,C,D,E) with the following dependencies: AB->C, CD->E, DE->B. Is AB a key of W? If not, is ABD? Justify your answer.
4. [25 points] For each of the following, show whether or not it's a valid entailment. If it is valid, show show how the entailment follows by using the algorithm from class. If the rule is not valid, give example relations and tuples that satisfy the if clause but not the then clause.
   1. If w->y, x-> z, then wx -> y
   2. If xy->z, y->w, then wx -> z
   3. If x->z, y->z, then x->y
   4. If x->y, z->w, then xz ->wy
   5. If xy->z, z->w, then x-> w
5. [16 points] For the following relations and functional dependencies
   1. Decompose the relations, as necessary, into collections of relations that are in BCNF. Show all of your work and explain which dependency violations you are correcting by your decompositions.
   2. Decompose the relations into a collection that follows 3NF instead.
   The relations:
   1. R(A,B,C,D,E) with functional dependencies AC->D, B->E.
   2. S(A,B,C,D,E) with functional dependencies A->B, BC->E, DE-> A.
6. [4 points] Why do we prefer 3NF to BCNF?
7. [25 points] (This is Exercise 3.6.8 from the book)
   We say a set of attributes X is closed (with respect to a given set of functional dependencies) if X⁺=X. Given the closed attribute sets, this gives us some information on the underlying functional dependencies.

   Consider a relation with schema R(A,B,C,D) and an unknown set of functional dependencies. For each closed attribute set below, give a set of functional dependencies that is consistent with it.

   1. All sets attributes are closed.
   2. The only closed sets are {} and {A,B,C,D}.
   3. The only closed sets are {}, {A,B}, and {A,B,C,D}.
8. [5 points] Please answer the following questions
   1. How long did it take you to complete this assignment?
   2. What did you like the best about this assignment?
   3. What did you like the least about this assignment?
   4. What helped you learn the best in this assignment?
   5. What distracted from your learning in this assignment?