## Managing Change in Graph-structured Data Using Description
Logics (Long Version with Appendix)

**Shqiponja Ahmetaj, Diego Calvanese, Magdalena Ortiz, and Mantas
Simkus**
*Technical Report, arXiv.org e-Print archive. CoRR Technical
Report arXiv:1404.4274* 2014. Available at
http://arxiv.org/abs/1404.4274.

In this paper, we consider the setting of graph-structured data
that evolves as a result of operations carried out by users or
applications. We study different reasoning problems, which range
from ensuring the satisfaction of a given set of integrity
constraints after a given sequence of updates, 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. We consider an
action language in which actions are finite sequences of
conditional insertions and deletions of nodes and labels, and use
Description Logics for describing integrity constraints and
(partial) states of the data. We then formalize the above data
management problems as a static verification problem and several
planning problems. We provide algorithms and tight complexity
bounds for the formalized problems, both for an expressive DL and
for a variant of DL-Lite.

@techreport{Corr-2014-graph-data-change,
title = "Managing Change in Graph-structured Data Using Description
Logics (Long Version with Appendix)",
year = "2014",
author = "Shqiponja Ahmetaj and Diego Calvanese and Magdalena Ortiz
and Mantas Simkus",
institution = "arXiv.org e-Print archive",
number = "arXiv:1404.4274",
note = "Available at http://arxiv.org/abs/1404.4274",
}

pdf
url