=Paper=
{{Paper
|id=Vol-1350/paper-62
|storemode=property
|title=Optimizations
for Decision Making and Planning in Description Logic Dynamic
Knowledge Bases
|pdfUrl=https://ceur-ws.org/Vol-1350/paper-62.pdf
|volume=Vol-1350
|dblpUrl=https://dblp.org/rec/conf/dlog/Stawowy15
}}
==Optimizations
for Decision Making and Planning in Description Logic Dynamic
Knowledge Bases==
https://ceur-ws.org/Vol-1350/paper-62.pdf
Optimizations for Decision Making and Planning
in Description Logic Dynamic Knowledge Bases
Michele Stawowy
IMT Institute for Advanced Studies, Lucca, Italy
michele.stawowy@imtlucca.it
Abstract. Artifact-centric models for business processes recently raised
a lot of attention, as they manage to combine structural (i.e. data re-
lated) 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 propos-
ing 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 offering 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.
1 Introduction
Classically, management of business processes always focused on workflows and
the actions/interactions that take part in them, an approach called process-
centric. One of the most prominent operations related to business processes is
planning [7], namely finding a sequence of operations/actions that allows to
reach a desired goal. Lately, such approach has been call into question, as the
sole focus on the workflow leaves out the informational context in which the
workflow is executed.
Artifact-centric models for business processes recently raised a lot of atten-
tion [2,6], as they manage to combine structural (i.e. data related) with dy-
namical (i.e. process related) aspects in a seamless way, thus overcoming the
limits of process-centric approach. In this context, we can see the development
of the framework called Knowledge and Actions Bases [9], the later higher for-
malization of it named Description Logic Based Dynamic Systems [5], and the
Golog-based work of [1]. These works all share the same concept: handle the
data-layer through a Description Logic ontology, while the process-layer, since
DLs are only able to give a static representation of the domain of interest, is
defined as actions that update the ontology (the so-called “functional view of
knowledge bases” [10]). The combination of these two elements generates a tran-
sition system in which states are represented by DL knowledge bases. They do
also share a similar objective: verification of temporal formulas over the afore-
mentioned transition system. Since finding a path that lead to a goal state can be
expressed as a reachability temporal formula, these environments can be used for
planning purposes, but they are not explicitly meant for this task. From their
definition, we are limited to explore the state-space in a forward manner (we
could end up having to explore the full state-space) and only by using the full
body of the available knowledge, which is not ideal for developing different ways
to search the state-space, as well as under a performance point of view.
In this paper we propose an artifact-centric framework, called Dynamic Knowl-
edge Bases, aimed at describing data-rich business domains and be a more versa-
tile 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 frame-
work 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 fulfil this
aspect with action rewriting, which rewrites actions and introduces a blocking
query: such query (which is fixed 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 [8], “an heuristic is a strategy
that ignores part of the information, with the goal of making decisions more
quickly, frugally, and/or accurately than more complex methods”. Being able to
work with partial information is vital when we deal with systems described by
complex ontologies and are composed of millions (if not more) instances. To
allow our framework to be used for such strategies we introduce partialization,
so that users can focus on a chosen subset of knowledge (partial knowledge); it
allows to build a transition system which starts from a subset of the original
ABox (the facts that describe the complete system), and, for each transition,
choose which knowledge to transfer to the next state. Lastly, we demonstrate
how, given a path found over the partial knowledge transition system, we can
calculate a global blocking query, which tells if such path can be performed in
the original transition system with no modifications.
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.).
2 Dynamic Knowledge Bases
Dynamic Knowledge Bases (DKBs) are, briefly, a variation of Knowledge and
Action Bases (KABs) [9], namely dynamic systems (more precisely labelled tran-
sition systems) in which states are constituted by DL knowledge bases (KBs),
and a set of actions that makes the system evolve by modifying those KBs.
Definition 1. A DKB is a tuple D = (T, A0 , Γ ), where (T, A0 ) is a DL-LiteA
KB, while Γ is a finite set of actions.
We adopt a restricted version of DL-LiteA knowledge bases [4], which does
not use attributes (available in full DL-LiteA KBs). DL-LiteA employs the
Unique Name Assumption, thus equality assertions are not allowed. We adopt
DL-LiteA as it is, like other DL-Lite dialects, quite expressive while maintaining
decidability, good complexity results, and enjoys the FOL-rewritability prop-
erty. In the followings, the set adom(A) identifies the individual constants in
the ABox A, which are defined over a countably infinite (object) universe ∆
of individuals (it follows that adom(A) ⊆ ∆). AT denotes the set of all pos-
sible consistent ABoxes w.r.t. T that can be constructed using atomic concept
and atomic role names in T , and individuals in ∆. The adopted semantic is the
standard one based on first-order interpretations and on the notion of model: a
TBox is satisfiable if admits at least one model, an ABox A is consistent w.r.t.
a TBox T if (T, A) is satisfiable, and (T, A) logically implies an ABox assertion
α (denoted (T, A) |= α) if every model of (T, A) is also a model of α.
We define 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 effects.
The guard q is a standard conjunctive query (CQ) of the type q = ∃→ −
y .conj(→
−x,→−
y ),
→
− →
− →
−
where conj( x , y ) is a conjunction of atoms using free variables x and existen-
tially quantified 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)6∃
→
− →
−
(resp., Vars(q)∃ ) 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 effects (i.e., atomic non-grounded ABox assertions)
which is divided in two subsets: the set E − of negative effects, and the set E + of
positive effects. All atoms of E − must use variables that are in Vars(q)6∃ , while
the atoms of E + uses variables from the set Vars(q)6∃ ∪ N . All variables are
defined over a countably infinite (object) universe V of variables.
Definition 2. The transition system ΥD is defined 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)6∃ );
3. choose an assignment for the variables in N and use it to extend ϑa . We
define an assignment function m(N, A) : 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 effects E and calculate Anext by applying the in-
stantiated effects to A.
The sets Σ and ⇒ are thus mutually defined using induction (starting from A0 )
as the smallest sets satisfying the following property: for every A ∈ Σ and action
a ∈ Γ , if exists an action instantiation aϑa s.t.
Anext = A \ sub(ent(E − , T )ϑa , A) ∪ E + ϑa
l
and Anext ∈ AT , then Anext ∈ Σ and A ⇒ Anext , with l = aϑa . aϑa is called an
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 effects e− in E − w.r.t. to
the TBox T . We take each single negative effect 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 e− −
rew 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 non-
shared variable represented by the symbol ‘ ’ (never both variables). We add
each atom e− − −
rew 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 e−
− −
rew 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 e− rew ϑa = α, assuming that the symbol
‘ ’ can be evaluated equal to any individual ( = ind , ∀ind ∈ 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, Anext i 6|= 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 definition of Anext , actions modify only ABox assertions:
it follows that the TBox is fixed, while the ABox changes as the system evolves
(thus an ABox Ai is sufficient to identify the state i of the system). The transition
system ΥD clearly can be infinite, as we have the possibility to introduce new
constants. We call a path π a (possibly infinite) sequence of transitions over ΥD
1 1 a ϑ n na ϑ
that start from A0 (π = A0 ⇒ ... ⇒ An ).
Example 1. Consider the DKB D described by the following elements and which
models a simple business scenario:
– the TBox T = {Employee v ¬Product, Technician v Employee};
– the ABox A0 = {Technician(t1), Product(p1)};
– the action set Γ composed of the following actions:
create: {Employee(x)}, {y} {Product(y)}+
fire: {Employee(x)} {Employee(x)}−
createϑ
If we consider A0 as the initial state in ΥD , then a possible transition is A0 ⇒
A1 where: ϑ = {x 7→ t1, y 7→ p2} (notice that we introduce a new individual p2),
and A1 = {Technician(t1), Product(p1), Product(p2)}.
We could also perform the action fire, as it exists a proper instantiation of it
by using the variable assignment ϑfire = {x 7→ t1}. The set ent(E − , T ) for the
−
action fire corresponds to the set {Employee(x), Technician(x)}, thus Esub(ϑ fire )
would be equal to {Technician(t1)}. Performing the action instantiation would
get us to the state A2 {Product(p1)}, and it’s clear that hT, A2 i 6|= Employee(t1). If
we would simply remove the instantiated negative effects in E − ϑfire ), we wouldn’t
achieve the same result (as the assertion Technician(t1) would still appear in the
final state), as if the action didn’t have any effect at all.
3 Optimizations
3.1 Action Rewriting
The first optimization we bring to the framework regards actions, and, more
specifically, 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 ev-
ery CQ q rew ∈ rewT (q), create an action arew : q rew , N E (with N and E taken
from a without modifications). These new actions slightly modify the transition
function ⇒: the guard is now evaluated without using the TBox, and the vari-
able assignment ϑarew must be taken from the certain answers ans(q rew , ∅, A),
while the rest of the transition function remains the same.
The second optimization regards the ending state of the transition: in the
specification 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 )) defined in [3]. Each positive effect e+ ∈ E + (column 1 in Table 1, we
need to change the variables accordingly to the ones in e+ ) could take part
in a negative inclusion assertion α ∈ cln(T ) (column 2 in Table 1); this mean
that we have to look for a possible assertion β (column 3 in Table 1) which
could break α when e+ is added (z represents a newly introduced variable, thus
z 6∈ Vars(q) ∪ N ∪ Vars(B)). To do so, for each possible β we get from e+ and
α, we perform the following steps (we start from B = ⊥, where ⊥ indicates a
predicate whose evaluation is false in every interpretation):
1. we check if β is present in the positive effects E + by executing ans(β, ∅, E + )
and retrieve all the certain answers φE + . For each φE + , it means it exist an
assertion βφE + which poses a problem. Since we are dealing with variables
(the effects are not instantiated yet), we have to express in B under which
conditions βφE + would make Anext inconsistent; we do this by adding the
corresponding CQ βE + (column 4 in Table 1) to B by or -connecting it to
the rest of the CQs.
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 effects that could block β by re-
moving 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 effects 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.
Definition 3. Given an action a ∈ Γ , its rewritten action arew is defined as:
arew : q rew , N, B E
rew
where q ∈ rewT (q), and B is the blocking query of arew .
The union of all possible rewritten actions defines the set of actions Γ rew .
Example 2. Let’s consider the action create: {Employee(x)}, {y} {Product(y)}+ .
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 effect e+ = Product(y) takes part in the negative-inclusion
assertion Employee v ¬Product, and, by the definition of cln(T ), also in the as-
sertion Technician v ¬Product: we thus have two β assertions, Employee(y), and
Technician(y). By following the procedure for building B, we have no βE + ele-
ments (as ans(β, ∅, E + ) = ∅, and no βE − elements (as ans(β, ∅, ent(E − , T )) =
∅). The final query is thus composed only of βA elements, and is
B = Employee(y) ∨ Technician(y)
e+ α β ϑE + → βE + ϑE − → βE − βA
A v ¬A1
A(x) A1 (x) {x 7→ y} → x = y {x 7→ y} → x 6= y ∧ A1 (x) A1 (x)
A1 v ¬A
A v ¬∃P {x 7→ y1 , z 7→ y2 } →
A(x) P(x, z) {x 7→ y} → x = y ∃z.P(x, z)
∃P v ¬A ∃z.P(x, z) ∧ x 6= y1 ∧ z 6= y2
A v ¬∃P− {x 7→ y1 , z 7→ y2 } →
A(x) P(z, x) {x 7→ y} → x = y ∃z.P(z, x)
∃P− v ¬A ∃z.P(z, x) ∧ x 6= y1 ∧ z 6= y2
∃P v ¬A
P(x1 , x2 ) A(x1 ) {x1 7→ y} → x1 = y {x1 7→ y} → x1 6= y ∧ A(x1 ) A(x1 )
A v ¬∃P
∃P− v ¬A
P(x1 , x2 ) A(x2 ) {x2 7→ y} → x2 = y {x2 7→ y} → x2 6= y ∧ A(x2 ) A(x2 )
A v ¬∃P−
∃P v ¬∃P1 {x1 7→ y1 , z 7→ y2 } →
P(x1 , x2 ) P1 (x1 , z) {x1 7→ y} → x1 = y ∃z.P1 (x1 , z)
∃P1 v ¬∃P ∃z.P(x1 , z) ∧ x1 6= y1 ∧ z 6= y2
∃P− v ¬∃P1 − {x2 7→ y1 , z 7→ y2 } →
P(x1 , x2 ) P1 (z, x2 ) {x2 7→ y} → x2 = y ∃z.P1 (z, x2 )
∃P1 − v ¬∃P− ∃z.P(z, x2 ) ∧ x2 6= y1 ∧ z 6= y2
∃P v ¬∃P1 − {x1 7→ y1 , z 7→ y2 } →
P(x1 , x2 ) P1 (z, x1 ) {x1 7→ y} → x1 = y ∃z.P1 (z, x1 )
∃P1 − v ¬∃P ∃z.P(z, x1 ) ∧ x1 6= y1 ∧ z 6= y2
∃P− v ¬∃P1 {x2 7→ y1 , z 7→ y2 } →
P(x1 , x2 ) P1 (x2 , z) {x2 7→ y} → x2 = y ∃z.P1 (x2 , z)
∃P1 v ¬∃P− ∃z.P(x2 , z) ∧ x2 6= y1 ∧ z 6= y2
P v ¬P1
{x1 7→ y1 , x2 7→ y2 } →
P1 v ¬P {x1 7→ y1 , x2 7→ y2 }
P(x1 , x2 ) P1 (x1 , x2 ) (x1 6= y1 ∧ P(x1 , x2 ))∨ P1 (x1 , x2 )
P− v ¬P1 − → x1 = y1 ∧ x2 = y2
(x2 6= y2 ∧ P(x1 , x2 ))
P1 − v ¬P−
P v ¬P1 −
{x1 7→ y1 , x2 7→ y2 } →
P1 − v ¬P {x1 7→ y1 , x2 7→ y2 }
P(x1 , x2 ) P1 (x2 , x1 ) (x1 6= y1 ∧ P(x2 , x1 ))∨ P1 (x2 , x1 )
P− v ¬P1 → x1 = y1 ∧ x2 = y2
(x2 6= y2 ∧ P(x2 , x1 ))
P1 v ¬P−
{x1 7→ y1 , z 7→ y2 } →
P(x1 , z) {x1 7→ y1 , x2 7→ y2 } ∃z.P(x1 , z)
P(x1 , x2 ) funct P (∃z.P(x1 , z) ∧ x1 6= y1 ∧ z 6= x2 )∨
∧ x2 6= z → x1 = y1 ∧ x2 6= y2 ∧ x2 6= z
(∃z.P(x1 , z) ∧ x1 = y1 ∧ z 6= x2 ∧ z 6= y2 )
{z 7→ y1 , x2 7→ y2 } →
P(z, x2 ) {x1 7→ y1 , x2 7→ y2 } ∃z.P(z, x2 )
P(x1 , x2 ) funct P− (∃z.P(z, x2 ) ∧ x2 6= y2 ∧ z 6= x1 )∨
∧ x1 6= z → x2 = y2 ∧ x1 6= y1 ∧ x1 6= z
(∃z.P(z, x2 ) ∧ x2 = y2 ∧ z 6= x1 ∧ z 6= y1 )
Table 1: Assertions βE + , βE − , and βA for a given positive effect e+ and assertion α
We get the following two rewritten actions:
createrew
1 : {Employee(x)}, {y}, {Employee(y) ∨ Technician(y)} {Product(y)}+
createrew
2 : {Technician(x)}, {y}, {Employee(y) ∨ Technician(y)} {Product(y)}+
Theorem 1. Given a satisfiable KB (T, A), an action arew ∈ Γ rew such that
ϑarew ∈ ans(q rew , ∅, A) and ans(Bϑarew , ∅, A) = ∅, then the ABox Anext = A \
−
Esub(ϑ arew )
∪ E + ϑarew is consistent w.r.t. T .
Proof. For the proof of the theorem we remind the reader to the Appendix of
the extended version of this paper [11].
Lemma 1. Given an action arew ∈ Γ rew , for every ABox A such that ϑarew ∈
ans(q rew , ∅, A) and ans(Bϑarew , ∅, A) = ∅, we can always perform the transition
arew ϑarew
A ⇒ Anext , with Anext ∈ AT .
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.
Definition 4. A partial transition system ΥDp is a tuple (∆, T, Σ p , Ap0 , →), where:
(i) ∆ is the universe of individual constants; (ii) T is a TBox; (iii) Σ p is a set
of states, namely ABoxes from the set AT (Σ p ⊆ AT ); (iv) Ap0 is a subset of
the initial ABox A0 (Ap0 ⊆ 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 Ap0 ⊆ A0 , we have the guarantee that Ap0 ∈ AT . The sets Σ p and →
are mutually defined using induction (starting from Ap0 ) as the smallest sets
satisfying the following property: for every Ap ∈ Σ p and action arew ∈ Γ rew , if
exists an action instantiation arew ϑarew s.t.
Apnext ⊆ Ap \ Esub(ϑ
−
arew )
∪ E + ϑarew
l
and Apnext ∈ AT , then Apnext ∈ Σ p and Ap ⇒ Apnext , with l = arew ϑarew .
Notice that Apnext can be any subset of Ap \Esub(ϑ
−
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 define the existing relation between
the the partial transition system ΥDp and the transition system ΥD . Given a path
π p in ΥDp , we say that π p is a proper partialization of a path π in ΥD (resp., π is
a proper completion of π p ) if:
– each state Api is a subset of the relative state Ai (Api ⊆ Ai );
– each transition is caused by the same action arew i and the related variable
assignments are equal (ϑpi = ϑi ).
Between ΥD and ΥDp there is no relation such as bisimulation or even simula-
tion; this is a clear (and intended) consequence of working with partial knowl-
edge. This also means that we have no immediate way to know if, given a partial
path π p in ΥDp , we can use the same actions instantiations in ΥD , and thus if it
exists a path π that is a proper completion π p . To overcome this problem, we
extend the definition of the blocking query B by creating a global blocking query
Bπp w.r.t to a finite partial path π p . Bπp is a boolean UCQ that can be evalu-
ated 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 ϑpi of the actions that compose π p (Algorithm 1, the symbol > indicates a
predicate whose evaluation is true in every interpretation). At each step, be-
fore adding the i-th instantiated blocking query Bi ϑpi to Bπp , we perform the
following operations:
– check that ans(Bπp , ∅, Ei+ ϑpi ) is False;
– 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 influence 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 first 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 β = ∃z.P(i1 , z) ∧ i2 6= z, then βtemp = P(i1 , z);
−
– perform ans(βtemp , ∅, Esub(ϑ p ):
i)
• if it evaluates to True, then it means that the instantiated negative effects
−
Esub(ϑ p remove the atom βtemp , and in this case we can remove the CQ
i)
β from Bπp ;
• if it returns answers of the type ϑβtemp = {z 7→ ind}, then it means that
−
the instantiated negative effects Esub(ϑ p remove the atom βtemp only if z
i)
is mapped to the individual ind. We thus add to the CQ β the inequality
z 6= ind.
Theorem 2. Given a DKB D, a finite partial path π p , and its global blocking
query Bπp , if ans(Bπp , ∅, A0 ) = ∅, then it exists a concretion π of π p such that
π ∈ ΥD .
Proof. For the proof of the theorem we remind the reader to the Appendix of
the extended version of this paper [11].
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 := {⊥}
i := n. of transitions in π p // counter variable
p
ai ϑ
while i > 0 do // each cycle refers to transition Api−1 →i Api
+ p
if ans(Bπp , ∅, Ei ϑi ) 6= ∅ then
Bπp := > // inconsistency in the i-th transition
break
end
foreach β ∈ Bπp do
if β contains (in)equalities that are always False then
Bπp := Bπp \ β // remove CQs that are always False
end
remove from β (in)equalities that are always True
βtemp := β without (in)equalities and existential operator
−
if ans(βtemp , ∅, Esub(ϑ p ) = T rue then
)
i
−
Bπp := Bπp \ β // Esub(ϑp
)
erases the CQ βtemp
i
−
else if ans(βtemp , ∅, Esub(ϑp ) 6= ∅ then
i)
−
foreach ϑβtemp = {z 7→ ind} ∈ ans(βtemp , ∅, Esub(ϑ p ) do
)
i
β := β ∧ z 6= ind // update the CQ β
end
end
end
Bπp := Bπp ∪ Bi ϑpi // add the blocking query of action ai
i := i − 1
end
– the TBox T = {Stored v ¬Shipped};
– the ABox A0 = {Product(p1), Stored(p1), Product(p2)};
– the action set Γ composed by the following actions:
pack: {Product(x)} {Packed(x)}+ ,
ship: {Packed(x)} {Shipped(x)}+
which becomes the set Γ rew composed of the actions:
packrew : {Product(x)} {Packed(x)}+ ,
rew
ship : {Packed(x)}, {Stored(x)} {Shipped(x)}+
At this point, we develop a partial transition system ΥbD by considering the partial
initial state Ap0 = {Product(p1)}. We can perform the sequence of transitions
packϑ shipϑ
π p = Ap0 → Ap1 → Ap2 , where: ϑ = {x 7→ p1}, Ap1 = {Packed(p1)}, and Ap2 =
{Shipped(p1)}. 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 Ap0 = {Product(p2)},
instead, we woould be able to find a proper completion of π p , as Bπp would be
Stored(p2) and ans(Bπp , ∅, A0 ) = ∅.
Given a finite 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
Ap0 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 Conclusions
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 defined by DL-LiteA knowl-
edge 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 difficult envi-
ronment 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 knowl-
edge 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 infinite 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 di-
rections. 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.
References
1. Baader, F., Zarrieß, B.: Verification of Golog programs over description logic ac-
tions. Lecture Notes in Computer Science (including subseries Lecture Notes in
Artificial Intelligence and Lecture Notes in Bioinformatics) 8152 LNAI, 181–196
(2013)
2. Bhattacharya, K., Gerede, C., Hull, R.: Towards formal analysis of artifact-centric
business process models. Business Process Management pp. 288–304 (2007)
3. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Poggi, A., Rodriguez-
Muro, M., Rosati, R.: Ontologies and Databases: the DL-Lite Approach 5689,
255–356 (2009)
4. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Poggi, A., Rosati, R.:
Linking data to ontologies: The description logic DL-LiteA . CEUR Workshop Pro-
ceedings 216 (2006)
5. Calvanese, D., De Giacomo, G., Montali, M., Patrizi, F.: Verification and Synthesis
in Description Logic Based Dynamic Systems, Lecture Notes in Computer Science,
vol. 7994. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)
6. Cohn, D., Hull, R.: Business artifacts: A data-centric approach to modeling busi-
ness operations and processes. IEEE Data Eng. Bull 32(3), 3–9 (2009)
7. Ghallab, M., Nau, D.S., Traverso, P.: Automated planning - theory and practice.
Elsevier (2004)
8. Gigerenzer, G., Gaissmaier, W.: Heuristic decision making. Annual review of psy-
chology 62, 451–482 (2011)
9. Hariri, B.B., Calvanese, D., Montali, M., De Giacomo, G., Masellis, R.D., Felli, P.:
Description Logic Knowledge and Action Bases. J. Artif. Intell. Res. (JAIR) 46,
651–686 (2013)
10. Levesque, H.J.: Foundations of a Functional Approach to Knowledge Representa-
tion. Artif. Intell. 23(2), 155–212 (1984)
11. Stawowy, M.: Optimizations for decision making and planning in description logic
based dynamic knowledge bases (2015), http://arxiv.org/abs/1502.04665