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) [8] has gained popularity recently as an alternative to traditional relational DBs 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 [4], 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 [7] that happens as the result of (agents or users) executing actions. 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. In 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 [7]. Here, we discuss further problems that can be considered as variants of planning, such as deciding if there is a sequence of actions that leads a given structure into a state where some property (either desired or not) holds, or deciding 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 consider both the case of known and arbitrary initial state. We show that existence of a plan (of unbounded length) is undecidable even for lightweight DLs and a simple forms of actions. Motivated by this we study planning for plans of bounded length, and provide tight complexity bounds for the considered variants of the problem. An extended version of this work, with proofs of the technical results and more detailed discussion can be found in [1].
We now introduce the DL ALCHOIQbr, which we use to describe constraints on GSD. In DLs, the domain of interest is modeled using individuals (denoting objects), concepts (denoting sets of objects), and roles (denoting binary relations between objects). We assume countably infinite sets NR of role names, NC of concept names, NI of individual names, and NV of variables. Roles are defined inductively: (i) if p 2 NR, then p and p (the inverse of p) are roles; (ii) if ft; t0g NI [ NV, then f(t1; t2)g is a role; (iii) if r1, r2 are roles, then r1 [ r2 and r1 n r2 are roles; and (iv) if r is a role and C is a concept, then rjC is a role. Concepts are defined inductively as well: (i) each A 2 NC is a concept; (ii) if t 2 NI [ NV, then ftg is a concept (called nominal); (iii) if C1, C2 are concepts, then C1 u C2, C1 t C2, and :C1 are concepts; (iv) if r is a role, C is a concept, and n is a non-negative integer, then 9r:C, 8r:C, 6n r:C, and >n r:C are concepts.
A concept (resp., role) inclusion has the form 1 v 2, where 1; 2 are concepts (resp., roles). A concept (resp., role) assertion has the form t : C (resp., (t; t0) : r), where ft; t0g NI [ NV, C is a concept, and r is a role. Concepts, roles, inclusions, and assertions without variables are called ordinary. We define (ALCHOIQbr-)formulae inductively: inclusion and assertions are formulas, and if K1; K2 are formulas, so are K1 ^ K2, K1 _ K2, and :K1. A knowledge base (KB) is a formula with no variables.
Notice that ALCHOIQbr extends the expressive DL ALCHOIQ [
As usual in DLs, the semantics is given in terms of interpretations. An interpretation
is a pair I = h I ; I i, where I 6= ; is the domain, AI I for each A 2 NC,
pI I I for each p 2 NR, and oI 2 I for each o 2 NI. We make the unique
name assumption (UNA), i.e., distinct individuals are interpreted as distinct objects. For
ordinary roles f(o1; o2)g, we let f(o1; o2)gI = f(o1I ; o2I )g, and for ordinary roles rjC ,
we let (rjC )I = f(e1; e2) j (e1; e2) 2 rI and e2 2 CI g. The function I is extended to
the remaining ordinary concepts and roles in the usual way [
An interpretation I satisfies an ordinary inclusion 1 v 2, denoted I j= 1 v 2, if 1I 2I , and an ordinary assertion = o : C (resp., = (o1; o2) : r), denoted I j= , if oI 2 CI (resp., (o1I ; o2I ) 2 rI ). Satisfaction is extended to knowledge bases as follows: (i) I j= K1 ^ K2 if I j= K1 and I j= K2; (ii) I j= K1 _ K2 if I j= K1 or I j= K2; (iii) I j= :K if I 6j= K. If I j= K, then I is a model of K. The finite satisfiability problem is to decide given a KB K if there exists a model I of K with I finite. The finite satisfiability problem for ALCHOIQbr KBs has the same computational complexity as for the standard ALCHOIQ:
We are interested in the problem of effectively managing GSDs satisfying the constraints expressed in a DL KB K. Hence, we must assume that such data are of finite size, i.e., they correspond naturally to finite interpretations that satisfy the constraints in K. In other words, we consider configurations of the GSD that are finite models of K.
Many of the reasoning problems we study here will be reduced to finite satisfiability,
which is NEXPTIME-complete for ALCHOIQbr [
Example 1. The following interpretation I1 represents (part of) the project database of a research institute. There are two active projects and three employees working in them.
PrjI1 = fp1; p2g; EmplI1 = fe1; e3; e7g;
ActivePrjI1 = fp1; p2g; FinishedPrjI1 = fg; worksForI1 = 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 ActivePrj t FinishedPrj) ^ (9worksFor:> v Empl) ^ (9worksFor :> v Prj) 3
For manipulating GSD, we use the following language. The basic actions allow one to insert or delete individuals from extensions of concepts, and pairs of individuals from extensions of roles. The candidates for additions and deletions can be chosen by means of complex concepts and roles. The language also allows for composition of actions and conditional action execution.
Definition 1 (Action language). Basic actions and (complex) actions are built according to the following grammar, where A is a concept name, C is an arbitrary concept, p is a role name, r is an arbitrary role, and K is an arbitrary ALCHOIQbr– formula. The special symbol " denotes the empty action: ! (A
C) j (A
C) j (p r) j (p r) ! j K ? ; j "
A (complex) action is called simple if (i) no (concept or role) inclusions occur in , and (ii) all concepts of are Boolean combinations of concept names, nominals, and concepts of the form 9r:>.
A substitution is a function from NV to NI. For a formula, an action or an action sequence , we use ( ) to denote the result of replacing in every occurrence of a variable x by the individual (x). An action is ground if it has no variables. An action 0 is called a ground instance of an action if 0 = ( ) for some substitution .
Intuitively, an application of an action (A C) on an interpretation I stands for the addition of the content of CI to AI . In turn, removing CI from AI can be done by applying (A C) on I. The two operations can also be performed on extensions of roles. Composition stands for successive action execution, and a conditional action K ? 1; 2 says that 1 is executed if the interpretation is a model of K, and 2 is executed otherwise. We now formally define the semantics of actions.
Definition 2. Assume an interpretation I and let E be a concept or role name. If E is a concept, let W I , and if E is a role, let W I I . Then let I E W (resp., I E W ) denote the interpretation I0 such that (i) I0 = I , (ii) EI0 = EI [ W (resp., EI0 = EI n W ), and (iii) E1I0 = E1I , for all symbols E1 6= E. For a ground action , we define a mapping S from interpretations to interpretations: S(A C) (I) = S (I S(A C) (I) = S (I
A CI )
A CI ) S"(I) = I
SK? 1; 2 (I) = S(p r) (I) = S (I p rI ) S(p r) (I) = S (I p rI ) (S 1 (I); if I j= K;
S 2 (I); if I 6j= K:
Note that we have not defined the semantics of actions with variables. In our approach, all variables of an action are seen as parameters whose values are given before execution by a substitution with actual individuals, i.e., by grounding.
The static verification problem amounts to checking, given a KB K and an action ,
that for every finite model I of K and every ground instance 0 of , S 0 (I) j= K, i.e.,
the execution of preserves the satisfaction of the constraints expressed by K.
Theorem 1 ([
The proof of this theorem relies on a regression technique that incorporates into a given K the effects of an action , and reduces reasoning about its effects on any structure satisfying K to reasoning about a single KB. In particular, static verification is reduced to finite KB unsatisfiability. This regression technique is also the main tool for most upper bounds in the next section, but we must omit proofs due to lack of space. 4
When data evolves, there may be desirable states that we want to ensure, or undesirable states that we want to avoid. For example, a finished project should never be made active again. We tackle such issues next, through some planning problems. We use DLs to describe states of KBs, which may act as goals or preconditions. A plan is a sequence of actions from a given set, whose execution leads from the current state to a state that satisfies a given goal. To support unbounded introduction of fresh values in the data, we allow for the domain to be expanded with a finite set of domain elements. Definition 3. Let I = h I ; I i be a finite interpretation, Act a finite set of actions, and K a KB (the goal KB). A finite sequence P = h 1; : : : ; ni of ground instances of actions from Act is called a plan for K from I (of length n), if there exists a finite set with I \ = ; such that S 1 n (I0) j= K, where I0 = h I [ ; I i. Example 2. Recall I1 and K1 from Example 1. 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. Action 1 moves p1 from the active to the finished projects, and removes the employees working only for p1 from the corresponding tables. Action 2 transfers e1 from project p1 to project p2 (only if the necessary preliminary checks are successful).
Kg = :(p1:ActivePrj) ^ e1:Empl 1 = ActivePrj fp1g FinishedPrj fp1g worksFor worksForjfp1g Empl
:9worksFor:Prj 2 =(p2:Prj ^ (e1; p1):worksFor) ? worksFor f(e1; p1)g worksFor f(e1; p2)g;" The sequence h 2; 1i is a plan for Kg from I1, and the interpretation S 2 1 (I1) that reflects the resulting status of the data looks as follows. Note that S 2 1 (I1) j= K1 ^ Kg.
We define the next 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 : FinishedPrj and K = x : ActivePrj may be used to check whether starting with GSD that satisfies the integrity constraints and contains some finished project p, it is possible to make p an active project again.
Unfortunately, these problems are undecidable in general.
Theorem 2. (P1) and (P2) are undecidable, already for DL-Lite KBs and simple actions.
To regain decidability, we define ‘bounded’ versions of these problems. (P1) becomes decidable if the size of in Definition 3 is bounded. (P2) remains undecidable even for = ;, but it becomes decidable if we place a bound on the length of plans. In the following we assume numbers are coded in unary. (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 where j j k? (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 )?
The problem (P1b) can be solved in polynomial space for ALCHOIQbr, and a
matching lower bound holds even for settings more restricted than DL-Lite (the goal is
a basic assertion a : C and only simple actions with no complex DL expressions are
allowed). Note that planning in our setting is not harder than deciding plan existence in
standard automated planning formalisms such as propositional STRIPS [
Now we establish the complexity of (P2b), both in the general setting where Kpre and K are in ALCHOIQbr, and for the restricted case of DL-Lite.
Theorem 4. The problem (P2b) is NEXPTIME-complete. It is NP-complete if Kpre ; K are expressed in DL-Lite and all actions in Act are simple.
Now 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. (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 ? Theorem 5. (i) Problem (S) is undecidable, already for DL-Lite KBs and simple actions. (ii) Problems (C) and (Sb) are coNEXPTIME-complete. (iii) If Kpre ; K are expressed in DL-Lite and all actions in Act are simple, then (C) is in coNP and (Sb) is in NPNP.
The upper bounds in the third item are tight for an extension of DL-Lite that allows to use regression for capturing action effects. We omit details due to lack of space. 5
We believe this work provides powerful tools for analyzing the effects of executing complex actions on graph structured data, possibly in the presence of integrity constraints expressed in DLs. The considered problems are intractable even for restricted fragments of DL-Lite and forms of actions. However, these are worst case bounds, and we believe that practicable algorithms can still be obtained. In our future work we want to verify this, and identify meaningful restrictions to regain tractability.