How to do recursive load with Entity framework?

Question

I have a tree structure in the DB with TreeNodes table. the table has nodeId, parentId and parameterId. in the EF, The structure is like TreeNode.Children where each child is a TreeNode... I also have a Tree table with contain id,name and rootNodeId.

At the end of the day I would like to load the tree into a TreeView but I can't figure how to load it all at once. I tried:

var trees = from t in context.TreeSet.Include("Root").Include("Root.Children").Include("Root.Children.Parameter")
        .Include("Root.Children.Children")
                        where t.ID == id
                        select t;

This will get me the the first 2 generations but not more. How do I load the entire tree with all generations and the additional data?

Reorder

If this is still a problem for you, I've provided another answer that's better than chatty DB calls and will be able to populate the entire hierarchy without having to specify infinite Includes. – Dockhand

Answer 1

I had this problem recently and stumbled across this question after I figured a simple way to achieve results. I provided an edit to Craig's answer providing a 4th method, but the powers-that-be decided it should be another answer. That's fine with me :)

My original question / answer can be found here.

This works so long as your items in the table all know which tree they belong to (which in your case it looks like they do: t.ID). That said, it's not clear what entities you really have in play, but even if you've got more than one, you must have a FK in the entity Children if that's not a TreeSet

Basically, just don't use Include():

var query = from t in context.TreeSet
            where t.ID == id
            select t;

// if TreeSet.Children is a different entity:
var query = from c in context.TreeSetChildren
            // guessing the FK property TreeSetID
            where c.TreeSetID == id
            select c;

This will bring back ALL the items for the tree and put them all in the root of the collection. At this point, your result set will look like this:

-- Item1
   -- Item2
      -- Item3
-- Item4
   -- Item5
-- Item2
-- Item3
-- Item5

Since you probably want your entities coming out of EF only hierarchically, this isn't what you want, right?

.. then, exclude descendants present at the root level:

Fortunately, because you have navigation properties in your model, the child entity collections will still be populated as you can see by the illustration of the result set above. By manually iterating over the result set with a foreach() loop, and adding those root items to a new List<TreeSet>(), you will now have a list with root elements and all descendants properly nested.

If your trees get large and performance is a concern, you can sort your return set ASCENDING by ParentID (it's Nullable, right?) so that all the root items are first. Iterate and add as before, but break from the loop once you get to one that is not null.

var subset = query
     // execute the query against the DB
     .ToList()
     // filter out non-root-items
     .Where(x => !x.ParentId.HasValue);

And now subset will look like this:

-- Item1
   -- Item2
      -- Item3
-- Item4
   -- Item5

About Craig's solutions:

1. You really don't want to use lazy loading for this!! A design built around the necessity for n+1 querying will be a major performance sucker.
********* (Well, to be fair, if you're going to allow a user to selectively drill down the tree, then it could be appropriate. Just don't use lazy loading for getting them all up-front!!)


2. I've never tried the nested set stuff, and I wouldn't suggest hacking EF configuration to make this work either, given there is a far easier solution.


3. Another reasonable suggestion is creating a database view that provides the self-linking, then map that view to an intermediary join/link/m2m table. Personally, I found this solution to be more complicated than necessary, but it probably has its uses.

Dockhand

JoeBrockhaus, I haven't test your code, but few things: 1) that code simply iterates and fill data as a single node and not as a tree node. 2) The root node would never be add. Perhaps you should try to assign the child objects in a ICollectionable problery. Doing so you would create a tree. I won't downvote, but please improve your answer. – Nickeliferous

@GabrielAndrésBrancolini The original question lacked a bit of detail about the model but my answer addresses both probable scenarios I mention. As for the collection of children, these will be populated automatically because of (and as long as) navigation properties (are) defined for the entities. One of them will be the root node. The ultimate change is in logic: don't think about querying a parent and getting its recursive children, but simply query for all the children and get the parent independently if needed. – Dockhand

Also, the comment about the downvote was because the original answer was downvoted before any other votes or comments were made, for an answer which at least some individuals believe is a better answer to the question. – Dockhand

This answer was useful to me, although it required one extra step when using Lazy load. I'm using Entity Framework Core 3.1 with Lazy load proxies. So, even when the tree was being populated, the proxies were triggering an extra load when Children was accessed. So, the solution was to add dbContext.Entry(treeNode).Collection(n => n.Children).IsLoaded = true; for each of the returned nodes. – Wailoo

Answer 2

When you use Include(), you are asking the Entity Framework to translate your query into SQL. So think: How would you write an SQL statement which returns a tree of an arbitrary depth?

Answer: Unless you are using specific hierarchy features of your database server (which are not SQL standard, but supported by some servers, such as SQL Server 2008, though not by its Entity Framework provider), you wouldn't. The usual way to handle trees of arbitrary depth in SQL is to use the nested sets model rather than the parent ID model.

Therefore, there are three ways which you can use to solve this problem:

1. Use the nested sets model. This requires changing your metadata.
2. Use SQL Server's hierarchy features, and hack the Entity Framework into understanding them (tricky, but this technique might work). Again, you'll need to change your metadata.i
3. Use explicit loading or EF 4's lazy loading instead of eager loading. This will result in many database queries instead of one.

Mispronounce

At the end, I added a recursive call that calls Load on the Children and on the other referenced objects. Thanks – Reorder

FYI... The 'nested sets model' link didn't work. InformationWeek said 'Non-working URL'. – Gorlin

Answer 3

I wanted to post up my answer since the others didn't help me.

My database is a little different, basically my table has an ID and a ParentID. The table is recursive. The following code gets all children and nests them into a final list.

public IEnumerable<Models.MCMessageCenterThread> GetAllMessageCenterThreads(int msgCtrId)
{
    var z = Db.MCMessageThreads.Where(t => t.ID == msgCtrId)
        .Select(t => new MCMessageCenterThread
        {
            Id = t.ID,
            ParentId = t.ParentID ?? 0,
            Title = t.Title,
            Body = t.Body
        }).ToList();

    foreach (var t in z)
    {
        t.Children = GetChildrenByParentId(t.Id);
    }

    return z;
}

private IEnumerable<MCMessageCenterThread> GetChildrenByParentId(int parentId)
{
    var children = new List<MCMessageCenterThread>();

    var threads = Db.MCMessageThreads.Where(x => x.ParentID == parentId);

    foreach (var t in threads)
    {
        var thread = new MCMessageCenterThread
        {
            Id = t.ID,
            ParentId = t.ParentID ?? 0,
            Title = t.Title,
            Body = t.Body,
            Children = GetChildrenByParentId(t.ID)
        };

        children.Add(thread);
    }

    return children;
}

For completeness, here's my model:

public class MCMessageCenterThread
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Title { get; set; }
    public string Body { get; set; }

    public IEnumerable<MCMessageCenterThread> Children { get; set; }
}

Ammieammine

This helped me today, Thanks! – Diggings

This is the recursive load method. It will spawn n-queries to the database. And there are a few problems with the code: 1. GetAllMessageCenterThreads returns a list but only ever has a single item (.Where(t=>t.ID == msgCtrId)). 2. your ParentID property should be nullable (int? vs int), and ParentId = t.ParentID ?? 0, will always return '0' because ParentID can't be null (This must not be code-first?). 3. It looks like your model is missing a property: MessageCenterId. All items should have this field, so you can get all items by that id. – Dockhand

If your goal in this scenario is to get all the replies to a particular thread (vs all threads for a particular blog), then you should look into Common Table Expressions (or CTEs), which are specifically for recursive scenarios. In this case, you would create a recursive union+self-join. See this answer: https://mcmap.net/q/261288/-cte-to-get-all-children-descendants-of-a-parent – Dockhand

This code was taken from a database-first example; secondly, if you have a better solution perhaps you ought to post it, eh? I guess bashing someone else's working solution is always more fun ;) – Ammieammine

Answer 4

I wrote something recently that does N+1 selects to load the whole tree, where N is the number of levels of your deepest path in the source object.

This is what I did, given the following self-referencing class

public class SomeEntity 
{
  public int Id { get; set; }
  public int? ParentId { get; set; }
  public string Name { get; set;
}

I wrote the following DbSet helper

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Threading.Tasks;

namespace Microsoft.EntityFrameworkCore
{
    public static class DbSetExtensions
    {
        public static async Task<TEntity[]> FindRecursiveAsync<TEntity, TKey>(
            this DbSet<TEntity> source,
            Expression<Func<TEntity, bool>> rootSelector,
            Func<TEntity, TKey> getEntityKey,
            Func<TEntity, TKey> getChildKeyToParent)
            where TEntity: class
        {
            // Keeps a track of already processed, so as not to invoke
            // an infinte recursion
            var alreadyProcessed = new HashSet<TKey>();

            TEntity[] result = await source.Where(rootSelector).ToArrayAsync();

            TEntity[] currentRoots = result;
            while (currentRoots.Length > 0)
            {
                TKey[] currentParentKeys = currentRoots.Select(getEntityKey).Except(alreadyProcessed).ToArray();
                alreadyProcessed.AddRange(currentParentKeys);

                Expression<Func<TEntity, bool>> childPredicate = x => currentParentKeys.Contains(getChildKeyToParent(x));
                currentRoots = await source.Where(childPredicate).ToArrayAsync();
            }

            return result;
        }
    }
}

Whenever you need to load a whole tree you simply call this method, passing in three things

1. The selection criteria for your root objects
2. How to get the property for the primary key of the object (SomeEntity.Id)
3. How to get the child's property that refers to its parent (SomeEntity.ParentId)

For example

SomeEntity[] myEntities = await DataContext.SomeEntity.FindRecursiveAsync(
  rootSelector: x => x.Id = 42,
  getEntityKey: x => x.Id,
  getChildKeyToParent: x => x.ParentId).ToArrayAsync();
);

Alternatively, if you can add a RootId column to the table then for each non-root entry you can set this column to the ID of the root of the tree. Then you can fetch everything with a single select

DataContext.SomeEntity.Where(x => x.Id == rootId || x.RootId == rootId)

Baseman

This may be OK for small sets with very low RPS, but if you must, you really should be using a CTE at the database to recursively load the whole set. – Dockhand

Is that better than DataContext.SomeEntity.Where(x => x.Id == rootId || x.RootId == rootId) ? – Baseman

If you have a rootId then you don't need the CTE at the database. The value of the CTE is simply to perform all the recursive iteration at the database so that you aren't incurring connection & round-trip overhead. – Dockhand

Answer 5

For an example of loading in child objects, I'll give the example of a Comment object that holds a comment. Each comment has a possible child comment.

private static void LoadComments(<yourObject> q, Context yourContext)
{
    if(null == q | null == yourContext)
    {
        return;
    }
    yourContext.Entry(q).Reference(x=> x.Comment).Load();
    Comment curComment = q.Comment;
    while(null != curComment)
    {
        curComment = LoadChildComment(curComment, yourContext);
    }
}

private static Comment LoadChildComment(Comment c, Context yourContext)
{
    if(null == c | null == yourContext)
    {
        return null;
    }
    yourContext.Entry(c).Reference(x=>x.ChildComment).Load();
    return c.ChildComment;
}

Now if you were having something that has collections of itself you would need to use Collection instead of Reference and do the same sort of diving down. At least that's the approach I took in this scenario as we were dealing with Entity and SQLite.

Endways

Answer 6

This is an old question, but the other answers either had n+1 database hits or their models were conducive to bottom-up (trunk to leaves) approaches. In this scenario, a tag list is loaded as a tree, and a tag can have multiple parents. The approach I use only has two database hits: the first to get the tags for the selected articles, then another that eager loads a join table. Thus, this uses a top-down (leaves to trunk) approach; if your join table is large or if the result cannot really be cached for reuse, then eager loading the whole thing starts to show the tradeoffs with this approach.

To begin, I initialize two HashSets: one to hold the root nodes (the resultset), and another to keep a reference to each node that has been "hit."

var roots = new HashSet<AncestralTagDto>(); //no parents
var allTags = new HashSet<AncestralTagDto>();

Next, I grab all of the leaves that the client requested, placing them into an object that holds a collection of children (but that collection will remain empty after this step).

var startingTags = await _dataContext.ArticlesTags
        .Include(p => p.Tag.Parents)
        .Where(t => t.Article.CategoryId == categoryId)
        .GroupBy(t => t.Tag)
        .ToListAsync()
        .ContinueWith(resultTask => 
             resultTask.Result.Select(
                  grouping => new AncestralTagDto(
                        grouping.Key.Id, 
                        grouping.Key.Name)));

Now, let's grab the tag self-join table, and load it all into memory:

var tagRelations = await _dataContext.TagsTags.Include(p => p.ParentTag).ToListAsync();

Now, for each tag in startingTags, add that tag to the allTags collection, then travel down the tree to get the ancestors recursively:

foreach (var tag in startingTags)
{
    allTags.Add(tag);
    GetParents(tag);
}
return roots;

Lastly, here's the nested recursive method that builds the tree:

void GetParents(AncestralTagDto tag)
{
    var parents = tagRelations.Where(c => c.ChildTagId == tag.Id).Select(p => p.ParentTag);
    if (parents.Any()) //then it's not a root tag; keep climbing down
    {
        foreach (var parent in parents)
        {
            //have we already seen this parent tag before? If not, instantiate the dto.
            var parentDto = allTags.SingleOrDefault(i => i.Id == parent.Id);
            if (parentDto is null)
            {
                parentDto = new AncestralTagDto(parent.Id, parent.Name);
                allTags.Add(parentDto);
            }

            parentDto.Children.Add(tag);
            GetParents(parentDto);
        }
    }
    else //the tag is a root tag, and should be in the root collection. If it's not in there, add it.
    {
        //this block could be simplified to just roots.Add(tag), but it's left this way for other logic.
        var existingRoot = roots.SingleOrDefault(i => i.Equals(tag));
        if (existingRoot is null)
            roots.Add(tag);
    }
}

Under the covers, I am relying on the properties of a HashSet to prevent duplicates. To that end, it's important that the intermediate object that you use (I used AncestralTagDto here, and its Children collection is also a HashSet), override the Equals and GetHashCode methods as appropriate for your use-case.

Bedouin

Answer 7

I have used a recursive function to solve this problem. thank to Peter Morris answer but that solution load all set recursively. so I tried to solve this problem to load just required records.

namespace Microsoft.EntityFrameworkCore
{
    public static class DbSetExtensions
    {   
        public static List<TEntity> FindRecursive<TEntity, TKey>(
            this DbSet<TEntity> source,
            Expression<Func<TEntity, bool>> rootPredicate,
            Expression<Func<TEntity, TKey>> rootKey,
            Expression<Func<TEntity, TKey?>> childKey)
            where TEntity : class
            where TKey : struct
        {
            var roots = source.Where(rootPredicate).ToList();
            var result = new List<TEntity>();
            result.AddRange(roots);

            var rootIds = roots.Select(rootKey.Compile()).ToList();
            foreach (var id in rootIds)
            {
                var childPredicate = BuildPredicate(childKey, id);
                result.AddRange(FindRecursive1(source, childPredicate, rootKey, childKey));
            }
            return result;
        }

        private static Expression<Func<TEntity, bool>> BuildPredicate<TEntity, TKey>(Expression<Func<TEntity, TKey?>> keySelector, TKey value)
            where TEntity : class
            where TKey : struct
        {
            var parameter = Expression.Parameter(typeof(TEntity), "x");
            var left = Expression.Invoke(keySelector, parameter);
            var right = Expression.Constant(value, typeof(TKey?));
            var body = Expression.Equal(left, right);
            return Expression.Lambda<Func<TEntity, bool>>(body, parameter);
        }
    }
}

And for usage :

var recursiveData = DataContext.SomeEntity.FindRecursive(
  rootPredicate: x => x.Id = 50,
  rootKey: x => x.Id,
  childKey: x => x.ParentId);

Sectional