4.1.4.4: Ein Vektorraummodell für strukturierte Anfragen an Sammlungen von XML-Dokumenten

Ein mögliches Vorgehen bei der Suche in XML-Dokumenten soll im Folgenden an einem Beispiel geschildert werden. Schlieder und Meuss (2002) [->] beschreiben ein Verfahren, bei dem mit strukturierten Anfragen nach einzelnen Elementen in XML-Dokumenten gesucht und auch mit einem erweiterten Vektorraummodell eine Rangordnung gleicher Elemente berechnet werden kann.

Baumdarstellung von Dokumenten

Die Dokumente werden in diesem Ansatz als Baum dargestellt, wobei jedes Element durch einen Knoten repräsentiert wird, der eine Bezeichnung trägt (labeled node), und von dem eine Kante zu den Knoten der Unterelemente führt. Dieser klassische Baum eines SGML- oder XML-Dokuments wird durch weitere Knoten und Kanten erweitert, wie es bereits im Abschnitt über XPath kurz beschrieben wurde: Für jedes Attribut wird ein Knoten eingeführt, der mit einer Kante am Knoten des Elements hängt, zu dem das Attribut gehört. Hat das Attribut einen Wert, wird dieser als weiterer Knoten an den Attributwert gehängt. Wenn der Attributwert aus mehreren Wörtern besteht, wird für jedes Wort ein separater Knoten an den Attributknoten angehängt. Die Wörter werden auf Grundformen reduziert.

Schließlich werden auch die Inhalte der Elemente in diesem Baum dargestellt: Wie die Attributwerte werden die Texte in Wörter zerlegt, auf Grundformen reduziert und für jeden dieser Terme ein Knoten an den Knoten des Elements, das den Text enthält, gehängt. Die Knoten des Baums haben dabei alle den gleichen Typ (bzw. sie werden nicht nach Datentypen unterschieden). Die Bäume der Dokumente einer Sammlung werden durch einen gemeinsamen Wurzelknoten zusammengefasst, sodass die Sammlung durch einen großen Baum repräsentiert wird, der die Dokumente als Teilbäume (sub-trees) enthält. (Ein Teilbaum enthält alle Nachfolgerknoten eines Knotens, während ein Ast nicht alle Nachfolgerknoten enthalten muss.) Teildokumente, die als (gegebenenfalls Top-Level-)Elemente in den Dokumenten enthalten sind, bilden ebenfalls Teilbäume. Allgemeiner kann jeder Teilbaum, der in einem Elementknoten beginnt, als Teildokument oder logisches Dokument aufgefasst werden.

Strukturierte Terme und Anfragen

Betrachtet man umgekehrt die Blätter des Baums, also die Knoten, von denen keine Kanten ausgehen, so sind das zunächst alle Terme, die in den Dokumenten vorkommen, die Terme, die in den Werten der Attribute vorkommen, die Attribute ohne Wert und schließlich eventuell Elemente, die keinen Inhalt und keine Attribute haben. Diese Knoten können als Terme der Dokumente betrachtet werden. Schlieder und Meuss bezeichnen weiterhin aber auch alle anderen Knoten zusammen mit den Teilbäumen, deren Wurzeln sie sind, als strukturierte Terme. Derselbe Teilbaum eines XML-Dokumentbaums kann also ein logisches Dokument oder ein strukturierter Term sein, je nachdem, in welcher Rolle er betrachtet wird.

Wie beim Vektorraummodell haben in diesem Modell Anfragen das gleiche Format wie Dokumente: Sie sind ebenfalls Bäume mit bezeichneten Knoten und Kanten zu Unterelementen. Nach welchen logischen Dokumenten mit einer Anfrage gesucht wird, hängt von der Bezeichnung des Wurzelknotens der Anfrage ab: Eine Anfrage sucht nach genau den logischen Dokumenten, deren Wurzelknoten die gleiche Bezeichnung haben wie der Wurzelknoten der Anfrage.

Um das Auftreten eines strukturierten Terms in einem logischen Dokument oder einer Anfrage zu beschreiben, verwenden die Autoren den Begriff der Einbettung eines bezeichneten Teilbaums in einen (anderen) bezeichneten Baum: Ein Baum Q kann in einen Baum D eingebettet werden, wenn sich die Knoten von Q auf die Knoten von D so abbilden lassen, dass zum einen das Bild eines Knotens die gleiche Bezeichnung hat wie der Knoten selbst und zum anderen der Elternknoten eines Knotens aus Q auf den Elternknoten des Bildes in D abgebildet wird. Das heißt, dass Q in D eingebettet werden kann, wenn sich die Baumstruktur der Anfrage auf die des Dokuments abbilden lässt und dabei die Bezeichnungen der Knoten erhalten bleiben.

Es müssen aber nicht für alle Knoten aus D Knoten aus Q existieren, die darauf abgebildet werden: Das Bild des eingebetteten Baums kann eine Teilmenge des Teilbaums in D sein, in den er eingebettet wird. Außerdem können mehrere Knoten auf den gleichen Bildknoten abgebildet werden.

Über die Einbettung wird das Auftreten eines strukturierten Terms in einem logischen Dokument oder einer strukturierten Anfrage definiert: Ein strukturierter Term tritt in einer Anfrage oder in einem Dokument auf, wenn er darin eingebettet werden kann. Um eine Anfrage zu bearbeiten, werden alle strukturierten Terme, die darin enthalten sind, isoliert, und es wird ihr Auftreten in den logischen Dokumenten der Sammlung untersucht, die durch Knoten definiert sind, die die gleiche Bezeichnung haben wie der Wurzelknoten der Anfrage.

Um nicht immer eine vollständige strukturierte Anfrage verwenden zu müssen, die die vollständigen Pfade vom Wurzelknoten des gesuchten logischen Dokuments bis zu den Termen oder Attributwerten enthalten müsste, führen die Autoren eine Darstellung der Anfrage mit "freien" strukturierten Termen ein: Neben der Bezeichnung des Wurzelelements (durch das das logische Dokument bestimmt wird, nach dem gesucht wird) werden einzelne strukturierte Terme angegeben, über deren Auftreten in den logischen Dokumenten die Ähnlichkeiten der Anfrage zu diesen logischen Dokumenten im Vektorraummodell berechnet werden. Dabei ist nicht ganz klar, ob auch die Unterterme der strukturierten Terme verwendet werden oder nicht.

Die Lage der freien strukturierten Terme im logischen Dokument ist nicht mehr vollständig festgelegt wie bei der Spezifizierung einer strukturierten Anfrage als vollständigen Baum. Wenn also ein Stichwort in allen Elementen durch ein Element indexterm als solches gekennzeichnet werden kann, würde durch einen einzigen freien strukturierten Term <indexterm>Kirschblüte</indexterm> in der Anfrage dieses Element in allen XML-Elementen, die in den logischen Dokumenten vorkommen, als Stichwort erfasst - wie ein relativer Pfad in XPath.

Wenn es nur innerhalb eines bestimmten Elements als Stichwort erkannt werden soll, müsste ein entsprechend langer Pfad angegeben werden, der dieses Element (z.B. durch einen absoluten Pfadnamen) eindeutig bezeichnet. Durch die Verwendung von freien strukturierten Termen in Anfragen wird der Einfluss der Suche nach globalen Strukturen auf die berechneten Ähnlichkeiten verringert und damit der Einfluss der Terme und der lokalen Struktur verstärkt.

Das Vektorraummodell für strukturierte Terme

Wie beim klassischen Vektorraummodell wird in diesem Modell die Häufigkeit des Auftretens von strukturierten Termen in strukturierten Anfragen und logischen Dokumenten verwendet. Zur Berechnung der Gewichte des Dokumentvektors werden für alle logischen Dokumente, deren Wurzel die gleiche Bezeichnung hat wie die Wurzel der Anfrage, die Termhäufigkeiten und Dokumenthäufigkeiten zur Anfragezeit berechnet, um beispielsweise eine TF-IDF-Formel anzuwenden. Die Gewichte der angegebenen strukturierten Terme für den Anfragevektor können von den Nutzenden vergeben werden. Automatisch extrahierte Unterterme erhalten das Gewicht 1.

Implementierung

In der von Schlieder und Meuss beschriebenen Implementierung wird jeder Knoten im Baum der Dokumentensammlung durch drei Einträge in der Positionsliste des Terms, mit dem er bezeichnet ist, angegeben:

• mit seiner Ordnungsnummer (pre-order number), für die der Baum in der Wurzel beginnend prioritär von "oben nach unten" und sekundär von "links nach rechts" durchnummeriert wird,
• mit der größten Ordnungsnummer, die im Teilbaum, der im Knoten wurzelt, vorkommt (das ist die Ordnungsnummer des Knotens "rechts unten"),
• mit der Anzahl des Auftretens des häufigsten Terms in diesem Teilbaum.

Das beschriebene System wurde bisher nur auf eine kleine Sammlung von 22 Dokumenten angewendet, die alle die gleiche DTD zu verwenden scheinen. Über eine systematische Evaluierung wird nicht berichtet. Kritisch ist bei diesem Ansatz sicherlich die Tatsache, dass die Nutzenden die Elementstruktur der Dokumente kennen müssen, um gezielt suchen zu können.