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

From: John Gilson <jag_at_acm.org>
Date: Wed, 18 Sep 2002 16:33:06 GMT
Message-ID: <6V1i9.3339$GJ3.581739@twister.nyc.rr.com>

"John Gilson" <jag_at_acm.org> wrote in message news: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.

[...]

Here's the exact same algorithm as described above but with a further simplified and more efficient implementation. The code below should supersede the previous version posted.

The change is in dropping the ancestor-descendant relationship (implemented previously by the Descendants view) in favor of a path relationship (implemented by the Paths view below). The paths relationship is conceptually a relation of triples (head of path, tail of path, node in path) for a tree. For example,

SELECT head, tail, node
FROM Paths
WHERE head = 'Albert' AND tail = 'Donna' ORDER BY lftNode

returns

head tail node
Albert Donna Albert
Albert Donna Chuck
Albert Donna Donna

Here's the new version of the code. The only differences from the previous implementation are adding the Paths view, dropping the Descendants view, and significantly simplifying the implementation of the ShiftLeftHelper procedure by using the Paths view.

• 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)
• 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
• 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
• 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 INNER JOIN Paths AS P ON P.head = @node AND P.node = G.rgtChild) OR EXISTS (SELECT * FROM ParentOldestChildGaps AS G INNER JOIN Paths AS P ON P.head = @node AND P.node = G.child) BEGIN UPDATE Tree SET lft = Tree.lft - COALESCE((SELECT SUM(G.gap) FROM ConsecutiveSiblingGaps AS G INNER JOIN Paths AS P ON P.head = @node AND P.tail = Tree.value AND P.node = G.rgtChild), 0) - COALESCE((SELECT SUM(G.gap) FROM ParentOldestChildGaps AS G INNER JOIN Paths AS P ON P.head = @node AND P.tail = Tree.value AND P.node = G.child), 0), rgt = Tree.rgt - COALESCE((SELECT SUM(G.gap) FROM ConsecutiveSiblingGaps AS G INNER JOIN Paths AS P ON P.head = @node AND P.tail = Tree.value AND P.node = G.rgtChild), 0) - COALESCE((SELECT SUM(G.gap) FROM ParentOldestChildGaps AS G INNER JOIN Paths AS P ON P.head = @node AND P.tail = Tree.value AND P.node = G.child), 0) WHERE EXISTS (SELECT * FROM ConsecutiveSiblingGaps AS G INNER JOIN Paths AS P ON P.head = @node AND P.tail = Tree.value AND P.node = G.rgtChild) OR EXISTS (SELECT * FROM ParentOldestChildGaps AS G INNER JOIN Paths AS P ON P.head = @node AND P.tail = Tree.value AND P.node = 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 - 11:33:06 CDT