Part I — Database Fundamentals and Relational Theory

Chapter 3. Relational Algebra and Relational Calculus

SQL lets you ask; relational algebra and calculus let you reason. Before SQL existed, Codd defined two equivalent formal languages for the relational model: an algebra, which composes operations on relations the way arithmetic composes + and ×, and a calculus, which states what a result must satisfy the way logic states a theorem. Every SQL query you will ever write is, underneath, one of these — and Chapter 19 will show that the query optimizer literally rewrites your SQL into algebra, then transforms that algebra into cheaper equivalent forms. Learning the algebra once, formally, is what makes optimization, indexing, and even everyday query debugging comprehensible later.

Both languages are small. The algebra has five primitive operations — selection, projection, Cartesian product, union, and set difference — plus convenient derived forms (join, intersection, rename, division). This chapter defines each operation, exercises it on the university database, and ends by translating algebra into SQL mechanically.

After studying this chapter you will be able to:

• Write selection and projection expressions and predict their results exactly.
• Apply union, intersection, and set difference to compatible relations.
• Explain why the Cartesian product explodes in size and how joins tame it.
• Use rename to make self-joins expressible.
• Distinguish inner, natural, and outer joins and know which SQL clause implements each.
• Express "for all" questions with the division operation.
• Read and write tuple and domain relational calculus expressions.
• Translate any algebra expression into SQL, and division into double NOT EXISTS.

3.1 Selection and projection

Selection σ (sigma) picks rows: σ[condition](R) returns the tuples of R for which the condition is true. Projection π (pi) picks columns: π[A,B](R) returns just attributes A and B of every tuple, with duplicates removed — because relations are sets, and after dropping columns two tuples may become identical.

σ gpa > 3.80 (student)
→  { (21100003, 'Sadia Afrin', 2, 2021, 96, 3.88),
     (21300003, 'Arif Mahmud', 1, 2023, 60, 3.90) }

π full_name, gpa (σ gpa > 3.80 (student))
→  { ('Sadia Afrin', 3.88), ('Arif Mahmud', 3.90) }

π major_dept_id (student)
→  { 1, 2, 3, 4, 5 }        -- duplicates collapse; 12 rows give 5 values

Selection composes with ∧, ∨, ¬: σ[semester = 'Fall' ∧ section_year = 2026](course_section) yields sections 11, 12, and 13 — the three sections running now. Two habits prevent most beginner errors: put single quotes around string constants ('Fall', never Fall), and remember that σ never removes duplicates (it cannot create them) while π always does.

3.2 Union, intersection, and set difference

The three set operations combine two relations row-wise. They require union compatibility: the same attribute names and compatible domains, in the same order. All three remove duplicates, because their results are sets.

Let A = students enrolled in section 11 (ENG105, Fall 2026) and B = students enrolled in section 12 (CSE221, Fall 2026):

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

B = π student_id (σ section_id = 12 (enrollment))
  = { 21300003, 21500002 }

A ∪ B  = { 21100004, 21100006, 21300003, 21300004, 21500002 }   -- enrolled in either
A ∩ B  = { 21500002 }                                            -- Shahriar Islam, in both
A − B  = { 21100004, 21100006, 21300004 }                        -- ENG105 but not CSE221
B − A  = { 21300003 }                                            -- CSE221 but not ENG105

Section 11 and section 12 share exactly one student — Shahriar Islam (21500002), who is taking both Academic Writing and Database Systems this fall. Set difference is the natural home of "rows in one table with no match in another": students with no enrollment at all, or a course with no section. (The canonical dataset has no such student — all 12 are enrolled somewhere — but section 5, CSE321 Spring 2026, has no enrollments, and outer joins in Section 3.5 expose it.)

3.3 Cartesian product

The Cartesian product R × S pairs every tuple of R with every tuple of S: the result's attributes are all of R's followed by all of S's, and its cardinality is |R| × |S|. The product is the algebra's only way to combine two tables' data — and its danger:

student × course_section
→  degree 6 + 7 = 13 attributes, cardinality 12 × 13 = 156 tuples

Almost all 156 pairings are meaningless — Zara Hossain is paired with a 2024 section of CSE215, and so is everyone else. The useful rows are the ones that satisfy the join condition, and that is exactly how the algebra defines a join: product followed by selection. Selecting the product of enrollment and course_section on matching section_id keeps only real pairings:

σ enrollment.section_id = course_section.section_id (enrollment × course_section)
→  28 tuples: each enrollment paired with exactly its own section

The lesson generalizes: never ship the raw product anywhere. SQL never produces a bare product unless you ask for CROSS JOIN (or list two tables with no join condition — the accidental Cartesian product is a classic production bug, recognizable by its enormous row count and glacial speed).

3.4 Rename

Rename ρ (rho) gives a relation, or its attributes, new names: ρ[s2](student) is student under the name s2. Its purpose is enabling self-joins — comparing a relation with itself, which requires two distinguishable "copies."

Which pairs of instructors share a department? Pair instructor with itself, keep pairs with equal dept_id, and break the symmetry with < so each pair appears once and nobody pairs with themselves:

σ i1.dept_id = i2.dept_id ∧ i1.instructor_id < i2.instructor_id
  ( ρ i1 (instructor) × ρ i2 (instructor) )
→  { (101 'Ahmed Kabir', 102 'Farhana Rahman') }     -- both in CSE, dept 1

Exactly one pair: Ahmed Kabir and Farhana Rahman are the university's only co-departmental instructors. Rename also resolves attribute name clashes in products (both tables above carry dept_id; the algebra treats them as i1.dept_id and i2.dept_id). In SQL, rename is the AS alias — Chapter 10 — and self-joins are written exactly this way, with two aliases over one table.

3.5 Inner, outer, and natural joins

The join θ⋈ combines a product with a selection: R ⋈[condition] S = σ[condition](R × S). The common case compares a foreign key with the key it references. The natural join R ⋈ S is the join on equality of all shared attribute names, with the duplicated columns merged away — the algebra's cleanest expression of "match the keys":

π section_id, room, full_name
  ( σ semester = 'Fall' ∧ section_year = 2026 (course_section) ⋈ instructor )
→  { (11, 'AAB-210', 'Tahmina Karim'),      -- ENG105
     (12, 'SAC-401', 'Farhana Rahman'),      -- CSE221
     (13, 'SAC-303', 'Ahmed Kabir') }        -- CSE251

Inner joins drop tuples without partners. Outer joins keep them, padding the missing side with NULLs: a left outer join ⟕ keeps every left tuple, a right outer join ⟖ every right one, and a full outer join ⟗ both. The canonical dataset's built-in example is section 5 — CSE321, Spring 2026, which nobody enrolled in:

π section_id, course_id (course_section ⟕ enrollment)
→  { (1..4, ...), (5, 'CSE321'), (6..13, ...) }     -- section 5 survives, paired with NULLs

An inner join of those tables would silently lose section 5; the left outer join keeps it, and its NULL-padded student columns are the answer to "which sections had no enrollments?" SQL's LEFT/RIGHT/FULL JOIN implements these directly (Chapter 12), with the important dialect note that MySQL has no FULL JOIN — it is emulated with LEFT JOIN ... UNION ... RIGHT JOIN.

3.6 Division operation

Division answers "for all" questions: R ÷ S, where R contains attributes A ∪ B and S exactly B, returns the A-values whose B-sets include every value in S. Formally, a tuple t is in R ÷ S iff for every tuple s in S, t ⋈ s appears in R.

Question. Which students are enrolled in every section of CSE221 offered in Fall 2026?

R = π student_id, section_id (enrollment)
S = π section_id ( σ course_id = 'CSE221' ∧ semester = 'Fall' ∧ section_year = 2026
                   (course_section) )
  = { 12 }

R ÷ S = { 21300003, 21500002 }        -- Arif Mahmud, Shahriar Islam

Because Fall 2026 offers exactly one CSE221 section, the divisor is {12} and the quotient is simply section 12's students. Make the divisor all three Fall 2026 sections — S = {11, 12, 13} — and the answer changes to the empty set: no student is enrolled in every Fall 2026 section, and division says so precisely. Division is derived, not primitive — it can be expressed with product, projection, and difference — and SQL has no ÷ operator; Section 3.9 builds it from double NOT EXISTS.

3.7 Tuple relational calculus

The tuple relational calculus describes results by a predicate over tuple variables: { t | φ(t) }, read "the set of tuples t for which formula φ holds." Formulas use comparisons (∧, ∨, ¬) and the quantifiers ∃t ("there exists a tuple t") and ∀t ("for all tuples t"). The calculus is declarative in the pure sense — it names the desired set, never a procedure.

The chapter's running examples in calculus form:

{ s | student(s) ∧ s.gpa > 3.80 }
  -- the students themselves (Sadia Afrin, Arif Mahmud)

{ s.full_name | student(s) ∧ s.gpa > 3.80 }
  -- just their names

{ s | student(s) ∧ ∀e ( ¬enrollment(e) ∨ e.student_id ≠ s.student_id
                        ∨ e.grade ≠ NULL-pending ) }
  -- illustration of ∀: "students with no in-progress enrollment" is written
  -- as "for every enrollment e, either it is not mine, or it is graded"

The last example shows the shape of universal statements: ∀x φ is ¬∃x ¬φ — "every enrollment of mine is graded" equals "there is no enrollment of mine that is ungraded." That negation trick is the key to Section 3.9's division translation, and it is why SQL has no FOR ALL — NOT EXISTS suffices.

One restriction keeps the calculus computable: formulas must be range-restricted (safe) — every variable must be tied to some relation's extent, so "the set of all tuples not in student" is not a legal query. Codd proved that the safe calculus and the algebra are equivalent in expressive power: each can express exactly the queries of the other. That theorem made both languages the yardstick of relational completeness — a query language is relationally complete if it can express every algebra-expressible query. SQL is relationally complete (its extra features — aggregation, ordering, NULLs — go beyond the model, not short of it).

3.8 Domain relational calculus

The domain relational calculus is the calculus's second form: variables range over domains (values), not tuples, and relations appear as predicates in the style of logical implication — R(x1, ..., xn) means "the tuple (x1, ..., xn) is in R":

{ ⟨fn, g⟩ | ∃sid, m, ay, tc
      ( student(sid, fn, m, ay, tc, g) ∧ g > 3.80 ) }
  -- ('Sadia Afrin', 3.88), ('Arif Mahmud', 3.90)

{ ⟨cs.room⟩ | ∃sid, cid, sem, yr, cap, iid, st, sd, gr
      ( course_section(sid, cid, sem, yr, cs.room, cap, iid)
        ∧ enrollment(st, sd, gr)
        ∧ sd = sid ∧ st = 21600001 ) }
  -- the rooms Zara Hossain studies in this fall: SAC-303

The two calculi are intertranslatable — rename a tuple variable's components as value variables and the formulas coincide — and the domain form is the conceptual ancestor of query-by-example interfaces, where you fill in a blank table and the system infers the predicate. For the rest of this book the tuple form is the one you will see, because its notation matches SQL's row-oriented thinking.

The theory's payoff is a precise statement of what a query language must be able to do. When a vendor claims a product "supports relational queries," the minimum bar is Codd-completeness: express every algebra expression. Both PostgreSQL and MySQL clear the bar — and both then add aggregation, window functions, recursion, and NULL handling, which the pure model never dreamed of.

3.9 Translating relational algebra into SQL queries

Every algebraic construct has a direct SQL spelling. The mechanical dictionary:

Two worked translations. First, a composition — names and majors of the students in ENG105 this fall (section 11):

π s.full_name, d.dept_name
  ( σ e.section_id = 11 ( (ρ e (enrollment) ⋈ student) ⋈ department ) )

SELECT s.full_name, d.dept_name
FROM   enrollment AS e
JOIN   student   AS s ON s.student_id = e.student_id
JOIN   department AS d ON d.dept_id  = s.major_dept_id
WHERE  e.section_id = 11;

 Imran Hossain      | Business Administration
 Sumaiya Tabassum   | English
 Nabil Khan         | Business Administration
 Shahriar Islam    | Electrical and Electronic Engineering

Second, division. "Students enrolled in every Fall 2026 section of CSE221" is the ∀-statement "for this student there does not exist a Fall 2026 CSE221 section in which the student is not enrolled":

SELECT s.full_name
FROM   student AS s
WHERE  NOT EXISTS (
         SELECT 1
         FROM   course_section AS cs
         WHERE  cs.course_id = 'CSE221'
          AND   cs.semester  = 'Fall'
          AND   cs.section_year = 2026
          AND   NOT EXISTS (
                 SELECT 1
                 FROM   enrollment AS e
                 WHERE  e.student_id = s.student_id
                  AND   e.section_id = cs.section_id ) );

 full_name
-------------
 Arif Mahmud
 Shahriar Islam

The double-NOT EXISTS shape — no divisor row for which the subject lacks a match — is the universal translation pattern; Chapter 12 uses it for every "all"/"every" problem from finding students who took every course in a list to classes nobody passed. When you meet such a query in the wild, recognize it: someone is doing division.

Chapter Summary

• Relational algebra (procedural) and relational calculus (declarative) are two equivalent formal languages for the relational model; Codd proved their equivalence, defining relational completeness.
• σ selects rows; π selects columns and removes duplicates; string constants take single quotes.
• Union, intersection, and difference need union-compatible inputs and produce sets.
• The Cartesian product pairs everything (|R|×|S| rows) and is only useful as the substrate of joins; shipping one raw is a classic bug.
• Rename ρ enables self-joins and disambiguates shared attribute names.
• Join = product + selection; natural join matches shared names; outer joins preserve partnerless tuples with NULLs (section 5's emptiness is visible only through an outer join).
• Division answers "for all" questions and is derived, not primitive.
• Tuple calculus quantifies over tuples; domain calculus over values; ∀x φ ≡ ¬∃x ¬φ is the translation workhorse.
• SQL maps algebra mechanically: WHERE, SELECT DISTINCT, JOIN ON, aliases, UNION/INTERSECT/EXCEPT, and double NOT EXISTS for division.

Key Terms

Laboratory Exercises

1. Express in algebra, then run in SQL: students with GPA above 3.80, projected to names. *Expected result: Sadia Afrin, Arif Mahmud — remember DISTINCT if you project.*
2. Compute, using set operations on section-enrollment projections, the students enrolled in both Fall 2026 sections 11 and 12, and those enrolled in 11 but not 12. Expected results: both — {21500002, Shahriar Islam}; 11-but-not-12 — {21100004, 21100006, 21300004}.
3. Predict the cardinality of student × instructor, then verify with SQL CROSS JOIN and COUNT(*). Expected result: 156.
4. Write the self-join that lists instructor pairs sharing a department (use aliases), and confirm there is exactly one pair. Expected result: Ahmed Kabir and Farhana Rahman (both CSE).
5. Show section 5 through a left outer join of course_section to enrollment and count how many rows mention section 5. Expected result: exactly one row, with NULL student columns — CSE321 has no enrollments.
6. Translate the division query of Section 3.9 into SQL yourself, run it, and then change the divisor to all Fall 2026 sections (11, 12, 13) and rerun. Expected results: {Arif Mahmud, Shahriar Islam}, then the empty set.

Review Questions and Exercises

1. Why does projection remove duplicates while selection never does? Projection can make previously distinct tuples identical by dropping distinguishing attributes; selection only filters whole tuples, so it can neither create nor merge them.
2. State the union-compatibility rules, and give one pair of our tables that is compatible and one that is not. Same attribute names, same order, compatible domains. π student_id (enrollment) and π student_id (σ ...) (student) are compatible; student and instructor are not (different degrees and names).
3. Why is the Cartesian product alone almost never the desired result? It pairs every row with every row (|R|×|S|), producing mostly meaningless pairings at combinatorial cost; useful rows require a join condition.
4. Express the join R ⋈[R.a = S.b] S using only primitives. σ[R.a = S.b](R × S).
5. What does the natural join do with shared attribute names, and why do production SQL writers avoid NATURAL JOIN? It equates all shared names and merges the duplicates; NATURAL JOIN's meaning changes silently when a column is added or renamed, so explicit ON conditions are preferred.
6. Section 5 disappears from an inner join but survives a left outer join of course_section to enrollment. Why? Inner joins keep only matched tuples; the left outer join keeps every left tuple, padding missing partners with NULLs — section 5 has no enrollment partner.
7. Define division, then answer: what is π student_id, section_id (enrollment) ÷ π section_id (σ[semester='Fall' ∧ section_year=2026](course_section))? The A-values paired with every divisor value; since no student is in all of sections 11, 12, and 13, the result is empty.
8. Write in tuple calculus: instructors hired after 2019. { i | instructor(i) ∧ i.hire_date > '2019-12-31' } — Farhana Rahman (2020-08-01) and Tahmina Karim (2021-01-10). (Chapter 11 formalizes date comparison.)
9. Why must calculus queries be safe (range-restricted)? Otherwise a formula like "all tuples not in student" denotes an infinite or undecidable set; safety ties every variable to a relation's extent, keeping queries finite and computable.
10. What does relational completeness certify about SQL, and name one SQL feature that goes beyond the pure model. It certifies SQL can express every algebra/calculus query; aggregation (GROUP BY), NULL handling, recursion, and ordering all exceed the pure model.
11. Translate to SQL: π[full_name](σ[gpa < 3.00](student)).

    SELECT full_name
    FROM   student
    WHERE  gpa < 3.00;

    Expected output: Farhan Akter (2.98) — one row; Nabil Khan's 3.05 does not qualify.
12. The double-NOT EXISTS idiom implements which algebra operation, and through which logical equivalence? Division; through ∀x φ ≡ ¬∃x ¬φ — "no divisor row for which the subject lacks a match."

Mini-Project

Build an algebra-to-SQL worksheet for yourself. Take five informational needs of the university — (a) the Fall 2026 timetable with instructor names, (b) departments with no major students, (c) students enrolled in both section 11 and section 12, (d) instructors who have never taught a Fall 2026 section, (e) students enrolled in every section taught by Ahmed Kabir (101) — and for each: write the algebra expression first (using σ, π, ⋈, −, ÷ and ρ as needed), predict the exact result rows on paper from the Appendix H dataset, then implement and run the SQL. Check yourself against the data: (a) 3 rows, (b) none — every department has majors, (c) 1 row (Shahriar Islam), (d) 4 rows (Nazmul Chowdhury, Sharmin Ahmed, Mahmudul Islam, Tahmina Karim), (e) empty — no student is in all three of sections 1, 4, and 13. File the worksheet: it is your personal answer key for Chapter 28's laboratory.