Reasoning over Evolving Graph-structured Data Under Constraints

Proc. of the 10th Alberto Mendelzon Int. Workshop on Foundations of Data Management (AMW 2016). Volume 1577 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2016.

Graph-structured data are receiving increased attention in the database community. We argue that Description Logics (DLs), which are studied extensively in Knowledge Representation, are tightly connected to graph-structured data, and provide indeed quite powerful mechanisms for expressing forms of constraints capturing domain knowledge. We draw interesting connections between expressive variants of DLs and path-constraints studied in databases, and derive new results on implication of such constraints. We then consider the challenging setting where graph-structured data evolve as a result of update operations that add and delete facts in the style of action languages, under DL constraints. In this setting, we discuss two fundamental reasoning tasks, considering both lightweight and expressive variants of DLs: verification, i.e., checking the consistency of a sequence of operations with respect to constraints; and plan existence, i.e., existence of a sequence of operations leading to a goal state.

@inproceedings{AMW-2016-keynote,
  title = "Reasoning over Evolving Graph-structured Data Under Constraints",
   year = "2016",
   author = "Diego Calvanese",
   booktitle = "Proc. of the 10th Alberto Mendelzon Int. Workshop on
Foundations of Data Management (AMW 2016)",
   volume = "1577",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}