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

---

Minimum and Maximum is 2000 (If we assume R in r1 is FK)

If this is not assumed, minimum is 0, max is still 2000 (because of the constraint that, R is primary key in r2)

---

@shashankrustagi

Actually, it will always be size of the relation table which contains the foreign key

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

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 ???

---

For natural join we see for common attribute and join, also in natural join we don't include the nulls wala records. Since que doesn't mention as such any details so considered the case that 2000 tuples match with R2 and rest tuples in r2 are might be null so not considered in natural join.

---

@PreyumKr yes you are true, its one heck of a question that ccould and shouuld be asked in Gate . bc for every tuple in R1 will be clubbed with every other tuple in R2. the only thing thats stopping it in this questions case is the fact that R is a primary ket in R2 hence forced to be unique.

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.

Answer 5

BEST ANSWER

r1(P, Q, R)                    P and R are Primary key  so all Tuples are unique

Total tuples= 2000

---

---

  r2(R, S, T) 

 Total tuples= 2500    

R is common attribute in both the tables

the minimum and maximum cardinality will be Min(r1,r2) = Min(2000, 2500) = 2000

So correct answer is (a)   i.e 2000