Data Warehouse

• Erläuterung
• Literatur
• Autor & Copyright
   

Erläuterung

Besonders heftig wird derzeit im Umfeld der Management Support Systeme über das Thema Data Warehouse diskutiert. Dabei ist unter einem Data Warehouse eine Systemlösung zu verstehen, die die unternehmensweite Versorgung der Front-End-Systeme zur Managementunterstützung mit den benötigten Informationen zu gewährleisten hat [7]. Zweckmäßigerweise wird das Data Warehouse getrennt von den operativen Vorsystemen aufgebaut und betrieben. Nur so läßt sich eine konsistente unternehmensweite Datenbasis etablieren, in die selektierte und verdichtete Informationen anwendungsgerecht aufbereitet einfließen und auf die interaktiv und intuitiv zugegriffen werden kann. Für die gespeicherten Dateninhalte ist deren thematische Ausrichtung sowie Vereinheitlichung, Dauerhaftigkeit und Zeitorientierung charakteristisch [4].

Unternehmensweite Data Warehouse-Lösungen weisen unterschiedliche (Software-) Komponenten auf, deren reibungsloses Zusammenwirken als ein zentrales Erfolgskriterium zu werten ist. In Abb. 1 wird die logische Anordnung der einzelnen Komponenten unter Architekturgesichtspunkten versinnbildlicht.

Als Kernkomponente einer Data Warehouse-Architektur ist der zentrale Datenspeicher zu verstehen, der heute i.d.R. durch eine relationale Datenbank gebildet wird. Verschiedene funktionale Erweiterungen der marktgängigen relationalen Datenbanken (so z.B. spezielle Indizierungsverfahren [Bit-Indexing] oder Abfragetechniken [Star-Joins]) tragen dazu bei, daß die spezifischen Anforderungen, die aus den Managementapplikationen erwachsen, auch bei großen Datenmengen erfüllt werden können [1, 3].

Zugunsten der erforderlichen Zugriffsperformance wird darüber hinaus häufig auf eine konsequente Normalisierung – wie bei operativen Systemen üblich – verzichtet. Vielmehr erfolgt der Aufbau denormalisierter Datenmodelle, die als Star-Schema bezeichnet werden und aus Fakten- und Dimensionstabellen bestehen [3, 9]. Die Faktentabellen beinhalten die betriebswirtschaftlich relevanten und durch mehrere sachliche Identifikationskriterien bzw. Dimensionen (wie Region, Kunde oder Artikel) beschriebenen numerischen Meßgrößen. Dagegen speichern Dimensionstabellen, die mindestens eine Attributspalte mit den zugehörigen Faktentabellen teilen, weitere Angaben zu den Dimensionselementen (wie Artikelnummer, Artikelbezeichnung oder Artikelgruppe). Im Fact-Constellation-Schema und im Snowflake-Schema, die als Varianten des Star-Schemas zu bezeichnen sind, wird eine Aufgliederung von Fakten- und Dimensionstabellen in unterschiedliche Teilaggregate vorgenommen, um hieraus weitere Performancevorteile zu aktivieren und unnötige Redundanzen zu eliminieren [8].

Ein hoher Anteil des Aufwandes beim Aufbau eines Data Warehouses resultiert aus der Etablierung von Zugriffsstrategien auf die operativen Datenhaltungseinrichtungen. Die hier eingesetzten Import-Komponenten leisten automatische, zeitgesteuerte Aktualisierungen der Data Warehouse-Datenbasis in belastungsarmen Zeiten und führen dabei vielfältige Transformationen und Aufbereitungen der einzubindenden Daten durch.

Insbesondere beim interaktiven Zugriff auf die Datenbasis kann sich ein unternehmensweites Data Warehouse als zu unflexibel und schwerfällig erweisen, um den Anforderungen der Anwender zu genügen. Aus diesem Grunde werden häufig funktionsbereichs- oder personengruppenspezifische Extrakte aus dieser Datenbasis entnommen und als Data Marts separat gespeichert. Hierbei kommen oftmals sogenannte OLAP (On-Line Analytical Processing)-Server bzw. -Engines zum Einsatz [5]. Derartige OLAP-Werkzeuge sind speziell auf die Analyse multidimensionaler Datenbestände ausgelegt, da sich die multidimensionale Aufgliederung betriebswirtschaftlicher Kennzahlen als geeignete Sichtweise für das Management erwiesen hat.

Dagegen sind die angeschlossenen Front-End-Werkzeuge auf den Desktop-Rechnern wie z.B. Abfrage- und Berichtsgeneratoren oder Tabellenkalkulationsprogramme keine Bestandteile des Data Warehouses im eigentlichen Sinne, zumal sie durch die Nutzung offener Schnittstellen austauschbar bleiben sollen. In der Praxis ist allerdings häufig zur Gewährleistung bestmöglicher Performance eine enge technologische Verzahnung von Endbenutzer-Tools und Datenspeichern auszumachen.

Zukünftig werden möglicherweise neue Werkzeuge die beschriebenen Komponenten erweitern bzw. ergänzen. So ist im Zuge der weltweiten Vernetzung (Internet) eine zunehmende Einbindung externer On-Line-Informationsquellen bei der Informationsversorgung des Managements zu erwarten [2]. Die Nutzbarmachung der hier gebräuchlichen Netzwerktechnologien, Zugangstechniken und Benutzungsoberflächen für den unternehmensinternen Bereich wird bereits unter dem Stichwort Intranet gehandelt. Intelligente Agenten sollen – so die Versprechen von Produktanbietern von Data Mining-Tools – in Zukunft selbständig nach interessanten Datenmustern schürfen und bislang unerkannte Strukturen und Zusammenhänge aufdecken [6].

                   Atikelanfang   Seitenanfang

Literatur

1. Bontempo, C., Saracco, C.: Accelerating Index Searching. Database Programming & Design, The Online Edition, o. O. 1996,
   www.dbpd.com/bontempo.htm
2. Gluchowski, P.; Gabriel, R.; Chamoni, P.: Management Support Systeme. Computergestützte Informationssysteme für Führungskräfte und Entscheidungsträger. Berlin, Heidelberg: Springer 1997
3. Holthuis, J.: Multidimensionale Datenstrukturen. In: Mucksch, H., Behme, W. (Hrsg.): Das Data-Warehouse-Konzept, Wiesbaden: Gabler 1996, S. 165–204
4. Inmon, W. H.: Building the Data Warehouse. 2. Aufl. New York: John Wiley & Sons 1996
5. Jahnke, B.; Groffmann, H.-D.; Kruppa, S.: On-Line Analytical Processing (OLAP). Wirtschaftsinformatik 38. 321–324 (1996)
6. Mattison, R.: Data Warehousing. Strategies, Technologies, and Techniques. New York: Mc Graw-Hill 1996
7. Mucksch, H.; Holthuis, J.; Reiser, M.: Das Data Warehouse-Konzept – ein Überblick. Wirtschaftsinformatik 38. 421–433 (1996)
8. Raden, N.: Star Schema 101. White Paper, Archer Decision Sciences Inc., Santa Barbara CA 1996,
   http://members.aol.com/nraden/str101.htm
9. Schinzer, H.: Data Warehouse. Informationsbasis für die Computerunterstützung des Managements. WiSt, Heft 9, September 1996

                   Atikelanfang   Seitenanfang

Autor & Copyright
Dr. Peter Gluchowski
Heinrich-Heine-Universität Düsseldorf
Wirtschaftswissenschaftliche Fakultät,
Universitätsstrasse 1,
D-40225 Düsseldorf

© 1997 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Atikelanfang   Seitenanfang

Deduktive Datenbanken

• Erläuterung
• Literatur
• Autor & Copyright
   

Erläuterung

Während der letzten 15 Jahre ist die Symbiose von Datenbanksystemen und Logikprogrammierung intensiv untersucht worden, mit dem Ziel traditionelle sowie neue Datenbankanwendungen besser zu behandeln. Dies führte zu Erweiterungen der herkömmlichen, relationalen Datenbankensysteme um regelbasierte Sprachen zur Wissensrepräsentation – die sowohl als Modellierungs- als auch als Anfragesprache verwendet werden – und um Deduktionsmethoden zur Wissensverarbeitung. Als zentrale Konzepte der deduktiven Datenbanken werden in diesem Artikel Ableitungsregeln und Integritätsbedingungen behandelt. Diese Konzepte sind in relationalen Datenbanksystemen nur in sehr eingeschränktem Umfang modellierbar. Der kürzlich entwickelte neue Standard SQL3 für relationale Datenbanken ermöglicht u.a. jetzt aber die Spezifikation von rekursiven Sichten und greift somit das deduktive Konzept der allgemeinen Ableitungsregeln auf. Das ebenfalls neu eingeführte Triggerkonzept ermöglicht eine imperative Spezifikation der Integritätsprüfungen. Deduktive Datenbanksysteme ermöglichen eine wesentliche Erweiterung des Anwendungsbereiches von Datenbanksystemen, und sie können auch die Migration zwischen unterschiedlichen Datenbanksystemen erleichtern.

Eine deduktive Datenbank, die auf einer relationalen Datenbank basiert, besteht aus Tupeln (auch Fakten genannt), sowie zusätzlich Ableitungsregeln und Integritätsbedingungen.

Eine Ableitungsregel ist eine allgemeine Definition, die es ermöglicht, Daten intensional zu spezifizieren, wie etwa die Regel „Alle Bücher des Springer-Verlages aus der Reihe LNCS sind auf Englisch verfaßt" zur Verwaltung eines Informationssystems über eine Bibliothek. Zum Ausdruck von Ableitungsregeln werden Sprachen mit „Wenn-Dann-Regeln" verwendet, wie in den Bereichen der Künstlichen Intelligenz (vgl. manche Expertensysteme), der Logikprogrammierung sowie der automatischen Deduktion. Dabei wird ein Tupelkalkül, wie etwa in der bekannten relationalen Sprache SQL, verwendet (z.B. „Buch. Nummer = 1234 and Buch. Sprache = Englisch"), oder ein sogenannter Domänenkalkül (womit das obige SQL-Beispiel als „Buch(1234, Englisch)" ausgedrückt wird), wie in der Logik. Die oben erwähnte Ableitungsregel kann z.B. wie folgt im Domänenkalkül dargestellt werden:

Buch(x, Englisch) <- Verlag(x, Springer),Reihe (x, LNCS)

Rekursive Regeln ermöglichen die intensionale Spezifikation von Daten, die auf Zusammenhängen von unbestimmtem Umfang beruhen, wie etwa die Definition einer Stücklistenauflösung (billofmaterials) oder einer indirekten Flugverbindung mit möglicherweise mehreren Maschinenwechseln. Wie in relationalen Datenbanken wird die Negation als Scheitern interpretiert, d.h. ein negierter Ausdruck wie etwa „not Buch (x, Englisch)" gilt als wahr, wenn für keine Buchnummer „x" der positive Ausdruck „Buch (x, Englisch)" ableitbar ist.

Ableitungsregeln werden bei der Auswertung von Anfragen automatisch eingesetzt, um das intensional dargestellte Wissen effizient wiederzugeben, wie etwa zur Beantwortung folgender Anfrage über in Englisch geschriebene Bücher über Datenbanksysteme (DBS) unter Berücksichtigung der oben erwähnten Regel:

Buch (x, Englisch), Thema (x, DBS)

Ein Hauptthema der Forschung über deduktive Datenbanken war die Definition von terminierenden und vor allem effizienten Anfrageauswertungsverfahren.

Integritätsbedingungen ermöglichen es, normative Bedingungen auszudrücken, wie etwa folgende funktionale Abhängigkeit zwischen Attributen einer Relation: „Die Nummer eines Buches ist ein eindeutiger Bezeichner des Buches", oder beliebig komplexe Zusammenhänge zwischen Daten: „An jedem Arbeitstag gibt es mindestens einen direkten Flug von einem der drei größten Flughäfen Deutschlands zur Ostküste der USA".Integritätsbedingungen setzen Normen, die die Datenbank nach jeder beliebigen Aktualisierung erfüllen soll. Im Gegensatz zu Ableitungsregeln können Integritätsbedingungen in der Regel zur Beantwortung von Anfragen nicht verwendet werden, weil sie die Daten nicht notwendigerweise eindeutig spezifizieren.

Integritätsbedingungen können anschaulich mit Hilfe von Ableitungsregeln dargestellt werden, deren Konklusionen „falsch" sind, wie etwa in:

false Reihe <- (x,LNCS), not Thema(x, Informatik)

d.h. „Es gibt kein Buch ,x‘ aus der LNCS-Reihe, welches nicht über Informatik ist". Weitere Hauptbeiträge der Forschung über deduktive Datenbanksysteme sind die Behandlung von uneingeschränkten, allgemeinen Integritätsbedingungen und die Automatisierung der Integritätsprüfung, d.h. der Spezifikation von effizienten, inkrementellen Verfahren zur Auswertung der Integritätsbedingungen nach jeder Aktualisierung. Diese beruhen auf Deduktionsmethoden, die aus deklarativen Integritätsbedingungen, welche als Programmspezifikation dienen, ein aus Triggern bestehendes imperatives Programm zur Integritätsprüfung automatisch generieren.

Im Gegensatz zu Integritätsbedingungen ermöglichen Trigger – wie z.B. in SQL3 vorhanden – nur eine imperative Spezifikation der Integritätsprüfung, aber keine deklarative Definition von Bedingungen. Der Unterschied kann bei komplizierten Integritätsbedingungen wesentlich sein. Wenn komplexe Zusammenhänge zwischen Daten im allgemeinen leicht vom Datenbankdesigner deklarativ spezifiziert werden können, erweist sich eine den Integritätsbedingungen entsprechende, effiziente Spezifikation von Triggern – wenn überhaupt möglich – oft als eine schwierige Aufgabe. Darüber hinaus ist die Aktualisierung von imperativen Integritätsprüfungs-Triggern viel komplexer und fehleranfälliger als eine Änderung von deklarativen Integritätsbedingungen. Text

Objektorientierte Datenmodellierung: Da die „flache" Wissensrepräsentation in der sogenannten „ersten Normalform" in Tupel- und Domänen-Kalkülen zu wenig Strukturierungsmöglichkeiten bietet, sind deduktive und objektorientierte Modellierungs- und Anfragesprachen kombiniert worden, so daß neben den herkömmlichen Daten auch Ableitungsregeln und Integritätsbedingungen in einem objektorientierten Kontext spezifiziert werden können. Man spricht dann von DOOD-Systemen, d.h. deduktiven und objektorientierten Datenbanksystemen.

In den meisten Datenbankanwendungen sind intensionale Spezifikationen konzeptuell allgegenwärtig. Sie werden in nichtdeduktiven Datenbanken durch extensionale, d.h. explizite, Spezifikationen von Tupeln oder Objekten sowie durch spezielle Anwendungsprogramme implementiert, die für jede Anwendung gesondert entwickelt werden müssen. Dabei zeigen sich folgende Nachteile, die von deduktiven Datenbankverwaltungssystemen vermieden werden:

• Abweichung von den tatsächlichen Spezifikationen,
• unsystematische Programmentwicklung,
• stark von der Programmierung abhängende Effizienz,
• Verwaltung der Programme außerhalb der Datenbank,
• imperative statt deklarative Spezifikationen.

Aus der Sicht relationaler Datenbanken ist die Erweiterung einer Datenbank um Ableitungsregeln und (uneingeschränkte) Integritätsbedingungen aus mehreren Gründen natürlich. Zum einen stellen Ableitungsregeln lediglich eine Verallgemeinerung des im relationalen Modell vorhandenen Begriffes der „Sicht" (view) dar. Zum anderen war ein allgemeiner Ansatz für Integritätsbedingungen bereits ein Ziel der relationalen Datenbanken, das bisher nur teilweise realisiert worden ist. Intensionale Darstellungen haben nicht nur den Vorteil, konzeptuell natürlicher zu sein als traditionelle, extensionale Datenbankspezifikationen. Sie haben den zusätzlichen Vorteil, oft eine wesentliche Datenkompaktierung zu ermöglichen. Kompaktierungsfaktoren von 10 bis mehrere 100 sind in Anwendungen nicht selten, die – wie etwa Fahrpläne – eine reguläre Stuktur aufweisen. Weniger Platz ist notwendig, um z.B. die folgende Regel zu spezifizieren:

„12 Minuten nach jeder vollen Stunde gibt es einen Flug von München nach Frankfurt/Main",

als die Angaben zu allen solchen Flügen mehrfach zu speichern.

Klassische Datenbanken, wie etwa Verwaltungsdatenbanken, werden intern in Unternehmen eingesetzt, z.B. zur Verwaltung von Personaldaten, Bankkonten oder Versicherungspolicen. Während des letzten Jahrzehnts wurden zunehmend Informationssysteme für ein breites Publikumangeboten, z.B. öffentliche Verkehrsinformationssysteme. Weil sie eine deklarative Modellierung ermöglichen, sind für solche Anwendungen deduktive sowie relationale Datenbanksysteme sehr passend. Neuerdings setzen sich Informationssysteme durch – auch übers Internet zugreifbar – die nicht nur Auskünfte geben, sondern auch komplexe Transaktionen wie etwa Buchungen von kompletten Flugreisen oder Bestellungen bei einem Versandhaus ermöglichen. Für Anwendungen aus diesem Bereich erweist sich der deklarative Ansatz der deduktiven Datenbanksysteme als sehr gut geeignet. Auch für neuere Datenbankanwendungen wie etwa im Bereich des Computer-Aided-Designs (CAD) oder der Entscheidungsunterstützung (z.B. Diagnosesysteme und Expertensysteme) sind deduktive Datenbanksysteme besonders geeignet. Darüber hinaus sind wegen ihrer Behandlung von uneingeschränkten Integritätsbedingungen deduktive Datenbanksysteme im traditionellen Bereich der Verwaltungsdatenbanken auch sehr nützlich. Regeln erleichtern z.B. die Spezifikation der Aufnahme in Sperrlisten bei Kreditkartenunternehmen.

Neuere Anwendungen für deduktive Datenbanken erfordern erweiterte Möglichkeiten zur Repräsentation von Wissen. Zur Zeit wird deshalb intensiv an der Erweiterung deduktiver Datenbanken um eine uneingeschränkte Negation als Scheitern und um verschiedenen Formen von unsicherem Wissen, wie etwa in disjunktiven Datenbanken, gearbeitet. Für viele Anwendungen ist die deklarative Spezifikation von Datenbankänderungen sehr wichtig. Dies hat zu Forschungsaktivitäten im Bereich der aktiven Datenbanken geführt, in denen Regelformalismen zur Definition von Änderungen verwendet werden. Auch neueste Datenbankthemen, wie z.B. Knowledge Discovery (auch Data Mining genannt) und Constraint-Datenbanken, bei denen spezielle Theorien zur Spezifikation von besonderen Daten wie etwa Intervallen oder numerischen Werten eingesetzt werden, nutzen oder erweitern Methoden der deduktiven Datenbanken.

Die in deduktiven Datenbanken eingeführten Erweiterungen haben für die Datenbankforschung einen Sprung ins Unbekannte dargestellt. Zum ersten Mal wurde ein Datenbankkonzept vorgeschlagen, das genauso wie eine Programmiersprache uneingeschränkte Berechnungen ermöglicht, weil die aus Fakten und Ableitungsregeln bestehenden Sprachen Turingvollständig sind. Daran mag es liegen, daß die neue, zukunftsweisende Technologie der deduktiven Datenbanken sich nur langsam außerhalb der Forschungskreise etabliert. Die kürzliche Aufnahme von rekursiven Sichten im neuen Standard SQL3 wird in Fachkreisen als eine wichtige Erweiterung von traditionellen Datenbanksystemen um Konzepte deduktiver Datenbanksysteme angesehen.

                   Artikelanfang  Seitenanfang

Literatur

1. Bry, F.; Manthey, R.; Schütz, H.: Deduktive Datenbanken, KI – Künstliche Intelligenz – Forschung, Entwicklung, Erfahrungen, wird erscheinen.
2. Kießling, W.; Güntzer, U.: Deduktive Datenbanken auf dem Weg zur Praxis, Informatik Forschung und Entwicklung, Heft 5, 1990, S. 177-187
3. Special Issue on Prototypes of Deductive Database Systems, The VLDB Journal, vol. 3(2), 1994.

                   Artikelanfang  Seitenanfang>

Autor & Copyright
François Bry¹, Dietmar Seipel²

¹Inst. f. Informatik,
Ludwig.-Maximil.-Univ.,
Geschwister-Scholl-Platz 1,
D-80539 München

²Inst. f. Informatik,
Jul.-Maximil.-Univ.,
Am Hubland,
D-97074 Würzburg

© 1996 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang  Seitenanfang

Versionsunterstützung in Datenbanken

• Erläuterung
• Literatur
• Autor & Copyright
   

Erläuterung

Die Aufgabe eines Datenbanksystems ist es, Informationen über einen (für den Benutzer des Datenbanksystems) relevanten Ausschnitt der realen Welt zu speichern. Heutige Datenbanksysteme beschreiben genau einen Zustand dieser Informationen. Änderungen in der realen Welt führen zu Änderungen in der Datenbank, die Informationen über den alten Datenbank-Zustand werden vergessen. Lediglich für die Implementierung bestimmter Funktionalitäten werden alte Zustände in Log-Files aufgehoben, etwa für Recovery-Zwecke oder zur Erhöhung der Parallelität zwischen Schreib- und Lesetransaktionen. Dagegen gibt es auf der Datenmodell-Ebene in der Regel keine Möglichkeit, mehrere Zustände eines Datenbankobjektes zu verwalten.

Mindestens zwei Anwendungsbereiche erfordern jedoch die Darstellung mehrerer Datenbank-Zustände:

1. die Modellierung des Zeitbegriffs und die Darstellung der dynamischen Änderungen in der realen Welt,
2. die Unterstützung von konstruktiven Tätigkeiten in Entwicklungs- und Planungsprozessen.

Aus diesem Grunde wurden und werden in verschiedenen Forschungsarbeiten und Prototyp-Implementierungen Konzepte entwickelt und erprobt, um mehrere Versionen von Datenbank-Objekten verwalten zu können. Dabei zeigte sich, daß die verschiedenen Anwendungen recht unterschiedliche Anforderungen an das Versions-Management stellen, so daß eine Reihe von Konzepten zur Versions-Verwaltung entstanden.

Versionen zur Modellierung des Zeitbegriffs

Das Festhalten alter Zustände und die Zuordnung von Operationen zu bestimmten Zeitpunkten (etwa bei Buchungsvorgängen) ist ein wichtiges Problem, das auch in konventionellen Datenbank-Anwendungen auftritt. Üblicherweise werden in heutigen Realisierungen bei der Nutzung herkömmlicher Datenbanken den Objekten spezielle Zeitattribute hinzugefügt. Um ihre korrekte Benutzung zu gewährleisten, dürfen diese Attribute nur durch spezielle Anwendungsprogramme manipuliert werden.

In zeitorientierten Datenbanken geht es darum, die Semantik dieser Zeitattribute dem Datenbanksystem bekannt zu machen. Das Ziel besteht darin, die Geschichte von Objekten darzustellen, d.h. jedem Zeitpunkt einen bestimmten Zustand des Objektes zuzuordnen. Zeit ist eine Größe, die sich kontinuierlich verändert. In Datenbanken können dagegen nur diskrete Zustände von Objekten gespeichert werden. Im allgemeinen geht man jedoch davon aus, daß zwischen zwei Änderungen der Wert eines Objektes gleich bleibt (zustandserhaltende Geschichte, andere Geschichtsarten sind in [5] dargestellt. Daher führt jede Änderungsoperation zur Erzeugung einer neuen zeitbehafteten Version aller betroffenen Objekte. Das Ergebnis einer Frage nach dem Objektzustand eines Objektes o zum Zeitpunkt t ist dann die jüngste Version, deren Zeitmarke älter als t ist.

Eine Zeitangabe in einer zeitbezogenen Datenbank kann mehrere Bedeutungen haben: Es kann der Zeitpunkt gemeint sein, zu der eine Version in die Datenbank eingespeichert wurde (Aufzeichnungszeit, physical time, transaction time), oder aber der Zeitpunkt, ab dem ein bestimmter Zustand in der Realität wirksam wird (Gültigkeitszeit, logical time, valid time). Weitere Bedeutungen von Zeitangaben sind denkbar.

Snodgrass [7] klassifiziert zeitorientierte Datenbanken gemäß den Zeitbegriffen, die sie unterstützen:

• Snapshot database

Konventionelle Datenbank, die nur einen Zustand (Schnappschuß) des Weltschnittes darstellt und keine zeitorientierten Queries zuläßt.

• Roll-back database

Datenbank, die die Aufzeichnungszeit von Versionen (Zeitpunkt der Update-Transaktion) verwaltet und damit die Änderungsgeschichte der Datenbank beschreibt. Damit sind Fragen der folgenden Art möglich (AS-OF-Queries): "Wie sah die Datenbank zum Zeitpunkt t aus?".

Die AIMP-Datenbank kann gemäß dieser Klassifikation als Roll-Back-Datenbank angesehen werden: Zeitmarken stellen Transaktionszeiten dar, und durch AS-OF-Queries können alte Zustände der Datenbank abgefragt werden.

• Historical database

Datenbank, die die Gültigkeitszeit verwaltet und damit die Geschichte von Objekten der Realwelt aus heutiger Sicht beschreibt. Ist der Version [Name = Meier, Gehalt = 4000] des Angestelltenobjektes ein Zeitpunkt t zugeordnet, so besagt dies, daß zu diesem Zeitpunkt eine Gehaltserhöhung (oder -festsetzung) wirksam wurde. Wie und wann dieses Gehalt festgelegt wurde, etwa durch eine nachträgliche Gehaltserhöhung, läßt sich in diesem Fall nicht ermitteln.

• Temporal database

Datenbank, die sowohl die Aufzeichnungszeit als auch die Gültigkeitszeit festhält. Dadurch können sowohl nachträgliche Änderungen (Korrekturen, rückwirkende Änderungen, z.B. rückwirkende Gehaltserhöhung) als auch zukünftige Änderungen vollständig aufgezeichnet werden. Durch die Kombination der beiden Zeitangaben können Aufzeichnungs- und Gültigkeitszeit in Anfragen zueinander in Beziehung gesetzt werden: Welchen Zustand hat das Objekt o zum Zeitpunkt tg (Gültigkeitszeit), bezogen auf die Informationen, die zum Zeitpunkt ta (Aufzeichnungszeit) in der Datenbank vorlagen. Beispiel: Welches Gehalt erwartete der Angestellte Meier am 1. Juli (ta) für seine im September (tg) zu leistende Arbeit? (Frage nach der am 1. Juli in der Datenbank gespeicherten gültigen Version für September). Die temporale Datenbanksprache TQuel [7] unterstützt die beide Zeitdimensionen und erlaubt damit die Formulierung entsprechender Anfragen.

Zur Zeit beschäftigen sich mehr als zwanzig Forschungsgruppen mit der Darstellung des Zeitbegriffes in Datenbanken, eine Übersicht über eine Vielzahl dieser Projekte wird in [6] gegeben. Ausführliche Literaturhinweise finden sich z.B. in [4] und in [7].

Versionen zur Unterstützung konstruktiver Tätigkeiten

In herkömmlichen Anwendungen enthält die Datenbank ein Abbild der Realwelt. Wird sie dagegen zur Unterstützung von kreativen Prozessen eingesetzt, etwa im CAD/CAM, im Software Engineering oder im Bürobereich, so beinhaltet sie Vorbilder für später zu konstruierende Realwelt-Objekte oder sie enthält diese Objekte selbst (etwa Briefe im Bürobereich, Programme bei Software Engineering). Außerdem enthält die Datenbank nicht nur die „fertigen" Objekte, sondern sie wird gerade für die Abspeicherung der Daten genutzt, die auf dem Weg zum fertigen Produkt anfallen. Um diese Zwischenversionen zu verwalten, müssen neben der linearen Anordnung der Versionen entlang der Zeitachse(n) weitere Strukturen zur Organisation der Versionsmenge eingesetzt werden.

Die verschiedenen Anwendungen in diesem Bereich haben ihre spezifischen Anforderungen an die Versionsverwaltung. Dies spiegelt sich wider in vielen unterschiedlichen Begriffen, die jeweils eine spezielle Versions-Semantik ausdrücken: Revisionen stellen verschiedene Änderungsbestände eines Objektes dar, Alternativen sind unterschiedliche Ansätze zur Entwicklung eines Objektes. Varianten sind Versionen, die unter einer bestimmten Abstraktion gleich sind und sich durch bestimmte Parameter unterscheiden (Schrauben verschiedener Länge, Programme für unterschiedliche Betriebssysteme). Repräsentationen sind unterschiedliche Darstellungsformen eines Objektes, etwa Source- und Objekt-Code von Programmen oder Logik und Layout-Darstellung von Chips.

Zur Modellierung der verschiedenen Versionsvorstellungen wurden Versionsmodelle entwickelt, die jeweils bestimmte Aspekte des Versionsbegriffs in den Vordergrund stellen. Die wesentlichen Elemente der Versionsmodelle sind:

• Definition von Beziehungen zwischen Versionen: Revisionen (Ableitungsgeschichte) sind Baumstrukturen, Alternativen sind parallele Äste einer solchen Baumstruktur, und das Mischen von Versionen führt zu allgemeinen nicht-zyklischen Graphen.
• Zuordnung von Eigenschaften (Versionszustände, Klassifikation von Versionen): Versionen können z. B. entscheidend der Tests, die sie bestanden haben, als konsistent oder nicht-konsistent klassifiziert werden, oder sie durchlaufen Zustände wie Konstruktion, Produktion oder Wartung, die ihre Stellung im Lebenszyklus des Produktes darstellen.
• Definition bestimmter Operationen für die Manipulation der Strukturen der Versionsmenge: z.B. werden beim Erzeugen einer neuen Version automatisch Beziehungen zu Vorgängerversionen geknüpft (aus denen die neue Version hervorgegangen ist), und/oder die neue Version erhält automatisch einen bestimmten Versionszustand. Häufig sind die erlaubten Operationen von der Stellung der Version in der Organisationsstruktur abhängig, und durch die Definition von Zustands-Übergangsfolgen können Lebenszyklen von Design-Objekten beschrieben werden. Ein Beispiel zeigt Abb. 1: Die Zustände in-progress, alternative, effective können beliebig oft durchlaufen werden und beschreiben jeweils einen Schritt der Konstruktion. Wird eine Version vom Zustand effective in den Zustand released transferiert, so gilt sie als freigegeben für die Produktion. Später kann sie archiviert oder gelöscht werden. Abhängig von ihrem Zustand dürfen Versionen nur gelesen (R) oder auch geändert werden (RW).

In einigen Ansätzen wird versucht, die Versionsmodellierung flexibler an die Anforderungen der einzelnen Anwendungen anzupassen. Zu diesem Zweck bietet sie elementare Versionsmechanismen an, um mit ihrer Hilfe die Beschreibung des gewünschten Versionskonzepts im Schema der Datenbank zu ermöglichen. So werden in [2] Versions-Cluster eingeführt, durch die auf der Schema-Ebene eine bestimmte Teilmengen-Struktur über die Versionsmenge definiert werden kann. In [8] werden Versions-Umgebungen definiert, die es erlauben, Graphen und Partitionen über die Versionsmenge zu legen, um die Beziehungen zwischen Versionen und die Versionszustände darstellen zu können. Es werden primitive Operationen auf diesen Strukturen angeboten, auf deren Basis komplexere, benutzerorientierte Operationen definiert werden können. Zusammen mit Constraints, die die Ausführung einer Operation von bestimmten Bedingungen abhängig machen, besteht damit die Möglichkeit, durch zugeschnittene Versionsstrukturen und Operationen darauf den gewünschten Versionsbegriff der Anwendung zu modellieren.

Ein wichtiger Aspekt der Versionsverwaltung in konstruktiven Anwendungen ist die Einbindung des Versionskonzepts in die Objektstrukturen. Design-Objekte sind typischerweise sehr komplex, und sie sind in verschiedene Beziehungen eingebettet: Ein Design-Objekt kann aus anderen, unabhängig entwickelten Design-Objekten zusammengesetzt sein (Zellen im VLSI-Design sind aus anderen Zellen zusammengesetzt, Programm-Module benutzen andere, unabhängige Programm-Module), es kann in verschiedenen Abstraktionsebenen vorliegen (z.B. Implementierung und Schnittstelle eines Programm-Objektes) und in verschiedenen Repräsentationsformen dargestellt sein. Änderungen an einem Element dieser komplexen Beziehungsstrukturen können Auswirkungen auf viele andere Objekte haben. Hier kann die Versionierung von Design-Objekten im Zusammenspiel mit speziellen Mechanismen zu einer höheren Flexibilität und einer größeren Sicherheit vor Fehlern führen.

Betrachten wir als Beispiel die Aufruf-Hierarchie zweier Module: Modul M1 benutzt Funktionen des Moduls M2, d.h. von M1 geht eine benutzt-Referenz (oder Komponenten-Referenz) auf M2. Falls einer der Funktionsaufrufe in M2 geändert wird, so benutzt M1 diese Funktion nicht mehr korrekt. Bewirkt die Änderung die Erzeugung einer neuen Version von M2, so kann M1 weiter die alte Version benutzen und braucht nicht geändert werden. Andererseits kann die Änderung der Funktion aber auch eine wesentliche Effizienz-Verbesserung der Funktion beinhalten, so daß der Programmierer des Moduls M1 sie gerne benutzen würde. Ein System zur Änderungskontrolle muß somit sowohl die Benutzung von alten Versionen als auch Mechanismen zur flexiblen Auswahl neuer Versionen von Komponenten ermöglichen.

In anderen Anwendungsbereichen ist das Erkennen von Inkompatibilitäten wesentlich schwieriger als im Software Engineering, da das Konzept der Schnittstelle nicht überall so eindeutig definiert werden kann. Doch verschiedene Verfahren und insbesondere ihre kombinierte Anwendung bieten in vielen Fällen eine befriedigende Lösung der Änderungsverwaltung:

Durch den Mechanismus der Change Notification werden übergeordnete Objekte von Änderungen ihrer Komponenten informiert. Sie werden z.B. markiert, oder der Konstrukteur erhält direkt eine Nachricht. Ein anderes Konzept wird als Version-Percolation oder Change Propagation bezeichnet: Die Erzeugung einer neuen Version eines Objektes führt automatisch zur Erzeugung von neuen Versionen der sie benutzenden Objekte [3]. Eine weitere Methode besteht in der Einführung generischer Referenzen, durch die ein dynamisches Binden von Komponenten-Versionen erreicht wird. Im Gegensatz zur festen Referenzierung bestimmter Versionen einer Komponente (statisches Binden) wird hierbei zunächst nur festgelegt, welches Design-Objekt als Komponente benutzt wird, ohne bereits eine bestimmte Version auszuwählen. Die Auswahl der Komponentenversionen erfolgt dynamisch, z.B. durch einen Qualifikationsausdruck, der die auszuwählende Version beschreibt (etwa die neueste Version im Zustand freigegeben), oder durch die Bereitstellung von repräsentativen Versionen für jedes Design-Objekt durch den Benutzer.

Abspeicherung von Versionen

Ein Problem bei der Versionierung von Objekten kann die Größe des erforderlichen Speicherplatzbedarfes sein, besonders wenn jede Änderung grundsätzlich zur Erzeugung einer neuen Version führt. Daher wurden bereits früh Konzepte zur Verringerung des Speicherplatzbedarfs entwickelt, und die bekannteste Methode ist die Delta-Speicherung: Versionen werden nicht alle vollständig abgespeichert, sondern es werden nur die Unterschiede der Version zur vorherigen Version (Deltas) festgehalten. Hinter der ältesten Version eines Objekts, die als Anker vollständig abgelegt ist, bildet sich eine Delta-Kette, die beim Zugriff auf eine Version durchlaufen werden muß. Durch die Auswertung der abgespeicherten Deltas wird die gewünschte Version dabei sukzessive rekonstruiert. Geht man davon aus, daß am häufigsten auf die neueste Version zugegriffen wird, so kann man die Delta-Kette auch umdrehen [1]: die neueste Version wird als Anker vollständig abgespeichert, und die Kette wird immer in Richtung auf die Vergangenheit durchlaufen. Je älter eine Version ist, desto größer ist dann der Aufwand für ihre Rekonstruktion.

                   Artikelanfang  Seitenanfang

Literatur

1. Damdam, P., Lum, V., Werner, H.-D.: Integration of Time Versions into a Relational Database System. Proc. 10th Int. Conf. on Very Large Data Bases (VLDB), Singapore 1984
2. Dittrich, K.R., Lorie, R.A.: Version support for engineering data base systems. [EEE Trans. Software Eng. 14, No. 4 (1988)
3. Katz, R.H., Chang, E.: Managing Change in a Computer Aided Design Database. Proc. 13th Int. Conf. of Very Large Data Bases (VLDB), Brighton 1987
4. McKenzie, E.: Bilbliography: Temporal databases. ACM SIG-MOD Rec. 15, No. 4 (1986)
5. Petry, E.: Versionenverwaltung von Objekten durch ein erweitertes relationales Datenbanksystem. Dissertation ETH Zürich 1988
6. Snodgrass, R. (ed.): Research concerning time in databases: Project summaries. ACM SIGMOD Rec. 15, No. 4 (1986)
7. Snodgrass, R.: The temporal query language TQuel. ACM Trans. Database Syst.. 12, No. 3 (1987)
8. Wilkes, W.: Der Versionsbegriff und seine Modellierung in CAD/CAM-Datenbanken. Dissertation FernUniversität Hagen 1987

                   Artikelanfang  Seitenanfang

Autor & Copyright
W. Wilkes (Hagen)

© 1989 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang  Seitenanfang

Remote Database Access: Kommunikationsunterstützung für Fernzugriff auf Datenbanken

• Erläuterung
• Literatur
• Autor & Copyright
   

Erläuterung

Datenbanken sind in der Praxis weit verbreitet und haben den Vorteil, daß sich damit sowohl der Nutzen als auch die (oft hohen!) Kosten von Datensammlung und -verwaltung auf einen weiten Kreis von Benutzern verteilen lassen. Im Zusammenhang mit der zunehmenden Vernetzung von Rechnern aller Art über unterschiedliche Distanzen hinweg (LAN, WAN, MAN, . . .) bekommt diese Eigenschaft von Datenbanken noch eine zusätzliche Bedeutung. So wird es nun möglich, von lokal zur Verfügung stehenden Arbeitsplatzrechnern aus Dienste von entfernten, dedizierten Spezialrechnern (z.B. Datenbankrechnern) auch über lokale Rechnergrenzen hinaus mit größtmöglicher Aktualität direkt zu nutzen.

Insbesondere in offenen Rechnernetzumgebungen, in denen die Kommunikationspartner variieren können und einander nicht im voraus bekannt sein müssen sind flexible Nutzungsmöglichkeiten von entfernten Datenbankdiensten von großem praktischen Wert. Gegenüber klassisch verteilten Datenbanken hat dabei der dem „Remote Database Access" (RDA) zugrunde liegende Client/Server-Ansatz insbesondere den Vorteil das der Datenverwaltung auf den Servern ein hohes Maß an lokaler Autonomie erhalten bleibt.

Kommunikationsunterstützung für heterogene, offene Rechnernetze basiert auf generell vereinbarten Software-Schnittstellen und allgemein bekannten (d.h. standardisierten) Kommunikationsprotokollen. So beruht auch beim Fernzugriff auf Datenbanken (engl. Remote Database Access) die Kommunikation zwischen den verteilten heterogenen und miteinander kooperierenden Rechnerknoten auf von der International Standards Organization (ISO) und ihren internationalen Unterorganisationen im Rahmen des Referenzmdells [1] für die Kommunikation in Offenen Systemen (Open Systems Interconnection, OSI) festgelegten Standards.

RDA-Modell

Entsprechend einem allgemeinen Client/Server-Ansatz für verteilte Datenverarbeitung [5] geht auch das dem RDA zugrunde liegende Modell von einem Datenbank-Klienten aus (z.B. einer Arbeitsstation), der die ISO-OSI-Kommunikationsdienste dazu benutzt, auf einen oder mehrere entfernte(n) Datenbank-Server in einer hererogenen Rechnernetzumgebung zuzugreifen. (Abb. 1).

Nach diesem Modell wird der RDA-Dienst als asymmetrischer ISO-OSI-Anwendungsdienst (d.h. Teil der Ebene 7) sowohl auf der Seite de Klienten als auch auf der des Servers basierend auf den Diensten der darunterliegenden ISO-OSI-Schichten 1 bis 6 erbracht. Auf der Seite des Klienten sind die RDA-Dienste über ein - z.Zt. nicht norminiertes - „Application Program Interface" (API) dem Anwendungsprogramm zugänglich. Auf der Seite des Servers vermittelt ein - ebenfalls nur lokal spezifizierter - Server-Prozeß zwischen ein- und ausgehenden RDA-Nachrichten und dem angesprochenen Datenbankverwaltungssystem (DBMS).

Entsprechend dem ISO-OSI-Referenzmodell definiert dabei die RDA-Dienstschnittstelle die Funktionalität aller RDA-Kommunikationdienste, die sowohl dem Klienten als auch dem Server zur Verfügung stehen. Das RDA-Kommunikationsprotokoll beschreibt dann im Detail die Datenformate und die erlaubten Reihenfolgen aller Nachrichten, die zwischen je zwei RDA-Kommunikationspartnern ausgetauscht werden können.

RDA-Kommunikationsdienste

An der RDA-Dienstschnittstelle stellt die RDA-Kommunikationsunterstützung die folgenden Gruppen von Diensten bereit: Gemäß einer Vereinbarung zwischen RDA-Klient und -Server zu Dialogbeginn können davon auch nur Teilmengen (Functional Units) für bestimmte Verbindungen ausgewählt werden.

Dialogverwaltung: Wie andere ISO-OSI-Anwendungen auch beruht RDA auf verbindungsorientierter Kommunikation zwischen Partnern (Peers). Um eine RDA-Kommunikationsbeziehung aufzubauen, stellt RDA explizite Dienste zum Auf- und Abbau eines Kommunikationsdialoges bereit: „R-BeginDialogue" und „R-EndDialogue" (Die Liste und die Bezeichnungen der Dienste entsprechen dem Stand der Normung von Ende 1990). Dialoge sind logische Beziehungen zwischen Kommunikationspartnern der OSI-Anwendungsebene, die auch über etwaige zwischenzeitliche Störungen der darunterliegenden Verbindungen (Associations) hinweg erhalten bleiben.

Ressourcen-Verwaltung: Während eines Dialoges kann mit der Hilfe der RDA-Dienste „R-Open" und „R-Close" vom Klienten an den Server der Wunsch übermittelt werden, „Ressourcen" der entfernten Datenbank zu öffnen oder zu schließen. Dabei sind Ressourcen von der Anwendung bestimmte Teile der Datenbank, die von einzelnen Tupeln bis zur gesamten Datenbank reichen können.

Da die Übermittlung und Ausführung aller RDA-Operationen in der Regel zu einem „Resultat" führt (z.B. einer „Antwort", einer „Status"- oder einer Fehlermeldung), läßt sich die Grundstruktur der Ausführung aller RDA-Dienste wie folgt beschreiben: Der RDA-Klient übermittelt an den RDA-Server den Wunsch (Request), eine bestimmte Operation entfernt auszuführen; dieser Wunsch wird beim Server angezeigt (Indication), und nach Ausführung der Operation sendet der Server ein Resultat an den Klienten zurück.

Datenbanksprachenunterstützung: Während eines Dialoges und nach Öffnung der notwendigen Ressourcen kann der RDA-Klient mit Hilfe des Dienstes „R-ExecuteDBL" Datenbankkommandos in einer zuvor ausgewählten Datenbanksprache (Database Language, DBL) an den Server übermitteln. Der Server sendet dann als Ergebnis eines solchen Dienstaufrufes die entsprechenden Resultate (s.o.) an den Klienten zurück. Die bei diesem Dienstaufruf verwendete (standardisierte!) Datenbanksprache wird bei Dialogbeginn ausgewählt.

Darüber hinaus stellt RDA Möglichkeiten bereit, durch Verwendung des Dienstes „R-Define" Datenbankkommandos unabhängig von ihrer Ausführung (zu Optimierungszwecken) auch schon vorab an den Server zu übermitteln, dann mit Hilfe des Dienstes „R-Invoke" - i.d.R. später aufzurufen und derartige Definitionen mit Hilfe des Dienstes „R-Drop" wieder zu löschen.

Kontrolldienste: Wenn die Ausführung einzelner Datenbankkommandos unerwartet lange dauert, stellt RDA Dienste zur Abfrage des Status (R-Status) oder zum Löschen (R-Cancel) vorab übermittelter, aber noch nicht abgeschlossener Operationen auf dem Server zur Verfügung.

RDA-Transaktionsverwaltung: Zur Übermittlung von speziellen Nachrichten zur Kontrolle von Datenbanktransaktionen stellt RDA in seiner einfachsten Form optional die folgenden Dienste bereit: „R-BeginTransaction" dient zum Initiieren, „R-Commit" bzw. „R-Rollback" zum erfolgreichen Beenden bzw. zum Zurücksetzen einer entfernten Transaktion.

Wesentlich weiter gehende Kommunikationsmechanismen für die Kontrolle von verteilten Transaktionen stehen als Alternative zu den genannten RDA-Diensten in einem erweiterten RDA-Anwendungskontext zur Verfügung. Hier wird durch direkte Referenz auf den entsprechenden ISO-OSI-Standard für verteilte Transaktionsunterstützung (Transaktion Processing TP) [4] vermieden, daß RDA die auch für andere OSI-Anwendungen wichtigen Grundfunktionen zur Transaktionsverwaltung eigens neu definiert.

RDA-Spezialisierungshierarchie

Da RDA eine spezielle Art beschreibt, entfernte Datenbankoperationen - asynchron - aufzurufen, entspricht das Grundmuster der dabei verwendeten Kommunikation dem eines allgemeineren entfernten Prozeduraufrufes. Innerhalb dieses Rahmens spezifiziert dann der „generische" Teil des RDA [2] einen Rahmen für allgemeine RDA-Dienste, die unabhängig von der zugrunde liegenden Datenbanksprache sind. Erst in einem zweiten Teil des RDA-Standards werden dann die speziellen Datenbankkommandos näher definiert, die für eine bestimmte Datenbanksprache verwendet werden dürfen. Für die standardisierte relationale Datenbanksprache SQL ist dies in [3] im einzelnen genau beschrieben.

RDA-Kommunikationsprotokoll

Das RDA-Kommunikationsprotokoll spezifiziert im Detail zunächst die genauen Formate aller RDA-Nachrichten (Protocol Data Units, PDUs), die zwischen beliebigen RDA-Klienten und RDA-Servern in einer offenen Netzumgebung ausgetauscht werden können. Über die Definition der RDA-PDUs hinaus spezifiziert das RDA-Protokoll dann Regeln und Bedingungen, die jede mit dem Standard konforme Implementierung befolgen muß. Wichtigstes Beispiel für derartige Einschränkungen sind die Reihenfolgeregeln, die alle legalen Abfolgen von RDA-PDUs zwischen den RDA-Kommunikationspartnern beschreiben (Einfaches Beispiel: „R-BeginDialog" muß allen anderen RDA-Operationen vorangehen.)

Status

Ein erster technischer Vorschlag zu RDA wurde bis ca. 1986 von der „European Computer Manufacturers Association" (ECMA) erstellt und darauf in die nationalen und internationalen ISO-Normungsgremien eingebracht. Ende 1990 liegt ein Normungsvorschlag der ISO zu RDA als 2. „Committee Draft" (CD) vor und soll - nach der Planung vom Jahresende 1990 - 1991 als technisch stabiler ISO „Draft International Standard" (DIS) und ein Jahr darauf als verbindlicher ISO-Standard international verabschiedet werden.

Die Liste der im derzeitigen RDA-Standardentwurf noch offenen Punkte umfaßt alternative RDA-Spezialisierungen (z.B. für SQL2, SQL3, Netzwerksprache etc.), spezielle Unterstützung für (Datenbanksprach-)Module, unterbrechbare RDA-Dialoge, erweiterte Transaktionsverwaltungsmechanismen oder etwa Erweiterungen für komplexere Datenmodelle (z.B. für Zugriff auf Multi-Media-Datenbanken) oder auch Anpassungen an die Möglichkeiten von Hochgeschwindigkeitsnetzen.

                   Artikelanfang  Seitenanfang

Literatur

1. international Organization for Standardization: Basic Reference Model Information Processing Systems - Open Systems Interconnection, international Standard 7498 (1984)
2. international Organization for Standardization: Remote Database Access - Part 1: Generic Information Processing Systems - Open Systems Interconnection, Draft Proposal 9579-2 (ISO/IECJTC1/C21 WG3 N996) (1990)
3. International Organization for Standardization: Remote Database Access - Part 2: SQL Specialization Information Processing Systems - Open Systems Interconnection, Draft Proposal 9579-2 (ISO/IECJTC1/C21 WG3 N996) (1990)
4. International Organization for Standardization: Distributed Transaction Processing Information Processing Systems - Open Systems Interconnection, Draft International Standard 10026-1, 10026-2, 10026-3 (1989)
5. Svoboda, L.: Clint/Server Model of Distributed Processing, Proc. GI/NTG-Fachtagung "Kommunikation in verteilten Systemen", Karlsruhe, W.-Germany, Informatik-Fachberichte. Vol. 95, pp. 485-498, Heidelberg: Springer 1985

                   Artikelanfang  Seitenanfang

Autor & Copyright
Prof. W. Lamersdorf
Fachbereich Informatik, Universität Hamburg
Schlüterstr. 70,
W-2000 Hamburg 13

© 1991 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang  Seitenanfang

Objektorientierter Datenbankentwurf

• Erläuterung
• Fazit
• Literatur
• Autor & Copyright
   

Erläuterung

Objektorientierte Datenbankmodelle nehmen für sich in Anspruch, eine natürlichere Modellierung der Anwendung zu ermöglichen, als im Relationenmodell oder den bisherigen Entwurfsmodellen, meist Versionen des Entity-Ralationship-Modells (ER-Modell), üblich. Zusätzlich kann man noch zwei prinzipielle Vorteile aufführen:

• Das Entwurfsmodell entspricht auch einem der möglichen Implementierungsmodelle, da es bereits objektorientierte Datenbankmodelle zumindest weitgehend unterstützen. In bisherigen Entwurfsmethoden wurde ein der Anwendungswelt angepaßtes Entwurfsmodell (etwa das ER-Modell) auf ein Implementierungsmodell (etwa das Relationenmodell) abgebildet, wobei ein Verlust von Semantik nicht vermieden werden konnte.
• Im Gegensatz zu den bisherigen Entwurfsmodellen kann nun auch das dynamische Verhalten von Objekten durch Angabe von objekt- oder klassenspezifischen Methoden modelliert werden. In bisherigen Entwurfsmodellen wurde diese Funktionalität entweder durch Programme außen aufgesetzt oder dadurch realisiert, daß Attributwerte in Relationen als Implementierung einer Funktion aufgefaßt werden konnten. Ein durchgängiges Entwurfsverfahren für Strukturen und Verhalten gemeinsam gab es noch nicht.

Entity-Relationship-Modelle

Der klassische Datenbankentwurf modelliert Objekte und ihre Attribute, klassifiziert diese in Entity-Typen und stellt die entworfenen Entity-Typen miteinander in verschiedene Beziehungen (etwa [7]). Dabei wurden Normalisierungsverfahren zur Redundanzvermeidung analog dem Relationenmodell ausgenutzt. Die ER-Modelle unterscheiden sich in der Anzahl der unterstützten Konzepte (etwa Typkonstruktoren, Is-a-Beziehungen,...). Sie werden beim klassische Software-Entwurf zum Entwurf der Datenstrukturen eingesetzt, Verfahren wie Strukturierte Analyse dagegen zum Entwurf der Funktionen. Die Integration der datenorientierten und funktionsorientierten Sicht ist hier nur eingeschränkt möglich.

Objektorientierte Modellierung

Datenbankentwurf und Software-Entwurf werden durch die objektorientierte Modellierung miteinander integriert. Man identifiziert Objekte, die ihre Attribute und Methoden, klassifiziert sie in Klassen und ordnet die Klassen in mehreren Hierarchien an:

1. in der Klassenhierarchie ist eine Klasse Ku Unterklasse einer anderen Klasse Ko, wenn die Menge der Objekte in Ku eine Teilmenge der Objektmenge von Ko ist.
2. in der Typenhierarchie ist eine Klasse Ku deren Attribute und Methoden einen Typ Tu haben, unterhalb der Klasse Ko mit Typ To, falls Tu mehr oder speziellere Komponenten hat als To.
3. In der Implementierungshierarchie ist eine Klasse Ku Unterklasse von Ko, falls Ku, die Implementierungsumgebung (also Attribute und Methoden) von Ko erbt und für eigene Attribute und Methoden verwenden kann.
4. In der Komponentenhierarchie ist eine Klasse Kk Komponente einer anderen Klasse K, wenn K ein Attribut vom Typ der Klasse KK besitzt. Im Gegensatz zu den anderen Hierarchien können diese Komponentenbeziehungen auch zyklisch werden.
5. In der Instanzenhierarchie ist eine Klasse Ki Instanz einer (Meta-)Klasse Km, wenn Ki Element der Objektmenge der Klasse km ist.

Objektorientierte Programmiersprachen unterstützen die Hierarchien 3 und 4, eventuell auch 5. Die Klassenhierarchie ist eine Spezialität der objektorientierten Datenbankmodelle (s.u.).

Außer in Hierarchien können Klassen in objektorientierten Modellen noch in Bereiche gruppiert werden. Diese Bereiche werden etwa Subsysteme, subjects [2] oder cluster [1] genannt.

Objektorientierte Analyse und objektorientierter Entwurf

Verfahren zur objektorientierten Modellierung eines Anwendungsbereiches kann man auftrennen in die objektorientierte Analyse (OOA [2], was soll modelliert werden ?) und den objektorientiert Entwurf (object-oriented design, OOD [1], wie soll es modelliert werden ?). Die gängigen Verfahren können wiederum in Adaptionen von bekannten daten- oder funktionsorientierten Entwurfsverfahren, eine Mischung aus beiden Verfahren (etwa [3] oder eigenständige Verfahren für objektorientierte Modelle [2, 1] eingeteilt werden. In OOA und OOD müssen drei Problembereiche berücksichtigt werden:

• die Modellierung von Strukturen, etwa Klassen und ihre Anordnung in Hierarchien,
• die Modellierung von Funktionen, etwa die Methoden der einzelnen Klassen, sowie
• die Modellierung des Gesamtverhaltens des Systems.

Während etwa [2] sich auf die Analyse von Strukturen beschränkt, werden in [1] auch die Funktionen modelliert. Die Spezifikation des Gesamtverhaltens ist in diesem Verfahren nur unzureichend berücksichtigt.

Spezifikation des dynamischen Verhaltens

Ein Schritt in diese Richtung sind Verfahren zur Spezifikation des dynamischen Verhaltens einer Datenbankanwendung. Diese sind teilweise noch unabhängig von objektorientierten Modellen. In [5] werden etwa dynamische Integritätsbedingungen beschrieben, die die Spezifikation der Evolution einer Datenbank über ihre gesamte Lebensdauer hinweg liefern können. Diese Spezifikation kann in ein relationales Datenbankschema umgesetzt werden, wenn im verwendeten Datenbanksystem Trigger-Mechanismen zur Verfügung stehen, die bei Eintreten bestimmter Ereignisse und unter bestimmten Bedingungen die in der Spezifikation festgelegten Aktionen ausführen können. in [6] wird diese Technik auf objektorientierte Datenbanken ausgeweitet, indem die Lebensläufe einzelner Objekte in temporaler Logik spezifiziert werden.

Spezielle Datenbankeigenschaften im objektorientierten Entwurf

Speziell für objektorientierte Datenbankmodelle [4] gibt es noch einige zusätzliche Eigenschaften, die in den bisher vorgestellten OOA-, OOD- oder Spezifikationsverfahren noch nicht berücksichtigt wurden. So muß der objektorientierte Datenbankentwurf

1. den Entwurf von Klassenhierarchien unterstützen, d.h. die Teilmengenbeziehung zwischen den Objektmengen zweier Klassen kontrollieren (in herkömmlichen objektorientierten Modellen gibt es keine Teilmengenbeziehung, da ein Objekt nur zu genau einer Klasse gehören darf),
2. die Objekt-Evolution ermöglichen, d.h. den kontrollierten Wechsel eines Objektes zwischen den verschiedenen Klassen einer Klassenhierarchie (Rollenwechsel des Objektes)
3. die Schema-Evolution ermöglichen, d.h. die kontrollierte Veränderung des objektorientierten Datenbankschemas unter weitgehender Beibehaltung der unter dem alten Schema gespeicherten Objekte und ihrer Informationen, und
4. durch Anfragen oder Sichten abgeleitete Klassen in den Entwurf mit einbeziehen.

Die Punkte 2 und 3 werden durch die langfristig ausgerichteten Datenbankanwendungen nötig: im Gegensatz u objektorientierten Programmiersprachen, die Objekte während eines Programmablaufs modellieren, muß durch die Forderung der Persistenz die Evolution eines Objektes beziehungsweise eines ganzen Datenbankschemas möglich sein.

Der Punkt 4 ist ein typisches Datenbank-Feature: Informationen können nicht nur in gespeicherter Form vorliegen sondern auf vielfältige Weise durch Anfragen oder Sichtdefinitionen abgeleitet werden [4]. Diese abgeleiteten Klassen werden in herkömmlichen Entwurfstechniken noch im Schema direkt spezifiziert und "blähen" in vielen Fällen das Datenbankschema unnötig durch redundante Informationen auf

Fazit

Der objektorientierte Datenbankentwurf integriert den bisher getrennten Entwurf von Strukturen und Funktionen eines Systems. Zusätzlich kann das Gesamtverhalten des Systems etwa durch dynamische Integritätsbedingungen spezifiziert werden. Die Integration dieser drei Bereiche ist nicht immer vollständig gelungen. Weiterhin sind bisher einige datenbankspezifische Bereiche wie Objekt-Evolution und abgeleitete Klassen in den eher auf objektorientierte Programmiersprachen zugeschnittene Verfahren noch nicht ausreichend berücksichtigt.

                   Artikelanfang  Seitenanfang

Literatur

1. Booch, G.: Object-Oriented Design - with Applications. Redwood City, CA: Benjamin/Cummings 1991
2. Coad, P., Yourdon, E.: Object-Oriented Analysis, Englewood Cliffs: Prentice-Hall 1991
3. Ferstl, O.K., Sinz, E.J.: Ein Vorgehensmodell zur Objektmodellierung betrieblicher Informationssysteme im Semantischen Objektmodell (SOM), Wirtschaftsinformatik 6, 477-491 (1991)
4. Heuer, A.: Objektorientierte Datenbanken - Konzepte, Modelle, Systeme. Bonn: Addison-Wesley 1992
5. Lipeck, U.W.: Dynamische Integrität von Datenbanken - Grundlagender Spezifikation und Überwachung. Informatik-Fachberichte, Band 209, Berlin: Springer 1989
6. Saake, G.: Descriptive specification of database object behaviour. Data Knowl. Eng. 6, 47-73 (1991)
7. Thalheim, B.: Konzepte des Datenbank-Entwurfs, in: G. Vossen, K.-U. Witt (Hrsg.): Entwicklungstendenzen bei Datenbank-Systemen, Kapitel 1, S. 1-48. München: Oldenbourg 1991

                   Artikelanfang  Seitenanfang

Autor & Copyright
Dr. Andreas Heuer
Institut für Informatik,
TU Clausthal
Erzstraße 1
W-3392 Clausthal-Zellerfeld

© 1993 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang  Seitenanfang

Objektrelationale Datenbanksysteme

• Kurzinfo
• Erläuterung
• Fazit
• Literatur
• Autor & Copyright

Kurzinfo Objektrelationale Datenbankmanagementsysteme (DBMS) versuchen, traditionelle relationale Systeme unter Verwendung objektorientierter Konzepte erweiterbar zu gestalten, um ihnen neue Anwendungsgebiete mit komplexen Daten zu erschließen

Erläuterung

Mitte der neunziger Jahre von einigen als nächste Generation von DBMS gefeiert [10], hat sich die anfängliche Euphorie inzwischen etwas gelegt. Das Thema ist aber keinesfalls erledigt, namhafte Hersteller relationaler DBMS haben objektrelationale Konzepte in ihre Produkte integriert oder werden dies tun. Mit der in diesem Jahr anstehenden Verabschiedung wichtiger Teile von SQL3, nun besser als SQL:1999 bezeichnet, wird objektrelationale Funktionalität auch normiert [2, 6].

Die Kritik an den mageren Typsystemen traditioneller relationaler DBMS bezieht sich vor allem auf zwei Punkte. Zum einen sollen (oft sehr umfangreiche) Daten, die nicht im Rahmen von Datenbankanwendungen entstanden sind oder gepflegt werden, in Datenbanksysteme eingebunden werden. Beispiele sind Texte, Bilder, Konstruktionsdaten, XML-Dokumente oder GeoInformation, Gründe sind der integrierte Datenzugriff und die Nutzung der Persistenzmechanismen des DBMS. Zum anderen erzwingt ein zu einfaches Typsystem häufig eine unnatürliche Modellierung von an sich komplex strukturierten Daten mit entsprechenden Auswirkungen auf Verwendbarkeit und Leistung des resultierenden Systems. Das gilt auch für die traditionelle relationale Datenmodellierung, insbesondere aber für das ungenügende Zusammenspiel mit objekt-orientierten Anwendungen, deren Datenmodell ja gerade auf der Zusammenarbeit verschiedenster Datentypen beruht (impedance mismatch).

Objektorientierung und Objektpersistenz

Die Basis objektorientierter Anwendungen sind Datenobjekte, die oft sehr komplex und auf vielfache Weise miteinander verbunden sind. Ein Objekt umfaßt als Instanz einer Klasse nicht nur die zu manipulierenden Daten, sondern auch die für die Klasse definierten Operationen (Methoden); die Daten können in der Regel nur über diese Operationen angesprochen werden (Datenkapselung). Die Klassendefinition legt also das Verhalten ihrer Objekte fest, in Sprachen mit Typsystem spricht man auch von der Spezifikation nutzerdefinierter Datentypen.

Ein Objekt hat zudem eine werteunabhängige, unveränderliche Identität, die in einem gegebenen Umfeld räumlich und idealerweise auch zeitlich eindeutig ist. Die Objektidentität dient unter anderem zur Herstellung von Beziehungen zwischen Objekten über Objektreferenzen, die damit im Gegensatz etwa zu Fremdschlüsseln in relationalen Datenbanken nicht wertebezogen sind. Neben solchen Beziehungen kann ein Objekt auch direkt Teil eines anderen Objekts sein, auf diese Weise können komplex verschachtelte Objektstrukturen entstehen.

Ein Grundkonzept der Objektorientierung ist die Vererbung von Klassen in ihren verschiedenen Spielarten. Eine Klasse wird dabei mit Bezug auf eine oder mehrere andere Klassen definiert, sie erbt deren Datenstrukturen und Operationen, kann diese in Grenzen verändern und eigene hinzufügen. Objekte einer solchen Klasse lassen sich dann auch an allen Stellen verwenden, an denen Objekte einer Oberklasse nötig sind, die objektspezifisch erforderlichen Operationen werden zur Laufzeit be stimmt (Substituierbarkeit, Polymorphie und dynamisches Binden).

Für die Integration von Persistenz in objektorientierte Anwendungen gibt es im wesentlichen drei Varianten [9]. Der Gateway-Ansatz erlaubt als Middleware-Lösung die Nutzung nicht-objektorientierter, oft schon existierender Datenquellen zum Speichern von Objektdaten. Erforderlich ist dazu eine Abbildung zwischen dem objektorientierten Schema der Anwendung und dem auf einem anderen Datenmodell beruhenden Schema des Speichers, z.B. einer relationalen Datenbank. Als anwendungs- oder auch programmiersprachenzentriert kann man den Einsatz objektorientierter DBMS ansehen, der eine nahtlose Einbindung von Persistenz in Anwendungen erlaubt. Ein dritter, datenbankzentrierter Ansatz zum Speichern von Objekten ergibt sich schließlich aus der Weiter entwicklung relationaler zu objektrelationalen DBMS.

Objektrelationale Datenbanksysteme sind um nutzerdefinierte Datentypen mit Eigenschaften wie den oben genannten erweiterbar, interessant ist daneben auch die typunabhängige Verlagerung von Anwendungslogik in ein Datenbanksystem. Die Möglichkeiten eines solchen Systems sollen im folgenden anhand von SQL:1999 angedeutet werden. Für einen effizienten Datenbankbetrieb müssen neue Datentypen und Routinen durch geeignete Optimierungsmöglichkeiten unterstützt werden, die auf generischen oder nutzerdefinierbaren Zugriffsmethoden basieren.

Normierung in SQL:1999

Mit SQL:1999 werden in diesem Jahr wichtige objektrelationale Sprachmittel normiert. Dazu gehören der Umgang mit großen Datenmengen (LOB-Datentypen), nutzerdefinierte Datentypen und Datenbankroutinen, verschiedene Typgeneratoren und typisierte Tabellen. An der Normung für den integrierten Zugriff auf extern erstellte und verwaltete Daten über Dateiverweise oder sogenannte abstrakte Tabellen und für einen verbesserten Datenzugriff aus objektorientierten Programmierspachen (Vorbild SQLJ) wird dagegen noch gearbeitet [4, 5].

Das Typsystem von SQL:1999 ist unter anderem durch verschiedene Typgeneratoren und nutzerdefinierbare Datentypen erweiterbar. Letztere werden von SQL:1999 als strukturiert bezeichnet, die Attribute dieser inneren Struktur können orthogonal wiederum auf beliebigen Datentypen beruhen. Strukturierte Datentypen ermöglichen Methodendefinition, Objektidentität und -referenzierbarkeit, eine gewisse Datenkapselung und Einfachvererbung, darauf aufbauend Substituierbarkeit von Objekten und dynamisches Binden der Methoden. Die ursprünglich geplante Mehrfachvererbung wurde für SQL:1999 fallengelassen, Generik gibt es ebensowenig. Typgeneratoren dienen der Definition von Struktur-, Kollektions- und Referenzdatentypen, SQL kennt hier unbenannte Strukturen, Felder und Referenzen auf Objekte strukturierter Datentypen.

Die neuen Datentypen können analog zu vordefinierten Typen zur Definition von Attributen einer Datenbanktabelle genutzt werden, SQL erweitert auch die Datenmanipulationsmöglichkeiten entsprechend. Man beachte im übrigen, daß nutzerdefinierte Datentypen durchaus nicht dem Relationenmodell, der theoretischen Grundlage relationaler Datenbanksysteme, widersprechen, auch die Forderung nach skalaren Attributwerten (erste Normalform) ist bei genauem Hinsehen keine ernsthafte Hürde [1]. Weiterhin sei angemerkt, daß eine zu tiefe Verschachtelung von Daten mit Hilfe nutzerdefinierter Datentypen auch Probleme mit sich bringen kann, insbesondere für vom Modellierer zunächst nicht vorgesehene Ad-hoc-Anfragen, bei denen relationale Datenbanksysteme aufgrund der anwendungsneutralen Datenmodellierung traditionell stark sind.

Eine andere Art der Verwendung nutzerdefinierter Datentypen sind typisierte Tabellen. Eine solche Tabelle wird bezüglich eines strukturierten Datentyps angelegt, dessen Struktur bildet zusammen mit einem Feld zur Aufnahme von Objektidentifikatoren die Tabellenattribute. Neben der gewohnten relationalen Nutzbarkeit kann die Tabelle dann auch als Container für Werte (Objekte) des strukturierten Datentyps angesehen werden; die einzelnen Tabellentupel repräsentieren die Zustände der abgelegten Objekte, auf die Objekte sind die zugehörigen Methoden anwendbar. Mit Hilfe der bereits genannten Referenzdatentypen können Tupel typisierter Tabellen direkt angesprochen werden, die Sprache erlaubt die Nutzung dieser Referenzen bei der Datenmanipulation mit Hilfe sogenannter Pfadausdrücke als Alternative zum mengenorientierten Tabellenverbund. Pfadausdrücke lösen die Referenzen zwischen Objekten auf und erlauben das Eindringen in deren Struktur. Vererbungsbeziehungen zwischen strukturierten Datentypen können auf darauf beruhende typisierte Tabellen ausgedehnt werden; es entstehen Tabellenhierarchien, in denen Tupel einer Subtabelle automatisch auch zu jeder Supertabelle gehören (extensionale Vererbung). Typisierte Tabellen eignen sich damit insbesondere zur Ablage von Objekten objektorientierter Anwendungen, für die auch auf der Datenbankebene selbst geeignete Manipulationsmöglichkeiten, z.B. komplexe mengenorientierte Anfragen, zur Verfügung stehen sollen.

Datenbankprodukte

Die Entwicklung von SQL:1999 wurde durch bereits vorhandene Produkte beeinflußt, schließlich sind führende Hersteller relationaler DBMS in den Normungsgremien vertreten. Informix war ein Vorreiter unter den großen Herstellern, auch Marktführer Oracle und IBM (DB2) bieten seit längerem objekt-relationale Funktionen. Leider lassen die Heterogenität der verschiedenen Implementierungen und die Unterschiede zur kommenden Norm Interoperabilität nur in sehr geringem Umfang zu [7]. Es bleibt zu hoffen, daß sich das mit SQL:1999 allmählich ändert.

Die genannten Hersteller bieten neben der eigentlichen Funktionalität auch proprietäre Programmierschnittstellen und Werkzeuge an, die das Zusammenfassen nutzerdefinierter Erweiterungen in Paketen erleichtern. Solche auch von Drittanbietern und Endanwendern implementierbaren Pakete (Oracle: Cartridges, Informix: DataBlades, IBM DB2: Extenders) wurden zunächst u.a. für Text-, Zeitserien- und Bilddaten angeboten, prinzipiell ist die Technik aber für beliebige Erweiterungen verwendbar.

Nutzerdefinierbare Erweiterungen relationaler Datenbanksysteme wurden bisher vor allem im Rahmen der erwähnten Pakete von DBMS- oder Drittherstellern eingesetzt, der tagtägliche Einsatz objektrelationaler Modellierungsmöglichkeiten hält sich bisher in Grenzen. Das ist im wesentlichen auf die noch unzureichende und vor allem sehr heterogene Implementierung in den Produkten zurückzuführen, aber auch auf die oft recht komplexe physische Optimierung, etwa die Implementierung adäquater Zugriffspfade für neue Datentypen und Datenbankroutinen. Die neue SQL-Norm könnte hier auf funktionaler Ebene einen entscheidenden Schub bewirken, für eine Vereinfachung des physischen Datenbankentwurfs ist aber noch einiges an Entwicklungsarbeit zu leisten. Interessant für die weitere Entwicklung dürften unter anderem Bibliotheken neuer Datentypen und Datenbankroutinen sein [3], aber auch die verbesserte Einbindung externer Daten unter dem Stichwort der föderierten Datenbanken [8].

Fazit

Vielversprechend erscheint der Einsatz objektrelationaler Datenbanksysteme insbesondere für die schon in größerem Umfang praktizierte Integration von Texten, Bildern und anderen Daten häufig genutzter Art in relationale Datenbanken, bei der Ergänzung existierender relationaler um objektorientiert modellierte Daten oder für den objektorientierten Zugriff auf vorhandene Daten. Mit nutzerdefinierten Datentypen und objektorientierten Konzepten erlauben objektrelationale Datenbanksysteme das Abspeichern und das direkte Manipulieren von Anwendungsobjekten ebenso wie ein flexibles Auffinden und Kombinieren dieser Objekte in Anfragen. Die Datenmodelle von Datenbanksystemen und den verschiedenen objektorientierten Programmiersprachen werden jedoch trotz gemeinsamer Grundlagen aufgrund der Sprachvielfalt nie völlig übereinstimmen. Diesem Nachteil stehen Sprachunabhängigkeit, eine ausgereifte Datenbanktechnologie, reiche Anfragemöglichkeiten und Mittel zum datenzentrierten Verlagern von Typ- und Anwendungslogik in das Datenbanksystem gegenüber.

                   Artikelanfang  Seitenanfang

Literatur

1. Date, C. J., Darwen, H.: Foundation for Object/Relational Databases: The Third Manifesto. Addison-Wesley, Reading, MA, 1998
2. Eisenberg, A., Melton, J.: SQL:1999, formerly known as SQL3. ACM SIGMOD Records, 28(1), März 1999
3. ISO/IEC Final Committee Draft: Information Technology – Database Languages – SQL Multimedia and Application Packages (SQL/MM) – Part 1: Framework. Oktober 1998
4. ISO Working Draft: Information Technology – Database Languages – SQL – Part 9: Management of External Data (SQL/MED). März 1999
5. ISO Working Draft: Information Technology – Database Languages – SQL – Part 10: Object Language Bindings (SQL/OLB). März 1999
6. ISO/IEC 9075:1999: Information Technology – Database Languages – SQL – Part 2: Foundation (SQL/Foundation). 1999. To be published
7. Lufter, J.: Datentypkonzepte und funktionaler Vergleich einiger objektrelationaler Datenbanksysteme. Jenaer Schriften zur Mathematik und Informatik Math/Inf/99/02, Institut für Informatik, Friedrich-Schiller-Universität Jena, Februar 1999
8. Mattos, N.: From Object-Relational to Federated Databases. In: Tagungsband der GI-Fachtagung Datenbanksysteme in Büro, Technik und Wissenschaft (BTW), S. 185–209, Freiburg, März 1999
9. Srinivasan, V., Chang, D. T.: Object persistence in object-oriented applications. IBM Systems Journal, 36(1), 1997
10. Stonebraker, M., Moore, D.: Object-Relational DBMSs: The Next Great Wave. Morgan Kaufmann, San Francisco, CA, 1996

                   Artikelanfang  Seitenanfang

Autor & Copyright
Jens Lufter
Friedrich-Schiller-Universität Jena, Institut für Informatik,
Ernst-Abbe-Platz 1–4, D-07743 Jena
lufter@informatik.uni-jena.de

© 1999 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang  Seitenanfang

Partitionierung von Datenbanktabellen

• Erläuterung
• Literatur
• Autor & Copyright
   

Erläuterung

Neue Anwendungen, z.B. Data Warehousing, und der zunehmend weit verbreitete Einsatz integrierter betrieblicher Informationssysteme, wie etwa des SAP Systems R/3, führten zu Datenbanken im hohen Gigabyte- oder gar im Terabyte-Bereich. Das Datenvolumen selbst stellt Datenbanken kaum noch vor Probleme. Problematisch hingegen sind oftmals sehr große Tabellen mit Millionen Einträgen pro Tabelle; in der Praxis existieren bereits Datenbanken, wo eine einzelne Tabelle Milliarden Zeilen enthält [5]. Die Datenmanipulation im OLTP-Betrieb (Online Transaction Processing), aber auch eine klassische Datensicherung (Offline-Backup) oder die Reorganisation derartig großer Tabellen begrenzen zum einen die Leistung des gesamten Systems, zum anderen kann dadurch die Verfügbarkeit der Daten wesentlich eingeschränkt werden.

Es gibt verschiedene Ansätze, mit diesen Problemszenarien umzugehen: Eine mögliche Herangehensweise ist der Einsatz verbesserter Techniken u.a. zur Datensicherung und Reorganisation, etwa ein Online-Backup [4] oder eine Online-Reorganisation [6], wie von verschiedenen DBMS-Produkten bereits angeboten. Dies löst teilweise die Probleme bezüglich der Verfügbarkeit auf Datenbankebene, nicht jedoch Verfügbarkeitsprobleme und Leistungsengpässe aufgrund sehr großer Datenmengen innerhalb einer Tabelle. Deren Anwachsen kann nicht durch Löschen von Daten begrenzt werden, wenn diese aus betriebswirtschaftlichen oder rechtlichen Gründen erhaltenswert oder gar aufbewahrungspflichtig sind. Hier bietet sich das Auslagern von Daten in ein separates Archiv an, das sich auf preisgünstigeren Tertiärspeichermedien befinden kann. Archivierte Daten entlasten somit die Datenbank, sind aber weiterhin auswertbar und können bei Bedarf auch in die Datenbank zurückgeladen werden [2]. Archivierung allein löst allerdings auch nicht alle Probleme. Zum einen sind die archivierten Daten nicht mehr im gewünschten schnellen und direkten Zugriff, was sich nicht nur im Bereich Data Warehousing nachteilig auswirkt. Zum anderen bieten heutige DBMS noch keine integrierte Archivierungsfunktionalität an, was zu „aufgesetzten" Archivierungslösungen (wie in SAP R/3) mit möglichen Leistungseinschränkungen führt oder Integritätsprobleme nach sich ziehen kann.

Eine Alternative zum Erreichen von Leistungs- und Verfügbarkeitsanforderungen für sehr große Datenbanktabellen bieten deshalb Techniken zur Partitionierung bzw. Verteilung dieser Tabellen. Ursprünglich wurden Datenbankdateien partitioniert, wenn sie für eine Festplatte zu groß waren oder die Zugriffsgeschwindigkeit einer einzelnen Platte zu gering war. Das Konzept der Partitionierung wurde in wissenschaftlichen Arbeiten zu verteilten [3] und parallelen [1] Datenbanken auf Datenbanktabellen übertragen und weitergeführt. In verteilten Datenbanken geht es darum, einen großen Datenbestand geographisch zu verteilen und Rechnerknoten so zuzuordnen, daß einerseits knotenübergreifend problemlos Anfragen gestellt werden können (Verteilungstransparenz), andererseits aber aus Leistungsgründen die Daten möglichst dort verfügbar gehalten werden, wo sie vorwiegend gebraucht werden. In parallelen Datenbanken werden Daten vor dem Hintergrund paralleler Datenbankoperationen partitioniert. Die Konzepte zur Verteilung der Daten basieren auf einer Aufteilung der Tabellen, die je nach „Schnittrichtung" durch die Tabelle horizontal bzw. vertikal und entweder wertebasiert (range/hash partitioning) oder zufällig (round robin) erfolgen kann.

In jüngeren Jahren hat die Partitionierung von Datenbanktabellen auch Eingang in zentralisierte Datenbanken gefunden, zunächst vorwiegend in Gestalt vertikaler Partitionierung, um große Objekte (Large Objects, LOBs) abzuspalten und somit physisch von den „eigentlichen" Daten abzutrennen. Damit kann bei einem sequentiellen Zugriff auf die eigentlichen Daten das zu durchsuchende Datenvolumen eingeschränkt werden, jedoch nicht die Anzahl der zu durchsuchenden Datensätze. Mittlerweile wird daher auch die horizontale Partitionierung – wertebasiert oder zufällig – verstärkt in relationale DBMS integriert. Dabei stellen Partitionen eine zusätzliche Zugriffsschicht zwischen Tabellen und Table Spaces dar.

Der Ansatz kann wie folgt beschrieben werden: Eine (typischerweise sehr große) Datenbanktabelle wird mittels eines Partitionierungsschemas horizontal unterteilt, die entstehenden einzelnen Partitionen können zielgerichtet den physischen Bereichen der Datenbank, den Table Spaces, zugeordnet werden. Der Partitionierungsgedanke kann dabei auf Zugriffspfade (Indexe) übertragen werden. Verschiedene Tabellen können bei Bedarf nach gleichem Kriterium partitioniert werden (beispielsweise eine Abteilungstabelle und eine Mitarbeitertabelle jeweils nach gleichen Abteilungsnummerintervallen). Die so entstandene logische Beziehung zwischen den Partitionen der beiden Tabellen kann sich in einer Zuordnung zum gleichen Table Space widerspiegeln (Clustering). Die Partitionierung erfolgt in den bekannten DBMS-Produkten generell vollständig und disjunkt, um Datenverluste und Redundanz zu vermeiden. Beispiele für DBMSe, die eine Partitionierung unterstützen, sind DB2, Oracle, Informix und Adabas. Die Realisierungsformen und Möglichkeiten in diesen Systemen unterscheiden sich teilweise erheblich voneinander.

Insgesamt erhofft man sich von einer Partitionierung eine ganze Reihe potentieller Vorteile hinsichtlich der Leistungsfähigkeit und der Administration sehr großer Tabellen, aber auch bei der Unterstützung spezieller Anwendungen, wie beispielsweise Data Warehousing oder Archivierung. Eine partitionierte Tabelle stellt sich nicht mehr als ein großer Monolith dar, das DBMS kann durch Parallelisierung Such- und Änderungsoperationen auf einem großen Datenbestand potentiell effizienter ausführen. Durch effizientere Ausführungsstrategien können viele Anfragen auf einige wenige Partitionen der Tabelle eingeschränkt werden. Für dieses Eingrenzen ist die Optimierungskomponente des DBMS verantwortlich; es soll selbstverständlich nicht Aufgabe des Anwenders sein, hier „von Hand" zu optimieren. Die Anfrageausführung kann darüber hinaus von der Tabellenpartitionierung profitieren, wenn die globalen Tabellenindexe durch kleinere lokale Partitionsindexe ersetzt oder ergänzt werden. Aus Sicht des Administrators können bei entsprechendem physischen Design administrative Aufgaben (Backup/Recovery, Reorganisation u.a.) wesentlich feingranularer, nämlich auf Partitionsebene, ausgeführt werden. Die Datenbanktabelle wird dadurch nicht als ganzes für längere Zeit blockiert, sondern nur die einzelne, aktuell angesprochene Partition für einen vergleichsweise kurzen Zeitraum. Weiterhin ist es möglich, Partitionen einer Tabelle verschiedenen Speichermedien (unterschiedliche Leistungscharakteristika, Preis-Leistungs-Verhältnis) zuzuordnen. Dies kann u.U. als Alternative zum expliziten Archivieren von Daten dienen, wobei auf Tertiärspeicher liegende Partitionen mit einem Archiv vergleichbar sind.

Partitionierung erhöht natürlich auch die Komplexität der Datenbankadministration. Die Partitionierung als strukturelle Erweiterung erfordert die Erstellung und Pflege eines Partitionierungsschemas, welches sowohl die logische als auch die physische Ebene umfaßt. Daneben müssen Verwaltungs- und statistische Informationen auf Partitionsebene bereitgestellt werden, um durch geeignete Administrationstechniken, Zugriffsstrukturen und interne Optimierungsverfahren die gewünschten Vorteile zu erzielen. Außerdem ist für Prädikate in Datenbankanfragen intern die Partitionierung zu berücksichtigen. Aus Sicht des praktischen Einsatzes weisen existierende DBMS noch manche Defizite in bezug auf die Partitionierungskonzepte auf, wie Untersuchungen gezeigt haben. So ist u.a. das Kriterium der Datenunabhängigkeit nicht immer voll erfüllt, und der Anwender wird teils in seinen Definitions- und Änderungsmöglichkeiten eingeschränkt. Auch bei der Anfrageoptimierung wird die Tabellenpartitionierung oft noch nicht hinreichend berücksichtigt. Derartige Einschränkungen und Defizite sollten sich im Laufe der technologischen Weiterentwicklung der Produkte reduzieren, wie beispielsweise ein Vergleich zwischen Oracle8i und Oracle8 zeigt.

Die Partitionierung ist ein mächtiger Mechanismus, der einerseits einen Mehraufwand darstellt und durchdachte physische Entwurfsentscheidungen verlangt und sich andererseits wesentlich auf das Leistungsverhalten und die Verfügbarkeit des Systems – auch negativ – auswirken kann. Nicht nur die Praxis hat hier noch Nachholbedarf, auch von seiten der Wissenschaft gibt es noch Klärungsbedarf etwa für verfeinerte und angepaßte Algorithmen zur Optimierung, für die Leistungsvorhersage und für eine bessere Administrationsunterstützung. Entsprechende Forschungsarbeiten sind am laufen.

                   Artikelanfang  Seitenanfang

Literatur

1. DeWitt, D. J., Gray, J.: Parallel database systems: The future of high performance database systems. Communications of the ACM, 35(6): 85–98 (1992)
2. Herbst, A.: Anwendungsorientiertes DB-Archivieren: Neue Konzepte zur Archivierung in Datenbanksystemen. Berlin, Heidelberg: Springer 1997
3. Öszu, M. T., Valduriez, P.: Principles of Distributed Database Systems. Englewood Cliffs, New Jersey: Prentice-Hall 1991
4. Störl, U., Großmann, G.: Backup- und Recovery-Mechanismen in Datenbanksystemen: Beschreibung und Bewertung. HMD: Theorie und Praxis der Wirtschaftsinformatik, 200: 110–129 (1998)
5. Winter, R., Auerbach, K.: The Big Time. Database Programming & Design, 11(8): 36–45 (1998)
6. Zou, C., Salzberg, B.: Towards Efficient Online Database Reorganization. IEEE Bulletin of the Technical Committee on Data Engineering, 19(2): 33–40 (1996)

                   Artikelanfang  Seitenanfang

Autor & Copyright
Klaus Küspert, Jan Nowitzky
Friedrich-Schiller-Universität Jena, Institut für Informatik, Lehrstuhl für Datenbanken und Informationssysteme, Ernst-Abbe-Platz 1-4, D-07743 Jena
kuespert@informatik.uni-jena.de
nowitzky@informatik.uni-jena.de

© 1999 Informatik Spektrum, Springer-Verlag Berlin Heidelberg

                   Artikelanfang  Seitenanfang

• Erläuterung
• Literatur
• Autor & Copyright

Erläuterung

Unter einem „Datenstrom" versteht man kontinuierlich übersandte Datensätze, deren Größe, Menge sowie schnelles Aufkommen verbieten, sie vor der Verarbeitung zu speichern. Die bisherige Forschung hat in erster Linie zum Ziel, Verfahren zu entwickeln, die es erlauben, ohne Verzögerung des Datenflusses

• einen Strom auf das Vorkommen von bestimmten Daten zu überwachen und
• die Daten aus einem Strom zu analysieren.

Anwendungsgebiete

Datenströme finden sich in vielen Gebieten wie der Nachrichten- (Presse-, Börsen- und Meteorologienachrichten) oder Systemüberwachung und -steuerung (Verkehrs- und Produktionssteuerung, Logistik, Netzwerkverwaltung) und der Analyse von wissenschaftlichen Messdaten (Astronomie, Medizin, Meteorologie, u.a. zur Früherkennung von Tornados). Neue Techniken zur Vermittlung von Datenströmen werden beispielsweise zur Verfolgung von Gepäckstücken oder Paketen entwickelt, die mit (kleinen und billigen) Sendern ausgestattet sind. Presse- oder sonstige Nachrichten werden an Abonnenten als Ströme gesandt, die nach bestimmten Inhalten oder Mustern gefiltert und verteilt werden. Aus Anwendungssicht wird oft zwischen Transaktions- und Messdatenströmen unterschieden.

Transaktionsdatenströme sind kontinuierlich ausgesandte Aufzeichnungen (so genannte Log-Daten) über Transaktionen wie Kreditkartennutzung, Telefonanrufe oder Zugriffe auf Webressourcen.

Messdatenströme bestehen aus Daten, die Sensoren, Rechnernetzwerke und wissenschaftliche (astronomische, meteorologische oder medizinische) Messstationen liefern. Transaktionsdatenströme und Messdatenströme unterscheiden sich im Hinblick auf ihre Verarbeitung nicht wesentlich.

Push- contra Pull-Kommunikation

Datenströme sind zentraler Bestandteil einer neuartigen Kommunikationsform, der so genannten „Push-Kommunikation": Nur die für einen Interessenten relevanten Daten werden automatisch an diesen übersandt, sobald sie zur Verfügung stehen. Für manche Anwendungen ist dieser Ansatz der dem Web zu Grunde liegenden „Pull-Kommunikation" überlegen, bei der Datenverbraucher die von ihnen gewünschten Daten von den Datenquellen anfordern. Insbesondere angesichts der zunehmenden Informationsfülle wird vermutlich in Zukunft das Informationsbedürfnis von Nutzern durch eine Mischung von Push- und Pull-Kommunikation befriedigt werden.

Punkt-, Tupel- und XML-Ströme

In der Forschung über Datenströme werden derzeit drei komplementäre Arten von Datensätzen betrachtet: Ein Datenstrom wird als eine sehr lange oder ununterbrochene Folge entweder von Punkten (also skalaren Werten wie Zahlen oder Zeichen) oder von Tupeln oder von XML-Dokumenten (oder so genannten XML-Elementen, d.h. wohlgeformten Fragmenten von XML-Dokumenten) angesehen.

Punkt- und Tupelströme bestehen aus Datensätzen, die

• alle dieselbe Länge haben und
• „flach" sind, d.h. keine Schachtelung zulassen.

Diese Eigenschaften vereinfachen die Verarbeitung von Strömen. Punktströme können als Sonderfall von Tupelströmen angesehen werden.

Die XML-Dokumente, wie sie in vielen XML-Strömen, insbesondere bei der Überwachung von Messdaten, anzutreffen sind, haben einen geringen Textanteil. XML wird hier also als Formalismus verwendet, um verbundartige Datensätze zu spezifizieren, deren Größe und/oder Schachtelungstiefe möglicherweise unbegrenzt ist und denen eine rekursiv definierte Struktur zu Grunde liegen kann.

Wenn diese Datensätze unterschiedlich groß sind, in unterschiedlicher Weise geschachtelt sein oder eine unbestimmte Schachtelungstiefe haben können, dann stellt die Verarbeitung von XML-Strömen eine besondere Herausforderung dar.

Überwachung von Datenströmen oder Anfrageauswertung gegen Datenströme

Die Überwachung eines Datenstroms ist die Suche nach bestimmten Mustern in den übersandten Daten wie etwa Nachrichten über ein bestimmtes Land in einem Strom von Pressemeldungen, große Kurschwankungen in einem Strom von Börsendaten oder bestimmte lebensbedrohliche Wertkombinationen in einem Strom von medizinischen Messdaten. Neben „Überwachung" werden auch die Begriffe „Filtern" und „Anfragen" verwendet. In der Tat handelt es sich dabei um mehr oder weniger komplexe Anfragen, wie sie in Datenbankanwendungen zu finden sind. Es bietet sich daher an, zur Überwachung von Datenströmen die selben Anfragesprachen wie für Datenbankanfragen zu verwenden.

In der Datenstromforschung werden derzeit in erster Linie SQL für Anfragen gegen Punkt- und Tupelströme [2] und XPath für Anfragen gegen XML-Ströme [5], sowie mehr oder weniger weitgehende Vereinfachungen dieser Anfragesprachen betrachtet. Für besondere Anwendungsgebiete werden spezielle Anfragesprachen definiert.

So wurde z.B. am AT&T eine Anfragesprache namens Hancock mit dem Ziel entwickelt, in Tupelströmen über angerufene Telefonnummern Veränderungen im Benutzerverhalten zu erkennen, die auf Missbrauch hinweisen.

Datenströme stellen neue Herausforderungen für die Anfrageauswertung dar. Neue Verfahren zur Anfrageauswertung werden benötigt, die eine zeitnahe Auswertung von möglicherweise komplexen Anfragen ermöglichen und die Speicherung von Daten und/oder Zwischenergebnissen so weit wie möglich einschränken. Anfragen gegen Datenströme werden manchmal kontinuierliche Anfragen genannt, da die Anfragen ununterbrochen oder kontinuierlich gegen eintreffende Daten ausgewertet werden. Davon unabhängig ist die Frage, zu welchem Zeitpunkt der Nutzer über Antworten informiert wird. Dies kann ebenfalls kontinuierlich, in vorgegebenen Zeitintervallen, beim Eintreten bestimmter Ereignisse oder sogar nur auf explizite Anforderung des Nutzers geschehen.

Analyse von Datenströmen

Die Analyse von Datenströmen besteht darin, aus Datenströmen aggregierte Werte zu ermitteln.

Anwendungen der Datenstromanalyse sind z.B. die Trendanalyse, die Abrechnung über die Nutzung von Rechnern und Rechnernetzen sowie Verkehrswegen, die Systemüberwachung und etwa in der Astronomie oder Meteorologie die Früherkennung von Ereignissen. Wie die Datenstromanfrage verlangt die Datenstromanalyse neue platzsparenden Verfahren, die eine zeitnahe Verarbeitung ermöglichen. Die Datenstromanalyse beruht aber auf herkömmlichen Aggregationsformen.

Sichten

Die Indizierung der Daten in herkömmlichen Datenbanksystemen zur Beschleunigung des Zugriffs auf relevante Daten ist auf einem Datenstrom mit sequenziellem Zugriff nur sehr eingeschränkt möglich. Stattdessen werden manchmal Sichten oder Indizes über die Datensätze eines Datenstroms mit dem Ziel berechnet, jeden Datensatz im Strom mit geeigneten Metadaten anzureichern. Die Verwendung dieser Metadaten kann die Anfrageauswertung oder Datenanalyse beschleunigen, beispielsweise indem irrelevante Daten übersprungen werden.

Merkmale der Datenströmenanfrage und -analyse

• Einpass-Algorithmen, die mit nur einen einzigen Durchlauf über die Daten auskommen, werden angestrebt, weil sie keine oder nur eine beschränkte Speicherung der Eingabedaten benötigen.
• Änderungen an bereits ermittelten Ergebnissen (wie Antworten zu Anfragen und aggregierten Werten) sind meist ausgeschlossen. Die einzige Datenänderungsart, die meist berücksichtigt wird, ist das Hinzufügen von weiteren Datensätzen.
• So genannte „Fensterverfahren", die Auszüge mit einer bestimmten Höchstlänge (das „Fenster") aus einem Datenstrom verarbeiten, werden oft eingesetzt. Dabei wird in Kauf genommen, dass statt exakten Ergebnissen nur angenäherte ermittelt werden.
• Verfahren werden oft mittels Automaten, wie endlichen oder Kellerautomaten, formalisiert, die über einfache und eingeschränkte Speichermöglichkeiten verfügen.

Datenstrom- contra Datenbanksysteme

Die Anfrageauswertung und Analyse von Datenströmen stellt ein komplementäres Forschungsgebiet zu der Anfrageauswertung und Datenanalyse (siehe u.a. data warehouses) in Datenbanken dar. Aus praktischer Sicht ergänzt die Anfrageauswertung gegen Datenströme die Anfrageauswertung in Datenbanken, weil Datenströme gefiltert, d.h. angefragt, werden können, um eine Datenbank zu bevölkern. Der Vergleich zwischen der herkömmlichen Anfrageauswertung in Datenbanken und derjenigen gegen Datenströme ist interessant (Abb. 1).Während in Datenbanken die Daten in der Regel dauerhaft und zahlreich und die Anfragen flüchtig und gering an Zahl sind, sind bei Datenströmen die Anfragen dauerhaft und zahlreich, die Daten aber flüchtig. Publish-subscribe-Systeme, die aus Datenströmen (z.B. von Pressenachrichten) Daten gemäß Anfragen von Abonnenten filtern, speichern und aktualisieren, beruhen auf Datenbanken von Anfragen. Traditionelle Datenbanktechniken wie Indizierung können für Anfragen oder Teile von Anfragen angewandt werden. So indiziert das System XTrie [4] XPath-Anfragen. Mit solchen Indizes beschleunigt XTrie die Auswertung großer Mengen von Anfragen gegen den selben XML-Strom.

Einige Stromsysteme

Aurora [1] und STREAM [2] werten Anfragen gegen Tupelströme aus. Sie bieten Anfragealgebren mit ähnlichen Operationen wie die relationale Algebra und Fenster-basierte Aggregation an. Aurora kennt Qualitätsmerkmale (u.a. hinsichtlich der Datenrate, Exaktheit der Antwort, Verzögerung), die dazu dienen, eintreffende Tupel zu ignorieren, falls die Daten schneller eintreffen, als die Anfragen ausgewertet werden können. Aurora sammelt Statistiken, um spätere Anfrageauswertungen durch Veränderungen des Auswertungsnetzwerks zu beschleunigen. Abbildung 2 zeigt den gemeinsamen Anfrageplan zur Auswertung zweier Anfragen Q₁ und Q₂ im STREAM-System, wobei Q₁ eine Selektion über einen Verbund der Ströme R und S und Q₂ einen Verbund über die Ströme R, S und T darstellt.

Weitere Tupelstromsysteme sind Gigascope, Hancock, NetFlow, OpenCQ, SEQ, SWAT, Telegraph und Tribecca.

SPEX [5] wertet XPath-Anfragen gegen XML-Ströme aus. XPath-Anfragen werden zuerst in so genannte ForwardXPath-Anfragen übersetzt, die keine Rückwärtsachsen (wie parent oder ancestor) enthalten. Aus solchen Anfragen werden Netzwerke von Kellerautomaten generiert, wie in Abbildung 3 gezeigt, die einen XML-Strom wie folgt verarbeiten.

Jeder Automat leitet den XML-Strom unverändert oder annotiert (d.h. mit Zusatzzeichen ergänzt) an die Automaten weiter, die ihn folgen. Der erste Automat in annotiert den Anfang des ersten Elements; der letzte Automat out fügt die berechneten Antwortteilen zusammen. Die Automaten nutzen ihre Keller, um die Tiefe und/oder relative Position der Elemente im XML-Strom zu ermitteln und durch Annotationen zu markieren. So können u.a. Geschwisterbeziehungen (z.B. das nächste „child") erkannt und weitergegeben werden. Zu einem or- oder and-Automat gehört ein cd-or- bzw. cd-and-Automat, welches das Ergebnis entsprechend verknüpft. Die als Ergebnis zu liefernden Elemente werden vom als Box dargestellten Automat ermittelt. SPEX kann XPath-Anfragen mit Prädikaten gegen XML-Ströme von unbegrenzter Tiefe und Größe auswerten. Die kombinierte Zeit- und Speicherkomplexität der SPEX-Anfrageauswertung wächst polynomiell in Länge und Anzahl der XPath-Anfragen. SPEX wird auch zur Auswertung von angenäherten Antworten unter Verwendung von Fensterverfahren eingesetzt.

XMLTK [3] übersetzt mehrere XPath-Anfragen ohne Prädikate in einen einzigen deterministischen endlichen Automaten, der alle Anfragen gegen einen XML-Strom auswertet. Da die Anzahl der Zustände des erzeugten Automaten exponentiell in der Größe der Anfragen wächst, wurde eine „träge" (lazy) Automatenerzeugung entwickelt.

Weitere XML-Stromsysteme sind MatchMaker, NiagaraCQ, XPush, XSM, XTrie und YFilter. Alle ermöglichen eine gemeinsame Auswertung von gemeinsamen Teilanfragen.

                   Artikelanfang  Seitenanfang

Literatur

1. Aurora, http://www.cs.brown.edu/research/aurora/
2. STREAM, http://www-db.stanford.edu/stream/
3. XMLTK, http://xmltk.sourceforge.net/
4. Chan, C.-Y., Felber, P., Garofalakis, M., Rastogi, R.: Efficient filtering of XML documents with XPath expressions. Proc. of Int. Conf. on Data Engineering (ICDE), 2002
5. Olteanu, D., Furche, T., Bry, F.: An efficient single-pass query evaluator for XML data streams. Proc. of ACM Symposium on Applied Computing (SAC), 2004

Hinweis: Die URLs entsprechen dem Stand bei der Veröffentlichung des Artikels und werden nicht aktualisiert.