1

次のように、グラフ検索を実行して、開始点からアクセス可能なすべてのノードを見つけようとしています。

with recursive
  nodes_traversed as (
    select START_NODE ID
    from START_POSITION

    union all
    select ed.DST_NODE
    from EDGES ed
    join nodes_traversed NT
      on (NT.ID = ed.START_NODE)
      and (ed.DST_NODE not in (select ID from nodes_traversed))
  )
select distinct * from nodes_traversed

残念ながら、それを実行しようとすると、エラーが発生します。

再帰 CTE メンバー (nodes_traversed) は、FROM 句でのみ参照できます。

ただし、その「not in select」句は、再帰式にとって重要です。これは、終了点を提供するためです。(それがなければ、無限再帰が得られます。)これは非常に循環的なグラフであるため、この質問に対する受け入れられた回答のように、世代カウントを使用しても役に立ちません。

繰り返し実行するストアド プロシージャを作成せずに、これを回避する方法はありますか?

4

1 に答える 1

2

これがグローバル一時テーブルを使用する私のソリューションです。一時テーブルからのレベルとノードによる再帰を制限しています。大規模なデータセットでどのように機能するかはわかりません。

create procedure get_nodes (
    START_NODE integer)
returns (
    NODE_ID integer)
as
declare variable C1 integer;
declare variable C2 integer;
begin

    /**
    create global temporary table id_list(
        id integer
    );
    create index id_list_idx1 ON id_list (id);
    */
    delete from id_list;


    while ( 1 = 1 ) do
    begin
        select count(distinct id) from id_list into :c1;

        insert into id_list
        select id from
            (
                with recursive nodes_traversed as (
                select :START_NODE AS ID , 0 as Lv
                from  RDB$DATABASE

                union all
                select ed.DST_NODE , Lv+1
                from  edges ed

                join nodes_traversed NT
                  on
                  (NT.ID = ed.START_NODE)
                  and nt.Lv < 5 -- Max recursion level
                  and nt.id not in (select id from id_list)
            )
        select distinct id from nodes_traversed);

        select count(distinct id) from id_list into :c2;
        if (c1 = c2) then break;
    end

    for select distinct  id from id_list into :node_id do
    begin
        suspend ;
    end
end
于 2012-12-10T01:40:44.050 に答える