Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Description Logics & Ontologies

Decidable fragments behind the semantic web.

OWL, the ontology language of the semantic web, sits at a deliberately chosen point on a map where each added constructor can push reasoning from polynomial time to PSPACE, EXPTIME, NEXPTIME or beyond. Description logics are that map, together with the algorithms that navigate it.

What you’ll learn

  • Define the syntax and set semantics of ALC, TBoxes and ABoxes, and reduce subsumption, equivalence and instance checking to (un)satisfiability.
  • Run the ALC tableau algorithm, and prove that concept satisfiability without a TBox is PSPACE-complete.
  • Prove that EL subsumption is polynomial with a completion (saturation) algorithm, and explain why disjunction breaks it.
  • Place EL, DL-Lite, ALC, SHIQ, SHOIN and SROIQ on the expressivity–complexity map, connect them to OWL and its profiles, and explain open-world semantics.

ALC: syntax, semantics and reasoning tasks

For example, Parent≡Person⊓∃hasChild.Person\mathit{Parent}\equiv\mathit{Person}\sqcap\exists\mathit{hasChild}.\mathit{Person} (two inclusions) defines parents, and Parent⊓∀hasChild.Doctor\mathit{Parent}\sqcap\forall\mathit{hasChild}.\mathit{Doctor} describes parents all of whose children are doctors. On its own, ∀hasChild.Doctor\forall\mathit{hasChild}.\mathit{Doctor} also contains everyone without children. Translating ∃r.C\exists r.C as ∃y (r(x,y)∧C(y))\exists y\,(r(x,y)\wedge C(y)) maps ALC into first-order logic with just two variables, reused alternately, and ALC is a notational variant of the multimodal logic Km\mathbf K_m (Schild, 1991). All the standard reasoning tasks reduce to one:

C⊑TD  ⟺  C⊓¬D is unsatisfiable w.r.t. TC≡TD  ⟺  C⊑TD and D⊑TCT,A⊨a:C  ⟺  T,A∪{a:¬C} is inconsistent\begin{aligned}C\sqsubseteq_{\mathcal T}D&\iff C\sqcap\neg D\text{ is unsatisfiable w.r.t. }\mathcal T\\ C\equiv_{\mathcal T}D&\iff C\sqsubseteq_{\mathcal T}D\text{ and }D\sqsubseteq_{\mathcal T}C\\ \mathcal T,\mathcal A\models a:C&\iff\mathcal T,\mathcal A\cup\{a:\neg C\}\text{ is inconsistent}\end{aligned}
Every task is a satisfiability question, so a DL reasoner needs one engine: a procedure that decides whether a concept, or a whole knowledge base, has a model.
Check your understanding

Which ALC concept is unsatisfiable, that is, empty in every interpretation?

  1. ∀r.A⊓∀r.¬A\forall r.A\sqcap\forall r.\neg A
  2. ∃r.A⊓∃r.¬A\exists r.A\sqcap\exists r.\neg A
  3. ∃r.A⊓∀r.¬A\exists r.A\sqcap\forall r.\neg A
  4. ∀r.⊥\forall r.\bot
Show the answer

C. ∃r.A⊓∀r.¬A\exists r.A\sqcap\forall r.\neg A

An element of ∃r.A\exists r.A has an rr-successor in AA, and ∀r.¬A\forall r.\neg A forces that same successor into ¬A\neg A: a clash. The other three concepts are satisfiable.

The tableau algorithm

To decide whether a concept C0C_0 is satisfiable (with an empty TBox), first push negations inward to negation normal form, using ¬∃r.C≡∀r.¬C\neg\exists r.C\equiv\forall r.\neg C, ¬∀r.C≡∃r.¬C\neg\forall r.C\equiv\exists r.\neg C and De Morgan's laws. Then try to build a model: a completion tree whose nodes xx carry labels L(x)⊆sub⁡(C0)\mathcal L(x)\subseteq\operatorname{sub}(C_0), starting from a single node labeled {C0}\{C_0\}. Apply the rules below until none applies, or until some node contains a clash: {A,¬A}⊆L(x)\{A,\neg A\}\subseteq\mathcal L(x) or ⊥∈L(x)\bot\in\mathcal L(x).

RuleConditionAction
⊓\sqcapC1⊓C2∈L(x)C_1\sqcap C_2\in\mathcal L(x), not both in L(x)\mathcal L(x)add C1C_1 and C2C_2 to L(x)\mathcal L(x)
⊔\sqcupC1⊔C2∈L(x)C_1\sqcup C_2\in\mathcal L(x), neither in L(x)\mathcal L(x)add C1C_1 or C2C_2 (a nondeterministic choice)
∃\exists∃r.C∈L(x)\exists r.C\in\mathcal L(x), no rr-successor yy with C∈L(y)C\in\mathcal L(y)create an rr-successor yy with L(y)={C}\mathcal L(y)=\{C\}
∀\forall∀r.C∈L(x)\forall r.C\in\mathcal L(x), yy an rr-successor of xx, C∉L(y)C\notin\mathcal L(y)add CC to L(y)\mathcal L(y)
C0C_0 is satisfiable if and only if some sequence of choices yields a complete, clash-free tree.
DerivationA subsumption, decided by tableau
  1. L(x0)={C0, ∃r.(A⊓B), ∀r.(¬A⊔C)}\mathcal L(x_0)=\{C_0,\ \exists r.(A\sqcap B),\ \forall r.(\neg A\sqcup C)\}

    Test C0=∃r.(A⊓B)⊓∀r.(¬A⊔C)C_0=\exists r.(A\sqcap B)\sqcap\forall r.(\neg A\sqcup C), already in NNF. The ⊓\sqcap-rule splits the root's label:

  2. (x0,y)∈r,L(y)={A⊓B, ¬A⊔C, A, B}(x_0,y)\in r,\qquad\mathcal L(y)=\{A\sqcap B,\ \neg A\sqcup C,\ A,\ B\}

    The ∃\exists-rule creates a successor yy; the ∀\forall-rule pushes the universal restriction into it; the ⊓\sqcap-rule splits the conjunction:

  3. ¬A∈L(y)  (clash)orL(y)={A⊓B, ¬A⊔C, A, B, C}\neg A\in\mathcal L(y)\ \ (\text{clash})\qquad\text{or}\qquad\mathcal L(y)=\{A\sqcap B,\ \neg A\sqcup C,\ A,\ B,\ C\}

    The ⊔\sqcup-rule must choose. Adding ¬A\neg A clashes with AA, so the search backtracks and adds CC, which completes a clash-free tree:

  4. ΔI={x0,y},rI={(x0,y)},AI=BI=CI={y}\Delta^{\mathcal I}=\{x_0,y\},\quad r^{\mathcal I}=\{(x_0,y)\},\quad A^{\mathcal I}=B^{\mathcal I}=C^{\mathcal I}=\{y\}

    Read off a model: nodes are elements, edges are role pairs, and concept names hold where they appear in labels. So C0C_0 is satisfiable:

  5. {A,¬A}⊆L(y)  or  {C,¬C}⊆L(y)⟹C0⊑∃r.C\{A,\neg A\}\subseteq\mathcal L(y)\ \text{ or }\ \{C,\neg C\}\subseteq\mathcal L(y)\quad\Longrightarrow\quad C_0\sqsubseteq\exists r.C

    Now test C0⊑∃r.CC_0\sqsubseteq\exists r.C, that is, the satisfiability of C0⊓¬∃r.C=C0⊓∀r.¬CC_0\sqcap\neg\exists r.C=C_0\sqcap\forall r.\neg C. The ∀\forall-rule adds ¬C\neg C to L(y)\mathcal L(y), and both branches clash, so the subsumption holds:

DerivationProof sketch
  1. out-degree≤∣C0∣,depth≤∣C0∣\text{out-degree}\le|C_0|,\qquad\text{depth}\le|C_0|

    Termination. Labels are subsets of sub⁡(C0)\operatorname{sub}(C_0), which has at most ∣C0∣|C_0| elements. A node has at most one successor per ∃\exists-concept in its label, and the role depth (nesting of ∃\exists and ∀\forall) of label concepts strictly decreases along each edge:

  2. D∈L(x) ⟹ x∈DID\in\mathcal L(x)\ \Longrightarrow\ x\in D^{\mathcal I}

    Soundness. A complete, clash-free tree defines an interpretation, with AI={x:A∈L(x)}A^{\mathcal I}=\{x: A\in\mathcal L(x)\}. By induction on the structure of concepts, every label member holds at its node, so x0∈C0Ix_0\in C_0^{\mathcal I}:

  3. D∈L(x) ⟹ π(x)∈DID\in\mathcal L(x)\ \Longrightarrow\ \pi(x)\in D^{\mathcal I}

    Completeness. If d0∈C0Id_0\in C_0^{\mathcal I} in some model, let the model guide every ⊔\sqcup-choice, keeping a map π\pi from tree nodes to elements with the invariant below. Then no clash can arise:

  4. space O(∣C0∣2)⟹ALC concept satisfiability∈NPSPACE=PSPACE\text{space }\order{|C_0|^2}\quad\Longrightarrow\quad\text{ALC concept satisfiability}\in\mathsf{NPSPACE}=\mathsf{PSPACE}

    Polynomial space. Subtrees below different successors never interact, so explore them depth first, one at a time, and discard each after checking it. Only one root-to-leaf path is stored, at most ∣C0∣|C_0| nodes with labels of size at most ∣C0∣|C_0|, plus the choices made. That is a nondeterministic polynomial-space algorithm, and NPSPACE = PSPACE by Savitch's theorem. Hardness: quantified Boolean formulas reduce to it, one role step per quantifier.

A general TBox changes the picture. Every node must also satisfy each inclusion C⊑DC\sqsubseteq D (add ¬C⊔D\neg C\sqcup D to every label), and the ∃\exists-rule can now generate infinite paths: with T={A⊑∃r.A}\mathcal T=\{A\sqsubseteq\exists r.A\}, every new node needs yet another successor. Termination requires blocking: stop expanding a node whose label is contained in an ancestor's label, and fold the path back into a cycle when reading off the model. Satisfiability with respect to general ALC TBoxes is EXPTIME-complete (Schild, 1991, via propositional dynamic logic). Tableau reasoners with blocking are not worst-case optimal, but heavily optimized ones handle large real ontologies, alongside hypertableau and consequence-based reasoners.

Consequence-based reasoning in EL

Drop disjunction, negation and universal restrictions, keeping only ⊤\top, ⊓\sqcap and ∃r.C\exists r.C, and you get the logic EL. It sounds weak, yet SNOMED CT, a clinical terminology with a few hundred thousand concepts, is expressed in a member of the EL family. The payoff is that no case analysis is ever needed: a single canonical model exists, and subsumption can be computed by saturation, much like Datalog. After normalizing the TBox into axioms of four shapes, a completion algorithm keeps, for each concept name AA, a set S(A)S(A) of derived subsumers (initially {A,⊤}\{A,\top\}) and, for each role rr, a set R(r)R(r) of pairs:

RuleIf……then
CR1A′∈S(A)A'\in S(A) and A′⊑B∈TA'\sqsubseteq B\in\mathcal Tadd BB to S(A)S(A)
CR2A1,A2∈S(A)A_1,A_2\in S(A) and A1⊓A2⊑B∈TA_1\sqcap A_2\sqsubseteq B\in\mathcal Tadd BB to S(A)S(A)
CR3A′∈S(A)A'\in S(A) and A′⊑∃r.B∈TA'\sqsubseteq\exists r.B\in\mathcal Tadd (A,B)(A,B) to R(r)R(r)
CR4(A,B)∈R(r)(A,B)\in R(r), B′∈S(B)B'\in S(B) and ∃r.B′⊑C∈T\exists r.B'\sqsubseteq C\in\mathcal Tadd CC to S(A)S(A)
Completion rules for EL (Baader, Brandt & Lutz, 2005). With nn concept names there are at most n2n^2 entries in the SS sets and n2n^2 pairs per role, so saturation ends after polynomially many rule applications.
DerivationClassifying pericarditis
  1. Peri⊑Infl,Infl⊑Disease,Peri⊑∃loc.Pericardium,Pericardium⊑∃partOf.Heart,∃partOf.Heart⊑HeartPart,∃loc.HeartPart⊑AtHeart,Disease⊓AtHeart⊑HeartDisease\begin{aligned}&\mathit{Peri}\sqsubseteq\mathit{Infl},\quad\mathit{Infl}\sqsubseteq\mathit{Disease},\quad\mathit{Peri}\sqsubseteq\exists\mathit{loc}.\mathit{Pericardium},\quad\mathit{Pericardium}\sqsubseteq\exists\mathit{partOf}.\mathit{Heart},\\&\exists\mathit{partOf}.\mathit{Heart}\sqsubseteq\mathit{HeartPart},\quad\exists\mathit{loc}.\mathit{HeartPart}\sqsubseteq\mathit{AtHeart},\quad\mathit{Disease}\sqcap\mathit{AtHeart}\sqsubseteq\mathit{HeartDisease}\end{aligned}

    A normalized TBox in the style of medical terminologies (Peri\mathit{Peri} abbreviates pericarditis, Infl\mathit{Infl} inflammation):

  2. Infl, Disease∈S(Peri),(Peri,Pericardium)∈R(loc)\mathit{Infl},\ \mathit{Disease}\in S(\mathit{Peri}),\qquad(\mathit{Peri},\mathit{Pericardium})\in R(\mathit{loc})

    From S(Peri)={Peri,⊤}S(\mathit{Peri})=\{\mathit{Peri},\top\}, apply CR1 twice and CR3 once:

  3. (Pericardium,Heart)∈R(partOf) ⟹ HeartPart∈S(Pericardium)(\mathit{Pericardium},\mathit{Heart})\in R(\mathit{partOf})\ \Longrightarrow\ \mathit{HeartPart}\in S(\mathit{Pericardium})

    CR3 for the pericardium, then CR4, since Heart∈S(Heart)\mathit{Heart}\in S(\mathit{Heart}):

  4. (Peri,Pericardium)∈R(loc), HeartPart∈S(Pericardium) ⟹ AtHeart∈S(Peri)(\mathit{Peri},\mathit{Pericardium})\in R(\mathit{loc}),\ \mathit{HeartPart}\in S(\mathit{Pericardium})\ \Longrightarrow\ \mathit{AtHeart}\in S(\mathit{Peri})

    CR4 again, through the loc\mathit{loc} edge:

  5. Disease, AtHeart∈S(Peri) ⟹ HeartDisease∈S(Peri),  that is,  Peri⊑THeartDisease\mathit{Disease},\ \mathit{AtHeart}\in S(\mathit{Peri})\ \Longrightarrow\ \mathit{HeartDisease}\in S(\mathit{Peri}),\ \text{ that is, }\ \mathit{Peri}\sqsubseteq_{\mathcal T}\mathit{HeartDisease}

    CR2 joins the two strands. Saturation has proved a subsumption that no axiom states:

Check your understanding

Which axiom, added to an EL TBox, forces a reasoner into case analysis (and takes the TBox outside EL)?

  1. A⊓B⊑CA\sqcap B\sqsubseteq C
  2. A⊑B⊔CA\sqsubseteq B\sqcup C
  3. A⊑∃r.BA\sqsubseteq\exists r.B
  4. ∃r.A⊑B\exists r.A\sqsubseteq B
Show the answer

B. A⊑B⊔CA\sqsubseteq B\sqcup C

A disjunction on the right lets a model satisfy AA through BB or through CC, with different consequences in each case. No single canonical model exists any more, so saturation alone cannot decide subsumption; with general TBoxes the problem becomes EXPTIME-complete.

The map, OWL and open worlds

In 1984 Brachman and Levesque showed that a seemingly harmless addition to a small frame language makes subsumption coNP-hard, and in 1989 Schmidt-Schauß showed that the role-value maps of the KL-ONE system make it undecidable. Three decades of work mapped the territory in between:

LogicMain constructors addedReasoning complexityWhere it is used
EL⊤\top, ⊓\sqcap, ∃r.C\exists r.CP (subsumption with general TBoxes)OWL 2 EL; SNOMED CT
DL-Lite∃r\exists r, inverse roles, negation on the right of ⊑\sqsubseteqquery answering in AC0^0 data complexity, by rewriting into SQLOWL 2 QL; ontology-based data access
ALC¬\neg, ⊔\sqcup, ∀r.C\forall r.CPSPACE-complete (no TBox); EXPTIME-complete (general TBoxes)the core of the expressive DLs
SHIQtransitive roles, role hierarchies, inverse roles, qualified number restrictionsEXPTIME-completeOIL, a precursor of OWL
SHOIN(D)nominals, number restrictions, datatypesNEXPTIME-completeOWL 1 DL (2004)
SROIQ(D)complex role inclusions, qualified number restrictions, further role axiomsN2EXPTIME-complete (Kazakov, 2008)OWL 2 DL (2009)
Each row lists its main additions over the logics above it; DL-Lite is a separate lightweight branch. Complexities are for the standard tasks (satisfiability, subsumption) unless stated.

The W3C's OWL (2004) has a sublanguage, OWL DL, that corresponds to SHOIN(D). OWL 2 (2009) corresponds to SROIQ(D) and adds three tractable profiles: OWL 2 EL (polynomial classification of large terminologies), OWL 2 QL (DL-Lite: queries rewritten into SQL over relational data) and OWL 2 RL (rules implementable in Datalog). OWL 2 Full, which gives a meaning to every RDF graph, is undecidable.

Key takeaways

  • ALC concepts denote sets and TBoxes are general concept inclusions; subsumption, equivalence and instance checking all reduce to (un)satisfiability.
  • The tableau algorithm (NNF, four rules, clash detection) decides ALC concept satisfiability; depth-first exploration puts it in PSPACE, and the problem is PSPACE-complete. General TBoxes make it EXPTIME-complete and require blocking.
  • EL drops ⊔\sqcup, ¬\neg and ∀\forall, so a polynomial completion algorithm computes every subsumption by saturation: the basis of OWL 2 EL and of reasoning over SNOMED CT.
  • OWL 1 DL corresponds to SHOIN(D) (NEXPTIME-complete) and OWL 2 DL to SROIQ(D) (N2EXPTIME-complete), with the tractable profiles EL, QL and RL.
  • Ontologies are read under open-world semantics without unique names: absent facts are unknown, and cardinality limits merge individuals rather than flag errors.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

What is the complexity of deciding whether an ALC concept is satisfiable with respect to an empty TBox?

  1. NP-complete
  2. EXPTIME-complete
  3. PSPACE-complete
  4. Undecidable
Show the answer

C. PSPACE-complete

The tableau explores one branch of a tree of depth at most ∣C0∣|C_0| at a time, in polynomial space, and quantified Boolean formulas reduce to the problem (Schmidt-Schauß & Smolka, 1991).

Question 2

T={Parent≡Person⊓∃hasChild.⊤}\mathcal T=\{\mathit{Parent}\equiv\mathit{Person}\sqcap\exists\mathit{hasChild}.\top\} and A={bob:Person}\mathcal A=\{\mathit{bob}:\mathit{Person}\}. Which statement is true?

  1. bob:¬Parent\mathit{bob}:\neg\mathit{Parent} is entailed, since no child of Bob is recorded
  2. Neither bob:Parent\mathit{bob}:\mathit{Parent} nor bob:¬Parent\mathit{bob}:\neg\mathit{Parent} is entailed
  3. The knowledge base is inconsistent
  4. bob:Parent\mathit{bob}:\mathit{Parent} is entailed by the definition
Show the answer

B. Neither bob:Parent\mathit{bob}:\mathit{Parent} nor bob:¬Parent\mathit{bob}:\neg\mathit{Parent} is entailed

Some models give Bob a child and some do not, so neither assertion holds in all models. Description logics use the open-world assumption: missing information is unknown, not false.

Question 3

Why does a tableau algorithm for ALC with a general TBox need blocking?

  1. To keep labels from growing beyond the relevant subconcepts
  2. To make the ⊔\sqcup-rule deterministic
  3. To prevent clashes between different branches of the search
  4. Because inclusions such as A⊑∃r.AA\sqsubseteq\exists r.A make the ∃\exists-rule generate an infinite chain of nodes, which blocking folds into a cycle
Show the answer

D. Because inclusions such as A⊑∃r.AA\sqsubseteq\exists r.A make the ∃\exists-rule generate an infinite chain of nodes, which blocking folds into a cycle

With a TBox, every new node must satisfy every inclusion, so a node in AA needs an rr-successor in AA, which needs another, and so on. Once a node's label is contained in an ancestor's, expanding it would add nothing new: the model reuses the ancestor instead, and the tree stays finite.

Question 4

You maintain a medical terminology with hundreds of thousands of classes that must be classified quickly and predictably after every edit. Which OWL 2 profile fits best?

  1. OWL 2 EL
  2. OWL 2 QL
  3. OWL 2 Full
  4. OWL 2 DL with all of SROIQ
Show the answer

A. OWL 2 EL

OWL 2 EL is built on the EL family, whose subsumption is polynomial even with general TBoxes. Consequence-based EL reasoners classify terminologies of this size routinely.

Further reading

  • F. Baader, I. Horrocks, C. Lutz & U. Sattler, An Introduction to Description Logic (Cambridge University Press, 2017).
  • F. Baader, D. Calvanese, D. McGuinness, D. Nardi & P. Patel-Schneider (eds.), The Description Logic Handbook, 2nd ed. (Cambridge University Press, 2007).
  • M. Schmidt-Schauß & G. Smolka, "Attributive concept descriptions with complements," Artificial Intelligence 48(1) (1991), 1–26.
  • F. Baader, S. Brandt & C. Lutz, "Pushing the EL envelope," IJCAI (2005).
  • I. Horrocks, P. F. Patel-Schneider & F. van Harmelen, "From SHIQ and RDF to OWL: the making of a web ontology language," Journal of Web Semantics 1(1) (2003), 7–26.