A Journey into Ontology Approximation: From Non-Horn to Horn

Abstract

We study complete approximations of an ontology formulated in a non-Horn description logic (DL) such as $\mathcal{A}\mathcal{LC}$ in a Horn DL such as~$\mathcal{E}\mathcal{L}$. We provide concrete approximation schemes that are necessarily infinite and observe that in the $\mathcal{E}\mathcal{L}\mathcal{U}$-to-$\mathcal{E}\mathcal{L}$ case finite approximations tend to exist in practice and are guaranteed to exist when the original ontology is acyclic. In contrast, neither of this is the case for ${\mathcal{E}\mathcal{L}\mathcal{U}}_{\perp }$-to-${\mathcal{E}\mathcal{L}}_{\perp }$ and for $\mathcal{A}\mathcal{LC}$-to-${\mathcal{E}\mathcal{L}}_{\perp }$ approximations. We also define a notion of approximation tailored towards ontology-mediated querying, connect it to subsumption-based approximations, and identify a case where finite approximations are guaranteed to exist.

21 pages, 4 figures, paragraph with examples added