Actively Learning ELI Queries under DL-Lite Ontologies

We show that ELI queries (ELIQs) are learnable in polynomial time in the presence of a DL-Lite ontology O, in Angluin’s framework of active learning. When initially provided with a conjunctive query (CQ) that implies the target ELIQ under O (in the sense of query containment), it suffices for the learner to only pose membership queries to the oracle, but no equivalence queries. The initial CQ can be obtained by a single equivalence query and is available ‘for free’ in case that O does not pose any disjointness constraints on concepts. Our main technical result is that every ELI concept has only polynomially many most specific subsumers w.r.t. a DL-Lite ontology, generalizing a recent result about homomorphism frontiers by ten Cate and Dalmau.