Functional Dependencies (Part 1)

Data Anomalies

• Primary key of the table: $(NRIC, PhoneNumber)$, a composite key
• Anomalies arise due to a bad combination of attributes and redundancy
• Types of anomalies demonstrated:
  • Redundancy: the same address value appears in multiple rows
  • Update anomaly: updating one address row leaves another unchanged
  • Deletion anomaly: deleting a row may remove needed information about another attribute
  • Insertion anomaly: cannot insert a new person if the primary-key constraint would require NULL values
• Example table (Name, NRIC, PhoneNumber, HomeAddress):
  • Alice | 1234 | 67899876 | Jurong East
  • Alice | 1234 | 83848384 | Jurong East
  • Bob | 5678 | 98765432 | Pasir Ris
  • This illustrates that multiple rows share the same person (Alice) but different phone numbers

Normalization

• Goal: remove anomalies by decomposing the table into smaller, well-structured relations
• Decomposition example from the slide:
  • Original relation: (Name, NRIC, PhoneNumber, HomeAddress)
  • Decomposed into two relations:
  • R1(Name, NRIC, HomeAddress)
  • R2(NRIC, PhoneNumber)
• Resulting data:
  • R1 tuples:
  • (Alice, 1234, Jurong East)
  • (Bob, 5678, Pasir Ris)
  • R2 tuples:
  • (1234, 67899876)
  • (1234, 83848384)
  • (5678, 98765432)
• Effects of normalization:
  • Duplication is reduced (e.g., Alice’s address no longer duplicated)
  • Update anomalies eliminated (address stored in one place per NRIC)
  • Deletion anomalies eliminated (Bob’s phone can be removed without losing other data)
  • Insertion anomalies eliminated (you can insert an individual without a phone number)
• Final normalized design examples from the slide:
  • Name NRIC HomeAddress
  • Alice | 1234 | Jurong East
  • Bob | 5678 | Pasir Ris
  • NRIC PhoneNumber
  • 1234 | 67899876
  • 1234 | 83848384
  • 5678 | 98765432

This Lecture: Functional Dependencies (FD) and Armstrong's Axioms

• Topics covered in this lecture:
  • Data anomalies
  • Functional dependencies (FDs)
  • Armstrong's axioms for FD reasoning

Functional Dependencies (FD): Intuition and Examples

• Intuition: to understand why certain attribute values correlate, causing anomalies
• Example with two attributes: NRIC and Name
  • From real-world knowledge: NRIC uniquely identifies a person, so $NRIC \to Name$ holds
  • Conversely, multiple people can share the same name, so $Name \not\to NRIC$ in general
  • Thus: $NRIC \to Name$, but not $Name \to NRIC$
• Example with three attributes: StudentID, Name, Address, PostalCode
  • FD: $StudentID \to Name, Address, PostalCode$
  • Also, $Address \to PostalCode$

Formal Definition of FD

• For attribute sets $A<em>1, A</em>2, …, A<em>m$ and $B</em>1, B<em>2, …, B</em>n$:
  • $A<em>1A</em>2\ldots A<em>m \to B</em>1B<em>2\ldots B</em>n$
  • Meaning: there do not exist two tuples that have the same values on $A<em>1, A</em>2, \ldots, A<em>m$ but different values on $B</em>1, B<em>2, \ldots, B</em>n$
• Example: NRIC $\to$ Name expresses that no two persons with the same NRIC have different names

FD Examples (from the slides)

• Example FD set in a sample table:
  • $Category \to Department$
  • $Category, Color \to Price$
  • $Price \to Color$
  • $Name \to Color$
  • $Department, Category \to Name$
  • $Color, Department \to Name, Price$
• Sample data (Name, Category, Color, Department, Price):
  • Gizmo | Gadget | Green | Toys | 49
  • Tweaker | Gadget | Black | Toys | 99
  • Gizmo | Stationary | Green | Office Supplies | 59

Where Do FDs Come From?

• FD sources:
  • Common sense and knowledge about the real world
  • Application requirements and constraints
• Purchase example: Purchase(CustomerID, ProductID, ShopID, Price, Date)
  • FD: ShopID $\to$ ProductID (no shop sells more than one product)
  • FD: ProductID $\to$ CustomerID (no two customers buy the same product)
  • FD: $(CustomerID, ProductID, ShopID, Date) \to$ Price (no shop sells the same product to the same customer on the same date at two different prices)
• Notation for composite determinants: $ext{CustomerID, ProductID, ShopID, Date} \to \text{Price}$

Roadmap: Using FDs to Decide If a Table is Good

• Plan:
  • Understand basic concepts (FDs)
  • Learn how to reason with FDs
  • Apply to normalization to build good designs
• The goal is to decide whether tables are good or need normalization based on FD reasoning

Reasoning with FDs

• Goal: derive new FDs from given ones using rules
• Example: Given $NRIC \to Address$ and $Address \to PostalCode$, we can deduce $NRIC \to PostalCode$
• Why derivations matter: helps decide whether a table is "bad" or "good" by revealing hidden FDs
• Armstrong's Axioms provide a sound basis for FD reasoning (see next section)

Armstrong’s Axioms (the three basic rules)

• Axiom of Reflexivity: If $B \subseteq A$ then $A \to B$
  • Examples:
  • $NRIC, Name \to NRIC$
  • $StudentID, Name, Age \to Name, Age$
  • $ABCD \to ABC$
• Axiom of Augmentation: If $A \to B$ then $AC \to BC$ for any $C$
  • Examples:
  • If $NRIC \to Name$, then $NRIC, Age \to Name, Age$
  • If $NRIC, Salary, Weight \to Name, Salary, Weight$, then with $Addr$, $NRIC, Salary, Weight, Addr \to Name, Salary, Weight, Addr$
• Axiom of Transitivity: If $A \to B$ and $B \to C$ then $A \to C$
  • Example: If $NRIC \to Addr$ and $Addr \to PostalCode$, then $NRIC \to PostalCode$

Reasoning with FD: Derivation Patterns

• Given $A\to B$ and $BC\to D$, prove $AC\to D$:
  • Augmentation: $AC\to BC$
  • Transitivity: from $AC\to BC$ and $BC\to D$ derive $AC\to D$
• Given $A\to B$ and $D\to C$, prove $AD\to BC$:
  • Augmentation: $AD\to BD$
  • From $AD\to BD$ and reflexivity (since $B$ subset of $BD$) get $AD\to B$
  • From $D\to C$ and augmentation get $AD\to AC$
  • From $AD\to AC$ and reflexivity get $AD\to C$
  • Combine $AD\to B$ and $AD\to C$ to obtain $AD\to BC$
• Given $A\to C$, $AC\to D$, $AD\to B$, prove $A\to B$:
  • $A\to C$; Augment to $A\to AC$
  • With $AC\to D$, by Transitivity get $A\to D$
  • Augment to $A\to AD$; With $AD\to B$, by Transitivity get $A\to B$

An Intuitive, Stepwise FD Reasoning (closure approach)

• For 4 attributes $A,B,C,D$ with $B\to D$, $DB\to A$, $AD\to C$:
  • Start with the activated set: ${B}$
  • Apply $B\to D$: ${B, D}$
  • Apply $DB\to A$: ${B, D, A}$
  • Apply $AD\to C$: ${B, D, A, C}$
  • Conclude $B \to C$ (since $C$ is in the closure)

Exercises: Derivation Practice with FDs

• Exercise 1: Given $A \to C, C \to B, B \to D, D \to E, E \to A$, prove $C \to ABE$
  • Start with ${C}$; apply chain: $C\to B$ → {C,B}; $B\to D$ → {C,B,D}; $D\to E$ → {C,B,D,E}; $E\to A$ → {C,B,D,E,A}
  • Thus $A$, $B$, and $E$ are all in the closure, so $C \to ABE$ holds
• Exercise 2: Given $C \to D, AD \to E, BC \to E, E \to A, D \to B$, prove $C \to A$
  • Start with ${C}$; $C\to D$ → {C,D}; $D\to B$ → {C,D,B}; $BC \to E$ with $B$ and $C$ → {C,D,B,E}; $E \to A$ → {C,D,B,E,A}; hence $C \to A$
• Exercise 3: Given $C \to D, AD \to E, BC \to E, E \to A, D \to B, B \to F$, prove $D \to C$
  • Start with ${D}$; $D\to B$ → {D,B}; $B\to F$ → {D,B,F}
  • No further derivations yield $C$; thus the given set does not imply $D \to C$ (closure of $D$ is ${D,B,F}$)

Continuation

• This content leads to Topic 2: Functional Dependencies (2) which continues the discussion on FDs and normalization

Practical and Ethical/Policy Notes

• Copyright and usage: Course materials are for NTU students for educational purposes only; redistribution or reproduction without permission is prohibited. Follow institutional guidelines to avoid disciplinary or legal action.
• Practical takeaway: Understanding FDs and Armstrong's axioms is essential for deciding when a table design is prone to anomalies and how to decompose it to achieve normalization and data integrity