GATE CS 2005 Q29 — Normal Forms

Let us analyze each statement to identify the false one:

• Option A: $\text{BCNF}$ is stricter than $\text{3NF}$
  This is TRUE. Every relation schema that is in $\text{BCNF}$ is also in $\text{3NF}$, but the converse is not true. $\text{BCNF}$ eliminates anomalies arising from functional dependencies where a determinant is not a superkey, which $\text{3NF}$ might allow if the dependent is a prime attribute.


• Option B: Lossless, dependency-preserving decomposition into $\text{3NF}$ is always possible
  This is TRUE. There exists a standard synthesis algorithm (using a canonical cover) that guarantees any relation can be decomposed into $\text{3NF}$ relations while preserving all functional dependencies and ensuring a lossless join.


• Option C: Lossless, dependency-preserving decomposition into $\text{BCNF}$ is always possible
  This is FALSE. While a lossless decomposition into $\text{BCNF}$ is always possible, it is not always possible to preserve all functional dependencies.
  Counterexample: Consider the relation $R(A, B, C)$ with functional dependencies:$$C \rightarrow B$$$$AB \rightarrow C$$Here, the candidate keys are $AB$ and $AC$.
  • The dependency $C \rightarrow B$ violates $\text{BCNF}$ because $C$ is not a superkey.
  • If we decompose $R$ to achieve $\text{BCNF}$, the only valid decomposition is $R_1(C, B)$ and $R_2(A, C)$.
  • In this decomposition, the dependency $AB \rightarrow C$ cannot be preserved because its attributes are split across different relations.


• Option D: Any relation with two attributes is in $\text{BCNF}$
  This is TRUE. Consider a relation $R(A, B)$. The only possible non-trivial functional dependencies are $A \rightarrow B$ or $B \rightarrow A$.
  • If $A \rightarrow B$ holds, then $A$ is a candidate key (and thus a superkey).
  • If $B \rightarrow A$ holds, then $B$ is a candidate key (and thus a superkey).
  • If both hold, both are superkeys. If neither holds, there are no non-trivial FDs.
  In all cases, for every non-trivial dependency $X \rightarrow Y$, $X$ is a superkey. Hence, $R$ is in $\text{BCNF}$.

Therefore, the false statement is C.