[Solved] CS3431 Homework 6

Problem 1

For the relational schema given below and the corresponding functional dependencies (FDs)

R(A, B, C, D, E ) S = { AB E, B C, B D, CE A },

answer the following questions:

1. find all candidate keys of the relation R through an exhaustive set of attribute closures. Note when an attribute set closure is trivial.
2. Assume that S is a minimal basis for R. List the dependencies that violate 3NF, if any.

1. (5 points) If R is NOT in 3NF, decompose it into multiple relations that are in 3NF.
2. (5 points) List the dependencies, in the order given in S, that violate BCNF.

B -> C (not trivial, B not super key)

B -> D (not trivial, B not super key)

CE -> A (not trivial, CE not super key)

1. (10 points) If R is not in BCNF, provide decomposition into multiple relations where each one is in BCNF. For each decomposition step, use the first FD violation following the FD order given in S. For example, if AB E and B C are in BCNF but the other two FDs are in violation, then you would use B D for the decomposition. Make sure to specify which FD is used to make the decomposition.

Problem 2 (45 Points)

For the relational schema given below and its corresponding functional dependencies (FDs)

R(A, B, C, D, E ) S = { B A, B E, CE D, D B }

answer the following questions:

1. find all candidate keys of the relation through an exhaustive set of attribute closures. Note when an attribute set closure is trivial.
2. Decompose the relations to satisfy BCNF. Specify which FD is used to make the decomposition. If there is multi-step decomposition, then indicate each step along with which FD is used for the decomposition.
3. If the FDs are not in 3NF, calculate a minimal basis for the FDs and decompose the relations to satisfy 3NF.
4. Indicate whether each of the following decompositions is Lossy or Lossless and state why?
   1. Artist and Artwork are in one relation. Gallery, Address, and Artwork are in the other relation.

This is a lossless decomposition -> a natural join of the 2 relations would produce the original relation.

Another way to look at this is the following:

The common attributes of the two relations is just the Artwork.

Since the artwork is a key for both relations (i.e. Artwork -> Artist and Artwork -> Gallery,Address), the decomposition is lossless.

1. Gallery, Address, and Artwork are in one relation. Artist and Gallery are in one relation.

This is a lossy decomposition -> a natural join would create extra records for the Miami Beach Gallery

Another way to look at this:

The common attributes of the two relations is just the Gallery.

Since Gallery is not a key in either of them (i.e. Gallery x> Artist and Gallery x> Arist,Address), the decomposition is lossy.

2. (10 Points) Identify and list the set of functional dependencies from the data in the table above. Then, specify which of the following decompositions preserve those dependencies, and state why.

Note: it may help to draw the relations to visualize what may have changed through decomposition.

1. Gallery, Address, and Artist are in one relation. Artwork and Artist are in the other relation.

For the two tables individually we can see the following:

A natural Join of the Two Tables Would Looks as Follows

We can see from the natural join the following:

Preserves: Gallery -> Address

Artwork -> Artist

Artist -> Address

Artwork -> Address

Doesnt preserve: Artwork -> Gallery

Artist,Gallery -> Artwork

Since we can only join the tables on the Artist, we have no way of assigning a unique Gallery or Address to an Artwork. Weve also lost the ability to imply the Artwork using the Artist and the Gallery.

1. Gallery, Artist are in one relation. Artwork, Artist, and Address are in the other relation.

From the two tables individually we can see the following:

A natural join of the two tables would look as follows:

From the natural join we can see the following:

Since we can only join the tables on the Artist, we have no way of assigning a unique Gallery or Address to an Artwork. Weve also lost the ability to imply the Artwork using the Artist and the Gallery.