用SQL实现树的查询 SQLSQL Server数据结构算法ASP
程序员文章站
2022-07-12 16:26:53
...
引用
树形结构是一类重要的非线性结构，在关系型数据库中如何对具有树形结构的表进行查询，从而得到所需的数据是一个常见的问题。本文笔者以 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_id AS char(5)
)
RETURNS int AS
BEGIN
RETURN (
SELECT [工资] FROM [员工信息] WHERE [员工号码] = @manager_id) +
CASE
WHEN EXISTS(SELECT * FROM [员工信息] WHERE [上级号码] = @manager_id) THEN
( SELECT SUM(dbo.GetTotalSalary([员工号码])) FROM [员工信息]
WHERE [上级号码] = @manager_id
)
ELSE 0
END
END
上面的自定义用户函数中使用了CASE 搜索函数，它按指定顺序为每个 WHEN 子句的 Boolean_expression 求值，返回第一个取值为 TRUE 的 Boolean_expression 的 result_expression，如果没有取值为 TRUE 的 Boolean_expression，则当有ELSE子句时SQL Server将返回 else_result_expression; 若没有ELSE子句，则返回 NULL 值。
在自定义用户函数中，如果员工信息表中发现该员工有下属（EXISTS子查询），则为每个下属调用GetTotalSalary函数返回下属的工资总额，并用SUM函数求和；反之，则直接返回其工资额。
执行下面的语句可以得到所需的结果：
SELECT dbo.GetTotalSalary(‘E9902’) AS ‘工资总额’
实际工作还可能有这样的查询要求，即某名员工一共有多少个下属级别（包括其自身），如张建平一共有四个下属级别。用树的术语来描述，即求出某棵子树的深度。可以通过这样的递归函数来实现：
CREATE FUNCTION dbo.GetUnderlyingLevel
( @manager_id AS char(5)
)
RETURNS int AS
BEGIN
RETURN
CASE
WHEN EXISTS(SELECT * FROM [员工信息] WHERE [上级号码] = @manager_id)
THEN 1 + (SELECT MAX(dbo.GetUnderlyingLevel([员工号码])) FROM [员工信息] WHERE [上级号码] = @manager_id)
ELSE 1
END
END
执行下面的语句可以得到所需的结果：
SELECT dbo.GetUnderlyingLevel('E9901') AS ‘下属级别’
某棵子树所有子节点信息
前面的两种查询返回的都是标量值，这里的查询需返回某棵子树的所有子节点的信息，这是一个结果集，需要用 table 数据类型来存储。函数定义如下：
CREATE FUNCTION dbo.GetSubtreeInfo
( @manager_id AS int
)
RETURNS @treeinfo table
( [员工号码] [char] (5) NOT NULL,
[姓名] [char] (10) NOT NULL,
[年龄] [int] NOT NULL,
[工资] [money] NOT NULL,
[上级号码] [char] (5) NULL，
[级别] [int] NOT NULL
)
其中，@manager_id 代表要查询的上司的员工号码，返回的是其所有下属的信息，这些信息存放在 table 型变量 @treeinfo 中。
由于该查询返回的是一个结果集，因此已经不能使用递归的方法来实现，我们使用循环的方法来实现，循环的过程为：将参数 @manager_id 所代表的上司的信息插入到表中，赋予级别0；级别增加为1，将所有上级号码为以上 @manager_id 的员工信息插入到表中；级别增加为2，将所有上级号码与第2步插入的记录中的员工号码一致的员工信息插入到表中；依次增加级别，直到找不到上级号码与前一步插入的纪录中的员工号码一致的员工信息为止。
为了实现这个循环，我们要用系统函数 @@ROWCOUNT 来判断前一步中是否有新的记录被插入到表中。如果有，则循环继续；如果无，则循环结束。另外，我们在表中增加了一个名为“级别”的字段，既可以显示出所在的级别关系，还可以用来代表每一次新插入的记录，可谓一举两得。完整的函数定义如下：
CREATE FUNCTION dbo.GetSubtreeInfo
( @manager_id AS char(5)
)
RETURNS @treeinfo table
( [员工号码] [char] (5) NOT NULL,
[姓名] [char] (10) NOT NULL,
[年龄] [int] NOT NULL,
[工资] [money] NOT NULL,
[上级号码] [char] (5) NULL,
[级别] [int] NOT NULL
) AS
BEGIN
DECLARE @level AS int
SELECT @level = 0
INSERT INTO @treeinfo
SELECT [员工号码], [姓名], [年龄], [工资], [上级号码], @level
FROM [员工信息]
WHERE [员工号码] = @manager_id
WHILE @@ROWCOUNT > 0
BEGIN
SET @level = @level + 1
INSERT INTO @treeinfo
SELECT E.[员工号码], E.[姓名], E.[年龄], E.[工资], E.[上级号码], @level
FROM [员工信息] AS E JOIN @treeinfo AS T
ON E.[上级号码] = T.[员工号码] AND T.[级别] = @level - 1
END
RETURN
END
下面是测试的结果：
SELECT * FROM dbo.GetSubtreeInfo(‘E9903’)
员工号码 姓名 年龄 工资 上级号码 级别
-------- --------- ------- --
E9903 郑可可 38 5000.0000 E9901 0
E9906 肖遥 26 3350.0000 E9903 1
E9907 黄菁菁 22 2800.0000 E9906 2
最后我们来看一个有趣的例子。将上面的函数稍做修改后，可以将该树型结构以图形化的方式打印出来，结果如下所示：
@@d04_1t3_48.jpg;图3@@
完整的函数如下所示：
CREATE FUNCTION dbo.GetSubtreeInfo2
( @manager_id AS char(5) )
RETURNS @treeinfo table
( [员工号码] [char] (5) NOT NULL,
[姓名] [char] (10) NOT NULL,
[年龄] [int] NOT NULL,
[工资] [money] NOT NULL,
[上级号码] [char] (5) NULL,
[级别] [int] NOT NULL,
[标记] [varchar] (200) NOT NULL
) AS
BEGIN
DECLARE @level AS int, @path AS varchar(200)
SELECT @level = 0, @path = 'NULL'
INSERT INTO @treeinfo
SELECT [员工号码], [姓名], [年龄], [工资], [上级号码], @level, ‘NULL->’+ [员工号码]
FROM [员工信息]
WHERE [员工号码] = @manager_id
WHILE @@ROWCOUNT > 0
BEGIN
SET @level = @level + 1
INSERT INTO @treeinfo
SELECT E.[员工号码], E.[姓名], E.[年龄], E.[工资], E.[上级号码], @level, T.[标记] + ‘->’+ E.[员工号码]
FROM [员工信息] AS E JOIN @treeinfo AS T
｀ ON E.[上级号码] = T.[员工号码] AND T.[级别] = @level - 1
END
RETURN
END
使用以下语句，即可返回如上所示的树型结构示意图：
SELECT REPLICATE (‘ | ’, [级别]) + [姓名] AS 组织结构 FROM dbo.GetSubtreeInfo2(‘E9901’) order by [标记]
树型结构
关系型数据库将数据按表结构形式进行组织。它对表格的处理方便灵活，且易学易用，因而得到广泛的应用。关系型数据库所处理的表格是线性结构的，表的每一行对应着一个数据元素，称做一条记录。记录与记录之间呈线性排列，彼此间没有联系， 然而，在解决实际问题时，常常会遇到非线性结构的数据。如下表所示，每一条纪录中的上级代码，就和其他纪录有着联系，这样就形成了一棵具有层次结构的树，它可以用下面的图来形象地表示：
树形结构是一种结点之间有分支，并具有层次关系的结构，它非常类似于自然界中的树。 树结构在客观世界中大量存在，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，用树来组织信息；在分析算法的行为时，用树来描述其执行过程。
在关系型数据库中如何对具有树形结构的表进行查询，从而得到所需的数据是一种常见的需求。下面以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_id AS char(5)
)
RETURNS int AS
BEGIN
RETURN (
SELECT [工资] FROM [员工信息] WHERE [员工号码] = @manager_id) +
CASE
WHEN EXISTS(SELECT * FROM [员工信息] WHERE [上级号码] = @manager_id) THEN
( SELECT SUM(dbo.GetTotalSalary([员工号码])) FROM [员工信息]
WHERE [上级号码] = @manager_id
)
ELSE 0
END
END
上面的自定义用户函数中使用了CASE 搜索函数，它按指定顺序为每个 WHEN 子句的 Boolean_expression 求值，返回第一个取值为 TRUE 的 Boolean_expression 的 result_expression，如果没有取值为 TRUE 的 Boolean_expression，则当有ELSE子句时SQL Server将返回 else_result_expression; 若没有ELSE子句，则返回 NULL 值。
在自定义用户函数中，如果员工信息表中发现该员工有下属（EXISTS子查询），则为每个下属调用GetTotalSalary函数返回下属的工资总额，并用SUM函数求和；反之，则直接返回其工资额。
执行下面的语句可以得到所需的结果：
SELECT dbo.GetTotalSalary(‘E9902’) AS ‘工资总额’
实际工作还可能有这样的查询要求，即某名员工一共有多少个下属级别（包括其自身），如张建平一共有四个下属级别。用树的术语来描述，即求出某棵子树的深度。可以通过这样的递归函数来实现：
CREATE FUNCTION dbo.GetUnderlyingLevel
( @manager_id AS char(5)
)
RETURNS int AS
BEGIN
RETURN
CASE
WHEN EXISTS(SELECT * FROM [员工信息] WHERE [上级号码] = @manager_id)
THEN 1 + (SELECT MAX(dbo.GetUnderlyingLevel([员工号码])) FROM [员工信息] WHERE [上级号码] = @manager_id)
ELSE 1
END
END
执行下面的语句可以得到所需的结果：
SELECT dbo.GetUnderlyingLevel('E9901') AS ‘下属级别’
某棵子树所有子节点信息
前面的两种查询返回的都是标量值，这里的查询需返回某棵子树的所有子节点的信息，这是一个结果集，需要用 table 数据类型来存储。函数定义如下：
CREATE FUNCTION dbo.GetSubtreeInfo
( @manager_id AS int
)
RETURNS @treeinfo table
( [员工号码] [char] (5) NOT NULL,
[姓名] [char] (10) NOT NULL,
[年龄] [int] NOT NULL,
[工资] [money] NOT NULL,
[上级号码] [char] (5) NULL，
[级别] [int] NOT NULL
)
其中，@manager_id 代表要查询的上司的员工号码，返回的是其所有下属的信息，这些信息存放在 table 型变量 @treeinfo 中。
由于该查询返回的是一个结果集，因此已经不能使用递归的方法来实现，我们使用循环的方法来实现，循环的过程为：将参数 @manager_id 所代表的上司的信息插入到表中，赋予级别0；级别增加为1，将所有上级号码为以上 @manager_id 的员工信息插入到表中；级别增加为2，将所有上级号码与第2步插入的记录中的员工号码一致的员工信息插入到表中；依次增加级别，直到找不到上级号码与前一步插入的纪录中的员工号码一致的员工信息为止。
为了实现这个循环，我们要用系统函数 @@ROWCOUNT 来判断前一步中是否有新的记录被插入到表中。如果有，则循环继续；如果无，则循环结束。另外，我们在表中增加了一个名为“级别”的字段，既可以显示出所在的级别关系，还可以用来代表每一次新插入的记录，可谓一举两得。完整的函数定义如下：
CREATE FUNCTION dbo.GetSubtreeInfo
( @manager_id AS char(5)
)
RETURNS @treeinfo table
( [员工号码] [char] (5) NOT NULL,
[姓名] [char] (10) NOT NULL,
[年龄] [int] NOT NULL,
[工资] [money] NOT NULL,
[上级号码] [char] (5) NULL,
[级别] [int] NOT NULL
) AS
BEGIN
DECLARE @level AS int
SELECT @level = 0
INSERT INTO @treeinfo
SELECT [员工号码], [姓名], [年龄], [工资], [上级号码], @level
FROM [员工信息]
WHERE [员工号码] = @manager_id
WHILE @@ROWCOUNT > 0
BEGIN
SET @level = @level + 1
INSERT INTO @treeinfo
SELECT E.[员工号码], E.[姓名], E.[年龄], E.[工资], E.[上级号码], @level
FROM [员工信息] AS E JOIN @treeinfo AS T
ON E.[上级号码] = T.[员工号码] AND T.[级别] = @level - 1
END
RETURN
END
下面是测试的结果：
SELECT * FROM dbo.GetSubtreeInfo(‘E9903’)
员工号码 姓名 年龄 工资 上级号码 级别
-------- --------- ------- --
E9903 郑可可 38 5000.0000 E9901 0
E9906 肖遥 26 3350.0000 E9903 1
E9907 黄菁菁 22 2800.0000 E9906 2
最后我们来看一个有趣的例子。将上面的函数稍做修改后，可以将该树型结构以图形化的方式打印出来，结果如下所示：
@@d04_1t3_48.jpg;图3@@
完整的函数如下所示：
CREATE FUNCTION dbo.GetSubtreeInfo2
( @manager_id AS char(5) )
RETURNS @treeinfo table
( [员工号码] [char] (5) NOT NULL,
[姓名] [char] (10) NOT NULL,
[年龄] [int] NOT NULL,
[工资] [money] NOT NULL,
[上级号码] [char] (5) NULL,
[级别] [int] NOT NULL,
[标记] [varchar] (200) NOT NULL
) AS
BEGIN
DECLARE @level AS int, @path AS varchar(200)
SELECT @level = 0, @path = 'NULL'
INSERT INTO @treeinfo
SELECT [员工号码], [姓名], [年龄], [工资], [上级号码], @level, ‘NULL->’+ [员工号码]
FROM [员工信息]
WHERE [员工号码] = @manager_id
WHILE @@ROWCOUNT > 0
BEGIN
SET @level = @level + 1
INSERT INTO @treeinfo
SELECT E.[员工号码], E.[姓名], E.[年龄], E.[工资], E.[上级号码], @level, T.[标记] + ‘->’+ E.[员工号码]
FROM [员工信息] AS E JOIN @treeinfo AS T
｀ ON E.[上级号码] = T.[员工号码] AND T.[级别] = @level - 1
END
RETURN
END
使用以下语句，即可返回如上所示的树型结构示意图：
SELECT REPLICATE (‘ | ’, [级别]) + [姓名] AS 组织结构 FROM dbo.GetSubtreeInfo2(‘E9901’) order by [标记]
引用自http://www2.ccw.com.cn/02/0248/d/0248d04_1.asp