Executing a graph of scripts

Question

I have some (SQL) scripts. Most of them have some requirements: other scripts that should be run before.

You can imagine the merged dependency trees as a directed graph. I would like to be able to "invalidate" a certain node in the graph, which would result in a composite script which contains everything (in the right order) that should be re-run to reach the ready state.

I think of something like the Debian start-up process... with a twist.

Edit: If anyone needs an explicit question startting with W and ending with a question mark, the closest I can give: How can I achieve the behavior described above.

Edit2: The ideal solution would be something that scans files matching a pattern, and reading dependency info from the first (comment) line.

Answer 1

You could use make. Create a naming convention for stampfiles (maybe use the logfiles from the scripts) The Makefile can be generated by a script. Example:

stamp1: stamp2 stamp3 script1.sql
     sql <script1.sql > $@

stamp2: stamp3 stamp5 script2.sql
     sql <script2.sql > $@

...

EDIT: A Makefile is a Directed Acyclic Graph. In the above fragment, stamp1 "depends on" {stamp2,stamp3,script3.sql}: if any of these change, the line below it (sql <>) will be executed. So if script1 should always be run after script2, the above fragment would apply.

Answer 2

[sorry, earlier answer was not general enough. now fixed]

you need a topological sort of your graph. see http://en.wikipedia.org/wiki/Topological_sorting which says:

The canonical application of topological sorting (topological order) is in scheduling a sequence of jobs or tasks

that defines both your initial build order and how you can restart from any intermediate, invalidated, point (just locate that point in the sorted list and start from there).

you can also sort the subgraph reachable from an invalidated point, which will give you less points in some cases (you avoid rebuilding points on the original sort that could have been built "in parallel" with the invalid node, and their children) (to find the subgraph from a point just do a breadth first search from there).

ps since the order must be the same you can simply filter the global order for points that are below your invalidated point. in other words, you don't need to actually do the resort, just start from the invalidated point on your global list and skip nodes that are not in the subgraph below your bad point.

Answer 3

Could you use an approach that "bubbles" the order by finding errors? I've done this a number of times manually and have thought about writing a program to automate it:

Something like, given list of scripts L:

1. Start Transaction
2. Set i=1
3. Run L[i]
4. If Error Move L[i] to end of L, Rollback, Goto 1
5. Else i=i+1, Goto 3