implemented in Prolog itself, but not with the desired performance because Prolog lacks the appropriate primitives.

The conclusion is that changes are needed at the level of the Prolog engine itself. This requires an extension of the WAM (Warren Abstract Machine) which is the underlying abstract machine for most Prolog implementations. The extended WAM provides the or operator as discussed above: it permanently removes branches from the pack that do not ned to be investigated anymore.  This extended WAM has become the basis of a new Prolog engine dedicated to inductive logic programming, called ILPROLOG. This section continues with the introduction of some basic terminology for query packs and explains at a high level how query pack execution works. Next our meta-interpreter for the query pack execution is given and finally the changes needed for the WAM are clarified.

## 3.1.1 Principles Of Query Packs (Execution)

Before we discuss query pack execution in detail, note the following two points: (1) during the pack execution, the pruning of a branch must survive backtracking; (2) when executing a pack we are not interested in any variable instantiations, just in whether a member of the pack succeeds or not. In our previous description we were interested in the binding to the variable I. Since each branch can bind I to only one value - the query number - we collect these values in practice by a side effect denoted in Section 3.2 by report_success .

The starting point for the query pack execution mechanism is the usual Prolog execution of a query Q given a Prolog program P . By backtracking Prolog will generate all the solutions for Q by giving the possible instantiations θ such that Qθ succeeds in P .

A query pack consists of a conjunction of literals and a set of alternatives, where each alternative is again a query pack. Note that leaves are query packs with an empty set of alternatives. For each query pack Q, conj(Q) denotes the conjunction and children(Q)
denotes the set of alternatives. A set of queries is then represented by a so-called root query pack. For every query pack Q, there is a path of query packs starting from the root query pack Qroot and ending at the query pack itself, namely < Qroot ; Q1; …; Qn; Q >. The query packs in this path are the predecessors of Q. Every query pack has a set of dependent queries, dependent queries(Q). Let < Qroot , Qi,, ..., Qi,, Q > be the path to Q, then dependent_queries(Q) = {conj(Qroot) ∧ conj(Qit,) ∧ . . ∧ conj(Qin) ∧ conj(Q) ∧ conj(Qjt) ∧
.. ∧ con ĵ ( Q jm ) ∧ con ĵ ( Q i ) | < Q i Q jm ; ..., Q jm ; Q i > is a path from Q to a leaf Q i }. Note that dependent queries( Qroot ) are actually the members of the query pack as described earlier.

Example 3 For the query pack in Figure 1, Qroot is the root of the tree, conj(Qroot) is p(X).  The set children(Qroot) contains the 4 query packs which correspond to the trees rooted at the 4 sons of the root of the tree.  Suppose that these query packs are named (from left to right) Q1, Q2, Q3, and Q1. Then conj(Q2) equals (q(X,a), I = 2), children(Q2) equals the empty set, conj(Ql) equals (q(X,Y),t(X)), and dependentqueries(Ql) equals
{p(X), q(X,Y), t(X), I = 4), (p(X), q(X,Y), t(X), r(Y, 1), I = 5)}.

Execution of a root query pack Qroot aims at finding out which queries of the set dependent queries( Qroot ) succeed. If a query pack is executed as if the ors were usual disjunctions, backtracking occurs over queries that have already succeeded and too many