Relational Algebra

DSA, Database System & Operating System — Data Models, Normalization, and SQL, NEC licence examination syllabus (Nepal Engineering Council).

Relational Algebra

Six primitive operators that can express any relational query — the formal language SQL is compiled into.

🌍 Where this lives: relational algebra is not an academic curiosity — it is the intermediate representation inside every SQL engine. Your query text is parsed into an algebra tree, the optimiser rewrites that tree using algebraic equivalences (push selections down, reorder joins), and only then is a physical plan chosen. When you run EXPLAIN you are reading a decorated algebra tree. That is why WHERE a=1 AND b=2 and WHERE b=2 AND a=1 produce identical plans: both compile to the same algebra. Search "query rewrite algebraic equivalence rules" — the transformations in the optimiser are exactly the identities below.

The six primitive operators

Relational algebra is CLOSED: every operator takes relations and returns a relation, so operations compose. 1. SELECTION σ (sigma) choose ROWS σ_condition(R) σ_{marks > 70}(Student) 2. PROJECTION π (pi) choose COLUMNS π_{attr list}(R) π_{roll, name}(Student) → ELIMINATES DUPLICATES (the result is a set) 3. UNION ∪ R ∪ S rows in R or S (or both) requires UNION COMPATIBILITY 4. SET DIFFERENCE − R − S rows in R but not in S requires union compatibility 5. CARTESIAN PRODUCT × R × S every row of R paired with every row of S |R × S| = |R| × |S| 6. RENAME ρ (rho) ρ_{S(a,b)}(R) rename R to S with attributes a, b essential for self-joins UNION COMPATIBILITY — required for ∪, −, ∩ : · same NUMBER of attributes (same degree) · corresponding attributes drawn from the same DOMAIN Attribute NAMES need not match; positions matter. DERIVED (non-primitive) OPERATORS — expressible using the six: INTERSECTION R ∩ S = R − (R − S) THETA JOIN R ⋈_θ S = σ_θ(R × S) NATURAL JOIN R ⋈ S = π(σ_{common attrs equal}(R × S)) DIVISION R ÷ S (see the worked example) OUTER JOINS ⟕ ⟖ ⟗ (need NULL, so strictly an extension) AGGREGATION 𝓖 (γ) also an extension — the pure algebra has no COUNT or SUM That last point matters: the SIX primitives cannot express aggregation or ordering. Real query languages extend the algebra to add them.

Worked example — each operator on real data

algebra.sql

-- verified against PostgreSQL 18
CREATE TABLE student (roll INT PRIMARY KEY, name TEXT,
                      dept CHAR(6), marks NUMERIC(5,2));
CREATE TABLE course  (code CHAR(8) PRIMARY KEY, title TEXT);
CREATE TABLE enrol   (roll INT, course CHAR(8));

INSERT INTO student VALUES
    (101,'Ram','ACtE07',87.5), (102,'Sita','ACtE07',91.0),
    (103,'Hari','AExE01',55.0), (104,'Gita','AExE01',68.0);
INSERT INTO course VALUES
    ('C1','Database'), ('C2','Circuits'), ('C3','OS');
INSERT INTO enrol VALUES
    (101,'C1'),(101,'C2'),(101,'C3'),
    (102,'C1'),(102,'C3'),
    (103,'C2');
                             -- Gita (104): none

-- ===== SELECTION  σ_{marks > 70}(Student) =====
SELECT * FROM student WHERE marks > 70 ORDER BY roll;
--  roll | name |  dept  | marks
--  -----+------+--------+-------
--   101 | Ram  | ACtE07 | 87.50
--   102 | Sita | ACtE07 | 91.00
--  (2 rows)

-- ===== PROJECTION  π_{dept}(Student) =====
-- Algebra returns a SET, so duplicates vanish.
SELECT DISTINCT dept FROM student ORDER BY dept;
--   dept
--  --------
--  ACtE07
--  AExE01
--  (2 rows)   <- 4 students, 2 departments

-- WITHOUT DISTINCT, SQL keeps duplicates — SQL is a BAG
-- (multiset) algebra, not a set algebra:
SELECT dept FROM student ORDER BY dept;
--   dept
--  --------
--  ACtE07
--  ACtE07
--  AExE01
--  AExE01
--  (4 rows)
--
-- THIS IS THE SINGLE BIGGEST DIFFERENCE between the algebra
-- and SQL. π eliminates duplicates by definition; SELECT
-- does not unless you write DISTINCT.

-- ===== UNION  ∪  vs SQL's UNION ALL =====
SELECT dept FROM student UNION SELECT dept FROM student;
--   dept
--  --------
--  AExE01
--  ACtE07
--  (2 rows)   <- set semantics, duplicates removed

SELECT COUNT(*) FROM (SELECT dept FROM student
                      UNION ALL
                      SELECT dept FROM student) x;
--  count
--  -------
--      8   <- 4 + 4, bag semantics

-- ===== SET DIFFERENCE  −
-- students with NO enrolment =====
SELECT roll FROM student EXCEPT SELECT roll FROM enrol
ORDER BY roll;
--  roll
--  ------
--   104   <- Gita ✔

-- ===== INTERSECTION  ∩  =====
SELECT roll FROM student WHERE marks > 60
INTERSECT
SELECT roll FROM enrol
ORDER BY roll;
--  roll
--  ------
--   101
--   102
--  (2 rows)
-- Gita has marks > 60 but no enrolment; Hari is enrolled but
-- has marks 55. Only Ram and Sita satisfy both.

-- ===== RENAME  ρ  — required for a SELF JOIN.
-- Pairs in the same department where one outscores the
-- other:  σ_{a.marks > b.marks ∧ a.dept = b.dept}
--            (ρ_a(Student) × ρ_b(Student))          =====
SELECT a.name AS higher, b.name AS lower
FROM   student a, student b
WHERE  a.marks > b.marks AND a.dept = b.dept
ORDER  BY a.name;
--  higher | lower
--  --------+-------
--  Gita   | Hari      (68.0 > 55.0, both AExE01)
--  Sita   | Ram       (91.0 > 87.5, both ACtE07)
--  (2 rows)
--
-- Without ρ there is no way to refer to two copies of the
-- same relation. That is the entire purpose of the operator.

The set-versus-bag distinction is the one thing to carry away from this comparison. In the algebra, π is duplicate-eliminating by definition, so π_dept(Student) has exactly two rows. In SQL, SELECT dept FROM student has four. Every textbook algebra answer implicitly assumes DISTINCT, which is why translating algebra to SQL usually means adding it.

Division — the hardest operator

R ÷ S answers "which values in R are associated with ALL of S?" FORMAL DEFINITION Let R have attributes (X, Y) and S have attributes (Y). Then R ÷ S has attributes (X), and contains { x | for EVERY y in S, the tuple (x,y) is in R } EXAMPLE — "students enrolled in every course" Enrol(roll, course) ÷ π_code(Course) Enrol: Course: 101 C1 C1 101 C2 C2 101 C3 C3 102 C1 102 C3 103 C2 roll 101 → {C1,C2,C3} ⊇ {C1,C2,C3} ✔ INCLUDED roll 102 → {C1,C3} missing C2 ✗ roll 103 → {C2} missing C1,C3 ✗ roll 104 → {} missing all ✗ Result: {101} EXPRESSING ÷ WITH THE PRIMITIVES — the classic derivation: R ÷ S = π_X(R) − π_X( (π_X(R) × S) − R ) Read it inside out: π_X(R) all candidate x values π_X(R) × S every (x,y) combination that WOULD be needed (π_X(R) × S) − R the combinations that are MISSING π_X( ... ) the x values that are missing something π_X(R) − ... the x values missing NOTHING ✔ Applied to our data: π_roll(Enrol) = {101,102,103} π_roll(Enrol) × Course = 9 pairs minus Enrol = {(102,C2),(103,C1),(103,C3)} π_roll of that = {102,103} {101,102,103} − {102,103} = {101} ✔ IN SQL — the double-NOT-EXISTS idiom: SELECT s.roll FROM student s WHERE NOT EXISTS ( -- there is no course SELECT c.code FROM course c WHERE NOT EXISTS ( -- that this student SELECT 1 FROM enrol e -- has not taken WHERE e.roll = s.roll AND e.course = c.code)); Read the nesting as: "no course exists such that the student has not taken it" = "the student has taken every course". That double negation is why division is considered the hardest operator to express. THE COUNTING ALTERNATIVE — easier to read and usually faster: SELECT roll FROM enrol GROUP BY roll HAVING COUNT(DISTINCT course) = (SELECT COUNT(*) FROM course); → 101 has 3 distinct courses; there are 3 courses. ✔ Note DISTINCT is required if (roll,course) is not unique.

Algebraic equivalences — what the optimiser uses

These identities are how a query is rewritten into a cheaper but equivalent form. Every one is a theorem, not a heuristic. SELECTION 1. σ_{c1 ∧ c2}(R) ≡ σ_{c1}(σ_{c2}(R)) cascade 2. σ_{c1}(σ_{c2}(R)) ≡ σ_{c2}(σ_{c1}(R)) commutative 3. σ_c(R × S) ≡ R ⋈_c S form a join PROJECTION 4. π_{L1}(π_{L2}(R)) ≡ π_{L1}(R) if L1 ⊆ L2 cascade 5. π and σ commute when σ's attributes ⊆ L JOIN 6. R ⋈ S ≡ S ⋈ R commutative 7. (R ⋈ S) ⋈ T ≡ R ⋈ (S ⋈ T) associative → these two are why an n-way join has n! orderings for the optimiser to choose from PUSHING SELECTION THROUGH A JOIN — the single most valuable rewrite: 8. σ_c(R ⋈ S) ≡ σ_c(R) ⋈ S if c uses only R's attributes WHY IT MATTERS, quantified. Suppose |Student| = 10,000 |Enrol| = 100,000 σ_{dept='ACtE07'} selects 1,000 students BAD PLAN — join first, filter after: Student ⋈ Enrol → ~100,000 intermediate rows then σ → keep ~10,000 cost ≈ 100,000 rows processed GOOD PLAN — filter first, then join: σ_{dept='ACtE07'}(Student) → 1,000 rows then ⋈ Enrol → ~10,000 rows cost ≈ 10,000 rows processed → 10× less work, identical answer PUSHING PROJECTION DOWN 9. π_L(R ⋈ S) ≡ π_L( π_{L∪join attrs}(R) ⋈ π_{...}(S) ) Drop unneeded columns early so intermediate rows are narrower and more fit in each buffer page. SET OPERATIONS 10. R ∪ S ≡ S ∪ R, R ∩ S ≡ S ∩ R commutative 11. R − S ≢ S − R NOT commutative 12. σ_c(R ∪ S) ≡ σ_c(R) ∪ σ_c(S) distributes THE HEURISTIC OPTIMISATION RECIPE, applied in this order: 1. break conjunctive selections into a cascade (rule 1) 2. push each selection as far down the tree as possible (rule 8) 3. convert σ over × into a join (rule 3) 4. push projections down (rule 9) 5. reorder joins so the most restrictive is evaluated first (rules 6, 7) Steps 2 and 5 are where nearly all the gain is.

optimise.sql

-- The same query written two ways. Logically identical;
-- the optimiser produces the same plan for both, which is
-- itself the proof that the rewrite rules are being applied.

-- WRITTEN NAIVELY: product then filter
EXPLAIN (COSTS OFF)
SELECT s.name, c.title
FROM   student s, enrol e, course c
WHERE  s.roll = e.roll
  AND  e.course = c.code
  AND  s.dept = 'ACtE07';

-- WRITTEN OPTIMALLY: filter pushed down by hand
EXPLAIN (COSTS OFF)
SELECT s.name, c.title
FROM   (SELECT roll, name FROM student WHERE dept='ACtE07') s
JOIN   enrol e  ON e.roll = s.roll
JOIN   course c ON c.code = e.course;

-- ACTUAL PLAN from PostgreSQL 18 (both forms give this):
--
--   Nested Loop
--     ->  Hash Join
--           Hash Cond: (e.roll = s.roll)
--           ->  Seq Scan on enrol e
--           ->  Hash
--                 ->  Seq Scan on student s
--                       Filter: (dept = 'ACtE07'::bpchar)
--                                ^^^^^^^ pushed DOWN ✔
--     ->  Index Scan using course_pkey on course c
--           Index Cond: (code = e.course)
--
-- Read it bottom-up. The filter on dept sits at the SCAN of
-- student, not above the joins — rule 8 applied
-- automatically. Note also that the optimiser chose two
-- DIFFERENT join algorithms: a hash join for student/enrol
-- (no useful index on enrol.roll) and a nested loop with an
-- index scan for course (a primary-key lookup per row).
-- Algebra decides WHAT; the planner decides HOW.
--
-- You do not need to hand-optimise: the optimiser applies
-- rule 8 for you. But knowing the rule tells you WHY the
-- plan looks like that, and lets you spot the cases where
-- it CANNOT push a predicate down — for example through an
-- OUTER join, or when the predicate calls a
-- non-deterministic function.

Extended operators — aggregation and outer joins

The six primitives cannot express COUNT, SUM or NULL-padding. Practical algebra adds: AGGREGATION 𝓖 (also written γ) grouping-attrs 𝓖 aggregate-list (R) dept 𝓖 COUNT(roll), AVG(marks) (Student) → SELECT dept, COUNT(roll), AVG(marks) FROM Student GROUP BY dept; With no grouping attributes it aggregates the whole relation: 𝓖 COUNT(*)(Student) → SELECT COUNT(*) FROM Student OUTER JOINS — need NULL, which the pure algebra lacks R ⟕ S LEFT outer join (keep unmatched R rows) R ⟖ S RIGHT outer join R ⟗ S FULL outer join GENERALISED PROJECTION — allows computed columns π_{roll, marks * 1.1 AS scaled}(Student) The pure π may only choose existing attributes. WHY THE DISTINCTION MATTERS FOR EXAMS: if a question says "express in relational algebra" and the answer needs a count or an average, you must use 𝓖 and say so. Writing COUNT inside a σ is wrong — σ takes a per-row predicate and cannot see other rows. ✗ σ_{COUNT(*) > 2}(Enrol) ✔ σ_{cnt > 2}( roll 𝓖 COUNT(*) AS cnt (Enrol) ) That is the algebraic form of the WHERE-versus-HAVING distinction: σ before 𝓖 is WHERE, σ after 𝓖 is HAVING.

🌍 Go further: relational algebra is procedural — you specify an order of operations. Its declarative twin is relational calculus (tuple and domain calculus), where you state a logical condition and specify no order at all. Codd's theorem proves the two have equal expressive power, which is the formal justification for SQL being declarative: you write the what, the optimiser derives a how. Datalog and modern query languages descend from the calculus side. Search "Codd's theorem relational completeness" and "tuple relational calculus vs algebra".

💡 Exam angle: know the six primitives with their symbols (σ π ∪ − × ρ) and which operators are derived (∩, joins, ÷). State union compatibility as the requirement for ∪, − and ∩. The guaranteed hard question is division: give the "associated with ALL" meaning, the derivation π_X(R) − π_X((π_X(R) × S) − R), and the double-NOT EXISTS SQL form. Know the key equivalence rules, especially pushing selection below a join, and be ready to quantify why it helps. Remember π eliminates duplicates while SELECT does not.

Syllabus points

Select, project, union, set difference, join (numerical)

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.