Numeric methods for configuration management

Abstract

UML Klassendiagramme spielen eine zentrale Rolle im Bereich Software Engineering und werden zunehmend auch für das Modellieren von (Produkt-)Konfigurationssystemen verwendet. Eine Überprüfung formaler Eigenschaften wie der Konsistenz findet trotz ihrer Relevanz in der Regel nicht statt, da diese Fragestellungen für die verwendeten Formalismen wegen deren Ausdrucksstärke von hoher Komplexität und daher zeitintensiv sind. In dieser Dissertation beschränken wir uns daher auf ausgewählte UML Sprachelemente, die eine effiziente Behandlung zulassen. Dadurch können Entwickler bereits während der Designphase durch kontinuierliche Rückmeldungen unterstützt werden. In der vorliegenden Arbeit betrachten wir zunächst die Reduktion von Multiplizitäten. Multiplizitäten beschränken die Anzahl verbundener Objekte. Aufgrund anderer Einschränkungen (z.B. durch parallele Assoziationsketten) kommt es vor, dass diese Schranken gar nicht erreicht werden können. Dieser Umstand weist auf mögliche Modellierungsfehler hin und sollte daher vom System aufgezeigt werden. Wir entwickeln eine Methode um scharfe Multiplizitätsschranken zu berechnen. Basierend auf einer Übersetzung von Klassendiagrammen in ein lineares Ungleichungssystem beleuchten wir zuerst die Beschränkungen der Anzahl miteinander verbundener Objekte sowie die Bedeutung von zusammengesetzten Assoziationen. Danach präsentieren wir das Konzept von Assoziationsgleichungen (equality constraints), die zu redundanten Multiplizitäten führen können, und entwickeln eine Formel zur Reduktion dieser Multiplizitäten. Schlussendlich stellen wir einen Algorithmus zur Reduzierung von Assoziationsketten und Modellen vor. Wir diskutieren außerdem, welche Auswirkungen derartige Gleichungen auf die Erfüllbarkeit von Modellen und auf deren minimale Instanzen hat. Im Configuration Management sind wir nicht nur an Modellen, sondern auch an der Generierung von Instanzen (auch Konfigurationen genannt) interessiert. Das Lösen des Ungleichungssystems liefert die Anzahl der minimal benötigten Objekte pro Klasse sowie ein Intervall für die Anzahl benötigter Links je Assoziation. Wir präsentieren eine Methode, mit der diese Links unter den Objekten so aufgeteilt werden können, dass die resultierende Konfiguration eine Instanz des zugrunde liegenden Modells ist. Durch das Lösen von Minimum Cost Flow Problemen in speziellen Flussnetzwerken lassen sich dabei verschiedene Kriterien berücksichtigen. Insbesondere sind Varianten dieser Netzwerke auch dazu geeignet, Konfigurationen zu vervollständigen und zu reparieren. Diese Probleme treten etwa bei der Rekonfiguration von Altsystemen auf, wenn sich Anforderungen ändern.

UML class diagrams play a central role in software engineering and are increasingly also used for modelling (product) configuration systems. Although important, formal reasoning about class diagrams is still rarely done. A main reason is that the expressive languages used to specify models have a high computational complexity, which makes formal reasoning time-consuming and expensive. Therefore we develop efficient methods tailored to specific tasks, focusing on a limited range of U ML elements and constraints. With this approach we are able to guide the engineer through the design phase and to give immediate feedback after each change made to a diagram. We start by considering the reduction of multiplicities. Multiplicities are intervals restricting the number of connected objects. Because of additional constraints (e.g. imposed by parallel association chains) it may happen that the bounds of the intervals cannot be reached. As this may be caused by some underlying misconception this situation should be detected and eliminated. We discuss bounds on the number of connected objects and develop a method for composing associations based on the translation of class diagrams to systems of linear inequalities. Furthermore, we introduce the concept of equality constraints that may lead to redundant multiplicities and develop a formula for reducing these multiplicities. Finally, we present an algorithm for reducing association chains and models with respect to equality constraints. We also discuss the effects of equality constraints on the satisfiability of a model and its minimal instances. In configuration management we are not only interested in models, but also in generating instances (also called configurations). By solving the ILP problem formed by the system of inequalities we obtain the number of objects per class required for a minimal instance, as well as a range for the number of links for each association. In this thesis we present a method for distributing the links between the objects, such that the resulting configuration is an instance of the underlying model. We show how configuration completion and configuration repair can be addressed by solving minimum cost flow problems for certain flow networks derived from the model. This way we tackle the problem of reconfiguring legacy systems when requirements change.