RobertAkiraWatts


I'm hoping someone can help out with this. It seems like it should be easy, yet I keep banging my head against it to no avail. In short, I've got a table of employees. There's a number of fields, but the only relevant ones are:

ID int

SupervisorID int

LastName varchar (25)

What I'm trying to get is a list, by employee, of everyone under him in the hierarchy - not just one level, but all the way down. So, if the table has

1 Null Smith

2 1 Jones

3 1 Pink

4 2 White

5 3 Black

6 4 Green

I'd want to return something along the lines of:

LastName Supervises

Smith Jones

Smith Pink

Smith White

Smith Black

Smith Green

Jones White

Jones Green

Pink Black

White Green

Here's the code I've been tinkering with - in it's current state, it gets me one level down in the hierarchy.

WITH EmployeeCTE AS

(SELECT ID, LastName , SupervisorID

FROM Employee_EmployeeDatabase

WHERE SupervisorID is null

UNION ALL

SELECT E.ID, E.LastName, E.SupervisorID

FROM Employee_EmployeeDatabase E JOIN

EmployeeCTE x ON x.ID = e.SupervisorID)

SELECT ID, SupervisorID, LastName

FROM EmployeeCTE




Re: Navigating a hierarchy

Arnie Rowland


And Joe Celko's book, Hierachies and Trees, is an excellent resource. As is a Google search for "Hierachies and Trees".





Re: Navigating a hierarchy

Mark - SQL

Try this

WITH EmployeeCTE AS
(SELECT ID, LastName , SupervisorID
FROM Employee_EmployeeDatabase
WHERE SupervisorID is not null
UNION ALL
SELECT E.ID, x.LastName, E.SupervisorID
FROM Employee_EmployeeDatabase E JOIN
EmployeeCTE x ON x.SupervisorID = e.ID AND e.SupervisorID is not null)
SELECT E.LastName,C.LastName AS Supervises
FROM EmployeeCTE C
INNER JOIN Employee_EmployeeDatabase E ON E.ID=C.SupervisorID
ORDER BY E.ID






Re: Navigating a hierarchy

hunchback

You can create a function to returns the subordinates for a specific [ID], then use a "cross apply" to pass the [ID] of every manager.

Code Snippet

use northwind

go

create table dbo.t1 (

ID int,

SupervisorID int,

LastName varchar (25)

)

go

set nocount on

insert into dbo.t1 values(1, Null, 'Smith')

insert into dbo.t1 values(2, 1, 'Jones')

insert into dbo.t1 values(3, 1, 'Pink')

insert into dbo.t1 values(4, 2, 'White')

insert into dbo.t1 values(5, 3, 'Black')

insert into dbo.t1 values(6, 4, 'Green')

set nocount off

go

create function dbo.subordinates (

@ID int

)

returns table

as

return (

with cte

as

(

select LastName, ID

from dbo.t1

where SupervisorID = @ID

union all

select c.LastName, c.ID

from cte as p inner join dbo.t1 as c

on c.SupervisorID = p.ID

)

select LastName, ID from cte

)

go

select

a.LastName, b.LastName

from

dbo.t1 as a

cross apply

dbo.subordinates(1) as b

where

exists (

select *

from dbo.t1 as c

where c.SupervisorID = a.ID

)

order by

a.ID

option (maxrecursion 0)

go

drop function dbo.subordinates

go

drop table dbo.t1

go

AMB





Re: Navigating a hierarchy

Gert-Jan van der Kamp

We deal with hierachies a lot, typical installations have some 100k + objects in it, what we do is this:

Create a column

Lineage varchar(300) Null

Run this Query:

Code Snippet

Update TableX

Set Lineage = null

Update TableX

Set Lineage = cast(Id as varchar)

where SupervisorId is null --(or 0 or Id whatever you do for top elements)

While @@RowCount > 0

Update C

Set Lineage = P.Lineage + '.' + cast(C.Id as varchar)

From TableX C

inner join TableX P on C.SupervisorId = P.Id

where not P.Lineage is null

and C.Lineage is null

What you end up with is in your example is this

1 Null Smith 1

2 1 Jones 1.2

3 1 Pink 1.3

4 2 White 1.2.4

5 3 Black 1.3.6

6 4 Green 1.2.4.6

when you want to get everyone under Pink including Pink itself you

select *

from TableX

where Lineage like '1.3%'

without Pink:

select *

from TableX

where Lineage like '1.3.%' -- notice the dot before %

get all the ancestors of Green:

Select *

from TableX

where '1.2.4.6' like Lin + '%'

This works like a charm and is very fast as opposed to recursive queries because you can index the Lineage column. You can also include a level (int) column to select objects below or above a level in the hierarchy.

If you do a lot of updates in the hierarchy you should create a trigger that updates the lineage kind of like the initial query, because you have to update the entire subtree to leaf level.

Good luck,

John






Re: Navigating a hierarchy

hunchback

Hi Gert-Jan van der Kamp,

Thanks for mentioning it, I think it is worthy to mention other ways to deal with hierarchies in SQL Server, other than Adjacency List.

Materialized Path

Inside Microsoft SQL Server 2005: T-SQL Querying

by Itzik Ben-Gan, Lubor Kollar and Dejan Sarka

Chapter 9 - Graphs, Trees, Hierarchies, and Recursive Queries

Nested Sets

http://www.intelligententerprise.com/001020/celko.jhtml _requestid=1266295

Nested Intervals

http://www.dbazine.com/oracle/or-articles/tropashko4

AMB





Re: Navigating a hierarchy

RobertAkiraWatts

I arrived at something along those lines about an hour after posting my initial query. And, alas, I exhaust the maximum recursion. And setting maxrecursion to infinity gives me something that churns along far too long for my tastes. My suspicion is that CTEs, while elegant looking, might not be the best fit for this problem.



Re: Navigating a hierarchy

RobertAkiraWatts

Thanks. I got to something along these lines after going through Ken Henderson's Guru's Guide to T-SQL. And it's pretty much worked.

Appreciate everyone's answers. I'll do a bit more Googling next time.





Re: Navigating a hierarchy

Gert-Jan van der Kamp

Hunchback,

I actually considered switching to the nested sets technique for a minute (in conjunction with adjency), because is a lot more efficient storagewise. (we compress the int to a few chars with a hash before putting it in the path to counter that). I had seen NS before but it seemed to complicated then, now i've had a good look at it it's actually pretty clever.

We have a lot of inserts, deletes and moves in the hierachy though, Nested sets would require renumbering the entire tree. The upside with the materialized path in this case is that the changes are isolated to the subtree below the affected node. So i'll stick with the materialized path for now. Also becuase it's so simple i guess...

Thanks for pointing it out,

John