SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Everybody Reports to Somebody


Everybody Reports to Somebody

Author
Message
Mike C
Mike C
Hall of Fame
Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)

Group: General Forum Members
Points: 3627 Visits: 1168

Hi David and Craig,

The LeftID and RightID define a subset. In the case of John, his LeftID=1 and RightID=24. Anyone with a LeftID and RightID between these two numbers are defined by a subset of John's set. Bob's has the LeftID=2 and RightID=15, so his numbers are a subset of John's set {1..24} (apologies for the "fake" set notation .) Therefore, Bob reports to John. And so on...

Actually you don't need to use the adjacency list to renumber the left and right ID's of your nested sets. There are some other options to improve efficiency. In the example I gave the sets were a "tight" fit, with the left and right id numbers as close together as possible. However, that's not a requirement. You can actually spread them out further to start with, so long as they still properly "nest" within one another. For instance:

John Smith, LeftID=1, RightID=1000

Bob Johnson, LeftID=20, RightID=150

Sue Fields, LeftID=300, RightID=400


In this case, Bob and Sue are still nested within John Smith, but the range between LeftID and RightID has been widened. You can easily insert or delete individuals without recalculating (dependent on business rules). The recalculations come in when Bob's entire range is filled and he gets another subordinate.

Using this method you don't need to recalculate LeftID and RightID as often, which, as David pointed out can hurt performance on large data sets. Renumbering can also be done with just a few statements (albeit slightly more complex ones). This method also has the advantage that you can calculate things like the level of each employee in the hierarchy, total height of the tree, etc., relatively easily.

You can also convert adjacency list to nested sets, and vice versa.

Celko's written a lot on the topic of nested sets versus adjacency list. He also has a pretty good book on the subject - "Trees and Hierarchies in SQL". Although it's not SQL Server specific, his examples are fairly easy to port over.

Also, if you're going to use the adjacency list, you might consider using recursive CTEs (SQL 2K5) - they were defined for this type of thing


Timothy-313907
Timothy-313907
SSC-Enthusiastic
SSC-Enthusiastic (198 reputation)SSC-Enthusiastic (198 reputation)SSC-Enthusiastic (198 reputation)SSC-Enthusiastic (198 reputation)SSC-Enthusiastic (198 reputation)SSC-Enthusiastic (198 reputation)SSC-Enthusiastic (198 reputation)SSC-Enthusiastic (198 reputation)

Group: General Forum Members
Points: 198 Visits: 721

"In practice, does the data in the set correspond to an organisation's departmental structure, rather than individual relationships"

This is just a different model for storing hierarchical data in SQL tables. The origial article presented an adjacent set model, Mike presented a nested sets model, and there's another I've seen used called the maternalized path model. The maternalized path model is basically the same structure as a URL, folders and paths. In that model you store a node's entire ancestry in a column. To get to your question though, with both the nested sets and maternalized path models the information you use to maintain the tree structure can be, and usually is, entirely fictional with no relationship whatsoever with the data it's associated with. Kind of like inventing an ID column for a table instead of using a person's name as a key for instance.

I haven't had to model hierarchical data for a project in a while but I used the nested sets model to do it when I did. It really isn't as difficult to use or maintain as some articles I've read about it indicate -- of course I'll suffix that by saying each model has its advantages and disadvantages. Changing someone's boss, for instance, is essentially moving a node within the tree. In the nested sets model this boils down to updating rows that are between numerical ranges and adding or subtracting numbers. With the maternalized path model you update rows that are LIKE a certain string. In either case you could potentially update every row in the table. The adjacent set model wouldn't update as many rows to do this.


Mike C
Mike C
Hall of Fame
Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)

Group: General Forum Members
Points: 3627 Visits: 1168

Here's a short CTE, assuming a table named #Employees with the data shown in the article:

WITH OrgChart (UserID, LastName, FirstName, ManagerUserID)
AS
(
SELECT UserID, LastName, FirstName, ManagerUserID
FROM #Employees
WHERE ManagerUserID = 0
UNION ALL
SELECT e.UserID, e.LastName, e.FirstName, e.ManagerUserID
FROM #Employees e
INNER JOIN OrgChart o
ON e.ManagerUserID = o.UserID
)
SELECT UserID, LastName, FirstName, ManagerUserID
FROM OrgChart;

Please excuse any typos - I had to retype this in here.


Nils Gustav Stråbø
Nils Gustav Stråbø
SSCrazy
SSCrazy (2.7K reputation)SSCrazy (2.7K reputation)SSCrazy (2.7K reputation)SSCrazy (2.7K reputation)SSCrazy (2.7K reputation)SSCrazy (2.7K reputation)SSCrazy (2.7K reputation)SSCrazy (2.7K reputation)

Group: General Forum Members
Points: 2701 Visits: 3575
"I was hoping it would appear in SS2005..."

SQL Server 2005 introduced Common Table Expressions (CTE) which can be recursive.
deanroush
deanroush
SSC Journeyman
SSC Journeyman (84 reputation)SSC Journeyman (84 reputation)SSC Journeyman (84 reputation)SSC Journeyman (84 reputation)SSC Journeyman (84 reputation)SSC Journeyman (84 reputation)SSC Journeyman (84 reputation)SSC Journeyman (84 reputation)

Group: General Forum Members
Points: 84 Visits: 265
I like Craig's original approach because performance is good and it is straightforward. Another important consideration is many, if not most organizations that I am aware of tend to follow the 'one-employee-one-manager' model. I utilize essentially the same algorithm with three differences: 1) I encapsulate all of the code within the stored procedure, which simply outputs an ordered four-column dataset (SortName [Last, First], Employee ID, SupervisorID, Level), 2) I include the Level column (integer), which indicates how many levels down from the specified manager each employee is in the hierarchy, and 3) I have an additional input parameter for Level, which allows me to easily return only the direct reports for the manager (or some other number of levels deep that I may be interested in at the moment). Of course, my method makes certain assumptions about how the names will be used since I am controlling the name format (we do a lot of dropdown lists and reports using the output.)
James Raddock
James Raddock
SSC Journeyman
SSC Journeyman (89 reputation)SSC Journeyman (89 reputation)SSC Journeyman (89 reputation)SSC Journeyman (89 reputation)SSC Journeyman (89 reputation)SSC Journeyman (89 reputation)SSC Journeyman (89 reputation)SSC Journeyman (89 reputation)

Group: General Forum Members
Points: 89 Visits: 102
Being familiar with both the nested set model [specifically Celko's push stack] and the CTE model, they each have their advantages and are relatively easy to set up. I recommend the adjacency list for OLTP systems with a sproc to generate the nested set as hierarchical data is needed (it's a cheap operation).

Another option that I feel should at least be mentioned is denormalizing your data, although it limits the number of levels you can have in your hierarchy. Denormalization, however, would be the fastest hybrid OLTP/OLAP solution (nested sets IMO are functional OLAP).

- James
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (114K reputation)SSC Guru (114K reputation)SSC Guru (114K reputation)SSC Guru (114K reputation)SSC Guru (114K reputation)SSC Guru (114K reputation)SSC Guru (114K reputation)SSC Guru (114K reputation)

Group: General Forum Members
Points: 114655 Visits: 41394
James Raddock (5/16/2008)
...with a sproc to generate the nested set as hierarchical data is needed (it's a cheap operation).


I know this is an old thread, but can you post the code for that sproc? Thanks.

--Jeff Moden

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search