Functional Dependencies, Armstrong’s Axioms, and Normalization Basics

What is Normalization and Why Do We Need It? (In Simple Words)

When designing a database, beginners often make the mistake of dumping all data into one single giant table.

While this seems simple at first, storing unrelated information together introduces severe bugs known as Data Redundancy and Update Anomalies.

Normalization is a formal, step-by-step mathematical technique used to decompose bad, redundant tables into smaller, well-structured relations without losing any information (Lossless Decomposition).

1. The Three Update Anomalies

Consider an unnormalized table STUDENT_COURSE_FACULTY: [ Roll_No, Student_Name, Course_ID, Course_Name, Faculty_Name, Faculty_Room ]

If an unnormalized table stores student enrollments and faculty room details together, three severe anomalies occur:

Practical Examples of the Anomalies:

1. Insertion Anomaly: A new faculty member joins the college, but has not been assigned any students yet. Because Roll_No is part of the primary key and cannot be NULL, the college cannot insert the new faculty member into the database!
2. Deletion Anomaly: Student Roll_No 105 is the only student enrolled in “Cloud Computing”. If this student drops out and their record is deleted, the entire record of the Course and the Faculty teaching it is permanently lost from the college database!
3. Modification Anomaly: Faculty member “Dr. Sharma” moves from Room 101 to Room 205. If 500 students take Dr. Sharma’s course, the database must update 500 separate rows. If the server crashes after updating 300 rows, the database is left in a corrupted, inconsistent state!

2. Functional Dependency (FD)

A Functional Dependency (FD) is a constraint between two sets of attributes in a relation.

Formal Definition:

Given a relation R, an attribute Y is functionally dependent on attribute X (written as X → Y, read as “X functionally determines Y” or “Y is functionally dependent on X”), if and only if:

• Whenever two tuples have the same value for X, they MUST have the exact same value for Y.
• Here, X is called the Determinant and Y is called the Dependent.

Real-World Examples:

1. Roll_No → Student_Name: If two rows have the same Roll_No, they must have the same Student_Name (A roll number uniquely determines a student).
2. Aadhar_No → {Name, DOB, Address}: An Aadhar number uniquely identifies all personal details.
3. ISBN → Book_Title: A book’s ISBN uniquely determines its title.
4. {Course_ID, Semester} → Syllabus: A course ID and semester together determine the exact syllabus.

3. Types of Functional Dependencies

1. Trivial Functional Dependency:
   • An FD X → Y is trivial if Y is a subset of X (Y ⊆ X).
   • Example: {Roll_No, Name} → Roll_No (Always guaranteed to be true by definition!).
2. Non-Trivial Functional Dependency:
   • An FD X → Y is non-trivial if Y is not a subset of X (Y ⊄ X).
   • Example: Roll_No → Name.
3. Completely Non-Trivial FD:
   • X ∩ Y = ∅ (They share zero common attributes).
4. Full Functional Dependency:
   • Y depends on the entirety of composite key X, not on any of its proper subparts.
5. Partial Functional Dependency:
   • Y depends on only a portion of a composite primary key. (This violates 2NF!).
6. Transitive Functional Dependency:
   • If X → Y and Y → Z, then indirectly X → Z. (This violates 3NF!).

4. Armstrong’s Axioms (Inference Rules for FDs)

Formulated by William W. Armstrong in 1974, these axioms are the fundamental algebraic rules used to derive all possible functional dependencies from a given set of FDs:

The Primary Axioms:

1. Axiom of Reflexivity:
   • If Y ⊆ X, then X → Y.
   • Example: {Roll_No, Name} → Name.
2. Axiom of Augmentation:
   • If X → Y, then XZ → YZ for any attribute set Z.
   • Example: If Roll_No → Name, then {Roll_No, Dept_ID} → {Name, Dept_ID}.
3. Axiom of Transitivity:
   • If X → Y and Y → Z, then X → Z.
   • Example: If Roll_No → Dept_ID and Dept_ID → HOD_Name, then Roll_No → HOD_Name.

Secondary Derived Rules:

4. Union Rule: If X → Y and X → Z, then X → YZ.
5. Decomposition Rule: If X → YZ, then X → Y and X → Z.
6. Pseudo-Transitivity Rule: If X → Y and WY → Z, then WX → Z.

5. Attribute Closure and Finding Candidate Keys

The Attribute Closure of a set of attributes X (written as X⁺) is the set of all attributes that can be functionally determined by X using the given set of FDs.

Algorithm to Calculate Closure (X⁺):

1. Initialize X⁺ = X.
2. For every given FD A → B:
   • If A ⊆ X⁺, then add B to X⁺ (X⁺ = X⁺ ∪ B).
3. Repeat step 2 until no new attributes can be added.

Practical Exam Example:

Given Relation R(A, B, C, D, E) with FDs:

1. A → B
2. B → C
3. C → D
4. D → E

Find the closure of A (A⁺):

• Step 1: A⁺ = {A}
• Using A → B: A⁺ = {A, B}
• Using B → C: A⁺ = {A, B, C}
• Using C → D: A⁺ = {A, B, C, D}
• Using D → E: A⁺ = {A, B, C, D, E}

Since A⁺ contains every attribute of relation R, A is a Super Key (and because it is a single attribute, A is a Candidate Key)!

💡 DAVV Exam Preparation Tips

5-Mark Question: “What are the three update anomalies in DBMS? Explain with a short example.”

• Define Insertion, Deletion, and Modification anomalies.
• Use the combined Student-Course-Faculty table example to illustrate all three clearly.

10-Mark Question: “State and prove Armstrong’s Axioms for functional dependencies. How do you find the attribute closure and candidate keys of a relation? Solve with an example.”

• State the 3 primary rules (Reflexivity, Augmentation, Transitivity) and 3 derived rules (Union, Decomposition, Pseudo-transitivity).
• Write out the step-by-step Attribute Closure algorithm.
• Provide the numerical example showing A⁺ = {A, B, C, D, E} determining that A is the Candidate Key.