Math · Note 5
Products, quantifiers, grouping and joins
Pi is sigma with multiplication and identical grammar. For-all and there-exists are how keys and referential integrity get written. Grouping is a partition, and a join is a subset of a product — which is the whole mechanism in one line.
is a capital pi, and it is sigma with multiplication instead of addition. Identical grammar — same four parts, same set form, same conditions.
One thing to learn, and it is the counterpart of the empty sum:
The empty product is 1, not 0. The identity for addition is 0 — adding nothing changes nothing — and the identity for multiplication is 1. If the empty product were 0 it would poison every product it appeared in.
Where pi turns up in data work: counting combinations, where a form with fields and options in field has possible submissions, which is the rule generalized; and independent probabilities, where the chance that independent things all happen is . You will meet sigma a hundred times for every pi.
For all, and there exists
Two marks, and they are how constraints get written. is said for all x in S and means every element. is said there exists an x in S and means at least one.
A primary key on Customer says no two distinct rows share a `cust_id`:
The is implies — if the left is true, the right must be. A foreign key on Order says every order points at a customer that exists:
That is referential integrity, stated in one line.
The two are related: not all of them are X is the same as at least one of them is not X. Worth knowing, because a constraint is usually easiest to check by hunting for a single counterexample rather than by verifying every row.
Grouping
A partition cuts a set into non-overlapping pieces that together use up everything. `GROUP BY city` partitions Customer into the Leeds block and the Hull block:
The set of keys is the set of values actually present:
Note that form — set-builder with an expression on the left of the colon instead of a variable. Say it: the set of city-of-c, for c in Customer. It means apply the function to every element and collect the results, and because it is a set, duplicates collapse. So this is `SELECT DISTINCT city`.
A group-by query is then: for each key, an aggregate over its block.
The , said maps to, is how you write a function without naming it. Leeds maps to , Hull maps to .
Joins
A join is a subset of a product — take all possible pairs, keep the ones that match:
The is the join symbol — it is a bowtie. But you do not need it; the set-builder on the right is the definition, and it is clearer.
Here it gives three pairs. Cy appears in no pair, which is precisely why an inner join loses him, and why a nested sum giving is the better behavior.
Note the shape: has elements and the condition keeps 3. That is the whole mechanism, and it is why a missing join condition returns the product.
Exercises
Compute and .
Answer
, and . A constant body multiplied times is that constant to the power .
A checkout form has a country field with 50 options, a plan field with 3, and a yes/no box. Write the count with pi and evaluate it.
Answer
with , which is .
Say out loud. Is it true of the running example?
Answer
"For all lines l in Line, the quantity of l is greater than zero." True — the quantities are 1, 2 and 3.
Write "every customer has placed at least one order". Is it true here?
Answer
. **False** — Cy is the counterexample, which is what makes him useful.
Express "no line has a quantity of zero" twice — once with for-all, once with there-does-not-exist.
Answer
, and . Same claim.
Write , the set of distinct SKUs in Line, and give its size.
Answer
, which has size — A, B and C. A appears on two lines and is counted once, because this is a set.
Write the function "number of customers per city" and evaluate it for both cities.
Answer
, or equivalently . Leeds maps to , Hull to .
Write the join of Line and Order on order_id. How many pairs does it contain, and how many would it contain with no condition?
Answer
. Four pairs with the condition, since every line matches exactly one order; twelve without it.
Questions
Why is the empty product 1 and the empty sum 0?
Because each is the identity for its operation: adding zero changes nothing and multiplying by one changes nothing. Defining them this way keeps formulas correct when a set turns out to be empty, instead of making the empty case a special case.
How do you write a primary key constraint mathematically?
As a for-all statement: for any two rows of the table, if their key values are equal then they are the same row. A foreign key is a for-all combined with a there-exists, saying every row in one table has a matching row in another.
What is a join in set terms?
A subset of the Cartesian product of two tables, keeping only the pairs whose join condition holds. This is why a join with no condition returns every possible pairing, and why the result of an inner join drops rows that match nothing.