start with ... connect by用法簡介 sql有向圖問題期待新解決方案
/*******************************************************************************
通過START WITH . . . CONNECT BY . . .子句來實現SQL的層次查詢.
自從Oracle 9i開始，可以通過 SYS_CONNECT_BY_PATH 函數實現將父節點到當前行內容以“path”或者層次元素列表的形式顯示出來。
自從Oracle 10g 中，還有其他更多關于層次查詢的新特性 。例如，有的時候用戶更關心的是每個層次分支中等級最低的內容。
那么你就可以利用偽列函數CONNECT_BY_ISLEAF來判斷當前行是不是葉子。如果是葉子就會在偽列中顯示“1”，
如果不是葉子而是一個分支（例如當前內容是其他行的父親）就顯示“0”。
在Oracle 10g 之前的版本中，如果在你的樹中出現了環狀循環（如一個孩子節點引用一個父親節點），
Oracle 就會報出一個錯誤提示：“ ORA-01436: CONNECT BY loop in user data”。如果不刪掉對父親的引用就無法執行查詢操作。
而在 Oracle 10g 中，只要指定“NOCYCLE”就可以進行任意的查詢操作。與這個關鍵字相關的還有一個偽列——CONNECT_BY_ISCYCLE，
如果在當前行中引用了某個父親節點的內容并在樹中出現了循環，那么該行的偽列中就會顯示“1”，否則就顯示“0”。
The start with .. connect by clause can be used to select data that has a hierarchical relationship
(usually some sort of parent->child, boss->employee or thing->parts).
It is also being used when an sql execution plan is explained.
syntax:
select ... [start with initial-condition] connect by [nocycle] recurse-condition
level
With level it is possible to show the level in the hierarchical relation of all the data.
--oracle 9i
sys_connect_by_path
With sys_connect_by_path it is possible to show the entire path from the top level down to the 'actual' child.
--oracle 10g
connect_by_root
connect_by_root is a new operator that comes with Oracle 10g and enhances the ability to perform hierarchical queries.
connect_by_is_leaf
connect_by_isleaf is a new operator that comes with Oracle 10g and enhances the ability to perform hierarchical queries.
connect_by_iscycle
connect_by_is_cycle is a new operator that comes with Oracle 10g and enhances the ability to perform hierarchical queries.
--start with ... connect by ... 的處理機制
How must a start with ... connect by select statement be read and interpreted?
If Oracle encounters such an SQL statement, it proceeds as described in the following pseude code.
for rec in (select * from some_table) loop
if FULLFILLS_START_WITH_CONDITION(rec) then
RECURSE(rec, rec.child);
end if;
end loop;
procedure RECURSE (rec in MATCHES_SELECT_STMT, new_parent IN field_type) is
begin
APPEND_RESULT_LIST(rec);
for rec_recurse in (select * from some_table) loop
if FULLFILLS_CONNECT_BY_CONDITION(rec_recurse.child, new_parent) then
RECURSE(rec_recurse,rec_recurse.child);
end if;
end loop;
end procedure RECURSE;
created by zhouwf0726 2006.
*******************************************************************************/
--創建測試表，增加測試數據
create table test(superid varchar2(20),id varchar2(20));
insert into test values('0','1');
insert into test values('0','2');
insert into test values('1','11');
insert into test values('1','12');
insert into test values('2','21');
insert into test values('2','22');
insert into test values('11','111');
insert into test values('11','112');
insert into test values('12','121');
insert into test values('12','122');
insert into test values('21','211');
insert into test values('21','212');
insert into test values('22','221');
insert into test values('22','222');
commit;
--層次查詢示例
select level||'層',lpad(' ',level*5)||id id
from test
start with superid = '0' connect by prior id=superid;
select level||'層',connect_by_isleaf,lpad(' ',level*5)||id id
from test
start with superid = '0' connect by prior id=superid;
--給出兩個以前在"數據庫字符串分組相加之四"中的例子來理解start with ... connect by ...
--功能：實現按照superid分組,把id用";"連接起來
--實現：以下兩個例子都是通過構造2個偽列來實現connect by連接的。
/*------method one------*/
select superid,ltrim(max(sys_connect_by_path(id,';')),';') from(
select superid,id,row_number() over(partition by superid order by superid) id1,
row_number() over(order by superid) + dense_rank() over(order by superid) id2
from test
)
start with id1=1 connect by prior id2 = id2 -1
group by superid order by superid;
/*------method two------*/
select distinct superid,ltrim(first_value(id) over(partition by superid order by l desc),';')
from(
select superid,level l,sys_connect_by_path(id,';') id
from(
select superid,id,superid||rownum parent_rn,superid||to_char(rownum-1) rn
from test
)
connect by prior parent_rn = rn
);
--下面的例子實現把一個整數的各個位上的數字相加,通過這個例子我們再次理解connect by.
create or replace function f_digit_add(innum integer) return number
is
outnum integer;
begin
if innum<0 then
return 0;
end if;
select sum(nm) into outnum from(
select substr(innum,rownum,1) nm from dual connect by rownum<length(innum)
);
return outnum;
end f_digit_add;
/
select f_digit_add(123456) from dual;
/**********************************************************************************
***********************************************************************************
下面是關于SQL解決有向圖問題，在這個例子中作者提到的錯誤
select * from fares connect by prior arrive = depart start with depart = 'LHR';
ERROR:
ORA-01436: CONNECT BY loop in user data
在oracle10g以上版本可以利用connect by的nocycle參數來解。有興趣的朋友研究用一條sql實現有向圖問題!
***********************************************************************************
**********************************************************************************/
一個常見的高級計算機科學問題可以在“有向圖”的范疇之下描述。有向圖是由一組向量和邊所連接的一組有限的節點。
例如，一個節點可以想象為一座“城市”，而每個向量可以想象為兩座城市間的一個“航線”。
有很多算法和論文講到如何解決每種可能路線的遍歷問題以及尋找最短路徑或者最小代價路徑的問題。
這些算法中大部分都是過程化的，或者是使用遞歸方面來解決的。然而 SQL 的聲明性語言使得解決復雜的有向圖問題更加容易，
而且不需要很多代碼。
讓我們以兩座城市之間的航線為例子，創建一個表保存一些假想數據：
create table airports
(
code char(3) constraint airports_pk primary key,
description varchar2(200)
);
insert into airports values ('LHR','London Heathrow, UK');
insert into airports values ('JFK','New York-Kennedy, USA');
insert into airports values ('GRU','Sao Paulo, Brazil');
create table fares
(
depart char(3),
arrive char(3),
price number,
constraint fares_pk primary key (depart,arrive),
constraint fares_depart_fk foreign key (depart) references airports,
constraint fares_arrive_fk foreign key (arrive) references airports
);
insert into fares values('LHR','JFK',700);
insert into fares values('JFK','GRU',600);
insert into fares values('LHR','GRU',1500);
insert into fares values('GRU','LHR',1600);
不能使用CONNECT BY 語法來解決如何從倫敦到圣保羅，因為在圖中有數據產生一個環（從圣保羅飛回）：
select * from fares connect by prior arrive = depart start with depart = 'LHR';
ERROR:
ORA-01436: CONNECT BY loop in user data
要解決有向圖問題，我們需要創建一個臨時表來保存兩個節點之間所有可能的路徑。我們必須注意不復制已經處理過的路徑，
而且在這種情況下，我們不想路徑走回開始處的同一個地點。我還希望跟蹤到達目的地所需航程的數目，以及所走路線的描述。
臨時表使用以下腳本創建：
create global temporary table faretemp
(
depart char(3),
arrive char(3),
hops integer,
route varchar2(30),
price number,
constraint faretemp_pk primary key (depart,arrive)
);
一個簡單的視圖可以在稍微簡化這個例子中使用的代碼。視圖可以根據 fares 表中的單個航程計算從 faretemp 表中的一個路徑
到達一下一個航程的數據：
create or replace view nexthop
as
select src.depart,
dst.arrive,
src.hops+1 hops,
src.route||','||dst.arrive route,
src.price + dst.price price
from faretemp src,fares dst
where src.arrive = dst.depart
and dst.arrive != src.depart;
/
show errors;
這個算法相當簡單。首先，使用 fares 表中的數據填充 faretemp 表，作為初始的航程。然后，取到我們剛才插入的所有數據，
使用它們建立所有可能的二航程（two-hop）路徑。重復這一過程，直至在兩個節點之間創建了新路徑。
循環過程將在節點間所有可能的路徑都被描述之后退出。如果我們只對某個開始條件感興趣，
那么我們還可以限制第一次的插入從而減少裝載數據的量。下面是發現路徑的代碼：
truncate table faretemp;
begin
-- initial connections
insert into faretemp
select depart,arrive,1,depart||','||arrive,price from fares;
while sql%rowcount > 0 loop
insert into faretemp
select depart,arrive,hops,route,price from nexthop
where (depart,arrive)
not in (select depart,arrive from faretemp);
end loop;
end;
/
show errors;
select * from faretemp order by depart,arrive;
可以在表 A 中查看輸出。
前面的數據有一個小問題。數據是點之間最短路徑（最小航程數）的集合。然而，從倫敦到圣保羅的航程卻不是最便宜的一個。
要解決最便宜的費用問題，需要對我們的循環做一個改進，當在一個航程中發現一個更便宜的路線時使用這個路線代替原來的路線。
修改后的代碼如下：
truncate table faretemp;
declare
l_count integer;
begin
-- initial connections
insert into faretemp
select depart,arrive,1,depart||','||arrive,price from fares;
l_count := sql%rowcount;
while l_count > 0 loop
update faretemp
set (hops,route,price) =
(select hops,route,price from nexthop
where depart = faretemp.depart
and arrive = faretemp.arrive)
where (depart,arrive) in
(select depart,arrive from nexthop
where price < faretemp.price);
l_count := sql%rowcount;
insert into faretemp
select depart,arrive,hops,route,price from nexthop
where (depart,arrive)
not in (select depart,arrive from faretemp);
l_count := l_count + sql%rowcount;
end loop;
end;
/
show errors;
select * from faretemp order by depart,arrive;
可能在表 B中查看輸出。
算法發現LHR、JFK、GRU 路線比 LHR、GRU 路線便宜，所以用前者代替了后者。循環將在沒有更便宜的費用，
并且沒有其它可能路線時退出。