A Journey into Ontology Approximation: From Non-Horn to Horn (Abstract)?

Abstract

Despite prominent standardization e orts 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, nite 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 E LI are approximated in tractable Horn DLs such as E L. For example, it is shown there that nite complete E LI-to-E L 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 in nite ontology approximations to guide informed decisions when manually constructing incomplete nite 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 E L. We believe that these are extremely natural cases of ontology approximation, given that Horn vs. non-Horn is nowadays the most important classi cation 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

-

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 nd a (potentially in nite) EL ontology OT such that for all EL concepts C; D in the signature of OS, OS j= C v D i OT j= C v D.

Example 1. Consider the ELU ontology

OS = f

Job v MainJob t SideJob 9job:SideJob v 9job:(MainJob u PartTime) g:

Then the following is an EL approximation of OS:

OT = f 9job:SideJob v 9job:(MainJob u PartTime)

9job:Job v 9job:MainJob 9job:(Job u PartTime) v 9job:(MainJob u PartTime) g: The last two lines of OT illustrate that EL consequences of ELU ontologies can be rather non-obvious.

We rst prove that nite 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 in nite 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 nite approximations in practical cases. We perform a case study based on the Manchester ontology corpus that con rms this expectation. We also show that if OS is an acyclic ELU ontology, then a nite EL approximation always exists (though it need not be acyclic).

We then proceed to the cases of ELU ?-to-EL? and ALC-to-EL? approximations which turn out to be closely related to each other. They also turn out to be signi cantly di erent from the ELU -to-EL case in that nite approximations do not exist in extremely simple (and practical) cases, much like in the Horn approximation cases studied in [ 2 ]. Also, nite 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 e ect. We again provide an (in nite) approximation scheme.

Finally, we propose a notion of approximation that is tailored towards applications 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 nite 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 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 (E L?; 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. Botcher, 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. , RodriguezMuro , M. , Rosati , R.: Ontologies and databases: The DL-Lite approach . In: Reasoning 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 )