GATE CS 2004 Q14 — Relational Model: Relational Algebra

To find the maximum and minimum number of tuples in the natural join $\text{Students} \bowtie \text{Enroll}$, let us analyze the schema and constraints:

1. Common Attribute: The natural join is performed on the common attribute, which is rollno.
2. Primary Key Constraint:
   • In the Students table, rollno is the primary key. This means every rollno in Students is unique.
   • In the Enroll table, (rollno, courseno) is the primary key. Thus, rollno can repeat in Enroll, but each tuple represents a valid enrollment.
3. Referential Integrity: In a standard database schema, Enroll.rollno acts as a foreign key referencing Students.rollno. This means every student enrolled in a course must exist in the Students table.

Using these constraints, we can determine the size of the join:

• Since rollno is unique in Students, any rollno present in Enroll will match with exactly one tuple in Students.
• Since there are $8$ tuples in Enroll, and each of these $8$ tuples matches exactly one tuple in Students, the natural join will yield exactly $8$ tuples.

Therefore, both the maximum and minimum number of tuples in the natural join is $8$.