Entity Framework Traverse and return child records in self reference table

Question

I am using Entity Framework and have a table of BusinessUnits which can reference another record of the same type to form a child-parent hierarchy.

I also have a set of users, and user permissions, where each user defined in this table should have access to the BusinessUnit and all sub-business units in the hierarchy. Users should not have access to the BusinessUnit above the one referenced (if exists).

How can I go about forming LINQ queries to handle this self-referencing relationship tree and return all the business units (with child units) for which this user has access? Is it possible to do it in one query, or do I need to manually build the tree myself with a for-loop?

I have seen schema's reference in this way from node to parent, does this mean I have to start at the furthest child node to build the tree by one parent at a time?

Thanks in advance,

Chris

class BusinessUnit
{
    int BusinessUnitID {get;set;}
    public string BusinessName {get;set;}
    BusinessUnit ParentBusinessUnit {get;set;}
}

class User
{
    int UserID {get;set;}
    string Firstname {get;set;}
}

class UserPermissions
{
    [Key, ForeignKey("BusinessUnit"), Column(Order = 0)] 
    BusinessUnit BusinessUnit {get;set;}
    [Key, ForeignKey("User"), Column(Order = 1)] 
    User User {get;set;}
}

IEnumerable<BusinessUnit> GetUnitsForWhichUserHasAccess(User user)
{
/* Example 1
 given: BusinessUnitA (ID 1) -> BusinessUnitB (ID 2) -> BusinessUnitC (ID 3)
 with user with ID 1:
 and UserPermissions with an entry: BusinessUnit(2), User(1)
 the list { BusinessUnitB, BusinessUnitC } should be returned
*/

/* Example 2
 given: BusinessUnitA (ID 1) -> BusinessUnitB (ID 2) -> BusinessUnitC (ID 3)
 with user with ID 1:
 and UserPermissions with an entry: BusinessUnit(1), User(1)
 the list { BusinessUnitA, BusinessUnitB, BusinessUnitC } should be returned
*/
}

Answer 1

I had to solve a problem of returning hierarchal json data to the web and I started off by using Olly suggestion of using Common Expression table (CET) and my code was

    static public IEnumerable<TagMaster> GetHierarchy(IEnumerable<int> surveyId, Entities dbContext)
    {
        var sql = String.Format( @"
WITH SurveyTags ([TagID], [TagTitle], [SurveyID], [ParentTagID]) AS (
    SELECT [TagID], [TagTitle], [SurveyID], [ParentTagID]
    FROM [dbo].[TagMaster]
    WHERE [SurveyID] in ({0}) and ParentTagID is null
    UNION ALL
    SELECT
        TagMaster.[TagID], TagMaster.[TagTitle], TagMaster.[SurveyID], TagMaster.[ParentTagID]
        FROM [dbo].[TagMaster]
        INNER JOIN SurveyTags ON TagMaster.ParentTagID =  SurveyTags.TagID
)
SELECT [TagID], [TagTitle], [SurveyID], [ParentTagID]
FROM SurveyTags", String.Join(",", surveyId));
        return dbContext.TagMasters.SqlQuery(sql).Where(r => r.ParentTagID == null).ToList();
    }

But I noticed when accessing the children, the web app was still making round trips to the database! It is also painful to just pass the Entity object to Json because you many end up with fields you don’t want.

The final solution I came up with does not need CET and only makes one trip to the DB. In my case, I could pull up all the records based on the SurveyId but if you don’t have such a key to use, you can still use the CET to get the hierarchy.

This is how I converted the flat records to a tree and just took the fields I need.

1) First load the records I need from the db.

var tags = db.TagMasters.Where(r => surveyIds.Contains(r.SurveyID)).Select(r => new { id = r.TagID, name = r.TagTitle, parentId = r.ParentTagID }).ToList();

2) Create a dictionary of ViewModels for it.

var tagDictionary = tags.Select(r => new TagHierarchyViewModel { Id = r.id, Name = r.name }).ToDictionary(r => r.Id);

3) Then convert it to a hierarchy.

  foreach (var tag in tags) {
     if (tag.parentId.HasValue)  {
                    tagDictionary[tag.parentId.Value].Tags.Add(tagDictionary[tag.id]);
     }
  }

4) Remove all the child nodes.

var tagHierarchy = from td in tagDictionary
    join t in tags on td.Key equals t.id
    where t.parentId == null
    select td.Value;

Result:

Answer 2

OK, there are a few things here. We can make this a bit easier by adding some more properties to your model. Is that an option? If so, add collection properties to the entities. Now, I don't know which EF API you're using: DbContext (code first or edmx) or ObjectContext. In my sample I've used the DbContext API with an edmx model to generate these classes.

If you prefer, with a few annotations you could dispense with the edmx file.

public partial class BusinessUnit
{
    public BusinessUnit()
    {
        this.ChlidBusinessUnits = new HashSet<BusinessUnit>();
        this.UserPermissions = new HashSet<UserPermissions>();
    }

    public int BusinessUnitID { get; set; }
    public string BusinessName { get; set; }
    public int ParentBusinessUnitID { get; set; }

    public virtual ICollection<BusinessUnit> ChlidBusinessUnits { get; set; }
    public virtual BusinessUnit ParentBusinessUnit { get; set; }
    public virtual ICollection<UserPermissions> UserPermissions { get; set; }
}

public partial class User
{
    public User()
    {
        this.UserPermissions = new HashSet<UserPermissions>();
    }

    public int UserID { get; set; }
    public string FirstName { get; set; }

    public virtual ICollection<UserPermissions> UserPermissions { get; set; }
}

public partial class UserPermissions
{
    public int UserPermissionsID { get; set; }
    public int BusinessUnitID { get; set; }
    public int UserID { get; set; }

    public virtual BusinessUnit BusinessUnit { get; set; }
    public virtual User User { get; set; }
}

public partial class BusinessModelContainer : DbContext
{
    public BusinessModelContainer()
        : base("name=BusinessModelContainer")
    {
    }

    protected override void OnModelCreating(DbModelBuilder modelBuilder)
    {
        throw new UnintentionalCodeFirstException();
    }

    public DbSet<BusinessUnit> BusinessUnits { get; set; }
    public DbSet<User> Users { get; set; }
    public DbSet<UserPermissions> UserPermissions { get; set; }
}

@Chase medallion is correct in that we can't write recursive LINQ (or even Entity SQL) queries.

Option 1: Lazy Loading

With lazy loading enabled, you could do something like this...

    private static IEnumerable<BusinessUnit> UnitsForUser(BusinessModelContainer container, User user)
    {
        var distinctTopLevelBusinessUnits = (from u in container.BusinessUnits
                                             where u.UserPermissions.Any(p => p.UserID == user.UserID)
                                             select u).Distinct().ToList();

        List<BusinessUnit> allBusinessUnits = new List<BusinessUnit>();

        foreach (BusinessUnit bu in distinctTopLevelBusinessUnits)
        {
            allBusinessUnits.Add(bu);
            allBusinessUnits.AddRange(GetChildren(container, bu));
        }

        return (from bu in allBusinessUnits
                group bu by bu.BusinessUnitID into d
                select d.First()).ToList();
    }

    private static IEnumerable<BusinessUnit> GetChildren(BusinessModelContainer container, BusinessUnit unit)
    {
        var eligibleChildren = (from u in unit.ChlidBusinessUnits
                                select u).Distinct().ToList();

        foreach (BusinessUnit child in eligibleChildren)
        {
            yield return child;

            foreach (BusinessUnit grandchild in child.ChlidBusinessUnits)
            {
                yield return grandchild;
            }
        }
    }

Option 2: Pre-load Entities

However, there are some ways you could optimize this to avoid repeated trips to the server. If you have only a reasaonably small number of business units in the database you could load the entire list. Then, because of EFs ability to fix up relationships automatically, simply loading a user and his permissions from the database would give us all we need.

To clarify: this method means that you load all the BusinessUnit entities; even the ones that the user has no permissions to. However, because it greatly reduces the 'chatter' with the SQL Server, it may still perform better than Option 1 above. Unlike Option 3 below, this is 'pure' EF without any dependency on a specific provider.

        using (BusinessModelContainer bm = new BusinessModelContainer())
        {
            List<BusinessUnit> allBusinessUnits = bm.BusinessUnits.ToList();

            var userWithPermissions = (from u in bm.Users.Include("UserPermissions")
                                       where u.UserID == 1234
                                       select u).Single();

            List<BusinessUnit> unitsForUser = new List<BusinessUnit>();

            var explicitlyPermittedUnits = from p in userWithPermissions.UserPermissions
                                           select p.BusinessUnit;

            foreach (var bu in explicitlyPermittedUnits)
            {
                unitsForUser.Add(bu);
                unitsForUser.AddRange(GetChildren(bm, bu));
            }

            var distinctUnitsForUser = (from bu in unitsForUser
                                        group bu by bu.BusinessUnitID into q
                                        select q.First()).ToList();
        }

Please note that the above two examples could be improved, but serve as an example to get you going.

Option 3: Bespoke SQL Query Using Common Table Expression

If you have a large number of business units, you might want to try the most efficient method. That would be to execute custom SQL that uses a hierarchical Common Table Expression to get back the information in one hit. This would of course tie the implementation to one provider, probably SQL Server.

Your SQL would be something like this:

    WITH UserBusinessUnits
            (BusinessUnitID,
            BusinessName,
            ParentBusinessUnitID)
            AS
            (SELECT Bu.BusinessUnitId,
                    Bu.BusinessName,
                    CAST(NULL AS integer)
                    FROM Users U
                    INNER JOIN UserPermissions P ON P.UserID = U.UserID
                    INNER JOIN BusinessUnits Bu ON Bu.BusinessUnitId = P.BusinessUnitId
                    WHERE U.UserId = ?
            UNION ALL
            SELECT  Bu.BusinessUnitId,
                    Bu.BusinessName,
                    Bu.ParentBusinessUnitId
                    FROM UserBusinessUnits Uu
                    INNER JOIN BusinessUnits Bu ON Bu.ParentBusinessUnitID = Uu.BusinessUnitId)
    SELECT  DISTINCT
            BusinessUnitID,
            BusinessName,
            ParentBusinessUnitID
            FROM UserBusinessUnits

You would use code like the following to materialize a collection of BusinessUnit objects for which the user has permissions.

bm.BusinessUnits.SqlQuery(mySqlString, userId);

There is a subtle difference between the above line and the very similar code suggested by @Jeffrey. The above uses DbSet.SqlQuery() while his uses Database.SqlQuery. The latter produces entities that are not tracked by the context, while the former returns (by default) tracked entities. Tracked entities give you the ability to make and save changes, and automatic fix-up of the navigation properties. If you don't need those features, disable change tracking (either with .AsNoTracking() or by using Database.SqlQuery).

Summary

Nothing beats testing with a realistic data set to determine which method is most effective. Using hand-crafted SQL code (Option 3) is always likely to perform best, but at the expense of having more complicated code that is less portable (because it's tied to the underlying db technology).

Note also that the options available to you depend on the "flavour" of EF that you're using, and of course, on your chosen database platform. If you would like some more specific guidance that accounts for this please update your question with the extra information.

• What database do you use?
• Does you project use an EDMX file, or code first?
• If using an EDMX, do you use the default (EntityObject) code generation technique, or T4 templates?

Answer 3

To get hierarchy in single request, you need to use special table structure. One of possible solutions is to have a special key that contains all parents of this record. In this case you have simple and very fast (it will be faster than cte recursion) query to get all childs.
But if you want to move record to another branch of hierarchy it will be very expansive operation.

Answer 4

Recursive CTE in SQL is just a technique using ground rules. You can build the same query in LINQ using those ground rules.

Here are the simple steps to follow

1) Get the list of permissions from UserPermissions table 2) Foreach permission, recurse the tree to find the subset of permission

There are lot of ways to optmize\adapt these queries but here is the core:

//Gets the list of permissions for this user
        static IEnumerable<BusinessUnit> GetPermissions(int userID)
        {
            //create a permission tree result set object
            List<BusinessUnit> permissionTree = new List<BusinessUnit>();

            //Get the list of records for this user from UserPermissions table
            IEnumerable<UserPermissions> userPermissions = from UP in UPs
                                         where UP.User.UserID == userID
                                         select UP;

            //for each entry in UserPermissions, build the permission tree
            foreach (UserPermissions UP in userPermissions)
            {
                BuildPermissionTree(UP.BusinessUnit, permissionTree);
            }

            return permissionTree;
        }

//recursive query that drills the tree.
        static IEnumerable<BusinessUnit> BuildPermissionTree(BusinessUnit pBU,List<BusinessUnit> permissionTree)
        {
            permissionTree.Add(pBU);

            var query = from BU in BUs
                        where BU.ParentBusinessUnit == pBU
                        select BU;

            foreach (var BU in query)
            {
                BuildPermissionTree(BU,permissionTree);
            }
            return permissionTree;
        }

O\p when queried for User 1 -> Permissions in (B,C) (refer diagram)

BusinessUnitB
BusinessUnitG
BusinessUnitC
BusinessUnitD
BusinessUnitF
BusinessUnitE

Here is the full code :

class BusinessUnit
    {
        public int BusinessUnitID { get; set; }
        public string BusinessName { get; set; }
        public BusinessUnit ParentBusinessUnit { get; set; }

        public override string ToString()
        {
            return BusinessUnitID + " " + BusinessName + " " + ParentBusinessUnit;
        }
    }

    class User
    {
        public int UserID { get; set; }
        public string Firstname { get; set; }

        public override string ToString()
        {
            return UserID + " " + Firstname;
        }
    }

    class UserPermissions
    {
        public BusinessUnit BusinessUnit { get; set; }
        public User User { get; set; }

        public override string ToString()
        {
            return BusinessUnit + " " + User;
        }
    }

    class SOBUProblem
    {
        static List<BusinessUnit> BUs = new List<BusinessUnit>();
        static List<User> Users = new List<User>();
        static List<UserPermissions> UPs = new List<UserPermissions>();

        static void Main()
        {
            //AutoInitBU();
            InitBU();
            InitUsers();
            InitUPs();
            //Dump(BUs);
            //Dump(Users);
            //Dump(UPs);
            //SpitTree(BUs[2]);
            int userID = 1;
            foreach (var BU in GetPermissions(userID))
                Console.WriteLine(BU.BusinessName);

        }
        //Gets the lsit of permissions for this user
        static IEnumerable<BusinessUnit> GetPermissions(int userID)
        {
            //create a permission tree result set object
            List<BusinessUnit> permissionTree = new List<BusinessUnit>();

            //Get the list of records for this user from UserPermissions table
            IEnumerable<UserPermissions> userPermissions = from UP in UPs
                                         where UP.User.UserID == userID
                                         select UP;

            //for each entry in UserPermissions, build the permission tree
            foreach (UserPermissions UP in userPermissions)
            {
                BuildPermissionTree(UP.BusinessUnit, permissionTree);
            }

            return permissionTree;
        }

        //recursive query that drills the tree.
        static IEnumerable<BusinessUnit> BuildPermissionTree(BusinessUnit pBU,List<BusinessUnit> permissionTree)
        {
            permissionTree.Add(pBU);

            var query = from BU in BUs
                        where BU.ParentBusinessUnit == pBU
                        select BU;

            foreach (var BU in query)
            {
                BuildPermissionTree(BU,permissionTree);
            }
            return permissionTree;
        }

        static void Dump<T>(IEnumerable<T> items)
        {
            foreach (T item in items)
            {
                Console.WriteLine(item.ToString());
            }
        }

        static void InitBU()
        {
            BusinessUnit BURoot = new BusinessUnit() { BusinessUnitID = 1, BusinessName = "BusinessUnitA" };
            BUs.Add(BURoot);
            BusinessUnit BUlevel11 = new BusinessUnit() { BusinessUnitID = 2, BusinessName = "BusinessUnitB", ParentBusinessUnit = BURoot };
            BusinessUnit BUlevel12 = new BusinessUnit() { BusinessUnitID = 3, BusinessName = "BusinessUnitC", ParentBusinessUnit = BURoot };
            BUs.Add(BUlevel11);
            BUs.Add(BUlevel12);
            BusinessUnit BUlevel121 = new BusinessUnit() { BusinessUnitID = 4, BusinessName = "BusinessUnitD", ParentBusinessUnit = BUlevel12 };
            BusinessUnit BUlevel122 = new BusinessUnit() { BusinessUnitID = 5, BusinessName = "BusinessUnitE", ParentBusinessUnit = BUlevel12 };
            BUs.Add(BUlevel121);
            BUs.Add(BUlevel122);
            BusinessUnit BUlevel1211 = new BusinessUnit() { BusinessUnitID = 6, BusinessName = "BusinessUnitF", ParentBusinessUnit = BUlevel121 };
            BUs.Add(BUlevel1211);
            BusinessUnit BUlevel111 = new BusinessUnit() { BusinessUnitID = 7, BusinessName = "BusinessUnitG", ParentBusinessUnit = BUlevel11 };
            BUs.Add(BUlevel111);
        }

        static void AutoInitBU()
        {
            BusinessUnit BURoot = new BusinessUnit() { BusinessUnitID = 1, BusinessName = "BusinessUnitA" };
            BUs.Add(BURoot);
            Dictionary<int, string> transTable = new Dictionary<int, string>() {{2,"B"},{3,"C"} };
            //Create Child nodes
            for (int i = 0; i < 2; i++)
            {
                BUs.Add(new BusinessUnit() { BusinessUnitID = i + 2, BusinessName = "BusinessUnit" + transTable[i+2],ParentBusinessUnit =  BUs[i]});
            }
        }

        static void InitUsers()
        {
            Users.Add(new User() {UserID = 1,Firstname="User1" });
        }

        static void InitUPs()
        {
            UPs.Add(new UserPermissions() { BusinessUnit = BUs[1], User = Users[0] });
            UPs.Add(new UserPermissions() { BusinessUnit = BUs[2], User = Users[0] });
        }
    }

Answer 5

If you're not tied to using linq for the solution, its vastly simpler and faster to use a CTE in sql as such:

var sql = @"
WITH BusinessUnitHierarchy ( BusinessUnitID, BusinessName, ParentBusinessUnitID )
AS(
    Select bu.BusinessUnitID, bu.BusinessName, bu.ParentBusinessUnitID
    from BusinessUnit bu
    inner join [UserPermissions] up on bu.BusinessUnitID = up.BusinessUnitID
    where up.UserID = @userID
    UNION ALL

    Select
    bu.BusinessUnitID, bu.BusinessName, bu.ParentBusinessUnitID
    from BusinessUnit bu
    inner join BusinessUnitHierarchy buh on bu.ParentBusinessUnitID = buh.BusinessUnitID
)
SELECT * FROM BusinessUnitHierarchy buh
";
context.Database.SqlQuery<BusinessUnit>(sql, new SqlParameter("userID", [[your user ID here]]));

Answer 6

If I'm understanding correctly, what you want is a recursive query (a recursive common table expression in raw T-SQL). As far as I know, there is no way to write such a recursive query in pure LINQ to Entities.

However, if you know the max depth the hierarchy, you can build up a single query that joins on itself a fixed number of times to achieve the result that you want.

int userIdOfInterest = ...
IQueryable<BusinessUnit> units = ...

// start with a query of all units the user has direct permission to
var initialPermissionedUnits = units.Where(bu => bu.UserPermissions.Any(up => up.User.Id == userIdOfInterest));

var allHierarchyLevels = new Stack<IQueryable<BusinessUnit>();
allHierarchyLevels.Push(initialPermissionedUnits);
for (var i = 0; i < MAX_DEPTH; ++i) {
    // get the next level of permissioned units by joining the last level with 
    // it's children
    var nextHierarchyLevel = allHierarchyLevels.Peek()
            // if you set up a Children association on BusinessUnit, you could replace
            // this join with SelectMany(parent => parent.Children)
            .Join(units, parent => parent.BusinessUnitId, child => child.ParentBusinessUnit.BusinessUnitId, (parent, child) => child));
    allHierarchyLevels.Push(nextHierarchyLevel);
}

// build an IQueryable<> which represents ALL units the query is permissioned too
// by UNIONING together all levels of the hierarchy (the UNION will eliminate duplicates as well)
var allPermissionedUnits = allHierarchyLevels.Aggregate((q1, q2) => q1.Union(q2));

// finally, execute the big query we've built up
return allPermissionedUnits.ToList();

Of course, the performance of the generated query will most likely worsen as MAX_DEPTH increases. However, it will probably be better that executing 1 query per level of the hierarchy in a for loop.

If you don't know MAX_DEPTH, you could consider adding a depth column to your business units table (easy to set on insertion because it's always parent.depth + 1). Then you could easily query for MAX_DEPTH before running the permissioning query.