% File:    sect2.tex
% Author:  Florian Matthes
% Date:    22-FEB-1994 
% Purpose: Paper on Persistent Threads

\section{Bindings in persistent systems}
\label{Sec:Bindings}

In this section we introduce a terminology for the description of bindings 
to data, code and threads in persistent systems which we will use 
throughout the paper.

A binding is an association between a name and a computational entity
from a specific semantic domain \cite{Stra67}.  We also say that a name
is bound to a computational entity.  An environment is a (possibly
ordered) collection of bindings.  Names are used to identify entities in
an environment.  Different names can be bound to the same entity
(sharing, aliasing). The details of this identification process (static
scoping, dynamic scoping, user-defined conflict resolution) and
mechanisms to manipulate environments (import/export, inheritance,
record extension, imperative update \cite{Dea89}) are irrelevant for the
purpose of this paper.

Entities can be atomic (like integers or booleans) or structured (like
records, objects or functions).  Structured entities typically consist
of environments.  For example, the fields of a record lead to bindings
from field names to other entities.  Therefore, bindings can be used to
model (recursive) relationships between entities.

Entities can be flat (like records) or nested (like functions in
Algol-like languages).  In a nested entity, names bound in a global
outer environment are automatically visible in a local inner
environment.  As will be seen in sections~\ref{Sec:CD-Binding} and
\ref{Sec:DC-Binding-nested}, the semantics of bindings from and to
(dynamically) nested entities requires particular attention.

Entities can be transient (like local program variables) or persistent
(like database tables).  Virtually all database systems restrict
environments of persistent entities to contain only bindings to other
persistent entities since bindings to volatile entities would lead to
``dangling references''.  Such constraint violations are avoided in many
systems by a transitive reachability rule: Every entity reachable from a
persistent entity becomes persistent, too.  In reachability-based
systems, there is a so-called ``persistent root environment'', for
example, the set of all globally-defined database names in O$_2$
\cite{BDK92}.  An entity is made persistent by making it reachable
through chains of bindings (e.g., database definition, class extent)
starting from this persistent root environment.

An alternative approach to persistence management (supported, for example, 
by ObjectStore \cite{LLOW92}) is to define the lifetime of an entity at 
data-creation time using ``persistent new'', respectively ``volatile new'' 
operations and to replace bindings to volatile entities at 
transaction-commit time by a binding to a distinguished \p{NULL} entity.

The following three categories of structured entities are of particular 
interest in extended (higher-order) database modeling: 

\k{Persistent Data (D)} describe the persistent state of an information 
system by a collection of computational entities related through bindings.  
The structure (types) of the persistent entities and their bindings are 
described by a database schema.

\begin{xple}\label{Xple:persDB}persDB = \k{database}
      peter = [age = 30, married = true, boss = NULL],
      paul = [age = 30, married = true, boss = persDB.peter], \ldots
      persons = \{persDB.peter, persDB.paul, \ldots\}
\k{end}\end{xple}

In this example, the name \p{persDB} is bound to a database, i.e.  a 
persistent environment that stores bindings for the database variable names
\p{peter, paul} and \p{persons}.  For example, \p{paul} is a name bound to 
a record (an environment with three bindings).  One of these bindings
associates the name \p{boss} to the record identified by the name
\p{peter} within the environment \p{persDB}.  The set bound to the name
\p{persons} defines an environment of anonymous bindings.

\k{Code (C)} is a description of operation sequences that query and update 
volatile or persistent entities and bindings.

\begin{xple}\label{Xple:changeAll}\k{procedure} changeBoss(pers :Pers) = pers.boss:= persDB.paul;
\k{transaction} changeAll() = \k{for each} p \k{in} persDB.persons \k{do} changeBoss(p);
\end{xple}

Code involves names to describe bindings to other code (\p{changeBoss} 
referenced in the body of \p{changeAll}), bindings to persistent data 
(\p{persDB.persons}, \p{persDB.paul}), and bindings to volatile data 
(\p{p}, \p{pers}).  In statically-scoped languages, the binding of a name 
in a code fragment to a matching name in its environment is determined by a 
textual analysis of the code and of the database schema.

A \k{Thread (T)} is a representation of code \e{in the process of being
executed}.  A thread describes a single sequential flow of control in a
program.  Having multiple threads in a program means that at any instant
the program has multiple points of execution, one in each of its
threads.  Unlike operating system processes, multiple threads can
execute within a single (persistent) address space, permitting multiple
threads to access shared variables in addition to local variables.

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
\k{Conceptual Model} & \k{Language Model} & \k{Implementation Model} \\
\hline
entity               & variable         & data      \\
behavior             & function         & code      \\ 
activity             & continuation     & thread    \\
\hline
relationship         & name             & binding   \\
\hline
\end{tabular}
\end{center}
\caption{Corresponding notions at different levels of conceptualization}
\label{Fig:Notions}
\end{figure}

It may be helpful to compare our terminology with corresponding notions in 
language models and conceptual models as summarized in 
figure~\ref{Fig:Notions}.  Since in this paper we are interested also in 
implementation aspects of persistent threads, we are using a rather 
system-oriented terminology.  In our setting (as opposed to, for example, 
visual programming), the correspondence between high-level conceptual 
notions like entities, behavior, activities, relationships and their system 
counterparts (data, code, threads, bindings) is often established indirectly 
via formal language models expressed in terms of variables, functions, 
continuations and names bound in scopes.  Our system argument that threads 
should be treated as first-class persistent data could therefore be 
rephrased in high-level models by requiring activities to be viewed as 
first-class entities that can participate freely in abstractions like 
aggregation and classification.

A thread is created by submitting a non-parameterized code fragment
(e.g., the body of the transaction \p{changeAll}) and (persistent) data
(e.g., \p{persDB}) to an evaluator (\p{\k{eval} (changeAll, persDB)}).
As described in section~\ref{Sec:Semantics} the semantics of the
evaluator can be defined inductively by rules that map thread states to
thread states and that perform side-effects on data.  A thread state
subsumes bindings to the code fragments currently being executed and a
dynamic environment that records the current bindings from names
occurring in the code to local and global entities.  In most programming
and query language implementations thread states are represented as
records that reference stacks of so-called ``activation records'', one
for each function or query invocation.

The following thread state describes a snapshot of the execution of the
transaction \p{changeAll} against the database \p{persDB}.  More
precisely, it describes the state of the transaction while executing the
function \p{changeBoss} during the first iteration of the \k{for each}
loop, immediately preceding the assignment of the value \p{persDB.paul}
to the field \p{boss}.

\begin{xple}\label{Xple:thread1}thread1 = [result = persDB.paul, dynamicContext = [
    code = (pers.boss:= result),
    localEnvironment = [pers = persDB.peter],
    globalEnvironment = [persDB = \k{database}\ldots\k{end}],
    dynamicContext = [
        code = (\k{for each} p \k{in} notYetVisited \k{do} changeBoss(p)),
        localEnvironment = [p = persDB.peter, notYetVisited = \{persDB.paul, \ldots\}],
        globalEnvironment = [persDB = \k{database}\ldots\k{end}, changeBoss = \k{procedure} \ldots],
        dynamicContext = [] ] ] ]
\end{xple}

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
\k{Approach}              & \k{Bindings} & \k{Description}\footnotemark\\
\hline
database programming      & C{\r}D       & code bound to data \\
object-oriented databases & D{\r}C       & persistent data bound to code \\
transactional programming & T{\r}C       & threads bound to code \\
\hline
activity management       & D{\r}T       & persistent data bound to threads \\
\hline
\end{tabular}
\end{center}
\caption{Predominant binding patterns (see text)}
\label{Fig:Patterns}
\end{figure}

In this example the thread state consists of the result of the current 
subexpression (the right-hand-side of the assignment, i.e., 
\p{persDB.paul}) and a dynamic context (\e{continuation}) that describes
the code still to be executed together with the bindings valid within
this code.  The next instruction to be executed is the assignment
\p{(pers.boss:= result)}.  The binding of the parameter name \p{pers}
can be obtained from the local environment which has been established on
entry to the function \p{changeBoss}.  The dynamic context of the
function (the state of its ``caller'', i.e.  \p{changeBoss}) is captured
also by a continuation.  On function return, evaluation continues with
the bindings of this continuation.  The local variable \p{notYetVisited}
is used to control the iteration.  Since the dynamic context of the
transaction \p{changeAll} is empty, the thread will terminate on return
from this transaction.

\addtocounter{footnote}{0}\footnotetext
{$X$ bound to $Y$ means that names in entities of category $X$ are bound
to entities of category $Y$, i.e. that the semantics of $X$ depend on
the semantics of $Y$.}


Since entities of each of the three categories above -- data, code and 
threads -- may contain bindings, there are nine possible binding patterns 
between computational entities in fully orthogonal object systems.  In 
figure~\ref{Fig:Patterns} we list four of these binding patterns which we 
regard as ``historic'' milestones in the development of persistent system 
models:

\begin{itemize}

\item In database programming languages it is possible to write 
algorithmically-complete code that establishes C{\r}D bindings to 
persistent data and that modifies the state of persistent entities and 
their relationships expressed as D{\r}D bindings.  However, code is still 
separated strictly from persistent data in the sense that reverse 
bindings are not supported.

\item This restriction is lifted in object-oriented databases where
D{\r}C bindings extend the semantics of data entities to also include
code fragments (method code) which express behavioral aspects.
Similarly, in active databases it is possible to attach code (conditions
and actions) as triggers to persistent data (relations, classes).

\item In multi-user (database) systems there are multiple concurrent user 
sessions accessing shared data via transactional code.  Each active
transaction corresponds in our terminology to a single thread that is
bound (via a T{\r}C binding) to application code which in turn is bound
to shared (persistent) data.  However, threads are strictly separated
from persistent data and code in the sense that a thread cannot access
(query, store, update) the set of code or data bindings held by itself
or by other threads.

\item In this paper we argue that threads understood as dynamic 
environments of bindings are highly relevant for novel,
activity-oriented applications and, therefore, should gain first-class
status in future database models and not be hidden behind a specific
built-in binding pattern (transactions).  As detailed in
section~\ref{Sec:Programming}, mechanisms to establish bindings from
code, from data, and from threads to threads are very helpful to manage
cooperative and distributed activities.  In particular, D{\r}T bindings
from names in persistent data to threads naturally lead to the concept
of persistent threads in reachability-based persistent systems, which we
regard as highly relevant to \e{long-term activity management}.

\end{itemize}

The semantics and the implementation of pure D{\r}D bindings like the
binding of the name \p{persDB.paul.boss} to the entity \p{persDB.peter}
in \p{persDB} (on p.~\ref{Xple:persDB}) and of pure C{\r}C bindings like
the binding of the name \p{changeBoss} in the function \p{changeAll} are
sufficiently well understood that we restrict ourselves in the following
discussion to the binding patterns highlighted in
figure~\ref{Fig:Patterns}.

