Functional Dependencies, Candidate Keys & Normal Forms (1NF to BCNF)
“Armstrong axioms, attribute closures, 1NF to BCNF testing, and lossless decomposition.”
1.The Quest for Redundancy-Free Schema Design
§ 5.1.Poorly designed database schemas suffer from three catastrophic anomalies: Insertion Anomaly (cannot record a department without hiring an employee), Deletion Anomaly (deleting the last student in a course erases the course record), and Update Anomaly (changing an address requires updating 10,000 duplicate rows).
Normalization is the formal mathematical decomposition of relations to eliminate redundant storage without losing information. It relies on Functional Dependencies (FDs): constraints asserting that knowing the value of attribute set X uniquely determines the value of attribute set Y (X → Y).
2.Armstrong's Axioms & Attribute Closure
§ 5.2.Armstrong's 3 Primary Axioms (Sound and Complete):
1. Reflexivity: If Y ⊆ X, then X → Y (e.g., AB → A).
2. Augmentation: If X → Y, then XZ → YZ for any Z.
3. Transitivity: If X → Y and Y → Z, then X → Z.
Secondary Derived Rules:
• Union: If X → Y and X → Z, then X → YZ.
• Decomposition: If X → YZ, then X → Y and X → Z.
• Pseudotransitivity: If X → Y and WY → Z, then WX → Z.
The Attribute Closure Algorithm (X+):
To find all attributes determined by set X under dependencies F, initialize Closure = X. Repeatedly add RHS of any FD whose LHS is inside Closure until Closure stops expanding. If X+ equals all attributes of R, then X is a Superkey!
3. Interactive Normalization & Candidate Key Engine
Experiment with relations and functional dependencies. Click attributes to compute their live attribute closure, derive all minimal candidate keys, and check 1NF, 2NF, 3NF, and BCNF compliance.
Functional Dependency & Normal Form Evaluator
Compute attribute closures and test 1NF, 2NF, 3NF, and BCNF conditions.
Attribute Closure Calculator (X+)
Click attributes to compute their transitive functional reach under F:
Derived Candidate Keys (3)
A candidate key is a minimal superkey. Notice that no proper subset of these keys can determine all attributes.
Attribute Taxonomy
Normal Form Breakdown per Dependency
| FD | LHS is Superkey? | RHS is Prime? | 2NF Status | 3NF Status | BCNF Status |
|---|---|---|---|---|---|
| AB → C | Yes | Yes | Pass | Pass | Pass |
| C → D | No | Yes | Pass | Pass | Violates |
| D → A | No | Yes | Pass | Pass | Violates |
4.The Normal Form Hierarchy: 1NF → 2NF → 3NF → BCNF
§ 5.4.Every normal form is strictly stricter than the one before it: BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF.
1. First Normal Form (1NF): Every attribute value must be atomic (no arrays, lists, sets, or nested relations).
2. Second Normal Form (2NF): Relation is in 1NF AND no non-prime attribute is partially dependent on any candidate key. (Violation: If candidate key is AB, and A → C where C is non-prime).
3. Third Normal Form (3NF): Relation is in 2NF AND for every non-trivial FD X → Y, either X is a Superkey OR Y is a Prime Attribute. 3NF guarantees both Lossless Join AND Dependency Preservation!
4. Boyce-Codd Normal Form (BCNF): For every non-trivial FD X → Y, X must strictly be a Superkey. BCNF eliminates all FD redundancy, but some schemas cannot achieve BCNF without losing dependency preservation!
5. GATE Classic: Counting Superkeys from Candidate Keys
| Total Attributes n5 (A, B, C, D, E) | Candidate Key Size k2 (Attributes A and B) |
A superkey is any superset of a candidate key. Therefore, every superkey must contain both attributes A and B.
The remaining attributes {C, D, E} can either be included or excluded from the superkey. There are n - k = 5 - 2 = 3 independent choices.
2^(5 - 2) = 2^3 = 8 superkeys: {AB, ABC, ABD, ABE, ABCD, ABCE, ABDE, ABCDE}.
6. Normalization Concept Verification
Solve high-frequency GATE normalization problems.
Relation R(A, B, C, D) has FDs: {A → B, B → C, C → D}. What is the candidate key and the highest normal form of R?
7. 1-Minute Normalization Revision Anchors
“2NF = No Partial Dependency; 3NF = LHS Superkey OR RHS Prime; BCNF = LHS must be Superkey.”
- •Superkey count with single key size k: 2^(n - k).
- •Lossless condition: (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2.
- •3NF always guarantees dependency preservation; BCNF may lose dependencies.
- •Attributes that never appear on the RHS of any FD MUST be in every candidate key.
- •A partial dependency only exists when a PROPER SUBSET of a key determines a non-prime attribute.
- •If all candidate keys are single attributes, 2NF is automatically satisfied!
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Foundational paper formalizing functional dependencies and relational decomposition.
Canonical reference for minimal cover and lossless decomposition algorithms.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused numerical problem-solving with clear worked examples.
Fast conceptual coverage with step-by-step GATE numericals.
Systematic textbook-style explanations ideal for first-time learners.
Deep theoretical rigor on normalization and transaction serializability.