% File: dbpl_system.tex
% Benutzt: dbpl_system1.tex, dbpl_system2.tex, dbpl_system3.tex,
% DAIDALogo.EPSF, Modulgraph.EPSF
% Basiert auf: DBPLREPORT2.LATEX, INSTALL_DBPL.LATEX & Brussels_DBPL.LATEX
% Version: 3.4.1990 F. Matthes
% Version: 20.11.1990 F. Matthes
%
\documentstyle[a4,xple_tt,11pt]{report} 
\pagestyle{headings}
\parskip=5pt plus 2pt
\parindent=0pt
\def\XOC{$\uparrow$}                   % Dereferenzierungsoperator
\def\tilde{$\sim$}                     % ~ (NOT in DBPL)
\newenvironment{syntax}                % EBNF-Syntax tabuliert
{\sf\begin{tabbing}
XXXXXX\= \kill}{\end{tabbing}}
%
%  Aenderungen durch Marginalien gekennzeichnet
%
\newcommand{\bchanged}{\marginpar{$\top$}}
\newcommand{\echanged}{\marginpar{$\bot$}}
%
% horizontale Linie in Textbreite:
%
\def\separate{\rule{\textwidth}{0.5mm}}

%\includeonly{}

\begin{document}

%---------------------------------------------------------------------------
\begin{titlepage}
\hspace{0.5cm}
\setlength{\unitlength}{1mm}
\mbox{\special{illustration DAIDALogo.EPSF}	
\hspace*{3.7truecm}
\rule{0cm}{2.11truecm}}
\hfill
\parbox{7cm}{\bf
 ESPRIT PROJECT 892, DAIDA \\
 \ \\
 DEVELOPMENT OF \\
 ADVANCED \\
 INTERACTIVE \\
 DATA-INTENSIVE \\
 APPLICATIONS}



\vspace*{2cm}
\begin{tabular}{ll}            
{\bf Title:}   &   {\LARGE \bf DBPL Language and System Manual}\\[4cm]
{\bf Authors:} &   Joachim W. Schmidt \\
 														&   Florian Matthes \\
               &   Fachbereich Informatik, Universit\"at Hamburg, \\
               &   Schl\"uterstra{\ss}e 70, D-2000 Hamburg 13, FRG \\[4mm]
{\bf Project leader:} &     Joachim W. Schmidt \\[2mm]
{\bf Workpackage:}  & Month 48, MAP 2.3 \\[2mm]
{\bf Status:}       & initial document\\[2mm]
                    % in {initial, draft, working, final}
{\bf Distribution:} & Partners, CEC\\[2mm]
{\bf Date:}         & April 1990 \\[2mm]
{\bf Keywords:} &    D.3.0 [Programming Languages, General] 
                     {\em DBPL, Modula-2} \\
                &    D.3.3 [Programming Languages, Constructs] 
                     {\em data types and}\\
                &    {\em data structures, modules, packages}\\
                &    D.3.4 [Processors] {\em compilers, run-time
                     environments}\\
                &    H.2.3 [Database Management, Languages] {\em DDL, DML}\\[2mm]
{\bf Partners:} &    BIM S.A.I.N.V. (Belgium)\\
                &    Groupe Fran\c{c}aise d'Informatique (France)\\
                &    SCS Technische Automation und Systeme (FRG)\\
                &    Universit\"at Hamburg (FRG)\\
                &    Universit\"at Passau (FRG)\\
                &    Cretan Computer Institute (Greece)\\
                &    BP Research Center (UK)\\
\end{tabular}          
%---------------------------------------------------------------------------
\newpage                       
\thispagestyle{empty}    
          
{\noindent\large\bf Abstract}
\smallskip                                  

\noindent The database programming language DBPL \cite{SEM88} is a successor of
Pascal/R \cite{Schm77} and integrates a set- and predicate-oriented view of
relational database modelling into the system programming language Modula-2
\cite{Wirt83}. Based on integrated programming language and database technology
it offers a uniform framework for the implementation and maintenance of
database application software.

This document describes the rationale for the design of DBPL, defines the
elements of the DBPL language, and explains the use of the system software
available for VAX/VMS systems. A small, self-contained application program is
presented in chapter \ref{DBPLXple} to illustrate fundamental aspects of
application programming in DBPL (data definition, data manipulation,
modularization, user-interaction).

Chapter \ref{Report} gives a detailed description of the syntax and semantics
of DBPL. It is  based on the Modula-2 Report by N. Wirth as published in N.
Wirth: Programming in Modula-2, Springer-Verlag, Berlin, Heidelberg, New York,
3rd Edition, 1985. All modifications to the Modula-2 Report are indicated in
the margins ($\top$, $\bot$). 

\bigskip
\bigskip

\noindent{\large\bf Intended Audience}

\smallskip

This manual is written for readers who have a general knowledge of procedural
programming languages and of the relational data model. Users of the DBPL
system software should read the installation instructions (Chapter
\ref{Installation}) first.  Chapter \ref{Rationale} and \ref{Overview}
introduce the main language concepts and should be of general interest. The
example program in Chapter \ref{DBPLXple} illustrates the spirit of modular
program development using DBPL. Chapter \ref{Report} is intended as a
reference for programmers and language implementors.

\bigskip   
\bigskip

\noindent{\large\bf Related Documents}

\smallskip

Data- and Rule-Based Database Programming in DBPL \cite{DAIDA4}

The Type System of DBPL \cite{MaSc89}

DBPL System: The Prototype and its Architecture \cite{DAIDA2}

VAX-11 Modula-2 Users Guide

VAX-11 Symbolic Debugger Reference Manual

VAX-11 Linker Reference Manual

\bigskip   
\bigskip

\noindent{\large\bf Revision History}

\smallskip

\begin{description}

\item{April 1990:}  \\
 Initial version, corrections to DBPL report as of November
1988. Installation instructions for DBPL VAX/VMS software version 2.03.
\item{November 1990:}  \\
Installation instructions for DBPL VAX/VMS software version 2.1.
\end{description}
\end{titlepage}
\newpage
%----------------------------------------------------------------

\tableofcontents                 

\chapter{Rationale of DBPL}


\label{Rationale}

The development of data-intensive applications, such as information systems or
design applications in mechanical or software engineering, involves
requirements modeling, design specification, and, last but not least, the
implementation and maintenance of large database application programs. The
database programming language DBPL presented in this manual concentrates on the
last issue to offer a uniform and consistent framework for the
{\em efficient implementation} of database applications. 

As a first cut, data-intensive applications may be characterized by their needs
to specify and manipulate {\em heavily constrained} data that are {\em
long-lived} and may be {\em shared} by a user community. These requirements are
direct consequences of the fact that those data serve as (partial)
representations of some organizational unit or physical structure that exist in
their own context and on their own time-scale independent of any computer
system. Due to the size of the target system and the level of detail by which
it is represented, those representational data may become extremely voluminous
-- in current data-intensive applications up to $O(10^{9})$ or even higher. 

In addition to the need for global management of large amounts of {\em
representational data}, typical database applications also have a strong demand
to process small amounts of local {\em computational data} that implement
individual states or state transitions. 

In essence, it is this broad spectrum of demands -- the difference in purpose,
size, lifetime, availability etc. of data -- and the need to cope with all
these demands within a single application that determines the daily life of a
database programmer. 

DBPL \cite{SEM88} is a successor of Pascal/R \cite{Schm77} and addresses the
above issues by extending a well-understood system programming language (namely
Modula-2 \cite{Wirt83}) by a small set of abstraction mechanisms needed for
database application programming \cite{DAIDA4}. DBPL extends Modula-2 into
three dimensions:

\begin{itemize}
\item Bulk data management through a data type {\em set} (relation).
\item Abstraction from bulk iteration through {\em access expressions}.  
\item {\em Persistent modules} and {\em transactions} for sharing, recovery,
      and concurrency control.
\end{itemize}

The design of the DBPL language was influenced by requirements of the DAIDA
environment for database application development \cite{SWBM89,BMSW89,BJMSV89}
that asks for a target language that
\begin{itemize}
 \item makes extensive use of sets and first-order predicates, and
 \item provides complete separation of typing and persistence.
\end{itemize}

An essential guideline for the design of DBPL can be characterized by the
slogan ``power through orthogonality''.  Instead of designing a new language
(with its own naming, binding, scoping and typing rules) from scratch, DBPL
extends an existing language and puts particular emphasis on the
interoperability of the new ``database'' concepts with the given programming
language concepts.  In particular, DBPL aims to overcome the traditional
competence and impedance mismatch \cite{CoMa84} between programming languages
and database management systems by providing

\begin{itemize} 
\item a uniform treatment of volatile and persistent data, 
\item a uniform treatment of large quantities of objects with a simple 
      structure and small quantities of objects with a complex structure, 
      as well as 
\item a uniform (static) compatibility check between the declaration and the 
      utilization of each value. 
\end{itemize} 
         
Implementation details (e.g., storage layout of records, clustering of data,
existence of secondary index structures, query evaluation strategies,
concurrency and recovery mechanisms) are deliberately hidden from the DBPL
programmer. A key idea in the design and implementation of DBPL is to let the
runtime system choose appropriate implementation strategies based on
``high-level'' information extracted from the application programs. As it 
turns out, the widespread use of {\em access expressions} (see
\ref{DBPLAccessExp}) (i.e. first-order logic abstractions of bulk data access)
in typical DBPL programs facilitates such an approach.

Following the spirit of Modula-2, DBPL violates in some cases the design
principle of ``orthogonality of language concepts'' in order to enable a
well-engineered implementation of the language. For example, DBPL does not
support persistence of pointers and procedure variables. This was not only
motivated by the predominance of associative identification mechanisms in the
classical Relational Data Model, but also by the far-reaching consequences
of this identification mechanism on the concurrency control and distribution
support \cite{BJS86,DURESS88}.

Modula-2 was chosen to be the basis for DBPL as it is characterized by a
clear module concept and a strict type system. It is further excelled by
its balance between simplicity and expressive power. 

In contrast to some persistent programming languages
\cite{ACC81a,PPRG87,DCBM89,Dea89}, the evolution of database schemata and of 
application programs is outside the scope of the language DBPL and is delegated
to specific components of the DAIDA environment 
\cite{BJMSV89,DAIDA3,DAIDA88,NiSc89}.
                                                                   
To summarize, the most prominent feature of the DBPL is the type-complete
integration of sets and first-order predicates into a strongly typed,
monomorphic language with persistence as an orthogonal property of individual
compilation units.

% ----------------------------------------------------------------------------

\newpage
\chapter{Language Concepts for Database Programming}

\label{Overview}

The following subsections highlight the central new language
concepts of DBPL. Programmers familiar with a ``traditional'' programming
language like Modula-2 only need to understand these few additional features to
successfully utilize the database capabilities of DBPL. Due to its orthogonal
language design, there are no {\em special} rules governing the naming,
typing, binding, scoping, sequencing etc. of these Modula-2 extensions.

In particular, it should be noted that every correct Modula-2 program is also a
correct DBPL program, i.e., DBPL is a fully upward compatible Modula-2
extension.


\section{Data Type Relation} 

A relation type declaration specifies a structure consisting of a set of
elements of the same type. The cardinality of this set is basically unlimited.
Relations extend the notion of sets by allowing to specify a key, i.e. a
substructure of the set element that is guaranteed to have a unique value
within a relation and, therefore, provides (associative) identification. 

In DBPL, the definition of a relation type may contain any
nesting of records, arrays, variant records and relations. The only restriction
is that on each level of nesting there has to be at least one non-relational
attribute and that key attributes of non-first normal-form relations
(NF$^2$ relations) are non-relational.
\begin{xple}
TYPE
  Nodes  = RELATION OF CARDINAL;
  Edges  = RELATION OF RECORD a,b: CARDINAL; END;
  NF2Rel = RELATION a,b OF
             RECORD
               a,b: CARDINAL;
               subrel: Edges;
             END;
VAR
  N, NWE: Nodes; 
  E: Edges;
  P: NF2Rel;
\end{xple}

In the above example, \verb$Nodes$ and \verb$Edges$ are true set types, whereas
\verb$NF2Rel$ is a nested relation type with key attributes \verb$a$ and
\verb$b$.

Relation types are ``orthogonal'' type constructors, i.e. they coan
can occur as elements of arbitrary structures like arrays or records,
\begin{xple}
VAR
  Table: ARRAY[0..10] OF Nodes;
\end{xple}            

and relation variables can appear in arbitrary scopes and extents, for example,
in objects of other data types, i.e.

\begin{itemize}
\item as persistent, global, local, dynamic variables, and
\item as value and reference parameters.
\end{itemize}
\begin{xple}
PROCEDURE SwapNodes (VAR n1, n2: Nodes);
  VAR
    n: Nodes;
BEGIN
  n:= n1; n1;= n2; n2:= n;
END SwapNodes;
\end{xple} 

Note, that relations in the ``classical'' Relational Data Model are simply
relations with elements of ``flat'' record types, i.e. records that only
contain fields of the base types (INTEGER, REAL, ...). 
                                
Modula-2 identifies elements of arrays by index expressions and record
components by field names. Analogically, relation elements are identified by
their key values. Therefore, substructures of hierarchical objects are
uniformly accessed by a sequence of the previously mentioned identification
mechanisms. 

\begin{verbatim}
  P[1,5].subrel := Edges{}
\end{verbatim} 

This assignment replaces the value of the \verb$subrel$ attribute of an element
\verb$p$ with the key values \verb$p.a=1$ and \verb$p.b=5$ in the relation
\verb$P$ by the empty relation of type \verb$Edges$.

\section{Aggregates}

DBPL allows the denotation of structured values by means of aggregates, which
are simply an enumeration of (possibly structured) values prefixed by the name
of the type to be constructed. 
\begin{xple}
  N:= Nodes\{1,2,3,4\};
  E:= Edges\{ \{1,2\}, \{2,3\}, \{3,4\}\};
  P:= NF2Rel\{ \{1,4,E\} \};
\end{xple}            

As illustrated by the example above, the type identifier can be omitted in 
nested expressions where the aggregate type can be deduced from its context.

\section{First-Order Predicates}

Any boolean expression in DBPL can contain first-order predicates with
existential (\verb$SOME$) and universal (\verb$ALL$) quantifiers ranging over
relation expressions. The use of (nested) predicates often allows to avoid
explicit iterations over relations and thereby facilitates access optimization
to be performed by the DBPL system:  

\begin{xple}
  IF SOME n IN N (NOT SOME e IN E (e.a = n)) THEN 
    WriteString("There is a node without outgoing edges")
  END;
  IF NOT ALL e IN E (
    SOME n IN N (e.a = n) AND 
    SOME n IN N (e.b = n)) THEN
    WriteString("There are edges from/to non-existent nodes")
  END;
\end{xple}

First-order predicates play a central role in the formulation of access
expressions which are the subject of the next paragraphs.  


\section{Access Expressions}

\label{DBPLAccessExp}
Access Expressions are selection and construction rules for relations. They
generalize and unify the concepts of set-oriented retrieval,
element-oriented iteration and (updateable) views found in relational database
systems.

{\em Selctive access expressions} define subrelations of existing relation
variables. The following expressions select the elements \verb$e$ of the
relation variable \verb$E$, fulfiling the selection predicate \verb$e.a=5$
respectively \verb$SOME n IN N (e.a =n)$:

\begin{xple}
  EACH e IN E: e.a = 5
  EACH e IN E: SOME n IN N (e.a = n)
\end{xple}

The first selection expression selects all edges having 5 as their start node,
whereas the second selection expression selects all edges starting from a node
contained in the set \verb$N$.     

{\em Constructive access expressions} denote relation expressions that are
derived from combinations of existing relations: 

\begin{xple}
  \{n1,n2\} OF EACH n1 IN N, EACH n2 IN N: TRUE
  \{e1.a,e2.b\} OF EACH e1 IN E, e2 IN E: (e1.b = e2.a)
\end{xple}            

The first expression constructs the cartesian product $\verb$N$\times\verb$N$$.
The second constructive expression builds a set of edges, containing an edge
for each pair of nodes that are connected by a path of length 2.

Please note that access expressions (like boolean expressions) have to be used
in a conforming context. There are three possible contexts for access
expressions in DBPL:
\begin{description}

\item{Relation constructors} build a new relation containing (copies of) the
elements denoted by an access expression: (set-at-a-time operations)

\begin{xple}
  Edges\{EACH e IN E: e.a = 5\}
  Edges\{EACH e IN E: SOME n IN N (e.a = n)\}
  Edges\{\{n1,n2\} OF EACH n1 IN N, EACH n2 IN N: TRUE\}
\end{xple} 

\item{Relation iterators} iterate over a subrelation denoted by a selective
access expression: (element-at-a-time operations)

\begin{xple}
  FOR EACH e IN E: e.a = 5 DO WriteCard(e.b, 1) END;
  FOR EACH e IN E: SOME n IN N (e.a = n) DO WriteCard(e.b, 1) END;
\end{xple} 

\item{Selector and constructor declarations} allow to name and parameterize
a given access expression (see section \ref{DBPLSelectors} and
\ref{DBPLConstructors}). (Lambda abstraction) 

\begin{xple}
  SELECTOR StartAt WITH(x: Node): Edges;
  BEGIN EACH e IN E: e.a = x END StartAt;

  CONSTRUCTOR AllPossibleEdges: Edges;
  BEGIN EACH n1 IN N, EACH n2 IN N: TRUE END Edges;
\end{xple} 

\end{description}

As quantifiers may be nested and the range expression of the inner
quantifier may depend on the quantified variable of the outer scope, it is
possible to ``descend«« into nested relations:
\begin{xple}
E:= Edges\{e OF EACH p IN P, EACH e IN p.subrel: TRUE\}
\end{xple} 

On the other hand, the nesting of aggregates and relational constructors in the
projection list of a construction predicate facilitates the construction of
nested relations. 

\begin{xple}
NF2Rel \{ \{ e.a, e.b, \{e\}\} OF EACH e IN E: TRUE \}
\end{xple} 

To summarize, access expressions and first-order predicates form a relationally
complete query formalism, exceeding the power of existing relational DBMS.

\section{Relation Operations}

In addition to relation iteration and relation assignment as illustrated above,
DBPL has  predefined relation operations for set-oriented insertion, deletion
and update:

\begin{verbatim}
  E:= E2; E:+ E2; E:- E2; E:& E2
\end{verbatim} 

Furthermore, there are the usual infix operators (\verb$=, <, >, <=, >=, <>$) to
compare two relations of the same type on equality, (strict) set containment, 
or inequality. Therefore, one can write more succintly \verb$E <= E2$ instead
of
\begin{xple}
  ALL e IN E SOME e2 IN E2 ((e.a=e2.a) AND (e.b=e2.b))
\end{xple} 


\section{Databases and Persistence}

Any module (separate compilation unit) can be declared as a database module by
prefixing it with the keyword \verb$DATABASE$. All variables declared in a
database module are persistent, i.e. their lifetime is not restricted to a
single program execution and exceeds the lifetime of all programs importing
them. Furthermore, they are {\em shared} variables, i.e. they can be accessed by
several programs (concurrently). Procedure variables and pointers are not
allowed within a database module. The declaration of databases is not
restricted to definition modules, which permits the definition of persistent
abstract data types.

Persistent variables may only be accessed during transaction execution (see
section \ref{DBPLTransaction}). The DBPL runtime system will detect all
violations to this rule.

The initialization of persistent variables has to be accomplished before they
are accessed for the first time. This is done by extending the original
semantics of the module initialization code of Modula-2. Every database module
may contain a supplementary initialization code, which is executed only once at
the beginning of the existence of a persistent variable. 
\begin{xple}
DATABASE MODULE PersistentGraph;

TYPE
  Nodes  = RELATION OF CARDINAL;
  Edges  = RELATION OF RECORD a,b: CARDINAL; END;
VAR
  N : Nodes; 
  E : Edges;

TRANSACTION InitDB;
(* this transaction will be called only one during DB lifetime *)
BEGIN
  N:= Nodes\{1\};
  E:= Edges\{\{1,1\}\};
END InitDB;

DATABASE
  InitDB;
BEGIN
  (* standard Modula-2 initialization code *)
END PersistentGraph.
\end{xple}


\section{Transactions} 

\label{DBPLTransaction}
As the unit of concurrency control and recovery, a transaction comprises a
sequence of actions and is regarded atomic concerning its effect on the
database. Transaction in DBPL can be named and parameterized. In case
of nested or recursive calls of transactions, the inner calls are treaded
as ordinary procedure calls, i.e. DBPL only provides a ```flat««
transaction model.

The following transactions deletes all nodes in \verb$N$ that are reachable
through a path of arbitrary length of edges in \verb$E$ from a giving starting
node \verb$n$. It uses a standard depth-first search traversal strategy.

 \begin{verbatim}
TRANSACTION DeleteSuccessors(n: Node);
(* iterative solution *)
VAR 
  visited: Nodes;

  PROCEDURE VisitNode(n: Node);
  BEGIN
    visited:+ Nodes{n};
    FOR EACH succ IN N: 
      SOME e IN E ((e.a = n) AND (e.b = succ)) 
      AND NOT succ IN visited DO
       VisitNode(succ);
    END;
  END VisitNode;

BEGIN
  visited:= Nodes{};
  VisitNode(n);
  N:- visited;
END DeleteSuccessors;
\end{verbatim} 

If there are other transactions reading or updating the database variables
\verb$N$ or \verb$E$ simultaneously, the DBPL system will execute them
together with \verb$DeleteSuccessors$ in a serializable schedule.

\section{Selectors}

\label{DBPLSelectors}
Selectors are means to describe value-based constraints on relation variables.
The application of a selector defines a selected relation variable, which is
equivalent to an updatable view in database systems. 

The declaration of a selector has the following general structure:
\begin{xple} 
SELECTOR sp ON (R : RelType) 
            WITH ( formal parameters ) 
            FOR ( access restrictions ) 
BEGIN
  selective access expression
END sp;
\end{xple}         

The ON-parameter allows selectors to be bound to a relation type and not only
to a specific relation variable. 
\begin{xple}
SELECTOR NodesWithEdges ON (X: Nodes);
BEGIN              
  EACH n IN X: SOME e IN E ((e.a = n) OR (e.b = n))
END NodesWithEdges;
\end{xple}
           
By declaring access restrictions in the signature of a selector
(FOR-parameter), it is possible to restrict the operations allowed on relation
variables. The access restrictions are connected to the selector type. 
\begin{xple}
SELECTOR ReadNodesWithEdges ON (X: Nodes) FOR (=);
BEGIN              
  EACH n IN X: SOME e IN E ((e.a = n) OR (e.b = n))
END ReadNodesWithEdges;
\end{xple}

Within an expression, the value of a selected relation variable is equal to the
value of a relation created by a relational query expression, based on the
selective access expression of the selector. 
\begin{xple}
NWE:= N[NodesWithEdges]
\end{xple}
            
Informally, the semantics of updates to selected variables is defined as
follows:

\label{SelAppl}
\begin{quote} 
updates are executed if and only if a new relation value can be constructed,
such that the non-selected part of the new relation is equal to the
non-selected part of the relation before the update, and the selected part of
the new relation is equal to the right-hand-side of the update statement. 
\end{quote}                     

With the current selector semantics, any violation to this constraint will
cause the update operation not to be executed at all.         
\begin{xple}
N[NodesWithEdges]:= Nodes\{1,2,5\};
\end{xple}
As node \verb$5$ does not belong to any edge in \verb$E$, the assignment above 
will not be executed.

By virtue of these semantics of updates on selected relation variables, 
selectors can be used to enforce value-based integrity constraints on relation
variables. Using the optional access restrictions in a selector heading one can
constrain access to selected  relation variables even further, namely to those
kinds of operations explicitely listed in the heading of the selector. Access
restrictions are statically verified by the compiler: 

\begin{xple}
N[ReadNodesWithEdges]:= N;
\end{xple}            

Since the declaration of {\sf ReadNodesWithEdges} restricts the use of the
selected relation variable to read operations, the compiler disallows the
assignment above.

\section{Constructors}

\label{DBPLConstructors}
Constructors are named and paramaterized construction rules for relations. They
are used to define derived relations by a list of constructive access
expressions. These expressions refer to relation variables or to other derived
relations. One can show an equivalence between constructors in DBPL and
certain models of deductive database programs, which have been shown to
correspond to Horn-clause logic. Constructors are therefore considerably more
expressive than the relational query formalisms.

\subsection{Declaration}
The signature of a constructor defines its name, formal parameters and result
type. Similar to selectors, constructors are first-order objects, which are
typed according to their signature. The body of a constructor declaration is a
list of relational expressions, defining a relation of the result type. 
\begin{xple}
CONSTRUCTOR NonDirectedEdges: Edges;
BEGIN                
  EACH e IN E: TRUE,
  \{e.b, e.a\} OF EACH e IN E: TRUE
END NonDirectedEdges;
\end{xple}
   
\subsection{Application}

The application of constructors is restricted to relational expressions (i.e.
update operations on derived relations are inadmissible). The substitution of
actual parameters is executed according to the rules defined for selectors (see
\ref{SelAppl}). The value of a constructor application is obtained by an
evaluation of the predicates within the constructor body, which may contain
further constructors. 

\begin{xple}
E:= Edges\{NonDirectedEdges\}
\end{xple}

\subsection{Recursive Constructors}

A set of constructor declarations may contain cyclic references. The semantics
of the application of such a recursive constructor is defined by the least
fixed point of a system of relation-valued functions. The existence and
uniqueness of this fixed point is guaranteed for a (syntactically) restricted
class of constructors.

\begin{xple}
CONSTRUCTOR Closure ON (X: Edges): Edges;
BEGIN                            
  EACH e IN X: TRUE,
  \{e1.a, e2.b\} OF EACH e1 IN X, EACH e2 IN Edges\{Closure(X)\}: e1.b = e2.a
END Closure;
\end{xple}                                  

The above constructor defines a relation that contains an edge for all node
pairs that are connected by a (directed) path of arbitrary length.

Using recursive constructors one can express the transaction of section
\ref{DBPLTransaction} that deletes all transitive successors of a given node
more declaratively as

\begin{verbatim}
TRANSACTION DeleteSuccessors(n: Node);
BEGIN
  N:- Nodes{EACH succ IN N: SOME e IN Edges{Closure(E)} 
               ((e.a=n) AND (e.b=succ))}
END DeleteSuccessors;
\end{verbatim} 

This version of the transaction should be as least as efficient as the
previous iterative solution and it leaves even more possibilities for access
optimizations to be performed by the DBPL run-time system. 

\newpage

\include{dbpl_system1}

\include{dbpl_system2}

\include{dbpl_system3}

\bibliographystyle{tex$inputs:florian}
\bibliography{tex$inputs:florian}

\end{document}


