Projection is the problem of checking whether the execution of a given sequence of actions will achieve its goal starting from some initial state. In this paper, we study a setting where we combine a twodimensional Description Logic of context (ConDL) with an action formalism. We choose a well-studied ConDL where both: the possible states of a dynamical system itself (object level) and also different contextdependent views on this system state (context level) are organised in relational structures and can be described using usual DL constructs. To represent how such a system and its views evolve we introduce a suitable action formalism. It allows one to describe change on both levels. Furthermore, the observable changes on the object level due to an action execution can also be context-dependent. We show that the formalism is well-behaved in the sense that projection has the same complexity as standard reasoning tasks in case ALCO is the underlying DL.
Introduction
The role-based paradigm of modelling languages has been introduced for the
design of adaptive and context-sensitive software systems. The concept of roles
has been used at different levels of abstraction, for example in data models [
How to deal with explicit context extensions of modelling languages efficiently
is a well-studied research topic in different areas (e.g. [
However, ConDLs are only suitable for expressing static context-dependent
knowledge. In this paper, we focus on an extension with dynamic aspects and
introduce a ConDL-based action formalism for reasoning about change in context
models. To talk about particular states we consider the ConDL ALCOJALCOK
from [
The remainder of this paper is structured as follows. In the next section we recall the definitions of ALCOJALCOK. Section 3 introduces our action formalism and defines the projection problem. In Section 4, we present our reduction method for deciding projection. We finish with a conclusion in Section 5. 2
The Description Logic of Context ALCOJALCOK
For representing context-dependent knowledge we choose ALCOJALCOK, a
simple member of the family of ConDLs studied in [
The logic is two-sorted with a meta level signature M = (MC; MR; MI) and an object level signature O = (OC; OR; OI). We call MC, MR and MI the set of meta concept names, role names, and individual names respectively. Analogously, OC, OR, OI is called the set of object concept names, role names, and individual names respectively. All these sets are assumed to be pairwise disjoint.
We assume the standard definition of the syntax of ALCO-concepts, general
concept inclusions (GCIs) and KBs (see [
Definition 1 (Syntax). Let ' be an ALCO-KB over the object level signature O and A 2 MC, r 2 MR and a 2 MI meta level names. An ALCOJALCOKmeta level concept description C over M and O ( m-concept for short) is built according to the following syntax rule
C ::= A j fag j J'K j C u C j :C j 9r:C: Further constructors are defined as abbreviations: > := :(A u :A) and ? := (A u :A) (for some A 2 MC), C t D := :(C u :D) and 8r:C := :9r::C.
Let C and D be m-concepts. An ALCOJALCOK-Boolean meta level knowledge base over M and O (m-KB for short) is built according to the following syntax rule ::= C v D j ^ j : : Notation for concept assertions and role assertions is used as abbreviations: (a : C) := fag v C and ((a; b) : r) := fag v 9r:fbg. Further Boolean connectives like _ and ! are defined as usual.
The only non-standard expression is the meta concept constructor J'K that refers to a standard ALCO-KB '. It gives access to the object level from the meta level and describes the set of meta level domain elements (contexts) in which ' is true.
The semantics of ALCOJALCOK is defined in terms of nested interpretations. The structure consists of a single meta level interpretation over M where each domain element is associated with an object level interpretation over O. Definition 2 (Nested Interpretation). A nested interpretation I (over M and O) is a tuple of the form I := (C; I; ; fIcgc2C); where – (C; I) is an M-interpretation, and – Ic := ( ; Ic ) is an O-interpretation for each c 2 C.
Definition 3 (Semantics). Let I = (C; I; ; fIcgc2C) be a nested interpretation. The extension of the mapping I to complex m-concepts is defined by induction on the structure of m-concepts C and D as follows: (:C)I (9r:C)I (fag)I := faIg; ( ' )I J K (C u D)I := CI \ DI; := fc 2 C j Ic j= 'g; := C n CI; := fc 2 C j there exists c0 2 C such that (c; c0) 2 rI and c0 2 CIg; where a 2 MI, r 2 MR and ' is an ALCO-KB over O.
Let be an m-KB. Satisfaction of in I, written as I j= ), is defined by induction on the structure of as follows: ( I is a model of I j= C v D iff CI I j=
1 ^ 2 iff I j= I j= : 1 iff I 6j= 1: DI; 1 and I j= 2; Example 1. We describe some aspects of a conference management domain. On the meta level we talk about accounts that can be PC members of the DL workshop (meta level concept name DL-PC) with possibly conflict of interest (meta level role has-con ict) to authors (concept name DL-Author). Each account has a particular view on the object level where we have a domain of submissions and reviews. The object level concept names Subs-To-Review and Own-Subs describe the assigned submissions for reviewing and their own written submissions, respectively. The object level role has-review relates submissions to their reviews. We describe an initial situation using the meta level individual names bob’s-account and alice’-account and the object level name s denoting a concrete submission. Intuitively, in this model the meta level concept
Js : Own-SubsK describes the set of accounts (meta level domain elements) in which s is an instance of Own-Subs. Therefore, it represents the set of author accounts of s. The following meta level axioms represent some initial knowledge: :JOwn-Subs v ?K :JSubs-To-Review v ?K v DL-PC
> v Js : 8has-review :?K
DL-Author bob’s-account : Js : Own-SubsK alice’-account : (8has-con ict::Js : Own-SubsK) (1) (2) (3) (4) (5) Alice has no conflict of interest with an author of the submission s (1). Bob is an author of s (2), which has not received any reviews yet (3). DL author accounts are defined as those accounts with own submissions (4). Only PC members are allowed to review (5).
Representing Context-dependent Change We define separate action descriptions for the object level and the meta level. Syntactically, action descriptions are complex expressions with constructors for describing conditional and simultaneous execution. Semantically, actions update interpretations by changing the membership of named individuals in concept names or of pairs of named individuals in role names.
Definition 4. Let be an m-KB and A 2 MC, r 2 MR and a; b 2 MI be meta level names. An M-action description ( M-action for short) is built according to the following syntax rule: := hA ai j hA ai j hr (a; b)i j hr (a; b)i j ( . ) j ( k ):
Let C be an m-concept and B 2 OC, s 2 OR and o; o0 2 OI object level names. An O-action description ( O-action for short) is built according to the following syntax rule: := hB oi j hB oi j hs (o; o0)i j hs (o; o0)i j (C . ) j ( k ): We write just action if we do not distinguish between M-actions and O-actions. Actions of the form hA ai, hr (a; b)i, hB oi or hs (o; o0)i are called atomic actions.
An atomic action like hA ai over some signature N changes an N-interpretation I by adding aI to AI and hr (a; b)i deletes (aI ; bI ) from rI . M-actions have m-KBs as conditions and O-actions have m-concepts as conditions. A conditional M-action ( . 1) takes effect in the meta-level interpretation only if is satisfied and a conditional O-action of the form C . 1 means that an O-interpretation Ic in a nested interpretation I is only updated with 1 if c belongs to C in I. The construct ( 1 2) means that 1 and 2 are executed simultaneously.
For the first step of the definition of the execution semantics we define how a set of atomic M-actions (or atomic O-actions) updates a non-nested Minterpretation (or O-interpretation).
Definition 5 (Update). Let N 2 fM; Og denote either the meta-level or objectlevel signature, and let I := ( I ; I ) be an N-interpretation and E a set of atomic N-actions. The update of I with E is an interpretation denoted by IE and is defined for all A 2 NC, all r 2 NR and all a 2 NI as follows
I ;
IE := AIE := rIE aIE := aI :
AI n faI j hA ai 2 Eg [ fbI j hA bi 2 Eg := rI n f(aI ; bI ) j hr (a; b)i 2 Eg [ f(aI ; bI ) j hr (a; b)i 2 Eg
Next, we define the effects of the execution of a complex action in a nested interpretation as a set of atomic actions. The definition tells us how the conditions attached by the “ .” operator are evaluated for M-actions and O-actions. Definition 6 (Effects). Let I = (C; I; ; fIcgc2C) be a nested interpretation and an M-action. The set of atomic M-actions for I and , denoted by E ( ; I), is defined by induction on the structure of as follows and
E (hr (a; b)i; I) := fhr (a; b)ig Let be an O-action and c 2 C. The set of sets of atomic O-actions for I, c and , denoted by E ( ; c; I), is defined by induction on the structure of as follows and
E (hs (o; o0)i; c; I) := fhs (o; o0)ig E (hA E ( . 1; I) := ai; I) := fhA aig
(E ( 1; I) E ( 1 k 2; I) := E ( 1; I) [ E ( 2; I): if I j= ; otherwise; E (hB E (C . 1; c; I) := oi; c; I) := fhB oig (E ( 1; c; I) if c 2 CI; otherwise; ; ; E ( 1 k 2; c; I) := E ( 1; c; I) [ E ( 2; c; I):
An M-action only updates the outer meta level interpretation of a nested interpretation. An O-action leaves the meta level interpretation unchanged and updates all object level interpretation simultaneously. How a particular object level interpretation Ic in a nested interpretation I is updated as the result of executing an O-action depends only on the membership of c in the meta level concepts used as conditions in . The corresponding set E ( ; c; I) can also be empty.
Definition 7 (Nested Update). Let I := (C; I; ; fIcgc2C) be some nested interpretation, an M-action and an O-action. The update of I with is the nested interpretation
I := (C; I ; ; fIcgc2C); where (C; I ) is the update of (C; I) with E ( ; I) and all other components are unchanged. The update of I with is the nested interpretation
I := (C; I; ; fJcgc2C); where for each c 2 C the O-interpretation Jc := ( ; Jc ) is the update of Ic with E ( ; c; I).
Let be a sequence of M-actions and O-actions the update I is defined in the obvious way by induction on .
As in [
Note that it is possible to write an action that adds and deletes an object (or a pair of objects) to and from a name simultaneously. The semantics of updates gives precedence to add effects but we want to exclude those descriptions. In the following we assume that for any M-action , any O-action and any nested interpretation I and meta level domain element c the sets E ( ; I) and E ( ; c; I) are non-contradictory.
We are interested in checking whether a certain consequence formulated as an m-KB holds after executing a sequence of actions given an incomplete representation of the initial state in terms of an m-KB.
Definition 8 (Projection Problem). Let ; 0 be m-KBs and a sequence of actions. We say that 0 is a consequence of executing in iff for all models I of , we have that I j= 0. The projection problem is then to decide whether 0 is a consequence of executing in .
We continue our example about the conference management system. Example 2 (Example 1 continued). An M-action for adding Alice as a PC Member of DL is given by add-pc := hDL-PC alice’-accounti: It updates a nested interpretation by adding alice’-account to DL-PC on the meta level and changing nothing else. Next, we want to define an action which assigns Alice as a reviewer for the submission s under the condition that she has no conflict of interest with an author of this submission. It is specified as an O-action: add-sub := (falice’-accountg u :9has-con ict:Js : Own-SubsK) .
hSubs-To-Review si Note that only the account of Alice is affected. The action only updates the object level interpretation associated with alice’-account by adding s to the review set (Subs-To-Review ).
Let r be the name for the review Alice has written for s. We define an Oaction that enters this review to the system and removes s from the review list of Alice simultaneously.
finish := enter k remove; remove := falice’-accountg . hSubs-To-Review enter := (DL-PC u :9has-con ict:Js : Own-SubsK) . hhas-review si: (s; r)i; The review r is only visible for PC members with no conflict of interest with someone that is an author of s.
Assume initially we have axioms (1)-(5) from Example 1. After performing the sequence add-pc; add-sub it holds that is true and the constraint alice’-account : Js : Subs-To-Review K :JSubs-To-Review v ?K v DL-PC is preserved. Furthermore, after add-pc; add-sub; finish we have that alice’-account : J(s; r) : has-review K is true. 4
Deciding the Projection Problem in ALCOJALCOK
The approach of solving the projection problem in a DL-based action formalism
by reducing it to a standard consistency problem in the underlying DL has been
applied already in several settings (e.g. [
As a first step we introduce a normal form of action descriptions by conjoining conditions and pushing them inside. We say that an N-action with N 2 fM; Og is in normal form if it is of the form
( 1 . e1) k ::: k ( n . en); where each ei, for any i, 1 i n is an atomic N-action and i is either an m-KB (in case of an M-action) or an m-concept (in case of an O-action). We normalize an arbitrary N-action by applying exhaustively the following rules: where ? 2 f^; ug stands for ^ in case of an M-action and for u in case of an O-action. W.l.o.g., we assume from now on that any action is in normal form. For convenience, we denote a normal form of an N-action as a set of atomic N-actions with a single condition attached: = f( 1 . e1); :::; ( n . en)g.
Let an m-KB (initial state), 0 (goal state) and a sequence of actions = 1; :::; n in normal form be the input of the projection problem. Our goal is to construct a reduction m-KB that is consistent iff 0 is a consequence of executing in .
We say that concepts, roles, and individuals are relevant if they occur in the input of the projection problem. For the reduction we use fresh concept names and role names of the corresponding sort. For each execution step 0 i n, we introduce fresh time-stamped copies A(i) of all relevant concept names, r(i) of all relevant role names, and fresh time-stamped concept names T (i) for every C relevant complex subconcept C. A(0) refers to the initial content of A and the further copies A(j), 1 j n refer only to the set of named individual names of the corresponding sort that are instance of A after the jth execution step. This holds for both concept and role names. The copies of the form T (i) represent C the content (both named and unnamed) of the complex concept C after the ith execution step. The distinction between named and unnamed is made because actions only affect named individuals.
Furthermore, for the set of all named individuals of sort object in the input (denoted by ObjO) and for the set of all named meta level individuals in the input (ObjM) two fresh concept names NO and NM, respectively, are introduced.
The meaning of the new names is now axiomatized using meta level axioms as follows. For NO and NM we have obj = (NM
G c2ObjM fcg) ^ (> v JNO a2ObjO
G fagK):
We use (C; i) to denote the concept definition we introduce to define the names of the form TC(i). It is defined by induction on the structure of C as follows: Tf(ai)g
T (i)
A fag (NO u A(i)) t (:NO u A(0)) T:(iC) :TC(i)
TC(i1)uC2
TC(i1) u TC(i2) T9(ir):C
(NO u ((9r(0):(:NO u TC(i))) t (9r(i):(NO u TC(i))))) t (:NO u 9r(0):TC(i)) For referring meta concepts we haveT ('i) J'(i)K. For the object level, we ensure that the concept definitions hold in aJnyK context:
C2RO d(ie)fO := ^ > v J (C; i)K d(ie)fM :=
^ G2RM (G; i); where RO is the set of relevant object level subconcepts and RM the analogous set on the meta level. Given an O-GCI = C v D and a timestamp 0 i n, we define the timestamped copy (i) := TC(i) v T D(i), and '(i) is the timestamped O-KB obtained from ' as the result of replacing every O-GCI in ' with (i). Timestamped copies for M-GCI (i) and m-KB (i) are defined analogously.
We simply put timestamp zero for the initial knowledge base , i.e., we include (0) as a conjunct of the reduction m-KB.
Next, we encode the effects of each action i using the m-KB acti . Intuitively, we make sure that if the condition is satisfied, then corresponding atomic actions are applied to the next step. We define corresponding assertions for each atomic action e and a timestamp i with (e; i).
(hA
ai; i) := (a : A(i)) (hr (a; b)i; i) := ((a; b) : r(i)) (hA (hr ai; i) := (a : :A(i)) (a; b)i; i) := ((a; b) : :r(i)) We distinguish two cases, whether the action is an M-action or an O-action. First, we consider the case of i is an M-action i. We define: a(ic)tM := ^ ( (i 1) We encode the atomic O-actions similarly for i = i, with taking the context into account. Instead of having an m-KB, we have a timestamped m-concept as the condition. The atomic O-actions are propagated using referring meta concept for those contexts.
G.e2 i a(ic)tO :=
^ (T G(i 1) v J (e; i)K) In case of the other type of action happens at timestamp i, the corresponding a(ic)t is simply >. For example, a(ic)tM = > if i is an O-action.
Then, we make sure a change only happens if there is an effect that enforces it. For every i, 1 i n, we define an m-KB m(i)inM that encodes all the noneffects, that is, for each named individual a, each relevant concept name A from the meta level it contains a conjunct of the form
(a : A(i 1) ^ (a : :A(i 1) ^
^ .hA ai2 i
^ .hA ai2 i : (i 1)) ! a : A(i) ^ : (i 1)) ! a : :A(i); and analogous conjuncts for all relevant role names and pairs of named individuals. Likewise, we ensure a minimization of changes on the object level with an m-KB m(i)inO for every i, 1 i n consisting of conjuncts of the form (Jo : B(i 1)K ^
^ G.hB oi2 i :T G(i 1)) ! Jo : B(i)K; and analogously for the negative case and role names. Finally, we define the complete reduction m-KB: red :=
^ 1 i n init (i) actO ^ ^
^ 1 i n obj (i) actM ^ ^
^ 0 i n
^ 1 i n (i) defO (i) minO ^ ^
^ 0 i n
^ 1 i n (i) defM (i) minM ^ Lemma 1. Let be an m-KB, = 1; :::; n be a sequence of actions, and red be defined as above. The following properties hold: 1. For every sequence of nested-interpretations I0; :::; In such that I0 j= and Ii = Ii i 1 for each i, 1 i n there exists an interpretation L j= red such that for every i, 0 i n, and every relevant m-KB , we have Ii j= iff L j= (i). 2. For every nested-interpretation L j= red, there exists a sequence of nestedinterpretations I0; :::; In such that I0 j= and Ii = Ii i 1 for every i, 1 i n such that for every i, 0 i n, and every relevant m-KB , we have Ii j= iff L j= (i).
Lemma 1 shows the correspondence between the models of the reduction mKB red and the sequence of nested interpretations we obtain by executing in a model of the initial m-KB. This allows one to use the following reduction of the projection problem to a (in)consistency problem in ALCOJALCOK. Lemma 2. Let ; 0 be m-KBs, and is a consequence of executing in
be a sequence of actions. It holds that 0 iff red ^ :( 0(n)) is inconsistent.
This gives us a complexity result for the projection problem.
Theorem 1. The projection problem in ALCOJALCOK is ExpTime-complete.
Proof. red is polynomial in the size of the input, and obviously :( 0(n)) as well.
Since the consistency problem in ALCOJALCOK is ExpTime-complete [
For hardness, we can reduce the consistency problem in ALCOJALCOK to the projection problem. It is easy to see that an m-KB is consistent iff fag v > is a consequence of executing hi in . 5
Conclusion We have introduced an action formalism for reasoning about context and object level change in the ConDL ALCOJALCOK. The formalism is well-behaved in the sense that the projection problem has the same complexity as standard reasoning in ALCO.
From a practical point of view, choosing ALCOJALCOK has the advantage
that an efficient reasoning tool for checking consistency already exists [
For future work, we plan to investigate whether our action formalism offers
sufficient expressiveness for capturing also the dynamic features of the role-based
modelling language in [
Furthermore, we would like to study the complexity of reasoning in several extensions of the action formalism. This for example includes operators for nondeterminism in the action dimension and temporal specifications for possibly infinite action sequences.