A · Compressed recap
Mixing facts determined by different attributes in one table causes redundancy and update, insertion, deletion anomalies. An FD X → Y means tuples agreeing on X agree on Y in every state; instances only disprove FDs. Trivial: Y ⊆ X. Armstrong's axioms (reflexivity, augmentation, transitivity) are sound and complete; derived: union, decomposition, pseudotransitivity; never split a left side or reverse.
Closure X⁺ answers membership (Y ⊆ X⁺) and superkeys (X⁺ = R). Keys: never-on-right attributes are in every key; only-on-right ones in none; grow from the must-have set. Prime = in some key. F ≡ G if each covers the other. Minimal cover: split RHS, remove extraneous LHS attributes, remove redundant FDs; not unique.
B · Merged rule card
4.1.1 Why normalize: redundancy and insertion/deletion/update anomalies
- Redundancy = one fact stored in many rows.
- Update anomaly: copies must all change. Insertion anomaly: a fact needs an unrelated fact (key part would be NULL). Deletion anomaly: deleting one fact loses others.
- Cause: one table mixes facts determined by different attribute sets.
- Fix: split so each table's facts depend on its own key, without creating spurious tuples.
4.2.1 FD definition; trivial vs non-trivial; checking whether an FD holds on an instance
- X → Y: tuples agreeing on X agree on Y, in every valid state.
- Instance check: group by X; any group with two Y-values → FD fails. Instances disprove, never prove.
- Trivial: Y ⊆ X; non-trivial: Y ⊄ X; completely non-trivial: X ∩ Y = ∅.
- Superkey K ⇔ K → R.
4.2.2 Armstrong's axioms and derived rules
- Axioms: reflexivity (Y ⊆ X ⇒ X → Y), augmentation (X → Y ⇒ XZ → YZ), transitivity.
- Sound and complete.
- Derived: union, decomposition, pseudotransitivity (X → Y, WY → Z ⇒ WX → Z), composition.
- Never: split the left side, reverse, cancel.
4.2.3 Attribute closure; all candidate keys; prime vs non-prime; counting superkeys
- X⁺: start with X; add R for each L → R with L ⊆ result; repeat until no change.
- F ⊨ X → Y ⇔ Y ⊆ X⁺; X superkey ⇔ X⁺ = R.
- Keys: never-on-right attributes are in every key; only-on-right attributes in none; grow from the must-have set, smallest first, skip supersets of found keys.
- Prime = in some candidate key; non-prime = in none.
- Count superkeys with inclusion–exclusion over the keys.
4.2.4 Closure of an FD set; membership test; equivalence of FD sets
- F⁺ = all FDs implied by F.
- Membership: X → Y ∈ F⁺ ⇔ Y ⊆ X⁺.
- G covers F ⇔ every FD of F is implied by G (closures under G).
- F ≡ G ⇔ each covers the other ⇔ F⁺ = G⁺.
- |F⁺| = Σ over X of 2^|X⁺|.
4.2.5 Minimal (canonical) cover
- Minimal cover: equivalent; single-attribute right sides; no extraneous left attributes; no redundant FDs.
- Steps: split RHS → remove extraneous LHS attributes (A ∈ X⁺ under current set) → remove redundant FDs (A ∈ X⁺ under the others).
- Not unique; canonical cover groups same left sides.
C · Interleaved GATE-style questions
Q1 · MCQ · 1 mark(s) — Anomalies
A table stores (supplier, city, part, qty) with key (supplier, part). A supplier with no parts cannot be stored. This is:
- (A) an update anomaly
- (B) an insertion anomaly
- (C) a deletion anomaly
- (D) not an anomaly
Q2 · MSQ · 2 mark(s) — Instance
Instance of R(X, Y, Z): (1, a, p), (2, a, p), (1, b, p), (3, c, q). Which FDs hold in this instance?
- (A) Z → Y
- (B) X → Y
- (C) Y → Z
- (D) XY → Z
Q3 · MCQ · 1 mark(s) — Axioms
From A → B alone, which can be derived?
- (A) AC → BC
- (B) A → BC
- (C) C → B
- (D) B → A
Q4 · NAT · 2 mark(s) — Keys
R(A, B, C, D, E, F, G, H), F = {AB → C, A → DE, B → F, F → GH}. How many superkeys?
Numerical answer: ________
Q5 · NAT · 2 mark(s) — Keys
R(A, B, C, D, E), F = {A → B, B → A, C → D, D → C}. How many candidate keys?
Numerical answer: ________
Q6 · MCQ · 2 mark(s) — Equivalence
F = {A → B, C → D}, G = {A → B, C → D, AC → BD}. Then:
- (A) G implies more than F
- (B) neither covers the other
- (C) F implies more than G
- (D) F ≡ G
Q7 · NAT · 2 mark(s) — Minimal cover
How many FDs are in a minimal cover of {A → BC, B → C, C → A}?
Numerical answer: ________
Q8 · MCQ · 1 mark(s) — Closure
R(A, B, C, D), F = {A → B, B → C, C → D}. Which is not a superkey?
- (A) A
- (B) AB
- (C) BCD
- (D) AD
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: (B) · 1 mark(s)
Key would be incomplete.
- (A) is wrong: No.
- (C) is wrong: No.
- (D) is wrong: It is.
Re-read: Lesson 4.1.1 — Why normalize: redundancy and insertion/deletion/update anomalies
Q2 Answer: (C) (D) · 2 mark(s)
X = 1 has Y values a and b; Y → Z holds; Z = p has Y values a, b; XY pairs are all distinct.
- (A) is wrong: Z = p gives a and b.
- (B) is wrong: X = 1 gives a and b.
Re-read: Lesson 4.2.1 — FD definition; trivial vs non-trivial; checking whether an FD holds on an instance
Q3 Answer: (A) · 1 mark(s)
Augmentation.
- (B) is wrong: C is not determined.
- (C) is wrong: Unrelated.
- (D) is wrong: No reversal.
Re-read: Lesson 4.2.2 — Armstrong's axioms and derived rules
Q4 Answer: 64 · 2 mark(s)
Only key AB (A, B never on the right; AB⁺ = everything). 2⁸⁻² = 64.
Re-read: Lesson 4.2.3 — Attribute closure; all candidate keys; prime vs non-prime; counting superkeys
Q5 Answer: 4 · 2 mark(s)
E is never on the right. Need one of A, B and one of C, D: ACE, ADE, BCE, BDE.
Re-read: Lesson 4.2.3 — Attribute closure; all candidate keys; prime vs non-prime; counting superkeys
Q6 Answer: (D) · 2 mark(s)
AC → BD follows from F (composition).
- (A) is wrong: AC → BD is implied by F.
- (B) is wrong: Both cover each other.
- (C) is wrong: G contains F.
Re-read: Lesson 4.2.4 — Closure of an FD set; membership test; equivalence of FD sets
Q7 Answer: 3 · 2 mark(s)
Split: A → B, A → C, B → C, C → A. A → C is redundant (A → B → C). Result {A → B, B → C, C → A}.
Re-read: Lesson 4.2.5 — Minimal (canonical) cover
Q8 Answer: (C) · 1 mark(s)
BCD⁺ = BCD: A is missing.
- (A) is wrong: A⁺ = ABCD.
- (B) is wrong: Contains A.
- (D) is wrong: Contains A.
Re-read: Lesson 4.2.3 — Attribute closure; all candidate keys; prime vs non-prime; counting superkeys