Hierarchical Rollup

Problem

Given a set of transactions and a method for assigning each transaction to the leaf of a tree, produce the sum, count, and average of transaction values at each node of the tree.

Representation

We can represent a tree as a table of child-parent records. For example, the tree T:

	0
	  1
	    3
	    5
	  2
	    4
	    6

can be represented as the table:

We need two numbers to generate balanced trees like T: Depth, the number of nodes from the root to any leaf, and Width, the number of branches at each node.

We can represent the transactions as a table U:

U contains ten transaction records. The leaf column maps the value to a leaf in T. In this example, there are six transactions assigned to leaf 3, one to leaf 4, two leaf 6, and one to leaf 5.

We need one number to generate transaction tables like U: Records, the number of transaction records.

The rollup table R has four columns: node, sum, count, and avg. Each record in R maps calculated values to a node in T. For our example above, R looks like this:

Solution

The code is very straightforward:

	Records:1000000
	Width:10
	Depth:5

	Tree..d:".((`child;c);(`parent;,/0,{(#x)#y}':(0,+\\_ Width^!Depth-1)_ c:!+/_ Width^!Depth))"	
	Trans..d:".((`leaf;c Records _draw#c:Tree[`child]_dvl?Tree`parent);(`value;Records _draw 0))"

	Rollup..d:"
	 p:Tree[`parent]\\'!#Tree`parent                  
	 g:Tree[`child]?/:Trans`leaf
	 f:{@[x;p;y;@[x;g;y;z]]}
	 s:f[(#p)#0.;+;Trans`value]
	 c:f[(#p)#0;+;1]          			   
	 .((`node;Tree`child);(`sum;s);(`count;c);(`avg;s%c))"

	.k..c:`form
	.k..a:(`Depth`Width`Records;`Tree`Trans`Rollup)
	`show$`.k

Depth, Width, and Records are input fields. If we type a new value into Depth or Width, Tree recalculates itself. If we type a new value into Records, Trans recalculates itself. If Tree or Trans changes, Rollup recalculates itself.

Tree, Trans, and Rollup are defined as K dependencies: whenever any variable used in the definition changes, the definiens is invalidated; when a variable is on the screen, if it becomes invalid, it is immediately validated by evaluating its definition.

Tree depends on Width and Depth. Trans depends on Records. Rollup depends on Trans and Tree.

The last three lines specify the GUI attributes class and arrangement, and show the set of variables.