6. How the Machinery Actually Works

About 28 minutes spoken, 4,071 words. Plain text for a reader app: 06-how-the-machinery-works.txt

This is the sixth of ten talks about ontologies. Last time we walked the standards stack, and I offered you a way of remembering it: read each layer as an answer to a requirement set out in the Scientific American article of two thousand and one, with the caveat that the mapping is my reconstruction rather than a chain of cause and effect. Today we open the box. What does a reasoner actually compute, and why does it sometimes behave in ways that seem, on first contact, completely mad?

I’ll warn you that this is the most technical lecture in the series. There’s no code and nothing to look at, so I’ll keep every example small enough to hold in your head while walking.

Start with the mental model, which comes from description logics.

A description logic — DL for short, and those two letters are all over this material — is a formal knowledge-representation language, more expressive than propositional logic and less expressive than first-order logic. They come as a family, and that family is the logical foundation of OWL, the Web Ontology Language, and of its profiles. The mental model has three pieces and they’re simpler than the name suggests.

Concepts denote sets. When you write a class called Aircraft, you’re not naming a thing. You’re naming the set of all aircraft. Roles denote sets of ordered pairs. When you write a property called assignedTo, you’re naming the set of all pairs where the first element is assigned to the second. And individuals denote specific members. That’s it. Sets, pairs, and members.

From those three pieces you build compound descriptions. The set of things that are aircraft and have more than one aisle. The set of things that are flights whose assigned aircraft is a widebody. Description logics are, in essence, a compact notation for describing sets by their properties rather than by listing them, plus a machine that computes the relationships between those sets.

That austere little notation has travelled: the literature lists applications in ontologies, the Semantic Web, biomedical informatics, defence, climate modelling, and industrial knowledge graphs. Sets, pairs, and members, in every one of those.

Your ontology then splits into two parts, and this distinction is worth learning because the whole literature uses it.

The TBox is the terminology. General statements about concepts. Every widebody is an aircraft. No aircraft is a crew member. Every flight has exactly one assigned aircraft. These are the rules of your world.

The ABox is the assertions. Facts about specific individuals. This particular aircraft, tail number such-and-such, is a widebody. This flight is assigned to it. These are the contents of your world.

TBox is the schema-ish part, ABox is the data-ish part, and I say “ish” because the analogy leaks, as you’re about to see.

So what does a reasoner compute? Five things, mainly.

Subsumption. Is concept A a subset of concept B, in every possible interpretation that satisfies your axioms? This is the big one, and it’s less obvious than it sounds, because the answer is often yes for reasons nobody stated. Suppose you define a LongHaulFlight as a flight with duration over six hours, and separately define a TransatlanticFlight as a flight from Europe to North America, and you’ve said elsewhere that every Europe-to-North-America route has duration over six hours. The reasoner will tell you that every transatlantic flight is a long-haul flight. Nobody wrote that. It follows.

Classification. Do subsumption for every pair of concepts and you get the complete inferred hierarchy. This is the standard operation you run in an editor: you author a set of definitions in whatever order made sense to you, press the button, and the reasoner rearranges them into the hierarchy your axioms actually imply. When the result surprises you, one of your axioms says something you didn’t mean. I’d argue that’s the most valuable error message in the field.

Instance checking. Is this individual a member of that concept? Same logic, one level down.

Relation checking. Does this pair of individuals stand in this role? Instance checking asks whether a thing is in a set; relation checking asks whether a pair is in a set of pairs. Same question, one shape over — and it’s an inference, so the answer can come back yes when nobody asserted that pair.

Consistency. Is there any possible interpretation that satisfies all your axioms at once? If not, your ontology is inconsistent — you’ve described a world that cannot exist. A closely related service, which reasoners list separately, is finding unsatisfiable concepts: classes that can have no members in any interpretation at all.

Now. The open-world assumption. This is the idea that breaks people, and I want to spend real time on it, because every strange reasoner behaviour you’ll ever meet comes from here.

A database operates under the closed-world assumption. If a fact is not in the database, it’s false. You ask whether Melissa has a manager, the manager column is null, the answer is no. That’s not a limitation, it’s the design. A database is a record of what’s the case, and it’s authoritative over its domain.

OWL operates under the open-world assumption. If a fact is not stated, it’s unknown. Not false. Unknown. You ask whether Melissa has a manager, nothing says she does, and the answer is: I don’t know, and neither do you.

Here’s why, and it goes straight back to last time. The Semantic Web was built for a web of strangers publishing independently. Your graph is a fragment. The fact you’re missing might be on a server in Osaka that you’ll merge with tomorrow. Under those conditions, concluding “no” from “not stated” is simply invalid, so the logic refuses to do it.

Let me give you the consequence, because it’s the one that generates support tickets.

You write an axiom saying a valid order must have at least one line item. You load an order with no line items. You run the reasoner expecting a complaint. The reasoner reports that everything is fine. Why? Because you didn’t state a constraint. You stated a fact about the world: orders have line items. The reasoner reads your data, sees an order, and concludes that there exists at least one line item for it which you have not yet told it about. It has done exactly what you asked. It just wasn’t what you wanted.

Here’s a second case, and I prefer it to the first because it isn’t my illustration — it’s documented behaviour, written down by the people who maintain a production reasoner. You define a named class as equivalent to a restriction saying all the values of some property must be of a certain kind. Everyone assigned to this flight is cabin crew, say. Things with no value at all for that property may then get classified under your named class: the flight with nobody assigned to it comes back as one of your all-cabin-crew flights. My reading of why is that a condition on all the values of a property is trivially satisfied when there are no values — but the behaviour is the documented part and the gloss is mine. Note the shape of it either way. The surprise arrives not as an error but as a membership nobody wanted, sitting in a hierarchy that classified without complaint.

That’s why SHACL exists — the Shapes Constraint Language, a recommendation from the World Wide Web Consortium for describing a graph of RDF, the Resource Description Framework, by putting constraints on its content, its structure, and its meaning. And it’s why the split between inference and validation is not a matter of taste. When you want the machine to find what follows, use a reasoner. When you want the machine to find what’s missing, use SHACL: you write shapes, you say what they target, you feed the engine a data graph and a shapes graph, and it hands back a validation report with a severity on every finding. Reaching for the wrong one produces either a serene silence where you expected an error, or an error where the system was being perfectly reasonable.

A word on how shapes are put together, because it decides where a constraint actually bites. Shapes come in two kinds. Node shapes constrain nodes; property shapes constrain the values you reach by following a path. The constraints are the vocabulary you’d expect — datatype, minimum count, length, ranges, patterns, logical combinations. Targeting is the part people get wrong, in two documented ways. Targeting a class also targets the members of its subclasses, through the subclass relation, so a shape written for one class is quietly validating everything underneath it. And when a property shape is included inside a node shape, that property shape’s own targets are ignored. Where you put a shape changes what it validates, so if your shapes fire on things you never meant, or don’t fire at all, look there before you look at the constraints.

And one honest complication, because I’ve drawn the split too cleanly. Reasoners infer, SHACL validates — that’s the working heuristic, and SHACL doesn’t fully respect it. Alongside its built-in constraints it has extension mechanisms, and rules of its own for inferring new statements. So it’s a good way to decide which tool to reach for, not a wall between two kinds of technology.

There’s a companion assumption that catches people just as often, and it’s called the no unique name assumption. In a database, two different primary keys are two different rows. In OWL, two different identifiers might name the same thing. You have a person identified one way in the human resources system and another way in the badge system. Unless somebody asserts they’re different, the reasoner treats it as an open question. And it can run the other way too. If you say a flight has exactly one assigned aircraft, and your data shows two, a reasoner will not report an error. It will conclude that those two names denote the same aircraft. Which may be true. It may also mean your integration has a bug that you will now never see.

Notice that both assumptions are correct for the environment they were designed for and wrong for the environment most people use them in. The standards were built for an open web of strangers. Most deployments are inside one organisation where the data is authoritative and missing means missing. That mismatch is, I’d argue, the single largest source of frustration with this technology, and it’s a mismatch of context rather than a defect.

Now, the trade-off that shapes everything else: expressivity against complexity.

The more you can say in a language, the harder it is to compute with. This isn’t an implementation problem you can engineer your way past. It’s a mathematical property of the languages, and the sentence that states it is short: adding operators, and letting the concept hierarchy get more complicated, usually increases the computational complexity of inference. Negation, disjunction, cardinality restrictions, inverse properties — each one costs you. And past a certain point the language becomes undecidable, meaning no program can be guaranteed to give you an answer at all.

Description logic research charted that landscape in detail: for each combination of operators, how hard is reasoning, and is it decidable? Many of the core reasoning problems in the family are decidable, and they’re decidable because the languages were deliberately balanced to keep them so. That map is what OWL’s profiles are built from.

OWL two defines three of them, and the specification names them by letters: EL, QL, and RL. Each one restricts what you’re allowed to say in order to buy one stated benefit.

EL buys reasoning over large ontologies. ELK is a reasoner built for that profile, and it shows you what the restriction is worth: it implements a polynomial-time procedure for a fragment of OWL two EL, it can put several processor cores on the job at once, and when your axioms change it recomputes only the results that depended on them, which can bring a class-hierarchy update to something near real time. One wrinkle there, which I mention because it stands for a whole class of them: ELK’s standalone command-line tool cannot parse RDF in XML, the Extensible Markup Language — the syntax conformant OWL two tools are required to be able to exchange. It takes OWL two Functional-Style Syntax and nothing else, so you convert first, and large classifications may want a bigger Java heap.

QL buys relational querying. It’s the profile for the case where the data you care about lives in a relational database and you want to ask ontology-shaped questions of it.

RL buys rule-based processing of RDF graphs — which is to say you can run the thing as rules over the data rather than calling a reasoner at all. The specification attaches a caveat to that which is worth memorising. Rule-based OWL two RL reasoning over an arbitrary RDF graph is sound, but it may be incomplete unless the ontology meets the RL structural definition and the query conditions the spec sets out. Sound means it will not tell you anything false. Incomplete means it may not tell you everything true.

And then there’s full OWL two DL, with the expressive power and the worst-case complexity to match.

Two things about it that the profile story hides. The first is that OWL two DL charges for its decidability in the grammar. It imposes syntactic conditions on what counts as a legal OWL two DL ontology, and the example the specification’s own overview reaches for is this: a transitive property cannot appear in a number restriction. If parthood is transitive, you are not permitted to say a thing has exactly three parts. Not discouraged, not slow — not allowed. As I read it, that’s the decidability boundary drawn in advance, in what you may write down, rather than met at reasoning time by a tool that gives up.

The second is that OWL two has two semantics rather than one. The direct semantics supports OWL two DL and description-logic reasoning; the RDF-based semantics applies to any OWL two ontology taken as an RDF graph. So when a reasoner tells you which semantics it works to, that isn’t paperwork. It’s saying which of two readings of your file its answers are about.

Which brings us to two reasoners to know by name. HermiT is built on a hypertableau calculus, works to the direct semantics, and its authors say it passes all the OWL two conformance tests for direct-semantics reasoners. It also documents support for DL Safe rules, and the limit on those belongs right beside the RL caveat, because it’s the same bargain in different clothes: reasoning with DL Safe rules is incomplete when the ontology has property chains or transitivity axioms and the rule bodies use complex properties. Sound but possibly incomplete is not a tax the weak profiles pay for being weak. It turns up on a full DL reasoner too. Openllet is a Java reasoner for OWL two DL that will check whether an ontology is consistent, find the unsatisfiable concepts, compute the class hierarchy, check whether an axiom is entailed, explain an inference, and answer queries.

Both do genuinely impressive work, and both can fall off a cliff. The triggers are documented — Openllet ships a linting tool whose entire job is to find them, and the list it works from is this. General concept inclusions. Large disjunctions. Large cardinalities. Interacting existential restrictions. And large sets of assertions that individuals are all different from one another. Those are the constructs that create nondeterminism, generate extra individuals, or run the memory up in a tableau-based reasoner. So when an ontology that classified in two seconds stops finishing overnight, the diagnostic is not “reasoners are slow.” It’s: which one of those did I just add? And the honest answer is often that you have to remodel, because that linting tool warns you in as many words that its own automatic repairs are not semantically equivalent to the constructs they replace, and that several of its findings are warnings only.

That question has a limit, and the same tool draws it. It distinguishes modelling patterns that live inside a single axiom from patterns established across a whole ontology. The first kind you can point at. The second exists only in aggregate — no single axiom is the culprit, the shape of the thing is — and for those, I’d say the useful question isn’t what you added last week but what the ontology has been slowly turning into.

So how do you choose? Not by expressive power. By workload. What questions do you need answered, how big is the ontology, how big is the instance data, and how often does it change? The overview specification puts the rule plainly: pick EL, QL, or RL when its stated trade-off matches your application. A very large terminology with no instance data wants EL. A model sitting over a relational store wants QL. A pipeline running rules across a graph wants RL. Full DL is for when you genuinely need the expressive power and can pay for it.

A caveat about that document, since I’ve been quoting it all lecture. The OWL two overview is explicitly a non-normative overview and roadmap. The language is defined normatively across several other specification documents, and the overview says in as many words that later ones may supersede it. It’s the right map. It isn’t the territory, and conformance decisions don’t live in it.

And the wider class of wrinkle I flagged at ELK, quickly, because it decides more afternoons than the theory does. Openllet has required Java eleven since its two point six point five release and its documented Protégé plugin wants a Protégé built on the five point one line of the OWL programming interface; HermiT’s documented release is one point three point eight, on version three point four point three of that same interface. Serialisations are spelling and convert freely. Versions are not spelling.

Now, something about what reasoners are actually good for in practice, because there’s a gap between the textbook pitch and the working reality.

The textbook pitch is that the reasoner derives valuable new knowledge at query time. That happens, and it’s real, particularly in classification-heavy domains.

The working reality, in my reading of how successful projects use this, is that the reasoner is most valuable as a contradiction detector during authoring. You have a hundred people editing a large ontology over ten years. Somebody adds an axiom in one branch that contradicts an axiom added six years ago in another. No human will catch that. The reasoner catches it every time, in the build. Treat classification as a continuous integration check on meaning, and the technology earns its keep even if you never run a single inference in production.

There’s a companion habit on the authoring side, and it turns a classified ontology from a wall of inferred parents into something you can interrogate. Protégé Desktop has a feature called the DL Query tab — shipped as both a tab and a view widget, in version four, version five, and later — which searches a classified ontology using class expressions written in Manchester OWL syntax. A class expression is just the compound description we built at the start of the lecture, written down: things that are aircraft and have more than one aisle. You describe a set, and it hands you back what falls into it. Because it works from the inferred relationships rather than the asserted ones, you can ask for the subclasses and superclasses of an expression nobody ever named, and get answers nobody ever typed.

The workflow is short. Start a reasoner — FaCT plus plus, or HermiT — to classify the active ontology, confirm the inferred hierarchy is populated, enter your expression, choose which kinds of result you want back. And if the query looks right, you can add it to the ontology as a newly named defined class. Dwell on that last move, because it’s the loop this whole technology exists for. You describe a set by its properties, you look at what falls into it, and only when the membership looks right do you give the set a name. Definition after inspection, rather than definition and then hope.

Two documented ways it goes wrong. Queries run only on a classified ontology, so until you’ve run the reasoner there is nothing to query. And matching individuals aren’t shown unless the individuals result option is ticked — the exact recipe for a query that looks correct, is correct, and returns nothing. There’s a broader tell too: if the inferred hierarchy contains only Thing and nothing beneath it, that isn’t an ontology with no structure. That’s classification having failed.

Let me give you two more things that come up the moment you use a reasoner in anger.

The first is explanation, and it’s the feature that turns a reasoner from a curiosity into a tool you can work with.

When a reasoner tells you your ontology is inconsistent, that’s useless on its own. Your ontology has four thousand axioms. Which ones are fighting? So the reasoners implement explanation. ELK will show you, step by step, how a logical consequence follows from your axioms. Openllet lists explaining inferences as one of its services alongside consistency and classification. You point at the conclusion and the machine walks you back to what produced it.

That’s the debugger. You get told that your class Widebody has been inferred to be equivalent to nothing — unsatisfiable, no possible members — and you ask for the explanation, and you get back three axioms. One says every widebody has more than one aisle. One says every aircraft in the regional fleet has exactly one aisle. And one, added by a colleague two years ago, says every widebody is in the regional fleet. Nobody could have found that by reading. The machine finds it in a second and hands you the three lines.

Which is why I’d say explanation, rather than inference, is what makes an ontology maintainable by more than one person over more than one year.

The second thing is the choice between computing entailments ahead of time and computing them when asked. This part is my own engineering reading rather than anything the specifications hand you, so take it as that.

You can run the reasoner once, write everything it derives into the store beside the statements you asserted, and then query the result with an ordinary engine that knows nothing about logic. That’s the shape the RL profile is built for. Queries get fast, and everything downstream is just data. What you pay is three things: the stored graph gets much bigger than the source you started from, updates get awkward, because adding one fact can entail many and retracting one means working out what depended on it, and you’re held to whatever profile your rule engine implements, with the sound-but-possibly-incomplete caveat we just went through.

Or you keep the reasoner in the loop and compute the entailments when somebody asks. Openllet is the worked example: it answers queries through Jena, through the OWL programming interface, or from its own command line, with the reasoner underneath the whole time. Nothing is stored twice, updates are trivially correct, and you get the full expressive power. And your query latency now depends on a reasoning problem whose worst case is the cliff I described a moment ago.

So, the claim to keep from this lecture.

Open-world semantics is the single idea that most often breaks a database engineer’s intuition, and every strange behaviour of a reasoner follows from it. Unstated means unknown, never false. That is why your reasoner will not complain about the order with no line item, why two identifiers can quietly turn out to be one aircraft, and why SHACL had to exist as a separate technology rather than as a feature of OWL. Everything else today — sets and pairs, TBox and ABox, the profiles and what each one costs — is machinery. That one assumption is the thing to carry out with you.

Next time, we put all of this into practice, and find out why an ontology project is really a governance project with a file attached.