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 21:19:14 GMT
Message-ID: <m56i9.3934$GJ3.730335_at_twister.nyc.rr.com> 






"--CELKO--" <71062.1056_at_compuserve.com> wrote in message
news:c0d87ec0.0209170539.7ce7653a_at_posting.google.com...

> >> For some reason, what you are trying to do reminds me of the
> process of
> defragmenting a disk. <<
>
> Good thought!
>
> Richard Romley sent me a recursive UDF that computes the new left
> value for a node.  It can be put into one statement then used in
>   UPDATE Tree
>      SET lft = ShiftLeft(left),
>          rgt = ShiftLeft(left) + (rgt-lft);
>
> Very neat.  I have to go out of town, but I will post it when I get
> back.





Actually, it's possible to write a single view, with a few supporting
views for clarity, that can calculate the total amount every node in
the tree needs to be shifted, relative to some reference node, to move
all gaps rightward.  The algorithm is as follows:



forall(Paths P with head node H and tail node T where H = T or T is a

       descendant of H, have T be the node whose shift amount will be
       calculated with respect to the reference node H)


begin


  headNodeLevel := Level(H)


  tailNodeLevel := Level(T)


  forall(Nodes N where Level(N) >= headNodeLevel and

         Level(N) <= tailNodeLevel and
         PN is the node at Level(N) within Path P and
         N's lft value is <= PN's lft value)


  begin


    The total shift amount of T with respect to H is
    sum(ConsecutiveSiblingGap of N) + sum(ParentOldestChildGap of N)
  end


end



The translation of this to SQL is



    
  
  •   For every pair of nodes (N1, N2) where N2 = N1 or N2 is a descendant
  
  •   of N1, calculate the amount of left shifting that needs to be applied
  
  •   to N2 when the tree rooted at N1 is completely left shifted
CREATE VIEW ShiftedLeftValues
AS
SELECT P.head AS rootNode,
       P.tail AS shiftNode,
       SUM(COALESCE(G1.gap, G2.gap, 0)) AS gap
FROM Paths AS P
     INNER JOIN

     NodeLevels AS L1
     ON L1.value = P.tail
     INNER JOIN

     NodeLevels AS L2
     ON L2.value = P.node
     INNER JOIN

     Descendants AS D
     ON D.ancestor = P.head
     INNER JOIN

     NodeLevels AS L3
     ON L3.value = D.descendant AND
        L3.level = L2.level AND
        D.lft <= P.lftNode
     LEFT OUTER JOIN

     ConsecutiveSiblingGaps AS G1
     ON G1.rgtChild = D.descendant
     LEFT OUTER JOIN

     ParentOldestChildGaps AS G2
     ON G2.child = D.descendant
GROUP BY P.head, P.tail






With the helping views defined as



    
  
  •   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 ancestor-descendant relationship where a node
  
  •   is also considered its own descendant
CREATE VIEW Descendants
AS
SELECT T1.value AS ancestor,
       T2.value AS descendant,
       T2.lft AS lft,
       T2.rgt AS rgt
FROM Tree AS T1
     INNER JOIN

     Tree AS T2
     ON 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)

  
  •   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

  
  •   Enumerate all nodes in all paths in tree from a head node to a
  
  •   tail node, both inclusive.
CREATE VIEW Paths
AS
SELECT T1.value AS head,
       T2.value AS tail,
       T3.value AS node,
       T3.lft AS lftNode,
       T3.rgt AS rgtNode
FROM Tree AS T1
     INNER JOIN

     Tree AS T2
     ON T1.lft <= T2.lft AND
        T1.rgt >= T2.rgt
     INNER JOIN

     Tree AS T3
     ON T3.lft BETWEEN T1.lft AND T2.lft AND
        T3.rgt BETWEEN T2.rgt AND T1.rgt






The procedure to actually shift the tree is now very straightforward
and succinct



CREATE PROCEDURE ShiftLeftHelper


_at_node VARCHAR(10) -- reference node of tree or subtree to begin shifting
AS


BEGIN


  UPDATE Tree


  SET lft = Tree.lft - (SELECT gap

                        FROM ShiftedLeftValues
                        WHERE rootNode = _at_node AND
                              shiftNode = Tree.value),
      rgt = Tree.rgt - (SELECT gap
                        FROM ShiftedLeftValues
                        WHERE rootNode = _at_node AND
                              shiftNode = Tree.value)
  WHERE (SELECT gap
         FROM ShiftedLeftValues
         WHERE rootNode = _at_node AND
               shiftNode = Tree.value) > 0





END -- PROCEDURE




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

  
  •   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

  
  •   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






This will produce the same results as my other algorithm.  It would be
interesting to evaluate the performance of these two approaches,
especially on large trees.



Let's look at a couple of examples.



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



To shift the entire tree



EXEC ShiftLeft



Tree becomes



value   lft     rgt


Albert 100 1200


Bert 101 191


Ernie 192 242


Chuck 243 943


Donna 244 344


Eddie 345 445


Fred 446 546



and to shift a subtree, for example,



EXEC ShiftLeftSubtree 'Chuck'



Tree becomes



Albert 100 1200


Bert 111 201


Ernie 250 300


Chuck 301 1001


Donna 302 402


Eddie 403 503


Fred 504 604



Regards,


jag
Received on Wed Sep 18 2002 - 23:19:14 CEST












Original text of this message