MySQL: Move node in nested set

Question

I'd need a MySQL query that moves a node and all it's children within a nested set. I found this site, but that function just seems so illogical - there's no universeid or treeid in a nested set model, and the code itself it just longer than what feels required. The only extra column I've got in the table is "parent".

I couldn't just remove and add the node again since it will loose it's ID.

Thank you in advance.

Answer 1

Moving subtrees around is very expensive and complex in the Nested Sets design.

You should consider a different design for representing trees.

For example, if you use the Path Enumeration design, you store the list of direct ancestors of each node as a concatenated string.

id path
 1  1/
 2  1/2/
 3  1/3/
 4  1/3/4/
 5  1/3/5/

Then moving a subtree (say node 3 moves to be a child of node 2):

UPDATE Tree t
 JOIN Tree node2 ON (node2.id = 2)
 JOIN Tree node3 ON (node3.id = 3)
SET t.path = CONCAT(node2.path, REPLACE(t.path, node3.path, node2.path))
WHERE t.path LIKE CONCAT(node3.path, '%');

Answer 2

See the article in my blog for storing and using hierarchical data in MySQL:

• Hierarchical queries in MySQL

To move a whole branch in such a table, you'll just need to update the root's parent (a single row)

You'll need to create a function:

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

        SET _parent = @id;
        SET _id = -1;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

        LOOP
                SELECT  MIN(id)
                INTO    @id
                FROM    t_hierarchy
                WHERE   parent = _parent
                        AND id > _id;
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, parent
                INTO    _id, _parent
                FROM    t_hierarchy
                WHERE   id = _parent;
        END LOOP;
END

and use it in a query:

SELECT  CONCAT(REPEAT('    ', level - 1), CAST(hi.id AS CHAR)) AS treeitem, parent, level
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
        FROM    (
                SELECT  @start_with := 0,
                        @id := @start_with,
                        @level := 0
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    t_hierarchy hi
ON      hi.id = ho.id

Answer 3

I have a stored procedure that moves a node in a nested set to a new parent node. I am using a table called "category" in a MySQL / InnoDB database called "somedb". Of course, if the destination is a subcategory of the category you want to move this procedure will screw things up, so make sure that you aren't trying to embed a node inside of itself. I will leave it as an exercise to the reader to make this procedure safe for that case.

CREATE PROCEDURE `somedb`.`moveCatParent` (IN cat_a VARCHAR(45), IN cat_b VARCHAR(45))
BEGIN
    START TRANSACTION;

    /* cat_b.lft + 1 is the destination. */
    SELECT @destination := (lft + 1)
    FROM category
    WHERE name = cat_b;

    SELECT @cat_a_width := ((rgt - lft) + 1)
    FROM category
    WHERE name = cat_a;

    /* Rip this table a new cat_a sized hole inside cat_b. */  
    UPDATE category SET rgt = rgt + @cat_a_width WHERE rgt >= @destination;
    UPDATE category SET lft = lft + @cat_a_width WHERE lft >= @destination;

    SELECT @cat_a_lft := lft, @cat_a_rgt := rgt
    FROM category
    WHERE name = cat_a;

    SELECT @diff := @destination - @cat_a_lft;

    /* Move cat_a and all inhabitants to new hole */  
    UPDATE category SET rgt = rgt + @diff WHERE rgt BETWEEN @cat_a_lft AND @cat_a_rgt;
    UPDATE category SET lft = lft + @diff WHERE lft BETWEEN @cat_a_lft AND @cat_a_rgt;

    /* Close the gap created when we moved cat_a. */
    UPDATE category SET rgt = rgt - @cat_a_width WHERE rgt >= @cat_a_lft;
    UPDATE category SET lft = lft - @cat_a_width WHERE lft >= @cat_a_lft;

    COMMIT;
END

Answer 4

I see, that this topic is quite old, but anyway it's still unanswered. I got here from Google, and found no direct answer to this question.

So, after a little research I found quite easy solution.

Everything, what we gonna need to move our node is: node left and right positions, new parent node right position. The node to the new position then can be moved in four easy steps:

1. Change positions of node ant all it's sub nodes into negative values, which are equal to current ones by module.
2. Move all positions "up", which are more, that pos_right of current node.
3. Move all positions "down", which are more, that pos_right of new parent node.
4. Change positions of current node and all it's subnodes, so that it's now will be exactly "after" (or "down") of new parent node.

That's theory, now - this algorithm realization in MySQL (example using PHP):

# step 0: Initialize parameters.
SELECT
    @node_id := 1, #put there id of moving node 
    @node_pos_left := 0, #put there left position of moving node
    @node_pos_right := 1, #put there right position of moving node
    @parent_id := 2, #put there id of new parent node (there moving node should be moved)

    @parent_pos_right := 4; #put there right position of new parent node (there moving node should be moved)
SELECT
    @node_size := @node_pos_right - @node_pos_left + 1; # 'size' of moving node (including all it's sub nodes)

# step 1: temporary "remove" moving node

UPDATE `list_items`
SET `pos_left` = 0-(`pos_left`), `pos_right` = 0-(`pos_right`)
WHERE `pos_left` >= @node_pos_left AND `pos_right` <= @node_pos_right;

# step 2: decrease left and/or right position values of currently 'lower' items (and parents)

UPDATE `list_items`
SET `pos_left` = `pos_left` - @node_size
WHERE `pos_left` > @node_pos_right;
UPDATE `list_items`
SET `pos_right` = `pos_right` - @node_size
WHERE `pos_right` > @node_pos_right;

# step 3: increase left and/or right position values of future 'lower' items (and parents)

UPDATE `list_items`
SET `pos_left` = `pos_left` + @node_size
WHERE `pos_left` >= IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_size, @parent_pos_right);
UPDATE `list_items`
SET `pos_right` = `pos_right` + @node_size
WHERE `pos_right` >= IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_size, @parent_pos_right);

# step 4: move node (ant it's subnodes) and update it's parent item id

UPDATE `list_items`
SET
    `pos_left` = 0-(`pos_left`)+IF(@parent_pos_right > @node_pos_right, @parent_node_right - @node_pos_right - 1, @parent_pos_right - @node_pos_right - 1 + @node_size),
    `pos_right` = 0-(`pos_right`)+IF(@parent_pos_right > @node_pos_right, @parent_node_right - @node_pos_right - 1, @parent_pos_right - @node_pos_right - 1 + @node_size)
WHERE `pos_left` <= 0-@node_pos_left AND `pos_right` >= 0-@node_pos_right;
UPDATE `list_items`
SET `parent_item_id` = @parent_id
WHERE `item_id` = @node_id;

Please beware - there still may be some syntax errors in SQL code, because I actually use this algorithm in PHP like this:

$iItemId = 1;
$iItemPosLeft = 0;
$iItemPosRight = 1;
$iParentId = 2;
$iParentPosRight = 4;
$iSize = $iPosRight - $iPosLeft + 1;
$sql = array(

    // step 1: temporary "remove" moving node

    'UPDATE `list_items`
    SET `pos_left` = 0-(`pos_left`), `pos_right` = 0-(`pos_right`)
    WHERE `pos_left` >= "'.$iItemPosLeft.'" AND `pos_right` <= "'.$iItemPosRight.'"',

    // step 2: decrease left and/or right position values of currently 'lower' items (and parents)

    'UPDATE `list_items`
    SET `pos_left` = `pos_left` - '.$iSize.'
    WHERE `pos_left` > "'.$iItemPosRight.'"',
    'UPDATE `list_items`
    SET `pos_right` = `pos_right` - '.$iSize.'
    WHERE `pos_right` > "'.$iItemPosRight.'"',

    // step 3: increase left and/or right position values of future 'lower' items (and parents)

    'UPDATE `list_items`
    SET `pos_left` = `pos_left` + '.$iSize.'
    WHERE `pos_left` >= "'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iSize : $iParentPosRight).'"',
    'UPDATE `list_items`
    SET `pos_right` = `pos_right` + '.$iSize.'
    WHERE `pos_right` >= "'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iSize : $iParentPosRight).'"',

    // step 4: move node (ant it's subnodes) and update it's parent item id

    'UPDATE `list_items`
    SET
        `pos_left` = 0-(`pos_left`)+'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iItemPosRight - 1 : $iParentPosRight - $iItemPosRight - 1 + $iSize).',
        `pos_right` = 0-(`pos_right`)+'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iItemPosRight - 1 : $iParentPosRight - $iItemPosRight - 1 + $iSize).'
    WHERE `pos_left` <= "'.(0-$iItemPosLeft).'" AND i.`pos_right` >= "'.(0-$iItemPosRight).'"',
    'UPDATE `list_items`
    SET `parent_item_id` = "'.$iParentItemId.'"
    WHERE `item_id`="'.$iItemId.'"'
);
foreach($sql as $sqlQuery){
    mysql_query($sqlQuery);
}

Please note also, that code may be optimized, but I going to leave it like that for better readability. Also consider table locking if you are using nested sets in multi-user systems.

Hope that my message will help to anyone, who will search for a solution after me. Any comments and corrections are also welcome.

Answer 5

http://stackoverflow.com/questions/889527/mysql-move-node-in-nested-set/1274175#1274175

Hi Arturas! You code is excelent! Nevertheless, It have un little bug in step 1, you haven't AND in conditions sql "WHERE pos_left >= @node_pos_left AND pos_right <= @node_pos_right; "

Answer 6

I believe that with two extra columns to store the original Node right and left values (and all subsequent subnodes) the algorithm can be simplified. I have worked the examples with pencil and paper so if you find any holes in the algorithm please let me know.

The target Node (The new parent of Node that you are moving) is tNode. Left value of Target Node is tNode.L and right value is tNode.R. Similarly the node you are moving is mNode and left and right values for mNode are mNode.L and mNode.R. The two extra columns are mNode.SL and mNode.SR

So all in all we have 4 columns for manipulation R,L, SL and SR

---

Step1

calculate

delta1 = (mNode.R - mNode.L) + 1

Step2

Save the mNode original L and R into SL and SR columns

- For All L between mNode.L and mNode.R 
   mNode.SL = mNode.L ; mNode.L = 0 ;
 - For All R between mNode.L and mNode.R 
   mNode.SR = mNode.R ; mNode.R = 0 ;

Step3

Do For all Nodes
IF L > mNode.SR 
   L = L + delta1
IF R > mNode.SR
   R = R + delta1

Now the mNode is detached from Tree and Tree is adjusted without mNode.

Step4

calculate

delta2 = (tNode.R - mNode.SL)

Step5

Do for all Nodes
  IF L >= tNode.R
    L = L + delta1
  IF R >= tNode.R
    R = R + delta1

Now we have adjusted the Tree (and target node) to accept the number of nodes that were deleted.

Step6

Attach mNode at tNode and reset SL/SR column values

Do for all Nodes
 IF SL between mNode.SL and mNode.SR
    L = mNode.SL + delta2 ; mNode.SL = 0  ;
 IF SR between mNode.SL and mNode.SR
    R = mNode.SR + delta2 ; mNode.SR = 0 ;

After all these steps we should have moved mNode under the tNode.

Answer 7

Hi,

$row is an array that represents the row I have to move; it must be like this:

Array ( [lft] => 5 [rgt] => 10 [width] => 6 )

$row2 is an array that represents the destiny node;

Array ( [id] => 5 [lft] => 2 [rgt] => 17 [width] => 16 )

...

mysql_query("UPDATE entryCategory SET rgt = rgt + %d - %d, lft = lft + %d - %d WHERE rgt <= %d and lft >= %d;",$row2["rgt"],$row["lft"],$row2["rgt"],$row["lft"],$row["rgt"],$row["lft"]);
mysql_query("UPDATE entryCategory SET rgt = rgt + %d WHERE id=%d;",$row["width"],$row2["id"]);
mysql_query("UPDATE entryCategory SET rgt = rgt - %d, lft = lft - %d  WHERE rgt > %d and lft > %d;",$row["width"],$row["width"],$row["rgt"],$row["rgt"]);