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

Oracle中start?with...connect?by?prior子句使用方法?connect?by?是結構化查詢中用到的，其基本的語法是：?
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;?

?????簡單說來是將一個樹狀結構存儲在一張表里，比方一個表中存在兩個字段:?
org_id,parent_id那么通過表示每一條記錄的parent是誰，就能夠形成一個樹狀結構。?
?????用上述語法的查詢能夠取得這棵樹的全部記錄。?
?????當中：?
?????條件1?是根結點的限定語句，當然能夠放寬限定條件，以取得多個根結點，實際就是多棵樹。?
?????條件2?是連接條件，當中用PRIOR表示上一條記錄，比方?CONNECT?BY?PRIOR?org_id?=?parent_id就是說上一條記錄的org_id?是本條記錄的parent_id，即本記錄的父親是上一條記錄。?
?????條件3?是過濾條件，用于對返回的全部記錄進行過濾。?

?????簡介例如以下：?
?????早掃描樹結構表時，須要依此訪問樹結構的每一個節點，一個節點僅僅能訪問一次，其訪問的過程例如以下：?
?????第一步：從根節點開始；?
?????第二步：訪問該節點；?
?????第三步：推斷該節點有無未被訪問的子節點，若有，則轉向它最左側的未被訪問的子節，并運行第二步，否則運行第四步；?
?????第四步：若該節點為根節點，則訪問完成，否則運行第五步；?
?????第五步：返回到該節點的父節點，并運行第三步驟。?

?????總之：掃描整個樹結構的過程也即是中序遍歷樹的過程。?

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

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

oracle?提供了start?with?connect?by?語法結構能夠實現遞歸查詢。

1.?一個簡單舉例:
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>


上面的語句查找出了從1開始，而且day_number?逐漸+1?遞增的，而且?msisdn?同樣的哪些個數據.


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

在以下的這個start?with?connect?by?結構中，就表示?查找出了從1開始，而且day_number?逐漸+1?遞增的，而且?msisdn?同樣的那些個數據.

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

3.??運行計劃
對于這個特殊的語法結構，我們來看看它的運行計劃。
通過以下的運行計劃，我們能夠看出，對于簡單的訪問一個對象的遞歸查詢，實際上oracle?要三次訪問要查詢的對象。因此，這一個告訴我們，在使用遞歸查詢時，一定要慎重，由于即使原表數據不多，可是三倍的訪問喜愛來，代價也會非常大。

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>


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

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

--直接添?條件后的運行計劃
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>


--使用子查詢，將過濾條件嵌在子查詢中
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.?實際中?遞歸查詢的使用。

問題：
數據庫里有字段day_number，msisdn。怎樣寫月度連續3天有記錄的手機號？表結構例如以下：

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

表中3月份連續3天有記錄的紀錄就是1380000000。請問怎樣寫這種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>