oracle中?connect?by?prior?遞歸算法?

Oracle中start?with...connect?by?prior子句使用方法?connect?by?是結(jié)構(gòu)化查詢中用到的，其基本的語(yǔ)法是：?
select?...?from?tablename?start?with?條件1?
connect?by?條件2?
where?條件3;?
例：?
select?*?from?table?
start?with?org_id?=?'HBHqfWGWPy'?
connect?by?prior?org_id?=?parent_id;?

?????簡(jiǎn)單說(shuō)來(lái)是將一個(gè)樹狀結(jié)構(gòu)存儲(chǔ)在一張表里，比方一個(gè)表中存在兩個(gè)字段:?
org_id,parent_id那么通過(guò)表示每一條記錄的parent是誰(shuí)，就能夠形成一個(gè)樹狀結(jié)構(gòu)。?
?????用上述語(yǔ)法的查詢能夠取得這棵樹的全部記錄。?
?????當(dāng)中：?
?????條件1?是根結(jié)點(diǎn)的限定語(yǔ)句，當(dāng)然能夠放寬限定條件，以取得多個(gè)根結(jié)點(diǎn)，實(shí)際就是多棵樹。?
?????條件2?是連接條件，當(dāng)中用PRIOR表示上一條記錄，比方?CONNECT?BY?PRIOR?org_id?=?parent_id就是說(shuō)上一條記錄的org_id?是本條記錄的parent_id，即本記錄的父親是上一條記錄。?
?????條件3?是過(guò)濾條件，用于對(duì)返回的全部記錄進(jìn)行過(guò)濾。?

?????簡(jiǎn)介例如以下：?
?????早掃描樹結(jié)構(gòu)表時(shí)，須要依此訪問(wèn)樹結(jié)構(gòu)的每一個(gè)節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)僅僅能訪問(wèn)一次，其訪問(wèn)的過(guò)程例如以下：?
?????第一步：從根節(jié)點(diǎn)開始；?
?????第二步：訪問(wèn)該節(jié)點(diǎn)；?
?????第三步：推斷該節(jié)點(diǎn)有無(wú)未被訪問(wèn)的子節(jié)點(diǎn)，若有，則轉(zhuǎn)向它最左側(cè)的未被訪問(wèn)的子節(jié)，并運(yùn)行第二步，否則運(yùn)行第四步；?
?????第四步：若該節(jié)點(diǎn)為根節(jié)點(diǎn)，則訪問(wèn)完成，否則運(yùn)行第五步；?
?????第五步：返回到該節(jié)點(diǎn)的父節(jié)點(diǎn)，并運(yùn)行第三步驟。?

?????總之：掃描整個(gè)樹結(jié)構(gòu)的過(guò)程也即是中序遍歷樹的過(guò)程。?

?????1．?樹結(jié)構(gòu)的描寫敘述?
樹結(jié)構(gòu)的數(shù)據(jù)存放在表中，數(shù)據(jù)之間的層次關(guān)系即父子關(guān)系，通過(guò)表中的列與列間的關(guān)系來(lái)描寫敘述，如EMP表中的EMPNO和MGR。EMPNO表示該雇員的編號(hào)，MGR表示領(lǐng)導(dǎo)該雇員的人的編號(hào)，即子節(jié)點(diǎn)的MGR值等于父節(jié)點(diǎn)的EMPNO值。在表的每一行中都有一個(gè)表示父節(jié)點(diǎn)的MGR（除根節(jié)點(diǎn)外），通過(guò)每一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，就能夠確定整個(gè)樹結(jié)構(gòu)。?
在SELECT命令中使用CONNECT?BY?和藹START?WITH?子句能夠查詢表中的樹型結(jié)構(gòu)關(guān)系。其命令格式例如以下：?
SELECT?。。。?
CONNECT?BY?{PRIOR?列名1=列名2|列名1=PRIOR?裂名2}?
[START?WITH]；?
當(dāng)中：CONNECT?BY子句說(shuō)明每行數(shù)據(jù)將是按層次順序檢索，并規(guī)定將表中的數(shù)據(jù)連入樹型結(jié)構(gòu)的關(guān)系中。PRIORY運(yùn)算符必須放置在連接關(guān)系的兩列中某一個(gè)的前面。對(duì)于節(jié)點(diǎn)間的父子關(guān)系，PRIOR運(yùn)算符在一側(cè)表示父節(jié)點(diǎn)，在還有一側(cè)表示子節(jié)點(diǎn)，從而確定查找樹結(jié)構(gòu)是的順序是自頂向下還是自底向上。在連接關(guān)系中，除了能夠使用列名外，還同意使用列表達(dá)式。START?WITH?子句為可選項(xiàng)，用來(lái)標(biāo)識(shí)哪個(gè)節(jié)點(diǎn)作為查找樹型結(jié)構(gòu)的根節(jié)點(diǎn)。若該子句被省略，則表示全部滿足查詢條件的行作為根節(jié)點(diǎn)。?
START?WITH：?不但能夠指定一個(gè)根節(jié)點(diǎn)，還能夠指定多個(gè)根節(jié)點(diǎn)。?
2．?關(guān)于PRIOR?
運(yùn)算符PRIOR被放置于等號(hào)前后的位置，決定著查詢時(shí)的檢索順序。?
PRIOR被置于CONNECT?BY子句中等號(hào)的前面時(shí)，則強(qiáng)制從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的順序檢索，即由父節(jié)點(diǎn)向子節(jié)點(diǎn)方向通過(guò)樹結(jié)構(gòu)，我們稱之為自頂向下的方式。如：?
CONNECT?BY?PRIOR?EMPNO=MGR?
PIROR運(yùn)算符被置于CONNECT?BY?子句中等號(hào)的后面時(shí)，則強(qiáng)制從葉節(jié)點(diǎn)到根節(jié)點(diǎn)的順序檢索，即由子節(jié)點(diǎn)向父節(jié)點(diǎn)方向通過(guò)樹結(jié)構(gòu)，我們稱之為自底向上的方式。比如：?
CONNECT?BY?EMPNO=PRIOR?MGR?
在這樣的方式中也應(yīng)指定一個(gè)開始的節(jié)點(diǎn)。?
3．?定義查找起始節(jié)點(diǎn)?
?????在自頂向下查詢樹結(jié)構(gòu)時(shí)，不但能夠從根節(jié)點(diǎn)開始，還能夠定義不論什么節(jié)點(diǎn)為起始節(jié)點(diǎn)，以此開始向下查找。這樣查找的結(jié)果就是以該節(jié)點(diǎn)為開始的結(jié)構(gòu)樹的一枝。?
4．使用LEVEL?
在具有樹結(jié)構(gòu)的表中，每一行數(shù)據(jù)都是樹結(jié)構(gòu)中的一個(gè)節(jié)點(diǎn)，因?yàn)楣?jié)點(diǎn)所處的層次位置不同，所以每行記錄都能夠有一個(gè)層號(hào)。層號(hào)依據(jù)節(jié)點(diǎn)與根節(jié)點(diǎn)的距離確定。不論從哪個(gè)節(jié)點(diǎn)開始，該起始根節(jié)點(diǎn)的層號(hào)始終為1，根節(jié)點(diǎn)的子節(jié)點(diǎn)為2，?依此類推。?
5．節(jié)點(diǎn)和分支的裁剪?
在對(duì)樹結(jié)構(gòu)進(jìn)行查詢時(shí)，能夠去掉表中的某些行，也能夠剪掉樹中的一個(gè)分支，使用WHERE子句來(lái)限定樹型結(jié)構(gòu)中的單個(gè)節(jié)點(diǎn)，以去掉樹中的單個(gè)節(jié)點(diǎn)，但它卻不影響其后代節(jié)點(diǎn)（自頂向下檢索時(shí)）或前輩節(jié)點(diǎn)（自底向頂檢索時(shí)）。?
6．排序顯示?
象在其他查詢中一樣，在樹結(jié)構(gòu)查詢中也能夠使用ORDER?BY?子句，改變查詢結(jié)果的顯示順序，而不必依照遍歷樹結(jié)構(gòu)的順序?

----------------------------------------------------------------------------------------------------------

oracle?提供了start?with?connect?by?語(yǔ)法結(jié)構(gòu)能夠?qū)崿F(xiàn)遞歸查詢。

1.?一個(gè)簡(jiǎn)單舉例:
SQL>?select?*??from?test;

BILL_MONTH???????????DAY_NUMBER?MSISDN
--------------------?----------?--------------------
200803????????????????????????1?13800
200803????????????????????????3?13800
200803????????????????????????2?13800
200803????????????????????????2?13801
200803????????????????????????4?13804
200803????????????????????????5?13804
200803????????????????????????7?13804
200803????????????????????????8?13804
200803????????????????????????6?13802
200803????????????????????????6?13801
200803????????????????????????7?13801
200803????????????????????????8?13801

12?rows?selected

SQL>
SQL>?select?*?from?test
2???????start?with?day_number=1
3???????connect?by??prior?day_number=day_number-1?and?prior?msisdn=?msisdn
4??????;

BILL_MONTH???????????DAY_NUMBER?MSISDN
--------------------?----------?--------------------
200803????????????????????????1?13800
200803????????????????????????2?13800
200803????????????????????????3?13800

SQL>


上面的語(yǔ)句查找出了從1開始，而且day_number?逐漸+1?遞增的，而且?msisdn?同樣的哪些個(gè)數(shù)據(jù).


2.?start?with??connect?by?語(yǔ)法結(jié)構(gòu)
如上面說(shuō)看到的?樣例，?其語(yǔ)法結(jié)構(gòu)為??start?with?condition??connect?by??condition?（含?prior?keyword)
start?with?conditon?給出的seed?數(shù)據(jù)的范圍,?connect?by??后面給出了遞歸查詢的條件,prior?keyword表示父數(shù)據(jù)，prior?條件表示子數(shù)據(jù)須要滿足父數(shù)據(jù)的什么條件。

在以下的這個(gè)start?with?connect?by?結(jié)構(gòu)中，就表示?查找出了從1開始，而且day_number?逐漸+1?遞增的，而且?msisdn?同樣的那些個(gè)數(shù)據(jù).

start?with?day_number=1
connect?by??prior?day_number=day_number-1?and?prior?msisdn=?msisdn

3.??運(yùn)行計(jì)劃
對(duì)于這個(gè)特殊的語(yǔ)法結(jié)構(gòu)，我們來(lái)看看它的運(yùn)行計(jì)劃。
通過(guò)以下的運(yùn)行計(jì)劃，我們能夠看出，對(duì)于簡(jiǎn)單的訪問(wèn)一個(gè)對(duì)象的遞歸查詢，實(shí)際上oracle?要三次訪問(wèn)要查詢的對(duì)象。因此，這一個(gè)告訴我們，在使用遞歸查詢時(shí)，一定要慎重，由于即使原表數(shù)據(jù)不多，可是三倍的訪問(wèn)喜愛(ài)來(lái)，代價(jià)也會(huì)非常大。

SQL>?explain?plan?for
2?
2???select?*?from??test
3????--where??bill_month='200803'
4????start?with?day_number=1
5????connect?by??prior?day_number=day_number-1?and?prior?msisdn=?msisdn
6??;

Explained

SQL>?select?*??from??table(?dbms_xplan.display);

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
-------------------------------------------------------------------------
|?Id??|?Operation?????????????????|??Name???????|?Rows??|?Bytes?|?Cost??|
-------------------------------------------------------------------------
|???0?|?SELECT?STATEMENT??????????|?????????????|???????|???????|???????|
|*??1?|??CONNECT?BY?WITH?FILTERING|?????????????|???????|???????|???????|
|*??2?|???FILTER??????????????????|?????????????|???????|???????|???????|
|???3?|????TABLE?ACCESS?FULL??????|?TEST????????|???????|???????|???????|
|???4?|???NESTED?LOOPS????????????|?????????????|???????|???????|???????|
|???5?|????BUFFER?SORT????????????|?????????????|???????|???????|???????|
|???6?|?????CONNECT?BY?PUMP???????|?????????????|???????|???????|???????|
|*??7?|????TABLE?ACCESS?FULL??????|?TEST????????|???????|???????|???????|
|???8?|???TABLE?ACCESS?FULL???????|?TEST????????|???????|???????|???????|
-------------------------------------------------------------------------
Predicate?Information?(identified?by?operation?id):
---------------------------------------------------
1?-?filter("TEST"."DAY_NUMBER"=1)
2?-?filter("TEST"."DAY_NUMBER"=1)

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
7?-?filter("TEST"."MSISDN"=NULL?AND?"TEST"."DAY_NUMBER"-1=NULL)
Note:?rule?based?optimization

23?rows?selected

SQL>


另外，發(fā)現(xiàn)了在含有其它條件的遞歸中，是先處理全部的遞歸查詢，最后才用添?的條件過(guò)濾.
請(qǐng)看以下的樣例。
和上面的運(yùn)行計(jì)劃對(duì)照下我們能夠知道，添?條件???where??bill_month='200803'?后，實(shí)際上卻是在遞歸完畢后，最后才運(yùn)行的????1?-?filter("TEST"."BILL_MONTH"='200803')?。

所以，為了確保語(yǔ)句的性能，不要直接添?條件在start?with?connect?by?結(jié)構(gòu)中，而是要想辦法將原表的數(shù)據(jù)控制住。這個(gè)能夠採(cǎi)用子查詢的辦法，或者使用暫時(shí)表等（最好採(cǎi)用暫時(shí)表，將數(shù)據(jù)量從本源上控制住；由于從子查詢的運(yùn)行計(jì)劃我們能夠看到，它每次也都是訪問(wèn)全表，再用條件過(guò)濾，要反復(fù)三次，不是一次過(guò)濾就夠了).

--直接添?條件后的運(yùn)行計(jì)劃
SQL>?explain?plan?for
2?
2???select?*?from??test
3????where??bill_month='200803'
4????start?with?day_number=1
5????connect?by??prior?day_number=day_number-1?and?prior?msisdn=?msisdn
6??;

Explained

SQL>?select?*??from??table(?dbms_xplan.display);

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
--------------------------------------------------------------------------
|?Id??|?Operation??????????????????|??Name???????|?Rows??|?Bytes?|?Cost??|
--------------------------------------------------------------------------
|???0?|?SELECT?STATEMENT???????????|?????????????|???????|???????|???????|
|*??1?|??FILTER????????????????????|?????????????|???????|???????|???????|
|*??2?|???CONNECT?BY?WITH?FILTERING|?????????????|???????|???????|???????|
|*??3?|????FILTER??????????????????|?????????????|???????|???????|???????|
|???4?|?????TABLE?ACCESS?FULL??????|?TEST????????|???????|???????|???????|
|???5?|????NESTED?LOOPS????????????|?????????????|???????|???????|???????|
|???6?|?????BUFFER?SORT????????????|?????????????|???????|???????|???????|
|???7?|??????CONNECT?BY?PUMP???????|?????????????|???????|???????|???????|
|*??8?|?????TABLE?ACCESS?FULL??????|?TEST????????|???????|???????|???????|
|???9?|????TABLE?ACCESS?FULL???????|?TEST????????|???????|???????|???????|
--------------------------------------------------------------------------
Predicate?Information?(identified?by?operation?id):
---------------------------------------------------
1?-?filter("TEST"."BILL_MONTH"='200803')

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
2?-?filter("TEST"."DAY_NUMBER"=1)
3?-?filter("TEST"."DAY_NUMBER"=1)
8?-?filter("TEST"."MSISDN"=NULL?AND?"TEST"."DAY_NUMBER"-1=NULL)
Note:?rule?based?optimization

25?rows?selected

SQL>


--使用子查詢，將過(guò)濾條件嵌在子查詢中
SQL>?explain?plan?for
2?
2??select?*?from?(select?*?from?test
3????????where??bill_month='200803')
4???????start?with?day_number=1
5???????connect?by??prior?day_number=day_number-1?and?prior?msisdn=?msisdn
6??????;

Explained

SQL>?select?*??from?table(dbms_xplan.display);

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
-------------------------------------------------------------------------
|?Id??|?Operation?????????????????|??Name???????|?Rows??|?Bytes?|?Cost??|
-------------------------------------------------------------------------
|???0?|?SELECT?STATEMENT??????????|?????????????|???????|???????|???????|
|*??1?|??CONNECT?BY?WITH?FILTERING|?????????????|???????|???????|???????|
|*??2?|???FILTER??????????????????|?????????????|???????|???????|???????|
|*??3?|????TABLE?ACCESS?FULL??????|?TEST????????|???????|???????|???????|
|???4?|???NESTED?LOOPS????????????|?????????????|???????|???????|???????|
|???5?|????BUFFER?SORT????????????|?????????????|???????|???????|???????|
|???6?|?????CONNECT?BY?PUMP???????|?????????????|???????|???????|???????|
|*??7?|????TABLE?ACCESS?FULL??????|?TEST????????|???????|???????|???????|
|*??8?|???TABLE?ACCESS?FULL???????|?TEST????????|???????|???????|???????|
-------------------------------------------------------------------------
Predicate?Information?(identified?by?operation?id):
---------------------------------------------------
1?-?filter("TEST"."DAY_NUMBER"=1)
2?-?filter("TEST"."DAY_NUMBER"=1)

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
3?-?filter("TEST"."BILL_MONTH"='200803')
7?-?filter("TEST"."BILL_MONTH"='200803'?AND?"TEST"."MSISDN"=NULL?AND
"TEST"."DAY_NUMBER"-1=NULL)
8?-?filter("TEST"."BILL_MONTH"='200803')
Note:?rule?based?optimization

26?rows?selected

SQL>



4.?實(shí)際中?遞歸查詢的使用。

問(wèn)題：
數(shù)據(jù)庫(kù)里有字段day_number，msisdn。怎樣寫月度連續(xù)3天有記錄的手機(jī)號(hào)？表結(jié)構(gòu)例如以下：

id???bill_month???day_number?????msisdn
1??????200803??????1???????????13800000000
2??????200803??????1???????????130137.....
3??????200803??????2???????????13800000000
4??????200803??????3???????????13800000000
..............................

表中3月份連續(xù)3天有記錄的紀(jì)錄就是1380000000。請(qǐng)問(wèn)怎樣寫這種sql？


解決方式：
SQL>?create??table???test?(?bill_month?varchar2(20),day_number?number?,msisdn?varchar2(20));

Table?created

SQL>?insert?into??test?values?(?'200803',1,'13800');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',3,'13800');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',2,'13800');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',2,'13801');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',4,'13804');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',5,'13804');

1?row?inserted

SQL>?commit;

Commit?complete

SQL>?select?*??from?test;

BILL_MONTH???????????DAY_NUMBER?MSISDN
--------------------?----------?--------------------
200803????????????????????????1?13800
200803????????????????????????3?13800
200803????????????????????????2?13800
200803????????????????????????2?13801
200803????????????????????????4?13804
200803????????????????????????5?13804

6?rows?selected

SQL>
SQL>?select?distinct??msisdn??from?test??a
2??where??bill_month='200803'
3??and?exists
4??(?select?msisdn?from??test
5????where??bill_month='200803'?and?msisdn=a.msisdn
6????start?with?day_number=a.day_number
7????connect?by??prior?day_number=day_number-1?and?prior?msisdn=?msisdn
8????group?by?msisdn
9????having?count(*)>=3
10????);

MSISDN
--------------------
13800


SQL>?select?*??from?test;

BILL_MONTH???????????DAY_NUMBER?MSISDN
--------------------?----------?--------------------
200803????????????????????????1?13800
200803????????????????????????3?13800
200803????????????????????????2?13800
200803????????????????????????2?13801
200803????????????????????????4?13804
200803????????????????????????5?13804

6?rows?selected

SQL>?insert?into??test?values?(?'200803',7,'13804');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',8,'13804');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',6,'13802');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',6,'13801');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',7,'13801');

1?row?inserted

SQL>?insert?into??test?values?(?'200803',8,'13801');

1?row?inserted

SQL>?select?*??from?test;

BILL_MONTH???????????DAY_NUMBER?MSISDN
--------------------?----------?--------------------
200803????????????????????????1?13800
200803????????????????????????3?13800
200803????????????????????????2?13800
200803????????????????????????2?13801
200803????????????????????????4?13804
200803????????????????????????5?13804
200803????????????????????????7?13804
200803????????????????????????8?13804
200803????????????????????????6?13802
200803????????????????????????6?13801
200803????????????????????????7?13801
200803????????????????????????8?13801

12?rows?selected

SQL>?commit;

Commit?complete

SQL>
SQL>?select?distinct??msisdn??from?test??a
2??where??bill_month='200803'
3??and?exists
4??(?select?msisdn?from??test
5????where??bill_month='200803'?and?msisdn=a.msisdn
6????start?with?day_number=a.day_number
7????connect?by??prior?day_number=day_number-1?and?prior?msisdn=?msisdn
8????group?by?msisdn
9????having?count(*)>=3
10????);

MSISDN
--------------------
13800
13801

SQL>