Lexikon

Semistrukturierte Daten

Wie die meisten Forschungsgebiete der Informatik wurde die Datenbankforschung zuerst vorwiegend vom Paradigma einer zentralen Verwaltung geprägt.

Diese Sicht wurde zunehmend in Frage gestellt. Der Ansatz der semistrukturierten Daten seit Mitte der 90 er Jahre ist ein weiterer Schritt in diese Richtung. Ausgangspunkt war die Verwaltung von Inhalten im dezentralen WWW und die Datenmodellierungssprache XML. In den Ansatz „semistrukturierte Daten" führt das Buch von Abiteboul et al. ein.

Ein traditionelles Datenbanksystem setzt voraus, dass die gespeicherten Daten gemäß einem im Voraus festgelegten Datenschema strukturiert sind. Schemata erleichtern die Datenspeicherung und dienen der Anfrageauswertung. Im dezentral verwalteten WWW sind Schemata oft zu restriktiv. In vielen Bereichen wie in der Bioinformatik werden Daten in heterogenen Formaten zwischen Datenbanken oder sonstigen Anwendungen ausgetauscht, denen kein einheitliches Schema zugrunde liegt, weswegen solche Daten zunächst „unstrukturiert", danach „semistrukturiert" genannt wurden.

Oft haben zudem die Daten eine Struktur, die mit den flachen Tupeln des relationalen Datenmodells nur unzutreffend wiedergegeben werden kann. Auch das Objektmodell ist oft ungeeignet: Zwar kann man damit auch „tiefe" Strukturen repräsentieren, allerdings keine unregelmäßige Strukturen mit fehlenden oder wiederholten Komponenten. Fehlt das Schema, so muss zudem die Bedeutung der Struktur in den Datensätzen selbst wiedergegeben werden. Man spricht von „strukturtragenden" oder von „selbsterklärenden" Daten.

Ausgangspunkt XML

Die Datenmodellierungssprache XML eignet sich für die oben genannten Fälle: Mit XML können beliebig komplexe Datensätze spezifiziert werden; XML lässt Ausnahmen zu (in XML können alternative Strukturen spezifiziert werden und die spezifizierte Struktur darf sogar missachtet werden); XML-Datensätze, im XML-Jargon Dokumente genannt, sind strukturtragend.

Zum Beispiel kann eine Adresskartei wie folgt in XML spezifiziert werden:

 

Bartl Bastscho

Universität München

bartl@bastscho.net

 

Susi Schlau

Universität München

Fakultät für Mathematik und Informatik

susi@bastscho.net

www.bastscho.net/freunde/susi

 

Der zweite Datensatz hat eine reichere Struktur als der erste; in den beiden Datensätzen befindet sich die E-Mail-Adresse nicht auf derselben Tiefe.

In einer Anfrage an eine solche Adresskartei sollen nicht nur die Texte, Zahlen oder sonstige Daten ermittelt werden, die als Inhalte der innersten Elemente vorkommen, sondern auch die Elementnamen, wie „Name", „Einrichtung" oder „Kontakt". Schema- und Objektdaten sollen also in Anfragen nicht wie in traditionellen Anfragesprachen wie SQL unterschiedlich behandelt werden.

Wird in einer solchen Adresskartei nach einer E-Mail-Adresse für eine bestimmte Person gesucht, dann kann der Elementname „EMail" (oder irgendein Synonym dieses Elementnamens, welches eine sog. Ontologie liefern könnte) an beliebiger Tiefe gesucht werden. Eine Anfragesprache muss also über Sprachkonstrukte verfügen, die es ermöglichen, eine unbekannte Struktur oder eine unbestimmte Tiefe auszudrücken.

Datenmodelle für semistrukturierte Daten

Für semistrukturierte Daten wurden einige Modelle vorgeschlagen, die nur unwesentlich voneinander abweichen.

Im Object Exchange Model, kurz OEM, werden Datensätze Objekte genannt. Wie Objekte von Objektdatenbanken kann (muss aber nicht) ein OEM-Objekt eine sog. Objektidentität besitzen, so dass zwei OEM-Objekte, die denselben Wert haben, unterschiedlich sein können. Der Wert eines atomaren OEM-Objekts hat einen Typ wie etwa „integer", „string" oder „image". Ein zusammengesetztes OEM-Objekt besteht aus Attributen, die Werte besitzen, die wiederum OEM-Objekte sind. Die Attribute eines zusammengesetzten OEM-Objekts bilden entweder eine Menge oder eine Sequenz. OEM bietet eine weitreichende Typanpassung, um Unregelmäßigkeiten Rechnung zu tragen.

Ein OEM-Objekt kann als ein gerichteter Multigraph angesehen werden, dessen Knoten eindeutige Objektbezeichner sind und dessen Kanten die Attribute darstellen. Ein OEM-Objekt besitzt eine Wurzel, d.h. einen ausgezeichneten Knoten, von dem aus alle Knoten des OEM-Objektes erreichbar sind.

Der erste Adresskarteieintrag kann also wie folgt dargestellt werden, wobei „& n" Objektbezeichner sind:

Die Kanten stellen sowohl die Beziehung eines Elements zu einem Kindelement als auch etwaige Verweise wie (Hypertext- oder Nichthypertext-) Links dar. Ein OEM-Objekt entspricht nicht notwendigerweise einem Baum, d.h., OEM lässt zyklische Objekte zu. OEM-Objekte können HTML-Links oder einfache XML-Links darstellen, jedoch nicht die erweiterten XML-Links von XLink.

Das Datenmodell, das der Anfragesprache UnQL zugrunde liegt, ist OEM ähnlich. Er ist aber „wertbasiert", d.h., dass es keine Objektidentität kennt. Mit diesem Datenmodell ist die Verwendung der „Bisimulation" für semistrukturierte Daten eingeführt worden, die sich für die Anfrageauswertung als wichtig erwiesen hat. Eine Simulation eines Multigraphen G1 in einen Multigraphen G2 ist eine binäre Relation S zwischen den Knoten von G1 und G2 , die die Kanten von G1 auf Kanten von G2 abbildet. Eine Simulation S von G1 in G2 ist eine Bisimulation, falls S –1 eine Simulation von G2 in G1 ist. Für UnQL sind zwei semistrukturierte Objekte identisch, wenn sie bisimilar sind.

Das Datenmodell YAT bietet neben ähnlichen Merkmalen wie OEM und dem Datenmodell der Anfragesprache UnQL die „Modellinstanziierung". Damit können unter gewissen Umständen die Typen einer Datenmodellierung den Typen einer anderen Datenmodellierung angepasst werden. So können unterschiedliche Modellierungen von Anwendungen verglichen und Ergebnisse von Anfragen strukturiert werden.

Vergleich mit den relationalen und Objektmodellen

Eine Relation oder Tabelle kann als ein semistrukturiertes Objekt dargestellt werden, dessen Attribute die Tupel sind. Ein Tupel kann ebenfalls als ein semistrukturiertes Objekt dargestellt werden, dessen Attribute die Attributswerte des Tupels sind.

Diese Darstellung einer Relation ist ziemlich natürlich. Sie ist aber auch etwas trügerisch. Zum einen kann eine Relation auf viele andere Weisen als semistrukturiertes Objekt dargestellt werden. Zum anderen kann bei einer solchen Repräsentation ein Teil der Semantik verloren gehen, weil im Gegensatz zu einer relationalen Anfragesprache wie SQL die Anfragesprachen für semistrukturierte Daten alle Knoten gleich behandeln. So muss der Benutzer einer Anfragesprache für semistrukturierte Daten die Bedeutung der Verknüpfungen beachten.

Ein Datenmodell für semistrukturierte Daten kann als Vereinfachung eines Objektmodells angesehen werden, weil es in der Regel weder Klassen noch Vererbung anbietet. Der Verzicht auf Klassen und Vererbung ist jedoch fraglich. Die Modellinstanziierung von YAT entspricht der Vererbung.

Schemaextraktion

Traditionell stützen sich Anfrageauswertung und -optimierung auf Schemata. Um Anfragen über semistrukturierten Daten auszuwerten, bietet es sich also an, zuerst aus den vorhandenen Daten ein Schema zu extrahieren.

Viele WWW-Informationsserver liefern HTML-Seiten, die dynamisch aus einer Datenbank erzeugt werden. Es sind Methoden entwickelt worden, um aus solchen Seiten ein Schema zu erkennen, das evtl. nicht identisch mit dem Datenbankschema ist. Man spricht von „web site wrapping" und von „Schemaextraktion". Das extrahierte Schema wird manchmal „data guide" genannt. Eine Schemaextraktion ist eine Art Klassifikation von vorhandenen Datensätzen nach ihren Strukturen. Die meisten Methoden sind halbautomatisch und interaktiv und stützen sich auf Heuristiken.

Von Nestorov et al. wird ein auf Deduktion und Datalog beruhender Ansatz zur Schemaextraktion dargestellt, der zulässt, dass derselbe Datensatz mehreren Klassen zugeordnet wird und Approximationsschemata, denen nicht alle Datensätze entsprechen, liefert. Eine Metrik wird vorgeschlagen, womit die Qualität eines Approximationsschemas gemessen werden kann.

Anfragesprachen

Eine Anfragesprache ist wünschenswert zur Erstellung von dynamischen WWW-Seiten, die Inhalte teilen statt kopieren, um Sichten („views") zu erzeugen und um die Suche nach Inhalten zu erleichtern. Wünschenswerte Eigenschaften von Anfragesprachen für semistrukturierte Daten wurden von Maier ausgearbeitet.

Viele Anfragesprachen für semistrukturierte Daten oder „für das WWW" sind entwickelt worden – u.a. Lorel und XQuery. Einige sind von SQL und OQL inspiriert, andere sind im Zusammenhang mit XML entstanden. Vergleiche bieten Bonifati und Fernandez et al. an.

Die meisten Anfragesprachen verwenden Variablen, um Knoten – einige sowohl für Elementinhalte als auch für Elementnamen – zu bezeichnen. Reguläre Ausdrücke werden von vielen Anfragesprachen verwendet, um die Navigation im befragten Datensatz auszudrücken.

Mit dem Sternoperator kann z.B. ein Element an beliebiger Tiefe gefunden werden, mit dem Optionsoperator können Unregelmäßigkeiten der Datensatzstruktur berücksichtigt werden. Mit einer „Wildcard" kann eine Navigation entlang von unvollständig spezifizierten Pfaden definiert werden.

Zum Beispiel können im Stil von XML-QL wie folgt E-Mail-Adressen an beliebiger Tiefe (ausgedrückt durch die Wildcard $ gefolgt vom Sternoperator) gefunden werden, wobei $name und $email Variablen sind:

where < $* >

< Nachname > $name < /Nachname >

< EMail > $email < /EMail >

< /> in "www.yellowpages.net/ adresses.xml"

construct

< Antwort >

< Person >

< Name > $name < /Name >

< Mail > $email < /Mail >

< /Person >

< /Antwort >

Die meisten Anfragesprachen ermöglichen, die Antwort beliebig zu strukturieren. 

Einige Prototypen von Systemen zur „Verwaltung von Websites", d.h. zur Verwaltung von Inhalten, sind entwickelt worden, womit die ersten Anfragesprachen für semistrukturierte Daten entwickelt und getestet worden sind.

Literatur

  1. Bonifati, A., Ceri, S.: Comparative Analysis of Five XML Query Languages. Proc. ACM SIGMOD, Int. Conf. on Management of Data (2000)
  2. Bonifati, A., Lee, D.: Technical Survey of XML Schema and Query Languages. Proc. Int. Conf. on Very Large Databases (2001)
  3. Fernandez, M., et al.: XML Query Languages: Experiences and Exemplars. http:// cm.bell-labs.com/cm/cs/who/wadler/topics/xml.html
  4. Buneman, P., et al.: Programming Constructs for Unstructered Data. Proc. Int. Workshop on Database Programming Languages (DBPL) (1995)
  5. Abiteboul, S., et al.: Data on the Web – From Relations to Semistructured Data and XML. Hove: Morgan Kaufmann 2000
  6. Nestorov, S., et al.: Extracting Schema from Semistructured Data. Proc. ACM SIGMOD, Int. Conf. on Management of Data (1998)
  7. Maier, D.: Database Desiderata for an XML Query Language. Query Languages Workshop (1998); 
    www.w3.org/TandS/QL/QL98/pp/maier.html
  8. XML und XML-bezogene Formalismen: http://www.w3.org

Autor und Copyright

François Bry, Michael Kraus, Dan Olteanu, Sebastian Schaffert 
Institut für Informatik, 
Universität München, 
Oettingenstraße 67, 
D-80538 München; 
www.pms.informatik.uni-muenchen.de

© 2001 Informatik Spektrum, Springer-Verlag Berlin Heidelberg