% File:     fide-pas.tex
% Date:     6-JUL-1993
% Authors:  Florian Matthes, Joachim W.~Schmidt
% Purpose:  Euro-Arch Talk JWS
%
\documentstyle[12pt,a4,xple_sl,epsf]{article}

\newcommand{\figwidth}{0.6\textwidth}
\newcommand{\colwidth}{0.48\textwidth}
\setlength{\textheight}{24.5cm}
\setlength{\textwidth}{16cm}
\pagestyle{empty}

% also defined in tycoon.sty:
\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\k}[1]{{\bf #1}}
\newcommand{\comment}[1]{\par{[*** #1 ***]}\par}
\newcommand{\p}[1]{{\frenchspacing\sl{}#1}}
\def\longhrule{\par\hbox to \linewidth{\hss
               \hbox to \textwidth{\hrulefill}}\par}

% Tycoon general:
\newcommand{\TL}{{\sc Tl}}
\newcommand{\TML}{{\sc Tml}}
\newcommand{\TSP}{{\sc Tsp}}
\newcommand{\engl}[1]{{\em #1\/}}
\newcommand{\fsub}{{F$_{\leq}$}}

% Specific for this text:
\newcommand{\arr}{$\rightarrow$}
\newcommand{\var}[1]{\k{var}($\alpha_{#1}$)}
\newcommand{\id}[1]{$\alpha_{#1}$}

\title{\Large\bf Building Persistent Application Systems\\
       in Fully Integrated Data Environments:\\
       Modularization, Abstraction and Interoperability\thanks{This
research is supported by ESPRIT Basic Research, Project FIDE, \#6309.}}
\author{\normalsize\begin{tabular}{ccc}
  Joachim~W.~Schmidt& Florian Matthes & Patrick Valduriez \\
\multicolumn{2}{c}{\small{}Universit\"at Hamburg, DBIS} & {\small INRIA} \\
\multicolumn{2}{c}{\small{}Vogt-K\"olln Stra{\ss}e 30} & {\small Roquencourt, B.P. 105} \\
\multicolumn{2}{c}{\small{}D-22527 Hamburg, Germany} & {\small F-78153 Le Chesnay Cedex, France}\\
\end{tabular}}
\date{}

\begin{document}
\maketitle
\thispagestyle{empty}

\begin{abstract}
\noindent Research and development in the FIDE project on Fully Integrated Data
Environments has led to the concept of Persistent Object Systems (POS)
which generalize database systems by re-interpreting schemas as type
definitions and databases as typed variables in addition to treating
lifetime as a type-independent property. Furthermore, FIDE develops
uniform linguistic interfaces for data modelling, computation and
communication, and extends database, programming and communication
technology to enable integrated application development based on
interoperating POSs.

As a consequence of such an integrated view, formerly disjoint concepts 
such as databases, program and module libraries, files or repositories can 
now be treated uniformly as POSs differentiated essentially by the types of 
objects they contain and by the operational abstractions they provide. 

Based on state-of-the-art database technology, this paper outlines FIDE
results in extending databases and providing the integrated technology
considered necessary for the construction and maintenance of Persistent
Application Systems.  Since our main goal is to
improve substantially a system's capability of persisting successfully
over time in changing environments, particular emphasis will be placed
on systems scalability and its consequences for POS interoperability.
\end{abstract}

\section{Introduction: Application Development in Fully Integrated Data Environments}

Successful application development nowadays is rarely based on extensive 
\e{coding} of application programs. Instead, there is a strong tendency to 
application systems \e{modelling} by exploiting the services provided
through open and modular environments already populated with
prefabricated and packaged functionality and information. Examples of
such environments are databases, function libraries and module
repositories.

This shift in application development has motivated \e{service suppliers}
to improve their market by providing safer and functionally extended
servers, in addition to allowing \e{service consumers} to conveniently
buy functionality and information by simply specifying their needs (---
and paying for it). However, since such services are developed
independently of each other with widely varying conventions on naming,
typing, binding and whatever else may describe their interfaces,
application developers who wish to exploit multiple services within a
single application find themselves working in quite complex and finally
unfriendly and unsafe environments. Examples are interfaces between C
programs and SQL databases, window system or RPC packages.

In the ESPRIT Basic Research project FIDE our response to the situation
sketched above is the development of a technology for Fully Integrated
Data Environments. Central to the FIDE Research and Development is the
concept of Persistent Object Systems (POS) which can be seen as a
generalization of database systems along the following lines:

\begin{itemize}
\item re-interpreting database schemas as type definitions and databases
as typed  variables,
\item treating lifetime as a property of computational objects which is 
independent of their type,
\item developing uniform linguistic interfaces for data modelling, computation 
and communication,
\item extending database, programming and communication technology to 
enable integrated application development based on interoperating POSs.
\end{itemize}

As a result of such a generalized view, formerly disjoint concepts such
as databases, program and module libraries, files or repositories can
now be treated uniformly as POSs differentiated essentially by the
types of objects they contain and by the operational abstractions they
provide.

Persistent Object Systems are required to provide the basis for characteristic 
interoperation needs such as:

\begin{itemize}
\item Persistent Object Management: Objects which outlive program executions 
or exist independently of any application impose specific requirements
on their naming, scoping and binding mechanisms. Such mechanisms have to
cope not only with the fact that object creation and object use may
happen at different times but also on different platforms using
diifferent tools.

\item Data and Function Control: Within a single language, important
classes of constraints on data and functions can be expressed by various
type systems and for many of them there exist efficient algorithms to
prove constraint satisfaction.  Similarly, language-independent
mechanisms have to be provided for persistent objects shared across
platforms.

\item Generic Interfaces and Functionality: The degree of re-usability of 
Persistent Object Systems is strongly correlated with the genericity of
the services offered by the POS. Querying, report generation, form
management, sorting and searching are examples of services accomplished
best by instantiating generic algorithms with type-specific arguments.
On the system level, substantial portions of interoperation protocols,
e.g. link functions or marshalling procedures, can be obtained by
providing generators with object signatures and platform specific
information.
\end{itemize}
	
This presentation outlines FIDE results in providing the integrated
technology considered necessary for the construction and maintenance of
Persistent Application Systems as interoperating POSs. Section
\ref{Sec:DDB} reports briefly on the state-of-the-art of the
integration and distribution technology developed in the context of
Database Management Systems. The scope of the discussion is widened in
section \ref{Sec:FIDE} by outlining a framework for interoperability
across a variety of services represented by Persistent Object Systems. A
specific environment for database programming with particular emphasis
on interoperability across sites, languages and platforms is discussed
in section \ref{Sec:DBPL}. The paper concludes with a short reference on
requirements for open communicating environments\footnote{Earlier
versions of the material presented in this paper can be found in
\cite{ScMa93,OzVa91,MaSc91b}}.
 
\section{Overview: Distribution and Integration of Database
Functionality}\label{Sec:DDB}

The success of Database Management Systems (DBMS) as commercial software 
products lies principally in their well-packaged functionality required by 
many bulk data processing applications: controlled persistent storage and 
optimized concurrent iteration. Although the concentration on a particular, 
well-chosen functionality is a major cornerstone of the DBMS success, it 
also contains the roots for its limitations. Marketed as closed, sealed 
servers, DBMSs contribute little to the interoperability \e{across} services. 
DBMSs interoperate with other systems only through their built-in 
interfaces which are either limited in functionality (e.g. SQL) or low in 
technology (e.g. cursor interfaces). Therefore, applications which require 
a variety of services, e.g. for objects on disk, on the screen, in memory 
or on wire, usually end up in low-level interface coding on the basis of 
strings, addresses and error codes. 

On the other hand, in recognition of this shortcoming the database
community is further improving interoperability \e{between} databases.
This work can be classified roughly as covering two dimensions: the
vertical dimension addresses interoperability issues between components
of one logically related database transparently managed by a DBMS
distributed over the sites of a network, while the horizontal dimension
researches interoperability in the setting of multiple independent
databases.

In this section we provide a short overview of the state-of-the-art of both 
dimensions in addition to reporting on research in the combined areas of 
distributed multidatabases. In the subsequent sections we open the 
discussion and outline a framework for interoperability across a variety of 
services, present a particular system for interoperable database 
programming and conclude with requirements for open communicating 
environments. 


\subsection{Databases as Distributed Systems}

A distributed database (DDB) is a collection of multiple, logically
interrelated databases distributed over a computer network
\cite{OzVa91,OzVa93}. A distributed database management system (DDBMS) is then
defined as the software system that manages a DDB transparently
according to the following assumptions:
\begin{itemize}

\item Data are stored at a number of sites. Each site is assumed to consist 
logically of a single processor. 

\item The processors at individual sites are interconnected by a computer 
network thereby realizing a loose interconnection between independently
operating processors.

\item Data in a DDB are logically connected by relationships defined 
according to some structural formalism and accessed at a high level via 
some common interface (e.g. the relational model and its query languages). 

\item The system has the full DBMS functionality. It is neither a 
distributed file system nor a transaction processing system
\cite{Bern90}. 


\end{itemize}

These assumptions are valid for today's technology. Most of the existing
distributed systems are built on top of local area networks with sites
consisting of a single computer. However, next generation DDBMS
environments will include multiprocessor database servers connected to
high speed networks linking them and other data repositories to client
machines that run application code as well as participating in the
execution of database requests \cite{Tayl87,KiLo89,ZdMa89}.

A distributed DBMS as defined above is only one way of providing
database management support for a distributed computing environment. In
\cite{OzVa91} a working classification of possible design alternatives
was presented distinguishing three dimensions: autonomy, distribution,
and heterogeneity.

\begin{itemize} 

\item Autonomy refers to the distribution of control indicating the degree 
to which individual DBMSs can operate independently. It involves factors 
such as information exchange between component systems, independent 
transaction execution, and the degree of individual DBMSs modification. 

\item Distribution deals with data. Usually 
two cases are considered: physical data distribution over multiple 
communicating sites or data concentration at only one site. 

\item Heterogeneity in distributed systems ranges 
from hardware heterogeneity and differences in networking protocols to 
variations in data managers. DBMS heterogeneity relates to 
data models, query languages, interfaces, and transaction management 
protocols. 
\end{itemize}

Distribution is identified as one of the major characteristics of
next-generation database systems, which will be ushered in by the
penetration of database technology into new application areas with
different requirements than traditional business data processing and the
technological developments in computer architecture and networking. The
nature of distribution in next generation DBMSs is a controversial
issue. There are a number of documents that attempt to define
alternative positions \cite{SSU90,ABW*90,Manifesto90,Ston90a} all
sharing at least the following two characteristics:

\begin{itemize}

\item Data model extension: Future data models need to be more powerful 
than the relational one, yet without compromising its advantages (data 
independence and high-level query languages). When applied to more complex 
applications such as CAD/CAM or software design the relational model 
exhibits severe limitations in terms of complex object support, type system 
and rule management. To address these issues, three important technologies, 
persistent polymorphic languages, object-oriented databases and knowledge 
base management are currently undergoing heavy research. 

\item Improved interoperability support: An expected consequence of 
applying database technology to an extended range of application domains
is the proliferation of different, yet complementary, DBMSs and other
generalized information services. Thus, interoperability of such systems
within a computer network becomes increasingly important. Fully
integrated data environments require significant improvements in
interoperability. In the following subsections, interoperability is
addressed in more detail showing that it is receiving increasing
attention in the joint community of databases and programming languages.

\end{itemize}

\subsection{Integrated Views on Multiple Databases}\label{Sec:IntegratedViews}
	
As already indicated above, a \e{multidatabase} organization is an
alternative to logically integrated distributed databases. The
fundamental difference between the two is the degree of autonomy
afforded to the component data managers at each site. While the
independent DBMSs may have, for example, facilities to execute
transactions, they have no notion of executing distributed transactions
that span multiple components (i.e., they do not have global concurrency
control mechanisms or distributed commit protocol implementation). The
integration issue of multiple databases definitely deserves more space
than available in this paper. In this subsection, we concentrate on
issues of global database schema management and highlight some of the
potential of object-oriented software for systems with high autonomy .


\subsubsection{Global Schema Definition and Management Issues}

The arguments against full transparency gain more weight in
multidatabase environments. The additional autonomy of individual
components and their potential heterogeneity make it more difficult
(some claim impossible) to support full transparency. A major difficulty
relates to the definition of a global conceptual schema (GCS) as a
specification of the structure and constraints of the global database.
The definition and role of the GCS is well understood in the case of
integrated distributed database systems: it defines a logical single
image over physically distributed data. The same clear understanding
does not exist in the case of multi-DBMSs with autonomy
\cite{ScYu90}. One way the integration issue can be tackled is to treat the 
global conceptual schema as a generalization defined over local
conceptual schemas. Studies along this line have been conducted before
\cite{MoBu81,DaWa84} and their practical implications with respect to
transparency need to be reconsidered.

Finally, there are arguments that the absence of a GCS may be a
significant advantage of multi-DBMSs over DDBMSs \cite{LiAb87}. A
language sufficiently powerful to access multiple databases without
defining a GCS is presented in \cite{LiAb87}.  A significant research
problem is the nature of such multi-DBMS languages. Problems with
languages that are as powerful as the union of the component ones arise,
as discussed in \cite{ScYu90}, with non-standard query operators of
component DBMSs or with component DBMSs providing different interfaces
to general-purpose programming languages. A solution may lie in
extensible languages.

\subsubsection{Object-Orientation and Multidatabase Interoperability}

A central issue is the development of software technology that can deal 
inherently with autonomous system components. A prime candidate technology 
is object-orientation. Here we only comment on its role in addressing the 
interoperability issues. Object-oriented systems treat the entities in 
their domain typically as instances of some abstract type. In the case of 
database systems these entities are usually data objects. However, it is 
quite common for object-oriented models to treat every entity uniformly as 
objects. Thus, for example, interface definitions, user queries, or 
programs are considered objects in certain object models and the technology 
is primarily concerned with providing the necessary tools and methodology 
for the consistent management of such entities. 

Applying object-orientation to interoperability leads to the systematic
and abstract treatment of autonomous DBMS components as software objects
which can interoperate only through well-defined interfaces. There has
been some initial work on the requirements of such interoperation
interfaces \cite{Mano90,ScYu90,HeZd90}, an issue which clearly needs
and deserves further investigation.


\subsection{Database Interoperability: Multiple Databases in Dis\-tri\-bu\-ted 
Environments}

Finally, since multiple databases are expected to be available in 
distributed environments, the two problem spaces sketched above cannot be 
treated independently. This subsection outlines some of the issues raised 
when queries and transactions are run against multiple databases in 
distributed environments and concludes with a short reference to standards 
and their relevance for interacting autonomous systems. 


\subsubsection{Query Processing}

The autonomy and potential heterogeneity of component systems create 
problems in query processing and optimization. A fundamental difficulty is 
global optimization when local cost functions are not known and local cost 
values cannot be communicated. Proposals have been made to concentrate on 
semantic optimization based only on qualitative information \cite{ScYu90}, 
however, semantic query processing is not fully understood either. There 
seems to be a great potential for hierarchical query optimizers which 
perform some global query optimization and leave it to each local system to 
perform further optimization on the localized subquery. Although this 
partitioning may not lead to optimal solutions, it will improve the 
tractability of the optimization problem. The emerging standards may also 
make it easier to define global cost models as well as share cost 
information. 


\subsubsection{Transaction Processing}

For transaction processing in autonomous multi-DBMSs, the following 
consensus on a global transaction execution model seems to emerge: Each 
component DBMS has its own transaction processing services (i.e., 
transaction manager, scheduler, recovery manager) and is capable of 
accepting local transactions and running them to completion. In addition, 
the multi-DBMS layer has its own transaction processing components (global 
transaction manager, global scheduler) in charge of accepting global 
transactions accessing multiple databases and coordinating their execution. 


Autonomy requires that global transaction management be performed on top
of the existing local transaction execution functions. Heterogeneity has
the additional implication that the transaction processing components
involved may employ different concurrency control, commit, and recovery
protocols and the coexistence of local and global transaction further
complicates scheduling \cite{BrSi88}. If serializability is used as the
correctness criterion, it has to be ensured that the serialization order
of global transactions at each site are the same. Some solutions use
global serializability of transactions as their correctness criteria
(see, e.g., \cite{Geor91,BrSi88}) while others relax serializability
(e.g., \cite{DuEl89,Bark90}). 

A further difficulty is the development of reliability and recovery
protocols for multi-DBMSs and their integration with concurrency control
mechanisms. Even though the topic has been discussed in some recent
works \cite{BaOz91,Geor90,WoVe90}, these approaches are initial
engineering solutions.


\subsubsection{Autonomy and Standards}

Probably one of the fundamental impediments to further development of 
distributed multidatabase systems is the lack of understanding of the 
nature of autonomy. An initial characterization that has been made 
identifies three different forms of autonomy: design autonomy, 
communication autonomy, and execution autonomy. Other characterizations 
have also been proposed \cite{GaKo88}. Furthermore, most researchers 
treat autonomy as if it were an all-or-nothing criterion and not as a range 
of possibilities. It seems essential to precisely 
\begin{itemize}

\item isolate a range of autonomy levels
\item identify, on each level, the appropriate degrees of database consistency 
\item  define transaction models appropriate for different levels of autonomy. 
\end{itemize}

This might lead to a layered interoperability architecture for autonomous 
and possibly heterogeneous DBMSs, similar to ISO Open System 
Interconnection. Some work along this line is already under way within the 
Remote Data Access (RDA) standard, possibly improving substantially the 
development of practical solutions to DB interoperability. 

\section{Towards Fully Integrated Data Environments}\label{Sec:FIDE}

Generalizing from database applications leads to the conclusion that
application development benefits greatly from an integrated technology
which supports modularized persistent systems and generalized module
definition and management. In this section we present a higher-order
core language which, essentially by modularizing name and binding
spaces, supports module definition and interaction in the presence of
module persistence. Reference is made to Modula-2 \cite{Wirt85b}, to
DBPL \cite{ScMa91a,MRSS92}, a modular Database Programming Language with
persistence, and to Tycoon \cite{MaSc92a,Matt93}, which is used as a conceptual
basis for our core language.

\subsection{Modularity: The Basis for Interoperability}\label{Sec:Modularity}

Based on the experience with Modula-2, the Database Programming Language
DBPL exploits the power of modular programming and module management for
data-intensive and long-lived applications. DBPL programs are structured
into modules with well-defined import/export relationships. Definition
modules provide signatures for type, value and
location\footnote{Locations are the conceptual basis for sharing and
updates. In this paper, however, we do not discuss the subtle type issues
related to location bindings. The interested reader is referred to
\cite{ScMa93}.} bindings defined in
implementation modules.  Program modules export a single, parameterless
function value, the main program.

An interface and a skeleton DBPL module exporting basic data
types and values to handle telephone numbers would look as follows:
\begin{center}
\begin{tabular}{ll}
\begin{minipage}[t]{\colwidth}\footnotesize
\begin{xple}\label{Keyword:PhoneIface}
\k{definition module} Phone;
\k{type} Number = \k{array} [0..20] \k{of char};
\k{var} localPrefix, myNr :Number;
\k{procedure} operator(prefix:Number):Number;
\k{end} Phone.
\end{xple}
\end{minipage}
&
\begin{minipage}[t]{\colwidth}\footnotesize
\begin{xple}
\k{implementation module} Phone;
\k{procedure} operator(prefix :Number) :Number;
\k{begin} \ldots \k{return} \ldots \k{end} operator;
\k{begin} (* module initialization: *)
    localPrefix:=``4940''; 
    myNr:=concat(localPrefix,``85312'');
\k{end} Phone.
\end{xple}
\end{minipage}
\end{tabular}
\end{center}
During type checking of these compilation units, the DBPL compiler
extracts type and value signatures from the definition module and
verifies that the bindings defined in the implementation module match
their corresponding signatures. In the next section we introduce a
conceptual model that allows us to explain this process and the
compilation of client modules against a compiled interface in more
detail. This level of detail is required to generalize the simple 
Modula-2 module mechanism to distributed, multi-language database
environments (see Sec.~\ref{Sec:DBPL}).

\subsection{A Core Language for Fully Integrated Data Environments}
\label{Sec:Model}

In this section we introduce (informally) a model to describe the
naming, typing and binding concepts involved in Persistent Object System
interoperability. The model itself (subsequently referred to as the
\e{Tycoon POS model}) is based on concepts of higher-order type systems
and is sufficiently expressive to serve as a language-independent
framework for program translation, generation and binding. The
presentation of the actual DBPL system and its gateways in the following
sections makes use of a limited subset of the Tycoon POS model. The
potential of the full model is discussed in \cite{MaSc93}.

The Tycoon POS model is based on the notion of \e{types},
\e{signatures}, \e{values} and \e{bindings}. Types are understood as (partial)
specifications of values. Values and types can be named in bindings for
identification purposes and to introduce shared or recursive structures at the
value and the type level. Signatures act as (partial) specifications of static
and dynamic bindings. Bindings are embedded into the syntax of values, i.e.
they can be named, passed as parameters, etc.

The syntax for \e{types} includes a set of base types $B_i$ (\k{Int},
\k{Real}, \k{String}, \ldots), a type constant \k{Any} (the trivial
type), user-defined type variables, function types, aggregated
signatures, parameterized type expressions (type operator definitions)
and type operator applications:
\begin{xple}
Type::= $B_i$ $|$ \k{Any} $|$ TypeName $|$ \k{Fun}(Signatures) Type $|$ \k{Sig}(Signatures) $|$
            \k{Oper}(Signatures) Type $|$ Type(Bindings)
\end{xple}
Function types are used to describe the signatures of parameterized
objects like functions, procedures, methods, generators or relational
queries. Aggregated signatures are used to describe the signatures of
language entities like records, tuples, structures, modules, object
definitions, database definitions, or object files.

Type operators denote parameterized type expressions that map types or
type operators to types or type operators.  Many programming languages
have built-in type operators that map types to types (\p{Array},
\p{List}, \p{File}, \p{Pointer}, \ldots).

\e{Signatures} are sequences of value, location or type signatures. A
value signature associates a value name with a type (\p{peter
:Student}). A type signature associates a type name with
a supertype specification (\p{Student $<$:Person}).
\begin{xple}
Signatures::= \{TypeSig $|$ ValueSig $|$ LocationSig\}
TypeSig::= Name $<$:Type  ValueSig::= Name :Type  LocationSig::= \k{var} Name :Type
\end{xple}
Aggregated signatures are used to describe named \e{declarations} as
they occur in function headings, module signatures, \k{external}
declarations in C programs or in database schema definitions.

Signatures specify invariants on bindings and allow the verification of  the
correctness of (value or type) expressions depending on names without
having access to the actual binding in which the name is defined. For example,
based on the signature \p{age :Int}, the type-correctness of the
expression \p{age + 1} can be verified without having access to the
actual value bound to \p{age}. Signatures therefore play a central role
in type-safe module systems.

The syntax for \e{values} includes base values $b_{ij} :B_i$, like 0, 3.4,
``xyz'', \k{true}, a canonical value of the type \k{Any}, function
values including built-in functions like \p{+, --, *} of type
\p{\k{Fun}(x :\k{Int}  y: \k{Int}) \k{Int}} and user-defined
functions and aggregated bindings:
\begin{xple}
Value::= $b_{ij}$ $|$ \k{any} $|$ \k{fun}(Signatures)Expr $|$ \k{bnd}(Bindings)
\end{xple}
The syntax \k{bnd}(Bindings) defines that aggregated value and type bindings
are first-class values, generalizing classical concepts like value, function
and type aggregation in records, structures, abstract data types or modules. 
The syntax of \e{expressions} in functions is deliberately not specified here in
order to be able to describe POS involving multiple languages. 

\e{Bindings} are sequences of type, value and location bindings. A type
binding \p{Age$\equiv$\k{Int}} defines a name for a type. A value binding
\p{pi=3.1415} defines a name for a value. 
\begin{xple}
Bindings::= \{TypeBnd $|$ ValueBnd $|$ LocBnd\}
TypeBnd::= Name$\equiv$Type  ValueBnd::= Name=Value  LocBnd::= Name=\var{i} Value
\end{xple}
Bindings model type, constant, variable and function declarations in
programming languages and instances of database schemas in database
systems.

As usual, types are intended to classify values, and signatures are to
classify bindings. Moreover, it is possible to define
\e{generic} functions (functions that take type bindings as arguments),
value-dependent type operators, abstract data types (bindings that
contain partially-specified type components and operations on that
type). The formal type rules for this model (defining well-formed types,
the types of values, the subtype relationship between types and the
signatures of bindings)  become therefore quite subtle. 

In traditional systems, types and signatures are handled exclusively  at
compile-time, while values and bindings only appear at run-time. In
persistent systems, the distinction between compile-time and run-time
blurs, and it becomes possible, for example, to inspect value and type
bindings at compile-time, giving rise to powerful reflective algorithms
\cite{S*92}.

We now return to the DBPL example presented in
section~\ref{Sec:Modularity} and demonstrate how its modules are
modelled in the Tycoon POS model: 
\begin{xple}\label{Keyword:CompileEnv}
CompileEnv $\equiv$ \k{Sig}(Phone $<$:\k{Sig}(Number $<$:\k{array}...
     \k{var} localPrefix :Number  \k{var} myNr :Number  operator :\k{Fun}(prefix :Number) Number)
     linkPhone :\k{Fun}(imports :\k{Sig}()) Phone)
\end{xple}
The definition module is represented as a type signature which associates
the interface name \p{Phone} (understood as a type variable) with a
supertype that is an aggregate of all types and values signatures
exported by the interface. The implementation module is
represented as a single function, \p{linkPhone}, that takes an
aggregated binding of all imported module values (in this case an empty
binding) and returns a binding that conforms to the interface signature
\p{Phone}.\footnote{As we will see later, we would lose some modelling
precision if we were to treat the implementation module as a simple
binding of type \p{Phone}.}

The signatures of \p{Phone} and \p{linkPhone} are both elements of a
flat name space modelled by a signature bound to the type variable
\p{CompileEnv}. In a typical DBPL
system implementation, this name space is managed implicitly via search
paths to look up compiled interfaces, called ``symbol files''.

The code generated for the implementation module \p{Phone} is stored as
a named binding in a flat name space that collects all compiled modules.
This name space is represented in the Tycoon POS model as a named value
\p{linkEnv} whose type matches the signatures specified by
\p{CompileEnv}:
\begin{xple}
linkEnv = \k{bnd}(linkPhone=\k{fun}(imports :\k{Sig}()) \ldots)
\end{xple}
This name space is also utilized by the DBPL linker to compose all
module initialization functions that make up an executable application
program. The main module
\begin{xple}
\k{module} Main \k{import} Phone; \ldots  \k{end} Main.
\end{xple}
is represented by the following link function:
\begin{xple}
linkMain :\k{Fun}(imports :\k{Sig}(phone :Phone)) Main
\end{xple}
It leads to the following module initialization sequence:
\begin{xple}
initEnv=\k{bnd}()
phoneE=initEnv$\cup$\{phone=linkEnv.linkPhone(initEnv)\}
mainE=phoneEnv$\cup$\{main=linkEnv.linkMain(phoneE)\}
\end{xple}


\subsection{The Potential of Persistent Objects}\label{Sec:Persistence}

This section demonstrates how the concept of \e{orthogonal persistence}
\cite{AtBu86} as found in DBPL extends the potential for
interoperability along two new dimensions: sharing over time and sharing
between multiple users.

DBPL introduces the notion of a \e{persistent module} (database
module) to define persistent location bindings in a
strongly-typed programming environment. For example, the following
local changes marked by underscores are sufficient to turn
\p{localPrefix} and \p{myNr} into persistent variables 
(compare Sec.~\ref{Keyword:PhoneIface}).
\begin{center}
\begin{tabular}{ll}
\begin{minipage}[t]{\colwidth}\footnotesize
\begin{xple}
\underline{\k{database}} \k{definition module} Phone;
    \ldots (* see Sec.~\ref{Keyword:PhoneIface} *)
\k{end} Phone.
\end{xple}
\end{minipage}
&
\begin{minipage}[t]{\colwidth}\footnotesize
\begin{xple}
\k{implementation module} Phone;
    \ldots (* see Sec.~\ref{Keyword:PhoneIface} *)
\underline{\k{database definition}} \k{begin}
    localPrefix:=``4940''; 
    myNr:=concat(localPrefix,``85312'');
\k{end} Phone.
\end{xple}
\end{minipage}
\end{tabular}
\end{center}
The compilation of these modules defines a collection of signatures that
is identical to the non-persistent environment \p{CompileEnv} defined in
Sec.~\ref{Keyword:CompileEnv}. The import semantics of persistent
modules differ from volatile modules: the link-time execution of the
module initialization code \p{linkPhone} of a persistent module does not
return a new set of bindings to newly created process-local locations
(copy semantics), but returns bindings to locations that are
\e{shared} between all programs importing the persistent module
(reference semantics).  Therefore, side effects created by one
application on persistent variables are visible to other applications
importing the same persistent module:
\begin{xple}
\k{module} Main1 \k{import} Phone;
\k{begin} Phone.localPrefix:= ``004940" \k{end} Main1.

\k{module} Main2; \k{import} Phone;
\k{begin} Phone.localPrefix:=concat(Phone.localPrefix,``-") \k{end} Main2.
\end{xple}
The sequential execution of \p{Main1} and \p{Main2} would lead to the
following location bindings:
\begin{xple}
\k{bnd}(localPrefix=\var{1}``004940-''  myNr=\var{2}``494085312''  
         operator=\k{fun}(prefix :Number)\ldots)
\end{xple}
The statement sequence marked by the keywords \k{database definition
begin} is executed only once during the lifetime of the database module
\p{Phone}, namely before it is imported for the first time into a DBPL
application program.

The main advantages of persistent modules lie in overcoming the naming,
typing and genericity problems associated with file-based solutions
\cite{ScMa93} without introducing additional linguistic complexity in the
programming environment. Since the name space populated by database
modules is not only persistent but also \e{shared} between several
programs, it is necessary to ensure that destructive updates of
persistent data structures performed by concurrent applications are
performed \e{atomically} to handle system and program failures
graciously.  Therefore, DBPL supports user-defined (parameterized)
\e{transactions} to handle the concurrency-control, recovery and
integrity issues based on standard database transaction models.

\section{DBPL: An Interoperable Database Programming
Environment}\label{Sec:DBPL} 

A modular environment with persistence and sharing is particularly
suited to support long-lived applications which need large collections
of data.  Since, over time, such applications have a strong tendency to
extend functionality and to proliferate information, they also require
scalability into open and distributed environments. In this section we
outline FIDE results in functionality extension and in interoperability
support. We present interoperability examples across database servers,
programming languages and system platforms.

\subsection{Service Extension: Bulk Types in DBPL}\label{Sec:Bulk}

In the process of building a POS, it is often necessary to handle large,
dynamic homogeneous collections of objects (e.g., class extents).
Furthermore, it is necessary to represent relationships between object
collections and to perform efficient, set-oriented update and retrieval
operations. Database systems have been designed to provide specific
modelling and system support for these tasks. Expanding on our running example, let
us assume that there is a need to register variable amounts of telephone
entries composed of person names and telephone numbers.
This kind of information is adequately described by the following
relational database definition:
\begin{xple}\label{Keyword:IngresDB}
\k{createdb} SQLPhoneDB \ldots
\k{create table} register (name \k{char}(50), num \k{char}(21))
\end{xple}
The language SQL provides simple, efficient, declarative read and write
access to the information held in the database (\k{insert into table},
\k{delete from table}, \k{select} \ldots \k{from} \ldots \k{where}
\ldots). However, it turns out to be surprisingly difficult to access SQL
databases from application programs, e.g., to use the \p{Fax} service to
send a message to every person named ``Smith''. We do not want to go
into the detailed problems of SQL host language embedding, but there
arise numerous difficulties due to the differences in naming, typing and
binding between SQL and host languages such as C, Cobol or Ada (see
\cite{ScMa93} for details).

DBPL overcomes these difficulties by using the persistence and
modularization concepts described in Sec.~\ref{Sec:Modularity} in
addition to extending the language by a generic bulk types operator
\k{relation} and predefined polymorphic operations on values of type
relation. Due to the orthogonality of the DBPL type system, it is
possible to define a richer set of data structures than it is possible
in the classical relational model, however, this flexibility is not required
here
\cite{ScMa91a}. The SQL database schema is represented by the
following persistent DBPL module:
\begin{xple} 
\k{database definition module} PhoneDB; \k{import} Phone;
\k{type} Entry = \k{record} name :String num :Phone.Number \k{end};
\k{type} Register = \k{relation} name \k{of} Entry;
\k{var} register :Register;
\k{end} PhoneDB.
\end{xple}
Names have been assigned to all types to be re-usable in application
programs importing \p{PhoneDB}. It is worth noting that, of course, more
than one database module can be defined in a DBPL application, thus
realizing the concept of multi-databases discussed in
Sec.~\ref{Sec:IntegratedViews}. DBPL also provides a rich set of set-oriented update
operators and an extended relational calculus including recursion based
on fixed-point semantics to express bulk operations \cite{ERMS91}:
\begin{xple}
register:+ Register\{\{``John", ``249"\}\}; 
print(Register\{\k{each} n \k{in} register:n.num$>$``240''\});
\end{xple}
DBPL has special (generic) type rules for the built-in relation
operators, e.g., to capture the fact that the set-oriented insertion
operator ``:+'' can be applied to relations of arbitrary element type,
as long as the right-hand side expression is also a relation of the same
element type.  In \cite{ScMa93} it is demonstrated how type operators of
the Tycoon POS can be used to capture accurately these built-in type
rules for relation types. This formalization is a only a first step
towards a generalized type-safe handling of user-defined bulk data types
\cite{MaSc91b,MaSc93}.

\subsection{The DBPL/SQL Gateway}

The DBPL language and system supports bindings to 
external persistent objects in addition to internal persistent DBPL
objects \cite{MRSS92b}.  For example, the following modification of the
header of module \p{PhoneDB} binds the location variable \p{register}
to an \e{external} SQL relation \p{register} defined in an Ingres
database named \p{SQLPhoneDB}: 
\begin{xple}
\k{database definition} \underline{\k{for} Ingres} \k{module} PhoneDB; 
\k{import} Phone; \ldots \k{var} register :Register; \k{end} PhoneDB.
\end{xple}
All DBPL statements and expressions referring to external relation
variables are translated fully transparently into SQL update and
selection expressions submitted to the Ingres SQL database management
system.  These SQL expressions typically take DBPL program variables
(value and location bindings) as arguments and return (set) values that
are converted appropriately for further processing within DBPL. For
example, the query
\begin{xple}
\k{if} \k{all} n \k{in} register n.phone $>$ x \k{then} \ldots \k{end}
\end{xple}
is translated into a \k{select from where} SQL expression that
uses the actual value stored in the DBPL location \p{x} of type
\k{String}. Depending on the cardinality of the set-valued result, a boolean
value is then returned to the compiled DBPL code.

It should be noted that DBPL can handle arbitrarily nested (possibly
recursive) query expressions that mix volatile relations, persistent
DBPL relations residing in local or remote databases and SQL database
relations. Therefore, much care has been devoted to develop evaluation
heuristics that minimize data transfer and make best use of index
information available for individual relations. Evaluation strategies
are not determined at compile-time but depend on cardinality and
index information available at run-time.

Again, a conceptually simple generalization of an existing programming
language concept suffices to overcome the interoperability deficiencies
of todays database programming interfaces that have developed in
a system-driven, bottom-up fashion.

Although the system details of the DBPL/SQL gateway are quite delicate
and often require ad-hoc case analysis to achieve good system
performance, this specific gateway implementation follows a more general
pattern that directly reflects the model of typed programming languages
in terms of types, signatures, values and bindings presented in
Sec.~\ref{Sec:Model}. Our general experience in extending a language
$L_{int}$ by generic gateways to an external language $L_{ext}$	 (i.e.,
to embed $L_{ext}$ as a sublanguage of $L_{int}$) is described in more
detail in \cite{ScMa93}. Specific requirements can be stated on the type
and expression syntax of $L_{int}$ and $L_{ext}$ as well as on the tools
for mapping signatures and bindings between $L_{int}$ and $L_{ext}$. In
the DBPL/SQL scenario this is achieved by using
\e{DynamicSQL}, a set of library routines shipped with the Ingres DBMS
to create cursors and communication buffers to convert Ingres values
(element-by-element, attribute-by-attribute according to their type
structure) to DBPL values and to pass arguments (of scalar types) to SQL
query strings.

Our work on gateway construction can be summarized by the experience
that the task is simplified considerably if the external functionality
is provided through well-structured libraries with abstract and
``minimal'' signatures, and not through extensive, ``verbose''
(SQL-like) and informally described interfaces.

\subsection{Cross-Language Interoperability}\label{Sec:Cross-Language}

The most primitive (but also most common) form of cross-language
interoperability is achieved by having a standardized,
language-independent link format (e.g., COFF of Unix System V) that
allows static bindings in a language $L_{imp}$ to bind to values or
locations defined in another language $L_{exp}$. In this setting,
$L_{imp}$ is able to import from $L_{exp}$. The next step is to define
standardized, language-independent parameters passing conventions that
allow argument values or argument locations defined in $L_{imp}$ to be
bound dynamically to function parameters defined in $L_{exp}$. If the
roles of $L_{imp}$ and $L_{exp}$ can be interchanged, full
cross-language interoperability (including ``call-back'' mechanisms) is
supported.

Since this interoperability takes place at the value, location and
binding level only, all naming and typing consistency control enforced
by the use of type names, types and signatures in compilers is
effectively lost in this scenario.

The DBPL compilers for VAX, Sparc and Motorola architectures attack this
problem by providing the DBPL programmer with a mechanism to recover
type and signature information for external bindings via so-called
\e{foreign definition modules}. For example, the interface of the
\p{Fax} module defined in Section~\ref{Keyword:FaxInterface} could be
revised as follows to define a FAX service implemented in the
programming language C:
\begin{xple}
\k{definition} \underline{\k{for} C} \k{module} Fax;
\k{import} Phone;
\k{type} Status = (error, busy, done); \ldots  
\k{end} Fax.
\end{xple}
The compiler will enforce the consistent use of the bindings exported by
the external \p{Fax} package in all importing DBPL programs. For
example, it would catch the following type error in the application of
the function \p{Fax.dial} that attempts to pass an integer value as a
string argument:
\begin{xple}
\k{module} SendFax; \k{import} Phone, Fax;
\k{begin} Fax.dial(853228);Fax.send(``Sample fax.");Fax.hangup(); \k{end} SendFax;
\end{xple}
The skeleton of a C-program to provide value bindings matching the
signatures \p{Fax} looks as follows.
\begin{xple}
\k{typedef} \k{char}* Phone\_Number
\k{typedef} \k{int} Status
\#\k{define} error ((Status) 0)  
\#\k{define} busy ((Status) 1) \ldots
Status Fax\_dial(\k{char}* number)\{ \ldots \}
Status Fax\_send(\k{char}* text) \{ \ldots \k{return} done; \ldots \}
\k{void} Fax\_hangup() \{ \ldots \}
\end{xple}
Since relation types and relation operations are fully integrated into
the DBPL language, they can be freely combined with the cross-language
binding mechanisms:
\begin{xple}
\k{for each} b \k{in} register :contains(n.name, ``Smith'') \k{do} Fax.dial(n.num); \k{end}
\end{xple}
It is also possible to call DBPL transactions on bulk objects from C.

\subsection{Cross-Platform Interoperability}\label{Sec:Cross-Platform}

The distributed version of DBPL \cite{JGLR88,JLRS88} exploits the basic
module concepts to add an additional layer of type-safety to standard
remote procedure call mechanisms (RPC) in federated client-server
programming models.

To give access to a local fax service at a site called
``CentralOffice'', this site would compile the following \e{remote
definition module} and then \e{export} the compiled description
(typically together with its source text for documentation purposes)
only to those clients on the network who are to be authorized to use the  
service.
\begin{xple}\label{Keyword:FaxInterface}
\k{\underline{remote} definition module} Fax \underline{\k{for}
``CentralOffice''}; 
\k{import} Phone;
\k{type} Status = (error, busy, done);
\k{procedure} dial(number :Phone.Number) :Status;
\k{procedure} send(text :\k{array of char}) :Status;
\k{procedure} hangup();
\k{end} Fax.
\end{xple}
In this scenario, signatures of compiled definition modules accumulated
in the compilation environment serve as protocol specifications.
Frequently clients require distribution transparency. In this case it is
of considerable advantage if a main program
\begin{xple}\label{Keyword:SendFax}
\k{module} SendFax; \k{import} Phone, Fax;
\k{begin} Fax.dial(``853228'');Fax.send(``Sample fax.");Fax.hangup(); \k{end} SendFax;
\end{xple}
stays textually unchanged whether it uses a local definition module
\p{Fax} or the above remote definition module \p{Fax} for ``Central
Office'' offered by a server somewhere in the network. This distribution
transparency is achieved as usual by a client stub and a server stub
that marshal and unmarshal the arguments and results supplied to
functions defined in the remote definition module.

In terms of the Tycoon POS model, RPC-based communication mechanisms are
an implementation technology that enables the creation of function value
bindings between names in a client program and function values in a
server program. Using plain RPC mechanisms it is not possible to
directly define location bindings spanning machine boundaries. In
particular, we would have to revise the module interface \p{Phone} not
to directly export the locations \p{localPrefix} and \p{myNr}. However,
using the concept of persistent variables introduced in
section~\ref{Sec:Persistence} these restrictions are lifted in DBPL by
the provision of truly distributed persistent variables.

The crucial feature of DBPL is to retain (static) type safety across
machine boundaries by maintaining a distributed compilation environment
that allows local and remote modules to \e{share} signatures for
type checking purposes and to share module bindings for transparent connection
establishment. 


% 5 --------------------------------------------------------------------
\section{Concluding Remarks}

After seven years of development, the DBPL system has now reached a
level of maturity and interoperability that makes its linguistic
abstractions readily available for implementors of non-trivial
Persistent Object Systems on several hardware-platforms.\footnote{The DBPL
system is distributed by Hamburg University.}

From a research point of view, an interesting side-effect of this DBPL
implementation effort is an insight into repeating patterns of language
and system extension requirements, some of which are outlined in
Sec.~\ref{Sec:DBPL}. Consequently, our current work in the Tycoon
project \cite{Matt93,MaSc91b,MaSc92a} investigates languages and
architectures that facilitate such incremental, problem-specific
extensions in a type-safe environment.

In contrast to DBPL, Tycoon takes a rather radical approach by not
maintaining upward compatibility with existing programming languages
(Modula-2) and data models (extended relational models). Also its
internal protocols for store access, program representation and linkage
do not adhere to pre-existing standards. The rationale behind the design
of Tycoon is to provide a lean language and system environment that
provides just the kernel services and abstractions needed to define
higher-level, problem-oriented ``languages'' and ``data models'' and
provide an ``ideal'' basis for systems extensibility and
interoperability.

% ----------------------------------------------------------------------
{\small
\bibliographystyle{florian}
\bibliography{florian}
}

\end{document}
