Lowest Child in recusive query

Database
N/A

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.

3 REPLIES
Supporter

Re: Lowest Child in recusive query

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
Enthusiast

Re: Lowest Child in recusive query

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

Senior Apprentice

Re: Lowest Child in recusive query

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;