Enhancing Context Knowledge Repositories with Justifiable Exceptions (Extended Abstract)

1 Introduction

In the field of Knowledge Representation and Reasoning, the problem of dealing with context dependent knowledge is a well-known area of study. Initial proposals for a formal definition of contextual knowledge and reasoning date back to the works of McCarthy [1993], Lenat [1998], and Giunchiglia et al. [2001; 1994]. In the era of the Semantic Web (SW), the representation of context dependent knowledge has been recognized as an extremely relevant issue, due to the need for equipping data sets with meta-data in order to enable users and applications to interpret the data contents in the right context. This interest has led to a number of logic based proposals, e.g. [Brewka and Eiter, 2007; Khriyenko and Terziyan, 2006; Klarman, 2013; Serafini and Homola, 2012; Straccia et al., 2010]. In this paper, we extend the Contextualized Knowledge Repository (CKR) framework [Serafini and Homola, 2012; Bozzato et al., 2012; 2013] in its latest formulation in [Bozzato and Serafini, 2013], with a new form of non-monotonic reasoning based on justification.

� This paper is an extended abstract of an article in the Artificial Intelligence Journal [Bozzato et al., 2018].

2 CKRKnowledge Bases

A CKR knowledge base is a two-layer structure: the upper layer consists of a global context, while the lower layer consists of a set of local contexts.

For example, a CKR for a touristic recommendation system in the Trentino region is depicted in Figure 1: it is composed of a global context G that describes all locations, venues and events that are available in the region, and of a set of local contexts each of which describes the details of an event (e.g. a football match fbmatch, a local market market) or the profile, interests and plans of a single user (e.g. a certain tourist tourist01).

The global context of a CKR contains knowledge of two kinds: (i) a context-independent kernel of facts and axioms about the domain of discourse (or global object knowledge), and (ii) meta-knowledge specifying the properties and structural relationships of contexts, which may be arranged in a context hierarchy. As regards (i), the truth of the pieces of knowledge in the kernel is assumed to be indisputable; for instance, the fact isLocatedIn(CastelloDelBuonconsiglio; Trento) or City(Rovereto). This knowledge is accessible by all local contexts. As regards the meta-knowledge in (ii), given that events are viewed as contexts, we may e.g. assert that sports events are events (SportsEvent v Event), that the football match event is a sports event (SportsEvent(fbmatch)) and that the football match and local market events are low-priced events (CheapEvent(fbmatch); CheapEvent(market)). An axiom Event v 9modfm eventg may express that each event is associated with axioms of a knowledge module m event for events. Knowledge modules are pieces of (object level) information that can be associated either to single context or contexts classes.

Local contexts, on the other hand, contain knowledge that holds under specific circumstances or assumptions and thus they represent di�erent partial and views of the domain in perspective. In our example, local axioms may represent knowledge that is valid during a certain event (e.g. HomeTeam(trento) in the event fbmatch) or in the local preferences of a certain user (e.g. CulturalEvent v InterestingEvent in the knowledge of tourist01). Knowledge in di�erent contexts is not completely independent, as the global context independent knowledge is propagated from the global to the local contexts and it is used to constrain local knowledge in di�erent contexts.

3 Motivation and Aim

In many practical cases, however, it is desirable to leave the possibility to "override" the global object knowledge at the local level, by allowing axioms to admit exceptions in their local instantiations. For example, in the above scenario of the event recommendation system, we might want to assert at the global level G that "by default, all cheap events are interesting" (i.e. CheapEvent v InterestingEvent), but then override this implication for particular kind of events in the context of a specific participant: for instance, tourist01 can state to not be interested in the football match, independently of its price by locally asserting :InterestingEvent(fbmatch). We might also want to express defeasibility on the propagation of information: for instance, in a CKR representing an organization, we might want to express that "by default, all the employees of a year will be employees in the next year" and override the axiom in the context of a specific year for employees that finished their working contract.

In other words, we want to allow certain global axioms to be defeasible, so that they admit exceptional instances in local contexts, while holding in the general case: this clearly requires to add a notion of non-monotonicity across the global and the local parts of a CKR.

The aim of this work is thus to extend the CKR framework in order to support the form of defeasibility for global object knowledge as described above, under some desiderata:

1. defeasibility should be used parsimoniously, in the sense that information is inherited as much as possible, such that the information loss in conclusions at the local level is as
2. little as necessary (e.g. since InterestingEvent(market) is not locally contradicted, we want that this conclusion of the global defeasible axiom holds locally);
3. overriding should be supported by clear evidence, in terms of facts that lead to a contradiction (e.g. in our example, the local assertion :InterestingEvent(fbmatch));
4. reasoning with exceptions should be realized using deductive database technology, in particular SQL and datalog, that has been fostered for CKRs [Bozzato and Serafini, 2013] in line with work around Description Logics [Motik et al., 2005; Calvanese et al., 2007; Kr¨otzsch, 2010; Kr¨otzsch et al., 2010; Kontchakov et al., 2010; Eiter et al., 2012; Ahmetaj et al., 2016].

To this end, we introduce defeasible axioms inspired by the approach of inheritance logic programs in [Buccafurri et al., 1999] and extend the datalog representation of CKR semantics in [Bozzato and Serafini, 2013]. In inheritance logic programs the idea is that special rules recognize exceptional facts at the local level and others propagate global facts only if they are not proved to be overridden at the local level, which happens if the opposite is derived; in the same vein, we consider instances of axioms that might be overridden at the local level. On the basis of this semantics, we develop a translation for CKRs formulated in the Description Logics SROIQ-RL, which in essence underlies OWL-RL [Motik et al., 2009], with defeasible axioms into datalog programs under the answer set semantics [Gelfond and Lifschitz, 1991]. Specifically, instance checking over a CKR reduces this way to (cautious) inference from answer set programs which thus can be exploited to implement query answering for CKR with defeasibility.

4 Main Contributions

The main contributions of this paper are briefly summarized as follows:

CKR extension with defeasible global axioms. We present a new syntax and semantics of an extension of CKR for defeasible axioms D(�) in the global context (in our example above, � = CheapEvent v InterestingEvent). Notably, this allow us to introduce for the first time a notion of non-monotonicity across contexts in CKR. Intuitively, a global defeasible axiom D(�) means that, at the level of instantiations for individuals, the axiom � is inherited by local contexts unless it generates a contradiction in the local context knowledge base. The model based semantics of CKR needs thus to be extended in order to reason with exceptions for such axioms. Axiom instances �(e) representing local exceptions are called clashing assumptions: in the evaluation of � at a local context, its instantiation with e is not considered (i.e. � is "overridden" for e). In our example, we could have e = fbmatch for � at the context tourist01. However, such assumptions of exceptions must be justified: the instance of � for e must be provably unsatisfiable at the local context, given the contents of the context local knowledge base. This is ensured if (atomic) assertions can be derived locally which entail this unsatisfiability: we call such assertions clashing sets. In our example, S = fCheapEvent(fbmatch); :InterestingEvent(fbmatch)g would be such a clashing set. As such, CKR interpretations are thus extended with a set of the local clashing assumptions CAS and called CAS-interpretations. Intuitively, CAS-interpretations interpret local axioms by disregarding exceptional instances contained in CAS. Then, CKR models can be defined as those CAS-models that are justified, i.e. provide a reason for the presence of each clashing assumption in CAS by verifying some corresponding local clashing set (in our example, the set S above). As it turns out justified CAS-models involve minimal sets of clashing assumptions; that is, exceptions are used, in the spirit of Occam's razor, as little as necessary.

Reasoning. We characterize reasoning in CKR with defeasible axioms, where we consider entailment of axioms and conjunctive queries (CQs) for a specific context or all contexts of a CKR. More in detail, we derive semantic characterizations of justified clashing assumptions in terms of least models via fixpoint-constructions. Armed with them, we study the computational complexity of major reasoning tasks. In particular, we show that justified CAS- and CKR-model checking are feasible in polynomial time. On the other hand, satisfiabilty is NP-complete in general (and NP-hardness holds even if the contextual structure is fixed). Under data complexity, entailment of axioms is coNP-complete while answering conjunctive queries is � p 2 -complete, with lower complexity for restricted inputs: in particular, CQ answering is tractable in the case of acyclic CQs over CKRs that contain no defeasible axioms.

Datalog translation. We extend the datalog translation for CKRs based on SROIQ-RL from [Bozzato and Serafini, 2013] with rules for the translation of defeasible axioms and for considering local exceptions in the propagation of such knowledge. We express non-monotonicity using answer set semantics, such that instance checking over a CKR with defeasible axioms reduces to cautious inference from all answer set of the translation, and likewise conjunctive query answering. In particular, we note that the proposed translation (based on positive datalog programs) is non-trivial and checking the derivability of negative knowledge in clashing sets (as :InterestingEvent(fbmatch) in our example) needs special attention (in particular, the presence of negative disjunctive information), as a naive extension of a materialization calculus to negative literals fails. To overcome this problem, we develop a translation in which derivation of negative knowledge is accomplished by encoding proofs by contradiction, using a special set of "test" rules in the translation. In our example, to check whether :InterestingEvent(fbmatch) is derivable, we add InterestingEvent(fbmatch) hypothetically to the knowledge base and test whether a contradiction would be derivable. We show that the proposed translation provides a sound and complete materialization calculus for instance checking and conjunctive query answering on CKRs formulated in SROIQ-RL (i.e., in OWL-RL). We briefly discuss the possibility of a more direct encoding where the test mechanism can be omitted by assuming a suitable notion of justification safeness.

Datalog translation prototype CKRew. We have developed a prototype implementation, called CKRew (CKR datalog Rewriter) that compiles a CKR (represented in terms of OWLRL RDF files) to a datalog program following the presented translation. We present the prototype and we study its behavior with respect to di�erent sizes of the input CKR and percentage of defeasible axioms. In particular, the experiments confirm that scalability of the approach is influenced by the percentage of defeasible axioms in the initial CKR and the number of their exceptional instances. The prototype and test sets are freely distributed for use, replication of experiments and possible comparison with other similar implementations: the prototype and test sets used in the experiments are online available at http://ckrew.fbk.eu/.

5 Context and RelatedWork

The contributions of this work are interesting in general for the area of (logic based) Knowledge Representation: our solution proposes an expressive means for combining reasoning with structured Description Logics knowledge bases (viz. contextualized Semantic Web knowledge bases) with a notion of axiom overriding. As such, our work can be compared not only with respect to approaches to incorporate defeasibility in contextualized logics (e.g. [Brewka and Eiter, 2007; Bikakis and Antoniou, 2010]), but also to solutions for introducing non-monotonic reasoning in Description Logics (e.g. [Giordano et al., 2013; Bonatti et al., 2015]). In our work we provide an extended comparison of our approach with some of the major non-monotonic formalisms for description logics and contextual knowledge representation, highlighting commonalities and di�erences. In particular, our work di�ers from these formalisms with respect to some relevant aspects:

• our approach allows to reason with non-monotonic features in modular knowledge bases under an expressive language corresponding to a standard ontology language (cf. [Brewka and Eiter, 2007; Bikakis and Antoniou, 2010]);
• in case of conflicts across possible overridings, it does not request or elicit a preference on possible interpretations, but it presents-in line with the ASP paradigm-alternatives as di�erent models, thus allowing to "reason by cases" on the conflicting solutions: in particular, reasoning by cases in the well-known Nixon Diamond scenario can be properly handled (cf. [Bikakis and Antoniou, 2010; Bonatti et al., 2015]);
• the definition of model is not defined by minimization, but through the idea of justification of exceptions which is based on semantic consequence (cf. for example [Giordano et al., 2013]). In particular, no "normal" members of a concept are defined, but instead single or tuples of individuals are regarded as "exceptional" with respect to defeasible axioms: this allows us to deal with inheritance of properties at the level of instances (cf. [Bonatti et al., 2015]);
• we provide a translation to datalog that is a direct extension of the materialization calculus approach proposed for the monotonic case in [Bozzato and Serafini, 2013] and shows how modular knowledge can be encoded for non-monotonic reasoning using existing tools.

6 Summary and Conclusion

In conclusion, our work contributes to the body of work extending formalisms based on description logics, where the use of database technology such as datalog have an important role in ongoing improvements that can be exploited by the resulting reasoning systems.

As for future work, it is possible to explore new solutions both in the computational and modelling directions.

Regarding computation, in order to increase the practical applicability of the defeasible CKRs to larger sets of data, the current translation and its implementation need optimization: some possibilities are represented by the study of alternative datalog translations limiting the need for materialization or the use of di�erent reasoning approaches. One possible direction is to limit the use proofs by contradiction for negative knowledge in clashing sets to CKRs that are not "safe" with respect to a direct reasoning about negative facts; preliminary results identify some syntactic classes of "justification safe" knowledge bases.

On the modeling side, an interesting direction is to allow defeasible axioms across local contexts, possibly along an explicit hierarchical relation between contexts (as by the coverage relation in [Serafini and Homola, 2012]). Allowing local defeasible axioms also opens the discussion on how defeasible knowledge import across contexts should be defined, thus allowing a notion of "defeasible propagation" of knowledge along local contexts. Another direction would be to allow local inconsistencies in contexts, similarly to defeasible MCS [Bikakis and Antoniou, 2010].

Acknowledgements

This work has been supported in part by the Austrian Science Fund (FWF) via the projects P24090 and P27730 and by the FBK Mobility program.