Unit 4: Normalization

4.1 Anomalies Created by Poor Database Design

When a database is designed poorly without considering the underlying relationships between data items, it often leads to data redundancy. Data redundancy not only consumes extra storage space but also creates severe maintenance problems known as anomalies. An anomaly is an undesirable irregularity or inconsistency in a database that arises when modifying data.

There are three primary types of anomalies in poor database design:

1. Insertion Anomaly: This occurs when certain attributes cannot be inserted into the database without the presence of other attributes. For example, consider a table Course_Instructor(CourseID, CourseName, InstructorID, InstructorName) where the primary key is a combination of CourseID and InstructorID. If a new instructor is hired but has not yet been assigned a course, we cannot insert their details into the table because the CourseID (part of the primary key) cannot be NULL.
2. Deletion Anomaly: This occurs when the deletion of a record inadvertently causes the loss of other essential data. Using the same Course_Instructor table, if an instructor temporarily stops teaching a specific course and we delete that course record, we might unintentionally lose all information about the instructor if they teach no other courses.
3. Updation (Update) Anomaly: This occurs when one or more instances of duplicated data are updated, but others are left unchanged, leading to data inconsistency. If an instructor's name changes, the update must be applied to every row where that instructor teaches a course. If even one row is missed, the database will contain contradictory information about the instructor's name.

4.2 Normalization

4.2.1 Definition and its Importance

Normalization is the systematic process of organizing data within a relational database to minimize redundancy and eliminate undesirable characteristics like insertion, update, and deletion anomalies. Introduced by Edgar F. Codd in 1970, normalization involves dividing larger, poorly structured tables into smaller, well-structured tables and linking them using relationships (primary and foreign keys).

Importance of Normalization:

• Data Integrity: Ensures data accuracy and consistency across the database.
• Efficient Updates: Reduces the amount of time and resources required to update, insert, or delete records.
• Space Optimization: Minimizes duplicated data, thereby reducing the physical storage required.
• Logical Data Grouping: Grouping data logically into related tables makes it easier to query and understand the database schema.

4.2.2 Goals of Normalization

The primary goals of the normalization process include:

• Eliminating Redundant Data: Ensuring that the same piece of information is not stored in more than one place unnecessarily.
• Ensuring Data Dependencies Make Sense: Storing data in tables only if it logically belongs there. For instance, student details should be in a Students table, not mixed with a Courses table.
• Isolating Data: Ensuring that additions, deletions, and modifications of a field can be made in just one table and propagated throughout the database securely via defined relationships.
• Minimizing Null Values: Structuring the database to avoid sparsity or the necessity of storing numerous NULL values.

4.3 Functional Dependencies

Functional Dependency (FD) is a foundational concept in database normalization. It describes the relationship between attributes in a table.

4.3.1 Prime Vs Non-Prime Attributes

To understand functional dependencies and normal forms deeply, one must distinguish between prime and non-prime attributes:

• Candidate Key: A minimal set of attributes that can uniquely identify a tuple (row) in a relation.
• Prime Attribute: Any attribute that is a part of any candidate key of the relation.
• Non-Prime Attribute: Any attribute that is not a part of any candidate key.

Example: In a relation R(A, B, C, D) where the candidate keys are {A, B} and {B, C}, the prime attributes are A, B, and C. D is a non-prime attribute.

4.3.2 Functional Dependency

A Functional Dependency is a relationship that exists between two sets of attributes in a relational database. If attribute X uniquely determines attribute Y, we say that Y is functionally dependent on X.

This is denoted as X → Y (read as "X determines Y" or "Y is functionally dependent on X").

• Determinant: The attribute (or set of attributes) on the left side of the arrow (X).
• Dependent: The attribute on the right side of the arrow (Y).

For example, in a Student table, StudentID → StudentName. If we know the StudentID, we can unambiguously find the StudentName.

4.3.2.1 Partial Functional Dependency

A Partial Functional Dependency exists when a non-prime attribute is functionally dependent on only a part of a composite candidate key.

Example: Consider a table Enrollment(StudentID, CourseID, StudentName).

• The primary key is the composite key {StudentID, CourseID}.
• The attribute StudentName depends only on StudentID, not on the whole composite key.
• Thus, StudentID → StudentName is a partial dependency because StudentID is just a part of the primary key.

4.3.2.2 Full Functional Dependency

A Full Functional Dependency occurs when an attribute is functionally dependent on the entire primary key and not on any subset of that key.

Example: In the same Enrollment(StudentID, CourseID, Grade) table:

• To determine the Grade, one needs both the StudentID and the CourseID.
• Therefore, {StudentID, CourseID} → Grade is a full functional dependency. The grade cannot be determined by the student alone or the course alone.

4.3.2.3 Transitive Dependency

A Transitive Dependency occurs when an indirect relationship exists between values in the same table. Specifically, if X → Y and Y → Z, then X → Z is a transitive dependency, assuming Y is not a candidate key.

Example: Consider a table Employee(EmpID, DeptID, DeptName).

• EmpID → DeptID (An employee belongs to a department)
• DeptID → DeptName (A department ID determines its name)
• Therefore, EmpID → DeptName is a transitive dependency, as the department name depends on EmpID indirectly through DeptID.

4.4 Normal Forms

Normal forms provide specific criteria to determine the degree to which a database table is normalized. A table in a higher normal form is less prone to anomalies.

4.4.1 First Normal Form (1NF)

A relation is in First Normal Form (1NF) if and only if it follows these two rules:

1. Atomicity: Every cell in the table must hold a single, indivisible (atomic) value.
2. No Repeating Groups: A table must not contain repeating groups or arrays of data in a single column.

Example Problem: A table storing multiple phone numbers in one column.

1NF Solution: Create individual rows for each atomic value.

4.4.2 Second Normal Form (2NF)

A relation is in Second Normal Form (2NF) if it satisfies two conditions:

1. It is already in 1NF.
2. It contains no partial functional dependencies. (Every non-prime attribute must be fully functionally dependent on the whole candidate key).

Example Problem: Consider OrderDetails(OrderID, ProductID, ProductName, Quantity). Primary key: {OrderID, ProductID}.

• Partial Dependency: ProductID → ProductName. The product name depends only on the product ID, not the order ID.

2NF Solution: Decompose the table to remove partial dependencies.

• Order(OrderID, ProductID, Quantity)
• Product(ProductID, ProductName)

4.4.3 Third Normal Form (3NF)

A relation is in Third Normal Form (3NF) if it meets the following criteria:

1. It is already in 2NF.
2. It contains no transitive dependencies. (Non-prime attributes must depend ONLY on candidate keys, not on other non-prime attributes).

Example Problem: Consider Student(StudentID, Name, ZipCode, City, State). Primary key: StudentID.

• Transitive Dependency: StudentID → ZipCode, and ZipCode → {City, State}. The City and State depend on the ZipCode, not directly on the StudentID.

3NF Solution: Decompose the table to eliminate the transitive dependency.

• Student(StudentID, Name, ZipCode)
• Location(ZipCode, City, State)

4.4.4 Boyce Codd Normal Form (BCNF)

Boyce-Codd Normal Form (BCNF) is a stricter version of 3NF, often referred to as 3.5NF. A relation is in BCNF if:

1. It is in 3NF.
2. For every non-trivial functional dependency X → Y, the determinant X must be a Superkey.

BCNF handles cases where 3NF fails, typically in tables with multiple overlapping candidate keys.

Example Problem: Consider Class(Student, Course, Instructor). Rules: A student can take many courses. A course can be taught by multiple instructors, but an instructor teaches only one course.

• Candidate Keys: {Student, Course} and {Student, Instructor}.
• Dependency: Instructor → Course. Even though the table is in 3NF (no partial or transitive dependencies of non-prime attributes), it violates BCNF because Instructor is a determinant but NOT a superkey.

BCNF Solution: Decompose the relation:

• Teach(Instructor, Course)
• Enroll(Student, Instructor)

By adhering to these normal forms, a database designer creates robust, efficient, and reliable database architectures free from data anomalies.