GATE CS 2005 Q78 — Integrity Constraints

To find the candidate keys of the relation $R(A, B, C, D, E, H)$, we first identify the attributes that must be present in every candidate key.

Step 1: Identify Essential Attributes

An attribute that does not appear on the right-hand side (RHS) of any functional dependency must be part of every candidate key because it cannot be determined by any other attribute.

• The given functional dependencies are:
  • $A \rightarrow B$
  • $BC \rightarrow D$
  • $E \rightarrow C$
  • $D \rightarrow A$
• Attributes on the RHS: $B, D, C, A$
• Attributes not on the RHS: $E$ and $H$

Thus, every candidate key must contain both $E$ and $H$. This immediately eliminates options A and B.

Step 2: Test Closures of Combinations with $E$ and $H$

Let's find the attribute closures for combinations of $E$ and $H$ with other attributes:

1. For $AEH$: $$\begin{aligned} (AEH)^+ &= \{A, E, H\} \\ &= \{A, B, E, H\} \quad (\text{using } A \rightarrow B) \\ &= \{A, B, C, E, H\} \quad (\text{using } E \rightarrow C) \\ &= \{A, B, C, D, E, H\} \quad (\text{using } BC \rightarrow D) \\ &= R \end{aligned}$$ Since $(AEH)^+$ contains all attributes of $R$ and no proper subset of $AEH$ can determine $R$ (as $E$ and $H$ are essential), $AEH$ is a candidate key.


2. For $BEH$: $$\begin{aligned} (BEH)^+ &= \{B, E, H\} \\ &= \{B, C, E, H\} \quad (\text{using } E \rightarrow C) \\ &= \{B, C, D, E, H\} \quad (\text{using } BC \rightarrow D) \\ &= \{A, B, C, D, E, H\} \quad (\text{using } D \rightarrow A) \\ &= R \end{aligned}$$ Thus, $BEH$ is a candidate key.


3. For $DEH$: $$\begin{aligned} (DEH)^+ &= \{D, E, H\} \\ &= \{A, D, E, H\} \quad (\text{using } D \rightarrow A) \\ &= \{A, B, D, E, H\} \quad (\text{using } A \rightarrow B) \\ &= \{A, B, C, D, E, H\} \quad (\text{using } E \rightarrow C) \\ &= R \end{aligned}$$ Thus, $DEH$ is a candidate key.

Therefore, the candidate keys of $R$ are $AEH$, $BEH$, and $DEH$.