Abstract
In the setting of graph-structured data, description logics are well suited to impose constraints that capture the semantics of the domain of interest. When the data evolves as a result of operations carried out by users or applications, it is important to ensure that the satisfaction of the constraints is preserved, analogously to the consistency requirement for transactions in relational databases. In this paper we introduce a simple action language in which actions are finite sequences of insertions and deletions performed on concept/roles, and we study static verification in this setting. Specifically, we address the problem of verifying whether the constraints are still satisfied in the state resulting from the execution of a given action, for every possible initial state satisfying them. We are able to provide a tight coNExpTime bound for a very expressive DL, and show that the complexity drops to coNP-complete for the case of extit{DL-Lite}.