如何构造一个可查询递归数据库表的查询?

I have a database table like this:

我有一个这样的数据库表:

Entity
---------------------
ID        int      PK
ParentID  int      FK
Code      varchar
Text      text

The ParentID field is a foreign key with another record in the same table (recursive). So the structure represents a Tree.

ParentID字段是一个外键，在同一个表中有另一个记录(递归)。所以这个结构代表一棵树。

I'm trying to write a method to query this table and get 1 specific Entity based on a path. A path would be a string representing the Code properties of the Entity and the parent Entities. So an example path would be "foo/bar/baz" which means the one specific Entity of which the Code == "baz", the parent's Code == "bar" and the parent of the parent's Code == "foo".

我尝试编写一个方法来查询这个表，并根据路径获得一个特定的实体。路径将是表示实体和父实体的代码属性的字符串。因此，一个示例路径是“foo/bar/baz”，意思是代码== "baz"的特定实体，父代码== "bar"，父代码的父代码== "foo"。

My attempt:

我的尝试:

public Entity Single(string path)
{
 string[] pathParts = path.Split('/');
 string code = pathParts[pathParts.Length -1];

 if (pathParts.Length == 1)
  return dataContext.Entities.Single(e => e.Code == code && e.ParentID == 0);

 IQueryable<Entity> entities = dataContext.Entities.Where(e => e.Code == code);
 for (int i = pathParts.Length - 2; i >= 0; i--)
 {
  string parentCode = pathParts[i];
  entities = entities.Where(e => e.Entity1.Code == parentCode); // incorrect
 }

 return entities.Single();
}

I know this isn't correct because the Where inside the forloop just adds more conditions to the current Entity instead of the parent Entity, but how do I correct this? In words I would like the for-loop to say "and the parent's code must be x and the parent of that parent's code must be y, and the parent of that parent of that parent's code must be z .... etc". Besides that, for performance reasons I'd like it to be one IQueryable so there will be just 1 query going to the database.

我知道这是不正确的，因为forloop中的Where只给当前实体添加了更多的条件而不是父实体，但是我该如何更正呢?的话我希望循环说”和父母的代码必须在父母的父母的x和y代码必须,和父母的,父母的父母的代码必须z ....等”。除此之外，出于性能原因，我希望它是一个可查询的，这样就会有一个查询到数据库。

3 个解决方案

#1

How to formulate an IQueryable to query a recursive database table? I'd like it to be one IQueryable so there will be just 1 query going to the database.

如何构造一个可查询递归数据库表的查询?我希望它是一个IQueryable，这样就会有一个查询到数据库。

I don't think traversing an hierarchical table using a single translated query is currently possible with Entity Framework. The reason is you'll need to implement either a loop or recursion and to my best knowledge neither can be translated into an EF object store query.

我不认为使用单个翻译的查询来遍历一个层次结构的表是当前实体框架所能实现的。原因是您需要实现一个循环或递归，并且我的最佳知识都不能转换为EF对象存储查询。

UPDATE

更新

@Bazzz and @Steven got me thinking and I have to admit I was completely wrong: it is possible and quite easy to construct an IQueryable for these requirements dynamically.

@Bazzz和@Steven让我思考，我不得不承认我是完全错误的:这是可能的，而且很容易构造一个可以动态地满足这些需求。

The following function can be called recursively to build up the query:

可以递归地调用以下函数来构建查询:

public static IQueryable<TestTree> Traverse(this IQueryable<TestTree> source, IQueryable<TestTree> table, LinkedList<string> parts)
{
    var code = parts.First.Value;
    var query = source.SelectMany(r1 => table.Where(r2 => r2.Code == code && r2.ParentID == r1.ID), (r1, r2) => r2);
    if (parts.Count == 1)
    {
        return query;
    }
    parts.RemoveFirst();
    return query.Traverse(table, parts);
}

The root query is a special case; here's a working example of calling Traverse:

根查询是一个特例;这里有一个工作示例，调用遍历:

using (var context = new TestDBEntities())
{
    var path = "foo/bar/baz";
    var parts = new LinkedList<string>(path.Split('/'));
    var table = context.TestTrees;

    var code = parts.First.Value;
    var root = table.Where(r1 => r1.Code == code && !r1.ParentID.HasValue);
    parts.RemoveFirst();

    foreach (var q in root.Traverse(table, parts))
        Console.WriteLine("{0} {1} {2}", q.ID, q.ParentID, q.Code);
}

The DB is queried only once with this generated code:

DB只对生成的代码查询一次:

exec sp_executesql N'SELECT 
[Extent3].[ID] AS [ID], 
[Extent3].[ParentID] AS [ParentID], 
[Extent3].[Code] AS [Code]
FROM   [dbo].[TestTree] AS [Extent1]
INNER JOIN [dbo].[TestTree] AS [Extent2] ON ([Extent2].[Code] = @p__linq__1) AND ([Extent2].[ParentID] = [Extent1].[ID])
INNER JOIN [dbo].[TestTree] AS [Extent3] ON ([Extent3].[Code] = @p__linq__2) AND ([Extent3].[ParentID] = [Extent2].[ID])
WHERE ([Extent1].[Code] = @p__linq__0) AND ([Extent1].[ParentID] IS NULL)',N'@p__linq__1 nvarchar(4000),@p__linq__2 nvarchar(4000),@p__linq__0 nvarchar(4000)',@p__linq__1=N'bar',@p__linq__2=N'baz',@p__linq__0=N'foo'

And while I like the execution plan of the raw query (see below) a bit better, the approach is valid and perhaps useful.

虽然我比较喜欢原始查询的执行计划(请参阅下面)，但是这个方法是有效的，而且可能是有用的。

End of UPDATE

月底更新

Using IEnumerable

使用IEnumerable

The idea is to grab the relevant data from the table in one go and then do the traversing in the application using LINQ to Objects.

它的想法是先从表中获取相关数据，然后在应用程序中使用LINQ对对象进行遍历。

Here's a recursive function that will get a node from a sequence:

这是一个递归函数，它将从序列中得到一个节点:

static TestTree GetNode(this IEnumerable<TestTree> table, string[] parts, int index, int? parentID)
{
    var q = table
        .Where(r => 
             r.Code == parts[index] && 
             (r.ParentID.HasValue ? r.ParentID == parentID : parentID == null))
        .Single();
    return index < parts.Length - 1 ? table.GetNode(parts, index + 1, q.ID) : q;
}

You can use like this:

你可以这样使用:

using (var context = new TestDBEntities())
{
    var path = "foo/bar/baz";
    var q = context.TestTrees.GetNode(path.Split('/'), 0, null);
    Console.WriteLine("{0} {1} {2}", q.ID, q.ParentID, q.Code);
}

This will execute one DB query for each path part, so if you want the DB to only be queried once, use this instead:

这将为每个路径部分执行一个DB查询，因此，如果您希望DB只被查询一次，请使用以下方法:

using (var context = new TestDBEntities())
{
    var path = "foo/bar/baz";
    var q = context.TestTrees
        .ToList()
        .GetNode(path.Split('/'), 0, null);
    Console.WriteLine("{0} {1} {2}", q.ID, q.ParentID, q.Code);
}

An obvious optimization is to exclude the codes not present in our path before traversing:

一个明显的优化是排除在遍历之前在我们的路径中不存在的代码:

using (var context = new TestDBEntities())
{
    var path = "foo/bar/baz";
    var parts = path.Split('/');
    var q = context
        .TestTrees
        .Where(r => parts.Any(p => p == r.Code))
        .ToList()
        .GetNode(parts, 0, null);
    Console.WriteLine("{0} {1} {2}", q.ID, q.ParentID, q.Code);
}

This query should be fast enough unless most of your entities have similar codes. However, if you absolutely need top performance, you could use raw queries.

这个查询应该足够快，除非您的大多数实体都有类似的代码。但是，如果您绝对需要*性能，您可以使用原始查询。

SQL Server Raw Query

SQL Server原始查询

For SQL Server a CTE-based query would probably be best:

对于SQL Server，基于cte的查询可能是最好的:

using (var context = new TestDBEntities())
{
    var path = "foo/bar/baz";
    var q = context.Database.SqlQuery<TestTree>(@"
        WITH Tree(ID, ParentID, Code, TreePath) AS
        (
            SELECT ID, ParentID, Code, CAST(Code AS nvarchar(512)) AS TreePath
            FROM dbo.TestTree
            WHERE ParentID IS NULL

            UNION ALL

            SELECT TestTree.ID, TestTree.ParentID, TestTree.Code, CAST(TreePath + '/' + TestTree.Code AS nvarchar(512))
            FROM dbo.TestTree
            INNER JOIN Tree ON Tree.ID = TestTree.ParentID
        )
        SELECT * FROM Tree WHERE TreePath = @path", new SqlParameter("path", path)).Single();
    Console.WriteLine("{0} {1} {2}", q.ID, q.ParentID, q.Code);
}

Limiting data by the root node is easy and might be quite useful performance-wise:

通过根节点来限制数据是很容易的，而且可能在性能上非常有用:

using (var context = new TestDBEntities())
{
    var path = "foo/bar/baz";
    var q = context.Database.SqlQuery<TestTree>(@"
        WITH Tree(ID, ParentID, Code, TreePath) AS
        (
            SELECT ID, ParentID, Code, CAST(Code AS nvarchar(512)) AS TreePath
            FROM dbo.TestTree
            WHERE ParentID IS NULL AND Code = @parentCode

            UNION ALL

            SELECT TestTree.ID, TestTree.ParentID, TestTree.Code, CAST(TreePath + '/' + TestTree.Code AS nvarchar(512))
            FROM dbo.TestTree
            INNER JOIN Tree ON Tree.ID = TestTree.ParentID
        )
        SELECT * FROM Tree WHERE TreePath = @path", 
            new SqlParameter("path", path),
            new SqlParameter("parentCode", path.Split('/')[0]))
            .Single();
    Console.WriteLine("{0} {1} {2}", q.ID, q.ParentID, q.Code);
}

Footnotes

脚注

All of this was tested with .NET 4.5, EF 5, SQL Server 2012. Data setup script:

所有这些都测试了。net 4.5, EF 5, SQL Server 2012。数据设置脚本:

CREATE TABLE dbo.TestTree
(
    ID int not null IDENTITY PRIMARY KEY,
    ParentID int null REFERENCES dbo.TestTree (ID),
    Code nvarchar(100)
)
GO

INSERT dbo.TestTree (ParentID, Code) VALUES (null, 'foo')
INSERT dbo.TestTree (ParentID, Code) VALUES (1, 'bar')
INSERT dbo.TestTree (ParentID, Code) VALUES (2, 'baz')
INSERT dbo.TestTree (ParentID, Code) VALUES (null, 'bla')
INSERT dbo.TestTree (ParentID, Code) VALUES (1, 'blu')
INSERT dbo.TestTree (ParentID, Code) VALUES (2, 'blo')
INSERT dbo.TestTree (ParentID, Code) VALUES (null, 'baz')
INSERT dbo.TestTree (ParentID, Code) VALUES (1, 'foo')
INSERT dbo.TestTree (ParentID, Code) VALUES (2, 'bar')

All examples in my test returned the 'baz' entity with ID 3. It's assumed that the entity actually exists. Error handling is out of scope of this post.

在我的测试中，所有的例子都返回了ID为3的“baz”实体。假设实体存在。错误处理超出了本文的范围。

UPDATE

更新

To address @Bazzz's comment, the data with paths is shown below. Code is unique by level, not globally.

要处理@Bazzz的注释，下面显示了带有路径的数据。代码是独一无二的，不是全局的。

ID   ParentID    Code      TreePath
---- ----------- --------- -------------------
1    NULL        foo       foo
4    NULL        bla       bla
7    NULL        baz       baz
2    1           bar       foo/bar
5    1           blu       foo/blu
8    1           foo       foo/foo
3    2           baz       foo/bar/baz
6    2           blo       foo/bar/blo
9    2           bar       foo/bar/bar

#2

The trick is to do it the other way around, and build up the following query:

诀窍是反过来做，并建立以下查询:

from entity in dataContext.Entities
where entity.Code == "baz"
where entity.Parent.Code == "bar"
where entity.Parent.Parent.Code == "foo"
where entity.Parent.Parent.ParentID == 0
select entity;

A bit naive (hard coded) solution would be like this:

有点天真(硬编码)的解决方案是这样的:

var pathParts = path.Split('/').ToList();

var entities = 
    from entity in dataContext.Entities 
    select entity;

pathParts.Reverse();

for (int index = 0; index < pathParts.Count+ index++)
{
    string pathPart = pathParts[index];

    switch (index)
    {
        case 0:
            entities = entities.Where(
                entity.Code == pathPart);
            break;
        case 1:
            entities = entities.Where(
                entity.Parent.Code == pathPart);
            break;
        case 2:
            entities = entities.Where(entity.Parent.Parent.Code == pathPart);
            break;
        case 3:
            entities = entities.Where(
                entity.Parent.Parent.Parent.Code == pathPart);
            break;
        default:
            throw new NotSupportedException();
    }
}

Doing this dynamically by building expression trees isn't trivial, but can be done by looking closely at what the C# compiler generates (using ILDasm or Reflector for instance). Here is an example:

通过构建表达式树来动态地实现这一点并不简单，但可以通过仔细查看c#编译器生成的内容(例如使用ILDasm或反射器)来实现。这是一个例子:

private static Entity GetEntityByPath(DataContext dataContext, string path)
{
    List<string> pathParts = path.Split(new char[] { '/' }).ToList<string>();
    pathParts.Reverse();

    var entities =
        from entity in dataContext.Entities
        select entity;

    // Build up a template expression that will be used to create the real expressions with.
    Expression<Func<Entity, bool>> templateExpression = entity => entity.Code == "dummy";
    var equals = (BinaryExpression)templateExpression.Body;
    var property = (MemberExpression)equals.Left;

    ParameterExpression entityParameter = Expression.Parameter(typeof(Entity), "entity");

    for (int index = 0; index < pathParts.Count; index++)
    {
        string pathPart = pathParts[index];

        var entityFilterExpression =
            Expression.Lambda<Func<Entity, bool>>(
                Expression.Equal(
                    Expression.Property(
                        BuildParentPropertiesExpression(index, entityParameter),
                        (MethodInfo)property.Member),
                    Expression.Constant(pathPart),
                    equals.IsLiftedToNull,
                    equals.Method),
                templateExpression.Parameters);

        entities = entities.Where<Entity>(entityFilterExpression);

        // TODO: The entity.Parent.Parent.ParentID == 0 part is missing here.
    }

    return entities.Single<Entity>();
}

private static Expression BuildParentPropertiesExpression(int numberOfParents, ParameterExpression entityParameter)
{
    if (numberOfParents == 0)
    {
        return entityParameter;
    }

    var getParentMethod = typeof(Entity).GetProperty("Parent").GetGetMethod();

    var property = Expression.Property(entityParameter, getParentMethod);

    for (int count = 2; count <= numberOfParents; count++)
    {
        property = Expression.Property(property, getParentMethod);
    }

    return property;
}

#3

You need a recursive function instead of your loop. Something like this should do the job:

您需要一个递归函数而不是循环。像这样的事情应该可以做:

public EntityTable Single(string path)
{
    List<string> pathParts = path.Split('/').ToList();
    string code = pathParts.Last();

    var entities = dataContext.EntityTables.Where(e => e.Code == code);

    pathParts.RemoveAt(pathParts.Count - 1);
    return GetRecursively(entities, pathParts);
}

private EntityTable GetRecursively(IQueryable<EntityTable> entity, List<string> pathParts)
{
    if (!(entity == null || pathParts.Count == 0))
    {
        string code = pathParts.Last();

        if (pathParts.Count == 1)
        {
            return entity.Where(x => x.EntityTable1.Code == code && x.ParentId == x.Id).FirstOrDefault();
        }
        else
        {                    
            pathParts.RemoveAt(pathParts.Count - 1);

            return this.GetRecursively(entity.Where(x => x.EntityTable1.Code == code), pathParts);
        }
    }
    else
    {
        return null;
    }
}

As you see, I am just returning the ultimate parent node. If you wanted to get a list of all EntityTable objects then I would make the recursive method to return a List of Ids of found nodes, and at the end - in the Single(...) method - run a simple LINQ query to get your IQueryable object using this list of IDs.

正如您所看到的，我只是返回最终的父节点。如果你想获得所有EntityTable对象的列表然后我将递归方法返回发现节点的id的列表,最后-单(…)方法中运行一个简单的LINQ查询得到你这个IQueryable对象使用这个id列表。

Edit: I tried to do your task but I think that there is a fundamental problem: there are cases when you are not able to identify a single path. For example, you have two pathes "foo/bar/baz" and "foo/bar/baz/bak" where "baz" entities are different. If you'll be seeking path "foo/bar/baz" then you'll always find two matching pathes (one would be partial of the four-entity path). Although you can get your "baz" entity correctly, but this is too confusing and I would just redesign this: either put a unique constraint so that each entity can only be used once, or store full path in the "Code" column.

编辑:我试图完成你的任务，但我认为存在一个基本问题:当你无法确定一条路径时，会出现一些情况。例如，您有两个pathes“foo/bar/baz”和“foo/bar/baz/bak”，其中“baz”实体是不同的。如果您正在寻找path“foo/bar/baz”，那么您将总是找到两个匹配的路径(一个将是四实体路径的一部分)。虽然您可以正确地获得您的“baz”实体，但是这太混乱了，我将重新设计这个:要么设置一个惟一的约束，以便每个实体只能被使用一次，或者在“代码”列中存储完整的路径。