Move node in nested set

Question

I'd need a MySQL query that moves a node and all its 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 is 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 its ID.

Answer 1

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 and 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_pos_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_pos_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 2

Here is a solution that lets you move a node to any position in the tree, either as a sibling or a child with just a single input parameter - the new left position (newlpos) of the node.

Fundamentally there are three steps:

• Create new space for the subtree.
• Move the subtree into this space.
• Remove the old space vacated by the subtree.

In psuedo-sql, it looks like this:

//
 *  -- create new space for subtree
 *  UPDATE tags SET lpos = lpos + :width WHERE lpos >= :newlpos
 *  UPDATE tags SET rpos = rpos + :width WHERE rpos >= :newlpos
 * 
 *  -- move subtree into new space
 *  UPDATE tags SET lpos = lpos + :distance, rpos = rpos + :distance
 *           WHERE lpos >= :tmppos AND rpos < :tmppos + :width
 * 
 *  -- remove old space vacated by subtree
 *  UPDATE tags SET lpos = lpos - :width WHERE lpos > :oldrpos
 *  UPDATE tags SET rpos = rpos - :width WHERE rpos > :oldrpos
 */

The :distance variable is the distance between the new and old positions, the :width is the size of the subtree, and :tmppos is used to keep track of the subtree being moved during the updates. These variables are defined as:

// calculate position adjustment variables
int width = node.getRpos() - node.getLpos() + 1;
int distance = newlpos - node.getLpos();
int tmppos = node.getLpos();
        
// backwards movement must account for new space
if (distance < 0) {
    distance -= width;
    tmppos += width;
}

For a complete code example, see my blog at

https://rogerkeays.com/how-to-move-a-node-in-nested-sets-with-sql

If you like this solution, please up-vote.

Answer 3

I know this is an old question, but I've just used the answer myself but for SQL Server. Should anyone want it, here is the code for a SQL Server Stored Proc based on the accepted answer.

CREATE PROCEDURE [dbo].[Item_Move] 
    @id uniqueidentifier, 
    @destinationId uniqueidentifier
AS
BEGIN

    SET NOCOUNT ON;

    declare @moverLeft int,
            @moverRight int,
            @destinationRight int,
            @node_size int

    -- step 0: Initialize parameters.
    SELECT 
        @moverLeft = leftExtent, 
        @moverRight = rightExtent 
    FROM 
        Item 
    WHERE 
        id = @id

    SELECT 
        @destinationRight = rightExtent 
    FROM 
        Item 
    WHERE 
        id = @destinationId

    SELECT
        @node_size = @moverRight - @moverLeft + 1; -- 'size' of moving node (including all it's sub nodes)

    -- step 1: temporary "remove" moving node
    UPDATE Item
    SET leftExtent = 0-(leftExtent), rightExtent = 0-(rightExtent), updatedDate = GETDATE()
    WHERE leftExtent >= @moverLeft AND rightExtent <= @moverRight;

    -- step 2: decrease left and/or right position values of currently 'lower' items (and parents)
    UPDATE Item
    SET leftExtent = leftExtent - @node_size, updatedDate = GETDATE()
    WHERE leftExtent > @moverRight;
    UPDATE Item
    SET rightExtent = rightExtent - @node_size, updatedDate = GETDATE()
    WHERE rightExtent > @moverRight;

    -- step 3: increase left and/or right position values of future 'lower' items (and parents)
    UPDATE Item
    SET leftExtent = leftExtent + @node_size, updatedDate = GETDATE()
    WHERE leftExtent >= CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @node_size ELSE @destinationRight END;
    UPDATE Item
    SET rightExtent = rightExtent + @node_size, updatedDate = GETDATE()
    WHERE rightExtent >= CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @node_size ELSE @destinationRight END;

    -- step 4: move node (and it's subnodes) and update it's parent item id
    UPDATE Item
    SET
        leftExtent = 0-(leftExtent) + CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @moverRight - 1 ELSE @destinationRight - @moverRight - 1 + @node_size END,
        rightExtent = 0-(rightExtent) + CASE WHEN @destinationRight > @moverRight THEN @destinationRight - @moverRight - 1 ELSE @destinationRight - @moverRight - 1 + @node_size END, 
        updatedDate = GETDATE()
    WHERE leftExtent <= 0-@moverLeft AND rightExtent >= 0-@moverRight;
    UPDATE Item
    SET parentId = @destinationId, updatedDate = GETDATE()
    WHERE id = @id;


END