GATE CSE 2004 | Question: 14

Question

Consider the following relation schema pertaining to a students database:

• Students (rollno, name, address)
• Enroll (rollno, courseno, coursename)

where the primary keys are shown underlined. The number of tuples in the student and Enroll tables are $120$ and $8$ respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where ‘*’ denotes natural join?

• A. $8, 8$
• B. $120, 8$
• C. $960, 8$
• D. $960, 120$

Comments

i think you are correct @Tuhin

---

@srestha your case is based on assuming Referential IC is there. 
But another case can also arise when Student table roll no contain 1 to 120 distinct number and but Enroll table roll number contain rollno not present in student table( these can vary like only 1 student have roll no. out bounds, then only 2 students have roll no. out of bounds and so on till 8)

---

Beauty of this question will be understood through deepak's sir answer -

 https://gateoverflow.in/1011/gate-cse-2004-question-14?show=361056#a361056

Answer 1

Rollno in students is key, ans students table has $120$ tuples, In Enroll table rollno is FK referencing to Students table. In natural join it'll return the records where the rollno value of enroll matches with the rollno of students so, in both conditions min and max records will be resulted $(8,8).$
hence A is the answer.

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

Comments

@commenter commenter Really,If this is true???

 

 

 

 

 

 

---

@arpit.jha Means If we have  option  8,0

It would be answer

So,that means we are putting null in all tuples of rollno in Enroll??

 

 

---

@mahendrapatel No that's not what I said , Natural Join is done here on Roll no col right . so what if there is no common roll no value . in both of the relation . in that case in resultant relation there will be no tuple thats why I said it can be minimum zero . One more condition can be where Enroll relation don't have any record in that case also we get min 0.

Answer 2

Some interesting variations can be asked in such question. I have discussed some of them below.

To ensure entity integrity, it is required that every table have a primary key(PK). Neither the PK nor any part of it can contain null values. 

Note that “rollno” in Student relation is primary key, So, it cannot contain Null values. Similarly, “rollno” and “courseno” in Enroll table cannot contain Null values. 

The number of tuples in the student and Enroll tables are 120 and 8 respectively.

Some Variations we can try in this question :

Case 1 :

If there was a referential constraint in place ensuring that every rollno in Enroll must also appear in Student (i.e. “rollno” of relation Enroll is assumed to be a foreign key referencing to the relation “Students”) :

1. 

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes natural join?

Answer : Maximum = 8 ; Minimum = 8

​​​​​​​2.

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes Cartessian Product (aka Cross product or cross join) ?

Answer : Maximum = $120 \times 8$ ; Minimum = $120 \times 8$

3.

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes natural left outer join join?

Answer : Maximum = 127 ; Minimum = 120

4.

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes natural right outer join join?

Answer : Maximum = 8 ; Minimum = 8

5.

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes natural full outer join join?

Answer : Maximum = 127 ; Minimum = 120

Case 2 :

The question doesn't actually mention any referential constraint constraint So there's no need to assume that the referential integrity constraint exists just because the rollno attribute appears in both tables. So,

If there is NO referential constraint in place ensuring that every rollno in Enroll must also appear in Student (i.e. “rollno” of relation Enroll is NOT a foreign key referencing to the relation “Students”) :

​​​​​​​1. 

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes natural join?

Answer : Maximum = 8 ; Minimum = 0

​​​​​​​2.

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes Cartessian Product (aka Cross product or cross join) ?

Answer : Maximum = $120 \times 8$ ; Minimum = $120 \times 8$

3.

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes natural left outer join join?

Answer : Maximum = 127 ; Minimum = 120

4.

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes natural right outer join join?

Answer : Maximum = 8 ; Minimum = 8

5.

What are the maximum and minimum number of tuples that can be present in (Student $*$ Enroll), where $’*’$ denotes natural full outer join join?

Answer : Maximum = 128 ; Minimum = 120

Comments

@Deepak Poonia sir in the above answer wherever 127 is written should be replaced with 126. I am assuming that you got 127 by arpit patel’s logic but that is wrong. In enroll table rollno,courseno is primary key and if in every tuple rollno value is same then courseno alone can be primary key. So there must exist a tuple in which rollno value is different and courseno value is same so that it makes {rollno courseno} values unique.

So in case of maximum 1 tuple of student matches with 7 tuples of enroll and another tuple of student matches with the 8th tuple of enroll. So that results 118+8=126

---

Explanation, of variations using chat gpt. 

---

Complete analysis done

Answer 3

for minimum

since , here, roll no is primary key is given for both the table not any clue about foriegn key is given so, we cant assume ROLL as foreign key.

suppose a condition:-

STUDENT                                                                

rollno(PK)	name	add
25	jan	a
32	man	c
42	pan	b

 ENROLL

rollno(PK)	name	add
45	moh	a
32	soh	b
64	poh	c

then , if we apply natural join(*) hen no any tuples will be selected

so,min=0

now for aximum,

suppose a condition where all the 8 tuples in ENROLL is present then STUDENT(naturaljoin)ENROLL gives 8 tuplesbecause out of 120  tuples only 8 tuples will be matched

and, since , roll no. os student table is also PK then they must be differnt so maxm * tuples 

so, final answer must be 8,0

but, in option it is not given so, i think GATE question setter have missed out to mention refrencial integrity . if, RI would be there then it's answer will be 8,8

Comments

In Enroll table roll no is not primary key so  you are wrong and (8,8) is answer option A

---

I tested on MYSQL and it does give 0 as minimum tuples with ‘NATURAL JOIN’ but, I didn’t get...why 0 tuples?

---

0 Tuples in case if there are no Foreign Key, 8 tuples if there is a foreign key Roll no in Enrollment table referring to Roll no in the Student table.

Answer 4

nothing mentioned about foriegn key
we have two cases :
case 1)  Student(rollno) is foreign key but it is not possible becoz if it is foreign key ( it have 120 tupples) then parent relation (Enroll) should have atleast 120 tupples but Enroll have only 8 tupples
case 2)  Enroll(rollno) is foreign key and it is possible becoz parent table of it(Student) have atleast 8 tupples)

now come to question
Maximum and Minimum no of tuples are (8,8) becoz in Child relation (Enroll) we have 8 tuples and only those 8 tuples are join with parent relation (Students)

correct me if wrong :)

Comments

wrong analysis but correct answer

bcz of FK not possible here bcz parent tabel attribute and fk attribute cardinality not  same

Answer 5

Ans: 8 records

Justification:

• There are 120 distinct Rollno in the students table.
• There are 8 unique <Rollno, courseno> pairs in the enroll table.

Thinking about worst and best cases:

• Min there can be 1 Rollno, 8 distinct courses.
• Max there can be 8 distinct Rollno, and same/diff courses, 1 for each Rollno.
• Notice that irrespective of distribution of Rollno.s; after join, we still end up with 8 records only

This observation can be extended to conclude that whenever we join 2 tables where table $T_1$’s PK is FK in $T_2$, and is a part of $T_2$’s PK; then the number of records after natural join stays the same as number of records of $T_2$.

Answer 6

No foreign key :

No tuples matching, Minimum tuples = 0

Maximum tuples = 8, as rollno in student is a primary key, it contains distinct values.

Foreign key :

All tuples have Null values in roll no field of Enroll, Minimum - 0

Maximum - 8

So, the best option that matches the answer is a) 8,8