% -----------------------------------------------------------------------------
% File: sofsem.tex
% Date: 24.8.1989
% Author: FM, JWS
% Note: NEEDS FILE sofsem1 (encapsulated postscript file) on Mac
% -----------------------------------------------------------------------------
\documentstyle{article}
\pagestyle{empty}  
\setlength{\topskip}{0truecm}
\setlength{\topsep}{0truecm}
\setlength{\topmargin}{0truecm}
\setlength{\headheight}{0truecm}
\setlength{\headsep}{0truecm}
\setlength{\oddsidemargin}{0truecm}
\setlength{\evensidemargin}{0truecm}
\setlength{\textwidth}{15.3cm}
\setlength{\textheight}{24cm} 
\setlength{\parindent}{0cm}
\setlength{\parskip}{0.5\baselineskip}      

\title{Advances in Database Programming: \\
       On Concepts, Languages and Methodologies
       \thanks{This research was supported in part by the European Commission
               under ESPRIT contract \# 3070 (FIDE)}}
\author{Joachim W. Schmidt \and Florian Matthes }
\date{ {\small                                                    
                  Fachbereich Informatik  \\
                  Universit\"at Hamburg \\
                  Schl\"uterstra{\ss}e 70 \\  
                  D-2000 Hamburg 13, FRG \\
                  e-mail: schmidt@rz.informatik.uni-hamburg.dbp.de
       }
     }
     
\begin{document} 

\maketitle

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

\begin{abstract}        
The development of data-intensive applications, such as information systems or
design applications in mechanical or software engineering, involves requirements
modeling, design specification, and, last but not least, the implementation and
maintenance of large database application programs. This paper concentrates on
the last issue and presents the state-of-the-art in {\em Database Programming}.

Over the years, computer science has isolated a number of requirements
essential for data modeling and has developed a variety of solutions to those
demands. Examples include the various concepts to identify, structure and
constrain data, as well as contributions to data visibility, lifetime,
abstraction etc. 

The paper first characterizes data-intensive applications by their specific
demands in data modeling and argues for  database programming languages and
environments based on highly integrated and consistent sets of data modeling
concepts. Next, a classification scheme for Database Programming Languages
(DBPLs) is introduced and applied to several DBPLs. The paper concludes with
initial results on database programming  methodologies and environments that
support the engineering of data-intensive applications. 
\end{abstract}                                 
                          
\begin{description}

\item[Key words:] 
    Data-intensive applications, database programming languages,
    constraints, persistence, binding, type systems,
    polymorphism, abstraction mechanisms, methodologies.
\end{description}

\thispagestyle{empty}

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

\section{Introduction and Overview}

As a first cut, data-intensive applications may be characterized by their needs
to specify and manipulate {\em heavily constrained} data that are {\em
long-lived} and may be {\em shared} by a user community. These requirements are
direct consequences of the fact that those data serve as (partial)
representations of some organizational unit or physical structure that exist in
their own 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, those representational data may become extremely voluminous -- in
current data-intensive applications up to $O(10^{9})$ or even higher. 

In strong contrast to the need for global management of large amounts of {\em
representational data}, our class of applications also has a strong demand to
process small amounts of local {\em computational data} that implement
individual states or state transitions. 

In essence, it is this broad spectrum of demands -- the difference in purpose,
size, lifetime, availability etc. of data -- and the need to cope with all
these demands within a single application that determines the daily life of a
database programmer. 

Another characteristic property of data-intensive applications is {\em
evolution}, i.e. the frequent need to accommodate changing target systems,
growing user communities, extended application functionality etc. Frequently,
such changes have to be done ``on the fly'', while minimizing the loss of data
and preserving the relationship between and identity of existing data. 

Section~\ref{Modeling} presents and discusses in detail the basic data
modeling concepts found in modern programming languages and database models.
Based on those findings, the abstraction principles required by data-intensive
applications are discussed and related in section~\ref{DAIA}. A classification
scheme for Database Programming Languages is presented in
section~\ref{Languages}, and selected DBPLs are discussed and compared. The
paper concludes by presenting in section~\ref{Method} first experiences with an
extended database programming methodology and an environment for the engineering
of high-quality data-intensive applications.     

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

\section{Data Modeling Concepts}\label{Modeling}
                             
The purpose of this section is to present and discuss a set of concepts
considered essential for high level data modeling. Many of these concepts,
such as data identification and data structuring, have to solve similar
problems in both applications, programming and database modeling, others
have to meet different requirements resulting from substantial variations,
e.g. in data lifetime or quantity.

It should be noted, however, that the designer of a particular DBPL has to
balance between different design goals, including expressive power, generality,
ease of notation, but also efficiency, implementability and understandability.
Therefore, each DBPL represents a judicious combination of the language concepts
enumerated in this section. Readers with particular interest in such language
design issues are referred to the survey paper by Atkinson and Buneman
\cite{AtBu86}, which presents several DBPLs in more detail.

Research and development in the area of DBPLs is based on 
results from -- until now -- separate research areas, such as

\begin{itemize}

\item Data Modeling (semantic data models, abstraction mechanisms, integrity 
      constraints);
\item Transaction Management (concurrency and synchronization models, protocols,
    implementations);
\item Query Evaluation (join algorithms, access path selection, cost modeling);
\item Memory Management (data placement and replacement, buffering, access
      structures); 
\item Data and Transaction Distribution (degrees of replication and 
      transparency, communication protocols);
\item Language Theory (type theory, semantics of programming languages);
\item Compiler Technology (compilation techniques, data management,
      garbage collection).

\end{itemize}                                                

The long-term goal of DBPL research is to establish an integrated technology
based on a sound understanding of that multi-dimensional language design space.
A first step in this direction is the definition of a common vocabulary as there
are already some terms (like ``sharing'', ``persistence'' or
``object-orientation'') that mean different things to different people
\cite{KhVa88}. Therefore, the following subsections will also discuss some of
the central notions used in the DB and PL literature. 


\subsection{Data Lifetime}\label{Lifetime}
                                                
The lifetime of data objects during program execution is well understood:
Static variables exist during the whole program execution, variables local to a
scope (e.g. block or procedure in C or Pascal) are
automatically allocated on scope entry and de-allocated on scope exit, and heap
variables have a lifetime controlled by the programmer. Scoping rules, variable
initialization and garbage collection allow programmers to concentrate on data
modeling issues, abstracting from low level memory management tasks
\cite{Sebe89} . 

However, when data are required to last longer than the duration of one program
execution, the treatment is much less uniform as it is performed ``outside''
the language, using operating system or database system services with their
own naming, scoping and binding mechanisms.

The notion of {\em persistence} means the ability of data values to exist for
an arbitrary length of time -- as long as necessary, as briefly as required
\cite{ABCCM83,AtSc89}. 
      
{\em Persistent Programming Languages} (PPL), like PS-Algol, Napier or Amber,
\cite{AtMo85,AtMo88} try to extend the scope of programming languages to tasks
usually accomplished by specialized tools in the programming environment 
(e.g. linking \cite{AtMo85a}). The rationale of these languages can be
summarized as follows \cite{AtSc89}:

\begin{description}                 
    
\item[Persistence Independence:] Operations on data should be specified in
    a way that is independent of the persistence of that data. Similarly, the
    persistence of a value should be independent of the operations applied to
    it. 

\item[Persistence Data Type Orthogonality:] The right to persist should
    be independent of the type of a data value. 

\item[Orthogonal Persistence Management:] Persistence
    should not limit the computational model, the control structures or the
    strength of the type system. 
\end{description} 

The models of persistence found in implementations of programming languages can
be roughly categorized as follows: 

\begin{description} 

\item[Workspaces:] They provide the simplest form of persistence found in many
    interactive systems (like APL \cite{Iver79} or LISP \cite{Teit75}). At the
    end of a session the whole workspace (containing programs and variables) is
    saved and can be loaded at the beginning of a new session. There is no way
    of sharing at a finer granularity than through the entire workspace. 

\item[Modules] (e.g. in DBPL and Adaplex, or external
    databases in Pascal/R): They generalize the notion of databases in DBMS by
    providing a local name space for constant, type and variable declarations.
    All variables declared (statically) within such a database module are
			 persistent and can be accessed by several applications simultaneously.
		  Programs can import and manipulate persistent variables like all other
			 program variables. 

\item[Side-by-Side Address Spaces:] In this model there is an ephemeral
    (main memory) and a persistent (disk) storage space. A value in main memory
    can be made persistent by an {\em extern} operation which writes it to
    persistent memory. Such a value can be recovered by a symmetrical {\em
    intern} operation. These operations preserve the structure of data,
    including sharing of subobjects and circularities \cite{CaMcQu88}. There
    are subtle differences between various implementations of this model
    \cite{BJW88,Card86,Harp85,AgGh89}: 

    \begin{itemize} 

      \item Is the identity of an object between pairs of {\em intern} and {\em
	     extern} operations preserved? 
                                                   
      \item Which objects can be made persistent (values, types, procedures)? 

      \item What is the type of an object returned by an {\em intern}
		    operation? What happens with values of abstract data types? 

      \item Is there a possibility for concurrent access? 

    \end{itemize} 

\item[Single Address Space:] In PS-Algol, Napier and OPAL there is a single
    global {\em persistent heap} \cite{ACC81a,DCBM89,MaSt87}. All
    objects (including procedures) accessible transitively from a global root
    pointer are persistent. This model combines the advantages of modules (no
    explicit operations for data movement) and side-by-side address spaces
    (dynamic creation of persistent objects of any type). 

    Implementations of persistent programming languages demonstrate that it is
    feasible to have efficient and shared access to such a homogeneous address
    space. 

\end{description}    

For a type-safe handling of persistent data, it is necessary to have
persistent meta-data (type, i.e. schema information). The size and longevity
of these data can limit the efficiency of traditional type matching
algorithms and complicate the modification of existing software systems
using persistent data \cite{Zdon87}.

As a partial solution to the problem, PPL provide {\em incremental binding}
mechanisms \cite{MAD87}. Traditionally, a binding consists of a name-value
pair \cite{Stra67} that can be augmented by a type and an indication whether the
value is constant or mutable. The binding can take place at compile time (static
binding) or during program execution (dynamic binding). 
                             
\label{Binding} One particular mechanism of dynamic binding is the use of {\em
environments} \cite{Dea89}: They are collections of bindings that can be
extended or modified dynamically. Within the scope of an environment type
checking is entirely static. Only on entry into the scope is a single dynamic type
check necessary to verify that the environment contains type
compatible bindings for all identifiers used within the scope. Using
environments, it is possible to perform ``local'' changes to data types and
procedures on ``live'' information systems without the need to recompile the 
whole system in order to guarantee its type consistency 
\cite{AtBu86,DCBM89}. 


\subsection{Data Typing}

Type systems are one of the most important issues in DBPL design. 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).

    But also in DBPLs, 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}. 
                                
    Modern DBPLs make heavy use of type information to increase programmer
    efficiency and productivity in the construction of large information
    systems. 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 like 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 the ability to {\em name} types
    (e.g. Age, Dollar, Sex) and re-use type descriptions. Furthermore it is
    desirable that the notation of a type system is able to express more or
    less directly the well-known abstraction mechanisms of semantic data models
    \cite{SmSm77,PeMa88} like \begin{itemize} \item classification (classes,
    sets),
    \item aggregation (objects, entities, records), \item generalization
    (superclasses or appropriate subtyping rules), and \item association
    (nested sets, multi-valued functions). \end{itemize} 
                       
\item Powerful type systems support type {\em abstraction} to hide
    irrelevant program information or to protect ``private'' information from
    external access.
    
    Abstraction supports the ordered evolution of large information systems
    \cite{Card89,DAIDA4}. It should be noted, however, that the problem
    of encapsulation and abstraction conflicts with some basic assumptions
    of existing database query languages, which view a database as a single
    ``flat'' name space \cite{BCD89}. 

\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. 
    
    The basic mechanisms to attain genericity are explained in 
    Section~\ref{Poly}.

\end{itemize}        
    
There are many detailed criteria for a comparison of type systems for DBPLs
\cite{A*89}. The following sections address only the most important language
features and discuss their impact on database programming. 


\subsection{On Data Consistency}\label{TypeCheck}

The moment when consistency constraints on data are checked can vary over a
wide time interval. The earliest possible point in time depends, of course, on
the kind of constraint, but also on the technology applied for constraint
maintenance.
                                        
Database management systems perform checks at the latest possible point in time:
at {\em execution time} of an operation or even later, at transaction commit
time, when data become visible to other users. CASE Systems choose the earliest
possible point in time: consistency is already enforeced at {\em application
design time}. Language (i.e. type-) sensitive editors perform incremental
semantic checks at {\em programming time}.  Traditional language processors
verify type constraints at {\em compilation time}.

In a {\em strongly} typed programming language all computations
are checked for type errors. As pointed out in \cite{BBo89} this definition
depends on the notion of ``type compatibility'' supported by a particular
language\footnote{For example, computations like $3 + (7<8)$ are valid in
languages that do not discriminate numbers and boolean values.}. 

A language is {\em dynamically} type checked if the types of the arguments are
checked as the operators are applied. In {\em static} type checking, type
consistency can be {\em completely} determined before program execution. In
``traditional'' programming languages, static type checking takes place during
compilation (eventually supported by the use of version keys during linkage). 

In the presence of dynamic binding (see Section~\ref{Binding}) things are more
complicated as there is a need for some form of delayed type checking.
However, the flexibility and adaptability of dynamic typing is counter-balanced
by the possibility of run-time type errors during application execution and the
need for a time-consuming type checking code \cite{Matt87}.

The policy of modern languages can be described as {\em eager type checking}
\cite{AtBu86}: The language supports as much static type checking as possible
and there are special type constructors (e.g. {\tt dynamic} \cite{Card86}
\cite{Card86b}, {\tt env} \cite{Dea89} \cite{DCBM89} \cite{AtMo88}, {\tt ANY}
\cite{RLW85} \cite{Card88}, {\tt Auto} \cite{Card89}) that enable the
programmer to specify the boundary between the realms of static and dynamic
type checking.                                    
                                                  
There must be a mechanical way to verify that a program respects all its type
constraints. Furthermore this process has to be transparent \cite{Card89}: If a
typecheck fails, the reason should be apparent\footnote{This situation should be
contrasted with problems that arise in the area of general program
verification.}. 

There should be both a consistent theory supporting the type system (e.g.
a typed $\lambda$-calculus \cite{Reyn74} or a theory of constructions
\cite{CoHu85}) and an efficient type check algorithm (e.g. \cite{Miln78}). 
            
The above discussion concentrates on the verification of the very limited set
of {\em type constraints}. Loosely speaking, these constraints require that at
any time during program execution the value of a variable is an element of a
set that is defined without any reference to other variables (e.g.
age $\in$ INT).  

To be able to enforce {\em general constraints} (invariants of a particular
database application), some database programming languages provide additional
language support: 

\begin{itemize}

\item Application dependent constraints are commonly specified as first
    order {\em predicates} ranging over set variables (e.g. $\forall$ e $\in$
    EMPLOYEES: salary(manager(e)) $>$ salary(e)). In some languages it is
    possible to attach such a constraint to a particular type declaration
    (e.g. in Galileo \cite{ACO85} and TAXIS \cite{MyWo80}), whereas other languages
    allow the declaration of database wide constraints (e.g. ADABTPL
    \cite{SSB86}). 

\item Most transformations of one consistent database state into another
    have to be performed in current languages by a sequence of operations.
    Therefore, it is sometimes necessary to have intermediate states that
    violate the global integrity constraints. {\em Transactions} allow the
    programmer to group such sequences into a single {\em atomar} operation
    with respect to integrity control. Transactions as language constructs can be
    found for example in the languages DBPL, TAXIS and Adaplex. 
    
\item It should be possible for application programs to ``catch'' violations
    of integrity constraints in order to resume execution in an ordered
    manner. Several DBPLs therefore support {\em exceptions} that propagate
    along the dynamic call chain of nested procedure calls, in search of
    an appropriate exception handler (e.g. Amber, Adaplex, Galileo).
\end{itemize}

A more general solution to the problem of integrity violations can be found in
TAXIS \cite{CRBM88}.  The long-term behavior of processes is modeled in
TAXIS by means of {\em scripts} that offer a Petri-net like graphical
formalism. Transitions in scripts (i.e. transactions) can be {\em triggered}
by various conditions: Intra-class predicates, temporal conditions (e.g.
\$now after 7) but also by the violation of a precondition, a postcondition,
or of an attribute constraint.                

Such a ``data-driven'' programming style is advocated by the designers of
``active database systems'' as a new paradigm for constructing
time-constrained database applications \cite{McCD89}. 

There are several DBPLs that allow the restriction of the operations on data by the
definition of {\em access constraints}: In Napier it is possible to define
elements of arrays and fields of records as constants that must not be altered
after their initialization. The same functionality is provided in TAXIS
\cite{MyWo80} by the attribute category {\em unchanging}. The language DBPL
allows the association of access rights (a subset of the set \{insert, delete,
update, read, assign\}) with views on relation variables. These access rights
are verified at compile time \cite{DAIDA4}. 

\subsection{Data Identification}\label{Ide}

A main task in data modeling is the representation of objects and of
relationships between them \cite{Brod84}. Ullman \cite{Ullm87} distinguishes
between {\em value-based} and {\em object-based} models. 

In a value-based model (e.g. the relational data model), objects (tuples) are
identified using associative identifiers (key values). This way objects and
relationships can be represented uniformly. Many (procedural, functional and
logic) DBPLs use sets as bulk data types and support  (restricted subsets) of
first-order logic for data selection, identification and data transformation
(e.g. Pascal/R, DBPL, Modulex, Plain, Aldat, Adaptbl, LDL, FQL and LIFE).

Semantic data models and object-oriented languages emphasize the importance of
{\em object identity}, i.e. ``the ability to distinguish objects from one
another regardless of their content, location, or addressability''
\cite{KhCo86}.                                 

The object-oriented language OPAL \cite{CoMa84} and the initial design of FAD
\cite{DaVa88} postulated that {\em every} database object (even every string)
has a globally unique identity that makes it distinguishable from all other
objects at all times. 

This should be seen in contrast to many entity-based languages (like Adaplex,
Galileo, TAXIS) and modern object-oriented systems (like O$_2$ \cite{LRV88} or
OODAPLEX \cite{Daya89}) that distinguish between entities (resp. objects) and
values (without identity). The rationale of this distinction is to provide a
``natural'' interpretation of equality, ``$=$'', a predicate that is involved
in virtually every database operation (selection, duplicate elimination,
join) \cite{AbKa89}: For objects it designates a test on ``identity''
(e.g. person1 = person2) whereas for values it designates ``equality''
(e.g. person1.name = `Smith') \cite{SAM89}. A similar solution can be found
in DBPLs that support references (called mutable objects in functional
programming languages): equality of references means ``identity'' of objects
(e.g. see \cite{OBBT89}). 

Systems that support object identity also offer two very different
rules for the lifetime of an object. The predominant solution is the {\em
reachability} rule: An object implicitly ceases to exist as soon as there are
no other objects that reference it. Thus it is only possible to destroy
references to an object (e.g. by overwriting with a new value), but there
is no way to delete the object itself. This policy avoids dangling
references and guarantees {\em referential integrity}. Other language models
allow the explicit {\em destruction} of objects, thereby invalidating
implicitly all references to it (e.g. the language E \cite{RiCa87} in the
EXODUS project \cite{CDeW88}). 


\subsection{Data Structuring}\label{TypeConstr}

Traditionally, database systems only supported a limited and fixed set of
built-in types (integer, string, real, eventually date, time, currency etc.)
and two powerful type constructors, namely some sort of records and sets (i.e.
relations or owner-member or father-children relationships in the network and
the hierarchical data model) \cite{Date81}. The spectrum of data structures was
determined by the needs of the database applications, and the kinds of entities
and relationships found in {\em commercial applications} had a big impact on
early data models. 

Programming languages, on the other hand, provide a variety of type
constructors (e.g. array, record, reference) over a set of base types. In
general purpose programming languages the device of data structures was
influenced by the general notion of {\em algorithmic completeness}, but limited
by the requirements of implementation efficiency. Therefore, most languages do
not have built-in (generic) bulk data structures (e.g. relations, multisets,
tables, index structures) to support dynamic data structures with a
time-varying extent. However, modern languages enable the programmer to define
new base types and type constructors using polymorphism and data abstraction
(see Section~\ref{Poly} and~\ref{Abst}). 
                            
Many database programming languages incorporate a data model in their type
system. The first DBPLs adopted the relational data model and included a type
constructor {\tt RELATION} \cite{Schm77} into a procedural programming
language. Other languages are based on the functional data model \cite{Ship81}
or on object-oriented data models \cite{Alba83,ACO85,MyWo80,BMW84}. 
                                  
Viewing data models as (specialized) type systems allows one to measure  the
initial definition of the relational data model \cite{Codd70} against design
principles for ``good'' type systems in programming languages. It also
demonstrates how recent DBMS extend these definitions to overcome limitations
of the traditional data model: 
 
\begin{description} 

\item[Type Completeness:] In the relational model records must be
    ``flat'', i.e. their fields must contain values from the basic domains and
    relations have to contain records as elements. This should be seen in
    contrast to a {\em type-complete} data model where each type constructor
    can be applied to any base type or composite type. The regularity
    gained by the principle of type completeness not only enhances the
    modeling power of a type system \cite{AtBu86}, but also simplifies the
    understanding of the universe of discourse spanned by the typing system
    \cite{AtMo85}. 

    Several research prototypes of DBMS try to overcome limitations of the
    relational approach by including nested relations to support a wider range
    of applications, such as CAD/CAM and office information systems
    \cite{BaKi85,HaRe83a,JaSc82,ScPi82}. 

    Another example of a violation of the type completeness principle in
    a programming language is the data type {\em file} found in Pascal
    \cite{Wirt71}: it is not
    allowed to declare files of files or to store pointers on external
    files  to make dynamic data structures persistent.    

\item[User-Defined Data Types:] In order to support so-called
    ``non-standard applications'', DBMS researchers recognized the
    need for non-standard, i.e. user-defined base types (e.g. points, line
    segments) and type constructors (e.g. arrays, sequences, multisets). 

    An attractive approach is the inclusion of {\em abstract
    data types} (ADTs) into relational DBMS, viewing ADTs as a mechanism to
    define {\em new base types} (domains) \cite{RoSt87,DeWi88,BaBu84}. 

    However, the use of ADTs to define {\em new composite types} (e.g. lists
    or queues) finds much less attention in the research community. A notable
    exception is the ATLANT language \cite{Zamu88}
    that utilizes generic data types to construct user-defined data models. A
    major problem with the ADT approach is query optimization, which needs
    knowledge about the {\em
    semantics} of the operations defined for an ADT \cite{HFLP89} (e.g.
    selectivity of filters, commutativity of binary operators) \cite{MaDa86}. 
  
    There is also some work on new bulk type constructors
    for database systems and database languages (e.g. lists, multisets
    \cite{PiAn86}, indexable lists \cite{LRV88,LeRi89}). 

\item[Function Types:] An interesting feature of modern languages (like
    ADA, Modula-2, ML, Prolog) is the ability to define higher-order functions,
    i.e. functions that take or return other functions. A comparable feature
    can be found in POSTGRES \cite{RoSt87} that allows field values containing
    POSTQUEL procedures. These stored queries can be executed during the
    evaluation of other queries simulating {\em is-a} hierarchies, {\em
    part-of} hierarchies or non-1NF relations \cite{DeWi88}. 

\end{description}                                                          


\subsection{On Data Compatibility}\label{Poly}

Essentially, traditional programming languages (such as Pascal or C) take a
``black-or-white'' view in the sense that data are either of the same type
and fully compatible or they are of a different type and, therefore, not
compatible at all.

In contrast to those ``mathematical'' types are the ``taxonomical'' type systems
\cite{Card84} that take a more realistic view of data by emphasizing the
commonalities between types rather than their differences.

{\em Polymorphic languages} are based on taxonomical type systems and allow a
variable or a value to have more than one type. Generally speaking, this
ability is important to {\em avoid overspecifications} of data structures or
operations. Overly restrictive type constraints result from the need of
{\em monomorphic languages} (like Pascal or C) to associate a single type
with each variable, parameter and value.

On the other hand, with growing application systems there is the experience
that for some operations data need to be discriminated by their type (e.g.
data of type boolean have to be ruled out for integer multiplication), while
for others a whole range of data is acceptable (e.g. push and pop operations
on stacks). A more tolerant policy makes it possible to specify, for example,
stacks that work for arbitrary element types or to implement an operation
{\tt celebrate birthday} that increments the age of a person, an employee or
a student. 

Following the established classification presented in \cite{CaWe85}, one can
distinguish the following kinds of polymorphism: 
        
\begin{description}

\item[Ad-hoc Polymorphism] is found in many languages (e.g. Ada or Pascal)
    and can be further classified into: 
    
    \begin{description}
    
    \item[Overloading:] A variable or function name (e.g. {\tt Add}) is used to
        denote different objects or operations. The context of the application
        of that name determines the actual object or operation to be used
        (e.g. {\tt Add} to a stack or to a queue).
    
    \item[Coercion] is a semantic operation that converts an argument to
        the type expected by a function. For example {\tt sin(1)} is converted
        (by the compiler) into {\tt sin(float(1))} because {\tt sin} expects
        a floating point number as its argument.     
    
    \end{description}
    
    These mechanisms can be understood as pure ``syntactic sugar'' as they
    do not add any expressive power to a monomorphic type system.
    
\item[Universal Polymorphism:] On the implementation level a universally
    polymorphic function can be characterized by its ability to execute the
    {\em same} code for arguments of any admissable type. Universal
    polymorphism is often considered {\em true} polymorphism, whereas
    ad-hoc polymorphism is some kind of {\em apparent} polymorphism
    \cite{CaWe85}. There are two forms of universal polymorphism:    
    
    \begin{description}
        
    \item[Parametric Polymorphism:] A polymorphic function (sometimes
        called {\em generic} function) has an explicit or implicit type
        parameter which determines the type of argument for each
        application of that function. A typical example is a function {\tt
        reverse} that reverses lists with arbitrary element types. 

        In some languages (e.g. Napier \cite{DCBM89}), the programmer has to
        supply a type parameter for each application of the function ({\tt
        reverse[int](ilist), reverse[real](rlist)}) and the compiler verifies
        that {\tt ilist} is a list of integers and {\tt rlist} is a list of
        reals. Other languages (e.g. ML \cite{HMT88}, Machiavelli
        \cite{OBBT89}) provide special {\em type inference} rules, i.e. the
        compiler infers the (implicit) type parameter from the types of the
        arguments. In the presence of type inference there is no need at
			     all to declare the (polymorphic) type of the argument of
        {\tt reverse}: the type checker is able to deduce the ``most general''
        polymorphic type of the function argument from the operations applied
        to the argument within the function body \cite{Miln78}. 
               
        Sometimes it is necessary to impose additional constraints on the type
        parameters of generic functions: a function to sort sequences with
        elements of type $\alpha$ only works for types $\alpha$ for which a
        comparison function is defined ({\em bounded parametric polymorphism}
        \cite{CaWe85}). 

        The main use of generic functions in data-intensive applications is the
        definition of user-defined type constructors (e.g. {\tt tree of
        $\alpha$}) with their associated operations (e.g. {\tt insert,
        delete}). Such polymorphic functions could also be used as vehicles
        to provide the user-defined semantics for an extensible DBMS	
			     ({\tt relation of $\alpha$, index from $\alpha$ to $\beta$}).

    \item[Inclusion Polymorphism:] The notion of inclusion polymorphism
        first appeared in Simula67 \cite{DaNy66} and can be found in several
        modern programming languages (e.g. Amber \cite{Card86}, Modula-3
        \cite{Card88}, Oberon \cite{Wirt87a}, Eiffel \cite{Meyer88}, Quest
        \cite{Card89}). There is a {\em subtype} relation between types,
        similar to the relation of containment between sets. If $A$ is a
        subtype of $B$, then any object of $A$ is also an object of $B$. 
    
        The most common subtype relationship is between record types: A record
        type $A$ (e.g. Student) that has at least all fields of a record
        type $B$ (e.g. Person) is a subtype of $B$. In Machiavelli
        \cite{OBBT89} there is also a``lifted'' version of this subtyping
        rule, stating that a set of (relation of) $A$ is a subtype of a set
        of $B$ iff $A$ is a subtype of $B$.                                
                                                               
        The subsequent section will illustrate the use of inclusion
        polymorphism to directly represent generalization (specialization)
	       hierarchies within the type system of a DBPL. 

        \end{description} 
        
        It should be noted that it is possible to simulate (bounded and unbounded)
        parametric polymorphism using inclusion polymorphism, but not vice
        versa, i.e. inclusion polymorphism is more expressive than parametric
        polymorphism \cite{Meyer86}. However, many languages retain both
        forms of polymorphism supporting a more succinct notation
        (e.g. Eiffel \cite{Meyer88}, Trellis/Owl \cite{S*86}).

\end{description} 

In \cite{Card88b}, Cardelli proposes a three level structure as a framework
for languages with {\em type operators} for (type-safe)
operations on type structures. Intuitively, level 0 consists of the set of
all possible values, level 1 contains types (as sets of values) and type
operators (mapping types to other types), and level 2 is the level of {\em
kinds}, which are ``types'' of types and type-operators. As demonstrated
in Quest \cite{Card89}, such a sophisticated type system can help in
adding power and regularity to data-oriented languages. 

% ------------------------------------------------------------------------
                                                      
\section{Abstraction Mechanisms for Data-Intensive Applications}
\label{Abst}\label{DAIA}

Advances in computerized applications are closely correlated with a better
understanding and increased utilization of appropriate {\em abstraction
principles}. Abstraction aims at decomposing large problems into smaller
tractable ones and at concentrating on selected issues of current interest
while postponing others considered as irrelevant representational,
computational or operational details. Thus, abstraction allows one to identify and
delegate subproblems that can be solved independently and can be combined at a
higher level to a solution of the original problem. 

Following our previous discussion, data-intensive applications require
the joint application and close cooperation of abstraction principles
from at least two areas:
\begin{itemize}

\item representation abstraction as provided by data models;

\item computation abstraction as supported by programming languages.

\end{itemize}

Furthermore, data-intensive applications have a strong demand for certain
operational services such as concurrency or distribution management and
recovery from failure which, in a traditional setting, are provided
through various operating system services.

This abstraction space for data-intensive applications (Fig. \ref{Fig1})
will be presented and discussed in the following subsections.

\begin{figure}      
\begin{center}
\mbox{\special{illustration sofsem1}	
\hspace*{7truecm}
\rule{0cm}{7truecm}}
\end{center}
\caption{Abstraction Space for Data-Intensive Applications}
\label{Fig1}
\end{figure}

\subsection{Abstraction in Data Modeling}

The abstraction mechanisms in up-to-date data models are
\cite{SmSm77} 

\begin{description}

\item[Classification] is a form of abstraction in which a collection of
    objects is considered as a single higher level object, frequently called
    {\em class}. Classification is used in conceptual modeling \cite{BMS84} to
    identify, classify, and describe objects in terms of object classes. 

    In many DBPLs, classification is represented by two separate
			 mechanisms:
    A {\em type} specifies the (time-invariant) common structural properties
    of objects of a given object class, and a {\em variable} (e.g. of a
    set type) serves as a ``container'' for the (time-varying) extent
    of that class. The {\em class} concept of object-oriented languages
    subsumes both mechanisms.

\item[Aggregation] is a form of abstraction in which a relationship
    between component objects is considered as a higher level aggregate
    object.

    This {\em part-of} relationship is represented in DBPLs either explicitly
    by means of record constructors or implicitly in a class definition. 

\item[Generalization] is a form of abstraction in which a relationship
    between class objects is considered as a higher level generic object. The
    abstraction of the three class objects {\tt student}, {\tt programmer} and
    {\tt lecturer} to the single generalized object {\tt person} may serve as
    an example. 
    
    In semantic data models and object-oriented DBPLs this {\em is-a}
    relationship is captured  by inheritance hierarchies. Subclasses inherit
    all attributes of their superclass(es) but they can also add new attributes
    (e.g. Galileo, Adaplex). TAXIS has separate inheritance hierarchies for
    data, transaction and exception classes \cite{MyBeWo80,CRBM88}.
    OPAL has a single inheritance hierarchy, as all operations on data objects
    have to be attached as {\em methods} to their class definition. Thereby it
    is possible for subclasses to selectively {\em override} method
    specifications inherited from their superclass. 
    
    OPAL and the implementation of Galileo only support {\em single
    inheritance}, i.e. a category object can only be generalized to a single
    generic object. Amber is an example of a language that has {\em multiple
    inheritance}. Another unique feature of Amber is the
    fact that the {\em is-a} relationship between two object types is inferred
    by the compiler and needs not to be declared explicitly \cite{Card84}.
    
    From the previous discussions it should be clear that the notion of
    inheritance is close to the (more abstract and technical) definition of
    inclusion polymorphism (see Section~\ref{Poly}).

\end{description} 

Following \cite{Dijk76} and  \cite{BrRi84} these {\em data abstractions} can
guide the top-down design of database transactions by mapping operations on
higher-level objects into composite operations (sequencing, case analysis,
iteration) on lower-level objects. 
 
\subsection{Abstraction in Computation Modeling}

The notion of {\em abstraction} has a somewhat different flavor in
computation abstraction as supported by modern programming languages.
Here abstraction emphasizes the advantages of {\em information hiding},
encapsulation, and protection. Liskov and Guttag \cite{LiGu86} distinguish
three kinds of abstractions: 

\begin{description}

\item[Procedural Abstraction] has two aspects: {\em Abstraction by 
    parameterization} allows one to represent a potentially infinite set of
    different computations with a single program text that is an abstraction
    of all of them. {\em Abstraction by specification} allows one to abstract
    from the details of a computation given by the body of a procedure.
    This is accomplished by associating with each procedure a specification,
    usually in form of first-order predicates for {\em pre- and
    postconditions}, or input/output relationship \cite{Hoar69,Dijk76,Hehn84}.

    The notion ``procedural'' abstraction is somewhat misleading as
    parameterization and specification are fundamental concepts of functional
    and logic-based languages too.                                 
    
\item[Data Abstraction] is achieved by bundling a set of objects and a
    set of operations that characterize the behavior of these objects.
    The objects can only be created, modified or inspected using a given
    set of operations (constructors, mutators and observers). 
    {\em Abstract data types} hide irrelevant information of the 
    type representation and protect internal invariants from external
    access.
                                           
\item[Iteration Abstraction] abstracts from details of loops iterating over
    elements of composite objects (e.g. iteration order, or effects of updates
    during iteration). For example, CLU \cite{L*81} and Trellis \cite{S*86}
    provide built-in language constructs to support user-defined iterators
    (e.g. over sets, lists, trees). 

    Many DBPLs (e.g. Pascal/R, DBPL, Adaplex, OPAL) not only have specialized
    loop statements that apply to variables of their built-in bulk data types,
    but also support quantified expressions for set selection and set
    construction. Other approaches to iteration abstraction can be found in
    Aldat \cite{Merr77} or Machiavelli \cite{OBBT89} both of which generalize the
    operators of the relational algebra (selection, projection, join). 

    A main advantage of built-in iterators, set-valued expressions or
    set-oriented operators is the
    ability to specify intentionally the set of objects that are to be
    processed and to delegate the task of choosing an ``optimal'' execution
    strategy to the compiler or the run-time system. Based on the knowledge of
    existing access paths, they can speed up the execution of bulk data
    operations considerably.
    
    This ``declarative'' style of programming is further emphasized in 
    logic-based languages (e.g. LDL \cite{NaTs89}, FAD \cite{BBKV87}). In
    these languages, the programmer utilizes (mutually recursive) rules to
    select and construct sets
    of objects. The semantics (e.g. fixed point semantics) of these languages
    allow one to abstract from iteration sequences as well as from termination
    conditions that arise in recursive query processing.
    
    To integrate procedural elements like updates or sequencing of operations
    into such a declarative formalism, LDL uses the notion of {\em
    stratification} \cite{Naqv89}. DBPL, a procedural database
    programming language, takes an inverse approach: fixed point semantics are
    only assigned to a distinguished set of ``functional'' query expressions
    (called constructors) that can be procedurally abstracted (i.e. named
    and parameterized \cite{JLS85}.

\end{description}

To give a first summary, abstraction in data modeling provides
support for describing the {\em statics} of an application (i.e. its
structures and invariants), whereas the abstraction mechanisms found in
programming languages are designed to help in defining the
{\em dynamics} of a system (i.e. its short- and long-term behavior).
   
Modern design methodologies and languages emphasize the importance of an
integrated view on the statics and dynamics in system design and
implementation. They utilize the various forms of data abstractions (e.g.
ADTs, classes) to encapsulate state, behavior and invariants, and (re-)use such
capsules as adaptable building blocks for large information systems
\cite{Meyer88}. 

\subsection{Operational Support for DBPL Applications}

Up to now only a few DBPLs provide the operational support considered necessary
for realistic data-intensive applications. The key concept by which operation
abstraction is achieved is that of a {\em transaction} \cite{Gray81,Gray78}

In the DBPL system \cite{Reim81,MRS84} transactions are first-class language
constructs that provide, in addition to procedural abstraction, concurrency and
recovery abstraction based on serializability and ``undo/redo'' semantics
\cite{BHG87}.                                          

Again, the relational approach provides an excellent framework for integrating that
kind of operational support into a DBPL. By representing data classes through
(disjoint) sets and abstraction computations through (first-order) predicates the
notion of disjointness and sharing, locking and validation can be transformed into
a logic framework that provides sound and ``efficient'' solutions
\cite{KuRo81,BJS86}.

Additional work has been done in high level support for data-intensive applications
in distributed environments. References can be found in
\cite{Lisk84,JGLR88,L*87}.
                                                      
% ------------------------------------------------------------------------

\section{Integrated Database Programming Languages}\label{Languages}

\begin{figure}      
\begin{center} \footnotesize
\begin{tabular}{l|llll}              
\hline
                  & Pascal/R           & DBPL               & Aldat              & LDL                \\
\hline                                 
\\
References        & \cite{Schm77,Schm80} & \cite{SEM88,MaSc89} & \cite{Merr77,Merr84} & \cite{NaTs89,TsZa86} \\
\\
Model of          & database $=$ record & Modules, orth.     & workspace          & workspace (?)      \\
Persistence       & of relations       & persistence        &                    &                    \\
\\
Binding           & static \& dynamic  & static             & ?                  & static             \\
\\
Typing            & static             & static             & ?                  & static             \\
\\
Identification    & value based        & value based        & value based        & value based        \\
\\
Bulk Data         & relations          & sets               & relations          & sets               \\
Structures        & not type-complete  & type-complete      & not type-complete  & type-complete      \\
\\
Bulk Data         & iterators, quant-  & (recursive) quant- & relational algebra,& (recursive)        \\         
Manipulation      & ified expressions  & ified expressions, & recursive func-    & rules              \\
                  &                    & iterators          & tion equations     &                    \\
\\
Recovery          & no                 & Transactions       & no                 & no                 \\
\\
Concurrency       & no                 & Transactions       & ?                  & no                 \\
\\
Data Abstraction  & no                 & ADTs, modules      & no                 & modules            \\
\\
Polymorphism      & no                 & no                 & no                 & no                 \\
\\
Exceptions        & no                 & no                 & no                 & no                 \\
\\
Algor. Kernel     & Pascal            & Modula-2            & ---                & ---                \\
\hline
\end{tabular}
\end{center}                                                                         
\caption{Relational DBPLs}
\end{figure}

\begin{figure}      
\begin{center} \footnotesize
\begin{tabular}{l|lll}
\hline
                  & PS-Algol          & Napier88          & Amber                 \\
\hline                              
\\
References        & \cite{ACC81a,ABCCM83,PPRG87} & \cite{DCBM89,AtMo85,AtMo88} & \cite{Card86,Card86b} \\
\\
Model of          & single address    & single address    & side-by-side address  \\
Persistence       & space             & space             & spaces (orthogonal)   \\
\\
Binding           & static \& dynamic & static \& dynamic & static \& dynamic     \\
\\
Typing            & static \& dynamic & static \& dynamic & static \& dynamic     \\
\\
Identification    & references        & references        & references            \\
\\
Bulk Data         & ---               & ---               & ---                   \\
Structures        &                   &                   &                       \\
\\
Bulk Data         & ---               & ---               & ---                   \\
Manipulation      &                   &                   &                       \\
\\
Recovery          & no                & no                & no                    \\
\\
Concurrency       & limited           & no                & no                    \\
\\
Data Abstraction  & no                & ADTs              & modules, ADTs         \\
\\
Polymorphism      & no                & parametric polym. & multiple inher.       \\
\\
Exceptions        & no                & no                & yes                   \\
\\
Algor. Kernel     & S-Algol           & ---               & ---                   \\ \hline
\end{tabular}
\end{center}
\caption{Persistent programming languages}
\end{figure}

\begin{figure}      
\begin{center} \footnotesize
\begin{tabular}{l|llll}
\hline
                  & OPAL                 & O$_2$             & O++               & E                   \\
\hline                                 
\\
References        & \cite{CoMa84,MaSt87} & \cite{LRV88,LeRi89} & \cite{AgGh89,AgGh89b} & \cite{RiCa87,CDeW88} \\
                  & \cite{MSOP86}        & \cite{BCD89}      &                   &                     \\
\\
Model of          & single address       & single address    & side by side      & side by side        \\
Persistence       & space                & space             & address spaces    & address spaces      \\
\\
Binding           & dynamic              & static \& dynamic & static            & static              \\
\\
Typing            & dynamic              & static \& dynamic & static \& dynamic & static \& dynamic   \\
\\
Identification    & object based         & object based      & pointers          & pointers            \\
\\
Bulk Data         & sets (and user-      & sets, lists       & clusters          & files, insert-      \\
Structures        & defined collections) &                   & not type-complete & able arrays         \\
\\
Bulk Data         & iterators, optimized & iterators,        & iterators, fixed- & iterators           \\
Manipulation      & set-oriented         & ``embedded query  & point semantics   &                     \\
                  & operators            & language''        & for recursion     &                     \\
\\
Recovery          & yes (shadows)        & ?                 & no                & yes                 \\
\\
Concurrency       & yes (Transactions)   & ?                 & ?                 & yes (Transactions)  \\
\\
Data Abstraction  & yes (methods)        & yes (methods)     & yes (methods)     & yes (methods)       \\
\\
Polymorphism      & single inher.        & multiple inher.   & single inher.     & single inher.       \\
\\
Exceptions        & yes                  & no                & no                & no                  \\
\\
Algor. Kernel     & Smalltalk            & (C/Basic)         & C++               & C++                 \\
\hline
\end{tabular}
\end{center}
\caption{Object-oriented DBPLs}
\end{figure}              

\begin{figure}      
\begin{center} \footnotesize
\begin{tabular}{l|llll}
\hline                     
                  & Adaplex              & Galileo           & TAXIS             & Machiavelli         \\
\hline               
\\                  
References        & \cite{SFL83}         & \cite{ACO85,AGOO88} & \cite{MyWo80,BMW84} & \cite{OBBT89,Ohor88} \\
                  &                      & \cite{AGO89}      &  \cite{CRBM88,MyBeWo80} &                     \\
\\
Model of          & modules, persistence & modules (work-    & no transient      & modules (?)         \\
Persistence       & only for entities    & space implem.)    & data              &                     \\
\\
Binding           & static               & static            & static            & static              \\
\\
Typing            & static               & static            & static (?)        & static              \\
\\
Identification    & object based         & object based      & object based      & value \& object b.  \\
\\
Bulk Data         & entity sets          & classes,          & class extents     & sets                \\
Structures        & not type-complete    & sequences         &                   & type-complete       \\
\\
Bulk Data         & iterators, quant-    & iterators, quant- & class iterators   & generalized rel-    \\
Manipulation      & ified predicates     & ified predicates  &                   & ational algebra     \\

\\
Recovery          & yes                  & ?                 & no                & no                  \\
\\
Concurrency       & yes (Transactions)   & ?                 & yes (Transactions)& no                  \\
\\
Data Abstraction  & ADTs                 & (semi) ADTs       & no                & ADTs                \\
\\
Polymorphism      & generic modules,     & single inher.     & multiple inher.   & parametric polym.,  \\
                  & single inher.        &                   &                   & multiple inher.     \\
\\
Exceptions        & yes                  & yes               & yes               & yes                 \\
\\
Algor. Kernel     & Ada                  & (early ML)        & ---               & Standard ML         \\
\hline
\end{tabular}
\end{center}
\label{AdvancedTypes}
\caption{DBPLs with advanced type systems}
\end{figure}

In the following figures, DBPLs are grouped into four broad categories: 
Relational DBPLs support bulk data definition and manipulation using set
(relation) types and quantified predicates (query expressions). Persistent
programming languages provide persistence for all of their data values and
include language mechanisms for static as well as dynamic binding and type
checking.  Object oriented DBPLs emphasize the notion of object identity
using classes to organize objects and operations on them. The remaining DBPLs in
Fig.~\ref{AdvancedTypes} are all excelled by their elaborate type systems
supporting a direct representation of the data modeling concepts outlined in
Section~\ref{Abst}. 

Figures 2 through 5 characterize the conceptual foundations of several DBPLs.
Syntactic or implementation details of particular languages are
de-emphasized in this section. The following criteria are applied:
\begin{description}

\item[Model of Persistence:] How is data lifetime modeled within the language
    (see Section~\ref{Lifetime})?

\item[Binding:] When are names bound to constants, variables,
    procedures or types (see Section~\ref{Binding})?

\item[Typing:] When do type checks take place (see 
    Section~\ref{TypeCheck})? 

\item[Identification:] How are objects identified (see Section~\ref{Ide})?

\item[Bulk Data Types:] Which built-in type constructors are used to define large
    collections of (persistent) objects? How do these type constructors
    interact with other types (type-completeness, see Section~\ref{TypeConstr})?
                     
\item[Bulk Data Manipulation:] Does the language support abstraction from
    iteration (see Section~\ref{Abst})? Are there predefined iterators for
    the built-in bulk data types?

\item[Exceptions:] Can exception handling be expressed within the language?

\item[Recovery:] Is there a notion of {\em atomic} transactions involving
    failure recovery?

\item[Concurrency:] Is it possible for several applications to access shared 
    data simultaneously? 
    
\item[Data Abstraction:] What are the mechanisms of information hiding
    (see Section~\ref{Abst})?
    
\item[Polymorphism:] Is it possible to write generic code that is
    statically type checked? Does the type system include subtyping rules
    (see Section~\ref{Poly})?
    
\end{description}

In addition to these criteria, the tables include specific references (e.g. to
language reports) for each of these languages. 

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

\section{On Methodologies for Application Design and Implementation}
\label{Method}

Probably the single most unifying view on database programming is that taken
from the position of {\em constraint maintenance}. As already emphasized the
data of interest for our applications serve as (partial) descriptions of
structures and processes that exist in their own organizational or physical
context independent of any computer system. From that context, data inherit a
wide range of qualifications, and the degree to which computerized systems
meet those qualifications decides upon their quality. 

We will first discuss issues of data qualifications by distinguishing three
classes of constraints with increasing generality: type constraints, dependency
constraints and semantic constraints. Then we will give a short overview over
some major approaches to database programming, each of which concentrates on a
particular class of such qualifications. 
                                         
\subsection{Classes of Constraints and Dependencies in Data-Intensive
            Applications}

In many applications one can isolate  domains, $D$, such that, for each element
$e\in D$,  there exist $n$ partial functions, $f_i : D \rightarrow C_i$ , $1
\leq i \leq n$,  each of which associates with $e$ an element of some
co-domain, $C_i$. Some basic restrictions on $f$, $D$ and $C$ may serve as a
starting point for constraint and dependency classification. 

In the simplest case, co-domains are supposed to be {\em pre-defined}
and {\em time invariant}. Those static co-domains may be given by
enumeration of their elements or by constraining larger, implicitly
defined sets. Such constraints can be upper and lower bounds or some other
propositional {\em domain constraint}. For example, take the
domain Employees, and the co-domains given by the value sets of the
types string, cardinal, Boolean, that function as employee name,
salary and marital status. 

Frequently, $n$ is fixed (for a long time) and each element, $e \in
D$, can best be perceived together with its $n$ associates,
$f_i(e)$, as one {\em structural entity} with $n$ components, identified by
appropriate component selectors, such as \verb$e.ci$ , \verb$e[i]$,
\ldots (= $f_i(e)$). One way or another, all data models do offer
constructs to express and maintain such structural constraints: the
class structure in object-oriented models serves that purpose, as
well as, for the more classical models, the structure of tuples in
relations, records in DBTG-sets, or segments in IMS hierarchies. 

For a wide range of domain and structural constraints there exist
standard compile-time techniques to map the constrained data
automatically and effectively into efficient storage structures and
to prove that all operations of an entire application program
maintain the constraints. Out of obvious reasons we will use the
term {\em type constraints} for the combination of both, structural
constraints and (static) domain constraints. 

However, the above co-domains need not be static; they may as well
be {\em dynamic} in the sense that their elements and cardinalities
do change over time. In such cases, the qualification of constrained
entities depends on the existence of their contributing entities,
giving rise to the class of {\em dependency} constraints. For 
example, take the domain, \verb$worksOn$, that associates entities
from the \verb$Employees$ domain and the \verb$Projects$ domain
under the assumption that projects and employees may come and go. 

Depending on the application semantics there may be many more ways
to qualify data. Frequently, those {\em semantic constraints} can be
formalized adequately by general first-order invariants on data
and by pre- and postconditions on transactions. 

\subsection{On Methodologies and Environments for Data-Intensive
Applications} 

The decision for a particular design methodology, i.e. for a set of
tools, tasks, and techniques considered appropriate for the
development of a data-intensive application system, depends heavily
on the extent to which the above mentioned classes of constraints
and dependencies are prevalent in the application and the degree to
which they are supported by the data model at hand. 

Early design methodologies, such as SSADM or multiview, concentrated
on representing domain constraints and structural constraints, 
modeling the entities of an application by the type system of the
programming language in use. 

For data-intensive applications entity models were soon extended to
Entity-Relationship models \cite{Chen76,Chen80,Chen85,SSW80,TYF86,Marc88} that
can also capture various forms of dependency constraints (1:1, 1:n, n:m).
Conceptually, however, the E-R approach can be encountered as a generalized
type design methodology: the dependencies modeled by an E-R diagram are mapped
into the database schema/type, and the DBMS acts as a global runtime facility
that maintains dependencies by standard checks at transaction commit time. An
overview of these more traditional approaches can be found in
\cite{OSVS82,OST83,OSVS86}. 

An essential step forward was the development of integrated
methodologies that support both, the design of DB schemata and the
programming of DB transactions \cite{ABLV81,BrRi84,RRUZ83}.

A remarkable contribution was the LIDAS environment, an interactive design
system that includes the database programming language Modula/R \cite{Reim83}
and the design tool GAMBIT \cite{BDRZ83}. Based on an extended E-R model,
GAMBIT provides interactive support for the specification of entities and
dependency constraints. Furthermore, it performs standard mappings of such
specifications into relational data structures and transaction skeletons that
consist of guarded database update operations. Such conditional updates
maintain dependency constraints and restricted classes of semantic constraints.
It is essential to this approach that the underlying integrated database
programming language has built-in high level language constructs for data of
type relation, such as first-order Boolean and relational query expressions,
and supports the notion of transactions \cite{MRS84}.

Most current developments in database application support are
characterized by that shift of responsibility for global constraint
maintenance away from the DBMS and towards integrated database
programming environments that care about entire application systems. 

The authors and their collaborators are involved in project DAIDA, its goal being
to design and build such an advanced software engineering environment for
developing and maintaining data-intensive applications
\cite{BJMSV89,BMSW89,SWBM89}. Essential novel characteristics of the DAIDA
approach are: 

\begin{itemize}
\item the utilization of a Knowledge Base Management System to
      represent
      \begin{itemize}
      \item application-dependent knowledge about the problem
            domain, collected as
            part of the requirements specification activity;
      \item meta-knowledge about the current system's design decisions and
            evolutionary history; and
      \item application-independent knowledge such as design and
            implementation strategies for data-intensive software.
      \end{itemize}

\item the application of three specific languages for the
      description of data-intensive software at each stage: 
      \begin{itemize}
       \item the knowledge representation language Telos for domain 
             analysis \cite{BGM85,BKMS89}
       \item the semantic data model TDL for conceptual design of
             system states and transitions \cite{DAIDA5,MyBeWo80}; and
       \item the imperative database programming language  DBPL for
             the efficient management of typed data including 
             sets/relations \cite{SEM88}.
       \end{itemize}
\end{itemize}

Since a major effort of the DAIDA project concentrates on the
production of high-quality database application software, the
mapping between the TDL level and the DBPL level is of particular
importance. TDL is based on the semantic data model of Taxis
\cite{MyBeWo80}, but has been refurbished to permit
predicative specifications of transactions by general semantic
constraints given as invariants and pre- and postconditions.
Furthermore, TDL maintains Taxis' object-oriented approach, however,
its expression language, unlike Taxis, is based on set theoretic
notions. 

For the mapping between TDL designs and DBPL implementations DAIDA 
makes the following assumptions:

\begin{itemize}

\item for a given TDL-design there may be substantially different
DBPL implementations, and it needs human interaction to make and
justify decisions that lead to efficient implementations;

\item the decisions are too complex to be made all at once --- let
alone automatically; it needs a series of refinement steps referring
to both data and procedural objects; 

\item not all objects and decisions relevant for the refinement
process need to have formally assigned properties; 

\item these properties should be recorded to support overall system
consistency and evolution.

\end{itemize}

To meet these requirements, DAIDA relies heavily on current work of
J.-R. Abrial \cite{AGMS88}.

\begin{itemize}

\item TDL designs are translated into Abstract Machines with states
represented by mathematical objects like functions and sets, and
state transitions defined by Generalized Substitutions; 

\item the formal properties of Machines and Substitutions are       
assured and organized by Abrial's interactive proof assistant, the
B-Tool \cite{AMSV88}.

\end{itemize}

DAIDA's first results support the conclusion that Abrial's
methodology of refining Abstract Machines is a promising direction
to study the issue of data-intensive application development in a
provably correct manner. In this setting, a language like DBPL
with a set- and predicate-oriented approach to data modeling, a
rich typing system, and abstract support for concurrency, recovery
and persistence, turns out to be an appropriate target for the
refinement of TDL specifications into database application software. 
                                               
% ------------------------------------------------------------------------

\section{Conclusion}

By now it has been recognized that the production of high-quality software
for data-intensive applications suffers severely from the lack of {\em
integrated} programming tools, methodologies and environments. Current
approaches are based on separately developed technologies like database
models and database management systems, programming languages and
compilers, communication protocols and operating systems. In current
applications, these pieces of technology have to interact through ad hoc
and narrow communication links leading to poor performance, difficult
maintenance and complex programming.
         
The classical examples of such ill-fitting components, assembled without
change, are the interfaces between database query languages and host
languages used for application programming: they lead to the well-known
{\em impedance mismatch} \cite{CoMa84}: 

\begin{description}

\item[]Databases operate set-at-a-time on many data instances of few built-in
  data types. They have a declarative style for queries, centralized data and
  integrity design (by the DBA), and a small set of powerful operators. 

\item[]Programming languages typically operate one-element-at-a-time on few
  data instances of a multiplicity of data types. They have an imperative
  style, separate compilation, pre and postconditions local to procedures and
  user defined types and operations. 

\end{description}

In recent years, research and development in the area of {\em database
programming languages} (DBPLs) has produced interesting results to overcome
these mismatches by a ``seamless integration'' \cite{CoMa84} of database
functionality in programming languages. 

To date there exists also a severe {\em competence mismatch} between the 
DB and PL area. Over the decades, the field of programming languages has agreed
upon a rich set of high-level principles that make the various dimensions of
computational technology available in a safe and user-acceptable form. In
the past, the area of databases definitely failed to reach a comparable
level of representative abstraction and linguistic maturity.

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

\bibliographystyle{[-.lit]florian}
\bibliography{[-.lit]florian1,[-.lit]florian2,[-.lit]florian3}
\end{document}
                                   

