% File:    sect3.tex
% Author:  Florian Matthes
% Date:    19-MAY-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 or PL/SQL and in
database programming languages like DBPL \cite{ScMa94} or E
\cite{RCS93}, 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{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}\small{}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 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.  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}, 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}\small\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}\small
peterObj.changeBoss=[
   code=(\k{if} newBoss!=thisBoss \k{then} \ldots \k{end}),
   globalEnv=[thisBoss=paulObj,oldMethod=\ldots]]
paulObj.changeBoss=[
   code=(\k{if} newBoss!=thisBoss \k{then} \ldots \k{end}),
   globalEnv=[thisBoss=NULL,oldMethod=\ldots]]\end{xple}

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