%
% File:   dbplenv3.tex
% Author: FM
% Date:   5.8.1991
% Included by: dbplenv.tex
%

\section{The Multi-User DBPL Database System}
\label{run-time}

The layered architecture of the DBPL run time system
(Fig.~\ref{dbpl-system}) is roughly equivalent to the architecture of
other relational or object-oriented database systems
\cite{ScMa90b,C*86,P*87,Ston90}. It is excelled by its support
for non-relational persistent objects, temporary relations, recursive
queries, complex objects and client-server architectures.
Fig.~\ref{dbpl-sizes} gives an idea of the relative complexity of the
various DBPL system implementation tasks measured in lines of Modula-2
source code.

\subsection{DBPLRTS -- The DBPL Runtime System Interface}
\label{DBPLRTS}

The module \kw{DBPLRTS} represents the only interface to the runtime
system. It is accessed by compiled DBPL object programs and by
interactive tools (e.g.~the DBPL database browser) that require
database system functionality.  The foremost function of this module is
the isolation of applications from implementation details of the
database system.

\kw{DBPLRTS} exports the following abstract data types: values of type
\kw{Type} are runtime representations of DBPL type structures (see
Fig.~\ref{}), \kw{Databases} identify open databases during program
execution, \kw{Expressions} identify DBPL query expressions which are
evaluated and optimized by an interpreter at run time, \kw{Relations}
identify relation variables, and \kw{Transactions} identify active
transactions.

The data type \kw{Relation} may illustrate the power and
orthogonality that can be achieved by the consequent use of abstract
data types in the DBPL system. A \kw{Relation} value at the 
\kw{DBPLRTS} interface may denote a normalized or a non-normalized
relation, a base relation variable or a relational attribute, a
persistent database relation or a temporary intermediate result.
Furthermore, a \kw{Relation} may be equipped with a \e{selection
predicate} that defines integrity constraints that are to be preserved
by relational updates on the relation variable. By virtue of this
uniform identification mechanism, a given \kw{DBPLRTS} operation 
(e.g.~\kw{AssignRelation}) which accepts parameters of type
\kw{Relation} can be used in a large number of programming situations
and can still provide tailored implementations for special parameter
combinations (e.g. assignments between temporary relations).

In addition to these types, the interface \kw{DBPLRTS} exports the
semi-abstract data types \kw{Bytesize} and \kw{Address} which are
needed  for the identification of program variables, database
variables, relation element buffers and attributes within relation
elements. 

\kw{DBPLRTS} provides all relevant functions required for each of the
exported ADTs listed above:
\begin{itemize}
\item Definition of DBPL type structures (see figure
\ref{Abb:Typbaum});

\item Definition of new databases and database variables
(\kw{CreateDB}, \kw{CreateDBVar}), enumeration of the variables,
indices and types of a database module; 

\item Opening and closing of databases as well as binding of scalar
database variables to program addresses (\kw{OpenDB},
\kw{CloseDB}, \kw{OpenDBVar});

\item Transaction management (\kw{BeginTransaction},
\kw{EndTransaction}, \kw{Commit}, \kw{UseExpression},
\kw{TransactionBody}, \kw{HandleException});

\item Synchronization of the access to non-relational database
variables (\kw{GetDBVar}, \kw{ReleaseDBVar});

\item Operations concerning relations and predicates (i.e., all
operations provided by the layer \kw{PSMS}, see Sec.~\ref{PSMS});

\item Iteration loops (\kw{BeginIteration}, \kw{Step},
\kw{StopIteration}); 

\item Synchronized access to relation elements via their
primary key value (\kw{GetTuple}, \kw{ReleaseTuple});

\item Creation, deletion and update of hierarchically structured
objects (\kw{CreateObject}, \kw{DropObject}, \kw{AssignObject}).
\end{itemize}      

Most of the functions mentioned above are implemented in the lower
layers \kw{PSMS}, \kw{CTMS} and \kw{CRDS}. Only the following
functionality is realized within the layer \kw{DBPLRTS} itself: 

\begin{itemize}
\item Exceptions (e.g., division by zero) occuring within an application
are handled to enable the correct termination of transactions.

\item Database variables that are not of type relation and that do not
contain relation-valued components are mapped to long records (see
section \ref{SMS}) in a specific database relation. Entries to the
data dictionary (layer \kw{CRDS}) are maintained for the  handling of
these database variables.

\item Iterations over relations restricted by a predicate are
implemented  within this layer. At the commencement of an iteration,
all relation elements satisfying the selective access expression are
stored in a temporary relation which is then taken as the basis for
the iteration itself. This expensive copy process is avoided if the
compiler is able to guarantee that the body of the iteration
statement is free of updates to the range relation.

\item Nested \kw{GetDBVar} and \kw{GetTuple} operations issued in
different static contexts by the compiler for the same database object
have to be identified dynamically in order to share the same
application tuple buffer and to preserve the semantics of traditional
variable updates.

\item The operations \kw{CreateObject}, \kw{DropObject} and          
\kw{AssignObject} are intended to simplify the code generation. They
help to manipulate composed variables containing relations, selectors
and constructors as substructures (e.g. variables of type \kw{Table},
defined on page~\pageref{xple-Table}).
\end{itemize}


\subsection{PSMS -- Evaluation of Parameterized and Recursive Queries}
\label{PSMS}
Since the language DBPL strongly encourages the use of named,
parameterized query expressions (selectors and constructors), an
important requirement for the DBPL system implementation was to
support query optimization also for expressions that involve multiple,
independently developed and dynamically bound query expressions.
Therefore, the exported \kw{PSMS} operations resemble those found at a
standard set-oriented database interface (evaluation of a set-valued
or a boolean-valued expression, bulk insertion, deletion, update
and assignment). However, since these expressions may contain
references to other expresssions and actual parameters to be
substituted for the formal parameters of the referenced expression,
the expressive power of \kw{PSMS} operations is well beyond
relationally complete queries \cite{ERMS91}.

On the other hand, selectors and constructors as realized by \kw{PSMS}
also support more traditional database system tasks like the
\begin{itemize}
\item definition of views and the resolution of queries on views to
queries on the underlying base relations;
\item definition and check of predicative integrity constraints and access
restrictions;
\item evaluation of recursive fixed-point queries (as found in
deductive databases). 
\end{itemize}

The \kw{PSMS} interface is centered around the ADT \kw{Expression} and
provides functions to create elementary expressions from constants and
(program or logical) variables, to combine expressions to new
expressions (comparison, conjunction, disjunction, quantification) and
to introduce references as well as parameters into an expression.
\kw{PSMS} operations are provided for symbolic manipulations of
expressions (\kw{CopyExpression, DropExpression, StoreExpression,
GetExpression, SubstituteWithInPredicate, PrepareForEvaluation}) prior
to their evaluation yielding a set-valued (\kw{Evaluate}) or
boolean-valued (\kw{BooleanValue}) result.

Values of the ADT \kw{Expression} are implemented as attributed
abstract syntax trees that contain pointers to other attributed
abstract syntax trees, to global program variables and to type
descriptions. \kw{PSMS} \kw{Expressions} are evaluated by a mapping to
\kw{Predicates} of the module \kw{CPMS} which are in turn evaluated by
\kw{CPMS} routines (\kw{Evaluate, BooleanValue, Assign, Insert,
Delete, Update}). For non-recursive queries, this mapping can be
understood as a simple expansion process that replaces a reference to
another expression by a copy of that expression in which formal
parameters are subsituted by their corresponding actual parameters.
For recursive references between query expressions like in the
definition of transitive relationships (e.g., ancestors, transitive
subparts, strongly connected components), such a naive expansion
process would not terminate. As described in detail in \cite{ERMS91},
\kw{PSMS} constructs for a given query $Q$ a graph $G$ that represents
the \e{used by} relationship between named query expressions (more
precisely: between parameterized instances of named query
expressions) in $Q$.

Cycles in $G$ correspond to recursive query expressions in $Q$ that
have \e{fixed-point} semantics. Furthermore, each edge in $G$ can be
either be marked  as ``positive'' or ``negative''. Negative edges
result from negated or universally quantified subexpressions. It can
be shown that a \e{stratified} \cite{Naqv89} recursive query in DBPL
corrsponds to a graph $G$ that does not have cycles involving negative
edges. If the analyis of a graph indicates a non-stratified query, the
transaction that issued the query is terminated with an error
message. Otherwise, the graph is partitioned into its strongly
connected components $G_i$ that are then evaluated bottom up component
by component, replacing evaluated subexpressions (subgraphs) by
their relational result. The evaluation of each (cyclic) strongly
connected component requires an \e{iterative} fixed-point computation.

The DBPL system provides two alternative strategies for this
fixed-point computation: The naive strategy computes the
fixed-point of a set of recursive set expressions starting with the
empty set and by repeated application of the set expressions to the
result derived in the previous iteration. The preferred \kw{PSMS}
strategy is to apply a delta transformation \cite{GKB87} to the
set expressions prior to their repeated evaluation. Although this
symbolic transformation increases the complexity of the set
expressions, it typically reduces the evaluation time by an order of
magnitude. Essentially, this ``wave-front'' optimization simply avoids
the redundant recalculation of a large number of result tuples in
consecutive iterations by exploiting the monotonicity of stratified
queries. The naive evaluation strategy is only employed in
``pathological'' cases where the delta transformation would result in
an exponential blow-up of the number of relations involved in
multi-way joins.

As mentioned above, \kw{PSMS} makes heavy use of query optimization
and query evalaution functions exported by the layer \kw{CPMS}. Since
\kw{PSMS} typically re-evaluates a given non-recursive query
expression several times in short succession, it turned out to be
advantageous to have separate functions for the symbolic optimization
of a query expression against a given database (\kw{CPMS.Transform})
and its evaluation (\kw{CPMS.Evaluate}).
        

\subsection{CTMS and LMS -- Multi-Level Transaction Management}

In a multi-user environment, operations on persistent objects have to
be synchronized against each other. In DBPL the unit of concurrency
control and recovery is the transaction. 

The DBPL system utilizes a \e{three-level} synchronization scheme
(indicated by the arrows to module \kw{LMS} in
Fig.~\ref{dbpl-system}). Serializability and recovery of (flat)
user-defined DBPL transactions is achieved by appropriate \kw{CTMS}
locking and logging strategies  at the abstraction level of complex
objects and set-oriented expressions over these objects. The design
decision to put \kw{CTMS} below \kw{PSMS} considerably simplifies the
structure of expressions to be analyzed by the scheduler (i.e.~no
recursion, no references to other expression) while maintaining a
sufficient high level of abstraction (essentially relational calculus
expressions) to support advanced concurrency control mechanisms (like
predicative locking or validation). 

\kw{CTMS} synchronization and recovery works under the assumption that
individual \kw{CRDS} operations (like \kw{InsertTuple, GetTuple}) are
executed \e{atomically} and that conflicts arising from the concurrent
use of access paths or from specific page allocation strategies for
complex objects are also handled internally by the layer \kw{CRDS}.
\kw{CRDS} operations are therefore \e{nested transactions} and require
appropriate locking and logging mechanisms \cite{BSW88,Wei88}. In
fact, this division of labour between higher and lower-level
transactions can be also found between the layers \kw{CRDS} and
\kw{SMS} since \kw{SMS} operations are again executed atomically and
recoverable.

The foremost advantage of such a nested transaction scheme is its
strong support for flexible, modular database system architectures
since higher-level transactions can abstract from the implementation
details of lower-level transactions and transactions on each layer
can exploit local knowledge about possible concurrently executing
transactions on their abstraction level. For example, the layer
\kw{CRDS} is capable of avoiding deadlocks by acquiring locks on
\kw{CRDS} objects in a commonly agreed order.

Since locks of lower-level (\kw{CRDS, SMS}) transactions are already
released at the end of a subtransactions, another advantage of nested
transactions (often quoted in the literature \cite{BSW88}) is a gain in
parallelism for massive multi-user applications. In DBPL, however, the
increased parallelism does not yield a corresponding increase in total
transaction throughput since nested transactions introduce some
bookkeeping overhead (e.g. there are three logs and lock requests on
three distinct layers for a given user-level operation).

The layer \kw{LMS} provides the generic services required for the
implementation of transactions (handling of a \e{write-ahead-log},
distribution of lock requests from application programs to the
centralized scheduler, generation of lock identifiers). Each of the
layers \kw{CTMS, CRDS} and \kw{SMS} specializes these services for its
own purposes: \kw{CTMS} maintains a wait-for graph to detect deadlock
situations and utilizes a multi-granularity locking scheme
\cite{GLP75}, while the index management in the layer
\kw{CRDS} employs a tailored graph locking protocol for B-link trees
\cite{LeYa81} that supports concurrent updates. Page and record
operations are synchronized using a standard strict two-phase locking
scheme.

The current DBPL system does not provide crash recovery since all log
records are not forced to stable storage but are simply kept in main
memory.


\subsection{CPMS -- Transformation and Evaluation of Complex Object Queries}

Essentially, \kw{CPMS} is composed of two components: \e{Evaluation
System} and \e{Transformation System}. Both components deal with
problems created by  allowing predicates over type-complete data
objects. The major interdependences between the two components are
based on the fact that the predicate transformation module is aware of
the needs of the evaluation module and transforms predicates into a
structure that is considered advantageous for its evaluation. 

The layer \kw{CPMS} exports (1) data structures for the internal
representation of predicates, (2) equivalence transformations on
predicates to achieve a standardized predicate structure or an
improved query evaluation efficiency, and (3) evaluation routines for
quantified boolean predicates [\kw{\k{some/all} r \k{in} rel
(predicate)}], set-valued expressions [\kw{\k{each} r \k{in} rel:
predicate}], and the test of the validity of a predicate for a given
relation element \kw{tup} [\kw{\k{some/all} r \k{in} rel (predicate(r,
tup)}].

A predicates is represented by a predicate tree. Nodes are used to
define the elements of a predicate, whereas edges describe its
syntactical structure. Fig.~\ref{Abb:Syntaxbaum} sketches the predicate
tree for the following single-variable query: 
\begin{xple}
\{x.Delivery.Day, x.Delivery.Month\} \k{of} \k{each} x \k{in} A[20]: x.Delivery.Year=1988 
\end{xple}

\begin{figure}
\centerline{\epsfbox{query-tree.ps}}
\caption{Predicate tree for a DBPL query expression}
\label{Abb:Syntaxbaum}
\end{figure}

Eight different node types suffice to represent arbitrary
complex DBPL queries: \e{constant} nodes appear in terms and projection
lists; \e{index} nodes represent array accesses;
\e{variable} nodes can be either bound to quantifiers (some, all,
each) or to a global program variable (variables are identified
internally by numbers that are unique within a given expression);
\e{projection} nodes are used in the target list of a query or in the
definition of a key access; \e{term} nodes are further
distinguished into monadic, dyadic and boolean terms; \e{connection}
nodes represent disjunctions or conjunctions; \e{quantification} nodes
introduces scopes for bound relational variables; \e{root} nodes
correspond to relational expressions. A root node contains the
hierarchical type description of the relational result type. A root
node can represent an empty relation, a relation variable, a selective
access expression, a selector or constructor, or a single relation
element. 
              
\kw{PSMS} provides several algorithms for the transformation of
predicate trees into semantically equivalent trees. Some of them (elimination of negations, elimination of empty
ranges, constant folding, transformation into prenex normal form) aim
at a standardization, simplification and decomposition of queries in
order to simplify the subsequent query evaluation or query
optimization process. Other transformations are used for query
optimization tasks. Some of them employ algebraic equivalences
(propagation of filters and projections over joins and unions), others
introduce implementation-oriented access mechanisms (primary key,
secondary key or hierarchical access) into the query representation.

The \kw{PSMS} transformation system also utilizes cardinality
information about relations involved in a query expression. Thereby,
one can distinguish between data-independent and data-dependent
transformations. Even though the former are executable by the
compiler, the DBPL system carries out all transformations at run time.
Although this leads to an additional expense during runtime, there are
also some advantages: the compiler can work with a simplified internal
structure of predicates; interactive components can pass user-defined
predicates on to the runtime system without preceding transformations;
all transformation routines and data structures for predicate trees
are localized in a single component of the database system.

\begin{figure}
\centerline{\epsfxsize=0.6\textwidth\epsfbox{cpms-eval.ps}}
\caption{Evaluation procedures for DBPL queries and their mutual
dependencies} \label{Abb:Eval}
\end{figure}

The main strategies of the current DBPL query optimizer to efficiently
deal with complex objects are to minimize the read set of a query, to
exploit the primary key access structures maintained in the layer
\kw{CRDS} not only for flat relations but also for subrelations in
complex objects, and finally to minimize the repeated re-evaluation of
target expressions involving relational subqueries. Furthermore,
\kw{CPMS} can rely on powerful complex object operations provided by
\kw{CRDS} to efficiently access and copy complete substructures of
hierarchically structured objects. For flat relations, many of the
algorithms developed for the Pascal/R system and previous DBPL system
versions are still employed \cite{JaKo83,Koch80,JaKo84}.

Fig.~\ref{Abb:Eval} may give an idea of the highly recursive structure
of the evaluation procedures for complex object queries that is implied
by the orthogonality of type constructors and query expressions in
DBPL.  The evaluation procedures are not only capable of evaluating
set-oriented expressions, but they can be also employed to evaluate
boolean-valued quantified expressions and to check integrity
constraints on individual relation elements (as required by the layer
\kw{PSMS}).

As a first cut, the central evaluation algorithm of the \kw{CPMS}
evaluation system can be understood as a \e{nested loop} algorithm
extended to handle relational subqueries and target
expressions. The algorithm employs sophisticated bookkeeping
mechanisms (so-called ``virtual'' conjunctive and disjunctive normal
forms and arrays of bit-sets of modified loop variables) to re-use
partial results computed in earlier iteration steps. Furthermore,
sequential scans over (sub)relations can be replaced by value-oriented
(primary or secondary) key accesses provided by \kw{CRDS} operations
(\kw{FindKey, FindRange}).


\subsection{CRDS -- Type-Complete Relational Database Management}

Using the  facilities for fixed-sized short records and
variable-sized long records exported by the storage management system
\kw{SMS}, \kw{CRDS} offers an external, abstract view on complex
objects of the DBPL type-complete data model. \kw{CRDS} implements the
ADTs \kw{Type}, \kw{Relation}, \kw{Key} and \kw{Database} used by the
upper DBPL system layers.

The primary concern for the design of the \kw{CRDS} interface was to
achieve the complete functionality for all kinds of relations in a
uniform way. In particular, this includes the possibility of selective
and associative access to (nested) relations of arbitrary depth. The
interface offers the following services:
\begin{itemize}
\item Creation of type structures;
\item Creation, opening and closing of root relations;
\item Monadic and dyadic relation operators applicable to arbitrary
relations and combinations thereof (\kw{ClearRel}, \kw{Card},
\kw{Empty}, \kw{AssignRel});
\item Navigational and direct access via the primary key 
(\kw{FindFirst}, \kw{FindNext}, \kw{Find});
\item Retrieval of relation elements or parts thereof (\kw{GetTuple});
\item Modification of relation elements (\kw{InsertTuple},
\kw{UpdateTuple}, \kw{DeleteTuple});
\item Definition of secondary access paths for root relations and
their employment in conventional and non-standard search routines
(\kw{FindFirstKey}, \kw{FindKey}, \kw{FindRange});
\item Procedures for the handling of variable-sized long attributes
(\kw{GetLongField, InsertInLongField, DeleteFromLongField,
UpdateLongField});
\item \kw{BOT}, \kw{EOT} and \kw{UNDO} operations.
\end{itemize}

The module \kw{CRDSDatabases} offers additional features for
manipulating databases (create, open, drop) and \e{data dictionaries}.
Data dictionaries are implemented as relations of tuples with
variable-sized long attributes and are also made available to higher
levels of the DBPL system for their private purposes.

Relational data structures are implemented in the layer
\kw{CRDS} as follows: tuples of first normal form (``flat'') relations
are mapped directly onto fixed-sized \kw{SMS} records. If the tuple
size exceeds the maximum page size of the underlying operating system
(as defined at DBPL installation time, e.g. 4K), \kw{CRDS}
automatically maps these tuples onto page-spanning long records. In
both cases, tuples are identified via stable tuple identifiers
(\kw{TID}s) and a B-link tree is utilized to enforce the
primary key constraint and to speed up direct and sequential access to
relation elements. The B-link tree is an extension of the B$^{*}$-tree,
efficiently solving the problems given by concurrent operations on
this kind of data structure \cite{LeYa81}. The DBA can define
dynamically additional secondary indices for relation variables that
are also maintained by \kw{CRDS} operations.

\kw{CRDS} utilizes a \e{key-oriented chained map concept} for a
compact representation of the structure of \nfnf-relations.
This storare concept is a substantial extension of the map structures
presented in \cite{LKNM84} to provide fast indexed,
sequential and key-based access to (nested) relations of arbitrary
depth. It is based on a separation between user information and
structural information:
\begin{itemize}
\item Complex relation elements are decomposed by a concatenation of
all non-relational, fixed-sized attributes at the different levels,
storing them together as a flat \kw{SMS} (long or short) record. The
dissection starts at the top level, and nested relations are then
decomposed recursively.

\item A data structure called \e{map} is associated with each root
element, containing information about the relationship and the
key-based order of the (nested) relation elements. They can be
accessed by their storage identifier (\e{TID}), also contained within
the map. 
\end{itemize}

\begin{figure}\centering 
  \begin{tabular}{|c|c|c|c|c|c|c|}% 7 Spalten
  \hline
  (Map-Id) & Rel-Id & Parent-Id & Brother & Brother & Key- & Data- \\
           &        &           &   left  &  right  & Part &  TID \\
  \hline
  $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ &%
    $\vdots$ \\
  \hline
  \end{tabular}
\caption{Structure of a map}
\label{Abb:map}\end{figure}

A map is implemented as a \kw{SMS} long record and is interpreted a
vector of  numbered entries (Map-Id, see Fig.~\ref{Abb:map}). Each
entry corresponds to exactly one of the (nested) relation elements
obtained during the decomposition. The different columns of the map
have the following meaning:  
\begin{description}
\item [Rel-Id:] Nested relations are uniquely numbered within each 
\nfnf-relation type;
\item [Parent-Id:] Reference to the map entry of the parent tuple
that contains this element; 
\item [Brother left/right:] Reference to the entry of the brother
tuple with the next lower or higher key value;
\item [Key-Part:] A fixed-sized key value prefix of the corresponding
tuple;
\item [Data-TID:] The storage identifier of the atomar fragment
of the tuple. 
\end{description}

Whereas a pair [Rel-Id, Parent-Id] uniquely identifies a nested
relation, thus being useful to model the hierarchical relationship,
the two brother columns --- constituting a doubly connected list
structure --- function as a (sequential) access path to each of the
nested relation elements. Their performance is enhanced by the key
prefix which in most cases prevents data from having to be accessed.
As, apart from the pair [MapTID, MapIndex], elements of nested
relations are addressed indirectly, this \kw{SuperTID} represents a
stable database address. 
 
\begin{figure}
\begin{center}
\setlength{\unitlength}{0.75mm}
\begin{picture}(100,60)
% Dreieck B-link Tree incl. abgehender Pfeil
\put(2,40){\line(1,0){40}}
\put(2,40){\line(1,1){20}}
\put(42,40){\line(-1,1){20}}
\put(0,43){\makebox[40mm]{\small B$^{\mbox{\small link}}$-Tree}}
\multiput(6,41)(4,0){9}{\circle*{1.5}}
\put(18,40){\line(0,-1){7}}
\put(18,33){\vector(1,0){10}}
% Map
\put(28,5){\framebox(24,30){}}
\multiput(32,5)(4,0){2}{\line(0,1){30}}
\put(48,5){\line(0,1){30}}
\multiput(28,31)(0,-4){2}{\line(1,0){24}}
\put(28,9){\line(1,0){24}}
\put(38.5,17){....}
\put(28,0){\makebox[24mm]{Map}}
% Von der Map abgehende Pfeile
\put(50,33){\vector(1,0){17}}
\put(50,29){\line(1,0){7}}
\put(57,29){\line(0,-1){4}}
\put(57,25){\vector(1,0){10}}
\put(50,7){\line(1,0){7}}
\put(57,7){\line(0,1){10}}
\put(57,17){\vector(1,0){10}}
% Data Records
\put(67,37){\makebox[30mm]{Data records}}
\put(67,31){\framebox(30,4){}}
\put(67,23){\framebox(22,4){}}
\put(67,15){\framebox(26,4){}}
\end{picture}
\end{center}
\caption{\label{Abb:APMS} \kw{CRDS} access path management}
\end{figure}

As illustrated in Fig.~\ref{Abb:APMS}, a \nfnf-relation is implemented
by a B-link tree that functions as an index to maps which in turn
provide access to all the data records that make up an element of the
root relation.
        

\subsection{SMS -- Persistent Storage Management}
\label{SMS}
The layer \kw{SMS} performs rather traditional DBMS system tasks like
record allocation, record identification, buffer management and free
space management. In addition to fixed-sized data records, \kw{SMS}
also exports page spanning long records. Long records are of dynamical
and almost unrestricted size and allow partial retrieval and
modification.  A long record is organized by means of a directory
storing the length and the address (TID) of all short records
belonging to it.  The directory itself is also implemented as a short
record. This implies that the length of an individual long record is
bounded by 
\mbox{\rule[-0.5cm]{0cm}{1cm}$\frac{|\mbox{page}|^{2}}{|\mbox{TID}| +
|\mbox{Length}|}$}. Typical page sizes between a half and 4K lead to a
maximum length of 43K -- 2.8MByte.

An important taks of \kw{SMS} in the DBPL system is to provide
\e{persistence abstraction}: \kw{SMS} clients need not to be aware
whether record operations are executed locally in main memory data
structures or on a remote machine on persistent data structures. The
only difference lies in the fact that only record operations on shared
data structures have to be executed atomically and recoverable.

Since DBPL supports client-server architectures and client machines
have their own page buffers, there is a need for a cache coherence
protocol between concurrently executing clients. An important
optimization to minimize network traffic and to significantly speed up
remote database accesses is achieved by ``piggy packing'' the time
stamps required by the cache coherence protocol to higher-level lock
messages sent to the central \kw{LMS} lock server (see
Fig.~\ref{dbpl-system}).

In contrast to other database management systems, the DBPL system
makes heavy use of the possibility to distribute disjoint database
objects to different operating system files. This complicates the
internal identification of data records and the free space management,
but simplifies database evolution, backup and access control using
operating system programs. 
