REVIEW 2 major objections 3 minor
Fitting Description Logic Ontologies to ABox and Query Examples
T0 review · 2 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read The paper classifies the complexity of fitting description logic ontologies to positive and negative (ABox, query) examples, showing coNP-completeness for atomic and full conjunctive queries, and 2EXPTIME-completeness for conjunctive querie
desk verdict Fresh ontology fitting problem with a plausible complexity dichotomy, but the upper bounds need a compactness lemma the abstract doesn't state. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is a compactness or canonical-form lemma: if any fitting ontology exists, then one exists with a TBox whose size is bounded by a function of the example ABoxes, typically by constructing a finite set of general concept inclusions (GCIs) of bounded depth. This bounded canonical form turns the search over all ontologies into a finite, decidable problem, enabling the coNP upper bounds via a witness that can be guessed and checked in polynomial time, and the 2EXPTIME upper bounds via a translation to alternating automata or similar exponential-space devices. The characterizations rest on the fact that only the logical consequences of the ontology over the finite ABoxes matt
What would settle it
Take a specific pair of positive and negative examples in ALCI with conjunctive queries where the effective characterization says no fitting ontology exists, but an explicit infinite or unbounded-depth TBox (e.g., a chain of role successors of increasing length) can be exhibited that makes the positive query entailed and the negative query not entailed. Producing such a case would show the bounded-witness lemma fails. Conversely, to test the lower bound, construct a family of instances for which the characterization is equivalent to a known 2EXPTIME-hard problem (e.g., word problem for alterna
Extended reading notes
Core claim
For the ontology fitting problem, in which an ontology O must entail a Boolean query q over an ABox A for positive examples (A,q) and not entail it for negative examples, the paper establishes exact worst-case complexity boundaries. For atomic queries (AQs) and full conjunctive queries (which allow quantified variables in the query answer), deciding the existence of a fitting ontology in ALC or ALCI is coNP-complete. For conjunctive queries (CQs) and unions of conjunctive queries (UCQs), the same decision problem is 2EXPTIME-complete. The paper accompanies these complexity results with effective characterizations: for each case, one can decide whether a fitting ontology exists by checking st
Load-bearing premise
The existence of a bounded, canonical TBox for every fitting instance is load-bearing: the complexity upper bounds rely on being able to restrict attention to ontologies of size and depth bounded by the examples, and if some fitting problem required ontologies of unbounded depth or noncanonical axiom forms, the decision procedures would no longer decide the original problem.
Editorial extensions
If this is right
- If the characterizations are correct, a practitioner can decide algorithmically whether a set of example-mediated queries is consistent with any ALC or ALCI ontology, without enumerating candidate ontologies.
- The coNP-completeness for atomic queries means that checking consistency of ontology fitting is easy in practice when queries are of the simplest form, assuming NP is not too hard; the 2EXPTIME-completeness for unions of conjunctive queries shows that adding disjunction or join structure sharply raises the intrinsic difficulty.
- The results give a firm baseline for any future work on learning description logic ontologies from examples: no more tractable general algorithm can exist for the standard query languages, so practical systems must either restrict the query language, restrict the ontology language, or use heuristics.
- Because the same complexity levels hold for both ALC and ALCI, the inverse role operator is not a source of hardness; any future attempt to find a tractable fragment should focus on the query language or the form of the TBox.
- The effective characterizations can serve as a certificate format: a fitting ontology can be checked by verifying the characterizations on the finite examples, which is a step toward explaining why a particular set of examples admits a consistent ontology.
Reading between the lines
- A testable extension would be to ask whether the same complexity bounds hold when the ontology is allowed to contain role inclusions, transitive roles, or nominals; the paper's restriction to GCIs in ALC/ALCI suggests that adding such features could break the 2EXPTIME upper bound, but the proof machinery may generalize.
- The coNP bound for atomic queries likely transfers to the problem of finding a single ontology that simultaneously fits multiple mutually inconsistent example sets, because the bounded-witness condition is monotone in the set of negative examples; this is not stated in the paper but follows from the structure of the characterization.
- A natural follow-up is to study the counting or enumeration version—how many distinct (up to logical equivalence) fitting ontologies exist—since the characterization gives a finite description of all candidates but does not count them.
- The dichotomy between coNP and 2EXPTIME suggests a phase transition: if one restricts the query language to acyclic conjunctive queries, the complexity may drop to coNP or stay 2EXPTIME depending on the shape of the join structure, which is a concrete open question raised implicitly by the paper.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the ontology fitting problem: given positive and negative examples of the form (ABox, Boolean query), decide whether there exists an ontology O (in ALC or ALCI) such that all positive examples are entailed and all negative examples are not. The abstract announces effective characterizations and complexity classifications for atomic queries (AQs), conjunctive queries (CQs), and unions of conjunctive queries (UCQs). Specifically, it claims CO NP-completeness for AQs and for a class called 'full CQs', and 2EXPTIME-completeness for CQs and UCQs, in both ALC and ALCI.
Significance. If correct, the paper provides a complete worst-case complexity landscape for ontology fitting over standard DL and query languages, a problem directly relevant to ontology learning, repair, and interactive knowledge-base construction. The claimed boundary between CO NP and 2EXPTIME is nontrivial and would be a useful guide for designing practical algorithms. The promise of 'effective characterizations' goes beyond mere complexity, potentially giving algorithmic insight into the structure of fitting ontologies. However, because the review is based solely on the abstract, the validity of these claims rests entirely on the technical development that is not visible here.
major comments (2)
- [Abstract (upper-bound claims)] The upper-bound results (CO NP for AQs/full CQs and 2EXPTIME for CQs/UCQs) presuppose a compactness or normal-form lemma: if any fitting ontology exists, then one exists whose size and role depth are bounded by a computable function of the input ABoxes and queries. The abstract neither states nor justifies such a bound. Without it, decision procedures over the infinite space of all finite ALC/ALCI TBoxes cannot terminate. This is a load-bearing step, not a minor technicality; the paper should state the lemma explicitly and indicate where it is proved. If the lemma is already in the full text, the abstract should summarize it.
- [Abstract (terminology: 'full CQs')] The term 'full CQs' is used without definition. It appears in the CO NP result alongside the 2EXPTIME-complete result for 'CQs', which is confusing. If 'full CQs' is a restricted class of conjunctive queries, its definition and the relationship to general CQs must be given. If it is a synonym for Boolean CQs, then the apparent contradiction with the 2EXPTIME-completeness of CQs needs immediate clarification. This is not merely cosmetic: the complexity classification is the central contribution, and ambiguity here undermines the accuracy of the announced results.
minor comments (3)
- [Abstract / Introduction] Please clarify the exact syntax of the ontology. The abstract says 'ontology' but does not state whether it is a TBox only (general concept inclusions), whether role axioms are allowed, and whether the ontology is required to be finite. These choices affect the complexity bounds.
- [Notation] State explicitly that ABoxes are finite and that all queries are Boolean; otherwise the example format (A,q) is ambiguous.
- [References] The abstract should reference prior work on ontology learning and query entailment complexity (e.g., 2EXPTIME-completeness of CQ answering in ALC) to contextualize the contributions.
Circularity Check
No circularity found; the fitting problem is defined from first principles and the complexity results are benchmarked against independent reasoning complexity.
full rationale
This is an abstract-only review. The paper defines a novel fitting problem (given positive/negative (ABox, Boolean query) examples, does there exist an ALC/ALCI ontology satisfying all of them?) and states complexity classifications (CONP for AQs and full CQs, 2EXPTIME-complete for CQs and UCQs). There is no quoted derivation, equation, or self-citation in the abstract that would allow a circular-step accusation. In particular: (1) No parameter is fitted to a subset of the examples and then renamed a prediction; the sought object is an ontology, not a predicted label. (2) No prior work by the same authors is cited in the abstract, so no self-citation chain or imported uniqueness theorem is detectable. (3) The complexity lower bounds are presumably reductions from known reasoning problems, which are external benchmarks, and the upper bounds are decision procedures whose termination would rely on structural lemmas about fitting ontologies. The skeptic's concern about an unstated compactness/normal-form lemma bounding TBox size is a legitimate correctness or completeness question, but it is not circularity: a missing bound does not make the result equivalent to its inputs by construction. Similarly, the undefined term 'full CQs' is a clarity issue, not a circularity. With only the abstract in evidence, the appropriate finding is no significant circularity (score 0).
Assumptions & free parameters
assumptions (3)
- standard math Standard Turing machine model of computation and standard notions of CO NP and 2EXPTIME completeness.
- domain assumption Standard first-order semantics for ALC/ALCI TBoxes and ABoxes (role assertions and concept inclusions).
- domain assumption Known hardness of the underlying description logic reasoning tasks used in lower-bound reductions (e.g., conjunctive query answering in ALC is 2EXPTIME-hard).
Cite this review
Pith. "Pith review of Fitting Description Logic Ontologies to ABox and Query Examples." pith.science (2026). https://pith.science/paper/KGYWVK26
@misc{pith2026250808007,
author = {Pith},
title = {Pith review of: Fitting Description Logic Ontologies to ABox and Query Examples},
year = {2026},
howpublished = {\url{https://pith.science/paper/KGYWVK26}},
note = {Machine review of arXiv:2508.08007}
}
abstract
We study a fitting problem inspired by ontology-mediated querying: given a collection of positive and negative examples of the form $(\mathcal{A},q)$ with $\mathcal{A}$ an ABox and $q$ a Boolean query, we seek an ontology $\mathcal{O}$ that satisfies $\mathcal{A} \cup \mathcal{O} \vDash q$ for all positive examples and $\mathcal{A} \cup \mathcal{O}\not\vDash q$ for all negative examples. We consider the description logics $\mathcal{ALC}$ and $\mathcal{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 CO}NP$ for AQs and full CQs and $2E{\scriptsize XP}T{\scriptsize IME}$-complete for CQs and UCQs. These results hold for both $\mathcal{ALC}$ and $\mathcal{ALCI}$.
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.