Homework Assignment 3

Each question is worth 25 points.

1. Consider a relation R with five attributes ABCDE. You are given the following dependencies: A B, BC E, and ED A.

a. List all keys for R.

b. Is R in 3NF?

c. Is R in BCNF?

2. Consider the following collection of relations and dependencies. Assume that each relation is obtained through decomposition from a relation with attributes ABCDEFGHI and that all the known dependencies over relation ABCDEFGHI are listed for each question. (The questions are independent of each other.)

For each (sub)relation: (1) State the strongest normal form that the relation is in. (2) If it is not in BCNF, decompose it into a collection of BCNF relations.

a. R1(A,C,B,D,E), A B, C D

b. R2(A,B,F), AC E, B F

c. R3(A,D,G), D G, G H

d. R4(D,C,H,G), A I, I A

e. R5(A,I,C,E)

3. Suppose that we pick the following three tuples from a legal instance of a relation S (S has 100 tuples in total). Relation S has the following schema:

(A : integer, B : integer, C : integer).

The three tuples are: (1,2,3), (4,2,3), and (5,3,3).

a. Which of the following dependencies can you infer does not hold over S?

1. A B,

2. BC A,

3. C B

b. Can you identify any dependencies that hold over S?

4. Suppose that we pick the following four tuples from a legal relation S (S has 100 tuples in total). S has the following schema:

(A: integer, B: integer, C: integer)

The four tuples are: (1,2,3), (4,2,3), (5,3,3) and (5,3,4).

Which of the following functional ()can you infer does not hold over relation S?

a. A B

b. BC A

c. A C

d. AC B