Entailment and the Reasoning Budget

A SPARQL query asks for ?person :employedBy ?org and comes back empty. The store holds forty million :worksFor triples and an ontology line saying :worksFor rdfs:subPropertyOf :employedBy. Nothing is wrong with the data or the query. Whether that query returns rows depends entirely on whether something in the stack computed the consequence of that one axiom, and when it did so. Entailment is the name for the gap between what was asserted and what follows, and the interesting engineering question is never "is it true" but "who pays for it".

What the vocabulary licenses

RDFS buys four workhorse axioms: rdfs:subClassOf, rdfs:subPropertyOf, rdfs:domain and rdfs:range. Their consequences are computable by a small fixed rule set, so the full entailment closure of an RDFS graph can be produced in a single bottom-up pass. This is the cheap tier, and it covers most of what practitioners actually want: type hierarchies, property hierarchies, and the inference that a subject of :worksFor is a :Person because the domain says so.

OWL 2 buys much more, and the price curve is steep. The description logic behind OWL 2 DL is SROIQ, and the combined complexity of its reasoning problems is doubly exponential, which is why the W3C standardised three profiles, each cut to fit a tractable algorithm rather than a modelling wish list (W3C, 2012, OWL 2 Web Ontology Language Profiles):

• OWL 2 EL keeps existential restrictions, conjunction and property chains, and drops disjunction and universal restrictions. The basic reasoning problems run in time polynomial in the size of the ontology, which is why the large biomedical terminologies live here.
• OWL 2 QL is designed so that conjunctive query answering can be performed in LOGSPACE with respect to the size of the data. That is the formal way of saying it compiles into SQL over an ordinary relational database.
• OWL 2 RL is expressible as a rule set over triples, so a production-rule engine or a Datalog evaluator can implement it, again in polynomial time.

Picking a profile is a budget decision made at modelling time. Add one axiom outside it and the ontology is no longer in the profile, which changes the algorithm your store is allowed to use.

Materialise or rewrite

Two strategies, and essentially only two.

Forward chaining computes the closure when data lands and stores the derived triples alongside the asserted ones. Queries then become plain pattern lookups with no reasoning at all, which is why it is the default in most production triple stores. The costs are store inflation and deletion. Retracting one asserted triple means knowing which derived triples depended on it, and because a derived triple can have several independent derivations, the honest answer requires truth maintenance. Most engines answer by recomputing the affected closure instead, which turns a single delete into a batch job.

Query rewriting leaves the data exactly as asserted and expands the query instead, typically into a union of conjunctive queries that between them cover every way the answer could be derived. Nothing is duplicated on disk and deletes are trivial. The cost moves to query time, and the rewriting can grow exponentially in the size of the query and the ontology, so a four-triple pattern over a rich TBox can compile into a union with hundreds of branches (Hogan et al., 2021, Knowledge Graphs, ACM Computing Surveys 54(4)).

The hybrid that actually ships is materialising the cheap closure (RDFS plus a slice of OWL RL) at load, and rewriting the expensive parts on demand.

What entailment will never do for you

Entailment is monotonic: adding triples can never retract a conclusion. That single property rules out an entire category of thing people expect ontologies to do.

Declare that every :Patient has at least one :birthDate with an OWL cardinality restriction, then load a patient with no birth date. OWL does not report a problem. It concludes that the birth date exists and is simply not named. Declare :hasSSN functional, then assert two different values for one person. Again no error: OWL concludes the two values denote the same resource. These are not bugs in reasoners; they are the correct reading of an open-world, monotonic semantics.

Checking that the data in front of you has the shape you require is a different job with a different formalism, which is what SHACL exists for.

When it breaks

Deletion under materialisation. The asymmetry between load and retract is the most common operational surprise. Pipelines that rebuild the graph nightly never notice; pipelines that stream corrections do, immediately.

Silent incompleteness on profile violation. A single axiom outside the chosen profile means the engine's algorithm is no longer complete for that ontology. Several stores degrade quietly rather than refusing the load, so queries return fewer rows than they should and nothing in the logs says why.

Equality closure explosion. owl:sameAs is reflexive, symmetric and transitive, so a cluster of \(n\) co-referent IRIs licenses on the order of \(n^2\) equality triples, and every property on any member must be replicated onto every other member. One over-eager interlinking job can multiply a graph.

Counting becomes ambiguous. COUNT over a materialised graph counts derived triples as well as asserted ones. Whether that is the number you wanted depends on the question, and the query gives you no way to tell the two apart unless the derived triples were kept in a separate named graph.

Inconsistency is global. A single contradiction makes every statement entailed, so one bad axiom does not degrade answers locally, it invalidates all of them.