% File: locality1.tex
% Status: Last edit by Florian on 08-JAN-1990
%
\section{Introduction and Motivation}
\label{sec:intro}

Object-oriented data models are based on the notion of {\em object
identity\/}, i.e.\ ``the ability to distinguish objects from one
another regardless of their content, location, or addressability''
\cite{KhCo86}. They thereby relieve database modelers and programmers
from the tedious and error-prone ``manual'' management of key values
and their associated uniqueness and referential integrity
constraints as required, for example, in relational databases.

This shift from copy semantics to reference semantics in database
systems, together with recent advances in computationally complete
database languages reinforces the interest in persistent {\em object
stores\/} \cite{ABM88}, providing long term storage of and
shared access to data objects and code fragments with mutual
cross references via object identifiers. There is, however, an
increasing awareness of the {\em problems of scale} that have to be
solved in order to make object stores a viable technology for large
scale, multi-user or distributed databases. 

A promising approach to the solution of these problems is to partition
the logically homogeneous object store into disjoint {\em
repositories\/} (files \cite{CDeW88,CDJS86}, pools \cite{Moss89},
databases \cite{ACC81a,ABCCM83}) and to localize objects in these
repositories.  Despite a great deal of research and implementation
efforts in object-oriented databases and persistent programming, very
little is known about the properties of such repositories, the
localization of objects in repositories and, most importantly, the
dependencies between objects induced by the creation and propagation
of object identifiers.  

The interest of this work is to integrate the advantages of a
partitioned store into a data model for complex objects.  Furthermore,
we would like to achieve this integration within a typed programming
language so that the database programmer can also enjoy the benefits of
a static type system.
 
In this paper, we propose an abstract partitioning mechanism of an
object store in a type system of a programming language. We model
objects through {\em references\/} to complex expressions, as they are
implemented in Standard ML \cite{HMT88}. In contrast to Standard ML,
however, our reference space is partitioned into disjoint
repositories. Each repository is associated with a set of repositories
representing the {\em reachability set\/} of the repository to other
repositories. We then develop a static type system to reason about the
dependency of a value to repositories (or the {\em locality\/} of a
value).  In the type system, the locality of a value is represented as
part of its type and the reachability constraint among repositories is
enforced by a static type discipline.

The main goal of this paper is to analyze the problem of object
locality control and to explain our solution with emphasis on the
rationale behind the type system. The reader is referred to
\cite{OMS90} for a complete description of the type system and proofs
of various technical properties. The paper is organized as follows. In
section~\ref{sec:objects}, we set the stage by defining a core
database language with records, collections, references and
repositories. Section~\ref{sec:types} develops a type system for that
language. We introduce first the notion of types and localities and
then define type checking rules. The proof of the soundness of these
rules with respect to the run-time evaluation of the language is
the subject of section~\ref{sec:sound}.  Section~\ref{sec:typeinf}
outlines a method to develop a type inference system for objects with
locality.  The paper concludes with a discussion of the use of static
locality information in database systems and describes possible
extensions to our type system.


