Building a LINQ Expression to find items related to all descendants of a tree node

The Scenario

I have built a database structure that represents a category tree to help classify some of the data we have stored. The implementation is that each record in the Category table has a nullable foreign key back into the Category table to represent the parent Category of this category (one-to-many), essentially allowing for subcategories within a broader parent level. There is a CategoryMembership table that links a record in the Item table to its respective Category (many-to-many). I have created the DBML for this database, and it has a member access structure that includes the following:

Dim aCategory As New Category()
Dim aPa开发者_开发技巧rentCategory As Category = aCategory.Parent
Dim aChildCategoryCollection As EntitySet(Of Category) = aCategory.Subcategories
Dim aMembershipCollection As EntitySet(Of CategoryMembership)  = aCategory.CategoryMemberships

Each item in aMembershipCollection has the following member access structure:

Dim aMembership As CategoryMembership = aMembershipCollection.First()
Dim aLinkedCategory As Category = aMembership.Category
Dim aLinkedItem As Item = aMembership.Item

The Requirement

I am attempting to construct a LINQ Expression that would allow me to determine which Items have CategoryMemberships that are for the requested Category (i.e. aCategory.id = myID) or memberships for descendants of the requested Category, the idea being that I want all Items that are in the parent category or its multiple levels of subcategories.

Essentially the query would be built in a fashion similar to:

Dim results As IQueryable(Of Item) = _
    From cm In db.CategoryMemberships.Where(myInCategoryPredicate(myID)) _
    Select cm.Item

...where myInCategoryPredicate returns the LINQ Expression object that would help me make that determination. This is of course working from the assumption that the CategoryMembership table is the place to start to retrieve the IQueryable(Of Item). I may have made an erroneous assumption here and that is why I have come seeking advice.

The Problem

I'm having a hard time seeing the forest for the trees. I can't determine if I should start building the predicate from the Category or from the CategoryMembership, nor can I fathom the requisite code that would accomplish what I would like. I'm hoping that someone else who has already built a similar tree structure for a database might be able to help me navigate my way around the DBML classes.

Available Resources

I have previously made use of PredicateBuilder in the past and am relatively familiar with its workings but I haven't been able to devise a way to traverse upward through the tree and build a predicate recursively that would indicate whether an Item is in a category that is either the requested category or a child thereof. So far I've produced the following, with the very noticeable gap labeled SomeRecursiveCall():

Private Function InCategory(ByVal myID As Integer) As Expression(Of Func(Of CategoryMembership, Boolean))
    Dim predicate = PredicateBuilder.False(Of CategoryMembership)()

    predicate = predicate.Or(Function(cm) cm.fkCategoryID = myID OrElse SomeRecursiveCall())

    Return predicate
End Function

However, I realize that a predicate builder may be of no use here whatsoever and a different direction may be required.

I've considered there's always the possibility of selecting the Category record for the requested ID and building a list of IDs from it and all the members of Subcategories recursively then using that list to evaluate a .Contains() comparison on that list, but I was wondering if there weren't other options that didn't quite feel so ugly.

You can't do data-limitted recursion in a linq to sql query (where you want to recurse until there is no more data to fetch). This is because the query translator needs to know when to stop generating the query and it can't look at the data to know that.

You can use a Common Table Expression in TSql to do data-limitted recursion... If you just slap that CTE in a view, you can query the view from linq to sql.

The solution required creating a table-valued function from a recursive common table expression described by David B and querying against the function result in LINQ-to-SQL with a .Contains() on my test category's primary key. The details of how this is done are below.

A table-valued function GetAllCategories was declared using the following script. When given a parameter @ParentCategoryID, it returns that parent along with all subcategories and the respective depth of each record relative to the parent as a new field called CategoryLevel.

USE MyDatabase
GO

IF OBJECT_ID (N'dbo.GetAllCategories') IS NOT NULL

DROP FUNCTION dbo.GetAllCategories

GO

CREATE FUNCTION dbo.GetAllCategories(@ParentCategoryID int)

RETURNS TABLE

AS RETURN

(

WITH AllCategories (pkCategoryID, fkParentID, Name, Description, CategoryLevel)
AS
(
-- Anchor member definition
    SELECT c.pkCategoryID, c.fkParentID, c.Name, c.Description, 
        0 AS CategoryLevel
    FROM dbo.Category AS c
    WHERE c.pkCategoryID = @ParentCategoryID
    UNION ALL
-- Recursive member definition
    SELECT c.pkCategoryID, c.fkParentID, c.Name, c.Description,
        CategoryLevel + 1
    FROM dbo.Category AS c
    INNER JOIN AllCategories AS ac
        ON c.fkParentID = ac.pkCategoryID
)

SELECT *
FROM AllCategories

)

This table-valued function can now be included in your DBML from the server explorer by expanding the "Functions" subfolder of your database connection. FYI: It can also be seen in SQL Server Management Studio 2008 under MyDatabase > Programmability > Functions > Table-valued Functions. This function now becomes a member of any data context object you instantiate.

To utilize this function in solving the requirements above, I constructed a LINQ-to-SQL expression like so:

Using db As New MyDatabaseDataContext()
    Dim results As IQueryable(Of Item) =
        From cm In db.CategoryMemberships _
        Where (From i In db.GetAllCategories(searchValue) _
               Select i.pkCategoryID).Contains(cm.Category.pkCategoryID) _
        Select cm.Item
End Using

The expression projects a list of all primary keys from the function result and uses the .Contains() extension to test for the presence of the primary key for each CategoryMembership record's Category within. If successful, the corresponding Item for the membership is selected.

This returned all Items that were members of the Category with a primary key equal to searchValue, or members of any Category that were children of that parent.