Re: transitive closure code and SQL wanted

In article <3CE085F1.A65784C6_at_drew.edu>, "Steve Kass" <skass_at_drew.edu> wrote:

> Steve,
>
> While it's not efficient, the straightforward way to get the
> transitive
> closure is to start with the adjacency matrix M for the graph and
> compute M & M^2 & M^3 ... until there are no further changes.
>

You can also just square the matrix repeatedly. It's a bit faster, and not much difference in coding.

Below is for generalized directed graphs, although a tree could be put in just as well. I don't have a T-SQL server of any kind right now, so it's not tested.

/* T-SQL code for creating transitive closure */ /* status: not running */

/* the base graph for the TC */
create table node( node_id int primary key,...) create table node_relationship( parent_node_id int references node, child_node_id int references node,
primary key (parent_node_id, child_node_id))

/* a temp table to hold the resultant TC */ create table tc(anc_id int, desc_id int, primary key (anc_id, desc_id))

/* initialize with graph edges */
insert into tc select parent_node_id, child_node_id from node_relationship

/* expand using Warshall-type algorithm until no more */ while( @@rowcount > 0 ) /* aka SQL%ROWCOUNT %/  insert into tc select distinct p.anc_id, c.desc_id  from tc p join tc c on p.desc_id = c.anc_id  where not exists (select * from tc t2 where t2.anc_id = p.anc_id

                    and t2.desc_id = c.desc_id)