Consider the following relation schema pertaining to a students database:…
Consider the following relation schema pertaining to a students database:
student(rollno, name, address)
enroll(rollno, course no, course name)
where the primary keys are shown underlined. The number of tuples in student and enroll are 100 and 50 respectively. What is the maximum and minimum number of tuples that can be present in (student ⋈ enroll), where ⋈ denotes natural join?
Answer: 50 — ConceptA natural join R ⋈ S pairs each tuple of R with each tuple of S that agree on their shared attribute. Two facts fix the size of the result. First, how…
Attempted by 171 students.
Show answer & explanation
Correct answer: 50
Concept
A natural join R ⋈ S pairs each tuple of R with each tuple of S that agree on their shared attribute. Two facts fix the size of the result. First, how that attribute behaves as a key: if it is a primary key in BOTH relations it is unique on each side, so the match is at most one-to-one and the result can never exceed the smaller relation. Second, whether a referential-integrity (foreign-key) constraint guarantees that every value on the referencing side also exists on the referenced side; when it does, every referencing tuple is guaranteed to find its one match.
Application to this schema
The only shared attribute is rollno — student’s "name" and enroll’s "course name" are different attributes, so they are not join columns. rollno is the primary key of student (100 distinct values) and the primary key of enroll (50 distinct values). In this students database enroll.rollno is a foreign key that refers to student.rollno: a roll number can be enrolled only if that student already exists (referential integrity). This is the assumption the standard answer to this classic GATE problem uses.
rollno is unique in student, so each enroll tuple matches at most one student tuple — the join is one-to-one.
By referential integrity every one of the 50 enroll rollno values is guaranteed to occur in student, so each enroll tuple matches exactly one student tuple.
Each enroll tuple therefore contributes exactly one result tuple, and students that have no enrollment add nothing, so the join contains exactly 50 tuples.
Because the count is pinned to exactly 50, the maximum and the minimum coincide: maximum = 50 and minimum = 50. The single value to enter is 50.
Cross-check / contrast
Upper bound: the result cannot exceed min(100, 50) = 50, because rollno is a key on both sides (one-to-one matching). Lower bound: referential integrity forces every enroll tuple to have a parent in student, so the count cannot fall below 50. Both bounds meet at 50, so the answer is fixed. Note on the variant: if one does NOT assume the foreign-key/referential-integrity link — treating the two rollno columns as unrelated — the enroll roll numbers could all be absent from student and the minimum would drop to 0. The standard/official answer to this problem assumes the natural student→enroll referential integrity, giving minimum = maximum = 50, which is why the single NAT answer is 50.