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

\section{From data-oriented modeling to object-orientation}

In this section we review briefly the evolution of database languages in 
terms of their binding patterns.  We argue that the expressiveness and 
usability of a database system model is related directly to the 
orthogonality of its binding patterns and that, in retrospect, many ad-hoc 
binding restrictions found in database systems are simply based on the 
choice of an improper implementation technology.

\subsection{Binding names in code to persistent data}
\label{Sec:CD-Binding}

All database management systems with a programming language interface
support C{\r}D bindings.  In a third-generation language, a C{\r}D
binding to a database is established at program run-time using an
explicit operation similar to the SQL \p{connect} statement.  C{\r}D
bindings to individual elements in a database collection are established
using explicit cursor manipulation operations, typically embedded into
program loops.

In fourth-generation languages like Ingres/Windows 4GL \cite{Ing90} or
PL/SQL \cite{Orac90} and in database programming languages like DBPL
\cite{ScMa92a,ScMa94} or E \cite{Rich89}, the outermost program
environment already contains bindings to persistent entities which are
therefore directly accessible in statements and expressions.  Moreover,
these languages provide bulk data types \cite{AtBu86,MaSc91b} with
operations that work on collections of (anonymous) bindings at once.  As
a consequence, programming with persistent bulk data in these languages
is as effortless as programming with volatile data in 3GLs.

Two more pitfalls have been encountered in the implementation of C{\r}D 
bindings.

The first problem results from ill-designed interfaces between
programming languages and DBMS which are unable to handle control
structures found in modern programming languages properly.  For example,
several commercially available embedded SQL versions are based on
statically allocated database communication areas for cursors and query
expressions and therefore do not support recursively nested cursor
loops, as they appear in many DB applications like the classical bill of
material example.  Other SQL versions avoid this particular problem
using a stack discipline for the management of C{\r}D bindings.
Unfortunately, the preprocessor of these systems which inserts
stack-manipulation operations on block entry and exit does not handle
block-structured exceptions as found in C++, ADA and Modula-3 correctly.
Only very few DBMSs support a non-block-structured control flow as it
occurs in languages with coroutines, multiple threads or asynchronous
interrupts.

A second problem facing database programmers is the lack of 
type-independent persistence management (the possibility to make data of 
any type persistent \cite{AtBu86}).  For example, in order to store a 
binding to a single boolean variable in a relational database management 
system it is necessary to create a table that holds a single tuple with a 
single boolean attribute since the binding structure of the relational data 
model does not match the type algebra \cite{AtBu86} of standard programming 
languages.  Similar problems occur with union types (variant records) and 
function types in more advanced, object-oriented models.

\subsection{Binding names in persistent data to flat code}
\label{Sec:DC-Binding-flat}

An object in an object-oriented database can be modeled as an environment 
of bindings and a (hidden) object identifier. 

\begin{xple}peterObj :PersonObject = \k{object} age = 30, married = true, boss = NULL,
     changeBoss = \k{method}(newBoss :PersonObject) \k{self}.boss:= newBoss
\k{end}\end{xple}

Attributes like \p{age, married} or \p{boss} lead to standard D{\r}D
bindings to persistent state variables while a method definition is a
D{\r}C binding from a method name (\p{changeBoss}) to a code fragment
(\p{\k{self}.boss:= newBoss}).  In most object-oriented models, a method
is bound in an environment attached to an object class; however, some
systems (e.g., $O_2$) also support so-called ``exceptional objects''
where methods can be overridden by bindings established on a per-object
basis.  Message names in code, like \p{changeBoss} in the dot expression
\p{peterObj.changeBoss(\ldots)}, are bound dynamically to matching method 
code identified by D{\r}C bindings attached to the object itself 
(\p{peterObj}), its class (\p{PersonObject}) or its transitive superclasses.

D{\r}C bindings are also supported by active database systems where it
is possible to bind a trigger consisting of a condition (a code fragment
that returns a boolean value) and an action (a code fragment that
performs a side-effect) to a persistent data structure (typically a
global collection variable).  Views as attribute values in Postgres
\cite{RoSt87} and ``viewers'' as proposed in \cite{SMRS93} are a third form
of D{\r}C bindings that attach code fragments (returning bulk data
values) to individual persistent data items.

D{\r}C bindings add a new dimension to data modeling since it becomes
possible to attach behavior to shared and persistent data and to adopt a
data-centristic execution model.  In this view, the application logic is
no longer hard-wired statically in ``structured'' application code that
drives the passive database system via read/write instructions.  Instead
of this, the application logic can be divided into semantically rich and
loosely coupled conceptual classes attached to persistent data
structures, and the application system is ``driven'' by messages
dispatched dynamically by the DBMS.

In all systems mentioned so far, the code participating in a D{\r}C
binding has to come from a \e{flat} environment.  For example, the
object-oriented programming languages Eiffel, C++, Modula-3 and Trellis
as well as the object-oriented database systems ObjectStore and O$_2$
have syntax and scope rules that make it impossible to bind a
function that is nested within another function as a method to a
database object.  As a consequence, the only bindings available inside
method code are static global D{\r}D or D{\r}C bindings, and dynamic
bindings established via explicit method arguments (\p{newBoss}), and
the dynamic binding of the distinguished identifier \k{self} to the
receiver of the message.  Analogous restrictions hold for stored
database procedures written in fourth-generation languages and triggers
in active databases.

The rationale behind these restrictions is to simplify the implementation 
of D{\r}C bindings.

A typical implementation of a D{\r}C binding from persistent data to
flat code consists of a volatile object code address plus a persistent
symbolic persistent code reference.  The latter could be a pair
consisting of an object library file name
(\p{/usr/local/lib/libperson.so.1.0}) and a code label name
(\p{person\_changeBoss}) that identifies machine code stored in a
dynamic link library outside the object store itself.  Code generators
for high-level programming languages generate unique code label names
based on message name, class name and an encoding of the method
parameter types (``name mangling'') \cite{ElSt90}.  Augmenting code
label names with object file names makes it possible to distinguish
between method definitions that occur in disjoint versions or variants
of a system derived from the same source text.

A more elegant implementation of D{\r}C bindings to flat code is achieved 
in object-oriented database systems like O$_2$ that manage executable code 
in the object store itself.  In these systems D{\r}C and D{\r}D bindings 
are implemented uniformly as intra-object-store bindings exploiting the 
concept of persistent object identity.


\subsection{Binding names in persistent data to nested code}
\label{Sec:DC-Binding-nested}

The increased modeling power of orthogonal D{\r}C bindings that also handle 
\e{nested} code correctly has been demonstrated by higher-order programming 
languages like Lisp, Scheme, Standard ML, Dylan and Haskell
(higher-order functions) but also by Smalltalk (first-class blocks) and
CLOS.  As a consequence there is a clear evolution in the family of
higher-order database languages from PS-algol \cite{AtMo85a}, Napier88
\cite{DCBM89}, Galileo \cite{ACO85}, P-Quest \cite{MMS92}, Fibonacci
\cite{AGO91} to Tycoon \cite{MaSc92a} allowing programmers to treat
functions, procedures and transactions as first-class computational
entities that can be passed as arguments, returned as results, and
embedded into persistent data structures.

Here, we focus on the semantics of D{\r}C bindings to nested code and do
not discuss the relative advantages of full higher-order models
over plain object-oriented models (see
\cite{ScMa93}).  The following simple example shows a parameterized 
transaction \p{disallowBoss} that overrides an existing method binding
defined for the message \p{changeBoss} of a person object
\p{thisPerson}.  The new D{\r}C binding relates \p{changeBoss} to a
nested method code fragment that depends on the parameter value
\p{thisBoss} of its enclosing transaction (see \cite{AbCa94} for a
detailed discussion of the expressive power of statically nested method
definitions).

\begin{xple}\k{transaction} disallowBoss(thisPerson, thisBoss :PersonObject) = \k{begin}
    \k{let} oldMethod = thisPerson.changeBoss
    thisPerson.changeBoss:= \k{method}(newBoss :PersonObject)
          \k{if} newBoss != thisBoss \k{then} oldMethod(newBoss)
          \k{else} \k{raise} illegalBossException \k{end}
\k{end}\end{xple}

This transaction can be called with person objects as arguments, for 
example, to raise an exception if \p{paulObj} is to become the boss of
\p{peterObj} or if an attempt is made to delete the boss of \p{paulObj}:

\begin{xple}disallowBoss(peterObj, paulObj)
disallowBoss(paulObj, NULL)\end{xple}

A correct representation of the D{\r}C binding for the name \p{changeBoss} 
has to consist not only of a binding to the nested method code but it has also 
to record the environment of global C{\r}D bindings valid for the nested 
code (bindings for the parameter \p{thisBoss} and the variable 
\p{oldMethod} of the enclosing transaction).  Such a [code,
environment]-pair is called a (function) \e{closure}.  The two
transaction calls above yield the following closures:

\begin{xple}
peterObj.changeBoss = [
   code = (\k{if} newBoss != thisBoss \k{then} oldMethod(newBoss) \k{else} \ldots \k{end}),
   globalEnvironment = [thisBoss = paulObj, oldMethod = \ldots] ]
paulObj.changeBoss = [
   code = (\k{if} newBoss != thisBoss \k{then} oldMethod(newBoss) \k{else} \ldots \k{end}),
   globalEnvironment = [thisBoss = NULL, oldMethod = \ldots] ]\end{xple}

Although the code bound to \p{peterObj.changeBoss.code} and 
\p{paulObj.changeBoss.code} is shared, the global environments differ such 
that the execution of the method code in these different environments has 
different semantics.
