各ノードに 1 回だけアクセスする再帰クエリを使用した Oracle SQL の有向グラフ

トラバース アルゴリズムが既に訪れたエッジに戻らないようにするために、実際に訪れたエッジをどこかに保持することができます。すでにわかっているように、文字列連結ではあまり成功しません。ただし、他にも使用可能な「値の連結」テクニックがあります...

便利なスカラーのスキーマ レベルのコレクションを 1 つ用意する必要があります。

create or replace type arr_strings is table of varchar2(64);

そして、各反復で訪問したエッジをそのコレクションに収集できます:

with nondirected$ as (
    select from_id, to_id, from_id||'-'||to_id as edge_desc
    from edge
    where from_id != to_id
    union all
    select to_id, from_id, from_id||'-'||to_id as edge_desc
    from edge
    where (to_id, from_id) not in (
            select from_id, to_id
            from edge
        )
),
graph$(lvl, from_id, to_id, edge_desc, visited_edges) as (
    select 1, from_id, to_id, edge_desc,
        arr_strings(edge_desc)
    from nondirected$ R
    where from_id in (&nodes)
    --
    union all
    --
    select
        lvl+1,
        Y.from_id, Y.to_id, Y.edge_desc,
        X.visited_edges multiset union arr_strings(Y.edge_desc)
    from graph$ X
        join nondirected$ Y
            on Y.from_id = X.to_id
    where not exists (
            select 1
            from table(X.visited_edges) Z
            where Y.edge_desc = Z.column_value
        )
)
search breadth first by edge_desc set order_id
    cycle edge_desc set is_cycle to 1 default 0,
ranked_graph$ as (
    select C.*,
        row_number() over (partition by edge_desc order by lvl, order_id) as rank$
    from graph$ C
--    where is_cycle = 0
)
select *
from ranked_graph$
--where rank$ <= 1
order by lvl, order_id
;

メモ

再訪エッジをゼロに制限

SQL では、できません。あなたが言及したPostgreSQLソリューションはそれを行います。ただし、Oracle ではできません。トラバーサル結合ごとに、他のすべてのトラバーサル結合の行をテストする必要があります。そして、それはある種の集計または分析を意味します... Oracle はこれを禁止し、ORA 例外をスローします。

PLSQL が役に立ちますか?

ただし、PL/SQL で実行できます。どの程度のパフォーマンスが期待されるかは、DB からのエッジのプリフェッチに費やすメモリの量と、「現在の」ノードからグラフをトラバースするために必要な SQL ラウンドトリップの数、または使用する意思があるかどうかによって異なります。通常の arr_output に対して逆結合する場合と比較して、訪問したノードをエッジごとにインデックス付けされた派手なコレクションに保持するためのさらに多くのメモリ コレクション l_visited_nodes .複数の選択肢があります。賢明に選択してください。

とにかく、SQL エンジンを多用する最も単純なシナリオでは、これが探しているコードかもしれません...

create or replace
package pkg_so_recursive_traversal
is


type rec_output                     is record (
    from_id                             edge.from_id%type,
    to_id                               edge.to_id%type,
    lvl                                 integer
);
type arr_output                     is table of rec_output;


function traverse_a_graph
    ( i_from                        in arr_strings
    , i_is_directed                 in varchar2 default 'NO' )
    return arr_output
    pipelined;


end pkg_so_recursive_traversal;
/
create or replace
package body pkg_so_recursive_traversal
is


function traverse_a_graph
    ( i_from                        in arr_strings
    , i_is_directed                 in varchar2 )
    return arr_output
    pipelined
is
    l_next_edges                    arr_output;
    l_current_edges                 arr_output;
    l_visited_edges                 arr_output := arr_output();
    l_out                           rec_output;
    i                               pls_integer;
    l_is_directed                   varchar2(32) := case when i_is_directed = 'YES' then 'YES' else 'NO' end;
begin
    select E.from_id, E.to_id, 0
    bulk collect into l_next_edges
    from table(i_from) F
        join edge E
            on F.column_value in (E.from_id, case when l_is_directed = 'YES' then null else E.to_id end)
    where E.from_id != E.to_id;

    l_out.lvl := 0;

    loop
        dbms_output.put_line(l_next_edges.count());
        exit when l_next_edges.count() <= 0;
        l_out.lvl := l_out.lvl + 1;

        -- spool the edges to output
        i := l_next_edges.first();
        while i is not null loop
            l_out.from_id := l_next_edges(i).from_id;
            l_out.to_id := l_next_edges(i).to_id;
            pipe row(l_out);
            i := l_next_edges.next(i);
        end loop;

        l_current_edges := l_next_edges;
        l_visited_edges := l_visited_edges multiset union l_current_edges;

        -- find next edges
        select unique E.from_id, E.to_id, 0
        bulk collect into l_next_edges
        from table(l_current_edges) CE
            join edge E
                on CE.to_id in (E.from_id, case when l_is_directed = 'YES' then null else E.to_id end)
                or l_is_directed = 'NO' and CE.from_id in (E.from_id, E.to_id)
        where E.from_id != E.to_id
            and not exists (
                select 1
                from table(l_visited_edges) VE
                where VE.from_id = E.from_id
                    and VE.to_id = E.to_id
            );
    end loop;

    return;
end;


end pkg_so_recursive_traversal;

/

A の開始ノードが呼び出されたとき グラフが無向であると考えると...

select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
        i_from => arr_strings('A'),
        i_is_directed => 'NO'
    ));

... それは ...

FROM_ID    TO_ID             LVL
---------- ---------- ----------
A          B                   1
C          A                   1
C          E                   2
B          D                   2
C          F                   2
E          B                   2
G          D                   3
H          F                   3
G          I                   4

メモ