Relational algebra treats set difference as a primitive operator but intersection as a derived one. Show how intersection can be expressed using only union and difference, and explain why having a minimal set of primitive operators matters.

## The derivation Start with the definitions over union-compatible relations R and S: - `R − S = { t | t ∈ R and t ∉ S }` - `R ∩ S = { t | t ∈ R and t ∈ S }` Now evaluate `R − (R − S)` on an arbitrary tuple `t ∈ R`: - If `t ∈ S`, then `t ∉ (R − S)`, so t survives the outer difference. It is kept. - If `t ∉ S`, then `t ∈ (R − S)`, so the outer difference removes it. It is dropped. Kept exactly when `t ∈ R` and `t ∈ S` — which is the definition of intersection. And any tuple not in R cannot appear, since the outer expression starts from R. Hence `R ∩ S = R − (R − S)`. A useful sanity check: this is the set-theory analogue of the identity `A ∩ B = A \ (A \ B)`, which is easy to see on a two-circle diagram — remove from the left circle everything that is *only* in the left circle, and the overlap is what remains. There is also a De Morgan-flavoured route in models with a complement, but relations have no universal relation to complement against, so the double-difference form is the standard derivation. ## The minimal basis Codd's classical primitive set is six operators: 1. **Selection σ** — filter tuples by a predicate. 2. **Projection π** — restrict to a subset of attributes. 3. **Union ∪** — combine union-compatible relations. 4. **Set difference −** — subtract union-compatible relations. 5. **Cartesian product ×** — pair every tuple with every tuple. 6. **Rename ρ** — change attribute names, which is what makes self-products and name mismatches workable. Everything else is sugar: - `R ∩ S = R − (R − S)` - `R ⋈_θ S = σ_θ(R × S)` — theta join. - Natural join = product, then selection equating the shared attributes, then projection removing the duplicated copies. - Division is expressible with product, difference and projection. ## Why anyone cares about minimality **Proof economy.** If you want to prove something about the algebra — that every expression is monotone except those using difference, that evaluation always terminates, that a rewrite preserves semantics — you prove it once per primitive and get the derived operators free by substitution. Six cases instead of a dozen. **A definition of expressive power.** "Relational completeness" is the standard for query languages: a language is relationally complete if it can express every query expressible in the primitive algebra. Relational calculus (tuple and domain) was proved equivalent in power to the algebra, and that equivalence is what justifies declarative SQL — you say *what* you want, and the system is free to pick any algebraic expression that computes it, because it can always find one. **Knowing the boundary.** The minimal basis also makes the algebra's *limits* visible. Plain relational algebra cannot express transitive closure — "all parts reachable through a bill-of-materials" — because no finite composition of the six primitives does unbounded iteration. That is precisely why SQL had to add recursive queries as a language extension rather than a rewriting. **Monotonicity.** Five of the six primitives are monotone: adding tuples to an input can only add tuples to the output. Difference is the exception — adding a tuple to S can *remove* a tuple from `R − S`. That single fact explains why difference (and its derived users like intersection and antijoin) behaves differently in incremental view maintenance, streaming, and distributed evaluation: monotone operators can be computed incrementally and out of order, non-monotone ones need to know that their negative input is complete. ## Back to SQL SQL exposes `UNION`, `INTERSECT` and `EXCEPT` directly even though `INTERSECT` is redundant in theory. Two good reasons: readability — `A INTERSECT B` states intent far better than a nested double difference — and optimization — an engine can implement intersection as a single hash or merge pass over both inputs, whereas the naive double-difference form would scan and materialise twice. Expressive power and execution efficiency are different questions, and the algebra's minimality speaks only to the first. Also note the associativity and commutativity that follow directly from set theory: union and intersection are both commutative and associative; **difference is neither** (`R − S ≠ S − R`, and `(R − S) − T ≠ R − (S − T)` in general). That asymmetry is the thing candidates most often get wrong when they reason about these operators as if they were all interchangeable.