%\batchmode
\documentstyle[twocolumn]{article}
\newcommand{\comment}[1]{}
%\newcommand{\IEEESoftware}[1]{} % for KBSE version
%\newcommand{\KBSE}[1]{#1} % for KBSE version
%\newcommand{\IEEESoftware}[1]{IEEESoftware[[[#1]]]} % for combined version
%\newcommand{\KBSE}[1]{KBSE[[[#1]]]} % for combined version
\newcommand{\IEEESoftware}[1]{#1} % for IEEE Software version
\newcommand{\KBSE}[1]{} % for IEEE Software version
\comment{ Letter to D. Setliff:
Dear Dr. Setliff,

The enclosed submission is a superset of the paper that will be in the
KBSE conference.  I fully expect that, after comments from your
reviewers, the result will look less like a strict superset than a
major rewrite.  Certainly the final KBSE paper is substantially
different from the version that was originally submitted there, both
due to suggestions from the referees and because I tried to achieve
the page limit.  In any case the semantic content is, and is likely to
remain, similar.  I hope that this is not objectionable in itself, but
I thought I should mention it just in case.  }

\pagestyle{empty}
\input{psfig}
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.07in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.26in}
\setlength{\parindent}{1pc}
\hyphenpenalty=80  % Evidently I don't like hyphenation

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

%  --- scribe translations ---
\newenvironment{remark}{\begin{small}}{\end{small}}
\renewcommand{\i}[1]{{\sl#1}}    % \i was a dotless i (p. 40 latex)
\renewcommand{\t}[1]{{\tt#1}}    % \t was an accent (p. 40 latex)
\newcommand{\foot}[1]{\footnote{#1}}
% \newcommand{\-}{_}             % \- used for hyphenating
\newbox\atempbox
\newcommand{\w}[1]{\setbox\atempbox=\hbox{#1}\hskip\wd\atempbox\penalty0\hskip-\wd\atempbox\box\atempbox}
%\newcommand{\w}[1]{\mbox{#1}}
\newcommand{\sect}[1]{\section{#1}}
\newcommand{\subsect}[1]{\subsection{#1}}
\newcommand{\subsubsect}[1]{\subsubsection{#1}}

% --- all this is tricky stuff for the code command ---
\def\uncatcodespecials{\def\do##1{\catcode`##1=12 } \dospecials}
\def\setupverbatim{\tt \spaceskip=0pt	% Make sure we get fixed tt spacing
    \obeylines \uncatcodespecials
    \obeyspaces \verbatimdefs}
% This macro turns on verbatim mode until \endverbatim is seen.
\def\xverbatim{\begingroup \setupverbatim \catcode`\{=1\catcode`\}=2
  \parskip=0pt plus .05\baselineskip \parindent=0pt
   \catcode`\ =13 \catcode`\^^M=13  \catcode`\\=0}
{\catcode`\^^M=13{\catcode`\ =13\gdef\verbatimdefs{\def^^M{\ \par}\let =\ }}
  \gdef\verbatimgobble#1^^M{}}
% This defines \xendverbatim to end the group which begins with \xverbatim
\let\xendverbatim=\endgroup
\newcommand{\code}[0]{\xverbatim\footnotesize\tt\helpcode}
\def\helpcode#1{#1\xendverbatim}

\begin{document}

%don't want date printed
\date{}

\title{\Large\bf Automatic Composition of Data Structures to Represent Relations} 
\author{%\begin{tabular}[t]{c@{\extracolsep{8em}}c}
Donald Cohen, Neil Campbell \\
 \\
USC / Information Sciences Institute \\
4676 Admiralty Way \\
Marina del Rey, CA 90292-6695
%\end{tabular}
}

\maketitle

%I don't know why I have to reset thispagesyle, but otherwise get page numbers
\thispagestyle{empty}

\subsection*{\centering Abstract}
This paper describes a very general class of composite data
structures, and a language in which programmers can describe which to
use for each purpose.  These data structures are composed of primitive
data structures drawn from a relatively small library that can be
extended by the programmer.  We describe the semantics of composite
data structures in terms of a relational model.  Programmers can use
relational programming languages to express computations independent
of data representation decisions, and then use our data structure
language to specify representations for the relations in their
programs.  Finally, we describe how a compiler translates operations
on relations represented by composite data structures.  It uses a cost 
model to choose among alternative algorithms.

\section{Introduction}

For some years now our group has been working to support a style of
programming in which the programmer first thinks about the desired
behavior of a program and only later, when he is satisfied with the
behavior, thinks about performance.  In order to promote this style,
programs are separated into ``specifications'', which describe the
desired behavior independent of performance considerations, and
``annotations'' which affect only performance.  Data representation
decisions in particular are regarded as performance concerns.  We
therefore wish to make it trivial to choose or change data
representations.

We also wish to minimize any penalty in performance for separating
specifications from annotations.  Our specification language models
data in terms of objects and relations.  It provides operations on
relations such as adding tuples, iterating over tuples, and testing
whether a tuple is in the relation.  The representations used for
those objects and relations are determined by annotations.  We want
our relational languages to offer operations on relations that can be
compiled, given appropriate representation annotations, into code
comparable to what the programmer would have written.  We also wish to
make available, through annotations, all of the interesting data
structures that appear in real programs.  For instance, the operation
``make 3 be the only value in relation R'', if R were represented by a
variable, might compile into ``set V to 3''.

Our first approach to satisfying these goals, AP5\cite{ap5}, allowed a
programmer to choose representations for relations from a library of
representations.  The library could be extended with new
representations, but this was much more difficult than choosing one
already in the library.  For this reason programmers tended to use the
best representation {\em in the library} for the situation at hand,
even when they knew of a better representation that was not in the
library.  Our solution to this problem can be viewed either as making
the library much larger or much easier to extend.  It provides a small
specification language with which programmers can describe many
relation representations as compositions of building blocks.  We will
call this the {\em representation} specification language, to
distinguish it from the {\em relational} specification language in
which data is modelled in terms of objects and relations.  As before,
it is much easier to use building blocks that are already in the
library than to add new ones to the library.  However a very small
library of building blocks can be combined into a very large set of
compound representations.

Describing data representations in our representation specification
language is not much easier or harder than writing data declarations
in conventional programming languages.  The leverage for the
programmer is that a compiler can automatically translate those
descriptions into programs that perform operations on relations with
the given representations.  In a conventional language the programmer
would have to write these himself, and would have to rewrite them if
he decided to change the data representations.  In some cases there is
a large set of possible algorithms for an operation.  Like any query
optimizer, our compiler bases its choice on a cost model.  This is
provided in part by the building blocks and in part by additional
programmer annotations.

\paragraph{Example:}

Consider a program that deals with groups of parts combined into
assemblies, where these are in turn combined into larger assemblies,
etc.  The objects in this domain would include parts and assemblies.
The relations would include the subassembly relation, indicating that
one assembly is a subassembly of another.  A programmer might make the
following representation decision(s):

{\em Assemblies are represented by records.  These contain a
``children'' field which holds a pointer to a linked list of
subassemblies.  Assembly records also contain a ``parent'' field
which holds a pointer to the parent assembly (there must be
exactly one).}

The information expressed informally above can be expressed formally
as follows.  The syntax is described in detail in section \ref{specify}.

\code{
/* relation subassembly(super, sub) */
/* label     representation      slots    children */

             field-map(children) super    sub-list
 sub-list    list-set            sub
             field-map(parent)   sub      one-super
 one-super   singleton-set       super
}

Such terms as ``field'' and ``list'' correspond to elements of the
building block library.  The first two lines (after the comment lines) 
mean that the children
field of each superassembly points to a list of subassemblies, and
the last two lines mean that the parent field of each subassembly
points to its superassembly.  This description is used as input to a
compiler that implements operations of the relational specification
language, such as testing whether assembly Y is a subassembly of
assembly X.  In this case there are two possible algorithms.  One is
to compare X with the parent field of Y.  The other is to iterate
through the list in the children field of X comparing the elements to
Y.  In order to make a rational choice, the compiler must estimate the
cost of each of these algorithms.  It can then implement the operation
with the lower cost algorithm.

Section \ref{intuition} describes, on an intuitive level, the kinds of
data structures supported.  Section \ref{bblocks} describes the kinds
of building blocks that are used.  Section \ref{specify} describes the
composition language.  It also provides a number of examples and
discusses the semantics of compositions.  Section \ref{compiler}
describes compilation of relational interfaces.  This includes
descriptions of the operations provided by building blocks and
examples of compilers for some common relational operations.  It also
describes some of the choices the compilers must make, and the cost
model.  We finish with brief sections on related work, current status,
future work, and conclusions.


\section{Intuitive description of compositions}\label{intuition}

\comment{
Our goal is to build data structures that represent relations among
objects with some significance in an application domain, such as
assemblies and parts.  These objects are all presumed to have types,
e.g., part and assembly might be types.  The representations of these
types are to be chosen by the programmer, and communicated to the
compiler by annotations, e.g., parts might be represented by integers
in the target language, assemblies might be represented by records,
etc.  Numbers and strings might also qualify as objects in the
application domain.  These would, in all likelihood, be represesnted
by numbers and strings in the target language.  We assume that
equality is defined over these types.  This is necessary, for instance, 
in order to determine whether one assembly is a subassembly of another.
In this case we have to compare the second with the contents of the 
parent field of the first.  Some representations require additional
interfaces, such as ordering predicates and hash functions.
}

Composite representations offer the following features that
appear in the data structures of real programs:

\begin{itemize}

\item the ability to build nested data structures, e.g., lists of arrays
of hash tables,

\item the ability to store data redundantly (in order to improve speed
at the cost of space), and

\item the ability to share structure between redundant representations
(in order to save space).\foot{Since readers tend to ask at this point
about recursion, here's the answer.  Recursive data structures appear
in two ways.  One is that the data structures used as building blocks
are recursive, e.g., a list or tree used to represent a set of
objects.  The other is that recursion is encoded in the relations.
For instance the subassembly relation may be regarded as an instance
of recursion, since subassemblies may themselves have subassemblies.
However the relation itself only represents the single level relationship
between one assembly and another.}

\end{itemize}

An example of a nested data structure is the field of the assembly
record that contains a list of other assemblies.  As another example,
a text editor might associate with each buffer an array indexed by
line number, where each element is another array indexed by character
position containing in each element the character at that position in
the given line of the given buffer.  We have in mind here a particular
meaning for nesting.  In the example above, given a buffer we can find
an array.  This array represents the relation between line numbers,
columns, and characters for that buffer.  From that array, given a
line number we can find another array.  This array represents the
relation between columns and characters for the buffer and line number
that were used to find it.  Similarly, the list of subassemblies
contains only those related to the assembly represented by the record
containing the list.

Nesting is certainly the most important capability provided by
composite representations.  It alone would provide a useful form of
composition.  The others appear less frequently in real programs.  
Of these, redundancy is probably more important than sharing.
By redundancy we simply mean that there is more than one way to
obtain the same information.  The relation between assemblies 
provides an example.  There are two different ways to determine 
whether one assembly is a subassembly of another.  Similarly, in 
order to add or remove such a relationship it is necessary to 
update two different data structures.

Structure sharing is simply storing several pointers to the same data
structures.  This saves space when the data structures to be stored
are larger than the pointers needed to refer to them.  It's also
faster to update one shared data structure than several that are
stored separately.  As an example of structure sharing, suppose we are
writing a program to schedule travel.  Suppose we have a relation
between people, places and times, e.g., some person is scheduled to be
at some place at some time.  (The example is not meant to imply any
cardinality constraints, i.e., a person might be scheduled to be in
several places at the same time.)

\begin{figure}[h]
\par
% following line cannot be broken (!)
\centerline{\psfig{figure=structure-share.pp,height=1.5in,width=2.1in,bbllx=0in,bblly=0in,bburx=3.5in,bbury=2.5in}}
\par
\caption{Example of structure sharing}
\label{sharing}
\end{figure}

Suppose this relation were redundantly represented as illustrated in
figure \ref{sharing}.  First, each representation of a time contains a
pointer to a table associating places with lists of people.  Second,
each representation of a place contains a pointer to a table
associating times with lists of people.  For any time and place that
are related, we would then have two lists of people, one stored in
the table for the place and another in the table for the time.  Of
course, these lists would always represent the same set of people,
namely the set of people related to that particular place and time, so
there is no need to keep two copies.  Instead both tables could hold
pointers to the same list.

A nested data structure can be described as a sequence of primitives
where each element contains (or contains pointers to) the next, e.g.,
a table containing lists of arrays corresponds to the sequence table,
list, array.  From this perspective the example above looks like two
sequences sharing a tail.  The symmetric case where two sequences
share a head is also possible.  For instance the same relation might
be represented as a single table indexed by person, and containing for
each person two more tables.  One of these would associate times with
lists of places and the other would associate places with lists of
times.  As we will see, it is also possible to share both heads
and tails, and even middle segments.

\comment{
It is sometimes advantageous to store redundant information in order
to promote sharing.  Suppose that we have an n-ary relation for which
it is important to be able to quickly find all tuples containing an
input object in any of m positions, e.g., all tuples containing an
input person or time.  A reasonable solution would be to associate
with each object in the m critical positions a list of records of
(n-1)-tuples, e.g., associate with a person a list of time, place
pairs.  Sometimes we can actually save space by adding redundancy.
Instead of (n-1)-tuples we could store complete n-tuples.  Although a
record of n items takes more space than a record of n-1, we can share
one n item record among m lists instead of creating m n-1 item
records.

Note the solution with n-1 item records still permits a perverse sort
of sharing.  A single n-1 tuple could be related to several objects,
and those objects could all point to a shared record.  Unfortunately,
this can be extremely inefficient in time.  First, a long search may be
required to find an existing record that can be shared.  Second, when
a record is deleted from a list it becomes nontrivial to determine
whether that record is now garbage.  Our current implementation does
not support this kind of sharing.  For the kind of sharing that it
does support such problems do not arise.\comment{limitation}}

\section{Building blocks}\label{bblocks}

Composite data structures are made out of primitive data structures,
which we call building blocks.  These include such common data
structures as arrays, linked lists, hash tables, records, etc.  We do
not claim to supply an exhaustive set of such building blocks.  Rather
a library contains the most common ones and a programmer can, with
some effort, add more.  The important point is that the number of
building blocks is much smaller than the number of ways in
which they can be composed.  We expect that new building blocks will
be invented much more slowly than new compositions of old ones.

There are three different kinds of building blocks, which we call
\t{tuple}s, \t{set}s, and \t{map}s.\foot{The typewriter typeface is
used to distinguish these implementation data structures from the
mathematical objects of the same names which they closely resemble.} A
\t{tuple} represents a (mathematical) tuple of a fixed length known at
compile time, containing objects or data structures of fixed types
also known at compile time.  A \t{set} is very much like a relation,
in that it represents a (mathematical) set of (mathematical) tuples of
objects.  A \t{map} is similar to a \t{set} in that it represents a
set of tuples, but some of the elements of those tuples are objects
and others are \t{set}s or \t{map}s.  Maps, in effect, relate tuples
to other relations, e.g., person objects (1-tuples) might be related
to relations between times and places.  In order for a map to be useful 
it must provide access to the relation associated with an input tuple.

\comment{
 The most obvious representation for \t{tuple}s is a record.  However
 there are other possible representations as well.  For instance, a 
 \t{tuple} of three objects that are all represented by integers between 
 0 and 9 might be represented as a single integer between 0 and 999.
 There are many representations for \t{set}s, of course.}

\begin{figure}
\par
% following line cannot be broken (!)
\centerline{\psfig{figure=map-example.pp,height=1.2in,width=2.4in,bbllx=0in,bblly=0in,bburx=4in,bbury=2in}}
\par
\caption{Text editor representation}
\label{map-example}
\end{figure}

\t{Map}s provide nesting.  The relation in the text editor example,
as illustrated in figure \ref{map-example},
would be represented by a \t{map} from buffer objects to \t{map}s from
lines (or line numbers) to \t{map}s from columns to \t{set}s each
containing a single character object.  In this case each \t{map} has a
single object as the domain, but this is not always the case.  For
example, if it were important to be able to quickly iterate over the
characters in a given column (and there were a limited number of lines
and columns), we might have used a two dimensional array indexed on
both line and column.  Similarly a
\t{set} representing a relation between lines and columns might be
implemented by a two dimensional bit array.

\t{Tuple}s are used to factor out one aspect shared by many \t{map}s 
and \t{set}s.  We sometimes want to store multiple domain objects or
multiple range building blocks in a \t{map} or \t{set} for which the
representation does not offer any interesting indexing.  Rather than
forcing the \t{map} or \t{set} to worry about these multiple things we
allow it to store single things, \t{tuple}s, which encapsulate the
multiple things.  Since there are actually several different
representations for \t{tuple}s, this also allows us to factor the
tuple representation out from that of the \t{map} or \t{set}.  It
further allows us to share pointers to \t{tuple}s.

\comment{
The current implementation imposes a few restrictions that are not
strictly necessary.  It does not allow tuples to contain other
tuples.  Every tuple contains either all objects or all building
blocks.  Further, a \t{map} or \t{set} cannot mix \t{tuple}s with
other objects or building blocks.  It must either store all its own
objects or one \t{tuple} that in turn stores all of its objects.
Similarly a \t{map} must either store all of its range building blocks
or store one \t{tuple} that in turn stores all of its range building
blocks.  These restrictions could be relaxed, but we have seen no real
need to do so.}

\section{Specifying compositions}\label{specify}

A relation is represented by a set of building blocks.
It is convenient to abstract out the \t{tuple}s by regarding them as
parts of the \t{map}s and \t{set}s that they help to represent.  
This leaves just \t{map}s and \t{set}s, each of which refer to objects 
which are in tuples of the relation being represented.  In addition,
the \t{map}s refer to other \t{map}s and \t{set}s.  In figure 
\ref{map-example} the columns group building blocks by their use.  The 
first column contains the single \t{map} used to associate buffers
with the \t{map}s in the second column.  Each of these (one for each
buffer in the relation) associates the lines in the buffer with
\t{map}s in the next column.  Notice that figure \ref{sharing} is not
organized in this way.  In each of the first two columns the different
maps represent totally different kinds of relations.  Our
representation specification language exploits the regularity of
figure \ref{map-example}: all of the building blocks in a given column
are described by a single {\em building block description}.

In general, a relation representation is specified by a set of
building block descriptions, where each description contains the
following information:

\begin{itemize}

\item {\em slots:} an ordered set of relation slots

\item {\em representation:} a representation choice

\item {\em parameters:} representation specific parameters

\item {\em children:} an ordered set of ``child'' descriptions 
(present only in \t{map} descriptions)

\end{itemize}

The elements of the tuples of a relation are labelled by what we call
the {\em slots} of the relation.  For instance, the appointment
scheduling relation has three slots, which we might label the
``person'', ``time'' and ``place''.  The subassembly relation has two
slots, which we might label ``super'' and ``sub''.  The text editor 
relation has four slots, which we might label ``buffer'', ``line'', 
``column'' and ``character''.  

The {\em slots} of a building block description specifies which slots
of the relation are represented in the corresponding building blocks.
For instance, in the text editor example, the description of the
\t{map}s used to map lines to relations between columns and characters
has as its set of slots the singleton set containing the line slot.
The description of the singleton sets of characters has as its set of
slots the singleton set containing the character slot.  For
descriptions of building blocks that represent multiple slots, these
must be ordered.  The interpretation of the ordering is dependent on
the representation choice.  For instance, in a two dimensional array,
it might mean that the first slot indexes the rows of the array and
the second indexes the columns.

The {\em representation} identifies how the corresponding building
blocks are to be represented.  This is just the name of a
representation in the library.  The library associates these names
with a set of standard functions that provide information or produce
code to implement standard operations on building blocks of that
representation.  We describe these functions in section \ref{compiler}.

The {\em parameters} might include such things as the size of the hash
table to be allocated, the name of the field of a record in which some
data is to be stored, or the ordering relation used to sort a list.

The {\em children} of a \t{map} description indicates that each
corresponding \t{map} associates tuples of its slots with an ordered set
of building blocks corresponding to the children.  For instance, the
description of the \t{map}s that relate lines to relations between
columns and characters has one child description, which is the
description of the \t{map}s that relate columns to relations (sets) of
characters.  Again, if there is more than one child, the
interpretation of the ordering depends on the representation choice.
Shared pointers to a single data structure are specified by having
several building block descriptions with common children.

\subsection{Examples}

For purposes of exposition we offer both a minimal textual syntax and
a graphical depiction for specifications of relation representations.
In the graphical depiction each building block description is a
box containing the representation and slots, with arrows pointing to
the children.  The textual syntax uses a separate line for each building
block description, containing an optional label 
(for other descriptions to refer to)\foot{If not for sharing, a nested
syntax would be more natural.  One might also use nested syntax with
labels to indicate sharing.}, a name to indicate the representation
with an optional list of parameters in parentheses, a slot
specification and a child specification.  A slot specification is
either a list of slot labels or an at-sign followed by the label of a
\t{tuple} building block description, where the tuple description with
that label contains a slot specification that is a list of slot labels
and an empty child specification.  Similarly, a child specification is
either a list of building block descriptions or an at-sign followed by
the label of a \t{tuple} building block description, where the tuple
description with that label contains an empty slot specification and a
child specification that is a list of labels of building block
descriptions.  Descriptions of \t{set}s and \t{map}s must have
non-empty slot specifications while child specifications for
\t{set}s must be empty and for \t{map}s must be non-empty.

Representation names will include one of the the words ``map'',
``set'' or ``tuple'' to indicate the type of building blocks they
represent.

\begin{figure}[h]
% following line cannot be broken (!)
\centerline{\psfig{figure=subassembly-example.pp,height=.75in,width=1.5in,bbllx=0in,bblly=0in,bburx=2.5in,bbury=1.25in}}
\code{
/* relation subassembly(super, sub) */
/* label     representation      slots    children */

             field-map(children) super    sub-list
 sub-list    list-set            sub
             field-map(parent)   sub      one-super
 one-super   singleton-set       super
}
\caption{Subassembly representation}
\label{subassembly-example}
\end{figure}

Figure \ref{subassembly-example} describes the representation of the
relation between assemblies and their subassemblies.  The representation
\t{field-map} describes a \t{map} which associates an object represented
by a record with another building block.  A pointer to the associated
building block is stored in a field of that record.  The parameter, 
\t(children), is the name of the field.  This representation requires 
that the slot specification contain only one slot, where the objects
that fill that slot are represented by records.  Such restrictions are
checked at compile time by code supplied as part of the building blocks.
In this case there are two different descriptions using field-map on
two different fields of assemblies.  The first maps a superassembly to
a building block corresponding to the description with the label
\t{sub-list}.  This is a list of subassemblies.  The other maps a
subassembly to a building block corresponding to the description with
the label \t{one-super}.  This is a degenerate case of a set which
represents a singleton set by its sole element, in this case the
superassembly.

\begin{figure}[h]
% following line cannot be broken (!)
\centerline{\psfig{figure=tuple-with-child-example.pp,height=.75in,width=3in,bbllx=0in,bblly=0in,bburx=5in,bbury=1.25in}}
\code{
/* relation  Schedule(person, time, place) */
/* label      representation  slots   children */

              hash-map   person      @ tuple
 tuple        record-tuple           time-map,
                                       place-map
 time-map     hash-map   time        place-set
 place-map    hash-map   place       time-set
 place-set    list-set   place
 time-set     list-set   time
}
\caption{Tuples of building blocks}
\label{tuple-with-child-example}
\end{figure}

Figure \ref{tuple-with-child-example} illustrates the use of a tuple to 
store building blocks.  In this case we initially index on people.  Each
person is thereby associated with a record containing a pair of hash tables.  
The first maps times to lists of places and the second maps places to lists
of times.

As mentioned earlier, AP5 provided a library of representations for
relations.  It is instructive to see how all of those representations
can be specified.  Of course, this library provided representations
that were either frequently desired or sufficiently general to provide
tolerable performance in a wide variety of situations.  While it's
important to be able to provide these, the real point of composing
building blocks is to tailor representations to particular
applications.  Some of the representations in the library correspond to
building blocks, e.g., arrays, hash tables, fields of records, etc.
However these representations tended to come in pairs.  The more
general mapped objects to lists of related objects, while the other 
was specialized to map objects to single objects.  These now correspond
to two of many alternatives, list-set and singleton-set.

Other representations were simply redundant combinations.  One of
these represented binary relations by pairs of pointers between
structures (similar to the subassembly representation, except that
both fields pointed to lists).  Another combined a pointer in a field
of a structure with a hash table which stored the inverse mapping.
The default representation in AP5 was a list of tuples, where tuples 
were in turn represented by lists.  This would now be expressed as in
Figure \ref{list-of-tuples-example}:

\begin{figure}[h]
% following line cannot be broken (!)
\centerline{\psfig{figure=list-of-tuples-example.pp,height=.36in,width=1.8in,bbllx=0in,bblly=0in,bburx=3in,bbury=.6in}}
\code{
/* relation Schedule (person, time, place) */
/* label   representation   slots         children */

           list-set         @ tuple
 tuple     list-tuple       person, 
                              time, place
}
\caption{List of tuples representation}
\label{list-of-tuples-example}
\end{figure}

There were two other interesting representations that were capable of
representing relations of any arity.  One was a discrimination net
where the discriminations were made on the basis of different slots of
the relation.  For instance, the relation Schedule (person, time,
place), was represented as a map from people to maps from times to
sets of places.  The maps all used one particular representation which
was a hash table optimized for the case of a small number of keys.
Our composed relations were originally conceived as a generalization
of this representation.  Figure \ref{discrimination-net-example} shows
how that can now be specified.

\begin{figure}[h]
% following line cannot be broken (!)
\centerline{\psfig{figure=discrimination-net-example.pp,height=.3in,width=2.7in,bbllx=0in,bblly=0in,bburx=4.5in,bbury=.5in}}
\code{
/* relation Schedule (person, time, place) */
/* label   representation   slots       children */

           small-hash-map   person      child1
 child1    small-hash-map   time        child2
 child2    small-hash-set   place 
}
\caption{Discrimination net representation}
\label{discrimination-net-example}
\end{figure}

The other representation used shared tuples.  This was a set of hash
tables, each indexed by a user chosen slot (specified as a parameter
of the representation).  Thus there might be a hash table mapping
places to lists of tuples of the relation, and another hash table
mapping times to lists of tuples.
Figure \ref{partial-index-example} shows how that can now be specified.

\begin{figure}
% following line cannot be broken (!)
\centerline{\psfig{figure=partial-index-example.pp,height=.75in,width=2.4in,bbllx=0in,bblly=0in,bburx=4in,bbury=1.25in}}
\code{ 
/* relation Schedule (person, time, place) */
/* label   representation   slots         children */

           hash-map         place         list1
           hash-map         time          list2
 list1     list-set         @ shared
 list2     list-set         @ shared
 shared    record-tuple     person, 
                              time, place
}
\caption{Hashing to shared tuples}
\label{partial-index-example}
\end{figure}

\subsection{Semantic restrictions}

We now formalize what each building block represents and explore some
consequences.  For simplicity we will again abstract out the
\t{tuples}.  Above we described what it meant for one building block
description to be the {\em child} of another.  We will say that one
building block description is the {\em parent} of another if the
second is a child of the first.  Since we are abstracting out
\t{tuples} this includes the case where the first is a \t{map} that
maps its tuples of objects to \t{tuple}s of building blocks which
include the second.  We now extend the notion of parent and child
from building block descriptions to the building blocks themselves.
One building block is the {\em parent} of another if the first is a
\t{map} that maps some tuple of objects to the second.  The number of
children of a building block is therefore the number of tuples that it
is associating with other building blocks times the number of children
that its description has.  We further use the terms {\em ancestor} and
{\em descendant} in the obvious ways.  We call a building block
without parents a {\em root}, and one without children a {\em leaf}.
(Leaves are the same thing as \t{set}s.)

We defined above the {\em slots} of a building block description.
The {\em slots*} of a building block description is the union of the
slots of that building block description and all of its ancestors.
Recall that when we abstract out \t{tuple}s we include in the
slots of a building block description any slots that are stored by
the \t{tuple}s that it uses to store its slots.

Given a set of slot labels, $\{L_1, \ldots , L_n\}$, we define a
{\em partial tuple} over that set as an assignment of values to some
subset of the labels.  We define the {\em merge} of two such partial
tuples as the union of the two sets of assignments.  The case where 
two partial tuples to be merged assign different values to the same 
label will not arise below.  

Finally we define a {\em residue} of a relation, R, with respect to a
partial tuple, T1, over the slots of R.  This is another relation, R',
over the slots of R that are not assigned by T1.  R' contains a tuple,
T2, iff the result of merging T1 and T2 is in R.  For instance, the
residue of Schedule with respect to a given person and time is the
unary relation (think of it as a set) containing the places related by 
Schedule to the given person and time.  The residue of Schedule with 
respect to a given person, place and time is a 0-ary relation, in 
essence a proposition, which is true (contains a single tuple of zero 
slots) if the given person, place and time is in the Schedule relation 
and otherwise false (contains no tuples).  The residue of any relation 
with respect to an empty partial tuple is the relation itself.

Each building block (still ignoring \t{tuple}s) represents a residue
of the relation.  Any root building block represents the entire
relation.  That is, by following pointers in that building block one
can find out about complete tuples.  In that same sense, if a building
block, B, represents the residue of relation R with respect to tuple
T1, and maps a tuple, T2 to a child, C, then C represents the residue
of R with respect to the result of merging T1 and T2.

An immediate consequence of the requirement above is that all children
of a given building block must represent the same residue.  It also
follows that all parents of a given building block must have the same
slots*.  Any building block (other than a \t{tuple}) with the same
slots* as its parent(s) is devoid of information and therefore of no
value.  Our requirements prohibit ``partial representations''.  In
particular every leaf building block must have all of the slots of the
relation in its slots*.  Thus we cannot represent Schedule by just a
list of times.  Of course, one might define another relation as the
set of times that appear in Schedule, and represent that relation by a
list of times.

\comment{
 In the case of \t{tuple}s of objects, the current implementation
 requires that the building blocks that the \t{tuple}s help to
 represent all have the same slots*.  (Recall that this includes all
 the slots of the \t{tuple}.)  This means that, given a partial tuple
 assigning objects to those slots* slots, either there will be one
 \t{tuple} pointed to by all of those building blocks or none of those
 building blocks will point to any such \t{tuple}.\foot{It appears that
 this could be generalized slightly, by simply requiring that one of
 these building blocks have a slots* that is a subset of all the
 others.  This would mean that the \t{tuple}, if it existed, could
 always be found from that building block.\comment{***}}  The case
 where, say, a \t{tuple} of windows and assemblies is shared by two
 lists representing residues of two different warehouses cannot even be
 expressed in our language.  These two lists would be described by the
 same building block description even though the \t{tuple}s were not
 shared.  Multiple parents of a building block description only mean
 that there are two paths to a single building block for a single
 partial tuple assigning values to the slots* of that building block.
 Two partial tuples assigning different values to the slots* of a
 building block description always lead to different building blocks.
}
\comment{5200 - 600 comment words already}

\section{Compilation}\label{compiler}

Since different relational languages may provide different interfaces
to relations, we concentrate here on a few examples that seem likely
to apply (with perhaps minor modification) to almost any relational
language.  We describe in some detail iteration over a relation (which
includes testing as a special case) and in less detail adding a tuple
to a relation.  A compiler for a relational language uses data from
several different sources when compiling an operation on a relation:

\begin{itemize}

\item the declaration of the relation (its representation specification)

\item parameters of the operation describing semantic variants

\item other annotations

\item the library of building blocks

\end{itemize}

The parameters of operations indicate such things as the fact that a
tuple to be added is known to not already be present, which kind of
iteration over a relation is desired (described below), or the fact
that only one tuple is needed.  Other annotations come from the source
program.  The most relevant of these for our purposes are estimates of
relation sizes.  For instance the fact that most assemblies have many
subassemblies but only one superassembly could influence the choice of
testing algorithm.  The library of building blocks provides standard
interfaces for building block representations.  These do things like
generating code for particular operations on building blocks and
estimating the cost of that code.  In general these interfaces are
optional.  In many cases default methods can combine interfaces that
are supplied to build one that is not.  At worst,
the lack of support for some operations will simply make it impossible
to compile certain operations on relations that use the building
block.
\KBSE{In order to follow the examples below it is necessary to
understand the following building block interfaces.}

\IEEESoftware{
\subsection{Functions on building block descriptions}

The set of functions that should be supported by building blocks
clearly depends on the set of operations to be supported by the
relational language.  One guideline is that, since most building
blocks can be used by themselves to represent relatively simple
relations, the building blocks ought to support the operations on
relations, e.g., in order to support iteration over relations it
will help to support iteration over building blocks.  We certainly
do not claim that our current set is ideal for all relational
languages.  Rather we present some interfaces that we have found
useful for compiling efficient code to do relational operations that
appear frequently in our own specifications.  Most of these accept
parameters related to details of the operation to be performed, but
these are largely ignored below.

\i{Type}: Building blocks are, with one exception, data structures
that can be referred to by a single pointer.  One thing that the
translator needs to know, at least in a typed language, is the type of
data structure used to represent the building block.  This may depend
on such things as the (types of) slots and children of the building
block description.  For example, in order to declare a record type to
hold a tuple, it is important to know the types of the tuple elements.

The exception is that some root building blocks are represented by
data structures that are ``distributed'' among the objects that are
related.  An example is the use of a field in the records representing
assemblies.  The semantics required of building blocks prevents this 
from occurring in non-roots.
\comment{ justify that?  Suppose, for example, in
 the Shows-In relation, that we wanted to map from assemblies to lists
 of warehouses and store in a field of each warehouse the set of windows.
 This makes no sense unless we can guarantee that the set of windows is
 the same for every assembly (in which case assemblies really don't figure
 in the relation at all).  One might choose to have a different field for 
 each assembly, or to make the single field represent a relation between
 assemblies and windows, but this is just making the map from warehouses
 represent the entire relation rather than the required residue for the..}
Therefore the type function on root descriptions is allowed to return a 
special value indicating that the data is distributed among the slot objects.

\i{Restrictions}: Another function is provided to check that any
restrictions on the building block are satisfied.  One example is the
fact that many representations allow only one slot object or child
building block.  Another example is that some building blocks are 
restricted to certain types.  For instance arrays are generally only 
indexed by integers.  If we use an array map with a slot of type person, 
and people are represented by records, then this function should complain.  
Note that for this purpose it is convenient to require a function that 
maps abstract types such as person to a fixed set of implementation types 
such as array, record and integer.  Otherwise the restriction function 
would have to know about all abstract types that could be used to index
arrays.  Another example is that if we ask to hash on people, it
is necessary to determine whether a hashing function is available.
(This is, of course, conveniently handled by yet another function
on implementation types.)

All of the functions below produce algorithms that manipulate building
blocks.  In addition to producing code these are responsible for
estimating the cost of that code.  

\i{Create}: Other than ``distributed'' building blocks, the translator
needs to know how to create building blocks.  In general it might want
to be able to create them in states representing arbitrary sets of
tuples determined at run time.  The result of this function is a piece
of source code that creates a building block of the corresponding
description.  For instance, it might return code to allocate space for
a record.

\comment{
 Our implementation imposes one more restriction which is
 not strictly necessary.  It prohibits pointers to building blocks
 that represent empty sets of tuples.  For instance, if we remove
 the last element from the list of subassemblies then we destroy the
 list and store a null pointer (some representation of an empty list
 that does not take any other storage) in the field.  There are two
 reasons for this choice.  One is that it greatly simplifies the issue
 of storage reclamation.  If we eagerly reclaim storage then we do not
 have to worry about when to reclaim it.  The other reason is related
 to one of the iteration interface for relations described below.
}

\i{Destroy}: This is the corresponding function for cleaning up 
(typically deallocating storage) when a building block is no longer 
needed.  In systems with garbage collection it is generally a noop.
}

\i{Test/Fetch}: This provides code that tests whether a tuple of
objects is stored in a building block.  In the case of a \t{map} it
may also return the building blocks associated with the tuple.
(This is actually a special case of iteration described below.)

\i{Add/Add-new}: This provides code that adds a tuple to a \t{set} or
associates a tuple with a set of building blocks in a \t{map}.  (It
does not apply to \t{tuple}s.)  If the tuple is already there, this
is a noop for a \t{set} and it replaces the associated building blocks
in a \t{map}.  The Add-new variation assumes that the tuple is not
already present and is therefore faster in some cases.

\IEEESoftware{
\i{Delete}: This provides code that deletes a tuple and any associated
building blocks from a \t{set} or \t{map}.  In the case of a non-root
building block, if the last tuple is being deleted it may be required
to not actually delete the tuple but rather return a value indicating
that the building block is now empty.  In this case the building block
and the tuple with which it is associated may be removed from all parent
building blocks and the storage needed to represent them reclaimed.
}

\i{Test-add}: This is a combination of test and add.  It returns two
pieces of code, one to do a test and the other to do an add.  The
``test'' is allowed to make some temporary data available to the add,
which may allow it to be faster than a normal add.  For instance, a
hash table test would compute the hash table index and this could be
used by the add.

\IEEESoftware{
Analogous functions are provided for \i{test-delete} and \i{test-add-delete}.
}

\i{Iterate}: This provides code for iterating over the tuples and
associated building blocks of a \t{set} or \t{map}.  There may be
several ways of iterating over the same kind of building block.  These
are characterized in terms of which slots of the \t{set} or \t{map}
are inputs and which are to be generated.  If all the slots are inputs
this is very much like a test, since it results in one iteration if
the tuple of inputs is in the relation and otherwise none.  As an
example, suppose that we have an array indexed by time and place,
where each element is a list of people.  There are four possible
iterations.  The one in which both slots are outputs would iterate
over the entire array, for each (non-empty) element reporting the
time, place and (non-empty) list of people.  The one in which the 
first element was an input and the second was an output
would iterate over the row (or column) of the array corresponding to
an input time, and report for each (non-empty) element of that
row (or column) the place and list of people.

\subsection{Translation of iterations}

Iteration over a relation is analogous to iteration over a building
block.  One simplification is that there are no output building
blocks.  However, an additional complication is that slots may be
classified not only as inputs and outputs but also as ``any'' slots.
If the relation is Schedule(person, time, place), where the person
slot is an input, the time slot is an output and the place slot is an
any, then we need an algorithm which accepts a person and iterates
over all times that are related to that person (and any place).  A
nested representation that maps people to \t{map}s which map times to
\t{set}s of places can do this very efficiently if there is an
efficient algorithm for doing an input iteration (a test/fetch) on the
first \t{map}, an efficient algorithm for doing an output iteration on
the second \t{map}, and empty building blocks are eagerly reclaimed.
If empty building blocks are stored (for instance hash tables with no
entries) it will suffice to have an efficient way to determine whether
they are empty.  Otherwise it might be necessary to do more search in
order to make sure that there really was a place related to a
particular person and time.

Each iteration algorithm for a relation corresponds to a sequence of
building block descriptions in the relation representation specification,
where

\begin{itemize}

\item the first element of the sequence is a root,

\item every other building block description is a child of the one
before it, and

\item every building block is assigned one of its iteration methods.

\end{itemize}

Intuitively the algorithm looks like a nesting of iterations (where a
lookup is a special case of a loop that can only execute zero or one
times).  The outermost loop corresponds to the root.  The description
of the resulting composed algorithm assigns to each slot of the
relation the description assigned to that slot by the iteration
algorithm for the first building block description in the sequence
containing that slot, or if there is none then ``any''.  For example,
consider a description containing a \t{map} from people to
\t{map}s from times to \t{set}s of places, where the first map is 
assigned an output iteration and the second is assigned an input
iteration.  The resulting algorithm iterates over people that are
related to an input time and any place.  It iterates over the root map
to find all of the people in the relation.  For each person it looks
up the input time.  If it's there (and if either we eagerly reclaim
empty sets or we verify that the associated set is non-empty), then it
outputs the person.  Our translator can automatically convert output
slots of iteration algorithms to input slots or any slots.  That is,
an output iteration can be used to build an (inefficient) input
iteration by simply filtering out the undesired outputs.  This makes
it unnecessary, when adding a building block, to supply trivial
iteration algorithms.

The cost of the composed algorithm can be estimated from the costs of
the building block iteration algorithms along with the sizes of the
relations that the building blocks represent.  These are estimated
from the size characterizations of the original relation.  Our
translators actually support size characterizations with enough detail
to allow the translator to accurately estimate the sizes of building
blocks.  This facility can be used to tell the translator just what it 
needs in order to optimize a particular query.

\IEEESoftware{
As an example, suppose that we wish to test whether assembly Y is a
subassembly of assembly X.  Tests are implemented as iterations where
all slots are treated as inputs.\foot{In this case we also know that
at most one iteration will be needed, and this information is passed
in for purposes of optimization.} The question is which iteration to
use.  The answer depends not so much on the total size of the relation
as on the numbers of tuples in the relation that contain the
particular inputs to be tested.  For instance, if the value of X tends
to be an assembly with lots of subassemblies, the algorithm that
searches the list of children will be very expensive.  If, however,
the value of X tends to be an assembly with no subassemblies at all,
it might even be cheaper to do this iteration than to compare X with
the parent of Y.  The relevant information is the expected number of
parent and child assemblies of X and Y.  This information can also be
scoped so that different tests in the code to be translated can be
optimized for their own usage patterns.

In order to actually compile the test the compiler must examine the
possible algorithms.  A field map provides a very good input algorithm
- just fetch the field of the input object.  Notice that a field map
provides no output algorithm at all.  In this case there would be no
algorithm for generating all tuples of the subassembly relation.
Either field map produces a \t{set} for which there is an input
algorithm.\foot{In both these cases the input algorithm is really just
the same as the output algorithm filtered by an equality test.  Our
implementation supplies such algorithms automatically whenever they
are needed.} In the case where we start from the parent the total cost
of the test is the cost of fetching the field plus the cost of
iterating over the list and comparing each element with the child.
This of course depends on the expected number of children and the cost
of the equality cost.  In the other case the cost is the cost of
fetching the field plus one comparison.\foot{This assumes that the
singleton set representation is really only capable of holding a
singleton set, i.e., it cannot hold a null pointer.  This of course
requires every assembly to have a parent, which might not be
desirable.  If the representation is capable of holding a null pointer
then this might require additional overhead (checking for null).} The
algorithm with the lower expected cost is used to test the relation.

As pointed out above, it is possible for a specification to use an
iteration that cannot be supported by the representation.  This must
result in a translation failure.  In other cases the specification may
use an iteration that is not ``naturally'' supported by the
representation, but can supported nevertheless.  A special case of
this is the use of an output algorithm to simulate an input algorithm
as in the example above.  Output algorithms can also be used to
simulate ``any'' algorithms.  However, this may result in duplicate
tuples which must be removed in cases where duplication is not
allowed.\foot{In order to maintain the kind of efficiency associated
with normal programs our relational languages have incremental
interfaces to iteration algorithms.  That is, they ask for one tuple
at a time, and if the iteration terminates early, i.e., a satisfactory
tuple is found so the other tuples are not needed, then the cost of
the rest of the iteration can be avoided.  The incremental algorithm
for removing duplicates records in an internal relation the tuples
found so far.  Each duplicate-free iteration discards tuples until a
new one is found before returning.} Suppose that the Schedule relation
is implemented by hashing from people to hash tables that map from
places to lists of times.  Suppose, however, that the specification 
uses an iteration (without duplicates) over all times related to an 
input person.  The translator must find the
best way to specialize an overly general algorithm, i.e., one that
generates more than necessary.  In this case there are only two such
algorithms.  One iterates over all tuples of the relation and one
iterates over all tuples related to a given person.  Naturally we
would expect the second to be cheaper.  The resulting algorithm would
therefore hash on the input person to find the hash table representing
the residue relation between places and times.  It would then
iterate through that table.  For each set of times stored in the
table it would iterate over the set.  For each time in the set it
would check whether the time had already been returned, and if
not, return it.
}

\subsection{Translation of add/add-new}

The Add/Add-new function for relations is analogous to the Add/Add-new
function on building blocks.  It must produce code (and estimate its
cost) which, given a tuple of objects, adds the tuple to the relation
if it is not already there.  Not all representations support all updates.  
For example, the subassembly representation does not support the operation 
of adding a tuple, since the parent field can only represent singleton 
sets.\comment{  In our older
 relational language, the operation for adding a tuple was supposed to
 signal exceptions at run time to indicate that the representation was
 not capable of representing the result of an attempted update.  Our
 newer languages simply do not compile such updates.  Either another
 representation must be chosen (if we really expect to be able to add
 new tuples to the relation) or the specification must be rewritten
 to use more suitable operations.
}\foot{Typically the useful operations for updating relations with keys 
not only add a tuple but also delete any previous tuple with the same key,
e.g., delete any previous parent of the subassembly.  Such operations 
are likely to be presented in the syntax of the source language as 
``assignments'', e.g., make the parent of assembly A1 be assembly A2.}

An add involves several conceptually different tasks.  One is
determining whether the tuple is already in the relation.  If so the
add is a noop and no more work is needed.  (This does not
apply to the add-new case.)  If not, it is necessary to determine
which of the building blocks needed to represent the tuple already
exist and which do not.  Note that every tuple is represented by one
building block of each description in the relation representation
description.  These building blocks can be classified into three
groups.  There are some (near the roots) which need not be changed at
all.  These are the ones whose children already exist.  There are
others, near the leaves, that do not yet exist.  They must be created
and connected to their parents.  Since our translator only creates such
(non-root) building blocks non-empty it creates them from the leaves
up.  That is, a child building block is used as an input to the code
that creates a parent building block.  Finally there are those on the
boundary which exist but whose children do not yet exist.  These are
the ones that we really want to find.  To these we must add the
children that are to be created.  Of course, these boundary building
blocks generally cannot be found without first finding at least some
of their ancestors.

There are several opportunities for optimization in adding tuples.
First, we have to look up tuples in some building blocks which may or
may not already be there.  If they are not there we will want to add
them.  This motivates test-add algorithms.  Second,
the presence or absence of a tuple in one building block may
imply the presence or absence of a tuple in another one.  When we
know that the tuple is present we can improve the test-add to a fetch,
and when we know it is not we can improve it to an add-new.  Finally,
structure sharing presents choices of how to find building blocks.

The translator groups all of the building block descriptions in the
relation representation description by their slots*.  The import of
the group is that at most one member need be tested.  In particular,
the test of every member will return true iff the relation has a
non-empty residue with respect to the partial tuple assigning the
slots* slots to the corresponding elements of the input tuple, i.e.,
if the slots* slots of the input are already related.  More generally,
if a member of another group with a smaller (subset) slots* turns out
not to already exist, then this group need not be tested at all, e.g.,
if there is no tuple containing the given person, there's no need to
look for a tuple containing the given person and place.

\section{Related work}

In addition to our own relational languages, there are at least two
other set oriented languages.  These are Setl\cite{setl} and
Refine\cite{refine}.  These do not support general relations but
rather provide direct support for tuples, sets and maps.\foot{There
are some differences between the tuples, sets and maps described here
and those offered by Setl and Refine.  However, this characterization
is a close approximation to the net effect.} An extension to
Refine\cite{dtre} allows programmers to choose representations for
sets, maps and tuples, much as AP5 allows them to choose
representations for relations.  Setl has a somewhat more limited
facility (and has no facility for user extension).  The setl
researchers have also worked on automatically choosing efficient data
structures\cite{paige} for algorithms already written by programmers.

However, in these languages programs are written directly in terms of
maps, sets and tuples rather than in terms of the more abstract
relations which we have described here.  That is, one would have to
substantially rewrite the program in order to change the
representation of the Schedule relation from a \t{set} of \t{tuple}s 
to a \t{map} from places to \t{map}s from times to \t{set}s of people.  
This rewriting, as well as the corresponding part of the initial version,
is what out compiler does automatically.

Another form of related work is query optimizers that have been
written for relational languages.  These are necessary components of a
programming language that separates performance related implementation
decisions from behavioral specifications.  Consider, for example, a
program to find which parts in an assembly are available in a
warehouse.  There may be several ways to do this, e.g., iterating over
the parts in the assembly and for each checking whether it is in the
warehouse, or iterating over the parts in the warehouse and for each
checking whether it is in the assembly.  Since the choice of algorithm
depends on the representations of the relations (or at least what
operations they support and at what cost), it certainly does not
belong in the specification.  Furthermore, since representation
decisions should be easy to change, it makes no sense for the
programmer to expend any effort choosing algorithms that depend on
particular representation choices.  Instead he should write the
specification in a form that does not commit to a particular
algorithm, e.g, using the language of relational calculus, and rely on
a query optimizer to find an algorithm suitable to whatever
representations are eventually chosen.  There are many query
optimizers for relational languages supported by database
systems\cite{ullman}.  These generally optimize on the basis of a cost
model, and generally support a variety of representations. However the
set of representations cannot typically be extended by programmers,
and both the representations and optimization strategies are
specialized to large disk resident sets of data.  In AP5 we have
provided optimizers for relational calculus\cite{wff-compiler}, for
rule triggering\cite{triggering} and several other small languages for
defining relations in terms of other relations (such as transitive
closures, summations, maxima, etc.).

\section{Current status and future directions}

Our group is still in the early stages of building a new family of
relational languages.  We are currently building a new relational
extension to commonlisp and our first relational extension
to Ada.  We also forsee a relational extension to C++.  At the moment
our compiler for relations composed of building blocks only produces
lisp code, but we expect retargeting to be very easy.  (The same is
true of the compiler for relations defined by relational calculus.)
The building block library is still quite small.  It does, however,
include all of the building blocks used in the examples, with the
exception of small-hash-map and record-tuple.  (In AP5 we used lists
to represent tuples, and these are in the library.)  Of course, the
building blocks themselves must also be extended to produce code for
different target languages.  Finally we need to provide compilers for
more operations on relations.  So far we have concentrated on the
minimal set used in AP5: iteration (including test, fetch), add and
delete.  The next priorities are assignment and an operation to remove
all tuples (needed for destroying relations in languages without
garbage collection).  We are also very interested in lingustic support
for residues.  For instance, we would like to be able to iterate over
the people in the Schedule relation and inside the iteration treat the
residue for that person as another relation which could be tested,
added to, etc.  Operations analogous to test-add for relations would
be a special case of these residue relations.  (The add would be to a
zero-ary residue defined with respect to a complete tuple.)  We later
hope to experiment with various kinds of rules in these languages
similar to the kinds we already use in AP5.

\section{Conclusion}

We have described a language which allows a programmer to succinctly
describe composite representations for relations, and a compiler that
implements relational interfaces to the representations described in
that language.  The language allows nested data structures, redundant
representation of data and shared data structures.  The compiler is
analogous to a query optimizer in that it searches a space of possible
algorithms and evaluates each with respect to a cost model in order to
choose an implementation for a relational interface.

\bibliographystyle{plain}
\bibliography{/user/donc/tex/kbse}
%\newpage
%\pagenumbering{roman}
%\setcounter{page}{1}
%\tableofcontents
\end{document}



\parskip=4pt

----------------------------------------------------------------

He may also use a relational expression to 
describe what he wants, e.g., find all assemblies in a particular
warehouse containing parts built by a given company.  In this case he
also relies on a query optimizer

----------------
intro1

``Automatic programming'' may be viewed as the development of higher
level programming languages along with compilers for these languages
that deliver code with acceptable performance.  The term ``higher
level'' really just means that more of the programming task is taken
care of by the compiler.  While some research in automatic programming
has aimed at an ultimate specification language, a great deal of
progress has been made by analyzing relatively small programming tasks
that occur frequently, and designing small specialized languages
(along with compilers) for these tasks in which programmers can
succinctly describe what they desire.  An old example is the loop
macro, which is now part of Common Lisp.\ref{interlisp}\ref{commonlisp}  
This allowed programmers to replace code like this:

\code{
; print the elements of list in prime positions
(prog (i tail x)
   (setq i 1)
   (setq tail list)
 label
   (cond ((null tail) (return)))
   (setq x (car tail))
   (cond ((prime i) (print x)))
   (setq tail (cdr tail))
   (setq i (+ i 1))
   (go label))
}

with code like this:

\code{
(loop for x in list as i from 1 when (prime i) do (print x))
}

We hope that readers will agree that the second program is easier to
read, write, debug and maintain.  Our efforts over the last several
years have concentrated on the use of relational abstraction in
programming\ref{ap5}.  This means that we have provided facilities
that allow programmers to think of most of their data and much of
their computation as relations.  For instance, we want to relieve the
programmer of the need to write code that depends on the fact that a
record representing an assembly has a field that contains a linked
list of pointers to records representing its subassemblies, and that
the record representing the subassembly has a field that points back
to its parent assembly.  For that matter, we want to relieve the
programmer of the need to write code that searches up the parent
links.  Instead he should write code in terms of relations such as
that between parent and child assemblies and the transitive closure of
that relation (which is another relation).

An ideal compiler for such a relational language would automatically
determine how each relation should be represented in order to obtain
optimal performance.  We do not claim that we can write such a
compiler.  Rather we ask the programmer to make such decisions.  In
particular, he should be able to say with a very brief annotation that
the relation between parent and child assemblies is to be represented
by storing the parent in a field of the child and a list of children
in a field of the parent.  Having said this, the compiler can then
translate all of the references to that relation into the appropriate
references to the underlying data structures.  The compiler makes such
optimization decisions as how best to test whether one assembly is a
subassembly of another.  In this case, it would decide to compare the
second with the parent field of the first, rather than searching the
list of children of the second.  In general the programmer also has to
supply size estimates, e.g., the number of subassemblies of a typical
assembly, in order for the compiler to estimate costs and thereby
rationally choose among alternative algorithms.  These are used by a
number of such compilers, such as the one that produces code for
transitive closures and another one that handles relations defined in
terms of relational calculus expressions.\ref{wff-compiler}  In our
relational languages to date all size estimates have been optional.
Where they are not supplied the compilers simply make default
assumptions.

In previous versions of our relational languages a programmer could
very succinctly choose a representation for a relation from a library
of representations.  The library could be extended with new
representations, but this was much more difficult than choosing one
already in the library.  For this reason programmers tended to use the
library representations if at all possible.  This paper describes a
small language in which programmers can describe many representations
such as the one above by composing elements of library of building
blocks.  As before, it is much easier to to use building blocks that
are already in the library than to add new building blocks to the
library, but we anticipate that a small number of building blocks will
be sufficient to cover almost all needs.

The small language for describing composite representations actually
has very little to do with relations.  We expect that it could be used 
for other purposes as well.  We also describe interfaces to these 
composite representations that were defined for our relational
languages.  Even these are quite general, in the sense that very
similar interfaces would probably be used for any other use of such
composite data structures.

----------------
intro2


This paper describes how a common programming task can be automated.
In particular we have:

\begin{itemize}

\item analyzed the task in order to determine what choices the programmer
is really making and which of these can be readily automated,

\item defined a small specification language in which the programmer can
succinctly and formally describe those choices that cannot be readily
automated, and

\item written a compiler for that language that carries out the choices 
in a specification and automatically makes the other choices.

\end{itemize}

The problem that we attack here is the composition of data structures.
The programmer will start by determining what representation he wants
to use for certain data.  For instance, he might decide that he wants
records representing assemblies to include a field containing a linked
list of pointers to the records representing their subassemblies, and
that each subassembly should also have a field holding a pointer to
its parent assembly.  The programmer will communicate this decision by
writing a specification in our small language.  However, he will not
write any code that actually depends on this decision.  Instead he
will write code in terms of another specification language that
provides standard access methods to that data, e.g., he may ask
whether one assembly contains another, or iterate over the
subassemblies of an assembly.  The standard access methods will be
implemented by a compiler which understands both specification
languages.  The obvious benefit is that the programmer has less code
to write.  Another benefit is that the specification remains
independent of the representation decisions.  To the extent that
performance is influenced by these decisions, the program can then be
tuned by changing only the representation specifications, which cannot
affect the behavior of the program (other than its performance).

----------------
intro3


This paper describes the automation of a common programming task,
namely writing code to access and update data structures.  In
particular we address the problem of composing complex data structures
out of primitive data structures.  In the style of programming we wish
to support, the programmer will still choose representations for his
data.  For instance, he might decide that he wants records
representing assemblies to include a field containing a linked list of
pointers to the records representing their subassemblies, and that
each subassembly should also have a field holding a pointer to its
parent assembly.  However he will describe these choices to a
compiler, not in terms of code, but a more natural and higher level
specification.  He will write programs in terms of a standard set of
high level operations which will be implemented by the compiler.
These will include such operations as testing whether a given assembly
is a subassembly of another, iterating through the subassemblies of a
given assembly, or making one assembly be a subassembly of another.

In essence we have been able to characterize a very large (though
perhaps not universal - this is discussed below) subset of the ways in
which programmers use data structures in terms of a small formal
language.  In this language the programmer expresses the same sort of
information expressed informally in the example above.  The next
problem is to write a compiler to implement the standard set of high
level operations.  Of course, different standard sets are possible.
We describe compilers for a few of the operations that are likely to
be present in almost any standard set.  There are, in general, many
different ways to implement a standard operation.  The compilers we
describe optimize on the basis of a cost model which is supplied
partly by the library of primitive data structures and partly by the
programmer.

----------------
intro4

\section{Introduction}

The goal of the work described here is to support a style of
programming in which the programmer first thinks about the desired
behavior and only later, when the behavior is correct, thinks about
performance.  In particular, data representation decisions are
regarded as performance tuning.  We therefore wish to make it trivial
to make and change these choices.  The program is separated into a
``specification'' in which all data is modelled in terms of objects
and relations, and ``annotations'' which do not affect whether the
behavior adheres to the specification, but only the resulting
performance.  The specification language provides such operations on
relations as adding tuples, iterating over the tuples, and testing
whether a tuple is in the relation.

One important component of such a programming language is a query
optimizer.  The programmer cannot optimize queries that involve more
than one relation without knowing anything about how those relations
are represented.  He must therefore write a specification in a way
that does not commit to a particular algorithm, e.g, using the
language of relational calculus, and rely on the query optimizer to
find an algorithm suitable to the representations which will be chosen
later.  In our previous relational languages\cite{ap5} we have provided
such optimizers for relational calculus\cite{wff-compiler}, for rule
triggering\cite{triggering} and for a few other idioms available for
defining relations in terms of other relations (such as transitive
closures, summations, maxima, etc.).  In this paper we discuss another
kind of query optimizer.

In previous versions of our relational languages a programmer could
very succinctly choose a representation for a relation from a library
of representations.  The library could be extended with new
representations, but this was much more difficult than choosing one
already in the library.  For this reason programmers tended to use the
library representations if at all possible.  This paper describes a
small language in which programmers can describe many representations
by composing elements of a library of building blocks.  As before, it
is much easier to to use building blocks that are already in the
library than to add new building blocks to the library, but a very
small library of building blocks can be combined into a very large
set of compound representations.

\subsection{Example}

Suppose that a programmer is writing a program that deals with groups
of parts combined into assemblies, where these are in turn combined
into larger assemblies, etc.  The objects in this domain would most
likely include parts and assemblies.  The relations would include
things like Subassembly, i.e., one assembly is a subassembly of
another.  A programmer might make the following representation
decision(s): 

{\em Assemblies will be represented by records containing a
``children'' field which will hold a (pointer to a) linked list of
their subassemblies and a ``parent'' field which will hold a pointer
to the parent assembly if any (there can be at most one).}

This paper describes a small language in which the programmer can
formalize this decision.  It also describes how a compiler can
implement such specification level operations as testing whether one
assembly is a subassembly of another.  In this case there are two ways
of doing that.  In order to make a rational choice the compiler has to
estimate the cost of comparing the first to whatever is in the parent
field of the second with the cost of comparing the second to each of
the elements in the list contained in the child field of the first.

----------------------------------------------------------------

----------------

\comment{*** include this? - another paper?  A related topic, how general
are relational languages?  point out that assignment of global var can be 
done at right cost}
\subsection{How general are relations?}

Our data structures have thus far been defined in terms of relations.
While such familiar technologies as relational databases and logic
programming illustrate that relations are quite expressive, the reader
may very well wonder whether they provide an adequate replacement for
{\em all} data structures found in programming.  Indeed even if
relations can {\em express} the meaning of all of the information that
real programs use, can they do so with efficiency comparable to that
of the data structures now used.

stack/queue
sequences with insertion?
- consider the example of an array of employee, project, percent records
sorted by employee, along with an ``index'' which is an array of records
containing employee and the index into the other array where the employee
first appears.  This is similar but not identical to a sorted alist of
employees.

We have identified along the way some of the restrictions that our
implementation places on our data structure compositions, e.g., we do
not allow tuples of tuples, every \t{map} and \t{set} must have more
slots* than its parents, etc.  A more general question is how well the
relations represented by our compositions (and by building blocks
themselves) cover the actual uses of data structures by programmers.
Of course, data structures are used to represent not only relations
but also objects.  However, the representations of objects are also
covered by our scheme, in that they are generally drawn from a small
library, and the programmer need not write programs that depend on
these decisions, since the ``structure'' of the objects is naturally
modelled by relations.  For instance, given that some of the fields of
records representing assemblies are devoted to the subassembly
relation, there is no need for the programmer to deal with these
fields directly.  

One restriction on relations is that they have fixed arity.  For
example, one might wish to represent a set of sequences of varying
length, e.g., the words in the dictionary, by a discrimination net,
which is a nested structure of varying depth.  One way to model this
would be, in effect, to alter your idea of what the domain objects
are.  Rather than words, one might choose set of tails of words.
In particular, the set of all words would be one such set of tails.
In this case a set of tails might be implemented as an array of 26
sets of tails (or empty markers).  This would be used to store what
we could now regard as a three place relation between sets of tails, 
letters, and other sets of tails, namely that the subset of the first
set that starts with the letter is the result of adding that letter to
the head of each element of the second set.  This is rather 
unsatisfying, however, since we would hope that the specification
in terms of objects and relations allows us to express things in the 
most natural way.

Another approach is to add discrimination nets as a primitive 
representation for sets of sequences.  Unfortunately, 
discrimination nets can be built out of many different data structures,
e.g., arrays, records, hashtables, etc.  Of course, these all just 
correspond to different kinds of \t{map}s, and one could imagine
adding a discrimination net as a primitive with a parameter that
named a \t{map} representation, similar to the tricks with singleton
sets.

  These were not strictly necessary, but
we consider them beneficial in that they seem to prevent nothing
useful.  One exception is the prohibition of pointers to empty
building blocks (also called eager garbage collection), was imposed
in order to guarantee that certain useful operations would be fast.
Nevertheless, it would make sense to relax this restriction in some
cases.

----------------

Actually, in our implementation,
representations are just subclasses of a class of building blocks, and
building block descriptions are instances of those classes.  Of
course, the important point is that these descriptions can be passed
as arguments to (virtual or generic) functions that tell us how to
implement various operations on the building blocks that they
describe.

  The restrictions
above are all checked by our implementation.

  We have implemented
translators which produce code for these kinds of operations.  These
in turn make use of relation representation specifications,
information about the size of the relation, and some capabilities to
produce code for and and answer questions about the underlying
building blocks.  The translator processes a relation representation
specification by creating a set of building block descriptions of the
appropriate types, filling in their slots and children, checking that
the result satisfies various constraints, and packaging them up into
an object describing the relation.  Source code that accesses this
relation is translated by calling (virtual or generic) functions on
this relation description.  These functions in turn call (virtual or
generic) functions on the building block descriptions used by the
relation description.



\subsection{Access to residues}

We have not proposed such operations as test-add for composed relations.
Instead we hope to provide a much more general capability which allows
the translator to make use of the nested structures in the same way that
a programmer might.  This capability is the use of residues as relations.
As an example, consider the following pseudo-code:

\code{
If window W is in the Shows-In relation 
   then ...
   else relate assembly B and warehouse C to W
}

If it happens that Shows-In is represented as a \t{map} from windows to
other \t{map}s then we would like to start with a test-add on this \t{map}
in which we look up W and remember enough to efficiently do the add in the 
else case.  We propose to formalize our pseudo-code as follows:

\code{
let R be residue Shows-In(W,_,_) in
If R(any, any)
   then ...
   else add R(B, C)
}

The translator would see that within the scope of the residue declaration
was a test of R(any, any) and an add of R.  


----------------
when can tuples be shared by parents with different slots*
which sharing is disallowed

conclusion - more usefulness than seen in real programs, like triggers?

how about
tuples of s1,s2 where one parent binds s0 and the other s0, s1

array(s0) => list (tuple)

----------------
instructions for making diagrams with framemaker
run framemaker - xmaker on lax
draw picture - lower left corner is easiest to use
save file for editing
print to file only to get .ps version
do maker2ps fmport file.ps file.pp
include in latex file as in examples in this file
compile with latex - on LAX (needs psfig)
do dvips kbse.dvi to convert dvi file to ps file
gs kbse.ps (ghostscript) to show it on xwindow
lpr -Pps11a kbse.ps to print it


NeilC suggestions

- intro use 2 or 3 text editor representations, no formal spec
describe similarity of different kinds of maps

use editor as much as possible - first example

kbse - mention create, delete, destroy - 1 sentence

each iteration:  add intuitive description, inc example
 -- need formality?
