Relational algebra turns each relation into another relation through a sequence of operators. A single university database keeps every input, intermediate relation, and final output visible, so you can predict the result of selection, projection, joins, division, and rewrites. For the broader exam path, use the GATE CS Exam Preparation category.
Relational algebra: the relation-in, relation-out model
Relational algebra is a procedural query language: an expression states which operations to perform and in what sequence. Closure means every operation returns a relation, so its result can feed the next operation. A schema defines the attributes; an instance is the current set of tuples. Classical algebra uses set semantics, so duplicate tuples are not retained.
Our running instance is:
Relation | Schema | Tuples |
|---|---|---|
STUDENT | SID, Name, Dept |
|
COURSE | CID, Title, Credits |
|
ENROLMENT | SID, CID, Grade |
|
Esha has no enrolment. Selection sigma filters rows, projection pi chooses attributes, and rename rho supplies fresh names. Union, intersection, and difference combine compatible relations. Product pairs tuples, join keeps meaningful matches, and division handles “all required values”. Selection, projection, union, difference, product, and rename form the classical core. Join, intersection, and division are derived; outer joins belong to extended algebra.
Selection, projection, and rename with exact outputs
sigma_{Dept='CS'}(STUDENT) keeps the schema (SID, Name, Dept) and returns (101,Asha,CS), (103,Charu,CS), (104,Dev,CS), and (105,Esha,CS). Similarly, sigma_{Grade='A' AND CID='C1'}(ENROLMENT) returns (101,C1,A) and (103,C1,A). Selection changes cardinality, not degree.
pi_{Dept}(STUDENT) = {CS, EE}. Its degree is 1 and cardinality is 2 because projection removes repeated CS values. By contrast, pi_{SID,Dept}(sigma_{Dept='CS'}(STUDENT)) = {(101,CS),(103,CS),(104,CS),(105,CS)}, with degree 2 and cardinality 4.
Rename becomes necessary in a self-join. Let S1=rho_{S1}(STUDENT) and S2=rho_{S2}(STUDENT). Select S1.Dept=S2.Dept AND S1.SID<S2.SID, then project the names. The result is {(Asha,Charu),(Asha,Dev),(Asha,Esha),(Charu,Dev),(Charu,Esha),(Dev,Esha)}. The SID inequality removes self-pairs and mirrored duplicates.
Set operations, compatibility, and Cartesian product
Define DBMS_IDS=pi_{SID}(sigma_{CID='C1'}(ENROLMENT))={101,102,103} and OS_IDS=pi_{SID}(sigma_{CID='C2'}(ENROLMENT))={101,103,104}. Union, intersection, and difference need the same number of attributes with compatible domains, so STUDENT and COURSE cannot be combined directly.
Union:
{101,102,103,104}Intersection:
{101,103}DBMS_IDS minus OS_IDS:{102}OS_IDS minus DBMS_IDS:{104}
Difference is directional; union and intersection are commutative. STUDENT product COURSE has 5 x 4 = 20 tuples and degree 3 + 3 = 6. Samples include (101,Asha,CS,C1,DBMS,4) and (101,Asha,CS,C2,Operating Systems,4). An equijoin equals a selection over a product logically, although a DBMS need not materialise all 20 pairs.
Joins and one complete multi-operator query
Find the names of CS students who earned grade A in a 4-credit course:
pi_{Name}(sigma_{Dept='CS' AND Grade='A' AND Credits=4}(STUDENT join_{STUDENT.SID=ENROLMENT.SID} ENROLMENT join_{ENROLMENT.CID=COURSE.CID} COURSE))
The two equijoins produce 10 matched enrolment tuples because every ENROLMENT SID and CID resolves. Selection leaves (101,Asha,CS,C1,A,DBMS,4), (103,Charu,CS,C1,A,DBMS,4), and (104,Dev,CS,C2,A,Operating Systems,4). Projection returns schema (Name), degree 1, cardinality 3, and {Asha,Charu,Dev}.
Asha’s C3 and Charu’s C4 rows fail because those courses carry 3 credits. Bharat fails the department and grade tests. Esha never enters the inner join. A theta join permits any comparison; these equality conditions make equijoins. A natural join infers equal-name columns and may accidentally use an unintended one. STUDENT left-outer-join ENROLMENT has 11 rows, including (105,Esha,CS,NULL,NULL). See SQL Queries and Joins in DBMS: Worked Join and GROUP BY for the SQL translation.
Division: translating “every required course”
Let REQUIRED(CID)={(C1),(C2),(C3)} and COMPLETED=pi_{SID,CID}(ENROLMENT). Then COMPLETED divide REQUIRED={101,103}. Both SIDs cover C1, C2, and C3; Charu’s extra C4 changes nothing. Bharat lacks C2 and C3, Dev lacks C1, and Esha has no candidate tuple in COMPLETED.
Without division, CANDIDATES=pi_{SID}(COMPLETED)={101,102,103,104}. CANDIDATES product REQUIRED has 4 x 3 = 12 pairs. Subtracting COMPLETED exposes the relevant missing pairs {(102,C2),(102,C3),(104,C1)}. Projecting failing SIDs gives {102,104}; subtracting these from CANDIDATES leaves {101,103}. A query beginning with every STUDENT must also mark Esha as missing all three courses.
An OR over C1, C2, and C3 means “at least one” and returns {101,102,103,104}. It cannot enforce universal qualification.
Equivalent expressions and safe query rewrites
The naive STUDENT product ENROLMENT product COURSE creates 5 x 10 x 4 = 200 tuples before equality filters. Key joins yield 10. Pushing Grade='A' into ENROLMENT leaves 6 rows; pushing Credits=4 into COURSE leaves 2. Their join leaves exactly 101-C1, 103-C1, and 104-C2 before the STUDENT match and name projection.
Selections using one input can move below a join. Consecutive selections can combine or commute. Consecutive projections collapse only if attributes required later survive. Inner joins can often be reordered while preserving conditions and schemas. Project SID away from ENROLMENT and the STUDENT join becomes impossible; project CID away and the COURSE join fails.
Logical equivalence promises the same relation. Physical execution is the optimiser’s chosen plan, not necessarily the written order. Query rewriting is also different from schema normalisation.
GATE-style and interview checks
Trace these facts with a reason: STUDENT has degree 3 and cardinality 5; ENROLMENT has degree 3 and cardinality 10; the CS selection has cardinality 4; department projection has cardinality 2; STUDENT product COURSE has degree 6 and cardinality 20; division has cardinality 2.
Students in DBMS but not OS are {102}; reverse the operands and get {104}. Students in both are {101,103}. “Every required course” needs division or its product-and-difference expansion, not intersection alone. In an interview, narrate the three-row grade-A join pipeline before writing symbols.
Common traps, the short version, and your next step
Keep the corrections concrete: selection changes rows, projection changes attributes; set projection gives {CS,EE}; union needs compatible schemas; {102} is not the reverse difference {104}; product has 20 rows and is not a join; natural join may match unintended names; division means every value and gives {101,103}.
The six-line recap:
Closure makes each result usable as the next input.
Selection filters, projection chooses attributes, and rename disambiguates.
Union, intersection, and difference require compatible relations.
Product pairs everything; join retains matches.
Division expresses “all required values”.
Push selections safely, but never project away a future join key.
The published Relational Algebra for GATE: Count Tuples, Prove Equivalence provides the exam-focused overview of tuple counts and equivalence. Then rebuild the running database and trace every intermediate relation before checking Normalization in DBMS: 1NF to BCNF Rules, Worked Example for schema design. GATE Guidance by Sanchit Sir adds a structured preparation path.
Finally, rebuild STUDENT, COURSE, ENROLMENT, and REQUIRED. Reproduce {Asha,Charu,Dev} and {101,103} without looking back.
