Closure of an FD set; membership test; equivalence of FD sets

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What is A⁺ under {A → C, C → D, B → E}? from Lesson 4.2.3
2. Which axiom lets you add the same attributes to both sides of an FD? from Lesson 4.2.2
3. What is a trivial FD? from Lesson 4.2.1

1 · The Hook

Two designers write the FDs of the same table differently. One writes {A → B, B → C, A → C}; the other writes {A → B, B → C}. Do they mean the same thing? And is AB → C "in" their FDs, even though neither wrote it? This lesson defines the closure of a whole FD set and the two tests built on it: membership and equivalence.

2 · Predict First

F = {A → B, B → C}. Is A → C in F⁺? Is G = {A → BC, B → C} equivalent to F?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

A⁺ under F = ABC, so A → C ∈ F⁺. G implies A → B and B → C (decompose A → BC); F implies A → BC (A⁺ = ABC) and B → C. Each covers the other: equivalent.

Closure of an FD set: F⁺

F⁺ is the set of all FDs implied by F, trivial ones included. It is usually huge (it contains every X → Y with Y ⊆ X⁺), so we never list it; we test membership.

Membership test

X → Y ∈ F⁺ iff Y ⊆ X⁺ (closure computed under F). One closure per question.

Cover and equivalence

• G covers F (F ⊆ G⁺) if every FD of F is implied by G: for each X → Y in F, Y ⊆ X⁺ computed under G.
• F and G are equivalent (F ≡ G, F⁺ = G⁺) if F covers G and G covers F.

Procedure:

1. For each FD in F, compute its left side's closure under G; check the right side is inside.
2. For each FD in G, compute its left side's closure under F; check.
3. Equivalent only if both directions pass.

Example

F = {A → B, AB → C, D → AC}, G = {A → BC, D → AB}.

• F's FDs under G: A⁺ = ABC ⊇ B ✓; AB⁺ = ABC ⊇ C ✓; D⁺ = DABC ⊇ AC ✓. G covers F.
• G's FDs under F: A⁺ = ABC ⊇ BC ✓; D⁺ = DACB ⊇ AB ✓. F covers G.
• Equivalent.

How many FDs are in F⁺? (rarely asked)

For each left side X there are 2^|X⁺| FDs X → Y (any Y ⊆ X⁺). Summing over all 2ⁿ left sides gives |F⁺|. With R(A, B) and F = {A → B}: ∅ → ∅ (1), A → {∅, A, B, AB} (4), B → {∅, B} (2), AB → 4 subsets (4): 11 FDs, including trivial ones.

4 · Visual

Equivalence test   F = {A->B, AB->C, D->AC}    G = {A->BC, D->AB}

  F's FD     closure of left side under G    contains right side?
  A  -> B    A+  = ABC                       yes
  AB -> C    AB+ = ABC                       yes
  D  -> AC   D+  = ABCD                      yes        => G covers F

  G's FD     closure under F
  A  -> BC   A+  = ABC                       yes
  D  -> AB   D+  = ABCD                      yes        => F covers G     => F ≡ G

5 · Worked Examples

Example 1 Easy

F = {A → B, B → C, C → D}. Is AD → BC in F⁺? Is D → A?

Solution

AD⁺ = ABCD ⊇ BC: yes. D⁺ = D: no.

Example 2 Medium

F = {A → B, B → C}, G = {A → B, A → C}. Equivalent?

Solution

G under F: both implied (A⁺ = ABC). F under G: B → C? B⁺ under G = B: not implied. Not equivalent: F covers G, but G does not cover F.

Example 3 GATE

F = {A → C, AC → D, E → AD, E → H}, G = {A → CD, E → AH}. Is F ≡ G?

Solution

F under G: A⁺ = ACD ⊇ C ✓; AC⁺ = ACD ⊇ D ✓; E⁺ = EAHCD ⊇ AD ✓, ⊇ H ✓. G under F: A⁺ = ACD ⊇ CD ✓; E⁺ = EADHC ⊇ AH ✓. Equivalent.

8 · Connect the Dots

Lesson 4.2.3 computed closures of attribute sets; this lesson used them to test FD membership and equivalence. Next: the smallest equivalent FD set, the minimal cover, which the 3NF algorithm needs as its input.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Membership

F = {A → B, BC → D}. Which is in F⁺?

1. (A) AC → D
2. (B) B → D
3. (C) A → D
4. (D) D → A

Q2 · MCQ · 2 mark(s) — Equivalence

F = {A → B, B → C, C → A}, G = {A → BC, B → A, C → A}. Is F ≡ G?

1. (A) No: G does not imply C → A
2. (B) No: G does not imply B → C
3. (C) Yes
4. (D) No: F does not imply A → BC

Q3 · MSQ · 2 mark(s) — Coverage

F = {AB → C, C → D}, G = {AB → CD}. Which are true?

1. (A) C → D ∈ G⁺
2. (B) G covers F
3. (C) F ≡ G
4. (D) F covers G

Q4 · NAT · 2 mark(s) — Closure size

R(A, B) with F = {A → B}. How many FDs (including trivial ones) are in F⁺?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Definition

F ≡ G means:

1. (A) F ⊆ G
2. (B) |F| = |G|
3. (C) F = G as sets
4. (D) F⁺ = G⁺

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

closure of an FD set F⁺membership testcover (G covers F)equivalence of FD sets