% File: locality.tex
% Needs files locality1..7.tex, florian.bib
% Status: 15-JAN-1990 by Florian
% Status: 15-NOV-1990 by Atsushi
%
\documentstyle{article}

\setlength{\topskip}{0truecm}
\setlength{\textwidth}{13.5truecm}
\setlength{\textheight}{20.0truecm}
\pagestyle{empty}
\renewcommand{\sc}{}
\newcommand{\parskipsize}{8pt}
\setlength{\parskip}{\parskipsize}
\newcommand{\vbar}{\mbox{$\ |\ $}}
\newcommand{\asgn}[2]{#1\,:=\,#2}
\newcommand{\deref}[1]{!#1}
\newcommand{\funtype}[1]{\stackrel{#1}{\func}}
\newcommand{\bdt}[1]{\{#1\}}
\newcommand{\locality}{{\cal L}}
\newcommand{\code}[1]{\mbox{{\tt #1}}}
\newcommand{\torder}{\ll}
\newcommand{\typing}[3]{#1\rhd#2\,:\,#3}
\newcommand{\ctyping}[2]{\models #1\,:\,#2}
\newcommand{\record}[1]{[#1]}
\newcommand{\reduction}[5]{#1\vdash(#2,#3)\Longrightarrow(#4,#5)}
\newcommand{\repenv}{{\cal E}}
\newcommand{\clocality}{{\cal L}^c}
\newcommand{\eass}{\emptyset_{{\cal A}}}
\newcommand{\evenv}{\emptyset_\varenv}
\newcommand{\erenv}{\emptyset_\repenv}
\newcommand{\ass}{{\cal A}}
\newcommand{\basetype}{{\cal B}}
\newcommand{\dotl}{.\:}
\newcommand{\env}{\varepsilon}
\newcommand{\exlabelwidth}{17ex}
\newcommand{\exsep}{\hspace*{0.5cm}}
\newcommand{\func}{\rightarrow}
\newcommand{\glb}{\sqcap}
\newcommand{\kwd}[1]{\mbox{{\bf #1}}}
\newcommand{\lub}{\sqcup}
\newcommand{\order}{\sqsubseteq}
\newcommand{\psep}{\hspace*{0.5cm}}
\newcommand{\qed}{\mbox{\ \rule{0.6ex}{1.8ex}}}
\newcommand{\rvsep}{\vspace*{12pt}}
\newcommand{\rvpselim}{\Longrightarrow}
\newcommand{\sel}{\bm{.}}
\newcommand{\sepr}{\hspace*{0.6cm}}
\newcommand{\sep}{\hspace{0.6cm}}
\newenvironment{program}{\setlength{\parskip}{0pt}\begin{tt}\begin{tabbing}\hspace{1cm}\=\+\kill}{\end{tabbing}\end{tt}\noindent\setlength{\parskip}{\parskipsize}}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{cor}{Corollary}
\newcommand{\vsep}{\vspace*{4pt}}
\newcommand{\rulelab}{14ex}
\newcommand{\rulecr}{\\ \sepr\makebox[\rulelab][l]{}}
\newcommand{\axiom}[2]{\sepr\makebox[\rulelab][l]{#1}#2}
\newcommand{\axiomc}[3]{\sepr\makebox[\rulelab][l]{#1}#2\sep#3}
\newcommand{\ruleone}[3]{\sepr\makebox[\rulelab][l]{#1}\begin{tabular}{c}#2\\ \hline #3\end{tabular}}
\newcommand{\ruleonec}[4]{\sepr\makebox[\rulelab][l]{#1}\begin{tabular}{c}#2\\ \hline #3\end{tabular}\sep#4}
\newcommand{\ruletwo}[4]{\sepr\makebox[\rulelab][l]{#1}\begin{tabular}{ccc}#2&\sep&#3\\ \hline \multicolumn{3}{c}{#4}\end{tabular}}
\newcommand{\ruletwoc}[5]{\sepr\makebox[\rulelab][l]{#1}\begin{tabular}{ccc}#2&\sep&#3\\ \hline \multicolumn{3}{c}{#4}\end{tabular}\sep#5}
\newcommand{\rulethree}[5]{\sepr\makebox[\rulelab][l]{#1}
                         \begin{tabular}{ccccc}#2&\sep&#3&\sep&#4\\ \hline
                         \multicolumn{5}{c}{#5} 
                         \end{tabular}}
\title{Typing Schemes for Objects with Locality}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\author{\small \begin{tabular}{c}
Florian Matthes\footnotemark[1]\rvsep\\
{\footnotesize
\begin{tabular}{c}
Dept.\ of Computer Science\\
University of Hamburg\\
Schl\"uterstra\ss e 70\\
D-2000 Hamburg 13, FRG\\
\ 
\end{tabular}
}
\end{tabular}
\begin{tabular}{c}
Atsushi Ohori\footnotemark[3]\rvsep\\
{\footnotesize
\begin{tabular}{c}
Kansai Laboratory\\
OKI Electric Industry\\
Crystal Tower\\
1-2-27 Chuo-ku\\
Osaka 540, Japan
\end{tabular}
}
\end{tabular}
\begin{tabular}{c}
Joachim W.\ Schmidt\footnotemark[1]\rvsep\\
{\footnotesize
\begin{tabular}{c}
Dept.\  of Computer Science\\
University of Hamburg\\
Schl\"uterstra\ss e 70\\
D-2000 Hamburg 13, FRG\\
\ 
\end{tabular}
}
\end{tabular}}
\date{}

\begin{document}
\bibliographystyle{alpha}
\maketitle

\thispagestyle{empty}

\footnotetext[1]{
This work was supported in part by the European Commission unter
ESPRIT BRA contract \# 4092 (FIDE).}
\footnotetext[3]{
Most of the work presented here was carried out during the second
author's visit to the University of Glasgow supported by a British
Royal Society Research Fellowship.}

\begin{abstract}
\noindent 
The crucial characteristic of object-oriented databases is the concept of
object identity which allows the direct representation of various kinds of
dependencies between objects, for example, sharing and cyclicity. For
object stores to become a viable technology for large shared databases, a
certain degree of spatial control over object dependencies (or object {\em
locality\/}) seems to be essential. This paper exploits the power of a static
type system to capture and evaluate locality information on objects. First, we
represent objects by {\em references\/} to complex expressions in a functional
language. To control the locality of objects, the space of references is
partitioned into a set of subspaces with an explicit {\em reachability
constraint}. Next, we define a type system where the locality of an object is
part of its static type specification and the predefined reachability
constraint is enforced via a static typing discipline. We conclude by
highlighting the impact of locality information on the operational support to
be expected by next generation database systems.
\end{abstract}

\input{locality1}

\input{locality2}

\input{locality3}

\input{locality4}

\input{locality5}

\input{locality6}

\input{locality7}

\section*{Acknowledgement}
The authors would like to thank Malcolm Atkinson for stimulating
discussions on controlling object locality. The second author
also thanks John Launchbury for his comments about our earlier results
on type inference.

\bibliography{florian}

\end{document}

