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:

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

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.

Example 2   In this example the literals $I = i$ have been left out, because they do not contribute to the discussion:

      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

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

This query pack can be represented as the tree in Figure 1. For a query pack $\cal Q$ 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 $Q$ which is a member of $\cal Q$, denoted $Q \in \cal Q$. The or construct is implicit in the branching points.

Figure 1: A query pack.

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.