The following functional dependencies hold for relations R(A, B, C) and S(B,…
2010
The following functional dependencies hold for relations R(A, B, C) and S(B, D, E)
B → A,
A → C
The relation R contains 200 tuples and the relation S contains 100 tuples. What is the maximum number of tuples possible in the natural join R \( \bowtie \) S?
- A.
100
- B.
200
- C.
300
- D.
2000
Attempted by 281 students.
Show answer & explanation
Correct answer: A
Answer: 100
Reasoning:
From the functional dependencies B → A and A → C, by transitivity we get B → A,C. So B functionally determines all attributes of relation R.
Therefore, within R each value of B can appear in at most one tuple (B is a key for R).
A natural join between R and S matches tuples on B. Because each B value in S can match at most one tuple in R, each tuple of S contributes at most one tuple to the join.
S has 100 tuples, so the join can have at most 100 tuples.
This bound is achievable if every B value present in S also appears in R (with at most one matching R tuple per B), in which case the join produces exactly 100 tuples.
A video solution is available for this question — log in and enroll to watch it.