\section{The Language SBQL}
 

In this section we illustrate how the semantics of query
language primitives, and hence also complete query languages,
can be defined on our machine.  We sketch here the definition of
an untyped language, called SBQL (Stack-Based Query Language).
For lack of space, we present only some of the constructs. A few
update and procedural constructs are presented in the next
section.
 
\subsection{The General Framework}
 
The structure of the language is simple: Any constant or name is
an {\em atomic} query.  From such queries we build  complex
queries by applying unary or binary operators.  For example,
$EMP, SAL$, $1800$ and $2$ are queries, from which we can build
such queries as $EMP \; where \; (SAL > 1800)$ and $2 * 2$.
With the exception of typing constraints (e.g., one cannot
multiply two sets of strings), we assume full orthogonality of
operators. Parentheses are allowed, precedence rules are not
discussed here.
 
To define the semantics of the language, we introduce a
recursive procedure $eval$ that maps a syntactically correct
query and a machine state to a result. The state consists of a
store and a state of the environment stack. The procedure is
defined by cases, one for each operator. It may change the
environment stack; however, the state of the stack after
evaluation is always the same as before evaluation. The result
of a query is left as a new cell at the top of $QRES$.
 
\subsection{Atomic Queries}
 
We start with atomic queries, namely constants and names.  We
assume that constants that denote some elements of $V$ are
available in the language.  For the query $c$, where $c$ is a
constant, $eval(c)$ leaves the $1 \times 1$ table $\{c\}$ at the
top of $QRES$.  For the query $n$,where $n$ is a name, $eval(n)$
searches for bindings for $n$ is $ES$, and leaves the result,
$search(n)$, at the top of $QRES$.  For example, the query
$EMP$, applied to $MyDatabase$, returns a single-column table
containing identifiers $i_1, i_5, i_9$.
 
\subsection{Compound Queries: Algebraic Operators}
 
An operator is called {\em algebraic} if its effect is defined
purely in terms of its argument(s), and is independent of the
environment.  By convention, such an operator takes its
argument(s) from $QRES$ (popping the cells that contain them)
and pushes its result there.  Examples of algebraic operators
include operations on atomic values such as arithmetic
operations and comparisons, string operations, boolean
operations, and equality tests of identifiers. They also include
aggregates applied to collections, and set operations such as
set union, product, tests for containment, emptiness, and so on.
 
The semantics of a binary algebraic operator $\Theta$ is defines as
follows:\\\\
\h {\bf case} $query$ is $q_1 \Theta q_2$ ($\Theta$ algebraic): \\
\hh {\bf begin}\\
\hhh $eval(q_1)$;\\
\hhh $eval(q_2)$;\\
\hhh $apply(\Theta)$\\
\hh {\bf end}\\\\
By our assumption on the state of $ES$ before and after a call
to $eval$, both queries are evaluated in the same environment.
We assume that $apply$ is defined without any use of the
environment. The semantics of operations such as set union or
product may be defined using the same pattern. Dereferencing may
be needed, dependening on the operator being applied; for
example, $SAL > 2500$ requires dereferencing of an identifier
returned by $SAL$. For the space limit we omit further
discussion.
 
\subsection{Compound Queries: non-Algebraic Operators}
 
The general syntax for application of a non-algebraic operators
is $q_1 \Theta q_2$, where $q_1$ and $q_2$ are (arbitrarily
complex) queries, and $\Theta$ is an operator.  The general
pattern that defines a part of the {\em eval} procedure for
queries with a non-algebraic operator is as follows.\\\\
\h {\bf case} query is $q_1 \Theta q_2$ ($\Theta$ non-algebraic):\\
\hh {\bf begin}\\
\hhh {\em eval}$(q_1)$; \\
\hhh for each row $r$ in $top(QRES)$ do in parallel \\
\hhhh push( $ES, nested(r))$;\hhh (* Open a new scope on ES *)\\
\hhhh $eval(q_2)$; \\
\hhhh $partial\_result := combine( r, top(QRES), \Theta)$;\\
\hhhh pop( $ES$ ); pop( $QRES$ ); (* Restore the state of local
processors *) \\
\hhh end for each;\\
\hhh $merged\_result := merge( partial\_results, \Theta )$;\\ 
\hhh pop( $QRES$ ); (* Remove from QRES the table created by
$q_1$ *)\\
\hhh push( $QRES, merged\_result$ );\\
\hh {\bf end}\\\\
Before the evaluation of $q_2$, many parallel processors are
activated, one for each row $r$ from the table returned by
$q_1$.  Each processor opens an own new scope $nested(r)$, then
evaluates $q_2$. A partial result returned by it depends on the
result returned by $q_2$, $r$ and $\Theta$. Finally, partial
results are merged; the merging function depends on $\Theta$.

Note that the evaluation is not symmetric in the two subqueries,
since $q_2$ is evaluated in environments determined by the
result of $q_1$. In the rest of the section we define and
illustrate various non-algebraic operations that exploit these
environment stack dependencies.
 
\subsection{Selection}
 
The syntax for the selection operation is $q_1 \; where \; q_2$,
where $q_1$ is any query, and $q_2$ is a boolean-valued query, i.e.,
a condition.  The semantics is defined by the scheme above,
where the function $combine$ is defined  by:
\begin{tabbing}
\h$combine(r, top(QRES), where) \equiv$ \={\bf if} $top(QRES) = TRUE$ \\ 
\>{\bf then} return \{$r$\} {\bf else} return $\emptyset$
\end{tabbing}
The $merge$ function is the union of partial results.
\begin{examp} (C.f. {\em MyDatabase}).\\
Consider \hh $EMP \; where \; ( SAL \; > \; 1800)$ \hh
expressing the query``List employees earning more than 1800''.
We follow its execution. Initially, the environment stack
contains one section containing identifiers of all root database
records:\vsmall\\
\hsmall\framebox{$i_{1(EMP)}, i_{5(EMP)}, i_{9(EMP)}, i_{13(DEPT)},
 i_{17(DEPT)}$}\vsmall\vtiny\\
First, $eval$ is called with the atomic query $EMP$.  The name
$EMP$ is bound to three objects, whose identifiers are put in a
single-column table in $QRES$:
\begin{center}
\begin{tabular}{|l|}
\hline
$i_1$\\ $i_5$\\ $i_9$\\
\hline
\end{tabular}
\end{center}
Each row is processed by the body of $for \; each$. For the row
containing $i_1$, we have $nested(i_1)=\{i_2,i_3,i_4\}$.  This
set is pushed onto $ES$:\vsmall\\
\hsmall\parbox{10cm}{
\begin{tabular}{|l|} \hline
$i_{2(NAME)}, i_{3(SAL)}, i_{4(WORKS\_IN)} $\\
\hline
$i_{1(EMP)}, i_{5(EMP)}, i_{9(EMP)}, i_{13(DEPT)}, i_{17(DEPT)}$\\
\hline \end{tabular}
}\vtiny\\
Now $SAL > 1800$ is evaluated. The predicate $>$ is algebraic,
so subqueries $SAL$ and $1800$ are evaluated with the same
environment stack. The evaluation goes through the following
states of local $QRES$ (which is assigned to a processor
processing $i_1$):\\
\parbox[b]{2.8cm}{ \begin{center}
                $eval(SAL)$:\\
                \begin{tabular}{|l|} \hline
                $i_3$\\
                \hline  \end{tabular}
                \end{center}}
\parbox[b]{2.8cm}{ \begin{center}
                 $eval(1800)$:\\
                \begin{tabular}{|l|}  \hline
                $1800$\\
                \hline
                $i_3$\\
                \hline \end{tabular}
                \end{center}}
\parbox[b]{2.8cm}{ \begin{center}
                Dereferencing:\\
                \begin{tabular}{|l|} \hline
                $1800$\\
                \hline
                $2500$\\
                \hline \end{tabular}
                \end{center}}
\parbox[b]{2.8cm}{ \begin{center}
                Comparison:\\
                \begin{tabular}{|l|} \hline
                $TRUE$\\
                \hline \end{tabular}
                \end{center}}

\noi Since the predicate returns $TRUE$, the row $i_1$ is
included into the result.
 
The same action is performed concurrently for the rows $i_5$,
for which the predicate is also $TRUE$, and  $i_9$, for which
the predicate returns $FALSE$.  At the end, upon exit from the
{\em for each}, the environment stack will be the same as at the
beginning. Merging individual results of parallel streams is
collected at the top of $QRES$ as a table \{$i_1, i_5$\}.
\end{examp}
 
\subsection{Joins}
 
Using the product and the selection, we can define joins.
Consider the query\vsmall\\
\hsmall
$(DEPT \times EMP) \; where \; (DNO = EDNO)$.\vsmall\\
As described above, the query $DEPT \times EMP$ leaves on $QRES$
a two-column table where each row is a pair of identifiers of
$DEPT$ and $EMP$ objects.  A stream in the evaluation of the
{\em where} clause will push onto $ES$ $nested(\{i,j\})$ for one
such pair, then evaluate the condition.  The top section now
contains identifiers of objects whose names are the attributes
of the $DEPT$ and $EMP$ collections. The condition $DNO = EDNO$
is evaluated on attributes of the two objects. The final result
is a set of pairs of identifiers, one from each collection, that
identify pairs of objects for which the condition is true.
 
\subsection{Projection, Navigation, Path Expressions}
 
We need the ability to retrieve subobjects of previously
identified objects. This is provided by the `dot' operator.
When used more than once, it allows navigation in an object
graph using path expressions. The syntax is $q_1.q_2$, where
$q_1$ and $q_2$ are queries. To avoid parenthesis in long path
expressions, we assume association to the left. The definition
of the semantics is very similar to the semantics of {\em
where}, except that the $combine$ function simply returns the
table returned by $q_2$.
\begin{examp}
\label{examp:works}
\ \vsmall\\
\hsmall$EMP.SAL$\vsmall\vtiny\\
returns a single-column table, in which each row is the
identifier of a $SAL$ object nested inside some EMP object, for
example, $\row{i_3}$.
\vsmall\\
\hsmall$(EMP \; where \; NAME = "Smith" ).WORKS\_IN$.\vtiny\\
The evaluation of the first part terminates with $ES$ containing
only the initial section, and $QRES$ containing the table
$\{\row{i_5}\}$. Now, to evaluate the `$.WORKS\_IN$' part, we
push on $ES$ the section $nested(i_5)= \{i_6 , i_7 , i_8\}$. The
evaluation terminates with $\{\row{i_8}\}$ at the top of $QRES$.
\end{examp}

To find the name of the department where Smith works, we have to
write\vsmall\\
\hsmall $(EMP \; where \; NAME = "Smith").WORKS\_IN.DEPT.DNAME$\vtiny\\
An evaluation strategy requires $DEPT$ in the path expression to
be able to access $DNAME$. This is a viable option, however, it
makes path expressions longer. Most languages for
object-oriented databases have chosen to interpret the ``dot''
operation so that $EMP.WORKS\_IN.DNAME$ is a legal query.
 
To follow this tendency, we could introduce a new function
$nested$, which for a pointer object returns its r-value.
However, this will make it difficult to treat updates. How do we
define assignment of a new $DEPT$ identifier to the $WORKS\_IN$
attribute of Smith? We need the query that returns the l-value
for the assignment, which in this case is $i_8$, but with the
currently considered option the query returns the r-value,
$i_{17}$. We can also consider elliptic syntax, which does not
change semantics, but allows us in some contexts to omit some
elements of a full query. These issues are not considered in
this paper.
\begin{examp}
\ \vsmall\\
\hsmall $EMP \; where \; SAL > ((EMP \; where \; NAME
= "Smith").SAL)$\vtiny\\
This query combines nested $where$ clauses with `dot'. It
expresses the query ``List employees earning more than Smith''.
Note that the binding of the second occurrence of $EMP$ is
performed on $ES$ containing two sections, e.g.\vsmall\\
\hsmall\parbox{10cm}{
\begin{tabular}{|l|}
\hline
$i_{2(NAME)}, i_{3(SAL)}, i_{4(WORKS\_IN)}$\\
\hline
$i_{1(EMP)}, i_{5(EMP)}, i_{9(EMP)}, i_{13(DEPT)}, i_{17(DEPT)}$\\
\hline
\end{tabular}
}\vtiny\\
and will again return \{$i_1,i_5,i_9$\}, and binding of the
second occurence of $SAL$ is performed on the stack containing
three sections, e.g.\vsmall\\
\hsmall\parbox{10cm}{
\begin{tabular}{|l|}
\hline
$i_{6(NAME)}, i_{7(SAL)}, i_{8(WORKS\_IN)}$\\
\hline
$i_{2(NAME)}, i_{3(SAL)}, i_{4(WORKS\_IN)}$\\
\hline
$i_{1(EMP)}, i_{5(EMP)}, i_{9(EMP)}, i_{13(DEPT)}, i_{17(DEPT)}$\\
\hline
\end{tabular}
}\vtiny\\
and will return (in this case) $i_7$.
\end{examp}

It is easy to see that `dot' is an associative operation:
$(q_1.q_2).q_3$ is equivalent to $q_1.(q_2.q_3$); thus,
parentheses are not needed.
\begin{examp}
\ \vsmall\\
\htiny $(EMP \; where \; NAME =
"Smith").WORKS\_IN.\\ \hh DEPT.EMPLOYS.EMP.(NAME \times JOB)$\vtiny\\
returns a table containing (identifiers of) the name and job of
the employees working in the same department as Smith. This
query illustrates the use of product for constructing
multi-component target list, which may be important in the
context of multivalued attributes.
\end{examp}

Path expressions for navigation in object databases have been
proposed in many papers, e.g. \cite{KKS92}. We believe that our
approach is very general, fully orthogonal to other query
operators, and semantically clean.
 
\subsection{Navigational Join}
 
The `dot' operation allows one to `walk' on a path, but the
result is always the end point of the path. Another interesting
operation is {\em navigational join}, that forms pairs
containing the start and end points of a path. For example, we
might want to create a set of pairs of employees and the
departments they work in. In relational systems such an
operator can be defined as a product followed by a selection,
but in object-oriented systems it is often more natural to
express it directly as a navigation through a pointer-valued
attribute.
 
The syntax is $q_1 \bowtie q_2$. Let $\otimes$ denote the
cartesian product generalized to bags. The semantics of the
operation is defined by the same scheme as above, except for the
$combine$ function, which is defined as follows:\\
\hh $combine(r, top(QRES), \bowtie ) \equiv return( \{r\}
\otimes top(QRES)) $\\
Thus, each row $r$ returned by $q_1$ is combined with each row
returned by $q_2$ for this $r$. As previously, the final result
is a union of partial results.
\begin{examp}
\ \vsmall\\
\hsmall $EMP \bowtie (WORKS\_IN.DEPT)$\vtiny\\
returns a two-column table, where each row contains the identifiers of
an employee and the identifier of his department.\\
\hsmall $EMP \bowtie (DEPT \; where \; EDNO = DNO)$\vtiny\\
is a relational variant of the previous example.  It shows that
the construct is general. In $q_1 \bowtie q_2$, the second
component $q_2$ can be any query, in particular, a function of
the elements returned by $q_1$.\vsmall\\
\hsmall $EMP \bowtie (WORKS\_IN.DEPT.(DNAME \times LOC))$\vtiny\\
returns a three column table, where identifiers of $EMP$ are
associated with identifiers of $DNAME$ and $LOC$ of the
department in which the employee works.
\vsmall\\
\hsmall$DEPT \; \bowtie \; avg(EMPLOYS.EMP.SAL)$
\vtiny\\
returns a table of pairs consisting of a department identifier
and the average salary of its employees. In SQL this query
requires the {\em group by} operator. In our approach we achieve
the same goal using clean functional semantics and
orthogonality.
\end{examp}
 
\subsection{Quantifiers}

The syntax is $ Q q_1(q_2)$, where $Q$ is either $\forall$ or
$\exists$, $q_1$ is an arbitrary query, and $q_2$ is an
arbitrary boolean-value condition. Thus, $Q$ is regarded as a
binary operation, similar to previous non-algebraic operations.
The semantics is also defined similarly. The differences are in the
$combine$ function, and in how the results of the parallel
evaluation streams are merged. The $combine$ function simply returns
the truth value returned by $q_2$. For $\forall$ the result is
$TRUE$ if $q_1$ returns an empty table, or the boolean conjunction
of all returned truth values otherwise; for $\exists$ the
result is $FALSE$ in the first case, or the booloean alternative
of partial results otherwise. 
\begin{examp} Departments where all programmers used to work for IBM:
\vsmall\\
\hsmall $DEPT \; where \; \forall \; (EMPLOYS.EMP \; where \; JOB =
 "programmer")$\\
\hhhh$(\; \exists \; PREV\_JOB \; (COMPANY = "IBM") )$\vtiny
\end{examp}

Usually quantifiers are associated with auxiliary variables. The
next sub-section addresses this problem.

\subsection{Correlation Variables and Synonyms}
 
Most logical calculi rely strongly on the use of variables; so
do many query languages. However, the concept of variable as
used in these languages is quite different from its standard use
in programming languages as a cell used to hold an updatable
value. In calculi and query languages, variables are used as
temporary names: either to provide synonyms for stored relations
(to avoid name conflict), or as iterators over sets. The SQL
phrase $from \; EMP \; e$, introduces $e$ for a similiar
purpose.

Semantics of such auxiliary names is not always obvious. An example is
the DBPL construct \cite{ScMa92}:\vsmall\\
\hsmall $FOR \; EACH \; x \; IN \; EMP : x.JOB = {\it ``clerk''}
\; DO \; x.SAL := 3000; \; END;$\vtiny\\ 
where $x$ is used both as a calculus variable and as a
programming variable. Achieving all goals of auxiliary naming,
(i.e. local synonyms for objects with statically determined
scope, naming of a query result or its parts, iterators/cur\-sors,
updating via auxiliary names, easy and clean semantics, avoiding
semantic anomalies) is difficult. The proposal below
(implemented and tested in LOQIS) is a solution that in our
opinion is very simple, universal, and free of many
disadvantages of other solutions.

The basic idea is that an auxiliary name can be used to refer
object temporarily, i.e., only in the context of a subquery.
This blends naturally with our scoping-based approach. We
distinguish two kinds of occurrences of auxiliary names in a
query: declaration and use. The syntax for the declaration is $n
\la q$, where $q$ is an arbitrary query. The declaration
associates the name $n$ with each row in the result of $q$. For
row $r$ returned by $q$, $n(r)$ denotes the corresponding row
returned by $n \la q$.  We allow also such named rows to appear
in $ES$. To be consistent with our previous definitions, we have
to improve the function $nested$: for arguments $n(r)$ it is an identity
function. This means that during opening a new scope such elements
are copied to $ES$ without changes. The binding works as usual,
but with a small difference: when name $n$ occured in a query
is bound to the object $n(r)$ on $ES$, only $r$ is pushed on $QRES$;
name $n$ is not propagated to the result.

\begin{examp}(C.f. MyDatabase.)\vsmall\\
\hsmall $(x \la EMP) \; where \; (x.SAL > 1800)$\vtiny\\
As before, the atomic query $EMP$ returns a single-column table
\{$\row{i_1}, \row{i_5}, \row{i_9}$\}. Application of $x \la$
changes this table into \{$\row{x(i_1)}, \row{x(i_5)},
\row{x(i_9)}$\}. Assume $x(i_1)$ is processed by the $where$
operator. This means the application of $nested$, which pushes
$x(i_1)$ without changes on $ES$. Name $x$ in the predicate
after $where$ is bound to this element, but only $i_1$ is send
to $QRES$; name $x$ is not propagated. The dot operator in a
subquery $x.SAL$ pushes $nested(i_1) = \{i_2, i_3, i_4 \}$ on
the top of $ES$; thus $SAL$ can be bound, as usual, to $i_3$.
Then, the dereferencing and comparison operators will return
$TRUE$. In the result, the whole query will return a
single-column table \{$\row{x(i_1)}, \row{x(i_5)}$\}.

The reader can verify that the SQL-style query
\vsmall\\
\hsmall $(((x \la (EMP \; where \; JOB = "clerk")) \; \times$
$(y \la EMP) \times (z \la DEPT))$\\
\hsmall $where \; (x.SAL > y.SAL \wedge x.EDNO = z.DNO \; \wedge $
$z.MGR = y.ENO)).x$\vtiny\\
returns identifiers of clerks earning more than their managers.
Besides the SQL style, this general mechanism of auxiliary names
allows for many other styles (in particular, the domain calculus
style).
\end{examp}

