1/* @(#)qplan.pl	24.1 2/23/88 */
    2
    3/* 
    4	Copyright 1986, Fernando C.N. Pereira and David H.D. Warren,
    5
    6			   All Rights Reserved
    7*/
    8% QPLAN - supplies the control information (ie. sequencing and cuts) needed
    9%         for efficient execution of a query.
   10
   11:-public qplan/2.   12
   13:-mode
   14   qplan(+,-),
   15   qplan(+,+,-,-),
   16   mark(+,-,+,-),
   17   subquery(+,-,?,?,?,?),
   18   negate(+,+,-),
   19   negationcost(+,-),
   20   setofcost(+,+,-),
   21   variables(+,+,-),
   22   variables(+,+,+,-),
   23   quantificate(+,+,?,-),
   24   log2(+,-),
   25   schedule(+,+,-),
   26   schedule1(+,+,-),
   27   maybe_cut(+,+,?,-),
   28   plan(+,+,+,+,-),
   29   is_conjunction(+),
   30   marked(+,?,?,?),
   31   freevars(+,?),
   32   best_goal(+,+,+,?,?,-),
   33   instantiate(+,+,-),
   34   instantiate0(+,+,-),
   35   recombine(+,+,-),
   36   incorporate(+,+,+,+,+,-),
   37   incorporate0(+,+,+,+,-),
   38   minimum(+,+,-),
   39   add_keys(+,-),
   40   strip_keys(+,-),
   41   strip_key(+,?),
   42   variablise(+,+,-),
   43   variablise(+,+,+,+),
   44   cost(+,+,-),
   45   cost(+,+,+,+,-),
   46   instantiated(+,+,-).   47
   48qplan((P:-Q),(P1:-Q1)) :- qplan(P,Q,P1,Q1), !.
   49qplan(P,P).
   50
   51qplan(X0,P0,X,P) :-
   52   numbervars(X0,0,I), variables(X0,0,Vg),
   53   numbervars(P0,I,N),
   54   mark(P0,L,0,Vl),
   55   schedule(L,Vg,P1),
   56   quantificate(Vl,0,P1,P2),
   57   functor(VA,$,N),
   58   variablise(X0,VA,X),
   59   variablise(P2,VA,P).
   60
   61mark(X^P,L,Q0,Q) :- !, variables(X,Q0,Q1), mark(P,L,Q1,Q).
   62mark((P1,P2),L,Q0,Q) :- !,
   63   mark(P1,L1,Q0,Q1),
   64   mark(P2,L2,Q1,Q),
   65   recombine(L1,L2,L).
   66mark(\+P,L,Q,Q) :- !, mark(P,L0,0,Vl), negate(L0,Vl,L).
   67mark(SQ,[m(V,C,SQ1)],Q0,Q0) :- subquery(SQ,SQ1,X,P,N,Q), !,
   68   mark(P,L,0,Vl),
   69   L=[Q],   % Too bad about the general case!
   70   marked(Q,Vq,C0,_),
   71   variables(X,Vl,Vlx),
   72   setminus(Vq,Vlx,V0),
   73   setofcost(V0,C0,C),
   74   variables(N,V0,V).
   75mark(P,[m(V,C,P)],Q,Q) :-
   76   variables(P,0,V),
   77   cost(P,V,C).
   78
   79subquery(setof(X,P,S),setof(X,Q,S),X,P,S,Q).
   80subquery(numberof(X,P,N),numberof(X,Q,N),X,P,N,Q).
   81
   82negate([],_,[]).
   83negate([P|L],Vl,[m(Vg,C,\+P)|L1]) :-
   84   freevars(P,V),
   85   setminus(V,Vl,Vg),
   86   negationcost(Vg,C),
   87   negate(L,Vl,L1).
   88
   89negationcost(0,0) :- !.
   90negationcost(_V,1000).
   91
   92setofcost(0,_,0) :- !.
   93setofcost(_,C,C).
   94
   95variables('$VAR'(N),V0,V) :- !, setplusitem(V0,N,V).
   96variables(T,V,V) :- atomic(T), !.
   97variables(T,V0,V) :- functor(T,_,N), variables(N,T,V0,V).
   98
   99variables(0,_,V,V) :- !.
  100variables(N,T,V0,V) :- N1 is N-1,
  101   arg(N,T,X),
  102   variables(X,V0,V1),
  103   variables(N1,T,V1,V).
  104
  105quantificate(W-V,N,P0,P) :- !, N1 is N+18,
  106   quantificate(V,N,P1,P),
  107   quantificate(W,N1,P0,P1).
  108quantificate(0,_,P,P) :- !.
  109quantificate(V,N,P0,'$VAR'(Nr)^P) :-
  110   Vr is V /\ -(V),     % rightmost bit
  111   log2(Vr,I),
  112   Nr is N+I,
  113   N1 is Nr+1,
  114   V1 is V >> (I+1),
  115   quantificate(V1,N1,P0,P).
  116
  117log2(1,0) :- !.
  118log2(2,1) :- !.
  119log2(4,2) :- !.
  120log2(8,3) :- !.
  121log2(N,I) :- N1 is N>>4, N1=\=0, log2(N1,I1), I is I1+4.
  122
  123schedule([P],Vg,Q) :- !, schedule1(P,Vg,Q).
  124schedule([P1|P2],Vg,(Q1,Q2)) :- !, schedule1(P1,Vg,Q1), schedule(P2,Vg,Q2).
  125
  126schedule1(m(V,C,P),Vg,Q) :-
  127   maybe_cut(V,Vg,Q0,Q),
  128   plan(P,V,C,Vg,Q0).
  129
  130maybe_cut(V,Vg,P,{P}) :- disjoint(V,Vg), !.
  131maybe_cut(_V,_Vg,P,P).
  132
  133plan(\+P,Vg,_,_,\+Q) :- !, Vg = 0,
  134   marked(P,V,C,P1),
  135   plan(P1,V,C,Vg,Q1),
  136   quantificate(V,0,Q1,Q).
  137plan(SQ,Vg,_,_,SQ1) :- subquery(SQ,SQ1,X,P,_,Q), !,
  138   marked(P,V,C,P1),
  139   variables(X,Vg,Vgx),
  140   setminus(V,Vgx,Vl),
  141   quantificate(Vl,0,Q1,Q),
  142   plan(P1,V,C,Vgx,Q1).
  143plan(P,V,C,Vg,(Q,R)) :- is_conjunction(P), !,
  144   best_goal(P,V,C,P0,V0,PP),
  145   plan(P0,V0,C,Vg,Q),
  146   instantiate(PP,V0,L),
  147   add_keys(L,L1),
  148   keysort(L1,L2),
  149   strip_keys(L2,L3),
  150   schedule(L3,Vg,R).
  151plan(P,_,_,_,P).
  152
  153is_conjunction((_,_)).
  154
  155marked(m(V,C,P),V,C,P).
  156
  157freevars(m(V,_,_),V).
  158
  159best_goal((P1,P2),V,C,P0,V0,m(V,C,Q)) :- !,
  160   ( marked(P1,Va,C,Pa), Q=(Pb,P2) ; marked(P2,Va,C,Pa), Q=(P1,Pb) ), !,
  161   best_goal(Pa,Va,C,P0,V0,Pb).
  162best_goal(P,V,_C,P,V,true).
  163
  164instantiate(true,_,[]) :- !.
  165instantiate(P,Vi,[P]) :- freevars(P,V), disjoint(V,Vi), !.
  166instantiate(m(V,_,P),Vi,L) :- instantiate0(P,V,Vi,L).
  167
  168instantiate0((P1,P2),_,Vi,L) :-
  169   instantiate(P1,Vi,L1),
  170   instantiate(P2,Vi,L2),
  171   recombine(L1,L2,L).
  172instantiate0(\+P,V,Vi,L) :- !,
  173   instantiate(P,Vi,L0),
  174   freevars(P,Vf), setminus(Vf,V,Vl),
  175   negate(L0,Vl,L).
  176instantiate0(SQ,Vg,Vi,[m(V,C,SQ1)]) :- subquery(SQ,SQ1,X,P,_,Q), !,
  177   instantiate(P,Vi,L),
  178   L=[Q],   % Too bad about the general case!
  179   marked(Q,Vg,C0,_),
  180   setminus(Vg,Vi,V),
  181   variables(X,0,Vx),
  182   setminus(V,Vx,V0),
  183   setofcost(V0,C0,C).
  184instantiate0(P,V,Vi,[m(V1,C,P)]) :-
  185   setminus(V,Vi,V1),
  186   cost(P,V1,C).
  187
  188recombine(L,[],L) :- !.
  189recombine([],L,L).
  190recombine([P1|L1],[P2|L2],L) :-
  191   marked(P1,V1,C1,_), nonempty(V1),
  192   incorporate(P1,V1,C1,P2,L2,L3), !,
  193   recombine(L1,L3,L).
  194recombine([P|L1],L2,[P|L]) :- recombine(L1,L2,L).
  195
  196incorporate(P0,V0,C0,P1,L1,L) :-
  197   marked(P1,V1,C1,_),
  198   intersect(V0,V1), !,
  199   setplus(V0,V1,V),
  200   minimum(C0,C1,C),
  201   incorporate0(m(V,C,(P0,P1)),V,C,L1,L).
  202incorporate(P0,V0,C0,P1,[P2|L1],[P1|L]) :- incorporate(P0,V0,C0,P2,L1,L).
  203% JanW incorporate(P0,V0,C0,P1,[P2,L1],[P1|L]) :- incorporate(P0,V0,C0,G2,L1,L).
  204
  205incorporate0(P0,V0,C0,[P1|L1],L) :- incorporate(P0,V0,C0,P1,L1,L), !.
  206incorporate0(P,_,_,L,[P|L]).
  207
  208minimum(N1,N2,N1) :- N1 =< N2, !.
  209minimum(_N1,N2,N2).
  210
  211add_keys([],[]).
  212add_keys([P|L],[C-P|L1]) :- marked(P,_,C,_), add_keys(L,L1).
  213
  214strip_keys([],[]).
  215strip_keys([X|L],[P|L1]) :- strip_key(X,P), strip_keys(L,L1).
  216
  217strip_key(_C-P,P).
  218
  219variablise('$VAR'(N),VV,V) :- !, N1 is N+1, arg(N1,VV,V).
  220variablise(T,_,T) :- atomic(T), !.
  221variablise(T,VV,T1) :-
  222   functor(T,F,N),
  223   functor(T1,F,N),
  224   variablise(N,T,VV,T1).
  225
  226variablise(0,_,_,_) :- !.
  227variablise(N,T,VV,T1) :- N1 is N-1,
  228   arg(N,T,X),
  229   arg(N,T1,X1),
  230   variablise(X,VV,X1),
  231   variablise(N1,T,VV,T1).
  232
  233cost(+P,0,N) :- !, cost(P,0,N).
  234cost(+_P,_V,1000) :- !.
  235cost(P,V,N) :- functor(P,F,I), cost(I,F,P,V,N).
  236
  237cost(1,F,P,V,N) :-
  238   arg(1,P,X1), instantiated(X1,V,I1),
  239   nd(F,N0,N1),
  240   N is N0-I1*N1.
  241cost(2,F,P,V,N) :-
  242   arg(1,P,X1), instantiated(X1,V,I1),
  243   arg(2,P,X2), instantiated(X2,V,I2),
  244   nd(F,N0,N1,N2),
  245   N is N0-I1*N1-I2*N2.
  246cost(3,F,P,V,N) :-
  247   arg(1,P,X1), instantiated(X1,V,I1),
  248   arg(2,P,X2), instantiated(X2,V,I2),
  249   arg(3,P,X3), instantiated(X3,V,I3),
  250   nd(F,N0,N1,N2,N3),
  251   N is N0-I1*N1-I2*N2-I3*N3.
  252
  253instantiated([X|_],V,N) :- !, instantiated(X,V,N).
  254instantiated('$VAR'(N),V,0) :- setcontains(V,N), !.
  255instantiated(_,_,1).
  256
  257/*-------------------------Put in reserve--------------------
  258
  259sort_parts([],[]) :- !.
  260sort_parts([X],[X]) :- !.
  261sort_parts(L,R) :-
  262   divide(L,L1,L2),
  263   sort_parts(L1,R1),
  264   sort_parts(L2,R2),
  265   merge(R1,R2,R).
  266
  267divide([X1|L0],[X1|L1],[X2|L2]) :- list(L0,X2,L), !, divide(L,L1,L2).
  268divide(L,L,[]).
  269
  270list([X|L],X,L).
  271
  272merge([],R,R) :- !.
  273merge([X|R1],R2,[X|R]) :- precedes(X,R2), !, merge(R1,R2,R).
  274merge(R1,[X|R2],[X|R]) :- !, merge(R1,R2,R).
  275merge(R,[],R).
  276
  277precedes(G1,[G2|_]) :- goal_info(G1,_,N1), goal_info(G2,_,N2), N1 =< N2.
  278
  279-------------------------------------------------------------*/
  280
  281:-mode
  282   nonempty(+),
  283   setplus(+,+,-),
  284   setminus(+,+,-),
  285   mkset(+,+,-),
  286   setplusitem(+,+,-),
  287   setcontains(+,+),
  288   intersect(+,+),
  289   disjoint(+,+).  290
  291nonempty(0) :- !, fail.
  292nonempty(_).
  293
  294setplus(W1-V1,W2-V2,W-V) :- !, V is V1 \/ V2, setplus(W1,W2,W).
  295setplus(W-V1,V2,W-V) :- !, V is V1 \/ V2.
  296setplus(V1,W-V2,W-V) :- !, V is V1 \/ V2.
  297setplus(V1,V2,V) :- V is V1 \/ V2.
  298
  299setminus(W1-V1,W2-V2,S) :- !, V is V1 /\ \(V2),
  300   setminus(W1,W2,W), mkset(W,V,S).
  301setminus(W-V1,V2,W-V) :- !, V is V1 /\ \(V2).
  302setminus(V1,_W-V2,V) :- !, V is V1 /\ \(V2).
  303setminus(V1,V2,V) :- V is V1 /\ \(V2).
  304
  305mkset(0,V,V) :- !.
  306mkset(W,V,W-V).
  307
  308setplusitem(W-V,N,W-V1) :- N < 18, !, V1 is V \/ 1<<N.
  309setplusitem(W-V,N,W1-V) :- !, N1 is N-18, setplusitem(W,N1,W1).
  310setplusitem(V,N,V1) :- N < 18, !, V1 is V \/ 1<<N.
  311setplusitem(V,N,W-V) :- N1 is N-18, setplusitem(0,N1,W).
  312
  313setcontains(_W-V,N) :- N < 18, !, V /\ 1<<N =\= 0.
  314setcontains(W-_V,N) :- !, N1 is N-18, setcontains(W,N1).
  315setcontains(V,N) :- N < 18, V /\ 1<<N =\= 0.
  316
  317intersect(W1-V1,W2-V2) :- !, ( V1 /\ V2 =\= 0 ; intersect(W1,W2) ), !.
  318intersect(_W-V1,V2) :- !, V1 /\ V2 =\= 0.
  319intersect(V1,_W-V2) :- !, V1 /\ V2 =\= 0.
  320intersect(V1,V2) :- V1 /\ V2 =\= 0.
  321
  322disjoint(W1-V1,W2-V2) :- !, V1 /\ V2 =:= 0, disjoint(W1,W2).
  323disjoint(_W-V1,V2) :- !, V1 /\ V2 =:= 0.
  324disjoint(V1,_W-V2) :- !, V1 /\ V2 =:= 0.
  325disjoint(V1,V2) :- V1 /\ V2 =:= 0