Updating Nested Set

Question

I was hoping someone could explain how one goes about updating a nested set.

I've looked at http://dev.mysql.com/tech-resources/articles/hierarchical-data.html, but it really only deals with adding and deleting nodes.

I need to be able to move nodes with and without child nodes.

Any help would be appreciated.

Answer 1

Consider that moving a node is equivalent to deleting the node and all its children, if any, and insertig the node, and its children if any, in the new position.

Now re-read the tech article, working out what the whole table will look like after you do that delete followed by that insert, and you'll find the update that does the same thing.

Answer 2

The Nested Sets design isn't a good choice for this kind of change to a tree. It's really complicated to recalculate the right/left numbers as you move nodes around.

The Adjacency List is the easiest tree design for moving subtrees:

UPDATE TreeTable
SET parent = $newparent
WHERE id = 123;

The Path Enumeration design also makes it easy to relocate a node and its children:

UPDATE TreeTable
SET path = REPLACE(path, 'A/B/C/', 'A/D/F/') -- MySQL function
WHERE path LIKE 'A/B/C/%';

Answer 3

Moving with child nodes:

In classic nested sets where the ‘left’ and ‘right’ values are all in a contiguous block of 0..n*2 values, there will be a range of rows that moves either ‘x’ places to the left or ‘x’ places to the right when the subtree is moved, where ‘x’ is the number of left/right values being moved. eg.

A: 1,6
   B: 2,3
   C: 4,5
D: 7,8
E: 9,10

If you moved ‘A’ with descendents to between ‘D’ and ‘E’, everything to the right of ‘A’ but to the left of ‘E’ needs to have its left/right indexes reduced by 6 (the size of ‘A’ with descendents):

UPDATE things
SET nsl=nsl+(
    IF nsl BETWEEN 1 AND 6 THEN 6  -- A-C go forward 6
    ELSE -6                        -- D goes back 6
), nsr=nsr+(                       -- same again
    IF nsl BETWEEN 1 AND 6 THEN 6
    ELSE -6
)
WHERE
    nsl BETWEEN 1 AND 6            -- select A-C
    OR nsl BETWEEN 7 AND 8         -- select D

Moving without child nodes is more complicated. The contained nodes have to go back one, the nodes after the removed node all have to go back two, then the nodes after the new insertion point have to go forward two to make room.

Whilst you can do this in the same style as above, it's starting to get really confusing and you might like to consider alternative approaches such as rewriting all the left/right values manually or using a different schema type that makes these kinds of operations simpler, such as a full ancestor-descendent adjacency relation.