Datalog Rewriting Techniques for Non-Horn Ontologies Mark Kaminski, Yavor Nenov, and Bernardo Cuenca Grau Department of Computer Science University of Oxford, UK Abstract. We study the closely related problems of rewriting disjunc- tive datalog programs and non-Horn DL ontologies into plain datalog programs that entail the same facts for every dataset. We first propose the class of markable disjunctive datalog programs, which is efficiently recognisable and admits polynomial rewritings into datalog. Markabil- ity naturally extends to SHI ontologies, and markable ontologies admit (possibly exponential) datalog rewritings. We then turn our attention to resolution-based rewriting techniques. We devise an enhanced resolution rewriting procedure for disjunctive datalog, and propose a second class of SHI ontologies that admits exponential datalog rewritings via reso- lution. Finally, we evaluate the feasibility of our techniques over a large corpus of ontologies, with encouraging results. 1 Introduction Query answering over DL ontologies is a key reasoning problem for many ap- plications. Query answering can sometimes be implemented via rewriting into datalog, where a rewriting of a query Q w.r.t. an ontology O is a datalog program P that preserves the answers to Q for any dataset. Rewriting queries into data- log not only ensures tractability in data complexity—an important requirement in data-intensive applications—but also enables the reuse of scalable rule-based reasoners such as OWLim [4], Oracle’s Data Store [20], and RDFox [15]. Datalog rewriting techniques have been investigated in depth for Horn DLs, and optimised algorithms have been implemented in systems such as Requiem [17], Clipper [6], and Rapid [19]. Techniques for non-Horn DLs, however, have been studied to a lesser extent. Atomic queries were shown datalog rewritable w.r.t. DL-Litebool ontologies [1, 5]. In contrast, datalog rewritings may not exist for ontologies expressed in the basic non-Horn DL ELU [12, 5], and sufficient conditions that ensure rewritability were identified in [9]. Datalog rewritability of atomic queries w.r.t. SHI ontologies was proved NExpTime-complete in [3]. Our focus is on atomic queries. In this setting, rewritability for ontologies is strongly related to the rewritability of disjunctive datalog programs into datalog: every SHIQ ontology can be transformed into a disjunctive program that entails the same facts for each dataset (thus preserving answers to atomic queries) [8]. In [10], we proved a characterisation of datalog rewritability for disjunctive programs based on linearity: a restriction that requires each rule to contain at most one IDB atom in the body. We showed that every linear disjunctive pro- gram can be polynomially rewritten into plain datalog; conversely, every datalog program can be polynomially translated into an equivalent linear disjunctive datalog program. Motivated by this characterisation, we proposed weakly linear disjunctive datalog : a language that extends both datalog and linear disjunctive datalog, and which admits polynomial datalog rewritings. In a weakly linear program, the linearity requirement is relaxed: instead of applying to all IDB predicates, it applies only to those that “depend” on a disjunctive rule. A different approach to rewriting disjunctive programs into datalog by means of a resolution-based procedure was proposed in [5]. The procedure works by sat- urating the input disjunctive program P such that in each resolution step at least one of the premises is a non-Horn rule; if this process terminates, the procedure outputs the subset of datalog rules in the saturation, which is guaranteed to be a rewriting of P. The procedure was shown to terminate for so-called simple disjunctive programs; furthermore, it was shown that DL-Litebool ontologies can be transformed into disjunctive programs that satisfy the simplicity condition. In this paper, we present several improvements over existing techniques, and evaluate their feasibility in practice over a large corpus of non-Horn ontologies. In Section 3, we propose the class of markable disjunctive datalog programs, in which the weak linearity condition from [10] is further relaxed. We show that our extended class of programs is efficiently recognisable and that each markable pro- gram admits a polynomial datalog rewriting. These results can be readily applied to ontology reasoning. We first consider the “intersection” between OWL 2 and disjunctive datalog (which we call RLt ), and show that fact entailment over RLt ontologies corresponding to a markable program is tractable in combined com- plexity (and hence no harder than in OWL 2 RL). We then lift the markability condition to ontologies, and show that markable SHI-ontologies admit a (pos- sibly exponential) datalog rewriting. In Section 4, we refine the resolution-based rewriting procedure from [5] by further requiring that only atoms involving dis- junctive predicates can participate in resolution inferences. This refinement can significantly reduce the number of inferences drawn during saturation, without affecting correctness. We then turn our attention to ontologies, and propose an extension of the logics in the DL-Litebool family that admits (possibly exponen- tial) datalog rewritings. Our empirical results show that many realistic non-Horn ontologies can be rewritten into datalog. Furthermore, we have tested the scala- bility of query answering over the programs obtained using our techniques, with promising results. Proofs are delegated to a technical report [11]. 2 Preliminaries We consider standard notions of terms, atoms, literals, formulae, sentences, and entailment. A fact is a ground atom and a dataset is a finite set of facts. We assume that equality ≈ is an ordinary predicate and that each set of formu- lae contains the axiomatisation of ≈ as a congruence relation for its signature. Clauses, substitutions, most general unifiers (MGUs), clause subsumption, tau- dn Fm Vn Wm 1. i=1 Ai v j=1 Cj i=1 Ai (x) → j=1 Cj (x) 2. ∃R.A v B R(x, y) ∧ A(y) → B(x) 3. A v Self(R) A(x) → R(x, x) 4. Self(R) v A R(x, x) → A(x) 5. RvS R(x, y) → S(x, y) 6. R v S− R(x, y) → S(y, x) 7. R◦S vT R(x, z) ∧ S(z, y) → T (x, y) 8. A v ≥ m R.B A(x) →V∃≥m y.(R(x, y) ∧ B(y)) W 9. A v ≤ m R.B A(z) ∧ m i=0 R(z, xi ) ∧ B(xi ) → 0≤i, C atomic or ⊥, and R, S, T atomic. tologies, binary resolution, and factoring are as usual [2]. Clause C θ-subsumes D if C subsumes D and C has no more literals than D. Clause C is redundant in a set of clauses if C is tautological or if C is θ-subsumed by another clause in the set. A condensation of a clause C is a minimal subset that is subsumed by C. A rule r is a function-free sentence ∀x∀z.[ϕ(x, z) → ψ(x)] where tuples of variables x and z are disjoint, ϕ(x, z) is a conjunction of distinct equality-free atoms, and ψ(x) is a disjunction of distinct atoms. Formula ϕ is the body of r, and ψ is the head. Quantifiers in rules are omitted. We assume that rules are safe. A rule is datalog if ψ(x) has at most one atom, and it is disjunctive otherwise. A program P is a finite set of rules; it is datalog if it consists only of datalog rules, and disjunctive otherwise. We assume that rules in P do not share variables. For convenience, we treat > and ⊥ in a non-standard way as a unary and a nullary predicate, respectively. Given a program P, P> is the program with a rule Q(x1 , . . . , xn ) → >(xi ) for each predicate Q in P and each 1 ≤ i ≤ n, and a rule → >(a) for each constant a in P. We assume that P> ⊆ P and > does not occur in head position in P \ P> . We define P⊥ as consisting of a rule with ⊥ as body and empty head. We assume P⊥ ⊆ P and no rule in P \ P⊥ has an empty head or ⊥ in the body. Thus, P ∪ D |= >(a) for every a in P ∪ D, and P ∪ D is unsatisfiable iff P ∪ D |= ⊥. Head predicates in P \ P> are intensional (or IDB ) in P. All other predicates (including >) are extensional (EDB ). An atom is intensional (extensional) if so is its predicate. A rule is linear if it has at most one IDB body atom. A program P is linear if all its rules are. We assume familiarity with DLs. W.l.o.g. we consider normalised axioms as in Table 1. An ontology O is SHIQ if each axiom of type 7 satisfies R = S = T ;1 it is SHI if it is SHIQ, it does not contain axioms of type 9, and each axiom of type 8 satisfies m = 1; it is ALCHI if it is SHI and it has no axiom of type 7; it is RLt if it does not contain axioms of type 8, and it is RL if it is RLt and m = 1 for each axiom of type 1 and 9. Programs obtained from RLt ontologies have rules with bounded number of variables: fact entailment is PTime-complete for RL and co-NP-complete for RLt (in combined complexity).2 1 SHIQ enforces additional restrictions to ensure decidability, which we omit here. 2 RLt and RL allow for nominals, which we omit. All our results immediately extend. P0 = {C(x) → B(x) ∨ G(x) (1) (1) B (2) G(y) ∧ E(x, y) → B(x) (2) C (2) (3) E (4) B(y) ∧ E(x, y) → G(x) (3) (1) (3) G E(y, x) → E(x, y) } (4) Fig. 1. A weakly linear disjunctive datalog program An (atomic) query is a function-free atom. A (disjunctive) program P is a rewriting of F w.r.t. a set of predicates S if for each dataset D over the signature of F and every fact α over S we have F ∪ D |= α iff P ∪ D |= α. Program P is a rewriting of F if it is a rewriting w.r.t. the set of all predicates in F, in which case it preserves answers to all atomic queries. Hudstadt et al. [8] developed an algorithm for transforming a SHIQ ontology into a disjunctive program that preserves entailment of facts over non-transitive relations. This technique was extended in [5] to preserve all facts. Thus, every SHIQ ontology O admits a disjunctive datalog rewriting DD(O), which can be of exponential size. 3 Datalog Rewritings Based on Linearity In [10] we proposed the class of weakly linear programs (WL), which extends both datalog and linear disjunctive datalog. In a WL program predicates are parti- tioned into disjunctive (i.e., those whose extension may depend on a disjunctive rule) and datalog (those that depend solely on datalog rules). A program is WL if all rules have at most one occurrence of a disjunctive predicate in the body. Definition 3.1. The dependency graph GP = (V, E, µ) of a program P is the smallest edge-labeled digraph such that: 1. V contains every predicate occurring in P; 2. r ∈ µ(P, Q) whenever P, Q ∈ V , r ∈ P \ P> , P occurs in the body of r, and Q occurs in the head of r; and 3. (P, Q) ∈ E whenever µ(P, Q) is nonempty. A predicate Q depends on a rule r ∈ P if GP has a path that ends in Q and involves an r-labeled edge. Predicate Q is datalog if it only depends on datalog rules; otherwise, Q is disjunctive. Program P is weakly linear (WL for short) if each rule body in P has at most one occurrence of a disjunctive predicate. Consider the disjunctive program P0 and its dependency graph depicted in Figure 1. Predicate C is EDB, predicates B and G depend on Rule (1) and hence are disjunctive, whereas E depends only on Rule (4) and hence it is datalog. Each rule has at most one disjunctive body atom and the program is WL. WL programs admit a polynomial rewriting [10]. Roughly speaking, they are translated into datalog by “moving” all disjunctive body atoms to the head and all disjunctive head atoms to the body while replacing their predicates with fresh ones of higher arity; the new predicates are “initialised” using additional rules. Markable Programs We next propose the class of markable disjunctive data- log programs, which extends WL programs. A key feature of a markable program is that one can identify a subset of disjunctive predicates, called marked predi- cates, such that the program can be translated into datalog by “moving” only those disjunctive atoms in a rule whose predicates are marked. Definition 3.2. Let P be a disjunctive program. A marking of P is a set M of disjunctive predicates in P such that: 1. Every rule in P has at most one body atom Q(t) with Q ∈ M . 2. Every rule in P has at most one head atom Q(t) with Q ∈ / M. 3. If Q ∈ M and P is reachable from Q in GP , then P ∈ M . A predicate Q is marked by M if Q ∈ M . An atom is marked if so is its predicate. A disjunctive program is markable if it has a marking. Markability generalises weak linearity in the following sense. Proposition 3.3. A disjunctive program P is WL if and only if the set of all disjunctive predicates in P constitutes a marking of P. Let P1 extend P0 with the following rules: V (x) → C(x) ∨ U (x) (5) C(x) ∧ U (x) → ⊥ (6) The dependency graph is given next. Note that C, U , B, and G are disjunctive as they depend on Rule (5). Thus, (6) has two disjunctive body atoms and P1 is not WL. The program, however, has markings {C, B, G} and {U, B, G}. (5) V (5) (1) B (2) U C (2) (3) E (4) (6) ⊥ (6) (1) G (3) The following proposition establishes that checking markability is tractable and amenable to efficient implementation via reduction to 2-SAT. Proposition 3.4. Markability can be checked in polynomial time. Datalog Rewritability of Markable Programs We now show that markable programs are rewritable into datalog by means of a quadratic translation ΞM , which extends the translation for weakly linear programs given in [10]. Consider P1 and the marking M = {B, G, U }. We introduce fresh binary Y Y Y predicates B , G , and U for every disjunctive predicate Y . Intuitively, if G a fact B (c, d) holds in ΞM (P1 ) ∪ D then proving B(c) suffices for proving G(d) in P1 ∪ D (or, in other words, we have P1 ∪ D |= B(c) → G(d)). Anal- ogously, for the unmarked disjunctive predicate C we introduce fresh binary predicates C Y for each disjunctive predicate Y ; these predicates have a different intuitive interpretation: if a fact C U (c, d) holds in ΞM (P1 ) ∪ D then P1 ∪ D implies C(c) ∨ U (d). To “initialise” the extension of the fresh predicates we need the following rules for every X ∈ M and every disjunctive predicate Y . X >(x) → X (x, x) (7) >(y) ∧ C(x) → C Y (x, y) (9) Y C X (x, y) ∧ X(x) → Y (y) (8) C (x, x) → C(x) (10) These rules encode the intended meaning of the auxiliary predicates. For example, Rule (8) states that if X(c) holds for some constant c and this is sufficient to prove Y (d) for some d, then Y (d) holds. The key step is to “flip” the direction of all rules in P1 involving the marked predicates B, G and U by moving all marked atoms from the head to the body and vice versa while at the same time replacing their predicates with the relevant auxiliary predicates. Thus, Rule (2) leads to the following rules in ΞM (P1 ) for each disjunctive predicate Y : Y Y B (x, z) ∧ E(x, y) → G (y, z) These rules are natural consequences of Rule (2) under the intended meaning of the auxiliary predicates: if we can prove a goal Y (z) by proving first B(x), and E(x, y) holds, then by Rule (2) we deduce that proving G(y) suffices to prove Y (z). In contrast to (2), Rule (1) contains no disjunctive body atoms. We “flip” this rule as follows, for each disjunctive predicate Y : Y Y C(x) ∧ B (x, y) ∧ G (x, y) → Y (y) Similarly to the previous case, this rule follows from Rule (1): if C(x) holds and we can establish that Y (y) can be proved from B(x) and also from G(x), then Y (y) must hold. In contrast to marked atoms, unmarked atoms are not moved. So, Rules (5) and (6) yield the following rules for each disjunctive predicate Y : Y Y V (x) ∧ U (x, y) → C Y (x, y) C Y (x, y) → U (x, y) And indeed, these rules are consequences of Rule (5) and (6), respectively, under the intended meaning of the auxiliary predicates: V (x) and U (x) → Y (y) imply C(x) ∨ Y (y) by Rule (5), while C(x) ∨ Y (y) and U (x) imply Y (y) by Rule (6). Definition 3.5. Let P be a disjunctive program, Σ the set of disjunctive pred- icates in P \ P> , and M ⊆ Σ a marking of P. For each (P, Q) ∈ Σ 2 , let P Q Q and P be fresh predicates of arity arity(P ) + arity(Q). Then, ΞM (P) is the dat- alog program with the rules given next, where ϕ is the conjunction of all datalog atoms in a rule, ϕ> is the least conjunction of >-atoms that makes a rule safe, all predicates Pi , Qj are in Σ, and y, z are disjoint vectors of fresh variables: 1. every rule in P that contains no disjunctive predicates; Vm Vn R R 2. a rule ϕ> ∧ ϕ ∧ j=1 QR j (tj , y) ∧ i=1 P i (si , y) → Q (t, y) for every rule Vm Wn r = ϕ ∧ Q(t) ∧ j=1 Qj (tj ) → i=1 Pi (si ) ∈ P \ P> and every R ∈ Σ, where Q(t) is the unique marked body atom of r (and hence all Pi (si ) are marked); Vm Vn R 3. a rule ϕ> ∧ ϕ ∧ j=1 QR (t , y) ∧ i=1 P i (si , y) → R(y) for every rule Vm Wjn j r = ϕ ∧ j=1 Qj (tj ) → i=1 Pi (si ) ∈ P \ P> and each R ∈ Σ, where r has no marked body atoms and no unmarked head atoms; Vm Vn R 4. a rule ϕ> ∧ ϕ ∧ j=1 QR j (tj , y) ∧ i=1 P i (si , y) → P R (s, y) for every rule Vm Wn r = ϕ ∧ j=1 Qj (tj ) → P (s) ∨ i=1 Pi (si ) ∈ P \ P> and each R ∈ Σ, where r has no marked body atoms, and P (s) is the unique unmarked head atom; R 5. a rule ϕ> → R (y, y) for every R ∈ M ; R 6. a rule Q(z) ∧ Q (z, y) → R(y) for every pair (Q, R) ∈ M × Σ; 7. a rule ϕ> ∧ Q(z) → QR (z, y) for every pair (Q, R) ∈ (Σ \ M ) × Σ; 8. a rule RR (y, y) → R(y) for every R ∈ Σ \ M . The transformation is quadratic and the arity of predicates is at most doubled. For P1 and the marking M , we obtain the datalog program ΞM (P1 ) consisting of the following rules, where X ∈ M and Y is disjunctive: Y V (x) ∧ U (x, y) → C Y (x, y) (5’) E(y, x) → E(x, y) (4) Y Y X C (x, y) → U (x, y) (6’) >(x) → X (x, x) (7) Y Y Y C(x) ∧ B (x, y) ∧ G (x, y) → Y (y) (1’) X(x) ∧ X (x, y) → Y (y) (8) Y Y Y B (x, z) ∧ E(x, y) → G (y, z) (2’) >(y) ∧ C(x) → C (x, y) (9) Y Y C G (x, z) ∧ E(x, y) → B (y, z) (3’) C (x, x) → C(x) (10) Correctness of ΞM is established by the following theorem. Theorem 3.6. Let P be a disjunctive program and let M be a marking of P. Then ΞM (P) is a polynomial datalog rewriting of P. Being a rewriting of P, ΞM (P) preserves the extension of all predicates in P. If we only want to query a specific predicate Q, we can compute a smaller program, which is linear in the size of P and preserves the extension of Q. If Q is datalog, each proof in P of a fact about Q involves only datalog rules, and Q if Q is disjunctive each such proof involves only fresh predicates X Q and X . Thus, in ΞM we can dispense with all rules involving auxiliary predicates X R R or X for R 6= Q (if Q is datalog the rewriting has no auxiliary predicates). Theorem 3.7. Let P be a disjunctive program, M a marking of P, S a set of predicates in P, and P 0 obtained from ΞM (P) by removing all rules with a R predicate X R or X for R ∈ / S. Then P 0 is a rewriting of P w.r.t. S. Rewriting Ontologies Our results are directly applicable to RLt . In [10], we showed tractability of fact entailment for the class of RLt ontologies correspond- ing to WL programs. We now extend this result to markable programs. Theorem 3.8. Checking O ∪ D |= α, for O an RLt ontology that corresponds to a markable program, is PTime-complete w.r.t. data and combined complexity. We next lift the markability condition from disjunctive programs to ontolo- gies. Observe that the notions of dependency graph and markability naturally extend to sets of first-order clauses (written as rules where function symbols are allowed). We define a predicate to be disjunctive in O if it is disjunctive in the set FO of clauses obtained by skolemisation; we call O markable if so is FO ; and we call a set of predicates a marking of O if it is a marking of FO . Example 3.9. Consider the ontology O1 and its corresponding clauses FO1 : O1 ={Person v Man t Woman, Person v ∃child.Person, ∃married.Person v Person, Woman v Person, Man v Person} FO1 ={Person(x) → Man(x) ∨ Woman(x), Person(x) → child(x, f (x)), Person(x) → Person(f (x)), Person(y) ∧ married(x, y) → Person(x), Woman(x) → Person(x), Man(x) → Person(x)} Ontology O1 is markable since the set {Person, Man, Woman} is a marking of FO1 . As already mentioned, every normalised SHI ontology can be rewritten into disjunctive datalog by means of a resolution-based calculus [8, 5]. The following lemma establishes that binary resolution and factoring preserve markability. Lemma 3.10. Let M be a marking of a set of clauses F, and let F 0 be obtained from F using binary resolution and factoring. Then M is a marking of F 0 . Thus, markable SHI ontologies admit a (possibly exponential) rewriting. Theorem 3.11. Let O be a SHI ontology and let M be a marking of O. Let DD(O) be the disjunctive datalog rewriting of O as in [8, 5]. Then M is a marking of DD(O) and ΞM (DD(O)) is a datalog rewriting of O. Corollary 3.12. Checking O ∪ D |= α, for O a markable SHI ontology is PTime-complete w.r.t. data and in ExpTime w.r.t. combined complexity. 4 Resolution-Based Rewritings Resolution provides an alternative technique for rewriting disjunctive programs into datalog [5]. Procedure 1 saturates the input program P under binary res- olution and positive factoring, with the restriction that two Horn clauses are never resolved together. The procedure is compatible with redundancy elimina- tion techniques such as tautology elimination, subsumption and condensation. If it terminates, the procedure returns the subset of Horn clauses (equivalently, datalog rules) in the saturation, which is guaranteed to be a rewriting of P. We show that the separation between disjunctive and datalog predicates (Def- inition 3.1) can be exploited to refine this procedure. The idea is to further refine resolution by ensuring that the resolved atoms involve a disjunctive predicate. Definition 4.1. Compile-Horn-Restricted is obtained from Procedure 1 by adding to the definition of R in step 5 the additional restriction that the predicate in the atoms being resolved must be disjunctive in S. Procedure 1 Compile-Horn Input: S: set of clauses Output: SH : set of Horn clauses 1: SH := {C ∈ S | C is a Horn clause and not a tautology} 2: SH := {C ∈ S | C is a non-Horn clause and not a tautology} 3: repeat 4: F := factors of each C1 ∈ SH non-redundant in SH ∪ SH 5: R := resolvents of each C1 ∈ SH and C2 ∈ SH ∪ SH not redundant in SH ∪ SH 6: for each C ∈ F ∪ R do 7: C 0 := the condensation of C 8: Delete from SH and SH all clauses θ-subsumed by C 0 9: if C 0 is Horn then SH := SH ∪ {C 0 } 10: else SH := SH ∪ {C 0 } 11: until F ∪ R = ∅ 12: return SH Correctness of Compile-Horn-Restricted relies on the observation that resolutions on datalog predicates can always be delegated to the datalog reasoner and hence do not have to be performed as part of the rewriting process. Theorem 4.2. If Compile-Horn-Restricted terminates on a disjunctive program P with a program P 0 , then P 0 is a datalog rewriting of P. The class of disjunctive programs over which Compile-Horn-Restricted termi- nates is incomparable with the class of markable programs. Furthermore, the rewritings produced by both approaches are also quite different. Markable pro- grams lead to polynomial rewritings, in which the arity of predicates is increased; rewritings computed via resolution can be much larger, but since all the datalog rules in the rewriting are logically entailed by the original program, the arity of predicates stays the same. In Section 5 we will discuss practical implications. Rewriting Ontologies The procedure Compile-Horn was shown to terminate for a class of programs called simple [5]; furthermore, DL-LiteH,+ bool ontologies are transformed into disjunctive programs that satisfy the simplicity condition using the algorithm by Hustadt, Motik and Sattler [8]. We now extend this result by devising a sufficient condition for datalog rewritability of SHI ontologies via Compile-Horn-Restricted. Since transitivity axioms can be eliminated from SHI ontologies by a polynomial transformation while preserving fact entailment (see [8, 5]), it suffices to formulate our condition for ALCHI.3 First, we adapt the notion of simple rules in [5] as follows. Definition 4.3. An axiom of the form ∃R.A v B is simple w.r.t. a set of predicates S (or S-simple) if A ∈ / S. An ontology O is S-simple if so is every axiom of the form ∃R.A v B in O. 3 Note that neither Compile-Horn nor Compile-Horn-Restricted are well-suited for deal- ing with (axiomatised) equality. Both will diverge on every disjunctive program with equality due to the congruence axioms P (x) ∧ x ≈ y → P (y) with P disjunctive. Note that ontology O1 from Example 3.9 is not simple w.r.t. its disjunctive predicates due to axiom ∃married.Person v Person. If, however, we replace this axiom with Man u Woman → ⊥, we obtain a simple ontology, which in turn is no longer markable. The following theorem then generalises the result in [5] to a sufficient condition for datalog rewritability of ALCHI ontologies. Theorem 4.4. Let O be an ALCHI ontology that is simple w.r.t. its disjunctive predicates, and let DD(O) be the disjunctive datalog rewriting of O as in [5]. Compile-Horn-Restricted terminates on DD(O) with a datalog rewriting of O. 5 Evaluation We have evaluated whether realistic ontologies can be rewritten into datalog us- ing our approaches. We analysed 118 ontologies that use disjunctive constructs from BioPortal, the Protégé library, and the corpus in [7]. To transform ontolo- gies into disjunctive datalog we used KAON2 [14], which succeeded to compute disjunctive programs for 103 ontologies.4 Out of the 103 disjunctive programs, 32 were WL, and 35 were markable. Furthermore, 26 programs could be rewrit- ten using Compile-Horn, and 27 could be rewritten using Compile-Horn-Restricted (within 1min). Furthermore, programs produced by Compile-Horn were on av- erage 18% larger (w.r.t. the number of rules) than those produced by Compile- Horn-Restricted. Many of the programs obtained by KAON2 contained equality, and hence could not be rewritten by means of resolution (see Section 4). Hence, we additionally considered simplified versions of the 103 programs where we re- moved all rules containing equality. Out of these, 33 turned out to be WL, and 36 were markable; as expected the effect of equality on linearity-based approaches is rather minor. In contrast, resolution-based approaches were significantly more effective than before: Compile-Horn succeeded in 39 cases, and Compile-Horn- Restricted in 41 cases. The intersection between the programs rewritable using markability and resolution turned out to be quite large: in the general case, there were 16 programs that could be rewritten by only one approach, and in the equality-free case only 5. Still, taken together, the two approaches succeeded to rewrite 39 programs (38%) in the general case and 41 programs (40%) in the equality-free case. Moreover, on average, 73% of the predicates were datalog, and so could be queried using a datalog engine even if the disjunctive program was not rewritable. Finally, we found that 20 out of the 103 ontologies were RLt , out of which 17 were markable. Of the remaining three, two could be rewritten via resolution. We have also tested scalability of query answering using datalog programs obtained by our approach. For this, we used UOBM [13] and DBpedia, which come with large datasets. We considered the RLt subset of UOBM, which is equivalent to a markable program but is not datalog rewritable using Compile- Horn-Restricted, and generated datasets for 1 to 10 universities. DBpedia is a realistic ontology with a large dataset from Wikipedia. Since DBpedia is Horn, we extended it with reasonable disjunctive axioms. We used RDFox as a datalog 4 We doctored the ontologies to remove constructs outside SHIQ. Our approach HermiT Pellet dlog disj err dlog disj err dlog disj err U01 <1s 8s 6s 107s 146s 172s U04 <1s 55s 50s 50s 2 — — — U07 <1s 62s 3 107s 122s 2 — — — U10 <1s 66s 5 176s 182s 2 — — — Table 2. Average query answering times engine. Performance was measured against HermiT [16] and Pellet [18]. We used a server with two Intel Xeon E5-2643 processors and 128GB RAM. Timeouts were 10min for one query and 30min for all queries; a limit of 100GB was allo- cated to each task. We ran RDFox on 16 threads. Systems were compared on individual queries (one for each predicate in the ontology) and on precomput- ing answers to all queries. All systems succeeded to answer all queries for U01: HermiT required 890s, Pellet 505s, and we 52s. Table 2 depicts average times for datalog and disjunctive predicates, and number of queries on which a system failed.5 Pellet only succeeded to answer queries on U01. HermiT’s performance was similar for datalog and disjunctive predicates. In our case, queries over the 130 datalog predicates in UOBM (88% of the 148 predicates in UOBM) were answered instantaneously (<1s); queries over disjunctive predicates were signif- icantly harder. Finally, due to its size, DBpedia’s dataset cannot even be loaded by HermiT or Pellet. Still, we could compare the rewritings obtained by mark- ing and Compile-Horn-Restricted. Since Compile-Horn-Restricted cannot compute rewritings on per query basis, we compared the rewritings for the full ontolo- gies only. Using RDFox, the rewritings produced by the marking approach and Compile-Horn-Restricted precomputed the answers for all predicates in 48 and 1.5 seconds, respectively. In this case, the rewriting obtained by Compile-Horn- Restricted performs better as it introduces fewer rules. The marking approach introduces predicates of higher arity, which leads to a larger materialisation. 6 Conclusion We have proposed enhanced techniques for rewriting disjunctive datalog pro- grams and DL ontologies into plain datalog programs. Our techniques enable the use of scalable datalog engines for data reasoning. In this paper, we have focused on rewritings that preserve fact entailment and hence answers to atomic queries; we are working on rewriting techniques for full conjunctive queries. Acknowledgements This work was supported by the Royal Society, the EPSRC projects Score!, Exoda, and MaSI3 , and the FP7 project OPTIQUE. 5 Average times do not reflect queries on which a system failed. References 1. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. Artif. Intell. Res. 36, 1–69 (2009) 2. Bachmair, L., Ganzinger, H.: Resolution theorem proving. In: Handbook of Auto- mated Reasoning, pp. 19–99. Elsevier and MIT Press (2001) 3. Bienvenu, M., ten Cate, B., Lutz, C., Wolter, F.: Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP. In: PODS. pp. 213–224 (2013), arXiv:1301.6479 4. Bishop, B., Kiryakov, A., Ognyanoff, D., Peikov, I., Tashev, Z., Velkov, R.: OWLIM: A family of scalable semantic repositories. Semantic Web 2(1), 33–42 (2011) 5. Cuenca Grau, B., Motik, B., Stoilos, G., Horrocks, I.: Computing datalog rewritings beyond Horn ontologies. In: IJCAI. pp. 832–838 (2013), arXiv:1304.1402 6. Eiter, T., Ortiz, M., Šimkus, M., Tran, T.K., Xiao, G.: Query rewriting for Horn- SHIQ plus rules. In: AAAI. pp. 726–733 (2012) 7. Gardiner, T., Tsarkov, D., Horrocks, I.: Framework for an automated comparison of description logic reasoners. In: ISWC. pp. 654–667 (2006) 8. Hustadt, U., Motik, B., Sattler, U.: Reasoning in description logics by a reduction to disjunctive datalog. J. Autom. Reasoning 39(3), 351–384 (2007) 9. Kaminski, M., Cuenca Grau, B.: Sufficient conditions for first-order and datalog rewritability in ELU. In: DL. pp. 271–293 (2013) 10. Kaminski, M., Nenov, Y., Cuenca Grau, B.: Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning. In: AAAI (2014), arXiv:1404.3141 11. Kaminski, M., Nenov, Y., Cuenca Grau, B.: Datalog rewriting techniques for non- Horn ontologies. Tech. rep., Department of Computer Science, University of Oxford (2014), https://krr-nas.cs.ox.ac.uk/2014/DL/rewritings/paper.pdf 12. Krisnadhi, A., Lutz, C.: Data complexity in the EL family of description logics. In: LPAR. pp. 333–347 (2007) 13. Ma, L., Yang, Y., Qiu, Z., Xie, G.T., Pan, Y., Liu, S.: Towards a complete OWL ontology benchmark. In: ESWC. pp. 125–139 (2006) 14. Motik, B.: Reasoning in Description Logics using Resolution and Deductive Databases. Ph.D. thesis, Univesität Karlsruhe (TH), Karlsruhe, Germany (2006) 15. Motik, B., Nenov, Y., Piro, R., Horrocks, I., Olteanu, D.: Parallel materialisation of datalog programs in centralised, main-memory RDF systems. In: AAAI (2014) 16. Motik, B., Shearer, R., Horrocks, I.: Hypertableau reasoning for description logics. J. Artif. Intell. Res. 36, 165–228 (2009) 17. Pérez-Urbina, H., Motik, B., Horrocks, I.: Tractable query answering and rewriting under description logic constraints. J. Appl. Log. 8(2), 186–209 (2010) 18. Sirin, E., Parsia, B., Cuenca Grau, B., Kalyanpur, A., Katz, Y.: Pellet: A practical OWL-DL reasoner. J. Web Sem. 5(2), 51–53 (2007) 19. Trivela, D., Stoilos, G., Chortaras, A., Stamou, G.B.: Optimising resolution-based rewriting algorithms for DL ontologies. In: DL. pp. 464–476 (2013) 20. Wu, Z., Eadon, G., Das, S., Chong, E.I., Kolovski, V., Annamalai, M., Srinivasan, J.: Implementing an inference engine for RDFS/OWL constructs and user-defined rules in Oracle. In: ICDE. pp. 1239–1248 (2008)