Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies

1 Introduction

In the widely studied paradigm of ontology-mediated querying, a database query is enriched with an ontology that provides domain knowledge as well as additional vocabulary for query formulation [Bienvenu et al., 2013b; Calvanese et al., 2009]. We consider ontologies formulated in description logics (DLs) of the DL-Lite family and queries that are ELI queries (ELIQs) or, in other words, tree-shaped unary conjunctive queries (CQs). DL-Lite is a prominent choice for the ontology language as it underpins the OWL 2 QL profile of the OWL ontology language [OWL Working Group, 2009]. Likewise, ELIQs are a prominent choice for the query language as they are computationally very well-behaved: without an ontology, they can be evaluated in polynomial time in combined complexity, in contrast to NP-completeness for unrestricted CQs. Moreover, in the form of ELI concepts they are a central building block of ontologies in several dialects of DL-Lite and beyond.

The aim of this paper is to study the related topics of computing least general generalizations (LGGs) of ELIQs under DL-Lite ontologies and learning ELIQs under DLLite ontologies in Angluin's framework of exact learning [Angluin, 1987a; Angluin, 1987b]. Computing generalizations is a natural operation in query engineering that plays a crucial role in learning logical formulas [Plotkin, 1970; Muggleton, 1991], in particular in exact learning [ten Cate andDalmau, 2021]. Exact learning, in turn, is concernedwith constructing queries and ontologies. This can be challenging and costly, especially when logic expertise and domain knowledge are not in the same hands. Aiming at such cases, exact learning provides a systematic protocol for query engineering in which a learner interacts in a game-like fashion with an oracle, which may be a domain expert.

Our results on LGGs concern the notion of a frontier of an ELIQ q w.r.t. an ontology O. Such a frontier is a set F of ELIQs that generalize q, that is, q ⊆O qF and qF ̸⊆O q for all qF ∈ F, where '⊆O' denotes query containment w.r.t. O. Moreover, F must be complete in that for all ELIQs q′ with q ⊆O q′ and q′ ̸⊆O q, there is a qF ∈ F such that qF ⊆O q′ . We are interested in computing a frontier that contains only polynomially many ELIQs of polynomial size, in polynomial time. This is possible in the case of ELIQs without ontologies as shown in [ten Cate and Dalmau, 2021]; for the simpler EL queries, the same had been observed earlier (also without ontologies) in [Baader et al., 2018; Kriegel, 2019]. In contrast, unrestricted CQs do not even admit finite frontiers [Nesetril and Tardif, 2000].

In exact learning, the learner and the oracle know and agree on the ontology O, and they also agree on the target query qT to use only concept and role names from O. The learner may ask membership queries where they produce an ABox A and a candidate answer a and ask whether A,O |= qT (a), that is, whether a is an answer to qT w.r.t. O on A. The oracle faithfully answers "yes" or "no". Polynomial time learnability then means that the learner has an algorithm for constructing qT , up to equivalence w.r.t. O, with running time bounded by a polynomial in the sizes of qT and O.

Learning with only membership queries, as described above and studied in this article, is a strong form of exact learning. In fact, there are not many cases where polynomial time learning with only membership queries is possible, ELIQs without ontologies being an important example [ten Cate and Dalmau, 2021]. Often, one would therefore also admit equivalence queries where the learner provides a hypothesis ELIQ 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 answer a such that A, O |= qT (a) and A,O ̸|= qH(a) or vice versa. This is done, for instance, in [Konev et al., 2018; Funk et al., 2021].

We consider as ontology languages the DLs DL-LiteH and DL-LiteF , equipped with role inclusions (also known as role hierarchies) and functional roles, respectively. Both dialects admit concept and role disjointness constraints and ELI concepts on the right-hand side of concept inclusions [Calvanese et al., 2007; Kikot et al., 2011]. We show that DL-LiteH admits polynomial frontiers that can be computed in polynomial time, and that DL-LiteF does not even admit finite frontiers. We then introduce a fragment DL-LiteF- of DL-LiteF that restricts the use of inverse functional roles on the right-hand side of concept inclusions and show that it is as well-behaved as DL-LiteH. Both frontier constructions require a rather subtle analysis. We also note that adding conjunction results in frontiers of exponential size, even for very simple fragments of DL-Lite. One application of our results is to show that every ELIQ q can be characterized up to equivalence w.r.t. ontologies formulated in DL-LiteH or DL-LiteF- by only polynomially many data examples of the form (A, a), labeled as positive if A, O |= q(a) and as negative otherwise.

We then consider in detail the application of our results in the context of exact learning and show that ELIQs can be learned in polynomial time w.r.t. ontologies O formulated in DL-LiteH or DL-LiteF-. The learning algorithm uses only membership queries provided that a seed query is available, that is, an ELIQ q0 such that q0 ⊆O qT . Such a seed query can be constructed using membership queries if O contains no concept disjointness constraints and obtained by a single initial equivalence query otherwise. We also show that ELIQs cannot be learned at all w.r.t. unrestricted DL-LiteF ontologies using only membership queries, and that they cannot be learned with only polynomially many membership queries when conjunction is admitted.

Proof details are given in the long version [Funk et al., 2022].

Related Work. Exact learning of queries in the context of description logics has been studied in [Funk et al., 2021] while [Konev et al., 2018] considers learning entire ontologies, see also [Ozaki et al., 2020; Ozaki, 2020]. It is shown in [Funk et al., 2021] that a restricted form of CQs (that do not encompass all ELIQs) can be learned in polynomial time under EL ontologies using both membership and equivalence queries. The results from that paper indicate that inverse roles provide a challenge for exact learning under ontologies and thus it is remarkable that we can handle them without any restrictions in our context. Related forms of learning are the construction of the least common subsumer (LCS) and the most specific concept (MSC) [Baader, 2003; Baader et al., 1999; Baader et al., 2007; Jung et al., 2020b; Zarrieß and Turhan, 2013] which may both be viewed as a form of query generalization. There is also a more loosely related research thread on learning DL concepts from labeled data examples [Funk et al., 2019; Jung et al., 2020a; Lehmann and Hitzler, 2010; Lehmann and V¨olker, 2014; Sarker and Hitzler, 2019].

2 Preliminaries

Ontologies and ABoxes. Let NC, NR, and NI be countably infinite sets of concept, role, and individual names. A role R

is a role name r ∈ NR or the inverse r- of a role name r. An ELI concept is formed according to the syntax rule C,D ::= ⊤ | A | C ⊓ D | ∃R.C where A ranges over concept names and R over roles. A basic concept B is an ELI concept of the form ⊤, A, or ∃R.⊤. When dealing with basic concepts, for brevity we may write ∃R in place of ∃R.⊤.

A DL-LiteHF ontology O is a finite set of concept inclusions (CIs) B ⊑ C, role inclusions (RIs) R1 ⊑ R2, concept disjointness constraints B1 ⊓ B2 ⊑ ⊥, role disjointness constraints R1 ⊓ R2 ⊑ ⊥, and functionality assertions func(R). Here, B, B1, and B2 range over basic concepts, C over ELI concepts, and R1,R2,R over roles. Superscript ·H indicates the presence of role inclusions (also called role hierarchies) and superscript ·F indicates functionality assertions, and thus it should be clear what we mean with a DL-LiteH ontology and with a DL-LiteF ontology. In fact, we are mainly interested in these two fragments of DL-LiteHF .

A DL-LiteHF ontology is in normal form if all concept inclusions in it are of one of the forms A ⊑ B, B ⊑ A, and A ⊑ ∃R.A′ with A,A′ concept names or ⊤ and B a basic concept. Note that CIs of the form ∃R ⊑ ∃S are not admitted and neither are CIs of the form A ⊑ ∃R.C with C a compound concept. An ABox A is a finite set of concept assertions A(a) and role assertions r(a, b) with A a concept name or ⊤, r a role name, and a, b individual names. We use ind(A) to denote the set of individual names used in A.

As usual, the semantics is given 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} and (r-)I = {(b, a) | r(a, b) ∈ I} for all r ∈ NR. This definition of interpretation is slightly different from the usual one, but equivalent; 1 its virtue is uniformity as every ABox is a finite interpretation. The interpretation function ·I can be extended from concept names to ELI concepts in the standard way [Baader et al., 2017]. An interpretation I satisfies a concept or role inclusion α1 ⊑ α2 if αI 1 ⊆ αI 2 , a concept or role disjointness constraint α1 ⊓ α2 ⊑ ⊥ if αI 1 ∩ αI 2 = ∅, and a functionality assertion func(R) if RI is a partial function. It satisfies a concept or role assertion α if α ∈ I. Note that, as usual, we thus make the standard names assumption, implying the unique name assumption.

An interpretation is a model of an ontology or an ABox if it satisfies all inclusions, disjointness constraints, and assertions in it. We write O |= α1 ⊑ α2 if every model of the ontology O satisfies the concept or role inclusion α1 ⊑ α2 and O |= α1 ≡ α2 if O |= α1 ⊑ α2 and O |= α2 ⊑ α1. If α1 and α2 are basic concepts or roles, then such consequences are decidable in PTIME both in DL-LiteH and in DL-LiteF [Artale et al., 2009]. An ABox A is satisfiable w.r.t. an ontology O if A and O have a common model. Deciding ABox satisfiability is also in PTIME in both DL-LiteH and DL-LiteF .

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 representation of O as a word in a suitable alphabet.

1 This depends on admitting assertions ⊤(a) in ABoxes.

Queries. An ELI concept C can be viewed as an ELI query (ELIQ). An individual a ∈ ind(A) is an answer to C on an ABox A w.r.t. an ontology O, written A, O |= C(a), if a ∈ C I for all models I of A and O. We shall often view ELIQs as unary conjunctive queries (CQs) and also consider CQs that are not ELIQs. In this paper, CQs are always unary. A CQ thus takes the form q(x0) = ∃¯ y ϕ(x0, ¯ y) with ϕ a conjunction of concept atoms A(x) and role atoms r(x, y) where A ∈ NC and r ∈ NR. We use var(q) to denote the set of variables that occur in q. We may view q as a set of atoms and may write r-(x, y) in place of r(y, x). We call x0 the answer variable and use the notion of an answer and the notation A,O |= q(a) also for CQs. The formal definition is in terms of homomorphisms as usual, details are in the long version. ELIQs are in 1to-1 correspondence with CQs whose Gaifman graph is a tree and that contain no self-loops and multi-edges. For example, the ELIQ C = A ⊓ ∃r-.(∃s.B ⊓ ∃r.A) is the CQ q(x0) = {A(x), r(y, x), s(y, z),B(z), r(y, z′ ),A(z′ )}. We use Aq to denote the ABox obtained from CQ q by viewing variables as individuals and atoms as assertions. A CQ q is satisfiable w.r.t. ontology O if Aq is.

For CQs q1 and q2 and an ontology O, we say that q1 is contained in q2 w.r.t. O, written q1 ⊆O q2 if for all ABoxes A and a ∈ ind(A), A,O |= q1(a) implies A,O |= q2(a). If q1, q2 are ELIQs, then this coincides with q1 viewed as ELI concept being subsumed w.r.t. O by q2 viewed as an ELI concept [Baader et al., 2017]. We call q1 and q2 equivalent w.r.t. O, written q1 ≡O q2, if q1 ⊆O q2 and q2 ⊆O q1.

O-saturatedness and O-minimality. A CQ q is Osaturated, with O an ontology, if Aq,O |= A(y) implies A(y) ∈ q for all y ∈ var(q) and A ∈ NC. It is O-minimal if there is no x ∈ var(q) such that q ≡O q|var(q)\{x} with q|S the restriction of q to the atoms that only contain variables in S. For a CQ q and an ontology O formulated in DL-LiteH or DL-LiteF , one can easily find in polynomial time an O-saturated CQ q′ with q ≡O q′ . To achieve Ominimality, we may repeatedly choose variables x ∈ var(q), check whether Aq|var(q)\{x} ,O |= q, and if so replace q with q|var(q)\{x}. For ELIQs, the required checks can be carried out in PTIME in DL-LiteF [Bienvenu et al., 2013a], but are NP-complete in DL-LiteH [Kikot et al., 2011]. We conjecture that in DL-LiteH, it is not possible to construct equivalent O-minimal ELIQs in polynomial time.

3 Frontiers in DL-LiteH

We show that for every ELIQ q and DL-LiteH ontology O such that q is satisfiable w.r.t. O, there is a frontier of polynomial size that can be computed in polynomial time. We also observe that this fails when DL-LiteH is extended with conjunction, even in very restricted cases.

Definition 1. A frontier of an ELIQ q w.r.t. a DL-LiteHF ontology O is a set of ELIQs F such that

1. q ⊆O qF for all qF ∈ F;
2. qF ̸⊆O q for all qF ∈ F;
3. for all ELIQs q′ with q ⊆O q′ ̸⊆O q, there is a qF ∈ F with qF ⊆O q′ .

It is not hard to see that finite frontiers that are minimal w.r.t. set inclusion are unique up to equivalence of the ELIQs in them, that is, if F1 and F2 are finite minimal frontiers of q w.r.t. O, then for every qF ∈ F1 there is a q′F ∈ F2 such that qF ≡O q′F and vice versa. The following is the main result of this section.

Theorem 1. Let O be a DL-LiteH ontology and q an ELIQ that is O-minimal and satisfiable w.r.t. O. Then a frontier of q w.r.t. O can be computed in polynomial time.

We note that Theorem 1 still holds when O-minimality is dropped as a precondition and Condition 2 of frontiers is dropped as well. For proving Theorem 1, we first observe that we can concentrate on ontologies that are in normal form.

Lemma 1. For everyDL-LiteH ontologyO, we can construct in polynomial time a DL-LiteH ontology O′ in normal form such that every O-minimal ELIQ q is also O′ -minimal and a frontier of q w.r.t. O can be constructed in polynomial time given a frontier of q w.r.t. O′ .

We now prove Theorem 1, adapting and generalizing a technique from [ten Cate and Dalmau, 2021]. Let O and q(x0) be as in the formulation of the theorem, with O in normal form. We may assume w.l.o.g. that q is O-saturated. To construct a frontier of q w.r.t. O, we consider all ways to generalize q in a least general way where 'generalizing' means to construct from q an ELIQ q′ such that q ⊆O q′ and q′ ̸⊆O q and 'least general way' that there is no ELIQ ̂ q that generalizes q and satisfies ̂ q ⊆O q′ and q′ ̸⊆O ̂ q. We do this in two steps: the actual generalization plus a compensation step, the latter being needed to guarantee that we indeed arrive at a least general generalization.

For x ∈ var(q), we use qx to denote the ELIQ obtained from q by taking the subtree of q rooted at x and making x the answer variable. The construction that follows involves the introduction of fresh variables x, some of which are a 'copy' of a variable from var(q). We then use x↓ to denote that original variable.

Step 1: Generalize. For each variable x ∈ var(q), define a set F0(x) that contains all ELIQs which can be obtained by starting with qx(x) and then doing one of the following:

• (A) Drop concept atom:
• choose an atomA(x) ∈ q such that
• (a) there is no B(x) ∈ q with O |= B ⊑ A and O ̸|= A ⊑ B and
• (b) there is no R(x, y) ∈ q with O |= ∃R ⊑ A;
• remove all B(x) ∈ q withO |= A ≡ B, includingA(x).
• (B) Generalize subquery:
• choose an atomR(x, y) ∈ q directed away from x0;
• remove R(x, y) and all atoms of qy;
• for each q′ (y) ∈ F0(y), add a disjoint copy ̂ q′ of q′ and the role atom R(x, y′′ ) with y′′ the copy of y in ̂ q′ ;

4. for every role S with O |= R ⊑ S and O ̸|= S ⊑ R, add a disjoint copy ̂ qy of qy and the role atom S(x, y′ ) with y′ the copy of y in ̂ qy .

The definition of x↓ should be clear in all cases. In Point 3 of Case (B), for example, for every variable z in q′ that was renamed to z′ in ̂ q′ set z′↓ = z↓ . Note that z↓ is defined for all variables z that occur in queries in F0(x). Also note that, in Point 1b of (A), it is important to use q rather than qx as y could be a predecessor of x in q.

Step 2: Compensate. We construct a frontier F of q(x0) by including, for each p ∈ F0(x0), the ELIQ obtained from p by the following two steps. We write x ⇝Rq,O A if Aq, O |= ∃R.A(x) and there is no S(x, y) ∈ q with O |= S ⊑ R and Aq , O |= A(y).

Step 2A. Consider all x ∈ var(p), roles R, S, and concept names A such that x↓ ⇝Rq,O A, O |= R ⊑ S, and O |= ∃S ⊑ B implies B(x) ∈ p for all concept names B. Add the atoms S(x, z),A(z),R(x′ , z) where z and x′ are fresh variables with z↓ undefined, x′↓ = x↓ , and add a disjoint copy ̂ q of q, glue the copy of x↓ in ̂ q to x′ .

Step 2B. Consider every S(x, y) ∈ p directed away from x0 that was not added in Step 2A. Then x↓ and y↓ are defined. For every role R with Aq,O |= R(x↓ , y↓ ), add an atom R(z, y), z a fresh variable with z↓ = x↓ , as well as a disjoint copy ̂ q of q and glue the copy of x↓ in ̂ q to z.

This finishes the construction of the frontier F of q.

Example 1. Consider the DL-LiteH ontology O = {A ⊑ ∃r, ∃r ⊑ A, r ⊑ s} and the ELIQ q(x0) = A(x0) ∧B(x0). Then F contains the ELIQs p1 and p2 shown below:

ELIQ p1 is the result of dropping the concept atom A(x0) and p2 is the result of dropping the concept atomB(x0). Step 2A adds an r-successor and an s-successor of x0 in p2 but only an s-successor in p1 as O |= ∃r ⊑ A, and then attaches copies of q. Step 2B does nothing, as all role atoms have been added in Step 2A. 2

Example 2. Consider the DL-LiteH ontology O = {r ⊑ s} and the ELIQ q(x0) shown on the left-hand side below:

Then F contains only the ELIQ p shown on the right-hand side. It is the result of dropping the concept atomA(y) in qy, then generalizing the subquery r(x0, y) in qx0 = q, and then compensating. Step 2A of compensation adds nothing. Step 2B adds the two dashed role atoms and attaches copies of q to x1 and x2.

2 Variables x2 and z2 can be dropped from p2 resulting in an ELIQ that is equivalent w.r.t. O. We did not include such optimizations in the compensation step to avoid making it more complicated.

Lemma 2. F is a frontier of q(x0) w.r.t. O.

We next show that the constructed frontier is of polynomial size and that its computation takes only polynomial time.

We next observe that adding conjunction to DL-Lite destroys polynomial frontiers and thus Theorem 1 does not apply to DL-Litehorn ontologies [Artale et al., 2009]. In fact, this already holds for very simple queries and ontologies, implying that also for other DLs that support conjunction such as EL, polynomial frontiers are elusive. A conjunction of atomic queries (AQ∧) is a unary CQ of the form q(x0) = A1(x0) ∧ · · · ∧ An(x0) and a conjunctive ontology is a set of CIs of the form A1 ⊓ · · · ⊓ An ⊑ A where A1, . . . , An and A are concept names.

Theorem 2. There are families of AQ∧s q1, q2, . . . and conjunctive ontologies O1,O2, . . . such that for all n ≥ 1, any frontier of qn w.r.t. On has size at least 2n .

4 Frontiers in DL-LiteF

We start by observing that frontiers of ELIQs w.r.t. DL-LiteF ontologies may be infinite. This leads us to identifying a syntactic restriction on DL-LiteF ontologies that regains finite frontiers. In fact, we show that they are of polynomial size and can be computed in polynomial time.

Theorem 3. There is an ELIQ q and a DL-LiteF ontology O such that q does not have a finite frontier w.r.t. O.

In the proof of Theorem 3, we use the ELIQ A(x) and

The universal model Uq,O of Aq and O is an infinite r-path on which every point has an s-successor. Now consider the following ELIQs q1, q2, . . . that satisfy qi ̸⊆O q ⊆O qi:

Any frontier F must contain a pi with pi ⊆O qi for all i ≥ 1. We show that, consequently, there is no bound on the size of the queries in F. We invite the reader to apply the frontier construction from Section 3 after dropping func(r-).

The proof actually shows that there is no finite frontier even if we admit the use of unrestricted CQs in the frontier in place of ELIQs. To regain finite frontiers, we restrict our attention to DL-LiteF ontologies O such that if B ⊑ C is a CI in O, then C contains no subconcept of the form ∃R.D with func(R-) ∈ O. We call such an ontology a DL-LiteF- ontology. We again concentrate on ontologies in normal form.

Lemma 4. For every DL-LiteF- ontology O, we can construct in polynomial time a DL-LiteF- ontology O′ in normal form such that for every ELIQ q, a frontier of q w.r.t. O can be constructed in polynomial time given a frontier of q w.r.t. O′ .

The main result of this section is as follows.

Theorem 4. Let O be a DL-LiteF- ontology and q an ELIQ that is satisfiable w.r.t. O. Then a frontier of q w.r.t. O can be computed in polynomial time.

To prove Theorem 4, let O and q be as in the theorem, O in normal form. We may assume w.l.o.g. that q is O-minimal and O-saturated. The construction of a frontier follows the same general approach as for DL-LiteH, but the presence of functional roles significantly complicates the compensation step. As before, we introduce fresh variables and rely on the mapping x↓ .

Step 1: Generalize. For each variable x ∈ var(q), define a set F0(x) that contains all ELIQs which can be obtained by starting with qx(x) and then doing one of the following:

• (A) Drop concept atom: exactly as for DL-LiteH.
• (B) Generalize subquery:
• choose an atomR(x, y) ∈ q directed away from x0;
• remove R(x, y) and all atoms of qy;
• if func(R) /∈ O, then for each q′ (y) ∈ F0(y) add a disjoint copy ̂ q′ of q′ and the role atomR(x, y′ ) with y′ the copy of y in ̂ q′ ;
• if func(R) ∈ O and F0(y) ̸= ∅, then choose and add a q′ ∈ F0(y) and the role atomR(x, y).

Step 2: Compensate. We construct a frontier F of q(x0) by including, for each p ∈ F0(x0), the CQ obtained from p by the following two steps. For x ∈ var(q), R a role, and M a set of concept names from O, we write x ⇝Rq,O M if M is maximal with Aq,O |= ∃R. � M(x) and there is no R(x, y) ∈ q with Aq, O |= � M(y).

Step 2A. Consider every x ∈ var(p), role R, and set of concept names M = {A1, . . . ,Ak} with x↓ ⇝Rq,O M. If O |= ∃R ⊑ B implies B(x) ∈ p for all concept names B, add the atoms R(x, z),A1(z), . . . ,Ak(z) where z is a fresh variable, and leave z↓ undefined.

Step 2B. This step is iterative. For bookkeeping, we mark atoms R(x, y) ∈ p to be processed in the next round of the iteration. Marking is only applied to atoms R(x, y) directed away from x0 such that y↓ is defined and if x↓ is undefined then func(R-) /∈ O or q contains no atom of the form R(y↓ , z).

To start, consider every R(x, y) ∈ p directed away from x0 with func(R-) /∈ O. Then x↓ is defined. Extend p with atom R-(y, x′ ), x′ a fresh variable with x′↓ = x↓ . Mark the new atom.

Then repeatedly choose a marked atom R(x, y) and unmark it. If func(R-) /∈ O or q contains no atom of the form R(y↓ , z), then add a disjoint copy ̂ q of q and glue the copy of y↓ in ̂ q to y. Otherwise, do the following:

• (i) add A(y) whenever Aq,O |= A(y↓ );
• (ii) for all atoms S(y↓ , z) ∈ q with S(y↓ , z) ̸= R-(y↓ , x↓ ), extend p with atom S(y, z′ ), z′ a fresh variable with z′↓ = z. Mark S(y, z′ ).
• (iii) For all roles S and sets M = {A1, . . . ,Ak} such that y↓ ⇝Sq,O M, extend p with atoms S(y, u), S-(u, y′ ),A1(u), . . . ,Ak(u) where u and y′ are fresh variables. Set y′↓ = y↓ and mark S-(u, y′ ).

The step is repeated as long as possible. Note that in Point (iii), the role S must occur on the right-hand side of some CI in the DL-LiteF- ontology O. Consequently, func(S-) /∈ O and it is not a problem that u receives two Spredecessors. Also in Point (iii), func(S) ∈ O implies that q cannot contain an atom S(y↓ , z) due to the definition of '⇝' and thus we may leave u↓ undefined.

This finishes the construction of the frontier F of q.

Example 3. Consider the ontology O = {func(s)} and ELIQ q(x0) shown on the left-hand side below:

Lemma 5. F is a frontier of q(x0) w.r.t. O.

As for DL-LiteH, the constructed frontier is of polynomial size and its computation takes only polynomial time. Crucially, the iterative process in Point 2B terminates since in Step (ii) a (copy of a) subquery of q is added and the process stops at atoms added in Step (iii).

Lemma 6. The construction of F runs in time polynomial in ||q||+||O|| (and thus ∑ p∈F ||p|| is polynomial in ||q||+||O||).

One first application of our results on frontiers is to the unique characterization of ELIQs w.r.t. ontologies by labeled data examples. Details are in the long version.

5 Learning ELIQs under Ontologies

We use our results on frontiers to show that ELIQs are polynomial time learnable under ontologies formulated in DL-LiteH and DL-LiteF-, using only membership queries. We also present two results on non-learnability.

Theorem 5. ELIQs are polynomial time learnable under DL-LiteH ontologies and under DL-LiteF- ontologies using only membership queries.

If the ontology contains concept disjointness constraints, then this only holds true if the learner is provided with a seed CQ (definition given below).

For proving Theorem 5, let O be an ontology formulated in DL-LiteH or DL-LiteF- and qT (x0) the target ELIQ known to the oracle. We may again assume O to be in normal form.

Algorithm 1 Learning ELIQs under DL-Lite ontologies

Input An ontology O in normal form and a CQ q0H satisfiable w.r.t. O such that q0H ⊆O qT Output An ELIQ qH such that qH ≡O qT qH := treeify(q0H ) while there is a qF ∈ FqH with qF ⊆O qT do qH := minimize(qF ) end while return qH

Lemma 7. In DL-LiteH and DL-LiteF-, every polynomial time learning algorithm for ELIQs under ontologies in normal form that uses only membership queries can be transformed into a learning algorithm with the same properties for ELIQs under unrestricted ontologies.

The learning algorithm is displayed as Algorithm 1. It assumes a seed CQ q0H , that is, a CQ q0H such that q0H ⊆O qT and q0H is satisfiable w.r.t. O. If O contains no disjointness constraints, then for Σ = sig(O) we can use as the seed CQ

We can still construct a seed CQ q0H in time polynomial in ||O|| if O contains no disjoint constraints on concepts (but potentially on roles); details at in the long version. In the presence of concept disjointness constraints, a seed CQ can be obtained through an initial equivalence query.

The algorithm constructs and repeatedly updates a hypothesis ELIQ qH while maintaining the invariant qH ⊆O qT . The initial call to subroutine treeify yields an ELIQ qH with q0H ⊆O qH ⊆O qT to be used as the first hypothesis. The algorithm then iteratively generalizes qH by constructing the frontier FqH of qH w.r.t. O in polynomial time and choosing from it a new ELIQ qH with qH ⊆O qT . In between, the algorithm applies the minimize subroutine to ensure that the new qH is O-minimal and to avoid an excessive blowup while iterating in the while loop.

We next detail the subroutines treeify and minimize. We define minimize on unrestricted CQs since it is applied to nonELIQs as part of the treeify subroutine.

The minimize subroutine. The subroutine takes as input a unary CQ q(x0) that is satisfiable w.r.t. O and satisfies q ⊆O qT . It computes a unary CQ q′ with q ⊆O q′ ⊆O qT using membership queries that is minimal in a strong sense. Formally, minimize first makes sure that q is O-saturated and then exhaustively applies the following operation:

Remove atom. Choose a role atom r(x, y) ∈ q and let qbe the maximal connected component of q \ {r(x, y)} that contains x0. Pose the membership query Aq-, O |= qT (x0). If the response is positive, continue with q- in place of q.

Clearly, the result of minimize is O-minimal.

The treeify subroutine. The subroutine takes as input a unary CQ q(x0) that is satisfiable w.r.t. O, and satisfies q ⊆O qT . It computes an ELIQ q′ with q ⊆O q′ ⊆O qT by repeatedly increasing the length of cycles in q and minimizing the obtained query; a similar construction is used in [ten Cate and Dalmau, 2021]. The resulting ELIQ is O-minimal.

Formally, treeify first makes sure that q(x0) is O-saturated and then constructs a sequence of CQs p1, p2, . . . starting with p1 = minimize(q) and then taking pi+1 = minimize(p′i ) where p′i is obtained from pi by doubling the length of some cycle. Here, a cycle in a CQ q is a sequence R1(x1, x2), . . . ,Rn(xn, x1) of distinct role atoms in q such that x1, . . . xn are distinct. More precisely, p′i is the result of the following operation.

Double cycle. Choose a role atom r(x, y) ∈ pi that is part of a cycle in pi and let p be pi \ {r(x, y)}. The CQ p′i is then obtained by starting with p, adding a disjoint copy p′ of p where x′ refers to the copy of x ∈ var(p) in p′ and adding the role atoms r(x, y′ ), r(x′ , y).

If pi contains no more cycles, treeify stops and returns pi.

Returning to Algorithm 1, let q1, q2, . . . be the sequence of ELIQs that are assigned to qH during a run of the learning algorithm. We show in the long version that for all i ≥ 1, it holds that qi ⊆O qT , qi ⊆O qi+1 while qi+1 ̸⊆O qi, and |var(qi+1)| ≥ |var(qi)|. This can be used to prove that the while loop in Algorithm 1 terminates after a polynomial number of iterations, arriving at a hypothesis qH with qH ≡O qT .

We now turn to non-learnability results. Without a seed CQ, ontologies with concept disjointness constraints are not learnable using only polynomially many membership queries. A disjointness ontology is a DL-LiteHF ontology that only consists of concept disjointness constraints.

Theorem 6. AQ∧s are not learnable under disjointness ontologies using only polynomially many membership queries.

We next show that when we drop the syntactic restriction from DL-LiteF-, then ELIQs are no longer learnable at all using only membership queries. Note that this is not a direct consequence of Theorem 3 as there could be an alternative approach that does not use frontiers.

Theorem 7. ELIQs are not learnable under DL-LiteF ontologies using only membership queries.

6 Outlook

A natural next step for future work is to generalize the results presented in this paper to DL-LiteHF , adopting the same syntactic restriction that we have adopted for DL-LiteF , and additionally requiring that functional roles have no proper subroles. The latter serves to control the interaction between functional roles and role inclusions. Even with this restriction, however, that interaction is very subtle and the frontier construction becomes significantly more complex. Other interesting questions are whether ELIQs can be learned in polynomial time w.r.t. DL-Litehorn ontologies and whether CQs can be learned w.r.t. DL-Litecore ontologies when both membership and equivalence queries are admitted.

Acknowledgements

Carsten Lutz was supported by DFG CRC 1320 EASE.