CS2855 Normalisation

CS2855 Database Normalization Revision Notes

1. Functional Dependencies (FDs)

• Definition: A FD 𝛼 → 𝛽 asserts that if two tuples agree on 𝛼, they must agree on 𝛽.
• Armstrong’s Axioms:
  1. Reflexivity: If 𝛽 ⊆ 𝛼, then 𝛼 → 𝛽 (e.g., AB → A).
  2. Augmentation: If 𝛼 → 𝛽, then 𝛾𝛼 → 𝛾𝛽 (e.g., A → C ⟹ AB → BC).
  3. Transitivity: If 𝛼 → 𝛽 and 𝛽 → 𝛾, then 𝛼 → 𝛾.

2. Closure of FDs

• Closure (F⁺): All FDs logically implied by a set F.
• Attribute Closure (𝛼⁺): Set of attributes determined by 𝛼 using F.
• Algorithm to Compute 𝛼⁺:

Initialize result = 𝛼
Repeat:
For each FD 𝛽 → 𝛾 in F:
If 𝛽 ⊆ result, add 𝛾 to result
Until no more changes
Return result

3. Redundant Attributes & Canonical Cover

• Redundant Attribute: An attribute in an FD that can be removed without changing F⁺.
• Example: Given F = {A → C, AB → CD}, C is redundant in AB → CD because {A → C, AB → D} ⟹ AB → CD.
• Canonical Cover:

1. Decompose FDs to single RHS (e.g., A → BC becomes A → B, A → C).
2. Remove redundant LHS attributes (e.g., ABC → D becomes AB → D if C is redundant).
3. Eliminate redundant FDs (e.g., if A → B is implied by other FDs).

4. Decomposition

• Lossless Decomposition: Original relation can be recovered by a natural join of sub-relations.
• Check Lossless:
  • If (R1 ∩ R2) is a superkey for R1 or R2.
• Dependency Preservation: All FDs in F⁺ can be checked in the decomposed relations.

5. Normal Forms

a) First Normal Form (1NF)

• All attributes are atomic (no multi-valued/composite attributes).

b) Boyce-Codd Normal Form (BCNF)

• Definition: For every non-trivial FD 𝛼 → 𝛽 in F⁺, 𝛼 is a superkey.
• Decomposition Algorithm:
• Find a violating FD 𝛼 → 𝛽 (where 𝛼 is not a superkey).
• Decompose into (𝛼 ∪ 𝛽) and (R – 𝛽).
• Repeat until all relations are in BCNF.

c) Third Normal Form (3NF)

• Definition: For every non-trivial FD 𝛼 → 𝛽 in F⁺:
• 𝛼 is a superkey, OR
• 𝛽 is a prime attribute (part of a candidate key).
• Advantage: Always preserves dependencies.

BCNF vs 3NF

• BCNF eliminates all redundancy but may lose dependencies.
• 3NF compromises to preserve dependencies.

---

Past Paper Question Types & Solutions

Type 1: Identify Normal Form

Steps:

1. List all FDs.
2. Find candidate keys.
3. For each FD, check:

• BCNF: If 𝛼 is a superkey.
• 3NF: If 𝛽 is prime or 𝛼 is a superkey.

Example (CS2855-22):
Given R(A,B,C,D) with FDs AB → C, C → D:

• Candidate keys: AB (determines C and D via FDs).
• Violating FD: C → D (C is not a superkey).
• Not in BCNF (C is not a superkey) but satisfies 3NF (D is prime? No → Check if D is prime).

Type 2: Decompose into BCNF/3NF

Example:
Decompose R(A,B,C,D) with FDs AB → C, C → D into BCNF.

1. Find violating FD: C → D (C is not a superkey).
2. Decompose:

• R1 = (C,D)
• R2 = (A,B,C)

3. Check: R1 is in BCNF (key = C), R2 (key = AB → C, satisfies BCNF).

Type 3: Check Lossless Join

Example:
Decomposition R1(A,B), R2(B,C) where B → A.

• R1 ∩ R2 = B.
• B is a key for R1 (B → A).
• Lossless as B is a key in R1.

---

Important Notes

• E-R to Relational Model: Translate entities to tables, relationships to foreign keys.
• SQL Queries:
• GROUP BY is used with aggregate functions (SUM, AVG).
• HAVING filters groups; WHERE filters rows.
• Example:

  SELECT dept, AVG(salary) 
  FROM employees 
  WHERE age > 30 
  GROUP BY dept 
  HAVING AVG(salary) > 50000;

• Transaction ACID: Ensure atomicity, consistency, isolation, durability.