Abstract
We study the problem of learning Description Logic (DL) ontologies in Angluin et al.’s framework of exact learning via membership and equivalence queries posed to an oracle. Our quest is on investigating whether DL ontologies can be exactly learned in polynomial time or, at least, with polynomially many polynomial size queries to an oracle. We consider two instances of the problem:
• in the first instance we admit entailment queries “is a given subsumption entailed by the unknown target DL ontology?” and equivalence queries “is a given DL ontology equivalent to the target DL ontology?”. Assuming that the vocabulary and DL L of the target ontology are known, we study polynomial learnability of ontologies in L;
• in the second instance we admit membership queries of the form “is a tuple ⃗a of individuals a certain answer to a data retrieval query q in a given data set and the unknown target DL ontology?” and equivalence queries of the form “is a given DL ontology equivalent to the target DL ontology?”. Given the DL L, the data retrieval query language Q and the vocabulary of the target ontology, we study polynomial learnability of ontologies in L using data retrieval queries in Q.
In both instances of the problem, we provide an almost complete classification for DLs that are fragments of ELH and of DL-Lite. Some results are proved by non-trivial reductions to the first instance of the problem, described above.