## Managing Change in Graph-structured Data Using Description
Logics

**Shqiponja Ahmetaj, Diego Calvanese, Magdalena Ortiz, and Mantas
Simkus**
*ACM Trans. on Computational Logic. 18(4):27:1--27:35*
2017.

In this paper, we consider the setting of graph-structured data
(GSD) that evolves as a result of operations carried out by users
or applications. We study different reasoning problems, which range
from deciding whether a given sequence of actions preserves the
satisfaction of a given set of integrity constraints, for every
possible initial data instance, to deciding the (non-)existence of
a sequence of actions that would take the data to an (un)desirable
state, starting either from a specific data instance or from an
incomplete description of it. For describing states of the data
instances and expressing integrity constraints on them, we use
Description Logics (DLs) closely related to the two-variable
fragment of first-order logic with counting quantifiers. The
updates are defined as actions in a simple yet flexible language,
as finite sequences of conditional insertions and deletions, which
allow one to use complex DL formulas to select the (pairs of )
nodes for which (node or arc) labels are added or deleted. We
formalize the above data management problems as a static
verification problem and several planning problems and show that,
due to the adequate choice of formalisms for describing actions and
states of the data, most of these data management problems can be
effectively reduced to the (un)satisfiability of suitable formulas
in decidable logical formalisms. Leveraging this, we provide
algorithms and tight complexity bounds for the formalized problems,
both for expressive DLs and for a variant of the popular DL-Lite,
advocated for data management in recent years.

@article{TOCL-2017,
title = "Managing Change in Graph-structured Data Using Description
Logics",
year = "2017",
author = "Shqiponja Ahmetaj and Diego Calvanese and Magdalena Ortiz
and Mantas Simkus",
journal = "ACM Trans. on Computational Logic",
pages = "27:1--27:35",
number = "4",
volume = "18",
doi = "10.1145/3143803",
}

pdf
url