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

1 Introduction

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 [Baader et al., 2017]. 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 [Pan and Thomas, 2007; Ren et al., 2010; Botoeva et al., 2010; Carral et al., 2014; Zhou et al., 2015; B¨otcher et al., 2019].

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 of such statements. 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 contained in 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 [B¨otcher et al., 2019] 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 including those occurring in practice. The authors then lay out a new research program for ontology approximation that consists in mapping out the structure of complete (infinite) ontology approximations as a tool for guiding informed decisions when constructing incomplete (finite) approximations in practice, and also to enable a better understanding of the degree and nature of incompleteness.

In this paper, 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. Arguably, these are extremely natural cases of ontology approximation given that Horn vs. non-Horn is nowadays the most important classification criterion for DLs [Baader et al., 2017]. 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 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 [Cucala et al., 2019]. Despite being natural, however, non-Horn-to-Horn approximation turns out to be 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 ⊑D iff OT |= C ⊑D.

Example 1. Consider the ELU ontology

Then the following is an EL approximation of OS:

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 [B¨otcher et al., 2019], 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 confirm 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). The finite approximations that we obtain are too large to be directly used in practice. Nevertheless, we view our results as positive and believe that in practice approximations of reasonable size often exist, as in Example 1. A 'push button technology' for constructing them, however, is outside of the scope of this paper.

We then proceed to the cases of ELU⊥-to-EL⊥ and ALCto-EL⊥ approximations 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 approximation cases studied in [B¨otcher et al., 2019]. 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 has such a dramatic effect. We again provide an (infinite) approximation scheme.

Finally, we propose a notion of approximation that is tailored towards applications in ontology-mediated querying [Calvanese et al., 2009] 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 ALCto-EL⊥ case. Compared to the related work presented in [Kaminski et al., 2016], 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.

All proofs are deferred to the appendix [Haga et al., 2020].

2 Preliminaries

Let NC and NR be disjoint and countably infinite sets of concept names and role names. In the description logic ALC, concepts C, D are built according to the syntax rule

where A ranges over NC and r over NR. The depth of a concept is the nesting depth of the constructors ∃r and ∀r in it. For example, the concept ∃r.B ⊓ ∃r.∃s.A is of depth 2. We introduce other DLs as fragments of ALC. An ELU⊥ concept is an ALC concept that does not contain negations ¬C and value restrictions ∀r.C. An EL⊥ concept is an ELU⊥ concept that does not contain disjunctions C ⊔D. ELU concepts and EL concepts are defined likewise, but additionally forbid the use of the bottom concept ⊥.

For any of these DLs L, an L ontology is a set of concept inclusions (CIs) C ⊑ D where C and D are L concepts. While ontologies used in practice have to be finite, we frequently consider also infinite ontologies. W.l.o.g., we assume that all occurrences of ⊥ in ELU⊥ ontologies are in CIs of the form C ⊑ ⊥, where C does not contain ⊥. An acyclic ontology O is a set of concept inclusions A ⊑ C and concept equivalences A ≡ C where A is a concept name (that is, it is not a compound concept), the left-hand sides are unique, and O does not contain a definitiorial cycle A0 ▷◁1 C0, . . . , An ▷◁n Cn, ▷◁i∈ {⊑, ≡}, where Ci contains Ai+1 mod n+1 for all i ≤ n. An equivalence A ≡ C can be viewed as two CIs A ⊑ C and C ⊑ A and thus every acyclic ontology is an ontology in the original sense.

A signature Σ is a set of concept and role names, uniformly referred to as symbols. We use sig(X) to denote the set of symbols used in any syntactic object X such as a concept or an ontology. If sig(X) ⊆ Σ, we also say that X is over Σ. The size of a (finite) syntactic object X, denoted ||X||, is the number of symbols needed to write it, with every occurrence of a concept and role name contributing one.

The semantics of concepts and ontologies is defined in terms of interpretations I = (∆I , ·I ) as usual, see [Baader et al., 2017]. An interpretation I satisfies a CI C ⊑ D if C I ⊆ DI , an equivalence A ≡ C if AI = C I , and it is a model of an ontology O if it satisfies all CIs in O. Concept C is subsumed by concept D w.r.t. ontology O, written O |= C ⊑ D, if every model I of O satisfies the CI C ⊑ D; we then also say that the CI is a consequence of O. Subsumption can be decided in polynomial time in EL⊥ and is EXPTIME-complete between ELU and ALC [Baader et al., 2017]. We now give our main definition of approximation. With concept of depth bounded by ω, we mean concepts of unrestricted depth.

Definition 1. Let OS be an ALC ontology, sig(OS) = Σ, LT any of the DLs introduced above, and ℓ ∈ N ∪ {ω}. A (potentially infinite) LT ontology OT is an ℓ-bounded LT approximation of OS if

for all LT concepts C, D over Σ of depth bounded by ℓ. OT is non-projective if sig(OT ) ⊆ Σ and projective otherwise. We refer to ω-bounded LT approximations as LT approximations.

We refer to the "if" direction of the biimplication in Definition 1 as soundness of the approximation and to the "only if" direction as completeness. Infinite approximations always exist: take as OT the set of all L CIs C ⊑ D with C, D over Σ and OS |= C ⊑ D. In the same way, finite (non-projective) depth-bounded approximations always exist. With LS-to-LT approximation, LS a DL and LT a fragment of LS, we mean the task to approximate an LS ontology in LT , possibly using an infinite ontology.

3 ELU-to-EL Approximation

We consider ELU-to-EL approximation as the simplest case of approximating non-Horn ontologies in a Horn DL.

Fundamentals. We start with observing that projective approximations are more powerful than non-projective ones.

Proposition 1. The ELU ontology

Figure 1: Candidate EL approximation OT .

has a finite projective EL approximation, but every nonprojective EL approximation is infinite.

In fact, a finite projective EL approximation OT of the ontology OS from Proposition 1 is obtained from OS by replacing the CI in the first line with

The intuitive reason for why OS has no finite non-projective EL approximation is that OS |= A′ ⊓ ∃rn .A ⊑ M for all n ≥ 0. Proposition 1 indicates that projective approximations are preferable. Since they also seem perfectly acceptable from an application viewpoint, we concentrate on the projective case and from now on mean projective approximations whenever we speak of approximations.

To illustrate the challenges of ELU-to-EL approximation, it is instructive to consider a candidate approximation scheme that might be suggested by Proposition 1. We use sub(OS) to denote the set of all subconcepts of (concepts in) the ontology OS and sub-(OS) to denote the restriction of sub(OS) to concept names and existential restrictions ∃r.C. We use Con(OS) to denote the set of all non-empty conjunctions of concepts from sub-(OS) without repetitions and Dis(OS) to mean the set of all disjunctions of concepts from Con(OS) without repetitions. Now, a (finite projective) candidate EL approximation scheme is given in Figure 1 where C ranges over sub(OS) and D1,D2,D3 range over Dis(OS). It indeed yields an approximation when applied to the ontology OS in Proposition 1. There are, however, two major problems. First, the syntactic structure of OS is lost completely, which is undesirable in practice where ontologies are the result of a careful modeling effort. We could include all EL concept inclusions fromOS in the approximation, but this would be purely cosmetic since all such CIs are already implied. Second, the approximation is incomplete in general. In fact, finite approximations need not exist also in the projective case while the approximation scheme in Figure 1 is always finite.

Proposition 2. The ELU ontology

has no finite EL approximation.

The intuitive reason for why OS has no finite EL approximation is that OS |= ∃r.(A⊓∃sn .⊤) ⊑ ∃r.(B1 ⊓∃sn .⊤) for all n ≥ 0.

The ontology in Proposition 2 can be varied to show that even bounded depth approximations can get very large. The function tower : N × N → N is defined as tower(0, n) := n and tower(k + 1, n) := 2tower(k,n) .

where in the last line

• F is an EL concept over sig(OS) decorated with disjunctions from Dis(OS) at leaves and
• G is an OS-generatable EL concept over sig(OS) such that depth(F ) ≤ depth(G) < ℓ.

Figure 2: ℓ-bounded EL approximation OℓT .

Proposition 3. Let On S be obtained from the ontology OS in Proposition 2 by replacing the bottommost CI with

Then for all n, ℓ ≥ 1 and any ℓ-bounded EL approximation OT of On S , ||OT || ≥ tower(ℓ, n).

AComplete Approximation. We present amore careful approximation scheme that aims to preserve the structure of OS, is complete, and yields a finite approximation in many practical cases. Let OS be an ELU ontology to be approximated. As a preliminary, we assume that for all CIs C ⊑ D ∈ OS, C is an EL concept. If this is not the case, then we can rewrite OS by exhaustively replacing every disjunction C ⊔D that occurs (possibly as a subconcept) on the left-hand side of a concept inclusion in OS with a fresh concept name XC⊔D and adding the inclusions C ⊑ XC⊔D and D ⊑ XC⊔D. It is not hard to see that the resulting ontology O′S is of size polynomial in ||OS|| and a conservative extension of OS in the sense that OS |= C ⊑ D iff O′S |= C ⊑ D for all ELU concepts C, D over sig(OS). Consequently, every EL approximation of O′S is also a projective EL approximation of OS and we can work with O′S in place of OS.

Let ℓ ∈ N ∪ {ω}. The proposed EL approximation OℓT of OS is given in Figure 2 where D1,D2 range over Dis(OS) and D ranges over Dis-(OS), the set of all disjunctions in Dis(OS) that have at least two disjuncts. We still have to define the notation and terminology used in the figure. For an ELU concept C such that all disjunctions in C are from Dis(OS), we use C ↑ to denote the EL concept obtained from C by replacing every outermost D ∈ Dis-(OS) with a fresh concept name XD. Set DNF(C) = C if C is a concept name or of the form ∃r.D, DNF(C1 ⊓ C2) = DNF(C1) ⊓ DNF(C2), and define DNF(C1 ⊔ C2) to be the ELU-concept obtained by converting C1 ⊔C2 into disjunctive normal form (DNF), treating existential restrictions ∃r.D as atomic concepts, that is, the argument D is not modified. Note that while ||DNF(C)|| may be exponential in ||C||, we have ||DNF(C)↑ || ≤ ||C||. By decorating an EL concept C with disjunctions from Dis(OS) at leaves, we mean to replace subconcepts ∃r.E of C with E of depth 0 by ∃r.(E ⊓ D), D ∈ Dis(OS). As a special case, we can replace C with C ⊓D, D ∈ Dis(OS), if C is of depth 0.

Definition 2. An EL concept C is OS-generatable if there is an ∃r.D ∈ sub(OS) that occurs on the right-hand side of a CI in OS and satisfies OS |=D ⊑ C.

Let us explain the proposed approximation. The first three lines of Figure 2 can be viewed as a more careful version of the first four lines of Figure 1. In the first line, we preserve the structure of OS as long as it lies outside the scope of a disjunction operator, thanks to the careful definition of DNF(C). This is not cosmetic as in the candidate approximation in Figure 1: since we introduce the concept names XD only when a disjunction is 'derived' (first line) and only for disjunctions D ∈ Dis-(OS), OℓT is no longer guaranteed to be an approximation when the first line in Figure 2 is dropped. The last line of the approximation addresses the effect illustrated by Proposition 2. It is strong enough so that a counterpart of the second last line in Figure 1 is not needed. An example application of our approximation scheme is given in [Haga et al., 2020].

An interesting aspect of our approximation is that it turns out to be finite in many practical cases. In fact, it is easy to see that OℓT is finite for all ℓ < ω and that Oω T is finite if and only if there are only finitely many EL concepts that are OS-generatable, up to logical equivalence; we then say that OS is finitely generating. Since ontologies from practice tend to have a simple structure, one might expect that they often enjoy this property. Below, we report about a case study that confirms this expectation.

How does the approximation scheme in Figure 2 relate to the examples given above? For the ontologies OS in Example 1 and in Proposition 1, our approximation Oω T contains all CIs in the approximation OT given in place. Of course, Oω T also contains a lot of additional CIs that, however, do not result in any new consequences C ⊑ D with C,D EL concepts over sig(OS). It seems very difficult to identify up front those CIs that are really needed. We can remove them after constructing Oω T by repeatedly deciding conservative extensions [Lutz and Wolter, 2010], but this is not practical given the size of Oω T . Nevertheless, both ontologies OS are finitely generating and thus in both cases Oω T is finite. In Example 1, the OS-generatable concepts are ⊤, MainJob, PartTime, and MainJob ⊓ PartTime (up to logical equivalence) while there are no OS-generatable concepts for Proposition 1. For Proposition 2, there are infinitely many OS-generatable concepts such as ∃sn .⊤ for all n ≥ 0.

Case Study. We have considered the seven non-trivial ELU ontologies that are part of the Manchester OWL corpus. 1 The size of the ontologies ranges from 113 to 813 concept inclusions and equalities. All ontologies use disjunction on the right-hand side of CIs (thus in a non-trivial way) and none of them is acyclic. We have been able to prove that all these ontologies are finitely generating and thus the approximation Oω T is finite. Our proof relies on the following observation.

Lemma 1. OS is not finitely generating iff for every n ≥ 0, there is an ∃r.D ∈ sub(OS) that occurs on the right-hand side of a CI and a sequence r1, . . . , rn of role names from OS such that OS |= D ⊑ ∃r1. · · · .∃rn.⊤.

In our implementation, we use role inclusions to avoid going through all of the exponentially many sequences r1, . . . , rn. Lemma 1 can also be used to show the following.

1 http://owl.cs.manchester.ac.uk/publications/supportingmaterial/owlcorpus/

Theorem 1. It is decidable whether a given ELU-ontology OS is finitely generating.

By what was said above, this implies that it is decidable whether the approximation Oω T from Figure 2 is finite.

Soundness and Completeness. We now establish soundness and completeness of the proposed approximation, the main result in this section.

Theorem 2. For every ℓ ∈ N ∪ {ω}, OℓT is an ℓ-bounded EL approximation of OS.

While soundness is easy to show, completeness is remarkably subtle to prove. It is stated by the following lemma which shows that our approximation OℓT is actually stronger than required in that it preserves all EL subsumptions C ⊑ D with D of depth bounded by ℓ and C of unrestricted depth.

Lemma 2. Let ℓ ∈ N∪ {ω}. Then OS |= C0 ⊑ D0 implies OℓT |= C0 ⊑ D0 for all EL concepts C0,D0 over sig(OS) such that the role depth of D0 is bounded by ℓ.

The proof of Lemma 2 is the most substantial one in this paper. It uses a chase procedure for ELU ontologies that is specifically tailored towards proving completeness in that it is deterministic rather than disjunctive and mimics the concept inclusions in Figure 2. Showing that this chase is complete is far from trivial.

Fewer Symbols. The number of fresh concept names XD in OℓT is double exponential in ||OS|| since the number of disjunctions in Dis-(O) is. However, OℓT can be rewritten into an ontology ̂ OℓT that uses only single exponentially many fresh concept names and is still an ℓ-bounded approximation of OS. The idea is to transition from disjunctive normal form to conjunctive normal form, that is, to replace each concept name XD, D ∈ Dis-(O), with a conjunction of concept names YD′ where D′ is a disjunction of concepts from sub-(O), rather than conjunctions thereof. Details are in [Haga et al., 2020].

Theorem 3. For every ℓ ∈ N∪ {ω}, ̂ OℓT is an ℓ-bounded EL approximation of OS.

AcyclicOntologies. Using Lemma 1, one can show that Oω T is finite whenever OS is an acyclic ELU ontology. In fact, the length n of role sequences with the properties stated in the lemma is bounded by ||OS|| if OS is acyclic.

Theorem 4. Every acyclic ELU ontology has a finite EL approximation.

There is, however, more that we can say about acyclic ontologies. We first observe that there are acyclic ELU ontologies that have finite EL approximations, but no EL approximation that is an acyclic ontology.

Example 2. Consider the acyclic ELU ontology

Then OT = {B1 ⊓ B2 ⊑ A, B1 ⊓ B3 ⊑ A, A ⊑ B1} is an EL approximation of OS, but OS has no EL approximation that is an acyclic ontology, finite or infinite.

Further, our approximations OℓT can be simplified for acyclic ELU ontologies OS. Let ˜ OℓT be defined like OℓT

in Figure 2, except that in the last line, F ranges only over concept names (not decorated with disjunctions) rather than over compound concepts, a significant simplification.

Theorem 5. Let ℓ ∈ N ∪ {ω} and let OS be an acyclic ELU ontology. Then ˜ OℓT is an ℓ-bounded EL approximation of OS.

Based on this observation, constructing finite EL approximations of acyclic ELU ontologies does not seem infeasible in practice.

4 ALC-to-EL⊥ Approximation

We consider ELU⊥-to-EL⊥ and ALC-to-EL⊥ approximation which turn out to be closely related to each other and significantly different from ELU-to-EL approximation.

It immediately follows from the results in Section 3 that finite approximations are guaranteed to exist neither in the ELU⊥-to-EL⊥ nor in the ALC-to-EL⊥ case. However, while we have argued that finite ELU-to-EL approximations can be expected to exist in many practical cases, this does not appear to be true for ELU⊥-to-EL⊥ and ALC-to-EL⊥. The following example illustrates the problem.

Example 3. Consider the ELU⊥ ontology

There are no OS-generatable EL concepts. Yet, there is no finite EL⊥ approximation of OS. Informally, this is because

While the above example is for ELU⊥-to-EL⊥, there is an additional effect in ALC-to-EL⊥ that already occurs for very simple ontologies OS.

Example 4. The ALC ontology OS = {A ⊑ ∀r.B} has no finite EL⊥ approximation. This is shown in [B¨otcher et al., 2019] for the equivalent ELI ontology {∃r-.A ⊑ B}. Informally, this is because OS |= A ⊓ ∃rn+1 .⊤ ⊑ ∃r.(B ⊓ ∃rn .⊤) for all n ≥ 1.

Note that the ontology OS in Example 4 is acyclic and thus in contrast to the ELU-to-EL case, finite EL⊥ approximations of acyclic ALC ontologies need not exist. In a sense, Example 3 shows the same negative result for the ELU⊥-to-EL⊥ case. While the ontology used there is not strictly acyclic, acyclic ontologies do not make much sense in the case of ELU⊥ and additionally admitting CIs C1 ⊓ C2 ⊑ ⊥ as used in Example 3 seems to be the most modest extension possible that incorporates ⊥ in a meaningful way.

Despite these additional challenges, we can extend the approximation given in Section 3 to ELU⊥-to-EL⊥ and to ALCto-EL⊥ when we are willing to drop OS-generatability and, as a consequence, accept the fact that approximations are infinite unless they are depth bounded. Note that the latter is also the case in L-to-EL approximation where L is an expressive Horn DL such as ELI [B¨otcher et al., 2019].

2 A formal proof is analogous to that of Proposition 2.

where in the last line F is an EL concept over sig(OS) decorated with disjunctions from Dis(OS) at leaves and G is an EL concept over sig(OS) such that

1. F has no top-level conjunct ∃r.F ′ s.t. OS |= F ′ ⊑ G;
2. depth(F) ≤ depth(G) < ℓ.

Figure 3: ℓ-bounded EL⊥ approximation OℓT .

We first reduce ALC-to-EL⊥ approximations to ELU⊥-toEL⊥ approximations. Let OS be an ALC ontology. We can transform OS into an ELU⊥ ontology as follows:

1. replace each subconcept ∀r.C with ¬∃r.¬C;
2. select a concept ¬C such that C contains no negation, replace all occurrences of ¬C with the fresh concept name A¬C, and add the CIs ⊤ ⊑ C ⊔ A¬C and C ⊓ A¬C ⊑ ⊥; repeat until no longer possible.

The resulting ontology O′S is of size polynomial in ||OS|| and a conservative extension of OS in the sense that OS |= C ⊑ D iff O′S |= C ⊑ D for all ALC concepts C,D over sig(OS). Consequently, every EL⊥ approximation of O′S is also a (projective) EL⊥ approximation of OS.

It thus suffices to consider ELU⊥-to-EL⊥ approximations. Thus let OS be an ELU⊥ ontology. For each ℓ ∈ N ∪ {ω}, the EL⊥ approximation OℓT of OS is given in Figure 2 where again D ranges over Dis-(OS) and D1, D2 range over Dis(OS); both Dis(OS) and Dis-(OS) are defined exactly as for ELU ontologies and in DNF(C) we drop all disjuncts that contain ⊥ as a conjunct, possibly resulting in the empty disjunction (which represents ⊥). Point 1 can be viewed as an optimization that sometimes helps to avoid the expensive last line. There, a top-level conjunct means a concept Fi if F takes the form F1 ⊓ · · · ⊓ Fn, n ≥ 1. In [Haga et al., 2020], we point out another non-trivial such optimization.

Theorem 6. OℓT is an ℓ-bounded EL⊥ approximation of OS.

The proof of Theorems 2 and 6 also establishes another result that will turn out to be interesting in the context of ontology-mediated queries in Section 5. We use OT to denote the restriction of Oω T to the (instantiations) of the first three lines in Figure 3 (equivalently: Figure 2). Clearly, OT is always finite.

Theorem 7. Let C0,D0 be EL⊥ concepts with D0 ∈ sub(OS). Then OS |= C0 ⊑D0 iff OT |= C0 ⊑D0.

5 Approximations and Query Evaluation

The notion of approximations given in Section 2 is tailored towards preserving subsumptions. In ontology-mediated querying, in contrast, the main aim of approximation is to preserve as many query answers as possible. We propose a suitable notion of approximation and show that the results obtained in the previous sections have interesting applications also in ontology-mediated querying.

Let NI be a countably infinite set of individual names disjoint from NC and NR. An ABox is a finite set of concept assertions A(a) and role assertions r(a, b) where A ∈ NC, r ∈ NR, and a, b ∈ NI. We use Ind(A) to denote the set of individual names in the ABox A. An interpretation I satisfies a concept assertion A(a) if a ∈ AI and a role assertion r(a, b) if (a, b) ∈ rI . It is a model of an ABox if it satisfies all assertions in it. A Σ-ABox is an ABox A with sig(A) = Σ.

An ontology-mediated query (OMQ) is a triple Q = (O, Σ, q) with O an ontology, Σ ⊆ sig(O)∪sig(q) an ABox signature, and q an actual query. While conjunctive queries (CQs) and unions of CQs are a popular choice for formulating q and our central Definition 3 below makes sense also for these richer query languages, for simplicity we concentrate on atomic queries (AQs) A(x) where A is a concept name and on EL queries (ELQs) C(x) where C an EL concept. We also mention ALC queries (ALCQs) C(x) where C is an ALC concept. Note that all such queries are unary. We use ELQ(Σ) to denote the language of all ELQs that use only symbols from signature Σ. Let (L, Q) denote the OMQ language that contains all OMQs Q in which O is formulated in DL L and q in query language Q, such as in (EL, AQ).

Let Q = (O, Σ, C(x)) be an OMQ and A a Σ-ABox. Then a ∈ Ind(A) is an answer to Q on A, written A |= Q(a), if a ∈ C I for all models I of O and A. For OMQs Q1 and Q2, Qi = (Oi,Σ, qi), we say that Q1 is contained in Q2 and write Q1 ⊆ Q2 if for every Σ-ABox A and a ∈ Ind(A), A |= Q1(a) implies A |= Q2(a). We say that Q1 is equivalent to Q2 and write Q1 ≡ Q2 if Q1 ⊆ Q2 and Q2 ⊆ Q1.

A natural definition of ontology approximation in the context of OMQs is as follows.

Definition 3. Let OS be an ALC ontology, LT one of the DLs from Section 2, and Q a query language. An LT ontology OT is an LT approximation of OS w.r.t Q if for all queries q ∈ Q and all signatures Σ with Σ ∩ sig(OT ) ⊆ sig(OS),

1. (OS,Σ, q) ⊇ Q implies (OT ,Σ, q) ⊇ Q for all OMQs Q = (O′T , Σ, q) with O′T ∈ LT .

OT might use fresh symbols and thus approximations are projective. Informally, Point 1 is a soundness condition and Point 2 formalizes 'to preserve as many query answers as possible'. It is not guaranteed that the OMQs (OS,Σ, q) and (OT , Σ, q) are equivalent for all relevant queries q and signatures Σ, and the following example shows that this is in fact impossible to achieve.

Example 5. Let OS be the ELU ontology

Then an EL approximation of OS w.r.t. ELQ is

However, there is no OMQ in (EL, ELQ) that is equivalent to (OS, {r}, A(x)) since it would have to return a as an answer on the ABox {r(a, a)}, but not on the ABox {r(a, b), r(b, a)}. No OMQ from (EL, ELQ) has this property.

It turns out that the approximations from Sections 3 and 4 are also useful in the context of Definition 3 when we choose ELQ or AQ as the query language. In particular, it follows from Theorem 7 that every ALC ontology OS has a finite EL⊥ approximation w.r.t. AQ.

Theorem 8. Let OS be an ALC ontology, sig(OS) = Σ. Then

1. the ontologyOω T from Section 4 is an EL⊥ approximation of OS w.r.t. ELQ(Σ);
2. the ontology OT from Section 4 is a (finite) EL⊥ approximation of OS w.r.t. AQ;
3. if OS falls within ELU, then the ontology Oω T from Section 3 is an EL approximation of OS w.r.t. ELQ(Σ).

Point 2 also implies that OT is an EL approximation of OS w.r.t. AQ whenever OS is an ELU ontology. We close with an interesting application of Theorem 8.

The topic of rewriting an OMQ into a simpler query language has received a lot of interest in the literature, see for example [Calvanese et al., 2007; Gottlob et al., 2014; Kaminski et al., 2016; Feier et al., 2019]. An OMQ Q is (L,Q)-rewritable if there is an OMQ Q′ in the OMQ language (L, Q) such that Q ≡ Q′ .

By virtue of Theorem 8, we can decide whether an OMQ Q = (O, Σ, A(x)) from (ALC, AQ) is (EL⊥, AQ)-rewritable. It can be seen that this is the case if and only if Q is equivalent to an OMQ Q′ ∈ (EL⊥, AQ) of the form (O′ , Σ, A(x)). By Condition 2 of Definition 3, it thus suffices to construct the finite EL⊥ approximation OT of O w.r.t. AQ from Theorem 8 and check whether Q ≡ (OT , Σ, A(x)), which is decidable [Bienvenu et al., 2014]. This result extends to (ALC,ALCQ) since every OMQ from this language is equivalent to one from (ALC,AQ). Via the results in [Feier et al., 2018], this can be lifted further to a certain class of conjunctive queries.

Theorem 9. Given an OMQ Q ∈ (ALC, ALCQ), it is decidable whether Q is (EL⊥, AQ)-rewritable.

6 Conclusion

We have investigated the structure and finiteness of ontology approximations when transitioning from non-Horn DLs to Horn DLs. We believe that our results shed significant light on the situation. It remains, however, an important and challenging topic for future work to push our techniques further towards practical applicability. Also, there are many other relevant cases of approximation. As a first step, one might think about extending the DLs considered in this paper with role inclusions. It might further be interesting to study the problem to decide whether a given (finite) candidate is an approximation of a given ontology. We expect this to be quite non-trivial. A related result in [Lutz et al., 2012] states that it is between EXPTIME and 2EXPTIME to decide whether a given ELU ontology OS of a restricted syntactic form has a finite complete EL approximation. Without the restriction, even decidability is open.

Acknowledgements

Supported by the DFG Collaborative Research Center 1320 EASE - Everyday Activity Science and Engineering.