Recursive query possible in LINQ

Question

This is my first question and a pity for my weak language.

I have a table similar to 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 the menu has many lines,

 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 a second class for preparing a menu tree;

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

I need a linq query to get this result:

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

I use a recursive function to get the children, but it takes too much time to get the results.

How to write a sentence to get the entire menu tree in one query?

UPDATE:

I want to save the main menu in a table. And this table will be used to manage access permissions for users. Some lines will be displayed inside the menu, some of them will only be used to gain access privileges.

In this situation, I need many times to get a table tree. The table tree will be created as filtered user permissions. Upon receipt of the tree stored in the session. but many sessions mean a lot of RAM. If there is a quick way to get the menu tree from sql when I need it, I will not store it in the session.

Answer 1

If you need to go through the whole tree, you must use a stored procedure. Entity Framework is especially bad for recursive relationships. You need to either issue N + 1 queries for each level, or load a specific set of levels. For example, .Include("Childs.Childs.Childs") load three levels. However, this will create a monstrous request, and you still have to issue N + 1 requests for any additional level that you do not include at the beginning.

In SQL, you can use WITH to recursively traverse a table, and it will be much faster than anything the Entity Framework can do. However, your result will be flattened, not the graphic you get from the Entity Framework. For instance:

 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] 

It looks a lot harder than it is. To ensure that the parents arrange the menu items correctly and their position inside this parent tree, we need to create a hierarchical order view for the order. I do this here by creating a line in the form 1.1.1 , where essentially every order of the elements is added to the end of the line of the parent hierarchy. I also use REPLICATE to align the order for each level, so you have no problems with string ordering of numbers where something like 10 precedes 2 because it starts with 1 . The @Pad ad just gets the maximum length I need to fill out based on the highest order number in the table. For example, if the maximum order was something like 123 , then the @Pad value would be 3, so orders less than 123 would still have three characters (i.e. 001 ).

Once you go through all this, the rest of SQL is pretty straight forward. You simply select all the root elements, and then combine them with your whole child, walking through the tree. This is the connection of each new level. Finally, you select from this tree the information you need, sorted by the hierarchy ordering line that we created.

At least for my trees, this query is reasonably fast, but it may be slightly slower than you might like if there is a scale of complexity or there are a ton of menu items you need to deal with. It’s a good idea to do some kind of tree caching, even using this request. Personally, for something like a site navigator, I would recommend using a child action in conjunction with OutputCache . You call a child action in your layout, where the navigator should appear, and it will either launch the action to get the menu, or get the HTML code already created from the cache, if it exists. If the menu is intended for individual users, just make sure that you change differently as you wish, and take into account the user ID or something in your user line. You could also just cache memory as a result of the request itself, but you could also reduce the cost of creating HTML, also when you are on it. However, you should avoid storing it in a session.

Answer 2

LINQ to Entities does not support recursive queries.

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

All you need to do is create the right model and FK relationships:

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

Free configuration:

 modelBuilder.Entity<Menu>() .HasMany(e => e.Children) .WithOptional() .HasForeignKey(e => e.ParentID); 

An important change is that to set up such a relationship, the ParentID must be null and the root elements must use null instead of 0 .

Now, having a model, loading the whole tree is simple:

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

With AsEnumerable() we guarantee that upon execution of the query, the entire table will be retrieved into memory by simple non-recursive SELECT SQL. Then we just filter the root elements.

And it's all. At the end we have a list with root nodes with our children, grandchildren, etc., Populated!

How it works? No lazy, impatient or explicit download is required. All the magic is provided by the DbContext tracking and navigation DbContext .

Answer 3

I will try something like this.

This query will take all menu entries from the database and create a dictionary with ParentId for the key and all menus for the specific parent identifier 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 parentIds and instantiate MyMenu very easily

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

You now have a list with associations. Thus, you will have children and a parent connected by a link (without duplicate links at different levels of nesting). But I wonder how you define the roots, if you need to know them at all? I do not know if this is suitable for you.