ट्रैवर्सिंग एल्गोरिथम को पहले से देखे गए किनारों पर लौटने से रोकने के लिए, कोई वास्तव में विज़िट किए गए किनारों को कहीं रख सकता है। जैसा कि आप पहले ही पता लगा चुके हैं, आपको एक स्ट्रिंग संयोजन के साथ बहुत अधिक सफलता नहीं मिलेगी। हालांकि, अन्य प्रयोग करने योग्य "मूल्य संयोजन" तकनीकें उपलब्ध हैं...
आपके पास अपने निपटान में स्केलर का एक आसान स्कीमा-स्तरीय संग्रह होना चाहिए:
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. द्वारा निर्देशित ग्राफ़ को गैर-निर्देशित ग्राफ़ को पूर्व-संसाधित किया है - इनपुट के लिए रिवर्स किनारों का एक सेट। इससे रिकर्सिव ट्रैवर्सल को पढ़ने में आसान भविष्यवाणी करनी चाहिए। एसक्यूएल के आसान पढ़ने + लिखने के मेरे उद्देश्यों के लिए पूरी तरह से। बेशक, आपको ऐसा करने की ज़रूरत नहीं है। - मुझे याद है कि कुछ साल पहले Oracle 11.2 पर कुछ इस तरह की कोशिश कर रहा था। और मुझे याद है कि यह असफल हो रहा था, हालांकि मुझे याद नहीं क्यों। 12.2 पर, यह ठीक चला। बस इसे 11g पर भी आजमाएं; मेरे पास एक उपलब्ध नहीं है।
- चूंकि प्रत्येक पुनरावृत्ति करता है, ट्रैवर्सल इनर जॉइन के अलावा, एक एंटी-जॉइन भी होता है, मुझे ईमानदारी से संदेह है कि यह अधिक प्रदर्शन करने वाला होगा। हालांकि, यह निश्चित रूप से पुनरावर्ती नेस्टिंग की संख्या को कम करने की समस्या को हल करता है।
- आपको वांछित आदेश को स्वयं हल करना होगा, जैसा कि आप शायद मेरी टिप्पणियों से समझ गए हैं। :-)
फिर से देखे गए किनारों को शून्य तक सीमित करना
एसक्यूएल में, आप नहीं कर सकते। आपके द्वारा उल्लिखित PostgreSQL समाधान करता है। ओरेकल में, हालांकि, आप नहीं कर सकते। आपको प्रत्येक ट्रैवर्सल जॉइन के लिए, अन्य सभी ट्रैवर्सल जॉइन के लिए टेस्ट रो करना होगा। और इसका मतलब होगा किसी प्रकार का एकत्रीकरण या विश्लेषण... जिसे Oracle मना करता है और ORA अपवाद को बाहर कर देता है।
पीएलएसक्यूएल बचाव के लिए?
हालांकि, आप इसे पीएल/एसक्यूएल में कर सकते हैं। यह कितना प्रदर्शनकारी होना चाहिए, यह इस बात पर निर्भर करता है कि आप डीबी बनाम प्रीफेचिंग किनारों पर कितनी मेमोरी खर्च करना चाहते हैं। "वर्तमान" नोड्स से ग्राफ को पार करने के लिए आप कितने एसक्यूएल राउंडट्रिप्स लेने के इच्छुक हैं या यदि आप उपयोग करने के इच्छुक हैं विज़िट किए गए नोड्स को एक फैंसी इंडेक्स-बाय-एज संग्रह में रखने के लिए और भी अधिक मेमोरी बनाम यदि आप नियमित 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तक मेज़। अनावश्यक बढ़त के साथ शुद्ध-एसक्यूएल समाधान की तुलना में यह एक बड़ा प्रदर्शन हिट हो सकता है या नहीं भी हो सकता है। अधिक समाधानों का ठीक से परीक्षण करें, देखें कि कौन सा आपके लिए सबसे अच्छा काम करता है। - कोड का यह विशेष भाग 12c और उच्चतर पर काम करेगा। 11g और उससे कम के लिए आपको
rec_output. घोषित करना होगा औरarr_outputस्कीमा स्तर पर प्रकार।
