A Logic-Based Incremental Approach to Graph Repair (bibtex)
by , ,
Abstract:
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 delta-based (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.
Reference:
A Logic-Based Incremental Approach to Graph Repair (Sven Schneider, Leen Lambers, Fernando Orejas), In Fundamental Approaches to Software Engineering - 22nd International Conference, FASE 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic April 6-11, 2019, Proceedings (Reiner Hähnle, Wil M. P. van der Aalst, eds.), Springer, volume 11424, 2019.
Bibtex Entry:
@InProceedings{SLO19,
AUTHOR = {Schneider, Sven and Lambers, Leen and Orejas, Fernando},
TITLE = {{A Logic-Based Incremental Approach to Graph Repair}},
YEAR = {2019},
BOOKTITLE = {Fundamental Approaches to Software Engineering - 22nd International                Conference, FASE 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic April 6-11, 2019, Proceedings},
VOLUME = {11424},
PAGES = {151--167},
EDITOR = {Hähnle, Reiner and van der Aalst, Wil M. P.},
SERIES = {Lecture Notes in Computer Science},
PUBLISHER = {Springer},
URL = {doi.org/10.1007/978-3-030-16722-6_9},
ABSTRACT = {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\^{a}��managing the storage and manipulation of graph data\^{a}��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 delta-based (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.}
}
Powered by bibtexbrowser