Recursive SQL to Find Critical Path?

Question

Given these two tables:

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

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

I'm trying to find the latest end date of the Tasks immediate predecessors. For the Task table, ScheduledStart is nullable. The idea behind this is that if it does not have an explicitly scheduled start, it could be derived from its predecessors (the root level tasks must have a ScheduledStart, so the calculation can start somewhere). Tasks can also have multiple predecessors.

I've come up with a fake recursive function that (I think) does what I'm looking for. What I'm wondering is if there is a more efficient way to write this in SQL since I'm used to more procedural programming. Should I just make Function_A a stored procedure and have it call itself? Is there a way this can be accomplished with a WITH statement (and are those a more efficient way of recursive querying, or a recursive function like this)?

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;
}

Thanks for the help!

Answer 1

You can use a recursive CTE to find all upstream tasks. Then you can calculate the first available start date based on the last ending child task. It would require multiple passes if a task has child tasks that themselves have an unknown start date.

Example code using a recursive 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

Test data:

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

This prints:

3    2010-01-07

It filters out task 5, which has child tasks with an unknown start date. If you enter the calculated start date for task 3, you can then calculate the start date for task 5.