Relational algebra and its SQL
Part of the free LogicWiz SQL & Databases course, Module 16: Inside the DBMS. The queries and practice run in the app on real Postgres.
The exam paper says: write π_name(σ_{cgpa>9}(Students)). Riya freezes, then realises it is just SELECT DISTINCT name FROM students WHERE cgpa > 9. Every algebra symbol has a SQL twin.
You'll learn to
- Read and write select, project, join, rename and the set operators
- Translate an algebra expression into SQL and back
- Do relational division in SQL with NOT EXISTS and with GROUP BY
Learn
Algebra: operators on tables
Relational algebra is the maths behind SQL. Each operator takes one or two relations (tables) and gives back a new relation, so you can chain them like + and × in school maths.
- σ (sigma), select: keep the rows that pass a condition.
- π (pi), project: keep some columns.
- ⋈ (bowtie), join: combine matching rows of two relations.
- ∪, ∩, −: union, intersection, difference of two relations.
- ×: cross product, every row with every row.
- ρ (rho): rename.
We type the condition or column list after an underscore: σ_{city=Delhi}(students) is σ with city = Delhi written small below it. One thing to remember: a relation is a set, so it never has duplicate rows.
Each operator and its SQL
| Algebra | Means | SQL |
|---|---|---|
| σcond(R) | rows where cond is true | SELECT FROM R WHERE cond |
| π{a,b}(R) | columns a, b, no duplicates | SELECT DISTINCT a, b FROM R |
| R × S | every pair of rows | SELECT FROM R CROSS JOIN S |
| R ⋈cond S | pairs that match | SELECT FROM R JOIN S ON cond |
| R ∪ S | in either | R UNION S |
| R ∩ S | in both | R INTERSECT S |
| R − S | in R, not in S | R EXCEPT S |
| ρT(R) | rename R to T | FROM R AS T |
∪, ∩ and − need union-compatible relations: the same number of columns, with matching types, in the same order.
σ then π
-- π name, city ( σ city = 'Delhi' (students) )
SELECT DISTINCT name, city
FROM students
WHERE city = 'Delhi';
Read algebra from the inside out: first σ filters the rows, then π picks the columns.
Projection removes duplicates, SQL does not
SELECT COUNT(city) AS sql_rows,
COUNT(DISTINCT city) AS algebra_rows
FROM students;
π_city(students) has 13 rows, one per city. SELECT city FROM students returns 20, with Delhi three times. SQL works on bags (multisets), algebra on sets.
Difference: students with no enrollment
-- π student_id (students) − π student_id (enrollments)
SELECT student_id FROM students
EXCEPT
SELECT student_id FROM enrollments;
EXCEPT, like algebra's −, removes duplicates. Only Aditya (114) has never enrolled.
Division: "for every"
R ÷ S answers questions with every or all in them: students who took every course in the list.
If R(student, course) and S(course), then R ÷ S gives each student who is paired in R with all the courses in S.
SQL has no ÷, so we say it the long way round, with a double negative:
a student such that there is no required course that they did not take.
That sentence becomes NOT EXISTS (... NOT EXISTS (...)), as the next card shows.
Takes ÷ Required, by hand
| Takes(student, course) | Required(course) | Takes ÷ Required |
|---|---|---|
| Aarav DBMS, Aarav OS, Aarav CN | DBMS | Aarav |
| Meher DBMS, Meher OS | OS | |
| Riya DBMS, Riya CN, Riya Maths | CN | |
| Kabir OS |
Only Aarav has all three. Meher misses CN; Riya misses OS (her Maths does not help). In basic operators: R ÷ S = π_A(R) − π_A((π_A(R) × S) − R), where A is the student column.
Division in SQL: students who took every CS course
SELECT s.student_id, s.name
FROM students s
WHERE NOT EXISTS (
SELECT 1
FROM courses c
WHERE c.dept_id = 1
AND NOT EXISTS (
SELECT 1
FROM enrollments e
WHERE e.student_id = s.student_id
AND e.course_id = c.course_id
)
);
For each student: is there a CS course with no enrollment row for them? If not, keep the student. Only Arjun took all four CS courses. The other way is GROUP BY student HAVING COUNT(DISTINCT course) = (SELECT COUNT(*) FROM required), after joining to the required list.
Exams ask for tuple counts. If |R| = r and |S| = s: R × S has exactly r·s rows; σ(R) and π(R) have at most r; R ∪ S has between max(r, s) and r + s; R ∩ S at most min(r, s); R − S at most r; R ⋈ S anything from 0 to r·s. They also ask which operators are basic: σ, π, ×, ∪, −, ρ. Join, ∩ and ÷ can be built from those.
In one line
σ = WHERE, π = SELECT DISTINCT, ⋈ = JOIN, ∪ ∩ − = UNION INTERSECT EXCEPT, and ÷ ("for every") = double NOT EXISTS.
Interview corner
How do you write relational division in SQL?
With a double NOT EXISTS: keep x when there is no y in the divisor that x is not paired with. Or join to the divisor, GROUP BY x HAVING COUNT(DISTINCT y) = (SELECT COUNT(*) FROM divisor). Typical question: customers who bought every product in a category.
How is SQL different from relational algebra?
Algebra works on sets: no duplicate rows and no order. SQL works on bags, so SELECT keeps duplicates unless you write DISTINCT, and it adds NULLs, aggregates, ORDER BY and LIMIT. UNION, INTERSECT and EXCEPT remove duplicates like algebra; their ALL versions keep them.
What is a natural join and why is it risky?
R ⋈ S with no condition joins on all columns with the same name and keeps one copy of each. In SQL, NATURAL JOIN does the same. It is risky because adding an unrelated column with a shared name (like name or city) silently changes the join. Write JOIN ... ON or USING (col) instead.