Beda Christoph Hammerschmidt: KeyX: Selective Key-Oriented Indexing in Native XML-Databases Zusammenfassung In relationalen Datenbanken werden Indizes zur Beschleunigung von häufig wiederkehrenden Anfragen genutzt. Ein Index ist hierbei eine Datenstruktur, die spezifische Anfragen optimal unterstützt und Zugriffe auf die physikalische Datenbankschicht reduziert. In relationalen Datenbank-Management-Systemen (RDBMS) sind Indizes gut verstanden und werden tagtäglich eingesetzt, um spezifische und häufig wiederkehrende Anfragen zu beschleunigen.Für die Indizierung von XML-Datenbanken existieren zur Zeit noch keine Standardverfahren, sondern verschiedene Ansätze in der wissenschaftlichen Literatur, die oft nur Strukturanfragen zulassen und nur in wenigen Ausnahmen eine Auswahl bezüglich der indizierten Elemente erlauben. Die gängigen XML-Anfragesprachen wie XQuery und XPath nutzen Pfadausdrücke, um innerhalb der XML-Daten zu navigieren. Aus diesem Grund ist die effiziente Ausführung von Pfadausdrücken eine wichtige Aufgabe von XDBMS.Hierbei existieren verschiedene Ansätze, die z.T. nur navigierende Anfragen ohne Wertvergleiche oder ausschließlich Wertanfragen ohne Pfadberücksichtigung unterstützen. Sogenannte Structural-Summaries, die alle Knoten der XML-Daten in einer zweiten Datenstruktur ablegen, sind nicht selektiv, benötigen viel Speicher und verbessern die Leistung eines Datenbanksystems nicht, wenn häufig Änderungen vorgenommen werden, da jedes Mal die Indexstruktur aktualisiert werden muss. In dieser Dissertation wird das Konzept von spezifischen Indizes auf native XML-Datenbank-Management-Systeme (XDBMS) übertragen. Mit KeyX wird ein Indizierungsansatz vorgestellt, der XML-Element- und Attributwerte mit spezifischem Pfad als Schlüssel interpretiert und die dazugehörenden oder benachbarten Knoten im Original-Dokument als Rückgabewert referenziert. Da sich Schlüssel und Wert unterscheiden können, entfällt der Aufwand, der für navigierende Pfadverfolgung zwischen beiden benötigt wird. Die Auswahl von passenden Indizes ist ein wichtiger Prozess beim Anlegen und Optimieren der Datenbank. In dieser Arbeit wird dieses in der relationalen Welt wohlbekannte Index Selection Problem (ISP) auf XML Datenbanken übertragen. Das Bestimmen der besten Lösung ist i.A. sehr aufwendig, da das ISP ein NP-vollständiges Problem ist, zu dessen Lösung ein deterministischer Algorithmus exponentiell viel Zeit benötigt. Heuristiken, die gute Ergebnisse in wesentlich kürzerer Zeit liefern, wurden implementiert und bewertet. Es wird eine Implementierung präsentiert, die häufige Anfragen erkennt und nutzt, um die Datenbank zu optimieren. Da der Workload periodisch analysiert wird und durch das ISP günstige Indizes automatisch angelegt und ggf. auch wieder aufgelöst werden, garantiert die KeyX-Implementierung eine hohe Leistung über die gesamte Lebenszeit der Datenbank. Jeder Index muss aktualisiert werden, wenn die indizierten Daten sich im Original geändert haben. In relationalen Datenbanken, wo ein Index auf einer Tabelle und einer oder mehreren Spalten definiert wird, ist es ein triviales Problem, zu erkennen, ob eine SQL-Anweisung einen Wert einer solchen Spalte ändert oder nicht. In strukturierten XML Daten ist dieses Problem nicht so einfach zu entscheiden. Durch Platzhalter und bereichsübergreifende Pfadausdrücke ist es möglich, einen Knoten zu selektieren, der im Pfadausdruck nicht explizit aufgeführt wird. Für dieses Problem wird in der Arbeit ein auf endlichen Automaten basierender Algorithmus vorgestellt.