# Fitting Description Logic Ontologies to ABox and Query Examples

arXiv: https://arxiv.org/abs/2508.08007 · HTML: https://mlsanity.com/paper/2508.08007/

## 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 (most cited first, 7 of 7)

- [Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP](https://mlsanity.com/paper/1301.6479/) (2013)
- [Learning Description Logic Ontologies. Five Approaches. Where Do They Stand?](https://mlsanity.com/paper/2104.01193/) (2021)
- [Exact Learning of Lightweight Description Logic Ontologies](https://mlsanity.com/paper/1709.07314/) (2017)
- [Logical Separability of Labeled Data Examples under Ontologies](https://mlsanity.com/paper/2007.01610/) (2020)
- [Separating Data Examples by Description Logic Concepts with Restricted Signatures](https://mlsanity.com/paper/2107.05285/) (2021)
- [Finite Query Answering in Expressive Description Logics with Transitive Roles](https://mlsanity.com/paper/1808.03130/) (2018)
- [Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics](https://mlsanity.com/paper/2010.11842/) (2020)

## Built on by (most cited first, 2 of 2)

- [Fitting Horn DL Ontologies to ABox and Query Examples: A Tale of Simulation Quantifiers and Finite Models](https://mlsanity.com/paper/2604.26976/) (2026)
- [From USD Scenes to Knowledge Graphs: Zero-Shot Ontology Grounding with LLMs](https://mlsanity.com/paper/2606.09134/) (2026)

## 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.