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 \to \beta$ holds, but $\beta \to \alpha$ does not hold. Let $A$ be an attribute that is not in $\alpha$, is not in $\beta$, and for which $\beta \to 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 \to A$, $\alpha \to \beta$, $A\notin \alpha ,A\notin \beta$, and $\beta \to \alpha$ does not hold. But then $\beta \to A$ violates the textbook definition of 3NF since

• $A\notin \beta$ implies $\beta \to A$ is nontrivial.
• Since $\beta \to \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 \to \beta$ that fails all three conditions. Thus,

• $\alpha \to \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 \to A$. Let $\gamma$ be a candidate key for $R$. Then $\gamma \to \alpha ,\alpha \to \gamma$ does not hold (since $\alpha$ is not a superkey), $A\notin \alpha$, and $A\notin \gamma$ (since $A$ is nonprime). Thus $A$ is transitively dependent on $\gamma$, violating the exercise definition.