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@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
@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 = @node AND
                              shiftNode = Tree.value),
      rgt = Tree.rgt - (SELECT gap
                        FROM ShiftedLeftValues
                        WHERE rootNode = @node AND
                              shiftNode = Tree.value)
  WHERE (SELECT gap
         FROM ShiftedLeftValues
         WHERE rootNode = @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 @root VARCHAR(10) SELECT @root = value FROM RootNode IF @root IS NOT NULL EXEC ShiftLeftHelper @root
• Only left-shift subtree rooted at the given node CREATE PROCEDURE ShiftLeftSubtree @node VARCHAR(10) AS IF EXISTS (SELECT * FROM Tree WHERE value = @node) EXEC ShiftLeftHelper @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 - 16:19:14 CDT