Appendices

Appendix E. Relational Algebra Notation

The notation of Chapter 3, consolidated: operators, symbols, formal reading, an equivalent SQL form, and a canonical university example for each.

Notation table

Operation	Symbol	Reads as	SQL equivalent
Selection	σ[c](R)	rows of R where c holds	`WHERE`
Projection	π[A,B](R)	columns A, B of R, deduplicated	`SELECT DISTINCT A, B`
Cartesian product	R × S	every tuple of R paired with every tuple of S	`CROSS JOIN`
Theta join	R ⋈[c] S	σ[c](R × S)	`JOIN ... ON c`
Natural join	R ⋈ S	join on all shared attribute names, merged	`NATURAL JOIN`
Inner/outer joins	R ⟕ S, R ⟖ S, R ⟗ S	keep unmatched left / right / both with NULL padding	`LEFT/RIGHT/FULL JOIN`
Rename	ρ[S](R) or ρ[S(A1..An)](R)	R under a new name / new attribute names	`AS`
Union	R ∪ S	rows in R or S (duplicates collapse; union-compatible)	`UNION`
Intersection	R ∩ S	rows in both	`INTERSECT`
Difference	R − S	rows in R not in S	`EXCEPT`
Division	R ÷ S	A-values of R paired with every S value	double `NOT EXISTS`

Derived operators: join = select-after-product; intersection = union+difference; division = product/projection/difference.

The five primitives

Selection, projection, Cartesian product, union, and difference generate every relational operation (with rename as a notational convenience). The algebra is closed: every operation consumes relations and produces relations, so expressions compose.

Worked examples (canonical data)

σ gpa > 3.80 (student)
→  Sadia Afrin (3.88), Arif Mahmud (3.90)

π full_name, gpa (σ gpa > 3.80 (student))
→  the same two students, two columns

A = π student_id (σ section_id = 11 (enrollment))   → {21100004, 21100006, 21300004, 21500002}
B = π student_id (σ section_id = 12 (enrollment))    → {21300003, 21500002}

A ∪ B  → five students
A ∩ B  → {21500002}              (Shahriar Islam, in both sections)
A − B  → {21100004, 21100006, 21300004}

σ i1.dept_id = i2.dept_id ∧ i1.instructor_id < i2.instructor_id (ρ i1(instructor) × ρ i2(instructor))
→  (Ahmed Kabir, Farhana Rahman) — the only co-departmental pair

π section_id (σ course_id='CSE221' ∧ semester='Fall' ∧ section_year=2026 (course_section))
= {12};   R ÷ {12} → {21300003, 21500002}   (Arif Mahmud, Shahriar Islam)

Calculus notation (tuple and domain forms)

Tuple calculus:      { t | student(t) ∧ t.gpa > 3.80 }
  (and projections)   { t.full_name | student(t) ∧ t.gpa > 3.80 }

Domain calculus:     { ⟨fn, g⟩ | ∃ sid, m, ay, tc
                         ( student(sid, fn, m, ay, tc, g) ∧ g > 3.80 ) }

Universal via negation:  ∀x φ  ≡  ¬∃x ¬φ
  (the shape behind every NOT EXISTS "all/every" query)

Codd's theorem: the safe (range-restricted) calculus and the algebra are equivalent in expressive power — the definition of relational completeness. SQL is relationally complete, with aggregation, ordering, NULLs, and recursion exceeding the pure model.

Translation dictionary (algebra → SQL)

σ[c](R)                 →  FROM R WHERE c
π[A](R)                 →  SELECT DISTINCT A FROM R
R × S                   →  FROM R CROSS JOIN S
R ⋈[c] S                →  FROM R JOIN S ON c
ρ x(R)                  →  FROM R AS x
R ∪ S / R ∩ S / R − S   →  UNION / INTERSECT / EXCEPT
R ÷ S                   →  WHERE NOT EXISTS (... NOT EXISTS (...))