Planning and Change in Graph Structured Data under Description Logics Constraints

Shqiponja Ahmetaj, Diego Calvanese, Magdalena Ortiz, and Mantas Simkus

Proc. of the 8th Alberto Mendelzon Int. Workshop on Foundations of Data Management (AMW 2014). Volume 1189 of CEUR Workshop Proceedings, http://ceur-ws.org/. 2014.

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 present a simple yet powerful action language in which actions are finite sequences of insertions and deletions of nodes and labels, and use Description Logics for describing integrity constraints and (partial) states of the data. We then discuss the complexity of 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 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.


@inproceedings{AMW-2014-graph-dbs,
   title = "Planning and Change in Graph Structured Data under Description
Logics Constraints",
   year = "2014",
   author = "Shqiponja Ahmetaj and Diego Calvanese and Magdalena Ortiz
and Mantas Simkus",
   booktitle = "Proc. of the 8th Alberto Mendelzon Int. Workshop on
Foundations of Data Management (AMW 2014)",
   volume = "1189",
   series = "CEUR Workshop Proceedings, http://ceur-ws.org/",
}
pdf url