## Verification of Evolving Graph-structured Data under Expressive
Path Constraints

**Diego Calvanese, Magdalena Ortiz, and Mantas Simkus**
*Proc. of the 19th Int. Conf. on Database Theory (ICDT 2016).
Volume 48 of Leibniz International Proceedings in Informatics
(LIPIcs).* 2016.

Integrity constraints play a central role in databases and,
among many other applications, are fundamental for preserving data
integrity when databases evolve as a result of operations
manipulating the data. In this context, an important task is that
of static verification, which consists in deciding whether a given
set of constraints is preserved after the execution of a given
sequence of operations, for every possible database satisfying the
initial constraints. In this paper, we consider constraints over
graph-structured data formulated in an expressive Description Logic
(DL) that allows for regular expressions over binary relations and
their inverses, generalizing many of the well-known path constraint
languages proposed for semi-structured data in the last two
decades. In this setting, we study the problem of static
verification, for operations expressed in a simple yet flexible
language built from additions and deletions of complex DL
expressions. We establish undecidability of the general setting,
and identify suitable restricted fragments for which we obtain
tight complexity results, building on techniques developed in our
previous work for simpler DLs. As a by-product, we also obtain new
(un)decidability results for the implication problem of path
constraints, and improve previous upper bounds on the complexity of
the problem.

@inproceedings{ICDT-2016,
title = "Verification of Evolving Graph-structured Data under Expressive
Path Constraints",
year = "2016",
author = "Diego Calvanese and Magdalena Ortiz and Mantas Simkus",
booktitle = "Proc. of the 19th Int. Conf. on Database Theory (ICDT 2016)",
pages = "15:1--15:19",
volume = "48",
publisher = "Schloss Dagstuhl--Leibniz-Zentrum für Informatik",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
doi = "10.4230/LIPIcs.ICDT.2016.15",
}

pdf
url