2025/08/11 by Maurice Funk, Funk, Maurice, Grosser, Marvin +2
Computer Science · #Semantic Web and Ontologies #Advanced Database Systems and Queries #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2508.08007
We study a fitting problem inspired by ontology-mediated querying: given a collection of positive and negative examples of the form (A,q) with A an ABox and q a Boolean query, we seek an ontology O that satisfies A ∪ O \vDash q for all positive examples and A ∪ O\not\vDash q for all negative examples. We consider the description logics ALC and ALCI as ontology languages and a range of query languages that includes atomic queries (AQs), conjunctive queries (CQs), and unions thereof (UCQs). For all of the resulting fitting problems, we provide effective characterizations and determine the computational complexity of deciding whether a fitting ontology exists. This problem turns out to be \scriptsize CONP for AQs and full CQs and 2E\scriptsize XPT\scriptsize IME-complete for CQs and UCQs. These results hold for both ALC and ALCI.