Description Logics & OWL

Hideaki Takeda
takeda@nii.ac.jp
National Institute of Informatics
Hideaki Takeda / National Institute of Informatics

Types of Ontologies
Upper (top-level) ontology vs. Domain ontology
n Upper Ontology: A common ontology throughout all domains
n Domain Ontology: An ontology which is meaningful in a specificdomainl Object ontology vs. Task ontology
n Object Ontology: An ontology on “things” and “events”
n Task Ontology: An ontology on “doing”
lHideaki Takeda / National Institute of Informatics

A Layer model for Semantic Web
l

l

l

OWL
n General concept description language
u Logical consistencyu Various class expressionsu Various constraints
RDF Scheman Addition of “concept” to RDF
u class-subclass, constraints
RDF (Resource Description Framework)
n The primitive model for metadata description
u SVO modelu Entity-Relation Modelu Semantic net

Tim Berners-Lee http://www.w3.org/2002/Talks/09-lcs-sweb-tbl/
Hideaki Takeda / National Institute of Informatics

Conceptualization
objecton_desk(A)on(A, B)put(A,B)box

red boxobjectbox

on_desk(A)on(A, B)put(A,B)box
color:{red, blue, yellow}

blue box yellow box

objectboxon(A/box, B/object)put(A/box,B/object)

desk
box
color:{red, blue, yellow}

There are many possible ways to conceptualize the target world
Trade off between generality and efficiency
Hideaki Takeda / National Institute of Informatics

Ontology in Information System
An ontology is an explicit specification of a conceptualization[Gruber]l An ontology is an explicit specification of a conceptualization. The term isborrowed from philosophy, where an Ontology is a systematic account of
Existence. For AI systems, what "exists" is that which can be represented.
When the knowledge of a domain is represented in a declarative
formalism, the set of objects that can be represented is called the universeof discourse. This set of objects, and the describable relationships among
them, are reflected in the representational vocabulary with which aknowledge-based program represents knowledge. Thus, in the context ofAI, we can describe the ontology of a program by defining a set ofrepresentational terms. In such an ontology, definitions associate the namesof entities in the universe of discourse (e.g., classes, relations, functions, orother objects) with human-readable text describing what the names mean,
and formal axioms that constrain the interpretation and well-formed use of
these terms. Formally, an ontology is the statement of a logical theory.
Hideaki Takeda / National Institute of Informatics

Description LogicllWhat is Description Logic?
n Representation for structured knowledge
levelu Concepts, relations between concepts,
inheritanceis-an Logical formalization
History

Semantic Networks[Quillian66]- nodes, association- mixture of representation levels- no semantics

KL-ONE
Frames[Minsky81]- concepts, slots, (facets)- object-oriented- mixture of descriptions and assertions- not good semantics[Brachman78]- concepts, roles, inheritance- separation from logical/conceptual
levelsDL formalization[Brachman&Levesque84]- formal semantics- tradeoff of expressiveness andcomputational complexity- various languages and implementations
Hideaki Takeda / National
Institute of Informatics
LOOM, CLASSIC, KRISConcept

Personv/r(1,∞)

FemaleWoman

hasChild

ParentMother

Hideaki Takeda / National Institute of Informatics

Thingv/r

Date

sendDate (1,1)
v/rsender(1,1)

message
(1,1)
v/r

Mail

Text

Personreceiver(1,NIL)v/r

Mail ⊑ Thing ⊓"sendDate.Date ⊓ "sender.Person⊓ "receiver.Person ⊓ "message.Text

Hideaki Takeda / National Institute of Informatics

Thingv/r

Date

sendDate (1,1)
v/rsender(1,1)

message
(1,1)
v/r

Mail

Personv/r

receiver(1,NIL)Private
Mail

Text

(1,1)

Hideaki Takeda / National Institute of Informatics

Thingv/r

Date

sendDate (1,1)
v/rsender(1,1)

message
(1,1)
v/r

Mail

Personreceiver(1,NIL)

Business
Mail

Text

v/r

Business
PeopleHideaki Takeda / National Institute of Informatics

Thingv/r

Date

sendDate (1,1)
v/rsender(1,1)

message
(1,1)
v/r

Mail

Personv/r

receiver(1,NIL)
Business
Mail

Confidential
Mail

Text

Business
People(1,1)

Hideaki Takeda / National Institute of Informatics

Elements of Description Logic
l

l

l

l

Concepts: entities and classes
u Personn Unary predicates in FOL
u {x | Person(x)}, lx.Person(x)Roles: properties and relations
u haschildn 2-ary predicates in FOLu {x, y | hasChild(x, y)}Constructors for concept expression: conjunction(⊓), union(⊔)
u Person ⊓ $hasChild.Femaleu {x | Person(x) Ù $y.haschild(x, y) Ù Female(y)}Individuals: instances of concepts, co-reference to objects in the worldn Ex, Takeda, s1234

Hideaki Takeda / National Institute of Informatics

Constructors for concept expression
FL-

AL*

Constructors

SyntaxSemantics

ConceptCC I Í DI

Role nameR

R I Í DI ´ DI

Conjunction

C⊓DCI ⋂ DI

Value restriction"R.C{x Î DI | "y.(x,y) Î RI Þ y Î CI }Existential quantification $ R{x Î DI | $ y.(x,y) Î RI}

Negation

¬C

DI

Top

^

DI

Bottom^Æ

Disjunction

C⊔DCI ⋃ DI

Existential restriction$ R.C{x Î DI | $ y.(x,y) Î RI Ù y Î CI }Number restriction( ⩾ n R){x Î DI | |{y| y.(x,y) Î RI | ³ n}Collection of individuals

I, a I, …}/ National Institute of Informatics{a1, a2, …} Hideaki{a1Takeda
2/

CIVariety of Description Logicsl

ALC is the smallest propositionally closed DL
n – Concept operators: ⋂, ⋃, ¬, ", $n – No role operators (only atomic roles)
n – Concept axioms: ⊑, ≡n – No role axioms

http://www.cs.ox.ac.uk/ian.horrocks/Seminars/download/oracle-seminar-20101210.pdf
Hideaki Takeda / National Institute of Informatics

Variety of Description Logicsl

S used for ALC extended with (role) transitivity axioms

Additional letters indicate various extensions, e.g.:n H for role hierarchy (e.g., hasDaughter ⊑ hasChild)n R for role box (e.g., hasParent ⊓ hasBrother ⊑ hasUncle)
n O for nominals/singleton classes (e.g., {Italy})n I for inverse roles (e.g., isChildOf ≡ hasChild-)n N for number restrictions (e.g., ⩾2 hasChild, ⩽3 hasChild)n Q for qualified number restrictions (e.g., ⩾ 2 hasChild.Doctor)
n F for functional number restrictions (e.g., ⩽ 1 hasMother)l E.g., SHIQ = S + role hierarchy + inverse roles + QNRsl SHOIN = S + role hierarchy + nominals + inverse roles + NR
l SHIF = S + role hierarchy + inverse roles + FNRl

Hideaki Takeda / National Institute of Informatics

Semantics
Interpretation I consists of the domain of discourse DI (non emptyset) and interpretation function I
n I mapsu Concept C to CI Í DI
u Role R to RI Í DI´ DI
l A model for C is an interpretation where CI is not emptyl A concept C is satisfiable if it has a model for Cl

Hideaki Takeda / National Institute of Informatics

TBox & ABoxlllKnowledge Base S = <TBox, ABox>
TBox
n Conceptual or terminological knowledge
n Intensional knowledge
n General knowledge
n Examples
u Woman º Person ⊓ Femaleu Parent º Person ⊓ $ hasChild.Person ⊓ " hasChild.Personu Mother º Female ⊓ Parent(1,∞)
Personv/r
ABox
hasChildn Instance or assertional knowledge
Femalen Extensional knowledge
n Knowledge in a situaion
Woman
Parentn Examples
u Woman(Sazae)
Motheru hasChild(Sazae, Tara)
Hideaki Takeda / National Institute of Informatics

ReasoninglSubsumptionn Concept satisfiablity: S ⊭ C º ^n Concept Subsumption: S ⊨ C ⊑ D or S ⊨ C ⊓ ¬Dº ^n Inconsistency:
n Ex.)
u Mother ⊑ Woman
Personv/rFemale
Woman
MotherhasChild

ParentHideaki Takeda / National Institute of Informatics

Structural Subsumption AlgorithmlNormalization (Conjunctive normal form)nnlMother= Person ⊓ Female ⊓ "hasChild.Person
SMother= Person ⊓($hasChild ⊓ "hasChild.Person) ⊓ Female ⊓ " hasChild.Student= Person ⊓ Female ⊓ $ hasChild ⊓ " hasChild.(Person ⊓ Student)

Compare each termn C subsumes D if each term Ci Î C satisfies:u If Ci is atomic or $R, then there is Dj with Dj=Ci
u If Ci is "R.C’, then there is a Dj with Dj= "R.D’ and C’
subsumes D’Liner complexity and soundl Complete only for FLl

Hideaki Takeda / National Institute of Informatics

Tableau algorithms
Check satisfiability of concept descriptionsn Assume an instance b which satisfies all the descriptionsn Then check whether this assumption turns out impossibleu The assumption is wrong -> not satisfiable
l For NNF (Negation Nomarl Form)n Negation appears only just before concepts
l Completion rules
n Adding constraints by interpreting terms
n Derive contradictionlHideaki Takeda / National Institute of Informatics

Tableau algorithmslCompletion rulesn ⊓ -rule:u Condition: S contains (C ⊓ D)(x) and does not contains both C(x) and D(x)u Action: S’=S ⊔{C(x), D(x)}n ⊔ -rule:u Condition: S contains (C ⊔ D)(x) and neither C(x) nor D(x)u Action: S’=S ⊔{C(x)} or S’=S ⊔{D(x)}n $-rule:
u Condition: S contains ($R.C)(x) and no individual z such that satisfy C(z)and R(x,z) in S
u Action: S’=S ⊔{C(y),R(x,y)}n "-rule:
u Condition: S contains ("R.C)(x) and R(x,y), and does not contain C(y)u Action: S’=S ⊔{C(y)}Hideaki Takeda / National Institute of Informatics

Sumsumption by Tableau algorithms
Unfold Tbox T to T’n Remove defined concepts by applying their definition in T
u Pick up B such as AºB in T
u Replace A’ such as A’ºB’ with B’ in B recursivelyl Remove defined concepts by applying their definition in C ⊓¬D
u Pick up A such as AºB in C ⊓¬D
u Replace A with B
l Transform C ⊑ D to C ⊓¬Dl Transform C ⊓ ¬D into NNF (Negation Normal Form)l Check C ⊓ ¬D by Tableau algorithmlHideaki Takeda / National Institute of Informatics

Tableau algorithms: An exmplelll

Dmom ⊑ Mother ?
Tn Woman º Person ⊓ Femalen Parent º Person ⊓ $ hasChild.Person ⊓ " hasChild.Person
n Mother º Female ⊓ Parentn Dmom º Woman ⊓ $ hasChild.Woman ⊓ " hasChild.Woman
T’
n
n
n

Woman º Person ⊓ Female
Parent º Person ⊓ $ hasChild.Person ⊓ " hasChild.Person
Mother º Female ⊓ Person ⊓ $ hasChild.Person ⊓ " hasChild.Person

Dmom º Person ⊓ Female ⊓ $ hasChild.(Person ⊓ Female) ⊓ " hasChild. (Person ⊓ Female)Transform C ⊑ D to C ⊓ ¬Dn Dmom ⊓ ¬Mother
Remove defined concepts
n Person ⊓ Female ⊓ $ hasChild. (Person ⊓ Female) ⊓ " hasChild. (Person ⊓ Female) ⊓ ¬(Female⊓ Person ⊓ $ hasChild.Person ⊓ " hasChild.Person)
NNF
n Person ⊓ Female ⊓ $ hasChild. (Person ⊓ Female) ⊓ " hasChild. (Person ⊓ Female) ⊓ (¬Female⊔ ¬Person ⊔ "¬hasChild.Person ⊔ $ ¬hasChild.Person)
n

l

l

l

Hideaki Takeda / National Institute of Informatics

An examplelS0={x: Person ⊓ Female ⊓ $ hasChild. (Person ⊓ Female) ⊓ " hasChild. (Person ⊓ Female) ⊓(¬Female ⊔ ¬Person ⊔ "¬hasChild.Person ⊔ $ ¬hasChild.Person)}n⊔-rulen

S1=S0 ⊔ {x: ¬Female}= ^nS1’’= S0 ⊔ {x: ¬Person}= ^nS1’’’= S0 ⊔ {x: "¬hasChild.Person }(1)unn⊓-ruleS2=S1’’’ ⊔ {x: Person ⊓ Female ⊓ $ hasChild. (Person ⊓ Female), x:" hasChild. (Person ⊓Female)}u $-rule
S3=S2 ⊔ {y: Person ⊓ Female, (x,y): hasChild}u ⊓ -rulen

S4=S3 ⊔{y:Person, y:Female}n"-rule (for (1))
S5= S4 ⊔ {y: ¬Person}= ^nS1’’’’= S0 ⊔ {x: $ ¬hasChild.Person }

u

u

….

Hideaki Takeda / National Institute of Informatics

OWL(Web Ontology Language)lllMore general knowledge representation
Based on Description Logics
Featuresn Classu Necessary condition / necessary and sufficient conditionu Class expression:l Constraint by property
n Like slot definition of a classn Type constraint (all/some), cardinality, typed cardinalityl Logical operation of classes: union, intersection, negationn Propertyu Multiple ranges and domains
u Specifying meta-property
n Import of definitions
Hideaki Takeda / National Institute of Informatics

Class descriptions
a class identifier (a URI reference)l an exhaustive enumeration of individuals that together form theinstances of a classl a property restriction
l the intersection of two or more class descriptions
l the union of two or more class descriptions
l the complement of a class descriptionlHideaki Takeda / National Institute of Informatics

OWL: InstanceslInstance
n Instance for a class or propertyn rdf:type:Mary rdf:type :Person .
l Equality and Inequality of Individuals:John owl:differentFrom :Bill .
:James owl:sameAs :Jim.

Hideaki Takeda / National Institute of Informatics

l

OWL

Class axioms
n rdfs:subClassOf
n owl:equivalentClassn owl:intersectionOf!"#$%&'()*+!+,-./%++0* !12$%/2'3!4,$%&'#5/!26,78%/2&9./%++ !:2(+#&'3!;#9<2('()*+!+,-./%++0* =()*!9>?2 #5/!./%++ @#5/!,&7#&0* A'!12$%/2'!:%(2&9B

FemalePersonWoman

v/r

hasChild

ParentMother
Hideaki Takeda / National Institute of Informatics

OWL
Object Properties:John :hasWife :Mary .
l Data properties
n :John:hasAge 51 .
l Property hierarchy:hasWife rdfs:subPropertyOf :hasSpouse .
l Domain and rage
:hasWife rdfs:domain :Man ;rdfs:range :Woman .
:hasAge rdfs:domain :Person ;rdfs:range xsd:nonNegativeInteger .
l

Hideaki Takeda / National Institute of Informatics

OWLl

Property restrictionn A special kind of class description. It describes an anonymous class, namely aclass of all individuals that satisfy the restriction

Hideaki Takeda / National Institute of Informatics

OWL: Value constraintsll

A restriction class to either a class description or a data range
owl:allValuesFromnl

owl:someValuesFromnl

All individuals must satisfy the specific condition (class or data range)

At least one property value must satisfy the specific condition

owl:hasValuen:HappyPerson rdf:type owl:Class ;owl:equivalentClass [rdf:type owl:Restriction ;owl:onProperty :hasChild ;owl:allValuesFrom :Happy] .
:Parent owl:equivalentClass [rdf:type owl:Restriction ;owl:onProperty :hasChild ;owl:someValuesFrom :Person] .

Constrain the value as the specific individual:JohnsChildren owl:equivalentClass [rdf:type owl:Restriction ;owl:onProperty :hasParent ;owl:hasValue :John
Hideaki] . Takeda / National Institute of Informatics

OWL: Cardinality constraintsll

to allow only a specific number of values
owl:maxQualifiedCardinalityn

A restriction containing an owl:maxQualifiedCardinality constraint
describes a class of all individuals that have at most N semantically distinct
values:John rdf:type [rdf:type owl:Restriction ;owl:maxQualifiedCardinality "4"^^xsd:nonNegativeInteger ;owl:onProperty :hasChild ;owl:onClass :Parent
] .

l
l

owl:minQualifiedCardinality
owl:qualifiedCardinality

Hideaki Takeda / National Institute of Informatics

l

Cardinality Constraint

OWL
FemalePersonWoman

v/r

hasChild

ParentMother:Parent rdfs:quivalentClass [rdf:type owl:Restriction ;owl:onProperty :hasChild ;ow:allValuesFrom :person ;owl:minQualifiedCardinality ”1"^^xsd:nonNegativeInteger ;owl:onClass :person] .

Hideaki Takeda / National Institute of Informatics

OWL Families
OWL liten SHIF(D) = SHIF + Datatypel OWL DLn SHOIN(D) = SHOIN + Datatypel OWL Fulln OWL + RDFS
n Eg.,
u Owl:class vs rdfs:classu Owl:ObjectTypeProperty and rdf:PropertylHideaki Takeda / National Institute of Informatics

http://ragrawal.wordpress.com/2007/02/20/difference-between-owl-lite-dl-and-full/

Difference among Lite, DL, and Full
Lite

DL

Full

Compatibility
with RDF

Theoretically, no rdf document
can be assumed to be compatible
with OWL Lite

Theoretically,no rdf document can beassumed to be compatible with OWL DL

All valid rdf documents are OWL fullRestrictions onclass definition

Requires separation of classes,
instances, properties, and data
valuesRequires separation of classes, instances,properties, and data values

Classescan be instances or properties at the same time. For
example, it is perfectly legal in OWL Full to have a“Fokker-100″ identifier which acts both as a class name(denoting the set of Fokker-100 airplanes flying around theworld) and as an individual name (e.g., an instance ofthe class AirplaneType).

RDF Mixing

Restricts
mixing of rdf and owl constructs

Restricts
mixing of RDF and OWL constructs

Freely allows mixing of RDF and OWL constructs

Classes
Descriptions

The only class description
available in OWL lite isIntersectionOf

Classescan be described as UnionOf ,ComplementOf, IntersectionOf, andenumeration
Eg: class can be exhaustively defined by its
instances. For example defining a class
DaysOfWeek exhaustively by Sun, Mon,
Tue, Wed, Thurs,
Fri, SatClasses can be UnionOf, ComplementOf, IntersectionOf,
and enumeration Eg:
class can be exhaustively defined by its instances. For
example defining aclass DaysOfWeek exhaustively by Sun, Mon, Tue, Wed,
Thurs, Fri, Sat

Hideaki Takeda / National Institute of Informatics

l

RDF Schema Features:
n
n
n
n
n
n
n

l

l

Class (Thing, Nothing)rdfs:subClassOf
rdf:Property
rdfs:subPropertyOf
rdfs:domain
rdfs:range
Individual

n
n
n
n
n

equivalentClassequivalentProperty

Property Restrictions:
n
n
n
n

l

n
n

l

sameAsdifferentFrom
AllDifferent
distinctMembers

Restriction
onProperty
allValuesFrom
someValuesFrom

l
l

n
n

Ontology
imports

n
n
n
n
n

l

n
n
n
n
n

ObjectProperty
DatatypeProperty

n

n
n
n
n
n
n

inverseOf
TransitiveProperty
SymmetricProperty
FunctionalProperty
InverseFunctionalPropertylversionInfo
priorVersion
backwardCompatibleWith
incompatibleWith
DeprecatedClass
DeprecatedProperty

Annotation Properties:

Property Characteristics:nIntersectionOf

Versioning:nminCardinality (only 0 or 1)
maxCardinality (only 0 or 1)
cardinality (only 0 or 1)

Header Information:

Class Intersection:nRestricted Cardinality:n(In)Equality:nl

OWL Literdfs:label
rdfs:comment
rdfs:seeAlso
rdfs:isDefinedBy
AnnotationProperty
OntologyProperty

Datatypesn

xsd datatypes

Hideaki Takeda / National Institute of Informatics