In the previous chapters you learned what a relation is, what keys are, and which integrity constraints keep the data valid. Now comes the obvious next question: how do we ask a relational database for information?
Before SQL existed, E. F. Codd defined a small mathematical language for exactly this purpose. It is called Relational Algebra, and it is still the foundation that every SQL engine is built on. When you write a SQL query, the database first translates it into an internal tree of relational-algebra-style operators (the basis of a "query plan") and then decides how to execute it.
Relational Algebra is a procedural query language consisting of a set of operators. Each operator takes one or two relations as input and produces a new relation as output.
Two words in that definition matter a lot:
Procedural means you describe how to get the result: first filter this, then join with that, then keep these columns.
Relation in, relation out means the output of one operator can be fed into another operator. This property is called closure, and it is what lets us build big queries out of small pieces, just like arithmetic expressions such as
(2 + 3) × 4.
Why Learn Relational Algebra?
It explains SQL. Every
WHERE,SELECTcolumn list,JOIN,UNIONandEXCEPTmaps to a relational algebra operator.It explains query optimization. The optimizer rewrites one algebra expression into an equivalent but cheaper one (for example, filtering before joining).
It is heavily tested. GATE and university exams regularly ask you to write an expression, or to find the output or the number of tuples of a given expression.
Sample Relations Used in This Chapter
We will use a tiny university database with three relations. The data was loaded into MySQL 8.4, so every SQL result shown later is real output. Remember that a relation is a set, so row order has no meaning; where the order matters for display, the SQL uses ORDER BY.
Student(sid, name, dept, age)
Course(cid, title, dept, credits)
Enrolled(sid, cid)Student
+-----+--------+------+------+
| sid | name | dept | age |
+-----+--------+------+------+
| 1 | Asha | CSE | 20 |
| 2 | Bharat | ECE | 21 |
| 3 | Chitra | CSE | 22 |
| 4 | Dev | ME | 20 |
| 5 | Esha | CSE | 21 |
| 6 | Farhan | ECE | 22 |
+-----+--------+------+------+
Course
+-----+----------+------+---------+
| cid | title | dept | credits |
+-----+----------+------+---------+
| C1 | DBMS | CSE | 4 |
| C2 | OS | CSE | 4 |
| C3 | Signals | ECE | 3 |
| C4 | Networks | ECE | 3 |
+-----+----------+------+---------+
Enrolled
+-----+-----+
| sid | cid |
+-----+-----+
| 1 | C1 |
| 1 | C2 |
| 1 | C3 |
| 2 | C3 |
| 3 | C1 |
| 3 | C2 |
| 4 | C1 |
| 5 | C2 |
+-----+-----+Notice two things we will use later: Farhan (sid 6) is not enrolled in any course, and nobody is enrolled in C4 (Networks).
Overview of the Operators
Operator | Symbol | Type | What it does |
|---|---|---|---|
Selection | σ | Unary, fundamental | Keeps rows that satisfy a condition |
Projection | π | Unary, fundamental | Keeps chosen columns, removes duplicate rows |
Rename | ρ | Unary, fundamental | Renames a relation or its attributes |
Union | ∪ | Binary, fundamental | Rows in either relation |
Set Difference | − | Binary, fundamental | Rows in the first but not the second |
Cartesian Product | × | Binary, fundamental | Every row of one paired with every row of the other |
Intersection | ∩ | Binary, derived | Rows present in both |
Join | ⋈ | Binary, derived | Product followed by selection |
Division | ÷ | Binary, derived | "For all" queries |
The first six are the fundamental operators. Everything else can be written using them, so the derived operators exist only for convenience. You may also see a slightly different "basic set" in some books (some leave out ρ because attributes can be referred to by position), but this six-operator set is the most common one.
1. Selection (σ)
Selection picks rows (tuples) that satisfy a condition, called the predicate.
σ[condition](R)In books the condition is written as a small subscript under σ. In this tutorial's code blocks we write the subscript in square brackets, so σ[dept = 'CSE'] means σ with the subscript dept = 'CSE'. The same applies to π, ρ and ⋈.
The condition can use comparison operators (=, ≠, <, ≤, >, ≥) and can combine them with ∧ (AND), ∨ (OR) and ¬ (NOT).
Example: All CSE students
σ[dept = 'CSE'](Student)In SQL this is a WHERE clause:
SELECT * FROM Student WHERE dept = 'CSE';+-----+--------+------+------+
| sid | name | dept | age |
+-----+--------+------+------+
| 1 | Asha | CSE | 20 |
| 3 | Chitra | CSE | 22 |
| 5 | Esha | CSE | 21 |
+-----+--------+------+------+Example: CSE students older than 20
σ[dept = 'CSE' ∧ age > 20](Student)+-----+--------+------+------+
| sid | name | dept | age |
+-----+--------+------+------+
| 3 | Chitra | CSE | 22 |
| 5 | Esha | CSE | 21 |
+-----+--------+------+------+Key properties of selection:
The output has the same columns as the input.
The number of output rows is between
0and|R|.Selection is commutative:
σ[c1](σ[c2](R)) = σ[c2](σ[c1](R)) = σ[c1 ∧ c2](R). The optimizer uses this to apply the most selective filter first.
2. Projection (π)
Projection picks columns (attributes).
π[A1, A2, ..., Ak](R)Because a relation is a set of tuples, the result cannot contain duplicates. So projection automatically removes duplicate rows.
Example: Which departments do students belong to?
π[dept](Student)Student has 6 rows, but the answer has only 3, because CSE and ECE repeat:
+------+
| dept |
+------+
| CSE |
| ECE |
| ME |
+------+This is where SQL behaves differently. SQL tables are bags (multisets), not sets, so a plain SELECT dept FROM Student returns all 6 values including repeats. To get true projection you must write DISTINCT:
SELECT DISTINCT dept FROM Student;π in relational algebra = SELECT DISTINCT in SQL, not plain SELECT.
Combining σ and π
Names of students older than 20:
π[name](σ[age > 20](Student))Read it from the inside out: first filter rows, then keep the name column.
+--------+
| name |
+--------+
| Bharat |
| Chitra |
| Esha |
| Farhan |
+--------+Note that the order of σ and π matters when the projection drops a column used by the condition. σ[age > 20](π[name](Student)) is invalid, because after the projection there is no age column left to test.
3. Rename (ρ)
Rename gives a new name to a relation (and optionally to its attributes):
ρ[S](Student) rename the relation to S
ρ[S(id, nm, d, a)](Student) rename the relation and all attributesWhy would you need it? Mainly for self-joins, when a relation has to be compared with itself. Without renaming, Student × Student would have two columns both called Student.age, and we could not tell them apart. With ρ[S1](Student) × ρ[S2](Student) we can write S1.age < S2.age. In SQL, ρ is the table alias (FROM Student S1) or a column alias (AS).
4. Set Operations: Union, Intersection, Difference
These work exactly like set operations in mathematics, but with one rule: the two relations must be union-compatible (also called type-compatible):
Both must have the same number of attributes.
The i-th attribute of both must come from the same domain.
So Student ∪ Course is invalid, but two single-column relations of student ids are fine. Let us define:
A = π[sid](σ[dept = 'CSE'](Student)) = {1, 3, 5} CSE students
B = π[sid](σ[cid = 'C1'](Enrolled)) = {1, 3, 4} students taking C1Expression | Meaning | Result | SQL (MySQL 8.0.31+) |
|---|---|---|---|
A ∪ B | CSE students or taking C1 | {1, 3, 4, 5} |
|
A ∩ B | CSE students taking C1 | {1, 3} |
|
A − B | CSE students not taking C1 | {5} |
|
B − A | Taking C1 but not from CSE | {4} |
|
The SQL for A − B, run on MySQL 8.4:
SELECT sid FROM Student WHERE dept = 'CSE'
EXCEPT
SELECT sid FROM Enrolled WHERE cid = 'C1';+-----+
| sid |
+-----+
| 5 |
+-----+Important facts:
∪ and ∩ are commutative; − is not (A − B ≠ B − A, as the table shows).
Intersection is not fundamental:
A ∩ B = A − (A − B). Check: A − B = {5}, and {1, 3, 5} − {5} = {1, 3}.Sizes:
max(|A|, |B|) ≤ |A ∪ B| ≤ |A| + |B|,0 ≤ |A ∩ B| ≤ min(|A|, |B|),0 ≤ |A − B| ≤ |A|.
5. Cartesian Product (×)
The Cartesian product (cross product) pairs every row of the first relation with every row of the second.
If R has n1 rows and a1 attributes, and S has n2 rows and a2 attributes:
R × S has n1 × n2 rows and a1 + a2 attributes.For our data, Student × Course has 6 × 4 = 24 rows and 4 + 4 = 8 attributes. Here is a smaller product that fits on screen: ME students paired with CSE courses.
π[name](σ[dept = 'ME'](Student)) × π[cid](σ[dept = 'CSE'](Course))SELECT S.name, C.cid
FROM Student S CROSS JOIN Course C
WHERE S.dept = 'ME' AND C.dept = 'CSE'
ORDER BY C.cid;+------+-----+
| name | cid |
+------+-----+
| Dev | C1 |
| Dev | C2 |
+------+-----+On its own the product is rarely meaningful (it pairs every student with every course whether or not they are related). Its real use is as the first step of a join: build all combinations, then keep only the sensible ones.
6. Joins (⋈)
Theta Join
A theta join is a Cartesian product followed by a selection:
R ⋈[θ] S = σ[θ](R × S)θ can be any condition using =, ≠, <, ≤, >, ≥. As an example, pairs of CSE students where the first is younger than the second (a self-join, so we rename):
π[S1.name, S2.name](σ[S1.dept='CSE' ∧ S2.dept='CSE'](ρ[S1](Student) ⋈[S1.age < S2.age] ρ[S2](Student)))In SQL (the two name columns are given the aliases younger and older):
SELECT S1.name AS younger, S2.name AS older
FROM Student S1 JOIN Student S2 ON S1.age < S2.age
WHERE S1.dept = 'CSE' AND S2.dept = 'CSE'
ORDER BY younger, older;+---------+--------+
| younger | older |
+---------+--------+
| Asha | Chitra |
| Asha | Esha |
| Esha | Chitra |
+---------+--------+Equi Join
An equi join is a theta join where θ uses only equality. Students paired with courses offered by their own department:
Student ⋈[Student.dept = Course.dept] CourseSELECT S.name, S.dept, C.title
FROM Student S JOIN Course C ON S.dept = C.dept
ORDER BY S.sid, C.cid;+--------+------+----------+
| name | dept | title |
+--------+------+----------+
| Asha | CSE | DBMS |
| Asha | CSE | OS |
| Bharat | ECE | Signals |
| Bharat | ECE | Networks |
| Chitra | CSE | DBMS |
| Chitra | CSE | OS |
| Esha | CSE | DBMS |
| Esha | CSE | OS |
| Farhan | ECE | Signals |
| Farhan | ECE | Networks |
+--------+------+----------+Dev (ME) is missing, because no course has dept = 'ME'. Remember this; outer joins fix it.
Natural Join
The natural join R ⋈ S (no subscript) is the most used join in exams:
Take R × S.
Keep only rows where all attributes with the same name have equal values.
Keep only one copy of each common attribute.
Student ⋈ Enrolled (common attribute: sid)SELECT * FROM Student NATURAL JOIN Enrolled;+-----+--------+------+------+-----+
| sid | name | dept | age | cid |
+-----+--------+------+------+-----+
| 1 | Asha | CSE | 20 | C1 |
| 1 | Asha | CSE | 20 | C2 |
| 1 | Asha | CSE | 20 | C3 |
| 2 | Bharat | ECE | 21 | C3 |
| 3 | Chitra | CSE | 22 | C1 |
| 3 | Chitra | CSE | 22 | C2 |
| 4 | Dev | ME | 20 | C1 |
| 5 | Esha | CSE | 21 | C2 |
+-----+--------+------+------+-----+Notice sid appears once, and Farhan (no enrollments) disappears.
Two edge cases examiners love:
If R and S have no common attribute,
R ⋈ S = R × S.A natural join matches every common name.
Student ⋈ Coursewould match ondept, which is probably fine here, butStudent ⋈ Enrolled ⋈ Coursematches Enrolled–Course oncidand then also forcesStudent.dept = Course.dept. That silently drops Asha's ECE course C3 and Dev's CSE course C1. Accidental name matches are the classic natural-join bug, so project away unwanted columns first.
Outer Joins (Extended Relational Algebra)
An inner join loses rows that have no match. Outer joins keep them and fill the missing side with NULL.
Join | Symbol | Keeps unmatched rows from |
|---|---|---|
Left outer join | ⟕ | Left relation |
Right outer join | ⟖ | Right relation |
Full outer join | ⟗ | Both relations |
π[sid, name, cid](Student ⟕ Enrolled)+-----+--------+------+
| sid | name | cid |
+-----+--------+------+
| 1 | Asha | C1 |
| 1 | Asha | C2 |
| 1 | Asha | C3 |
| 2 | Bharat | C3 |
| 3 | Chitra | C1 |
| 3 | Chitra | C2 |
| 4 | Dev | C1 |
| 5 | Esha | C2 |
| 6 | Farhan | NULL |
+-----+--------+------+Farhan is back, with NULL for cid. Outer joins are not part of Codd's original algebra (which has no NULLs); they belong to the extended relational algebra. MySQL supports LEFT JOIN and RIGHT JOIN but not FULL OUTER JOIN; you emulate it with a UNION of a left and a right join.
7. Division (÷)
Division answers "for all" questions, such as:
Find students who are enrolled in ALL courses offered by CSE.
Let r(A, B) and s(B). Then r ÷ s returns every value a such that, for every b in s, the pair (a, b) is in r.
r = Enrolled(sid, cid)
s = π[cid](σ[dept = 'CSE'](Course)) = {C1, C2}
Enrolled ÷ s:
sid 1 → {C1, C2, C3} contains C1 and C2 ✓
sid 2 → {C3} ✗
sid 3 → {C1, C2} ✓
sid 4 → {C1} ✗
sid 5 → {C2} ✗
Result = {1, 3}Division Using Basic Operators
Division is derived. The trick is to find the students who are missing at least one required course, and remove them.
r ÷ s = π[A](r) − π[A]( (π[A](r) × s) − r )Step by step on our data:
Step 1: π[sid](Enrolled) = {1, 2, 3, 4, 5}
Step 2: Step1 × s = every (sid, required course) pair, 5 × 2 = 10 rows
Step 3: Step2 − Enrolled = pairs that SHOULD exist but don't
= {(2,C1), (2,C2), (4,C2), (5,C1)}
Step 4: π[sid](Step3) = {2, 4, 5} students missing something
Step 5: Step1 − Step4 = {1, 3}Step 3 was run in MySQL to confirm (sorted by sid, cid):
SELECT E.sid, C.cid
FROM (SELECT DISTINCT sid FROM Enrolled) E CROSS JOIN Course C
WHERE C.dept = 'CSE'
AND (E.sid, C.cid) NOT IN (SELECT sid, cid FROM Enrolled)
ORDER BY E.sid, C.cid;+-----+-----+
| sid | cid |
+-----+-----+
| 2 | C1 |
| 2 | C2 |
| 4 | C2 |
| 5 | C1 |
+-----+-----+SQL has no division operator. The usual translation is a double NOT EXISTS: "there is no CSE course that this student is not enrolled in".
SELECT DISTINCT E.sid
FROM Enrolled E
WHERE NOT EXISTS (
SELECT * FROM Course C
WHERE C.dept = 'CSE'
AND NOT EXISTS (
SELECT * FROM Enrolled E2
WHERE E2.sid = E.sid AND E2.cid = C.cid));+-----+
| sid |
+-----+
| 1 |
| 3 |
+-----+If we divide by all four courses instead, the answer is empty, because nobody takes C4. A "for all" query becomes empty as soon as one required value has no takers.
Worked Examples
Example 1: Names of students enrolled in DBMS
π[name]( σ[title = 'DBMS']( Student ⋈ Enrolled ⋈ π[cid, title](Course) ) )We project Course to (cid, title) first so the natural join does not also match on dept. Result: Asha, Chitra, Dev.
A better plan (same answer, less work) pushes the selection down before the join:
π[name]( Student ⋈ Enrolled ⋈ π[cid](σ[title = 'DBMS'](Course)) )Both expressions are equivalent, but the second joins with 1 course row instead of 4. This "push selections down" rewrite is exactly what a query optimizer does (covered in the Query Processing & Optimization chapter).
Example 2: The oldest age, without MAX
Basic relational algebra has no aggregate functions, yet we can still find the maximum. Idea: an age is not the maximum if some other age is larger.
π[age](Student) − π[S1.age]( σ[S1.age < S2.age]( ρ[S1](Student) × ρ[S2](Student) ) )
π[age](Student) = {20, 21, 22}
ages smaller than some other age = {20, 21}
Result = {22}This "subtract the ones that lose a comparison" pattern is a favourite exam question. Flip < to > to get the minimum.
Example 3: Students not enrolled in any course
π[sid](Student) − π[sid](Enrolled) = {1,2,3,4,5,6} − {1,2,3,4,5} = {6} (Farhan)Extended Operators (Brief)
Real systems need more than the classic operators, so textbooks add an extended relational algebra:
Generalized projection: arithmetic in the projection list, e.g.
π[title, credits × 2](Course).Aggregation (γ):
[dept]γ[count(sid), avg(age)](Student)groups by dept, like SQLGROUP BY.Outer joins, which you have already seen.
SELECT dept, COUNT(*) AS cnt, AVG(age) AS avg_age FROM Student GROUP BY dept;+------+-----+---------+
| dept | cnt | avg_age |
+------+-----+---------+
| CSE | 3 | 21.0000 |
| ECE | 2 | 21.5000 |
| ME | 1 | 20.0000 |
+------+-----+---------+Relational Algebra vs SQL
Relational Algebra | SQL |
|---|---|
σcondition |
|
πcolumns |
|
ρ | Table alias / |
∪, ∩, − |
|
× |
|
⋈θ |
|
⋈ (natural) |
|
÷ | No operator; double |
Works on sets (no duplicates) | Works on bags (duplicates kept unless |
Procedural: says how | Declarative: says what |
Common Mistakes
Forgetting that π removes duplicates. If asked for the number of tuples in
π[dept](Student), the answer is 3, not 6.Projecting away a column before selecting on it. The inner operator must still have every attribute the outer one needs.
Using set operations on incompatible relations. Always check arity and domains first.
Accidental common attributes in a natural join. Rename or project first.
Mixing up the sides of division. The divisor's attributes must be a subset of the dividend's, and the result has the dividend's remaining attributes.
Assuming joins keep unmatched rows. Only outer joins do.
Interview and Exam Questions
Q1. Which operators are fundamental in relational algebra?
Selection, projection, union, set difference, Cartesian product and rename. Intersection, joins and division can all be expressed using them.
Q2. R has 10 tuples and S has 5. What are the minimum and maximum sizes of R ⋈ S (natural join)?
Minimum 0 (no matching values). Maximum 50, which happens when every tuple matches every tuple, for example when there are no common attributes and the join becomes R × S.
Q3. How is intersection expressed using difference?
R ∩ S = R − (R − S).
Q4. When would you use division?
For "for all" questions: students who took all courses, suppliers who supply all parts, customers who bought every product in a category.
Q5. What is the difference between theta join, equi join and natural join?
A theta join allows any comparison condition. An equi join allows only equality. A natural join is an equi join on all same-named attributes that also keeps only one copy of each common attribute.
Q6. Is relational algebra procedural or non-procedural?
Procedural. The expression specifies the sequence of operations. Relational calculus, covered in the next chapter, is the non-procedural counterpart.
Summary
Relational algebra is a procedural language of operators that take relations and return relations, so expressions can be nested.
σ filters rows, π keeps columns and removes duplicates, ρ renames.
∪, ∩, − need union-compatible relations; × pairs every row with every row.
Joins are a product plus a selection; natural join matches all same-named attributes; outer joins keep unmatched rows with NULLs.
Division answers "for all" queries and equals
π[A](r) − π[A]((π[A](r) × s) − r).SQL is built on relational algebra but works with bags, so π corresponds to
SELECT DISTINCT.
Next, in Relational Calculus, we will express the same queries declaratively by describing what the result should satisfy rather than how to compute it.