% File : TypeSystem.tex
% Date : 15.8.1989 
% Date : 19.11.1989 adapted to HH TeX
% Note : Includes footnote describing form of publication ##
% Subj : 5 minute presentation: 2nd Int. Workshop on DBPLs, Oregon, May 1989
%
\documentstyle[a4]{article}  % ##
% \pagestyle{empty}     ##
%\setlength{\evensidemargin}{2truecm}
%\setlength{\oddsidemargin}{2truecm}
%\setlength{\topskip}{0truecm}
%\setlength{\textwidth}{16.5truecm}
%\setlength{\textheight}{22.9truecm}
\setlength{\parskip}{8pt}
\setlength{\parindent}{0.7truecm}
%\setlength{\topsep}{0truecm}
\newcommand{\comment}[1]{} 
\newcommand{\dbpl}{DBPL}
\newcommand{\nf}{NF$^{2}$} 
\newcommand{\kw}[1]{{\tt #1}}

\title{The Type System of \dbpl 
       \thanks{This research was supported in part by the European Commission
               under ESPRIT contract \# 892 (DAIDA).}
  \thanks{Appeared in {\em Proc.~of the 2nd International Workshop on Database
           Programming Languages, Portland, Oregon}, June 1989.}
      }
\author{Florian Matthes \and Joachim W. Schmidt}
\date{ {\small\em Fachbereich Informatik \\
                  Johann Wolfgang Goethe-Universit\"at \\
                  D-6000 Frankfurt, Germany \\
                  e-mail: schmidt@dbis.informatik.uni-frankfurt.dbp.de}
     }
     
\begin{document} 
\maketitle

\begin{abstract}        
\noindent
This paper presents the type system of the database programming language \dbpl\
\cite{SEM88} within the framework proposed in \cite{A*89}. 
\end{abstract}                                 


%------------------------------------------------------------------------------
     
\section{Rationale of \dbpl}   
                                        
% ## \thispagestyle{empty}
The database programming language \dbpl\ \cite{SEM88} is a
successor of Pascal/R \cite{Schm77} and integrates a set- and
predicate-oriented view of relational database modelling into the system
programming language Modula-2 \cite{Wirt83}. Based on integrated programming
language and database technology it offers a uniform and consistent framework
for the implementation of database applications. 

A central design issue of \dbpl\ was the development of abstraction mechanisms
for database application programming \cite{DAIDA4}. \dbpl's bulk data types are
based on the notion of (nested) sets. First-order predicates are provided for
set evaluation and program control. Particular emphasis had been put on the
interaction between these extensions and the type system of Modula-2. 
 
The rationale of the design of \dbpl\ could be characterized by the slogan
``power through orthogonality''. Instead of designing a new language from
scratch, we started with a modern system programming language and extended its
simple, but powerful concepts (e.g., for modularization, procedural
abstraction, and procedure types) {\em orthogonally} into three dimensions: 

\begin{itemize}
\item Bulk data management through a data type {\em set} (relation).
\item Abstraction from bulk iteration through {\em access expressions}.  
\item {\em Persistent modules} and {\em transactions} for sharing, recovery,
      and concurrency control.
\end{itemize}

Section 2 presents the type system of \dbpl\ within the framework proposed in
\cite{A*89}. To simplify the comparison of \dbpl\ with other languages, the
presentation strictly follows the structure defined in the framework paper,
although this leads to some omissions of essential features of \dbpl\
(e.g., control abstraction, transactions, views).

%------------------------------------------------------------------------------
        
\section{The Type System of \dbpl}

\subsection{The Nature of the Type System}

\dbpl\ is a fully upward compatible extension of Modula-2. Therefore, it
inherits the elaborate type system of Modula-2 that is extended orthogonally by
a set (relation) type and specific function types for subset definition
and set evaluation (selector and constructor types).

The inclusion of these ``database'' concepts into the type system of a strongly
typed programming language aims to overcome the traditional competence and
impedance mismatch between programming languages and database management
systems, since it provides 
\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 value. 
\end{itemize} 
         
DBPL is strongly typed; all type checks are performed statically.

Low level implementation details (e.g., storage layout of records, existence of
index structures) are completely hidden from the \dbpl\ programmer who uses
types only for data modelling.

\dbpl\ utilizes the notion of type compatibility to associate statically
checked {\em access rights} with views on large collections of shared objects.
The definition of access restrictions gains importance in connection with
the module concept of \dbpl\ to define ``safe'' database interfaces for
different clients of the same database.

\subsection{Expressiveness}\label{Expressiveness}
          
\dbpl\ offers the traditional ordinal types (\kw{INTEGER}, \kw{CARDINAL},
\kw{LONGINT}, \kw{LONGCARD}, \kw{CHAR}, \kw{BOOLEAN}) and real numbers
(\kw{REAL}, \kw{LONGREAL}). 
    
\dbpl\ supports application-specific extensions of the set of basic types by
means of enumeration types. 

Subrange types are derived from either basic or enumeration types. They impose
additional restrictions on the range of values described by the subrange type.
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. 
    
Bit strings are declared as sets of ordinal types. 

\dbpl\ provides the following type constructors:
\begin{description}
\item[Records:]
    The scope of the field labels is the record definition itself. They are
    also accessible as field designators referring to components of variables
    of that record type and within a \kw{WITH} statement. 

\item[Variants:]           
    \dbpl\ inherits variant records from Modula-2, which are more general than
    those of Pascal because both, nested and consecutive variant sections are
    supported. Access to fields within a variant section requires a run-time
    check of the tagfield. 
    
\item[Arrays:]
    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}. 

    Although arrays are of limited use for the implementation of dynamic data
    structures, they allow an efficient implementation of data structures that
    have a statically known maximum size. 
                                        
    Strings are arrays of characters with a fixed maximum length. The
    compatibility rules for strings are relaxed in order to allow assignments
    of strings of length $n$ to variables of length $m\geq n$. 

\item[References:] 
    \dbpl\ provides pointer types only to be upward compatible with Modula-2.
    Dynamic data structures and data structures with shared subobjects are
    implemented in \dbpl\ by means of (keyed) sets. Therefore, references are no
    first class citizens in \dbpl, e.g., they can not be made persistent.
     
\item[Procedures:]             
    The type of a procedure is derived from its signature. In \dbpl\ there are
    ordinary procedures and transaction procedures. The latter are marked by
    the symbol \kw{TRANSACTION} instead of \kw{PROCEDURE}\footnote{In contrast
    to ordinary procedures, nested and recursive calls of transactions are
    inadmissable. Persistent variables can only be accessed during the
    execution of a transaction. Transactions can be regarded as atomic with
    respect to their effects on the database.}. Each of them can be further
    subdivided into proper procedures and function procedures. The latter are
    activated by a function designator within an expresion, whereas proper
    procedures are activated by a procedure call statement. 

    A function result must have a basic or a reference type.
    There are two kinds of parameters, namely value and variable parameters.
    If the parameter is an array, the specification of the actual index
    bounds can be omitted. The parameter is then said to be an
    {\em open array parameter}.                            

\item[Opaque Types:] 
                                                                  
    \dbpl\ provides opaque types, which hide the representation of a type
    declared within a definition module. The implementation module contains the
    concrete type, which must be a basic type or a reference type\footnote{In
    most \dbpl\ applications, the hidden representation of an opaque type is a
    key value for a set variable; keys act as a ``handle'' for further
    informations stored within set elements since keys are the relational
    solution of the identification problem.}. If the hidden representation
    changes but the interface remains the same, client modules will not need to
    be reprogrammed, or even recompiled. 

\item[Sets:] Sets are the most important types for the representation of
    bulk collections of simple or composite objects in \dbpl. 

    A set type specifies a structure consisting of elements of identical type,
    called the set element type. The number of elements, called the cardinality
    of the set, is not fixed. A set variable never contains more than one
    element for a given value of the set element type (i.e., duplicates
    are not allowed).
    
    {\em Keyed sets} have the additional constraint that a keyed set variable
    never contains more than one element for a given key value. The declaration
    of a keyed set type therefore defines a list of components of the set
    element type that uniquely determines each set element \footnote{The
    current implementation doesn't support key components that are part of
    variant sections of a record type or that are of type set.}. 

    Note that relations of the relational data model are just the specific case
    of keyed sets of flat records. 
    
\item[Selectors:] 
    In \dbpl\ set evaluation is achieved through {\em access expressions}:
\begin{verbatim}
EACH e IN Set: p(e, .. ci ..)
\end{verbatim}                     
    is an expression that denotes exactly those elements in the set, 
    \verb$Set$, that fulfil the selection predicate \verb$p$, just as
    the arithmetic expression $5+7$ denotes $12$. The predicate \verb$p$
    may be existentially and universally quantified.
\begin{verbatim}
SetType{EACH e IN Set: p(e, .. ci ..)}
\end{verbatim}                      
    is a set expression that denotes the set of (copies of) the elements
    selected by the enclosed access expression.
\begin{verbatim}
FOR EACH e IN Set: p(e, .. ci ..) DO .. END
\end{verbatim}        
    provides selected iteration over those elements denoted by the enclosed
    access expression. 
    
    Finally, access expressions can be named and parameterized:
\begin{verbatim}
SELECTOR sp ON (S: SetType) WITH (.. pi: Ti ..): SetType;
BEGIN
  EACH e IN S: p(e, .. pi ..)
END sp;
\end{verbatim}                      
    Like procedures in Modula-2, selectors in \dbpl\ have types based
    on the selector signature. Due to the importance of bulk data access
    in database programming, \dbpl\ has selector types (and selector
    variables) as first-class language constructs.

    Selected relation variables can be compared with updateable database
    views.
    
\item[Constructors] extend the notion of selectors; they are based on
    relationally complete access expressions (not just one-variable
    selections) and provide (through recursion) the power of deductive
    databases \cite{JLS85}, \cite{ScLi85}, \cite{SGLJ89}.
\end{description}            
                                   
\dbpl\ is a {\em type-complete} language: composite types (records, variants,
arrays, procedures, sets, selectors and constructors) can be constructed
from elements of any (simple or composite) \dbpl\ type. Furthermore, objects of
any type can be used in any context (e.g., as parameters of procedures or right
hand sides of assignments) in a uniform way. This orthogonality within a
programming language enhances its modelling power and comprehensibility.
                     
An active line of research is the extension of the relational model towards
relations with relation-valued attributes (nested relations,
non-first-normal-form relations, \nf\ relations). In \dbpl\, the concept of
type completeness ``naturally'' leads to a data model where nested relations
are just a special case of nested type structures. 
                                                   
Recursive data structures and sharing of subobjects have to be modelled in
\dbpl\ by means of associative identifieres (key values of set types),
i.e., recursive types are not allowed (see \cite{Lame84} and \cite{LMS84} for a
presentation of a recursive data model, implemented on top of the ``flat''
relational data model of Pascal/R). 

\dbpl\ is a monomorphic language. The only polymorphic functions are the
predefined operations on sets (test on membership, insertions, deletions,
updates, quantified predicates, selective and constructive access expressions).


\subsection{Types and Values}

Values of all \dbpl\ types are first class language objects: They can be named,
denoted by expressions, stored in (persistent) variables and passed as value
and variable parameters. 

\dbpl\ has a uniform mechanism to construct values of a composite type (array,
record, variant, set) by an enumeration of its elements: the elements are
enclosed in curly brackets and preceded by the name of the type that is to be
constructed. Furthermore, it is possible to select elements of a composite value
by a path consisting of array index expressions, record components, and
key values for sets.
                     
Access expressions (see section~\ref{Expressiveness}) can be seen as a
generalization of these single-element construction and selection mechanisms. 

In \dbpl, it is possible to emulate (persistent) objects using modules and
opaque types. However, \dbpl\ is no object-oriented language, since it neither
supports inheritance nor late binding. 
                            
The predefined equality operator, \kw{$=$}, of \dbpl\ is overloaded:
\begin{itemize}
\item    It denotes structural equality if it is applied to operands of 
         a basic or a string type.
\item    It is not applicable to operands of record, variant or array types.
\item    It denotes set equality based on the values of the key components 
         if it is applied to operands of a set type.
\end{itemize}

\dbpl\ neither has null values nor object types.


\subsection{Relationships among Types}\label{Relationships}

There are two reasons why \dbpl\ uses {\em name equivalence} to define the
type equivalence relationship:
\begin{enumerate}
\item The type system of Modula-2 is based on name equivalence.
\item Persistent variables are introduced by ``normal'' variable declarations
      within a database definition module. All access to database variables
      is defined {\em statically} based on the standard import
      and export mechanisms of Modula-2. 
\end{enumerate}                                                 

As there is no dynamic binding between database variables and the programs 
using them, all compatibility checks can be performed at compile and link-time.

The handling of abstract, ``concrete'' and unnamed types in \dbpl\ is adopted
without changes from Modula-2.

Modules in \dbpl\ are not first-class values, but merely units of
encapsulation, compilation and persistence: Any compilation unit of \dbpl\
(interface, implementation or program module) can be declared as a
\kw{DATABASE} module. All variables declared at the outmost scope level of such
a module will be {\em persistent}, i.e., in contrast to other program
variables, their lifetime is longer than that of all programs importing this
database module. 

Persistent variables are 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. Transactions guarantee serializability (and failure
recovery). The (user-defined) initialization of database variables is performed
only once during database lifetime, namely before any access to the persistent
variables has been made. 


\subsection{Types and Subtypes}
                              
\dbpl\ only provides  primitive subtyping rules for its base types (integers,
reals) and subrange types. 

\dbpl\ neither has subtyping rules for record or object types as in Oberon
\cite{Wirt87b} and Modula-3 \cite{Card88}, nor has it type inference rules for
selector and constructor types (e.g., see Machiavelli \cite{OBBT89} in a
ML-style type system).                                


\subsection{Database Issues}

Persistence is an attribute of a module (see section~\ref{Relationships}). All
variables declared within a database module are persistent and shared
objects.

Changes to a (database) definition module only affect clients of that
interface, which have to be recompiled. Changes to a (database) implementation
module are invisible to its clients. 

The conversion of persistent data of an ``old'' version of a database module
into a representation suitable for a revised version of that module has to be
done explicitely. This process is supported by specific tools, outside the
scope of the language \dbpl, and so is the definition of access paths etc. 


\subsection{Other Issues}
                     
In the \dbpl\ project there is a strong commitment to implementability. A
multi-user DBPL system under VAX-VMS is used at the university of Frankfurt
since 1985 for courses on database programming. Based on this implementation,
there are several prototype extensions for concurrency control (optimistic,
pessimistic and mixed strategies), storage structures for complex objects,
recursive queries and distribution. The construction of a distributed \dbpl\
system is based on ISO/OSI communication standards and involved a
re-implementation of the compiler to generate native code for the IBM-PC/AT. 

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

\section{Concluding Remarks}

The most prominent feature of the \dbpl\ type system is the type-complete
integration of sets and first-order predicates into a stronly typed,
monomorphic language with persistence as an orthogonal property. 

This integration is motivated by the insight that the developers of
data-intensive applications need language support for efficient, {\em
set-oriented} access to both, private and shared collections of data. 

Although Type systems are a crucial part in the design of database programming
languages, there are other issues of particular importance for DBPLs: 
\begin{itemize}
\item How to decompose large database application programs into manageable
units, which can be developed and maintained independently?

\item How to support concurrency, sharing and failure recovery by appropriate
transaction models?

\item What about data and function distribution and communication?
\end{itemize}                                                     
Issues like these influenced the design and implementation of \dbpl\
\cite{DAIDA4} \cite{JGLR88} \cite{MRS84} but are de-emphasized in this paper.

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

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