Medium ●●

🔣 Relational Algebra & Calculus

Why it matters: Queries are asked in algebra form: what does an expression compute, how many rows can it return, which expressions are equivalent.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.

Formulas

Union
max(m, n) ≤ |R ∪ S| ≤ m + n
Intersection
0 ≤ |R ∩ S| ≤ min(m, n)
Difference
max(0, m − n) ≤ |R − S| ≤ m
Cross product
|R × S| = m · n (columns add up)
Natural join
0 ≤ |R ⋈ S| ≤ m · n; with join column a key of S: ≤ m
Division
R ÷ S = π_A(R) − π_A((π_A(R) × S) − R)
Theta join
R ⋈_θ S = σ_θ(R × S)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
What does this algebra expression return?
Evaluate step by step on the small sample tables; watch NULLs and duplicates.
★★★
Min / max rows from a join or set operation
Use the size bounds and key / foreign key facts.
★★★
Equivalence of queries and the use of division
Recognise "for all" queries as division or double negation.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

12 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

12 questions · 0 correct of 0 attempted · marks 0 / 20

Year:
GATE 2025 CS1 · Q39MCQ2 marks
Consider two relations describing teams and players in a sports league: teams(tid, tname) and players(pid, pname, tid), where tid, tname are team-id and team-name, and pid, pname, tid are player-id, player-name and the team-id of the player. Which ONE of the following tuple relational calculus queries returns the name of the players who play for the team having tname as 'MI'?
GATE 2024 CS1 · Q35NAT1 mark
Consider the following two relations, R(A, B) and S(A, C). R = {(10, 20), (20, 30), (30, 40), (30, 50), (50, 95)} and S = {(10, 90), (30, 45), (40, 80)}. The total number of tuples obtained by evaluating the expression σB<C(R ⋈R.A=S.A S) is ______.
GATE 2024 CS2 · Q45MCQ2 marks
The relation schema Person(pid, city) describes the city of residence for every person uniquely identified by pid. The following relational algebra operators are available: selection, projection, cross product, and rename. To find the list of cities where at least 3 persons reside, using the above operators, the minimum number of cross product operations that must be used is
GATE 2023 · Q16MCQ1 mark
Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?
GATE 2022 · Q25MSQ1 mark
Consider the following three relations in a relational database: Employee(eId, Name), Brand(bId, bName), Own(eId, bId). Which of the following relational algebra expressions return the set of eIds who own all the brands?
(A) πeId(πeId,bId(Own) / πbId(Brand)).
(B) πeId(Own) − πeId((πeId(Own) × πbId(Brand)) − πeId,bId(Own)).
(C) πeId(πeId,bId(Own) / πbId(Own)).
(D) πeId((πeId(Own) × πbId(Own)) / πbId(Brand)).

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 1 · Q23NAT1 mark
A relation r(A, B) in a relational database has 1200 tuples. The attribute A has integer values ranging from 6 to 20, and the attribute B has integer values ranging from 1 to 20. Assume that the attributes A and B are independently distributed. The estimated number of tuples in the output of σ(A>10) ∨ (B=18)(r) is ______.
GATE 2021 Set 1 · Q27MCQ2 marks
The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key: empAge(empNo, age). Consider the relational algebra expression πempNo(empAge ⋈(age > age1) ρempNo1, age1(empAge)). What does the above expression generate?
GATE 2019 Set 2 · Q55NAT2 marks
Consider the relations P(X, Y, Z), Q(X, Y, T) and R(Y, V). P = {(X1,Y1,Z1), (X1,Y1,Z2), (X2,Y2,Z2), (X2,Y4,Z4)}; Q = {(X2,Y1,2), (X1,Y2,5), (X1,Y1,6), (X3,Y3,1)}; R = {(Y1,V1), (Y3,V2), (Y2,V3), (Y2,V2)}. How many tuples will be returned by the relational algebra query πX(σP.Y=R.Y ∧ R.V=V2(P × R)) − πX(σQ.Y=R.Y ∧ Q.T>2(Q × R))?
GATE 2018 · Q41MCQ2 marks
Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query Q: r ⋈ (σB<5(s)). Let LOJ denote the natural left outer-join operation. Assume that r and s contain no null values. Which one of the following queries is NOT equivalent to Q?
GATE 2017 Set 1 · Q41MCQ2 marks
Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId) and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.
(I) { t | ∃u ∈ EMP (t[EmpName] = u[EmpName] ∧ ∀v ∈ DEPT (t[DeptId] ≠ v[DeptId])) }
(II) { t | ∃u ∈ EMP (t[EmpName] = u[EmpName] ∧ ∃v ∈ DEPT (t[DeptId] ≠ v[DeptId])) }
(III) { t | ∃u ∈ EMP (t[EmpName] = u[EmpName] ∧ ∃v ∈ DEPT (t[DeptId] = v[DeptId])) } Which of the above queries are safe?
GATE 2013 Code A · Q35MCQ2 marks
Consider the relational schema Students(rollno, sname), Courses(courseno, cname), Registration(rollno, courseno, percent). Which of the following queries are equivalent to the English query "Find the distinct names of all students who score more than 90% in the course numbered 107"? (I)
SELECT DISTINCT S.sname
FROM Students AS S, Registration AS R
WHERE R.rollno = S.rollno AND R.courseno = 107 AND R.percent > 90
(II) πsname(σcourseno=107 ∧ percent>90(Registration ⋈ Students)). (III) {T | ∃S ∈ Students, ∃R ∈ Registration (S.rollno = R.rollno ∧ R.courseno = 107 ∧ R.percent > 90 ∧ T.sname = S.sname)}. (IV) {<SN> | ∃SR ∃RP (<SR, SN> ∈ Students ∧ <SR, 107, RP> ∈ Registration ∧ RP > 90)}.
GATE 2012 Code A · Q50MCQ2 marks
Consider the following relations. A = {(12, Arun, 60), (15, Shreya, 24), (99, Rohit, 11)}, B = {(15, Shreya, 24), (25, Hari, 40), (98, Rohit, 20), (99, Rohit, 11)} (both with schema Id, Name, Age), and C(Id, Phone, Area) = {(10, 2200, 02), (99, 2100, 01)}. How many tuples does the result of the relational algebra expression (A ∪ B) ⋈A.Id > 40 ∨ C.Id < 15 C contain? Assume that the schema of A ∪ B is the same as that of A.

Common traps

π removes duplicates in the algebra, but SQL SELECT does not unless DISTINCT is used.
A natural join with no common attribute is a cross product.
Division is for "all", never for "some".
Outer joins are not expressible with σ π ∪ − × alone unless you add NULL padding.