Re: transitive closure code and SQL wanted

>> I want to get code (includes the the database DDL and queries)that will compute the transitive closure of a graph (actually a tree) ...I am aware of the technique that assigns each node in the node_parent table a pair of numbers for the left and right edges of the interval defined by its descendants. <<

If you know the nested sets model, this is easy:

CREATE TABLE OrgChart
(emp CHAR(10) NOT NULL PRIMARY KEY,
  lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),   rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),   CONSTRAINT order_okay CHECK (lft < rgt) );

OrgChart
emp lft rgt

The organizational chart would look like this as a directed graph:

            Albert (1,12)
            /        \
          /            \
    Bert (2,3)    Chuck (4,11)
                   /    |   \
                 /      |     \
               /        |       \
             /          |         \
        Donna (5,6)  Eddie (7,8)  Fred (9,10)

You did not say how you wanted to see each path, so here is one way of doing it:

 SELECT O1.emp AS boss, O2.emp AS subordinate,

       COUNT(O2.lft) AS distance
   FROM OrgChart AS O1, OrgChart AS O2
  WHERE O2.lft BETWEEN O1.lft AND O1.rgt   GROUP BY O1.emp;

This will give you the start and stop nodes of all paths and there distance in edges. Received on Mon May 13 2002 - 14:54:03 CDT