Planning in graph databases under description logic constraints

Abstract

Graph databases are gaining increasing importance and they are fundamental for storing, for example, web data in RDF form, but also other forms of semi-structured data. Given the very large amount of data currently available in these stores, efficient management of these data becomes harder and harder. In addition, the development of automated management tools for them is becoming a pressing problem. As in traditional databases, integrity constraints on graph databases are important to capture the semantics of domain of interest. One of the tools to modify this data are transactions. A transaction encapsulates a sequence of modifications to the data which are executed and committed as a unit. Description Logics (DLs) are decidable languages that have been strongly advocated for managing data repositories, for expressing integrity constraints and they are particularly natural for talking about graph databases, as argued in some recent work. A challenging topic is planning in such context. Planning is a classical topic and has been an important problem in Artificial Intelligence for over five decades. In this thesis, we propose a framework for planning in graph databases. To the best of our knowledge, this is the first attempt to formally define planning in such setting. We use an expressive action language that is already defined by an earlier work. This language is expressed through a DL that has the feature to introduce new values to the data. Graph databases are seen as finite DL interpretations. We identify some interesting reasoning tasks, relevant for the setting we consider. The standard one is plan-existence, which corresponds in trying to find a plan for a given instance of a planning problem. We investigate two variants of the problem. The difference between them is that in one of them we do not allow the transactions to introduce fresh constants. We prove that deciding plan-existence for the variation without fresh constants is PSpace-complete. After applying several syntactic restrictions, we are able to determine NlogSpace and NP-hard cases. We are also able to provide several polynomial algorithms for some other cases. In addition, to get some insights to the relationship between our formalism and STRIPS, which is a classical approach to planning, we investigate whether planning in our setting can be reduced to STRIPS. We show that such encoding is possible under some syntactical restrictions. In this way, STRIPS planners can be exploited to solve our planning problem. Furthermore, we study the variation, where the transactions are allowed to introduce fresh constants. Intuitively, this makes planning more involved. We are able to single out some cases in this setting that can be reduced to planning without fresh constants. In this way we prove that those cases are in PSpace.