Walking a hierarchy table with Linq

Question

I have a table with two columns, GroupId and ParentId (both are GUIDS). The table forms a hierarchy so I can look for a value in the “GroupId” filed, when I have found it I can look at its ParentId. This ParentId will also appear in the GroupId of a different record. I can use this to walk up the hierarchy tree from any point to the root (root is an empty GUID). What I’d like to do is get a list of records when I know a GroupId. This would be the record with the GroupId and all the parents back to the root record. Is this possible with Linq and if so, can anyone provide a code snippet?

Answer 1

It's definitely possible with Linq, but you'd have to make a DB call for each level in the heirarchy. Not exactly optimal.

Answer 2

LINQ is not designed to handle recursive selection.

It is certainly possible to write your own extension method to compensate for that in LINQ to Objects, but I've found that LINQ to Entities does not like functionality not easily translated into SQL.

Edit: Funnily enough, LINQ to Entities does not complain about Matt Warren's take on recursion using LINQ here. You could do:

var result = db.Table.Where(item => item.GroupId == 5)
                     .Traverse(item => db.Table.Where(parent 
                                                       => item.ParentId == parent.GroupId));

using the extension method defined here:

static class LinqExtensions
{
    public static IEnumerable<T> Traverse<T>(this IEnumerable<T> source,
                                             Func<T,IEnumerable<T>> selector){
    foreach(T item in source){
        yield return item;
        IEnumerable<T> children = selector(item);
        foreach (T child in children.Traverse(selector))
        {
            yield return child;
        }
    }
}

Performace might be poor, though.

Answer 3

The other respondents are right - performance is going to be pretty bad on this, since you'll have to make multiple round-trips. This will be somewhat dependent on your particular case, however - is your tree deep and will be people be performing this operation often, for instance.

You may be well served by creating a stored procedure that does this (using a CTE), and wiring it up in the Entities Designer to return your particularly defined Entity.