We help IT Professionals succeed at work.

adjacency model + rec. CTE to determine leaf

csetzkorn
csetzkorn asked
on
Medium Priority
543 Views
Last Modified: 2012-05-07
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
Comment
Watch Question

Kevin CrossChief Technology Officer
CERTIFIED EXPERT
Most Valuable Expert 2011

Commented:
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

Racim BOUDJAKDJIDatabase Architect - Dba - Data Scientist
CERTIFIED EXPERT

Commented:
<<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...

Author

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

Author

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
Racim BOUDJAKDJIDatabase Architect - Dba - Data Scientist
CERTIFIED EXPERT

Commented:
<<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...
Chief Technology Officer
CERTIFIED EXPERT
Most Valuable Expert 2011
Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)
UNLOCK SOLUTION
Unlock the solution to this question.
Thanks for using Experts Exchange.

Please provide your email to receive a sample view!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.