ToolSphere
Back to all articles
student

SQL to Relational Algebra: Worked Examples

2026-10-177 min read

Try it: free SQL to Relational Algebra

Turn SQL into relational algebra and compare query trees

Open →

Every SQL query a database runs is first rewritten as relational algebra: a small set of operations that each take relations in and give a relation out. Translating by hand is a standard exam question, and it is mechanical once you know which clause maps to which operator.

The mapping

SQL Relational algebra Symbol
SELECT columns projection π
WHERE condition selection σ
FROM A, B Cartesian product ×
JOIN … ON condition theta join ⋈
table alias (Employee e) rename ρ
GROUP BY with COUNT, AVG… grouping / aggregation γ
AND, OR, NOT conjunction, disjunction, negation ∧, ∨, ¬

Read the expression inside out: the relations are at the centre, and π is always the outermost operator, because SELECT is applied last.

The examples use the COMPANY schema from Elmasri and Navathe: Employee(fname, ssn, salary, dno), Department(dnumber, dname), Works_On(essn, pno), Project(pnumber, pname, plocation).

1. A simple selection

SELECT fname, salary FROM Employee WHERE salary > 30000
π_{fname, salary}(σ_{salary > 30000}(Employee))

WHERE becomes σ directly on the table; SELECT becomes π around it.

2. OR in the condition

SELECT fname FROM Employee WHERE salary > 30000 OR dno = 5
π_{fname}(σ_{salary > 30000 ∨ dno = 5}(Employee))

AND and OR go inside the σ subscript as ∧ and ∨. (OR could also be written as a union of two selections, but one σ is the usual answer.)

3. A join written with WHERE

SELECT e.fname, d.dname
FROM Employee e, Department d
WHERE e.dno = d.dnumber AND d.dname = 'Research'

The canonical translation is mechanical: product of everything in FROM, one σ with the whole WHERE, one π:

π_{e.fname, d.dname}(σ_{e.dno = d.dnumber ∧ d.dname = 'Research'}(ρ_{e}(Employee) × ρ_{d}(Department)))

It is correct, but the product pairs every employee with every department before anything is filtered. With 1,000 employees and 50 departments that is 50,000 rows to throw almost all of away.

Optimising it

Two heuristics, applied in order:

  1. Push selections down. d.dname = 'Research' mentions only d, so filter Department first.
  2. Turn σ over × into ⋈. A product followed by e.dno = d.dnumber, which compares a column from each side, is exactly a join.
π_{e.fname, d.dname}(ρ_{e}(Employee) ⋈_{e.dno = d.dnumber} σ_{d.dname = 'Research'}(ρ_{d}(Department)))

Now only the one Research row reaches the join.

The query tree

Exams often ask for the tree instead of the one-line form. Leaves are relations, and every operator is a node above its inputs:

            π e.fname, d.dname
                    |
            ⋈ e.dno = d.dnumber
              /             \
     ρ e(Employee)    σ d.dname = 'Research'
                              |
                       ρ d(Department)

4. Three tables with JOIN … ON

SELECT e.fname, p.pname
FROM Employee e
JOIN Works_On w ON e.ssn = w.essn
JOIN Project p ON w.pno = p.pnumber
WHERE p.plocation = 'Houston'

Canonical:

π_{e.fname, p.pname}(σ_{p.plocation = 'Houston'}((ρ_{e}(Employee) ⋈_{e.ssn = w.essn} ρ_{w}(Works_On)) ⋈_{w.pno = p.pnumber} ρ_{p}(Project)))

Optimised, with the Houston filter pushed onto Project:

π_{e.fname, p.pname}((ρ_{e}(Employee) ⋈_{e.ssn = w.essn} ρ_{w}(Works_On)) ⋈_{w.pno = p.pnumber} σ_{p.plocation = 'Houston'}(ρ_{p}(Project)))

JOIN … ON is already a join, so only the push-down applies. Joins in SQL are left-associative, which is why the Employee–Works_On join is the inner one.

5. DISTINCT

SELECT DISTINCT fname FROM Employee
π_{fname}(Employee)

Classical relational algebra works on sets, so π already removes duplicates. SQL keeps duplicates unless you write DISTINCT; plain SELECT fname translates to the same π, and it's worth a sentence in your answer that the bag semantics differ.

6. GROUP BY and aggregates

SELECT dno, COUNT(*), AVG(salary) FROM Employee GROUP BY dno
π_{dno, COUNT(*), AVG(salary)}(γ_{dno, COUNT(*), AVG(salary)}(Employee))

γ groups by the attributes before the aggregates and computes one row per group. Some textbooks write it as {dno}𝒢{COUNT(*), AVG(salary)}; it is the same operator. HAVING becomes a σ on top of γ.

Common mistakes

  • Putting π inside σ. If you project first, the columns the condition needs may be gone. π goes outermost.
  • Pushing a join condition down. Only a condition that mentions a single relation can move below the join.
  • Dropping the aliases. With e and d in the query, write ρ (or qualify every column) so e.dno still means something.
  • Forgetting that × with no condition is not a join. σ is what turns it into one.

Check your answers

The SQL to relational algebra converter translates any SELECT with WHERE, JOIN … ON, aliases and GROUP BY, draws both the canonical and the optimised query tree, and lists each rewrite it made. For the design side of the same course, see attribute closure and candidate keys.

Use the Candidate Key Finder to investigate candidate keys before comparing normal forms.

Looking for other tools?

Explore ToolSphere Homepage →