Move Nested Set Node

[Kalon]

Hi,

I am using the Nested Set Model to manage categories for an online store.

I have got sql queries to display/add/delete category nodes and their children and they work fine.

What I need now is some help to write the sql to move a node and its children to a new parent node.

I am trying to avoid deleting the node and then inserting it under the new parent because that would involve storing the node temporarily somewhere first.

Can anybody please point me in the right direction with any links to where this has already been done.

In this case, google hasn't been too friendly or maybe I'm not using the right keywords.

If it's any help, this is my category table structure.

 
Field
------
fldCatId
fldCatName
fldLft
fldRgt

Any help will be much appreciated.

[SpacePhoenix]

I'm not sure that you can do it with one query, if it can't be done with a single query, I think this is one case where transactions may well be a must to prevent corruption of the tree if anything goes wrong when moving a branch of a tree to another branch.

[Kalon]

I'm sure it will involve more than 1 query.

To add or delete nodes takes more than 1 query for each function.

For example - to add a node called LCD below the TELEVISIONS node I am using this:

SELECT @myRight := fldRgt FROM tblcategory
WHERE fldCatName = 'TELEVISIONS';
UPDATE tblcategory SET fldRgt = fldRgt + 2 WHERE fldRgt >= @myRight;
UPDATE tblcategory SET fldLft = fldLft + 2 WHERE fldLft >= @myRight;
INSERT INTO tblcategory(fldCatName, fldLft, fldRgt) VALUES('LCD', @myRight, @myRight + 1);

[Kalon]

I feel like I have been re-inventing the wheel to some extent but I've had to because I couldn't find any sql code (for free at least) to move nodes.

I have been using this very good tutorial as a base to blend its code to add and delete nodes into a single block of code to move a node as a sibling to another node (I have changed the table and column names to suit my test database).

The code below assumes fldCatId is a primary key integer.

I had to use a temporary table to store and reset the lefts and rights of the sub tree to move before putting them back into the main table. There probably is a way of doing it without a temporary table but unfortunately it's beyond the processing capacity of the cpu inside my head atm

The next step is to write code to move a subtree as a child to another node.

This code moves the 'mp3 players' node and its children (in the above tutorial) next to the 'plasma' node.

 
/* Move Node as sibling of target node */
 
/* get the parameters for the sub tree to move */
SELECT @myLeft := fldLft, @myRight := fldRgt, @myWidth := fldRgt - fldLft + 1, @catId := fldCatID
FROM tblcategory
WHERE fldCatID = '7';
 
/* get the fldRgt value of the node to move next to */
SELECT @insRgt := fldRgt FROM tblcategory WHERE fldCatName = 'plasma';
 
/* get the offset to renumber the subtree lefts and rights */
SELECT @step := @insRgt - @myLeft + 1;
 
/* transfer the subtree to a temp table */
INSERT tblcattemp
SELECT * FROM tblcategory
WHERE fldLft >= @myLeft AND fldLft <= @myRight;
 
/* update the temp table - renumber the lefts and rights and make the catId neg temporarily */
UPDATE tblcattemp
SET fldLft = fldLft + @step, 
fldRgt = fldRgt + @step,
fldCatID = -fldCatID;
 
/* update the rest of the tree to the right of the move point*/
UPDATE tblcategory SET fldLft = fldLft + @myWidth WHERE fldLft > @insRgt;
UPDATE tblcategory SET fldRgt = fldRgt + @myWidth WHERE fldRgt > @insRgt;
 
/* bring the sub tree in the temp table back to the main table */
INSERT tblcategory
SELECT * FROM tblcattemp;
 
/* delete the original subtree */
SELECT @myLeft := fldLft, @myRight := fldRgt, @myWidth := fldRgt - fldLft + 1
FROM tblcategory
WHERE fldCatID = @catId;
DELETE FROM tblcategory WHERE fldLft BETWEEN @myLeft AND @myRight; 
UPDATE tblcategory SET fldRgt = fldRgt - @myWidth WHERE fldRgt > @myRight;
UPDATE tblcategory SET fldLft = fldLft - @myWidth WHERE fldLft > @myRight;
 
/* reset neg. catId's to pos. and clean up tblcattemp*/
UPDATE tblcategory SET fldCatID = -fldCatID WHERE fldCatID < 0;
DELETE FROM tblcattemp;

[Kalon]

Using the test data from the tutorial link I posted earlier, this code will move a node and its children to a leaf node as a new child of that leaf.

/* Move Node to child of target node */
 
/* get the parameters for the sub tree to move */
SELECT @myLeft := fldLft, @myRight := fldRgt, @myWidth := fldRgt - fldLft + 1, @catId := fldCatID
FROM tblcategory
WHERE fldCatID = '7';
 
/* get the fldLft and fldRgt value of the new parent cat */
SELECT @insLft := fldLft, @insRgt := fldRgt FROM tblcategory WHERE fldCatID = '4';
 
/* get the offset to renumber the subtree lefts and rights */
SELECT @step := @insLft - @myLeft + 1;
 
/* transfer the subtree to a temp table */
INSERT tblcattemp
SELECT * FROM tblcategory
WHERE fldLft >= @myLeft AND fldLft <= @myRight;
 
/* update the temp table - renumber the lefts and rights and make the catId neg temporarily */
UPDATE tblcattemp
SET fldLft = fldLft + @step, 
fldRgt = fldRgt + @step,
fldCatID = -fldCatID;
 
/* update the rest of the tree to the right of the move point*/
UPDATE tblcategory SET fldLft = fldLft + @myWidth WHERE fldLft >= @insRgt;
UPDATE tblcategory SET fldRgt = fldRgt + @myWidth WHERE fldRgt >= @insRgt;
 
/* insert the sub tree in the temp table */
INSERT tblcategory
SELECT * FROM tblcattemp;
 
/* delete the original subtree */
SELECT @myLeft := fldLft, @myRight := fldRgt, @myWidth := fldRgt - fldLft + 1
FROM tblcategory
WHERE fldCatID = @catId;
DELETE FROM tblcategory WHERE fldLft BETWEEN @myLeft AND @myRight; 
UPDATE tblcategory SET fldRgt = fldRgt - @myWidth WHERE fldRgt > @myRight;
UPDATE tblcategory SET fldLft = fldLft - @myWidth WHERE fldLft > @myRight;
 
/* reset neg. catId's to pos. and clean up tblcattemp*/
UPDATE tblcategory SET fldCatID = -fldCatID WHERE fldCatID < 0;
DELETE FROM tblcattemp;

[firblazer]

Hi!

I have used your SQL code and try to move zmei.html from the docs directory into the demo directory. But it says: Out of range value for 'id' at row 1.

What I did was to change the new fldCatID from 4 to 3 in your second line of SQL statements.

I see @step := @insLft - @mylft + 1 is -4

Can you help? Thanks.

[Kalon]

The code I posted simply manipulates records in a database for a nested set model.

it doesn't move files physically from one folder to another.

[firblazer]

Hi Kalon,

Yes, I was using the nested set database model in the tutorial that you posted.

I was trying to move the file/folder record in the database. Why am I getting a -4?

Please help. Thanks.

[Kalon]

without seeing your code I can't tell what you have done.

post your code, table structure and a description of how your zmei.html file is related to your code.

[firblazer]

Hi! Thanks for your reply. Sorry I was using another table which also has left and right using the nested set database.

Here's the table and the code.

CREATE TABLE IF NOT EXISTS `mediatree` (
  `id` BIGINT(20) NOT NULL AUTO_INCREMENT,
  `parent_id` BIGINT(20) NOT NULL,
  `position` BIGINT(20) NOT NULL,
  `lft` BIGINT(20) NOT NULL,
  `rgt` BIGINT(20) NOT NULL,
  `level` BIGINT(20) NOT NULL,
  `title` text CHARACTER SET utf8 COLLATE utf8_unicode_ci,
  `type` VARCHAR(255) CHARACTER SET utf8 COLLATE utf8_unicode_ci DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=13 DEFAULT CHARSET=utf8;
 
NSERT INTO `mediatree` (`id`, `parent_id`, `position`, `lft`, `rgt`, `level`, `title`, `type`) VALUES
	(1, 0, 2, 1, 14, 0, 'ROOT', ''),
	(2, 1, 0, 2, 11, 1, 'C:', 'drive'),
	(3, 2, 0, 3, 6, 2, '_demo', 'folder'),
	(4, 3, 0, 4, 5, 3, 'index.html', 'default'),
	(5, 2, 1, 7, 10, 2, '_docs', 'folder'),
	(6, 1, 1, 12, 13, 1, 'D:', 'drive'),
	(7, 5, 0, 8, 9, 3, 'zmei.html', 'default');

/* Move Node to child of target node */
 
/* get the parameters for the sub tree to move */
SELECT @mylft := lft, @myrgt := rgt, @myWidth := rgt - lft + 1, @catId := id
FROM mediatree
WHERE id = '7';
 
/* get the lft and rgt value of the new parent cat */
SELECT @insLft := lft, @insRgt := rgt FROM mediatree WHERE id = '3';
 
/* get the offset to renumber the subtree lfts and rgts */
SELECT @step := @insLft - @mylft + 1;
 
/* transfer the subtree to a temp table */
INSERT tblcattemp
SELECT * FROM mediatree
WHERE lft >= @mylft AND lft <= @myrgt;
 
/* update the temp table - renumber the lfts and rgts and make the catId neg temporarily */
UPDATE tblcattemp
SET lft = lft + @step,
rgt = rgt + @step,
id = -id;
 
/* update the rest of the tree to the rgt of the move point*/
UPDATE mediatree SET lft = lft + @myWidth WHERE lft >= @insRgt;
UPDATE mediatree SET rgt = rgt + @myWidth WHERE rgt >= @insRgt;
 
/* insert the sub tree in the temp table */
INSERT mediatree
SELECT * FROM tblcattemp;
 
/* delete the original subtree */
SELECT @mylft := lft, @myrgt := rgt, @myWidth := rgt - lft + 1
FROM mediatree
WHERE id = @catId;
DELETE FROM mediatree WHERE lft BETWEEN @mylft AND @myrgt;
UPDATE mediatree SET rgt = rgt - @myWidth WHERE rgt > @myrgt;
UPDATE mediatree SET lft = lft - @myWidth WHERE lft > @myrgt;
 
/* reset neg. catId's to pos. and clean up tblcattemp*/
UPDATE mediatree SET id = -id WHERE id < 0;
DELETE FROM tblcattemp;

tblcattemp is another empty table with the same structure as mediatree.

[Kalon]

The good news

I ran your scripts and recreated your table and data without problems and your lft and rgt values appear to be set correctly and what you are trying to move makes sense now.

I'm now looking into it - back soon.

[firblazer]

Strangly, I ran your script on the table provided by the tutorial. I was trying to move tube into portable electronics. It gives:

category_id, name, lft, rgt
1, electronics, 1, 20
2, televisions, 2, 7
3, tube, 9, 10
4, lcd, 3, 4
5, plasma, 5, 6
6, portable electronics, 8, 19
7, mp3, 9, 12
8, flash, 10, 11
9, cd players, 13, 14
10, 2 way radios, 15, 16

17 and 18 are missing

[Kalon]

ok, we have lift off

1) the script you were using moves a node as a child to a leaf node which is not what you want in this case because _demo already has a child (index.html) and so it is not a leaf node.

2) what you want in this case is for zmie.htm to be a child of _demo just like index.html is. In other words you want zmie.htm to be a sibling of index.html.

3) therefore you have to use my other posted script.

below is my posted script that moves 'mp3 players' next to 'plasma' but edited to suit your table structure.

also, make sure tblcattemp (which you can rename to whatever you like) has exactly the same structure as mediatree table. you can srun your mediatree creation script and just change the table name

 
/*  Move Node to sibling of target node  */
/* get the parameters for the sub tree to move */
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1, @catId := id
FROM mediatree
WHERE id = '7';
 
/* get the rgt value of the node to move next to */
SELECT @insRgt := rgt  FROM mediatree WHERE id = '4';
 
/* get the offset to renumber the subtree lefts and rights */
SELECT @step := @insRgt - @myLeft + 1;
 
/* transfer the subtree to a temp table */
INSERT tblcattemp
SELECT * FROM mediatree
WHERE lft >= @myLeft AND lft <= @myRight;
 
/* update the temp table - renumber the lefts and rights and make the catId neg temporarily */
UPDATE tblcattemp
SET lft = lft + @step, 
rgt = rgt + @step,
id = -id;
 
/* update the rest of the tree to the right of the move point*/
UPDATE mediatree SET lft = lft + @myWidth WHERE lft > @insRgt;
UPDATE mediatree SET rgt = rgt + @myWidth WHERE rgt > @insRgt;
 
/* insert the sub tree in the temp table */
INSERT mediatree
SELECT * FROM tblcattemp;
 
/*  delete the original subtree */
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM mediatree
WHERE id = @catId;
DELETE FROM mediatree WHERE lft BETWEEN @myLeft AND @myRight; 
UPDATE mediatree SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE mediatree SET lft = lft - @myWidth WHERE lft > @myRight;
 
/* reset neg. catId's to pos. and clean up tblcattemp*/
UPDATE mediatree SET id = -id WHERE id < 0;
DELETE FROM tblcattemp;

now the zmie.html node is a child of _demo and a sibling to index.html

so to use my 2 scripts you first need to decide which type of move you need and then use the appropriate script.

There might be better ways of doing this, but this works for me. if you need more help just post back

[Kalon]

looking at your data model, I think you could be better off if you have one table for all your folders like root, c:, d:, _demo etc etc and another table for all the files in each each folder. each file will have a foreign key linking it to the id of the folder it belongs to in the folder table.

think of it as your folders being categories and the files being the products in each category.

anyway, just my

[Kalon]

something I just noticed different in your table structure.

you have a parent_id column. you will have to update the value for the moved node to the value of its new parent.

that is simple and straight forward, but don't forget to add that to your code.

[Kalon]

Strangly, I ran your script on the table provided by the tutorial. I was trying to move tube into portable electronics. It gives:

category_id, name, lft, rgt
1, electronics, 1, 20
2, televisions, 2, 7
3, tube, 9, 10
4, lcd, 3, 4
5, plasma, 5, 6
6, portable electronics, 8, 19
7, mp3, 9, 12
8, flash, 10, 11
9, cd players, 13, 14
10, 2 way radios, 15, 16

17 and 18 are missing

I have 2 scripts posted and without seeng the code you used I can't tell if you used the right one and if you did what you did wrong.

but a few posts back from here is the appropriate script to solve your initial problem.

[firblazer]

Hi! Thanks for your code. But it is not correct. What I got is:

 
INSERT INTO `mediatree` (`id`, `parent_id`, `position`, `lft`, `rgt`, `level`, `title`, `type`) VALUES
	(1, 0, 2, 1, 14, 0, 'ROOT', ''),
	(2, 1, 0, 2, 11, 1, 'C:', 'drive'),
	(3, 2, 0, 3, 6, 2, '_demo', 'folder'),
	(4, 3, 0, 4, 5, 3, 'index.html', 'default'),
	(5, 2, 1, 9, 10, 2, '_docs', 'folder'),
	(6, 1, 1, 12, 13, 1, 'D:', 'drive'),
	(7, 5, 0, 7, 8, 3, 'zmei.html', 'default');

How come zmei.html is at lft: 7 and rgt: 8? The correct structure should be:

title, lft, rgt
ROOT, 1, 14
C:, 2, 11
_demo, 3, 8
index.html, 4, 5
_docs, 9, 10
D:, 12, 13
zmei.html, 6, 7

if I want to move zmei.html from docs into _demo using the code at post #13

[Kalon]

this is what I get and they are the corrct lft and rgt values if you draw out the structure on a piece of paper

 
id parent_id position lft rgt level title type
1 0 2 1 14 0 ROOT 
2 1 0 2 11 1 C: drive
3 2 0 3 8 2 _demo folder
4 3 0 4 5 3 index.html default
5 2 1 9 10 2 _docs folder
6 1 1 12 13 1 D: drive
7 5 0 6 7 3 zmei.html default

[Kalon]

I think you've moved zmei.html next to docs instead of next to index.htm

you have to make sure you input the correct id for the source and target nodes - the only 2 inputs to the script

[Kalon]

drop your mediatree table and recreate it.

then run the script in post #13

[firblazer]

Hi! Thanks for your reply.

You are right. I have mistaken the second select statement to be the folder I want to move INTO instead of the file that I want to move NEXT to.

Is there a way to specify the folder that I want to INTO since I only get the id of the folder I want to move INTO from the application?

Many thanks.

[Kalon]

pheewww... I'm glad you got it working. I need a

The script that moves a node as child to a node will move that node and all its children "into" the target node only if the target node is a leaf node (has no children).

I haven't written a script to move a node as a child to a target node where the target node has children. but it can be done. it's just a matter of working out the logic to renumber the lft and rgt values accordingly.

so far I haven't a need to do that and that is why I haven;t done it but there might scripts that do that somewhere on the www.

I use the nested set model for my categories table where the type of node is the same (a category). you have mixed node types and that is why I posted earlier

looking at your data model, I think you could be better off if you have one table for all your folders like root, c:, d:, _demo etc etc and another table for all the files in each each folder. each file will have a foreign key linking it to the id of the folder it belongs to in the folder table.

think of it as your folders being categories and the files being the products in each category.

anyway, just my

and that could make your life easier since you have folders and files in your data model

[firblazer]

ok. Many thanks for your advice. I buy you beer someday.

[Kalon]

you're welcome