GATE IT 2006 | Question: 14

Question

Consider the relations $r_{1}\text{(P, Q, R)}$ and $r_{2}\text{(R, S, T)}$ with primary keys $\text{P}$ and $\text{R}$ respectively. The relation $r_{1}$ contains $2000$ tuples and $r_{2}$ contains $2500$ tuples. The maximum size of the join $r_1⋈ r_2$ is :

• A. $2000$
• B. $2500$
• C. $4500$
• D. $5000$

Comments

Attribute R in relation r1 is assumed to be a Foreign Key referencing attribute R in relation r2.

---

Repeatetive question

INfact, both the minimum and maximum cardinality will be min(A,B) as R is common attribute in both the tables

 

minimum when In r1 table, R attribute is having same entry i.e. 1

maximum when in R1 table, R attribute is having different entry for each tuple, then also 2000 will be the answer

Answer 1

The common attribute is $\text{R}$ and it is the primary key in the second relation. So $\text{R}$ value should be distinct (primary key implies unique) for $2500$ rows. Hence when we do join, maximum possible number of tuples is $2000.$

Correct option is A.

Comments

table which has non-key, no of records of that will be resulted.

---

Explaining @ijnuhb’s comment a bit, the number of tuples always results in the number of tuples in the table containing the common attribute (here $R$) as the non-key (here $R$ is non key in table $r1$. hence no. of records = no of tuples in $r1 = 2000$).

Similar q: https://gateoverflow.in/1011

---

What if the R value in R2 is not primary and all values of R is same in r2 and that value is present in R1. Then if only one row or R1 has that common value then answer will be 2500 ? and if all the rows in r1 also has the same value then answer will be 2000*2500 = 5000000 ???

Answer 2

Let us see two scenarios with small number of tuples r1 having 5 tuples and r2 with 3 tuples.

Scenario 1: when all the attributes in R in r1 do not match value of R in r2.

r1

P	Q	R
5	m	1
6	n	2
7	o	2
8	p	5
9	q	6

r2

R	S	T
1	a	m
2	b	n
3	c	u

natural join on r1 and r2 would give me

P	Q	R	S	T
5	m	1	a	m
6	n	2	b	n
7	0	2	b	n

Scenario 2: 

There are no uncommon values for R between r1 and r2

P	Q	R
5	m	1
6	n	2
7	o	2
8	p	2
9	q	1

Natural join would give

P	Q	R	S	T
5	m	1	a	m
6	n	2	b	n
7	o	2	b	n
8	p	2	b	n
9	q	1	a	m

So in this case we get the max number of tuples ,which is equal to the max number of tuples in relation r1.

Generalizing this inference we can derive that ans is a)2000 =max no of tuples in r1.

Comments

In the answer given tuples are not correct I think

Foreign key always refer a primary key

then how 5,6 possible for R which are not in primary key?

P	Q	R
5	m	1
6	n	2
7	o	2
8	p	5
9	q	6

---

@srestha Yes you are correct 5,6 are not present in R of r2, R of r1 should always refer to R of r2 bcoz it is a foreign key.

---

@srestha a small thing.

foreign key always refer a primary key.

I think the primary key should be replaced by the candidate key in the above sentence.

Answer 3

See the image below carefully in order to understand that the maximum cardinality of join operation is minimum tuples of R1,R2

Comments

The generalization concluded is wrong , think about it.

Answer 4

Maximum number of tuples or size of the join is 2000 i.e. number of tuples in r1.