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

From: Kendall <kendallwillets_at_yah000.com>
Date: Wed, 18 Sep 2002 19:06:36 -0700
Message-ID: <pan.2002.09.18.19.06.36.486.11608@yah000.com>

In article <c0d87ec0.0209131524.42b8085b_at_posting.google.com>, "--CELKO--" <71062.1056_at_compuserve.com> wrote:

>>> I'm a bit confused about what this is trying to achieve, but it

> looks like a lot of work, so why not try this: .. <<
>
> That is the standard way to close up all the gaps in a Nested Sets
> model. But what I want to do is keep the spread the same and close only
> the gaps. A spread is defined as (rgt -lft) -- the size of a given node
> and how much roo it has for children. A gap is the different between
> the (rgt) value of one and the (lft) value of its sibling on the
> immeidate left or right side.
>
> I want to retain the spread, but close the gaps by moving the nodes to
> the left. This will leave me with a single large gap on the right of
> each parent.
>
>
>
>

It could be possible to do this with one sql statement, but it's difficult. The main idea is to sum the offsets for all the ancestors of a node, which are calculated by adding up left siblings' spreads on each level. These offsets are exactly the difference between a node's lft value and that of its parent in the intended result set.

Example time:

           parent( 0, 100 )
          /        |       \

  s1(3, 13) s2( 35, 40 ) s3( 77, 87 )

Shifting left means starting at the parent's lft value and adding spreads from s1 across to s3, which is a simple join. The spreads above are 10, 5, and 10, so the resulting ranges are (1,11), (12,17), and (18.28).

So, the offset for a given node n from its parent's lft is

     1+ sum( 1+ leftsibling.rgt - leftsibling.lft ) where leftsibling.parent_id = n.parent_id and leftsibling.rgt < n.lft.

A view for the same:

create view siblingoffset( node_id int, lft int, rgt int,

     lft_offset, rgt_offset )
as

    select

        n.node_id, n.lft, n.rgt,
        1 + sum( 1+ leftsibling.rgt - leftsibling.lft ), 
        1 + sum( 1+ leftsibling.rgt - leftsibling.lft ) + (n.rgt - n.lft)

from

    orgchart n, orgchart leftsibling
where n.parent_id = leftsibling.parent_id and leftsibling.rgt < n.lft

Given the sibling offsets, it's a matter of summing them for all nodes x in the path from root, ie the usual nested sets predicate, where x.lft < n.lft and x.rgt > n.rgt. The sum is the offset from root's lft value (1 or 0).

update orgchart n set lft =
  ( select sum( x.lft_offset ) from siblingoffset x     where n.lft >= x.lft and n.rgt <= x.rgt ),   rgt =
  (select sum( x.rgt_offset ) from siblingoffset x     ....same....)

The update could be more elegant, but this form is fairly clear. Received on Wed Sep 18 2002 - 21:06:36 CDT