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: Wed, 18 Sep 2002 07:32:07 GMT
Message-ID: <XZVh9.2110$GJ3.401908_at_twister.nyc.rr.com> 






The algorithm I posted previously to solve this problem, while
correct, was unnecessarily constrained.  I had applied shifting level
by level, i.e., before level N is shifted all levels before N are
fully shifted.  This constraint has been removed leading to a cleaner
algorithm and code.  Even though this solution is essentially the same
as the previous one, for completeness and ease of understanding I'll
make this posting self-contained.



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


   the left value of its parent PL.  We look for instances where
   CL - PL > 1.  Let's call this kind of gap a ParentOldestChildGap.
2. Between the left value of a node S2L and the right value of the


   sibling S1R to its immediate left.  We look for instances where
   S2L - S1R > 1.  Let's call this kind of gap a
   ConsecutiveSiblingGap.



Using this notion of gaps, the algorithm to left shift a tree or
subtree rooted at node N is as follows:



declare N TreeNode -- root node


while(exists TreeNode N1 where N1 = N or N1 is a descendant of N and


             N1 has a ConsecutiveSiblingGap or a ParentOldestChildGap)
begin


  forall(TreeNode N1 where N1 = N or N1 is a descendant of N and

         (N1 has a ConsecutiveSiblingGap SG; SG is 0 if none) or
         (N1 has a ParentOldestChildGap PCG; PCG is 0 if none) or
         forall(TreeNode N2 where N2 = N or N2 is a descendant of N
                and N2 is an ancestor of N1 and N2 has an ancestor
                ConsecutiveSiblingGap ASG or an ancestor
                ParentOldestChildGap APCG; ASG and APCG are 0 if none))


  begin


    update N1.lft = N1.lft - SG - PCG - SUM(ASG) - SUM(APCG),


           N1.rgt = N1.rgt - SG - PCG - SUM(ASG) - SUM(APCG)
    from N1


  end


end



Note that when left shifting a node with a gap, the same amount of
shifting must be simultaneously applied to all descendants of this
node so that the tree's ancestor-descendant relationship, represented
by nested sets, is always maintained.



Below is T-SQL code, tested on SQL Server, that implements this
algorithm followed by a few examples.  Note that while iteration is
used, no temp tables or extra columns are required and no local
variables are needed in the loop.



First, let's show the DDL code 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', 111, 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.



    
  
  •   Tree's root node
CREATE VIEW RootNode
AS
SELECT T1.value, T1.lft, T1.rgt
FROM Tree AS T1
WHERE NOT EXISTS (SELECT *

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

  
  •   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,
       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)

  
  •   Gap between parent and oldest child, i.e., leftmost child, > 0
CREATE VIEW ParentOldestChildGaps
AS
SELECT C1.parent AS parent,
       C1.child AS child,
       C1.lftChild - C1.lftParent - 1 AS gap
FROM Children AS C1
WHERE NOT EXISTS (SELECT *

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






Finally, the stored procedure that does the left shifting.



    
  
  •   Procedures to left-shift tree
  
  •   All gaps are moved rightward
  
  •   All spreads remain the same
CREATE PROCEDURE ShiftLeftHelper
_at_node VARCHAR(10), -- root node of tree or subtree to begin shifting
_at_normalizeTree BIT = 0 -- normalize tree?
AS
BEGIN





IF EXISTS (SELECT *


           FROM RootNode
           WHERE value = _at_node AND
                 lft <> 1) AND




   _at_normalizeTree = 1


BEGIN



  DECLARE _at_rootGap INT


  SELECT _at_rootGap = lft - 1


  FROM RootNode


  UPDATE Tree


  SET lft = Tree.lft - _at_rootGap,


      rgt = Tree.rgt - _at_rootGap


END -- IF




    
  
  •   While any gaps exist at or below provided root node, left shift nodes
  
  •   with gaps and all of their descendants by the necessary amounts
WHILE EXISTS (SELECT *

              FROM ConsecutiveSiblingGaps AS G
              WHERE G.rgtChild = _at_node OR
                    EXISTS (SELECT *

                            FROM Descendants AS D
                            WHERE D.ancestor = _at_node AND
                                  D.descendant = G.rgtChild)) OR
      EXISTS (SELECT *

              FROM ParentOldestChildGaps AS G
              WHERE G.child = _at_node OR
                    EXISTS (SELECT *

                            FROM Descendants AS D
                            WHERE D.ancestor = _at_node AND
                                  D.descendant = G.child))
BEGIN

  UPDATE Tree
  SET lft = Tree.lft -
            COALESCE((SELECT gap
                      FROM ConsecutiveSiblingGaps
                      WHERE rgtChild = Tree.value),
                     (SELECT gap
                      FROM ParentOldestChildGaps
                      WHERE child = Tree.value),
                     0) -
            COALESCE((SELECT SUM(G.gap)
                      FROM ConsecutiveSiblingGaps AS G
                           INNER JOIN

                           Descendants AS D1
                           ON D1.ancestor = G.rgtChild AND
                              D1.descendant = Tree.value AND
                              (G.rgtChild = _at_node OR
                               EXISTS

                               (SELECT *

                                FROM Descendants AS D2
                                WHERE D2.ancestor = _at_node AND
                                      D2.descendant = G.rgtChild))), 0) -
            COALESCE((SELECT SUM(G.gap)
                      FROM ParentOldestChildGaps AS G
                           INNER JOIN

                           Descendants AS D1
                           ON D1.ancestor = G.child AND
                              D1.descendant = Tree.value AND
                              (G.child = _at_node OR
                               EXISTS

                               (SELECT *

                                FROM Descendants AS D2
                                WHERE D2.ancestor = _at_node AND
                                      D2.descendant = G.child))), 0),
      rgt = Tree.rgt -
            COALESCE((SELECT gap
                      FROM ConsecutiveSiblingGaps
                      WHERE rgtChild = Tree.value),
                     (SELECT gap
                      FROM ParentOldestChildGaps
                      WHERE child = Tree.value),
                     0) -
            COALESCE((SELECT SUM(G.gap)
                      FROM ConsecutiveSiblingGaps AS G
                           INNER JOIN

                           Descendants AS D1
                           ON D1.ancestor = G.rgtChild AND
                              D1.descendant = Tree.value AND
                              (G.rgtChild = _at_node OR
                               EXISTS

                               (SELECT *

                                FROM Descendants AS D2
                                WHERE D2.ancestor = _at_node AND
                                      D2.descendant = G.rgtChild))), 0) -
            COALESCE((SELECT SUM(G.gap)
                      FROM ParentOldestChildGaps AS G
                           INNER JOIN

                           Descendants AS D1
                           ON D1.ancestor = G.child AND
                              D1.descendant = Tree.value AND
                              (G.child = _at_node OR
                               EXISTS

                               (SELECT *

                                FROM Descendants AS D2
                                WHERE D2.ancestor = _at_node AND
                                      D2.descendant = G.child))), 0)
  WHERE (Tree.value = _at_node OR
         EXISTS (SELECT *

                 FROM Descendants
                 WHERE descendant = Tree.value AND
                       ancestor = _at_node)) AND
        (EXISTS (SELECT *

                 FROM ConsecutiveSiblingGaps AS G
                 WHERE G.rgtChild = Tree.value) OR
         EXISTS (SELECT *

                 FROM ConsecutiveSiblingGaps AS G
                      INNER JOIN

                      Descendants AS D1
                      ON D1.ancestor = G.rgtChild AND
                         D1.descendant = Tree.value AND
                         (G.rgtChild = _at_node OR
                          EXISTS (SELECT *

                                  FROM Descendants AS D2
                                  WHERE D2.ancestor = _at_node AND
                                        D2.descendant = G.rgtChild))) OR
         EXISTS (SELECT *

                 FROM ParentOldestChildGaps AS G
                 WHERE G.child = Tree.value) OR
         EXISTS (SELECT *

                 FROM ParentOldestChildGaps AS G
                      INNER JOIN

                      Descendants AS D1
                      ON D1.ancestor = G.child AND
                         D1.descendant = Tree.value AND
                         (G.child = _at_node OR
                          EXISTS (SELECT *

                                  FROM Descendants AS D2
                                  WHERE D2.ancestor = _at_node AND
                                        D2.descendant = G.child))))
END -- WHILE

END -- PROCEDURE


  
  •   Left-shift complete tree
CREATE PROCEDURE ShiftLeft
AS
DECLARE _at_root VARCHAR(10)
SELECT _at_root = value
FROM RootNode
IF _at_root IS NOT NULL
  EXEC ShiftLeftHelper _at_root

  
  •   Left-shift complete tree with the root's left value set to 1, i.e.,
  
  •   placed in normal form
CREATE PROCEDURE ShiftLeftNormalized
AS
DECLARE _at_root VARCHAR(10)
SELECT _at_root = value
FROM RootNode
IF _at_root IS NOT NULL
  EXEC ShiftLeftHelper _at_root, 1

  
  •   Only left-shift subtree rooted at the given node
CREATE PROCEDURE ShiftLeftSubtree
_at_node VARCHAR(10)
AS
IF EXISTS (SELECT * FROM Tree WHERE value = _at_node)
  EXEC ShiftLeftHelper _at_node






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



value   lft     rgt


Albert 100 1200


Bert 111 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 191


Ernie 192 242


Chuck 243 943


Donna 244 344


Eddie 345 445


Fred 446 546



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



EXEC ShiftLeftNormalized



which results in the following tree



value   lft     rgt


Albert 1 1101


Bert 2 92


Ernie 93 143


Chuck 144 844


Donna 145 245


Eddie 246 346


Fred 347 447



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


Ernie 250 300


Chuck 301 1001


Donna 302 402


Eddie 403 503


Fred 504 604



or



EXEC ShiftLeftSubtree 'Ernie'



value   lft     rgt


Albert 100 1200


Bert 111 201


Ernie 202 252


Chuck 400 1100


Donna 501 601


Eddie 701 801


Fred 901 1001



Regards,


jag
Received on Wed Sep 18 2002 - 09:32:07 CEST












Original text of this message