Relational division is not a primitive operator. Show how it is derived from projection, Cartesian product and set difference, and explain why the derivation is naturally read as 'build the counterexamples and subtract them'.

## The setup Let the dividend be `A` with attributes `(X, Y)` and the divisor `B` with attributes `(Y)`. The goal is `A DIVIDE B`, the set of `X` values that are paired in `A` with **every** `Y` value in `B`. ## The derivation, step by step ``` 1. candidates = pi X (A) -- every x that appears at all 2. all_pairs = candidates x B -- every (x, y) the query demands 3. missing = all_pairs - A -- demanded pairs that do not exist 4. bad = pi X (missing) -- candidates with at least one missing y 5. result = candidates - bad -- candidates with none missing ``` Work it on the enrolment example. `A = Enrolled(student, course)` with `(ann, db), (ann, os), (ann, ml), (bob, db)`; `B = Required(course)` with `(db), (os)`. - `candidates = {ann, bob}` - `all_pairs = {(ann, db), (ann, os), (bob, db), (bob, os)}` - `missing = all_pairs - A = {(bob, os)}` — note `(ann, ml)` never enters, because `all_pairs` only contains required courses - `bad = {bob}` - `result = {ann}` That is the correct answer, and the trace shows why extras such as `ann`'s `ml` course are irrelevant: they never appear in `all_pairs`, so they can never create a missing pair. ## Why 'build the counterexamples and subtract them' The logical statement being computed is universal: ``` for every y in B: (x, y) in A ``` Standard quantifier duality rewrites this as ``` not ( exists y in B: (x, y) not in A ) ``` Every line of the derivation matches a piece of that formula. `candidates x B` enumerates the `y in B` for each `x` — the existential's search space. `- A` is the inner negation `(x, y) not in A`. The projection is the existential quantifier: an `x` appears in `bad` if there is *at least one* witness. The final subtraction is the outer negation. This is why the fastest practical implementation of a division-shaped query is a doubly nested negated existential rather than the literal algebraic recipe: the algebra materialises the entire candidate-by-divisor product, while a nested-negation evaluation can abandon a candidate at its first missing value. ## Why difference must appear This is the part that separates a memorised recipe from understanding. Selection, projection, Cartesian product, join and union are all **monotone**: adding tuples to any input can only add tuples to the output, never remove any. Division is *not* monotone in its divisor — take the example above, add `(ml)` to `Required`, and `ann` disappears from the result. A non-monotone function cannot be built from monotone building blocks, so any correct derivation of division must use set difference (or some other negation) at least once. The proof is short and it is a good thing to be able to give on demand. The same argument explains a family of related facts: universal quantification, "not exists", anti-join and set difference are all faces of the same non-monotone capability, and a query language without any of them cannot express "for all". ## The candidate set is a real choice Step 1 uses `pi X (A)` as the candidate set, which means a student who appears nowhere in `Enrolled` cannot be in the result. That is usually right when the dividend is the only source of candidates. But if you have a separate `Students` relation and the requirement set is empty, the two formulations diverge: dividing yields only the students who appear in `Enrolled`, whereas a natural-language reading of "students who satisfy all zero requirements" would include everyone. Whenever candidates exist independently of the dividend, take the candidate set from the candidate relation and use `Students x B - A` in step 3. Interviewers who know the operator well often probe exactly this. ## Cost profile of the three standard implementations 1. **The algebraic derivation.** Materialises `|candidates| x |B|` pairs. Simple to reason about, worst asymptotics, and it is the one to avoid at scale. 2. **Nested negated existential.** Evaluates per candidate and stops at the first missing value; with an index on `(x, y)` this is usually the winner and it degrades gracefully. 3. **Count comparison.** Restrict the dividend to pairs whose `y` is in `B`, count distinct `y` per `x`, keep those whose count equals `|B|`. Reads well and vectorises nicely, but it always processes the full restricted dividend, and it is only correct with the restriction and the distinctness — a duplicated `(x, y)` pair or an unrestricted count silently over-counts and admits candidates that should fail. All three compute the same relation. Which one an engine picks depends on selectivity, indexing and whether the divisor is small and known in advance. ## Interview framing Write the five lines, trace one small example, then state the two insights: the derivation is quantifier duality made concrete, and difference is provably required because division is non-monotone in the divisor. Finish with the observation that the algebraic form is the slowest of the three real implementations.