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 回答