Is there a way, using LINQ/EF, to get the top most item in a parent/child hierarchy?

Question

I have a class called Structure:

public class Structure
{
    public int StructureId { get; set; }
    public Structure Parent { get; set; }
}

As you can see, Structure has a parent Structure. There can be an indefinite number of structures within this hierarchy.

Is there any way, using LINQ (with Entity Framework), to get the top-most structure in this hierarchy?

Currently, I'm having to hit the database quite a few times in order to find the top most parent. The top most parent is a Structure with a null Parent property:

Structure structure = structureRepository.Get(id);
while (structure.Parent != null)
{
    structure = structureRepository.Get(structure.Parent.StructureId);
}

// When we're here; `structure` is now the top most parent.

So, is there any elegant way to do this using LINQ/Lambdas? Ideally, starting with the following code:

var structureQuery = from item in context.Structures
                     where item.StructureId == structureId
                     select item;

I just want to be able to write something like the following so that I only fire off one database hit:

structureQuery = Magic(structureQuery);
Structure topMostParent = structureQuery.Single();

Answer 1

I like the question and can't think of a linq-y way of doing this. But could you perhaps implement this on your repository class? After all, there should be only one at the top and if the need for it is there, then maybe it deserves a structureRepository.GetRoot() or something.

Answer 2

you can use the linq take construct, for instance

            var first3Customers = (
                from c in customers
                select new {c.CustomerID, c.CustomerName} )
            .Take(2);

Answer 3

I have a similar situation. I didn't manage to solve it directly with LINQ/EF. Instead I solved by creating a database view using recursive common table expressions, as outlined here. I made a user-defined function that cross applies all parents to a child (or vice versa), then a view that makes use of this user-defined function which I imported into my EF object context.

(disclaimer: simplified code, I didn't actually test this)

I have two tables, say MyTable (containing all items) and MyParentChildTable containing the ChildId,ParentId relation

I have then defined the following udf:

CREATE FUNCTION dbo.fn_getsupertree(@childid AS INT) 
    RETURNS @TREE TABLE
(
     ChildId INT NOT NULL
    ,ParentId  INT NULL
    ,Level   INT NOT NULL
)
AS
BEGIN
  WITH Parent_Tree(ChildId, ParentId)
  AS
  ( 
    -- Anchor Member (AM)
    SELECT ChildId, ParentId, 0
    FROM MyParentChildTable
    WHERE ChildId = @childid

    UNION all

    -- Recursive Member (RM)
    SELECT info.ChildId, info.ParentId, tree.[Level]+1
    FROM MyParentChildTable AS info
      JOIN Parent_Tree AS tree
        ON info.ChildId = tree.ParentId
  )
  INSERT INTO @TREE
    SELECT * FROM Parent_Tree;

  RETURN
END

and the following view:

CREATE VIEW VwSuperTree AS (
SELECT tree.*
FROM MyTable
CROSS APPLY fn_getsupertree(MyTable.Id) as tree
)
GO

This gives me for each child, all parents with their 'tree level' (direct parent has level 1, parent of parent has level 2, etc.). From that view, it's easy to query the item with the highest level. I just imported the view in my EF context to be able to query it with LINQ.

Answer 4

This is not a direct answer, but the problem you are having is related to the way you are storing your tree. There are a couple ways of simplifying this query by structuring data differently.

One is to use a Nested Set Hierarchy, which can simplify many kinds of queries across trees.

Another is to store a denomralized table of Ancestor/Descendant/Depth tuples. This query then becomes finding the tuple with the current structure as the descendant with the maximum depth.

Answer 5

I think the best I'm going to get is to load the entire hierarchy in one hit from the structure I want the top parent of:

var structureQuery = from item in context.Structures
                         .Include(x => x.Parent)
                     where item.StructureId == structureId
                     select item;

Then just use the code:

while (structure.Parent != null)
{
    structure = structure.Parent;
}