# Re: Trees in SQL

From: --CELKO-- <71062.1056_at_compuserve.com>
Date: 7 Jul 2002 12:33:55 -0700

>> 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

Original text of this message