adjacency model + rec. CTE to determine leaf

I have a table that uses the adjacency approach to model hierarchies:

ItemId      ItemName      ParentId
5      parent1  NULL
6      c2 5
7      c3 6
8      c1 5
9      parent2 NULL
10      c5 9
11      c6 10
12      c4 9

This query determines the level of each node in the tree:

with Hierachy(ItemId, ItemName, ParentId, Level) as
(
      select ItemId, ItemName, ParentId, 0 as Level
      from Items e  
      WHERE ParentID IS NULL
      union all  
      select e.ItemId, e.ItemName, e.ParentId, eh.Level + 1
      from Items e inner join Hierachy eh on e.ParentId = eh.ItemId
)
select ItemId, ItemName, ParentId, Level from Hierachy

I am interested in determining whether a node is a leaf or not. Is there an easy way to do this? Otherwise, I would have to implement a tie-breaker using correlated sub queries ...

Thanks.

Best wishes,

Christian
csetzkornAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Kevin CrossChief Technology OfficerCommented:
By leaf, you mean it has no children of its own correct.  If so, then you can tell a leaf if there is not a record that notes its id as a parentid.
SELECT ItemId, ItemName, ParentId
FROM Items i
WHERE NOT EXISTS (
   SELECT 1
   FROM Items p
   WHERE p.ParentId = i.ItemID
);

Open in new window

0
Racim BOUDJAKDJIDatabase Architect - Dba - Data ScientistCommented:
<<I am interested in determining whether a node is a leaf or not. Is there an easy way to do this?>>
A more correct and simple to maintain way to represent hierarchies in relational perspective is the following.

item
name        
----------
parent1        
c2                
c3                
c1                
parent2        
c4                                
c5                
c6                

item_lineage
parent          child
-----------------------
parent1         c1
parent1         c2
c2                 c3
parent2         c5
parent2         c4
c5                 c6


<<I am interested in determining whether a node is a leaf or not.>>
With above design:

> you can test whether an item is a leaf simply by using the exists function

if exists(select 1 from lineage where child = 'identifier of the leaf')

> you *can* have many parent for the same child
> you can actually (if you want to) have a specific item belong to several hierarchies at different level of depth.
you can determine the level of a node simply by running


declare @counter int, @item varchar(30)
set @counter = 0
set @item = 'c6'
while exist(select 1 from lineage where child = @item )
begin
         set @counter = @counter + 1
         select @item = parent from lineage where child = @item
end

returns 2...

Hope this helps...
0
csetzkornAuthor Commented:
Thanks. That makes sense. This is what I have so far:

with Hierachy(ItemId, ItemName, ParentId, Level) as
(
      select ItemId, ItemName, ParentId, 0 as Level
      from Items e  
      WHERE ParentID IS NULL
      union all  
      select e.ItemId, e.ItemName, e.ParentId, eh.Level + 1
      from Items e inner join Hierachy eh on e.ParentId = eh.ItemId
)
select
ItemId,
ItemName,
ParentId,
Level,
case when (select count(*) from Items as i where h.itemid = i.parentid) > 0 then 'false' else 'true' end as isLeaf
from Hierachy as h
order by itemid

is there anything that can be optimised?

C
0
10 Tips to Protect Your Business from Ransomware

Did you know that ransomware is the most widespread, destructive malware in the world today? It accounts for 39% of all security breaches, with ransomware gangsters projected to make $11.5B in profits from online extortion by 2019.

csetzkornAuthor Commented:
Racimo,

Thanks. I am usually also using nested set approach. Would have to investigate how to get this done using NHibernate. But thanks anyway.

C
0
Racim BOUDJAKDJIDatabase Architect - Dba - Data ScientistCommented:
<<Thanks. I am usually also using nested set approach. Would have to investigate how to get this done using NHibernate. But thanks anyway.>>
This should not be an issue since Hibernate is only a query formulator.  And since you already know this approach,  I suggest you consider forgetting the other.   You noticed how this *adjacency* approach makes things more complex to establish even the simplest information.  Alternatively, the other way makes it (almost) a child's game.  

Anyway good luck...
0
Kevin CrossChief Technology OfficerCommented:
Looks fine.  For large data sets, you can consider casting as BIT so that returned data is smaller footprint.

cast(case when (select count(*) from Items as i where h.itemid = i.parentid) > 0 then 0 else1 end as BIT) as isLeaf
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Microsoft SQL Server

From novice to tech pro — start learning today.