[Uni












Natix: Ein natives Datenbanksystem für XML


Veröffentlichungen

Darüber hinaus gibt es noch zahlreiche interne Berichte, die die in den Veröffentlichungen angesprochenen Themen vertiefen.

Zusammenfassung

Die rapide Zunahme an XML-Dokumenten verlangt nach einer systematischen Verwaltung von XML-Dokument-Kollektionen. Das in diesem Aufsatz beschriebene Datenbankmanagementsystem Natix ist speziell füur die effiziente Verwaltung von XML-Dokumenten entwickelt worden. Wir beschreiben die Architektur von Natix und ausgewählte Module für die Speicherung und Anfrageauswertung.

Geschichte

Die Entwicklung von Natix startete im März 1998.

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.

Einleitung

Dieser Artikel beschreibt das native XML-Repository Natix, das speziell für die Verwaltung von XML-Dokumenten entwickelt wurde.

Wozu Natix? Die Antwort in Kürze:

Durch die rasant wachsende Akzeptanz von XML gibt es mehr und mehr XML-Dokumente, die systematisch verwaltet werden müssen. Ein System, das dies unterstützt, sollte dabei mindestens folgende Anforderungen erfüllen: Es muß XML-Dokumente effektiv speichern können und den effizienten Zugriff auf ganze XML-Dokumente oder Teile davon erlauben. Um sicheres Arbeiten mit Dokumentkollektionen zu gewährleisten muß ein solches System eine Transaktionsverwaltung beinhalten, die Recovery und Synchronisation realisiert. Vom W3C standardisierte deklarative Anfragemechanismen wie X-Path und X-Query sollten selbstverständlich ebenfalls unterstützt werden. Zur Realisierung von Anwendungen auf einem solchen System ist die Unterstützung von DOM und SAX unabdingbar. Die Architektur von Natix wird im nächsten Abschnitt beschrieben. Die darauf folgenden Abschnitte beschreiben das Speichersubsystem und die Anfrageauswertungsmaschinerie. Der letzte Abschnitt faßt den Artikel zusammen.

Natix-Systemüberblick

Bei der Realisierung von Natix wurde darauf Wert gelegt, die oben geschilderten Probleme beim Einsatz von konventionellen DBMS zur Speicherung von XML an der Wurzel zu beheben. Durch die Berücksichtigung der XML-Anforderungen bei Entwurf und Implementierung auch der unteren Schichten des Systems wurde dabei ein sehr leistungsstarkes, auf XML spezialisiertes DBMS geschaffen.

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.

Speicherebene

Dieser Teil von Natix übernimmt die Verwaltung aller persistenten Daten. Dazu gehören neben den XML-Dokumenten, auf deren Speicherung in Abschnitt~\ref{sec:storage} im Detail eingegangen wird, Indexstrukturen, Metainformationen und Protokolle für die Recovery-Algorithmen der Transaktionsverwaltung.

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.

Datenbankdienste

Das Natix Engine Interface stellt ein Framework zur Kommunikation der Dienste zur Verfügung. Operationen wie Compilation (Prepare) und Auswertung einer Anfrage, der Import und Export von Dokumenten werden als Request an das Engine Interface gestellt und an die jeweils beteiligten Dienste weitergeleitet.

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.

Anbindungsebene

In der Anbindungsebene sind die Schnittstellen zum Zugriff auf die Datenbank-Engine aus den verschiedenen Anwendungen realisiert.

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.

Speicherung

Anforderungen

In der Regel wird auf XML-Dokumente in Programmen mit Interfaces wie DOM oder SAX zugegriffen, in denen die Dokumentstruktur als Baum abgebildet wird.

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.

Speicherungsformat auf den Seiten

Der Hintergrundspeicher in Natix wird in Blöcken oder Seiten von fixer Länge (max. 64K) eingeteilt. Auf jeder Hintergrundspeicherseite können mehrere Teilbäume (also auch mehrere Dokumente pro Seite) abgelegt werden, wobei jeder Teilbaum von der unter der XML-Speicherung befindlichen Ebene als opaker, variabel großer Datensatz gehandhabt wird. Zur Verwaltung dieser Datensätze kommen erprobte Techniken wie Slotted Pages und extentbasiertes Freispeichermanagement zum Einsatz.

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!).

Verteilung eines Dokuments auf mehrere Seiten

Zur Repräsentation von Dokumenten, die größer sind als eine Seite, werden in die auf den Seiten gespeicherten Teilbäume sogenannte "`Proxy"'-Knoten eingefügt. Diese Knoten enthalten einen Verweis auf einen weiteren Teilbaum-Datensatz. Ersetzt man alle Proxies rekursiv durch ihre referenzierten Teilbäume, ergibt sich das Gesamtdokument. Jeder Teilbaum-Datensatz enthält außerdem wie oben beschrieben einen Rückzeiger auf den referenzierenden Teilbaum.

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}.

Isolation in Natix

Implementiert man ein natives Datenbanksystem für XML, so bereitet es keine Schwierigkeiten, Sperren auf Dokumentebene anzusiedeln. Aber auch Sperrprotokolle für feinere Granularitäten wie Dokumentknoten sind möglich. In Natix bietet es sich an, Sperren auf Teilbäumen zu vergeben, die in einem physischen Satz gespeichert sind. Will man ein hohes Maß an Nebenläufigkeit errreichen, so kann man die Semantik der Operationen auf Dokumentknoten ausnutzen und sehr spezifische Protokolle entwerfen. Die Grundlage bilden dabei Ansätze für die Synchronisation von ADTs. Hat man darüber hinaus noch Wissen über die DTD, so läßt sich ein Höchstmaß an Nebenläufigkeit erreichen. Die Beschreibung möglicher Protokolle würde den Rahmen dieses Übersichtsartikels sprengen. Wir verweisen den interessierten Leser daher auf die unten angegebene Literatur.

Auswertung von XML-Anfragen

Wie bereits beschrieben, wird zur Auswertung einer deklarativen XML-Anfrage diese in ein Auswertungsprogramm übersetzt und auf der Natix Virtual Machine ausgeführt. Da in Natix wie auch in traditionellen DBMS die Anfrageauswertung algebraisch erfolgt, beschreibt ein Auswertungsprogramm im wesentlichen die Auswertung eines algebraischen Ausdrucks. Gegenstand dieses Abschnitts ist daher die Übersetzung von deklarativen XML-Anfragen in algebraische Ausdrücke. Als Basis hierfür dient ein kurzer Überblick über die Besonderheiten von deklarativen XML-Anfragen.

Deklarative XML-Anfragen

Vereinfachend dargestellt dient eine XML-Anfrage zur Selektion, Extraktion, Kombination und Restrukturierung von XML-Daten. Die Selektion bezeichnet die Auswahl von Dokumenten aufgrund von Inhalt, Struktur oder anderen Attributen, wie Name, Alter usw. Die Extraktion ist die Auswahl von Dokumentausschnitten, wie Elemente, Textfragmente oder Attributwerte. Zur Extraktion werden bestimmte Methoden zur Adressierung von Ausschnitten in XML-Dokumenten verwendet, wie z.B. Pfadausdrücke. Das Zusammenführen des Inhalts mehrerer XML-Dokumente wird als Kombination bezeichnet. Dies entspricht der Verbund- (Join-)Operation in relationalen oder objektorientierten Datenbankmanagementsystemen. Der letzte Punkt, die Restrukturierung, bezeichnet die Transformation oder Umstrukturierung eines XML-Dokuments. Wichtige Anfrageprimitiven hierfür sind geschachtelte Anfragen, Gruppierungen und Ordnungsoperationen.

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.

<ELEMENT bib (conference|journal)*> <ELEMENT conference (title, year, article+)> <ELEMENT journal (title, volume, no?, article+)> <ELEMENT article (title, author+)> <ELEMENT title (#PCDATA)> <ELEMENT author EMPTY> <ATTLIST author last CDATA #REQUIRED first CDATA #REQUIRED>

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 } 
    
}

Q1: XQuery-Anfrage zur Bestimmung von aktuellen Konferenzen.

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}
}
Q2: XQuery zur Generierung eines Dokuments mit Konferenzautoren.

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.

Natix-Algebra

Wie im vorangehenden Abschnitt gezeigt, beruhen XML-Anfragen auf der Bearbeitung von Variablenbindungen. Diese lassen sich effizient in Tabellenstrukturen verwalten. Ausgehend von dieser Überlegung, basiert der Entwurf der Natix-Algebra auf einer Erweiterung einer relationalen Algebra. Die Erweiterung besteht in der Einführung neuer Datentypen zur Abbildung des XPath Datenmodells \cite{XPath} und neuer Operatoren zur Generierung von Variablenbindungen und zur Konstruktion von Ergebnisdokumenten. Wir können an dieser Stelle aus Platzgründen die Natix-Algebra nur kurz skizzieren und verweisen daher für eine detaillierte Beschreibung auf \cite{FiMo01+}.

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.

Generieren von Variablenbindungen

Das Generieren von Variablenbindungen beruht, wie in den Beispielanfragen gezeigt, auf Lokalisationspfaden. Ein Lokalisationspfad besteht aus einer Sequenz von Lokalisationsschritten (Location Steps). Ein Lokalisationsschritt beschreibt einen Navigationsschritt ausgehend von einem Kontextknoten in einem Dokumentbaum entlang einer Navigationsachse. Die Navigationsachse bestimmt die Beziehung, die zwischen dem Kontextknoten und den erreichten Knoten besteht. Zur Filterung der durch die Navigation erreichten Knoten können vom Lokalisationsschritt Filterprädikate angewendet werden. Ein Lokalisationsschritt liefert somit in einem Lokalisationspfad eine gefilterte Liste von Knoten, die jeweils den Kontextknoten für den nächsten Lokalisationsschritt bilden.

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.

Als Operatorbaum dargestellter algebraischer Ausdruck zur Auswertung der Anfrage Q1.

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.

Ergebniskonstruktion

Die Ergebniskonstruktion erfolgt durch das Anwenden von Konstruktionsfunktionen auf Variablenbindungen. Diese übermitteln das Ergebnis der Anfrage per Seiteneffekt an die Anwendung. Im einfachsten Fall handelt es sich bei den Konstruktionsfunktionen um Ausgabefunktionen zur Konstruktion einer textuellen Darstellung. Für eine effizientere Form der Ergebnisweiterleitung ist es auch möglich, Konstruktionsfunktionen zu verwenden, die SAX-Events generieren.

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:

Als Operatorbaum dargestellter algebraischer Ausdruck zur Auswertung von der Anfrage Q2.

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.

Fazit

Wir haben einen Überblick über die Architektur von Natix gegeben und anhand ausgewählter Module von Natix gezeigt, wie effektive und effiziente Lösungen für die Verarbeitung von XML aussehen können.

Aber auch andere Module benötigen spezielle Lösungen für den effektiven und effizienten Umgang mit XML:

Literaturhinweise