\documentclass [12pt,letterpaper, notitlepage]{report}
\usepackage[dvips]{graphicx}
\usepackage{color}
\title{SQL Front-End for the JRelix Relational-Programming System \vspace{0.4 in}}
\author{Ibrahima KHAYA \\ \\
{\normalsize School of Computer Science} \\
{\normalsize McGill University, Montreal, Quebec, Canada}}
\date{{\normalsize March 2008}}
\pagestyle{headings}
\begin{document}
\begin{titlepage}
    \maketitle
\thispagestyle{empty}
    
    \vfill
    
    \begin{center}
{\normalsize A thesis submitted to McGill University in partial fulfilment of the requirements of the degree of} 

{\normalsize Master of Science }

\vspace{0.25 in}


{\normalsize T. H. Merrett, Advisor }

\vspace{0.25 in}

{\footnotesize Copyright \copyright \hspace{0.04 in} Ibrahima KHAYA 2008}	
\end{center}
  \end{titlepage}
  
\chapter*{Abstract}

This thesis discusses the design and implementation of an SQL front end for a relational database programming system JRelix. The purpose of this thesis is to lay a strong basis for the full SQL support by JRelix.

The SQL language is the de facto standard in Relational Databases which motivates its integration into JRelix. Through the SQLSTMT and SQLEXP commands the user can use SQL to perform operations on a JRelix database. These operations are translated into Aldat (the native programming language of JRelix) and can interactively perform updates, deletions and selections on the distinct relations of the database. The SQLSTMT command allows us to execute full SQL commands on the system whereas the SQLEXP command returns a relational expression to the system that can interact with other elements of the commands written in Aldat in the same statement.

\chapter*{R\'{e}sum\'{e}}

La pr\'{e}sente th\`{e}se traite de la conception et de la mise en \oe uvre d'une interface SQL pour le syst\`{e}me de programmation de bases de donn\'{e}es relationnelles JRelix. Cette th\`{e}se a pour but de poser les fondements d'une couverture exhaustive de SQL par JRelix.

Le Language SQL est le standard en bases de donn\'{e}es relationnelles ce qui est \`{a} l'origine de son int\'{e}gration dans JRelix. A l'aide des commandes SQLSTMT et SQLEXP l'utilisateur peut effectuer des requ\^{e}tes sur la base de donn\'{e}es JRelix en SQL. Ces requ\^{e}tes sont traduites en Aldat (le language natif de programmation de JRelix) et peut, de fa\c{c}on interactive, effectuer mises \`{a} jour, suppressions et s\'{e}lections sur les diff\'{e}rentes relations. La commande SQLSTMT permet d'ex\'{e}cuter des requ\^{e}tes enti\`{e}rement exprim\'{e}es en SQL alors que la commande SQLEXP retourne au syst\`{e}me une expression relationnelle qui peut interagir avec d'autres expressions relationnelles exprim\'{e}es en Aldat dans la m\^{e}me requ\^{e}te.

\pagenumbering{roman} \setcounter{page}{1}

\chapter*{Acknowledgments}

First and foremost, I would really like to thank my thesis supervisor \mbox{Professor} Tim MERRETT. First for giving me a whole different point of view on relational databases, then for giving me the opportunity to go further on this subject by having my research in this domain of interest and finally for being always present to motivate my work, to give me a noticeable financial support, to give valuable insight during the implementation and to carefully read my thesis. 

All this work and all my education would not have been if it would not have been my parents, Modou KHAYA and Aminata NDOYE. Their love, support and confidence in me and my ambitions just were everything. I cannot be more grateful to the man that was, is and will always be my hero and role model and to the woman that sacrificed her body, her time and her carreer for me without any hesitation. 

I wish to thank my sister, Amy KHAYA, who has always been there for me and who has always driven me in becoming a better student and a better person. I also wish to thank my brother-in-law, Oumar DIA, for being the older brother that I have always dreamed of. His support was crucial. 

Last but not least, I owe a special thought to my grand-mother, Sabelle NIANG, for showing me that there are few things stronger than your will when you are really decided to do something and to my whole family, back in Senegal who have always been very supportive of my education. 

\tableofcontents%

	\chapter{Introduction}
	
	\pagenumbering{arabic} \setcounter{page}{1}
	
		\section{SQL Generalities}
		
		We will narrow our overview of SQL to the areas we covered in our research. We will also use the SQL conventions of Oracle 7.
		
			\subsection{History}
			
			Based on the model defined by Dr. E.F. Codd in his paper \cite{RelModel1}, IBM developed in the 1970's, the Relational Database Project System R and the Structured English QUEry Language (SEQUEL)\cite{Sequel1} used to perform queries on that database. SEQUEL became the Structured Query Language (SQL) after standardization. It has been extended by each Relational DataBase Management System (RDBMS) vendor. Oracle was the first to introduce SQL commercial implementation, in 1979.
			
		\subsection{Data Modification}
		
		Manipulating the data to reflect changes in the database is as important as viewing it, if not more important. So we will begin by the manipulation. This is mainly achieved through the three following commands in SQL : \textit{Insert, Update and Delete}.
		
		\subsubsection{Update}
		
		\textit{Updates} are expressed in SQL using an optional condition in the \textit{Where} clause to \texttt{"}flag\texttt{"} the tuples that should be updated otherwise all tuples are updated. 
		The syntax is the following : \newline
			\begin{quote}
		UPDATE \textit{relation} SET \textit{att} = \textit{value$|$exp1} WHERE \textit{condition-list} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation from which tuples will be updated.
				\item \textit{att} : The name of the attribute to update in the relation cited above.
				\item \textit{value$|$exp1} : The new value of the attribute. It can be a constant, an attribute or an arithmetic expression involving the attributes of the relation.
				\item \textit{condition-list} : The boolean expression corresponding to the conditions that need to be satisfied to have tuples flagged for the update. This boolean expression is expressed in the boolean algebra using the classic \textbf{(and, or, not)} sufficient set of operators. 				
			\end{itemize}
			
		\subsubsection{Delete}
		
		\textit{Deletions} are expressed in SQL using an optional condition in the \textit{Where} clause to \texttt{"}flag\texttt{"} the tuples that should be deleted otherwise all tuples are deleted. That may be useful in order to keep the structure of the relation without the data.
		The syntax is the following : \newline
			\begin{quote}
		DELETE FROM \textit{relation} WHERE \textit{condition-list} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation from which tuples will be deleted.
				\item \textit{condition-list} : The boolean expression corresponding to the conditions that need to be satisfied to have tuples flagged for the delete.  				
			\end{itemize}
			
		\subsubsection{Insert}
		
		In SQL inserting tuples in an existing relation can be done using the \textit{Insert Into} command. A single tuple can be inserted using the keyword \textit{Values} or another relation using a subquery. Nevertheless the subquery is not inserted as a relation but rather as a set of tuples.
		The syntax is the following : \newline
			\begin{quote}
		INSERT INTO \textit{relation(att1, ..., attn)} VALUES \textit{(value1, ..., \mbox{valuen})} ;\newline
		or \newline
		INSERT INTO \textit{relation(att1, ..., attn)} (\textit{subquery}) ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation(att1, ..., attn)} : The name of the relation in which tuples will be inserted. 
			The attributes cited will be filled with the corresponding values. The other attributes of the relation, if any, are filled by nulls. 
				\item \textit{(value1, ..., valuen)} : The constants to insert in the relation. Their count should be the same as the cited attributes count from the relation.
				\item \textit{subquery} : The subquery that will produce the set of tuples to insert. The count of attributes of that set should be the same as the cited attributes count from the relation.				
			\end{itemize}
			
		\subsection{Selections}
		
		The selectors in their different variants allow us to extract and view the elements of data that the user wants to see from the database. They are the commands that probably are the most used in a first approach to SQL. 
	\subsubsection{Selects}
	
		Concerning the syntax of selections they accept one of these two options:
	\begin{itemize}
			\item \textit{Distinct} : This option causes a selection to consider only
distinct tuples.
			\item \textit{All} : This option causes a selection to consider all tuples
including duplicates. This is the default option in SQL.		
			\end{itemize}
		The syntax is the following : \newline
			\begin{quote}
		SELECT [DISTINCT$|$ALL] \textit{exp1} [[AS]\textit{Alias1}], ..., \textit{expn} [[AS]\textit{Aliasn}] FROM \textit{relation-list} WHERE \textit{condition-list} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{exp1} [[AS]\textit{Alias1}], ..., \textit{expn} [[AS]\textit{Aliasn}] : The expressions returned by the selection with their corresponding alias, which are optional. They can be a constant, an attribute or an arithmetic expression involving the attributes of the relation.
				\item \textit{relation-list} : The name of the relations involved in the query.
				\item \textit{condition-list} : The boolean expression corresponding to the conditions that need to be satisfied to have tuples returned in the selection. 			
			\end{itemize}
			It is possible to select all available fields from the relation using the \texttt{"}*\texttt{"} special character. 
		The syntax is the following : \newline
			\begin{quote}
		SELECT [DISTINCT$|$ALL] * FROM \textit{relation-list} WHERE \textit{condition-list} ;
			\end{quote}
		It is also possible to create a relation having the same structure as the source relation and insert the tuples at the same time using the \textit{Select Into} command. It acts as the \textit{Insert Into} command with a subquery. The syntax is the following : \newline
			\begin{quote}
		SELECT [DISTINCT$|$ALL] \textit{exp1} [AS] [\textit{Alias1}], ..., \textit{expn} [AS] [\textit{Aliasn}] INTO  \textit{relation} FROM \textit{relation-list} WHERE \textit{condition-list} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation that will be created and in which tuples will be inserted.
			\end{itemize}
			
	\subsubsection{Selections with Joins}
	
	The join conditions are specified in the \textit{condition-list} of the \textit{Where} clause. The relations involved are in the \textit{relation-list} in the \textit{from} clause. If no join condition is specified a cartesian product is made. 
	The different joins that can be made are : 
	\begin{itemize}
		\item \textbf{INNER JOIN} \newline
		Specify the attribute from each relation on which you want to perform the join.
			\begin{quote}
			SELECT X, Y, Z FROM R, S WHERE R.Y = S.Y ;
			\end{quote}
		\item \textbf{LEFT OUTER JOIN} \newline
		To allow nulls on the right side of the join use (+) on that side.
			\begin{quote}
			SELECT X, Y, Z FROM R, S WHERE R.Y = S.Y (+);
			\end{quote}
		\item \textbf{RIGHT OUTER JOIN} \newline
		To allow nulls on the left side of the join use (+) on that side.
			\begin{quote} 
			SELECT X, Y, Z FROM R, S WHERE R.Y (+) = S.Y ;
			\end{quote}
		\item \textbf{FULL OUTER JOIN}	\newline
		You are obliged as mentioned below to make the union of the right and the left outer join to get the nulls on both side. The following is not allowed :
			\begin{quote}
			SELECT X, Y, Z FROM R, S WHERE R.Y (+) = S.Y (+);
			\end{quote}
		\item \textbf{CARTESIAN PRODUCT} \newline
		No condition is specified to perform directly the cartesian product.
			\begin{quote}
			SELECT X, Y, Z FROM R, S;
			\end{quote}
	\end{itemize}
			Note that selection conditions as well as join conditions can be expressed at the same time in the \textit{condition-list} as in the following : 
			\begin{quote}
			SELECT X, Y, Z FROM R, S WHERE R.Y = S.Y AND \mbox{W = 1};
			\end{quote}
			
	\subsubsection{\label{SetOperators}Selections with Set Operators}
	
	Oracle allows the use of the following set operators:
		\begin{itemize}
			\item UNION 
			\item UNION ALL (allows duplication in the union)
			\item INTERSECT
			\item MINUS
		\end{itemize}
		Nevertheless these are only set operators and may need to be combined with join operators to express complex joins. \newline
		For example, if we take the case of the \textit{full outer join}:
			\begin{quote}
			(SELECT X, Y, Z FROM R, S WHERE R.Y (+) = S.Y) \newline
			UNION \newline
			(SELECT X, Y, Z FROM R, S WHERE R.Y = S.Y (+));
			\end{quote}
			These set operators can only be used on \textit{selections} and not directly on relations because there is a syntactic restriction. So the following is not allowed : \newline
			\begin{quote}
			SELECT X, Y, Z FROM R UNION S;
			\end{quote}
			
		\subsection{Aggregations}
		
		Aggregation is performed in SQL through the aggregation functions such as \textit{Sum or Max}. The optional presence of the \textit{Group By} clause allows us to aggregate regarding certain criteria. For aggregated data an eventual condition will be expressed by a \textit{Having} clause. So there is a clear distinction between the \textit{Where} keyword reserved for individual tuples and the \textit{Having} keyword reserved for aggregated tuples.
		
		Concerning the syntax of these aggregation functions they accept one of these two options:
	\begin{itemize}
			\item \textit{Distinct} : This option causes an aggregation function to consider only
distinct values of the argument throughout all the tuples returned.
			\item \textit{All} : This option causes an aggregation function to consider all values
including all duplicates. This is the default option in SQL.
		\end{itemize}
		The syntax of the main aggregation functions is the following :
		\begin{itemize}
			\item SUM([DISTINCT$|$ALL] att) returns the sum of att.
			\item AVG([DISTINCT$|$ALL] att) returns the average of att.
			\item MIN([DISTINCT$|$ALL] att) returns the min of att.
			\item MAX([DISTINCT$|$ALL] att) returns the max of att.
			\item COUNT(*$|$[DISTINCT$|$ALL] att) returns the numbers of tuples. If * is specified all tuples will be counted otherwise tuples containing non-null values in att will be counted.
		\end{itemize}
		All aggregation functions except COUNT(*) ignore nulls.
		
		In a complete query it will be in the following form : \newline
			\begin{quote}
		SELECT [DISTINCT$|$ALL] \textit{aggregate-function}([DISTINCT$|$ALL]\textit{exp1}) [AS] [\textit{Alias1}], ..., \textit{aggregate-function}(\textit{expn}) [AS] [\textit{Aliasn}], \textit{exp1'} [AS] [\textit{Alias1'}], ..., \textit{expn'} [AS] [\textit{Aliasn'}]  FROM \textit{relation-list} WHERE \textit{condition-list} GROUP BY \textit{exp1'}, ... , \textit{expn'} HAVING \textit{condition-list'};
			\end{quote}
				For example we could have the following : \newline
				\begin{quote}
					SELECT SUM(salary) AS SumSal, MAX(salary), department FROM employees WHERE seniority $>$ 3 GROUP BY department HAVING SUM(salary) $>$ 100000;
				\end{quote}
				This would give the total amount of salaries and the greatest salary by department for the employees having more than 3 years of seniority where the total amount of salaries of the department is greater than 100000. The \textit{Having} condition applies to the total returned.
				
				Note that when no alias is specified a system-generated name is used and that the system does not allow us to reuse the alias SumSal in the \textit{Having} clause. That is allowed in MySQL only.
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{aggregate-function}(\textit{exp1}) [AS] [\textit{Alias1}], ..., \textit{aggregate-function}(\textit{expn}) [AS] [\textit{Aliasn}] : The expressions on which the aggregation functions will be performed and their corresponding aliases, if any.
				\item \textit{relation-list} : The name of the relations involved in the query.
				\item \textit{condition-list} : The boolean expression corresponding to the conditions that need to be satisfied to have simple tuples considered for the aggregation. 			
				\item \textit{condition-list'} : The boolean expression corresponding to the conditions that need to be satisfied by the aggregated tuples to be returned in the selection. 		
				\item \textit{exp1'} [AS] [\textit{Alias1'}], ..., \textit{expn'} [AS] [\textit{Aliasn'}] : The expressions on which the aggregation will be based and their corresponding aliases, if any.	
			\end{itemize}
			
		\subsection{Relation creation and deletion}
		
		In SQL a relation and its attributes creations are linked. It is in the relation creation command that the the attributes datatypes and properties are specified. The syntax is the following : \newline
			\begin{quote}
		CREATE TABLE \textit{relation} (\textit{col1 datatype1}, ..., \textit{coln datatypen})  ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation that will be created.
				\item \textit{col1 datatype1}, ..., \textit{coln datatypen} : The name of the attributes included in this relation and their corresponding datatypes.
			\end{itemize}
			To delete a relation you just use the following syntax : \newline
			\begin{quote}
		DROP TABLE \textit{relation} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation that will be deleted.
			\end{itemize}
			
		\subsection{Triggers}
		
		Triggers can be used in Oracle 7. They can be triggered by \textit{Update, Delete or Insert} statements. The trigger body can be executed \textit{Before or After} the data manipulation. The old and new configuration of the relation are referenced as \textit{OLD} and \textit{NEW}. The trigger can be started only once for the statement or for each tuple affected by the statement using the \textit{FOR EACH ROW} command.
		
		We could have as an example :
			\begin{quote}
			CREATE TRIGGER trig \newline
			AFTER UPDATE ON Employees \newline
			FOR EACH ROW\newline
			WHEN NEW.hierarchy = \texttt{\char"0D}Manager\texttt{\char"0D}\newline
			BEGIN\newline
				INSERT INTO Managers VALUES (New.fName, New.lName)\newline
			END
			\end{quote}
		Recursive Triggers can be implemented but there is a hard coded limit of 50 recursive calls before raising an error to prevent infinite loops. This limit will be configurable after \textit{Oracle 8} which allows a mechanism to prevent infinite loops and have the flexibility of choosing the limit to reach.
		
		\section{Aldat Generalities}
		
		We will restrict our overview of Aldat to the areas we covered in our research. We will use a similar breakdown for this section to the breakdown in the previous one.
		
			\subsection{History}
			
			Based on the same paper from Codd \cite{RelModel1} McGill began the \textit{Al}gebraic approach to \textit{dat}a (Aldat) Project in the 1970's and extended Codd's Relational Algebra to the Domain Algebra proposed by Merrett \cite{Merrett1}. This extension toward the Domain Algebra allowed Aldat to directly deal with Programming aspects in its core from a relational point of view. 
			
			The latest implementation of Aldat as a RDBMS is the \textit{J}ava implementation of a \textit{Rel}ational database programming language in Un\textit{ix} (JRelix). This implementation is principally based on the contributions made by Baker\cite{Baker1}, Yuan\cite{Yuan1} and Hao\cite{Hao1}, through their M.Sc. theses and projects at McGill.
			
		\subsection{Data Modification}
		
		\subsubsection{Update}
		
		\textit{Updates} are expressed in Aldat using a join to \texttt{"}flag\texttt{"} the tuples that should be updated otherwise all tuples are updated. The syntax is the following : \newline
			\begin{quote}
		UPDATE \textit{relation} CHANGE \textit{att} $<$- \textit{value$|$exp1} USING \textit{relational expression} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation from which tuples will be updated.
				\item \textit{att} : The name of the attribute to update in the relation cited above.
				\item \textit{value$|$exp1} : The new value of the attribute. It can be a constant, an attribute or an arithmetic expression involving the attributes of the relation.
				\item \textit{relational expression} : The relational expression that is joined with \textit{relation} to flag its tuples for the update. 				
			\end{itemize}
			Another alternative is to use conditions rather than a join to update. In that case there is no join to \texttt{"}flag\texttt{"} the tuples that should be updated so all of them are considered for the update and it is the conditional expression that changes only the tuples that need to. Of course this is not optimal because even though only one tuple may have to be updated all of them will be selected for the update. The syntax is the following :\newline
			\begin{quote}
		UPDATE \textit{relation} CHANGE \textit{att} $<$- IF \textit{condition-list} THEN \textit{value$|$exp1} ELSE \textit{att} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{condition-list} : The boolean expression corresponding to the conditions that need to be satisfied to do the update.		
			\end{itemize}			
			
		\subsubsection{Delete}
		
		\textit{Deletions} are expressed in Aldat using a keyword to specify the tuples that should be deleted. 
		The syntax is the following : \newline
			\begin{quote}
		UPDATE \textit{relation} DELETE \textit{relational expression} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation from which tuples will be deleted.
				\item \textit{relational expression} : The relational expression that is used to specify the deletion. 				
			\end{itemize}
			
		\subsubsection{Insert}
		
		Insertions are performed in Aldat using the following syntax : 
			\begin{quote}
		UPDATE \textit{relation} ADD \textit{relational expression} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation to which tuples will be added.
				\item \textit{relational expression} : The relational expression whose tuples will be inserted in \textit{relation}. 				
			\end{itemize}		
			
		\subsection{Selections}
		
	\subsubsection{Selects}
	
		In Aldat selections are divided into three categories :
		\begin{itemize}
			\item Projections consist of a selection of available attributes but with all tuples returned. They use the following syntax : \newline
			\begin{quote}
		[\textit{att1}, ..., \textit{attn}] IN \textit{relational expression} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{att1}, ..., \textit{attn} : The attributes returned by the selection.
				\item \textit{relational expression} : The relational expression that is used as a source for the selection. 
				\item \textit{condition-list} : The boolean expression corresponding to the conditions that need to be satisfied to have tuples returned in the selection. 			
			\end{itemize}
			\item Selections consist of a selection of available tuples but with all attributes returned. They use the following syntax : \newline
			\begin{quote}
		WHERE \textit{condition-list} IN \textit{relational expression} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relational expression} : The relational expression that is used as a source for the selection. 
				\item \textit{condition-list} : The boolean expression corresponding to the conditions that need to be satisfied to have tuples returned in the selection. 			
			\end{itemize}
			\item T-Selections consist first of a selection of available tuples and then of available attributes. It is a fusion of the two preceding selections. They use the following syntax : \newline
			\begin{quote}
		[\textit{att1}, ..., \textit{attn}] WHERE \textit{condition-list} IN \textit{relational expression} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{att1}, ..., \textit{attn} : The attributes returned by the selection.
				\item \textit{relational expression} : The relational expression that is used as a source for the selection. 
				\item \textit{condition-list} : The boolean expression corresponding to the conditions that need to be satisfied to have tuples returned in the selection. 			
			\end{itemize}			
		\end{itemize}
		From this point we will be considering T-Selections throughout this section since they can express anything that can be expressed with the two others. Also note that Aldat will always return distinct tuples, being fully relational.
		
	\subsubsection{Selections with Joins}	
	
	Aldat being all relational by design there are no set operators but only join operators. They are :
	\begin{itemize}
		\item \textbf{INNER JOIN} \newline
		You specify the attribute from each relation on which you want to perform the join.
			\begin{quote}
			[X, Y, Z] IN (R[Y:IJOIN:Y]S) ;
			\end{quote}
			If the attribute is the same on both relations then you are not obliged to specify it and Aldat will perform the join on the common attribute available :
			\begin{quote}
			[X, Y, Z] IN (R IJOIN S) ;
			\end{quote}
			This can be performed for all joins. From now on we will be considering the case where the join attributes are explicit.
		\item \textbf{LEFT OUTER JOIN} \newline
		You specify that you want to allow nulls on the right side of the join  using the \textit{ljoin} operator.
			\begin{quote}
			[X, Y, Z] IN (R[Y:LJOIN:Y]S );
			\end{quote}
		\item \textbf{RIGHT OUTER JOIN} \newline
		You specify that you want to allow nulls on the left side of the join using the \textit{rjoin} operator.
			\begin{quote} 
			[X, Y, Z] IN (R[Y:RJOIN:Y]S) ;
			\end{quote}
		\item \textbf{FULL OUTER JOIN}	\newline
		You specify that you want to allow nulls on both sides of the join using the \textit{ujoin} operator.
			\begin{quote}
			[X, Y, Z] IN (R[Y:UJOIN:Y]S) ;
			\end{quote}
		\item \textbf{DIFFERENCE JOIN}	\newline
		You specify that you do not want to allow the tuples matching on the right side of the join using the \textit{djoin} operator.
			\begin{quote}
			[X, Y, Z] IN (R[Y:DJOIN:Y]S) ;
			\end{quote}
		\item \textbf{DIFFERENCE RIGHT JOIN}	\newline
		You specify that you do not want to allow the tuples matching on the left side of the join using the \textit{drjoin} operator.
			\begin{quote}
			[X, Y, Z] IN (R[Y:DRJOIN:Y]S) ;
			\end{quote}
		\item \textbf{SYMMETRIC DIFFERENCE JOIN}	\newline
		You specify that you do not want to allow the tuples matching on both sides of the join using the \textit{sjoin} operator.
			\begin{quote}
			[X, Y, Z] IN (R[Y:SJOIN:Y]S) ;
			\end{quote}
		\item \textbf{CARTESIAN PRODUCT} \newline
		If there is no common attributes the cartesian product is directly performed using the \textit{ijoin} operator.
			\begin{quote}
			[X, Y, Z] IN (R IJOIN S) ;
			\end{quote}
			Note that selection conditions could be used on the relational expression resulting from the join as in the following : 
			\begin{quote}
			[X, Y, Z] WHERE W = 1 IN (R[Y:IJOIN:Y]S) ;
			\end{quote}
	\end{itemize}
	
		\subsection{Aggregations through Domain Algebra}
		
		We will limit our overview of the Domain Algebra to the elements relevant to the aggregation.
		The domain algebra can be divided into two main types of operations : 
		\begin{itemize}
			\item The horizontal operations that cover arithmetic expressions including attributes, the use of constants and the renaming (aliasing) of the attributes.			
			\item The vertical (aggregations) operations : \textit{reduction}, \textit{equivalence reduction}, \textit{functional mapping} and \textit{partial functional mapping}. 
		\end{itemize}
		We will principally focus on the latter ones. The first operation relevant is the \textit{reduction}.
			The syntax is the following : \newline
			\begin{quote}
			LET \textit{Alias} BE RED \textit{Operator} OF \textit{exp} ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{Alias} : The name of the aggregated expression.
				\item \textit{Operator} : One of the operator that can be used in reduction operations : \texttt{"}+\texttt{"}, \texttt{"}*\texttt{"}, \texttt{"}max\texttt{"}, \texttt{"}min\texttt{"}, \texttt{"}and\texttt{"}, \texttt{"}or\texttt{"}.
				\item \textit{exp} : The expression on which the aggregation will be performed.
			\end{itemize}
			The \textit{reduction} allows us to make aggregation but does not do it using a grouping. For that we have to use the \textit{equivalence reduction} whose syntax is the following : \newline
			\begin{quote}
			LET \textit{Alias} BE EQUIV \textit{Operator} OF \textit{exp} BY \textit{att1, ..., attn};
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{Alias} : The name of the aggregated expression.
				\item \textit{Operator} : One of the operator that can be used in reduction operations : \texttt{"}+\texttt{"}, \texttt{"}*\texttt{"}, \texttt{"}max\texttt{"}, \texttt{"}min\texttt{"}, \texttt{"}and\texttt{"}, \texttt{"}or\texttt{"}.
				\item \textit{exp} : The expression on which the aggregation will be performed.
				\item \textit{att1, ..., attn} : The attributes on which the grouping will be performed.
			\end{itemize}
			Aldat also allows us to perform operations in a cumulative manner. The \textit{functional mapping} is used for that with the following syntax : \newline
			\begin{quote}
			LET \textit{Alias} BE FUN \textit{Operator} OF \textit{exp} ORDER \textit{att1, ..., attn};
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{Alias} : The name of the aggregated expression.
				\item \textit{Operator} : One of the operator that can be used in functional mapping operations : \texttt{"}+\texttt{"}, \texttt{"}*\texttt{"}, \texttt{"}-\texttt{"}, \texttt{"}�\texttt{"}, \texttt{"}max\texttt{"}, \texttt{"}min\texttt{"}, \texttt{"}$|$$|$\texttt{"}, \texttt{"}pred\texttt{"}, \texttt{"}succ\texttt{"}, \texttt{"}and\texttt{"}, \texttt{"}or\texttt{"}.
				\item \textit{exp} : The expression on which the aggregation will be performed.
				\item \textit{att1, ..., attn} : The attributes that are the basis of the accumulation.
			\end{itemize}
			The accumulation can also be performed under a grouping with the following syntax : \newline
			\begin{quote}
			LET \textit{Alias} BE PAR \textit{Operator} OF \textit{exp} ORDER \textit{att1, ..., attn} BY \textit{att1', ..., attn'};
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{Alias} : The name of the aggregated expression.
				\item \textit{Operator} : One of the operator that can be used in functional mapping operations : \texttt{"}+\texttt{"}, \texttt{"}*\texttt{"}, \texttt{"}-\texttt{"}, \texttt{"}�\texttt{"}, \texttt{"}max\texttt{"}, \texttt{"}min\texttt{"}, \texttt{"}$|$$|$\texttt{"}, \texttt{"}pred\texttt{"}, \texttt{"}succ\texttt{"}, \texttt{"}and\texttt{"}, \texttt{"}or\texttt{"}.
				\item \textit{exp} : The expression on which the aggregation will be performed.
				\item \textit{att1, ..., attn} : The attributes that are the basis of the accumulation.
				\item \textit{att1', ..., attn'} : The attributes on which the grouping will be performed.
			\end{itemize}
			
		\subsection{Relation creation and deletion}
		
		In Aldat a relation and its attributes creations are totally independent. The attributes and their datatypes have to be created first and then the relation can be created. The syntax is the following : \newline
			\begin{quote}
			DOMAIN \textit{col1 datatype1};\newline
			...\newline
			DOMAIN \textit{col1 datatype1};\newline
			RELATION \textit{relation} (\textit{col1}, ..., \textit{coln})  ;
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation that will be deleted.
				\item \textit{col1 datatype1}, ..., \textit{coln datatypen} : The name of the attributes included in this relation and their corresponding datatypes.
			\end{itemize}
			To delete a relation and the attributes composing it you just use the following syntax : \newline
			\begin{quote}
			DR \textit{relation} ; \newline
			DD \textit{col1}, ..., \textit{coln};
			\end{quote}
			The definitions of the terms used are as follows : 
			\begin{itemize}
				\item \textit{relation} : The name of the relation that will be deleted.
				\item \textit{col1}, ..., \textit{coln} : The name of the attributes that will be deleted.
			\end{itemize}
		
		\subsection{Triggers}
		
		Triggers called event handlers are also part of Aldat. They can be triggered by \textit{Change, Delete or Add} statements. The trigger body can be executed before (\textit{Pre}) or after (\textit{Post}) the data manipulation. In the case of a \textit{Pre} The old configuration of the relation is referenced as the relation itself and the new configuration as \textit{TRIGGER}. In the case of a \textit{Post} it is the other way around. A simple example would be : \newline
			\begin{quote}
				Comp:Post:Change:Employees() is\newline
				{Update Managers Add ([fName, lName] where hierarchy = \texttt{"}Manager\texttt{"} in Employees);\newline
				}
			\end{quote}
		Recursive Triggers are allowed without any limit of recursion. It is the responsibility of the programmer to avoid infinite loops. This is another characteristic of Aldat: there are no restrictions to give the programmer the full control of the tools Aldat provides but it is its responsibility to make sure that he uses them right.

		\section{Motivation and notions used in our research}		
		
		\subsection{Motivation}
		
		SQL being the de facto standard query language for databases, an SQL interface was obviously missing from the Aldat and JRelix Project at McGill which have deep insights in the Relational and Domain Algebras. Pretty much any existing system supporting queries would provide an SQL interface to it and the absence of an SQL front-end to this system would definitely lower its popularity despite the advanced capabilities of Aldat. 
		
		The best way to show that Aldat subsumes SQL is by providing an SQL-Aldat translation. Therefore the interface would then just be the translator that would feed the system with the translated statements to execute them. There would be no need to make an interface that would directly deal with the internals of the system as it would be the case if Aldat did not subsumes SQL.
		
		Even an incomplete translator at first, that could be completed in future research, is a proof of concept that Aldat does subsume SQL and can provide a translator as an interface. This challenge was so appealing that the decision was made to start a research focusing on the design and the implementation of an extension to JRelix that would provide an SQL interface to it. It would allow JRelix to be available for several purposes that would not involve directly the learning of Aldat, e.g. being plugged to existing systems with an SQL interface, while being still available for more complex purposes that could be achieved through Aldat.
		
		This research will not cover the whole scope of SQL but would provide a strong basis of the translation between SQL and Aldat that can be extended to have a full coverage of the SQL language in a future work. It has been principally based on the the following key notions described with more details in the following sections and which usage is very common in the Computer Science environment: 
		\begin{itemize}
			\item Context-free grammars and LL parsers
			\item Boolean Logic
			\item Abstract Syntax Trees
		\end{itemize}
		These three sections correspond to the three main steps of the translation : 
		\begin{itemize}
			\item The SQL statements are parsed by the LL parser generated from the SQL context-free grammar
			\item They are further parsed by our own boolean parser using the Boolean Logic
			\item Abstract Syntax Trees are then generated from these statements to translate them in Aldat
		\end{itemize}
		
		\subsection{Context-free grammars and LL parsers}
		
		Context-free grammars, which have been first formalized by  N. Chomsky \cite{Chomsky1},  play a major role in Computer Science because they can describe the design of most of the currently used programming languages and compilers. They can almost always be described by a context free grammar because it allows us to capture the block structure inherent to most programming languages nowadays. The main other advantage of context-free grammars is that parsing algorithms can generally be found or generated rather easily from them. 
		
		LL parsers cannot parse all the context-free grammars but the subset of them whose rules can be applied from \textit{left to right} i.e. using a \textit{leftmost derivation} from the root of the grammar. This is often the case in Computer Science because the programming languages are often written by people used to read and write from left to right. Therefore they can be described by the LL grammars and parsed by the corresponding parsers.  
		
		In the case of our research we used a context-free grammar\cite{antlr2} expressed using the Extended Backus�Naur Form notation (EBNF)\cite{Wirth1} to generate a parser with a meta parser, ANTLR  \cite{antlr1}, which is LL. We choose the ANTLR Metaparser because we could easily find an SQL grammar for it and the parser it generates can also generate ASTs\footnote{See Section \ref{AST1}} after the parsing. JavaCC\cite{javacc1} is another widely used Meta Parser and actually is the one used in JRelix to generate its parser. Nevertheless we could not find a simple SQL grammar for it so we chose ANTLR.  
		
		\subsection{Boolean Logic}
		
		Boolean Logic is one of the most used notions in Computer Science because it allows us to describe computational logic. Its scope goes beyond computers and Boolean Logic is also used in electrical engineering to describe the electronic circuits using the gates as operators. 
		
		It is Boolean Logic which is used in both SQL and Aldat to express the conditions, e.g. to \texttt{"}flag\texttt{"} tuples for a selection. This was a critical notion for us because SQL expresses selection conditions and join conditions in the same clause which is not the case in Aldat and we had to separate them by breaking down the clause into simple elements and recombining each boolean subexpression to express the same statement. This would not have been possible without Boolean Logic. 
		
		Specially considering that the parser simply copies the content of the \textit{Where} clause in the AST, we had to design and implement our own Boolean Parser \footnote{See Section \ref{BooleanParser}} that would further process the ASTs generated by the parser to have the \textit{Where} clause broken down using Boolean Logic to simple boolean expressions. We consider the sufficient set \{AND, OR, NOT\} of operators and used the parentheses to disambiguate the boolean expressions by imposing the evaluation order of the different clauses composing it. 
		
		\subsection{\label{AST1} Abstract Syntax Trees}
		
	\subsubsection{A powerful intermediate form}	
	
		Abstract Syntax Trees (AST) are a very powerful intermediate form between a source code written in a programming language, in our case the SQL statements, and generally the binary code or any other language corresponding to the result of the grammar, in our case the translated Aldat statements. It is often used for optimization purposes because it allows us to keep the structure of the program without being sensitive to the the grammar used to parse it as in the case of a Parse Tree. This is made possible by the Abstract Syntax that specifies the range of possible structures of the language. This Abstract Syntax may be defined using the Abstract Syntax Notation One (ASN.1) \cite{ASN1}. The usefulness of the ASTs have already been recognized \cite{AST2}\cite{AST3}\cite{AST4}. The JRelix implementation actually utilize the ASTs as an intermediate form after the parsing for the interpreter. 
		
		\subsubsection{Tree structure of an AST}
		
		An AST consists of a finite tree where interior nodes are operators of the language and their children the operands. The leaves are then variables or constants used in that statement. So the statement which will be broken down from the root to the leaves capturing its structure in the tree structure. The translation of the statement is then eased by the fact that its structure is already known. 

		\subsubsection{ASTs in the context of our translator}
		
		\begin{itemize}
		\item Ordered Trees \newline
		In the case of our implementation, as it is often the case with ASTs actually, the ASTs generated are ordered. The ordering of these ASTs is important in the sense that the order of the clauses of a statement has to be kept in its intermediate form and is an integral part of the structure of that statement.Therefore it would not have been logical to generate unordered trees. 
		\item Boolean Parser \newline
		In the case of the \textit{Where} clause the AST generated is flat. So we had to develop our own Boolean Parser and we would then generate ASTs with the same structure as the ones generated by the ANTLR parser and replace the flat one by our own. From there we can translate the whole SQL statements using the ASTs. 
\end{itemize}
		\section{General discussion about SQL and Aldat}
		
		\subsection{Quick overview of the main versions of SQL}
		
		\begin{itemize}
			\item \textbf{SQL-86} \cite{sql1986} \newline
			This is the first standardization of SQL adopted by the American National Standards Institute (ANSI) in 1986 and the International Standards Organization (ISO) in 1987. It has been slightly revised and adopted by the U.S. National Institute of Standards and Technology (NIST) in 1989 to become SQL-89 (also known as SQL1 or FIPS 127-1). A conformance testing suite \cite{nist1} to the standard has been provided by NIST to improve the standardization process for the RDBMS vendors.
			\item \textbf{SQL-92 (SQL2)} \cite{sql1992} \newline
			This is the first major revision of the SQL-86 standard. There was a clear effort made to go from SQL-86 with a quite incomplete standardization of the language with an important part of the scope left as \texttt{"}implementor-defined\texttt{"} to a full coverage of the standard. It standardized the ANSI JOIN notation, between many other standardizations, and introduced the levels of compliance to the standard notion. There were three levels of compliance defined in SQL-92 :
			\begin{itemize}
				\item Entry-level conformance  (only the barest improvements to SQL-89)
				\item Intermediate-level conformance (a generally achievable set of major advancements)
				\item Full conformance (total compliance with the SQL-92 features)
			\end{itemize}
			The entry level is also known as FIPS 127-2 and has a conformance testing suite available provided by NIST.
			\item \textbf{SQL-99 (SQL3)} \cite{sql1999} \newline
			This is the second major revision of the SQL-86 standard. It mainly added the following features in the standardization : regular expression matching, recursive queries and triggers. It also standardized the support for procedural and control-of-flow statements with the definition of a standard procedural programming language extension which has been called SQL/Persistent Stored Module (SQL/PSM). The new level of compliance defined are : Core SQL99 and Enhanced SQL99. They are no longer certified by NIST since 1996 but by the vendors themselves.
			\item \textbf{SQL-2003} \cite{sql2003} \newline
			This revision mainly introduced XML and more generally semi-structured data support in SQL. This has been a major awaited improvement \cite{sqlxml2} with the emergence of XML, and other forms of semi-structured data, in the late 1990's as one of the most reliable ways to transfer large amount of data. SQL-2003 standardized \cite{sqlxml1} the mapping between the two languages.
		\end{itemize}		
		
		\subsection{Quick overview of some of the RDBMS most used currently}
		
		\subsubsection{Oracle}
		
		Oracle \cite{oracle1} is a leader among RDBMS vendors. That is one of the reason we chose an Oracle SQL grammar for our research. The main characteristics specific to this vendor that we will deal with in our research are : 
		\begin{itemize}
			\item \textbf{The default column expression name}  \newline
			The expression itself is used as a name. That can be done using quoted identifiers which allows all characters in their composition.
			\item \textbf{The column aliases references} \newline
			The column aliases can not be referred to in the \textit{Where} and \textit{having} clause.
			\item \textbf{Old outer join notation} \newline
			The outer join notation prior to SQL-92 is the following : 
			\begin{quote}
			SELECT X, Y, Z FROM R, S WHERE R.Y = S.Y (+);
			\end{quote}
			\item \textbf{Procedural programming language extension} : Procedural Language/SQL (PL/SQL) \newline
		\end{itemize}		
		
		\subsubsection{MS SQL Server}
		
		Microsoft \cite{MSSQL1} has also an important share of the RDBMS world because of its high compatibility with other Microsoft software that are well spread, e.g. its operating system Windows. The main characteristics specific to this vendor that are relevant to our research are : 
		\begin{itemize}
			\item \textbf{The default column expression name} \newline
			\texttt{"}No Name\texttt{"} is used as a name.
			\item \textbf{The column aliases references} \newline
			The column aliases can not be referred to in the \textit{Where} and \textit{having} clause.
			\item \textbf{Old outer join notation} \newline
			The outer join notation prior to SQL-92 is the following : 
			\begin{quote}
			SELECT X, Y, Z FROM R, S WHERE R.Y *= S.Y ;
			\end{quote}
			\item \textbf{Procedural programming language extension} : Transact-SQL(T-SQL) \newline
		\end{itemize}		
		
		\subsubsection{IBM DB2}
		
		IBM \cite{db21} was the precursor in the research on SQL but has been overtaken by Oracle in its commercial implementation. The main characteristics specific to this vendor that are relevant to our research are : 
		\begin{itemize}
			\item \textbf{The default column expression name} \newline
			The column number is used as a name.
			\item \textbf{The column aliases references} \newline
			The column aliases can not be referred to in the \textit{Where} and \textit{having} clause.
			\item \textbf{Old outer join notation} \newline
			The outer join was not available prior to SQL-92 so it is the only notation available. 
			\item \textbf{Procedural programming language extension} : SQL Procedural Language (SQL PL) \newline
		\end{itemize}		
		
		\subsubsection{MySQL}
		
		MySQL \cite{MySQL1} is one of the most known Open Source RDBMS. The main characteristics specific to this vendor that are relevant to our research are :
		\begin{itemize}
			\item \textbf{The default column expression name} \newline
			The expression itself is used as a name.
			\item \textbf{The column aliases references}  \newline
			The column aliases can not be referred to in the \textit{Where} but can be used in the \textit{having} clause.
			\item \textbf{Old outer join notation} \newline
			The outer join was not available prior to SQL-92 so it is the only notation available. 
			\item \textbf{Procedural programming language extension} : MySQL \newline
		\end{itemize}		
		
		\subsection{SQL-Aldat Comparison}
		
		\subsubsection{Joins}
		
	SQL unlike Aldat can be very ambiguous with joins. It begins the ambiguity directly by using the \textit{where} keyword which is also the same to express a condition. Furthermore some database systems have adopted the ANSI (American National Standards Institute) join keywords (\texttt{"}INNER JOIN\texttt{"}, \texttt{"}OUTER JOIN\texttt{"}, ...), included in SQL-92, only very recently which leaves a certain amount of older systems still running without the ANSI joins. Oracle only adopted the ANSI joins with the version 9. Since our translator is based on Oracle 7 \cite{oracle1} grammar we will not be able to use the ANSI joins. 
	
		\subsubsection{Aggregations}
		
		The aggregations performed in SQL through the aggregation functions are a subset of the domain algebra defined in Aldat which allows us to do as much and even more being more generic. Also the distinction between the \textit{Where} keyword reserved for individual tuples and the \textit{Having} keyword reserved for aggregated tuples in SQL is nonexistent in Aldat in which the condition for aggregated data as much as individual data will be expressed by the \textit{Where} keyword. 
		
		Furthermore the domain algebra allows us to use alias as for aggregated expressions in any part of a statement whereas in SQL for example column aliases can not be used in the \textit{Having} clause because of the evaluation order of the clauses, in particular the \textit{Having} clause is evaluated before the \textit{Select} clause, apart from in MySQL where there is a different evaluation order which allows us to use column aliases in the \textit{Having} clause.
		
		Aldat, having a totally relational design, considers only distinct values. So the default option is the DISTINCT in the aggregation functions. Once again the difference in the design of the the two languages resurfaces. Nevertheless it is possible to express aggregations on duplicates.
		
		\subsubsection{Data Modification}
		
		\begin{itemize}
			\item \textbf{Inserts} \newline
		In SQL inserting tuples is done considering the set of rows to insert whereas in Aldat the relation to insert itself is considered as a whole and added directly. 
			\item \textbf{Updates and Deletions} \newline
		\textit{Updates and Deletions} are expressed in SQL with a condition in the \textit{Where} clause to \texttt{"}flag\texttt{"} the tuples that should be updated or deleted. \textit{Updates} are expressed in Aldat with a join on the relation specified in the \textit{Using} clause to \texttt{"}flag\texttt{"} the tuples that should be updated. Relations in Aldat are considered as a whole whereas in SQL it will rather be individual tuples. This is another design decision which emphasizes this difference between Aldat and SQL. 
		\end{itemize}
		
		\subsubsection{Relation creation and deletion}
		
		In SQL the attributes are bound to the relation incorporating them and so their creation and deletion are linked to those of the relation. Whereas in Aldat the relation only incorporates the attributes in its declaration. The attributes  were created before the relation even existed and will continue to exist even after the deletion of the relation. The only restriction that exists is the deletion of an attribute that is still used in a relation which is forbidden because it would break the structure of that relation. 
		
		A further difference is due once again to the Domain Algebra notion which is absent in SQL and an important part of Aldat conception. SQL only incorporates the Relational Algebra notion and uses functions, e.g. aggregation functions, to deal with operations on attributes that should be performed using the Domain Algebra. 
		
		These differences are part of the overall difference between Aldat and SQL concerning the principles of abstraction and closure \cite{Merrett2}. Aldat respects them whereas SQL does not. The principle of closure stipulates that operations result should conserve the type of the operands, e.g. operations on relations produce relations. And the principle of abstraction stipulates that operations should be independent of the structure of the operands and of their context. Another example of the application of this latter principle is the case of the virtual attribute notion that Aldat integrates and which is absent from SQL. A straight-forward example of the first is the boundless recursive definition of a view that can be done in Aldat and can not in SQL.
		
			\subsubsection{Triggers}
			
		Triggers body have to be written in PL/SQL, \textit{Begin ... End} block, to deal with the programming aspect of triggers which embodies one of the main advantages of Aldat. The language itself have been designed to include both relational and programming aspects of databases. Whereas here we have a difference between the SQL which is intended for and only for the relational aspect and the PL/SQL which adds the programming aspect. One of the main problems of this differentiation apart from the obvious efficiency one and the lack of uniformity is that PL/SQL is an extension to SQL made by Oracle and so it can not be used with other databases such as MS SQL Server for example which uses its own extension T-SQL. So the portability of the code, which was not totally assured because of the differences noted before in the notations, is definitely lost when you introduce the programming side. 
		
	\chapter{User's Manual}	
		  	
		To get started let's first start JRelix in which our translator is integrated eventually. First of all let's open a terminal with a command line. Let's type in the command line relix to launch it :
			\begin{quote}
			\$ \textbf{relix}
			\end{quote}		
			Which will output :
			\begin{quote}
			Starting stand alone JRelix.
			\begin{tabbing}
+------------------------------------------------------\= +\\
\hspace*{.03in}$|$ \hspace*{.39in} Relix Java version 0.96 \> $|$\\
\hspace*{.03in}$|$ Copyright (c) 1997 -- 2007 Aldat Lab \> $|$\\
\hspace*{.03in}$|$ \hspace*{.25in} School of Computer Science \> $|$\\
\hspace*{.03in}$|$ \hspace*{.51in} McGill University \> $|$\\
+------------------------------------------------------\> +\\
$>$
\end{tabbing}
			\end{quote}		
			
		\section{\label{SQLSTMTSection} SQLSTMT command}
		
		\subsection{Selects}
		
		Let's now consider consider simple selects :
		\begin{itemize}
			\item 1 First selecting an attribute from a relation :
			\begin{quote}
			Type in the command line the SQL query that we want to translate: \newline
			$>$ sqlstmt \texttt{"}select a into destRel from b;\texttt{"}; \newline
			Which will execute the corresponding Aldat query : \newline
  		\texttt{destRel$<$- [a] in b;} \newline
			\end{quote}
			We specified the target relation because this is a command so it cannot have a void action. In the section \ref{SQLEXPSection} we will see how to have selections without it.
			
			\item 2 Then selecting a qualified attribute from a relation :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b.a into destRel from b;\texttt{"}; \newline
  		\texttt{destRel$<$- [a] in b;} \newline
			\end{quote}				
			
			\item 3 Then selecting distinct elements of a attribute from a relation :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select distinct a into destRel from b;\texttt{"}; \newline
  		\texttt{destRel$<$- [a] in b;} \newline
			\end{quote}
				Aldat is totally relational so the tuples returned are always distinct.
			\item 4 Then selecting all attributes from a relation :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select * into destRel from b;\texttt{"}; \newline
  		\texttt{destRel$<$- b;} \newline
			\end{quote}
			
			\item 5 Now selecting attributes from a subquery with a where condition :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select a, b into destRel from (select a,b,c from d where (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}) or g=2);\texttt{"}; \newline
			\texttt{destRel$<$- [a,b] in ([a,b,c] where (e=1 and f=\texttt{"}a\texttt{"}) or g=2 in d);} \newline
			\end{quote}
				
			\item 6 Then selecting expression from a relation :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select a + b into destRel from c;\texttt{"}; \newline  		
			\texttt{let No\_Name be a+b;} \newline
			\texttt{destRel$<$- [No\_Name] in c;} \newline
			\end{quote}
			We took the same naming convention as MS SQL Server concerning expressions without alias i.e. using \textit{No Name}. Oracle and MySQL uses the expression itself, DB2 uses the column number.
			
			\item 7 Then selecting attribute with an alias from a relation :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select a as b into destRel from c;\texttt{"}; \newline  		
			\texttt{let b be a;} \newline
			\texttt{destRel$<$- [b] in c;} \newline
			\end{quote}
			
			\item 8 Then selecting attribute with an alias without the keyword \textit{as} from a relation :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select a b into destRel from c;\texttt{"}; \newline  		
			\texttt{let b be a;} \newline
			\texttt{destRel$<$- [b] in c;} \newline
			\end{quote}
			
			\item 9 Then selecting attributes from a query with a \textit{LIKE} condition :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select a into destRel from b where c like \mbox{\texttt{\char"0D}\%OMPUTE\%\texttt{\char"0D}};\texttt{"}; \newline  		
			\texttt{destRel$<$- [a] where att = \texttt{"}c\texttt{"} in (grep(att) \texttt{"}ompute\texttt{"} in b);} \newline
			\end{quote}
			
			\item 10 Then selecting attributes from a query with a condition involving an expression:
			\begin{quote}
			$>$ sqlstmt \texttt{"}select a into destRel from b where c + d = 1;\texttt{"}; \newline  		
			\texttt{destRel$<$- [a] where c+d=1 in b;} \newline
			\end{quote}
			
		\end{itemize}
		
		\subsection{Joins}
		
		\subsubsection{\label{IjoinExample} Inner Joins and Difference Join}
		
		Now we can get to more complex selects implying joins :
		\begin{itemize}
			\item 11 First the most straightforward select with join on one attribute :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:a]d);} \newline
			\end{quote}
						
			\item 12 Now select with join on several attributes :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a and c.e = d.e and c.f = d.g;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a,e,f:ijoin:a,e,g]d);} \newline
			\end{quote}
						
			\item 13 Now select with a difference join on several attributes :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a and not(c.e = d.e and c.f = d.g);\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:a]d) djoin (c[e,f:ijoin:e,g]d);} \newline
			\end{quote}
						
			\item 14 Now select with a join and a condition on several attributes :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a and e=1 and f=\texttt{\char"0D}a\texttt{\char"0D};\texttt{"}; \newline
			\texttt{destRel$<$- [b] where e=1 and f=\texttt{"}a\texttt{"} in (c[a:ijoin:a]d);} \newline
			\end{quote}
						
		\end{itemize}
		
		\subsubsection{Left Outer Join, Right Outer Join and Full Outer Join}
		
		We can then get to more subtle joins :
		\begin{itemize}
			\item 15 First a simple right outer join :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a (+) = d.a;\texttt{"}; \newline
  		\texttt{destRel$<$- [b] in (c[a:rjoin:a]d);} \newline
			\end{quote}
			The \texttt{"}(+)\texttt{"} allows nulls on the left side of the join so that makes it a right outer join.
			\item 16 The corresponding left outer join :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a (+);\texttt{"}; \newline
  		\texttt{destRel$<$- [b] in (c[a:ljoin:a]d);} \newline
			\end{quote}
						
			\item 17 Now a little variant not allowed in Oracle SQL but that we allow to ease full outer joins expression :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a (+) = d.a (+);\texttt{"}; \newline
  		\texttt{destRel$<$- [b] in (c[a:ujoin:a]d);} \newline
			\end{quote}
						
			\item 18 Now a left outer join on several attributes :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a (+) and c.e = d.e (+);\texttt{"}; \newline
  		\texttt{destRel$<$- [b] in (c[a,e:ljoin:a,e]d);} \newline
			\end{quote}
								
			\item 19 Now  select with 2 different joins on several attributes :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a (+) and c.e = d.e;\texttt{"}; \newline
  		\texttt{destRel$<$- [b] in (c[a:ljoin:a]d) ijoin (c[e:ijoin:e]d);} \newline
			\end{quote}
		
			\item 20 Now select with the 3 different joins on several attributes :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a (+) and c.e = d.e and c.f (+) = d.g;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ljoin:a]d) ijoin (c[e:ijoin:e]d) ijoin (c[f:rjoin:g]d);} \newline
			\end{quote}
						
			\item 21 Now select with 1 inner join and 2 left outer joins on several attributes :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a and c.e = d.e (+) and c.f  = d.g (+);\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:a]d) ijoin (c[e,f:ljoin:e,g]d);} \newline
			\end{quote}
						
			\item 22 Now select with 1 inner join or 2 left outer joins on several attributes :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a or c.e = d.e (+) and c.f  = d.g (+);\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:a]d) ujoin (c[e,f:ljoin:e,g]d);} \newline
			\end{quote}
						
		\end{itemize}						
						
		\subsubsection{Joins with unqualified attributes or none}
		
		It is possible to use joins using the unqualified names of the attributes. The system will be able to differentiate them. For example if we consider a relation c with the attributes a,b and f and a relation d with the attribute e and no shared attributes between the 2 relations. We will have the following:
				
			\begin{quote}
			23 $>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = c.f;\texttt{"}; \newline
			\texttt{destRel$<$- [b] where a=f in (c ijoin d);} \newline
			\end{quote}
			
		With the same output as :
		
			\begin{quote}
			24 $>$ sqlstmt \texttt{"}select b into destRel from c, d where a = f;\texttt{"}; \newline
			\texttt{destRel$<$- [b] where a=f in (c ijoin d);} \newline
			\end{quote}
			
		and :
		
			\begin{quote}
			25 $>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.e;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:e]d);} \newline
			\end{quote}
			
		With the same output as :
		
			\begin{quote}
			26 $>$ sqlstmt \texttt{"}select b into destRel from c, d where a = e;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:e]d);} \newline
			\end{quote}
		and if no attribute is specified we have the cartesian product :
		
			\begin{quote}
			27 $>$ sqlstmt \texttt{"}select b into destRel from c, d;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c ijoin d);} \newline
			\end{quote}
			
		\subsection{Aggregations}
		
		Aggregations are an important way to summarize data. They can be used the following way :
		\begin{itemize}
			\item 28 First a simple sum without alias :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select sum(salary) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red + of salary;} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\end{quote}
					
			\item 29 Then a simple distinct sum without alias :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select sum(distinct salary) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red max of (fun + of salary order salary);} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\end{quote}
					
			\item 30 Then a simple avg without alias :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select avg(salary) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red + of salary / red + of 1;} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\end{quote}
					
			\item 31 Then a simple max without alias :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select max(salary) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red max of salary;} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\end{quote}
					
			\item 32 Then a simple min without alias :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select min(salary) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red min of salary;} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\end{quote}
					
			\item 33 Then a simple count without alias :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select count(*) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red + of 1;} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\end{quote}
					
			\item 34 Then another simple count without alias :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select count(salary) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red + of (if isnull(salary) then 0 else 1);} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\end{quote}
			As usual in SQL the number of tuples having a non NULL value of the column.
			
			\item 35 Now a simple distinct count without alias :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select count(distinct salary) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red max of fun + of 1 order (salary);} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\end{quote}
					
			\item 36 Now a more complex sum involving an alias, a group by and a having condition :
			\begin{quote}
			$>$ sqlstmt \texttt{"}select sum(salary) S into destRel from employees group by dept having S $>$ 10;\texttt{"}; \newline
  		\texttt{let S be equiv + of salary by dept;} \newline
  		\texttt{destRel$<$- [S] where S $>$ 10 in salary;} \newline
			\end{quote}
			As in MySQL we allow the column aliases to be used in the GROUP BY clause.
		\end{itemize}
		
		\subsection{Delete}
		
		Deletions can be expressed the following way :
		\begin{itemize}
					\item 37 A delete without a condition :
			\begin{quote}
			$>$ sqlstmt \texttt{"}delete from b;\texttt{"}; \newline
  		\texttt{update b delete b;} \newline
			\end{quote}
			
					\item 38 A delete with a condition :
			\begin{quote}
			$>$ sqlstmt \texttt{"}delete from b where a = 1;\texttt{"}; \newline
  		\texttt{update b delete where a = 1 in b;} \newline
			\end{quote}
			
		\end{itemize}
		
		\subsection{Update}
		
		Updates are also supported :
		\begin{itemize}
					\item 39 Updating a attribute with a condition on another :
			\begin{quote}
			$>$ sqlstmt \texttt{"}update a set b = 10 where c = 2;\texttt{"}; \newline
  		\texttt{update a change b $<$- if c = 2 then 10 else b;} \newline
			\end{quote}
						
		\end{itemize}
		
		\subsection{Multiple statements}
		
		It is also possible to write several statements at once :
			\begin{quote}
			$>$ sqlstmt \texttt{"}delete from b where a = 1;\newline
			select b into destRel from c, d where c.a = d.a or c.e = d.e (+) and c.f  = d.g (+);\newline
			update a set b = 10 where c = 2;\texttt{"}; \newline
			
  		\texttt{update b delete where a = 1 in b;} \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:a]d) ujoin (c[e,f:ljoin:e,g]d);} \newline
  		\texttt{update a change b $<$- if c = 2 then 10 else b;} \newline
			\end{quote}
			
		\subsection{Omissions}
		
		In the current version of the tool we do not support all the commands of SQL because the parser we chose does not support the full SQL grammar. The most important omissions are listed below:
		\begin{itemize}
					\item The create command : table, view, trigger, ... etc
					\item The drop command
					\item The insert command
		\end{itemize}
				
				
		\section{\label{SQLEXPSection} SQLEXP keyword}
		
		We added the SQLEXP keyword to be able to use SQL relational expression in enclosing Aldat statements. Any Aldat statement using relational expression can use it. 
		
		\subsection{Selects}
		
		Let's now consider Aldat statements involving the SQLEXP keyword:
		\begin{itemize}
			\item 1 printing a SQL relational expression:
			\begin{quote}
			$>$ pr sqlexp \texttt{"}select a from b;\texttt{"}; \newline
			Which will execute Aldat query : \newline
  		\texttt{pr ([a] in b);} \newline
			\end{quote}
			\item 1' Assigning a join between an existing relation and a SQL relational expression:
			\begin{quote}
			$>$ d$<$- c ijoin sqlexp \texttt{"}select a from b;\texttt{"}; \newline
			Which will execute Aldat query : \newline
  		\texttt{d$<$- c ijoin ([a] in b);} \newline
			\end{quote}
			\item 1'' Printing a projection of a SQL relational expression:
			\begin{quote}
			$>$ pr [a] in (sqlexp \texttt{"}select a, c from b;\texttt{"}); \newline
			Which will execute Aldat query : \newline
  		\texttt{pr [a] in ([a, c] in b);} \newline
			\end{quote}
		\end{itemize}
			For the ease of examples we will consider printing statements from now on. All the SQL selection statements from section \ref{SQLSTMTSection} are supported. We will limit our examples to the most important ones. The examples follow the same numbering as in the section before.
		\begin{itemize}
			
			\item 5 Now selecting attribute from a subquery with a where condition :
			\begin{quote}
			$>$ pr sqlexp \texttt{"}select a, b from (select a,b,c from d where (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}) or g=2);\texttt{"}; \newline
			\texttt{pr [a,b] in ([a,b,c] where (e=1 and f=\texttt{"}a\texttt{"}) or g=2 in d);} \newline
			\end{quote}
			
		\end{itemize}
		
		\subsection{Joins}
		
		\subsubsection{Inner Joins and Difference Join}
		
		Now we can get to more complex selects implying joins :
		\begin{itemize}
						
			\item 14 Now select with a join and a condition on several attributes :
			\begin{quote}
			$>$ pr sqlexp \texttt{"}select b from c, d where c.a = d.a and e=1 and f=\texttt{\char"0D}a\texttt{\char"0D};\texttt{"}; \newline
			\texttt{pr [b] where e=1 and f=\texttt{"}a\texttt{"} in (c[a:ijoin:a]d);} \newline
			\end{quote}
						
		\end{itemize}
		
		\subsubsection{Left Outer Join, Right Outer Join and Full Outer Join}
		
		We can then get to more subtle joins :
		\begin{itemize}
			
			\item 20 Now select with the 3 different joins on several attributes :
			\begin{quote}
			$>$ pr sqlexp \texttt{"}select b from c, d where c.a = d.a (+) and c.e = d.e and c.f (+) = d.g;\texttt{"}; \newline
			\texttt{pr [b] in (c[a:ljoin:a]d) ijoin (c[e:ijoin:e]d) ijoin (c[f:rjoin:g]d);} \newline
			\end{quote}
						
		\end{itemize}
										
		\subsubsection{Joins with unqualified attributes or none}
		
		It is possible to use joins using the unqualified names of the attributes. The system will be able to differentiate them. For example if we consider a relation c with the attributes a,b and f and a relation d with the attribute e we will have the following:
				
			\begin{quote}
			25 $>$ pr sqlexp \texttt{"}select b into destRel from c, d where c.a = d.e;\texttt{"}; \newline
			\texttt{pr [b] in (c[a:ijoin:e]d);} \newline
			\end{quote}
			
		With the same output as :
		
			\begin{quote}
			26 $>$ pr sqlexp \texttt{"}select b into destRel from c, d where a = e;\texttt{"}; \newline
			\texttt{pr [b] in (c[a:ijoin:e]d);} \newline
			\end{quote}
			
		\subsection{Aggregations}
		
		Aggregations are an important way to summarize data. They can be used the following way :
		\begin{itemize}
			
			\item 36 Now a more complex sum involving an alias, a group by and a having condition :
			\begin{quote}
			$>$ pr sqlexp \texttt{"}select sum(salary) S from employees group by dept having S $>$ 10;\texttt{"}; \newline
  		\texttt{let S be equiv + of salary by dept;} \newline
  		\texttt{pr [S] where S $>$ 10 in salary;} \newline
			\end{quote}
			
		\end{itemize}
		
		\subsection{Multiple statements}
		
		It is also possible to write several statements at once :
			\begin{quote}
			$>$ pr sqlexp \texttt{"}delete from b where a = 1;\newline
			select b from c, d where c.a = d.a and e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}; \newline
			select b from c, d where c.a = d.a or c.e = d.e (+) and c.f  = d.g (+);\newline
			update a set b = 10 where c = 2;\texttt{"}; \newline
  		\texttt{update b delete where a = 1 in b;} \newline
  		\texttt{update a change b $<$- if c = 2 then 10 else b;} \newline
			\texttt{pr [b] in (c[a:ijoin:a]d) ujoin (c[e,f:ljoin:e,g]d);} \newline
			\end{quote}
			The first select will be ignored because only the last one will be returned.
			
		\section{FILE Keyword}
		
		In both previous sections the SQL statements were directly written as the string parameter of the command. It is possible as with the \textit{input} keyword in JRelix to specify a location on the disk to a file containing several statements to execute. The extra parameter using the file keyword allows the translator to know that the string transferred by the interpreter is not directly the SQL to translate but the path to the file where the SQL statements are. So the file is read from disk and from there the mechanism is the same as before for both SQLEXP and SQLSTMT.
		let consider a file named \textit{\texttt{\char"0D}example.sql\texttt{\char"0D}} containing the following text in the current directory:
  	\begin{quote}
			\textbf{select a into destRel from b;}
		\end{quote}
		
		We will have for the following run using the the SQLSTMT command with the FILE extra parameter :
		 
  	\begin{quote}
			\item 1 $>$ sqlstmt file \texttt{"}example.sql\texttt{"};
		\end{quote}
  	The output corresponding :
  	\begin{quote}
  		\texttt{destRel$<$- [a] in b};
		\end{quote}
		
		And if we consider a file named \textit{\texttt{\char"0D}example2.sql\texttt{\char"0D}} containing the following text in the current directory:
  	\begin{quote}
			\textbf{select a from b;}
		\end{quote}
		
		We will have for the following run using the the SQLEXP keyword with the FILE extra parameter :
		 
  	\begin{quote}
			\item 2 $>$ pr sqlexp file \texttt{"}example2.sql\texttt{"};
		\end{quote}
  	The output corresponding :
  	\begin{quote}
  		\texttt{pr [a] in b};
		\end{quote}
		
  \chapter{Implementation details}
  
  \section{SQLSTMT Command}
  
		\subsection{Selections}
		
		\subsubsection{Selects}
		
		Let's consider the first of the series of runs in the previous chapter to have an idea of what is occurring in the implementation :
		
  	\begin{quote}
			\item 1 $>$ sqlstmt \texttt{"}select a into destRel from b;\texttt{"};
		\end{quote}
  	The output will be :
  	\begin{quote}
  		\texttt{destRel$<$- [a] in b};
		\end{quote}
		To achieve this output we can succinctly describe what is occurring in the following way :
		\begin{itemize}
			\item First of all the input stream is redirected from the String transmitted to the translator by the JRelix system, then the lexer and the parser are invoked. The rules of the grammar are processed, the tokens recognized and finally we obtain the Abstract Syntax Tree (AST) corresponding to our SQL statement.
  		\item Then we visit recursively each of the subtrees corresponding to a statement and store the result in a String before returning it to the JRelix system for further processing.
  	\end{itemize}
  	
		To be more detailed for this run we have the following execution :
		\begin{itemize}
			\item 1 $>$ sqlstmt \texttt{"}select a into destRel from b;\texttt{"}; \newline
  		\texttt{destRel$<$- [a] in b}; \newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree1.latex}}
						\caption{AST \textit{select a into destRel from b;}}
						\label{figure:AST1}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes[a] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(4) : Include relations b\newline
			(5) : Add target relation name [destRel] to the final translated statement\newline
			(6) : End of statement \newline
		\end{itemize}
		In the step 1 above the target relation name is removed from the SQL to translate, stored aside and gets pasted only at step 6. This is because the \textit{into} keyword is absent from our current grammar. Nevertheless we managed to find a workaround to be able to use it in this case (what we have not been able to do in a reasonable timeframe for the other omissions). So we intercept the SQL to translate before sending it to the parser to retrieve the target relation name, remove the into clause from the SQL and paste at the end to the translated SQL the target relation name. 
		
			Using the same logic we have for the following runs : 
		\begin{itemize}
			\item 2 $>$ sqlstmt \texttt{"}select b.a into destRel from b;\texttt{"}; \newline
  		\texttt{destRel$<$- [a] in b}; \newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree15.latex}}
						\caption{AST \textit{select b.a into destRel from b;}}
						\label{figure:AST2}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize qualified name [b.a] and erase the relational part [b.] \newline
			(3) : Recognize \textit{select} and include attributes[a] \newline
			(4) : Recognize \textit{from} and check presence of \textit{where} \newline
			(5) : Include relations b\newline
			(6) : Add target relation name [destRel] to the final translated statement\newline
			(7) : End of statement \newline
						
			\item 5 $>$ sqlstmt \texttt{"}select a, b into destRel from (select a,b,c from d (where e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}) or g=2);\texttt{"}; \newline
			\texttt{destRel$<$- [a,b] in ([a,b,c] where (e=1 and f=\texttt{"}a\texttt{"}) or g=2 in d);} \newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.4}{\input{tree2.latex}}
						\caption{AST \textit{select a, b into destRel from (select a,b,c from d where (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}) or g=2);}}
						\label{figure:AST5}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [a,b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(4) : Recognize subquery \newline
			(5) : Recognize \textit{select} and include attributes [a,b,c] \newline
			(6) : Recognize \textit{from} and check presence of \textit{where} \newline
			(7) : Process \textit{where} before \textit{from} and check presence of join \newline
			(8) : Include conditions (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D} or g=2)\newline
			(9) : Include relations d\newline
			(10) : End of subquery \newline
			(11) : Add target relation name [destRel] to the final translated statement\newline
			(12) : End of statement \newline
			
			\item 6 $>$ sqlstmt \texttt{"}select a + b into destRel from c;\texttt{"}; \newline  		
			\texttt{let No\_Name be a+b;} \newline
			\texttt{destRel$<$- [No\_Name] in c;} \newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree17.latex}}
						\caption{AST \textit{select a + b into destRel from c;}}
						\label{figure:AST6}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} \newline
			(3) : Recognize expression [a + b] without an alias \newline
			(4) : Recognize \textit{from} and check presence of \textit{where} \newline
			(5) : Include relations c\newline
			(6) : Add domain algebra corresponding to the expression with the default alias\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
			
			\item 7 $>$ sqlstmt \texttt{"}select a as b into destRel from c;\texttt{"}; \newline  		
			\texttt{let b be a;} \newline
			\texttt{destRel$<$- [b] in c;} \newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree18.latex}}
						\caption{AST \textit{select a as b into destRel from c;}}
						\label{figure:AST7}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} \newline
			(3) : Recognize aliasing [a as b]\newline
			(4) : Recognize \textit{from} and check presence of \textit{where} \newline
			(5) : Include relations c\newline
			(6) : Add renaming for the alias\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
			
			\item 9 $>$ sqlstmt \texttt{"}select a into destRel from b where c like \mbox{\texttt{\char"0D}\%OMPUTE\%\texttt{\char"0D}};\texttt{"};\newline  		
			\texttt{destRel$<$- [a] where att = \texttt{"}c\texttt{"} in (grep(att) \texttt{"}ompute\texttt{"} in b);} \newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree20.latex}}
						\caption{AST \textit{select a into destRel from b where c like \mbox{\texttt{\char"0D}\%OMPUTE\%\texttt{\char"0D}};}}
						\label{figure:AST9}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [a] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(4) : Process \textit{where} before \textit{from} and check presence of join \newline
			(2) : Recognize \textit{like} condition (c like \mbox{\texttt{\char"0D}\%OMPUTE\%\texttt{\char"0D}}) and generate corresponding \textit{grep} condition\newline
			(6) : Include grep condition\newline
			(7) : Include relations b\newline
			(8) : Add target relation name [destRel] to the final translated statement\newline
			(9) : End of statement \newline
			
			\item 10 $>$ sqlstmt \texttt{"}select a into destRel from b where c + d = 1;\texttt{"}; \newline  		
			\texttt{destRel$<$- [a] where c+d=1 in b;} \newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree21.latex}}
						\caption{AST \textit{select a into destRel from b where c + d = 1;}}
						\label{figure:AST10}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [a,b,c] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(4) : Process \textit{where} before \textit{from} and check presence of join \newline
			(5) : Include conditions (c + d = 1)\newline
			(6) : Include relations b\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
			
		\end{itemize}
		
		\subsection{Joins}
		
		\subsubsection{IJoins}
		
		Let's continue with a runs involving a join :
		\begin{itemize}
			\item 11 $>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:a]d);} \newline
			\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree3.latex}}
						\caption{AST \textit{select b into destRel from c, d where c.a = d.a;}}
						\label{figure:AST11}
					\end{center}
				\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(Discarded) : Discard \textit{from} processing because of the join \newline
			(5) : Process \textit{where} before \textit{from} and check presence of join \newline
			(6) : Process  join and determine type of join on [a] attribute\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
		\end{itemize}
					
		To detect the presence of a join (step 5 above) we first try to detect a selection in the \textit{where} and if it is not a selection then we have a join. To do that we make it in 5 steps:
		\begin{itemize}
			\item 1 First we count the number of relations involved in the \textit{from} clause. If we have only one relation no need to go any further. There will be no join. This is done only once.
			\item 2 Then we break down the \textit{where} clause to each single condition.
			\item 3 For each of these condition we look for the presence of a \textit{literal} which means that it is a selection because joins involve only identifiers.
			\item 4 Finally on each of these conditions we test to see if the condition does not involve the same relation in which case it will again be a selection.
			\item 5 If any of these steps turns out to prove that it is not a selection then we have a join. 
			\item 6 If we have a join we determine the type of the join and if we can compress it with the joins already processed, e.g. join on several attributes. We keep looping from 3 to 6 until the \textit{where} clause is totally checked.
		\end{itemize}
		
		The following runs follow the same logic : 
		\begin{itemize}
			\item 12 $>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a and c.e = d.e and c.f = d.g;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a,e,f:ijoin:a,e,g]d);} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.4}{\input{tree4.latex}}
					\caption{AST \textit{select b into destRel from c, d where c.a = d.a and c.e = d.e and c.f = d.g;}}
					\label{figure:AST12}
				\end{center}
			\end{figure}			
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(Discarded) : Discard \textit{from} processing because of the join \newline
			(5) : Process \textit{where} before \textit{from} and check presence of join \newline
			(6) : Process  join and determine type of join on [a, e, f, g] attributes\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline			
						
		\end{itemize}
		
		
		\subsubsection{LJoin, RJoin and UJoin}
		
		\begin{itemize}
			\item 15 $>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a (+) = d.a;\texttt{"}; \newline
  		\texttt{destRel$<$- [b] in (c[a:rjoin:a]d);} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree5.latex}}
					\caption{AST \textit{select b into destRel from c, d where c.a (+) = d.a;}}
					\label{figure:AST5}
				\end{center}
			\end{figure}
					
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(Discarded) : Discard \textit{from} processing because of the join \newline
			(5) : Process \textit{where} before \textit{from} and check presence of join \newline
			(6) : Process  join and determine type of join on [a] attribute\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
													
			\item 20 $>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.a and c.e (+) = d.e and c.f = d.g (+);\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:a]d) ijoin (c[e:rjoin:e]d) ijoin (c[f:ljoin:g]d);} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree25.latex}}
					\caption{AST \textit{select b into destRel from c, d where c.a = d.a and c.e (+) = d.e and c.f = d.g (+);}}
					\label{figure:AST20}
				\end{center}
			\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(Discarded) : Discard \textit{from} processing because of the join \newline
			(5) : Process \textit{where} before \textit{from} and check presence of join \newline
			(6) : Process joins and determine type of different joins on [a, e, f, g] attributes\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
									
		\end{itemize}
						
		\subsubsection{Joins with unqualified attributes or none}
		
		It is possible to use joins using the unqualified names of the attributes. The system will be able to differentiate them. In order to achieve that we have to retrieve a reference to the RD relation currently in RAM for JRelix system any time a call to our translator is made. With that reference we will be able to disambiguate each attribute with an unqualified name. 
		
		For example let's consider a relation c with the attributes a,b and f and a relation d with the attribute e and let's make the following runs:
		
		\begin{itemize}
			\item 23 $>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = c.f;\texttt{"}; \newline
			\texttt{destRel$<$- [b] where a=f in (c ujoin d);} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree28.latex}}
					\caption{AST \textit{select b into destRel from c, d where c.a = c.f;}}
					\label{figure:AST23}
				\end{center}
			\end{figure}			
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(Discarded) : Discard \textit{from} processing because of the join \newline
			(5) : Process \textit{where} before \textit{from} and check presence of join \newline
			(6) : Include conditions (a=f)\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
			
			\item 24 $>$ sqlstmt \texttt{"}select b into destRel from c, d where a = f;\texttt{"}; \newline
			\texttt{destRel$<$- [b] where a=f in (c ujoin d);} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree30.latex}}
					\caption{AST \textit{select b into destRel from c, d where a = f;}}
					\label{figure:AST24}
				\end{center}
			\end{figure}			
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(Discarded) : Discard \textit{from} processing because of the join \newline
			(5) : Process \textit{where} before \textit{from} and check presence of join using the RD relation\newline
			(6) : Include conditions (a=f)\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
			
			\item 25 $>$ sqlstmt \texttt{"}select b into destRel from c, d where c.a = d.e;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:e]d);} \newline
			\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree29.latex}}
						\caption{AST \textit{select b into destRel from c, d where c.a = d.e;}}
						\label{figure:AST25}
					\end{center}
				\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(Discarded) : Discard \textit{from} processing because of the join \newline
			(5) : Process \textit{where} before \textit{from} and check presence of join \newline
			(6) : Process  join and determine type of join on [a] attribute\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
			
			\item 26 $>$ sqlstmt \texttt{"}select b into destRel from c, d where a = e;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c[a:ijoin:e]d);} \newline
			\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree31.latex}}
						\caption{AST \textit{select b into destRel from c, d where a = e;}}
						\label{figure:AST26}
					\end{center}
				\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(Discarded) : Discard \textit{from} processing because of the join \newline
			(5) : Process \textit{where} before \textit{from} and check presence of join  using the RD relation\newline
			(6) : Process  join and determine type of join on [a] attribute\newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
			
			\item 27 $>$ sqlstmt \texttt{"}select b into destRel from c, d;\texttt{"}; \newline
			\texttt{destRel$<$- [b] in (c ujoin d);} \newline
			\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree32.latex}}
						\caption{AST \textit{select b into destRel from c, d;}}
						\label{figure:AST27}
					\end{center}
				\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes [b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(4) : Process \textit{from} and determine the cartesian product\newline
			(5) : Add target relation name [destRel] to the final translated statement\newline
			(6) : End of statement \newline
			
		\end{itemize}
		
		\subsection{Aggregations}
		
		\begin{itemize}
			\item 28 $>$ sqlstmt \texttt{"}select sum(salary) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red + of salary;} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree9.latex}}
					\caption{AST \textit{select sum(salary) into destRel from employees;}}
					\label{figure:AST28}
				\end{center}
			\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and recognize \textit{aggregation function} \newline
			(3) : Check presence of \textit{alias} and \textit{group by} \newline
			(4) : Process \textit{aggregation function} and include attributes [salary] \newline
			(5) : Recognize \textit{from} and check presence of \textit{where} \newline
			(6) : Process \textit{from} and include relation employees \newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
					
			\item 29 $>$ sqlstmt \texttt{"}select sum(distinct salary) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red max of (fun + of salary order salary);} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree33.latex}}
					\caption{AST \textit{select sum(distinct salary) into destRel from employees;}}
					\label{figure:AST29}
				\end{center}
			\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and recognize \textit{aggregation function} \newline
			(3) : Check presence of \textit{alias} and \textit{group by} \newline
			(4) : Process \textit{aggregation function} and include attributes [salary] \newline
			(5) : Recognize \textit{from} and check presence of \textit{where} \newline
			(6) : Process \textit{from} and include relation employees \newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
										
			\item 33 $>$ sqlstmt \texttt{"}select count(*) into destRel from employees;\texttt{"}; \newline
  		\texttt{let No\_Name be red + of 1;} \newline
  		\texttt{destRel$<$- [No\_Name] in employees);} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree37.latex}}
					\caption{AST \textit{select count(*) into destRel from employees;}}
					\label{figure:AST33}
				\end{center}
			\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and recognize \textit{aggregation function} \newline
			(3) : Check presence of \textit{alias} and \textit{group by} \newline
			(4) : Process \textit{aggregation function} \newline
			(5) : Recognize \textit{from} and check presence of \textit{where} \newline
			(6) : Process \textit{from} and include relation employees \newline
			(7) : Add target relation name [destRel] to the final translated statement\newline
			(8) : End of statement \newline
		
			\item 36 $>$ sqlstmt \texttt{"}select sum(salary) S into destRel from employees group by dept having S $>$ 10;\texttt{"}; \newline
  		\texttt{let S be equiv + of salary by dept;} \newline
  		\texttt{destRel$<$- [S] where S $>$ 10 in salary;} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree10.latex}}
					\caption{AST \textit{select sum(salary) S into destRel from employees group by dept having S $>$ 10;}}
					\label{figure:AST36}
				\end{center}
			\end{figure}
		
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and recognize \textit{aggregation function} \newline
			(3) : Check presence of \textit{alias} and \textit{group by} \newline
			(4) : Process \textit{aggregation function} and include attributes [salary] \newline
			(5) : Recognize \textit{from} and check presence of \textit{where} \newline
			(6) : Process \textit{from} and include relation employees \newline
			(7) : Process \textit{having} and include conditions \newline
			(8) : Add target relation name [destRel] to the final translated statement\newline
			(9) : End of statement \newline
			
		\end{itemize}
		
		\subsection{Delete}
		
		\begin{itemize}
			\item 37 $>$ sqlstmt \texttt{"}delete from b;\texttt{"}; \newline
  		\texttt{update b delete b;} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree38.latex}}
					\caption{AST \textit{delete from b;}}
					\label{figure:AST37}
				\end{center}
			\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{delete} and include relation b \newline
			(2) : Process \textit{delete}\newline
			(3) : End of statement \newline
			
			\item 38 $>$ sqlstmt \texttt{"}delete from b where a = 1;\texttt{"}; \newline
  		\texttt{update b delete where a = 1 in b;} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree11.latex}}
					\caption{AST \textit{delete from b where a = 1;}}
					\label{figure:AST38}
				\end{center}
			\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{delete} and include relation b \newline
			(2) : Recognize \textit{where} and the condition \newline
			(3) : Process \textit{delete}\newline
			(4) : End of statement \newline
			
		\end{itemize}
		
		\subsection{Update}
		
		\begin{itemize}
			\item 39 $>$ sqlstmt \texttt{"}update a set b = 10 where c = 2;\texttt{"}; \newline
  		\texttt{update a change b $<$- if c = 2 then 10 else b end;} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree12.latex}}
					\caption{AST \textit{update a set b = 10 where c = 2;}}
					\label{figure:AST39}
				\end{center}
			\end{figure}
			
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{update} and include relation a \newline
			(2) : Recognize \textit{set} and include attribute [b]  \newline
			(3) : Recognize \textit{where} and the condition \newline
			(4) : Process \textit{update}\newline
			(5) : End of statement \newline
			
		\end{itemize}
		
		\subsection{Insert}
		The insert command has not been added to the grammar we are using. It then can not be parsed and so it is not supported in the current version of the software. Nevertheless we can easily write the translator.
		
		\begin{itemize}
			\item 40 $>$ sqlstmt \texttt{"}insert into employees values(\texttt{\char"0D}Gerard\texttt{\char"0D}, \texttt{\char"0D}Tremblay\texttt{\char"0D}, 30, \texttt{\char"0D}Analyst\texttt{\char"0D});\texttt{"}; \newline
  		\texttt{update employees add \{(\texttt{"}Gerard\texttt{"}, \texttt{"}Tremblay\texttt{"}, 30, \texttt{"}Analyst\texttt{"})\};} \newline
			\begin{figure}[htbp]
				\begin{center}
					\scalebox{0.5}{\input{tree13.latex}}
					\caption{AST \textit{insert into employees values(\texttt{\char"0D}Gerard\texttt{\char"0D}, \texttt{\char"0D}Tremblay\texttt{\char"0D}, 30, \texttt{\char"0D}Analyst\texttt{\char"0D});}}
					\label{figure:AST40}
				\end{center}
			\end{figure}
		
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{insert} and include relation employees \newline
			(2) : Recognize \textit{values} and the data to input \newline
			(3) : Process \textit{values}\newline
			(4) : End of statement \newline
			
		\end{itemize}
		
		
		\subsection{General algorithm}
		
		Let's consider these 5 algorithms cited in the section above :		
		
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} and store target relation name [destRel] \newline
			(2) : Recognize \textit{select} and include attributes[a] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(4) : Include relations b\newline
			(5) : Add target relation name [destRel] to the final translated statement\newline
			(6) : End of statement \newline
			
				\textbf{Algorithm :} \newline
			(1') : Recognize \textit{into} and store target relation name [destRel] \newline
			(2') : Recognize \textit{select} and include attributes [b] \newline
			(3') : Recognize \textit{from} and check presence of \textit{where} \newline
			(4' Discarded) : Discard \textit{from} processing because of the join \newline
			(5') : Process \textit{where} before \textit{from} and check presence of join \newline
			(6') : Process join and determine type of join on [a] attribute\newline
			(7') : Include conditions (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D})\newline
			(8') : Add target relation name [destRel] to the final translated statement\newline
			(9') : End of statement \newline
		
				\textbf{Algorithm :} \newline
			(1'') : Recognize \textit{into} and store target relation name [destRel] \newline
			(2'') : Recognize \textit{select} and recognize \textit{aggregation function} \newline
			(3'') : Check presence of \textit{alias} and \textit{group by} \newline
			(4'') : Process \textit{aggregation function} and include attributes [salary] \newline
			(5'') : Recognize \textit{from} and check presence of \textit{where} \newline
			(6'') : Process \textit{from} and include relation employees \newline
			(7'') : Process \textit{having} and include conditions \newline
			(8'') : Add target relation name [destRel] to the final translated statement\newline
			(9'') : End of statement \newline
						
				\textbf{Algorithm :} \newline
			(1''') : Recognize \textit{update} and include relation a \newline
			(2''') : Recognize \textit{set} and include attribute [b]  \newline
			(3''') : Recognize \textit{where} and the condition \newline
			(4''') : Process \textit{update}\newline
			(5''') : End of statement \newline
			
				\textbf{Algorithm :} \newline
			(1'''') : Recognize \textit{delete} and include relation b \newline
			(2'''') : Recognize \textit{where} and the condition \newline
			(3'''') : Process \textit{delete}\newline
			(4'''') : End of statement \newline
			
			They will be mapped in the following general algorithm :
		\begin{itemize}
			\item The JRelix Runtime recognize the SQLSTMT command which has been added to its grammar. This addition has been done modifying the Parser.jjt to add SQLSTMT as a new token, $<$INSQL$>$, in the \textit{Commands Tokens} section and modifying the Command() Method so that it awaits the $<$INSQL$>$ token with its $<$STRING$>$ parameter and its optional $<$FILE$>$ \footnote{See Section \ref{FileSection}} parameter. Depending on the presence or not of the $<$FILE$>$ parameter the OP\_INSQL or the OP\_INSQLFILE command will be transmitted to the interpreter with the $<$STRING$>$ parameter.
			\item In the interpreter the executeCommand() Method has been modified: two cases have been added to expect the OP\_INSQL or the OP\_INSQLFILE command. The Translator, which consist of one class, Main, including all its elements, is invoked through its translate() Method supplying it with the String parameter, whether to consider it as a path or not, a reference to the RD relation in RAM. 
  	\item In the translator itself if the String parameter is not a filename path\footnote{See Section \ref{FileSection}} it is divided into statements using the separator \textbf{\texttt{"};\texttt{"}}. (1, 1', 1'') At the same time the \textit{into} Clause is extracted and removed from Selection statements and the target relation is stored in the \textit{intoDest} array.
  	\item Still in the translate Method the statements are then concatenated into an InputStream which is supplied to the ANTLR parser \footnote{See Section \ref{ToolsSection}} which will parse it and generate the ASTs corresponding to each statement.   	
  	\item The visit() Method, which is the core method of the Translator, is then recursively invoked on each AST to produce the translated statement. This method generally translates sequentially unless some information is needed at the beginning, e.g. \textit{group by} Clause.  	
  	\item (2, 2', 2'') First of all the visit() recognizes the \textit{select} and includes the corresponding attributes. 
  	
  	In the case of expression, determined using the isExpression() method, it adds them using the AddExpression() method.
  	
  	(3'') In the case of aliases, determined using the isAlias() method, it adds them using the AddAliases() method.
  	
  	(4'') In the case of aggregate function it processes the aggregate function using the \textit{group by} in the visitGroup() Method.
  	
  	(1''', 2''', 3''', 4''', 1'''', 2'''', 3'''') If it recognizes \textit{update} or \textit{delete} rather than \textit{select} the whole statement is processed including the relation, the condition and the column to update in the case of an \textit{update}.  	
		\item (3, 3', 5'') In the case of a \textit{select} statement it then recognizes the \textit{from} and checks the presence of a \textit{where}. 
		\item (4, 6'') In the case of a \textit{where} it delays the \textit{from} processing because of the join presence possibility and processes the \textit{where} using the further parsed where condition, through our Boolean Parser \footnote{See Section \ref{BooleanParser}} with the parseWhereCondition() Method before the \textit{from} and checks the presence of a join with the isJoinGlobal() Method. If there is no join it processes the \textit{from}.
			\item  (4', 5', 6', 7') In the case of a join it processes the join and determine the type of the join on the selected attributes using the visitWhereJoin() Method that also includes the conditions of the statement if necessary.
			
			When unspecified the join attributes scan through the RD relation to find to which relation they belong to disambiguate the join. In the case of the stand alone translator there is no RD reference to disambiguate so all joins must be completely specified.  	
			\item (7'')In the case of a \textit{where} without a join or a \textit{having} it includes conditions using the visitWhere() Method.
			\item (5, 8', 8'')It then adds the target relation name to the final translated statement using the intoDest array.
			\item (6, 9', 9'', 5''', 4'''') The final translated statement is returned to the JRelix Runtime
  	\item Once the translator returns the SQL translated into Aldat to the system, it is then pushed onto the Parser Stack to be executed in the next loop of the interpreter.Then the control is given back to the interpreter that can loop for the next statement to execute which is the one we just put in the Stack.
		\end{itemize}
		
  \section{SQLEXP Keyword}
  
		We added the SQLEXP keyword to be able to use SQL relational expression in enclosing Aldat statements. Any Aldat statement using relational expression can use it. The reason we could not use the SQLSTMT command is because as other Aldat commands it is supposed to end by an action and return to the system whereas in the case of relational expression we want to return to the system the corresponding Selection. For the ease of examples we will mostly consider printing statements.
		
		\subsection{Selections}
		
		\subsubsection{Selects}
		
		Let's consider the first of the series of runs in the previous chapter to have an idea of what is occurring in the implementation :
		
  	\begin{quote}
			\item 1 $>$ d$<$- c ijoin sqlexp \texttt{"}select a from b;\texttt{"};
		\end{quote}
  	The output will be :
  	\begin{quote}
  		\texttt{d$<$- c ijoin ([a] in b);}
		\end{quote}
		To achieve this output we can succinctly describe what is occurring in the following way :
		\begin{itemize}
			\item First of all the input stream is redirected from the String transmitted to the translator by the JRelix system, then the lexer and the parser are invoked. The rules of the grammar are processed, the tokens recognized and finally we obtain the Abstract Syntax Tree (AST) corresponding to our SQL statement.
  		\item Then we visit recursively each of the subtrees corresponding to a statement and store the result in a String before returning it to the JRelix system for further processing.
  	\end{itemize}
  	
		To be more detailed for this run we have the following execution :
		\begin{itemize}
			\item 1 $>$ d$<$- c ijoin sqlexp \texttt{"}select a from b;\texttt{"}; \newline
  		\texttt{d$<$- c ijoin ([a] in b);} \newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree1.latex}}
						\caption{AST \textit{select a from b;}}
						\label{figure:AST1}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} absence and store system-generated intermediate relation name \newline
			(2) : Recognize \textit{select} and include attributes[a] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(4) : Include relations b\newline
			(5) : Add system-generated intermediate relation name to the final translated statement\newline
			(6) : End of statement \newline
		\end{itemize}
		
		As in the previous section, it is the \textit{into} mechanism which is also used to keep track of the intermediate relation name in the SQLEXP case. The name generated by JRelix is just transferred by the interpreter to the translator that adds it to the last Selection statement of the SQL String. That allows us to have other statements to be executed in the same SQL String while returning the result of the last Selection in the SQL translated.
		
		 Nevertheless it is worth mentioning that retrieving that correct system generated intermediate name was not straightforward. A pretty clear comprehension on JRelix internal mechanism has to be acquired first.
		 
		\begin{itemize}
			
			\item 5 $>$ pr sqlexp \texttt{"}select a, b from (select a,b,c from d where (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}) or g=2);\texttt{"}; \newline
			\texttt{pr [a,b] in ([a,b,c] where (e=1 and f=\texttt{"}a\texttt{"}) or g=2 in d);} \newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.4}{\input{tree2.latex}}
						\caption{AST \textit{select a, b from (select a,b,c from d where (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}) or g=2);}}
						\label{figure:AST5}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{into} absence and store system-generated intermediate relation name \newline
			(2) : Recognize \textit{select} and include attributes [a,b] \newline
			(3) : Recognize \textit{from} and check presence of \textit{where} \newline
			(4) : Recognize subquery \newline
			(5) : Recognize \textit{select} and include attributes [a,b,c] \newline
			(6) : Recognize \textit{from} and check presence of \textit{where} \newline
			(7) : Process \textit{where} before \textit{from} and check presence of join \newline
			(8) : Include conditions (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D} or g=2)\newline
			(9) : Include relations d\newline
			(10) : End of subquery \newline
			(11) : Add system-generated intermediate relation name to the final translated statement\newline
			(12) : End of statement \newline
			
		\end{itemize}
		
		\subsection{General algorithm}
		This general algorithm is a customized variation of the preceding one, for the SQLSTMT command, to take care of SQLEXP specificities. Only the differences are presented underneath :
		\begin{itemize}
			\item The JRelix Runtime recognize the SQLEXP command which has been added to its grammar. This addition has been done modifying the Parser.jjt to add SQLEXP as a new token, $<$EXPSQL$>$, in the \textit{Reserved Words Tokens} section and modifying the Primary() Method so that it invokes the SQLExpression() Method which itself awaits the $<$EXPSQL$>$ token with its $<$STRING$>$ parameter and its optional $<$FILE$>$ \footnote{See Section \ref{FileSection}} parameter. Depending on the presence or not of the $<$FILE$>$ parameter the OP\_EXPSQL or the OP\_EXPSQLFILE command will be transmitted to the interpreter with the $<$STRING$>$ parameter.
			\item In the interpreter the evaluateTLExpression() Method has been modified: two cases have been added to detect the OP\_EXPSQL or the OP\_EXPSQLFILE command. The Translator, which consist of one class, Main, including all its elements, is invoked through its translate() Method supplying it with the String parameter, whether to consider it as a path or not, a reference to the RD relation in RAM and the system-generated intermediate relation name. This system-generated intermediate relation name is provided as one of the arguments of the evaluateTLExpression() by the executeStatement() through a call to the nextTempName() Method.
  	\item The last selection without an into is assigned the intermediate relation name in its intoDest index. All the other selections without into are ignored. From there it works exactly as having an into for that relation.
  	\item Once the translator returns the SQL translated into Aldat to the system, it is then pushed onto the Parser Stack to be executed in the next loop of the interpreter. Then the control is given back to the interpreter that can loop for the next statement to execute which is the one we just put in the Stack.
		\end{itemize}
				
		\section{\label{FileSection} FILE Keyword}
		
		In both previous sections the SQL statements were directly written in the \textit{String} parameter. The extra parameter using the file keyword allows the translator to know that the string transferred by the interpreter is not directly the SQL to translate but the path to the file where the SQL statements are.
		Let's consider a file named \textit{\texttt{\char"0D}example.sql\texttt{\char"0D}} containing the following text in the current directory:
  	\begin{quote}
			\textbf{select a into destRel from b;}
		\end{quote}
		
		We will have for the following run using the the SQLSTMT command with the FILE extra parameter :
		 
  	\begin{quote}
			\item 1 $>$ sqlstmt file \texttt{"}example.sql\texttt{"};
		\end{quote}
  	The output corresponding :
  	\begin{quote}
  		\texttt{destRel$<$- [a] in b};
		\end{quote}
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree1.latex}}
						\caption{AST \textit{select a into destRel from b;}}
						\label{figure:AST1}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{file} extra parameter and read from file at specified path \newline
			(2) : Recognize \textit{into} and store target relation name [destRel] \newline
			(3) : Recognize \textit{select} and include attributes[a] \newline
			(4) : Recognize \textit{from} and check presence of \textit{where} \newline
			(5) : Include relations b\newline
			(6) : Add target relation name [destRel] to the final translated statement\newline
			(7) : End of statement \newline
		
		And if we consider a file named \textit{\texttt{\char"0D}example2.sql\texttt{\char"0D}} containing the following text in the current directory:
  	\begin{quote}
			\textbf{select a from b;}
		\end{quote}
		
		We will have for the following run using the the SQLEXP keyword with the FILE extra parameter :
		 
  	\begin{quote}
			\item 2 $>$ pr sqlexp file \texttt{"}example2.sql\texttt{"};
		\end{quote}
  	The output corresponding :
  	\begin{quote}
  		\texttt{pr [a] in b};
		\end{quote}
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.5}{\input{tree1.latex}}
						\caption{AST \textit{select a from b;}}
						\label{figure:AST2}
					\end{center}
				\end{figure}
				\textbf{Algorithm :} \newline
			(1) : Recognize \textit{file} extra parameter and read from file at specified path \newline
			(2) : Recognize \textit{into} absence and store system-generated intermediate relation name \newline
			(3) : Recognize \textit{select} and include attributes[a] \newline
			(4) : Recognize \textit{from} and check presence of \textit{where} \newline
			(5) : Include relations b\newline
			(6) : Add system-generated intermediate relation name to the final translated statement\newline
			(7) : End of statement \newline
		
		\subsection{General algorithms}
		
		The general algorithms are exactly the same as the ones described in the two sections before. The only difference is rather dividing the \textit{String} parameter into statements in the translate() method, it is used as a path to a file whose content is stored in a temporary \textit{String} which will divided into statements. From there the behavior is exactly the same for both algorithms. 
		
		\section{Commands grammar used which ANTLR cannot parse}
		
		Certain commands have not been added to the grammar we are using so they can not be parsed and that is the reason why they are not supported in the current version of the software. Nevertheless we can easily support them once they would have been integrated into the grammar because structures are very close whether in Aldat or SQL. They are :
		\begin{itemize}
					\item The create command : table, view, trigger, ... etc
					\item The drop command
					\item The insert command
		\end{itemize}
		
  	\section{JRelix Configuration}
  	
  	Both the ANTLR and the SQL2RELIX Jar files should be included in the classpath of JRelix to use the SQL front end interface in the JRelix Runtime. The ANTLR jar is needed by the SQL2RELIX jar for the ASTs generation and navigation. And the SQL2RELIX jar is obviously needed for the SQL translation.
  	
	  \section{\label{ToolsSection} Tools}
	  
		  \subsection{ANTLR v2.7.7 and how it operates}
		  
		  To generate the SQL parser we needed for our translator, we used this framework and the SQL Grammar \footnote{See Section \ref{GrammarSection}} provided on their website. This allows us to think of the evolution of the parser. Through this \texttt{"}Meta-parser\texttt{"} we will be able easily to use a new grammar including new SQL standards. 
		  
		  So the interest was double. First it allowed us to have a \texttt{"}Meta-parser\texttt{"} that can generate the SQL parser we needed with all the AST that we could navigate through easily for our translation. Second it allowed us to plan a way to integrate the omissions in our current version of the translator from the beginning knowing that we could update the grammar as soon as we find a new one more conforming to the recent standards.
		  
		  To have an idea of how the meta parser operates let's go through the steps that we did to generate our SQL Parser. 
			  \begin{itemize}
			  	\item First of all we download it from the ANTLR website\cite{antlr1}:
			  	\item Then what is needed is a grammar that defines the rules of the Parser and the Lexer. In our case we directly took an SQL grammar\cite{antlr2} from the ANTLR website but otherwise one could have defined it. The grammar is principally composed of two parts :
			  	\begin{itemize}
			  		\item A subclass of the generic Parser class provided by ANTLR. This subclass allows us to specify the specific rules of our SQL Parser. The rules are written using the standard Extended Backus-Naur Form. 
			  		\item A subclass of the generic Lexer class provided by ANTLR. This subclass allows us to specify the operators of our SQL Lexer. The pattern is the same as above.
			  	\end{itemize}
			  \item Then from that grammar we can generate our specific Parser and Lexer using the ANTLR engine. We just run it on the grammar :
			  \begin{quote}
			  	java antlr.Tool sql.g;
			  \end{quote}
			  It will run through the grammar and that is all that needed to be done with the Meta Parser. The files have been generated from this point on. They can now be used in the design of our translator.
			  
			  Nevertheless we will need two other classes from the ANTLR Framework :
			  \begin{itemize}
			  \item ANTLR.collections.AST \newline
			  This class gives the methods to be able to navigate through the ASTs, to identify the node type and to retrieve its value. The methods that we principally use are :
			  \begin{itemize}
			  \item getFirstChild()\newline
			  This methods allows us to get the first child of an AST.
			  \item getNextSibling()\newline
			  This methods allows us to get the next sibling of an AST.
			  \item getType()\newline
			  This methods allows us to get the type of a node of an AST.
			  \item getText()\newline
			  This methods allows us to get the the value of a node of an AST.
			  \end{itemize}
			  \item ANTLR.ASTFactory \newline
			  This class is a factory class for the AST. It then gives methods to create ASTs that we used principally for the boolean parser that we developed and that is described in this chapter in a few sections.
			  \end{itemize}
			  \end{itemize}
			  
					\subsection{Files generated}
					
					The generated files will be : 
					\begin{itemize}
					\item 1 SQLLexer.java
					\item 2 SQLParser.Java
					\item 3 SQLTokenTypes.java
					\item 4 SQLParser.smap
					\item 5 SQLLexer.smap
					\item 6 SQLTokenTypes.txt
					\end{itemize}
					The files we will take a deeper look at are the Java files. The information in the other three files are redundant with the one contained in the Java Files from the point of view of our research.
					To use the parser easily from the main elements of the program it will be necessary to navigate through the AST generated with the parser. All this will be allowed by the Java files generated by ANTLR. Among those files, some will allow us to make the lexical analysis (1), the parsing itself (2) and the AST generation (2). We then use the AST collection class provided by the ANTLR package to easily navigate through the AST. A dictionary of the different tokens (3) , the token types, is also generated which allows us to easily identify each node of the AST and have the corresponding behavior.
					
					Apart from the beginning where the lexing and parsing take place, we do not use the lexer and parser classes. Whereas the token types class has been used all over our translator because it allowed us to identify the clauses and to match almost one by one the clauses with Aldat. We also use a lot the AST collection class and the AST Factory class provided by the ANTLR package.
					
						We also needed to have Java files because the current version of Aldat, JRelix, is written in Java and to ease the integration of our translator in JRelix it was much better to use the same programming language. We added the two new commands, \textit{sqlstmt} and \textit{sqlexp} in JRelix, to be able to directly type SQL statements in Aldat with these commands and have the output of our translator redirected to JRelix and executed. This was the main idea of our research: be able to use SQL in Aldat with the transparent SQL interface.
						
					 	\subsection{\label{GrammarSection} Oracle 7 SQL grammar from ANTLR website}
					 	
					 	From the ANTLR website grammar library we took this grammar \cite{antlr2} to generate the corresponding java files that would be used to parse the SQL, to generate the Abstract Syntax Tree and to navigate through it with our translator. This grammar is a little bit old. It is based on SQL 1 from 1986 principally. Oracle did not include ANSI statements or other evolutions of SQL until Oracle 9. 
					 	
					 	This grammar is not also totally complete. We realized this during the course of our research. It does not cover the whole scope of the complete Oracle 7. Nevertheless it still covers enough to be able to create a translator that covers the basics of SQL which was our goal. 
					 	
					 	The main reason we chose this grammar is because we wanted a SQL grammar that we can use to generate Java files. More recent grammars were available but they either did not generate Java but rather C++ files which was not what we needed or they would impose the PL/SQL Syntax which is specific to Oracle and more complex than the simple SQL syntax. So even if it was a little bit old this grammar was the most generic we could find without having to rewrite one of our own. 
					 	
					\subsection{\label{BooleanParser} Boolean Parser}
					
						Due to the absence of analysis in the parsing of the \textit{Where Condition} due to the grammar used in ANTLR we had to develop using the ANTLR Framework and the AST classes a boolean parser. This is principally because the AST generated for the \textit{Where Condition} Clause is flat. At first we tried to work around it and just translate it directly. Nevertheless with the joins we finally noticed we needed to reparse it to have a real AST that we can use. To do so we used the ASTFactory class to generate the ASTs corresponding to the boolean conditions. We did not go beyond parsing the boolean expression because we did not need to. This part would be handled by the JRelix parser the output of our translator would be fed directly to it. 
						
						The boolean parser is invoked through the parseWhereCondition() Method in the translator. It takes as argument the flat AST corresponding to the boolean expression and returns the reconstructed, layered AST corresponding to it.
						
						Having a true AST rather than a flat one allows us to keep using our recursive approach to explore it. E.g. in the case of joins it allowed us to use the isJoinGlobal() method recursively up to the leaves of the boolean AST where the simple isJoin() method would be invoked. Whereas before creating we had to sequentially check for joins and have a very complex approach in the way we were processing \textit{Where Condition} in particular with joins on several attributes. Generally speaking dealing with flat ASTs was much more error prone and complex than with real structured ASTs. Therefore adding this further parsing was not a luxury but a real necessity.
						
						To give an idea of how the boolean parser operates let's consider the following boolean condition :
						\begin{quote}
						e=1 and f=\texttt{\char"0D}a\texttt{\char"0D} or g=2 \newline
						\end{quote}
						In the context of the following select :
						\begin{quote}
						select a, b from (select a,b,c from d where (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}) or g=2);
						\end{quote}
						
			It will normally generate this corresponding flat AST:\newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.4}{\input{tree2.latex}}
						\caption{AST \textit{select a, b from (select a,b,c from d where (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}) or g=2);}}
						\label{figure:AST1}
					\end{center}
				\end{figure}
				
				And after a second parsing it will finally generate this AST :\newline
				\begin{figure}[htbp]
					\begin{center}
						\scalebox{0.4}{\input{tree41.latex}}
						\caption{AST \textit{select a, b from (select a,b,c from d where (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D}) or g=2);}}
						\label{figure:AST2}
					\end{center}
				\end{figure}
				
			The parser mainly recursively look for the boolean operators \textit{and} and \textit{or} and constructs on the way the ASTs corresponding to the boolean expressions on each side of the operator until it arrives to non boolean expression (not involving \textit{and} or \textit{or}) and then consider them as leaves. Our Boolean parser takes into account boolean expressions enclosed in brackets as one boolean expression and breaks it down to the non boolean expression.
			
			In the case of our example the boolean expression is first parsed in two expressions connected with an \textit{or} operator by calling the parseWhereCondition():
					\begin{itemize}
					\item A boolean expression : (e=1 and f=\texttt{\char"0D}a\texttt{\char"0D})
					\item And a non boolean expression : g=2
					\end{itemize}
					The first operand will be further broken down in two leaves connected by an \textit{and} by recursively calling the parseWhereCondition(): 
					\begin{itemize}
					\item A non boolean expression : e=1
					\item A non boolean expression : f=\texttt{\char"0D}a\texttt{\char"0D}
					\end{itemize}
			Which gives the AST mentioned above.
			
	\chapter{Conclusion}
	
		\section{Recapitulation}
		
	After a brief introduction to SQL and Aldat generalities and syntaxes their resemblances and differences begin to be noticeable and some of the challenges that had to be overcome started to arises with their comparison. In particular it becomes obvious that with the vast panoply of RDBMS vendors (IBM, MySQL, SQL Server, Sybase, Oracle) and SQL versions (86, 92, 99, 2003) a choice had to be made for the SQL grammar that will be used in this research. These challenges only strengthen the motivation for this research that would use some key notions used through it (context-free grammars, LL parsers, Boolean Logic, ASTs).
	
	After the design and the implementation of the SQL front-end for JRelix it became obvious that there will be two categories of users : the basic end-users and those interested in its internals. From there the user's manual really allows somebody who will just use the system to catch on quickly on how it operates and to see which translations he could expect from this JRelix extension. The main keywords (SQLSTMT, SQLEXP, FILE) are introduced and their behavior described through a series of examples to easily grasp their meaning. It goes from simple statements to complex multi-statements batches to translate and execute on the system.
	
	The implementation manual then deepens into the architecture and the algorithms of the systems. Each of the keywords and how it operates on selections, updates, deletions, joins, aggregations and insertions is described in detail with the corresponding ASTs generated along the algorithm for the same series of examples as the user's manual. The configuration of the JRelix system to incorporate the extension as well as the tools used to build it (ANTLR, the Oracle SQL grammar, our own Boolean Parser) are also described in this manual.
	
		\section{Future work}
		
		Several leads have been revealed by this research : 
			\begin{itemize}
				\item One lead that needs to be followed would be to find a more recent grammar or complete this grammar to make it compliant with the more current SQL standard. The objective would be to make it compliant with the 2003-SQL. Three possibilities are the most plausible:
				\begin{itemize}
				\item 1 A new grammar is posted in the ANTLR Grammar list that corresponds to the 2003-SQL. In that case the parser would be regenerated with that grammar and the backward compatibility with the current translator would need to be checked before going forward and completing the translation of the remaining grammar.
				\item 2 Modify and update the current grammar to make it compliant. In this case no backward compatibilty check would need to be performed since the research would build on the current grammar and its corresponding generated parser. Nevertheless this possibily requires a certain ease with the specifications of the rules of the grammar to consistently add them.
				\item 3 Modify the PL/SQL Grammar available in the ANTLR Grammar list to only keep the SQL part of the grammar. In that case also the backward compatibility needs to be checked before going forward. It is also important to make sure that with the removal of the rules intended for the PL/SQL part no new ambiguity is introduced.
				\end{itemize}
				\item We appreciate the examiner's suggestion that we modify the rules to trigger
AST-generation automatically instead of writing our own Boolean Parser. Having the grammar deal directly with all aspects of the parsing and the AST-generation without needing further programming could be less error-prone.

This has not been done this way in the first place because of a limited knowledge of the ANTLR grammar syntax at the beginning of the research.
				\item It is also important to support more of the SQL grammar in our translator. Our research goal was not to be extensive but to begin to show that Aldat equivalents can be written for any code in SQL, which is the de facto standard language concerning databases. To push it further it would be logical to try to think about questions as :
				\begin{itemize}
				\item \textbf{What can Aldat do that SQL can not do?}\newline
				One strength of Aldat is that it supports recursion by design whereas in SQL recursions are often not allowed or when they are there is always a boundary in the depth of recusion allowed (triggers, views, ...). Therefore some applications, e.g., an inference engine that derives the possible conclusions from the set of rules and the known facts, can be done easily in Aldat and are just currently impossible in SQL \cite{Merrett2}. Since Aldat supports recursion natively with the principles of closure and abstraction, there is no limitation in the level of recursion. 
				
				Another great limitation of SQL is that the set of aggregation functions available is limited and there can not be any functional expression that is not derived from them. Certain RDBMS gave the opportunity to write in their own procedural extension a custom-aggregated function but the syntax is complex and limited to the corresponding RDBMS if they offer it. In Aldat with the Domain Algebra there is no limitation to the functions that can be created for the aggregations. For example a simple aggregated product cannot be done easily in SQL whereas it is done in two lines for Aldat : 
			\begin{quote}
			$>$ let prod be red * of possibilities; \newline
  		$>$ pr [prod] in permutations; \newline
			\end{quote}
			Matrix multiplication and more complex aggregations can be performed by Aldat as easily \cite{Merrett2}, in just a few lines, whereas one can imagine how complex the custom defined aggregation function may get for it. Furthermore there are no cumulative functions supplied by SQL and any of them that would be needed would have to be defined if possible in the same schema for the custom aggregate functions. In Aldat they are already integrated in the system. 
			
				The recent support of XML in the SQL standard \cite{sql2003} could also be compared to the semistructured data support \cite{Gu1} in Aldat. This could lead to an exciting research toward the current interest in XML-related subjects.
				\item \textbf{Can Aldat do all that SQL can do even though Aldat is much simpler than SQL?}	\newline
				To this point we have been able to support all of the SQL capabilities that we intended to in our research, principally the more commonly used. To prove that Aldat totally subsumes SQL, this research would need to be pushed further and become extensive on the capacities of SQL. 
				
					Nevertheless we need to keep in mind that Aldat does not provide constraint mechanisms such as the \textit{Primary Key} to avoid duplicates because of its relational approach that does not create duplicates. In the same kind of idea, it does not provide \textit{Indexes}  mechanisms because Aldat considers indexing to be an implementation issue outside of the scope of the langage. Unlike in SQL any tuple is unique and is not identified by its row number. A tuple with a row number X can not have the exact same data as a tuple with the row number Y.
				\end{itemize}
				\item Something else that needs to be looked at is the comparison between the queries written in SQL and their translation into Aldat to compare the syntactic complexity of these queries. 
				For example if we look at the selections: 
			\begin{quote}
			$>$ pr sqlexp \texttt{"}select * from b;\texttt{"}; \newline
  		\texttt{pr b;} \newline
			\end{quote}
			It is obvious that the syntaxic complexity of the query is lower in Aldat than in SQL.
			
				It might also be interesting to see if the same queries could have been expressed more easily if they have been directly written in Aldat.
				The example that comes directly at mind is the \textit{ijoin ijoin ijoin} example\footnote{See Section \ref{IjoinExample}} which is the brute force translation from the SQL query for a join on several attributes than can collapse to the more simpler \textit{ijoin} with the corresponding attributes. Other occurrences of these simplifications could constitute the pool of study.
				\end{itemize}
	\appendix
	\chapter{SQL Grammar}
	\begin{quote}
	
	
	class SqlParser extends Parser;\newline
\newline
options \{\newline
    exportVocab = Sql;\newline
    k = 4;\newline
    buildAST = true;\newline
\}\newline
\newline
tokens \{\newline
    SQL\_STATEMENT;\newline
    SELECT\_LIST;\newline
    TABLE\_REFERENCE\_LIST;\newline
    WHERE\_CONDITION;\newline
    SUBQUERY;\newline
    SQL\_IDENTIFIER;\newline
    SQL\_LITERAL;\newline
    FUNCTION;\newline
    GROUP\_FUNCTION;\newline
    USER\_FUNCTION;\newline
    MULTIPLY;\newline
\}\newline
\newline
start\_rule: (sql\_statement)* EOF;\newline
\newline
sql\_statement: sql\_command (SEMI)?\newline
        \{ \#sql\_statement = \#([SQL\_STATEMENT, "sql\_statement"], \#sql\_statement); \}\newline
    ;\newline
\newline
sql\_command: \newline
        to\_modify\_data\newline
    ;\newline
\newline
to\_modify\_data:\newline
        select\_command \newline
        $\|$ update\_command \newline
        $\|$ delete\_command \newline
    ;\newline
\newline
select\_command \newline
    :\newline
        select\_statement ( "union" select\_statement )* \newline
    ;\newline

select\_statement\newline
    :\newline
        ( OPEN\_PAREN select\_command CLOSE\_PAREN ) =$>$ OPEN\_PAREN select\_command CLOSE\_PAREN\newline
        $\|$ select\_expression\newline
    ;\newline
\newline
select\_expression:\newline
      "select" ( "all" $\|$ "distinct" )? select\_list\newline
      "from" table\_reference\_list\newline
      ( "where" where\_condition )?\newline
      ( connect\_clause )?\newline
      ( group\_clause )?\newline
      ( ( set\_clause ) =$>$ set\_clause )?\newline
      ( ( order\_clause ) =$>$ order\_clause )?\newline
      ( ( update\_clause ) =$>$ update\_clause )?\newline
    ;\newline
\newline
select\_list:\newline
      ( ( displayed\_column ) =$>$ displayed\_column ( COMMA displayed\_column )*\newline
        $\|$ ASTERISK )\newline
        \{ \#select\_list = \#([SELECT\_LIST, "select\_list"], \#select\_list); \}\newline
    ;\newline
\newline
table\_reference\_list:\newline
        selected\_table ( COMMA selected\_table )*\newline
        \{ \#table\_reference\_list = \#([TABLE\_REFERENCE\_LIST, "table\_reference\_list"], \#table\_reference\_list); \}\newline
    ;\newline
\newline
where\_condition:\newline
        condition\newline
        \{ \#where\_condition = \#([WHERE\_CONDITION, "where\_condition"], \#where\_condition); \}\newline
    ;\newline
\newline
displayed\_column\newline
      :\newline
      ( (schema\_name DOT)? table\_name DOT ASTERISK ) =$>$ ( ( schema\_name DOT )? table\_name DOT ASTERISK )\newline
      $\|$ ( exp\_simple ( alias )? )\newline
    ;\newline
\newline
schema\_name \newline
      : identifier\newline
    ;\newline
\newline
table\_name \newline
      : identifier \newline
    ;\newline
\newline
exp\_simple : expression ;\newline
\newline
expression \newline
      : term ( ( PLUS $\|$ MINUS ) term )*\newline
    ;\newline
\newline
alias \newline
      : ( "as" )? identifier\newline
    ;\newline
\newline
term \newline
      : factor ( ( multiply $\|$ DIVIDE ) factor )*\newline
    ;\newline
\newline
multiply:\newline
        ASTERISK\newline
        \{ \#multiply = \#([MULTIPLY, "multiply"], \#multiply); \}\newline
    ;\newline
\newline
factor \newline
      : factor2 ( VERTBAR VERTBAR factor2 )*\newline
    ;\newline
\newline
factor2\newline
      : ( sql\_literal ) =$>$ sql\_literal\newline
      $\|$ ( ( PLUS $\|$ MINUS ) expression ) =$>$ ( PLUS $\|$ MINUS ) expression\newline
      $\|$ ( function ( OPEN\_PAREN expression ( COMMA expression )* CLOSE\_PAREN ) ) =$>$ function ( OPEN\_PAREN expression ( COMMA expression )* CLOSE\_PAREN )\newline
        \{ \#factor2 = \#([FUNCTION, "function"], \#factor2); \}\newline
      $\|$ ( group\_function OPEN\_PAREN ( ASTERISK $\|$ "all" $\|$ "distinct" )? (expression)? CLOSE\_PAREN ) =$>$ group\_function OPEN\_PAREN ( ASTERISK $\|$ "all" $\|$ "distinct" )? (expression)? CLOSE\_PAREN\newline
        \{ \#factor2 = \#([GROUP\_FUNCTION, "group\_function"], \#factor2); \}\newline
      $\|$ ( user\_defined\_function ( OPEN\_PAREN expression ( COMMA expression )* CLOSE\_PAREN ) ) =$>$ user\_defined\_function ( OPEN\_PAREN expression ( COMMA expression )* CLOSE\_PAREN )\newline
        \{ \#factor2 = \#([USER\_FUNCTION, "user\_function"], \#factor2); \}\newline
      $\|$ ( OPEN\_PAREN expression CLOSE\_PAREN ) =$>$ OPEN\_PAREN expression CLOSE\_PAREN\newline
      $\|$ ( variable ) =$>$ variable\newline
        $\|$ expression\_list\newline
    ;\newline
\newline
expression\_list : OPEN\_PAREN expression ( COMMA expression )+ CLOSE\_PAREN ;\newline
\newline
sql\_literal:\newline
        ( NUMBER $\|$ QUOTED\_STRING $\|$ "null" )\newline
        \{ \#sql\_literal = \#([SQL\_LITERAL, "sql\_literal"], \#sql\_literal); \}\newline
    ;\newline
\newline
variable\newline 
    :\newline
        ( column\_spec ( OPEN\_PAREN PLUS CLOSE\_PAREN ) ) =$>$ column\_spec ( OPEN\_PAREN PLUS CLOSE\_PAREN )\newline
        $\|$ column\_spec\newline
    ;\newline
\newline
column\_spec\newline
    :\newline
        ( ( schema\_name DOT )? table\_name DOT )? column\_name\newline
    ;\newline
\newline
user\_defined\_function\newline
      : ( ( schema\_name DOT )? package\_name DOT )? identifier\newline
    ;\newline
\newline
package\_name : identifier ;\newline
\newline
column\_name : identifier ;\newline
\newline
function\newline 
      :\newline
      number\_function \newline
      $\|$ char\_function \newline
      $\|$ group\_function \newline      
      $\|$ conversion\_function \newline
      $\|$ other\_function \newline
    ;\newline
\newline
number\_function  \newline
      : \newline
      "abs" $\|$ "ceil" $\|$ "floor" $\|$ "mod" $\|$ "power" $\|$ "round"  \newline
      $\|$ "sign" $\|$ "sqrt" $\|$ "trunc" \newline
    ; \newline
 \newline
char\_function  \newline
      : \newline
      "chr" $\|$ "initcap" $\|$ "lower" $\|$ "lpad" $\|$ "ltrim" $\|$ "replace"  \newline
      $\|$ "rpad" $\|$ "rtrim" $\|$ "soundex" $\|$ "substr" $\|$ "translate" $\|$ "upper"  \newline
      $\|$ "ascii" $\|$ "instr" $\|$ "length"  \newline
      $\|$ "concat" \newline
    ; \newline
 \newline
group\_function  \newline
      : \newline
      "avg" $\|$ "count" $\|$ "max" $\|$ "min" $\|$ "stddev" $\|$ "sum"  \newline
      $\|$ "variance"  \newline
    ; \newline
 \newline
conversion\_function  \newline
      : \newline
      "chartorowid" $\|$ "convert" $\|$ "hextoraw" $\|$ "rawtohex" $\|$ "rowidtochar"  \newline
      $\|$ "to\_char" $\|$ "to\_date" $\|$ "to\_number"  \newline
    ; \newline
 \newline
other\_function  \newline
      : \newline
      "decode" $\|$ "dump" $\|$ "greatest" $\|$ "least" $\|$ "nvl"  \newline
      $\|$ "uid" $\|$ "userenv" $\|$ "vsize"  \newline
    ; \newline
 \newline
pseudo\_column \newline
    : \newline
        "user" $\|$ "sysdate" \newline
    ; \newline
 \newline
selected\_table  \newline
      : \newline
        ( table\_spec $\|$ subquery ) ( alias )? \newline
    ; \newline
 \newline
table\_spec \newline
    : \newline
      ( schema\_name DOT )? table\_name ( AT\_SIGN link\_name )? \newline
    ; \newline
 \newline
table\_alias \newline
    : \newline
      ( schema\_name DOT )? table\_name ( AT\_SIGN link\_name )? ( alias )? \newline
    ; \newline
 \newline
link\_name \newline 
      : identifier \newline
    ; \newline
 \newline
condition : logical\_term ( "or" logical\_term )* ; \newline
 \newline
logical\_term  \newline
      : logical\_factor ( "and" logical\_factor )* \newline
    ; \newline
 \newline
logical\_factor  \newline
      : \newline
      ( ( "prior" ) ? exp\_simple comparison\_op ( "prior" )? exp\_simple ) =$>$ ( ( "prior" ) ? exp\_simple comparison\_op ( "prior" )? exp\_simple )  \newline
      $\|$ ( exp\_simple ( "not" )? "in" ) =$>$ exp\_simple ("not")? "in" exp\_set \newline
      $\|$ ( exp\_simple ( "not" )? "like" ) =$>$ exp\_simple ( "not" )? "like" expression ( "escape" QUOTED\_STRING )? \newline
      $\|$ ( exp\_simple ( "not" )? "between" ) =$>$ exp\_simple ( "not" )? "between" exp\_simple "and" exp\_simple \newline
      $\|$ ( exp\_simple "is" ( "not" )? "null" ) =$>$ exp\_simple "is" ( "not" )? "null" \newline
      $\|$ ( quantified\_factor ) =$>$ quantified\_factor  \newline
      $\|$ ( "not" condition ) =$>$ "not" condition \newline
      $\|$ ( OPEN\_PAREN condition CLOSE\_PAREN )  \newline
    ; \newline
 \newline
quantified\_factor  \newline
      : \newline
      ( exp\_simple comparison\_op ( "all" $\|$ "any" )? subquery ) =$>$ exp\_simple comparison\_op ( "all" $\|$ "any" )? subquery \newline
      $\|$ ( ( "not" )? "exists" subquery ) =$>$ ( "not" )? "exists" subquery \newline
      $\|$ subquery \newline
    ; \newline
 \newline
comparison\_op  \newline
      :  \newline
      EQ $\|$ LT $\|$ GT $\|$ NOT\_EQ $\|$ LE $\|$ GE  \newline
    ; \newline
 \newline
exp\_set  \newline
      : ( exp\_simple ) =$>$ exp\_simple \newline
      $\|$ subquery \newline
    ; \newline
 \newline
subquery  \newline
    : \newline
        OPEN\_PAREN select\_command CLOSE\_PAREN  \newline
        \{ \#subquery = \#([SUBQUERY, "subquery"], \#subquery); \} \newline
    ; \newline
 \newline
connect\_clause  \newline
      : \newline
      ( "start" "with" condition )? // the start can be before the connect by \newline
      "connect" "by"  \newline
        condition \newline
      ( "start" "with" condition )? \newline
    ; \newline
 \newline
group\_clause  \newline
      : \newline
      "group" "by" expression ( COMMA expression )* ( "having" condition )? \newline
    ; \newline
set\_clause  \newline
      : \newline
      ( ( "union" "all" ) $\|$ "intersect" $\|$ "minus" ) select\_command  \newline
    ; \newline
 \newline
order\_clause \newline
      : \newline
      "order" "by" sorted\_def ( COMMA sorted\_def )* \newline
    ; \newline
 \newline
sorted\_def  \newline
      : \newline
      (( expression ) =$>$ expression $\|$ ( NUMBER ) =$>$ NUMBER ) ( "asc" $\|$ "desc" )?  \newline
    ; \newline
 \newline
update\_clause  \newline
      : \newline
      "for" "update" ( "of" column\_name ( COMMA column\_name )* )? ( "nowait" )? \newline
    ; \newline
 \newline
delete\_command  \newline
      : \newline
      "delete" ( "from" )? table\_alias ( "where" condition )? \newline
    ; \newline
 \newline
update\_command  \newline
    : \newline
        ( subquery\_update ) =$>$ subquery\_update  \newline
        $\|$ simple\_update \newline
    ; \newline
 \newline
simple\_update  \newline
      : \newline
      "update" table\_alias \newline
      "set" column\_spec EQ ( ( expression ) =$>$ expression $\|$ subquery )  \newline
      ( COMMA column\_spec EQ ( ( expression ) =$>$ expression $\|$ subquery ) )* \newline
      "where" condition  \newline
    ; \newline
 \newline
subquery\_update  \newline
      : \newline
      "update" table\_alias \newline
      "set" OPEN\_PAREN column\_spec ( COMMA column\_spec )* CLOSE\_PAREN EQ subquery  \newline
      "where" condition  \newline
    ; \newline
 \newline
identifier: \newline
        ( IDENTIFIER $\|$ QUOTED\_STRING $\|$ keyword ) \newline
        \{ \#identifier = \#([SQL\_IDENTIFIER, "sql\_identifier"], \#identifier); \} \newline
         \newline
    ; \newline
 \newline
quoted\_string : QUOTED\_STRING ; \newline
 \newline
match\_string : QUOTED\_STRING ; \newline
 \newline
keyword \newline
    : \newline
        "abs" \newline
        $\|$ "ascii" \newline
        $\|$ "ceil" \newline
        $\|$ "chartorowid" \newline
        $\|$ "chr" \newline
        $\|$ "concat" \newline
        $\|$ "convert" \newline
        $\|$ "count" \newline
        $\|$ "decode" \newline
        $\|$ "dump" \newline
        $\|$ "floor" \newline
        $\|$ "greatest" \newline
        $\|$ "hextoraw" \newline
        $\|$ "initcap" \newline
        $\|$ "instr" \newline
        $\|$ "intersect" \newline
        $\|$ "least" \newline
        $\|$ "length" \newline
        $\|$ "lower" \newline
        $\|$ "lpad" \newline
        $\|$ "ltrim" \newline
        $\|$ "nvl" \newline
        $\|$ "power" \newline
        $\|$ "rawtohex" \newline
        $\|$ "replace" \newline
        $\|$ "round" \newline
        $\|$ "rowidtochar" \newline
        $\|$ "rpad" \newline
        $\|$ "rtrim" \newline
        $\|$ "sign" \newline
        $\|$ "soundex" \newline
        $\|$ "sqrt" \newline
        $\|$ "substr" \newline
        $\|$ "sysdate" \newline
        $\|$ "to\_char" \newline
        $\|$ "to\_date" \newline
        $\|$ "to\_number" \newline
        $\|$ "translate" \newline
        $\|$ "trunc" \newline
        $\|$ "upper" \newline
        $\|$ "user"  \newline
        $\|$ "userenv" \newline
        $\|$ "vsize" \newline
    ; \newline
 \newline
class SqlLexer extends Lexer; \newline
 \newline
options \{ \newline
    exportVocab = Sql; \newline
    testLiterals = false; \newline
    k = 2; \newline
    caseSensitive = false; \newline
    caseSensitiveLiterals = false; \newline
    charVocabulary = '$\backslash$3' .. '$\backslash$177'; \newline
\} \newline
 \newline
IDENTIFIER options \{ testLiterals=true; \} \newline
    :  \newline
        'a' .. 'z' ( 'a' .. 'z' $\|$ '0' .. '9' $\|$ '\_' $\|$ '\$' $\|$ '\#' )* \newline
    ; \newline
 \newline
QUOTED\_STRING \newline
      : '$\backslash$'' ( \~{}'$\backslash$'' )* '$\backslash$''  \newline
    ; \newline
 \newline
SEMI : ';'; \newline
DOT : '.' ; \newline
COMMA : ',' ; \newline
ASTERISK : '*' ; \newline
AT\_SIGN : '\@' ; \newline
OPEN\_PAREN : '(' ; \newline
CLOSE\_PAREN : ')' ; \newline
PLUS : '+' ; \newline
MINUS : '-' ; \newline
DIVIDE : '/' ; \newline
VERTBAR : '$\|$' ; \newline
EQ : '=' ; \newline
NOT\_EQ : \newline
            '$<$' \{ \_ttype = LT; \} \newline
                (       ( '$>$' \{ \_ttype = NOT\_EQ; \} ) \newline
                    $\|$   ( '=' \{ \_ttype = LE; \} ) )? \newline
        $\|$ "!=" $\|$ "\^{}=" \newline
    ; \newline
GT : '$>$' ( '=' \{ \_ttype = GE; \} )? ; \newline
NUMBER  \newline
    : \newline
        ( PLUS $\|$ MINUS )? \newline
        ( ( N DOT N ) =$>$ N DOT N $\|$ DOT N $\|$ N ) \newline
        ( "e" ( PLUS $\|$ MINUS )? N )? \newline
    ; \newline
 \newline
protected \newline
N : '0' .. '9' ( '0' .. '9' )* ; \newline
 \newline
DOUBLE\_QUOTE : '"' \{ \$setType(Token.SKIP); \} ; \newline
 \newline
WS  :   (   ' ' \newline
        $\|$   '$\backslash$t' \newline
        $\|$   '$\backslash$r' '$\backslash$n' \{ newline(); \} \newline
        $\|$   '$\backslash$n'      \{ newline(); \} \newline
        $\|$   '$\backslash$r'      \{ newline(); \} \newline
        ) \newline
        \{\$setType(Token.SKIP);\}  \newline
    ; \newline
	\end{quote}

	\chapter{Sql Token Types}
		public interface SqlTokenTypes \{ \newline
			int EOF = 1;\newline
			int NULL\_TREE\_LOOKAHEAD = 3;\newline
			int SQL\_STATEMENT = 4;\newline
			int SELECT\_LIST = 5;\newline
			int TABLE\_REFERENCE\_LIST = 6;\newline
			int WHERE\_CONDITION = 7;\newline
			int SUBQUERY = 8;\newline
			int SQL\_IDENTIFIER = 9;\newline
			int SQL\_LITERAL = 10;\newline
			int FUNCTION = 11;\newline
			int GROUP\_FUNCTION = 12;\newline
			int USER\_FUNCTION = 13;\newline
			int MULTIPLY = 14;\newline
			int SEMI = 15;\newline
			int LITERAL\_union = 16;\newline
			int OPEN\_PAREN = 17;\newline
			int CLOSE\_PAREN = 18;\newline
			int LITERAL\_select = 19;\newline
			int LITERAL\_all = 20;\newline
			int LITERAL\_distinct = 21;\newline
			int LITERAL\_from = 22;\newline
			int LITERAL\_where = 23;\newline
			int COMMA = 24;\newline
			int ASTERISK = 25;\newline
			int DOT = 26;\newline
			int PLUS = 27;\newline
			int MINUS = 28;\newline
			int LITERAL\_as = 29;\newline
			int DIVIDE = 30;\newline
			int VERTBAR = 31;\newline
			int NUMBER = 32;\newline
			int QUOTED\_STRING = 33;\newline
			int LITERAL\_null = 34;\newline
			int LITERAL\_abs = 35;\newline
			int LITERAL\_ceil = 36;\newline
			int LITERAL\_floor = 37;\newline
			int LITERAL\_mod = 38;\newline
			int LITERAL\_power = 39;\newline
			int LITERAL\_round = 40;\newline
			int LITERAL\_sign = 41;\newline
			int LITERAL\_sqrt = 42;\newline
			int LITERAL\_trunc = 43;\newline
			int LITERAL\_chr = 44;\newline
			int LITERAL\_initcap = 45;\newline
			int LITERAL\_lower = 46;\newline
			int LITERAL\_lpad = 47;\newline
			int LITERAL\_ltrim = 48;\newline
			int LITERAL\_replace = 49;\newline
			int LITERAL\_rpad = 50;\newline
			int LITERAL\_rtrim = 51;\newline
			int LITERAL\_soundex = 52;\newline
			int LITERAL\_substr = 53;\newline
			int LITERAL\_translate = 54;\newline
			int LITERAL\_upper = 55;\newline
			int LITERAL\_ascii = 56;\newline
			int LITERAL\_instr = 57;\newline
			int LITERAL\_length = 58;\newline
			int LITERAL\_concat = 59;\newline
			int LITERAL\_avg = 60;\newline
			int LITERAL\_count = 61;\newline
			int LITERAL\_max = 62;\newline
			int LITERAL\_min = 63;\newline
			int LITERAL\_stddev = 64;\newline
			int LITERAL\_sum = 65;\newline
			int LITERAL\_variance = 66;\newline
			int LITERAL\_chartorowid = 67;\newline
			int LITERAL\_convert = 68;\newline
			int LITERAL\_hextoraw = 69;\newline
			int LITERAL\_rawtohex = 70;\newline
			int LITERAL\_rowidtochar = 71;\newline
			int LITERAL\_to\_char = 72;\newline
			int LITERAL\_to\_date = 73;\newline
			int LITERAL\_to\_number = 74;\newline
			int LITERAL\_decode = 75;\newline
			int LITERAL\_dump = 76;\newline
			int LITERAL\_greatest = 77;\newline
			int LITERAL\_least = 78;\newline
			int LITERAL\_nvl = 79;\newline
			int LITERAL\_uid = 80;\newline
			int LITERAL\_userenv = 81;\newline
			int LITERAL\_vsize = 82;\newline
			int LITERAL\_user = 83;\newline
			int LITERAL\_sysdate = 84;\newline
			int AT\_SIGN = 85;\newline
			int LITERAL\_or = 86;\newline
			int LITERAL\_and = 87;\newline
			int LITERAL\_prior = 88;\newline
			int LITERAL\_not = 89;\newline
			int LITERAL\_in = 90;\newline
			int LITERAL\_like = 91;\newline
			int LITERAL\_escape = 92;\newline
			int LITERAL\_between = 93;\newline
			int LITERAL\_is = 94;\newline
			int LITERAL\_any = 95;\newline
			int LITERAL\_exists = 96;\newline
			int EQ = 97;\newline
			int LT = 98;\newline
			int GT = 99;\newline
			int NOT\_EQ = 100;\newline
			int LE = 101;\newline
			int GE = 102;\newline
			int LITERAL\_start = 103;\newline
			int LITERAL\_with = 104;\newline
			int LITERAL\_connect = 105;\newline
			int LITERAL\_by = 106;\newline
			int LITERAL\_group = 107;\newline
			int LITERAL\_having = 108;\newline
			int LITERAL\_intersect = 109;\newline
			int LITERAL\_minus = 110;\newline
			int LITERAL\_order = 111;\newline
			int LITERAL\_asc = 112;\newline
			int LITERAL\_desc = 113;\newline
			int LITERAL\_for = 114;\newline
			int LITERAL\_update = 115;\newline
			int LITERAL\_of = 116;\newline
			int LITERAL\_nowait = 117;\newline
			int LITERAL\_delete = 118;\newline
			int LITERAL\_set = 119;\newline
			int IDENTIFIER = 120;\newline
			int N = 121;\newline
			int DOUBLE\_QUOTE = 122;\newline
			int WS = 123;\newline
			int ML\_COMMENT = 124;\newline
		\}
	\bibliographystyle{plain}
	\bibliography{References}
\end{document}