Institut für Informationssysteme

KeyX:
schlüssel-orientierter XML Index

english version

Kurzbeschreibung des Projektes:

In relationalen Datenbank-Management-Systemem (RDBMS) werden Indizes verwendet, um spezifische und häufig wiederkehrende Anfragen zu beschleunigen. Die Auswahl von passenden Indizes ist ein wichtiger Prozess beim Anlegen und Optimieren der Datenbank, der meist von einem Administrator oder einem Index-Auswahl-Tool durchgeführt wird, welches eine Menge von passenden Indizes vorschlägt. Für die Indizierung von XML-Daten existieren zur Zeit noch keine Standardverfahren sondern verschiedene Ansätze in der wissenschaftlichen Literatur, die oft rein Pfad-basiert sind und keine oder wenig Auswahl bezüglich der indizierten Elemente zulassen. Ansätze, die das gesamte Dokument indizieren - sogenannte Structural Summaries- haben zwangsläufig einen hohen Speicherplatzbedarf und garantieren keine Leistungssteigerung, wenn häufig Änderungen am XML-Dokument vorgenommen werden, da Änderungen der Datenbank immer auch an der Indexstruktur vorgenommen werden müssen.

In dem KeyX-Projekt wird das Konzept von spezifischen Indizes auf native XML-Datenbank-Management- Systeme (XDBMS) übertragen. Mit KeyX stellen wir einen Indizierungsansatz vor, 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. Experimentell bestimmte Ergebnisse der auf einem nativen XDBMS basierenden prototypischen Implementierung zeigen, dass unser Ansatz die Ausführungszeit von Anfragen signifikant beschleunigt.

KeyX unterstützt sowohl rein navigierende Anfragen ,wie auch Anfragen mit einem Wertvergleich. Insbesondere Anfragen mit mehrere Wertvergleichen werden durch mehrwertige Indizes effizient unterstützt. Anfragen, die Wildcards (*) oder self-or-descendant (//) enthalten sind ebenfalls möglich.

In einem Teilprojekt soll zu einer gegeben Menge von Anfragen und einer Datenbank die optimale Indexkonfiguration anhand eines Kostenmaßes gefunden werden. Hierbei werden insbesondere Änderungsoperationen berücksichtigt, die hohe Kosten erzeugen. Dieses Problem ist in der wissenschaftlichen Literatur als das 'Index Selection Problem' (ISP) bekannt und wird hier auf XML Datenbanken übertragen. Das ISP wird verwendet, um eine Menge von Indizes zu bestimmen, für die die Ausführungszeit eines Workloads von Datenbankoperationen minimal ist. Da der Workload periodisch analysiert wird und durch das ISP günstige Indizes automatisch angelegt und ggf. aufgelöst werden, garantiert die KeyX-Implementierung eine hohe Leistung über die gesamte Lebenszeit der Datenbank.
KeyX benötigt kein Schema, wie eine DTD oder ein XMLSchema, um Daten zu indizieren. Ohne Schema ist es unmöglich alle Indizes im voraus zu definieren; dies ist eine weitere Motivation für ein XDBMS, welches Indizes automatisch erzeugt.

Im Rahmen des KeyX - Projekts werden laufend Studien-, Bachelor- und Diplomarbeiten vergeben. Bei Interesse wenden Sie sich bitte an die Projektbeteiligten.

Beteiligte Mitarbeiter des Instituts für Informationssysteme:


Beteiligte Studenten (in alphabetischer Reihenfolge):

Publikationen

webmaster / 25.06.2004