From Horn-S RI Q to Datalog: A Data-Independent Transformation that Preserves Assertion Entailment?

Abstract

Assertion retrieval (AR)|i.e., the task of inferring all implicit assertions from a Description Logics (DL) knowledge base (KB)|is an important reasoning task with many applications in knowledge representation and data management. To access data e ciently, one approach is to rewrite the ontology into Datalog, and then use powerful Datalog engines to compute implicit entailments. Existing rewriting techniques support DL languages from E LH to Horn-SHIQ [3]. We present the rst such transformation for Horn-SRIQu, an expressive DL that allows for the use of the role chain constructor. Furthermore, we show that the resulting method for assertion retrieval is worst-case optimal for E LH, Horn-SHIQ, and Horn-SRIQu. We empirically show that the use of Datalog rewritings can outperform state-of-the-art reasoners and that we can construct rewritings of moderate sizes for many real-world ontologies. To give a formal intuition about our approach, our method computes an AR-rewriting in the following sense. De nition 1. Let O = hT ; Ai be a Horn-SRIQu KB. A Datalog rule set RT is an AR-rewriting for T i , for every ABox A and assertion de ned over the signature of T , hT ; Ai and hRT ; Ai are equi-satis able and hT ; Ai j= i KO = hRT ; Ai j= .

-

David Carral, Larry Gonzalez, and Patrick Koopmann 103 Reactome 102 101 103 102 101

Uniprot 105 103 101 1002.8M 5.1M 6.7M 8.1M

100 9M 17.8M 26.2M 33.9M axioms relevant to our Datalog program. Since this calculus was originally designed for Horn-SHIQ, we rst need to extend our input TBox T to a TBox T+ in which the behaviour of complex role inclusion axioms is su ciently simulated.

To show practical feasibility of our approach, we implemented a prototype and performed two di erent experiments. We rst compared the performance of solving AR using our Datalog rewritings versus using the DL reasoner Konclude [ 8 ]. We considered two real-world, data-intensive ontologies from the biological domain, Reactome and Uniprot [ 9 ] which we normalised and enriched with 3 and 5 complex role inclusion axioms, respectively. The resulting TBoxes contain 485 and 304 axioms. The rewritten Datalog programs contain 539 and 367 rules, and were computed in 221 and 182 seconds. For each ontology, we considered ABoxes of various sizes, generated by sampling the real-world ABoxes using the method by Zhou et al. [ 9 ]. We use RDFox [ 6 ] as Datalog engine for computing the chase of our rewritings, and compare its performance with that of Konclude. Figure 1 shows the wall-clock times measured in this experiment, ignoring the time used for parsing and loading, in logarithmic scale.

In our second experiment, we computed rewritings for 121 selected TBoxes from MOWLCorp [ 7 ]. Figure 1 shows the number of axioms of the input ontologies (blue bars) and the number of rules of the Datalog rewritings (red bars). For some ontologies, the rewritings got substantially larger. This was expected, and in theory unavoidable, due to the double exponential time complexity of assertion entailment in Horn-SRIQu: for Datalog, this complexity is only polynomial (since predicate arity is bounded), which is why our rewritings are in the worst case double exponential in the size of the input. Our evaluation conrms that these blow-ups are not only of theoretical nature, but may actually happen for some real-world ontologies. However, in most cases, the size of the computed Datalog rule sets was still of comparable dimensions: in 59% of cases, the increase was at most by 100%, and in 74% of cases, it was at most by 200%. Acknolwedgements. The rst two authors are funded by Deutsche Forschungsgemeinschaft in project number 389792660 (TRR 248, Center for Perspicuous Systems) and Emmy Noether grant KR 4381/1-1 (DIAMOND). The third author is funded by DFG in the CRC 912 (HAEC).

References

1. Carral , D. , Gonzalez , L. , Koopmann , P. : From Horn-SRIQ to datalog: A dataindependent transformation that preserves assertion entailment . In: Proceedings of the 33rd Conference on Arti cial Intelligence (AAAI 2019 ) ( January 2019 )

2. Deutsch , A. , Nash , A. , Remmel , J.B. : The chase revisited . In: Proc. PODS' 08 . ACM SIGMOD-SIGACT-SIGART. ACM ( 2008 )

3. Eiter , T. , Ortiz , M. , Simkus , M. , Tran , T. , Xiao , G.: Query rewriting for HornSHIQ plus rules . In: Proc. AAAI'12 . AAAI Press ( 2012 )

4. Horrocks , I. , Kutz , O. , Sattler , U. : The irresistible SRIQ . In: Proc. OWLED'05. CEUR Workshop Proceedings , vol. 188 . CEUR-WS.org ( 2006 )

5. Kazakov , Y. : An extension of complex role inclusion axioms in the description logic SROIQ . In: Proc. IJCAR'10. Lecture Notes in Computer Science , vol. 6173 , pp. 472 { 486 . Springer ( 2010 )

6. Motik , B. , Nenov , Y. , Piro , R. , Horrocks , I. , Olteanu , D. : Parallel materialisation of Datalog programs in centralised, main-memory RDF systems . In: Proc. AAAI'14 . pp. 129 { 137 . AAAI Press ( 2014 )

7. Parsia , B. , Matentzoglu , N. , Goncalves , R.S. , Glimm , B. , Steigmiller , A. : The OWL reasoner evaluation (ORE) 2015 competition report . J. of Autom. Reasoning 59 ( 4 ), 455 { 482 ( 2017 )

8. Steigmiller , A. , Liebig , T. , Glimm , B. : Konclude: System description . J. of Web Semantics 27 , 78 { 85 ( 2014 )

9. Zhou , Y. , Cuenca Grau , B. , Nenov , Y. , Kaminski , M. , Horrocks , I.: PAGOdA: Payas-you-go ontology query answering using a Datalog reasoner . J. of Artif. Intell. Res . 54 , 309 { 367 ( 2015 )