Evolving Graph Databases under Description Logic Constraints

Proc. of the 26th Int. Workshop on Description Logics (DL 2013). Volume 1014 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2013.

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 DL-Lite.

@inproceedings{DL-2013-actions,
   title = "Evolving Graph Databases under Description Logic Constraints",
   year = "2013",
   author = "Diego Calvanese and Magdalena Ortiz and Mantas Simkus",
   booktitle = "Proc. of the 26th Int. Workshop on Description Logics
(DL 2013)",
   pages = "120--131",
   volume = "1014",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}