sql中的拓扑排序

Question

我正在解决表中某些对象之间的依赖关系。 我必须对对象做一些事情来排序它们的依赖性。 例如，第一个对象不依赖于任何对象。第二个和第三个取决于第一个，依此类推。我必须使用拓扑排序。 有人可以展示在 t-sql 中进行排序的实现示例吗？ 我有一张桌子：

create table dependency
(
  DependencyId PK
  ,ObjectId
  ,ObjectName
  ,DependsOnObjectId
)

我想得到

对象ID 对象名 排序顺序

Answer 1

接缝，有效：

declare @step_no int

declare @dependency table 
(
  DependencyId  int
  ,ObjectId     int 
  ,ObjectName   varchar(100)
  ,DependsOnObjectId int 
  ,[rank]       int         NULL
  ,degree       int         NULL
);

insert into @dependency values (5, 5, 'Obj 5', 2, NULL, NULL)
insert into @dependency values (6, 6, 'Obj 6', 7, NULL, NULL)
insert into @dependency values (2, 2, 'Obj 2', 1, NULL, NULL)
insert into @dependency values (3, 3, 'Obj 3', 1, NULL, NULL)
insert into @dependency values (1, 1, 'Obj 1', 1, NULL, NULL)
insert into @dependency values (4, 4, 'Obj 4', 2, NULL, NULL)
insert into @dependency values (7, 7, 'Obj 7', 2, NULL, NULL)


update @dependency set rank = 0
-- computing the degree of the nodes
update  d set d.degree = 
    (
        select count(*) from @dependency t
        where t.DependsOnObjectId = d.ObjectId 
        and t.ObjectId <> t.DependsOnObjectId
    )
from @dependency d


set @step_no = 1
while 1 = 1
begin
    update @dependency set rank = @step_no where degree = 0

    if (@@rowcount = 0) break
    update @dependency set degree = NULL where rank = @step_no

    update d set degree = (
        select count(*) from @dependency t
        where t.DependsOnObjectId = d.ObjectId and t.ObjectId != t.DependsOnObjectId
        and t.ObjectId in (select tt.ObjectId from @dependency tt where tt.rank = 0))
    from @dependency d
    where d.degree is not null

    set @step_no = @step_no + 1
end

select * from @dependency order by rank

Answer 2

您有一个简单的树结构，每个

ObjectId

只有一条路径，因此基于遍历的

DependsOnObjectId

链接数量的标签仅给出一个答案，并且是一个足够好的答案来首先处理正确的内容。 使用公用表表达式很容易做到这一点，并且具有易于移植的优点：

dependency_levels 为
（
  选择 ObjectId、ObjectName、0 作为 links_traversed 
  来自 DependsOnObjectId 为 null 的依赖项
  联合所有
  选择对象 ID、对象名称、links_traversed+1
  来自依赖 
  将 dependency_levels 加入 dependency.DependsOnObjectId = dependency_levels.ObjectId
）
选择对象 ID、对象名称、链接遍历
来自 dependency_levels
按 links_traversed 排序