Skip to content

Relations as linear maps#

A sum or an at through a table that maps coordinates (a relation) is the product of a matrix and a vector. The relations page describes the same sum in database words, "joined on" and "grouped by". The matrix form is the sum in the form a paper uses.

Every formula below is over this spec:

dimensions:
  snapshot: { dtype: int }
  generator: { dtype: str }
  zone: { dtype: str }
relations:
  gen_zone: { key: [generator, snapshot], values: zone, missing: absent }
parameters:
  zone_cap: { dims: [snapshot, zone] }
variables:
  p: { dims: [snapshot, generator] }
constraints:
  zonal:
    dims: [snapshot, zone]
    expression: sum(p, over=generator, by=gen_zone[zone]) <= zone_cap
  looked_up:
    dims: [snapshot, generator]
    where: gen_zone
    expression: p <= at(zone_cap, by=gen_zone[zone])
objective:
  sense: minimize
  expression: sum(p)

zonal contains a sum of p through gen_zone, and looked_up a lookup of zone_cap through gen_zone. The spec loads.

The indicator of a relation#

A relation with columns over the dimensions \(D_1, \dots, D_n\) is a set of rows, so it is a subset \(R \subseteq D_1 \times \dots \times D_n\). Its indicator \(\mathbf{1}_R\) is \(1\) at a row of the table and \(0\) everywhere else. key: declares that the set has one row per combination of key labels (a key tuple). So a relation with key: K and values: V is the set of pairs \((k, f(k))\) of a function \(f: K \to V\) (its graph), and

\[ \mathbf{1}_R(k, v) = [\, f(k) = v \,]. \]

The bracket is \(1\) where \(f(k) = v\) and \(0\) elsewhere.

By default the function has a value at every key tuple (it is total). With data attached, the tool that builds the model (an engine) checks for one row per key tuple. The engine refuses a key tuple with no row. Under missing: absent, the function has no value at a key tuple with no row (it is partial). With \(\mathcal{G}\), \(\mathcal{T}\) and \(\mathcal{Z}\) the sets of generators, snapshots and zones, gen_zone in the spec above is the graph of a partial \(f: \mathcal{G} \times \mathcal{T} \to \mathcal{Z}\).

A relation with no values: (a bare relation) is a subset with no function behind it. So one generator may sit in several rows, each with its own zone. By default a bare relation also lists every key tuple, so one that does not must declare missing: absent.

Every column of a bare relation is in its key, so the relation has no value column for at to read. At load, mathspec refuses at through a bare relation.

A join and group-by as a contraction#

sum(p, over=generator, by=gen_zone[zone]) multiplies the indicator of gen_zone by p, and sums over the one index that they share and that the call lists in over=:

\[ y_{t,z} = \sum_{g} \mathbf{1}_R(g, t, z) \cdot p_{g,t} = \sum_{g \,:\, f(g,\,t) = z} p_{g,t} \]
A sum through a relation is a join, then a group-by with a sum The variable p has a row at each generator, gas and wind, and each snapshot, 0 and 1. The relation gen_zone, keyed by generator and snapshot, puts gas in zone north at snapshot 0 and in zone south at snapshot 1, and wind in zone north at both snapshots. The join pairs each row of p with the row of gen_zone that has the same generator and snapshot, and each pair takes the zone of that row. The group-by adds the pairs that have the same snapshot and zone. The result y has three rows: at snapshot 0 and zone north, p of gas and 0 plus p of wind and 0. At snapshot 1 and zone north, p of wind and 1. At snapshot 1 and zone south, p of gas and 1. relations: gen_zone: { key: [generator, snapshot], values: zone, missing: absent } variables: p: { dims: [snapshot, generator] } sum(p, over=generator, by=gen_zone[zone]) p a variable gen_zone a relation the join one pair per matching row the result an expression generator snapshot gas0 gas1 wind0 wind1 generator snapshot zone gas0north gas1south wind0north wind1north generator snapshot zone term gas0northp[gas,0] gas1southp[gas,1] wind0northp[wind,0] wind1northp[wind,1] snapshot zone value 0northp[gas,0] + p[wind,0] 1northp[wind,1] 1southp[gas,1] join on generator and snapshot sum by snapshot, zone: adds the pairs that agree on both pairs in zone north pairs in zone south

With the data in the figure, the join pairs each row of p with the row of gen_zone that has the same generator and snapshot. The group-by adds the two pairs in zone north at snapshot 0, so the result y has three rows.

The typesetter prints the right-hand form. The left-hand form is a sum over an index that two factors share (a tensor contraction). The relations page describes each column of the relation by two properties. Each pair of properties is a position that an index can take in the formula:

On the relations page In the formula
joined on, the column in over= \(g\) is on both factors and summed. It is not in the result.
grouped by, the column in by= \(z\) is on the indicator alone and not summed. It is in the result.
joined on and grouped by, a key column the call does not name \(t\) is on both factors and not summed. It is in the result.
neither, a value column the call does not name The column is not in the formula, and the sum does not use it.

The result has the free indices, which are the indices that are not summed. They are the indices of the operand and of the indicator together, less the summed one.

mathspec refuses a sum at load when the sum breaks one of two conditions, and the formula needs each of them:

  • The operand has every column joined on, including each key column that the call does not name. Without snapshot, \(t\) would sit on the indicator alone, which is the grouped position, and a sum lists the columns it groups by in by=.
  • The operand has no column grouped by. Otherwise \(z\) would sit on both factors and not be summed. Then the product would match the two occurrences of \(z\), and the result would gain no extra index (an axis) for \(z\). You write that match outside the operator, as in zone_cap * sum(p, over=generator, by=gen_zone[zone]).

At each \(t\), the matrix \(M_t[z, g] = \mathbf{1}_R(g, t, z)\) has one row per zone and one column per generator, with entries of zero and one, and \(y_t = M_t\, p_t\). Over all snapshots, the key column that the call does not name makes the matrix zero outside one block per snapshot (block-diagonal). A relation keyed by one column has one block.

A lookup through a relation#

at(zone_cap, by=gen_zone[zone]) joins the same table, and sums over the other index:

\[ w_{g,t} = \sum_{z} \mathbf{1}_R(g, t, z) \cdot \mathrm{zone\_cap}_{t,z} = \mathrm{zone\_cap}_{t,\, f(g,\,t)} \]
A lookup through a relation is a join with one row per key The parameter zone_cap has a value at each snapshot, 0 and 1, and each zone, north and south: 5 and 2 at snapshot 0, 6 and 3 at snapshot 1. The relation gen_zone, keyed by generator and snapshot, puts wind in zone north at both snapshots, and gas in zone north at snapshot 0 and in zone south at snapshot 1. The lookup joins each row of gen_zone with the row of zone_cap that has the same snapshot and zone. The result has one row per row of gen_zone: at snapshot 0, wind and gas both take 5, the value at north. At snapshot 1, wind takes 6, the value at north, and gas takes 3, the value at south. No row of the result takes the value 2 at snapshot 0 and zone south. relations: gen_zone: { key: [generator, snapshot], values: zone, missing: absent } parameters: zone_cap: { dims: [snapshot, zone] } at(zone_cap, by=gen_zone[zone]) zone_cap a parameter gen_zone a relation the result an expression snapshot zone value 0north5 0south2 1north6 1south3 generator snapshot zone wind0north gas0north wind1north gas1south snapshot generator zone value 0windnorth5 0gasnorth5 1windnorth6 1gassouth3 join on snapshot and zone one row per row of gen_zone

With the data in the figure, each row of gen_zone takes the value of zone_cap at its snapshot and zone. So at snapshot 0, wind and gas both take the value at north, and no row takes the value at south.

The indicator and the contraction are the same as for the sum, so the same free-index rule sets the dimensions of the result. As a matrix, at is \(M_t^{\mathsf{T}}\). The key tuples where \(f\) has a value are its domain. Because \(R\) is the graph of \(f\), the sum over \(z\) has exactly one term at each key tuple in the domain. It has no term elsewhere. So the contraction is the composition \(\mathrm{zone\_cap} \circ f\), which is a pullback: the value of zone_cap at \(f(g, t)\).

That one term is the difference between at and sum, and mathspec decides the difference at load from the key alone. Where the columns a call groups by include the whole key, every group is one row. An at is evaluated at the whole key, so each of its groups is always one row. A sum with one row per group adds up nothing, so mathspec refuses it, and the message suggests at.

The two maps are adjoint. The sum of elementwise products (the inner product) does not change when the matrix moves to the other side, flipped over its diagonal (its transpose). With \(x\) over generators and \(v\) over zones at one snapshot \(t\),

\[ \langle M_t x, v \rangle = \sum_{z} v_z \sum_{g} \mathbf{1}_R(g, t, z)\, x_g = \sum_{g} x_g \sum_{z} \mathbf{1}_R(g, t, z)\, v_z = \langle x, M_t^{\mathsf{T}} v \rangle. \]

Both maps contract the same indicator. So the compiled spec (the program) has at as a Join node, and sum(by=) as the same Join under a Sum.

Why the language has no join operator#

Two operators, sum(by=) and at(by=), are better here than a join and a sum. A separate join operator would return the product before the sum, with an axis for the column grouped by, \(z\). sum(by=) and at(by=) already add that axis and remove it in one call, so a join would add nothing that a file cannot state. mathspec refuses join as an unknown operator, and the message lists the operators that exist.

How an engine evaluates the product#

The file states the formula, and an engine decides how to evaluate it. A table lists the support of \(\mathbf{1}_R\), which is the set of rows where \(\mathbf{1}_R\) is \(1\). An engine can multiply a matrix stored that way by a vector in two steps:

  1. The engine pairs each row of the table with each row of the operand that agrees on every shared index, here \(g\) and \(t\). That is a join on the columns joined on that matches equal values (an inner equi-join). Each pair is one nonzero product \(1 \cdot p_{g,t}\), and it takes the label of the column grouped by, \(z\).
  2. The engine adds the pairs that agree on the free indices, here \((t, z)\). That is a sum grouped by the dimensions of the result.

For at, an engine runs step 1 only, because with one row per group no two pairs have the same coordinate. Where several \((g, t)\) share one \(z\), the engine gets several rows for that \(z\). Those rows are a column of \(M_t^{\mathsf{T}}\) with several ones.

So the database steps and the matrix product are one computation. The join step has only the entries where \(\mathbf{1}_R\) is \(1\), and the group-by is the \(\sum\).

Empty groups and missing values#

At two kinds of position the matrix product has no term.

  • An empty group is an empty sum. With data attached, a zone that no generator maps to at \(t\) has \(y_{t,z} = 0\), and the row is \(0 \le \mathrm{zone\_cap}_{t,z}\). The row has no variable. It exists once the data is attached. At load, mathspec refuses only a constraint whose expression has no variable, and the expression of zonal has p.
  • Outside the domain of \(f\) there is no value. \(\mathrm{zone\_cap} \circ f\) is undefined where \(f\) is undefined, so at has no row there (it is absent), and absence spreads to the row. Under the default, no key tuple is outside the domain. With where: gen_zone, looked_up declares the domain of \(f\) in the spec, so a reader sees which rows exist without opening the data.
An empty group is a row with no variable, and a key tuple outside the domain has no row The relation gen_zone, keyed by generator and snapshot with missing: absent, puts wind in zone north at snapshots 0 and 1, and gas in zone north at snapshot 0. It has no row for gas at snapshot 1, so f has no value there. The constraint zonal sums p by zone and has one row per snapshot and zone. At snapshot 0, north is p of wind plus p of gas, at most 5. At snapshot 1, north is p of wind, at most 6. South has no generator at either snapshot, so its rows are 0 at most 2 and 0 at most 3: empty groups with no variable. The lookup at of zone_cap by gen_zone has one row per row of gen_zone: wind at 0 takes 5, gas at 0 takes 5, wind at 1 takes 6. It has no row for gas at snapshot 1, where at is absent. relations: gen_zone: { key: [generator, snapshot], values: zone, missing: absent } sum(p, over=generator, by=gen_zone[zone]) <= zone_cap at(zone_cap, by=gen_zone[zone]) gen_zone a relation zonal a constraint at(zone_cap, by=gen_zone[zone]) an expression generator snapshot zone wind0north gas0north wind1north snapshot zone row 0northp[wind] + p[gas] ≤ 5 0south0 ≤ 2 1northp[wind] ≤ 6 1south0 ≤ 3 snapshot generator value 0wind5 0gas5 1wind6 empty group: no variable empty group: no variable no row for gas at 1: f has no value no row for gas at 1: at is absent sum by= groups at by= looks up data the file is given a constraint or an expression absent: no row

With the data in the figure, no generator maps to south, so both rows of zonal at south are empty groups with no variable. gen_zone has no row for gas at snapshot 1, so the lookup has no row there either.

Partitions and tests#

The other two uses of a relation, a partition and a test, are not matrix products. An operator with within=, such as shift, works separately on each set of members that \(f\) sends to one value (a fibre). The dimensions of the result do not change. With season_of: { key: snapshot, values: season }, shift(soc, along=snapshot, offset=1, edge='wrap', within=season_of[season]) steps back within each season:

A partition by season_of: shift wraps inside each season The variable soc has four rows, snapshots 1 to 4. The relation season_of puts snapshots 1 and 2 in winter and snapshots 3 and 4 in summer. shift of soc along snapshot, offset 1, edge wrap, within season_of season, has one row per snapshot. Snapshot 2 reads soc at 1 and snapshot 4 reads soc at 3. Snapshot 1, the first of winter, wraps to soc at 2, the last of winter, and snapshot 3, the first of summer, wraps to soc at 4. season_of: { key: snapshot, values: season } shift(soc, along=snapshot, offset=1, edge='wrap', within=season_of[season]) soc a variable snapshot 1 2 3 4 season_of a relation snapshot season 1 winter 2 winter 3 summer 4 summer the result an expression snapshot value 1 soc[2] 2 soc[1] 3 soc[4] 4 soc[3] one back group by season 1 and 3 wrap inside their season the group of season winter the group of season summer

Each season is one fibre of season_of, so no value crosses from winter to summer.

A test is the indicator itself. In a where, the name of a relation is \(\mathbf{1}_R\) at the coordinate of the entry.

You can now judge the dimensions of a sum or an at through a relation, and why the language has no join operator.

See also