Recursive Query - Only select nodes where leaf nodes represent active data

Question

Given the following recursive query:

WITH DepartmentHierarchy (DepartmentID, Name, IsInactive, IsSpecial, ParentId, HierarchyLevel) AS
(
   -- Base case
   SELECT
      DepartmentId,
      Name,
      IsInactive,
      IsSpecial,
      ParentId,
      1 as HierarchyLevel
   FROM StoreDepartment
   WHERE ParentId IS NULL

   UNION ALL

   -- Recursive step
   SELECT
      d.DepartmentId,
       d.Name,
      d.IsInactive,
      d.IsSpecial,
      d.ParentId,
      dh.HierarchyLevel + 1 AS HierarchyLevel
   FROM StoreDepartment d
      INNER JOIN DepartmentHierarchy dh ON
         d.ParentId = dh.DepartmentId
) SELECT * FROM DepartmentHierarchy 

I am able to select data which looks like this:

DepartmentId, Name, IsInactive, IsSpecial, ParentId, HeirarchyLevel
1, Store, 0, 0, NULL, 1
2, Main Department 1, 0, 1, 2
3, Main Department 2, 0, 1, 2
4, Sub For Main 1, 0, 2, 3

Also, assume a table exists with DepartmentId and ItemId (ex: DepartmentItemRelationship). Leaf nodes from the department heirarchy are paired with items here.

I want my recursive query to only return nodes (at any level) that have at least one leaf node below them with an match in the department/item relationship table. These nodes could be 6 or 7 levels down, so I'm not sure how I would amend my query to be sure to include those.

Thanks, Kyle

Answer 1

You can create a path column that keeps track of the hierarchy. Then you can only add the children nodes that have a match in the DepartmentItemRelationship table. And finally get only the nodes that at least have a child.

Try something like this:

    WITH DepartmentHierarchy (DepartmentID, Name, IsInactive, IsSpecial, ParentId, HierarchyLevel) AS
(
   -- Base case
   SELECT
      '/'+cast( DepartmentId as varchar(max)) as [path]
      DepartmentId,
      Name,
      IsInactive,
      IsSpecial,
      ParentId,
      1 as HierarchyLevel
   FROM StoreDepartment
   WHERE ParentId IS NULL

   UNION ALL

   -- Recursive step
   SELECT
      dh.[path] +'/'+ cast( d.DepartmentId as varchar(max)) as [path]
      d.DepartmentId,
      d.Name,
      d.IsInactive,
      d.IsSpecial,
      d.ParentId,
      dh.HierarchyLevel + 1 AS HierarchyLevel
   FROM StoreDepartment d
      INNER JOIN DepartmentHierarchy dh ON
         d.ParentId = dh.DepartmentId
   where exists ( select top 1 1 
                  from DepartmentItemRelationship di
                  where di.DepartmentId = d.DepartmentId )
) 
SELECT * 
FROM DepartmentHierarchy dh
where exists ( select top 1 1 
               from DepartmentHierarchy 
               where charindex('/'+dh.DepartmentID+'/',[path]) > 0) 

Answer 2

If I understand you correctly, you want all nodes that are exactly one level above the leaf level?

You don't actually need a recursive query for this. All you have to is first find the leaf nodes, then select all the parents.

WITH LeafNodeParents AS
(
    SELECT DISTINCT ParentId
    FROM StoreDepartment
    WHERE DepartmentId NOT IN
    (
        SELECT DISTINCT ParentId FROM StoreDepartment
    )
)
SELECT d.DepartmentId, d.Name, d.IsInactive, d.IsSpecial, d.ParentId
FROM LeafNodeParents p
INNER JOIN StoreDepartment d
    ON d.DepartmentId = p.ParentId

The only thing this won't tell you is the level. I'm not sure how badly you need that. If you don't, this should perform way better than the recursive version; if you do, it looks like Jose's query is OK for that (judging by a quick glance).