how to filter a directed acyclic graphs relationship

See more:

SQL-Server-2005

SQL-Server

trees

I'm trying to find a way to get a most granular vertex based on criteria in the path of the graph.

Giving the following tree:

and the following metadata description: (test)

label     h
---------------
h         1
a         1
p         2
b         2
s         3
q         4
z         4

and the following relationship table: (test_rel)

l       p          Hops
-----------------------------
H       Null            Null
A       Null            Null
P       H               1
B       A               1
S       P               1
S       B               1
Q       S               1
Z       S               1
Q       P               2
Q       H               3
Z       B               2
Z       A               3
S       H               2
S       A               2

Note: there is no route from z to h or q to a.

I'm trying to write a SQL query that will allow me have a temp table that define a level in the graph, and the ID (or 0 for all) and find all the children.

Here is what I came up with (which is not working) :(

    -- Insert statements for procedure here
create table #aa (id varchar(10), h int)
insert into #aa values ('h',1)
insert into #aa values ('p',2)
insert into #aa values ('0',3)
insert into #aa values ('0',4)
;


WITH GHierarchy (id, parentID, HierarchyLevel) AS
(
   -- Base case
   SELECT distinct 
		l,
		
		'',
		
		1
   FROM test_rel inner join test on label = l
	inner join #aa on test_rel.l = case when #aa.id='0' then test.label else #aa.id end  and #aa.h = 1
   
   WHERE 
	
	test.h = 1 
	
	
   UNION ALL

   -- Recursive step
   SELECT
      e.l,
      e.p,
      eh.HierarchyLevel + 1 AS HierarchyLevel
   FROM GHierarchy eh inner join test_rel e on eh.id = e.p
	
		inner join test_rel hops on hops.p = eh.id and hops.hops = 4 - eh.HierarchyLevel 
		inner join #aa on  e.l = case when #aa.id='0' then e.l else #aa.id end  and HierarchyLevel+1 = #aa.h
	where e.hops = 1
	
	  

)

select distinct * from GHierarchy
order by HierarchyLevel

drop table #aa

With this query - I get both 'q' and 'z' however - there is no path for h->p->s->z

Thanks!!

Rimon