CS145 - Introduction to Databases
Spring 2000, Prof. Widom

Written Assignment #2
Due Wednesday April 19

The procedure for turning in this assignment is the same as for prior assignments, and please remember the strictly enforced late policy.

Problem 1

Consider a database for a university that may include information about students, courses, professors, etc.

(a) Within this general domain, specify the schema for an example relation and a set of functional dependencies (FD's) over the relation such that the relation is not in Boyce-Codd Normal Form (BCNF). Your relation need not be extensive (i.e., it need not include many attributes and it may represent only a very small part of the complete university information), but the schema and the FD's should be realistic in their modeling of the real world. You should make no assumptions besides those captured by the schema and the FD's.

(b) Decompose your relation from part (a) so that the new schema is in BCNF.

(c) Now specify the schema for an example relation and a set of FD's and multivalued dependencies (MVD's) over the relation such that the relation is in BCNF but is not in Fourth Normal Form (4NF). Again, your relation need not be extensive but the schema and the dependencies should be realistic in their modeling of the real world, and you should make no assumptions besides those captured by the schema and the dependencies. The relation you give for this part of the problem can capture similar or different information from that captured in part (a).

(d) Decompose your relation from part (c) so that the new schema is in 4NF.

(d) Read the textbook to learn about Third Normal Form (3NF). Specify the schema for an example relation and a set of FD's over the relation such that the relation is in 3NF but is not in BCNF. Of course you could use the same example for this part of the problem and for part (a), but we would prefer that you use a different one: non-BCNF schemas are rarely in 3NF in practice, so an example you would come up with naturally for part (a) in isolation is not likely to be in 3NF.

Problem 2

A database designer has as his first assignment to design the schema for a company database. Each employee has an ID (unique across employees), Name, Address, Office, and Salary. The designer decides to create the following four relations:

EmpName(ID, Name)
EmpAddress(ID, Address)
EmpOffice(ID, Office)
EmpSalary(ID, Salary)

(a) State the completely nontrivial functional dependencies for each relation.

(b)Are all four relations in Boyce-Codd Normal Form (BCNF)?

(c)Is this a good database design? Why or why not?

Problem 3

Consider a relation R(A,B,C,D,E). Suppose that the following five functional dependencies hold on R:

A -> D
AB -> C
B -> E
D -> C
E -> A

Now suppose that we decompose relation R so that one of the new relations is R1(A,B,C). Given the complete set of FD's above, specify all keys for R1. Don't forget that a key must be minimal, i.e., no strict subset of the attributes in a key can also form a key.

Problem 4

Two sets of functional dependencies (FD's) F and F' are equivalent if all FD's in F' follow from the ones in F, and all FD's in F follow from the ones in F'. Consider the following three sets of functional dependencies:

F1 = { A -> B, B -> C }
F2 = { A -> B, A -> C }
F3 = { A -> B, AB -> C }

(a) Are F1 and F3 equivalent? If so, prove that all FD's in F3 follow from the ones in F1, and vice-versa. If not, give a counterexample: show an instance (set of tuples) of a relation with schema (A,B,C) such that the dependencies in one of the sets all hold, while some dependency in the other set does not hold.

(b) Are F2 and F3 equivalent? If so, prove that all FD's in F3 follow from the ones in F2, and vice-versa. If not, give a counterexample: show an instance of a relation with schema (A,B,C) such that the dependencies in one of the sets all hold, while some dependency in the other set does not hold.

Problem 5

There is a rule (page 160 of the textbook) that states "every functional dependency is a multivalued dependency." Prove that the converse is not true: it is not true that every MVD is an FD. Prove it by providing a counterexample: Give a relation schema, an MVD:

A1,A2,...,An ->> B1,B2,...,Bm

and a relation instance (set of tuples) for which the MVD holds but the corresponding functional dependency:

A1,A2,...,An -> B1,B2,...,Bm

does not hold. As an additional requirement, the MVD in your counterexample should be a nontrivial one, but otherwise please give the simplest counterexample you can come up with.

Problem 6

Recall the algorithm for performing BCNF decomposition given in class. (Please note that a somewhat less detailed algorithm is given in the textbook, so please base your answer on the algorithm from class.) Give an example where the final decomposition of relations will be different depending on which order violating functional dependencies (FD's) are selected during the iterative process. Give an initial schema for a relation and a set of functional dependencies over that relation. Show step-by-step how the algorithm decomposes the relations differently depending on which violating FD is chosen in each iteration.

Problem 7

Continuing with the algorithm for performing BCNF decomposition given in class: What happens if we skip the first step of the algorithm? That is, what happens if we begin the step (2) loop with the original user-supplied FD's, instead of applying the closure first to "extend" the FD's as much as possible? If your answer to any of these three questions is yes, support your claim with at least one concrete example.

Problem 8

Warning: this one is a bit open-ended. Don't worry if you don't come up with a good answer.

Now consider the algorithm for performing 4NF decomposition given in class. (Again, a somewhat less detailed algorithm is given in the textbook, so please base your answer on the algorithm from class.)