7.18
Let a prime attribute be one that appears in at least one candidate key. Let \(\alpha\) and \(\beta\) be sets of attributes such that \(\alpha \rightarrow \beta\) holds, but \(\beta \rightarrow \alpha\) does not hold. Let \(A\) be an attribute that is not in \(\alpha\), is not in \(\beta\), and for which \(\beta \rightarrow A\) holds. We say that \(A\) is transitively dependent on \(\alpha\). We can restate the definition of 3NF as follows: A relation schema \(R\) is in 3NF with respect to a set \(F\) of functional dependencies if there are no nonprime attributes \(A\) in \(R\) for which \(A\) is transitively dependent on a key for \(R\). Show that this new definition is equivalent to the original one.
Suppose \(R\) is in 3NF according to the textbook definition. We show that it is in 3NF according to the definition in the exercise. Let \(A\) be a nonprime attribute in \(R\) that is transitively dependent on a key \(\alpha\) for \(R\). Then there exists \(\beta \subseteq R\) such that \(\beta \rightarrow A\), \(\alpha \rightarrow \beta\), \(A \not\in \alpha, A \not\in \beta\), and \(\beta \rightarrow \alpha\) does not hold. But then \(\beta \rightarrow A\) violates the textbook definition of 3NF since
- \(A \not\in \beta\) implies \(\beta \rightarrow A\) is nontrivial.
- Since \(\beta \rightarrow \alpha\) does not hold, \(\beta\) is not a superkey.
- \(A\) is not in any candidate key, since \(A\) is nonprime.
Now we show that if \(R\) is in 3NF according to the exercise definition, it is in 3NF according to the textbook definition. Suppose \(R\) is not in 3NF according to the textbook definition. Then there is a functional dependency \(\alpha \rightarrow \beta\) that fails all three conditions. Thus,
- \(\alpha \rightarrow \beta\) is nontrivial.
- \(\alpha\) is not a superkey for \(R\).
- Some \(A\) in \(\beta - \alpha\) is not in any candidate key.
This implies that \(A\) is nonprime and \(\alpha \rightarrow A\). Let \(\gamma\) be a candidate key for \(R\). Then \(\gamma \rightarrow \alpha, \alpha \rightarrow \gamma\) does not hold (since \(\alpha\) is not a superkey), \(A \not\in \alpha\), and \(A \not\in \gamma\) (since \(A\) is nonprime). Thus \(A\) is transitively dependent on \(\gamma\), violating the exercise definition.