Sven Schneider-Winden Book order

Graph repair, restoring consistency of a graph, plays a prominent role in several areas of computer science and beyond: For example, in model-driven engineering, the abstract syntax of models is usually encoded using graphs. Flexible edit operations temporarily create inconsistent graphs not representing a valid model, thus requiring graph repair. Similarly, in graph databases--managing the storage and manipulation of graph data--updates may cause that a given database does not satisfy some integrity constraints, requiring also graph repair. We present a logic-based incremental approach to graph repair, generating a sound and complete (upon termination) overview of least-changing repairs. In our context, we formalize consistency by so-called graph conditions being equivalent to first-order logic on graphs. We present two kind of repair algorithms: State-based repair restores consistency independent of the graph update history, whereas deltabased (or incremental) repair takes this history explicitly into account. Technically, our algorithms rely on an existing model generation algorithm for graph conditions implemented in AutoGraph. Moreover, the delta-based approach uses the new concept of satisfaction (ST) trees for encoding if and how a graph satisfies a graph condition. We then demonstrate how to manipulate these STs incrementally with respect to a graph update. Die Reparatur von Graphen, die Wiederherstellung der Konsistenz eines Graphen, spielt in mehreren Bereichen der Informatik und darüber hinaus eine herausragende Rolle: Beispielsweise wird in der modellgetriebenen Konstruktion die abstrakte Syntax von Modellen in der Regel mithilfe von Graphen kodiert. Flexible Bearbeitungsvorgänge erstellen vorübergehend inkonsistente Diagramme, die kein gültiges Modell darstellen, und erfordern daher eine Reparatur des Diagramms. Auf ähnliche Weise können Aktualisierungen in Graphendatenbanken - die das Speichern und Bearbeiten von Graphendaten verwalten - dazu führen, dass eine bestimmte Datenbank einige Integritätsbeschränkungen nicht erfüllt und auch eine Graphreparatur erforderlich macht

Graphen sind in der Informatik allgegenwärtig, weshalb Methoden zur Darstellung und Untersuchung von Grapheigenschaften von großer Bedeutung sind. Besonders wichtig ist die vollautomatische Überprüfung der Erfüllbarkeit von Grapheigenschaften. In vielen Anwendungsszenarien ist es zudem wünschenswert, Graphen zu identifizieren, die bestimmte Eigenschaften erfüllen. Bei einer unendlichen Anzahl solcher Graphen ist ein kompakter Überblick anzustreben. Die Tableau-Methode für Grapheigenschaften von Lambers und Orejas ermöglicht die Entwicklung eines Algorithmus zur Generierung symbolischer Modelle. Grapheigenschaften werden in einer speziellen Logik formuliert, die auf Graphen und Graphmorphismen basiert und äquivalent zur First-Order Logic auf Graphen ist, wie sie von Courcelle eingeführt wurde. Der parallelisierbare Algorithmus ermittelt schrittweise eine endliche Menge symbolischer Modelle, wobei jedes Modell eine Menge endlicher Graphen beschreibt, die eine bestimmte Grapheigenschaft erfüllen. Diese Modelle gewährleisten Vollständigkeit, da sie alle endlichen Modelle abdecken, die die Eigenschaft erfüllen, und Korrektheit, da sie keine Graphen beschreiben, die die Eigenschaft verletzen. Zudem ist die Kompaktheit gegeben, da kein Modell von einem anderen abgedeckt wird. Der Algorithmus kann aus jedem symbolischen Modell ein minimales endliches Modell extrahieren und weitere endliche Modelle ableiten. Implementiert ist der Algor