=Paper=
{{Paper
|id=Vol-2663/abstract-14
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-2663/abstract-14.pdf
|volume=Vol-2663
|dblpUrl=https://dblp.org/rec/conf/dlog/HagaLMW20
}}
==None==
https://ceur-ws.org/Vol-2663/abstract-14.pdf
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)