Re: Trees in SQL

From: --CELKO-- <>
Date: 7 Jul 2002 12:33:55 -0700
Message-ID: <>

>> Aha, I was thinking I should check that before I typed it, but it's
to find out. I've found some db's producing the NULL, though, so they must have nonstandard behavior. <<

A scalar subquery expression converts an empty result set into a NULL,  as in

 SELECT a, (SELECT SUM(b) FROM Foo WHERE 1=0) AS total_b    FROM Bar;

That might be what is happening

>> The basic issue is to identify the "height" of each node, which is
the number of iterations needed to sum from the leaf nodes to a given node N. This quantity is simply the maximum depth to a leaf node from N, i.e. the depth of the subtree rooted at N. <<

Find the depth is easy:

SELECT T2.node, COUNT(T1.node) AS depth   FROM Tree AS T1, Tree AS T2
 WHERE T2.lft BETWEEN 1 AND (SELECT MAX(rgt) FROM Tree)    AND T2.node

       IN (SELECT node FROM Tree WHERE rgt = lft + 1)  GROUP BY T2.node;

What I did with the Frammis parts explosion problem was use a total weight of zero as a marker. The assembly was updated only when ALL of its immediate sub-assemblies had a weight greater than zero (i.e. they had been calculated).

Here is the basic query for immediate subordinates:

SELECT A.node AS assembly, S.node AS sub_assembly   FROM Tree AS S

       Tree AS A
       ON A.lft
          = (SELECT MAX(lft)
               FROM Tree AS OrgChart AS M
              WHERE S.lft > M.lft
                AND S.lft < M.rgt);
Received on Sun Jul 07 2002 - 21:33:55 CEST

Original text of this message