Artifact-centric models for business processes recently raised a lot of attention, as they manage to combine structural (i.e. data related) with dynamical (i.e. process related) aspects in a seamless way. Many frameworks developed under this approach, although, are not built explicitly for planning, one of the most prominent operations related to business processes. In this paper, we try to overcome this by proposing a framework named Dynamic Knowledge Bases, aimed at describing rich business domains through Description Logic-based ontologies, and where a set of actions allows the system to evolve by modifying such ontologies. This framework, by o ering action rewriting and knowledge partialization, represents a viable and formal environment to develop decision making and planning techniques for DL-based artifact-centric business domains.
Classically, management of business processes always focused on work ows and
the actions/interactions that take part in them, an approach called
processcentric. One of the most prominent operations related to business processes is
planning [
Artifact-centric models for business processes recently raised a lot of
attention [
In this paper we propose an artifact-centric framework, called Dynamic Knowledge Bases, aimed at describing data-rich business domains and be a more versatile environment for planning and decision-making: the data-layer is taken care of by a DL knowledge base, while a set of actions allows the system to evolve by adding/removing assertions, as well as introducing new instances to the system. To reach our goals, and overcome the afore-mentioned limitations, our framework relies on few optimizations. First of all, although our framework is based on Description Logic, it is desirable to skip completely the use of the TBox: this would allow us to avoid executing reasoning tasks and only work with facts from the ABox, simplifying especially the transition-building process. We ful l this aspect with action rewriting, which rewrites actions and introduces a blocking query : such query (which is xed for each action) tells if, given a state, we can perform the given action and built the ending state of the transition, or if the action will lead us to an inconsistent state w.r.t. the TBox. These operations are done without calculating the ending state, and without the need of the TBox (while keeping the consistency w.r.t. it).
Secondly, while the totality of the available knowledge is necessary to asses
the consistency of the overall system, it bounds us to work with details that might
not be of interests immediately. In decision making [
The resulting framework constitutes a sound base on top of which researchers can develop new planning techniques useful for all those situations in which is necessary to manipulate both actions and data together (e.g. the decision making process in agents, composition of web services, etc.).
Dynamic Knowledge Bases (DKBs) are, brie y, a variation of Knowledge and
Action Bases (KABs) [
We adopt a restricted version of DL-LiteA knowledge bases [
We de ne an action as:
a: q; N E where a is the action name, q is a query called action guard, N is a set of variables which are used in an instance creation function, and E are the action e ects. The guard q is a standard conjunctive query (CQ) of the type q = 9 !y:conj(!x ; !y), where conj(!x ; !y) is a conjunction of atoms using free variables !x and existentially quanti ed variables !y, no individuals. Atoms of q uses concepts and roles found in T . Vars(q) represents the variables in q (i.e., !x [ !y), while Vars(q)69 (resp., Vars(q)9) only the set !x (resp., !y).
The set N contains variables which do not appear in q (i.e., Vars(q) \ N = ;), and which are fed to an assignment function m when the action is executed. The set E is a set of atomic e ects (i.e., atomic non-grounded ABox assertions) which is divided in two subsets: the set E of negative e ects, and the set E+ of positive e ects. All atoms of E must use variables that are in Vars(q)69, while the atoms of E+ uses variables from the set Vars(q)69 [ N . All variables are de ned over a countably in nite (object) universe V of variables. De nition 2. The transition system D is de ned as a tuple ( ; T; ; A0; )), where: (i) is the universe of individual constants; (ii) T is a TBox; (iii) is a set of states, namely ABoxes from the set AT ( AT ); (iv) A0 is the initial state; (v) ) L is a labelled transition relation between states, where L = is the set of labels containing an action instantiation a#, where a is an action from and # a variable assignment in from V to . The transition system D represent the dynamics of a DKB D. Given a state A and selected an action a, the informal semantic of a transition is: 1. extract the certain answers ans(q; T; A) of the guard q from the state A; 2. pick randomly one tuple from ans(q; T; A) and use it to initiate the variable assignment #a for the variables Vars(a) (at this point we covered only the free variables in Vars(q)69); 3. choose an assignment for the variables in N and use it to extend #a. We de ne an assignment function m(N; A) : N ! ( n adom(A)), which assigns to each variable of N an individual from which does not appear in A; 4. use #a to instantiate the e ects E and calculate Anext by applying the instantiated e ects to A.
The sets and ) are thus mutually de ned using induction (starting from A0) as the smallest sets satisfying the following property: for every A 2 and action a 2 , if exists an action instantiation a#a s.t.
Anext = A n sub(ent(E ; T )#a; A) [ E+#a
and A )l Anext, with l = a#a. a#a is called an and Anext 2 AT , then Anext 2 instantiation of a.
ent(E ; T ) represents a set of atoms derived from E , which represents all the atoms which entail one or more single negative e ects e in E w.r.t. to the TBox T . We take each single negative e ect e and, by considering e as a CQ composed only by one atom, obtain an UCQ rewT (e ) by using the query reformulation algorithm [3, Chapter 5.2]. Since we consider a single atom at a time, the algorithm produces an UCQ composed only by CQs with a single atom erew in them. Each atom erew either contains variables found in e or, in case of a role term, one of the two variables can be a non-distinguished nonshared variable represented by the symbol ` ' (never both variables). We add each atom erew to the set ent(E ; T ). Given ent(E ; T ), we calculate the set sub(ent(E ; T )#a; A) in the following way. For each atom erew in ent(E ; T ), we apply the variable transformation #a to it (the symbol ` ' remains untouched, as it is not linked to any variable that appears in #a); we then check if it exists in the ABox A an assertion such that erew#a = , assuming that the symbol ` ' can be evaluated equal to any individual ( = ind ; 8ind 2 adom(A)).
For clarity, from now on we will denote the set sub(ent(E ; T )#a; A) with Esub(#a). Notice that the set Esub(#a) is not uniquely determined, as it depends on the ABox on which it is applied. This behaviour is intentional, as our aim is to have the certainty that an assertion e marked for removal will not appear in the next state nor in the ABox Anext, nor as an inferable assertion (hT; Anexti 6j= e ); to reach such goal, we have to remove all possible assertions that entail e . The set ent(E ; T ), instead, depends only on E and T , thus it's constant and can be calculated only one time at the beginning.
As we see from the de nition of Anext, actions modify only ABox assertions: it follows that the TBox is xed, while the ABox changes as the system evolves (thus an ABox Ai is su cient to identify the state i of the system). The transition system D clearly can be in nite, as we have the possibility to introduce new constants. We call a path
a (possibly in nite) sequence of transitions over that start from A0 ( = A0 a)1#1 ::: a)n#n An). Example 1. Consider the DKB D described by the following elements and which models a simple business scenario: { the TBox T = fEmployee v :Product; Technician v Employeeg; { the ABox A0 = fTechnician(t1); Product(p1)g; { the action set composed of the following actions: create: fEmployee(x)g; fyg fProduct(y)g+
re: fEmployee(x)g fEmployee(x)g If we consider A0 as the initial state in D, then a possible transition is A0 cre)ate# A1 where: # = fx 7! t1; y 7! p2g (notice that we introduce a new individual p2), and A1 = fTechnician(t1); Product(p1); Product(p2)g.
We could also perform the action re, as it exists a proper instantiation of it by using the variable assignment # re = fx 7! t1g. The set ent(E ; T ) for the action re corresponds to the set fEmployee(x); Technician(x)g, thus Esub(# re) would be equal to fTechnician(t1)g. Performing the action instantiation would get us to the state A2fProduct(p1)g, and it's clear that hT; A2i 6j= Employee(t1). If we would simply remove the instantiated negative e ects in E # re), we wouldn't achieve the same result (as the assertion Technician(t1) would still appear in the nal state), as if the action didn't have any e ect at all. 3 3.1
Action Rewriting The rst optimization we bring to the framework regards actions, and, more speci cally, the guard q. Using the query reformulation algorithm [3, Chapter 5.2], we can transform a query q into an UCQ rewT (q) such that ans(q; T; a) = ans(rewT (q); ;; A). We then take every action a, calculate rewT (q), and, for every CQ qrew 2 rewT (q), create an action arew: qrew; N E (with N and E taken from a without modi cations). These new actions slightly modify the transition function ): the guard is now evaluated without using the TBox, and the variable assignment #arew must be taken from the certain answers ans(qrew; ;; A), while the rest of the transition function remains the same.
The second optimization regards the ending state of the transition: in the
speci cation of a DKB, actions could lead to inconsistent states. We introduce
an additional element called blocking query B, a boolean UCQ used as a block
test in the state A before performing the action: if B returns false, then we
can perform the action and have the guarantee that the ending state Anext is
consistent w.r.t. T . The building of B is based on the NI-closure of T (denoted
cln(T )) de ned in [
Notice that we treat z as an existential variable, as it does not appear in e+ and thus we have no constrains about it. 2. we check if in E there are negative e ects that could block by removing it (thus eliminating the threat of an inconsistency). by executing ans( ; ;; ent(E ; T )) and retrieve all the certain answers #E . For each #E , it means it exist an assertion E which is removed. Since we are dealing with variables (the e ects are not instantiated yet), we have to express in B under which conditions E can't block an inconsistency in Anext; we do this by adding the corresponding UCQ E (column 5 in Table 1) to B by or -connecting it to the rest of the CQs. 3. if E can't block any inconsistency (thus ans( ; ;; ent(E ; T )) = ;), then we have to express in B under which conditions there will be a inconsistency in Anext due to an assertion in A w.r.t e+; we do so by adding A (column 6 in Table 1) to B by or -connecting it to the rest of the CQs.
Note that while building the blocking query B, we could have, for the UCQs E , inequalities of the type x 6= , with the non-distinguished non-shared variable generated by ent(E ; T ). Such inequalities always evaluate to False. De nition 3. Given an action a 2 , its rewritten action arew is de ned as: arew: qrew; N; B E where qrew 2 rewT (q), and B is the blocking query of arew.
The union of all possible rewritten actions de nes the set of actions rew.
Example 2. Let's consider the action create: fEmployee(x)g; fyg fProduct(y)g+. First we calculate rewT (q), which is the UCQ Employee(x) _ Technician(x). We can now calculate the blocking query B. We see that the concept term Product of the positive e ect e+ = Product(y) takes part in the negative-inclusion assertion Employee v :Product, and, by the de nition of cln(T ), also in the assertion Technician v :Product: we thus have two assertions, Employee(y), and Technician(y). By following the procedure for building B, we have no E+ elements (as ans( ; ;; E+) = ;, and no E elements (as ans( ; ;; ent(E ; T )) = ;). The nal query is thus composed only of A elements, and is
B = Employee(y) _ Technician(y) P
P )z ) ; x x : : z9 z ; z ) ) ( P 1 x ( ( ) z ; 1 x ( ) 2 x ; z ( 1 ) 1 x ; z ( 1 1 x2 :
P A z
: 9 z
P : 9 z 1 x ( 1 x g y ) )
) )z ) ()x ;
x 1 ( ;x )1 2 z ( ( x (
z ) ; 1 x x ( 1 P ^ P
A
A
P A
P P ^ P
P P
P
P +e A()x A() ) 2 x x ()x ;( 1 x ) 2 x 2 x z ; 2 x ( 1 ) 2 x ; 1 x ( ) 2 x ; 1 x ( 1 ) 2 x ; 1 x ( 1 ) 2 x ; ) 2 x ; z ( 1 ) 2 x ; x ( 1 ) 1 x ; 2 x ( 1 ) 2 x ; 1 x ( z
z !y1 y1
!y2 y2 y2g x=16 x=1 y2 x2 x2
g =6 = z7!)^)
^ 27!)^)^ 17!P:( P: z
7!:z xf (z9 (9 zf (9 (9
P P:
z x =6 P(z9 x2^ : P(z9 x1^ : , s n o i t r e s s : 1 e l b a 7!x2 2 ^ ;yx1 y=1 17!x1 ) z z =6 ;(x1 x2 ) 2 x ; We get the following two rewritten actions: creater1ew: fEmployee(x)g; fyg; fEmployee(y) _ Technician(y)g creater2ew: fTechnician(x)g; fyg; fEmployee(y) _ Technician(y)g fProduct(y)g+ fProduct(y)g+ Esub(#arew ) [ E+#arew is consistent w.r.t. T .
Theorem 1. Given a satis able KB (T; A), an action arew 2 rew such that
#arew 2 ans(qrew; ;; A) and ans(B#arew ; ;; A) = ;, then the ABox Anext = A n
Proof. For the proof of the theorem we remind the reader to the Appendix of
the extended version of this paper [
A arew)#arew Anext, with Anext 2 AT .
Lemma 1. Given an action arew 2 rew, for every ABox A such that #arew 2 ans(qrew; ;; A) and ans(B#arew ; ;; A) = ;, we can always perform the transition
Thanks to the rewriting of actions, we can build the transition system D without the need of the TBox T , while still having the guarantee that the system is consistent w.r.t. it. 3.2
Partial Transition System We now build a partialization Dp of the transition system D, which is built in the same way as D, apart from two points: i) the initial state is a subset of the ABox A0 ii) it uses a looser transition function. (Di)e niistitohne 4u.niAverpsaertoiaflitnrdainvsidituioanl csoynstsetamntsD;p (iisi)a Ttupislea( T;BTo;x; (pi;iAi)0p; !p )i,swaheseret: of states, namely ABoxes from the set AT ( p AT ); (iv) A0p is a subset of the initial ABox A0 (A0p A0); (v) ! p L p is a labelled transition relation between states, where L = rew is the set of labels containing an action instantiation arew#, where arew is an action from rew and # a variable assignment in from V to .
As A0p A0, we have the guarantee that A0p 2 ATp. The sets p and ! are mutually de ned using induction (starting from A0) as the smallest sets satisfying the following property: for every Ap 2 p and action arew 2 rew, if exists an action instantiation arew#arew s.t.
p
Anext Ap n Esub(#arew ) [ E+#arew and Apnext 2 AT , then Apnext 2 p and Ap )l Apnext, with l = arew#arew .
p
Notice that Anext can be any subset of Ap nEsub(#arew ) [E+#arew , thus allowing to select which knowledge to focus on, unlike in D where we transfer all the knowledge from one state to another. We now de ne the existing relation between thpeintheDpp,arwteiaslatyratnhsaittionp sisysatepmropeDpr apnadrtitahleiztartaionnsitoiofna spyastthem inD. DGi(vreenspa.,patihs a proper completion of p) if: { each state Aip is a subset of the relative state Ai (Aip Ai); { each transition is caused by the same action airew and the related variable assignments are equal (#ip = #i).
Between D and Dp there is no relation such as bisimulation or even simulation; this is a clear (and intended) consequence of working with partial knowledge. This also means that we have no immediate way to know if, given a partial epxaitshts ap pinathDp , wtheactanis uaseprtohpeesracmoemapcletitoionns inps.taTnotiaotvieorncso mine tDhi,sapnrdobthleums ,ifwiet extend the de nition of the blocking query B by creating a global blocking query B p w.r.t to a nite partial path p. B p is a boolean UCQ that can be evaluated in the complete initial state A0, and, if it is evaluated False, gives us the certainty that we can use the same actions instantiations found in p starting from A0 without generating any inconsistent state w.r.t. T .
B p is built by iteratively adding the single instantiated blocking queries Bi#ip of the actions that compose p (Algorithm 1, the symbol > indicates a predicate whose evaluation is true in every interpretation). At each step, before adding the i-th instantiated blocking query Bi#ip to B p , we perform the following operations: { check that ans(B p ; ;; Ei+#p) is False;
i { remove any CQ in B p that evaluates always False (i.e., contains (in)equalities that evaluates always to False, like indi = indl, or indi 6= indi); { remove from each CQ the (in)equalities that evaluates always to True, as they do not in uence the ending result. We are sure that no CQ will be left empty, because it would mean the whole CQ would always evaluate to True, and this would have blocked the rst step; { for each CQ , generate a temporary CQ temp by removing all the (in)equalities and transform existential variables in free ones. Looking at how the blocking query is built, we have that temp is either empty ( is composed only of (in)equalities) or contains only one atomic assertion with at most one free variable. For example, if = 9z:P(i1; z) ^ i2 6= z, then temp = P(i1; z); { perform ans( temp; ;; Esub(#ip)): if it evaluates to True, then it means that the instantiated negative e ects temp, and in this case we can remove the CQ Esub(#ip) remove the atom
from B p ; if it returns answers of the type # temp = fz 7! indg, then it means that the instantiated negative e ects Esub(#ip) remove the atom temp only if z is mapped to the individual ind. We thus add to the CQ the inequality z 6= ind.
Theorem 2. Given a DKB D, a nite partial path p, and its global blocking query B p , if ans(B p ; ;; A0) = ;, then it exists a concretion of p such that 2 D.
Proof. For the proof of the theorem we remind the reader to the Appendix of
the extended version of this paper [
Example 3. Consider the DKB D described by the following elements and which models a simple business scenario:
Algorithm 1: The algorithm to build the global blocking query B p input : A partial path p output: An UCQ B p B p := f?g i := n. of transitions in p // counter variable while i > 0 do // each cycle refers to transition Aip 1 a!i#ip Aip if ans(B p ; ;; Ei+#ip) 6= ; then
B p := > // inconsistency in the i-th transition break end foreach if
2 B p do contains (in)equalities that are always False then
B p := B p n // remove CQs that are always False end remove from
temp := if ans( temp; ;; Esub(#ip)) = T rue then
(in)equalities that are always True without (in)equalities and existential operator else if ans( temp; ;; Esub(#ip)) 6= ; then
B p := B p n
// Esub(#ip) erases the CQ temp ^ z 6= ind foreach # temp = fz 7! indg 2 ans( temp; ;; Esub(#ip)) do := // update the CQ
// add the blocking query of action ai end end end B p := B p [ Bi#ip i := i 1 end { the TBox T = fStored v :Shippedg; { the ABox A0 = fProduct(p1); Stored(p1); Product(p2)g; { the action set composed by the following actions: pack: fProduct(x)g fPacked(x)g+, ship: fPacked(x)g fShipped(x)g+ which becomes the set rew composed of the actions: packrew: fProduct(x)g fPacked(x)g+, shiprew: fPacked(x)g; fStored(x)g fShipped(x)g+ At this point, we develop a partial transition system bD by considering the partial initial state A0p = fProduct(p1)g. We can perform the sequence of transitions p = A0p pa!ck# A1p sh!ip# A2p, where: # = fx 7! p1g, A1p = fPacked(p1)g, and A2p = fShipped(p1)g. The global blocking query B p is Stored(p1), and we see that, if we try to transpose p in the original ABox A0, we have ans(B p ; ;; A0) 6= ;, thus meaning that p doesn't have a proper concretion (indeed if we perform the two actions, we would end up having an inconsistent state A2).
If we would consider instead the partial initial state A0p = fProduct(p2)g, instead, we woould be able to nd a proper completion of p, as B p would be Stored(p2) and ans(B p ; ;; A0) = ;.
Given a nite partial path p and its global blocking query B p , we have a way to know if we can transform p into a complete path without actually calculating it, only by performing an UCQ over the initial state A0. Notice also that this result can be applied to all possible ABoxes, not only A0; as long as A0p is contained in an ABox A, and ans(B p ; ;; A) = ;, then it exists a path which starts from A and is a proper concretion of p. 4
In this paper we formalize a framework, called Dynamic Knowledge Bases, aimed at modelling the dynamics of artifact-centric business processes. Such framework is represented by a transition system where states are de ned by DL-LiteA knowledge bases, and where a set of actions allows the system to evolve by adding or removing assertions, along with the possibility to introduce new instances. The expressive power and reasoning services of Description Logics are very helpful to describe and manage the domain knowledge, but constitute a di cult environment to deal with when it comes to the dynamics of the processes. To tackle this problem, we introduce two optimizations, namely action rewriting and the partialization of the transition system related to a Dynamic Knowledge Base: these optimizations give us a framework where we can work with partial knowledge and where the TBox is not needed, still guaranteeing that the resulting system is consistent with it. Given a path valid for the partial transition system, we can calculate its global blocking query, and know if it can be transferred to the complete transition system without any change, and without the need to do any other calculation.
Our work does not aim to propose a planning technique, neither try to give a solution w.r.t. the decidability/undecidability problem of plan research in our environment (since it is possible to generate an in nite transition system), but to create a framework that can be used as a formal domain-independent base to develop planning and decision making techniques for data-rich business domains by taking full advantage of the DL-Lite reasoning power.
We are currently working to further expand this framework in various directions. Under the theoretical side, we are already developing an abstraction of the transition system, in particular by expressing the needed knowledge by using only queries, which can be then used over the complete transition system. Under the practical side, we intend to propose a backward planning algorithm, which takes advantage of the abstract transition system and the possibility to work with partial knowledge to return all plans of interest w.r.t. a goal.
Although further investigation is surely needed, Dynamic Knowledge Bases are a promising framework that can be usefully employed to tackle the problem of planning and decision making in artifact-centric business domains.