% File:    dbpl3.tex
% Author:  F. Matthes
% Date:    24-SEP-991
% Title:   Bulk Types: Built-In vs. Add-On
%          DBPL-3 Workshop, Nafplion, Greece
%
\documentstyle[xple_indnt]{article}
\setlength{\topmargin}{0cm}
\setlength{\topskip}{0cm}
\setlength{\parindent}{0.7cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\setlength{\marginparwidth}{0cm}
\setlength{\textwidth}{16.5cm}
\setlength{\textheight}{23.5cm}
\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\kw}[1]{{\sl #1}}
\newcommand{\k}[1]{{\bf #1}}
\newcommand{\yes}{$\surd$}
\newcommand{\no}{$-$}
\newcommand{\comment}[1]{\par [*** #1 ***] \par}
\newcommand{\separate}{\par\vspace*{\baselineskip}
{\hrule width \textwidth height 0.2pt depth 0pt}\par\vspace*{\baselineskip}}
\newcommand{\pictures}[4]{\mbox{%
\special{picture #3 scaled #4}\hspace*{#1}\rule{0cm}{#2}}}

\pagestyle{empty} % ## plain

\title{{\Large\bf Bulk Types: Built-In or Add-On?}}
\author{Florian Matthes \and Joachim W.\ Schmidt}
\date{{\small University of Hamburg \\
      Department of Computer Science\\
      Schl\"uterstra{\ss}e 70 \\
      D-2000 Hamburg 13 \\
      \verb$matthes,schmidt@dbis1.informatik.uni-hamburg.de$}}

\begin{document}
\maketitle
\thispagestyle{empty}
\footnotetext[1]{This work was supported by the European Commission under
ESPRIT BRA contract \#~3070 (FIDE).}
%##\footnotetext[2]{Appeared in: Proceedings of the Third
%##International Workshop on Database Programming Languages,
%##Nafplion, Greece. Morgan Kaufmann Publishers. Sept.~1991.}

\begin{abstract} 
\noindent Bulk structures play a central r\^ole in data-intensive application
programming. The issues of {\em bulk type} definition and
implementation as well as their integration into database programming
languages are, therefore, key topics in current DBPL research.

In this paper we raise a more general language design and implementation
issue by asking whether there should be at all built-in bulk types in
DBPLs. Instead, one could argue that bulk types should be realized
exclusively as user-definable add-ons to unbiased core languages with
appropriate primitives and abstraction facilities.

In searching for an answer we first distinguish two substantially
different levels on which bulk types are supported. {\em Elementary
Bulk} essentially copes with persistent storage of mass data, their
identification and update.  {\em Advanced Bulk} provides additional
support required for data-intensive applications such as optimized
associative queries and integrity support under concurrency and failure.

Our long-term experience with bulk types in the DBPL language and system
clearly shows the limitation of the built-in approach: built-in {\em
Advanced Bulk}, as elaborate as it may be, frequently does not cover the
whole range of demands of a fully-fledged application and often does not
provide a decent pay-off for its implementation effort. On the other
hand, restriction to built-in {\em Elementary Bulk} gives too little
user-support for most data-intensive applications.
   
We report our current work on open database application systems which
favours DBPLs with bulk types as add-ons, and outline some of the
technological requirements for highly reusable implementations of
languages with advanced user-provided bulk type definitions.
\end{abstract}

% -------------------------------------------------------------------
\section{Bulk Data: A Language and System Problem}

There is no doubt that bulk types are of central importance in data-intensive
application programming. Accordingly, the design and implementation of bulk
types is a key topic in DB and DBPL research and development
\cite{Schm78,A*89,ABW*90,HuSu90,AtBu86}. Irrespective of the particular kind of
bulk data structures present in a given database programming environment
(e.g.\ lists, sets, relations in traditional DBPLs; class extents in
object-oriented databases; base predicates in deductive databases or
extensionally defined functions in functional databases), one can
distinguish two fundamentally different approaches to bulk type support
within a language framework:

\begin{description}
\item[Built-In Bulk Types] are provided as first-class parameterized type
constructors in several programming languages
\cite{Schm77,LRV88,OBBT89,NaTs89}, their syntax, type rules, semantics and
implementation being hard-wired into the language processor and the
run-time system support.

\item[Add-On Bulk Types] are defined and implemented utilizing standard
built-in language mechanisms (typing, naming, binding, scoping or
recursion) of a sufficiently generic general-purpose base language like
ML \cite{MTH90}, Modula-3 \cite{Card88}, Napier-88 \cite{DCBM89} or Eiffel
\cite{Meyer88}.
\end{description}

In this paper we analyze the motivations and basic assumptions behind both
(extreme) approaches and explore their individual advantages and shortcomings.
This investigation is based on the one hand on our substantial experience with
the design and implementation of database programming languages incorporating
powerful built-in bulk type support \cite{Schm77,Reim83,MaSc89}. On the other
hand it reports on our current work within the ESPRIT Basic Research Action
FIDE (Formally Integrated Database Environment) where we are designing
Tycoon\footnote{TYCOON: Typed Computational Objects in Open Environments}, a
language and system environment with add-on bulk types.

As elaborated in more detail in section~\ref{limitations}, the choice between
built-in and add-on bulk types is to be regarded more as an
architectural decision than a pure language-design problem. Therefore,
we will also present our experience gained in the process of
implementing built-in and add-on bulk types.

The issue of built-in vs. add-on bulk types has a longer tradition in
the Persistent Programming Language community, in the DBPL camp,
however, the main goal always consisted in building in advanced bulk
types. By reporting on our own past experiences and future
expectations we attempt to contribute to a more open and objective
discussion on this important DBPL research issue.

In section~\ref{built-in} we report on experience with built-in bulk
types by referring essentially to DBPL, a set- and predicate-based
procedural database programming language \cite{SEM88}. We illustrate
issues in language design, system construction and application
programming involving built-in bulk types. Since others have already
discussed the general properties and requirements of bulk types in some
detail \cite{ART91}, section~\ref{gist} only summarizes the gist of
built-in and add-on bulk types in terms of their elementary and advanced
demands.

In section~\ref{limitations} we point out some of the more severe
limitations of the built-in approach that provide a strong incentive to
look for systematic add-on approaches to bulk type definition and
manipulation in open database application systems. To illustrate this,
section~\ref{sets-add-on} sketches how typical built-in bulk types can
be captured as an add-ons in a state-of-the-art programming language.

Finally, section~\ref{iterators} outlines our current work in the Tycoon
environment that aims at defining uniformly and implementing
systematically declarative iteration abstractions applicable to a wide
variety of bulk structures. Specifically, we explain how the concepts of
data independence and query optimization can be generalized to liberally
extensible systems. We also identify specific language mechanisms
required for the efficient and robust construction of such open and
extensible database application systems.


% -------------------------------------------------------------------
\section{Experience with Built-In Bulk Types}
\label{built-in}

Looking back on several generations of models and systems
for bulk data management, one realizes that each of them was designed
and implemented targeting a rather uniform user community  with very
similar functional and operational requirements. Based on a thorough
understanding of the application domain (e.g.\ standard banking
applications), a high investment in specific though generic built-in
structures (e.g.\ polymorphic relation types) was justified.

We first study the substantial pay-off of such a language investment
as exemplified by DBPL, a type-complete database programming language
providing generalized (keyed) sets as built-in bulk types.
Specifically, we focus on the finer points of DBPL to clarify general
subtleties arising in bulk type definition and use. We also relate DBPL
design decisions to approaches found in other languages and systems.

In section~\ref{predicates}, we argue for the necessity to equip bulk types
with appropriate high-level abstractions to achieve ``declarative'' bulk data
access and generalized constraint maintenance without impairing their
operational qualities (efficient, concurrent, recoverable access).

We conclude the discussion of built-in bulk types by summarizing 
requirements for bulk types for data-intensive applications in persistent
environments (section~\ref{gist}).


\subsection{Bulk Types as Parameterized Type Operators}
% ------------------------------------------------
\label{relation-types}

DBPL provides a built-in parameterized relation type constructor that
is parameterized not only by the \e{relation element type} but also by an
(optional) ordered list of \e{key components}, which have to be selectors for
values of the relation element type: 
\begin{xple}
\k{relation} $<$key-components$>$ \k{of} $<$element-type$>$
\end{xple}
Here are some examples of simple and non-standard relation type declarations
in DBPL: 
\begin{xple}
\k{type}
   Persons = \k{relation} name \k{of} \k{record} name:String; age:CARDINAL \k{end};
   Employees = \k{relation} persNum \k{of} \k{record} 
         persNum:CARDINAL; salary:REAL; age: CARDINAL; partners :Persons
         \k{case} status: (PartTime, FullTime) \k{of}
           PartTime: hoursPerMonth: CARDINAL; $|$ FullTime: employedSince: Year;
         \k{end}
      \k{end}; 
   PersNumSet = \k{relation} \k{of} persNum;
\end{xple}

A value of a relation type is a homogeneous collection of simple values
(\kw{PersNumSet}) or aggregate values (\kw{Employees}) as specified by the
relation element type. The number of elements, called the cardinality of the
relation, is unconstrained. 

The cardinality of relation variables can vary dynamically, i.e.\ all
relation variables in DBPL programs are \e{mutable} values. Most
built-in bulk types (like those of Pascal/R, E or $O_2$
\cite{Schm77,RiCa87,LRV88}) and add-on bulk types (collections defined
in Smalltalk, Eiffel, Trellis/Owl or Modula-3
\cite{GoRo83,Meyer88,S*86,Card88}) define mutable entities. Bulk types in
functional languages (Machiavelli, FQL, ADAPTBL or TRPL
\cite{OBBT89,Nikh85,SFSS90,StSh91}) define pure values and therefore do
not offer destructive insertion, deletion or element update operations
on variables of bulk types (see also Fig.~\ref{table:bulk-types}).

The choice of the relation element type in DBPL is unconstrained, i.e.\
the relation type constructor is truly data type complete like the more
standard array, sequence or list type operators. Relation types are
integrated \e{orthogonally} into DBPL in the sense that they can be
utilized uniformly in (nested) type declarations, variable declarations,
parameter positions, module declarations etc. Furthermore, values of
relation types adhere to standard naming, typing, binding, scoping and
persistence rules.

A closer look at DBPL reveals, however, some complications inherent in
all bulk types (relations, maps, etc.) that are to provide
\e{associative element access} \cite{ART91,SDD*86,SFL83}. In DBPL, the key
of a relation defines a list of components of the relation element type
that \e{uniquely} determines each relation element. Key components have
to define total functions over the domain of possible relation elements.
Therefore, they must not be components of variant sections of a variant
record type (e.g., the field \kw{hoursPerMonth} is not a valid key
component for \kw{Employees}). An empty key component list is a synonym
for an enumeration of all components of the element type that are not
contained in a variant section of a variant record; in this case a
relation is just a \e{set} of relation elements (\kw{PersNumSet}).

Whereas the above restrictions are direct consequences of the semantics of
keyed relations, the decision in the current implementation of DBPL not to
allow key components that exceed 4K in size or that involve nested relations
-- which would require a (possibly nested) relation equality test for every
relation update operation -- is based on ``pure'' engineering considerations.


\subsection{Elementary Operations on Instances of Bulk Types}
% -----------------------------------------------
\label{primitives}

A minimum set of operations required for values of bulk types are the
means to define an empty bulk structure (\e{empty set}), to combine
two bulk structures of the same type (\e{set union}) and to access
individual elements of a bulk structure (\e{choose}; for a more
rigorous discussion of these issues see \cite{StSh91} and
\cite{Wadl90}). The following subsections present alternative
approaches to these tasks.

\subsubsection{Generation of Bulk Values}

A bulk type has at least to have functions to yield ``empty''
(\kw{nil}\/) bulk values for a given element type and that add a single
element to a bulk structure (\kw{cons}\/). Many programming and
database languages provide syntactic support to denote concisely
values of bulk types by an enumeration of their elements as
demonstrated by the following DBPL example: 

\begin{xple}
persons:= Persons\{\}; persons:= Persons\{person1,person2\}   
\end{xple} 
The type name preceding the curly brackets is required in DBPL to
determine the key constraints on the constructed relation value.

\subsubsection{Operations on Bulk Values}

In an orthogonal language framework there should be no need to define
special mechanisms to name, bind, scope or parameterize values of bulk types
since these should be ``inherited'' from the basic types or other aggregate
types like records or tuples. In particular, the semantics of assignments,
parameter passing mechanisms and equality predicates (monomorphic or
polymorphic \`a la ML) require particular attention from the language designer
and the application programmer. The following example should give an idea of the
variety of possible semantics for set and record assignment and set equality in 
different systems and languages:
\begin{xple}
person1:= Person\{"Peter", 35\}; person2:= Person\{"Peter", 35\}; person3:= person1;   
persons:= Persons\{person1\}; 
\k{if} persons = Persons\{person2\} \k{then} ``deep equality" 
\k{elsif} persons = Persons\{person3\} \k{then}``shallow equality"
\k{elsif} persons = persons \k{then} ``identity"
\k{else} ``???" \k{end};
\end{xple}

DBPL, Pascal/R, LDL and Machiavelli have built-in deep equality
semantics, whereas O$_2$, for example, utilizes shallow equality for
sets of objects.  Languages with add-on bulk data types (like PS-algol,
Napier-88, Eiffel or Smalltalk) rely heavily on reference semantics
(L-value bindings \cite{AtMo85}, object identity \cite{KhCo86}).
Implementations of collections of composite objects in these languages
typically store references to collection elements and often provide a
shallow equality test in addition to the built-in identity test. Because
of this sharing, an update to a collection element, like 
\begin{xple}
person1.age:= 36;
\end{xple}
in these systems simultaneously affects the value of collection
variables (e.g., \kw{persons}) referencing this object. 

DBPL -- as an extension of Modula-2 -- provides strict copy semantics
for assignments, value parameters, relation equality and relation
construction.  Since there is no notion of object identity in DBPL, it
may be necessary for database programmers to ``implement'' object
identifiers by explicitly managed unique keys.  On the other hand (as
argued at length in \cite{MOS91,ScMa90b}) copy semantics give the
database user fine control over the locality of and dependencies between
data objects in logically partitioned (distributed, heterogeneous,
autonomous) object store environments.

The nature of bulk types usually calls for incremental update operations in
addition to the plain bulk assignment. Here are some examples of such relation
update operations (assignment,  insertion, deletion and update) in DBPL: 
\begin{xple}
persons:= oldPersons;
persons:+ newPersons;
persons:-- oldPersons;         
persons:\& updatedPersons; 
\end{xple}
These operations on relation values are defined such that the 
\e{key integrity constraint} (no duplicate keys) is maintained
dynamically at run-time. For example, the above insertion operation
(:+) will ignore all elements in \kw{newPersons} with key values that
are already present in \kw{personSet}. The standard function
\kw{RESTRICTED()} allows the programmer to detect such constraint
violations (a posteriori). This deterministic behaviour of the update
operators is in strong contrast to the non-deterministic semantics of
the relation union operation in DBPL:  
\begin{xple}
persons:= Persons\{Person\{"Peter", 35\}, Person\{"Peter", 36\}\}
\end{xple}
DBPL does not specify which of the two tuples with conflicting key values is
chosen to become the member of \e{persons}. Without going into
details, this non-determinism also extends to DBPL's set-oriented query
expressions and to its recursive fixed-point queries and was found to
be essential for effective query optimization without pertubating the
comprehensibility of DBPL programs \cite{ScMa90b,ERMS91}.

To our understanding, the definition of useful bulk types (maps, relations,
bags, arrays etc.) has to include the possibility to attach {\em dynamic integrity
constraints} on instances of bulk types, e.g. the support for (associative)
identification of collection elements. Other examples for such integrity
constraints are subset relationships between the extent of a subclass and its
superclass(es), referential integrity constraints, cardinality constraints etc.

Some of the subtleties and pragmatic considerations of DBPL (and other systems)
are related to the handling of possible {\e constraint violations}. Therefore bulk
types are intimately related to other language mechanisms (transactions,
exceptions, triggers, evaluation strategies, side-effects) that at first glance
seem to be orthogonal to bulk type design.

\subsubsection{Element Selection}

There are three main approaches to accessing individual elements in a bulk value:
\begin{description}

\item[Cursors] provide a means to select individual elements from a bulk
structure according to a fixed (perhaps undefined) ordering on the
collection elements. Cursors can be defined as explicitly managed data
structures or they  can be manipulated implicitly (via side-effects)
as it is done via traditional interfaces between databases and
programming languages.

A conceptually rather different approach to navigation through homogeneous bulk
values is taken in functional languages: for example, the functions \kw{car} and
\kw{cdr} (\kw{head} and \kw{tail} or \kw{choose} and \kw{rest} etc.)
allow the access to individual collection elements as well as the book-keeping of
the progress of the iteration \cite{StSh91}. The following example illustrates
how to skip over the first $n$ elements of a stream in a functional framework. The
head element of a stream corresponds to the value at a cursor position while the
binding to the tail stream provides the ability to ``move'' the cursor.
\begin{xple}
\k{let rec} skip(s:Stream n:Int):Stream = 
   \k{if} $n<=0$ \k{then} s 
   \k{elsif} emptyStream(s) \k{then} s
   \k{else} skip(tail(s) n-1)
   \k{end}
\end{xple}

DBPL provides -- in addition to iterators and high-level query expressions --
low-level navigational operations on relation values (for details see
\cite{SEM88}). The following DBPL code fragment illustrates a programming
situation that requires an explicit navigation over bulk data structures. The
\kw{display} and \kw{getChoice} routine embedded in a \k{while}-loop allow a user
to interactively scroll forward and backward through the relation \kw{persons}. 
\begin{xple}
LOWEST(persons, p); choice:= forward;
\k{while not} EOR() \k{and not} (choice = quit) \k{do}
   display(p); choice:= getChoice();
   \k{if} choice = forward \k{then} NEXT(persons, p) 
   \k{elsif} choice = backward \k{then} PRIOR(persons, p)
   \k{end}
\k{end}
\end{xple}

\item[Iterators] abstract from the details of the element selection process.
Procedural languages like DBPL, SETL, Galileo or CO$_2$ are equipped with loop
constructs to execute a statement (sequence) for all elements of a collection in
turn: 
\begin{xple}
\k{for each} p \k{in} persons: p.age $>$ 30 \k{do} p.age:=  p.age + 1 \k{end}
\end{xple}

Higher-order functions like \kw{set-reduce} or \kw{map} \cite{StSh91} provide
another form of iteration abstraction in a functional framework:
\begin{xple}
\k{let} incrementAge = \k{fun} (p:Person):Person \k{tuple} p.name  p.age + 1 \k{end}
\k{let} newPersons = map(persons incrementAge)
\end{xple}
It should be noted that cursors offer more complex element selection patterns than
iterators which only enable a static nesting of iterations. Interactive scrolling
through a relation or linear-time merging of sorted lists are typical application
examples that call for cursors or general-purpose ``continuations'' \cite{SNG90}. 
However, for most programming tasks, such explicit control is  not required, and
iterators, an algebra or a calculus are to be preferred. The expressive power of
various iterators is discussed, for example, in \cite{HuSu90,StSh91}.

\item[Associative Element Selectors] provide an elegant solution for programming
tasks that require value-based access to an individual collection element. As an
example, the following DBPL statement increments the age of \kw{"Peter"} in the set
of persons: 
\begin{xple}
\k{with} persons["Peter"] \k{do} age:= age + 1 \k{end}
\end{xple}
In languages without such a facility one cannot adequately exploit the key uniqueness
constraint and one has to resort to standard bulk iteration constructs:
\begin{xple}
\k{for each} p \k{in} persons: p.name = "Peter" \k{do} p.age:=  p.age + 1 \k{end}
\end{xple}

Associative set and element selection is also a basis for logic- and
constraint-based programming languages like LDL \cite{NaTs89} or Life
\cite{AKN89}): 
\begin{xple}
person(Name, Age), Age$>$60.
person("Peter", PetersAge).
\end{xple}
\end{description}

It should be emphasized that in the above discussion on mutability, copy
vs.\ reference semantics, the handling of constraint violations or basic
iteration facilities, we do not argue in favour of a specific solution.
On the contrary, we are more interested in identifying the dimensions of
the available design space for bulk type definition since a better
understanding of this space seems to be a prerequisite to devising
language mechanisms supporting a wide range of (possibly user-defined)
bulk types and iteration facilities.


\subsection{Declarativity and Bulk Types}
% ---------------------------------------
\label{predicates}
          
DBPL provides named and parameterized access expressions as typed
first-class language constructs. (Recursive) database queries, bulk
iteration, viewing mechanisms and constraint management can thereby be
successfully distilled to a single, ``declarative'' iteration
abstraction that can furthermore be integrated rather well into a
compiled procedural programming environment.

In addition to the element-oriented operations sketched in the previous section,
DBPL provides declarative {\em query expressions} over values of bulk types.
There are three kinds of query expressions, namely boolean expressions,
selective and constructive expressions.
\begin{description}
\item[Quantified Expressions] yield a boolean result and may be nested:
\begin{xple} 
\k{some} e \k{in} employees (e.status = PartTime) 
\k{all} e \k{in} employees (e.status = PartTime) 
\k{all} e \k{in} employees \k{some} p \k{in} e.partners (p.name = "Peter")
\end{xple} 

\item[Selective Access Expressions] are \e{rules} for the selection of
relation elements.
\begin{xple}
\k{each} e \k{in} employees (e.status = PartTime)  
\end{xple}                                      
denotes all elements \kw{c} of the relation variable \kw{employees} (of type
\kw{Employees}) that fulfil the selection predicate \kw{(e.status =
PartTime)}. A selective access expression within a relation constructor
denotes the  subrelation of all selected tuples:
\begin{xple}
Employees\{\k{each} e \k{in} employees (e.status = PartTime)\}
\end{xple} 

Another context for selective access expressions are iterators (element-at-a-time
processing):
\begin{xple}
\k{for each} e \k{in} employees (e.status = PartTime) \k{do} e.hoursPerMonth:= 40 \k{end}
\end{xple} 

Finally, selective access expressions can be named and parameterized (see 
\cite{MaSc89}), a process conceptually similar to view definitions in relational
DBMS:
\begin{xple}
\k{selector} casual \k{on} (emp:Employees): Employees;
\k{begin each} e \k{in} emp (e.status = PartTime) \k{end} casual;
\end{xple}
Selectors differ from relation-valued functions in that they allow updates on the
selected subrelations. DBPL emphasizes this analogy to array selectors by the
following syntax:
\begin{xple}
employees[casual]:+ Employees\{peter\}
\end{xple}
The semantics of such selected bulk updates are discussed in \cite{ScMa90b}. In
this particular example, the selector \kw{casual} enforces the constraint that
only part time employees can be inserted into the
relation \kw{employees}.

\item[Constructive Access Expressions] are rules for the construction of
relation elements:
\begin{xple}
Pair\{e.age, p.age\} \k{of} 
    \k{each} e \k{in} employees \k{each} p \k{in} e.partners:
         (e.status = PartTime) \k{and} (p.age $>$ 22)
\end{xple}
where \kw{Pair} is the type \kw{\k{record} ageEmp, agePartner: CARDINAL \k{end}}.

Again, constructive access expressions can be named and parameterized. Recursive
constructor definitions have fixed point semantics similar to stratified datalog
programs \cite{ERMS91}. The use of a constructive access expression in a relation
constructor creates a relation that contains the values of all tuples denoted by
the construction rule.
\end{description}


\subsection{The Gist of Bulk Types}
% -------------------------------------
\label{gist}

The numerous requirements for bulk types (see, e.g., \cite{ABW*90,ART91})
can be classified into \e{elementary} and \e{advanced} requirements which
we will summarize below. This discussion is valid for both, built-in as
well as add-on bulk types, and, therefore, also establishes a framework
for section~\ref{add-on} where we investigate environments that
enable their users to add-on bulk types meeting these elementary and
advanced requirements.

As a first cut, the distinction between an elementary and an advanced
requirement can be based on the kind of technology that is required to
provide a particular bulk type support (see
Fig.~\ref{table:bulk-types}). Elementary requirements usually can be met
by \e{local} modifications to language processors (compilers, abstract
machines, run-time support libraries) essentially based on
\e{programming language} technology. On the other hand, more advanced
requirements (as mentioned already in section~\ref{built-in}), for
example effective query optimization or stratification analysis of
fixed-point queries, involve \e{global} analysis and modifications as
provided by advanced \e{database} technology.

\begin{figure}
\begin{center}
\small
\begin{tabular}{|l|ccccc|}
\hline  & & & & &
\\ {\bf Support / Language:} &  DBPL & Maps & Machiavelli & O2 & LDL
\\ & & & & &
\\ \hline & & & & &
\\ {\bf elementary} & & & & &
\\ type completeness      &  \yes  & \yes & \yes   & \yes  & \no
\\ subtyping              &  \no   & \no  & \yes   & \yes  & \no 
\\ ordering               &  \no   & \yes & \no    & \yes  & \no
\\ sharing                &  \no   & \yes & \no    & \yes  & \no
\\ update in place        &  \yes  & \yes & \no    & \yes  & \no
\\ persistence            &  \yes  & \yes & \no    & \yes  & \yes
\\ access optimization    &  \yes  & \yes & \no    & \yes  & \yes 
\\ & & & & &
\\ \hline & & & & &
\\ {\bf advanced} & & & & & 
\\ key constraints        &  \yes  & \yes & \no    & \yes  & \yes
\\ first-order predicates &  \yes  & \no  & \no    & \yes  & \yes
\\ general constraints    &  \no   & \no  & \no    & \yes  & \yes
\\ updatable views        &  \yes  & \no  & \no    & \no   & \no
\\ fixed-point queries    &  \yes  & \no  & \no    & \no   & \yes
\\ query optimization     &  \yes  & \yes & \no    & \yes  & \yes
\\ concurrent access      &  \yes  & \no  & \no    & \yes  & \no
\\ recovery               &  \yes  & \yes & \no    & \yes  & \no
\\ & & & & &
\\ \hline
\end{tabular}
\end{center}
\caption{Examples of Languages with Built-In Bulk Types}
\label{table:bulk-types}
\end{figure}

\subsubsection{Elementary Requirements}

The basic operations outlined in section~\ref{primitives} form a basis
for bulk type definition. In order to facilitate the definition of new,
type-safe bulk structures, a language has to support at least
\e{parametric polymorphism} and \e{type abstraction} over generic data
structures. In most standard programming languages, the definition of
bulk types also requires the use of \e{higher-order functions}, e.g. to
define a specialized monomorphic equality predicate at bulk structure
creation time to be used for subsequent associative element retrieval.

Since none of the classical programming languages (C, Pascal, Modula-2, Cobol,
Fortran, PL/I) satisfies these elementary requirements, database programming
languages derived from these languages (Pascal/R \cite{Schm77}, Plain
\cite{W*81}, Modula-R \cite{Reim83}, DBPL \cite{MaSc89}, E
\cite{RiCa87}, CO$_2$ \cite{LRV88} etc.) had to be equipped with built-in bulk
data types, i.e. all polymorphic code and all higher-order functions are
hard-wired into the compiler and the run-time support.

On the other hand, modern programming languages like ML, Eiffel, Napier-88,
TRPL or Trellis/Owl \cite{S*86}, have type systems that may be sufficiently
generic to allow programmers to define their own bulk data types (lists, trees,
bags, sets, relations or multi-dimensional search structures) from scratch. In
fact, much work is devoted to the construction of re-usable generic library
code for such bulk types that can be later instantiated with specific type
parameters and access mechanisms \cite{Meyer90}.

Despite this progress towards add-on bulk types there is nevertheless much
interest in {\em type quarks} \cite{ART91}, i.e. specialized built-in building
blocks to be used in the construction of fully-fledged user-defined bulk types. 
This interest in the DBPL research community is motivated by additional
\e{operational demands} arising in typical data-intensive applications that may
not be adequately supported by the language primitives available in the
above-mentioned languages.

For example, built-in specialized index structures ({\em maps}) \cite{ART91}
are capable of capturing the essence of associative access to bulk data.
By equipping the abstract machine of persistent languages like PS-algol,
Napier-88 or Amber \cite{Card86} with map operations, highly \e{optimized
storage structures}, buffering strategies, clustering policies and garbage
collection mechanisms can be employed in the run-time system, exploiting the
regularity and size of map structures.

%An analogy with operating systems may clarify the idea behind maps: An
%operating system  with built-in ISAM file structures may provide better
%operational support to its application programs than operating systems
%that only offer plain file structures. Furthermore, ISAM files can be
%advantageous as building blocks for more complicated file or database
%structures. On the other hand, maps have to be regarded as
%``higher-level'' concepts since they are equipped, for example,  with a
%well-defined algebra and a tailored query notation. 

\subsubsection{Advanced Requirements}

Looking at the historic development of relational database programming languages
(from Pascal/R, Plain, RAPP, Modula/R to the current definition of DBPL), one
can perceive a trend towards increased built-in language support for advanced
requirements of data-intensive applications.

In addition to elementary access primitives (get, insert, delete, update and
scan) for bulk structures, many DBPLs recognize the need to provide
\e{iteration abstractions} like iterators \cite{LiGu86}, query expressions
\cite{BCD89}, set operators \cite{Merr84} or data deduction mechanisms in
rule-oriented systems \cite{NaTs89,ERMS91}. The rationale behind such
\e{declarative access specifications} is to provide concise and
optimizable notations for complex data selection and data construction
tasks.  For example, \e{set comprehensions} \cite{Bun90,Wadl90,ART91}
nicely generalize relational calculus queries by exploiting the
expressive power of computationally complete optimisable languages in a
functional framework.

As exemplified by selectors and constructors in DBPL (see
Sec.~\ref{predicates}), iteration abstraction does not need to be limited to
set-oriented bulk read access, but can be uniformly generalized to \e{bulk
updates}, \e{constraint definition} and (recursive) data derivation
\cite{ERMS91}.

\e{Query optimization} as found in traditional DBMSs and some database
programming languages aims at exploiting the algebraic properties of high-level
access abstractions to (dynamically) choose cost-effective implementations for
these abstractions, minimizing execution time, storage requirements or network
traffic. Query optimization has to be regarded as a prerequisite for successful
iteration abstraction in data-intensive applications: without effective
optimizations, programmers fall back to procedural solutions in order to attain
the efficiency required in standard database applications.

Finally, it should be noted that the use of bulk types in shared, multi-user
environments also calls for highly \e{concurrent access} and optimized
\e{recovery mechanisms} to be implemented for variables of these bulk types.
Again, database systems and relational DBMS exploit the ``declarativity'' of
access abstractions and hard-wired knowledge about the representation
structures for these purposes. (e.g., see \cite{ScMa90b} for a discussion of
the support for these advanced operational requirements in the DBPL system).


\section{Limitations of the Built-In Bulk Type Approach}
% -------------------------------------
\label{limitations}

There exist several operational database language implementations that
provide built-in linguistic and system support for various kinds of bulk
types. However, there are two main categories of arguments against the
way bulk types are supported: pragmatic arguments against \e{limitations
of extensibility} and conceptual arguments against a
\e{lack of methodology} in the construction of the support systems for bulk
type extensions.

In illustrating these arguments our DBPL experience supports that gained
by other well-engineered systems (like O$_2$, Ingres, Oracle, Iris,
Orion, Postgres, LDL) which also address advanced database issues (like
query optimization, concurrency control, recovery and client-server
architectures) in addition to database programming language issues (like
typing, scoping, binding, iteration).

The consequences of built-in bulk can only be fully understood by
considering the typical implementation strategy for a database
programming language, say DB-X.  The compiler (interpreter) for DB-X strongly
resembles a compiler (interpreter) for a traditional programming
language X, extended by scoping, binding and type compatibility rules
for built-in bulk type constructors and their built-in operations (e.g.
selection, natural join). To meet database requirements (persistence
management, access optimization, concurrency control), the code
generation phase maps composite DB-X constructs systematically to
lower-level constructs (abstract machine instructions, calls to support
routines) that provide the required DBMS functionality.

\begin{figure}
\centerline{\pictures{116mm}{123mm}{dbpl-components}{700}}
\caption{Built-in system support for relational bulk types in the DBPL
system} \label{dbpl-architecture}
\end{figure}

\begin{figure}
\centerline{\pictures{144mm}{53mm}{dbpl-sizes}{600}}
\caption{The relative complexity of bulk type implementation in DBPL}
\label{dbpl-sizes} \end{figure}

As a specific example of this approach, Fig.~\ref{dbpl-architecture}
shows the layers of the DBPL run-time support. Note that DBPL users only
access a tiny fraction of the functionality present in the run-time
support, namely the topmost (over-abstracted and pre-packaged) interface
of the DBPL system (below the bounding box in
Fig.~\ref{dbpl-architecture}). In fact, even that functionality is
hidden from the user since all calls to (polymorphic) run-time functions
are automatically generated by the DBPL compiler, guaranteeing type
safety and enforcing concurrency control and storage management
protocols required in a persistent multi-user environment.
Fig.~\ref{dbpl-sizes} gives an idea of the complexity of the various
tasks involved in the implementation of bulk data types in the DBPL
system. A comparison with the (optimizing) Sun Modula-2 system that
provides the basis for the DBPL system reveals a significant increase in
size of the run-time system.

The  built-in approach can be characterized by the following assumptions:
\begin{itemize}
\item All language implementation details are hidden from the application
programmer (How is a bulk type implemented? How is a query represented,
transformed and evaluated? How is serialisability achieved?)

\item  The efficient implementation of the database language depends crucially
on detailed language design time knowledge about permissible language
constructs: Which (bulk) types exist? What is the syntax of the query
(sub-)language? What are the algebraic properties of the built-in language
primitives like equality predicates, comparison operations, aggregate functions?

\item Significant optimizations are based on a careful case-analysis within the
available language space. Examples are optimizations for special cases like flat
relations, unordered collections, read-only transactions or one variable
selection queries.
\end{itemize}

Some of these assumptions are in conflict with the programming language
principles of orthogonality and free extensibility. Accordingly, much
work in the database community aims at \e{extending database technology}
to support, e.g.
\begin{itemize}
\item new aggregate functions in queries,
\item new operations within queries (e.g. test for intersection of geometric
objects), 
\item new bulk structures (e.g. ordered sequences),
\item new operations in the target list of query expressions,
\item new storage structures,
\item new join algorithms, etc.
\end{itemize}

Despite progress made with extensible database systems (for a recent
survey see \cite{Ston90}), none of today's database programming language
implementations provides adequate support for the above extensions.

Take for example an extension of DBPL by ordered lists. Although this
could be achieved by rather limited local changes to an existing database
programming language implementation, this can hardly be done by ``ordinary''
application programmers. The first problem is the lack of polymorphism.
It is therefore necessary to write different code for lists of persons,
employees, integers, etc. (instead, the type variable \kw{Value} in the
following code fragment should be universally quantified):  
\begin{xple}
\k{const} nil = 0
\k{type} 
  Value = ... (* element type, e.g. String *)
  ID = CARDINAL;
  Item = \k{record} id: ID; val: Value; next:ID \k{end}
  Items = \k{relation} id \k{of} Item;
  List = \k{record} items: Items; head, nextIndex: ID \k{end}

\k{procedure} new(\k{var} list: List); \k{begin} list:= List\{\{\}, nil, nil\} \k{end} new;

\k{procedure} cons(val: Value; \k{var} list: List);
\k{begin} 
  \k{with} list \k{do} INC(nextindex); items:+ Item\{nextIndex, val, head\}; head:= nextindex
  \k{end}
\k{end} cons;
\end{xple}
Obviously, relations do not provide the ``right'' abstraction level at
which to build list structures, since the above example exploits
relations merely as a typed homogeneous store indexed by integer
``addresses''. Similarly, relational calculus expressions are not a
suitable basis to solve list processing tasks (e.g. to select a sublist
of all values satisfying a boolean predicate).

It should be noted that this inadequacy is not a deficiency of DBPL. 
It can be also found in polymorphic database languages like Machiavelli
or Galileo and all commercially available relational database systems,
since their bulk expressions do not scale up to user-defined bulk
structures.  Providing lists as built-in bulk structures (as  done in
E, O$_2$ and other object-oriented databases) does not overcome the
general lack of extensiblilty, e.g., it may still be impossible to
define adequately multisets or to represent geographic data (planes,
line segments etc.).

The price for the high level of abstraction and safety in DBPL programs
is the inability to re-use, override, reconfigure or adapt the DBPL
system code for purposes other than those foreseen at language design
time. For example, the implementation of list structures should be
performed preferably at the abstraction level of the layer CRDS (see
Fig.~\ref{dbpl-architecture}) {\em within the DBPL system}, utilizing
tuple-identifiers and tuples as provided by the layer SMS, inheriting
SMS's concurrency and recovery mechanisms without change. Limited
modifications of the generic query evaluation and optimization layer
CPMS would suffice to generalize access expressions to ordered bulk
types. No modifications at all seem to be required to have in addition
optimized fixed-point queries over lists by re-using the layer PSMS.

To summarize, the above problems with extensions stem from the fact that
traditionally built-in bulk types and query abstractions are only
intended to directly support very specific \e{modelling} requirements
and therefore are not designed to be used in the \e{implementation} of
other generic data structures.

In our experience the main arguments against the traditional built-in
approach to bulk types can be summarized as follows:
\begin{description}
\item[Reusability:] It is difficult (often impossible) to safely re-use
existing system components of the built-in system environment  (buffer manager,
polymorphic index structures, wait-for-graph management, clustering algorithms
etc.).

\item[Scalability:] It is typically not possible to eliminate unnecessary
functionality from the built-in system environment (concurrency control or
recovery  actions, components for recursive query evaluation).

\item[Adaptability:] Even if one has access to the implementations of the
built-in bulk structures, modifications of these components (e.g. replacing
B-Tree index structures by hashed structures or replacing a garbage collection
algorithm) have to be performed in a ``lower level'' programming language with
obvious negative consequences on the overall system correctness and long-term
system evolution. 
\end{description}

The apparent resistance of current DBPL \e{system implementations}
against DBPL \e{language extensions} gives rise to the
following important research question. Can one isolate
``generic'' language constructs that aid in the systematic
construction of flexible DBPL processors and meet more than just a
limited set of structures and algorithms foreseen at language design
time? The second part of this paper addresses the relationship
between DBPL language and system extensibility.


% -------------------------------------------------------------------
\section{From Built-In To Add-On Bulk Types}

\label{add-on}
In the following subsections we illustrate how well-understood bulk structures
(sets and relations) can be provided as add-ons without impairing their
linguistic quality (syntax), expressiveness (semantics) or optimizability.

As a concrete notation to present the add-on approach, we utilize Quest
\cite{Card89}, a functional language with imperative features, strict
evaluation strategies, explicit type quantification and subtyping rules
inductively defined over all type constructions. Although Quest lacks
important operational features required in database programming,
e.g.~persistence management with incremental loading strategies,
primitives for concurrency control and recovery, Quest turns out to be a
promising platform to investigate the relationship between language and
system extensibility for bulk types since it incorporates advanced
abstraction mechanisms required in bulk type definition and usage.

The main purpose of this section is to introduce some of the more
advanced language concepts that play a central r\^ole in extensible
languages and to convince the reader that many implementation and
optimization strategies employed for built-in bulk structures can be
carried forward to add-on solutions. Important issues of extensibility
and reusability are deferred until section~\ref{iterators}.

A discussion of the \e{fundamental language mechanisms} (typing,
binding, scoping, polymorphism, higher-order functions, type operators,
type inference) employed in the programming examples can be found in
\cite{Card89}. A more detailed study of these language mechanisms in the
context of database application systems is presented in \cite{MaSc91}.


\subsection{Add-On Relation Types}
\label{sets-add-on}

The following examples present an application programmer's view of
(add-on) relation types and simple relational operations in Quest:
\begin{xple}
\k{Let} Person = \k{Tuple} name :String  age :Int \k{end}
\k{Let} Student = \k{Tuple} name :String  age, semester :Int \k{end}
\k{let} sameName (p1, p2 :Person) :Bool = p1.name == p2.name
\k{let} persons = set.new(:Person sameName)
\k{let} students = set.new(:Student sameName)
\end{xple}

The first two lines introduce name -- type bindings, defining the types
\kw{Person} and \kw{Student} as tuple types; the third line defines
the function \kw{sameName} that tests whether two tuples of type
\kw{Person} have the same value in their name attribute. This function
is then used to define the key constraint for two newly created relation
variables \kw{persons} and \kw{students} with elements of type
\kw{Person} and \kw{Student}, respectively.  Since relations are
understood as keyed sets (like in DBPL), all operations on relations are
imported from a module \kw{set} and the dot-notation is used to name
individual operations from this module. Here are some examples for
further set operations:

\begin{xple}
set.insert(persons \k{tuple} \k{let} name = "Peter" \k{let} age = 32 \k{end})
\k{if} set.member(students \k{tuple} "Peter" 23 5 \k{end}) \k{then} ... \k{end}
\end{xple}

The Quest type checker enforces the obvious constraints on
values of relation types: Only values of subtypes of \kw{Person} can be
inserted into a relation of \kw{Persons}; elements of a \kw{Persons}
relation have type \kw{Person}; key definitions for relations of
\kw{Person}s have to involve \kw{Person} tuples; etc.  Since Quest does
not have built-in ``knowledge'' about relation types, there has to be a
way to add-on such type constraints in a systematic way. For the module
\kw{set} the necessary information is defined by the interface
definition \kw{Set} that is discussed below.

The operations \kw{empty, get} and \kw{rest} constitute basic mechanisms
to access individual elements of a set, one after the other. For a
non-empty set, the operation \kw{get} chooses an arbitrary element of
the set while \kw{rest} yields the set without the element returned by
\kw{get}.
\begin{xple}
\k{if} not(set.empty(persons)) \k{then} 
  \k{let} aPerson = set.get(persons)
  \k{let} otherPersons = set.rest(persons)
\k{end}
\end{xple} 
A more interesting task is to capture bulk operations on sets and relations:
\begin{xple}
set.forEach(students \k{fun}(s:Student)
    print("Name = " $<>$ s.name $<>$ " Age = " conv.int(s.age) $<>$ "\verb$\$n"))

\k{let} oldStudents():Students = set.select(students \k{fun}(s:Student) s.age$>$28)

set.join(\k{let} select(s:Student p:Person) = \k{tuple} p.name s.semester \k{end}
    \k{let} from1 = students
    \k{let} from2 = persons
    \k{let} where(s:Student p:Person) = s.name == p.name)

set.forEach(students \k{fun}(s:Student)
   set.forEach(persons \k{fun}(p:Person)
       \k{if} s.name == p.name \k{then} print(p.name $<>$ " " $<>$ s.name) \k{end}))

set.some(oldStudents() \k{fun}(s:Student) \{s.semester$>$5\}  $\wedge$ \{s.name = "Peter"\})

\k{let} maxSemester = set.reduce(oldStudents() \{\k{fun}(s:Student) s.semester\} int.max)
\end{xple}

The above programming examples show an iteration over the relation
\kw{students}, the definition of a view \kw{oldStudents}, the join between
two relations, a nested iteration loop, the application of an
existential quantifier and the computation of an aggregate function
(highest semester of all old \kw{students}). Note that the scoping rules
for the bound variables \kw{s} and \kw{p} support a programming style
that is very close to built-in iteration constructs.

It goes beyond the scope of this paper to demonstrate that the Quest
implementations of these bulk types (underlying the module \kw{set})
could be based on B-trees, hash tables, bit sets or a combination of
these data structures which could be even redefined dynamically via a
special ``DBA'' interface.

On the other hand, the following interface \kw{Set} of the module
\kw{set} contains all the information required by the Quest compiler to
check the syntax and type rules for add-on set types.

\begin{xple}\label{set-interface}
\k{interface} Set
\k{export}
  T ::\k{ALL}(E ::TYPE) TYPE
  new(E ::TYPE equal(:E :E):Bool) :T(E)
  member(E ::TYPE set :T(E) element :E) :Bool
  insert(E ::TYPE set :T(E) element :E) :Ok

  empty(E ::TYPE set :T(E)) :Bool
  get(E ::TYPE set :T(E)) :E
  rest(E ::TYPE set :T(E)) :T(E)

  forEach(E ::TYPE set :T(E) stmt(:E):Ok) :Ok
  select(E ::TYPE set :T(E) pred(:E):Bool) :T(E)
  join(E1,E2,F ::TYPE  select(:E1 :E2):F  
       from1 :T(E1) from2 :T(E2)  where(:E1 :E2):Bool) :T(F)
  some(E ::TYPE set :T(E) pred(:E):Bool) :Bool
\k{end};
\end{xple}

The first declaration in this interface defines an abstract type
constructor \kw{T} (identified as \kw{set.T} from outside of this
interface) that can be instantiated with an arbitrary type \kw{E} of
kind \kw{TYPE}. For example, a \kw{set.T(Student)} is the type of a set
of students, while \kw{set.T(Person)} denotes the type of a set of
persons. \kw{Set.new} is the only functions that creates values of type
\kw{set.T(E)} from scratch. It takes a boolean equality function 
\kw{equal} between
pairs of elements of type \kw{E} as a parameter. This function defines
the primary key constraint that has to be enforced at run-time by the
relation implementation.

Since all functions of the interface \kw{Set} work uniformly over sets
of any element type \kw{E}, all these polymorphic functions have a
formal type parameter \kw{E} (of kind \kw{TYPE}).  By using the name of
a type parameter  in the type definiton of more than one arguments of a
function  (e.g. \kw{E ::TYPE set :T(E) element :E} for \kw{insert}),
one can express correctly the constraint that only values of type
\kw{E} can be inserted into a set of type \kw{set.T(E)}. Similar
constraints hold for the functions \kw{member, get} and \kw{rest}.
Finally, the signatures of the function \kw{forEach} demonstrates how
to define functions that correspond to composite statements (e.g.
\k{for each ... do}) in traditional programming languages.

It should be noted that the implementation of bulk types and high-level
query abstractions in the add-on approach is performed in the \e{same
language} that is also used for database application programming. This
distinguishes the add-on approach from extensible database systems (like
EXODUS, Genesis, Starburst or Iris; for a survey see
\cite{Ston90}\nocite{Bat*88}) that have to resort to lower-level
languages like C or C++ to implement new data structures. In particular,
the implementation of add-on bulk types has to respect all typing rules
and language constraints that pertain to application programs. The
uniformity of system and application programming is essential for the
smooth ``factoring-out'' of code from application programs into the
application environment in case its functionality is found useful for a
broader user community. Vice versa, it is often necessary to import
generic code from the environment and to specialize or extend it
according to application-specific requirements. Finally, due to this
uniformity there is no need to define (ad hoc) interface rules between
internal and external data representations or internal and external
control structures.

\subsection{Classifying General Data Structures}
\label{general-BDT}

Being aware of the structural and operational richness of
state-of-the-art programming language technology, an immediate objection
to the add-on bulk type approach is the apparent threat of not being
able to cope with the implied system add-ons required, e.g., for query
optimization. As already mentioned in section~\ref{limitations},
optimizations in database systems make heavy use of algebraic or
structural peculiarities (e.g., commutativity, associativity,
homogeneity, ``flatness'') of the data structures and operators offered
by the underlying data model.

Therefore, a promising research direction towards generic optimizations
for generalized data models is to isolate such ``useful'' properties of
generalized data structures and operations and to identify partitions in
a generalized bulk type and operation space for which \e{systematic}
implementation and optimization strategies can be devised which exploit
these specific properties.

For example, the three operations \kw{empty}, \kw{get} and \kw{rest}
in the \kw{Set} interface (on p.~\pageref{set-interface}) seem to capture a
characteristic property of a large class of bulk structures, namely the
ability to (sequentially) enumerate their elements. Indeed, as discussed in
more detail in the next section, it is possible to define a rich declarative
query language based on these access primitives.

Other researchers are investigating similar characterizations of bulk
data structures based on algebraic properties of their inductively
defined constructor functions (Monads \cite{Wadl90}, Ringads
\cite{Trind91}). In a similar spirit, \cite{BTBN91} shows that the
expressive power of the relational algebra and of a complex object
algebra with or without powerset can also be characterized by the
concept of \e{structural recursion} on sets extended by very few
programming language constructs (like tupling or conditionals). Early
work on the systematic mapping from recursively defined data structures
and their associated operations down to relational structures and
operations (in the context of Pascal/R) can be found in \cite{Lame84}.

Formal software specification techniques may be another source for the
characterization of relevant subspaces amenable to global optimizations.
It is interesting to note that there is ongoing work to establish an
integrated framework incorporating both, aspects of logic databases, as
well as equational specifications of algebraic data types \cite{Beer91}.

As outlined in the next section, there is an important difference
between the idea of (conceptual) sublanguages in the add-on approach and
the traditional notion of built-in bulk type constructors with their
associated query notations. This difference results from the fact that
there is no artificial syntactic or linguistic barrier between
optimizable query notations and non-optimizable general purpose
programming constructs. Therefore, there is no need to revise the
language definition, the language processor or existing application
programs whenever advances in database technology enable the handling or
optimization of more general data structures or query constructs.

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

\section{Uniform Iteration Abstractions}
\label{iterators}

This section refines the approach outlined in section~\ref{general-BDT}
and captures the commonalities of a large class of bulk types by a small
common set of access primitives. We also demonstrate how a very
expressive query language can be systematically constructed from these
access primitives. Finally, we indicate our approach to methodically
achieving efficient implementations for this extended class of bulk
structures.

In Tycoon we seek to explore the potential of an approach which starts
with a type-safe core language supporting only low-level
structures (e.g. arrays or inductively defined data types) and basic
mechanisms to control mutability, sharing, clustering and persistence of
these structures. Application programmers typically do not utilize this
built-in primitive functionality but make heavy use of problem-oriented
bulk types (sets, relations, lists, priority queues etc.) and
\e{standardized} iteration abstractions over these bulk structures
already provided by their programming environment.

To motivate the potential of such standardized iteration abstractions,
it may be helpful to compare the query that, for example, selects the
top-ten managers according to the sales of all suppliers in their
company with the conceptually similar query that computes the ten
documents in a directory that contain the most mis-spelled words
according to a given dictionary of correct words:

\begin{xple}
\k{let} companySales(c:Company):Real = real.sumOf(SFW(
     \k{let} select(s:Supplier):Real = turnover(s)
     \k{let} from = suppliers 
     \k{let} where(s:Supplier):Bool = worksFor(s c)))
\k{let} topTenManagers = selectFirst(10 
   sort(managers \k{fun}(m:Manager):Real companySales(m.company) \{$real.>=$\}))

\k{let} errorCount(t:TextFile):Int = size(SFW(
     \k{let} select(s:Supplier) = s
     \k{let} from = text.wordsOf(t) 
     \k{let} where(s:String):Bool = not(member(s spellDictionary))))
\k{let} topTenFiles = selectFirst(10 
   sort(documents errorCount \{$int.>=$\}))
\end{xple}

Without going into details, the remarkable similarity between these two
queries is due to the availability of ``generic'' declarative query
constructs. For example, the bulk operations \kw{add, count, select ..
from .. where, selectFirst, member}, and \kw{sort} are higher-order
generic functions (defined in a Tycoon module, see
Appendix~\ref{iter-interface}) that are uniformly applicable not only to
bulk types of different element types (\kw{Strings} or \kw{Suppliers})
but also to a wide range of bulk types (\kw{Relations} or
\kw{Dictionaries}).

Some of the bulk types utilized in the examples are so common (like text
files, sequences of words, ordered lists, sets and relations) that they
are already made available in the standard Tycoon environment. New bulk
structures can be either defined from scratch (i.e. by utilizing the
primitive built-in Tycoon types like tuples, variants, functions and
fixed-sized arrays), or their implementation can be based on existing
bulk types like lists or hashed dictionaries.

Whereas the definition of bulk types and iteration abstractions is to be
regarded as a classical system programming task, application programmers
typically only need to instantiate or specialize these services by appropriate
type-specific information, e.g. to define application-specific bulk variables
like \kw{Suppliers, Managers, Documents} and bulk functions or associations
between them like \kw{turnover, worksFor} or \kw{wordsOf} and \kw{errorCount}.

As should be clear from the examples above, our main goal is to
factor-out repeating program control patterns from specific applications
into the language environment. The feasibility of this approach
depends crucially on the ability to isolate highly generic access
abstractions (captured by higher-order functions) that can be applied
uniformly even to highly \e{specialized bulk structures} (represented by
abstract types or abstract parameterized type constructors).


\subsection{An Elementary Bulk Type Interface}

\label{seq-iter}
As explained in section~\ref{general-BDT}, it is highly
desirable to find commonalities shared by all bulk structures that can
provide the basis for substantial system support required in a database
scenario.  The following type definition abstractly defines a basic
\e{protocol} for a \e{sequential enumeration} of the elements of an
arbitrary homogeneous bulk structure:

\begin{xple}
\k{Let Rec} IterRep(E ::TYPE) ::TYPE = \k{Tuple} 
   empty() :Bool
   get() :E
   rest() :IterRep(E)
\k{end}
\end{xple}

The recursively defined type constructor \kw{IterRep} is parameterized
by the element type \kw{E} of the iteration. For example,
\kw{IterRep(Int)} is the type of iterations over integer numbers while
\kw{IterRep(Person)} is the type of iterations over tuples of type
\kw{Person}. An \kw{IterRep} for a given element type \kw{E} is defined
as a tuple with the three named components \kw{empty, get} and \kw{rest}
which are parameterless functions. The function \kw{empty} yields \kw{true}
if the iteration contains zero elements. The other functions are only
defined for non-empty iterations and split an iteration into two parts:
\kw{get()} is a value of the iteration element type and \kw{rest()} is
again an iteration of type \kw{IterRep(E)}, however, without the value
returned by \kw{get()}.

In other words, any structure for which a value of type \kw{IterRep} can
be constructed, has ``bulk'' character. Intuitively, this can be
understood by the fact that if \kw{x} is of type \kw{IterRep(E)} then
the three function components (\kw{x.empty, x.get, x.rest}) provide a
mapping from \kw{x} to (possibly infinite) homogeneous lists:
\begin{xple}
[x.get()  x.rest().get()  x.rest().rest().get()  \ldots]
\end{xple}

This can be exemplified by the polymorphic function \kw{elements} that
maps an array \kw{arr} of an arbitrary element type \kw{E} to a
recursively defined value of type \kw{IterRep(E)}, i.e. arrays are bulk
types because one can sequentially enumerate their elements;

\begin{xple}
\k{let} elements(E ::TYPE arr :Array(E)) :IterRep(E) =
   \k{begin}
      \k{let rec} elementsFrom(index :Int) :IterRep(E) =
            \k{tuple} 
              \k{let} empty() :Bool = index $>$ size(arr)
              \k{let} get() :E = arr [index]
              \k{let} rest() :IterRep(E) = elementsFrom(index+1)
            \k{end}
      elementsFrom(1)
   \k{end}  
\end{xple}

The definition of type \kw{IterRep} does not only characterize
``stored'' bulk types like lists, arrays, sets, relations, dictionaries
or files, but it also captures related abstractions like predicatively
defined subcollections (views), derived collections (e.g. grandparents
or ancestors derived from parents), streams, pipes or channels in
operating systems or simple enumerations or intervals (e.g. ``all
numbers in the range from 1 to 999'').


\subsection{Generalized Iteration Abstractions}

Based on elementary bulk access defined by the standardized protocol of
abstract sequential access, we can now define higher-level, declarative
\e{iteration abstractions}. These abstractions can be either
algebra-like operations (union, difference, selection, cartesian product
or join) or calculus-like expressions involving (nested) existentially
or universally quantified expressions.  Technically speaking, iteration
abstractions do not work directly on bulk structures but on values of
type \kw{IterRep} derived from bulk structures:
\pagebreak

\begin{xple}
\k{let} persons :Array(Person) = ...
\k{let} oldPersons :Array(Person) = ...
\k{let} allPersons = iter.append(elements(persons) elements(oldPersons))
iter.join(
   \k{let} select(p1,p2:Person) = \k{tuple} p1.name p1.age p2.age \k{end}
   \k{let} from1 = elements(persons)
   \k{let} from2 = elements(oldPersons)
   \k{let} where(p1,p2:Person) = \{p1.name == p2.name\} $\wedge$ \{p1.age $>$ p2.age\}) 
\end{xple}

What are the operations we expect to be defined over general bulk structures?
These operations should allow (see also Appendix~\ref{iter-interface})
\begin{itemize}
\item the mapping of iterations to iterations of the same or another element
type  (e.g. \kw{map, select, select .. from .. where});

\item the quantification over bulk structures by reducing iterations to
values of the primitive types (e.g. \kw{size, reduce, fold, some, all});

\item the combination of iterations into a single new iteration (e.g.
\kw{append});

\item the iteration with side-effects over each element of an iteration (e.g.
\kw{forEach, forDo, untilDo, whileDo});

\item the ``associative'' selection of \e{individual} elements of a
iterations based on its properties expressed by a predicate analogous to
the ``de-setting'' operation, as found, for example, in Adaplex
\cite{SFL83} or DBPL (\kw{the, theOnly, theFirst, theLast}).
\end{itemize}

Similar iteration abstractions for specialized bulk types are discussed,
for example, in \cite{OBBT89,AtMo88,SDD*86}. Note that the
module \kw{iter} in the Tycoon environment provides a very general and
highly reusable functionality. For example, suppose an application has
to operate on stacks of rectangles and lists of line segments, the
operations in the module \kw{iter} provide a building block for a
declarative geometric ``query language'', e.g. to formulate a query to
find the topmost rectangle on a stack that has the maximum number of
intersections with a given set of line segments.

Even if the underlying data structures only provide simple sequential access
and no type-specific information, the nesting of iteration abstractions and
the existence of binary operations on bulk structures gives rise to
\e{alternative} evaluation strategies for a given ``query''. In the spirit of
database query optimizers (or loop optimization techniques in
programming languages) important optimizations can be applied to these
general data structures (filter promotion, quantifier exchange, constant
propagation, memorizing of repeating subqueries etc.). At the same time
it is possible to provide optimized implementations for join operations
(e.g. by sort and merge) without perturbating the declarative ``query''
style in application programs.

To our understanding, the main reason why none of the existing programming
languages provides these optimizations for add-on iteration abstractions lies
in the lack of an adequate \e{implementation technology} for such \e{global},
run-time optimizations: most optimizations rely on information about a
complete query expression (including selection predicates and user-defined
functions) or even on parameter values that are only determined at run-time.
Therefore, traditional (local, incremental) compilation technologies fall
short for this particular class of problems.



\subsection{Refined Bulk Type Interfaces}

The sequential bulk type interface presented in section~\ref{seq-iter}
can be used as a good starting point to study refined bulk type
interfaces with particular support for bulk optimizations. Our
experience with the query optimization problem in Pascal/R, Modula/R and
DBPL indicates that the \kw{IterRep} protocol definition needs to be
extended by three kinds of information to enable optimizations
that are competitive with today's commercially available systems.

\begin{itemize}
\item Information about alternative \e{access support} (sequential
access, positionally indexed access, value indexed access, ordered
access (for range queries), hierarchical access)\footnote{In
\cite{MaSc91}, these access mechanisms are characterized by type
constructors like it was done for the sequential case in
section~\ref{seq-iter}. This approach also allows to capture the
commonalities between access mechanisms by an (inferred) subtype
relationship.}. This implies that an individual bulk structure may
possess \e{multiple} access paths with substantially different
operational behaviour and that even for a single declarative iteration
abstraction a choice between these implementations becomes possible.

\item Cost functions for access mechanisms (computing time, number of
data elements visited) to guide the query transformation process.

\item Statistical information on the bulk structure cardinality, the
distribution of attribute values or the correlation between attribute
values. Some of this information is (conceptually) derivable from
knowledge about the application domain (e.g. the maximum number of
students in a lecture, the set of possible \kw{age} attribute values,
data dependencies between zip codes and city names), others have to be
computed at run-time. 

\end{itemize}

Technically, this information could be cast into an extended
\kw{IterRep} type specification that has to be met by implementors of add-on
bulk types. Since query optimization is an ``optional'' feature, it is
appropriate to allow ``do not know'' or default values for these
additional iterator attributes (as it is done in extensible query
optimizers). System experimentation is underway to understand how to
distribute this information systematically over the Tycoon environment
while maintaining modularity and extensibility.

We do not want to leave this discussion without mentioning the problems
arising from destructive updates (e.g., within \kw{forDo} loops or as
side-effects of user-defined functions defining selection expressions).
In \cite{MOS91} we propose extensions of polymorphic type systems to
capture not only structural aspects of data values, but also information
about the \e{locality} of (mutable) data objects with identity. This
allows one to utilize type checking and type inference technology to
reason about the scope of side-effects and to identify referentially
transparent (``purely functional'') subexpressions that permit effective
query rewriting techniques.


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

\section{Research Issues In Generic Bulk Data Support}

The main purpose of this paper is to discuss the rather complex
interaction between language and system considerations involved in bulk
type definition and support. We identify \e{elementary} and \e{advanced}
requirements for bulk types, each of which can be satisfied either by
specialized built-in language mechanisms or generalized open system
architectures.

Recent advances towards expressive type systems and highly effective compilation
schemes may allow the \e{elementary} requirements for bulk data storage
(including persistence management) to be satisfied without resorting to the
built-in approach. Given state-of-the-art language technology, a high
investment in built-in bulk types (as exemplified by DBPL)  can only be
justified by the support it provides for \e{advanced} requirements like
generalized associative queries or integrity constraint management in
multi-user environments. We finally reported on our current work that aims to
satisfy even these advanced requirements by user-definable add-ons to generic
core languages focussing on linguistic and architectural aspects, since
important component technology seems to be already available in extensible
database systems.


Clearly there remain many open research issues for further theoretical
and experimental work. What is a suitable formal framework for data
models supporting generalized bulk types?  Is it necessary to equip
DBPLs with specific {\em syntactic} support for a concise notation of
bulk data manipulations (e.g. list comprehensions)? Is there a taxonomy
for general optimization strategies (algebraic vs. operational, static
vs. dynamic, deterministic vs. probabilistic)? Where should the
meta-information required for optimizations come from (static program
analysis, program annotations via pragmas, access to program
specifications, compile-time or run-time reflection)? Can standardized
iteration abstractions be exploited for program verification tasks?

Finally, one could speculate that the experience gained in supporting
add-on bulk types may be relevant also for other kinds of substantial
language extensions such as the support of ``declarative'' constraint
management in the presence of destructive updates.

\section*{Acknowledgements}

The authors would like to thank Malcolm Atkinson, Catrieel Beeri and
Peter Buneman for stimulating comments on this work and the referees
for their constructive remarks on an earlier version of this paper that
helped in streamlining the flow of argumentation.

\bibliographystyle{florian}
\bibliography{../bib/florian}
\newpage
\appendix
\section{Iteration Abstractions for Add-On Bulk Types}

The following fragment taken from a prototypical Tycoon iterator
interface gives some examples of useful iteration abstractions that are
uniformly applicable to instances of a wide range of bulk types (see
Sec.~\ref{iterators}).

\label{iter-interface} 
{\small
\begin{xple}
\k{interface} Iter
\k{import} :IterRep 
\k{export}
  \k{Def} T = IterRep\verb$_$T
  error :Exception(Ok)
    (* Raised if any of the following operations cannot be carried out. *)

  select(E ::TYPE iter :T(E) p(:E):Bool) :T(E)
    (* Return an iteration over the elements in iter that fulfil p. *)
  append(E ::TYPE first, second :T(E)) :T(E)
    (* Return an iteration over each e in first and then each e in second. *)
  map(E, F ::TYPE iter :T(E) f(:E):F) :T(F)
    (* Return an iteration over f(e) for each e in iter. *)
  size(E ::TYPE iter :T(E)) :Int
    (* Return the number of elements of an iteration. *)
  fold(E, F ::TYPE iter :T(E) f(:E):F g(:F :F):F) :F 
    (* Reduce f(e) for each e in iter by g. Raise error if iter is empty. *)
  reduce(E ::TYPE iter :T(E) g(:E :E):E) :E 
    (* Reduce iter by g. Raise error if empty. *)
  flatten(E ::TYPE iter :T(T(E))) :T(E)
    (* Return an iteration over each e2 in each e1 in iter. *)
  unnest(E, F ::TYPE iter :T(E) f(:E) :T(F)) :T(F)
    (* flatten(map(iter f)). *)
  some, all(E ::TYPE iter :T(E) p(:E):Bool) :Bool
    (* Does p(e) hold for some element (resp. all elements) in iter? *)
  join(E1,E2,F ::TYPE  select(:E1 :E2):F  
       from1 :T(E1) from2 :T(E2)  where(:E1 :E2):Bool) :T(F)
    (* Join from1 with from2. *)
  any(E ::TYPE iter :T(E) p(:E):Bool) :E
    (* Choose any element in iter that fulfils p. 
       Raise error if no such element exists. *)
  selectFirst(E ::TYPE n :Int iter :T(E)) :T(E)
    (* Return first min\{n,size(iter)\} elements of iter. *)
  forEach(E ::TYPE iter :T(E) statement(:E):Ok) :Ok
    (* Perform statement for each e in iter. *)
  forDo, untilDo, whileDo
      (E ::TYPE iter :T(E) p(:E):Bool statement(:E):Ok) :Ok
    (* Equivalent to 
       forEach(select(iter p))
       forEach(selectUpto(iter p))
       forEach(selectBefore(iter fun(e:E) not(p(e))))  *)
  selectBefore, selectAfter, selectUpto, selectStartingWith
      (E ::TYPE iter :T(E) p(:E):Bool) :T(E)
    (* Let i be the index of the first element in iter that fulfils p.
       Return an iteration over all elements with an index j such that
       j$<$i, j$>$i, j$<=$i, j$>=$i *)
  sort(E ::TYPE iter :T(E) order(:E :E):Int) :T(E)
    (* Order has to define a linear order on values of type E. *)
\k{end}
\end{xple}
}

\newpage
%\section*{Keywords}

%\begin{xple}
%Associative access
%Bulk types
%DBPL
%Declarativity
%Extensibility
%Iterator
%Iteration abstraction
%Map
%Query Optimization
%Tycoon
%\end{xple}

\end{document}