The Prote´ge´ plug-in NoHR allows the user to combine an OWL 2 EL ontology with a set of nonmonotonic (logic programming) rules - suitable, e.g., to express defaults and exceptions - and query the combined knowledge base (KB). The formal approach realized in NoHR is polynomial (w.r.t. data complexity) and it has been shown that even very large health care ontologies, such as SNOMED CT, can be handled. As each of the tractable OWL profiles is motivated by different application cases, extending the tool to the other profiles is of particular interest, also because these preserve the polynomial data complexity of the combined formalism. Yet, a straightforward adaptation of the existing approach to OWL 2 QL turns out to not be viable. In this paper, we provide the nontrivial solution for the extension of NoHR to OWL 2 QL by directly translating the ontology into rules without any prior pre-processing or classification. We have implemented our approach and our evaluation shows encouraging results. Partially supported by Fundac¸ a˜o para a Cieˆncia e a Tecnologia under project PTDC/EIA-CCO/121823/2010 and strategic project PEst/UID/CEC/04516/2013. M. Knorr was also supported by grant SFRH/BPD/86970/2012. 1http://centria.di.fct.unl.pt/nohr/ 2http://protege.stanford.edu 3http://www.ihtsdo.org/snomed-ct/
NoHR1 is a plug-in for the ontology editor Prote´ge´2 that al+ ontologies and lows its users to query combinations of E L? non-monotonic rules in a top-down manner.
Its motivation stems from the fact that many current ontologies, such as the very large health care ontologies widely used in the area of medicine, e.g., SNOMED CT,3 are expressed in OWL 2 EL, one of the OWL 2 profiles [Motik et al., 2013], and its underlying description logic (DL) E L++ [Baader et al., 2005]. Yet, due to their monotonic semantics, i.e., previously drawn conclusions persist when new additional information is adopted, DL-based ontology languages [Baader et al., 2010] are not suitable to model defaults and exceptions with a closed-world view, a frequently requested feature, e.g., when matching patient records to clinical trial criteria [Patel et al., 2007].
Among the plethora of approaches for extending DLs with
non-monotonic features and deal with this problem
This choice is motivated, on the one hand, by the fact that
non-monotonic logic programming rules are one of the most
well-studied formalisms that admit expressing defaults,
exceptions, and also integrity constraints in a declarative way,
and are part of RIF [Boley and Kifer, 2013], the other
expressive language for the Semantic Web whose standardization
is driven by the W3C.4 On the other hand, Hybrid MKNF
provides a very general and flexible framework for
combining DL ontologies and non-monotonic rules
NoHR is thus applicable to combinations of
nonmonotonic rules and OWL 2 EL ontologies. However, other
applications
OWL 2 QL and the DL-Lite family [Calvanese et al., 2007; Artale et al., 2009] to which the DL underneath OWL 2 QL belongs, DL-LiteR, is suitable in these cases and has recently drawn a lot of attention in research and in applications.
Even though a simple language at first glance, it is expressive enough to capture basic ontology languages, conceptual data models, e.g., Entity-Relationship, and object-oriented formalisms, e.g., basic UML class diagrams. Reasoning focuses on answering queries by rewriting the initial query, with the help of the ontology, into a set of queries that can be answered using an industry-strength SQL engine over the data. This provides the very low data complexity of LOGSPACE for query answering, but also links directly to applications in ontology-based data access (OBDA) [Calvanese et al., 2011; Kontchakov et al., 2011]. Altogether, OWL 2 QL is naturally tailored towards huge datasets.
In order to provide also such applications based on OWL 2 QL with the additional expressive power obtained from combining DL ontologies with non-monotonic rules, in this paper, we extend NoHR to OWL 2 QL. Whereas, at first sight, this could seem like a routine exercise, the fact that, to the best of our knowledge, no dedicated open-source OWL 2 QL classifier with OWL API is available, and applying the E L reasoner ELK [Kazakov et al., 2013], currently used in NoHR, to classify a DL-LiteR ontology is obviously not possible, we have to follow a different path here, namely translate the ontology directly into rules. This introduces some non-trivial problems, in particular, the need to capture unsatisfiable concepts and roles and irreflexive roles, for which in [Calvanese et al., 2007] a closure of so-called negative axioms is computed, potentially introducing a huge number of additional axioms. We solve this problem by introducing an extension of the graph, used, e.g., in [Lembo et al., 2013] for classification in OWL QL, to negative axioms. The resulting translation is implemented as a module of the NoHR translator, and its performance evaluated. Our main contributions are: A procedure for translating DL-LiteR ontologies into rules which allows answering queries over hybrid KBs combining such ontologies and non-monotonic rules; An substantial extension of the Prote´ge´ plug-in NoHR to include OWL 2 QL ontologies, beyond DL-LiteR via normalizations, including optimizations on the number of created rules and the use of tabling in the top-down query engine XSB Prolog;5 An evaluation of our extension that shows that NoHR for OWL 2 QL maintains all positive evaluation results of the OWL 2 EL version [Ivanov et al., 2013], and is even faster during pre-processing, as no classification is necessary, in exchange for an on average slightly longer response time during querying.
The remainder of the paper is structured as follows. In Sect. 2, we briefly recall DL-LiteR and MKNF knowledge bases as a tight combination of the former DL and non-monotonic rules. Then, we present the translation of DL-LiteR ontologies which allows us to query such MKNF knowledge bases in Sect. 3. In Sect. 4, we discuss the changes made in the implementation for OWL 2 QL including optimizations, and evaluate it in Sect. 5, before we conclude in Sect. 6.
2.1
DL-LiteR The description logic underlying OWL QL is DL-LiteR, one language of the DL-Lite family [Calvanese et al., 2007; Artale et al., 2009], which we recall following the presentation in [Knorr and Alferes, 2011].
The syntax of DL-LiteR is based on three disjoint sets of individual names NI, concept names NC, and role names NR. Complex concepts and roles can be formed according to the following grammar B ! A j 9Q
C ! B j :B
Q ! P j P
R ! Q j :Q where A 2 NC is a concept name, P 2 NR a role name, and P its inverse. We also call B a basic concept, Q a basic relation, C a general concept and R a general role.
A DL-LiteR knowledge base O = (T ; A) consists of a TBox T and an ABox A. The TBox contains general inclusion axioms (GCI) of the form B v C and role inclusion axioms (RI) of the form Q v R, with B, C, Q, and R defined as above. We term positive inclusion axioms all GCIs and RIs in O such that C is a basic concept and R is a basic relation, respectively, and all other GCIs and RIs negative inclusion axioms. We also assume that Q denotes the role P if Q = P , and P if Q = P . The ABox contains assertions of the form A(a) and P (a; b) where A 2 NC, P 2 NR, and a; b 2 NI. Assertions C(a) for general concepts C can be included by A v C and A(a) for a new concept name A.
The semantics of DL-LiteR is based on interpretations I = ( I ; I ) consisting of a nonempty interpretation domain
I and an interpretation function I that assigns to each individual a a distinct6 element aI of I , to each concept name A a subset AI , and to each role name P a binary relation P I over I. This can be extended as usual: (P )I = f(i2; i1) j (i1; i2) 2 P I g (9Q)I = fi j (i; i0) 2 QI g (:B)I = (:Q)I =
I n BI I
I n QI
An interpretation I is a model of GCI B v C and of RI Q v R if BI CI and QI RI respectively. I is also a model of an assertion A(a) (P (a; b)) if aI 2 AI ((aI ; bI ) 2 P I ). Given an axiom/assertion we denote by I j= that I is a model of . A model of a DL-LiteR KB O = (T ; A) is an interpretation I such that I j= holds for all 2 T [ A, and O is satisfiable if it has at least one model, and unsatifiable otherwise. Also, O entails axiom , written O j= , if every model of O satisfies . 2.2
MKNF Knowledge Bases MKNF knowledge bases (KBs) build on the logic of minimal knowledge and negation as failure (MKNF) [Lifschitz, 1991]. Two main different semantics have been defined [Motik and Rosati, 2010; Knorr et al., 2011], and we focus on the wellfounded version [Knorr et al., 2011], due to its lower computational complexity and amenability to top-down querying without computing the entire model. Here, we only point out 6Hence, the unique name assumption is applied and, as shown in [Artale et al., 2009], dropping it would increase significantly the computational complexity of DL-LiteR. important notions following [Ivanov et al., 2013], and refer to [Knorr et al., 2011] and [Alferes et al., 2013] for the details.
We start by recalling MKNF knowledge bases as presented in [Alferes et al., 2013] to combine an ontology and a set of non-monotonic rules (similar to a normal logic program). Definition 1. Let O be an ontology. A function-free firstorder atom P (t1; : : : ; tn) s.t. P occurs in O is called DLatom; otherwise non-DL-atom. A rule r is of the form H
A1; : : : ; An; notB1; : : : ; notBm (1) where the head of r, H, and all Ai with 1 i n and Bj with 1 j m in the body of r are atoms. A program P is a finite set of rules, and an MKNF knowledge base K is a pair (O; P). A rule r is DL-safe if all its variables occur in at least one non-DL-atom Ai with 1 i n, and K is DL-safe if all its rules are DL-safe.
DL-safety ensures decidability of reasoning with MKNF knowledge bases and can be achieved by introducing a new predicate o, adding o(i) to P for all constants i appearing in K and, for each rule r 2 P, adding o(X) for each variable X appearing in r to the body of r. Therefore, we only consider DL-safe MKNF knowledge bases.
Example 1. Consider an MKNF knowledge base K as given below for recommending CDs adapted from [Knorr et al., 2011] (with some modifications). We denote DL-atoms and constants with upper-case names and non-DL-atoms and variables with lower-case names.7 commonly achieved using a partition of modal atoms, i.e., all expressions of the form K' for each K' or not' occurring in (K). For [Knorr et al., 2011], such a partition assigns true, false, or undefined to (modal) atoms, and can be effectively computed in polynomial time. If K is MKNFconsistent, then this partition does correspond to the unique model of K [Knorr et al., 2011], and, like in [Alferes et al., 2013], we call the partition the well-founded MKNF model Mwf (K). Here, K may indeed not be MKNF-consistent if the ontology alone is unsatisfiable, or by the combination of appropriate axioms in O and rules in P, e.g., A v :B, and A(a) and B(a) . Strictly speaking, unlike [Ivanov et al., 2013], we do not have to make assumptions on the satisfiability of O as we are not going to use a classifier when processing DL-LiteR ontologies. Still, for the technical results established in Sec. 3, we will rely on satisfiability, since we are able to entail everything from an unsatisfiable O, whereas the translation into rules defined in Sec. 3 would not permit that. This is why in the following, we assume that O occurring in K is satisfiable, which does not truly constitute a restriction as we can always turn the ABox into rules without any effect on Mwf (K). An alternative approach would be to use one of the paraconsistent semantics for MKNF knowledge bases [Kaminski et al., 2015], but this is outside the scope of this paper, and an issue for future work as currently no paraconsistent correspondence to the querying procedure SLG(O) used here exists. interesting (x ) owns(Summertime)
9HasArtist 9HasComposed
This example shows that we can seamlessly express defaults and exceptions, such as recommending pieces as long as they are not owned or having a low evaluation, and at the same time taxonomic/ontological knowledge including information over unknown individuals, such as every piece having at least one artist without having to specify whom, but also features of DL-LiteR, such as domain and range restrictions (of roles).
The semantics of MKNF knowledge bases K is usually given by a translation into an MKNF formula (K), i.e., a formula over first-order logic extended with two modal operators K and not. Namely, every rule of the form (1) is translated into KH KA1; : : : ; KAn; notB1; : : : ; notBm, (P) is the conjunction of the translations of its rules, and (K) = K (O) ^ (P) where (O) is the first-order translation of O. Reasoning with such MKNF formulas is then v Artist Piece v 9HasArtist 2.3 Querying in MKNF Knowledge Bases
In [Alferes et al., 2013], a procedure, called SLG(O), is dev Piece Artist v :Piece fined for querying MKNF knowledge bases under the wellv HasArtist founded MKNF semantics. This procedure extends SLG resPiece(x ); notowns(x ); notlowEval (x ); olution with tabling [Chen and Warren, 1996] with an oracle to O that handles ground queries to the DL-part of K by interesting (x ) returning (possibly empty) sets of atoms that, together with
Piece(x ); notowns(x ); Piece(y ); owns(y ); O and information already proven true, allows us to derive Artist (z ); HasArtist (y ; z ); HasArtist (x ; z ) the queried atom. We refer to [Alferes et al., 2013] for the full account of SLG(O), and only recall a few crucial notions Piece(Summertime) necessary in the following.
SLG(O) is based on creating top-down derivation trees with the aim of answering (DL-safe) conjunctive queries Q = q(X~ ) A1; : : : ; An; notB1; : : : ; notBm where each variable in Q occurs in at least one non-DL atom in Q, and where X~ is the (possibly empty) set of requested variables appearing in the body.
In general, the computation of Mwf (K) uses two different
versions of K in parallel to guarantee that a) coherence is
ensured, i.e., if :P (a) is derivable, then notP (a) has to be
true as well
7To ease readability, we omit the auxiliary atoms that ensure DLsafety and leave them implicit.
In [Alferes et al., 2013], the notion of oracle is defined to handle ground queries to the ontology, but before we recall that notion, we use an example to illustrate the idea.
Example 2. Recall K in Ex. 1. Here, we omit Kd and restrict ourselves to K, which suffices our purposes. Consider query q = recommend (Summertime). By instantiating the body of the matching rule head in K with x = Summertime, we obtain two new queries. The first one, Piece(Summertime), can be answered by means of the rule with matching head.
The second, notowns(Summertime), is handled by querying for owns(Summertime), for which a corresponding rule exists, so notowns(Summertime) fails, hence q is false.
Consider q1 = recommend (RhapsodyInBlue). Using the same rule with matching rule head we obtain four new instantiated queries from the rule body. Now, Piece(RhapsodyInBlue) cannot be derived from the rules, but we can query the ontology and the oracle will return, e.g., a query HasComposed (x1 ; RhapsodyInBlue) that if proven true can be added to O, which would allow us to derive the queried goal. This query succeeds because of HasComposed (Gershwin; RhapsodyInBlue) , and so does Piece(RhapsodyInBlue). Then, we cannot prove owns(RhapsodyInBlue) nor lowEval (RhapsodyInBlue), so both fail, succeeding their (default) negated queries. For the remaining new query interesting (RhapsodyInBlue), the second rule head matches, creating further subgoals. The first two were just answered, as the next two with y = Summertime for q. The remaining also follow from the interplay of O and P in K, so q1 succeeds.
We recall the notions of a complete and a (correct) partial oracle from [Alferes et al., 2013].
Definition 2. Let Kd = (O; Od; Pd) be a doubled MKNF KB, I a set of ground atoms (already proven to be true), S a ground query, and L a set of ground atoms such that each L 2 L is unifiable with at least one rule head in Pd.
The complete oracle for O, denoted compdTO, is defined by compTO(I; S; L) iff O [ I [ L j= S or O [ I [ L j= S. A partial oracle for O, denoted pTO, is a relation pTO(I; S; L) such that if pTO(I; S; L), then O[I [L j= S or Od[I [L j= S for consistent O [ I [ L and Od [ I [ L, respectively.
A partial oracle pTO is correct w.r.t. compTO iff, for all MKNF-consistent Kd, replacing compTO in SLG(O) with pTO succeeds for exactly the same set of queries.
Partial oracles may avoid returning unnecessary answers L, such as non-minimal answers or those that try to derive an MKNF-inconsistency even though Kd is MKNF-consistent.
Also, correctness of partial oracles is only defined w.r.t
MKNF-consistent K. The rationale is that, when querying
top-down, we want to avoid checking whether the entire KB
Kd is MKNF-consistent. This leads to para-consistent
derivations if Kd is not MKNF-consistent, e.g., some atom P is true,
yet P d is false, while other independent atoms are evaluated
as if Kd was MKNF-consistent
+ [Ivanov et al., 2013], axioms As argued for the case of E L? with 9 on the right-hand side, e.g., Piece v 9HasArtist , cannot be translated straightforwardly into rules, nor do they directly contribute to the result when querying for ground instances, e.g., of HasArtist (x ; y ). Still, such axioms may contribute to derivations within O, which is why, in [Ivanov et al., 2013], a classification using the dedicated and highly efficient E L reasoner ELK [Kazakov et al., 2013] is first applied to derive implicit consequences. These, together with all axioms in O, are then translated into rules, now discarding certain axioms with 9 on the right-hand side.
Here, since to the best of our knowledge no dedicated, open-source OWL 2 QL classifier with OWL API is available, we opt to follow a different path, namely translate the ontology directly into rules. This also simplifies and shortens the preprocessing phase and avoids a priori-classification, but requires some non-trivial considerations to ensure that no derivations are lost in the process, which we will explain next.
Essentially, axioms, such as Piece v 9HasArtist , cannot be translated into a rule HasArtist (x ; y ) Piece(x ) using a universal variable y, as this would allow us to derive HasArtist (x ; y ) for any Piece(x ) and y, which is clearly not what the axiom expresses. Using a new constant c instead of y would not be correct either, as querying for HasArtist (x ; y ) would return HasArtist (x ; c) for any Piece(x ) for the same c. Therefore, we proceed differently by introducing new auxiliary predicates that intuitively represent the domain and range of roles. For our example, this will yield the rule
the domain of HasArtist (and RHasArtist its range). Using such auxiliary predicates also means that we have to make sure that, e.g., HasArtist (Summertime; Gershwin) allows us to derive DHasArtist (Summertime), which can be achieved via an additional rule DHasArtist (x ) HasArtist (x ; y ). Moreover, for HasComposed v HasArtist , it does not suffice to translate the axiom to HasArtist (x ; y ) HasComposed (y ; x ), but also link the new auxiliary predicates for both roles, by adding, DHasArtist (x ) RHasComposed (x ) and
We now formalize this translation, and we start by introducing notation on how to translate general concepts and roles. For that purpose, we formally introduce for each role P 2 NR auxiliary predicates DP and RP with the intuition of representing the domain and range of P . Also, similar to previous work in [Alferes et al., 2013; Ivanov et al., 2013], we use special atoms N H(t~i) in SLG(O) that represent a query :H(t~i) to the oracle. These are, of course, only relevant if O contains negative inclusion axioms.
Definition 3. Let C be a concept, R a role, x and y variables, and v a new (anonymous) variable (disjoint from x and y). We define tr(C; x) and tr(R; x; y) as follows:
tr(C; x) = tr(R; x; y) = 8A(x) > > >>>DP (x) <
RP (x) >>>N A(x) > >:tr(:Q; x; v) 8P (x; y) > ><P (y; x) >N P (x; y) > :N P (y; x) if C = A if C = 9P if C = 9P if C = :A if C = :9Q if R = P if R = P if C = :P if C = :P We obtain trd(C; x) and trd(Q; x; y) from tr(C; x) and tr(Q; x; y) by substituting all predicates P in tr(C; x) and tr(Q; x; y) with P d, respectively.
tr(C; x) and tr(R; x; y) handle both positive and negative inclusions and no additional case distinction is necessary.
Before we present the actual translation, we need to introduce one central notion, namely a graph to represent the axioms in a given TBox T as well as the implicitly derivable axioms, which will be necessary for defining the translation itself, but also turn out useful when establishing the correctness of the translation. Graphs have been used for classification in OWL QL (of positive inclusion axioms) [Lembo et al., 2013], and we extend the notion here to also take negative inclusion axioms into account. We thus introduce the digraph (directed graph) of T as follows.
Definition 4. Let T be a DL-LiteR TBox. The digraph of T , GT = hV; E i, is constructively defined as follows. 1. If A 2 NC , then A and :A are in V; 2. If R 2 NR, then P , 9P , 9P , :P , :9P , and :P are in V; 3. If B1 v B2 2 T , then the edges (B1; B2) and (:B2; :B1) are in E ; 4. If Q1 v Q2 2 T , then the edges (Q1; Q2), (Q1 ; Q2 ), (9Q1; 9Q2), (9Q1 ; 9Q2 ), (:Q2; :Q1),(:Q2 ; :Q1 ), (:9Q2; :9Q1) e (:9Q2 ; :9Q1 ) are in E ; 5. If B1 v :B2 2 T , then the edges (B1; :B2) and (B2; :B1) are in E ; 6. If Q1 v :Q2 2 T , then the edges (Q1; :Q2), (Q2 ; :Q1 ), (9Q1; :9Q2), (9Q2; :9Q1), (9Q1 ; :9Q2 ) and (9Q2 ; :9Q1 ) are in E .
Basically, each possible general concept and general role over NC and NR is a node in GT , and the directed edges represent logical implications that follow from the axioms. Namely, for items 3. and 5., the subset inclusion itself and its contrapositive are in E , and this is similar for items 4. and 6., only that the additional combinations due to inverses, 9, and : have to be taken into account. In this sense, the graph can be understood as capturing all subset inclusions (explicit and implicit) in O, i.e., whenever there is a path from concept C1 to concept C2 and from role R1 to role R2, then C1 v C2 and R1 v R2 hold respectively. An Example of such a digraph is given in Fig. 1 for the TBox T from Example 1.
One observation to be made in Fig. 1, is that 9HasComposed v :9HasComposed , i.e., HasComposed is irreflexive. Even though this does not entail any assertion, knowing that 8x::HasComposed (x ; x ) does hold should be captured in the translation. We introduce (T ), the set of irreflexive roles in T , to be able to ensure exactly that. Definition 5. Let T be a DL-LiteR TBox and GT its digraph. W e define (T ) as the smallest set of all P 2 NR that satisfy at least one of the following conditions: 1. For some B1 v :B2 2 T , there exist paths from 9P to
B1 and from 9P to B2; 2. For some B1 v :B2 2 T , there exist paths from 9P to B1 and from 9P to B2; 3. For some Q1 v :Q2 2 T , there exist paths from P to
Q1 and from P to Q2; 4. For some Q1 v :Q2 2 T , there exist paths from P to
Q1 and from P to Q2.
This notion builds on GT , which is also required for detecting a further set of derivations. Imagine we would (wrongfully) add Artist v 9HasComposed to O in Example 1. Then there would be a path from Artist to both Piece and :Piece, i.e., the concept Artist would be unsatisfiable. Note that independently of whether the hybrid KB is MKNFinconsistent or not, we need to make sure that all unsatisfiable concepts and roles are determined, so we introduce (T ), quite similar in spirit to (T ).
Definition 6. Let T be a DL-LiteR TBox and GT its digraph. We define (T ) as the smallest set of all A 2 NC such that, for some B1 v :B2 2 T , there exist paths from A to both B1 and B2, and all P 2 NR that satisfy at least one of the following conditions: 1. For some B1 v :B2 2 T , there exist paths from 9P to both B1 and B2; 2. For some B1 v :B2 2 T , there exist paths from 9P to both B1 and B2; 3. For some Q1 v :Q2 2 T , there exist paths from P to both Q1 and Q2; 4. For some Q1 v :Q2 2 T , there exist paths from P to both Q1 and Q2.
With all pieces in place, we can finally introduce the definition of the translation of a DL-LiteR ontology into rules. roles, x, y variables, and a, b individuals, as the smallest set containing: Lemma 1. Let O be a DL-LiteR ontology, A a unary and R a binary predicate: (e) for every P 2 NR:
DP (x) P (x; y) DP d(x) P d(x; y)
RP (y) P (x; y) RP d(y) P d(x; y) (a1) for every A(a) 2 O:
A(a) Ad(a) notN A(a) (a2) for every P (a; b) 2 O:
P (a; b) P d(a; b) notN P (a; b) (s1) for every B1 v B2 2 O: tr(B2; x) tr(B1; x) trd(B2; x) trd(B1; x); nottr(:B2; x) tr(:B1; x) tr(:B2; x) (s2) for every Q1 v Q2 2 O: tr(Q2; x; y) tr(Q1; x; y) trd(Q2; x; y) trd(Q1; x; y); nottr(:Q2; x; y) tr(9Q2; x) tr(9Q1; x) trd(9Q2; x) trd(9Q1; x); nottr(:9Q2; x) tr(9Q2 ; x) tr(9Q1 ; x) trd(9Q2 ; x) trd(9Q1 ; x); nottr(:9Q2 ; x) tr(:Q1; x; y) tr(:Q2; x; y) (n1) for every B1 v :B2 2 O:
tr(:B1; x) tr(B2; x) tr(:B2; x) (n2) for every Q1 v :Q2 2 O: tr(:Q2; x; y) tr(Q1; x; y) tr(:Q1; x; y) tr(Q2; x; y) (i1) for every A 2 (T ): N A(x) (i2) for every P 2 (T ): N P (x; y) (ir) for every P 2 (T ): N P (x; x) tr(B1; x)
Item (e) ensures that the domain and range of roles is correctly encoded, items (a1) and (a2) translate the ABox, items (s1) and (s2) the positive inclusions, items (n1) and (n2) the negative inclusions, and items (i1), (i2), and (ir) introduce the rules representing unsatisfiable concepts and unsatisfiable d contains the rule repreand irreflexive roles. Note, that PO sentation for both O and Od, which is why items (e)–(s2) contain doubled rules. Of course, if O does not contain negative inclusion axioms, then we can skip all these, as well as items (n1)–(ir) which will not contribute anything anyway in this case. The additional default atoms are added to the doubled rules to be in line with the idea of the doubling of rules in [Alferes et al., 2013]: whenever, e.g., A(x) is “classically false” for some x, i.e., N A(x) holds, then we make sure that Ad(x) is derivable as false for that same x from the rules, but not necessarily A(x), thus allowing to detect potential MKNF-inconsistencies. That is also the reason why neither (n1)–(ir) nor the contrapositives in (s1) and (s2) do produce the doubled counterparts: atoms based on predicates of the forms N Cd or N Rd are not used anywhere. Finally, the doubled rules in (e) do not contain the default negated atom as this case only associates domain and range to a role assertion, either present in the ABox or derived elsewhere. Additionally, predicates N DP or N RP are not used anywhere, so such default negated atoms would be of no impact.
We can establish three correspondences between entailment from satisfiable O and the program resulting from the translation POd. First, we consider positive atoms. O j= A(a) iff PO j d = d = A(a) and O j= R(a; b) iff PO j
R(a; b).
A similar property holds for (classically) atoms.
Lemma 2. Let O be a DL-LiteR ontology, A a unary and R a binary predicate:
d = N A(a) and O j= :R(a; b) iff O j= :A(a) iff PO j
d = N R(a; b).
PO j
We can also show the correspondent to Lemma 1 for the doubled predicates.
Lemma 3. Let O be a DL-LiteR ontology, A a unary and R a binary predicate:
Od j= Ad(a) iff POd j= Ad(a) and Od j= Rd(a; b) iff d = Rd(a; b).
PO j
Thus, we can define a correct partial oracle based on POd. Theorem 4. Let Kd = (O; Od; Pd) be a doubled MKNF KB and pT QL a partial QL oracle such that pT QL(I; S; L) iff d O O PO [ I [ L j= S. Then pT QL is a correct partial oracle w.r.t.
O compTO.
Instead of coupling two rule reasoners that interact with each other using an oracle, we can simplify the process altogether and integrate both into one rule reasoner. The resulting approach is decidable with polynomial data complexity. Theorem 5. Let K = (O; P) be an MKNF KB with O in DL-LiteR. An SLG(O) evaluation of a query in KQL = (;; (Pd [ POd)) is decidable with data complexity in PTIME. 4
In this section, we briefly describe the changes to the architecture of our plug-in and discuss some optimizations implemented w.r.t. the translation described in Sec. 3.
To allow the usage of OWL QL ontologies, changes were essentially made in the translator. First, since now two OWL profiles are supported we have introduced a switch that checks the profile of the loaded/edited ontology. If it is in OWL EL, then NoHR behaves as described in [Ivanov et al., 2013], i.e., the reasoner ELK is used to classify the ontology and return the inferred axioms to translator, which are then translated. Otherwise, we treat O of the hybrid KB based on the translation described in Sec. 3 for OWL QL.
Notably, in Sec. 3, we only considered DL-LiteR while OWL QL includes a number of additional constructs which often can be expressed in DL-LiteR. To account for that, we first normalize such expressions to axioms in DL-LiteR. This includes ignoring certain expressions, most of which do not contribute anything to derivations, e.g., SubClassOf(B owl:Thing), while others make the ontology unsatisfiable, such as ClassAssertion(owl:Nothing a), although, as mentioned before, with no effect when querying the translated rules. The details on the normalization can be found in the appendix of the extended paper.
Subsequently, the graph is constructed, for determining unsatisfiable concepts and unsatisfiable and irreflexive roles, after which the translation is performed, which includes a number of optimizations. First, whenever there are no negative inclusions, the doubled rules are omitted in the cases (e)–(s2) of Def. 7. Additionally, case (e) is limited to those rules whose heads appear in the body of another rule. Both steps reduce the overall number of rules created during the translation.
The second group of optimizations is related to tabling in XSB, which contributes to help answering queries very efficiently in a top-down manner, and avoid infinite loops while querying. However, simply declaring all predicates to be tabled is very memory-consuming, so we reduced the number of tabled predicates without affecting loop detection. For example, only predicates that appear in any rule head and in any rule body need to be tabled. In addition, rules with an empty body (facts) can be ignored in the previous criterion, as these will not cause an infinite loop. 5
In this section, we evaluate our system and show that a) preprocessing is even faster when compared to NoHRs EL version, which was already capable of preprocessing large ontologies in a short period of time, b) querying scales well, even for over a million facts/assertions in the ABox, despite being slightly slower on average in comparison to EL, and c) adding rules scales linearly for pre-processing and querying, even for an ontology with many negative inclusions.
Tests were performed on a Notebook running Linux 3.17.6-1-ARCH (x86 64) with 1.8 GHz 4x Intel Core i3 processor and 4 GB of RAM. We used XSB 3.4.0 for querying, ran all tests in a terminal version and Java with “-XX:+AggressiveHeap” option, and report averages over 5 runs.
First, we considered LUBM8 [Guo et al., 2005], a standard benchmark for evaluating queries over a large data set. The ontology itself is already rather simple and we reduced it even a bit further by removing all axioms that are not common to both OWL 2 QL and EL. The resulting ontology has only ninety logical axioms, but this way we can use it with both translators included in NoHR and compare their performance. We created instances of LUBM 1–10 with assertions ranging
from roughly 100,000 to over 1,300,000 and performed preprocessing from loading the ontology to loading the translation result in XSB. The results for both translators EL and QL can be found in Fig. 2. Note that the segment “Initialization” is the time for preparing the translation, which for EL includes classifying the ontology, while the larger part of the segment “Other” corresponds to loading the ontology.
We can observe that QL is considerably faster, indeed up to 40s for LUBM10, to a considerable extent due to avoiding classification. Besides that, the preprocessing time increases linearly, and the overall time for preprocessing is acceptable in our opinion as this is only done once before querying.
Next, we also queried the resulting ten rule sets in XSB for both EL and QL using queries from the LUBM benchmark, that were manually transformed from SPARQL to queries usable in XSB. Among the fourteen provided queries, we chose seven, because the others were either no longer meaningful due to removal of certain axioms/DL constructors during the initial simplifications we applied to LUBM, or because initial tests revealed that XSB would run out of memory for a query, simply because, for our test system with 4GB memory, too much data was being gathered in the tables to answer the query. In more detail, we used the queries 1, 2, 3, 4, 5, 7, 10 from the LUBM benchmark. The results are shown for some representatives in Fig. 3. Basically, for queries 1, 3, 4, and 10, no real difference between EL and QL exists and the response time is strictly below 1s. For query 7, there exists a slight difference in favor of EL with 2.5s vs. 1s for LUBM10, whereas for queries 2 and 5 the difference increases. In all cases, the response time grows linearly w.r.t. the increasing size of LUBM, and we can conclude that on average querying in QL is slightly slower. Here, EL compensates for the longer preprocessing, and this effect becomes more visible, the more complex the query is and the more data needs to gathered to answer it. Intuitively, this can be explained by looking at a simple example with two axioms A v 9R and 9R v B For EL, classification, yields A v B and only one axiom is translated and only one derivation step is required in XSB to obtain, say B(a) from A(a). For QL, both axioms are translated directly without classification, using DR, but now, two derivation steps would be required in XSB to obtain B(a) from A(a). It thus seems that deciding which of the two forms of translations performs better depends on the kind (and number) of queries we pose.
Finally, with the aim of also testing a more expressive OWL 2 QL ontology, we used the LIPID ontology,9 which has, besides 749 subclass axioms, 1,486 class disjointness axioms and 20 inverse object properties in combination with non-monotonic rules. The latter were created by means of the rule generator already used in [Ivanov et al., 2013] with a ratio 1:10 between rules and facts, also introducing some new predicates not present in the ontology itself. We performed the preprocessing step and observed only slight effects due to the increasing amount of rules. The time for processing the ontology was naturally stable for all steps, and overall processing time was between 2 and 3s. Notably, the considerable amount of negative inclusions had no significant impact on time, e.g., when constructing the graph. Then, we posed three simple queries (Query1–3), namely Acyl Ester Chain(X), Lipid(X), and Entity(X) to the resulting rule sets in XSB. The results are shown in Fig. 4. As we can see, the response time is still very reasonable, from clearly below 1s to up to 8s. Still, the results in our opinion already show the effect of the arbitrary rules that tend to introduce links between predicates that increase the search space. This can be noted in particular for Query1, where in one case a smaller set of rules results in a higher response time, simply because no generated rule set is a subset of another. We note that performance tests of querying (non-monotonic) rules and ontologies would considerably benefit from real datasets but to the best of our knowledge currently none are available. 6
We have extended NoHR, the Prote´ge´ plug-in that allows to query non-monotonic rules and ontologies in OWL 2 EL, to also admit ontologies in OWL 2 QL. While the principal architecture of the tool remains the same, the crucial module that translates the ontology into rules with the help of a classifier simply cannot be re-used, which is why we introduced a novel direct translation for OWL 2 QL ontologies to cover this profile. We have implemented this translation and discussed optimizations. The evaluation shows that it maintains all positive evaluation results of the OWL 2 EL version [Ivanov et al., 2013], and is even faster during pre-processing, as no classification is necessary, in exchange for an on average slightly longer response time during querying.
Besides the OWL 2 EL profile supported by NoHR, and compared to in Sect. 5, also [Gomes et al., 2010; Knorr and
Alferes, 2011] both build on the well-founded MKNF semantics [Knorr et al., 2011]. While [Gomes et al., 2010] uses the non-standard CDF framework integrated in XSB, which complicates compatibility to standard OWL tools based on the OWL API, [Knorr and Alferes, 2011] presents an OWL 2 QL oracle based on common rewritings in the underlying DL DL-LiteR [Artale et al., 2009], but would require constant interaction between a rule reasoner and a DL reasoner, which is why we believe it to be less efficient than our approach.
Two related tools are DReW [Xiao et al., 2013] and HD
Rules [Drabent et al., 2007], although based on different
underlying formalisms to combine ontologies and rules
Future work includes the extension to OWL 2 RL, but developing an alternative for OWL 2 QL using the classifier integrated in ontop [Kontchakov et al., 2014] once its OWL API becomes available, or even the general reasoner Konclude [Steigmiller et al., 2014], could shed more light on whether classification or direct translation fares better for proper OWL 2 QL ontologies. The efficiency of the latter reasoner also motivates looking into non-polynomial DLs, with possible influences from recent work on rewriting disjunctive datalog programs [Kaminski et al., 2014]. Finally, we may extend NoHR for OWL 2 QL (and EL) to the paraconsistent semantics [Kaminski et al., 2015] that would provide true support to the already occasionally observed paraconsistent behavior, or alternatively, to either generalizations of hybrid KBs [Gonc¸alves and Alferes, 2010; Knorr et al., 2014; 2012; Knorr, 2015] or dynamics in hybrid KBs [Slota et al., 2011; Slota and Leite, 2012], or even both [Gonc¸alves et al., 2014].