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 $\theta$ such that $Q\theta$ 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 ${\cal Q}$, $conj({\cal Q})$ denotes the conjunction and $children({\cal Q})$ denotes the set of alternatives. A set of queries is then represented by a so-called root query pack. For every query pack ${\cal Q}$, there is a path of query packs starting from the root query pack ${\cal Q}_{root}$ and ending at the query pack itself, namely $<{\cal Q}_{root}$ , ${\cal Q}_1$, ..., ${\cal Q}_{n}$, ${\cal Q}>$. The query packs in this path are the predecessors of ${\cal Q}$. Every query pack has a set of dependent queries, $dependent\_queries({\cal Q})$. Let $<{\cal Q}_{root}$ , ${\cal Q}_{i_1}$, ..., ${\cal Q}_{i_n}$, ${\cal Q}>$ be the path to ${\cal Q}$, then $dependent\_queries({\cal Q})$ $=$ $\{ conj({\cal Q}_{root} ) \wedge conj({\cal Q}_{i_1}) \wedge \ldots \wedge conj... ...al Q}_{j_1}) \wedge \ldots \wedge conj({\cal Q}_{j_m}) \wedge conj( {\cal Q}_l)$ $\vert$ $<{\cal Q} , {\cal Q}_{j_1}$, ..., ${\cal Q}_{j_m}$, ${\cal Q}_l>$ is a path from $\cal Q$ to a leaf ${\cal Q}_l \}$. Note that $dependent\_queries({\cal Q}_{root})$ are actually the members of the query pack as described earlier.

Example 3   For the query pack in Figure 1, ${\cal Q}_{root}$ is the root of the tree. $conj({\cal Q}_{root})$ is $p(X)$. The set $children({\cal Q}_{root})$ 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) ${\cal Q}_{1}$, ${\cal Q}_{2}$, ${\cal Q}_{3}$, and ${\cal Q}_{4}$. Then $conj({\cal Q}_{2})$ equals $(q(X,a), I = 2)$, $children({\cal Q}_{2})$ equals the empty set, $conj({\cal Q}_{4})$ equals $(q(X,Y), t(X))$, and $dependent\_queries({\cal Q}_{4})$ 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 ${\cal Q}_{root}$ aims at finding out which queries of the set $dependent\_queries({\cal Q}_{root})$ 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 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 ${\cal Q}$ can be safely removed if all the queries that depend on it (i.e., all the queries in $dependent\_queries({\cal Q})$) succeeded once. For a leaf ${\cal Q}$ (empty set of children), success of $conj({\cal Q})$ is sufficient to remove it. For a non-leaf ${\cal Q}$, we wait until all the dependent queries report success or equivalently until all the query packs in $children({\cal 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({\cal 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 ${\cal Q} \theta$ is defined by the algorithm $execute\_qp( {\cal Q}, \theta)$ (Figure 2) which imposes additional control on the usual Prolog execution.

Figure 2: The query pack execution algorithm.

The usual Prolog execution and backtracking behaviour is modelled by the while loop (line 1) which generates all possible solutions $\sigma$ 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 calling query pack.

The additional control manages the $children({\cal Q})$. For each solution $\sigma$, the necessary children of ${\cal 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 $\sigma$, not all of the alternatives that were initially there, have to be executed any more. Moreover, by returning success the backtracking over the current query pack conjunction $conj({\cal Q})$ is stopped: all branches have reported success.