% File: IBM90.tex
% Date: 9.7.1990
% Author: FM, JWS
%
% Subject: IBM Symposium: Database Systems for the 90's / Nov. 1990
%

\documentstyle[lncs]{article}

\newcommand{\kw}[1]{{\tt #1}}
\newcommand{\missing}[1]{\centerline{\em #1}}


\setlength{\parskip}{0.25\baselineskip}
\setlength{\parindent}{0cm}
\setcounter{tocdepth}{2}
\pagestyle{plain}  % ##

\title{Language Technology for \\ 
       Post-Relational Data Systems
       \thanks{This research was supported in part by the European Commission
               under ESPRIT BRA contract {\#}�3070 (FIDE).}
\thanks{Appeared in: A. Blaser (Ed.), {\em Database Systems of
the 90s}, Lecture Notes in Computer Science, Vol.~466, 
Springer, 1990}
}
\author{Joachim W. Schmidt \and Florian Matthes}
\date{ {\small University of Hamburg \\
			            Department of CS \\
               Schl\"uterstra{\ss}e 70 \\
               D-2000 Hamburg 13 \\
               e-mail: schmidt@rz.informatik.uni-hamburg.dbp.de} 
     }
% --------------------------------------------------------------------------------     
\begin{document} 
\maketitle

\begin{abstract}

Practice has proven that databases are the keystones for  nearly all
application systems with a wider functionality, utilization and 
availabilty. As a consequence, next generation database systems will 
have to provide their services with a degree of  interoperability that
has to be substantially improved over existing  solutions. In this paper
we argue that this objective can be achieved  only through full
exploitation of current developments in computer language technology.

We claim that the merits of modern computer languages' naming schemes, typing 
systems and binding mechanisms are vital also for database management
systems if they want to improve the quality of their interaction with 
application languages and programming environments as well as their own
functionality and extensibility.

This paper studies the technological basis of modern computer languages
and presents DBPL as a working example of a highly interoperable database
programming language that exploits such technology.

Requirements of future data systems are discussed by emphasizing the 
abstraction principles considered helpful for the adequate design and 
organization of data-intensive applications and for the modularization,
localization and, finally, the implementation of data-based systems.
We conclude by relating the potential of advanced language
technology to such specific demands of the next generation of post-relational 
data systems.  \\

\noindent 
{\bf Key words:} database programming languages, query languages,
interoperability, open systems, language design principles, naming schemes,
type systems, binding mechanisms, DBPL.
\end{abstract}                                 

\thispagestyle{empty}

% --------------------------------------------------------------------------------     

\pagebreak

\section{Introduction}

There is no doubt that current research and development in computer languages
will have a significant impact on the process of programming and program
maintenance as well as on the architecture, functionality and, finally, the
overall quality of software systems. 

This quality improvement results only in part from the progress made in
isolating and providing the basic building blocks  for important classes of
applications, e.g. the essentials of systems communication, recovery and
persistence and by casting them into adequate {\em language primitives}.

More important, however, is the substantial progress made in understanding the
{\em fundamental abstraction principles} that enable the user of a language
to construct from a set of primitives a high-quality software solution,
i.e. a well-structured system with a high degree of modularity, genericity,
correctness and efficiency.

In the process of designing a computer language that aims for supporting such
abstraction principles a closely related set of technical problems has to be
solved that deals with the intimately related issues of naming, typing and
binding. Although such {\em language technology} is already well developed and
readily available its further extension and improvement is one of the main
subjects of research in computer languages. 

The purpose of this paper is to discuss the potential of language technology
and to exploit it for the development of {\em advanced data systems}. The
paper is organized as follows. 

Section 2 presents some basic principles of modern computer language design
and outlines the essentials of language technology. Furthermore, it
emphasizes the role of naming, typing and binding for systems with high
demands of interoperability. Section 3 discusses DBPL, a set- and
predicate-oriented database programming language that exploits language
technology to support abstraction principles and interoperability.

Requirements of post-relational data systems are addressed in section 4 with
particular emphasis on future needs of data-intensive applications. The paper
concentrates on demands for data modeling, interoperability and implementation
modularity and extensibility. Finally, in section 5 we discuss the potential
impact of advanced language technology for the design and development of
post-relational data systems.   


% --------------------------------------------------------------------------------     

\section{Language Technology and System Interoperability}

Current discussions of new database models and systems tend to
concentrate on the {\em expressiveness} of the particular query languages at
hand. This view is justified in a traditional setting where query languages
are the only means for interaction between  end-users and databases systems.

Experience with existing database systems and their query languages (like
Ingres, Oracle or DB2) demonstrates that the usability of a given language is
often severely impaired by its inability to be integrated smoothly into a
larger context. The classical example for such an integration is the
embedding of a query language into a host language necessary to provide
computational completeness, a prerequisite for application programming.
But there are other situations that reveal the {\em limited support for
interoperability} provided by existing database languages, such as the
coupling with a customized user-interface or the exchange of data with
standard software (e.g.\ spreadsheets like LOTUS 1-2-3).

There is a host of {\em ad-hoc solutions} to this problem of lack of
interoperability ranging from simple data conversion utilities and query
language cross-translators to sophisticated {\em fourth generation languages}
(like Ingres 4GL, SQL/Forms or ADF). However, these solutions have to be
considered as insufficient since they simply lift the interface problem
to a higher level without addressing the need for intrinsic extensibility and
orthogonality of concepts in order to attain the ultimate goal of
interoperability. A typical example is a fourth generation language like
Ingres 4GL that provides highly specialized support for convenient form
management and menu interfaces but that still has to rely on programming
language interfaces (without overall type security, without uniform naming
mechanisms) to escape its own lack of generality and universality.

In section \ref{SectionDBPL} we will present DBPL, a prototypical
member of the family of integrated database programming languages. These
languages aim to overcome the lack of interoperability and extensibility of
today�s databases by an integration of database
functionality into a general-purpose language. In the long run, database
programming languages are intended to replace the various language interfaces
(query language, data definition language, physical schema description
language, report definition language, etc.) by a single {\em linguistic
framework} with consistent naming, typing and binding mechanisms that is
expressive enough to unify this wide range of abstraction levels. 

The following subsections review fundamental concepts of programming
languages that are indispensable to attain such a high degree of safe
interoperability and extensibility in open systems.


\subsection{On the Design of Computer Languages}
%===============================================

A computer language can be described by a set of {\em primitive concepts}
(like values, variables, modules, semaphores, streams, databases, transactions \ldots)
and a set of {\em abstraction mechanisms} (like nesting of expressions or statements,
procedural abstraction, type abstraction, \ldots) that constrain and
assist the composition of these primitives to larger semantic units.

The set of primitive concepts found in a particular language depends heavily on its
application domain. Languages for mathematical applications might support complex
numbers, arrays, vectors with their associated operations whereas database languages
usually provide support for sets of entities and operations to access and manipulate
these data sets.

Despite the superificial disparity of the various general-purpose and
dedicated languages, there is a relatively small set of universal 
concepts that reappears one way or another in all of them. This paper concentrates
mainly on the universal concepts of {\em naming, typing} and {\em binding} and on
abstraction principles relevant for database programming.

The design of any computer language has to follow some {\em guiding
principles}. There have to be some criteria for evaluating the merits of
particular proposals. One such generally agreed upon criterion is the
{\em orthogonality} of its concepts (e.g. see \cite{Sebe89,Harl84}). This
principle states that all language concepts (e.g. typing, procedural
abstraction, assignment, \ldots) should be mutually independent of one
another so that there is no interference when they are used in arbitrary
combination. The principle of orthogonality thereby increases both the
expressiveness of a language (more combinations are possible) and its
understandability (there a fewer rules and exceptions to be learned).

Even in the restricted scope of relational query languages there is a
general awareness of the need for orthogonality of language concepts in
order to design expressive and understandable languages.\cite{Date89}
enumerates at length violations of the principle of orthogonality in the
current SQL standard. In particular, it is shown that SQL does not
fulfil the following minimum requirement for a good language design
\cite{Date84}: A language should provide, for each class of objects
it supports, at least the following:
\begin{itemize}

\item a constructor function, i.e. a means for constructing an object of the
class from literal (constant) values and/or variables of lower classes;

\item a means for comparing two objects of the class;

\item a means for assigning the value of one object in the class to another;

\item a selector function, i.e. a means for extracting component objects of
lower classes from an object of the given class;

\item a general, recursively defined syntax for expressions that exploits
to the full any closure properties the object class may possess.

\end{itemize}
The relevant classes of objects of a relational database system are tables,
columns, rows und scalars. However, there are {\em no} means to construct, compare or
assign individual rows in SQL. Furthermore, it is {\em not} possible to transform
arbitrary nested algebra expressions directly into nested ``table expressions'' of SQL
since there are limitations on the allowable nestings. 

Sections \ref{DBPLInteroperability} and \ref{AbstractionMechanisms} will
introduce additional criteria to evaluate the quality of a language design.


\subsection{Language Technology: Naming, Typing, Binding}
%========================================================

A {\em name} is a token used to identify some entity that can be talked about
by a computer language. A name is therefore said to be bound to an
entity. Traditionally, a {\em binding} consists of a name-value pair
\cite{Stra67} that can be augmented by a type \cite{BuLa84} and an
indication whether the value is constant or mutable \cite{AtMo85}. 
Such augmentations serve the purpose to restrict the binding of a name to
those entities that make sense in the context where the name is used -- and to
formally assure such semantic statements. Binding can take place at compile
time (static binding) or during program execution (dynamic binding)
\cite{MAD87}.

A binding is always performed with reference to a particular environment.
The {\em scope} of a name determines those parts of a program where it can
be used (e.g.\ to define other bindings). In static scoping, the scope can
be detected by a static analysis of program texts, whereas in dynamic
scoping these parts may vary from one program execution to another.

Values that can be named include atomic values (like integers,
characters, booleans etc.), composite values (like arrays, records,
relations of other values) but also variables (mutable values or
``containers'' for values), functions, procedures or views in database
systems.

A {\em type} can be associated with a binding to ensure that a name is
only used in an appropriate context, e.g.\ the field selection
\kw{Supplier.Name} should only be admissable if the name \kw{Supplier} is
bound to a value that is a record with a \kw{Name} attribute. Dynamic
type checking occurs when the run time system executes code to ensure
that the data is of the correct types. This typically occurs even in so-called statically checked languages in projections out of a union (e.g.
field selection from variant records in Pascal).

{\em Type systems} are one of the most important and critical issues in
language design (e.g.\ see \cite{A*89}). The advantage gained by the use of
type information is in a sense independent of the language it is embedded
in: it adapts equally well to functional, imperative, object-oriented,
and algebraic programming \cite{Card89}. 

A type system serves different purposes:

\begin{itemize}

\item Types support the selection of suitable (i.e. space or
time efficient) machine {\em representations} for data values. This
was the main purpose of type information in the early programming
languages (e.g.\ FORTRAN or COBOL). Especially in the presence of bulk
data this aspect must not be underestimated. 
                                                               
\item Type information guarantees that operations are only
applied to correct arguments, i.e. they help to avoid errors like
in the comparison \verb$"A" > 7$. The widespread use of type
information can thus be regarded as a partial specification of a
program. In this sense, types can be seen as {\em specifications},
and typechecking as a limited form of program {\em verification}. 
                                
Computer languages make heavy use of type information to increase
programmer efficiency and productivity in the construction of large
information systems. For example, most of the errors occurring in the
(untyped) interaction between programs and databases using
embedded DMLs can be detected even by the simplest type checker
\cite{BHR82}.

\item Types are {\em descriptions}. A type declaration in a DBPL
serves similar purposes as a schema description in a Data
Description Language of a DBMS. A particular database state is thus
an instance (a value) of that type. An important aspect of type systems is
therefore the ability to {\em name} types (e.g.\ Age, Dollar, Sex) and
re-use type descriptions.
                       
\item Powerful type systems support type {\em abstraction} to hide
irrelevant program information or to protect private
information from external access. Type abstraction thereby supports the
ordered evolution of large information systems \cite{Card89,DAIDA4}.

\item Finally, modern type systems support {\em genericity}, i.e. the
possibility to write operations with uniform behavior on values of
more than one data type. This kind of {\em polymorphism} is of particular
interest in information systems: A formalized notion of similarity of data
and algorithms enables the employment of re-usable and exchangeable
solutions to repeating patterns of information processing
requirements. 
    
\end{itemize}        


\subsection{Language Technology for Interoperability}
%=============================================


The designer of a computer language is faced with the problem of finding
appropriate naming, typing and binding mechanisms that enable the interaction
of as many computational units as possible and thus promote program genericity
and system interoperability.

Traditionally, programming language designers advocate static binding,
scoping and type checking, whereas database systems and operating systems
rely heavily on dynamic mechanisms. For example, the
existence of a \kw{CREATE TABLE} and \kw{DROP TABLE} command in SQL
implies that it is impossible to have a static binding between relation
names in queries and the stored database relation values. If a database
system furthermore allows the change or removal of individual columns from a
relation, it becomes impossible to perform static type checking
within query expressions since the correctness of a field selection from
a tuple of a relation (\kw{SELECT Supplier.Name FROM Supplier}) can
be invalidated at run time by a removal of the column \kw{Name}.

It should be noted that there exists a tradeoff between the flexibility
that can be achieved through dynamic binding, dynamic scoping and dynamic
typing and the security and efficiency supported by static binding,
scoping and typing.

Advances in computer language technology allow one to exceed the limits of the
traditional static binding and typing mechanisms (e.g.\ by means of
higher-order or polymorphic types) without sacrificing safety,
efficiency and understandability attainable with static mechanisms. A
presentation of some of these novel language concepts is the subject of
section \ref{AbstractionMechanisms}.


%--------------------------------------------------------------------------------     

\section{The Database Programming Language DBPL}
\label{SectionDBPL}

Based on the description of the general language principles of naming,
typing and binding given in the previous section we are now in a position to
illustrate these principles refering to a specific language in a relational
setting.


\subsection{An Overview of DBPL}
%===============================
\label{DBPLOverview}

DBPL \cite{SEM88} is a successor to Pascal/R \cite{Schm77} and addresses the
need for a uniform language framework for advanced database programming by
extending a well-understood system programming language (namely Modula-2
\cite{Wirt83}) by a small set of abstraction mechanisms needed for database
application programming \cite{DAIDA4}. DBPL extends Modula-2 into three
dimensions:

\begin{itemize}
\item bulk data management through a data type {\em set} (relation);

\item abstraction from bulk iteration through associative {\em access
      expressions};

\item {\em database modules} and {\em transactions} that abstract from
      persistence, sharing, concurrency control and recovery.

\end{itemize}

An essential guideline for the design of DBPL can be characterized by the
slogan ``power through orthogonality''.  Instead of designing a new language
(with its own naming, binding and typing rules) from scratch, DBPL
extends an existing language and puts particular emphasis on the
interoperability of the new database concepts with the given programming
language concepts.  In particular, DBPL aims to overcome the traditional
competence and impedance mismatch \cite{CoMa84} between programming languages
and database management systems by providing

\begin{itemize} 
\item a uniform treatment of volatile and persistent data, 
\item a uniform treatment of large quantities of objects with a simple 
      structure and small quantities of objects with a complex structure, 
      as well as 
\item a uniform (static) compatibility check between the declaration and the 
      utilization of each name. 
\end{itemize} 
         
Implementation details (e.g., storage layout of records, clustering of data,
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
runtime 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 {\em access
expressions} (i.e. first-order logic abstractions of bulk data access) in
typical DBPL programs facilitates such an approach.


\subsection{Naming, Typing and Binding in a Relational Environment}
%=================================================================

The first step towards a better integration of database concepts into a
language environment is to identify the basic database concepts and to
rephrase them in terms of an appropriate vocabulary of programming
concepts. 

The following paragraphs illustrate how DBPL captures the main principles
of set- and predicate-oriented database systems using the well-understood
notions of naming, typing and binding in procedural programming languages.


\subsubsection{Names and Types}
\label{Typing}

{\em Names} in DBPL are arbitrarily long sequences of upper and lowercase
letters and digits starting with a letter.

DBPL is a {\em statically and strongly typed} 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 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 the same.

DBPL provides the following {\em built-in types}: \kw{INTEGER}, \kw{LONGINT},
\kw{CARDINAL} (natural numbers), \kw{LONGCARD}, \kw{BOOLEAN}, \kw{CHAR},
\kw{REAL}, \kw{LONGREAL}.
\begin{verbatim}
TYPE Dollar = REAL;
\end{verbatim}
Values of these types are denoted by predefined names (e.g., \kw{TRUE})
or literals (e.g., \kw{0}, \kw{3.2E-2}, \kw{"A"}). It is furthermore
possible to introduce user-defined names for these values:
\begin{verbatim}
CONST DollarToDMRatio = 2.71;
\end{verbatim}
DBPL supports application-specific extensions of the set of basic
types. An {\em enumeration type} is defined by a list of names:
\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 the subrange 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 values of a base type to variables of a
compatible subrange type are checked at runtime.
 
{\em Strings} are treated as composite objects consisting of a sequence
of characters. Their type is therefore \kw{ARRAY [1..maxlength] OF CHAR},
where \kw{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 \kw{BOOLEAN} or \kw{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.\ \kw{supplier.Name}).
\begin{verbatim}
TYPE SupplierRecType = RECORD
                         Num     : SupplierNumType;
                         Name    : String;
                         Status  : SupplierStatusType;
                       END;                                            
     MadeFromRecType = RECORD
                         Num     : PartNumType;
                         Quantity: CARDINAL; 
                       END;
\end{verbatim}
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 and an ordered list of key
components: 
\begin{verbatim}
TYPE SupplierRelType = RELATION Num OF SupplierRecType;
     MadeFromRelType = RELATION Num OF MadeFromRecType;
     PartNumSetType  = RELATION OF PartNumType;
     Point2DSetType  = RELATION OF ARRAY [1..2] OF REAL;
\end{verbatim}                                                
The relation key defines a list of components of the relation element type
such that the relation always defines a 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
\kw{SupplierRel} of type \kw{SupplierRelType} can be expressed by the
following predicate stating that the equality of the key component \kw{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 is a synonym for an enumeration of all
components of the element type; in this case a relation is just a {\em set}
of relation elements. 

The example above declares two relation types (with record elements),
a set of natural numbers (\kw{PartNumSetType}), and a set of
points that are represented by their coordinates in the plane. 

In order to create ``containers'' for values of these (relation) types, it
is necessary to explicitly declare named {\em variables}. 
\begin{verbatim} 
VAR SupplierRel : SupplierRelType;
    OldSupplier : SupplierRelType;
    MadeFromRel : MadeFromRelType;
\end{verbatim}

In this respect, DBPL is a contrast to traditional relational
database systems, in which a \kw{CREATE TABLE} command subsumes the
declaration of an (anonymous) relation type and the declaration of a named
relation variable.

It should be clear that the above set of naming and typing rules allows one
to express (at least) the structures of the relational data model with a
fine-grained control over the basic domains.


\subsubsection{Scopes, Bindings and Lifetime}

\label{DBModule}
The above descriptions of the naming and typing rules have to be extended
by rules defining the scope of names and the lifetime of objects denoted
by these names. In order to do so we first have to introduce the concept
of a {\em module}.

A module constitutes a sequence of name definitions and statements (to be
discussed later in \ref{Operations}). A typical DBPL application 
consists of a multiplicity of modules. DBPL supports separate
compilation, i.e. modules can be developed independently. A module can
{\em import} names that are {\em exported} from other modules that
include definitions for these names or that simply import these names from
a third module. The compiler enforces the consistent use of names across
module boundaries following the typing rules above. 

The {\em scope} of a name \kw{n} declared in a module \kw{M} extends
over the whole body of \kw{M} and over all Module \kw{M$_{i}$} importing
\kw{n}. Names have to be unique within a scope. Modules are in turn
identified by names. In DBPL there is a single global scope for module
names. 

  
\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;
END SupplierPartDB;               
\end{verbatim}
\caption{A typed relational database schema in DBPL}
\label{FigSchema}
\end{figure}  

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

Since the import relationships between modules have to be declared
statically, there is no possibility for name conflicts and ambiguities at
runtime.

Modules can be defined as \kw{DATABASE} modules. All variables declared
within such a module are {\em persistent}, i.e. in contrast to other
program variables their {\em lifetime} exceeds a single program execution
\cite{ABCCM83}. To be precise, the lifetime of a persistent variable is longer
than that of any program importing it. Ordinary and persistent modules
therefore allow the modelling of both, transient and persistent data objects.

Persistent variables are {\em shared} objects and can thus be accessed by
several programs simultaneously. An access to a persistent variable must be
part of the execution of a transaction (see section \ref{Transactions}).


\subsubsection{Expressions and Operations}
\label{Operations}\label{Expressions}

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 types (\kw{v1}, \kw{v2}, \kw{v3}) and relation types (\kw{v4},
\kw{v5}, \kw{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 \kw{v5} and
\kw{v6} contain nested value constructors, e.g.\ \kw{v6} is assigned a
relation that contains a single record (of its element type
\kw{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 of a structured value:
\begin{itemize}
\item 
    Elements of an array are selected by an index value of their index type,
    enclosed in square brackets (e.g., \kw{vector[7]});
\item
    Fields of a record are selected by their field name (e.g., 
    \kw{supplier.Name});
\item
    Elements of a relation are selected by their key value, enclosed in
    square brackets (e.g., \kw{SupplierRel[7]}).
\end{itemize} 
Variable designators of DBPL therefore 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 query expressions} for relation types. There are three
kinds of query expressions, namely boolean expressions, selective and
constructive expressions.
 \begin{description} 
\item[Quantified Expressions] yield a boolean result (i.e. \kw{TRUE} or
\kw{FALSE}) and may be nested:
\begin{verbatim} 
SOME Supplier IN SupplierRel (Supplier.Name = "John") 

ALL Supplier IN SupplierRel (Supplier.Status = important) 

ALL Part IN PartRel (Part.State <> base) OR 
  SOME Supplier IN SupplierRel 
    (Part.SuppliedBy = Supplier.Num) 
\end{verbatim} 

The comparison operators ($=$, $<>$, $>=$, $<=$, $<$) for relations are
abbreviations for key-based quantified expressions, e.g.\
\kw{SupplerRel1$>=$SupplierRel2}  is equivalent to   
\begin{verbatim}
ALL s1 IN SupplierRel1 SOME s2 IN SupplierRel2 (s1.key = s2.key)
\end{verbatim}

The test for membership (\kw{thisSupplier IN SupplierRel}) is equivalent to
\begin{verbatim}
SOME s IN SupplierRel (thisSupplier.key = s.key)
\end{verbatim}

\item[Selective Access Expressions] are rules that select subrelations.

\label{SAE}\begin{verbatim}
EACH Supplier IN SupplierRel: Supplier.Status = important
\end{verbatim}                                      
selects all elements \kw{Supplier} of the relation variable \kw{SupplierRel}
that fulfil the selection predicate \kw{Supplier.Status $=$ important}.

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


\item[Constructive Access Expressions] are rules for the construction of
relations based on the values of other relations:
\label{CAE}\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 \kw{NameRecType} is a record of two strings defined as
\begin{verbatim} 
TYPE NameRecType = RECORD Part, Supplier: String END
\end{verbatim}
The construction rule above defines how to derive 
the names of all base parts with their suppliers from the two stored
relations \kw{PartRel} and \kw{SupplierRel}.

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 \kw{OF}), evaluated for all combinations
of the element variables (\kw{p}, \kw{s}) that fulfil the selection
expression \verb$(p.State = comp) AND (p.SuppliedBy =s.Num)$:

\begin{verbatim} 
NameRelType{
  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 the result relation type has to be defined as
\begin{verbatim}
TYPE NameRelType = RELATION OF NameRecType;
\end{verbatim}
\end{description} 

Note, access expressions do not denote relations; only in the context
of a relation constructor \verb$RelType{...}$ do they evaluate to a relation.
Other contexts in which access expressions can be used are given below.

In addition to these (side-effect free) expressions, DBPL provides specialized
{\em set operators} (\kw{:=, :+, :-, :\&}) for relation updates 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{Typing}.
As illustrated by the examples above, the nesting of DBPL
expressions captures the essence of relational query languages, namely to
provide {\em iteration abstraction} by means of high-level set-oriented
selection, construction and update mechanisms.



\subsection{Interoperability for Database Programming}
%======================================================
\label{DBPLInteroperability}

The above presentation of structures, expressions and statements of DBPL
departs from the main stream of ``standardized'' query languages in order to
achieve interoperability with strongly typed programming languages by means
of uniform naming, typing and binding mechanisms.

The following sections illustrate the advantage, in terms of increased data
manipulation, data description and data abstraction power, that is obtained
by investing language technology into the relational data model


\subsubsection{Computational Completeness}

The main reason to couple a DBMS with an algorithmically complete
programming language is to utilize the expressive power of the language
environment for arbitrary complex operations on the data stored in the
database. 

DBPL incorporates all data types, operations and control structures of
the system programming language Modula-2 \cite{Wirt83}, including 
recursive functions and procedures, higher-order functions and elaborately
structured statements (\kw{IF THEN ELSIF ELSE}, \kw{CASE}, \kw{WHILE},
\kw{REPEAT}, \kw{FOR}, \kw{LOOP EXIT} etc.). DBPL is therefore an ideal
environment for the implementation of complex database application
programs.

It should be noted that database and programming language features of a
database programming language should not simply reside side-by-side. On the
contrary, one needs many interfaces to create synergy between these
features. DBPL therefore allows the orthogonal combination of the concepts
inherited from both worlds, 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 (see \ref{Expressions}) can appear not only
within query 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}

As it turns out, the use of a (generalized) relational calculus instead of a
relational algebra facilitates such an approach, since predicates as
boolean-valued expressions can be utilized in a broader range of contexts
than pure relation-valued algebra expressions.

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{Expressions}) denoting a subset 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}


\subsubsection{Type Completeness}

In addition to the concept of computational completeness, DBPL adheres to
the language design principle of {\em type completeness} \cite{AtBu86}, i.e.
all type constructors of DBPL (relation, record, variant, array)
have equal status within the language. It is therefore possible to apply these
type constructors to arbitrary other types (e.g.\ to declare arrays of
relations or relations of variant records containing relations of integers).
Furthermore, values of these types can be used in expressions, assignments or
as parameters in a uniform way.

Finally, DBPL provides {\em orthogonal persistence} \cite{AtBu86} for
values of the base types and values constructed by means of the above type
constructors. The persistent variables declared within a database module
(see \ref{DBModule}) are not limited to relation types. This makes it
possible to declare, for example, a persistent boolean variable within a
database module.

As illustrated in the database schema of Fig.�\ref{FigSchema}, the concept
of type completeness therefore naturally leads to a data model that supports
the declaration of {\em complex objects} \cite{AbBe88} and
non-first-normal-form relations \cite{AFS89} thereby breaking the
restrictions of the classical relational data model that is limited to
relations of records with attributes from the basic domains.



\subsubsection{Completeness of Abstraction Mechanisms}

Up-to-date programming languages provide two important abstraction
mechanisms to achieve localization of information in large software systems
\cite{Sebe89,LiGu86}. {\em 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.{\em Type abstraction} allows programmers to abstract from
the implementation of a data structure and to operate on it only via a
well-defined interface, i.e. 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{Wirt83}. In addition,
DBPL provides {\em selectors} that abstract over selective access expressions
and {\em constructors} that abstract over constructive access expressions
(see \ref{Expressions}). These two abstractions capture the essence of
updateable and non-updateable {\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 following selector named \kw{ImportantSuppliers} defines an
updateable view on the supplier relation, selecting those suppliers having
\kw{important} as their status (see also p. \pageref{SAE}). 
\begin{verbatim}
SELECTOR ImportantSuppliers: SupplierRelType;
BEGIN
  EACH S IN SupplierRel: S.Status = important
END ImportantSuppliers;
\end{verbatim}

The constructor \kw{SuppliersForParts} (see also p. \pageref{CAE}) names a
non-updateable view that is derived from the base relations \kw{PartRel} and
\kw{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 {\em
recursion}. The semantics of a recursive query expression in DBPL is not
defined operationally (as it is common practice for procedures) but as
a least fixed point of recursive set equation \cite{JLS85,DAIDA4}. Thereby
constructors are at least as expressive as recursive DATALOG programs
with stratification semantics \cite{Mink88,Naqv89}.

\label{Transactions}
Another important abstraction mechanism of DBPL is the {\em
transaction} \cite{Gray81} that allows database programmers to abstract
from concurrency and recovery issues when accessing persistent and shared
database variables. Transactions can be regarded as atomic with respect to
their effects on the database. In particular, the implementation of DBPL
guarantees that concurrent transactions will be executed in a serializable
schedule.
\begin{verbatim}
TRANSACTION DeleteSuppliers(Suppliers: SupplierRelType): BOOLEAN;
(* returns TRUE on success *)
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;
\end{verbatim}          

In section \ref{AbstractionMechanisms} we will relate the above
abstraction mechanisms by embedding them into a larger context and discuss
their relevance for database programming.


\subsubsection{External Interfaces}

Even in a sound, computationally-complete and self-contained language
like DBPL, there are situations that demand communication with
external components like user interface management systems (such as Motif or
Open Look), network services, or simply with existing software components
coded in other standard programming languages like Pascal, C or COBOL. 

The challenge to integrate database programming languages into an
{\em open system architecture} is mainly a technological problem
and not a language design task. The current implementation of DBPL
\cite{S*88,ScMa90} (running under VAX/VMS) takes the following approach to
interoperability in a heterogeneous multi-language environment:
\begin{itemize}

\item There is a special class of modules (called \kw{FOREIGN DEFINITION
MODULES}) that contain signatures of procedures coded outside the scope of
the DBPL compiler. The use of these procedures is analogous (w.r.t. naming,
type checking and binding) to ordinary DBPL procedure declarations.

\item The DBPL compiler generates for every DBPL module an object code
file in the standard VAX-VMS linker format. The linker is therefore capable
of linking DBPL modules with object code generated by virtually all VAX/VMS
compilers.

\item Procedures and variables declared within individual DBPL modules can be
used from other languages, as long as they do not contain relation, selector
or constructor types.

\item The DBPL compiler generates debugger tables that can be interpreted by
the standard VAX/VMS multi-language debugger. This makes it possible to
set breakpoints as well as display and modify individual variables during the
execution of compiled DBPL programs.
\end{itemize}

The need for an {\em ad-hoc query interface} is addressed in DBPL by means of
a language-sensitive editor \cite{NiSc89} that was constructed using a
powerful system for the generation of language-sensitive tools
\cite{ReTe89,ReTe88}. The main idea is to simplify the task of an end-user
that wants to query a database not by an ad-hoc restriction of the
language to a subset of DBPL, but by providing {\em immediate}
feedback (e.g.\ on undeclared names or type mismatches) during textual or
form-oriented query input following the paradigm of {\em direct
manipulation}.


% --------------------------------------------------------------------------

\section{Requirements of Post-Relational Data Systems}
\label{AbstractionMechanisms}

The relational data model definitely is an important milestone in the
process of understanding the needs of data-intensive applications and of
developing a sound technological basis for database management systems.  
However, in the light of the above discussion, we see several severe
limitations of the relational model, of which only a few are addressed by 
currently developed relational extensions \cite{D*86,PiAn86,Sche88,Mink88}.

Shortcomings that are more difficult to repair (if at all) result from the
exclusively value-oriented approach advocated by relational data
modelers: ``all information in the database is represented as values in
tables'' (see foreword by Codd of \cite{ScBr83}). Realizing the limitations
of such a semantically poor basis this served as a starting point for a more
generalized view on data modeling \cite{SmSm77,Codd79} and resulted in a far
better understanding of the principles of {\em data abstraction}
\cite{AbHu87,AbKa89,Beer88}.

An important structural goal for many data-intensive applications is to
extract a maximum of relevant information from individual application
programs,  localize it in a separate environment, and then make it available
to a wider user community. However, by restricting itself to the
localization of data, the relational model does not fully exploit the
potential of {\em localization abstraction}.

Database management systems themselves turned out to be data-intensive
applications in a similar sense that compilers of algorithmic languages are
complex algorithmic programs. However, the interaction between two
computational entities in an algorithmic program, say, entering an abstract
representation of a conference deadline into a priority queue, differs
substantially from passing a user-defined persistent date value to an
optimizing join algorithm. Therefore, database applications are expected to
have particular demands for {\em implementation abstraction}.

To draw a first conclusion, we argue for the development of DBPLs that
support the increasing demands of data-intensive applications on the basis
of a small set of built-in functional primitives that are well-supported by
a body of abstraction principles which can be freely combined to ease and
encourage the construction of functionally extensible data environments. We
see this approach in contrast to the more or less ``random'' addition of
packaged functionality to relational database systems (like subtables,
triggers, graphical interfaces, \ldots).

In this section we want to motivate our approach by characterizing the
essential subtasks that arise in the implementation, extension and
maintenance of advanced data-intensive application systems. We will
concentrate on the principles of
\begin{itemize}

\item data abstraction, 

\item localization abstraction,

\item implementation abstraction,

\end{itemize}
that capture the essence of data modelling, software engineering and system
coding. They are intended to provide a sufficiently general and well-understood basis for the database languages of the 90ies.


\subsection{Data Abstraction}
%============================
\label{DataAbstraction}

The data modeling task of database applications can be characterized by the
need to describe large collections of entities by {\em heavily constrained
data} with rather simple manipulation operations (create object, remove
objects, update object attribute). Constraints can be classified into
{\em static constraints} (like attribute constraints, object constraints,
set constraints or dependency constraints)  that have to hold in each
database state and {\em dynamic constraints} as, for example, expressed by 
pre- and postconditions in transaction specifications
\cite{SWBM89,SSB86,CRBM88}.

Research and development in the area of conceptual modeling 
\cite{BMS84,MyBr89} has isolated three basic {\em data abstraction
principles} \footnote{The term {\em data abstraction} is sometimes used in
the programming language literature to denote encapsulation (see section
\ref{LocalizationAbstraction}), a mechanism to attain {\em localization
abstraction}.} that are sufficient to capture an important subclass of static
constraints, namely the structural invariants of data objects
\cite{SmSm77,Brod84}:

\begin{description}
\item[Classification / Instantiation] is a form of data abstraction in which
a collection of objects is considered as a higher level object class. An
object class is a precise characterization of all properties shared by each
object within the collection. Classification represents an {\em instance-of}
relationship between an object in the database and its object class that
allows to identify, classify, and describe objects.

\item[Aggregation / Decomposition] is a form of data abstraction in which a
relationship between component objects is considered as a higher level
aggregate object. This is the {\em part-of} relationship.

\item[Generalization / Specialization] is a form of abstraction in which a
relationship between object classes is considered as a higher level
generic object. This is the {\em is-a} relationship.

\end{description}

Much of the power of these three abstraction principles comes from their
{\em orthogonality}, i.e. the possibility to apply classification,
aggregation and generalization to objects that already have been abstracted
over, e.g.\ to define metaclasses (classes of classes \cite{MyBeWo80}),
nested aggregates (complex objects \cite{AbBe88}) or generalized generic
objects (multi-level inheritance hierarchies \cite{BMW84}).

Following \cite{Dijk76} and  \cite{BrRi84} these data abstractions can
furthermore guide the top-down design of database transactions by mapping
operations on composite objects into composite operations (sequencing, case
analysis, iteration) on component objects. 

Such a {\em hierachical decomposition} should be supported by appropriate
language mechanisms like set-oriented operations (selection, construction),
tuple  operations (field selection, record construction) and mechanisms to
view specialized objects as generic objects or to project generic objects
into specialized objects.

The classical relational data model only provides support for
classification by means of relations and aggregation of atomic values
within individual relation elements. Generalization, repeated aggregation,
or repeated classification is beyond the scope of a relational DBMS. A
first step to overcome these limitations was the inclusion of the concept
of generalization into the set of abstraction mechanisms applicable to data
values \cite{SmSm77}. The conceptual modeling language TAXIS \cite{BMW84}
extends this framework further by allowing one to aggregate, classify and
generalize not only data values but also transactions, constraints and
exceptions. Finally, object oriented languages rely heavily on the
aggregation of data and operations (procedural attachment) as well as the
possibility of specializing and generalizing these aggregates (inheritance)
\cite{Banc88,KiLo89,A*89b}.


\subsection{Localization Abstraction}
%====================================
\label{LocalizationAbstraction}

Due to the evolutionary nature of database applications (arising from changes
in the application domain itself or from add-on extensions to existing
application programs), the initial implementation of a database program
already has to take future incremental modifications and extensions into
account.

The main quality criteria to be met by data-intensive applications are
therefore:
\begin{description}

\item [Controlability] of data access. Sharing and persistence in a database
environment have to be controlled by appropriate authorization and protection
mechanisms. They should provide a fine-grained control over the set of data
objects and operations available to individual users and application programs. 

Database systems traditionally make heavy use of dynamic views and dynamic sets
of access rights (capabilities) whereas programming languages usually attain
controlability by means of static scoping and encapsulation mechanisms
\cite{CDMB90}.

\item [Extensibility] of data structures and application programs: Extensions
range from simple additions of attributes, classes, relationships or inclusion
of new queries and update transactions to the weakening or strengthening
of database-wide integrity constraints. It should be possible to perform
extensions in a way that does not disrupt the overall structure of
existing applications and data structures and that minimizes the need for
reverification of existing applications.

\item [Reusability] of data and operations. One of the main motivations for
the use of (centralized or distributed) database systems is the desire to
re-use and share information among larger user communities. By now it has
become obvious that a mere sharing of ``raw data'' (like employee records)
in some cases contradicts the goals of controlability and correctness as
explained above. A first solution to this dilemma is the {\em encapsulation} of
data objects where methods are the only means to interact with an object
\cite{Banc88,BCD89,KiLo89,LRV88,MSOP86}.

\item [Correctness] with respect to the (informal) specifications,
especially in the presence of incremental changes. For example, integrity
constraints on data objects (even those ``coded into'' application
transactions) have to be respected by all update transactions, especially
those implemented at a later point in time.

\end{description}

The typical approach to support these quality criteria during the evolution of
applications in a language framwork is based on the principle of {\em
localization abstraction}. The principle is based on the idea to localize
definitions, i.e. to ``factor out'' repetitive information from applications
and to replace them by a reference to a single, named declaration and to group
related information in a local scope. 

Classical examples of this principle are the declarations of named constants,
types and operations in Pascal-like programming languages. But databases
adhere to this principle also by factoring out objects and integrity
constraints from multiple application programs and localizing them in a
uniform, {\em centralized database schema}. By forcing application programs to
access data objects only through controlled database system services, DBMS
can guarantee a certain degree of correctness, controlability, extensibility
and reusability.

It is clear that the traditional model of a database (essentially a
single, global, unstructured store with a pool of integrity constraints)
is an insufficient model to support incremental modifications for large
database applications.

A first step towards a more uniform treatment of localization abstraction
in a relational environment was presented in section \ref{DBPLOverview}
by an extension of the module concept of Modula-2. Section
\ref{AdvancedLocalization} presents a more detailed discussion of new
binding and typing mechanisms that allow more flexible interfaces
between database systems and their clients. 



\subsection{Implementation Abstraction}
%====================================
\label{ImplementationAbstraction}

The previous two subsections were mainly concerned with modeling and
software engineering aspects of database applications. Because of the size,
value and longevity of the data to be dealt with, database applications
also have a strong demand for {\em non-functional support} to be provided
by a database system. 

The implementation of a lookup table may illustrate this aspect.
In a programming language setting, it is sufficient to implement a lookup
table by means of a hash table or a search tree. The implementation of a
lookup table is therefore adequately described by its operations (insert,
remove, lookup) and its time and space requirements. In a database
environment implementors of a persistent and shared lookup table have to
take care of the storage management on disk, avoid interference
between concurrent update operations and guarantee the integrity
of the data structure in cases of program failures or system crashes.

These additional non-functional (or operational) requirements of database
applications can be summarized as follows:

\begin{description}

\item [Persistence Management] allows application programmers to abstract
from low-level aspects of data representation, e.g.\ whether objects are
held in main memory or on secondary store, how objects are identified (virtual
addresses or tuple identifiers), when objects need to be transferred between
multiple nodes in a network, etc. \cite{ABCCM83,AtMo85a,KhVa88,Moss89}.

\item [Bulk Data Management] allows one to abstract from details of the underlying
data structures and access support structures, e.g.\ how objects are clustered
on disc or in main memory, which index structures have to be maintained during
update operations, which access paths can be utilized to speed up set-oriented
query evaluation, etc. \cite{AtBu86,A*89}.

\item [Support for Atomicity] is needed to define higher-level operations that
abstract from the possibility of failure of the lower-level
operations that are used by their implementation \cite{WeLi81,LCDS87}.

\item [Support for Concurrency Control] is needed to abstract from possible
interferences arising from concurrent access to shared data objects by
multiple threads of control \cite{BHG87}.

\end{description}

It should be noted that, for example, in a relational database management
system these requirements are met by a small set of highly interrelated and
generic concepts, namely set data structures, set-oriented query
languages and the traditional (and highly overloaded) transaction model.
The extreme complexity in the implementation of efficient, recoverable
and concurrent access to persistent, shared data structures thereby
remains completely hidden from database application programmers. The
necessity of hiding in particular the heavy non-functional requirements
from the clients of an operation demands language support for {\em
implementation abstraction}. 

Traditionally, implementation abstraction is achieved in a DBMS by using
{\em generic} mechanisms that perform persistence management, bulk data
management, query optimization, concurrency control and recovery for {\em
all possible} data structures and user transactions. This genericity can
only be attained based on a priori semantic knowledge of algebraic
properties about sets, set operations and transactions.

However, as soon as advanced database languages permit substantial extensions or
variations to be performed at the application level, there arises the need to
open and extend the up to now fixed and pre-canned functionality of a DBMS
at lower levels. Based on additional semantic knowledge of the application
domain, a DBMS has to allow application-specific extensions to the
persistence management, the bulk data management, the query optimizer etc.

Examples of such extensions are new base types, abstract data types,
user-defined collection types, user-defined operations on complex objects,
queries or functions as first-class language objects etc. Extensible database
systems \cite{Bato86,BeLo88,C*86,CDeW88,GoOr88,SAH88,HFLP89} usually provide
well-defined specialized interfaces to lower levels (e.g.\ to the index
manager or to the query evaluator) of the database system to ``plug in''
user-defined code. This DBMS kernel code written in a standard
programming language like C or a specialized database implementation
language like E \cite{RiCa87,Rich89} can be called by DBMS extensions
that implement, for example, application specific query languages.

% --------------------------------------------------------------------------


\section{The Potential of Advanced Language Technology}

The descriptions of the abstraction mechanisms for database programming
in the previous section remained deliberately abstract and general in
order to be able to specialize these concepts to the wide range of
languages proposed for the task of database programming. These proposals
range from standard query languages, functional query languages,
logic-based languages, relational database programming languages,
persistent programming languages to  object-oriented languages.

Without bias towards any of these solutions, one can predict that the
current development of language technology will have a significant impact on
the quality of the language interfaces for next-generation database systems.
The following subsections  give references to relevant literature and
highlight the most promising achievements of today�s language technology.


\subsection{The Ubiquitous Data Abstraction}
%========================================

The three data abstractions (aggregation, classification and generalization
as described in \ref{DataAbstraction}), rooted in the realms of knowledge
representation, heavily influenced the design of new data models
\cite{Alba83,AbHu87,DaVa88,HuKi87,LRV88,MaDa86} and are currently being
``discovered'' by type systems of database programming languages
\cite{AtBu86,ABM88}.

The intuitive interpretation of a {\em type} describing a set of
values \cite{CaWe85} captures an essential aspect of the concept of
classification \cite{Alba83,BaBu84}. This static classification based on
structural properties of data values and functions is furthermore theoretically
well-defined \cite{Reyn74,Miln78,DaMi82,OhBu88} and effectively
enforceable by means of static or dynamic type checkers
\cite{Matt87,BBO89}. 

Imperative and procedural programming languages have a long tradition in
representing the concept of aggregation by means of records \cite{Hoar68},
structures or tuples as found for example in COBOL, Pascal, Ada,
Modula-2 or C. On the other hand, functional languages and the theory of
programming languages ``neglected'' labeled cartesian product types and 
expressed aggregation simply by means of pairs, triples, \ldots\
\cite{FiHa88,Hudak89,Nikh85,Turn85}.

However, motivated by the strong interest in object-oriented concepts, record
types are currently receiving renewed interest not only from programming
language implementors \cite{S*86,Meyer88,Card88} but also from type
theoreticians \cite{Card84,Wand87,Stan88,OhBu89}. These languages introduce a
{\em subtyping} relationship between record types that allows one to utilize the
powerful data abstraction principle generalization in a strongly typed
framework. 

To summarize, striking parallels exist between the data abstraction
principles of conceptual modeling and fundamental concepts of modern type
systems. A further analogy is the fact that type systems also obey the
principle of {\em orthogonality}. A second-order $\lambda$-calculus
\cite{Reyn74}, for example, allows one to name types, to pass types as
parameters, to abstract over type expressions (yielding type operators) etc.
Recent development in programming language design \cite{Card88b,Card89} and
type theory \cite{CaLo90} even introduces a three level structure consisting
not only of values described by means of types (the traditional two-level
structure) but also of a third layer of {\em kinds} that classify types into
simple types, type operators, etc.

Finally, there is now a solid understanding of the mechanism of {\em type
inference} \cite{Miln78,DaMi82,Hudak89}, that allows one to omit the (sometimes
cumbersome) type annotations from expressions, statements, and functions
and to write generic queries and transactions. The compiler is not only
able to derive the missing type information from the operations performed
on the data values, but it also detects the {\em most general} polymorphic
type of every variable and parameter. Such a typing scheme is therefore
also a big step towards the goal of language support for localization
abstraction.


\subsection{Advances in System Architecture and Implementation}
%================================================
\label{AdvancedLocalization}

Today�s programming languages (like Ada \cite{I*83},
Modula-2 \cite{Wirt83}, Modula-3 \cite{Card88}, Eiffel \cite{Meyer88} or
Standard-ML \cite{Wiks87,HMT88}) provide sophisticated naming, typing and
parameterization mechanisms to define fine-grained and generic modules that
are robust with respect to local changes and that can be bound to
different \mbox{(type-)}parameters to be re-used in different contexts. 

Localization abstraction therefore requires database as well as language
support (see also \cite{LiGu86}): 
\begin{itemize}

\item data centralization as found in database systems including sharing,
concurrent access and integrity maintenance;

\item functional abstraction and parameterization \cite{L*77,AtMo85,LiGu86}
including higher-order functions and explicit or implicit type parameters
\cite{DeDo79,Miln78,DaMi82};

\item modularization and encapsulation including separate compilation
\cite{Wirt83}, type abstraction \cite{BuLa84,CaMcQu88}, and appropriate
incremental binding mechanisms \cite{Dea89}.
\end{itemize}

As explained in section \ref{ImplementationAbstraction}, extensions of
extensible database management systems are usually coded  in a standard
programming language like C or a specialized database implementation
language.

We argue that the coding of such application-specific extensions should be
understood also as part of the global database programming task. Furthermore,
it should be clear that for this particular subtask there is a strong
demand for the abstraction mechanisms presented in section
\ref{DataAbstraction} and \ref{LocalizationAbstraction}, like encapsulation,
procedural abstraction, strong and polymorphic typing, inheritance etc. 

If one adopts this holistic point of view, DBMSs can be viewed essentially
as  collections of highly generic and extremely reusable functions and
abstractions available in a database programming environment. These
functions can not only be utilized by building application programs calling
them, but they also provide ``hooks'' for user-specified extensions written
in the same language yet at a lower abstraction level.

As soon as one attempts to describe the functionality of a fully-fledged
database system in such a mono-linguistic framework one recognizes that
there are several places where a DBMS needs to perform {\em magic}. The most
striking example is the process of query optimization. Apparently, a DBMS
must have the ability to ``reason'' about a given query expression prior to
its execution, and, as a result of that reasoning, transform a query into a
semantically equivalent one that can be executed more efficiently.
Clustering of data objects and recovery are two other {\em magic} mechanisms
that are part of the {\em implementation abstraction} provided by the DBMS.

We claim that the essence of DBMS implementation abstraction can be captured
by three distinct language mechanisms:
\begin{description}

\item [Core Language Definition:] There has to be a small set of basic
language primitives (e.g.\ exception handling, persistence of simply
structured data values, lock primitives, atomic operations). These
primitives need to be built-in, since their implementation is beyond the
scope of a high-level (typed) programming language.

\item[Declaration Correspondence:] This principle introduced by Landin
\cite{Land66} heavily influenced the design of several languages
\cite{Harl84,BuLa84,Card89}. Its initial technical definition states that a
programming language obeys the declaration correspondence principle if
anything that can be declared inline can also be passed as a
parameter. All subsequent additions to this principle try to capture the
idea that a language should provide means to abstract from implementations
in such a way that a client using this functionality is unable to
distinguish it from built-in language constructs. Loosely speaking, this
means that all language constructs and values have the same ``civil
rights''.

\item [Reflection] is the ability of a system to support its own evolution.
This may entail changes to the programs that describe the system and the
types used by the system. Reynolds \cite{Reyn72} showed (in terms of the
$\lambda$-calculus) that it is impossible for a system to support itself in
the same language it is written in. This means that systems have to resort to
a lower level technology to express some part of the reflection. Examples for
reflection are the \verb$eval()$ function in Lisp (untyped, dynamically
bound), the {\em callable compiler} in the persistent store of PS-algol
\cite{ACC81a} and Napier \cite{DCBM89} (statically typed, dynamically bound)
and {\em generic forms} in ADAPTBL \cite{SFSS90} (statically typed and
statically bound).

\end{description}

Reflection seems to be a key mechanism in achieving the ``magic'' involved in
the process of query optimization: a query optimizer could use reflection to
access the code of a query expression submitted for evaluation, to obtain
information about existing access paths within the system and to construct a
new code for an equivalent query expression using these access paths.

% --------------------------------------------------------------------------

\section{Summary and Conclusion}

Looking back on two decades of relational database history one observes
contributions on three different levels.

The relational database {\em model} is, of course, a very important
contribution and provides a solid basis for a number of advanced data
modeling capabilities:

\begin{itemize}
\item reasonable data structures for a variety of commercial
applications,

\item concepts for very powerful queries and integrity
constraints,

\item	an adequate approach to database updates.
\end{itemize}

As a second contribution, relational database {\em technology} has
isolated and solved a variety of hard problems. It produced, however,
only tailor-made implementations in which solutions of conceptually
independent issues were bundled:
\begin{itemize}
\item	only sets of records over limited domains can be defined and made
persistent;
\item optimized associative access is provided only for flat
relational structures;
\item	the notion of transaction has highly specialized and overloaded
semantics.
\end{itemize}

The development of relational database {\em languages} was a third
contribution. However, it is now widely agreed that hardly any of them
reached the then state-of-the-art in language design. Some of them even
hindered the full exploitation of the relational model and led to various
mismatches in database application programming \cite{Date89}.

Currently, much effort is invested in the development of new data systems
which support typical database functionality and aim for going
substantially beyond the relational approach. Examples are the
object-oriented systems and the various forms of programming languages
with bulk data structures and persistence. 

What do we expect from such post-relational data systems? To put it
succinctly, we expect three contributions: generalization of the model,
unbundling of the technology and, in particular, improvement of the
languages.

To draw the comparison with the relational contributions as outlined
above, we anticipate post-relational data {\em models} to be liberated
from essential relational restrictions in that:

\begin{itemize}
\item	new typing schemes will be exploited and data models will become
type-complete and orthogonal;
\item bulk operators and assertions will be  generalized;
\item algorithmically complete constructs for data evaluation and
manipulation will be provided. 
\end{itemize}

From post-relational data {\em technology} we require the unbundling of
its essential contributions and provision of its capabilities independent
of one another:

\begin{itemize} 
\item persistence will be given to an enlarged or even open set of data
types and type constructors;
\item efficient implementations of adequate abstraction mechanisms for
bulk data access, modularization, interface definition and control etc.
are expected;
\item	support is needed for an appropriate set of base mechanisms for
non-functional requirements such as concurrency control, recovery and
communication.
\end{itemize}

Finally, we expect that post-relational data {\em languages} will utilize
modern language technology to bundle (or bind) the above capabilities
according to the specific needs of the problem at hand:
\begin{itemize}
\item	to allow for appropriate naming schemes for object identification
and reference; 
\item to offer binding mechanisms that allow users to choose
from a wide range of naming schemes, types, values and mutability
restrictions which abstract and protect best an object�s relevant
properties;	
\item	to capture additional object properties through extra capabilities
for flexible scoping, sharing and lifetime definition or an appropriate
recovery and migration status.
\end{itemize}

In conclusion, we are convinced that for the development of
next-generation database technology there is a need for a {\em
linguistic guideline}, and we see already a number of projects that are
heavily influenced by language design principles (e.g.
\cite{PiAn86,S*88,A*89b,Banc88}). On the other hand, next generation
database language design (e.g. see \cite{AtBu86,BaBu87,HSM89}) will be
driven and controlled by a ``systems vision'' with high but realistic
expectations of the potential of database technology.  
			

% --------------------------------------------------------------------------

\bibliographystyle{tex$inputs:florian}
\bibliography{tex$inputs:florian}

\end{document}
