1/*  Part of SWI-Prolog
    2
    3    Author:        Jan Wielemaker
    4    E-mail:        J.Wielemaker@vu.nl
    5    WWW:           http://www.swi-prolog.org
    6    Copyright (C): 1985-2012, University of Amsterdam
    7			      VU University Amsterdam
    8
    9    This program is free software; you can redistribute it and/or
   10    modify it under the terms of the GNU General Public License
   11    as published by the Free Software Foundation; either version 2
   12    of the License, or (at your option) any later version.
   13
   14    This program is distributed in the hope that it will be useful,
   15    but WITHOUT ANY WARRANTY; without even the implied warranty of
   16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   17    GNU General Public License for more details.
   18
   19    You should have received a copy of the GNU Lesser General Public
   20    License along with this library; if not, write to the Free Software
   21    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   22
   23    As a special exception, if you link this library with other files,
   24    compiled with a Free Software compiler, to produce an executable, this
   25    library does not by itself cause the resulting executable to be covered
   26    by the GNU General Public License. This exception does not however
   27    invalidate any other reasons why the executable file might be covered by
   28    the GNU General Public License.
   29*/
   30
   31:- module(rdf_optimise,
   32	  [ rdf_optimise/1,		% :Query
   33	    rdf_optimise/2,		% +Query, -Optimised
   34	    rdf_optimise/4,		% +Query, -Optimised, -Space, -Time
   35	    rdf_complexity/3,		% :Goal, -SpaceEstimate, -TimeEstimate
   36	    serql_select_bind_null/2	% +Goal, -WithBind
   37	  ]).   38:- use_module(library(semweb/rdf_db)).   39:- use_module(library(debug)).   40:- use_module(library(lists)).   41:- use_module(library(pairs)).   42:- use_module(library(ordsets)).   43:- use_module(library(ugraphs)).   44
   45:- meta_predicate
   46	rdf_optimise(0).   47
   48/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   49Queries  as  returned  by  serql_compile_path/2    consists  of  a  path
   50expression which is compiled to a conjunction  of calls to rdf/3 and the
   51translation of the WHERE clause acting as an additional filter.
   52
   53Optimisation of a query basically means moving conditions into the rdf/3
   54calls where possible, moving other conditions   as  early as possibly in
   55the graph-matching and reordering graph matching calls (rdf/3) to reduce
   56non-determinism.
   57
   58Reordering
   59----------
   60
   61Reordering of graph expressions  is   required  to  reduce backtracking.
   62Roughly I see three approaches:
   63
   64	* Learning
   65	Create permutations of the query and make them run under time
   66	constraints.  Try to learn patterns that work (fast).
   67
   68	* Use statistics
   69	Given the number of solutions on a certain partially instantiated
   70	rdf/3 call (and the required execution time), reorganise them to
   71	minimalise the cost.
   72
   73	* Use constraint solving
   74	Instead of trying to solve an rdf/3 call, create a constraint from
   75	it and only try to solve it if there is more information.  This
   76	is especially attractive if some form of high-level reasoning
   77	from the language entailment rules can be applied or set-theory
   78	is a possibility.
   79
   80After experiments with using constraint solving,   this  module now uses
   81planning based on statistical information provided by the rdf_db module.
   82This  algorithm  reaches  optimal  performance  under  quite  reasonable
   83assumptions  while  the  planning  overhead   is  very  reasonable.  The
   84algorithm is described in "An  optimised   Semantic  Web  query language
   85implementation        in        Prolog",          available         from
   86http://www.swi-prolog.org/download/publications/ICLP05-SeRQL.pdf
   87
   88NOTES:
   89
   90	* SeRQL LIKE works on resources *and* literals.  Do we want this?
   91	  See http://rdf4j.org/forum/mvnforum/viewthread?thread=275
   92- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
   93
   94:- multifile
   95	user:goal_expansion/2.   96
   97user:goal_expansion(rdf_complexity(G0, C), rdf_complexity(G, C)) :-
   98	expand_goal(G0, G).
   99user:goal_expansion(rdf_optimise(G0, O), rdf_optimise(G, O)) :-
  100	expand_goal(G0, G).
  101user:goal_expansion(rdf_optimise(G0, O, C, E), rdf_optimise(G, O, C, E)) :-
  102	expand_goal(G0, G).
  103
  104
  105/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  106Plan (conjunctions)
  107
  108	* Generate permutations and costs.  Select cheapest
  109	* The above moves tests right after the RDF call filling
  110	  its input argument.  As a last optimisation some of these
  111	  searches may be integrated in the rdf/3 call to help using
  112	  indexing of the RDF database.
  113
  114complexity/2 needs to update the order of clauses inside meta calls
  115(notably optional path expressions).
  116- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  117
  118%%	rdf_optimise(:Goal) is nondet.
  119%
  120%	Optimise Goal and execute the result. Semantically equivalent to
  121%	call/1.
  122%
  123%	@tbd	Module handling is not correct.
  124
  125rdf_optimise(Module:Goal) :-
  126	rdf_optimise(Goal, Optimised),
  127	call(Module:Optimised).
  128
  129
  130%%	rdf_optimise(+Goal, -Optimized) is det.
  131%
  132%	Goal is a Prolog control-structure with   calls to the rdf_db.pl
  133%	and  SeRQL  runtime  predicates.  Optimized  is  a  semantically
  134%	equivalent goal, obtained by re-ordering   conjunctions  in Goal
  135%	and  processing  sub-queries  that  do    not   share  variables
  136%	independently.
  137
  138rdf_optimise(Conj, Optimised) :-
  139	rdf_optimise(Conj, Optimised, _, _).
  140
  141rdf_optimise(Conj, Optimised, Space, Time) :-
  142	debug(rdf_optimise, '*** OPTIMIZING ***~n', []),
  143	dbg_portray_body(Conj),
  144	term_variables(Conj, Vars),
  145	rdf_complexity(Conj, Conj, S0, E0),
  146	State = state(Vars-Conj, S0, E0, 1),
  147	debug(rdf_optimise, 'C0 = ~w~n', [E0]),
  148	(   reorder(Conj, Perm),
  149	    (	debugging(rdf_optimise(all))
  150	    ->	dbg_portray_body(Perm)
  151	    ;	true
  152	    ),
  153	    rdf_complexity(Perm, Perm1, S, C),
  154	    debug(rdf_optimise(all), '--> space=~w, time=~w~n', [S, C]),
  155
  156	    arg(4, State, N),
  157	    N2 is N + 1,
  158	    nb_setarg(4, State, N2),
  159
  160	    (	arg(3, State, C0),
  161		C < C0
  162	    ->	debug(rdf_optimise,
  163		      'BETTER ONE [~D]: --> space=~w, time=~w~n', [N, S, C]),
  164		dbg_portray_body(Perm1),
  165	        nb_setarg(3, State, C),
  166		nb_setarg(2, State, S),
  167		nb_setarg(1, State, Vars-Perm1)
  168	    ;	true
  169	    ),
  170	    fail
  171	;   arg(1, State, Vars-Optimised),
  172	    arg(2, State, Space),
  173	    arg(3, State, Time),
  174	    debug(rdf_optimise, '  --> optimised: s/t = ~w/~w --> ~w/~w~n',
  175		  [S0, E0, Space, Time]),
  176	    dbg_portray_body(Optimised)
  177	), !.
  178optimise_order(Conj, Conj, -1, -1) :-
  179	debug(rdf_optimise, 'Failed to optimise:~n', []),
  180	dbg_portray_body(Conj).
  181
  182
  183		 /*******************************
  184		 *	     REORDERING		*
  185		 *******************************/
  186
  187%%	reorder(Goal, Reordered)
  188%
  189%	Assuming Goal is  a  conjunction,   create  permutations  of its
  190%	order. Instead of blindly generating   permutations  however, we
  191%	get an arbitrary element of  the   conjunction  to the front and
  192%	compute subgraphs of goals connected   through variables _after_
  193%	executing the first goal.
  194
  195reorder(Goal, Reordered) :-
  196	State = bindings([]),
  197	conj_to_list(Goal, Conj0),
  198	reorder_conj(Conj0, State, Conj1),
  199	list_to_conj(Conj1, Reordered),
  200	arg(1, State, Bindings),
  201	unbind(Bindings).
  202
  203reorder_conj([One], _, [One]) :- !.
  204reorder_conj(List, State, Perm) :-
  205	group_by_cut(List, Before, Cut, After), !,
  206	reorder_conj(Before, State, PermBefore),
  207	bind_args(Before, State),		% this part is done
  208	reorder_conj(After, State, PermAfter),
  209	append(PermBefore, [Cut|PermAfter], Perm).
  210reorder_conj(List, State, Perm) :-
  211	group_by_optional(List, Normal, Optional), !,
  212	reorder_conj(Normal, State, PermNormal),
  213	bind_args(Normal, State),		% this part is done
  214	reorder_conj(Optional, State, PermOptional),
  215	append(PermNormal, PermOptional, Perm).
  216reorder_conj(List, State, [goal(_,independent(SubPerms),_)]) :-
  217	make_subgraphs(List, SubGraphs),
  218	SubGraphs \= [_], !,
  219	reorder_subgraph_conjs(SubGraphs, State, SubPerms).
  220reorder_conj(List, State, [Prefix|Perm]) :-
  221	select(Prefix, List, Rest),
  222	bind_args(Prefix, State),
  223	make_subgraphs(Rest, SubGraphs),
  224	(   SubGraphs = [SubGraph]
  225	->  reorder_conj2(SubGraph, State, Perm)
  226	;   Perm = [goal(_,independent(SubPerms),_)],
  227	    reorder_subgraph_conjs(SubGraphs, State, SubPerms)
  228	).
  229
  230
  231%%	reorder_subgraph_conjs(SubGraphs, -ReorderedSubGraphs)
  232%
  233%	Reorder  the  individual  subgraphs.  As    we  know  these  are
  234%	independent there is no need to  order the subgraphs themselves.
  235%	we also know they are  fully   connected,  and no longer contain
  236%	cuts, so we use the simplified  version of reorder_conj/2 called
  237%	reorder_conj2/2.
  238
  239reorder_subgraph_conjs([], _, []).
  240reorder_subgraph_conjs([H0|T0], State, [H|T]) :-
  241	reorder_conj2(H0, State, H1),
  242	list_to_conj(H1, H),
  243	reorder_subgraph_conjs(T0, State, T).
  244
  245reorder_conj2([One], _, [One]) :- !.
  246reorder_conj2(List, State, [Prefix|Perm]) :-
  247	select(Prefix, List, Rest),
  248	bind_args(Prefix, State),
  249	make_subgraphs(Rest, SubGraphs),
  250	(   SubGraphs = [SubGraph]
  251	->  reorder_conj2(SubGraph, State, Perm)
  252	;   Perm = [goal(_,independent(SubPerms),_)],
  253	    reorder_subgraph_conjs(SubGraphs, State, SubPerms)
  254	).
  255
  256%%	group_by_cut(+List, -BeforeCut, -Cut, -AfterCut)
  257%
  258%	Split the conjunction over a  cut   (!)  as  we cannot guarantee
  259%	proper behaviour when moving goals to the other side of a cut.
  260
  261group_by_cut(Goals, Before, Cut, After) :-
  262	Cut = goal(_, !, _),
  263	append(Before, [Cut|After], Goals), !.
  264
  265
  266%%	group_by_optional(+List, -NotOptional, -Optional)
  267%
  268%	Split the conjunction in optional and non-optional part as we
  269%	always want the optional part to happen last.
  270
  271group_by_optional(List, Normal, Optional) :-
  272	split_optional(List, Normal, Optional),
  273	Normal \== [],
  274	Optional \== [].
  275
  276split_optional([], [], []).
  277split_optional([H|T0], Normal, Optional) :-
  278	(   optional(H)
  279	->  Optional = [H|T],
  280	    split_optional(T0, Normal, T)
  281	;   Normal = [H|T],
  282	    split_optional(T0, T, Optional)
  283	).
  284
  285optional(G) :-
  286	goal(G, (_*->_;_)).
  287
  288%%	bind_args(Goal, !State)
  289%
  290%	Bind all arguments in  Goal  or   list  of  goals.  Assumes that
  291%	executing a goal grounds all its arguments.   Only  the goal A =
  292%	literal(B), generated by optimising where constraints is handled
  293%	special.
  294%
  295%	State is a term bindings(List)  that is destructively maintained
  296%	by instantiate/4.
  297
  298bind_args([], _) :- !.
  299bind_args([H|T], State) :- !,
  300	bind_args(H, State),
  301	bind_args(T, State).
  302bind_args(H, State) :-
  303	goal(H, A=literal(B)),
  304	var(A), var(B), !,
  305	(   instantiated(A, I),
  306	    I \== (-)
  307	->  instantiate(B, _, I, State)
  308	;   instantiated(B, I),
  309	    I \== (-)
  310	->  instantiate(A, _, I, State)
  311	;   true
  312	).
  313bind_args(Goal, State) :-
  314	vars(Goal, Vars),
  315	ground_vars(Vars, State).
  316
  317ground_vars([], _).
  318ground_vars([H|T], State) :-
  319	instantiate(H, _, r, State),
  320	ground_vars(T, State).
  321
  322
  323%%	make_subgraphs(+Goals, -SubGraphs)
  324%
  325%	Create a list of connected subgraphs   from  Goals, assuming the
  326%	variables in the assoc Grounded have been bound.
  327%
  328%	@param Goals is a list goal(Id, Goal, Vars).
  329
  330make_subgraphs([Goal], [[Goal]]) :- !.
  331make_subgraphs([G1,G2], Graphs) :- !,
  332	unbound_vars(G1, V1),
  333	unbound_vars(G2, V2),
  334	(   ord_intersect(V1, V2)
  335	->  Graphs = [[G1,G2]]
  336	;   Graphs = [[G1],[G2]]
  337	).
  338make_subgraphs(Goals, SubGraphs) :-
  339	map_list_to_pairs(unbound_vars, Goals, UnBoundKeyed),
  340	connected_pairs(UnBoundKeyed, Edges),
  341	vertices_edges_to_ugraph(Goals, Edges, UGraph),
  342	connected_vertices(UGraph, SubGraphs).
  343
  344connected_pairs([], []).
  345connected_pairs([H|T], Edges) :-
  346	connected_pairs(T, H, Edges, EdgeTail),
  347	connected_pairs(T, EdgeTail).
  348
  349connected_pairs([], _, Edges, Edges).
  350connected_pairs([H|T], To, Edges, EdgeTail) :-
  351	(   connected(H, To, GH, GT)
  352	->  Edges = [GH-GT,GT-GH|Edges1],
  353	    connected_pairs(T, To, Edges1, EdgeTail)
  354	;   connected_pairs(T, To, Edges, EdgeTail)
  355	).
  356
  357connected(V1-G1, V2-G2, G1, G2) :-
  358	ord_intersect(V1, V2).
  359
  360connected_vertices([], []) :- !.
  361connected_vertices(UGraph, [Set1|Sets]) :-
  362	UGraph = [V1-_|_],
  363	reachable(V1, UGraph, Set1),
  364	del_vertices(UGraph, Set1, UGraph2),
  365	connected_vertices(UGraph2, Sets).
  366
  367
  368%%	unbound_vars(+Goal, -Vars) is det.
  369%
  370%	True when Vars is an ordered set of unbound variables in Goal.
  371
  372unbound_vars(Goal, Vars) :-
  373	vars(Goal, AllVars),
  374	unbound(AllVars, Vars0),
  375	sort(Vars0, Vars).
  376
  377unbound([], []).
  378unbound([H|T0], [H|T]) :-
  379	instantiated(H, -), !,
  380	unbound(T0, T).
  381unbound([_|T0], T) :-
  382	unbound(T0, T).
  383
  384%%	conj_to_list(+Conj, -List)
  385%
  386%	Translate a conjunction into a list of elements of the format
  387%
  388%%		goal(Id, Goal, Vars)
  389%
  390%	Where Id is a goal identifier, Goal  is the goal itself and Vars
  391%	is a list of variables inside the  Goal. Variables are sorted to
  392%	the standard order of terms.
  393
  394conj_to_list(Conj, List) :-
  395	phrase(conj_to_list(Conj, 1, _), List).
  396
  397conj_to_list((A,B), N0, N) --> !,
  398	conj_to_list(A, N0, N1),
  399	conj_to_list(B, N1, N).
  400conj_to_list(true, N, N) --> !,
  401	[].
  402conj_to_list(G, N0, N) -->
  403	{ term_variables(G, Vars0),
  404	  sort(Vars0, Vars),
  405	  N is N0 + 1
  406	},
  407	[ goal(N0, G, Vars)
  408	].
  409
  410
  411%%	list_to_conj(+List, -Conj)
  412
  413
  414list_to_conj([], true).
  415list_to_conj([goal(_,G,_)], G) :- !.
  416list_to_conj([goal(_,G,_)|T0], (G,T)) :-
  417	list_to_conj(T0, T).
  418
  419
  420%%	id(G, Id) is det.
  421%%	goal(G, Goal) is det.
  422%%	vars(G, Vars) is det.
  423%
  424%	Extract fields from the goal structure.
  425
  426%id(goal(Id, _, _),     Id).
  427goal(goal(_, Goal, _), Goal).
  428vars(goal(_, _, Vars), Vars).
  429
  430
  431		 /*******************************
  432		 *	       BINDING		*
  433		 *******************************/
  434
  435/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  436Keep track of binding status of a   variable.  There are basically three
  437ways. One is to use a seperate   (assoc) table. Alternatively we can use
  438attributed variables and delete the attributes   at the end, and finally
  439we can use normal variables and recreate  the original goal by unbinding
  440them again.
  441
  442Using assocs requires us to pass  these   things  around  and involves a
  443log(N) complexity lookup. Using real terms  has the disadvantage that to
  444unbind we have to copy the term, thus  loosing bindings it may have with
  445the environment.  Using attributes suffers neither of these problems and
  446its only drawback is relying on non-standard Prolog features.
  447
  448Note that the remainder of the  algorithm   uses  sets  organised to the
  449standard order of terms.  As  putting   attributes  does  not change the
  450identity of global stack variables and goals are global stack terms this
  451is guaranteed.
  452- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  453
  454%%	instantiate_obj(+Arg, -Old, +New, !Bindings) is det.
  455%
  456%	Called to change the state of an   RDF object after running some
  457%	goal. Old is the current instantiation.  After executing the RDF
  458%	Goal the new instantiation is New (typically =b=). Bindings is a
  459%	term  bindings(List),  which  is    updated   using  destructive
  460%	assignment. List is the list of all  variables to which we added
  461%	attributes.
  462
  463instantiate_obj(Arg, Old, New, Bindings) :-
  464	(   var(Arg)
  465	;   ground(Arg)
  466	), !,
  467	instantiate(Arg, Old, New, Bindings).
  468instantiate_obj(literal(Pattern, Var), +(Pattern), New, Bindings) :-
  469	instantiate(Var, _, New, Bindings).
  470
  471instantiate(Var, Old, New, Bindings) :-
  472	instantiated(Var, Old),
  473	(   Old == (-)
  474	->  put_attr(Var, instantiated, New),
  475	    arg(1, Bindings, B0),
  476	    setarg(1, Bindings, [Var|B0])
  477	;   true
  478	).
  479
  480instantiated(Term, How) :-
  481	(   nonvar(Term)
  482	->  How = +(+)
  483	;   get_attr(Term, instantiated, H)
  484	->  How = +(H)
  485	;   How = -
  486	).
  487
  488uninstantiate(Term, How) :-
  489	(   get_attr(Term, instantiated, How)
  490	->  del_attr(Term, instantiated)
  491	;   true
  492	).
  493
  494%%	instantiate_unify(A, B, State) is det.
  495%
  496%	We encounter a plain unification. Ideally, we determine the most
  497%	specific binding and propagate this and execute the unification.
  498%	The latter however must be undone  if we evaluate a disjunction.
  499%	For now, the code is somewhat   simplified  and we merely decide
  500%	that if one  side  is  instantiated,   the  other  will  be too,
  501%	disregarding the actual value we might know.
  502
  503instantiate_unify(A, B, State) :-
  504	instantiated(B, +(_)), !,
  505	instantiate(A, _, b, State).
  506instantiate_unify(A, B, State) :-
  507	instantiated(A, +(_)), !,
  508	instantiate(B, _, b, State).
  509instantiate_unify(_, _, _).
  510
  511
  512%%	attr_unify_hook(+Attribute, +Value)
  513%
  514%	For now, the attribute unify hook   only  allows unifying with a
  515%	variable  with  the  same  attribute.    This   deals  with  the
  516%	unification that takes place in rdf_optimise/3 for the variables
  517%	of the saved copy.
  518
  519instantiated:attr_unify_hook(Attr, Value) :-
  520	get_attr(Value, instantiated, Attr).
  521
  522instantiated:attr_portray_hook(Value, _Var) :-
  523	write(+(Value)).
  524
  525%%	instantiate_term(+Term)
  526%
  527%	Instantiate all unbound variables
  528
  529instantiate_term(Term, How) :-
  530	compound(Term), !,
  531	functor(Term, _, Arity),
  532	instantiate_args(Arity, Term, How).
  533instantiate_term(Term, How) :-
  534	(   var(Term),
  535	    \+ get_attr(Term, instantiated, _)
  536	->  put_attr(Term, instantiated, How)
  537	;   true
  538	).
  539
  540instantiate_args(0, _, _) :- !.
  541instantiate_args(N, Term, How) :-
  542	arg(N, Term, A),
  543	instantiate_term(A, How),
  544	N2 is N - 1,
  545	instantiate_args(N2, Term, How).
  546
  547
  548%%	uninstantiate_term(+Term, +How)
  549%
  550%	Remove all skolem instantiations from Term.
  551
  552uninstantiate_term(Term, How) :-
  553	compound(Term), !,
  554	functor(Term, _, Arity),
  555	uninstantiate_args(Arity, Term, How).
  556uninstantiate_term(Term, How) :-
  557	uninstantiate(Term, How).
  558
  559uninstantiate_args(0, _, _) :- !.
  560uninstantiate_args(N, Term, How) :-
  561	arg(N, Term, A),
  562	uninstantiate_term(A, How),
  563	N2 is N - 1,
  564	uninstantiate_args(N2, Term, How).
  565
  566
  567%%	delete_instantiated(+List, -Unbound)
  568%
  569%	Delete all elements of List that are not instantiated (i.e. var
  570%	and without an instantiated attribute).
  571
  572delete_instantiated([], []).
  573delete_instantiated([H|T0], L) :-
  574	(   instantiated(H, -)
  575	->  L = [H|T],
  576	    delete_instantiated(T0, T)
  577	;   delete_instantiated(T0, L)
  578	).
  579
  580
  581		 /*******************************
  582		 *	    COMPLEXITY		*
  583		 *******************************/
  584
  585%%	rdf_complexity(+GoalIn, -GoalOut, -SpaceEstimate, -TimeEstimate)
  586%
  587%	Provide an estimate  for  the  size   of  the  search  space for
  588%	executing Goal. For this we  estimate   the  branching factor of
  589%	each subgoal in the conjunction. If   the  branching factors are
  590%	B0, B1, ... then the total complexity estimate is
  591%
  592%		E = 1 + B0 + B0*B1 + B0*B1*B2, ...
  593%
  594%	Non-RDF calls are supposed  to  be   boolean  tests  that can be
  595%	executed at the first opportunity all arguments are bound by RDF
  596%	calls. They have a probability of   failure, reducing the search
  597%	space. Using the above formula, any   number  lower than 1 moves
  598%	the test as far as possible to the head of the conjunction.
  599%
  600%	If GoalIn and GoalOut are the same   the  system will not try to
  601%	optimize local conjunctions.
  602%
  603%	ISSUES: control structures ;, if-then-else, etc.
  604
  605rdf_complexity(Goal, SpaceEstimate, TimeEstimate) :-
  606	rdf_complexity(Goal, Goal, SpaceEstimate, TimeEstimate).
  607
  608rdf_complexity(Goal0, Goal, Space, Time) :-
  609	State = bindings([]),
  610	complexity(Goal0, Goal, State, 1, Space, 0, Time),
  611	arg(1, State, Bindings),
  612	unbind(Bindings).
  613
  614unbind([]).
  615unbind([H|T]) :-
  616	del_attr(H, instantiated),
  617	unbind(T).
  618
  619%	complexity(:GoalIn, -GoalOut,
  620%		   +State,
  621%		   +SpaceIn, -SpaceOut,
  622%		   +CountIn, -CountOut)
  623%
  624%	Compute the complexity of Goal.  Vars   is  an assoc holding the
  625%	variables bound earlier in the conjunction. Space keeps the size
  626%	of the search space and Count is   the  cummulative count of the
  627%	costs for exploring the search space  espressed in the number of
  628%	nodes that will be visited.
  629%
  630%	The (G*->_=true;_=false) clause deals with   the  code generated
  631%	from optional graph specs as provided by SeRQL.
  632
  633complexity((A0,B0), (A,B), State, Sz0, Sz, C0, C) :- !,
  634	complexity(A0, A, State, Sz0, Sz1, C0, C1),
  635	complexity(B0, B, State, Sz1, Sz, C1, C).
  636complexity((G0*->True;False),
  637	   ( G*->True;False), State, Sz0, Sz, C0, C) :- !,
  638	(   var(G)
  639	->  optimise_order(G0, G, Sz1, C1),
  640	    Sz is Sz0 * Sz1,
  641	    C is C0+Sz0*C1
  642	;   complexity(G, G, State, Sz0, Sz, C0, C)
  643	).
  644complexity((If0->Then0;Else0),		% dubious
  645	   ( If->Then; Else), State, Sz0, Sz, C0, C) :- !,
  646	(   var(If)
  647	->  optimise_order(If0,   If,   Sz1, C1),
  648	    optimise_order(Then0, Then, Sz2, C2),
  649	    optimise_order(Else0, Else, Sz3, C3),
  650	    Sz is max(Sz0 * Sz1 * Sz2, Sz0 * Sz3),
  651	    C  is C0 + max(Sz0*C1+Sz0*Sz1*C2, Sz0*C1+Sz0*Sz1*C3)
  652	;   complexity(If,   If,   State, Sz0, Sz1, C0, C1),
  653	    complexity(Then, Then, State, Sz1, Sz2, C1, C2),
  654	    complexity(Else, Else, State, Sz0, Sz3, C0, C3),
  655	    Sz is max(Sz2, Sz3),
  656	    C  is max(C2, C3)
  657	).
  658complexity((A0;B0), (A;B), State, Sz0, Sz, C0, C) :- !,
  659	(   var(A)
  660	->  optimise_order(A0, A, _, _),	% First try the cheap one?
  661	    optimise_order(B0, B, _, _)
  662	;   A = A0,
  663	    B = B0
  664	),
  665	complexity(A, A, State, Sz0, SzA, C0, CA),
  666	complexity(B, B, State, Sz0, SzB, C0, CB),
  667	Sz is SzA + SzB,
  668	C is CA + CB.
  669complexity(sparql_group(G0), sparql_group(G), State, Sz0, Sz, C0, C) :- !,
  670	(   var(G)
  671	->  rdf_optimise(G0, G, Sz1, C1),
  672	    Sz is Sz0 * Sz1,
  673	    C is C0+Sz0*C1
  674	;   complexity(G, G, State, Sz0, Sz, C0, C)
  675	).
  676complexity(sparql_group(G0, OV, IV),
  677	   sparql_group(G, OV, IV),
  678	   State, Sz0, Sz, C0, C) :- !,
  679	(   var(G)
  680	->  rdf_optimise(G0, G, Sz1, C1),
  681	    Sz is Sz0 * Sz1,
  682	    C is C0+Sz0*C1
  683	;   complexity(G, G, State, Sz0, Sz, C0, C)
  684	).
  685complexity(rdfql_carthesian(Bags),
  686	   rdfql_carthesian(Bags), State, Sz0, Sz, C0, C) :- !,
  687	carth_complexity(Bags, State, Sz0, Sz, C0, 0, C).
  688complexity(independent(Goals0), Goal, State, Sz0, Sz, C0, C) :- !,
  689	independent_complexity(Goals0, Goal, State, Sz0, Sz, C0, 0, C).
  690complexity(Goal, Goal, State, Sz0, Sz, C0, C) :-
  691	Goal = member(Var, List), !,	% List is list of resources
  692	instantiate(Var, _, b, State),
  693	length(List, Branch),
  694	Sz is Sz0 * Branch,
  695	C is C0 + Sz0*0.2 + Sz*0.2.
  696complexity(Goal, Goal, State, Sz, Sz, C0, C) :-
  697	Goal = (A=B), !,
  698	instantiate_unify(A, B, State),
  699	C is C0 + 0.2.
  700complexity(Goal, Goal, State, Sz, Sz, C0, C) :-
  701	Goal = (Var=literal(V)), !,
  702	instantiated(V, +(_)),
  703	instantiate(Var, _, b, State),
  704	C is C0 + 0.2.
  705complexity(Goal, Goal, State, Sz0, Sz, C0, C) :-
  706	rdf_db_goal(Goal, S, P, O), !,
  707	instantiate(S, SI, b, State),
  708	instantiate(P, PI, b, State),
  709	instantiate_obj(O, OI, b, State),
  710	complexity0(SI, PI, OI, P, Goal, SetUp, PerAlt, Branch),
  711	Sz is Sz0 * Branch,
  712	C is C0 + Sz0*SetUp + Sz*PerAlt,
  713	debug(rdf_optimise(complexity), 'Complexity ~p: (~w) ~w --> ~w',
  714	      [i(SI,PI,OI), Goal, Branch, C]).
  715complexity(sparql_eval(E,V), sparql_eval(E,V), _, Sz0, Sz, C0, C) :- !,
  716	term_variables(E, Vars),
  717	all_bound(Vars),
  718	Sz is Sz0,			% probability of failure
  719	C is C0 + Sz*20.		% Sz * CostOfEval
  720complexity(sparql_true(E), sparql_true(E), _, Sz0, Sz, C0, C) :- !,
  721	term_variables(E, Vars),
  722	all_bound(Vars),
  723	Sz is Sz0 * 0.5,		% probability of failure
  724	C is C0 + Sz0*20.		% Sz * CostOfEval
  725complexity(G, G, _, Sz0, Sz, C0, C) :-	% non-rdf tests
  726	term_variables(G, Vars),
  727	all_bound(Vars),
  728	Sz is Sz0 * 0.5,		% probability of failure
  729	C is C0 + Sz0.			% Sz * CostOfTest
  730
  731all_bound([]).
  732all_bound([H|T]) :-
  733	instantiated(H, +(_)),
  734	all_bound(T).
  735
  736%%	carth_complexity(+Bags, +State,
  737%%			 +Size0, -Size,
  738%%			 +Time0, +TimeSum0, -TimeSum) is det.
  739%
  740%	Compute the time and space efficiency of the carthesian product.
  741%	the total cost in time is the sum  of the costs of all branches,
  742%	The search space at the end is still the same product.
  743
  744carth_complexity([], _, Sz, Sz, _, C, C).
  745carth_complexity([bag(_,G)|T], State,
  746		 Sz0, Sz,
  747		 C0, Csum0, Csumz) :-
  748	complexity(G, G, State, Sz0, Sz1, C0, C1),
  749	Csum1 is Csum0 + C1,
  750	carth_complexity(T, State, Sz1, Sz, C0, Csum1, Csumz).
  751
  752
  753%%	independent_complexity(+GoalsIn, -Goals, +State,
  754%%			       +Size0, -Size,
  755%%			       +Time0, +TimeSum0, -TimeSum) is det.
  756%
  757%	Compute the complexity of an independent conjunction.
  758%
  759%	@param Goals is a list of g(Goal, Branch, Cost), where Branch is
  760%	the number of solutions expected fromGoal and Cost is the
  761%	estimated CPU time.
  762
  763independent_complexity(GoalsIn, Goal, State,
  764		       Size0, Size,
  765		       Time0, TimeSum0, TimeSum) :-
  766	indep_complexity(GoalsIn, Goals1, State,
  767			 Size0, Size,
  768			 Time0, TimeSum0, TimeSum),
  769	keysort(Goals1, ByCost),
  770	pairs_values(ByCost, Goals2),
  771	simplify_carthesian(Goals2, Goal).
  772
  773indep_complexity([], [], _, Sz, Sz, _, C, C).
  774indep_complexity([G0|GT0], [SzG-bag(Vars,G,SzG,CG)|GT], State,
  775		       Sz0, Sz,
  776		       C0, Csum0, Csumz) :-
  777	complexity(G0, G, State, Sz0, Sz1, C0, C1),
  778	term_variables(G, VList),
  779	Vars =.. [v|VList],
  780	(   Sz0 =:= 0
  781	->  SzG = 0,
  782	    CG = 0
  783	;   SzG is Sz1/Sz0,
  784	    CG is (C1-C0)/Sz0
  785	),
  786	Csum1 is Csum0 + C1,
  787	indep_complexity(GT0, GT, State, Sz1, Sz, C0, Csum1, Csumz).
  788
  789%%	simplify_carthesian(+Bags, -Goal) is det.
  790%
  791%	Peer of the leading little branching   goals from the carthesian
  792%	handler. If there is a bag of one   left,  turn it into a normal
  793%	goal.
  794
  795simplify_carthesian([], true).
  796simplify_carthesian([bag(_,Goal,_Branch,_Cost)], Goal) :- !.
  797simplify_carthesian([bag(_,Goal,Branch,_Cost)|Bags], Final) :-
  798	(   Branch < 1.5
  799	->  !, Final = (Goal, Final1),
  800	    simplify_carthesian(Bags, Final1)
  801	;   Bags == []
  802	->  !, Final = Goal
  803	).
  804simplify_carthesian(Bags, rdfql_carthesian(Bags)).
  805
  806
  807%%	complexity0(+SI, +PI, +OI, +P, +G, -Setup, -PerAlt, -Branch).
  808%
  809%	SI,PI,OI describe the instantiation pattern.  P is the predicate
  810%	and G is the actual goal. Complexity   is unified to an estimate
  811%	of the size of the search space and therefore an estimate of the
  812%	execution time required to prove the goal.
  813%
  814%	Literal `like' matches come  out   as  +(like(Pattern)). We must
  815%	estimate the percentage of the literals that match this pattern.
  816%	Suppose the factor is 1,000. This means the branching is reduced
  817%	by 1,000, but finding each solution  is   slow  as it requires a
  818%	linear scan. It is faster than going  all the way back to Prolog
  819%	backtracking however, so we estimate a   factor  10 (TBD: verify
  820%	that number).
  821%
  822%	ISSUES: rdf_has/3 vs rdf_reachable/3.
  823
  824complexity0(+(_),+(_),+(_), _, _, 1, 0, 1) :- !.
  825complexity0(+(b),+(+),-, P, G, 1, 1, B) :- !,
  826	subj_branch_factor(G, B, Prop),
  827	rdf_predicate_property(P, Prop).
  828complexity0(-,+(+),+(b), P, G, 1, 1, B) :- !,
  829	obj_branch_factor(G, B, Prop),
  830	rdf_predicate_property(P, Prop).
  831complexity0(+(b), -, -, _, _, 1, 1, B) :- !,
  832	rdf_statistics(triples(Total)),
  833	subject_count(Subjs),
  834	(   Total == 0
  835	->  B = 0
  836	;   B is Total/Subjs
  837	).
  838complexity0(_,_,+(like(Pat)),_, G, Factor, Factor, B) :- !,
  839	rdf_estimate_complexity(G, B0),
  840	pattern_filter(Pat, Factor0),
  841	Factor is max(1, min(B0, Factor0)/10),
  842	B is B0/Factor.
  843complexity0(_,_,_, _, G, 1, 1, B) :-
  844	rdf_estimate_complexity(G, B).
  845
  846:- if(rdf_statistics(subjects(_))).  847subject_count(Count) :-				% RDF-DB 2.x
  848	rdf_statistics(subjects(Count)).
  849:- else.  850subject_count(Count) :-				% RDF-DB 3.x
  851	rdf_statistics(resources(Count)).
  852:- endif.  853
  854:- multifile
  855        subj_branch_factor/3,
  856        obj_branch_factor/3.  857
  858subj_branch_factor(rdf(_,_,_),           X, rdf_subject_branch_factor(X)).
  859subj_branch_factor(rdf_has(_,_,_),       X, rdfs_subject_branch_factor(X)).
  860subj_branch_factor(rdf_reachable(_,_,_), X, rdfs_subject_branch_factor(X)).
  861
  862obj_branch_factor(rdf(_,_,_),            X, rdf_object_branch_factor(X)).
  863obj_branch_factor(rdf_has(_,_,_),        X, rdfs_object_branch_factor(X)).
  864obj_branch_factor(rdf_reachable(_,_,_),  X, rdfs_object_branch_factor(X)).
  865
  866
  867%%	rdf_db_goal(+Goal, -Subject, -Predicate, -Object)
  868%
  869%	True if Goal is a pure (logical)   predicate on the RDF database
  870%	involving the given  Subject,  Predicate   and  Object.  Defined
  871%	multifile, allowing the  optimiser   to  understand user-defined
  872%	rdf/3 like predicates.
  873%
  874%	@tbd	Allow specifying different costs and branching factors
  875
  876:- multifile
  877	rdf_db_goal/4.  878
  879rdf_db_goal(rdf(S,P,O),			S,P,O).
  880rdf_db_goal(rdf_has(S,P,O),		S,P,O).
  881rdf_db_goal(rdf_reachable(S,P,O),	S,P,O).
  882rdf_db_goal(rdf(S,P,O, _DB),		S,P,O). % TBD: less hits
  883
  884%%	pattern_filter(+Like, -Factor)
  885%
  886%	Estimate the efficiency of a pattern. This is a bit hard, as
  887%	characters are not independent.
  888
  889pattern_filter(Like, Factor) :-
  890	atom_codes(Like, Codes),
  891	pattern_factor(Codes, 1, Factor).
  892
  893pattern_factor([], F, F).
  894pattern_factor([0'*|T], F0, F) :- !,
  895	pattern_factor(T, F0, F).
  896pattern_factor([_|T], F0, F) :-
  897	F1 is F0*10,
  898	pattern_factor(T, F1, F).
  899
  900
  901%%	rdf_estimate_complexity(+Goal, -Complexity)
  902%
  903%	Estimate the branching factor introduced by  Goal. This uses the
  904%	rdf_db  statistics  of  the  hash  chains  which  are  based  on
  905%	exploiting the RDFS subPropertyOf reasoning.
  906%
  907%	In addition, rdf_reachable/3 introduces its own complexity which
  908%	must be estimate using the branching factor of the relation.
  909
  910rdf_estimate_complexity(G, C) :-
  911	rdf_db_goal(G, S, P0, O),
  912	map_predicate(P0, P),
  913	rdf_estimate_complexity(S, P, O, C).
  914
  915map(map_predicate(_,_)).
  916map(map_predicate(_,_):-_).
  917
  918term_expansion(In, Out) :-
  919	map(In), !,
  920	rdf_global_term(In, Out).
  921
  922map_predicate(X, X) :-
  923	var(X), !.
  924map_predicate(serql:directSubClassOf,    rdfs:subClassOf) :- !.
  925map_predicate(serql:directType,          rdf:type) :- !.
  926map_predicate(serql:directSubPropertyOf, rdfs:subPropertyOf) :- !.
  927map_predicate(X, X).
  928
  929
  930		 /*******************************
  931		 *     INSTANTIATE OPTIONAL	*
  932		 *******************************/
  933
  934/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  935In  SELECT  queries,  optional  parts  of   the  path  expression  leave
  936uninstantiated variables. These must be bound to  '$null$' to be able to
  937do correct merging for  DISTINCT.  The  naive   way  to  do  this  is to
  938instantiate all variables at the end  of   the  query.  On large selects
  939(i.e. involving many variables) this appears to be quite costly.  Doing
  940the job early, as in
  941
  942	(   Goal
  943	*-> true
  944	;   bind_null(VarsInGoal)
  945	)
  946
  947is not correct as well, as VarsInGoal may  be involved in other parts of
  948the code either before or after the optional path expression. So we need
  949to:
  950
  951	* Do abtract execution and find the bindings done before arriving
  952	  at Goal.
  953	* continue the execution, and watch for new bindings to these
  954	  variables.  If we find a binding for the second time, remove
  955	  it from the first and make a conditional binding for it.
  956
  957If we bind an argument unconditionally, we place an attribute 'b'. If it
  958is conditionally bound, we place an attribute   c(Set), where Set is the
  959set in which it was bound or plain  'c' if it was conditionally bound in
  960multiple places.
  961
  962TBD:	disjunctions and other control structures.
  963	queries that do not bind (such as SPARQL bound(X))
  964- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  965
  966serql_select_bind_null(Goal0, Goal) :-
  967	State = bindings([]),
  968	select_bind_null(Goal0, Goal1, State),
  969	arg(1, State, Bindings),
  970	c_unbind(Bindings, Left),
  971	(   Left == []
  972	->  Goal = Goal1
  973	;   Goal = (Goal1, rdfql_cond_bind_null(Left))
  974	).
  975
  976c_unbind([], []).
  977c_unbind([H|T0], L) :-
  978	(   get_attr(H, instantiated, c)
  979	->  L = [H|T]
  980	;   L = T
  981	),
  982	del_attr(H, instantiated),
  983	c_unbind(T0, T).
  984
  985
  986select_bind_null((A0,B0), (A,B), State) :- !,
  987	select_bind_null(A0, A, State),
  988	select_bind_null(B0, B, State).
  989select_bind_null((G0 *-> true; true),
  990		 ( G *-> true; Bind),
  991		 State) :- !,
  992	arg(1, State, B0),
  993	select_bind_null(G0, G, State),
  994	arg(1, State, B),
  995	Bind = rdfql_bind_null(Vars),
  996	c_bindings(B, B0, c(Bind), Vars).
  997select_bind_null(rdfql_carthesian(List0),
  998		 rdfql_carthesian(List), State) :- !,
  999	select_carth_bind_null(List0, List, State).
 1000select_bind_null(sparql_group(A0), sparql_group(A), State) :- !,
 1001	select_bind_null(A0, A, State).
 1002select_bind_null(sparql_group(A0,Outer,Inner),
 1003		 sparql_group(A, Outer,Inner),
 1004		 State) :- !,
 1005	select_bind_null(A0, A, State),
 1006	term_variables(Outer, Vars),
 1007	c_bind(Vars, State).
 1008select_bind_null(Goal, Goal, State) :-
 1009	term_variables(Goal, Vars),
 1010	c_bind(Vars, State).
 1011
 1012%%	c_bindings(+AtEnd, +AtStart, +CVars, -Vars)
 1013%
 1014%	The  variables  of  the    difference-list   AtEnd..AtStart  are
 1015%	conditionally bound. Tag each such  variable with CVars.
 1016%
 1017%	@param CVars	Term c(Vars), where Vars are the other variables
 1018%			that have the same conditional binding.
 1019
 1020c_bindings(B, B0, _, Vars)  :-
 1021	B == B0, !,
 1022	Vars = [].
 1023c_bindings([H|T0], B0, Attr, [H|Vars]) :-
 1024	get_attr(H, instantiated, I),
 1025	is_instantiated(I), !,
 1026	put_attr(H, instantiated, Attr),
 1027	c_bindings(T0, B0, Attr, Vars).
 1028c_bindings([_|T0], B0, Attr, Vars) :-
 1029	c_bindings(T0, B0, Attr, Vars).
 1030
 1031
 1032is_instantiated(b).		% unconditionally bound
 1033is_instantiated(c(_)).		% bound either by call or rdfql_bind_null/1
 1034
 1035
 1036%%	c_bind(+Vars, +State)
 1037%
 1038%	Do  unconditional  binding  of   Vars.   Var    may   be   in  a
 1039%	rdfql_bind_null/1 set. In that case, delete it from the set, and
 1040%	set the class to 'c' to make a conditional binding at the end.
 1041
 1042c_bind([], _).
 1043c_bind([H|T], State) :-
 1044	(   get_attr(H, instantiated, I)
 1045	->  (   I == b			% already unconditionally bound
 1046	    ->	true
 1047	    ;	I = c(Set)
 1048	    ->	arg(1, Set, Vars0),
 1049		del_var(H, Vars0, Vars),
 1050		setarg(1, Set, Vars),
 1051		put_attr(H, instantiated, c)
 1052	    ;	I == c
 1053	    ->	true
 1054	    )
 1055	;   put_attr(H, instantiated, b),
 1056	    arg(1, State, B0),
 1057	    setarg(1, State, [H|B0])
 1058	),
 1059	c_bind(T, State).
 1060
 1061del_var(H, [X|T0], T) :-
 1062	(   H == X
 1063	->  T = T0
 1064	;   T = [X|T1],
 1065	    del_var(H, T0, T1)
 1066	).
 1067
 1068select_carth_bind_null([], [], _).
 1069select_carth_bind_null([bag(Vars, G0)|T0], [bag(Vars, G)|T], State) :-
 1070	select_bind_null(G0, G, State),
 1071	select_carth_bind_null(T0, T, State).
 1072
 1073
 1074		 /*******************************
 1075		 *	  DEBUG SUPPORT		*
 1076		 *******************************/
 1077
 1078dbg_portray_body(G) :-
 1079	debugging(rdf_optimise), !,
 1080	portray_body(G).
 1081dbg_portray_body(_).
 1082
 1083portray_body(G) :-
 1084	(   pp_instantiate_term(G),
 1085	    debug(_, '~@',
 1086		  [ portray_clause(current_output, (<> :- G), [module(sparql_runtime)])
 1087		  ]),
 1088	    fail
 1089	;   true
 1090	).
 1091
 1092pp_instantiate_term(Term) :-
 1093	compound(Term), !,
 1094	functor(Term, _, Arity),
 1095	pp_instantiate_args(Arity, Term).
 1096pp_instantiate_term(Term) :-
 1097	var(Term),
 1098	get_attr(Term, instantiated, H), !,
 1099	del_attr(Term, instantiated),
 1100	Term = +(H).
 1101pp_instantiate_term(_).
 1102
 1103pp_instantiate_args(0, _) :- !.
 1104pp_instantiate_args(N, Term) :-
 1105	arg(N, Term, A),
 1106	pp_instantiate_term(A),
 1107	N2 is N - 1,
 1108	pp_instantiate_args(N2, Term).
 1109
 1110
 1111		 /*******************************
 1112		 *	      SANDBOX		*
 1113		 *******************************/
 1114
 1115:- multifile sandbox:safe_meta_predicate/1. 1116
 1117sandbox:safe_meta_predicate(rdf_optimise:rdf_optimise/1)