A Meta-interpreter for Query Packs

The first implementation of the query pack execution algorithm is the meta-interpreter meta_execute_qp(Q). The meta-interpreter uses the following labelling in its representation of a query pack:

• Query pack number All the non-leaf query packs in the tree are numbered, depth first, from left to right $(qp(i))$.
• Query number Each leaf is numbered, from left to right. If the original queries were numbered sequentially, then the numbers at the leaves correspond with these $( q(i))$.
• Child number For each non-leaf query pack with N children, all children are numbered from 1 up to N sequentially $(ch(i))$.

Consider the query pack a, (b, (c or d or e) or f or g, (h or i or j)). Note that the atoms in the example could in general be arbitrary conjunctions of non-ground terms. Its labelling is shown in Figure 3.

Figure 3: Query pack numbers $qp(i)$, Query numbers $q(i)$ and Child numbers $ch(i)$ in our example.

A labelled query pack ${\cal Q}$ is then represented as a Prolog term as follows (with ${\cal Q}_{f}$ the father of ${\cal Q}$):

• A leaf ${\cal Q}$ is represented by the term $(c, leaf(qpnbf,chnb,qnb))$ with $c$ the $conj({\cal Q})$, $qpnbf$ the query pack number of ${\cal Q}_f$, $chnb$ the child number of ${\cal Q}$ w.r.t. ${\cal Q}_f$, and $qnb$ the query number of ${\cal Q}$.
• A non-leaf ${\cal Q}$ is represented by the term $(c, or(cs,qpnbf,qpnb,chnb,totcs)$ with $c$ the $conj({\cal Q})$, $cs$ the list $children({\cal Q})$, $qpnbf$ the query pack number of ${\cal Q}_{f}$, $qpnb$ the query pack number of ${\cal Q}$, $chnb$ the child number of ${\cal Q}$ w.r.t. ${\cal Q}_{f}$, and $totcs$ the total number of $children({\cal Q})$). The query pack number of the father of the root query pack is assumed to be zero.

The example of Figure 3 has the following representation (as a Prolog term):

(a, or([(b,or([(c,leaf(2,1,1)),(d,leaf(2,2,2)),(e,leaf(2,3,3))],1,2,1,3)),
        (f,leaf(1,2,4)),
        (g,or([(h,leaf(3,1,5)),(i,leaf(3,2,6)),(j,leaf(3,3,7))],1,3,3,3))],
       0,1,1,3))

During the execution of the meta-interpreter, solved/2 facts are asserted. Each fact solved($qpnb$, $chnb$) denotes that the child with number $chnb$ from query pack with number $qpnb$ has succeeded. Such facts are asserted when reaching a leaf and also when all children of a query pack have succeeded. The meta-interpreter only executes children for which no solved/2 fact has been asserted.

Note that the time-complexity of this meta-interpreter is not yet as desired. Execution of a query pack will always be dependent on the number of original children, instead of the number of remaining (as yet unsuccessful) children.

run_QueryPack(Q) :-
         preprocess(Q, Qlabeled, 0, 1, 1, 1, _, _),
         % The code for preprocessing is given in Appendix A
         retractall(solved(_, _)),
         meta_execute_qp(Qlabeled),
         solved(0, _), !.

 meta_execute_qp((A,B)) :- !, 
         call(A),
         meta_execute_qp(B).
 meta_execute_qp(or(Cs, QpNbF, QpNb, ChildNb, TotCs)) :- 
         !,    % 'or' corresponds to a non-leaf query pack
         handlechildren(Cs, QpNb, 1),
         all_solved(QpNb, 0, TotCs),
         assert(solved(QpNbF,ChildNb)).
 meta_execute_qp(leaf(QpNbF, ChildNb , QueryNb)) :- 
         !, % 'leaf' corresponds to the end of a query
         write(succeed(QueryNb)), nl,
         assert(solved(QpNbF,ChildNb)).
 
 handlechildren([], _, _).
 handlechildren([C|_], QpNb, ChildNb) :-
         not(solved(QpNb,ChildNb)), 
         once(meta_execute_qp(C)), fail.
 handlechildren([_|Cs], QpNb, ChildNb) :-
         ChildNb1 is ChildNb + 1,
         handlechildren(Cs, QpNb, ChildNb1).
 
 all_solved(QpNb, ChildNb, TotCs) :- 
         (ChildNb = TotCs -> true 
         ;   ChildNb1 is ChildNb + 1,
             solved(QpNb, ChildNb1),
             all_solved(QpNb, ChildNb1, TotCs)
         ).