Largest possible natural join — Aptitude Question
Largest possible natural join: R(A, B) holds 200 tuples and S(B, C) holds 100 tuples. What is the maximum possible… Answer and worked solution on CodeKairo.
- Topic: OS, DBMS & Networks
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 105 seconds
Question
R(A, B) holds 200 tuples and S(B, C) holds 100 tuples. What is the maximum possible number of tuples in the natural join of R and S?
Options
- 0
- 100
- 200
- 20000
Show the answer and the worked solution
Correct answer: D. 20000
Worked solution
- The natural join pairs a tuple of R with a tuple of S whenever the two agree on B.
- If every tuple of both relations happens to carry the same B value, each of the 200 tuples of R matches each of the 100 tuples of S.
- That gives 200 × 100 = 20000 tuples, the same size as the cross product, and nothing can exceed it.
Answer: 20000.
The idea
The natural join is a selection over the cross product, so its size runs from 0 to |R| × |S|. If B were a key of S, the maximum would collapse to 200.
Shortcut. No join can exceed the cross product, and it is reached when every tuple shares a single B value: 200 × 100 = 20000.
Common trap. 200 assumes each R tuple matches at most one S tuple, which holds only if B is a key of S.