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: Use the raw definition of a functional dependency directly on sample tables instead of quoting axiom names.
Recall $X \rightarrow Y$ means: any two rows of the relation that agree on every attribute in $X$ must also agree on every attribute in $Y$.

Step 2: Disprove option (A) with a table.
Build rows $(P,Q,R)$: $(1, a, 100)$, $(1, b, 100)$, $(2, a, 200)$. Check $P \rightarrow R$: rows with $P=1$ both have $R=100$ (consistent), $P=2$ has $R=200$ (only one row), so $P \rightarrow R$ holds. Then $\{P,Q\}\rightarrow R$ holds automatically since $P$ alone already pins down $R$. Now check whether $Q \rightarrow R$ is forced: add one more row $(3, a, 300)$. Now $Q=a$ appears with $R=100$ and also with $R=300$ -- two rows agreeing on $Q$ but disagreeing on $R$, so $Q \rightarrow R$ fails while $P \rightarrow R$ and $\{P,Q\}\rightarrow R$ still hold. This table satisfies the hypothesis of option (A) but breaks its conclusion, so (A) is not always true.

Step 3: Disprove option (B) with the standard student/course/grade table.
Rows $(P,Q,R)$ = (StudentId, CourseId, Grade): $(101, CS1, A)$, $(101, CS2, B)$, $(102, CS1, B)$. Every pair of rows that agree on both StudentId and CourseId (there are no duplicate pairs here) trivially agrees on Grade, so $\{P,Q\} \rightarrow R$ holds. But rows with $P=101$ have different grades ($A$ and $B$), so $P \rightarrow R$ fails; and rows with $Q=CS1$ have different grades ($A$ and $B$), so $Q \rightarrow R$ fails too. The hypothesis holds but neither disjunct of the conclusion holds, so (B) is not always true.

Step 4: Confirm option (C) directly from the definition.
Suppose $P \rightarrow R$ and $Q \rightarrow S$ hold in some relation. Take any two rows that agree on both $P$ and $Q$. Since they agree on $P$ and $P \rightarrow R$ holds, they must agree on $R$. Since they also agree on $Q$ and $Q \rightarrow S$ holds, they must agree on $S$. So any two rows agreeing on $\{P,Q\}$ necessarily agree on both $R$ and $S$, which is exactly the statement $\{P,Q\} \rightarrow \{R,S\}$. This argument uses only the definition and holds for every instance, so (C) is always true.

Step 5: Confirm option (D) directly from the definition.
Suppose $P \rightarrow R$ holds. Take any two rows that agree on both $P$ and $Q$; in particular they agree on $P$, so by $P \rightarrow R$ they must agree on $R$. So any two rows agreeing on $\{P,Q\}$ agree on $R$, which is exactly $\{P,Q\} \rightarrow \{R\}$. This holds for every instance, so (D) is always true. (Adding more attributes to the determinant side of a dependency that already holds can never break it, only possibly become redundant.)

Step 6: Final answer.
$\[ \boxed{\text{(C) and (D) always hold; (A) and (B) can be broken by a counterexample table}} \]$