CSCI-GA.2433-011-Homework 4 solved

1.      Find a minimal cover for α, say ω

2.      Produce a relation from each FD in ω by combining the attributes from both the LHS and the RHS

3.      One by one, remove a relation that is a subset of another relation

4.      If (at least) one of the relations contains a key of R, you are done

5.      Otherwise, add a relation that is a key for R

Example 1. Assume that I am supposed to do the above for R = ABC with FDs

1.      AB → C

2.      A → B

I attempt to remove B from LHS of (1). The new set of FDs is

1.      A → C

2.      A → B

The new set can only be stronger than the old set to test for equivalence, I attempt to prove (1) of the new set from all of the old set. Doing that I get:

A + = ABC and as I get the RHS of the new (1), the new set is equivalent to the old set.

Nothing else can be attempted, so my last set (here the second) is a minimal cover.

I now create relations

AB

AC
Nothing can be removed.

I now test whether at least one of the relations contains a key for R. Using my FDs, I compute

AB + = ABC.

I conclude that AB contains a key for R and I am finished. 

Now 7 Problems for you to work on

1.  You are given the application described in slide 7/39. Do not assume any knowledge, such that the business rules are already in a nice format. You are just given the schema and the set of FDs that it satisfies. Follow the procedure in the above “Complete Procedure Review”. Do not skip any steps. This means that you have to compute every closure of the sets of attributes that you need and you need to show that your minimal cover is indeed a minimal cover, as otherwise you do not know that it is a minimal cover.

2.  You are given a relational schema satisfying some FDs, among them A → B. Explain why ABC cannot be a key of the schema.

3.   Using the heuristics described on slides 7/134–7/135 and providing full details and explanations, compute all the keys of R = ABCDEFGH given the FDs

•        A → AB

•        A → G

•        C → A

•        D → G

•        F → GH

•        H → AF

4. You are given a relational schema R = ABC, satisfying the following FDs

•        A → B

•        A → C

•        B → C

(a) Which normal forms are satisfied? (Ignore 2NF) (b) A decomposition into AB and AC is proposed.

•        Which normal forms are satisfied by AB and AC?

•        Show by a small example that the dependencies are not preserved.

5.  You are given a relational schema R = ABC, satisfying the following FDs

•        A → B

•        A → C

•        B → C

(a)  Which normal forms are satisfied? (Ignore 2NF) (b) A decomposition into AC and BC is proposed.

•        Which normal forms are satisfied by AC and BC?

•        Show by a small example that the decomposition is not a lossless-join decomposition.

6.  You are given a relational schema R = ABCDEFGH, satisfying α, the set of

FDs

•        A → D

•        A → E

•        AG → H

•        BF → H

•        C → H

•        E → D

•        F → B

(a)  Compute ω, a minimal cover for α.

Follow the procedure in the above “Complete Procedure Review”. Do not skip any steps. This means that you have to compute every closure of the sets of attributes that you need and you need to show that your minimal cover is indeed a minimal cover, as otherwise you do not know that it is a minimal cover.

7.  You are given a relational schema R = ABCDEFGH, satisfying α, the set of

FDs

•        AB → CD

•        A → E

•        B → FG

•        E → AH

You are told that α is a minimal cover, and you may believe that. (a) Find a decomposition satisfying the conditions in the above “Complete Proced