Cross tables

A cross table represents the Cartesian product between two tables. Cross tables are typically intended for situations that involve multiple dimensions (e.g. stores and products, SKUs and days, etc). Source tables can broadcast into the cross table. Cross tables also provide an additional class of vector operations within Envision.

Table of contents

Syntax overview

The keyword cross is used to declare a cross table as illustrated by:

table R = extend.range(2)
table S = extend.range(3)

table RS = cross(R, S)
RS.A = R.N
RS.B = S.N

show table "cross" a1b5 with RS.A, RS.B

In the above script, the two assignments of RS.A and RS.B, respectively originating from R and S work because the table RS has R and S as two upstream tables. The table tile displays the 6=2x3 lines, which result from the Cartesian product between R and S.

The right source table within a cross should be a small table. This constraint ensures that large cross tables can be processed efficiently when performing complex operations, such as the ones allowed by the each keyword.

A cross table has exactly two primary dimensions. Thus, the two source tables must be distinct and have one primary dimension each. The scalar table and cross tables cannot be used as source tables.

Every operation that expects two or more vectors to be in the same table attempts at finding a common table between those vectors. A cross table, once declared, becomes a candidate for being this common table.

For example, a map operation performed between two independent tables operates over the cross table associated to this pair of tables:

table R = extend.range(2)
table S = extend.range(3)

table RS = cross(R, S)
s = sum((1 into R) + (1 into S))

show scalar "sum" with s // 12

In the above script, the sum (1 into R) + (1 into S) is broadcasted in the common table between R and S, that is, the cross table RS. The resulting value, 2 over all the lines of the table RS is finally summed into s, a scalar variable.

The table RS must be declared for the above script to work. Indeed, Envision adopts a defensive design where combining within a single map operation two unrelated tables is illegal - unless the corresponding cross table is explicitly declared. This behavior prevents the accidental, and likely nonsensical, combination of values originating from unrelated tables.

A similar effect is obtained beyond the map operations, for example:

table R = extend.range(2)
table S = extend.range(3)
table RS = cross(R, S)
c = sum(sum(1) by [R.N, S.N]) // RS as common table
show scalar "count" with c // 6

Or alternatively:

table R = extend.range(2)
table S = extend.range(3)
table RS = cross(R, S)
show table "cross" a1b6 with R.N, S.N // RS as common table

A cross table can be aggregated into its source tables:

table R = extend.range(2)
table S = extend.range(3)

table RS = cross(R, S)
RS.A = R.N
RS.B = S.N

R.C = sum(RS.A + RS.B)
S.D = sum(RS.A + RS.B)

show table "R" a1b5 with R.C
show table "S" c1d5 with S.D

In the above script, R.C (resp. S.D) is defined as an aggregation from the table RS to the table R (resp. S).

Advanced remark: Cross tables in Envision can be seen as a stepping stone toward an extensive tensor comprehension. The tensor comprehension paradigm is the descendent of the array programming paradigm.

Roadmap: Cross tables are limited to two source tables, however we plan to lift this limitation in the future.

Transposition

It is not possible to declare two cross tables that have the same dimensions in the same order. However, as the ordering of the source dimensions matters, it is possible to declare two cross tables that have the same source dimensions, but in a distinct order. It is also possible to broadcast a cross table into its transposed counterpart.

Let’s consider a transposed cross table:

table R = extend.range(3)
table S = extend.range(4)

table RS = cross(R, S)
table SR = cross(S, R)

RS.N = (R.N into RS) + S.N
SR.N = (R.N into SR) + S.N

show table "" a1d6 with R.N as "R", S.N as "S", RS.N as "RS", SR.N as "SR"

In the above script, the variable R.N is explicitly broadcast first into the table RS and second into the table SR because there are two candidate common tables between R and S: both RS and SR are eligible. The broadcast indicates to Envision which cross table should be picked.

Indeed, the more direct approach does not compile:

table R = extend.range(3)
table S = extend.range(4)

table RS = cross(R, S)
table SR = cross(S, R)

RS.N = R.N + S.N // WRONG! Ambiguous common table between RS and SR

Simple assignments between a cross table and its transposed cross table are supported. As a result, the previous script can be rewritten as:

table R = extend.range(3)
table S = extend.range(4)

table RS = cross(R, S)
table SR = cross(S, R)

RS.N = (R.N into RS) + S.N
SR.N = RS.N // Transpose!

show table "" a1d6 with R.N as "R", S.N as "S", RS.N as "RS", SR.N as "SR"

The assignment SR.N = RS.N is a transposition of the values held within the table RS into the table SR.

As data accesses are vastly more efficient whenever lookups happen through the left table (more on this in the following), if a series of operations have to be performed through “right” lookups, it’s better to transpose the cross table, and then operate via “left” lookups afterward.

Filtering a cross table

Filtering a cross table is possible, however the filtering process itself removes the ‘cross’ property, as the table does not hold any more a complete Cartesian product of the source tables. Thus, filtering a cross table is performed by explicitly introducing the relevant table:

table R = extend.range(2)
table S = extend.range(3)

table RS = cross(R, S)
RS.N = R.N + S.N

table RSf = where RS.N > 3
RSf.N = RS.N

show table "RSf" a1b4 with R.N, S.N, RSf.N // only 3 lines

In the above script, the table RSf is defined as a filtered version of the cross table RS. This table inherits the primary dimensions of RS but those dimensions as inherited as secondary dimensions. As both R and S can broadcast into RSf, the table RSf is identified as the common table for the table tile.

Filtering a source table

Filtering a source table of a cross table transitively applies a filter on the cross table itself. This filtering pattern is of primary interest because it preserves the ‘cross’ nature of the table:

table R = extend.range(2)
table S = extend.range(3)

table RS = cross(R, S)

where R.N == 1
  RS.A = R.N
  RS.B = S.N
  show table "cross" a1b5 with RS.A, RS.B

In the above script, the source table R is filtered, and as a result, the cross table RS is also filtered. The table tile displays 3 lines instead of the 6 lines that would be expected if the table RS were unfiltered. The table RS is ‘cross’ when declared, and it remains ‘cross’ within the filter.

As filtering according to a source table do preserve the ‘cross’ nature of the cross table, all the operations over the cross table which are allowed outside the where block remain allowed.

It is also possible to define a cross table within a filtered context:

table R = extend.range(2)
table S = extend.range(3)

where R.N == 1
  table RS = cross(R, S)
  RS.A = R.N
  RS.B = S.N
  show table "cross" a1b5 with RS.A, RS.B

When a cross table is defined in a filtered context, then this cross table is bound to this context. For example, in the above example, using the table RS outside, after the end of the where block, would not be allowed.

As a filtered declaration of a cross table is strictly scoped to the filtered block, it is possible to define another identically named table after the end of the where block, as illustrated with:

table R = extend.range(2)
table S = extend.range(3)

where R.N == 1
  table RS = cross(R, S)
  RS.A = R.N
  RS.B = S.N
  show table "cross" a1b5 with RS.A, RS.B

table RS = extend.range(3)
show table "alt" c1d5 with RS.N

However, this behavior is specific to filtering blocks that do impact the cross table. Indeed, if a cross table is declared within a where block that does not impact any of its source tables, then the scope does not apply, and the cross table can be used after the end of the where block:

table R = extend.range(2)
table S = extend.range(3)
table Dummy = extend.range(4)

where Dummy.N == 1
  table RS = cross(R, S)
  RS.A = R.N
  RS.B = S.N

show table "cross" a1b5 with RS.A, RS.B

In the above script, the table RS is declared within a filtered scope, but this table is accessed after the end of the scope (i.e. the end of the where block) because the filter does not touch RS or its source tables.

Transitive broadcasting

Broadcasting into the cross table is possible for any table that can already broadcast into one of the source tables of the broadcast itself. This mechanism is of interest, for example, for situations that involve multiple hierarchical levels. Let’s consider 3 tables S1, S2 and T where T extends S2, as a cross table, and where S2 extends S1. Let’s see how values originating from S1 can be broadcast into T:

table R = extend.range(2)
table S1 = extend.range(3)
table S2 small 100 = extend.range(S1.N)

table RS2= cross(R, S2)
RS2.A = R.N
RS2.B = S1.N into S2

show table "cross" a1b5 with RS2.A, RS2.B

In the above script, the value S1.N is first broadcast into the table S2 via the expression S1.N into S2 and then, the resulting expression is itself broadcast into RS2 via the assignment RS2.B = ...

In order to remove the need for expliciting the intermediate broadcast table, i.e. S2 in the above script, a dimension can be imported into the cross table itself:

table R = extend.range(2)
table S1[s1] = extend.range(3)
table S2 small 100 = extend.range(S1.N)

table RS2 = cross(R, S2)
RS2.s1 = S2.s1 // same as 's1 into S2'
RS2.A = R.N
RS2.B = S1.N

show table "cross" a1b5 with RS2.A, RS2.B

In the above script, once the dimension s1 has been imported in the cross table RS2 via RS2.s1 = s1 into S2, there is no longer any need to specify S2 as the intermediate table. This allows the assignment RS2.B = S1.N, which involves a direct broadcast from S1 to RS2.

Lookups

Lookups offer dictionary-like access to vectors by specifying the key associated with the table’s primary dimension. Both regular tables and cross tables support lookups. The lookup over a cross table specifies two keys to identify the line within the table:

table R[r] = with
  [| as r |]
  [| 1    |]
  [| 2    |]

table S[s] = with
  [| as s |]
  [| 1    |]
  [| 2    |]
  [| 3    |]

table RS = cross(R, S)
RS.N = r + s

n = RS.N[r: 2, s: 3] 

show scalar "n" with n

In the above script, two tables R and S are declared through their respective table comprehensions. Also, r (resp. s) is the primary dimension of the table R (resp. S) and is of type number. A lookup is performed via the expression RS.N[r: 2, s: 3] to extract a single scalar value from the vector RS.N. The r and s prefixes match the names of the source tables’ dimensions R and S of the cross table RS.

The lookup syntax for cross tables is similar to the one used for regular vector lookup. The dimensions are named to lift any ambiguity. While the ordering of the lookup arguments has no impact, It is recommended, for the sake of code clarity, to keep the dimensions in the order of the declaration of the source tables (as done above).

Lookups over vectors are also allowed, as illustrated by:

table R[r] = with
  [| as r |]
  [| 1    |]
  [| 2    |]

table S[s] = with
  [| as s |]
  [| 1    |]
  [| 2    |]
  [| 3    |]

table RS = cross(R, S)
RS.N = r + s

table U = with 
  [| as I, as J |]
  [| 2,    3    |]
  [| 1,    2    |]
  [| 0,    1    |] // no matching counterpart

U.N = RS.N[r: U.I, s: U.J]

show table "U" a1b4 with U.I, U.J, U.N

In the above script, the lookup RS.N[r: U.I, s: U.J] is performed over the table U, and it attempts to extract one value from the vector RS.N for every line of the table U. When there is no matching line to be found within the table RS, as is the case for the last line of U, then the lookup returns the default value for the type, i.e. 0 (zero) here as the type is number.

In order to prevent unmatched lookups being replaced by default values, the default fail option can be specified. This can be done by replacing the declaration line for U.N by:

U.N = RS.N[r: U.I, s: U.J] default fail

Once this replacement is done, the above script fails as the last line of the table U cannot be looked-up with the cross table RS.

Lookups are expected to be infrequently needed in Envision. Default vector behaviors should cover most situations. However, lookups offer a greater degree of expressiveness, which can be required to cope with more complex calculations.

Roadmap: Lookups are read-only operations; they don’t yet have a write counterpart in Envision, although we plan to support such a write counterpart in the future.

Partial lookups

If we look at a cross table as a matrix, a partial lookup can be seen as the selection of a column or of a row: given a column (resp. a row) identifier, the column vector (resp. the row vector) is obtained. The lookup is said to be “partial” - as in partially explicit - because one key is provided explicitly while the other key is provided implicitly:

table R[r] = with
  [| as r |]
  [| 1    |]
  [| 2    |]

table S[s] = with
  [| as s |]
  [| 1    |]
  [| 2    |]
  [| 3    |]

table RS = cross(R, S)
RS.N = r + s

R.N = RS.N[s: 3]
S.N = RS.N[r: 2]

show table "R" a1b5 with R.N
show table "S" c1d5 with S.N

In the above script, the table RS is a cross between the tables R and S. The vector R.N (resp. the vector S.N) is obtained by performing a partial lookup over a line within the S table (resp. the R table). The explicit key belongs to the scalar table while the implicit one belongs to the table R (resp. the S table). As a result, the output of the lookup belongs to the table R (resp. the table S).

The common table used for the pairs of key can be expressed explicitly with a slightly more verbose version of the same script:

table R[r] = with
  [| as r |]
  [| 1    |]
  [| 2    |]

table S[s] = with
  [| as s |]
  [| 1    |]
  [| 2    |]
  [| 3    |]

table RS = cross(R, S)
RS.N = r + s

R.N = RS.N[s: 3 into R]
S.N = RS.N[r: 2 into S]

show table "R" a1b5 with R.N
show table "S" c1d5 with S.N

From another perspective, we could say that the partial lookup is “underspecified”, and returns all the lines that match the constraint expressed by the key.

Performance-wise, a partial lookup over the right dimension is expected to be more efficient than one over the left dimension. In the above example, the calculation of S.N (a left partial lookup) is structurally more efficient than the one of R.N (a right partial lookup). Unless there is some structural twist involved (e.g. a shift of dimension), the right partial lookup usually involves a matrix transposition operation, while the left partial lookup does not.

Advanced remark: The Envision runtime implementation of cross tables can be expected to loosely similar to multidimensional arrays which become quite popular through the ndarray object as found in the open source library NumPy. The left partial lookup is more efficient than the right one because it better preserves the locality of the data accesses.