From KL-ONE to OWL: Description Logics in the
Ivory Tower and the Semantic Web

Abstract

Description Logics are logical formalisms for representing information about classes and objects. Description Logics are often designed to serve as the basis of implemented knowledge representation systems. However these systems have been mostly used in research prototypes. Recent improvements in inference algorithms and computer power have resulted in new systems based on expressive Description Logics, leading to the development of OWL, which can be viewed as an expressive Description Logic designed for use the Semantic Web. This talk will provide an overview of research in Description Logics, but will delve more deeply into the developments leading up to OWL.

Two Caveats

1. This talk presents my view of much of the development of the field now known as Description Logics. I have been involved with most of the developments in the field, but there have been quite a number of excellent researchers active in the field, including Ron Brachman, Franz Baader, Ian Horrocks, and Uli Sattler. I will try to assign credit (and blame) where it is due, but it is inevitable that some ambiguities and miscommunications will creep in to this assignment.
2. This talk describes a major portion of my work but there are also other major efforts in which I have been involved, some related to Description Logics, some related to other knowledge representation formalisms, and some unrelated to Artificial Intelligence research at all.

What is a Description Logic?

• Logic-based knowledge representation formalism
  • syntax and model-theoretic semantics
• Represents information about classes (a.k.a. concepts), roles (a.k.a. properties), and objects (a.k.a. individuals)
  
  • Student = Person ∩ ( ∃ enrolledIn EducationalInstitution )
  • married ≤ Person × Person
  • Rutgers ∈ EducationalInstitution
  • John ∈ ( married : Susan ) ∩ (enrolledIn : Rutgers)
• Generally has decidable inference
  • Subsumption - whether one class is more general than another
  • Classification - determine subsumption between all named classes
  • Realization - determine the named classes an individual belongs to
• Susan belongs to Person
  John belongs to Student

Description Logic (OWL) Knowledge Base Fragment

Taken from the OWL wine and food ontologies.

<owl:Class rdf:ID="WhiteWine">
  <owl:intersectionOf rdf:parseType="Collection">
    <owl:Class rdf:about="#Wine" />
    <owl:Restriction>
      <owl:onProperty rdf:resource="#hasColor" />
      <owl:hasValue rdf:resource="#White" />
    </owl:Restriction>
  </owl:intersectionOf>
</owl:Class>

(From now on, I will not use the RDF/XML syntax!)

Description Logic (OWL) Knowledge Base Fragment

Wine ≤ PotableLiquid ∩ (=1 hasMaker) ∩ (∀ hasMaker Winery)
                ∩ (≥ 1 madeFromGrape) ∩ (= 1 hasColor) ∩ ...
madeFromGrape ≤ Wine × WineGrape
hasColor ≤ Wine × WineColor
WineColor = { White, Rose, Red }
White ≠ Rose   White ≠ Red   Rose ≠ Red
WineDescriptor = WineTaste ∪ WineColor
 
WhiteWine = Wine ∩ ( hasColor : White )
Riesling = Wine ∩ (madeFromGrape : RieslingGrape ) ∩
                 (≤ 1 madeFromGrape)
Riesling ≤ hasColor : White
 
CorbansDryWhiteRiesling ∈ Riesling ∩ (hasMaker : Corbans) ∩ ...

The Beginnings

• SI Nets [Brachman 1977]
• KL-ONE (a.k.a. KLONE) [Brachman and Schmolze 1985]
• ``KL-ONE is a system for representing knowledge in Artificial Intelligence programs [...] emphasizing [...] complex strutured descriptions'' [Brachman and Schmolze 1985, p. 171]
• KL-ONE provided a graphical representation for these structured descriptions based on a large set of knowledge-structuring primitives.
• KL-ONE did not have a formal meaning for its constructss
  • Lead to different groups intuiting different meanings
  • Lead to different systems implementing different inferences

Formalization of KL-ONE

• Turn SI nets into terminological logics (later called description logics)
• Specify a linear syntax
  • (AND Person (SOME child) (ALL child Lawyer))
• Provide a model-theoretic semantics
  • Interpretations and extensions
  • E[...] = E(Person) ∩ { x : ∃ y   <x,y> ∈ E(child) } &cap
               { x : <x,y> ∈ E(child) → y ∈ E(Lawyer) }
• Subsumption—one concept subsumes another if its extension is always a superset of the other's
• Classification—determine all the subsumption relationships between named concepts in a KB
• Realization—determine all the instance relationships for named individuals in a KB
• Above relationships are inter-reducible

Early Systems for Description Logics

 

NIKL [Moser 1983]

Large, expressive language; simple inference algorithm

KANDOR [Patel-Schneider 1984]

Small, inexpressive language; simple inference algorithm

BACK [Peltason et al 1987]

Medium-size language; simple inference algorithm

M. G. Moser. An Overview of NIKL, The New Implementation of KL-ONE. BBN Labs TR 5421, 1983.
Peter F. Patel-Schneider. Small can be Beautiful in Knowledge Representation. IEEE Workshop on Principles of Knowledge-Based Systems, 1984, pp. 11–16.
Christof Peltason, Kai von Luck, Bernhard Nebel, and Albrecht Schmiedel. The User's Guide to the BACK System. TU Berlin, KIT-Report 42, 1987.

Computing Subsumption (Performing Inference)

• Subsumption is worst-case intractable for many terminological logics
  • because they ``include'' propositional logics
  • thus inference algorithm in NIKL is incomplete
• Undecidable for some terminological logics
  • because they can be embedded in first-order logics
• Lots of ways to get undecidability
  • e.g., encoding the word problem with role equality [Patel-Schneider 1988]
• Even worse, worst-case intractable even without disjunctions
  • can get an analogue of disjunction in many ways [Brachman and Levesque 1984]
  • so inference algorithm in BACK is incomplete

Ronald J. Brachman and Hector J. Levesque. The Tractability of Subsumption in Frame-Based Description Languages. AAAI-84, pp. 34–37.
Peter F. Patel-Schneider. Undecidability of Subsumption in NIKL. Artificial Intelligence 39(2), 1989, pp. 263–272.

Why is Inference in NIKL Undecidable?

• NIKL concepts can be used to force certain properties of the domain.
  • A "universal" role
  • Functional roles
  • Equality of role chains
• Any word problem can be translated into a NIKL concept in a way that the word problem has a solution iff the NIKL concept is non-empty.
• Therefore subsumption in NIKL is undecidable.

Peter F. Patel-Schneider. Undecidability of Subsumption in NIKL. Artificial Intelligence 39, 2 (1989), pp. 263–272.

The Retreat to CLASSIC

CLASSIC [Patel-Schneider et al 1991]

• Attempt to build a useful system on a tractable Description Logic
• Need to severely limit expressive power
  • lots of things cannot be said in CLASSIC
• Lots of things can be said in CLASSIC
• Considerable attempt to make CLASSIC useful, including documentation [Brachman et al 1991]
• CLASSIC used in several systems within AT&T
• Implementations in LISP, C, and C++ (NeoClassic)

Peter F. Patel-Schneider, Deborah L. McGuinness, Ronald J. Brachman, Lori Resnick, and Alex Borgida. The CLASSIC Knowledge Representation System. SIGART Bulletin 2, 3 (1991), pp. 108–113.
Ronald J. Brachman, Alex Borgida, Deborah L. McGuinness, Peter F. Patel-Schneider, and Lori Resnick. Living with CLASSIC. In Principles of Semantic Networks, 1991, pp. 401–456.
Ronald J. Brachman, Deborah L. McGuinness, Peter F. Patel-Schneider, and Alex Borgida. ``Reducing'' CLASSIC to Practice. Artificial Intelligence 114, 1999, pp. 203–237.

CLASSIC Knowledge Base Fragment

WineColor = { White, Rose, Red }
(White ≠ Rose   White ≠ Red   Rose ≠ Red)
Wine ≤ PotableLiquid ∩ (=1 hasMaker) ∩ (∀ hasMaker Winery)
                ∩ (≥ 1 madeFromGrape) ∩ (= 1 hasColor) ∩ ...
madeFromGrape ≤ Wine × WineGrape
hasColor ≤ Wine × WineColor
WineDescriptor = WineTaste ∪ WineColor
WineTaste ≤ WineDescriptor
WineColor ≤ WineDescriptor
 
WhiteWine = Wine ∩ ( hasColor : White )
Riesling = Wine ∩ (madeFromGrape : RieslingGrape ) ∩
                 (≤ 1 madeFromGrape)
Riesling ≤ hasColor : White
CorbansDryWhiteRiesling ∈ Riesling ∩ (hasMaker : Corbans) ∩ ...

Tractability of Reasoning in CLASSIC

• The CLASSIC system uses an O(n log n) subsumption algorithm
  • Essentially computes a canonical completion and then checks to see whether two completions match up (structural subsumption)
• This algorithm is sound [Borgida and Patel-Schneider 1994]
• This algorithm is complete when no individuals are used
• This algorithm is not complete in general
• Sets of individuals cause difficulties
• Reasoning in CLASSIC is NP-hard
• What can be done?
  • Fiddle with the semantics of CLASSIC!
  • Essentially treat individuals as disjoint concepts
  • An alternate way of describing inference in CLASSIC

Alex Borgida and Peter F. Patel-Schneider. A Semantics and Complete Algorithm for Subsumption in the CLASSIC Description Logic. Journal of Artificial Intelligence Research 1, 1994, pp. 277–308.

Was CLASSIC a Success?

 

Yes

• implemented system
• used commercially inside AT&T
• used outside AT&T

No

• only a main-memory implementation
• no Java implementation
• no significant commercial usage outside AT&T

Description Logics in the Ivory Tower

Many formal developments in the late 1980s and 1990s.

• Correspondence to propositional modal logics
  • ALC is a notational variant of K_m
  • c,d ::= a | c ∩ d | c ∪ d | ∀ r d | ∃ r d
• Tableau method for inference in Description Logics [Hollunder and Nutt 1990]
  • Variants of the standard methods from propositional modal logics
• Complexity and decidability results for reasoning
  • Correspondences get PSPACE completeness for ALC,
    EXPTIME completeness for ALC with definitions
  • Many, many, many more, some from correspondences, some new

Bernhard Hollunder and Werner Nutt. Subsumption Algorithms for Concept Languages. DFKI Research Report, 1990.
Many, many, many more papers.
Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, eds. The Description Logic Handbook. Cambridge University Press, 2003.

Tiptoeing out of the Ivory Tower

• Systems for moderately-expressive Description Logics
  • KRIS [Baader and Hollunder 1991]
  • Description Logic system built on ALC
  • Reasonably fast implementation
• (D)ARPA KRSS API for Description Logic Systems [Patel-Schneider and Swartout 1993]
  • Common notation for Description Logics (for both papers and systems)
  • Common API for Description Logic systems

Franz Baader and Bernhard Hollunder. KRIS: Knowledge Representation and Inference System. SIGART Bulletin 2(2), 1991.
Peter F. Patel-Schneider and Bill Swartout. Description-Logic Knowledge Representation System Specification. AT&T Bell Labs, 1993.

Improving Description Logic Systems

• New Systems for expressive Description Logics
  (ALC + number restrictions + definitions + ...)
  • FaCT [Horrocks 1998], DLP [Patel-Schneider 1998],
    RACER [Haarslev and Moeller 2000]
• All use variants of tableaux methods, also used in modal logics
  • Try to build a model in an effective manner
  • If can't, then no model
• Performance
  • Surprisingly impressive [Horrocks and Patel-Schneider 1998, 1999]
  • Astonishingly faster than existing provers for propositional modal logics
  • Faster than CLASSIC!

Ian Horrocks. Using an Expressive Description Logic: FaCT or Fiction?. KR-98, pp. 636–647.
Peter F. Patel-Schneider. System Description: DLP. CADE-2000.
Volker Haarslev and Ralf Moeller. Expressive ABox Reasoning with Number Restrictions, Role Hierarchies, and Transitively Closed Roles. KR-2000, pp. 273–284.
Ian Horrocks and Peter F. Patel-Schneider. FaCT and DLP. Tableaux'98, pp. 27–30.
Peter F. Patel-Schneider and Ian Horrocks. DLP and FaCT. Tableaux'99, pp. 19–23.

Why are Description Logic Reasoners so Fast?

• Lots of optimizations
  • Lots of high-level optimizations
  • Few low-level optimizations (contrast with SAT solvers)
• Optimizations in FaCT and DLP [Horrocks and Patel-Schneider 1999]
  • Lexical normalization
  • Boolean constraint propagation
  • Searching in the semantic space
  • Caching previous results
  • Backjumping (dependency-directed backtracking)
  • Heuristics (of various sorts and flavors)

Ian Horrocks and Peter F. Patel-Schneider. Optimising Description Logic Subsumption. JLC 9(3), 1999, pp. 267–293.

Effectiveness of Optimizations

Effectiveness of optimizations [Horrocks et al 2000]

• Varies with the problem set (as expected)
• Lexical normalization is often very effective!
  • e.g., replacing disjunction with negated conjunction
• Backjumping is very effective (as expected)
  • Eliminates incredible amount of useless work
• Caching is very effective
  • Subproblems often repeat over and over
• Some heuristics are not very effective
  • Varies with problem set
  • Often better to use a different setting than in SAT

Ian Horrocks, Peter Patel-Schneider, and Roberto Sebastiani. An Analysis of Empirical Testing for Modal Decision Procedures. Logic Journal of the IGPL, 8(3), 2000, pp. 293–324.

Effectiveness of Optimizations

A problem set where caching is most effective.
K_dum non-valid problem set from Tableaux'98
(Note log scale for CPU time)

Effectiveness of Optimizations (cont'd)

A problem set where backjumping and semantic branching are most effective.
S₄_S₅ valid problem set from Tableaux'98
(Note log scale for CPU time)

Effectiveness of Optimizations (cont'd)

	FaCT	DLP	KRIS	CRACK
Load	6.03		135.90
Classify	204.03		>>400,000	>>10,000
Total	210.91	69.56	>>400,000	>>10,000

CPU time in seconds to process the GALEN Knowledge Base

Both KRIS and CRACK get about two-thirds of the way through and then get "stuck" on the first hard subsumption problem.

Measuring the Improvements

How fast are the systems, and why? [Horrocks et al 2002]

• Measure on actual knowledge bases (GALEN, etc.)
  • Only GALEN is suitable
  • Other KBs are too easy for new systems
• Measure on hand-generated formulae (Tableaux'98)
  • Lots of effort to build
  • Too easy for new systems
• Measure on random modal formulae (as in SAT)
  • Not really what we want
  • Easy to generate
  • Not easy to generate well

Ian Horrocks and Peter F. Patel-Schneider. Evaluating Optimised Decision Procedures for Propositional Modal Km Satisfiability. Journal of Automated Reasoning, 28:2, February 2002, pp. 173–204.

Measuring Performance on Random Formulae

Randomly generated 3CNF_◊ formulae in clause normal form.
Each clause has 3 disjuncts, either propositional literals or modal clauses.
N is number of propositional variables.
L is number of top-level clauses.
Median solution time for formulae with modal depth 1 (previous generator)

Measuring Performance (Half-Dome Plot)

Why the "half-dome" shape?
The modal formulae become propositionally unsatisfiable:
(... ∨ ◊ &alpha ∨ ...) ∧
(... ∨ ¬ ◊ α ∨ ...) ∧ ...
Median solution time for formulae with modal depth 2 (previous generator)

Improving the Measuring

• Artifacts in random formulae
  • Modal formulae that are propositionally unsatisfiable
  • Trivial clauses, with a subformula and its negation
• Need to generate good formulae [Patel-Schneider and Sebastiani 2003]
  • Cover the problem space
  • Lots of control over generated formulae
  • Suitable difficulty
• Need to be careful to
  • not repeat propositional variables
  • not repeat disjuncts in clauses (especially negated)
  • not disturb the various probabilities

Peter F. Patel-Schneider and Roberto Sebastiani. A New General Method to Generate Random Modal Formulae for Testing Decision Procedures. Journal of Artificial Intelligence Research, 18, 2003, pp. 351–389.

Improving the Measuring

No artifacts.
Much harder than previous generator!
Median solution time for formulae with modal depth 2 (new generator)

Moving to the Semantic Web

• What is the World Wide Web?
• What is the Semantic Web?
• Why move to the Semantic Web?
  • Because it's there!
  • A good opportunity for use
  • Interesting ontologies and knowledge bases
• What is Ontology? (Philosophy)
  • A systematic account of Existence (dictionary.reference.com)
• What is an Ontology? (Artificial Intelligence)
  • A way of saying what sorts of objects, etc., are to be described
  • Looks a lot like a collection of Description Logic concepts!
• To move to the Semantic Web, Description Logics have to live in the Semantic Web

Initial Steps towards the Semantic Web

• OIL (Ontology Inference Layer/Language/Logic) [Horrocks et al, 2001] [Fensel et al, 2001]
  • An expressive Description Logic with a frame-like syntax
  • Expressive power similar to that of FaCT, DLP, and RACER
  • Syntax is an XML dialect

<class-def>
  <class name="tree" />
  <subclass-of>
    <class name="plant" />
  </subclass-of>
</class-def>

Ian Horrocks, Peter Patel-Schneider, Frank van Harmelen, and Dieter Fensel. OIL: A Good Ontology Language for the Semantic Web. WWW-2001, 2001.
Dieter Fensel, Ian Horrocks, Frank van Harmelen, Deborah L. McGuinness, and Peter F. Patel-Schneider. OIL: An Ontology Infrastructure for the Semantic Web. IEEE Intelligent Systems 16(2), 2001.

Living in the Semantic Web (circa 2001)

Resource Description Framework (RDF) circa 2001

• base language for the Semantic Web; similar to Semantic Networks
• all information is represented in subject-predicate-object triples
• pretheoretic—no formal semantics
• some odd features—reification, higher-order

rdfs:Class rdf:type rdfs:Class .
ex:Person rdf:type rdfs:Class .
ex:John rdf:type ex:Person .
ex:Susan rdf:type ex:Person .
ex:John ex:friend ex:Susan .

Ora Lassila and Ralph R. Swick. Resource Description Framework (RDF) Model and Syntax Specification. W3C Recommendation 22 February 1999.
Dan Brickley and R. V. Guha. Resource Description Framework (RDF) Schema Specification 1.0. W3C Candidate Recommendation 27 March 2000.

The Semantic Web Vision

 
 
 
 
RDF is the base.
 
All other languages build on RDF and use its syntax.

The Semantic Web Tower (from Tim Berners-Lee)

DAML+OIL

DAML+OIL [Connolly et al 2001] [Horrocks et al 2002]

• Move OIL closer to the Semantic Web
• Use RDF syntax
• Not much semantics available to use!
• DAML+OIL provides its own model-theoretic semantics
  • Uses RDF only as a syntax

ex:Wine rdf:type daml:Class .
ex:Wine rdfs:subClassOf _:c .
_:c rdf:type daml:Restriction .
_:c daml:onProperty ex:hasMaker .
_:c daml:toClass ex:Winery

Dan Connolly, Frank van Harmelen, Ian Horrocks, Deborah L. McGuinness, Peter F. Patel-Schneider, and Lynn Andrea Stein. DAML+OIL (March 2001) Reference Description. W3C Note 18 December 2001.
Ian Horrocks, Peter F. Patel-Schneider, and Frank van Harmelen. Reviewing the Design of DAML+OIL: An Ontology Language for the Semantic Web. AAAI-2002, 2002.

Living in the Semantic Web (circa 2003)

• New basis for RDF
  • Syntax more rigourously specified [Beckett 2003]
  • Model-theoretic semantics [Hayes 2003]
    • RDF is more like FOL than a Description Logic
    • Each triple makes an assertion
    • Entailment relation, similar to entailment in FOL
• To fit in the Semantic Web vision, now need to fit into both syntax and semantics of RDF
  • Can this be done, when Description Logic constructs have to be encoded as triples?

Dave Beckett. RDF/XML Syntax Specification (Revised). W3C Proposed Recommendation 15 December 2003.
Patrick Hayes. RDF Semantics. W3C Proposed Recommendation 15 December 2003.

Problems with Living in the Semantic Web (Part 1)

• RDF can treat classes as individuals
  CorbansDryWhiteRiesling ∈ Wine
  Wine ≤ PotableLiquid ∩ (=1 hasMaker) ∩ (∀ hasMaker Winery)
  Wine ∈ owl:Class
  owl:Class ≤ rdfs:Class
  • Higher-order, but only in a sense
• This capability makes Description Logics undecidable
• Possible Solution: Define a subset of RDF and build on that
  • Eliminate classes as individuals
  • Forbid fiddling with RDF built-ins

Peter F. Patel-Schneider and Dieter Fensel. Layering the Semantic Web: Problems and Directions. ISWC-2002.

Problems with Living in the Semantic Web (Part 2)

• Requiring only RDF syntax causes problems
• Don't get John ∈ Person implying John ∈ Person ∪ Student
• Why?
  Consequent is
  

  
  ex:John rdf:type _:a .
  _:a daml:unionOf _:l1 .
  _:l1 daml:first ex:Person .
  _:l1 daml:rest _:l2 .
  _:l2 daml:first ex:Student .
  _:l2 daml:rest daml:nil . 

• The facts that are part of the "list" are not implied
• Solution: Add "comprehension principles" (as in set theory)
  • All lists exist everywhere
  • All descriptions exist everywhere

Problems with Living in the Semantic Web (Part 3)

• Comprehension principles are dangerous
• Could force existence of paradoxical concepts (like Russell's paradox)
  

  _:a rdf:type daml:Restriction .
  _:a daml:onProperty rdf:type .
  _:a daml:maxCardinalityQ 0 .
  _:a daml:hasClassQ _:b .
  _:b daml:oneOf _:c .
  _:c daml:first _:a .
  _:c daml:rest daml:nil . 

• Need to restrict the comprehension principle
  • But how?
• Partial Solution: Comprehension principles only create tree-like structures
  • Unfortunately, some non-tree structures are useful

OWL (Web Ontology Language)

What is OWL?

• An ontology language
  • Can represent information about classes and properties
  • Can also represent information about individuals
• A Description Logic
  • Constructs are the standard Description Logic constructs
  • More expressive than currently implemented Description Logics
• Part of the Semantic Web
  • Has RDF/XML syntax
  • Uses RDF model theory
  • Uses much more of RDF than OIL, and more than DAML+OIL

Mike Dean, Guus Schreiber, Sean Bechhofer, Frank van Harmelen, Jim Hendler, Ian Horrocks, Deborah L. McGuinness, Peter F. Patel-Schneider, and Lynn Andrea Stein. OWL Web Ontology Language Reference. W3C Proposed Recommendation 2003.
Ian Horrocks and Peter F. Patel-Schneider. Reducing OWL Entailment to Description Logic Satisfiability. ISWC-2003.

The Semantic Web vs Description Logics

• Two syntaxes for OWL
  • One Description Logic style, for ease of use
  • One RDF/XML, to fit into Semantic Web
• Two semantics for OWL
  • One Description Logic style, to get things right
  • One RDF style, to fit into Semantic Web
• Three languages for OWL
  • OWL Full, allows all of RDF, but is undecidable
  • OWL DL, decidable fragment
  • OWL Lite, even smaller fragment

Ian Horrocks, Peter F. Patel-Schneider, and Frank van Harmelen. From SHIQ and RDF to OWL: The Making of a Web Ontology Language. Journal of Web Semantics, 2003.

OWL Knowledge Base Fragment (Revisited)

Taken from the OWL wine and food ontologies.

<owl:Class rdf:ID="WhiteWine">
  <owl:intersectionOf rdf:parseType="Collection">
    <owl:Class rdf:about="#Wine" />
    <owl:Restriction>
      <owl:onProperty rdf:resource="#hasColor" />
      <owl:hasValue rdf:resource="#White" />
    </owl:Restriction>
  </owl:intersectionOf>
</owl:Class>