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


by Peter F. Patel-Schneider

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?

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

Formalization of KL-ONE

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)

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?

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]
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

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.
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

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

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?

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]

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

Results for K_dum_n

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)

Results for S4_S5_p

A problem set where backjumping and semantic branching are most effective.
S4_S5 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]
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

Results modal depth 1 (old)

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)

Results modal depth 2 (old)

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

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

Results modal depth 2 (new)

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

Moving to the Semantic Web

Initial Steps towards the Semantic Web


<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

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

Semantic Web Tower

 
 
 
 
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]

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)

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)

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)

Problems with Living in the Semantic Web (Part 3)

OWL (Web Ontology Language)

What is OWL?
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

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>

OWL Knowledge Base Fragment (Revisited)

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) ∩ ...

What Can OWL Do?

Given an Ontology:

  • Determine implicit subsumption relationships between classes
    • Reisling ≤ WhiteWine
  • Determine where a new description/individual fits
    • CorbansDryWhiteRiesling ∈ WhiteWine
  • Determine when a description is incoherent
    • Wine ∩ (≤ 0 hasColor)
  • Determine when an ontology is inconsistent
    • CorbansRedRiesling ∈ Riesling ∩ (hasColor : Red)

The End?

  • Not really
  • What needs to be done?
    • Inference
      • Characterizing inference in OWL-DL (in progress)
      • Optimizations for OWL
    • Systems
      • Real implemented systems for OWL
      • Evaluating OWL systems
    • Surround
      • Explanation, Query, Learning, ...
    • Usage
      • Ontologies, Data, ...

A Differing Vision of The Semantic Web

  • Vision based on single RDF-based syntax and semantics causes severe problems
  • So, allow for different syntaxes
    • One for RDF and RDFS
    • One for an ontology language
    • One for rules
    • One for XML data
    • One for ...
  • And tie them all together with semantics
    • Different semantics should be compatible
    • Semantics for the ontology language would also provide compatible semantics for (part of) the RDF syntax
Peter Patel-Schneider and Jerome Simeon. The Yin/Yang Web: A Unified Model for XML Syntax and RDF Semantics. IEEE TKDE 15(3), 2003, pages 797–812.
Ian Horrocks and Peter F. Patel-Schneider. Three Theses of Knowledge Representation in the Semantic Web. The Twelfth International World Wide Web Conference. Budapest, Hungary, May 2003, ACM Press, pp. 39–47.

My Future Research (Proposed)

  • Build system for OWL
    • Characterize inference in OWL
    • Optimize inference algorithm for OWL
    • Evaluate performance (on real data, hopefully)
  • Investigate alternative computing models for inference
    • Lots of opportunities for parallelism
      • Fine-grained - subset testing
      • Medium-grained - and/or searching
      • My provers are mostly-functional - does this help in building parallel hardware?
  • Integrate reasoning and learning into a cognitive system
    • Learn OWL concepts (probably many concepts)
    • Use learned concepts in applications
    • Retain learned concepts that were useful, discard the rest
    • Which application—web service composition???