Given two tables π 1(π₯,π¦) and π 2(π¦,π§) with 50 and 30 number of tuplesβ¦
2019
Given two tablesΒ π 1(π₯,π¦)Β andΒ π 2(π¦,π§)Β withΒ 50Β andΒ 30Β number of tuples respectively. Find maximum number of tuples in the output of natural join between tablesΒ π 1Β andΒ π 2Β i.e.Β π 1βπ 2? (β- Natural Join)
- A.
30
- B.
20
- C.
50
- D.
1500
Attempted by 265 students.
Show answer & explanation
Correct answer: D
Answer: 1500
Reasoning:
For each value of y, let count_R1(y) be the number of tuples in the first table with that y, and count_R2(y) be the number in the second table with that y.
The number of joined tuples contributed by a particular y value equals count_R1(y) Γ count_R2(y).
The total size of the join is the sum over all y values: Ξ£_y count_R1(y) Γ count_R2(y).
Given only the totals (Ξ£_y count_R1(y) = 50 and Ξ£_y count_R2(y) = 30), this sum of products is maximized when all tuples from both tables share the same y value, because concentrating counts on a single value maximizes the product.
In that case the join size is 50 Γ 30 = 1500, which is the maximum possible.
Note: The minimum possible join size is 0 if there are no matching y values between the two tables.
A video solution is available for this question β log in and enroll to watch it.