Contextualized Knowledge Repositories with Justifiable Exceptions

Abstract

Representation of context dependent knowledge in the Semantic Web has been recognized as a relevant issue: as a consequence, a number of logic based formalisms have been proposed in this regard. In response to this need, in previous works, we presented the description logic-based Contextualized Knowledge Repository (CKR) framework. Starting from this point, the first contribution of the paper is an extension of CKR with the possibility to represent defaults in context dependent axioms and a translation of extended CKRs to datalog programs with negation under answer sets semantics. The translation generates datalog programs which are sound and complete w.r.t. instance checking in CKRs. Exploiting this result, we have developed as a second contribution a prototype implementation that compiles a CKR based on OWL2RL to a datalog program. Finally, we compare our approach with major non-monotonic formalisms for description logics and contextual knowledge representation.

1 Introduction

Representation of context dependent knowledge in the Semantic Web has been recently recognized as a relevant issue: this lead to a number of logic based proposals, e.g. [ 13, 14, 17–20 ]. In this line, we have introduced the Contextualized Knowledge Repository (CKR) framework [ 17, 4–6 ], which is a two-layered structure with a lower layer containing a set of contextualized knowledge bases, and an upper layer containing context independent knowledge and knowledge about meta-data of contextual knowledge bases.

On the one hand, such a structure enables us to express at the upper level facts that are true in all the contexts, like “animals don’t have a job” without explicitly stating them in each single context. On the other hand, in many practical cases, there can be contexts that contain exceptional individuals that do not fit these general axioms. For instance, in the contexts of TV shows, or rescue activities, exceptional animals can work as actors, or as search and rescue dogs. Being able to represent axioms which tolerate exceptional instances in context, here called defeasible axioms, would provide more flexibility in the encoding of contextual knowledge in many real world domains.

In this paper we present an extension to the formal CKR semantics for dealing with defeasible axioms (preliminarily introduced in [ 7 ]) which is based on the notion of justification (inspired by the approach of [ 9 ]). The main idea is that, if a global axiom like, e.g. the concept inclusion C v D is declared to be a “defeasible axiom”, then in all the local contexts it allows to infer that an object x is a D by the fact that x is a C, unless there is a “justification” for x not to be a D. Such a justification is a deduction of ¬D(x) from the facts that holds in the context. We remark that existence of such “exceptional” instances do not impose the rejection of the axiom C v D as a whole, which can be applied to all the other “normal” instances in the context.

On the basis of this semantics, we develop a translation of OWL RL based CKRs with default axioms into datalog programs with negation. Specifically, instance checking over a CKR reduces this way to (cautious) inference from such programs under the answer sets semantics [ 10 ], which thus can be used to implement query answering for CKR with defeasibility. We have developed a prototype implementation3 that compiles a CKR to a datalog program, described in Section 5. Furthermore, in Section 4, we compare our approach with some major non-monotonic formalisms for description logics and contextual knowledge representation, highlighting commonalities and differences. 2

CKR with Defeasible Axioms

We summarize the basic definitions of the CKR framework and explain its extension with defeasible axioms: for a detailed description and complete examples, we refer to [ 7, 4 ] where the current formalization for CKR framework has been first introduced.

A Contextualized Knowledge Repository (CKR) is a two layered structure: the upper layer consists of a knowledge base G containing (1) meta-knowledge , i.e. the structure and properties of contexts of the CKR, and (2) global (context-independent) knowledge , i.e., knowledge that applies to every context; the lower layer consists of a set of (local) contexts that contain (locally valid) facts and can refer to what holds in other contexts. Meta-Language. The meta-knowledge of a CKR is expressed in a DL language containing the elements to define the contextual structure. A meta-vocabulary is a DL vocabulary Γ = NCΓ ] NRΓ ] NIΓ containing the following sets of symbols: context names N ⊆ NIΓ ; module names M ⊆ NIΓ ; context classes C ⊆ NCΓ , including the class Ctx; contextual relations R ⊆ NRΓ ; contextual attributes A ⊆ NRΓ ; and for every attribute A ∈ A, a set DA ⊆ NIΓ of attribute values of A. The role mod ∈ NRΓ defined on N × M expresses associations between contexts and modules. Intuitively, modules represent pieces of knowledge specific to a context or context class; attributes describe contextual dimensions (e.g. time, location, topic) identifying a context (class).

The meta-language LΓ of a CKR is a DL language over Γ such that in every concept • A.B and • mod.B where • ∈ {∀ , ∃, 6 n, > n}, concept B has the form B = {a} with a ∈ DA respectively B = {m} with m ∈ M.

Object Language. The knowledge in contexts of a CKR is expressed via a DL language LΣ , called object-language , over an (object-)vocabulary Σ = NCΣ ] NRΣ ] NIΣ . Expressions in LΣ are evaluated locally to contexts, i.e., contexts can interpret symbols independently. To access the interpretation of expressions inside a specific context or context class, we extend LΣ to LΣe with eval expressions of the form eval(X, C), where X is a concept or role expression of LΣ and C is a concept expression of LΓ (with C v Ctx). 3 http://dkm.fbk.eu/resources/ckr/ckr-datalog-rewriter-d-1.1.zip Defeasible Axioms. Compared to [ 7 ], the global object knowledge G may contain statements of the form D(α ) were α ∈ LΣ , which states that α is a defeasible axiom. Intuitively, this means that at the level of instantiations for individuals, α is inherited by local contexts unless it generates a contradiction there. In other words, a local exception to α for some individuals is tolerated. E.g., D(Concert v Expensive) ∈ G might express that in general concerts are expensive and propagate this to local contexts. At such a context, this might be contradicted by assertions Concert (freeconcert2014 ), ¬Expensive(freeconcert2014 ) that “override” the global axiom for freeconcert2014 . The DL language LΣD extends LΣ with the set of defeasible axioms in LΣ . CKR Syntax. We can now provide a formal definition of CKR:

Definition 1 (Contextualized Knowledge Repository, CKR). A Contextualized Knowl

edge Repository (CKR) over a metav-ocabulary Γ and an object vocabulary Σ is a structure K = hG, {Km}m∈Mi where: (i) G is a DL knowledge base over LΓ ∪ LΣD ; (ii) every Km is a DL knowledge base over LΣe , for each module name m ∈ M. In this paper, we consider SROIQ-RL (defined in [ 7 ]) as language of reference: SROIQ-RL is a restriction of SROIQ [ 12 ] syntax corresponding to OWL RL [ 16 ]. K is a SROIQ-RL CKR, if G and all Km are knowledge bases over the extended language of SROIQ-RL where eval-expressions can only occur in left-concepts and contain left-concepts or roles. We tacitly focus on SROIQ-RL CKRs in the following. Example 1. In this example, we want to define an event recommendation system: we represent touristic events and preferences of tourists in order to derive appropriate suggestions. In particular, we want to assert that, in general, all of the Cheap events are Interesting : we can do this using a defeasible axiom in the global context. Furthermore, we propose local markets (market ) and football matches (fbmatch) as examples of cheap events. However, we want to reflect that tourists interested in cultural events are not interested in a sports event like a football match: we express this by negating their interest in f bmatch. Thus, our example CKR Ktour = hG, {Kctourist m}i has:

G : { D(Cheap v Interesting), Cheap(fbmatch), Cheap(market ),

mod(cultural tourist, ctourist m) }

Kctourist m : { ¬Interesting(fbmatch) }

Note that the negative assertion in the local context represents an exception to the defeasible axiom: we want to recognize this “overriding” for the fbmatch instance, but still apply the defeasible inclusion for market . 3 Semantics. We extend the model-based semantics of CKRs in order to reason with exceptions and their justifications. Intuitively, we model local exceptions of axiom instances by pairs hα, ei of an axiom α ∈ LΣ and a tuple e of individuals in NIΣ (called clashing assumptions): in the evaluation of α at a local context, its instantiation with e is not considered. In previous concerts example, e.g., our clashing assumptions on the local context should contain hConcert v Expensive, freeconcert2014 i. However, such assumptions of exceptions must be justified: the instance of α for e must be unsatisfiable at the local context. This is ensured if assertions can be derived which prove this unsatisfiability: we call such assertions clashing sets. In our example, previous clashing assumption is in fact justified by the clashing set {Concert (freeconcert2014 ), ¬Expensive (freeconcert2014 )}. Models of a CKR will be then CKR interpretations in [ 7 ] which can be extended with clashing assumptions that are all justified. Definition 2 (CKR interpretation). A CKR interpretation for hΓ, Σ i is a structure I = hM, Ii s.t.: (i) M is a DL interpretation of Γ ∪ Σ s.t., for every c ∈ N, cM ∈ CtxM and, for every C ∈ C, CM ⊆ CtxM; (ii) for every x ∈ CtxM, I(x) is a DL interpretation over Σ s.t. Δ I(x) = Δ M and, for a ∈ NIΣ , aI(x) = aM. The interpretation of ordinary DL expressions on M and I(x) in I = hM, Ii is as usual; eval expressions are interpreted as follows: for every x ∈ CtxM, eval(X, C)I(x) = Se∈CM XI(e).

An instantiation of an axiom α ∈ LΣ with a tuple e of individuals in NIΣ , written α (e), is the specialization of α , viewed as its first order translation in a universal sentence ∀x.φ α (x), to e (i.e., φ α (e)); accordingly, e.g., e is void for assertions, a single element e for GCIs, and a pair e1, e2 of elements for role axioms.

A clashing set for a clashing assumption hα, ei is a satisfiable set S of ABox assertions such that S ∪ {α (e)} is unsatisfiable. That is, S provides an assertional “justification” for the assumption of local overriding of α on e. We remark that this notion of “assertional justification” is directly connected with the datalog translation (for instance checking reasoning) in Section 3: it corresponds to the provability of an assertional condition stating the inconsistency of the inherited axiom. By the Horn nature of S ROIQ-RL, such a “constructive” justification can always be found.

Given a CKR interpretation I = hM, Ii and a map CAS such that, for every x ∈ Δ M, CAS (x) is a set of clashing assumptions for x, we call the structure ICAS = hM, I, CAS i a CAS -interpretation . Intuitively, a CAS -interpretation pairs a usual CKR interpretation with an exception set for each local context.

Definition 3 (CAS -model). Given a CKR K = hG, {Km}m∈Mi and a CAS -interpretation ICAS = hM, I, CAS i, we say that ICAS is a CAS -model for K (ICAS |= K) if – for every α ∈ LΣ ∪ LΓ in G, M |= α ; – for every D(α ) ∈ G with α ∈ LΣ , M |= α ; – for every hx, yi ∈ modM with y = mM, I(x) |= Km; – for every α ∈ G ∩ LΣ and x ∈ CtxM, I(x) |= α , and – for every D(α ) ∈ G with α ∈ LΣ , x ∈ CtxM, and domain elements d ⊆ Δ I(x), if d 6= eM for every hα, ei ∈ CAS (x), then I(x) |= α (d).

Note that CAS -models basically extend the definition of CKR models from [ 7 ] by introducing the condition to disregard “exceptional elements” asserted by clashing assumptions in CAS (x) in the local interpretation of their defeasible axioms. We can give the following notion of entailment with respect to a given CAS assumption map: for α ∈ LΣe and c ∈ N, we write K |=CAS c : α if for every CAS -model ICAS of K it holds that I(cM) |= α ; for α ∈ LΓ , we write K |=CAS α if for every CAS -model ICAS of K it holds that M |= α .

As we motivated above, we are interested in models in which all clashing assumptions have justifications, that is provable clashing sets. We say that a CAS -model K with Δ M = Δ M0 , it holds I0(x) |= Sx,hα, ei.

ICAS = hM, I, CAS i of K is justified if, for every x ∈ CtxM and hα, ei ∈ CAS (x), some clashing set Sx,hα, ei exists s.t. for every CAS -model I0CAS = hM0, I0, CAS i of Definition 4 (CKR model). A CKR interpretation I = hM, Ii is a CKR model of K (I |= K), if some ICAS = hM, I, CAS i is a justified CAS -model for K. For α ∈ LΣe and c ∈ N, we write K |= c : α if I(cM) |= α for every CKR model I of K; similarly for α ∈ LΓ , we write K |= α if M |= α for every CKR model I of K. Example 2. We can now show an example of CKR model satisfying the CKR Ktour presented in Example 1. We can consider a CAS-model ICAStour = hM, I, CAS tour i such that CAS tour (cultural touristM) = {hCheap v Interesting , {fbmatch}i}. Note that the interpretation is justified as it is easy to check that Ktour |= cultural tourist : {Cheap(fbmatch), ¬Interesting (fbmatch)}, that in fact represents a clashing set for the defeasible axiom. Note that, by the definition of satisfiability under the assumptions in CAS tour , it holds I(cultural touristM) |= Interesting (market ). 3 While the notion of CKR-model is defined for arbitrary domains, it appears that the restriction to the named part of the domain preserves for SROIQ-RL CKRs justified clashing assumptions. This allow us to confine to named CKR-models in the correctness result of the datalog translation presented in the following section.

More formally, given a CAS -interpretation ICAS = hM, I, CAS i, we let INCAS = hM0, I0, CAS 0i be such that (i) Δ M0 = {aM | a ∈ NIΓ ∪ NIΣ }, and (ii) M0, I0 and CAS 0 are the restrictions of M, I and CAS to Δ M0 , respectively. Then we obtain: Proposition 1. Let ICAS be a justified CAS -model of K. Then, also the CAS -interpretation INCAS is a justified CAS -model of K.

As clashing assumptions in CAS maps are ground instances of axioms, they refer merely to named individuals. Using standard names for the domain elements, one could permit clashing assumptions for all elements in the definition of CAS -model. This proviso would not limit the approach nor compromise the datalog translatability, which builds on the possibility to access elements by names. 3

Datalog Translation

We summarize in the following the datalog translation for reasoning on instance checking in SROIQ-RL CKRs: this is an extension of the calculus from [ 7 ] with rules for the detection of axiom overriding and defeasible propagation of global knowledge. Normal form. To simplify the presentation of rules, we introduce a normal form for the considered axioms. We say that a CKR K = hG, {Km}m∈Mi is in normal form if: (i) G contains axioms in LΓ of the form of Table 1 or in the form C v ∃mod.{m}, C v ∃A.{dA} for A, B, C ∈ C, R, S, T ∈ R, a, b ∈ N, m ∈ M, A ∈ A and dA ∈ DA; (ii) G and every Km contain axioms in LΣ of the form of Table 1 and every Km contain axioms in LΣe of the form eval (A, C) v B, eval (R, C) v T for A, B, C ∈ NCΣ , a, b ∈ NIΣ , R, S, T ∈ NRΣ and C ∈ C;

R(a, b)

A v B ∃R.A v B ¬A(b) ¬R(a, b) a = b

A u B v C

A v 61R.B R v T

R ◦ S v T

Dis(R, S)

Inv(R, S)

Irr(R) (iii) G contains defeasible axioms D(α ) ∈ LΣD with α of the form of Table 1.

It can be seen that for named interpretations, i.e., of the form INCAS , every CKR can be rewritten into an equivalent one in normal form (using new symbols). Program syntax and ASP semantics. Following [ 15 ], we will express our rules in the language of datalog. However, while the rules in [ 15, 7 ] are positive, we need datalog with negation to capture defeasibility. In fact, we use two kinds of negation: strict (classical) negation ¬ and weak (default) negation not, as in answer sets semantics [ 10 ].

A description of the syntax of rules and their interpretation is provided in [ 4 ]; briefly, atoms are of the form p(t1, . . . , tn), where p is a predicate and each ti is a term, i.e., either a constant or a variable. A literal l is either a positive literal p or a negative literal ¬p with p an atom. A program is a set of (normal) rules r, which are of the form a ← b1, . . . , bk, not bk+1, . . . , not bm. where a, b1, . . . , bm are literals and not is default negation. We denote with Head(r) the head a of rule r and with Body+(r) and Body− (r) the positive (b1, . . . , bk) and NAF (bk+1, . . . , bm) part of the body. An answer set of a program P is any satisfiable set S of ground (variable-free) literals that is the least set of literals closed under the rules of the reduct P S (which is positive, i.e., no not occurs) [ 10 ]. A ground literal L is a consequence of P , written P |= L, iff L ∈ S for every answer set S of P . Translation. As in [ 7 ], we adopt the materialization calculus approach [ 15 ] but need to extend it to meet the structure of CKRs and the interpretation of defeasible axioms.

The translation has three components: (1) the input translations Iglob, Iloc, ID, Irl, where given an axiom or signature symbol α and c ∈ N, each I(α, c) is a (possibly empty) set of datalog facts or rules: intuitively, they encode as datalog facts and rules the contents of input global and local DL knowledge bases; (2) the deduction rules Ploc, PD, Prl, which are sets of datalog rules: they represent the inference rules for the instance-level reasoning over the translated axioms; and (3) the output translation O, where given an axiom α and c ∈ N, O(α, c) is either undefined (void) or a single datalog fact: O encodes as a datalog fact the ABox assertion α that we want to prove to be entailed by the input CKR (in the context c).

We extend the definition of input translations to knowledge bases (sets of axioms) S with their signature Σ , with I(S, c) = Sα ∈S I(α, c) ∪ Ss∈Σ I(s, c).

We briefly present here the form of the different sets of translation and deduction rules: tables with the complete set of rules can be found in [ 4 ]. (i) SROIQ-RL translation : Rules in Irl(S, c) translate to datalog facts SROIQ-RL axioms and signature (in context c). E.g., we translate atomic concept inclusions with the rule A v B 7→ {subClass(A, B, c)}. The rules in Prl are the deduction rules corresponding to axioms in SROIQ-RL: e.g., for atomic concept inclusions we have instd(x, z, c) ←

subClass(y, z, c), instd(x, y, c). (ii) Global and local translations: Global input rules of Iglob encode the interpretation of Ctx in the global context (i.e. conditions from Definition 2). Similarly, local input rules Iloc and local deduction rules Ploc provide the translation and rules for elements of the local object language. In particular for eval expressions in concept inclusions, we have the input rule eval (A, C) v B 7→ {subEval(A, C, B, c)} and the corresponding deduction rule: instd(x, b, c) ←

subEval(a, c1, b, c), instd(c0, c1, gm), instd(x, a, c0). (iii) Defeasible axioms translation: The inheritance and overriding of defeasible axioms is encoded by input rules ID and deduction rules PD, inspired by [ 9 ]. Input rules in ID provide the translation of defeasible axioms D(α ) in the global context: ID(D(α ), gk) adds to the program (in the module gk for the global object knowledge) a rule defining when the axiom is locally overridden. Intuitively, such rules encode the proof of existence for a clashing set for an instance of α . For example, if D(A v B) ∈ G, the fact subClass(A, B, gk). is added to the global context program together with the following overriding rule: ovr(subClass, x, A, B, c) ← ¬

instd(x, B, c), instd(x, A, c), prec(c, g).

Here prec(c, g) expresses that context c is more specific than context g. (iv) Inheritance rules: PD provides the rules for defeasible inheritance of axioms from the global context to the local contexts. E.g., the following rule propagates an atomic concept inclusion axiom: if the axiom is in the program of the global context and applicable to a local instance, it is applied only if the latter is not recognized as an exception. instd(x, z, c) ← subClass(y, z, g), instd(x, y, c),

prec(c, g), not ovr(subClass, x, y, z, c). (v) Output rules: Finally, the rules in O(α, c) provide the translation of ABox assertions that can be verified to hold in context c by applying the rules of the final program. For example, atomic concept assertions in a given context c are translated by A(a) 7→ {instd(a, A, c)}.

Translation process. Given a CKR K = hG, {Km}m∈Mi, the translation to its datalog program P K(K) proceeds in four steps: 1. the global program for G is translated to (where gm, gk are new context names):

P G(G) = Iglob(GΓ ) ∪ ID(GΣ ) ∪ Irl(GΓ , gm) ∪ Irl(GΣ , gk) ∪ Prl where GΓ = {α ∈ G | α ∈ LΓ } and GΣ = {α ∈ G | α ∈ LΣD }. Intuitively, P G(G) encodes all of the metaknowledge information in facts with context parameter gm and the global knowledge (including defeasible axioms) in facts with parameter gk. 2. Let NG = {c ∈ N | P G(G) |= instd(c, Ctx, gm)}. For every c ∈ NG, we define its associated knowledge base as

Kc = S{Km ∈ K | P G(G) |= tripled(c, mod, m, gm)} 3. We define each local program for c ∈ NG as

P C(c) := Ploc ∪ PD ∪ Prl ∪ Iloc(Kc, c) ∪ Irl(Kc, c) ∪ {prec(c, gk).} That is, local programs encode as datalog facts the object knowledge from all of the modules associated with the context c and include SROIQ-RL deduction rules Prl, local deduction rules Ploc and propagation rules PD for defeasible axioms. 4. The final CKR program is then defined as P K(K) = P G(G) ∪ Sc∈NG P C(c). Intuitively, the knowledge from the global program P G(G), in which not is absent (i.e., P G(G) is positive), is passed on to the local programs P C(c). The contexts in NG are those relevant for CKR-inference, and we can focus on them. At the local contexts, clashing assumptions correspond to ovr-literals that are assumed to be true; the answer sets semantics makes sure that these literals must be derived from rules, whose bodies resemble clashing sets. In turn, the literals in bodies must be derived, using the materialization rules and respecting the ovr-assumptions for defeasible axioms. Correctness. That the translation works for instance checking (for CKRs in normal form) can be shown by establishing a correspondence between relevant CKR-models of K and answer sets of P K(K). To this end, first a correspondence between inference from a CKR-model and from P K(K) with overriding assumptions is established.

Suppose CAS N assigns every c ∈ N a set CAS N(c) of clashing assumptions; then OVR(CAS N) = {ovr(p(e)) | hα, ei ∈ CAS N(c), Irl(α, c) = p} is the corresponding set of overriding assumptions, and we let GOVR(P K(K)) be the reduct P K(K)OVR(CASN) [ 10 ], i.e., the set of rules obtained from all ground instances of rules in P K(K) by removing (i) each rule r such that B− (r) ∩ OVR(CAS N) 6= ∅, and (ii) the not -literals (which involves only ovr) from all remaining rules.

Consider now a CKR interpretation I = hM, Ii and CAS NM such that, for all c ∈ N, CAS NM(cM) = CAS N(c). Then the following property holds: Lemma 1. GOVR(P K(K)) |= O(α, c) iff K |=CASNM c : α (if O(α, c) is defined). That is, inference relative to clashing assumptions is faithfully represented. Next one can establish that justified clashing assumptions correspond to overriding sets in answer sets of P K(K). For any set S of literals, let S|p be its restriction to predicate p. Lemma 2. For every justified CAS -model ICASNM = hM, I, CASNMi of K, some answer set S of P K(K) exists such that S|ovr = OVR(CAS N).

Lemma 3. For every answer set S of P K(K), some justified CAS -model ICASSM = hM, I, CAS SMi of K exists such that CAS S (c) = {hα, ei | Irl(α, c ) = p, ovr(p(e)) ∈ S} for every c ∈ N.

From the results above, the correctness result for instance checking is easily obtained. Theorem 1. For a (normal form) CKR K, K |= c : α iff P K(K) |= O(α, c) (provided O(α, c) is not void). 4

Discussion: Representing Defeasibility in DLs with CKR

In this section we discuss how to compare and relate our proposal with other approaches for including notions of defeasibility in description logics and contextual systems. In particular, we compare it to typicality in DLs [ 11 ], non-monotonic multi-context systems (MCS) [ 8 ] and multi-context systems under argumentation semantics [ 2 ]. Without going into formal details – which is beyond the scope of this paper – we aim to give a superficial intuition about analogies and differences in our representation of defaults. 4.1

Typicality in DL

Default assumptions about properties of the members in a class C and the properties of prototypical elements of C, as defined in [ 11 ], are closely related notions. Giordano et al. [ 11 ] formalize the intuition that a prototypical element of a concept C is a “generic element” of C. This definition stands on the possibility to organize objects in a genericspecific hierarchy, formally a well-founded partial order <, where y < x means that object y is more generic (less specific) than object x. For instance, if x is a red Ferrari car and y is a yellow one, x < y models that the typical Ferrari’s are red and not yellow. The non-monotonic formalization proposed in [ 11 ] represents the set of prototypical elements of a class C using the DL concept expression C u ¬3C. The semantics of the modal operator 3 is the usual Kripke semantics over <. Intuitively, C u ¬3C reads as “the set of C’s for which there is not a more generic (less specific) element of type C”. The approach in [ 11 ] is non-monotonic by restricting the orders < to those minimizing the set of non-specific elements of C, for all C (i.e., the set 3C); intuitively, every element of C is regarded as prototypical unless strictly imposing the contrary.

This is the main analogy with our default axioms, viz. that membership must be blocked. However, while Giordano et al. use semantic model minimization, we use a syntactic and consequence oriented approach, aiming at datalog translatability. Furthermore, we deal with modular structure and cross-references, which they do not consider.

Prototypical concepts may be represented in our formalism by means of an extra concept for each concept C, say CT for the typical elements of C, and by the axioms

CT v C D(C v CT ), which state that every prototypical C is a C and that by default a C is a prototypical C, unless the contrary is entailed; CT is then used for the prototypical concept. Formally casting this correspondence between the two approaches is beyond this paper and will require some adaptation of the approach described in [ 11 ] to the language of OWL2RL. We note that works adapting circumscription to DLs [ 3 ] basically consider a similar notion of “abnormality” under model-based minimization; thus in this respect, similar considerations as for the approach of Giordano et al. apply at a general level. 4.2

Non-monotonic MultiC-ontext Systems

The idea of CKRs with defeasible inheritance based on justifiable assumptions may also be realized within the nonmonotonic MCS framework of [ 8 ], where contexts Ci with local semantics (acceptable belief sets over a local knowledge base kbi) can add via bridge rules formulas to their kbi depending on the local belief sets of the contexts. Adopting open bridge rules (i.e. bridge rules with variables) to be instantiated over a given domain (using standard names in case), we may encode the global context G as an MCS context g and associate each element x of the domain with a context name in the MCS. We then may mimic satisfaction relative to assumptions as in CASinterpretations with bridge rules that access G to determine whether axioms resp. axiom instances must be evaluated at x (if x ∈ CtxM). In particular, defeasible axioms α of the kind D(C v D) can be encoded using auxiliary concept names Aα and bridge rules: x : C u Aα v D ← g : Ctx(x) x : Aα (y) ← g : Ctx(x), not (x : ¬Aα (y)) and for defeasible concept assertions D(A(c)) bridge rules x : A(c) ←

g : Ctx(x), not (x : ¬A(c)).

Intuitively, Aα serves as guard for the inclusion which by default is true for an individual, and thus the inclusion axiom applies to it; likewise, a concept assertion is true by default. The guard is blocked if a violation of the inclusion (an exception) is provable. The equilibria (stable global belief states) of the so constructed MCS are then akin to CKR-models (a formal relationship remains to be established). However, while this or a similar MCS approach is elegant, we need to extend the language and basically encode the problem in an expressive framework, for which currently limited computational support is available. Above we aim at a formalization from first principles (giving a model-based semantics) suitable for realization in a well-supported host formalism. 4.3

MCS Under Argumentation Semantics

Regarding defeasible MCS under argumentation semantics [ 2 ], we first note the different setting w.r.t. CKR: every context is seen as an independent agent having its own knowledge and preferences (ordering) on contexts. A CKR instead has a global structure of contexts and it only represents one level of “preference”, namely the precedence of G w.r.t. local contexts. In encoding a CKR in MCS (with preferences), for every context ci, its preference ordering may thus be defined as Ti = [ci, G].

Local and global axioms of a CKR can be translated to local and mapping rules with open bridge rules as in the case of [ 8 ]. In particular, global default axioms can be here introduced as local defeasible rules: e.g., D(A v B) can be represented (in every context ci) as the defeasible rule Ai(x) ⇒ Bi(x). A global subsumption can be propagated to each context as a strict local rule: e.g. if C v D is in G, then every context ci contains the strict rule Ci(x) → Di(x). Mapping rules can be related to eval expressions: e.g. eval (A, {c1}) v C in context c2 is expressible by the mapping rule A1(x) ⇒ C2(x). Note, however, that eval expressions are strict inclusions and allow to import knowledge from a class of contexts, possibly defined by a complex expression.

Our notion of overriding of a defeasible axiom compares to a “conflict” among two arguments for conflicting literals in [ 2 ]. In a CKR, conflicts occur only among arguments of the global and local contexts. Using the above preference ordering, local arguments are preferred over global arguments and thus relate to clashing sets; as in our semantics, they serve to justify the local conclusions. To this extent, the clashing assumptions CAS (x) for context x compare to the rejected global arguments of x.

In a related work [ 1 ], it is shown that this form of MCS can be translated and interpreted under a single theory of Defeasible Logic: the idea is to include strict and defeasible (mapping) rules in such theory and use the ordering defined over contexts in defining the rule priorities. In this respect, this shows how to reduce a distributed view of reasoning as in MCS to a centralized one: this is basically the vision we also take in the case of our unified translation of a CKR as a single datalog program.

Prototype Implementation

The presented datalog translation has been implemented in a prototype. It accepts as input global and local modules represented as RDF files containing OWL-RL axioms in the normal form above. The newly added contextual primitives have been defined in a RDF vocabulary (imported in the translation): in particular, axiom defeasibility assertions have been encoded as OWL axiom annotations hasAxiomType having the value defeasible. The prototype has been realized as an extension of the DL to datalog rewriter DReW [ 21 ], which is used in the translation of global and local OWL axioms into their datalog counterparts. The structure of contexts is managed by the prototype: external calls to DLV solver4 are used to determine the set of contexts and their module associations, extracted from the computed answer set(s) of the global program P G(G).

The translation process basically follows the strategy in Section 3. After type checking of the input files, the prototype proceeds to produce the rewriting. First the global module is translated, basically using translation rules from Iglob and Irl; if an axiom is recognized as defeasible, the corresponding instantiation of the overriding rule in ID is added. The global program is completed by adding the deduction rules from Prl. The set of contexts and their association to local modules are then computed by submitting the global program to DLV and retrieving the instances of Context concept and hasModule role in the resulting answer sets. Using this information, the prototype computes local knowledge bases for all contexts and applies the rewriting process to each of them (using rules in Iloc and Irl). The resulting program is completed with deduction rules Ploc and PD and saved. The final program P K(K) can then be queried using the DLV solver (which supports also non-ground queries). A demo of the prototype, together with RDF files containing the examples in [ 4, 7 ], is available on the Web.3 6

Conclusion

We have presented an extension to the CKR framework [ 17, 5, 6 ] introducing a notion of defeasible inheritance of global axioms. For that, we have extended the CKR semantics to deal with local exceptions based on justifications, and we have provided a datalog translation that permits instance checking (in a context) under local exceptions. Continuing the work in [ 4 ], we also provide a first prototype implementation and a comparison of CKRs with defeasible axioms to related approaches in DLs and contextual systems.

For future work, we plan an experimental evaluation to assess the translation and the query performance of the prototype over synthetic and real datasets, and to compare to with the current implementation of CKR based on SPARQL forward rules [ 7 ]. As for related approaches, refining the initial comparison and formally establishing relations with our approach is of interest. Finally, a natural extension to CKR semantics are defeasible axioms across local contexts, possibly along an explicit relation between contexts (e.g. coverage relation [ 17 ]), or across knowledge modules.

Acknowledgments. The research leading to these results has received funding from the European Union’s Seventh Framework Programme (FP7/2007-2013) under grant agreement no.257641 (PlanetData NoE). 4 http://www.dlvsystem.com/dlv/

References

1. Bikakis , A. , Antoniou , G.: Local and distributed defeasible reasoning in multi-context systems . In: RuleML'08 . pp. 135 - 149 ( 2008 )

2. Bikakis , A. , Antoniou , G.: Defeasible contextual reasoning with arguments in ambient intelligence . IEEE Trans. Knowl. Data Eng . 22 ( 11 ), 1492 - 1506 ( 2010 )

3. Bonatti , P.A. , Lutz , C. , Wolter , F. : Description logics with circumscription . In: KR . pp. 400 - 410 ( 2006 )

4. Bozzato , L. , Eiter , T. , Serafini , L. : Defeasibility in contextual reasoning with CKR . In: CILC 2014 . CEUR-WP, CEUR-WS.org ( 2014 )

5. Bozzato , L. , Ghidini , C. , Serafini , L. : Comparing contextual and flat representations of knowledge: a concrete case about football data . In: K-CAP 2013 . pp. 9 - 16 . ACM ( 2013 )

6. Bozzato , L. , Homola , M. , Serafini , L. : Towards More Effective Tableaux Reasoning for CKR . In: DL2012. CEUR-WP , vol. 824 , pp. 114 - 124 . CEUR-WS.org ( 2012 )

7. Bozzato , L. , Serafini , L. : Materialization Calculus for Contexts in the Semantic Web . In: DL2013. CEUR-WP , vol. 1014 . CEUR-WS.org ( 2013 )

8. Brewka , G. , Eiter , T. : Equilibria in heterogeneous nonmonotonic multi-context systems . In: Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI-07) . pp. 385 - 390 . Vancouver, Canada ( 2007 )

9. Buccafurri , F. , Faber , W. , Leone , N.: Disjunctive logic programs with inheritance . TPLP 2 ( 3 ), 293 - 321 ( 2002 )

10. Gelfond , M. , Lifschitz , V. : Classical Negation in Logic Programs and Disjunctive Databases . New Generation Computing 9 , 365 - 385 ( 1991 )

11. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L.: A non-monotonic description logic for reasoning about typicality . Artif. Intell . 195 , 165 - 202 ( 2013 )

12. Horrocks , I. , Kutz , O. , Sattler , U. : The even more irresistible SROIQ . In: Procs. of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR 2006 ). pp. 57 - 67 . AAAI Press ( 2006 )

13. Khriyenko , O. , Terziyan , V.: A framework for context sensitive metadata description . IJSMO 1 ( 2 ), 154 - 164 ( 2006 )

14. Klarman , S. : Reasoning with Contexts in Description Logics . Ph.D. thesis , Free University of Amsterdam ( 2013 )

15. Kro¨tzsch, M.: Efficient inferencing for OWL EL . In: JELIA 2010. Lecture Notes in Computer Science , vol. 6341 , pp. 234 - 246 . Springer ( 2010 )

16. Motik , B. , Fokoue , A. , Horrocks , I. , Wu , Z. , Lutz , C. , Grau , B.C. : OWL 2 Web Ontology Language Profiles . W3C recommendation, W3C (Oct 2009 ), http://www.w3.org/TR/2009/RECowl2-profiles-20091027/

17. Serafini , L. , Homola , M. : Contextualized knowledge repositories for the semantic web . J. of Web Semantics 12 ( 2012 )

18. Straccia , U. , Lopes , N. , Luka´csy, G., Polleres , A. : A general framework for representing and reasoning with annotated semantic web data . In: AAAI 2010 . AAAI Press ( 2010 )

19. Tanca , L. : Context-Based Data Tailoring for Mobile Users . In: BTW 2007 Workshops . pp. 282 - 295 ( 2007 )

20. Udrea , O. , Recupero , D. , Subrahmanian , V.S. : Annotated RDF . ACM Trans. Comput. Log . 11 ( 2 ), 1 - 41 ( 2010 )

21. Xiao , G. , Heymans , S. , Eiter , T.: DReW: a reasoner for datalog-rewritable description logics and dl-programs . In: BuRO 2010 ( 2010 ), system available at http://www.kr.tuwien. ac.at/research/systems/drew/