Home -> Usenet -> comp.databases.theory -> Re: Nested set model with large gaps and spreads in the numbering

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

From: John Gilson <jag_at_acm.org>
Date: Mon, 16 Sep 2002 20:47:48 GMT
Message-ID: <Urrh9.64759$c7.18055610_at_twister.nyc.rr.com> 






The issue is to move the gaps between siblings in a tree to the right
of the rightmost sibling while also maintaining the spread between
each node's left and right values.  Additionally, it would be useful
to be able to set the root node's left value to 1 before left shifting
so that the tree is put into "normal form".  This would be useful if
we wanted to present a subtree normalized.  Furthermore, we might want
to begin the left shifting at any node in the tree and not just the
tree's root node.  When working with a very large tree it could be
much more efficient to left shift only certain subtrees, indicated by
giving the subtree's root node.



Before we can left shift a tree we need to identify the gaps to
close.  There are two types of gaps:


1. Between the left value of the oldest, i.e., leftmost, child N1L and


   the left value of its parent N2L.  We look for instances where
   N1L - N2L > 1.


2. Between the left value of a node N1L and the right value of its


   sibling N2R to the immediate left.  We look for instances where
   N1L - N2R > 1.



For all gaps on level N to be closed, all gaps in the previous N-1
levels must have been closed.  This would lead to a top-down
breadth-first iterative algorithm.  However, note that when left
shifting a level N the same amount of shifting must be simultaneously
applied to all descendants of this level so that the tree's
ancestor-descendant relationship, represented by nested sets, is
always maintained.



Below is some T-SQL code, tested on SQL Server, that implements this
followed by a few examples.  The code might appear a bit complex on a
first pass but the algorithm is straightforward.  Note that while
iteration is used, no temp tables or extra columns are required.



First, let's show the DDL and sample data.



CREATE TABLE Tree


(


value VARCHAR(10) NOT NULL PRIMARY KEY,


lft INT NOT NULL CHECK (lft > 0),


rgt INT NOT NULL CHECK (rgt > 0),


CHECK (rgt > lft)


)



INSERT INTO TREE



SELECT 'Albert', 100, 1200


UNION ALL



SELECT 'Bert', 101, 201


UNION ALL



SELECT 'Ernie', 250, 300


UNION ALL



SELECT 'Chuck', 400, 1100


UNION ALL



SELECT 'Donna', 501, 601


UNION ALL



SELECT 'Eddie', 701, 801


UNION ALL



SELECT 'Fred', 901, 1001



Next, let's look at some views that provide structural information
about the tree.



    
  
  •   Define tree levels with the root node being at level 1,
  
  •   not the standard level 0
CREATE VIEW NodeLevels
AS
SELECT T2.value AS value,
       COUNT(T1.value) AS level
FROM Tree AS T1
     INNER JOIN

     Tree AS T2
     ON T2.lft BETWEEN T1.lft AND T1.rgt
GROUP BY T2.value

  
  •   Define tree parent-child relationship
CREATE VIEW Children
AS
SELECT T1.value AS parent,
       T2.value AS child,
       T1.lft AS lftParent,
       T1.rgt AS rgtParent,
       T2.lft AS lftChild,
       T2.rgt AS rgtChild
FROM Tree AS T1
     INNER JOIN

     Tree AS T2
     ON T2.lft > T1.lft AND
        T2.rgt < T1.rgt AND
        NOT EXISTS (SELECT *

                    FROM Tree AS T3
                    WHERE T3.lft > T1.lft AND
                          T3.lft < T2.lft AND
                          T3.rgt < T1.rgt AND
                          T3.rgt > T2.rgt)

  
  •   Define tree ancestor-descendant relationship
CREATE VIEW Descendants
AS
SELECT T1.value AS ancestor,
       T2.value AS descendant
FROM Tree AS T1
     INNER JOIN

     Tree AS T2
     ON T2.lft > T1.lft AND
        T2.rgt < T1.rgt

  
  •   Consecutive siblings with a gap > 0
CREATE VIEW ConsecutiveSiblingGaps
AS
SELECT C1.child AS lftChild,
       C2.child AS rgtChild,
       L.level AS level,
       C2.lftChild - C1.rgtChild - 1 AS gap
FROM Children AS C1
     INNER JOIN

     Children AS C2
     ON C1.parent = C2.parent AND
        C1.rgtChild < C2.lftChild - 1 AND
        NOT EXISTS (SELECT *

                    FROM Children AS C3
                    WHERE C3.parent = C1.parent AND
                          C3.lftChild > C1.rgtChild AND
                          C3.rgtChild < C2.lftChild)
     INNER JOIN

     NodeLevels AS L
     ON L.value = C1.child

  
  •   Gap between parent and oldest child, i.e., leftmost child, > 0
CREATE VIEW ParentOldestChildGaps
AS
SELECT C1.parent AS parent,
       C1.child AS child,
       L.level AS childLevel,
       C1.lftChild - C1.lftParent - 1 AS gap
FROM Children AS C1
     INNER JOIN

     NodeLevels AS L
     ON NOT EXISTS (SELECT *

                    FROM Children AS C2
                    WHERE C2.parent = C1.parent AND
                          C2.lftChild < C1.lftChild) AND
        C1.lftParent < C1.lftChild - 1 AND
        L.value = C1.child






Finally, the stored procedure that does the left shifting.



    
  
  •   Procedures to left-shift tree
  
  •   All gaps are moved rightward
  
  •   All spreads remain the same

  
  •   Only left-shift subtree rooted at the given node
CREATE PROCEDURE ShiftLeftSubtree
_at_node VARCHAR(10)
AS
DECLARE _at_level INT
SELECT _at_level = level
FROM NodeLevels
WHERE value = _at_node
IF _at_level IS NOT NULL
  EXEC ShiftLeftHelper _at_node, @level

  
  •   Left-shift complete tree where the root can optionally be shifted so
  
  •   that its left value is 1
CREATE PROCEDURE ShiftLeft
_at_rootLeftAt1 BIT = 0
AS
DECLARE _at_root VARCHAR(10)
SELECT _at_root = value
FROM NodeLevels
WHERE level = 1
IF _at_root IS NOT NULL
  EXEC ShiftLeftHelper _at_root, 1, @rootLeftAt1

  
  •   This is the main procedure that does all left shifting
CREATE PROCEDURE ShiftLeftHelper
_at_node VARCHAR(10), -- node to start shifting from
_at_level INT, -- node's level (root is level 1)
_at_rootLeftAt1 BIT = 0 -- set root's left value to 1?
AS
BEGIN


  
  •   Current tree level to visit
DECLARE _at_currentLevel INT
SELECT _at_currentLevel = @level

  
  •   Tree height
DECLARE _at_height INT
SELECT _at_height = MAX(level)
FROM NodeLevels

  
  •   Handle left shifting of root node when it's left value is to be 1
IF _at_currentLevel = 1
BEGIN

  IF _at_rootLeftAt1 = 1
  BEGIN


  
      
    
    •   Left shift tree based on gap provided by root node
    DECLARE _at_rootGap INT
    SELECT _at_rootGap = T1.lft - 1
    FROM Tree AS T1
    WHERE NOT EXISTS (SELECT *

                      FROM Tree AS T2
                      WHERE T2.lft < T1.lft AND
                            T2.rgt > T1.rgt)
    UPDATE Tree
    SET lft = CASE WHEN Tree.value = _at_node
                   THEN 1

                   ELSE Tree.lft - _at_rootGap
              END,

        rgt = Tree.rgt - _at_rootGap
  END

END

ELSE

BEGIN


    
        
      
      •   Left shift starting from a node at a level > 1
      
      •   This is the first pass at left shifting a subtree based only on
      
      •   the gap before a subtree's root.  All subsequent left shifting of
      
      •   this subtree provided by levels greater than the subtree's root
      
      •   level will take place in the loop following this block.


    
      

  
    





  DECLARE _at_consecutiveSiblingGap INT


  SELECT _at_consecutiveSiblingGap = G.gap
  FROM ConsecutiveSiblingGaps AS G


  WHERE G.level = _at_currentLevel AND


        G.rgtChild = _at_node



  DECLARE _at_parentOldestChildGap INT


  SELECT _at_parentOldestChildGap = G.gap
  FROM ParentOldestChildGaps AS G


  WHERE G.childLevel = _at_currentLevel AND


        G.child = _at_node



  UPDATE Tree

  SET lft = COALESCE(Tree.lft - _at_consecutiveSiblingGap,
                     Tree.lft - _at_parentOldestChildGap,
                     Tree.lft),
      rgt = COALESCE(Tree.rgt - _at_consecutiveSiblingGap,
                     Tree.rgt - _at_parentOldestChildGap,
                     Tree.rgt)
  WHERE Tree.value = _at_node OR
        EXISTS (SELECT *
                FROM Descendants
                WHERE ancestor = _at_node AND
                      descendant = Tree.value)


END




    
  
  •   Proceed to the level just after the level of the tree's (or
  
  •   subtree's) root node.
SELECT _at_currentLevel = @currentLevel + 1

  
  •   Loop through each level up to the height of the tree
WHILE _at_currentlevel <= @height
BEGIN


  
      
    
    •   Each iteration of this loop will shift a level's nodes further to
    
    •   the left until there are no more gaps on this level.
    
    •   Concurrently, all shifts applied to the nodes on this level are
    
    •   also applied to all of those nodes' descendants so as to maintain
    
    •   the tree's parent-child relationship.
  WHILE EXISTS (SELECT *

                FROM ConsecutiveSiblingGaps AS G
                     INNER JOIN

                     Descendants AS D
                     ON G.level = _at_currentLevel AND
                        D.descendant = G.rgtChild AND
                        D.ancestor = _at_node) OR
        EXISTS (SELECT *

                FROM ParentOldestChildGaps AS G
                     INNER JOIN

                     Descendants AS D
                     ON G.childLevel = _at_currentLevel AND
                        D.descendant = G.child AND
                        D.ancestor = _at_node)
  BEGIN

  UPDATE Tree
  SET lft = COALESCE((SELECT Tree.lft - G.gap
                      FROM ConsecutiveSiblingGaps AS G
                      WHERE G.level = _at_currentLevel AND
                            (G.rgtChild = Tree.value OR
                             EXISTS (SELECT *

                                     FROM Descendants AS D
                                     WHERE D.descendant = Tree.value AND
                                           D.ancestor = G.rgtChild))),
                     (SELECT Tree.lft - G.gap
                      FROM ParentOldestChildGaps AS G
                      WHERE G.childLevel = _at_currentLevel AND
                            (G.child = Tree.value OR
                             EXISTS (SELECT *

                                     FROM Descendants AS D
                                     WHERE D.descendant = Tree.value AND
                                           D.ancestor = G.child))),
                     Tree.lft),
      rgt = COALESCE((SELECT Tree.rgt - G.gap
                      FROM ConsecutiveSiblingGaps AS G
                      WHERE G.level = _at_currentLevel AND
                            (G.rgtChild = Tree.value OR
                             EXISTS (SELECT *

                                     FROM Descendants AS D
                                     WHERE D.descendant = Tree.value AND
                                           D.ancestor = G.rgtChild))),
                     (SELECT Tree.rgt - G.gap
                      FROM ParentOldestChildGaps AS G
                      WHERE G.childLevel = _at_currentLevel AND
                            (G.child = Tree.value OR
                             EXISTS (SELECT *

                                     FROM Descendants AS D
                                     WHERE D.descendant = Tree.value AND
                                           D.ancestor = G.child))),
                     Tree.rgt)
    
    •   Only interested in shifting nodes >= the current level that are
    
    •   also descendants of the supplied root node
  WHERE EXISTS (SELECT *

                FROM Descendants AS D
                     INNER JOIN

                     NodeLevels AS L
                     ON D.descendant = Tree.value AND
                        D.ancestor = _at_node AND
                        L.value = Tree.value AND
                        L.level >= _at_currentLevel)
  END


  
    
  
  •   Prepare to visit next level of nodes
SELECT _at_currentLevel = @currentLevel + 1
END





END


Some examples might be illustrative.  The tree we start with is



value   lft     rgt


Albert 100 1200


Bert 101 201


Ernie 250 300


Chuck 400 1100


Donna 501 601


Eddie 701 801


Fred 901 1001



If we want to left shift the entire tree we execute



EXEC ShiftLeft



so the resulting tree is



value   lft     rgt


Albert 100 1200


Bert 101 201


Ernie 202 252


Chuck 253 953


Donna 254 354


Eddie 355 455


Fred 456 556



If we want to shift the entire tree but start with a left value of 1
for the root node we execute



EXEC ShiftLeft 1



which results in the following tree



value   lft     rgt


Albert 1 1101


Bert 2 102


Ernie 103 153


Chuck 154 854


Donna 155 255


Eddie 256 356


Fred 357 457



Finally, we can just shift a subtree by giving that subtree's root
node by executing



EXEC ShiftLeftSubtree 'Chuck'



which modifies the original table to



value   lft     rgt


Albert 100 1200


Bert 101 201


Ernie 250 300


Chuck 301 1001


Donna 302 402


Eddie 403 503


Fred 504 604



or



EXEC ShiftLeftSubtree 'Eddie'



value   lft     rgt


Albert 100 1200


Bert 101 201


Ernie 250 300


Chuck 400 1100


Donna 501 601


Eddie 602 702


Fred 901 1001



Regards,


jag
Received on Mon Sep 16 2002 - 22:47:48 CEST












Original text of this message