TY  - JOUR
A1  - Schneider, Sven
A1  - Lambers, Leen
A1  - Orejas, Fernando
T1  - A logic-based incremental approach to graph repair featuring delta preservation
JF  - International journal on software tools for technology transfer : STTT
N2  - We introduce a logic-based incremental approach to graph repair, generating a sound and complete (upon termination) overview of least-changing graph repairs from which a user may select a graph repair based on non-formalized further requirements. This incremental approach features delta preservation as it allows to restrict the generation of graph repairs to delta-preserving graph repairs, which do not revert the additions and deletions of the most recent consistency-violating graph update. We specify consistency of graphs using the logic of nested graph conditions, which is equivalent to first-order logic on graphs. Technically, the incremental approach encodes if and how the graph under repair satisfies a graph condition using the novel data structure of satisfaction trees, which are adapted incrementally according to the graph updates applied. In addition to the incremental approach, we also present two state-based graph repair algorithms, which restore consistency of a graph independent of the most recent graph update and which generate additional graph repairs using a global perspective on the graph under repair. We evaluate the developed algorithms using our prototypical implementation in the tool AutoGraph and illustrate our incremental approach using a case study from the graph database domain.
KW  - Nested graph conditions
KW  - Graph repair
KW  - Model repair
KW  - Consistency
KW  - restoration
KW  - Delta preservation
KW  - Graph databases
KW  - Model-driven
KW  - engineering
Y1  - 2021
U6  - https://doi.org/10.1007/s10009-020-00584-x
SN  - 1433-2779
SN  - 1433-2787
VL  - 23
IS  - 3
SP  - 369
EP  - 410
PB  - Springer
CY  - Berlin ; Heidelberg
ER  -