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

Abstract

Purpose

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.

Design/methodology/approach

This paper proposes Schema Evolution Through UPdates, optimized version (SetUp_OPT), 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.

Findings

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.

Originality/value

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.

Citation

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. https://doi.org/10.1108/IJWIS-03-2021-0033