2. Datenmodelle und Schemata für semistrukturierte Daten

2.1 Datenmodelle

Semistrukturierte Daten entstehen dadurch, daß Daten aus verschiedenen Quellen gemeinsam in einer Datenbank abgelegt werden sollen. Das Datenmodell, das diese Daten beschreiben soll, muß also die Fähigkeit haben, Daten mit den unterschiedlichsten Strukturen zu beschreiben. Andererseits soll es aber auch in der Lage sein, vorhandene Strukturen zu erkennen und zu nutzen. Wenn z. B. Tabellen aus einer relationalen Datenbank importiert werden, wäre es oft unsinnig, die Tabellenstruktur völlig zu vernachlässigen und die Daten etwa als Text zu organisieren.
Diese Flexibilität bieten das Object Exchange Model (OEM) oder das Modell, das für die Abfragesprache UnQL verwendet wird. Einen anderen Ansatz bietet das Araneus Data Model (ADM), das für das Araneusprojekt [AMM97] entwickelt wurde. Im folgenden sollen diese Modelle vorgestellt werden.

2.1.1 OEM - Object Exchange Model

Das OEM Modell ist nach [Su98] das bekannteste unter den Datenmodellen für semistrukturierte Daten. Ursprünglich wurde es für das Tsimmis (The Stanford-IBM Manager of Multiple Information Sources) Projekt entwickelt.
Die Daten werden als gerichteter Graph dargestellt, wobei die einzelnen Knoten die Objekte darstellen und die von einem Knoten ausgehenden Kanten die Attribute dieses Objekts. Der gesamte Datenbestand kann also als eine Ansammlung von Objekten betrachtet werden.
Man unterscheidet zwischen atomaren und komplexen Objekten. Atomare Objekte sind vom Typ Integer, String, Bild, oder ähnliches. Sie stellen die Blätter des Graphen dar.
Komplexe Objekte bestehen aus einer Menge von Paaren der Gestalt (Attribut, Objekt). Im Graphen entspricht éAttribut' einer vom aktuellen Objekt ausgehenden Kante und éObjekt' dem Knoten, zu dem die Kante führt. Jedes Objekt hat eine eindeutige ID.
Der Graph hat mindestens eine Wurzel. Das ist ein ausgezeichnetes Objekt, von dem aus alle anderen Objekte erreichbar sind. Es können auch mehrere Wurzeln existieren. Dann sind von jeder aus alle Knoten des Graphs erreichbar.

Formal lassen sich semistrukturierte Daten also als G=(V, E, r1, ..., rk, v) definieren mit:
V = Vc Va die Menge der Knoten, wobei Vc die Menge der komplexen Objekte und Va die Menge der atomaren Objekte ist;
E Vc A V die Menge der Kanten, wobei A die Menge aller Attribute ist;
ri die Menge der Wurzeln;
v: Va D eine Abbildung, die atomaren Objekten Werte aus D, der Menge aller atomaren Werte, zuweist.

Beispiel (nach [MAG+97]):


Abb. 1: Ein OEM-Graph


Erläuterungen:
Die Objekte &5, &6, &7, &9 und &10 sind atomare Objekte, &1 ist die Wurzel und gleichzeitig ein komplexes Objekt, ebenso wie &2, &3 und &8. "Projekt", "Mitarbeiter", "Titel", "Name", "Alter", "Büro", "Gebäude" und "Zimmer" bilden die Menge der Attribute.

In Textform läßt sich der Graph so beschreiben:

Eine solche Beschreibung kann zum Beispiel in Lore benutzt werden, um Daten in die Datenbank zu laden.

Es gibt in diesem Modell zwei Arten von Gleichheit: flache und tiefe Gleichheit, ähnlich wie in objektorientierten Systemen.
Für zwei Objekte ist flache Gleichheit dann erfüllt, wenn die beiden dasselbe Objekt darstellen. Tiefe Gleichheit liegt dann vor, wenn die zwei Teilgraphen, die von den Objekten aus erreichbar sind, isomorph sind.
G1 = {a:{b:1, c:2}, a: {b:1, c:2}} und G2 = {a: {b:1, c:2}} sind hier in keinem Fall gleich .

Zur Verdeutlichung:
G1: G2:

Abb. 2: Gleichheit im OEM-Modell


G1 und G2 sind nicht identisch, also kann es sich nicht um das gleiche Objekt handeln. Flache Gleichheit ist nicht gegeben.
Von &1 aus erreicht man in G1 &2 und &3, in G2 nur &2. Im OEM-Modell hat jedes Objekt eine eindeutige ID. In G1 können &2 und &3 also nicht identifiziert werden, obwohl sie die gleichen Attribute mit den gleichen Werten haben.
Man erreicht also in G1 von &1 aus mehr Objekte als in G2. Deshalb sind die Teilgraphen nicht isomorph und somit ist auch die tiefe Gleichheit nicht erfüllt.
Für die beiden Objekte &2 und &3 in G1 ist die tiefe Gleichheit gegeben, da die beiden Untergraphen isomorph sind.

2.1.2 UnQL Datenmodell

UnQL (Unstructured Query Language) [Su98] ist eine Abfragesprache für semistrukturierte Daten. Das zugrundeliegende Datenmodell entspricht im Wesentlichen dem OEM-Modell, d. h. die Daten werden als gerichteter Graph dargestellt. Einzige Ausnahme ist die Definition der Gleichheit.
In diesem Modell sind zwei Graphen G, G' gleich, wenn sie bisimilar sind. Das bedeutet G und G' sind gleich, wenn sie sich durch eine Transformation ineinander überführen lassen. Bei der Transformation wird der Graph von der Wurzel aus entfaltet und an jedem Knoten werden Duplikate eliminiert. Auf das obige Beispiel bezogen heißt das, daß in G1 &2 und &3 das gleiche Objekt darstellen und eines entfernt werden kann. G1 ist dann isomorph zu G2 und die tiefe Gleichheit ist erfüllt.

2.1.3 ADM - Araneus Data Model

Das Araneus-System (araneus - lat. Spinne) [AMM97] wurde entwickelt, um Webseiten in eine Datenbank zu integrieren und aus einer Datenbank Webseiten zu generieren. Also ist das Datenmodell auf Webseiten zugeschnitten.
ADM basiert auf dem ODMG-Modell, das Objekte mit bestimmten Eigenschaften und einem bestimmten Verhalten definiert. Die Hauptkomponenten von ADM sind Objekte mit Attributen. Dabei entspricht jede Webseite einem Objekt mit einer eindeutigen ID (der URL) und einer Menge von Attributen, die einfach oder komplex sein können.
Einfache Attribute sind einwertig und modellieren Text, Bilder oder Links zu anderen Seiten.
Komplexe oder mehrwertige Attribute dienen dazu, die Gruppierungen, die in Webseiten vorhanden sein können, zu modellieren. Beispielsweise kann bei einer Seite, die die Veröffentlichungen eines Autors enthält, die Menge der Veröffentlichung (optisch) zusammengefaßt sein. Im Datenmodell wird dieses mehrwertige Attribut (éMenge der Veröffentlichungen') des Objekts Webseite durch eine Liste von Tupeln dargestellt, wobei jedes Tupel einer Veröffentlichung entspricht. Jedes Tupel kann dabei wieder eine Liste sein, wodurch man geschachtelte Listen erhält. Listen sind die einzigen mehrwertigen Attribute im ADM-Modell.

Darüberhinaus hat ADM einige Besonderheiten.
Die erste ist der Datentyp Formular. Webseiten enthalten oft Formulare, die eine Ausführung von Programmen auf einem Server oder die Generierung neuer Seiten anstoßen, wenn man die Felder ausgefüllt und einen Button gedrückt hat. Der Typ Formular entspricht einer virtuellen Liste von Tupeln, von denen jedes soviele Attribute hat wie Felder im Formular enthalten sind und zusätzlich noch einen Link auf die Seite, die das Ergebnis liefert. Jedes Tupel entspricht also einem ausgefüllten Formular. Virtuell ist die Liste deshalb, weil die Werte im Formular nicht auf der Page gespeichert sondern nur übermittelt werden, um eine Ergebnisseite zu erzeugen.
Die zweite Besonderheit ist, daß man Attribute als optional deklarieren kann, um die Eigenschaft semistrukturierter Daten zu modellieren, daß Attribute bei manchen Objekten vorhanden sind und bei anderen fehlen.

Die Grundform jeder Seite, die so nur einmal pro Site vorkommt, wird mit einem Seitenschema modelliert, das die Struktur enthält. Zum Beispiel könnten die verschiedenen Typen von Ergebnisseiten einer Suchanfrage (die Seiten enthalten entweder Ergebnisse oder weitere Auswahlmöglichkeiten) je ein Seitenschema bilden. Von diesen gibt es dann unterschiedliche Instanzen. Wenn zum Beispiel nach Autoren gesucht wird, kann entweder eine Auswahlseite mit allen passenden Autoren erstellt werden, oder es wird für jeden Autor, der die Suchkriterien erfüllt, eine Seite angelegt. Es gibt aber auch Seitenschemata, die einzigartig für diese Site sind und von denen es nur eine Instanz gibt. Eine solche wäre zum Beispiel, die index.html-Seite.
Um von einem Formular nicht zu jedem resultierenden Seitenschema einen Link setzen zu müssen, faßt man die möglichen Seitenschemata in einem sogenannten Uniontyp zusammen und modelliert dann nur einen Link zu dieser Union.

Abschließend kann man die einzelnen Seitenschemata einer Site und alle Links zwischen ihnen in einem Schema zusammenfassen. Diese Schema ist ein gerichteter Graph, bei dem jedes Seitenschema einem Knoten und jeder Link einer Kante entspricht. Seitenschemata, die nur einmal vorkommen, werden als einzelne Seite gezeichnet und diejenigen, die in mehrfacher Ausprägung existieren können, als Stapel.

Als Beispiel (nach [AMM97]) soll eine Datenquelle modelliert werden, die Autoren, Veröffentlichungen und Informationen über Konferenzen enthält (dblp.uni-trier.de). über ein Formular kann nach bestimmten Autoren gesucht werden. Man erhält dann eine Liste mit den Veröffentlichungen, die eventuell Verweise auf Konferenzen enthält, die mit der jeweiligen Veröffentlichung in Zusammenhang stehen.

Abb. 3: ADM-Modell

2.2 Das Schema semistrukturierter Daten

Das Schema, das die Struktur der Daten beschreibt, kann häufig nicht vorher definiert werden wie bei einer herkömmlichen Datenbank, sondern erst dann, wenn man die Datenbestände vorliegen hat. Das hat verschiedene Ursachen.
Semistrukturierte Daten sind sehr flexible Daten, die sich häufig ändern. Also muß auch das Schema variabel sein, um diese änderungen aufzunehmen und zu repräsentieren.
Da man oft auch große Datenmengen mit irregulärer Struktur hat, bekommt man häufig ein sehr umfangreiches Schema, das nicht sehr viel kleiner ist als die Datenmenge.
Bei relationalen Datenbanksystemen ist es so, daß der Nutzer das Schema kennt und es zugrunde legt, um seine Anfragen zu formulieren. Bei großen, sich schnell verändernden Schemata kann man nicht verlangen, daß er das gesamte Schema kennt. Also sollte es eine Möglichkeit geben, dieses abzufragen.
Ein herkömmliches Schema, wie man es von relationalen oder objektorientierten Datenbanken kennt, ist hier kaum von Nutzen. Eine Lösung sind Data Guides, wie sie in Lore [MAG+97] verwendet werden.

2.2.1 Data Guides

Ein Data Guide ist eine kurze und exakte übersicht der Struktur einer Datenbank mit semistrukturierten Daten. Angenommen man verwendet OEM zur Modellierung der Daten. Dann läßt sich ein Data Guide formal als ein OEM Graph G definieren, der eine mit OEM modellierte Datenbank D abstrahiert, wobei jeder unterschiedliche Pfad in D genau einmal in G vorkommt und es zu jedem Pfad in G mindestens einen entsprechenden Pfad in D gibt. Die Pfade müssen dabei immer von der Wurzel des entsprechenden Graphen ausgehen. Sie identifizieren die Rolle des Objekts, zu dem sie führen, in der Datenbank.
Ein Data Guide kann vielfältige Informationen aufnehmen.
Er kann durchsucht und abgefragt werden und bietet so dem Nutzer die Möglichkeit, sich über die Struktur der Daten zu informieren. Gleichzeitig kann dieser, wenn der Data Guide mit einem entsprechenden Interface versehen ist (wie z. B. bei Lore), beim Durchsuchen Anfragen formulieren, indem er Bedingungen für Objekte angibt. Diese werden dann automatisch in eine Lorel-Anfrage umgesetzt und an die Datenbank geschickt. Der Anwender muß also die Anfragesprache nicht beherrschen.
Man kann statistische Informationen über die Größe der Datenbank speichern, die von einem Queryoptimizer genutzt werden, oder den Data Guide als Index verwenden, um die Abarbeitung von Anfragen zu beschleunigen.
Die Pfade in einer Anfrage können vor der Bearbeitung überprüft werden, ob sie überhaupt existieren, und reguläre Pfadausdrücke können schon beim Kompilieren expandiert werden.
Beispiel für eine OEM-Datenbank (links) und den dazugehörigen Data Guide (nach [GW99]):

Abb. 4: DB und Data-Guide


2.2.2 Approximierte Data Guides

Diese vielfältigen Vorteile kann man nur nutzen, wenn man den vollständigen Data Guide für eine Datenbank berechnet hat. Das kann bei großen, zyklischen Datenmengen sehr lange dauern und, wie Versuche gezeigt haben [GW99], manchmal auch gar nicht zum Ende kommen, weil die Ressourcen vorher erschöpft sind.
Einen Ausweg bieten approximierte Data Guides [GW99]. Dabei werden während der Konstruktion ähnliche Teile des Data Guides herausgesucht und dann miteinander verschmolzen, indem zum Beispiel von zwei Objekten, bei denen die eingehende Kanten gleich sind, eines gelöscht wird.
Für die Abschätzung der ähnlichkeit gibt es zwei Strategien:

  • Object Matching: Zwei Pfade sind ähnlich, wenn die Mengen der Objekte, die über diese beiden Pfade erreicht werden können, ähnlich sind. ähnlich sind zwei Mengen, wenn ihr Durchschnitt mindestens k Objekte enthält.
  • Role Matching: Hier wird nur betrachtet, ob zwei Pfade ähnlich sind. Die Objekte, die darüber erreicht werden, spielen keine Rolle. Zwei Pfade sind im obigen Data Guide zum Beispiel ähnlich, wenn beide als letztes Attribut Name enthalten.

    Approximierte Data Guides können Pfade enthalten, die in der originalen Datenbank nicht vorkommen, aber sie repräsentieren immer alle wirklich enthaltenen Pfade. Also bieten auch sie alle Möglichkeiten eines genauen Data Guides bis auf die Verwendung als Pfadindex bei der Anfragebearbeitung (fehlende Exaktheit durch zusätzliche Pfade). Die einzigen Nachteile sind, daß man eventuell mit Obermengen der wirklichen Objekte arbeiten muß, was die Effizienz verringern kann, und daß der Nutzer Pfade sieht, die gar nicht existieren.

    Der approximierte Data Guide zur obigen Datenbank sieht so aus [GW99]:

    Abb. 5: Approximierter Data Guide
    Kapitel 1InhaltKapitel 3