Reasoning over Evolving Graph-structured Data
              Under Constraints

                              Diego Calvanese

                      Free University of Bozen-Bolzano
                          calvanese@inf.unibz.it



   Abstract. 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 con-
   nected to graph-structured data, and provide indeed quite powerful mech-
   anisms 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 implica-
   tion 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, consider-
   ing both lightweight and expressive variants of DLs: verification, i.e.,
   checking the consistency of a sequence of operations with respect to con-
   straints; and plan existence, i.e., existence of a sequence of operations
   leading to a goal state.