% File:    kiev90-4.tex
% Author:  F. Matthes
% Date:    11.2.1991
%
\section{An Exercise in Generic Collections and \mbox{Iterators}}
\label{Streams}

An essential element of DBMS functionality is to provide generic bulk
data structures \cite{ART90} and high-level query languages to
efficiently access and manipulate substructures of bulk structures.

In this section we first sketch how to adequately capture this specific
externally visible functionality of a DBMS by means of generalized
collection types and a standardized protocol expressed via higher-order
functions. In contrast to hard-wired services provided by conventional
DBMSs and database programming languages, this approach is
\e{intrinsically extensible}. The second subsection demonstrates how
well-known specialized implementations of set and relation structures
can be introduced systematically as subtypes of the externally visible
generalized collection type.  In the last subsection we briefly
illustrate how important issues like data independence and query
optimization can be achieved in such a generalized scenario.

Other authors already investigate the problem of defining generic,
reusable data structures \cite{Meyer88,Meyer90,S*86,CoMa84,GoRo83} or
aim at isolating a taxonomy of bulk data types \cite{StSh91,ART91}.
However, their work does not cover dynamic reconfiguration and global
optimization issues, topics we consider vital for reconciling
declarative data modelling with efficient data access.  Most of the
ideas expressed in this and the following section are based on our
practical experience in the construction and utilization of set- and
predicate- oriented database programming languages (e.g. see
\cite{S*88,ScMa90}).



\subsection{Generalized Protocols}

An important task in the construction of Database Application Systems
(as in any non-trivial system environment) is the specification of
protocols that regulate the division of labour between clients and
servers of a particular functionality.  Analysing existing approaches to
interface definition in operating systems, programming languages and
database systems, one can distinguish the following three main styles:

\begin{description}
\item[Operating system] services or other application environment
services (e.g. window management routines) are accessible through
special-purpose interfaces realized by \e{parameterized function calls}.
Much progress was made (see Unix, Mach) in achieving simplified call
interfaces by collapsing traditionally separated functionality (e.g.
terminal input and output, local disk access, remote disk access,
interprocess communication mechanisms) to a small set of uniform
primitives (e.g., open, close, read, write).
 
\item[Programming languages] (or more specialized languages like
\e{Postscript}) can also be viewed as mechanisms to specify a
recognized computational functionality. In contrast to the above simple
parameterized interfaces, programming language interfaces are extremely
generic and allow to express dependencies between individual operations,
to exploit contextual information during program interpretation, and
even to extend the functionality of a programming language interface by
introducing additional declarations.

\item[Database systems] traditionally combine the
previous two approaches by providing several special-purpose interfaces.
Examples are the DBMS facilities for schema definition, physical data
description, ad-hoc queries, embedded queries etc.

Much of the power of a relational interface comes from its
\e{over-abstraction}: Relational DBMSs are prepared to accept from their
clients predicates in some first-order language together with a
specialization that indicates whether it is to serve as a query
predicate, a view definition, an invariant or a trigger condition.
Other DBMS interfaces, e.g. those for schema declaration or access
support, provide their tailor-made functionality at a similar level of
abstraction.
\end{description}

According to our understanding of Database Application Systems as
expressed in the introduction of this paper, we would like to be able to
combine these three approaches in a single, unbiased language framework.
As a test case we will examine in this section the definition of a
unified, calculus-based ``query'' interface to values of generalized
collection types.

Section~\ref{SetInterface} already presents a signature
\kw{SetInterface}, defining a set type constructor \kw{Set} 
and algebra operations like \kw{union}, \kw{intersection} over set
values.  Similar generic interfaces can be defined for other types
appropriate for data collection, e.g. lists, (keyed)
relations, mappings, views on relations etc. To provide a
single, uniform query protocol for such a variety of types, we
abstract from individual properties of these collection types and
base the protocol definition on an abstract type operator of the
following kind:
\begin{xple}
Reader::\k{OPER}(E::TYPE) TYPE
\end{xple}
For the purpose of interface definition, we do not require any
additional information about this type operator.  As long as we assert
that for a given collection type (say \kw{List}) and any element type 
\kw{E} of kind \kw{TYPE} the property \kw{List(E)$<$:Reader(E)} 
holds, we can apply any \kw{Reader} operation also to \kw{Lists}.

Without going into details, \kw{Readers} may be considered as data
``sources'' since they (lazily) ``yield'' \cite{L*77,Bun90,Wadl90} data
elements. Collection types also have the capability of
\kw{Writer}s, namely acting as ``sinks'' for data elements.  For
example, a value \kw{partSequence} of type \kw{Reader(Part)} denotes a
homogeneous sequence of values of type \kw{Part}.  We do not want to
constrain the implementation of this sequence in any way, e.g. a
non-materialized view should be a legal \kw{Reader}, too.  Therefore,
the \kw{Reader} abstraction subsumes other well-known abstractions like
lists and list comprehensions in functional programming, sets,
relations, multisets and views in database systems, as well as files,
streams and pipes in operating systems or channels in the CSP model.

What are the operations we expect to be defined over such abstract
\kw{Readers}? \kw{ReaderOperations} should allow to
\begin{itemize}
\item map readers to readers of the same or another element type 
(e.g. \kw{rest, map, select, head});

\item to reduce readers to values of more primitive types  
(e.g. \kw{empty, size, hom, some, all, majority});

\item to combine readers into a single new reader (e.g. \kw{append, zip,
overlay, insert});

\item to perform operations with side-effects over all elements of
a reader (e.g. \kw{forEach, for, until, while});

\item to ``associatively'' select \e{individual} elements of a reader
based on its properties expressed by a predicate analogous to the
``de-setting'' operation, as found, for example, in Adaplex \cite{SFL81}
(\kw{the, theOnly, theFirst, theLast});
\end{itemize}

Figure \ref{ReaderOps} provides a fairly complete definition of such a
service protocol given in Quest. The signature \kw{ReaderOperations}
defines a list of higher-order function signatures that
are intended to provide \e{iteration abstraction} over homogeneous
sequences of data elements. All of these functions are polymorphic in
the element type of the sequence (indicated by the type parameters
\kw{E} of kind \kw{TYPE}).

The particular choice of operations and signatures depicted in Figure
\ref{ReaderOps} allows to entirely abstract from the properties of the
sequence element type, (e.g. a computable equality predicate is not
required) and to ``lazily'' evaluate expressions formed via reader
operations (e.g. quantifier evaluation may not require the computation
of all sequence elements).  Furthermore, all operations constructing a
reader from other readers can be defined in a way such that the
constructed reader ``naturally'' respects the given ordering on the
input readers.  Last, but not least, reader operations are defined in a
purely functional style without relying on the concept of mutability,
e.g. by providing destructive insert, update and delete operations on
streams.

\begin{figure}[htbf]
\begin{center}
\begin{xple}
\k{Let} ReaderOperations = \k{Tuple}
  empty(E::TYPE x:Reader(E)):Bool
  get(E::TYPE x:Reader(E)):E
  rest(E::TYPE x:Reader(E)):Reader(E)

  map(E,F::TYPE x:Reader(E) f(:E):F):Reader(F)
  append,zip(E::TYPE x,with:Reader(E)):Reader(E)
  overlay(E;F;G::TYPE x:Reader(E) with:Reader(F) f(:E :F):G) 
          unitE:E, unitF:F):Reader(G)
  
  forEach(E::TYPE x:Reader(E) body(:E):Ok):Ok
  hom(E,F::TYPE x:Reader(E) f(:E):F g(:F :F):F):F
  hom0(E,F::TYPE x:Reader(E) f(:E):F g(:F :F):F unit:F):F

  select(E::TYPE x:Reader(E) p(:E):Bool):Reader(E)
  for,until,while(E::TYPE x:Reader(E) p(:E):Bool body(:E):Ok):Ok
  the,theOnly,theFirst,theLast(E::TYPE x:Reader(E) p(:E):Bool):E

  some,all,majority(E::TYPE x:Reader(E) p(:E):Bool):Bool
  partition(E::TYPE x:Reader(E) p:Array(Fun(:E):Bool):Array(Reader(E))

  head,tail(E::TYPE x:Reader(E) len:Int):Reader(E)
  selectSub(E::TYPE x:Reader(E) i,len:Int):Reader(E)
  removeSub(E::TYPE x:Reader(E) i,len:Int):Reader(E)
  insert(E::TYPE x,into:Reader(E) after:Int):Reader(E)  
  reverse(E::TYPE x:Reader(E)):Reader(E)
\k{end}
\end{xple}
\end{center}
\caption{Iteration abstraction over generalized collections}
\label{ReaderOps}
\end{figure}

Similar iteration abstractions are discussed, for example, in
\cite{OBBT89,AtMo88,SFSS90,SDD*86}.  The following query applies
iteration abstrraction and selects all expensive parts from the set
\kw{parts} (of type \kw{Set(Part)$<$:Reader(Part)}).
\begin{xple}
\k{let} expensiveParts = select(parts \k{fun}(p:Part):Bool p.price $>$ 100.0)
\end{xple}
In this setting, a (read-only) view is nothing else than a
non-parameterized function referring to a global set variable
(\kw{parts}):
\begin{xple}
\k{let} partView():Reader(Part) = select(parts \k{fun}(p:Part):Bool p.price $>$ 100.0)
\end{xple}
Finally, the scoping and binding rules for function parameters also
enable the definition of nested predicates (e.g. for referential
integrity constraints):
\begin{xple}
all(compParts \k{fun}(cp:CompositePart):Bool
      all(cp.madeFrom \k{fun}(p:Part):Bool member(p allParts)))
\end{xple}

Additional generic operations can be defined by assuming
\e{finite} collections (eventually of bounded maximum size) with a
computable equality predicate over their elements (see
figure~\ref{CollectionOps}).  The main complication compared with the
\kw{ReaderOperations} of figure~\ref{ReaderOps} arises from the fact 
that for any operation on a \kw{Collection(E)}, an equality predicate
for values of type \kw{E} has to be available. Since this equality
predicate also captures primary key constraints on relations, the
\kw{CollectionOperations} avoid the well-known problems arising from the
subtle interaction between {\tt COUNT, AVERAGE} \ldots\ operations and
(implicit) duplicate elimination.

\begin{figure}[htbf]
\begin{center}
\begin{xple}
\k{Let} CollectionOperations = \k{Tuple}
  put(E::TYPE x:Collection(E) e:E):Collection(E)
  size(E::TYPE x:Collection(E)):Int
  full(E::TYPE x:Collection(E)):Bool
  remove(E::TYPE x:Collection(E) e:E):Collection(E)
  member(E::TYPE x:Collection(E) e:E):Bool 
  equal(E::TYPE x,y:Collection(E)):Bool 
  collect(E::TYPE x:Reader(E) into:Collection(E)): Collection(E)
  union,intersect,difference(E::TYPE x,y:Collection(E)):Collection(E)
  select2(E1,E2,F::TYPE target(:E1 :E2):F into:Collection(F)
         from1:Collection(E1) from2:Collection(E2)
         where(:E1 :E2):Bool)):Collection(F)
  select3(E1,E2,E3,F::TYPE target(:E1 :E2 :E3):F into:Collection(F)
         from1:Collection(E1) from2:Collection(E2) from3:Collection(E3)
         where(:E1 :E2 :E3):Bool)):Collection(F)
\k{end}
\end{xple}
\end{center}
\caption{Bulk operations for finite collections with a computable equality predicate}
\label{CollectionOps}
\end{figure}

The pragmatic goal behind the definition of such generalized protocol
templates is twofold: First, application programmers should be
encouraged to use high-level access specifications instead of explicit
iterations, thus making programs more readable, putting the burden of
correctness proofs (e.g.  termination) on the implementors of this
general protocol, and giving room to optimized implementations of such
protocols (see section \ref{Implementations}). Second, designers of new,
specialized system services (e.g. graph-traversal algorithms) should
tailor their interfaces to comply with the more general ones. Such
adherence to global protocols improves the understandability of large
systems and the interoperability between separately developed system
services.



\subsection{Specialized Implementations}
\label{Implementations}

In a Database Application System it is not sufficient to concisely
define the above protocols and to check the consistent use by protocol
clients, but it is equally important to have language support for
efficient protocol \e{implementations} without relying on ``magic''
predefined external services. Again, we first consider traditional
approaches to this task:
\begin{description}

\item[Operating system] and application libraries make heavy use of
standard procedure call mechanisms. The execution model is based on a
\e{substitute and call} semantics: The choice of a particular
implementation is typically performed by a simple dynamic case analysis
of actual parameter values (e.g.\ the state of a file descriptor allows
to distinguish between local and remote file access).

\item[Programming language] processors strive for a static selection
of protocol implementations. For example, the implementation of a
\kw{FOR} loop statement typically involves a static analysis of the
loop variable types, the actual loop bounds and the structure of the
loop body.  Even advanced optimization techniques employed in
state-of-the-art compilers are confined to \e{local} program text or
data flow analysis. Separate compilation techniques required in
large-scale and shared systems emphasize the lack of a single global
system ``picture'' to successfully guide global optimization techniques.

\item[Database systems] traditionally have to live with both, strong
demands on the efficiency of protocol implementations on the one hand
side, and very limited information to be derived statically from
protocol clients (application programs written in a host language).
Therefore, the choice of a particular implementation of a query
expression is usually delayed in a DBMS until run-time.  Another
distinctive property of DBMSs is the availability of several
functionally equivalent protocol implementations that only differ in
their \e{operational} characteristics (e.g. access time, storage
requirements or locking granularity). 
\end{description}

Languages for Database Application Systems have to support all three
approaches and therefore require a wide range of binding times and
binding alternatives.  For example, a ``good'' implementation of the
query expression
\begin{xple}
\k{let} expensiveParts = select(parts \k{fun}(p:Part):Bool p.price $>$ priceLimit)
\end{xple}
should be able to exploit local compile-time information (the structure
of the selection predicate \kw{p.price $>$ 100.0} or the type of \kw{p})
as well as information about the actual representation of the set
\kw{parts} (e.g. as a sequence ordered on \kw{p.price}), the
cardinality of \kw{parts}, the value of the global variable
\kw{priceLimit} at run-time or even statistical information
and application-domain knowledge about allowable part prices.

Efficient utilization of binding alternatives -- the choice of binding
time as well as the selection of the specific implementation to be bound
to -- requires a careful organization and high availability of such
alternatives.

As an example for such a taxonomy of protocol service implementations,
we investigate implementation alternatives for \kw{Readers}.  In Quest,
these alternatives can be classified by means of type operators that
define subtypes of \kw{Readers}. This enables compile-time checks to
assure that only (signature-)correct \kw{Reader} implementations are
supplied to the \kw{ReaderOperations} depicted in
Figure~\ref{ReaderOps}. Values of the most simple kind or
\kw{Reader} implementations, \kw{SequentialReaders} only provide 
the following protocol:
\begin{xple}
\k{Let} SequentialReader(E::TYPE)::TYPE = \k{Rec}(Reader) \k{Tuple}
  empty():Bool  get():E  rest():Reader
\k{end}
\end{xple}
It should be obvious that (potentially infinite) sequences, like
characters typed at a terminal, data records received via a network
connection, tokens recognized by a scanner, or arbitrary inductively
defined sequences (linear intervals, prime numbers, fibonacci numbers)
can be cast into this protocol, for example:
\begin{xple}
\k{let} \k{rec} countUp(from:Int):SequentialReader(Int) = \k{tuple}
    \k{let} empty() = false   (* infinite *)
    \k{let} get() = from
    \k{let} rest() = countUp(from + 1)
\k{end}
\end{xple}

Iterations over finite collections (like lists, stacks, queues, bags,
sequential files) independent of their actual implementation (e.g. via
linked records or arrays) can provide an additional useful piece of
information, namely the total \kw{size} of the sequence.
\begin{xple}
\k{Let} FiniteReader(E::TYPE)::TYPE = \k{Rec}(Reader) \k{Tuple}
  empty():Bool  get():E  rest():Reader  size():Int
\k{end}
\end{xple}

Bulk data structures suitable for database modelling and DBMS
implementation are special by providing means to \e{uniquely identify}
collection elements by their \e{properties}. Their generic protocol
\begin{xple}
\k{Let} IndexedReader(E::TYPE)::TYPE = \k{Rec}(Reader) \k{Tuple}
  empty():Bool  get():E  rest():Reader  size():Int
  member(e:E):Bool  getLike(e:E):E  equality():(:E :E):Bool
\k{end}
\end{xple}
subsumes a function to check for membership of a given element in the
sequence (possibly avoiding a full traversal) and for ``value-indexed''
retrieval using the function \kw{getLike} that returns an element with a
given index value.  Indexed \kw{Readers} require an equality predicate to be
defined over their elements. This equality function is usually passed as
a parameter of creation operations. It is also made externally
accessible as the result of the higher-order function \kw{equality}.
Sets and keyed relations are classical examples of this kind of data
structures. For example, the following creation of a
\kw{Part} relation defines the attribute \kw{name} to be the
primary key attribute of \kw{myPartRelation}:
\begin{xple}
\k{let} myPartRelation:IndexedReader(Part) = 
     relation.create(\k{fun}(p1,p2:Part) p1.name \k{is} p2.name)
\end{xple}

Set, relation and dictionary implementations based on hashing or bit
vectors also adhere to the \kw{IndexedReader} protocol. Similarly,
ordered data structures like ordered lists, ordered arrays, and various
kinds of search trees (B-trees, AVL-trees, R-trees, \ldots) exploit a
total ordering on their data elements that allows the fast determination
of all elements \kw{greater, greaterEqual, less,} or \kw{lessEqual} than
a given value of the reader element type \kw{E}.
\begin{xple}
\k{Let} OrderedReader(E::TYPE)::TYPE = \k{Rec}(Reader) \k{Tuple}
  empty():Bool  get():E  rest():Reader  size():Int
  greater,greaterEqual,less,lessEqual(e:E):Reader  ordering():(:E :E):Int
\k{end}
\end{xple}



\subsection{Efficienciy by Dynamic Case Discrimination}
\label{Efficiency}

\e{Query optimization} and \e{data independence} are essential for 
any database application. A substantial step towards data independence
is already achieved by defining a uniform \kw{ReaderOperations}
interface to a wide range of data structures. Clients of this uniform
interface are not ``tempted'' to utilize sort orders, indexed access,
clusterings etc.\ available only for specific data structures.  This
apprroach shields clients from implementation changes which are
inevitable in persistent and shared Database Application Environments.

As indicated in the previous seciton, creation operations for
\kw{Readers} are more sensitive to implementation changes, since more
specialized \kw{Readers} (e.g. hash tables) require additional
type-specific information (e.g. a particular comparison or hash-function
for part names). This dependency on type representation details may be
circumvented by ``structure directed operator addition'' as proposed in
\cite{SFSS90}. Another approach found in some object-oriented systems is
to equip \e{every} type with (possibly undefined) ``methods'' for
comparison, hashing, \ldots\ and to dynamically inquire the availability
of method implementations for a given \kw{Reader} element type. 

Query optimization can now be understood as the process of selecting a
particular value of the \kw{ReaderOperations} type (e.g.
\kw{sequentialReaderOperations} based on \kw{SequentialReaders}) to
achieve minimal execution costs for a given instantiation of the 
reader operation parameters (\kw{parts:IndexedReader(Part)}) like in the
function application
\begin{xple}
select(parts \k{fun}(p:Part):Bool p.price $>$ priceLimit)
\end{xple}
This implies a departure from simple
\e{substitute and call} semantics, as this selection process involves
a (dynamic) analysis not only of value parameters (\kw{priceLimit}), but
also of
\begin{itemize}
\item actual type parameters (is there a total order defined over \kw{E = Part}?),

\item actual function parameters (does the predicate \kw{p = \k{fun}(p:Part)
\ldots} produce or rely on side-effects; is it monotone in \kw{p\/}?),

\item bindings in the client's environment (is there an index defined on
\kw{p.name}?),

\item bindings in the server's environment (which \kw{Reader} 
implementations are available?).
\end{itemize}

We are confident that a small set of comprehensible and simple language
mechanisms can be isolated to serve as safe and controlled building
blocks for general-purpose (run-time) optimizers. Issues of query
interpretation, reflection, transformation and expansion can be treated
successfully without sacrificing the merits of static type checking and
simple compilation schemes as found in well-developed database
programming languages.


