6. Interaktive Suche in semistrukturierten Daten

Mit den in Abschnitt fünf beschriebenen Möglichkeiten, kann man Informationen aus dem Web abfragen. Man kann jedoch von einem normalen Nutzer nicht verlangen, die Syntax solcher Sprachen zu beherrschen. Vielmehr ist er daran gewöhnt, sich über eine Suchmaschine eine Liste von Seiten zu beschaffen, die eventuell passende Daten enthalten und diese dann weiter zu durchsuchen. Die Suche erfolgt also interaktiv. Da die meisten semistrukturierte Daten ihren Ursprung im Web haben, bietet sich hier eine interaktive Abfrage der Datenbank an. Lore, das Datenbanksystem für semistrukturierte Daten, bietet hierfür eine gute Grundlage, auf der Werkzeuge für eine interaktive Suche entwickelt wurden [GW98].

6.1 Ablauf der interaktiven Suche

Zur Erinnerung: Lore verwendet das graphbasierte OEM-Modell zur Modellierung der Daten und Data Guides zur Darstellung des Schemas ( vgl. Abschnitte 2.1 und 2.2.1).

Die interaktive Suche soll folgendermaßen ablaufen: Der Nutzer identifiziert zuerst über eine Schlüsselwortsuche, wie sie Suchmaschinen anbieten, die Kanten oder atomaren Objekte, die einen bestimmten Wert haben. Danach wird für jedes Ergebnis ein Data Guide über die unmittelbare Umgebung aufgebaut, den der Nutzer sich ansehen und anschließend seine Anfragen verfeinern kann, um genauere Ergebnisse zu erhalten.

Formal läßt sich eine Loresitzung über der ursprünglichen Datenbank D₀ mit der Wurzel r und dem ursprünglichen Data Guide G₀(r) als eine Folge von Anfragen q₁, q₂, ..., q_n beschreiben. Die Ergebnisobjekte einer Anfrage q_i sind über ein neu erzeugtes komplexes Objekt a_i erreichbar, dessen eingehende Kante mit Answer_i bezeichnet wird. Nach jeder Anfrage wird ein Data Guide G_i(ai) für den Ergebnisteilgraphen berechnet. Die Datenbank D ist nach der i-ten Anfrage auf D_i = D_i-1

a_i angewachsen, d. h. die Antwortobjekte werden einschließlich ihrer ausgehenden Kanten der Datenbank hinzugefügt.

Um diese Funktionalitäten zu realisieren, braucht man Algorithmen für die Schlüsselwortsuche und die Konstruktion sogenannter "fauler" Data Guides, die nur dann weiterberechnet werden, wenn der Nutzer diesen Teil der Datenbank tatsächlich besucht. Damit wird der Rechenaufwand, der zur Erstellung eines Data Guides notwendig ist, verringert. Ein weiteres Konstrukt, das für die Berechnung der Data Guides für eine Umgebung eingeführt wurde, sind Zeiger für die umgekehrte Kantenrichtung, da für eine Verfeinerung oft die Vorgängerknoten genauso wichtig sind wie die Nachfolger.

6.2 Beschreibung der Algorithmen

Der Algorithmus für die Suche lehnt sich an bekannte Verfahren aus dem Information Retrieval an. Er liefert eine geordnete Liste von Ergebnissen. Ein Unterschied liegt darin, daß in Frage kommende Werte als Bezeichner von Kanten und als atomare Objekte vorkommen können. Es sollten also sowohl die atomaren Objekte ausgegeben werden als auch die Objekte, die eine eingehende Kante mit dem gesuchten Wert haben. Um diese Suche effizient zu realisieren, wurden zwei Indizes in Form von verketteten Listen eingeführt. Der erste Index speichert zu Wörtern die atomaren Objekte, die diese Wörter enthalten, der zweite speichert zu den Wörtern die Kanten, deren Bezeichner die Wörter enthalten. Der erste Index bietet zusätzlich die Möglichkeit UND- oder ODER-Verknüpfungen zu bilden.

Ein Problem stellt sich, wenn ein Schlüsselwort mehrfach innerhalb eines Objekts oder in mehreren Objekten vorkommt. Bei mehreren Objekten zum gleichen Wort, möchte man natürlich benachbarte Objekte zusammenfassen. Als Abstand wird die Anzahl von Verbindungen genommen, die zwischen den Objekten liegen. Zum Zeitpunkt des Erscheinens des Artikels (März 1998) bot der Algorithmus dafür noch keine Lösung.

Der Aufbau eines Data Guide für die gesamte Datenbank kann sehr lange dauern und unter Umständen gar nicht zum Ende kommen (vgl. 2.2.2). Lange Wartezeiten sind bei einer interaktiven Abfrage unerwünscht, weshalb man in dem hier vorgestellten System zwei Lösungen kombiniert hat, um die Rechenzeiten zu verkürzen.
Eine Möglichkeit ist, in einer Hashtabelle abzulegen, welche Teile des kompletten Data Guides schon berechnet wurden. Wenn nun zum Ergebnis einer Suche der Data Guide konstruiert werden soll, schaut man in der Tabelle nach, welche Teile davon schon berechnet wurden, und erzeugt nur die neu, die dort keinen Eintrag haben.
Untersuchungen haben ergeben, daß die meisten Nutzer nur einen kleinen Teil des Data Guides wirklich nutzen. Deshalb wurde der Algorithmus zur Erzeugung des Data Guides von einem depth-first- in einen breadth-first-Algorithmus verwandelt, der zusätzlich die Teile nacheinander berechnet. Wenn ein Nutzer einen Teil des Data Guides betrachten will, der noch nicht berechnet wurde, wird dieser erst nach dem Klicken auf den Link erzeugt. Mit den oben beschriebenen Datenstrukturen läßt sich diese stückweise Berechnung leicht realisieren.

Die Data Guides für das Suchergebnis sollen nicht nur das Objekt sondern auch dessen Umgebung enthalten, da zum Beispiel der Data Guide für ein atomares Objekt leer ist. Das heißt, wenn der Nutzer sein Schlüsselwort so wählt, daß als Ergebnis ein oder mehrere atomare Objekte herauskommen, bekommt er einen leeren Data Guide, mit dem er seine Suche nicht mehr verfeinern kann.
OEM unterstützt nur Kanten vom Vorgänger zum Nachfolger. Um von einem atomaren Objekt die Umgebung zu erhalten, muß man in die umgekehrte Richtung gehen. Eine Lösungsmöglichkeit sieht so aus:
Wenn ein Objekt O eine eingehende Kante mit der Bezeichnung X hat, die von dem Objekt P kommt, führt man eine Kante von O nach P ein, die die Bezeichnung "X Of" hat. Damit wird P zum Nachfolger von O. Diese zusätzlichen Kanten kann man meistens als zusätzliche vorwärtsgerichtete Kanten betrachten.
In graphbasierten Modellen werden Objekte durch ihre eingehenden Kanten identifiziert. Dafür kann man diese Of-Kanten kaum verwenden, da zum Beispiel die Kante "Title-Of" nichts darüber aussagt, was das für ein Objekt ist, das einen bestimmten Titel hat. Es kann ein Buch, eine CD oder auch ein Mensch sein. Hier wurde der Algorithmus zur Erzeugung des Data Guide noch so abgeändert, daß er Objekte, die er über einenOf-Link erreicht, nicht durch diesen identifiziert sondern durch die eingehenden Kanten, die keine Of-Links sind. Das Ergebnis des Algorithmus wird als Panorama Data Guide bezeichnet.
Hier ist auch wichtig, daß der Algorithmus wie oben beschrieben Data Guides Stück für Stück erzeugt, da durch die Of-Links viele zusätliche Kanten eingeführt werden, die bei der Erstellung berücksichtigt werden müssen.

Zusammenfassung

Das Ziel aller Ansätze zum Umgang mit semistrukturierten Daten ist es, sie so einfach handhaben zu können wie Daten in einem relationalen DBS. Dazu muß man zuerst ihre Struktur analysieren, um daraus ein Modell und ein Schema erstellen zu können. Wenn man die Daten so modelliert hat, möchte man sie mit geeigneten Sprachen abfragen und dann eventuell in existierende relationale oder objektorientierte Datenbanken integrieren.
Nicht alle vorgestellten Systeme können alles, einige sind nur für Anfragen nicht aber zum Speichern von semistrukturierten Daten gemacht.
Die vollständigsten Systeme sind Lore und Araneus. Sie haben beide ein eigenes Datenmodell, mit dem semistrukturierte Daten beschrieben werden können, und speichern ihre Daten in einer Datenbank. Araneus erzeugt dafür Relationen und speichert alle Daten lokal. Lore bietet mit externen Objekten zusätzlich die Möglichkeit, die Daten nur bei Bedarf von ihren Quellen abzufragen.
Die Abfrage erfolgt bei Lore über die OQL-ähnliche Abfragesprache Lorel und erzeugt Ergebnismengen. Bei Araneus werden die Ergebnisse einer Anfrage als HTML-Seite dargestellt, die eventuell auch schon bestehende Seiten über Links einbindet.
Araneus ist also mehr auf die WWW-Anbindung zugeschnitten: ADM berücksichtigt Konstrukte, die oft in HTML-Seiten vorkommen, und stellt Ergebnisse wieder als Seiten dar.
Lore dagegen ist für alle möglichen Arten von semistrukturierten Daten gemacht. Diese müssen nicht aus dem WWW stammen, sondern können einfach in anderen Datenbanken liegen. Darüberhinaus bietet Lore mit den Data Guides die Möglichkeit, das Schema der Daten darzustellen. So etwas fehlt in Araneus.
Strudel hat ebenfalls ein eigenes Datenmodell und kann Daten aus unterschiedlichen Quellen in sein internes Repository integrieren. Das System wurde aber hauptsächlich entwickelt, um aus bestehenden Datenbeständen automatisch HTML-Seiten zu erstellen. Die WWW-Anbindung besteht hier also nicht darin, daß man Daten aus dem Web abfragt, sondern darin, Daten für das WWW bereitzustellen.
Die vorgestellten Wrapper dienen nur zur Abfrage von Daten, die als HTML-Seiten vorliegen. Für eine Speicherung und Weiterverarbeitung müssen sie mit anderen Systemen gekoppelt werden.
Es gibt also für alle Teilbereiche schon Lösungen, die aber oft noch nicht voll automatisiert sind. Vor allem bei der Strukturanalyse, die die Grundlage für alle weiteren Schritte wie Abfrage und Integration bildet, ist oft noch eine Interaktion mit dem Nutzer nötig, da nicht alle Daten gleich stark strukturiert sind.
Auch die ständigen Veränderungen und Erweiterungen vor allem im WWW machen eine optimale Lösung aller Teilaspekte schwierig. Aber mit den vorgestellten Systemen werden zumindest akzeptable Lösungen angeboten, wobei Lore das allgemeinste System mit den meisten Möglichkeiten ist.

Literaturverzeichnis:

[Ab97]	Abiteboul, S.: Querying Semi-Structured Data. ICDT, 1997
[AK97]	Ashish, N., Knoblock, C. A.: Wrapper Generation for Semi-structured Internet Sources. ACM SIGMOD Record 26(4), 1997
[AM97]	Atzeni, P., Mecca, G.: Cut and Paste. In Sixteenth ACM SIGMOD Intern. Symposium on Principles of Database Systems (PODS'97), Tuscon, Arizona, 1997. http://poincare.inf.uniroma3.it:8080/Araneus/publications.html
[AMM97]	Atzeni, P., Mecca, G., Merialdo, P.: Semistructured and Structured Data in the Web: Going Back and Forth. In Sigmod Record, Special Issue on the Workshop on the Management of Semistructured Data, 1997
[FFK+98]	Fernández, M., Florescu, D., Kang, J., Levy, A., Suciu, D.: Catching the Boat with Strudel: Experiences with a Web-Site Management System, 1998
[GW98]	Goldman, R., Widom, J.: Interactive Query and Search in Semistructured Databases. Proceedings of the First International Workshop on the Web and Databases (WebDB '98), Lecture Notes in Computer Science 1590, pages 52-62, Springer-Verlag, Berlin, March 1998
[GW99]	Goldman, R., Widom, J.: Approximate DataGuides. Proceedings of the Workshop on Query Processing for Semistructured Data and Non-Standard Data Formats, Jerusalem, Israel, January 1999
[MAG+97]	McHugh, J., Abiteboul, S., Goldman, R., Quass, D., Widom, J.: Lore: A Database Management System for Semistructured Data. SIGMOD Record, 26(3):54-66, September 1997
[MW97]	McHugh, J., Widom, J.: Integrating Dynamically-Fetched External Information into a DBMS for Semistructured Data. SIGMOD Record, 26(4):24-31, December 1997. Also appeared in Proceedings of the Workshop on Management of Semistructured Data, pages 75-82, Tucson, Arizona, May 1997
[NAM97]	Nestorov, S., Abiteboul, S., Motwani, R.: Inferring Structure in Semistructured Data, International workshop on management of semistructured data, 1997
[Su97]	Suciu, D.: Management of Semistructured Data. ACM SIGMOD Record 26(4), 1997.
[Su98]	Suciu, D.: An Overview of Semistructured Data. SIGACT News 29(4), 1998.

Kapitel 5

Inhalt