queries.tex

%!TEX root = reference.tex
\chapter{Queries}
\label{queries}
\index{queries}
A \ntRef{Query} is an expression that denotes a value implicitly -- by operations and constraints on other identified values. Typically, the result of a query is an \q{list} but it may be of any \ntRef{Type} -- provided that it implements the \q{sequence} contract.

There are several `flavors' of query: the \q{all} query (shown in Figure~\vref{allSolutionsFig}) projects a subset over one or more base collections; the \emph{N} \q{of} query extracts a list containing at most \emph{N} tuples from a collection; and the \q{any} query extracts a tuple that satisfies the query.

The results of a query may be sorted and may be filtered for uniqueness.

\begin{figure}[htbp]
\begin{eqnarray*}
\emph{Expression}&\arrowplus&\ntRef{Query}\\
\ntDef{Query}&\arrow&\ntRef{SequenceQuery}\ \choice\ \ntRef{ReductionQuery}\ \choice\ \ntRef{SatisfactionQuery}
\end{eqnarray*}
\caption{Query Expression}\label{relationQueryFig}
\end{figure}

\section{Sequence Queries}
\label{sequenceQueries}

A \ntRef{SequenceQuery} returns a collection of answers -- either all of them or some subset of them.

\begin{figure}[htbp]
\begin{eqnarray*}
\ntDef{SequenceQuery}&\arrow&\ntRef{SequenceType}\ \q{of}\ \q{\{}\ntRef{QueryExpression}\ \q{\}}\\
\ntDef{QueryExpression}&\arrow&\ntRef{AllSolutionsQuery}\\
&\choice&\ntRef{BoundedCardinalityQuery}
\end{eqnarray*}
\caption{Sequence Query Expression}\label{sequenceQueryFig}
\end{figure}

\noindent
where the \ntRef{SequenceType} plays a similar role in identifying the type of the result to that in \ntRef{SequenceExpression}s. If the \ntRef{SequenceType} is the keyword \q{sequence} then the result type is determined by the context of the \ntRef{Query} expression. Otherwise, \ntRef{SequenceType} identifies the name of a \ntRef{Type} -- which must implement the \q{sequence} contract (see Program~\vref{sequenceContractDef}) -- that denotes the result type of the query.

There are two variants of the \ntRef{SequenceQuery} -- \ntRef{AllSolutionsQuery} which returns a collection of all the answers to a question and \ntRef{BoundedCardinalityQuery} which returns some bounded subset of the query answers.

\subsection{All Solutions Queries}
\label{allSolutions}
\index{query!all solutions}
The all solutions query expressions return results corresponding to all the different ways that a condition may be satisfied. There are variants corresponding to finding distinct solutions and having the result sets ordered.

\begin{figure}[htbp]
\begin{eqnarray*}
\ntDef{AllSolutionsQuery}&\arrow&[\,\q{all}\,|\,\q{unique}\,]\ \ntRef{Expression}\ \q{where}\ \ntRef{Condition}\ [\ntRef{Modifier}]\\
\ntDef{Modifier}&\arrow&\q{order}\ [\q{descending}]\ \q{by}\ \ntRef{Expression}\ [\q{using}\ \ntRef{Expression}]
\end{eqnarray*}
\caption{All Solutions Query}\label{allSolutionsFig}
\end{figure}

For example, given a \q{list} bound to the variable \q{Tble}:
\begin{lstlisting}
def Tble is list of [
  ("john",23),
  ("sam",19),
  ("peter",21)
]
\end{lstlisting}
the query
\begin{lstlisting}
list of { all Who where (Who,A) in Tble and A>20 }
\end{lstlisting}
is a \ntRef{SequenceQuery} over the \q{Tble} list defined above. Its value is the \q{list}:
\begin{lstlisting}
list of [
  "john",
  "peter"
]
\end{lstlisting}
\q{"john"} and \q{"peter"} are in the result because both \q{("john",23)} and \q{("peter",21)} are in \q{Tble} and satisfy the condition that \q{A} is greater than 20.

\index{queries!bound expression}
In principle, any expression may follow the \q{all} clause in a query. The `bound expression' may mention variables that are `bound' within the query constraint.

\subsubsection{Ordered Result Sets}
The \q{order by} modifier is associated with a \emph{path expression} -- like the bound expression it is evaluated in the context of a successful solution to the condition. The results of an \q{order}ed query expression are sorted according to the values of this path expression. The type of this expression must be one that admits to being compared -- i.e., the type must implement the \q{comparable} contract.

For example, to return an ordered \q{cons} list\footnote{The type of the resulting collection is depends on whether the \ntRef{Query} is governed by an enclosing \ntRef{SequenceType} if available, or of type \q{array} by default.} of people over the age of 20 we can use the query expression:
\begin{lstlisting}
cons of { all Who where (Who,A) in Tble and A>20
                        order by A}
\end{lstlisting}
which would give the result:
\begin{lstlisting}
cons of [
  "peter",
  "john"
]
\end{lstlisting}

The \q{using} modifier may be used in conjunction with the \q{order by} modifier to override the default concept of less than. If given, the \q{using} keyword should be followed by a \q{boolean}-valued function defined over the same type as the \q{order by} expression.

For example, to override the use of \q{<} in the \q{order by} query above, with say \q{>}, we can use:
\begin{lstlisting}
cons of { all Who where (Who,A) in Tble and A>20
                        order by A using (>)}
\end{lstlisting}
which would give the result
\begin{lstlisting}
cons of [
  "john",
  "peter"
]
\end{lstlisting}

\subsubsection{Duplicate Elimination}
\label{duplicateElim}
\index{eliminating duplicates in queries}
\index{query!eliminating duplicates}
\index{unique@\q{unique} queries}

The \q{unique} keyword is used, instead of the \q{all} keyword, to signal a query where duplicate elements are eliminated from the answer set.

For example, the query:
\begin{lstlisting}
list of { unique Sib where (P,Who) in parent and
                           (P,Sib) in parent and Who!=Sib }
\end{lstlisting}
would have the effect of eliminating duplication caused by the fact that most people have two recorded parents.

The \q{unique} query requires that the type of the `bound expression' implements the \q{comparable} contract -- i.e., that \q{<} is defined for the type.

\begin{aside}
The \q{unique} query is potentially more expensive than the \q{all} query -- since it involves post-processing the results as the \q{all} query to perform the duplicate elimination.
\end{aside}

%\subsubsection{Type Safety}
%By default, the type of an \q{all} query is an \q{array} type; it requires that the condition be type safe:
%\begin{prooftree}
%\AxiomC{\typeprd{E}{B}{T}}
%\AxiomC{\typesat{E}{C}}
%\BinaryInfC{\typeprd{E}{\q{all}\ B\ \q{where}\ C}{\q{list of }T}}
%\end{prooftree}
%
%The type safety rule for \q{unique} queries very similar, except that the bound element must be of a type that implements the \q{comparable} contract:
%\begin{prooftree}
%\AxiomC{\typeprd{E}{B}{T\ \q{where comparable over }T}}
%\AxiomC{\typesat{E}{C}}
%\BinaryInfC{\typeprd{E}{\q{unique}\ B\ \q{where}\ C}{\q{list of }T}}
%\end{prooftree}
%
%\index{query!sorted}
%\index{sorted queries}
%\index{creating a sorted list from a query}
%In the case of an \q{ordered} query, the path expression must implement \q{comparable} and the result is a \q{list}:
%\begin{prooftree}
%\AxiomC{\typeprd{E}{B}{T}}
%\AxiomC{\typesat{E}{C}}
%\AxiomC{\typeprd{E}{P}{P\sub{T}\ \q{where comparable over }P\sub{T}}}
%\TrinaryInfC{\typeprd{E}{\q{all}\ B\ \q{where}\ C\ \q{order by}\ P}{\q{list of }T}}
%\end{prooftree}
%
\subsection{Bounded Cardinality Queries}
The \emph{N} \q{of} quantifier delivers \emph{at most} N solutions to the query. For example, the query:
\begin{lstlisting}
list of { 5 of X where (P,X) in children }
\end{lstlisting}
returns an \q{list} of the first 5 children of \q{P}.

\begin{figure}[htbp]
\begin{eqnarray*}
\ntDef{BoundedCardinalityQuery}&\arrow&\ntRef{QueryQuantifier}\ \q{where}\ \ntRef{Condition}\ [\ntRef{Modifier}]\\
\ntDef{QueryQuantifier}&\arrow&[\,\q{unique}\,]\ \ntRef{Expression}\ \q{of}\ \ntRef{Expression}
\end{eqnarray*}
\caption{Bounded Cardinality Query}\label{boundedCardinalityFig}
\end{figure}

\subsubsection{Duplicate Elimination}
If the \q{unique} keyword is used with the bounded cardinality then duplication elimination is performed \emph{before} counting the results. I.e., a query of the form:
\begin{lstlisting}
list of { unique 5 of X where (P,X) in children }
\end{lstlisting}
is guaranteed to find 5 unique answers -- assuming that there are at least 5 unique ways of solving the \q{(P,X) in children} condition.

\subsubsection{Ordered Result Sets}
If the \q{ordered by} modifier is \emph{not} present, there is no defined ordering for the answers in the result. In particular, if \emph{N} answers are requested, they could be any \emph{N} answers that satisfy the condition.

If an \q{order by} clause is specified then the result consists of the `smallest' results. I.e., if there are 5 answers to the query:
\begin{lstlisting}
list of { all X where (P,X) in children }
\end{lstlisting}
then the query
\begin{lstlisting}
list of { 3 of X where (P,X) in children order by X }
\end{lstlisting}
results in an \q{array} of 3 elements that are guaranteed to be smaller or equal to any remaining answers.

If the \q{order descending} modifier is used then the `largest' results will be the ones returned.
\begin{aside}
Of course, in order to compute this smallest set, all the answers must first be computed. The result set sorted and only then the first elements picked.
\end{aside}

%\subsubsection{Type Safety}
%The type of a bounded query is a \q{list} type; it requires that the condition be type safe, and that the bound is an \q{integer}:
%\begin{prooftree}
%\AxiomC{\typeprd{E}{N}{\q{integer}}}
%\AxiomC{\typeprd{E}{B}{T}}
%\AxiomC{\typesat{E}{C}}
%\TrinaryInfC{\typeprd{E}{N\ \q{of}\ B\ \q{where}\ C}{\q{list of }T}}
%\end{prooftree}
%
%In the case of an \q{ordered} bounded query, the path expression must implement \q{comparable} and the result is a \q{list}:
%\begin{prooftree}
%\AxiomC{\typeprd{E}{N}{\q{integer}}\quad\typeprd{E}{B}{T}}
%\AxiomC{\typesat{E}{C}}
%\AxiomC{\typeprd{E}{P}{P\sub{T}\,\q{where comparable over }P\sub{T}}}
%\TrinaryInfC{\typeprd{E}{N\ \q{of}\ B\ \q{where}\ C\ \q{order by}\ P}{\q{list of }T}}
%\end{prooftree}

\section{Satisfaction Queries}
A \ntRef{Satisfaction} is used to find an individual that satisfies the condition. It returns a  \emph{single} result corresponding to a solution of the query -- as an \q{option}al value.

\begin{figure}[htbp]
\begin{eqnarray*}
\ntDef{SatisfactionQuery}&\arrow&\q{any of}\ \ntRef{Expression}\ \q{where}\ \ntRef{Condition}\ [\ntRef{Modifier}]
\end{eqnarray*}
\caption{Satisfaction Query}\label{satisfactionQueryFig}
\end{figure}

For example, to find a child of \q{P} one could use the expression:
\begin{lstlisting}
any of X where (P,X) in children
\end{lstlisting}

The \q{default} clause is used in the case that the \ntRef{Condition} is \emph{not} satisfiable. For example, assuming that we did not have a record of \q{"fred"}'s parents, then the query
\begin{lstlisting}
any of P where (P,"fred") in children default "not known"
\end{lstlisting}
would result in the answer \q{"not known"}.

\subsubsection{A Sorted Satisfaction Query}
The \q{order by} clause can be used to select the `smallest' solution to the query: the result of an \q{any of} query that is governed by an \q{order by} clause is effectively the \emph{least} solution to the query. If the \q{order descending} modifier is used then the result is the largest solution to the query.

For example, to find the youngest child of \q{"john"} we can use the query:
\begin{lstlisting}
any of X where ("john",X) in children and (X,A) in ages order by A
\end{lstlisting}

\subsubsection{Type Safety}
A satisfaction query's type is \q{option} of the type of the bound expression. As with other queries, it requires that the condition is safe:
\begin{prooftree}
\AxiomC{\typeprd{E$\,\cup{}\,$varsIn(C)}{B}{T}}
\AxiomC{\typesat{E}{C}}
\BinaryInfC{\typeprd{E}{\q{any of}\ B\ \q{where}\ C}{\q{option of }T}}
\end{prooftree}

In the case of an \q{order}ed satisfaction query, the path expression must implement \q{comparable}:
\begin{prooftree}
\AxiomC{\typeprd{E$\,\cup{}\,$varsIn(C)}{B}{T}}
\AxiomC{\typesat{E}{C}}
\AxiomC{\typeprd{E}{P}{P\sub{T}\ \q{where comparable over }P\sub{T}}}
\TrinaryInfC{\typeprd{E}{\q{any of}\ B\ \q{where}\ C\ \q{order by}\ P}{\q{option of }T}}
\end{prooftree}

\section{Reduction Query}
\label{reductionQuery}
\index{accumulating over a query}
\index{applying a function to the results of a query}

A \ntRef{ReductionQuery} differs from other forms of query in that the results of satisfying the \ntRef{Condition} are `fed' to a function rather than being returned as some form of collection.

\begin{figure}[htbp]
\begin{eqnarray*}
\ntDef{ReductionQuery}&\arrow&\q{reduction}\ \ntRef{Expression}\ \q{of}\ \ntRef{QueryExpression}
\end{eqnarray*}
\caption{Reduction Query}\label{reductionQueryFig}
\end{figure}

The reduction function should have the type:
\begin{lstlisting}
(t\sub{E},t\sub{E})=>t\sub{E}
\end{lstlisting}
were \q{t\sub{E}} is the type of the bound expression in the \ntRef{QueryExpression}.

For example, to add up all the salaries in a department, one could use a query of the form:
\begin{lstlisting}
reduction (+) of { all E.salary where E in employees }
\end{lstlisting}

\begin{aside}
The reducing function is only applied if there is more than one solution to the query. In this sense, it is closer in semantics to \q{leftFold1} than to \q{leftFold} -- see Section~\vref{foldableContract}.
\end{aside}

\begin{aside}
The \ntRef{ReductionQuery} may be used with all the normal variants of \ntRef{QueryExpression}.
\end{aside}