# Thursday, August 12, 2004
« Uniqueidentifiers and Parent Child Dimen... | Main | RSS Feed »

If you are currently using the nested sets model for storing trees then it may be about time for a change. This model is great for queries but inserts and updates can touch nearly every row in the table. The more natural way of storing trees is via a ParentID known as the adjacency list model as shown below:

create table dbo.Projects

(

ProjectID int not null,

ParentID int null,

Name nvarchar(max) not null

)

The big drawback, however, is that you need to write recursive queries to get anything useful. Help is at hand though as SQL Server 2005 adds some features to automatically unwind the tree: Common Table Expressions or CTEs.

The basic structure of a CTE working with hierarchies is:

with <theCTE>

(

<anchor expression>

union all

<recursive expression>

)

select * from <theCTE>

Where the <anchor expression> determines where to start the recursion and the <recursive expression> does the work. Note that the <recursive expression> should join to the CTE to work properly, for example the following lists all descendants of the project defined by <rootID>:

with Tree (ParentID, ProjectID, Name, Level, Path)

as

(

select ParentID, ProjectID, Name,

0 as [Level], '/' + Name as [Path]

from dbo.Projects

where ParentID = <rootID>

union all

select p.ParentID, p.ProjectID, p.Name,

t.Level + 1, t.Path + '/' + p.Name

from dbo.Projects p

join Tree t on t.ProjectID = p.ParentID

)

select ParentID, ProjectID, Name, Level, Path

from Tree t

order by ParentID, Level, ProjectID

Note how the Level and Path are calculated by adding to the result from the previous iteration.

You can also recurse up the tree:

with Tree (ParentID, ProjectID, Name)

as

(

select ParentID, ProjectID, Name

from dbo.Projects

where ProjectID = <rootID>

union all

select p.ParentID, p.ProjectID, p.Name

from dbo.Projects p

join Tree t on t.ParentID = p.ProjectID

)

select distinct

ProjectID, ParentID, Name

from Tree t

order by ParentID, ProjectID

When you consider you can wrap these queries into table valued functions, there is a lot of scope for writing cohesive reusable SQL.

by This posting is provided "AS IS" with no warranties, and confers no rights.
posted on Thursday, August 12, 2004 2:37:48 PM (GMT Daylight Time, UTC+01:00)  #    Comments [0] Trackback
Related posts:
Do you have great business intelligence skills?
Integration Services Design Principals
Physical Data Warehouse Design
Analysis Services Essential Reading
When should you do an incremental extract?
Post TechReady and Popfly Invites
Comments are closed.