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.

Answer 1

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.

Answer 2

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.

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.

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();
 }