AP7 -- Ziele und Überblick

Norbert Fuhr <fuhr@cs.uni-dortmund.de>
Kai Großjohann <Kai.Grossjohann@CS.Uni-Dortmund.DE>

Ziele und Überblick

Ziel von AP7 ist es, ein System für das Retrieval in XML-Dokumenten zu bauen, das als Ersatz für Harvest dienen kann. Die Retrievalfunktionalität von Harvest ist verbesserungsbedürftig. Die von Harvest unterstützte Dokumentstruktur ist recht flach.

Das in AP7 zu entwickelnde System soll geschachtelte Dokumente ermöglichen und verschiedene Datentypen mit vagen Prädiketen anbieten. Für Personennamen wäre beispielsweise ein Prädikat sounds like wünschenswert, bei der ACM-Klassifikation muss ein similar-Prädikat anders definiert werden.

Systemarchitektur

Systemarchitektur

XQL

Die von uns verwendete Anfragesprache XIRQL (XML IR Query Language) lehnt sich an XQL an. Es zeichnet sich ab, dass XQL (oder eine ähnliche Sprache) die Standard-Anfragesprache für XML-Dokumente werden wird, denn XQL ist eine natürliche Erweiterung von XPath, und XPath ist bereits Standard des W3C.

XQL unterützt die strukturorientierte Suche in XML-Dokumente, unterstützt aber nur wenige Datentypen (Number, Date, und String) und keine vagen Prädikate. Ferner lehnt sich XQL sehr eng an die XML-Syntax an. Beispielsweise kann die gleiche Information (etwa der Autorname) in einem XML-Element oder in einem XML-Attribut codiert sein, und der Benutzer sollte nicht für jeden Dokumentenbestand einzeln lernen müssen, wie die Informationen codiert sind.

XQL an Beispielen

Man betrachte folgendes XML-Dokument als Beispiel:

<document class="H.3.3">
    <author>John Smith</author>
    <title>XML Retrieval</title>
    <chapter>
        <heading>Introduction</heading>
        This text explains all about XML and IR.
    </chapter>
    <chapter>
        <heading>Extensible Style Language</heading>
        <section>
            <heading>Examples</heading>
        </section>
        <section>
            <heading>Syntax</heading>
        </section>
    </chapter>
</document>
      

Für das Verständnis der Anfragesprache ist wichtig, zu verstehen, wie ein solches Dokument in die interne Darstellung, einen Baum, gewandelt wird. Jedes Element wird zu einem Knoten, jedes Attribut wird zu einem Knoten, und für den eigentlichen Text gibt es wieder Knoten. Obiges Beispieldokument wird in folgenden Baum transformiert:

XML-Baum zum Beispieldokument

XML-Baum zum Beispieldokument

Elemente sind als Ovale dargestellt, Attribute als Rechtecke, und Text-Knoten in Rechtecken mit abgerundeten Ecken.

Hier nun eine Reihe von Beispiel-Anfragen:

//heading
Liste aller Überschriften. // durchsucht alle Nachfahren der Wurzel, und die Einschränkung auf bestimmte Elemente erfolgt durch das Hinschreiben des Element-Namens.
//chapter/heading
Liste aller Kapitel-Überschriften. Der binäre Operator / drückt ein Eltern/Kind-Verhältnis aus.
//chapter[heading]
Liste aller Kapitel, die eine Überschrift haben. Der Filter-Operator [...] schränkt die Ergebnisse ein. Vergleiche auch die vorige Anfrage (die Überschriften-Knoten zurückliefert) mit dieser (die Kapitel-Knoten zurückliefert).
//document/*
Liste aller Top-Level-Elemente. * ist eine Wildcard.
/document[@class="H.3.3" $and$ author="John Smith"]
Dokumente aus ACM-Klasse H.3.3 von John Smith. Der unäre Operator / durchsucht alle Kinder der Wurzel (vgl. // für alle Nachfahren der Wurzel). Attributnamen werden mit @ geschrieben. Boolesche Operatoren $and$ sowie $or$ sind möglich.
/document[@class="H.3.3" $and$ author="John Smith"]/chapter[heading="XML"]
XML-Kapitel aus obigen Dokumente. Es kann mehr als ein Filter-Operator in der selben Anfrage verwendet werden.
//(chapter $or$ section)/heading
Kapitel- und Abschnittsüberschriften. Die Operatoren können überall verwendet werden, nicht nur innerhalb von [...]. Man kann Klammern zur Gruppierung benutzen.

XIRQL

XIRQL ist eine Erweiterung von XQL um Datentypen und vage Prädikate. XIRQL erlaubt die Abstraktion von der konkreten XML-Syntax (Ignorieren von Attribut vs. Element). Zur Suche in Volltexten ist das Feature der relevanzorientierten Suche nützlich. XQL ist auf die Suche in einem Dokument beschränkt; diese Beschränkung wird durch XIRQL aufgehoben. XIRQL unterstützt gewichtete Anfragebedingungen (mittels $wsum$).

XIRQL an Beispielen

/document[~class $approx$ "H.3.3" $and$ ~author $sounds_like$ "Smythe"]
ACM-Klasse soll ähnlich H.3.3 sein und er Autor klingt wie Smythe. Man beachte auch die Notation ~author, wo zwischen Element und Attribut nicht unterschieden wird.
//chapter[heading $contains$ "extensible"]
Kapitel mit `extensible' in Überschrift. Ein weiteres Beispiel für vage Prädikate, diesmal auf den (für Information Retrieval recht wichtigen) Datentyp `Text' angewendet.
//document[.//#pname $eq$ "Miller"]
Dokumente, wo Miller erwähnt wird. Dies ist nützlich, falls Dokumente Markup im Fließtext besitzen, wo beispielsweise Personennamen besonders hervorgehoben sind. Die Notation #pname bedeutet `beliebiges Element mit Datentyp Personenname', was eine weitere Abstraktion von der konkreten XML-Syntax erlaubt.

Index-Knoten

Wenn man in strukturierten Volltexten sucht, dann weiß man nicht unbedingt, welche Strukturebene die Antwort zur Anfrage enthält. Betrachte man als Beispiel die Anfrage ``Gib mir was über IR und XML'' (die mit Absicht so vage formuliert ist). Falls in einem Dokument ein Abschnitt enthalten ist, das beide Worte enthält, so sollte dieser Abschnitt im Anfrageergebnis auftauchen. Falls in einem anderen Dokument das Wort IR in Abschnitt 3.2 steht und das Wort XML in Abschnitt 3.5, so möchte man für dieses Dokument das Kapitel 3 zurückliefern, statt eines Abschnitts. Index-Knoten erlauben es dem System, den richtigen Kontext auf eine Anfrage zurück zu liefern.

Herkömmliche IR-Systeme verwenden ein Dokument-Konzept, das für strukturierte Dokumente nicht anwendbar ist. So macht es beispielsweise keinen Sinn den `kleinen Brockhaus' oder die `Encyclopedia Britannica' als Antwort auf eine Suchanfrage zurück zu liefern. Das andere Extrem wäre die Ebene des einzelnen XML-Elements. Diese Ebene hat jedoch eine viel zu kleine Granularität: sicherlich möchte man nicht das <em>-Element als Antwort auf eine Suchanfrage geliefert bekommen.

Die Lösung für diese Probleme sind die sogenannten Index-Knoten. Der Datenbankadministrator (der seine Dokumente ja am besten kennt) spezifiziert, welche Teilbäume eines Dokuments als Index-Knoten zu betrachten sind. Die Index-Knoten nehmen dann die Stellung von Dokumenten in herkömmlichen IR-Systemen ein, d.h. sie werden als Basis für die Termgewichtung verwendet, und können als Suchergebnisse zurückgeliefert werden.

Hier ein Beispiel für einen Dokument-Baum, wo die Index-Knoten markiert sind.

XML-Baum mit Index-Knoten

Die Index-Knoten partitionieren den XML-Baum in nichtüberlappende Teilbäume.

Für das Finden von Antworten auf eine Suchanfrage gibt es verschiedene Alternativen:

In unserem System werden sowohl die spezielle Funktion `contains' als auch die Variante des //-Operators angeboten.

Stand der Dinge