SQL中的图树层次结构

SQL中的图树层次结构

SQL code在RDBMS中操作S图 树 层次结构等特殊的数据结构时,我们通常采用2个主要方法:
一个是基于迭代/递归 另外一个是具体化描述数据结构的附加信息。
一般模型有：员工组织图(树,层次结构);料表--BOM(有向图);道路系统(无向循环图)
1.迭代/递归
迭代可以迭代图的一个节点,也可以迭代一个层次.后者比前者要快很多.
实现方法：SQL2000通过UDF(用户自定义函数),SQL2005使用CTE。

a.下属问题(通俗说,求子节点)
--这里我使用书上的员工表
SET NOCOUNT ON;
USE tempdb;
GO
IF OBJECT_ID('dbo.Employees') IS NOT NULL
  DROP TABLE dbo.Employees;
GO
CREATE TABLE dbo.Employees
(
  empid   INT         NOT NULL PRIMARY KEY,
  mgrid   INT         NULL     REFERENCES dbo.Employees,
  empname VARCHAR(25) NOT NULL,
  salary  MONEY       NOT NULL,
  CHECK (empid <> mgrid)
);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(1, NULL, 'David', $10000.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(2, 1, 'Eitan', $7000.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(3, 1, 'Ina', $7500.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(4, 2, 'Seraph', $5000.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(5, 2, 'Jiru', $5500.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(6, 2, 'Steve', $4500.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(7, 3, 'Aaron', $5000.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(8, 5, 'Lilach', $3500.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(9, 7, 'Rita', $3000.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(10, 5, 'Sean', $3000.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(11, 7, 'Gabriel', $3000.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(12, 9, 'Emilia' , $2000.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(13, 9, 'Michael', $2000.00);
INSERT INTO dbo.Employees(empid, mgrid, empname, salary)
  VALUES(14, 9, 'Didi', $1500.00);
--创建索引
CREATE UNIQUE INDEX idx_unc_mgrid_empid ON dbo.Employees(mgrid, empid);
go

--SQL2000 udf方法：
IF OBJECT_ID('dbo.fn_subordinates1') IS NOT NULL
  DROP FUNCTION dbo.fn_subordinates1;
GO
CREATE FUNCTION dbo.fn_subordinates1(@root AS INT)
RETURNS @Subs TABLE
(
  empid INT NOT NULL PRIMARY KEY NONCLUSTERED,
  lvl   INT NOT NULL,
  UNIQUE CLUSTERED(lvl, empid) 
)
AS
begin
declare @lv int
set @lv=0
insert @Subs values(@root,@lv)
while @@rowcount>0
begin
    set @lv=@Lv+1;
    insert @subs
    select b.empid ,@Lv
    from @subs a join dbo.Employees b on a.empid=b.mgrid and lvl=@lv-1
end
return;
end
go
SELECT empid, lvl FROM dbo.fn_subordinates1(3) AS S;

--SQL2005 CTE
DECLARE @root AS INT;
SET @root = 3;
WITH SubsCTE
AS
(
  -- Anchor member returns root node
  SELECT empid, empname, 0 AS lvl
  FROM dbo.Employees
  WHERE empid = @root

  UNION ALL

  -- Recursive member returns next level of children
  SELECT C.empid, C.empname, P.lvl + 1
  FROM SubsCTE AS P
    JOIN dbo.Employees AS C
      ON C.mgrid = P.empid
)
SELECT * FROM SubsCTE;
/*
empid       empname                   lvl
----------- ------------------------- -----------
3           Ina                       0
7           Aaron                     1
9           Rita                      2
11          Gabriel                   2
12          Emilia                    3
13          Michael                   3
14          Didi                      3

*/
---------------如果需要限制递归的层数------------
--SQL2000

IF OBJECT_ID('dbo.fn_subordinates2') IS NOT NULL
  DROP FUNCTION dbo.fn_subordinates2;
GO
CREATE FUNCTION dbo.fn_subordinates2
  (@root AS INT, @maxlevels AS INT = NULL) RETURNS @Subs TABLE
(
  empid INT NOT NULL PRIMARY KEY NONCLUSTERED,
  lvl   INT NOT NULL,
  UNIQUE CLUSTERED(lvl, empid) 
)
AS
BEGIN
  DECLARE @lvl AS INT;
  SET @lvl = 0;           
  -- 如果@maxlevels输入的是NULL,把他变为最大的INT类型
 SET @maxlevels = COALESCE(@maxlevels, 2147483647);
  INSERT INTO @Subs(empid, lvl)
    SELECT empid, @lvl FROM dbo.Employees WHERE empid = @root;

  WHILE @@rowcount > 0        
    AND @lvl < @maxlevels       -- 这里注意加一个小于最大的递归数的条件,是小于 不是小于等于
  BEGIN
    SET @lvl = @lvl + 1;       

    INSERT INTO @Subs(empid, lvl)
      SELECT C.empid, @lvl               --这里跟上面处理都一样
      FROM @Subs AS P          
        JOIN dbo.Employees AS C
          ON P.lvl = @lvl - 1 
          AND C.mgrid = P.empid;
  END

  RETURN;
END
GO
SELECT empid, lvl
FROM dbo.fn_subordinates2(3, NULL) AS S;
/*
empid       lvl
----------- -----------
3           0
7           1
9           2
11          2
12          3
13          3
14          3
*/
-----
SELECT empid, lvl
FROM dbo.fn_subordinates2(2, NULL) AS S;
/*
empid       lvl
----------- -----------
2           0
4           1
5           1
6           1
8           2
10          2
*/
PS：这里控制返回的层数 你当然可以用最开始的方法,然后再筛选语句里控制层数
 如SELECT empid, lvl FROM dbo.fn_subordinates1(3) AS S where lvl<3;  但是控制本身的递归只能在UDF里面了
 
 --sql2005方法类似
 WITH SubsCTE
AS
(
  SELECT empid, empname, 0 AS lvl
  FROM dbo.Employees
  WHERE empid = @root
  UNION ALL

  SELECT C.empid, C.empname, P.lvl + 1
  FROM SubsCTE AS P
    JOIN dbo.Employees AS C
      ON C.mgrid = P.empid
      AND P.lvl < @maxlevels -- 这里控制递归数
)
SELECT * FROM SubsCTE;

--还有一种偏方：但是不推荐 虽然结果正确 但是会报错
WITH SubsCTE
AS
(
  SELECT empid, empname, 0 AS lvl
  FROM dbo.Employees
  WHERE empid = @root

  UNION ALL

  SELECT C.empid, C.empname, P.lvl + 1
  FROM SubsCTE AS P
    JOIN dbo.Employees AS C
      ON C.mgrid = P.empid
)
SELECT * FROM SubsCTE
OPTION (MAXRECURSION 2);--就是这里的MAXRECURSION 控制递归
 /*
 empid       empname                   lvl
----------- ------------------------- -----------
3           Ina                       0
7           Aaron                     1
9           Rita                      2
11          Gabriel                   2
消息 530，级别 16，状态 1，第 4 行
语句被终止。完成执行语句前已用完最大递归 2。
    */
   
b.祖先(通俗说：求父节点)
其实思路跟子节点差不多
--SQL2000
IF OBJECT_ID('dbo.fn_managers') IS NOT NULL
  DROP FUNCTION dbo.fn_managers;
GO
CREATE FUNCTION dbo.fn_managers
(@empid AS INT, @maxlevels AS INT = NULL) RETURNS @Mgrs TABLE
(
  empid INT NOT NULL PRIMARY KEY,
  lvl   INT NOT NULL
)
AS
BEGIN
  IF NOT EXISTS(SELECT * FROM dbo.Employees WHERE empid = @empid) --这里判断是否存在经理,不存在 马上返回
    RETURN;

  DECLARE @lvl AS INT,@mgrid int ;
  SET @lvl = 0; 
  set @mgrid=@empid  --赋值给@mgrid 我这是为了更加清楚变量的意思 其实不用这个@Mgrid变量的         

  -- 如果@maxlevels输入的是NULL,把他变为最大的INT类型
  SET @maxlevels = COALESCE(@maxlevels, 2147483647);

  WHILE  @lvl <= @maxlevels and @mgrid is not null     --注意这里是小于等于 而且新插入的经理不可以为NULL，为null说明是老大了
  BEGIN
    --插入当前经理
    INSERT INTO @Mgrs(empid, lvl) VALUES(@mgrid, @lvl); --这里第一次插入是自己,后面就是各自的经理了
    SET @lvl = @lvl + 1;       
    --获得下一个级别的经理
    SET @mgrid = (SELECT mgrid FROM dbo.Employees
                  WHERE empid = @mgrid);
 
  END

  RETURN;
END
GO
SELECT empid, lvl
FROM dbo.fn_managers(8, NULL) AS M;
/*
empid       lvl
----------- -----------
1           3
2           2
5           1
8           0

*/
SELECT empid, lvl
FROM dbo.fn_managers(8, 2) AS M;
/*
empid       lvl
----------- -----------
2           2
5           1
8           0
*/

--sql2005
DECLARE @empid AS INT, @maxlevels AS INT;
SET @empid = 8;
SET @maxlevels = 2;

WITH MgrsCTE
AS
(
  SELECT empid, mgrid, empname, 0 AS lvl
  FROM dbo.Employees
  WHERE empid = @empid

  UNION ALL

  SELECT P.empid, P.mgrid, P.empname, C.lvl + 1
  FROM MgrsCTE AS C
    JOIN dbo.Employees AS P
      ON C.mgrid = P.empid
      AND C.lvl < @maxlevels--限制递归数...
)
SELECT * FROM MgrsCTE;