To read this content please select one of the options below:

Graph rewriting rules for RDF database evolution: optimizing side-effect processing

Jacques Chabin (LIFO, Universite d’Orleans, Orléans, France)
Cédric Eichler (LIFO, Universite d’orleans, Orléans, France and INSA Centre Val de Loire, Bourges, France)
Mirian Halfeld Ferrari (LIFO, Universite d’Orléans, Orléans, France)
Nicolas Hiot (LIFO, Universite d’Orléans, Orléans, France and Ennov Labs, Ennov France, Paris, France)

International Journal of Web Information Systems

ISSN: 1744-0084

Article publication date: 19 August 2021

Issue publication date: 1 December 2021




Graph rewriting concerns the technique of transforming a graph; it is thus natural to conceive its application in the evolution of graph databases. This paper aims to propose a two-step framework where rewriting rules formalize instance or schema changes, ensuring graph’s consistency with respect to constraints, and updates are managed by ensuring rule applicability through the generation of side effects: new updates which guarantee that rule application conditions hold.


This paper proposes Schema Evolution Through UPdates, optimized version (SetUpOPT), a theoretical and applied framework for the management of resource description framework (RDF)/S database evolution on the basis of graph rewriting rules. The framework is an improvement of SetUp which avoids the computation of superfluous side effects and proposes, via SetUpoptND, a flexible and extensible package of solutions to deal with non-determinism.


This paper shows graph rewriting into a practical and useful application which ensures consistent evolution of RDF databases. It introduces an optimised approach for dealing with side effects and a flexible and customizable way of dealing with non-determinism. Experimental evaluation of SetUpoptND demonstrates the importance of the proposed optimisations as they significantly reduce side-effect generation and limit data degradation.


SetUp originality lies in the use of graph rewriting techniques under the closed world assumption to set an updating system which preserves database consistency. Efficiency is ensured by avoiding the generation of superfluous side effects. Flexibility is guaranteed by offering different solutions for non-determinism and allowing the integration of customized choice functions.



Work supported by the French National Research Agency, under grant ANR-18-CE23-0010 and developed in the context of DOING@DIAMS group.


Chabin, J., Eichler, C., Halfeld Ferrari, M. and Hiot, N. (2021), "Graph rewriting rules for RDF database evolution: optimizing side-effect processing", International Journal of Web Information Systems, Vol. 17 No. 6, pp. 622-644.



Emerald Publishing Limited

Copyright © 2021, Emerald Publishing Limited

Related articles