Attribute closure; all candidate keys; prime vs non-prime; counting superkeys

0 · Recall Warm-up

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

1. Does AB → C imply A → C? from Lesson 4.2.2
2. R has candidate keys {A} and {B} and 4 attributes. How many superkeys? from Lesson 2.2.1
3. When is K a superkey in FD terms? from Lesson 4.2.1

1 · The Hook

"R(A, B, C, D, E) with F = {A → B, B → C, CD → E}. Find all candidate keys." This is probably the single most frequent normalisation question in GATE, and it feeds every normal-form question. One algorithm, the closure X⁺, solves it in a minute.

2 · Predict First

With F = {A → B, B → C, CD → E}, what does A determine? What does AD determine?

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

3 · Core Concept

Predict First — the answer

A → B → C, so A⁺ = ABC. AD: A gives B, C; then CD → E: AD⁺ = ABCDE, everything. So AD is a superkey.

Attribute closure X⁺

X⁺ = the set of all attributes that X determines under F.

Algorithm:

1. Start: result = X.
2. Repeat: for each FD L → R in F, if L ⊆ result, add R to result.
3. Stop when a full pass adds nothing.

F implies X → Y exactly when Y ⊆ X⁺. X is a superkey exactly when X⁺ = all attributes of R.

Finding all candidate keys

1. Must-have attributes: attributes that never appear on any right side must be in every key (nothing can determine them). Call this set M.
2. Never-in-key attributes: attributes that appear only on right sides (never on a left side) are determined by others and are in no key (unless needed... they never are, because some left side determines them).
3. Compute M⁺. If it is everything, M is the only candidate key.
4. Otherwise add attributes from the remaining "both sides" group, smallest combinations first: M + 1 attribute, then M + 2, … Keep a set if its closure is everything and it contains no key already found.

Example 1

R(A, B, C, D, E), F = {A → B, B → C, CD → E}. Right sides: B, C, E. Never on the right: A, D → M = AD. AD⁺ = ABCDE. Only key: AD.

Example 2

R(A, B, C, D), F = {AB → C, C → D, D → A}. Right sides: C, D, A. Never on the right: B. B⁺ = B. Try B + one: AB⁺ = ABCD ✓, BC⁺ = BCDA ✓, BD⁺ = BDAC ✓. Keys: AB, BC, BD.

Example 3

R(A, B, C, D, E, F), F = {AB → C, C → D, D → E, E → F, F → A}. Must-have: B. AB, BC, BD, BE, BF all have full closure (each starts the chain to A). Five keys.

Prime and non-prime attributes

• Prime: belongs to at least one candidate key.
• Non-prime: belongs to none.

Example 1: prime A, D; non-prime B, C, E. Example 2: all of A, B, C, D are prime.

Counting superkeys (from Lesson 2.2.1)

Once the keys are known, count supersets with inclusion–exclusion. Example 3: a superkey must contain B and at least one of A, C, D, E, F: 2⁵ − 1 = 31.

4 · Visual

Closure of AD under  A->B, B->C, CD->E

start          AD
A->B  fires    ABD
B->C  fires    ABCD
CD->E fires    ABCDE      = all attributes  -> AD is a superkey
no more changes; AD has no smaller superkey (A+ = ABC, D+ = D) -> candidate key

5 · Worked Examples

Example 1 Easy

R(A, B, C, D), F = {A → B, B → C, C → D}. Find A⁺, B⁺ and the candidate keys.

Solution

A⁺ = ABCD, B⁺ = BCD. A never appears on a right side and A⁺ is everything: only key A.

Example 2 Medium

R(A, B, C, D, E), F = {AB → C, C → D, D → B, D → E}. Find all candidate keys and the prime attributes.

Solution

Never on the right: A. A⁺ = A. AB⁺ = ABCDE ✓, AC⁺ = ACDBE ✓, AD⁺ = ADBEC ✓, AE⁺ = AE. Keys: AB, AC, AD. Prime: A, B, C, D; non-prime: E.

Example 3 GATE

R(A, B, C, D, E, F), F = {A → B, B → C, C → A, D → E}. How many candidate keys, and how many superkeys?

Solution

Never on the right: D, F. DF⁺ = DFE. Add one of A, B, C (each determines all three): ADF, BDF, CDF: 3 keys. Superkeys: must contain D and F and at least one of A, B, C; E is free: (2³ − 1) × 2 = 14.

8 · Connect the Dots

Lesson 4.2.2 gave the rules; this lesson turned them into the closure algorithm and found all keys. Next: closure of a whole set of FDs, testing whether an FD is implied, and checking whether two FD sets say the same thing.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Closure

R(A, B, C, D, E), F = {A → C, C → D, B → E}. How many attributes are in A⁺?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Candidate keys

R(A, B, C, D, E, F), F = {AB → C, C → D, D → E, E → F, F → A}. How many candidate keys?

Numerical answer: ________

Q3 · MCQ · 2 mark(s) — Candidate keys

R(A, B, C, D, E), F = {A → B, BC → E, ED → A}. The candidate keys are:

1. (A) ACD only
2. (B) ACD, BCD, CDE
3. (C) CD only
4. (D) ABCD

Q4 · NAT · 2 mark(s) — Superkeys

R(A, B, C, D), F = {AB → C, C → D, D → A}. How many superkeys?

Numerical answer: ________

Q5 · MSQ · 2 mark(s) — Prime attributes

R(A, B, C, D, E), F = {A → B, B → C, CD → E}. Which attributes are prime?

1. (A) E
2. (B) D
3. (C) A
4. (D) B

11 · Concept Ledger

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

attribute closure X⁺closure algorithmmust-have attributesfinding all candidate keysprime attributenon-prime attribute