T-SQL中的递归

MSSQL频道 >

时间: 2008-03-19 17:15

[摘要]递归是经典的技巧之一，主修计算机科学的学生经常通过编写汉诺塔程序来学习它。在这篇文章中，Alex Kozak探讨了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

1 / 1 页

跳转页

作者
star65225692

添加至收藏夹

SQL Server 2005新特性之使用with关键字解决递归父子关系

优化递归算法效率