No Stinking Loops
Tables with calculated columns
Vector 25:1, page 74
K4 has a quite different way of representing tables from that used in K3. This article describes how to simulate in q the column dependencies that K3 supported.
0. Dependencies¶
In K3, tables are pseudotypes, dictionaries of vectors. The ‘columns’ of a ‘table’ are first-class variables. Thus, using dot-notation:
The ‘records’ of a table are the corresponding elements of the ‘column’ variables.
A variable is a data-structure with three components:
- a simple symbolic name, e.g.
`f - a value, e.g.
10 20 30 - a recursive dictionary of attributes
The d attribute is used to define the variable as a functional dependency. For example, using double-dot-notation:
Thus, h is a variable in the dictionary t, having name t, value 50 70 90, and an attribute dictionary containing a single variable with name d, value "f+g", and empty attribute dictionary:
The evaluation of t recursively evaluates the columns f, g, and h of t. t.h depends on f and g. If either f or g changes, h is marked ‘invalid’. If h is invalid, then on reference it recalculates in t using f and g.
The K3 workspace is a tree of dictionaries rooted in the nameless dictionary. We can capture the entire workspace by evaluating the empty symbol; or, as one wag put it, “The value of nothing is everything”:
.`
.((`k
.,(`t
.((`f
10 20 30
)
(`g
40 50 60
)
(`h
50 70 90
.,(`d;"f+g";)))
)
)
(`t;-7.584544e+008;))
In q (i.e. K4) a table is a list of records – structurally identical dictionaries. The columns of a table are the corresponding entries of the records. (N.B. internally, q stores the table as a structure of column-lists.)
How then can we simulate in q the column dependencies we get for free in K3?
1. Tables and views.¶
In q we have tables:
and we have views:
v depends on t. When t is modified, v becomes ‘invalid’. v will be recalculated (‘validated’) the next time it is referenced:
2. Calculated columns¶
We can use update to add calculated columns to a table:
but q won’t allow us to add columns unless they depend strictly on existing columns in the table:
Columns must be added as a correctly-ordered sequences of separate updates:
q)update l:k*2 from update k:f+g from t
f g k l
-------------
20 50 70 140
30 60 90 180
40 70 110 220
3. Automating calculated columns¶
Let’s divide up the parameters to the problem and assign them to distinct variables:
| t | is a table |
| f | is a data-structure containing the names and definitions of calculated columns |
| v |
is a view which depends on t and f
|
For example, f might be defined through a GUI, in which users specify the calculated columns.
v will be a view which functionally depends on t and f:
The function willbe takes t and f as arguments and returns a table containing the columns of t plus the defined columns, or ‘willbes’, specified by f.
4. Implementation 1: update over¶
To start, let’s use q’s native parsing primitive to analyze the structure of the successful update from section 2:
q)parse"update l:k*2 from update k:f+g from t"
!
(!;`t;();0b;(,`k)!,(+;`f;`g))
()
0b
(,`l)!,(*;`k;2)
The functional form of update is:
where t is the table to be updated, a is the constraint, or ‘where’ clause, b is the group, or ‘by’ clause, and c is the dictionary of names and definitions of the columns to be added.
In the problem at hand we have no constraints and no grouping, so by convention a and b are () and 0b.
The column definitions are unit dictionaries. Each one gives the name and definition of a single field. A unit dictionary maps a one-element symbolic vector – the name – to a one-element parse of the definition. So, for example:
The form of the successful update is:
where kdict and ldict are unit-dictionaries which define k and l respectively. Generalising, we see that in order to add columns c1…cn to t we have to construct an expression of the form:
Let’s simplify this by defining a function which eliminates the constants:
col takes three arguments: x is a table, y is a symbol, and z is the parse of a definition. col returns x updated with the new column y. So:
We know what to do with this pattern: express it as the application of col over t, a vector of names, and a list of definitions:
col executes n times. Initially, t is updated with c1 to produce t1. Then t1 is updated with c2 to produce t2.
q)col/[t;`k`l;parse each("f+g";"k*2")]
f g k l
-------------
20 50 70 140
30 60 90 180
40 70 110 220
5. Implementation 2: column references¶
q still requires that we order the definitions correctly:
Let’s start by having f, our dictionary of column definitions:
Then parse each expression:
We want to order p by column-reference, but first we have to extract these from each parsed definition. The algorithm is recursive: descend the parse tree looking for symbol atoms:
We read the conditional $[..] as follows:
- if
xis a symbol, returnx - else if
xis not a list, return() - else
self each x
For example:
Since each recursion adds a level of nesting, we need to flatten the result. The q primitive raze (K: ,/) takes a list of sublists and returns the catenation of the sublists. The raze of x reduces one level of nesting. And since references can occur more than once in an expression, we need to compress out duplicates with distinct.
Since the result of ref is a tree it will often contain more than one level of nesting. For example:
But distinct raze reduces just one level:
To flatten a list of arbitrary depth, we keep applying raze until the result converges. That is, until the result cannot be any flatter:
So the final form of our function for extracting references from a parse-tree is:
Thus:
6. Implementation 3: column order¶
Now that we have the references of p just one piece remains: re-order p so we can add columns to t in correct order.
Let’s define f as follows:
Now if we index r by k:
we get the references of each definition. Notice that some symbols in the result are indices of r (`h`j`k) and some are not (`f`g). Indexing r by one of the latter returns an empty list:
In this process, we are drilling down in parallel to the ultimate constituents of each definition in r. Eventually, we bottom out in a nest of empties, since the ultimate constituents (f and g) are columns of t:
To capture the sequence of intermediates, we use scan:
q)r scan k
h j k
`j`k `f`g ,`j
(`f`g;,`j) (`symbol$();`symbol$()) ,`f`g
((`symbol$();`symbol$());,`f`g) (();()) ,(`symbol$();`symbol$())
((();());,(`symbol$();`symbol$())) (();()) ,(();())
((();());,(();())) (();()) ,(();())
Reversing the result, we get the constituent analysis of f in calculation order:
q)reverse r scan k
((();());,(();())) (();()) ,(();())
((();());,(`symbol$();`symbol$())) (();()) ,(();())
((`symbol$();`symbol$());,`f`g) (();()) ,(`symbol$();`symbol$())
(`f`g;,`j) (`symbol$();`symbol$()) ,`f`g
`j`k `f`g ,`j
h j k
The nesting and the empties are irrelevant, so we flatten the analysis:
This gives us a valid calculation order: the ultimate constituents first (in no particular order), followed by j (f+g), k (j*100), and h (j+k).
For complex f, flatten over reverse r scan key r produces ever-larger and more complex intermediates. By moving the flattening operation into the scan loop we keep the intermediate results as simple as possible, thereby reducing the complexity of the indexing:
Finally, we want to exclude non-calculated constituents from the result:
So our final function is:
7. Synthesis¶
Putting it all together:
willbe:{[t;f]
p:parse each f; / parse of expression
r:refs each p; / references
o:order r; / ordered by reference
col/[t;o;p o]} / create view
flatten:distinct raze over
ref:{$[-11=t:type x;x;t;();.z.s each x]}
refs:flatten ref@
col:{![x;();0b;enlist[y]!enlist z]}
order:{flatten[reverse(flatten x@)scan key x]inter key x}
Let’s run through an example:
8. Partitioned calculations¶
Our implementation allows us to define new columns by applying their definitions to existing columns as wholes. For example, h is all of j plus all of k. Suppose we add a grouping column e to t:
Then we may want to define a new column whose values are computed for each e-partition of t: for the subtable where e=1 and the subtable where e=2.
Notice that our definition of col supplies the constant 0b to the third position of !, so new columns are always computed on the ungrouped input table x:
Let’s add a parameter to willbe which controls grouping:
The new parameter g is a dictionary of ‘group by’ clauses, corresponding to the definitions of the calculated columns f.
We revise our suite of functions accordingly:
willbe:{[t;f;g]
p:parse each f; / parse of expression
r:refs each p; / references
o:order r; / ordered by reference
col/[t;g o;o map'p o]} / create view
flatten:distinct raze over
ref:{$[-11=t:type x;x;t;();.z.s each x]}
refs:flatten ref@
map:{enlist[x]!enlist y}
col:![;();;]
order:{flatten[reverse(flatten x@)scan key x]inter key x}
So that:
q)t:([]e:1 1 2;f:10 20 30;g:40 50 60)
q)f:`h`j`k`l!("j+k";"f+g";"j*100";"k%sum k")
q)g:`h`j`k`l!(0b;0b;0b;enlist[`e]!enlist`e)
q)v::willbe[t;f;g]
q)v
e f g j k h l
------------------------------
1 10 40 50 5000 5050 0.4166667
1 20 50 70 7000 7070 0.5833333
2 30 60 90 9000 9090 1
You can find this source code at www.nsl.com/q/willbe.q
Acknowledgements¶
Thanks to Attila Vrabecz and Michael Rosenberg for corrections and improvements.