Sustaining and improving graduated graph consistency: A static analysis of graph transformations

TY - JOUR

T1 - Sustaining and improving graduated graph consistency: A static analysis of graph transformations

AU - Kosiol, Jens

AU - Strüber, Daniel

AU - Taentzer, Gabriele

AU - Zschaler, Steffen

N1 - Funding Information: We thank the anonymous reviewers for their helpful comments. This work was partially funded by the German Research Foundation (DFG), project “Triple Graph Grammars (TGG) 2.0” and research fellowship with project number 413074939 . Publisher Copyright: © 2021 Elsevier B.V. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2022/2/1

Y1 - 2022/2/1

N2 - Where graphs are used for modelling and specifying systems, consistency is an important concern. To be a valid model of a system, the graph structure must satisfy a number of constraints. To date, consistency has primarily been viewed as a binary property: a graph either is or is not consistent with respect to a set of graph constraints. This has enabled the definition of notions such as constraint-preserving and constraint-guaranteeing graph transformations. Many practical applications -- for example model repair or evolutionary search -- implicitly assume a more graduated notion of consistency, but without an explicit formalisation only limited analysis of these applications is possible. In this paper, we introduce an explicit notion of consistency as a graduated property, depending on the number of constraint violations in a graph. We present two new characterisations of transformations (and transformation rules) enabling reasoning about the gradual introduction of consistency: while consistency-sustaining transformations do not decrease the consistency level, consistency-improving transformations strictly reduce the number of constraint violations. We show how these new definitions refine the existing concepts of constraint-preserving and constraint-guaranteeing transformations. To support a static analysis based on our characterisations, we present criteria for deciding which form of consistency-ensuring transformations is induced by the application of a transformation rule. We validate our contributions in the context of an application in search-based model engineering.

AB - Where graphs are used for modelling and specifying systems, consistency is an important concern. To be a valid model of a system, the graph structure must satisfy a number of constraints. To date, consistency has primarily been viewed as a binary property: a graph either is or is not consistent with respect to a set of graph constraints. This has enabled the definition of notions such as constraint-preserving and constraint-guaranteeing graph transformations. Many practical applications -- for example model repair or evolutionary search -- implicitly assume a more graduated notion of consistency, but without an explicit formalisation only limited analysis of these applications is possible. In this paper, we introduce an explicit notion of consistency as a graduated property, depending on the number of constraint violations in a graph. We present two new characterisations of transformations (and transformation rules) enabling reasoning about the gradual introduction of consistency: while consistency-sustaining transformations do not decrease the consistency level, consistency-improving transformations strictly reduce the number of constraint violations. We show how these new definitions refine the existing concepts of constraint-preserving and constraint-guaranteeing transformations. To support a static analysis based on our characterisations, we present criteria for deciding which form of consistency-ensuring transformations is induced by the application of a transformation rule. We validate our contributions in the context of an application in search-based model engineering.

UR - http://www.scopus.com/inward/record.url?scp=85116640698&partnerID=8YFLogxK

U2 - 10.1016/j.scico.2021.102729

DO - 10.1016/j.scico.2021.102729

M3 - Article

SN - 0167-6423

VL - 214

JO - SCIENCE OF COMPUTER PROGRAMMING

JF - SCIENCE OF COMPUTER PROGRAMMING

M1 - 102729

ER -