Re: Trees in SQL

In article <c0d87ec0.0207031059.551461ce_at_posting.google.com>, "--CELKO--" <71062.1056_at_compuserve.com> wrote:

You know, there is a way to use the nested sets with the percentage factors, which I just thought of/remembered from a similar problem.

If you have a tree structure with a percentage "discount" at each link, you can figure out each node's contribution to the root node's total by multiplying the node's cash-on-hand by the product of all the percentages along its path to root, to get a "total discount", eg:

                 total discount
root       -->  1.0          
  .8 A     -->  .8


    .4 B   -->  .8 * .4 = .32


    .4 C   -->  .32


      .3 D -->  (.8 * .4 * .3 = .096 )
  .3 E     -->  .3

The discount factor is just the product of the discounts on each parent-child link in the path to root; each node has a single path to root and a single discount (the graph must be a tree for this to work, but the method of decomposing a DAG into a tree is applicable).

So root's total cash is just a weighted sum of its subordinates,   totcash = .8A + .32B + .32C + ... + .06F

So far we have a quick way to total up root's cash, but not the other nodes. However, the factors we've created have a useful property: divisibility. If we want to find, say, the contributions of each of A's subordinates to A, we can divide out the discount factor between A and the root (.8), to get the correct discounts from A's subordinates to A.. We get:

node discount summing to A

A      (.8 / .8 = 1 )
  B    ( .32 / .8 = .4 )
  C    ( same - .4  )
    D  ( .096 / .8 = .12 )

In general, for a given node n, we divide n's root-discount into the root-discounts of its subordinates, and get the discounts from the subordinates to n.

In SQL terms, if we have columns:

node( id, parent_id, nodenum, lhs, rhs, rootDiscount, cashOnHand )

we can get totCash for a given ID as follows:

select sum( (sub.rootdiscount / target.rootdiscount) * sub.cashOnHand ) from node target, node sub
where target.id = ?
and sub.nodenum between target.lhs and target.rhs

This is the usual nested sets query to get the subordinates.

I've done similar things just to get paths between arbitrary nodes. Store the path to root for each node, and then "subtract" the ancestor's path from its subordinate's path to get the path from ancestor to subordinate. Path algebra ;-) Received on Thu Jul 04 2002 - 00:11:49 CEST