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:

• Query pack number All the non-leaf query packs in the tree are numbered, depth first, from left to right .
• 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 .
• Child number For each non-leaf query pack with N children, all children are numbered from 1 up to N sequentially .

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.

A labelled query pack is then represented as a Prolog term as follows (with the father of ):

• A leaf is represented by the term with the , the query pack number of , the child number of w.r.t. , and the query number of .
• A non-leaf is represented by the term with the , the list , the query pack number of , the query pack number of , the child number of w.r.t. , and the total number of ). 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(, ) denotes that the child with number from query pack with number 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: WAM Extensions Up: Efficient Execution of Query Previous: Principles of Query Packs
Hendrik Blockeel 2002-02-26