5. Abfrage semistrukturierter Daten

Wenn semistrukturierte Daten in einer Datenbank gespeichert sind, kann man sie mit ähnlichen Konstrukten abfragen, wie sie auch in relationalen oder objektorientierten Datenbanken verwendet werden. Da die Datenmodelle für semistrukturierte Daten auf Graphen basieren, müssen Anfragesprachen diesen Graphen nach bestimmten Vorgaben durchsuchen können. Beispiele dafür sind Lorel [MAG+97], das für das Lore-Datenbanksystem entwickelt wurde, und UnQL [Su98].
Die interessanten Seiten können aber auch auf irgendeinem Server liegen. Um sie von dort abzufragen, kann man Wrapper für die einzelnen Seiten konstruieren. Ein System dafür wurde an der University of Southern California enwickelt [AK97].
Abschließend wird noch kurz erläutert, wie die Ergebnisse von Anfragen dargestellt werden können.

5.1 Anfragesprachen

Eine Gemeinsamkeit aller Abfragesprachen ist, daß sie beliebig lange Pfade in dem die Daten modellierenden Graph ablaufen können. Diese Pfade werden meistens als reguläre Pfadausdrücke angegeben. Somit sind solche Abfragesprachen für semistrukturierte Daten rekursiv, eine Eigenschaft, die beispielsweise SQL nicht hat und die man dort nur mit Hilfe von bestimmten Konstrukten erreichen kann.
Die Graphen können auch Zyklen enthalten. Deshalb ist es wichtig, daß die Anfragesprachen damit umgehen können. Man kann zum Beispiel schon besuchte Objekte markieren oder in einer Hash-Tabelle ablegen, um so feststellen zu können, ob man das Objekt schon besucht hat.

5.1.1 Lorel

Lore verwendet das OEM-Datenmodell, also einen gerichteten Graphen mit beschrifteten Kanten, wobei die Knoten die Objekte und die Kanten ihre Attribute repräsentieren. Die Bearbeitung einer Lorelanfrage entspricht also dem Durchlaufen des Graphen. Deshalb sind einfache Pfadausdrücke wie Abteilung.Mitarbeiter.Büro der grundlegende Baustein von solchen Anfragen.
Ein Beispiel:
Diese Anfrage gibt die Büros aller Mitarbeiter aus, die älter als 40 Jahre sind.
Die Syntax ähnelt OQL und tatsächlich ist Lorel eine Erweiterung von OQL. Bei der Bearbeitung der Anfrage in Lore wird die Lorelsyntax in eine OQL-Syntax umgewandelt.
Wie in Punkt 1.2 ausgeführt können semistrukturierte Daten sehr irregulär sein. Im obigen Beispiel kann das Objekt Büro bei verschiedenen Mitarbeitern unterschiedliche Attribute haben, nur ein einwertiges Attribut sein oder vielleicht ganz fehlen. Um für die obige Anfrage trotzdem die richtigen Ergebnisse zu bekommen, betrachtet Lorel alle Attribute als mengenwertig. Damit sind das Fehlen (leere Menge) und die Einwertigkeit (Menge mit einem Element) nur noch Spezialfälle eines allgemeinen Begriffs. Intern wird deshalb M.Alter > 40 in exists A in M.Alter : A > 40 umgewandelt.
Da der Nutzer oft das Schema der Daten nicht kennt, kann er in seinen Anfragen auch allgemeine Pfadausdrücke verwenden, also Muster für Pfade, für Attribute und für atomare Werte vorgeben, für die dann beim Durchlaufen des Graphen Entsprechungen gesucht werden.
Auch hierfür wieder ein Beispiel, das den Namen der Mitarbeiter ausgibt, deren Büronummer auf 343 endet (nach [MAG+97]):
Muster für atomare Werte und für Attribute werden über wildcards (hier das %-Zeichen) angegeben. Bei den Pfaden werden reguläre Ausdrücke verwendet. Dabei steht
()|() für die Disjunktion,
()? für ein optionales Attribut,
().() für die Konkatenation,
()* für die keinmalige oder beliebig häufige Wiederholung des Klammerinhalts,
()+ für die mindestens einmalige Wiederholung des Klammerinhalts.
Im obigen Beispiel kann also das Büroobjekt ein Attribut haben, das mit Zimmer beginnt, oder es kann ein Attribut haben, das Raum heißt, es muß aber auch gar kein solches Attribut haben.
Es gibt noch die Wildcard #, die für einen beliebig langen Pfadausdruck (also auch Länge null) eingesetzt werden kann, wenn man zum Beispiel nicht weiß, welche Objekte zwischen Mitarbeiter und Zimmer liegen.
Eine weitere Erweiterung von Lorel ist der grep-Ausdruck, mit dem man in allen Subobjekten eines bestimmten Objekts nach einem bestimmten Wert suchen kann. Die where-Klausel kann dann so aussehen:
Die Wildcard % wird nacheinander durch alle Attribute des Objekts R ersetzt und diese werden dann nach dem Wert value durchsucht (ähnlich wie in UNIX).

Es gibt in Lorel wie auch in OQL die Möglichkeit, Subqueries zu formulieren und Ergebnismengen explizit zu konstruieren wie im folgenden Beispiel (nach [MAG+97]):
Für jeden Mitarbeiter der Ergebnismenge wird ein Objekt angelegt, das den Namen und die Titel aller seiner Projekte außer alpha enthält. Das Weglassen der from-Klausel in der Subquery führt in Lorel zu keinem Fehler. Bei der internen Umwandlung in eine OQL-Anfrage wird diese noch ergänzt.
Als Lorelspezifische Erweiterung ist noch der soundex-Operator zu nennen, mit dem eine phonetische Übereinstimmung eines Attributs mit einem Wert überprüft werden kann.
Auch Transformationen der Daten, also update-Operationen können ausgeführt werden, jedoch ist die Ausdrucksmächtigkeit der Konstrukte beschränkt.

5.1.2 UnQL

UnQL (Unstructured Query Language) basiert auf struktureller Rekursion, die eigentlich für die Programmierung mit Mengen und Listen eingeführt wurde. Mit diesem Formalismus kann man sowohl Anfragen an semistrukturierte Daten stellen als auch Transformationen ausführen. Bei einer Transformation kann dabei ein völlig neuer Graph entstehen, was bei den update-Operationen von Lorel nicht möglich ist. Bei Anfragen wird eine Teilmenge der Knoten des existierenden Graphen als Ergebnis ausgegeben.
Für jede Anfrage wird in UnQL eine rekursive Funktion mit einer bestimmten Menge an Regeln definiert, die dann auf die Datenmenge, also den Graphen angewandt werden, bis man eine Ergebnismenge konstruiert hat.
Zur Verdeutlichung dient eine Beispielanfrage, die alle Integerzahlen, die in einer Datenbank enthalten sind, zurückgibt (nach [Su97]):

steht dabei für eine Mengenvereinigung.
Wie in Punkt 2.1.2 dargestellt verwendet auch das UnQL-Datenmodell Objekte und Graphen. Jedes Objekt hat eine eindeutige ID.
Wenn man als Datenmenge D eine Bibliotheksdatenbank betrachtet, heißt das Einstiegsobjekt beispielsweise Bib und hat die ID &o1, als ist D = {Bib : &o1}. Als erstes müßte also Regel (3) angewandt werden und man erhält f(&o1). &o1 enthält als Subobjekte zwei Bücher und einen Artikel, sieht also so aus &o1 = {Buch : &o2, Buch : &o3, Artikel : &o4 } = {Buch : &o2 } {Buch : &o3} { Artikel : &o4 }. Wenn man jetzt hier Regel (4) zweimal anwendet und dann Regel (3) dreimal, erhält man als Zwischenergebnis f (&o2) f (&o3) f (&o4). Wenn man sich so bis zu den Blättern vorgearbeitet hat, kann man für jeden atomaren Wert Regel (1) anwenden und erhält so als Ergebnis eine Menge der Form {result : Zahl, ..., result : Zahl}.

Für Transformationen werden ebenfalls rekursive Funktionen definiert, wobei für eine Transformation auch mehrere Funktionen nötig sein können. Zum Beispiel eine, um die Stellen zu finden, an denen etwas verändert werden soll, und eine, um die Änderungen durchzuführen.

5.2 Wrapper

Viele Daten, die über das Web erreichbar sind, sind in Form von HTML-Seiten abgelegt. Diese können nicht direkt mit Datenbankanfragesprachen abgefragt werden, sondern müssen erst umgeformt oder "eingewickelt" werden.
Das hier vorgestellte System [AK97] geht von der Annahme aus, daß alle Seiten einer Quelle, die Informationen zum gleichen Thema enthalten (z. B. Informationen über Staaten, wobei es für jeden Staat eine Seite gibt, mit Informationen über Lage, Größe, Einwohner, usw.), die gleiche Struktur haben. Man muß also nur eine einzige Seite analysieren (vgl. Punkt 3.3). Für alle weiteren Anfragen an Seiten dieser Quelle, kann man auf die dabei gewonnene Information zurückgreifen.
Aus dem dabei entstehenden Baum wird eine Grammatik abgeleitet, die für jeden Knoten eine Regel enthält, die aussagt, daß der Abschnitt, den der jeweilige Knoten repräsentiert, genau die Unterabschnitte hat, die seine direkten Nachfolger darstellen. Die Reihenfolge der Unterabschnitte ist dabei durch die Reihenfolge der Kinderknoten festgelegt.
Mit Hilfe dieser Grammatik und der Tokens, die man im Strukturierungsschritt ( vgl. Punkt 3.3) erhält, kann ein Parser für diese Seiten generiert werden, der die gewünschten Informationen extrahiert.
Die Erzeugung des Parsers erfolgt automatisch mittels zweier Tools. Zuerst wird mit LEX ein Programm für die lexikalische Analyse erzeugt, das genau die gewünschten Tokens auf einer Seite identifiziert. Aus den Grammatikregeln wird mit YACC ein Parser generiert, der jede Seite dieser Quelle gemäß diesen Regeln analysieren kann.
Zu einem vollständigen Wrapper für die Seiten einer Quelle gehören noch Funktionalitäten, um (i) aus den Angaben in der Anfrage die URL der Seiten zu bestimmen, die untersucht werden sollen, (ii) die Daten dann von der Quelle zu laden und (iii) mit einem sogenannten Vermittler zu kommunizieren, also einem Programm, das die Daten in bestehende Datenbestände integriert. Für die Konstruktion der URL werden mapping - Funktionen verwendet, die der Nutzer vorher spezifizieren muß. Das Laden der Daten erfolgt über Perl-Skripte und die Kommunikation mit dem Vermittler erfolgt im Beispielsystem über KQML, eine Sprache zur Kommunikation zwischen Agenten.
Wrapper dieser Art bieten also die Möglichkeit, beliebige HTML-Seiten mit einer gewöhnlichen Anfragesprache zu bearbeiten und über Vermittler die Daten auch zu integrieren.

5.3 Araneus - Restrukturierung der Quelle

In Araneus [AMM97] werden für HTML-Seiten Schemata und Tabellen erzeugt, die dann in einer gewöhnlichen Datenbank gespeichert werden (vgl. Abschnitt 4.2), die eventuell auch andere relationale Daten enthält. Anschließend können mit der Sprache PENELOPE aus solchen Tabellen wieder HTML-Seiten erzeugt werden, die die Daten nach anderen Gesichtspunkten auswerten, und eventuell auch Links zu Originalseiten enthalten. Die Informationen werden also aus einer anderen Perspektive dargestellt.
Der Befehl in PENELOPE zur Erzeugung einer Seite aus einer Relation lautet
DEFINE PAGEP [ UNIQUE ]
ASS
FROMR

Dabei ist P der Name eines neuen Seitenschemas, UNIQUE gibt an, daß diese Seite einmalig ist, R ist eine Relation und S beschreibt die Struktur, indem die Attribute mit ihrem Typ und das entsprechende Attribut von R angegeben werden.
In Abschnitt 4.2 wurde eine Tabelle mit allen VLDB-Veröffentlichungen eines bestimmten Autors angelegt. Diese Tupel sollen jetzt nach dem Jahr der Veröffentlichung so sortiert werden, daß für jedes Jahr eine eigene Seite existiert, die alle Werke dieses Jahres enthält. Von jedem Werk aus soll es einen Link zu der Seite über diese Veröffentlichung geben, wobei hier die Seiten referenziert werden, die schon in der Quelle existieren. Als Einstiegsseite soll eine Seite dienen, die alle Jahre enthält. Von den einzelnen Einträgen dort kommt man dann zu den Jahresseiten.

Die Befehle in PENELOPE sehen folgendermaßen aus (nach [AMM97]):
DEFINE PAGEYearPage
AS
    URL URL(<Year>);
    Year: TEXT <Year>;
    Worklist: LIST OF
    ( Authors: TEXT <Authors>;
    Title: TEXT <Title>;
    Reference: TEXT <Reference>;
    ToRefPage: LINK TO ConferencePage UNION JournalPage
    <ToRefPage>);
FROMAuthorPapers


DEFINE PAGE AuthorYearsPage UNIQUE
AS URL éresult.html';
YearList : LIST OF
( Year : TEXT ;
ToYearPage : LINK TO YearPage(URL()));
FROMAuthorPapers

Die URL der neu erzeugten Seiten muß eindeutig sein. Man kann dafür entweder einen konstanten Wert angeben, wie im zweiten Befehl, oder einen Operator URL verwenden, der unter Verwendung eines übergebenen Werts (hier die Jahresangabe) eine eindeutige URL konstruiert. Die Attributwerte in spitzen Klammern sind die Attribute der Relation, die die Werte für die Attribute der neuen Seiten liefern. So hat zum Beispiel eine YearPage ein einwertiges Attribut Year, vom Typ Text, das den Wert des Attributs Year der Relation AuthorPapers annimmt (vgl. erster DEFINE-Befehl). Das Attribut ToRefPage bezeichnet Links zu Seiten, die auch mit ULIXES extrahiert wurden, aber in ihrer ursprünglichen Form verwendet werden sollen.
Auf diese Weise kann der Nutzer die Ergebnisse im ihm vertrauten HTML-Format betrachten und muß sich nicht erst durch eine Menge von Tupeln arbeiten, bei denen vielleicht nicht einmal die Attribute bezeichnet, sondern nur die Werte enthalten sind. Außerdem kann er ohne weitere Anfragen andere Seiten der Quelle mit betrachten. Araneus bietet also die Möglichkeit, interessante Daten unter anderen Gesichtspunkten zu betrachten, wobei nur ein Teil der Seiten wirklich neu erzeugt werden muß.

5.4 Strudel

Ein ähnliches System wie Araneus ist Strudel [FFK+98], das aus einer deklarativen Beschreibung der Struktur und des Inhalts einer zu erzeugenden Site (also mehrerer zusammengehöriger Seiten) automatisch HTML-Seiten erzeugt und sie mit Daten aus unterschiedlichen Quellen füllt. Dabei können die Daten sowohl aus externen Datenbanken oder Dateien stammen, als auch aus dem internen Repository von Strudel. Daten aus externen Quellen werden mit Wrappern geholt und im Strudel Repository gespeichert. Als Datenmodell für dieses Repository dient ein OEM-ähnliches Modell, also ein gerichteter, beschrifteter Graph.
Die Beschreibung der Seite erfolgt mit StruQL (Site Transformation Und Query Language), das folgende Syntax hat:
Die where - Zeile spezifiziert die Daten, die die neuen Seiten enthalten sollen, create, link und collect erzeugen einen Graphen, der auf dem vorhandenen Datengraphen basiert und die Struktur der Seiten beschreibt. Die folgende Anfrage (nach [FFK+98]) erzeugt einen Graphen TextOnly, der nur die Textobjekte eines Datengraphen enthält:

In der where-Zeile werden zuerst alle Objekte q bestimmt, die von der Wurzel p aus erreichbar sind (p->*->q), und danach alle Objekte q', die über genau eine Kante mit der Bezeichnung l von q aus erreichbar sind und keine Bilder sind.
Für p, alle q und alle q' werden mit New neue Objekt-IDs erzeugt. Danach werden zwischen allen Objekten q und q', die im ursprünglichen Graphen verbunden waren, Kanten eingefügt und zusätzlich eine neue Kante zur neuen Wurzel p.
Die collect-Zeile erzeugt eine Ausgabemenge, die die neue Wurzel p enthält.
Aus diesem Beschreibungsgraphen werden jetzt im HTML-Generator unter Verwendung einer HTML-Template-Bibliothek die neuen HTML-Seiten erzeugt.
Kapitel 4InhaltKapitel 6