Topological sorting in sql

Question

I am resolving dependency between some objects in a table. I have to do something with objects in order their dependency. For example, the first object doesn't depend on any object. The second and third ones depends on first one and so on. I have to use topological sorting. Could someone show the sample of implementation so sorting in t-sql. I have a table:

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

I want to get

ObjectId ObjectName SortOrder

Polyhedron

Answer 1

It seams, it works:

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

Polyhedron

Just an observation: it works as long as your relationships don't contain any cycles, but this is a limitation of the topological sorting, not the algorithm. – Enuresis

Answer 2

You have a simple tree structure with only one path to each ObjectId so labeling based off number of DependsOnObjectId links traversed gives only one answer and a good enough answer to process the right stuff first. This is easy to do with a common table expression and has the benefit of easy portability:

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

Megalomania