用SQL实现树的查询.doc

用SQL实现树的查询 树形结构是一类重要的非线性结构，在关系型数据库中如何对具有树形结构的表进行查询，从而得到所需的数据是一个常见的问题。本文笔者以 SQL Server 2000 为例，就一些常用的查询给出了相应的算法与代码，颇值得读者借鉴。 　　　　树型结构 　　　　关系型数据库将数据按表结构形式进行组织。它对表格的处理方便灵活，且易学易用，因而得到广泛的应用。关系型数据库所处理的表格是线性结构的，表的每一行对应着一个数据元素，称做一条记录。记录与记录之间呈线性排列，彼此间没有联系， 然而，在解决实际问题时，常常会遇到非线性结构的数据。如下表所示，每一条纪录中的上级代码，就和其他纪录有着联系，这样就形成了一棵具有层次结构的树，它可以用下面的图来形象地表示：　　　 　　树形结构是一种结点之间有分支，并具有层次关系的结构，它非常类似于自然界中的树。 树结构在客观世界中大量存在，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，用树来组织信息；在分析算法的行为时，用树来描述其执行过程。 　　　　在关系型数据库中如何对具有树形结构的表进行查询，从而得到所需的数据是一种常见的需求。下面以SQL Server 2000 为例，就三种常用的查询给出相应的算法与代码： 　　　　1．节点 A 的位于第 n 层的父结点信息，如：员工黄菁菁的上两级上司的名称。 　　　　2．某棵子树的统计信息，如：员工余顺景及其所有下属员工的工资总额。 　　　　3．某棵子树的结点信息，如：员工郑可可及其所有下属员工的名称。 　　 　　某节点的父节点信息　　　　　要实现这样的查询，常使用递归的方法。我们可以用SQL Server 2000 增加的用户定义函数 （UDF, User Defined Function）这个新特性来实现递归函数调用。下面是函数的定义： 　　　　CREATE FUNCTION dbo.GetManager 　　　　( @employee_id AS char(5), 　　　　@level AS int = 1 -- 缺省值为1 　　　　) 　　　　RETURNS char(5) 　　　　其中，employee_id表示要查询的员工号码，level表示高于该员工的级别数，返回的结果是上司的员工号码。 　　　　该函数的递归定义为： 如果 level = 0，则返回当前的员工号码；如果 level 0，则返回直接上司的 level-1 级的上司号码。 　　　　根据这样的递归定义，我们可以写出完整的递归函数： 　　　　CREATE FUNCTION dbo.GetManager 　　　　( @employee_id AS char(5), 　　　　@level AS int = 1 　　　　) 　　　　RETURNS char(5) AS 　　　　BEGIN 　　　　IF @level = 0 　　　　RETURN @employee_id 　　　　——如果 level 为0，表示已经找到其上司号码 　　　　RETURN dbo.GetManager( 　　　　(SELECT [上级号码] FROM [员工信息] WHERE [员工号码] = @employee_id), 　　　　@level -1) -- 如果 level 大于 0，则返回直接上司的 level-1 级的上司号码 　　　　END 　　　　执行下面的语句可以得到需要的结果： 　　　　SELECT * FROM [员工信息] WHERE [员工号码] =dbo.GetManager(‘E9907’, 2) 　　　　当然，如果要让该递归函数更为健壮，我们还需要在函数中加入容错检查，这里不再赘述。 　　　　某棵子树的统计信息 　　　　这个查询同样使用递归的方法来实现。先看一下函数定义： 　　　　CREATE FUNCTION dbo.GetTotalSalary 　　　　( @manager_id AS char(5) 　　　　) 　　　　RETURNS int 　　　　其中，@manager_id 是要统计的某位上司的员工号码，返回其所有下属的工资总额。 　　　　该函数的递归定义为：如果没有下属，则返回当前的工资额; 如果有下属，则返回所有下属的工资总额。 　　　　根据这样的递归定义，我们可以写出完整的递归函数： 　　　　CREATE FUNCTION dbo.GetTotalSalary 　　　　( @manager