Most Efficient Method of Self Referencing Tree Using Entity Framework

Most efficient method of self referencing tree using Entity Framework

I have successfully mapped hierarchical data using EF.

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

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:

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

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:

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:

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

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

Entity Framework self referencing - Parent-Child

I suppose to create a type for your purpose rather then using anonymous type and fill model via recursive method.

var three = BuildThree(db.Categories);

public IEnumerable<CategoryVm> BuildThree(IEnumerable<Categories> categories, int? parentCategoryId = null)
{
  if (categories == null)
  return null;
  var result = categories.select(c => new CategoryVm()
    { 
         id = c.CategoryId,
         text = c.CategoryName,
         parent = parentCategoryId, 
         children = BuildThree(c.children, c.CategoryId) 
    }
    return result;
 }

This solution there is on drawback - each time time when you call navigation property (children) you will make request to database. If you want to make it in one request and you have only one level of nested categories then .Include(c => c.Children) enough otherwise you have to make a choice one of the next options:

1. Write a common table expression (CTE) query, put it to view or stored procedure and map it by means of EF. The role of EF is not really big because the most tricky part is the SQL query

2. Especially for this kind of purpose, Microsoft SQL Server has hierarchyid but EF does not support it from the box. However there are some workarounds: Entity Framework HierarchyId Workarounds

3. You can add something like rootId to the Comment entity, when each child replay will has a link to root comment. After that you can load all hierarchy to memory in one sql query and map it manually. Given that database is bottleneck it will much faster then make new query for each level of hierarchy.

C# & Entity Framework - optimizing DB query for self-referencing entity with indefinite family tree

AFAIK, there is no support for doing such a recursive call through LINQ.

Therefore, you are left with the following options:

1. Write the query using Pure SQL, which would enable you to write a Common Table Expression that calls itself recursively. Then, the recursion logic to build up the result will be done in the database server at once, instead of having multiple roundtrips from the client application as you have now.
2. If you don't wanna have the raw SQL in your code for some reason, you could always create a database view from the same query you would build in option 1, and then query the view directly from your application.
3. Finally, there is an alternative without using Recursive CTEs at all: you could maintain your tree structure in the database in what's called a Nested Set Model. When doing that, you have to add two new properties to each node called something like Left and Right (or TreeMin and TreeMax), which represent the "position" when first/last visiting each node during a tree transversal. The idea of labeling each node with a Left and Right is that then you would be able to easily query all the children of one node checking if child.Left > parent.Left && child.Right < parent.Right. Maintaining such data structure in the DB might be a little bit more complex than the previous solution, and it's only advisable if your tree doesn't change that often.

Entity Framework Self Join

You cannot get all parents in one trip using any sane code.

However you can do something like this: https://stackoverflow.com/a/11565855/304832

By modifying your entity a bit, you can add 2 derived collections:

public class Item
{
    [Key]
    public int ItemId { get; set; }

    [Required]
    [MaxLength(255)]
    public string Name { get; set; }}

    public virtual Item Parent { get; set; } // be sure to make this virtual
    public virtual List<Item> Children { get; set; }

    public virtual ICollection<ItemNode> Ancestors { get; set; }
    public virtual ICollection<ItemNode> Offspring { get; set; }
}

You do need to introduce a new entity to make this work though, which looks like this:

public class ItemNode
{
    public int AncestorId { get; set; }
    public virtual Item Ancestor { get; set; }

    public int OffspringId { get; set; }
    public virtual Item Offspring { get; set; }

    public int Separation { get; set; } // optional
}

Now, if you want

all parents from ItemId 55 until no parent is found

...you can do something like this:

IEnumerable<Item> allParentsFrom55 = dbContext.Set<Item>()
    .Find(55).Ancestors.Select(x => x.Ancestor);

Entity framework.. self referencing table.. get records of Depth =x?

Theoretically you can create a method that builds query expression dynamically based on the specified depth level:

context.FamilyLabels.Where(x => 
    x.Parent. ... .Parent != null &&
    x.Parent.Parent ... .Parent == null);

The following implementation does the trick:

public static IList<FamilyLabel> Get(DbConnection connection, int depth)
{
    var p = Expression.Parameter(typeof(FamilyLabel));
    Expression current = p;

    for (int i = 0; i < deep; i++)
    {
        current = Expression.Property(current, "Parent");
    }

    var nullConst = Expression.Constant(null, typeof(FamilyLabel));

    var predicate = Expression.Lambda<Func<FamilyLabel, bool>>(
        Expression.AndAlso(
            Expression.NotEqual(current, nullConst),
            Expression.Equal(Expression.Property(current, "Parent"), nullConst)), p);

    using (MyDbContext context = new MyDbContext(connection))
    {
        return context.FamilyLabels.Where(predicate).ToList();
    }
}

However, presumably this will create a bunch of join expressions, so maybe this is not the most optimal way.

How to implement recursive self join entity framework?

I am not sure if you realize this but Menu1 is your parent Menu and Menu2 are your children menus. (I would recommending renaming both Menu1 and Menu2 properties to parent and children).

I believe all of the solutions you have linked have a solution you can use to solve your problem.

---

Code Sample:

void GetParents(Menu current) {
    dbContext.Entry(current).Reference(m => m.Menu2).Load();
    while (current.Menu2 != null) {
        current = current.Menu2; 
        dbContext.Entry(current).Reference(m => m.Menu2).Load();
    }
}

void GetChildren(Menu current) {
    if (current == null) {
        return;
    } else {
        dbContext.Entry(current).Collection(m => m.Menu1).Load();
        foreach (var menu in m.Menu1) {
            GetChildren(menu);
        }
    }
}

Something like this should help you get all parents and all children of a Menu instance called current. Note the efficiency is terrible. But that is a different problem. I don't optimize code until my performance tests indicate the bottlenecks in my application.

Fun quote: "Premature optimization is the root of all evil." - Donald Knuth

Rearranging the tree nodes and saving it back on a self-referencing table with EF

After days of trying out different things in vain I finally implemented command pattern and got it working as expected.

I implemented the following command interface for Add, Update, Delete and Reorder UI actions and stuff them in a collection which resides in the session.

public interface ITreeCommand
{
    void Execute(ICollection<ListItem> finalList, MainEntity source, ModelContainer db, ICollection<Guid> deletedIds);
}

Then on save, I execute these commands in order passing necessary parameters. I had to call db.SaveChanges() inside every execute method implementation. I had to keep the deleted node ids separately because I can skip any unnecessary additions, updates or reordering by checking against this list before executing.

Hope this helps someone someday.

---

Related Topics