A Journey into Ontology Approximation: From Non-Horn to Horn (Abstract)? Anneke Haga1 , Carsten Lutz1 , Johannes Marti2 , and Frank Wolter3 1 Universität Bremen, Germany 2 Universiteit van Amsterdam, Netherlands 3 University of Liverpool, UK Despite prominent standardization efforts such as OWL, a large variety of description logics (DLs) continues to be used as ontology languages. In fact, ontology designers choose a DL suitable for their purposes based on many factors including expressive power, computational properties, and tool support [1]. Since ontology engineering frequently involves (partial) reuse of existing ontologies, this raises the problem of converting an ontology written in some source DL LS into a desired target DL LT . A particularly important case is ontology approximation where LT is a fragment of LS , studied for example in [2,3,5,10,11,12] In practice, ontology approximation is often done in an ad hoc way by dropping all statements from the source ontology OS that are not expressible in LT , or at least the inexpressible parts thereof. It is well-known that this results in incomplete approximations, that is, there will be knowledge in OS that could be expressed in LT , but is not entailed by the resulting approximated ontology. The degree and nature of the resulting incompleteness is typically neither understood nor analyzed. One reason for this unsatisfactory situation might be the fact that it is by no means easy to construct complete approximations and, even worse, finite complete approximations are not guaranteed to exist. This was studied in depth in [2] where ontologies formulated in expressive Horn DLs such as Horn-SHIF and ELI are approximated in tractable Horn DLs such as EL. For example, it is shown there that finite complete ELI-to-EL approximations do not exist even in extremely simple cases that frequently occur in practice. This gives rise to a new research agenda for ontology approximation that consists in mapping out the structure of complete infinite ontology approximations to guide informed decisions when manually constructing incomplete finite approximations in practice. It also enables a better understanding of the degree and nature of incompleteness. In the paper that this abstract reports about [7,8], we consider LS -to-LT ontology approximation where LS is a non-Horn DL such as ALC and LT is a tractable Horn DL such as EL. We believe that these are extremely natural cases of ontology approximation, given that Horn vs. non-Horn is nowadays the most important classification criterion for DLs [1]. Non-Horn DLs include expressive features such as negation and disjunction and require ‘reasoning by cases’ which is computationally costly, but also have considerably higher expressive power ? Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 2 A. Haga et al. than Horn DLs. Horn DLs, in contrast, enjoy favourable properties such as the existence of universal models and of ‘consequence-based’ reasoning algorithms that avoid reasoning by cases [6]. It turns out, though, that non-Horn-to-Horn approximation is a challenging endeavour. We start with the fundamental case of ELU-to-EL approximation. Given an ELU ontology OS , we aim to find a (potentially infinite) EL ontology OT such that for all EL concepts C, D in the signature of OS , OS |= C v D iff OT |= C v D. Example 1. Consider the ELU ontology OS = { Job v MainJob t SideJob ∃job.SideJob v ∃job.(MainJob u PartTime) }. Then the following is an EL approximation of OS : OT = { ∃job.SideJob v ∃job.(MainJob u PartTime) ∃job.Job v ∃job.MainJob ∃job.(Job u PartTime) v ∃job.(MainJob u PartTime) }. The last two lines of OT illustrate that EL consequences of ELU ontologies can be rather non-obvious. We first prove that finite approximations need not exist in the ELU-to-EL case and that depth bounded approximations may be non-elementary in size. Our main result is then a concrete approximation scheme that makes explicit the structure of complete infinite approximations and aims to keep as much structure of the source ontology as possible. An interesting and, given the results in [2], surprising feature of our scheme is that it can be expected to often deliver finite approximations in practical cases. We perform a case study based on the Manchester ontology corpus that confirms this expectation. We also show that if OS is an acyclic ELU ontology, then a finite EL approximation always exists (though it need not be acyclic). We then proceed to the cases of ELU ⊥ -to-EL⊥ and ALC-to-EL⊥ approxima- tions which turn out to be closely related to each other. They also turn out to be significantly different from the ELU-to-EL case in that finite approximations do not exist in extremely simple (and practical) cases, much like in the Horn ap- proximation cases studied in [2]. Also, finite approximations of acyclic ontologies are no longer guaranteed to exist. While this is not good news, it is remarkable that the addition of the ⊥ symbol to the source DL has such a dramatic effect. We again provide an (infinite) approximation scheme. Finally, we propose a notion of approximation that is tailored towards applica- tions in ontology-mediated querying [4] and show that it is intimately related to the subsumption-based approximations that we had studied before. Remarkably, if we concentrate on atomic queries (AQs), then we obtain finite approximations even in the ALC-to-EL⊥ case. Compared to the related work presented in [9], we do not require the preservation of all query answers, but only of a maximal subset thereof, and our method is applicable to all ontologies formulated in the Title Suppressed Due to Excessive Length 3 source DL chosen rather than to a syntactically restricted class. We also observe an interesting application to the rewritability of ontology-mediated queries OMQ, that is, we use our results to prove that it is decidable wether an OMQ from the OMQ language (ALC, ALCQ) is rewritable into an equivalent OMQ from the language (EL⊥ , AQ). Here, ALCQ denotes the query language that consists of all ALC concepts and AQ denotes the class of atomic queries of the form A(x). Acknowledgments. Supported by the DFG Collaborative Research Center 1320 EASE - Everyday Activity Science and Engineering. References 1. Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press (2017) 2. Bötcher, A., Lutz, C., Wolter, F.: Ontology approximation in Horn description logics. In: Proc. of IJCAI. pp. 1574–1580. ijcai.org (2019) 3. Botoeva, E., Calvanese, D., Rodriguez-Muro, M.: Expressive approximations in DL-Lite ontologies. In: Proc. of AIMSA. LNCS, vol. 6304, pp. 21–31. Springer (2010) 4. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Poggi, A., Rodriguez- Muro, M., Rosati, R.: Ontologies and databases: The DL-Lite approach. In: Rea- soning Web. LNCS, vol. 5689, pp. 255–356. Springer (2009) 5. Carral, D., Feier, C., Grau, B.C., Hitzler, P., Horrocks, I.: EL-ifying ontologies. In: Proc. of IJCAR. pp. 464–479 (2014) 6. Cucala, D.T., Grau, B.C., Horrocks, I.: 15 years of consequence-based reasoning. In: Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday. LNCS, vol. 11560, pp. 573–587. Springer (2019) 7. Haga, A., Lutz, C., Marti, J., Wolter, F.: A journey into ontology approximation: From Non-Horn to Horn. In: Proc. of IJCAI. ijcai.org (2020) 8. Haga, A., Lutz, C., Marti, J., Wolter, F.: A journey into ontology approximation: From Non-Horn to Horn. CoRR abs/2001.07754 (2020), https://arxiv.org/abs/ 2001.07754 9. Kaminski, M., Nenov, Y., Grau, B.C.: Datalog rewritability of disjunctive datalog programs and non-Horn ontologies. Artif. Intell. 236, 90–118 (2016). https://doi.org/10.1016/j.artint.2016.03.006, https://doi.org/10.1016/j.artint.2016. 03.006 10. Pan, J.Z., Thomas, E.: Approximating OWL-DL ontologies. In: AAAI. pp. 1434– 1439 (2007) 11. Ren, Y., Pan, J.Z., Zhao, Y.: Soundness preserving approximation for tbox reasoning. In: Proc. of AAAI. AAAI Press (2010) 12. Zhou, Y., Grau, B.C., Nenov, Y., Kaminski, M., Horrocks, I.: Pagoda: Pay-as-you-go ontology query answering using a datalog reasoner. J. Artif. Intell. Res. 54, 309–367 (2015)