next up previous
Next: WAM Extensions Up: Efficient Execution of Query Previous: Principles of Query Packs


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:

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.
\begin{figure}\begin{center}
\epsfig{file=flockajN.eps}\end{center}\end{figure}

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

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)
         ).


next up previous
Next: WAM Extensions Up: Efficient Execution of Query Previous: Principles of Query Packs
Hendrik Blockeel 2002-02-26