% File:    spektrum.tex
% Author:  FM
% Date:    7-FEB-1992
% Purpose: Spektrum der Wissenschaft: Das Aktuelle Schlagwort
%

\documentstyle[german,xple_sl,florian-named,twocolumn]{article}
\textwidth 17.5cm
\topmargin -0.5cm
\oddsidemargin -1cm
\evensidemargin \oddsidemargin
\textheight 24cm
\topskip 0cm
\baselineskip 0.5mm

\newcommand{\e}[1]{{\em{#1}\/}}
\newcommand{\k}[1]{{\bf{#1}}}
\renewcommand{\labelitemi}{$\triangleright$}

\hyphenation{Typ-ope-rato-ren}
\hyphenation{Typ-in-fe-renz}
\hyphenation{Typ-in-fe-renz-mecha-nis-men}
\hyphenation{Typ-kon-zep-te}
\hyphenation{re-dun-dan-ten}

\title{Informatik Spektrum \\
Das aktuelle Schlagwort: \\
Datenbankprogrammiersprachen}
\author{Florian Matthes \and Joachim W.~Schmidt}
\date{\small\em
Universit"at Hamburg\\
Fachbereich Informatik\\
Arbeitsbereich DBIS\\
Vogt-K"olln Str.~30\\
2000 Hamburg 54\\
\today
}

\begin{document}
\maketitle
\noindent Datenbankprogrammiersprachen entstehen durch die konzeptuelle
Integration von Datenbankmodellen und algorithmisch vollst"andigen
Programmiersprachen. Sie leisten damit einen Beitrag zur Realisierung
ad"aquater Entwicklungsumgebungen f"ur datenintensive Anwendungen.

Motiviert wird diese Integration einerseits durch die inzwischen
allgemein klar erkannte Diskrepanz zwischen mengenorientierter,
deklarativer Datenverarbeitung in Datenbanksystemen und dem
elementorientierten, prozeduralen Paradigma konventioneller
Programmiersprachen (\e{impedance mismatch}).  Dar"uber hinaus gibt es
jedoch noch weitere Unvertr"aglichkeiten wesentlicher Konzepte in
Datenbankmodellen und Sprachen zur Anwendungsprogrammierung; Beispiele
hierf"ur sind Benennbarkeits- und Strukturierungsmechanismen sowie
Bindungszeitpunkte und Methoden zur Lebensdauerkontrolle (\e{competence
mismatch}).  Diese Inkompatibilit"aten f"uhren nicht nur zu oft
beklagten Performanzverlusten an der Schnittstelle zwischen Wirtsprache
und Datenbanksystem, sondern erzwingen vor allem redundante
Deklarationen und aufwendige repetitive Konvertierungsoperationen auf
niedrigem Abstraktionsniveau, die hohe Folgekosten im gesamten
Lebenszyklus der Applikationsprogramme nach sich ziehen.

Zur "Uberwindung dieser konzeptuellen Schwierigkeiten bieten
Datenbankprogrammiersprachen (DBPLs) linguistische Unterst"utzung auf
drei Ebenen:

\begin{description} 

\item[Persistenzabstraktion] durch die uniforme sprachliche Behandlung
fl"uchtiger sowie langlebiger Datenobjekte;

\item[Typvollst"andigkeit] unter besonderer Ber"ucksichtigung von
Massendaten (\e{bulk data types});

\item[Iterationsabstraktion] z.B.~durch quan\-ti\-fi\-zier\-te
Pr"a\-di\-ka\-te, mengenwertige Ausdr"ucke, Funktoren oder
unifikationsbasierte Datendeduktion.

\end{description}
\pagebreak
Neben diesen konzeptuellen Anforderungen, die auf ad\"aquatem
sprachlichen Niveau zu erf\"ullen sind (\e{Orthogonalit"at},
\e{Generik}, \e{Formalit"at}) werden an Datenbanksprachen auch hohe
\e{operationale} Anforderungen gestellt, wie z.B.~optimierender Zugriff
auf Sekund"arspeicher, Unterst"utzung der Transaktionsprogrammierung
sowei Verteilung und Kommunikation.  Zunehmende Bedeutung gewinnen
dar"uber hinaus solche Architekturen von DBPL Implementationen, die eine
Eingliederung in bereits existierende Systemarchitekturen
(Netzwerkdienste, Transaktionsmonitore, Benutzerschnitsstellen,
Objektspeicher) unterst"utzen (\e{Offenheit}, \e{Interoperabilit"at}).

Ausgehend von ersten Arbeiten Ende der 70er Jahre \cite{Schm77a} wird
die rasche Entwicklung dieses Forschungsgebiets durch zahlreiche
Ver"offentlichungen, Workshops \cite{dbpl1,dbpl2,dbpl3,RoKo89,POS90} und
nicht zuletzt durch evaluierbare Systeme und Produkte dokumentiert. An
dieser Stelle wird lediglich eine grobe Klassifikation in drei
Hauptentwicklungslinien von Datenbankprogrammiersprachen vorgenommen
sowie eine Einf"uhrung in Konzepte und einige realisierte Sprachen
gegeben.  Die angegebene Literatur, insbesondere \cite{AtBu86,ScMa90a},
erm"oglichen eine tiefergehende Auseinandersetzung mit dem Thema.

\subsection*{Typorientierte Datenbankprogrammiersprachen}

Eine wesentliche Sprachfamilie l"a"st sich durch ihre Ausrichtung an
wohlverstandenen Konzepten prozeduraler Programmiersprachen
charakterisieren (statische, blockstrukturierte Sichtbarkeitsregeln,
statische, strikte Typ"uberpr"ufung, Typkonstruktoren, Parametrisierung,
Modularisierung)

Mitglieder dieser Klasse sind die \e{Relationalen
Datenbankprogrammiersprachen} (z.B., Pascal/R, Plain, Rigel, Modula/R,
Modulex, DBPL) mit Pascal-"ahnlichen Sprachen als algorithmischen
Kern, der um Relationstypen und mengenorientierte Operationen auf
typisierten Relationenvariablen erweitert ist. Dar"uber hinaus
existieren Mechanismen zur Deklaration von persistenten Daten und zur
Definition von Transaktionen. Das folgende Beispiel in der
Datenbankprogrammiersprache DBPL illustriert die Vorteile eines solchen
Ansatzes:
\begin{xple} 
\k{from} EmpDB \k{import} EmployeeRel;\smallskip 
\k{transaction} HireYoung(\k{var} E: EmployeeRelType); 
\k{begin}
    \k{if} \k{all} e \k{in} E (e.age $<$25) \k{then} 
        EmployeeRel:+ E
    \k{else} 
        PrintEmployees(\{\k{each} e \k{in} E: e.age$>=$25\});
    \k{end}
\k{end} HireYoung;
\end{xple}
F"ur Programmierer sind die zugrundeliegenden Sprachkonzepte wie
Typisierung, Modularisierung und Parametrisierung bereits bekannt, und
die (meist kalk"ulorientierten) Anfragesprachen sind leicht zu
erlernen. Gleichzeitig gestatten die relational vollst"andigen
mengenorientierten Anfragesprachen, die eng mit den "ubrigen
Ausdr"ucken der Sprache verwoben sind, eine effiziente, dynamisch
optimierende Implementation.

Durch konsequente Anwendung des aus Programmiersprachen bekannten
Orthogonalit"atsprinzips bieten moderne Vertreter dieser Sprachfamilie
\e{integrierte} Modellierungs- und Manipulationsmechanismen, wie sie
beispielsweise in den historisch unabh"angig voneinander entstandenen
Datenmodellen f"ur komplexstrukturierte Objekte und deduktive
Datenbanken getrennt vorliegen. So werden etwa Strukturen wie
die des NF$^2$-Modells durch das Prinzip der freien Schachtelung von
Record-, Varianten-, Array- und Relationenkonstruktoren definierbar.
Durch Lambda-Abstraktion und Parametrisierung von Anfrageausdr"ucken
erreicht man die Ausdrucksm"achtigkeit von Anfragesprachen mit
stratifizierter Fixpunktsemantik.  Entkoppelt man schlie"slich noch die
Lebensdauer eines Datenobjektes von seinem Typ, so k"onnen auch
nicht-relationale Strukturen (z.B. eine boolesche Variable oder
eine Matrix) persistent gehalten werden.

Die Klasse der ebenfalls stark typorientierten \e{persistenten
Programmiersprachen} (PS algol, Napier88, Amber, P-Quest) konzentrierte
sich zuerst auf den Aspekt der Langlebigkeit beliebigstrukturierter
Datenobjekte.  Ausgehend von dem Modell eines
\e{persistent heap} k"onnen in diesen Sprachen alle semantisch
relevanten Objekte (Records, Funktionen, abstrakte Datentypen, Module,
Zeiger, \ldots) dynamisch in einem globalen, programm"ubergreifenden
Adressraum alloziert und manipuliert werden.  Alle Objekte, die
transitiv von einem ausgezeichneten Wurzelobjekt (\e{persistent root})
durch statische Sichtbarkeitsreglen oder dynamische Bindungen erreichbar
sind, werden langlebig gespeichert und stehen anderen Programmen (durch
Naviation ausgehend von dem Wurzelobjekt) zur Verf"ugung. Das Konzept
der orthogonalen Persistenz erfordert einen generalisierten
Bindungsbegriff, der es Anwendungsprogrammen gestattet, dynamisch
Bindungen an bereits existierende Datenstrukturen auf der persistenten
Halde zu erzeugen und bestehende Bindungen wieder zu l"osen. Eine gro"se
konzeptuelle und technologische Herausforderung stellt in diesem
Zusammenhang die Balance zwischen statischer Typsicherheit und
dynamischer Bindungsflexibilit"at dar, ein Problem, das sich ebenfalls
in modernen Systemprogrammiersprachen (Modula-3) und Sprachen f"ur
verteilte Anwendungen (Hermes) stellt.

Da auch Module und Anwendungsprogramme Bestandteil der persistenten
Halde sein k"onnen, ist es m"oglich, Aufgaben von spezialisierten
Werkzeuge, wie Schema- oder Formular-Editoren, Linker, Bibliotheks- oder
Versionsmanager (\e{make}) durch die Mechanismen der
Datenbankprogrammiersprache zu l"osen.

Noch weitgehend unerforscht ist die M"achtigkeit der \e{reflektiven}
Aspekte dieser Sprachfamilie. In der einfachsten Form bieten diese
Systeme die M"oglichkeit eines \e{callable compiler}, der Quelltexte
(z.B.~ad hoc Anfragen) in Funktionen "ubersetzt, die dynamisch zu dem in
Ausf"uhrung befindlichen Programm gebunden werden. Dieser Mechanismus
(\e{run time reflection}) wird z.B. erfolgreich zur "Ubersetzung von
Kalk"ulanfragen in geschachtelte Schleifen eingesetzt und prototypisch
f"ur die typstrukturgesteuerte Generierung von Applikationsprogrammen
benutzt. Eine andere Form der Reflektion (\e{compile time reflection})
erlaubt die Erweiterung der Syntaxanalysephase durch benutzerdefinierten
Code, der z.B. generische Spracherweiterungen durch Abbildung in
geschachtelte Ausdr"ucke einer reduzierten Kernsprache implementiert.

Eine wesentliche Einschr"ankung persistenter Programmiersprachen f"ur
konventionelle Datenbankanwendungen ist jedoch bisher das Fehlen einfach
zu handhabender generischer Datenstrukturen f"ur Massendaten und
sprachlicher Mechanismen zur Iterationsabstraktion.


\subsection*{Logikbasierte und funktionale Datenbanksprachen}

Die Strukturen und Iterationsabstraktionen des relationalen Datenmodells
(Mengen und Pr"adikate) bilden den Ausgangspunkt logikbasierter und
funktionaler Datenbanksprachen.  Sprachen deduktiver Datenbanken
(Wissensbanken, Expertensysteme) unifizieren extensionale und
intensionale Datenbankaspekte (Fakten und Regeln) und streben im
Gegensatz zu den imperativen typorientierten Sprachen eine rein
deklarative Sprachsemantik an. In logikbasierten Sprachen kann sich der
Anwender auf die Spezifikation der Eigenschaften der zu manipulierenden
Strukturen beschr"anken und dem System die Auswahl einer optimierten
Evaluationsreihenfolge "uberlassen.

Ausgehend von einfachen Horn-Klauseln wurden die Datenbanksprachen der
\e{Datalog}-Familie schrittweise um Basispr"adikate (Gleichheit,
Ordnungsrelationen), Negation, Aggregatfunktionen und Funktionssymbole
zur Repr"asentation komplexer Objekte erweitert. Neben NAIL!, POSTGRES,
ALGRES, PRISMA, educe und Megalog ist insbesondere die Sprache LDL zu
erw"ahnen, die auch Operatoren f"ur ``deklarative''
"Anderungsoperationen auf Datenbanken umfa"st.

Die genannten Systeme bieten ebenfalls Persistenzabstraktion, indem alle
erzeugten Fakten und Regeln persistent gespeichert werden. Der Preis
f"ur die potentiell exzellente Optimierbarkeit dieser Sprachen ist
allerdings der Verlust der algorithmischen Vollst"andigkeit. Praktisch
alle Sprachen bieten daher Schnittstellen zu imperativen Wirtsprachen
f"ur anspruchsvollere Datenmanipulationen (statistische Analysen,
Datenein- und ausgabe) an, so da"s der \e{impedance} und
\e{competence mismatch} eventuell auf einer h"oheren Ebene wieder auftritt.

Die Notation der \e{list comprehensions} in Programmiersprachen wie
Miranda oder Haskell hat wegen ihrer N"ahe zum relationalen Kalk"ul das
Interesse an der Verwendung funktionaler Sprachen f"ur Datenbankanfragen
wiederbelebt. Ein \e{join} in der Syntax einer \e{set comprehension}
\begin{xple}
$[(name\,e, salary\, e, name\,o)\, | \,e \leftarrow employees;$
     $s \leftarrow orders;\, supplier\, o = name\, e]$
\end{xple}
ist wesentlich leichter lesbar als seine Formulierung mittels Funktoren
in traditionellen funktionalen Datenbanksprachen wie FQL. Andererseits
gibt es triviale "Ubersetzungsalgorithmen von \e{comprehensions} in
Ausdr"ucke des reinen Lambda-Kalk"uls, auf denen Transformationen analog
zu den bekannten algebraische Optimierungen des Relationalen Kalk"uls
durchf"uhrbar sind. Zwar erlaubt die referentielle Transparenz rein
funktionaler Sprachen "ahnlich agressive Optimierungen wie in
logikbasierten Formalismen, jedoch gibt es substantielle Unterschiede in
der Semantik rekursiver Deklarationen.  Die Abbildung relationaler
Strukturen und Iterationsabstraktionen in den Lambda-Kalk"ul gestattet
auch die Untersuchung verallgemeinerter Datenstrukturen (\e{quads}) f"ur
Massendaten (Listen, Bags, Multimengen, B"aume), die alle mit
\e{comprehensions} als einer uniformen Anfragenotation ausgestattet
sind.  Der skizzierte Transformationsansatz wird ebenfalls f"ur die
prototypische Implementation funktionaler Datenbanksprachen eingesetzt,
die zudem voll in das Typsystem und das Ausf"uhrungsparadigma moderner
Programmiersprache (\`a la ML) integriert sind.

In der Sprache Machiavelli werden ebenfalls SQL-"ahnliche Ausdr"ucke als
``syntaktischer Zucker'' in Applikationen einer einzelnen vordefinierter
Funktionen h"oherer Ordnung (\e{hom}, homomorphe Extension)
transformiert. Machiavelli l"ost dar"uber hinaus das Problem der
Typisierung des \e{natural join} Operators ($Students \Join Employees$),
indem die Sprache polymorphe Typregeln f"ur konsistenzerhaltende
Joinoperationen auf Records ($Student \Join Employee$) definiert, die
gleichzeitig die Typisierung von allgemeinenen Vererbungsbeziehungen
erlaubt, wie sie in objekt-orientierten Sprachen auftreten.

Ein weiterer wichtiger Beitrag funktionaler Datenbanksprachen liegt im
Einsatz von \e{Typinferenzmechanismen}, die nicht nur dem Programmierer
die Angabe expliziter Typinformationen z.B.~bei der Formulierung von
Anfragen oder bei Sichtendefinitionen ersparen, sondern auch Anfragen
und Transaktion den ``m\"oglichst generischen'' Typ (\e{principal type
scheme}) zuordnen. Damit kann z.B.~die Anwendung der folgenden Anfrage auf alle
Relationen {\sl E} zugelassen werden, sofern sie nur ein numerisches
{\sl status} Attribut besitzen.
\begin{xple}
\k{select} * \k{from} E \k{where} status $>$ 30
\end{xple}

Abschlie"send seien noch die Sprachen Life und COL erw"ahnt, die
Konzepte der funktionalen Programmierung und Vererbungsbeziehungen durch
polymorph typisierte Termkonstruktoren ($\Psi$-Terme in Life) in einen
logikbasierten Rahmen integrieren.


\subsection*{Objekt-orientierte Systeme}

Im Gegensatz zu de eher durch konzeptuelle und formale Vorteile
motivierten funktionalen Datenbanksprachen wird der Entwurf
objekt-orientierter Systeme sehr stark durch technologische
"Uberlegungen geleitet, da viele der Sprachen im Zuge der Implementation
prototypischer oder kommerzieller Datenbanksysteme entstanden sind
(Adaplex f"ur MULTIBASE, OPAL f"ur GemStone, CO$_2$ f"ur O$_2$, O++ f"ur
ODE). Obwohl sich z.B.~Adaplex an einem funktionalen Datenmodell
orientiert, bietet es bereits Objektidentit"at, Klassifikation und
Mehrfachererbung sowie die f"ur objekt-orientiere Anfragesprachen
typische Iterationsabstraktion durch eine Mischung aus quantifizierten
Mengenausdr"ucken und navigierendem Datenzugriff "uber Objektreferenzen
(Punktnotation):
\begin{xple} 
\k{select} e.name, e.salary, o.name 
\k{from} e \k{in} Employees, o \k{in} e.orders 
\end{xple}
Objekt-orientierte Systeme bieten dar"uber hinaus Mechanismen zur
Definition sogenannter komplexer Objekte und Methoden sowie Mechanismen
zur sp"aten Bindung und Methodenredefinition in Subklassen.  Neben
harten technischen Problemen der Anfrageoptimierung (z.B. dynamisch
gebundene Methodenaufrufe), der Objektadressierung und
Speichererverwaltung (\e{clustering}, \e{garbage collection}) stellen
sich in diesen Systemen auch neuartige sprachliche Probleme. Biepsiele
sind etwa die Semantik dynamischer Restrukturierungen der
Klassenhierarchie oder die Frage nach Sichtbarkeitsregeln zwischen
Super- und Subklassen, die eine effektive gemeinsame Nutzung von
Methoden, Attributen und Integrit"atsbedingungen gestatten, ohne dabei
ungewollte Namenskonflikte in Mehrbenutzersystemen zuzulassen.

Eine besondere St"arke objekt-orientierter Systeme ist die enge
konzeptuelle und technologische Verflechtung zwischen grafischen
Benutzerschnittstellen, modularer und erweiterbarer Datenabstraktion
sowie effizienten Objektspeichern, wie sie z.B.\ durch die
Datenbankbrowser und Debugger von O$_2$ und GemStone demonstriert wird
(\e{objects on screen, in memory and on disk}).


\subsection*{Neuere Typsysteme f"ur Datenbankapplikationssysteme}

Zusammenfassend l"a"st sich heute eine erfreuliche Konvergenz der oben
skizzierten drei Entwicklungslinien feststellen. Alle neueren Systeme und
Sprachen betonen die \e{orthogonale} Kombinierbarkeit \e{elementarer}
Basiskonzepte f"ur Persistenzabstraktion, typvollst"andige
Datenstrukturierung und Iterationsabstraktion.

Gegenstand aktueller Forschungsarbeiten (z.B. in den Esprit Projekten
DAIDA, FIDE und dem DFG Programm \e{Objektbanken f"ur Experten}) ist die
formale Integration von Methoden, Sprachen und Systemen zur Entwicklung
integrierter, effizienter Datenbankapplikationssysteme. Hohe Priorit"at
besitzt dabei das Aufbrechen monolithischer Systemstrukturen in
wohldefinierte funktionale Teilkomponenten wie z.B.

\begin{itemize}
\item Modellunabh"angige Ob\-jekt\-spei\-cher\-systeme, die \linebreak
hocheffizienten Zugriff auf einfach strukturierte Daten in logisch oder
physisch partitionierten Bereichen (\e{repositories}) gestatten;

\item Bibliotheken generischer, frei kombinierbarer (evtl.
modellspezifischer) Datenstrukturen, wie \e{bang files} f"ur
logikbasierte Modelle, B"aume und Hashtabellen f"ur relationale Modelle,
Pfad-Indices f"ur objekt-orientierte Modelle;

\item Sammlungen parametrisierter Datenkonstruktoren zur
implementationsunabh"angigen Beschreibung von Massendaten (\e{bulk data
types}) und der auf ihnen definierten mengenorientierten Operationen;

\item Kanonische Zwischensprachen zur architekturunabh"angigen
Repr"asentation, Analyse, Transformation und "Ubersetzung von
Programmfragmenten (Anfragen) oder vollst"andigen Programmen.

\end{itemize} 

So wird z.B.~im FIDE Projekt \cite{MaSc91} speziell der Einsatz moderner
Typkonzepte (parametrischer und Subtyp-Polymorphismus, Metatypisierung,
\e{dependent types}) und Methoden algebraischer Spezifikationen zur
Definition und kontrollierten Implementation dieser generischen
Datenbankdienste in einem integrierten sprachlichen Rahmen untersucht.

\bibliographystyle{florian-named}
\bibliography{../bib/florian}

\end{document}
