Introduction to databases — Tutorial 2

Normalization

In this tutorial you’ll learn:

  • How to obtain a non-redundant set of functional dependencies.
  • How to determine the candidate keys of a table given its functional dependencies.
  • How to determine the normal form of a table.

1 Question 1

We consider a relational table \(R\) with four columns \(A\), \(B\), \(C\) and \(D\). Let \(\mathcal{F}\) be the following set of functional dependencies:

  1. \(AB \rightarrow C\)

  2. \(D \rightarrow BC\)

  3. \(A \rightarrow B\)

Exercise

Exercise 1.1 Derive a minimal set \(\mathcal{G}\) of functional dependencies that is equivalent to \(\mathcal{F}\).

2 Question 2

Let \(R\) be a relational table with five columns \((A, B, C, D, E)\). The following set \(\mathcal{F}\) 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 2.1 Specify the candidate keys of the table \(R\).

Exercise

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

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

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

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

Exercise

Exercise 2.3 If the table \(R\) from the previous exercise is not in BCNF, how would you change the schema so that BCNF is satisfied? For each table, specify the primary key and the foreign keys linking the tables to each other.

3 Question 3

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

Exercise

Exercise 3.1 Identify a minimal set of functional dependencies. Justify your answer.

Exercise

Exercise 3.2 Add \(B \rightarrow D\) to the set of functional dependencies that you identified in the previous exercise. Modify the minimal set of functional dependencies accordingly. Justify your answer.

Exercise

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

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

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

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

Exercise

Exercise 3.4 Normalize \(R\) to the BCNF form. Justify your choices.

4 Question 4

We consider the following table:

Patient (ssn, first_name, last_name, phone_number, insurance_number, 
         insurance_expiration_date)

where the following set \(\mathcal{F}\) of functional dependencies holds:

ssn -> first_name, last_name, phone_number, insurance_number, 
       insurance_expiration_date 

insurance_number -> insurance_expiration_date

Exercise

Exercise 4.1 Derive a minimal set \(\mathcal{G}\) of functional dependencies that is equivalent to \(\mathcal{F}\).

Exercise

Exercise 4.2 Given \(\mathcal{G}\), identify the candidate keys in the table Patient.

Exercise

Exercise 4.3 Specify the normal form of the table Patient. Justify your answer.

Exercise

Exercise 4.4 How would you normalize table Patient to BCNF? Justify your answer.