sql-server-2008t-sqlsortingtopological-sort

Topological sorting in sql


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


Solution

  • 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