Math · Note 4
Nested sums, and the loop they describe
Two sigmas side by side are two nested loops. Covers reading them outside-in, when the two can be separated, and the form that actually appears in data work — where the inner set depends on the outer element.
Two sigmas side by side mean: do the inner one completely, for each value of the outer one, and add up the results.
The inner sum is . That happens for and again for . So the whole thing is .
Work it out the long way once, and then never again:
Read outside in; evaluate inside out. The rightmost sigma is the innermost loop. If you write nested loops, the correspondence is exact — the outer sigma is the outer `for`, the inner sigma is the inner `for`, and the body is the line that adds to the accumulator. That is all a double sum is. Two loops and a running total.
When the two can be separated
If the body splits into a part that only mentions and a part that only mentions , the sums separate:
This only works when the inner bounds do not depend on the outer index. In database work they usually do depend on it, so you usually cannot. Recognizing which case you are in is worth a lot of arithmetic.
The form that actually appears
Here is the step that makes this useful, and it is the thing most people are reaching for when they try to write a formula for something like revenue per customer.
In the examples above the inner bounds were fixed. In real data the inner set depends on the outer element:
The inner sum runs over — the lines of this order — and is whatever the outer sum is currently on. That is a nested loop where the inner collection is fetched from the outer item: for each order of this customer, for each line of that order, add quantity times price.
Evaluate , which is Ada. . Order 10 has two lines, . Order 11 has one line, . So .
Now evaluate , which is Cy. , so the outer sum has no terms and . Not null, not an error. Zero. A formula written this way handles the customer with no orders correctly and for free, which is more than can be said for the average join.
Why is a function
takes a customer id and returns a number: . The sums are how it is computed; the function is what it is.
When you see something of the shape , that is someone defining a function whose value happens to be a total. There is nothing more to it than that, and the definition is doing exactly the job a function signature does in code.
Exercises
Compute .
Answer
.
Compute .
Answer
gives ; gives . Total .
Compute .
Answer
The body ignores , so the inner sum is added three times, or . Then .
Compute .
Answer
, which has one line, . So .
Compute . What should it equal, and does it?
Answer
, which is the total over Line from note three. It does. Checking a formula two ways like this is the cheapest bug-finding there is.
Write a formula for , the number of lines across all of customer 's orders, and compute .
Answer
, or equally . .
Write a formula for the total revenue of all customers in a given city .
Answer
. For Leeds that is ; for Hull, .
Questions
How do you read two summation signs in a row?
Outside in. The leftmost sigma is the outer loop and the rightmost is the inner one. For each value of the outer index, the inner sum is evaluated completely, and those results are added together.
When can a double sum be split into two sums?
Only when the body factors into a part depending on one index and a part depending on the other, and the inner bounds do not depend on the outer index. In database work the inner set usually does depend on it, so the split is usually unavailable.
What does a nested sum over related sets compute?
It walks a one-to-many relationship. The outer sum ranges over parent rows and the inner over the children of whichever parent it is currently on, which is exactly the loop you would write by hand to total a customer's order lines.