Question

Let \(P, Q, R\) and \(S\) be the attributes of a relation in a relational schema. Let \(X \rightarrow Y\) indicate functional dependency in the context of a relational database, where \(X, Y \subseteq \{P, Q, R, S\}\).
Which of the following options is/are always true?

• A. If (\(\{P,Q\} \rightarrow \{R\}\) and \(\{P\} \rightarrow \{R\}\)), then \(\{Q\} \rightarrow \{R\}\)
• B. If \(\{P,Q\} \rightarrow \{R\}\), then (\(\{P\} \rightarrow \{R\}\) or \(\{Q\} \rightarrow \{R\}\))
• C. If (\(\{P\} \rightarrow \{R\}\) and \(\{Q\} \rightarrow \{S\}\)), then \(\{P,Q\} \rightarrow \{R,S\}\)
• D. If \(\{P\} \rightarrow \{R\}\), then \(\{P,Q\} \rightarrow \{R\}\)

Hint:

Try to derive each implication using only reflexivity, augmentation and transitivity (and their consequences, decomposition and union); if you cannot derive it, hunt for a small counterexample table that breaks it.

Answer 1

The Correct Option is C, D

Step 1: Recall Armstrong's axioms.
Reflexivity: if \(Y \subseteq X\) then \(X \rightarrow Y\). Augmentation: if \(X \rightarrow Y\) then \(XZ \rightarrow YZ\) for any \(Z\). Transitivity: if \(X \rightarrow Y\) and \(Y \rightarrow Z\) then \(X \rightarrow Z\). Two standard derived rules follow: Decomposition (if \(X \rightarrow YZ\) then \(X \rightarrow Y\) and \(X \rightarrow Z\)) and Union (if \(X \rightarrow Y\) and \(X \rightarrow Z\) then \(X \rightarrow YZ\)). An option is "always true" only if it can be derived from these axioms for every possible relation instance; otherwise a single counterexample instance is enough to disprove it.

Step 2: Test option (A) with a counterexample.
Take a relation with rows \((P,Q,R) = (1, X, 10), (1, Y, 10), (2, Z, 20)\). Here \(P \rightarrow R\) holds (each \(P\) value maps to one \(R\) value), and consequently \(\{P,Q\} \rightarrow R\) also holds by augmentation. But \(Q \rightarrow R\) fails to be forced in general -- \(Q\) is not required to determine \(R\) at all (in this instance \(Q\) values happen to be distinct so it looks like it might hold, but one can equally build an instance where two different \(Q\) values map to two different \(R\) values with no relationship, since nothing in the axioms forces \(Q\) alone to determine \(R\)). Since \(Q \rightarrow R\) is not derivable from \(\{P,Q\}\rightarrow R\) and \(P \rightarrow R\) using Armstrong's axioms, option (A) is not always true.

Step 3: Test option (B) with the classic counterexample.
Let \(P\) = student id, \(Q\) = course id, \(R\) = grade. Here \(\{P,Q\} \rightarrow R\) holds (a student's grade in a specific course is uniquely determined), but neither \(P \rightarrow R\) holds alone (the same student gets different grades in different courses) nor \(Q \rightarrow R\) holds alone (the same course gives different grades to different students). So option (B) fails in general and is not always true.

Step 4: Prove option (C) using the axioms.
Given \(P \rightarrow R\), augment both sides with \(Q\): \(PQ \rightarrow RQ\). Given \(Q \rightarrow S\), augment both sides with \(P\): \(PQ \rightarrow SP\), i.e. \(PQ \rightarrow PS\). Decompose \(PQ \rightarrow RQ\) to get \(PQ \rightarrow R\) (dropping the trivial \(PQ \rightarrow Q\)). Decompose \(PQ \rightarrow PS\) to get \(PQ \rightarrow S\) (dropping the trivial \(PQ \rightarrow P\)). Now union \(PQ \rightarrow R\) and \(PQ \rightarrow S\) to get \(PQ \rightarrow RS\), which is exactly \(\{P,Q\} \rightarrow \{R,S\}\). This is a valid Armstrong's-axiom derivation for every instance, so option (C) is always true.

Step 5: Prove option (D) using the axioms.
Given \(P \rightarrow R\), apply augmentation with \(Q\): \(PQ \rightarrow RQ\). Decompose \(RQ\) on the right-hand side to drop the trivial \(Q\) part, leaving \(PQ \rightarrow R\), which is exactly \(\{P,Q\} \rightarrow \{R\}\). This holds for every instance, so option (D) is always true.

Step 6: Conclusion.
Options (C) and (D) follow directly from Armstrong's axioms and hold for every relation instance, while (A) and (B) can be broken by concrete counterexamples.
\[ \boxed{\text{Always true: (C) and (D)}} \]