sql script: Graphs, Trees, Hierarchies and Recursive Queries

2017-09-12 19:25:06来源:cnblogs.com作者:®Geovin Du Dream Park™人点击

分享
第七城市
----------------------------------------------------------------------- Inside Microsoft SQL Server 2008: T-SQL Querying (MSPress, 2009)-- Chapter 12 - Graphs, Trees, Hierarchies and Recursive Queries-- Copyright Itzik Ben-Gan, 2009-- All Rights Reserved-------------------------------------------------------------------------------------------------------------------------------------------- Scenarios-------------------------------------------------------------------------------------------------------------------------------------------- Employees Organizational Chart----------------------------------------------------------------------- Listing 12-1: DDL & Sample Data for EmployeesSET NOCOUNT ON;USE tempdb;GOIF OBJECT_ID('dbo.Employees') IS NOT NULL  DROP TABLE dbo.Employees;GOCREATE 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),  (2,  1,    'Eitan'  ,  $7000.00),  (3,  1,    'Ina'    ,  $7500.00),  (4,  2,    'Seraph' ,  $5000.00),  (5,  2,    'Jiru'   ,  $5500.00),  (6,  2,    'Steve'  ,  $4500.00),  (7,  3,    'Aaron'  ,  $5000.00),  (8,  5,    'Lilach' ,  $3500.00),  (9,  7,    'Rita'   ,  $3000.00),  (10, 5,    'Sean'   ,  $3000.00),  (11, 7,    'Gabriel',  $3000.00),  (12, 9,    'Emilia' ,  $2000.00),  (13, 9,    'Michael',  $2000.00),  (14, 9,    'Didi'   ,  $1500.00);CREATE UNIQUE INDEX idx_unc_mgrid_empid ON dbo.Employees(mgrid, empid);GO----------------------------------------------------------------------- Bill Of Materials (BOM)----------------------------------------------------------------------- Listing 12-2: DDL & Sample Data for Parts, BOMSET NOCOUNT ON;USE tempdb;GOIF OBJECT_ID('dbo.BOM') IS NOT NULL  DROP TABLE dbo.BOM;GOIF OBJECT_ID('dbo.Parts') IS NOT NULL  DROP TABLE dbo.Parts;GOCREATE TABLE dbo.Parts(  partid   INT         NOT NULL PRIMARY KEY,  partname VARCHAR(25) NOT NULL);INSERT INTO dbo.Parts(partid, partname) VALUES  ( 1, 'Black Tea'      ),  ( 2, 'White Tea'      ),  ( 3, 'Latte'          ),  ( 4, 'Espresso'       ),  ( 5, 'Double Espresso'),  ( 6, 'Cup Cover'      ),  ( 7, 'Regular Cup'    ),  ( 8, 'Stirrer'        ),  ( 9, 'Espresso Cup'   ),  (10, 'Tea Shot'       ),  (11, 'Milk'           ),  (12, 'Coffee Shot'    ),  (13, 'Tea Leaves'     ),  (14, 'Water'          ),  (15, 'Sugar Bag'      ),  (16, 'Ground Coffee'  ),  (17, 'Coffee Beans'   );CREATE TABLE dbo.BOM(  partid     INT           NOT NULL REFERENCES dbo.Parts,  assemblyid INT           NULL     REFERENCES dbo.Parts,  unit       VARCHAR(3)    NOT NULL,  qty        DECIMAL(8, 2) NOT NULL,  UNIQUE(partid, assemblyid),  CHECK (partid <> assemblyid));INSERT INTO dbo.BOM(partid, assemblyid, unit, qty) VALUES  ( 1, NULL, 'EA',   1.00),  ( 2, NULL, 'EA',   1.00),  ( 3, NULL, 'EA',   1.00),  ( 4, NULL, 'EA',   1.00),  ( 5, NULL, 'EA',   1.00),  ( 6,    1, 'EA',   1.00),  ( 7,    1, 'EA',   1.00),  (10,    1, 'EA',   1.00),  (14,    1, 'mL', 230.00),  ( 6,    2, 'EA',   1.00),  ( 7,    2, 'EA',   1.00),  (10,    2, 'EA',   1.00),  (14,    2, 'mL', 205.00),  (11,    2, 'mL',  25.00),  ( 6,    3, 'EA',   1.00),  ( 7,    3, 'EA',   1.00),  (11,    3, 'mL', 225.00),  (12,    3, 'EA',   1.00),  ( 9,    4, 'EA',   1.00),  (12,    4, 'EA',   1.00),  ( 9,    5, 'EA',   1.00),  (12,    5, 'EA',   2.00),  (13,   10, 'g' ,   5.00),  (14,   10, 'mL',  20.00),  (14,   12, 'mL',  20.00),  (16,   12, 'g' ,  15.00),  (17,   16, 'g' ,  15.00);GO----------------------------------------------------------------------- Road System----------------------------------------------------------------------- Listing 12-3: DDL & Sample Data for Cities, RoadsSET NOCOUNT ON;USE tempdb;GOIF OBJECT_ID('dbo.Roads') IS NOT NULL  DROP TABLE dbo.Roads;GOIF OBJECT_ID('dbo.Cities') IS NOT NULL  DROP TABLE dbo.Cities;GOCREATE TABLE dbo.Cities(  cityid  CHAR(3)     NOT NULL PRIMARY KEY,  city    VARCHAR(30) NOT NULL,  region  VARCHAR(30) NULL,  country VARCHAR(30) NOT NULL);INSERT INTO dbo.Cities(cityid, city, region, country) VALUES  ('ATL', 'Atlanta', 'GA', 'USA'),  ('ORD', 'Chicago', 'IL', 'USA'),  ('DEN', 'Denver', 'CO', 'USA'),  ('IAH', 'Houston', 'TX', 'USA'),  ('MCI', 'Kansas City', 'KS', 'USA'),  ('LAX', 'Los Angeles', 'CA', 'USA'),  ('MIA', 'Miami', 'FL', 'USA'),  ('MSP', 'Minneapolis', 'MN', 'USA'),  ('JFK', 'New York', 'NY', 'USA'),  ('SEA', 'Seattle', 'WA', 'USA'),  ('SFO', 'San Francisco', 'CA', 'USA'),  ('ANC', 'Anchorage', 'AK', 'USA'),  ('FAI', 'Fairbanks', 'AK', 'USA');CREATE TABLE dbo.Roads(  city1       CHAR(3) NOT NULL REFERENCES dbo.Cities,  city2       CHAR(3) NOT NULL REFERENCES dbo.Cities,  distance INT     NOT NULL,  PRIMARY KEY(city1, city2),  CHECK(city1 < city2),  CHECK(distance > 0));INSERT INTO dbo.Roads(city1, city2, distance) VALUES  ('ANC', 'FAI',  359),  ('ATL', 'ORD',  715),  ('ATL', 'IAH',  800),  ('ATL', 'MCI',  805),  ('ATL', 'MIA',  665),  ('ATL', 'JFK',  865),  ('DEN', 'IAH', 1120),  ('DEN', 'MCI',  600),  ('DEN', 'LAX', 1025),  ('DEN', 'MSP',  915),  ('DEN', 'SEA', 1335),  ('DEN', 'SFO', 1270),  ('IAH', 'MCI',  795),  ('IAH', 'LAX', 1550),  ('IAH', 'MIA', 1190),  ('JFK', 'ORD',  795),  ('LAX', 'SFO',  385),  ('MCI', 'ORD',  525),  ('MCI', 'MSP',  440),  ('MSP', 'ORD',  410),  ('MSP', 'SEA', 2015),  ('SEA', 'SFO',  815);GO----------------------------------------------------------------------- Iterations/Recursion-------------------------------------------------------------------------------------------------------------------------------------------- Subordinates----------------------------------------------------------------------- Creation Script for Function Subordinates1----------------------------------------------------------------------- Function: Subordinates1, Descendants---- Input   : @root INT: Manager id---- Output  : @Subs Table: id and level of subordinates of--                        input manager (empid = @root) in all levels---- Process : * Insert into @Subs row of input manager--           * In a loop, while previous insert loaded more than 0 rows--             insert into @Subs next level of subordinates---------------------------------------------------------------------USE tempdb;GOIF OBJECT_ID('dbo.Subordinates1') IS NOT NULL  DROP FUNCTION dbo.Subordinates1;GOCREATE FUNCTION dbo.Subordinates1(@root AS INT) RETURNS @Subs Table(  empid INT NOT NULL PRIMARY KEY NONCLUSTERED,  lvl   INT NOT NULL,  UNIQUE CLUSTERED(lvl, empid)  -- Index will be used to filter level 按级数筛选时用的索引)ASBEGIN  DECLARE @lvl AS INT = 0;      -- Initialize level counter with 0 初始化计数器为0  -- Insert root node to @Subs  INSERT INTO @Subs(empid, lvl)    SELECT empid, @lvl FROM dbo.Employees WHERE empid = @root;  WHILE @@rowcount > 0          -- while previous level had rows 当上一级存在行  BEGIN    SET @lvl = @lvl + 1;        -- Increment level counter 递增级数计数器    -- Insert next level of subordinates to @Subs    INSERT INTO @Subs(empid, lvl)      SELECT C.empid, @lvl      FROM @Subs AS P           -- P = Parent        JOIN dbo.Employees AS C -- C = Child          ON P.lvl = @lvl - 1   -- Filter parents from previous level 筛选上一级的父节点          AND C.mgrid = P.empid;  END  RETURN;ENDGO-- Node ids of descendants of a given node返回员工ID3的下属SELECT empid, lvl FROM dbo.Subordinates1(3) AS S;-- Descendants of a given nodeSELECT E.empid, E.empname, S.lvlFROM dbo.Subordinates1(3) AS S  JOIN dbo.Employees AS E    ON E.empid = S.empid;-- Leaf nodes underneath a given nodeSELECT empid FROM dbo.Subordinates1(3) AS PWHERE NOT EXISTS  (SELECT * FROM dbo.Employees AS C   WHERE C.mgrid = P.empid);-- Subtree of a Given Root, CTE Solution 锚点成员,返回DECLARE @root AS INT = 3;WITH SubsAS(  -- 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 Subs AS P    JOIN dbo.Employees AS C      ON C.mgrid = P.empid)SELECT * FROM Subs;-- Creation Script for Function PartsExplosion----------------------------------------------------------------------- Function: PartsExplosion, Parts Explosion 零件分解 另:产品零件组合---- Input   : @root INT: Root part id---- Output  : @PartsExplosion Table:--              id and level of contained parts of input part--              in all levels---- Process : * Insert into @PartsExplosion row of input root part--           * In a loop, while previous insert loaded more than 0 rows--             insert into @PartsExplosion next level of parts---------------------------------------------------------------------USE tempdb;GOIF OBJECT_ID('dbo.PartsExplosion') IS NOT NULL  DROP FUNCTION dbo.PartsExplosion;GOCREATE FUNCTION dbo.PartsExplosion(@root AS INT)  RETURNS @PartsExplosion Table(  partid INT           NOT NULL,  qty    DECIMAL(8, 2) NOT NULL,  unit   VARCHAR(3)    NOT NULL,  lvl    INT           NOT NULL,  n      INT           NOT NULL IDENTITY, -- surrogate key 代理键  UNIQUE CLUSTERED(lvl, n)  -- Index will be used to filter lvl 用索引号LVL进行筛选)ASBEGIN  DECLARE @lvl AS INT = 0;                -- Initialize level counter with 0  -- Insert root node to @PartsExplosion  INSERT INTO @PartsExplosion(partid, qty, unit, lvl)    SELECT partid, qty, unit, @lvl    FROM dbo.BOM    WHERE partid = @root;  WHILE @@rowcount > 0           -- while previous level had rows  BEGIN    SET @lvl = @lvl + 1;         -- Increment level counter    -- Insert next level of subordinates to @PartsExplosion    INSERT INTO @PartsExplosion(partid, qty, unit, lvl)      SELECT C.partid, P.qty * C.qty, C.unit, @lvl      FROM @PartsExplosion AS P  -- P = Parent        JOIN dbo.BOM AS C        -- C = Child          ON P.lvl = @lvl - 1    -- Filter parents from previous level          AND C.assemblyid = P.partid;  END  RETURN;ENDGO-- Parts Explosion   UDF CTE	返回White Tea 的零部件SELECT P.partid, P.partname, PE.qty, PE.unit, PE.lvlFROM dbo.PartsExplosion(2) AS PE  JOIN dbo.Parts AS P    ON P.partid = PE.partid;-- CTE Solution for Parts ExplosionDECLARE @root AS INT = 2;WITH PartsExplosionAS(  -- Anchor member returns root part  SELECT partid, qty, unit, 0 AS lvl  FROM dbo.BOM  WHERE partid = @root  UNION ALL  -- Recursive member returns next level of parts  SELECT C.partid, CAST(P.qty * C.qty AS DECIMAL(8, 2)),    C.unit, P.lvl + 1  FROM PartsExplosion AS P    JOIN dbo.BOM AS C      ON C.assemblyid = P.partid)SELECT P.partid, P.partname, PE.qty, PE.unit, PE.lvlFROM PartsExplosion AS PE  JOIN dbo.Parts AS P    ON P.partid = PE.partid;GO-- Parts Explosion, Aggregating PartsSELECT P.partid, P.partname, PES.qty, PES.unitFROM (SELECT partid, unit, SUM(qty) AS qty      FROM dbo.PartsExplosion(2) AS PE      GROUP BY partid, unit) AS PES  JOIN dbo.Parts AS P    ON P.partid = PES.partid;GOSELECT P.partid, P.partname, PES.qty, PES.unitFROM (SELECT partid, unit, SUM(qty) AS qty      FROM dbo.PartsExplosion(5) AS PE      GROUP BY partid, unit) AS PES  JOIN dbo.Parts AS P    ON P.partid = PES.partid;GO-- Creation Script for Function Subordinates2----------------------------------------------------------------------- Function: Subordinates2,--           Descendants with optional level limit---- Input   : @root      INT: Manager id--           @maxlevels INT: Max number of levels to return ---- Output  : @Subs TABLE: id and level of subordinates of--                        input manager in all levels <= @maxlevels---- Process : * Insert into @Subs row of input manager--           * In a loop, while previous insert loaded more than 0 rows--             and previous level is smaller than @maxlevels--             insert into @Subs next level of subordinates---------------------------------------------------------------------USE tempdb;GOIF OBJECT_ID('dbo.Subordinates2') IS NOT NULL  DROP FUNCTION dbo.Subordinates2;GOCREATE FUNCTION dbo.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)  -- Index will be used to filter level)ASBEGIN  DECLARE @lvl AS INT = 0;      -- Initialize level counter with 0  -- If input @maxlevels is NULL, set it to maximum integer  -- to virtually have no limit on levels  SET @maxlevels = COALESCE(@maxlevels, 2147483647);  -- Insert root node to @Subs  INSERT INTO @Subs(empid, lvl)    SELECT empid, @lvl FROM dbo.Employees WHERE empid = @root;  WHILE @@rowcount > 0          -- while previous level had rows    AND @lvl < @maxlevels       -- and previous level < @maxlevels  BEGIN    SET @lvl = @lvl + 1;        -- Increment level counter    -- Insert next level of subordinates to @Subs    INSERT INTO @Subs(empid, lvl)      SELECT C.empid, @lvl      FROM @Subs AS P           -- P = Parent        JOIN dbo.Employees AS C -- C = Child          ON P.lvl = @lvl - 1   -- Filter parents from previous level          AND C.mgrid = P.empid;  END  RETURN;ENDGO-- Descendants of a given node, no limit on levelsSELECT empid, lvlFROM dbo.Subordinates2(3, NULL) AS S;-- Descendants of a given node, limit 2 levelsSELECT empid, lvlFROM dbo.Subordinates2(3, 2) AS S;-- Descendants that are 2 levels underneath a given node 返回员工3以下第二级下属SELECT empidFROM dbo.Subordinates2(3, 2) AS SWHERE lvl = 2;GO-- Subtree with level limit, CTE Solution, with MAXRECURSIONDECLARE @root AS INT = 3;WITH SubsAS(  SELECT empid, empname, 0 AS lvl   FROM dbo.Employees  WHERE empid = @root  UNION ALL  SELECT C.empid, C.empname, P.lvl + 1  FROM Subs AS P    JOIN dbo.Employees AS C      ON C.mgrid = P.empid)SELECT * FROM SubsOPTION (MAXRECURSION 2);GO-- Subtree with level limit, CTE Solution, with level columnDECLARE @root AS INT = 3, @maxlevels AS INT = 2;WITH SubsAS(  SELECT empid, empname, 0 AS lvl   FROM dbo.Employees  WHERE empid = @root  UNION ALL  SELECT C.empid, C.empname, P.lvl + 1  FROM Subs AS P    JOIN dbo.Employees AS C      ON C.mgrid = P.empid)SELECT * FROM SubsWHERE lvl <= @maxlevels;----------------------------------------------------------------------- Sub-Path----------------------------------------------------------------------- Creation Script for Function Managers ----------------------------------------------------------------------- Function: Managers, Ancestors with optional level limit 具有可选级数限制的祖先(父)---- Input   : @empid INT : Employee id--           @maxlevels : Max number of levels to return ---- Output  : @Mgrs Table: id and level of managers of--                        input employee in all levels <= @maxlevels---- Process : * In a loop, while current manager is not null--             and previous level is smaller than @maxlevels--             insert into @Mgrs current manager,--             and get next level manager---------------------------------------------------------------------USE tempdb;GOIF OBJECT_ID('dbo.Managers') IS NOT NULL  DROP FUNCTION dbo.Managers;GOCREATE FUNCTION dbo.Managers  (@empid AS INT, @maxlevels AS INT = NULL) RETURNS @Mgrs TABLE(  empid INT NOT NULL PRIMARY KEY,  lvl   INT NOT NULL)ASBEGIN  IF NOT EXISTS(SELECT * FROM dbo.Employees WHERE empid = @empid)    RETURN;    DECLARE @lvl AS INT = 0;      -- Initialize level counter with 0  -- If input @maxlevels is NULL, set it to maximum integer  -- to virtually have no limit on levels  SET @maxlevels = COALESCE(@maxlevels, 2147483647);  WHILE @empid IS NOT NULL      -- while current employee has a manager    AND @lvl <= @maxlevels      -- and previous level <= @maxlevels  BEGIN    -- Insert current manager to @Mgrs    INSERT INTO @Mgrs(empid, lvl) VALUES(@empid, @lvl);    SET @lvl = @lvl + 1;        -- Increment level counter    -- Get next level manager    SET @empid = (SELECT mgrid FROM dbo.Employees WHERE empid = @empid);  END  RETURN;ENDGO-- Ancestors of a given node, no limit on levels 返回员工8的所有级别的经理SELECT empid, lvlFROM dbo.Managers(8, NULL) AS M;-- Ancestors of a Given Node, CTE Solution-- Ancestors of a given node, CTE SolutionDECLARE @empid AS INT = 8;WITH MgrsAS(  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 Mgrs AS C    JOIN dbo.Employees AS P      ON C.mgrid = P.empid)SELECT * FROM Mgrs;-- Ancestors of a given node, limit 2 levelsSELECT empid, lvlFROM dbo.Managers(8, 2) AS M;GO-- Ancestors with Level Limit, CTE SolutionDECLARE @empid AS INT = 8, @maxlevels AS INT = 2;WITH MgrsAS(  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 Mgrs AS C    JOIN dbo.Employees AS P      ON C.mgrid = P.empid)SELECT * FROM MgrsWHERE lvl <= @maxlevels;-- Ancestor that is 2 levels above a given nodeSELECT empidFROM dbo.Managers(8, 2) AS MWHERE lvl = 2;GO----------------------------------------------------------------------- Subtree/Subgraph with Path Enumeration 带有路径枚举的子图/子树----------------------------------------------------------------------- Creation Script for Function Subordinates3----------------------------------------------------------------------- Function: Subordinates3,--           Descendants with optional level limit,具有可选级数的下属,以及路径枚举--           and path enumeration---- Input   : @root      INT: Manager id--           @maxlevels INT: Max number of levels to return ---- Output  : @Subs TABLE: id, level and materialized ancestors path--                        of subordinates of input manager--                        in all levels <= @maxlevels---- Process : * Insert into @Subs row of input manager--           * In a loop, while previous insert loaded more than 0 rows--             and previous level is smaller than @maxlevels:--             - insert into @Subs next level of subordinates--             - calculate a materialized ancestors path for each--               by concatenating current node id to parent's path---------------------------------------------------------------------USE tempdb;GOIF OBJECT_ID('dbo.Subordinates3') IS NOT NULL  DROP FUNCTION dbo.Subordinates3;GOCREATE FUNCTION dbo.Subordinates3  (@root AS INT, @maxlevels AS INT = NULL) RETURNS @Subs TABLE(  empid INT          NOT NULL PRIMARY KEY NONCLUSTERED,  lvl   INT          NOT NULL,  path  VARCHAR(900) NOT NULL  UNIQUE CLUSTERED(lvl, empid)  -- Index will be used to filter level)ASBEGIN  DECLARE @lvl AS INT = 0;      -- Initialize level counter with 0  -- If input @maxlevels is NULL, set it to maximum integer  -- to virtually have no limit on levels  SET @maxlevels = COALESCE(@maxlevels, 2147483647);  -- Insert root node to @Subs  INSERT INTO @Subs(empid, lvl, path)    SELECT empid, @lvl, '.' + CAST(empid AS VARCHAR(10)) + '.'    FROM dbo.Employees WHERE empid = @root;  WHILE @@rowcount > 0          -- while previous level had rows    AND @lvl < @maxlevels       -- and previous level < @maxlevels  BEGIN    SET @lvl = @lvl + 1;        -- Increment level counter    -- Insert next level of subordinates to @Subs    INSERT INTO @Subs(empid, lvl, path)      SELECT C.empid, @lvl,        P.path + CAST(C.empid AS VARCHAR(10)) + '.'      FROM @Subs AS P           -- P = Parent        JOIN dbo.Employees AS C -- C = Child          ON P.lvl = @lvl - 1   -- Filter parents from previous level          AND C.mgrid = P.empid;  END  RETURN;ENDGO-- Return descendants of a given node, along with a materialized pathSELECT empid, lvl, pathFROM dbo.Subordinates3(1, NULL) AS S;-- Return descendants of a given node, sorted and indentedSELECT E.empid, REPLICATE(' | ', lvl) + empname AS empnameFROM dbo.Subordinates3(1, NULL) AS S  JOIN dbo.Employees AS E    ON E.empid = S.empidORDER BY path;-- Subtree with Path Enumeration, CTE Solution-- Descendants of a given node, with Materialized Path, CTE SolutionDECLARE @root AS INT = 1;WITH SubsAS(  SELECT empid, empname, 0 AS lvl,    -- Path of root = '.' + empid + '.'    CAST('.' + CAST(empid AS VARCHAR(10)) + '.'         AS VARCHAR(MAX)) AS path  FROM dbo.Employees  WHERE empid = @root  UNION ALL  SELECT C.empid, C.empname, P.lvl + 1,    -- Path of child = parent's path + child empid + '.'    CAST(P.path + CAST(C.empid AS VARCHAR(10)) + '.'         AS VARCHAR(MAX))  FROM Subs AS P    JOIN dbo.Employees AS C      ON C.mgrid = P.empid)SELECT empid, REPLICATE(' | ', lvl) + empname AS empnameFROM SubsORDER BY path;----------------------------------------------------------------------- Sorting----------------------------------------------------------------------- Sorting Hierarchy by empname, CTE SolutionDECLARE @root AS INT = 1;WITH SubsAS(  SELECT empid, empname, 0 AS lvl,    -- Path of root is 1 (binary)    CAST(1 AS VARBINARY(MAX)) AS sort_path  FROM dbo.Employees  WHERE empid = @root  UNION ALL  SELECT C.empid, C.empname, P.lvl + 1,    -- Path of child = parent's path + child row number (binary)    P.sort_path + CAST(      ROW_NUMBER() OVER(PARTITION BY C.mgrid                        ORDER BY C.empname) -- sort col(s)      AS BINARY(4))  FROM Subs AS P    JOIN dbo.Employees AS C      ON C.mgrid = P.empid)SELECT empid, ROW_NUMBER() OVER(ORDER BY sort_path) AS sortval,  REPLICATE(' | ', lvl) + empname AS empnameFROM SubsORDER BY sortval;GO-- Sorting Hierarchy by salary, CTE SolutionDECLARE @root AS INT = 1;WITH SubsAS(  SELECT empid, empname, salary, 0 AS lvl,    -- Path of root = 1 (binary)    CAST(1 AS VARBINARY(MAX)) AS sort_path  FROM dbo.Employees  WHERE empid = @root  UNION ALL  SELECT C.empid, C.empname, C.salary, P.lvl + 1,    -- Path of child = parent's path + child row number (binary)    P.sort_path + CAST(      ROW_NUMBER() OVER(PARTITION BY C.mgrid                        ORDER BY C.salary) -- sort col(s)      AS BINARY(4))  FROM Subs AS P    JOIN dbo.Employees AS C      ON C.mgrid = P.empid)SELECT empid, salary, ROW_NUMBER() OVER(ORDER BY sort_path) AS sortval,  REPLICATE(' | ', lvl) + empname AS empnameFROM SubsORDER BY sortval;----------------------------------------------------------------------- Cycles 环----------------------------------------------------------------------- Create a cyclic pathUPDATE dbo.Employees SET mgrid = 14 WHERE empid = 1;GO-- Detecting Cycles, CTE SolutionDECLARE @root AS INT = 1;WITH SubsAS(  SELECT empid, empname, 0 AS lvl,    CAST('.' + CAST(empid AS VARCHAR(10)) + '.'         AS VARCHAR(MAX)) AS path,    -- Obviously root has no cycle    0 AS cycle  FROM dbo.Employees  WHERE empid = @root  UNION ALL  SELECT C.empid, C.empname, P.lvl + 1,    CAST(P.path + CAST(C.empid AS VARCHAR(10)) + '.'         AS VARCHAR(MAX)),    -- Cycle detected if parent's path contains child's id    CASE WHEN P.path LIKE '%.' + CAST(C.empid AS VARCHAR(10)) + '.%'      THEN 1 ELSE 0 END  FROM Subs AS P    JOIN dbo.Employees AS C      ON C.mgrid = P.empid)SELECT empid, empname, cycle, pathFROM Subs;GO-- Not Pursuing Cycles, CTE SolutionDECLARE @root AS INT = 1;WITH SubsAS(  SELECT empid, empname, 0 AS lvl,    CAST('.' + CAST(empid AS VARCHAR(10)) + '.'         AS VARCHAR(MAX)) AS path,    -- Obviously root has no cycle    0 AS cycle  FROM dbo.Employees  WHERE empid = @root  UNION ALL  SELECT C.empid, C.empname, P.lvl + 1,    CAST(P.path + CAST(C.empid AS VARCHAR(10)) + '.'         AS VARCHAR(MAX)),    -- Cycle detected if parent's path contains child's id    CASE WHEN P.path LIKE '%.' + CAST(C.empid AS VARCHAR(10)) + '.%'      THEN 1 ELSE 0 END  FROM Subs AS P    JOIN dbo.Employees AS C      ON C.mgrid = P.empid      AND P.cycle = 0 -- do not pursue branch for parent with cycle)SELECT empid, empname, cycle, pathFROM Subs;GO-- Isolating Cyclic Paths, CTE SolutionDECLARE @root AS INT = 1;WITH SubsAS(  SELECT empid, empname, 0 AS lvl,    CAST('.' + CAST(empid AS VARCHAR(10)) + '.'         AS VARCHAR(MAX)) AS path,    -- Obviously root has no cycle    0 AS cycle  FROM dbo.Employees  WHERE empid = @root  UNION ALL  SELECT C.empid, C.empname, P.lvl + 1,    CAST(P.path + CAST(C.empid AS VARCHAR(10)) + '.'         AS VARCHAR(MAX)),    -- Cycle detected if parent's path contains child's id    CASE WHEN P.path LIKE '%.' + CAST(C.empid AS VARCHAR(10)) + '.%'      THEN 1 ELSE 0 END  FROM Subs AS P    JOIN dbo.Employees AS C      ON C.mgrid = P.empid      AND P.cycle = 0)SELECT path FROM Subs WHERE cycle = 1;-- Fix cyclic pathUPDATE dbo.Employees SET mgrid = NULL WHERE empid = 1;----------------------------------------------------------------------- Materialized Path-------------------------------------------------------------------------------------------------------------------------------------------- Custom Materialized Path-------------------------------------------------------------------------------------------------------------------------------------------- Maintaining Data----------------------------------------------------------------------- DDL for Employees with PathSET NOCOUNT ON;USE tempdb;GOIF OBJECT_ID('dbo.Employees') IS NOT NULL  DROP TABLE dbo.Employees;GOCREATE TABLE dbo.Employees(  empid   INT          NOT NULL PRIMARY KEY NONCLUSTERED,  mgrid   INT          NULL     REFERENCES dbo.Employees,  empname VARCHAR(25)  NOT NULL,  salary  MONEY        NOT NULL,  lvl     INT          NOT NULL,  path    VARCHAR(900) NOT NULL UNIQUE CLUSTERED);CREATE UNIQUE INDEX idx_unc_mgrid_empid ON dbo.Employees(mgrid, empid);GO----------------------------------------------------------------------- Adding Employees who Manage No One (Leaves) 具体化路径----------------------------------------------------------------------- Creation Script for Procedure AddEmp----------------------------------------------------------------------- Stored Procedure: AddEmp,--   Inserts new employee who manages no one into the table---------------------------------------------------------------------USE tempdb;GOIF OBJECT_ID('dbo.AddEmp') IS NOT NULL  DROP PROC dbo.AddEmp;GOCREATE PROC dbo.AddEmp  @empid   INT,  @mgrid   INT,  @empname VARCHAR(25),  @salary  MONEYASSET NOCOUNT ON;-- Handle case where the new employee has no manager (root)IF @mgrid IS NULL  INSERT INTO dbo.Employees(empid, mgrid, empname, salary, lvl, path)    VALUES(@empid, @mgrid, @empname, @salary,      0, '.' + CAST(@empid AS VARCHAR(10)) + '.');-- Handle subordinate case (non-root)ELSE  INSERT INTO dbo.Employees(empid, mgrid, empname, salary, lvl, path)    SELECT @empid, @mgrid, @empname, @salary,       lvl + 1, path + CAST(@empid AS VARCHAR(10)) + '.'    FROM dbo.Employees    WHERE empid = @mgrid;GO-- Sample Data for Employees with PathEXEC dbo.AddEmp  @empid = 1, @mgrid = NULL, @empname = 'David', @salary = $10000.00;EXEC dbo.AddEmp  @empid = 2, @mgrid = 1, @empname = 'Eitan', @salary = $7000.00;EXEC dbo.AddEmp  @empid = 3, @mgrid = 1, @empname = 'Ina', @salary = $7500.00;EXEC dbo.AddEmp  @empid = 4, @mgrid = 2, @empname = 'Seraph', @salary = $5000.00;EXEC dbo.AddEmp  @empid = 5, @mgrid = 2, @empname = 'Jiru', @salary = $5500.00;EXEC dbo.AddEmp  @empid = 6, @mgrid = 2, @empname = 'Steve', @salary = $4500.00;EXEC dbo.AddEmp  @empid = 7, @mgrid = 3, @empname = 'Aaron', @salary = $5000.00;EXEC dbo.AddEmp  @empid = 8, @mgrid = 5, @empname = 'Lilach', @salary = $3500.00;EXEC dbo.AddEmp  @empid = 9, @mgrid = 7, @empname = 'Rita', @salary = $3000.00;EXEC dbo.AddEmp  @empid = 10, @mgrid = 5, @empname = 'Sean', @salary = $3000.00;EXEC dbo.AddEmp  @empid = 11, @mgrid = 7, @empname = 'Gabriel', @salary = $3000.00;EXEC dbo.AddEmp  @empid = 12, @mgrid = 9, @empname = 'Emilia', @salary = $2000.00;EXEC dbo.AddEmp  @empid = 13, @mgrid = 9, @empname = 'Michael', @salary = $2000.00;EXEC dbo.AddEmp  @empid = 14, @mgrid = 9, @empname = 'Didi', @salary = $1500.00;GO-- Examine data after loadSELECT empid, mgrid, empname, salary, lvl, pathFROM dbo.EmployeesORDER BY path;----------------------------------------------------------------------- Moving a Subtree----------------------------------------------------------------------- Creation Script for Procedure MoveSubtree----------------------------------------------------------------------- Stored Procedure: MoveSubtree,--   Moves a whole subtree of a given root to a new location--   under a given manager---------------------------------------------------------------------USE tempdb;GOIF OBJECT_ID('dbo.MoveSubtree') IS NOT NULL  DROP PROC dbo.MoveSubtree;GOCREATE PROC dbo.MoveSubtree  @root  INT,  @mgrid INTASSET NOCOUNT ON;BEGIN TRAN;  -- Update level and path of all employees in the subtree (E)  -- Set level =   --   current level + new manager's level - old manager's level  -- Set path =   --   in current path remove old manager's path   --   and substitute with new manager's path  UPDATE E    SET lvl  = E.lvl + NM.lvl - OM.lvl,        path = STUFF(E.path, 1, LEN(OM.path), NM.path)  FROM dbo.Employees AS E          -- E = Employees    (subtree)    JOIN dbo.Employees AS R        -- R = Root         (one row)      ON R.empid = @root      AND E.path LIKE R.path + '%'    JOIN dbo.Employees AS OM       -- OM = Old Manager (one row)      ON OM.empid = R.mgrid    JOIN dbo.Employees AS NM       -- NM = New Manager (one row)      ON NM.empid = @mgrid;    -- Update root's new manager  UPDATE dbo.Employees SET mgrid = @mgrid WHERE empid = @root;COMMIT TRAN;GO-- Before moving subtreeSELECT empid, REPLICATE(' | ', lvl) + empname AS empname, lvl, pathFROM dbo.EmployeesORDER BY path;-- Move Subtree 移动子树BEGIN TRAN;  EXEC dbo.MoveSubtree  @root  = 7,  @mgrid = 10;  -- After moving subtree  SELECT empid, REPLICATE(' | ', lvl) + empname AS empname, lvl, path  FROM dbo.Employees  ORDER BY path;ROLLBACK TRAN; -- rollback used in order not to apply the change----------------------------------------------------------------------- Removing a Subtree----------------------------------------------------------------------- Before deleteting subtreeSELECT empid, REPLICATE(' | ', lvl) + empname AS empname, lvl, pathFROM dbo.EmployeesORDER BY path;-- Delete Subtree  删除子树BEGIN TRAN;  DELETE FROM dbo.Employees  WHERE path LIKE     (SELECT M.path + '%'     FROM dbo.Employees as M     WHERE M.empid = 7);  -- After deleting subtree  SELECT empid, REPLICATE(' | ', lvl) + empname AS empname, lvl, path  FROM dbo.Employees  ORDER BY path;ROLLBACK TRAN; -- rollback used in order not to apply the change----------------------------------------------------------------------- Querying Materialized Path 查询----------------------------------------------------------------------- Subtree of a given rootSELECT REPLICATE(' | ', E.lvl - M.lvl) + E.empnameFROM dbo.Employees AS E  JOIN dbo.Employees AS M    ON M.empid = 3 -- root    AND E.path LIKE M.path + '%'ORDER BY E.path;-- Subtree of a given root, excluding rootSELECT REPLICATE(' | ', E.lvl - M.lvl - 1) + E.empnameFROM dbo.Employees AS E  JOIN dbo.Employees AS M    ON M.empid = 3    AND E.path LIKE M.path + '_%'ORDER BY E.path;-- Leaf nodes under a given rootSELECT E.empid, E.empnameFROM dbo.Employees AS E  JOIN dbo.Employees AS M    ON M.empid = 3    AND E.path LIKE M.path + '%'WHERE NOT EXISTS  (SELECT *    FROM dbo.Employees AS E2   WHERE E2.mgrid = E.empid);-- Subtree of a given root, limit number of levelsSELECT REPLICATE(' | ', E.lvl - M.lvl) + E.empnameFROM dbo.Employees AS E  JOIN dbo.Employees AS M    ON M.empid = 3    AND E.path LIKE M.path + '%'    AND E.lvl - M.lvl <= 2ORDER BY E.path;-- Nodes that are n levels under a given rootSELECT E.empid, E.empnameFROM dbo.Employees AS E  JOIN dbo.Employees AS M    ON M.empid = 3    AND E.path LIKE M.path + '%'    AND E.lvl - M.lvl = 2;-- Ancestors of a given node (requires a table scan)SELECT REPLICATE(' | ', M.lvl) + M.empnameFROM dbo.Employees AS E  JOIN dbo.Employees AS M    ON E.empid = 14    AND E.path LIKE M.path + '%'ORDER BY E.path;-- Creating and Populating Auxiliary Table of NumbersSET NOCOUNT ON;USE tempdb;GOIF OBJECT_ID('dbo.Nums') IS NOT NULL  DROP TABLE dbo.Nums;GOCREATE TABLE dbo.Nums(n INT NOT NULL PRIMARY KEY);DECLARE @max AS INT = 1000000, @rc AS INT = 1;INSERT INTO Nums VALUES(1);WHILE @rc * 2 <= @maxBEGIN  INSERT INTO dbo.Nums SELECT n + @rc FROM dbo.Nums;  SET @rc = @rc * 2;ENDINSERT INTO dbo.Nums   SELECT n + @rc FROM dbo.Nums WHERE n + @rc <= @max;GO-- Creation Script for Function SplitPathUSE tempdb;GOIF OBJECT_ID('dbo.SplitPath') IS NOT NULL  DROP FUNCTION dbo.SplitPath;GOCREATE FUNCTION dbo.SplitPath(@empid AS INT) RETURNS TABLEASRETURN  SELECT    ROW_NUMBER() OVER(ORDER BY n) AS pos,    CAST(SUBSTRING(path, n + 1,           CHARINDEX('.', path, n + 1) - n - 1) AS INT) AS empid  FROM dbo.Employees    JOIN dbo.Nums      ON empid = @empid      AND n < LEN(path)      AND SUBSTRING(path, n, 1) = '.';GO-- Test SplitPath functionSELECT pos, empid FROM dbo.SplitPath(14);-- Getting ancestors using SplitPath functionSELECT REPLICATE(' | ', lvl) + empnameFROM dbo.SplitPath(14) AS SP  JOIN dbo.Employees AS E    ON E.empid = SP.empidORDER BY path;-- PresentationSELECT REPLICATE(' | ', lvl) + empnameFROM dbo.EmployeesORDER BY path;----------------------------------------------------------------------- Materialized Path with the HIERARCHYID Datatype 使用HIERARCHYID数据类型的具体化路径--HIERARCHYID类型提供了下列方法和属性:GetLevel,GetRoot,GetAncestor,GetDescendant,GetReparentedValue,IsDescendantOf,ToString,Parse,Read,Write---------------------------------------------------------------------SET NOCOUNT ON;USE tempdb;GOIF OBJECT_ID('dbo.Employees') IS NOT NULL  DROP TABLE dbo.Employees;GOCREATE TABLE dbo.Employees(  empid   INT NOT NULL,  hid     HIERARCHYID NOT NULL,  lvl AS hid.GetLevel() PERSISTED,  empname VARCHAR(25) NOT NULL,  salary  MONEY       NOT NULL,  mgrid INT NULL);CREATE UNIQUE CLUSTERED INDEX idx_depth_first ON dbo.Employees(hid);CREATE UNIQUE INDEX idx_breadth_first ON dbo.Employees(lvl, hid);CREATE UNIQUE INDEX idx_empid ON dbo.Employees(empid);GO----------------------------------------------------------------------- Maintaining Data-------------------------------------------------------------------------------------------------------------------------------------------- Adding Employees------------------------------------------------------------------------------------------------------------------------------------------ -- Stored Procedure: AddEmp, --   Inserts new employee who manages no one into the table --------------------------------------------------------------------- IF OBJECT_ID('dbo.AddEmp', 'P') IS NOT NULL  DROP PROC dbo.AddEmp;GOCREATE PROC dbo.AddEmp  @empid   AS INT,  @mgrid   AS INT,  @empname AS VARCHAR(25),  @salary  AS MONEYASDECLARE  @hid            AS HIERARCHYID,  @mgr_hid        AS HIERARCHYID,  @last_child_hid AS HIERARCHYID;BEGIN TRAN  IF @mgrid IS NULL    SET @hid = hierarchyid::GetRoot();  ELSE  BEGIN    SET @mgr_hid = (SELECT hid FROM dbo.Employees WITH (UPDLOCK)                    WHERE empid = @mgrid);    SET @last_child_hid =      (SELECT MAX(hid) FROM dbo.Employees       WHERE hid.GetAncestor(1) = @mgr_hid);    SET @hid = @mgr_hid.GetDescendant(@last_child_hid, NULL);  END  INSERT INTO dbo.Employees(empid, hid, empname, salary)    VALUES(@empid, @hid, @empname, @salary);  COMMIT TRANGOEXEC dbo.AddEmp @empid =  1, @mgrid = NULL, @empname = 'David'  , @salary = $10000.00;EXEC dbo.AddEmp @empid =  2, @mgrid =    1, @empname = 'Eitan'  , @salary = $7000.00;EXEC dbo.AddEmp @empid =  3, @mgrid =    1, @empname = 'Ina'    , @salary = $7500.00;EXEC dbo.AddEmp @empid =  4, @mgrid =    2, @empname = 'Seraph' , @salary = $5000.00;EXEC dbo.AddEmp @empid =  5, @mgrid =    2, @empname = 'Jiru'   , @salary = $5500.00;EXEC dbo.AddEmp @empid =  6, @mgrid =    2, @empname = 'Steve'  , @salary = $4500.00;EXEC dbo.AddEmp @empid =  7, @mgrid =    3, @empname = 'Aaron'  , @salary = $5000.00;EXEC dbo.AddEmp @empid =  8, @mgrid =    5, @empname = 'Lilach' , @salary = $3500.00;EXEC dbo.AddEmp @empid =  9, @mgrid =    7, @empname = 'Rita'   , @salary = $3000.00;EXEC dbo.AddEmp @empid = 10, @mgrid =    5, @empname = 'Sean'   , @salary = $3000.00;EXEC dbo.AddEmp @empid = 11, @mgrid =    7, @empname = 'Gabriel', @salary = $3000.00;EXEC dbo.AddEmp @empid = 12, @mgrid =    9, @empname = 'Emilia' , @salary = $2000.00;EXEC dbo.AddEmp @empid = 13, @mgrid =    9, @empname = 'Michael', @salary = $2000.00;EXEC dbo.AddEmp @empid = 14, @mgrid =    9, @empname = 'Didi'   , @salary = $1500.00;GOSELECT hid, hid.ToString() AS path, lvl, empid, empname, salaryFROM dbo.EmployeesORDER BY hid;SELECT *FROM dbo.Employees----------------------------------------------------------------------- Moving a Subtree---------------------------------------------------------------------SELECT  CAST('/1/1/2/3/2/' AS HIERARCHYID).GetReparentedValue('/1/1/', '/2/1/4/').ToString();--------------------------------------------------------------------- -- Stored Procedure: MoveSubtree, 移动子树--   Moves a whole subtree of a given root to a new location --   under a given manager --------------------------------------------------------------------- IF OBJECT_ID('dbo.MoveSubtree') IS NOT NULL  DROP PROC dbo.MoveSubtree;GOCREATE PROC dbo.MoveSubtree  @empid    AS INT,  @new_mgrid AS INTASDECLARE   @old_root AS HIERARCHYID,  @new_root AS HIERARCHYID,  @new_mgr_hid AS HIERARCHYID;BEGIN TRAN  SET @new_mgr_hid = (SELECT hid FROM dbo.Employees WITH (UPDLOCK)                      WHERE empid = @new_mgrid);  SET @old_root = (SELECT hid FROM dbo.Employees                   WHERE empid = @empid);  -- First, get a new hid for the subtree root employee that moves  SET @new_root = @new_mgr_hid.GetDescendant    ((SELECT MAX(hid)      FROM dbo.Employees      WHERE hid.GetAncestor(1) = @new_mgr_hid),     NULL);  -- Next, reparent all descendants of employee that moves  UPDATE dbo.Employees    SET hid = hid.GetReparentedValue(@old_root, @new_root)  WHERE hid.IsDescendantOf(@old_root) = 1;COMMIT TRANGOSELECT empid, REPLICATE(' | ', lvl) + empname AS empname, hid.ToString() AS pathFROM dbo.EmployeesORDER BY hid;BEGIN TRAN  EXEC dbo.MoveSubtree    @empid    = 5,    @new_mgrid = 9;  SELECT empid, REPLICATE(' | ', lvl) + empname AS empname, hid.ToString() AS path  FROM dbo.Employees  ORDER BY hid;ROLLBACK TRANGO----------------------------------------------------------------------- Querying 查询----------------------------------------------------------------------- SubtreeSELECT E.empid, E.empnameFROM dbo.Employees AS M  JOIN dbo.Employees AS E    ON M.empid = 3    AND E.hid.IsDescendantOf(M.hid) = 1WHERE E.lvl - M.lvl <= 3;-- Path 路径SELECT M.empid, M.empnameFROM dbo.Employees AS M  JOIN dbo.Employees AS E    ON E.empid = 14    AND E.hid.IsDescendantOf(M.hid) = 1;-- Direct Subordinates 直接下属SELECT E.empid, E.empnameFROM dbo.Employees AS M  JOIN dbo.Employees AS E    ON M.empid = 2    AND E.hid.GetAncestor(1) = M.hid;-- Leaf nodes 叶子节点SELECT empid, empnameFROM dbo.Employees AS MWHERE NOT EXISTS  (SELECT * FROM dbo.Employees AS E   WHERE E.hid.GetAncestor(1) = M.hid);-- Presentation/sortingSELECT REPLICATE(' | ', lvl) + empname AS empname, hid.ToString() AS pathFROM dbo.EmployeesORDER BY hid;----------------------------------------------------------------------- Further Aspects of Working with HIERARCHYID-------------------------------------------------------------------------------------------------------------------------------------------- Normalizing HIERARCHYID Values------------------------------------------------------------------------------------------------------------------------------------------ -- Stored Procedure: AddEmp, --   Inserts new employee who manages no one into the table --------------------------------------------------------------------- IF OBJECT_ID('dbo.AddEmp', 'P') IS NOT NULL  DROP PROC dbo.AddEmp;GOCREATE PROC dbo.AddEmp  @empid      AS INT,  @mgrid      AS INT,  @leftempid  AS INT,  @rightempid AS INT,    @empname    AS VARCHAR(25),  @salary     AS MONEY = 1000ASDECLARE @hid AS HIERARCHYID;IF @mgrid IS NULL  SET @hid = hierarchyid::GetRoot();ELSE  SET @hid = (SELECT hid FROM dbo.Employees WHERE empid = @mgrid).GetDescendant    ( (SELECT hid FROM dbo.Employees WHERE empid = @leftempid),      (SELECT hid FROM dbo.Employees WHERE empid = @rightempid) );INSERT INTO dbo.Employees(empid, hid, empname, salary)  VALUES(@empid, @hid, @empname, @salary);GOTRUNCATE TABLE dbo.Employees;EXEC dbo.AddEmp @empid =  1, @mgrid = NULL, @leftempid = NULL, @rightempid = NULL, @empname = 'A';EXEC dbo.AddEmp @empid =  2, @mgrid =    1, @leftempid = NULL, @rightempid = NULL, @empname = 'B';EXEC dbo.AddEmp @empid =  3, @mgrid =    1, @leftempid =    2, @rightempid = NULL, @empname = 'C';EXEC dbo.AddEmp @empid =  4, @mgrid =    1, @leftempid =    2, @rightempid =    3, @empname = 'D';EXEC dbo.AddEmp @empid =  5, @mgrid =    1, @leftempid =    4, @rightempid =    3, @empname = 'E';EXEC dbo.AddEmp @empid =  6, @mgrid =    1, @leftempid =    4, @rightempid =    5, @empname = 'F';EXEC dbo.AddEmp @empid =  7, @mgrid =    1, @leftempid =    6, @rightempid =    5, @empname = 'G';EXEC dbo.AddEmp @empid =  8, @mgrid =    1, @leftempid =    6, @rightempid =    7, @empname = 'H';EXEC dbo.AddEmp @empid =  9, @mgrid =    8, @leftempid = NULL, @rightempid = NULL, @empname = 'I';EXEC dbo.AddEmp @empid = 10, @mgrid =    8, @leftempid =    9, @rightempid = NULL, @empname = 'J';EXEC dbo.AddEmp @empid = 11, @mgrid =    8, @leftempid =    9, @rightempid =   10, @empname = 'K';EXEC dbo.AddEmp @empid = 12, @mgrid =    8, @leftempid =   11, @rightempid =   10, @empname = 'J';EXEC dbo.AddEmp @empid = 13, @mgrid =    8, @leftempid =   11, @rightempid =   12, @empname = 'L';EXEC dbo.AddEmp @empid = 14, @mgrid =    8, @leftempid =   13, @rightempid =   12, @empname = 'M';EXEC dbo.AddEmp @empid = 15, @mgrid =    8, @leftempid =   13, @rightempid =   14, @empname = 'N';EXEC dbo.AddEmp @empid = 16, @mgrid =    8, @leftempid =   15, @rightempid =   14, @empname = 'O';EXEC dbo.AddEmp @empid = 17, @mgrid =    8, @leftempid =   15, @rightempid =   16, @empname = 'P';EXEC dbo.AddEmp @empid = 18, @mgrid =    8, @leftempid =   17, @rightempid =   16, @empname = 'Q';EXEC dbo.AddEmp @empid = 19, @mgrid =    8, @leftempid =   17, @rightempid =   18, @empname = 'E';EXEC dbo.AddEmp @empid = 20, @mgrid =    8, @leftempid =   19, @rightempid =   18, @empname = 'S';EXEC dbo.AddEmp @empid = 21, @mgrid =    8, @leftempid =   19, @rightempid =   20, @empname = 'T';GOSELECT *FROM dbo.Employees-- Data before normalizationSELECT  empid,  REPLICATE(' | ', lvl) + empname AS emp,   hid,  hid.ToString() AS pathFROM dbo.EmployeesORDER BY hid;-- NormalizeWITH EmpsRN AS(  SELECT     empid,    hid,    ROW_NUMBER() OVER(PARTITION BY hid.GetAncestor(1) ORDER BY hid) AS rownum  FROM dbo.Employees),EmpPaths AS(  SELECT empid, hid, CAST('/' AS VARCHAR(900)) AS path  FROM dbo.Employees  WHERE hid = hierarchyid::GetRoot()    UNION ALL    SELECT C.empid, C.hid,     CAST(P.path + CAST(C.rownum AS VARCHAR(20)) + '/' AS VARCHAR(900))  FROM EmpPaths AS P    JOIN EmpsRN AS C      ON C.hid.GetAncestor(1) = P.hid)UPDATE E  SET hid = CAST(EP.path AS HIERARCHYID)FROM dbo.Employees AS E  JOIN EmpPaths AS EP    ON E.empid = EP.empid;-- Data after normalizationSELECT  empid,  REPLICATE(' | ', lvl) + empname AS emp,   hid,  hid.ToString() AS pathFROM dbo.EmployeesORDER BY hid;----------------------------------------------------------------------- Convert parent-child representation to new hierarchyid---------------------------------------------------------------------SET NOCOUNT ON;USE tempdb;GOIF OBJECT_ID('dbo.EmployeesOld') IS NOT NULL  DROP TABLE dbo.EmployeesOld;GOIF OBJECT_ID('dbo.EmployeesNew') IS NOT NULL  DROP TABLE dbo.EmployeesNew;GOCREATE TABLE dbo.EmployeesOld(  empid   INT          PRIMARY KEY,  mgrid   INT          NULL REFERENCES dbo.EmployeesOld,  empname VARCHAR(25)  NOT NULL,  salary  MONEY        NOT NULL);CREATE UNIQUE INDEX idx_unc_mgrid_empid ON dbo.EmployeesOld(mgrid, empid);INSERT INTO dbo.EmployeesOld(empid, mgrid, empname, salary) VALUES  (1,  NULL, 'David',  $10000.00),  (2,  1,    'Eitan',   $7000.00),  (3,  1,    'Ina',     $7500.00),  (4,  2,    'Seraph',  $5000.00),  (5,  2,    'Jiru',    $5500.00),  (6,  2,    'Steve',   $4500.00),  (7,  3,    'Aaron',   $5000.00),  (8,  5,    'Lilach',  $3500.00),  (9,  7,    'Rita',    $3000.00),  (10, 5,    'Sean',    $3000.00),  (11, 7,    'Gabriel', $3000.00),  (12, 9,    'Emilia' , $2000.00),  (13, 9,    'Michael', $2000.00),  (14, 9,    'Didi',    $1500.00);GOCREATE TABLE dbo.EmployeesNew(  empid   INT NOT NULL PRIMARY KEY,  hid     HIERARCHYID NOT NULL,  lvl AS hid.GetLevel() PERSISTED,  empname VARCHAR(25) NOT NULL,  salary  MONEY       NOT NULL);GOWITH EmpsRNAS(  SELECT empid, mgrid, empname, salary,    ROW_NUMBER() OVER(PARTITION BY mgrid ORDER BY empid) AS rn  FROM dbo.EmployeesOld),EmpPaths AS(  SELECT empid, mgrid, empname, salary,    CAST('/' AS VARCHAR(900)) AS cpath  FROM dbo.EmployeesOld  WHERE mgrid IS NULL    UNION ALL    SELECT C.empid, C.mgrid, C.empname, C.salary,    CAST(cpath + CAST(C.rn AS VARCHAR(20)) + '/' AS VARCHAR(900))  FROM EmpPaths AS P    JOIN EmpsRN AS C      ON C.mgrid = P.empid)INSERT INTO dbo.EmployeesNew(empid, empname, salary, hid)  SELECT empid, empname, salary,    CAST(cpath AS HIERARCHYID) AS hid  FROM EmpPaths;  SELECT REPLICATE(' | ', lvl) + empname AS empname, hid.ToString() AS pathFROM dbo.EmployeesNewORDER BY hid;----------------------------------------------------------------------- Sorting Separated Lists of Values---------------------------------------------------------------------USE tempdb;IF OBJECT_ID('dbo.IPs', 'U') IS NOT NULL DROP TABLE dbo.IPs;-- Creation script for table IPsCREATE TABLE dbo.IPs(  ip varchar(15) NOT NULL,  CONSTRAINT PK_IPs PRIMARY KEY(ip),  -- CHECK constraint that validates IPs  CONSTRAINT CHK_IP_valid CHECK  (      -- 3 periods and no empty octets      ip LIKE '_%._%._%._%'    AND      -- not 4 periods or more      ip NOT LIKE '%.%.%.%.%'    AND      -- no characters other than digits and periods      ip NOT LIKE '%[^0-9.]%'    AND      -- not more than 3 digits per octet      ip NOT LIKE '%[0-9][0-9][0-9][0-9]%'    AND      -- NOT 300 - 999      ip NOT LIKE '%[3-9][0-9][0-9]%'    AND      -- NOT 260 - 299      ip NOT LIKE '%2[6-9][0-9]%'    AND      -- NOT 256 - 259      ip NOT LIKE '%25[6-9]%'  ));GO-- Sample dataINSERT INTO dbo.IPs(ip) VALUES  ('131.107.2.201'),  ('131.33.2.201'),  ('131.33.2.202'),  ('3.107.2.4'),  ('3.107.3.169'),  ('3.107.104.172'),  ('22.107.202.123'),  ('22.20.2.77'),  ('22.156.9.91'),  ('22.156.89.32');-- IP PatternsIF OBJECT_ID('dbo.IPPatterns') IS NOT NULL DROP VIEW dbo.IPPatterns;GOCREATE VIEW dbo.IPPatternsASSELECT  REPLICATE('_', N1.n) + '.' + REPLICATE('_', N2.n) + '.'    + REPLICATE('_', N3.n) + '.' + REPLICATE('_', N4.n) AS pattern,  N1.n AS l1, N2.n AS l2, N3.n AS l3, N4.n AS l4,  1 AS s1, N1.n+2 AS s2, N1.n+N2.n+3 AS s3, N1.n+N2.n+N3.n+4 AS s4FROM dbo.Nums AS N1, dbo.Nums AS N2, dbo.Nums AS N3, dbo.Nums AS N4WHERE N1.n <= 3 AND N2.n <= 3 AND N3.n <= 3 AND N4.n <= 3;GO-- Sort IPs, solution 1SELECT ipFROM dbo.IPs  JOIN dbo.IPPatterns    ON ip LIKE patternORDER BY  CAST(SUBSTRING(ip, s1, l1) AS TINYINT),  CAST(SUBSTRING(ip, s2, l2) AS TINYINT),  CAST(SUBSTRING(ip, s3, l3) AS TINYINT),  CAST(SUBSTRING(ip, s4, l4) AS TINYINT);-- Sort IPs, solution 2SELECT ipFROM dbo.IPsORDER BY CAST('/' + ip + '/' AS HIERARCHYID);-- Generic form of problemSET NOCOUNT ON;USE tempdb;IF OBJECT_ID('dbo.T1', 'U') IS NOT NULL DROP TABLE dbo.T1;CREATE TABLE dbo.T1(  id  INT          NOT NULL IDENTITY PRIMARY KEY,  val VARCHAR(500) NOT NULL);GOINSERT INTO dbo.T1(val) VALUES  ('100'),  ('7,4,250'),  ('22,40,5,60,4,100,300,478,19710212'),  ('22,40,5,60,4,99,300,478,19710212'),  ('22,40,5,60,4,99,300,478,9999999'),  ('10,30,40,50,20,30,40'),  ('7,4,250'),  ('-1'),  ('-2'),  ('-11'),  ('-22'),  ('-123'),  ('-321'),  ('22,40,5,60,4,-100,300,478,19710212'),  ('22,40,5,60,4,-99,300,478,19710212');SELECT id, valFROM dbo.T1ORDER BY CAST('/' + REPLACE(val, ',', '/') + '/' AS HIERARCHYID);----------------------------------------------------------------------- Nested Sets嵌套集合-------------------------------------------------------------------------------------------------------------------------------------------- Assigning Left and Right Values 分配左值和右值----------------------------------------------------------------------- Producing Binary Sort Paths Representing Nested Sets RelationshipsUSE tempdb;GO-- Create index to speed sorting siblings by empname, empidCREATE UNIQUE INDEX idx_unc_mgrid_empname_empid  ON dbo.Employees(mgrid, empname, empid);GODECLARE @root AS INT = 1;-- CTE with two numbers: 1 and 2WITH TwoNumsAS(  SELECT n FROM(VALUES(1),(2)) AS D(n)),-- CTE with two binary sort paths for each node:--   One smaller than descendants sort paths--   One greater than descendants sort pathsSortPathAS(  SELECT empid, 0 AS lvl, n,    CAST(n AS VARBINARY(MAX)) AS sort_path  FROM dbo.Employees CROSS JOIN TwoNums  WHERE empid = @root  UNION ALL  SELECT C.empid, P.lvl + 1, TN.n,     P.sort_path + CAST(      (-1+ROW_NUMBER() OVER(PARTITION BY C.mgrid                        -- *** determines order of siblings ***                        ORDER BY C.empname, C.empid))/2*2+TN.n      AS BINARY(4))  FROM SortPath AS P    JOIN dbo.Employees AS C      ON P.n = 1      AND C.mgrid = P.empid    CROSS JOIN TwoNums AS TN)SELECT * FROM SortPathORDER BY sort_path;GO-- CTE Code That Creates Nested Sets RelationshipsDECLARE @root AS INT = 1;-- CTE with two numbers: 1 and 2WITH TwoNumsAS(  SELECT n FROM(VALUES(1),(2)) AS D(n)),-- CTE with two binary sort paths for each node:--   One smaller than descendants sort paths--   One greater than descendants sort pathsSortPathAS(  SELECT empid, 0 AS lvl, n,    CAST(n AS VARBINARY(MAX)) AS sort_path  FROM dbo.Employees CROSS JOIN TwoNums  WHERE empid = @root  UNION ALL  SELECT C.empid, P.lvl + 1, TN.n,     P.sort_path + CAST(      ROW_NUMBER() OVER(PARTITION BY C.mgrid                        -- *** determines order of siblings ***                        ORDER BY C.empname, C.empid, TN.n)      AS BINARY(4))  FROM SortPath AS P    JOIN dbo.Employees AS C      ON P.n = 1      AND C.mgrid = P.empid    CROSS JOIN TwoNums AS TN),-- CTE with Row Numbers Representing sort_path OrderSortAS(  SELECT empid, lvl,    ROW_NUMBER() OVER(ORDER BY sort_path) AS sortval  FROM SortPath),-- CTE with Left and Right Values Representing-- Nested Sets RelationshipsNestedSetsAS(  SELECT empid, lvl, MIN(sortval) AS lft, MAX(sortval) AS rgt  FROM Sort  GROUP BY empid, lvl)SELECT * FROM NestedSetsORDER BY lft;GO-- Materializing Nested Sets Relationships in a Table SET NOCOUNT ON;USE tempdb;GODECLARE @root AS INT = 1;WITH TwoNumsAS(  SELECT n FROM(VALUES(1),(2)) AS D(n)),SortPathAS(  SELECT empid, 0 AS lvl, n,    CAST(n AS VARBINARY(MAX)) AS sort_path  FROM dbo.Employees CROSS JOIN TwoNums  WHERE empid = @root  UNION ALL  SELECT C.empid, P.lvl + 1, TN.n,     P.sort_path + CAST(      ROW_NUMBER() OVER(PARTITION BY C.mgrid                        -- *** determines order of siblings ***                        ORDER BY C.empname, C.empid, TN.n)      AS BINARY(4))  FROM SortPath AS P    JOIN dbo.Employees AS C      ON P.n = 1      AND C.mgrid = P.empid    CROSS JOIN TwoNums AS TN),SortAS(  SELECT empid, lvl,    ROW_NUMBER() OVER(ORDER BY sort_path) AS sortval  FROM SortPath),NestedSetsAS(  SELECT empid, lvl, MIN(sortval) AS lft, MAX(sortval) AS rgt  FROM Sort  GROUP BY empid, lvl)SELECT E.empid, E.empname, E.salary, NS.lvl, NS.lft, NS.rgtINTO dbo.EmployeesNSFROM NestedSets AS NS  JOIN dbo.Employees AS E    ON E.empid = NS.empid;ALTER TABLE dbo.EmployeesNS ADD PRIMARY KEY NONCLUSTERED(empid);CREATE UNIQUE CLUSTERED INDEX idx_unc_lft_rgt ON dbo.EmployeesNS(lft, rgt);GO----------------------------------------------------------------------- Querying----------------------------------------------------------------------- Descendants of a given rootSELECT C.empid, REPLICATE(' | ', C.lvl - P.lvl) + C.empname AS empnameFROM dbo.EmployeesNS AS P  JOIN dbo.EmployeesNS AS C    ON P.empid = 3    AND C.lft >= P.lft AND C.rgt <= P.rgtORDER BY C.lft;-- Descendants of a given root, limiting 2 levelsSELECT C.empid, REPLICATE(' | ', C.lvl - P.lvl) + C.empname AS empnameFROM dbo.EmployeesNS AS P  JOIN dbo.EmployeesNS AS C    ON P.empid = 3    AND C.lft >= P.lft AND C.rgt <= P.rgt    AND C.lvl - P.lvl <= 2ORDER BY C.lft;-- Leaf nodes under a given rootSELECT C.empid, C.empnameFROM dbo.EmployeesNS AS P  JOIN dbo.EmployeesNS AS C    ON P.empid = 3    AND C.lft >= P.lft AND C.rgt <= P.rgtWHERE C.rgt - C.lft = 1;-- Count of subordinates of each nodeSELECT empid, (rgt - lft - 1) / 2 AS cnt,  REPLICATE(' | ', lvl) + empname AS empnameFROM dbo.EmployeesNSORDER BY lft;-- Ancestors of a given nodeSELECT P.empid, P.empname, P.lvlFROM dbo.EmployeesNS AS P  JOIN dbo.EmployeesNS AS C    ON C.empid = 14    AND C.lft >= P.lft AND C.rgt <= P.rgt;GO-- CleanupDROP TABLE dbo.EmployeesNS;GO----------------------------------------------------------------------- Transitive Closure-------------------------------------------------------------------------------------------------------------------------------------------- Directed Acyclic Graph (DAG)----------------------------------------------------------------------- Transitive Closure of BOM (DAG)WITH BOMTCAS(  -- Return all first-level containment relationships  SELECT assemblyid, partid  FROM dbo.BOM  WHERE assemblyid IS NOT NULL  UNION ALL  -- Return next-level containment relationships  SELECT P.assemblyid, C.partid  FROM BOMTC AS P    JOIN dbo.BOM AS C      ON C.assemblyid = P.partid)-- Return distinct pairs that have-- transitive containment relationshipsSELECT DISTINCT assemblyid, partidFROM BOMTC;GO-- Listing 12-4: Creation Script for the BOMTC UDFIF OBJECT_ID('dbo.BOMTC') IS NOT NULL  DROP FUNCTION dbo.BOMTC;GOCREATE FUNCTION BOMTC() RETURNS @BOMTC TABLE(  assemblyid INT NOT NULL,  partid     INT NOT NULL,  PRIMARY KEY (assemblyid, partid))ASBEGIN  INSERT INTO @BOMTC(assemblyid, partid)    SELECT assemblyid, partid    FROM dbo.BOM    WHERE assemblyid IS NOT NULL  WHILE @@rowcount > 0    INSERT INTO @BOMTC    SELECT P.assemblyid, C.partid    FROM @BOMTC AS P      JOIN dbo.BOM AS C        ON C.assemblyid = P.partid    WHERE NOT EXISTS      (SELECT * FROM @BOMTC AS P2       WHERE P2.assemblyid = P.assemblyid       AND P2.partid = C.partid);  RETURN;ENDGO-- Use the BOMTC UDFSELECT assemblyid, partid FROM BOMTC();GO-- All Paths in BOMWITH BOMPathsAS(  SELECT assemblyid, partid,    1 AS distance, -- distance in first level is 1    -- path in first level is .assemblyid.partid.    '.' + CAST(assemblyid AS VARCHAR(MAX)) +    '.' + CAST(partid     AS VARCHAR(MAX)) + '.' AS path  FROM dbo.BOM  WHERE assemblyid IS NOT NULL  UNION ALL  SELECT P.assemblyid, C.partid,    -- distance in next level is parent's distance + 1    P.distance + 1,    -- path in next level is parent_path.child_partid.    P.path + CAST(C.partid AS VARCHAR(MAX)) + '.'  FROM BOMPaths AS P    JOIN dbo.BOM AS C      ON C.assemblyid = P.partid)-- Return all pathsSELECT * FROM BOMPaths;-- Shortest Paths in BOMWITH BOMPaths -- All pathsAS(  SELECT assemblyid, partid,    1 AS distance,    '.' + CAST(assemblyid AS VARCHAR(MAX)) +    '.' + CAST(partid     AS VARCHAR(MAX)) + '.' AS path  FROM dbo.BOM  WHERE assemblyid IS NOT NULL  UNION ALL  SELECT P.assemblyid, C.partid,    P.distance + 1,    P.path + CAST(C.partid AS VARCHAR(MAX)) + '.'  FROM BOMPaths AS P    JOIN dbo.BOM AS C      ON C.assemblyid = P.partid),BOMMinDist AS -- Minimum distance for each pair(  SELECT assemblyid, partid, MIN(distance) AS mindist  FROM BOMPaths  GROUP BY assemblyid, partid)-- Shortest path for each pairSELECT BP.*FROM BOMMinDist AS BMD  JOIN BOMPaths AS BP    ON BMD.assemblyid = BP.assemblyid    AND BMD.partid = BP.partid    AND BMD.mindist = BP.distance;GO----------------------------------------------------------------------- Undirected Cyclic Graph----------------------------------------------------------------------- Transitive Closure of Roads (Undirected Cyclic Graph)WITH Roads2 -- Two rows for each pair (f-->t, t-->f)AS(  SELECT city1 AS from_city, city2 AS to_city FROM dbo.Roads  UNION ALL  SELECT city2, city1 FROM dbo.Roads),RoadPaths AS(  -- Return all first-level reachability pairs  SELECT from_city, to_city,    -- path is needed to identify cycles    CAST('.' + from_city + '.' + to_city + '.' AS VARCHAR(MAX)) AS path  FROM Roads2  UNION ALL  -- Return next-level reachability pairs  SELECT F.from_city, T.to_city,    CAST(F.path + T.to_city + '.' AS VARCHAR(MAX))  FROM RoadPaths AS F    JOIN Roads2 AS T      -- if to_city appears in from_city's path, cycle detected      ON CASE WHEN F.path LIKE '%.' + T.to_city + '.%'              THEN 1 ELSE 0 END = 0      AND F.to_city = T.from_city)-- Return Transitive Closure of RoadsSELECT DISTINCT from_city, to_cityFROM RoadPaths;GO-- Creation Script for the RoadsTC UDFIF OBJECT_ID('dbo.RoadsTC') IS NOT NULL  DROP FUNCTION dbo.RoadsTC;GOCREATE FUNCTION dbo.RoadsTC() RETURNS @RoadsTC TABLE (  from_city VARCHAR(3) NOT NULL,  to_city   VARCHAR(3) NOT NULL,  PRIMARY KEY (from_city, to_city))ASBEGIN  DECLARE @added as INT;  INSERT INTO @RoadsTC(from_city, to_city)    SELECT city1, city2 FROM dbo.Roads;  SET @added = @@rowcount;  INSERT INTO @RoadsTC    SELECT city2, city1 FROM dbo.Roads  SET @added = @added + @@rowcount;  WHILE @added > 0 BEGIN    INSERT INTO @RoadsTC      SELECT DISTINCT TC.from_city, R.city2      FROM @RoadsTC AS TC        JOIN dbo.Roads AS R          ON R.city1 = TC.to_city      WHERE NOT EXISTS        (SELECT * FROM @RoadsTC AS TC2         WHERE TC2.from_city = TC.from_city           AND TC2.to_city = R.city2)        AND TC.from_city <> R.city2;    SET @added = @@rowcount;    INSERT INTO @RoadsTC      SELECT DISTINCT TC.from_city, R.city1      FROM @RoadsTC AS TC        JOIN dbo.Roads AS R          ON R.city2 = TC.to_city      WHERE NOT EXISTS        (SELECT * FROM @RoadsTC AS TC2         WHERE TC2.from_city = TC.from_city           AND TC2.to_city = R.city1)        AND TC.from_city <> R.city1;    SET @added = @added + @@rowcount;  END  RETURN;ENDGO-- Use the RoadsTC UDFSELECT * FROM dbo.RoadsTC();GO-- All paths and distances in Roads (15262 rows)WITH Roads2AS(  SELECT city1 AS from_city, city2 AS to_city, distance FROM dbo.Roads  UNION ALL  SELECT city2, city1, distance FROM dbo.Roads),RoadPaths AS(  SELECT from_city, to_city, distance,    CAST('.' + from_city + '.' + to_city + '.' AS VARCHAR(MAX)) AS path  FROM Roads2  UNION ALL  SELECT F.from_city, T.to_city, F.distance + T.distance,    CAST(F.path + T.to_city + '.' AS VARCHAR(MAX))  FROM RoadPaths AS F    JOIN Roads2 AS T      ON CASE WHEN F.path LIKE '%.' + T.to_city + '.%'              THEN 1 ELSE 0 END = 0      AND F.to_city = T.from_city)-- Return all paths and distancesSELECT * FROM RoadPaths;-- Shortest paths in RoadsWITH Roads2AS(  SELECT city1 AS from_city, city2 AS to_city, distance FROM dbo.Roads  UNION ALL  SELECT city2, city1, distance FROM dbo.Roads),RoadPaths AS(  SELECT from_city, to_city, distance,    CAST('.' + from_city + '.' + to_city + '.' AS VARCHAR(MAX)) AS path  FROM Roads2  UNION ALL  SELECT F.from_city, T.to_city, F.distance + T.distance,    CAST(F.path + T.to_city + '.' AS VARCHAR(MAX))  FROM RoadPaths AS F    JOIN Roads2 AS T      ON CASE WHEN F.path LIKE '%.' + T.to_city + '.%'              THEN 1 ELSE 0 END = 0      AND F.to_city = T.from_city),RoadsMinDist -- Min distance for each pair in TCAS(  SELECT from_city, to_city, MIN(distance) AS mindist  FROM RoadPaths  GROUP BY from_city, to_city)-- Return shortest paths and distancesSELECT RP.*FROM RoadsMinDist AS RMD  JOIN RoadPaths AS RP    ON RMD.from_city = RP.from_city    AND RMD.to_city = RP.to_city    AND RMD.mindist = RP.distance;GO-- Load Shortest Road Paths Into a TableWITH Roads2AS(  SELECT city1 AS from_city, city2 AS to_city, distance FROM dbo.Roads  UNION ALL  SELECT city2, city1, distance FROM dbo.Roads),RoadPaths AS(  SELECT from_city, to_city, distance,    CAST('.' + from_city + '.' + to_city + '.' AS VARCHAR(MAX)) AS path  FROM Roads2  UNION ALL  SELECT F.from_city, T.to_city, F.distance + T.distance,    CAST(F.path + T.to_city + '.' AS VARCHAR(MAX))  FROM RoadPaths AS F    JOIN Roads2 AS T      ON CASE WHEN F.path LIKE '%.' + T.to_city + '.%'              THEN 1 ELSE 0 END = 0      AND F.to_city = T.from_city),RoadsMinDistAS(  SELECT from_city, to_city, MIN(distance) AS mindist  FROM RoadPaths  GROUP BY from_city, to_city)SELECT RP.*INTO dbo.RoadPathsFROM RoadsMinDist AS RMD  JOIN RoadPaths AS RP    ON RMD.from_city = RP.from_city    AND RMD.to_city = RP.to_city    AND RMD.mindist = RP.distance;CREATE UNIQUE CLUSTERED INDEX idx_uc_from_city_to_city  ON dbo.RoadPaths(from_city, to_city);GO-- Return shortest path between Los Angeles and New YorkSELECT * FROM dbo.RoadPaths WHERE from_city = 'LAX' AND to_city = 'JFK';GO-- Creation Script for the RoadsTC UDFIF OBJECT_ID('dbo.RoadsTC') IS NOT NULL  DROP FUNCTION dbo.RoadsTC;GOCREATE FUNCTION dbo.RoadsTC() RETURNS @RoadsTC TABLE(  uniquifier INT          NOT NULL IDENTITY,  from_city  VARCHAR(3)   NOT NULL,  to_city    VARCHAR(3)   NOT NULL,  distance   INT          NOT NULL,  route      VARCHAR(MAX) NOT NULL,  PRIMARY KEY (from_city, to_city, uniquifier))ASBEGIN  DECLARE @added AS INT;  INSERT INTO @RoadsTC    SELECT city1 AS from_city, city2 AS to_city, distance,      '.' + city1 + '.' + city2 + '.'    FROM dbo.Roads;  SET @added = @@rowcount;  INSERT INTO @RoadsTC    SELECT city2, city1, distance, '.' + city2 + '.' + city1 + '.'    FROM dbo.Roads;  SET @added = @added + @@rowcount;  WHILE @added > 0 BEGIN    INSERT INTO @RoadsTC      SELECT DISTINCT TC.from_city, R.city2,        TC.distance + R.distance, TC.route + city2 + '.'      FROM @RoadsTC AS TC        JOIN dbo.Roads AS R          ON R.city1 = TC.to_city      WHERE NOT EXISTS        (SELECT * FROM @RoadsTC AS TC2         WHERE TC2.from_city = TC.from_city           AND TC2.to_city = R.city2           AND TC2.distance <= TC.distance + R.distance)        AND TC.from_city <> R.city2;    SET @added = @@rowcount;    INSERT INTO @RoadsTC      SELECT DISTINCT TC.from_city, R.city1,        TC.distance + R.distance, TC.route + city1 + '.'      FROM @RoadsTC AS TC        JOIN dbo.Roads AS R          ON R.city2 = TC.to_city      WHERE NOT EXISTS        (SELECT * FROM @RoadsTC AS TC2         WHERE TC2.from_city = TC.from_city           AND TC2.to_city = R.city1           AND TC2.distance <= TC.distance + R.distance)        AND TC.from_city <> R.city1;    SET @added = @added + @@rowcount;  END  RETURN;ENDGO-- Return shortest paths and distancesSELECT from_city, to_city, distance, routeFROM (SELECT from_city, to_city, distance, route,        RANK() OVER (PARTITION BY from_city, to_city                     ORDER BY distance) AS rk      FROM dbo.RoadsTC()) AS RTCWHERE rk = 1;GO-- CleanupDROP TABLE dbo.RoadPaths;GO

  

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台