All Forums Database
edberg 1 post Joined 01/15
13 Jan 2015
Lowest Child in recusive query

Hi,

I have following input:

Input:

Child ID Parent ID
123 NULL
456 123
789 456
870 456
985 870

I am trying to populate lowest level child with path and depth...Output should be:

Child ID Parent ID Last Child Path Depth
123 NULL 789 /123 1
456 123 789 /123/456 2
789 456 789 /123/456/789 3

123 NULL 985 /123 1
456 123 985 /123/456 2
870 456 985 /123/456/870 3
985 870 985 /123/456/870/985 4
 
 
I tried creating multiple cte's in a with class but its not allowing.
Any suggestions.Thanks.

ulrich 816 posts Joined 09/09
14 Jan 2015

Below some code which seems to do what you want.
The idea is to create first a tmp table with all the leaf (lowest childs) and the complete path to this leave - using a recurisve query
Next you cross join the root with this temp table and use this as the base for the nex recursive query.
In the second recursive query you need the complete path to filter not wanted pathes...
Ulrich

create volatile table pc 
(
r_child smallint,
r_parent  smallint
) primary index (r_child)
on commit preserve rows;

insert into pc values (123,null);
insert into pc values (456, 123);
insert into pc values (789 ,456);
insert into pc values (870 ,456);
insert into pc values (985 ,870);

create volatile table leaf 
(
r_child smallint,
r_fullpath varchar(1000)
) unique primary index (r_child)
on commit preserve rows;

insert into leaf
with recursive base (r_child, r_fullpath)
as
(
select r_child, 
               cast('/'!!trim(r_child) as varchar(1000))
from pc as o
where not exists (select * 
                                    from pc as i
									where o.r_parent = i.r_child)
union all
select c.r_child,
               b.r_fullpath !! '/' !! trim(c.r_child)
from base b
           join 
		   pc c 
		   		on b.r_child = c.r_parent
)
select *
from base o
where not exists (select * 
                                    from pc as i
									where o.r_child = i.r_parent)


with recursive base (r_child, r_parent, r_leaf, r_fullpath, r_path, r_level)
as 
(
select r.r_child, 
               r.r_parent, 
			   l.r_child, 
			   l.r_fullpath,
			   cast('/'!!trim(r.r_child) as varchar(1000)), 
			   1
from
(
select *
from pc as o
where not exists (select * 
                                    from pc as i
									where o.r_parent = i.r_child)
) as r
cross join 
(
select *
from leaf
) as l
union all
select c.r_child, 
               c.r_parent, 
			   b.r_leaf, 
			   b.r_fullpath,
			   b.r_path !! '/' !! trim(c.r_child),
			   b.r_level + 1
from base b
           join 
		   pc c
		   	 on b.r_child = c.r_parent
where b.r_fullpath like b.r_path !! '/' !! trim(c.r_child) !! '%' 
)
select *
from base
order by 3,5

 

feel free to donate bitcoin:12kgAUHFUqvG2sQgaRBXFhCwyf9HXdkGud

Rohan_Sawant 55 posts Joined 07/14
14 Jan 2015

Hi Edberg,
 
Please find the below query.

/*Creating test data*/
CREATE SET VOLATILE TABLE VT_TEST_DATA ,NO FALLBACK ,
CHECKSUM = DEFAULT,
DEFAULT MERGEBLOCKRATIO,
NO LOG
(
  CHILD_ID INTEGER,
  PARENT_ID INTEGER
)
PRIMARY INDEX (CHILD_ID,PARENT_ID)
ON COMMIT PRESERVE ROWS;

INSERT INTO VT_TEST_DATA VALUES (123,NULL);
INSERT INTO VT_TEST_DATA VALUES (456,123);
INSERT INTO VT_TEST_DATA VALUES (789,456);
INSERT INTO VT_TEST_DATA VALUES (870,456);
INSERT INTO VT_TEST_DATA VALUES (985,870);
/*Completed creating test data*/

/*Creating a sequence for determining relationship*/
CREATE MULTISET VOLATILE TABLE VT_TEST_DATA_SEQUENCE, NO FALLBACK , NO LOG,
CHECKSUM = DEFAULT,
DEFAULT MERGEBLOCKRATIO
AS
(
  SELECT
    B.LOWEST_ID
  , A.CHILD_ID
  , A.PARENT_ID
  , ROW_NUMBER() OVER (PARTITION BY LOWEST_ID ORDER BY A.CHILD_ID ASC) AS ROW_NUM
  FROM
    VT_TEST_DATA A
  , ( 	
	  	SELECT
		  A.CHILD_ID AS LOWEST_ID
		FROM
		  VT_TEST_DATA A
		WHERE
		  A.CHILD_ID NOT IN 
		  (
		  	SELECT COALESCE(PARENT_ID,'')
		  	FROM
		  		VT_TEST_DATA
		  )
	) B
)
WITH DATA
PRIMARY INDEX (LOWEST_ID,CHILD_ID,PARENT_ID)
ON COMMIT PRESERVE ROWS;

/*Determining relationship*/
CREATE MULTISET VOLATILE TABLE VT_PARENT_CHILD, NO FALLBACK , NO LOG,
CHECKSUM = DEFAULT,
DEFAULT MERGEBLOCKRATIO
AS
(
	WITH RECURSIVE REC_CHILD_PARENT 
	( 
	  LOWEST_ID
	, CHILD_ID
	, PARENT_ID
	, ROW_NUM
	, LAST_CHILD_PATH 
	, DEPTH
	)  
	AS
	( 
		SELECT	
		  LOWEST_ID
		, CHILD_ID
		, PARENT_ID
		, ROW_NUM
		, CAST(CHILD_ID AS VARCHAR(1000)) AS LAST_CHILD_PATH
		, 1 AS DEPTH
		FROM 
		  VT_TEST_DATA_SEQUENCE
		WHERE
		  ROW_NUM = 1
		UNION ALL
		SELECT	
		  B.LOWEST_ID
		, B.CHILD_ID
		, B.PARENT_ID
		, B.ROW_NUM
		, A.LAST_CHILD_PATH || '/' || CAST(B.CHILD_ID AS VARCHAR(1000)) AS LAST_CHILD_PATH
		, A.DEPTH + 1 AS DEPTH_1
		FROM 
		  REC_CHILD_PARENT A
		JOIN
		  VT_TEST_DATA_SEQUENCE B
		ON A.CHILD_ID = B.PARENT_ID
	) 	 
	SELECT	
	DISTINCT
	  LOWEST_ID
	, CHILD_ID
	, PARENT_ID
	, LAST_CHILD_PATH
	, DEPTH
	FROM
	  REC_CHILD_PARENT
)
WITH DATA
PRIMARY INDEX (CHILD_ID,PARENT_ID)
ON COMMIT PRESERVE ROWS;

/*Removing wrong relations and here is your output*/
SELECT
  A.CHILD_ID
, A.PARENT_ID
, CAST(A.LOWEST_ID AS VARCHAR(1000)) || '/' || A.LAST_CHILD_PATH
, A.DEPTH
FROM
	VT_PARENT_CHILD A
INNER JOIN
(
	SELECT
	  LOWEST_ID
	, LAST_CHILD_PATH
	, MAX(DEPTH) OVER (PARTITION BY LOWEST_ID ORDER BY DEPTH DESC) AS MAX_DEPTH
	FROM
	  VT_PARENT_CHILD
	WHERE
	  LAST_CHILD_PATH LIKE '%' || CAST(LOWEST_ID AS VARCHAR(1000))
) B
ON	A.LOWEST_ID = B.LOWEST_ID
WHERE
  B.LAST_CHILD_PATH LIKE A.LAST_CHILD_PATH || '%'
ORDER BY A.LOWEST_ID,A.DEPTH;

 
Thanks,
Rohan Sawant

dnoeth 4628 posts Joined 11/04
14 Jan 2015

Nice variation of a path through a hierarchy :-)
Following CTE (based on Rohan's DDL) traverses bottom-up, thus resulting in inverted level counts and paths. Both are then fixed in the final select. 

WITH RECURSIVE cte (Child_ID, PARENT_ID, Last_Child, PATH, LEVEL) AS
 (
   SELECT
      Child_ID
      ,PARENT_ID
      ,Child_ID
      ,CAST('/' || TRIM(Child_ID) AS VARCHAR(1000))
      ,1 (BYTEINT) -- -> max recursion level 127
   FROM VT_TEST_DATA AS t
   WHERE NOT EXISTS -- start with the leaf nodes only
         (
           SELECT * FROM VT_TEST_DATA AS t2
           WHERE t.Child_id = t2.PARENT_ID
         )

   UNION ALL

   SELECT 
      d.Child_ID
      ,d.PARENT_ID
      ,cte.Last_child
      ,'/' || TRIM(d.Child_ID) || cte.PATH -- build the path backwards
      ,LEVEL + 1
   FROM VT_TEST_DATA AS d
   JOIN cte
     ON cte.PARENT_ID = d.Child_ID
 )
SELECT
   parent_id
   ,child_id
   ,last_child
   -- extract the path down to the current child
   ,SUBSTRING(maxPath FROM 1 FOR INSTR(maxPath || '/', '/',1,depth +1) - 1) AS PATH
   ,depth
FROM
 (
   SELECT
      parent_id
      ,child_id
      ,last_child
      -- full path down to the leaf node only
      ,MAX(CASE WHEN parent_id IS NULL THEN PATH end) OVER (PARTITION BY last_child) AS maxPath
      -- switch numbering
      ,MAX(LEVEL) OVER (PARTITION BY last_child) - LEVEL + 1 AS depth
   FROM cte
 ) AS dt
ORDER BY Last_child, depth;

 

Dieter

You must sign in to leave a comment.