Re: Trees in SQL

In article <5bd0d55e.0207011457.652672fb_at_posting.google.com>, "Raymond W." <ray7866_at_yahoo.com> wrote:

> I have the following tables:
>
> Table: Corp
> Fields: LEC#
> Name
> CashonHand
>
> Sample data:
>
> LEC# Name CashOnHand
> 1 Parent 100
> 2 Sub1 200
> 3 Sub2 250
> 4 Sub1a 300
> 5 Sub1b 450
> 6 Sub2a 400
> 7 Sub3 300
>
> Table: Relationship
> Fields: LEC#
> SubLec#
> Relation
>
> Sample Data:
>
> LEC# SubLec# Relation
> 1 2 80%
> 1 3 80%
> 2 4 100%
> 2 5 80%
> 3 6 80%
> 4 7 50%
> 6 7 50%
>
>
This is kind of a pain because you have to apply the percentages at each level.

The easiest way would just be to roll a "total cash" column up the tree, starting at the leaf nodes. The way I do it is just to set the totals to null, then set the leaf nodes to have TotCash = CashonHand. Then iterate, summing child nodes to the parent until all nodes are non-null.

The fun part is that the sum() function yields null if any summand is null, so if you're summing child nodes to parents, you only get a non-null value if all the child nodes are non-null. You are eventually guaranteed to get a non-null value for every node, but you have to iterate. It's a simple systolic algorithm.

Let's see:

Corp( lecnum int primary key, Name varchar(20), CashOnHand float,

      totcash float null )
Relationship( lecnum int references corp, sublecnum int references corp,

   relation float)

• clear totals update Corp set totcash = null;
• set leaf nodes update Corp c set totcash = CashOnHand where c.lecnum not in (select lecnum from relationship);
• loop to propagate non-nulls up the tree. while exists (select * from Corp where totcash is null ) begin update corp p set totcash = CashOnHand + (select sum( relation * c.totcash ) from corp c join relationship r on c.lecnum = r.sublecnum where r.lecnum = p.lecnum ); end

Note - the syntax of the while loop will vary from one DB to another, but hopefully the idea is clear - iterate until done.

Likewise, update statements tend to vary as well. If this doesn't work I could come up with several variations that might. Received on Wed Jul 03 2002 - 23:17:56 CEST