% File:   language.tex
% Date:   13.2.1991, 14:30 FM
% Author: FM, JWS
%
% Subject:Programming School'91, Bulgaria
%

\documentstyle[a4]{article}

\newcommand{\kw}[1]{{\tt #1}}
\setlength{\parskip}{0.25\baselineskip}
\setlength{\parindent}{0cm}
%\pagestyle{empty}  % ##

\title{Relational Database Programming:\\
       Naming, Typing and Binding
       \thanks{This research was supported in part by the European Commission
               under ESPRIT BRA contract {\#~3070 (FIDE).}}
      }
\author{Joachim W. Schmidt \and Florian Matthes}
\date{ {\small University of Hamburg \\
               Department of CS \\
               Schl\"uterstra{\ss}e 70 \\
               D-2000 Hamburg 13 \\
               e-mail: schmidt@rz.informatik.uni-hamburg.dbp.de} 
     }


\begin{document}
\maketitle

\begin{abstract}
\noindent The DBPL language orthogonally integrates sets and first-order
predicates into a strongly and statically typed programming language,
and the DBPL system supports the language with full database
functionality including persistence, query optimization and transaction
management. Modern language technology with its sound naming, typing and
binding schemes applied to database concepts results in new insights
into the relationship between types and schemas, expressions/iterators
and queries, selectors and views, or functions and transactions.
\end{abstract}


\section{Introduction and Overview}
%===============================
\label{DBPLOverview}

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

In essence, it is that broad spectrum of demands -- the difference in
purpose, size, lifetime, availability etc.\ of data -- and the need to
cope with all these demands within a single conceptual framework that
has to guide the design of integrated database programming languages.


Here we present an introduction to DBPL \cite{SEM88}, an integrated
database programming language that addresses the need for a uniform
language framework for advanced database application programming.  DBPL
is a successor to Pascal/R \cite{Schm77} and extends Modula-2 into three
dimensions:

\begin{itemize}

\item bulk data management through a data type {\em set} (relation);
\item abstraction from bulk iteration through associative {\em access
      expressions};
\item {\em database modules} and {\em transactions} that abstract from
      persistence, sharing, concurrency control and recovery.
\end{itemize}

An essential guideline for the design of DBPL can be characterized by
the slogan ``power through orthogonality''.  Instead of designing a new
language (with its own naming, binding and typing rules) from scratch,
DBPL extends an existing language and puts particular emphasis on the
interoperability of the database concepts with those already present in
the programming language. Furthermore, DBPL aims at a uniform treatment
of volatile and persistent data, large and small data collections and a
uniform (static) compatibility check between the declaration and the
utilization of each name.


\section{Naming, Typing and Binding in a Relational Environment}

The first step towards a better integration of database concepts into a
language environment is to identify the basic database concepts and to
rephrase them in terms of an appropriate vocabulary of programming
concepts. The following paragraphs illustrate how DBPL captures the main
principles of set- and predicate-oriented database systems using the
well-understood notions of naming, typing and binding in procedural
programming languages.

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

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

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

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

DBPL inherits from Modula-2 all standard {\em built-in types}
(\kw{INTEGER}, \kw{BOOLEAN}, \kw{CHAR}, \kw{REAL}, \ldots) and the
mechanisms to declare {\em user-defined} types and {\em subrange types}
thereof.  {\em Strings} are treated as composite objects consisting of a
sequence of characters. Furthermore, DBPL provides {\em array} and {\em
record} type constructors.

A {\em relation type} specifies a structure consisting of elements of
identical type, called the relation element type. The number of elements,
called the cardinality of the relation, is not fixed. The declaration of the
relation type specifies the relation element type and an ordered list of key
components: 
\begin{verbatim}
TYPE SupplierRel = RELATION Num OF SupplierRec;
     MadeFromRel = RELATION Num OF MadeFromRec;
     PartNumSet  = RELATION OF PartNum;
     Point2DSet  = RELATION OF ARRAY [1..2] OF REAL;
\end{verbatim}                                                
The relation key defines a list of components of the relation element type
such that the relation always defines a function between its key and its
element type. In other words, each key value uniquely determines (at most)
one relation element. For example, the key constraint for a relation
\kw{Suppliers} of type \kw{SupplierRel} can be expressed by the
following predicate stating that the equality of the key component \kw{Num}
implies the equality of the relation elements: 
\begin{verbatim} 
ALL s1, s2 IN Suppliers (s1.Num = s2.Num) => (s1 = s2)
\end{verbatim}
An empty key component list is a synonym for an enumeration of all
components of the element type; in this case a relation is just a {\em
set} of relation elements.  The example above declares two relation
types (with record elements), a set of natural numbers
(\kw{PartNumSetType}), and a set of points that are represented by their
coordinates in the plane.

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

\begin{figure}
\small
\begin{center}
\begin{verbatim}
DATABASE DEFINITION MODULE SupplierPartDB;
TYPE
   PartNum        = [0..99999];
   SupplierNum    = [1000..9999];
   SupplierStatus = (unimportant, important, veryImportant);
   String         = ARRAY [0..29] OF CHAR;   
   Dollar         = REAL;
   Kilo           = REAL;       
   PartState      = (base, comp);
   SupplierRec    = RECORD                
              Num     : SupplierNum;
              Name    : String;
              Status  : SupplierStatus;
            END;
   MadeFromSubRec = RECORD     
              Num     : PartNum;        
              Quantity: CARDINAL;
            END;
   MadeFromSubRel = RELATION Num OF MadeFromSubRec;
   PartRec = RECORD
              Num     : PartNum;
              Name    : String;
              CASE State : PartState OF
                base :
                  Cost        : Dollar;
                  Mass        : Kilo;
                  SuppliedBy  : SupplierNum;
              | comp :
                  MadeFrom    : MadeFromSubRel;
                  AssemblyCost: Dollar;
              END; 
            END;
   SupplierRel = RELATION Num OF SupplierRec;
   PartRel = RELATION Num OF PartRec;
VAR
   Suppliers: SupplierRel;
   Parts    : PartRel;
END SupplierPartDB;               
\end{verbatim}
\end{center}
\caption{A typed relational database schema in DBPL}
\label{FigSchema}
\end{figure}  

\subsection{Scopes, Bindings and Lifetime}

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

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

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

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

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

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

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

\subsection{Expressions and Operations}
\label{Operations}\label{Expressions}

For each type constructor of DBPL (record, array, relation), there is a
{\em value constructor} to create objects of the composite type by 
enumerating its components:
\begin{verbatim}
v1:= SupplierRec{11, "John", important};
v2:= MadeFromSubRec{11, 100};
v3:= PartRec{3, "nut", base, 300.0, 20.3, 11};
\end{verbatim}   

In DBPL there are three kinds of {\em value selectors} for the selection
of components of a structured value: Elements of an array are selected
by an index value of their index type, enclosed in square brackets
(e.g., \kw{vector[7]}); Fields of a record are selected by their field
name (e.g., \kw{supplier.Name}); Elements of a relation are selected by
their key value, enclosed in square brackets (e.g., \kw{Suppliers[7]}).
Variable designators of DBPL therefore consist of a name followed by a
path of value selectors.

In addition to these element-wise operations, DBPL provides  specialized
set-oriented {\em query expressions} for relation types. There are three
kinds of query expressions, namely boolean expressions, selective and
constructive expressions.
 \begin{description} 
\item[Quantified Expressions] yield a boolean result (i.e. \kw{TRUE} or
\kw{FALSE}) and may be nested:
\begin{verbatim} 
SOME Supplier IN Suppliers (Supplier.Name = "John") 
ALL Supplier IN Suppliers (Supplier.Status = important) 
ALL Part IN Parts (Part.State <> base) OR 
  SOME Supplier IN Suppliers (Part.SuppliedBy = Supplier.Num) 
\end{verbatim} 

\item[Selective Access Expressions] are rules that select subrelations.
\label{SAE}\begin{verbatim}
EACH Supplier IN Suppliers: Supplier.Status = important
\end{verbatim}                                      
selects all elements \kw{Supplier} of the relation variable \kw{Suppliers}
that fulfil the selection predicate \kw{Supplier.Status $=$ important}.

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

\item[Constructive Access Expressions] are rules for the construction of
relations based on the values of other relations:
\label{CAE}\begin{verbatim}                                     
NameRec{p.Name, s.Name} OF EACH p IN Parts, EACH s IN Suppliers:
     (p.State = comp) AND (p.SuppliedBy = s.Num)
\end{verbatim}                                      
where \kw{NameRec} is a record of two strings defined as \kw{RECORD
Part, Supplier: String END}. The construction rule above defines how to
derive the names of all base parts with their suppliers from the two
stored relations \kw{Parts} and \kw{Suppliers}.

The application of a relation constructor to a constructive access
expression creates a relation that contains the values of the target
expression (preceding the keyword \kw{OF}), evaluated for all combinations
of the element variables (\kw{p}, \kw{s}) that fulfil the selection
expression \verb$(p.State = comp) AND (p.SuppliedBy =s.Num)$:
\begin{verbatim} 
NameRel{{p.Name, s.Name} OF EACH p IN Parts, EACH s IN Suppliers:
       (p.State = comp) AND (p.SuppliedBy = s.Num)}
\end{verbatim}
where the result relation type has to be defined as
\kw{TYPE NameRel = RELATION OF NameRec}
\end{description} 

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

In addition to these (side-effect free) expressions, DBPL provides specialized
{\em set operators} (\kw{:=, :+, :-, :\&}) for relation updates which assign,
insert, delete, and update sets of relation elements:
\begin{verbatim}
Parts:= PartRel{};
Suppliers:- SupplierRel{EACH s IN Suppliers: s.Status=important}
\end{verbatim}            

The types of the expression and the variable on the left-hand side have
to be compatible according to the rules of section \ref{Typing}.  As
illustrated by the examples above, the nesting of DBPL expressions
captures the essence of relational query languages, namely to provide
{\em iteration abstraction} by means of high-level set-oriented
selection, construction and update mechanisms.


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

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

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


\subsection{Computational Completeness}

The main reason to couple a DBMS with an algorithmically complete
programming language is to utilize the expressive power of the language
environment for arbitrary complex operations on the data stored in the
database.  DBPL incorporates all data types, operations and control
structures of the system programming language Modula-2, including
recursive functions and procedures, higher-order functions and
elaborately structured statements. DBPL is therefore an ideal
environment for the implementation of complex database application
programs.

It should be noted that database and programming language features of a
database programming language should not simply reside side-by-side. On the
contrary, one needs many interfaces to create synergy between these
features. DBPL therefore allows the orthogonal combination of the concepts
inherited from both worlds, for example:

\begin{itemize}
\item Relation types are allowed to appear in arbitrary contexts,
i.e. not only as types for database variables, but also as types of local
variables within procedures, or as types of value- or variable-parameters; 

\item Quantified expressions (see \ref{Expressions}) can appear not only
within query expressions but also in conditionals or as termination conditions
of loops; 

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

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

\subsection{Type Completeness}

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

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

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

\subsection{Completeness of Abstraction Mechanisms}

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

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

The following selector named \kw{ImportantSuppliers} defines an
updateable view on the supplier relation, selecting those suppliers having
\kw{important} as their status (see also p. \pageref{SAE}). 
\begin{verbatim}
SELECTOR ImportantSuppliers: SupplierRel;
BEGIN  EACH S IN Suppliers: S.Status = important  END ImportantSuppliers;
\end{verbatim}

The constructor \kw{SuppliersForParts} (see also p. \pageref{CAE}) names a
non-updateable view that is derived from the base relations \kw{Parts} and
\kw{Suppliers} and that contains pairs of parts and supplier names for all
base parts with their respective suppliers.
\begin{verbatim}
CONSTRUCTOR SuppliersForParts: NameRel;
BEGIN
  NameRec{p.Name, s.Name} OF EACH p IN Parts, EACH s IN Suppliers:
      (p.State = comp) AND (p.SuppliedBy = s.Num)
END SuppliersForParts;
\end{verbatim}

Without going into details it should be noted that naming (of
statements, expressions etc.) naturally leads to the concept of {\em
recursion}. The semantics of a recursive query expression in DBPL is not
defined operationally (as it is common practice for procedures) but as
a least fixed point of recursive set equation \cite{JLS85,ERMS91}. Thereby
constructors are at least as expressive as recursive DATALOG programs
with stratification semantics.

\label{Transactions}
Another important abstraction mechanism of DBPL is the {\em transaction}
that allows database programmers to abstract from concurrency and
recovery issues when accessing persistent and shared database variables.
Transactions can be regarded as atomic with respect to their effects on
the database. In particular, the implementation of DBPL guarantees that
concurrent transactions will be executed in a serializable schedule.
\begin{verbatim}
TRANSACTION DeleteSuppliers(Suppliers: SupplierRel): BOOLEAN;
(* returns TRUE on success *)
BEGIN
  IF SOME bp IN Parts (bp.State = base) AND
    SOME s IN Suppliers (bp.SuppliedBy = s.Num) THEN
    RETURN FALSE; (* referential integrity violated *)
  ELSE         
    SupplierRel:- Suppliers;
    RETURN TRUE
  END;
END DeleteSuppliers;
\end{verbatim}          


\subsection{External Interfaces}

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

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

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

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

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

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

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



\section{Summary and Conclusion}

Practical experience with the use of DBPL in lab classes demonstrates
that students quite willingly accept the clear and improved interaction
of a database model in form of ``typed relational sets'' and
``declarative set expressions'' with other concepts needed and found in
procedural languages, like strong typing, fine-grained scoping and
dynamic parameterization. However, while set-oriented expressions are
readily used for the more standard data retrieval and manipulation
tasks, experience also seems to indicate that there is a tendency to
fall back to procedural solutions for more complex tasks, e.g. by
embedding set expressions into iterators or recursive procedures.

The reason behind such user behavior may originate from the fact that
simple query expressions can still be understood by refering back to an
operational semantics in terms of set construction by loops,
conditionals and assignments. However, this view becomes less
appropriate for complex queries such as recursive ones that require a
more abstract understanding in terms of model-theory and fixpoint
semantics.

For designers and teachers it is definitely quite a challenge to
reconcile this kind of ``abstraction mismatch'' inside their languages,
a problem hard to overcome without leaving the framework of traditional
computer languages (and definitly ruling out the ``PL1 + SQL + "*"
''-approach). We are convinced that only advanced language technology
with higher-order and polymorphic functions, taxonomic typing systems
and reflection will form the appropriate basis for next-generation
database programming languages \cite{Card89,MaSc91,SFSS90}.

\nocite{MaSc89,ScMa90b,ScMa89,ScMa90a}

\bibliographystyle{florian}
\bibliography{../bib/florian}

\end{document}