Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

adjacency model + rec. CTE to determine leaf

Posted on 2009-07-02
6
Medium Priority
?
499 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
Get free NFR key for Veeam Availability Suite 9.5

Veeam is happy to provide a free NFR license (1 year, 2 sockets) to all certified IT Pros. The license allows for the non-production use of Veeam Availability Suite v9.5 in your home lab, without any feature limitations. It works for both VMware and Hyper-V 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 2000 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

NFR key for Veeam Agent for Linux

Veeam is happy to provide a free NFR license for one year.  It allows for the non‑production use and valid for five workstations and two servers. Veeam Agent for Linux is a simple backup tool for your Linux installations, both on‑premises and in the public cloud.

Question has a verified solution.

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

In this article we will learn how to fix  “Cannot install SQL Server 2014 Service Pack 2: Unable to install windows installer msi file” error ?
Windocks is an independent port of Docker's open source to Windows.   This article introduces the use of SQL Server in containers, with integrated support of SQL Server database cloning.
This videos aims to give the viewer a basic demonstration of how a user can query current session information by using the SYS_CONTEXT function
Via a live example, show how to set up a backup for SQL Server using a Maintenance Plan and how to schedule the job into SQL Server Agent.

636 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