Método más eficiente de autorreferencia de árbol utilizando Entity Framework

Entonces tengo una tabla SQL que es básicamente

ID, ParentID, MenuName, [Lineage, Depth] 

Las dos últimas columnas se calculan automáticamente para ayudar con la búsqueda, por lo que podemos ignorarlas por el momento.

Estoy creando un sistema de menú desplegable con múltiples categorías.

Lamentablemente, EF no creo que juegue bien con las tablas de autorreferencia de más de 1 nivel de profundidad. Así que me quedan algunas opciones

1) Cree una consulta, ordene por profundidad y luego cree una clase personalizada en C #, llenándola una profundidad a la vez.

2) Encontrar alguna manera de cargar los datos con entusiasmo en EF, no creo que sea posible para una cantidad ilimitada de niveles, solo una cantidad fija.

3) De alguna otra manera ni siquiera estoy seguro.

Cualquier entrada sería bienvenida!

He correlacionado con éxito los datos jerárquicos usando EF.

Tomemos por ejemplo una entidad de Establishment . Esto puede representar a una empresa, universidad u otra unidad dentro de una estructura organizacional más grande:

 public class Establishment : Entity { public string Name { get; set; } public virtual Establishment Parent { get; set; } public virtual ICollection Children { get; set; } ... } 

Así es como se mapean las propiedades de padres / hijos. De esta forma, cuando configura la entidad principal de 1, la colección Niños de la entidad principal se actualiza automáticamente:

 // ParentEstablishment 0..1 <---> * ChildEstablishment HasOptional(d => d.Parent) .WithMany(p => p.Children) .Map(d => d.MapKey("ParentId")) .WillCascadeOnDelete(false); // do not delete children when parent is deleted 

Tenga en cuenta que hasta ahora no he incluido sus propiedades de linaje o profundidad. Tiene razón, EF no funciona bien para generar consultas jerárquicas anidadas con las relaciones anteriores. Lo que finalmente decidí fue la adición de una nueva entidad de gerundio, junto con 2 nuevas propiedades de entidad:

 public class EstablishmentNode : Entity { public int AncestorId { get; set; } public virtual Establishment Ancestor { get; set; } public int OffspringId { get; set; } public virtual Establishment Offspring { get; set; } public int Separation { get; set; } } public class Establishment : Entity { ... public virtual ICollection Ancestors { get; set; } public virtual ICollection Offspring { get; set; } } 

Mientras escribía esto, hazzik publicó una respuesta que es muy similar a este enfoque . Sin embargo, seguiré escribiendo para ofrecer una alternativa ligeramente diferente. Me gusta hacer tipos de entidades reales de mis antepasados ​​y descendientes porque me ayudan a obtener la separación entre el antepasado y el descendiente (lo que tú llamas profundidad). Así es como tracé estos mapas:

 private class EstablishmentNodeOrm : EntityTypeConfiguration { internal EstablishmentNodeOrm() { ToTable(typeof(EstablishmentNode).Name); HasKey(p => new { p.AncestorId, p.OffspringId }); } } 

… y finalmente, las relaciones de identificación en la entidad del establecimiento:

 // has many ancestors HasMany(p => p.Ancestors) .WithRequired(d => d.Offspring) .HasForeignKey(d => d.OffspringId) .WillCascadeOnDelete(false); // has many offspring HasMany(p => p.Offspring) .WithRequired(d => d.Ancestor) .HasForeignKey(d => d.AncestorId) .WillCascadeOnDelete(false); 

Además, no usé un sproc para actualizar las asignaciones de nodos. En su lugar, tenemos un conjunto de comandos internos que derivarán / calcularán las propiedades Ancestros y Descendientes basadas en las propiedades para padres e hijos. Sin embargo, en última instancia, terminas pudiendo hacer consultas muy similares a las de la respuesta de hazzik:

 // load the entity along with all of its offspring var establishment = dbContext.Establishments .Include(x => x.Offspring.Select(y => e.Offspring)) .SingleOrDefault(x => x.Id == id); 

El motivo de la entidad puente entre la entidad principal y sus Ancestros / Descendientes es nuevamente porque esta entidad le permite obtener la Separación. Además, al declararlo como una relación de identificación, puede eliminar nodos de la colección sin tener que llamar explícitamente a DbContext.Delete () en ellos.

 // load all entities that are more than 3 levels deep var establishments = dbContext.Establishments .Where(x => x.Ancestors.Any(y => y.Separation > 3)); 

Puede usar la tabla de jerarquía de soporte para realizar una carga ansiosa de niveles de árbol ilimitados.

Por lo tanto, debe agregar dos colecciones Ancestors y Descendants , ambas colecciones se deben mapear como muchas a muchas tablas de apoyo.

 public class Tree { public virtual Tree Parent { get; set; } public virtual ICollection Children { get; set; } public virtual ICollection Ancestors { get; set; } public virtual ICollection Descendants { get; set; } } 

Los antepasados ​​contendrán todos los antepasados ​​(padres, abuelos, abuelos, etc.) de la entidad y los Descendants incluirán a todos los descendientes (hijos, nietos, bisnietos, etc.) de la entidad.

Ahora debe mapearlo con el código EF primero:

 public class TreeConfiguration : EntityTypeConfiguration { public TreeConfiguration() { HasOptional(x => x.Parent) .WithMany(x => x.Children) .Map(m => m.MapKey("PARENT_ID")); HasMany(x => x.Children) .WithOptional(x => x.Parent); HasMany(x => x.Ancestors) .WithMany(x => x.Descendants) .Map(m => m.ToTable("Tree_Hierarchy").MapLeftKey("PARENT_ID").MapRightKey("CHILD_ID")); HasMany(x => x.Descendants) .WithMany(x => x.Ancestors) .Map(m => m.ToTable("Tree_Hierarchy").MapLeftKey("CHILD_ID").MapRightKey("PARENT_ID")); } } 

Ahora con esta estructura puedes hacer búsquedas ansiosas como seguir

 context.Trees.Include(x => x.Descendants).Where(x => x.Id == id).SingleOrDefault() 

Esta consulta cargará entidad con id y todos sus descendientes.

Puede completar la tabla de soporte con el siguiente procedimiento almacenado:

 CREATE PROCEDURE [dbo].[FillHierarchy] (@table_name nvarchar(MAX), @hierarchy_name nvarchar(MAX)) AS BEGIN DECLARE @sql nvarchar(MAX), @id_column_name nvarchar(MAX) SET @id_column_name = '[' + @table_name + '_ID]' SET @table_name = '[' + @table_name + ']' SET @hierarchy_name = '[' + @hierarchy_name + ']' SET @sql = '' SET @sql = @sql + 'WITH Hierachy(CHILD_ID, PARENT_ID) AS ( ' SET @sql = @sql + 'SELECT ' + @id_column_name + ', [PARENT_ID] FROM ' + @table_name + ' e ' SET @sql = @sql + 'UNION ALL ' SET @sql = @sql + 'SELECT e.' + @id_column_name + ', e.[PARENT_ID] FROM ' + @table_name + ' e ' SET @sql = @sql + 'INNER JOIN Hierachy eh ON e.' + @id_column_name + ' = eh.[PARENT_ID]) ' SET @sql = @sql + 'INSERT INTO ' + @hierarchy_name + ' ([CHILD_ID], [PARENT_ID]) ( ' SET @sql = @sql + 'SELECT [CHILD_ID], [PARENT_ID] FROM Hierachy WHERE [PARENT_ID] IS NOT NULL ' SET @sql = @sql + ') ' EXECUTE (@sql) END GO 

O incluso podría asignar la tabla de apoyo a una vista:

 CREATE VIEW [Tree_Hierarchy] AS WITH Hierachy (CHILD_ID, PARENT_ID) AS ( SELECT [MySuperTree_ID], [PARENT_ID] FROM [MySuperTree] AS e UNION ALL SELECT e.[MySuperTree_ID], e.[PARENT_ID] FROM [MySuperTree] AS e INNER JOIN Hierachy AS eh ON e.[MySuperTree_ID] = eh.[PARENT_ID] ) SELECT [CHILD_ID], [PARENT_ID] FROM Hierachy WHERE [PARENT_ID] IS NOT NULL GO 

Ya pasé un tiempo tratando de arreglar un error en tu solución. El procedimiento almacenado realmente no genera hijos, nietos, etc. A continuación encontrará el procedimiento almacenado fijo:

 CREATE PROCEDURE dbo.UpdateHierarchy AS BEGIN DECLARE @sql nvarchar(MAX) SET @sql = '' SET @sql = @sql + 'WITH Hierachy(ChildId, ParentId) AS ( ' SET @sql = @sql + 'SELECT t.Id, t.ParentId FROM dbo.Tree t ' SET @sql = @sql + 'UNION ALL ' SET @sql = @sql + 'SELECT h.ChildId, t.ParentId FROM dbo.Tree t ' SET @sql = @sql + 'INNER JOIN Hierachy h ON t.Id = h.ParentId) ' SET @sql = @sql + 'INSERT INTO dbo.TreeHierarchy (ChildId, ParentId) ( ' SET @sql = @sql + 'SELECT DISTINCT ChildId, ParentId FROM Hierachy WHERE ParentId IS NOT NULL ' SET @sql = @sql + 'EXCEPT SELECT t.ChildId, t.ParentId FROM dbo.TreeHierarchy t ' SET @sql = @sql + ') ' EXECUTE (@sql) END 

Error: referencia incorrecta. Traduciendo el código de @hazzik era:

  SET @sql = @sql + 'SELECT t.ChildId, t.ParentId FROM dbo.Tree t ' 

pero debería ser

  SET @sql = @sql + 'SELECT h.ChildId, t.ParentId FROM dbo.Tree t ' 

También agregué un código que le permite actualizar la tabla TreeHierarchy no solo cuando la rellene.

  SET @sql = @sql + 'EXCEPT SELECT t.ChildId, t.ParentId FROM dbo.TreeHierarchy t ' 

Y la magia. Este procedimiento o más bien TreeHierarchy le permite cargar a los Hijos simplemente incluyendo Ancestros (no Hijos ni Descendientes).

  using (var context = new YourDbContext()) { rootNode = context.Tree .Include(x => x.Ancestors) .SingleOrDefault(x => x.Id == id); } 

Ahora YourDbContext devolverá un rootNode con hijos cargados, hijos de hijos de rootName (nietos), y así sucesivamente.

Sabía que debe haber algo mal con esta solución. No es simple Usando esta solución, EF6 requiere otro paquete de hacks para administrar un árbol simple (eliminaciones). Así que finalmente encontré una solución simple pero combinada con este enfoque.

En primer lugar, deje la entidad simple: solo los padres y la lista de hijos es suficiente. También el mapeo debería ser simple:

  HasOptional(x => x.Parent) .WithMany(x => x.Children) .Map(m => m.MapKey("ParentId")); HasMany(x => x.Children) .WithOptional(x => x.Parent); 

A continuación, agregue la migración (primero el código: migrations: package console: Add-Migration Hierarchy) o de otra manera un procedimiento almacenado:

 CREATE PROCEDURE [dbo].[Tree_GetChildren] (@Id int) AS BEGIN WITH Hierachy(ChildId, ParentId) AS ( SELECT ts.Id, ts.ParentId FROM med.MedicalTestSteps ts UNION ALL SELECT h.ChildId, ts.ParentId FROM med.MedicalTestSteps ts INNER JOIN Hierachy h ON ts.Id = h.ParentId ) SELECT h.ChildId FROM Hierachy h WHERE h.ParentId = @Id END 

Luego, cuando intente recibir sus nodos de árbol de la base de datos, solo hágalo en dos pasos:

 //Get children IDs var sql = $"EXEC Tree_GetChildren {rootNodeId}"; var children = context.Database.SqlQuery(sql).ToList(); //Get root node and all it's children var rootNode = _context.TreeNodes .Include(s => s.Children) .Where(s => s.Id == id || children.Any(c => s.Id == c)) .ToList() //MUST - get all children from database then get root .FirstOrDefault(s => s.Id == id); 

Todo. Esta consulta lo ayuda a obtener un nodo raíz y cargar todos los elementos secundarios. Sin jugar con la introducción de Ancestros y Descendientes.

Recuerde también que cuando intente guardar un subnodo, hágalo de esta manera:

 var node = new Node { ParentId = rootNode }; //Or null, if you want node become a root context.TreeNodess.Add(node); context.SaveChanges(); 

Hazlo de esa manera, no agregando hijos al nodo raíz.

Otra opción de implementación en la que he trabajado recientemente …

Mi árbol es muy simple.

 public class Node { public int NodeID { get; set; } public string Name { get; set; } public virtual Node ParentNode { get; set; } public int? ParentNodeID { get; set; } public virtual ICollection ChildNodes { get; set; } public int? LeafID { get; set; } public virtual Leaf Leaf { get; set; } } public class Leaf { public int LeafID { get; set; } public string Name { get; set; } public virtual ICollection Nodes { get; set; } } 

Mis requisitos, no tanto.

Dado un conjunto de hojas y un único antepasado, muestre a los hijos de ese antepasado que tienen descendientes que tienen hojas dentro del conjunto

Una analogía sería una estructura de archivos en el disco. El usuario actual tiene acceso a un subconjunto de archivos en el sistema. A medida que el usuario abre nodos en el árbol del sistema de archivos, solo queremos mostrar los nodos de usuario que, finalmente, los conducirán a los archivos que pueden ver. No queremos mostrarles rutas de archivos a archivos a los que no tienen acceso (por razones de seguridad, por ejemplo, filtrar la existencia de un documento de cierto tipo).

Queremos poder express este filtro como IQueryable , por lo que podemos aplicarlo a cualquier consulta de nodo, filtrando los resultados no deseados.

Para hacer esto, creé una función de valor de tabla que devuelve los descendientes para un nodo en el árbol. Lo hace a través de un CTE.

 CREATE FUNCTION [dbo].[DescendantsOf] ( @parentId int ) RETURNS TABLE AS RETURN ( WITH descendants (NodeID, ParentNodeID, LeafID) AS( SELECT NodeID, ParentNodeID, LeafID from Nodes where ParentNodeID = @parentId UNION ALL SELECT n.NodeID, n.ParentNodeID, n.LeafID from Nodes n inner join descendants d on n.ParentNodeID = d.NodeID ) SELECT * from descendants ) 

Ahora, estoy usando Code First, así que tuve que usar

https://www.nuget.org/packages/EntityFramework.Functions

para agregar la función a mi DbContext

 [TableValuedFunction("DescendantsOf", "Database", Schema = "dbo")] public IQueryable DescendantsOf(int parentID) { var param = new ObjectParameter("parentId", parentID); return this.ObjectContext().CreateQuery("[DescendantsOf](@parentId)", param); } 

con un tipo de retorno complejo (no se pudo reutilizar el nodo, investigando eso)

 [ComplexType] public class NodeDescendant { public int NodeID { get; set; } public int LeafID { get; set; } } 

Poner todo junto me permitió, cuando el usuario expande un nodo en el árbol, obtener la lista filtrada de nodos secundarios.

 public static Node[] GetVisibleDescendants(int parentId) { using (var db = new Models.Database()) { int[] visibleLeaves = SuperSecretResourceManager.GetLeavesForCurrentUserLol(); var targetQuery = db.Nodes as IQueryable; targetQuery = targetQuery.Where(node => node.ParentNodeID == parentId && db.DescendantsOf(node.NodeID).Any(x => visibleLeaves.Any(y => x.LeafID == y))); // Notice, still an IQueryable. Perform whatever processing is required. SortByCurrentUsersSavedSettings(targetQuery); return targetQuery.ToArray(); } } 

Es importante tener en cuenta que la función se ejecuta en el servidor, no en la aplicación . Aquí está la consulta que se ejecuta

 SELECT [Extent1].[NodeID] AS [NodeID], [Extent1].[Name] AS [Name], [Extent1].[ParentNodeID] AS [ParentNodeID], [Extent1].[LeafID] AS [LeafID] FROM [dbo].[Nodes] AS [Extent1] WHERE ([Extent1].[ParentNodeID] = @p__linq__0) AND ( EXISTS (SELECT 1 AS [C1] FROM ( SELECT [Extent2].[LeafID] AS [LeafID] FROM [dbo].[DescendantsOf]([Extent1].[NodeID]) AS [Extent2] ) AS [Project1] WHERE EXISTS (SELECT 1 AS [C1] FROM ( SELECT 1 AS X ) AS [SingleRowTable1] WHERE [Project1].[LeafID] = 17 ) )) 

Tenga en cuenta la llamada de función dentro de la consulta anterior.

@danludwig gracias por tu respuesta

Escribo alguna función para Nodo de actualización, Funciona perfecto. ¿Mi código es bueno o debo escribirlo de otra manera?

  public void Handle(ParentChanged e) { var categoryGuid = e.CategoryId.Id; var category = _context.Categories .Include(cat => cat.ParentCategory) .First(cat => cat.Id == categoryGuid); if (null != e.OldParentCategoryId) { var oldParentCategoryGuid = e.OldParentCategoryId.Id; if (category.ParentCategory.Id == oldParentCategoryGuid) { throw new Exception("Old Parent Category mismatch."); } } (_context as DbContext).Configuration.LazyLoadingEnabled = true; RemoveFromAncestors(category, category.ParentCategory); var newParentCategoryGuid = e.NewParentCategoryId.Id; var parentCategory = _context.Categories .First(cat => cat.Id == newParentCategoryGuid); category.ParentCategory = parentCategory; AddToAncestors(category, category.ParentCategory, 1); _context.Commit(); } private static void RemoveFromAncestors(Model.Category.Category mainCategory, Model.Category.Category ancestorCategory) { if (null == ancestorCategory) { return; } while (true) { var offspring = ancestorCategory.Offspring; offspring?.RemoveAll(node => node.OffspringId == mainCategory.Id); if (null != ancestorCategory.ParentCategory) { ancestorCategory = ancestorCategory.ParentCategory; continue; } break; } } private static int AddToAncestors(Model.Category.Category mainCategory, Model.Category.Category ancestorCategory, int deep) { var offspring = ancestorCategory.Offspring ?? new List(); if (null == ancestorCategory.Ancestors) { ancestorCategory.Ancestors = new List(); } var node = new CategoryNode() { Ancestor = ancestorCategory, Offspring = mainCategory }; offspring.Add(node); if (null != ancestorCategory.ParentCategory) { deep = AddToAncestors(mainCategory, ancestorCategory.ParentCategory, deep + 1); } node.Separation = deep; return deep; }