We study a fitting problem inspired by ontology-mediated querying: given a collection of positive and negative examples of the form (, ) with an ABox and a query, we seek an ontology that satisfies ∪ |= for all positive examples (, ) and ∪ ̸|= for all negative examples (, ). We consider the description logics ℒ and ℒℐ 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 efective characterizations and determine the computational complexity of deciding whether a fitting ontology exists. This problem turns out to be coNP-complete for AQs and full CQs and 2ExpTime-complete for CQs and UCQs. These results hold for both ℒ and ℒℐ.
= { ∃authorOf.Publication ⊑ Author,
Reviewer ⊑ ∃reviews.Publication, }.
There are, however, many other fitting ℒ-ontologies, including ⊥ = {⊤ ⊑ ⊥} and, say, ′ = ∪ {Author ⊑ ∃authorOf.Reviewer}. We can make both of them non-fitting by adding the negative example ({Author()}, ∃ authorOf(, ) ∧ Reviewer()).
A main application of fitting ontologies is to assist with ontology construction and engineering. This
is in the spirit of several other proposals that have the same aim, such as ontology construction and
completion using formal concept analysis [
As ontology languages, we concentrate on the expressive yet fundamental DLs ℒ and ℒℐ, and as query languages for examples we consider atomic queries (AQs), conjunctive queries (CQs), full CQs (CQs without quantified variables), and unions of conjunctive queries (UCQs).
We formally define what we mean by ontology fitting. Let be a query language such as = AQ or = CQ. An ABox- example is a pair (, ) with a ABox1 and a query from such that all individual names that appear in are from ind(), the individuals appearing in . By a collection of labeled examples we mean a pair = (+, − ) of finite sets of examples. The examples in + are the positive examples and the examples in − are the negative examples. We say that an ℒ or ℒℐ ontology fits if ∪ |= for all (, ) ∈ + and ∪ ̸|= for all (, ) ∈ − .
Let ℒ be an ontology language, such as ℒ = ℒℐ, and a query language. Then (ℒ,)-ontology iftting is the problem to decide, given as input a collection of labeled ABox- examples , whether admits a fitting ℒ-ontology.
For all of the resulting combinations, we provide efective characterizations and determine the precise complexity of (ℒ, )-ontology fitting. The algorithms that we use to prove the upper bounds are able to produce concrete fitting ontologies.
As a starting point, we study an ontology fitting problem in which the examples are only ABoxes
and where we seek an ontology that is consistent with the positive examples and inconsistent with
the negative ones. To characterize fitting existence for these consistency examples, we make use of
the established connection between ontology-mediated querying and constraint satisfaction problems
(CSPs) from [
Theorem 1. Let = (+, − ) be a collection of labeled ABox examples, ℒ ∈ {ℒ, ℒℐ}, and + = ⨄︀ +. Then the following are equivalent:
2. ̸→ + for all ∈ − .
This characterization directly provides a coNP algorithm to decide fitting existence. Intuitively, a ontology that fits the examples can be derived from +. We obtain a corresponding lower bound via reduction from the digraph homomorphism problem.
For ABox-AQ examples, the role of the positive and negative examples reverses, as now a fitting ontology must be consistent with the ABox in a negative example (, ()), as otherwise ∪ |= (). Additionally, the positive examples act as “rules”, meaning that for some positive 1We do not admit compound concepts in ABoxes. example (, ()), whenever can be homomorphically found in − := ⨄︀(,())∈− , any fitting ontology must derive at the image of .2 To account for this, we introduce the notion of completions which enrich − with additional concept assertions and enable us to precisely characterize fitting existence in the setting of AQs. Let = (+, − ) be a collection of labeled ABox-AQ examples. A completion for is an ABox that extends − by assertions of the form (), with ∈ ind(− ) and a concept name that occurs as an AQ in +.
Theorem 2. Let = (+, − ) be a collection of labeled ABox-AQ examples and let ℒ ∈ {ℒ, ℒℐ}.
a) for all (, ()) ∈ +: if ℎ is a homomorphism from to , then (ℎ()) ∈ ; b) for all (, ()) ∈ − : () ̸∈ .
Note that an algorithm that directly follows this characterization yields a Σ 2 upper bound. We obtain a coNP upper bound via a more careful algorithm that does not blindly guess a suitable completion, but constructs one step-by-step. For this the algorithm starts with − , and then extends it by guessing, for some positive ABox-AQ example (, ()), a homomorphisms ℎ from to − , and then adding (ℎ()). We show coNP-hardness using a similar reduction as in the consistency based setting.
Ontology fitting for ABox-FullCQ examples has similar properties as ABox-AQ case. One notable diference is that ABox-FullCQ examples can force fitting ontologies to be inconsistent with their ABoxes.
Example 2. Consider a positive ABox-FullCQ example (, (, )) with (, ) ∈/ . Every ℒℐontology with ∪ |= (, ) must be inconsistent with .
Thus, we arrive at a characterization that extends the ABox-AQ case with considerations for
consistency. A modest modification of the AQ-algorithm then shows that ( ℒ, FullCQ)-ontology fitting
is coNP-complete. We remark that the obtained complexities for ontology fitting are lower than the
complexities of the associated query entailment problems, which are ExpTime-complete for the cases
discussed so far [
For ABox-CQ and ABox-UCQ examples, the intuition that positive examples behave like “rules” persists, but the presence of quantified variables results in higher expressive power. In fact, positive examples (, ) now behave similarly to existential rules: if is homomorphically found somewhere in the completion, then must also be found there in a certain slightly unusual sense made precise in the paper that, notably, treats quantified variables in in a similar way as existentially quantified variables in the head of an existential rule. It is thus easy to enforce that the completion contains, say, an infinite path. The completions that we construct in the CQ/UCQ case are thus ABoxes that extend − with potentially infinite tree-shaped components that are either rooted in an individual in − or disconnected. They thus take the same form as forest models which are well-known from algorithms for UCQ entailment.3 Example 3. Consider the collection of labeled ABox-CQ examples = (+, − ) where + = {(, ∃ (, ) ∧ ())}, − = {(, ∃∃ (, ) ∧ (, ))}, and = {()}. Any completion of contains − = . Hence, a homomorphism of into is found, and to satisfy the positive example viewed as an existential rule must contain an -successor of with () ∈ . There is thus another homomorphism from to that maps to and thus must have an -successor . While in principle this continues indefinitely, already at this point we have satisfied the query from the negative example. By the characterization given in the full paper, this implies that does not admit a fitting ℒ or ℒℐ ontology. 2The homomorphisms used here are not required to be the identity on ABox individuals (which would, in fact, trivialize them). 3In the full paper, we actually represent completions as forest models rather than as ABoxes.
As a consequence of this efect, the computational complexity of fitting existence turns out to be much higher: 2ExpTime complete for both CQ and UCQ examples, no matter whether we want to fit an ℒ- or ℒℐ-ontology. The upper bound is derived by a mosaic algorithm. The lower bound for ℒℐ is obtained via a reduction from query entailment and the lower bound for ℒ is shown via a reduction from the word problem of exponentially space-bounded alternating Turing machines.
complete.
For ℒℐ, the complexity thus coincides with that of query entailment, which is 2ExpTime-complete both for CQs and UCQs [20]. For ℒ, the complexity of the fitting problems is higher than that of the associated entailment problems, which are both ExpTime-complete [20].
The full version [21] of the paper [22] summarized in this extended abstract contains full proof details.
The third author was supported by DFG project LU 1417/4-1.
The author(s) have not employed any Generative AI tools.
University Press, 2017. [20] C. Lutz, Two upper bounds for conjunctive query answering in SHIQ, in: Proc. of DL 2008, volume 353 of CEUR Workshop Proceedings, CEUR-WS.org, 2008. URL: https://ceur-ws.org/Vol-353/Lutz. pdf. [21] M. Funk, M. Grosser, C. Lutz, Fitting description logic ontologies to abox and query examples, arXiv, 2025. URL: https://arxiv.org/abs/2508.08007. arXiv:2508.08007, 2508.08007. [22] M. Funk, M. Grosser, C. Lutz, Fitting description logic ontologies to ABox and query examples, in: Proc. of KR, 2025. To appear.