7.36

Show that every schema consisting of exactly two attributes must be in BCNF regardless of the given set \(F\) of functional dependencies.

---

Let \(R = (A, B)\) be a schema with two attributes. Let \(F\) be a set of functional dependencies that hold on \(R\).

We want to show:- \(R\) is in BCNF.

Suppose to the contrary that \(R\) is not in BCNF. That is, there exists \(\alpha \rightarrow \beta\) in \(F^+\) that is not trivial and \(\alpha\) is not a superkey.

Since \(\alpha \subseteq R\) and \(\beta \subseteq R\), we know that, both \(\alpha, \beta \in \{ \{A\}, \{B\}, \{A,B\} \}\).

• Case 1: \(\alpha = \{A\}\)

  • Sub-Case 1: \(\beta = \{A\}\)
    This sub-case is impossible since, it would make the functional dependency trivial. And we have assumed that the functional dependency \(\alpha \rightarrow \beta\) is not trivial.

  • Sub-Case 2: \(\beta = \{B\}\)
    Then we can write \(\alpha \rightarrow \beta\) as \(\{A\} \rightarrow \{B\}\). By Reflexivity rule followed by Union rule we know that this \(\{A\} \rightarrow \{A, B\}\) holds. This means \(\alpha\) is a superkey. But we have assumed \(\alpha\) is not a superkey. Thus this sub-case is also impossible.

  • Sub-Case 3: \(\beta = \{A,B\}\)
    Also impossible, since this would make \(\alpha\) a superkey. And we have assumed that \(\alpha\) is not a superkey.

• Case 2: \(\alpha = \{B\}\)

  • Sub-Case 1: \(\beta = \{A\}\)
    Then we can write \(\alpha \rightarrow \beta\) as \(\{B\} \rightarrow \{A\}\). By Reflexivity rule followed by Union rule we know that this \(\{B\} \rightarrow \{A, B\}\) holds. This means \(\alpha\) is a superkey. But we have assumed \(\alpha\) is not a superkey. Thus this sub-case is impossible.

  • Sub-Case 2: \(\beta = \{B\}\)
    This sub-case is impossible since, it would make the functional dependency trivial. And we have assumed that the functional dependency \(\alpha \rightarrow \beta\) is not trivial.

  • Sub-Case 3: \(\beta = \{A,B\}\)
    Also impossible, since this would make \(\alpha\) a superkey. And we have assumed that \(\alpha\) is not a superkey.

• Case 3: \(\alpha = \{A,B\}\)
  • This case is impossible, since \(\alpha\) is obviously a superkey.

Therefore \(R\) is in BCNF.