這篇論壇文章(賽迪網技術社區)針對T-SQL中的遞歸進行了經典的論述,詳細內容請參考下文:
我曾經擔任過大學的老師。我在開始講授子查詢時,會讓學生從Northwind數據庫的employees表中,找到年齡最小的雇員。大多數的學生很輕松地給出了下面的解答。
SELECT *
FROM employees
WHERE BirthDate =
(SELECT MAX(BirthDate) FROM employees)
然而,當我要求他們找出下一個年紀最小的雇員的時候,許多人被難住了。有幾個學生給出了下面的解答。
SELECT *
FROM employees
WHERE BirthDate=
(SELECT MAX(BirthDate)
FROM employees
WHERE BirthDate <
(SELECT MAX(BirthDate) FROM employees))
這個問題的遞歸特性是很明顯的,我記得曾經信誓旦旦地要編寫一個可以返回任何數據層次(年齡、重量、分數等等)的第N個記錄的存儲過程。但是,直到兩年後我在做一個有人給我出資的電子商業項目時,才最終完成了這個存儲過程的編寫。
概述
遞歸,發生在一個存儲過程或者一個函數調用它本身的時候,是一個廣爲人知並且很有用的數學和編程概念。然而,它也是很危險的,例如它會導致無限循環。(這可能是SQLSERVER2000將嵌套調用和嵌套層數限制爲32的一個原因,你可以在存儲過程運行時,使用全程變量@@NESTLEVELl來檢查該過程的嵌套層。)DBMS程序員要牢記:遞歸調用會很顯著地延長事務處理的時間,因此,在在線事務處理系統中通常要避免使用遞歸。
我們由一個例子開始。假設你有一個存有學生測驗成績的名爲checkRank的表,你的任務是找出成績排在第4位到第10位的學生。我寫了一個名爲fillCheckRank的腳本和一個名爲spu_testRecursion的存儲過程來演示該技巧。該腳本以相關的隨機數據創建和裝載checkRank表(見附帶光盤中的CreateCheckRank.sql),但是該存儲過程(見列表1)卻複雜得多,並且使用了遞歸算法、嵌套過程調用和嵌套子查詢來計算答案。
列表1 spu_testRecursion存儲過程:
IF EXISTS (SELECT * FROM sysobjects
WHERE id = object_id('spu_testRecursion')
and OBJECTPROPERTY(id, 'IsProcedure') = 1)
DROP PROCEDURE spu_testRecursion
GO
CREATE PROC spu_testRecursion
@level int, @tblName varchar(30),
@colName varchar(30), @answer varchar(8000) OUTPUT
AS
DECLARE @one_less int
SET NOCOUNT ON
–– Parameter @level greater than 31 is disallowed.
IF (@level < 0 OR @level > 31)
BEGIN
PRINT 'Illegal Parameter Value. Must be 0 through 31'
RETURN –1
END
IF (@level = 0 OR @level = 1)
BEGIN
SELECT @answer= 'select max(' + @colName + ')
from ' + @tblName
END
ELSE
BEGIN
SELECT @one_less = @level – 1
–– recursively call itself
EXEC spu_testRecursion @one_less, @tblName,
@colName, @answer output
IF @@ERROR <> 0 RETURN(–1)
SELECT @answer = 'select max(' + @colName + ')
from ' + @tblName + ' where ' + @colName +
' < ' + Char(10) + '(' + @answer + ')'
END
IF @@NESTLEVEL = 1
BEGIN
PRINT 'NESTED LEVEL '
+ CAST(@@NESTLEVEL AS VARCHAR(20)) + CHAR(10) +
@colName + ' rank ' + CAST(@level AS VARCHAR(10))
+ CHAR(10) + @answer
EXEC (@answer)
END
RETURN(0)
GO
/* How to run the procedure
DECLARE @answer varchar(8000)
exec spu_testRecursion 10, 'checkRank',
'testPoints', @answer output
*/
注:當你刪除和創建該存儲過程時,你會收到由于缺失「spu_testRecursion」無法在當前存儲過程的sysdepend中添加行的信息。但是不必擔心,該存儲過程仍然可以創建。更多信息請見Q24641。
該存儲過程會收到這些參數
@level:在層次中的等級或者位置
@tblName:表名
@answer:返回生成的Select語句的輸出參數
並返回這兩個參數:
值,對應于在層次結構中所需的級別或者位置
一段您可以獲得同等結果的腳本
爲得到成績爲第四名的結果,你可以這樣做:
DECLARE @answer varchar(4000)
EXEC spu_TestRecursion 4, 'checkRank', 'testPoints',
@answer output
下面是我的結果(你的結果可能不一樣,因爲表裏面的數據是隨機生成的)。
NESTED LEVEL 1
testPoints rank 4
select max(testPoints) from checkRank where testPoints <
(select max(testPoints) from checkRank where testPoints <
(select max(testPoints) from checkRank where testPoints <
(select max(testPoints) from checkRank)))
–––––––––––
93
這樣,第四名對應的分數是93分。
當我開始執行相同的查詢來得到第10名的分數時,我的答案是87分。第4到第10的排名問題的最終答案也可以通過檢索來推斷,或者通過運行一個查詢來確定(見附帶光盤中的4ththru10th.sql)
實踐例子
接下來的場景對于許多電子商務交易是很常見的。假設交易雙方――買方和賣方開始交易、報價或者詢價。報價和詢價可以發給有限數目的買方(賣方),或者可以發給和被所有參加該價格交換的成員看到。
當對詢價的第一個出價或者響應到達時,交易開始了。從這時起,各種不同的情形都是可能的,並且每一種情形都將創建自己的交易鏈。報價、出價或者這個鏈中的其他部分都可以被終止、取消、拒絕或者接受。用戶可以發送一個還價、再收到一個還價等等。這個循環可以按照市場規則反複開始。對基本規則的各種背離也是允許的。例如,你可能會允許當事人對已經完成的交易作一些有限的變更,如,依次地接受或者拒絕,等等。
交易的實際執行情況在細節上可能是會變化的,但是通常交易鏈的每個組成部分是以可能保存爲XML文檔、Java對象或者可以拆分和存儲在表格中的文檔來體現的。你可以使用文檔路徑來找到這些文檔在交易鏈中的順序。這與鏈接表類似,除根文件和結束文件以外,每個表(路徑)中的組成部分均有與其前和其後文件的聯系。
例如,假定有一個名爲Documents的表,存有所有文檔並有一個名爲docPath的列。對于docID(主鍵)=12315且docPath= 12217/12267/12299/12315的行,存在下一個洽談鏈:12217(作爲根文檔或模板的已提出的報價原始資料).12267(已提出的報價項目――實際的報價).12299(出價).12315(反向文檔)
現在假定我要分析交易過程, 找到最終文檔和原始文檔中的價格、運費、數量和價值的差別。 如果我要分析交易失敗的可能性, 我必須用取消、終止或者拒絕的狀態來標注文檔。 爲了分析實際價值和數量,我需要以接收狀態提取協議和購貨訂單。在這兩種情況中, 最終文檔將是docPath中的最後一個文檔(在我們的例子裏,12315),但是原始文檔不是第一個文檔。在我的例子裏,第一個文檔(12217)是一個只有基本報價參數的模板。 ( 只有當我得到一個出價,我才能計算貨費、總價和其他參數。) 因此在我的例子裏,第2 個文檔(12267) 是一個原始文檔。 總之,來自交易鏈的任何文檔,除了最後一個之外,都可能是原始文檔,因爲每個隨後的文檔會給原始文檔添加一些新特性,而且我可能正好對那些新參數感興趣。
因此我的任務是根據一些條件選出docPath的第n個組成部分,如果你使用T-SQL函數編寫一個腳本、存儲過程或者UDF,這會是一項微不足道的工作。但是,如果你想要使用SELECT語句(你可以想像一下實時的電子商務)得到"on the fly"的結果,任務變得非常複雜。
子鏈幫助程序
假設一個示例字符串'12/23/34/45/56/67/78/89/90/11/22/33/44/55/66/77/88/99/00/A/B/E/F/'。爲了找到這個字符串的任何一個組成部分,我們可以使用一個簡單的算法選出定界符的兩個連續位置之間的子串:
Member (1) = substring (string, 1, pos(1) – 1);
Member (2) = substring (string, pos(1) + 1, pos(2) – pos(1) – 1); ...
Member (n) = substring (string, pos(n–1) + 1, pos(n) – pos(n–1) – 1),
T_SQL的方法如下:
Member (1) = SUBSTRING (string,1,CHARINDEX('/', string,1)–1)
Member (2) = SUBSTRING (string, CHARINDEX('/', string,1)+1,CHARINDEX('/', string, CHARINDEX('/', string,1)+1)–CHARINDEX('/', string,1)–1) And so on.
spu_indDocID存儲過程(在下載文件中可以得到)生成允許我們選取這個字符串第1至第31個任意一個組成部分的腳本。該過程執行了我先前概略介紹過的算法並且使用了這些參數:
@str—The name of the string, usually variable or column name.
@level—This is actually a member's number or depth of recursion call.
@prevPos and @pos—I use these output parameters to save positions of delimiters and use them in the next procedure call.
@answer—One more output parameter to accumulate the result. 例子
爲了察看交易鏈的例子, 運行FindSource.sql腳本來看一下交易鏈的例子。腳本的第一部分創建了一個名爲「documents「的表, 然後在其中載入了示例數據。這些是這種情形的潛在規則:
假如在docPath中的第一個(最左邊)的文檔的docTypeID是1,那麽在docPath中的第一個文檔是文檔源。
假如第一個文檔的docTypeID是2,那麽文檔源是docPath中的第二個文檔
假如第一個文檔的docTypeID是3,那麽文檔源是docPath中的第三個文檔
因此利用存儲過程sup_findDocID,它能夠爲docPath中的第一、第二和第三個文檔産生相關的腳本
DECLARE @answer varchar(8000), @prevPos varchar(3000),
@pos varchar(3000)
EXEC spu_findDocID 'docPath', 1, @prevPos output,
@pos output, @answer output
EXEC spu_findDocID 'docPath', 2, @prevPos output,
@pos output, @answer output
EXEC spu_findDocID 'docPath', 3, @prevPos output,
@pos output, @answer output
最後,使用該腳本來看所有未成功交易的原始資料:
SELECT
failed.docID [failedDoc],
failed.docParh,
frst.docID [firstDoc],
frst.docTypeID [first docType],
CASE
WHEN frst.docTypeID = 1 THEN /*COPY GENERATED SCRIPT
FOR FIRST MEMBER OF docPath HERE*/
WHEN frst.docTypeID = 2 THEN /*COPY GENERATED SCRIPT
FOR SECOND MEMBER OF docPath HERE*/
WHEN frst.docTypeID = 3 THEN /*COPY GENERATED SCRIPT
FOR THIRD MEMBER OF docPath*/
END sourceDoc
FROM
(SELECT docID, docParh
FROM documents WHERE docTypeID IN(7, 8)) failed
INNER JOIN
(SELECT docID, docTypeID FROM documents) frst
ON frst.docID = SUBSTRING(docParh,1,
CHARINDEX('/', docParh,1)–1)
以下是使用我的數據的查詢結果:
failedDoc docParh firstDoc first docType sourceDoc
10 1/5/7/10/ 1 1 1
11 3/7/9/11/ 3 3 9
12 2/6/8/12/ 2 2 6
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
這篇論壇文章(賽迪網技術社區)針對T-SQL中的遞歸進行了經典的論述,詳細內容請參考下文:
我曾經擔任過大學的老師。我在開始講授子查詢時,會讓學生從Northwind數據庫的employees表中,找到年齡最小的雇員。大多數的學生很輕松地給出了下面的解答。
SELECT *
FROM employees
WHERE BirthDate =
(SELECT MAX(BirthDate) FROM employees)
然而,當我要求他們找出下一個年紀最小的雇員的時候,許多人被難住了。有幾個學生給出了下面的解答。
SELECT *
FROM employees
WHERE BirthDate=
(SELECT MAX(BirthDate)
FROM employees
WHERE BirthDate <
(SELECT MAX(BirthDate) FROM employees))
這個問題的遞歸特性是很明顯的,我記得曾經信誓旦旦地要編寫一個可以返回任何數據層次(年齡、重量、分數等等)的第N個記錄的存儲過程。但是,直到兩年後我在做一個有人給我出資的電子商業項目時,才最終完成了這個存儲過程的編寫。
概述
遞歸,發生在一個存儲過程或者一個函數調用它本身的時候,是一個廣爲人知並且很有用的數學和編程概念。然而,它也是很危險的,例如它會導致無限循環。(這可能是SQLSERVER2000將嵌套調用和嵌套層數限制爲32的一個原因,你可以在存儲過程運行時,使用全程變量@@NESTLEVELl來檢查該過程的嵌套層。)DBMS程序員要牢記:遞歸調用會很顯著地延長事務處理的時間,因此,在在線事務處理系統中通常要避免使用遞歸。
我們由一個例子開始。假設你有一個存有學生測驗成績的名爲checkRank的表,你的任務是找出成績排在第4位到第10位的學生。我寫了一個名爲fillCheckRank的腳本和一個名爲spu_testRecursion的存儲過程來演示該技巧。該腳本以相關的隨機數據創建和裝載checkRank表(見附帶光盤中的CreateCheckRank.sql),但是該存儲過程(見列表1)卻複雜得多,並且使用了遞歸算法、嵌套過程調用和嵌套子查詢來計算答案。
列表1 spu_testRecursion存儲過程:
IF EXISTS (SELECT * FROM sysobjects
WHERE id = object_id('spu_testRecursion')
and OBJECTPROPERTY(id, 'IsProcedure') = 1)
DROP PROCEDURE spu_testRecursion
GO
CREATE PROC spu_testRecursion
@level int, @tblName varchar(30),
@colName varchar(30), @answer varchar(8000) OUTPUT
AS
DECLARE @one_less int
SET NOCOUNT ON
–– Parameter @level greater than 31 is disallowed.
IF (@level < 0 OR @level > 31)
BEGIN
PRINT 'Illegal Parameter Value. Must be 0 through 31'
RETURN –1
END
IF (@level = 0 OR @level = 1)
BEGIN
SELECT @answer= 'select max(' + @colName + ')
from ' + @tblName
END
ELSE
BEGIN
SELECT @one_less = @level – 1
–– recursively call itself
EXEC spu_testRecursion @one_less, @tblName,
@colName, @answer output
IF @@ERROR <> 0 RETURN(–1)
SELECT @answer = 'select max(' + @colName + ')
from ' + @tblName + ' where ' + @colName +
' < ' + Char(10) + '(' + @answer + ')'
END
IF @@NESTLEVEL = 1
BEGIN
PRINT 'NESTED LEVEL '
+ CAST(@@NESTLEVEL AS VARCHAR(20)) + CHAR(10) +
@colName + ' rank ' + CAST(@level AS VARCHAR(10))
+ CHAR(10) + @answer
EXEC (@answer)
END
RETURN(0)
GO
/* How to run the procedure
DECLARE @answer varchar(8000)
exec spu_testRecursion 10, 'checkRank',
'testPoints', @answer output
*/
注:當你刪除和創建該存儲過程時,你會收到由于缺失「spu_testRecursion」無法在當前存儲過程的sysdepend中添加行的信息。但是不必擔心,該存儲過程仍然可以創建。更多信息請見Q24641。
該存儲過程會收到這些參數
@level:在層次中的等級或者位置
@tblName:表名
@answer:返回生成的Select語句的輸出參數
並返回這兩個參數:
值,對應于在層次結構中所需的級別或者位置
一段您可以獲得同等結果的腳本
爲得到成績爲第四名的結果,你可以這樣做:
DECLARE @answer varchar(4000)
EXEC spu_TestRecursion 4, 'checkRank', 'testPoints',
@answer output
下面是我的結果(你的結果可能不一樣,因爲表裏面的數據是隨機生成的)。
NESTED LEVEL 1
testPoints rank 4
select max(testPoints) from checkRank where testPoints <
(select max(testPoints) from checkRank where testPoints <
(select max(testPoints) from checkRank where testPoints <
(select max(testPoints) from checkRank)))
–––––––––––
93
這樣,第四名對應的分數是93分。
當我開始執行相同的查詢來得到第10名的分數時,我的答案是87分。第4到第10的排名問題的最終答案也可以通過檢索來推斷,或者通過運行一個查詢來確定(見附帶光盤中的4ththru10th.sql)
實踐例子
接下來的場景對于許多電子商務交易是很常見的。假設交易雙方――買方和賣方開始交易、報價或者詢價。報價和詢價可以發給有限數目的買方(賣方),或者可以發給和被所有參加該價格交換的成員看到。
當對詢價的第一個出價或者響應到達時,交易開始了。從這時起,各種不同的情形都是可能的,並且每一種情形都將創建自己的交易鏈。報價、出價或者這個鏈中的其他部分都可以被終止、取消、拒絕或者接受。用戶可以發送一個還價、再收到一個還價等等。這個循環可以按照市場規則反複開始。對基本規則的各種背離也是允許的。例如,你可能會允許當事人對已經完成的交易作一些有限的變更,如,依次地接受或者拒絕,等等。
交易的實際執行情況在細節上可能是會變化的,但是通常交易鏈的每個組成部分是以可能保存爲XML文檔、Java對象或者可以拆分和存儲在表格中的文檔來體現的。你可以使用文檔路徑來找到這些文檔在交易鏈中的順序。這與鏈接表類似,除根文件和結束文件以外,每個表(路徑)中的組成部分均有與其前和其後文件的聯系。
例如,假定有一個名爲Documents的表,存有所有文檔並有一個名爲docPath的列。對于docID(主鍵)=12315且docPath= 12217/12267/12299/12315的行,存在下一個洽談鏈:12217(作爲根文檔或模板的已提出的報價原始資料).12267(已提出的報價項目――實際的報價).12299(出價).12315(反向文檔)
現在假定我要分析交易過程, 找到最終文檔和原始文檔中的價格、運費、數量和價值的差別。 如果我要分析交易失敗的可能性, 我必須用取消、終止或者拒絕的狀態來標注文檔。 爲了分析實際價值和數量,我需要以接收狀態提取協議和購貨訂單。在這兩種情況中, 最終文檔將是docPath中的最後一個文檔(在我們的例子裏,12315),但是原始文檔不是第一個文檔。在我的例子裏,第一個文檔(12217)是一個只有基本報價參數的模板。 ( 只有當我得到一個出價,我才能計算貨費、總價和其他參數。) 因此在我的例子裏,第2 個文檔(12267) 是一個原始文檔。 總之,來自交易鏈的任何文檔,除了最後一個之外,都可能是原始文檔,因爲每個隨後的文檔會給原始文檔添加一些新特性,而且我可能正好對那些新參數感興趣。
因此我的任務是根據一些條件選出docPath的第n個組成部分,如果你使用T-SQL函數編寫一個腳本、存儲過程或者UDF,這會是一項微不足道的工作。但是,如果你想要使用SELECT語句(你可以想像一下實時的電子商務)得到"on the fly"的結果,任務變得非常複雜。
子鏈幫助程序
假設一個示例字符串'12/23/34/45/56/67/78/89/90/11/22/33/44/55/66/77/88/99/00/A/B/E/F/'。爲了找到這個字符串的任何一個組成部分,我們可以使用一個簡單的算法選出定界符的兩個連續位置之間的子串:
Member (1) = substring (string, 1, pos(1) – 1);
Member (2) = substring (string, pos(1) + 1, pos(2) – pos(1) – 1); ...
Member (n) = substring (string, pos(n–1) + 1, pos(n) – pos(n–1) – 1),
T_SQL的方法如下:
Member (1) = SUBSTRING (string,1,CHARINDEX('/', string,1)–1)
Member (2) = SUBSTRING (string, CHARINDEX('/', string,1)+1,CHARINDEX('/', string, CHARINDEX('/', string,1)+1)–CHARINDEX('/', string,1)–1) And so on.
spu_indDocID存儲過程(在下載文件中可以得到)生成允許我們選取這個字符串第1至第31個任意一個組成部分的腳本。該過程執行了我先前概略介紹過的算法並且使用了這些參數:
@str—The name of the string, usually variable or column name.
@level—This is actually a member's number or depth of recursion call.
@prevPos and @pos—I use these output parameters to save positions of delimiters and use them in the next procedure call.
@answer—One more output parameter to accumulate the result. 例子
爲了察看交易鏈的例子, 運行FindSource.sql腳本來看一下交易鏈的例子。腳本的第一部分創建了一個名爲「documents「的表, 然後在其中載入了示例數據。這些是這種情形的潛在規則:
假如在docPath中的第一個(最左邊)的文檔的docTypeID是1,那麽在docPath中的第一個文檔是文檔源。
假如第一個文檔的docTypeID是2,那麽文檔源是docPath中的第二個文檔
假如第一個文檔的docTypeID是3,那麽文檔源是docPath中的第三個文檔
因此利用存儲過程sup_findDocID,它能夠爲docPath中的第一、第二和第三個文檔産生相關的腳本
DECLARE @answer varchar(8000), @prevPos varchar(3000),
@pos varchar(3000)
EXEC spu_findDocID 'docPath', 1, @prevPos output,
@pos output, @answer output
EXEC spu_findDocID 'docPath', 2, @prevPos output,
@pos output, @answer output
EXEC spu_findDocID 'docPath', 3, @prevPos output,
@pos output, @answer output
最後,使用該腳本來看所有未成功交易的原始資料:
SELECT
failed.docID [failedDoc],
failed.docParh,
frst.docID [firstDoc],
frst.docTypeID [first docType],
CASE
WHEN frst.docTypeID = 1 THEN /*COPY GENERATED SCRIPT
FOR FIRST MEMBER OF docPath HERE*/
WHEN frst.docTypeID = 2 THEN /*COPY GENERATED SCRIPT
FOR SECOND MEMBER OF docPath HERE*/
WHEN frst.docTypeID = 3 THEN /*COPY GENERATED SCRIPT
FOR THIRD MEMBER OF docPath*/
END sourceDoc
FROM
(SELECT docID, docParh
FROM documents WHERE docTypeID IN(7, 8)) failed
INNER JOIN
(SELECT docID, docTypeID FROM documents) frst
ON frst.docID = SUBSTRING(docParh,1,
CHARINDEX('/', docParh,1)–1)
以下是使用我的數據的查詢結果:
failedDoc docParh firstDoc first docType sourceDoc
10 1/5/7/10/ 1 1 1
11 3/7/9/11/ 3 3 9
12 2/6/8/12/ 2 2 6