Difficult Query With Many-To-Many Relationship

I'm writing a workflow management application for my work, and its somewhat complicated, here's a general idea of how it works:

- Anything that a company does is defined by a workflow.
- A workflow consists of tasks.
- Some tasks in a workflow can't be started until other tasks have been completed. If task A can't be started until tasks B and C are finished, then task A depends on B and C.

You might imagine that a bank has a workflow for handling a house loan. Before a bank could sign a contract with an applicant, they'd need proof of house ownership, but before they could get proof of house ownership they need an applicant's proof of identity like a driver's license or military ID.

Here's an oversimplified visual:

Each arrow points to its dependency. Each task can have multiple dependencies.

The setup above is represented in the database by a Tasks and a Dependencies table. Tasks has an ID field, and Dependencies has a TaskID and DependencyID field which are both foreign keys to Tasks.ID.

Code:

[Tasks]
ID Status Name
-- ------ ----
1 Done Start Processing Loan Application
2 Done Photocopy applicant's driver's license
3 NotDone Photocopy proof of house ownership
4 NotDone Get a copy of applicant's W-2 forms
5 NotDone Perform credit check on applicant
6 NotDone Sign loan contract


[Dependencies]
TaskID DependencyID
------ ------------
1 0
2 1
3 1
4 2
5 2
5 3
6 4
6 5


Tasks has a many-to-many relationship with itself.

Here's the hard part:
- A task can't be started until all of its dependencies have been completed.
- after a task is completed (meanings its status is marked "done"), I need to return a list of all the new tasks that are ready to be started.

When TaskID 2 is marked "Done", then TaskID 4 is ready to begin; however, TaskID 5 is not ready to begin since it depends on 2 and 3, and 3 hasn't been completed yet.

The requirements of the query are very simple, but the implementation is difficult.


I'll post a prelimenary solution in the next post: