Query Packs

For simplicity, we make abstraction of the existence of keys in the following examples. What is relevant here, is that for each query we are only interested in whether it succeeds or not, not in finding all answer substitutions.

Given the following set of queries

p(X), I = 1. p(X), q(X,a), I = 2. p(X), q(X,b), I = 3. p(X), q(X,Y), t(X), I = 4. p(X), q(X,Y), t(X), r(Y,1), I = 5.we can choose to evaluate them separately. Since we are only interested in one - the first - success for each query, we would evaluate in Prolog the queries

once((p(X), I = 1)). once((p(X), q(X,a), I = 2)). once((p(X), q(X,b), I = 3)). once((p(X), q(X,Y), t(X), I = 4)). once((p(X), q(X,Y), t(X), r(Y,1), I = 5)).

The wrapper *once/1* is a pruning primitive and prevents the
unnecessary search for more solutions. Its definition in Prolog is
simply

once(Goal) :- call(Goal), !.

An alternative way to evaluate the queries consists in merging them into one (nested) disjunction as in:

The set of queries can now be evaluated as a whole: the success of one branch in the disjunctive query corresponds to the success of the corresponding individual query.

Compared to the evaluation of the individual queries, the disjunctive query has both an advantage and a disadvantage:

- +
- all the queries have the same prefix
`p(X)`, which is evaluated once in**each**individual query, while in the disjunctive query, the goal`p(X)`is evaluated only once; depending on the evaluation cost of`p/1`, this can lead to arbitrary performance gains. - the usual Prolog pruning primitives are not powerful enough to prevent all the unnecessary backtracking after a branch in the disjunctive query has succeeded; this is explained further in Example 2.

p(X), q(X). p(X), r(X).Evaluating these queries separately means evaluating

once((p(X), q(X))). once((p(X), r(X))).or equivalently

p(X), q(X), !. p(X), r(X), !.The corresponding disjunctive query is

p(X), (q(X) ; r(X)).

We can now try to place a pruning primitive in the disjunctive query:
`!/0` at the end of each branch results in

p(X), (q(X), ! ; r(X), !)

The scope of the first cut is clearly too large: after the goal `q(X)`
has succeeded, the cut will prevent entering the second branch. It
means that adding the cut in the disjunctive query leads to a wrong
result.

Using `once/1` in the disjunctive query results in

p(X), (once(q(X)) ; once(r(X)))

This results in a correct query. However, both branches are still
executed for every binding that the goal `p(X)` produces, even if both
branches have succeeded already.

The combination of the advantage of the disjunctive query with the
advantage of the individual query with pruning (once or cut) results in the
notion of the *query pack*. Syntactically, a query pack looks
like a disjunctive query where the *;* control construct is
replaced by a new control construct denoted by *or*. So the query
pack corresponding to the disjunctive query above is

This query pack can be represented as the tree in Figure
1. For a query pack such a tree has
literals or conjunctions of literals in the nodes. Each path from the
root to a leaf node represents a conjunctive query which is a *member* of , denoted . The *or* construct
is implicit in the branching points.

The intended procedural behaviour of the *or* construct is that
once a branch has succeeded, it is effectively pruned away from the
pack during the evaluation of the query pack on the current example.
This pruning must be recursive, i.e., when all branches in a subtree of
the query pack have succeeded, the whole subtree must be pruned.
Evaluation of the query pack then terminates when all subtrees have
been pruned or all of the remaining queries fail for the example.

The semantics of the *or* construct and its efficient
implementation is the subject of the rest of this section. It should
however be clear already now that in the case that all the answers of
each query are needed, pruning cannot be performed and the disjunctive
query is already sufficient, i.e., query packs are useful when a single
success per query suffices.