Actively Learning Concepts and Conjunctive Queries under ELr-Ontologies

1 Introduction

In logic based knowledge representation, a significant bottleneck is the construction of logical formulas such as description logic (DL) concepts, queries, and ontologies, as it is laborious and expensive. This is particularly true if the construction involves multiple parties because logic expertise and domain knowledge are not in the same hands. Angluin's model of exact learning, a form of active learning, is able to support the construction of logical formulas in terms of a game-like collaboration between a learner and an oracle [Angluin, 1987b; Angluin, 1987a]. Applied in knowledge representation, the learner can be a logic expert and the oracle a domain expert that is interactively queried by the learner. Alternatively, the oracle can take other forms such as a set of labeled data examples that in some way represents the formula to be learned. The aim is to find an algorithm that, when executed by the learner, constructs the desired formula in polynomial time even when the oracle is not able to provide most informative answers. Landmark results from active learning state that such algorithms exist for learning propositional Horn formulas and finite automata [Angluin et al., 1992; Angluin, 1987a].

The aim of this paper is to study active learning of DL concepts and of conjunctive queries (CQs) in the presence of an ontology. Concepts are the main building block of ontologies [Baader et al., 2017] and learning them is important for ontology engineering. CQs are very prominent in ontologymediated querying where data stored in an ABox is enriched with an ontology [Bienvenu et al., 2014]. We concentrate on the EL family of DLs which underlies the OWL EL profile of the OWL 2 ontology language [Kr¨otzsch, 2012] and is frequently used in biomedical ontologies such as SNOMED CT. We consider ontologies formulated in the DLs ELr and ELI where ELr extends EL with range restrictions and ELI extends ELr with inverse roles. In both DLs, concepts can be viewed as a tree-shaped conjunctive query, and from now on we shall treat them as such. In fact, it is not uncommon to use concepts as queries in ontology-mediated querying, which provides an additional motivation for learning them.

We now describe the learning protocol in detail. It is an instance of Angluin's model, which we do not repeat here in full generality. The aim is to learn a target CQ qT (¯x) in the presence of an ontology O. The learner and the oracle both know and agree on the ontology O, the arity of qT , and the concept and role names that are available for constructing qT ; we assume that all concept and role names in O can be used also in qT . The learner can ask two types of queries to the oracle. In a membership query, the learner provides an ABox A and a candidate answer ¯a and asks whether A, O |= qT (¯a); the oracle faithfully answers "yes" or "no". In an equivalence query, the learner provides a hypothesis CQ qH and asks whether qH is equivalent to qT under O; the oracle answers "yes" or provides a counterexample, that is, an ABox A and tuple ¯a such that A, O |= qT (¯a) and A, O ̸|= qH(¯a) (positive counterexample) or vice versa (negative counterexample). When we learn a restricted class of CQs such as EL-concepts, we assume that only CQs from that class are admitted in equivalence queries. We are then interested in whether there is a learning algorithm that constructs qT (¯x), up to equivalence under O, such that at any given time, the running time of the algorithm is bounded by a polynomial in the sizes of qT , of O, and of the largest counterexample given by the oracle so far. This is called polynomial time learnability. A weaker requirement is polynomial query learnability where only the sum of the sizes of the queries posed to the oracle up to the current time point has to be bounded by such a polynomial.

Our main results are that the following can be learned in polynomial time under ELr -ontologies: (1) EL-concepts, (2) ELI-concepts that are symmetry-free, and (3) CQs that are chordal, symmetry-free, and of bounded arity. In Point (2), symmetry-freeness means that there is no subconcept of the form ∃r.(C ⊓ ∃r-.D) with r a role name, a condition that has recently been introduced in [Jung et al., 2020], in a slightly less general form where r can also be an inverse role. In Point (3), chordal means that every cycle of length at least four that contains at least one quantified variable has a chord and symmetry-free means that the CQ contains no atoms r(x1, y), r(x2, y) such that x1 ̸= x2, y is a quantified variable, neither r(x1, y) nor r(x2, y) occur on a cycle, and there is no atom s(z, z) for any z ∈ {x1, x2, y}. An analysis of well-known benchmarks for ontology-mediated querying suggests that the resulting class CQ csf of CQs is sufficiently general to include many relevant CQs that occur in practical applications. Our proofs crucially rely on the use of a finite version of the universal model that is specifically tailored to the class CQ csf . We also show that the restriction to bounded arity can be removed from Point (3) when we admit unrestricted CQs as the argument to equivalence queries. Proving this requires very substantial changes to the learning algorithm.

In addition, we prove several negative results. First, we show that none of the classes of CQs in Points (1) to (3) can be learned under EL-ontologies using only membership queries or only equivalence queries (unless P = NP in the latter case). Note that polynomial time learning with only membership queries is important because it is related to whether CQs can be characterized up to equivalence using only polynomially many data examples [ten Cate and Dalmau, 2020]. We also show the much more involved result that none of the classes of CQs in Points (1) to (3) is polynomial query learnable under ELI-ontologies. Note that while polynomial time learnability cannot be expected because subsumption in ELI is EXPTIME-complete, there could well have been a polynomial time learning algorithm with access to an oracle (in the classical sense) for subsumption/query containment under ELI-ontologies that attains polynomial query learnability. Our result rules out this possibility. The appendix with proof details is available in [Funk et al., 2021].

Related work. Learning EL-ontologies, rather than concepts or queries, was studied in [Konev et al., 2018; Konev et al., 2016]. It turns out that EL-ontologies are not polynomial time learnable while certain fragments thereof are. In contrast, we attain polynomial time learnability also under unrestricted EL-ontologies. See also the surveys [Lehmann and V¨olker, 2014; Ozaki, 2020] and [Ozaki et al., 2020] for a variation less related to the current work. It has been shown in [ten Cate et al., 2013; ten Cate et al., 2018] that unions of CQs (UCQs) are polynomial time learnable, and the presented algorithm can be adapted to CQs. Active learning of CQs with only membership queries is considered in [ten Cate and Dalmau, 2020] where among other results it is shown that ELI-concepts can be learned in polynomial time with only membership queries when the ontology is empty. PAC learnability of concepts formulated in the DL CLASSIC, without ontologies, was studied in [Cohen and Hirsh, 1994b; Cohen and Hirsh, 1994a; Frazier and Pitt, 1996].

2 Preliminaries

Concepts and Ontologies. Let NC, NR, and NI be countably infinite sets of concept names, role names, and individual names, respectively. A role R takes the form r or rwhere r is a role name and r- is called an inverse role. If R = s- is an inverse role, then R- denotes the role name s. An ELI-concept is formed according to the syntax rule

where A ranges over NC and R over roles. An EL-concept is an ELI-concept that does not use inverse roles.

An ELI-ontology O is a finite set of concept inclusions (CIs) C ⊑ D where C and D range over ELI-concepts. An ELr -ontology is an ELI-ontology where inverse roles occur only in the form of range restrictions ∃r-.⊤ ⊑ C with C an EL-concept. Note that domain restrictions ∃r.⊤ ⊑ C can be expressed already in EL. An EL-ontology is an ELI-ontology that does not use inverse roles. An ELr -ontology is in normal form if all CIs in it are of one of the forms

where A, A1, A2 are concept names or ⊤. An ABox A 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 that are used in A and may write r-(a, b) in place of r(b, a). An ABox is a ditree if the directed graph (ind(A), {(a, b) | r(a, b) ∈ A}) is a tree and there are no multi-edges, that is, r(a, b), s(a, b) ∈ A implies r = s.

The semantics is defined as usual in terms of interpretations I, which we define to be a (possibly infinite and) nonempty set of concept and role assertions. We use ∆I to denote the set of individual names in I, define AI = {a | A(a) ∈ I} for all A ∈ NC, and rI = {(a, b) | r(a, b) ∈ I} for all r ∈ NR. The extension C I of ELI-concepts C is then defined as usual [Baader et al., 2017]. This definition of interpretation is slightly different from the usual one, but equivalent; its virtue is uniformity as every ABox is a (finite) interpretation. An interpretation I satisfies a CI C ⊑ D if C I ⊆ DI , and a (concept or role) assertion α if α ∈ I or α has the form ⊤(a). We say that I is a model of an ontology/ABox if it satisfies all concept inclusions/assertions in it and write O |= C ⊑ D if every model of the ontology O satisfies the CI C ⊑ D.

A signature is a set of concept and role names, uniformly referred to as symbols. For any syntactic object O such as an ontology or an ABox, we use sig(O) to denote the symbols used in O and ||O|| to denote the size of O, that is, the length of a word representation of O in a suitable alphabet.

CQs and Homomorphisms. A conjunctive query (CQ) takes the form q(¯x) ← ϕ(¯x, ¯ y) where ϕ is a conjunction of concept atoms A(x) and role atoms r(x, y) with A ∈ NC and r ∈ NR. We may write r-(x, y) in place of r(y, x). Note that the tuple ¯x used in the head q(¯x) of the CQ may contain repeated occurrences of variables. When we do not want to make the body ϕ(¯x, ¯ y) explicit, we may denote q(¯x) ← ϕ(¯x, ¯ y) simply with q(¯x). We refer to the variables in ¯x as the answer variables of q. and to the variables in ¯ y as the quantified variables. When we are not interested in order and multiplicity, we treat ¯x and ¯ y as sets of variables. We use var(q) to denote the set of all variables in ¯x and ¯ y. The arity of q is the length of tuple ¯x and q is Boolean if it has arity zero. Every CQ q(¯x) ← ϕ(¯x, ¯ y) gives rise to an ABox (and thus interpretation) Aq obtained from ϕ(¯x, ¯ y) by viewing variables as individual names and atoms as assertions. A CQ is a ditree if Aq is.

A homomorphism h from interpretation I1 to interpretation I2 is a mapping from∆I1 to ∆I2 such that d ∈ AI1 implies h(d) ∈ AI2 and (d, e) ∈ rI1 implies (h(d), h(e)) ∈ rI2 . For ¯ di a tuple over ∆Ii , i ∈ {1, 2}, we write I1, ¯ d1 → I2, ¯ d2 if there is a homomorphism h from I1 to I2 with h( ¯ d1) = ¯ d2. With a homomorphism from a CQ q to an interpretation I, we mean a homomorphism from Aq to I.

Let q(¯x) ← ϕ(¯x, ¯ y) be a CQ and I an interpretation. A tuple ¯ d ∈ (∆I )|¯x| is an answer to q on I, written I |= q( ¯ d), if there is a homomorphism h from q to I with h(¯x) = ¯ d. Now let O be an ELI-ontology and A an ABox. A tuple ¯a ∈ ind(A)|¯x| is an answer to q on A under O, written A,O |= q(¯a) if ¯a is an answer to q on every model of O and A.

For q1 and q2 CQs of the same arity n and O an ELIontology, we say that q1 is contained in q2 under O, written q1 ⊆O q2, if for all ABoxes A and ¯a ∈ ind(A)n , A,O |= q1(¯a) implies A,O |= q2(¯a). We call q1 and q2 equivalent under O, written q1 ≡O q2, if q1 ⊆O q2 and q2 ⊆O q1.

Every ELI-concept can be viewed as a unary tree-shaped CQ in an obvious way. For example, the EL-concept A ⊓ ∃s.⊤⊓∃r.B yields the CQ q(x) ← A(x)∧s(x, y)∧r(x, z)∧ B(z). We use ELQ to denote the class of all EL-concepts viewed as a CQ, and likewise for ELIQ and ELI-concepts.

Important Classes of CQs. We next define a class of CQs that we show later to admit polynomial time learnability under ELr -ontologies, one of the main results of this paper. Let A be an ABox. A path in A from a to b is a sequence p = R0(a0, a1), . . . ,Rn-1(an-1, an) ∈ A, n ≥ 0, such that a0 = a and an = b. We say that p is a cycle of length n if a0 = an, all assertions in p are distinct, and all of a0, . . . , an-1 are distinct. A chord of cycle p is an assertion R(ai, aj) with 0 ≤ i, j < n-1 and i /∈ {j, j-1 mod n, j+1 mod n}. A cycle in a CQ q is a cycle in Aq. With CQ csf , we denote the class of CQs q(¯x) ← ϕ(¯x, ¯ y) that are

1. chordal, that is, every cycle R0(x0, x1), . . . , Rn-2(xn-2, xn-1) in q of length at least four that contains at least one quantified variable has a chord;
2. symmetry-free, that is, if ϕ contains atoms r(y1, x), r(y2, x) with y1 ̸= y2, then x is an answer variable or one of the atoms occurs on a cycle or ϕ contains an atom s(z, z) for some z ∈ {x, y1, y2}.

In Point 2, r is a role name and thus there are no restrictions on 'inverse symmetries': ϕ may contain atoms r(x, y1), r(x, y2) with x a quantified variable and none of the atoms occurring on a cycle and no reflexive loops present. Note that CQ csf contains all CQs without quantified variables

(also called full CQs), all ELQs, and all ELIQs obtained from ELI-concepts that are symmetry-free, that is, that do not contain a subconcept of the form ∃r.(C ⊓ ∃r-.D) with r a role name. We denote the latter class with ELIQ sf . CQ csf also includes all CQs obtained from such ELIQs by choosing a set of variables and making them answer variables. Note that CQs fromCQ csf need not be connected, in fact CQ csf is closed under disjoint union. Every CQ whose graph is a clique or a k-tree (a maximal graph of treewidth k) with k > 1 is in CQ csf . Some concrete examples for CQs in CQ csf are given below, filled circles indicating answer variables:

We believe that CQ csf includes many relevant CQs that occur in practical applications. To substantiate this, we have analyzed the 65 queries that are part of three widely used benchmarks for ontology-mediated querying, namely Fishmark, LUBM∃ , and NPD [Bail et al., 2012; Lutz et al., 2013; Lanti et al., 2015]. We found that more than 85% of the queries fall into CQ csf while less than 5% fall into ELIQ sf .

Universal Models. Let A be an ABox and O an ELr - ontology. The universal model of A and O, denoted UA,O, is the interpretation obtained by starting with A and then 'chasing' with the CIs in the ontology which adds (potentially infinite) ditrees below every a ∈ ind(A). The formal definition is in the appendix. The model is universal in that UA,O |= q(¯a) iff A, O |= q(¯a) for all CQs q(¯x) and tuples ¯a ∈ ind(A)|¯x| . It can be useful to represent universal models in a finite way, as for example in the combined approach to ontology-mediated querying [Lutz et al., 2009]. Here, we introduce a finite representation that is tailored towards our class CQ csf .

The 3-compact model C 3A,O of A and O is defined as follows. Let sub(O) be the set of all concepts in O, closed under subconcepts. C 3A,O uses the individual names fromA as well as individual names of the form ca,i,r,C where a ∈ ind(A), 0 ≤ i ≤ 4, r is a role name from O, and C ∈ sub(O). For every role name r, we use Cr to denote the conjunction over all C such that ∃r-.⊤ ⊑ C ∈ O, and ⊤ if the conjunction is empty. Let i ⊕ 1 be short for (i mod 4) + 1. Define

There is a homomorphism from UA,O to C 3A,O that is the identity on ind(A), but in general not vice versa. Nevertheless, C 3A,O is universal for CQ csf .

Lemma 1. Let A be an ABox and O an ELr -ontology. Then C 3A,O is a model of A and O such that for every CQ q(¯x) ∈ CQcsf and ¯a ∈ ind(A)|¯x| , C 3A,O |= q(¯a) iff A,O |= q(¯a).

C 3A,O is defined so as to avoid spurious cycles of length at most 3 while larger spurious cycles are irrelevant for CQs that are chordal. This explains the superscript ·3 and enables the lemma below. C 3A,O also avoids spurious predecessors connected via different role names. Spurious predecessors connected via the same role name cannot be avoided, but are irrelevant for CQs that are symmetry-free.

Lemma 2. Every cycle in C 3A,O of length at most three consists only of individuals from ind(A).

We also use the direct product I1 × I2 of interpretations I1 and I2, defined in the standard way (see appendix). For tuples of individuals ¯ai = (ai,1, . . . , ai,n), i ∈ {1, 2}, we set ¯a1 ⊗ ¯a2 = ((a1,1, a2,1), . . . , (a1,n, a2,n)).

3 Learning under ELr -Ontologies

We establish polynomial time learnability results under ELr - ontologies for the query classes CQ csf , ELQ, and ELIQ sf . For CQ csf , we additionally have to assume that the arity of CQs to be learned is bounded by a constant or that unrestricted CQs can be used in equivalence queries. When speaking of equivalence queries, we generally imply that the CQs used in such queries must be from the class of CQs to be learned. If this is not the case and unrestricted CQs are admitted in equivalence queries, then we speak of CQ-equivalence queries. When using CQ-equivalence queries, the learned representation of the target query is a CQ, but need not necessarily belong to C (though it is equivalent to a query from C). For w ≥ 0, let CQ csf w be the restriction of CQ csf to CQs of arity at most w. The following are the main results obtained in this section.

Theorem 1.

1. ELQ- and ELIQ sf -queries are polynomial time learnable under ELr -ontologies using membership and equivalence queries;
2. for every w ≥ 0, CQ csf w -queries are polynomial time learnable under ELr -ontologies using membership and equivalence queries;
3. CQ csf -queries are polynomial time learnable under ELr -ontologies using membership and CQ-equivalence queries.

Before providing a proof of Theorem 1, we show that both membership and equivalence queries are needed for polynomial learnability. Let AQ∧ denote the class of unary CQs of the form q(x) ← A1(x) ∧ · · · ∧ An(x), and let a conjunctive ontology be an EL-ontology without role names.

Theorem 2.

1. AQ∧-queries are not polynomial query learnable under conjunctive ontologies using only membership queries;
2. ELQ-queries are not polynomial time learnable (without ontologies) using only CQ-equivalence queries unless P = NP.

Note that Points 1 and 2 of Theorem 2 imply the same statements for all relevant query classes, that is, ELQ, ELIQ sf , CQ csf , CQ csf w for all w ≥ 1, and CQ, in place of the classes mentioned in the theorem. In particular, Point 2 implies that Algorithm 1 Learning queries qT from ELQ / ELIQ sf / CQ csf w under an ELr -ontology O.

procedure LEARNCQ qH(¯x) := refine(q⊥(¯x0)) while qH ̸≡O qT (equivalence query) do Let A, ¯a be the positive counterexample returned and let q′H (¯x′ ) be C 3AqH ,O × C 3A,O viewed as a CQ with answer variables ¯x′ = ¯x ⊗ ¯a qH(¯x) := refine(q′H (¯x′ )) return qH(¯x)

unrestricted CQs are not polynomial time learnable with only equivalence queries in the classical setting (without ontologies) unless P = NP, even when only unary and binary relations are admitted, see [Cohen, 1995; Haussler, 1989; Hirata, 2000] for related results. The proof of Point 1 follows basic lower bound proofs for abstract learning problems [Angluin, 1987b]. Point 2 is proved by exploiting connections between active learning and inseparability questions studied in [Funk et al., 2019; Jung et al., 2020; Funk, 2019].

3.1 Reduction to Normal Form

We show that the ontology under which we learn can w.l.o.g. be assumed to be in normal form. It is well-known that every ELr -ontology O can be converted into normal form by introducing fresh concept names [Baader et al., 2017]. We use such a conversion to show that, for the relevant classes of CQs, a polynomial time learning algorithm under ELr - ontologies in normal form can be converted into a polynomial time learning algorithm under unrestricted ELr -ontologies. Care has to be exercised as the fresh concept names can occur in membership and equivalence queries. From now on, we thus assume that ontologies are in normal form.

Proposition 1. Let Q ∈ {ELQ, ELIQ sf , CQ csf w | w ≥ 0}. If queries in Q are polynomial time learnable under ELr - ontologies in normal form using membership and equivalence queries, then the same is true for unrestricted ELr -ontologies.

3.2 AlgorithmOverview

We start with proving Points 1 and 2 of Theorem 1. Thus let Q ∈ {ELQ, ELIQ sf , CQ csf w | w ≥ 0}. The algorithm that establishes polynomial time learnability of queries from Q under ELr -ontologies is displayed as Algorithm 1. We next explain some of its details.

Let O be an ELr -ontology, Σ a finite signature that contains all symbols in O, and ar ≤ w an arity for the query to be learned with ar = 1 if Q ∈ {ELQ, ELIQ sf}, all known to the learner and the oracle. Further let qT (¯ y) ∈ Q be the target query known to the oracle, formulated in signature Σ. The algorithm maintains and repeatedly updates a hypothesis CQ qH(¯x) of arity ar. It starts with the hypothesis

where ¯x0 contains only the variable x0, repeated ar times. By construction, q⊥ ⊆O q for all CQs q of arity ar that use only symbols from Σ. Note that q⊥ ∈ CQ csf w for all w, but q⊥ is neither in ELQ nor in ELIQ sf .

If q1(¯x1), q2(¯x2), . . . are the hypotheses constructed during a run of the algorithm, then for all i ≥ 1:

1. qi ∈ Q and qi ⊆O qT ;
2. qi ⊆O qi+1 and qi ̸≡O qi+1;
3. |var(qi)| ≤ |var(qT )|.

Taken together, Points 1 and 2 mean that the hypotheses approximate the target query from below in an increasingly better way and Point 3 is crucial for proving that we must reach qT after polynomially many steps. The fact that O is in normal form is used to attain Point 3.

Point 1 also guarantees that the oracle always returns a positive counterexample A, ¯a to the equivalence query used to check whether qH ̸≡O qT in the while loop. The algorithm extracts the commonalities of qH(¯x) and A, ¯a by means of a direct product with the aim of obtaining a better approximation of the target. The same is done in the case without ontologies [ten Cate et al., 2013] where AqH × A (viewed as a CQ) is the new hypothesis, but this is not sufficient here as it misses the impact of the ontology. The product UAqH ,O × UA,O would work, but need not be finite. So we resort to C 3AqH ,O×C 3A,O instead, viewed as a CQ q′H (¯x′ ). This new hypothesis need not belong to Q, so we call the subroutine refine detailed in the subsequent section to convert it into a new hypothesis qH(¯x) ∈ Q such that q′H ⊆O qH ⊆O qT . The initial call to refine serves the same purpose as q⊥(¯x0) need not be in Q, depending on the choice of Q.

It is not immediately clear that the described approach achieves the containment in Point 2 since C 3AqH ,O × C 3A,O is potentially too strong as a replacement of UAqH ,O ×UA,O; in particular, there might be cycles in the former product that do not exist in the latter. What saves us, however, is that the CQ qH constructed by refine belongs to Q while the models C 3AqH ,O and C 3A,O are universal for Q as per Lemma 1.

3.3 The refine Subroutine

The refine subroutine gets as input a CQ q′H (¯x′ ) that does not need to be in Q, but that satisfies q′H ⊆O qT . It produces a query qH(¯x) from Q such that q′H ⊆O qH ⊆O qT and |var(qH)| ≤ |var(qT )|. For notational convenience, we prefer to view q′H (¯x′ ) as a pair (A, ¯a) where A = Aq′H and ¯a = ¯x′ . Let nmax denote the maximum length of a chordless cycle in any query in Q, that is nmax = 0 for Q ∈ {ELQ, ELIQ sf} and nmax = 3 for Q = CQ csf w , w ≥ 0. We shall use the following.

Minimize. Let B be an ABox and ¯b a tuple such that B, O |= qT (¯b). Then minimize(B, ¯b) is the ABox B′ obtained from B by exhaustively applying the following operations:

(1) choose c ∈ ind(B) \ ¯b and remove all assertions that involve c. Use a membership query to check whether, for the resulting ABox B-, B-, O |= qT (¯b). If so, proceed with Bin place of B.

(2) choose r(a, b) ∈ B and use a membership query to check whether B \ {r(a, b)},O |= qT (¯b). If so, proceed with B \ {r(a, b)} in place of B.

The refine subroutine builds a sequence (B1, ¯b1), (B2, ¯b2), . . . starting with (B1,¯b1) = (minimize(A, ¯a), ¯a) and exhaustively applying the following step:

Expand. Choose a chordless cycle R0(a0, a1), . . . , Rn-1(an-1, an) in Bi with n > nmax and, in case that Q = CQ csf w , {a0, . . . , an-1} ̸⊆ ¯bi. 1 Let B′i be the ABox obtained by doubling the length of the cycle: start with Bi, introduce copies a′0 , . . . , a′n-1 of a0, . . . , an-1, and then

• remove all assertions R(an-1, a0);
• add B(a′i ) if B(ai) ∈ Bi;
• add R(a′i , c) if R(ai, c) ∈ Bi with 0 ≤ i < n and c ∈ ind(Bi) \ {a0, . . . , an-1};
• add R(a′i , a′j ) if R(ai, aj) ∈ Bi with 0 ≤ i, j < n and {i, j} ̸= {0, n - 1};
• add R(an-1, a′0 ) and R(a′n-1 , a0) if R(an-1, a0) ∈ Bi.

A similar construction is used in [Konev et al., 2016]. Let τi be the set of tuples ¯b obtained from ¯bi = (b1, . . . , bk) by replacing any number of components bj by b′j . Use membership queries to identify ¯bi+1 ∈ τi with B′i ,O |= qT (¯bi+1) and set Bi+1 = minimize(B′i ,¯bi+1). We prove in the appendix that such a ¯bi+1 always exists and that the Expand step can only be applied polynomially many times. The resulting (Bn, ¯bn) viewed as a CQ with answer variables ¯bn is chordal, but not necessarily symmetry-free. To establish also the latter, we compute a sequence of ABoxes Bn, Bn+1, . . . by exhaustively applying the following step:

Split. Choose r(a, b), r(c, b) ∈ Bi such that b /∈ ¯bn and neither r(a, b) nor r(c, b) occurs on a cycle. Construct B′i by removing r(a, b) from Bi, taking a fresh individual b′ , and adding B(b′ ) for all B(b) ∈ Bi and S(d, b′ ) for all S(d, b) ∈ Bi with S(d, b) ̸= r(c, b). If B′i ,O |= qT (¯bn), then Bi+1 = minimize(B′i , ¯bn).

We prove in the appendix that only polynomially many applications are possible and that, for Bm the resulting ABox, (B′m,¯bn) viewed as a CQ is chordal and symmetry-free. Moreover, it is in ELQ if qT is, and likewise for ELIQ sf . Refine returns this CQ as its result. Note that the running time of refine depends exponentially on ar due to the brute force search for a tuple ¯bi+1 ∈ τi in the Expand step.

3.4 Unbounded Arity

To prove the remaining Point 3 of Theorem 1, we have to deal with CQs of unbounded arity and cannot use the refine subroutine presented in Section 3.3. We thus introduce a second version of refine that works rather differently from the previous one. We give an informal description, full details are in the appendix.

Recall that refinement starts with the product P = C 3AqH ,O × C 3A,O . In Section 3.3, we blow up cycles in P, not distinguishing the ABox part and the existentially generated part of the 3-compact models involved. The second version of refine instead unravels the existentially generated part of the two 3-compact models inside the product P . A full such unraveling would eventually result in UAqH ,O × UA,O, but we interleave with a Minimize step as in Section 3.3 and thus obtain a finite initial piece thereof. Unlike in the previous version of refine, we do not have to redefine the answer variables at all (but note that they may still change outside of refine when we take the product).

1 This is because CQ csf admits cycles that consist only of answer variables while ELQ and ELIQ sf do not.

The above suffices for target CQs from CQ csf in which every variable is reachable from an answer variable. In the general case, disconnected Boolean components might be present (or emerge during unraveling and minimization) that are never unraveled. To address this, we subsequently apply the original version of refine to such components, avoiding the Splitting step and leaving the already unraveled parts untouched. Note that the exponential blowup in the arity is avoided because the original refine is only applied to Boolean subqueries. However, the resulting queries are not guaranteed to be in CQ csf . We can thus not rely on Lemma 1 as before which is why we need CQ-equivalence queries.

4 Learning under ELI-Ontologies

When we replace ELr -ontologies with ELI-ontologies, polynomial time learnability can no longer be expected since containment between ELQs under ELI-ontologies is EXPTIMEcomplete [Baader et al., 2008]. In contrast, polynomial query learnability is not ruled out and in fact it is natural to ask whether there is a polynomial time learning algorithm with access to an oracle (in the classical sense) for query containment under ELI-ontologies. Note that such an algorithm would show polynomial query learnability. We answer this question to the negative and show that polynomial query learnability cannot be attained under ELI-ontologies for any of the query classes considered in this paper. This is a consequence of the following result, which also captures learning of unrestricted CQs.

Theorem 3. EL-concepts are not polynomial query learnable under ELI-ontologies with membership queries and CQ-equivalence queries.

For the proof, we use the ELI-ontologies On, n ≥ 1, given in Figure 1. There, r = s and s = r. Every On is associated with a set Hn of 2n potential target concepts of the form

where ∃rn denotes the n-fold nesting of ∃r. The idea of the proof is to show that if there was an algorithm for learning EL-concepts under ELI-ontologies such that, at any given time, the sum of the sizes of all (membership and CQequivalence) queries asked to the oracle is bounded by a polynomial p(n1, n2, n3) with n1 is the size of the target query, n2 is the size of the ontology, and n3 is the size of the largest counterexample seen so far, then we can choose n large enough so that the learner needs more than p(n1, n2, n3) queries to distinguish the targets in Hn under On if the oracle uses a 'sufficiently destructive' strategy to answer the queries. Such a strategy is presented in the appendix, we only give one example that highlights a crucial aspect.

Assume that the learner poses as an equivalence query the EL-concept CH = ∃σ1 · · · ∃σn.∃rn .A. Then the

Figure 1: ELI-ontology On

oracle returns "no" and positive counterexample A = {K0(a0), W σ1 1 (a0), . . . ,W σn n (a0)}. It is instructive to verify that A,O |= C ′H (a0) for all C ′H ∈ Hn \ {CH} while A,O ̸|= CH(a0) as this illustrates the use of inverse roles in On.

5 Conclusion

We conjecture that our results can be extended from ELr - ontologies to ELHr -ontologies, thus adding role inclusions. In contrast, we do not know how to learn in polynomial time unrestricted ELI-concepts under EL-ontologies, or symmetry-free CQs under EL-ontologies. We would not be surprised if these indeed turn out not to be learnable in polynomial time. It is an interesting question whether our results can be generalized to symmetry-free CQs that admit chordless cycles of length bounded by a constant larger than three. This would require the use of a different kind of compact universal model.

Acknowledgements

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