Motivation The complex structure and increasing size of information that has to be managed in today's applications calls for flexible mechanisms for storing such information, making it easily and efficiently accessible, and facilitating its change and evolution over time. The paradigm of graph structured data (GSD) [5] has gained popularity recently as an alternative to traditional relational databases that provides more flexibility and thus can overcome the limitations of an a priori imposed rigid structure on the data. Indeed, differently from relational data, GSD do not require a schema to be fixed a priori. This flexibility makes them well suited for many emerging application areas such as managing Web data, information integration, persistent storage in object-oriented software development, or management of scientific data. Concrete examples of models for GSD are RDFS [2], object-oriented data models, and XML. Here we build on recent work that advocates the use of Description Logics (DLs) for managing change in GSD that happens as the result of (agents or users) executing actions [4]. We consider GSD understood in a broad sense, as information represented by means of a node and edge labeled graph, in which the labels convey semantic information. We identify GSD with the finite structures over which DLs are interpreted, and use DL knowledge bases as descriptions of constraints and properties of the data. We express actions using a specially tailored action language in which actions are finite sequences of (possibly conditional) insertions and deletions performed on the extensions of labels. For this setting, the static verification problem, which consists on deciding whether the execution of a given action will preserve some given integrity constraints on any possible GSD, has been studied in [4]. Here we discuss further problems that can be considered as variants of planning, such as deciding whether there is a sequence of actions that leads a given structure into a state where some property (either desired or not) holds, or whether a given sequence of actions leads every structure into a state where some property necessarily holds. We develop algorithms for variations of these problems, and characterize their computational complexity. We refer the reader to [1] for the extended version of this paper, which also includes an extensive discussion of related work. Updating GSD For manipulating GSD we use a specially tailored language [1], in which a basic action can take, for example, the form (A C) for a concept name A and an arbitrary concept C. Intuitively, when this action is applied to an interpretation The work has been partially supported by FWF projects T515 and P25518, WWTF project ICT12-015, EU IP Project Optique FP7-318338, and the Wolfgang Pauli Institute.
(i.e., a GSD instance) I, the content of CI is added to AI . Similarly (A C) removes CI from AI , and there are analogous operations (p r) and (p r) on roles. These basic actions can be combined using action composition and conditional action execution K ? 1 k 2. Actions may be non-ground and contain variables, which act as parameters. The semantics is then given using substitutions in the natural way.
Given a set Act of actions, a finite interpretation I, and a goal KB K, a plan is a finite sequence of ground instances of actions from Act , whose execution leads from I to a state I0 that satisfies K. We allow to introduce fresh values in the data by expanding in I0 the domain of I with a finite set of domain elements.
Example 1. The following interpretation I represents (part of) the project database of a research institute. There are two active projects and three employees working in them.
EmplI = fe1; e3; e7g
PrjI = fp1; p2g
ActPrjI = fp1; p2g FinPrjI = fg worksForI = f(e1; p1); (e3; p1); (e7; p2)g We assume constants pi with piI = pi for projects, and analogously constants ei for employees. The KB K1 expresses constraints on this project database: all projects are active or finished, the domain of worksFor are the employees, and its range the projects.
(Prj v ActPrj t FinPrj) ^ (9worksFor:> v Empl) ^ (9worksFor :> v Prj) The following goal KB requires that p1 is not an active project, and that e1 is an employee. Consider the following actions 1 and 2; here " stands for the empty action. Action 1 moves p1 from the active to the finished projects, and removes the employees that work only for p1. Action 2 transfers an employee x from project p1 to project p2, if the necessary preliminary checks are successful.
Kg=:(p1:ActPrj) ^ e1:Empl 1=ActPrj fp1g FinPrj fp1g Empl 8worksFor:fp1g worksFor worksForjfp1g 2=(p2:Prj ^ (x; p1):worksFor) ? worksFor f(x; p1)g worksFor f(x; p2)g k " The sequence h 20; 1i is a plan for Kg from I, where 20 is the result of applying to 2 the substitution : fx 7! e1g, that is, parameter x takes the value e1. The interpretation I0 that reflects the resulting status of the data looks as follows (note that I0 j= K1 ^ Kg): EmplI = fe1; e7g
PrjI = fp1; p2g
ActPrjI = fp2g FinPrjI = fp1g worksForI = f(e1; p2); (e7; p2)g Planning Problems for GSD We define the following planning problems: (P1) Given a set Act of actions, a finite interpretation I, and a goal KB K, does there exist a plan for K from I? (P2) Given a set Act of actions and a pair Kpre , K of formulae, does there exist a substitution and a plan for (K) from some finite I with I j= (Kpre )? (P1) is the classic plan existence problem, formulated in the setting of GSD. (P2) also aims at deciding plan existence, but rather than the full actual state of the data, we have as an input a precondition KB, and we are interested in deciding the existence of a plan from some of its models. To see the relevance of (P2), consider the complementary problem: a ‘no’ instance of (P2) means that, from every relevant initial state, (undesired) goals cannot be reached. For instance, Kpre = Kic ^ x : FinPrj and K = x : ActPrj may be used to check whether, starting with a GSD that satisfies the integrity constraints Kic and contains some finished project p, it is possible to make p an active project again.
Unfortunately, these problems are undecidable already for DL-Lite KBs and a quite
restricted form of actions. For (P1), the intuition behind this is that we do not know
how many fresh objects we need to add to the domain of I. If we put a bound on the
number of these fresh objects, we regain decidability. (P2) remains undecidable even if
the domain is fixed, but it becomes decidable if we place a bound on the length of plans.
(P1b) Given a set Act of actions, a finite interpretation I, a goal KB K, and a positive
integer k, does there exist a plan for K from I such that at most k elements are
added to the domain of I?
(P2b) Given a set of actions Act , a pair Kpre ; K of formulae, and a positive integer k,
does there exist a substitution and a plan of length at most k for (K) from
some finite interpretation I with I j= (Kpre )?
In what follows, we assume that the integers k given as bounds are encoded in unary. The
problem (P1b) is PSPACE-hard already for settings more restricted than DL-Lite, and it can
be solved in polynomial space even for the very expressive ALCHOIQbr (an extension
of ALCHOIQ with further role constructors and Boolean KBs). Note that the problem
is not harder than deciding plan existence in standard planning formalisms such as
propositional STRIPS [
Next we consider problems that are related to ensuring that plans always achieve a goal K, given a possibly incomplete description Kpre of the initial data. They are variants of the so-called conformant planning, which deals with incomplete information. The first such problem is to ‘certify’ that a candidate plan is always a plan for the goal. (C) Given a sequence P of actions and formulae Kpre , K, is (P ) a plan for (K) from every finite interpretation I with I j= (Kpre ), for every substitution ? Finally, we are interested in deciding the existence of a plan that always achieves the goal, for every possible state satisfying the precondition. Solving this problem corresponds to the automated synthesis of a program for reaching a certain condition. This is formalized via the following problems: (S) Given a set Act of actions and formulae Kpre , K, does there exist a sequence P of actions from Act such that (P ) is a plan for (K) from every finite I with I j= (Kpre ), for every substitution ? (Sb) Given a set Act of actions, formulae Kpre ; K, and a positive integer k, does there exist a sequence P of actions from Act such that (P ) is a plan for (K) of length at most k, from every finite I with I j= (Kpre ), for every substitution ? Problem (S) is undecidable already for DL-Lite. For ALCHOIQbr, (C) and (Sb) are complete for coNEXPTIME. For DL-Lite, (C) is complete for coNP and (Sb) for NPNP. Conclusions We believe this work provides powerful tools for analyzing the effects of executing complex actions on GSD in the presence of integrity constraints expressed in DLs. Interesting lines for further research are developing practicable algorithms and identifying meaningful restricted fragments of lower complexity, in particular tractable fragments.