Solved

adjacency model + rec. CTE to determine leaf

Posted on 2009-07-02
6
465 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
Windows Server 2016: All you need to know

Learn about Hyper-V features that increase functionality and usability of Microsoft Windows Server 2016. Also, throughout this eBook, you’ll find some basic PowerShell examples that will help you leverage the scripts in your environments!

 

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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Everyone has problem when going to load data into Data warehouse (EDW). They all need to confirm that data quality is good but they don't no how to proceed. Microsoft has provided new task within SSIS 2008 called "Data Profiler Task". It solve th…
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.
This video shows, step by step, how to configure Oracle Heterogeneous Services via the Generic Gateway Agent in order to make a connection from an Oracle session and access a remote SQL Server database table.
This video shows how to set up a shell script to accept a positional parameter when called, pass that to a SQL script, accept the output from the statement back and then manipulate it in the Shell.

730 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