Software Development

# kdb+/q – Display a Table as a Tree

This post shows how you can convert a keyed table to a hierarchical tree format in kdb+/q. This could be useful if you want to display data as a tree widget in a front-end.

Consider the following keyed table of world populations:

 0102030405060708091011121314 continent     country        city            | population---------------------------------------------| ----------North America United States  New York City   | 8550405North America United States  Los Angeles     | 3971883North America Mexico         Mexico City     | 8918653Europe        United Kingdom London          | 9126366Europe        Russia         Moscow          | 12195221Europe        Russia         Saint Petersburg| 5383890Africa        Nigeria        Lagos           | 14862000Africa        Egypt          Cairo           | 9908788Africa        Egypt          Giza            | 8800000Asia          China          Shanghai        | 22315474Asia          India          Mumbai          | 12691836Asia          China          Beijing         | 11716620

We would like to display it as a tree of continent > country > city, as shown below (similar to a pivot table in Excel):

 010203040506070809101112131415161718192021222324252627 node                        | population----------------------------| ----------Total                       | 128441136    Asia                    | 46723930        China               | 34032094            Shanghai        | 22315474            Beijing         | 11716620        India               | 12691836            Mumbai          | 12691836    Africa                  | 33570788        Egypt               | 18708788            Cairo           | 9908788            Giza            | 8800000        Nigeria             | 14862000            Lagos           | 14862000    Europe                  | 26705477        Russia              | 17579111            Moscow          | 12195221            Saint Petersburg| 5383890        United Kingdom      | 9126366            London          | 9126366    North America           | 21440941        United States       | 12522288            New York City   | 8550405            Los Angeles     | 3971883        Mexico              | 8918653            Mexico City     | 8918653

In order to achieve this, we need to aggregate the data with different groupings, then combine the resultant tables and format it into a tree.

1. Grouping the data

First, we will add a dummy Total column to the table and then aggregate the table with the following groupings:

• Total
• Total, continent
• Total, continent, country
• Total, continent, country, city

The code for this is shown below:

 01020304050607080910111213 // add Total column to the table. (td is a keyed table)td:(`Total,keys[td]) xkey update Total:`Total from td;keyCols:keys td; // create a list of groupingsgroupings:(1+til count keyCols) sublist\: keyCols; // aggregate the table with each grouping// this gives us a list of keyed tables (one per grouping)tds:?[td;();;c!(sum;)each c:cols value td] each {x!x} each groupings; // this step is optional but it's nice to sort each table on populationtds:`population xdesc'tds;

2. Joining the data

Next, we need to join the tables that were obtained as a result of the groupings. We do this by unkeying the tables and then using uj:

 1 td:keyCols xkey (uj/) 0!'tds;

3. Formatting the data

Now let’s add a Path column by concatenating the key columns:

 12 td:![td;();0b;enlist[`Path]!enlist(`\$sv';">";(string;(each;{x except `};(flip;enlist,keyCols))))];td:(`Path,keyCols) xkey td;

This is what our tree looks like so far:

 010203040506070809101112131415161718192021222324252627 Path                                            Total continent     country        city            | population---------------------------------------------------------------------------------------------------| ----------Total                                           Total                                              | 128441136Total>Asia                                      Total Asia                                         | 46723930Total>Africa                                    Total Africa                                       | 33570788Total>Europe                                    Total Europe                                       | 26705477Total>North America                             Total North America                                | 21440941Total>Asia>China                                Total Asia          China                          | 34032094Total>Africa>Egypt                              Total Africa        Egypt                          | 18708788Total>Europe>Russia                             Total Europe        Russia                         | 17579111Total>Africa>Nigeria                            Total Africa        Nigeria                        | 14862000Total>Asia>India                                Total Asia          India                          | 12691836Total>North America>United States               Total North America United States                  | 12522288Total>Europe>United Kingdom                     Total Europe        United Kingdom                 | 9126366Total>North America>Mexico                      Total North America Mexico                         | 8918653Total>Asia>China>Shanghai                       Total Asia          China          Shanghai        | 22315474Total>Africa>Nigeria>Lagos                      Total Africa        Nigeria        Lagos           | 14862000Total>Asia>India>Mumbai                         Total Asia          India          Mumbai          | 12691836Total>Europe>Russia>Moscow                      Total Europe        Russia         Moscow          | 12195221Total>Asia>China>Beijing                        Total Asia          China          Beijing         | 11716620Total>Africa>Egypt>Cairo                        Total Africa        Egypt          Cairo           | 9908788Total>Europe>United Kingdom>London              Total Europe        United Kingdom London          | 9126366Total>North America>Mexico>Mexico City          Total North America Mexico         Mexico City     | 8918653Total>Africa>Egypt>Giza                         Total Africa        Egypt          Giza            | 8800000Total>North America>United States>New York City Total North America United States  New York City   | 8550405Total>Europe>Russia>Saint Petersburg            Total Europe        Russia         Saint Petersburg| 5383890Total>North America>United States>Los Angeles   Total North America United States  Los Angeles     | 3971883

4. Reordering the rows

The tree looks okay so far and you can stop there if you want but it would look better if child nodes were directly under their parents e.g. Shanghai should appear under China. In order to do this, we cannot simply use uj to combine our tables but we need to use the Over (/) accumulator to build the tree instead.

In order to get the row ordering correct, we add an id to each row, which will be a combination of the parent id and the row id. These id’s look like this: 0, 0.0, 0.1, 0.1.1 etc. and will be used to sort the tree so that children appear under their parents.

Here is the final version of the code:

 0102030405060708091011121314151617181920212223242526272829303132333435363738394041424344454647 // Converts a table into a tree.// @param td - a keyed table// @param sortCol - the column to sort on// @returns a table with a tree columntable2tree:{[td;sortCol]    // add Total column to the table    td:(`Total,keys[td]) xkey update Total:`Total from td;    keyCols:keys td;     // create a list of groupings    groupings:(1+til count keyCols) sublist\: keyCols;     // aggregate the table with each grouping    // this gives us a list of keyed tables (one per grouping)    tds:?[td;();;c!(sum;)each c:cols value td] each {x!x} each groupings;     // sort the tables    if[not null sortCol;tds:sortCol xdesc'tds];     // initial tree only has the Total row    tree:update id:"0",node:enlist "Total" from 0!first tds;     // build the tree using the over accumulator    tree:{[tree;td]        keyCols:keys td;         // join the parent id to the current table        td:td lj k xkey ?[tree;();0b;{x!x}(k:-1_keyCols),`id];         // update the id by concatenating the parent id to the row id        // we need to left-pad the row id so that sorting works correctly        // e.g. 1.3 should come before 1.10        td:update id:`\$"."sv'flip(string id;(-1*count string count td)\$string i) from td;         // add a node column which corresponds to the value of the last key column        td:![td;();0b;enlist[`node]!enlist last keyCols];         // add indentation to the node based on the depth (i.e. number of key columns)        indentation:(4*-1+count keyCols)#" ";        td:update node:(indentation,/:string node) from td;         // now add the table to tree        tree uj 0!td    }/[tree;1_tds];     // sort the tree on id    (`node,keyCols) xkey `id xasc tree}

This is what our final tree looks like:

 010203040506070809101112131415161718192021222324252627282930 q) data:3!("SSSI";enlist",") 0: `\$"population.csv";q) select node,population from table2tree[data;`population] node                         population-----------------------------------------Total                        128441136    Asia                     46723930        China                34032094            Shanghai         22315474            Beijing          11716620        India                12691836            Mumbai           12691836    Africa                   33570788        Egypt                18708788            Cairo            9908788            Giza             8800000        Nigeria              14862000            Lagos            14862000    Europe                   26705477        Russia               17579111            Moscow           12195221            Saint Petersburg 5383890        United Kingdom       9126366            London           9126366    North America            21440941        United States        12522288            New York City    8550405            Los Angeles      3971883        Mexico               8918653            Mexico City      8918653

I also played around with adding lines to connect nodes of the tree but it got complicated very fast!

Can you think of a better way to do this? Let me know in the comments below!

 Published on Java Code Geeks with permission by Fahd Shariff, partner at our JCG program. See the original article here: kdb+/q – Display a Table as a TreeOpinions expressed by Java Code Geeks contributors are their own.

### Fahd Shariff

Fahd is a software engineer working in the financial services industry. He is passionate about technology and specializes in Java application development in distributed environments.
Subscribe
Notify of

This site uses Akismet to reduce spam. Learn how your comment data is processed.