Introduction to databases — Tutorial 2

Normalization


Question 1

Let \(R\) be a relational table with five columns \((A, B, C, D, E)\). The following set of functional dependencies hold:

  1. \(AB \rightarrow C\)
  2. \(C \rightarrow A\)
  3. \(C \rightarrow B\)
  4. \(C \rightarrow D\)
  5. \(D \rightarrow E\)

Exercise

Exercise 1 Find all the candidate keys of table \(R\).

Exercise

Exercise 2 We assume that \(R\) is in 1NF.

  • Is table \(R\) in 2NF? Justify your answer.

  • Is table \(R\) in 3NF? Justify your answer.

Exercise

Exercise 3 If the table \(R\) from the previous exercise is not in 3NF, what changes would you make to turn \(R\) into a 3NF table?

Important. For each table that you create, specify the primary key and the foreign keys.

Question 2

Each table has its own set of functional dependencies. For the sake of simplicity, we should always identify a minimal set of functional dependencies.

A set of functional dependencies is minimal if it complies with the following properties:

  1. Every functional dependency in the set is in canonical form: the right side consists of only one column.

  2. Every functional dependency in the set is left-irreducible: it is impossible to remove any of the columns on the left side without losing any information.

  3. Every functional dependency in the set is non-redundant. We should not be able to derive one functional dependency in the set from another.

Formally, a functional dependency is redundant if we can derive it by successive applications of the Armstrong’s axioms on the other functional dependencies. Armstrong’s axioms are detailed here.

Exercise

Exercise 4 Let \(R\) be a relational table with four columns \((A, B, C, D)\). \(\{A, B\}\) is the only candidate key of \(R\).

Identify a minimal set of functional dependencies on \(R\).

Justify your answer.

Exercise

Exercise 5 Would the set obtained in the previous exercise still be minimal, if we added the functional dependency \(B \rightarrow D\)?

Justify your answer and, in case of a negative answer, specify the minimal set of functional dependencies.

Exercise

Exercise 6 We assume that \(R\) is in 1NF.

  • Is table \(R\) in 2NF? Justify your answer.

  • Is table \(R\) in 3NF? Justify your answer.

Exercise

Exercise 7 Normalize \(R\) to the 3NF form.

Important. For each table that you create, specify the primary and foreign keys.

Justify your choices.

Question 3

Let \(R\) be a relational table with five columns \(A\), \(B\), \(C\), \(D\), \(E\). The following set of functional dependencies is given:

  1. \(A \rightarrow B\)
  2. \(A \rightarrow C\)
  3. \(B \rightarrow C\)
  4. \(D \rightarrow E\)

Exercise

Exercise 8 Is the given set of functional dependencies minimal? If not, which functional dependencies must be removed to obtain a minimal set?

Justify your answer.

Exercise

Exercise 9 Given the minimal set of functional dependencies obtained from the previous exercise, determine the candidate keys of \(R\).

Justify your answer.

Exercise

Exercise 10 Given the candidate keys that you found in the previous exercise, which columns are prime? Which ones are non-prime?

Exercise

Exercise 11 We assume that R is in 1NF. Which normal form is R in?

Justify your answer.

Exercise

Exercise 12 How would you turn R into 3NF?

Justify your answer.

Specify primary and foreign keys of all tables that you create.