%Purpose: final version published in ADB-94
%Author: K. Subieta, A. Rudloff
%Date: 15-JUN-1993, F. Matthes, fixed KS's e-mail address in the title
%

\documentstyle[epsf]{llncs}
%\newenvironment{verbatimar}{\vspace*{-0.3cm} \begin{verbatim}}
%                          {\end{verbatim} \vspace*{-0.3cm}}

\newcommand{\bverbatim}{\vspace*{-0.3cm}\begin{verbatim}}
\newcommand{\everbatim}{\end{verbatim}\vspace*{-0.3cm}}
\newcommand{\e}[1]{{\em #1\/}}
\newlength{\vlength}
\vlength 0.05cm
\topsep 0.05cm
\begin{document}


\title{A Gateway from DBPL to Ingres \thanks{This research was supported by
ESPRIT Basic Research (FIDE)}} 

\author{Florian Matthes\inst{1}, Andreas Rudloff\inst{1},
        Joachim W. Schmidt\inst{1}, Kazimierz Subieta\inst{2}}

\institute{University of Hamburg, Dept. of Computer Science, 
           Vogt-K\"olln-Stra{\ss}e 30, D-22527 Hamburg, Germany,
           e-mail: J\_Schmidt@informatik.uni-hamburg.de
           \and
           Polish Academy of Sciences, Institute of Computer Science,
           Ordona 21, PL-01-237 Warszawa, Poland,
           e-mail: subieta@wars.ipipan.waw.pl}
\maketitle

\vspace*{-5.5cm}                                                                             {\footnotesize Appeared in: \e{Lecture Notes in Computer Science} Vol.~819, pp.~365--380,~1994\\
(Proceedings of First International Conference on Applications of Databases, ADB-94)}
\vspace*{6cm}

%********************************** Abstract *************************
\begin{abstract}
A gateway from DBPL (being a superset of Modula-2) to the commercial 
database system Ingres is described.  DBPL extends Modula-2 by a new
bulk data type constructor 
``relation'', persistence, and high-level relational expressions (queries) 
based on the predicate calculus, thereby maintaining the basic concepts of 
the language like strong typing and orthogonality.  The gateway enables 
the user to write {\sl normal} DBPL programs for accessing Ingres 
databases.  This is in contrast to typical implementations that embed SQL 
statements into a programming language and results in a fully transparent 
interface for DBPL programmers. DBPL queries and statements referring to Ingres
tables are automatically converted into corresponding SQL statements,
are evaluated by the Ingres database server and the results are
transferred 
back under the control of the DBPL program. This procedure also resolves queries referring to both Ingres and
DBPL tables. The design assumptions of the gateway and the used implementation methods are 
presented as well as design and implementation difficulties.
\end{abstract}

%*********************************** Introduction ***********************
\section{Introduction}

The coupling of programming languages with relational database systems is 
based conventionally on embedding a query language into a programming 
language.  The border distinguishing querying and programming languages has 
become, however, more and more fuzzy.  Many functionalities typical for 
programming languages and programming environments were fixed in the 
SQL standard as capabilities of the ``query language''.  Besides the 
impedance mismatch, this approach involved yet another disadvantage known as 
{\em bottom-up evolution}, i.e.  extending incrementally and {\em ad hoc} 
the functionalities of query languages with the result that many positive 
features that were the reason for the initial development were lost.  
This concerns mainly SQL which recently evolved in the direction of 
programming languages (which is especially striking in the 
INGRES/Windows4GL \cite{Ingr90} and Oracle PL/SQL \cite{Orac91}).

Initial motivation and trends in the development of query languages were 
different from those of programming languages.  One basic assumption was 
simplicity and naturalness of the whole query interface, called {\em 
user-friendliness}.  The positive aspects of user-friendliness include data 
independence, declarativity, simplification of notions concerning data 
views, macroscopic operations allowing the user to determine extensive 
computations in a compact form, and a syntax similar to a natural language. 
 However, user-friendliness also means the restriction of the language` s 
functionality and power as well as non-orthogonality of the language` s 
constructs (e.g. due to syntax).  Real applications may consist of a large 
number of queries and other constructs with the consequence that other interpretations of 
user-friendliness are of vital importance such as preventing the user from 
his/her own errors, computational completeness, and support of various 
programming abstractions.

Database Programming Languages (DBPL-s) are to be distinguished from
these pure query languages. DBPL-s are strongly and statically type 
checked (allowing the removal of many errors before a program 
is executed) as well as syntactically and semantically orthogonal (leading
to a reduction of the number of necessary primitives in the language, as well as the 
size of manuals).  They support full computational and pragmatic 
universality as well as various programming abstractions and have clean 
semantics.  DBPL-s adopt the concept of a query language as a powerful 
construct of a programming language.  The language DBPL 
\cite{ScMa91,ScMa92,MRSS92} extends Modula-2 in several directions.  In 
particular, it introduces persistence, bulk data (relations) and high-level 
relational expressions (equivalent to queries), which allow declarative 
and associative access to relation variables.

Despite the various advantages of DBPL, we are aware that it has little 
chance of success in the commercial world as a complete system.
As observed in \cite{Banc92}, products of 
research activity suffer from the ``new programming language syndrome'': 
very few organizations are ready to adopt a new programming language or a 
new system.  DBPL is a new product working with its own database format
produced at a university.  
Clients of database systems usually prefer the long existence of the 
databases, since investment in gathering data, writing programs, education 
of staff, organization of technological routines of data processing, etc.  
is high. Commercial systems are equipped with a large family of utilities which are not implemented in DBPL 
since (however very useful) they do not present scientific problems.  We do 
not expect, therefore, that potential clients of database systems will 
decide to use DBPL as the only tool for the full development of database 
applications.

University software such as DBPL and their concepts, however, can be 
transferred to the commercial world as a supplement on top of popular and 
widely distributed systems.  Many professionals who are dissatisfied with 
the capabilities and the programming style offered by languages such as SQL 
embedded in some host language delivered with commercial database systems 
are potential DBPL clients.  Direct use of the high level language with 
its clean concepts is at hand with storage and access of the data, for example, in an 
Ingres database, thereby allowing the use of all the tools supported by the 
system.  This was the main reason for deciding to create the 
gateway.  Vice versa, the implementation of the gateway allows the DBPL 
community - students and researchers - to access large 
commercial database systems and thereby use, within the DBPL programming 
environment, their various capabilities.

There are several possible approaches in designing a gateway.  In this 
project we decided to couple the DBPL run-time system with the Ingres SQL 
machine \cite{IngrA89,IngrB89}. All references from DBPL programs to Ingres databases are 
transformed during run-time into dynamic SQL statements.  This permits the 
use of the SQL optimizer and all capabilities of Ingres that are ``below'' 
the SQL machine (concurrency, indices, views, Ingres/Star, gateways, etc.). 
 The interface is fully transparent to DBPL programmers: knowledge of SQL 
and Ingres is not necessary.   
This approach does not support the opinion that SQL should be the 
``intergalactic language'' \cite{SRLG+90} for the next database era, but 
only accepts a widely used standard.  We do not believe that SQL, as a 
programming language, has reached its maturity (despite fixing it in huge standards).

The paper is organized as follows.  In Section 2 we present briefly 
similarities and differences between DBPL and Ingres SQL.  In Section 3 we 
discuss possible methods of mapping DBPL constructs into SQL statements and 
present the methods chosen.  In Section 4 we present architectural 
assumptions of the gateway in connection with the architecture of DBPL.  In 
Section 5 implementation difficulties are discussed.
%*********************************** Section 2 **************************
\section{Similarities and Differences of DBPL and Ingres SQL}
There are significant differences in the available types for structuring
data offered by Ingres and DBPL. Full orthogonality of type constructors
is a leading principle in DBPL which results in the possibility of
defining nested relational structures whereas Ingres allows flat
relations only. On the level of queries orthogonality of DBPL f.e. allows
range relations of queries to be described by queries itself, in SQL
this is not possible. Persistence in DBPL is also introduced as a orthogonal property of modules ({\tt DATABASE MODULE}s) allowing variables of every type (except pointer-variables) to become persistent.  INGRES only supports persistent relations.

Primary keys of relations in DBPL are considered as a structural property of a relation and as such they 
are declared in the definition of the relation type.  The semantics of some 
operators depends on them.  In contrast to this primary keys in Ingres are 
defined for relation variables and used only internally (for creating an 
index structure).  For querying the information about 
primary keys is irrelevant. As a consequence DBPL does not allow
duplicate tuples either in stored relations or in intermediate query
outputs, but Ingres does so. So efficient programming of some
tasks in DBPL may prove impossible.

Both Ingres SQL and DBPL make the distinction between querying a database 
and processing a database.  SQL was designed for retrieval and then 
extended by some programming capabilities, that is, inserting, deleting and 
updating.  It is not computationally complete: more complex (but still 
typical) programming tasks require a classical (host) programming language. 
 In DBPL the main reason for the distinction between queries and other 
constructs of the language is query optimization.  DBPL is based on the 
assumption that queries problematic for query optimizers should be 
forbidden syntactically.  As a consequence, functions and 
operators are not allowed within DBPL predicates.  This restriction results 
in a potential for good performance, however, it violates the orthogonality 
principle. As consequence it is 
practically impossible to utilize in DBPL queries requiring capabilities
available in SQL like 
arithmetic operators, aggregate functions and grouping.

By high-level constructs we denote such programming capabilities which 
support data independence and follow the ``many-data-at-a-time'' principle. 
 We list all high-level constructs of DBPL that may concern Ingres 
databases with short comments concerning their semantics and possible 
equivalents in SQL.  All examples refer to the classical supplier-part 
database defined as follows (whereby the primary key is determined by the attributes following the {\tt 
RELATION}-keyword in the type definition):
\vspace*{\vlength}
\begin{verbatim}
  TYPE suppRel = RELATION sno OF 
            RECORD sno:...; sname:...; status:...; city:... END;
       partRel = RELATION pno OF
            RECORD pno:...; pname:...; color:...; 
                   weight:...; city:... END;
       spRel   = RELATION pno OF
            RECORD sno:...; pno:...; qty:... END;
  VAR supp: suppRel; part: partRel; sp: spRel;            
\end{verbatim}
\begin{enumerate}
\item Quantified boolean expressions, for example:
\vspace*{\vlength}
\begin{verbatim}
  ALL X IN part (SOME Y IN sp (X.pno = Y.pno))
\end{verbatim}
\vspace*{\vlength}
Quantifiers have several counterparts in SQL; we will discuss them later.
\item Selective access expressions, for example:
\vspace*{\vlength}
\begin{verbatim}
  EACH X IN supp: SOME Y IN sp (X.sno = Y.sno)
\end{verbatim}
\vspace*{\vlength}
Selective access expressions can be used inside the FOR iterator; in this 
case the range variable has the status of an updatable programming 
variable.  Selective access expressions have a direct counterpart in SQL.  
\item Constructive access expressions, for example:
\vspace*{\vlength}
\begin{verbatim}
  {X.sname,Y.pno} OF EACH X IN supp, EACH Y IN sp: 
      (X.sno = Y.sno) AND (Y.qty > 200)
\end{verbatim}
\vspace*{\vlength}
They have a direct counterpart in SQL.
\item Aggregate expressions  used to construct tuple and relation values
have no counterpart in SQL. One example is:
for example:
\vspace*{\vlength}
\begin{verbatim}
  partRel{{"P7", "bolt", "green", 65, "London"},
          {"P8", "nut",  "red", 11, "Rome"  }}
\end{verbatim}
\vspace*{\vlength}
\item Relation expressions for describing relation values by combining an 
access expression with a compatible relation type (which determines the 
primary key), for example:
\vspace*{\vlength}
\begin{verbatim}
  JoinRelType{{X.sname,Y.pname} OF
    EACH X IN supp, EACH Y IN part: SOME Z IN sp
      ((X.sno = Z.sno) AND (Y.pno = Z.pno) AND (Z.qty > 200))}
\end{verbatim}
\vspace*{\vlength}
Relation expressions can be used in all contexts allowed for stored 
relations, i.e.  they follow the orthogonality principle.  SQL does not 
allow expressions as range relations under a {\tt from} clause.
\item Union operator, for example:
\vspace*{\vlength}
\begin{verbatim}
  suppRel{EACH X IN supp: X.city = "London",
          EACH Y IN supp: Y.status > 10,
          {"S8", "Miller", 20, "Paris"}}
\end{verbatim}
\vspace*{\vlength}
Ingres SQL also supports union, but only on the top nesting level.
\item Relational operators $=$, \#, $<$, $<=$, $>$, $>=$ denoting relation 
equality, non-equality and set-theoretic inclusions, for example:
\vspace*{\vlength}
\begin{verbatim}
  suppRel{EACH Y IN supp: Y.status > 30} <=
    suppRel{EACH X IN supp: X.city = "London"}
\end{verbatim}
\vspace*{\vlength}
SQL does not support these comparisons. 
\item Assignments on relations realizing all updates: $:=$ (assign), 
$:-$ (delete), $:+$ (insert), and :\& (update), for example the insert operation:
\vspace*{\vlength}
\begin{verbatim}
  supp   :+ suppRel{{"S1", "Schmidt", 25, "Berlin"}};  
\end{verbatim}
\vspace*{\vlength}
All operators follow the ``many-data-at-a-time'' principle (both operands 
are relation-valued; in the example the right-hand side expressions is a 
relation value of cardinality one).  They can be implemented by SQL 
high-level ``update'', ``insert'', ``delete'' statements, or by fetching the
required tuples from Ingres tables to a DBPL buffer, doing the required 
operations and shipping them back to Ingres.
\end{enumerate}
The standard DBPL functions CARD (the number of relation elements) has a
direct counterpart in SQL whereas the ``one-data-at-a-time'' functions  EXCL 
and INCL (exclude/include one tuple) present a problem, because their
semantics is based on primary keys (discussed later). No SQL equivalent
exists for the low-level standard procedures LOWEST, 
HIGHEST, THIS, NEXT and PRIOR.  They enable processing of DBPL relations in 
a tuple-by-tuple fashion.  Some tasks cannot be programmed without them, 
for example, merging of relations or a browsing utility for visualizing
the contents of a database.

 SQL views are special objects with independent existence in the database.  
They can be dynamically created and deleted.  In DBPL similar notions are 
called ``constructors'' and ``selectors'' \cite{ERMS91}.  They are not, 
however, properties of the database but rather properties of the source 
text of programs.  They are first-class objects and may exist in the 
database as values of variables, but only when proper assignments are 
executed in the user program. Both, selectors and constructors, may have
parameters and so they are different from SQL views. Beside this
selectors could be considered as updatable views whereas the
constructors (pure query expressions) could be recursive (with a
fixed-point semantics). Since the mapping 
of selectors and constructors into views implies problems, we have chosen 
to construct the gateway between DBPL and Ingres on architectural levels 
that are below these abstractions (still allowing to evaluate recursive
queries on Ingres tables).

DBPL does not deal with null-values.  In Ingres SQL null-values are 
associated with special facilities (a comparison operator {\em is [not] 
null} and {\em indicator variables} in embedded SQL) and with a special 
treatment in aggregate functions.  Null-values are captured in DBPL by 
variant records; however, there is no simple systematic mapping from 
existing SQL databases to semantically equivalent DBPL type definitions.
Ingres types such as {\em date, money, table-key}, and {\em 
object-key} could be represented in DBPL but they require special functions 
to serve them and are currently not available.

Both DBPL and Ingres are multi-user database systems and employ their own 
methods for dealing with transactions, locks, deadlocks, logs, etc.  There 
is no danger of improper interference of these mechanisms since from the 
point of view of Ingres, a DBPL application is one of its clients, and a 
Ingres application cannot be a client of DBPL.


%*********************************** Section 3 ***********************
\section{Mapping DBPL into SQL}
Since the gateway from DBPL to Ingres is a generic application which
must work for all types of relations and for any DBPL high-level
expressions the use of dynamic SQL was necessary.  It is an extension of
the capabilities 
in embedded SQL allowing to write SQL statements as strings  
which can be manipulated during run-time. Basic component is the so-called SQL Description Area (SQLDA), which allows a
communication between the application and the Ingres server through pointers.  It is a dynamically created data 
structure consisting of explicit typing information and pointers to data.  
The pointers are counterparts of the host variables in embedded SQL.  They 
have two kinds of applications.  In the first case (used by {\tt select} 
statements) they determine places, where the attributes of a retrieved 
tuple are to be written.  In the second case, they determine actual 
parameters of an SQL statement.  This technique assumes application of 
statements containing question marks as ``formal parameters'' which will
be substituted by the values referenced through the pointers at
execution time.

In the following the basic methods that  have been used to map DBPL 
constructs referring to Ingres relations are presented.  
For most DBPL constructs such a mapping exists, but in some cases there
is no convenient solution, thus we needed some escape methods.
Although being not 
very efficient, they allow the completion of computations.  There are 
several such methods; in this project we use only one of them, namely 
copying DBPL relations to the Ingres side.
\subsection{Unproblematic Cases}
DBPL expressions without quantifiers: Consider the following DBPL 
expression:
\begin{quote}
{\tt \{{\em projection list}\} OF \\
       EACH X$_{1}$ IN Rel$_{1}$,..., EACH X$_{n}$ IN Rel$_{n}$: p(X$_{1}$,...,X$_{n}$)}
\end{quote}
If the predicate {\tt p} does not contain quantifiers and all
comparisons in {\tt p}
are available 
in SQL, then this expression is equivalent to the following SQL 
query:
\begin{quote}
{\tt select {\em projection list} \\ from Rel$_{1}$ X$_{1}$, ... , 
Rel$_{n}$ X$_{n}$ \\where p(X$_{1}$,...,X$_{n}$)}
\end{quote}
DBPL predicates returning boolean values: SQL has no semantic domain 
with boolean values, thus we convert a DBPL predicate p into the following 
SQL statement:
\vspace*{\vlength}
\begin{verbatim}
  select * from AuxRel where p
\end{verbatim}
\vspace*{\vlength}
where AuxRel is the name of an auxiliary Ingres table containing exactly 
one tuple. 
We need only a simple procedure returning TRUE if the select statement 
will return a non-empty result, and FALSE otherwise. The DBPL predicate 
(``Do all suppliers have a status higher than 10?'')
\vspace*{\vlength}
\begin{verbatim}
  ALL X IN supp (X.status > 10)
\end{verbatim}
\vspace*{\vlength}
is converted to the following SQL query:
\vspace*{\vlength}
\begin{verbatim}
  select * from AuxRel where not exists 
    (select * from supp X where not( X.status > 10 ) )
\end{verbatim}
\vspace*{\vlength}
DBPL expressions with quantifier SOME in the prenex form:
If a DBPL expression contains only SOME quantifiers in the prenex form, the 
conversion is simple.  The DBPL expression
\begin{quote}
{\tt \{{\em projection list}\} OF \\
\hspace*{0.2cm}EACH X$_{1}$ IN Rel$_{1}$,\ldots,EACH X$_{n}$ IN Rel$_{n}$:\\
\hspace*{0.4cm}SOME Y$_{1}$ IN Rel$_{n+1}$,\ldots,SOME Y$_{m}$ IN
Rel$_{n+m}$ (p)}
\end{quote}
where p contains no quantifiers, can be directly mapped to the following 
SQL query:
\begin{quote}
{\tt select {\em projection list} from \\
\hspace*{0.2cm} Rel$_{1}$ X$_{1}$, \ldots , Rel$_{n}$ X$_{n}$, 
Rel$_{n+1}$ Y$_{1}$, \ldots, Rel$_{n+m}$ Y$_{m}$ where p}
\end{quote}
DBPL projection lists into SQL equivalents with no change, since syntax in 
both cases is the same.
\subsection{Predicates with Universal Quantifiers}
\label{quantified}
SQL supports several methods for expressing queries which require the
use of universal quantifiers when formulated in other languages 
\cite{Frat91}. These are the following:
\begin{description}
\item[Quantified comparisons] They are normal comparisons followed by 
the key words {\tt all} or {\tt any}, for example, {\tt $=$all}, {\tt $<$any}, 
{\tt $>=$all}, etc.  Because of the lack of universality of quantified 
comparisons the automatic conversion of DBPL' s universal quantifiers is 
problematic.
\item[Function ``count''] Since it requires materialization 
of its argument, this method may lead to performance problems. 
\item[Operator ``exists'']
The predicate {\tt ALL X IN R (p(X))} can be expressed in SQL as
\vspace*{\vlength}
\begin{verbatim}
  not exists (select * from R X where not p(X))
\end{verbatim}
\vspace*{\vlength}
The method seems to be the most promising because of its universality and 
potential for optimization; thus it is used in the implementation. The DBPL access expression
and the corresponding SQL statement for the query
(``Suppliers supplying all parts'') are
\vspace*{\vlength}
\begin{verbatim}
 EACH X IN supp: ALL  Y IN part
    (SOME Z IN sp ((X.sno = Z.sno) AND (Y.pno = Z.pno)))
\end{verbatim}
\vspace*{\vlength}
\vspace*{\vlength}
\begin{verbatim}
 select * from supp X1 where  not exists 
 (select * from part X2 where  not exists 
  (select * from sp X3 where X1.sno = X3.sno and X2.pno = X3.pno))
\end{verbatim}
\vspace*{\vlength}
\end{description}
\subsection{DBPL Expressions Mixing DBPL and Ingres Relations}
Two kinds of mixing can be distinguished.  In the first case, a DBPL 
statement contains sub-statements independent of external variables.  As an 
example, consider the expression
\vspace*{\vlength}
\begin{verbatim}
  EACH X IN supp: SOME Y IN sp (Y.pno = "P1")
\end{verbatim}
\vspace*{\vlength}
Assume that {\tt supp} is an Ingres table and {\tt sp} is a DBPL relation.  Since the 
internal sub-predicate does not reference the external variable X, we can 
evaluate it on the side of DBPL, and then generate a proper SQL statement.  
This method is applied in the implementation: using a procedure that 
recursively scans a predicate tree, discovers independent subpredicates, 
evaluates them, and then modifies the tree by reducing it and inserting the 
calculated truth values resp.  temporary relations.  In other cases mixing 
requires the application of escape methods.
\subsection{Predicates with a Range Relation Given by a Subpredicate}
SQL does not allow {\tt select} blocks in the {\tt from} clause, thus 
direct mapping of predicates with range subpredicates (range relations 
described by relation expressions) is impossible.  There are several 
methods of solving this problem, in particular unnesting and creation of a view 
on the Ingres side.  In this project we decided to create a temporary range 
relation on the Ingres side.
\subsection{FOR EACH Construct}
Mapping the FOR EACH construct of DBPL was the most difficult 
implementation problem. The semantics of the construct
\begin{quote}
{\tt
\hspace*{0.0cm}FOR EACH {\em variable} IN {\em relation}: {\em predicate} DO\\
\hspace*{0.2cm}       {\em sequence of statements}\\
\hspace*{0.0cm}END
}
\end{quote}
can be explained as follows.  The {\em sequence of statements} is executed 
for each tuple in {\em relation}, for which {\em predicate} is true.  The 
{\em sequence of statements} may contain arbitrary DBPL statements, in 
particular other ``FOR EACH'' statements.  The {\em variable} inside the 
{\em sequence of statements} is considered as a normal programming 
variable.  In particular, all updates of the {\em relation} can be done by 
this variable.  The updating semantics is, however, not straightforward: 
the variable contains a main memory copy of the processed tuple and all 
updates modify the copy only.  At the end of each loop the original tuple 
in the relation is modified according to the values of this eventually 
modified copy.

An example of the FOR EACH construct follows:
\vspace*{\vlength}
\begin{verbatim}
  FOR EACH X IN supp : X.city = "London" DO
    X.status := X.status + 10;
    FOR EACH Y IN sp : X.sno = Y.sno DO
      WriteString(X.sname); WriteString(Y.pno); WriteInt(Y.qty); 
    END;
  END;
\end{verbatim}
\vspace*{\vlength}
The above semantics has a direct counterpart in SQL relying on the 
application of cursors. Dynamic SQL assumes that the buffer for 
fetching/flushing a tuple is organized through SQLDAs. DBPL allows 
nested FOR EACH and recursion, thus  SQLDAs, names of cursors and SQL
{\em PREPARE} statements must be managed by a special stack, 
which we implemented in SQL+C.

The dynamic SQL version is neither clear nor well specified in SQL 
manuals; there are also some bugs. Thus the final solution is the result 
of experiments rather than careful reading of manuals. To serve the FOR 
EACH construct we need the following steps:
\begin{enumerate}
\item Generate a SQL query from the argument of the FOR EACH statement.  
The statement presented above will produce the query
\vspace*{\vlength}
\begin{verbatim}
  select X1.* from supp X1 where X1.city = "London"
\end{verbatim}
\vspace*{\vlength}
\item Execute {\em PREPARE} and {\em DESCRIBE} SQL commands with the 
the query generated in the previous step as argument. This step is 
necessary to obtain the attribute names of the relation.
\item Generate an extended SQL query
\vspace*{\vlength}
\begin{verbatim}
  <previous query> FOR DIRECT UPDATE OF <list of all attributes>
\end{verbatim}
\vspace*{\vlength}
The statement presented above will produce the query
\vspace*{\vlength}
\begin{verbatim}
  select X1.*  from supp X1  where X1.city = "London"
  FOR DIRECT UPDATE OF sno, sname, status, city
\end{verbatim}
\vspace*{\vlength}
\item Generate a new statement name and push it on the stack. Then
create a new SQLDA and push it also on the stack.
\item Execute {\em PREPARE} and {\em DESCRIBE} SQL statements for the given
extended query, statement name and SQLDA. 
\item Generate a new cursor name and push it on the stack. Then declare
the cursor.
\item Open the cursor. This is the preparation step for fetching tuples 
from the Ingres 
relation. 
\item Extract the relation name from the query and generate the SQL
update statement
\begin{quote}
{\tt UPDATE relation name \\
SET attribute$_{1}$ = ?,..., attribute$_{n}$ = ? \\
WHERE CURRENT OF cursor name}
\end{quote}
For the example above we generate the statement
\begin{quote}
{\tt UPDATE supp SET sno = ?, sname = ?, status = ?, city = ? \\
WHERE CURRENT OF dbcurs$_{i}$}
\end{quote}
\item Generate a new statement name and push it on the stack. Then
execute the SQL {\em PREPARE} statement w.r.t. the generated UPDATE 
statement and the new statement name. 
\end{enumerate}
Now, on the top of the stack we have two statements, one cursor and one 
SQLDA.  Fetching tuples requires the SQL {\em FETCH} command (with the 
cursor addressing the first statement), while flushing requires the SQL 
{\em EXECUTE} command addressing the second statement.

The above procedure is complicated, although the task is typical.  In our 
opinion, design solutions concerning cursor processing in embedded SQL were 
burdened by attempts to hide the fact that cursors are pointer-valued 
variables.  In effect, this programming interface is more difficult than 
it should be.
\subsection{Implementation of High-Level Relational Assignments}
For each of the four kinds of high-level relational assignments in DBPL 
(assign, insert, update, delete) we must consider four cases, depending
on the status of the left-hand and right-hand side relations
(DBPL/DBPL, DBPL/Ingres, Ingres/DBPL, Ingres/Ingres).  Each case implied 
specific methods.  Even in the Ingres/Ingres case not all operations can be 
executed by SQL because of the lack of power.  An example of these problems 
is the {\em delete} operation for the Ingres/DBPL case.  In DBPL the 
construct R$_{1} :-$ R$_{2}$ means removing from R$_{1}$ all those tuples 
whose primary keys are the same as for one of the R$_{2}$ tuples; values of 
other attributes of R$_{2}$ are not taken into account.  The SQL method of 
passing parameters to statements through question marks requires filling in 
values of {\em all} attributes.  As follows from DBPL semantics, some of 
attributes of $R_{2}$ tuples may be meaningless. To ignore them, we generate 
the SQL statement
\begin{quote}
{\tt DELETE FROM R$_{1}$ WHERE p$_{1}$ AND p$_{2}$ AND ... AND p$_{n}$}
\end{quote}
where n is the number of attributes. Predicate {\tt p$_{i}$} has the form 
{\tt attribute$_{i} =$ ?} for key attributes, and the form {\tt ( $1=1$ OR 
attribute$_{i} =$ ? )} for non-key attributes. For example, the DBPL 
statement
\vspace*{\vlength}
\begin{verbatim}
  supp :- suppRel{{"S1","",0,""}, {"S2","",0,""}};
\end{verbatim}
\vspace*{\vlength}
generates the SQL statement
\vspace*{\vlength}
\begin{verbatim}
  DELETE FROM supp  WHERE  sno = ?  AND (1=1 OR sname = ?)
     AND (1=1 OR status = ?)  AND (1=1 OR city = ?)
\end{verbatim}
\vspace*{\vlength}
This statement is executed for each tuple of the right hand side relation. 
The example clearly shows the disadvantage of the SQL {\em ad hoc} 
approach to generic programming.
\subsection{Relational Comparisons}
Since DBPL does not allow duplicate tuples, all comparisons can be 
performed by one operator {\em contains} (denoted $>=$).  Equality and 
strong comparisons are obtained by comparison of the numbers of tuples and 
{\em contains}.  Semantics of relational comparisons in DBPL assumes that 
only primary keys are taken into account.  That is, 
the DBPL predicate R$_{1}$ $>=$ R$_{2}$ means
\begin{quote}
{\tt $\pi_{primary keys}$( R$_{1}$ ) $\supseteq$ 
$\pi_{primary keys}$( R$_{2} )$}
\end{quote}
where $\pi$ denotes projection, and $\supseteq$ is an inclusion of sets.
As in the previous case, we must consider four cases of relational 
comparisons,
dependingly whether the left-hand side and right-hand side relations are on
the DBPL or Ingres side. 
In the case when one relation is DBPL and another is Ingres, we apply a 
sequential 
scan through the right hand side relation and check if the primary key of 
the tested 
tuple is present in the left hand side relation. If both relations are 
from the side of 
Ingres, we change predicate R$_{1}$ $>=$ R$_{2}$ into a quantified 
predicate
\begin{quote}
{\tt 
\hspace*{0.2cm}ALL Y IN R$_{2}$ (SOME X IN R$_{1}$\\
\hspace*{0.4cm}((X.key$_{1}$ = Y.key$_{1}$) AND \ldots AND (X.key$_{last}$ = Y.key$_{last}$)))}
\end{quote}
and then transform it in a corresponding {\em select} statement (see
sec. \ref{quantified}).
%and then generate the corresponding {\em select} statement:\\
%\\
%{\tt 
%\hspace*{0.2cm}SELECT * FROM AuxRel WHERE NOT EXISTS \\
%\hspace*{0.4cm}(SELECT * FROM R$_{2}$ Y WHERE NOT EXISTS \\
%\hspace*{0.6cm}(SELECT * FROM R$_{1}$ X WHERE X.key$_{1}$ = Y.key$_{1}$
%AND \ldots AND X.key$_{last}$ = Y.key$_{last}$ )) \\}
%\\
%As before, AuxRel is the name of auxiliary Ingres table containing exactly 
%one tuple and key$_{i}$ is the name of {\em i}-th primary key attribute.  
%If the result of the {\em select} is non-empty, it means that the original 
%query returns {\em TRUE}; otherwise {\em FALSE}

%*********************************** Section 5 ***********************
\section{Architecture of the Gateway}
The general architectural view of the gateway, DBPL and Ingres is presented
in Fig. \ref{gateconnections}.
\begin{figure}[htb]
\begin{center}
\leavevmode
\epsfxsize=9cm
%\epsfxsize=\columnwidth
\epsffile{archglob.epsf}
\end{center}
\caption{General view on the gateway, DBPL and Ingres}
\label{gateconnections}
\end{figure}
The entry Ingres interface is embedded SQL. We wrote a package of
procedures in embedded 
SQL + C capable of mapping all DBPL constructs (unfortunately the
dynamic embedding is not standardized until now).  The procedures are also 
available in a normal DBPL module.  They allow the user to write SQL 
statements inside DBPL programs, an advantage for some kinds of 
applications.

Exit points in DBPL implied more problems.  We assumed that the DBPL 
compiler should not be changed; all connections to Ingres should be done 
from the existing run-time system.  The DBPL run-time system consists of 
several layers and features of DBPL are tailored to parts of different 
layers.  Some work was necessary to make the architecture of the run-time 
system cleaner.  Afterwards it was possible to determine exit points 
``below'' the transaction processing system (thus the gateway does not deal 
with locking, unlocking, log, recovery, etc.) and ``below'' the system 
responsible for evaluation of DBPL selectors and constructors (thus the 
gateway also does not deal with them).  Exit points to Ingres are in the 
module responsible for evaluation of DBPL predicates and sometimes in the 
lower layer responsible for tuple-oriented processing of relations.

We introduced a change to the DBPL data dictionary allowing to distinguish
between DBPL and Ingres relations.  Since the compiler is unchanged, a DBPL 
program processing Ingres relations is exactly the same as that required 
for DBPL relations.  This means that each Ingres relation which has to be 
processed by DBPL should have a ``twin'' relation on the DBPL side.  
Normally this twin is empty and not used but it must be declared and 
stored.  Twin DBPL relations allow the user to retrieve typing information 
and sometimes they are internally used for storing intermediate results.
\begin{figure}
\begin{center}
\leavevmode
\epsfxsize=8cm
%\epsfxsize=\columnwidth
\epsffile{gatearch.epsf}
\end{center}
\caption{Architecture of the gateway}
\label{gatearch}
\end{figure}
The architecture of the gateway is presented in more detail in Fig. 
\ref{gatearch}.
A special utility is written to change the status of DBPL relations.  This 
utility compares types of corresponding DBPL and Ingres twin relations.  If 
the types are fully compatible, it allows the user to change the status of 
the DBPL relation so that further processing will be performed on the 
Ingres relation.

Generation of SQL queries from DBPL predicates is done by a recursive scan 
of the DBPL predicate tree.  During the scan a list of SQL lexicals is 
built.  Roots of the tree corresponding to access expressions cause pushing 
lexicals {\em select}, {\em from} and {\em where} to the list.  Then, 
projections in the tree insert proper lexicals after {\em select}, range 
relations in the tree insert proper lexicals after {\em from}, and 
conditional expression insert proper lexicals after {\em where}.  The list 
works as a stack: to take into account nested select blocks, the insertions 
are done after this {\em select}, {\em from} or {\em where}, which is the 
nearest from the top of the list.  When the select block is completed it is 
``masked'' (so it is not seen by further insertions).  This algorithm is 
modified for {\em exists} and other lexicals to take into account all 
situations that can occur in DBPL predicate trees.  The final SQL query is 
obtained by direct generation of the query text from the list of lexicals.

For evaluating DBPL predicates containing mixed references to DBPL and Ingres 
relations the corresponding predicate tree is recursively scanned and 
one of the following answers is produced: {\em pure dbpl, pure ingres, top dbpl, top 
ingres, mixed joins, badly mixed}.  The answer {\em pure ingres} means that 
the predicate contains only references to Ingres relations and can be 
converted into a SQL query.  {\em Top dbpl} means that the predicate 
contains independent subpredicates that are {\em pure ingres}. They 
can be evaluated internally and the whole predicate becomes {\em 
pure dbpl}.  Similarly, {\em top ingres} means that the predicate contains 
subpredicates that are {\em pure dbpl}; they can be internally evaluated on 
the side of DBPL, then the resulting temporary relations are copied to the 
Ingres side, thus the whole predicate becomes {\em pure ingres}.  In the 
case of {\em mixed joins} we send the participating DBPL relations to the 
Ingres side (the escape method), thus the predicate becomes {\em pure 
ingres}.  The result {\em badly mixed} means that all good methods fail, 
and the only method is copying Ingres relations to the DBPL side.  For 
performance reasons we prefer to generate in such a case a run-time error 
in the current implementation.

%*********************************** Section 6 ***********************
\section{Implementation Difficulties}
A few problems were caused on the side of DBPL. On the language level
the missing possibility of using arithmetic and other operators inside
the high-level constructs limits the utilization of the full power of
SQL. On the system level the use of Modula-2 as system-programming
language requires that all advanced data structures are stored in
dynamic memory. This concerns, in 
particular, syntactic trees for high-level expressions and predicates, type 
descriptors, and the data dictionary.  Receiving information from these 
structures requires navigation via pointers, a feature which is cumbersome 
and error-prone.  In Modula-2 there is no alternative solution.  This is an 
argument in favour of languages having the possibility to define bulk 
types. The construction and semantics of internal DBPL structures is not 
always well specified and clear.  Small optimizations concerning syntactic 
trees introduced additional difficulties in recognizing their semantics and 
in traversing them.

Most of the problems had their origin on the SQL side especially in 
bad design assumption of SQL and its (dynamic) embedding concept.
\begin{enumerate}
\item Communication of dynamic SQL with the external world is based on 
prepared statements, cursors, and SQL Description Areas.  This interface is 
not well prepared for nested and recursive processing, which is inherent 
for languages like DBPL.  Therefore we have to implement a special stack of 
statements, cursors and SQLDAs together with operators acting on this 
stack.
\item Although the concept of primary keys is a fundamental part of the
relational model, SQL has no direct possibility of updates based on primary
keys. In contrast, in DBPL all updates are based on primary keys. This
causes problems in expressing some DBPL updates in SQL.
\item The missing orthogonality of the language leads to problems in the 
automatic generation of SQL queries.  For example there is no nested union, 
there are no range expressions described by queries, all this must be done 
on the DBPL side. Another example is the {\tt select count(*) from 
...} statement where we would prefer the syntax {\tt count( select ...  
from ...)}.
\item No queries returning boolean values, they must be simulated by 
counting the number of elements of a corresponding select-statement.
The missing truth values requires the substitution by formulas like {\tt 1=1} or {\tt 1=0}.
\end{enumerate}
Sometimes it is also difficult to retrieve internal information from the 
system which is necessary for writing generic applications. May be the 
ongoing standardization work (f.e. for the data dictionary) will lead to a
better situation.
\begin{enumerate}
\item There are difficulties in retrieving all information about Ingres 
tables; in particular, this concerns recognizing which attributes are 
forming the primary keys.
\item No comparison of tuples for equality, and no (officially supported) 
explicit tuple identifiers and operations on them.  
\item In programming of generic applications we need to ``capture'' some 
system reactions to errors.  These reactions and error codes are not well specified in the 
documentation of Ingres. 
In this context the automatic generation of the {\em SQL STOP} statement, in all possible 
places where an error is expected, is controversial.  STOPs after errors 
are frequently unacceptable, because before the stop some operations must 
be performed.  This forces use to use the statement {\em WHENEVER SQLERROR 
CONTINUE} after each SQL statement, which makes the text of the program 
longer and less readable.
SQL itself gives poor testing capabilities for programmers, e.g. about names
of available relations, about their ownership, status, number of tuples, 
etc.
\end{enumerate}
With new releases (and realizations) of the SQL-standard, which will also
cover dynamic SQL, some of the following problems will hopefully become 
obsolete.
\begin{enumerate}
\item The system of navigation through cursors gives no possibility to 
navigate to the {\em prior} tuple,  making the implementation of browsing 
capabilities extremely difficult.
\item SQL dynamic statements use question marks as ``formal parameters''.  
This is inconvenient and error-prone.
\item To open a cursor for updating in dynamic SQL, the programmer must 
generate the statement {\em select ...  from ...  FOR DIRECT UPDATE OF ...} 
which is not described in the manual (we invented it by experiments).
\item There are some not well-justified syntactic features of SQL 
statements; for example, an {\em update} statement through a cursor 
requires the relation name despite the fact that it was determined 
previously during declaration of the cursor.
\item Direct update through cursors may change the order of rows, what 
means that the processing may lose consistency (e.g.  the same row will be 
updated two times).
\end{enumerate}
Surprisingly there also have been technical problems with bugs in the 
used version of the Ingres system. So opening a cursor for a query
returning an empty result causes a run-time error.  Because normally it
is impossible to predict whether the result of a user query is empty or
non-empty a special handling of empty query results is necessary.
Another example was the {\em WHENEVER SQLERROR CONTINUE} statement that
does not work in all cases, requiring the manual correction of the C programs generated by the ESQL-precompiler.

%*********************************** Conclusion *************************
\section{Conclusion}

The implementation of the gateway from DBPL to the commercial Ingres 
system achieves several results. A direct pragmatic result is that Ingres 
databases are now transparently accessible within DBPL programs. This 
allows the user to build up modular designed applications using a type-safe 
language with orthogonal language constructs thereby significantly reducing the 
risk of run-time errors and increasing the maintainability and 
extensibility of the application while using the reliability and 
effectiveness of a commercial database system developed and improved over 
years. It
has also uncovered some limitations and disadvantages of both DBPL and 
SQL. When considering DBPL, we recognized limitations of high-level constructs 
which may produce problems for 
users especially if they  come from the SQL world. The advantage of DBPL 
- strong typing - may become a hindrance to the development of some applications 
requiring generic procedures mainly because of its monomorphic type
system. This shows directly the need for new languages with polymorphic
type systems as a base for persistent programming and system 
construction \cite{ScMa93}. 

The majority of problems were connected, however, with SQL.  In contrast 
to the enthusiasm found in popular database textbooks, our experience with 
SQL as a programming language indicated that SQL is below the 
state-of-the-art. Many {\em ad-hoc} solutions, irregularity of syntax and 
semantics, limitations, unclear rules of  use, an approach to 
user-friendliness which forbids untypical (but
still  reasonable) situations, lack of programming abstractions, etc.
make the programming of generic programs difficult and frustrating. 

This clearly emphasizes the necessity and usefulness of our approach to 
view database systems simply as external servers which can be accessed via 
powerful languages like DBPL.  We feel that SQL has yet to achieve the 
maturity necessary for next-generation databases.  It is our hope that this 
paper helps clarify some design pitfalls in database languages and offers a 
way to solutions for avoiding these problems.


%****************************** References *************************

\begin{thebibliography}{XXXXX88}

\bibitem[Banc92]{Banc92} F. Bancilhon.
\newblock Understanding Object-Oriented Database Systems.
\newblock Advances in Database Technology - EDBT '92, Proc. of 3rd 
International
Conference on Extending Database Technology, Vienna, Austria, March 1992, 
Springer LNCS 580, pp.1-9, 1992

\bibitem[Date87]{Date87} C.J. Date.
\newblock A Guide to Ingres.
\newblock Addison-Wesley 1987.

\bibitem[ERMS91]{ERMS91} J.~Eder, A.~Rudloff, F.~Matthes, J.W.~Schmidt.
\newblock Data Construction with Recursive Set Expressions.
\newblock Next Generation Information System Technology. Proc. of 1st 
East/West 
Database Workshop, Kiev, USSR, Oct.1990, Springer LNCS 504, 1991, pp.271-293

\bibitem[Frat91]{Frat91} C. Fratarcangeli.
\newblock Technique for Universal Quantification in SQL.
\newblock SIGMOD RECORD Vol.20, No.3, Sep. 1991, pp.16-24

\bibitem[IngrA89]{IngrA89}
\newblock Ingres/SQL Command Summary for the UNIX and VMS Operating 
Systems.
\newblock Release 6, Relational Technology Inc., August 1989

\bibitem[IngrB89]{IngrB89}
\newblock Ingres/SQL Reference Manual.
\newblock Release 6, Relational Technology Inc., August 1989

\bibitem[Ingr90]{Ingr90} Language Reference Manual for INGRES/Windows 4GL 
for the UNIX and VMS Operating Systems.
\newblock  INGRES Release 6, Ingres Corporation, August 1990.

\bibitem[Orac91]{Orac91} 
PL/SQL, User Guide and Reference, Version 1.0, June 1991.
\newblock Oracle Corporation 1991.

\bibitem[MRSS92]{MRSS92} F.~Matthes, A.~Rudloff, J.W.~Schmidt, K.~Subieta.
\newblock The Database Programming Language DBPL, User and System Manual.
\newblock FIDE, ESPRIT BRA Project 3070, Technical Report Series, 
FIDE/92/47, 1992

\bibitem[ScMa91]{ScMa91} J.W.~Schmidt, F.~Matthes.
\newblock The Rationale behind DBPL.
\newblock 3rd Symposium on Mathematical Fundamentals of Database and Knowledge Base Systems, Springer LNCS 495, 1991.

\bibitem[ScMa92]{ScMa92} J.W.~Schmidt, F.~Matthes.
\newblock The Database Programming Language DBPL, Rationale and Report.
\newblock FIDE, ESPRIT BRA Project 3070, Technical Report Series, 
FIDE/92/46, 1992

\bibitem[ScMa93]{ScMa93} J.W.~Schmidt, F.~Matthes.
\newblock Lean Languages and Models: Towards an Interoperable Kernel for
Persistent Object Systems.
\newblock Proceedings if the IEEE International Workshop on Research
Issues in Data Engineering RIDE'93 Vienna, Austria, April 1993

\begin{sloppypar}
\bibitem[SRLG+90]{SRLG+90} M. Stonebraker, L.A. Rowe, B. Lindsay, J.
Gray, M. Carey, M. Brodie, P. Bernstein, D.~Beech:
\newblock The C\-ommittee $ $for $ $Advanced $ $DBMS $ $Function.
\newblock $ $Third-Generation $ $Data Base $ $System Manifesto. 
\newblock ACM SIGMOD Record 19(3), pp.31-44, 1990. 
\end{sloppypar}
\end{thebibliography}

\end{document}
