Re: Account Hierachies

i put together the following demo last year. the problem occurs often enough to make one wonder why it's not used as a standard benchmark for expressivity/performance.

given a table expressing some account hierarchy, and a table of transactions on the leaf-accounts, generate the rollup table.

the rollup table contains one record for each node in the tree (including leaf-accounts). the value of a record in the rollup table is the sum of the subordinate accounts and the count of subordinate transactions.

the particular demo happens to be coded in k, a fast vector language also used to code kdb, a sql-based database engine.

whether or not you care to follow the code, running the example displays three tables which are involed in the demo. sql partisans might wish to try to duplicate the solution in their preferred tongue.

to run: go to www.kx.com, download and install kdb for windows or linux. the download is 180k, and takes about .5 seconds to install. clip the code below and store it as a text file called, say, rollup.k. then run it from a command prompt: k rollup.k

there are five "blocks" of code in the script:

1. define the three input parameters: Records (defaults to 100,000) is the number of transaction records; Level (defaults to 3) is the number of levels in the account hierarchy; Nodes (defaults to 10) is the maximum number of nodes at each level of the hierarchy.
2. next, generate the account tree. this is a table Tree with two fields: child and parent.
3. next, generate the raw transactions. this is a table Trans with two fields: leaf, the id of the leaf-account; and value, the value of the transaction, a randomly selected floating point number between 0 and 1.
4. next, calculate the rollup table. this a table with three fields: node, all the account ids; sum, the sum of all subordinate transactions; and count, the count of all subordinate transactions.
5. arrange the tables and parameters for interactive display. the key calculations are defined as functional dependencies on the three input parameters. for example, by changing the Records input from 100000 to 5000000, five million new transactions are generated, and the rollup table recalculated (this takes about 2 seconds on my 450 mhz pentium II). or the number of levels or maximum nodes for the hierarchy table can be redefined by changing Level or Node.

--

\e 0

/ parameters:

Records:100000
Level:3
Nodes:10

/ generate account tree:

tree:{[level;nodes;parent;child](child;parent),'
:[level;,'/_f[level-1;nodes;child]'inc'!2+()_draw nodes-1;2#,!0]}
inc:{x;:Inc+:1}
Inc..d:"Level;Nodes;0"
Tree..d:".+(`child`parent;+{x_at_<x}@+tree[Level;Nodes;0;0])"

/ generate transactions:

gen:{[tree;count]
 c:tree.child_at_&~tree.child _lin tree.parent
 .((`leaf;c count _draw#c);(`value;count _draw 0))}

Trans..d:"gen[Tree;Records]"

/ calculate rollups:

sum:{[tree;trans]
 point:tree.child?/:tree.parent                        / point[i] is the
parent of i
 points:point\'!#point                                 / all paths to grand
total
 groups:tree.child?/:trans.leaf                        / group the leaves
 float:(#point)#0.                                     / initialize to 0.0
 sums:_at_[float;points;+;@[float;groups;+;trans.value]]  / total up the tree
 int:(#point)#0                                        / initialize to 0
 counts:_at_[int;points;+;@[int;groups;+;1]]              / count up the tree
 .((`node;tree.child);(`sum;sums);(`count;counts))}    / return a table

Rollup..d:"sum[Tree;Trans]"

/ arrange window components and show:

.k..c:`form
.k..a:,+(`Level`Nodes`Records;`Tree`Trans`Rollup)
`show$`.k


Markus Janscha <markus_at_janscha.co.uk> wrote in message
news:89oqf8$gm9$1_at_gxsn.com...


> Sorry, perhaps I was not clear enough when I referred to parent child


> relationships.

>  I am talking about account numbers not people.

> For example numbers 1 to 9 have a parent 10 (total of 1 to 9)

> Parents 10, 20, ..... are grouped under parent 100 (for example)

> I can draw a tree representing the hierarchy but what is the best table

> design?

> There are three parent levels

> Markus

>


> Joe "Nuke Me Xemu" Foster <joe_at_bftsi0.UUCP> wrote in message


> news:sbutmackee6159_at_corp.supernews.com...

> > "Markus Janscha" <markus_at_janscha.co.uk> wrote in message

 news:89nqjs$3o2$1_at_gxsn.com...


> >

> > > Could anyone please point me to a source of information for creating


 account


> > > hierarchies.


 


> > > I need to make child - parent and parent - parent relationships.


> > > Some data sets  must only be entered into children but

> > > some data sets (budgets) may have to be entered into a parent level.

 


> > > The parent level would also have to be identified.


 


> > > I was thinking of building recursive relationships with a parent or


 child


> > > flag?


> >

> > What happens when children become parents themselves? I'd use a Person

> > table and a separate Relationship table to encode the relationships

> > between various people.

> >

> > --

> > Joe Foster <mailto:jfoster_at_ricochet.net>  Space Cooties!

 <http://www.xenu.net/>


> > WARNING: I cannot be held responsible for the above        They're


 coming  to


> > because  my cats have  apparently  learned to type.        take me away,


 ha ha!


> >

> >

>
>