GATE CS 2022 Q4 — Normal Forms

Let us analyze each option to determine the correct statement:

• Option A: A relation with only two attributes is always in BCNF. (TRUE)

  Let $R(A, B)$ be a relation with only two attributes. The only possible non-trivial functional dependencies (FDs) are $A \rightarrow B$ and/or $B \rightarrow A$.

  • If $A \rightarrow B$ holds, then $A$ is a candidate key (and hence a superkey).
  • If $B \rightarrow A$ holds, then $B$ is a candidate key (and hence a superkey).
  • If both hold, both $A$ and $B$ are candidate keys.
  • If no non-trivial FDs hold, BCNF is trivially satisfied.

  In every case, for any active non-trivial FD $X \rightarrow Y$, the determinant $X$ is a superkey. Thus, any binary relation is always in BCNF.

• Option B: If all attributes of a relation are prime attributes, then the relation is in BCNF. (FALSE)

  Consider a relation $R(A, B, C)$ with functional dependencies: $$AB \rightarrow C \quad \text{and} \quad C \rightarrow B$$ The candidate keys are $AB$ and $AC$. All attributes $\{A, B, C\}$ are prime attributes. However, for the dependency $C \rightarrow B$, the determinant $C$ is not a superkey. Hence, the relation is in 3NF but not in BCNF.

• Option C: Every relation has at least one non-prime attribute. (FALSE)

  In the counterexample used for Option B ($R(A, B, C)$ with keys $AB$ and $AC$), all attributes are prime. There are no non-prime attributes.

• Option D: BCNF decompositions preserve functional dependencies. (FALSE)

  While BCNF decomposition is always lossless, it is not always dependency-preserving. For example, decomposing $R(A, B, C)$ with $AB \rightarrow C$ and $C \rightarrow B$ into BCNF relations $R_1(C, B)$ and $R_2(A, C)$ loses the dependency $AB \rightarrow C$.