qplan.pl

contents

%query: qplan(i,o).

%------------------------------------------------------------------------------
%	Benchmark Program - query plan of CHAT80
%
%	by D.H.D. Warren
%	Date: 
%
%------------------------------------------------------------------------------
% QPLAN - supplies the control information (ie. sequencing and cuts) needed
%         for efficient execution of a query.

%:- entry(qplan(X,Y),[share([[X],[Y]]),free([Y])]).

%:-public qplan/2.
:- op(900,xfx,`=).
:- op(900,xfx,=+).
:- op(900,xfx,=:).
:- op(450,xfy,:).
:- op(400,xfy,'##').
:- op(300,fx,`).
:- op(200,xfx,--).
:- op(359,xf,ject).
/*
:-mode
   qplan(+,-),
   qplan(+,+,-,-),
   mark(+,-,+,-),
   subquery(+,-,?,?,?,?),
   negate(+,+,-),
   negationcost(+,-),
   setofcost(+,+,-),
   variables(+,+,-),
   variables(+,+,+,-),
   quantificate(+,+,?,-),
   log2(+,-),
   schedule(+,+,-),
   schedule1(+,+,-),
   maybe_cut(+,+,?,-),
   plan(+,+,+,+,-),
   is_conjunction(+),
   marked(+,?,?,?),
   freevars(+,?),
   best_goal(+,+,+,?,?,-),
   instantiate(+,+,-),
   instantiate0(+,+,-),
   recombine(+,+,-),
   incorporate(+,+,+,+,+,-),
   incorporate0(+,+,+,+,-),
   minimum(+,+,-),
   add_keys(+,-),
   strip_keys(+,-),
   strip_key(+,?),
   variablise(+,+,-),
   variablise(+,+,+,+),
   cost(+,+,-),
   cost(+,+,+,+,-),
   instantiated(+,+,-).
*/
qplan((P:-Q),(P1:-Q1)) :- qplan(P,Q,P1,Q1), !.
qplan(P,P).

qplan(X0,P0,X,P) :-
   numbervars(X0,0,I), variables(X0,0,Vg),
   numbervars(P0,I,N),
   mark(P0,L,0,Vl),
   schedule(L,Vg,P1),
   quantificate(Vl,0,P1,P2),
   functor(VA,$,N),
   variablise(X0,VA,X),
   variablise(P2,VA,P).

mark(X^P,L,Q0,Q) :- !, variables(X,Q0,Q1), mark(P,L,Q1,Q).
mark((P1,P2),L,Q0,Q) :- !,
   mark(P1,L1,Q0,Q1),
   mark(P2,L2,Q1,Q),
   recombine(L1,L2,L).
mark(\+P,L,Q,Q) :- !, mark(P,L0,0,Vl), negate(L0,Vl,L).
mark(SQ,[m(V,C,SQ1)],Q0,Q0) :- subquery(SQ,SQ1,X,P,N,Q), !,
   mark(P,L,0,Vl),
   L=[Q],   % Too bad about the general case!
   marked(Q,Vq,C0,_),
   variables(X,Vl,Vlx),
   setminus(Vq,Vlx,V0),
   setofcost(V0,C0,C),
   variables(N,V0,V).
mark(P,[m(V,C,P)],Q,Q) :-
   variables(P,0,V),
   cost(P,V,C).

subquery(setof(X,P,S),setof(X,Q,S),X,P,S,Q).
subquery(numberof(X,P,N),numberof(X,Q,N),X,P,N,Q).

negate([],_,[]).
negate([P|L],Vl,[m(Vg,C,\+P)|L1]) :-
   freevars(P,V),
   setminus(V,Vl,Vg),
   negationcost(Vg,C),
   negate(L,Vl,L1).

content may be truncated. 'popout' for larger text window.