Рекурсивный SQL для поиска критического пути?

Question

Учитывая эти две таблицы:

[dbo].[Task]
[Id]   [Duration]   [ScheduledStart]
int    int          Nullable DateTime

[dbo].[TaskDependencies]
[Id]   [PredecessorTaskId]   [TaskId]
int    FK_Task_Id            FK_Task_Id

Я пытаюсь найти самую последнюю дату окончания Задач непосредственных предшественников.Для таблицы задач ScheduledStart обнуляется.Идея заключается в том, что если он не имеет явно запланированного запуска, он может быть получен от своих предшественников (задачи корневого уровня должны иметь ScheduledStart, чтобы вычисление могло начаться где-нибудь).Задачи также могут иметь несколько предшественников.

Я придумал поддельную рекурсивную функцию, которая (я думаю) делает то, что я ищу.Мне интересно, есть ли более эффективный способ написать это на SQL, так как я привык к более процедурному программированию.Должен ли я просто сделать Function_A хранимой процедурой и вызвать ее самому?Есть ли способ, которым это можно сделать с помощью оператора WITH (и это более эффективный способ рекурсивных запросов или подобной рекурсивной функции)?

DateTime Function_A(Task)
{
    var predecessorList = getPredecessors(Task)
    var latestEndDate;
    var currentPredecessorLatestEndDate;

    ForEach(Predecessor in predecessorList)
    {
        if(Predecessor.ScheduledStart != null)
        {
            if(latestEndDate != null)
            {
                if(Predecessor.StartDate + Predecessor.Duration > latestEndDate)
                {
                    latestEndDate = Predecessor.StartDate + Predecessor.Duration;
                }
            }
            else
            {
                latestEndDate = Predecessor.StartDate + Predecessor.Duration;
            }

        }
        else
        {
            currentPredecessorLatestEndDate = Function_A(Predecessor.Id);

            if(latestEndDate != null)
            {
                if(currentPredecessorEndDate > latestEndDate)
                {
                    latestEndDate = currentPredecessorEndDate;
                }
            }
            else
            {
                latestEndDate = currentPredecessorEndDate;              
            }
        }
    }

    return latestEndDate;
}

Спасибо за помощь!

Answer 1

Вы можете использовать рекурсивный CTE, чтобы найти все последующие задачи. Затем вы можете рассчитать первую доступную дату начала на основе последней конечной дочерней задачи. Потребуется несколько проходов, если у задачи есть дочерние задачи, у которых неизвестная дата начала.

Пример кода с использованием рекурсивного CTE:

;with Predecessors as
(
select  Id as RootId
,       null as ChildId
from    @Task
union all
select  p.RootId
,       cd.PredecessorTaskId as ChildId
from    @TaskDependencies cd
join    Predecessors p
on      cd.TaskId = ISNULL(p.ChildId, p.RootId)
)
select  RootId
,       max(dateadd(day, c.Duration+1, c.ScheduledStart))
from    Predecessors p
join    @Task c
on      p.ChildId = c.Id
        -- Filter out tasks with child tasks that themselves have
        -- an unknown start date.
where   not exists
        (
        select  *
        from    Predecessors p2
        join    @Task c2
        on      p2.ChildId = c2.Id
        where   p2.RootId = p.RootId
                and c2.ScheduledStart is null
        )
group by
        RootId

Данные испытаний:

declare @Task table (Id int, Duration int, ScheduledStart datetime)
insert @Task 
          select 1, 3, '2010-01-01'
union all select 2, 3, '2010-01-03'
union all select 3, 3, null
union all select 4, 3, '2010-01-01'
union all select 5, 3, null

declare @TaskDependencies table (PredecessorTaskId int, TaskId int)
insert @TaskDependencies
          select 1, 3
union all select 2, 3
union all select 4, 5
union all select 3, 5

Это печатает:

3    2010-01-07

Отфильтровывает задачу 5, в которой есть дочерние задачи с неизвестной датой начала. Если вы введете рассчитанную дату начала для задачи 3, вы сможете рассчитать дату начала для задачи 5.