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@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 @node VARCHAR(10), -- root node of tree or subtree to begin shifting @normalizeTree BIT = 0 -- normalize tree? AS BEGIN

IF EXISTS (SELECT *

           FROM RootNode
           WHERE value = @node AND
                 lft <> 1) AND

   @normalizeTree = 1
BEGIN
  DECLARE @rootGap INT
  SELECT @rootGap = lft - 1
  FROM RootNode
  UPDATE Tree
  SET lft = Tree.lft - @rootGap,

      rgt = Tree.rgt - @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 = @node OR EXISTS (SELECT * FROM Descendants AS D WHERE D.ancestor = @node AND D.descendant = G.rgtChild)) OR EXISTS (SELECT * FROM ParentOldestChildGaps AS G WHERE G.child = @node OR EXISTS (SELECT * FROM Descendants AS D WHERE D.ancestor = @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 = @node OR EXISTS (SELECT * FROM Descendants AS D2 WHERE D2.ancestor = @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 = @node OR EXISTS (SELECT * FROM Descendants AS D2 WHERE D2.ancestor = @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 = @node OR EXISTS (SELECT * FROM Descendants AS D2 WHERE D2.ancestor = @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 = @node OR EXISTS (SELECT * FROM Descendants AS D2 WHERE D2.ancestor = @node AND D2.descendant = G.child))), 0) WHERE (Tree.value = @node OR EXISTS (SELECT * FROM Descendants WHERE descendant = Tree.value AND ancestor = @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 = @node OR EXISTS (SELECT * FROM Descendants AS D2 WHERE D2.ancestor = @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 = @node OR EXISTS (SELECT * FROM Descendants AS D2 WHERE D2.ancestor = @node AND D2.descendant = G.child)))) END -- WHILE END -- PROCEDURE
• 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
• Left-shift complete tree with the root's left value set to 1, i.e.,
• placed in normal form CREATE PROCEDURE ShiftLeftNormalized AS DECLARE @root VARCHAR(10) SELECT @root = value FROM RootNode IF @root IS NOT NULL EXEC ShiftLeftHelper @root, 1
• 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

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 - 02:32:07 CDT