Is recursive query possible in LINQ to Entities

Question

this is my first question and sorry about my weak language.

I've got a table like this model;

 public class Menu
 {
      [Key]
      public int ID {get;set;}
      public int ParentID {get;set;}
      public string MenuName {get;set;}
      public int OrderNo {get;set;}
      public bool isDisplayInMenu {get;set;} // Menu or just for Access Authority
 }

and there are many rows about menu like this;

ID     ParentID      MenuName          Order
---    ---------     -------------     ------
1      0             Main.1               1     >> if ParentID==0 is Root
2      1             Sub.1.1              1
3      2             Sub.1.2              2
4      0             Main.2               2
5      4             Sub.2.1              1
6      4             Sub.2.2              2

I have got a second class to prepare menu tree;

public class MyMenu:Menu
{
    public List<MyMenu> Childs { get;set;}
}

I need a linq query to get the result like this;

var result = (...linq..).ToList<MyMenu>();

I am using a recursive function to get childs but this take too much time for to get results.

How can I write a sentence to get all menu tree in one query?

UPDATE:

I want to store main menu in a table. And this table will use on access authority control for users. Some rows will display inside the menu, some ones will use only to get access authority.

In this situation, I need many times to get the table tree. The table tree will be created as the filtered user authorities. When get the tree, stored in session. but many sessions means much RAM. If is there any fast way to get menu tree from the sql when I need then I will not store in the session.

Sit

LINQ query is too broad. Are you talking about EF? Please update the post and tags accordingly. – Truant

The Menu entity should have a so called 'navigation property' to it's parent and children. I would also think that the ParentID member should be nullable (since there has to be one root Menu). Have a look at this: msdn.microsoft.com/en-us/library/jj713564(v=vs.113).aspx – Rutledge

LINQ to Entities does not support recursive queries. If you need to load the whole tree and can setup FK relationship (which would require ParentID to be int? and for root items to be null instead of 0), then you can use something like this. Otherwise you have to execute multiple queries. The main question is if you need the whole tree or the subtree based on some criteria. So please clarify your requirements and show what you have done. – Truant

Thank you for FK relationship advice. I never user relationships before. I will check your other answer link about nullable integer parentIDs. – Sit

Answer 1

LINQ to Entities does not support recursive queries.

However, loading the whole tree stored in a database table is easy and efficient. There seem to be some myths from earlier version of Entity Framework, so let's demystify them.

All you need is to create a proper model and FK relationship:

Model:

public class Menu
{
    public int ID { get; set; }
    public int? ParentID { get; set; }
    public string MenuName { get; set; }
    public int OrderNo { get; set; }
    public bool isDisplayInMenu { get; set; }

    public ICollection<Menu> Children { get; set; }
}

Fluent configuration:

modelBuilder.Entity<Menu>()
    .HasMany(e => e.Children)
    .WithOptional() // EF6
    .WithOne() // EF Core
    .HasForeignKey(e => e.ParentID);

The important change is that in order to setup such relationship, ParentID must be nullable, and root items should use null instead of 0.

Now, having the model, loading the whole tree is simple as that:

var tree = db.Menu.AsEnumerable().Where(e => e.ParentID == null).ToList();

With AsEnumerable() we ensure that when the query is executed, the whole table will be retrieved in memory with a simple non recursive SELECT SQL. Then we simply filter out the root items.

And that's all. At the end we have a list with root nodes with their children, grand children etc. populated!

How it works? No lazy, eager or explicit loading is needed/used. The whole magic is provided by the DbContext tracking and navigation property fix up system.

Truant

Nice.I'd like to emphasize that this is suitable for relatively small tables. I think these myths have to do with large hierarchies, or hierarchies of which only some specific levels should be queried. That will never be nearly as elegant with LINQ to E. Still, people keep asking for the one-liner statement doing it. – Grossularite

Answer 2

If you need to walk the entire tree, you should use a stored procedure. Entity Framework is particularly ill-suited for recursive relationships. You'll either need to issue N+1 queries for each level, or eagerly load a defined set of levels. For example, .Include("Childs.Childs.Childs"), would load three levels. However, this is going to create a monstrous query, and you'll still need to issue N+1 queries for any additional level you don't include at the start.

In SQL, you can use WITH to recursively walk the table, and it will be much quicker than anything Entity Framework can do. However, your result will be flattened, rather than the object graph you would get back from Entity Framework. For example:

DECLARE @Pad INT = (
    SELECT MAX([Length])
    FROM (
        SELECT LEN([Order]) AS [Length] FROM [dbo].[Menus]
    ) x
);

WITH Tree ([Id], [ParentId], [Name], [Hierarchy]) AS
(
    SELECT
        [ID],
        [ParentID],
        [MenuName],
        REPLICATE('0', @Pad - LEN([Order])) + CAST([Order] AS NVARCHAR(MAX))
    FROM [dbo].[Menus]
    WHERE [ParentID] = 0 -- root
    UNION ALL
        SELECT
            Children.[ID],
            Children.[ParentID],
            Children.[MenuName],
            Parent.[Hierarchy] + '.' + REPLICATE('0', @Pad - LEN(Children.[Order])) + CAST(Children.[Order] AS NVARCHAR(MAX)) AS [Hierarchy]
        FROM [dbo].[Menus] Children
        INNER JOIN Tree AS Parent
            ON Parent.[ID] = Children.[ParentID]
)
SELECT
    [ID],
    [ParentID],
    [MenuName]
FROM Tree
ORDER BY [Hierarchy]

That looks much more complicated than it is. In order to ensure that the items in the menu are ordered properly by parent and their position within that parent's tree, we need to create a hierarchical representation of the order to order by. I'm doing that here by creating a string in the form of 1.1.1, where essentially each item's order is appended to the end of the parent's hierarchy string. I'm also using REPLICATE to left-pad the order for each level, so you don't have issues common with string ordering of numbers, where something like 10 comes before 2, because it starts with 1. The @Pad declaration just gets the max length I need to pad based on the highest order number in the table. For example, if the max order was something like 123, then the value of @Pad would be 3, so that orders less than 123 would still be three characters (i.e. 001).

Once you get past all that, the rest of the SQL is pretty straight-forward. You simply select all the root items and then union all with all their child by walking the tree. This and joining in each new level. Finally, you select from this tree the information you need, ordered by the hierarchy ordering string we created.

At least for my trees, this query is acceptably quick, but could be somewhat slower than you might like if the complexity scales or there's a ton of menu items to deal with. It's not a bad idea to do some sort of caching of the tree, even with using this query. Personally, for something like a site nav, I'd recommend using a child action combined with OutputCache. You call the child action in your layout where the nav should appear, and it will either run the action to get the menu or retrieve the already created HTML from cache if it exists. If the menu is specific to individual users, then just make sure you vary by custom, and factor in the user's id or something in your custom string. You could also just memory cache the result of the query itself, but you might as well reduce the cost of generating the HTML, too, while your at it. However, storing it in the session should be avoided.

Continuation

I don't know why the people continue claiming that Include has to contain multiple levels and will eagerly load only that levels. When retrieving the whole tree (table), using Include("Childs") is enough and will load all levels correctly using a relatively simple SQL (single self left outer join). Of course the same can easily be achieved w/o Include in memory. Using raw SQL defeats the purpose of EF. – Truant

That's flat out wrong. EF does not recursively query and if it did, it would take a similar query to what I posted, i.e. using WITH. A single join would not load all the levels. – Continuation

Guaranteed to work :) Relationship fixup does the necessary work to link the materialized query result. Still less efficient then doing it manually though. – Truant

Sorry, but again, that's simply not the case. A single inner join will only bring in a single level. You're likely just relying on the lazy loading and not realizing additional queries are being issues each level you traverse. – Continuation

Nevermind. I'm absolutely sure what I'm talking about because I don't use lazy loading (have no virtual properties, ProxyCreationEnabled and LazyLoadingEnabled are both set to false). It's the eager loading which does the trick with the help of the context tracking services and navigation property fixup feature. All this applies to the latest EF6.1.3 (it might been different in earlier versions), and also in current EF Core which has no lazy loading at all. – Truant

Ah. I think I've figured out the confusion. Looks like EF core has added support for hierarchyid. This feature of SQL Server allows easy relational hierarchies but was never previously supported in EF. If you're using EF Core, then want you're saying may be true, but it absolutely will not work in EF6 or less. – Continuation

Dear Seniors, both of you, that you live thing is my dreams :) Thank you so much to both of you and your sharings. These have been illuminated me so much! – Sit

@ChrisPratt Thanks to our little discussion, I've realized that no Include is needed at all. – Truant

Answer 3

I will try something like this.

This query will take all menu records from the database and will create dictionary with ParentId for key and all menus for specific parent id as values.

// if you're pulling the data from database with EF
var map = (from menu in ctx.Menus.AsNoTracking()
           group by menu.ParentId into g
           select g).ToDictionary(x => x.Key, x => x.ToList());

Now we can iterate the parentIds and create MyMenu instances very easly

var menusWithChildren = new List<MyMenu>()
foreach(var parentId in map.Keys)
{
   var menuWithChildren = new MyMenu { ... }
   menuWithChildren.AddRange(map[parentId]);
}

Now you have list with the associations. This way you will have the children and parent associated by reference (no dublicate references across different nesting levels) But i wonder how do you define the roots, if you need to know them at all ? I don't know if this is suitable for you.

Fetor

which parent ID equal 0 are the root elements. In my function like this; public List<MyMenu> getMenu(List<MyMenu> allMenuElements, int ParentID) and I call this function first getMenu(allMenuElements, 0). In the function; for each parent element call same function again for their childs. – Sit

I am curious about that is there a way to get list inside the query? – Sit

Also thank you rest your time for me and thank you again about "AsNoTracking" tip. I learned a new thing :) – Sit

With the current structure of your EF models i am not very sure. But for alternative check @ivanstoev comment of your post. – Fetor

Answer 4

public class Menu
{
    public int ID { get; set; }
    public int? ParentID { get; set; }
    public string MenuName { get; set; }
    public int OrderNo { get; set; }
    public bool isDisplayInMenu { get; set; }
    public Menu Parent { get; set; }
    public ICollection<Menu> Children { get; set; }
}

menuConfiguration:

builder.HasMany(z => z.Children).WithOne(z => z.Parent).HasForeignKey(z => z.ParentId).OnDelete(DeleteBehavior.Cascade);

MenuService:

public Task<List<Menu>> GetListByChildren()
{
   return _dbSet.AsNoTracking().Include(z => z.Children).Where(z => z.ParentId == null).ToListAsync();
 }

Obtrusive

Answer 5

I have used a recursive function to solve this problem.

 namespace Microsoft.EntityFrameworkCore
{
    public static class DbSetExtensions
    {   
        public static List<TEntity> FindRecursive<TEntity, TKey>(
            this DbSet<TEntity> source,
            Expression<Func<TEntity, bool>> rootPredicate,
            Expression<Func<TEntity, TKey>> rootKey,
            Expression<Func<TEntity, TKey?>> childKey)
            where TEntity : class
            where TKey : struct
        {
            var roots = source.Where(rootPredicate).ToList();
            var result = new List<TEntity>();
            result.AddRange(roots);

            var rootIds = roots.Select(rootKey.Compile()).ToList();
            foreach (var id in rootIds)
            {
                var childPredicate = BuildPredicate(childKey, id);
                result.AddRange(FindRecursive1(source, childPredicate, rootKey, childKey));
            }
            return result;
        }

        private static Expression<Func<TEntity, bool>> BuildPredicate<TEntity, TKey>(Expression<Func<TEntity, TKey?>> keySelector, TKey value)
            where TEntity : class
            where TKey : struct
        {
            var parameter = Expression.Parameter(typeof(TEntity), "x");
            var left = Expression.Invoke(keySelector, parameter);
            var right = Expression.Constant(value, typeof(TKey?));
            var body = Expression.Equal(left, right);
            return Expression.Lambda<Func<TEntity, bool>>(body, parameter);
        }
    }
}

And for usage :

var recursiveData = DataContext.SomeEntity.FindRecursive(
  rootPredicate: x => x.Id = 50,
  rootKey: x => x.Id,
  childKey: x => x.ParentId);

Dezhnev