0 1 execute qp( pack Q, substitution θ) {
while ( σ ← next_solution( conj(Q)θ)

![0_image_0.png](0_image_0.png)

}
Figure 2: The query pack execution algorithm.

successes are detected.  To avoid this, it should be the case that as soon as a query succeeds, the corresponding part of the query pack should no longer be considered during backtracking.  Our approach realises this by reporting success of queries (and of query packs) to predecessors in the query pack. A (non-root) query pack Q can be safely removed if all the queries that depend on it (i.e., all the queries in dependent queries ( Q )) succeeded once. For a leaf Q (empty set of children), success of conj ( Q ) is sufficient to remove it. For a non-leaf Q, we wait until all the dependent queries report success or equivalently until all the query packs in children(Q) report success.

At the start of the evaluation of a root query pack, the set of children for every query pack in it contains all the alternatives in the given query pack. During the execution, query packs can be removed from children sets and thus the values of the children(Q) change accordingly. When due to backtracking a query pack is executed again, it might be the case that fewer alternatives have to be considered.

The execution of a query pack Q0 is defined by the algorithm execute qp(Q, 0) (Figure 2) which imposes additional control on the usual Prolog execution.

The usual Prolog execution and backtracking behaviour is modelled by the while loop
(line 1) which generates all possible solutions σ for the conjunction in the query pack. If no more solutions are found, fail is returned and backtracking will occur at the level of the clling query pack.

The additional control manages the children(Q). For each solution σ the necessary children of Q will be executed. It is important to notice that the initial set of children of a query pack is changed destructively during the execution of this algorithm. Firstly, when a leaf is reached, success is returned (line 8) and the corresponding child is removed from the query pack (line 6). Secondly, when a query pack that initially had several children, finally ends up with an empty set of children (line 6), also this query pack is removed (line 8).

The fact that children are destructively removed, implies that when due to backtracking the same query pack is executed again for a different σ, not all of the alternatives that were initially there, have to be executed any more.  Moreover, by returning success the