The Combined Approach to Query Answering in Horn-ALCHOI Q (Extended Abstract)?

Abstract

Answering conjunctive queries (CQs) over Description Logics (DL) ontologies is an important reasoning task with many applications in knowledge representation. Intensive research e orts in recent years have signi cantly improved our understanding of this problem, and led to e cient algorithms and implementations for many DL languages [2,3]. Query rewriting was an important step towards widespread practical implementation in legacy databases, but it is limited to DLs of sub-polynomial data complexity. This limitation was overcome by the so-called combined approach, which answers CQs in two steps: 1. Materialisation: data is augmented to build a query-independent interpretation, which may not be a model but is complete for CQ answering. 2. Filtration: queries are evaluated over this interpretation and unsound answers are discarded in a ltration step.

-

103 102 600 400 200 0 David Carral, Irina Dragoste, and Markus Krotzsch

UOBM

Reactome Uniprot

Proof of Concept. We evaluate a prototype implementation of the materialisation phase, which we consider the performance-critical part of our algorithm. In contrast, our ltration phase uses a polynomial algorithm, which is computationally similar to the ltration in other combined approaches that have already been shown to be e cient in practical cases [ 5 ]. Since materialisation decides fact entailment for Horn-ALCHOIQ, we can meaningfully compare performance against standard DL reasoners. We use our implementation to solve assertion retrieval, that is, the reasoning task that consists in computing all assertions that are entailed by an ontology. We compare performance with that of Konclude (v0.6.2) [ 16 ], which we use as a command-line client on local input les.

Since CQ answering is most relevant in data-intensive applications, we consider ontologies with large sets of assertions (ABoxes). We select a standard benchmark, UOBM [ 10 ]; and two real-world ontologies, Reactome and Uniprot, which are used in the evaluation of PAGOdA [ 17 ]. The resulting ontologies contain 254 (UOBM), 481 (Reactome), and 317 (Uniprot) terminological axioms, respectively. None of these ontologies belong to a known tractable fragment of Horn-ALCHOIQ. For each ontology, we consider ABoxes of various sizes, generated by using the size parameter for the benchmark (UOBM), and by sampling the real-world ABoxes (Reactome, Uniprot).

Our test system is a commodity laptop (16GB RAM, 500GB SSD, CPU i78550U/4 cores/1.8GHz, Windows 10), where we con gure the operating system to allow up to 28GB of virtual memory. We measure wall-clock times spent during reasoning, ignoring the time required for parsing and loading. Konclude reports detailed times, while for our implementation we measure the time from within our prototype. Figure 1 shows the results. Note the logarithmic scale in the case of Reactome. Konclude ran out of memory for the two largest of the Uniprot samples, hence no times are reported here. The performance results show that our prototype can already achieve competitive performance. Acknolwedgements. This work is supported by Deutsche Forschungsgemeinschaft in project number 389792660 (TRR 248, Center for Perspicuous Systems) and Emmy Noether grant KR 4381/1-1 (DIAMOND).

The Combined Approach to Query Answering in Horn-ALCHOIQ

References

1. Baader , F. , Brandt , S. , Lutz , C. : Pushing the EL envelope . In: Proc. 19th Int. Joint Conf. on Arti cial Intelligence (IJCAI) ( 2005 )

2. Bienvenu , M. , Hansen , P. , Lutz , C. , Wolter , F. : First order-rewritability and containment of conjunctive queries in Horn description logics . In: Proc. 25th Int. Joint Conf. on Arti cial Intelligence (IJCAI) ( 2016 )

3. Calvanese , D. , De Giacomo , G. , Lembo , D. , Lenzerini , M. , Rosati , R. : Tractable reasoning and e cient query answering in description logics: The DL-Lite family . Journal of Automated Reasoning ( 2007 )

4. Carral , D. , Dragoste , I. , Krotzsch, M.: The combined approach to query answering in horn-ALCHOIQ . In: Proc. 16th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR) ( 2018 )

5. Feier , C. , Carral , D. , Stefanoni , G. , Cuenca Grau , B. , Horrocks , I. : The combined approach to query answering beyond the OWL 2 pro les . In: Proc. 24th Int. Joint Conf. on Arti cial Intelligence (IJCAI) ( 2015 )

6. Kazakov , Y. : Consequence-driven reasoning for Horn-SHIQ ontologies . In: Proc. 21st Int. Joint Conf. on Arti cial Intelligence (IJCAI) ( 2009 )

7. Kontchakov , R. , Lutz , C. , Toman , D. , Wolter , F. , Zakharyaschev , M.: The combined approach to ontology-based data access . In: Proc. 22nd Int. Joint Conf. on Arti cial Intelligence (IJCAI) ( 2011 )

8. Krotzsch, M. , Rudolph , S. , Hitzler , P. : Complexities of Horn DLs . ACM Transactions Computational Logic ( 2013 )

9. Lutz , C. , Seylan , I. , Toman , D. , Wolter , F. : The combined approach to OBDA: Taming role hierarchies using lters . In: Proc. 12th Int. Semantic Web Conf. (ISWC) ( 2013 )

10. Ma , L. , Yang , Y. , Qiu , Z. , Xie , G.T. , Pan , Y. , Liu , S. : Towards a complete OWL ontology benchmark . In: Proc. 3rd Int. Semantic Web Conf. (ESWC) ( 2006 )

11. Ortiz , M. , Rudolph , S. , Simkus , M. : Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2 . In: Proc. 12th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR) ( 2010 )

12. Ortiz , M. , Rudolph , S. , Simkus , M. : Query answering in the Horn fragments of the description logics SHOIQ and SROIQ . In: Proc. 22nd Int. Joint Conf. on Arti cial Intelligence (IJCAI) ( 2011 )

13. Rudolph , S. , Glimm , B. : Nominals, inverses, counting, and conjunctive queries or: Why in nity is your friend! Journal of Arti cial Intelligence Research ( 2010 )

14. Simanc k , F., Kazakov , Y. , Horrocks , I. : Consequence-based reasoning beyond Horn ontologies . In: Proc. 22nd Int. Joint Conf. on Arti cial Intelligence (IJCAI) ( 2011 )

15. Stefanoni , G. , Motik , B. , Horrocks , I. : Introducing nominals to the combined query answering approaches for EL . In: Proc. 27th (AAAI) Conf. on Arti cial Intelligence (AAAI) ( 2013 )

16. Steigmiller , A. , Liebig , T. , Glimm , B. : Konclude: System description . Journal of Web Semantics ( 2014 )

17. Zhou , Y. , Cuenca Grau , B. , Nenov , Y. , Kaminski , M. , Horrocks , I.: PAGOdA: Payas-you-go ontology query answering using a Datalog reasoner . Journal Arti cial Intelligence Research ( 2015 )