For SQL Hierarchical Data, How To Show Only Tree Branches Including Certain Type Of Entities And Discard Others

If you have a tree of entities represented into a SQL database into parent-child relation as in the image above, you may need to be able to view only the tree branches which include a certain type of entities
and discard the branches which don't include this type.

For example, let's have a look on the tree above and assume that we need to show only the branches which include the "J" type of entities. For this to happen, then we need to transfer the above tree into the one below.

How to do this in SQL?
To be able to answer this question, we first need to know how our mind does it. Our mind does a lot of processing and computing in an efficient way which makes us think that it is so easy, but is it that easy?

Assume that we have these types of entities in our tree.

And the real entities instances in our database are as in the image below.

Which means that our entities are in the tree form as in the image below.

Now, let's assume that we need to view only the tree branches including the "J" type. To do this manually just by a piece of paper and a pen, we look at the leaf entities in the tree. By leaf I mean the entities which have no children. Then, up from there we trace each branch and if a branch doesn't include a "J", we erase this branch till we finally get the final tree.

To do this in a more systematic approach, we can first locate our leaf entities. Then, we go up one level for each one of the leaf entities, then another one level up and so on till we reach the top of the tree. This could be illustrated as in the table below.

 

As you can see, we first started with the leaf entities and it took us five iterations to reach the top most of the tree. But why do we need to do that?

We did that because we already know the sequence of the system entities types, for example we know that if the leaf entity of a branch is "T", then this branch will not have a "J" as "J" comes after "T". So, we needed to trace back each branch to decide which branch to keep and which to discard.

Does that mean that every branch doesn't end with "J" should be completely deleted up to the top of the tree? No, as you can see in our tree above, there is a branch which ends with "T4", we are sure that this branch will not include a "J" but if we delete this branch up to the "C" entity, we will lose "P2" which has valid "J" children.

So, to get it right you can think of it as a voting system. Each entity in the tree should vote on whether its parent should be kept or no. Finally, we sum the voting on each parent and know if at least one child needs this parent, if not, we can discard this parent without any problems or loosing any valid branches.

So, each entity of the leaf entities should already know if its parent should be kept or not, so in our example, if the leaf entity is a "J", then its parent should be voted a "1". But if the leaf entity is a "S" or "T" or "P" or "C" then the parent should be voted a "0".

So, this leads us to the result in the image below.

Now, we need to sum the votes of each entity to know which entities to keep and which to discard. After doing the summation, we will get the result as in the image below.

So, to make sure the logic we applied here is valid, let's return to the tree diagram and highlight the entities which got a sum of "0" votes. These entities are decided by all child entities to be useless and disposable.

Are these the entities we can delete from the tree to make sure every branch includes a "J" entity? Yes, those are the ones and by deleting them we get the final tree as in the image below.

So, now we are sure that the logic we applied is valid but can we apply this complex logic in SQL?

Applying the same logic in SQL

--Creating the Entities table.
--This table contains the main entities in the system with
--their internal parent-child relations.
DECLARE @Entities AS Table
(
 Id INT
 , Name NVARCHAR(100)
 , ParentId INT
)

--Inserting entites into the @Entities table
INSERT INTO @Entities
(
 Id
 , Name
 , ParentId
)
VALUES
(1, 'Company', NULL)
, (2, 'Project Leader', 1)
, (3, 'Team Leader', 2)
, (4, 'Senior', 3)
, (5, 'Junior', 4)



--Creating the AggregatedEntities table.
--This table contains each main entity and its children
--recursively down to the end of the tree.
DECLARE @AggregatedEntities AS Table
(
 EntityId INT
 , EntityName NVARCHAR(100)
 , ChildId INT
)

;WITH AggregatedEntitiesTVP(EntityId, EntityName, ChildId) AS
(
 SELECT Parent.Id AS EntityId
 , Parent.Name AS EntityName
 , Child.Id AS ChildId
 FROM @Entities AS Parent
 
 INNER JOIN @Entities AS Child
 ON Child.ParentId = Parent.Id

 UNION 

 SELECT Parent.Id AS EntityId
 , Parent.Name AS EntityName
 , Parent.Id AS ChildId
 FROM @Entities AS Parent

 UNION ALL

 SELECT AggregatedEntitiesTVP.EntityId AS EntityId
 , AggregatedEntitiesTVP.EntityName AS EntityName
 , Entities.Id AS ChildId
 FROM AggregatedEntitiesTVP
 
 INNER JOIN @Entities AS Entities
 ON (Entities.ParentId = AggregatedEntitiesTVP.ChildId)
)

INSERT INTO @AggregatedEntities
(
 EntityId
 , EntityName
 , ChildId
)
SELECT DISTINCT EntityId
, EntityName
, ChildId
FROM AggregatedEntitiesTVP
ORDER BY EntityId, ChildId



--Creating AllEntities table.
--This table includes the created instances of the
--main entities.
DECLARE @AllEntities AS Table
(
 Id INT
 , Name NVARCHAR(100)
 , ParentId INT
 , TypeId INT
)

INSERT INTO @AllEntities
(
 Id
 , Name
 , ParentId
 , TypeId
)
VALUES
(1, 'C', NULL, 1)
, (2, 'P1', 1, 2)
, (3, 'P2', 1, 2)
, (4, 'T1', 2, 3)
, (5, 'T2', 2, 3)
, (6, 'T3', 2, 3)
, (7, 'T4', 3, 3)
, (8, 'T5', 3, 3)
, (9, 'S1', 4, 4)
, (10, 'S2', 4, 4)
, (11, 'S3', 5, 4)
, (12, 'S4', 6, 4)
, (13, 'S5', 6, 4)
, (14, 'S6', 8, 4)
, (15, 'S7', 8, 4)
, (16, 'J1', 10, 5)
, (17, 'J2', 10, 5)
, (18, 'J3', 11, 5)
, (19, 'J4', 11, 5)
, (20, 'J5', 14, 5)
, (21, 'J6', 14, 5)



--Declaring a variable to hold the required ensured entity type
--Each branch in the tree should include this entity type, otherwise,
--the whole branch will be excluded from the final result
DECLARE @EnsuredEntityType AS NVARCHAR(10)
SET @EnsuredEntityType = 'Junior'



;WITH EnsuredEntityTree(Id, Name, ParentId, Voting) AS
(
 --Strating with the leaf entities on the tree as the seed
 SELECT parent.Id
 , parent.Name
 , parent.ParentId
 , CASE
 WHEN 
 (
 parent.TypeId IN (SELECT ChildId FROM @AggregatedEntities WHERE EntityName = @EnsuredEntityType)
 ) THEN 1
 ELSE 0 END AS Voting
 FROM @AllEntities AS parent
 
 LEFT OUTER JOIN @AllEntities AS children
 ON children.ParentId = parent.Id
 
 WHERE children.Id IS NULL

 UNION ALL

 SELECT parent.Id
 , parent.Name
 , parent.ParentId
 , et.Voting --the same voting from the original seed object
 FROM @AllEntities AS parent
 INNER JOIN EnsuredEntityTree AS et
 ON et.ParentId = parent.Id
)



SELECT DISTINCT Id, Name, ParentId
FROM EnsuredEntityTree
GROUP BY Id, ParentId, Name
HAVING SUM(Voting) > 0

Finally, I hope you find this useful someday.
Good luck.