Use Linq to Query for terminal/Leaf nodes in Hierarchical Table/Composite pattern

Question

I have a self-referencing table with an Id, CategoryName, and ParentId. It's a typical scenario of a hierarchy table of categories that can themselves be divided into categories that DB experts tell me is called the adjacency model.

What I want is to use Linq to SQL to query for subcategories that themselves are related to no other subcategories, ie they are immediate leaf nodes of some given category or subcategory.

The easy part, I got, which is just getting the subcategories. Almost embarrassed to put the code here. But we do like to see code..

IList<Categories> subcategories = context.Where( c => c.ParentId == 1).ToList();

But narrowing it to categories with no subcategories is turning me around. Any help would be much appreciated.

Thanks for you help. Jeff

UPDATE** It would appear this works, but if someone could confirm that it is "proper" I'd be grateful. So, if I want leaf nodes under a category with Id = 1, I would do this:

Categories.Where( c => !c.Children.Any ( d => d.ParentId == c.Id)).Where( e => e.ParentId == 1)

"Children" is the name Linq gives the self-referencing association.

Answer 1

I think if I understand your question correctly you're trying to get all of the Child elements that have no children of there own... this query self joins the table on itself to test if the node is used as a parent, if it's not then it's displayed in the result.

I'm not sure if this works as I have nothing to test it on...

   (from c in context
    join cc in context on c.id equals cc.parentid into temp
    from t in temp.DefaultIfEmpty()
    where t == null
    select c).ToList()

Answer 2

Your solution is correct because the Any() method, translates into sql "EXISTS()" function and !c.Children.Any ( d => d.ParentId == c.Id)) translates into a sql clause similar to NOT EXISTS (SELECT * FROM Categories WHERE ParentID = outerRef.ID)

Another way to do it is to use Count :

Categories.Where( c => c.Children.Count(d => d.ParentId == c.Id) == 0).Where( e => e.ParentId == 1)

But usually EXISTS() is preferred to COUNT() in sql (for performance reasons) so the solution with Any() should be the right one.

Answer 3

Perfect, Pop! Many thanks!