\section{An Abstract Store Model}

The store is the component of the abstract machine that models
the database. The operational semantics of queries is defined to
a large extent in terms of accesses and manipulations of its
elements. The store model and its relationship to other data
models are described below.

\subsection{The Goals}

The primary goal is to serve as a basis for defining the
operational semantics of query languages. The model does not
include details of physical data organization, indices, storage
hierarchies, and buffer management. We view a database as a
large collection of (possibly interrelated) entities, as it can
be found in modern persistent object stores
\cite{Moss90,BrMo92}. The store may contain both persistent and
volatile entities; we strive to treat them uniformly.
 
Current implemented or proposed data models include a large
variety of features: data types such as records and arrays; bulk
data types such as sets, bags, lists, maps and trees; object
features such as identity, {\em is-a} relationships, methods and
encapsulation. We want our approach to semantics to be
applicable to a wide range of query languages. One possible
approach to addressing this diversity of concepts is to define a
rich model that contains ``all'' features. We have chosen the
opposite approach of a very simple model, where various
conceptual models, from value-based to object-based, can easily
be mapped to it. Semantics for a specific query language over a
given model can be defined by a mapping to our model, and by
providing the semantics in our model. Although some features
found in existing models have no direct mapping to our model, it
covers a large variety of features and can be easily extended.
The approach presented in this paper can also be adapted
directly (without translation) as another data model.

The ideas treated in the paper do not require a specific
(monomorphic, polymorphic) type discipline nor precise data
representation details. Types are very important for enforcing
static constraints on the use of queries and procedures;
however, they are irrelevant to the goals of this paper, hence
are not discussed.
 
\subsection{The Model}
  
Intuitively, a stored database (at a given point of time)
consists of a collection of stored entities which we call {\em
store objects}\footnote {These should not be confused with the
conceptual objects of object-oriented models.}. There are three
components in a store object: (1) its location; (2) the name
that can be used to denote it; (3) the value stored there, i.e.,
its content.  As we are not interested in physical organization,
we represent locations abstractly, using the concept of
$l$-value from programming language semantics. Atomic values,
records, components of records, conceptual objects, are all
store objects: each one of them resides somewhere in memory and
needs location for internal identification, in order to be
retrieved, updated or deleted.  For us, these locations have no
structure or meaning, except that they can be used to access
objects; queries do not refer to them or use their values in any
way. In the sequel, to emphasize their abstract nature,
locations are called identifiers.
 
Names are among the basic building blocks of queries and, in
general, of program expressions. Their bindings are an important
component of semantics, and a central topic in this paper. While
for general programming languages names used in a program are
normally defined in the program itself, most of the names used
in queries are defined in the database.  That is, we are dealing
with persistent data where names are an inherent part.
  
The contents (i.e., the $r$-value) can be an atomic or complex
value, or a location.  As for the names, we assume that each
store object contains one value. As seen below, more than one
value associated with an object is modelled by creating many
objects.

Formally, let $I$ be a set of {\em identifiers}, $N$ be a set of
{\em names}, and $V$ be a set of atomic values. We make no
assumption about $V$; it may contain numerals, strings,
graphics, compiled procedures, and so on.  Atomicity of the
elements of $V$ means that we do not assume the existence of
operations that refer to their parts. We assume $I \cap (V \cup
N) = \emptyset$; however, $N$ and $V$ are not required to be
disjoint. It is possible, even common, that programs compute
values, then use them as names, e.g., integers  are used as
array indices. Generally, some stored values can be used as
names of store objects; this property supports genericity of
programming. In many languages, for example Ingres/Windows 4GL
\cite{Ingr90}, LOQIS \cite{Subi91} and F-logic \cite{KL89}, data
names are first-class citizens.
 
A {\em store object} is a triple $<i, n, \vartheta>$, where $i
\in I , n \in N$, and $\vartheta$ are its identifier, name, and
value, respectively. We say that $i$ identifies this object. The
value $\vartheta$ can be one of the following:
\begin{itemize}
\item An atomic value from $V$.
\item An identifier from $I$. This identifier, as the value of
the store object, serves as a (logical) pointer to another store
object.
\item A set of objects.
\end{itemize}

We refer to these three types of objects as {\em value-objects},
{\em pointer-objects}, and {\em set-objects}, respectively.
Objects of the first two types are called  {\em atomic}, those
of the third type are called {\em complex}. Nesting of
set-objects allows us to represent arbitrarily complex objects
with hierarchical structure.  Below is an example of a complex
object, consisting of three atomic objects.
\begin{tabbing}
\hsmall$ <i_5, EMP, \{$ \=$<i_{51}, NAME, Smith>,$ \\
                      \>$<i_{52}, SAL, 2000>, <i_{53}, WORKS\_IN, i_6>
\: \} \: >$ 
\end{tabbing}
In the following, ``object'' always means store object,
unless specifically noted otherwise.

A {\em store} is a set $S$ of store objects, and set $R$  of
identifiers of designated {\em root} objects. We make no
assumption that elements of $R$ refer to the top hierarchy level
of store objects: sometimes elements of $R$
refer to objects nested in other objects. We assume that $S$
satisfies the obvious constraints: An element $i \in I$ is used
in it at most once as an identifier; that is, there is a
one-to-one correspondence between the set of identifiers used in
a database, and the set of objects in it. If an identifier is
used as a pointer, then it is also used as an identifier
(referential integrity). We also assume that each root
identifier actually identifies an object in $S$. By definition,
objects inaccessible from $R$ (directly or indirectly) do not
exist. As we will see later, we build over the set $R$ some
structure which we will call {\em environment stack}. The
persistence status of objects is irrelevant in our approach;
indeed, there is no essential semantic property that can make
distinction between querying persistent and volatile data. (The
orthogonality of types, queries and persistence is assumed in
many modern DBPLs \cite{ACO85,MRSS92a,MBCD89,OBB89,ScMa92,Subi91}.)
 
We re-emphasize that the identifiers are {\em internal} -- they
are not used in queries or programs, and are not printable.  A
one-to-one mapping of all identifiers to another collection of
identifiers cannot be recognized from the outside. The names are
{\em external} in the sense that they are used in queries --
they are part of the users' model.
\begin{examp}
The following is an example store. The root objects are \vsmall \\
\hsmall $\{ i_1, i_5, i_9, i_{13}, i_{17}\}$.
\hsmall \\
{\small 
\begin{center}
\begin{tabular}{|lll|}
\hline &&\\
 &&MyDatabase:\\ &&\\
$<i_1,$ & $EMP,$ & $\{<i_2, NAME, Brown>, $\\
        &&\hspace*{1.7mm}$<i_3, SAL, 2500>, <i_4, WORKS\_IN, i_{13}> \}>$\\ &&\\
$<i_5,$ & $EMP,$ & $\{<i_6, NAME, Smith>, $\\ 
        &&\hspace*{1.7mm}$<i_7, SAL, 2000>,  <i_8, WORKS\_IN, i_{17}> \}>$\\ &&\\
$<i_{9},$ & $EMP,$ & $\{<i_{10}, NAME, Jones>, $\\
          &&\hspace*{1.7mm}$<i_{11}, SAL, 1500>, <i_{12}, WORKS\_IN, i_{17}> \}>$\\ &&\\
$<i_{13},$ & $DEPT,$ & $\{<i_{14}, DNAME, Toy>, $\\
           &&\hspace*{1.7mm}$<i_{15}, LOC, Paris>, <i_{16}, LOC, London> \}>$\\ &&\\
$<i_{17},$ & $DEPT,$ & $\{<i_{18}, DNAME, Sales>, $\\ 
           &&\hspace*{1.7mm}$<i_{19}, LOC, Berlin>\}>$\\ &&\\
\hline
\end{tabular}
\end{center}}
\vsmall
\noi  Note that an object  WORKS\_IN stores an identifier of a
department object. If instead it contained, say, a department
name, the example would be value-based. If additionally we
disallow multiple LOC objects for a department, we obtain a
relational database.
\end{examp}
\noi In examples we also use the schema presented in
Fig.\ref{fig3}.  It has redundancy allowing us to demonstrate
different styles of querying, e.g. relational and navigational.
Arrows denote pointers, and symbols 1 and n denote a 1:n
relationship. For example, EMPLOYS denotes pointer-objects
inside DEPT objects; a DEPT objects can contain many EMPLOYS
objects.  Similarly, LOC and PREV\_JOB are multi-valued
attributes.
 
\begin{figure}[htb]
\begin{center}
\leavevmode
\epsfxsize=10cm
\epsffile{fig3.eps}
\end{center}
\caption{A database schema used in examples}
\label{fig3}
\end{figure}
 
\subsection{Discussion}
\label{section:discuss}
 
Having defined the model, let us now consider how databases
given in one of the common conceptual models can be represented
in it. In the relational model, to represent information about
employees, we may use a relation, i.e., a set of tuples, called
EMP. Considering the execution of the query {\bf select} SAL
{\bf from} EMP, we can see that the name EMP gets {\em bound to
each tuple} of the relation. As we are interested in names in
the context of binding, in our model the name EMP is associated
not with the relation, but rather with each of its tuples. This
holds in general for any named set: in our model the name is
associated with each of the elements of the set; see, e.g., LOC
of DEPT in MyDatabase.
 
Speaking in terms of programming languages, a tuple defines a
local environment: each attribute is a name that, {\em in the
context of this tuple}, can be bound to the associated object --
attribute value.  Note that we do not have {\em tuple} as a data
structure in our model -- as just seen, a tuple is represented
by the set of its named components. Also note that the
identifier of the object representing the tuple is internal and
has nothing to do with the conceptual model, in which this tuple
is a value, not an object. It is just an abstract representation
of the fact that the tuple is an identifiable store object.
(Many relational systems indeed use tuple-id's internally.)
 
Names can be numbers. For example,
\begin{tabbing}
\hsmall$<i_1, A, \{$\=$<i_2, 1, Monday>, $\\
                    \>$<i_3, 2, Tuesday>,\ldots , <i_8, 7, Sunday> \}>$
\end{tabbing}
represents an {\em array}. Thus, tuples and arrays have
essentially the same representation. Indeed, both are
essentially local environments, and the differences have to do
only with the type and generation of the names that can be used
in the environment. As already noted, names used in arrays are
also values, and can be calculated during run-time.
 
We do not impose constraints requiring that objects with
the same name should have the same structure. This allows us to
represent {\em variants}, as in the following database
fragment:\vsmall\\
\hsmall$<i_1,EMP,\{<i_2,NAME,Brown>, <i_3, SAL, 2500>\}>$\\
\hsmall$<i_6,EMP,\{<i_7,NAME,Smith>,<i_9, IS\_STUDENT, TRUE>\}>$\vsmall\\
Similarly, we can represent {\em null values}, when they mean
lack of stored information.  Since the definition of a store
does not include any concept of format, a null value is
represented simply by the absence of a binding. For example, in
the database fragment above, the SAL field for Smith is
null-valued.  We do not associate any semantics with this
absence. As far as we are concerned, Smith may have no salary,
or his salary may be unknown, or it may be determined in another
way, e.g., by using the information that he is a student. The
interpretation of the absence of information is part of the
semantics of the data, but is {\em outside} of the scope of our
model. Of course, we need the ability to test for the lack of a
stored object with a given name, so that the query evaluator can
interpret this and apply the appropriate semantics.
 
To generalize to the nested relational, or complex object
models, we need to be able to represent sets, and obviously we
have that in the model. We can also represent bags. For example,
the object $<i_1,N, \{<i_2,M,5>, <i_3,M,5>\}>$ represents the
bag $\{5,5\}$. Similarly one can represent lists, trees, and
generally, instances of recursively defined data types.
 
Let us now consider a conceptual object. It has an identity, and
an updatable state. The mapping is straightforward -- an object
is represented as a store object.  Object sharing and
relationships between objects can be easily mapped by using
internal object identifiers as values of pointer sub-objects, as
seen in {\em MyDatabase} above.
 
In summary, this simple model allows one to represent a variety
of data structures and concepts, and their combinations,
including tuples, arrays, sets, bags and lists, variants, null
values; objects, object sharing, and instances of recursive
types. For object-oriented models some simple extensions are
needed; we discuss them in \cite{SBMS93}. However, we believe
that the simplicity of the model is an advantage: it allows us
to explain the meaning of query constructs without having to
deal with a variety of special cases.
