Learning, in Angluin's framework of exact learning, a query in the presence of a description logic ontology often involves as a crucial (iterated) step the generalization of a hypothesis query. This may be achieved, for example, by constructing a least general generalization of the hypothesis and a counterexample that was provided by the oracle. In this research note, we observe that it may pay of to resort to a more liberal construction that uses the counterexample as a guide to produce a generalization of the hypothesis while not necessarily achieving a generalization of the counterexample. We use this approach to show polynomial time learnability of ℰℒℐ concept queries (ELIQs) in the presence of ontologies which are formulated in a mild restriction of DL-Litehℱorn.
Various forms of learning description logic (DL) concepts, ontologies, and queries have been
studied in the literature, including PAC learning [
The interest in exact learning in DLs started with an investigation of ontology learning in
(the conference version of) [
To explain the contribution of this article, let us introduce exact learning of queries in the presence of DL ontologies. Learner and oracle both know and agree on the ontology and they also agree on the target query to use only concept and role names from . There are two kinds of queries that the learner may pose to the oracle. In a membership query, the learner provides an ABox and a candidate answer ¯ and asks whether , |= (¯) ; the oracle faithfully answers “yes” or “no”. In an equivalence query, the learner provides a hypothesis query and asks whether is equivalent to under ; the oracle answers “yes” or provides a counterexample, that is, an ABox and tuple ¯ such that , |= (¯) and , ̸|= (¯) (positive counterexample) or vice versa (negative counterexample). Then, polynomial time learnability means that there is a learning algorithm that constructs (¯) , up to equivalence w.r.t. , such that at any given time, the running time of the algorithm is bounded by a polynomial in the sizes of , , and the largest counterexample given by the oracle so far. 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 has to be bounded by such a polynomial.
We next describe, on an informal level, how a typical learning algorithm works. The described
strategy has been used, e.g., to learn CQs and mappings in database theory [25, 26], LTL
formulas [27], as well as ontologies and queries in a DL context [
0 ⊆ 1 ⊆ 2 ⊆ · · · of increasingly general hypothesis queries, where ‘⊆ ’ denotes query containment under the ontology . It maintains the invariant that ⊆ for all ≥ 0 where is the target query to be learned (only known to the oracle). As the initial hypothesis 0, one constructs a very strong query which implies any possible . If, for example, the query language is unary CQs and the ontology does not express any disjointnesses between concept and role names, then this query might be the single-variable query that has atoms () and (, ) for all concept names and role names . If a more restricted query class such as ELIQs is used or the ontology expresses disjointness constraints, then the construction of the initial hypothesis might be more subtle and also involve interaction with the oracle, see [22, 24].
To move from hypothesis to +1, the algorithm repeatedly employs a suitable generalization strategy, which may be viewed as the heart of the learning algorithm. In the literature, one ifnds two main such strategies. To describe them, assume that the class of target queries is a class of CQs such as all CQs or all ELIQs.
When query and ontology language are suficiently restricted, it may happen that the set
of all possible least general generalizations of the current hypothesis can be computed in
polynomial time. Then, membership queries to the oracle can be used to identify a generalization
that implies the target, and the algorithm does not need to use equivalence queries at all. This
strategy has been used, for example, to learn ELIQs in the presence of ontologies formulated
in DL-Liteℋ and DL-Liteℱ− [
The aim of this note is to introduce a variation of the second approach to generalization, and to demonstrate its usefulness by devising a polynomial time learning algorithm for ELIQs in the presence of DL-Litehℱo−rn ontologies. In theory, a natural way to construct a -LGG of the hypothesis and counterexample is to build the universal models of (viewed as an ABox) and of under the ontology , and to then take their direct product.1 If we interpret ‘universal model’ as meaning homomorphism universal,2 then such models are infinite and thus the described construction cannot be used in a learning algorithm. But homomorphism universality is not strictly required to obtain a -LGG when is not the class of all CQs. We may then use -universal models which only require that for every query in the target query language , the answers to on under coincide with the answers to on the universal model. Sometimes, it is possible to construct finite -universal models, an approach that has been used successfully to learn a restricted form of CQs in the presence of ℰℒ ontologies [22]. To learn ELIQs under DL-Lite ontologies, however, this approach fails since finite ELIQ-universal models are not guaranteed to exist (even for non-branching ELIQs).
Example 1. Let = {⊤ ⊑ ∃.⊤} and = {()}. The homomorphism-universal model of and is extended with an infinite -path (, 1), (1, 2), . . . . Any ELIQ-universal model also needs such a path, and thus the only chance to obtain a finite ELIQ-universal model is to reuse individuals on the path. But such a model cannot be ELIQ-universal: if = , with < , then is an answer to the ELIQ ∃.∃(− ). on the universal model, but not on under .
Of course, there could potentially be ways to construct a -LGG other than taking the direct product of -universal models. In the presence of DL-Lite ontologies, though, the -LGG is not guaranteed to exist when is the class of CQs or the class of non-branching ELIQs extended with reflexive role atoms. For non-extended ELIQs, the existence of -LGGs remains open. Example 2. Let = {∃− .⊤ ⊑ ∃.⊤, ∃− .⊤ ⊑ ∃.⊤}. Consider the unary CQs () = ∃∃ (, ) ∧ (, ) ∧ (, ) ∧ (, ) ∧ () and () = ∃ () ∧ (, ).
We claim that no ELIQ-LGG of and exists, and thus also no -LGG for any query class that contains all ELIQs. To see this, assume that the CQ () is an ELIQ-LGG of and , and ̂︀ consider all ELIQs of the form , = ∃.∃.∃− .∃(− ). with , ≥ 1. It is easy to see that ⊆ , and ⊆ , if and only if = , thus ̂︀ ⊆ , if and only if = . For all ≥ 1, take a homomorphism ℎ from , to the homomorphism universal model of ̂︀ (viewed as an ABox) and ; this model is defined in detail in Section 2. If for some , ℎ maps two distinct variables in the ‘∃’ prefix of , to the same element of , then an easy pumping argument shows that ̂︀ ⊆ , for some > , a contradiction. Otherwise, there is some ≥ 1 such that ℎ chooses as the -successor required by the ‘∃’ infix in , an element of that was 1This may yield a CQ that does not fall within , but there are strategies for the learning algorithm to deal with this. 2that is, a universal model of an ABox and admits a homomorphism into every model of and . generated by an existential quantifier, that is, it is in the tree-shaped ‘anonymous’ part of . Since , is rooted, the ℎ-homomorphic image of the ‘∃’ prefix of , enters the anonymous part from the same non-anonymous element where it also leaves it to eventually reach an element that satisfies (there are no such elements in the anonymous part). Thus is reachable in ̂︀ from along an -path and reaches an instance of along an -path, which means that ̂︀ ⊆ ∃. for some ≥ 1. But this contradicts ⊆ ̂︀.
In this paper, we propose to replace -LGGs by a more liberal construction, which still
achieves a generalization of the hypothesis, though not necessarily of the counterexample. In
fact, we use the counterexample only as a guide to identify in polynomial time a generalization
of the hypothesis that is contained in the target query. In contrast to the construction of -LGGs
via products, our construction is asymmetric in that it treats the hypothesis diferently from
the counterexample. We use our construction as a central ingredient to prove polynomial
time learnability of ELIQs in the presence of DL-Litehℱo−rn ontologies. For the type of learning
algorithm that we pursue, there is a ‘natural ensemble’ of lemmas that one may use to prove
correctness and termination in polynomial time [
Missing proof details will be provided in the long version of the paper.
Ontologies and ABoxes. Let NC, NR, and NI be countably infinite sets of concept, role and individual names. A role is a role name or the inverse − of a role name, and − denotes when = − . A basic concept is of the form ⊤, , or ∃ where ranges over NC and over roles. A DL-Litehℱorn ontology is a set of concept inclusions (CIs) 1 ⊓ · · · ⊓ ⊑ , concept disjointness constraints 1 ⊓ · · · ⊓ ⊑ ⊥, role disjointness constraints 1 ⊓ 2 ⊑ ⊥, and functionality assertions func() where , range over basic concepts and 1, 2, over roles. In a DL-Litehℱo−rn ontology, we additionally require that if ∃ occurs on the right-hand side of a CI, then func(− ) ∈/ [24].
An ℰℒℐ concept is an expression that is built according to the rule ::= ⊤ | | ⊓ | ∃. where ranges over concept names and over roles. An ℰℒℐℱ ontology is a finite set of concept inclusions (CIs) ⊑ , emptiness constraints ⊑ ⊥, role disjointness constraints 1 ⊓ 2 ⊑ ⊥, and functionality assertions func() where , range over ℰℒℐ concepts and 1, 2, over roles. The basic concept ∃ is a diferent way to write the ℰℒℐ concept ∃.⊤. Note that every DL-Litehℱorn ontology is an ℰℒℐℱ ontology. An ℰℒℐℱ ontology (and thus also a DL-Litehℱorn ontology) is in normal form if all concept inclusions in it are of the form ⊑ or ⊑ , where is a concept name. Every DL-Litehℱorn ontology can be transformed in polynomial time into a DL-Litehℱorn ontology ′ in normal form such that ′ is a conservative extension of , and the same is true for ℰℒℐℱ ontologies.
An ABox is a finite set of concept assertions () and role assertions (, ) with a concept name or ⊤, a role name, and , individual names. We use ind() to denote the set of individual names used in . We admit concept assertions ⊤() in order to represent interpretations and ABoxes in a uniform way.
The semantics is defined as usual in terms of interpretations ℐ, which we define to be a (possibly infinite and) non-empty set of concept and role assertions. We use ∆ ℐ to denote the set of individual names in ℐ and set ℐ = { | () ∈ ℐ} for all ∈ NC and ℐ for compound concepts in the usual way [28]. Note that every ABox is a finite interpretation and, vice versa, every finite interpretation is an ABox. An interpretation ℐ satisfies a concept inclusion ⊑ if ℐ ⊆ ℐ , a constraint ⊑ ⊥ if ℐ = ∅, a functionality assertion func() if ℐ is a partial function, a concept assertion () if ∈ ℐ , and a role assertion (, ) if (, ) ∈ ℐ . An interpretation is a model of an ℰℒℐℱ ontology or an ABox if it satisfies all concept inclusions, constraints, and assertions in it. We write |= ⊑ if every model of the ontology satisfies the concept inclusion ⊑ and , |= () if every model of and satisfies the concept assertion (). An ABox is satisfiable w.r.t. an ℰℒℐℱ ontology if and have a common model. We use ℐ1 × ℐ 2 to denote the direct product of two interpretations ℐ1, ℐ2.
A signature is a set of concept and role names, uniformly referred to as symbols. For a syntactic object such as an ontology, we use sig() to denote the symbols used in and |||| to denote the size of , that is, the length of a representation of as a word in a suitable alphabet. Queries. Every ℰℒℐ concept can be viewed as an ℰℒℐ query (ELIQ). An individual ∈ ind() is an answer to on an ABox w.r.t. an ontology , written , |= (), if ∈ ℐ for all models ℐ of and . We shall often view ELIQs as unary conjunctive queries (CQs) and also consider CQs that are not ELIQs. A CQ takes the form (¯) = ∃¯ (¯, ¯) with a conjunction of concept atoms () and role atoms (, ) where ∈ NC and ∈ NR. We call the variables in ¯ answer variables. The arity of is the length |¯| of ¯, and a query is Boolean if it has arity 0. We use var() to denote the set of variables that occur in . We may view as a set of atoms whenever convenient and may write − (, ) in place of (, ). A CQ is rooted if in its Gaifman graph = (var(), {{, } | (, ) ∈ }) every variable is reachable from some answer variable. It is well-known that ELIQs are in 1-to-1 correspondence with rooted, unary CQs whose Gaifman graph is a tree and that contain no self-loops and multi-edges. We use to denote the ABox obtained from CQ by viewing variables as individuals and atoms as assertions. A CQ is satisfiable w.r.t. ontology if is. For any CQ and set ⊆ var(), | is the restriction of to all atoms that only contain variables in .
The semantics of CQs is given in terms of homomorphisms as usual. As for ELIQs, we will write , |= (¯) if the tuple ¯ is an answer to (¯) on w.r.t. . For CQs 1 and 2 and an ℰℒℐℱ ontology , we say that 1 is contained in 2 w.r.t. , written 1 ⊆ 2, if for all ABoxes and ¯ from ind(), , |= 1(¯) implies , |= 2(¯) . We call 1 and 2 equivalent w.r.t. , written 1 ≡ 2, if 1 ⊆ 2 and 2 ⊆ 1.
Universal Model. Query answering and query containment w.r.t. DL-Litehℱorn ontologies can be conveniently characterized using universal models. Let be an DL-Litehℱorn ontology in normal form and an ABox that is satisfiable w.r.t. . For a set of concept names, we write d as a shorthand for d∈ . For ∈ ind(), , ′ sets of concept names, and a role, we write ⇝ , if , |= ∃. d () and is maximal with this condition. We write ⇝ ′ if |= d ⊑ ∃. d ′ and ′ is maximal with this.
A trace for and is a sequence = 1122 . . . , ≥ 0 where ∈ ind(), 1, . . . , are roles in sig(), and 1, . . . , are sets of concept names in sig(), such that (i) ⇝ 1, 1 and there is no ∈ ind() with 1(, ) ∈ , (ii) ⇝ +1 +1 and +1 ̸= − , for 1 ≤ < .
The set T of all traces for and forms the domain of the universal model ,, defined as , = ∪ {() | , |= ()} ∪ {( ) | ∈ T and ∈ } ∪ {(, ) | ∈ T}.
For a CQ , we usually write , instead of ,. The following property of , is crucial for our technical development.
Observation 3. Let be a DL-Litehℱorn ontology in normal form, an ABox, and ℐ = , ∖ . Then for every role , ℐ is a partial function. -saturatedness and -minimality. Let be an ℰℒℐℱ ontology. A CQ is -minimal if there is no ⊊ var() such that ≡ | . A CQ is -saturated if , |= () implies () ∈ for all ∈ var() and ∈ NC. Every CQ (or ELIQ) can be converted into an equivalent -saturated one in polynomial time when an oracle for queries of the form “, |= ()?” is available. In DL-Litehℱorn, such queries can be answered in polynomial time [29] and thus -saturatedness can be established in polynomial time.
Recall from the introduction that a CQ ̂︀ is a least general -generalization (-LGG) of CQs , under an ontology if ⊆ ̂︀ , and ̂︀ ⊆ ′ for every ′ ∈ with ⊆ ′ and , ⊆ ̂︀ ⊆ ′. We consider the following weakening of -LGGs.
Definition 4. Let be an ontology and a class of queries, and let , be CQs with ̸⊆ . A CQ ̂︀ is a -guided -generalization of under if the following conditions are satisfied: 1. ⊆ ̂︀; 2. ̂︀ ̸⊆ ; 3. ̂︀ ⊆ ′, for every ′ ∈ with ⊆ ′ and ⊆ ′.
Conditions 1 and 3 match the first and the last condition in the definition of a -LGG. Intuitively, they mean that is a generalization of (Condition 1) which preserves all common ̂︀ -consequences of and (Condition 3). Condition 2 weakens the second condition in the definition of an LGG: instead of requiring ⊆ , we only want to strictly generalize . In the ̂︀ ̂︀ context of learning, one may view as orthogonal knowledge about how to imply the unknown target, and the goal of guided generalization is to incorporate some of that knowledge into . ̂︀ Thus, in contrast to LGGs, guided generalizations are an asymmetric notion in that the two queries and play diferent roles: is the query to be generalized and acts as the guide for doing so. We start with observing that -guided -generalizations are not uniquely defined. Example 5. Consider () = () ∧ () ∧ () and () = (). Then both 1() = () and 2() = () ∧ () are -guided ELIQ-generalizations of under the empty ontology.
It is not by accident that in Example 5 the ELIQ-LGG of and (which is 1) is also a guided ELIQ-generalization. In fact, it is not dificult to show that each -LGG of two CQs , under an ontology is both a -guided -generalization of under and a -guided -generalization of under . The subsequent example shows that the converse direction is not true, that is, there are cases where a guided generalization exists, but LGGs do not.
Example 6. Consider again queries and and the ontology from Example 2, and recall that there is no CQ-LGG for , . However, the query () = ∃∃′ (, ) ∧ (, ′) ∧ (′) ̂︀ is a -guided CQ-generalization of under . To illustrate the asymmetry of the notion, observe that ̂︀ is not a -guided CQ-generalization of under , since it does not satisfy Condition 1.
We now give our main result, namely that guided ELIQ-generalizations of ELIQs under DL-Litehℱo− rn ontologies always exist and can be computed in polynomial time. Theorem 7. Given a DL-Litehℱo− rn ontology in normal form and ELIQs , such that , are satisfiable w.r.t. and is -minimal,3 we can compute in polynomial time a -guided ELIQgeneralization of under such that ̂︀ is satisfiable w.r.t. .
̂︀ Let (1), (2) be ELIQs. We construct a -guided ELIQ-generalization of under in ̂︀ three steps as follows. We start with the query ̂︀ = (, × ,)|{(1,2)}, that is, the restriction of , × , to variable (1, 2), which will be the answer variable of . This query is then ̂︀ extended by first exhaustively applying rule (A1) below and then applying rule (A2). (A1) For every (, ) ∈ var() with ∈ var() and ∈ ∆ , , every atom (, ′) in , and ̂︀ every atom (, ′) ∈ ,, add the atom ((, ), (′, ′)), and all atoms (′, ′) such that (′) ∈ , and (′) ∈ ,. (A2) For every (, ) ∈ var() with ∈ var() and ∈ ∆ , and every role such that ̂︀ ⇝ , for some and there is no atom of the form (, ′) in , add the atoms ((, ), ), (′, )
̂︀ ̂︀ with a fresh variable, and add a copy ′ of in which the copy of is ′.
̂︀ 3We conjecture that, given an ELIQ, an equivalent -minimal ELIQ can be computed in polynomial time by extending the techniques for answering tree-shaped queries over DL-Lite knowledge bases in polynomial time [30] to DL-Litehℱorn knowledge bases. For the purpose of this paper the statement in the theorem sufices. Recall that , × ,, when viewed as an infinitary CQ, may serve as a CQ-LGG of and . Intuitively, the above construction may be viewed as producing an approximation of this product from below, in the sense that the product may be more general. It is easy to see that after having applied (A1) exhaustively, we have constructed exactly the restriction of the product , × , to the elements (, ′) that are reachable from the element (1, 2) and satisfy ∈ var(). We will show that this is a finite structure and even of polynomial size, which is essentially due to Observation 3 on the shape of universal models for DL-Litehℱo− rn ontologies. What is missing is the infinite part of , × , determined by elements (, ′) where is a proper trace, that is, is not a variable from . (A2) approximates this part by traveling the traces of , (but not of ,) for only one step and then adding copies of as described. Note that for DL-Litehℱo− rn ontologies , the first step into the traces of , is enough to regenerate via the entire universal model ,. Also note that for (A2) to produce a query that is satisfiable w.r.t. , we rely on the restriction to DL-Litehℱo− rn: the precondition of (A2) implies that ∃ appears on the right-hand side of some concept inclusion in and thus − is not functional.
We demonstrate our construction on two examples that additionally illustrate (1) that (A2) is indeed needed and (2) that the result is not necessarily an ELIQ.
̂︀ Example 8. (1) Consider the ontology = { ⊑ ∃, ∃ ⊑ , ∃− ⊑ ∃} and ELIQs (1) = (1) ∧ (1)
(2) = ∃′∃ (2) ∧ (2, ) ∧ (′, ) ∧ (′) ∧ (′).
Note that and are -saturated. The result of exhaustively applying Step (A1) is 0() = (),4 ̂︀ which generalizes , but is too general: the ELIQ
() = ∃′∃∃′∃ (, ) ∧ (, ) ∧ (′, ) ∧ (′, ′) ∧ (′) satisfies ̂︀0 ̸⊆ , while ⊆ and ⊆ . After additionally applying (A2), we obtain () = ∃′∃ () ∧ (, ) ∧ (′, ) ∧ (′) ∧ (′), ̂︀ which is a -guided ELIQ-generalization of under .
(2) Consider the following queries ′, ′ and the empty ontology.
′() = ∃1∃2 (, 1) ∧ (, 2) ∧ (1) ∧ (2) ′() = ∃∃ (, ) ∧ (, ) ∧ () ∧ () The result of (A1) is the direct product ′ × ′ of ′ and ′ which is ′() = ∃1∃2∃ (, 1) ∧ ̂︀ (, 2) ∧ (, 1) ∧ (, 2) ∧ (1) ∧ (2), which is not an ELIQ.
We apply the notion of guided generalizations to show that ELIQs are polynomial time learnable in the presence of DL-Litehℱo− rn ontologies using membership and equivalence queries. It is known that both kinds of queries are needed as otherwise polynomial time learnability fails (already without functional roles) [22]. Our learning algorithm follows the scheme detailed in the introduction. The main result is as follows. 4We have replaced the single answer variable (1, 2) with for the sake of readability.
Algorithm 1 Algorithm for learning ELIQs under DL-Litehℱo−rn ontologies
Input A DL-Litehℱo−rn ontology and a unary CQ 0 satisfiable w.r.t. such that 0 ⊆ Output An ELIQ such that ≡ := extract-minimal-ELIQ(0 ) while the equivalence query “ ≡ ?” returns a counterexample (, ) do := extract-minimal-ELIQ() where is viewed as a CQ with answer variable ′ := a -guided ELIQ-generalization of under := extract-minimal-ELIQ(′ ) end while return Theorem 9. ELIQs are polynomial time learnable under DL-Litehℱo−rn ontologies using membership and equivalence queries.
To prove the theorem, it sufices to consider ontologies in normal form: Lemma 10. If ELIQs are polynomial time learnable under DL-Litehℱo−rn ontologies in normal form using membership and equivalence queries, the same is true for unrestricted DL-Litehℱo−rn ontologies.
Our learning algorithm is listed in Algorithm 1. It takes as input a DL-Litehℱo−rn ontology in normal form and a seed query 0 with 0 ⊆ . A seed query can be obtained in several ways, depending on the type of disjointness constraints present in ; we refer to [24] for details. As explained in the introduction, the algorithm starts with the seed query and constructs a sequence of increasingly more general hypothesis queries. In each round, the learner asks whether the current hypothesis is the target using an equivalence query. If not, they use the counterexample provided by the oracle as a guide to generalize via the construction from the proof of Theorem 7. Since both the input to that construction and the queries posed as equivalence queries must be ELIQs, the algorithm relies on the subroutine extract-minimal-ELIQ to generalize a CQ with ⊆ into an ELIQ ′ with ′ ⊆ using membership queries. In order to attain polynomial running time, extract-minimal-ELIQ additionally ensures a strong minimality condition on ′, namely that it is ( , )-minimal, which means that there is no ⊊ var(′) with ′| ⊆ . Importantly, a ( , )-minimal query may have at most as many variables as (provided that it is -saturated, a condition that we shall maintain at all times), and it is -minimal. We next detail the extract-minimal-ELIQ subroutine.
The extract-minimal-ELIQ subroutine takes as input a unary CQ that satisfies ⊆ . It computes an ELIQ ′ with ⊆ ′ ⊆ by repeatedly attaining ( , )-minimality and increasing the length of cycles in . A cycle in a CQ is a sequence 1(1, 2), . . . , (, 1) of distinct role atoms in such that 1, . . . are distinct. Now, extract-minimal-ELIQ computes the -saturation of and then modifies by exhaustively applying the following two rules:
Drop variable. Choose a variable ∈ var() and let ′ = |var()∖{}. If the response to the membership query ′ , |= () is positive, continue with ′ in place of .
Double cycle. Choose a role atom (, ) ∈ that is part of a cycle. Then add a disjoint copy ′ of to and let ′, ′ be the copies of , in ′. Remove the atoms (, ), (′, ′) and add the atoms (, ′), (′, ).
We give preference to the first rule, that is, the second rule is only applied when the first one is not applicable. Clearly, if Drop variable is not applicable, then is ( , )-minimal. Once no rule is applicable anymore, extract-minimal-ELIQ returns ′ = .
The following lemma collects the relevant properties of extract-minimal-ELIQ. All properties except termination are essentially consequences of the definition of the subroutine. The proof of termination after polynomially many steps relies on Theorem 13 below.
Lemma 11. Let be a unary CQ with ⊆ that is satisfiable w.r.t. . Then, extract-minimal-ELIQ() terminates in time polynomial in |||| + |||| + || || and returns an ELIQ ′ that is -saturated, ( , )-minimal, and satisfies ⊆ ′ ⊆ .
To show termination and correctness of our algorithm, we first formalize the notion of a ‘sequence of increasingly general hypotheses which are all contained in ,’ which is underlying the general scheme described in the introduction.
Definition 12. Let be a CQ and an ontology. A sequence 1, 2, . . . of CQs is a generalization sequence towards under if for all ≥ 0, ⊆ +1 ̸⊆ , ⊆ , and sig() ⊆ sig().
Let 1, 2, . . . be the sequence of ELIQs that are assigned to during the run of the algorithm. We show inductively that 1, 2, . . . is a generalization sequence towards the target query under . For the base case, note that extract-minimal-ELIQ (0 ) computes an initial with 0 ⊆ ⊆ . For the inductive step, let (, ) be a counterexample provided by the oracle to the equivalence query “ ≡ ?”. We may assume that uses only symbols from (we can simply drop all assertions mentioning other symbols). Since ⊆ , the counterexample is positive and thus ̸⊆ . The subroutine extract-minimal-ELIQ generalizes into a query , hence ̸⊆ . Since ′ is a -guided ELIQ-generalization of , we have ⊆ ′ (Condition 1 of Definition 4), ′ ̸⊆ (Condition 2), and ′ ⊆ (Condition 3). It remains to note that extract-minimal-ELIQ preserves these conditions.
It has been observed that already for ELIQs that do not use inverse roles and under the empty ontology, there is no elementary bound on the length of generalization sequences towards a given query [31]. However, since Lemma 11 guarantees that all are ( , )-minimal and -saturated, the next theorem implies that only polynomially many hypotheses are produced. Theorem 13. Let be a rooted CQ and an ℰℒℐℱ ontology in normal form, and let 1, 2, . . . be a generalization sequence towards under such that 1 is satisfiable w.r.t. . If all are ( , )-minimal and -saturated, then the sequence has length at most |var( )|3 · | sig()|.
It remains to show that the extract-minimal-ELIQ subroutine terminates after polynomially many steps. For this, consider the sequence 1, 2, . . . of queries that Double cycle is applied to during a run of extract-minimal-ELIQ. All these queries are -saturated. By the preference imposed on rule application, they are also ( , )-minimal. Since an application of Drop Variable decreases the size of the query, there are at most polynomially many such applications between and +1. Thus, it sufices to show the following lemma and apply Theorem 13. Lemma 14. The sequence 1, 2, . . . is a generalization sequence towards under .
We conclude the section with some comments regarding the (limits of) generality of the central Theorem 13. It has been shown that Theorem 13 holds for unrestricted CQs when one considers the restriction ℰℒ of ℰℒℐ as ontology language [22] and we conjecture the same to be true also for many DL-Lite dialects, e.g., DL-Litehℱorn. However, the extension to unrestricted, that is, possibly non-rooted, CQs is not possible for ℰℒℐ. The subsequent example illustrates that it fails already for Boolean CQs with a single variable.
Example 15. Let , for 1 ≤ ≤ be concept names and a role name. Let be an ℰℒℐ ontology that contains the following concept inclusions, for all with 1 ≤ ≤ : ⊑ ∃.⊤ ∃− .(0 ⊓ · · · ⊓ − 1 ⊓ ) ⊑ ∃− .(0 ⊓ · · · ⊓
− 1 ⊓ ) ⊑ ∃− . ⊓ ⊑ ∃− . ⊓ ⊑ Each subset of {, | 1 ≤ ≤ } containing exactly one of , for each represents a number between 0 and 2 − 1 in an obvious way. Let be the Boolean CQ that corresponds to number . Clearly, all are -saturated and (2− 1, )-minimal. The sequence 1, 2, . . . , 2− 1 is a generalization sequence towards 2− 1 under , but its length is exponential in .
We have introduced a new form of generalizations and proved its applicability in the context
of exact learning of ELIQs in the presence of DL-Litehℱo−rn ontologies. We believe it is worth
investigating the new notion of guided generalizations more thoroughly. On the one hand,
there are basic open questions such as whether there always exists a least general or most
general -guided ELIQ-generalization of for all ELIQs , . On the other hand, we would
like to understand whether Theorem 7 holds for other relevant combinations of query class
and ontology language, e.g., ELIQs and DL-Litehℱorn, CQs and any DL-Lite dialect, ELIQs and
DL-Liteℋ, that is, DL-Lite with role hierarchies. The latter will be challenging since there are no
universal models that satisfy Observation 3. We note that Theorem 7 does not extend to ELIQs
and ℰℒℐ ontologies: Our results imply that if we could compute in polynomial time using an
oracle for queries of the form “, |= ()”, guided ELIQ-generalization of ELIQs under ℰℒℐ
ontologies, then ELIQs would be polynomial query learnable under ℰℒℐ ontologies which is
known not to be the case [22]. In cases where guided generalizations are not guaranteed to exist,
it would be interesting to study the induced existence and verification decision problems [
As we have shown, positive answers to (some of) these questions would directly lead to polynomial time learnability results. Here, interesting open (and challenging) questions are whether CQs are polynomial time learnable in the presence of DL-Litehℱorn (or even DL-Lite) ontologies, and whether ELIQs are eficiently learnable under DL-Litehℱorn or DL-Liteℋ ontologies. ability, in: Proc. of ICDT, volume 186 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 9:1–9:24. [22] M. Funk, J. C. Jung, C. Lutz, Actively learning concept and conjunctive queries under ℰ ℒ-ontologies, in: Proc. of IJCAI, 2021, pp. 1887–1893. [23] M. Funk, J. C. Jung, C. Lutz, Actively learning ELI queries under DL-Lite ontologies, in:
Proc. of DL 2021), volume 2954 of CEUR Workshop Proceedings, CEUR-WS.org, 2021. [24] M. Funk, J. C. Jung, C. Lutz, Frontiers and exact learning of ℰ ℒℐ queries under DL-Lite ontologies, in: Proc. of IJCAI, 2022. [25] B. ten Cate, P. G. Kolaitis, K. Qian, W. Tan, Active learning of GAV schema mappings, in:
Proc. of PODS, 2018, pp. 355–368. doi:10.1145/3196959.3196974. [26] B. ten Cate, V. Dalmau, P. G. Kolaitis, Learning schema mappings, ACM Trans. Database
Syst. 38 (2013) 28:1–28:31. [27] M. Fortin, B. Konev, V. Ryzhikov, Y. Savateev, F. Wolter, M. Zakharyaschev, Unique characterisability and learnability of temporal instance queries, in: Proc. of KR, 2022. [28] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logics, Cambridge
University Press, 2017. [29] A. Artale, D. Calvanese, R. Kontchakov, M. Zakharyaschev, The DL-Lite family and relations, J. Artif. Intell. Res. 36 (2009) 1–69. [30] M. Bienvenu, M. Ortiz, M. Simkus, G. Xiao, Tractable queries for lightweight description logics, in: Proc. of IJCAI, 2013, pp. 768–774. [31] F. Kriegel, Navigating the ℰ ℒ subsumption hierarchy, in: M. Homola, V. Ryzhikov, R. A.
Schmidt (Eds.), Proc. of DL, volume 2954 of CEUR Workshop Proceedings, CEUR-WS.org, 2021.