# Maximum join of relations

I have a question as follows

Consider the relations $$r1(P, Q, R)$$ and $$r2(R, S, T)$$ with primary keys $$P$$ and $$R$$ respectively. The relation $$r1$$ contains $$2000$$ tuples and $$r2$$ contains $$2500$$ tuples. The maximum size of the join $$r1⋈ r2$$ is :

My attempt - Suppose all value of $$R$$ in $$r1$$ are same. Then it should be $$4499$$.

But it's given $$2000$$. Am I missing something?

• Why downvote out of nowhere? – Mr. Sigma. Nov 25 '18 at 3:10

## 1 Answer

$$r1⋈ r2$$ is the natural join of $$r1$$ and $$r2$$/ That is inner join on the common attribute $$R$$, where $$R$$ is the primary key of $$r2$$. It is Cartesian product of $$r1$$ and $$r2$$ followed by selection.

For each element $$(a,b)\in r1⋈ r2$$, where $$a=(p,q,r)$$ and $$b=(r', s,t)$$, we must have $$r=r'$$. That is, $$b=(r,s,t)$$. Since $$R$$ is the primary key for $$r2$$, for any $$a\in r1$$, there is at most one $$b$$ that can "join" $$a$$. So we will have at most 2000 tuples.

By the way, I could not see why "Suppose all value of R in r1 are same. Then it should be 4499". It is not even an option in the original problem.

• Thanks, don't know why it happens. I don't know what the hell I was thinking then... – Mr. Sigma. Nov 25 '18 at 2:51
• And why downvotes to questions? – Mr. Sigma. Nov 25 '18 at 2:52
• You should ask that why as a comment to your question. I did not downvote. – John L. Nov 25 '18 at 3:09