A logic-based incremental approach to graph repair

En savoir plus sur le livre

Graph repair, the process of restoring a graph's consistency, is essential in various fields of computer science. In model-driven engineering, for instance, the abstract syntax of models is often represented using graphs. Flexible editing operations can lead to temporary inconsistencies, necessitating graph repair. Similarly, in graph databases, updates might violate integrity constraints, prompting the need for repair. We propose a logic-based incremental approach to graph repair, providing a comprehensive overview of least-changing repairs that is sound and complete upon termination. Consistency is formalized through graph conditions equivalent to first-order logic on graphs. Our approach includes two types of repair algorithms: state-based repair, which restores consistency without regard to the update history, and delta-based repair, which considers this history explicitly. Our algorithms build on an existing model generation algorithm for graph conditions implemented in AutoGraph. Additionally, the delta-based method introduces satisfaction (ST) trees to represent how a graph meets a graph condition. We demonstrate the incremental manipulation of these STs in response to graph updates, highlighting the effectiveness of our approach in maintaining graph consistency.