A backward execution algorithm for nondeterministic AND-Parallel logic programs is described. The algorithm extends the class of semi-intelligent backward execution algorithms allowing them to efficiently execute programs with dynamic data dependencies. This is accomplished by generalizing the data dependency graph from an instance of data dependency for a clause to a static description of the set of possible data dependencies. This static description makes the algorithm suitable for compilation to a simple abstract instruction set.