#Practical Session 6 - Functional Dependencies and Normal Forms

###By Dr Edmund Sadgrove

### University of New England

---

## Reading
* Chapter 8 from ***Fundamentals of Database Systems*** by Elmazri and Navathe

---

## Summary

* Introduction
* Functional Dependencies
* Normal Forms
* Examples

---

## Introduction

* In this workshop we will revise and work through the concepts of function depencies and normal forms. Our exercises will explore the manual examination of a fictional database and look at ways to improve / optimise a solution. 

---

## Functional Dependencies 

* Recall that functional dependencies reflect real relationships between attributes and columns in our database. 
* In database schema design, the main goals are:
	* **Information preservation**:
<img style="float: right;" width="50%" src="images/databaseInt.png" />
		* Preserving database integrity.
		* The meaning of our data.
	* **Minimum redundancy**:
		* Minimising the redundant storage of the same data.
		* Improves efficiency of operations.
		* Reduces storage requirements.

* The process of normalisation reduces redundancy and preserves the meaning of the data.

* ***Functional Dependencies***:
	* Denoted by `\( X \rightarrow Y\)`.
		* Where X and Y are sets of attributes from a relation.
		* Specifies a constraint that `X`  functionally determines `Y`

	* Further:
		*  If t<sub>1</sub> and t<sub>2</sub> are tuples and if `\(t _1 [X] = t _2[X]\)` then `\(t _1 [Y] = t _2[Y]\)` 
		* As values of *Y* in *r* are determined by *X*.
		
* Example: DEPARTMENT dnumber determines dname.

* One final note on the notation
    * Single attributes (of relation *R*) can determine the values of a set of attributes in *R*.

    * Denoted using the curly braces: `\( a \rightarrow \{b,c\}\)` 
    	* Example: `\( pnumber \rightarrow \{pname,plocation\}\)`.
    	* And the reverse `\( \{ssn,pnumber\} \rightarrow hours\)`.

* Now we can look at the **normalisation process**.
## Normal Forms:
* Recall from the lectures: 
	* To satisfy a normal form, a relational schema must satisfy a criteria.

* Within this framework there are 6 **normal forms**:
    * First (1NF), Second (2NF), third (3NF), Boyce-Codd (BCNF), forth (4NF) and fifth(5NF) Normal form.
    
<img style="float: right;" width="35%" src="images/norms.png" />

    * In this course, we will cover the use of 1NF, 2NF, 3NF and BCNF

## First Normal Form

* **First Normal form**:
<img width="35%" src="images/car_er.png" />
	* Based on the formal definition of a flat relational model.
	* **1NF** dis-allows **multi-valued attributes**:
		* Each attribute must only include ***atomic values*** (single values).

* Within the relational data model, any valid relation will satisfy the first normal form.

* There are 3 approaches for normalising to **1NF**:
<img style="float: right;" width="55%" src="images/1nf.png" />
	* **Separate relation**:
		* Offending attribute moved to a new relation.
		* E.g. DEPT_LOCATIONS relation.
	* **New tuple**:
		* New a tuple for each value.
		* Introduce redundancy.
	* **New attribute**:
		* New attribute for each value.
		* Causes NULL values. 

* **Separate relation**:
	* This is the most desrable option.
	* Does not introduce redundancy or NULL values.

* **1NF** also disallows the use of *relation-valued* attributes.
	* These are *nested relations*:
		* Allows attributes within the tuples to contain another relation.
	* **Nested relations** can be normalised as a stand-alone relation.
		* A **foreign-key** constraint is used to link back to the original relation.
		
## Second Normal Form

* **Second normal form**:
	* Based on the concept of *full functional dependency* on the **primary key**.
	* **Full functional dependency**:
		* Occurs if the removal of any attribute from the left side destroys the dependency.
	* **Partially dependent**:
		* Attributes that can be removed from the left side without destroying *all* dependencies.
	* A relation is in **2NF**:
		* If **non-prime** attributes *A* in *R* are *fully* **functionally dependent** on the **primary key**.

* Testing is intuitive: If attributes on the right are not determined by an attribute on the left, it is not in **2NF**.

<img width="40%" src="images/ex2.png" />

* **Normalising 2NF**:
	* **Non-2NF** relations are decomposed into separate 2NF relations.
	* In the new **2NF** relations, all attributes are fully dependent on their **primary keys**.
	* New relations are linked through **foreign keys**.
		* This preserves the meaning of our data.

* This also applies to candidate keys:
	* E.g. {Country_name, Lot#}

* Single attribute **primary keys** need not be tested.

## Third Normal Form

* **Third normal form**: Based upon the idea of *transitive dependency*.
* A **transitive dependency** `\(X \rightarrow Y\)`:
	* Exists in a relation *R* if:
		* There exists a set of attributes *Z* in *R*:
		* Such that: `\(X  \rightarrow Z\)` and `\( Z \rightarrow Y\)`
		* Where *Z* is either a candidate key or not part of the primary key (*nontrivial*).
* A relation *R* is in **3NF** if:
	* It satisfies **2NF**.
	* No **non-prime** attribute of *R* is **transitively dependent** on the **primary key**.
		* This implies prime attributes can be transitively dependent.

<img style="float: right;" width="40%" src="images/2nf.png" />

* **3NF example 1**:
	* The **EMP_DEPT** relation is in **2NF**:
		* No attribute is partially dependent on the primary key.
	* It is not in **3NF**:
		* Dname and Dmgr_ssn are dependent on the Dnumber.
		* Dnumber is not a candidate key.

	* This relation can be normalised by decomposing it into two 3NF relations (ED1 and ED2).

* **3NF example 2**:
	*  **LOTS1** is still not in **3NF**:
<img width="45%" src="images/3nf.png" />
		* Transitive dependency - Price is dependent on area.
		* Area is not part of the primary key and Price is a **non-prime** attribute.
		* Price is transitively dependent on both of the candidate keys.

	* Price is determined by Area independent of the other attributes.
	* To normalise this relation , we can decompose it into two 3NF relations. 

## Normalise Example

<img width="60%" src="images/bad_data.png" />

* EMP_PROJ and EMP_DEPT are already in 1NF:
	* No multi-valued attributes or nested relations.
		* Nested relations are not allowed in SQL.
* They are both in 2NF:
	* Both have attributes functionally dependent on the primary key.
* However, they are not in 3NF or BCNF:
	* They contain transitive dependencies and prime attributes.

* While ssn is the primary key, dnumber determines dlocation and dname. 
* We need to decompose EMP_DEPT.
	* Based on duplicates and matching primary attributes:
		* It is clear that `\( Ssn \rightarrow \{Ename,Bdate,Address\}\)` 
		* And that `\( Dnumber \rightarrow \{Dname,Dmgr_ssn\}\)` 
		* Which makes two relations: EMP & DEPT
	
* Again, while ssn is the primary key, pnumber determines plocation and pname. 
* The ssn and pnumber determine hours. We should decompose EMP_PROJ.
	* Based on duplicates and matching primary attributes:
		* It is clear that `\( Ssn,Pnumber \rightarrow \{Hours\}\)` 
		* And that `\( Pnumber \rightarrow \{Pname,Plocation\}\)` 
		* And that `\( Ssn \rightarrow \{Ename\}\)`  (redundant)
		* Which makes two relations: PROJ and WORKS_ON
		
* The new relations now satisfy 3NF.
* They also satisfy BCNF, as no prime attributes determined by primary keys.

---
## Exercises for You
For these questions, feel free to make assumptions about the key attributes for functional dependencies, there may be more than one result, but there is typically a more efficient result, see if you can find it.

### Exercise 1:
Reviewing the following relation and associated tuples, find all the functional dependencies depicted. For this, you can look at the uniqueness of each attribute and what it aligns with.

* Enrollments(StudentID, CourseID, StudentName, DeptID, DeptName, CourseTitle, Grade)

| StudentID | CourseID | StudentName  | DeptID | DeptName          | CourseTitle | Grade |
|:---------:|:--------:|:-------------|:------:|:------------------|:------------|:-----:|
| S01       | C101     | Alice Brown  | D10    | Computer Science  | Databases   | A     |
| S01       | C102     | Alice Brown  | D10    | Computer Science  | Networks    | B+    |
| S02       | C101     | Ben Clark    | D20    | Mathematics       | Databases   | B     |
| S02       | C103     | Ben Clark    | D20    | Mathematics       | Algorithms  | B-    |
| S03       | C103     | Chloe Diaz   | D10    | Computer Science  | Algorithms  | A-    |
| S03       | C102     | Chloe Diaz   | D10    | Computer Science  | Networks    | A     |

### Exercise 2:
Following the rules for each normal form, provide justification at each step and decompose the relation in Exercise 1 into 3NF.

## Exercise 3:
Review the following relation with composite key (A, C) and set of functional dependencies, from the information provided, determine the normal form and if it is not in 3NF decompose the relation into separate relations that meet the criteria for 3NF.

* R(<u>A</u>, <u>C</u>, B, D, E, F)
* 1) A  → B
* 2) C  → D
* 3) AC → E
* 4) E  → F

### Exercise 4: 
Review the following relation and set of functional dependencies, from the information provided, determine the normal form and if it is not in 3NF decompose the relation into separate relations that meet the criteria for 3NF. 

Hint: You will need to first determine the composite key of the relation.

* Relation: R(A, B, C, D, E)
* F = {A -> BC, CD -> BE}