Datalog Rewriting Techniques for Non-Horn Ontologies

Abstract

We study the closely related problems of rewriting disjunctive datalog programs and non-Horn DL ontologies into plain datalog programs that entail the same facts for every dataset. We rst propose the class of markable disjunctive datalog programs, which is e ciently recognisable and admits polynomial rewritings into datalog. Markability 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 resolution. Finally, we evaluate the feasibility of our techniques over a large corpus of ontologies, with encouraging results.

Introduction

Query answering over DL ontologies is a key reasoning problem for many applications. 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 datalog 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 E LU [ 12, 5 ], and su cient conditions that ensure rewritability were identi ed 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 program 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 di erent approach to rewriting disjunctive programs into datalog by means of a resolution-based procedure was proposed in [ 5 ]. The procedure works by saturating 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 e ciently recognisable and that each markable program admits a polynomial datalog rewriting. These results can be readily applied to ontology reasoning. We rst 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 complexity (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 (possibly exponential) datalog rewriting. In Section 4, we re ne the resolution-based rewriting procedure from [ 5 ] by further requiring that only atoms involving disjunctive predicates can participate in resolution inferences. This re nement can signi cantly reduce the number of inferences drawn during saturation, without a ecting correctness. We then turn our attention to ontologies, and propose an extension of the logics in the DL-Litebool family that admits (possibly exponential) datalog rewritings. Our empirical results show that many realistic non-Horn ontologies can be rewritten into datalog. Furthermore, we have tested the scalability 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 nite set of facts. We assume that equality is an ordinary predicate and that each set of formulae contains the axiomatisation of as a congruence relation for its signature. Clauses, substitutions, most general uni ers (MGUs), clause subsumption, tau1: dn

i=1 Ai v Fjm=1 Cj 2: 9R:A v B 3: A v Self(R) 4: Self(R) v A 5: R v S 6: R v S 7: R S v T 8: A v 9: A v m R:B m R:B

Vin=1 Ai(x) ! Wjm=1 Cj(x) R(x; y) ^ A(y) ! B(x) A(x) ! R(x; x) R(x; x) ! A(x) R(x; y) ! S(x; y) R(x; y) ! S(y; x) R(x; z) ^ S(z; y) ! T (x; y) A(x) ! 9 my:(R(x; y) ^ B(y)) A(z) ^ Vim=0 R(z; xi) ^ B(xi) ! W0 i<j m xi xj 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 8x8z:['(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. Quanti ers 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 nite 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 n P>. We de ne P? as consisting of a rule with ? as body and empty head. We assume P? P and no rule in P n P? has an empty head or ? in the body. Thus, P [ D j= >(a) for every a in P [ D, and P [ D is unsatis able i P [ D j= ?. Head predicates in P n 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 satis es 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 satis es 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 = fC(x) ! B(x) _ G(x)

G(y) ^ E(x; y) ! B(x) B(y) ^ E(x; y) ! G(x) E(y; x) ! E(x; y) g (2) (3) (4)

C (1) G (3) (2) (3)

E (4)

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 j= i P [ D j= . 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 partitioned 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. De nition 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 2 (P; Q) whenever P; Q 2 V , r 2 P n P>, P occurs in the body of r, and

Q occurs in the head of r; and 3. (P; Q) 2 E whenever (P; Q) is nonempty.

A predicate Q depends on a rule r 2 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 datalog programs, which extends WL programs. A key feature of a markable program is that one can identify a subset of disjunctive predicates, called marked predicates, such that the program can be translated into datalog by \moving" only those disjunctive atoms in a rule whose predicates are marked.

De nition 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 2 M . 2. Every rule in P has at most one head atom Q(t) with Q 2= M . 3. If Q 2 M and P is reachable from Q in GP , then P 2 M .

A predicate Q is marked by M if Q 2 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 fC; B; Gg and fU; B; Gg.

U (5) (6)

V ? (5) (6)

C (1) (1)

B G (2) (3) (2) (3)

E (4)

The following proposition establishes that checking markability is tractable and amenable to e cient 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 = fB; G; U g. We introduce fresh binary predicates BY , GY , and U Y for every disjunctive predicate Y . Intuitively, if a fact BG(c; d) holds in M (P1) [ D then proving B(c) su ces for proving G(d) in P1 [ D (or, in other words, we have P1 [ D j= B(c) ! G(d)). Analogously, for the unmarked disjunctive predicate C we introduce fresh binary predicates CY for each disjunctive predicate Y ; these predicates have a di erent intuitive interpretation: if a fact CU (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 2 M and every disjunctive predicate Y .

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 su cient to prove Y (d) for some d, then Y (d) holds. The key step is to \ ip" 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 : 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 rst B(x), and E(x; y) holds, then by Rule (2) we deduce that proving G(y) su ces to prove Y (z). In contrast to (2), Rule (1) contains no disjunctive body atoms. We \ ip" this rule as follows, for each disjunctive predicate 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 : 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). De nition 3.5. Let P be a disjunctive program, the set of disjunctive predicates in P n P>, and M a marking of P. For each (P; Q) 2 2, let P Q

Q and P be fresh predicates of arity arity(P ) + arity(Q). Then, M (P) is the datalog 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;

2. a rule '> ^ ' ^ Vjm=1 QjR(tj ; y) ^ Vin=1 P iR(si; y) ! QR(t; y) for every rule r = ' ^ Q(t) ^ Vjm=1 Qj (tj ) ! Win=1 Pi(si) 2 P n P> and every R 2 , where Q(t) is the unique marked body atom of r (and hence all Pi(si) are marked); 3. a rule '> ^ ' ^ Vjm=1 QjR(tj ; y) ^ Vin=1 P iR(si; y) ! R(y) for every rule r = ' ^ Vjm=1 Qj (tj ) ! Win=1 Pi(si) 2 P n P> and each R 2 , where r has no marked body atoms and no unmarked head atoms;

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 2 M and Y is disjunctive:

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 speci c 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 if Q is disjunctive each such proof involves only fresh predicates XQ and XQ. Thus, in M we can dispense with all rules involving auxiliary predicates XR or XR 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 P0 obtained from M (P) by removing all rules with a predicate XR or XR for R 2= S. Then P0 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 corresponding to WL programs. We now extend this result to markable programs. Theorem 3.8. Checking O [ D j= , 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 ontologies. Observe that the notions of dependency graph and markability naturally extend to sets of rst-order clauses (written as rules where function symbols are allowed). We de ne 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 =fPerson v Man t Woman; Person v 9child:Person;

9married:Person v Person; Woman v Person; Man v Persong

FO1 =fPerson(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)g

Ontology O1 is markable since the set fPerson; Man; Womang 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 j= , 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 resolution and positive factoring, with the restriction that two Horn clauses are never resolved together. The procedure is compatible with redundancy elimination 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 (Definition 3.1) can be exploited to re ne this procedure. The idea is to further re ne resolution by ensuring that the resolved atoms involve a disjunctive predicate. De nition 4.1. Compile-Horn-Restricted is obtained from Procedure 1 by adding to the de nition of R in step 5 the additional restriction that the predicate in the atoms being resolved must be disjunctive in S. 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 P0, then P0 is a datalog rewriting of P.

The class of disjunctive programs over which Compile-Horn-Restricted terminates is incomparable with the class of markable programs. Furthermore, the rewritings produced by both approaches are also quite di erent. Markable programs 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-LitebHo;o+l 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 su cient 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 su ces to formulate our condition for ALCHI.3 First, we adapt the notion of simple rules in [ 5 ] as follows.

De nition 4.3. An axiom of the form 9R:A v B is simple w.r.t. a set of predicates S (or S-simple) if A 2= S. An ontology O is S-simple if so is every axiom of the form 9R:A v B in O. 3 Note that neither Compile-Horn nor Compile-Horn-Restricted are well-suited for dealing 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 9married: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 su cient 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 using our approaches. We analysed 118 ontologies that use disjunctive constructs from BioPortal, the Protege library, and the corpus in [ 7 ]. To transform ontologies 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 rewritten using Compile-Horn, and 27 could be rewritten using Compile-Horn-Restricted (within 1min). Furthermore, programs produced by Compile-Horn were on average 18% larger (w.r.t. the number of rules) than those produced by CompileHorn-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 simpli ed versions of the 103 programs where we removed all rules containing equality. Out of these, 33 turned out to be WL, and 36 were markable; as expected the e ect of equality on linearity-based approaches is rather minor. In contrast, resolution-based approaches were signi cantly more e ective than before: Compile-Horn succeeded in 39 cases, and Compile-HornRestricted 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 CompileHorn-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. 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 allocated to each task. We ran RDFox on 16 threads. Systems were compared on individual queries (one for each predicate in the ontology) and on precomputing 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 significantly 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 marking and Compile-Horn-Restricted. Since Compile-Horn-Restricted cannot compute rewritings on per query basis, we compared the rewritings for the full ontologies 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-HornRestricted 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 programs 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 re ect 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 Automated 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. , Ognyano , 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. , Simkus , M. , Tran , T.K. , Xiao , G.: Query rewriting for HornSHIQ 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. : Su cient conditions for rst-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 nonHorn 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 , Univesitat 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. Perez-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-de ned rules in Oracle . In: ICDE. pp. 1239 { 1248 ( 2008 )