GATE CS 2010 Q43 — Normal Forms

To find the maximum number of tuples in the natural join $R \bowtie S$, we first identify the join attribute and analyze the constraints on it.

1. Identify the Join Attribute: The common attribute between $R(A, B, C)$ and $S(B, D, E)$ is $B$. Therefore, the natural join is performed on $B$.
2. Analyze the Functional Dependencies on $R$: We are given:
   • $B \to A$
   • $A \to C$
   By transitivity, $B \to C$. Since $B$ functionally determines all attributes of $R$ (i.e., $B \to \{A, B, C\}$), $B$ is a candidate key for relation $R$.
3. Determine Tuple Uniqueness: Because $B$ is a candidate key of $R$, the values of $B$ in $R$ must be unique. Thus, each distinct value of $B$ can appear at most once in $R$.
4. Calculate the Join Size: In the natural join $R \bowtie S$, each tuple in $S$ can match with at most one tuple in $R$ (since $B$ is unique in $R$). Since $S$ contains $100$ tuples, the maximum number of matching tuples in the join is $100 \times 1 = 100$.

Thus, the maximum number of tuples possible in $R \bowtie S$ is $100$.