Functional dependencies and normalisation notes — Unit 4

Novice database designers often try to cram all related data into a single, massive table. For example, a single table storing `Student_ID`, `Student_Name`, `Course_ID`, `Course_Name`, and `Instructor`.

This poor design leads to massive data redundancy and catastrophic update problems known as Anomalies.

⇒1.1 The Three Anomalies

• Insertion Anomaly: We hire a new Instructor to teach a new Course. However, no student has registered for it yet. Because `Student_ID` is part of the primary key, we cannot insert the course into the database without a student (due to Entity Integrity). We are blocked from adding data.
• Deletion Anomaly: If a course only has ONE student enrolled, and that student decides to drop the class, we delete their row. Tragically, in doing so, we accidentally delete all information about the Course itself and the Instructor teaching it.
• Update Anomaly: The `Course_Name` for a specific `Course_ID` is repeated 500 times for the 500 students enrolled. If the university renames the course, the DBA must execute 500 updates. If one update fails due to a crash, the database becomes inconsistent (the same ID has two different names).

Normalization is the mathematical process of decomposing this bad table into smaller, perfect tables to eliminate these anomalies forever.

Before we can normalize a table, we must understand the mathematical relationships between its columns. This is defined by Functional Dependencies.

⇒2.1 The Formal Definition

A Functional Dependency $X \rightarrow Y$ (read as "X functionally determines Y") exists if and only if, whenever two tuples have the exact same value for attribute X, they MUST also have the exact same value for attribute Y.

For example: `Aadhar_Number` $\rightarrow$ `Name`. If two rows have the same Aadhar Number, they absolutely must belong to the exact same Name.

However, `Name` $\not\rightarrow$ `Aadhar_Number`, because two different people can be named "John Smith".

In database terms, if X is a Primary Key, then X functionally determines every other attribute in the entire table.

Armstrong's Axioms are a set of sound and complete mathematical inference rules used to discover new, hidden functional dependencies from a given starting set.

⇒3.1 Primary Axioms

• 1. Reflexivity: If Y is a subset of X, then $X \rightarrow Y$. (Trivial dependency. e.g., `{Name, Age}` $\rightarrow$ `Name`).
• 2. Augmentation: If $X \rightarrow Y$, then $XZ \rightarrow YZ$ for any attribute Z. (You can add the same attribute to both sides).
• 3. Transitivity: If $X \rightarrow Y$ and $Y \rightarrow Z$, then $X \rightarrow Z$. (The most critical rule for finding flaws in database design).

⇒3.2 Secondary Rules

• Union: If $X \rightarrow Y$ and $X \rightarrow Z$, then $X \rightarrow YZ$.
• Decomposition: If $X \rightarrow YZ$, then $X \rightarrow Y$ and $X \rightarrow Z$.
• Pseudo-transitivity: If $X \rightarrow Y$ and $WY \rightarrow Z$, then $WX \rightarrow Z$.

The Closure of a set of attributes X (denoted as $X^+$) is the complete set of all attributes that can be functionally determined by X using Armstrong's Axioms.

Calculating the closure is how we mathematically prove whether an attribute is a Candidate Key.

⇒4.1 Finding a Candidate Key

Algorithm:
1. Start with an attribute (e.g., $A$).
2. Add any attributes that A determines directly (e.g., if $A \rightarrow B$, then $A^+ = \{A, B\}$).
3. Look at the new attributes in the set. If $B \rightarrow C$, add C. ($A^+ = \{A, B, C\}$).
4. Repeat until the set stops growing.

The Golden Rule: If the closure of an attribute $X^+$ contains EVERY single attribute in the entire table, then X is a Super Key. If X is minimal, it is a Candidate Key.

Normalization is a systematic, step-by-step process of evaluating a database design against a series of strict mathematical tests (Normal Forms) to ensure it is free from anomalies and redundancy.

If a table fails a test, it must be Decomposed (split into two or more smaller tables).

⇒5.1 Properties of Decomposition

When splitting a table, two properties MUST be maintained:

• Lossless Join: After splitting Table R into R1 and R2, if we Natural Join R1 and R2 back together, we must get the exact original Table R, with no missing rows and no extra "spurious" ghost rows.
• Dependency Preservation: All original functional dependencies must be enforceable across the new split tables without requiring a join.

This is the absolute baseline. A table is not even considered a relational database table until it satisfies 1NF.

⇒6.1 The Rule

A relation is in 1NF if and only if every attribute is atomic.

You cannot have multi-valued attributes, composite attributes, or nested tables. Every cell must contain a single, indivisible value.

Violation Example: A `STUDENT` table where the `PhoneNumbers` column contains "555-1234, 555-9876".

The Fix: Create a separate `STUDENT_PHONE` table, or duplicate the student row for each phone number (which introduces redundancy, but satisfies 1NF).

To understand 2NF, we must define Prime and Non-Prime attributes.

• Prime Attribute: An attribute that is a part of ANY Candidate Key.
• Non-Prime Attribute: An attribute that is NOT part of any Candidate Key.

⇒7.1 The Rule

A relation is in 2NF if it is in 1NF AND it contains no Partial Dependencies.

A Partial Dependency occurs when a non-prime attribute is functionally determined by only a part of a composite Primary Key, rather than the whole key.

Violation Example: Table `ORDERS(OrderID, ProductID, Quantity, ProductName)`.
The Primary Key is `{OrderID, ProductID}`.
The non-prime attribute `ProductName` depends ONLY on `ProductID`, not the whole key. This is a partial dependency. If a product is ordered 100 times, the name is redundantly stored 100 times.

The Fix: Decompose. Remove `ProductName` into a new `PRODUCTS(ProductID, ProductName)` table.

3NF deals with relationships between non-prime attributes.

⇒8.1 The Rule

A relation is in 3NF if it is in 2NF AND it contains no Transitive Dependencies.

A Transitive Dependency occurs when a non-prime attribute determines another non-prime attribute. (e.g., $X \rightarrow Y$ and $Y \rightarrow Z$, where Y is not a candidate key).

Violation Example: Table `EMPLOYEE(EmpID, Name, DeptID, DeptName)`.
The Primary Key is `EmpID`.
`EmpID` $\rightarrow$ `DeptID` (Valid).
`DeptID` $\rightarrow$ `DeptName` (Transitive!).
The non-prime attribute `DeptName` relies on another non-prime attribute `DeptID`. This causes massive update anomalies if the Department changes its name.

The Fix: Decompose. Remove the offending columns into a new `DEPARTMENT(DeptID, DeptName)` table.

BCNF is a stricter, stronger version of 3NF. It handles rare edge cases where a table has overlapping candidate keys. It is often referred to as 3.5NF.

⇒9.1 The Rule

A relation is in BCNF if and only if, for every functional dependency $X \rightarrow Y$, $X$ is a Super Key.

In plain English: The left side of every arrow MUST be a unique identifier for the table. If a non-key attribute tries to determine a prime attribute, it violates BCNF.

Every table in BCNF is automatically in 3NF. However, a table in 3NF is not necessarily in BCNF.

Note on Decomposition: While converting to 3NF guarantees both Lossless Join and Dependency Preservation, converting a table to BCNF might force you to lose Dependency Preservation. It is a trade-off.

Unit 4 is entirely theoretical and mathematical. Expect heavy problem-solving questions.

⇒10.1 University Exam Checklist

• Explain Insertion, Deletion, and Update Anomalies with concrete examples.
• Define Functional Dependency ($X \rightarrow Y$).
• State Armstrong's Axioms (Reflexivity, Augmentation, Transitivity).
• Calculate the Attribute Closure ($X^+$) given a set of FDs, and use it to mathematically prove whether an attribute is a Candidate Key.
• Explain the concepts of Lossless Join Decomposition and Dependency Preservation.
• State the exact mathematical rules for 1NF, 2NF, 3NF, and BCNF.
• Given a poorly designed schema and a list of Functional Dependencies, normalize the schema step-by-step up to 3NF or BCNF, showing the decomposed tables at each stage.
• What is the difference between a Partial Dependency and a Transitive Dependency?