I have a table that looks like this:
/* input */
-- | parent | child |
-- | ------ | ----- |
-- | 1 | 2 |
-- | 2 | 3 |
-- | 3 | 4 |
-- | 5 | 6 |
-- | 6 | 7 |
-- | 8 | 9 |
-- | 10 | 11 |
and I want create something that looks like this:
/* output */
-- | person | first_ancestor |
-- | ------ | --------------- |
-- | 1 | 1 |
-- | 2 | 1 |
-- | 3 | 1 |
-- | 4 | 1 |
-- | 5 | 5 |
-- | 6 | 5 |
-- | 7 | 5 |
-- | 8 | 8 |
-- | 9 | 8 |
-- | 10 | 10 |
-- | 11 | 10 |
If I were using bigquery, it would be simple using a recursive CTE
-- recursive CTE: get the first ancestor of each record
with recursive table_data as (
-- populate data
select 1 as parent, 2 as child union all
select 2,3 union all
select 3,4 union all
select 5,6 union all
select 6,7 union all
select 8,9 union all
select 10,11
),
base_records as (
-- make the base case (get all records that are not children of another record)
-- also has the effect of filtering out cyclic groups (e.g. 1->2->->1)
select parent as first_ancestor,parent as person
from table_data
where parent not in (select child from table_data)
),
lookup_table as (
-- first start with the base case...the first ancestor
select person,first_ancestor from base_records
union all
-- recursively add descendants, noting the first ancestor to that descendant
select table_data.child as person,lookup_table.first_ancestor
from lookup_table
join table_data
on lookup_table.person = table_data.parent
)
select person,first_ancestor from lookup_table
order by first_ancestor,person
is there 1) some function that has recursion in databricks (spark sql or pyspark), or 2) a canonical way to do this?
I can brute force this by coding an arbitrary length join (join table_data t1 to table_data t2 to table_data t3 ...) but was wondering if there's a less inefficient/more dynamic way. I know nothing about graph databases or if the proper solution lies in them.
Thank you so much 🙂
