Functional Dependencies and Candidate Keys in $R(A,B,C)$

In the relation schema $R(A,B,C)$ with functional dependency set $F=\{A \rightarrow B,\; B \rightarrow A\}$, the correct statement is:

(iv) Neither $A$ nor $B$ is a key.2

A candidate key must determine every attribute in the relation, including $C$.2 Here, $A$ determines $B$, and $B$ determines $A$, so $A$ and $B$ are mutually determining attributes. However, there is no functional dependency involving $C$ on the right-hand side, so neither $A^+$ nor $B^+$ can include $C$ under the given FD set.2

Thus:

• $A^+ = \{A,B\}$
• $B^+ = \{A,B\}$

Since neither closure equals $\{A,B,C\}$, neither $A$ nor $B$ is a superkey, and therefore neither can be a candidate key.2

A useful rule of thumb is that if an attribute such as $C$ is not derivable from other attributes, then any key must include it. So the actual candidate keys are:

• $\{A,C\}$
• $\{B,C\}$

3

Footnotes

1. Determining candidate keys with functional dependencies simple - Explains key-finding heuristics, including that attributes not derivable from others must appear in every key. ↩ ↩² ↩³ ↩⁴

2. Closure of a Set of Functional Dependencies - Describes attribute closure computation and use of Armstrong-derived inference rules. ↩ ↩² ↩³

3. Candidate key - Wikipedia - Defines candidate keys as minimal sets whose closure contains all attributes of the relation. ↩ ↩² ↩³

4. Candidate Keys (LSU PDF) - Defines superkeys and candidate keys using attribute closure over the full relation schema. ↩ ↩²

5. Normalization – Relational Databases - Notes that if $B \rightarrow A$ also holds, then $A$ and $B$ can both be candidate keys only when they determine the remaining attributes as well. ↩

To understand why, we use attribute closure.2 The closure of a set $X$, written $X^+$, contains every attribute that can be inferred from $X$ using the given functional dependencies.

For this problem:

Because a key must determine all attributes of $R$, both $A$ and $B$ fail, but $AC$ and $BC$ succeed.2

This also illustrates minimality: although $AC$ determines all attributes, neither $A$ nor $C$ alone does, so $AC$ is minimal and hence a candidate key.2

Footnotes

1. Candidate key - Wikipedia - Defines candidate keys as minimal sets whose closure contains all attributes of the relation. ↩ ↩² ↩³

2. Candidate Keys (LSU PDF) - Defines superkeys and candidate keys using attribute closure over the full relation schema. ↩ ↩² ↩³

3. Determining candidate keys with functional dependencies simple - Explains key-finding heuristics, including that attributes not derivable from others must appear in every key. ↩

A deeper conceptual point is that $A$ and $B$ are equivalent with respect to each other, but not with respect to the whole relation. In other words, they can replace each other when deriving $A$ or $B$, yet neither can generate $C$.2

Using Armstrong's axioms such as reflexivity and transitivity, we can derive:

• $A \rightarrow A$ by reflexivity
• $B \rightarrow B$ by reflexivity
• $A \rightarrow B$ given
• $B \rightarrow A$ given

But there is still no derivation of $A \rightarrow C$ or $B \rightarrow C$.2 Therefore, $C$ remains outside both single-attribute closures.

This is why many database design heuristics note that an attribute not derivable from others often must appear in every key. Here, $C$ must be included in any candidate key, yielding $AC$ and $BC$ as the minimal keys.2

Footnotes

1. Normalization – Relational Databases - Notes that if $B \rightarrow A$ also holds, then $A$ and $B$ can both be candidate keys only when they determine the remaining attributes as well. ↩ ↩² ↩³

2. Closure of a Set of Functional Dependencies - Describes attribute closure computation and use of Armstrong-derived inference rules. ↩ ↩²

3. Determining candidate keys with functional dependencies simple - Explains key-finding heuristics, including that attributes not derivable from others must appear in every key. ↩ ↩²

4. Candidate key - Wikipedia - Defines candidate keys as minimal sets whose closure contains all attributes of the relation. ↩

Final Answer

For the relation $R(A,B,C)$ with $F=\{A \rightarrow B,\; B \rightarrow A\}$:

• $A^+=\{A,B\}$
• $B^+=\{A,B\}$

Neither closure contains $C$, so neither $A$ nor $B$ is a key.3

Therefore, the correct option is:

$$\boxed{\text{(iv) Neither A nor B is key}}$$

The actual candidate keys are:

$$\{A,C\} \quad \text{and} \quad \{B,C\}$$

Footnotes

1. Determining candidate keys with functional dependencies simple - Explains key-finding heuristics, including that attributes not derivable from others must appear in every key. ↩

2. Closure of a Set of Functional Dependencies - Describes attribute closure computation and use of Armstrong-derived inference rules. ↩

3. Candidate key - Wikipedia - Defines candidate keys as minimal sets whose closure contains all attributes of the relation. ↩