The final lesson on operations, focusing on superstriction and substriction to round out the complete operator set of the Data Algebra.
Intro | Lesson 2 | Lesson 3 | Lesson 4 | Lesson 5 | Lesson 6 | Lesson 8
Transcript
Slide 1: Welcome to Lesson 7. We have spent two lessons in discussing the algebraic operators. We decided to provide a third, because as they say, three’s the charm. And what could be more charming than a striction.
Slide 2: Our reason for devoting a whole presentation to the strictions is simply that this is the area of data algebra that is new to everyone who encounters it for the first time. The goal, here, is to increase familiarity with these new operators.
Slide 3: Superstriction is the first operator the algebra adds that isn’t inherited from set theory, and it behaves unlike anything in SQL. Written with a right-pointing triangle, it takes two relations and asks a single question: does everything in B also appear in A? If it does, if B is a subset of A, the operator hands back A, whole and unchanged. If it doesn’t, there is no result at all. Look at the three cases. B1 sits entirely inside A1, so the gate opens and we get A1. B2 shares a couplet but brings others A1 hasn’t got, undefined. B3 contains all of A1 and one couplet more, also undefined. That’s why we call these partial operators. Think of superstriction as a gate rather than a filter: it doesn’t trim A down, it either passes A through intact or refuses.
Slide 4: Let’s do this with real data. Here is the Outlaws table from the book, five rows, six columns. The SQL we want to answer selects every outlaw born in New York. And here is the data algebra command that does the same work: C equals Outlaws, cross-superstriction, the clan holding one couplet, New York points to BornIn. Row by row, that comes down to a plain superstriction of each row against that single-couplet relation. So the operator walks the table asking one question of each row: does this row contain it? Robin Hood was born in Locksley, so no, undefined. Billy the Kid, New York, yes, and the operator hands back the entire row, all six couplets, untouched. Al Capone, the same. Loki and Chewbacca fail. Two rows come back whole. That is precisely what a WHERE clause does.
Slide 5: Substriction is superstriction seen in a mirror. The same question, asked in the opposite direction: this time we want A to fit inside B. So A substriction B gives you A when A is a subset of B, and nothing otherwise. In the diagram, A2, kernel, seed, root and germ, sits wholly within B4, which holds those four couplets and one more. The gate opens, and the result is A2, unchanged. B5 fails because it’s smaller than A2, a subset rather than a superset. B6 fails because it swaps in a couplet A2 doesn’t hold. Notice that with both operators the result, when it’s defined at all, is always the left-hand relation, untouched. And that undefined outcome is a genuine nuisance, which is precisely why we lift these two up to clans, where the awkwardness disappears.
Slide 6: Substriction asks the same question from the other side. The command is P substriction R, where R is row two of Outlaws, and lifted to the clan it becomes P cross-substriction Outlaws. Here is R written out as what it really is: a relation of six couplets, Billy the Kid’s row. Now we test small relations against it. Murder points to Crime, five hundred dollars points to Reward: both couplets are in R, so P is a subset of R, and substriction hands P back. Swap in Bounty points to Reward and it fails, because Bounty is Chewbacca’s reward, not Billy’s. New York and On the lam both appear, so that one passes. Billy the Kid with Larceny fails, because Larceny is Robin Hood’s crime. Note the real difference: superstriction returns the row, substriction returns the probe.
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. Next time we climb the final rung of the tower and gather clans themselves. In Lesson 8, the horde.
Slide 8: Hopefully you now have a better knowledge of the strictions. Thank you for your time; in Lesson 8 we will climb to the top of the ladder.