2
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], 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), 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], 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).
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
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