% File:    dbpl3.tex
% Author:  F. Matthes
% Date:    18-apr-1997
% Title:   F2 Book: Bulk Types: Built-In vs. Add-On (Synopsis)
%
\documentstyle{clmult01}

\pagestyle{myheadings}

\def\descriptionlabel#1{\hspace\labelsep \bf #1\hfil}

\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}}}

\title{Chapter 1.4.2\\Bulk Types: Built-In or Add-On?}

\author{Florian Matthes \and Joachim W. Schmidt}

\institute{Technical University Hamburg-Harburg\\
Harburger Schlo{\ss}stra{\ss}e 20\\
D-21071 Hamburg, Germany}

\begin{document}

\authorrunning{Florian~Matthes \and Joachim~W.~Schmidt}
\titlerunning{Bulk Types: Built-In or Add-On?}

\maketitle

\abstract{This text is a summary of \cite{MaSc91b}.}

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 tat bulk types should be realized
exclusively as user-definable add-s 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.

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{Schm77a,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{Schm77a,Reim83,MaSc89}. On the other
hand it reports on the design rationale for
Tycoon\footnote{Tycoon: Typed Communicatng Objects in Open Environments.}, a
language and system environment with add- bulk types.
The issue of built-in vs. add- 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.

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. 


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 sumarize below. This discussion is valid for both, built-in as
well as add- bulk types, and, therefore, also establishes a framework
for an investigation of 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.
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, 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.

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 serializability 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 \cite{Ston90}, none of today's database programming language
implementations provides adequate support for the above extensions.

The paper outlines the initial design of the Tycoon bulk type 
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.

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.


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?

\begin{acknowledgement}
This work was supported by the European Commission under
ESPRIT BRA contract \#~3070 (FIDE).
\end{acknowledgement}

\small
\bibliographystyle{plain}
\bibliography{../dbis-macros,../florian}

\end{document}
