Solved

adjacency model + rec. CTE to determine leaf

Posted on 2009-07-02
6
469 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
0
Comment
Question by:csetzkorn
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
  • 2
6 Comments
 
LVL 60

Expert Comment

by:Kevin Cross
ID: 24764327
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
 
LVL 23

Expert Comment

by:Racim BOUDJAKDJI
ID: 24764412
<<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
 

Author Comment

by:csetzkorn
ID: 24764440
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
Webinar: Aligning, Automating, Winning

Join Dan Russo, Senior Manager of Operations Intelligence, for an in-depth discussion on how Dealertrack, leading provider of integrated digital solutions for the automotive industry, transformed their DevOps processes to increase collaboration and move with greater velocity.

 

Author Comment

by:csetzkorn
ID: 24764457
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
 
LVL 23

Expert Comment

by:Racim BOUDJAKDJI
ID: 24764553
<<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
 
LVL 60

Accepted Solution

by:
Kevin Cross earned 500 total points
ID: 24764681
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

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction SQL Server Integration Services can read XML files, that’s known by every BI developer.  (If you didn’t, don’t worry, I’m aiming this article at newcomers as well.) But how far can you go?  When does the XML Source component become …
Load balancing is the method of dividing the total amount of work performed by one computer between two or more computers. Its aim is to get more work done in the same amount of time, ensuring that all the users get served faster.
Via a live example, show how to extract information from SQL Server on Database, Connection and Server properties
Viewers will learn how to use the SELECT statement in SQL and will be exposed to the many uses the SELECT statement has.

688 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question