Question 7 of 8: Functional dependencies and normalization

Question 7: Functional dependencies and normalization (3+5+2+(5+5)=20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) Functional dependency. A functional dependency $X \rightarrow Y$ on relation schema $R$ holds if, for every possible legal instance of $R$, any two tuples that agree on all attributes of $X$ must also agree on all attributes of $Y$ — that is, the values of $X$ uniquely determine the values of $Y$. It is a statement about every valid state the relation could ever hold, not just about the current contents of one particular table.

(b) BCNF vs. 3NF. Both normal forms forbid "bad" functional dependencies, but they draw the line differently. A relation is in 3NF if, for every nontrivial FD $X\rightarrow A$, either $X$ is a superkey OR $A$ is part of some candidate key (the "prime attribute" exception). BCNF drops that exception entirely: for every nontrivial FD $X\rightarrow A$, $X$ must be a superkey, full stop. BCNF is strictly stronger (every BCNF relation is automatically in 3NF, but not vice versa) — the prime-attribute loophole in 3NF is exactly what lets a relation keep a small, specific class of redundancy-causing FDs that BCNF would reject.

(c) Is every FD in BCNF also "in" 3NF? Yes. Any nontrivial FD $X\rightarrow A$ that satisfies BCNF's requirement ($X$ is a superkey) automatically satisfies 3NF's requirement too, since "$X$ is a superkey" is precisely 3NF's first disjunct (the "$A$ is prime" clause only matters as a fallback when $X$ is NOT a superkey). So BCNF's condition on an FD is strictly more demanding than 3NF's, and satisfying the harder condition trivially satisfies the easier one — every relation in BCNF is therefore also in 3NF (the converse fails: a 3NF relation using the prime-attribute exception need not be in BCNF).

(d) Given. $R = \{SSN, Name, Address, Hobby\}$, $F = \{SSN \rightarrow Name, Address\}$, decomposed into $R_1=\{SSN,Name,Address\}$ with $F_1=F$, and $R_2=\{SSN,Hobby\}$ with $F_2=\emptyset$.

1. (i) Lossless-join test. A binary decomposition is lossless iff $(R_1 \cap R_2)$ is a superkey of at least one of $R_1$ or $R_2$ under $F^+$. Here $R_1 \cap R_2 = \{SSN\}$, and its attribute closure under $F$ is $\{SSN\}^+ = \{SSN, Name, Address\} = R_1$ — so $SSN$ is a superkey of $R_1$. $$\boxed{\text{Decomposition is LOSSLESS-JOIN}}$$
2. (ii) Dependency-preservation test. A decomposition preserves dependencies iff $(F_1 \cup F_2)^+ = F^+$, checked by confirming every FD in $F$ is derivable from $F_1 \cup F_2$ alone. Here $F_1 \cup F_2 = \{SSN \rightarrow Name, Address\}$, which IS $F$ itself (nothing was lost — $Hobby$ carried no dependency to begin with, so $F_2=\emptyset$ costs nothing). $$\boxed{\text{Decomposition is DEPENDENCY-PRESERVING}}$$