CS6999 Presentation
Introduction to Description Logic
and Ontology Languages
Jidi (Judy) Zhao
October 4, 2015
Talk Outline
• Introduction to Ontologies
• Introduction to Description Logic (DL)
• Reasoning in DL
• Introduction to Ontology Languages: OWL
• Extensions of DL and Research Challenges
2
What is an ontology?

Many definitions have been given:




from Philosophy: “a systematic explanation of being”
Neches gives some guidelines: “…defines the basic
terms and relations including the vocabulary of a
topic area as well as the rules for combining terms
and relations to define extensions to the vocabulary.”
Gruber, the most quoted: “…an explicit specification
of a conceptualization”
An ontology defines the concepts used to describe
and represent an area of knowledge, as well as
relations among them.
3
Types of Ontologies

Top-level Ontologies

The Standard Upper Ontology (SUO):
http://suo.ieee.org/
4
Types of Ontologies

Top-level Ontologies

The Standard Upper Ontology (SUO):
http://suo.ieee.org/

WordNet:
http://wordnet.princeton.edu/



Sowa’s top-level ontology
Cyc’s upper ontology
Domain Ontologies






Thing
E-commerce
Medicine
Engineering
Enterprise
Chemistry
….
Living
5
Nonliving
Methodologies for Ontology Engineering


Building domain ontologies from huge
ontologies (SENSUS, Cyc, AKT,…)
OTK (On-To-Knowledge) Methodology


Univ. of Karlsruhe
Methontology

Univ. Politecnica de Madrid
6
Methontology: A Methodology for Building Ontologies
Methontology Ontology Development Process Life Cycle
(Fernández-López et al., 1997;1999)
7
Tools for Ontology Engineering

OilEd from University of Manchester


Ontolingua from KSL (Stanford University)


http://kmi.open.ac.uk/projects/webonto/
WebODE from UPM


http://protege.stanford.edu/
WebOnto from KMI (Open University)


http://ontoserver.aifb.unikarlsruhe.de/ontoedit/
Protégé from SMI (Stanford University)


http://www.isi.edu/isd/ontosaurus.html
OntoEdit from Karlsrhue Univ.


http://www-ksl.stanford.edu
OntoSaurus from ISI (USA)


http://oiled.man.ac.uk/
http://webode.dia.fi.upm.es/webODE/
KAON from AIFB and FZI at the University of Karlsruhe

http://kaon.semanticweb.org/
8
Talk Outline
• Introduction to Ontologies
• Introduction to Description Logic (DL)
• Reasoning in DL
• Introduction to Ontology Languages: OWL
• Extensions of DL and Research Challenges
9
Description Logic

Brachman and Levesque [1984] “there is a tradeoff
between the expressiveness of a representation language
and the difficulty of reasoning over the representations built
using that language”.


Description Logics




The more expressive the language, the harder the reasoning.
overcome the ambiguities of early semantic networks and frames
first realized in the system KL-One [Brachman and Schmolze, 1985]
Well-studied and decidable (most DL languages)
Tight coupling between theory and practice
Architecture of a DL System

from DL Handbook
DL Basics

Concepts (unary predicates/formulae with one free variable)


Roles (binary predicates/formulae with two free variables)


E.g., Mary, John
Constructors









E.g., hasChild
Individuals (constants)


E.g., Person, Female
Uniont, Intersectionu
Exists restriction9: 9hasChild.Doctor
Value restriction8: 8hasChild.Doctor
Complement /negation:: :Mother
Number restriction ≥n, ≤n
Inverse role (-): isChildOf ≡ hasChild–
transitive role (+): hasSister
Role hierarchy : hasDaughter v hasChild
Axioms


Subsumptionv: MothervParent
Assertion: Mary: Mother, Mary hasChild John
12
What does 8 R.C and 9 R.C mean?

A DogLover is someone whose pets are all
hasPet
dogs, in this case {C}
A
Fido
DogLover = 8 hasPet.Dog
{p | 8 a, (p, a) 2 hasPet ! a 2 Dog}
Also writen more simply as
{p | hasPet(p, a) ! Dog(a) }
A
Fluffy
B
Tabby
C
Rover
C
Flip
Cat
Fluffy
A DogLiker is someone who owns a dog ,
Dog
in this case {A, C}
Fido
Tabby

DogLiker = 9 hasPet.Dog
{p | hasPet(p, a) Æ Dog(a) }
This slide is from Dr. Bruce Spencer’s slides (2007).
Rover
Flip
The DL Family

Smallest propositionally closed DL is ALC
 Concepts constructed using boolean operators
t,u,:
plus restricted quantifiers
9,8
 Only atomic roles
E.g.,
Person u 8hasChild.(Doctor t 9hasChild.Doctor)
14
The DL Family (cont.)


S often used for ALC extended with transitive roles (R+)
Additional letters indicate other extensions, e.g.:







H for role hierarchy
O for nominals (e.g., {Mary, John})
I for inverse roles
N for number restrictions
Q for qualified number restrictions (e.g., ≥2hasChild.Doctor)
R for limited complex role inclusion axioms, role disjointness
ALC+ transitive role (R+)+role hierarchy (H) +O + I + Q =
SHOIQ
15
DL Semantics
 Semantics given by standard FO model theory
 The vocabulary is the set of names (consist of concepts and roles )
we use in our model of (part of) the world
 {Daisy, Cow, Animal, Person, Car, drives, …}
 An interpretation I is a tuple (I, •I)
 I is the domain (a set)
 •I is a mapping that maps:
 Names of objects (individuals/constants) to elements of I
 Names of unary predicates (classes/concepts) to subsets of I
 Names of binary predicates (properties/roles) to subsets of I ×I
16
DL Semantics
(adapted from Horrocks 2006)
Interpretation function •I
Individuals iI 2 I
Mary
John
Concepts CI µ I
Teacher
Student
Car
Roles RI µ I × I
hasChild
owns
(Teacher u Student)
17
Interpretation domain I
DL Knowledge Bases


A Knowledge Base (KB) <T,A>=
a Tbox + an Abox
A TBox (terminology) is a set of inclusion
axioms and equivalence axioms



the vocabulary of an application domain
e.g.: { Mother v Person,
GrandMother ≡ Person u 9hasChild.Parent }
An ABox (Assertion) is a set of assertions
about individuals


about named individuals in terms of this vocabulary
e.g.: {Mary: Mother, Anita hasChild Mary}
18
Talk Outline
• Introduction to Ontologies
• Introduction to Description Logic (DL)
• Reasoning in DL
• Introduction to Ontology Languages: OWL
• Extensions of DL and Research Challenges
19
Tableau Reasoning (1)

Key reasoning tasks





Satisfiability: asat(A), whether the assertions in a KB have a model
Instance checking: C(a)?
Concept satisfiability: C?
Retrieval: retrieve a set of individuals that instantiate C
Subsumption: B v A ?



Equivalence: A≡B? , B v A ? And A v B?
Reasoning tasks reducible to KB (un)satisfiability: asat(A)





A subsumes B if every individual of concept B is also of concept A.
Instance checking: instance(a, C, A) , :asat (A [ {a: :C})
Concept satisfiability: sat(C) , asat(A [ {a:C})
Concept subsumption:
C v D w.r.t. KB A , A [ {:D u C} is not satisfiable , :asat(A [ {a::D u C})
Retrieval:
check each individual in the Abox, reducible to instance checking
DL systems typically use tableau algorithms to decide the satisfiability
(consistency) of KB
20
Tableau Reasoning (2)





Tableau algorithms work by trying to construct a concrete example
(model) consistent with KB.
A KB A is satisfiable iff a fully expanded clash-free graph is
constructed.
Tableau reasoning contains a set of completion rules operating on
constraint sets or tableau
Clash: a clash is an obvious contradiction, e.g., A(x), :A(x)
Proof procedure:




start from assertions about individuals (ABox axioms)
unfold the TBox so that atomic concepts only appear on the right side of
axioms
transform all concepts into negation normal form (i.e. negation only
occurs in front of atomic concept names):

: (C u D) ! :C t :D

: 9R.C ! 8 R.:C
apply completion rules in arbitrary order as long as possible
 stops when a clash is found
 terminates if no completion rule is applicable
 A KB is satisfiable iff a clash-free tableau can be derived
21
CS6795 Semantic Web Techniques
Tableau Reasoning (3)
completion rules
22
Tableau Reasoning (5): Concept Subsumption
KB:
Reasoning task: mother v woman?
Exercise:
Is the concept : woman u mother satisfiable?
23
Tableau Reasoning (4): asat(A)




E.g., KB:
{HappyParent≡Person u ∀hasChild.(Doctor t 9hasChild.Doctor),
John:HappyParent, John hasChild Mary,
Mary: :Doctor, Wendy hasChild Mary, Wendy marriedTo John}
Person
∀hasChild.(Doctor t ∃hasChild.Doctor)

from Harrock, 2006
24
Tableau Reasoning (6)



Some completion rules are nondeterministic (e.g., 9 , ≤ ).
Blocking Strategies are often needed to ensure termination.
E.g., KB:
{Person v 9hasParent.Person,
John:Person}
25
Tableau Reasoning (7)

In general,
(representation of) model
consists of:


Named individuals forming
arbitrary directed graph
Trees of anonymous
individuals rooted in
named individuals
26
Tableau Reasoning (8)


Similar tableaux expansions can be designed for
more expressive DL languages.
A tableau algorithm has to meet three
requirements:



Soundness: if a complete and clash-free graph is
found by the algorithm, we can construct a model.
Completeness: Given a model, the algorithm can
always find an complete and clash-free graph
Termination: the algorithm can terminate in finite
steps with specific result.
Software for DL Reasoning
Pellet
CEL
KAON2
28
Efficiency of Tableau Reasoning
I can’t find an efficient algorithm, but neither can all these famous people.
NP-Complete Cartoons,
http://max.cs.kzoo.edu/~kschultz/CS510/ClassPresentations/NPCartoons.html
Talk Outline
• Introduction to Ontologies
• Introduction to Description Logic (DL)
• Reasoning in DL
• Introduction to Ontology Languages: OWL
• Extensions of DL and Research Challenges
30
Ontology Languages

Traditional Ontology Languages





Ontolingua and KIF
LOOM
OKBC
F-logic
Ontology Markup Languages





SHOE
RDF and RDF Schema
OIL
DAML+OIL
OWL
31
The Web Ontology Language OWL


Semantic Web led to requirement for a “web
ontology language”
set up Web-Ontology (WebOnt) Working
Group




WebOnt developed OWL language
OWL based on earlier languages OIL and DAML+OIL
OWL now a W3C recommendation
OIL, DAML+OIL and OWL based on Description
Logic
32
OWL

Three species of OWL




OWL DL Benefits from many years of DL
research





OWL full is the union of OWL syntax and RDF
OWL DL restricted to FOL fragment (is equivalent to
SHOIN(Dn) DL)
OWL Lite is an “easier to implement” subset of OWL
DL
Well defined semantics
Formal properties well understood (complexity,
decidability)
Known reasoning algorithms
Implemented systems (highly optimised)
Adapted from ENC 2004 Tutorial by Peter F. Patel-Schneider
33
OWL RDF/XML Exchange Syntax
E.g., Person u ∀hasChild.(Doctor t ∃hasChild.Doctor):
<owl:Class>
<owl:intersectionOf rdf:parseType=“collection">
<owl:Class rdf:about="#Person"/>
<owl:Restriction>
<owl:onProperty rdf:resource="#hasChild"/>
<owl:allValuesFrom>
<owl:unionOf rdf:parseType=“collection">
<owl:Class rdf:about="#Doctor"/>
<owl:Restriction>
<owl:onProperty
rdf:resource="#hasChild"/>
<owl:someValuesFrom
rdf:resource="#Doctor"/>
</owl:Restriction>
</owl:unionOf>
</owl:allValuesFrom>
</owl:Restriction>
</owl:intersectionOf>
</owl:Class>
34
Class/Concept Constructors
35
Ontology Axioms

OWL ontology equivalent to DL KB (Tbox +
Abox)
36
Talk Outline
• Introduction to Ontologies
• Introduction to Description Logic (DL)
• Reasoning in DL
• Introduction to Ontology Languages: OWL
• Extensions of DL and Research Challenges
37
Extensions of DL






Combinations of DL and Logic Programs (LP)
Uncertainty extension of DL
Concrete domain constraints
Modal, epistemic, and temporal operators
Open world vs. close world
…..
38
Venn Diagram of DL, LP, and FOC
39
Motivation(1)



DL cannot represent “more than one free variable at a
time”.
(1) A rule involving multiple variables. E.g.,
Man(?X) ∧ Woman(?Y)
!PotentialFriendshipBetween(?X,?Y).
(2) Chaining to derive values of Properties. E.g.,
Father(?X,?Y) ∧ Father(?Y,?Z)! Grandfather(?X,?Z). (not allowed in
SHOIN)
Work(?X, ?Y) ∧ Live(?X, ?Z) ∧ Loc(?Y,?W) ∧ Loc(?Z,?W)
!HomeWorker(?X).
Y
Work
Loc
X
Live
Loc
Z
W
40
Motivation(2)
•Horn Logic cannot represent a (1) disjunction
or (2) existential in the head.
•(1) State a subclass of a complex class
expression which is a disjunction. E.g.,
(Human u Adult) v (Man t Woman)
•(2) State a subclass of a complex class
expression which is an existential. E.g.,
Radio v 9hasPart.Tuner
41
Different approaches
1. Approaches reducing description logics to logic programs
A. DLP
B. OWL 2 RL
2. Homogeneous approaches
A. OWL Rules
B. SWRL
3. Hybrid approaches accessing description logic through
queries in logic programs
A. AL-Log
42
Uncertainty extension of DL
 Handling uncertain knowledge is becoming a critical
research direction for the (Semantic) Web.
 knowledge on the Web is often uncertain and imprecise.
 E.g., many concepts needed in business domain
ontology modeling lack well-defined boundaries or,
precisely defined criteria of relationship between
concepts
 Domain modeling and Ontology reasoning
 Quantify degree of an individual belonging to a class
 Quantify degree of subsumption between a class and its
subclasses
 Concept mapping between ontologies
 Quantify degree of alignment between classes of two
ontologies
43
URW3 Situation Report: uncertainty
ontology

URW3
44
44
Probability, Possibility and Fuzzy logic

Probabilistic Description Logic:



Fuzzy Description Logic:



Statistical information
e.g. John is a student with the probability 0.6 and a
teacher with the probability 0.4
Express vagueness and imprecision
e.g. John is tall with the degree of truth 0.9
Possibilistic Description Logic:


Particular rankings and preferences
e.g. John prefers an ice cream to a beer
45
Research Challenges






Syntax and Semantics
Decidability
Reasoning algorithms for possible
extensions
Soundness and completeness
Complexity/efficiency
Effective methods for reasoning
under uncertainty
46
Questions?
Descargar

幻灯片 1