Covers two more core operators, restriction and lifting, and shows how combining them naturally produces the join operation familiar to SQL users.
Intro | Lesson 2 | Lesson 3 | Lesson 4 | Lesson 5 | Lesson 7 | Lesson 8
Transcript
Slide 1: Welcome to Lesson 6. Last time we handled the operations you already half-knew: transpose, composition, and the set operations. Today we add the few the algebra introduces of its own, and with them we’ll do something that may surprise you: rebuild the SQL join from scratch, exactly, with no hand-waving. There are really just two new ideas. The first is restriction, a precise way to keep only the data that matches a condition. The second is lifting, a way to carry any operation up a level of the tower. Put them together and the famous, fearsome join simply falls out.
Slide 2: Here’s the plan in one sentence. With restriction we can pick out exactly the rows we want, that’s the WHERE clause. With lifting we can take any operation defined on relations and apply it across a whole clan of them. And once we have both, the join, that operation SQL treats as a black box, turns out to be nothing more than restriction and composition, lifted and combined. Everything you do in SQL can be re-expressed in the algebra, precisely, and often more clearly. Let’s take the two new ideas one at a time.
Slide 3: The first new operator is restriction, and it comes in two mirror forms. Superstriction, written with a triangle pointing right, keeps a relation only if it contains what you’re looking for, and discards it otherwise. Substriction is its mirror. That sounds abstract, but you already use it constantly: it is exactly what the WHERE clause does, keep the rows that match, drop the rest, now made mathematically exact. And when we lift it to a whole clan, cross-superstriction runs that same filter across every relation, every row, in the table. Filtering, precisely defined.
Slide 4: Let me show you how neatly the SQL you know lines up with the algebra. SELECT, choosing which columns you want, is composition, following each row into just the columns you name. WHERE, filtering the rows, is superstriction. And JOIN is the natural join, which we’re about to build. The point is not that the algebra replaces SQL with something alien. It’s that SQL, for all its quirks, was always doing algebra underneath, without the clean foundation. The algebra simply gives the same operations an honest mathematical form.
Slide 5: Now the second idea: lifting. It’s the simplest thing in the whole algebra. Take any operation you have on relations and apply it to every pair of relations, one from each clan, collecting the results. That’s a cross-operator, and we mark it by drawing a broken circle around the familiar symbol. Cross-union, cross-intersection, cross-difference, cross-composition, cross-restriction, they’re not new operations to memorise, just old ones carried up a level. And here’s the reward on the sixth card: the natural join. It is not a primitive at all. It is restriction and composition, lifted and combined. The black box, opened.
Slide 6: Step back and see the shape of it. Every operator in the algebra either lives at the foot of the tower or is a lifted version of one that does. That’s why twenty-three operators is far less daunting than it sounds: most are the same few verbs, carried upward. Lifting is the engine of the whole system. It’s what lets one small set of ideas cover tables, documents, graphs and databases without ever growing a special case. Learn a verb once at the bottom; lifting delivers it, faithfully, everywhere above.
Slide 7: So, to carry forward. Restriction, superstriction and substriction, is the WHERE clause made exact: keep what matches. Lifting turns any relation-level verb into a clan-level one by applying it to every pair, and we mark it with a broken circle. And the join, that intimidating cornerstone of SQL, is simply restriction and composition, lifted and combined, no magic required. With that, you’ve met the whole family of operations.
Slide 8: That’s the algebra’s own operators, and the join laid bare. Thank you for your time; in Lesson 7 we have a little more to say about the strictions.