Re: Nested set model with large gaps and spreads in the numbering

From: Heinz Huber <hhuber_at_racon-linz.at>
Date: 08 Oct 2002 05:48:20 GMT
Message-ID: <Xns92A14F66A4810hhuberraconlinzat_at_195.3.96.116>

71062.1056_at_compuserve.com (--CELKO--) wrote in news:c0d87ec0.0210041151.6cfc30d8_at_posting.google.com:

>>> Writing a book AND moving!  You're a glutton for punishment. :-) <<

>
> This was not quite my plan, but life is what happens while you are
> working on your dreams.
>

>>> Looking over the many posts in this forum concerning the nested set

> model, I can't help but wonder if one could define the sets equally
> well by replacing the "left" and "right" columns with "node_id" and
> "num_descendants" columns. <<
>
> Actually I have a suggestion somewhat like that. use the pre-order
> traversal number and the rightmost son.
>
> OrgChart
> emp trv_nbr rgt_most
> ==========================
> 'Albert' 1 6
> 'Bert' 2 2
> 'Chuck' 3 6
> 'Donna' 4 4
> 'Eddie' 5 5
> 'Fred' 6 6
>
> The organizational chart would look like this as a directed graph:
>
> Albert (1,6)
> / \
> / \
> Bert (2,2) Chuck (3,6)
> / | \
> / | \
> / | \
> / | \
> Donna (4,4) Eddie (5,5) Fred (6,6)
>
> Remember a shorthand in PL/I where you coudl replace a string of END
> keywords with a single "END <block name>" construct? Same idea.

I've finally found a "simple" sql that calculates all the shifts in this model or also in the original nested set model. The only condition is that you can calculate the nr of "slots" that a row really occupies (I call it the gap).

In your case above that would be:
emp trv_nbr rgt_most gap

---

'Albert'        1    6         6
'Bert'          2    2         1
'Chuck'         3    6         4
'Donna'         4    4         1
'Eddie'         5    5         1
'Fred'          6    6         1

This is incidently milkchaser's num_descendants + 1. But only because you don't have any empty "slots".

To calculate the shift of every row, you take all the gaps of its siblings, the siblings of its parent, the siblings of its grandparent, ... which come before the row. That is the gap of all rows that come before the row and don't have an ancestor that is not an ancestor of this row. Then you add the number of ancestors, since each row needs 1 slot. Here only ancestors are relevant, since other rows have been dealt with by the gaps of their respective ancestor.

SELECT trv_nbr, rght_most,

    (SELECT SUM(rght_most - trv_nbr + 1)

     FROM Employees before
     WHERE before.rght_most < emp.trv_nbr AND NOT EXISTS
         (SELECT trv_nbr
          FROM Employees parent
          WHERE parent.trv_nbr < before.trv_nbr AND 
                before.trv_nbr <= par.rght_most AND 
                parent.rght_most < emp.trv_nbr)) AS gaps, 
    (SELECT COUNT(*) 
     FROM Employees parent 
     WHERE parent.trv_nbr < emp.trv_nbr AND 
           emp.trv_nbr <= parent.rght_most) AS parents, 

    COALESCE(gaps, 0) + parents + 1 AS shift  FROM Employees emp
 ORDER BY trv_nbr;

I'm not sure whether you could directly plug this into an update according to the SQL standard, since I don't know whether all the values of shift have to calculated before the update is made.

But you can surely write a stored procedure that opens a cursor (as a snapshot) on the select above and adjust trv_nbr and rght_most for every row.

Regards,
Heinz Received on Tue Oct 08 2002 - 07:48:20 CEST