How does Entity Framework work with recursive hierarchies? Include() seems not to work with it

Question

I have an Item. Item has a Category.

Category has ID, Name, Parent and Children. Parent and Children are of Category too.

When I do a LINQ to Entities query for a specific Item, it doesn't return the related Category, unless I use the Include("Category") method. But it doesn't bring the full category, with its parent and children. I could do Include("Category.Parent"), but this object is something like a tree, I have a recursive hierarchy and I don't know where it ends.

How can I make EF fully load the Category, with parent and children, and the parent with their parent and children, and so on?

This is not something for the whole application, for performance considerations it would be needed only for this specific entity, the Category.

Answer 1

Instead of using the Include method you could use Load.

You could then do a for each and loop through all the children, loading their children. Then do a for each through their children, and so on.

The number of levels down you go will be hard coded in the number of for each loops you have.

Here is an example of using Load: http://msdn.microsoft.com/en-us/library/bb896249.aspx

Answer 2

If you definitely want the whole hierarchy loaded, then if it was me I'd try writing a stored procedure who's job it is to return all the items in a hierarchy, returning the one you ask for first (and its children subsequently).

And then let the EF's relationship fixup ensure that they are all hooked up.

i.e. something like:

// the GetCategoryAndHierarchyById method is an enum
Category c = ctx.GetCategoryAndHierarchyById(1).ToList().First();

If you've written your stored procedure correctly, materializing all the items in the hierarchy (i.e. ToList()) should make EF relationship fixup kicks in.

And then the item you want (First()) should have all its children loaded and they should have their children loaded etc. All be populated from that one stored procedure call, so no MARS problems either.

Hope this helps

Alex

Answer 3

Use this extension method which calls the hard-coded version of Include, to achieve a dynamic depth level of inclusion, it works great.

namespace System.Data.Entity
{
  using Linq;
  using Linq.Expressions;
  using Text;

  public static class QueryableExtensions
  {
    public static IQueryable<TEntity> Include<TEntity>(this IQueryable<TEntity> source,
      int levelIndex, Expression<Func<TEntity, TEntity>> expression)
    {
      if (levelIndex < 0)
        throw new ArgumentOutOfRangeException(nameof(levelIndex));
      var member = (MemberExpression)expression.Body;
      var property = member.Member.Name;
      var sb = new StringBuilder();
      for (int i = 0; i < levelIndex; i++)
      {
        if (i > 0)
          sb.Append(Type.Delimiter);
        sb.Append(property);
      }
      return source.Include(sb.ToString());
    }
  }
}

Usage:

var affiliate = await DbContext.Affiliates
  .Include(3, a => a.Referrer)
  .SingleOrDefaultAsync(a => a.Id == affiliateId);

Anyway, meanwhile, join the discussion about it on the EF repo.

Answer 4

It could be dangerous if you did happen to load all recursive entities, especially on category, you could end up with WAY more than you bargained for:

Category > Item > OrderLine > Item
                  OrderHeader > OrderLine > Item
         > Item > ...

All of a sudden you've loaded most of your database, you could have also loaded invoices lines, then customers, then all their other invoices.

What you should do is something like the following:

var qryCategories = from q in ctx.Categories
                    where q.Status == "Open"
                    select q;

foreach (Category cat in qryCategories) {
    if (!cat.Items.IsLoaded)
        cat.Items.Load();
    // This will only load product groups "once" if need be.
    if (!cat.ProductGroupReference.IsLoaded)
        cat.ProductGroupReference.Load();
    foreach (Item item in cat.Items) {
        // product group and items are guaranteed
        // to be loaded if you use them here.
    }
}

A better solution however is to construct your query to build an anonymous class with the results so you only need to hit your datastore once.

var qryCategories = from q in ctx.Categories
                    where q.Status == "Open"
                    select new {
                        Category = q,
                        ProductGroup = q.ProductGroup,
                        Items = q.Items
                    };

This way you could return a dictionary result if required.

Remember, your contexts should be as short lived as possible.

Answer 5

You don't want to do recursive loading of the hierarchy, unless you are allowing a user to iteratively drill down/up the tree: Every level of recursion is another trip to the database. Similarly, you'll want lazy loading off to prevent further DB trips as you're traversing the hierarchy when rendering to a page or sending over a webservice.

Instead, flip your query: Get Catalog, and Include the items in it. This will get you all items both hierarchically (navigation properties) and flattened, so now you just need to exclude the non-root elements present at the root, which should be pretty trivial.

I had this problem and provided a detailed example of this solution to another, here

Answer 6

You chould rather introduce a mapping table that maps each Category a parent and a child, instead of adding the parent and child property to the cargo itself.

Depending on how often you need that information it can be queried on demand. Via unique constraints in the db you can avoid an infinite amount of relationships beeing possible.

Answer 7

I found out that if you include "two parent levels", you will get the whole parent hierarchy, like that:

var query = Context.Items
            .Include(i => i.Category)
            .Include(i => i.Category.Parent.Parent)

Answer 8

And now for a completely different approach to hierarchical data, for example populating a treeview.

First, do a flat query for all data, and then build the object graph in memory:

  var items = this.DbContext.Items.Where(i=> i.EntityStatusId == entityStatusId).Select(a=> new ItemInfo() { 
            Id = a.Id,
            ParentId = a.ParentId,
            Name = a.Name,
            ItemTypeId = a.ItemTypeId
            }).ToList();

Get the root item:

 parent = items.FirstOrDefault(a => a.ItemTypeId == (int)Enums.ItemTypes.Root);

Now build your graph:

 this.GetDecendantsFromList(parent, items);


 private void GetDecendantsFromList(ItemInfo parent, List<ItemInfo> items)
    {
        parent.Children = items.Where(a => a.ParentId == parent.Id).ToList();
        foreach (var child in parent.Children)
        {
            this.GetDecendantsFromList(child,items);
        }
    }

Answer 9

Here is a clever recursive function I found here that would work for this:

public partial class Category
{
    public IEnumerable<Category> AllSubcategories()
    {
        yield return this;
        foreach (var directSubcategory in Subcategories)
            foreach (var subcategory in directSubcategory.AllSubcategories())
            {
                yield return subcategory;
            }
    }
}

Answer 10

You could also create a tablevalued function in the database and add that to your DBContext. Then you can call that from your code.

This example requires that you import EntityFramework.Functions from nuget.

public class FunctionReturnType
{
    public Guid Id { get; set; } 

    public Guid AnchorId { get; set; } //the zeroPoint for the recursion

    // Add other fields as you want (add them to your tablevalued function also). 
    // I noticed that nextParentId and depth are useful
}

public class _YourDatabaseContextName_ : DbContext
{
    [TableValuedFunction("RecursiveQueryFunction", "_YourDatabaseContextName_")]
    public IQueryable<FunctionReturnType> RecursiveQueryFunction(
        [Parameter(DbType = "boolean")] bool param1 = true
    )
    {
        //Example how to add parameters to your function
        //TODO: Ask how to make recursive queries with SQL 
        var param1 = new ObjectParameter("param1", param1);
        return this.ObjectContext().CreateQuery<FunctionReturnType>(
            $"RecursiveQueryFunction(@{nameof(param1)})", param1);
    }

    protected override void OnModelCreating(DbModelBuilder modelBuilder)
    {
        //add both (Function returntype and the actual function) to your modelbuilder. 
        modelBuilder.ComplexType<FunctionReturnType>();
        modelBuilder.AddFunctions(typeof(_YourDatabaseContextName_), false);

        base.OnModelCreating(modelBuilder);
    }

    public IEnumerable<Category> GetParents(Guid id)
    {
        //this = dbContext
        return from hierarchyRow in this.RecursiveQueryFunction(true)
            join yourClass from this.Set<YourClassThatHasHierarchy>()
            on hierarchyRow.Id equals yourClass.Id
            where hierarchyRow.AnchorId == id
            select yourClass;
    }
}

Answer 11

try this

List<SiteActionMap> list = this.GetQuery<SiteActionMap>()
                .Where(m => m.Parent == null && m.Active == true)
                .Include(m => m.Action)
                .Include(m => m.Parent).ToList();    

if (list == null)
    return null;

this.GetQuery<SiteActionMap>()
    .OrderBy(m => m.SortOrder)
    .Where(m => m.Active == true)
    .Include(m => m.Action)
    .Include(m => m.Parent)
    .ToList();

return list;

Answer 12

@parliament gave me an idea for EF6. Example for Category with Methods to load all parents up to root node and all children.

NOTE: Use this only for non performance critical operation. Example with 1000 nodes performance from http://nosalan.blogspot.se/2012/09/hierarchical-data-and-entity-framework-4.html.

Loading 1000 cat. with navigation properties took 15259 ms 
Loading 1000 cat. with stored procedure took 169 ms

Code:

public class Category 
{
    [Key, DatabaseGenerated(DatabaseGeneratedOption.Identity)]
    public int Id { get; set; }

    public string Name { get; set; }

    public int? ParentId { get; set; }

    public virtual Category Parent { get; set; }

    public virtual ICollection<Category> Children { get; set; }

    private IList<Category> allParentsList = new List<Category>();

    public IEnumerable<Category> AllParents()
    {
        var parent = Parent;
        while (!(parent is null))
        {
            allParentsList.Add(parent);
            parent = parent.Parent;
        }
        return allParentsList;
    }

    public IEnumerable<Category> AllChildren()
    {
        yield return this;
        foreach (var child in Children)
        foreach (var granChild in child.AllChildren())
        {
            yield return granChild;
        }
    }   
}

Answer 13

My suggestion would be

var query = CreateQuery()
    .Where(entity => entity.Id == Id)
    .Include(entity => entity.Parent);
var result = await FindAsync(query);

return result.FirstOrDefault();

and it means it will load single entity and all this entity.Parent entities recursive.

entity is same as entity.Parent

Answer 14

public static class EntityFrameworkExtensions
{
    public static ObjectContext GetObjectContext(this DbContext context) 
    {
        ObjectContext objectContext = ((IObjectContextAdapter)context).ObjectContext;

        return objectContext;
    }

    public static string GetTableName<T>(this ObjectSet<T> objectSet) 
        where T : class
    {
        string sql = objectSet.ToTraceString();
        Regex regex = new Regex("FROM (?<table>.*) AS");
        Match match = regex.Match(sql);

        string table = match.Groups["table"].Value;
        return table;
    }

    public static IQueryable<T> RecursiveInclude<T>(this IQueryable<T> query, Expression<Func<T, T>> navigationPropertyExpression, DbContext context)
        where T : class
    {
        var objectContext = context.GetObjectContext();

        var entityObjectSet = objectContext.CreateObjectSet<T>();
        var entityTableName = entityObjectSet.GetTableName();
        var navigationPropertyName = ((MemberExpression)navigationPropertyExpression.Body).Member.Name;

        var navigationProperty = entityObjectSet
            .EntitySet
            .ElementType
            .DeclaredNavigationProperties
            .Where(w => w.Name.Equals(navigationPropertyName))
            .FirstOrDefault();

        var association = objectContext.MetadataWorkspace
            .GetItems<AssociationType>(DataSpace.SSpace)
            .Single(a => a.Name == navigationProperty.RelationshipType.Name);

        var pkName = association.ReferentialConstraints[0].FromProperties[0].Name;
        var fkName = association.ReferentialConstraints[0].ToProperties[0].Name;

        var sqlQuery = @"
                EXEC ('
                    ;WITH CTE AS
                    (
                        SELECT 
                            [cte1].' + @TABLE_PK + '
                            , Level = 1
                        FROM ' + @TABLE_NAME + ' [cte1]
                        WHERE [cte1].' + @TABLE_FK + ' IS NULL

                        UNION ALL

                        SELECT 
                            [cte2].' + @TABLE_PK + '
                            , Level = CTE.Level + 1
                        FROM ' + @TABLE_NAME + ' [cte2]
                            INNER JOIN CTE ON CTE.' + @TABLE_PK + ' = [cte2].' + @TABLE_FK + '
                    )
                    SELECT 
                        MAX(CTE.Level)
                    FROM CTE 
                ')
            ";

        var rawSqlQuery = context.Database.SqlQuery<int>(sqlQuery, new SqlParameter[]
            {
                new SqlParameter("TABLE_NAME", entityTableName),
                new SqlParameter("TABLE_PK", pkName),
                new SqlParameter("TABLE_FK", fkName)
            });

        var includeCount = rawSqlQuery.FirstOrDefault();

        var include = string.Empty;

        for (var i = 0; i < (includeCount - 1); i++)
        {
            if (i > 0)
                include += ".";

            include += navigationPropertyName;
        }

        return query.Include(include);
    }
}

Answer 15

Let me offer my simple solution that fits needs to enable/disable the branch of hierarchical data of the selected department's structure of an organization.

The table Departments looks according this SQL

CREATE TABLE [dbo].[Departments](
    [ID] [int] IDENTITY(1,1) NOT NULL,
    [Name] [nvarchar](1000) NOT NULL,
    [OrganizationID] [int] NOT NULL,
    [ParentID] [int] NULL,
    [IsEnabled] [bit] NOT NULL, 
 CONSTRAINT [PK_Departments] PRIMARY KEY CLUSTERED 
(
    [ID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO

C# code provides a very simple approach that work fine for me. 1. It returns the complete table asynchronously. 2. It changes property for the linked rows.

public async Task<bool> RemoveDepartmentAsync(int orgID, int depID)
            {
                try
                {
                    using (var db = new GJobEntities())
                    {
                        var org = await db.Organizations.FirstOrDefaultAsync(x => x.ID == orgID); // Check if  the organization exists
                        if (org != null)
                        {
                            var allDepartments = await db.Departments.ToListAsync(); // get all table items
                            var isExisting = allDepartments.FirstOrDefault(x => x.OrganizationID == orgID && x.ID == depID);
                            if (isExisting != null) // Check if the department exists
                            {
                                isExisting.IsEnabled = false; // Change the property of visibility of the department
                                var all = allDepartments.Where(x => x.OrganizationID == orgID && x.ID == isExisting.ID).ToList();
                                foreach (var item in all)
                                {
                                    item.IsEnabled = false;
                                    RecursiveRemoveDepartment(orgID, item.ID, ref allDepartments); // Loop over table data set to change property of the linked items
                                }
                                await db.SaveChangesAsync();
                            }
                            return true;
                        }
                    }
                }
                catch (Exception ex)
                {
                    logger.Error(ex);
                }

                return false;
            }

            private void RecursiveRemoveDepartment(int orgID, int? parentID, ref List<Department> items)
            {
                var all = items.Where(x => x.OrganizationID == orgID && x.ParentID == parentID);
                foreach (var item in all)
                {
                    item.IsEnabled = false;
                    RecursiveRemoveDepartment(orgID, item.ID, ref items);
                }
            }

This approach works very fast for relative small amount of records I guess less 100000. Probably for big set of data you have to implement server side stored function.

Enjoy!