Moving Subtrees - Nested Sets for Hierarchical MySQL 1

[evostrata]

Hi,

<b>Overview</b>

I am using the Nested Set Method to store hierarchical data in MySQL. The principle is that you can store each record with a left and right value, and all the subordinates of that node will have left and right values between those two values.

http://www.vbmysql.com/articles/database-design/managing-hierarchical-data-in-mysql/

http://www.sitepoint.com/article/hierarchical-data-database

Here is an example of a table I have with the title of each record and their left and right values either side of them.

(1)Animals(24)
-(2)Pets(9)
--(3)Dogs(8)
---(4)Alsatian(5)
---(6)Labrador(7)
-(10)Farm(23)
--(11)Pigs(14)
---(12)Pink(13)
--(15)Cats(22)
---(16)Tabby(17)
---(18)Tortoise Shell(19)
---(20)Black(21)

Anyway, say I notice that Cats is in the wrong category – instead of being under Farm it should be under Pet.

That would mean I would want my database to become

(1)Animals(24)
-(2)Pets(17)
--(3)Cats(10)
---(4)Tabby(5)
---(6)Tortoise Shell(7)
---(8)Black(9)
--(11)Dogs(16)
---(12Alsatian(13)
---(14)Labrador(15)
-(18)Farm(23)
--(19)Pigs(20)
---(21)Pink(22)

<b>Problem</b>

The problem is, I am having trouble working out the sort of queries I would perform.


To do this I:

1) Set the left value as the new parent (Pets) left value plus 1, and set the right value as this plus the width of the subtree (eg. 3+7).

2) Subtracting the change in the right value and left value (eg. left WAS 15 NOW 3) from all pages where the left value is between the OLD left and right of the subtree (eg. all the pages under the node Cats that I want to move (so Tabby, Tortoise Shell, Black).

I am happy with the above steps, but this is where I feel my problem is:-

3) For all pages with a left value greater than the OLD left value of the subtree, subtracting the change amount (from step 2) from their left.

4) For all pages with a right value greater than that of the old subtree’s left, but NOT with a left value greater than the subtree’s old left value, subtracting the change amount from their right value.

Obviously I wanted this to work whichever subtree I move around, eg. the whole of pets to under farm, or Dogs under Pigs>Pink.

I have spent such a long time thinking about this and getting nowhere so it would be great if anyone could provide a different view on the matter!

Thanks!

 

[hvass]

I think you just need to treat it as a series of steps first you prune cats out then you add them back in

step 1 - decide what you want to cut in this case cats=15-22
step 2 - cut cats : this means set status of cats to 0 and give then lt and rt of a pruned tree
step 3 - take (22-15+1)=8 off the left & right values of everything with a value >end of cats
step 4 - decide where you want to insert in your case you want after the beginning of pets 2
step 5 - for all records before the insert point add 8 to all rt
step 6 - for all records after the insert point add 8 to all lt and rt
step 7 - insert the cats at 2

Now all you need to do is see if you can collapse this into fewer steps

drop table if exists test.catsanddogs;
create table test.catsanddogs
	(
	lt tinyint(3) unsigned not null,
	name char(20),
	rt tinyint(3) unsigned not null,
	status tinyint(1) unsigned not null
	);

insert into test.catsanddogs
	values
(1,"Animals",24,1),
(2,"Pets",9,1),
(3,"Dogs",8,1),
(4,"Alsatian",5,1),
(6,"Labrador",7,1),
(10,"Farm",23,1),
(11,"Pigs",14,1),
(12,"Pink",13,1),
(15,"Cats",22,1),
(16,"Tabby",17,1),
(18,"Tortoise",19,1),
(20,"Black",21,1);

update test.catsanddogs
	set lt:=lt+@insert,
		rt:=rt+@insert,
		status=1
where status=0;

select 
	node.lt,
	concat( repeat('-', count(parent.name) - 1), node.name) as name,
	node.rt,
	node.status
from test.catsanddogs as node,  test.catsanddogs as parent
where node.lt between parent.lt and parent.rt
group by node.name
order by node.lt;


##step 1 
select 
	@cutfrom:=lt, 
	@cutto:=rt,
	@cut:=rt-lt+1
from test.catsanddogs
where name='cats';

##step 2 
update test.catsanddogs
	set status=0,
	       lt:=lt-@cutfrom+1,
	       rt:=rt-@cutfrom+1
where lt between @cutfrom and @cutto;

##step 3
update test.catsanddogs
	set lt:=lt-@cut
where lt >=@cutfrom and status=1;
update test.catsanddogs
	set rt:=rt-@cut
where rt>=@cutto and status=1;

##step 4 
select
	@insert:=lt
from test.catsanddogs
where name='pets';

##step 5 
update test.catsanddogs
	set rt:=rt+@cut
where lt<=@insert and status=1;

##step 6
update test.catsanddogs
	set lt:=lt+@cut,
		rt:=rt+@cut
where lt>@insert and status=1;

##step 7
update test.catsanddogs
	set lt:=lt+@insert,
		rt:=rt+@insert,
		status=1
where status=0;

select 
	node.lt,
	concat( repeat('-', count(parent.name) - 1), node.name) as name,
	node.rt,
	node.status
from test.catsanddogs as node,  test.catsanddogs as parent
where node.lt between parent.lt and parent.rt
group by node.name
order by node.lt;