How to do a recursive query in Linq2Sql?

Question

I have the following table, MenuItems, in the database:

ID  ParentID  Name
--- --------- -----
1   0         Item 1
2   1         Item 2
3   1         Item 3
4   0         Item 4
5   3         Item 5

I want to write an extension method to get all menu items to the root of the tree. Something like this:

public IQueryable<MenuItem> GetToRoot(this IQueryable<MenuItem> source, int menuItemID)
{
    return from m in source
           ????
           ????
           select m;
}

If I call this extension method with the data above for the menu item with ID 3, I should get:

ID  ParentID  Name
--- --------- -----
1   0         Item 1
3   1         Item 3

Is this possible with Linq2Sql with only one call to the database?

Answer 1

I don't think you'll be able to do it in a single query, and here's my thinking: discovering an item's parent effectively requires one join of the table with itself. Each additional menu level requires one more join of the table with itself. How many joins/additional levels will you need to reach the root? You won't know until you perform each one, right? So, whether on the database/SQL side or in LINQ to SQL, you'll have to take each step one at a time.

If you know your menu system won't go beyond a certain depth, I suppose you could set up a LINQ to SQL query that joins the table with itself that number of times, but that sounds ugly.

What I would suggest is setting up an association of the table with itself in your DBML designer, that would give you a parent EntityRef<> property on the class. Since cycles are not allowed in your LoadOptions (and therefore the parent cannot be pre-loaded), you could force the lazy load of the parent in the entity's partial OnLoaded() method.

Here are some relevant SO questions:

http://stackoverflow.com/questions/1435229/hierarchy-problem-replace-recursion-with-linq-join http://stackoverflow.com/questions/43111/linq-to-sql-for-self-referencing-tables

Here is a server-side/SQL treatment of the problem:

http://www.sqlteam.com/article/more-trees-hierarchies-in-sql

Here is someone who has written some helper code:

http://www.scip.be/index.php?Page=ArticlesNET18