Datatype Reasoning That Stays Cheap When the Numbers Are Simple

Ontology reasoners, the programs that check class hierarchies in large knowledge bases such as SNOMED CT, have a gap where numbers and strings meet logic. Real ontologies say things like "a pediatric dose is a dose whose value lies in [0, 12]" or "an adult is a person whose age is at least 18." The fastest complete reasoners today cannot read these statements at all. These are consequence-based reasoners: instead of building candidate models and backtracking, they derive new facts directly by deterministic inference rules. Reasoners that can read such statements fall back on model-building search that scales poorly. This note proposes adding numeric and string data ranges to a consequence-based calculus so that the extra cost is paid only when the data constraints actually force case analysis.

The core idea is a single analogy. In logic-only reasoning, Horn axioms (those with no "either/or") keep reasoning cheap and disjunction makes it expensive. Data constraints have their own version of this split, called convexity. A set of numeric ranges is convex if, whenever a range is contained in a union of other ranges, it is already contained in one of them. We propose a calculus in which an external datatype solver is queried only for the data ranges that occur in a given local reasoning context. Its answers come back as ordinary clauses. When the ranges in that context are convex, every answer is a Horn clause, and the reasoner keeps its polynomial-time behavior. A clause with real disjunction is generated only where a non-convex combination of ranges actually appears.

Why this gap, and what already exists

Consequence-based reasoning has grown from Horn logics to almost all of OWL 2 DL. Consequence-Based Reasoning beyond Horn Ontologies handles disjunction without case splitting. On the non-Horn SCT-SEP ontology its ConDOR reasoner classified in 88.9 seconds, against 2,324.1 seconds for FaCT++, while HermiT and Pellet failed. The Sequoia line localizes inferences into a graph of "contexts". Consequence-Based Reasoning for Description Logics with Disjunctions and Number Restrictions adds number restrictions through equality reasoning, Consequence-based Reasoning for Description Logics with Disjunction, Inverse Roles, Number Restrictions, and Nominals adds nominals, and Sequoia: A Consequence Based Reasoner for SROIQ adds a two-phase saturation that processes Horn clauses before disjunctive ones.

These papers motivate the proposal directly, because both the Sequoia system paper and the ALCHOIQ calculus paper say that datatypes are missing. The first says datatypes are "prevalent in real-world applications." The second says datatypes are needed for full OWL 2 DL coverage. Neither specifies how a datatype solver should interact with resolution over contexts, and that interface is what we design.

The concrete-domain literature supplies the oracle side and also sets limits on scope. A Scheme for Integrating Concrete Domains into Concept Languages treats the numeric domain as a black box and requires it to be "admissible": its predicates are closed under negation, and satisfiability of conjunctions of them is decidable. We reuse this contract. Closure under negation is what lets the oracle answer containment questions as well as satisfiability questions. Reasoning with Concrete Domains introduces a "cluster" strategy in tableaux: concrete constraints are grouped only when feature paths connect them. Our context-local oracle calls are the consequence-based counterpart of that grouping.

Web Ontology Reasoning with Datatype Groups contributes per-datatype type checkers with scoped negation. Scoped negation avoids the "Fred" problem, where the negation of "greater than 5" wrongly includes the string "Fred". We adopt that design for the oracle.

Two papers constrain the scope. Keys, Nominals, and Concrete Domains shows that general key constraints over concrete features become undecidable. NExpTime-complete Description Logics with Concrete Domains shows that general terminologies combined with feature paths raise complexity sharply. We therefore restrict to unary data ranges on data properties, without paths or keys. This is the OWL 2 DL datatype fragment as actually used, and it avoids those barriers.

The tiered systems connect the two directions without closing the gap. MORe: Modular Combination of OWL Reasoners for Ontology Classification partitions an ontology by locality. It sends the simple module to a fast profile reasoner and the rest to HermiT. Its partitioning ignores datatypes, so any datatype axiom may pull its neighborhood into the slow reasoner. PAGOdA: Pay-As-You-Go Ontology Query Answering Using a Datalog Reasoner brackets query answers between sound and complete Datalog bounds, but has no approximation for numeric predicates. Both of these systems are architectural workarounds; the proposal changes the calculus itself.

Core Claim

Data-range reasoning can be added to a consequence-based calculus for ALCHIQ, and later for the Sequoia SROIQ engine, in a way that is pay-as-you-go in two independent dimensions. The first is the familiar Horn versus non-Horn dimension on the logical side. The second is convex versus non-convex on the data side. On Horn ontologies whose data ranges are convex within each context, classification remains polynomial, and runtime should stay within a small constant factor of datatype-free saturation. That case covers the OWL 2 EL datatype restrictions, which were designed to be convex. Disjunctive clauses produced by the data side are created only in contexts that contain a non-convex set of ranges, and their number is bounded by the ranges occurring in that context rather than in the whole ontology.

Research Program

The calculus extends context clauses with a second sort for data values. Consider an axiom such as $A \sqsubseteq \exists p.D$, where $p$ is a data property and $D$ a data range. It does not create a successor context. Instead it introduces, within the current context, a data term $y$ carrying literals $p(x,y)$ and $D(y)$. Data terms never get their own contexts, which keeps the context graph unchanged.

The new inference is theory-lemma resolution. Take a context whose clauses mention a set of data ranges $\mathcal{R}$. The oracle is asked one question about it: for which $D \in \mathcal{R}$ and $S \subseteq \mathcal{R}$ does

$$D \models \bigvee_{E \in S} E \quad\text{and } S \text{ is minimal}?$$

Here $D \models \bigvee S$ means every value in range $D$ falls into some range in $S$. Each answer is turned into the clause $D(y) \rightarrow \bigvee_{E \in S} E(y)$ and resolved like any other clause. Unsatisfiable conjunctions of ranges appear as the special case where the right-hand side is empty.

Convexity is the central observation. When $\mathcal{R}$ is convex, every minimal $S$ has at most one element, so every lemma is Horn. Under Sequoia's two-phase strategy, these lemmas are then processed in the cheap deterministic phase. Lemmas are generated lazily, only for ranges that appear negatively in the context's clauses. This is the step that separates the design from eager compilation.

Data number restrictions, such as "at least $n$ values of $p$ in range $D$", require a counting query to the oracle: how many distinct values does $D \wedge \neg E_1 \wedge \dots$ admit? They are handled through the existing equality machinery, with lemmas asserting that two data terms are equal when a finite range forces it. This is the part most at risk of the clause blow-up that the Sequoia SROIQ paper already reports for combined at-most restrictions. We treat it as a second phase, after the unary core is complete.

The theoretical deliverables are three. The first is soundness and completeness of the extended calculus relative to an admissible oracle. The second is a proof that the Horn plus convex case stays polynomial. The third is a bound on oracle calls per context. The implementation deliverable is an extension of Sequoia with interval oracles for the integers and reals and with string facet oracles.

Baselines

The naive reference point is Sequoia unchanged, run with all data axioms removed. It is the fastest possible run, but it is incomplete. We report how many subsumptions it misses relative to a complete reasoner, and how much of our extension's runtime overhead those missed subsumptions account for. No reported result was found on Lacuna for missed subsumptions caused by dropping datatypes.

The strongest complete competitors are tableau reasoners with built-in datatype handling: HermiT, Konclude, and FaCT++. HermiT follows the type-checker design of Web Ontology Reasoning with Datatype Groups. These systems are the strongest baseline because they are the only systems that are sound and complete on the same input today. On datatype-free inputs, the closest reported comparison is ConDOR at 88.9 seconds against FaCT++ at 2,324.1 seconds on SCT-SEP, from the ConDOR paper. The Sequoia SROIQ paper reports that Sequoia classified more ontologies of the 777-ontology Oxford corpus than HermiT, Pellet, FaCT++, and Konclude, though without numeric runtimes. No reported result was found on Lacuna for any of these systems on datatype-rich ontologies. All systems will run on the same machine with the same timeout and memory limits and default settings. Beating the tableau baseline means two things: more ontologies classified within the timeout, and lower median time on datatype-bearing ontologies that take longer than 30 seconds, with hierarchies identical to theirs.

The architectural competitor is MORe with HermiT as its fallback. MORe reported roughly 410 seconds against roughly 1,900 seconds for HermiT on a SNOMED CT extension with injected disjunctions. We will measure what fraction of each ontology MORe's locality split sends to HermiT once data axioms are present. Beating it means lower total time on ontologies where data axioms are spread across the hierarchy.

The ablation that isolates the main ingredient is eager compilation. Before running unmodified Sequoia, each data range in the ontology is replaced by a fresh concept. All containment and disjointness axioms computed by the oracle are added, along with the full set of covering disjunctions. We run two variants: a Horn-only version, which is incomplete, and a full version, which is complete. A second ablation keeps our lazy, context-local lemmas but turns off the convexity test, so that every lemma is processed in the disjunctive phase.

Why not just…?

Why not just use HermiT or Konclude, which already support datatypes? They do, but the cited evidence is that model-building search degrades sharply on large non-Horn ontologies, as the SCT-SEP and Oxford corpus results show. Those are datatype-free results, however. It is possible that datatypes are rare or shallow enough in practice that tableaux cope well. The datatype subset of the Oxford corpus experiment settles this directly. If the tableau reasoners already classify that subset quickly, the practical case for the proposal shrinks to the large injected-data ontologies.

Why not just compile each data range into a fresh class and run Sequoia unchanged? This is the real threat, and we do not argue around it: it is built in as the main ablation. On ontologies whose ranges are convex everywhere, compilation produces only Horn axioms and may perform as well as our method. The proposal's distinctive claim is narrower. When even a few non-convex combinations exist, eager compilation adds covering disjunctions everywhere, while lazy lemmas confine them to the contexts that need them. If the full-compilation variant matches our runtime on the non-convex injected benchmarks, the calculus offers no gain over preprocessing, and we would report the compiler as the contribution instead.

Why not just route datatype axioms to HermiT through MORe-style modules? That works when data axioms sit in a small corner of the ontology. Datatype restrictions in clinical ontologies, however, tend to attach to central classes such as doses and measurements. The module-size measurement shows whether the slow module stays small. If it does, MORe is a sufficient engineering answer for classification, and the calculus matters mainly for completeness inside one engine.

Why not just encode values as nominals? A Scheme for Integrating Concrete Domains into Concept Languages documents why such encodings lose ordering and contradiction detection. The ALCHOIQ consequence-based calculus also shows that nominals are its most expensive feature, pushing it to triple-exponential time. Encoding values as nominals would therefore move data reasoning into the costliest part of the engine.

Proposed Experiments

The first experiment uses the Oxford Ontology Repository. We extract every ontology that uses data properties with ranges, run all systems, and report three things: ontologies classified, median and tail runtimes, and agreement of the computed hierarchy with HermiT's.

The second experiment is a controlled injection study in the style of MORe's SNOMED extensions. Starting from SNOMED CT (Horn) and SCT-SEP (non-Horn), we attach numeric ranges to measurement- and dose-like classes. The proportion of non-convex combinations is varied from zero upward, which yields a two-by-two grid of Horn versus non-Horn logic and convex versus non-convex data.

The decisive check is the shape of the runtime curve. Our method's overhead over datatype-free Sequoia should stay near constant in the Horn plus convex cell. It should then grow with the number of non-convex contexts, not with the total number of data axioms. The eager-compilation curve should grow with the total. If the two curves coincide, the laziness claim is refuted.

A secondary check counts lemmas per context, to confirm the predicted bound on oracle calls. A final stress test adds data cardinality restrictions on finite integer ranges, to find where the known blow-up from at-most restrictions reappears.