Flexible and Selective Indexing in XML Databases

XML, the eXtensible Markup Language, is becoming more and more popular not only as data exchange format on the Web but also as data format in database applications. The emerging trend towards XML applications creates the need for persistent storage of XML documents in databases. To efficiently query documents, XML databases require indices on the content and structure of frequently queried document fragments. Currently, XML databases still fail in offering flexible and selective indexing support for the specific requirements of the hierarchical, semi-structured XML data model.

Flexibility in indexing refers to supporting arbitrary queries on the content and/or structure of XML documents. Providing flexibility poses the following challenges: How can indices represent and process the hierarchical document structure? Which index structures are necessary to support arbitrary queries on the document content and structure? Selectivity refers to indexing frequently queried document fragments instead of entire documents. Providing selectivity raises the following research questions: How can a database management system process indices that refer to arbitrary document fragments? How can it keep arbitrary indices consistent with updates on documents?

The indexing approach SCIENS (Structure and Content Indexing with Extensible, Nestable Structures), which is presented in this thesis, provides flexible and selective indexing for XML databases. To represent and process the document structure, SCIENS uses a labeling scheme that encodes structural relationships into labels. While existing XML indexing approaches propose proprietary index structures, SCIENS adapts existing index structures to the XML data model. By extending and nesting index structures, SCIENS provides indices for arbitrary query workloads. The index framework enables SCIENS to process arbitrary indices based on an index model. To keep indices consistent with document updates, the maintenance algorithm of SCIENS exploits the document fragments being updated to extract relevant index updates.

The advantages of SCIENS are manifold. Flexible indices enable the definition of those indices that best match the query workload. Selectivity reduces index size and accelerates index traversal. Compared to existing XML indexing approaches, SCIENS only requires a small number of existing index structures, but can support a wider range of queries. The index framework guarantees that querying and updating documents remains unaffected by specific indices used. By exploiting the structure of update fragments, the maintenance algorithm can process updates more efficiently than existing approaches.

XML ist eine Auszeichnungssprache, welche ursprünglich vor allem als Datenaustauschformat eingesetzt wurde. Auch als Datenmodell gewinnt XML zunehmend an Bedeutung, weshalb Datenbanken zur Speicherung und Abfrage von XML Dokumenten benötigt werden. Um effizient Abfragen durchführen zu können, müssen XML Datenbanken den Inhalt und die Struktur häufig abgefragter Dokumentfragmente indizieren. Bislang unterstützen XML Datenbanken keine flexiblen, selektiven Indexstrukturen, welche den speziellen Anforderungen des hierarchischen, semi-strukturierten Datenmodells von XML gerecht werden.

XML Datenbanken benötigen Indizes, welche Abfragen auf den Inhalt und die Struktur von XML Dokumenten unterstützen. Diese Flexibilität stellt folgende Herausforderungen: Wie können Indizes die hierarchische Dokumentstruktur darstellen und verarbeiten? Welche Indexstrukturen sind notwendig, um beliebige Abfragen auf den Dokumentinhalt und die Dokumentstruktur zu unterstützen? Um nicht Dokumente als Ganzes indizieren zu müssen, sollen XML Datenbanken Indizes auf häufig abgefragte Dokumentfragmente definieren können. Diese Selektivität wirft folgende Fragen auf: Wie kann ein Datenbankverwaltungssystem Indizes auf beliebige Dokumentfragmente verarbeiten? Wie kann es beliebige Indizes mit änderungen am Datenbestand konsistent halten?

Diese Dissertation stellt einen neuen Indizierungsansatz namens SCIENS (Structure and Content Indexing with Extensible, Nestable Structures) vor. SCIENS repräsentiert und verarbeitet die Dokumentstruktur mit Hilfe von Labels, welche strukturelle Eigenschaften kodieren. Während bestehende XML Indizierungsansätze auf proprietären Indexstrukturen basieren, passt SCIENS existierende Indexstrukturen an das XML Datenmodell an. Durch Erweitern und Schachteln dieser Indexstrukturen stellt SCIENS Indizes für beliebige Abfragen zur Verfügung. Das Indexframework von SCIENS kann beliebige Indizes basierend auf einem Indexmodell verarbeiten. Um Indizes mit Dokumentänderungen konsistent zu halten, verwendet es einen neuen Algorithmus, welcher Indexänderungen aus den zu ändernden Dokumentfragmenten extrahiert.

Die Vorteile von SCIENS sind vielfältig. Flexibilität ermöglicht die Definition jener Indizes, welche die zu erwartenden Abfragen am besten unterstützen. Selektivität reduziert den Speicherbedarf und beschleunigt den Indexzugriff. Obwohl SCIENS lediglich auf einer kleinen Anzahl an Indexstrukturen basiert, kann es mehr Abfragen als bestehende Ansätze unterstützen. Das Indexframework garantiert, dass Indizes angelegt werden können, ohne Abfragen und änderungen an Dokumenten zu beeinflussen. Der Algorithmus, welcher Indizes mit Dokumentänderungen konsistent hält, ist effizienter als bestehende Ansätze.