Alan K. Dippel
CSC 570/671
October 26,1998
Professor: Fred Sadri
Department of Mathematical Sciences
University of North Carolina at Greensboro

http://www.cs.indiana.edu/~adippel/csc671/assignment4.htm

1. given
2. given
3. by augmentation applied to 1
4. by augmentation applied to 2
5. by transitivity applied to 3 and 4

Question 2 (10%)

Let be the relation scheme, and hold in R. Write (the closure of . Indicate which FD's are trivial. Use the attribute closure algorithm to calculate . Show your work.

Trivial FDs based on reflexity

, , , , , , , , , , , , , , , , , ,

Nontrivial FDs based on the following nontrivial attribute closures.

given, , , , , , given, , , , , , ,

Question 3 (20%)

Consider the relation scheme , with the following functional dependencies:

(a)

(5%) Compute the closure of BE.

trivial

union with 3.

union with 4

union with 1 on second pass

(b)

(15%) Find all candidate keys of R.

In order to have a candidate key the following must be true. K is the set of attributes.

Possible candidates are ,

trivial

union with 1

union with 3

union with 2 on second pass

trivial

union with 4

union with 1 second pass

union with 3 on second pass

trivial

union with 2

union with 4

union with 1 second pass

  trivial

union with 3, no more attributes in closure.

The candidate keys of R are .

The key is not a candidate, because a subset of is a candidate key

Question 4 (20%)

(a) Is it possible to have a relation (instance) on the scheme that satisfies the FDs and but violates the FD ? If it is possible, then write down such a relation with the fewest number of tuples possible. If it is not possible then prove (justify, argue) why it is not possible.

1.  given
2.  given
3. augmentation of 2
4. transitivity on 1 and 3
5. decomposition of 4

Since is an FD that can be derived from the given FDs, it is not possible for an instance of R to not satisfy .

(b) Is it possible to have a relation (instance) on the scheme that satisfies the FDs and but violates the FD ? If it is possible, then write down such a relation with the fewest number of tuples possible. If it is not possible then prove (justify, argue) why it is not possible.

satisfies and both and satisfy , but and violate , therefore it is possible.

Note: In the above questions, if an instance exists, then it is possible to find one with only two tuples.

Question 5 (20%)

Find a canonical (or minimal) cover for the following set of functional dependencies.

1. given
2. given
3. given
4. given
5. given
6. using union rule on 1 and 4
7. solving for on 6, G is extraneous
8. solving for on 7, C is extraneous
9. solving for on 2, E is extraneous
10. There are no extraneous attributes on the left side.

The Canonical cover is as follows:

Alan K. Dippel