Recursive CTEs for graph traversal

connect-by-oracle.sql

/* flatten bus route */
with bus_stops(from_stop, to_stop) as (
              select 'BM',  'WQS' from dual
    union all select 'CR',  'BM'  from dual
    union all select 'CS',  'LL'  from dual
    union all select 'GG',  'CS'  from dual
    union all select 'LL',  'OS'  from dual
    union all select 'OS',  'CR'  from dual
    union all select 'WQS', 'GG'  from dual
)

select
    max( substr(sys_connect_by_path(from_stop, ' - '), 4) ) as route
from bus_stops
start with from_stop = 'BM'
connect by nocycle prior to_stop = from_stop
;


/* find all related family members */
create table people as
              select 100 as parent_id, 101 as child_id from dual
    union all select 100, 102 from dual
    union all select 101, 103 from dual
    union all select 101, 104 from dual
    union all select 101, 105 from dual
    union all select 106, 107 from dual
    union all select 106, 108 from dual
    union all select 103, 109 from dual
    union all select 103, 110 from dual
    union all select 103, 105 from dual
    union all select 104, 105 from dual
    union all select 107, 111 from dual
    union all select 107, 112 from dual
    union all select 108, 112 from dual
    union all select 113, 114 from dual
    union all select 113, 115 from dual
    union all select 114, 116 from dual
    union all select 114, 117 from dual
    union all select 115, 117 from dual
    union all select 118, 119 from dual
    union all select 118, 120 from dual
    union all select 121, 120 from dual
;


with relations(person_id, relation_id) as (
          select parent_id, child_id from people
    union select child_id, parent_id from people
)

select distinct relation_id
from relations
start with person_id = 104
connect by nocycle person_id = prior relation_id
order by relation_id
;

recursive-ctes-graph-traversal.sql

/*
    Recursive CTEs for graph traversal

    DuckDB version: 1.0.0

    Bill Wallis, 2024-10-18
*/


select version();


/* flatten bus route */
with recursive

bus_stops(from_stop, to_stop) as (
    values
        ('BM',  'WQS'),
        ('CR',  'BM'),
        ('CS',  'LL'),
        ('GG',  'CS'),
        ('LL',  'OS'),
        ('OS',  'CR'),
        ('WQS', 'GG')
),

routes(starting_stop, current_stop, route) as (
        select 'BM', 'BM', 'BM'
    union all
        select
            routes.starting_stop,
            bus_stops.to_stop,
            concat_ws(' - ', routes.route, bus_stops.to_stop)
        from routes
            inner join bus_stops
                on  routes.current_stop = bus_stops.from_stop
                and routes.starting_stop != bus_stops.to_stop
)

select max(route) as route
from routes
;


/* find all related family members */
with recursive

people(parent_id, child_id) as (
    values
        (100, 101),
        (100, 102),
        (101, 103),
        (101, 104),
        (101, 105),
        (106, 107),
        (106, 108),
        (103, 109),
        (103, 110),
        (103, 105),
        (104, 105),
        (107, 111),
        (107, 112),
        (108, 112),
        (113, 114),
        (113, 115),
        (114, 116),
        (114, 117),
        (115, 117),
        (118, 119),
        (118, 120),
        (121, 120)
),

relations(person_id, relation_id) as (
          select parent_id, child_id from people
    union select child_id, parent_id from people
),

family(person_id, relation_id, seen) as (
        select 104, 104, [104]
    union all
        select
            family.person_id,
            relations.relation_id,
            list_append(family.seen, relations.relation_id)
        from family
            inner join relations
                on  family.relation_id = relations.person_id
                and not array_contains(family.seen, relations.relation_id)

)

select distinct person_id, relation_id
from family
order by all
;

This is part of the following LinkedIn posts:

• https://www.linkedin.com/posts/bill-wallis_sqlwithbill-sql-activity-7253691525191077890-E5Jg
• https://www.linkedin.com/posts/bill-wallis_sqlwithbill-sql-activity-7254023711119347713-M8dj