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.

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

`
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?

`
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.
*

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

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

**(a)** Could we get a different result? If so, is it better
or worse, and why?

**(b)** Could we get an incorrect result, e.g., a
decomposition that is missing information, or from which we cannot
reconstruct the original relation?

**(c)** Could we get a result that is not
in BCNF?

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

**(a)** We did not specify how to perform the "closure" of the
initial FD's and MVD's in step (1). Any ideas?

**(b)** We also did not specify how to assign new FD's and MVD's
after splitting a relation into two smaller relations. Any ideas?