reorganizing/copying parts of a hierarchical tree

[redbullmarky]

I might be missing something that makes this easier than it seems, but:

 

If I have a DB table of categories, subcategories and items, like this:

 

id
parent_id
type (category or item)
name

 

and maybe a structure like this:

 

- Fruit [id = 1]
--- Apple [id = 2, parent = 1]
--- Orange [id = 3, parent = 1]
--- Banana [id = 4, parent =1]
- Cars [id = 5]
--- Ford [id=6, parent=5]
------ something [id=10, parent=6]
--- BMW [id=7, parent=5]
--- Mercedes [id=8, parent=5]
------ blah [id=11, parent=8]
------ hmm [id=12, parent=8]
--- Audi [id=9, parent=5]

 

lets say that i want to duplicate an entire section (for example, Cars) including its children, giving the clone a totally new set of id's/parent_id's.

 

i'm not really fussed about using other systems of storing tree data, so using this way - what are my options to do this? I was thinking of  simply adding a number to all the keys (based on the number of the last record in the DB), but I can see how this can possibly cause issues with my ID's all over the shop.

 

As a second question, lets say (for whatever reason) i wanted to tidy up my database - rewriting the keys from 1 to whatever with no gaps. can this be done easily? are there any special sorts of algorithms for doing something like that?

 

Any thoughts?

Cheers

[redbullmarky]

* bump *

anyone have any ideas?

[448191]

i'm not really fussed about using other systems of storing tree data, so using this way - what are my options to do this? I was thinking of  simply adding a number to all the keys (based on the number of the last record in the DB), but I can see how this can possibly cause issues with my ID's all over the shop.

 

I don't have clue what 'fussed' means, but I take the above quote means you have no interest in using preordered tree traversal? Using that method you can select a parent an and all it's children and use it in an insert statement.

[redbullmarky]

yeah i'm not comfortable enough with that method as yet, but i'd assume that the principles of duplicating a section of the tree to another node would pose the same sort of issues so just trying to solve the problem with a way i'm already familiar with. selecting parent/children is not the problem as such - but re-assigning ID's is.

[448191]

I can't think of anything 'off the bat' (as you would say). Obviously if you have an auto_increment field, that would automatically be assigned... But how to ensure that parent_id refers to the new id... You could simply split up the process, fetching a last entry id before inserting a child, but that's hardly ideal.

 

Unless.. It might be possible to do a select, and increment the NEW parent id by some equation. e.g., you get the new id for the root entry, calculate the difference between the old id, the the formula for a child's new parent id is: parent_id+displacement.

 

Just a thought, may not work.

[redbullmarky]

if i'm getting you right, i've considered that method but found that maybe it'll play havoc with my ID's. using my first example:

 

- Fruit [id = 1]
--- Apple [id = 2, parent = 1]
--- Orange [id = 3, parent = 1]
--- Banana [id = 4, parent =1]
- Cars [id = 5]
--- Ford [id=6, parent=5]
------ something [id=10, parent=6]
--- BMW [id=7, parent=5]
--- Mercedes [id=8, parent=5]
------ blah [id=11, parent=8]
------ hmm [id=12, parent=8]
--- Audi [id=9, parent=5]

 

i'd get the maximum ID(in this case 12) and add 1, and if i wanted to duplicate "mercedes" (key = 8 ) and copy it to be a child of 'orange' (key = 3), then i'd probably:

1, find the minimum ID of the tree i wish to copy, to prevent clashes (it'd be straightforward ordinarily, but there are possible occasions where a subcat/item could have an ID lower than its parent if for example i decide to move items)

2, in my example, 8 is the minimum ID of the tree i want to copy and 13 is the next available ID, so i'd add 5 onto all the children/grandchildren of mercedes and write them to the DB

3, set the parent ID of my new parent (ID 13) to 3. now i'd have:

 

- Fruit [id = 1]
--- Apple [id = 2, parent = 1]
--- Orange [id = 3, parent = 1]
------ Mercedes [id=13, parent=3]
--------- blah [id=16, parent=13]
--------- hmm [id=17, parent=13]
--- Banana [id = 4, parent =1]
- Cars [id = 5]
--- Ford [id=6, parent=5]
------ something [id=10, parent=6]
--- BMW [id=7, parent=5]
--- Mercedes [id=8, parent=5]
------ blah [id=11, parent=8]
------ hmm [id=12, parent=8]
--- Audi [id=9, parent=5]

 

so it WOULD work, but even in this small example, i've left a gaping hole between record 13 and 16. I'm not sure what impact this would have on a huge database.

 

now as i wrote that, i can see that it'd be easy in this case to rewrite the ID's and parent_id's, but looking further, this would become tricky when introducing grandchildren and greatgrandchildren, etc which is ultimately what's making this tricky

 

any more thoughts?

[448191]

I think you need to be strict about the assigning of id's, not having entries with id's lower than a 'previous'. The entries have to be 'in order'.

 

So this:

 

--- Mercedes [id=8, parent=5]

------ blah [id=11, parent=8]

------ hmm [id=12, parent=8]

--- Audi [id=9, parent=5]

 

Is something you would need to avoid. Before you do a insert, you have to rewrite the id's for all entries that come after it. E.g.:

 

UPDATE tree SET id = id+$displacement WHERE id > $newParentId

 

Note: if you do implement this, you may want to use an extra id field that doesn't change all the time. Probably even change the name of the current one, because it's now useless as an identifier.

 

So given this:

 

- Fruit [id = 1]

--- Apple [id = 2, parent = 1]

--- Orange [id = 3, parent = 1]

--- Banana [id = 4, parent =1]

- Cars [id = 5]

--- Ford [id=6, parent=5]

------ something [id=7, parent=6]

--- BMW [id=8, parent=5]

--- Mercedes [id=9, parent=5]

------ blah [id=10, parent=9]

------ hmm [id=11, parent=9]

--- Audi [id=12, parent=5]

 

You first update everything higher than 3 with the number of entries you're copying (3), resulting in this:

 

 

- Fruit [id = 1]

--- Apple [id = 2, parent = 1]

--- Orange [id = 3, parent = 1]

--- Banana [id = 7, parent =1]

- Cars [id = 8]

--- Ford [id=9, parent=8]

------ something [id=10, parent=9]

--- BMW [id=11, parent=8]

--- Mercedes [id=12, parent=8]

------ blah [id=13, parent=12]

------ hmm [id=14, parent=12]

--- Audi [id=15, parent=8]

 

Now that there is space, we can insert the copied entries:

 

- Fruit [id = 1]

--- Apple [id = 2, parent = 1]

--- Orange [id = 3, parent = 1]

------ Mercedes [id=12-8:4, parent=4-1: 3]

--------- blah [id=13-8:5, parent=5-1: 4]

--------- hmm [id=14-8:6, parent=6-2: 4]

--- Banana [id = 7, parent =1]

- Cars [id = 8]

--- Ford [id=9, parent=8]

------ something [id=10, parent=9]

--- BMW [id=11, parent=8]

--- Mercedes [id=12, parent=8]

------ blah [id=13, parent=12]

------ hmm [id=14, parent=12]

--- Audi [id=15, parent=8]

 

To do this you first need to acquire the mutation of the id's (-8 in this case). Something like ($newParentId-$rootCopyNodeOldId)+1 ((3-12)+1).

 

Then we need even more basic math to calculate all the new id's and parent id's:

 

SELECT id, parent_id, id-8 AS new_id, id-parent_id-8 AS new_parent_id

 

This is all hardly ideal and probably expensive on resources.

 

Tbh, I think you're better off using the Modified Preorder Tree Traversal. It suffers from the same problem, but easier solved IMO. All you have to do before inserting is select the number of entries whose left and right values are higher than the node you want to attach to and increase their left and right values by the number of entries to insert *2 (because every entry has a left and right value).

 

So say I have an entry with a left value of 5 and a right value of 12, I know I have to make extra space for 12-5(-1)/2 = 3 children. Adding the entry itself and multiplying by 2, I know I have increment the tree values by 8, which consequently is also the 'space' the entry to copy occupies: 12-5(+1).

 

So I could execute two simple queries like this:

 

UPDATE tree SET right = right+8 WHERE right>point_of_insertion;
UPDATE tree SET left = left+8 WHERE left>point_of_insertion;

 

Note that point_of_insertion doesn't necessarily equal the left value of parent node, it can also be the right value of an existing child node.

 

If a node doesn't have children it's left and right values will be sequential, e.g. 20-21. This is why you must subtract 1 when calculating the number of children. To calculate a point of insertion: right - 1. So in 20-21 that equals the parents left value, in for example 21-27 that equals the the last child's right value.

 

If recall correctly you can't do a INSERT...SELECT on a single table for some reason, but forgetting that for a second:

 

INSERT INTO tree (name, left, right)  SELECT name+($right-$left+1) , left+($right-$left+1), right+($right-$left+1) FROM tree WHERE left BETWEEN $left AND $right

[redbullmarky]

blimey, there's some food for thought! gimme a bit to read it but looks interesting, anyhow. if the pro's of using the other tree method outweight the cons (ie, the fact that it's totally alien to me, amongst other reasons) then i might look at making the switch if it makes it tonnes easier.

[448191]

I would read the article again. At first it makes little sense, but it is one of those things where at some point you get that AHA feeling. It's a solid way of storing hierarchical data. You might want to use id's too though because the left-right values are subject to change when something 'left' to an entry is added.

 

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