% File:    infosys.tex
% Author:  Florian Matthes, Joachim W. Schmidt
% Date:    15-OCT-1993
% Update:  22-FEB-1994
%	   AR adaption to FBI-Berichte format
% Purpose: Information Systems Article 
%	   [including comments from Matthias & Dennis]
%
\documentstyle[11pt,epsf,twoside]{article}

\textheight 23cm
%\leftmargin 0cm
\oddsidemargin 0.5cm
\evensidemargin 0.5cm
\textwidth 15cm
\setlength{\baselineskip}{2.0\baselineskip}
\topmargin -0.6cm
% -- Macros:
\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\p}[1]{{\tt{}#1}}
\newcommand{\k}[1]{{\bf{}#1}}
\newcommand{\nfnf}{NF$^2$}

%\title{\vspace*{4cm} \normalsize Bericht Nr. xxx\\[6ex]
%\Large\bf The DBPL Project$^1$:\\[0.2cm]
%Advances in Modular Database Programming
%}
%
%\author{Florian Matthes \and Joachim W.~Schmidt}
%
%\date{$ $ \\[0.4cm] \hspace*{8.5cm} \normalsize FBI-HH-B-xxx/94\\[5cm]
%Februar 1994\\[3ex]
%Fachbereich Informatik\\
%Universit\"at Hamburg\\
%Vogt-K\"olln-Str. 30\\
%D-22527 Hamburg \\
%Federal Republic of Germany \\
%{\small \{J\_Schmidt,matthes\}@dbis1.informatik.uni-hamburg.de}
%\vspace*{0.5cm}
%\footnotetext[1]{This research has been supported in part by
%ESPRIT Basic Research, Project \#892 (DAIDA), \#3070 (FIDE), \#6309
%(FIDE$_2$).} 
%\setcounter{footnote}{1}
%}
\begin{document}
\begin{center}
{\large 
{\huge Fachbereich Informatik der Universit\"at Hamburg} \\ [0.5cm]
Vogt-K\"olln-Str. 30 $\Diamond$ D-22527 Hamburg/Germany \\ [0.5cm]
{\Large University of Hamburg - Computer Science Department} \\ [4cm]
Bericht Nr. 168 $\bullet$ Report No. 168
\vspace*{1cm} \\
{\LARGE \bf The DBPL Project:\\ [0.6cm]
Advances in Modular Database Programming} \\ [1cm]
{\bf Florian Matthes \hspace*{2cm}  Joachim W.~Schmidt} \\ [0.5cm]
{\small \{J\_Schmidt,matthes\}@dbis1.informatik.uni-hamburg.de} \\[2.5cm]
{\Large FBI-HH-B-168/94} \\ [1cm]
March 1994 \\ [2.5cm]
\begin{tabular}{ccc}
\hspace*{6cm}                 & \hspace*{1cm} & \hspace*{6cm}  \\
In die Reihe der Berichte des &               & Accepted for Publication in the Report \\
Fachbereichs Informatik       &               & Series of the Department of Computer \\
aufgenommen durch	      &               & Science by
\end{tabular} 
$ $ \\ [0.5cm]
Prof. Dr. M. Jantzen and Prof. Dr. W. Menzel
}\normalsize
\thispagestyle{empty}
\end{center}
\newpage
\textheight 22cm
$ $ \\[1.5cm]
\begin{abstract}
\thispagestyle{empty}
\noindent
\thispagestyle{empty}
In the DBPL project we tackled the problem of supporting data-intensive
applications in a single framework, clean and simple in its conceptual
foundation and free of technical mismatches.  Conceptually, we based the
DBPL language on Modula-2 and added three built-in extensions:
a parametric bulk type constructor for relations;
a module concept which supports sharing across programs and implies
persistence and a procedure concept with transactional semantics (serializability and recovery). 
They were considered necessary (and sufficient) for data-intensive
applications at that time.

Besides reporting on project achievements (resulting in a
mature product) and spin-offs,
we also present our insight in good-quality project design and its
dependency on conceptual simplicity and implementational strictness.
This also includes early recognition of the essential project
``terminator'' which, in our project, was Modula-2's monomorphic type
system and its intrinsic restrictions on systems extensibility.
\vspace*{1cm}
\begin{center}
\bf{Zusammenfassung}
\end{center}
Ziel des DBPL Projekts war die Unterst\"utzung datenintensiver
Anwendungen in einer einheitlichen Umgebung, die sauber und einfach in
ihren konzeptuellen Grundlagen ist und keine technischen M\"angel
besitzt. Konzeptuell basiert die Sprache DBPL auf Modula-2 und drei
statisch integrierten Konzepten: einem parametrisierbaren
Massendatentypkonstruktor f\"ur Relationen, einem Modulkonzept zur
Unterst\"utzung gemeinsam genutzter persistenter Daten und einem Prozedurkonzept mit transaktionaler Semantik (Serialisierbarkeit und Fehlererholung). Diese wurden damals als notwendige (und ausreichende) Basis f\"ur datenintensive Anwendungen angesehen.

Neben den Ergebnissen des DBPL Projekts (das in einem reifen Produkt
endete) und eng verwandter Projekte stellen wir auch unsere Erkenntnisse \"uber qualitiativ anspruchsvolles Projektdesign vor, insbesondere dessen Ab\-h\"ang\-ig\-keit von kon\-zep\-tu\-eller Einfachheit und konsequenter Implementierung. Eingeschlossen ist auch die fr\"uhe Erkennung des Faktors zur Projektbeendung, der im monomorphen Typsystem von Modula-2 und den daraus folgenden inh\"arenten Einschr\"ankungen der Sys\-tem\-erwei\-ter\-bar\-keit zu finden ist.
\end{abstract}
\newpage
\oddsidemargin 1cm
\evensidemargin 1cm
\textwidth 14cm
\section{Introduction}
\setcounter{page}{1}
Our research\footnote{This research has been supported in part by
ESPRIT Basic Research, Project \#892 (DAIDA), \#3070 (FIDE), \#6309
(FIDE$_2$).}
in database programming languages started in the mid 70ies
when we first suggested some high-level language constructs for data of
type relation \cite{Schm77b}.  The prime goal of the related R\&D
projects was to understand better and relate the data modeling
requirements of programs and databases and to support data-intensive
application development by systems free of conceptual and technical
mismatches.

This research can be divided clearly into two series of projects,
reflecting both the increasing demands on database programming but also
our better understanding of the field. The first run of projects, which
is evaluated in this paper, started with Pascal/R
\cite{Schm77b,Schm78,Schm80} and culminated recently in the delivery of
a mature implementation of the DBPL system\footnote{The DBPL System is
distributed through Hamburg University.}
\cite{ScMa93b,MaSc93a,ScMa92,MRSS92,MaSc89}.  Here database programming
support is based on \e{monomorphic type systems} resulting in a fixed
selection of type constructors which is hard-wired into DBPL and laid
out to span a wide type space which also includes bulk data types.
Around 1990 we started transferring our DBPL experience into a new set
of projects based on \e{polymorphic type systems} which enable add-on
bulk type definitions \cite{MaSc91b} and a more open approach to system
construction.  This ongoing experience is referred to briefly at the end
of the paper.

For DBPL we chose Modula-2 \cite{Wirt85b}, a modular system programming
language, as its algorithmic core. Our development of specific language
extensions required by data-intensive applications (such as bulk types,
iteration abstractions, transactions and persistence abstractions) was
guided by a strict adherence to the widely accepted language design
principles of \e{simplicity}, \e{orthogonality} and \e{abstraction}
\cite{Stra67}. This is to be seen in direct contrast to some DB-language
developments -- notably SQL -- which appear to be driven by ad-hoc
definitions and series of local extensions.

The paper is structured as follows: in section~\ref{Sec:Rationale} we
review the rationale behind our design of DBPL that sets DBPL apart from
extended database query languages, persistent programming languages and
conceptual modeling languages. We then present the essential DBPL
language concepts that support bulk data structuring, persistence
abstraction and declarative bulk data manipulation
(Sec.~\ref{Sec:DBPL-Language}). In section~\ref{Sec:DBPL-System} we shed
some light on the extensions to relational database and procedural
programming language technology that we had to develop to support DBPL's
orthogonal and fully integrated language model. 

Due to the longevity of the DBPL project (the first language report
appeared in 1985 \cite{EEKM85}, the most recent version of the system
was released at the end of 1992 \cite{MRSS92a}), it is interesting to
review briefly the evolution of DBPL (Sec.~\ref{Sec:DBPL-History}) and
to highlight spin-off research projects (Sec.~\ref{Sec:DBPL-SpinOff})
that relied heavily on the availability of DBPL as a stable,
algorithmically complete database programming language. These spin-offs
expanded into the area of distributed systems, interoperability and
database design environments.  We conclude in
section~\ref{Sec:Termination} by justifying our DBPL project decision to
``declare success and quit'' -- keeping in mind DBPL's goals and means.

\section{The Rationale behind DBPL}
\label{Sec:Rationale}

Data-intensive applications are characterized by their needs to model
and manipulate {\em heavily constrained} data that are {\em long-lived}
and {\em shared} by a user community. These requirements result directly
from the fact that databases serve as (partial) representations of some
organizational unit or physical structure that exist in their own
constraining context and on their own time-scale independent of any
computer system. Due to the size of the target system and the level of
detail by which it is represented, such representational data may become
extremely voluminous. In strong contrast to the need for global
management of large amounts of {\em representational data},
data-intensive applications are also required to process small amounts
of local {\em computational data} that implement individual states or
state transitions.

In essence, it is that broad spectrum of demands -- the difference in
purpose, size, lifetime, availability etc.\ of data -- combined with the
need to cope with all these demands within a single conceptual framework
that is decisive in the design of a database programming language
\cite{ScMa91d}.

In DBPL \cite{ScMa92,MRSS92,MaSc89}, we address the above issues by
incorporating a set- and rule-based view of relational database
modeling into the well-understood system programming language Modula-2.

\subsection{Conceptual DBPL Foundations}

The leitmotiv behind the DBPL design was the exploitation and {\em
integration} of a solid, well-understood conceptual framework capable of
capturing consistently the wide range of data-intensive application
requirements --- and not the desire to implement new theoretical
concepts in isolation.

Classical \e{type systems} and the \e{relational data model} are the
cornerstones of the DBPL language design. Both contributions provide an
enlightening foundation from a technological as well as from a
theoretical point of view. However, the revealing new experiences are
made at the border where types (and expressions, selectors,
functions \ldots) and data models (and queries, views, transactions
\ldots) meet and have to be understood, one in light of the other.

The DBPL language and system both rely heavily on conceptual and
theoretical input from the following research areas: programming
language foundations (typing, scoping, binding; \cite{MaSc89,ScMa90a}),
compilation technology (type checking, local data flow analysis,
intermediate languages, separate compilation; \cite{ScMa90b,Matt93}),
extended relational models (data constructors, bulk operations, query
languages and their expressive power), query optimization
(transformations at compile- and run-time, cost models, search
strategies; \cite{JaKo83}), recursive query evaluation (fixed point
semantics, stratification, recursive rule definition; \cite{ERMS91}),
concurrency control (multi-level concurrency control and recovery for
complex objects; \cite{ScMa90b}), and distribution models (transaction
procedures, sagas, compensating transactions; \cite{JGLR88,JLRS88}).

As indicated in the preceding references, our DBPL research contributed
to the further development of some of these conceptual and technological
foundations. In general, however, one can say that the DBPL project
stayed more or less inside the boundaries drawn by conventional language
technology and concentrated on improving the linguistic support for
state-of-the-art database technology.

\subsection{Language Design Considerations}

Our design of DBPL can be characterized by the phrase ``power through
orthogonality''.  Instead of designing a completely new language with
its own naming, binding and typing rules, we extended an existing
language (Modula-2 \cite{Wirt85b}) and placed particular emphasis on the
interoperability of the new database concepts with the given programming
language concepts. At DBPL design-time we considered the following
extensions necessary (and sufficient) to meet the specific requirements
of data-intensive applications:
\begin{itemize}
\item bulk data structuring using an orthogonal type constructor
      \p{RELATION OF} (see Sec.~\ref{Sec:Relations});

\item abstraction from
      persistence, sharing, concurrency control and recovery based on
      the concept of \p{DATABASE MODULE}s and parameterized 
      \p{TRANSACTION}s (see Sec.~\ref{Sec:Modules});

\item abstraction from bulk iteration through associative \e{access
      expressions} (see Sec.~\ref{Sec:AccessExpressions});

\end{itemize}
In particular, we eliminated the traditional competence and impedance
mismatch \cite{CoMa84} between programming languages and database
management systems by providing for
\begin{itemize} 
\item a uniform treatment of volatile and persistent data 
      (``orthogonal persistence'' \cite{AtBu86}), 
\item a uniform treatment of large quantities of objects with a simple 
      structure and small quantities of objects with a complex structure
      (``type completeness'' \cite{AtBu86}), 
      as well as 
\item a uniform (static) compatibility check between the declaration and the 
      utilization of each name (``strong static typing'' \cite{Sebe89}). 
\end{itemize} 
         
Implementation details such as the storage layout of records, the
clustering of data, the existence of secondary index structures, query
evaluation strategies, concurrency and recovery mechanisms, are
deliberately hidden from the DBPL programmer. A key idea in the design
and implementation of DBPL is to let the system choose appropriate
implementation strategies based on high-level information extracted from
the application program or its environment. As it turns out, the
widespread use of access expressions (i.e. first-order logic
abstractions of bulk data access) in typical DBPL programs facilitates
such an approach.

DBPL reflects Modula-2 by occasionally sacrificing ``language
orthogonality'' based on engineering and efficiency considerations.  For
example, DBPL does not support persistence of pointers and procedure
variables, concepts, which in some sense provide the technological basis
for object identification and procedural attachment. This was not only
motivated by the predominance of associative identification mechanisms
in the classical Relational Data Model, but also by the far-reaching
consequences of this identification mechanism on the concurrency control
and distribution support
\cite{BJS86,JLRS88}.

Modula-2 was chosen as the basis for DBPL because of its software
engineering qualities. It provides a clear module concept and a strict
type system and exceeds further through its balance between simplicity
and expressive power. Finally, our group has a long tradition in
Modula-2 compiler construction \cite{KMP82,MSS91}.

The compatibility between DBPL and Modula-2 is a design decision with
far-reaching consequences. DBPL is designed to be fully upward
compatible with Modula-2, i.e. every correct Modula-2 program has to be
a correct DBPL program. This decision not only limits the freedom in
language extensions (for example, the keyword \e{SET} is already used
for bit sets in Modula-2 and is not available for ``true'' sets, i.e.,
relations in DBPL), but also forces adherence to language mechanisms
(variant records, string handling, local modules, \ldots) for which
nowadays ``better'' solutions are available. The main advantage of our
compatibility decision is to lower the conceptual and technological
burden for DBPL users since they do not have to learn yet another
language.  Furthermore, this decision allows the smooth integration of
DBPL into existing, fully-fledged software development environments
(debuggers, profilers, version managers, \ldots), and the benefit of
software libraries and of interfaces to other languages and systems.

In contrast to some persistent programming languages, the evolution of
database schemata and of application programs is left outside the scope
of DBPL. This was based on the insight that this is a complex issue in
itself that should be delegated to a specific design environment (see
Sec.~\ref{Sec:DAIDA}).
                                                                   
\section{DBPL Language Concepts}
\label{Sec:DBPL-Language}

The first step towards a better integration of database concepts into a
language environment is to identify the basic database concepts (like
domains, tuples, tables and schemata) and to rephrase them in terms of
an appropriate vocabulary of programming concepts (like types, type
constructors and modules). In the following, we illustrate how DBPL
captures the main principles of set- and predicate-oriented database
modeling using the well-understood notions of naming, typing and binding
in procedural programming languages.

\subsection{Uniform Naming and Typing}
\label{Sec:Typing}

{\em Names} in DBPL are arbitrarily long sequences of upper- and lowercase
letters and digits starting with a letter. Names are case sensitive and 
are used to identify semantic objects of the language (values, types, 
variables, procedures, transactions, modules, \ldots).

DBPL is a {\em statically and strongly typed monomorphic} language:
every name is associated with a unique type that is determined at
compile-time. The compiler uses this information to assure that all
names for values, expressions or operations are only used in an
appropriate context. The advantages of such a typing scheme are well
known: programs are less liable to contain errors and there are no
time-consuming dynamic type checks.

The type compatibility rules for composite types in DBPL are based on
{\em name equivalence}, i.e., two composite objects have the same type
if and only if they have been declared by using the same type name. This
should be seen in contrast to the rule of {\em structural equivalence}
where two objects are type compatible if their fully expanded
definitions are isomorphic.  Most relational systems do not allow the
introduction of names for relation types and schemata and are therefore
based on structural equivalence.

DBPL provides a rich set of {\em built-in types} like \p{INTEGER}, \p{LONGINT},
\p{CARDINAL} (natural numbers), \p{LONGCARD}, \p{BOOLEAN}, \p{CHAR},
\p{REAL}, and \p{LONGREAL} that gives programmers a fine control over 
the mapping from application-specific domains to tailored machine
representations:
\begin{verbatim}
TYPE Dollar = REAL;
\end{verbatim}
Values of these built-in types are denoted by predefined names (e.g., \p{TRUE})
or literals (e.g., \p{0}, \p{3.2E-2}, \p{"A"}). It is furthermore
possible to introduce user-defined names for constant values:
\begin{verbatim}
CONST DollarToDMRatio = 2.64;
\end{verbatim}
DBPL supports application-specific extensions of the set of basic
types. An {\em enumeration type} is defined by a list of named values:
\begin{verbatim}
TYPE SupplierStatusType = (unimportant, important, veryImportant);
\end{verbatim}
This declaration defines an order on the values of the enumeration
type:
\begin{verbatim}
    unimportant < important < veryImportant
\end{verbatim}
{\em Subrange types} are derived from either
basic or enumeration types. They impose additional restrictions on the range
of values described by their base type: 
\begin{verbatim}
TYPE PartNumType = [0..99999];
     ImportantStatusType = [important..veryImportant];
\end{verbatim}                                       
Within expressions, values of a subrange type are compatible with values of
their base type. Assignments of base type values to variables of a
compatible subrange type are checked at run-time.
 
{\em Strings} are treated as composite objects consisting of a sequence
of characters. Their type is therefore \p{ARRAY [0..maxlength] OF CHAR},
where \p{maxlength} can vary from one string type to another. 
\begin{verbatim}
TYPE LongString = ARRAY [0..999] OF CHAR;
     String = ARRAY [0..29] OF CHAR; 
\end{verbatim}
{\em Arrays} are composed of a fixed number of elements. These elements are
positionally designated by indices, which are values of the index
type. The latter must be an enumeration type, a subrange type or the
basic type \p{BOOLEAN} or \p{CHAR}. 
\begin{verbatim}
TYPE BonusTable = ARRAY SupplierStatusType OF Dollar;
\end{verbatim}              
A {\em record type} declaration defines a labeled cartesian product type. The
scope of the label names is the record definition itself. These names are also
accessible as field designators referring to components of variables of that
record type (e.g.\ \p{supplier.Name}).
\begin{verbatim}
TYPE SupplierRecType = RECORD
                         Num     : SupplierNumType;
                         Name    : String;
                         Status  : SupplierStatusType;
                       END;                                            
\end{verbatim}

\subsection{Orthogonal Relation Types}
\label{Sec:Relations}

A {\em relation type} specifies a structure consisting of elements of
identical type, called the relation element type. The number of elements,
called the cardinality of the relation, is not fixed. The declaration of the
relation type specifies the relation element type (e.g.,
\p{SupplierRecType}) and an ordered list of key
components (e.g., the field \p{Num} of \p{SupplierRecType}):
\begin{verbatim}
TYPE SupplierRelType = RELATION Num OF SupplierRecType;
\end{verbatim}
The classical relational data model constrains the relation element type
to records with attributes of the built-in types (``flat tuples''). By
lifting this rather ad-hoc restriction, we substantially enhanced the
modeling power of the language and obtained structuring capabilities
beyond data models that simply support {\em complex objects} and
non-first-normal-form relations \cite{AFS89}. For example, the following
DBPL types are also well formed:
\begin{verbatim}
TYPE PartNumSetType     = RELATION OF PartNumType;
     Point2DSetType     = RELATION OF ARRAY [1..2] OF REAL;
     GroupedSuppRelType = RELATION Num OF RECORD
                            Num       : SupplierNumType;
                            SuppParts : PartNumSetType;
                          END
\end{verbatim}  
This type declaration introduces three type names to denote sets of
natural numbers, sets of points that are represented by their
coordinates in the plane, and nested relations that group supplier
numbers with sets of part numbers.
                                              
The \e{relation key} in a relation type expression defines a list of
components within the relation element type such that the relation
always defines a (partial) function between its key and its element
type. In other words, each key value uniquely determines (at most) one
relation element. For example, the key constraint for a relation
\p{SupplierRel} of type \p{SupplierRelType} can be expressed by the
following predicate stating that the equality of the key component
\p{Num} implies the equality of the relation elements:
\begin{verbatim} 
ALL s1, s2 IN SupplierRel (s1.Num = s2.Num) => (s1 = s2)
\end{verbatim}
An empty key component list as in \p{Point2DSetType} is a synonym for an
enumeration of all components of the element type; in this case a
relation is just a set of relation elements.

\subsection{Generalized Scope and Lifetime Concepts}
\label{Sec:Modules}

\begin{figure}
\small
\begin{verbatim}DATABASE DEFINITION MODULE SupplierPartDB;
TYPE PartNumType        = [0..99999];
     SupplierNumType    = [1000..9999];
     SupplierStatusType = (unimportant, important, veryImportant);
     String             = ARRAY [0..29] OF CHAR;   
     Dollar             = REAL;
     Kilo               = REAL;       
     PartStateType      = (base, comp);
     SupplierRecType = RECORD                
                Num     : SupplierNumType;
                Name    : String;
                Status  : SupplierStatusType;
              END;
     MadeFromSubRecType = RECORD     
                Num     : PartNumType;        
                Quantity: CARDINAL;
              END;
     MadeFromSubRelType = RELATION Num OF MadeFromSubRecType;
     PartRecType = RECORD
                Num     : PartNumType;
                Name    : String;
                CASE State : PartStateType OF
                  base  :
                    Cost        : Dollar;
                    Mass        : Kilo;
                    SuppliedBy  : SupplierNumType;
                | comp  :
                    MadeFrom    : MadeFromSubRelType;
                    AssemblyCost: Dollar;
                END; 
              END;
     SupplierRelType = RELATION Num OF SupplierRecType;
     PartRelType = RELATION Num OF PartRecType;
VAR SupplierRel       : SupplierRelType;
    PartRel           : PartRelType;
    HighestPartNoUsed : PartNumType;
END SupplierPartDB;               
\end{verbatim}
\caption{An extended relational database schema in DBPL}
\label{Fig:Schema}
\end{figure}  

\begin{figure}
\small
\begin{verbatim}MODULE Application;
FROM SupplierPartDB IMPORT SupplierRelType, PartRel, SupplierRel;

TRANSACTION DeleteSuppliers(Suppliers: SupplierRelType): BOOLEAN;
BEGIN IF SOME bp IN PartRel (bp.State = base) AND
         SOME s IN Suppliers (bp.SuppliedBy = s.Num) THEN
        RETURN FALSE; (* referential integrity violated *)
      ELSE         
        SupplierRel:- Suppliers;
        RETURN TRUE
     END;
END DeleteSuppliers;

BEGIN ... END Application;
\end{verbatim}
\caption{An application program that imports shared database objects}
\label{Fig:Application}
\end{figure}  

\noindent In a classical relational database system, a \p{CREATE TABLE}
command implies (1) the declaration of an (anonymous) relation type, (2)
the declaration of a named relation variable of this type, and (3) the
specification that this relation variable should persist, i.e., preserve
its state until explicitly deleted. In DBPL, we again exploit
programming language principles and strive for a greater modeling power
by decoupling the concepts of type, scope, and lifetime.

In order to create ``containers'' for values of (relation) types in
DBPL, it is necessary to declare named variables explicitly:
\begin{verbatim} 
VAR SupplierRel : SupplierRelType;
    OldSupplier : SupplierRelType;
    MadeFromRel : MadeFromRelType;
    GroupedSupp : GroupedSuppRelType;
\end{verbatim}
The scope and lifetime of variables depend on the context of their
declaration. Variables declared within a procedure are visible
within their enclosing procedure and are created and destroyed
automatically on block entry and exit, respectively.  Successive or
recursive procedure invocations create independent variable instances.

Similarly, variables declared in the outermost block of a program are 
visible within the full program and they are created and destroyed 
automatically on program entry and exit, respectively. Multiple program 
activations (sequentially or simultaneously) create independent variable 
instances.

The module concept makes it possible to declare named objects (types,
constants, variables, procedures, \ldots) that are in the \e{scope} of
multiple programs. Typically, an application program consists of a
multiplicity of modules. DBPL supports separate compilation, i.e.
modules can be developed independently and incrementally. A module can
import names that are exported from other modules that include
definitions for these names or that import these names from a third
module. The compiler enforces the consistent use of names across module
boundaries. Program modules have a \e{copy semantics}
in the sense that variables visible in the scope of multiple programs
are implemented by independent variable instances.

In DBPL we extended modules using a second concept which we call
\p{DATABASE} modules (see Fig.~\ref{Fig:Schema}).  All variables
declared within such a module are \e{persistent} and \e{shared}: in
contrast to other program variables their \e{lifetime} exceeds a single
program execution \cite{ABCCM83} and concurrent processes share a common
variable instance. In this sense database modules have a \e{reference
semantics}.  The lifetime of a persistent variable is longer than that
of any program importing it.

Using these rules it is a straightforward matter to model the scoping
rules of conventional relational database systems. A database schema is
simply a database module that declares and exports names for types of
appropriate basic domains and declares and exports persistent variables
of relation types (see Fig.~\ref{Fig:Schema}). Similarly, an application
program is a module that explicitly imports names from a database schema
(see Fig.~\ref{Fig:Application}).

Read and write access to shared variables is required to be part of the
execution of a \e{transaction} \cite{Reim81}.  The ACID property
\cite{GrRe93} of DBPL transactions allows database programmers to abstract
from concurrency and recovery issues since transactions are atomic with
respect to their effects on persistent and shared database variables (see
Fig.~\ref{Fig:Application}).

\begin{sloppypar}
The potential arising from the separation between type and lifetime is
exemplified in Fig.~\ref{Fig:Schema} by the declaration of a single
persistent and shared integer variable \p{HighestPartNoUsed} which issues
unique part numbers. Another example is the transaction in
Fig.~\ref{Fig:Application} that uses a (temporary) parameter 
\p{Suppliers} of type \p{RELATION} to specify a set of suppliers to be
deleted from the database variable \p{SupplierRel}.
\end{sloppypar}

Another highly relevant modeling alternative supported by DBPL (the ADT
style) is to encapsulate database variables like 
\p{SupplierRel} and \p{PartRel} in Fig.~\ref{Fig:Schema} into a DBPL
\e{implementation module} and to restrict update operations to ``trusted``
transactions exported by its corresponding \e{definition} module
\cite{ScMa93a}.

Since the import relationships between modules have to be declared
statically, there is no possibility for name conflicts and schema
incompatibilities at run-time. Furthermore, since we allow for the
definition of multiple (database) modules, the concept of \e{multibases}
is also covered by DBPL.

\subsection{Bulk Expressions and Operations}
\label{Sec:AccessExpressions}

The extension of the type space available to DBPL programmers through an
orthogonal bulk type constructor \p{RELATION OF} is complemented by an
orthogonal extension of the DBPL expression language by bulk value
constructors and associative value selectors. Again, we aimed for high
language economy by supporting full orthogonality between Modula-2's
arithmetic and Boolean expression syntax and DBPL's bulk expression
syntax.

For each type constructor of DBPL (record, array, relation) there is a
{\em value constructor} to create objects of the composite type by 
enumerating its components:
\begin{verbatim}
v1:= SupplierRecType{11, "John", important};
v2:= MadeFromSubRecType{11, 100};
v3:= PartRecType{3, "nut", base, 300.0, 20.3, 11};
v4:= PartNumSet{1, 3, 77};
v5:= Point2DSetType{ {1.0, 2.0}, {2.0, 1.0} };
v6:= PartRelType{ {4, "bolt", base, 30.2, 11.4, 11} };
\end{verbatim}   
The right-hand sides of these assignments make use of value constructors
for record values (assigned to \p{v1}, \p{v2}, \p{v3}) and relation
values (assigned to \p{v4}, \p{v5}, \p{v6}). Note that the curly
brackets \verb${}$ are {\em overloaded}: depending on the type
identifier preceding them they construct records, arrays, or relations.
The assignments to variables \p{v5} and \p{v6} contain nested value
constructors, for example, \p{v6} is assigned a relation that contains a
single record of its element type \p{PartRecType}. Type identifiers for
nested value constructors can be omitted.

In DBPL there are three kinds of {\em value selectors} for the selection
of components within a structured value.  Elements of an array are selected
by an index value of their index type, enclosed in square brackets
(\p{vector[7]}).  Fields of a record are selected by their field name
(\p{supplier.Name}).  Elements of a relation are selected by their key
value, enclosed in square brackets (\p{SupplierRel[7]}).  Therefore, variable
designators of DBPL consist of a name followed by a path of
value selectors:
\begin{verbatim}
SupplierRel[7].Name:= "Peter";
PartRel[3].Mass:= 13;
\end{verbatim}           

In addition to these element-wise operations, DBPL provides  specialized
set-oriented {\em bulk expressions} for relation types. There are three
kinds of bulk expressions, namely Boolean expressions,
selective and constructive access expressions.

\noindent \k{Boolean Expressions} yield a truth value (\p{TRUE} / \p{FALSE}) and
may be nested:  
\begin{verbatim} 
SOME s IN SupplierRel (s.Name = "John") 

ALL s IN SupplierRel (s.Status = important) 

ALL p IN PartRel (p.State <> base) OR 
  SOME s IN SupplierRel (p.SuppliedBy = s.Num) 
\end{verbatim} 
The comparison operators ($=$, $<>$, $>=$, $<=$, $<$) for relations are
abbreviations for key-based quantified expressions, e.g., \p{SupplerRel1$>=$SupplierRel2} denotes relation containment and is
equivalent to    
\begin{verbatim}
ALL s1 IN SupplierRel1 SOME s2 IN SupplierRel2 (s1.key = s2.key)
\end{verbatim}
The test for membership (\p{thisSupplier IN SupplierRel}) is equivalent to
\begin{verbatim}
SOME s IN SupplierRel (thisSupplier.key = s.key)
\end{verbatim}

\noindent \k{Selective Access Expressions} are rules that select subrelations.
\begin{verbatim}
EACH s IN SupplierRel: s.Status = important
\end{verbatim}                                      
selects all elements \p{s} of the relation variable \p{SupplierRel}
that fulfil the selection predicate \p{s.Status $=$ important}.

A selective access expression within a relation constructor denotes a
relation of all selected elements:
\begin{verbatim}
SupplierRelType{EACH s IN SupplierRel: s.Status = important}
\end{verbatim}    

\noindent \k{Constructive Access Expressions} are rules for the construction of
relations based on the values of other relations:
\begin{verbatim}                                     
NameRecType{p.Name, s.Name} OF 
   EACH p IN PartRel, EACH s IN SupplierRel:
     (p.State = comp) AND (p.SuppliedBy = s.Num)
\end{verbatim}                                      
where \p{NameRecType} is a record of two strings defined as
\begin{verbatim} 
TYPE NameRecType = RECORD Part, Supplier: String END
\end{verbatim}
The construction rule above declares that pairs of names of all base
parts together with their suppliers from the two stored relations
\p{PartRel} and \p{SupplierRel} are to be constructed.

The application of a relation constructor to a constructive access
expression creates a relation that contains the values of the target
expression (preceding the keyword \p{OF}), evaluated for all combinations
of the element variables (\p{p}, \p{s}) that fulfil the selection
expression \verb$(p.State = comp) AND (p.SuppliedBy = s.Num)$:

\begin{verbatim} 
NameRelType{{p.Name, s.Name} OF 
     EACH p IN PartRel, EACH s IN SupplierRel:
       (p.State = comp) AND (p.SuppliedBy = s.Num)}
\end{verbatim}
results in a relation value which has to comply with
\begin{verbatim}
TYPE NameRelType = RELATION OF NameRecType;
\end{verbatim}
Note that access expressions do not denote relations; only in the context of
a relation constructor \verb$RelType{...}$ do they evaluate to a
relation value.  Other contexts in which access expressions can be used are
given below.

In addition to these (side-effect free) bulk expressions, DBPL provides
specialized \e{bulk operators} (\p{:=, :+, :-, :\&}) for relation
alterations which assign, insert, delete, and update sets of relation
elements:
\begin{verbatim}
PartRel:= PartRelType{};
SupplierRel:- SupplierRelType{EACH s IN SupplierRel: s.Status=important}
\end{verbatim}            
The types of the expression and the variable on the left-hand side have
to be compatible according to the rules of section \ref{Sec:Typing}.  As
illustrated by the examples above, the nesting of DBPL expressions
captures the essence of relational query languages, namely to provide
\e{iteration abstraction} by means of high-level set-oriented
selection, construction and update mechanisms.

\subsection{Exploiting Language Orthogonality}
\label{Sec:Orthogonality}

It should be noted that the database and programming language features
of DBPL sketched in the previous sections do not simply stay
side-by-side. On the contrary, there are many interfaces to create
synergy between these features, for example:
\begin{itemize}
\item Relation types are allowed to appear in arbitrary contexts,
i.e. not only as types for database variables, but also as types of local
variables within procedures, or as types of value- or variable-parameters; 

\item Quantified expressions can appear not only
within bulk expressions but also in conditionals or as termination
conditions of loops;

\item Relation constructors can be used freely within expressions of
arbitrary types. A relation constructor can contain function calls,
arithmetic operations etc.
\end{itemize}

Relation constructors provide an expressive mechanism to build relations
from their elements. To support the inverse operation (``de-setting'')
there is a strong need for {\em iterators}. The essence of an iterator
is a selective access expression (see \ref{Sec:AccessExpressions})
denoting selected elements of a relation variable to be iterated over.
The body of an iteration is an arbitrary statement sequence that can
read and update the value of the loop variable:
\begin{verbatim}
FOR EACH s IN SupplierRel: s.Status = important DO
  InOut.WriteString(s.Name); InOut.WriteLn;
END;
\end{verbatim}

Up-to-date programming languages provide two important abstraction
mechanisms to achieve localization of information in large software systems
\cite{Sebe89,LiGu86}. Process abstraction allows programmers to
abstract from the implementation of a subroutine and to perform complex
operations simply through reference to its name with an appropriate list
of actual parameters. Type abstraction allows programmers to abstract
from the implementation of a data structure and to operate on it only
via a well-defined interface expressed as a set of operations defined
for an abstract data type.

DBPL embodies both abstraction mechanisms by means of procedures that
abstract over statements, functions that abstract over expressions, and
opaque types that abstract over type expressions \cite{Wirt85b}. In
addition, DBPL provides {\em selectors} that abstract over selective
access expressions and {\em constructors} that abstract over
constructive access expressions (see \ref{Sec:AccessExpressions})
\cite{JLS85}. These two abstractions capture the essence of updatable and
non-updatable {\em views} in relational databases since selector
applications can appear wherever a relation variable is expected and
constructor applications can appear wherever a relation expression is
expected.

The selector \p{SuppliersWithStatus(important)} defines an
\e{updatable} view on the supplier relation selecting those suppliers having
\p{important} as their status (see also Sec.~\ref{Sec:AccessExpressions}):
\begin{verbatim}
SELECTOR SuppliersWithStatus(st: SupplierStatusType): SupplierRelType; 
BEGIN EACH s IN SupplierRel: s.Status = st END SuppliersWithStatus;
\end{verbatim}

The following constructor \p{SuppliersForParts} names a \e{non-updatable}
view that is derived from the base relations \p{PartRel} and
\p{SupplierRel} and that contains pairs of parts and supplier names for all
base parts with their respective suppliers.
\begin{verbatim}
CONSTRUCTOR SuppliersForParts: NameRelType;
BEGIN
  NameRecType{p.Name, s.Name} OF 
     EACH p IN PartRel, EACH s IN SupplierRel:
       (p.State = comp) AND (p.SuppliedBy = s.Num)
END SuppliersForParts;
\end{verbatim}

Without going into details it should be noted that naming (of
statements, expressions etc.) naturally leads to the concept of
recursion. The semantics of a recursive query expression in DBPL is not
defined operationally (as is common practice for procedures) but as a
least fixed point of recursive set equation \cite{ERMS91,JLS85}.
Thereby, constructors are at least as expressive as recursive DATALOG
programs with stratification semantics \cite{Mink88,Naqv89} over complex
objects:
\begin{verbatim}
TYPE NumPairType = RELATION OF RECORD Super, Sub : PartNumType END;

CONSTRUCTOR TransitiveMadeFrom: NumPairType;
BEGIN
  {p.Name, mf.Num} OF 
     EACH p IN PartRel, EACH mf IN p.MadeFrom:
       p.State = comp,
  {mf1.Super, mf2.Sub} OF 
    EACH mf1 IN {TransitiveMadeFrom}, EACH mf2 IN {TransitiveMadeFrom}:
      mf1.Sub = mf2.Super
END TransitiveMadeFrom;
\end{verbatim}


\section{DBPL System and Environment}
\label{Sec:DBPL-System}

The development of data-intensive and long-lived applications is
recognized as a demanding system construction task that requires full
software-engineering support. In implementing DBPL we therefore paid
attention to smoothly integrate the DBPL tools into the native software
development environments available on DBPL's host architectures. In
several DBPL spin-off projects we also studied more advanced issues of
open distribution, commercial interoperability and computer-aided
software engineering (see Sec.~\ref{Sec:DBPL-SpinOff}).

We based the DBPL system implementation on state-of-the-art relational
database and compiler technology. We were, however, compelled to invest a
significant amount of development work to overcome mismatches of the
contributing technologies that otherwise would have disrupted the clean 
and simple DBPL language model described in the previous section. In
section~\ref{Sec:Extending-PL} and \ref{Sec:Extending-DB} we therefore
report on experience gained during the past six years of DBPL system
(re-)implementation and refinement in
\begin{itemize}
\item removing conventional compiler implementation restrictions,
\item extending the expressiveness of the bulk query language,
\item generalizing the storage model, and
\item reducing system performance bottlenecks resulting from
mismatches between independently developed contributing technologies.
\end{itemize}
In section~\ref{Sec:DBPL-Complexity} we share some of the conclusions we
have drawn from the DBPL implementation effort for our future work on
database programming language implementations.

\subsection{Architectural Overview}
\label{Sec:DBPL-Integration}

An important task in the design of the DBPL system was the division of
labour between the various DBPL system components. Program analysis and
code optimization is performed statically by the DBPL compiler, the
linker verifies the overall consistency between separately developed
system components at application link-time, while the run time system
looks after dynamic aspects of database applications such as query
optimization, storage management, serialization of transactions and
failure recovery for persistent data.

\begin{figure}
\centerline{\epsfbox{dbpl-components.ps}}
\caption{Overall DBPL system architecture}
\label{Fig:DBPLSystem} 
\end{figure}

Figure~\ref{Fig:DBPLSystem} depicts the overall DBPL system architecture
as well as the interaction between the various parts of the DBPL system.
A DBPL application typically consists of a collection of modules and
interfaces (represented by dashed boxes in Fig.~\ref{Fig:DBPLSystem}).
Some of these modules define \e{shared} objects like library routines or
database variables, others define private, application specific code or
data. Individual modules and interfaces are translated by the DBPL
compiler and then linked with other compiled DBPL modules or object code
developed in other programming languages (C, C++, Modula-3) yielding an
executable program with (symbolic, type-safe) references to shared
libraries and shared databases.

At run-time, this executable program interacts through the interface module 
\p{DBPLRTS} with the various layers of the DBPL run time system. Database 
objects are either stored in a DBPL-specific format in files accessed 
through operating system calls issued by the layer \p{SMS} or they are held 
in commercial SQL databases (Ingres, Oracle) and accessed via set-oriented 
dynamic SQL+C statements following the \e{X-Open} standard for SQL database 
access. The distinction between DBPL and SQL database objects is fully 
transparent to the application programmer. 

Fig.~\ref{Fig:DBPLSystem} also shows the interaction between two DBPL
applications (possibly running on different nodes of a TCP/IP or a
DECnet local area network) that import a common set of database modules
and therefore run against shared databases. The sharing of DBPL database
objects is achieved by a page-oriented client-server architecture using
a three-level (\p{CTMS, CRDS, SMS}) concurrency-control and recovery
protocol based on explicit message passing. The layer \p{LMS} provides
communication services and a centralized scheduling process that
guarantees serializable transaction execution for DBPL applications.
Concurrent and possibly remote access to SQL databases is handled using
built-in services of the commercial SQL servers. Due to limitations of
the currently available SQL server interfaces there is no two-phase
commit protocol to guarantee abort and commit consistency across mixed
DBPL and SQL databases in case of system failures at commit-time.

Currently, we are distributing DBPL in two distinct system
implementations, Sun DBPL and VAX/VMS DBPL. Application programs
developed with one system (including user-interface code) can be
recompiled without change using the other system. Both systems are
written entirely in Modula-2 and consist of a compilation and a run-time
environment. The multi-user DBPL run time system is highly portable and
runs under VAX/VMS 6.1, SunOS 4.1, IBM AIX 3.2 and IBM OS/2. Both DBPL
systems can be integrated fully into commercially available software
development environments (NSE, Teamware, CMS) and provide an optional
SQL gateway in addition to the DBPL-specific storage manager.


\subsection{Extending Compilation Technology}
\label{Sec:Extending-PL}

By recasting the concept of schemata into the concept of shared modules, we 
were able to successfully exploit the compilation and module management 
technology developed for modular languages like Ada, Modula-2, Modula-3 and 
Eiffel. We extended this technology by link-time mechanisms to check the 
consistency of persistent variables against the type information used by 
their importing applications. Furthermore, we developed ``binding tools'' 
to support simple persistent data conversions as required by typical 
evolutionary schema changes. These tools also allow database administrators 
to bind dynamically persistent variables to alternative type-compatible 
implementations like internal DBPL storage structures or external (Ingres, 
Oracle) SQL database relations. 

The scoping and polymorphic type checking required at compile-time for 
relational expressions and (higher-order) selectors and constructors was 
implemented (analogously to array operations and procedures) by hand-coded 
checking routines, one for each language construct. The DBPL compiler also 
performs a limited form of type inference to eliminate the need for 
``redundant'' type annotations in nested queries. While these tasks are 
captured adequately in the larger framework of polymorphic type systems 
(like ML \cite{MTH90} or Quest \cite{Card89}), the DBPL system also calls for 
\e{dynamic} type descriptions available at run-time to perform, for example, 
type-dependent tuple value equality comparisons.

The interaction between imperative programming language statements and
declarative, dynamically optimized bulk operations in DBPL is solved
technically as follows: DBPL operations on individual relation elements
and navigational operations are mapped by the compiler directly to
operations of the run-time system. Bulk operations (quantified
predicates, calculus expressions, assignments of entire relations to
relation variables, applications of selectors), however, are not
realized by means of (nested) loops in the object code. Instead of this,
the run-time system receives a compact internal representation of the
operation in form of a \e{predicate tree} containing attributes. The
execution of an arbitrarily complex relation-valued operation is
accomplished in three steps:
\begin{enumerate} 
\item Evaluation of simple (non-relational) parts of the 
expression and address computations, utilizing \e{inline code}.
\item Generation of a predicate tree by means of a sequence of operations of the 
run-time system, thereby binding operands to program variables.
\item Optimization and evaluation of the operations on the dynamically bound operands as defined 
by the predicate tree. 
\end{enumerate} 

Selectors and constructors are represented at run-time exclusively by means 
of predicate trees. Therefore, predicate trees are allowed to contain 
parameters as well as (possibly cyclic) references to other predicate 
trees, together with a list of actual parameters. The run-time system 
provides symbolic operations for the manipulation of predicate trees (copy, 
delete, expand, \ldots). With the help of these elementary operations, the 
compiler can implement selector and constructor declarations as well as 
variables, partial parameter substitution, selector applications and the 
usage of selectors and constructors in relational constructors and 
iterators. 
    
It was possible to undertake virtually all extensions from Modula-2 to
DBPL without interference with the machine dependent parts of the code
generation and to obtain a high portability of the compiler front end.
Many operations of DBPL are (conceptually) implemented by sequences of
equivalent statements of Modula-2, containing calls to the run-time
support module \p{DBPLRTS} (see~Fig.~\ref{Fig:DBPLSystem}). Accordingly,
the VAX DBPL and the Sun DBPL compiler utilize the same compilation
strategies despite significant differences in the details of the target
code generation.


\subsection{Extending Database Technology}
\label{Sec:Extending-DB}

The architecture of the DBPL run-time system is similar to the layered
architecture of other extended or extensible relational database systems
\cite{DE87,Ston90}. As can be seen in  Fig~\ref{Fig:DBPLSystem}, the DBPL
run-time support subsumes a storage management system (SMS) for
fixed-sized records and variable-sized long fields (maximum 8MB in
size), a complex-object relational data system (CRDS), a predicate
management system for the optimization and evaluation of composite
relation- and boolean-valued expressions (CPMS), a database deduction
engine to perform optimized fixed-point algorithms over sets of
predicates (PSMS), a predicative set-oriented transaction-manager (CTMS,
see also \cite{BJS86}), and an ADT-based interfaced (DBPLRTS) to the
DBPL compiler and other DBPL tools.

A repeating pattern in the development of the DBPL system was the need
to generalize existing database solutions to meet the requirements
imposed by the orthogonal DBPL language model. At the storage level, for
example, we had to substantially revise the interface to the
``relational data storage system'' to be able to identify, create,
manipulate and destroy non-persistent relations, non-set-valued
persistent objects, non-homogeneous collections, or to navigate through
nested complex objects.  Similarly, the query evaluation and
optimization component had to be extended substantially to handle
parameterized query expressions, non-set-valued queries, type-complete
data structures, user-defined functions and arbitrarily nested query
expressions.

As a result of these generalizations, the operations at the interfaces
of the DBPL system layers are centered around general \e{programming
language abstractions} like value, variable, type, scope, object
identifier, parameter and expression and no longer around DBMS-specific
combinations of these concepts like tuple, relation, dictionary, TID,
view, or query tree.


\subsection{On the DBPL System Complexity}
\label{Sec:DBPL-Complexity}

Figure~\ref{Fig:DBPL-Sizes} gives a rough quantitative overview of the
relative complexity of the different tasks in the DBPL system. The
complexity is distributed fairly equally between the run-time system,
the compiler front-end that performs type checking, inter-module
consistency checking, intermediate code generation and the
industrial-strength compiler back-end that performs object code
generation and optional intermediate code optimizations like tail call
optimization, automatic inlining, aggregate breaking, loop-invariant
code motion, strength reduction, common subexpression elimination, copy
and constant propagation, register allocation, loop unrolling or unused
code elimination.

The compactness and relative efficiency of the DBPL run-time system
results from the fact that a large number of scanning, parsing, type
checking, error recovery and consistency checking tasks performed by
conventional database systems was factored-out into the DBPL compiler.
In particular, there is no need to check the parameters or the nesting
of run-time system calls (e.g., hidden cursor operations, buffer
creation and deallocation) since these calls are generated exclusively
by the compiler and not by application programmers.

Fig.~\ref{Fig:DBPL-Sizes} also reveals a disadvantage of the multi-level 
concurrency control and recovery scheme adopted in the DBPL system 
\cite{BSW88}. The layer CRDS that is responsible for the mapping of 
tuple-level complex object operations to operations on atomic fragments
maintained by the storage manager SMS does not rely exclusively on
concurrency control and recovery primitives of the SMS but performs its
own concurrency control and recovery mechanisms exploiting the semantics
of complex object manipulations. As can be seen in
Fig.~\ref{Fig:DBPL-Sizes}, the price for a gain in parallelism is a
significant increase in the complexity of this system component.
Furthermore, bugs in the recovery code are very hard to locate since
they only become visible if the system is operated in stress situations.
In retrospect, we feel that we should have chosen a less aggressive
approach to scheduling and fault tolerance in DBPL.

The heavy dependency of the DBPL compilers for Sparc, VAX, Motorola and
Intel architectures on architecture-specific object code, debugger
information and link formats turned out to be a major issue in the
long-term maintenance of the DBPL system. In our current research
projects outlined in Sec.~\ref{Sec:Termination} we therefore moved to
platform-independent, optimizable and \e{persistent} code
representations based on continuations \cite{App92}; a move that seems
to give rise to interesting new database programming concepts like
run-time reflection, persistent threads, or the dynamic distribution of
data and code across architecture boundaries \cite{Matt93}.

The Open DBPL/SQL gateway (compare Sec.~\ref{Sec:Gateway}) and the
bidirectional call interfaces between DBPL and other languages
demonstrated that it requires a surprisingly small effort to embed a
``closed'' database programming language with a well-designed internal
architecture into ``open'' system environments. On the other hand, this
effort was highly appreciated by DBPL users since these generic gateways
enable the construction of hybrid application systems that make best use
of the technologies from both worlds.

\begin{figure}
\centerline{\epsfxsize=\textwidth\epsfbox{dbpl-code.ps}}
\caption{Relative sizes of DBPL system components (lines of Modula-2 code)}
\label{Fig:DBPL-Sizes} 
\end{figure}

\section{A Short Reflection on DBPL's Development}

DBPL was not designed in ``one shot'' but developed in phases which
reflect rather clearly our degree of understanding and our level of
ambition. In the mid-70ies we were not the only group working on
algorithmically complete languages for data-intensive applications ---
in the relational setting the correspondence between central concepts in
programming and database modeling seemed obvious and it was agreed that
types were the notion to bridge the gap \cite{Shop79,Wass79,RS79}.
However, it took us more than 30 man-years to develop the concepts
underlying a relational database programming language into the DBPL
system which fully exploits them and provides sufficient efficiency and
operational support for their effective use.

On the other hand, DBPL was not the end of our efforts in supporting
database programming. We embedded it into a network of DBPL-based
spin-off projects ranging from distributed DBPL \cite{JGLR88} to SQL
server gateways \cite{MRSS92a} and DBPL-oriented programming
environments \cite{Jark93}.


\subsection{DBPL as a Learning Experience}
\label{Sec:DBPL-History}

In Pascal/R \cite{Schm77b} we concentrated on capturing and integrating
relational semantics in the context of a strongly and statically typed
monomorphic programming language. We introduced relation types to model
schemata, relation expressions for queries and generalized assignment
statements for relation updates. A database was an aggregate of relation
variables imported through external program variables in the same manner
as Pascal works with external files. Optimization of relation
expressions was another large issue at that time \cite{JaSc82b} and some
of the algorithms designed by Matthias Jarke and J\"urgen Koch
\cite{JaKo83} still seem to be alive in DBPL. Since nesting of
relational expressions was heavily used for controlling subquery
execution, we soon discovered that something must be wrong with the
standard predicate transformation rules in cases of empty range
relations: universal quantifiers do not necessarily commute in this
case. Frank Palermo visited us in Hamburg and helped us by fixing his
algorithms \cite{Pale72}. Another issue was that of update semantics in
the case of key constraint violations. Keys while being part of type
definitions destroyed static type checking for relations.  Pascal/R
introduced specific run-time exceptions on relation updates, an
experience which motivated our subsequent emphasis on transactions and
on exception handling in general.

The Pascal/R system was used quite extensively and successfully in
education including about 20 installations abroad. However, as soon as
we started implementing bigger database applications with Pascal/R
(e.g., FIBEX \cite{CFH*82}) we quickly experienced two rather severe
deficiencies. The first inadequacy was the missing transactional support
in Pascal/R, the second one was a general deficit inherited from Pascal,
namely its lack of support for modular system programming. We recognized
that, in order to make progress with system programming support, we had
to leave the framework of Pascal.  Before initiating the DBPL project we
began an intensive period of concept development and evaluation in order
to improve on the deficits mentioned above\footnote{This work was
supported by DFG grant Schm.450/2-1
(``Datenbankprogrammiersprachen'').}. As a consequence, we decided to
move to Modula-2 as a host and implementation language, an effort we
started by porting the ETH/Zurich compiler into the DEC/VMS environment
\cite{KMP82} (As a side effect we still hold more than 600 licenses
for that product!).

We started working on transactional abstraction, work
leading to parameterized transaction procedures \cite{Reim81}.
Furthermore, we recognized the central importance of iteration
abstraction for relation value construction, relation iteration control
and relation view definition (see Sec.~\ref{Sec:Orthogonality}). Selectors
were introduced as named and parameterized access expressions thereby
supporting iteration abstraction by a first-class concept in database
languages.

In 1980 we began a close cooperation with ETH/Zurich on Modular/R
\cite{Reim83} (by having Manuel Reimer from Hamburg working at ETH). This small
project was essentially an exercise in evaluating the concepts developed
for iteration and transaction abstraction. Furthermore, we started
exploiting Modula's module concept for database programming. Having
modules available as a general concept to organize code sharing between
programs surely influenced our next step to exploit modules also for
data sharing \cite{MRS84}. We introduced persistent database modules
which, in Modula/R, were still restricted to relations only. Relation
types and operations as well as the work on query optimization were
carried over in a fairly straightforward way from Pascal/R into Modula/R
and then further into DBPL.

Based on the above experience we decided around 1983 to start the DBPL
project. Our vision for DBPL was as simple as ambitious \cite{ScMa83}:
define and implement a language which provides, in an algorithmically
complete context, its four database concepts -- relation type, access
expression, database module, transaction procedure --
\e{unrestrictedly}.

During DBPL development it became obvious that both communities,
databases and programming languages, were adhering to several, mostly
unnecessary and ad-hoc restrictions. Some limitations, for example, the
lack of data {\em type orthogonality} (i.e. the restriction to first
normal form relations), had already been realized, others, such as {\em
orthogonal persistence} (providing persistence for all types, not just
for relations), were new for the database community (but already
discovered by the persistent programming language people
\cite{ABCCM83}). Other insights, for example, the relationship between
abstract access expressions and queries, iterators and views, or between
recursive access expressions and deductive databases, came as a
surprise, at least to us.


\subsection{DBPL Spin-Off Projects}
\label{Sec:DBPL-SpinOff}

DBPL initiated several spin-off projects, all of which were triggered by
the fact that a language is hardly ever used in isolation but has to
enable good-quality interaction in heterogeneous environments consisting
of other programs, databases, tools, machines etc. Therefore, we
embedded DBPL as a product deeply into its native environments (see
Sec.~\ref{Sec:DBPL-Integration}) and we used DBPL as a research vehicle for
several R\&D projects to investigate issues of distribution,
interoperability and computer-aided software engineering.

\subsubsection{DURESS: Distributed DBPL in Heterogeneous Environments}

In the DURESS project\footnote{DURESS was supported by a grant
from the IBM European Network Center, Heidelberg.} \cite{JGLR88,LEERS87}
we exploited DBPL's module concepts described in
section~\ref{Sec:Modules} to add an additional layer of type-safety to
standard remote procedure call mechanisms (RPC) in federated
client-server programming environment. In DURESS, individual DBPL
compilation units may be located at different nodes in a (LAN/WAN)
network consisting of PC workstations and VAX servers.

In the distributed DBPL environment, the compiler automatically
generates the necessary client and server stub code to access procedures
exported from remote sites. Furthermore, dynamic type descriptions are
assigned to compiled remote interface definitions. These descriptions
are used during connection establishment to verify that all parts of a
distributed program have been compiled using compatible versions of the
interface specifications. This mechanism directly generalizes  the
link-time consistency control mechanisms developed for persistent DBPL
modules.

In DURESS, remote modules can also export (database) variables,
transactions and views (represented as selectors and constructors). In
this case, the extended DBPL run-time system performs the necessary
low-level communication and distributed query evaluation to blur the
distinction between local and remote objects:
\begin{verbatim}
DATABASE DEFINITION RemoteSupplierDB ON "Server7";
IMPORT SupplierPartDB;
VAR SupplierTable : SupplierRelType;
END RemoteSupplierDB;
\end{verbatim}

\subsubsection{Open DBPL/SQL: A Gateway to Commercial SQL Servers}
\label{Sec:Gateway}

In another subproject\footnote{This work was supported by a
grant of the DAAD, Bonn.} we studied issues of DBPL system interoperability by
extending the DBPL system to support bindings to external persistent
objects in addition to internal persistent DBPL objects
\cite{MRSS92a}. The only change to the language definition of DBPL is
the syntax of definition module headers:
\begin{verbatim}
DATABASE DEFINITION FOR Ingres MODULE Suppliers2;
IMPORT SupplierPartDB;
VAR SupplierTable : SupplierRelType;
END Suppliers2;
\end{verbatim}
This module exports a persistent variable \p{SupplierTable} that is
implemented by the table \p{SupplierTable} stored in the Ingres database
\p{Suppliers2}. All DBPL statements and expressions referring to such an
``external'' variable 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 as arguments and return (relation) values that are converted
appropriately for further processing within DBPL. For example, the query
\begin{verbatim}
IF ALL s IN SupplierRel (s.Status > x) THEN ... END
\end{verbatim}
is translated into a \p{select from where} SQL expression that uses the 
actual value stored in the DBPL variable \p{x} of type
\p{SupplierStatusType}. 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.
\textheight 22.5cm

\subsubsection{DAIDA: An Environment for Data-Intensive Application Development}
\label{Sec:DAIDA}
In the DAIDA project\footnote{DAIDA was supported by Esprit Project
\#892.} \cite{SWBM89,JMW*90,Jark93}, software houses, research centers
and universities from five European countries have contributed to
solving the problem of intelligent development assistance for database
applications. Within the integrated DAIDA framework, DBPL served as the
target language for the implementation of high-quality database
application software while the application requirement analysis task and
the conceptual modeling process are expressed using specialized
high-level languages (Telos and Taxis DL, respectively). A central
contribution of DAIDA is the development of methodologies and tools that
assist the system analyst, system designer and database programmer in
the mapping process between the three languages involved. The mappings
and the associated design decisions are recorded in a global knowledge
base (ConceptBase \cite{JRJ93}) to support the long-term evolution and
maintenance of software systems.

\section{On Project Termination}
\label{Sec:Termination}

To summarize, the most prominent feature of the DBPL language is the
type-complete integration of sets and first-order predicates into a
strongly typed, monomorphic language with persistence as an orthogonal
property of individual compilation units. The DBPL system is further
characterized by its coverage of a wide range of operational database
demands, such as query optimization, transaction and distribution
management and computer-aided support for database application
development.

Over the years, we encountered several data modeling concepts
(inheritance, object identifiers, ordered bulk data structures,
triggers, \ldots) and database system requirements (communication
between concurrent processes, exception handling, \ldots) that did not
fit nicely into the original DBPL language framework. However, instead
of ``fixing'' these DBPL limitations by ad-hoc, incremental language
extensions, we tried to isolate the conflicting system or model
assumptions in the initial DBPL (or Modula-2) design.

More specifically, we regard the monomorphic type system of Modula-2,
the lack of first-class procedures, and the strict separation between
built-in and user-defined system functionality in the DBPL system
architecture as hard, built-in limitations which prevent, without
violating our design principles, DBPL extensions beyond the realms of
set- and predicate-based data models and first-order programming
languages.

As a consequence, our work in the Tycoon project\footnote{Tycoon: Typed
Communicating Objects in Open Environments.\\Tycoon is
supported in part by Esprit project \#6309 (FIDE$_2$).} \cite{MaSc92a} is
based on a higher-order polymorphic core language consisting of a small
set of highly generalized primitives for naming, typing and binding
\cite{ScMa93}. Our initial Tycoon experiments
\cite{ScMa90a,MaSc91,MaSc91b} suggest that the Tycoon framework by
virtue of the orthogonality of its contributing concepts goes
significantly beyond conventional relational, object-oriented and
deductive approaches.

In a similar vein, the Tycoon system architecture \cite{Matt93} aims at
increased system scalability, portability and interoperability with
commercial and standardized systems by ``unbundling'' database
functionality and separating data storage, data manipulation and data
modeling. To summarize, the Tycoon project carries forward in a more
general linguistic and architectural framework the experience gained
with bulk data typing, iteration abstraction, and modularization in DBPL.

\newpage
\textheight 22cm
{\small
\bibliographystyle{modified-unsrt}
\bibliography{../bib/florian}
}
\end{document}
