Concept Hierarchies as Ordered Structures

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.

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.

That a concept hierarchy is a tree, so every pair of concepts stands in some ancestor or descendant relation and every pair has a nearest common parent. Subsumption is a partial order, and partial means pairs may be incomparable: in a hierarchy of nine concepts including Mammal, Bird, Dog, Cat, Pet and WorkingAnimal, ten of the thirty-six pairs are incomparable, because a pet need not be a mammal and a mammal need not be a pet. Nor does every pair have a meet or a join among the named concepts. Mammal and Pet have lower bounds Dog, Cat and Nothing, none of which subsumes the others, so there is no greatest lower bound; Dog and Cat have upper bounds Thing, Animal, Mammal and Pet, and neither Mammal nor Pet subsumes the other, so there is no least upper bound. An ordinary hierarchy is therefore a partial order that is not a lattice, which is precisely why description logics supply conjunction and disjunction constructors rather than relying on the named concepts to supply bounds.

That a query returning no results against an ontology means the answer is no, as it would against a database. Under the open-world assumption an ontology records what is known, so an unasserted fact is unknown rather than false. Asking whether a person owns a pet, when nothing has been asserted about their pets, returns no entailment: the ontology entails neither that they do nor that they do not. A relational database answering the same query returns no rows and that is read as a negative answer, because closed-world semantics treat absence as negation. The consequence for engineering is concrete. A reasoner will not report a constraint violation merely because required information is missing, so validation of completeness needs a separate mechanism such as SHACL rather than the reasoner itself.