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

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

http://www.ninthavenue.com.au/how-to-move-a-node-in-nested-sets-with-sql

If you like this solution, please up-vote.

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 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 4

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 5

$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"]);

Answer 6

Thanks for the idea of transforming the lft and rgt to their negative counterparts. I posted a more general approach for this here: Move node in Nested Sets tree.

The queryBatch() function encloses the query in a transaction.