3. Ableiten der Struktur semistrukturierter Daten
Semistrukturierte Daten sind dadurch gekennzeichnet, daß ihre Struktur nicht immer sofort offensichtlich ist und sie nicht stark typisiert sind. Wenn man solche Daten speichern oder abfragen will, muß man aber ihre Struktur zumindest bis zu einem gewissen Grad kennen. Im folgenden wird zuerst der Algorithmus zur Erzeugung eines Data Guides beschrieben. Danach werden zwei Ansätze vorgestellt, die versuchen, Struktur und Typisierung semistrukturierter Daten abzuleiten. Das erste Verfahren [NAM97] geht dabei von Daten aus, die als OEM-Graph vorliegen, und erzeugt für diese eine Typhierarchie. Bei der zweiten Methode [AK97] werden HTML-Seiten analysiert und ihre Struktur in einer Baumstruktur festgehalten.
3.1 Algorithmus zur Erzeugung eines exakten Data Guides
Der Algorithmus bestimmt zuerst für jeden Pfad in der OEM-Repräsentation der Datenbank die Menge von Objekten, die über diesen Pfad erreicht werden. Diese Mengen werden als Zielmengen bezeichnet.
Jede unterschiedliche Zielmenge wird im Data Guide durch einen Knoten dargestellt und der dazugehörige Pfad, über den sie erreicht wird, als eingehende Kante. Jeder Knoten im Data Guide hat so viele eingehende Kanten wie es in der Datenbank Pfade mit der Zielmenge gibt, die der Knoten repräsentiert.
Um die Zielmengen zu generieren, wird der Datenbankgraph depth-first durchlaufen. Für jeden dabei gegangenen Pfad wird eine Zielmenge erzeugt und in einer Hash-Tabelle abgelegt. Bei jeder neuen Menge wird in der Hash-Tabelle nachgeschaut, ob diese schon existiert. Wenn ja, wird im Data Guide eine Kante zu dem die Zielmenge repräsentierenden Objekt eingefügt. Wenn nein, wird ein neues Data Guide Objekt angelegt und an dem entsprechenden Pfad in den Data Guide eingefügt. Die neue Zielmenge wird in der Hash-Tabelle abgelegt.
3.2 Ein graphbasierter Ansatz
3.2.1 Definitionen
Ausgehend von einer als OEM-Graph modellierten Datenbank D werden folgende Begriffe definiert:
Sei o ein Objekt, also ein Knoten in D. Dann ist attributes(o) die Menge der Bezeichner der von o ausgehenden Kanten und roles(o) die Menge der Bezeichner der in o eingehenden Kanten.
S sei eine Menge von Bezeichnern, D die Datenbank. Dann gilt:
at(S) ist die Anzahl von Objekten in D, für die gilt attributes(o)=S;
above(S) ist die Anzahl von Objekten in D, für die gilt attributes(o) 
S.
Da alle Objekte, die für at(S) gezählt werden, auch für above(S) mitgezählt werden, ist above(S) immer größer oder gleich at(S) und beide sind immer größer oder gleich 0.
Zusätzlich wird noch eine Funktion jump(S) = at(S)/above(S) definiert, die genau dann 0 ist, wenn at(S)=0 ist. Wegen der obigen Beziehung zwischen at(S) und above(S) liegt jump(S) per Definition immer zwischen 0 und 1.
3.2.2 Der Algorithmus
Der vorgeschlagene Algorithmus versucht Typen zu finden, die die Objekte in der Datenbank repräsentieren können, wobei die Typen so gewählt werden, daß zum einen möglichst viele Objekte den gleichen Typ haben und zum anderen die Objekte so genau wie möglich beschrieben werden.
Dazu werden zuerst Kandidaten für Typen gesucht, dann die Typen daraus ausgewählt und eine Typhierarchie angelegt. Danach werden die Regeln abgeleitet, nach denen die Objekte den einzelnen Typen zugewiesen werden. Zum Schluß wird die gefundene Hierarchie gegen die vorhandenen Daten getestet.
Um die Kandidaten zu finden, werden zuerst alle unterschiedlichen Mengen attributes(o) bestimmt und für diese dann jeweils die at- und die above-Werte bestimmt. Um die unterschiedlichen Mengen und die at-Werte zu bestimmen, muß man die Datenmenge D nur jeweils einmal durchlaufen und die above-Werte lassen sich in O(n2)berechnen, wobei n die Anzahl der von null verschiedenen at-Werte ist.
Die Mengen werden mit ihren at-Werten in einem Verband so angeordnet (die Zahlen entsprechen den at-Werten):
Abb. 6: Die Mengen attributes(o) mit ihren at-Werten
Der above-Wert ist für die Menge A, B, C gleich dem at-Wert und für die Menge A, B ist er gleich 50+10+20+100+200 = 380.
Jetzt werden alle die Mengen K bestimmt, für die jump(K) über einem bestimmten, vorher festgelegten Grenzwert g liegt. Diese Mengen sind Typkandidaten. Um eventuell weitere Kandidaten zu finden, werden die at-Werte der Mengen, die im Gitter nicht oberhalb eines schon gefundenen Kandidaten liegen, erhöht, indem die at-Werte der direkten Vorgänger dazuaddiert werden. Dann wird erneut die jump-Funktion berechnet.
Im zweiten Schritt wird aus den Kandidaten eine Typhierarchie aufgebaut. Dazu wird die Menge roles(o) mitbenutzt. Jeder Typkandidat entspricht einer Menge von Objekten. Für diese Objekte wird jetzt derjenige Attributbezeichner bestimmt, der am häufigsten in den Mengen roles(o) vorkommt. Dieser Bezeichner wird als primäre Rolle oder p-role(K) des Typkandidaten K bezeichnet. Ein Kandidat K wird dann endgültig zum Typ, wenn kein anderer Kandidat K' existiert, so daß K' 
K ist und p-role(K) = p-role(K'). Das heißt, daß die minimale Menge von Attributen ausgewählt wird, die nötig sind, um einen Typ eindeutig zu beschreiben.
Als nächstes werden die Objekte o der Datenmenge den Typen K1, ..., Kn so zugewiesen, daß Ki der Typ mit dem geringsten Abstand zu o ist. Als einfaches Abstandsmaß kann man z. B. die Kardinalitäten der Mengendifferenzen attributes(o) - Ki und Ki - attributes(o) verwenden.
Abschließend wird die gefundene Typisierung mit den Daten verglichen. Zur Bewertung, wie gut oder schlecht eine Typisierung ist, kann man die Anzahl von Typen, die Korrektheit und Exaktheit der Typisierung betrachten.
Der Erfolg des Algorithmus hängt entscheidend von dem Grenzwert g ab, der in Schritt 1 verwendet wird. Ist g zu groß, erhält man nur wenige Typen, also wird die Beschreibung der Objekte durch ihren Typ sehr ungenau. Wählt man g zu klein, erhält man eine genauere Beschreibung der Objekte durch den jeweiligen Typ, aber zu viele unterschiedliche Typen. Ein Extrem wäre g = 0. Dann werden nur zwei Objekte demselben Typ zugeordnet, die sich nicht unterscheiden.
Wenn man also mit dem Ergebnis nicht zufrieden ist, muß man einen anderen Wert für g wählen und den Algorithmus erneut laufen lassen. In die Bestimmung von g können dabei z. B. die Datenbankgröße, die Menge von erwünschten Typen oder die Anzahl unterschiedlicher Kantenbezeichner eingehen.
3.3 Analyse von HTML-Seiten
Eine HTML-Seite besteht oft aus mehreren Abschnitten, wobei einige davon anderen untergeordnet sein können. Bei dem Ansatz, wie er in [AK97] beschrieben ist, wird versucht, aus dem Quelltext diese Struktur herauszufiltern.
Ein Beispiel für eine Site, die sich für dieses Vorgehen eignet, ist das CIA World Fact Book.
Ein Ausschnitt aus der Seite für Frankreich:
France
Geography
Location: Western Europe, bordering the Bay of Biscay and Englisch Channel, between Belgium and Spain southeast of the UK; bordering the Mediterranean Sea, between Italy and Spain
Map references: Europe
Der Beginn eines neuen Abschnitts ist meist durch bestimmte Wörter oder Phrasen in einem besonderen Format (z. B. das Heading-Tag) gekennzeichnet. Diese Tokens kann man mittels lexikalischer Analyse aus dem HTML-Quelltext herausfiltern. Das geht deshalb, weil in HTML die Formatierungen als Anfangs- und Endtag den zu formatierenden Text einschließen.
Wenn man die Tokens bestimmt hat, die neue Abschnitte einleiten, muß man noch herausfinden, ob diese Abschnitte alle auf einer Ebene liegen oder ob sie verschachtelt sind. Das Verfahren dafür beruht auf zwei Heuristiken:
Die Überschriften von Unterabschnitten haben normalerweise eine kleinere Schrift, als die Überschrift des übergeordneten Abschnitts.
Unterabschnitte werden durch Einrückungen gekennzeichnet, die im HTML-Code entweder direkt als solche eingegeben werden, oder durch Tags angegeben sind.
Der Algorithmus baut nun zuerst einen Baum auf, indem er für jedes Token, das einen neuen Absatz kennzeichnet, einen Knoten erzeugt und den Knoten zum Vater des neuen macht, der aufgrund der Schriftgröße und der Einrückung den unmittelbaren übergeordneten Absatz im Text repräsentiert. Die Kinder jedes Knoten werden entsprechend der Reihenfolge der Abschnitte im Originaltext sortiert.
Da der Algorithmus auf Heuristiken beruht, können Tokens fälschlicherweise ausgewählt oder übersehen werden. Über eine grafische Schnittstelle kann man dem Nutzer die Möglichkeit geben, die Liste der Tokens zu korrigieren, bevor die Struktur der Seite weiter analysiert wird.