Để giữ cho thuật toán duyệt không quay trở lại các cạnh đã được truy cập, người ta thực sự có thể giữ các cạnh đã thăm ở đâu đó. Như bạn đã phát hiện ra, bạn sẽ không gặt hái được nhiều thành công với việc nối chuỗi. Tuy nhiên, có sẵn các kỹ thuật "nối giá trị" có thể sử dụng khác ...
Bạn phải có một bộ sưu tập vô hướng cấp giản đồ tiện dụng theo ý của bạn:
create or replace type arr_strings is table of varchar2(64);
Và sau đó, bạn có thể thu thập các cạnh đã truy cập vào bộ sưu tập đó trong mỗi lần lặp lại:
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
;
Ghi chú
- Tôi đã xử lý trước biểu đồ được hướng dẫn đến một biểu đồ không được chuyển hướng bởi
union-ing một tập hợp các cạnh đảo ngược với đầu vào. Điều đó sẽ làm cho các vị từ duyệt đệ quy dễ đọc hơn. Chỉ dành cho mục đích của tôi là đọc + viết SQL dễ dàng hơn. Tất nhiên, bạn không cần phải làm điều đó. - Tôi nhớ mình đã thử một cái gì đó như thế này vài năm trước trên Oracle 11.2. Và tôi nhớ rằng nó đã thất bại, mặc dù tôi không nhớ tại sao. Vào ngày 12.2, nó chạy OK. Chỉ cần thử vào 11g thôi; Tôi không có sẵn một cái.
- Vì mỗi lần lặp lại, ngoài phép nối bên trong truyền tải, còn có một phép nối chống, tôi thực sự nghi ngờ rằng điều này sẽ hiệu quả hơn. Tuy nhiên, nó chắc chắn giải quyết được vấn đề giảm số lượng tổ đệ quy.
- Bạn sẽ phải tự mình giải quyết thứ tự mong muốn, như bạn có thể hiểu từ những nhận xét của tôi. :-)
Giới hạn các cạnh được xem lại bằng 0
Trong SQL, bạn không thể. Giải pháp PostgreSQL mà bạn đã đề cập làm được điều đó. Trong Oracle, tuy nhiên, bạn không thể. Bạn sẽ phải, đối với mỗi phép nối truyền tải, kiểm tra các hàng cho tất cả các phép nối truyền tải khác. Và điều đó có nghĩa là một số loại tổng hợp hoặc phân tích ... mà Oracle cấm và đưa ra một ngoại lệ ORA.
PLSQL để giải cứu?
Tuy nhiên, bạn có thể làm điều đó trong PL / SQL. Nó được cho là có hiệu suất như thế nào, tùy thuộc vào lượng bộ nhớ bạn muốn sử dụng để tìm nạp trước các cạnh từ DB so với bao nhiêu bước tròn SQL mà bạn sẵn sàng thực hiện để duyệt qua biểu đồ từ các nút "hiện tại" hoặc nếu bạn sẵn sàng sử dụng thậm chí nhiều bộ nhớ hơn để giữ các nút đã truy cập trong một bộ sưu tập được lập chỉ mục theo từng cạnh ưa thích so với nếu bạn muốn chống tham gia với arr_output thông thường bộ sưu tập l_visited_nodes . Bạn có nhiều lựa chọn, hãy chọn một cách khôn ngoan.
Dù sao, đối với tình huống đơn giản nhất với việc sử dụng công cụ SQL nặng hơn, đây có thể là mã bạn đang tìm kiếm ...
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;
/
Khi được gọi cho nút bắt đầu của A và coi biểu đồ là vô hướng ...
select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
i_from => arr_strings('A'),
i_is_directed => 'NO'
));
... nó mang lại ...
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
Ghi chú
- Một lần nữa, tôi đã không cố gắng để giữ đơn hàng bạn yêu cầu, vì bạn đã nói rằng điều đó không quan trọng.
- Điều này đang thực hiện nhiều (chính xác là 5 cho các đầu vào ví dụ của bạn) SQL vòng tới
edgebàn. Điều đó có thể có hoặc có thể không phải là một hiệu suất lớn hơn khi so sánh với giải pháp thuần SQL với việc truy cập cạnh dư thừa. Thử nghiệm nhiều giải pháp phù hợp hơn, xem giải pháp nào phù hợp nhất với bạn. - Đoạn mã cụ thể này sẽ hoạt động trên 12c trở lên. Đối với 11g trở xuống, bạn sẽ phải khai báo
rec_outputvàarr_outputcác loại ở cấp giản đồ.
