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

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

---

some variation !! 

Condition on Join Attribute (R)	Max Size	Min Size	Why
R is Primary Key in r2	2000	0	Each row in r1 finds at most one match in r2.
R is Primary Key in BOTH	2000	0	1-to-1 relationship. Max matches equal the smaller table size.
R is NOT a Key in either	5,000,000	0	Cartesian product (2000 times 2500) if all rows happen to have the exact same R value.
r1(R) is a Foreign Key to r2	2000	2000	Every row in r1 must find exactly one match in r2.

 Reason for row 2 minimum value : Primary Key only guarantees uniqueness inside its own table. It does not force the two different tables to actually share any of the same values.

Think of it like two separate schools:

• School A (r1) has 2000 students. Student_ID (R) is the Primary Key. (IDs are 1 to 2000).

• School B (r2) has 2500 students. Student_ID (R) is the Primary Key. (IDs are 5001 to 7500).

In both tables, R is a perfectly valid Primary Key because there are no duplicates inside School A, and no duplicates inside School B.

However, if you join them to find students enrolled in both schools, you will get 0 matches because their ID numbers do not overlap at all.

To guarantee a minimum of 2000, you must have a Foreign Key from r1 to r2.

Without a Foreign Key, the database will always allow the theoretical minimum to be 0 (because it allows the tables to have completely different values).

• Primary Keys control the Maximum.

• Foreign Keys control the Minimum.

 

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

Why are you considering it a Natural Join when it says simply Join and join produces mxn tuples on joining.

---

@Zeeshan ⋈  is reprasent natural join for m*n result we use cross product, r₁* r_{2(cross product).}

---

Can you clear my doubt on this: R is a primary key in only second relation and hence unique and distinct only there. But R in the first relation can be non-unique. So if we assume the above hypothesis, then R can have same value for 2000 tuples in first relation and then the maximum possible tuples of natural join could be 2500. Could you please clarify my doubt ?

---

In first relation 20 records and in second relation assume 25 records.Now R in first relation is referring R in second relation.In first relation R can be unique or it may not be.So R will have 20 values in first relation.Say my first value if 20. Now when i natural join this with the second table,i will see how many R are there with value 20,then as R in unique in second so i will get exactly one match,right?So first 20 is mapped to only one record.On similar basis i can say remaining 19 records will match with 19 of the second relation.so i will get only 20 as maximum.

You may argue that in relation first i can have 5 number as 20.Its fine then.One 20  of R1 maps to One 20  of R2.Second 20 of R1 will map to same 20 again and so on. You can never match R1 with more than one record.So you can not have more than 20 records.

---

@Bikram sir ,if here options are not given , then maximum will be 2500*2000 , rt , bcoz i assuming that for common attribute dont have same value ... rt ?

---

@sid1221

If we are assuming that for common attribute dont have same value 

Then answer must be 2000 + 2500 = 4500

---

Bikram sir explain your comment

---

@ but how can you assume so in this question where R is  foreign key mentioned . so it must have common values . yes in the other cases suppose their is no referential key and commom attributes have no same value . than its cardinality will be " same an cross product's cardinality.

@ Bikram sir, please verify.

---

@Bikram

"If we are assuming that for common attribute dont have same value "

Then answer must be 2000 + 2500 = 4500"

it's wrong, then answer will be 0. 

---

max will be only cross product rt ?

---

@Sid 1221 there is a common column between r1 and r2 i.e. R, and the natural join is given so cross product is never possible.

---

minimum is 0 since it is not given that R of r1 is a foreign key referring to r2 ...

---

@manu thakur it means here you are not considering integrity constraint(foreign key)

---

But even in maximum case how 0 (zero) is possible plz  explain

---

@manu sir i was talking regaring this .. where i was wrong , https://gateoverflow.in/2344/gate2010-43 

---

@sid in this question , B is the key of Relation R and It contains 200 rows.

S has common attribute B and contains 100 columns.

Natural join will result in maximum 100 records and minimum 0.

---

okay :)

---

In r2 R has unique values
So, maximum and minimum number of tuples in natural join is 2000

---

In $r_{1},R$ is the $FK$,so it can be contain $NULL$

So, the minimum number of tuples in natural joins  is  $0$

and In $r_{2}, R$ has unique values$(PK)$
So, the maximum  number of tuples in natural join $r_{1}\Join_{<R=R>} r_{2}$ is $2000$

---

@Lakshman Patel RJIT

In r1(P,Q,R)  .. 'R' s not FK referring to primary key in r2 ..it is not given in question..

But min rows in r1 * r2  = 0 ..reason for that is ..R in r1 can take any values(lets say 4000 to 6000) which where not even single matching with R in r2(lets say 1000 to 3500)..hence in natural join equality fails everytime hence output 0 rows.hence MIN =  0

--------------------------------------------------------------------------------------------------------------------------------

Now other case if . 'R' s FK referring to primary key in r2 ..

Then it seems right all for entries for R in r1 if NULL  ..then anything compared with NULL is false hence if R is FK then also MIN = 0..

-----------------------------------------------------------------------------------------------------------------------------------

Max = 2000 in both cases

please check this

@Shaik Masthan

 

---

@Zeeshan Ashraf Coz, Join comes with a condition (i.e. which attributes to be considered from the relations as we only compare when they have same set of values (Domain)), which is not mentioned in the question. In Question, we are given that we have a Common Attribute (R), therefore, we can consider it as a Natural Join. 

---

https://stackoverflow.com/questions/14548543/natural-join-if-no-common-attributes

---

http://www.cs.toronto.edu/~faye/343/f07/lectures/wk3/03_RAlgebra.pdf

---

https://gateoverflow.in/141588/natural-join

---

https://gateoverflow.in/53460/question-on-join

---

https://stackoverflow.com/questions/22673235/maximum-and-minimum-number-of-tuples-in-natural-join

---

@bikram sir thanks alot

---

what will be the minimum number of tuples? will it be 1 or 0?

---

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

---

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