In einem Projekt mit Spektrum Akademischer Verlag, Universität Erlangen (Prof. Gasteiger) und der Universät Passau (Prof. Brandenburg) sollte ein multimediale Aufbereitung der Biochemical Pathways erfolgen. In diesem vom BMBF geförderten Projekt war die Universität Mannheim (Prof. Moerkotte) für die Datenhaltung zuständig. Im März 1998 wurde entschieden hierfür ein natives XML Datenbanksystem zu erstellen. Natix wurde geboren.
Der projektbetreuende Mitarbeiter der ersten Stunde war Herr Kanne. Er ist immer noch, auch nach auslaufen des Projektes aktiv an der Entwicklung von Natix beteiligt.
Herr Westmann und Herr Fiebig sind zwei weitere aktive Mitglieder des Natix-Projekts. Darüber hinaus halfen und helfen zahlreiche Studenten bei der Implementierung: Jürgen Dufner, Soeren Goeckel, Andreas Grünhagen, Alexander Hollmann, Jochen Leitz, Norman May, Julia Mildenberger, Oliver Moers, Thomas Neumann, Robert Schiele, Felix Schleer, Frank Ültzhöffer, Thomas Wecker, . Ohne die Unterstützung unseres Systemadministrators Herrn Leideck wäre ein Projekt wie Natix nicht durchführbar. Die administrativen Aufgaben erledigt in vorzüglicher Weise unsere Sekretärin Frau Seeger.
Als neuestes Mitglied in der Truppe der Natixer konnten wir Dr. Sven Helmer gewinnen.
Ebenfalls im Jahr 1998 wurde von INRIA (Dr. Abiteboul und Dr. Cluet) ein Projekt namens Xyleme initiiert, dass den Aufbau eines XML Warehouses zum Ziel hatte, das alle XML Dokumente, die auf dem Web zu finden sind speichert und anfragbar macht. Dabei sollten auch Anfragen unterstützt werden, die sich auf Änderungen beziehen, sogenannte Delta-Queries. Da man für dieses Projekt ein hoch skalierbares XML-Repository benötigte, wurde eine Kooperation vereinbart und Natix eingesetzt.
Aus dem Xyleme Projekt wurde 1999 das Start-Up-Unternehmen Xyleme. Parallel dazu wurde aus der Universität Mannheim das Unternehmen data ex machina ausgegründet.
Wozu Natix? Die Antwort in Kürze:
Natix ist in C++ auf UNIX-Plattformen entwickelt, Windows-Versionen und Java-Anbindungen sind aber in der Erprobung.
Die Architektur von Natix besteht aus drei Ebenen:
Die unterste ist die Speicherebene, die für die Speicherung von XML-Daten, Metadaten und Indexstrukturen zuständig ist.
In der nächsthöheren Ebene befinden sich die verschiedenen Datenbankdienste, die die über einfache Speicherung hinausgehenden Anforderungen der Anwendungen erfüllen.
Speicherebene und Dienste bilden zusammen die Natix Engine. Die Dienste kommunizieren untereinander und mit den Anwendungen durch das Natix Engine Interface, das eine einheitliche Schnittstelle für die gesamte Datenbank-Engine zur Verfügung stellt.
Auf Basis des Natix Engine Interface sind dann in der Anbindungsebene die verschiedenen Anwendungsanbindungen realisiert, in der die internen Repräsentationen von Dokumenten, Anfragen und Metadaten in die vom jeweiligen API benötigte Darstellung umgewandelt werden.
Die Speicherungsschicht enthält neben einem Cache-Mechanismus eine Abstraktionsschicht für Massenspeichergeräte, so da"s beliebige Medien mit blockweisem, wahlfreiem (Random Access) Zugriff als Träger von Natix-Partitionen dienen können (neben normalen Dateien kann Natix so auch direkt auf Festplattenpartitionen zugreifen).
Neben Standard-Indexstrukturen wie B-Bäumen und invertierten Listen ist auf dieser Ebene auch ein Index geplant, der in der Lage ist, neben der absoluten Positionen von Suchbegriffen auch Zusatzinformationen über den Kontext zu liefern, in dem der Begriff vorkommt.
Die virtuelle Maschine dient der Auswertung von Anfragen. Zur effizienten Abarbeitung simuliert sie einen Prozessor, dessen Befehlssatz neben einfachen Operationen auf Basistypen auch mächtige Befehle zum Zugriff auf Dokumente enthält. Dabei kann die virtuelle Maschine bei der Auswertung der Anfragen direkt auf die Hintergrundspeicherrepräsentation der XML-Dokumente zugreifen, ohne diese zunächst mit hohem CPU-Aufwand in eine Hauptspeicherrepräsentation (z.B. einen DOM-Tree) umzuwandeln. Auf die Struktur der Auswertungsprogramme wird in Abschnitt~\ref{sec:query} ausführlicher eingegangen.
Der Query Compiler übernimmt die Aufgabe, die in XML-Anfragesprachen formulierten Anfragen in Programme für die Natix Virtual Machine zu übersetzen. Es können auch mehrere Query Compiler im System vorhanden sein, falls mehrere Anfragesprachen unterstützt werden. Derzeit steht ein XPath-Compiler zur Verfügung. Näheres zur Anfragebearbeitung folgt in Abschnitt~\ref{sec:query}.
Die Transaktionsverwaltung stellt die Infrastruktur für Mehrbenutzerbetrieb zur Verfügung, bei dem die ACID-Eigenschaften (Atomicity, Consistency, Isolation, Durability) für die parallel ablaufenden Transaktionen garantiert werden können. Die wesentlichen Komponenten sind hier erstens die Isolation der Transaktionen durch das Verwalten von Sperren auf Objekten (wie Dokumenten und Knoten), sowie zweitens die Recovery, die für die Wiederherstellung der Daten bei einem Systemausfall oder dem Abbruch einer Transaktion zuständig ist und dafür eine Logdatei mit den erfolgten Änderungsoperationen verwaltet.
Dabei verlangt das Anforderungsprofil eines XML-DBMS mit sehr vielen Teilobjekten pro Dokument auch spezielle Sperrtypen und Protokolleinträge für Dokumente und Teildokumente. Eine konventionelle Transaktionskomponente ist hier schnell an der Grenze ihrer Leistungsfähigkeit. In Abschnitt~\ref{sec:iso} gehen wir beispielhaft auf die Optimierungsmöglichkeiten in der Isolationskomponente ein.
Um korrekten und durchsatzstarken Mehrbenutzerbetrieb zu ermöglichen, ist die Transaktionsverwaltung dabei eng mit der Speicherebene und der Anfragebearbeitung verzahnt, damit Sperren und Logeinträge für XML-Daten mit minimalem Overhead verwaltet werden können.
Zur Vermeidung von wiederholten Repräsentationswechseln zwischen der Hintergrundspeicherrepräsentation und den verschiedenen, von den Anwendungen verwendeten Hauptspeicherrepräsentationen (z.B. DOM-Tree) von Dokumenten wird ein Objekt-Cache eigesetzt, auf den die verschiedenen Anwendungstreiber über einen Objektmanager zugreifen können.
Neben den obligatorischen DOM-Schnittstellen für C++ und Java ist hier auch ein Dateisystemtreiber angesiedelt, der den Datenbankinhalt allen Anwendungen zur Verfügung stellt, die mit regulären Dateien arbeiten können. Dadurch kann die eventuell bestehende anfängliche Hürde beim Einsatz eines neuen DBMS leichter genommen werden.
Ein geeignetes Speicherungsformat für XML-Dokumente in einem DBMS mu"s die in der Einleitung angedeuteten Anforderungen erfüllen: 1. Navigation durch die Baumstruktur mu"s ohne erneuten Parsingaufwand möglich sein. 2. Man mu"s Dokumente mit beliebiger (auch ohne) DTD speichern können, und DTDs müssen entsprechend einem DB-Schema dem System zunächst bekannt gemacht werden. 3. Typische Zugriffsmuster (z.B. Navigation entlang der XPath-Achsen, Export einer textuellen XML-Darstellung) müssen effizient unterstützt werden.
Die typischerweise verwendeten generischen Formate zur Speicherung von XML-Dokumenten genügen den Anforderungen nicht:
Bei der Speicherung von ganzen Dokumenten in CLOBs geht die Dokumentstruktur verloren, und die Navigation zwischen einzelnen Dokumentknoten kann nicht effizient unterstützt werden, sondern erfordert erneutes Parsen und damit in der Regel aufwendige I/O-Zugriffe auch auf unbeteiligte Dokumentbestandteile.
Speichert man Dokumente knotenweise in einem herkömmlichen DBMS, geht sehr viel Platz verloren, da jeder Knoten zusätzlich zum Knotentyp (inkl. Tag-Namen) noch Referenzen auf den Vater-, Geschwister- und Kinderknoten enthalten mu"s. Diese Referenzen, z.B. als Fremdschlüssel realisiert, müssen beliebige andere Knoten erreichen können und dominieren daher den Platzaufwand. Au"serdem sind die Knoten eines Dokuments über den Hintergrundspeicher verteilt und müssen wiederum durch aufwendige I/O-Zugriffe beschafft werden.
Natix verwendet ein hybrides Speicherungsformat, das Teilbäume eines Dokuments jeweils auf einer Hintergrundspeicherseite clustert und dort in einem kompakten Format ablegt (Abbildung). Paßt ein Teilbaum aufgrund einer Änderungsoperation nicht mehr auf eine Seite, wird er gesplittet und auf mehrere neue Seiten verteilt. Nur für Referenzen, die Seitengrenzen überschreiten, muß ein platzaufwendigeres Format verwendet werden.
Im folgenden wird nun zunächst das Speicherungsformat der Teilbäume auf den Seiten beschrieben, und dann die Verteilung von größeren Dokumenten auf mehrere Seiten skizziert.
Jeder Teilbaum-Datensatz besteht aus einem Header und den Knotendaten. Der Header enthält eine Referenz auf den Vaterteilbaum sowie eine Kennung, zu welchem Dokument er gehört.
Die Knoteninformationen bestehen ebenfalls jeweils aus einem Header und dem Knoteninhalt. Der Knoteninhalt kann dabei entweder (z.B. bei Text- oder Attributknoten) ein Stringwert oder (z.B. bei Elementknoten) eine Folge von Kinderknoten sein.
Der Knotenheader enthält den Knotentyp, evtl. den Tag- oder Attributnamen, einen Zeiger auf den Vaterknoten und die Länge der Knotenrepräsentation inkl. Inhalt.
Dabei wird genutzt, daß die Länge des Knotens und die Position des Vaterknotens durch die Seitengröße begrenzt sind, d.h. es reichen je 2 Byte, um diese Information festzuhalten. Außerdem ist der Tag- oder Attributname nicht als Text, sondern in Form eines Verweises in eine Symboltabelle gespeichert. So benötigt die Codierung der gesamten Strukturinformation eines Knotens nur einen 8-Byte-Header. Das ist weniger, als ein Element-Tag mit zwei Zeichen Länge in Textform benötigt (<xx> </xx> = 9 Byte!).
Diese Darstellung ähnelt dem häufig für Indexstrukturen verwendeten B-Baum, nur daß als Schlüssel keine gewöhnlichen Datentypen wie Strings oder Zahlen verwendet werden, sondern Pfade im Dokumentbaum. Auch der Algorithmus zur Erzeugung und Pflege der so auf Seiten verteilten Dokumentstruktur weist Ähnlichkeiten mit den entsprechenden Algorithmen zur Pflege eines B-Baums auf:
Beispielsweise wird beim Einfügen eines neuen Knotens zunächst versucht, den Knoten in einen vorhandenen Teilbaum einzufügen. Sollte dies fehlschlagen, weil der resultierende Datensatz nicht mehr auf eine Seite passen würde, wird der Teilbaum in mehrere kleinere zerlegt (Split) und auf neue Hintergrundspeicherseiten verteilt. Dabei kann es bei Knoten mit sehr vielen Kindern auch dazu kommen, daß Teilbaum-Datensätze entstehen, die nur Proxies enthalten, die wiederum auf Proxies verweisen. Dies entspricht dem "`Überlauf"' in einem B-Baum, der denselben Schlüssel (hier: Pfad) mehrfach enthalten darf.
Der genaue Mechanismus findet sich in \cite{KaMo99}.
Betrachten wir nun ein paar Beispielanfragen, zu deren Formulierung wir die Anfragesprache XQuery verwenden wollen. Dabei handelt es sich um einen der prominentesten Vertreter der zahlreichen Vorschläge für eine deklarative XML-Anfragesprache. Wir beschränken uns hier auf XQuery-Anfragen, die aus einer FOR- bzw. LET-Klausel, einer WHERE- und einer RETURN-Klausel bestehen. Die FOR- bzw. LET-Klausel dient dem Generieren von Variablenbindungen, die in der WHERE-Klausel gefiltert werden. Die Ergebniskonstruktion anhand der gefilterten Variablenbindungen wird in der RETURN-Klausel spezifiziert.
Ein- und Ausgabe einer XQuery-Anfrage sind Instanzen einer Erweiterung des XPath-Datenmodells. Somit werden im wesentlichen XML-Dokumente als Bäume modelliert. Zur Navigation in einem Dokumentbaum bzw. zur Adressierung von Teilen eines Dokumentbaums werden in XQuery Lokalisationspfade (Location Paths) verwendet. Dabei handelt es sich um Pfadausdrücke aus dem XPath-Standard \cite{XPath}.
Die Beispielanfragen beziehen sich auf XML-Dokumente, die der in der Abbildung dargestellten Document-Type-Definition (DTD) entsprechen. Die DTD beschreibt die Struktur von Einträgen in einer Bibliographiedatenbank. Die Einträge enthalten Informationen über den Typ der Veröffentlichung, den Titel und die Autoren.
Die folgende Abbildung dargestellte erste Beispielanfrage Q1 zeigt die XQuery-Fähigkeiten zur Datenextraktion. Sie ermittelt Konferenzen, die nach 1996 stattgefunden haben.
{ FOR \$c IN document("bib.xml")/bib/conference WHERE \$c/year > 1996 RETURN } { \$c/title } { \$c/year }
Die FOR-Klausel extrahiert mittels eines Lokalisationspfads die im
Dokument bib.xml enthaltenen conference Elemente und
bindet diese an die Variable c. Die Variablenbindungen werden
von der WHERE-Klausel gefiltert. Das Filterprädikat überprüft, ob
das Veranstaltungsjahr der Konferenz nach 1996 liegt.
Für jede der gefilterten Variablenbindungen erzeugt die
RETURN-Klausel ein conference Element, dessen Inhalt aus dem
Titel und dem Veranstaltungsjahr der Konferenz gebildet wird. Die
conference Elemente werden in ein bib Element
eingebettet.
Während die vorangehende Anfrage eine einfache Extraktion vornimmt,
führt die in Abbildung~\ref{xquery2} gezeigte Anfrage eine
Restukturierung durch. In XQuery werden dazu geschachtelte Anfragen
verwendet. Die Anfrage erzeugt in einem conf-authors
Element eine Liste von author Elementen, die neben dem
Autorennamen eine Liste der mitverfaßten Konferenzartikel enthalten.
FOR \$a IN document("bib.xml")//conference/article/author
RETURN
{
FOR \$b IN document("bib.xml")//conference/article,
\$c IN \$b/author
WHERE \$c/@first = \$a/@first AND \$c/@last=\$a/@last
RETURN
{\$b/title}
}
Die Anfrage besteht aus zwei geschachtelten Anfragen. Die äußere
extrahiert die Autoren von Konferenzartikeln aus dem Dokument
bib.xml und erzeugt für jeden ein author Element.
Die in die FOR-Klausel eingebettete Unteranfrage bestimmt für jeden
Autor die Artikelliste. Dazu extrahiert sie alle Konferenzartikel aus
dem Dokument bib.xml, die den Autor in ihrer Autorenliste
enthalten.
Zur Darstellung von XML-Daten dient der Datentyp XML-Knoten. Entsprechend dem XPath-Datenmodell werden sieben Knotentypen unterschieden: Root, Element, Attribute, Text, NameSpace, ProcessingInstruction und Comment. Um Eigenschaften eines Knoten zu erfragen, wie den Markierungsbezeichner (Tag Name), den Typ oder den Zeichenkettenwert (String Value), stehen Funktionen wie getTagName, getType und getValue zur Verfügung. Die Navigation im Dokumentbaum wird mittels Navigationsfunktionen realisiert. Für die Umwandlung von Relationeninhalten in XML-Ergebnisdokumente stehen Konstruktionsfunktionen zur Verfügung.
Die Operatorenmenge der Natix-Algebra besteht aus relationalen Operatoren wie Select, Project und Join zur Bearbeitungen von Relationen. Da die Bearbeitung von XML-Daten weitgehend über Funktionen erfolgt, beinhaltet die Natix-Algebra verschiedene Map-Operatoren, die ein Auswerten von Funktionen auf den Tupeln einer Eingaberelation ermöglichen. Neben den Map-Operatoren führt die Natix-Algebra spezielle Gruppierungsoperatoren ein, die es erlauben, Kombinationen von Gruppierungen auszudrücken, was für die Auswertung von restrukturierenden Anfrage wichtig ist.
Bei der Auswertung eines Lokalisationspfads wird dieser zunächst in seine Lokalisationsschritte aufgeteilt. Zur Navigation entsprechend der Naviagationsachse wird für jeden Schritt ein UnnestMap-Operator eingeführt. Dabei handelt es sich um einen speziellen Map-Operator, der eine im Subskript spezifizierte mengenwertige Funktion auf den Tupeln der Eingaberelation auswertet und diesen das entschachtelte Funktionsergebnis als zusätzliches Attribut hinzufügt. Zur Auswertung eines Lokalisationsschritts besteht das Subskript aus einer Navigationsfunktion. Dabei handelt es sich um eine Funktion, die zu einem XML-Knoten eine geordnete Menge von Knoten entsprechend einer Navigationsachse bestimmt. Beispiele hierfür sind die Funktionen getParent, getChildren, getDescendantsOrSelf und getAttributes.
Zur Filterung der durch eine Navigation erreichten Knoten kann den Navigationsfunktionen ein Bezeichner als zusätzlicher Parameter übergeben werden, um nur Knoten mit einem bestimmten Namen zu selektieren. Weitere Filterprädikate können mittels eines Select-Operators angewendet werden.
Startet der auszuwertende Lokalisationspfad vom Wurzelknoten eines über eine URI spezifizierten Dokuments, wird ein ExpressionScan-Operator zusammen mit der getDocumentRoot Funktion verwendet, die zu einer URI den Wurzelknoten des entsprechenden Dokuments ermittelt. Der ExpressionScan-Operator liest keine Eingaberelation sondern wertet lediglich eine im Subskript spezifizierte Funktion aus und wandelt das Ergebnis in einen Tupelstrom um.
Abbildung~\ref{fig:plan1} zeigt den Operatorbaum der übersetzten
Anfrage aus Abbildung~\ref{xquery1}. Der ExpressionScan bindet
die Wurzel des Dokuments bib.xml an die Variable d. Die
anschließenden UnnestMap-Operatoren binden die im Dokument
enthaltenen bib-Elemente an die Variable b und die
conference-Elemente an die Variable c.
Die den UnnestMap-Operatoren folgenden Map-Operatoren
binden das erste titel und year Kindelement des an
c gebundenen XML-Knotens, an die Variablen t und y.
Für den Zugriff auf den ersten Knoten in einer geordneten Menge, wie
sie von einer Navigationsfunktion geliefert wird, wird hier die
Funktion getFirst verwendet. Das Filtern der
Variablenbindungen erfolgt durch einen Select-Operator. Dessen
Filterprädikat überprüft, ob das an y gebundene
year-Element eine Jahresangabe enthält, die größer als
1996 ist.
Die Konstruktionsfunktionen werden, wie die Navigationsfunktionen bei
der Variablenbindungsgenerierung, als Subskript für
Map-Operatoren verwendet. Der Auswertungsplan in
Abbildung~\ref{fig:plan1} enthält zur Ergebniskonstruktion einen
FL-Map-Operator. Dessen Subskript besteht aus drei Funktionen,
first, each und last. Die first Funktion
wird auf dem ersten, die last Funktion auf dem letzten und die
each Funktion auf jedem Tupel der Eingaberelation ausgewertet.
Im Beispielplan erzeugt die first Funktion die Startmarkierung
(Start-Tag) des bib Elements, dessen Inhalt aus dem
Anfrageergebnis besteht. Die each Funktion erzeugt ein
conference Element mit dem Konferenztitel und dem
Veranstaltungsjahr. Die last Funktion schließt die
Ergebniskonstruktion ab und erzeugt dazu die Endemarkierung des
bib Elements.
Zur Auswertung restrukturierender Anfragen und zum Entschachteln von XQuery-Anfragen sind in Natix spezielle Gruppierungsoperatoren vorgesehen, die ein Kombinieren von Gruppierungsoperationen ermöglichen. Einen entsprechenden Operatorbaum, der der Übersetzung der Anfrage aus Abbildung~\ref{xquery2} entspricht, zeigt die folgende Abbildung:
An die UnnestMap- und Map-Operatoren, die die Variablenbindungen erzeugen, schließen sich die Operatoren zur Ergebniskonstruktion an. Da es sich bei der Anfrage um eine restrukturierende Anfrage handelt, werden zur Ergebniskonstruktion die Variablenbindungen mittels des Groupify/GroupApply-Operatorenpaars gruppiert. Der Groupify Operator führt eine Gruppierung der Eingaberelation durch, die durch die im Subskript spezifizierte group-by Liste definiert wird. Zwischen den Operatoren ist ein Teilplan eingebettet, der auf jeder Gruppe ausgewertet wird. Zur Ergebniskonstruktion enthält das Subskript des Groupify Operators eine first Funktion, die vor dem eingebetteten Teilplan ausgewertet wird. Zusätzlich enthält das Subskript des GroupApply Operators eine last Funktion, deren Auswertung nach der des eingebetteten Teilplans für jede Gruppe erfolgt.
Aber auch andere Module benötigen spezielle Lösungen für den effektiven und effizienten Umgang mit XML: