 \section{An Abstract Machine Model}

 

In this section we present an abstract machine model, on which
query language expressions can be evaluated. A component of a
state of the machine is a store, as described above. Other
components include an environment stack and a result stack for
the store of intermediate results.  We discuss some commands of
the machine, and its facility for parallel execution.

\subsection{The Environment Stack}
 
The atomic components of queries are the names and constants.
The evaluation of names means binding them to data units, 
depending on the context.  Consider, for example, a query
in a relational database that asks for the names of employees
satisfying some condition:\\
\hhh {\bf select} {\em NAME} {\bf from} {\em EMP} {\bf where}
\ldots\\
\noi The evaluation of the query involves finding a set of
bindings for {\em EMP}, then removing some of them which do not
satisfy a predicate after $where$. Each binding for {\em NAME}
is then determined in a context associated with one of the
bindings to {\em EMP}; it is bound to the appropriate $NAME$
sub-object inside an EMP object.

\subsubsection{Stack Organization}
 
While bindings for simple relational queries, such as the one
above, seem to be well understood, this is not the case for more
complex queries. For example, in a query that selects the
salaries of employees that earn more than their managers, {\em
SAL} is used three times, and there is a need to define how each
occurrence is bound. The problem is aggravated in models that
admit deeply nested structures, possibly, with repeated (sub)
attributes. The binding of a name to its meaning may then depend
both on the positions of the name in the data structure, and its
use in the query.
 
To deal with this issue, we propose a well known concept of
{\em environment\/}. Abstractly, an environment is an
association of names and objects. It is constructed
incrementally, by accumulating local scopes and the scope added
last is the first to be visited in a search. Thus, the
environment is subdivided into parts, called {\em sections\/},
which form  the {\em environment stack}, denoted {\em ES}.
 
We assume that each section of $ES$ stores identifiers of store
objects.  Given an identifier, the complete object can be
retrieved.  In particular, the name stored in the object can be
retrieved, to be compared with the name for which a binding is
requested. Thus, storing identifiers suffices for establishing
bindings.

In a (run-time) stack in programming languages a stack section
typically contains local data such as parameters and local
variables of a procedure. Such local data {\em lives} on the
stack. In contrast, we are dealing here with global data, that
live in the database, and continue to exist not only when a
stack section is removed, but also when query evaluation has
terminated and the complete stack has disappeared. Thus the
objects themselves will be stored in the store, and their
identifiers stored in the appropriate stack section(s). This
scheme allows the same object to be referenced from several
sections (in contrast to the run-time stack where an object
occurs in precisely one section). The semantics we are going to
deal with depends on this property. Note that in a run-time
stack a name occurring in a program is bound to one object. In
contrast, we allow a section in {\em ES} to associate several
objects with a name, as e.g. for the EMP name.

In summary, our proposal generalizes  the environment stack as
used in programming languages in two major ways: (1) The stack
contains identifiers of both persistent and volatile store
objects, which exist outside the stack; (2) Binding is a
multi-valued, rather than a single-valued. This is intimately
related to the set orientation and parallelism inherent in query
semantics.

In an implementation based on our semantics many optimizations
are possible, such as storing names with the identifiers in
sections, avoiding long lists of identifiers of objects having
the same name, and performing some bindings during compilation.
Some of these optimisations are implemented in LOQIS; they are
not discussed here.
 
We assume that at the beginning of the evaluation of a query the
environment stack consists of one section containing identifiers
of all persistent {\em root} database objects, such as the $EMP$
and $DEPT$ objects in $MyDatabase$.
 
\subsubsection{Binding via Stack Operations}
 
Binding a name $n$ is performed by a search for one or more
objects associated with that name in the environment stack. The
search follows {\em scope rules}. The simplest rule is to
strictly follow the structure of the stack, from the top down
towards the bottom. The search terminates when it finds a
section that contains one or more bindings for the given name.
In that case, the set of {\em all} objects associated with the
name in that section is returned as the result of the search.
The result we denote by $search(n)$. If no section with bindings
for the given name exists, the search terminates at the bottom
of the stack, returning an empty set. This simple search
strategy will be changed to accommodate more sophisticated scope
rules, e.g., skipping irrelevant stack sections for binding
names used inside a procedure.
 
Changes to the environment have to update the stack by adding or
removing sections at its top, using the traditional operations
$push$ and $pop$. These operations correspond to opening a new
scope and closing a scope, respectively.

In programming languages, opening a new scope corresponds to an
activation of a block or a procedure. In a query language, it
corresponds also to the evaluation of a query component in a
context determined by another component. In the general case,
this operation depends on both the structure of the query and
the structure of the data. Consider, for example, the query
$DEPT.LOC$. Each possible binding for $LOC$ is determined by a
binding for $DEPT$. That is, first $DEPT$ is bound, in general
to many identifiers $i_1, i_2,..., i_k$ (one for each
department). Each identifier $i_j$ identifies a department
object, and this object defines a scope in which names such as
DNO, DNAME, MGR, LOC are associated with the objects that make
up the department object. The semantics of the dot operation is
that bindings for $LOC$ are determined in each of these scopes.
 
Let $o =<i, n, v>$ be an object, with identifier $i$.  We denote
by ${\em nested}(i)$ the following set of identifiers: If $o$ is
a set object, then $nested(i)$ is the set $v$; if $o$ is a
pointer object $<i, n, j>$, then $nested(i) = \{j\}$; if $o$ is
a value object, $v \in V$, then $nested(i) = \emptyset$.
For uniformity, we extend the function $nested$ for values $v
\in V$: $nested(v) = \emptyset$. Then we extend the function to
sequences of identifiers and values by defining the result to be
the union of the value of the function on the components.  For
example (c.f. {\em MyDatabase}), $nested (i_1 ) = \{i_2, i_3,
i_4 \}$, $nested(i_4) = \{i_{13}\}$, $nested(i_{3}) =
nested(1800) = \emptyset$,  and $nested(<i_1, i_{13}>) = \{i_2,
i_3, i_4, i_{14}, i_{15}, i_{16} \}$.
 
Going back to the evaluation of $DEPT.LOC$, we see that for a
given binding $i$ for $DEPT$, the scope in which it makes sense
to look for a binding for $LOC$ is $nested(i)$. If this set is
pushed as a new scope on the stack then the search for bindings
for $LOC$ will find the objects representing the location(s) of
the given department, as required. As will be shown, this
approach is a core of the definition of many query operators,
including $where$, dot, join, and quantifiers.
 
\subsection{The Query Result Stack}
 
In addition to the environment stack $ES$, we also need a place
for intermediate query results.  These are kept on another
stack, called the {\em query result stack} ($QRES$).  In
particular, at the end of evaluation its top holds the answer to
the query. We assume that an intermediate result is always a
{\em table}, where a table is a multi-set (bag) of {\em rows\/},
all of the same width. Rows may contain atomic values or
identifiers, i.e. their elements belong to $V \cup I$.  For
uniformity, we represent single values or identifiers as tables
having one row and one column ($1 \times 1$ tables), and do not
distinguish between such a table and the element in it. An
example table, referring to {\em MyDatabase}, is presented
below; it may represent an answer to the query ``Get employee
names, their department's names, and 10\% of their salary''.
\begin{center}
\begin{tabular}{|lll|}
\hline
$i_2$ & $i_{14}$ & 250\\
$i_6$ & $i_{18}$ & 200\\
$i_{10}$ & $i_{18}$ & 150\\
\hline
\end{tabular}
\end{center}
 
A table is not in the form we want to see for printed query
results. We assume, however, that the visualisation of it, if
necessary, can be done by a some procedure (e.g. $display$)
taking the table as an argument.

\subsection{Set Orientation and Parallelism}

\begin{sloppypar}
The query $DEPT.LOC$ illustrates an important characteristic of
queries, namely parallelism. The bindings for $LOC$ are to be
performed {\em for each\/} binding found for $DEPT$. In
principle, choosing a binding for $DEPT$ and then searching for
bindings for $LOC$ can be done in any order, even in parallel.
For queries, there is no difference between a parallel or a
sequential execution in some arbitrary order; however, there is
a significant difference when updates are considered. Consider,
for example, the update `increase the salary of each employee by
10\% if smaller than the average of the employees' salaries.' In
a parallel execution, the average is the same for all updates.
In a sequential execution, each update changes the average and
thus may influence the next update. To precisely define the
semantics of a bulk updates, parallelism is a very useful
notion, even if the real implementation will be sequential.
\end{sloppypar}

We assume that our machine has sequencing, denoted by `;',
parallel loops denoted by {\em foreach $i$ in $C$ do in
parallel\ldots end foreach}, and regular sequential loops
denoted similarly, without ``in parallel'.' The degree of
parallelism is determined by a specified collection: each
element $i$ in the collection corresponds to, or generates an
evaluation stream.  The element $i$ is available for use, as a
parameter, in the stream.  We assume that when a parallel loop
is started, a separate processor is allocated to each stream.
Each processor has its own stacks: $QRES$ is initially empty,
and $ES$ is a copy of the common stack.  Each branch of the
parallel loop continues as a process running one of these
processors, and the processors execute concurrently and
asynchronously. The streams merge into one stream when they
terminate. The store is shared among the parallel streams.
 
There are issues that we need to worry about in this idealized
parallel execution. One is how these streams are merged when
they terminate. We assume that when a branch terminates, $ES$
returns to its state at the time just before the loop started;
thus, at the end environment stacks are identical for all
streams. Considering QRES, when a parallel stream executes, it
does not change any part of the stack below the level at the
starting time, and that at the end the local stack contains one
cell storing the partial result. When the parallel branches
merge, these tables are merged, forming one table at the top of
the common $QRES$. The merge function depends in general on on
the query operator being actually evaluated.

