Relational algebra questions usually hide one of two jobs: count the result tuples, or decide whether two expressions always agree. Both jobs become easier when you stop reasoning from symbols alone and write a tiny relation instance. The worked tables below make every match, duplicate removal, and NULL-padded row visible.
Core relational algebra operators
Relational algebra is closed: every operator takes relations as input and returns a relation. Its fundamental and commonly derived operators are:
Operator | Symbol | Main effect |
|---|---|---|
Selection |
| Keeps rows satisfying a predicate |
Projection |
| Keeps columns and removes duplicate tuples |
Union |
| Keeps tuples in either compatible relation |
Difference |
| Keeps tuples in the left relation but not the right |
Cartesian product |
| Pairs every left tuple with every right tuple |
Rename |
| Renames a relation or its attributes |
Intersection |
| Keeps tuples present in both relations |
Join |
| Combines tuples that satisfy a match condition |
Division |
| Answers a "for every" condition |
Relational algebra uses set semantics. Projection removes duplicates. Plain SQL generally uses bag semantics, so SELECT dept may repeat values while relational pi_dept behaves like SELECT DISTINCT dept. The SQL queries and joins guide is the right companion when translating these operators into SQL.
Tuple-count bounds worth deriving
Let r contain m tuples and s contain n tuples. Assume union compatibility where required.
Expression | Minimum | Maximum |
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
For m=5 and n=3, union ranges from max(5,3)=5 to 5+3=8. Intersection ranges from 0 to 3. Difference r-s ranges from max(0,5-3)=2 to 5. Product is exactly 5x3=15.
Now verify those set operations on concrete unary relations P={1,2,3,4} and Q={3,4,5}:
P union Q = {1,2,3,4,5}, so the count is 5.P intersection Q = {3,4}, so the count is 2.P-Q = {1,2}, so the count is 2.Q-P = {5}, so reversing difference changes the count to 1.
Worked inner and outer joins
Use these relation instances:
R.A | R.B |
|---|---|
1 | x |
2 | y |
3 | y |
4 | z |
S.B | S.C |
|---|---|
x | 10 |
y | 20 |
y | 30 |
w | 40 |
The natural join matches on B. The R tuple (1,x) matches one S tuple. Each of (2,y) and (3,y) matches two S tuples. (4,z) matches none. Therefore the inner-join count is 1 + 2 + 2 + 0 = 5.
A | B | C |
|---|---|---|
1 | x | 10 |
2 | y | 20 |
2 | y | 30 |
3 | y | 20 |
3 | y | 30 |
For the left outer join, add one NULL-padded row for unmatched R tuple (4,z). Count: 5+1=6. For the right outer join, preserve unmatched S tuple (w,40). Count: 5+1=6. The full outer join preserves both unmatched tuples. Count: 5+1+1=7.
This example also shows why a join can exceed either input count. Repeated matching values create several combinations even though each input relation itself contains no duplicate tuple.
Join counts under key constraints
Suppose S.B is a primary key and every R.B is a non-NULL foreign key referencing it. Each R tuple matches exactly one S tuple, so R natural join S has exactly m tuples. If the foreign key is nullable or unenforced, some R tuples may not match, and the count can fall below m.
If two relations share no attribute, a natural join has no equality condition and becomes their Cartesian product, with exactly mn tuples. If a question gives only m and n without key, foreign-key, or value-frequency information, do not invent an exact inner-join count. Use the valid range 0 to mn.
Division means "for all"
If Enrolled(student, course) records enrolments and Required(course) lists required courses, then Enrolled division Required returns students enrolled in every required course. One standard construction is:
pi_student(Enrolled) - pi_student((pi_student(Enrolled) x Required) - Enrolled)
The inner difference finds missing student-course pairs. Projecting gives students who miss something. Subtracting them leaves only students with all required pairs.
Query equivalence and safe pushdown
Selection cascades and commutes:
sigma_p(sigma_q(R)) = sigma_q(sigma_p(R)) = sigma_(p AND q)(R).
Selection also pushes through a join when its predicate refers only to one input:
sigma_p(R join S) = sigma_p(R) join S, when p uses only R attributes.
Projection pushdown needs more care. You may remove unused attributes early, but each side must retain its join attributes plus every attribute needed later. Projecting away the join column before the join makes the rewrite wrong or undefined. Selection and projection commute only when the projected attributes retain every attribute mentioned by the selection predicate.
A theta join is a selected Cartesian product:
R join_condition S = sigma_condition(R x S).
For a natural join, equal-name attributes form the equality conditions, followed by a projection that keeps one copy of each common attribute. Rename first when a self-join or same-name collision would make the condition ambiguous.
One classic non-equivalence is projection over difference. Let R={(1,a),(2,b)} and S={(1,b)}. Then R-S=R, so projecting A gives {1,2}. But pi_A(R)-pi_A(S)={1,2}-{1}={2}. A three-tuple counterexample proves that projection does not generally distribute over difference.
How GATE tests relational algebra
Expect exact or extreme tuple counts, translation between algebra and SQL, and equivalent-expression choices. On a counting question, list matches by join value. On an equivalence question, apply a valid law or build a two-row counterexample. The DBMS normalization explained post is a useful next DBMS drill after algebra.
About 2,100 published Database Management System questions in the KnowledgeGate bank provide broader practice. Confirm current paper instructions on the official GATE portal of the organising IIT.
The short version
Derive set-operation bounds from overlap, count joins from actual matching groups, and add unmatched rows only for the preserved side of an outer join. For equivalence, push selection freely only when its attributes belong to that input, and push projection only while retaining join and output attributes.
Recompute the 5, 6, 6, and 7 join counts without the explanation. Then use the GATE Test Series under time pressure, and the GATE category page to choose the next practice block.
