C# 使用实体框架自引用树的最有效方法

Most efficient method of self referencing tree using Entity Framework

提问by John Mitchell

So I have a SQL table which is basically

所以我有一个 SQL 表，它基本上是

ID, ParentID, MenuName, [Lineage, Depth]

The last two columns are auto-computed to help with searching so we can ignore them for now.

最后两列是自动计算的以帮助搜索，因此我们现在可以忽略它们。

I'm creating a drop down menu system with multiple categories.

我正在创建一个具有多个类别的下拉菜单系统。

Unfortunately EF I don't think plays nice with Self referencing tables more than 1 level deep. So I'm left with a few options

不幸的是，我认为 EF 不适合深度超过 1 级的自引用表。所以我有几个选择

1) Create query, order by depth and then create a custom class in C#, populating it one depth at a time.

1）创建查询，按深度排序，然后在 C# 中创建一个自定义类，一次填充一个深度。

2) Find some way to eager load the data in EF, I don't think it is possible for an unlimited amount of levels, only a fixed amount.

2）找到某种方式在EF中急切加载数据，我认为不可能有无限数量的级别，只有固定数量。

3) Some other way I'm not even sure about.

3）我什至不确定的其他方式。

Any inputs would be welcomed!

欢迎任何输入！

采纳答案by danludwig

I have successfully mapped hierarchical data using EF.

我已经成功地使用 EF 映射了分层数据。

Take for example an Establishmententity. This can represent a company, university, or some other unit within a larger organizational structure:

以一个Establishment实体为例。这可以代表公司、大学或更大组织结构中的其他单位：

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

Here is how the Parent / Children properties are mapped. This way, when you set the Parent of 1 entity, the Parent entity's Children collection is automatically updated:

这是父/子属性的映射方式。这样，当您设置 1 个实体的 Parent 时，Parent 实体的 Children 集合会自动更新：

// 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

Note that so far I haven't included your Lineage or Depth properties. You are right, EF doesn't work well for generating nested hierarchical queries with the above relationships. What I finally settled on was the addition of a new gerund entity, along with 2 new entity properties:

请注意，到目前为止，我还没有包括您的 Lineage 或 Depth 属性。你是对的，EF 不能很好地生成具有上述关系的嵌套层次查询。我最终确定的是添加一个新的动名词实体，以及 2 个新的实体属性：

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<EstablishmentNode> Ancestors { get; set; }
    public virtual ICollection<EstablishmentNode> Offspring { get; set; }

}

While writing this up, hazzik posted an answer that is very similar to this approach. I'll continue writing up though, to provide a slightly different alternative. I like to make my Ancestor and Offspring gerund types actual entity types because it helps me get the Separation between the Ancestor and Offspring (what you referred to as Depth). Here is how I mapped these:

在写这篇文章时，hazzik 发布了一个与这种方法非常相似的答案。不过，我会继续写下去，以提供一个略有不同的替代方案。我喜欢让我的祖先和后代动名词类型成为实际的实体类型，因为它帮助我获得祖先和后代之间的分离（你所说的深度）。这是我如何映射这些：

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

... and finally, the identifying relationships in the Establishment entity:

...最后，建立实体中的识别关系：

// 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);

Also, I did not use a sproc to update the node mappings. Instead we have a set of internal commands that will derive / compute the Ancestors and Offspring properties based on the Parent & Children properties. However ultimately, you end up being able to do some very similar querying as in hazzik's answer:

另外，我没有使用 sproc 来更新节点映射。相反，我们有一组内部命令，这些命令将根据父和子属性派生/计算祖先和后代属性。但是，最终，您最终能够像 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);

The reason for the bridge entity between the main entity and its Ancestors / Offspring is again because this entity lets you get the Separation. Also, by declaring it as an identifying relationship, you can remove nodes from the collection without having to explicitly call DbContext.Delete() on them.

主实体和它的祖先/后代之间的桥梁实体的原因再次是因为这个实体让你得到了分离。此外，通过将其声明为标识关系，您可以从集合中删除节点，而无需对其显式调用 DbContext.Delete()。

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

回答by hazzik

You could use supporting hierarchy table to do eager loading of unlimited levels of tree.

您可以使用支持层次结构表来预先加载无限级别的树。

So, you need to add two collections Ancestorsand Descendants, both collection should be mapped as many-to-many to supporting table.

因此，您需要添加两个集合Ancestors和Descendants，两个集合都应该多对多地映射到支持表。

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

Ancestors will contain all ancestors (parent, grand-parent, grand-grand-parent, etc.) of the entity and Descendantswill contain all the descendants (children, grand-children, grand-grand-children, etc) of the entity.

Ancestors 将包含实体的所有祖先（父母、祖父母、祖祖父母等），Descendants并将包含实体的所有后代（孩子、孙辈、孙辈等）。

Now you have to map it with EF Code First:

现在您必须使用 EF Code First 映射它：

public class TreeConfiguration : EntityTypeConfiguration<Tree>
{
    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"));
    }    
}

Now with this structure you could do eager fetch like following

现在有了这个结构，你可以像下面这样快速获取

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

This query will load entity with idand all of it descenadnts.

此查询将加载实体id及其所有后代。

You could populate the supporting table with following stored procedure:

您可以使用以下存储过程填充支持表：

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

Or even you could map supporting table to a view:

或者甚至您可以将支持表映射到视图：

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

回答by DeXteR

I've already spent a while trying to fix a bug in your solution. The stored procedure really don't generate children, grandchildren, etc. Below you will find fixed stored procedure:

我已经花了一段时间试图修复您的解决方案中的错误。存储过程真的不会生成子、孙等。下面你会发现固定的存储过程：

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

Mistake: wrong reference. Translating @hazzik code it was:

错误：错误的参考。翻译@hazzik 代码是：

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

but should be

但应该是

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

also I've added code that allows you to update TreeHierarchy table not only when you will populate it.

我还添加了代码，允许您更新 TreeHierarchy 表，而不仅仅是在填充它时。

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

And the magic. This procedure or rather TreeHierarchy allows you to load Children just by including Ancestors (not Children and not Descendants).

还有魔法。此过程或更确切地说 TreeHierarchy 允许您仅通过包含祖先（不是子代也不是后代）来加载子代。

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

Now the YourDbContext will return a rootNode with loaded children, children of rootName's children (grandchildren), and so on.

现在，YourDbContext 将返回一个带有加载的子节点、rootName 子节点（孙子节点）的子节点等的 rootNode。

回答by DeXteR

I knew that there must be something wrong with this solution. It is not simple. Using this solution, EF6 require another package of hacks to manage a simple tree (fe. deletions). So finally I've found a simple solution but combined with this approach.

我知道这个解决方案一定有问题。这并不简单。使用这个解决方案，EF6 需要另一个黑客包来管理一个简单的树（fe.删除）。所以最后我找到了一个简单的解决方案，但结合了这种方法。

First of all leave entity simple: just Parent and list of Children is enough. Also mapping should be simple:

首先让实体保持简单：只需要​​ Parent 和 Children 列表就足够了。映射也应该很简单：

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

 HasMany(x => x.Children)
    .WithOptional(x => x.Parent);

Then add migration (code first: migrations: package console: Add-Migration Hierarchy) or in other ways a stored procedure:

然后添加迁移（代码优先：迁移：包控制台：添加迁移层次结构）或以其他方式添加存储过程：

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

Then when you will try to receive your tree nodes from database just do it in two steps:

然后，当您尝试从数据库接收树节点时，只需分两步完成：

//Get children IDs
var sql = $"EXEC Tree_GetChildren {rootNodeId}";
var children = context.Database.SqlQuery<int>(sql).ToList<int>();

//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);

It all. This query helps you to get a root node and load all children. Without playing with introducing Ancestors and Descendants.

这一切。此查询可帮助您获取根节点并加载所有子节点。不玩介绍祖先和后代。

Remember also when you will try to save sub-node, then do it just this way:

还请记住，当您尝试保存子节点时，请按照以下方式进行：

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

Do it that way, not by adding children to root node.

这样做，而不是通过向根节点添加子节点。

回答by DeXteR

Another implementation option that I've recently worked on...

我最近研究的另一个实现选项......

My tree is very 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<Node> 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<Node> Nodes { get; set; }
}

My requirements, not so much.

我的要求，没有那么多。

Given a set of leaves and a single ancestor, show children of that ancestor who have descendants that have leaves within the set

给定一组叶子和一个单一祖先，显示该祖先的子代，其后代在该集合中具有叶子

An analogy would be a file structure on disk. The current user has access to a subset of files on the system. As the user opens nodes in the file system tree, we only want to show that user nodes that will, eventually, lead them to the files they can see. We don't want to show them file paths to files they do not have access to (for security reasons, e.g., leaking the existence of a document of a certain type).

一个类比是磁盘上的文件结构。当前用户有权访问系统上的文件子集。当用户打开文件系统树中的节点时，我们只想显示最终将引导他们到他们可以看到的文件的用户节点。我们不想向他们显示他们无权访问的文件的文件路径（出于安全原因，例如，泄露某种类型的文档的存在）。

We want to be able to express this filter as an IQueryable<T>, so we can apply it to any node query, filtering out unwanted results.

我们希望能够将此过滤器表示为IQueryable<T>，因此我们可以将其应用于任何节点查询，过滤掉不需要的结果。

To do this, I created a Table Valued Function that returns the descendants for a node in the tree. It does this via a CTE.

为此，我创建了一个表值函数，该函数返回树中节点的后代。它通过 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
)

Now, I'm using Code First, so I had to use

现在，我使用的是 Code First，所以我不得不使用

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

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

in order to add the function to my DbContext

为了将函数添加到我的 DbContext

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

with a complex return type (couldn't reuse Node, looking into that)

具有复杂的返回类型（无法重用 Node，调查一下）

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

Putting it all together allowed me, when the user expands a node in the tree, to get the filtered list of child nodes.

当用户展开树中的一个节点时，将所有这些放在一起允许我获得过滤后的子节点列表。

public static Node[] GetVisibleDescendants(int parentId)
{
    using (var db = new Models.Database())
    {
        int[] visibleLeaves = SuperSecretResourceManager.GetLeavesForCurrentUserLol();

        var targetQuery = db.Nodes as IQueryable<Node>;

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

It's important to note that the function is executed on the server, not in the application. Here's the query that gets executed

需要注意的是，该函数是在服务器上执行的，而不是在应用程序中执行的。这是执行的查询

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
        )
    ))

Note the function call within the query above.

注意上面查询中的函数调用。

回答by SH_SWAT

@danludwig thanks for your answer

@danludwig 感谢您的回答

I write some function for update Node, It work's perfect. My code is it good or I should write it in other way?

我写了一些更新节点的函数，它工作得很好。我的代码是好的还是我应该以其他方式编写？

    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<CategoryNode>();
        if (null == ancestorCategory.Ancestors)
        {
            ancestorCategory.Ancestors = new List<CategoryNode>();
        }

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