Lexikon

Versionsunterstützung in Datenbanken

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. 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 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 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 gegeben.

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).

Lebenszyklus eines Design-Objektes

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 Versions-Cluster eingeführt, durch die auf der Schema-Ebene eine bestimmte Teilmengen-Struktur über die Versionsmenge definiert werden kann. In 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. 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: 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.

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

Autor und Copyright

W. Wilkes (Hagen)

© 1989 Informatik Spektrum, Springer-Verlag Berlin Heidelberg