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?

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.