Database Normalization

Database Normalization

Normalization is the formal process of organizing data in a database. It involves dividing large, poorly designed tables into smaller, well-structured tables and establishing relationships between them. The goal is to minimize data redundancy and eliminate undesirable characteristics like Insertion, Update, and Deletion Anomalies.

1. Database Anomalies

1. Insertion Anomaly: You cannot add a new Course and Instructor to the database until at least one student enrolls in it (assuming Student_ID is part of the primary key).
2. Deletion Anomaly: If the only student taking a specific course drops out and their record is deleted, the information about the course and its instructor is also permanently lost.
3. Update (Modification) Anomaly: If an instructor's name changes, you must update multiple rows (one for every student taking that instructor's course). If you miss even one row, the data becomes inconsistent.

2. Functional Dependency (FD)

• Determinant: The set of attributes on the left side of the arrow (X).
• Dependent: The attribute on the right side of the arrow (Y).
• Trivial FD: X -> Y is trivial if Y is a subset of X (e.g., {Roll_No, Name} -> Roll_No).
• Non-Trivial FD: X -> Y where Y is not a subset of X.
• Fully Functional Dependency: An attribute Y is fully functionally dependent on X if it is dependent on X and not on any proper subset of X.
• Partial Dependency: When a non-prime attribute depends on only a part of a composite primary key. (e.g., If Primary Key is {A, B}, and A -> C, then C is partially dependent).
• Transitive Dependency: When a non-prime attribute depends on another non-prime attribute. (e.g., A -> B and B -> C, implies A -> C).

2.1 Armstrong's Axioms

1. Reflexivity: If Y is a subset of X, then X -> Y.
2. Augmentation: If X -> Y, then XZ -> YZ.
3. Transitivity: If X -> Y and Y -> Z, then X -> Z.
4. Union: If X -> Y and X -> Z, then X -> YZ.
5. Decomposition: If X -> YZ, then X -> Y and X -> Z.
6. Pseudotransitivity: If X -> Y and WY -> Z, then WX -> Z.

3. Normal Forms

3.1 First Normal Form (1NF)

• Rule: A relation is in 1NF if every cell contains a single, atomic value.
• It explicitly forbids multi-valued attributes, composite attributes, and repeating groups.
• Example Violation: A Student table with a Phone_Numbers column containing "12345, 67890".
• Fix: Create a separate row for each phone number, or a separate table mapping Student_ID to Phone_Number.

3.2 Second Normal Form (2NF)

• Rule 1: The relation must be in 1NF.
• Rule 2: It must not have any Partial Dependency. Every non-prime attribute (attribute not part of any candidate key) must be fully functionally dependent on the entire primary key.
• Note: If a table has a single-attribute primary key and is in 1NF, it is automatically in 2NF.
• Example Violation: Table Order_Details(Order_ID, Product_ID, Product_Name, Quantity). Primary Key is {Order_ID, Product_ID}. However, Product_Name depends only on Product_ID (partial dependency).
• Fix: Split into Order_Details(Order_ID, Product_ID, Quantity) and Products(Product_ID, Product_Name).

3.3 Third Normal Form (3NF)

• Rule 1: The relation must be in 2NF.
• Rule 2: It must not have any Transitive Dependency. Non-prime attributes must not depend on other non-prime attributes.
• Formal Definition: For every non-trivial FD X -> Y, either X is a Super Key, OR Y is a prime attribute.
• Example Violation: Employee(Emp_ID, Name, Department_ID, Department_Name). Emp_ID -> Department_ID, and Department_ID -> Department_Name. Therefore, Emp_ID -> Department_Name transitively.
• Fix: Split into Employee(Emp_ID, Name, Department_ID) and Department(Department_ID, Department_Name).

3.4 Boyce-Codd Normal Form (BCNF)

• BCNF is a stronger, stricter version of 3NF (sometimes called 3.5NF).
• Rule: For every non-trivial functional dependency X -> Y, X must be a Super Key.
• It resolves anomalies that 3NF cannot handle, specifically in tables where there are multiple, overlapping candidate keys.
• If a table is in BCNF, it is guaranteed to be in 3NF, 2NF, and 1NF.

3.5 Fourth Normal Form (4NF)

• Rule: The relation must be in BCNF, and it must not contain any Multi-valued Dependencies (MVD).
• An MVD X ->-> Y exists when for a single value of X, there are multiple values of Y, and these values of Y are independent of other attributes in the table.
• Example: A Professor can teach multiple Courses and have multiple Hobbies. Courses and Hobbies are independent. Storing them in one table (Professor, Course, Hobby) creates massive redundancy.

3.6 Fifth Normal Form (5NF) / Project-Join Normal Form (PJNF)

• Rule: The relation must be in 4NF, and it cannot have a Join Dependency.
• A table is in 5NF if it cannot be decomposed into smaller tables without losing information when those smaller tables are joined back together (lossless decomposition).

4. De-normalization

• Normalization reduces redundancy but increases the number of tables. Retrieving data often requires complex, resource-intensive JOIN operations.
• De-normalization is the intentional process of adding redundancy back to a normalized database to optimize read (SELECT) performance.
• It is heavily used in OLAP (Online Analytical Processing) and Data Warehousing, where fast read times are more critical than fast write/update times.