# Re: Trees in SQL

Date: 7 Jul 2002 12:33:55 -0700

Message-ID: <c0d87ec0.0207071133.52279297_at_posting.google.com>

>> Aha, I was thinking I should check that before I typed it, but it's

good

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

LEFT OUTER JOIN 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