> Not sure if recursive is the right word, but here's the situation:
Hierarchical fetches, tree-fetches, nested set model queries etc. it
has a truckload of names ;)
> Using AdventureWorks, LINQPad, and the Employee table.
>
> An Employee has a ManagerID column. If the value is NULL then that Employee
> has no manager.
>
> What I want to do is select the top-level employee, his/her subordinates,
and
> for each of those their subordinates, and so on.
It's the typical textbook example of how to store a tree-based
structure in a single table. It's also the most inefficient way to do it, but
you can't do a thing about that of course, as it's not your db.
The main drawback is, as you've found out, that you can't retrieve a
hierarchy or part of the hierarchy in a single query, you need 1 query per
tree-level.
In the case you run into this again and you DO control the db schema,
you can take two different approaches.
1) use a 'precalc' table for the hierarchy, which is kept up to date with a
trigger. This comes down to querying the precalc table together with the real
table and you get any part of the hierarchy in 1 query. I explain it here with
sample code:
http://www.llblgen.com/tinyforum/GotoMessage.aspx?MessageID=17746&ThreadID=320
8
2) use the nested set model described by Celko. Use this link:
http://groups.google.com/group/microsoft.public.sqlserver.programming/browse_f
rm/thread/a0971b548a1daa06/d94afd1d56858df4?q=tree
Ok, back to your problem at hand, where you have to deal with a table
which contains a complete hierarchy.
> Var query = from mgr in Employees
> Where mgr.ManagerID == null
> Select new
> {
> Title = mgr.Title,
> Subordinates = from person
in
> Employees
>
> Where person.ManagerID = mgr.EmployeeID
>
> Select new { Title = person.Title }
> };
>
>
> This gets me one level deep. But I'd like to see how it can be written to
go
> deeper until eventually I arrive at an Employee who no subordinate.
>
> Hope that makes sense and looking forward to any info.
This approach will of course not scale. If you add a hierarchy level
to the tree, you have to adjust all your queries.
So it's better to take a different approach. This uses an ~O(2n)
algorithm to construct the tree in-memory, from a flat list. ( O(2n) worse
case)
First, simply fetch the employees in full:
var q = from e in ctx.Employees select e;
We'll now build the tree. Let's assume there are more top-level managers, so
we'll add any top level manager to a list:
HashSet<Employee> roots = new HashSet<Employee>();
We'll need an ID -> Employee lookup index, so we'll create a Dictionary on the
fly:
Dictionary<int, Employee> idToEmployee = new Dictionary<int, Employee>();
At this point, we're set to build the tree. We'll simply traverse the
employees we've fetched and build the tree along the way. We need a list of
employees we can't add to a manager yet. This is the reason the algorithm is
O(2n) and not O(n). With sorting it can be made more efficient.
List<Employee> orphanedEmployees = new List<Employee>();
// build the tree
BuildTree(q, idToEmployee, roots, orphanedEmployees);
Here is the routine which builds the tree
// traverse the employees, build the tree along the way.
public void BuildTree(IEnumerable<Employee> toTraverse,
Dictionary<int, Employee> idToEmployee,
HashSet<Employee> roots,
List<Employee> orphanedEmployees)
{
foreach(Employee e in toTraverse)
{
// always first add the employee to the lookup dictionary
idToEmployee[e.EmployeeID] = e;
if(!e.ManagerID.HasValue)
{
// has no manager, is root
roots.Add(e);
continue;
}
Employee manager = null;
if(idToEmployee.TryGetValue(e.ManagerID.Value, out manager))
{
// manager found
e.Manager = manager;
}
else
{
// manager is not yet seen, add to orphaned list
orphanedEmployees.Add(e);
}
}
// it could be the order in which the employees were stored in the
list
// to traverse was suboptimal (i.e. managers were stored after the
employees) // we therefore traverse the orphaned list once
BuildTree(orphanedEmployees, idToEmployee, roots, new
List<Employee>());
}
Not tested, written down from memory.
Frans
------------------------------------------------------------------------
Lead developer of LLBLGen Pro, the productive O/R mapper for .NET
LLBLGen Pro website: http://www.llblgen.com
My .NET blog: http://weblogs.asp.net/fbouma
Microsoft MVP (C#)
------------------------------------------------------------------------
===================================
This list is hosted by DevelopMentor® http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com
