Description Logic: Concepts, Roles, and Individuals

📍 Where we are: Part II · Description Logic — Chapter 4. The previous chapter, TBox and ABox, split the ontology into a schema box of general rules and a data box of ground facts; now we open the schema box and ask the question it left hanging — in exactly what language are those axioms written, and what do they mean?

An ontology is only as trustworthy as the language its axioms are written in. Chapter 3 sorted the academic world into a TBox (the schema — general rules like "a professor is a researcher") and an ABox (the data — ground facts like "alice is a professor"), but it treated the axioms themselves as suggestive prose. This chapter makes them exact. The language is a description logic (DL), a small, carefully chosen fragment of first-order logic (FOL), and it is small on purpose: three kinds of vocabulary, a handful of ways to combine them, and a meaning so precise that a machine can hold every sentence up against a model and report what must follow.

The simple version

Imagine describing everyone in a department using only three kinds of word. Nouns for kinds — "professor," "student," "person" — each naming a set of people. Verbs that link two people — "advises," "cites" — each naming a relationship. And proper names — "alice," "bob" — each pointing at one specific person. With just those three word-kinds, plus two ways to glue them together ("a professor who advises some student"), you can say a surprising amount with no ambiguity — and a machine can check every sentence against the actual roster and tell you what else has to be true. That disciplined three-word language is a description logic.

What this chapter covers

• The three vocabularies — concept names (sets of individuals), role names (binary relations between individuals), and individual names (the things themselves); the academic world declares exactly 10 concepts and 6 roles.
• The constructors, decoded before the symbols — conjunction $C \sqcap D$ (in both sets at once), existential restriction $\exists r.C$ (related by $r$ to some $C$), and the two extremes ⊤ (everything) and ⊥ (nothing).
• Model-theoretic meaning — an interpretation $\mathcal{I} = (\Delta^{\mathcal{I}}, \cdot^{\mathcal{I}})$ sends every concept to a set and every role to a relation, and each constructor has one fixed set-theoretic reading.
• Axioms, made exact — a general concept inclusion $C \sqsubseteq D$ holds in a model iff $C^{\mathcal{I}} \subseteq D^{\mathcal{I}}$, and it is entailed iff it holds in every model; role inclusions and role chains read the same way one level down.
• The surface syntax — how the companion's And, Some, Sub, Chain, and RoleSub builders assemble an axiom such as Professor ⊑ ∃advises.Student out of nested tuples.
• What a reasoner computes — the four standard tasks, subsumption, satisfiability, classification, and instance checking, and which line of the companion answers each.

A description logic in one picture: concept names map to sets, role names to relations, and individual names to points of a domain, with each constructor and each subsumption reading off as a plain set-theoretic fact. Original diagram by the authors, created with AI assistance.

The three vocabularies

A description logic starts from three disjoint alphabets [1]. A concept name is an atomic class of individuals — the DL counterpart of a unary predicate in first-order logic, a set of things. A role name is an atomic binary relationship — a binary predicate, a set of ordered pairs. An individual name is a constant that points at one specific thing. In first-order terms, Professor is the predicate $\text{Professor}(x)$, advises is the predicate $\text{advises}(x,y)$, and alice is a constant $a$. The whole of description logic is the study of what you can build and decide when you restrict FOL to exactly these three ingredients and a fixed menu of ways to combine them.

The academic world fixes its two schema-level alphabets in ontology.py as plain Python lists (lines 112–118):

CONCEPTS = [
    "Person", "Researcher", "Professor", "Student",
    "Paper", "Institution", "Topic",
    "Dean", "TenuredStudent", "TenuredStudentAdvisor",
]

ROLES = ["advises", "authored", "cites", "affiliated", "about", "grandAdvisor"]

That is the entire vocabulary above the data: 10 named concepts and 6 roles. The individuals are the third alphabet, and they come not from a hand-written list but from Volume 1's facts — 13 of them, alice, bob, p1, mit, and the rest (Chapter 3 showed how the ABox is built mechanically so it is provably the same world). Everything the reasoner concludes is stated purely in these names; the fresh symbols _N1, _N2 that normalization will invent later are internal scaffolding, deliberately excluded from the reported vocabulary.

The constructors, decoded before the symbols

Concept names on their own only let you name kinds. The power of a description logic is that you can build new, unnamed concepts out of old ones with a small set of constructors. The EL fragment — the one this ontology lives in — keeps exactly two, plus two constants. Here they are in words first, symbols second.

• Conjunction, written $C \sqcap D$ and read "$C$ and $D$": the individuals that are in both concepts at once. Professor ⊓ Student is everyone who is simultaneously a professor and a student.
• Existential restriction, written $\exists r.C$ and read "related by $r$ to some $C$": the individuals that have at least one $r$-neighbour lying in $C$. ∃advises.Student is everyone who advises at least one student. The role $r$ and the filler concept $C$ are both part of the constructor; changing either changes the set.
• Top, written ⊤ and read "everything": the concept every individual belongs to, the DL name for owl:Thing.
• Bottom, written ⊥ and read "nothing": the empty concept, owl:Nothing. No individual is ever a ⊥, so deriving that some named concept is contained in ⊥ is exactly how a reasoner reports "this class is impossible."

These four combine and nest freely: $\exists\text{advises}.(\exists\text{authored}.\text{Paper})$ is "advises someone who authored a paper," a compound the ontology actually uses. What EL pointedly lacks — negation $\lnot C$, disjunction $C \sqcup D$, the universal $\forall r.C$ — is the subject of the next chapter, and the reason this one stays computationally tame.

Model-theoretic meaning

Syntax without semantics is just decoration. What makes a description logic a logic is that every one of those symbols has a fixed, mechanical meaning given by a model [2]. The meaning is set-theoretic, and it hangs on a single object.

An interpretation is a pair $\mathcal{I} = (\Delta^{\mathcal{I}}, \cdot^{\mathcal{I}})$. The first component $\Delta^{\mathcal{I}}$ (read "delta-I") is a non-empty domain: the set of all things that exist in this particular world. The second, $\cdot^{\mathcal{I}}$ (read "the interpretation function"), is a dictionary that grounds every symbol in that domain:

• each concept name $A$ becomes a subset $A^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}}$ — the things that are an $A$;
• each role name $r$ becomes a binary relation $r^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}$ — the pairs the role connects;
• each individual name $a$ becomes one element $a^{\mathcal{I}} \in \Delta^{\mathcal{I}}$ — the thing it names.

From that base the two constants and the two constructors are forced, each by one equation. The constants are the extremes:

$$\top^{\mathcal{I}} = \Delta^{\mathcal{I}}, \qquad \bot^{\mathcal{I}} = \varnothing .$$

Conjunction is set intersection, and existential restriction is a one-step reachability set:

$$(C \sqcap D)^{\mathcal{I}} \;=\; C^{\mathcal{I}} \cap D^{\mathcal{I}},$$ $$(\exists r.C)^{\mathcal{I}} \;=\; \{\, x \in \Delta^{\mathcal{I}} \; : \; \text{there is a } y \text{ with } (x,y) \in r^{\mathcal{I}} \text{ and } y \in C^{\mathcal{I}} \,\}.$$

Read the second one slowly, because it is the heart of the logic. The colon inside the braces reads "such that"; the whole expression collects every domain element $x$ that can step along an $r$-edge to at least one $y$ that lies in $C^{\mathcal{I}}$. It is an existential — one witnessing neighbour is enough — which is exactly why the constructor is written with $\exists$. This decodes each constructor into pure set theory, so a machine can evaluate any compound concept in any interpretation with no ambiguity. The table collects the whole menu.

constructor	syntax	plain reading	semantics ($\cdot^{\mathcal{I}}$)
top	$\top$	everything	$\Delta^{\mathcal{I}}$
bottom	$\bot$	nothing	$\varnothing$
conjunction	$C \sqcap D$	both a $C$ and a $D$	$C^{\mathcal{I}} \cap D^{\mathcal{I}}$
existential restriction	$\exists r.C$	$r$-related to some $C$	$\{\, x : \exists y.\, (x,y) \in r^{\mathcal{I}} \wedge y \in C^{\mathcal{I}} \,\}$

Axioms, made exact

Now the payoff: an axiom is a constraint on which interpretations are allowed, and it too has a one-line set-theoretic meaning. The workhorse axiom is the general concept inclusion (GCI), written $C \sqsubseteq D$ and read "$C$ is subsumed by $D$." It holds in an interpretation exactly when the left set sits wholly inside the right one:

$$\mathcal{I} \text{ satisfies } C \sqsubseteq D \quad\iff\quad C^{\mathcal{I}} \subseteq D^{\mathcal{I}}.$$

An interpretation that satisfies every axiom of the TBox is a model of it. And the question a reasoner really answers is not "does this hold in one model" but "does it hold in all of them": the TBox entails $C \sqsubseteq D$, written $\mathcal{T} \models C \sqsubseteq D$, iff $C^{\mathcal{I}} \subseteq D^{\mathcal{I}}$ in every model $\mathcal{I}$ of $\mathcal{T}$. Entailment is subsumption that no legal world can escape — the difference between "these two circles happen to nest in the picture I drew" and "these two circles must nest in every picture consistent with the rules."

Role axioms read one level down, on pairs instead of elements. A role inclusion $r \sqsubseteq s$ means $r^{\mathcal{I}} \subseteq s^{\mathcal{I}}$: every pair the role $r$ connects, $s$ connects too. A role chain $r_1 \circ r_2 \sqsubseteq s$ (the ∘ reads "composed with") means

$$r_1^{\mathcal{I}} \circ r_2^{\mathcal{I}} \;=\; \{\, (x,z) : \exists y.\, (x,y) \in r_1^{\mathcal{I}} \wedge (y,z) \in r_2^{\mathcal{I}} \,\} \;\subseteq\; s^{\mathcal{I}}.$$

The academic world's one chain, advises ∘ advises ⊑ grandAdvisor, is precisely this: follow two advising edges in a row and you are forced into a grandAdvisor edge — the same two-hop composition Volume 1 computed by forward chaining, now stated as a schema law that binds every model.

The surface syntax: how an axiom is built

The companion writes these axioms in a tiny Python surface syntax, one builder per construct, so that the very code you read is the notation. Here are the five builders and the pretty-printer, verbatim from ontology.py (lines 53–75, then 98–106):

def And(*concepts) -> tuple:
    """The conjunction of two or more concepts: C ⊓ D ⊓ ..."""
    return ("⊓", tuple(concepts))


def Some(role: str, concept) -> tuple:
    """The existential restriction ∃role.concept — "related by *role* to some *concept*"."""
    return ("∃", role, concept)


def Sub(lhs, rhs) -> tuple:
    """A general concept inclusion (GCI): lhs ⊑ rhs."""
    return ("⊑", lhs, rhs)


def Chain(r1: str, r2: str, s: str) -> tuple:
    """A role chain (complex role inclusion): r1 ∘ r2 ⊑ s."""
    return ("∘⊑", (r1, r2), s)


def RoleSub(r: str, s: str) -> tuple:
    """A simple role inclusion: r ⊑ s."""
    return ("r⊑", r, s)

Every construct is a tagged tuple: a concept is either a bare string name, or a pair whose first element is a Unicode tag ⊓ or ∃, and an axiom is a triple tagged ⊑, ∘⊑, or r⊑. Watch axiom (4), Professor ⊑ ∃advises.Student, assemble itself. It is written in the TBox as a single nested call (ontology.py line 133):

    Sub("Professor", Some("advises", "Student")),

Inside out: Some("advises", "Student") returns the tuple ("∃", "advises", "Student") — the compound concept $\exists\text{advises}.\text{Student}$. Sub wraps that as ("⊑", "Professor", ("∃", "advises", "Student")) — the GCI whose left side is the name Professor and whose right side is that existential. Nothing is stringly-typed prose; the axiom is a data structure the reasoner will pattern-match on. The render function (lines 98–106) walks the same tuples backward into textbook notation, joining conjuncts with ⊓ and printing an existential as ∃role.filler. Running the module prints the entire TBox that way — this is the real, committed output of python3 ontology.py:

10 named concepts, 6 roles, 14 TBox axioms; ABox: 13 concept assertions, 18 role assertions over 13 individuals.

TBox:
  Professor ⊑ Researcher
  Student ⊑ Researcher
  Researcher ⊑ Person
  Professor ⊑ ∃advises.Student
  ∃advises.⊤ ⊑ Researcher
  Professor ⊓ Student ⊑ ⊥
  advises ∘ advises ⊑ grandAdvisor
  Dean ⊑ Professor
  Dean ⊑ ∃advises.Professor
  TenuredStudent ⊑ Professor
  TenuredStudent ⊑ Student
  TenuredStudentAdvisor ⊑ ∃advises.TenuredStudent
  ∃advises.∃authored.Paper ⊑ Person
  Person ⊓ ∃authored.Paper ⊑ Researcher

Every line is one of the three axiom shapes, and every symbol in it now has the exact semantics of the previous two sections. Professor ⊓ Student ⊑ ⊥ says the intersection $\text{Professor}^{\mathcal{I}} \cap \text{Student}^{\mathcal{I}}$ must be empty in every model — the disjointness that makes the two deliberately broken concepts, TenuredStudent and TenuredStudentAdvisor, impossible to satisfy.

What a reasoner computes

A description-logic reasoner is not a database that stores answers; it derives them from the semantics above. There are four standard tasks, and every one of them is defined by entailment — "holds in every model" — so each is a genuine deduction, not a lookup [3].

• Subsumption: does $\mathcal{T} \models C \sqsubseteq D$? Is one concept necessarily a subset of another? This is the atomic query; the others are built from it.
• Satisfiability: is there some model in which $C^{\mathcal{I}}$ is non-empty? Equivalently, is $C \sqsubseteq \bot$ not entailed? An unsatisfiable concept is a modelling bug — a class no individual could ever join.
• Classification: compute all subsumptions among the named concepts at once, yielding the concept hierarchy (the inferred one, not just the asserted edges).
• Instance checking: does $\mathcal{T} \cup \mathcal{A} \models C(a)$? Is the named individual $a$ forced to be an instance of concept $C$? This is the one task that consults the ABox, and it is subsumption's counterpart down at the data level.

The companion's el_completion.py answers the first three directly off a saturated data structure S, where S(A) holds every concept name that A is subsumed by. Its classification step is one biconditional (lines 35–36): "$A \sqsubseteq B$ iff $B \in S(A)$; a concept with $\bot \in S(A)$ is unsatisfiable." The reading functions make that literal — subsumes (lines 322–324) checks membership sup in S.get(sub, ...), and unsatisfiable (lines 273–276) collects every name with BOT in subs. The table pins each task to the line that answers it.

task	question	answer read off S	companion function
subsumption	$\mathcal{T} \models C \sqsubseteq D$?	$D \in S(C)$	subsumes (322–324)
satisfiability	is $C$ ever non-empty?	$\bot \notin S(C)$	unsatisfiable (273–276)
classification	the whole hierarchy	all $B \in S(A)$	classify / subsumptions (279–319)
instance checking	$\mathcal{T}\cup\mathcal{A} \models C(a)$?	ABox individual as a concept	(deferred; ABox reasoning, Part IV onward)

How that saturation is computed — normalization into four normal forms, then a fixpoint of completion rules — is the subject of Chapters 8 and 9 (Normalization and Completion Rules). This chapter only needs the shape of the answer: three of the four tasks reduce to reading a single membership off S, and that reduction is exactly what the small, model-theoretic language of concepts, roles, and individuals buys you.

The unsolved part

The honest tension of this whole chapter is a trade with no free side. The meaning we gave every symbol is set-theoretic and total — every constructor evaluates in every interpretation — so richer constructors are always available in principle: nothing in the semantics forbids negation $\lnot C$ (set complement), disjunction $C \sqcup D$ (set union), or the universal $\forall r.C$ ("all $r$-neighbours are $C$"). The catch is not meaning but cost. Add those operators and you climb the description-logic complexity ladder: subsumption in the expressive logic $\mathcal{SROIQ}$ behind OWL 2 DL is decidable but N2ExpTime-complete, worst-case doubly exponential, and the reasoners that decide it can stall on large ontologies. Keep only $\sqcap$ and $\exists$ — the two constructors this chapter chose — and subsumption stays decidable in polynomial time, which is why the same machinery classifies medical terminologies with hundreds of thousands of classes. Which constructors to admit is therefore not a matter of taste but the central engineering decision of the field, and it is genuinely unsettled: there is no single "right" description logic, only a Pareto frontier of expressivity against tractability, and every application has to pick its point on it. That choice is exactly where neuro-symbolic systems will later feel the strain, because a learned component cannot honour a guarantee the underlying logic was never given.

Why it matters

For neuro-symbolic AI, the value of a description logic is that it draws a crisp line a learner can be measured against. Because every concept denotes a set and every axiom is a set-inclusion, the answer to "does $C \sqsubseteq D$ follow?" is a hard yes or no with a proof behind it — the exact ground truth a robust-but-opaque neural model is trying to approximate when it embeds concepts as vectors and scores plausibility. A neural link predictor might rank TenuredStudent as a plausible class; the DL proves it unsatisfiable and can say why. Holding the two side by side — the provable subsumption and the learned guess — is only possible because the symbolic side committed to a precise, model-theoretic meaning first. Every later volume that fuses the two leans on this chapter's discipline: you cannot check a guess against a specification you never wrote down.

Key terms

• Description logic (DL) — a decidable fragment of first-order logic built from concepts (unary predicates), roles (binary predicates), and individuals (constants), closed under a fixed menu of constructors.
• Concept name / role name / individual name — the three disjoint alphabets: a set of individuals, a binary relation, and a constant pointing at one thing.
• Constructor — a way to build a compound concept: conjunction $C \sqcap D$, existential restriction $\exists r.C$, and the constants ⊤ (everything) and ⊥ (nothing).
• Interpretation $\mathcal{I} = (\Delta^{\mathcal{I}}, \cdot^{\mathcal{I}})$ — a non-empty domain plus a function sending each concept to a subset, each role to a relation, and each individual to an element.
• Model — an interpretation that satisfies every axiom of the TBox.
• General concept inclusion (GCI) $C \sqsubseteq D$ — the workhorse axiom; satisfied in $\mathcal{I}$ iff $C^{\mathcal{I}} \subseteq D^{\mathcal{I}}$, entailed iff that holds in every model.
• Role inclusion / role chain — $r \sqsubseteq s$ (every $r$-pair is an $s$-pair) and $r_1 \circ r_2 \sqsubseteq s$ (following two roles in a row forces the third).
• Entailment $\mathcal{T} \models \alpha$ — $\alpha$ holds in every model of the TBox; the "in all worlds" quantifier that turns a picture into a proof.
• The four reasoning tasks — subsumption, satisfiability, classification, and instance checking, each defined by entailment and each computable from the completion structure S.

Where this leads

We now have the language: three vocabularies, two constructors, a set-theoretic meaning for every symbol, and four tasks a reasoner can compute. The next question is which slice of that language to actually use — because the choice of constructors decides everything about whether reasoning is fast or hopeless. Choosing exactly conjunction $\sqcap$ and existential restriction $\exists$, and nothing else, defines the EL family, the deliberately impoverished logic that nonetheless classifies the largest ontologies ever built. The next chapter, The EL Family: Small Logic, Big Ontologies, makes that bet precise and runs it live on the academic world, saturating to a fixpoint in three rounds and reading off exactly 8 named subsumptions and 2 unsatisfiable concepts.