Execution-Deferred query to identify all descendants?

Question

So I have a simple table that looks like this to represent a tree of categories and subcategories supporting a dynamic N levels of depth.

CategoryID int NOT NULL (PK)
ParentCategoryID int NULLABLE (FK to self)
CategoryName varchar(100) NOT NULL

My entity (typed this out from memory, sorry if there's a silly mistake in here):

public class Category
{
    public int CategoryId { get; set; }
    public int ParentCategoryId { get; set; }
    public string CategoryName { get; set; }

    public virtual Category ParentCategory { get; set; }
    public IDbSet<Category> ImmediateChildCategories { get; set; }
}

Using an execution-deferred lambda expression in Entity Framework (6.x) in C# (4.5+), how would I identify all categories that are descendants of a specified category?

My pseudocode SQL query that I'd like would be this:

SELECT * FROM Category WHERE AnyLevelOfAncestorId = 123;

My pseudocode EF query that I'd like to see would be this (paging is there to emphasize my need for execution-deferred support):

_db.Categories.Where(cat => cat.HasAncestor(123)).Skip(1000).Take(25).ToList();

Additional details:

A category with a NULL ParentCategoryID is a root node of a tree (there can be several).
No category will have its own CategoryID nor any descendant's ID as a ParentCategoryID (i.e. no circular relationships and all relationships eventually terminate at a root node although I may query for an ID lower than a root node)
I'm not sure if I want to include the specified ID (123) in the results or not. So I'll accept an answer that goes either way and adjust as necessary once I know if I want that specific one also included.

I don't believe that EF supports the generation of recursive queries. I would typically solve this problem by defining a recursive view in the database that projects all category–descendant pairs, and then query or join to that from EF. How to define the recursive view depends on the DBMS. SQL Server has [recursive CTEs](https://technet.microsoft.com/en-us/library/ms186243(v=sql.105).aspx); I don't know about Oracle. — Douglas, Jan 29 '16 at 17:27
@Douglas I had a DBA show me some P-SQL syntax that uses `START WITH`, `CONNECT BY PRIOR`, and `GROUP BY ROLLUP` to perform this in a single query. There is no way for EF to project a query using such constructs? If we must, we'll bundle this in a stored proc but I was hoping we could avoid that since they're a pain for us to maintain (same with views if that's the path we must take). — Jaxidian, Jan 29 '16 at 17:29
Apparently, newer versions of Oracle support recursive CTEs too, so I would suggest you go with those. They're more maintainable than stored procedures, and allow further query composition (as per your requirements). — Douglas, Jan 29 '16 at 17:31
Related answer recommending recursive CTEs: http://stackoverflow.com/a/11929928/1149773. Recursion in Oracle: http://stackoverflow.com/a/4659866/1149773. — Douglas, Jan 29 '16 at 17:35
@Douglas I think those CTE links are the answer I need. Not exactly what I was looking for but seems what I was looking for isn't possible with EF at this time. I'm going to edit your answer to include that info and mark it as the answer. Thanks! — Jaxidian, Jan 29 '16 at 18:00
Thanks for updating the answer. I've edited out the term "deferred execution", since it technically also applies to an IEnumerable populated through LINQ-to-Objects (like in the recursive descent of my example). What you're presumably seeking is the generation of an IQueryable encompassing the recursive operation that can be issued as a *single query* to the database. — Douglas, Jan 30 '16 at 10:03

score 2 · Accepted Answer · edited May 23 '17 at 12:30

I assume that your Category entity type has a collection navigation property for retrieving its child categories (as related through the foreign key). This navigation property would cause the child categories to be loaded lazily the first time it is accessed. You can define a method that recursively calls this navigation property (e.g. ChildCategories) on the root and its children.

public static IEnumerable<Category> GetDescendants(Category root)
{
    return root.ChildCategories.Concat(root.ChildCategories.SelectMany(GetDescendants));
}

The drawback with the above code is that it will issue a separate database query for retrieving each parent's children. I don't believe that Entity Framework supports the generation of a single recursive query at present (EF 6.1.3). Instead, I would suggest that you define a recursive view in the database that projects all category–descendant pairs; include this view as an entity in your entity data model; and then query or join to it from your LINQ queries. The view can be defined using DBMS-specific technology. SQL Server supports recursive CTEs, as do recent versions of Oracle.

Looks like I'll have to go down the recursive CTE or other path for this recursive query. Thanks @Douglas! — Jaxidian, Jan 29 '16 at 18:02

Execution-Deferred query to identify all descendants?

1 Answers1