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.

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

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(_, _)),
         solved(0, _), !.

 meta_execute_qp((A,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),
 meta_execute_qp(leaf(QpNbF, ChildNb , QueryNb)) :- 
         !, % 'leaf' corresponds to the end of a query
         write(succeed(QueryNb)), nl,
 handlechildren([], _, _).
 handlechildren([C|_], 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