A · Compressed recap
A decomposition splits R into pieces with the projected data. Lossless: joining the projections gives back r exactly (no spurious tuples). Two pieces: lossless ⇔ (R₁ ∩ R₂)⁺ ⊇ R₁ or ⊇ R₂; empty intersection → lossy. Several pieces: chase with a/b symbols; lossless ⇔ some row becomes all a's.
Dependency preserving: the FDs projected (from F⁺) onto the pieces imply all of F. Quick check: each FD inside a piece; otherwise run the piecewise closure (result ∪= (result ∩ Rᵢ)⁺ ∩ Rᵢ). Lossless and preserving are independent; lossless is mandatory.
B · Merged rule card
4.3.1 Lossless-join decomposition: binary test and chase (table) method
- Lossless (non-additive): ⋈ of projections = r for every legal r (no spurious tuples).
- Binary: lossless ⇔ (R₁ ∩ R₂)⁺ ⊇ R₁ or ⊇ R₂. Empty intersection → lossy.
- Chase: rows = pieces, a's for owned attributes, apply FDs to equate; lossless ⇔ some row all a's.
- A lossless split of a lossless piece keeps the whole decomposition lossless.
4.3.2 Dependency preservation
- Fᵢ = FDs of F⁺ within Rᵢ. Preserving ⇔ (∪ Fᵢ)⁺ = F⁺.
- Quick: every FD inside some piece → preserving.
- Test X → Y: result = X; repeat result ∪= ((result ∩ Rᵢ)⁺ ∩ Rᵢ) over pieces; preserved ⇔ Y ⊆ result.
- Lossless and preserving are independent; lossless mandatory, preserving desirable.
C · Interleaved GATE-style questions
Q1 · MCQ · 1 mark(s) — Lossless
R(A, B, C, D), F = {B → D}. Which decomposition is lossless?
- (A) {ABC, BD}
- (B) {AB, CD}
- (C) {ABD, CD}
- (D) {AC, BD}
Q2 · NAT · 1 mark(s) — Spurious
R(A, B) holds (1, 5), (2, 5), (3, 5). It is decomposed into R1(A) and R2(B). How many spurious tuples does R1 × R2 contain?
Numerical answer: ________
Q3 · MCQ · 2 mark(s) — Chase
R(A, B, C, D, E), F = {A → BC, C → D, D → E}, decomposed into {ABC, CD, DE}. It is:
- (A) lossy, since DE does not contain A
- (B) lossy, since three pieces need a common attribute
- (C) lossless only if E → A
- (D) lossless
Q4 · MCQ · 2 mark(s) — Preservation
R(A, B, C, D), F = {AB → C, C → D}, pieces {ABC, CD}. Preserving?
- (A) Yes
- (B) No, C → D is lost
- (C) No, AB → C is lost
- (D) Only if lossless
Q5 · MSQ · 2 mark(s) — Both
R(A, B, C), F = {AB → C, C → B}. Which decompositions are lossless?
- (A) {AC, BC}
- (B) {AB, BC}
- (C) {AB, AC}
- (D) {ABC}
Q6 · MCQ · 1 mark(s) — Independence
Which is possible?
- (A) Neither
- (B) Lossy and dependency preserving
- (C) Both A and B
- (D) Lossless and not preserving
Q7 · NAT · 2 mark(s) — Test
R(A, B, C, D), F = {A → B, B → C, C → D, D → A}, pieces {AB, BC, CD}. How many of the 4 FDs are preserved?
Numerical answer: ________
Q8 · MCQ · 1 mark(s) — Binary
For {R₁, R₂} to be lossless, R₁ ∩ R₂ must be:
- (A) empty
- (B) a single attribute
- (C) a key of R
- (D) a superkey of R₁ or of R₂
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: (A) · 1 mark(s)
Common B, B⁺ = BD ⊇ BD.
- (B) is wrong: Common ∅.
- (C) is wrong: Common D, D⁺ = D.
- (D) is wrong: Common ∅.
Re-read: Lesson 4.3.1 — Lossless-join decomposition: binary test and chase (table) method
Q2 Answer: 0 · 1 mark(s)
R1 × R2 = {1, 2, 3} × {5} = exactly the original 3 tuples.
Re-read: Lesson 4.3.1 — Lossless-join decomposition: binary test and chase (table) method
Q3 Answer: (D) · 2 mark(s)
Chase: row ABC gets D (C → D) and E (D → E).
- (A) is wrong: Not required.
- (B) is wrong: Not required.
- (C) is wrong: Not needed.
Re-read: Lesson 4.3.1 — Lossless-join decomposition: binary test and chase (table) method
Q4 Answer: (A) · 2 mark(s)
Both FDs lie inside pieces.
- (B) is wrong: Inside CD.
- (C) is wrong: Inside ABC.
- (D) is wrong: Independent property.
Re-read: Lesson 4.3.2 — Dependency preservation
Q5 Answer: (A) (D) · 2 mark(s)
A: common C → B, so C → BC. B: common B, B⁺ = B. C: common A, A⁺ = A. D: no split.
- (B) is wrong: B⁺ = B.
- (C) is wrong: A⁺ = A.
Re-read: Lesson 4.3.2 — Dependency preservation
Q6 Answer: (C) · 1 mark(s)
The properties are independent.
- (A) is wrong: Both happen.
- (B) is wrong: Also B.
- (D) is wrong: Also A.
Re-read: Lesson 4.3.2 — Dependency preservation
Q7 Answer: 4 · 2 mark(s)
Three lie in pieces; D → A is preserved through D → C → B → A.
Re-read: Lesson 4.3.2 — Dependency preservation
Q8 Answer: (D) · 1 mark(s)
The binary test.
- (A) is wrong: Empty means lossy.
- (B) is wrong: Not required.
- (C) is wrong: Not required.
Re-read: Lesson 4.3.1 — Lossless-join decomposition: binary test and chase (table) method