\section{Grundlagen der Datenbankmodellierung}
\label{Grundlagen der Datenbankmodellierung}

Dieser Abschnitt f"uhrt grundlegende Konzepte ein, die unabh"angig vom
jeweiligen Datenmodell f"ur die erfolgreiche Realisierung von
Informationssystemen relevant sind.  Dazu werden in Abschnitt
\ref{Abstraktionsmechanismen zur Datenstrukturierung} zun"achst
strukturbezogene Abstraktionskonzepte eingef"uhrt und daran
anschlie"send in Abschnitt \ref{Persistenzabstraktion} und
\ref{Datenunabhaengigkeit durch Schemaarchitekturen}
operationsbezogene Konzepte.  Basierend auf den Abstraktionsniveaus
wird in Abschnitt \ref{Grobklassifikation von Datenmodellen} eine
Grobklassifikation der Datenmodelle vorgenommen.  Sie wird erg"anzt
durch die Schilderung der Benutzergruppen eines Datenbanksystems und
den damit verbundenen Modalit"aten in Abschnitt \ref{Benutzergruppen
  und Modalitaeten}.  Ein historischer Abri"s wichtiger Ereignisse in
der Forschung der Datenbanktechnik beschlie"st dieses Kapitel.

\subsection{Abstraktionsmechanismen zur Datenstrukturierung}
\label{Abstraktionsmechanismen zur Datenstrukturierung}

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/7.eps}
\caption{Abbildung eines Realit"atsausschnitt auf ein Informationssystem}
\label{realitaet}  
\end{center}
\end{figure}

Unabh"angig von der Vielf"altigkeit der existierenden Datenmodelle gibt es
grundlegende Konzepte und Abstraktionsmechanismen, die in der einen oder
anderen Form in fast allen Datenmodellen eine zentrale Rolle spielen. Diese
werden in diesem Abschnitt als grundlegendes Vokabular f"ur die Vorstellung
der klassischen Datenbankmodelle im n"achsten Kapitel eingef"uhrt.
Gleichzeitig werden die Objektdiagramme nach OMT als eine m"ogliche graphische
Notation f"ur die Datenmodellierung vorgestellt, die bereits im letzten
Abschnitt zur Illustration des Beispiels eingesetzt werden.

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/8.eps}
\caption{Modelle und Abstraktion}
\label{modelle und abstraktion}  
\end{center}
\end{figure}

\comment{Hier nur einfache, minimale Grundlagen. Ziel: \\ 
Vokabular und grafische \\ 
Notation Objektdiagramme nach OMT / Rumbaugh f"ur Vorstellung \\ 
der klassichen Datenbankmodelle im n"achsten Kapitel [Brodie, ...]}

In Datenbankmodellen lassen sich zwei grundlegende 
Konzepte zur Informationsrepr"asentation unterscheiden:

\begin{description}
\item[Werte (Literale)] besitzen eine Semantik unabh"angig vom Zustand der
  Datenbank. Man unterscheidet dabei atomare \e{Basiswerte,} wie zum Beispiel
  Zahlen, Zeichen oder Zeichenketten und strukturierte, \e{zusammengesetzte
    Werte}. Zusammengesetzte Werte lassen sich in \e{heterogene Strukturen}
  bestehend aus einer festen Anzahl benannter Attribute, wie z.B. Name, Alter
  und Telenfonnummer, (Tupel, Rekords, Strukturen) und \e{homogene Strukturen}
  (Kollektionen) bestehend aus einer flexiblen Anzahl anonymer Elemente
  (Arrays, Listen, Mengen, Multimengen) unterscheiden. Operationen auf Werten
  (Addition, Rekordfeldzugriff, Listenkonkatenation) besitzen
  \e{Kopiersemantik}. Als Faustregel gilt, da"s sich Werte verlustfrei durch
  lineare textuelle Repr"asentationen darstellen lassen.

\item[Objekte] besitzen eine Semantik, die vom Zustand der Datenbank abh"angig
  ist. Der Objektbegriff in Datenbanken ist eng mit dem Begriff der
  \e{Zustandsvariablen} imperativer Programmiersprachen verwandt.  Wie bei
  Variablen in imperativen Sprachen kann der Zustand eines Objektes durch
  destruktive \e{Zuweisungen} (auf Teilkomponenten oder das gesamte Objekt)
  "uber die Lebensdauer einer Datenbank hinweg ver"andert werden.  Unabh"angig
  von seinem Zustand beh"alt ein Objekt jedoch seine \e{Objektidentit"at
    (object identity, OID)} Die Objektidentit"at eines Objektes kann als Wert
  in mehreren Datenstrukturen verwendet werden, um das Objekt "uber
  verschiedene Pfade zu \e{referenzieren}. Zum Beispiel kann die
  Objektidentit"at eines Objekts zur Beschreibung eines Kindes als Wert des
  Attributes Kind seiner beiden Eltern und als anonymes Element in einer Menge
  Sch"uler auftreten (\e{sharing}). "Anderungen des Objektzustands, z.B. des
  Alters des Kindes, werden unmittelbar auf allen Pfade sichtbar, in denen das
  Objekt referenziert wird (Seiteneffeke, \e{aliasing}). Objekte besitzen also
  eine Referenzsemantik und eine textuelle Repr"asentation von
  Objektstrukturen erfordert die Einf"uhrung von speziellen Notationen, um die
  (evtl. zyklische) Graphstruktur von Objektreferenzen linear zu
  repr"asentieren.
\end{description}

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/13.eps}
\caption{Referentielle Identifikation}
\label{Referentielle Identifikation}  
\end{center}
\end{figure}

Datenstrukturen bestehend aus Werten und Objekten werden zur Repr"asentation
von Informationsstrukturen verwendet, die ihrerseits durch die wiederholte
Anwendung von \e{Abstraktionsmechanismen} sogenannter \e{semantischer
  Datenmodelle} beschrieben werden k"onnen (s. Kapitel xx).

\comment{Formulieren:}
Als graphische Notation zur Darstellung von... werden in diesem Kapitel 
E/R-Diagramme verwendet, 
Zusammen mit der Einf"uhrung der einzelnen Konzepte wird auch deren 
grafische Dartsaellung in OMT-Notation beschrieben. 

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/14.eps}
\caption{Grundlegende Elemente von E/R-Diagrammen}
\label{Legende ER}
\end{center}
\end{figure}

  
\subsubsection{Klassifikation und Instanziierung}
\label{Klassifikation und Instanziierung}

Bei der \e{Klassifikation} werden Objekte mit "ahnlichen Eigenschaften zu
einer \e{Klasse} zusammengefa"st. Jedes Objekt wird als \e{Instanz} seiner
Klasse bezeichnet. Instanzen einer Klasse verf"ugen "uber die gleiche
Struktur, ????

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/15.eps}
\caption{Klassifikation und Instantiierung}
\label{Klassifikation und Instantiierung}
\end{center}
\end{figure}

Ein weiterer Aspekt einer Klasse ist die Verwaltung ihres \e{dynamischen
  Extension}, die alle Objekte der Klasse umfa"st.  (Literale, Dom"anen,
strukturelle Klassifikation \& Typen, Klasse, Instanz, statische Typisierung
vs. dynamische Extensionsverwaltung, Iteration)

In der E/R-Notation werden Klassen durch Rechtecke dargestellt, Instanzen
durch Rechtecke mit abgerundeten Ecken.

\subsubsection{Aggregation und Dekomposition}
\label{Aggregation und Dekomposition}

Eine Instanz besitzt in der Regel mehrere Eigenschaften. Solche Eigenschaften
werden duch Attribute beschrieben, die aus einem \e{Attributwert} und einem
\e{Attributnamen} bestehen. Diese Attribute einer Instanz werden zu einem
\e{Tupel} oder \e{Record} zusammengefa"st (\e{aggregiert}). Auf der Ebene der
Klassen besteht diese Aggregation aus der Zusammenfassung von Paaren aus
Attributnamen und zugeh"origen Typ des Attributs (Dom"ane).

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/16.eps}
\caption{Attribute des Objekttyps \e{Projekt}}
%\label{}  
\end{center}
\end{figure}

Durch \e{Dekomposition} kann "uber die Attributnamen auf die einzelnen
Attributwerte einer Instanz zugegriffen werden. Sie ist vergleichbar der
Selektion von Record-Komponenten in einer Programmiersprache.

Aggregation kann sich aber auch auf die Zusammensetzung von Objekten zu einem
"ubergeordneten Objekt beziehen(vgl.\cite{Smith and Smith}), wobei eine
\e{part of}-Beziehung zwischen den Komponenten und dem aggregierten Objekt
besteht.  Das aggregierte Objekt stellt eine Beziehung zwischen Objekten dar,
hat aber den Vorteil, da"s man ihm Eigenschaften zuordnen kann und da"s es
auch selbst wieder an Beziehungen teilnehmen kann. Ein typisches Beispiel sind
St"ucklisten.

Die strukturellen Komponenten einer Klasse werden in der OMT-Notation durch
Auflistung der Attributnamen und der zugeh"origen Dom"anen dargestellt.  Die
Bildung von aggregierten Objekten wird durch spezielle Beziehungen
dargestellt.

(statische Aggregation, Attributname, Attributwert, Records, Tupel, Werte vs.
Typen)

\subsubsection{Generalisierung und Spezialisierung}
\label{Generalisierung und Spezialisierung}

Bei der \e{Spezialisierung} wird eine oder mehrere Klassen definiert, die die
urspr"ungliche Klasse verfeinern. Die speziellere Klasse wird als
\e{Subklasse}, die allgemeinere als \e{Superklasse} bezeichnet.  Die Klassen
bilden eine \e{Subklassenhierarchie}.Der umgekehrte Vorgang zur
Spezialisierung ist die \e{Generalisierung} bei der gemeinsame Strukturen und
Verhalten mehrer Klassen herausfaktorisiert und in einer Superklassen
gesammelt werden. Spezialisierung und Generalisierung betonen die
Gemeinsamkeiten von Klassen, ohne jedoch die Differenzen zu verwischen.

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/17.eps}
\caption{Generalisierung und Spezialisirung}
%\label{}  
\end{center}
\end{figure}

Jede Instanz einer Klasse ist auch Instanz all ihrer Superklassen. Eine
Spezialisierung kann disjunkt oder "uberlappend sein, wobei im ersten Fall
jedes Objekt einer Klasse nur in h"ochstens einer ihrer direkten Subklassen
enthalten sein darf.

Eine Subklasse \e{erbt} die Eigenschaften (Attribute und Methoden) ihrer
Superklasse und f"ugt evtl. neue hinzu. An allen Stellen, an denen ein Objekt
einer Klasse erwartet wird, wie z.B. bei Operationen kann auch eine beiebige
Instanz einer ihrer Subklassen verwendet werden.
 
\comment{Subtypisierung, Typhierarchie, Substituierbarkeit, 
Subsumption)}?????

\subsubsection{Assoziation und Identifikation} 
\label{Assoziation und Identifikation}

Objekte k"onnen miteinander in Beziehung gesetzt -\e{assoziiert}- werden
\comment{Beispiel}.  Zwischen zwei Klassen besteht eine Beziehung, wenn deren
Instanzen miteinander assoziiert sind.  \e{Bin"are} Beziehungen stellen eine
Verkn"upfung zwischen zwei Klassen bzw. Objekten dar, \e{tern"are} Beziehungen
entsprechend zwischen drei Klassen.  Es gibt auch Beziehungen mit noch mehr
beteiligten Klassen. Man spricht dann allgemein von n-"aren Beziehungen. \p{n}
wird dabei als \e{Grad} der Beziehung bezeichnet.  In der OMT-Notation werden
bin"are Beziehungen durch Linien dargestellt, und Beziehungen h"oheren Grades
durch Rauten.

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/18.eps}
\caption{Bin"are Beziehungen}
\label{Bin"are Beziehungen}
\end{center}
\end{figure}

Im allgemeinsten Fall kann jedes Objekt einer Klasse mit beliebig vielen
Objekten der zweiten Klasse in Beziehung stehen und umgekehrt. Man spricht
dann von einer n:m-Beziehung.  \e{Kardinalit"atsbeschr"ankungen} dienen dazu
genaue Werte oder zul"assige Intervalle f"ur die Zahl der Instanzen einer
Klasse, die mit einer Instanz der anderen Klasse in Beziehung stehen k"onnen,
festzulegen. Weiterhin kann zwischen \e{partiellen} und \e{totalen}
Beziehungen unterschieden werden. Bei einer totalen Beziehung mu"s jeder
Instanz der ersten Klasse mindestens eine Instanz der zweiten Klasse
zugeordnet sein, bei einer partiellen Beziehung ist die Zuordnung optional.

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/19.eps}
\caption{n:m-Beziehung zwischen Abteilungen und Projekten}
\label{n:m-Beziehung zwischen Abteilungen und Projekten}
\end{center}
\end{figure}

Wenn man die Assoziation zwischen zwei Klassen als Linie betrachtet, so bildet
jedes Ende eine \e{Rolle}, der ein eindeutiger \e{Rollenname} zugeordnet
werden kann.  Rollennamen schaffen die M"oglichkeit, sich die Menge der
Instanzen einer Klasse zu \e{identifizieren}, die mit einer Instanz der Klasse
am entgegengestzten Ende der Linie assoziiert ist, ohne explizit auf die
Beziehung zuzugreifen. Aus der Sicht des Objekts bildet eine Rolle ein
abgeleitetes Attribut mit dem Rollennamen als Attributnamen.  Der Wert des
Attributs ist die Menge der Objekte, die durch die betrachtete Beziehung mit
dem Objekt assoziiert sind.  

\comment{Beispiel mit Bild}

\subsubsection{Identifikation und Schl"ussel}
\label{Identifikation und Schluessel}

Rolle der Identifikation

Die Identifikation einzelner Objekte in den umfangreichen Extensionen einer
Datenbank spielt eine zentrale Rolle. Grunds"atzlich kann man zwischen zwei
Arten von Identifikation unterscheiden. Bei der \e{referntiellen
  Identifikation} gibt es zur Identifikation direkte Verweise auf die
einzelnen Objekte, die mit Zeigern in der Programmiersprachenwelt vergleichbar
sind. Die \e{assoziative Identifikation} verwendet Werte der Attribute oder
von Attributkombination, um sich eindeutig auf ein Objekt zu beziehen.

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/22.eps}
\caption{Referentielle Identifikation vs. Assoziative Identifikation}
\label{Referentielle Identifikation vs. Assoziative Identifikation}
\end{center}
\end{figure}

Ein Schl"ussel ist ein Attribut oder eine Attributkombinationen mit der
Eigenschaft, da"s keine zwei Instanzen die gleiche Wertkombination in diesen
Attributen besitzt.  Schl"ussel k"onnen deshalb zur eindeutigen Identifikation
von Instanzen eingestzt werden.  Es kann mehrere verschiedene
Schl"usselkandidaten geben, von denen einer als \e{Prim"arschl"ussel} zur
Identifikation der Instanzen ausgew"ahlt wird.

Bei der \e{referentielllen Integrit"at} geht es grunds"atzlich darum, da"s ein
referenziertes Objekt auch tats"achlch existiert. Zur Darstellung einer
Beziehung zu einem Objekt, kann ein Schl"ussel als Attributwert verwendet
werden (Relationales Modell).  Man spricht dann von einem \e{Fremdschl"ussel}.
verwendet werden. Dabei ist sicherzustellen, da"s das durch den
Fremdschl"ussel identifizierte Objekt auch tats"achlich existiert
(\e{referentielle Integrit"at}).

\comment{ Erkl"are: Orthogonalit"at und Typvollst"andigkeit}


\subsection{Persistenzabstraktion}
\label{Persistenzabstraktion}

Moderne Datenbanksprachen bieten direkte Mechanismen zur Benennung und
Manipulation langlebiger Daten und erfordern keine expliziten Lade- und
Speicherungsoperationen beim Zugriff auf benannte Datenbankvariablen. Sie
erlauben dem Datenbankprogrammierer damit eine \e{Persistenzabstraktion}.
Somit werden die komplexen Details des Datentransfers zwischen Sekund"ar- und
Prim"arspeicher aus den Algorithmen des Informationssystems eliminiert, und es
wird dem Datenbanksystem ein erheblicher Optimierungsspielraum bei der
Organisation von Speicherzugriffen gegeben.

In Sprachen, in denen sowohl langlebige als auch kurzlebige Daten bearbeitet
werden k"onnen, l"a"st sich die Qualit"at der Persistenzabstraktion genauer
charakterisieren: Ist jede Datenstruktur, die f"ur transiente Daten zur
Verf"ugung steht, auch f"ur persistente Daten verf"ugbar (Beispiele: Rekords,
Vektoren, Rekords mit Varianten, Listen, Zeiger) und umgekehrt jede
Datenstruktur f"ur persistente Daten auch f"ur transiente Daten verf"ugbar
(Beispiele: sequentielle Datei, relationale Tabelle), so handelt es sich um
eine Sprache mit \e{orthogonaler Persistenz}. In solchen Sprachen ist der
Anwendungsprogrammierer von der Aufgabe befreit, Datenstrukturkonvertierungen
beim "Ubergang zwischen persistenter und transienter Speicherung
durchzuf"uhren.

Eine Sprache bietet dar"uber hinaus \e{Persistenzunabh"angigkeit}, wenn es
m"oglich ist, Algorithmen z.b.| in Form von Prozeduren, Funktionen und
Anfragen zu formulieren, die uniform auf transiente und persistente Daten als
Argumente angewendet werden k"onnen.

In Datenbanksprachen lassen sich drei Ans"atze zur \e{Definition der
  Datenlebensdauer} unterscheiden.

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/23.eps}
\caption{Alternativen zur Definition der Datenlebensdauer}
\label{Alternativen zur Definition der Datenlebensdauer}
\end{center}
\end{figure}

\begin{description}
\item[Persistente Typen:] Die Lebensdauer eines Datums wird explizit zusammen
  mit seiner Struktur definiert. So unterscheiden viele Sprachen zwischen
  persistenten Datenbanktabellen und transienten Ergebnistabellen. Dieses
  Modell ist inkompatibel mit dem Konzept der Persistenzunabh"angigkeit.

\item[Persistente Sichtbarkeitsbereiche:] Die Lebensdauer eines Datums wird
  implizit aus dem statischen Kontext abgeleitet, in dem das Datum deklariert
  wird. Eine Variable, die lokal in einer Anfrage definiert wird, ist in
  diesem Modell ein transientes Datum, w"ahrend eine global in einem
  Datenbankschema definierte Variable als persistent betrachtet wird.

\item[Transitive Erreichbarkeit:] Dieses Modell ist eine Verfeinerung des
  Modells der persistenten Sichtbarkeitsbereiche. In diesem Modell gibt es
  ebenfalls statische persistente Sichtbarkeitsbereiche, die auch als Wurzeln
  der Persistenz (\e{roots of persistence}) bezeichnet werden. Dabei handelt
  es sich zum Beispiel um die Datenbankschemata eines Datenbanksystems.
  Zus"atzlich werden bei der Lebensdauerdefinition auch (dynamische)
  Abh"angigkeiten zwischen Daten ber"ucksichtigt. Solche Abh"angigkeiten
  entstehen, wenn die Semantik eines Datums \e{A} von der Semantik eines
  Datums \e{B} abh"angt. Beispiele f"ur solche Abh"angigkeiten sind:

\begin{itemize}
\item \e{A} besitzt \e{B} als Rekordfeld oder Mengenelement. 
\item \e{A} ist ein Zeiger auf \e{B}.
\item \e{A} ist ein Fremdschl"ussel f"ur \e{B}. 
\item \e{A} ist eine Subklasse von \e{B}. 
\item \e{A} ist eine Funktion oder Anfrage, die \e{B} benutzt.
\end{itemize}

Zur Sicherstellung der referentiellen Integrit"at (s. Abschnitt
\ref{Referentielle Integritaet}) dieser Abh"angigkeiten impliziert in
diesem Modell die Persistenz des Datums \e{A} automatisch die Persistenz des
Datums \e{B}. Insgesamt sind also genau die Daten persistent, die transitiv
von den Wurzeln der Persistenz aus erreichbar sind.

Ein erheblicher Vorteil des Modells der transitiven Erreichbarkeit ist die
M"oglichkeit, eine komplexe, transient erzeugte Datenstruktur durch eine
einzelne Zuweisung dynamisch von einer persistenten Datenstruktur aus
erreichbar zu machen. Au"serdem werden subtile Speicherlecks (\e{memory
  leaks}) vermieden, die aufgrund fehlender Speicherfreigabeanweisungen f"ur
nicht mehr erreichbare persistente Daten in Informationssystemen entstehen.
\end{description}

Das Persistenzkonzept der transitiven Erreichbarkeit kann als 
Generalisierung des Konzepts der automatischen Freispeicherverwaltung 
(\e{garbage collection}) angesehen werden, die in zunehmendem 
Ma"se in Programmiersprachen eingesetzt wird. Ein Programm bildet 
dabei einen transienten Sichtbarkeitsbereich, und seine lokalen 
Variablen bilden Wurzeln der Erreichbarkeit. Insgesamt lassen 
sich w"ahrend der Programmlaufzeit drei Klassen von Daten unterscheiden: 
Persistente Daten sind von den Wurzeln der Persistenz erreichbar, 
transiente Daten sind von lokalen Variablen aus erreichbar, tote 
Daten sind unerreichbar, und der von ihnen belegte Speicherplatz 
wird automatisch durch das System freigegeben. 

\subsection{Datenunabh"angigkeit durch Schemaarchitekturen}
\label{Datenunabhaengigkeit durch Schemaarchitekturen}

Der bereits in Abschnitt \ref{Unterstuetzung der Persistenz} kurz
angesprochene Begriff der Datenunabh"angigkeit l"a"st sich besonders gut
anhand der sog.\ Drei-Schichten-Architektur erl"autern. Diese Architektur
wurde vom ANSI/SPARC-Kommittee unter anderm mit dem expliziten Ziel der
Unabh"angigkeit der Daten von Anwendungen und der Unterst"utzung mehrerer
Benutzersichten entworfen.

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/24.eps}
\caption{Drei-Schichten-Architektur}
\label{Drei-Schichten-Architektur}
\end{center}
\end{figure}

Wie der Name bereits andeutet, k"onnen bei dieser Architektur in drei
Schichten verschiedene Schemata definiert werden.  Alle Schemata sind im
DB-Katalog abgelegt.
 
\begin{enumerate}
\item Die \e{interne Schicht} besitzt ein \e{internes Schema}, das die
  physikalischen Speicherstrukturen der Datenbank beschreibt, wozu die
  Einzelheiten der Datenspeicherung und der Zugriffspfadunterst"utzung
  geh"oren.

\item In der \e{konzeptuellen Schicht} legt das \e{konzeptuelle Schema} die
  Strukturen der konzeptuellen Sicht der gesamten Datenbank f"ur eine ganze
  Benutzergemeinde fest. Dabei liegt die Betonung auf den Entit"aten,
  Datetypen, Beziehungen und Integrit"atsbedingungen, w"ahrend die
  physikalischen Speicherstrukturen verborgen werden.

\item Aufgabe der f"ur informationsverarbeitende Aktivit"aten sichtbare
  \e{externen Schicht} ist die Unterst"utzung von Benutzersichten. Jedes
  \e{externe Schema}, auch Benutzersicht genannt, beschreibt die Sicht eines
  Benutzers oder einer Benutzergruppe auf die Daten.  Es sind nur die f"ur
  diesen Benutzer relevanten Daten sichtbar, der "ubrige Teil wird
  ausgeblendet.
\end{enumerate}
 
Es lassen sich zwei Arten von Datenunabh"angigkeit unterscheiden, die mit
Bezug auf die unterschiedlichen Schemata der Drei-Shema-Architektur erl"autert
werden.

\begin{description}
\item[Logischer Datenunabh"angigkeit:] Das konzeptuelle Schema kann weitgehend
  ohne Konsequenzen f"ur das externe Schema ge"andert werden.  So soll z.B.
  nicht nur das Einf"ugen neuer Datens"atze, sondern auch strukturelle
  Erweiterungen des konzeptuellen Schemas ohne Einflu"s auf das externe Schema
  sein.  Beim L"oschen von Datens"atzen und auch von Strukturen sollen
  zumindest die externen Schemata, die sich nur auf den verbleibenden Teil der
  Datenbank beziehen, unbeeinflu"st bleiben

\item[Physischer Datenunabh"angigkeit:] Das interne Schema kann unabh"angig
  von dem konzeptuellen Schema modifiziert werden. M"ogliche Modifikationen
  des internen Schemas sind z.B.\ die Reorganisation der Daten und die
  Einrichtung neuer Zugriffspfade. Solange die Datenbank weiterhin dieselben
  Nutzdaten enth"alt, sollten solche Ver"anderungen keine Auswirkungen auf das
  konzeptuelle Schema besitzen.
\end{description}

Wie bereits an der Drei-Schema-Architektur gesehen, erreicht man
Datenunabh"angigkeit bei Datenbankmodellen unter anderem durch
\e{Schemaschichtung}. Anfragen und Operationen der informationsverarbeitenden
Aktivit"aten werden gegen das externe Schema gestellt, w"ahrend die Daten
selbst in der internen Schicht angesiedelt sind. Der notwendige
Abbildungsproze"s zwischen den Schichten ist Aufgabe des Datenbanksystems. Er
birgt zwar Optionen f"ur die Optimierung ist aber auch mit einem erheblichen
Aufwand behaftet und wird daher in manchen Systemen umgangen.

%\comment{Verwischt sich in modernen Modellen, da dort idealerweise wiederholte 
%benutzerdefinierte Abstraktionen. Persistente Objektsysteme (Abbildung?)}

%\comment{Navathe 2.2 \& 2.2.2 ``Drei Schema-Architektur''
%Cattell 3.2.1 und 3.2.2}

\subsection{Grobklassifikation von Datenmodellen}
\label{Grobklassifikation von Datenmodellen}

%s. Navathe 2.5 (2.1.1) K,S S6+7,S18: Unterscheidung: 
Es gibt viele verschiedene Datenmodelle.  Sie lassen sich z.B.\
klassifizieren nach dem Abstraktionsniveau der Konzepten die sie zur
Datenbeschreibung anbieten:

\begin{description}
\item[] \e{Konzeptuelle} Datenmodelle (\e{high-Level}, \e{semantische}
  Datenmodelle, Informationsmodelle) orientieren sich an einer dem Benutzers
  vertrauten Sicht der Informationsmodellierung. Die verwendeten Konzepte sind
  Objekte, Entit"aten, Attribute, Beziehungen usw.

\item[] \e{Implementationsmodelle} sehen Konzepte vor, die vom
  Endbenutzer verstanden werden k"onnen, aber trotzdem nicht zu weit
  weg von der Datenrepr"asentation im Rechner sind. Auf diese Weise
  ist sichergestellt, da"s die Konzepte in direkter Weise realisiert
  werden k"onnen.  Zu diesen Modellen z"ahlen die in Kapitel \ref{Die
    etablierten Datenbankmodelle im Ueberblick} vorgestellten
  relationales Datenmodell, Netzwerkdatenmodell und hierarchisches
  Datenmodell.  Da sie Informationen auch in Rekords speichern werden
  sie auch als \e{rekord-basierte} Datenmodell bezeichnet.

\item[] \e{low-level} (physische) Datenmodelle bieten Konzepte auf einem sehr
  niedrigen Abstraktionsniveau an. Diese nehmen Bezug auf Details der
  Datenspeicherung und der Implementierung des Datenbanksystems. Der Einsatz
  dieser Datenmodelle erfordert einschl"agige Erfahrungen im Bereich der
\end{description} 

\e{Datenbankmodelle} Zugriffspfade Unterscheidung nach den Entit"aten die, die
Basisstrukturen des Datenmodells bilden:????

\begin{description}
\item[] \e{Objektbasierte} Datenmodelle beschreiben haupts"achlich Objekte und
  die Beziehungen zwischen diesen Objekten.

\item[] \e{Rekordbasierte} Datenmodelle verwenden Recordstrukturen f"ur die
  Repr"asentation der Daten.

%\comment{siehe noch Text Navathe S. 24 und S.33?}
%  overview data models Navathe S. 637
\end{description}

{\normalsize Klassifikation: Wertbasierte (relationale, funktionale) 
und objektbasierte (hierarchische, netzwerkartige, objektorientierte) 
Datenmodelle. Zustandsbegriff jedoch in allen Datenbanken (auf 
top level). Vorw"artsverweis auf Objektdiskussion in ODMG Kapitel.}

Informationsspeicherung auf verschiedenen Abstraktionsstufen 
mit unterschiedlichen Operationen m"oglich: [s. Cattell]

Datenbank ...

 Objektbank ...

 Wissensbank ...


\comment{Information Base: Volltextinfo, Rohdaten}

\subsection{Benutzergruppen und Modalit"aten}
\label{Benutzergruppen und Modalitaeten}

\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsffile{Bilder/PostScript/9.eps}
\caption{Benutzergruppen und Modalit"aten}
%\label{}  
\end{center}
\end{figure}

\begin{description}
\item Der \e{Datenbankadministrator(DBA)} ist f"ur die Kontrolle der
  internen und der konzeptuellen Schicht der Datenbank verantwortlich. In
  seinen Aufgabebereich fallen die Definition des Datenbankschemas
  (Konzeptuelles Schema), die Spezifikation von Integrit"atsbedingungen, der
  Entwurf der Speicherungstrukturen und Zugriffspfade (Internes Schema),
  Modifikationen des Schemas und der physischen Datenorganisation und die
  Vergabe von Zugriffsrechten an Benutzer.

\item Der \e{Anwendungsprogrammierer} gestaltet die externe Schicht der
  Datenbank verantwortlich. Er definiert die externen Schemata und realisiert
  Anwendungsprogramme mit eingebetteten Aufrufen an die Datenbank. Diese
  stehen dem Endbenutzer als vordefinierte Transaktionen zur Verf"ugung.

\item Die \e{Endbenutzer} lassen sich nach der Art der Benutzung und ihrer
  Kenntnis der Datenbank in mehrere Gruppen unterteilen.

\begin{itemize}
\item Der \e{interaktiver Benutzer} zeichnet sich typischerweise dadurch aus,
  da"s er die DB nur gelegentliche benutzt und meist keine Standardanfragen
  stellt.  Er geh"ort in der Regel zum Management und schreibt keine
  Programme, sondern verwendet eine Datenbankanfragesprache.

\item Der \e{parametrische Benutzer} verwendet vordefinierte
  Standardtransaktionen, die er nur noch mit den geeigneten Parametern
  versieht. Beipiele daf"ur sind Buchungen im Reiseb"uro und "Uberweisungen in
  der Bank. Diese Art der Benutzung der Datenbank erfordert keine
  informatische Ausbildung.

\item \e{Spezialisierte Benutzer} haben komplexe Anforderungen an die
  Datenbanken, die "uber den Rahmen der vordefinierten Transaktionen
  hinausgehen. Sie schreiben Programme f"ur ihre eigenen speziellen
  Bed"urfnisse, was eine gr"undliche Einarbeitung in die Eigenschaften und
  Schnittstellen des Datenbanksystems voraussetzt.
\end{itemize} 
\end{description}
%\comment{[s. Date, Navathe, Cattell 3.2.3]}

Eng verkn"upft mit den verschiedenen Arten von Endbenutzern sind die
verschiedenen Modalit"aten der Benutzung einer Datenbank.

%\comment{Aufz"ahlung Modalit"aten [Gesamter Abschnitt zu 1.1.6?]}

\subsection{Datenbanksysteme und ihre Modelle: Ein historischer Abri"s}
\label{Datenbanksysteme und ihre Modelle: Ein historischer Abriss}

Die Entwicklung von Datenbankmodellen und -sprachen ist im Flu"s und starken
Einf"ussen durch kommerzielle Datenbanksystemprodukte und
Standardisierungsbem"uhungen unterworfen. Dieser Abschnitt gibt einen
"Uberblick "uber die historische Evolution von Datenbanksystemen und ihren
Modellen, soweit sie zum Verst"andnis der heute in der Praxis und Forschung
relevanten Produkte und Konzepte notwendig erscheint. Die Darstellung lehnt
sich an [Catell xx, Brodie xx,] und [Navathe xx] an.

\subsubsection{Dateisysteme}
\label{Dateisysteme}

Die fr"uhen Betriebssysteme f"ur kommerzielle Anwendungen boten 
bereits die Basisdienste und Modellprimitive, die sich auch in 
den modernen Datenbanksystemen wiederfinden:

1. Rekords fester Gr"o"se aggregieren Attribute verschiedener 
Datentypen.

2. Dateien fassen gleichartige Rekords zusammen, k"onnen dynamisch 
wachsen und schrumpfen, in ihrem Umfang die Kapazit"at des Hauptspeicher 
des Computers "uberschreiten, und langlebig gespeichert werden.

3.Zugriffsstrukturen, wie Hashtabellen und sp"ater ISAM-Dateien 
erm"oglichen es, Rekords basierend auf ihren Attributwerten effizient 
innerhalb einer Datei zu selektieren.

4.Explizite oder implizite Datei- und Rekordsperren werden eingesetzt, 
um parallele Zugriffe zu kontrollieren.

\subsubsection{Fr"uhe Datenbanksysteme}
\label{Fruehe Datenbanksysteme}

In den 60er und fr"uhen 70er Jahren entstanden die ersten vollst"andigen 
Datenbanksysteme, die das hierarchische und das Netzwerkmodell 
unterst"utzen und die Funktionalit"at von Dateisystemen um weitere 
Dienste und Abstraktionen erweitern:

5.Rekordidentifikatoren, Adressen oder Verweisattribute erm"oglichen 
es, Rekords f"ur den effizienten direkten Zugriff zu verketten 
und hierarchische oder netzwerkartige Datenbankstrukturen zu 
bilden.

6.Mehrere Indexstrukturen k"onnen gleichzeitig ge"offnet sein 
und werden vom Datenbanksystem konsistent als eine gemeinsame 
Datenbank mit Verweisinformationen gewartet.

7.Zugriffskontrollmechanismen beschr"anken Rekordzugriffe auf 
authorisierte Agenten (Benutzer und Programme).

8.Es existiert eine Trennung zwischen logischem und physischen 
Schema.

9. Transaktionen bieten automatische Fehlererholung, Verklemmungserkennung 
und Integrit"at beim Mehrbenutzerzugriff .

Nachfolgend sind wichtige Meilensteine dieser Entwicklung aufgef"uhrt:

\begin{description}

\item[] 1959 Die \e{Conference on Data Systems and Languages} gr"undet
  zwei Komitees zur Entwicklung einer Sprache f"ur kommerzielle
  Anwendungen.  Das \glqq kurzfristige\grqq\ Komitee entwickelt
  \e{COBOL}, wohingegen das \glqq langfirstige\grqq\ Komitee unter dem
  Titel \e{List Processing Task Group} (sp"ater \e{Database Task
    Group}) Datenbanksprach- und modellkonzepte untersucht.

\item[] 1962 Das erste Datenbanksystem \e{Integrated Data Store} (I-D-S) von
  \e{General Electric} wird vertrieben. Sp"atere Systemversionen werden
  schrittweise um R"ucksetzoperationen, Fehlererholungsmechanismen und
  Sicherungspunkte (1964), Online Transaktionsverarbeitung (OLTP, 1966) sowie
  Parallelit"atskontrolle und Verklemmungserkennung (1968) erweitert.

\item[] 1961 Bachmann, der Architekt von I-D-S, stellt Datenstrukturdiagramme
  basierend auf sogenannten \e{record types} und \e{set types} vor. Diese
  Terminologie ist pr"agend f"ur die \e{CODASYL/DBTG} Standardisierung.

\item[] 1968 Das Produkt \e{ IMS/360 Version 1} basierend auf dem
  Hierarchischen Datenmodell wird von IBM f"ur das MVS Betriebssystem
  ausgeliefert. Das Produkt \e{IMS DB/DC (database/data communication)}
  entwickelt sich schnell zur Standardplattform zur Realisierung von
  Informationssystemen.  1994 existieren ca. 8000 IMS Installationen weltweit.

\item[] 196?-7? xx Partielle Implementierungen des CODASYL/DBTG Datenmodells
  werden als Produkte vermarktet.

\item[] 1971 Ver"offentlichung des \e{CODASYL/DBTG Report}, der das
  Netzwerkdatenmodell und den Dienstzugang zu Netzwerkdatenbanken beschreibt.

\item[] 1973 Bachmann erh"alt den \e{ACM Turing Award}.
\end{description}


\subsubsection{Relationale Datenbanksysteme}
\label{Relationale Datenbanksysteme}

In den sp"aten 70er und fr"uhen 80er Jahren wurden relationale 
Datenbanksysteme entwickelt und erreichten den Status kommerzieller 
Produkte, deren Dienste sich wie folgt von den fr"uhen Datenbanksystemen 
unterscheiden:

10.Hochsprachliche, deklarative Anfragesprachen erm"oglichen 
eine abstrakte, mengenorientierte Datenmodellierung und -manipulation 
unabh"angig von der Verf"ugbarkeit gespeicherter Verweisstrukturen.

11.Zus"atzliche anwendungsorientierte Dienstschnittstellen unterst"utzen 
interaktive (ad-hoc) Anfragen, Formular- und Reportdefinitionen, 
sowie die integrierte Beschreibung von Algorithmen und Anfragen 
in Sprachen der Vierten Generation (4GLs).

12.Es existiert eine Trennung zwischen konzeptuellem und logischen 
Schema.

Wie die folgende historische "Ubersicht zeigt, ist die Entwicklung 
relationaler Systeme eng mit der Entwicklung von Datenbanken 
als einer akademischen Disziplin gekoppelt:


\comment{Mit Kalenderdaten vereinheitlichen:}


Im Juni 1970 ver"offentlichte die 
\e{Association for Computing Machinery} einen Text von Dr. 
E.F. Codd, damals Mitarbeiter am IBM Forschungslabor in San Jose, 
Kalifornien. Der Text mit dem Titel 
\e{A Relational Model of Data for Large Data Bank }stellt 
einen Meilenstein in der Entwicklung von Datenbankmodellen dar:

\begin{itemize}
\item Daten werden nat"urlich beschrieben, ohne Bezug auf spezielle
  Implementierungsdetails auf Computern (mengenorientierter Tabellenzugriff
  vs. navigierender Zugriff auf ISAM Dateien).

\item Mathematische Fundierung des Modells (Mengen, Pr"adikate, funktionale
  Abh"angigkeiten,...)

\item Unabh"angigkeit der Datenstrukturen von Zugriffspfaden. Uniforme
  Repr"asentation von Objekten und Objektbeziehungen (vs. Tupel und Zeiger).
\end{itemize}

Direkt nach der Ver"offentlichung des Artikels von Dr. Codd begannen 
Entwicklunsarbeiten am IBM San Jose Research Laboratory f"ur 
ein Datenbanksystem und eine Sprache, die das relationale Modell 
unterst"utzt. Das Datenbankprojekt hie"s System R und die Sprache, 
um Datenbankzugriffe aus Anwendungsprogrammen durchzuf"uhren, 
wurde SEQUEL (Structured English Query Language) genannt Andere 
Hersteller waren schneller mit relationalen Produkten auf dem 
Markt (zum Beispiel Relational Softare Inc. heute Oracle). 


\comment{IBM 1981 Produkt SQL/DS. 1983 erste Version von 
DB2 (heutiges Produkt). Anderes Produkt: Ingres (Relational Technology) 
basierend auf Entwicklungsarbeiten an der Universit"at Berkeley 
(Michael Stonebraker, Eugene Wong). Ingres und Digital Equipment 
Corporation: Rdb/VMS, Rdb/ELN besa"sen urspr"unglich ander DB-Sprachschnittstellen 
(QUEL bzw. RDML), jedoch Marktdruck (IBM und Standardisierung) 
f"uhrte zur Verdr"angung dieser Sprachen trotz sprachlicher Vorteile. 
Weitere relationale Datenbanksysteme: Oracle, Sybase, Tandem 
xx

SQL-89 war unvollst"andig: Schema"anderungen nicht standardisiert, 
obwohl Funktionalit"at in allen DBMS vorhanden. Dynamisches SQL, 
Szstemtabellen, Mengenoperationen, Fehlerbehandlung. Kleinster 
gemeinsamer Nenner.

Erste Standardisierung 1986, leicht erweitert 1989. 1992 wurde 
eine entscheidend erweiterte "Uberarbeitung des Standards abgeschlossen. 
Implementierungen des vollst"andigen SQL-92 Sprachumfangs stehen 
aus (1994), L"osung: Schichtung des Standards. Gro"se Verbreitung 
von SQL Implementierungen macht SQL auch zum de-facto Standard. 
Intergalactical data speak (Stonebreaker). 

Umfang SQL-92 = 580 Seiten, SQL-89 = 115 Seiten. (5-fache Komplexit"at?). 


Schichtung: Entry SQL, Intermediate SQL, Full SQL. Entry SQL 
im wesentlichen SQL-89 (Ersatz f"ur SQL-89 Konstrukte, die nicht 
mehr unterst"utzt werden, Ersatz f"ur inkompatible Konstrukte, 
Vorbereitung f"ur Full SQL [Schl"usselwortkonflikte bei Bezeichnern], 
Fehlerkorrekturen des SQL-89 Standards).

Conformance

Implementation-defined

Implementation-dependent}

\comment{Interessante Frage: Trennung Funktionalit"at von 
Sprache. API. Erkl"arung ODBC von Microsoft.}

\begin{description}
\item[] 1972 Bayer und McCreight ver"offentlichen einen Artikel in \e{Acta
    Informatica}, in dem sie B-Trees vorstellen, eine Schl"usseltechnologie
  f"ur die Implementierung wertbasierter, assoziativer Zugriffe.

\item[] 1972 Die \e{Special Interest Group on Management of Data} (SIGMOD) der
  \e{American Association of Computing Machinery} (ACM) veranstaltet ihre
  erste internatinale Konferenz.

\item[] 1975 ANSI SPARC definiert Schichtenarchitektur, Einflu"sreich auf
  Verst"andnis, nicht unbedingt Produkte.

\comment{Get more info}

\item[] 1975 Die \e{Very Large Database Foundation} organisiert die erste
  internationale Konferenz.

\item[] 1976 Die \e{IFIP Working Group 2.6} XX organisiert ihre erste
  Konferenz.

\item[] 1976 IBM System R ver"offentlicht
\end{description}


\comment{19?? IBM DB2 ver"offentlicht

1978 Jim Gray ver"offentlicht den Artikel 
\e{Notes on Database Operating Systems}

L"oschen oder erkl"aren warum relevant.

19?? AMADEUS? 

1979 Vorschlag: Semantische Datenmodelle und Abstraktionsmechanismen 
(Codd, Roussopoulos, Brodie,) Frame-Basiert

1981 Codd erh"alt den 
\e{ACM Turing Award}

ER Datenmodell vorgeschlagen (Peter Chen)

Seit 1979 regelm"a"sige Konferenz

1983 ANSI/SPARC Relational Task Group ??

1983 H"arder, Reuter (ACID) in ACM CS.

198? QBE

19x? Minker, Reiter: Deduktive Datenbanken.Sehr aktiv in

19xx Erste Konferenz PODS ??

198? Ingres, Oracle, ...

198? System R, 

ADABAS, TH Darmstadt

1989 Erster SQL Standard

198? Fourth-Generation Language: XXX

198? Asthon Tate' s dBase ist erstes DB-Produkt, Borland Paradox, 
4th Dimension f"ur den Macintosh... alle basierend auf dem Relationalen 
Modell}

\subsubsection{Objektorientierte Datenbanksysteme}
\label{Objektorientierte Datenbanksysteme}

Beginn der objektorientierten Datenbanksysteme

13.Programmiersprachenanbindung

14. Persistenzabstraktion

15.Objektidentit"at

16.Verhaltensmodellierung

17. Vererbung von Struktur und Operationen

18.Versionsverwaltung

Als Meilensteine in der Entwicklung objektorientierter Datenbanksysteme sind zu nennen:
\comment{
19  Erster Workshop "uber Datenbankprogrammiersprachen. 
Alle zwei Jahre im Wechsel mit Persistent Object Stores.

19xx Erste Konferenz OOPSLA

19?? GemStone: Object Identity / Smalltalk

1989 OODBMS Manifesto: Revolution Politsches Pamphlet. Unbedingt 
notwendige, optionale und offene Bestandteile.

198? Next-Generation Manifesto: Evolution

Dittrich: Verhaltensm"a"sig objektorientiert, strukturell Objektorientiert

1993 ODMG-93 Standard Release 1. Gefolgt von Release 1.1 in 1994}

\subsubsection{Datenbanken in offenen Systemen}
\label{Datenbanken in offenen Systemen}

\comment{Evtl. Abschnitt l"oschen, weil zu spekulativ.

?? Legacy Databases

19?? DCE, CORBA, ...

19?? Object Store

19xx Visual Basic, PowerBuilder

198? Microsoft stellt Access vor und definiert ODBC. "Ubernahme 
durch Front-End Werkzeuge Spreadsheets und Back-Ends19?? O2 

19xx Volltextsuche mit WAIS

1994 WWW Mosaic erlaubt uniformen Datenzugriff in Weitverkehrsnetzen 
(Internet). Paradigma: Hypertext. 

1993 Gray, Reuter: Transaction Processing, Dienstsicht

Intelligent Information Systems

s. Catell 4.13-4.1.7



Gleichzeitig andere Speicherungssysteme (Volltextdatenbanken, 
Hypertextdokumente in Filesystemen, Bilddatenbanken. Wissenschaftliche 
Datenbanken}
