Database Normalization

• Normalization allows you to remove redundant data within your database.
• This involves restructuring the tables to successively meeting higher forms of Normalization
• A properly normalized database should have the following characteristics
• Scalar values in each fields
• Absence of redundancy.
• Minimal use of null values.
• Minimal loss of information.

Definition

• Levels of normalization based on the amount of redundancy in the database.
• Various levels of normalization are:
• First Normal Form (1NF)
• Second Normal Form (2NF)
• Third Normal Form (3NF)
• Boyce-Codd Normal Form (BCNF)
• Fourth Normal Form (4NF)
• Fifth Normal Form (5NF)
• Domain Key Normal Form (DKNF)

Levels of Normalization

Redundancy

Number of Tables

Most databases should be 3NF or BCNF in order to avoid the database anomalies.

Complexity

Levels of Normalization

Each higher level is a subset of the lower level

First Normal Form (1NF)

• A relation will be 1NF if it contains an atomic value.
• It states that an attribute of a table cannot hold multiple values. It must hold only single-valued attribute.
• First normal form disallows the multi-valued attribute, composite attribute, and their combinations.

​

First Normal Form (1NF)

Example: Relation EMPLOYEE is not in 1NF because of multi-valued attribute EMP_PHONE.

EMPLOYEE table:

First Normal Form (1NF)

The decomposition of the EMPLOYEE table into 1NF has been shown below:

• A table is considered to be in 1NF if all the fields contain only scalar values (as opposed to list of values)
• There should not be any multi-valued attribute

Example (Not 1NF)

First Normal Form (1NF)

Author and AuPhone columns are not scalar

1. Place all items that appear in the repeating group in a new table
2. Designate a primary key for each new table produced.
3. Duplicate in the new table the primary key of the table from which the repeating group was extracted or vice versa.

Example (1NF)

1NF - Decomposition

1. If one set of attributes in a table determines another set of attributes in the table, then the second set of attributes is said to be functionally dependent on the first set of attributes.

​

Example 1

Functional Dependencies

Table Scheme: {ISBN, Title, Price}

Functional Dependencies: {ISBN} 🡪 {Title}

{ISBN} 🡪 {Price}

Example 2

Functional Dependencies

Table Scheme: {PubID, PubName, PubPhone}

Functional Dependencies: {PubId} 🡪 {PubPhone}

{PubId} 🡪 {PubName}

{PubName, PubPhone} 🡪 {PubID}

Example 3

Table Scheme: {AuID, AuName, AuPhone}

Functional Dependencies: {AuId} 🡪 {AuPhone}

{AuId} 🡪 {AuName}

{AuName, AuPhone} 🡪 {AuID}

Database to track reviews of papers submitted to an academic conference. Prospective authors submit papers for review and possible acceptance in the published conference proceedings. Details of the entities

• Author information includes a unique author number, a name, a mailing address, and a unique (optional) email address.
• Paper information includes the primary author, the paper number, the title, the abstract, and review status (pending, accepted,rejected)
• Reviewer information includes the reviewer number, the name, the mailing address, and a unique (optional) email address
• A completed review includes the reviewer number, the date, the paper number, comments to the authors, comments to the program chairperson, and ratings (overall, originality, correctness, style, clarity)

FD – Example

Functional Dependencies

• AuthNo 🡪 AuthName, AuthEmail, AuthAddress
• AuthEmail 🡪 AuthNo
• PaperNo 🡪 Primary-AuthNo, Title, Abstract, Status
• RevNo 🡪 RevName, RevEmail, RevAddress
• RevEmail 🡪 RevNo
• RevNo, PaperNo 🡪 AuthComm, Prog-Comm, Date, Rating1, Rating2, Rating3, Rating4, Rating5

FD – Example

Second Normal Form (2NF)�

• In the 2NF, relational must be in 1NF.
• In the second normal form, all non-key attributes are fully functional dependent on the primary key
• Example: Let's assume, a college can store the data of teachers and the subjects they teach. In a college, a teacher can teach more than one subject.

​

Second Normal Form (2NF)�

TEACHER table:

In the given table, non-prime attribute TEACHER_AGE is dependent on TEACHER_ID which is a proper subset of a candidate key. That's why it violates the rule for 2NF.

• To convert the given table into 2NF, we decompose it into two tables:

​

TEACHER_DETAIL table:

TEACHER_SUBJECT table:

Third Normal Form (3NF)�

• A relation will be in 3NF if it is in 2NF and not contain any transitive partial dependency.
• 3NF is used to reduce the data duplication. It is also used to achieve the data integrity.
• If there is no transitive dependency for non-prime attributes, then the relation must be in third normal form.
• Or No attribute is transitively dependent on the primary key

​

​

Third Normal Form (3NF) �

• A relation is in third normal form if it holds atleast one of the following conditions for every non-trivial function dependency

X → Y.

• X is a super key.
• Y is a prime attribute, i.e., each element of Y is part of some candidate key.

​

Third Normal Form (3NF) �

​

Example:

EMPLOYEE_DETAIL table:

​

Third Normal Form (3NF) �

Super key in the table above:

• {EMP_ID}, {EMP_ID, EMP_NAME}, {EMP_ID, EMP_NAME, EMP_ZIP}....so on  

Candidate key: {EMP_ID}

​

Third Normal Form (3NF) �

• Non-prime attributes: In the given table, all attributes except EMP_ID are non-prime.
• Here, EMP_STATE & EMP_CITY dependent on EMP_ZIP and EMP_ZIP dependent on EMP_ID. The non-prime attributes (EMP_STATE, EMP_CITY) transitively dependent on super key(EMP_ID). It violates the rule of third normal form.
• That's why we need to move the EMP_CITY and EMP_STATE to the new <EMPLOYEE_ZIP> table, with EMP_ZIP as a Primary key.

​

Third Normal Form (3NF) �

​

EMPLOYEE table:

​

Third Normal Form (3NF) �

​

EMPLOYEE_ZIP table:

​

�Boyce Codd normal form (BCNF)�

• BCNF is the advance version of 3NF. It is stricter than 3NF.
• A table is in BCNF if every functional dependency X → Y, X is the super key of the table.
• For BCNF, the table should be in 3NF, and for every FD, LHS is super key.
• Example: Let's assume there is a company where employees work in more than one department.

​

​

EMPLOYEE table:

In the above table Functional dependencies are as follows:

1. EMP_ID  →  EMP_COUNTRY  
2. EMP_DEPT  →   {DEPT_TYPE, EMP_DEPT_NO}  

Candidate key: {EMP-ID, EMP-DEPT}

The table is not in BCNF because neither EMP_DEPT nor EMP_ID alone are keys.

To convert the given table into BCNF, we decompose it into three tables:EMP_COUNTRY table:

EMP_DEPT table:

EMP_DEPT_MAPPING table:

Functional dependencies:

EMP_ID   →    EMP_COUNTRY  

EMP_DEPT   →   {DEPT_TYPE, EMP_DEPT_NO}  

Candidate keys:

For the first table: EMP_ID�For the second table: EMP_DEPT�For the third table: {EMP_ID, EMP_DEPT}

Fourth normal form (4NF)�

• A relation will be in 4NF if it is in Boyce Codd normal form and has no multi-valued dependency.
• For a dependency A → B, if for a single value of A, multiple values of B exists, then the relation will be a multi-valued dependency.

​

Example�

STUDENT

The given STUDENT table is in 3NF, but the COURSE and HOBBY are two independent entity. Hence, there is no relationship between COURSE and HOBBY.

In the STUDENT relation, a student with STU_ID, 21 contains two courses, Computer and Math and two hobbies, Dancing and Singing. So there is a Multi-valued dependency on STU_ID, which leads to unnecessary repetition of data.

• So to make the above table into 4NF, we can decompose it into two tables:

​

STUDENT_COURSE

STUDENT_HOBBY

Fifth normal form (5NF)�

• A relation is in 5NF if it is in 4NF and not contains any join dependency and joining should be lossless.
• 5NF is satisfied when all the tables are broken into as many tables as possible in order to avoid redundancy.
• 5NF is also known as Project-join normal form (PJ/NF).

​

Example

​

In the above table, John takes both Computer and Math class for Semester 1 but he doesn't take Math class for Semester 2. In this case, combination of all these fields required to identify a valid data.

Suppose we add a new Semester as Semester 3 but do not know about the subject and who will be taking that subject so we leave Lecturer and Subject as NULL. But all three columns together acts as a primary key, so we can't leave other two columns blank.

• So to make the above table into 5NF, we can decompose it into three relations P1, P2 & P3:
• P1:

​

P2

P3