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, (two inclusions) defines parents, and describes parents all of whose children are doctors. On its own, also contains everyone without children. Translating as maps ALC into first-order logic with just two variables, reused alternately, and ALC is a notational variant of the multimodal logic (Schild, 1991). All the standard reasoning tasks reduce to one:
Which ALC concept is unsatisfiable, that is, empty in every interpretation?
Show the answer
C.
An element of has an -successor in , and forces that same successor into : a clash. The other three concepts are satisfiable.
The tableau algorithm
To decide whether a concept is satisfiable (with an empty TBox), first push negations inward to negation normal form, using , and De Morgan's laws. Then try to build a model: a completion tree whose nodes carry labels , starting from a single node labeled . Apply the rules below until none applies, or until some node contains a clash: or .
| Rule | Condition | Action |
|---|---|---|
| , not both in | add and to | |
| , neither in | add or (a nondeterministic choice) | |
| , no -successor with | create an -successor with | |
| , an -successor of , | add to |
Test , already in NNF. The -rule splits the root's label:
The -rule creates a successor ; the -rule pushes the universal restriction into it; the -rule splits the conjunction:
The -rule must choose. Adding clashes with , so the search backtracks and adds , which completes a clash-free tree:
Read off a model: nodes are elements, edges are role pairs, and concept names hold where they appear in labels. So is satisfiable:
Now test , that is, the satisfiability of . The -rule adds to , and both branches clash, so the subsumption holds:
Termination. Labels are subsets of , which has at most elements. A node has at most one successor per -concept in its label, and the role depth (nesting of and ) of label concepts strictly decreases along each edge:
Soundness. A complete, clash-free tree defines an interpretation, with . By induction on the structure of concepts, every label member holds at its node, so :
Completeness. If in some model, let the model guide every -choice, keeping a map from tree nodes to elements with the invariant below. Then no clash can arise:
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 nodes with labels of size at most , 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 (add to every label), and the -rule can now generate infinite paths: with , 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 , and , 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 , a set of derived subsumers (initially ) and, for each role , a set of pairs:
| Rule | If… | …then |
|---|---|---|
| CR1 | and | add to |
| CR2 | and | add to |
| CR3 | and | add to |
| CR4 | , and | add to |
A normalized TBox in the style of medical terminologies ( abbreviates pericarditis, inflammation):
From , apply CR1 twice and CR3 once:
CR3 for the pericardium, then CR4, since :
CR4 again, through the edge:
CR2 joins the two strands. Saturation has proved a subsumption that no axiom states:
Which axiom, added to an EL TBox, forces a reasoner into case analysis (and takes the TBox outside EL)?
Show the answer
B.
A disjunction on the right lets a model satisfy through or through , 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:
| Logic | Main constructors added | Reasoning complexity | Where it is used |
|---|---|---|---|
| EL | , , | P (subsumption with general TBoxes) | OWL 2 EL; SNOMED CT |
| DL-Lite | , inverse roles, negation on the right of | query answering in AC data complexity, by rewriting into SQL | OWL 2 QL; ontology-based data access |
| ALC | , , | PSPACE-complete (no TBox); EXPTIME-complete (general TBoxes) | the core of the expressive DLs |
| SHIQ | transitive roles, role hierarchies, inverse roles, qualified number restrictions | EXPTIME-complete | OIL, a precursor of OWL |
| SHOIN(D) | nominals, number restrictions, datatypes | NEXPTIME-complete | OWL 1 DL (2004) |
| SROIQ(D) | complex role inclusions, qualified number restrictions, further role axioms | N2EXPTIME-complete (Kazakov, 2008) | OWL 2 DL (2009) |
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 , and , 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.
What is the complexity of deciding whether an ALC concept is satisfiable with respect to an empty TBox?
- NP-complete
- EXPTIME-complete
- PSPACE-complete
- Undecidable
Show the answer
C. PSPACE-complete
The tableau explores one branch of a tree of depth at most at a time, in polynomial space, and quantified Boolean formulas reduce to the problem (Schmidt-Schauß & Smolka, 1991).
and . Which statement is true?
- is entailed, since no child of Bob is recorded
- Neither nor is entailed
- The knowledge base is inconsistent
- is entailed by the definition
Show the answer
B. Neither nor 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.
Why does a tableau algorithm for ALC with a general TBox need blocking?
- To keep labels from growing beyond the relevant subconcepts
- To make the -rule deterministic
- To prevent clashes between different branches of the search
- Because inclusions such as make the -rule generate an infinite chain of nodes, which blocking folds into a cycle
Show the answer
D. Because inclusions such as make the -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 needs an -successor in , 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.
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?
- OWL 2 EL
- OWL 2 QL
- OWL 2 Full
- 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.