За да предпазите алгоритъма за преминаване от връщане към вече посетени ръбове, човек наистина може да запази посетените ръбове някъде. Както вече разбрахте, няма да постигнете голям успех с конкатенация на низове. Съществуват обаче и други приложими техники за "конкатенация на стойности"...
Трябва да имате на ваше разположение една удобна колекция от скалари на ниво схема:
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
;
Бележки
- Обработих предварително насочената графика в ненасочена чрез
union-ing набор от обратни ръбове към входа. Това трябва да направи предикатите за рекурсивно преминаване по-лесни за четене. Единствено за моите цели за по-лесно четене+запис на SQL. Не е нужно да правите това, разбира се. - Спомням си, че опитах нещо подобно преди няколко години на Oracle 11.2. И си спомням, че се проваляше, макар че не помня защо. На 12.2 вървеше добре. Просто опитайте и с 11g; Нямам наличен.
- Тъй като всяка итерация прави, в допълнение към вътрешното свързване на преминаването, също анти-съединяване, искрено се съмнявам, че това ще бъде по-ефективно. Със сигурност обаче решава проблема с намаляването на броя на рекурсивните вмъквания.
- Ще трябва да разрешите желаната поръчка сами, както вероятно сте разбрали от моите коментари. :-)
Ограничаване на преразгледаните ръбове до нула
В 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
Бележки
- Отново не положих никакви усилия да запазя поръчката, която поискахте, тъй като казахте, че не е толкова важно.
- Това прави множество (точно 5 за вашите примерни входни данни) SQL обиколки до
edgeмаса. Това може или не може да бъде по-голям удар в производителността в сравнение с решението с чист SQL с излишно посещение на границите. Тествайте правилно повече решения, вижте кое работи най-добре за вас. - Тази конкретна част от кода ще работи на 12c и по-нови версии. За 11g и по-ниски ще трябва да декларирате
rec_outputиarr_outputтипове на ниво схема.
