%
% File:    dbpl-language.tex
% Author:  FM
% Date:    1-JUL-1992
%

\section{Language Concepts for Database Programming}

The following sections highlight the central database 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.

The running example used in this chapter is the representation of a
directed graph by means of a node and an edge set. A more realistic,
self-contained database example is given in the next section.

\subsection{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{verbatim}
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{verbatim}
In the example above, \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 can
occur as elements of arbitrary structures like arrays or records,
\begin{verbatim}
VAR Table: ARRAY[0..10] OF Nodes;
\end{verbatim}            
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{verbatim}
PROCEDURE SwapNodes (VAR n1, n2: Nodes);
  VAR n: Nodes;
BEGIN
  n:= n1; n1;= n2; n2:= n;
END SwapNodes;
\end{verbatim} 
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$.

\subsection{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{verbatim}
N:= Nodes{1, 2, 3, 4};
E:= Edges{ {1,2}, {2,3}, {3,4} };
P:= NF2Rel{ {1, 4, E} };
\end{verbatim}            
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.

\subsection{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{verbatim}
  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{verbatim}
First-order predicates play a central role in the formulation of access
expressions which are the subject of the next paragraphs.  

\subsection{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{verbatim}
EACH e IN E: e.a = 5
EACH e IN E: SOME n IN N (e.a = n)
\end{verbatim}

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{verbatim}
  {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{verbatim}            
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{verbatim}
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{verbatim} 

\item{Relation iterators} iterate over a subrelation denoted by a selective
access expression: (element-at-a-time operations)
\begin{verbatim}
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{verbatim} 

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

\begin{verbatim}
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{verbatim} 

\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{verbatim}
E:= Edges{e OF EACH p IN P, EACH e IN p.subrel: TRUE}
\end{verbatim} 
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{verbatim}
NF2Rel{ {e.a, e.b, {e} } OF EACH e IN E: TRUE}
\end{verbatim} 
To summarize, access expressions and first-order predicates form a
relationally complete query formalism, exceeding the power of existing
relational DBMS.

\subsection{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{verbatim}
ALL e IN E SOME e2 IN E2 ((e.a=e2.a) AND (e.b=e2.b))
\end{verbatim} 


\subsection{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{verbatim}
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{verbatim}


\subsection{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
treated 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.

\subsection{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{verbatim} 
SELECTOR sp ON (R : RelType) 
            WITH ( formal parameters ) 
            FOR ( access restrictions ) 
BEGIN
  selective access expression
END sp;
\end{verbatim}         

The ON-parameter allows selectors to be bound to a relation type and not only
to a specific relation variable. 
\begin{verbatim}
SELECTOR NodesWithEdges ON (X: Nodes);
BEGIN              
  EACH n IN X: SOME e IN E ((e.a = n) OR (e.b = n))
END NodesWithEdges;
\end{verbatim}
           
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{verbatim}
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{verbatim}

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{verbatim}
NWE:= N[NodesWithEdges]
\end{verbatim}
            
Informally, the update semantics for 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{verbatim}
N[NodesWithEdges]:= Nodes{1,2,5};
\end{verbatim}
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{verbatim}
N[ReadNodesWithEdges]:= N;
\end{verbatim}            

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

\subsection{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 that due to the substitution semantics of
\kw{WITH} parameters, the constructor formalism in DBPL is more
expressive than stratified datalog programs \cite{ERMS91}.

\subsubsection{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
(note that the concatenation of access expressions via ``,'' defines a
\e{union} operation):
\begin{verbatim}
CONSTRUCTOR NonDirectedEdges: Edges;
BEGIN                
  EACH e IN E: TRUE,
  {e.b, e.a} OF EACH e IN E: TRUE
END NonDirectedEdges;
\end{verbatim}
   
\subsubsection{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{verbatim}
E:= Edges{NonDirectedEdges}
\end{verbatim}

\subsubsection{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{verbatim}
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{verbatim}                                  
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.

