🚀 go-pugleaf

Hi there in netland,

I have now finished the first release of my Prolog to SQL compiler. It
translates database access requests, which consist of a projection term
and a database goal to the appropriate SQL query. This compiler may
be useful in Prolog-to-RDBMS interfaces, which often allow SQL queries
as string arguments (e.g. the Quintus Prolog Oracle interface and others).

The compiler is written in standard Edinburgh Prolog. It has been ported
to a number of Prologs both on the Mac and on UNIX machines - the code
given here works for ECRC's SEPIA Prolog. Other Prologs require a little
modification in the gensym/2 predicates (Quintus Prolog has them in the
library strings, LPA MacProlog has them as built-ins, other Prologs do
not have global variables and thus require assert/1 and retract/1 for
the implementation of gensym/2) - but this is the only place where the
code had to be adapted.

Some specific details on the compiler:

 - it is very powerful in that it allows negation, arithmetics,
   and aggregate functions
 - it is fast (approx. 6 ms in Quintus Prolog on a Sparc)
 - and the code is very clean (no tricks, no secrets...)

Furthermore, a report on the implementation is available (with loads of
benchmarks, motivation, and references to further reading). To receive a 
copy of the report, mail to the following address:

   draxler@sun1.cis.uni-muenchen.de

and give your full postal address. 

Note that there is a copyright on the compiler - however, it may be used
and distributed free of charge for non-commercial purposes and provided 
that the copyright notice is not changed.

How to use the compiler? 

Five sample queries are included in the code, so you consult the file,
and run the goal:

 ?- benchmark(1,N,D).

This evaluation returns the execution time D for one run (first arg) of
query number N. Backtracking will bind N to 2,3,4, and 5 and return the
corresponding runtimes.

A second way to run the compiler is to call it with the goal translate/3:
e.g.

   ?- translate(plane(Type,Seats),plane(Type,Seats),SQLQuery).

translates to an SQL query which retrieves all planes from a given 
relation PLANE. Note that only the two relations flight/4 and plane/2
are defined - roll your own by simply adding them to the meta-database
section in the code (or keep it in a separate file).

I would very much appreciate comments, suggestions for improvements,
and criticism - feel free to mail me. See the introductory remarks in the
commented code for details...

So, have fun (let me know how you did)...

Christoph Draxler

draxler@sun1.cis.uni-muenchen.de


-----------------------------------------------------------------------------

CIS Centre for Information and Language Processing
Ludwig-Maximilians-University Munich
Leopoldstr. 139
D 8000 Munich 40

Tel: +49 / +89 / 36 40 72
Fax: +48 / +89 / 361 61 99


--- CODE BEGINS HERE --------------------------------------------------------

 
% --------------------------------------------------------------------------------------
%
% This Prolog to SQL compiler may be distributed free of charge provided that it is
% not used in commercial applications without written consent of the author, and
% that the copyright notice remains unchanged.
%
%                    (C) Copyright by Christoph Draxler, Munich
%                        Version 1.0 Sept. 3 1992
%
% I would like to keep in my hands the further development and distribution of the
% compiler. This does not mean that I don't want other people to suggest or even
% implement improvements - quite on the contrary: I greatly appreciate contributions 
% and if they make sense to me I will incorporate them into the compiler (with due
% credits given!). 
% 
% For further development of the compiler, address your requests, comments and
% criticism to the author:
%
%                    Christoph Draxler
%                    CIS Centre for Information and Language Processing
%                    Ludwig-Maximilians-University Munich
%                    Leopoldstr. 139
%                    D 8000 Munich 40
%                    Tel : ++49 / +89 / 36 40 72
%                    Fax : ++49 / +89 / 361 61 99
%                    Mail: draxler@sun1.cis.uni-muenchen.de
%
%
%
% RELEASE INFORMATION
% ===================
% Current version is v. 1.0 of Sept. 15th 1992.
%
% --------------------------------------------------------------------------------------





% --- Meta Database for schema definition of SQL DB in Prolog --------------------------
%
% maps Prolog predicates to SQL table names, Prolog predicate argument positions to SQL
% attributes, and Prolog operators to SQL operators. 
%
% ATTENTION! It is assumed that the arithmetic operators in Prolog and SQL are the same,
% i.e. + is addition in Prolog and in SQL, etc. If this is not the case, then a mapping
% function for arithmetic operators is necessary too.
% --------------------------------------------------------------------------------------


% --- relation(PrologFunctor,Arity,SQLTableName) ---------------------------------------

relation(flight,4,'FLIGHT').
relation(plane,2,'PLANE').


% --- attribute(PrologArgumentPosition,SQLTableName,SQLAttributeName) ------------------

attribute(1,'FLIGHT','FLIGHT_NO').
attribute(2,'FLIGHT','DEPARTURE').
attribute(3,'FLIGHT','DESTINATION').
attribute(4,'FLIGHT','PLANE_TYPE').


attribute(1,'PLANE','TYPE').
attribute(2,'PLANE','SEATS').


% --- Mapping of Prolog operators to SQL operators -------------------------------------

comparison(=,=).
comparison(<,<).
comparison(>,>).
comparison(@<,<).
comparison(@>,>).


negated_comparison(=,'<>').
negated_comparison(\=,=).
negated_comparison(>,=<).
negated_comparison(=<,>).
negated_comparison(<,>=).
negated_comparison(>=,<).


% --- aggregate_function(PrologFunctor,SQLFunction) -----------------

aggregate_functor(avg,'AVG').
aggregate_functor(min,'MIN').
aggregate_functor(max,'MAX').
aggregate_functor(sum,'SUM').
aggregate_functor(count,'COUNT').




% --------------------------------------------------------------------------------------
%
% Top level predicate translate/3 organizes and the compilation and prints the output
% to the screen.
%
% --------------------------------------------------------------------------------------


translate(ProjectionTerm,DatabaseGoal,SQLQueryTerm):-
   % --- initialize variable identifiers and range variables for relations -----
   init_gensym(var),
   init_gensym(rel),

   % --- tokenize projection term and database goal ----------------------------
   tokenize_term(DatabaseGoal,TokenDatabaseGoal),
   tokenize_term(ProjectionTerm,TokenProjectionTerm),

   % --- lexical analysis: reordering of goals for disjunctive normalized form -
   disjunction(TokenDatabaseGoal,Disjunction),

   % --- code generation ---------------------------------------------------------------
   query_generation(Disjunction,TokenProjectionTerm,SQLQueryTerm),

   % --- output ------------------------------------------------------------------------
   printqueries(SQLQueryTerm).





% --- disjunction(Goal,Disjunction) ----------------------------------------------------
%
% turns original goal into disjunctive normalized form by computing all conjunctions
% and collecting them in a list
%
% --------------------------------------------------------------------------------------

disjunction(Goal,Disjunction):-
   findall(Conjunction,linearize(Goal,Conjunction),Disjunction).




% --- linearize(Goal,ConjunctionList) --------------------------------------------------
%
% Returns a conjunction of base goals for a complex disjunctive or conjunctive goal
% Yields several solutions upon backtracking for disjunctive goals
%
% --------------------------------------------------------------------------------------

linearize(((A,B),C),(LinA,(LinB,LinC))):-
   % --- transform left-linear to right-linear conjunction (',' is associative) ----
   linearize(A,LinA),
   linearize(B,LinB),
   linearize(C,LinC).

linearize((A,B),(LinA,LinB)):-
   not (A = (_,_)),
   % --- make sure A is not a conjunction ------------------------------------------
   linearize(A,LinA),
   linearize(B,LinB).

linearize((A;B),LinA):-
   linearize(A,LinA).

linearize((A;B),LinB):-
   linearize(B,LinB).

linearize(not A, not LinA):-
   linearize(A,LinA).

linearize(Var^A, Var^LinA):-
   linearize(A,LinA).

linearize(A,A):-
   not (A = (_,_)),
   not (A = (_;_)),
   not (A = _^_),
   not (A = not(_)).




% --- tokenize_term(Term,TokenizedTerm) -------------------------------------------------
%
% If Term is a 
%
%  - variable, then this variable is instantiated with a unique identifier 
%    of the form var(VarId), and TokenizedTerm is bound to the same term var(VarId). 
%
%  - constant, then TokenizedTerm is bound to const(Term).
%
%  - complex term, then the term is decomposed, its arguments are tokenized,
%    and TokenizedTerm is bound to the result of the composition of the original
%    functor and the tokenized arguments.
%
% --------------------------------------------------------------------------------------

tokenize_term(var(VarId),var(VarId)):-
   var(VarId),
   % --- uninstantiated variable: instantiate it with unique identifier.
   gensym(var,VarId).

tokenize_term(var(VarId),var(VarId)):-
   nonvar(VarId).

tokenize_term(Constant,const(Constant)):-
   nonvar(Constant),
   functor(Constant,_,0).

tokenize_term(Term,TokenizedTerm):-
   nonvar(Term),
   not (Term = var(_)),
   not (Term = const(_)),
   Term =.. [Functor|Arguments],
   not (Arguments = []),
   tokenize_arguments(Arguments,TokenArguments),
   TokenizedTerm =.. [Functor|TokenArguments].



% --- tokenize_arguments(Arguments,TokenizedArguments) ---------------------------------
%
% organizes tokenization of arguments by traversing list and calling tokenize_term
% for each element of the list.
%
% --------------------------------------------------------------------------------------

tokenize_arguments([],[]).

tokenize_arguments([FirstArg|RestArgs],[TokFirstArg|TokRestArgs]):-
   tokenize_term(FirstArg,TokFirstArg),
   tokenize_arguments(RestArgs,TokRestArgs).







% --- query_generation(ListOfConjunctions, ProjectionTerm, ListOfQueries) -------------- 
%
% For each Conjunction translate the pair (ProjectionTerm,Conjunction) to an SQL query
% and connect each such query through a UNION-operator to result in the ListOfQueries.
%
% A Conjunction consists of positive or negative subgoals. Each subgoal is translated 
% as follows:
%  - the functor of a goal that is not a comparison operation is translated to
%    a relation name with a range variable
%  - negated goals are translated to NOT EXISTS-subqueries with * projection
%  - comparison operations are translated to comparison operations in the WHERE-clause
%  - aggregate function terms are translated to aggregate function (sub)queries
% 
% The arguments of a goal are translated as follows:
%  - variables of a goal are translated to qualified attributes
%  - variables occurring in several goals are translated to equality comparisons
%    (equi join) in the WHERE-clause
%  - constant arguments are translated to equality comparisons in the WHERE-clause
% 
% Special treatment of arithmetic functions:
%  - arithmetic functions are identified through the Prolog is/2 operator
%  - an arithmetic function may contain an unbound variable only on its left side
%  - the right side of the is/2 operator may consist of 
%    * bound variables (bound through occurrence within a positive database goal, or 
%      bound through preceeding arithmetic function), or of 
%    * constants (numbers, i.e. integers, reals)
% 
% The following RESTRICTION holds:
%
%  - the binding of variables follows Prolog: variables are bound by positive base goals
%    and on the left side of the is/2 predicate - comparison operations, negated goals
%    and right sides of the is/2 predicate do not return variable bindings and may even 
%    require all arguments to be bound for a safe evaluation.
%
% --------------------------------------------------------------------------------------

query_generation([],_,[]).

query_generation([Conjunction|Conjunctions],ProjectionTerm,[Query|Queries]):-
   projection_term_variables(ProjectionTerm,InitDict),
   translate_conjunction(Conjunction,SQLFrom,SQLWhere,InitDict,Dict),
   translate_projection(ProjectionTerm,Dict,SQLSelect),
   Query = query(SQLSelect,SQLFrom,SQLWhere),
   query_generation(Conjunctions,ProjectionTerm,Queries).



% --- translate_goal(Goal,SQLFrom,SQLWhere,Dict,NewDict) -------------------------------
%
% translates a
%
%   - positive database goal to the associated FROM- and WHERE clause of an SQL query
%   - a negated goal to a negated existential subquery
%   - an arithmetic goal to an arithmetic expression or an aggregate function query
%   - a comparison goal to a comparison expression
%   - a negated comparison goal to a comparison expression with the opposite comparison
%     operator
%
% --------------------------------------------------------------------------------------

translate_goal(SimpleGoal,[SQLFrom],SQLWhere,Dict,NewDict):-
   % --- positive goal binds variables - these bindings are held in the dictionary -----
   functor(SimpleGoal,Functor,Arity),
   translate_functor(Functor,Arity,SQLFrom),
   SimpleGoal =.. [Functor|Arguments],
   translate_arguments(Arguments,SQLFrom,1,SQLWhere,Dict,NewDict).

translate_goal(Result is Expression,[],SQLWhere,Dict,NewDict):-
   translate_arithmetic_function(Result,Expression,SQLWhere,Dict,NewDict).

translate_goal(not NegatedGoals,[],SQLNegatedSubquery,Dict,Dict):-
   % --- negated goals do not bind variables - hence Dict is returned unchanged --------
   functor(NegatedGoals,Functor,_),
   not comparison(Functor,_),
   translate_conjunction(NegatedGoals,SQLFrom,SQLWhere,Dict,_),
   SQLNegatedSubquery = [negated_existential_subquery([*],SQLFrom,SQLWhere)].

translate_goal(not ComparisonGoal,[],SQLCompOp,Dict,Dict):-
   % --- comparison operations do not bind variables - Dict is returned unchanged ------
   ComparisonGoal =.. [ComparisonOperator,LeftArg,RightArg],
   comparison(ComparisonOperator,SQLOperator),
   negated_comparison(SQLOperator,SQLNegOperator),
   translate_comparison(LeftArg,RightArg,SQLNegOperator,Dict,SQLCompOp).

translate_goal(ComparisonGoal,[],SQLCompOp,Dict,Dict):-
   % --- comparison operations do not bind variables - Dict is returned unchanged ------
   ComparisonGoal =.. [ComparisonOperator,LeftArg,RightArg],
   comparison(ComparisonOperator,SQLOperator),
   translate_comparison(LeftArg,RightArg,SQLOperator,Dict,SQLCompOp).




% --- translate_conjunction(Conjunction,SQLFrom,SQLWhere,Dict,NewDict) -----------------
% 
% translates a conjunction of goals (represented as a list of goals preceeded by 
% existentially quantified variables) to FROM- and WHERE-clause of an SQL query.  
% A dictionary containing the associated SQL table and attribute names is built up
% as an accumulator pair (arguments Dict and NewDict)
%
% --------------------------------------------------------------------------------------

translate_conjunction(var(VarId)^Goal,SQLFrom,SQLWhere,Dict,NewDict):-
   % --- add info on existentially quantified variables to dictionary here -------------
   add_to_dictionary(VarId,_,_,existential,Dict,TmpDict),
   translate_conjunction(Goal,SQLFrom,SQLWhere,TmpDict,NewDict).

translate_conjunction(Goal,SQLFrom,SQLWhere,Dict,NewDict):-
   not (Goal = (_,_)),
   translate_goal(Goal,SQLFrom,SQLWhere,Dict,NewDict).

translate_conjunction((Goal,Conjunction),SQLFrom,SQLWhere,Dict,NewDict):-
   translate_goal(Goal,FromBegin,WhereBegin,Dict,TmpDict),
   translate_conjunction(Conjunction,FromRest,WhereRest,TmpDict,NewDict),
   append(FromBegin,FromRest,SQLFrom),
   append(WhereBegin,WhereRest,SQLWhere).




% --- translate_arithmetic_function(Result,Expression,SQLWhere,Dict,NewDict) -----------
%
% Arithmetic functions (left side of is/2 operator is bound to value of expression on
% right side) may be called with either
%
% - Result unbound: then Result is bound to the value of the evaluation of Expression
% - Result bound: then an equality condition is returned between the value of Result
%   and the value of the evaluation of Expression.
%
% Only the equality test shows up in the WHERE clause of an SQLquery.
%
% --------------------------------------------------------------------------------------

translate_arithmetic_function(var(VarId),Expression,[],Dict,NewDict):-
   % assigment of value of arithmetic expression to variable - does not
   % show up in WHERE-part, but expression corresponding to
   % variable must be stored in Dict for projection translation

   evaluable_expression(Expression,Dict,ArithExpression),
   add_to_dictionary(VarId,is,ArithExpression,all,Dict,NewDict).


translate_arithmetic_function(var(VarId),Expression,ArithComparison,Dict,Dict):-
   % --- test whether left side evaluates to right side: return equality comparison ----
   % Left side consists of qualified attribute, i.e. range variable must not be
   % arithmetic operator is/2 
   lookup(VarId,Dict,PrevRangeVar,PrevAtt),
   not (PrevRangeVar = is),
   evaluable_expression(Expression,Dict,ArithExpression),
   ArithComparison = [comp(att(PrevRangeVar,PrevAtt),'=',ArithExpression)].

translate_arithmetic_function(var(VarId),Expression,ArithComparison,Dict,Dict):-
   % --- test whether left side evaluates to right side: return equality comparison ----
   % Left side consists of arithmetic expression, i.e. VarId is stored in Dict as 
   % belonging to arithmetic expression which is expressed as RangeVar-argument 
   % of lookup returning is/2 

   lookup(VarId,Dict,is,LeftExpr),
   evaluable_expression(Expression,Dict,RightExpr),
   ArithComparison = [comp(LeftExpr,'=',RightExpr)].

translate_arithmetic_function(const(Constant),Expression,ArithComparison,Dict,Dict):-
   % --- is/2 used to test whether left side evaluates to right side -------------------
   evaluable_expression(Expression,Dict,ArithExpression),
   ArithComparison = [comp(const(Constant),'=',ArithExpression)].




translate_comparison(LeftArg,RightArg,CompOp,Dict,Comparison):-
   evaluable_expression(LeftArg,Dict,LeftTerm),
   evaluable_expression(RightArg,Dict,RightTerm),
   Comparison = [comp(LeftTerm,CompOp,RightTerm)].




% --- translate_functor(Functor,QualifiedTableName) ------------------------------------
%
% translate_functor searches for the matching relation table name for
% a given functor and creates a unique range variable to result in
% a unique qualified relation table name.
%
% --------------------------------------------------------------------------------------

translate_functor(Functor,Arity,rel(TableName,RangeVariable)):-
   relation(Functor,Arity,TableName),
   gensym(rel,RangeVariable).




% --- translate_arguments(Arguments,RelTable,ArgPos,Conditions,Dict) -------------------
%
% translate_arguments organizes the translation of term arguments. One
% term argument after the other is taken from the list of term arguments
% until the list is exhausted. 
%
% --------------------------------------------------------------------------------------

translate_arguments([],_,_,[],Dict,Dict).

translate_arguments([Arg|Args],SQLTable,Position,SQLWhere,Dict,NewDict):-
   translate_argument(Arg,SQLTable,Position,Where,Dict,TmpDict),
   NewPosition is Position + 1,
   translate_arguments(Args,SQLTable,NewPosition,RestWhere,TmpDict,NewDict),
   append(Where,RestWhere,SQLWhere).




% --- translate_argument(Argument,RelTable,Position,Condition,Dict) --------------------
%
% The first occurrence of a variable leads to its associated SQL attribute information
% to be recorded in the Dict. Any further occurrence creates an equi-join condition 
% between the current attribute and the previously recorded attribute.
% Constant arguments always translate to equality comparisons between an attribute and 
% the constant value.
%
% --------------------------------------------------------------------------------------

translate_argument(var(VarId),rel(SQLTable,RangeVar),Position,[],Dict,NewDict):-
   attribute(Position,SQLTable,Attribute),
   add_to_dictionary(VarId,RangeVar,Attribute,all,Dict,NewDict).

translate_argument(var(VarId),rel(SQLTable,RangeVar),Position,AttComparison,Dict,Dict):-
   % --- Variable occurred previously - retrieve first occurrence data from dictionary -
   lookup(VarId,Dict,PrevRangeVar,PrevAtt),
   attribute(Position,SQLTable,Attribute),
   AttComparison = [comp(att(RangeVar,Attribute),=,att(PrevRangeVar,PrevAtt))].

translate_argument(const(Constant),rel(SQLTable,RangeVar),Position,ConstComparison,Dict,Dict):-
   % --- Equality comparison of constant value and attribute in table ------------------
   attribute(Position,SQLTable,Attribute),
   ConstComparison = [comp(att(RangeVar,Attribute),=,const(Constant))].





% --- projection_term_variables(ProjectionTerm,Dict) -----------------------------------
%
% extracts all variables from the ProjectionTerm and places them into the
% Dict as a dict/4 term with their Identifier, a non instantiated RangeVar and 
% Attribute argument, and the keyword existential for the type of quantification
%
% --------------------------------------------------------------------------------------

projection_term_variables(const(_),[]).

projection_term_variables(var(VarId),[dict(VarId,_,_,existential)]).

projection_term_variables(ProjectionTerm,ProjectionTermVariables):-
   ProjectionTerm =.. [Functor|ProjectionTermList],
   not (Functor = var),
   not (ProjectionTermList = []),
   projection_list_vars(ProjectionTermList,ProjectionTermVariables).


projection_list_vars([],[]).
projection_list_vars([var(VarId)|RestArgs],[dict(VarId,_,_,existential)|RestVars]):-
   projection_list_vars(RestArgs,RestVars).
projection_list_vars([const(_)|RestArgs],Vars):-
   projection_list_vars(RestArgs,Vars).






% --------------------------------------------------------------------------------------
% RESTRICTION! ProjectionTerm underlies the following restrictions:
%
%  - ProjectionTerm must have a functor other than the built-in
%    operators, i.e. ',',';', etc. are not allowed
%
%  - only variables and constants are allowed as arguments,
%    i.e. no structured terms
%
% --------------------------------------------------------------------------------------

translate_projection(var(VarId),Dict,SelectList):-
   projection_arguments([var(VarId)],SelectList,Dict).

translate_projection(const(Const),_,[const(Const)]).

translate_projection(ProjectionTerm,Dict,SelectList):-
   ProjectionTerm =.. [Functor|Arguments],
   not (Functor = var),
   not (Functor = const),
   not (Arguments = []),
   projection_arguments(Arguments,SelectList,Dict).



projection_arguments([],[],_).

projection_arguments([Arg|RestArgs],[Att|RestAtts],Dict):-
   retrieve_argument(Arg,Att,Dict),
   projection_arguments(RestArgs,RestAtts,Dict).




% - retrieve_argument(Argument,SQLAttribute,Dictionary) --------------------------------
%
% retrieves the mapping of an argument to the appropriate SQL construct, i.e.
%
%  - qualified attribute names for variables in base goals
%  - arithmetic expressions for variables in arithmetic goals
%  - constant values for constants
% 
% --------------------------------------------------------------------------------------

retrieve_argument(var(VarId),Attribute,Dict):-
   lookup(VarId,Dict,TableName,AttName),
   (
    TableName = is ->
      Attribute = AttName
   ;
      Attribute = att(TableName,AttName)
   ).

retrieve_argument(const(Constant),const(Constant),_).





% --- lookup(Key,Dict,Value) -----------------------------------------------------------

lookup(VarId,Dict,RangeVar,Attribute):-
   member(dict(VarId,RangeVar,Attribute,Quant),Dict),
   (
    Quant = all ->
      true
   ;
      nonvar(RangeVar),
      nonvar(Attribute)
   ).



% --- add_to_dictionary(Key,RangeVar,Attribute,Quantifier,Dict,NewDict) ----------------

add_to_dictionary(Key,RangeVar,Attribute,_,Dict,Dict):-
   member(dict(Key,RangeVar,Attribute,existential),Dict).

add_to_dictionary(Key,RangeVar,Attribute,Quantifier,Dict,NewDict):-
   not member(dict(Key,_,_,_),Dict),
   NewDict = [dict(Key,RangeVar,Attribute,Quantifier)|Dict].




% --- aggregate_function(AggregateFunctionTerm,Dict,AggregateFunctionQuery) ------------
%
% aggregate_function discerns five Prolog aggregate function terms: count, avg, min,
% max, and sum. Each such term is has two arguments: a variable indicating the attribute
% over which the function is to be computed, and a goal argument which must contain in 
% at least one argument position the variable:
%
%    e.g.  avg(Seats,plane(Type,Seats))
%
% These aggregate function terms correspond to the SQL built-in aggregate functions.
% 
% RESTRICTION: AggregateGoal may only be conjunction of (positive or negative) base 
% goals
% 
% --------------------------------------------------------------------------------------

aggregate_function(AggregateFunctionTerm,Dict,AggregateFunctionExpression):-
   AggregateFunctionTerm =..[AggFunctor,AggVar,AggGoal],
   aggregate_functor(AggFunctor,SQLFunction),
   conjunction(AggGoal,AggConjunction),
   aggregate_query_generation(SQLFunction,AggVar,AggConjunction,Dict,AggregateFunctionExpression).


conjunction(Goal,Conjunction):-
   disjunction(Goal,[Conjunction]).




% --- aggregate_query_generation(Function,FunctionVariable,AggGoal,Dict,AggregateQuery) 
%
% compiles the function variable (representing the attribute over which the aggregate 
% function is to be computed) and the aggregate goal (representing the selection and 
% join conditions for the computation of the aggregate function) to an SQL aggregate 
% function subquery.
% 
% --------------------------------------------------------------------------------------

aggregate_query_generation(count,const('*'),AggGoal,Dict,AggregateQuery):-
   translate_conjunction(AggGoal,SQLFrom,SQLWhere,Dict,TmpDict),

   % ATTENTION! It is assumed that in count(*) aggregate query terms there cannot be
   % free variables because '*' stands for "all arguments"

   AggregateQuery = agg_query(Function,(count,[const(*)]),SQLFrom,SQLWhere,[]).


aggregate_query_generation(Function,FunctionVariable,AggGoal,Dict,AggregateQuery):-
   translate_conjunction(AggGoal,SQLFrom,SQLWhere,Dict,TmpDict),

   % --- only variables occurring in the aggregate goal are relevant to the translation
   % of the function variable and the free variables in the goal.
   % Thus subtract from TmpDict all entries of Dict
   set_difference(TmpDict,Dict,AggDict),
 
   translate_projection(FunctionVariable,AggDict,SQLSelect),
   translate_grouping(FunctionVariable,AggDict,SQLGroup),
   AggregateQuery = agg_query(Function,SQLSelect,SQLFrom,SQLWhere,SQLGroup).




% --- translate_grouping(FunctionVariable,Dict,SQLGroup) -------------------------------
%
% finds the free variables in the aggregate function term and collects their
% corresponding SQL qualified attributes in the SQLGroup list.
% 
% --------------------------------------------------------------------------------------

translate_grouping(FunctionVariable,Dict,SQLGroup):-
   free_vars(FunctionVariable,Dict,FreeVariables),
   translate_free_vars(FreeVariables,SQLGroup).




% --- free_vars(FunctionVariable,Dict,FreeVarList) -------------------------------------
%
% A Variable is free if it neither occurs as the FunctionVariable, nor is stored as
% existentially quantified (through ^/2 in the original goal) in the dictionary
% 
% FreeVars contains for each variable the relevant attribute and relation information 
% contained in the dictionary
% 
% --------------------------------------------------------------------------------------

free_vars(FunctionVariable,Dict,FreeVarList):-
  projection_term_variables(FunctionVariable,FunctionVariableList),
  findall((Var,Table,Attribute),
      (member(dict(Var,Table,Attribute,all),Dict),
       not member(dict(Var_,_,_),FunctionVariableList)
      ),
      FreeVarList).


% --- function_variable_list(FunctionVariable,FunctionVariableList) --------------------
%
% extracts the list of variables which occur in the function variable term
%
% RESTRICTION: FunctionVariable may only contain one single variable.
% 
% --------------------------------------------------------------------------------------

function_variable_list(var(VarId),[VarId]).




% --- translate_free_vars(FreeVars,SQLGroup) -------------------------------------------
%
% translates dictionary information on free variables to SQLGroup of aggregate
% function query
% 
% --------------------------------------------------------------------------------------

translate_free_vars([],[]).
translate_free_vars([(VarId,Table,Attribute)|FreeVars],[att(Table,Attribute)|SQLGroups]):-
   translate_free_vars(FreeVars,SQLGroups).




% --- evaluable_expression(ExpressionTerm,Dict,Expression) ----------------------------
%
% evaluable_expression constructs SQL arithmetic expressions with qualified attribute
% names from the Prolog arithmetic expression term and the information stored in the
% dictionary.
%
% The dictionary is not changed because it is used for lookup only. 
% 
% --------------------------------------------------------------------------------------

evaluable_expression(AggregateFunctionTerm,Dict,AggregateFunctionExpression):-
   aggregate_function(AggregateFunctionTerm,Dict,AggregateFunctionExpression).

evaluable_expression(LeftExp + RightExp,Dict,LeftAr + RightAr):-
   evaluable_expression(LeftExp,Dict,LeftAr),
   evaluable_expression(RightExp,Dict,RightAr).

evaluable_expression(LeftExp - RightExp,Dict,LeftAr - RightAr):-
   evaluable_expression(LeftExp,Dict,LeftAr),
   evaluable_expression(RightExp,Dict,RightAr).

evaluable_expression(LeftExp * RightExp,Dict,LeftAr * RightAr):-
   evaluable_expression(LeftExp,Dict,LeftAr),
   evaluable_expression(RightExp,Dict,RightAr).

evaluable_expression(LeftExp / RightExp,Dict, LeftAr / RightAr):-
   evaluable_expression(LeftExp,Dict,LeftAr),
   evaluable_expression(RightExp,Dict,RightAr).

evaluable_expression(var(VarId),Dict,att(RangeVar,Attribute)):-
   lookup(VarId,Dict,RangeVar,Attribute),
   not (RangeVar = is).

evaluable_expression(var(VarId),Dict,ArithmeticExpression):-
   lookup(VarId,Dict,is,ArithmeticExpression).

evaluable_expression(const(Const),_,const(Const)).





% --------------------------------------------------------------------------------------
%
% Output to screen predicates - rather crude at the moment
%
% --------------------------------------------------------------------------------------


% --- printqueries(Code) ---------------------------------------------------------------

printqueries([Query]):-
   nl,
   print_query(Query),
   write(';'),
   nl,
   nl.

printqueries([Query|Queries]):-
   not (Queries = []),
   nl,
   print_query(Query),
   nl,
   write('UNION'),
   nl,
   printqueries(Queries).



% --- print_query(QueryCode) -----------------------------------------------------------

print_query(query([agg_query(Function,Select,From,Where,Group)],_,_)):-
   % --- ugly rule here: aggregate function only in SELECT Part of query ----
   !,
   print_query(agg_query(Function,Select,From,Where,Group)).

print_query(query(Select,From,Where)):-
   print_clause('SELECT',Select,','),
   nl,
   print_clause('FROM',From,','),
   nl,
   print_clause('WHERE',Where,'AND'),
   nl.

print_query(agg_query(Function,Select,From,Where,Group)):-
   print_clause('SELECT',Function,Select,','),
   nl,
   print_clause('FROM',From,','),
   nl,
   print_clause('WHERE',Where,'AND'),
   nl,
   print_clause('GROUP BY',Group,',').

print_query(negated_existential_subquery(Select,From,Where)):-
   write('NOT EXISTS'),
   nl,
   write('('),
   print_clause('SELECT',Select,','),
   nl,
   print_clause('FROM',From,','),
   nl,
   print_clause('WHERE',Where,'AND'),
   nl,
   write(')').




% --- print_clause(Keyword,ClauseCode,Separator) ---------------------------------------
%
% with 
% Keyword    one of SELECT, FROM, WHERE, or GROUP BY, 
% ClauseCode the code corresponding to the appropriate clause of an SQL query, and 
% Separator  indicating the character(s) through which the items of a clause
%            are separated from each other (',' or 'AND').
% 
% --------------------------------------------------------------------------------------

print_clause(Keyword,[],_).

print_clause(Keyword,[Column|RestColumns],Separator):-
   write(Keyword),
   write(' '),
   print_clause([Column|RestColumns],Separator).

print_clause(Keyword,Function,[Column],Separator):-
   write(Keyword),
   write(' '),
   write(Function),
   write('('),
   print_clause([Column],Separator),
   write(')').





% --- print_clause(ClauseCode,Separator) -----------------------------------------------

print_clause([Item],_):-
   print_column(Item).

print_clause([Item,NextItem|RestItems],Separator):-
   print_column(Item),
   write(' '),
   write(Separator),
   write(' '),
   print_clause([NextItem|RestItems],Separator).




% --- print_column(ColumnCode) ---------------------------------------------------------

print_column('*'):-
   write('*').

print_column(att(RangeVar,Attribute)):-
   write(RangeVar),
   write('.'),
   write(Attribute).

print_column(rel(Table,RangeVar)):-
   write(Table),
   write(' '),
   write(RangeVar).

print_column(const(Value)):-
   write(Value).

print_column(comp(LeftArg,Operator,RightArg)):-
   print_column(LeftArg),
   write(' '),
   write(Operator),
   write(' '),
   print_column(RightArg).

print_column(LeftExpr * RightExpr):-
   print_column(LeftExpr),
   write('*'),
   print_column(RightExpr).

print_column(LeftExpr / RightExpr):-
   print_column(LeftExpr),
   write('/'),
   print_column(RightExpr).

print_column(LeftExpr + RightExpr):-
   print_column(LeftExpr),
   write('+'),
   print_column(RightExpr).

print_column(LeftExpr - RightExpr):-
   print_column(LeftExpr),
   write('-'),
   print_column(RightExpr).

print_column(agg_query(Function,Select,From,Where,Group)):-
   nl,
   write('('),
   print_query(agg_query(Function,Select,From,Where,Group)),
   write(')').

print_column(negated_existential_subquery(Select,From,Where)):-
   print_query(negated_existential_subquery(Select,From,Where)).
append([],L,L).
append([H1|L1],L2,[H1|L3]):-
   append(L1,L2,L3).



member(X,[X|_]).
member(X,[_|T]):-
   member(X,T).



repeat_n(N):-
   integer(N),
   N > 0,
   repeat_1(N).

repeat_1(1):-!.
repeat_1(_).
repeat_1(N):-
   N1 is N-1,
   repeat_1(N1).



% --- benchmark programs for translation of database goals ---------------
%
% taken from R. O'Keefe: The Craft of Prolog, MIT Press 1990
%
% Sepia Prolog version

cpu_time(Time):-
   cputime(Time).


cpu_time(Goal,Duration):-
   !,
   cputime(T1),
   (call(Goal) -> true; true),
   cputime(T2),
   Duration is T2 - T1.

cpu_time(N,Goal,Duration):-
   !,
   cpu_time((repeat_n(N),(Goal -> fail);true),D1),
   cpu_time((repeat_n(N),(true -> fail);true),D2),
   Duration is D1 - D2.



% --- set_difference(SetA,SetB,Difference) --------------------------------------------
%
% SetA - SetB = Difference

set_difference([],_,[]).

set_difference([Element|RestSet],Set,[Element|RestDifference]):-
   not member(Element,Set),
   set_difference(RestSet,Set,RestDifference).

set_difference([Element|RestSet],Set,RestDifference):-
   member(Element,Set),
   set_difference(RestSet,Set,RestDifference).
bench(N,D):-
   cpu_time(N,translate(flight(No,Dep,Dest,Type),flight(No,Dep,Dest,Type),SQLQueryTerm),D).

bench(N,D):-
   cpu_time(N,translate(capacity(No,Dep,Dest,Type,Seats),(flight(No,Dep,Dest,Type),plane(Type,Seats),Type='b-737'),SQLQueryTerm),D).

bench(N,D):-
   cpu_time(N,translate(no_planes(No,Dep,Dest,Type),(flight(No,Dep,Dest,Type),not plane(Type,Seats)),SQLQueryTerm),D).

bench(N,D):-
   cpu_time(N,translate(X,X is count(S,plane(P,S)),SQLQueryTerm),D).



% --- sample query from report --------------------

bench(N,D):-
   cpu_time(N,translate(big_planes(munich,Dest,Type,Seats),FNo^(flight(FNo,munich,Dest,Type),plane(Type,Seats),Seats > avg(S, T^plane(T,S))),SQLQueryTerm),D).
% --- benchmarks of sample queries ---------

benchmark(N,1,D):-
   cpu_time(N,translate(flight(No,Dep,Dest,Type),flight(No,Dep,Dest,Type),Code),D).
benchmark(N,2,D):-
   cpu_time(N,translate(capacity(No,Dep,Dest,Type,Seats),(flight(No,Dep,Dest,Type),plane(Type,Seats),Type='b-737'),Code),D).
benchmark(N,3,D):-
   cpu_time(N,translate(no_planes(No,Dep,Dest,Type),(flight(No,Dep,Dest,Type),not plane(Type,Seats)),Code),D).
benchmark(N,4,D):-
   cpu_time(N,translate(X,X is count(S,plane(P,S)),Code),D).
benchmark(N,5,D):-
   cpu_time(N,translate(big_planes(munich,Dest,Type,Seats),FNo^(flight(FNo,munich,Dest,Type),plane(Type,Seats),Seats > avg(S, T^plane(T,S))),SQLQueryTerm),D).
% --- gensym(Root,Symbol) ----------------------------------------------------
%
% SEPIA 3.0.7. version - other Prolog implementations provide gensym/2
% and init_gensym/1 as built-ins. */
%
% (C) Christoph Draxler, Aug. 1992
%
% 

gensym(Root,Symbol):-
   not var(Root),
   var(Symbol),

   incval(Root),
   getval(Root,Counter),

   % --- create char list of root and counter ---
   name(Root,RootList),
   name(Counter,CounterList),

   % --- append RootList and CounterList ---
   append(RootList,CounterList,SymbolList),

   % --- create atom from SymbolList ---
   name(Symbol,SymbolList).


init_gensym(Root):-
   not var(Root),
   setval(Root,0).