Топологическая сортировка в sql - PullRequest
Новая
       14

Топологическая сортировка в sql

5 голосов
/ 24 марта 2011

Я разрешаю зависимость между некоторыми объектами в таблице.Я должен сделать что-то с объектами, чтобы их зависимость.Например, первый объект не зависит от какого-либо объекта.Второй и третий зависит от первого и так далее.Я должен использовать топологическая сортировка .Может ли кто-то показать пример реализации такой сортировки в t-sql.У меня есть таблица: 

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

Я хочу получить

ObjectId ObjectName SortOrder

Спасибо.

Ответы [ 3 ]

4 голосов
/ 25 марта 2011

Это швы, это работает: 

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
1 голос
/ 11 июня 2012

У вас есть простая древовидная структура с только одним путем к каждому ObjectId, поэтому маркировка на основе количества пройденных ссылок DependsOnObjectId дает только один ответ и достаточно хороший ответ, чтобы сначала обработать нужные вещи. Это легко сделать с помощью обычного табличного выражения и обеспечивает удобство переносимости: 

with dependency_levels as
(
  select ObjectId, ObjectName, 0 as links_traversed 
  from dependency where DependsOnObjectId is null
  union all
  select ObjectId, ObjectName, links_traversed+1
  from dependecy 
  join dependency_levels on dependency.DependsOnObjectId = dependency_levels.ObjectId
)
select ObjectId, ObjectName, links_traversed
from dependency_levels
order by links_traversed
0 голосов
/ 24 марта 2011

В этой статье рассматривается пример с топологической сортировкой и т-sql.Можно загрузить код , использованный в примере.

Редактировать: Ссылка не работает;Вот архивная версия: Использование топологической сортировки для создания сценария удаления базы данных

...