Reasoning over Evolving Graph-structured Data Under Constraints
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.