Re: Nested Sets and Delete/Exchange?

From: --CELKO-- <joe.celko_at_northface.edu>
Date: 23 Sep 2003 16:16:44 -0700
Message-ID: <a264e7ea.0309231516.1a619ac6_at_posting.google.com>

>> 1. How to renumber the values for left and right after the deletion
of an
element? <<

That depends on your business rules for replacing an employee. Let's just promote the subordinates to their former boss's boss:

CREATE VIEW LftRgt (i)
AS SELECT lft FROM OrgChart

   UNION ALL
   SELECT rgt FROM OrgChart;

UPDATE OrgChart

   SET lft = (SELECT COUNT(i)

                FROM LftRgt
               WHERE i <= lft,
       rgt = (SELECT COUNT(i)
                FROM LftRgt
               WHERE i <= rgt;

>> 2. How to exchange two elements and their subtrees? <<

The following solution for swapping the positions of two siblings under the same parent node is due to Mr. Vanderghast and originally appeared in a posting on the MS-SQL Server Newsgroup.

If the leftmost sibling has its (lft, rgt) = (i0, i1) and the other subtree, the rightmost sibling, has (i2, i3), implicitly, we know that (i0 < i1 < i2 < i3).

With a little algebra, we can figure out that if (i) is a lft or rgt value in the table between i0 and i3, then

1. If (i BETWEEN i0 AND i1) then (i) should be updated to (i + i3- i1).
2. If (i BETWEEN i2 AND i3 then (i) should be updated to (i + i0 - i2).
3. If (i BETWEEN i1+1 AND i2-1) then (i) should be updated to (i0 + i3 + i - i2 -i1).

All of this becomes a single update statement, but we will put the (lft, rgt) pairs of the two siblings into local variables so a human being can read the code.

CREATE PROCEDURE SwapSiblings

       (IN lft_sibling CHAR(2), IN rgt_sibling CHAR(2)) LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC

DECLARE i0 INTEGER;
DECLARE i1 INTEGER;
DECLARE i2 INTEGER;
DECLARE i3 INTEGER;
SET i0 = (SELECT lft FROM Tree WHERE node = lft_sibling);
SET i1 = (SELECT rgt FROM Tree WHERE node = lft_sibling);

SET i2 = (SELECT lft FROM Tree WHERE node = rgt_sibling); SET i3 = (SELECT rgt FROM Tree WHERE node = rgt_sibling);

UPDATE Tree

   SET lft = CASE WHEN lft BETWEEN i0 AND i1

                  THEN i3 + lft - i1
                  WHEN lft BETWEEN i2 AND i3
                  THEN i0 + lft - i2
                  ELSE i0 + i3 + lft - i1 - i2 END, 
       rgt = CASE WHEN rgt BETWEEN i0 AND i1
                  THEN i3 + rgt - i1
                  WHEN rgt BETWEEN i2 AND i3
                  THEN i0 + rgt - i2
                  ELSE i0 + i3 + rgt - i1 - i2 END

 WHERE lft BETWEEN i0 AND i3

   AND i0 < i1
   AND i1 < i2
   AND i2 < i3;

END; Received on Wed Sep 24 2003 - 01:16:44 CEST