Re: Nested set model with large gaps and spreads in the numbering
Date: Wed, 18 Sep 2002 19:06:36 -0700
Message-ID: <pan.2002.09.18.19.06.36.486.11608_at_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 =
The update could be more elegant, but this form is fairly clear.
( 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....)