沿 DAG 的顶点行

Question

目标是从

查询

-- a → b → c → d
-- ↓ ↘   ↘
-- g   e → f
-- ↓
-- h
dag (vertex, successor) as (values
    ('alpha', 'bravo'),
    ('bravo', 'charlie'),
    ('charlie', 'delta'),
    ('delta', null),
    ('alpha', 'echo'),
    ('echo', 'foxtrot'),
    ('bravo', 'foxtrot'),
    ('foxtrot', null),
    ('alpha', 'golf'),
    ('golf', 'hotel'),
    ('hotel', null)
)

进入

'id_foo', 0, 'alpha'
'id_foo', 1, 'bravo'
'id_foo', 2, 'charlie'
'id_foo', 3, 'delta'
'id_bar', 0, 'alpha'
'id_bar', 1, 'bravo'
'id_bar', 2, 'foxtrot'
'id_qux', 0, 'alpha'
'id_qux', 1, 'echo'
'id_qux', 2, 'foxtrot'
'id_fno', 0, 'alpha'
'id_fno', 1, 'golf'
'id_fno', 2, 'hotel'

我可以分两步完成。

with recursive intermediate as (
    select * from (
        with recursive
            dag (vertex, successor) as (values
                ('alpha', 'bravo'),
                ('bravo', 'charlie'),
                ('charlie', 'delta'),
                ('delta', null),
                ('alpha', 'echo'),
                ('echo', 'foxtrot'),
                ('bravo', 'foxtrot'),
                ('foxtrot', null),
                ('alpha', 'golf'),
                ('golf', 'hotel'),
                ('hotel', null)
            ),
            cte as (
                select
                        vertex,
                        successor,
                        1 as length,
                        vertex as path
                    from dag where successor is null
                union all
                select
                        dag.vertex,
                        dag.successor,
                        length + 1,
                        dag.vertex||'→'||path
                    from dag join cte
                    where dag.successor = cte.vertex
            )
        select
            length, path
            from cte
            where vertex = 'alpha'
        -- 3, 'alpha→bravo→charlie→delta'
        -- 3, 'alpha→bravo→foxtrot'
        -- 3, 'alpha→echo→foxtrot'
        -- 4, 'alpha→golf→hotel'
    )
),
cte as (
    select
            length,
            path,
            -1 as "index",
            '' as vertex,
            path||'→' as rest
        from intermediate
    union all
    select
            length,
            path,
            "index" + 1,
            substr(rest, 0, instr(rest, '→')),
            substr(rest, instr(rest, '→') + 1)
        from cte
        where rest != ''
)
select length, path, "index", vertex from cte
where vertex != ''
order by path, "index";

我觉得这样做很浪费。有没有可能没有字符串连接和拆分，没有中间结果集？

目标平台模糊modern SQL。上面的代码已经过测试并使用 SQLite 运行。

Answer 1

with recursive
dag (vertex, successor) as (values
    ('alpha', 'bravo'),
    ('bravo', 'charlie'),
    ('charlie', 'delta'),
    ('delta', null),
    ('alpha', 'echo'),
    ('echo', 'foxtrot'),
    ('bravo', 'foxtrot'),
    ('foxtrot', null),
    ('alpha', 'golf'),
    ('golf', 'hotel'),
    ('hotel', null)
),
head (vertex) as (
        select vertex from dag except select successor from dag
),
paths (row, depth, parent_row, vertex, successor) as (
        select row_number() over (), 1, 0::bigint, dag.vertex, dag.successor
                from head
                join dag on (dag.vertex = head.vertex)
        union all
        select row_number() over (), depth + 1, row, dag.vertex, dag.successor
                from paths
                join dag on (dag.vertex = paths.successor)
),
result (path_id, parent_row, depth, vertex) as (
        select row_number() over (), parent_row, depth, vertex
                from paths
                where successor is null
        union all
        select result.path_id, paths.parent_row, paths.depth, paths.vertex
                from result
                join paths on (paths.row = result.parent_row and paths.depth = result.depth - 1)
)
select path_id, depth, vertex
        from result
        order by 1, 2
;

Postgresql 特定

with recursive
dag (vertex, successor) as (values
        ('alpha', 'bravo'),
        ('bravo', 'charlie'),
        ('charlie', 'delta'),
        ('delta', null),
        ('alpha', 'echo'),
        ('echo', 'foxtrot'),
        ('bravo', 'foxtrot'),
        ('foxtrot', null),
        ('alpha', 'golf'),
        ('golf', 'hotel'),
        ('hotel', null)
),
head (vertex) as (
        select vertex from dag except select successor from dag
),
paths (path, successor) as (
        select array[dag.vertex], dag.successor
                from head
                join dag on (dag.vertex = head.vertex)
        union all
        select array_append(paths.path, dag.vertex), dag.successor
                from paths
                join dag on (dag.vertex = paths.successor)
),
result_paths (path_id, path) as (
        select row_number() over (), path
                from paths
                where successor is null
),
result (path_id, depth, vertex) as (
        select path_id, p.nr, p.elem
                from result_paths
                left join lateral unnest (path) with ordinality as p(elem, nr) on true
)
select * from result
        order by 1,2
;

沿 DAG 的顶点行

rows of vertices along a DAG

sql

common-table-expression

directed-acyclic-graphs