SQL

SQL-图，树，层次结构和递归查询

树：指二叉， 三叉树，属于有向无循环图， 且根结点只有一个

层次结构： 如料表， 属于有向无循环图DAG， 不过和树不同， 根结点可以是一个或多个

图： 通用概念， 主要是看是否有循环， 循环的如道路系统，即无向循环图

案例一：返回指定结点的所有下属（员工系统，树）

With SubsCTE

As

(

--定位点成员， 返回指定的根结点

Select empid, empname, 0 as Lvl

From dbo.Employees

Where empid=@root

www.

Union All

--递归成员， 返回下级员工

Select C.empid, C.empname, P.lvl+1

From SubsCTE as P

Join dbo.Employees as C on C.managerID = P.empid

)

Select * from SubsCTE;

案例二： 返回指定结点的所有祖先

With MangersCTE

As

(

Select empid, managerid, empname, 0 as lvl

From dbo.Employees

Where empid = @empid

Union All

Select p.empid, p.ManagerID, p.empname, C.lvl+1

From ManagersCTE as C

Join dbo.Employees as P on C.managerid = p.empid

)

案例三： 返回带有路径的员工链

With SubsCTE

As

(

--定位点成员， 返回指定的根结点

Select empid, empname, 0 as Lvl, ('.' +Cast(empid as varchar(10)) + '.')) as Path

From dbo.Employees www.

Where empid=@root

Union All

--递归成员， 返回下级员工

Select C.empid, C.empname, P.lvl+1 , (P.path +Cast(C.empid as varchar(10))+'.') as Path

From SubsCTE as P

Join dbo.Employees as C on C.managerID = P.empid

)

Select * from SubsCTE;

案例四： 检测员工管理关系是否包含循环关系：1->3->1视为循环

思路： 采用员工路径链进行判断， 若包含现有的员工编号则视为循环, 添加循环标识cycle列

With SubsCTE

As

(

--定位点成员， 返回指定的根结点

Select empid, empname, 0 as Lvl, ('.' +Cast(empid as varchar(10)) + '.')) as Path,

--根结点不存在循环

0 as cycle

From dbo.Employees

Where empid=@root

Union All

--递归成员， 返回下级员工

Select C.empid, C.empname, P.lvl+1 , (P.path +Cast(C.empid as varchar(10))+'.') as Path，

--如果父路径包含子级ID则检测到循环

Case When P.Path like '%.'+Cast(c.empid as varchar(10)) +'.%' then 1 else 0 as cycle

From SubsCTE as P www.

Join dbo.Employees as C on C.managerID = P.empid

And p.cycle = 0--为防止死循环， 对已经检测出有循环的就不再进行循环了

)

Select * from SubsCTE where cycle=1;--仅返回有循环的路径行

案例五： 无向图返回最短路径， 以道路系统为例

Roads表结构：City1, City2, Distance(距离)--表示城市1与城市2的距离

思路： 先将无向道路图转换成有向图， 将一行变成两行， 再递归查询所有从出发城市能够到达的城市路径和距离，查询过程中为避免死循环， 应对循环做出判断， 当路径包含子路径时即不再循环， 再按照出发城市，到达城市进行分组， 获取最小路径， 最后再选择出所有出发城市， 到达城市和最短路径。

With Roads2

As

(

--将无向图变为有向图， 每行产生两行

Select city1 as From_City, city as To_City, distance from dbo.Roads

Union all

Select city2, city1, distance from dbo.Roads

),

RoadsPath 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)) as Path

From RoadPaths as F

Join Roads2 as T

--递归死循环判断， 当父级路径已经包含能到达的城市时， 不再进行递归循环

On (Case When F.path like '%.' + T.to_city +'.%' then 1 else o end)=0

And F.to_city = T.from_city www.

),

RoadsMinDist --用于选取出最短路径

As

(

Select from_city, to_city, Min(distance) as minDist

From RoadPaths

Group by from_city, to_city

)

Select RP.*

From RoadMinDist as RMD

Inner join RoadPaths as RP

On RMD.from_city = RP.from_city

And RMD.to_city = RP.to_city

And RMD.MinDist= RP.distance

作者 Chao Hong