Concept Hierarchies as Ordered Structures

A concept hierarchy is usually drawn as a tree, and the drawing misleads in two ways at once.

It is not a tree. Subsumption is a partial order, and partial is the operative word: Mammal and Pet stand in no relation at all, since some mammals are pets and some pets are not mammals. In the nine-concept hierarchy worked later, ten of the thirty-six pairs are incomparable. That is ordinary structure rather than a modelling error.

It is not closed. Ask for the most specific concept subsuming both Dog and Cat. The candidates are Thing, Animal, Mammal and Pet, and neither Mammal nor Pet subsumes the other, so there is no least one. The hierarchy has a pair with no join, which means it is a partial order but not a lattice, and that gap is exactly why description logics let you write $\text{Dog}\bigsqcup \text{Cat}$ rather than hoping a named concept happens to be it.

And the hierarchy you get out is not the one you drew. Assert that dogs are animals, define a dog owner and a pet owner by what they own, and a classifier concludes that dog owners are pet owners. Nobody wrote that. It follows because restricting over a smaller concept yields a smaller concept, and a reasoner computes everything the axioms force.

The unit ends on the difference that causes most trouble in practice: when a query comes back empty, a database is saying no and an ontology is saying I don't know.

The canonical statements above give the order, the bounds, the constructors and the open-world assumption. What follows is the scope of each, which is what decides an unfamiliar case.

Antisymmetry holds up to equivalence, not identity. If $C⊑D$ and $D⊑C$ then the two concepts have the same extension in every model, so they are logically equivalent, but they remain two names. Subsumption is therefore a partial order on equivalence classes, and a tool reporting Vehicle ≡ Conveyance has found exactly this.

Bounds are relative to the set of concepts in play. "The meet of $C$ and $D$" is ambiguous until the candidate set is fixed.

So "this hierarchy is not a lattice" is a statement about the vocabulary, not a defect in the logic. The constructors exist precisely to close the gap.

Monotonicity is what makes classification non-trivial. Each constructor preserves subsumption in its argument:

A classifier propagates asserted subsumptions through these rules and takes the transitive closure. Everything it reports is forced; nothing rests on what the names suggest.

Classification derives only what is entailed. A subsumption that reads as obvious from the names, Bird ought to be CanFly, will not appear unless an axiom forces it. Its absence is a missing axiom, not a failure of the reasoner.

The open-world assumption is about entailment, not about data quality. An ontology entails $A$, entails $\mathrm{\neg }A$, or entails neither. The third case is common and is not resolved by adding more individuals; it is resolved by asserting an axiom that settles it. A database has no third case, which is the entire difference.

A caution about finite extensional models. Illustrating these ideas by fixing a domain and computing extensions as sets is faithful for the order structure and misleading for the semantics: computing membership from a finite table treats an absent edge as false, which is the closed-world reading. Such a model demonstrates meets, joins and derived subsumptions correctly, and cannot by itself demonstrate open-world behaviour.

Incomparability is the normal case, not the exception. Two concepts are comparable only when one's instances are all instances of the other. Mammal and Pet fail that in both directions simultaneously, and so do most pairs drawn from different classification axes, species and role, material and purpose, shape and function. Counting over a nine-concept hierarchy gives ten incomparable pairs out of thirty-six. A tree diagram cannot show this, which is why the diagram misleads.

Missing bounds follow directly. To find the join of Dog and Cat, collect every concept subsuming both: Thing, Animal, Mammal, Pet. For a join to exist, one of these must be subsumed by all the others. It must be the least. Mammal and Pet are incomparable, so neither qualifies, and no join exists among the named concepts.

The same failure happens downward. Mammal and Pet have lower bounds Dog, Cat and Nothing; Dog and Cat are incomparable, so there is no greatest, and no meet.

So the hierarchy is a partial order and not a lattice, and the cause is precisely the incomparability that the first paragraph called normal. This is the argument for constructors. Writing $\text{Dog}\bigsqcup \text{Cat}$ supplies the join by construction, and $\text{Mammal}\sqcap \text{Pet}$ supplies the meet, without requiring anybody to have coined a name.

Why classification adds edges you did not draw. Assert $\text{Dog}⊑\text{Animal}$ and define

Nothing states that dog owners are pet owners. It follows anyway: the existential restriction is monotone, so $\mathrm{\exists }\text{hasPet}.\text{Dog}⊑\mathrm{\exists }\text{hasPet}.\text{Animal}$, and conjoining Person to both preserves it. On the worked model the extensions confirm it, DogOwner is $\{4,9\}$ and PetOwner is $\{4,5,9,10\}$.

The reasoner is not being clever. It applies the monotonicity rules and closes transitively, and the result is often a hierarchy the author did not intend to describe.

**Why what it does not derive matters as much.** On the same model, HappyPetOwner is $\{4,5,9\}$ and is not subsumed by DogOwner $=\{4,9\}$, because individual 5 owns a cat. If you expected that subsumption, the fix is an axiom, not a different tool.

And why an empty answer is not a negative answer. Individual 11 is a Person with no asserted pet. A database says: not a pet owner. An ontology says: nothing entails that they are, and nothing entails that they are not. Both answers are empty and they mean different things.

A product catalogue. Laptop, Portable, BusinessDevice. A laptop is portable and it is also a business device; portable and business device are incomparable, since a portable speaker is neither and a desktop workstation is the second and not the first. Classification axes multiply, and every additional axis produces more incomparable pairs. This is the ordinary shape of a catalogue and the reason a single tree of categories fails within about three levels.

A file system. Directories form a genuine tree: each entry has exactly one parent and any two paths have a nearest common ancestor. This is a partial order that is nearly a lattice, and its familiarity is what makes people expect concept hierarchies to behave the same way. The difference is that a file belongs to one directory by construction, whereas a concept can specialise several others at once.

Java class extension against interface implementation. Single inheritance of classes gives a tree; interfaces give a partial order with genuine incomparability, and a class implementing several unrelated interfaces has no single nearest supertype. The language designers chose the first to avoid the diamond problem, which is the practical form of a missing meet.

A medical terminology. SNOMED concepts are defined by their properties, and classification derives subsumptions no author wrote: a concept defined as an infection of the lung is placed under both infections and lung disorders automatically. The hierarchy is maintained by asserting definitions rather than edges, and the edges are computed, which is the only tractable way to keep hundreds of thousands of concepts consistent.

A permissions model. Roles with sets of granted actions, ordered by containment. Two roles with overlapping but distinct grants are incomparable, and the join, a role granting exactly the union, often does not exist until someone creates it. Systems that require a least upper bound end up manufacturing composite roles, which is the constructor solution arrived at independently.

---

What separates the second from the rest. Only the file system is a tree, and only because its structure is imposed rather than described. Wherever a concept can be specialised along more than one axis, incomparability appears immediately, bounds start going missing, and the choice is between inventing composite names and allowing expressions.

To verify that a hierarchy is a partial order.

1. Reflexivity: every concept subsumes itself. Automatic under the extensional reading, and worth confirming that the tool agrees.
2. Antisymmetry: find any pair subsuming each other. They are logically equivalent, so either merge them or record deliberately that two names denote one concept.
3. Transitivity: for each asserted chain $A⊑B⊑C$, confirm $A⊑C$ appears in the classified hierarchy.
4. Find one incomparable pair and keep it to hand. It is the counterexample to every claim that begins "since the hierarchy is a tree".

To compute a meet or a join.

1. Fix the candidate set, named concepts only, or named concepts plus expressions. The answer differs and the question is ambiguous without this.
2. For the meet of $C$ and $D$: list every concept subsumed by both. Then check whether one of them subsumes all the others. If exactly one does, it is the meet; if none does, there is no meet in that candidate set.
3. For the join: list every concept subsuming both, and look for one that all the others subsume.
4. Do not read either off a diagram. A drawn hierarchy shows asserted edges and hides incomparability, so the nearest-looking common ancestor is frequently not a least upper bound.

To predict what a classifier will derive.

1. List the asserted subsumptions between atomic concepts.
2. Propagate through each constructor using monotonicity: from $D⊑C$ infer $\mathrm{\exists }r.D⊑\mathrm{\exists }r.C$, and $D\sqcap E⊑C\sqcap E$.
3. Close transitively.
4. Compare against your expectations. A subsumption you expected and did not get is a missing axiom. A subsumption you did not expect and did get is usually correct and worth understanding before it is removed.

To diagnose an unexpected classification result.

1. Ask whether the conclusion is forced by the axioms rather than whether it matches the names. Bird will not be subsumed by CanFly unless something says so.
2. Look for an over-strong axiom if a concept has become equivalent to another or has been found unsatisfiable: a domain or range restriction, or a disjointness assertion, usually did it.
3. Check whether the missing conclusion needs a closed-world reading. "Every person with no recorded pet is not a pet owner" is not entailed and never will be.

Checks. Confirm the classified hierarchy is transitively closed. Confirm no concept is equivalent to Nothing unless intended, unsatisfiability is nearly always a modelling error. And before reporting that a query returned nothing, determine whether the ontology entails a negative answer or entails neither, because those are different findings and only the second is about missing information.

The hierarchy. Twelve individuals, numbered 1 to 12. Each concept is given by the individuals it applies to.

Step 1: subsumption is a partial order. $C$ subsumes $D$ exactly when $D$'s extension is contained in $C$'s. Containment is reflexive, antisymmetric and transitive, and checking all nine concepts confirms each property holds.

Step 2: it is partial. Ten of the thirty-six pairs are incomparable:

Mammal–Bird, Mammal–Pet, Bird–Dog, Bird–Cat, Bird–Pet, Bird–WorkingAnimal, Dog–Cat, Dog–WorkingAnimal, Cat–WorkingAnimal, Pet–WorkingAnimal.

Take Mammal and Pet: individual 4 is a mammal and not a pet, individual 6 is a pet and not a mammal. Neither contains the other.

Step 3: bounds where they exist.

For Dog and Pet, Dog's extension $\{1,2\}$ sits inside Pet's $\{1,2,3,6\}$, so the pair is comparable and the bounds are the two concepts themselves.

Step 4: two pairs with no bound.

Mammal and Pet have no meet. The concepts subsumed by both are Dog $\{1,2\}$, Cat $\{3\}$ and Nothing. For a meet, one of these must subsume the other two, but Dog and Cat are incomparable. There is no greatest lower bound.

Dog and Cat have no join. The concepts subsuming both are Thing, Animal, Mammal $\{1,2,3,4,5\}$ and Pet $\{1,2,3,6\}$. For a join, one must be subsumed by all the others, but Mammal and Pet are incomparable. There is no least upper bound.

So this hierarchy is a partial order and not a lattice. Exactly two of the thirty-six pairs are responsible. The remedy is not to add more names but to allow expressions: $\text{Dog}\bigsqcup \text{Cat}$ is the join, and $\text{Mammal}\sqcap \text{Pet}$ is the meet, once the constructors are available.

---

Step 5: classification derives what nobody asserted. Add a role hasPet with pairs $(4,1),(5,3),(9,2),(10,6)$, a concept Person $=\{4,5,9,10,11\}$ and Happy $=\{4,5,9\}$. Define

Computing the extensions:

The first follows from $\text{Dog}⊑\text{Animal}$ alone: the existential restriction is monotone, so restricting over the smaller concept gives the smaller concept. The third fails because individual 5 owns a cat, if it was expected, the fix is an axiom rather than a different reasoner.

---

Step 6: what this model cannot show. Individual 11 is a Person with no hasPet pair. The table above computes PetOwner as $\{4,5,9,10\}$, excluding 11, because computing extensions from a finite table treats an absent edge as false. That is the closed-world reading.

Under OWL's open-world semantics the ontology entails neither PetOwner(11) nor its negation: 11 simply has no asserted pet, which is not the same as having none. The extensional model above is a faithful device for the order structure and for derived subsumptions, and it is the wrong device for this point, which has to be argued from the semantics rather than read off the table.

A tree against a partial order.

The tree's structure is imposed by construction; the hierarchy's is described, and description along several axes at once produces incomparability immediately.

Bounds among named concepts against bounds as expressions.

The same hierarchy is described both ways. Whether it is a lattice depends entirely on what is allowed into the candidate set, which is why the question needs the candidate set stated.

Asserted against derived.

The second follows from the first by monotonicity of $\mathrm{\exists }r.C$; nobody wrote it and a classifier reports it. The third does not follow, and its absence is a missing axiom rather than a reasoner limitation, individual 5 owns a cat.

Open world against closed world, on the same question.

Is individual 11, a Person with no asserted pet, a pet owner?

Both return nothing. Reading the second as the first is the most common error in moving between them, and it is a difference in semantics rather than in how complete the data happens to be.

A reasoner against a validator.

A reasoner answers what follows from the axioms; it will not complain that a required property is absent, because absence is not a contradiction. Checking that every Person has a recorded name is a validation task with closed-world semantics, which is why a separate mechanism such as SHACL exists rather than that job being given to the classifier.

Reading a nearest common ancestor off the diagram. A drawn hierarchy shows asserted edges and cannot show incomparability. Dog and Cat appear to sit under Mammal, and Pet also subsumes both, so the least upper bound does not exist among the named concepts. Compute bounds from the sets of candidates; the picture will not tell you.

Treating an empty query result as a negative answer. An ontology entails $A$, entails $\mathrm{\neg }A$, or entails neither, and the third case is common. Individual 11 has no asserted pet, so the ontology does not entail that they own one, and does not entail that they do not. A database returning no rows means something stronger, and conflating the two produces reports that confidently assert absences nobody stated.

Expecting a reasoner to catch missing data. For the same reason, a classifier will not flag that a Person lacks a required property: absence is not a contradiction. Validation against a shape or a schema is a different task with different semantics, and assigning it to the reasoner produces silence rather than errors.

Inferring a subsumption from the names. Bird will not be classified under CanFly unless an axiom says so, however obvious the reading. A missing conclusion is evidence about the axioms and not about the tool.

---

Two failures that produce wrong answers rather than no answer.

An over-strong domain or range restriction. Declaring that hasPet has domain Person means anything with a pet is inferred to be a person, not that non-persons are rejected. Authors who intend a constraint frequently get an inference instead, and the ontology then quietly classifies a Company as a Person.

An unintended equivalence. Two concepts subsuming each other are logically identical, and a classifier will report them as equivalent. Where that was not intended it usually traces to a definition that is too loose. An equivalence axiom written where a subclass axiom was meant.

---

And one about illustration. Computing extensions over a fixed finite domain, as the worked example does, is faithful for the order structure and for derived subsumptions. It is not faithful for the open-world semantics: a table treats an absent edge as false, which is exactly the closed-world reading. The distinction has to be argued from what the semantics says, and it cannot be read off a model that has already assumed the answer.

Clinical terminologies. SNOMED CT holds hundreds of thousands of concepts, and its hierarchy is not maintained by drawing edges. Concepts are given definitions, an infection caused by a bacterium, located in the lung, and a classifier computes the placement, so a new concept lands under every ancestor its definition entails. Maintaining that by hand would be impossible, and the derived edges are the product.

Gene and protein annotation. The Gene Ontology's relations are transitive, so an annotation to a specific process implies annotations to every more general one. Analyses rely on that closure being computed rather than stored, and a term's incomparability with another is meaningful information about the biology.

Schema.org and search. Publishers annotate pages with types, and consumers reason over the hierarchy to decide whether a page describes something they care about. The open-world assumption fits: a page that does not state a property has not denied it, which is the right reading for the web and the wrong one for an inventory system.

Configuration and product modelling. A valid configuration is one satisfying a set of constraints, and a description-logic reasoner can detect that a combination of options is unsatisfiable, that the concept describing it is equivalent to Nothing. Finding that a marketable configuration is logically impossible is cheaper before manufacturing than after.

Access control. Role hierarchies are partial orders, and the composite roles organisations end up creating are joins that did not previously exist. Systems that compute permission closure from role subsumption get consistency for free; systems that store the closure get drift.

---

Each maintains a structure too large to check by hand, and each gains from having the consequences computed rather than asserted. The cost is that the computed hierarchy is only as good as the definitions: a missing axiom produces a missing edge silently, and an over-strong one produces an edge nobody wanted. Both failures are diagnosed by asking what the axioms entail rather than what the names suggest.