Metric Temporal Graph Logic over Typed Attributed Graphs

Extended Version

Sven Schneider, Lucas Sakizloglou, Maria Maximova, Holger Giese (Autoren)

Buch | Softcover

32 Seiten

2019
Universitätsverlag Potsdam
978-3-86956-463-0 (ISBN)

Keine Verlagsinformationen verfügbar

Artikel merken

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 deltabased (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.

Erscheinungsdatum	19.11.2020
Reihe/Serie	Technische Berichte des Hasso-Plattner-Instituts für Softwaresystemtechnik an der Universität Potsdam ; 127
Verlagsort	Potsdam
Sprache	englisch
Maße	210 x 297 mm
Gewicht	140 g
Themenwelt	Mathematik / Informatik ► Informatik ► Theorie / Studium
Schlagworte	metric temporal logic • Nested graph conditions • runtime monitoring • sequence properties • symbolic graphs • temporal logic • typed attributed graphs
ISBN-10	3-86956-463-6 / 3869564636
ISBN-13	978-3-86956-463-0 / 9783869564630
Zustand	Neuware