Optimizing the Computation of Overriding in DLN (Extended Abstract)

Optimizing the Computation of Overriding in DLN (Extended Abstract)∗

Piero A. Bonatti1 , Iliana Petrova2 and Luigi Sauro1

1Universit`a di Napoli Federico II 2 Inria, Sophia Antipolis, France

{pieroandrea.bonatti, luigi.sauro}@unina.it, iliana.petrova@inria.fr

The formulation of knowledge typically involves the use of by-default axioms that can be overridden in order to accommodate specific exceptions. Biologists, in particular, have commonly followed an incremental approach to introduce exceptions to general properties. For instance, in humans, the heart is typically positioned on the left side of the thorax. However, there are individuals born with a condition called situs inversus, where the heart is located on the opposite side of the body. Similarly, eukaryotic cells are generally defined as having a nucleus, but mammalian red blood cells, in their mature stage, do not possess a nucleus.

Similarly, privacy policies generally include default conditions, such as open and closed policies, conflict resolution methods such as denials take precedence, and authorization inheritance with exceptions [Bonatti and Samarati, 2003].

Description logics (DLs), which underlie the Semantic Web standard OWL2, do not allow to express defeasible knowledge and exceptions. Consequently, several authors proposed different nonmonotonic extentions as a useful means to address this limitation [Bonatti et al., 2011a; Bonatti et al., 2010; Bonatti et al., 2011b; Donini et al., 2002; Giordano et al., 2013; Giordano et al., 2009; Giordano et al., 2015; Casini and Straccia, 2010; Bonatti, 2019].

In this context, DLN [Bonatti et al., 2015a; Bonatti and Sauro, 2017; Bonatti et al., 2015b] is a recent family of nonmonotonic DL which derives from a utilitarian approach to nonmonotonic logic. The primary objective of this approach is to meet the practical requirements of ontology designers, which are highlighted by a number of instances in the literature on biomedical ontologies and semantic web policies. N features normality concepts NC to denote the standard/prototypical instances of a concept C, and prioritized defeasible inclusions (DIs) C ⊑n D that mean (roughly speaking): "by default, all prototypical instances that satisfy C satisfy also D, unless stated otherwise", that is, unless some higher priority axioms contradict this implication; in this case, C ⊑n D is overridden. The standard/prototypical instances of C are required to satisfy all the DIs that are not overridden in C.

DLN adopts the simplest possible criterion for overriding, that is, inconsistency with higher priority axioms. Conflicts between DIs that cannot be resolved with priorities are regarded as knowledge representation errors and are to be fixed by the knowledge engineer (typically, by adding specific DIs). As a consequence, all the normal instances of a concept C conform to the same set of default properties, sometimes called prototype. Here is a summary of the main strenghts of DLN .

* This is an extended abstract of [Bonatti et al., 2022].

No inheritance blocking. Most of the logics grounded on preferential semantics and rational closure block the inheritance of all default properties towards exceptional subclasses (as opposed to overriding only the properties that are modified in those subclasses). DLN 's overriding mechanism does not suffer from this drawback.

No undesired CWA effects. Many nonmonotonic DLs extend default properties to as many individuals as possible, thereby introducing CWA (i.e. closed-world assumption) effects that clash with the intended behavior of ontologies. DLN does not introduce any CWA effect because it does not force individuals to be normal, unless explicitly stated otherwise.

Control on priorities. Since priorities are not fixed a priori in DLN , knowledge engineers can adapt them to their needs. In principle, it is possible to override DIs based on temporal criteria (which may be useful in legal ontologies and ontology versioning), define default conflict resolution criteria, and even use rational closure's specificity-based axiom ranking. The logics derived from inheritance networks, preferential semantics, and rational closure can only support their fixed, specificity-based overriding criterion.

Default role fillers. DLN axioms can specify whether a role should range only over normal individuals or not. Some logics are completely unable to apply default properties to role values. 1 Some others cannot switch this inference off when it is not desired. Only DLN and ALC +Tmin make it possible to control this kind of inference.

Inconsistent prototype detection. DLN facilitates the identification of all conflicts that cannot be resolved with priorities (via consistency checks over normality concepts), because their correct resolution is application dependent and should require human intervention.

1 This is the case for rational closure. Recently, in [Pensel, 2019], a solution has been proposed for EL with ⊥. It is unclear how to extend it to more expressive DLs, and it is not possible to "turn off" the application of default rules to role fillers.

Unique deductive closure. As a result of automated conflict resolution, several nonmonotonic logics yield multiple deductive closures, corresponding to all the alternative ways of solving each conflict. DLN is one of the logics that has a unique closure.

Generality. DLN can be uniformly applied to all description logics up to the standard OWL2-DL (i.e. the logic SROIQ(D)). Typicality logics and rational closure, instead, are limited to logics that satisfy the disjoint union model property. Recently, it has been shown that for expressive DLs that do not enjoy this property, syntactic inference does not match semantics [Bonatti, 2019]. The same paper introduces stable rational closure that solves the generality problem for rational closure, but re-introduces the issue of multiple (or non existent) deductive closures. It is currently not clear how to design a logic that satisfies the KLM postulates, is fully general, and yields a unique closure for all knowledge bases.

Low complexity. DLN preserves the tractability of subsumption and instance checking for all low-complexity DLs, including the rich tractable logics EL++ and DL-lite(HN) Horn . Currently, no other nonmonotonic DL enjoys this property to the same extent. Rational closure has been proved to be tractable for EL extended with ⊥ [Casini et al., 2019; Pensel, 2019]. Some logics, such as [Casini and Straccia, 2010; Casini et al., 2013; Casini and Straccia, 2013; Giordano et al., 2009; Giordano et al., 2013], preserve the asymptotic complexity of ExpTime-complete DLs like ALC. More generally, DLN preserves the asymptotic complexity of all the DLs that belong to a deterministic complexity class that contains P. For nondeterministic complexity classes C, an upper bound is P C .

In [Bonatti et al., 2015a; Bonatti and Sauro, 2017] the semantic properties of DLN and the computational complexity of the related reasoning tasks have been thoroughly studied. As mentioned above DLN preserves the tractability of lowcomplexity DLs, this opens the way to processing very large nonmonotonic KBs within these fragments. For practical purposes, however, asymptotic tractability alone is insufficient. DLN reasoning is based on an iterative procedure that, given the signature of the queries of interest, discards overridden inclusions and transforms the other defeasible inclusions into classical axioms. In the worst case the number of concept consistency checks carried out by this reduction is quadratic in both the knowledge base and of input signature size. These consistency checks are conducted on different subsets of the knowledge base, which are generally uncomparable. This is why they cannot be computed by a single classification of the knowledge base.

In [Bonatti et al., 2015a], a preliminary implementation of a DLN reasoner has clearly demonstrated that such a quadratic dependence can significantly slow down the execution of the computation, even when the engine takes advantage of the incremental reasoning facilities native to state-ofthe-art reasoners like ELK. Consequently, practical reasoning on large knowledge bases - such as biomedical ontologies - requires ad hoc optimizations to detect and prune unnecessary computations during the reduction to classical DL. For this purpose, we propose two optimization techniques that effectively speed up reasoning.

The first optimization focuses on discarding irrelevant axioms for a given query by adapting a classical module extraction algorithm to DLN. This technique also reduces the number of iterations required for the reduction to classical DL. However, adapting classical module extractors to DLN is a challenging task due to the nonmonotonic nature of its inferences.

As mentioned earlier, the initial DLN reasoner utilized the incremental reasoning mechanisms of the underlying classical reasoner. The second optimization, known as the optimistic method, aims to minimize the number of retractions, which are typically the most computationally expensive operations in incremental reasoning.

The efficiency of each optimization and their combined effect is evaluated through experimental analysis. To ensure realistic test cases, we conducted experiments on nonmonotonic versions of prominent biomedical ontologies, including Gene Ontology, Fly Anatomy, and SNOMED. These ontologies not only find applications in specific scenarios but are also widely adopted as benchmarks for assessing performance. To the best of our knowledge, this study represents the first exploration in the field of Description Logics to apply nonmonotonic reasoning techniques to knowledge bases containing a significant number of axioms, ranging between approximately ∼ 20, 000 and ∼ 30, 000.

First, we considered the nonmonotonic versions of Fly Anatomy (>19K axioms) and Gene Ontology (>28K axioms) obtained by transforming classical inclusions into defeasible inclusions. In all of these experiments the average query response time is below one second, and mostly below 0.5 seconds. Similar experiments based on SNOMED (>290K axioms) yield response times between 1.5 and 4.6 seconds, that are compatible with a wide range of use cases. In another set of experiments, we have injected random DIs in Fly Anatomy, Gene Ontology, and SNOMED, thereby increasing their size up to 25%, and introducing random dependencies between different parts of the knowledge base. For the smaller ontologies Fly Anatomy and Gene Ontology, response times are always below 1.5 minutes, and less than 4 seconds in most test cases. For SNOMED, the hardest test cases (∼ 72K additional axioms, 250 normality concepts in the knowledge base) took approximately 1 hour and 45 minutes, while the simplest test cases (N-free) are completed within approximately 1 minute.

In summary, the results obtained from DLN ontologies containing up to 35K axioms demonstrate that the combination of both optimizations significantly reduces computation time by up to four orders of magnitude. This improvement allows for the processing of subsumption queries within response times suitable for various practical applications, including interactive query answering. For knowledge bases derived from SNOMED, which are approximately ten times larger, response times may vary depending on several crucial performance factors. These factors include the number of normality concepts present in the knowledge bases and the extent of logical dependencies between different concepts. In test cases where the size and structure of SNOMED are preserved, the response times remain compatible with interactive query answering. However, in fully random test cases, the response times range from 11 seconds to nearly two hours.

The challenge of developing accurate module extraction techniques for nonmonotonic logics remains an open problem in general. Even within the realm of DLN , our proofs do not encompass module extraction methods based on principles other than locality. Additionally, the potential applications of module extraction extend beyond optimization. Conducting a comprehensive investigation into module extraction for nonmonotonic reasoning represents an interesting subject for future research.