Division, grouping and extended relational algebra

Division answers “for all” questions. For relations R(A, B) and S(B), R ÷ S returns the values of A that R pairs with every tuple of S: with Enrolled(sid, cid) and a list of core courses Core(cid), Enrolled ÷ Core is the set of students who took every core course. Division is not a core operator, because it can be written as π A (R) − π A ((π A (R) × S) − R), a formula this lesson takes apart step by step. Extended relational algebra adds what the core lacks for everyday questions: grouping with aggregation (γ), which counts, sums and averages per group, generalised projection, which computes new values such as credits times grade points, duplicate elimination (δ), sorting (τ), and versions of union, intersection and difference that work on bags, as SQL’s do. Along the way, three SQL forms of division meet an empty divisor, and they return three different answers.

What division answers

Take the enrolments without their grades, R(sid, cid), and the three core courses of the college in S(cid): CS201, CS202 and MA101. A student belongs to R ÷ S when R holds a tuple (sid, c) for every course c in S:

The result’s heading is A, the attributes of R that are not in S. Asha (sid 1) took CS201, CS202 and MA101, and Esha (sid 5) took them too, plus HS101: extra courses do not matter. Chitra took two of the three, Bilal and Dev one each, so Enrolled ÷ Core holds sids 1 and 5.

The questions division answers have “every”, “all” or “each” in them: the suppliers who supply every part, the customers who bought every product of a category, the employees who worked on all the projects of their department. The divisor S is the “every” list, and the dividend R holds the pairs that may cover it.

Division from the core operators

The definition talks about “every”, which none of the six core operators says. The formula turns “every” into “not missing any”: find the candidates that miss at least one tuple of S, and remove them.

Read from the inside: π A (R) lists the candidates. Pairing every candidate with every tuple of S gives all the pairs that R would have to contain. Subtracting R leaves the pairs that are missing, and projecting those on A gives the candidates that miss something. The candidates that remain are the answer. E. F. Codd gave this reduction, in his own notation, in the 1972 paper that defined his relational algebra, and noted there that division is the algebra’s counterpart of the universal quantifier.

"""Division R(A, B) ÷ S(B), by its definition and by the formula built from the core operators."""
from itertools import chain, combinations, product

# Enrolled reduced to (sid, cid), and the core courses every student is meant to take.
ENROLLED = {(1, "CS201"), (1, "CS202"), (1, "MA101"), (2, "EC210"), (2, "MA101"), (3, "CS201"),
            (3, "MA101"), (4, "MA101"), (5, "CS201"), (5, "CS202"), (5, "MA101"), (5, "HS101")}
CORE = {"CS201", "CS202", "MA101"}


def by_definition(R, S):
    """The a values of R that are paired in R with every b of S."""
    return {a for (a, _) in R if all((a, b) in R for b in S)}


def by_formula(R, S, show=False):
    """π A (R) − π A ((π A (R) × S) − R)"""
    candidates = {a for (a, _) in R}                         # π A (R)
    every_pair = {(a, b) for a in candidates for b in S}     # π A (R) × S
    missing = every_pair - R                                 # ... − R
    short = {a for (a, _) in missing}                        # π A (...)
    if show:
        print(f"  π sid (Enrolled)              {len(candidates):>2} tuples  {sorted(candidates)}")
        print(f"  that × Core                   {len(every_pair):>2} tuples")
        print(f"  that − Enrolled               {len(missing):>2} tuples  {sorted(missing)}")
        print(f"  π sid of the missing pairs    {len(short):>2} tuples  {sorted(short)}")
        print(f"  π sid (Enrolled) − that       {len(candidates - short):>2} tuples  {sorted(candidates - short)}")
    return candidates - short


print("Enrolled ÷ Core, step by step:")
by_formula(ENROLLED, CORE, show=True)

# Every R over A × B and every S over B, for small A and B: the formula never disagrees with the definition.
A, B = (1, 2, 3), ("p", "q", "r")
pairs = list(product(A, B))
all_r = list(chain.from_iterable(combinations(pairs, k) for k in range(len(pairs) + 1)))
all_s = list(chain.from_iterable(combinations(B, k) for k in range(len(B) + 1)))
checked = disagreements = 0
for R in map(set, all_r):
    for S in map(set, all_s):
        checked += 1
        disagreements += by_definition(R, S) != by_formula(R, S)
print(f"\n{checked:,} pairs (R, S) checked, {disagreements} disagreements")

print("\nEdge cases:")
print("  Core empty: Enrolled ÷ {} =", sorted(by_formula(ENROLLED, set())))
print("  Enrolled empty: {} ÷ Core =", sorted(by_formula(set(), CORE)))

Enrolled ÷ Core, step by step:
  π sid (Enrolled)               5 tuples  [1, 2, 3, 4, 5]
  that × Core                   15 tuples
  that − Enrolled                5 tuples  [(2, 'CS201'), (2, 'CS202'), (3, 'CS202'), (4, 'CS201'), (4, 'CS202')]
  π sid of the missing pairs     3 tuples  [2, 3, 4]
  π sid (Enrolled) − that        2 tuples  [1, 5]

4,096 pairs (R, S) checked, 0 disagreements

Edge cases:
  Core empty: Enrolled ÷ {} = [1, 2, 3, 4, 5]
  Enrolled empty: {} ÷ Core = []

The five candidates and the three core courses make 15 pairs that would all have to be enrolments. Five of them are not: Bilal missed two core courses, Chitra one and Dev two. Removing sids 2, 3 and 4 leaves 1 and 5. The program then tries every R over three values of a and three of b against every S over the same b values, 4,096 pairs of relations, and the formula never disagrees with the definition.

Two edge cases come out of the run. If S is empty, “for every b in S” is true of everything, so R ÷ S is all of π A (R): students 1 to 5. If R is empty, there are no candidates, and Codd’s paper says so explicitly: when R is empty, R divided by S is empty, even if S is empty too.

Note which candidates division considers: only the values of A that appear in R. Farhan, who has no enrolment, is not in π sid (Enrolled), so he can never be in Enrolled ÷ Core, not even when Core is empty. To divide over all students, put π sid (Student) in place of π A (R) in both places of the formula.

Division in SQL, and the empty divisor

SQL has no division operator. The standard way to write “every” is a double negation: a student qualifies when no core course exists that the student has not taken. Each “no … exists” is a NOT EXISTS subquery, and since an EXISTS test only asks whether a row exists, the nesting carries no risk of duplicate rows. A second common way counts: a student qualifies when the number of different core courses they took equals the number of core courses. The program writes three versions as one view, runs it, empties the core list and runs it again:

CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
CREATE TABLE core (cid TEXT PRIMARY KEY);
INSERT INTO student VALUES
  (1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
  (4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO enrolled VALUES
  (1, 'CS201', 'A'), (1, 'CS202', 'B'), (1, 'MA101', 'A'), (2, 'EC210', 'A'),
  (2, 'MA101', 'B'), (3, 'CS201', 'B'), (3, 'MA101', 'A'), (4, 'MA101', 'C'),
  (5, 'CS201', 'A'), (5, 'CS202', 'A'), (5, 'MA101', 'B'), (5, 'HS101', 'A');
INSERT INTO core VALUES ('CS201'), ('CS202'), ('MA101');

-- Three ways to ask for the students who took every core course.
CREATE VIEW answers AS
-- 1. Double NOT EXISTS over all students: no core course exists that the student has not taken.
SELECT 'NOT EXISTS, candidates from student' AS method, count(*) AS answers,
       coalesce(group_concat(sid, ', ' ORDER BY sid), '(none)') AS sids
FROM student s
WHERE NOT EXISTS (SELECT 1 FROM core c
                  WHERE NOT EXISTS (SELECT 1 FROM enrolled e WHERE e.sid = s.sid AND e.cid = c.cid))
UNION ALL
-- 2. The same test with the candidates taken from enrolled, as R ÷ S takes them from R.
SELECT 'NOT EXISTS, candidates from enrolled', count(*),
       coalesce(group_concat(sid, ', ' ORDER BY sid), '(none)')
FROM (SELECT DISTINCT sid FROM enrolled) r
WHERE NOT EXISTS (SELECT 1 FROM core c
                  WHERE NOT EXISTS (SELECT 1 FROM enrolled e WHERE e.sid = r.sid AND e.cid = c.cid))
UNION ALL
-- 3. Counting: as many different core courses taken as there are core courses.
SELECT 'GROUP BY and count', count(*), coalesce(group_concat(sid, ', ' ORDER BY sid), '(none)')
FROM (SELECT e.sid FROM enrolled e
      WHERE e.cid IN (SELECT cid FROM core)
      GROUP BY e.sid
      HAVING count(DISTINCT e.cid) = (SELECT count(*) FROM core));

SELECT * FROM answers;

-- The college drops its core list for a term: "every core course" is now true of every student.
DELETE FROM core;
SELECT * FROM answers;

┌──────────────────────────────────────┬─────────┬──────┐
│                method                │ answers │ sids │
├──────────────────────────────────────┼─────────┼──────┤
│ NOT EXISTS, candidates from student  │ 2       │ 1, 5 │
│ NOT EXISTS, candidates from enrolled │ 2       │ 1, 5 │
│ GROUP BY and count                   │ 2       │ 1, 5 │
└──────────────────────────────────────┴─────────┴──────┘
┌──────────────────────────────────────┬─────────┬──────────────────┐
│                method                │ answers │       sids       │
├──────────────────────────────────────┼─────────┼──────────────────┤
│ NOT EXISTS, candidates from student  │ 6       │ 1, 2, 3, 4, 5, 6 │
│ NOT EXISTS, candidates from enrolled │ 5       │ 1, 2, 3, 4, 5    │
│ GROUP BY and count                   │ 0       │ (none)           │
└──────────────────────────────────────┴─────────┴──────────────────┘

With three core courses, all three versions agree on sids 1 and 5. With an empty core list they give three answers:

• NOT EXISTS over student returns all 6 students. No core course exists, so none is missing for anyone, Farhan included. This is the plain reading of “took every core course” when there are none.
• NOT EXISTS over the sids of enrolled returns the 5 students who have any enrolment. It is exactly Enrolled ÷ Core, because its candidates come from R, as the algebra’s do.
• GROUP BY with count returns nobody. It first keeps the enrolments in core courses, of which there are none, so no group is left to compare with a count of 0.

None of the three is wrong in itself, but only the first two agree with the definition of “every”. The counting form also needs care in normal use: it must keep only enrolments in divisor courses (an extra course would otherwise make up for a missing one) and count distinct courses (a duplicated enrolment would otherwise count twice). Prefer the double NOT EXISTS, and choose its outer table by deciding who the candidates are.

Extended operators: grouping, computing and sorting

The core algebra can find the courses with the most credits, but it cannot count or add up anything. Extended relational algebra adds operators for that, each with a direct SQL counterpart:

• Grouping and aggregation, written γ grouping attributes; aggregates (R): one tuple per group, with an aggregate function such as count, sum, avg, min or max computed over the group. γ branch; count(sid) → students (Student) gives one tuple per branch. With no grouping attributes, the whole relation is one group.
• Generalised projection, π with expressions: π sid, credits × 10 → hours (R) computes a new attribute from old ones, the way a SELECT list can.
• Duplicate elimination, δ (R), which removes repeated tuples from a bag; on sets it changes nothing.
• Sorting, τ attributes (R), which orders the result. A relation has no order, so τ only makes sense at the root of an expression, like ORDER BY at the end of a query.
• Outer joins, from the previous lesson, which need NULL and so are not part of the core either.

CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
INSERT INTO student VALUES
  (1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
  (4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
INSERT INTO course VALUES
  ('CS201', 'Databases', 'CSE', 4), ('CS202', 'Operating Systems', 'CSE', 4),
  ('CS301', 'Compilers', 'CSE', 4), ('MA101', 'Discrete Mathematics', 'MATH', 3),
  ('EC210', 'Signals and Systems', 'ECE', 3), ('HS101', 'Technical Writing', 'HSS', 2);
INSERT INTO enrolled VALUES
  (1, 'CS201', 'A'), (1, 'CS202', 'B'), (1, 'MA101', 'A'), (2, 'EC210', 'A'),
  (2, 'MA101', 'B'), (3, 'CS201', 'B'), (3, 'MA101', 'A'), (4, 'MA101', 'C'),
  (5, 'CS201', 'A'), (5, 'CS202', 'A'), (5, 'MA101', 'B'), (5, 'HS101', 'A');

-- γ branch; count(sid) → students (Student): one tuple per group.
SELECT branch, count(sid) AS students FROM student GROUP BY branch;

-- Generalised projection (grade points, on a 10-point scale with A = 10, B = 8, C = 6), then
-- γ sid; sum(credits), sum(points × credits) / sum(credits) → the credit-weighted average, sorted (τ).
SELECT e.sid, sum(c.credits) AS credits,
       round(sum(CASE e.grade WHEN 'A' THEN 10 WHEN 'B' THEN 8 WHEN 'C' THEN 6 END * c.credits) * 1.0
             / sum(c.credits), 2) AS weighted_points
FROM enrolled e JOIN course c ON c.cid = e.cid
GROUP BY e.sid
ORDER BY weighted_points DESC;

-- Aggregates over no rows: count gives 0 and sum gives NULL, while grouping gives no groups at all.
SELECT count(*) AS f_grades, quote(sum(c.credits)) AS f_credits,
       (SELECT count(*) FROM (SELECT grade FROM enrolled WHERE grade = 'F' GROUP BY grade)) AS f_groups
FROM enrolled e JOIN course c ON c.cid = e.cid WHERE e.grade = 'F';

┌────────┬──────────┐
│ branch │ students │
├────────┼──────────┤
│ CSE    │ 3        │
│ ECE    │ 2        │
│ ME     │ 1        │
└────────┴──────────┘
┌─────┬─────────┬─────────────────┐
│ sid │ credits │ weighted_points │
├─────┼─────────┼─────────────────┤
│ 5   │ 13      │ 9.54            │
│ 1   │ 11      │ 9.27            │
│ 2   │ 6       │ 9.0             │
│ 3   │ 7       │ 8.86            │
│ 4   │ 3       │ 6.0             │
└─────┴─────────┴─────────────────┘
┌──────────┬───────────┬──────────┐
│ f_grades │ f_credits │ f_groups │
├──────────┼───────────┼──────────┤
│ 0        │ NULL      │ 0        │
└──────────┴───────────┴──────────┘

The second query combines all three. A generalised projection turns each grade into points on a 10-point scale (A is 10, B is 8 and C is 6 in this example) and multiplies them by the course’s credits; γ sid adds those up per student and divides by the student’s credits; τ sorts the result. Esha’s 124 points over 13 credits give 9.54. Farhan has no row, because he has no enrolment to group: as with division, an aggregate only sees the tuples its input has.

The last query shows aggregates over no rows. count returns 0, but sum returns NULL: PostgreSQL’s manual makes the same point about its own aggregates, all of which give NULL over an empty input except count, so that the sum of nothing is NULL rather than 0. Grouped by grade, the same empty input gives no group at all, so a GROUP BY query returns no rows where the ungrouped query returned one. That is the same effect that made the counting form of division return nobody.

Bags: the algebra that SQL uses

An SQL table can hold the same row twice, so SQL works with bags (multisets), in which each tuple has a multiplicity. The bag versions of the set operators count copies: a tuple that appears m times in R and n times in S appears m + n times in the bag union R ⊎ S, min(m, n) times in the bag intersection and max(m − n, 0) times in the bag difference. These are the rules of SQL’s ALL operators; PostgreSQL’s manual gives the last two for INTERSECT ALL (“min(m,n) times”) and EXCEPT ALL (“max(m-n,0) times”). SQLite has UNION ALL, but not INTERSECT ALL or EXCEPT ALL.

"""Bag (multiset) versions of union, intersection and difference, the way SQL's ALL operators count."""
from collections import Counter
import sqlite3

# The branches of the students in two tutorial groups: a bag, because a branch can appear more than once.
group_1 = Counter(["CSE", "CSE", "ECE", "ME"])
group_2 = Counter(["CSE", "ECE", "ECE"])


def show(label, bag):
    print(f"  {label:40} {sorted(bag.elements())}")


show("group 1", group_1)
show("group 2", group_2)
show("union, m + n copies (UNION ALL)", group_1 + group_2)
show("intersection, min(m, n) (INTERSECT ALL)", group_1 & group_2)
show("difference, max(m − n, 0) (EXCEPT ALL)", group_1 - group_2)
show("set union (UNION)", Counter(set(group_1) | set(group_2)))

# SQLite has UNION ALL, so the first bag operation can be checked against a real engine.
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE g1 (branch TEXT)")
db.execute("CREATE TABLE g2 (branch TEXT)")
db.executemany("INSERT INTO g1 VALUES (?)", [(b,) for b in group_1.elements()])
db.executemany("INSERT INTO g2 VALUES (?)", [(b,) for b in group_2.elements()])
rows = Counter(b for (b,) in db.execute("SELECT branch FROM g1 UNION ALL SELECT branch FROM g2"))
print("  SQLite's UNION ALL gives the same bag:", rows == group_1 + group_2)

# A law of sets that bags break: R ∪ R = R.
print("  R ∪ R = R for sets:", set(group_1) | set(group_1) == set(group_1),
      "| for bags:", group_1 + group_1 == group_1)

  group 1                                  ['CSE', 'CSE', 'ECE', 'ME']
  group 2                                  ['CSE', 'ECE', 'ECE']
  union, m + n copies (UNION ALL)          ['CSE', 'CSE', 'CSE', 'ECE', 'ECE', 'ECE', 'ME']
  intersection, min(m, n) (INTERSECT ALL)  ['CSE', 'ECE']
  difference, max(m − n, 0) (EXCEPT ALL)   ['CSE', 'ME']
  set union (UNION)                        ['CSE', 'ECE', 'ME']
  SQLite's UNION ALL gives the same bag: True
  R ∪ R = R for sets: True | for bags: False

Python’s Counter implements exactly these rules with +, & and -, and SQLite’s UNION ALL gives the same bag as +. Most algebraic laws survive the move to bags, such as selection distributing over union, but some do not: R ∪ R = R holds for sets, while R ⊎ R has every tuple twice. An optimiser that rewrites SQL must use the bag laws, because duplicates change counts and sums.

What relational algebra cannot express

Some questions are beyond every expression of the algebra, extended or not. A classic one is the transitive closure of a relation: with a relation Prereq(course, needs), list every course with all its prerequisites, direct and indirect, to any depth. A. V. Aho and J. D. Ullman proved in 1979 that relational algebra cannot express it. The intuition is that an expression has a fixed number of joins, so it can follow chains of prerequisites only up to a fixed length, and a chain one step longer escapes it. SQL closes the gap with recursive queries: in PostgreSQL’s words, RECURSIVE lets a WITH query “refer to its own output”, which is what following a chain of any length needs. A later lesson of this track covers recursive queries and Datalog.

Exercises

-- The students enrolled in every course of the department named in target.
SELECT s.name
FROM student s;

# Sample tests: each one builds the tables, runs your query on them and compares the rows it returns (in any order).
tests:
  - name: "a department with one course: everyone who took MA101"
    setup: |
      CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
      CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
      CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
      CREATE TABLE target (dept TEXT NOT NULL);
      INSERT INTO target VALUES ('MATH');
      INSERT INTO student VALUES
        (1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
        (4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
      INSERT INTO course VALUES
        ('CS201', 'Databases', 'CSE', 4), ('CS202', 'Operating Systems', 'CSE', 4),
        ('CS301', 'Compilers', 'CSE', 4), ('MA101', 'Discrete Mathematics', 'MATH', 3),
        ('EC210', 'Signals and Systems', 'ECE', 3), ('HS101', 'Technical Writing', 'HSS', 2);
      INSERT INTO enrolled VALUES
        (1, 'CS201', 'A'), (1, 'CS202', 'B'), (1, 'MA101', 'A'), (2, 'EC210', 'A'),
        (2, 'MA101', 'B'), (3, 'CS201', 'B'), (3, 'MA101', 'A'), (4, 'MA101', 'C'),
        (5, 'CS201', 'A'), (5, 'CS202', 'A'), (5, 'MA101', 'B'), (5, 'HS101', 'A');
    expected:
      columns: [name]
      rows:
        - [Asha]
        - [Bilal]
        - [Chitra]
        - [Dev]
        - [Esha]
  - name: "a department with two courses: only the students who took both"
    setup: |
      CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
      CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
      CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
      CREATE TABLE target (dept TEXT NOT NULL);
      INSERT INTO target VALUES ('CSE');
      INSERT INTO student VALUES (10, 'Ravi', 'ECE'), (11, 'Meena', 'CSE'), (12, 'Kiran', 'ME'), (13, 'Lata', 'ME');
      INSERT INTO course VALUES
        ('CS201', 'Databases', 'CSE', 4), ('CS250', 'Computer Networks', 'CSE', 4),
        ('ME110', 'Mechanics', 'ME', 3), ('HS102', 'Ethics', 'HSS', 2);
      INSERT INTO enrolled VALUES
        (10, 'CS250', 'B'), (11, 'CS201', 'A'), (11, 'CS250', 'A'),
        (12, 'CS201', 'B'), (12, 'CS250', 'C'), (12, 'ME110', 'A');
    expected:
      columns: [name]
      rows:
        - [Meena]
        - [Kiran]
  - name: "a department with no courses: every student, also those with no enrolment"
    setup: |
      CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
      CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
      CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
      CREATE TABLE target (dept TEXT NOT NULL);
      INSERT INTO target VALUES ('LAW');
      INSERT INTO student VALUES
        (1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
        (4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
      INSERT INTO course VALUES
        ('CS201', 'Databases', 'CSE', 4), ('CS202', 'Operating Systems', 'CSE', 4),
        ('CS301', 'Compilers', 'CSE', 4), ('MA101', 'Discrete Mathematics', 'MATH', 3),
        ('EC210', 'Signals and Systems', 'ECE', 3), ('HS101', 'Technical Writing', 'HSS', 2);
      INSERT INTO enrolled VALUES
        (1, 'CS201', 'A'), (1, 'CS202', 'B'), (1, 'MA101', 'A'), (2, 'EC210', 'A'),
        (2, 'MA101', 'B'), (3, 'CS201', 'B'), (3, 'MA101', 'A'), (4, 'MA101', 'C'),
        (5, 'CS201', 'A'), (5, 'CS202', 'A'), (5, 'MA101', 'B'), (5, 'HS101', 'A');
    expected:
      columns: [name]
      rows:
        - [Asha]
        - [Bilal]
        - [Chitra]
        - [Dev]
        - [Esha]
        - [Farhan]

-- Every other student enrolled in all the courses the target student is enrolled in.
SELECT s.name
FROM student s
WHERE s.sid <> (SELECT sid FROM target);

# Sample tests: each one builds the tables, runs your query on them and compares the rows it returns (in any order).
tests:
  - name: the students who took all of Asha's courses, Asha left out
    setup: |
      CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
      CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
      CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
      CREATE TABLE target (sid INTEGER NOT NULL);
      INSERT INTO target VALUES (1);
      INSERT INTO student VALUES
        (1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
        (4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
      INSERT INTO course VALUES
        ('CS201', 'Databases', 'CSE', 4), ('CS202', 'Operating Systems', 'CSE', 4),
        ('CS301', 'Compilers', 'CSE', 4), ('MA101', 'Discrete Mathematics', 'MATH', 3),
        ('EC210', 'Signals and Systems', 'ECE', 3), ('HS101', 'Technical Writing', 'HSS', 2);
      INSERT INTO enrolled VALUES
        (1, 'CS201', 'A'), (1, 'CS202', 'B'), (1, 'MA101', 'A'), (2, 'EC210', 'A'),
        (2, 'MA101', 'B'), (3, 'CS201', 'B'), (3, 'MA101', 'A'), (4, 'MA101', 'C'),
        (5, 'CS201', 'A'), (5, 'CS202', 'A'), (5, 'MA101', 'B'), (5, 'HS101', 'A');
    expected:
      columns: [name]
      rows:
        - [Esha]
  - name: the students who took all of Chitra's courses
    setup: |
      CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
      CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
      CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
      CREATE TABLE target (sid INTEGER NOT NULL);
      INSERT INTO target VALUES (3);
      INSERT INTO student VALUES
        (1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
        (4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
      INSERT INTO course VALUES
        ('CS201', 'Databases', 'CSE', 4), ('CS202', 'Operating Systems', 'CSE', 4),
        ('CS301', 'Compilers', 'CSE', 4), ('MA101', 'Discrete Mathematics', 'MATH', 3),
        ('EC210', 'Signals and Systems', 'ECE', 3), ('HS101', 'Technical Writing', 'HSS', 2);
      INSERT INTO enrolled VALUES
        (1, 'CS201', 'A'), (1, 'CS202', 'B'), (1, 'MA101', 'A'), (2, 'EC210', 'A'),
        (2, 'MA101', 'B'), (3, 'CS201', 'B'), (3, 'MA101', 'A'), (4, 'MA101', 'C'),
        (5, 'CS201', 'A'), (5, 'CS202', 'A'), (5, 'MA101', 'B'), (5, 'HS101', 'A');
    expected:
      columns: [name]
      rows:
        - [Asha]
        - [Esha]
  - name: "a student with no courses: every other student qualifies"
    setup: |
      CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
      CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
      CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
      CREATE TABLE target (sid INTEGER NOT NULL);
      INSERT INTO target VALUES (6);
      INSERT INTO student VALUES
        (1, 'Asha', 'CSE'), (2, 'Bilal', 'ECE'), (3, 'Chitra', 'CSE'),
        (4, 'Dev', 'ME'), (5, 'Esha', 'CSE'), (6, 'Farhan', 'ECE');
      INSERT INTO course VALUES
        ('CS201', 'Databases', 'CSE', 4), ('CS202', 'Operating Systems', 'CSE', 4),
        ('CS301', 'Compilers', 'CSE', 4), ('MA101', 'Discrete Mathematics', 'MATH', 3),
        ('EC210', 'Signals and Systems', 'ECE', 3), ('HS101', 'Technical Writing', 'HSS', 2);
      INSERT INTO enrolled VALUES
        (1, 'CS201', 'A'), (1, 'CS202', 'B'), (1, 'MA101', 'A'), (2, 'EC210', 'A'),
        (2, 'MA101', 'B'), (3, 'CS201', 'B'), (3, 'MA101', 'A'), (4, 'MA101', 'C'),
        (5, 'CS201', 'A'), (5, 'CS202', 'A'), (5, 'MA101', 'B'), (5, 'HS101', 'A');
    expected:
      columns: [name]
      rows:
        - [Asha]
        - [Bilal]
        - [Chitra]
        - [Dev]
        - [Esha]
  - name: other data, where one student took a superset and one a different set
    setup: |
      CREATE TABLE student (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, branch TEXT NOT NULL);
      CREATE TABLE course (cid TEXT PRIMARY KEY, title TEXT NOT NULL, dept TEXT NOT NULL, credits INTEGER NOT NULL);
      CREATE TABLE enrolled (sid INTEGER NOT NULL, cid TEXT NOT NULL, grade TEXT, PRIMARY KEY (sid, cid));
      CREATE TABLE target (sid INTEGER NOT NULL);
      INSERT INTO target VALUES (11);
      INSERT INTO student VALUES (10, 'Ravi', 'ECE'), (11, 'Meena', 'CSE'), (12, 'Kiran', 'ME'), (13, 'Lata', 'ME');
      INSERT INTO course VALUES
        ('CS201', 'Databases', 'CSE', 4), ('CS250', 'Computer Networks', 'CSE', 4),
        ('ME110', 'Mechanics', 'ME', 3), ('HS102', 'Ethics', 'HSS', 2);
      INSERT INTO enrolled VALUES
        (10, 'CS250', 'B'), (11, 'CS201', 'A'), (11, 'CS250', 'A'),
        (12, 'CS201', 'B'), (12, 'CS250', 'C'), (12, 'ME110', 'A');
    expected:
      columns: [name]
      rows:
        - [Kiran]

Check yourself

Interview questions

What does R ÷ S return when S is empty? It returns π A (R), every value of A that appears in R. A value qualifies when it is paired in R with every tuple of S, and with no tuple in S that condition holds for every value, so nothing is removed. Two consequences follow: values of A that do not appear in R are still not returned, and an SQL version that counts the divisor’s rows returns nothing at all, so it does not agree with division in this case.

Key takeaways

• R(A, B) ÷ S(B) returns the values of A that R pairs with every tuple of S; it answers “every”, “all” and “each” questions.
• R ÷ S = π A (R) − π A ((π A (R) × S) − R): the candidates, minus those that miss at least one pair.
• With an empty divisor, division returns π A (R); a double NOT EXISTS agrees with “every”, while the counting form returns nothing.
• Extended algebra adds γ (grouping and aggregation), generalised projection, δ, τ and outer joins; count over no rows is 0, but sum is NULL.
• SQL works with bags: a tuple appears m + n times in UNION ALL, min(m, n) times in INTERSECT ALL and max(m − n, 0) times in EXCEPT ALL, and R ⊎ R ≠ R.
• Relational algebra cannot compute a transitive closure; recursive SQL queries can.