Even sophisticated techniques start out from simple ideas. Later, in reply to application needs or theoretical problems new concepts are introduced and new formalisations proposed, often to a point where the original simple core is hardly recognizably. In this paper we provide a non-technical introduction to the basic concepts of typed graph transformation systems, completed by a survey of more advanced concepts, and explain some of its history and motivations.
Keywords: rule-based graph transformation; typed attributed graphs; application conditions and constraints; control conditions; multi objects
The ability of applications to dynamically discover required services is a key motivation for Web Services. However, this aspect is not entirely supported by current Web Services standards. It is our objective to develop a formal approach, allowing the automation of the discovery process. The approach is based on the matching of interface specifications of the required and provided services. In the present paper, we establish an integral notion of structural and behavioural compatibility of service specifications. While structural information is represented by operation declarations, behavioural descriptions are provided by contracts expressed as graph transformation rules with positive and negative application conditions. The integration of structural and behavioural descriptions is facilitated by typed and parameterised graph transformation systems, augmenting the rule-based description of behaviour by a type graph and operation declarations representing the structural aspect. The matching relation taking into account this combination is called parameterised substitution morphism. We show that substitution morphisms satisfy the semantic requirement inherent in its name: the substitutability of abstract operations by (calls to) concrete ones.
Service-oriented architectures (SOA) provide a flexible and dynamic platform for implementing business solutions. In this paper, we address the modeling of such architectures by refining business-oriented architectures, which abstract from technology aspects into service-oriented ones, focusing on the ability of dynamic reconfiguration (binding to new services at run-time) typical for SOA. The refinement is based on conceptual models of the platforms involved as architectural styles, formalized by graph transformation systems. Based on a refinement relation between abstract and platform-specific styles, we investigate how to realize business-specific scenarios on the SOA platform by automatically deriving refined, SOA-specific reconfiguration scenarios.
Model-based approaches to software development require languages and tools to support the creation and analysis, consistency management, refinement, and implementation of models. In order to provide such support in a variety of contexts, efficient ways of designing languages have to be found, accepting that languages are evolving and that tools need to be delivered in a timely fashion. Thus, an engineering approach is required which allows for the generation of such languages and tools from high-level specifications. The primary objective of the SegraVis network, a European Research Training Network on Syntactic and Semantic Integration of Visual Modelling Techniques consists in developing meta-level solutions for the definition, integration, and implementation of visual modelling techniques. These proceedings provide a selection of the contributions to the School. Supplementary materials, including copies of the presentations, exercises, and solutions, can be found at http://www.segravis.org/school.
In distributed and mobile systems with volatile bandwidth and fragile connectivity, non-functional aspects like performance and reliability become more and more important. To formalise, measure, and predict these properties, stochastic methods are required. At the same time such systems are characterised by a high degree of architectural reconfiguration. Viewing the architecture of a distributed system as a graph, this is naturally modelled by graph transformations. To address these two concerns, stochastic graph transformation systems have been introduced associating with each rule its application rate—the rate of the exponential distribution governing the delay of its application. Deriving continuous-time Markov chains, Continuous Stochastic Logic is used to specify reliability properties and verify them through model checking. In particular, we study a protocol for the reconfiguration of P2P networks intended to improve their reliability by adding redundant connections. The modelling of this protocol as a (stochastic) graph transformation system takes advantage of negative application and conditions path expressions. This ensuing high-level style of specification helps to reduce the number of states and increases the capabilities for automated analysis.
Analog zu stochastischen Petrinetzen oder Prozesskalkülen wurden stochastische Graphtransformationssysteme entwickelt, um funktionale und nichtfunktionale (insbesondere zeitabhängige und probabilistische) Aspekte von Softwaresystemen integrieren und auf hohem Abstraktionsniveau beschreiben zu können. Diese Kombination eignet sich vor allem für die Modellierung und Analyse mobiler Anwendungen, wo dynamische Rekonfiguration von Netzen an der Tagesordnung ist. Mit Hilfe von Analysewerkzeugen wie stochastischen Modelcheckern ist es möglich, Eigenschaften dieser Modelle zu überprüfen. Um diese Technik auf Systeme interessanter Größe anwenden zu können, befasst sich die vorliegende Arbeit mit der Modularisierung der stochastischen Analyse. Insbesondere wird die Korrektheit eines entsprechenden modularen Erzeugungsverfahrens gezeigt und von Experimenten berichtet, die die Überlegenheit des modularen Ansatzes belegen.
Web Services are the basic building blocks of next generation Internet applications, based on dynamic service discovery and composition. Dedicated discovery services will store both syntactic and behavioral descriptions of available services and guarantee their compatibility with the requirements expressed by clients. In practice, however, interactions may still fail because the Web Service’s implementation may be faulty. In fact, the client has no guarantee on the quality of the implementation associated to any service description. In this paper, we propose the idea of high-quality service discovery incorporating automatic testing for validating Web Services before allowing their registration. First, the discovery service automatically generates conformance test cases from the provided service description, then runs the test cases on the targetWeb Service, and only if the test is successfully passed, the service is registered. In this way, clients bind with Web Services providing a compatible signature, a suitable behavior, and a high-quality implementation.
In order to model the behaviour of open concurrent systems by means of Petri nets, we introduce open Petri nets, a generalisation of the ordinary model where some places, designated as open, represent an interface between the system and the environment. Besides generalising the token game to reflect this extension, we define a truly concurrent semantics for open nets by extending the Goltz–Reisig process semantics of Petri nets. We introduce a composition operation over open nets, characterised as a pushout in the corresponding category, suitable for modelling both interaction through open places and synchronisation of transitions. The deterministic process semantics is shown to be compositional with respect to such a composition operation. If a net Z3 results as the composition of two nets Z1 and Z2, having a common subnet Z0, then any two deterministic processes of Z1 and Z2 that ‘agree’ on the common part, can be ‘amalgamated’ to produce a deterministic process of Z3. Conversely, any deterministic process of Z3 can be decomposed into processes of the component nets. The amalgamation and decomposition operations are shown to be inverse to each other, leading to a bijective correspondence between the deterministic processes of Z3 and the pair of deterministic processes of Z1 and Z2 that agree on the common subnet Z0. Technically, our result is similar to the amalgamation theorem for data-types in the framework of algebraic specification. A possible application field of the proposed constructions and results is the modelling of interorganisational workflows, recently studied in the literature. This is illustrated by a running example.
flexible and dynamic platform for implementing business solutions. In this paper, we address the modeling of such architectures by refining business-oriented architectures, which abstract from technology aspects, into service-oriented ones, focusing on the ability of dynamic reconfiguration (binding to new services at runtime) typical for SOA. The refinement is based on conceptual models of the platforms involved as architectural styles, formalized by graph transformation systems. Based on a refinement relation between abstract and platform-specific styles we investigate how to realize business-specific scenarios on the SOA platform by automatically deriving refined, SOA-specific reconfiguration scenarios.
Modularization is a well-known concept to structure software systems as well as their specifications. Modules are equipped with export and import interfaces and thus can be connected with other modules requesting or providing certain features. In this paper, we study modules the interfaces of which consist of behavioral specifications given by typed graph transformation systems. We introduce a framework for classifying and systematically defining relations between typed graph transformation systems. The framework comprises a number of standard ingredients, like homomorphisms between type graphs and mappings between sets of graph transformation rules. The framework is applied to develop a novel concept of substitution morphism by separating preconditions and effects in the specification of rules. This substitution morphism is suited to define the semantic relation between export and import interfaces of requesting and providing modules.
The design and development of complex software systems is a difficult task, and it is not easy to ensure the quality of a developed software. The paper presents an architectural style-based approach to specifying and analyzing complex software systems. The approach is developed based on UML-like meta models and graph transformation techniques to support sound methodological principals, formal analysis and refinement. The approach is illustrated through the specification and simulation of architectural styles of mobile computing middleware, where three abstract levels of architectural styles are defined in order to decrease the complexity brought by mobility.
Web services are software components that can be discovered and employed at runtime using the Internet. Conflicting requirements towards the nature of these services can be identified. From a business perspective, Web services promise to enable the formation of ad-hoc cooperations on a global scale. From a technical perspective, a high degree of standardization and rigorous specifications are required to enable the automated integration of Web services. A suitable technology for Web services has to mediate these needs for flexibility and stability. To be usable in practice, this technology has to be aligned to standard software engineering practice to allow for a seamless development of Web service enabled components. In this paper, we introduce a new approach to the description of Web services. It is a visual approach based on the use of software models and graph transformations and allows for the flexible description of innovative services while providing a precise matching concept. A methodology enabling the seamless development of such Web service descriptions in the context of a standard model-based development approach is presented.
Web Services are composed by linking together service providers and requestors. To ensure interoperability, the requestor’s requirements for a service have to be matched against a service description offered by the provider. Besides data types and operation signatures, this requires service specifications to include behavioral information, like contracts specifying pre- and post-conditions of (required or provided) operations. In this paper, we propose to visualize contracts by graph transformation rules which blend well with a UML-based notion of data models and signatures. The operational interpretation of rules could turn out to be useful for simulating the behavior of required components in unit testing.
Model-driven software engineering requires the refinement of abstract models into more concrete, platform-specific ones. To create and verify such refinements, behavioral models capturing reconfiguration or communication scenarios are presented as instances of a dynamic meta-model, i.e., a typed graph transformation system specifying the concepts and basic operations scenarios may be composed of. Possible refinement relations between models can now be described based on the corresponding meta-models. In contrast to previous approaches, refinement relations on graph transformation systems are not defined as fixed syntactic mappings between abstract transformation rules and, e.g., concrete rule expressions, but allow for a more loose, semantically defined relation between the transformation systems, resulting in a more flexible notion of refinement.
This file has been generated by bibtex2html 1.79