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)

  1. A.

    30

  2. B.

    20

  3. C.

    50

  4. 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.

Explore the full course: Mppsc Assistant Professor