SQL Server 2008 - HierarchyId - How do you move nodes/subtrees around

In a recent post SQL Server 2008 - HierarchyId whats the point? I talk about the scenarios that the new hieararchyId can be applied to. Here we expand on this further and also provide a solution for moving hierarchies around.

The limitation is that you can't do something like this to change the parent of a node.

declare @newParent = (select node from Org where OrgId = 1234)

update Org

   set node.parent = @newparent

 where OrdId = 4567

Similarly if you want to move all the children nodes of one node to another node you can't in a simple way.

The reason is that the hierarchyId is a path enumeration model and if node 457 has children the children have the path to node 4567 embedded in them, i.e. they reference the 4567 node by path.

Look at this situation with nodes "/", "/1/" and "/1/1/", "/1/1/1/, "/2/" and "/2/1/", "/2/1/1", "/2/2/" and "/2/2/1" represent the root and two sets of a grand parent, parent and child nodes. See diagram.

We want to move the sub tree of  "/1/1/" to the new parent "/2/", by subtree I mean all the nodes below and including "/1/1/". Those with bold outlines below

If we change the parent of "/1/1/" to "/2/" using the reparent function then we will have a conflict in our hierarchy. As there will now be two nodes with the same path.

Whats more if we don't change the path of the nodes below "/1/1/"  then these nodes will reference an invalid path (an ancestor will be missing).

So we have to reparent all the nodes in the subtree. Unfortunately that makes the issue of nodes with the same path even worse. (See nodes with a red outline)

 

So what we have to do is find the last child of our new parent, in this example "/2/2" in order that we can move the sub tree to a new path that doesn't conflict with an existing one, "/2/3/"

As we are maintaining the subtree below the node we are moving we have to reparent the child nodes using this new parent record.

Nicely the reparent function on the hierarchyId type if you specify a old parent node that is itself it will just return the new parent i.e. just changing its own path. (Note the reparent is not a mutator so you have to assign the result of the reparent function). Reparent unlike its name suggests doesn't do anything but return a node with a path based on the inputs.

So thats the logic so how do you go about doing it in code. The following includes a few more nodes to show moving multiple trees in one go.To setup the tables and data use the script at the end.

Firstly lets find the maximum for the child we want to move 

declare @NewParent hierarchyId = '/3/'

declare @OldParent hierarchyId = '/1/'

 

--Find the max child node that belongs to the new parent node. The nodes being moved will be

--appended after those that already belong to the new parent

declare @Maxchild hierarchyId = (select max(node)

                                   from HTest

                                  where @NewParent.IsDescendant(node) = 1

                                    and node.GetLevel() = @NewParent.GetLevel() + 1)

You could use GetAncestor which is equivalent to the code above, I think the above is more readble.

Unfortunately there is no method to return the child index of a node, the reason we need this is that we are going to build the path directly and so need the child index so we can add values to it.

declare @ChildCount int = (select substring(left(@MaxChild.ToString(),LEN(@MaxChild.ToString()) - charindex('/',reverse(@MaxChild.ToString()),2) ),2,10))

So now the crunch, what we need to do is find all the nodes we are going to move. We will be moving two types of node. Top level nodes and child nodes, it is the top level nodes we that need to have there position calculated. The position of the children don't change. If in the example above the child "/1/1/1/" is still the 1st child of its parent the only difference is its parent is now "/2/3/".

We therefore need to calculate the position for these parents. This can be used by using a window aggregate. The dense_rank() allows us to return the same position for the parent as well as the children. To do this for the children we use the GetAncestor and GetLevel methods to find the parent node that is moving (it actually works for the parent as well so we can use the same code in the order by). This dense_rank returns an incrementing value starting at 1. We can then add that to the max child position calculated above. In conjunction with the new parent path we have the new path for the top nodes we are moving.

We can then use Reparent method to return the new paths of the nodes.

The following is a SELECT statement that returns the reparented nodes so you can see what is going on.

--Query to calculate the new path by using the reparent function along with a calculation to work out the correct position in

--the children of the new parent.

select  node.Reparent(oldNodeParent, @NewParent.ToString() + cast(@ChildCount + NewChildPos as varchar(10)) + '/').ToString(), *

from (

select node

     , dense_rank() over (order by node.GetAncestor(node.GetLevel() - @OldParent.GetLevel())) NewChildPos

     , node.GetAncestor(node.GetLevel() - @OldParent.GetLevel()).ToString() oldNodeParent

     , value, node.ToString() nodeText, node.GetAncestor(1).ToString() Parent -- these are for debugging aren't need to calculate the new path.

from HTest

where value like '1.1.%'

or value like '1.2.%') d

This shows how the above can be used in an update statement.

update HTest

  set node = d.node.Reparent(oldNodeParent, @NewParent.ToString() + cast(@ChildCount + NewChildPos as varchar(10)) + '/').ToString()

from (

select node

     , dense_rank() over (order by node.GetAncestor(node.GetLevel() - @OldParent.GetLevel())) NewChildPos

     , node.GetAncestor(node.GetLevel() - @OldParent.GetLevel()).ToString() oldNodeParent

from HTest

--This is the criteria for selecting the nodes to move.

where value like '1.1.%'

or value like '1.2.%'

) d

where d.node = HTest.node

To setup the tables and data use the following script

set nocount on

go

use test

go

drop table Htest

go

create table HTest (node hierarchyId, value varchar(10))

go

create unique index IX_HTest_node on HTest(Node)

go

declare @h1     hierarchyId = HierarchyID::GetRoot()

declare @h1_1   hierarchyId = @h1.GetDescendant(null,null)

declare @h1_2   hierarchyId = @h1.GetDescendant(@h1_1,null)

declare @h1_3   hierarchyId = @h1.GetDescendant(@h1_2,null)

declare @h1_4   hierarchyId = @h1.GetDescendant(@h1_3,null)

declare @h1_5   hierarchyId = @h1.GetDescendant(@h1_4,null)

declare @h1_1_1 hierarchyId = @h1_1.GetDescendant(null,null)

declare @h1_1_2 hierarchyId = @h1_1.GetDescendant(@h1_1_1,null)

declare @h1_1_2_1 hierarchyId = @h1_1_2.GetDescendant(null,null)

declare @h1_1_3 hierarchyId = @h1_1.GetDescendant(@h1_1_2,null)

declare @h1_2_1 hierarchyId = @h1_2.GetDescendant(null,null)

declare @h1_2_2 hierarchyId = @h1_2.GetDescendant(@h1_2_1,null)

declare @h1_2_3 hierarchyId = @h1_2.GetDescendant(@h1_2_2,null)

declare @h1_3_1 hierarchyId = @h1_3.GetDescendant(null,null)

declare @h1_3_2 hierarchyId = @h1_3.GetDescendant(@h1_3_1,null)

declare @h1_3_3 hierarchyId = @h1_3.GetDescendant(@h1_3_2,null)

 

insert into HTest values(@h1    ,'1')

insert into HTest values(@h1_1  ,'1.1')

insert into HTest values(@h1_2  ,'1.2')

insert into HTest values(@h1_3  ,'1.3')

insert into HTest values(@h1_4  ,'1.4')

insert into HTest values(@h1_5  ,'1.5')

insert into HTest values(@h1_1_1,'1.1.1')

insert into HTest values(@h1_1_2,'1.1.2')

insert into HTest values(@h1_1_2_1,'1.1.2.1')

insert into HTest values(@h1_1_3,'1.1.3')

insert into HTest values(@h1_2_1,'1.2.1')

insert into HTest values(@h1_2_2,'1.2.2')

insert into HTest values(@h1_2_3,'1.2.3')

insert into HTest values(@h1_3_1,'1.3.1')

insert into HTest values(@h1_3_2,'1.3.2')

insert into HTest values(@h1_3_3,'1.3.3')

 

go

select *, node.ToString() from HTest

 

 

 

 



-
Published 31 March 2008 10:13 by simonsabin

Comments

# Dew Drop - April 1, 2008 | Alvin Ashcraft's Morning Dew

Pingback from  Dew Drop - April 1, 2008 | Alvin Ashcraft's Morning Dew

# Reflective Perspective - Chris Alcock » The Morning Brew #64

Pingback from  Reflective Perspective - Chris Alcock  » The Morning Brew #64

# Migracja id-parentid do hiererchyid | itsouldiers.com/blog

Pingback from  Migracja id-parentid do hiererchyid | itsouldiers.com/blog