\documentstyle[a4,epsf]{article}
%\setlength{\textwidth}{16cm}
%\setlength{\textheight}{24cm}
\setlength{\baselineskip}{4mm}
\begin{document}

%*********************************** 1st slide ***********************
\Huge
\vspace*{1cm}
\begin{center}
{\bf A Gate from DBPL\\ to Commercial INGRES}\\
\end{center}
\vspace*{1cm}
\LARGE
\begin{tabular}{lll}
Designers: & &\\
           & Florian & Matthes\\
           & Andreas & Rudloff\\
           & Joachim W. & Schmidt\\
           & Kazimierz & Subieta\\
Programming: & &\\
           & Kazimierz & Subieta\\
           &           & (who persistently disturbed\\
           &           & F.Matthes and A.Rudloff)\\
Testing: & &\\
           & Plamen & Kiradjiew\\
           & Andreas & Rudloff\\
           & Kazimierz & Subieta\\
\end{tabular}
\vspace*{2cm}


\begin{tabular}{ll}
{\bf Modula-2} & - a programming language\\
{\bf DBPL}     & - an extension of Modula-2 \\
               & (bulk and persistent data, queries,...)\\
{\bf INGRES}   & - a commercial database management syst.\\
{\bf SQL+C}    & - SQL embedded in the progr. language C:\\
               & one of INGRES programming interfaces.\\
\end{tabular}
\pagebreak

%*********************************** 2nd slide ***********************
\Huge
\begin{center}
{\bf Motivations}
\end{center}
\vspace*{1.5cm}
\huge
\begin{enumerate}
\item General: bridges over different worlds support progress and development;
\item Current programming interfaces to commercial database systems make
impression to be below the state-of-the-art (embedded SQL, PL/SQL);
\item 4GL Programming is attractive, but it has no established
tradition and design principles: there are ad hoc solutions and unclear
limitations in power;
\item Avoiding impedance mismatch;
\item Make possible database programming based on principles of strong typing, orthogonality, computational completeness and abstraction;
\item The {\bf new programming language syndrome}: own database format, no powerful utilities, ...: no rabbits who want to use a new system;
\item  Possibility to access large databases made under INGRES: meaning for didactics and research activities;
\end{enumerate}
\pagebreak

%*********************************** 3rd slide ***********************


\Huge
\begin{center}
{\bf Approaches to Make a Gate}
\end{center}
\vspace*{1cm}

\LARGE
\begin{enumerate}
\item {\bf A precompiler for SQL embedded in DBPL}\\

\item {\bf Procedures calling INGRES routines}\\
Full access to INGRES databases through routines calling dynamic SQL: impedance mismatch.\\

\item {\bf Package of procedures serving INGRES files}\\
SQL optimizer, concurency mechanisms of INGRES, indices, catalogs, etc. would not be used. Physical organization of INGRES databases is probably not easy and not well specified.\\

\item {\bf A gateway from DBPL serving INGRES files}\\
INGRES database is seen as a normal DBPL database. SQL optimizer, INGRES concurrency control, etc. would not be used.\\

\item {\bf Interface from the DBPL run-time system to the INGRES SQL machine}\\
All references from DBPL programs to INGRES databases are transformed into 
dynamic SQL statements.\\
\end{enumerate}
\pagebreak

%*********************************** 4th slide ***********************
\Huge
\begin{center}
{\bf Differences of data structures}
\end{center}
\vspace*{1cm}

\huge
\begin{enumerate}
\item DBPL allows {\bf nested relational structures}.
INGRES deals with flat relations only.\\

\item In DBPL {\bf primary keys} of relations are conceptual issue. In INGRES  information about primary keys is irrelevant for querying and programming.\\

\item DBPL uses machine-independent {\bf convention for types} (cardinal,
integer, char, ...), while INGRES uses the convention with roots in 
the traditional data processing (money, date,...). \\

\item INGRES deals with {\bf null-values}, while DBPL does not.\\

\item INGRES allows {\bf duplicates} either in stored relations and in
intermediate query outputs. DBPL does not allow duplicate tuples.
\end{enumerate}

\pagebreak
%*********************************** 5th slide ***********************
\Huge
\begin{center}
{\bf Levels of Database Interfaces}
\end{center}
\vspace*{2cm}

\begin{figure}[h]
\begin{center}
\leavevmode
\epsfxsize=14cm
\epsffile{pic1.epsf}
\end{center}
\end{figure}
\pagebreak

%*********************************** 6th and 7th slides *****************
\Huge
\begin{center}
{\bf High-level Constructs of DBPL}
\end{center}
\vspace*{1cm}
\LARGE
\begin{itemize}

\item Selective access expressions, for example:
\begin{verbatim}
EACH X IN supp: X.city = "London"

EACH X IN supp: SOME Y IN sp (X.sno = Y.sno)
\end{verbatim}
They have direct counterparts in SQL.

\item Quantified boolean expressions, for example:
\begin{verbatim}
ALL X IN part ( SOME Y IN sp (X.pno = Y.pno))
\end{verbatim}
Several counterparts in SQL.

\item Constructive access expressions, for example:
\begin{verbatim}
{X, Y} OF EACH X IN supp, EACH Y IN sp:
            (X.sno = Y.sno) AND (Y.qty > 200)

{X.sname,Y.pno} OF EACH X IN supp, Y IN sp:
            (X.sno=Y.sno) AND (Y.qty>200)
\end{verbatim}
They have a direct counterpart in SQL.

\item Relation expressions, for constructing sets of relation elements, for 
example:
\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}

\item Union operator, for example:
\begin{verbatim}
suppRel{ EACH X IN supp: X.city = "London",
         EACH Y IN supp: Y.status > 10,
         { "S8", "Miller", 20, "Paris"}    }
\end{verbatim}
INGRES SQL also supports union, but only on the top nesting level.

\item Relational operators $=$, \#, $<$, $<=$, $>$, $>=$ denoting relation 
equality, non-equality and set-theoretic inclusions:
\begin{verbatim}
suppRel{EACH Y IN supp: Y.status>30} <= 
    suppRel{EACH X IN supp: X.city="London"}
\end{verbatim}
SQL does not support these comparisons.
 
\item Assignments on relations making possible all updates: $:=$ (assign), 
$:-$ (delete), $:+$ (insert), and :\& (update), for example:
\begin{verbatim}
mysupp := suppRel{EACH Y IN supp:Y.status>20};
supp   :- suppRel{ "S1", "", 0, "" };
supp   :+ suppRel{"S1","Schmidt",25,"Berlin"};
supp   :& suppRel{"S1","Schmidt",30,"Berlin"};
\end{verbatim}

\item Standard DBPL functions: CARD, EXCL, INCL;
\end{itemize}

Semantics of many DBPL high-level features is based on primary keys.

\pagebreak
%*********************************** 8th slide ***********************
\Huge
\begin{center}
{\bf Abstractions, null-values, concurrency}
\end{center}
\vspace*{1cm}
\huge
\begin{itemize}
\item SQL views are special objects, with independent existence in the INGRES 
database.\\
DBPL "constructors" and "selectors" are properties of the source text of programs.\\
Common conceptual intersection, but different capabilities and pragmatics.\\
Thus we do not deal with them.\\

\item INGRES database procedures, integrities and access permisions:\\
DBPL has no equivalent notions.\\

\item Null-values: DBPL has no equivalent notions.\\

\item Concurrency control: no problem since DBPL application is simply
a client of INGRES. Nested transactions (?)
\end{itemize}
\pagebreak

%*********************************** 9th slide ***********************
\Huge
\begin{center}
{\bf Dynamic SQL: Generic\\ Programming in INGRES}
\end{center}
\vspace*{1cm}
\huge
Extension of capabilities of embedded SQL.\\
SQL statements are strings of characters 
which can be manipulated during run time.\\
Differences in semantics and pragmatics in comparison to normal embedded SQL.\\
\\
SQL Description Area (SQLDA).\\
\\
\LARGE
\begin{center}
\begin{tabular}{||l|ll||}
\hline
       & & Some constant data\\
\hline
sqln   & & Size of table sqlvar\\
\hline
sqld   & & Nbr of columns in the table\\
\hline
sqlvar & & An sqln-size array:\\
\cline{2-3}
       & sqltype & Type of an attribute\\
       & sqllen  & Length of the attr.\\
       & {\bf sqldata} & Pointer to the attr. value\\
       & sqlind  & Pointer to null indicator\\
       & sqlname & Attribute name\\
\cline{2-3}
       & sqltype & \\
       & sqllen  & \\
       & {\bf sqldata} & \\
       & sqlind  & \\
       & sqlname & \\
\cline{2-3}
       & ..... & \\
\hline
\end{tabular}
\end{center}
\pagebreak



%*********************************** 10th slide ***********************
\Huge
\begin{center}
{\bf Dynamic SQL, continued}
\end{center}
\vspace*{1cm}
\huge
Pointers {\em sqldata} are counterparts of host variables in embedded SQL.They
are filled in by an application program, and point to values, which are stored 
elsewhere.\\
\\
Applications of SQLDA:
\begin{enumerate}
\item {\em select} statements: determines var-s where attributes of a selected tuple will be written.
\item Determines actual parameters of an SQL statement.
The method assumes application of statements containing 
question marks as "formal parameters".
\end{enumerate}

\begin{verbatim}
INSERT INTO supp(sno,sname,status,city)
          VALUES( ?,   ?,    ?,    ?  )
\end{verbatim}
Pointers {\em sqldata} point values, which will substitute question marks 
when the statement is executed.\\\\
Statements PREPARE (parse and optimize), DESCRIBE (fill in typing information
in SQLDA), and EXECUTE (execute the statement).
\pagebreak



%*********************************** 11th slide ***********************
\Huge
\begin{center}
{\bf Low-level DBPL Capabilities}
\end{center}
\vspace*{1cm}
\huge
\begin{itemize}
\item LOWEST: find a tuple having {\em lowest} primary key 
\item HIGHEST: find a tuple having {\em highest} primary key
\item THIS: find a tuple having {\em this} primary key
\item NEXT: find a tuple having {\em next} primary key
\item PRIOR: find a tuple having {\em prior} primary key
\end{itemize}
\vspace*{1cm}
Sometimes they cannot be avoided (merging, browsing), but
SQL has no equivalents.\\
\\
So far we have no idea how to map them.
\pagebreak

%*********************************** 12th slide ***********************
\Huge
\begin{center}
{\bf Mapping DBPL Constructs into SQL (1)}
\end{center}
\vspace*{1cm}
\huge
{\bf Escape Methods}\\
\\
\begin{itemize}
\item Copying DBPL relation(s) to the INGRES side.\\

\item Copying INGRES table(s) to the DBPL side.\\

\item Tuple substitution according to INGRES or DBPL relation(s). INGRES or DBPL relation(s) will be processed tuple-by-tuple. The method 
requires "additivity" of DBPL predicates with respect to processed tuples.
\end{itemize}
\pagebreak


%*********************************** 13th slide ***********************
\Huge
\begin{center}
{\bf Mapping DBPL Constructs into SQL (2)}
\end{center}
\vspace*{1cm}
\huge
{\bf DBPL expressions without quantifiers ALL and SOME}\\
\\
{\tt  EACH X IN Rel: p(X) \\}
\\
{\tt  \{ {\em projection list} \} OF \\
EACH X$_{1}$ IN Rel$_{1}$,...,EACH X$_{n}$ IN Rel$_{n}$:\\
p(X$_{1}$,...,X$_{n}$) \\}
\\
If p does not contain quantifiers, and all comparisons in p are available 
in SQL, then:\\\\
{\tt select X.* from Rel X where p(X)\\}
\\
{\tt select {\em projection list} \\
from Rel$_{1}$ X$_{1}$, ... , Rel$_{n}$ X$_{n}$\\
where p(X$_{1}$,...,X$_{n}$)\\}
\pagebreak


%*********************************** 14th slide ***********************
\Huge
\begin{center}
{\bf Mapping DBPL Constructs into SQL (3)}
\end{center}
\vspace*{1cm}
\huge
{\bf DBPL predicates\\ returning boolean values}\\
\\
SQL has no semantic domain with boolean values. Thus
DBPL predicate p is converted into the following SQL statement:
\begin{verbatim}
select * from AuxRel where p
\end{verbatim}
where AuxRel is the name of auxiliary INGRES table containing exactly one tuple.\\  
\\
The DBPL predicate\\
("Have all suppliers the status higher than 10?")
\begin{verbatim}
ALL X IN supp ( X.status > 10 )
\end{verbatim}
is converted to the following SQL query:\\
\begin{verbatim}
select * from AuxRel
where not exists( 
          select * from supp X1
          where not( X1.status > 10 ) )
\end{verbatim}
\pagebreak


%*********************************** 15th slide ***********************
\Huge
\begin{center}
{\bf Mapping DBPL Constructs into SQL (4)}
\end{center}
\vspace*{1cm}
\huge
{\bf Universal Quantifiers}\\
\\
{\bf DBPL:} {\tt ALL X IN R (p(X))}\\
{\bf SQL:} {\tt not exists(\\
\hspace*{1.5cm}select * from R X where not p(X))}\\\\
Existential quantifiers are also implemented via {\em exists}.
An example of conversion: ("Suppliers supplying all parts")\\\\
{\bf DBPL:}
\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}
{\bf SQL:}
\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}
\pagebreak



%*********************************** 16th slide ***********************
\Huge
\begin{center}
{\bf DBPL Expressions Mixing DBPL and INGRES Relations.\\Range predicates}
\end{center}
\vspace*{1cm}
\LARGE
\begin{itemize}
\item {\bf Easy mixing}: when subexpressions are pure DBPL or pure INGRES\\
{\tt EACH X IN supp: SOME Y IN sp(Y.pno="P1")}\\

\item {\bf Mixed joins}: when INGRES relations are joined with flat DBPL relations.
\begin{verbatim}
EACH X IN supp: SOME Y IN sp( 
         (X.sno=Y.sno) AND (Y.pno="P1"))
\end{verbatim}
Implies copying DBPL relations to the INGRES side.\\
\item {\bf Badly mixed}: e.g. when an INGRES relation is mixed with a nested 
DBPL relation.\\
\item {\bf Range predicates}: not available in SQL. We create a temporary
relation on the INGRES or DBPL side. Another method is creating a view.\\
If range predicates contain external variables, then they are badly mixed.
\end{itemize}
\pagebreak


%*********************************** 17th slide ***********************
\Huge
\begin{center}
{\bf Recognition of mixing}
\end{center}
\vspace*{1cm}
\LARGE
Based of the recursive traversing of DBPL predicate trees.

\begin{figure}[h]
\begin{center}
\leavevmode
\epsfxsize=15cm
\epsffile{pic4.epsf}
\end{center}
\end{figure}
\begin{itemize}
\item Propagating the relation status to variables.
\item Bottom-up propagating the status to higher level roots of the tree.
\end{itemize}
\pagebreak


%*********************************** 18th slide ***********************
\Huge
\begin{center}
{\bf FOR EACH Construct of DBPL}
\end{center}
\vspace*{1cm}
\LARGE
{\tt FOR EACH {\em variable} IN {\em relation} : {\em predicate} DO\\
\hspace*{1cm} {\em sequence of statements}\\
END\\}
\\
\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);
    WriteLn;
  END;
END;
\end{verbatim}
\vspace*{1cm}
Nested FOR EACH statement.\\
Recursive procedures\\
SQL gives no possibility of recursion.\\
We must implement {\bf recursive possibilities of SQL}, through
the stack of SQLDA areas, statements and cursors.\\
\\
The solution is complicated and tricky, although the
task is typical. Conclusion: dynamic SQL is not really prepared for
writing generic programs.
\pagebreak

%*********************************** 19th slide ***********************
\Huge
\begin{center}
{\bf High-level Relational Assignments}
\end{center}
\vspace*{1cm}
\LARGE
For each of four kinds of high-level relational assignments in DBPL (assign, 
insert, update, delete) we must consider four cases, dependingly which kinds
of relations are on the left and right side of an assignment. \\\\
Tricky solutions, for example,
\begin{verbatim}
supp :- suppRel{{"S1","",0,""},{"S2","",0,""}};
\end{verbatim}
generates the following SQL statement (which "masks" non-key attributes):
\begin{verbatim}
DELETE FROM supp WHERE sno    = ?
           AND (1=1 OR sname  = ?)
           AND (1=1 OR status = ?) 
           AND (1=1 OR city   = ?)
\end{verbatim}
This statement is executed for each DBPL tuple from the righ-side relation.
\pagebreak



%*********************************** 20th slide ***********************
\Huge
\begin{center}
{\bf High-level Relational Comparisons}
\end{center}
\vspace*{1cm}
\LARGE
All set comparisons of DBPL are done by an operator {\em contains} and the comparison of the numbers of tuples.\\
\begin{center}
R$_{1}$ $ {\em contains} $ R$_{2}$
\end{center}
means
\begin{center}
{\tt $\pi_{primary keys}$( R$_{1}$ ) $\supseteq$ $\pi_{primary keys}$( R$_{2} )$}
\end{center}
\vspace*{1cm}
4 cases, dependingly on the kinds of relations. If both relations are from the side of INGRES, then we change into predicate\\
\\
{\tt ALL Y IN R$_{2}$( SOME X IN R$_{1}$((X.key$_{1}$ = Y.key$_{1}$) \\
\hspace*{1cm}AND .. AND (X.key$_{last}$ = Y.key$_{last}$)))\\}
\\
and then generate the equivalent {\em select} statement:\\
\\
{\tt SELECT * FROM AuxRel WHERE NOT EXISTS( \\
\hspace*{0.5cm}SELECT * FROM R$_{2}$ Y WHERE NOT EXISTS( \\
\hspace*{1cm}SELECT * FROM R$_{1}$ X\\
\hspace*{1cm}WHERE X.key$_{1}$ = Y.key$_{1}$\\ 
\hspace*{1cm}AND ..AND X.key$_{last}$ = Y.key$_{last}$ ))}
\pagebreak




%*********************************** 21th slide ***********************
\Huge
\begin{center}
{\bf Architecture of the Gate}
\end{center}
\vspace*{1cm}

\begin{figure}[h]
\begin{center}
\leavevmode
\epsfxsize=16cm
\epsffile{pic2.epsf}
\end{center}
\end{figure}
\pagebreak




%*********************************** 22th slide ***********************
\Huge
\begin{center}
{\bf Detailed Architecture\\ of the Gate}
\end{center}
\vspace*{1cm}

\begin{figure}[h]
\begin{center}
\leavevmode
\epsfxsize=16cm
\epsffile{pic3.epsf}
\end{center}
\end{figure}
\pagebreak


%*********************************** 23th slide ***********************
\Huge
\begin{center}
{\bf Open Problems}
\end{center}
\vspace*{1cm}
\huge
\begin{itemize}
\item No arithmetic and other operators inside DBPL 
predicates causes that the full power of SQL cannot 
be utilized.
\item Mapping DBPL nested relations into two or more INGRES relations connected
by referential integrities
\item Optimization of the case when a DBPL predicate mixes references to DBPL 
and INGRES relations
\item Processing null-values by DBPL.
\item Duplicate handling
\item Ordering
\item Mapping of DBPL selectors or constructors into SQL views.
\item Utilization in DBPL various capabilities of 
INGRES: form management, 4th-generation programming, access rights, integrities, various kinds of rules, database procedures, and so on.
\end{itemize}

\end{document}

