Fitting Description Logic Ontologies to ABox and Query Examples
Not on the map. Why?
Abstract (arXiv)
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 cup O vDash q for all positive examples and A cup OnotvDash 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 2Escriptsize XPTscriptsize IME-complete for CQs and UCQs. These results hold for both ALC and ALCI.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 7 of its 42 references that are in the map. First posted on arXiv 11 Aug 2025.
Builds on
7 of 42 references.
References · 7
- 2013Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNPcited by 15
- 2021Learning Description Logic Ontologies. Five Approaches. Where Do They Stand?cited by 12
- 2017Exact Learning of Lightweight Description Logic Ontologiescited by 10
- 2020Logical Separability of Labeled Data Examples under Ontologiescited by 10
- 2021Separating Data Examples by Description Logic Concepts with Restricted Signaturescited by 5
- 2018Finite Query Answering in Expressive Description Logics with Transitive Rolescited by 4
- 2020Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logicscited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.