I ran into an interesting problem today while considering how to find out where subordinate employees fit into an organizational chart. The problem was that I need to list every employee that was “under” a given employee, but could only really do this in SQL - if I were to try and do this from within PHP, it would have made a single exception case where we build an SQL query based on another query - something I’d rather not have to do. Let’s see if this little graph can more adequately describe what the issue was:
+-----------+-------------+ | Employee | Subordinate | | --------- | ----------- | | Frank | Tim | | Frank | Jacob | | Frank | John | | Frank | Mark | | Tim | Chris | | Tim | Randy | | Randy | Dave | | Mark | Joey | +-----------+-------------+
So, with this list, the goal was that if I were looking for all subordinate employees under Frank, it would return rows with the names “Tim, Jacob, John, Mark, Chris, Randy, Joey”, since everyone else is under Frank. However, if I were to look for Tim’s subordinates, I’d only get “Chris, Randy, Dave”, and if I looked for Joey, I wouldn’t get any rows.
What does this mean, then? It means we have to search the table multiple times - once for each node, or employee, that we find - the first entry we give it as well as every entry below that employee. It also means we need to hard code the number of levels of employees we’re looking for, or, gasp, use recursion in our SQL.
To fix this issue, I started by digging around in Google. I’m using MSSQL, so maybe I could have created a stored procedure, but I tend to shy away from them in case I ever want to change database technologies. What I found was a really great PDF that almost matched my needs over at NaSPA . The problem with the query he came up with, however, is that it merely wanted to know the number of subordinates, where we’re interested in much more data than that.
This is the solution I came up with based on Rob Mala’s code:
(
SELECT Employee, Subordinate, 0
FROM orgChart WHERE Employee = ‘Frank’
UNION ALLSELECT a.Employee, b.Subordinate, a.iteration + 1
FROM temp_orgChart AS a, orgChart AS b
WHERE a.Subordinate = b.Employee
)
SELECT Subordinate
FROM temp_orgOrgchart
Let’s take a look at this step by step then, shall we? Maybe you’ll get a grasp of how to adapt this for your needs.
WITH temp_orgChart (Employee, Subordinate, iteration) AS
(
All this says is that we’re creating a temporary table to do our SELECT command on, and that this table is going to have three columns - “Employee”, “Subordinate”, and “iteration”.
SELECT Employee, Subordinate, 0
FROM orgChart WHERE Employee = ‘Frank’
UNION ALL
Here, we’re doing our first step in the recursive technique - finding the very first employee to start with. Notice that we’ve added a “0″ to the end of the SELECT list - this is our index. As we increase our index, we go deeper into the tree of employees. Also, if we wanted to start with a different employee, we’d name him here instead of Frank.
We also did a UNION ALL afterwards. This means we’re going to include everything in the next statement too.
SELECT a.Employee, b.Subordinate, a.iteration + 1
FROM temp_orgChart AS a, orgChart AS b
WHERE a.Subordinate = b.Employee
This is our recursive step. This means it’s essentially the equivalent of calling a specific SELECT statement with different input over and over again based upon the results of the preceding SELECT statement. Here, we’re grabbing the current employee that we just found, and looking for their subordinate in the organizational chart. When we find one, we look for that subordinate’s subordinates and if we find one we do it again until we don’t find any more. We then go back to the previous subordinate and keep digging.
The process goes like this:
- The original step (before recursion) adds the following values to the temporary table:
Frank, Tim, 0
Frank, Jacob, 0
Frank, John, 0
Frank, Mark, 0 - The first recursive step looks into the existing temporary table, and sees that Tim has people below him, and adds the following values to the temporary table:
Tim, Chris, 1
Tim, Randy, 1 - The recursion then sees that Randy has someone below him:
Randy, Dave, 2 - The recursion doesn’t see anyone else below, so it returns to the last level and adds:
Mark, Joey, 1
This is the confusing step, and may be difficult to wrap your mind around. Hell, it was a mess for me to figure out and I’m not entirely sure the above process is exactly the way it’s done, but I do know that the code works. It’s okay - take the code, and play with it. Keep in mind that every iteration is a new “level” on the chart.
SELECT Subordinate
FROM temp_orgOrgchart
Back to the simple stuff - this just says that the data we want is in the column “Subordinate” in the temporary table we’ve just filled up.
This recursive SQL statement really isn’t too difficult, as there’s only one really confusing bit to it - the actual recursion.
I hope this helps a few of you put together the calls you need and saves you some time.
This is a little known but wonderful technique. I used it in the past for building an org chart type of results. When you look at the full query it is a bit confusing as to how it works, but work it does.
Nice write up.
I would prefer using nested sets. There should be libraries for your language.
I guess this works, but a much cleaner, clearer and efficient way to achieve this is to use an MPTT (modified pre-order tree traversal) table. It employs the use of a ‘left’ and ‘right’ value for each node in the tree, and with one sql query (no temporary views/tables) you can get the complete (and ordered) list of all children, or if you know the child and want all parents, you can get a breadcrumb trail back up the tree as well with one query. Work smart, not hard
I understand how MPTT can be used for easy retrieval from a tree. However, am I missing something, or will every change (insert/delete/move) to a tree mean that the right/left values of every node in the tree may need to be rebuilt? It seems to me that any time the tree changes, you have to do a recursive traversal to rebuild the MPTT indices, and only after that could you take advantage of MPTT’s easy retrieval. Of course in some situations it’s a worthwhile tradeoff - I just want to make sure I’m characterizing this correctly. Thanks, -Juan
Would a ‘connect by’ statement work here?
select employee, subordinate, level
from orgChart
start with employee = ‘Frank’
connect by subordinate = prior employee
If I’m not mistaken, this would produce a list of employees who report to Frank. ‘level’ in this case would produce an incremented number based on the ‘level’ below Frank.
I’m a little confused by the implied schema of the orgChart. I think it would be better if each employee record held a reference to the supervisor, but whatever.
Thank you for this! I used your example to replace a cursor method I was using and it cut the query response time to about half.
Very nice article!
- Glen
Thanks! I never knew that this method existed. It has saved me a lot of time.
very interesting article. wish i had known this earlier, would have saved me a lot of trouble. but knowing it now with such a clear explanation is very much worth appreciating the author.
Check out “Common Table Expressions” here:
http://technet.microsoft.com/en-us/library/ms186243.aspx
This is a pretty convenient way to do recursive queries
Thank you for sharing this. I had a similar issue looking at categories of various levels (category-subcate-subsubcate .. etc), and your script helped tremendously. One thing I’d like to point out though, from following your code, is that you missed a space in “ALLSELECT” (making it “ALL SELECT”). Me with my entry level sql knowledge thought it was some secret keyword I’ve never came across.
It’s a very helpful ability of SQL, especially in areas like B.O.M., Organisation Charts, or anywhere that you have a Parent-Child-Grand child relationship.
An extra step tat can be done here to make these even more useful is by creating a Table Function. With this you can provide a Parameter, which can then be used as the starting point for the recursive SQL. For instance - pass through the name of a person, and return all subordinates below that particular person.
This then also allows you to use the function within a SQL statement at any time.
Example:
create function ReportingLines(@StaffID VARCHAR)
RETURNS TABLE AS RETURN (
WITH ReportStructure (StaffID, StaffName, ManagerID, [Level]) AS
(
SELECT StaffID, StaffName, ManagerID, 0 AS [Level]
FROM StaffTable
WHERE StaffID = @StaffID
UNION ALL
SELECT Child.StaffID, Child.[StaffName], Child.ManagerID, ReportStructure.[Level] 1
FROM StaffTable AS Child
INNER JOIN ReportStructure ON ReportStructure.StaffID = Child.ManagerID
)
SELECT * FROM ReportStructure
)
Then to use this you would simply do;
SELECT * FROM ReportingLines(’000001′) WHERE Level = 1 — Return all direct Reports to
SELECT * FROM ReportingLines(’000001′) WHERE Level > 0 — Return all people underneath
Cheers
This is very important article for me.but I have no success to do this.
I am using mysql (Server version: 5.0.51b-community-nt)
please can you help me
———————————————————————-
OrgCart problem:how retreive all children of a parent
How my database design:
Table org_chart(int ID,int ParentID,string name)
example:
__________
1 |0 |A
2 |0 |B
3 |1 |C
4 |2 |D
5 |1 |E
6 |3 |F
————
Hint:the ParentID of A=0 => A has no parent (it is root)
the Problem1:
I want to retrieve all children of a specific parent that has id=X.with ONE SQL statment.SO no need to use a recursive function in my program.
example:all children of A are (C,E,F).
the Problem2:
I want to retrieve all parents of a specific child that has id=X.with ONE SQL statment.SO no need to use a recursive function in my program.
example:all Parent of f are (C,A).
I want the solution in SQL standard or in MySQL database
If any have a solution in another database like oracle write it with note about where can we use.
———————————————————-
Thanks for this article. I found this very useful.
This was very well explained and really helped me a lot today. Thanks so much for taking the time to write it up.
Thanks - Charlie
Excellent article. One line of code I suggest adding is in the second where clause. In my code I added the equivilent of:
and not (a.Employee = b.Subordinate)
This stops the iteration if a subordinate points back to employee, thus creating a loop.
Dear Ben,
Thanks a lot for your article, really helpful. I was wondering if there is a way to create a more comprehensive manager-employee table where I can list not only all employees of Frank but Tim, Jacob, John etc. I am building a fact table for a cube where each user (manager in your case) will have all allowed groups - both parent and children - (employee) listed.
Are unions allowed with the recursive queries? Something like
WITH temp_orgChart (Employee, Subordinate, iteration) AS
(
SELECT Employee, Subordinate, 0
FROM orgChart WHERE Employee = ‘Frank’
UNION ALLSELECT a.Employee, b.Subordinate, a.iteration 1
FROM temp_orgChart AS a, orgChart AS b
WHERE a.Subordinate = b.Employee
) ;
union
WITH temp_orgChart (Employee, Subordinate, iteration) AS
(
SELECT Employee, Subordinate, 0
FROM orgChart WHERE Employee = ‘Tim’
UNION ALLSELECT a.Employee, b.Subordinate, a.iteration 1
FROM temp_orgChart AS a, orgChart AS b
WHERE a.Subordinate = b.Employee
) ;
union
etc.
Is there any way to automatically loop through Tim, Jacob …? Otherwise I have to manually define all the where clauses and then maintain it. Help is much appreciated
Thanks, for the sharing… encountered something similar in my web project.
I am wondering, exactly how many times will this loop until it ends is it just 4 times? Also how fast/slow is this technique when you are looping through a lot of information?
very useful technique ! Thanks you
If you get Oracle error ORA-32031 then you should use the CONNECT BY statement.
E.g.:
SELECT wbs_id
FROM PROJWBS
START WITH wbs_id = 4264
CONNECT BY PRIOR wbs_id = parent_wbs_id;
Please, be serious. This code does not work, there are sintax errors:
1. UNION ALLSELECT …
It should be:
UNION ALL
SELECT …
2. SELECT Subordinate
FROM temp_orgOrgchart
It should be:
SELECT Subordinate
FROM temp_orgChart
The name of the table is not correct.
A good example:
http://consultingblogs.emc.com/christianwade/archive/2006/09/20/SQL-Server-Standard-_2D00_-Recursive-Hierarchies-to-XML.aspx
Dear Billy Huang,
I got ORA-32031, but I don’t know how to fix that.
would you help me to modify with this example on Oracle?
Jim
Thanks a lot!
This was great and save my day at work.
I just modified this line:
UNION ALLSELECT a.Employee, b.Subordinate, a.iteration 1
as:
UNION ALL SELECT b.Employee, b.Subordinate, a.iteration 1
since a.Employee does not generate the parents at output.
Cheers,
Jeff
I just had little knowledge in sal.. but I had a situation to get exactly like this.
and When I read this .. I just thought what a perfect example ..
Great work..and thank you very much
This code looks promising but I cannot convert it to mssql.
I get the “Incorrect syntax near the keyword ‘WITH’” error message. I even found similar example in the mssqk 2005 help but still I recieve this error. What can be wrong in there? Anyone had similar case?
Thanks.
This is awesome. I have had to do this in the past using Recursive Stored Procedures - nasty. This is a really elegant and nice solution to a “common” problem. Now all I have to do is fully understand it, rather than use CTRL-C and CTRL-V
I received a pair of uggs on sale for Christmas and after only wearing them sporadically (and never really in wet weather) for little more than a year, a hole developed in one boot. I was disappointed that they did not last longer for the price you pay and the expectations of a good quality boot.
Hi Friends,
I was trying to run this query as per mysql format but couldn’t successed. Please clear where can I be wrong
create temporary table temp_orgChart (Employee VARCHAR(100), Subordinate VARCHAR(100) not null, iteration bigint(100))
SELECT Employee, Subordinate, 0
FROM orgChat WHERE Employee = ‘Frank’
union all SELECT a.Employee, b.Subordinate, a.iteration 1
FROM temp_orgChart as a, orgChart AS b
WHERE a.Subordinate = b.Employee;
select Employee,Subordinate,iteration from temp_orgChart;
Boots sold UGG boot hot ugg all households maintain our heart to find your favourite, UGGs stunning collection design ugg boots in the UK. High Nike classic high-drunk UGG starts Baise in-ear ghd ugg boots Baise ear button
This was very useful. I am a programmer of necessity and I love it when I find helpful hints like this. Well written.
Thank you
David
JUST DO IT
It is my great pleasure to visit your website and to enjoy your excellent post here. I like that very much. I can feel that you paid much attention for
those articles, as all of them make sense and are very useful. Thanks so much for sharing. I can be very good reader&listener if you are same searching for
all to be good. Appreciate for your time!
Happy New Year!
http://www.uggboots-home.net
http://www.cheapuggsonline.net uggs outlet
This is a really nice article. I am sure a lot of people will benefit from it. Thanks!
I have carefully read your Bo-wen, indeed very good. Do you know http://www.eshooes.com cheap shoes store
Watch this article:
http://msdn.microsoft.com/en-us/library/ms186243.aspx
It is for SQL Server 2008, it is good.
I am so glad you shared this here. I have been looking around for a way to create recursive sql calls for tables with parent-child relationships. Thank you.
This information shared here was brilliant. Thanks for sharing.
Thank you so much for posting this article here. It was a great read.
This recursive SQL statement really isn’t too difficult, as there’s only one really confusing bit to it - the actual recursion.
If I had to try this from within PHP, it would have made a single exception case where we build an SQL query based on another query, So thanks mate!
According to my analysis, billions of persons on our planet receive the loan from good banks. Hence, there’s good chances to get a credit loan in all countries.
This is great for recursive expansions, such as BOM and org charts. What about recursive collapses? Say I have some intervals:
1,3
2,5
4,6
9,14
10,11
12,13
ultimately, I want the results to be
1,6,3
9,14,3
where the third value is the count of the number of overlapping subintervals composing the interval.
Doing the blind approach leads to a runaway expansion that terminates after a recursive depth of 100. That makes sense because this syntax is geared toward expanding - that is what the join does. Actually I suppose it is really the UNION ALL that expands…
I need to do a cross product of the above, eliminating the duplicates: the six instances of the interval and itself, e.g. (1,3,1,3) as well as one of (1,3,2,5), (2,5,1,3). That leaves 15 cross product rows. Then taking the smallest of the first coordinate and the largest of the second, (1,3,2,5) => (1,5) for example, and applying the overlap check I would get four rows that look like the original table:
1,5
2,6
9,14
9,14
Then I need to do the cross product, duplicate elimination, etc. on that set of rows.
Continuing until there are a set of intervals with no overlaps. So this recursions needs to result in a smaller number of rows with each go-round.
I’ll include my code in case anyone wants to try it and supply (I hope) an obvious fix that I just can’t see. It is like I need a set difference function rather than union… and outer joins are not allowed.
TIA!
dc
Code follows:
CREATE TABLE TimeIntervals (
t0 int not null,
t1 int not null,
intcnt int not null
)
INSERT INTO TimeIntervals
(t0, t1, intcnt)
VALUES
(1,3,1)
INSERT INTO TimeIntervals
(t0, t1, intcnt)
VALUES
(2,5,1)
INSERT INTO TimeIntervals
(t0, t1, intcnt)
VALUES
(4,6,1)
INSERT INTO TimeIntervals
(t0, t1, intcnt)
VALUES
(9,14,1)
INSERT INTO TimeIntervals
(t0, t1, intcnt)
VALUES
(10,11,1)
INSERT INTO TimeIntervals
(t0, t1, intcnt)
VALUES
(12,13,1)
WITH CollapsedTimeIntervals (t0, t1, intcnt)
AS
(
– Anchor member definition
select CASE WHEN I.t0 I.s1 THEN I.t1 ELSE I.s1 END AS t1,
newIntcnt
from (
select T.t0 AS t0, T.t1 AS t1, S.t0 AS s0, S.t1 AS s1, T.intcnt 1 AS newIntcnt
from TimeIntervals T, TimeIntervals S
where T.t0 != S.t0 and T.t1 != S.t1
and T.t0 = T.t0 AND S.t0 = T.t0 AND S.t1 = S.t0 AND T.t0 = S.t0 AND T.t1 I.s1 THEN I.t1 ELSE I.s1 END AS t1,
newIntcnt
from (
select T.t0 AS t0, T.t1 AS t1, S.t0 AS s0, S.t1 AS s1, T.intcnt 1 AS newIntcnt
from TimeIntervals T, TimeIntervals S
where T.t0 != S.t0 and T.t1 != S.t1
and T.t0 = T.t0 AND S.t0 = T.t0 AND S.t1 = S.t0 AND T.t0 = S.t0 AND T.t1