Bücher der Reihe Xteubner-Texte Zur Informatik

Unendliche Mazurkiewicz Spuren stellen einen mathematischen Rahmen dar für die Untersuchung nichtterminierender nebenläufiger Systeme, z. B. verteilter Transaktionssysteme. Eine grundlegende Eigenschaft dabei ist die endliche Kontrollierbarkeit (Erkennbarkeit) des Systemverhaltens. Das vorliegende Buch behandelt den Begriff der Erkennbarkeit für unendliche Spuren aus der Sicht der Automaten mit verteilter Kontrolle. Es werden grundlegende Automaten-Konstruktionen (Determinisierung, Komplementierung) vorgestellt, und damit wird die klassische Theorie der unendlichen Sequenzen zu unendlichen Spuren erweitert.

Relationale Datenbanksysteme werden heute immer haufiger in Anwendungsberei­ chen wie Computer Aided Design (CAD), Kartographie, geographische Informations­ systeme, technische Informationssysteme, Dokumentenverwaltungssysteme usw. ein­ gesetzt, fUr welche sie ursprtinglich nicht entworfen wurden. Aile diese Anwendungs­ gebiete haben gemeinsam, daB groBe, komplex strukturierte Datenobjekte ("komple­ xe Objekte") zu verwalten sind. Heutige relationale Datenbanksysteme, mit ihrem "fiachen" Relationenmodell, konnen diese Art von Datenobjekten nicht adaquat ver­ walten, was dazu fUhrt, daB im Anwendungssystem Funktionalitaten implementiert werden mtissen, die an sich ins Datenbanksystem gehoren. Die heute auf den Markt drangenden objektorientierten Datenbanksysteme (OODBMS), aber auch die im Be­ reich der SQL-Standardisierung ("SQL 3") geplanten Erweiterungen der relationalen Datenbanksysteme behaupten jeweils, hierfUr die richtigen Losungen bereitzustel­ len, wobei technologisch teilweise sehr unterschiedliche Ansatze verfolgt werden. Der (zuktinftige) Anwender solcher Systeme ist also gut beraten, sich etwas intensiver mit den Moglichkeiten und Grenzen eines bestimmten Ansatzes zu befassen, urn im gegebenen Fall die richtige Wahl treffen zu konnen. Herr KeBler untersucht in dem vorliegenden Buch systematisch, wie sich komplexe Objekte auf den Hintergrundspeicher abbilden lassen und wie der Zugriff auf diese Objekte tiber Indexe unterstUtzt werden kann. Ein wesentliches Merkmal der von ihm entwickelten Konzepte ist die strikte Trennung von logischem und physischem Schema, die eine nachtragliche Optimierung der Speicherungsstrukturen erlaubt; ein groBes Manko heutiger OODBMS. Die Starke des vorliegenden Buches ist seine Abgeschlossenheit und Vielseitig­ keit.

konzeptionellen Entwurf, der ein Informationssystem in Schichten urn eine zentrale Datenbank herum model­ liert, gewidmet. Nach einer allgemeinen Kritik dieses Ansatzes wird der Bezug des klassischen Entwurfsansatzes zu objektorientierten Entwurfsprinzipien diskutiert.

Das Prinzip der Evolution wurde von Charles Darwin vor nur wenig mehr als hundert Jahren entdeckt. Die Lebewesen in der Natur unterliegen einer steten Veränderung, die durch Kooperation und Konkurrenz zwischen einzelnen Arten und deren Anpassungsfähigkeit an ihre Umwelt vorangetrieben wird. Inwieweit die heute existierenden Lebewesen ausschließlich durch den Evolutionsprozeß entstanden sind, ist eine philosophische und theologische Streitfrage, die in diesem Buch nicht weiter behandelt werden soll. Das grundlegende Prinzip besteht in der iterativen Abfolge von Rekom­ bination, Mutation und Selektion, wobei eine Tendenz zum Überleben der stärkeren und besseren Individuen besteht. Dieses Prinzip ist in der Natur sehr erfolgreich. Optimierung ist eine der wichtigsten Aufgaben in der modernen Industrie. Prozesse müssen schneller und sicherer ablaufen, Material wird gespart, die Produktivität soll ständig steigen. Diejenigen Firmen, denen das gelingt, haben im Wettbewerb um die Märkte die besten Überlebenschancen. Die freie Marktwirtschaft hat sich dieses Prinzip zu eigen gemacht und große Erfolge erzielt (allerdings oft zum Schaden der Umwelt, weil die dort entstandenen Schäden meistens keine finanziell meßbaren Kosten verursachen). Optimierung wird als Wissenschaft vor allem im Bereich des Operations Research untersucht. In der Mathematik sind ebenfalls viele Verfahren vorgeschlagen und entwickelt worden. Seit Mitte der 80er Jahre sind darüber hinaus Neuronale Netze zur Lösung von Optimierungspro­ blemen attraktiv geworden.

Es ist nun beinahe fünfzehn Jahre her, daß Jon Doyle mit seiner Master's Thesis den Grundstein für eine ganze Reihe unterschiedlicher Systeme legte, die alle als Truth-Maintenance-Systeme bezeichnet werden. Die Mehrzahl dieser Systeme wurde allerdings nur prozedural, ohne eine begleitende formale Untersuchung ihrer Eigenschaften vorgestellt - "at a time we weren't so formal and logical", wie es Johan de Kleer einmal ausgedrückt hat. In neueren Publikationen läßt sich zwar ein klarer Trend hin zu Beschreibungen von Truth-Maintenance-Systemen erkennen, die formale Aussagen über die Systeme ermöglichen; jedoch gibt es bis heute keinen formalen Apparat, mit dem alle diese Systeme einheitlich im Hinblick auf eine spätere Implementierung beschreibbar wären. Die vorliegende Arbeit versucht, dieses Defizit für eine Teilklasse der Truth­ Maintenance-Systeme zu beseitigen: die sogenannten monotonen Truth-Mainte­ nance-Systeme. Ausgangspunkt war eine Spezial-Vorlesung, die ich erstmals im Wintersemester 91/92 und dann erneut in stark überarbeiteter Form im Winter­ semester 92/93 an der Universität Erlangen-Nürnberg sowie im Wintersemester 95/96 an der Universität Jena gehalten habe. Mein erster Dank gilt deshalb je­ nen, die in vorderster Linie geholfen haben, diese Vorlesung zu einem Erfolg zu machen - meinen Studenten.