For SQL Hierarchical Data, How To Show Only Tree Branches Including Certain Type Of Entities And Discard Others
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.
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.
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.
