Transaktionen sind ein fundamentales Konzept in Datenbanksystemen, das auch im Bereich der Betriebssysteme und Programmiersprachen zunehmende Beachtung findet [6]. Ein Programm wird als Transaktionsprogramm und eine aus seiner Ausführung resultierende Folge von Aktionen als Transaktion bezeichnet, wenn das zugrundeliegende Laufzeitsystem dafür bestimmte Eigenschaften gewährleistet [2, 3]: Aus der Sicht des Anwenders und des Anwendungsprogrammierers sind Transaktionen atomar, persistent und untereinander isoliert, d.h. die Effekte einer Transaktion kommen selbst im Fall eines Systemzusammenbruchs stets entweder vollständig oder gar nicht zum Tragen (Atomarität), nach erfolgreicher Beendigung einer Transaktion wird die Dauerhaftigkeit aller Änderungen permanenter Daten garantiert (Persistenz), und schließlich werden unerwünschte Wechselwirkungen mit parallelen Transaktionen durch geeignete Systemmaßnahmen ausgeschlossen (Isolation. Darüber hinaus kann ein Programm bei negativem Resultat anwendungsspezifischer Konsistenzprüfungen auch von sich aus den Abbruch einer Transaktion erzwingen (Konsistenzerhaltung). Diese Eigenschaften des Transaktionskonzepts werde in der Literatur auch unter dem Begriff „ACID-Prinzip" (Atomicity, Consistency, Isolation, Durability) zusammengefaßt [3].

Eine typische Anwendung, bei der sich das Transaktionskonzept bewährt hat, sind beispielsweise Flugreservierungssysteme, wobei einzelne Transaktionen im allgemeinen relativ kurz sind. Im Zusammenhang mit komplexeren, sogenannten „Non-Standard"-Anwendungen sowie der Verwendung von Transaktionen als allgemeines Programmierinstrument wurde jedoch die berechtigte Kritik laut, daß das klassische Transaktionskonzept in verschiedener Hinsicht zu unflexibel ist [5]. Geschachtelte Transaktionen bieten demgegenüber die Möglichkeit, daß Aktionen selbst wiederum Transaktionen sein können und somit - zumindest teilweise - die Eigenschaften Atomarität, Persistenz und Isolation haben. Das klassische Beispiel einer geschachtelten Transaktion ist die „Urlaubsbuchung" [2]. Abbildung 1 zeigt die Struktur dieses Transaktionstyps.

Abb. 1 Struktur einer geschachtelten Transaktion

Innerhalb einer solchen Transaktion ist der Flug zu buchen, ein geeignetes Hotel am Zielort muß ausfindig gemacht werden, und schließlich gilt es, nach den günstigsten Mietwagenangeboten zu recherchieren und eine Reservierung vorzunehmen. Jeder dieser Schritte ist eine Subtransaktion der gesamten Anwendungstransaktion, wobei die Flugbuchung wiederum zwei Subtransaktionen für den Hinflug und den Rückflug beinhaltet. Die Basistransaktionen dieses Transaktionsbaums, d. h. diejenigen Subtransaktionen, die selbst keine weiteren Subtransaktionen haben, bestehen - wie herkömmliche „flache" Transaktionen - aus einer Folge von Operationen auf den jeweiligen Datenbeständen, z.B. Lese- und Schreibzugriffe auf Speicherseiten einer Datenbank. Dieses Grundmodell wird in der Literatur häufig dahingehend eingeschränkt, daß elementare Datenoperationen nur innerhalb von Basistransaktionen zulässig sind. Da man Datenzugriffe in Nichtbasistransaktionen stets durch Erzeugen einer zusätzlichen Subtransaktion an Stelle der Zugriffsaktion vermeiden kann, ist dies keine wesentliche Restriktion.

Geschlossen geschachtelte Transaktionen

Die konventionelle Realisierung einer „Urlaubsbuchung" als flache Transaktion hat zwei entscheidende Nachteile: zum einen führt jede Fehlersituation während ihres Ablaufs zwingend zum Zurücksetzen der gesamten Anwendungstransaktion; und zum anderen müssen die einzelnen Teilschritte in der Regel nacheinander ausgeführt werden, wenn die Möglichkeit nicht ausgeschlossen werden kann, daß verschiedene Aktionen zum Teil auf dieselben Daten zugreifen (unter Einschluß von systeminternen Daten wie z.B. Zugriffspfaden). Geschachtelte Transaktionen in der vor allem durch [4] bekannt gewordenen Form, die auch "geschlossen geschachtelte Transaktionen" genannt werden, beseitigen diese beiden Schwachpunkte des klassischen Transaktionskonzepts. Sie erlauben flexiblere Rücksetzmöglichkeiten im Sinne des altbekannten "Savepoint"-Konzepts [2], und sie gestatten es, Subtransaktionen derselben Anwendungstransaktion parallel auszuführen.

Subtransaktionen haben in diesem Ansatz - unabhängig von ihrer Schachtelungstiefe - die Eigenschaft der Atomarität. Persistenz dagegen wird lediglich für die gesamte Anwendungstransaktion garantiert. Ein in einer Subtransaktion aufgetretener Fehler führt zunächst nur zum Zurücksetzen der direkt betroffenen Subtransaktionen. Dies wird der unmittelbaren Vatertransaktion mitgeteilt, die daraufhin entscheiden kann, die gescheiterte Subtransaktion neu zu starten oder ihre eigene Rücksetzung zu veranlassen. Je nach der gerade vorliegenden Schachtelungstiefe ergeben sich somit zu jedem Zeitpunkt i.a. mehrere potentielle Intratransaktions-Rücksetzpunkte. Die Möglichkeit, Fehler gewissermaßen lokal, d.h. innerhalb von Subtransaktionsgrenzen zu handhaben, macht sich insbesondere in einem verteilten System bezahlt. Im „Urlaubsbuchungs"-Szenario z.B. liegt die Annahme nahe, daß Flugbuchung, Hotelreservierung und Mietwagenreservierung in verschiedenen Rechnern ablaufen. Bei einem lokalen Fehler während der Ausführung der „Mietwagen"-Subtransaktion (z.B. Rechnerausfall, lokaler Deadlock o.ä.) genügt es, nur die betroffene Subtransaktion zurückzusetzen und erneut zu starten.

In einem verteilten System - sowie generell zur besseren Ressourcenauslastung - drängt es sich förmlich auf, die verschiedenen Aktionen einer „Urlaubsbuchung" zumindest teilweise parallel auszuführen. Eine wesentliche Voraussetzung für diese Art der Intratransaktions-Parallelität ist, daß es zwischen den parallelen Aktionen ein- und derselben Anwendungstransaktion keinerlei Konflikte bei den Zugriffen auf gemeinsam benutzte Daten und Speicherstrukturen gibt. Da diese Bedingung gerade auf die Eigenschaft der Isolation von Transaktionen hinausläuft, garantiert die Ausführung von Aktionen als Subtransaktionen in der Tat, daß diese voneinander isoliert sind, ohne dabei die Parallelität unnötig einzuschränken. Im Beispiel könnten die drei Schritte „Flug", „Hotel" und „Mietwagen" gleichzeitig angestoßen werden, und innerhalb der „Flug"-Subtransaktion könnten wiederum die Buchung des „Hinflugs" und des „Rückflugs" parallel erfolgen, sofern geeignete „Concurrency-Control"-Maßnahmen angewandt werden, wie z.B. die in [4] vorgeschlagene Erweiterung des klassischen strikten Zweiphasen-Sperrprotokolls. Sperren werden dabei jeweils bis zum Ende einer Subtransaktion gehalten, so daß parallele Subtransaktionen desselben Vaters voneinander isoliert sind. Bei Beendigung einer Subtransaktion werden Sperren an die jeweilige Vatertransaktion „vererbt" und erst beim Ende der gesamten Anwendungstransaktion endgültig freigegeben. Wegen dieser von herkömmlichen Transaktionen gewohnten - strengen Isolation paralleler Anwendungstransaktionen untereinander wird diese Variante geschachtelter Transaktionen auch die „geschlossene" genannt.

Offen geschachtelte Transaktionen

Geschachtelte Transaktionen in der „geschlossenen" Variante tragen im wesentlichen nichts zur Erhöhung der Parallelität zwischen Anwendungstransaktionen (Intertransaktions-Parallelität) bei, da alle im Laufe der Ausführung von Subtransaktionen erworbenen Sperren bis zum Ende der gesamten Anwendungstransaktionen gehalten werden. Gerade bei langen bzw. interaktiven Transaktionen, wie sie geschachtelte Transaktionen typischerweise sind, ist dies aber ein kritischer Punkt. Im Beispiel der „Urlaubsbuchung" etwa würde eine Sperre auf einem Zähler für die Anzahl freier Plätze eines bestimmten Fluges alle anderen Anwendungstransaktionen, die diesen Flug buchen wollen, blockieren - und zwar wegen des stattfindenden Benutzerdialogs u.U. sehr lange. Ein Ansatz, solche Blockierungen weitgehend zu vermeiden, bzw. erheblich zu verkürzen, besteht darin, zwar nach wie vor parallele Subtransaktionen untereinander zu isolieren, aber die erworbenen Sperren jeweils beim Ende einer Subtransaktion freizugeben und damit die strenge Isolation gegenüber anderen Anwendungstransaktionen fallenzulassen. Unmittelbar nach Abschluß der Flugbuchung könnten dann bereits andere „Urlaubsbuchungen" auf diese Flugdaten zugreifen, selbst wenn die zugehörige Anwendungstransaktion noch im Gang ist. Wegen der vorzeitigen Sichtbarkeit von Änderungen wird diese Variante als die Methode der „offen geschachtelten Transaktion" bezeichnet.

Zwei schwerwiegende Probleme sind bei diesem Ansatz zu lösen. Zum einen können beendete Subtransaktionen immer noch durch den Abbruch eines Vorfahren zurückgesetzt werden. Da aber inzwischen parallele Anwendungstransaktionen auf der Grundlage der vorzeitig freigegebenen Änderungen weitere Modifikationen durchgeführt haben könnten, scheint eine Lawine kaskadenartiger „Rückrufaktionen" unvermeidlich. Die Lösung des Problems besteht darin, an Stelle herkömmlicher zustandsorientierter „Recovery"-Methoden für jede bereits beendete zurückzusetzende Subtransaktion eine weitere Subtransaktion zu starten, die die erfolgten Änderungen kompensiert. Eine Flugreservierung wird z.B. durch eine Stornierung wieder aus der Welt geschafft, und solche inverse Aktionen bzw. Kompensations-Subtransaktionen sind - bis auf wenige Ausnahmen mit irreversiblen Effekten - in der Regel immer möglich.

Das zweite Problem der offen geschachtelten Transaktionen ist die vermeintliche Aufgabe der Serialisierbarkeit als Korrekturkriterium, d.h. der Äquivalenz der parallelen Abläufe zum sequentiellen Einbenutzer-Betrieb. Die Lösung dieses Problems besteht in der Anwendung einer semantischen Concurrency-Control-Methode auf die abgeschlossenen Subtransaktionen entsprechenden abstrakten Aktionen, so daß die „abstrakte Serialisierbarkeit" der gesamten offen geschachtelten Transaktionen bzw. die Korrektheit im allgemeineren Sinn sichergestellt ist [1, 6].

Mehrschichten-Transaktionen

Ein wichtiger Spezialfall der offen geschachtelten Transaktionen, bei dem die Erzeugung von Subtransaktionen durch die Struktur des zugrundeliegenden Systems bestimmt ist, sind „Mehrschichten-Transaktionen". Zugrundegelegt wird eine Schichtenarchitektur, in der einzelne Operationen einer bestimmten Schicht jeweils durch Folgen von Operationen der nächsttieferen Abstraktionsebene implementiert sind. In einer dementsprechenden Mehrschichten-Transaktionen wird für jede Aktion der höheren Schicht eine Subtransaktion auf der jeweils darunterliegenden Implementierungsebene gebildet. Dieses Prinzip wird von Schicht zu Schicht fortgesetzt, so daß alle Basistransaktionen dieselbe Schachtelungstiefe haben. Der Vorteil dieser festen Struktur ist, daß man nun gegenüber dem allgemeinen Konzept der offen geschachtelten Transaktionen vergleichsweise einfach geeignete Protokolle für die Isolation von Anwendungstransaktionen entwickeln kann [1]. Dabei sind Anwendungstransaktionen im allgemeinen „nur" auf dem Abstraktionsniveau der Anwendungsoperationen (d.h. der obersten Schicht) serialisierbar, was jedoch für den Benutzer vollkommen ausreicht und den darunterliegenden Schichten größeren Freiraum für die parallele Ausführung von Subtransaktionen gibt. Eine ausführliche Diskussion der Implementierungsaspekte von Mehrschichten-Transaktionen ist in [6] zu finden.

Artikelanfang Seitenanfang

Literatur

Beeri, C. Schek, H.-J., Weikum, G.: Multi-Level Transaction Management - Theoretical Art of Practical Need? Proc. Int. Conf. Extending Database Technology (Lecture Notes in Computer Sience, Vol. 303). Berlin, Heidelberg, New York: Springer 1988
Gray, J.: The Transaction Concept: Virtues and Limitations. Proc. Int. Conf. on Very Large Data Bases, 1981
Härder, T., Reuter, A.: Principles of transaction-oriented database recovery. ACM Comput. Surv. 15 (4), (1983)
Moss, J.E.B.: Nested Transactions: An Approach to Reliable Distributed Computing, Cambridge: MIT Press 1985
Walter, B.: Nested Transactions with Multiple Commit Points: An Approch to the Structuring of Advanced Database Applications. Proc. Int. Conf. on Very Large Data Bases, 1984
Weikum, G.: Transaktionen in Datenbanksystemen, Bonn: Addison-Wesley, 1988

Artikelanfang Seitenanfang

Autor & Copyright
G. Weikum (TH Darmstadt)

Artikelanfang Seitenanfang

GPS - Global Positioning System

Erläuterung
Literatur
Autor & Copyright

Erläuterung

Mobilität gewinnt in vielen Lebensbereichen zunehmend an Bedeutung. Die Ermittlung der aktuellen eigenen geographischen Position (beispielsweise in Höhe, Längen- und Breitengrad) ist dabei eine zentrale Aufgabe, welche über die Jahrhunderte bereits mit immer besseren Methoden gelöst wurde. Ein heute sehr gefragtes System ist GPS (global positioning system), ein satellitenbasiertes Positionsbestimmungssystem [1, 2, 3]. Es gestattet weltweit mit etwa ab 400 DM teueren handlichen Endgeräten (sogenannten GPS-Empfängern) eine kontinuierliche Echtzeit-Orts- und damit auch Geschwindigkeitsbestimmung zum Nulltarif.

Das GPS-System besteht aus drei Komponenten. Erstens, 24 GPS-Satelliten, die dem amerikanischen Verteidigungsministerium (DoD, department of defense) gehören und die von diesem für alle Nutzer kostenfrei betrieben werden. GPS-Satelliten sind weder in der Lage, Objekte zu orten, noch zu verfolgen; sie strahlen lediglich permanent einen für die terrestrische Ortsbestimmung wichtigen zeitabhängigen Code ab.

Zweitens, einigen bodengebundenen Satelliten-Beobachtungsstationen des DoD und drittens, GPS-Empfänger beliebig vieler Benutzer. Der in einem GPS-Empfänger enthaltene Minirechner ist in der Lage zu berechnen, wo sich ein Satellit zu einer gegebenen Zeit im All befindet, und welcher Code von welchem Satelliten zu welcher Zeit abgestrahlt wird. Dabei können selbst minimale Abweichungen der Satelliten von der im GPS-Empfänger berechneten theoretischen Umlaufbahn berücksichtigt werden, da diese von den stationären Erdstationen des DoD ermittelt und über die GPS-Satelliten an die mobilen GPS-Empfänger weitergeleitet werden.

Zur Ortsbestimmung empfängt ein GPS-Empfänger gleichzeitig (in einfacheren Geräten auch nacheinander) die von mehreren Satelliten abgestrahlten Codes. Empfängt ein GPS-Empfänger zum Beispiel zur Zeit t2 den Code, der von einem Satelliten A zur Zeit t1 abgestrahlt worden sein mußte, so beträgt die Signallaufzeit zwischen Senden und Empfangen t2 – t1 und der GPS-Empfänger kann seinen momentanen Abstand zu A berechnen. Im Prinzip geschieht dies nach der Formel Abstand = Lichtgeschwindigkeit x Signallaufzeit. Sind die Aufenthaltsorte und die Abstände von vier Satelliten bekannt, läßt sich daraus die eigene Position im Raum eindeutig bestimmen, da alle Punkte gleichen Abstands um einen Satelliten eine Kugel beschreiben und sich diese vier Kugeln im Raum in genau einem gemeinsamen Punkt schneiden .

So wie bisher skizziert, setzt die Abstandsmessung allerdings noch eine synchrone Uhrzeit in Satelliten und Empfänger voraus, die aber aufgrund der Forderung nach billigen GPS-Empfänger internen Uhren einerseits und der zu messenden geringen Zeiten andererseits (Signalausbreitungsgeschwindigkeit ungefähr Lichtgeschwindigkeit) heute nicht gegeben ist. Daher bedient man sich eines einfachen Tricks. Jeder Satellit enthält eine Atomuhr. (Zur Gewährleistung einer höheren Ausfallsicherheit enthalten die GPS-Satelliten tatsächlich sogar mehrere Atomuhren.) Jeder GPS-Empfänger enthält jedoch nur eine „normale" Uhr, sagen wir eine Quarzuhr. Aufgrund der Uhren-Ungenauigkeit im Empfänger erhält man durch die oben beschriebene Ortsbestimmung über vier Satelliten die (falsche) Position x1 als Ergebnis. Wurde gleichzeitig der Abstand zu einem fünften Satelliten gemessen, so kann mit diesem und drei von den vorherigen Abstandsmessungen erneut die Position bestimmt werden. Ergebnis wird die (ebenfalls falsche) Position x2 sein, wobei wegen der Uhren-Ungenauigkeit x2 ungleich x1 gelten wird. Nur wenn alle Uhren synchron wären, würde x1 = x2 gelten und die Position x1 bzw. x2 wäre der tatsächliche Aufenthaltsort des GPS-Empfängers. Diese Überlegung führt auf die Idee, nach einmal erfolgter Abstandsmessung zu 5 Satelliten die Ortsbestimmungen rein rechnerisch mehrfach durchzuführen, dabei aber jedesmal eine leicht veränderte Uhrzeit des GPS-Empfängers zugrunde zulegen. Ergeben die Ortsbestimmungen x1 = x2 , so ist die Uhrenkorrektur und der Aufenthaltsort gefunden. Tatsächlich läßt sich diese Idee statt durch einen iterativen Prozeß auch durch ein Gleichungssystem beschreiben, so daß die richtige Uhrenkorrektur direkt berechnet werden kann.

Zur Uhrensynchronisation wird also der Empfang von Signalen von einem weiteren Satelliten durchgeführt. Insgesamt wäre also zur Ortsbestimmung im Raum der Empfang von 5 Satelliten nötig. Tatsächlich lassen sich jedoch aus Plausibilitätsgründen im allgemeinen bereits bei Empfang von 4 Satelliten alle theoretisch möglichen geographischen Positionen bis auf eine einzige ausschließen. Ist darüber hinaus bekannt, daß der Empfänger sich auf der Erdoberfläche (und nicht etwa in der Luft) befindet, so reicht durch dieses Zusatzwissen bereits der Empfang von 3 Satelliten zur Ortsbestimmung aus. Leider führen eine Reihe von Störungen noch zu Genauigkeitsverlusten der GPS-Meßmethode. So ist beispielsweise die Ausbreitungsgeschwindigkeit des vom Satelliten abgestrahlten Codes zwar im Vakuum konstant, nicht aber in der Erdatmosphäre. Ein Teil der Änderungen der Ausbreitungsgeschwindigkeit in der Erdatmosphäre ist frequenzabhängig (wie bei der Passage durch die Ionosphäre), so daß die Änderungen durch Senden des Codes auf zwei Frequenzen im Empfänger berechnet und ausgeglichen werden können. Ein (kleiner) Teil (die Passage durch die Troposphäre/Wolken) läßt sich allerdings kaum berechnen. Die bei weitem größten Störungen können jedoch vom DoD absichtlich generiert werden. Mit sogenannten selective availability-Störungen kann der DoD allen GPS-Empfängern (außer den „eigenen") sowohl eine verfälschte Atomuhrzeit in den Satelliten als auch eine verfälschte Satellitenposition im All vortäuschen, so daß die Posistionsbestimmung deutlich ungenauer wird.

Glücklicherweise gilt jedoch für alle obigen Störungen, daß aufgrund der Höhe der Umlaufbahn der Satelliten in einer E-Umgebung eines Punktes auf der Erde die gleichen Störungen zu erwarten sind. Dies wird im sogenannten Differential-GPS-System wie folgt zur Erhöhung der Meßgenauigkeit in GPS-Empfängern ausgenutzt. Ein stationärer GPS-Empfänger, der seine genaue Position kennt, kann wie oben beschrieben seine geographische Position über das GPS-System bestimmen und mit der ihm bekannten genauen Position vergleichen. Auf diese Weise kann ein Soll-Ist-Vergleich der gemessenen und tatsächlichen Abstände zu jedem der (im Empfangsbereich befindlichen) Satelliten durchgeführt werden. Die Differenz ist der durch Störungen zu diesem Zeitpunkt verursachte Fehler, der für eine genauere Ortsbestimmung von allen Empfängern innerhalb dieser E-Umgebung zu berücksichtigen wäre. Existiert daher ein solcher stationärer GPS-Empfänger, der permanent die aktuellen Fehlerkorrekturen zu den empfangbaren Satelliten abstrahlt, so können GPS-Empfänger die Genauigkeit der Ortsbestimmung von ±50 m in den Zentimeterbereich verbessern.(Etwa 2 m-Genauigkeit bei E= 1000 km; Zentimeter-Genauigkeit bei E= 10 km.) Eine Möglichkeit der Bereitstellung der für Differential-GPS nötigen Korrekturdaten besteht in der Ausstrahlung dieser Information in einem standardisierten Format über Rundfunk (RDS, radio data System oder in naher Zukunft DAB, digital audio broadcast), wie dies in Deutschland bereits im Testbetrieb über RDS in einer Kooperation zwischen dem Landesvermessungsamt Nordrhein-Westfalen und dem WDR realisiert wurde.

Artikelanfang Seitenanfang

Literatur

P. K. Enge: The global positioning System: Signals, measurements, and performance. International Journal of Wireless Information Networks 1:2, pp. 83–105, 1994.
J. Hurn: GPS – a guide to the next utility. Trimble Navigation Ltd., Sunnyvale, CA94088-3642, 1989.
J. Hurn: Differential GPS explained. Trimble Navigation Ltd., Sunnyvale, CA94088-3642, 1993.

Artikelanfang Seitenanfang

Autor & Copyright
Horst Mehl,
IBM Deutschland GmbH,
Europäisches Zentrum für Netzwerkforschung (ENC),
Postfach 10 30 68,
D-69020 Heidelberg
hmehl@vnet.ibm.com

Artikelanfang Seitenanfang